arvostelija
Stabilointi
Marja Hassinen
Helsinki 28.10.2007
Hajautetut algoritmit -seminaari HELSINGIN YLIOPISTO Tietojenk¨asittelytieteen laitos
Sis¨ alt¨ o
1 Johdanto 1
2 Resynkroninen stabilointi 2
3 Yleinen stabilointi: j¨arjestelm¨an tarkkailu ja alustus 4 3.1 Virheiden havaitseminen . . . 4 3.2 J¨arjestelm¨an alustus . . . 8 3.3 J¨arjestelm¨an toipumiskyky . . . 12
4 L¨ahteet 13
1 Johdanto
T¨am¨a esitelm¨a k¨asittelee stabilointia eli algoritmien muuntamista toipumiskykyi- siksi (self-stabilizing). Jos johonkin ongelmaan tunnetaan algoritmi, joka ei ole toi- pumiskykyinen, voidaan stabiloinnin avulla muodostaa vastaava toipumiskykyinen algoritmi.
Stabilointi voidaan suorittaa sek¨a synkronisissa ett¨a asynkronisissa j¨arjestelmiss¨a.
Synkronisissa j¨arjestelmiss¨a l¨ahetet¨a¨an globaali kellopulssi, jonka vastaanottaessaan jokainen prosessori suorittaa yhden askelen algoritmistaan. Asynkronisissa j¨arjestel- miss¨a prosessorit suorittavat algoritmejaan rinnakkain ja mahdollisesti eri nopeuksil- la. Synkronisissa j¨arjestelmiss¨a toimivat algoritmit voidaan muuntaa asynkronisissa j¨arjestelmiss¨a toimiviksi. T¨at¨a muunnosta kutsutaan synkronoinniksi.
Viestinv¨alitykseen ja jaettuun muistiin perustuvat hajautetut j¨arjestelm¨at eiv¨at olennaisesti eroa toisistaan, sill¨a jaetun muistin j¨arjestelmiss¨a toimivat algoritmit voidaan muuntaa viestinv¨alitysj¨arjestelmiss¨a toimiviksi. Stabiloinnin osalta voidaan siis yleisyytt¨a rajoittamatta tarkastella jompaakumpaa kommunikointimallia.
Hajautettujen j¨arjestelmien toipumiseen kuluvaa aikaa mitataan kierrosten ja syklien avulla. Kierros (round) on lyhin ajanjakso, jonka aikana jokainen proses- sori suorittaa v¨ahint¨a¨an yhden laskenta-askelen. Jokaisella prosessorilla oletetaan olevan algoritmi, joka on esitetty ikuisena silmukkana. Sykli (cycle) on lyhin ajan- jakso, jonka aikana jokainen prosessori suorittaa yhden kerran ikuisen silmukkansa sis¨all¨on.
Stabilointialgoritmit k¨aytt¨av¨at osateht¨avien suorittamiseen muita toipumiskykyisi¨a algoritmeja. Tarvittavia algoritmeja ovat esimerkiksi johtajan valinta ja viestika- navien muuntaminen luotettaviksi. Lis¨aksi k¨aytet¨a¨an tietoa siit¨a, ett¨a toipumisky- kyinen algoritmi voidaan muodostaa reilun koostamisen (fair composition) avulla osateht¨av¨at suorittavista toipumiskykyisist¨a algoritmeista.
Luvussa 2 esitell¨a¨an resynkroninen stabilointi, joka on yksinkertainen menetelm¨a kiinte¨an tulosteen algoritmien muuntamiseksi toipumiskykyisiksi. Toipumiskykyis- ten ja ei-toipumiskykyisten algoritmien v¨alill¨a ei siis ole periaatteellista eroa, sill¨a ei-toipumiskykyinen algoritmi voidaan muuntaa toipumiskykyiseksi resynkronisen stabiloinnin avulla.
Luvussa 3 esitet¨a¨an yleisempi menetelm¨a stabiloinnin suorittamiseen. Menetelm¨a perustuu tarkkailuun, jonka avulla havaitaan j¨arjestelm¨ass¨a esiintyv¨at virheet, ja alustukseen, jonka avulla j¨arjestelm¨a palautetaan sallittuun alkutilaan.
2 Resynkroninen stabilointi
Seuraavaksi tarkastellaan kiinteiden tulosteiden (fixed output) algoritmien muunta- mista toipumiskykyisiksi. Esimerkiksi minimaalisen viritt¨av¨an puun laskevan algo- ritmin tulosteena on verkon minimaalinen viritt¨av¨a puu, joten algoritmin tuloste on kiinte¨a. Toisaalta esimerkiksi keskin¨aisen poissulkemisen algoritmeilla ei ole kiinte-
¨a¨a tulostetta, vaan algoritmin oikeellinen toiminta on jatkuva prosessi, jossa jaettua resurssia k¨aytt¨a¨a vain yksi prosessori kerrallaan.
Resynkroninen stabilointi (resynchronous stabilizer) on yksinkertainen stabilointita- pa, jolla mik¨a tahansa hajautettuja sy¨otteit¨a k¨aytt¨av¨a kiinte¨an tulosteen algoritmi voidaan muuntaa toipumiskykyiseksi. Resynkronista stabilointia voidaan soveltaa sek¨a synkronisiin ett¨a asynkronisiin algoritmeihin.
Algoritmin synkronisella suoritusajalla tarkoitetaan sit¨a askelten m¨a¨ar¨a¨a, jossa synk- ronoidun j¨arjestelm¨an prosessorit saavat laskettua algoritmin tulosteen. Tarkastel- laan algoritmiaA, jonka suoritusaika synkronisessa j¨arjestelm¨ass¨a ont askelta. Tar- koituksena on m¨a¨aritell¨a algoritmi, joka toimii kuten A ja on toipumiskykyinen.
Tarkastellaan prosessorien tiloja, kun algoritmiaAsuoritetaan synkronisessa j¨arjes- telm¨ass¨a, jossa ei esiinny virheit¨a. Aluksi jokainen prosessori Pi on alkutilassa Ti,0. Ensimm¨aisen laskenta-askelen aikana jokainen prosessoriPi lukee naapureidensa al- kutilatTj,0ja laskee niiden ja oman alkutilansa perusteella uuden tilansaTi,1. Toisen laskenta-askelen aikana jokainen prosessori Pi lukee naapureidensa tilat Tj,1 ja las- kee niiden ja oman tilansa Ti,1 perusteella uuden tilansa Ti,2. Viimeist¨a¨an t askelen kuluttua prosessorit ovat saaneet laskettua halutun tulosteen.
Resynkronisen stabiloinnin perusajatus on tallentaa jokaisen prosessorin Pi yhtey- teen tieto tiloista Ti,0, Ti,1, . . . , Ti,t. Jokaisen prosessorin yhteyteen tallennetaan siis t+ 1 alkion taulukko, jonka soluihin n¨am¨a tilat tallentuvat. Aluksi taulukon sis¨al- t¨o voi olla mit¨a tahansa, mutta laskennan edetess¨a taulukon soluihin tallentuvat halutut tilat.
Resynkronisen stabiloinnin suoritus. Jokainen prosessoriPi laskee ikuisen sil- mukkansa suorituksen aikana uudelleen kaikki tilansaTi,0, Ti,1, . . . , Ti,t. Aluksi se tal- lentaa tilaan Ti,0 algoritminsa m¨a¨ar¨a¨am¨an alkutilan. Sen j¨alkeen se lukee naapurei- densa Pj tilataulukot Tj,0, Tj,1, . . . , Tj,t. Oman ja naapureiden 0-tilojen perusteella se laskee tilansa Ti,1, sen ja naapureiden 1-tilojen perusteella tilansa Ti,2 ja niin edelleen.
? ? ? ?
? ? ? ?
? ? ? ?
A ? ? ?
C ? ? ? B ? ? ?
A D ? ?
C ? ? ? B ? ? ?
Kuva 1: Kun virheet¨on jakso alkaa, prosessorit voivat olla mielivaltaisessa tilassa.
Ensimm¨aisen syklin j¨alkeen jokainen prosessori on alustanut alkutilansa (A, B ja C). Toisen syklin aikana jokainen prosessori saa laskettua toisen tilansa oikein, sill¨a tilan m¨a¨aritt¨amiseen tarvittavat sy¨otteet (t¨ass¨a A, B ja C) on tallennettu oikein.
Koska kaikki naapureiden tilat eiv¨at v¨altt¨am¨att¨a vastaa algoritminA virheett¨om¨as- s¨a suorituksessa esiintyvi¨a tiloja, ei prosessori itsek¨a¨an saa laskettua kaikkia omia tilojaan oikein. Kuitenkin, jos naapureiden tilat Tj,0, . . . , Tj,k ja prosessorin omat tilatTi,0, . . . , Ti,k on tallennettu oikein, saa prosessori laskettua tilansaTi,k+1 oikein.
J¨arjestelm¨an toipumiskyky. Kun virheet loppuvat, niin jossain vaiheessa jokai- nen prosessori Pi on suorittanut ikuisen silmukkansa sis¨all¨on v¨ahint¨a¨an kerran ja alustanut l¨aht¨otilanteen Ti,0 oikeaksi. T¨am¨an j¨alkeen jokainen prosessori Pi pystyy laskemaan oikein tilansa Ti,1, sill¨a tarvittavat sy¨otteet, prosessorin itsens¨a 0-tila ja muiden prosessorien 0-tilat, on laskettu oikein. Kun jokainen prosessori on laskenut oikein 1-tilansa, voivat kaikki prosessorit laskea oikein 2-tilansa. N¨ain edeten voidaan havaita, ett¨a jossain vaiheessa kaikki prosessorit saavat algoritminsa suoritettua lop- puun, ellei uusia virhetilanteita esiinny.
Olennaista on, ett¨a mik¨a¨an prosessori ei muuta kertaalleen oikein laskettuja tiloja, vaikka se laskeekin ne uudelleen. N¨ain ollen jokainen sykli lis¨a¨a ainakin yhden tilan oikein laskettujen tilojen joukkoon.
Kuva 1 havainnollistaa resynkronisen stabiloinnin toimintaa, kun hajautetun j¨arjes- telm¨an virheet¨on jakso alkaa.
Resynkronisen stabiloinnin ongelmia. Resynkroninen stabilointi tarvitsee ep¨ak¨ayt¨ann¨ollisen paljon muistia, sill¨a jokainen prosessori joutuu tallentamaan oman tilansa yht¨a monta kertaa kuin algoritmin suorittamiseen tarvitaan askelia. Lis¨aksi resynkroninen stabilointi ei sovellu satunnaisalgoritmien stabilointiin, koska satun- naisalgoritmeissa prosessorin seuraava tila ei m¨a¨ar¨aydy deterministisesti sen edelli- sen tilan ja naapurien tilojen avulla.
3 Yleinen stabilointi: j¨ arjestelm¨ an tarkkailu ja alustus
Resynkronisen stabiloinnin sijasta algoritmi voidaan muuntaa toipumiskykyiseksi k¨aytt¨aen yleist¨a stabilointia. Yleist¨a stabilointia voidaan soveltaa sek¨a kiinte¨an tu- losteen algoritmeihin ett¨a ei-kiinte¨an tulosteen algoritmeihin. T¨ass¨a luvussa tarkas- tellaan kiinte¨an tulosteen algoritmeja. Voidaan lis¨aksi yleisyytt¨a rajoittamatta tar- kastella hajautettuja j¨arjestelmi¨a, joissa prosessorien v¨alinen kommunikaatio perus- tuu viestinv¨alitykseen.
Yleisen stabiloinnin perusajatus on havaita j¨arjestelm¨ass¨a esiintyv¨at virheet (tark- kailu) ja palauttaa j¨arjestelm¨a sallittuun l¨aht¨otilanteeseen virheen tapahtuessa (alus- tus). Tarkkailun ja alustamisen yhteensovittaminen ei ole triviaalia: on esimerkiksi varmistettava, ett¨a virheen havaitsemisesta johtuva alustus suoritetaan loppuun en- nen uusien alustusten k¨aynnist¨amist¨a.
Luvussa 3.1 esitell¨a¨an virheidenhavaitsemisalgoritmi ja luvussa 3.2 kuvataan algo- ritmi, joka alustaa j¨arjestelm¨an eli palauttaa sen sallittuun alkutilaan. Luvussa 3.3 esitet¨a¨an lyhyt perustelu j¨arjestelm¨an toipumiskyvyst¨a.
3.1 Virheiden havaitseminen
Useissa toipumiskykyisiss¨a algoritmeissa ei pyrit¨a eksplisiittisesti havaitsemaan vir- heit¨a, vaan ohjataan j¨arjestelm¨a¨a jatkuvasti kohti sallittua tilaa. Prosessorit eiv¨at yleens¨a pid¨a yll¨a tietoa siit¨a, onko j¨arjestelm¨a kulloinkin sallitussa tilassa vai ei.
T¨ast¨a l¨ahestymistavasta poiketen tarkkailu ja alustus -stabiloinnissa on m¨a¨aritelt¨a- v¨a keino havaita, onko virheit¨a tapahtunut.
Er¨as keino havaita virheiden havaitsemiseen on tallentaa kuva j¨arjestelm¨an hetkelli- sest¨a kokonaistilanteesta ja tarkastaa sen avulla, onko j¨arjestelm¨a sallitussa tilassa.
Kuvan ottaminen ei keskeyt¨a varsinaista laskentaa, vaan suoritetaan sen lomassa.
Tilannekuva-algoritmi. Oletetaan, ett¨a toipumiskykyisen johtajanvalinta- algoritmin avulla jokin prosessori on valittu johtajaksi. Kuvanottoalgoritmissa jokainen prosessori tallentaa muistiinsa kopion tilastaan ja saamistaan viesteist¨a.
Sen j¨alkeen johtaja ker¨a¨a tiedot prosessoreilta.
Kuvanottoalgoritmissa oletetaan, ett¨a viestikanavat ovat luotettavia. T¨am¨a voidaan saada aikaan toipumiskykyisell¨a algoritmilla, jolla jaetun muistin j¨arjestelmiss¨a toi- mivat algoritmit muunnetaan viestinv¨alityst¨a k¨aytt¨aviksi. Lis¨aksi kuvanottoalgo- ritmi k¨aytt¨a¨a luvussa 3.2 kuvattavaa alustusalgoritmia tarvitsemiensa muuttujien alustamiseen.
Kuvan tallentava algoritmi on seuraava:
1. Johtaja tallentaa oman tilansa ja alkaa l¨ahett¨a¨a merkki¨a toistuvasti jokaiselle naapurilleen.
2. Kun prosessori Pi saa merkin ensimm¨aisen kerran, se tallentaa muistiinsa ko- pion nykyisest¨a tilastaan ja l¨ahett¨a¨a merkin jokaiselle naapurilleen.
3. Jos prosessoriPisaa viestin prosessoriltaPk, se tallentaa kopion viestist¨a muis- tiinsa. Kun prosessori Pi saa merkin prosessorilta Pk, prosessori Pi lopettaa saapuvien viestien tallentamisen.
4. Kun prosessori Pi on saanut merkin jokaiselta naapuriltaan, se l¨ahett¨a¨a tal- lentamansa tiedot johtajalle.
Vaikka prosessorin Pi tila tallennetaan eri ajanhetkell¨a kuin sen naapuriprosesso- rin Pj tila, saa viestien tallentaminen aikaan sen, ett¨a kokonaiskuva j¨arjestelm¨an tilasta on yhten¨ainen. Jos prosessorin Pi tila tallennetaan ensin ajanhetkell¨a t1 ja prosessorin Pj tila my¨ohemmin ajanhetkell¨a t2, tallentaa prosessori Pi muistiinsa prosessoriltaPj tulevat viestit, jotka saapuvat ajanhetkient1 jat2 v¨alill¨a. Kokonais- kuvaan kuuluu prosessorin Pi tila ajanhetkell¨a t1, prosessorin Pj tila ajanhetkell¨a t2 sek¨a prosessorinPi tallentamat viestit. Kokonaiskuva voidaan tulkita tilanteeksi, jossa molempien prosessorien tilat on tallennettu ajanhetkell¨a t2 eik¨a prosessori Pi ole saanut suoritusvuoroa ajanhetkien t1 ja t2 v¨alill¨a. Tallennettujen viestien voi- daan ajatella olevan matkalla viestikanavassa, jolloin prosessori Pi ole viel¨a ehtinyt saada niit¨a. Todellisuudessa prosessoriPi on voinut muuttaa tilaansa ajanhetkient1
ja t2 v¨alill¨a ja se on my¨os saanut tallentamansa viestit.
Saatuaan kuvanottoalgoritmin tallentamat tiedot kaikilta prosessoreilta johtaja muodostaa kokonaiskuvan j¨arjestelm¨ast¨a ja tarkastaa, onko j¨arjestelm¨a sallitussa tilassa vai ei. Se, miten tarkastus suoritetaan, riippuu stabiloitavasta algoritmista.
Kiinte¨an tulosteen algoritmeja stabiloitaessa on pystytt¨av¨a erottamaan virhetilan- ne j¨arjestelm¨an normaalista toiminnasta, jossa halutun tuloksen laskenta on viel¨a kesken.
Joissain tilanteissa kuvanottoalgoritmi voidaan korvata versiolla, jossa j¨arjestelm¨an tila tallennetaan useisiin paikallisiin tilannekuviin. T¨all¨oin stabiloitavan algoritmin on oltava sellainen, ett¨a virheet voidaan havaita paikallisista tilannekuvista.
Esimerkki virheiden havaitsemisesta. Tarkastellaan esimerkkin¨a seuraavaa al- goritmia, joka laskee prosessorien et¨aisyydet tiettyyn kohdeprosessoriin. Jokaisella prosessorillaPi on muuttujadi, johon se tallentaa nykyisen k¨asityksen et¨aisyydest¨a.
Algoritmi on kuvattu taulukossa 1.
Kohdeprosessori P0
Alustus: aseta d0 = 0
L¨ahet¨a jokaiselle naapurille tietod0:sta Muut prosessorit Pi
Alustus: aseta di =∞
Kun saat naapurilta Pj arvon dj:
Josdj+ 1 < di, aseta di =dj+ 1 ja l¨ahet¨a jokaiselle muulle naapurille tietodi:st¨a Muutoin ¨al¨a tee mit¨a¨an
Taulukko 1: Algoritmi, jolla prosessorit laskevat oman et¨aisyytens¨a kohdeprosesso- rista. Algoritmi ei ole toipumiskykyinen.
T¨am¨a algoritmi ei ole toipumiskykyinen. Esimerkiksi jos jonkin prosessorinPj muut- tujaan dj tallentuu virheen johdosta arvo 0, vaikkei Pj ole kohdeprosessori, niin al- goritmi ei saa sit¨a korjatuksi.
Esitetty et¨aisyyksienlaskenta-algoritmi voidaan kuitenkin stabiloida eli muuntaa toi- pumiskykyiseksi. Sit¨a varten on muodostettava menetelm¨a, jolla virheet havaitaan j¨arjestelm¨an tilannekuvasta.
Johtajaprosessorin saamassa tilannekuvassa on tieto arvoista, jotka on tallennettu muuttujiind. J¨arjestelm¨an normaalissa toiminnassa prosessorinPi arvodi on yleen- s¨a yht¨a suurempi kuin pienin naapuriprosessorien arvoista. Muissa tapauksissa pro-
d = 0
d = Inf
d = Inf d = Inf
d = 0
d = 1
d = Inf d = 1
d = 0
d = 1
d = 2 d = 1
Kuva 2: Esimerkki et¨aisyydet laskevan algoritmin oikeasta suorituksesta.
d = 0
d = 3
d = Inf d = Inf
d = 0
d = 1
d = Inf d = 1
d = 0
d = 0
d = 2 d = 1
Kuva 3: Esimerkkej¨a virhetilanteista eli tilanteista, jotka eiv¨at voi esiinty¨a et¨aisyydet laskevan algoritmin normaalin suorituksen aikana.
sessori Pi ei ole viel¨a ehtinyt saada viesti¨a silt¨a naapurilta, jolta pienempi d-arvo periytyisi. Johtajaprosessori voi siis prosessorien d-muuttujista ja viestikanavien si- s¨all¨oist¨a p¨a¨atell¨a, onko j¨arjestelm¨a sallitussa tilassa vai ei.
Sen sijaan virhetilanteeksi ei pid¨a tulkita tilannetta, jossa jonkin prosessorin d-arvo ei vastaa prosessorin et¨aisyytt¨a kohdeprosessorista. T¨allainen tilanne kuuluu j¨arjes- telm¨an normaaliin toimintaan silloin, kun et¨aisyyksien laskenta on viel¨a kesken.
Kuvassa 2 on esimerkki et¨aisyydenlaskemisalgoritmin oikeasta suorituksesta ja ku- vassa 3 on esimerkkej¨a virhetilanteista, jotka eiv¨at voi esiinty¨a j¨arjestelm¨an oikean suorituksen aikana. Virhetilanteet voidaan erottaa normaaliin suoritukseen kuulu- vista tilanteista tarkastelemalla solmujen tiloja ja viestikanavien sis¨alt¨oj¨a.
Virheet voidaan havaita esimerkiksi tarkastamalla seuraava ehto:
Algoritmin tila on sallittu, jos
• kohdesolmulleP0 p¨ateed0 = 0 ja muille solmuille Pi p¨atee di >0 ja
• jokaisella kohdesolmusta eroavalla solmullaPi on naapuri Pj, jolle p¨ateedi = dj+ 1 tai matkalla on arvon dj sis¨alt¨av¨a viesti naapurilta Pj naapurille Pi.
3.2 J¨ arjestelm¨ an alustus
J¨arjestelm¨an alustus suoritetaan, kun virheenhavaitsemisalgoritmi ilmoittaa, ettei j¨arjestelm¨a ole sallitussa tilassa. Alustuksen teht¨av¨an¨a on palauttaa j¨arjestelm¨a sal- littuun alkutilaan.
Seuraavaksi esitet¨a¨an alustusalgoritmi, jossa mik¨a tahansa prosessori voi virheen havaitessaan pyyt¨a¨a j¨arjestelm¨an alustusta. Algoritmi k¨aytt¨a¨a johtajanvalinta-algoritmia ja β-synkroinoija-algoritmia osateht¨avien suoritta- miseen. Johtajanvalinta-algoritmi muodostaa viritt¨av¨an puun, jonka juurena oleva prosessori on nimetty johtajaksi.β-synkronoija v¨aritt¨a¨a puun toistuvasti siten, ett¨a juuri valitsee uuden v¨arin, joka ”valuu” puussa alasp¨ain kunnes koko puu on saman v¨arinen. Sen j¨alkeen juuri valitsee seuraavan v¨arin ja sama prosessi toistuu.
Kun j¨arjestelm¨a ei ole sallitussa tilassa, virheidenhavaitsemisalgoritmi takaa, ett¨a ainakin yksi prosessori havaitsee virheen. Seuraavaksi kuvattava alustusalgoritmi saa aikaan j¨arjestelm¨an alustuksen silloin, kun jokin prosessoreista havaitsee virheen.
Alustusalgoritmin runkona on puun toistuvan v¨arityksen suorittava algoritmi. Alus- tusalgoritmin toiminnot, kuten virheist¨a raportointi ja oman tilan alustus, lomittu- vat puun toistuvaan v¨aritykseen.
Puun toistuva v¨aritys. Jokaisella prosessorilla on tieto siit¨a, mitk¨a prosessorit ovat sen lapsia ja mik¨a prosessori on sen vanhempi. Lis¨aksi prosessorillaPi on tieto omasta v¨arist¨a¨an colori. V¨ari on kokonaisluku joukosta {0, . . . ,5n−4}, jossa n on prosessoreiden m¨a¨ar¨a1.
Prosessorien v¨alisen kommunikoinnin mallina k¨aytet¨a¨an jaettua muistia. Prosesso- rin Pi ja sen vanhemman Pj v¨aliseen kommunikointikanavaan liittyy kaksi muut- tujaa: colorj,i, jolla vanhempi kertoo lapselleen v¨arins¨a ja colori,j, jolla lapsi kertoo vanhemmalleen alipuunsa v¨arin.
1L¨ahdeteoksessa esitetyss¨a algoritmissa v¨ari¨a kasvatetaan modulo 5n−3, jolloin suurin mah- dollinen v¨ari on 5n−4 eik¨a 5n−2.
2
1 1
1 1 1
2
2 2
1 1 1
Kuva 4: Kun juuri on valinnut uuden v¨arin, se kertoo sen lapsilleen, jotka vaihtavat v¨arins¨a ja kertovat uuden v¨arin omille lapsilleen.
Juurena toimiva prosessori suorittaa seuraavaa algoritmia: Jos kaikki lapset ilmoit- tavat, ett¨a niiden alipuut ovat saman v¨arisi¨a kuin juuri, niin juuri kasvattaa omaa v¨ari¨a¨an. Joka tapauksessa juuri kertoo lapsille oman v¨arins¨a.
Muut prosessorit suorittavat seuraavaa algoritmia: Jos vanhempi on kertonut pro- sessorille jonkun muun v¨arin kuin prosessorin nykyisen v¨arin, niin prosessori vaihtaa oman v¨arins¨a vanhemman v¨ariksi. Jos kaikki lapset ilmoittavat, ett¨a niiden alipuut ovat saman v¨arisi¨a kuin prosessori itse, niin prosessori ilmoittaa t¨am¨a alipuun v¨arin vanhemmalleen. Joka tapauksessa prosessori kertoo lapsille oman v¨arins¨a.
T¨am¨an algoritmin seurauksena juuren valitsema v¨ari valuu puussa alas. Kun koko puu on saman v¨arinen, tieto siit¨a v¨alittyy puussa yl¨osp¨ain juureen asti. T¨am¨an seurauksena juuri valitsee uuden v¨arin ja sama prosessi toistuu.
Kuva 4 havainnollistaa v¨arin valumista alas puussa. Jokainen solmu kertoo lapsilleen oman v¨arins¨a. Kuva 5 havainnollistaa, miten tieto v¨arityksen loppuunsaattamisesta etenee puussa yl¨osp¨ain.
Synkronointi voidaan saada aikaan hy¨odynt¨am¨all¨a puun toistuva v¨aritys -algoritmia antamalla jokaisen prosessorin suorittaa yksi laskenta-askel silloin, kun se vaihtaa omaa v¨ari¨a¨an. T¨allaista synkronointialgoritmia kutsutaan β-synkronoinniksi. Ylei- sess¨a stabiloinnissa puun toistuva v¨aritys -algoritmia ei kuitenkaan k¨aytet¨a synkro- nointiin vaan alustuksen suorittamiseen.
2
2 2
2 2 2
2
2 2
2 2 2
Kuva 5: Kun koko puu on v¨aritetty, lehtisolmut kertovat vanhemmilleen, ett¨a niiden alipuut on v¨aritetty niiden omalla v¨arill¨a. Lehtisolmujen vanhemmat huomaavat, ett¨a my¨os niiden alipuut on v¨aritetty niiden omalla v¨arill¨a ja v¨alitt¨av¨at t¨am¨an viestin edelleen vanhemmilleen.
Alustusalgoritmin toiminta. Puun toistuva v¨aritys -algoritmin tarvitsemien muuttujien lis¨aksi alustusalgoritmi tarvitsee seuraavat muuttujat: jokaisella proses- sorilla Pi on alustusta varten kaksi bin¨a¨arimuuttujaa: invokei ja reseti. Muuttuja invokei saa arvon true, jos prosessori Pi on havainnut virheen. Muuttuja reseti saa arvon true, jos prosessori Pi tiet¨a¨a, ett¨a alustus on parhaillaan k¨aynniss¨a.
Prosessorin Pi ja sen vanhemman Pj v¨aliseen kommunikointikanavaan liittyy kaksi lis¨amuuttujaa: resetj,i, jolla vanhempi v¨alitt¨a¨a lapselleen tiedon k¨aynniss¨a olevasta alustuksesta ja requesti,j, jolla lapsi v¨alitt¨a¨a vanhemmalleen tiedon alustuspyynn¨os- t¨a.
Alustusalgoritmi on erilainen juurena toimivalle prosessorille ja muille prosessoreille.
Jos alustusta ei ole k¨aynniss¨a, jokainen prosessori suorittaa virheentarkastusalgorit- min juuri ennen kuin se raportoi vanhemmalleen, ett¨a sen koko alipuu on v¨aritetty nykyisell¨a v¨arill¨a2.
Jos prosessori Pi havaitsee virheen, se kirjoittaa muuttujaansa invokei arvon true. Kun virheen havainnut prosessori kertoo vanhemmalle oman alipuunsa olevan itsens¨a v¨arinen, se v¨alitt¨a¨a samalla vanhemmalleen pyynn¨on k¨aynnist¨a¨a j¨arjestelm¨an alustus kirjoittamalla vanhempansa kommunikointikanavan request-muuttujaan arvontrue.
Kun vanhempi huomaa t¨am¨an alustuspyynn¨on, se v¨alitt¨a¨a sen vastaavasti omalle vanhemmalleen samalla kun se raportoi oman alipuunsa olevan itsens¨a v¨arinen. N¨ain
2L¨ahdeteoksessa esitetyss¨a algoritmissa juuriprosessori ei koskaan suorita virheidenhavaitsemi- salgoritmia; t¨am¨a t¨aytynee lis¨at¨a algoritmiin.
alustuspyynt¨o etenee puussa yl¨osp¨ain.
Lopulta alustuspyynt¨o saapuu juuriprosessorille, joka k¨aynnist¨a¨a j¨arjestelm¨an alus- tuksen. Kun juuri seuraavan kerran vaihtaa v¨arins¨a, se alustaa oman tilansa ja v¨a- litt¨a¨a lapsilleen tiedon uudesta v¨arist¨a ja k¨aynniss¨a olevasta alustuksesta. Aina, kun prosessori vaihtaa oman v¨arins¨a vanhemman v¨ariksi, se alustaa oman tilansa ja kirjoittaa invoke-muuttujaansa arvon false. Kun prosessori kertoo oman v¨arins¨a lapsilleen, se v¨alitt¨a¨a my¨os tiedon k¨aynniss¨a olevasta alustuksesta.
Kun uusi v¨ari ja sen kanssa v¨alitett¨av¨a tieto alustuksesta on edennyt puussa juu- resta lehtisolmuihin, jokainen prosessori on alustanut tilansa. Sen j¨alkeen tieto siit¨a, ett¨a puu on v¨aritetty loppuun, alkaa kulkea puussa yl¨osp¨ain. T¨all¨a kertaa mik¨a¨an prosessori ei suorita virheentarkastusta, sill¨a j¨arjestelm¨an alustus on k¨aynniss¨a.
Kun tieto v¨arityksen saattamisesta loppuun kulkeutuu puussa yl¨osp¨ain, jokainen prosessori v¨alitt¨a¨a vanhemmalleen tiedon siit¨a, ettei uutta alustusta pyydet¨a, eli kir- joittaa vanhempansa kommunikointikanavan request-muuttujaan arvon false. Kun t¨am¨a tieto v¨alittyy juureen asti, juuri kirjoittaa muuttujaansa reset arvonfalse. Kun juuri seuraavan kerran valitsee uuden v¨arin, sen lapset kopioivat arvon false omiin reset-muuttujiinsa. Uuden v¨arin valuessa alas puussa jokainen prosessori huomaa, ettei j¨arjestelm¨an alustus ole k¨aynniss¨a, eik¨a t¨all¨a kertaa alusta omaa tilaansa.
Alustusalgoritmin oikeellisuus. Esitetty alustusalgoritmi takaa sen, ettei uusia virheentarkastuksia k¨aynnistet¨a, kun j¨arjestelm¨an alustus on k¨aynniss¨a. Vasta kun kaikki prosessorit ovat alustaneet oman tilansa, voidaan virheentarkastusalgoritmi suorittaa uudelleen.
Alustusalgoritmin oikea toiminta edellytt¨a¨a viritt¨av¨an puun muodostamista ja puun toistuva v¨aritys -algoritmin oikeaa toimintaa. Viritt¨av¨a puu voidaan muodostaa toi- pumiskykyisell¨a johtajan valita-algoritmilla ja my¨os puun toistuva v¨aritys -algoritmi on toipumiskykyinen.
Kun j¨arjestelm¨an virheet loppuvat, voi viritt¨av¨an puun muodostavan algoritmin toi- puminen alkaa. Kun se on toipunut virheist¨a, alkaa puun toistuva v¨aritys -algoritmin toipuminen. Senkin toivuttua alustusalgoritmi voi olla mielivaltaisessa tilassa. Jon- kin prosessorin invoke-muuttujassa voi esimerkiksi olla arvo true, vaikkei j¨arjestel- m¨a¨a tarvitsisi alustaa. Alustusalgoritmi toipuu kuitenkin n¨aist¨a virhetilanteista, sill¨a vaikka se aluksi suorittaisikin turhia alustuksia, niin viimeist¨a¨an kahden seuraavan puussa valuvan v¨arin my¨ot¨a prosessorien invoke- ja reset-muuttujien arvot korja- taan. Sen j¨alkeen alustusalgoritmi alkaa toimia oikein.
Stabilointi
Virheiden
tarkkailu Alustus
Kuvanotto
Johtajan valinta
Toistuva väritys
Puun muodostus Viestikanavat
luotettaviksi
Muuttujien alustus
Kuva 6: Stabilointialgoritmin jakautuminen osateht¨aviin.
3.3 J¨ arjestelm¨ an toipumiskyky
J¨arjestelm¨ass¨a esiintyv¨at virheet voivat vaikuttaa my¨os virheenhavaitsemisalgorit- min ja alustusalgoritmin toimintaan. J¨arjestelm¨ass¨a esiintyv¨an virheen johdosta vir- heidenhavaitsemisalgoritmi voi toimia v¨a¨arin, eli ilmoittaa olemattomasta virheest¨a tai j¨att¨a¨a virheen havaitsematta. Riitt¨a¨a kuitenkin, ett¨a virheidenhavaitsemisalgo- ritmi ei ilmoita virheist¨a silloin, kun sek¨a virheidenhavaitsemisalgoritmi ett¨a tark- kailtava algoritmi ovat sallitussa tilassa.
Tarkastellaan j¨arjestelm¨an toimintaa silloin, kun virheet loppuvat ja j¨arjestelm¨an toi- puminen voi alkaa. Aluksi j¨arjestelm¨a voi olla mielivaltaisessa tilassa. Jonkin ajan kuluttua osateht¨avi¨a suorittavat toipumiskykyiset algoritmit, kuten viritt¨av¨an puun muodostava algoritmi ja kommunikointikanavat luotettavaksi tekev¨a algoritmi, ovat p¨a¨atyneet sallittuun tilaan. Niiden toivuttua virheist¨a alkavat virheidentarkkailual- goritmi ja alustusalgoritmi toimia edell¨a kuvatulla tavalla.
Kuva 6 havainnollistaa stabilointialgoritmin osateht¨avi¨a. Jokaisessa solmussa oleva algoritmi voi toipua virheist¨a kun sen lapsisolmuina kuvatut osateht¨avi¨a suorittavat algoritmit ovat p¨a¨atyneet sallittuun tilaan.
Virheidentarkkailualgoritmin ja alustusalgoritmin toivuttua virheist¨a voi varsinainen tarkkailtava algoritmi olla sallitussa tai ei-sallitussa tilassa. Jos algoritmi on sallitus- sa tilassa, virheidentarkkailualgoritmi toimii oikein eik¨a havaitse virhett¨a, ja sallittu
suoritus voi jatkua. Jos algoritmi ei ole sallitussa tilassa, virheidentarkkailualgorit- mi toimii oikein ja havaitsee virheen, jolloin alustusalgoritmi palauttaa j¨arjestelm¨an sallittuun tilaan. Sen j¨alkeen virheidenhavaitsemisalgoritmi ei en¨a¨a ilmoita virheist¨a eik¨a uusia alustuksia suoriteta. Jos uusia virheit¨a ei tapahdu, varsinaisen algoritmin suoritus jatkuu sallitusti.
4 L¨ ahteet
Shlomi Dolev: Self-Stabilization, luku 5. MIT Press 2000.
