Előző
A kiterjesztett PRAM-modell felhasználásával az operációs rendszer szintjén összetettebb szinkronizációs eszközök hozhatók létre. Ezek közül a következőkben a szemafort, az erőforrást és az eseményt tárgyaljuk.
Szemafor
A szemafor, mint univerzális szinkronizációs eszköz használatára Dijkstra tett javaslatot 1965-ben. A szemafor egy speciális változó, amelyet csak a hozzá tartozó két, oszthatatlan művelettel lehet kezelni.
Az általános szemafor esetén a szemaforváltozó egész (integer) típusú. A két művelet elnevezése többféle lehet, például Belép és Kilép, vagy Vár (Wait) és Jelez (Signal). Leggyakrabban azonban az eredeti definícióban szereplő jelölést (P és V) használja a szakirodalom, így a továbbiakban mi is ezt követjük.
A P(s) művelet hatása egyenértékű azzal, mintha a folyamathoz tartozó logikai processzor a következő programrészletet hajtaná végre oszthatatlanul (definíciós program):
while s<1 do üres_utasítás;
s:=s-1;
(az üres_utasítás művelet nélküli továbblépést jelent, s pedig a közös memóriában lévő szemaforváltozó)
A V(s) művelet definíciós programja:
s:=s+1;
Hangsúlyozni kell, hogy mindkét művelet oszthatatlan, valamint azt is, hogy a szemaforváltozó más utasításokkal (írás, olvasás) nem érhető el. Azt is meg kell jegyeznünk, hogy a definíció a véletlenre bízza, hogy a várakozó folyamatok közül melyiknek sikerül a továbbhaladás, amikor egy másik folyamat V műveletet hajtott végre.
Vegyük észre, hogy az általános szemafort k kezdőértékre állítva a rendszer k darab P műveletet végrehajtó folyamatot enged tovább, a továbbiakat azonban várakoztatja. Ezután csak akkor enged tovább folyamatot a P rendszerhívásról, ha más folyamat V műveletet hajtott végre. Ezzel egy olyan általánosított kritikus szakaszt hoztunk létre, amelyiken belül egyidejűleg k darab folyamat tartózkodhat.
Precedencia és kölcsönös kizárás megvalósítására alkalmas a bináris szemafor, amelynek szemaforváltozója csak két értéket vehet fel (0 és 1, vagy foglalt és szabad). Kölcsönös kizárásra 1 kezdőértékű bináris szemafor használható, amelyre a kritikus szakaszba belépni kívánó folyamat P műveletet, a kritikus szakaszból kilépő pedig V műveletet hajt végre. Precedencia megvalósításához 0 kezdőértékű bináris szemafor használható. Az előbb végrehajtandó műveletet követően a folyamat V műveletet hajt végre a szemaforra, a másik folyamat pedig a később végrehajtandó művelet előtt P műveletet.
Erőforrás
Az erőforrás, mint szinkronizációs eszköz egy logikai objektum, amelyet egy folyamat lefoglalhat és felszabadíthat. A lefoglalás és a felszabadítás között a folyamat kizárólagosan használhatja az erőforrást, azaz erre a szakaszára és más folyamatok ugyanezen erőforrásra vonatkozó foglalási szakaszaira kölcsönös kizárás valósul meg. Az erőforrásokat egy név vagy egy sorszám azonosítja. A programozók megegyezésén, illetve rendszertervezői döntésen múlik, hogy egy-egy erőforrást milyen tartalommal használnak. A Lefoglal(<erőforrás>) és Felszabadít(<erőforrás>) műveletek egyenértékűek egy s bináris szemaforra kiadott P(s) és V(s) műveletekkel. Mint a szemafornál sem, az erőforrásra várakozó folyamatok esetén sem meghatározott, hogy melyikük kapja meg a felszabaduló erőforrást, és haladhat tovább. Csak az biztos, hogy egyetlen ilyen folyamat lesz.
Esemény
Az esemény egy pillanatszerű történés a rendszerben, amelyre folyamatok várakozhatnak. Az esemény bekövetkezése valamennyi rá várakozó folyamatot továbbindítja. Az eseménnyel így egy összetett precedencia valósítható meg, ahol több, különböző folyamatokban elhelyezett műveletre ugyanazt az előzményt írjuk elő. Két folyamat esetén egy esemény jelzése és az arra való várakozás egyenértékű egy szemaforra kiadott V, illetve P műveletekkel. Több folyamat esetén azonban lényeges különbség, hogy a szemaforra kiadott V művelet hatására csak egyetlen várakozó folyamat indulhat tovább, míg az esemény bekövetkezése valamennyi várakozó folyamatot továbbindítja. Míg a szemafor és az erőforrás felszabadítása az objektum állapotában megőrződik akkor is, ha nem várnak rá, és egy későbbi foglalás várakozás nélkül sikeres lesz, az esemény jelzése általában hatástalan, ha nincs rá várakozó, csak a várakozás megkezdése után bekövetkező esemény indít tovább folyamatot.
A bemutatott szinkronizációs eszközök közül a szemafor és az erőforrás több várakozó folyamat közül egy továbblépését teszi lehetővé, azonban ennek kiválasztását a véletlenre bízza. Ez a megoldás sok esetben nem kielégítő. Az egyik fő érv a megoldás ellen, hogy nincs garancia arra, hogy minden várakozó véges időn belül tovább tud lépni. Egy másik – az előzőnek egyébként ellentmondó – érv a véletlenre hagyatkozás ellen, hogy amennyiben fontossági sorrendet (prioritást) állítunk fel a folyamatok között, a véletlenszerű továbbindítás ezt nem érvényesíti. Felmerül tehát annak az igénye, hogy a választás meghatározott algoritmus szerint történjen. Ennek megoldása a várakozó folyamatok sorbaállítása, és ütemezett továbbengedése. A szemaforokhoz és erőforrásokhoz így várakozási (ütemezési) sorokat rendelhetünk, amelyeket a rendszer meghatározott (ütemezési) algoritmus szerint kezel. A leggyakoribb az érkezési sorrend szerinti (FIFO), illetve a prioritásos ütemezés.
Előző