1. elıadás
1. elıadás
Az elıadás
Elosztott rendszerek
• Tankönyv: Andrew S. Tanenbaum – Maarten van Steen: Elosztott Rendszerek Alapelvek és Paradigmák
1. Bevezetés
Az elosztott rendszer definíciója
• http://people.inf.elte.hu/bonnie
[email protected]
Köztesrétegként felépülı elosztott rendszer
Az elosztott rendszer az önálló számítógépek olyan összessége, amely kezelıi számára egyetlen koherens rendszernek tőnik.
Célok • Felhasználók és erıforrások összekapcsolása • Átlátszóság • Nyitottság
1.1
Felhasználók és erıforrások összekapcsolása • Távoli erıforrások elérése • Más felhasználókkal ellenırzött módon való megosztás
• Átméretezhetıség
1
1. elıadás
Nyitottság
Átlátszóság az elosztott rendszerekben Átlátszóság
Leírás
Hozzáférhetıség (Access)
Elrejti az erıforrás elérésének mikéntjét és az adatábrázolási különbözıségeket.
Elhelyezkedés (Location)
Elrejti az erıforrás fizikai elhelyezkedését.
Áthelyezhetıség (Migration)
Elrejti az erıforrás más helyre való áthelyezhetıségét.
Mozgathatóság (Relocation)
Elrejti a használatban lévı erıforrás más helyre való mozgathatóságát.
Többszörözhetıség (Replication)
Elrejti az erıforrás többszörözöttségét.
Egyidejőség (Concurrency)
Elrejti az erıforrás több versenyhelyzető felhasználó közötti megoszthatóságát.
Meghibásodás (Failure)
Elrejti az erıforrás meghibásodását és újbóli üzembe helyezését.
Állandóság (Persistence)
Elrejti, hogy a (szoftver) erıforrás a memóriában vagy a háttértárolón van-e.
Átméretezhetıségi problémák Koncepció
Példa
Központosított szolgáltatás
Egy kiszolgáló minden felhasználó számára
Központosított adat
Egyetlen on-line telefonkönyv adatbázis
Központosított algoritmus
A teljes információn alapuló útválasztás
Mintapéldák az átméretezhetıség korlátaira
Az átméretezés technikája (1)
• Szolgáltatások jól definiált szintaktikai és szemantikai szabályoknak megfelelıen • Együttmőködés • Hordozhatóság • A megvalósítás és a módszer szétválasztása
Decentralizált algoritmusok • Egyetlen gépnek sincs teljes információja a rendszer állapotáról. • A gépek kizárólag helyi információk alapján hoznak döntéseket. • Egyetlen gép meghibásodása sem okozza az algoritmus leállását. • Még közvetett módon sem feltételezi bármiféle globális óra meglétét.
Az átméretezés technikája (2)
1.5 1.4
Miként különbözik a) a szerver, vagy
Példa a DNS-névtér zónákra osztása
b) a kliens által végzett őrlap ellenırzés az őrlap kitöltése közben
2
1. elıadás
Szoftverkoncepciók Rendszer
Leírás
Egyprocesszoros operációs rendszerek Fı cél
DOS (Distributed Operating Systems)
Többprocesszoros és homogén multiszámítógépek szorosan csatolt operációs rendszere
Hardvererıforrások elrejtése és kezelése
NOS (Network Operating Systems)
Heterogén multiszámítógépek (LAN és WAN) gyengén csatolt operációs rendszere
Helyi szolgáltatások távoli kliensek számára elérhetıvé tétele
Köztesréteg
A NOS fölötti, általános célú szolgáltatásokat implementáló újabb réteg
Elosztottsági átlátszóság biztosítása
Az operációs rendszer és az alkalmazások elválasztása a mikrokernel használatával
Többprocesszoros operációs rendszerek (2)
Többprocesszoros operációs rendszerek (1)
monitor Counter {
monitor Counter {
private:
private: int count = 0; public:
int count = 0;
void decr() {
int blocked_procs = 0;
if (count ==0) {
wait (unblocked);
public:
blocked_procs = blocked_procs – 1;
int value () { return count;}
int value() { return count;}
}
void incr () {
void incr () { count = count + 1;}
else
if (blocked_procs == 0)
void decr() { count = count – 1;}
count = count – 1;
count = count + 1; else
}
signal (unblocked);
Az egész számot az egyidejő eléréstıl megvédı monitor
blocked_procs = blocked_procs + 1;
condition unblocked;
} }
}
Egyidejő elérés ellen védett egész számot megvalósitó monitor, amely képes blokkolni a hívó folyamatokat
Multiszámítógépes operációs rendszerek (1)
Multiszámítógépes operációs rendszerek (2)
A blokkolás és a pufferelés lehetséges esetei üzenetátadáskor
3
1. elıadás
Multiszámítógépes operációs rendszerek (3) Szinkronizációs pont Küldı blokkolása amíg a puffer tele
Küldı puffer
Elosztott, közös memóriájú rendszerek a)
A címtartomány lapjainak elosztása négy gép között
b)
A kialakult helyzet, miután CPU 1 a 10. lapra hivatkozott
c)
A kialakult helyzet, ha a 10. lap csak olvasható, és többszörözést is használunk
Megbízható-e a kommunikáció?
Van
Nem feltétlenül
Küldı blokkolása az üzenet elküldéséig
Nincs
Nem feltétlenül
Küldı blokkolása az üzenet megérkezéséig
Nincs
Kötelezıen
Küldı blokkolása az üzenet kézbesítéséig
Nincs
Kötelezıen
A blokkolás a pufferelés és a megbízható kommunikáció összefüggése
Hálózati operációs rendszerek (1)
Hálózati operációs rendszerek (2)
A hálózati operációs rendszer általános felépítése
Egy szerver és két kliens a hálózati operációs rendszerben.
Hálózati operációs rendszerek (3)
A köztesréteg helyének kiválasztása
A különbözı kliensek a szervereket különbözı helyre Szerelhetik fel.
A köztesrétegként megvalósított elosztott rendszer általános felépítése.
4
1. elıadás
A köztesréteg és a nyitottság
A rendszerek összehasonlítása Szempont
Átlátszóság foka Azonos operációs rendszer minden csomóponton? Operációs rendszer másolatok száma
A nyitott köztesréteg alapú elosztott rendszerben mind a köztesrétegek által használt protokollnak, mind pedig az alkalmazásokhoz kapcsolható interfészüknek meg kell egyeznie.
Elosztott operációs rendszer
Hálózati operációs rendszer
Köztesréteg alapú elosztott rendszer
Magas
Alacsony
Magas
Igen
Nem
Nem
Többprocesszoros
Multiszámítógépes
Nagyon magas Igen 1
N
N
N
Kommunikáció alapja
Közös memória
Üzenetek
Állományok
Modellfüggı
Erıforráskezelés
Globális, központi
Globális, elosztott
Csomópontonként
Csomópontonként
Nincs
Közepes
Igen
Változó
Zárt
Zárt
Nyitott
Nyitott
Átméretezhetıség Nyitottság
5
2. előadás
Kommunikáció
2. előadás •
Kommunikáció
•
1. rész
•
Többrétegű protokollok előnyei
•
Kapcsolat-orientált / kapcsolat nélküli
Szabályok – protokollok •
ISO OSI
Protokollrétegek (1)
Protokollrétegek (2)
Az OSI-modell szintjei, interfészei és protokolljai.
A hálózaton megjelenő tipikus üzenet szerkezete.
Fizikai réteg • •
„A” és „B” folyamatnak meg kell egyeznie a bitek jelentésében
Adatkapcsolati réteg (2)
0/1 átvitelének módjai Feszültség, küldés sebessége, stb.
Adatkapcsolati réteg • • •
Meghibásodást fedi el Adatkeretek Ellenőrző összeg
A küldő és a fogadó közötti párbeszéd az adatátviteli rétegben.
1
2. előadás
Kliens-szerver TCP
Hálózati réteg • •
Útvonalválasztás IP – Internet Protocol
Szállítás • • • • •
Csomagok elveszhetnek Megbízható kapcsolatot épít TCP – Transmission Control Protocol UDP – Universal Datagram Protocol RTP – Real-time Transport Protocol
Viszony- és megjelenítési rétegek • •
a) b)
Köztesréteg protokoll (1) •
Logikailag az alkalmazási rétegbe tartozik, de tartalmaz általános célú protokollokat
Párbeszéd vezérlése Bitek jelentése •
Köztesréteg szolgáltatásait támogató protokollok • • • •
Alkalmazási réteg • •
A TCP normál működése Tranzakciós TCP
FTP – File Transfer Protokoll vs. ftp-program Köztesréteg-protokoll •
Azonosító Jogosultságok Véglegesítő protokoll Elosztott zárolási protokoll
Magas szintű kommunikációs szolgáltatások: RPC, RMI
Köztesréteg protokoll (2)
RPC • •
Remote Procedure Call Elrejti a kommunikáció tényét
•
Hagyományos eljáráshívás count = read(fd, buf, nbytes); •
Érték szerinti / hivatkozás szerinti paraméterátadás
A hálózatos kommunikáció módosított hivatkozási modellje.
2
2. előadás
Hagyományos eljáráshívás
a) b)
Paraméter-átadás helyi eljáráshívás esetén: a verem állapota a „read” függvény meghívása előtt A verem állapota a hívott eljárás futása közben
Távoli eljárás hívása során végrehajtandó lépések A kliensfolyamat hagyományos módon meghívja a kliensoldali eljáráscsonkot. 2. A csonk felépíti az üzenetet, és meghívja a helyi op. rsz.-t. 3. A kliensoldali op. rsz. elküldi az üzenetet a távoli op. rsz.-nek. 4. A távoli op. rsz. átadja az üzenetet a szerveroldali eljáráscsonknak. 5. A csonk kicsomagolja a paramétereket és meghívja a szervert. 6. A szerver elvégzi a feladatát, és visszaadja az eredményt a csonknak. 7. A csonk becsomagolja az eredményt, és meghívja a helyi (szerveroldali) op. rsz.-t. 8. A szerveroldali op. rsz. elküldi az üzenetet a kliensoldali op. rsz.-nek. 9. A kliensoldali op. rsz. átadja az üzenetet a kliensoldali csonknak. 10. A csonk kicsomagolja az eredményt, és visszatér a hívó kliensfolyamathoz
Kliens- és szerveroldali eljáráscsonkok
A kliens és a szerver közötti távoli eljárás hívásának (RPC) alapelve.
Paraméterek átadása (1)
1.
Paraméterek átadása (2)
a) b) c)
Az RPC útján történő távoli feladatvégzés során szükséges lépések.
A paraméterek leírása és a csonk generálása
Az eredeti üzenet a Pentium gépen. Az üzenet, miután megérkezik a SPARC gépre. Az invertált üzenet (a dobozok felső sarkában látható kis számok a bájt sorszámát jelentik).
3
2. előadás
Elosztott objektumok
A távoli objektum elterjedt kialakítása a kliensoldali helyettes (proxy) alkalmazásával
4
3. előadás
Protokollok
3. előadás •
RPC (Remote Procedure Call) – távoli eljáráshívás
Kommunikáció
•
RMI (Remote Method Invocation) – távoli metódushívás
2. rész
•
MOM (Message-Oriented Middleware) – üzenetorientált köztesréteg
•
Streams – folyamatok
Távoli eljáráshívás
RPC – kommunikáció menete
- Üzenetküldés elrejtése - Hozzáférési átlátszóság 2-8
RPC - paraméterátadás • • •
Probléma: különböző gépek, különböző adatábrázolással Mutatók Komplex adatszerkezetek
•
=> protokoll: • • •
DCE RPC (1) •
Distributed Computing Environment
• •
Konverzió IDL • • • •
Üzenet formátumának definiálása Egyszerű adatszerkezetek ábrázolása Üzenettovábbítás módja
• •
Eljáráshívás szintaxisa Konstans deklaráció Típusdefiníció „konvertálási” információ
Azonosítók
IDL (Interface Definition Language)
1
3. előadás
DCE RPC (2)
DCE RPC (3)
Kliens csatlakozása a szolgáltatáshoz Kliens és a szerver megírásának lépései a DCE RPC esetén.
Ajtók - Doors
Aszinkron RPC
a) b)
Késleltetett szinkronizált RPC
Kliens és szerver együttműködése két aszinkron RPC segítségével.
A kliens és a szerver együttműködése hagyományos RPC során Együttműködés aszinkron RPC esetén
RMI – elosztott objektumok
Modell – kliensoldali helyettessel és szerveroldali vázzal.
2
3. előadás
RMI • •
Elosztott objektum Távoli objektum
• •
Fordítási idejű objektum Futási idejű objektum
• •
Állandó objektum Nem állandó objektum
Kliens csatlakozása az objektumhoz Distr_object* obj_ref; obj_ref = …; obj_ref-> do_something();
// Deklarálja az objektumhivatkozást // Inicializálja az objektumhivatkozást // Implicit csatlakozás és metódushívás (a)
Distr_object objPref; Local_object* obj_ptr; obj_ref = …; obj_ptr = bind(obj_ref); obj_ptr -> do_something();
Implicit csatlakozás Explicit csatlakozás
RMI – távoli művelet hívása Statikus hívás - IDL -> csonk fobject.append(number);
Java RMI •
Csak távoli objektum
•
Objektumok zárolása – synchronized •
• •
Dinamikus hívás - futás közbeni összeállítás invoke(fobject, id(append), number); [ általánosan: invoke(objektum, metódus, input_paraméterek, output_paraméterek); ]
Üzenetorientált kommunikáció •
RPC, RMI nem mindig használható:
• •
Szerver nem biztos, hogy üzemel a kérés elküldésekor Nem mindig hatékony a nagyfokú szinkronitás
•
=> üzenetcsere
Deklarálja az objektumhivatkozást Deklarálja a helyettes mutatóját Inicializálja az objektumhivatkozást Explicit csatlakozás (helyettes mutatója) Helyetes metódusának meghívása
(b)
a) b)
• •
// // // // //
•
kliensen blokkol
Helyettes szerializálható
Korábbi kommunikációs modell
Pufferelés és a küldő blokkolásának lehetséges helyei
3
3. előadás
Üzenetküldés
Új kommunikációs modell • •
Megtartó kommunikáció Időleges kommunikáció
• •
Szinkron kommunikáció Aszinkron kommunikáció
•
Ezek kombinációja is lehetséges
Kommunikáció fajtái – 1.
a) b)
Megtartó aszinkron kommunikáció Megtartó szinkron kommunikáció
Kommunikáció fajtái – 3.
e) f)
Kommunikáció fajtái – 2.
c) d)
Időleges aszinkron kommunikáció Nyugta alapú időleges szinkron kommunikáció
Üzenetorientált időleges kommunikáció •
Szállítási réteg által biztosított modell
• •
Kommunikációs csatlakozópont (socket) TCP primitívek
Kézbesítés alapú időleges szinkron kommunikáció Válasz alapú időleges szinkron kommunikáció
4
3. előadás
Berkeley kommunikációs csatlakozópontok Primitív Csatlakozópont (Socket)
Jelentése Új kommunikációs végpont létrehozása
Kötés (Bind)
A csatlakozóponthoz hozzárendel egy helyi címet
Figyel (Listen)
Meghirdeti a kommunikációra való képességet
Elfogad (Accept)
Blokkolja a hívót a kapcsolatfelvételi kérés megérkezéséig
Csatlakozik (Connect)
Aktívan megkísérli a kapcsolat felépítését
Küld (Send)
Adatot küld a kapcsolaton keresztül
Fogad (Receive)
Adatot fogad a kapcsolaton keresztül
Lezár (Close)
Bontja a kapcsolatot
MPI – Üzenetátadó interfész •
Berkeley kommunikációs csatlakozópontok
Message-Passing Interface
•
Csatlakozóponos megoldás nem eléggé magas szintű
•
=> kommunkációs könyvtárak – inkompatibilitás
•
=> MPI (szabványosítás)
• •
Időleges kommunikáció Azonosító (csoport, folyamat)
Üzenetorientált megtartó kommunikáció •
Üzenetorientált köztesréteg – MOM
•
Megtartó aszinkron kommunikáció
•
Üzenetek köztes szinten való tárolása (várakozási sorok)
MPI – Üzenetátadó interfész Primitív
Jelentése
MPI_bsend
A helyi küldőpuffer végéhez hozzáadja a kimenő üzenetet
MPI_send
Üzenetet küld, és vár annak helyi vagy távoli pufferbe történő másolásáig
MPI_ssend
Üzenetet küld, és vár a nyugta megérkezéséig
MPI_sendrecv
Üzenetet küld, és vár a válasz megérkezéséig
MPI_isend
Átad egy kimenő üzenetre mutató hivatkozást, és továbbmegy
MPI_issend
Átad egy kimenő üzenetre mutató hivatkozást, és várja ennek nyugtázását
MPI_recv
Üzenet fogadása; blokkolódik, ha nincs üzenet
MPI_irecv
Ellenőrzi, hogy van-e beérkező üzenet, de nem blokkolja a hívót
Üzenetsor-kezelő modell
Várakozási sort használó gyengén csatolt kommunikáció 4 lehetősége
5
3. előadás
Üzenetsor-kezelő modell
Primitív
Az üzenetsor-kezelő rendszer általános felépítése
Jelentése
Betesz (Put)
A megadott várakozási sor végére helyez egy üzenetet
Kivesz (Get)
Mindaddig blokkol, amíg üres a várakozási sor, majd kiveszi a legelső üzenetet
Lekérdez (Poll)
Megvizsgálja, a megadott várakozási sort, és kiveszi a legelső üzenetet, nem blokkol
Értesít (Notify)
Egy kezelő rutint installál, amely mindannyiszor meghívásra kerül, ha üzenet kerül a várakozási sorba
Az üzenetsor-kezelő rendszer várakozási sorát kezelő alapinterfész
Az üzenetsor-kezelő szint szerinti és szállítási szint szerinti cím összefüggése
Az üzenetsor-kezelő rendszer általános felépítése
Üzenetközvetítők
Az útválasztókkal kiépített üzenetsor-kezelő rendszer általános felépítése
Az üzenetközvetítőt használó üzenetsor-kezelő rendszer általános felépítése
6
4. előadás
4. előadás
Kommunikáció
Kommunikáció 3. rész
3. rész
Folyamatok
•
1. rész
Adatfolyam-orientált kommunikáció
Kommunikáció típusok (1)
Kommunikáció típusok (2)
Diszkrét interakció
•
B
•
Eddig: • •
A
egymástól független, teljes információegységek cseréje kommunikáció lezajlásának pillanata nem fontos
idő
•
Most: • •
Folyamatos interakció
időzítés pontossága alapvető fontosságú folyamatos média támogatása
A
•
Hogyan támogatja ezt az elosztott rendszer?
<
B
idő
Média •
Diszkrét (ábrázolású) média •
•
•
pl. szöveg, kép
• •
Quality of Service
aszinkron szinkron izoszinkron •
pl. hang, videó
Multimédia Folyamatos képsor biztosítása •
Adategységek sorozatának átviteli módjai: • • •
Folyamatos (ábrázolású) média: •
• •
Folyamok (Streams)
• •
Folyam
Egyszerű folyam (Simple Stream) Összetett folyam (Complex Stream) • •
több egymással kapcsolatban álló egyszerű folyam alfolyamok közötti kapcsolat szintén időfüggő
Átlátszóság Standardok
1
4. előadás
Adatfolyam (1)
Movie, mint összetett folyam
Két folyamat között a hálózaton keresztül létesített folyam.
Adatfolyam (2)
Adatfolyam (3)
Közvetlenül két eszközt összekötő folyam.
Példa egy műsorszóró folyam több fogadó felé való küldésére.
Multimedia Rendszer-környezet
Technológiai adatok
(Multimedia System Environment) Mbit/s
GB/h
Telefon (PCM)
Multimédia forrás
0.064
0.003
MP3
0.14
0.06
Audió CD
Eszköz
Mbit/s
Fast Ethernet
100
EIDE Disk
133
1.4
0.62
1 – 1.5
0.66
MPEG-2 videó
4
1.76
Digitális kamera (720*480)
25
11
Gigabit Ethernet
1 000
Tömörítetlen TV (640*480)
221
97
SCSI Ultra-160
1 280
Tömörítetlen HDTV (1280*720)
648
288
MPEG-1 videó
ATM OC-3
156
SCSI Ultra wide disc
320
IEEE 1394 (FireWire)
400
2
4. előadás
A szolgáltatás minősége •
QoS kategóriák
QoS – Quality of Service
•
Időbeliség (timeliness) •
•
•
Időfüggő követelmények •
•
mit várunk el a hálózattól
• •
• • •
időzítési mennyiségi és megbízhatósági kérdések
Qos követelmények megadása
Időbeliség dimenziói • • •
•
•
Késleltetés (latency) Kezdeti késleltetés (start-up latency) Remegés (jitter)
•
•
sávszélesség frames/s vagy bits/s vagy bytes/s
MTBF (Mean Time Between Faliure) MTTR (Mean Time To Repair) Telekommunikációs vonalak esetén a hiba-ráta
Max késleltetés (s)
Max remegés (ms)
Sávszélesség (Mbit/s)
valószínűségi értékek a QoS-re
•
Eloszláson alapuló (stochastic distributions)
•
Minőségi osztályok
A QoS meghatározása zsetontartály algoritmus (1)
Tipikus QoS követelmények QoS
precíz értékek, értékhatárok
Valószínűségi (probabilistic) •
Megbízhatóság dimenziói • • •
Determinisztikus - folyamspecifikáció •
Mennyiség dimenziói •
adatvesztés mértéke
Költség (cost) Kritikusság (criticality) Érzékelés minősége (quality of perception)
QoS dimenziók •
áteresztőképesség (throughput)
Megbízhatóság (reliability) •
Folytonos adatfolyamok esetén • • •
adatnak időben kell megérkeznie
Mennyiség (volume)
Bit hiba-ráta
Csomag hiba-ráta
Hang
0.25
10
0.054
< 10-3
< 10-4
Videó (TV)
0.25
100
100
< 10-2
< 10-3
Tömörített videó
0.25
100
2 – 10
< 10-6
< 10-9
Kép
1
-
2 – 10
< 10-4
< 10-9
Adat (file-átvitel)
1
-
2 – 100
0
0
Valós-idejű adat
0.001 – 1
-
< 10
0
0
A zsetontartály-algoritmus elve.
3
4. előadás
A QoS meghatározása zsetontartály algoritmus (2)
QoS függőségek •
Bemeneti adatok jellemzői • Adategység maximális mérete (bájt) • Zsetontartály időegységráta (bájt/s) • Zsetontartály mérete (bájt) • Maximális átviteli adatráta (bájt/s)
Megkövetelt szolgáltatások • Veszteségi érzékenység (bájt) • Veszteségi időtartam (µs) • Löketveszteségi érzékenység (adategység) • Legkisebb észlelt készleltetés (µs) • Legnagyobb késleltetési eltérés (µs) • Szavatolt minőség
Egy komponens által nyújtott QoS függhet egy másik komponens által nyújtott QoS-től •
•
pl. rétegelt rendszerekben
QoS igények megfogalmazásának egy rendszere
Folyamspecifikáció.
QoS működtetése •
Specifikáció
•
A folyam megindítása •
Tárgyalás (negotiation) •
•
az alkalmazás kevesebbet is elfogadhat kevesebb költségért
Beléptetés (admission control) •
•
ha belépett, a rendszer garantálja a QoS-t
Erőforrás-lefoglalás •
ha szükséges a QoS betartásához
QoS-nek megfelelő erőforrások lefoglalása • • •
•
sávszélesség puffer feldolgozási kapacitás
Erőforrás lefoglaló protokoll (RSVP – Resource reSerVation Protocol) • • • •
QoS fogadó által kezdeményezett beléptetés, lefoglalás multicast üzenetküldés támogatása
A folyam megindítása
Az RSVP-módszerrel történő erőforrás-lefoglalás általános vázlata az elosztott rendszerben.
4
4. előadás
Szinkronizálási mechanizmusok (1)
Szinkronizálási mechanizmusok (2)
Az adategység szintjén történő explicit szinkroniálás elve.
A magas szintű interfészek által támogatott szinkronizáció elvi vázlata.
Folyamatok •
Folyamat •
kezelése, ütemezése – folyamattábla • •
Folyamatok
•
•
Szálak használata a nem elosztott rendszerekben
szálkezelő rendszer szálak védése egymástól a programozó feladata
Szálak implementációja •
Száltámogató csomagok • •
•
létrehozás, megsemmisítés szinkronizálás
Szálkönyvtár futhat • • •
•
Az IPC hatására bekövetkező állapotváltozások
folyamatok elválasztása egymástól átlátszó
Szál • •
1. rész
új folyamat létrehozása átkpcsolás
felhasználói módban kernel módban hibrid megoldás: könnyűsúlyú folyamatok (LWP – LightWeight Process)
LWP: • • •
száltámogató csomag felhasználói módban blokkoló rendszerhívás nem blokkolja az egész folyamatot átlátszó
5
4. előadás
Szálak implementációja
Többszálú szerverek (1)
A felhasználói szintű szálak és a kernel szintű könnyűsúlyú folyamatok kombinációja.
A diszpécser/dolgozó modell szerinti többszálú szerver felépítése.
Többszálú szerverek (2) Modell
Jellemzője
Szálak
Párhuzamos végrehajtás, blokkoló rendszerhívások
Egyszálú folyamat
Nincs párhuzamos végrehajtás, blokkoló rendszerhívások
Véges állapotú gép
Párhuzamos végrehajtás, nem blokkoló rendszerhívások
A szerver felépítésének három módja.
6
5. előadás
5. előadás
Folyamatok
Folyamatok
2. rész 2. rész
Elnevezési rendszerek 1. rész
Emlékeztető • • •
Folyamatok Szálak Könnyűsúlyú folyamatok
•
Szálak nem elosztott rendszerekben • • •
rendszerhívásra várakozás alatt hasznos munka többprocesszoros rendszerek kihasználása implementációs okok
Kliensoldali szoftver és az átlátszóság •
Hozzáférhetőségi átlátszóság
•
Elhelyezkedési, áthelyezhetőségi és mozgathatsági átlátszóság
•
Meghibásodási átlátszóság
•
Többszörözhetőségi átlátszóság
Többszálú kliens •
Előnyök: • •
•
elosztottsági átlátszóság hatékonyság
Kliens (tipikus) feladatai: • • • • •
felhasználói felület helyi feldolgozó rész kommunikációs rész … + elosztottsági átlátszóság eléréséhez szükséges elemek
Többszörözhetőségi átlátszóság megvalósítása kliens-oldalon
A távoli objektumtöbbszörözés átlátszóvá tételének egyik lehetséges módja a kliensoldali megoldás használata.
1
5. előadás
Többszálú szerver (2)
Többszálú szerver (1) •
Előnyök: • • •
•
egyszerűbb kód párhuzamos végrehajtás lehetősége blokkoló rendszerhívás idejének kihasználása
Szerver feladatai: • •
várakozik a beérkező kérésekre kezeli a kérést
A diszpécser/dolgozó modell szerinti többszálú szerver felépítése.
Hogyan találják meg a kliensek a szervert
Többszálú szerver – általános tervezési szempontok •
Ismétlőszerver <-> konkurens szerver
•
Lehet-e megszakítást küldeni a szervernek
•
Állapot nélküli szerver <-> állapotteljes
•
Hogyan találják meg a kliensek a szervert a) b)
Kód áthelyezése •
démon használatával (mint a DCE esetén szokásos) szuperszerver használatával (mint a Unix-rendszerekben szokásos)
A kód áthelyezésének okai
A kód áthelyezésének okai: •
teljesítménynövelés – terhelésmegosztási algoritmusok
•
kommunikáció leszorítása – adatot ott dolgozzuk fel, ahol van
•
párhuzamos végrehajtás kihasználása
•
rugalmasság A kliens szerverrel folytatott kommunikációjának dinamikus konfigurálási elve. A kliens először letölti a szükséges szoftvert, majd meghívja a szervert.
2
5. előadás
A folyamat szegmensei •
Kódszegmens – végrehajtott program
•
Erőforrásszegmens – igényelt külső erőforráshivatkozások
•
Végrehajtási szegmens – futási állapot
Kódáthelyezési modellek (1) • •
Gyenge mobilitás Erős mobilitás
• •
Küldő által kezdeményezett Fogadó által kezdeményezett
•
Gyenge mobilitásnál • •
•
Erős mobilitásnál • •
Kódáthelyezési modellek (2)
Célfolyamatban fut Külön folyamatban fut Áthelyezett folyamat Klónozott folyamat
Az áthelyezés és a helyi erőforrások (1) •
Folyamat-erőforrás kötés • • •
•
azonosítókapcsolt – kizárólag az adott erőforrás kell tartalomkapcsolt – az adott erőforrás tartalma kell típuskapcsolt – adott típusú erőforrás kell
Erőforrás-gép kötés • • •
csatolatlan – könnyen áthelyezhető rögzített – áthelyezhető, de költséges mozdíthatatlan – nem helyezhető át
A kódáthelyezés lehetőségei.
Folyamat-erőforrás kötés
Erőforrás-gép kötés
Azonosítókapcsolt
Tartalomkapcsolt
Típuskapcsolt
Csatolatlan
Rögzített
Mozdíthatatlan
erőforrás áthelyezése (vagy globális hivatkozás létesítése)
globális hivatkozás létesítése (vagy erőforrás áthelyezése)
globális hivatkozás létesítése
tartalom másolása (vagy erőforrás áthelyezése vagy globális hivatkozás létesítése)
globális hivatkozás létesítése
globális hivatkozás létesítése
újrakapcsolódás helyileg elérhetőhöz (vagy erőforrás áthelyezése vagy tartalom másolása)
újrakapcsolódás helyileg elérhetőhöz (vagy globális hivatkozás létesítése vagy tartalom másolása)
Kód áthelyezése heterogén rendszerben •
Szükséges az összes platform támogatottsága – újrafordítás Erős mobilitásnál – végrehajtási szegmens áthelyezhetősége Végrehajtási szegmens tartalma:
• •
(vagy tartalom másolása) újrakapcsolódás helyileg elérhetőhöz (vagy globális hivatkozás létesítése)
Másik gépre való kódáthelyezés során a helyi erőforrásokra való hivatkozásokkal kapcsolatos műveletek.
• • •
•
folyamat által elérhető védett adatok programszámláló értéke folyamat vermének tartalma
Lehetséges megoldás: • • •
kódáthelyezés csak meghatározott pontokon programvermem másolatának (áthelyezési verem) tárolása gépfüggetlen módon kódáthelyezéskor kód és áthelyezési verem átküldése
3
5. előadás
Programozási nyelv által támogatott mobilitás – JoCaml
Kód áthelyezése heterogén rendszerben
Szerver:
let def f x = reply x*x in Ns.register "square" f vartype;; let loc here do {};; Ns.register "here" here vartype; Join.server ();;
Kliens: let loc mobile do { let here = Ns.lookup "here" vartype in go here;
A végrehajtási szegmens áthelyezhetőségének támogatásához szükséges áthelyezési verem kezelésének elvi vázlata heterogén környezetben.
let sqr = Ns.lookup "square" vartype in let result = sqr 5 in print_string ("square of 5 = "^string_of_int result^"\n"); flush stdout; }
Nevek, azonosítók és címek •
Elnevezési rendszerek
•
Nevek – erőforrások megosztása, entitások egyértelmű azonosítása, helyek megjelölése, stb. Nevek feloldása – névszolgáltató rendszer
•
Kapcsolódási pont
•
Helyfüggetlen név
•
Azonosító
•
Emberközeli nevek
1. rész
Névterek (1) •
Névterek (2)
Elnevezési gráfok • • • •
csomópontok gyökér globális név helyi név
Általános elnevezési gráf egyetlen gyökércsomóponttal.
4
5. előadás
Névfeloldás •
Név visszakeresése
•
Csomópontról csomópontra
•
Kiválasztási mechanizmus
Csatolás és felszerelés (1)
Az elnevezési gráfban lévő szimbolikus hivatkozás elvének magyarázata.
Csatolás és felszerelés (2)
Csatolás és felszerelés (3)
Távoli névtér felszerelése adott hozzáférési protokoll segítségével.
A DEC globális névszolgáltatásának felépítése.
5
4. előadás
A névtér elosztása (1)
6. előadás
Elnevezési rendszerek 2. rész
A DNS-névtér felosztása (három rétegre), amely az interneten keresztül elérhető állományokat is tartalmaz.
A névtér elosztása (2) Egység Földrajzi átméretezhetőség Csomópontok száma
A névfeloldás implementálása (1)
Globális
Szervezeti
Kezelői
Világméretű
Vállalat szintű
Osztály szintű
Kevés
Sok
Rendkívül sok
Másodpercek
Milliszekundumok
Azonnal
Frissítési terjedés
Ráérősen
Azonnal
Azonnal
Másolatok száma
Sok
Nincs vagy kevés
Nincs
Kliensoldali gyorsítótárat használunk?
Igen
Igen
Néha
Visszakeresés elvárt válaszideje
•
Tegyük fel, hogy a névszervereket nem többszörözzük és nem használunk kliensoldali gyorsítótárat
•
Iteratív névfeloldás •
•
Rekurzív névfeloldás •
A globális, szervezeti és kezelői rétegbe szervezett nagyméretű névtérben található, csomópontokat implementáló névszerverek összehasonlítása.
A névfeloldás implementálása (2)
Az iteratív névfeloldás elve.
•
kliens több névszerverrel is felveszi a kapcsolatot
kliens csak a gyökér-névszerverrel tartja a kapcsolatot
root:
(ftp://ftp.cs.vu.nl/pub/globe/index.txt)
A névfeloldás implementálása (3)
A rekurzív névfeloldás elve.
1
4. előadás
A névfeloldás implementálása (4) Csomópontszerver
Feloldandó
Visszakeresendő
Visszakapja és tárolja
Átadja a gyereknek
A névfeloldás implementálása (5)
Visszatér az igénylőhöz
cs
#
--
--
#
vu
#
#
# #
nl
#
# #
# # #
gyökér
#
# # #
# # # #
A rekurzív és az ismétlő névfeloldás során szükséges kommunikáció összehasonlítása.
Az rekurzív névfeloldása. A névszerverek gyorsítótárba helyezik a köztes eredményeket a későbbi visszakeresés gyorsítása érdekében.
A DNS-névtér (2)
A DNS-névtér (1) •
Tartományi névszolgáltató rendszer (Domain Name System) Levelezőszerverek és gazdagépek nevének lekérdezése
•
•
DNS névtér • • • •
fa címke, teljes név tartomány, tartománynév erőforrásrekordok
Rekord típusa
Kapcsolódó entitás
Leírás
SOA
Zóna
A hozzá tartozó zónáról tartalmaz információt
A
Gazdagép
A csomópont által képviselt gazdagép IP-címét tartalmazza
MX
Tartomány
A csomópontnak címzett levelet kezelő szerverre való hivatkozás
SRV
Tartomány
Adott szolgáltatást nyújtó szerverre való hivatkozás
NS
Zóna
A kapcsolódó zónát implementáló névszerverre való hivatkozás
CNAME
Csomópont
Szimbolikus hivatkozás a kapcsolódó csomópont elsődleges nevére
PTR
Gazdagép
A gazdagép teljes nevét tartalmazza
HINFO
Gazdagép
A csomópont által képviselt gazdagépről tartalmaz információt
TXT
Bármi
Hasznosnak gondolt entitásspecifikus információt tartalmaz
A DNS-névtér csomópontjainak tartalmát alkotó erőforrásrekordok legfontosabb típusai.
A DNS megvalósítása (1) •
A kezelői réteg nem a DNS része
• •
Minden zónát névszerver valósít meg A névszerverek többszörözöttek
• •
A zóna frissítését az elsődleges névszerver végzi Zónaátvitel
•
Erőforrás-rekordok
A DNS megvalósítása (2) A cs.vu.nl zóna DNSadatbázisának részlete
2
4. előadás
A DNS megvalósítása (3) Név
Rekord típusa
Rekord értéke
cs.vu.nl
NS
solo.cs.vu.nl
solo.cs.vu.nl
A
130.37.21.1
OSI X.500 (1) •
Katalógusszolgáltatás
•
Tulajdonság alapú keresés
• •
Katalógusbejegyzések Rekord – tulajdonság-érték párok
A vu.nl tartomány leírásának a cs.vu.nl altartományt meghatározó részlete.
X.500 (2) Tulajdonság
Rövidítés
Country
C
X.500 (3) Érték
NL
Locality
L
Amsterdam
Organization
L
Vrije Universiteit
OrganizationalUnit
OU
Math. & Comp. Sc.
CommonName
CN
Main server
Mail_Servers
--
130.37.24.6, 192.31.231,192.31.231.66
FTP_Server
--
130.37.21.11
WWW_Server
--
130.37.21.11
Katalógus információs fa részlete
X.500-as elnevezési konvenciókat használó egyszerű példa az X.500-as katalógusbejegyzéseire
The X.500 Name Space (3) Jellemző
Érték
Jellemző
Érték
Country
NL
Country
NL
Locality
Amsterdam
Locality
Amsterdam
Organization
Vrije Universiteit
Organization
Vrije Universiteit
OrganizationalUnit
Math. & Comp. Sc.
OrganizationalUnit
Math. & Comp. Sc.
CommonName
Main server
CommonName
Main server
Host_Name
star
Host_Name
zephyr
Host_Address
192.31.231.42
Host_Address
192.31.231.66
Mozgó entitások helyének meghatározása •
Cím megváltozik • •
•
tartományon belül tartományon kívül
Nevet nem szabad megváltoztatni • •
•
gép új címe a DNS adatbázisba szimbolikus hivatkozás
Nevek helyett azonosítók használata •
helymeghatározó szolgáltatás
Két olyan katalógusbejegyzés, amelyeknél a Host_Name a relatív megkülönböztető név.
3
4. előadás
Entitások elnevezése a helymeghatározással szemben
Egyszerű megoldások •
Adatszórás és csoportcímzés • •
kérés mindenkinek az érintett válaszol (cím)
•
pl. ARP
•
Továbbítómutatók • •
a) b)
az entitás hivatkozást hagy maga után pl. SSP lánc módszere
Címek és nevek közötti közvetlen, egyszintű leképezés. Azonosítókat használó kétszintű leképezés.
Továbbítómutatók (1)
Továbbítómutatók (2)
A továbbmutató átirányítása a rövidítő információ tárolásával. A (helyettes, váz) párokat használó továbbmutatók elve.
Otthon alapú módszerek (1) •
Nagyméretű hálózaton
•
Otthon – entitás pillanatnyi helye
•
Otthon alapú módszerek (2)
pl. Mobile IP • •
hazai ügynök (home agent) felügyeleti cím (care-of address)
A Mobile IP elve.
4
4. előadás
Hierarchikus módszerek (1)
Hierarchikus módszerek (2)
A helymeghatározó-szolgáltatás hierarchikus tartományokká szervezése, melyek mindegyikének van egy hozzá tartozó katalógus-csomópontja.
Különböző levéltartományokban elhelyezkedő, két címmel rendelkező entitásra vonatkozó információ tárolása.
Hierarchikus módszerek (3)
Hierarchikus módszerek (4)
a) Adott hely megkeresése a hierarchikusan szervezett helymeghatározó-szolgáltatással.
b)
A kérés az első olyan csomópontig megy, amely ismeri E entitást. A levélcsomópontig vezető továbbítómutatók láncának létrehozása.
Mutatótárolás (1)
Mutatótárolás (2)
Arra a katalógus-csomópontra hivatkozó mutató gyorsítótárba való helyezése, amely az entitás leggyakoribb tartózkodási helyét takarja.
Érvénytelenítendő, gyorsítótárban lévő mutató, amely nem helyi címmel térne vissza, miközben helyi cím is elérhető lenne.
5
4. előadás
A méretezhetőség kérdései
A helymeghatározó-szolgáltatás által fedett hálózat méretezhetőségi problémája, ha az alcsomópontokat egyenlően osztjuk el a hálózaton.
6
2010.05.06.
7. előadás
Elnevezési rendszerek
Elnevezési rendszerek
3. rész 3. rész
Szinkronizálás
A nem hivatkozott entitások eltávolítása
1. rész
Motiváció
A nem hivatkozott objektumok problémája
A nem elérhető hivatkozást el kell távolítani => elosztott szemétgyűjtő
Példa az egymásra hivatkozó objektumokat ábrázoló gráfra.
Egyszerű hivatkozásszámlálás •
Objektumra mutató hivatkozások megszámolása
•
Hivatkozás létrehozásakor növeljük
•
Hivatkozás eltávolításakor csökkentjük
•
Ha a számláló 0, az objektum törölhető
Probléma az egyszerű hivatkozásszámlálással (1)
A hivatkozásszámláló helyes értékének beállítási problémája megbízhatatlan kommunikáció esetén.
1
2010.05.06.
Probléma az egyszerű hivatkozásszámlálással (2)
Fejlettebb hivatkozásszámlálás (1) • • • •
Súlyozott hivatkozásszámlálás – csak csökkentés Minden objektumnak előre meghatározott teljes súlya van. <-> részleges súly Új hivatkozáskor, másoláskor a súly felét átadjuk Törléskor: az objektum a teljes súlyát a törlendő részleges súlyával csökkenti Ha a teljes súly 0, az objektum törölhető
a) A hivatkozás átmásolása egy másik folyamatnak és a hivatkozásszámláló elkésett növelése b) A megoldás
•
Fejlettebb hivatkozásszámlálás (2)
Fejlettebb hivatkozásszámlálás (3)
a) b)
A súlyok kezdeti hozzárendelése súlyozott hivatkozásnál. Súlyok hozzárendelése az új hivatkozás létrehozásakor.
Fejlettebb hivatkozásszámlálás (4)
Indirekció alkalmazása, amikor egy hivatkozás részleges súlya eléri az egyet.
c) Súlyok hozzárendelése a hivatkozás másolásánál.
Fejlettebb hivatkozásszámlálás (5)
Távoli hivatkozás létrehozása és átmásolása nemzedéki hivatkozásszámlálás esetén.
2
2010.05.06.
Hivatkozáslista •
•
A váz nyilvántartja a rá hivatkozó helyetteseket (mutató) Létező elem hozzáadása, nem létező törlése idempotens művelet Létrehozáskor az új elküldi azonosítóját a váznak Másoláskor az új értesíti a vázat
•
Pl. Java RMI
• •
Elérhetetlen entitások azonosítása (1) •
Egyszerű nyomkövetés az elosztott rendszerben • • •
egyprocesszoros rendszerekben jelöl és takarít (mark and sweep) a jelölőszakasz a gyökérkészletből indulva megjelöli az entitásokat • • •
Elérhetetlen entitások azonosítása (2) •
•
fehér – minden entitás kezdetben szürke – ami elérhető, de még nem dolgoztuk fel (a folyamat előrehaladása közben) fekete – ami elérhető a gyökérből (a jelölő szakasz végére)
a takarítószakasz törli a meg nem jelölteket
Csoporton belüli nyomkövetés (1)
Csoporton belüli nyomkövetés • • • • •
vázak megjelölése a jelölések kiterjesztése a vázakról a helyettesekre a jelölések kiterjesztése a helyettesekről a vázakra stabilizálás az előző két lépés megismétlésével szemét eltávolítása
• •
váz lehet: puha / kemény a helyettes lehet: puha / kemény / semmilyen
A vázak kezdeti jelölése.
Csoporton belüli nyomkövetés (2)
Csoporton belüli nyomkövetés (3)
A folyamatok helyi jelölésmásolásának befejezése utáni állapot.
Végső jelölések.
3
2010.05.06.
Az órák szinkronizálása
Szinkronizálás 1. rész Ha mindegyik gép a saját óráját használja, akkor az adott esemény után történt másik eseményhez az elsőnél korábbi idő társulhat.
Fizikai órák (1)
A csillagidő és a szoláris idő összefüggése.
Fizikai órák (2)
A TAI-másodperc a szolárissal ellentétben azonos hosszúságú. Szökőmásodperceket kell használnunk arra, hogy a TAI a Nappal szinkronban tartható legyen.
Óraszinkronizáló algoritmusok
Cristian algoritmusa
Az óra által mutatott idő és az UTC összefüggése az óra eltérése esetén.
A pontos idő lekérdezése az időszerverről.
4
2010.05.06.
A Berkeley-algoritmus
Átlagoló algoritmusok • •
Decentralizált algoritmus Újraszinkronizálási időszakok • • •
minden gép kihirdeti a saját idejét elindít egy időmérőt a beérkezett hírdetéseket összegyűjti
Többszörözött külső időforrások a) b) c)
Az idődémon lekérdezi a többi géptől az általuk nyilvántartott pontos időt A gépek válaszolnak Az idődémon mindegyiket utasítja, hogyan állítsa be az óráját
• •
Lamport időbélyege
Szinkronizált órák használata •
Több UTC-forrás vevő a rendszerben Ezek rendszeresen kihirdetik az idejüket
Többször küldött üzenetek figyelmen kívül hagyására •
hogy ne kelljen a végtelenségig tárolni
Logikai órák • •
Elegendő, ha az összes gép órája ugyanazt az időt mutatja Az események sorrendje a fontos a). Három folyamat, mindegyik saját órával. Az órák különböző sebességgel futnak. b). Lamport algoritmusa az órák összehangolására.
Példa – pontosan sorbarendezett csoportcímzés
Időbélyeg vektor (1) • •
• •
‘C(a)’ és ‘C(b)’ összehasonlítása semmit sem mond ‘a’ és ‘b’ kapcsolatáról Lamport időbélyegei nem foglalkoznak az oksági viszonyokkal Oksági viszony – időbélyeg-vektorok alkalmazása Ha ‘VT(a)’ < ‘VT(b)’ => ‘a’ ‘b’ előzménye
A többszörözött adatbázis frissítése és az inkonzisztens állapot kialakulása.
5
2010.05.06.
Időbélyeg vektor (2) •
Pi folyamat Vi vektorának tulajdonságai: 1. Vi [i] a Pi folyamatban eddig bekövetkezett események száma 2. Ha Vi [j] = k, akkor Pi tudja, hogy a Pj folyamatban eddig k esemény történt
• •
Okozatilag összefüggő üzenetek küldése r csak akkor kézbesíti az üzenetet, ha: 1. vt(r)[j] = Vk[j] + 1 2. vt(r)[i] < / = Vk[i] teljesül valamennyi i<>j
6
2010.05.06.
Globális állapot (1)
Szinkronizálás 2. rész
a) Konzisztens metszet b) Inkonzisztens metszet
Globális állapot (2)
Globális állapot (3)
b) c) d)
a)
A folyamat és csatornáinak szerkezete az elosztott pillanatfelvétel elkészítéséhez.
Szavazó algoritmusok - zsarnok (1)
A zsarnok algoritmus • A 4-es folyamat választást tart • 5-ös és 6-os válaszol, megmondva 4-esnek, hogy álljon le a választással • 5-ös és 6-os választást kezdeményez
Q folyamat a jelzést először kapja meg, ezért feljegyzi saját állapotát. Q valamennyi érkező üzenetét feljegyzi. Q megkapja a jelzést a bejövő csatornán és befejezi a csatorna állapotának rögzítését.
Szavazó algoritmusok - zsarnok (2)
d) e)
6-os szól 5-ösnek, hogy álljon le a választással 6-os megnyeri a választást és kihirdeti a győzelmét
1
2010.05.06.
Kölcsönös kizárás: A központosított algoritmus
Szavazó algoritmusok - gyűrű
a) b)
Kört használó szavazó algoritmus. c)
Kölcsönös kizárás: Az elosztott algoritmus
a) b) c)
Két folyamat akar ugyanabban a pillanatban belépni ugyanarra a kritikus területre. A 0-ás folyamatnak alacsonyabb az időbélyege, így ő nyer. Amikor a 0-ás folyamat végzett, ő is elküldi az OK választ, így a 2-es folyamat már beléphet a kritikus területre.
Kölcsönös kizárás: összehasonlítás Belépési / kilépési üzenetszám
Belépés előtti késleltetés (üzenetidőben)
Központosított
3
2
2(n–1)
2(n–1)
Bármely folyamat összeomlása
1 to ∞
0 to n – 1
Elveszett zseton, a folyamat összeomlása
Zsetongyűrű
Kölcsönös kizárás: A zsetongyűrű algoritmus
a) A folyamatok rendezetlen csoportja a hálózaton. b) A szoftver által alkotott logikai gyűrű.
Elosztott tranzakciók tranzakciómodell (1)
Algoritmus
Elosztott
Az 1-es folyamat engedélyt kér a koordinátortól, hogy beléphessen a kritikus területre. Az engedély megadva. A 2-es folyamat engedélyt kér ugyanerre a kritikus területre való belépéshez. A koordinátor nem válaszol. Amikor az 1-es folyamat elhagyja a kritikus területet, értesíti erről a koordinátort, aki ezután válaszol a 2-es folyamatnak.
Problémák A koordinátor összeomlása
A kölcsönös kizárást biztosító algoritmusok összehasonlítása.
A mesterszalag frissítése hibatűrő folyamat.
2
2010.05.06.
Elosztott tranzakciók tranzakciómodell (2) Primitív
Leírása
BEGIN_TRANSACTION
Tranzakció kezdetének jelzése
END_TRANSACTION
Tranzakció végének jelzése
ABORT_TRANSACTION
A tranzakció félbeszakítása és az eredeti állapot visszaállítása
READ
Adat beolvasása állományból, táblából vagy bárhonnan
WRITE
Adat kiírása állományba, táblába vagy bárhová
Elosztott tranzakciók tranzakciómodell (3) BEGIN_TRANSACTION reserve WP -> JFK; reserve JFK -> Nairobi; reserve Nairobi -> Malindi; END_TRANSACTION (a)
a) b)
BEGIN_TRANSACTION reserve WP -> JFK; reserve JFK -> Nairobi; reserve Nairobi -> Malindi full => ABORT_TRANSACTION (b)
4 járat helyfoglalása egy tranzakcióként A tranzakció félbeszakad, amikor a negyedik járat nem elérhető
Néhány példa a tranzakció-primitívekre.
A tranzakciók tulajdonságai (ACID) 1. Oszthatatlan (elemi) - Atomic
A tranzakciók osztályozása Az egységes tranzakciók korlátai
2. Konzisztens - Consistent • Beágyazott tranzakciók 3. Elkülönülő - Isolated • Elosztott tranzakciók 4. Maradandó - Durable
Elosztott tranzakciók
Implementáció – saját munkaterület
a) b)
a) b)
Beágyazott tranzakció Elosztott tranzakció
c)
Egy három blokk hosszúságú állomány indexei és lemezblokkjai Az állomány 0-ás blokkjának módosítása a tranzakció során, és egy negyedik blokk hozzáfűzése után kialakult helyzet A tranzakció lezárása utáni helyzet
3
2010.05.06.
Implementáció – munkatervnapló x = 0; y = 0; BEGIN_TRANSACTION; x = x + 1; y=y+2 x = y * y; END_TRANSACTION; (a)
Log
Log
Log
[x = 0 / 1]
[x = 0 / 1] [y = 0/2]
[x = 0 / 1] [y = 0/2] [x = 1/4]
(b)
(c)
(d)
a) Egy tranzakció b) – d) Az egyes utasítások végrehajtása előtt kiírt naplóbejegyzés
4
2010.05.06.
9. előadás
Szinkronizálás
Szinkronizálás
3. rész 3. rész
Konzisztencia és többszörözés
Konkurenciakontroll
1. rész
A tranzakciók tulajdonságai (ACID)
Konkurenciakontroll (1)
1. Oszthatatlan (elemi) - Atomic 2. Konzisztens - Consistent
3. Elkülönülő – Isolated [sorosítható – serializable] 4. Maradandó - Durable
A tranzakciókat megvalósító kezelők általános felépítése.
Konkurenciakontroll (2) Az elosztott tranzakciókat feldolgozó kezelők általános felépítése.
Sorosíthatóság (1) BEGIN_TRANSACTION x = 0; x = x + 1; END_TRANSACTION (a)
BEGIN_TRANSACTION x = 0; x = x + 2; END_TRANSACTION
BEGIN_TRANSACTION x = 0; x = x + 3; END_TRANSACTION
(b)
(c)
1. ütemterv
x = 0; x = x + 1; x = 0; x = x + 2; x = 0; x = x + 3
Helyes
2. ütemterv
x = 0; x = 0; x = x + 1; x = x + 2; x = 0; x = x + 3;
Helyes
3. ütemterv
x = 0; x = 0; x = x + 1; x = 0; x = x + 2; x = x + 3;
Hibás
(d)
a) – c) Három tranzakció: T1, T2, and T3 d) Lehetséges ütemtervek
1
2010.05.06.
Sorosíthatóság (2)
Kétfázisú zárolás (1)
• write(Ti, x); read(Ti, x); write(Ti, x) • ütköző műveletek • szinkronizálás • kölcsönös kizárás • időbélyegek • megközelítés • pesszimista • optimista
Kétfázisú zárolás (2)
Kétfázisú zárolás
Pesszimista időbélyeg-rendezés (1) • T tranzakció – ts(T) kezdeti időbélyeg • x adatelem – tsRD(x), tsWR(x) utolsó olvasást / írást végző tranzakció időbélyege • read(T, x), ahol ts(T) < tsWR(x) => T megszakad • read(T, x), ahol ts(T) > tsWR(x) => OK [tsRD(x) <- max{ts(T), tsRD(x)}]
Szigorú kétfázisú zárolás
Pesszimista időbélyeg-rendezés (2)
• write(T, x), ahol ts(T) < tsRD(x) => T megszakad • write(T, x), ahol ts(T) > tsRD(x) => OK [tsWR(x) <- max{ts(T), tsWR(x)}]
Optimista időbélyeg-rendezés • Saját munkaterület • Ha az ütközések ritkák • Tranzakció közben nincs vizsgálat, csak nyilvántartás (írások, olvasások)
Az időbélyeget használó konkurenciakontrol.
• Tranzakció lezárásakor az összes többi tranzakció vizsgálata • megszakad, vagy • lezárul • Időbélyeg használata
2
2010.05.06.
A többszörözés okai • Megbízhatóság növekedése • Teljesítmény növekedése
Konzisztencia és többszörözés 1. rész
• Többszörözés ára – konzisztencia • Átméretezési technika • frissítések gyakorisága • konzisztencia • Gyorsítótár (cache)
Többszörözhetőségi átlátszóság megvalósítása kliens-oldalon
A távoli objektumtöbbszörözés átlátszóvá tételének egyik lehetséges módja a kliensoldali megoldás használata.
Objektumtöbbszörözés (2)
a) b)
A konkurens hívások kezelésére képes távoli objektum. A konkurens hívások kezelésének felelősségét az objektumadapterre átruházó távoli objektum.
Objektumtöbbszörözés (1)
Két különböző kliens által közösen használt elosztott távoli objektum szerkezete.
Példa – pontosan sorbarendezett csoportcímzés
A többszörözött adatbázis frissítése és az inkonzisztens állapot kialakulása.
3
2010.05.06.
Objektumtöbbszörözés (3)
a) b)
Többszörözést támogató objektumok az elosztott rendszerben. Az elosztott rendszer felel a többszörözés kezeléséért.
Szigorú konzisztencia
Azonos adatelemen műveletet végző két folyamat viselkedése: a) szigorúan konzisztens adattár b) nem szigorúan konzisztens adattár
Lineáris és soros konzisztencia (2)
Process P1
Process P2
Process P3
x = 1; print ( y, z);
y = 1; print (x, z);
z = 1; print (x, y);
Három egyidejűleg végrehajtott folyamat.
Adatközpontú konzisztenciamodellek
A fizikailag több folyamat között elosztott és többszörözött logikai adattár általános felépítése.
Lineáris és soros konzisztencia (1)
a) b)
A sorosan konzisztens adattár. A sorosan konzisztens kritériumot nem teljesítő adattár.
Lineáris és soros konzisztencia (3) x = 1; print ((y, z); y = 1; print (x, z); z = 1; print (x, y);
x = 1; y = 1; print (x,z); print(y, z); z = 1; print (x, y);
y = 1; z = 1; print (x, y); print (x, z); x = 1; print (y, z);
y = 1; x = 1; z = 1; print (x, z); print (y, z); print (x, y);
Prints: 001011
Prints: 101011
Prints: 010111
Prints: 111111
Signature: 001011 (a)
Signature: 101011 (b)
Signature: 110101 (c)
Signature: 111111 (d)
Ez előző ábrán bemutatott folyamatok 4 lehetséges végrehajtási sorrendje.
4
2010.05.06.
Okozati konzisztencia (1)
Okozati konzisztencia (2)
Szükséges feltétel: A potenciálisan okozatilag összefüggő írási műveleteket valamennyi folyamatnak ugyanabban a sorrendben kell látnia. Ez a sorrend megengedett az okozatilag konzisztens adattárban, de tiltott a sorosan vagy a szigorúan konzisztens rendszerben.
Okozati konzisztencia (3)
FIFO-konzisztencia (1) Szükséges feltétel: Egy adott folyamat által végrehajtott valamennyi írási művelet eredményét az összes többi folyamatnak az írást végző folyamat által meghatározott sorrendben kell látnia.
a) b)
Az okozati konzisztenciát megsértő műveleti sorrend. Az események konzisztens adattárban érvényes lehetséges sorrendje.
FIFO-konzisztencia (2)
FIFO-konzisztencia (3) x = 1; print (y, z); y = 1; print(x, z); z = 1; print (x, y);
x = 1; y = 1; print(x, z); print ( y, z); z = 1; print (x, y);
y = 1; print (x, z); z = 1; print (x, y); x = 1; print (y, z);
Prints: 00
Prints: 10
Prints: 01
(a)
Az események lehetséges sorrendje a FIFOkonzisztenciamodell szerint.
(b)
(c)
A korábbi ábrán látható 3 folyamat utasításainak különböző végrehajtási sorrendje.
5
2010.05.06.
FIFO-konzisztencia (4) Process P1
Process P2
x = 1; if (y == 0) kill (P2);
y = 1; if (x == 0) kill (P1);
Két konkurens folyamat.
Gyenge konzisztencia (1) Tulajdonságok: • Az adattárhoz tartozó szinkronizáló változók elérése sorosan konzisztens. • A szinkronizáló változóval végzett újabb művelet mindaddig nem engedélyezett, amíg az összes korábbi írási művelet mindenütt be nem fejeződött. • Az adatelemeken végzett egyetlen írási vagy olvasási művelet sem engedélyezett, amíg az összes szinkronizáló változó értelmezett művelet mindenütt be nem fejeződött.
Gyenge konzisztencia (2) int a, b, c, d, e, x, y; int *p, *q; int f( int *p, int *q);
/* variables */ /* pointers */ /* function prototype */
a = x * x; b = y * y; c = a*a*a + b*b + a * b; d = a * a * c; p = &a; q = &b e = f(p, q)
/* a stored in register */ /* b as well */ /* used later */ /* used later */ /* p gets address of a */ /* q gets address of b */ /* function call */
A program fragment in which some variables may be kept in registers.
Gyenge konzisztencia (3)
a) b)
Feloldó konzisztencia (1)
Az eseményeknek a feloldó konzisztenciamodellben megengedett lehetséges sorrendje.
Gyenge konzisztencia esetén megengedett eseménysorrend. Gyenge konzisztencia esetén tiltott eseménysorrend.
Feloldó konzisztencia (2) Szabályok: • Megosztott adaton bármely olvasási/írási művelet előtt minden korábbi igénylésnek be kell fejeződnie. • Feloldási művelet előtt a folyamatnak az összes korábbi írási/olvasási műveletét be kell fejeznie. • A szinkronizáló változók elérése FIFOkonzisztens.
6
2010.05.06.
Belépő konzisztencia (1) Feltételek: • Szinkronizáló változó adott folyamat általi igénylése addig nem történhet, amíg az általa védett megosztott adat valamennyi frissítőművelete be nem fejeződött az adott folyamat számára. • A folyamat csak akkor szerezheti meg a kizárólagos ellenőrzést a szinkronizáló változó felett, ha egyetlen más folyamat sem birtokolja. • Miután egy folyamat megszerezte a kizárólagos ellenőrzést egy szinkronizáló változó felett, bármely más folyamat nem kizárólagos ellenőrzési kérelme addig nem teljesíthető, amíg a kizárólagos jogot az azt birtokló folyamat fel nem adja.
Belépő konzisztencia (2)
A belépő konzisztenciában érvényes eseménysorrend.
7
2010.05.12.
10. előadás
Adatközpontú konziszteniamodellek összehasonlítása Konzisztencia
Konzisztencia és többszörözés
Leírás
Szigorú
Valamennyi megosztott hozzáférés abszolút sorrendje.
Lineáris
A megosztott hozzáféréseket valamennyi folyamat pontosan ugyanabban a sorrendben látja. A hozzáférések sorrendjét (nem egyedi) globális időbélyeg határozza meg.
Soros
A megosztott hozzáféréseket valamennyi folyamat pontosan ugyanabban a sorrendben látja. A hozzáférések nincsenek idő szerint sorba rendezve.
Okozati
Az okozatilag összefüggő megosztott hozzáféréseket valamennyi folyamat pontosan ugyanabban a sorrendben látja.
FIFO
Valamennyi folyamat a többi írási műveleteit pontosan a kiadás sorrendjében fogja látni. A különböző folyamatok által végrehajtott írási műveletek sorrendje bármi lehet. (a)
2. rész
Konzisztencia
Leírás
Gyenge
A megosztott adat konzisztens voltára csak a szinkronizálás végrehajtása után lehet számítani.
Feloldó
A megosztott adat konzisztensé válik a kritikus terület elhagyásakor.
Belépő
A kritikus területhez tartozó megosztott adat konzisztensé válik a kritikus területre való belépéskor. (b)
a) b)
Gyenge konzisztencia (ismétlés)
a) b)
Gyenge konzisztencia esetén megengedett eseménysorrend. Gyenge konzisztencia esetén tiltott eseménysorrend.
Belépő konzisztencia (ismétlés)
Szinkronizáló műveleteket nem igénylő konzisztenciamodellek. Szinkronizáló műveleteken alapuló konzisztenciamodellek.
Feloldó konzisztencia (ismétlés)
Az eseményeknek a feloldó konzisztenciamodellben megengedett lehetséges sorrendje.
Kliensközpontú konzisztenciamodellek • Adattárak különleges csoportja: • nincs párhuzamos módosítás • a legtöbb művelet csak olvassa az adattárat
Fokozatos konzisztencia (1) A belépő konzisztenciában érvényes eseménysorrend. • Frissítés hiányában valamennyi másolat lassan az összes többivel egyformává válik (a frissítéseket előbb-utóbb valamennyi másolathoz elküldjük)
1
2010.05.12.
Fokozatos konzisztencia (2)
Fokozatos konzisztencia (3) • Probléma: a felhasználó nem mindig ugyanahhoz a másolathoz csatlakozik
• Megoldás: kliensközpontú konzisztencia – egy adott felhasználó számára nyújt biztosítékot arra nézve, hogy az általa látott adattár konzisztens lesz
Az elosztott adatbázis különböző másolatait elérő mozgó felhasználó elve.
Monoton olvasás (1)
Monoton olvasás (2)
Ha a folyamat beolvassa x adatelemet, akkor x minden további olvasásának ugyanazt vagy frissebb értéket kell szolgáltatnia.
Adott P folyamat által végzett olvasási műveletek az adattár két különböző helyi másolatán futnak. a) Monoton olvasási konzisztens adattár b) Monoton olvasás követelményét ki nem elégítő adattár
Monoton írás (1)
Monoton írás (2)
Adott folyamat által végrehajtott x adatelemet módosító írási műveletnek be kell fejeződnie, mielőtt ugyanez a folyamat újabb írási műveletet hajtana végre ugyanezen az adatelemen.
Egyetlen P folyamat által ugyanazon adattár két különböző másolatán végrehajtott írási műveletek sorrendje. a) Monoton írási konzisztenciával rendelkező adattár esete b) Monoton írási konzisztencia követelményét nem teljesítő adattár esete
2
2010.05.12.
Olvasd az írásod (2)
Olvasd az írásod (1) Adott folyamat által x adatelemen végrehajtott írási művelet eredményének mindig láthatónak kell lennie a folyamat által x adatelemen végrehajtott későbbi olvasási művelet számára.
a) b)
Az „olvasd az írásod” konzisztencia követelményét kielégítő adattár „olvasd az írásod” konzisztenciának nem megfelelő adattár
Írás olvasás után (1)
Írás olvasás után (1) A folyamat által x adatelemen végrehajtott írási művelet, amely x adatelemnek a folyamat által korábban történt olvasását követi, feltétlenül ugyanazt az értéket vagy annál frissebbet állít be, mint amit korábban olvasott. a) b)
Kliensközpontú konzisztencia implementálása (1)
Az „írás olvasás után” konzisztens adattár Az „írás olvasás után” konzisztencia követelményét nem teljesítő adattár
Kliensközpontú konzisztencia implementálása (2)
• Minden írási művelethez egyedi azonosítót rendelünk. • Probléma: olvasás- és íráskészletek mérete
• Minden kliens tárol: • Olvasáskészlet • Íráskészlet
• Megoldás: szakaszokra bontás
• Monoton olvasás: olvasás előtt olvasáskészlet ellenőrzése • olvasáskészletben az írások kiadási helyének és idejének
• Probléma: teljes készlet átküldése a hálózaton • Megoldás: időbélyeg vektorok
tárolása
• Monoton írás: írás előtt íráskészlet vizsgálata • Olvasd az írásod: olvasás előtt íráskészlet vizsgálata • Írás olvasás után: írás előtt olvasáskészlet vizsgálata
3
2010.05.12.
Másolat elhelyezése (1)
Elosztott protokollok Implementációs kérdések konzisztenciamodelltől függetlenül.
• Másolat elhelyezése • Frissítés terjesztése • Járványprotokollok Az adattár különböző típusú másolatainak három koncentrikus körként megjelenített logikai szervezése.
Másolat elhelyezése (2)
Szerver által kezdeményezett másolatok
• Másolatok típusa: • Állandó másolatok: másolatok kezdeti készlete, tükrözések, biztonsági másolatok
• Szerver által kezdeményezett másolatok: szükségmásolatok (dinamikus)
• Kliens által kezdeményezett másolatok: kliensoldali gyorsítótár (cache)
Különböző kliensektől érkező kérések számlálása.
Frissítés terjesztése • Mit kell elterjeszteni? • frissítésről szóló értesítés – érvénytelenítő protokollok • adatok – a módosított adat átküldése • frissítőművelet – mit kell a másolatoknak lefuttatnia • Ki kezdeményezzen? • küldés alapú módszer (szerver alapú protokoll) • rendelés alapú módszer (kliens alapú protokoll) • vegyes módszer: haszonbérlet (dinamikus: kor alapú,
Rendelő és küldő protokollok Témakör
Küldés alapú
Rendelés alapú
Szerverállapot
A kliensmásolatok és -gyorsítótárak listája
Nincs
Küldött üzenetek
Frissítés (esetleg letöltő frissítés később)
Lekérdezés és frissítés
Válaszidő a kliensnél
Azonnali (vagy letöltő frissítés ideje)
Letöltő frissítés ideje
megújítási frekvencia alapú, szerverterhelés alapú)
• Hogyan küldjük? • egycímű átvitel • többcímű átvitel
A küldés és a rendelés alapú protokollok összehasonlítása az egyszerveres, többkliensű rendszerekben.
4
2010.05.12.
Járványprotokollok (1) • Fokozatos konzisztencia implementálásához • fertőző: terjesztendő frissítéssel rendelkező • fertőzhető: még nem frissített • elkülönített: frissített, de terjesztésre nem képes • Frissítésterjesztő modellek: • küldési módszer • rendelési módszer • küldés-rendelés módszer
Járványprotokollok (2) • másik módszer: rémhírterjesztés / pletykálkodás • nincs garancia a teljes elterjedésre • Adatok eltávolítása: • törlést nehéz elterjeszteni • halotti bizonyítványok – törlés, mint frissítés • halotti bizonyítvánnyal rendelkezők mikor törölhetők?
• az eddigi módszerekkel a fertőzés előbb-utóbb elterjed
5
2010.05.12.
11. előadás
Konzisztencia és többszörözés Konzisztencia és többszörözés 3. rész
3. rész
Hibatűrés 1. rész
Konzisztenciaprotokollok (soros)
Elsődleges másolaton alapuló protokollok
Távoli írás protokollok (1)
Az adattár minden elemének van elsődleges másolata, aki felel az írási műveletek koordinálásáért.
Elsődleges távoli írás-protokoll, az olvasási és írási műveletek elvégzésére kizárólagosan hivatott rögzített szerverrel.
Távoli írás protokollok (2)
Az elsődleges másolatprotokoll alapelve.
Helyileg író protokollok (1)
Elsődleges másolat alapú helyileg író protokoll, amelyben az adatelem egyetlen példánya vándorol.
1
2010.05.12.
Helyileg író protokollok (2)
Többszálú írás-protokollok Az írási művelet több másolaton is végrehajtható
A frissítést végrehajtani kívánó folyamatok között vándorló elsődleges másolat protokollja.
Aktív többszörözés (1)
Aktív többszörözés (2)
a)
A többszörözött hívás problémája. b)
Testület alapú protokollok (1) • Többszörözött írás támogatása szavazás alapján • Olvasás és írás előtt a többiektől engedélyt kell kérni • Olvasási testület: NR • Írási testület: NW • NR + NW > N • NW > N/2
Továbbítja a többszörözött objektumtól érkező hívási kérést egy másik többszörözött objektumnak. A válasz visszaküldése az egyik többszörözött objektumtól a másiknak.
Testület alapú protokollok (2)
A szavazó algoritmus három példája: a) Az írási és olvasási testület taglétszámának helyes megválasztása b) Lehetséges írás-írás ütközéshez vezető taglétszám c) A ROWA (read one, write all) néven ismert helyes taglétszámválasztás
2
2010.05.12.
Gyorsítótár-egyezőségi protokollok (1) • Egyöntetűség-észlelő stratégia – mikor veszik észre a tár eltérő voltát – statikus – dinamikus
• Mikor történik az észlelés? – tranzakció előtt – tranzakció közben – tranzakció lezárásakor
Gyorsítótár-egyezőségi protokollok (2) • Egyöntetűség-biztosítási stratégia – hogyan maradnak konzisztensek az adatok – – – – –
megosztott adat csak a szerveren változáskor érvényesítő üzenet változáskor frissítés terjesztése keresztülíró gyorsítótár visszaíró gyorsítótár
Alapelvek (1) Üzembiztos rendszer
Hibatűrés 1. rész
Alapelvek (2) • • • •
Meghibásodott rendszer Hiba Hibaok Hibatűrő képesség
• Hibák csoportosítása – alkalmi hiba – ismétlődő hiba – állandó hiba
• • • •
Elérhetőség (availability) Megbízhatóság (reliability) Biztonságosság (safety) Kezelhetőség (maintainability)
Meghibásodásmodellek Meghibásodás típusa
Leírás
Összeomlás (crash)
A szerver megáll, de a leállás pillanatáig helyesen működött
Kiesés (omission) Fogadási (receive) kiesés Küldési (send) kiesés
A szerver nem válaszol a beérkező üzenetekre A szerver nem kapja meg a beérkező üzeneteket A szerver nem tud üzenetet küldeni
Időzítési hiba (timing)
A szerver válaszküldésének időpontja kívül esik a meghatározott időintervallumon
Válaszhiba (response) Értékhiba Állapotátmeneti hiba
A szerver hibás választ küld A válaszüzenet értéke rossz A szerver eltér a helyes vezérlési sorrendtől
Váratlan hiba (arbitrary)
A szerver tetszőleges időpontban tetszőleges válaszokat tud előállítani
A meghibásodások különböző típusai.
3
2010.05.12.
Meghibásodás elfedése redundanciával
Hármas moduláris redundancia.
Egyenlő és hierarchikus csoportok
a) b)
Közös megegyezés a hibás rendszerekben (1)
Kommunikáció az egyenlő csoportban Kommunikáció az egyszerű hierarchikus csoportban
Közös megegyezés a hibás rendszerekben (2)
A bizánci tábornok problémája három lojális és egy áruló tábornok esetén. a) A tábornokok jelentik a saját haderejük nagyságát b) A négy tábornok által összegyűjtött információ-vektorok c) A harmadik lépésben megkapott vektorok
Ugyanaz, mint az előző ábra, de ezúttal két lojális és egy áruló tábornok esetére.
A szerver összeomlása (1)
A szerver összeomlása (2) Kliens
Szerver M -> P stratégia MPC
MC(P)
C(MP)
PMC
PC(M)
Mindig
DUP
OK
OK
DUP
DUP
OK
OK
ZERO
ZERO
OK
OK
ZERO
DUP
OK
ZERO
DUP
OK
ZERO
OK
ZERO
OK
OK
DUP
OK
Soha Csak ha jött ACK Csak ha nem jött ACK
A szerver működése a kliens-szerver kommunikációban a) Alapeset b) Összeomlás a végrehajtás után c) Összeomlás a végrehajtás előtt
P -> M stratégia
Újraküldési stratégia
C(PM)
A szerver és a kliens stratégiák különböző kombinációi szerverhiba esetén
4
2010.05.12.
12. előadás
Hibatűrés fokozása redundanciával • Megbízhatatlan folyamatok
• Többszörözés megvalósítása
Hibatűrés 2. rész
Megbízható csoportkommunikáció (1) Megbízható többcímű átvitel: a csoportnak küldött üzenet a csoport valamennyi tagjához eljut. Átviteli réteg – megbízható pont-pont csatornákat kínál. • Minden folyamat helyesen üzemel • Hibás folyamatok is vannak
Alapvető megbízható csoportcímű sémák (1)
Megbízható csoportkommunikáció (2) Tfh. Minden folyamat helyesen üzemel + egyezség van a csoport tagságokban => az üzenetet mindenkinek el kell küldeni • A feladó minden többcímű üzenethez sorszámot rendel • A fogadó – Sikeres fogadás esetén nyugta és/vagy – felismeri, ha valami hiányzik negatív nyugtát küld
Alapvető megbízható csoportcímű sémák (1) Feladónak tárolnia kell az üzenetet.
A megbízható csoportcímzés egyszerű megvalósítása, ha minden címzett ismert és egyikről sem feltételezhető a meghibásodás a) Üzenet átvitele b) Visszajelzés küldése
Hátrányok: • Sikeres fogadás esetén nyugta – visszajelzés áradat • Csak negatív nyugta van – feladónak örökre tárolnia kell, vagy nem megbízható az átvitel
1
2010.05.12.
Nem hierarchikus visszajelzés-vezérlés (1)
Nem hierarchikus visszajelzés-vezérlés (2)
• Átméretezhető megoldás - visszajelzés-elfojtás • SRM – átméretezhető megbízható többcímű üzenetküldés (Scalable Reliable Multicasting) • Siker esetén nincs nyugta • Negatív nyugta a csoport összes tagjának (véletlenszerű késleltetéssel) • Ha negatív nyugtát akar küldeni, de közben kap mástól => elfojtás
Nem hierarchikus visszajelzés-vezérlés (3)
Több címzett is beütemezte az újraküldési kérést, de az első újraküldési kérés a többi elfojtásához vezet
Hierarchikus visszajelzés-vezérlés
• Jól átméretezhető • Hátrányok: – folyamatok összehangolásának szükségessége – haszontalan üzenetek fogadása és feldolgozása A megbízható csoportcímzés hierarchikus megvalósítása. a) Valamennyi helyi koordinátor az általa felügyelt gépeknek továbbítja az üzeneteket, és b) kezeli a későbbi újraküldési kéréseket
Elemi csoportcímzés
Látszólagos szinkronitás (1)
A folyamatok meghibásodhatnak => az üzeneteknek valamennyi működő folyamathoz el kell jutniuk (esetleg ugyanabban a sorrendben), vagy egyikhez sem (ha a feladó összeomlik a küldés során) • Üzenet érkezése • Üzenet fogadása
Az üzenet érkezését és kézbesítését megkülönböztető elosztott rendszer logikai felépítése.
2
2010.05.12.
Látszólagos szinkronitás (2)
Látszólagos szinkronitás (3)
• Látszólagos szinkronitás: ha a küldő összeomlik, akkor az üzenetet vagy minden fogadónak meg kell kapnia, vagy egyiknek sem • Csoportkép – kézbesítése lista (minden üzenethez – küldő ismerete) • Látványváltozás – üzenet, ha változik a csoportkép -- határ, amit egy üzenet sem léphet át
Üzenetek sorbarendezése 1. 2. 3. 4.
Rendezetlen üzenetküldés FIFO-sorrendű üzenetküldés Okozatilag sorbarendezett üzenetküldés Pontosan sorbarendezett többcímű üzenetküldés
A látszólagosan szinkronizált többcímű üzenetküldés elve.
Megbízható, rendezetlen csoportcímzés P1 folyamat
P2 folyamat
P3 folyamat
elküldi m1 üzenetet
megkapja m1-et
megkapja m2-t
elküldi m2 üzenetet
megkapja m2-t
megkapja m1-et
Egy csoport három, egymással kommunikáló folyamata. Az események folyamatonkénti sorrendjét a függőleges tengelyen ábrázoljuk.
Megbízható FIFO-sorrendű csoportcímzés
Üzenetek sorbarendezése Csoportcímzés
Alapvető üzenetrendezés
Pontosan rendezett kézbesítés?
P1 folyamat
P2 folyamat
P3 folyamat
P4 folyamat
m1 elküldése
m1 fogadása
m3 fogadása
m3 elküldése
Megbízható csoportcímzés
Nincs
Nem
m3 fogadása
m3 fogadása
m1 fogadása
m1 fogadása
FIFO-csoportcímzés
FIFO-sorrendű kézbesítés
Nem
m2 elküldése
m2 fogadása
m2 fogadása
m2 fogadása
Okozati csoportcímzés
Nem
m4 fogadása
m4 fogadása
m4 fogadása
m4 elküldése
Okozati sorrendű kézbesítés
Elemi csoportcímzés
Nincs
Igen
FIFO elemi csoportcímzés
FIFO-sorrendű kézbesítés
Igen
Okozati elemi csoportcímzés
Okozati sorrendű kézbesítés
Igen
A csoport négy folyamata két feladó esetében, és a FIFO-sorrend által megengedett két lehetséges üzenetkézbesítési sorrend.
A látszólagosan szinkronizált megbízható csoportcímzés hat különböző változata.
3
2010.05.12.
Látszólagos szinkronitás implementálása (1)
Látszólagos szinkronitás implementálása (2)
• Üzenetküldés mindenkinek megbízható pontpont csatornán (pl. TCP) • Ha a feladó összeomlott: a hiányzó üzenetet egymástól is beszerezhetik • Stabil üzenet: minden folyamathoz megérkezett – csak ezeket lehet kézbesíteni a)
• Ürítési üzenet: felkészült az új csoportkép installálására
b) c)
Elosztott véglegesítés
A 4. folyamat észreveszi, hogy a 7-es összeomlott, ezért egy csoportképváltozási üzenetet küld. A 6. folyamat kiküldi valamennyi nem stabil üzenetét, majd egy ürítési üzenetet. A 6. folyamat akkor installálja az új csoportképet, amikor a többi folyamattól ürítési üzenetet kapott
Kétfázisú véglegesítés (1)
• Az adott műveletet a csoport összes tagja hajtsa végre, vagy egyikük sem (az elemi csoportcímzési probléma az elosztott véglegesítés speciális esete – művelet: üzenet kézbesítése) • Egyfázisú véglegesítési protokoll: koordinátor segítségével
Kétfázisú véglegesítés (2) • Első fázis: szavazás • Második fázis: döntés
a) b)
A 2PC-koordinátort jelképező véges állapotgép. A résztvevőt jelképező véges állapotgép.
Kétfázisú véglegesítés (3) Q állapota COMMIT
• Probléma meghibásodás esetén – blokkoló hívások: – résztvevő / INIT: megoldás: timeout – koordinátor / WAIT: megoldás: timeout – Résztvevő / READY: => megvárja, míg újraindul a koordinátor VAGY lekérdezi másik folyamattól
P cselekedete Átmegy COMMIT állapotba
ABORT
Átmegy ABORT állapotba
INIT
Átmegy ABORT állapotba
READY
Másik résztvevőt vizsgál meg
A READY állapotba beragadt P résztvevő által végrehajtható műveletek Q résztvevő állapotának megvizsgálása után.
4
2010.05.12.
Kétfázisú véglegesítés (4)
Kétfázisú véglegesítés (5) A koordinátor lépései:
• A felépülés lehetőségéhez az állapotot menteni kell
while START _2PC to local log; multicast VOTE_REQUEST to all participants; while not all votes have been collected { wait for any incoming vote; if timeout { while GLOBAL_ABORT to local log; multicast GLOBAL_ABORT to all participants; exit; } record vote; } if all participants sent VOTE_COMMIT and coordinator votes COMMIT{ write GLOBAL_COMMIT to local log; multicast GLOBAL_COMMIT to all participants; } else { write GLOBAL_ABORT to local log; multicast GLOBAL_ABORT to all participants; }
• Koordinátor: – 2PC-protokoll megkezdése – döntés meghozása
• Résztvevők: – INIT, COMMIT, ABORT – READY
A koordinátor által végrehajtott lépések vázlata a kétfázisú protokollnál.
Kétfázisú véglegesítés (6)
Kétfázisú véglegesítés (7)
A résztvevők lépései:
A résztvevők lépéssorozatának vázlata a 2PCeljárásban.
write INIT to local log; wait for VOTE_REQUEST from coordinator; if timeout { write VOTE_ABORT to local log; exit; } if participant votes COMMIT { write VOTE_COMMIT to local log; send VOTE_COMMIT to coordinator; wait for DECISION from coordinator; if timeout { multicast DECISION_REQUEST to other participants; wait until DECISION is received; /* blokkolva marad */ write DECISION to local log; } if DECISION == GLOBAL_COMMIT write GLOBAL_COMMIT to local log; else if DECISION == GLOBAL_ABORT write GLOBAL_ABORT to local log; } else { write VOTE_ABORT to local log; send VOTE ABORT to coordinator; }
Háromfázisú véglegesítés (1)
Akciók a döntési kérelmek kezeléséhez: /* végrehajtva elkülönített szálon */ while true { wait until any incoming DECISION_REQUEST is received; /* blokkolva marad */ read most recently recorded STATE from the local log; if STATE == GLOBAL_COMMIT send GLOBAL_COMMIT to requesting participant; else if STATE == INIT or STATE == GLOBAL_ABORT send GLOBAL_ABORT to requesting participant; else skip; /* résztvevő blokkolva marad */
A bejövő döntési kérések lépéssorozatának vázlata.
Háromfázisú véglegesítés (2)
• Megakadályozza a folyamatok blokkolódását megállási meghibásodások esetében • Nincs egyetlen olyan állapot sem, amelyből közvetlen átmenet lenne akár a COMMIT, akár az ABORT állapotba • Nincs olyan állapot, amelyben ne lenne lehetséges a végső döntés elérése, miközben közvetlen átmenet van a COMMIT állapotba
a) b)
A 3PC koordinátorának véges állapotgépe. A résztvevő véges állapotgépe.
5
