動機

只是記錄用，因為在現代計算機架構下，基本上都沒用 但有面試問過，所以寫一下

Peterson algorithm

用flag與term來阻止對方

def f1():
    flag[0] = true
    turn = 1
    while flag[1] == true and turn == 1:
        # busy wait
    # critical section
    # ...
    # end of critical section
    flag[0] = false

def f1():
    flag[1] = true
    turn = 0
    while flag[0] == true and turn == 0:
        # busy wait
    # critical section
    # ...
    # end of critical section
    flag[1] = false

為什麼需要turn? 不然flag都會是true

Lamport’s bakery algorithm

利用sequence嚴格遞增，對thread做sort

// Entering: array [1..NUM_THREADS] of bool = {false};
// Number: array [1..NUM_THREADS] of integer = {0};

lock(integer i) {
  Entering[i] = true;
  Number[i] = 1 + max(Number[1], ..., Number[NUM_THREADS]);
  Entering[i] = false;
  for (integer j = 1; j <= NUM_THREADS; j++) {
      // Wait until thread j receives its number:
      while (Entering[j]) { /* nothing */ }
      // Wait until all threads with smaller numbers or with the same
      // number, but with higher priority, finish their work:
      while ((Number[j] != 0) && ((Number[j], j) < (Number[i], i))) { /* nothing */ } // 有沒有想到raft的投票，或是at-least-updated
  }
}

unlock(integer i) {
  Number[i] = 0;
}

問題是?

現代cpu會reorder程式碼

像peterson的可以reorder成

turn = 1
flag[0] = true
# ...

turn = 0
flag[1] = true

bakery可以reorder成

lock(integer i) {
  Entering[i] = true;
  Entering[i] = false; // 之後變成只剩false
  Number[i] = 1 + max(Number[1], ..., Number[NUM_THREADS]);
  // ...
}

因為想做atomic的資料與做atomic的資料沒有關聯(因果關係)

感覺比較可以的: Szymański’s algorithm

把狀態切的細一點，分成 0: 在外面，未申請訪問臨界區 1: 在入口門外等待 2: 在入口門內等待其它提出申請的進程都進入入口門 3: 正在進入入口門 4: 入口門關閉，在等候室里等待進入臨界區，或正在訪問臨界區

// Entry protocol
flag[self] = 1                    // Standing outside waiting room
await(all flag[1..N] ∈ {0, 1, 2}) // Wait for open door
flag[self] = 3                    // Standing in doorway
if any flag[1..N] = 1:            // Another process is waiting to enter
    flag[self] = 2                // Waiting for other processes to enter
    await(any flag[1..N] = 4)     // Wait for a process to enter and close the door

flag[self] = 4                    // The door is closed
await(all flag[1..self-1] ∈ {0, 1})   // Wait for everyone of lower ID to finish exit protocol

// Critical section
// ...

// Exit protocol
await(all flag[self+1..N] ∈ {0, 1, 4}) // Ensure everyone in the waiting room has
                                       // realized that the door is supposed to be closed
flag[self] = 0 // Leave. Reopen door if nobody is still in the waiting room