Алгоритм Пітерсона

Алгоритм Пітерсона, також відомий як розв'язок Пітерсона (англ. Peterson's algorithm, Peterson's solution)  алгоритм паралельного програмування для взаємного виключення, який дозволяє двом процесам спільно використовувати одновикористовний ресурс без конфліктів, застосовуючи лише спільну пам'ять для зв'язку. Сформульовано Гарі Л. Пітерсоном 1981 року^[1]. Хоча у початковому формулюванні алгоритм Пітерсона працює лише з двома процесами, його можна узагальнити на декілька процесів^[2].

Алгоритм

flag[0] = 0;
flag[1] = 0;
turn;
   
P0: flag[0] = 1;                                        P1: flag[1] = 1;
    turn = 1;                                               turn = 0;
    while (flag[1] == 1 && turn == 1)                       while (flag[0] == 1 && turn == 0)
    {                                                       {
           // очікуваня                                             // очікування
    }                                                       }                                 
    // критична секція                                      // критична секція 
       ...                                                     ...
    // кінець критичної секції                              // кінець критичної секції
    flag[0] = 0;                                            flag[1] = 0;

Алгоритм має дві змінні flag і turn. Якщо flag встановлений в 1, то процес намагається увійти до критичної секції. Вхід до критичної секції надається процесу P0, якщо P1 не намагається увійти до своєї критичної секції або P1 надав пріоритет P0 встановленням turn в 0.

Алгоритм задовільняє трьом головним критеріям розв'язку задачі критичної секції^[3]:

1. Взаємне виключення
2. Прогрес
3. Обмежене очікування

Взаємне виключення

Процеси не можуть перебувати в критичній секції одночасно: якщо P0 у своїй критичній секції, тоді flag[0] дорівнює 1 і:

• або flag[1] дорівнює 0 (значить P1 вже завершив свою критичну секцію)
• або turn дорівнює 0 (значить P1 намагається увійти до критичної секції, але змушений очікувати).

В обох випадках, P1 не може перебувати в своїй критичній секції.

Прогрес

Прогрес визначається таким чином: якщо жоден процес не виконує свою критичну секцію і деякі процеси намагаються увійти до своєї критичної секції, тоді лише ці процеси враховуються під час прийняття рішення, хто з них увійде до критичної секції наступним. Це рішення не може відкладатися необмежено^[3]. Процес не може увійти до критичної секції одразу після виходу з неї, якщо інший процес вже встановив свій прапорець, висловивши цим своє бажання також увійти до критичної секції.

Обмежене очікування

Обмежене очікування означає, що «після здійснення будь-яким процесом запиту на вхід до критичної секції і до того, як цей запит буде задоволено, обмежується кількість входів до критичної секції, дозволених іншим процесам»^[3]. В алгоритмі Пітерсона процес очікуватиме входу до критичної секції не довше, ніж один вхід іншого процесу.

Зауваження

У випадку роботи на апаратному рівні, алгоритм Пітерсона зазвичай не потребує атомарного доступу. Деякі процесори мають особливі команди, такі як test-and-set або compare-and-swap, які, шляхом блокування шини пам'яті, може бути застосовано для забезпечення взаємного виключення в SMP системах.

Примітки

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. Silberschatz. Operating Systems Concepts: Seventh Edition. John Wiley and Sons, 2005., Pages 194

Портал «Програмування»