INFORMATICA 1/1982 PREGLED JEZIKOVNIH ELEMENTOV ZA OPIS SINHRONIZACIJE PARALELNIH PROCESOV UDK: 681.3.012 MONIKA KAPUS INŠTITUT ..JOŽEFSTEFAN", UUBLJANA tflanek podaja pregled razvoja jezikovnih »lenentov za opis sinhronizacije paralelni pracesov. Povdarek j» na predstavitvt Iogi£n1h osnov paraleInega prooesiranja \n na opazovanju pojavai da postajajo jezik 1 za aultiprograniranji vedno bolj homogeni. The paper is an overvitu o< the development of synchronizatlon primitives. logicat basts of paratlel processtng and describes th» hoaogenization of languages. It presents the nultiprogramming 0. Uvod V zatfetku je bil osnovni namen paralelnega procestranja »konoattfno izkoritfftanJ» hardvara v gkladu s pravilomi da naj proces zaseda nek raCunatntSki vir le v tistih Basovnih ir.terval ihi ko ga zaras uporablja. Operacijski sifiteo je moral dtlovati takoi da so procesi tfio nanj tfutftt prisotnost drugih procesov v sisteau. Zato dela prograaske kodet ki sta se Izvajala paralelnoi nista smela btti logiflno povezana. zavedatii izvajali razdelijo NajpreprostejSa povezava med procesi se je pojavila takrati ko so se progranerji zaffeli da lahko programei ki so se prej kot en procesi na nekaterih odsekih na paralelne procese in s tem jj tfas obdelave. Taki paralelni procesl so bili logifino povezani v tem snislu« da se je izvajanje programa Lahko nadaljevalo £ele takrati ko so biti znani rezultati vseh paralelnth prooesovt ki so se spet zdruiHH v en proces. Pravzaprav ni Slo za medsebojno povezavo paralelnih procesovt temvefi za povezavo paraleltiih prooesov s svojio oSetomi ki je med njihovin iivajanje« miroval. Z razvojen velikih raffunalnifikih ststeaov se je pogled na paralalno procesiranje sprenenil. Predvsem sfi je veflina logifinega naCrtovanja prenesla s harduarskega na programski nivo. Se vefi: Po splofini sistemski teoriji sta dva sistena ekvivalentnai tte dajeta pri enakih vhodnih signalih enak odziv. Zato se je na programski nivo preneslo tudi funkcionalistiCno pojmovanje sisteaa. Uveljavilo se je praviloi ena funkctja-en Eistemskt blok. Sisteoski blok v raffunalnifitvu je navideznt (logiBni) stroj. ki je izveden harduarskoi programsko ali aetfano. Programsko izveden logitfni slroj predstavlja v sistcnu poseben prooesi ki je atalno prisoten* tako kot bi btl harduarsko izveden logiBni stroji ali pa ga poJfeneoo iakrat. ko ga potrrbujemo. Razbitje natogs na funkctjske bloke je posebno pri«erru> za pisanje obseKnih programovi kakrtfnn Je operacijski sistem. 1. LoaiBna odvlsnost pardlelnih nrpceiov Funkclonalistitfna opredelitev procesa je najbolj naravna* saj je proces deklariran kot objekl-nosIlec aktivnosti. Zaradi takega natfina dela pa procesi niso veS nujno neodvisni. Dva procesa sta medseocjno logifino odvisna« Be uporabljata skupne ratfunalniSke virei ki so lahko pasivni ali aktivni predmetii tako da se morata tecja zavedati. Ker je vee dogajanje v ratfunatniku v bistvu branje in spreninjanje podatkov. so procesi soodvisni natanko takrat« kadai- lzvajajo operacij* nfl istih podatkovnih predmetih. Podatkovne predmetei ki jih obravnava procesi deliao v tri skupinet vhodne spremenljivkei izhodne sprementjivke in sprenenljivke stanja. Kot pri vsakea sisterau smemo meje prnoesa premikatii pri Cemer zaiamemo med sprenenl j (vke stanja veff ali m.in) njegovih operandov. Ker pa Jfelimo obravnavat i proces kot logiffni strojt uvrstino med spremenljivke stanja le tiste spremenljivkei do katerih nima neposrednega dostopa noben drug proces. Vhodne in izhodne sprenenljivke procesa so v sploSnem tudi vhodne ali/in izhodne spremenljivke drugih procesov. 2. Sinhronizaciia procesov Za pravilno delovanje praviloi sistema vetja nastednje Ko eden od procesov nastavi vrednost neke spreraent j i vke i ki naj b\ jo brala ski|pina prouesov-Citalcev (lahko tudi procesi ki je vrednast vpisaDi soejo vsi procesi to vrednost poljubno spreoinjati pod pogojeot da bo imela sprcoenljivka pravilno vrednost v vseh tistih trenutkihi ko jo bo bral kak proces iz skupine Citalcev. Vidimoi da iaajo procesi skaraj popolno svdbodo. Na spreaenljivkah smejo izvajati poljubne operacijei ki niso prepovedane s statifinia zaSCitnio mehanIZBOO podatkovnih predmetov. to je s pravilit kateri aktivni predmet i imajo (i-avico doslopa do nekega pasivnega predaeta in kaktfen sne biti ta dostop. Od procesa zahtevano le toi , da spremenljivke po polrebi vraCa na stare vrednosti. Ooenino («i da zgodovine spreaenljivk ne predslavlja v vsakem primeru enn sama vrednost. Spreoenljivka ima navidezno toliko vrednostii kolikor je procesovi ki so vanjo vpisati neko vrednost z namenont da ostane konstantna. Lahko bi 72 ugovarjali. da Je tako razmiSljanjs nepotrebnoi saj bi iahko dalt vsakemu procesu svojo spremenljivko. Vendar vseh spremenljivk. ne moreroo enostavno razntnoi i t i. To velja predvsem za aktivne spominske celieei kakrfine so registri. Organizacija sistsmai v katerem obstajajo spremenljivke z vetf navideznimi vrednostmii je izredno težlkai posebnoi kadar inamo enakopravne procese. Problem sinhron1zacije procesov zapletajo tfasovni pogoji. V preprostih sisteraih zadoStfai da uskladimo hitrosti posaraeznih procesov kar z vstavljanjem ukazovt ki porabijo dolotteno Stevilo urinih oiklov. Taka sinhronizacija procesov je statiBna in se ne zna prilagajati nepredvidenim motnjara v sistemu. SploSna refiitev je s i nhroni zac i j a procesov z medprocesno komLin ikac i jo> ki je lahko neposredna preko skupnih spremenljivk al i pa posredna preko pomoinega procesa. Pr> sinhronizaciji preko skupnih spremenljivk procesi ki prvi dose2e sinhronizacijsko tofikoi v zanki testira sinhronizacijsko spremenljivkoi dokler rou drug proces ne pofilje statičnega signala. Komunikacija preko pomoSnega procesa je lahko takai da partnerja paC izvajata operacije nad sinhronizacijsko spremen l jivko s posredovanjem pomožnega procesa. Najpogosteje pa je 'posrednik sistemski procesi ki mu hitrejfii proces narotfii naj ga po^enei k'o bo partner priScl do s1nhronizacijske tottke. Proces fiaka pasivnoi kar je zelo ugodnoi ker tudi golo testiranje troši ratunalni^ki Bas. Sporofiilo poSasnega prooesa posrednikui da' je dosegel sinhronizaoijsko. tofikoi predstavlja kratkotrajen signali ki požene tfakajoči procesi tfe seveda obstaja. tie je fiakanje simetriffr)Oi torej tie ffaka vedno tisti procesi ki je pr.vi priSel na s i nhron i zac \ jsko tofiko« partner pa vedno po^Lje signali se bosta procesa vedno uspešno sretfaLa (princip rendez-vous-a). tfe pa vriaprej predpiSemot kdo poSilja signale in fcdo jih tfakai je nevarnot da se kak signal Izgubit kar je usodnoi Ce procesi ki je poslal signali kar nadaljuje izvajanje. V' tem prjmeru se procesa ne sretiala. Isto veljar tfe proces dinamitfno signalizira potjuben dogodeki na katerega Baka partner. Pogoji za delo so tahko popolnoma izpolnjenii pa proces tega ne opazi. 2.1. Problem vzaiemnega i zkliuBevan i a Osnovni probtem sinhronizacije je dostop veb procesov do skupnega podatkovnega predmeta. Oovoljeno je paralelno branjei ni pa dovoljenp paralelno pisanje ali paralelno branje in pisanje. Dele programske kodei 'ki naslavljajo obravnavani prednetf imenujemo z ozirora na ta predmet kriliBne dele prograraa. Recinot da z^elimo zagotovitii da bo v vsakem trenutku izvajal svoj kritjtini det najved en proces. Nalogo iraenujemo problem vzajemnega Izkljuftevanja. Od refiitve zahtevamo Se naslednje lastnosti: -simetrijo (prooesi ne smejo imeti. stattfine priori tete)» -neodvisnost-od relativnih hitrosti procesovl -neobfiutlj1vost na pojavi da se kak procos ustavi izven kritifinega delai -kadar vetf procesov hkrati zahteva vstop v krititfni deli se mora algoritem odlofiiti z* enega od njih v kontnem fiasu. Problem vzajemnega izkljutfevanja ni diroktna posplo£itev vsakega sinhronizactjskega probteraa. V nekaterih pogledih so zahtevi prestroge (npr. ne . dovolimo paralelnega branja)> v nekaterih preblage (npr. nt predpisujemoi da moramo vrednost podatka najprej vpisatii prtden jo lahko beraoo). Algoritem vzajemnega izkljufievanj* je saoo orodjei s katerim lahko reSimo katerikoli sinhronizacijski problem. Z vpetjavo dodatnih spremenljivk za medprocesno sinhronizacijo brez tefav omejioo vzajenno izktjutfevanje na tiste dele programdvi kjer je res potrebno. Problem vzajejnnega i zkl jutfevan ja je prvi reSil danski matematik J.Dekker. ZapiSimo atgoritem za vzajemno iskljufievanja potjubnega fltevila procesovi ki ga je predstavil Dijkstra v C33 v Atgolu 60) begin integer arrav bic C0!N3i i nt eaer turrti f or turn != 0 step 1 unt i l N d_o begin bCturn] s= li cCturn] != 1 ertdi turn := Oi parbegin prooess H begin end i . "probess 2l beg i n end i process NJ begi n end parbegin end. process i: begin i nteger j! Ai: bCi] : = Oi L i i IX be turn <> i then in , cC i 3 i= 1i . i f bCturnJ = 1 then turn '• = i i • v. . goto L i endi cCiD != Oi for . i := 1 step 1 untit N do begin jj. j <> i ajid cCj] = 0 then goto Li endi krititfno podroCje! turn. := O'i cCi3 := 15 bfj] i= li . pstanek cikla ii goto A1 end,- Namesto dokazai d.a algoriten zadofitfa vsem zahtevami opiSimo njegovo delovanje v naravneo jeziku. Zanimivo jei . da v aLgoritnui ki omogotfa medsebojno izkljufievanje procesovi vsi procesi prosto uporabljajo skupn* spremenljivke. . Poraisliti pa moranot da je digitalni raffunalnik sekvenfin.i stroj i v katerem se ukazi za pisanje in tfitanje po naravi izvajajo zaporedno. tie zahtevamo vpis dveh ražlitfnih. vrednost a in b v isto spremenljivkcn bo vrednost spreoenljivke v vsakem trenutku ali a ali bi nikakor pa m mefianica obeh vrednosti. Konkurenflni procesi sklepajo na naslednji naffini OznaCim. da Jelin vstopiti v krititfno podroffjc. Preverimi tie sem navrsti. tie nisenii pogl.edami at i j.e tistis ki je navrstii konftal delo. Be ne dela veff. oznaCiai da isa navrsti - jaz. Preverimi ali ni raorda kak drug proces tud-i ugotovili da prejSnjt procis ns dela veS in se je poskusil postaviti na jafietek vrste. Ce me je izrinili zaCntm postopek za preboj. na Selo vrste od zaSitka z vljudnia flakanjemi *da proces na fielu kontfa delo. Ko sem na tfelu vrste, oznaeini da vstopara v kritifino podrofije. Spet privirlii ali morda kdo ne dela. To je flisto aogofle. Med trenutkomi ko sera ugotovili da ii l«am pravico postaviti na dtlo vrstti tn mtd cojin vpisora ha tfeto vrste je minilo nekaj fiasa. Hedtem je tahko kak posebno hittr proce«. ki se prej Ce ni zanlmal 7» kritiflno podrotfjti prifiel (n zafiel z delon. flt jt to riii >t au umaknen in ponovim postopek za prtboj na zafletek vrstei sicor pa vstopli v kritiflnp podrotfje. Po izstopu oznatfioi da «• ktlriiino 73 podrotfje ne zanima ve/J in ustvarto mofnostt z< enakopraven konkurentfnt boj vseh procesov. 2.2. MedeU tvost Semafori1 vzroka In posLedioe. Iz tega algoritma smo se nauCill. da JB vtr te£av naslednje preprosto dejstvol Proces dobi informaoijo o stanju drugih procesov in se odlotfii kako bo ukrepal. Toda ko zafine ukrep izvajatii ntma zagotovilai da stara 1nformaci]a sploh Se velja. Morda je dobil jsignal te . novo vrednost. Problem je v preveliki dinamiki procesovi ki poSHJajo signale. . Vsak signal :zahtevoi nora tzpolnjevatI naslednjo Stgnal naj k 1 j i m j i traja dovolj namen jem kolikorkrat ?elijoi stanjei .signali pa mora trajatii uresnitfeni vs< ukrepii ki so stanja in ne bi vetf ustrezalii spremen iU. dolgoi da ga prooesii opazijo 1n preberejoi ki ga opisuje dokler nifio posledioe tega fle bi se stanje To pravilo nedeljivosti vzroka 0 then si= s+1 else beoi n vktjuSi prooes v vrstoJl utill P(«) end end. Operacijc v oklepajih so nedeljivs. Definioija semaforja n>. pove nifl o njegovi Izvedbi. Tudi na podroCju sinhronizaoiji prpoesov teKino k lo«itivi deklarat(vnoga \n proceduralnega obravnavanja problema. tie zapiSemo obsefno proceduro za sinhronizacijo< sloer lahko pravilno delujei vendar njej namen n\ Jasno vtden \n preverjanje pravilnosti je teifko. Zato vk l jufiu j emo ukaze za s1nhronizacijo v visoke prograraske jezikei v; katerih opisujeno« kakSen naj bo odnos med procesi 1n podatkovnimi predmetii gradnjo potrebnih prooedur pa prepustimo prevajaLniku. 2.3. Razvoi sinhronizao i io iez ikovn ih elemcntov Pred deftnicijo semaforjev je moral programer vedno znova pisati proceduret kakrSen je Dekkerjev algoritem. Ukazit ki bi zdrui?evali testiranje in spreminjanje podatkovi praktiSno niso obstajali.Seraafor pomeni prvi podatkovni predraeti ki ni navadna spremenljivka in je namenjena izkljuBno sinhronizaciji. Po uvedbi semaforjev so si avtorji najprej prizadevali i zboljgat i sam koncept semaforiev. Operacije na semaforjih so testiranje razliflnosti od Oi zmanj^anje in povefianje vrednosti. Uodon je leta 1972 namesto P in V operacij uvedei operaciji u£ 0)i doun SaiSq pomeni zmanj£anjei u£ SaiSq pa povefianje semaforjev a 1n q. Na ta nafiin Lahko realiziramo bolj kompleksne nedeljive pare pogojev in posledic (npr. Sa.Sb.i doun SaiSb). Dijkstrov semafor je le poseben primer < s! down s = P(s)i up. s = V(s)). Izboljfievanje P in V ukazov se je konfialo s predlogi bolj sestavljenih pogojev za izvedbo operacij CAND/OR izrazi) in z razniSljanjem o organizactji impLicitne vrste. Z razvojem teorije programskih jezikov se je pogled na ukaze za sinhronizacijo spreminjal. Prodrlo je spoznanjei da moramo ponuditi programerju taka jezikovna sredstvai ki ga bodo spodbujala k strukturiranemu programiranju. Hoare in Brinch Hansen sta leta 1972 definirala "kritiCno podrotfie". Novost je v temida prevajalniku deklariramoi kateri podatkovni preraeti so skupni. Kadar i^elimo delati s skupnimi podatkovnimi predmetii to eksplicitno izrazimo in sistem sam poskrbi za vzajemno izkljufievanje. var v i sharedi region v do operaoija na v <£d PrevajaLnik pomaga programerju na ta natjim da javi napakoi Be naslovimo skupne podatke izven krititfnega podroflja. Se botj struk tur* irana so pogo ina kr \ t i tfna podroCia (prav tako Hoare in Brinch Hansen)i k1 so naravna razSiritev pojma kritifinega podroffja 4n vkljufiujejo Se Sakanje procesa na dogodek. var v shared? reaion v vihen B do operacija na v s^ Ko pročes vstopi v kritifino podrofljei se testira pogoj B. fie je pogoj izpolnjem le zahtevana operacija izvedei sicer pa proces zatfasno zapusti kritittno podrotije in se postavi v procesno vrsto spremenljivke v. Vrsta je ena sama za vse procesei ne glede na toi na kakfien pogoj ffakajo. Kadarkoli nak proces uspetfrui zakljufii operaoije v kritiOnem podrotfjui sistem testira pogojsi na katere ffakajo procesi v vrst i i \n potttne snega od procesovi katerih pogoj je izpolnjen. Princip pogojev ]e ekvi valentan *t at itfnem zignalooi. Danes so jezikovnt elementi za sfnhronizaciJo dosegU stopnjo« ko predstalja s Inhron i zac < ta le del oplsa abstraktnega podatkovnega t ina \n programerju o njej sploh ni treba razmiStjati» kadar ptSe proceduro« v kateri naslavlja skupnt podatkovni predmet. Abstraktni podatkovnl tip zdrufuje opis podatkovne strukture 1n operaciji ki so na njej deftnirane. Zunaj dela programa« kjer opifiemo podatkovni lipi lahko opazujamo samo ufitnek definiranih operacij na predmete tega tipai nikakor pa ne nafiina izvajanja teh operacij. Lastnosti abstraktnega podatkovnega tipa lahko preverjamoi ne da bi upo£tevali uporabq posameznih prodraetov tega tipa. Preverjati abstraktni podatkovni tip pomeni preverjatii ali izvedba operacij na padatkovni strukturi ustreza deklaraciji. Tako pojmovanje sinhronizaoije omogotfa hierarhiBno fitrukturiranje .obse2nih programov. Iz operaciji ki smo jih definirali in preverili na n12jih ntvojthi lahko gradimo operacije na vifijih nivojih, ki jih testiramo Le glede na deklaracije viSjih nivojev. NajenostavnejSi primer podatkovnega tipa z vgrajeno sinhronizacijo so mon i torii (Dijkstrai Brinoh Hanseni Hoare). Monitor je konstrukt< ki vsebuje lokalne spremenljivke in procedurei ki definirajo operacije nad temi jspremenljivkami . Monitorsks spremenLjivke lahko doseierao te preko oionitorskih procedur. Vsaka monitorska procedura sme imeti tudi svoje lokalne spremenljivke. Monitorske procedure ne smejo nastavljati spremenLjivk zunaj monitorja. Vse monitorske procedure se vzajerono izkLjufiujej01 le v primerui da kaka proccdura tfaka na signalisme teffi druga procedura do takrati da prva procedura sprejme signal in spet pravzame kontrolo. Navadno monitorske procedure ne sprejeraajo zunanjih signalovi ampak tfakajo na signal tistT monitorsko procedurei ki tetle. Signali so •dinamifnii to pomenii da se izgubijo« tie jih nihffe na tfaka. Hkrati sme Cakati na signal sne vrste tudi vefi procedun po signalu pa stefie ena sama in sicer tista z najviSjo prioriteto ali z najdaljSira flasom dakanja. Operacije uait so edine operacijet ki se sraejo iizvajati paralelno z drugimi operacijani. honitorske procedure ne smejo •nestandardnih zunanjih procedur« Se lokatne procedure drugih monitorjev. j j klicati manj pa j jMonitorji sicer zdrulfijo sinhron izac i jo s podatkii na katere se nanaSat vendar oiora programer ffe vedno pisati monitorske procedure s klasiflnimi jezikovnimi sredstvii iz katerih ni razvidnoi kaj pravzaprav i"el i . Kadar uporabljajo procesi skupne sprementjivkei je vzajemno izkljufievanje pogosto samo tehnifino vpraSanjei ki le v primerui da gre za golo dodeljevanje virovi predstavlja bistvo dogajanja. V vseh zahtevnejSih apljkacijah je namen skupnlh spreroenljtvk koounikaoija oed procesii ki aorajo brati in pisati vrednosti spremenljivk v dolotfenem zaporedju. Prograraer potrebujB jezikovno sredstvoi s katerira ba ta zaporedja opisal. ReSitev sta podala Campbsll 1n Habsraann l«ta 1974 z uvedbo "opisov poti". Opts pot t )• Izrazi ki podaja vsa dovoljena zaportdja opiracij na nekem podatkovnem predmetu. Prtproste poti so cikliflnei osnovni operatorji v izrazih pa so sekvenoiranje i Izbira \n ponavljanj*. Specifikactja podatkovnaga tipa ima nasiednjo oblikoi tvce ime «• beoin opis podatkovns strukture path opis poti end onerat ion opts moifnih operacij end Izraz path fl (g* + h)l i end na primer ,op1su]e cikel« ki se obvezno zatfne z eno operacijo fi sledi poljubno Stevito ponovitev operacjje g al< ina operacija h< zakLJutfi si z eno operacijo t. Vss operacije se vzajtmno =No(f2)>= >=No(fm)>=No(fl)-n 0= • eehanizeo #<- — > # kontr.ola *- l-> #«#*#««#*»«# I I -> • uporabntjfki • —> » prooesi #- I dajanska •- akt ivnost 75 2.Uporabni£ki procesi so btokii pri katerih kontrolne inforaacije sprožfijo aktivnost. ki Jo predpiSe uporabnik. ZaStfitni raehanizmi so blokii pri katerih doloffena aktivnost .uporabniSk ih procesov sproii generiranje kontrotnih informacij. Torej ima raCunalniSki sistem povratno zanko. ' 3.Uporabni£ki proces posredno al i. neposredno izvaja tiste aktivnosti. v katerih (s staHSCa uporabnikov) naslopa kot subjekt. ZaSBitni mehanizem nadzoruje oz.. izvaja tiste aktivnosti i v katerih njegov podatkovni predmet nastopa kot objekt. ZaStfitni mehanizem mora predvidevati na svojera vhodu poljubno kombinacijo zahtev za izvedbo operacij nad podatki. V vsakem trenutku se lahko odloffi in sprožM izvajanje skupine zahtevi odložM skupino zahtev za dolotien fias ati skupino zahtev zavrnei s tem da generira kontrolne informacije. To pomenit da smemo v izafiflitnem mehanizmu definirati poljubno stopno paraletnosti , izvajanja operacij nad podatkovnim predmetom. ZaSiMtni mehanizem ima tudi svoje spremenljivke stanjai v katerih hrani zgodovino operacij. Ker se vsaka aktivnost ratfunalniSkega sistema odraia na vrednosti spremenl)ivki za opis odloditvene verige splofinega mehanizma za zaStfito podatkov zadnSCai da reSemoi da se mehanizem odloBa na podlagi vrednosti vseh spremenljivk v sistemu. Pri tem pa moramo vedetii da upofiteva razen vrednosti spremenljivki ki jih obravnavajo uporabnifiki procesii tucii spremenljivkei ki povedoi kateri procesi obstajajo v sistemui v kakSnem stanju foi kako tetfe realni tias in predvseroi kdo je spro^il zahtevo za izvajanje neks operacije. Identiteto procesa predstavlja njegovo lastno ime skupaj z iraeni vseh prednikov. Ves tias zanemarjamo važno dejstvoi da pomeni klicanje procedure za operacijo nad podatki komunikacijo med uporabnifikim procesom in zaStJitnim mehan i zmom. Komun i kac i j a poteka seveda preko skupne spremenljivkei ki jo tudi nadzoruje zaSCitni mehanizem itd.. Vedno pridemo do komunikacije na nekem ni2)em nivojui za katero smemo reSii da je že zadovoljivo realizirana. Morda se komu zdi trditevi da je zafifiitni mehanizera procesi preozka. Vendar pri tem ne mislimot da ima zaSCitni mehanizem v sistemu nujno enak poloilaj kot uporabniSki procesi. Proces nam pomeni le ime za spreminjanje skupine spremenLjivk v odvisnosti od stopenjske spremenljivke - reatnega oz. ratfunalniSkega tiasa. Od teh spremenljivk so le nekatere iz uporabni£kega podrofijai torej deklarirane s progr^amom. Zato sei kot srao ie reklii zaSfiitni mehanizern Cvsaj v nekaterih jezikih) ne pojavlja v programu kot deklaracija procesai temvetf • kot del deklaracije pripadajofie podatkovne strukture. Ko pa prevajalnik jezikovni konstrukt realizirai dejstvai da je zaSCitm mehanizem proces aLi ( v primeru« da definiramo paratelne operacije) celo druifina procesovi ne moremo zan i kat i. Detovanje za#0itnega mehanizma se kai^e v dveh f azah: l.Med prevajanjem programa kot zaffflitai da ne zahtevamo operacij« ki nad zaSfiiteno podatkovno strukturo niso definirane• ati da eksplicitno ne zahtevamo nedefiniranih paraleLnost i. 2.Med izvajanjem programa kot zakasnitev ali zavrnitev operaciji ki niso takoj izvedljive zaradi dinamike celotnega sistema. ki iz samega programa ni razvidnai ker prevajalnik normalno ne izvaja kompletnega vrednotenja tfasovnih razmer (kar bi biVo skoraj nemogoBe ali neekonomitfno). «e sme zaSCitni mehanizem uporabljati Le svoje lokatne in globalne spreraenljivke. smo pri definiciji bolj kompleksnih operaci] prisiljeni zdruifevat i veti podatkovnih predmetov v enega. Opis dovoljenih zaporedij operacij postane zelo napregledent ker zageitni mehanizem nadzoruje veB kot eno funkoijo sistema ali pa se na vmesniku zafifiitni mehanizem - uporabnifiki prooesi pojavljajo operacije z razlifino stopnjo kompleksnosti. To ne pomenii da prostor podatkovnih predmetov hierarhitfno fiirimoi ker predroetii ki jih zdruSMmoi izginejo. Boljfie rezultate dobirooi fie zafiBitneniu mehanizmu dovolirao uporabo tudi tistih spremenljivki ki jih SSitijo drugi zaSCitni mehanizmi. Pridemo do tegai da se zaSCitni mehanizem pojavlja kot enakovreden partner uporabniSkih procesov na vhodu podatkovnih predmetov. Edina razlika raed zafiBitnimi mehanizmi in uporabnifikimi procesi je ta» da so zafitfitni mehanizmi deklarirani kot pasivni procesii ki tetfejo samo takrati kadar skuSajo uporabniSki procesi izvesti_neko operaoijo nad njihovim podatkovnim predmetom. V sistemu je dovoljeno dinamiCno generiranje procesov. Dovolimo še dinamitfno generiranje novih podatkovnih predmetovi pa ni vefl nobene ovirei da ne bi pasivnih in uporabni^kih procesov obravnavali kot enotno vrsto procesov v sistemui le da imajo pasivni procesi posebno nalogo. Dovoljeno naj bo tudi spreminjanje in ukinjanje podatkovnih predmetov in njihovih zafifiitnih mehanizroov. Spreminjanje lastnosti prostora podatkovnih predmetov sme zahtevati vsak proces v sisteroui ne glede na toi ali je pasiven ali aktiven- (uporabniSki). Sistemski program sme izvesti zahtevo po spremembi le v primerui da so izpoLnjeni pogoju zaSdite prostora podatkovnih predmetov. Procesi ki zahteva generiranje novega predmetai mora navesti naslednje podatke: -katere spremenljivke bo vkljufiil novi .podatkovni predmet. Vse spremenljivke morajo biti globalnei torej izven vseh obstojefiih od uporabnika definiranih podatkovnih predmetov. Smisel ima tudi toi da predmet ne vsebuje nobenih lokalnih spremenljivk. V tem primeru ga generiramo samo zaradi implementacije bolj kompleksnih operaci) nad spremenljivkami v drugih podatkovnih predmetih. -katere globalne spremenljivke bo naslavljal zaStfitni mehanizera novega predmetat -katere tuje podatkovne predmete bo naslavljajl za^tfitni mehanizem in kakSne operacije bo izvajal na njihi -katere operacije nad novim podatkovnim predmetom naj sestavljajo vmesnik podatkovni predraet - okoljet -kakSna so legalna zaporedja operacij nad podatkovn1m predmetom in pod kakSnimi pogoji. Za^tfitni mehanizem je procesi ki sme posegati v tuje podatkovne predmete med odtotanjem in med izvajanjem definiranih operacij. Tako se zgodii da procedure enega zaStfitnega mehanizma klifiejo procedure drugih zaSCitnih mehanizmov in operacije na veesniku z okoljem posredno posegajo tudi v druge podatkovne predmete. Zato niti ni veff nujno, da je legalno zaporedje operacij nad enim podatkovnim predmetom popolno v tem smisLui da bi zafifiitni sistem reSeval vse probleme sinhronizacije procesov - uporabnikov na predmetui ki ga nadzoruje. tfe na tistih odsekih zaporedij' ki Se niso popolnii ne dovolimo direktnega dostopa uporabnikov in vkljufiimo pred vhod predmeta drug podatkovnt predmet oz. njegov 76 za£01tnt mehaniz*flt st uporabnikov* zahtivt vetfkrat filtrirajo. Tako dosetfemoi da zahtevst kl so na neken vhodu prepovedane tn jih vhod nt zna tztoflitii fUtrira ftlter pred tem vhodon in prepovedane zahteve (npr. interferirajofft paralelne operaoije) se nikoli ne pojavijo. Prograoerju ni veft treba dtrektno graditi koapleksnih podatkovnih struktur in zaStfitnih mehantzmovi gradi jih hierarhitfno od spodaj navzgor ali oelo rekurzivno iz bolj enostavnih gradnikov. Za£01tni mehanizem izvaja definirane operacije kot podprograme ali kot posebne procese. Zato za vsako spremembo obstojeCih podatkovnih predmetov veljajo pravila za spreminjanje aktivnih podprograaov oz. procesovt ki so fflorda ofietje ali sinovi drugih procesov in podprogramov. Poseben jezik za opis legalnih zaporedij operaciji kakrSnega predstavljajo znani izrazt za opis potii je odvetfi ker se pri velikih zaStfitnih mehanizmih razraste v prav tako kompteksnosti ki je znafiilna za prograoske jezikei s katerimi opisujemo uporabniSke procese. Zato naj vse doga i an i e v_ sistemu opisuie enoten iez 1k po zgledu jezika ADA. fle obravnavano zaSfiitne mehanizme kot posebnostii ki jih Sele pri prevajanju realiziramo z normalno programsko kodoi potrebujemo tudi posebne tehnike za preverjanje pravilnosti delovanja paraLelnih procesov. Naravo objekta za kontrolo sinhronizacije karakterizira invariantna relacija oed spremenljivkamii ki je izpolnjena vednoi kadar element ni aktiven. To relacijo uporabljamo skupaj z drugimi relaoijami v sistemu za formalno' dokazovanje pravilnosti algoritmov. Aktivnost objekta za sinhronizacijo precizno. opiSemo Se s temi da navademo pogojei ki morajo biti izpolnjenii preden se Lahko izvede dana operacija. Za objekt posebne vrstei ki ga nanovo vpeljemo v jeziki moramo odkritt njegovo invariantno relacijoi kar ni zmeraj enostavno. • Res pa je> da.pozneje invariantne rslacije ni treba ponovno iskatii medtem ko moramo objekte za kontrolo sinhronizacijei ki nlso tipiziranii opisovati sproti. Vendar to n\ problemi He . je objekt za kontrolo sinhronizacije zgrajen po enakih zakonihi kot ostali objekti v sistemu. S tem se ne ravna po standardu za posebno podroCje sinhronizacijei ampak pb standardu za celoten sistem. Podrobna zgradba ' objekta za slnhronizac i jo ni vnaprej zri.a"hai znaifB~pa~*o" metode za konstruiranje objektai ki so povsem spVošne. laStiitni mehanizem v modernem programskem Jeziku je proces kot vsak drug< ioia skupino lokalnih podatkovi ki jih SCiti. \n skupino procedur za dostop do podatkovi ki jih drugi procesi ktitfejo preko procesnih vhodov. flazen podatkov z dinamitfno zafiSito pa Se vedno &bsiajaji> podatki s statiflno zaStfitoi pri katerih predpisu)e 1n nadzira deljivost ali inedeljivost operacij implicitM sistemski proces. Tako sploh ne moremo veS govoriti o direktnem dostopu do spremenljVvk in sraerao znotraj rafiunalniSkega sistema vse spremenljivke. k1 jih uporabljamo, vkljuSiti v razlitfne funkcijske bloke. Vsa sinhronizacija se pravzaprav odvija implicitno s sistemsko kontroto prooesnih vhodov po principu rendez-vous-ai klicani ali kliSofii proces avtoraatiflno tfakata drug na drugega v dolofienih tofikah algoritma. ZaSHMni mehanlzemi ki je impl emen t iran kot normalen procesi lahko predstavlja aktivni filter vhodnih klicev. Vse do sedaj omenjBne vrste zaStfitnih mehanizmov \ so lmete edino funkoljoi da zahteve za izvedbo operacije ati sprejmejo ali zavrnejo ali zakasnijo. Ko je nehanizen neko zahtevo sprejeli je operactjo vedno tzvedel na enak natftm neodvisno od stanja sisttna. Seveda bi v procedure« ki optsujejo izvajanje operacijt lahko vktjueili upoStevanje stanja sistemai vendar je bil osnovnl namen tai da uporabnikova zahteva kadarkolt sprozM isto proceduro. ZaSCitni mehanlzera )e bU izkljuffno pasiven filter. ZaStfitni mehanizenn ki JB normalen procesi sprejema enake zahteve na vcfi razlitfnih prooesnih vhodihi v odvisnosti od tegai do katerega vhoda je prjteket algoritem zaSCitnega mehantzma. Vsak procesni vhod predstavlja stavek when klio sprejet do akcija in vsak procesni vhod ima svojo lastno posledico klica. ZaSffitni oiehanizen ni vefl pasivnf filten ki spuStfa uporabnikove klice lokalnih procedur v notranjostt temvefi te kUce aktivno preoblikuje. Prav tako je lahko zaSSita lokalnih spremenlj1vk samo stranska naloga procesa. Aktivni filter ni samo nadzornik uporabnikove aktivnostit ampak servisni proces. Razvoj jezikovnih eleoientov za sinhron izaci jo oz. komunikacijo med paraLeLnimi procesi je 5 tem dosegel tisto toCkoi ko se obravnavano pošebno podroffje vktjutfi v jezik na tako popoln natfini da neha biti posebnost in ga ni vefi treba principielno raziskovati z jezikovnega siaiiSda. Oblikovalci jezikov za paraLelno programiranje se ukvarjajo v glavnetn s podrobnostimi izvedbe jn manjeimi spremebami jezikovnih konstruktovi ki ne vplivajo na bistvo refiitve. Oglejmo s\ Se problem s i nhron i zac i i e procesov < k i i ih impli c i t no soroiaio proorami Y 1BZ i k ih za nepostopkovno programiran i e. Tudi nepostopkovne programe sestavljajo zaporedja ukazov in sicer za vna£anje novih dejstev v bazo znanjai za spreminjanje starega znanja .ter za iskanje podatkov in izpeljevanje logifinih sklepov na osnovi znanja^ v bazi. Sistero pogosto realiziramo kot pomniLnik brez vnaprej deklarirane logiffne strukturei kjer so podatki spravljeni v obliki sintaktifinih konstruktov. Osnovni proces v sistemu je administrator bazei ki sprejema ukaze uporabnikov in za procesiranje vsakega ukaza sproii poseben proces. Procesi posegajo v bazo znanja kot pisci ali tfUalci. ZaSfiitni mehanizem baze dodeli vsakemu piscu del praznega pomniIniSkega prostora ali obstojefli sintaktifini konstruktt ki ga proces ie\.\ Spremeniti. Proces - pisec je izkLjutfni lastnik dodeljenega objektai dokler n» konCa dela. Procesi smejo prosto brati vst konstrukte v bazi znanjai ki niso Last procesov - piscevi ker samo ti konstrukti predstavljajo veljavno znanje. Citalci s* obrafiajo na zaSfiitni mehanizem bazet kadar ištlejo v bazi konstrukte z dano strukturo. ZaSflitni mehanizem mora sinhron1zirati procesi takoi da ne dovoli spreninjanja tistih konstruktovi ki jih fe bere kak proces. in branja tistih konstruktov« ki jih kak proces Ye spreminja. Imamo klasitfen priraer pisciv tn ffitalcev. Ukrepi proossovi kt uporabljajo znanje \i bazei so posledice prsbransg* znanja. Zato zahtevamo tudi tu ' dolofleno stopnjo nedeljtvosti vzroka in posttdice. Baza znanja naj bi bila slika nektga svcta. Ne glede na toi ali ji ta abstrakteni sroemo refiii da se spreminja v odvisnosti svet realtn ali ovlotno znanj* od stopenjske spremenj l jivke in logika sveta pridptsujet da se morajo nekateri elementt znanja sprtnaniti to pomenii da raora staro znanje v 77 trenutku preiti v novo. Zaradi vsaj delno sekvenfinoga delovanja raffunalnika pa to n1 res in obstaja nevarnostt da bo uporabnik bral kombinacije eleoentov znanjai ki se v svetui ki ga opisuje baza znanja« ne bi pojavile. Zato je vaina sinhronizacijska naloga zaSttitnega oehanizma bazei da siraulira realno spreminjanje sveta \n prepreSi dostop uporabnikov baze do podatkovi ki se spreminjajoi oed trajanjem prehodnega pojava. Pri tem se naloga ne ujema popolnoma z blokiranjem (Mtalcev, enega sintaktifinega konstrukta med njegovim sprsminjanjem. Obstajati oora ukaz za blokado poljubne skupine sintaktitfnih konstruktovi dokler vsi ne dobijo nove vrednosti.Procesi - uporabniki baze znanja morajo za smiselno upoštevanje bLokade lotfiti aned primeromai da je neka izjava v bazi žanikana ali da v bazi ne obstaja niti trdilna niti nikalna oblika izjave. Ce izjave ni v bazii mora proces avtomatitfno ponovno preiskovati bazo do preteka dovoljenega fiasa iskanja 1n Sele nato podati uponabniku kontfno porotfilo. Oznatfevanje sintaktiflnih konstruktovi ki naj se navidezno spremenijo istotfasnoi in nj.ihovo vk t utfevan j e v bazo po spremeinbi je nedeljiva operacijai med katero procesi lahko spreminjajo konstrukte« ki so jih te prej rezervirali kot piscii ni pa dovoljeno branje ie oznaKenih konstruktov. Sinhronizaoijske potrebe v sistemu Se narastejoi Be en ukaz uporabnika sproii izvajanje vefiih procesov. Kot vidimoi se kaže Vpostopkovnost nepostopkovnih programskih jezikov kot komunikacija sištema \n uporabnikai impUcitno pa tudi med izvajanjem programov. Postopkovni in nepostopkovni jeziki se po sintaksi bistveno razlikujejo. S postopkovnimi eksplicltno opisujemo procese v rafiunaLnikui z nepostopkovnimi samo dektariramo relacije med podatki in prepustimo gradnjo procedur in organizacijo procesov za iskanje odgovorov na na£a vpraSanja sistemu. Med samim izvajanjem 50 problemi koounikacije in sinhronizacije v obeh primerMh enako pomembni in se reSujejo z enakimi pri stopii le da se pri nepostopkovnem 'programiranju ne odrafajo na jeziku in ker iprocese organizira ststeui so procesni sklopi Ipreprostejii in manj raznoliki. 3. Sktep Paralelno proceslranje se podreja majhni skupint teoeljnih zakonitosti. ki jih brez teiav odkrtjemo in opiSemo. Kljub temui da je bit razvoj .jezikovni h elementov za opis sinhronizacije paralelnih procesov precej poCasem je danes dosegel zadovoljivo stopnjo. Zato se je te«i*ffe dela preneslo na optirairanje programov v roultiprocesnem okolju ob podpori visoklh programskih jezikov. >,. Viri N.Mirth Toward a Discipline if Real-Time Programmingi Comm. ACM 20 (1977). N0.81 377-5B3 . N.Uirth MODULA! A Language for Hodular Multiprogramraingi Softuare Praotioe and Eiperienoe 7 (1977). 3-35 E.U.Dijkstra Co-operating Secjuential ProcBSsesi . Programming Languages> ed. F.Genuysi Acadenic Pressi 1968 . , C.A.fi. Hoare Monitorst An Operating System Structurtng Concepti Comm. ACM 17 (197^). 10i 349 - 537 S. Andler Synchronization Primitives and the Ver i f icat ion of Concurrent Programsi Carnegie-Hellon University N.Eieli. F.Prijatelj Prograoiranje sprotnih in vgnezdenih, sistemov: . Procesi v ADI. Infornatica 198t/2