Critical Section Problem

Race condition

• 多個行程同時對同一個資料存取
• 存取的順序影響結果
• 解決辦法 : 一次僅允許一個行程存取

Critical Section

• 一個程式碼片段，用來放置共享變數

Critical Section Problem

• 必須滿足下列三個要求

1. Mutual exclusion
   • 任意時間點，只允許一個行程進入
2. Progress
   • 不想進去的人不能妨礙別人
   • 決定誰可以進去的時間是有限的
3. Bounded waiting
   • 從請求進入到獲准的時間是有限的
     • n 個行程最多等 n-1 次

Peterson's Solution

• A software-based solution
• Two process solution

int turn;
Boolean flag[2];

• turn : 現在輪到誰進去

• flag[i] = true : P_i 準備好了

• Peterson's solution for process P_i

do {

    flag[i] = TRUE;
    turn = j;
    while(flag[j] && turn == j);
    
    CRITICAL SECTION
    
    flag[i] = FALSE;
    
    REMAINDER SECTION
}

1. 滿足Mutual exclusion

   • 如果flag[j] == false或turn = i, P_i 可以進去

   • 如果都想進去, flag[i] == flag[j] == true

   • 然而turn 只能是其中一個

   • 只有 P_i 或 P_j 其中一個能先進去

   • 另一個要等他結束

2. 滿足Progess

   1. P_i 準備好了

      • 如果 P_j 還沒準備好(在remainder section)

      • 那麼flag[j] == false

      • P_i 可以進去

   2. P_i 和 P_j 都準備好了

      • flag[i] == flag[j] == true

      • turn == i P_i 進去

      • turn == j P_j 進去

3. 滿足Bounded waiting

   • 當 P_i 離開後又想再進去一次

   • 此時 P_i 會執行 turn = j

   • P_i 就進不去了

   • 因此 P_j 最多等待一次

Synchronization Hardware

Atomic operation

• 不會被中斷或是context switch
• 一旦開始執行就會執行到結束

Test and Set

boolean test_and_set(boolean *target)    {
    boolean *rv = target;
    *target = true;
    
    return rv;
}

// initialize varible lock to false
do    {
    while(test_and_set(&lock));
    // critical section
    lock = false;
    // remainder section
    
} while(true);

• 回傳舊值，並將舊值改為true

  • 只有第一次會是false

• 第一個執行 test_and_set 的 process 會將 lock 值設為 true 並回傳 false

• 其他想要拿 lock 的 process 會卡在 while 迴圈

Compare and Swap

int compare_and_swap(int *value, int expected, int new_value)    {
    int temp = *value;
    
    if(*value == expected)
        *value = new_value;
    
    return temp;
}

// initialize varible lock to false
do    {
    while(compare_and_swap(&lock, 0, 1) != 0);
    // critical section
    lock = 0;
    // remainder section
    
} while(true);

• 回傳舊值，並比較lock的值

  • 如果是 false(0) 把 lock 值改為 true(1)
  • 如果是 true(1) 就還是 true(1)

• 概念與 test_and_set 同

小結

• 這兩個演算法都不滿足bounded-waiting

• 一個用 test_and_set() 改良的演算法可以滿足所有 critical-section 的條件

修正後的 test_and_set()

// initialize varible lock to false
do    {
    waiting[i] = true;
    key = true;
    while(waiting[i] && key)
        key = test_and_set(&lock);
    waiting[i] = false;
    
    // critical section
    
    j = (i+1) % n;
    while((j != i) && !waiting[j])
        j = (j+1) % n;
    
    if(j == i)
        lock = false;
    else
        waiting[j] = false;
        
    //remainder section
    
} while(true)

• waiting[i] = ture means P_i is waiting

• 只有 waiting[i] == false 或 key == false 才能進入 critical path

• 第一個執行 test_and_wait() 的 process 會讓 lock = true ， 其他人就要等

• 如果沒有 process 在等，釋放 lock

• 如果有，讓 P_j 拿著lock，進入 critical section

1. 滿足 Mutual exclusion

   • 一個行程離開，一個行程獲得機會進去
   • waiting[j] = false

2. 滿足 Progress

   • 一個行程離開 critical section 後，會把 lock 設成 false 或把 waiting[j] 設成 false

   • 這些都會決定要讓哪個在等的行程進入 critical section

3. 滿足 Bounded-waiting

   • 當一個行程離開後，會scan waiting array (i, i+1, … n, 1, 2, … i-1)

   • 任一行程最多等n-1次

---

last edit

dotSun, Dec 22, 2019, 8:58 PM

HOME PAGE

{%hackmd theme-dark %}

tags : OS CSIE