Peterson-algoritmus

A Wikipédiából, a szabad enciklopédiából

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 | forrásszöveg szerkesztése]

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 | forrásszöveg szerkesztése]

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 | forrásszöveg szerkesztése]

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 | forrásszöveg szerkesztése]

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 | forrásszöveg szerkesztése]

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 | forrásszöveg szerkesztése]

  • 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ásszöveg szerkesztése]

Források[szerkesztés | forrásszöveg szerkesztése]

  1. G. L. Peterson: "Myths About the Mutual Exclusion Problem", Information Processing Letters 12(3) 1981, 115–116
  2. As discussed in Operating Systems Review, January 1990 ("Proof of a Mutual Exclusion Algorithm", M Hofri).
  3. ^ a b Silberschatz. Operating Systems Concepts: Seventh Edition. John Wiley and Sons, 2005., Pages 194