Алгоритм Пітерсона, також відомий як розв'язок Пітерсона () алгоритм паралельного програмування для взаємного виключення, який дозволяє двом процесам спільно використовувати одновикористовний ресурс без конфліктів, застосовуючи лише спільну пам'ять для зв'язку. Сформульовано Гарі Л. Пітерсоном 1981 року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)..
Алгоритм flag = 0; flag = 0; turn;
P0: flag = 1; P1: flag = 1; turn = 1; turn = 0; while (flag == 1 && turn == 1) while (flag == 1 && turn == 0)
// очікуваня // очікування
// критична секція // критична секція ... ... // кінець критичної секції // кінець критичної секції flag = 0; flag = 0; Алгоритм має дві змінні flag і turn. Якщо flag встановлений в 1, то процес намагається увійти до критичної секції. Вхід до критичної секції надається процесу P0, якщо P1 не намагається увійти до своєї критичної секції або P1 надав пріоритет P0 встановленням turn в 0.
Алгоритм задовільняє трьом головним критеріям розв'язку задачі критичної секціїSilberschatz. Operating Systems Concepts: Seventh Edition. John Wiley and Sons, 2005., Pages 194: Взаємне виключення Прогрес Обмежене очікування
Взаємне виключення Процеси не можуть перебувати в критичній секції одночасно: якщо P0 у своїй критичній секції, тоді flag дорівнює 1 і: або flag дорівнює 0 (значить P1 вже завершив свою критичну секцію) або turn дорівнює 0 (значить P1 намагається увійти до критичної секції, але змушений очікувати). В обох випадках, P1 не може перебувати в своїй критичній секції.
Прогрес Прогрес визначається таким чином: якщо жоден процес не виконує свою критичну секцію і деякі процеси намагаються увійти до своєї критичної секції, тоді лише ці процеси враховуються під час прийняття рішення, хто з них увійде до критичної секції наступним. Це рішення не може відкладатися необмежено. Процес не може увійти до критичної секції одразу після виходу з неї, якщо інший процес вже встановив свій прапорець, висловивши цим своє бажання також увійти до критичної секції.
Обмежене очікування Обмежене очікування означає, що «після здійснення будь-яким процесом запиту на вхід до критичної секції і до того, як цей запит буде задоволено, обмежується кількість входів до критичної секції, дозволених іншим процесам». В алгоритмі Пітерсона процес очікуватиме входу до критичної секції не довше, ніж один вхід іншого процесу.
Зауваження У випадку роботи на апаратному рівні, алгоритм Пітерсона зазвичай не потребує атомарного доступу. Деякі процесори мають особливі команди, такі як test-and-set або compare-and-swap, які, шляхом блокування шини пам'яті, може бути застосовано для забезпечення взаємного виключення в SMP системах.
Примітки