Try   HackMD

Critical Section Problem

Race condition

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

Critical Section

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

Image Not Showing Possible Reasons
  • The image file may be corrupted
  • The server hosting the image is unavailable
  • The image path is incorrect
  • The image format is not supported
Learn More →

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 : Pi 準備好了

    Image Not Showing Possible Reasons
    • The image file may be corrupted
    • The server hosting the image is unavailable
    • The image path is incorrect
    • The image format is not supported
    Learn More →

  • Peterson's solution for process Pi

do {

    flag[i] = TRUE;
    turn = j;
    while(flag[j] && turn == j);
    
    CRITICAL SECTION
    
    flag[i] = FALSE;
    
    REMAINDER SECTION
}
  1. 滿足Mutual exclusion

    • 如果flag[j] == falseturn = i, Pi 可以進去

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

    • 然而turn 只能是其中一個

    • 只有 Pi 或 Pj 其中一個能先進去

    • 另一個要等他結束

  2. 滿足Progess

    1. Pi 準備好了

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

      • 那麼flag[j] == false

      • Pi 可以進去

    2. Pi 和 Pj 都準備好了

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

      • turn == i Pi 進去

      • turn == j Pj 進去

  3. 滿足Bounded waiting

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

    • 此時 Pi 會執行 turn = j

    • Pi 就進不去了

    • 因此 Pj 最多等待一次

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 Pi is waiting

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

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

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

  • 如果有,讓 Pj 拿著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

Image Not Showing Possible Reasons
  • The image file may be corrupted
  • The server hosting the image is unavailable
  • The image path is incorrect
  • The image format is not supported
Learn More →

{%hackmd theme-dark %}

tags : OS CSIE