SINHRONIZACIJA V PORAZDELJENIH RAČUNALNIŠKIH SISTEMIH INFORMATICA 2/88 UDK 681.3.02 Jože Rugelj Institut »Jožef Stefan« Sinhron1zac1jski mehanlzmi v porazde1]enih računa1niških sistemih so potrebni za definicijo in reallzacljo urejenosti dogodkov v računalnIškem sistemu. Clanek podaja pregled mehanizmov za sinhronizacijo na ra.zličnih nivojih abstrakcije računa1niškega sistema. Synchron i zat i on the reallzatlon mechan i sms, used mechanisms in distributed computing systems are necessary for the definition and of event ordering in the computing system. Thiš article gives an overview of on different levels of abstraction. 1. UVOD Porazdeljen računalnlški slstem je množlca procesnlh elementov. Vsak procesni element lma lasten pomnilnik in procesne zmoglJ1vosti. V procesnih elementih se izvajajo procesi. Z oznako porazdeljenost Je mišljena porazdelitev nadzora ln ne nujno tudi prostorska porazde 1Jenost . V tesno sklopljenlh slstemlh so procesi povezanl med seboj s skupnim potnn i 1 n i kora, v Sibko sklopljenih sistemih pa so procesna mesta povezana s komunlkacijskiml kanali, ki skupaj tvorijo komunikacljsko tnrežo. Skupnega pomnllnlka v takih sIstemih nl. V tem prlmeru gre tudi za prostorsko porazdelltev procesnlli elementov, ki jim zaradl tega reCemo tudl procesna mesta. Procesne elemente združuje v porazdeljen slstem porazdeljen operacljskl slstem. Glavne naloge porazde1jenega operacijskega slstema so podpora medprocesne komunikacIje, dodeljevnje vlrov In upravljanje z njlml, upravljanje z imenl ter reševanje iz napak. Jedra porazde1jenega operacljskega sistema na posameznlh mestih so lahko imp1ementirana kot jedra osnovnega operacIjskega sistema na tem mestu ali kot procesl na uporabniškem nivoju /Trip87/. V sistemih z večlmi procesnimi elementi se procesl izvajajo sočasno, dokler ne potrebujejo medsebojnlh stikov. Načrtovane in vodene stike med procesf imenujemo procesna komunlkacija ln sinhron 1 zacija . Procesl morajo sodelovati zaradl omejevanja sofiasnostl ln zaradl medsebojnega razvrščanja /Verj83/. Odnose med procest bi glede na načln sodelovanja lahko razdellli v dve glavni kategoriji: lahko tekmujejo med seboj ali so v odnosu prolzvajalec-potrošnik /Hwan85/. 2. KONSISTENTNOST IN NEDELJIVOST Predpostavljarao, da se procesi lzvajajo v diskretnlh koraklh ln . na vsakem koraku generlrajo dogodek. Dogodek je lahko lokalen procesu in ga drugl procesl j e v i den vsem i n slnhronizaclje. ne opazljo ali pa vsebuje problem Na vsakein nlvoju abstrakclje lahko proces, ki se lzvaja na nekem procesnem mestu, sprožl operacije. Operacija na nivoju j je imp1ement1rana kot množica aktivnostl na nivoju i, pri čemer velja i < j. Kar vidimo z nivoja j kot aktlvnost Je definirano na nivoju i kot operacija. Tak model velja rekurzivno za vse nlvoje. Operacije oziroma aktivnosti vodijo in upravljajo vlre. Vlrl so predstav1jen1 kot podatkovni objekti. Na primer, periferna naprava je lahko predstav1Jena s svojlm trenutnim stanjem, kl je doloCeno z vrednostml množlce par.amet ro v. Zapls na datoteki lahko predstavimo z njegovo vsebino. Prlmerl aktivnosti, ki delajo s podatkovnimi objekti, so plsanje, branje, krelranje in b r1s an j e . Podatkovnl objekti lmajo med seboj semantične povezave, to pomeni, da morajo njihove vrednosti zadoščatl nekim omejitvam. Ko objekt kreiramo, brlšemo ali vanj plšemo, je pogosto potrebno kreirati, brisati ali pisati še v druge objekte, da bi. zadostili konsistenčnIm omejitvam /LeLa81/. Vsaka operacija je deflnirana tako, da predpostavlja na vhodu mnozlco objektov s kons1stentnimi vrednostmi in zagotavlja kot rezultat množico novih vrednosti, ki so tudi konslstentne. Torej, če so konslstentna statija, kl se prenašajo med procesi ali so shranjena, J e tudl procesiranje konsistentno. Če ni posebnih predpostavk, lahko ohranimo konsistentnost samo z zagotav]janjem nedeljlvostl operacij. Z definiranjem nekaterih druglh zahtev 1ahko zahtevo za nedeljivost opustimo. Definlrajmo nedel j ivost operacije. Operacija je nedeljiva, če zadošča naslednjima pogojema: al 1 al i se Izvedejo vse aktivnosti popolnoma pa se ne izvede nobena in 2. vmesna stanja pri izvajanju operaclje 108 niso vidna nobeni drugl operaciji. Nedeljivost Je dobro poznan koncept /Lmps81/. Oblčajne nedelj ive na en i s1s temlh operac i j i procesnih povezav. operac i J v cent ral Ins t rukc 1 j e na ker se 1zvaj aJo procesnl enot I . se ak11 vnos 11 , kI 1ahko i zvajaj o enotah Zato zahteva 1z1rant h raCuna 1 nIku 80 strogo zaporedno V porazdeljenlti prlpadajo dani na raz1 I čn I h brez določenlh Casovnih imp1ementac1ja nedeljlvih speclflčne mehanizme, ki Jlh slstemlh ne potrebujemo. Začetek Izvajanja operacije sele po lzvršltvi preJSnJe operacije vodi k posebnl vrsti dodeljevanja imenovanega zaporedno dodeljevanje (serlal schedullng). V porazdeljenih sistemih pa je Izključna uporaba zaporednega dodeljevanja zelo neuCInkovita. Ce aktlvnosti, ki jth sprozl dana mnozica operaclj, delujejo nad različnimi objektl, vzporedno lzvajanje aktivnostl nl le mozno, ampak celo prIporoč1jivo. Se več, če so aktivnosti, ki delujejo nad danlm objektom in prlpadajo različnim operacljam, sprožene sočasno in postavljene v čakalno vrsto procesriega elementa, ki vsebuje objekt, Je nelzkorišCen čas med dvema zaporednima akttnostima krajšl kot v primeru, fie je naenkrat sprožena samo ena akt i vnos t . ToreJ je zaželjeno, da dovoljujemo prepletanje aktlvnosti (1nter1eavlng) , kollkor je to mogoče, in s tem optlmiziramo zmoglJ1vosti. OdgovarJaJoča dodeljevanja Iroenujemo dodeljevanja s prepletanjem tn nekatera od njih so ekvlva1entna zaporednlm, torej so kons1stentna . Toda v splošnem to ne velja. Ce torej želimo čira veejo paralelnost ln s tem vellko hitrost in dobro Izkorišienost vlrov moramo polskati ustrezno prepletanje, kl ohranja kons 1 stentnost . S sinhron1zacIJskiml mehanlzml pa lahko reallzlramo potrebne odnose med procesi oz. operac i J amt. 3. RAZVRSCANJE D0G0DK0V Določanje, kateri dogodek se je zgodll prej, je običajno Intultlvno zasnovano na razmlšljanju v fizlkalnem Casovnem svetu. Tak prlstop predpostavl]a. da lahko definiramo nek unlverzalen čas, kl je dosegljlv z razllčnih lokacij v sistemu. Vemo pa, da taka resitev ne obstaja. V praksl 1ahko dobimo priblizke univerza1nega časa z dano natančnostJo. Vendar pa ni potrebno ali pa nl mogoče izrazlti slstemsklh speclflkaclj s fizikalnim časom /Kope87/. Obstaja določena kronoloSka urejenost dogodkov v ststemu, ker procesl, kl generirajo te dogodke, spoštujejo speclfična pravila (algorltme, protokole), ki Izražajo relatlvno urejenost v množici dogodkov opazovanega slstema. Taka urejenost dovoljuje procesom, ki opazujejo dogodke, da pravilno imp1ementirajo sistemske aktivnostl. Glede na naravo teh aktlvnostl Je potrebna delna alt popolna urejenost dogodkov. De 1 no ure j enos t , označeno z " --> " (beri "se zgodl pred") lahko definlramo nad katerokoli množico dogodkov, kl jlh generirajo procesl, ki lzmenjujejo sporočila /Lamp78/. Za relacijo "se zgodl pred" velja: če s t a procesa a --> b a in b akttvnosti Istega istega ln se a zgodi pred b, potem Je če je a aktlvnost za poSlIjanje sporočila iz enega procesa In Je b aktlvnost, ki sprejme to sporofiilo v drugem procesu, ve I j a a --> b 3 . če j e a a --> c In b —> c, potem velja Ce procesi komuniciraJo med seboj z izmenjavanjem sporoCll, 1ahko razvrstItImo nekatere dogodke, kl se zgodijo v razllCnih procesih. Urejenost " --> " je samo delna. Npr. če imamo dogodka a in b in velja a --> b in b --> a, potem je nemogoče rečl, kateri od dogodkov se je zgodil prej. Za take dogodke reCemo, da so sočasni (concurrent ) . V sploSnem dogodkov lz procesov, ki med seboj ne komuniciraJo, ne moremo razvrstiti. V odvisnosti od omejitev, kl jlh moramo upoštevatl, Je to dopustno all pa tudi ne. Eden od načlnov za dosego popolne urejenostl, le-ta nujna, Je pridobltev popolne iz delne z definicijo popolne kadar j e ureJ enos t i urej enos t 1 nad množico procesov. Omcn1t i moramo računa1n i sklh zakasnltev enoprocesorsklh do1ofiImo Cas, za 1zvr š i tev splošnem operacijskl sisteml na osnovl taklh podatkov. Se enega od osnovnlh problemov slstemov, to je problem prl procesiranJu . V slstemih lahko zelo natanfino kl ga procesna enota potrebuje danega ukaza. Seveda pa v n i so zasnovani man j pa b i b11a taka zasnova upravlčena za porazdeljene operacijske sisteme, saj zakasnitve vključujejo Se čas, kl je potreben za prenos podatkov ln ukazov med posamezniml procesnlmi enotamt po koraunIkac1Jski mrezl. V porazde1jenih sistemlh, kjer se operaclje Izvajajo na razllčnlh procesnlh enotah, spremlnjanje zakasnitev v komunikacIjskem podststemu lahko zmoti določeno urejenost dogodkov, ki jo prIčakuJemo. To se lahko zgodl celo v slstemlh, kjer so zakasnltve stalne. Zato moramo uporabljatl doloCone s 1 nliron i zac i j ske mehanizme prl proceslh, kjer se dogodki zgodijo in pri procesih, ki opazujejo te dogodke. Namen s1nhronizac1jskIh mehanizmov Je deflnlranje in realizacija razvrstltve poljubne množlce dogodkov. Natančneje, rekli bomo, da je s 1 nhronizacija načln za definicijo in reallzacljo delne all popolne urejenostl nad neko mnozlco dogodkov. Slnhronizacijskih mehanizmi nudijo procesom prlpomoCke, s katerimi se slstem oliranja v konsistentnem stanju. Stanje računalniškeca slstema je konsistentno , Ce v vsakem trenutku ustreza nekim zunanjim določllom. SPLOSNE MEHANIZMOV ZNACILNOSTI SINHRONIZACIJSKIH S 1 nhron i zac1j sk i opazovan j u 1n s i n h r o n 1 z a c i j s k i sklopljenih si pomn i1n i ku, v so na nekat er 1 h Zahteve za s p remen1j1vk prenašej o kot rar ež 1 . mehanlzmi temeljijo na sprerainJanju določenih skupnlh h spremen1j1vk. V tesno stemlh so le-te v skupnem šibko sklopljenlh sistemih pa ali na vseh procesnih mestih. branje ali spreminjanje In njihove vrednosti se sporočila po komunikacijski 109 Pri porazde1jenih reSitvah so s1nhron1zac1jske spremenlj1vke podvojene, razcepljene ali porazdeljene med mesta v s i s temu. Pod vo j enos t a 1 1 ce 1 o pomno zenos 1. spremenIJ1vke pomeni, da so verzije lste spremen1jivke v vseh all vsaj v večih mestlh v s1stemu. Ustrezen mehanlzem poskrbl za delno ali popolno kons I stentnost v vsakem t renutku . Razcep1]enost spremen1]1vk je razdelitev vrednostl spremen1j1vke na veC komponent. Komponente so porazdeljene po mest.ih, kjer se spreminja njihova vrednost. Prava vrednost spremen1jivke je linearna kombinacIJa vrednostl njenih komponent. Porazdelltev spremen1j. 1vk pa je rešitev, pri kateri so s 1 nhronizac1jske spremen1j1vke porazdeljene po razllčnih mestih v sistemu, vendar samo po ena verzija vsake. Za lzvedbo operaclj spremen1j1vkami na abstrakcije se lahko osebek , k1 ga nad slnhron k a t e r eni ko sk11cu j emo lmenu j emo sinhronlzacl jski osebek. Le-ta j vsakemu prolzvajalcu vsaklč, ko oper ac i J o. Termin "sInhronizac 1 jski osebek" za usklajevalce procesov , monitorje ipd.; to so torej akt popravljajo in spremljajo sinhronizacijskih spremen1j1vk. i z a c I j s k i in I 1i n ! vo j u na določen cen t r a 1 n i e dostopen začne novo upo r ab1j amo semaforj e, Ivnos t 1 , k i s t a n j e S i nhron 1 zac i j sk i ve1j a: osebek j e cent r a 1 en , če da iraa edinstveno ime, kl ga poznajo vsi procest, ki se sinhronIz1rajo med seboj, katerikoll o d teh procesov lma dost op do slnhronizacijskega osebka v vsakem trenutku /LeLaSl/. Nekateri sisteml so zgrajenl tako, da preživijo napake, kl se pojavijo pri centralnem s1nhronizaciJskem osebku. Predvidene so tehnlke za reševanje ob napakah, ki Izberejo nov s 1 nhronizacijsk 1 osebek, ko prlde do napake. Vsak sinhron l zacijski mehanizem, kl temelji na centralnem sinhronIzacijskem osebku lmenujemo centra I iziran. Ostal^e mehanizrae imenujemo po r azde 1 J ene . S1nhronizaciJski mehanizmi so lahko reallzlrani v elementih strojne opreme računalnlka, kot prlmitivi v programskih Jezikih ali v operacijskih sistemih. 5. ELEMENTl STROJNE SINHRONIZACIJE OPREME ZA PODPORO Eden od najbolj enostavnlh mehanizmov, ki omogofiajo nedeljlvost ln medsebojno izk1jučevanje procesov je onemogočan1e preki ni tev procesorja. Ta rešitev je bila uporabljena že na enoprocesorskIh slstemlh, ki so delovali na prlncipu kvazi-paralelnosti. Na porazde1jenih slstemth nima posebnega pomena, saj procesorji med seboj ne morejo lzvajati takih ukazov /Fink86/. V tesno sklopljenih sistemih,.kjer procesorji opazujejo ln popravljajo vrednostl spremenljivk, . je za ohranjanje konsistentnosti nujno zagotavljanje nedeljivosti branja in pisanja vrednosti spremenljlvk glede na prebrano vrednost. Prlmera takih ukazov sta test-and-set i n compare-and-swap /Hwan85/. Taki ukazi oinogočajo reallzacijo. komp 1 eksne j S i h s 1 nhronizacijskih mehanizmov na višjem n i v o j u . Obstaja Se drugsinhronizacijski prlmitiv, ki Je oblCajno reallzlran v strojni opreml in dopušča določeno stopnjo sofiasnostl pri uveljavljanju zaporednostl dostopa do skupnega pomnilnlka. Imenuje se fetch-and-add. Priml.tiv ima obliko F&A(X,e) in vrne vrednost spremen1jivke X ter poveča njeno vrednost za e. Ce se lzvede več taklh ukazov hkratl, se vrednost spremen1j1vke naenkrat za vsoto vseh e , vsak pa dobi vrnjeno vrednost, kot da bl se izvajall v naključnem vrstnem redu poveča p roces ukaz i zaporedno. V Sibko sklopljenih- sistemih uporabljajo kot osnovo za realizacijo nekaterih v i š J en I vo j sk I h mehanlzinov posebne š t e v n I k e , Imenovane fizlčne ure. /Kope87/ predstavlja posebno časovno s i nh ron 1 ?. ac 1 ] sko enoto, kl poleg podatkov o realnem času vsebuje tudl mehanizme za usklajevanje ln popravljane fiasovne baze, zasnovane na. /Lamp78/. S t. ako enoto razbreraenimo procesor, kl ga Je lzvajanje sinhronizaci ] e preveč obremenilo. SINHRONIZACIJSKI JEZIKIH PRIMITIVI V PROGRAMSKIH Pomembna lastnost apllkacijske in sistemske programske opreme, ki poveCuje preglednost in zmanjšuje komp1eksnost, je njena modularnost. Navzven porazdeljen sistem tako lzgleda kot množica programsklb modulov , kjer Je vsak modul zase enostaven zaporeden proces. Procesi v tesno sklopljenih sistemih sodelujejo med seboj tako, da komuniciraJo preko skupnih spremenlj1vk. Osnovna rešltev problema medseboJnega izk 1 jučevanje procesov, ki kpmunlcirajo preko skupnih sp r emen 1 J i vk , Je Dekker.lev algoritem /BenA83/. V njem so združene vse dobre lastnosti enostavnejSih rešitev, kot so akivno čakanje z opazovanjem skupne spremen1jivke (busy-waitIng) in uporabe spremen1jivke za izmenlčen dostop (swltch-var1ab1e). Hkrati pa odpravlja pomank1jivost1, zaradl katerih so te rešftve v praksi neuporabne. Mislimo predvsem na nedoslednost prl medsebojnem izk1jufievanju In na vellko odvisnost med procesi pri iiporabi takega mehanizma. Dekkerjev algorltem je precej kompleksen in nl primeren za imp 1 emen t ac i j o .' Veliko bolj enostavna rešltev je semafor /Dijk68/, ki ga je lahko irnp 1 emen t 1 r a t i In je dovolj. močan, da Iahko z njlm elegantno rešimo probleme medsebojnega izkIjučevanja in razvrščanja procesov. Dobra lastnost semaforjev, ki jo prej omnejenl mehanizmi nlmajo, je tudi to, daso procesi, ki čakajo na doseg do določenega vira, blokirani. Zato medtem, ko čakajo, sprostijo procesne zmog1j1vosti za druge procese. Semaforje lahko uporabimo tudl pri imp1ementacij1 močnejših primitivov. Semafor s Je strogo pozitivna ce1ošteviIska spremen1jivka, ki ji je pridružena še vrsta 110 procesov. Deflnlrani sta dve operaciji nad semaforjem, P(s) in V(s), ki sta nedeljlvl. Operacljo P(s) zmanjša vrednost s za ena, če Je s > 0, slcer pa odložl proces, k1 Je Izvedel to operacijo v vrsto. Operacija V(s) pa zbudi prvl proces v vrstl, če pa Je vrsta prazna,' poveča vrednost s za ena. pomeni, da uporabniku ni treba vedeti, kje se nahajajo iskani vlri nlti mu ni treba sestavljati sporočil. Vse to zna narediti operacljski sistem. Konstrukt v jeziku Ada /USAD80/, imenovan rendezvous, Je komblnaclja RPC in izraenjavanja sporočil. Omogoča sinhron 1 zac 1 jo procesov v času izvajanja konstrukta /BenA82/. Kr 111čna področJ a odpravljajo edlno slabo lastnost semaforjev, to je vellka moznost za napake pri njlhovl uporabl. Neprnvilna razvrstltev operaclj P in V Je lahko usodna. KrltlCna področja so dell programa, kjer proces dosega skupne spremen1jIvke, kl so v tlstem Casu nedostopne drugim procesom. Začetek ln konec krltičnega področja oznaCujeJo posebnl Jezlkovnl konstruktl, kl so zelo enostavnt za uporabo. Operacljski slstem potem sam poskrbl za dejansko realizacljo medsebo]nega 1zkljuCevanJa. Poeo I na krIt1Cna poiiroč j a so prej SnJega področje je nek pogoj. krltlCnega področja razšlrltev konstrukta. Vstop v krtiCno dovoljen šele, ko je Izpolnjen Ovrednotenje pogoja ln lzvedba sta nede1J i va. Hoare in Brlnch Hansen sta defiulrala mon1tor /Hoar74/, /BrHa73/. Podobno kot proces predstavlja koristno abstrakcljo prl mutlprogramiranju je monltor abstrakcija za medprocesno komunlkaciJo. Monltor Je razSlrltev pogojnih , krltlčnlli sekcij. Monltor predstavlja telo, kl vsebuje skupne spremenIj1vke in procedure s kritlCnlmi sekcijaml za delo z njiml. S tein postanejo te spremen1Jivke loknlne, skrlte znotraj monltorja. Procesl, ki želljo dostop do takih spremen1Jivk, ga lahko dobljo samo preko monltorsklh procedur. Monitor je pasiven v slstemu In se aktlvlra sumo takrat, ko procesi želijo dostop do njegovih spremenIj i vk. Prl šibko sklopljenih sistemlh pa je sodelovanje med procesl v razllčnih programsklh modulih povezano s poSlljanJem ln spreJemanjem sporočtl, ki sluzijo za s1nhronizacl]o in prenaaanje podatkov /Slom87/. Komunlkac1ja med procesi je lahko enosinerna ali dvosmerna. Osnovna primitlva pri enosniernl komun I kac I j l sta 'poS1i1' ln 'spreJml'. prl dvosmernl pn zahtevek z odgovorom ( reques t-rep 1 y ) , (remote procedure oddaljenl kllc procedure call) tn rendezvoua• Primitive za sinhrono sprejemanje podatkov najdemo v večlni jezlkov, ki so primernl za porazdeljene slsteme ( ADA /USAD80/, CONIC /Slom85/, CSP /Hoar78/, SR /Andr81/, Pascal-m /Abra83/ ). Modul, kl čaka na sprejem sporočlla od drugega modula se blokira ter postavl v vrsto čakajočlh in se aktlvlra Sele po prejemu pričakovanega sporočlla. CSP ima podoben konstrukt tudi za pošlljanje sporočl 1 . Vsi dvosmernl primltlvl omogočaju sInhronizaclJo med procesl, ki jih Izvajajo. Ceprav se v podrobnost1h in načlnth Izvedbe nekoliko razllkujejo. Zahtevek z odgovorom Je dvosmerni prlmlt.lv, kl Je v bistvu komblnaclja slnhronega pošlljanja ln sprejema sporočlla. Oddaljenl klic procedure Ima določene prednostl, saj omogoča transparentnost lokaclje virov ln procesov /Stan82/. To 7. SINHRONIZACIJSKl SISTEMIH MEHANIZMI V OPERACIJSKIH 7 . 1 Centra) 1 z 1 ran i mehan i zmi s i nhron1zacIj sk i Skupna lastnost centraliziranih s1nhron 1 zac l ]sk I h mehanizmov je v tem. da temeljijo na enem s1nhronizac1jskem osebku. Ftzlčna ura predstavlja osnovo za razvršeanje dogodkov podobno kot v central ! zlranlh slstemlh. Operacljskl slstem za reallzacljo tega mehanlzma uporablja posebne elemente strojne opreme. Procesl so razvrščenl na osnovt Casovnlh značk, kl ]lh dobijo, kadar Je potrebna s1nhronIzac1Ja. Ceprav Je ta metoda enostavna, Ima mnogo pomanJk1jIvostI. Pravllno zaznamovanje dogodkov s Casovnlml značkami je popolnoma odvisno od sprejema stanja ure ob vsakem dogodku. Napaka pri prenosu sporočlla 8 tem podatkotn Je lahko usodna za pravilno razvrstitev. Potrebujemo tudi vnaprejSnje točno poznavanje zakasnltev v prenosnlh kanallh. Natanenost Je odvlsna od zahtev sistema oziroma apllkaclje. Stevec dogodkov Je objekt, kl Steje dogodke, kl so se zgodtli v doloCenem razredu (npr. aktivnostl). Deflnlranl so trlje prlmltivi: povečaj vrednost števca, preberl vrednostl Stevca in odloži kllcočl proces, dokler ni vrednost števca vsaj enaka podanl konstantt. Pomembna prednost tega mehanizma je v tem, da dovoljuje soCasno Izvajanje teh prlmltlvov na istem Stevcu brez medsebojnega 1zk1jučevanja. Pojem "Stevec z enlm upravljaIcem" je definiran kot Stevec dogodkov, ki deluje pravllno, dokle.r Je prepovedano sočasno povefianje vrednostl Stevca. Vendar pa je sistem zelo občutljiv na izpad posaroeznlh elementov, saj je vsaka napaka števca usodna za pravilno razvršfianje. StatIčn i razvržčevaln1k uporabljamo za popolno razvrstltev dogodkov v danem razredu (stevec dogodkov omogoča samo delno urejenost). KazvršCevalnlk Je celoštevllčtia spremenlj1vka. Za delo z razvrSčevaln1kom je deflntran samo en prlmltiv, lmencvan vstopnica (tlcket), kl vrne tekoCo vrednost razvrščeva lnika in poveča njegovo vrednosti za 1. RazvrSčevalnlk zahteva loeen mehanlzem za medsebojno 1zk1jufievanje zato. da je prlmltlv vstopnica nedeljiv. Dva proizvajalca ne moreta dobltl vstopnlce hkratl. Glavni problemi pri uporabi razvrščevaln1ka so pri Izblrl mehanizma za raedsebojno izk1jučevanJe in vpllv napak alt Izpada razvrSCeva ln lka na prežlvetje s I nhron1zac1jskega mehanlzma. Jasno je, da centralIziranl prlstopi v porazdelJenlh sistemlh ne izpolnjujejo zahtev, kl so blstvene za take slsteme. Slsteml. zgrajenl na takth osnovah. ne morejo lmetl vlsoke stopnje razpolozlj1vosti in imajo v splosnem slabše zmog1j1vosti zaradl 111 ozkega grla. kl ga predstavlja centralna enota. 7.2. Porazdeljenl mehanIzml s1nhron i zac I j sk 1 S porazdelJenlml raehanlzmi dosegamo večjo stopnjo paralelnosti ln s tem hitreJSe delovanje, boljSo 1zkoriSCenost opreme in veCJo zanes 1 Jivost . Porazdeljenl sinhronizac1Jskl mehanizml so večkratne fiziCne ure, večkratne loglčne ure, abstraktnl lzrazi, ' skupne spremen1J1vke, krozečl žeton In krožeči razvrščeva l nIk. CilJ uporabe f1zlčnlh ur je v določltvl enotnega flzičnega Casa v sistemu. Konsistentno dode1jevanje lahko doblmo iz popolne kronoloSke razvrstitve aktivnostl, ki se pojavljajo v slstemu. Prl uporabi več ur ni pomembna samo točnost vsak.e posamezne ure ampak tudi raedsebojna usklajenost. tako da je razllka med potjubnima dvema urama manjSa od vnaprej doloeene konstante. ReSItev tega problema Je podal Lamport /Lamp 78/. Sistem modeliramo kot povezan graf procesov s premerom d. Premer grafa predstavlja minimalno Stevllo procesnih mest, preko katerih mora iti sporočilo iz poljubnega procesnega mesta, da doseže poljubno drugo procesno mesto. Vsak proces lma uro ln periodično (perioda t) poSllja sinhron1zaciJska sporočtla vsekemu drugemu procesu. Vsako sinhron1zaclJsko sporočilo vsebuje fizično časovno znaCko. Po prejeriiu slnhronlzacljskega sporočila proces pomakne svojo uro naprej, če Je časovna značka večja od stanja ure. Predpostavljamo, da poznamo spodnjo mejo (u) In zgornjo mejo (u + z) zakasnltev na komunikac1jsk1 mreii. Naj bo k natančnost vsake ure (k<10~ ) in e dovoljen zamik med poljubnima dvema urama. Ce Je e/(l-k) < u in e << t, potem Je možno izračunatl približno vrednost e, ki Je prlbl1žno d(2kt + z) . V odvisnostt od zahtev glede relativnih zamlkov in veljavnostl predpostavk glede zakasnltev na komunikacijski mreži se lahko odločlmo za tveganje, da bomo občasno Izgublli sporoClla zaradi prevelikih zakasnitev in tako dosegll verjetnost, no s I nhron I zac I jo ali pa ne boino tvegali. Tak prlstop blstveno . zmanjša zmog1JIvost1 slstema. Ključni paramcter prl tem Je razmerJe z/u. Večkratne loglčne ure so prviC oplsane v /Lamp 78/. Imp1ementirane so kot funkctje C, kl dodelljo Stevllo vsakl začetl lokalnl aktlvnostl. To so torej navadni števcl. V slstemu, kjer ima vsak proizvajalec svojo logtčno uro Je probletn, kako zagotoviti globalno razvrstltev. Funkclja C ima lastnost, da velja C(i.a) < C(J,b), če sta a in b aktivnosti v procesih i in j ln velja a > b. Prl reallzacijl logičnlh ur moramo upoStevati dve pravlli: Pravilo 1: Vsak proces i poveča vrednost Stevca C(i) med dvcma zaporednima aktIvnostlma. Pravllo 2: Ce aktlvnost a v procesu i poSllJa sporočllo In potem sporočllo m vsebuje Casovno značko T(m) = C(l.a). Po prejemu sporočlla m proces J postavl svoj števec C(j) na vrednost, ki je večja ali kvečjemu ennka trenutni vrednostl in je veftja od T(m). Vsako funkcijo C, ki ima zgoraj navedeno lastnost. lahko uporablmo za popolno razvrstitev poljubne množlce aktlvnostl. Za to potrebujemo Se popolno ureditev procesov (npr. glede na njlhova imena). Aktivn,ost a se je zgodila pred b. Ce Je C(l,a) < C(J.b) ozlroma C(l.a) =• C(J,b) in je 1 < J. SihronizaciJski mehanizem definiran s pravlll 1 ln 2 in popolna razvrstttev dovoljujeta konsistentno dodeljevanje aktlvnosti. Definirana popolna razvrst(tev nl edinstvena in nl ekvivalentna kronološkl razvrstltvi. To Je razlog, da Je včaslh treba imp1ement1rati sistem logifinlh ur na slstemu fizifinlh ur. Mehanizera z uporabo abstraktnlh izrazov /Herm83/ temelji na uporabl logičnih ur. Vsaka ura ima poleg osnovne verzije, kl je pri procesu, kl povečuje njeno vrednost Se dodatne verzije prl drugih procesih, kl sarao spremljajo njeno vrednost. Pr edpos t av Itno , da mora vedno veljatl ubstrakten izraz kjer sta c. in k konstanti, Xj vrednost loglčne ure in 1 število logičnlh ur. Dodatne verzije loglčne ure lmenujerao njene sllke. Označene so z m(x ) in se lahko razllkujejo od osnovne verzlje. Z uporabo dodatnih verzij pri delu s s1nhron1zac1jskimi spremen1j1vkaml zelo zmanjšamo komunikacijske potrebe in povečamo učinkovitost. Zamenjava osnovne verzlje loglčne ure z njeno sliko je dopustna, če pri zamenjavl upoštevamo tako stroge omejitve, da je kljub dopustni napakl sllke izpolnjena zahteva osnovnega abstraktnega tzraza. To pomenl, da lahko prl slikati logičnih ur. kjer je konstanta c( negatlvna popravljamo njlhove vrednosti z zakasnitvljo, ne da bi s tem ogrozill pravllnost abstraktnega izraza. Podobno lahko vrednostt sllk logičnth ur, ki imajo kons t anto vnaprej . c. pozitivno, popravljamo S 1 nhronizac1jsk 1 mehanizmi, ki temeljijo na flzlčnlh all logičnlh urah lmajo skupno lastnost, da ne temeljijo na medseboJnem izk 1 Jučevanju. To Je velika prednost pri uporabl v porazde1jen1h slstemih, saj omogoCa paralelnost izvajanja.. Sinhronlzacljskl mehanizml 1ahko prl svojeni delu uporabljajo dejstvo, da imajo proceši edinstvena in stalna lmjna. To določa popolno razvrstltev ppocesov, ki daje opazovalcu občutek, da so procesi povezani v neko verigo ali obroč. Vsak proces lma natančno določenega prednlka ln naslednika. Taka logična razvrstltev ni nujno povezana s fizično topologijo sistema. Obroč služl kot osnova za prenašanje posebnlh pravic med procesi v sistemu. Pri sinhron1zacij1 taka posebna pravica pomeni dostop do s lnhron 1 zacljskega osebka. Skupne spremen11i vke: S i nhron i zac1j skI mehanizem, ki temelji na konceptu logiCnega obroea Je bil predstavljen v /Dijk74/. Ker predvideva uporabo skupnth spremenljlvk je uporaben v tesno sklopljnlh slstemth. LastnlStvo nad posebno pravlco tahko zaznamo z opazovanjem spremen1JIvke, ki Jo proces dell z enlm od obeh sosedov v obroCu. Z znanimi nlgorltml lahko dosežemo stabilno stanje, kjer od večih posebnlh pravtc ostane samo še ena, ki potem krozl po obroču ln zagotavlja medsebojno Izk1JučevanJe. Odkrivanje napak, reSevanje iz napak in dlnumlčno Slrjenje slstema so možnl z metodami, opisaniml pri podajanju žetona. 112 KrožečI žeton je s 1 nhron1zaciJsk1 mehanizem zasnovan na enaRih osnovah kot deljene spremen1Jivke, le da se posebna pravica prenaSa med procesi s sporočilom, ki ima edinstveno obllko ln ga imenujemo žeton. S tem prlnclpom dosežemo medsebojno Izk1jučevanje procesov v šlbko sklopljenih slstemlh. Po prejerau žetona lahko proces opravl željeno aktlvnost. 2eton lahko obdržl največ nek naprej določen čas in potem ga mora predatl naslednlku v obroču. Mehanlzem mora zagotoviti obnovitev logičnega obroča ln podajanja žetona, če lzpade trenutni lastnlk žetona all katerlkoll elemnnt loglčnega obroča, hkratl pa lahko dopušča v slstemu samo en žeton. Protokoll za odkrivanje napak in njihovo reševanje so podanl v /LeLa77/ In v /LeLa78/. Tak s 1 nhron1zac1jski mehanizem je uporabljen tudl na loglCnem nivoju lokalnlh mrež in definlran v /ISO802/. UCinkovitost s 1 nhron 1 zacijskih mehanlzmov za medsebojno lzključevanje med procesi je v vellki merl odvisna od časovne obsežnostl krltičnih sekclj. Ce kritične sekcije vključujejo izmenjavo sporočil med proizvajalci In potrošnlki, potem to daje nizke zmoglJ1vostI. Krožečl razvrSčeva1nik je razvršCeva1nik, kl stalno krožl po logičnem obroču tn uporablja mehanizem podajanja žetona. Po prejemu žetona lahko proces aktivira več prlmitlvov tipa vstopnlca ln potem pošlje zeton nasledntku. Na ta načln dosežemo medsebojno izk1jučevanje uporabnikov razvrSCeva1n1ka. V članku /LeLa78/ je oplsanl protokol, ki uporablja oplsani koncept. Protokol uporablja Stevilko obhodov, kl jo nosi žeton ln se poveCa vsaklč, ko doseže proces, katerega naslednlk lma nlžjo številko, kot Je njegova. shranjevanje potrebnih informacij Konvergentnost In poSt, enost s t a 1 a s t. n o s t. I se v konfltktnlh enakomerno slstema. kl zagotav1Jata, da situacijah viri ln zmožnosti porazdelljo med tekmujoče procese. RazSlrljivost je zahteva, da mora sinhronizac I Jsk 1 mehanlzem dopuščati dodajanje all ponovno vključevanje procesnlh element.ov, ne da bl s tem mo t I 1 delovanje s i s tema. I)o 1 nčono« I. . Sistein lmenujemo det.erminlst.ICen, Ce Je zasnovan tako, da v vsakem primeru doseže sinhroniziranost . Ce pa dosežc sinhronizaciJo samo v vefiini primerov, se sistem imenuje verjetnosten. Reševanje iz napak Je zelo pomemben nabor funkcij. Posameznl mehanizmi se razllkujejo po kolifiini pomočl, kl jo nudljo prl reševanju lz napak, po vplivu pokvarjenlh elementov slstema na pravllno delujoče 1u po easu, kl Je potreben, da se popravljenl elementi spet vključijo v normalno delovanje s i s tema. Povezanost med elementl sistema se zelo razlikuje glede na razllčne mehanizme. Slabi so taki mehanizml, ki zalitevajo polno povezanost, saj Je le-ta zelo draga v primerjavi s tlpl povezanostl, kjer so elementi združenl v verigo all obroč. Vzpostavi tve z aCc t neRa s t an j a komp1eksnosti lahko zelo razllkujejo. po Razum)jIvost In enostavnost mehanizma nam olajšata delo pri snovanju, formalnem preverjanju, lmp1ementaciJi, testiranju in vzdrževanJ u . 9. LITERATURA 8. KRITERIJI ZA SINHRONIZACIJSKIH MEHANIZMOV VREDNOTENJE Sinhronizacljskl mehanizml nimajo ideiitičnih lastnostl. V nadaljevanju podajamo važnejše kriterije za vrednotenje sinhronIzac1Jskih mehan1zmov. Pomembnost vsakega od njlh Je odvlsna od omejttev. kl jih postnvimo s1s temu. Odzivnl čas ln propustnos t mora v največjl možni meri izkoriSčatl vse prednosti delovanja porazde1Jenega slstema. v s I nhronizaclJi in. prl komunIc1ranju Vs ak mehanIzem upoš tevat 1 I n paralel nost i Paralelnost omogoča veliko propustnost in kratke odzivne čase. Prožnost pomeni, da mora sinhron1zac 1 Jski mehanizem bltl odporen na pojav napak in zmanjSanJa Stevila procesov v s1stemu. Potrebujemo pravzaprav bolj natančnb merjenje te lastnosti, ki bl izrazila Stevilo hkratnih napak oziroma tzpadov procesov, ki jlh sistem 5e prež 1 vi. Dodatna poraba vlrov (overhead) je piavzaprav cena, ki jo moramo plačati, da iahko lzvedemo sinhronizac1jo. Kaže se v povečanju prometa med procesl ln je odvisna od števila in velikosti paketov, v večjI potrebl za procesiranje (dodatnih sporočil za s lnhronlzacijo) in v uporabi pomnilnlka za /Andr81/ G.R.Andrews: The 0 1 str1buted Programming Language, Software Practlce and Experlence vol.12 1982 /BenA83/ M. Ben-Arl: Prlnclples of Concurrent Programming, Prentice Hall Internatlonal 1983 /BrHa73/ P.Brinch Hansen: Operatlng Systems Prlnciples, Prentice Hall 1973 /Dijk68/ E.W. Sequen t i al Languages, Di jks tra: Proces ses i n Academlc Press Cooperati ng Progr ammi ng 1968 /Dijk74/ E.W. Sys t ems Con t ro 1 1974 Dijkstra: Se I f-stabI I izing ln Splte of Dtstributed Comm. ACM vol.17 no.ll /Fink86/ R.A. Finkel: An SystemsVade Mecum, 1986 Opera t1ng Prenti ce-Hal1 /Herm83/ D. Herman: Approach to Control of Di str ibuted Academic Press Towards a Sy s t ema t. i c Implement Dlstrlbuted Sjrnchronization, tn Computing Systems, 1983 /Hoar74/ C.A.R. Hoare: Monltors: An Operating Systems Structurlng Concept, Comm. ACM vol.17 no.10 1974 113 /Hoar78/ /Hwan85/ C.A.R. Sequen 11a1 vo1.21 no. Hoare : Processes 8 1978 Commun1ca t1ng Comm. ACM K. Hwang, Archl tecture McGraw-Hl11 F. A and 1985 Br i ggs : Compu ter P a r a 1 e I P r o c e s s 1 n g , /1SO802/ ISO IS 8802/4 Local Area Networks, Token Passlng Bus Acces Protocol /Kope87/ H. Kopetz, W. Ochsenre 1 ter: Clock Synchron1zat1on in Distrlbuted Real-Tlme Systems, IEEE Trans. on comp., vol.36 no.8 1987 /Lamp78/ L. Lampor t: Order i ng of vol.21 no . 7 Tirae , Clocks , and the Even t s, Comm. ACM, 1978 /LmpsSl/ L. Lampson: Atomic Transact ions, LNCS 105, Sprlnger Verlag 1981 /LeLa77/ G. LeLann: Distributed Systems Towards a Formal Approach, Proc.IFIP Congress Toronto, North-Ho11and 1977 /LeLa78/ G. LeLann: Algorlthms for Distributed Data Sharing System whlch Use Tlckets, Proc. 3.Berkley Workshop, August 1978 /LeLa81/ /Slom85/ G. 105 , M. for Proc Cont 1985 LeLann: Spr 1 nger Sloman et Bui ldlng 6.IFAC r. Comp. Synchron i zat i on , ver1ag 198 1 LNCS al : The CONIC Toolki t Distrlbuted System VVorkshop on Distr. Sys., Pergamon Press /Slom87/ M. SlomariV' J. Kramer: Dlstrlbuted Computer Systems and Computer Netvvorks, Prentice Hall International 1987 /Stan82/ J.A. Stankovlc: Software Conunun1catIon Mechanlsms: Procedure Calls vs. Messages, IEEE Computer, Aprll 198 2 /Tr!p87/ A.Tripatbl: Dlstrlbuted Operatlng Systems, Tutoria) of 7th ICDCS Berlln, september 1987 /USAD80/ USA Departement of Defence: Reference Manual for the AUA Programmlng Language, Proposed Stahdard Document 1980 /VerjB3/ J.P. Verjus: Synchron 1 zat 1 on In Distributed Systems, ln Distributed Computing Systems, Academlc Press 1983