Ugrás a tartalomhoz

Operációs rendszerek mérnöki megközelítésben

Benyó Balázs, Fék Márk, Kiss István, Kóczy Annamária, Kondorosi Károly, Mészáros Tamás, Román Gyula, Szeberényi Imre, Sziray József

Panem Kiadó

2.2. Folyamatokból álló rendszerek

2.2. Folyamatokból álló rendszerek

Egy számítógéprendszeren belül általában egyidejűleg több folyamat van jelen. Ezek a folyamatok különbözőképpen keletkezhettek és különböző kapcsolatok lehetnek közöttük. Ha a rendszer célja csak a hatékony erőforrás-kihasználás, a folyamatok kezelése az operációs rendszer belügye maradhat. A felhasználó (az egyszerű felhasználó és a programfejlesztő) nem is találkozik folyamatokkal, számára csak futtatandó programok, esetleg jobok léteznek. A folyamatkezelésben csak az operációs rendszert készítő programozók és a rendszermenedzserek érintettek. Más a helyzet, ha a felhasználó is létrehozhat olyan folyamatokat, amelyek együttműködve oldanak meg egy feladatot. Ilyenkor a kezelői és programozói felületen is meg kell jeleníteni a folyamatkezelést, valamint a folyamatok együttműködésének szervezését segítő funkciókat. Azokat az operációs rendszereket, amelyek a felhasználó számára is lehetővé teszik a folyamatkezelést, multitaszkos rendszereknek szokták nevezni.

2.2.1. Folyamatok létrehozásának indokai

Láttuk, hogy történetileg a multiprogramozás kialakulását a processzor­ki­hasz­nálás javítása motiválta. Emellett más szempontok is indokolhatják, hogy egy rendszerben több folyamatot hozzunk létre. Melyek tehát az indokok?

  • Hatékonyabb erőforrás-kihasználás. Ez a processzorkihasználás javításának egy általánosabb megfogalmazása. A processzoron kívül le­het­nek a rendszerben más, nagy értékű erőforrások, amelyeket egyetlen folyamat csak működésének egy rövidebb szakaszában használ, a többi időben indokolt a használatot mások számára lehetővé tenni. Egy feladatmennyiség egy adott erőforráskészlettel akkor oldható meg a leghatékonyabban, ha lehetőleg minden eszköz (erőforrás) minden pillanatban valamilyen hasznos feladatot végez, és nem tétlen.

  • A feladat-végrehajtás gyorsítása. Az erőforrások hatékony kihasználása általában a feladatmegoldást is gyorsítja. Ezen túlmenően a feladatoknak kereshetjük azokat a megoldásait, amelyek párhuzamosan megoldható részfeladatokra bontják az eredeti problémát. Ha ilyenkor ezeket a részfeladatokat az erőforrások többszörözésével, valódi párhuzamossággal, folyamatokként tudjuk végrehajtani, további jelentős gyorsítást érhetünk el.

  • Többféle feladat egyidejű végrehajtása. A felhasználók számára hasznos és kényelmes lehet, ha a számítógépet egyidejűleg többféle célra használhatják (például egy hosszadalmas számítás közben szövegszerkesztés végezhető).

  • Rendszerstrukturálás. Bizonyos feladatokra könnyebb olyan szerkezetű programrendszert készíteni, amelyiken belül több folyamat működik együtt, mindegyik a feladat egy leválasztható részén dolgozik, csak meghatározott pontokon cserélnek információt. Ilyen feladatok elsősorban a valósidejű rendszerek körében fordulnak elő, ha a rendszernek a környezet többféle, egymástól függetlenül bekövetkező eseményére kell reagálnia (például irányítórendszerek, több kezelőt interaktívan kiszolgáló rendszerek).

A folyamatok létrehozása mellett szóló érvek mellett meg kell említeni egy lényeges ellenérvet is. A folyamatokból álló rendszer fejlesztése – elsősorban a tesztelés fázisában – lényegesen nehezebb és bonyolultabb feladat, mint a szekvenciális programoké. A folyamatok aszinkron futása miatt ugyanis a rendszer egy adott lefutása gyakorlatilag reprodukálhatatlan, a szisz­te­ma­tikus tesztelés és hibakeresés ezért igen nehéz.

2.2.2. Független, versengő és együttműködő folyamatok

A rendszer folyamatai egymáshoz való viszonyukat, a köztük lévő csatolás erősségét tekintve lehetnek függetlenek, versengők vagy együttműködők.

A független folyamatok egymás működését semmilyen módon nem befolyásolják. Végrehajtásuk teljes mértékben aszinkron, azaz egymással párhuzamosan is végrehajtódhatnak, de a végrehajtás egymáshoz viszonyított sebességéről semmilyen feltételezést nem tehetünk. Számunkra az ilyen folyamatok gyakorlatilag érdektelenek, hiszen ezek külön-külön, önálló programokként vizsgálhatók.

A versengő folyamatok nem ismerik egymást, de közös erőforrásokon kell osztozniuk. Versengő folyamatok alakulnak ki például egy kötegelt feldolgozást végző rendszerben, a véletlenszerűen érkező, egymást nem ismerő felhasználói jobok feldolgozásakor. Az egyes jobok részeként elinduló programok ugyanazon a számítógépen hajtódnak végre egy multiprogramozott operációs rendszer felügyelete alatt. Ezeknek a folyamatoknak nem kell tudniuk még azt sem, hogy őket multiprogramozottan fogják végrehajtani, ezért programkódjuk ugyanolyan, mintha egy soros feldolgozást végző rendszerre írták volna. A több egyidejűleg működő folyamat helyes és hatékony futtatásának problémáit az operációs rendszeren belül kell megoldani (például minden folyamatnak külön memóriaterülete legyen, a nyomtatásaik ne gaba­lyod­janak össze, lehetőleg minden erőforrás munkában legyen stb.). Ezt a bo­nyolult erőforrás-kiosztási, gazdálkodási, védelmi és koordinációs feladatot az operációs rendszereken belül gyakran együttműködő folyamatokkal oldják meg. Az operációs rendszer saját, belső folyamatait rendszerfolyamatoknak, a többit felhasználói folyamatoknak nevezzük. A korrekt és biztonságos erőforrás-kezelés a folyamatok aszinkron futásának korlátozását, szinkronizálását igényli (például, ha egy folyamat nyomtatni akar, amikor egy másik folyamat éppen összetartozó adatsorozatát nyomtatja ki, meg kell várnia, amíg a másik folyamat nyomtatóhasználata befejeződik).

Az együttműködő folyamatok ismerik egymást, együtt dolgoznak egy feladat megoldásán, információt cserélnek. Az együttműködő folyamatokból álló rendszert tervszerűen bontottuk folyamatokra, amelyektől ezért a tervező szándéka szerinti kooperatív viselkedés várható el. Ezekben az esetekben a folyamatok egymástól való védelmének jelentősége kisebb, párhuzamosan működő programrészekként szálak is alkalmazhatók. Együttműködő folyamatok esetén a folyamatok leírása és az együttműködés műveletei a programkódban is megjelennek, azaz a logikai processzor utasításkészletében szerepelnie kell az ehhez szükséges utasításoknak (például folyamat indítása, erőforrás kizárólagos használatának kérése, üzenetküldés egy másik folyamatnak stb.). Valójában ezeket a műveleteket az operációs rendszer hajtja végre. Az együttműködéshez szükséges funkciókon kívül természetesen a versengő folyamatoknál már említett erőforrás-kezelési feladatokat is el kell látnia az operációs rendszernek.

Együttműködő folyamatok munkájukat információcsere útján tudják összehangolni. A cserélt információ esetenként egyetlen bitnyi, csupán jelzés jellegű, máskor akár több megabájt is lehet.

2.2.3. Folyamatok születése és halála

Mindeddig nem foglalkoztunk azzal a kérdéssel, hogy hogyan jönnek létre és hogyan szűnnek meg a rendszert alkotó folyamatok. Vizsgáljuk most ezt a kérdést az egyszerűség kedvéért egyetlen fizikai processzort tartalmazó, azaz multiprogramozott rendszerre.

A Neumann-elven működő számítógépek soros feldolgozást végeznek. Ami­kor egy ilyen számítógépet bekapcsolunk, elindul egy rendszerépítési folyamat (boot, inicializálás). Ezt egy ősfolyamatnak tekinthetjük, amelyik létrehozza a rendszert alkotó többi folyamatot. A rendszerépítés eredményeként már egy működésre kész operációs rendszer alakul ki, amelyik maga is több folyamatból állhat (rendszerfolyamatok).

A működésre kész operációs rendszerben például interaktív kiszolgálás esetén minden terminálhoz tartozhat egy rendszerfolyamat, amelyik felhasználói parancsokat fogad és hajt végre. Kötegelt feldolgozás esetén elindulhat egy jobkészletet kezelő folyamat, amelyik jobok végrehajtását kezdi meg és jobonként egy újabb folyamatot indít. Valósidejű rendszer esetén az operációs rendszer saját felépülése után létrehozza és inicializálja a felhasználói rendszert alkotó folyamatokat.

A rendszerfolyamatok tehát újabb, felhasználói folyamatokat hoznak létre, a felhasználói folyamatok pedig – bizonyos típusú rendszerekben – maguk is létrehozhatnak további felhasználói folyamatokat a logikai processzor megfelelő utasításának végrehajtásával (például fork, create).

A folyamatok általában saját jószántukból fejezik be működésüket a logikai processzor megfelelő (például exit) utasításának végrehajtásával. Bizonyos esetekben (például működési hibák) azonban szükség lehet arra, hogy más folyamat szüntessen meg egy folyamatot (például kill).

Azokat a rendszereket, amelyek működése során – a felépülés és inicializálás kezdeti szakaszától eltekintve – nem jönnek létre és nem szűnnek meg folyamatok, statikus rendszereknek nevezzük, szemben a dinamikus rendszerekkel, amelyekben működés közben bármikor születhetnek és megszűnhetnek folyamatok.

A folyamatok eredetét szükség esetén a szülő–gyermek viszonyokkal, azaz egy fa struktúrával írhatjuk le (processzgráf). Dinamikus rendszerben a fa természetesen folyamatosan követi a folyamatok születését és halálát. Sok operációs rendszer a szülő–gyermek viszonyokra építi erőforrás-gazdálkodási és jogosultsági filozófiáját. Ennek egyik megközelítése a hierarchikus erőforrás-gazdálkodás, amikor a gyermek folyamatok csak a szülő erőforrásaiból részesülhetnek és nem létezhetnek önállóan, csak amíg szülőjük is létezik. Egy másik megközelítés a globális erőforrás-gazdálkodás, amikor a rendszer valamennyi folyamata létrejötte után egyenrangú, önálló szereplő, és versenyezhet a teljes erőforráskészletből való részesedésért.

2.2.4. Folyamatok együttműködése

A folyamatok együttműködése információátadással valósul meg. A folyamatok közötti információcserének két alapvető módja alakult ki, a közös memórián keresztül, illetve az üzenetváltással történő adatcsere (később mindkettőt részletesen tárgyaljuk). Valamennyi konkrét megoldás – a legegyszerűbb, processzorok közötti jelzőbittől a nagy adatbázisokon végzett tranzakciókig vagy a földrészeket átfogó hálózati alkalmazásokig – erre a két alapsémára vezethető vissza.

2.2.4.1. Együttműködés közös memórián

Közös memórián keresztül történő adatcsere esetén az együttműködő folyamatok mindegyike saját címtartományában lát egy közös memóriát. A közös memória elérését (a közös memória címtartományára kiadott olvasás vagy írás művelet végrehajtását) valamilyen adatátviteli rendszer (kapcsolóhálózat, sín stb.) teszi lehetővé.

A folyamatok párhuzamos futása miatt a közös memóriát egyidejűleg több folyamat is írhatja, illetve olvashatja. Ilyen esetekre a RAM-modell nem határozza meg a memória működését, ezért a közös memóriát a RAM-modell kiterjesztésével kapott PRAM (Pipelined Random Access Memory) modell szerint kell kialakítani.

2.1. ábra. ábra - Folyamatok együttműködése PRAM szerint működő közös memórián

Folyamatok együttműködése PRAM szerint működő közös memórián


A PRAM-modell szerint működő memóriát több processzor írhatja és olvashatja egyidejűleg. Az olvas és ír műveletek egyidejű végrehajtására a RAM-modellhez képest az alábbi kiegészítések vonatkoznak:

  • olvasás-olvasás ütközésekor mindkét olvasás ugyanazt az eredményt adja, és ez megegyezik a rekesz tartalmával,

  • olvasás-írás ütközésekor a rekesz tartalma felülíródik a beírni szándékozott adattal, az olvasás eredménye vagy a rekesz régi, vagy az új tartalma lesz, más érték nem lehet,

  • írás-írás ütközésekor valamelyik művelet hatása érvényesül, a két beírni szándékozott érték valamelyike írja felül a rekesz tartalmát, harmadik érték nem alakulhat ki.

Ezek a szabályok lényegében azt jelentik, hogy az egyidejű műveletek nem interferálhatnak, azaz nem lehet közöttük zavaró kölcsönhatás. Hatásuk olyan lesz, mintha valamilyen előre nem meghatározható sorrendben hajtódnának végre (ezt tükrözi a pipelined elnevezés, arra utalva, hogy a memóriához egy sorosítást végző csővezetéken jutnak el a parancsok). Másként fogalmazva, ezek a műveletek a modell szintjén oszthatatlanok (atomiak).

A közös memória használatával történő adatcsere helyes lebonyolításához a PRAM-modell szerint működő memória mellett a folyamatok működésének összehangolása is szükséges (például az adat fogadója akkor olvassa el az adatot, ha a küldő már elhelyezte azt; összetett adatok átadásakor félig átírt rekordot ne kezdjen olvasni a fogadó stb.). Ez ismét a folyamatok szabadon futásának (aszinkronitásának) korlátozását jelenti, azaz szinkronizációt igényel.

2.2.4.2. Együttműködés üzenetváltással

Üzenetváltásos adatcsere esetén a folyamatoknak nincs közös memóriája. Az adatátviteli rendszer most a logikai processzorokat kapcsolja össze. Rajta keresztül a folyamatok üzeneteket tudnak küldeni, illetve fogadni. Az üzenetküldésre, illetve fogadásra a folyamatok logikai processzorainak utasításkészletében megfelelő utasítások állnak rendelkezésre. Legyenek ezek a Küld (Send) és a Fogad (Receive) műveletek.

A Küld(<cím>,<folyamat>) művelet végrehajtásakor a műveletet végrehajtó folyamat elküldi a saját memóriájának megadott címén tárolt adatot a megadott folyamatnak, a Fogad(<cím>,<folyamat>) művelet pedig végrehajtásakor a megadott folyamattól érkező üzenetet a saját memória megadott címén tárolja.

2.2. ábra. ábra - Folyamatok együttműködése üzenetváltással

Folyamatok együttműködése üzenetváltással


Míg gyakorlatilag valamennyi közös memóriás információcserét alkalmazó megoldás a PRAM-modellre alapul, az üzenetközvetítésre nincs egyetlen elfogadott modell. Ha csak a működés logikájával foglalkozunk, és olyan lényeges kérdéseket nem is érintünk, mint az átviteli sávszélesség, az összeköttetés megbízhatósága, az üzenetszerkezet, az átviteli közeg sajátosságai, a kapcsolatépítés esetleges dinamikája, akkor is számos tulajdonságot találunk, amelyekben az egyes megoldások eltérhetnek, és amelyek ismerete fontos a felhasználók (rendszertervezők, programozók, üzemeltetők) számára. A folyamatok kommunikációs műveleteinek tulajdonságaival ezért külön pontban foglalkozunk.

2.2.5. Folyamatok szinkronizációja

A közös erőforrások használata, valamint a folyamatok közötti közös memóriás információcsere biztonsága és helyessége érdekében a folyamatok aszink­ron „szabadonfutását” esetenként korlátozni kell. A művelet­vég­re­haj­tás­ra vonatkozó időbeli korlátozásokat nevezzük szinkronizációnak. A korlátozások alapesetei a következők:

Kölcsönös kizárás (mutual exclusion)

Több folyamatban lehetnek olyan utasítássorozatok (kritikus szakaszok), amelyek egyidejű (konkurens) végrehajtása nem megengedett, azaz ezeknek az utasítássorozatoknak a végrehajtása kölcsönösen ki kell, hogy zárja egymást.

Kölcsönös kizárás szükséges jellegzetesen a megosztottan használt erőforrásokon végzett oszthatatlan műveletsorozatok esetén (például, ha egy folyamat megkezdett egy nyomtatást, ki kell zárni, hogy más folyamat közbenyomtathasson egy-egy sort, vagy a közös memóriában tárolt, összetett adatszerkezetek kezelésekor, az adatbázis-tranzakciók végrehajtásakor meg kell akadályozni, hogy egyes folyamatok félig átírt, inkonzisztens rekordokat lássanak). Ezeknek a műveletsorozatoknak az idejére az adott erőforrás használatára kizárólagosságot kell biztosítani a folyamat számára.

Kicsit pontosabb fogalmazásban: egy folyamatokból álló rendszerben egy K kritikus szakasz folyamatok végrehajtási szakaszainak egy Sk halmazát jelenti, amely Sk halmaz bármely két sk,i és sk,j elemének átlapolt végrehajtása tilos. Ha egy folyamat sk,i Є Sk szakaszának végrehajtása megkezdődik, azt mondjuk, hogy a folyamat belépett a K kritikus szakaszba. Hasonlóan sk,i végrehajtásának befejeződésekor azt mondjuk, hogy a folyamat kilépett a K kritikus szakaszból. Egy folyamat csak akkor léphet be a K kritikus szakaszba, ha egyetlen más folyamat sem tartózkodik éppen K-ban. Ellenkező esetben meg kell várnia, amíg a bent tartózkodó folyamat elhagyja K-t. Ha egy folyamat elhagyja K-t, az esetleges belépésre várakozó folyamatok közül egyetlen léphet be K-ba.

Fentiekből következik, hogy egy rendszerben több, egymástól független kritikus szakasz létezhet. Minden kritikus szakaszhoz az egymást kizáró végrehajtási szakaszok egy halmaza tartozik. Egy K kritikus szakaszba való belépésnek nem feltétele az, hogy más (L, M, N stb.) kritikus szakaszokban éppen tartózkodik-e folyamat és melyik. Az is lehetséges, hogy egy folyamat egyszerre több kritikus szakaszban tartózkodik (például több kizárást igénylő erőforrást használ egyidejűleg).

Megjegyezzük, hogy a folyamat szekvenciális végrehajtása miatt (a szálakat önálló folyamatnak tekintve) egy folyamaton belül a kölcsönös kizárás bármely két utasítás között teljesül, folyamaton belüli két utasítássorozat kölcsönös kizárásának előírása értelmetlen.

A kritikus szakaszokat a programozók definiálják, a belépési szándékot és a szakaszból való kilépést a kódban elhelyezett műveletekkel jelölik. Versengő folyamatok esetén ez nem más, mint kizárólagos használat kérése, illetve ennek feloldása bizonyos eszközökre [például Lefoglal(nyomtató), Fel­sza­ba­dít(nyomtató)]. A műveletek rendszerhívásokat jelölnek, és futási időben az operációs rendszer hozza meg a döntést a folyamat továbbengedéséről vagy várakoztatásáról. Együttműködő folyamatok elvileg bármilyen egyeztetett megoldást használhatnának a probléma megoldására. A gyakorlatban számukra is kialakultak az operációs rendszer szinkronizációs rendszerhívásai, amelyek már nem kötődnek konkrét eszközhasználathoz, csak koordinációs szerepük van (lásd később).

Egyidejűség (randevú)

Különböző folyamatokban elhelyezett műveletekre előírhatjuk, hogy azok várják be egymást és „egyidejűleg” hajtódjanak végre. Kellően finom időléptékben természetesen az egyidejűség értelmezése problematikus. Az egyidejűség pontosabban úgy értendő, hogy egyik folyamat sem léphet túl a benne egyidejű végrehajtásra kijelölt végrehajtási szakaszon mindaddig, amíg valamennyi többi folyamat meg nem kezdte a saját kijelölt szakaszának végrehajtását.

Az egyidejűség tipikus alkalmazása az átmeneti tárolót nem tartalmazó adatátvitel Küld és Fogad műveleteinek végrehajtása, valamint a távoli eljáráshívás kiadása és elfogadása (lásd később).

Előírt végrehajtási sorrend (precedencia)

Különböző folyamatok kijelölt műveletei között végrehajtási sorrendet írhatunk elő. Legyen például P1 folyamat egy utasítása S1, P2 egy utasítása pedig S2. Az S1 => S2 precedencia előírása azt jelenti, hogy S1 végrehajtásának be kell fejeződnie, mielőtt S2 végrehajtása megkezdődik. Ha az egyébként aszinkron futású P1 és P2 úgy hajtódna végre, hogy S2 hamarabb kerülne sorra, P2-nek meg kell várnia, míg P1-ben S1 végrehajtása befejeződik.

A precedencia előírása jellegzetesen annak biztosítására használatos, hogy egy folyamat csak akkor kezdje felhasználni a másik folyamat által előállított adatokat, amikor azok már rendelkezésre állnak.

2.2.5.1. Megoldások a PRAM-modell keretei között (szoftvermegoldások)

A szinkronizáció igénye először a multiprogramozott operációs rendszeren belül a kölcsönös kizárás problémájának formájában vetődött fel. A multipro­g­-ra­mozott rendszer folyamatainak kézenfekvő együttműködési módja a közös memória használata. A probléma megoldását ennek megfelelően a PRAM-modell szerinti közös memóriát használó folyamatokra keresték – további hardveres támogatás nélkül. A szinkronizáció ebben a felfogásban a folyamatok felelőssége. A folyamatok egyezményes adatszerkezeteket használnak a probléma megoldására, és a szinkronizációs pontokon egyezményes műveletsorozatot (protokoll) hajtanak végre. Ezért említi az irodalom ezeket szoftvermegoldásokként.

(Megjegyzés: a szoftvermegoldások bemutatását elsősorban didaktikai szempontok indokolják, hiszen a mai megoldások hardvertámogatásra épülnek.)

Lássuk tehát a kölcsönös kizárás problémájának megoldási kísérleteit!

A kölcsönös kizárás megoldásaival szemben a következő általános elvárásokat támasztjuk:

  • minden körülmények között teljesüljön a kölcsönös kizárás,

  • a belépési protokoll döntéshozatala csak a belépésben érdekelt folyamatok részvételét igényelje, azaz a többi folyamat nyugodtan haladhasson anélkül, hogy foglalkozniuk kellene a kérdéssel,

  • véges időn belül minden belépni szándékozó folyamat bejuthasson (ettől esetenként eltekinthetünk).

Kézenfekvő megoldásnak tűnik kritikus szakaszonként egy foglaltságjelző bit elhelyezése a közös memóriában szabad kezdőértékre állítva. A kritikus szakaszba belépni szándékozó folyamat teszteli a jelzőt, ha szabad, akkor átállítja foglaltra és belép a kritikus szakaszba, kilépéskor pedig visszaállítja szabadra. A folyamatok tehát a következőképpen működnek (a programrészleteket Pascal-szerű pszeudo-kóddal illusztráljuk):

var közös_jelző:{foglalt,szabad}:=szabad Valamennyi folyamat: … belépés: olvas (közös_jelző) if foglalt then goto belépés ír (közös_jelző,foglalt) <kritikus szakasz>

kilépés: ír (közös_jelző,szabad)

A megoldás problémája, hogy mivel a közös_jelző a közös memóriában helyezkedik el, kis valószínűséggel bár, de előfordulhat, hogy több folyamat olvassa egyidejűleg, és így többen is szabadnak találják. Ekkor egyidejűleg többen léphetnek be a kritikus szakaszba, ami nyilvánvalóan hibás.

Megjegyezzük, hogy az algoritmus nemcsak a folyamat általános modelljét (amikor minden folyamatnak külön processzora van) feltételezve hibás, hanem multiprogramozott megvalósításban is. Ekkor ugyan a párhuzamos olvasás kizárt (hiszen az egyetlen processzor egyidejűleg csak egyetlen utasítással foglalkozik), azonban az olvasás és visszaírás közé beékelődhet más folyamat végrehajtása, amelyik ugyancsak olvashatja, és szabadnak találhatja a jelzőt.

Néhány további zsákutcát átugorva, amelyek vagy ugyancsak nem biztosítják a kölcsönös kizárást, vagy csak felváltva engedik be a két folyamatot, vagy holtpontot okozhatnak, lássunk egy igazi megoldást!

A probléma egy helyes megoldása két folyamatra (Peterson, 1981): legyen a két folyamat P1 és P2. Legyen mindkét folyamatnak egy-egy jelzője a belépési szándékra, valamint egy változó, amelyik megmutatja, hogy egyidejű belépési szándék esetén melyik léphet be.

var jelző:array[1..2]of{foglal,szabad}:=szabad következő: {1,2} P1 folyamat: ... ír (jelző[1],foglal) ír (következő,2) belépés1: olvas (jelző[2]) if szabad then goto belép1 olvas (következő) if 2 then goto belépés1 belép1: <kritikus szakasz> kilép1: ír (jelző[1],szabad) … – – – – – – – – – – – P2 folyamat: ír (jelző[2],foglal) ír (következő,1) belépés2: olvas (jelző[1]) if szabad then goto belép2 olvas (következő) if 1 then goto belépés2 belép2: <kritikus szakasz> kilép2: ír (jelző[2],szabad) … – – – – – – – – – – – –

Figyeljük meg, hogy a belépésre vonatkozó döntésben a következő változónak csak akkor van szerepe, ha a másik folyamat jelzője nem szabadot mutat, azaz egyidejű belépési szándék veszélye áll fenn. Ilyenkor legrosszabb esetben a következő változóra kiadott írás is egyidejű, de az írási verseny valahogy eldől. A következő változó csak egy értéket vehet fel, mégpedig a későbbi írás eredménye (a vesztes) jelöli ki a másik folyamatot belépőnek, ami akkor is helyes, ha a másik folyamat már korábban is a szakaszban tartózkodott.

A megoldás követése már két folyamatra sem valami egyszerű, több folyamatra pedig csak a gyakorlatban alig használható bonyolultságú általános megoldás adható. Elsőként Dijkstra publikált megoldást n folyamatra 1965-ben, majd több más javaslat is született. Talán a legáttekinthetőbb Lamport megoldása (1974) a pékség és egyéb sorállásra alkalmas üzletek és szol­gál­ta­tóhelyek működésének analógiájára (bakery algorithm).

Bakery algoritmus adatszerkezetek közös tárban: var számot_kap: array [0..n-1] of Boolean := false; (jelzi, hogy egy folyamat éppen sorszámot kap) sorszám: array [0..n-1] of integer := 0; (tárolja a sorszámokat) Pi folyamat: belépési protokoll: Sorszámot kér: számot_kap[i]:=true; sorszám[i]:=max(sorszám)+1; számot_kap[i]:=false; Amíg van nála kisebb sorszámú, helybenjár: for j:=0 to n-1 do begin while számot_kap[j] do üres_utasítás;

while sorszám[j]ą0 and (sorszám[j],j)< (sorszám[i],i) do üres_utasítás; end; kilépési protokoll: sorszám[i]:=0;

Az algoritmus szerint a belépni szándékozó folyamatok először sorszámot kérnek. Mivel a sorszámosztás a közös memóriában tárolt sorszám tömb maximális elemének kiválasztását igényli, nem atomi PRAM-művelet. Ezért folyamatonként egy jelző (számot_kap) véd attól, hogy eközben a folyamat sorszámát vizsgálhassa egy másik folyamat. Az ellen azonban nincs védelem az algoritmusban, hogy két folyamat azonos sorszámot kapjon.

Miután a folyamat megkapta a sorszámát, végignézi a többi folyamat sorszámait, és ha az övé a legkisebb, belép a kritikus szakaszba. A vizsgálat közben kivárja, míg egy éppen sorszámot kérő folyamat megkapja a számot, csak utána hasonlítja össze a sajátjával. Valahányszor talál olyan folyamatot, amelyik kisebb sorszámot kapott, kivárja, amíg az a folyamat elhagyja a szakaszt, csak azután lép a következő folyamat sorszámának vizsgálatára. Így a ciklus végére érve biztosan beléphet a szakaszba, mert kivárt minden korábban érkezőt, és ezek egy esetleges következő belépési szándék esetén már csak nagyobb sorszámokat kaphattak.

Mivel két folyamatnak lehet azonos sorszáma, az algoritmus a sorszámok összehasonlítása helyett a sorszámból és a folyamat azonosító számából álló rendezett számpárokat (sorszám[i],i) hasonlítja össze, így egyező sorszámok esetén is egyértelmű a döntés a kisebb azonosító számot viselő folyamat javára.

A szoftvermegoldások bonyolultsága más irányokba terelte a probléma megoldásán fáradozó kutatókat. Olyan eszközöket dolgoztak ki, amelyek – a PRAM-modellt is kiterjesztve – a processzor utasításkészletébe épülve támogatják a folyamatok szinkronizációjának megoldását (hardvertámogatás). A következőkben ezek közül ismertetünk néhányat.

2.2.5.2. A PRAM-modell kiterjesztése

A kritikus szakaszhoz rendelt foglaltságjelző bit logikailag egyszerű és jó ötlet. A problémát az okozza, hogy a jelző értékét többen is kiolvashatják, mielőtt az első olvasó szabadról foglaltra állította volna. Megoldódik a probléma, ha a PRAM-modellt úgy módosítjuk, hogy a jelzőkre vonatkozóan az olvas és ír utasításokon kívül bevezetjük az OlvasÉsÍr (TestAndSet) utasítást. Az utasítás kiolvassa és az olvas utasításhoz hasonlóan visszaadja egy jelző értékét, majd foglaltra állítja azt. A művelet ugyanúgy oszthatatlanul (sorosítva) hajtódik végre, mint az olvas és ír utasítások. Ez azt jelenti, hogy egy szabad jelzőre több OlvasÉsÍr utasítást egyidejűleg végrehajtva ezek közül csak egy ad vissza szabad értéket, a jelző végső értéke pedig természetesen foglalt lesz.

Az OlvasÉsÍr utasítás segítségével a kölcsönös kizárás megoldása:

var közös_jelző:{foglalt,szabad}:=szabad

Valamennyi folyamat:

… belépés: OlvasÉsÍr (közös_jelző) if foglalt then goto belépés <kritikus szakasz> kilépés: ír (közös_jelző,szabad) …

Az OlvasÉsÍr utasításhoz hasonlóan a Csere (Swap) utasítás bevezetésével is megoldható a probléma. A Csere utasítás a közös memória egy rekeszének és a folyamat saját memóriája egy rekeszének tartalmát cseréli meg ugyancsak oszthatatlanul. A kölcsönös kizárás megoldása a Csere utasítással:

var közös_jelző:{foglalt,szabad}:=szabad Valamennyi folyamat: var saját_jelző:{foglalt,szabad} … saját_jelző:=foglalt belépés: Csere (közös_jelző,saját_jelző) olvas (saját_jelző) if foglalt then goto belépés <kritikus szakasz> kilépés: ír (közös_jelző,szabad) …

Az OlvasÉsÍr vagy a Csere utasítások valamelyikét egy ideje már a fizikai processzorok utasításkészlete tartalmazza. Ezek megvalósítása olyan, hogy többprocesszoros rendszerben is garantálja az oszthatatlanságot például a memóriasín több műveletre kiterjedő lefoglalásával (lásd LOCK az Intel processzorcsalád, read-modify-write ciklus a Motorola processzorcsalád esetén). Multiprogramozott rendszerben (egy processzor) az oszthatatlanságot a meg­sza­kítások tiltásával is elérhetjük, így szimulálhatók az oszthatatlan OlvasÉsÍr vagy a Csere utasítások.

A fenti megoldások nem garantálják, hogy a kritikus szakaszba belépni szándékozó folyamatok véges időn belül bejutnak a szakaszba. Ez ugyanis azon múlik, hogy a versenyző OlvasÉsÍr vagy Csere utasítások milyen sorrendben kerülnek a PRAM sorosító csővezetékébe. A foglaltságjelző ciklikus tesztelésére alapozottan ez a probléma ismét csak igen bonyolultan oldható meg. Áttekinthető megoldáshoz akkor jutunk, ha a várakozó belépési szándékokat nyilvántartjuk, és a belépések ütemezését meghatározottá tesszük. Minden szempontból célszerűbb tehát, ha a folyamatok önszervező belépési protokolljai helyett a szinkronizáció problémájának korrekt, a hardver lehetőségeihez igazodó, tisztességes ütemezést biztosító megoldását logikailag a folyamatokat végrehajtó virtuális processzorra, realizációját tekintve az operációs rendszerre bízzuk.

2.2.5.3. Szinkronizációs eszközök az operációs rendszer szintjén

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 megva­ló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 Le­fog­lal(<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.

2.2.6. Folyamatok kommunikációja

Mint láttuk, a folyamatok együttműködésének másik alapmodellje a közös me­móriás együttműködés mellett az üzenetváltásos együttműködés, azaz a folyamatok közötti kommunikáció. Az üzenetváltásos együttműködés akkor került előtérbe, amikor realitássá vált több, adatátviteli vonalon, vagy hálózaton keresztül összekapcsolt számítógép együttműködése.

A kommunikáció alapsémáját a 2.3. ábra mutatja be. Azonkívül, hogy a logikai processzor utasításkészletében szerepel Küld és Fogad művelet, a kommunikáció működésével, tulajdonságaival kapcsolatban számos nyitott kérdés maradt, és megállapítottuk, hogy nincs egyetlen tiszta modell, amelyet a megoldások követnek.

Néhány a legkézenfekvőbb kérdések közül:

  • Hogyan nevezhetjük meg a partnert? A partnert látjuk, vagy egy közbülső objektumot (csatornát, postaládát)? Egyetlen partner veheti egyszerre az üzenetünket, vagy több is? Csak egyetlen partnertől várhatunk üzenetet egy adott pillanatban, vagy többektől is?

  • Amikor a Küld művelet befejeződött, meddig jutott az üzenet? Már ott van a partnernél, vagy csak útjára bocsátottuk (lásd levél bedobása a postaládába)? Honnan fogjuk megtudni, hogy rendben megérkezett-e?

  • Hogyan működik a Fogad művelet? Mi történik, ha hamarabb akarunk fogadni egy üzenetet, mint azt elküldték? Kell-e visszaigazolást küldenünk, vagy ezt a rendszer automatikusan elintézi?

A következőkben a felmerülő kérdések közül hárommal foglalkozunk részletesebben:

  • Milyen megnevezést használhatnak a kommunikáló partnerek, hogy egymásra találjanak?

  • Milyen szemantikai konzisztenciának kell fennállni a küldés és a fogadás között?

  • Milyen járulékos (implicit) szinkronizációs hatása van a kommuniká-ciónak?

2.2.6.1. A partner megnevezése

Megnevezés tekintetében beszélhetünk közvetlen (direkt), közvetett (indirekt), valamint aszimmetrikus kommunikációról, illetve megnevezésről, továbbá csoportkijelölésről és üzenetszórásról.

A közvetlen (direkt) kommunikáció két folyamat között zajlik, mind a Küld, mind a Fogad művelet megnevezi a partner folyamatot (2.3. ábra). P1 elküldi a saját címtartományában tárolt x változó értékét P2-nek, aki azt saját y változójába teszi el. (Ha a változók közös címtartományban lennének, egyszerűen y:=x értékadást használhatnánk, így azonban kommunikációs műveletek szükségesek.)

2.3. ábra. ábra - Kommunikáció direkt megnevezéssel

Kommunikáció direkt megnevezéssel


Közvetett (indirekt) kommunikáció esetén a partnerek nem egymást nevezik meg, hanem egy közvetítő objektumot, (például postaládát, vagy csatornát). A postaládán keresztül bonyolódó kommunikációt a 2.4. ábra szemlélteti.

2.4. ábra. ábra - Kommunikáció indirekt megnevezéssel

Kommunikáció indirekt megnevezéssel


A postaláda egy általában véges, de elméletileg esetleg korlátlan befogadóképességű, az üzenetek sorrendjét megtartó (FIFO) tároló, amely a Küld-Fogad, (betesz-kivesz) műveletpárral kezelhető. A Küld(<cím>,<posta­lá­da>) művelet a saját címtartományban elhelyezkedő üzenetet a postaláda következő szabad tárolóhelyére másolja. Ha a postaláda tele van, ürülésig várakozik. A Fogad(<cím>,<postaláda>) művelet a postaládában legrégebben várakozó üzenetet kimásolja a megadott, saját címtartománybeli címre, helyét pedig felszabadítja.

A csatorna olyan kommunikációs objektum, amelyik két folyamatot kapcsol össze. A csatorna lehet egyirányú (szimplex), osztottan kétirányú, azaz egyidejűleg egyirányú, de az irány változtatható (félduplex), vagy kétirányú (duplex). Tartalmazhat 0, véges vagy végtelen kapacitású átmeneti tárolót. Egy véges tárolókapacitású duplex csatorna egyenértékű két véges befogadóképességű postaládával, amelyeket csak két folyamat használ, egyiket egyik irányú, másikat az ellenkező irányú adatcserére.

A postaláda és a csatorna lazítja a kommunikáló folyamatok közötti csatolást, lehetővé teszi, hogy olyan folyamatok is információt cseréljenek, amelyek nem ismerik egymást.

2.5. ábra. ábra - Kommunikáció asszimetrikus megnevezéssel

Kommunikáció asszimetrikus megnevezéssel


Aszimmetrikus megnevezés esetén az egyik folyamat, az adó vagy vevő, megnevezi, hogy melyik folyamattal akar kommunikálni, a másik partner viszont egy saját be-/kimeneti kaput (port) használ, amelyiket – ha csak egy van – nem is kell megneveznie. Ha az üzenet vevője használ bemeneti kaput, akkor a műveletek alakja Küld(<cím>,<folyamat>), Fogad(<cím>). Ez a megoldás azokban az esetekben hasznos, amikor a fogadó folyamat nem ismeri a küldőt, de a küldő ismeri a fogadót, például egy ügyfél folyamat szolgáltatási kérelmet küld egy szolgáltató folyamatnak (kliens–szerver modell). A fordított irányú aszimmetria alkalmazására pedig egy feladat lebontását és szétosztását végző menedzser folyamat és több, munkáért versengő végrehajtó folyamat kapcsolata lehet példa. A küldő a kimeneti port­jára küldi az elvégzendő feladatot tartalmazó üzenetet, a fogadó pedig az első ráérő feldolgozó lesz (farmer–worker modell).

Csoportkommunikáció esetén az üzenet küldője folyamatok (esetleg kommunikációs objektumok) egy csoportját nevezheti meg vevőként. Ilyenkor egyetlen üzenetküldő művelet végrehajtása azt eredményezi, hogy az üzenetet a csoport valamennyi tagja megkapja. Az üzenetszórás (broadcasting) logikailag a csoportkommunikáció azon esete, amikor az egyetlen művelettel elküldött üzenet a rendszer valamennyi folyamatához eljut (2.6. ábra).

2.6. ábra. ábra - Kommunikáció üzenetszórással

Kommunikáció üzenetszórással


A csoportkommunikáció lehetősége lényegesen egyszerűsíti a küldő műveleteit, ha több folyamattal akarja ugyanazt az információt közölni. Bizonyos típusú fizikai átviteli közegeken a csoportkommunikáció igen hatékonyan valósítható meg (például sín-topológiájú összeköttetések, rádiókommunikáció).

2.2.6.2. Szemantikai konzisztencia

Most azt szeretnénk tisztázni, hogy mi történik a kommunikációs műveletek végrehajtásakor, milyen hatása van a műveleteknek az egyes folyamatok ál­la­­potterére (változókra, kommunikációs objektumokra), milyen minimális kon­zisztencia-feltételt kell betartani a műveletek megvalósításakor.

Az üzenetváltásos modell akkor került előtérbe, amikor több számítógépet kapcsoltak össze egy rendszerré adatátviteli vonalon, vagy hálózaton keresztül. Ilyenkor fel kell készülni olyan rendkívüli esetekre is, hogy a partner folyamatot futtató számítógépet esetleg kikapcsolták, vagy a nagyobb távolságot áthidaló átvitel közben az adatok sérülnek, hiszen a hibalehetőség lényegesen nagyobb, mint az egyetlen chipben, dobozban, esetleg egyetlen kártyán elhelyezkedő egységek közötti átvitel esetén. Az üzenettovábbítás műveleteivel szemben ezért elvárás, hogy a műveletet végrehajtó folyamat ne fagyjon be sem átviteli hibák, sem a partner folyamatok kiesése esetén, és a kommunikációs műveletek helyes vagy hibás végrehajtásáról szerezzen tudomást. A műveletek helyességének visszajelzésére az egyik szokásos megoldás egy állapotkód visszaadása, amelynek egyik értéke a helyes végrehajtás, további értékei pedig az előforduló hibakódok lehetnek. Egy másik megoldás lehet a logikai processzor szintjén megvalósított hiba-megszakítás, ami a folyamat végrehajtását a hiba felderítéséhez és a folyatáshoz szükséges információk tárolását követően egy hibakezelési pontra (exception handler) irányítja. A partner folyamat kiesését szokásosan a műveletekre megszabott időkorlát (time-out) figyelésével észlelik. A kommunikációs művelet az időkorlát elérésekor hibajelzéssel akkor is befejeződik, ha a partner válaszának hiánya, vagy a kommunikációs közeg hibája miatt az adatcsere még nem történt meg. A folyamatok programozásához megfelelő rugalmasságot nyújt, ha lehetőség van a kommunikációs műveletekre vonatkozó időkorlát paraméterként történő megadására.

A hibajelzéssel és időkorláttal kiegészítve közvetlen kommunikáció esetén a műveletek a következő alakúak: Küld(<cím>,<folya­mat>,<idő­kor­lát>, <hi­bakód>), illetve Fogad(<cím>,<folyamat>,<időkorlát>,<hibakód>).

Az időkorlát lehetséges értékei között célszerű a 0 és a <végtelen> értéket is megengedni. A 0 várakozás például akkor hasznos, ha egy fogadó folyamat működésének egy pontján csak akkor akar üzenetet fogadni, ha azt már elküldték, egyébként van más teendője. A <végtelen> várakozás pedig az olyan folyamatok esetén szükséges, amelyiknek nincs teendője, amíg valaki egy üzenettel el nem indítja.

A Küld művelet szemantikáját tekintve elsősorban az a kérdés merül fel, hogy okozhat-e várakozást a művelet, és mi az, ami az adatcseréből a művelet befejeződésekor, azaz a folyamat továbblépésekor már megtörtént.

A lehetséges megoldásváltozatok közül az egyik véglet: a Küld művelet akkor fejeződik be, amikor az adatcsere teljes egészében befejeződött, a küldött üzenet rendben megérkezett és a helyére került. Ez a megoldás általában a Küld művelet várakozását is okozhatja, a végrehajtás során ellenőrzések, esetleg hibajavítások is történhetnek. A megoldás ahhoz hasonló, mint amikor tértivevényes levelet küldünk valakinek, és addig nem lépünk tovább, amíg a tértivevény aláírva vissza nem érkezett.

A másik véglet az lehet, hogy a Küld befejeződésekor az üzenet csupán bekerült a kommunikációs rendszerbe, de további sorsáról semmit sem tudunk. Ilyenkor a Küld művelet általában sohasem várakozik. Ez a megoldás ahhoz hasonló, mint amikor valakinek úgy küldünk levelet, hogy egyszerűen bedobjuk a postaládába, és továbbmegyünk.

A két véglet között számos köztes megoldás létezhet (például az üzenet elhagyta azt a processzort, amelyiken a küldő folyamat fut stb.).

Valamennyi megoldás esetén be kell tartani azt a minimális konzisztencia-feltételt, hogy amennyiben nincs hibajelzés, az elküldött üzenetet tartalmazó terület a küldő folyamat saját memóriájában (a <cím> tartalma) a Küld be­fe­jeződése után – akár a következő utasítással – felülírható legyen. Ennek már nem szabad hatással lennie az elküldött üzenetre.

A Fogad művelet megvalósításai általában várakozást okozhatnak abban az esetben, ha még nem érkezett üzenet. A művelet egyszeri végrehajtása pontosan egy üzenetet helyez el a fogadó folyamat saját memóriájába akkor is, ha esetleg több várakozó üzenet van a folyamat számára a kommunikációs rendszerben. Az üzenetek érkezési sorrendben fogadhatók, minden üzenet csak egyszer, azaz a fogadás törli az üzenetet a kommunikációs rendszerből. Postaláda, illetve bemeneti kapu használata esetén kérdés, hogy a fogadó tudomást szerez-e arról, hogy ki az üzenet küldője. Erre általában szükség van, hiszen az üzenetre gyakran választ kell küldeni. Ha a kommunikációs rendszer ezt az információt nem közli automatikusan, a folyamatoknak kell gondoskodniuk arról, hogy a küldő azonosítható legyen az üzenet tartalma alapján.

2.2.6.3. Járulékos (implicit) szinkronizáció

A kommunikációs műveletek általában a kommunikációban résztvevő folyamatok szabadonfutásának korlátozását okozzák. Az egyes műveletekkel járó szinkronizációs mellékhatás elsősorban a kommunikációs rendszer átmeneti tárolójának (puffer) kapacitásától függ.

Tárolás nélküli átvitel esetén a kommunikációs rendszer csak közvetít, de a Küld és Fogad műveleteknek be kell várnia egymást ahhoz, hogy az információcsere megtörténhessen. A két folyamat ezen utasításaira egyidejűség érvényes (a Küld és a Fogad randevúja).

Véges kapacitású tároló alkalmazása bizonyos keretek között kiegyenlíti a küldő és fogadó folyamatok sebességingadozásait. A fogadó folyamat várakozik, ha üres az átmeneti tároló, a küldő folyamat pedig akkor, ha nincs szabad hely a tárolóban. Ugyanazon üzenet elküldésének meg kell előznie az üzenet fogadását, tehát ezen műveletekre sorrendiség (precedencia) érvényesül. Emellett egy rövid távú szinkronizációs hatás is érvényesül, magának a tárolónak a kezelése általában kölcsönös kizárással valósul meg, azaz két folyamat ugyanazon kommunikációs objektumra hivatkozó kommunikációs műveleteinek megvalósítási részleteit szemlélve egyes szakaszokra kölcsönös kizárás áll fenn.

Végtelen kapacitású tároló (csak modellben létezik) esetén a küldő folyamatnak sohasem kell várakoznia, egyébként a véges kapacitású tárolóra elmondottak érvényesek.

2.2.7. Holtpont

Amikor az első multiprogramozott rendszereket üzembe állították, időnként nehezen reprodukálható, ezért nehezen megkereshető és megmagyarázható hibákat tapasztaltak. Ezek egyik típusa a lyukas kölcsönös kizárásokból (foglaltságjelző bit) származott. A másik jelenségtípus a rendszerek időnkénti „lefagyása”. Ahogy a kölcsönös kizárás korrekt megoldása is alapos analízist, majd elméletileg megalapozott megoldást igényelt, a lefagyási jelenségekkel kapcsolatban is hasonló volt a helyzet. Az elemzések kiderítették, hogy folyamatok bizonyos esetekben úgy akadhatnak össze, hogy csak egymást tudnák továbbindítani, de mivel mindegyik a másikra vár, senki nem tud továbblépni. Az ilyen helyzeteket holtpontnak (deadlock) nevezzük. Holtpont bekövetkezésének gyakran igen kicsi a valószínűsége. A hiba éppen ezért alattomos, és nehezen reprodukálható. Vegyük hát alaposabb vizsgálat alá a jelenséget!

2.2.7.1. Mi a holtpont?

Ha az együttműködő folyamatok szinkronizációs és kommunikációs műveleteit kellő körültekintés nélkül alkalmazzuk, könnyen előidézhetjük a rendszer folyamatainak teljes vagy részleges befagyását.

Tegyük fel, hogy egy rendszerben két erőforrást (például az NY nyomtatót és az M mágnesszalag egységet) használ két folyamat a következő módon:

P1 folyamat: ... Lefoglal(M) <mágnesszalag használata>... Lefoglal(NY) ... <nyomtató és mágnesszalag együttes használata> ... Felszabadít(M) <nyomtató használata>… Felszabadít(NY) ... – – – – – – – – – – – – – –

P2 folyamat: ... Lefoglal(NY) <nyomtató használata>... Lefoglal(M) ... <nyomtató és mágnesszalag együttes használata> ... Felszabadít(NY) <nyomtató használata>… Felszabadít(M) ... – – – – – – – – – – – – – –

Tegyük fel, hogy a két folyamat együttfutásakor P1 már lefoglalta M-et, de még nem foglalta le NY-et, P2 pedig lefoglalta NY-et de még nem foglalta le M-et. (Ilyen helyzet kialakulhat, hiszen a folyamatok futására nincs korlátozás, de ugyanezért nem biztos, hogy minden együttfutáskor kialakul.) A továbbiakban P1 előbb-utóbb le akarja foglalni NY-et is, de nem kaphatja meg, mert az már P2-é, P2 pedig le akarja foglalni M-et is, de az már P1-é. Így mindkét folyamat arra fog várni, hogy a másik elengedje az erőforrását, de addig egyik sem tud eljutni, mert előbb erőforráshoz kellene jutnia. A két folyamat között keresztreteszelés alakul ki, ebből a helyzetből egyik sem tud továbblépni.

Vegyük észre, hogy ha a folyamatok úgy futnak le, hogy valamelyiknek sikerül mindkét erőforrást megszerezni, akkor már nem alakulhat ki holtpont, hiszen akkor ez a folyamat előbb-utóbb fel is szabadítja azokat és ekkor – ha már közben igényelte, várakozás után – a másik is hozzájuk juthat. A holtpont kialakulásának valószínűsége annál nagyobb, minél hosszabb a folyamatok azon szakasza, amikor még csak egyik erőforrást birtokolják. Nem alakulhatna ki holtpont, ha a folyamatok egyetlen művelettel kérnék el mindkét erőforrást.

Vegyük észre azt is, hogy akkor sem alakulhatna ki holtpont, ha mindkét folyamat azonos sorrendben kérné el a két erőforrást.

A fenti, legegyszerűbb esetnél lényegesen bonyolultabban és áttételesebben is összegubancolódhatnak folyamatok amiatt, hogy közös erőforrásaik vannak, illetve üzeneteket várnak egymástól.

Általánosságban azt mondjuk, hogy egy rendszer folyamatainak egy H részhalmaza holtponton van, ha a H halmazba tartozó valamennyi folyamat olyan eseményre vár, amelyet csak egy másik, H halmazbeli folyamat tudna előidézni.

Megjegyzések:

  • A definíció általános, az esemény nemcsak erőforrás felszabadulása lehet, hanem tetszőleges más valami is, amire egy folyamat várakozni tud.

  • A rendszerben lehetnek futó, élő folyamatok a holtponton lévők mellett, tehát nem biztos, hogy a befagyás teljes.

  • Nem biztos, hogy a holtpont a folyamatok minden együttfutásakor kialakul, sőt az esetek jelentős részében igen kis valószínűséggel alakul ki. Ezért a jelenség nehezen reprodukálható, alattomos hibaforrás.

  • A holtpont egyrészt azon funkciók kiesését okozza, amelyeket a befagyott folyamatok látnak el, másrészt csökkenti a rendszer teljesítőképességét, hiszen a befagyott folyamatok által lekötött erőforrásokhoz a többi folyamat sem tud hozzájutni.

A továbbiakban olyan rendszerekre szorítkozunk, amelyek folyamatai között csak az erőforrásokért folytatott verseny miatt van kapcsolat (ide tartozhat tetszőleges, kölcsönös kizárás jellegű szinkronizáció is).

2.2.7.2. Holtpont erőforrásokért versengő rendszerekben

Az erőforrásokért versengő rendszerekre a következő rendszermodellt állíthatjuk fel:

  • A rendszerben véges számú és típusú erőforrást kell felosztani az értük versengő folyamatok között.

  • Az erőforrások osztályokba (típusokba) sorolhatók. Egyes típusokhoz egyetlen erőforráspéldány tartozik (egypéldányos erőforrások), más típusú erőforrásokból több példány áll rendelkezésre (többpéldányos erőforrások), amelyek használati értékükben azonosak. Egy folyamat számára közömbös, hogy azonos típuson belül melyik erőforráspéldányokat használja. Jellegzetes egypéldányos erőforrások például a speciális perifériák (rajzgép, kisebb rendszerek egyetlen nyomtatója), rendszertáblák, multiprogramozott rendszerek processzora stb. Jellegzetes többpéldányos erőforrások: memória, a rendszer egyenértékű nyomtatói, mun­katerület a mágneslemezen.

  • Az erőforrásokat használati módjuk szerint csoportosíthatjuk megosztottan használható vagy csak kizárólagosan használható erőforrásokra. A megosztottan használható erőforrások állapota menthető és visszaállítható (preemptable), így esetleg elvehetők egy folyamattól, és később visszaadhatók úgy, hogy a folyamat zökkenőmentesen folytatódhasson (lásd CPU, memória). Ilyen erőforrásokra megfelelő időbeli ütemezéssel (a használat időbeli megosztásával) látszólag párhuzamos használatot lehet szimulálni. A csak kizárólagosan használható erőforrások állapota nem menthető (non-preemptable), így nem vehetők el a folyamattól anélkül, hogy a folyamatot visszaküldenénk egy korábbi állapotába (lásd nyomtató).

  • A folyamatok az erőforrások használata során a következő lépéseket hajtják végre:

    1. Igénylés. Az igénylés rendszerhívással történik. Legyen az erőforráskérés művelete a Kér. Egy kéréssel általános esetben (többpéldányos erőforrások) akár valamennyi erőforrásfajtából is lehet egyidejűleg több példányt igényelni. Ha a rendszerben n fajta erőforrás van, a művelet paramétere egy n elemű vektor, amelynek minden eleme az adott erőforrásfajtából igényelt mennyiséget jelöli (Kér (n1,n2, ...,nn)). Az igény nem teljesíthető, ha bármelyik erőforrástípusból nem adható ki a folyamatnak az igényelt mennyiség. Ilyenkor a folyamat várakozni kényszerül. Tekintve, hogy az erőforráspéldányok egyenértékűek, a folyamat a szabad példányok bármelyikét megkaphatja. A folyamat azonban a megkapott konkrét példányokat használja, amelyeket tehát most már azonosítani kell. A Kér művelet ezért általános esetben erő­for­rás­típusonként egy-egy tömböt is visszaad, amelyik az odaadott erőforráspéldányok azonosítóit tartalmazza. A felszabadítás – amennyiben nem az adott típus valamennyi birtokolt példányának felszabadítása a folyamat szándéka – a konkrét példányok felszabadítását kell hogy jelentse.

    2. Használat.

    3. Felszabadítás. Általános esetben a Felszabadít művelet két formáját célszerű bevezetni. A Felszabadít (E1,E2,...,Em) paraméterei erőforrástípusok. A művelet a felsorolt erőforrástípusokból a folyamat által birtokolt valamennyi példányt felszabadítja. A Felszabadít (V1,V2, ...,Vn) alakban a paraméterek Vi vektorok, amelyek az egyes erőforrástípusokból felszabadítandó példányok azonosítóit tartalmazzák. Amennyiben az erőforrásokra várakoztak más folyamatok, ezek közül valamelyik megkaphatja a felszabaduló erőforrásokat és továbbléphet.

A holtpont kialakulásának szükséges feltételei:

  1. Kölcsönös kizárás: legyenek olyan erőforrások a rendszerben, ame­lyeket a folyamatok csak kizárólagosan használhatnak.

  2. Foglalva várakozás: legyen olyan folyamat, amelyik lefoglalva tart erőforrásokat, miközben más erőforrásokra várakozik.

  3. Nincs erőszakos erőforrás-elvétel a rendszerben, azaz minden folyamat addig birtokolja a megkapott erőforrásokat, amíg saját jószántából fel nem szabadítja azokat.

  4. Körkörös várakozás: a rendszerben lévő folyamatok közül létezik egy olyan {P0, P1, ... Pn} sorozat, amelyben P0 egy P1 által lefoglalva tartott erőforrásra vár, Pi egy Pi+1-re, végül Pn pedig P0-ra vár.

A rendszer pillanatnyi állapotát erőforrásfoglalási gráffal (resource allo­cation graph) modellezhetjük (2.7. ábra).

2.7. ábra. ábra - Erőforrásfoglalási gráf

Erőforrásfoglalási gráf


A gráfnak kétféle csomópontja van: erőforrás (Ri, téglalap) és folyamat (Pi, kör). Ugyancsak kétféle él található a gráfon. Irányított él vezet Pi folyamattól Rj erőforráshoz (kérés él), ha Pi már kérte Rj-t, de még nem kapta meg. Irányított él vezet Ri-től Pj-hez (foglalás él), ha Pj birtokolja (megkapta és még nem szabadította fel) Ri-t. Többpéldányos erőforrások esetén a példányokat megfelelő számú ponttal jelezzük az erőforrástípust jelképező téglalapon belül. Annak érzékeltetésére, hogy a folyamat konkrét példányt birtokol, de csak típust kér, a foglalás éleket a konkrét példányt jelképező pontból indítjuk, a kérés éleket pedig csak a téglalap határvonaláig vezetjük.

Az erőforrásfoglalási gráf a rendszer működése során folyamatosan változik, ahogyan új kérések és foglalások történnek. A gráf elemzése alapján következtethetünk holtponthelyzetek fennállására. Körkörös várakozás esetén (holtpont 4. szükséges feltétele) a gráfon is irányított kör van. Abban az esetben, ha minden erőforrás egypéldányos, a gráfon kimutatható kör egyben elégséges feltétel is a holtpont fennállására. Többpéldányos esetben azonban kör jelenléte nem jelenti feltétlen azt, hogy a rendszerben holtpont van. A 2.8. ábra (b) oldalán a kör ellenére látjuk, hogy mind R1, mind R2 egy-egy példányát olyan folyamat birtokolja, amelyik nem várakozik (P2 és P4), így van esély rá, hogy felszabadítja az erőforrást. A körben szereplő P1 és P3 tehát nem feltétlen egymásra vár, hanem P2, illetve P4 által okozott esemény hatására is továbbléphetnek.

2.8. ábra. ábra - Irányított kört tartalmazó gráf holtponttal és holtpont nélkü

Irányított kört tartalmazó gráf holtponttal és holtpont nélkü


Az ábra (a) oldalán ezzel szemben olyan helyzetet látunk, amelyben mindhárom folyamat várakozik, és bármelyiküket csak a három várakozó valamelyike tudná egy erőforrás-felszabadítással továbbengedni.

Miután megalkottuk a holtpontprobléma vizsgálatára alkalmas rendszermodellt az erőforrásokért versengő folyamatok esetére, foglalkozzunk azzal a kérdéssel, hogy mit kezdhetünk a problémával. Háromféle alapállásunk lehet:

  1. Nem veszünk tudomást a problémáról és nem teszünk semmit (strucc algoritmus).

  2. Észrevesszük, ha holtpont alakult ki, és megpróbáljuk feloldani (detektálás és feloldás).

  3. Védekezünk a holtpont kialakulása ellen. Ezen belül is két lehetőségünk van:

    megelőzés, amikor is strukturálisan holtpontmentes rendszert tervezünk, amelyben a szükséges feltételek valamelyikének kizárása miatt eleve nem alakulhat ki holtpont,

    elkerülés, amikor is a rendszer futás közben csak olyan erőforráskéréseket elégít ki, amelyek nem vezetnek holtpontveszélyhez.

2.2.7.3. A strucc algoritmus

Az „algoritmus” elnevezését Tanenbaum és Woodhull könyvéből kölcsönöztük. Első reakciónk valószínűleg az, hogy ez az alapállás meglehetősen hanyag magatartásforma, hiszen ismert hibalehetőséget hagyunk tudatosan a rendszerben. Bizonyos típusú rendszerek esetén – ahol élet- és vagyonbiztonság a tét – nem is engedhető meg az ilyen tervezői megközelítés. Más, kisebb kockázatú esetekben – ahol megengedhető a „kiszállunk, beszállunk, és akkor biztos jó lesz ...” szemlélet, azaz különösebb veszteség nélkül újraindítható a rendszer – azonban mégis reális lehet a probléma figyelmen kívül hagyása.

Mint a mérnöki praxisban annyiszor, azt kell mérlegelnünk, mekkora a prob­léma és milyen áron tudjuk megoldani. Az esetek többségében a holtpont kialakulásának valószínűsége meglehetősen kicsi, bár néhány tényező ezt a valószínűséget jelentősen megnövelheti. Minél többféle típusú, de típusonként minél kevesebb erőforrásért minél több folyamat verseng, a holtpont kockázata általában annál nagyobb. Minél hosszabb ideig tartják lefoglalva a folyamatok az erőforrásokat, és minél inkább alkalmazzák a „rákérést”, azaz újabb erőforrások igénylését a már használtak mellé, a holtpont kialakulásának valószínűsége ugyancsak annál nagyobb.

Ugyanakkor látni fogjuk, hogy az észlelés és feloldás a kritikus rendszerekben nem jelent minőségi különbséget a probléma figyelmen kívül hagyásához képest, a megelőzésnek és elkerülésnek pedig hatékonyságromlásban jelentkező ára van.

Végül is tervezői mérlegelés kérdése, hogy egy rendszerben milyen alapállás és milyen megoldás a legmegfelelőbb. Tény, hogy az általános célú, közismert operációs rendszerek általában nem foglalkoznak a problémával, legfeljebb a belső funkciók tervezésekor törekedtek arra, hogy a holtpont kialakulásának valószínűségét csökkentsék. A felhasználó együttműködő fo­lyamatainak holtpontra jutása ellen azonban nincsenek beépített védelmek.

2.2.7.4. A holtpont észlelése

A rendszer futása során több jel mutathat arra, hogy holtpont van. Bizonyos funkciók nem élnek, a rendszer lelassul, parancsokra nem, vagy nagyon lassan reagál. A gyanú felmerülésekor – vagy óvatosságból gyakrabban, például bizonyos időközönként, vagy eseményekhez kötötten is – elindíthatunk a rendszerben egy holtpontdetektálást végző programot, amelyik felderíti, hogy vannak-e a rendszerben holtponton lévő folyamatok, és ha igen, melyek azok. Ha vannak, akkor a holtpontot érdemes felszámolni, ami többnyire rombolással jár, de annyival jobb a helyzet, mint a probléma figyelmen kívül hagyása esetén, hogy nem kell a teljes rendszert újraindítani, hanem megúszhatjuk néhány folyamatra kiható beavatkozással.

A detektálás indítása történhet az operációs rendszer által automatikusan, vagy kezelői parancsra. Megjegyzendő, hogy ha nagyon óvatosak vagyunk, akkor az operációs rendszer akár minden erőforráskérés teljesítése után ellenőrizheti, nem vezetett-e holtpontra a kérés teljesítése. Ezzel azonban körülbelül akkora adminisztrációs terhelést (overhead) okozunk a rendszerben a detektáló program gyakori futtatásával, mintha az elkerülés érdekében minden kérés teljesítése előtt hajtanánk végre ellenőrzéseket, tehát akkor már inkább az elkerülést válasszuk.

Milyen algoritmus szerint működjön a detektáló program? Érdemes megkülönböztetni az egypéldányos és többpéldányos erőforrások esetét, ugyanis egyszerűbb algoritmust alkalmazhatunk, ha valamennyi erőforrásfajtából csak egyetlen példányunk van.

Kezdjük az általános esettel, azaz a többpéldányos erőforrásokkal. Mutassuk be a problémát egy példán. Egy adott fajtájú erőforrásból a rendszerben van 10 példány. A rendszerben négy folyamat (P1,...,P4) működik. A pillanatnyi helyzetet a 2.9. ábra szemlélteti.

2.10.ábra. táblázat - Többpéldányos erőforrások maximális igény előrejelzésével

 

FOGLAL

KÉR

P1

4

4

P2

1

0

P3

3

4

P4

1

2


Az erőforrások közül 9 a FOGLAL oszlop szerint már ki lett osztva, 1 szabad példánya van még a rendszernek. P1, P3 és P4 várakozik a KÉR oszlop szerinti példányra (nyilván egyik sem szolgálható ki, mert nincs elég szabad példány), P2 pedig fut. Vajon vannak-e a rendszerben holtponton lévő folyamatok?

P2 nyilván nincs holtponton, hiszen fut. P1, P3 és P4 várakozik, de vajon egymásra várnak-e, vagy van még esélyük a továbblépésre? A válasz némi elemzést igényel. Meg kell vizsgálni a továbblépési esélyeket. Pillanatnyilag csak P2 fut, ő fel tud szabadítani erőforrásokat, legfeljebb annyit, amennyi van nála. Ez 1 példány, ezzel együtt a rendszernek 2 szabad példánya lesz. Ez mire elég? P1-nek nem, P3-nak nem, de P4-nek igen. Így P4-nek van továbblépési esélye. Ha továbblép, arra is van esély, hogy felszabadítsa a nála lévő erőforrásokat. Már nála van egy, a továbblépéshez kap kettőt, tehát három példányt tud felszabadítani. Mivel a rendszernek nincs további szabad példánya, ebben az esetben összesen ez a 3 lesz szabad. Sajnálatosan ez sem P1, sem P3 számára nem elég, így innen már nincs továbblépési lehetőség. Az elemzés végeredménye tehát az, hogy P1-nek és P3-nak nincs továbblépési esélye, P1 és P3 tehát holtponton van.

Az elemzésnek ezt a gondolatmenetét általánosítja a Coffman és szerzőtársai által 1971-ben publikált algoritmus több erőforrástípusra.

Legyen a folyamatok száma N, az erőforrástípusok száma M.

Tároljuk a szabad erőforrások számát a SZABAD nevű, M elemű vektorban, az egyes folyamatok által már lefoglalt erőforrások számát a FOGLAL, N×M elemű mátrixban, a várakozó kéréseket a KÉR, N×M elemű mátrixban.

Jelentse FOGLAL[i] a Pi folyamat által az egyes erőforrásfajtákból foglalt mennyiséget tároló vektort, azaz a FOGLAL mátrix i-edik sorát, hasonlóan KÉR[i] pedig a Pi folyamat egyes erőforrástípusokra vonatkozó várakozó kéréseit, az a KÉR mátrix i-edik sorát.

Az algoritmus alapgondolata, hogy szisztematikusan megkeresi azokat a folyamatokat, amelyeknek továbblépési esélye van, ha végül maradnak olyan folyamatok, amelyeknek nincs, azok holtponton vannak. A keresés minden lépésében olyan folyamatot keres, amelynek várakozó kérései kielégíthetők a rendelkezésre álló erőforrásokkal. Ha van ilyen folyamat, akkor az kivehető a további vizsgálatból (van továbblépési esélye), a rendelkezésre álló készlet pedig megnövelhető a folyamat által birtokolt erőforrásokkal (hiszen van rá esély, hogy a továbbinduló folyamat ezeket felszabadítja), és a következő folyamat a megnövelt készlettel kereshető. Az algoritmus úgy zárul, hogy nem talál újabb folyamatot. Ennek egyik lehetséges oka, hogy elfogytak a folyamatok – ilyenkor nincs holtpont a rendszerben; másik lehetséges oka, hogy nincs köztük olyan, amelyiknek elég az éppen rendelkezésre álló készlet – ilyenkor a megmaradt folyamatok holtponton vannak.

Az algoritmus egy GYŰJTŐ nevű, M elemű vektort használ a továbbléptethető folyamatoktól visszakapott erőforrások akkumulálására, valamint egy TOVÁBB nevű, N elemű logikai változó vektort azoknak a folyamatoknak a kipipálására, amelyeket továbbléptethetőnek talált.

Az algoritmus 2. lépésében a KÉR[i] ≤ GYŰJTŐ reláció (két vektor összehasonlítása) akkor igaz, ha KÉR[i],[j] ≤ GYŰJTŐ[j] fennáll minden j-re (j=1,2,...,M), azaz a kérést valamennyi erőforrásfajtából ki lehet elégíteni.

A Coffman-féle holtpontdetektáló algoritmus 1. Kezdőértékek beállítása: GYŰTŐ := SZABAD TOVÁBB[i] := hamis minden i-re (i=1,2,...,N) 2. Továbblépésre esélyes folyamatok keresése: Keress i-t, amelyre (TOVÁBB[i] = hamis ÉS KÉR[i] ≤ GYŰJTŐ); Ha van ilyen i, akkor GYŰJTŐ := GYŰJTŐ + FOGLAL[i]; TOVÁBB[i] := igaz; ismételd a 2. lépést; Egyébként folytasd a 3. lépéssel 3. Kiértékelés: Ha TOVÁBB[i] = igaz minden i-re (i=1,2,...,N), akkor NINCS HOLTPONT; Egyébként A Pi folyamatok, amelyekre TOVÁBB[i] = hamis, HOLTPONTON VANNAK.

A fenti algoritmus természetesen egypéldányos erőforrások esetén is mű­ködik, azonban ilyenkor egyszerűbb, kedvezőbb komplexitású algoritmus is hasz­nálható. Egypéldányos erőforrások esetén holtpont van a rendszerben, ha az erőforrásfoglalási gráfon kör alakul ki, és azok a folyamatok vannak holt­ponton, amelyek a kör csomópontjaiban találhatók. Az irányított gráfok kördetektáló algoritmusai hatékonyabbak az általános esetre bemutatott Coff­man-algoritmusnál, ezért egypéldányos esetben inkább ezek használata célszerű.

2.2.7.5. A holtpont feloldása

Ha a holtpont már kialakult, általában nem számolható fel veszteségek nélkül. Ahhoz, hogy a holtponton lévő folyamatok továbbléphessenek, illetve az általuk foglalt erőforrások felszabaduljanak, valamilyen erőszakos megoldáshoz kell folyamodni. A lehetséges megoldásokat közelíthetjük a folyamatok, illetve az erőforrások oldaláról, de az eredmény minkét esetben hasonló. Ha a folyamatok oldaláról közelítünk, ki kell lőni (abortálni kell) egy vagy több folyamatot a holtponton lévők közül, ezeket egyszersmind megfosztjuk valamennyi erőforrásuktól. Az erőforrások oldaláról közelítve a feloldáshoz erőszakkal kell elvenni erőforrásokat egy vagy több folyamattól. Ennek következménye – hacsak az erőforrás állapota nem menthető – az, hogy az érintett folyamatokat vagy kezdőpontjukra kell visszaállítani (ez egyenértékű az abortálással), vagy legalábbis egy olyan állapotba kell visszaküldeni, ahol még nem használták az erőforrásokat, és ahonnan ismételhető a végrehajtásuk (rollback). A holtpont feloldását végezheti a rendszer kezelője manuálisan, vagy megkísérelheti az operációs rendszer automatikusan.

A holtpont feloldásakor – bármelyik oldalról közelítünk is – a következő problémákkal találkozunk:

  • Dönteni kell, hogy radikális, vagy kíméletes megoldást válasszunk-e. A radikális megoldás, ha valamennyi, a holtpontban érintett folyamatot felszámoljuk. Ez biztosan megszünteti a holtpontot és nem merül fel kiválasztási költség. Mérlegelés esetén meg kell vizsgálni, hogy a választott folyamatok felszámolása elegendő-e a holtpont megszűnéséhez. Ezen túlmenően az áldozatok kiválasztásához szempontrendszert kell felállítani, és ennek megfelelő döntési algoritmust kell végrehajtani, ami időt és erőforrásokat igényel. A mérlegelendő szempontok között szerepelhet például, hogy

    • nincsenek-e menthető állapotú erőforrások, amelyek elvétele esetén nincs szükség abortálásra, vagy visszaállításra,

    • a lehető legkevesebb folyamatot kelljen felszámolni,

    • milyen a folyamatok prioritása,

    • mekkora részét végezték már el feladataiknak (ez veszne kárba).

  • Biztosítani kell a folyamatok visszaállíthatóságát. Ha arra gondolunk, hogy egy folyamat létrehozhat és módosíthat fájlokat, egyéb maradandó változásokat okozhat a rendszerben, sőt holtpontra jutásakor félkész, inkonzisztens állapotot hagyhat maga után, az sem nyilvánvaló, hogy egy folyamat következmények nélkül abortálható és újraindítható. Közbenső visszaállítási pontok létrehozásához pedig legalább a végrehajtáskor érintett utolsó visszaállítási ponthoz tartozó állapotot tárolni kell. Ezt a problémát az operációs rendszer önmaga gyakorlatilag nem tudja megoldani, a folyamatokat is fel kell készíteni arra a lehetőségre, hogy sor kerülhet újraindításukra, vagy visszaállításukra.

2.2.7.6. A holtpont megelőzése

Ha a holtpont kialakulása nem engedhető meg egy rendszerben, védekezni kell ellene. Ennek egyik módja, hogy gondosan tervezünk, és valamelyik szükséges feltétel kiküszöbölésével strukturálisan holtpontmentes rendszert hozunk létre, ezzel megelőzzük a holtpont kialakulását. Az így tervezett rendszernek futás közben nem kell foglalkoznia az erőforrások kiadásakor a pillanatnyi helyzethez igazodó döntéshozatallal, hiszen működése során eleve nem alakulhat ki holtpont.

Vegyük sorra, milyen lehetőségeink vannak arra, hogy a holtpont kialakulásának szükséges feltételeit kiküszöböljük!

Kölcsönös kizárás

A kiküszöbölésre gyakorlatilag nincs esélyünk. Bizonyos mozgásterünk van abban, hogy csökkentsük a kizárólagosan használt erőforrások számát. Például egy rekord vagy fájl esetén, amelyeket egyébként indokoltan nyilvánítunk erőforrásnak, megengedhetjük az olvasások egyidejűségét. Egy másik lehetőség a kizárólagos használati szakaszok oszthatatlan műveletként történő megvalósítása, és ezeknek az oszthatatlan műveleteknek a sorosítása. Erre példa az operációs rendszerekben gyakran alkalmazott fájlonkénti nyomtatás. A folyamatok a nyomtató hosszú távú lefoglalása helyett egy saját használatú fájlban tárolják a nyomtatandó adatokat, majd a fájlt küldik el a nyomtató várakozási sorába. A sort egy önálló nyomtatófolyamat dolgozza fel fájlonként sorosan, így a fájlok között nincs konfliktus, és nem szükséges a nyomtató erőforrásként történő lefoglalása. Finomabb léptékben a folyamatok közös memóriájának PRAM-modellje is ezt az elvet követi, de alkalmazhatjuk a megoldást rekordok felülírása esetén is. Megjegyzendő, hogy a kölcsönös kizárás problémáját ezek a megoldások nem száműzik a rendszerből, csupán az időtávot csökkentik, és a megoldás felelősségét a rendszer egy jól kézbentartható területére korlátozzák. A nyomtató sorába való beláncolás, vagy a PRAM csővezetékébe való parancselhelyezés ugyanis maga is igényli, hogy rövidebb távú kölcsönös kizárások érvényesüljenek.

Foglalva várakozás

Foglalva várakozás akkor alakul ki, ha egy folyamat már birtokol erőforrást, és ekkor kér újabbat, amire várakoznia kell. Ez a helyzet elkerülhető, ha minden folyamat betartja azt a szabályt, hogy az egyidejűleg szükséges valamennyi erőforrását egyetlen rendszerhívással kéri el. A szabály betartásával megelőzhető a holtpont, de ára az erőforrás-kihasználás jelentős romlása. Ha ugyanis a folyamatnak van olyan futási szakasza, amelyiken több erőforrást is használ egyidejűleg, akkor ezek mindegyikét már akkor le kell foglalnia, amikor az elsőre szüksége van. Így a többit akkor is leköti, amikor még nem használja őket.

Nincs erőszakos erőforráselvétel

Ezt a feltételt menthető állapotú erőforrások esetén küszöbölhetjük ki prob­lémamentesen, ellenkező esetben az erőforrás elvétele egyben a folyamat abortálását, vagy legalábbis egy korábbi állapotba való visszaállítását okozza.

Az egyik erőszakos megoldás az erőforrást kérő folyamatot bünteti. Amelyik folyamat olyan erőforrást kér, amire várnia kellene, várakozásba is kerül, egyben valamennyi már birtokolt erőforrását is elveszti, és csak akkor folytatódhat, ha ezeket is, és a kérteket is egyidejűleg vissza tudja kapni.

A másik megoldás az erőforrást kérő folyamatot igyekszik előnyben részesíteni. Ha a folyamat kérése nem elégíthető ki a szabad készletből, a rendszer a már amúgy is várakozó folyamatoktól elvett erőforrásokkal igyekszik teljesíteni a kérést. Ha így sem sikerül, csak akkor kell a kérő folyamatnak várakoznia, ami persze azt jelenti, hogy közben tőle is vehetnek el erőforrást. A folyamat akkor folytatódhat, ha a kért és az esetleg közben elvett erőforrásokat is egyszerre megkaphatja.

Körkörös várakozás

Ez a feltétel kiküszöbölhető, ha a folyamatok mindegyike betart egy viselkedési szabályt, amelyik kicsit bonyolultabb, mint az „egyszerre kérem az erőforrásaimat”, de kevésbé rontja az erőforrás-kihasználást.

A körkörös várakozás az erőforrásfoglalási gráfon keletkező körnek felel meg. Egy ilyen kör alakja: PiRjPi+1Rj+1 → .... Pi+nRj+nPi

Tegyük fel, hogy a folyamatok megegyeznek az erőforrástípusok sorszámozásában. Viselkedjen minden folyamat úgy, hogy csak nagyobb sorszámú erőforrást kérhet azoknál, amelyek már a birtokában vannak. Vegyük észre, hogy ekkor a gráf minden útja csak növekvő sorszámú erőforrásokon át vezethet (a folyamatokba befutó élek kisebb sorszámú erőforrástól indulnak, mint ahova a folyamatból kivezető élek befutnak), így ezek az utak sohasem záródhatnak, nem alakulhat ki kör az erőforrásfoglalási gráfon.

2.2.7.7. A holtpont elkerülése

A holtpont elleni védekezés másik lehetősége a megelőzés mellett az elkerülés. Az elkerülés alapelve, hogy a rendszer minden erőforrásigény kielégítése előtt mérlegeli, hogy nem vezet-e holtpontveszélyre a kérés teljesítése, másszóval, fennmarad-e a biztonságos állapot. Így lehetséges, hogy egy kérést akkor sem elégít ki, és a kérő folyamatot várakoztatja, ha egyébként elegendő számú szabad példány áll rendelkezésre a kérés teljesítéséhez. Az elkerülés tehát a védekezés egy dinamikus formája, amelyik futási idejű hely­zetelemzést igényel. Nem vezet be az erőforrás-kihasználást rontó megkötéseket, ugyanakkor adminisztrációs teljesítményveszteséget okoz.

Kérdés, hogy milyen algoritmussal dönthető el, hogy egy kérés kielégítése esetén biztonságos marad-e a rendszer állapota. Ismét csak érdemes megkülönböztetni az egypéldányos, illetve többpéldányos erőforrások esetét. Kezdjük ismét az általános, többpéldányos esettel és egy egyszerű példával!

A rendszerben négy folyamatunk van (P1,...,P4), és egy erőforrástípusból tíz példányunk. Az aktuális helyzetet a 2.10. ábra mutatja. Tudjuk, hogy futásuk során az egyes folyamatoknak egyidejűleg legfeljebb hány példányra lesz szükségük (MAXIMÁLIS IGÉNY). A már megkapott mennyiséget a FOGLAL oszlop mutatja, a MÉG KÉRHET oszlop pedig a két előző különbsége, legfeljebb ekkora igénnyel jelentkezhet a továbbiakban egy-egy folyamat. Ennek alapján a rendszernek még 3 szabad példánya van. Pillanatnyilag P3 jelentkezett 2 példányért, és P4 1 példányért. A szabad mennyiségből mindkét kérés kielégíthető. Vizsgáljuk meg, mi történik, ha kielégítjük mindkét kérést!

2.17.ábra. táblázat - Elérési mátrix statikus védelmi tartományokkal

 

MAXIMÁLIS IGÉNY

FOGLAL

MÉG KÉRHET

KÉR

P1

7

3

4

0

P2

7

0

7

0

P3

8

1

7

2

P4

6

3

3

1


P3 sora a táblázatban ekkor 8,3,5,0 lesz, P4-é pedig 6,4,2,0. A rendszernek nem marad szabad példánya. Mi történhet ezután? A legrosszabb esetben a következő pillanatban minden folyamat bejelenti a még kérhető maximális igényét, azaz P1 4, P2 7, P3 5, P4 pedig 2 példányt kér. A rendszernek nincs szabad példánya, egyik kérést sem tudja kielégíteni, tehát holtpont alakul ki. Mindkét kérés kielégítése tehát veszélyes, a rendszer holtpontra juthat.

Most tegyük fel, hogy csak P4 kérését teljesítjük. Ekkor a táblázatban P3 sora 8,1,7,2 marad, és a folyamat várakozik, P4 sora pedig 6,4,2,0 lesz. A rendszernek marad 2 szabad példánya. Tegyük fel most is, hogy a következő pillanatban a legrosszabb eset lép fel, azaz minden folyamat jelentkezik a még kérhető maximumra vonatkozó igényével, azaz P1 4, P2 7, P3 további 5, tehát összesen 7 (ez úgy értendő, hogy ha megkapja a várt 2 példányt, a következő pillanatban kérhet újabb 5-öt), P4 pedig 2 példányt kér. Mit tehet most a rendszer? P4 kérését teljesíteni tudja a 2 szabad példánnyal. P4 már nem kérhet többet, feltételezhetjük, hogy lefut és felszabadítja a nála lévő valamennyi erőforrást. Ekkor a rendszernek 6 szabad példánya lesz. A még várakozó folyamatok közül ki tudja elégíteni P1 kérését (4), P1 is lefuthat, és felszabadítja erőforrásait. Ezután a rendszernek már 9 szabad példánya lesz. Ezzel már P2 vagy P3 kérése is teljesíthetővé válik, bármelyiket teljesítjük először, a folyamat lefuthat és újabb erőforrások szabadulnak fel, tehát az utolsónak hagyott folyamat igénye is teljesíthető lesz. Megállapíthatjuk tehát, hogy ha a rendszer továbbra is kellő óvatosságot tanúsít, akkor nem alakul ki holtpont. Az az állapot tehát, amelyik az eredeti helyzetből P4 kérésének teljesítésével kialakul, biztonságos.

A bemutatott gondolatmenetet követi a problémát több erőforrásfajtára általánosan megoldó bankár-algoritmus (Dijkstra, 1965). A név onnan származik, hogy a probléma hasonló a bankok erőforrás-kihelyezési problémájához. Hitelezők fordulnak a bankhoz beruházásaik finanszírozásához szükséges hitelekért. Közlik a maximális hiteligényüket, amelyet a bank a megvalósítás ütemében folyósít. A bank véges tőkével rendelkezik. A hitelt csak az az ügyfél tudja visszafizetni, aki be tudta fejezni a beruházást, ehhez pedig szüksége van arra, hogy előbb-utóbb hozzájusson az igényelt hitel teljes összegéhez. Ha a bankár nem elég óvatos, ott állhat egy csomó félkész beruházással és kiürült kasszával, a hitelek következő részletét nem tudja folyósítani, ügyfelei pedig nem tudnak törleszteni. Hogy viselkedjen a bankár, hogy elkerülje az ilyen helyzeteket (kicsit életszerűtlenül tételezzük fel, hogy az állam segítségére sem számíthat)?

Legyen a folyamatok száma N, az erőforrástípusok száma M.

A folyamatoktól elvárjuk, hogy előzetesen bejelentik erőforrástípusonként a maximális igényeiket. Ezt a MAX nevű, NxM elemű mátrixban tartjuk nyilván.

Tároljuk a szabad erőforrások számát a SZABAD nevű, M elemű vektorban, az egyes folyamatok által már lefoglalt erőforrások számát a FOGLAL, NxM elemű mátrixban. Jelöljük a MAX – FOGLAL mátrixot MÉG névvel. MÉG ugyancsak NxM méretű, és elemei azt jelölik, hogy egy folyamat egy erőforrásból még legfeljebb mekkora igényt nyújthat be.

Jelentse FOGLAL[i] a Pi folyamat által az egyes erőforrásfajtákból foglalt mennyiséget tároló vektort, azaz a FOGLAL mátrix i-edik sorát, hasonlóan MÉG[i] a MÉG mátrix i-edik sorát.

A folyamatok várakozó kéréseit a KÉR mátrix (NxM elemű, i-edik sora a Pi folyamat várakozó kérésének adatait tartalmazza, jelölése KÉR[i]) tárolja.

Az algoritmus arra ad választ, hogy egy kiválasztott folyamat várakozó kérése kielégíthető-e úgy, hogy a rendszer biztonságos állapotban maradjon.

Az algoritmust két szinten tárgyaljuk. Az első szint ellenőrzi a kérést, és ha érdemes vele foglalkozni, módosítja a nyilvántartást a kérés teljesítése után kialakuló értékekre. Ezután megvizsgálja, hogy ez az állapot biztonságos-e. Ha igen, a kérés teljesíthető, a folyamat megkapja az erőforrásokat. Ha nem, a folyamatnak várakoznia kell, a nyilvántartást pedig vissza kell állítani a vizsgálat kezdetén fennálló értékekre.

Bankár-algoritmus (első szint): 1. A kérés ellenőrzése: Ha KÉR[i] > MÉG[i] akkor STOP; (HIBA, a folyamat hazudós) Ha KÉR[i] > SZABAD akkor VÉGE; (nincs elég, várni kell) 2. A nyilvántartás átállítása az új állapotra: SZABAD := SZABAD – KÉR[i]; FOGLAL[i] := FOGLAL[i] + KÉR[i]; 3. Biztonságosság vizsgálata 4. Ha nem BIZTONSÁGOS akkor állapot visszaállítása: SZABAD := SZABAD + KÉR[i]; FOGLAL[i] := FOGLAL[i]KÉR[i]; VÉGE; (várni kell) Egyébként kérés teljesítése; VÉGE; Biztonságosság vizsgálata (2. szint, előző 3. pont): B1. Kezdőértékek beállítása: GYŰJTŐ := SZABAD LEFUT[i] := hamis minden i-re (i=1,2,...,N) B2. Továbblépésre esélyes folyamatok keresése: Keress i-t, amelyre (LEFUT[i] = hamis ÉS MÉG[i] ≤ GYŰJTŐ); Ha van ilyen i, akkor GYŰJTŐ := GYŰJTŐ + FOGLAL[i]; LEFUT[i] := igaz; ismételd a B2. lépést; Egyébként folytasd a B3. lépéssel B3. Kiértékelés: Ha LEFUT[i] = igaz minden i-re (i=1,2,...,N), akkor BIZTONSÁGOS Egyébként NEM BIZTONSÁGOS; (A Pi folyamatok, amelyekre LEFUT[i] = hamis, holtpontra juthatnak)

A második szinten a biztonságosság vizsgálatát mutatjuk be. Az algoritmus alapgondolata, hogy szisztematikusan megkeresi azokat a folyamatokat, amelyek a legkedvezőtlenebb esetben is le tudnak futni. A legkedvezőtlenebb eset az, ha az adott pillanatban mindenki a még kérhető maximális igénnyel jelentkezik. A keresés minden lépésében olyan folyamatot keres, amelynek a még kérhető maximális igénye is kielégíthető a rendelkezésre álló erőforrásokkal. Ha van ilyen folyamat, akkor az kivehető a további vizsgálatból (biztosan le tud futni), a rendelkezésre álló készlet pedig megnövelhető a folyamat által birtokolt erőforrásokkal (hiszen a folyamat lefutása után ezek felszabadulnak), és a következő folyamat a megnövelt készlettel kereshető. Az algoritmus úgy zárul, hogy nem talál újabb folyamatot. Ennek egyik lehetséges oka, hogy elfogytak a folyamatok – ilyenkor az állapot biztonságos, hiszen minden folyamat biztosan le tud futni; másik lehetséges oka, hogy nincs köztük olyan, amelyiknek elég az éppen rendelkezésre álló készlet – ilyenkor az állapot nem biztonságos, hiszen a legkedvezőtlenebb esetben a maradék folyamatok holtpontra juthatnak.

A biztonságosságot vizsgáló algoritmus egy GYŰJTŐ nevű, M elemű vektort használ a lefutó folyamatoktól visszakapott erőforrások akkumulálására, valamint egy LEFUT nevű, N elemű logikai változó vektort azoknak a folyamatoknak a kipipálására, amelyeket továbbléptethetőnek talált.

Az algoritmusban a vektorok összehasonlítása (például MÉG[i] ≤ GYŰJTŐ reláció) akkor igaz, ha MÉG[i],[j] ≤ GYŰJTŐ[j] fennáll minden j-re (j=1,2,...,M), azaz a kérést valamennyi erőforrásfajtából ki lehet elégíteni.

Az algoritmus emlékeztet a korábban tárgyalt Coffman-féle holtpontdetektáló algoritmusra, a két algoritmus megszületésének időrendje azonban tárgyalási sorrendünkkel ellentétes.

A detektáló algoritmusokhoz hasonlóan egypéldányos erőforrások esetére ismét csak érdemes az erőforrásfoglalási gráfhoz fordulni, mert ott hatékonyabb algoritmusokat találhatunk.

A biztonságosság vizsgálatához szükséges előzetes információ egypéldányos esetben azt jelenti, hogy fogja-e használni a folyamat az adott erőforrást. Ennek jelölésére bevezethetünk a gráfon egy új éltípust, az ún. lehetséges kérés élet. Ez az él folyamattól erőforráshoz vezet, és jelöli, hogy egy folyamat kérheti az adott erőforrást. A biztonságosság vizsgálatakor a legrosszabb eset az, ha valamennyi lehetséges kérés fellép, azaz a lehetséges kérések valódi kérésekké válnak. Ha tehát egy kérés teljesítését mérlegeljük, kísérletképpen módosítjuk az erőforrásfoglalási gráfot, mintha odaadtuk volna az erőforrást (egy kérés él iránya megfordul és foglalás éllé válik). Ha most a lehetséges kérés éleket is figyelembe véve kört találunk a gráfon, a kérés teljesítésekor kialakuló állapot nem biztonságos, a kérést nem szabad teljesíteni.

Az elmondottakat a 2.11. ábra szemlélteti két folyamat és két erőforrás egyszerű esetére. A lehetséges kérés éleket szaggatott vonal jelzi. A kezdeti állapotot az (a) ábra mutatja. Először P1 kéri R1-et. A vizsgálathoz a rendszer bejegyzi a (b) ábrának megfelelően az R1 ® P1 foglalás élet. A gráfon láthatóan nincs kör, a kérést a rendszer teljesíti.

2.11. ábra. ábra - Potenciális kérések az erőforrásfoglalási gráfon

Potenciális kérések az erőforrásfoglalási gráfon


Ezután két lehetséges továbblépést mutat a (c) és a (d) ábra. Ha P2 kéri R2-t, a (c) ábra szerinti helyzet alakul ki a kérés teljesítése esetén. A gráfon kör van, az állapot nem biztonságos, a kérést nem szabad kielégíteni. P1 ugyanis bármikor kérheti R2-t, P2 pedig R1-et, és ekkor a rendszer holtpontra jutna. Ha viszont P1 kéri R2-t, a (d) ábra szerinti helyzet áll elő, a gráfon nincs kör, a rendszer biztonságos állapotban marad, a kérés teljesíthető.

2.2.7.8. Kombinált stratégiák

A holtpontprobléma kezelésének ismertetett módszerei kombináltan is alkalmazhatók. A rendszer erőforrásai például osztályokba sorolhatók. Az egyes osztályok sorszámozottak, a folyamatok betartják, hogy különböző osztályokhoz tartozó erőforrásokat csak az osztálysorrend szerint foglalnak le. Az egyes osztályokon belül más-más megelőzési vagy elkerülési stratégia is használható.

Egy ismert rendszer például a következő megoldást alkalmazta.

Az erőforrásokat négy osztályba sorolták:

  • Belső erőforrások (például rendszertáblák, leírók stb.). Mivel ez a rendszerfolyamatokat érinti, a megoldás a rendszertervező kezében van, aki betartathat egy egyezményes foglalási sorrendet, így az osztályon belül is alkalmazható a sorrendezésen alapuló megelőzés.

  • Memória. Menthető állapotú erőforrás (háttértárra másolás, visszatöltés), erőszakos elvétel használható megelőzésre.

  • Készülékek és fájlok. Az osztályon belül elkerülés alkalmazható a használati igény előzetes bejelentése alapján.

  • Munkaterület a lemezen. Általában ismert méretű igények vannak, egyszerre kell kérni a szükséges méretet, nincs „rákérés”.

Az osztályok között a felsorolás szerinti foglalási sorrendet kellett betartani.

2.2.7.9. Kommunikációs holtpontok

Holtponthelyzet nemcsak erőforráshasználat miatt alakulhat ki, hanem a fo­lya­matok tetszőleges olyan együttműködése során, amelyik a folyamatok körkörös várakozására vezethet.

Tételezzünk fel például egy kliens-szerver architektúrájú rendszert, ahol az ügyfelek és a szolgáltatók is folyamatok. Ebben a rendszerben az ügyfél küld egy kiszolgálást kérő üzenetet a szolgáltatónak, majd vár a válaszra. Ha a szolgáltatói és ügyfél szerepeket nem sikerül statikusan elkülöníteni, előfordulhat, hogy egy folyamat egyik kapcsolatában ügyfél, egy másikban azonban szolgáltató. Az is előállhat, hogy egy szolgáltatónak egy ügyfél kiszolgálása közben ügyfélként kell más szolgáltatóhoz fordulnia. Előfordulhat, hogy ilyenkor az ügyfél-kiszolgáló lánc záródik, tehát egy kiszolgálást kérő folyamat a választ csak akkor kaphatja meg, ha a közben – esetleg több áttételen keresztül – hozzá, mint kiszolgálóhoz érkező kérésre válaszol. Ha a folyamat erre nincs felkészítve, ebben az esetben holtpont alakul ki. Az ehhez hasonló problémák kezelésében segítenek a folyamaton belül kialakítható szálak, amelyek különösen a szerver szerepet (is) betöltő folyamatok programozásakor hasznosak.

A kommunikáció által okozott várakozások ugyancsak szemléltethetők irányított gráfokkal, amelyek csomópontjai folyamatok, irányított élei pedig a várakozó folyamattól vezetnek ahhoz a folyamathoz, amelyiknek az üzenetet küldenie kellene. Ilyen várakozási gráf (wait-for graph) egyébként az erőforrásfoglalási gráf redukálásával is létrejöhet. A kördetektáló algoritmusok értelemszerűen itt is használhatók.

2.2.8. Éhezés

A holtpont mellett a folyamatok működésének egy másik zavara lehet az éhezés. Az éhezés azt jelenti, hogy egy várakozó folyamat nincs ugyan holtponton, de nincs rá garancia, hogy véges időn belül továbbindulhasson.

A szinkronizációs eszközök tárgyalásakor bevezettük az ütemezés fogalmát. Azokban az esetekben, amikor több várakozó folyamat közül kell továbbindulót választani, a választást gyakran nem célszerű a véletlenre bízni, hanem meghatározott algoritmus szerint kell dönteni. A rendszer a szemaforokhoz, erőforrásokhoz, egyéb szinkronizációs objektumokhoz várakozási (ütemezési) sorokat rendel, amelyeket meghatározott algoritmusok szerint kezel (így még az esetleges véletlen kiválasztás is tudatossá tehető).

Az ütemezés leggyakoribb alapalgoritmusai az érkezési sorrend szerinti (FIFO) és a prioritásos ütemezés.

Egy ütemezést tisztességesnek (fair) nevezünk, ha garantálja, hogy egy várakozási sorból minden folyamat véges időn belül továbbindulhat, ameny-nyiben a rendszerben véges számú folyamat működik és a rendszerben nincs holtpont vagy hibás folyamat (amelyik például nem enged el egy megszerzett erőforrást). Ellenkező esetben az ütemezés tisztességtelen (unfair).

Tisztességes ütemezés például az érkezési sorrend szerinti kiszolgálás, tisztességtelen a statikusan rögzített prioritás szerinti kiszolgálás (ilyenkor nincs garancia arra, hogy egy alacsony prioritású folyamat valaha is hozzájut az erőforráshoz, ha mindig van nála magasabb prioritású igény).

Megjegyzések:

  • Az éhezés nem jelent holtpontot.

  • Külső eseményre (például kezelői beavatkozás) való meghatározatlan idejű várakozás nem jelent sem éhezést, sem holtpontot.

  • Tisztességtelen ütemezés tudatosan is alkalmazható, csak számolni kell a kevésbé fontos funkciók kiesésével a terhelés (a futtatandó folyamatok száma) növekedésekor.

2.2.9. Klasszikus konkurens problémák

Tekintsünk át néhány olyan feladatot, amelyek megoldása jellegzetesen együttműködő folyamatokra vezet! Tapasztalatok szerint a folyamatok használatával megoldható gyakorlati problémák többsége visszavezethető ezeknek a klasszikussá vált feladatoknak valamelyikére. Éppen ezért ezek a problémák egy-egy újabb együttműködési modell, szinkronizációs, vagy kommunikációs eszköz kidolgozása esetén gyakran szerepelnek mint teszt és bench­mark esetek.

2.2.9.1. Termelő–fogyasztó probléma

A rendszerben egymással párhuzamosan egy termelési folyamat, valamint egy fogyasztási folyamat zajlik. A Termelő saját ritmusában és algoritmusa szerint előállít valamit (például adatokat), amit egy raktárba tesz (Buffer).

2.12. ábra. ábra - A termelő-fogyasztó probléma

A termelő-fogyasztó probléma


A Fogyasztó saját ritmusában, saját algoritmusa szerint működve felhasználja a termelő által előállított terméket (adatokat), a soron következőt mindig a raktárból véve elő.

A Termelő és a Fogyasztó sebességére nincs kikötésünk. A Buffer kiegyenlítő hatású, kisebb sebességingadozások esetén nem akadnak fenn a folyamatok, legfeljebb a Termelő lelassulása esetén a raktárkészlet fogy, a Fogyasztó lelassulása esetén pedig növekszik. Mivel a Buffer kapacitása véges, elvárjuk, hogy ha megtelt a Buffer, a Termelő várjon a következő elem betételével, amíg felszabadul egy hely, illetve ha üres a Buffer, a Fogyasztó várjon, amíg érkezik egy elem. Ugyancsak elvárjuk, hogy az elemeket a Fogyasztó ugyanabban a sorrendben dolgozza fel, ahogyan a Termelő előállította azokat.

Hogyan tudnánk olyan programot írni egy adott programozási nyelvet és operációs rendszert feltételezve, amelyik végrehajtásakor a Termelő és a Fogyasztó párhuzamosan hajtódhat végre, és a Buffer kezelése is helyes lesz?

2.2.9.2. Írók–olvasók problémája

Egy adatszerkezetet (például egy hirdetőtáblát vagy egy fájlt) többen kívánnak írni is és olvasni is. Az írások és olvasások csak bizonyos rendszabályok betartása esetén nem zavarják össze egymást:

  • egyidejű olvasásokat tetszőleges számban megengedünk, mert nem zavarják egymást,

  • írás és olvasás nem folyhat egyidejűleg, mert aki olvas, félig átírt dolgokat látna, amiből valami zagyvaság jöhet ki,

  • több írás nem folyhat egyidejűleg, mert ha két írás átlapolódhatna, a végeredmény egyik fele az egyik írás eredménye lehet, a másik fele a másiké, ami nagy valószínűséggel ismét csak zagyvaságot eredményez.

Ennek megfelelően elvárjuk, hogy írás csak akkor kezdődhessen, ha sem írás, sem olvasás nincs folyamatban, olvasás viszont kezdődhet ha más olvasások már folyamatban vannak.

2.13. ábra. ábra - Az írók-olvasók problémája

Az írók-olvasók problémája


Megjegyezzük, hogy ésszerű lehet még egy kikötés annak elkerülésére, hogy a folyamatosan érkező olvasók miatt az írni szándékozók a végtelenségig ne jussanak szóhoz: ha van várakozó író, akkor újabb olvasó már ne kerüljön sorra, amíg a várakozó írók nem végeztek (írók–olvasók II. probléma).

Hogyan tudnánk olyan programot írni, amelyik kifejezi az írók és olvasók párhuzamos működését és biztosítja a megadott szabályok betartását (nyelv, operációs rendszer)?

2.2.9.3. Az étkező filozófusok problémája

Egy tibeti kolostorban öt filozófus él. Minden idejüket egy asztal körül töltik (2.14. ábra). Mindegyikük előtt egy tányér, amiből sohasem fogy ki a rizs. A tányér mellett jobb és bal oldalon is egy-egy pálcika található a rajz szerinti elrendezésben.

2.14. ábra. ábra - Az étkező filozófusok problémája

Az étkező filozófusok problémája


A filozófusok életüket az asztal melletti gondolkodással töltik. Amikor megéheznek, étkeznek, majd ismét gondolkodóba esnek a következő megéhezésig. És ez így megy az idők végezetéig. Az étkezéshez egy filozófusnak meg kell szereznie a tányérja melletti mindkét pálcikát. Ennek következtében amíg eszik, szomszédai nem ehetnek. Amikor befejezte az étkezést, leteszi a pálcikákat, amelyeket így szomszédai használhatnak.

Hogyan kell viselkedniük a filozófusoknak, hogy ne vesszenek össze a pálcikákon, ne kerüljenek olyan megoldhatatlan probléma elé, amin fenn-akadva többé nem tudnak sem enni, sem gondolkozni (például, ha mindegyikük felveszi mondjuk a bal pálcikát és nem teszi le, az holtponthelyzet), és egyikük se haljon éhen, azaz ha enni akar, ez egy idő után a leggyámoltalanabbjuknak is sikerüljön? Hogyan tudnánk olyan programot írni, amelyik leírja a filozófusok viselkedését?

2.2.9.4. Adatfolyamok illesztése

Ez a probléma a CPASCAL (Concurrent Pascal) nyelv bevezetésének szokásos mintapéldája. Eredetileg arról szól, hogy adott egy kártyaolvasó és egy nyomtató. A kártyaolvasóba helyezett kártyák egy hosszabb szöveget tartalmaznak, amit ki kell nyomtatni. Maga a szöveg egy bekezdésekre tagolt karakterfolyam, amelyben az új bekezdést speciális karakter jelzi (NL). Egy kártya 80 karaktert tud tárolni, a kártyaolvasóról tehát nyolcvan karakteres blokkokban érkezik az adatfolyam. A szöveget lapokra tördelve, lapszámozással ellátva, a bekezdéseket külön sorban kezdve, soronként 132 pozíciót használva kell kinyomtatni.

A probléma általánosabban úgy fogalmazható meg, hogy egy beérkező, sajátosan strukturált és ütemezett adatfolyamot egy más struktúrájú és ütemezésű adatfolyamként kell továbbítani. Modern változatban könnyen fogalmazhatnánk hasonló feladatot szövegfájlok kezelése, vagy hálózati adatátviteli rendszerek protokolljainak illesztése témakörében.

2.15. ábra. ábra - Adatfolyamok illesztésének problémája

Adatfolyamok illesztésének problémája


A kérdés ismét az, hogy hogyan írhatunk olyan programot, amelyik maximális sebességgel tudja működtetni mindkét oldalon a készülékeket, és minél tisztább szerkezetben tudja megoldani az eltérő struktúrák illesztését. (Ennél a feladatnál még a folyamatokra bontás sem adott. Ha a feladat megoldásával próbálkozunk, érdemes kísérletet tenni először egyetlen szekvenciális programmal, azaz egyetlen folyamattal, majd legalább két, egy olvasó és egy nyomtató folyamatra való felbontással.)

A bemutatottakon kívül további klasszikus problémákat is találhatunk az irodalomban. Valamennyinek lényeges eleme, hogy több aktív szereplő (több folyamat) együttműködését kell megoldani és leírni. Ajánljuk az olvasónak, hogy vágjon neki, és próbáljon kedvenc programnyelvén (persze annak pszeu­do változata is megteszi) megoldási kísérleteket tenni a fenti feladatokra. Egyelőre tételezze fel, hogy írhat olyan programrészleteket, amelyek majd valahogy folyamatként, egymással párhuzamosan fognak végrehajtódni. Válasszon valamilyen együttműködési modellt (közös memória vagy üzenetváltás), és használja a már bemutatott szinkronizációs, kommunikációs eszközök közül azokat amelyeket jónak lát. Tételezze fel, hogy ezek rendszerhívásként elérhetőek.

2.2.10. Folyamatokból álló rendszerek leírása nyelvi szinten

Ahhoz, hogy az előző pontban bemutatott feladatokat megoldó programokat írhassunk, megfelelő nyelvi eszközök szükségesek annak kifejezésére, hogy mely programrészletek lesznek önálló folyamatok, azaz hajtódhatnak végre párhuzamosan, valamint milyen műveletekkel oldják meg a kommunikáció és a szinkronizáció problémáit. Ezek nélkül csak „kézi” módszereink vannak: egyenként megírjuk a programokat, valahogyan elindítjuk őket folyamatként az operációs rendszer kezelői felületéről, és a szinkronizációs, kommunikációs rendszerhívásokat megpróbáljuk a nyelvi interfészen keresztül elérni.

Konkurens (párhuzamosan végrehajtható ágakat tartalmazó) programok készítésének igénye először az operációs rendszerek programozásakor vetődött fel, azonban a multiprogramozott, majd a multitaszkos rendszerek megjelenésekor az alkalmazásfejlesztők ilyen irányú igénye is megjelent. A nyelveknek egyrészt tehát a párhuzamosság leírására, másrészt a folyamatok együttműködésének leírására kellett modelleket és eszközöket adniuk. A kö­vet­kezőkben az erre kialakult megoldásokat mutatjuk be röviden.

2.2.10.1. A párhuzamosság leírása

Tegyük fel, hogy egy feladat megoldása során olyan műveleteket használunk fel, amelyeket már nem tudunk, vagy nem akarunk tovább bontani, részletezni (elemi folyamatok). A megoldáshoz meg kell adnunk azt is, hogy ezek az elemi műveletek milyen vezérléssel (milyen sorrendben, milyen feltételek mellett stb.) hajtandók végre. Ha folyamatokban gondolkozunk, lehetnek ezek között párhuzamosan végrehajthatók, és lehetnek olyanok, amelyek csak egy másik elemi folyamat után hajthatók végre. Ahhoz képest, hogy akár minden elemi folyamat párhuzamosan futhatna, egy sereg precedenciát írunk elő. A végeredményt egy precedenciagráfon ábrázolhatjuk (2.16. ábra).

2.16. ábra. ábra - Precedenciagráf

Precedenciagráf


A precedenciagráfon bármelyik irányított úton elhelyezkedő elemi folyamatok (Ux) egyetlen folyamattá is összevonhatók. Bármely két utasítás, amelyet nem köt össze irányított út, párhuzamosan is végrehajtódhat, azaz konkurens.

A precedenciagráf szemléletesen kifejezi a párhuzamosságot, de síkban kell ábrázolni, míg a programszövegek lineáris sorozatok.

A programnyelvi leírásra az első javaslat a fork-join operátorok alkalmazása volt. A fork C utasítás hatására a végrehajtás párhuzamosan elágazik, az egyik szál a következő utasításon, a másik a C címkén folytatódik. A join N utasítás pedig N szál összefuttatását oldja meg. Az utasítás több szálon is végrehajtódhat. Minden végrehajtása eggyel csökkenti az utasításhoz rendelt számláló értékét, amelynek kezdőértéke N volt. Az utasítás minden őt végrehajtó szálat elnyel, amíg a számláló le nem nullázódik, csak azt engedi tovább, amelyik a nullára csökkenést előidézte.

A fork-join páros a goto-hoz hasonló anomáliákhoz vezetett (áttekinthetetlen vezérlési szerkezet), így helyette egy strukturált utasítás bevezetését javasolták, a parbegin-parend párt. Ez a megoldás valóban áttekinthetőbbé és biztonságosabbá tette a nyelvi leírást, de nem írható le vele tetszőleges precedenciagráf, csak járulékos szinkronizációs műveletekkel.

A megvalósított első konkurens nyelvben, a CPascalban (és később több másikban is, például MODULA, ADA) az explicit folyamatdeklaráció (process declaration) használatos annak kifejezésére, hogy egy programegység folyamatként, azaz más hasonló programegységgel párhuzamosan hajtódhat végre. A folyamatdeklarációk igen hasonlóak az eljárás­deklarációkhoz.

2.2.10.2. Az együttműködés nyelvi modelljei

A párhuzamos végrehajtású programrészek az egygépes rendszerekben közös memórián működhettek együtt – megfelelő szinkronizációt feltételezve. A szemaforra alapozott szinkronizációt a párhuzamosságot megengedő ma­gas­szintű nyelvekben nem találták elég biztonságosnak, hiszen például egy kölcsönös kizárás megoldása esetén a programozó következmények nélkül elfelejtheti a használatát, vagy ami legalább olyan kellemetlen, elfelejtheti a felszabadítását. A szemafor és a védett objektum között csak a prog­ra­mozó(k) tudatában van kapcsolat, így az objektumot bármelyik folyamat nyugodtan használhatja a szemafor lefoglalása nélkül.

A kölcsönös kizárás megoldására az első javasolt magasszintű eszköz a kritikus régió volt. A javaslat szerint a változódeklarációkban jelölni kellett a védett közös változókat (shared), az ilyen változókra pedig csak a változóhoz tartozó kritikus régióban hivatkozhat a program (ha X shared-ként deklarált: region X do...<X használata>...od). A megoldás lehetővé teszi a fordítási időben történő ellenőrzést az esetleges régión kívüli hivatkozások felderítésére.

A kritikus régióval meglehetősen nehézkesen kezelhetők azok a helyzetek, amelyekben egy feltételvizsgálattól teszik függővé a folyamat a szakaszba való belépést, de már magának a feltételvizsgálatnak az elvégzéséhez is a védett változót kell használni. Erre kínált megoldást a feltételes kritikus régió.

A következő jelentős lépcsőfok a CPascal nyelvi modellje, amelyik az absztrakt adatszerkezetek adatrejtési elveit (encapsulation) és a konkurens végrehajtás lehetőségét ötvözte. Bevezette a monitor rendszertípust. A monitor három fő összetevőből áll. Vannak privát, kívülről el nem érhető adatai, ezeken saját, kívülről is hívható eljárásai tudnak csak műveletet végezni, valamint van egy inicializáló kódrésze. A kívülről hívható eljárásokra garantált, hogy kölcsönös kizárással futnak le, és várakozási sor szerveződik rájuk. Az eljárásokban a feltételes kritikus szakasz funkciójának megvalósítására egy speciális változótípust (queue) vezettek be, amely delay és continue műveletekkel kezelhető. Egy delay(x:queue) művelet várakozásba helyezi a hívó folyamatot, és lehetővé teszi, hogy más lépjen be a kritikus szakaszba. A folyamat addig vár, amíg valaki végre nem hajt egy continue(x:queue) mű­veletet. Megjegyzendő, hogy a continue hatása nem őrződik meg, ha nincs várakozó, a jelzés elszáll.

Két maradandó hatású nyelvi modell – nem konkrét nyelv – született a ’70-es években: az együttműködő folyamatok CSP (Communicating Sequen­tial Processes) és az elosztott folyamatok DP (Distributed Processes) modell.

Mindkettőt az motiválta, hogy megjelentek az egymással adatátviteli vonalakon, vagy hálózaton összekapcsolt számítógépek, és a folyamatmodellt és a folyamatok együttműködésének modelljét lehetőleg úgy kellett kialakítani, hogy azonos processzoron futó, és különböző processzorokon futó folyamatokra is alkalmazható legyen.

A CSP-modell üzenetváltással együttműködő folyamatokat kezel, bevezeti az őrzött parancs (guarded command), az alternatíva, és az ismétléses alternatíva szerkezeteket, amelyekkel a több belépési ponttal rendelkező, konkurens hívásoknak kitett szerver típusú folyamatok működése is leírható, amelyek nem tudják előre, hogy a következő hívásuk honnan érkezik.

A DP-modell hasonló alapokról indul, a folyamatok közötti kommunikációt azonban az eljáráshívás és paramétercsere szemantikájára alapozza (távoli eljáráshívás, remote procedure call).

A ’80-as évek elején érett szabvánnyá az ADA nyelv, amely szintetizálta a kor valamennyi elméleti eredményét. A párhuzamos programrészek létrehozására taszkok deklarálhatók, amelyek a távoli eljáráshívás elvén működhetnek együtt. A szerver típusú folyamatok a CSP-modellben javasolt alternatív szerkezetet (select), és az őrzött parancsoknak megfelelő szerkezetet (when F => accept <entry-call>) használhatják a többfelől várható hívások fogadására.

A további nyelvek a párhuzamosság és az együttműködés alapsémái tekintetében már nem hoztak átütő újdonságot. Napjainkban a legelterjedtebben a C nyelvi könyvtárak formájában megvalósított PVM (Parallel Virtual Machine), vagy MPI (Message Passing Interface), valamint a Java nyelv mo­delljei használatosak a programszinten párhuzamos végrehajtás területén.