Peterson-algoritmus
Peterson-algoritmus egy konkurens programozási algoritmus, mely lehetővé teszi közös memóriaterületet használó programok futását konfliktusok nélkül, a kölcsönös kizárás módszerével.
Gary L. Peterson (amerikai matematikus) formulázta meg először ezt a módszert 1981-ben,[1] mely segítségével két processz konfliktusmentesen tud futni egy gépen. A módszer kiterjeszthető több processzre is.[2]
Az algoritmus szerkesztés
Az algoritmus két változót használ: a ‘flag’ és a ‘turn’ nevű változókat. A ‘flag’ változó igaz értéke jelzi, hogy egy processz be akar lépni a kritikus területre. A ‘turn’ változó a sorra kerülő processz azonosítóját tartalmazza. P0 processz számára engedélyezett a belépés a kritikus területre, ha P1 processz nem akar belépni, vagy ha P1 prioritást ad P0-nak azzal, hogy a ‘turn’ változót 0-ra állítja.
//flag[] boolean tömb; turn egész
flag[0] = false;
flag[1] = false;
turn;
| |
P0: flag[0] = true;
turn = 1;
while (flag[1] == true && turn == 1)
{
// aktív várakozás
}
// kritikus szakasz
...
// kritikus szakasz vége
flag[0] = false;
|
P1: flag[1] = true;
turn = 0;
while (flag[0] == true && turn == 0)
{
// aktív várakozás
}
// kritikus szakasz
...
// kritikus szakasz vége
flag[1] = false;
|
Az algoritmus kielégíti a három lényeges kritériumot, mely megoldja a kritikus terület használatának a problémáját.
Ez a három kritérium: kölcsönös kizárás, progressz, korlátos várakozás.[3]
Kölcsönös kizárás szerkesztés
P0 és P1 sohasem lehet egyidőben a kritikus memóriaterületen. Ha P0 a kritikus területen van, akkor a ‘flag(1)’ hamis (ami azt jelzi, hogy P1 elhagyta a kritikus területet), vagy ‘turn’ 0 (ami azt jelenti, hogy P1 most éppen megpróbál belépni a területre, de ‘nagyvonalúan’ várakozik). Mindkét esetben, P1 nem lehet a kritikus területen, ha P0 ott van.
Progressz szerkesztés
A progressz a követkőképpen definiálható: Ha nincs processz a kritikus területén, és néhány processz szeretne belépni, akkor csak az a processz vehet részt a döntésben a következő belépőről, amely nem hajt végre maradék részen programot. Ez a kiválasztás nem halogatható végtelenségig.[3] Egy processz nem léphet be újra azonnal a kritikus területére, ha más processz ‘flag’ változója jelzi, hogy be kíván lépni a területre.
Korlátos várakozás szerkesztés
Ez azt jelenti, hogy létezik egy limit, mely korlátozza az időt, miután egy processz jelezte, hogy be szeretne lépni. Peterson-algoritmusában nem vár egy kérésnél többet: miután a processz megkapta a prioritást, el kell végeznie a feladatot, majd 0-ra állítja a “flag”-jét, jelezve ezzel, hogy beléphet más processz a kritikus területre.
Megjegyzés szerkesztés
Nincs mindenhol szükség a Peterson-algoritmus alkalmazására. Néhány processzornak vannak speciális utasításai, mint például: test-and-set vagy compare-and-swap, melyek blokkolják a memóriasínt és gondoskodnak a kölcsönös kizárásról az SMP (szimmetrikus többprocesszoros) rendszereknél.
A korszerű CPU-knál a memóriahozzáférést hatékony memória-hozzárendelő utasításokkal kezelik.
Konkurens programokat kezelő CPU-kban garantált „atomi működés” biztosítja, hogy egy processz a többi résztvevőnek úgy tűnjék, hogy azonnal végrehajtódik és nem megszakítható.
Ilyenek a x86 processzoroknál az XCHG, és az egyéb architektúrák egyes utasításai (pl. a load-link/store-conditional (Alpha), MIPS, PowerPC). Ezen utasítások célja a hatékony szinkronizálás.
Irodalom szerkesztés
- G. L. Peterson: Myths About the Mutual Exclusion Problem. (hely nélkül): Information Processing Letters 12(3). 1981. 115–116. o.
- Silberschatz: Operating Systems Concepts: Seventh Edition. (hely nélkül): John Wiley and Sons. 2005.
Kapcsolódó szócikkek szerkesztés
Források szerkesztés
- ↑ G. L. Peterson: "Myths About the Mutual Exclusion Problem", Information Processing Letters 12(3) 1981, 115–116
- ↑ As discussed in Operating Systems Review, January 1990 ("Proof of a Mutual Exclusion Algorithm", M Hofri).
- ↑ a b Silberschatz. Operating Systems Concepts: Seventh Edition. John Wiley and Sons, 2005., Pages 194
