D-OS-Ch06c-Peterson_Solution

Peterson’s Solution

Introduction

Peterson’s solution 是兩個 process 的 software-only critical-section problem 解法，用 flag 與 turn 同時滿足 mutual exclusion、progress、bounded waiting。

它主要用來理解 algorithmic idea；現代系統通常不直接使用。

Shared Variables

int turn;
boolean flag[2];

• flag[i] = true：$P_i$ 想進入 critical section
• turn = j：若雙方同時想進入，優先讓 $P_j$

How it works?

Process $P_i$ 的 entry / exit section：

flag[i] = true;
turn = j;
while (flag[j] && turn == j)
    ;
 
/* critical section */
 
flag[i] = false;

如果只有 $P_i$ 想進入，flag[j] == false，可直接進入。若兩邊同時想進入，最後寫入的 turn 決定誰等待。

Requirements

• Mutual exclusion：兩邊不可能同時通過 while，因為 turn 不能同時等於 0 與 1
• Progress：另一方沒有要進入時，flag 為 false，不會阻擋
• Bounded waiting：對方離開時會把 flag 改回 false，等待者最多讓對方先進一次

Limitation

Modern processor / compiler 可能 reorder 沒有 dependency 的 load / store，破壞 Peterson’s solution 依賴的記憶體順序。因此實務上需要 hardware synchronization support 或更高階工具。