Informatika | Operációs rendszerek » Időkezelés és koordináció elosztott rendszerekben

Időkezelés és koordináció elosztott rendszerekben Elosztott rendszerekben az idő, és annak konzisztens kezelése központi jelentőségű. Egyes alkalmazásokban a pontos, valós időre van szükség (pl. naplózás, számlakezelés), míg az esetek jelentős részében elegendő olyan időkezelés, amely biztosítja a rendszerben bekövetkező események sorrendezését. külső szinkronizáció: pontos, külső órához kell szinkronizálni belső szinkronizáció: az elosztott rendszer órái egymáshoz szinkronizáltan működnek, de lehet, hogy csúsznak a pontos külső órához képest esemény: oszthatatlanul hajtódik végre, pillanatnyi jellegű Ha az események az óra felbontásánál gyakrabban (nagyobb frekvenciával) következnek be, akkor azokat nem lehet sorrendezni. naív feltételezés: a elég ismerni az egyes órák közötti eltérést, és akkor megoldható sorrendezés Nem, mert az órák csúsznak. Kvarc oszcillátor alapú órák is csúsznak,

vagyis az időt más "ferkvenciával" mérik, mint a pontos referencia óra, így az általuk mutatott idő egyre jobban eltér attól. A csúszás lehet nagyon pici, de az idő múltával az akkumulálódik. Pl kvarc oszcillátoros órák: ~10-6 sec/sec pontosak --> 1 másodperc 1000000 másodperc alatt (11.6 nap) Koordinált Univerzális Idő (KUI) Érdekesség: atomóra pontossága: 10-13 sec/sec Nemzetközi Atomidő: 9192631777 átmenet a Cs133 alapállapotának 2 hiperfinom szintje között Az emberiség az időt a csillagászati időhöz szökőmásodperceket kell beiktatni, vagy törölni igazítja --> KUI KUI-t sugározzák rádióállomások (pl. az amerikai WWV), űrszondák: Geostationary Operational Environmental Satellites (GOES) Global Positioning System (GPS) Terjedés: Magyarország kb. 500 km széles, 3X108 m/s --> 1-2 msec légköri zavarok --> terjedési idő pontosan nem számítható KUI rádió: GEOS GPS: ~0,1 - 10 ms ~0,1 ms ~1 ms

(néha Időszolgáltatók sok helyen fel vannak szerelve KUI vevővel, így ahhoz szinkronizálhatnak. Fontos! 10 ms nem elég pontos számos alkalmazás számára azok eseményeinek sorrendezésére. Egy 10 MIPS-es gép ennyi idő alatt 100000 utasítást végez el Óracsúszás kompenzálása Egy adott gép órája kétféleképpen csúszhat a valós, pontos órához képest: késhet, illetve siethet. Az első esetet viszonylag egyszerűen le lehet kezelni Ha a valós időt Tval, a pontatlan lokális időt Tlok jelöli, és Tval > Tlok, akkor Tlok := Tval állítással a problémát meg lehet oldani. Ez a módosítás teljesítia természetes elvárást, hogy az idő értéke növekedjen. Sajnos ennél nehezebb problémával találjuk szemben magunkat, ha a lokális óra siet. Nem tehetjük meg, hogy egyszerűen visszaállítjuk, mert ekkor az a feltételezés, hogy az idő előre halad nem teljesülne. (pl Unix make csak azokat az állományokat fordítja újra, amelyeknek a

forrása frissebb, mint a hozzájuk tartozó object állomány. Ha megengednénk az óra visszaállítását, akkor előállhatna az az eset, hogy ódosítunk egy forrás állományt, és a make mégsem fordítja újra, mert közben a szinkronizálás miatt az órát a rendszer visszaállította, és így az object állomány későbbinek tűnik.) Így azt kell elérni, hogy az óra lassabban járjon. A hardver órát általában nem lehet lassítani, így a szoftver órát kell állítani A továbbiakban használjuk az alábbi jelöléseket: S(t): szoftver óra H(t): hardver óra δ(t): kompenzáció S(t) = H(t) + δ(t) Amennyiben a módosítást folytonosnak szeretnénk, akkor δ(t) legyen egy lineáris függvény: δ(t) = aH(t) + b Tegyük fel, hogy S(t) = Tskew amikor H(t) = h, és ekkor a pontos referencia óra Treal-t mutat. Ha azt akarjuk elérni, hogy S N további tikk után mutassa a pontos időt, akkor Tskew = (1+a)h + b (behelyettesítést elvégezve) Treal+N = (1+a)(h+N) +

b ebből a = (Treal - Tskew)/N és b = Tskew - (1+a)h Órarendszerek csoportosítása Pontos központi órával rendelkező rendszerek • • • egy pontos óra szolgáltatja az idót az egész rendszernek. (A többi óra jelenlétéről nem veszünk tudomást, amíg a központi óra meg nem hibásodik.) Hibatűrés --> meleg tartalék A módszer pontos (az alkalmazott órától függően ns - ms), de drága • speciális a processzorba integrált hardvert igényel. Az óra ezt állítja, a többi folyamat ezt olvassa. Kommunikációs költség alacsony: 1 üzenet/szinkronizáció/hely, vagy broadcast példa: GPS, 4 szatelit , ~ ns • • Központilag felügyelt órákkal rendelkező rendszerek (master -slave) • • • • pontosnak elfogadott master óra lekérdezi a slave-eket csúszásokat mér, korrekciót küld a slave-eknek master meghibásodik --> választás átviteli időt becsülik Elosztott órás rendszerek • • • • minden hely homogén,

azonos algoritmust futtat minden hely a többi óra üzenete alapján frissíti a saját óráját (becsüli saját pontosságát) hibatűrés protokoll alapú --> észreveszik, ha valamelyik óra meghibásodott, és figyelmen kívül hagyják az értékét nagy kommunikációs költség Cristian algoritmusa ábra kliens --> kérés --> szerver --> válasz tartalmazza az időt is --> kliens Tround-ot a kliens a saját órájával mérheti 10-6-os pontossággal. Az időszolgáltató a válaszba csak az utolsó pillanatban írja be az időt, így a Tround mérése pontosabb lesz. Berkeley algoritmus (master - slave típusú) A master lekérdezi a slave-ek idejét és korrekciót küld vissza. A nagy eltéréseket kihagyja --> hibatűrő átlagolás. Elért pontosság: 20 - 25 ms A Network Time Protocol Az Internet időmodellje a Network Time Protocol. Tervezési célok: • kliensek pontosan szinkronizálhassanak a KUI-hez • megbízható szolgáltatás legyen, éljen

túl hosszú idejű szétcsatolást • kellően gyakori szinkronizálást tegyen lehetővé • védjen időszolgáltatás hamisítás ellen Struktúra: ábra szinkronzációs alhálózat stratum: szint elsődleges szerver: közvetlen KUI vevő másodlagos szerver: elsődleges szerverrel szinkronizál Minél magasabb egy szerver stratuma, annál pontatlanabb, megbízhatatlanabb. Három típusú szinkronizálás: multicals (LAN) - kis késleltetést feltételez, pontatlan, de sok alkalmazás számára ez elég eljáráshívás szerver - kliens kapcsolat, kérések, nagyobb pontosság, vagy olyan esetekben, ahol multicast nem támogatott szimmetrikus mód <ofszet, konf. int d> alakú üzenetek A gépek az utolsó nyolcat tárolják, a legkisebb d-jűt választják. ~1991: ~ 20 - 30 elsődleges szerver ~ 2000 másodlagos szerver ~ 30 ms pontosság. De ez best-effort szolgáltatás, nincs garantált időkorlát. Logikai idő és logikai órák Tetszőleges folyamatban a folyamat

eseményeit egyértelműen sorba lehet rendezni a folyamat fizikai órája alapján. Elosztott rendszerekben sajnos fizikai órát nem lehet események sorrendezésére használni, mert a folyamatok fizikai óráit nem lehet tökéletesen szinkronizálni. Ezért szükség van valamilyen módszerre, amely biztosítja a folyamatok eseményeinek sorrendezését elosztott környezetben. Mielőtt rátérnénk a módszer tárgyalására, definiáljuk a korábban-történt relációt. Ennek értelmezéséhez tekintsük először azonban az alábbi két triviálisnak tűnő kijelentést: 1. Ha két esemény ugyanabban a folyamatban történt, akkor azok sorrendje megegyezik azzal a sorrenddel, ahogyan azt a folyamat látja. 2. Amikor egy folyamat üzenetet küld egy másik folyamatnak, akkor az üzenet elküldése megelőzi az üzenet megkapását. Ezek után már definiálható a korábban-történt reláció, az alábbi jelölésekkel: P x  y : x és y két esemény, mindkettő

egyazon P folyamatban történt, és x megelőzte y-t. x   y folyamat : x korábban-történt relációban van y-nal (x és y nem egy eseményei) P KT1: Ha ∃ P folyamat, melyre x   y KT2: ∀m üzenetere send( m)   rcv( m) − − , akkor x   y , ahol send(m) az üzenet elküldésének, rcv(m) pedig az üzenet megkapásának eseménye. KT3: Ha x, y és z olyan események, amelyekre x   y és y   z , akkor x   z ábra Logikai órák A korábban-történt rendezéshez támogatást kell nyújtani, hogy azt számszerűen meg lehessen ragadni. Ezt a szerepet hivatott betölteni a logikai óra A logikai óra monoton növekvő szoftver számláló, amelynek az értéke nem kell, hogy bármilyen fizikai órához kapcsolódjon. Minden P folyamatnak van egy saját logikai órája, CP, amelyet a folyamat események időcímkével való ellátására használ. A következőkben a P folyamatban az a esemény időcímkéjét CP(a) jelöli,

míg egy tetszőleges folyamat b eseményét C(b). A folyamatok az alábbiak szerint állítják a logikai órájukat, illetve az üzenetekben az alábbi időcímkéket küldik: LÓ1: CP minden egyes esemény P-beli bekövetkezte előtt inkrementálódik: CP := CP + 1 LÓ2: a) Amikor egy P folyamat egy m üzenetet küld, akkor a folyamat az m üzenetet t = CP időcímkével látja el. b) Amikor egy Q folyamat megkap egy (m, t) üzenetet, kiszámolja CQ := max(CQ, t)-ot és aztán alkalmazza LÓ1-et az rcv(m) esemény időcímkével történő ellátása előtt. A fenti logokai órára teljesül az alábbi összefüggés: a b ⇒ C(a) < C(b) Könnyen belátható azonban, hogy a fenti összefüggés fordítottja nem igaz, vagyis C(a) < C(b), abból nem következik, hogy a b. A 6 ábra az 5 ábra példájára alkalmazza a logikai órákat. Mind P1, P2 és P3 logikai órája 0 kezdőértékkel indul Az órák értékei a hozzájuk legközelebbi esemény utáni értéket mutatja. A

példából látható, hogy C(b) > C(e), de b || e. Teljesen rendezett logikai órák Az előbbiekben tárgyalt logikai óra konstrukció csak részleges rendezést ad az eseményeken, hisz léteznek olyan különböző folyamatokhoz tartozó események, amelyekhez azonos logikai óra érték tartozik. Azonban viszonylag egyszerűen ki lehet teljesíteni a fenti sémát, hogy az teljes rendezést adjon. Ehhez a folyamatok azonosítóját is fel kell használni az időcímkék megkonstruálásához. Ha a Pa folyamat egy eseménye, amely Ta helyi időcímkével rendelkezik, és b Pb folyamat egy eseménye, amely Tb helyi időcímkével rendelkezik, akkor az ezen eseményekhez tartozó globális időcímkék: (Ta, Pa), illetve (Tb, Pb). Ezek segítségével a teljes rendezés: (Ta, Pa) < (Tb, Pb) akkor ;s csak akkor, ha Ta < Tb vagy Ta = Tb és Pa < Pb. Elosztott koordináció Elosztott folyamatoknak is koordinálni kell a tevékenységüket, különös tekintettel az

osztottan kezelt erőforrásokra. Mint azt a korábbiakban láttuk, a Sun NFS egy állapotmentes szerver, így ott állományok megosztott kezelésére nem lehet a szerveren lockokat használni, hisz ez ellentmondona az állapotmentességnek. Így ebben az esetben a Unix egy külön daemon - a lockd segítségével oldja meg a szinkronizálást. Azonban gyakran célszerű az erőforrást kezelő szerverrel szervesen egybeépíteni a szinkronizálási eszközöket. A leggyakrabban előforduló szinkronizálás osztottan használt erőforrások esetén a kölcsönös kizárás. Elosztott rendszerekben az elosztottság a korábban megismert megvalósításokkal szemben újabb igényeket támaszt, amelyeket elosztott kölcsönös kizárási algoritmusokban figyelembe kell venni. A továbbiakban ezekre nézünk meg néhány példát. Elosztott kölcsönös kizárás Egy osztottan használt erőforrással kapcsolatosan a kölcsönös kizárással szemben az alábbi követelményeket

támasztjuk: KK1(biztonság): KK2(életteliség, haladás): Választási algoritmusok Elosztott rendszerekben a választási algoritmusok nagy szerepet kapnak. Feladatuk egy folyamatcsoportból egy kitüntetett folyamat kiválasztása. Ezen folyamat több szempontból is lehet kitüntetett: például kölcsönös kizárást biztosító szerver, koordinátor, tokengenerátor, stb. A választási algoritmus eredményeként kiválasztott folyamattal szemben a fő követelmény, hogy a kiválasztott folyamat egyedi legyen, a csoport minden folyamata ugyanazt a folyamatot gondolja megválasztottnak, még akkor is, ha egyszerre több folyamat is elindítja a választást. A továbbiakban két algoritmust vizsgálunk meg: a bully algoritmust, amely esetén a résztvevő folyamatok ismerik egymás azonosítóit, azok prioritását, míg a gyűrű algoritmus esetén csak az egyik szomszéd kommunikációs azonosítójára van szükség. A bully (erőszakos) algoritmus Az algoritmus akkor

alkalmazható, ha a folyamatcsoport tagjai ismerik egymás azonosítóit (illetve a hozzájuk rendelt prioritásokat - gyakran a prioritás megegyezik az azonosítóval), és hálózati címeit. Az algoritmus a folyamatcsoportból kiválasztja a legnagyobb prioritású még aktív folyamatot, és megválasztja koordinátornak. Az algoritmus működése során feltételezzük, hogy a kommunikáció megbízható, de a folyamatok maga a válaszási algoritmus alatt is meghibásodhatnak, továbbá a tárgyalás leegyszerűsítése érdekében a folyamat azonosítója egyben a prioritása is, és a nagyobb azonosító nagyobb prioritást jelöl. Az algoritmusban három típusú üzenet jelenhet meg: • • • választás válasz koordinátor - választás megkezdését jelzi - választási üzenet válasza - az új, megválasztott koordinátor azonosítóját küldi szét Az algoritmus mindig azzal kezdődik, hogy egy folyamat észreveszi a koordinátor meghibásodását. Legyen ez

Pi Ekkor: • • • • Pi választás(Pi) üzenetet küld minden egyes Pj | j > i Ezután Pi várakozik válasz(Pj)-re Tvv ideig. Ha nem érkezik válasz, akkor Pi magát tekinti a legnagyobb prioritású, még működő folyamatnak (hisz a magasabb prioritásúaktól nam kapott választ), és az alacsonyabb prioritású folyamatoknak kiküld egy koordinátor(Pi) üzenetet, vagyis, megválasztja magát koordinátornak. Ha érkezett valamilyen Pj | j > i folyamattól válasz, akkor Pi vár Tvk ideig, hogy a magasabb prioritású folyamat koordinátornak deklarálja magát. Amennyiben Tvk alatt nem jön ilyen üzenet, újabb választást kezdeményez. Ha egy folyamat egy koordinátor(Pj) üzenetet kap, akkor feljegyzi az üzenetben szereplő folyamat azonosítóját, és ettől kezdve ezt a folyamatot koordinátorként kezeli. Ha egy Pj folyamat választás(Pi) üzenetet kap, akkor visszaküld egy válasz(Pj) üzenetet, és Pj is kezdeményez egy választást, hacsak már

nem kezdeményezett korábban. Amikor egy meghibásodott folyamat újraindul, azonnal választást kezdeményez. Amennyiben ennek a folyamatnak a legnagyobb prioritású az azonosítója, akkor úgy dönt, hogy ő lesz a koordinátor, még akkor is, ha a korábbi koordinátor működőképes. Ezért kapta az algoritmus a nevét, vagyis, hogy erőszakos, hisz minden körülmények között a legmagasabb prioritású működő folyamat lesz a koordinátor. Az algoritmus működésének bemutatására tekintsük az alábbi egyszerű példát (ábra): Négy folyamat alkotja a folyamatcsoportot, ezek P1, P2, P3 és P4. P1 észreveszi a P4-es koordinátor folyamat meghibásodását, és egy választást kezdeményez. (a 11 ábra 1. lépése) A választás üzenet megkapása után P2 és P 3 válasz üzenetet küld vissza P1-nek, és maga is választást kezdeményez, de P3 nem kap választ a meghibásodott P4-es folyamattól (2. lépés) Ennek hatására P3 úgy dönt, hogy maga lesz a

koordinátor, de mielőtt kiküldhetné a koordinátor üzenetet maga is meghibásodik (3. lépés) Amikor P1 időkorlátja lejár (ebben az esetben feltételezzük, hogy hamarabb jár le, mint P2-é) észreveszi a koordinátor üzenet hiányát és újabb választást kezdeményez. Ekkor P2 lesz a koordinátor (4 lépés) 11. ábra: P2 P4 és P3 meghibásodása után koordinátorrá választása Az algoritmus során küldött üzenetek száma A legkedvezőbb esetben a második legnagyobb prioritású folyamat veszi észre a koordinátor meghibásodását és kezdeményez választást. Ekkor rögtön megválaszthatja magát, és szétküld (n-2) koordinátor üzenetet az alacsonyabb prioritású folyamatoknak. A legrosszabb esetben a Bully algoritmus O(n2) üzenetet igényel. Ebben az esetben a legkisebb prioritású folyamat észleli a koordinátor meghibásodását, és mind az (n-1) folyamat választást kezdeményez, választás üzeneteket küldve a magasabb prioritású

folyamatoknak. A gyűrű algoritmus A folyamatcsoportban lévő folyamatokat egyirányú logikai gyűrűbe kell szervezni. Ez nem jelent megkötést a fizikai topológiára. Ebben az esetben feltételezzük, hogy az egyes folyamatok nem ismerik egymás azonosítóit, így prioritásukat sem, csak azt tudják, hogyan kell kommunikálni az egyik, mondjuk az óra járásával megegyező szomszédjukkal. Az algoritmus célja a legnagyobb prioritású egyedi koordinátor megválasztása. Az algoritmus feltételezi, hogy a folyamatok az algoritmus alatt nem hibásodnak meg, és elérhetők maradnak. Kezdetben minden folyamat a választásban nem-résztvevő-nek van jelölve. Bármelyik folyamat kezdeményezhet választást. Ekkor első lépésben választában résztvevő-nek jelöli magát, és az azonosítóját egy választás üzenetben elküldi a szomszédjának. Amikor egy folyamat egy választás üzenetet kap, összehasonlítja az üzenetben foglalt azonosítót a sajátjával.

Amennyiben a beérkezett azonosító nagyobb, a folyamat továbbítja az üzenetet a szomszédjának. Azonban ha a beérkezett azonosító kisebb a saját azonosítójánál, akkor a folyamat először megvizsgálja, hogy résztvevő-e. Amennyiben nem, akkor az üzenetben lecseréli az azonosítót a sajátjára, és résztvevőnek jelöli magát, majd továbbítja a választás üzenetet a szomszédjának. A folyamat akkor is résztvevő-nek jelöli magát, ha nem cserélte le az azonosítót. Amennyiben az azonosító megegyezik az üzenetet kapó folyamat saját azonosítójával, akkor a kör bezárult, a folyamat a legnagyobb prioritású folyamat a körben, ő lesz a koordinátor. A folyamat nem-résztvevő-nek jelöli magát, és egy megválasztott üzenetet küld a szomszédjának a saját azonosítójával, így tudatva a koordinátor kilétét. Ha egy nem koordinátor folyamat megválasztott üzenetet kap, magát nem-résztvevőnek jelöli, megjegyzi a koordinátor

azonosítóját és továbbítja az üzenetet a szomszédjának. Folyamatok résztvevő-nek, illetve nem-résztvevő-nek jelölésének értelme akkor domborodik ki, amikor egyszerre több folyamat kezdeményez választást. Ekkor a fenti jelöléseket ki lehet használni, és minimalizálni lehet az üzeneteket. Az algoritmus során küldött üzenetek száma Ha csak egy folyamat kezdeményezi a választást, akkor a legrosszabb eset olyankor áll fenn, amikor a kezdeményező óra járásával ellentétes szomszédja birtokoljaa legmagasabb azonosítót. Ekkor ezen szomszéd eléréséhez n - 1 üzenet szükséges, amely addig nem nyilvánítja magát koordinátornak, amíg a saját üzenetét vissza nem kapja újabb n üzenettel később. Ekkor a megválasztott üzenet is n-szer megjelenik, így összesen 3n - 1 üzenetre van szükség. A 12 ábra egy gyűrűs választási algoritmust mutat. A választást a 17-es folyamat kezdeményezte A választás üzenet jelenleg a 24-es

azonosítót tartalmazza, de a 28-as folyamat ezt majd lecseréli a saját azonosítójára, ha majd megkapja az üzenetet. A sötét körök a résztvevő folyamatokat jelölik. 12. ábra: Gyűrű választási algoritmus