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,G. L. Peterson: "Myths About the Mutual Exclusion Problem", Information Processing Letters 12(3) 1981, 115–116 mely segítségével két processz konfliktusmentesen tud futni egy gépen. A módszer kiterjeszthető több processzre is.As discussed in Operating Systems Review, January 1990 ("Proof of a Mutual Exclusion Algorithm", M Hofri).
Az algoritmus 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 = false; flag = false; turn;P0: flag = true; turn = 1; while (flag == true && turn == 1)
// aktív várakozás
// kritikus szakasz ... // kritikus szakasz vége flag = false;P1: flag = true; turn = 0; while (flag == true && turn == 0)
// aktív várakozás
// kritikus szakasz ... // kritikus szakasz vége flag = 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.Silberschatz. Operating Systems Concepts: Seventh Edition. John Wiley and Sons, 2005., Pages 194
Kölcsönös kizárá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 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. 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 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 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
Kapcsolódó szócikkek Szymanski-algoritmus Dekker-algoritmus Szemafor Algoritmus Processzor Programozás CPU
Jegyzetek
Kategória:Algoritmusok