2. tétel - Szinkronizáció I.

Ismertesse Dekker és Peterson algoritmusát kölcsönös kizárásra! Mire szolgál és milyen elven működik Lamport Bakery algoritmusa?

A kód azon részét, ahol a közös, függést okozó változók vannak, kritikus szakasznak nevezzük. Cél: a kritikus szakaszban egyszerre csak egy szál legyen.

Dekker algoritmusa

• Két szál verseng, hogy a kritikus szakaszba léphessen
• Az algoritmus a szál indexétől függően eltérően viselkedik.
• flag[i] true értéket vesz fel, ha az i indexű szál be kíván lépni a kritikus szakaszba
• Ha a szálak egyszerre kezdik meg a belépést, akkor a turn változó értéke jelzi, hogy melyik szál következik

• A 0 indexű szál a flag[0] értékét igazra állítja, és megvizsgálja a flag[1] értékét.
• Ha hamis, akkor a szál belép a kritikus szakaszba. Kilépéskor pedig visszaállítja hamisra a saját flagjét.
• A gyakorlatban a turn dönt a belépésről azokban az esetekben, amikor a belépést a szálak esetleg egyszerre kezdik meg: a turn értéke jelzi, hogy mely szál következik; a másik szál várakozik.
• Ha a turn azt jelzi, hogy a másik szál van soron, akkor a szál leveszi a flagjét, és várakozik a turn megváltozására. Fontos észrevenni, hogy a flag hamisra állítása fontos lépés, hisz a másik szál esetlegesen ezt vizsgálja a belépési protokolljában, így nem léphet be amíg az true értékű.

Előfordulhat olyan eset, hogy:

• T₀ a kritikus szakaszban van, T1 várakozik
• T₀ a kilépés után egyből belépést kezdeményez, T1 nem tud időben kijönni a várakozó állapotból. Ekkor sérül a fair kiszolgálás.

Peterson algoritmusa

• A turn változó a belépési feltétel részeként szerepel
• A flag átállítását követően a turn a másik szálra fog mutatni, hogy az következik a sorban.
• Ebben az eseten megfigyelhető a fair viselkedés, vagyis amelyik szál hamarabb kezdi meg a belépést, garantáltan az fog előbb belépni a kritikus szakaszba. Ekkor ugyanis a turn érvényes értéke az utolsó beállított érték lesz.

Lamport algoritmusa

Lamport Bakery algoritmusa több szál kölcsönös kizárását hivatott megoldani, amely a pékségekben használt várósoron alapul.

• Minden szál egy sorszámot kap, és mindig a legkisebb sorszámú kerül kiszolgálásra, addig a többi várakozik.
• Az algoritmusban előre ismert a szálak száma.
• Kezdetben minden szám egy sorszámot kap, eggyel nagyobbat az utolsónál.
• Van egy choosing tömb. choosing[i] igaz, ha az i indexű szál még nem kapott sorszámot.
• Amíg a choosing tömb bármelyik eleme igaz, a szálak várakoznak,tehát megvárják, hogy minden szál sorszámhoz jusson.
• A várakozás megvalósításában, ha egy B szál már a belépési protokollban vagy a kritikus szakaszban tartózkodik, és a sorszáma kisebb, vagy egyező és az indexe kisebb, mint A szálnak, akkor A szál várakozni kényszerül.