同步問題 Synchronization

14 min readSep 29, 2021

名詞解釋 — Race Condition
多個processes or threads同時存取共享資源，系統依排程次序執行，而造成資料不正確的問題發生。

假設今天有兩個thread，一個負責讀取變數然後加一，另一個負責讀取變數乘以二，在期望之下應該都可以正常執行。但在race condition下就有可能發生其中一個thread還沒write，但另一個thread已經去讀取，造成讀取到舊值，最終導致結果的錯誤。

為了讓資料的處理得到期望的結果，程式就必須有同步的機制。

The Critical Section Problem：提供對共享變數之存取的互斥控制，確保資料的正確性。

Entry section
Critical section
Exit section
Remainder section

進入critical section的條件:

Mutual exclusion：任一時間點，只允許一個 process 進入他自已的 critical section 內活動。
Progress：必須同時滿足下面2個要件：
- 不想進入 critical section 的 process 不可以阻礙其它 process 進入 critical section，即不可參與進入 critical section 的決策過程。
- 必須在有限的時間從想進入 critical section 的 process 中，挑選其中一個 process 進入 critical section，隱含No Deadlock。

tips: 有空位時讓「想進的人」「馬上」進入。

Bound waiting：自 process 提出進入 critical section 的申請到獲准進入 critical section 的等待時間是有限的。即若有 n 個 processes 想進入，則任一 process 至多等待 n-1 次即可進入，隱含 No starvation。

Peterson’s solution — software solution

Two process solution. Assume that the LOAD and STORE instructions are atomic; that is, cannot be interrupted.

Share variables :

turn：整數，存放的値為 i 或 j，誰擁有此值誰就有資格進入。
flag[i]：布林陣列，表示 i 想不想進去。

do{
 flag[i] = TRUE;
 turn = j; //禮讓的概念 while ( flag[j] && turn == j); //想進去且輪到他進去 CRITICAL SECTION flag[i] = FALSE; REMAINDER SECTION} while (TRUE);

Bakery Alogorithm — software solution

multiple process solution

Lamport把這個並發控制算法非常直觀地類比為顧客去麵包店採購。麵包店一次只能接待一位顧客的採購。已知有n位顧客要進入麵包店採購，按照次序安排他們在前台登記一個簽到號碼。該簽到號碼逐次增加1。顧客根據簽到號碼的由小到大的順序依次入店購貨。完成購買的顧客在前台把其簽到號碼歸0。如果完成購買的顧客要再次進店購買，就必須重新排隊。

do {       
  choosing[i] = true; // 正在抽號碼牌
  number[i] = max(number[0], number[1], …, number [n – 1])+1; //抽最大號碼牌
  choosing[i] = false; // 抽完號碼牌
  for (j = 0; j < n; j++) { // 跟其他人比      
    while (choosing[j]); // 確認他是否抽完了
    while ((number[j]!= 0) && compare(number[j],number[i]))); // 確認其他人是否都排你後面
  }  number[i] = max(number[0], number[1], …, number [n – 1])+1;
  choosing[i] = false;       
  for (j = 0; j < n; j++) {       
    while (choosing[j]);
    while ((number[j]!= 0) && (number[j],j)<(number[i],i)));
  }  // critical section  number[i] = 0; // 丟掉號碼牌  // remainder section
} while(1);

Disable interrupt — hardware instructions support

透過disable interrupt 來達到atomically processing，以下介紹兩種方法

TestAndSet：檢查並設置是一種不可中斷的基本 (原子) 運算 (atomically)，它會寫值到某個記憶體位置並傳回其舊值。

/* Test_and_Set C.S. example */
repeat
 while(Test_and_Set(Lock)) do no-op; //entry
  critical section
 Lock = False; //exit
  remainder section
until false

2. Swap：a, b 兩值互換。

/* SWAP C.S. example */
Repeat
 key = true;
 repeat
  SWAP(Lock, key);
 until key = False;
  C.S.
 Lock = False;
  R.S.
Until false

然而以上兩個都違反 bounded waiting：未規範order使得次序以亂數決定。

正確方式應再加上waiting[i]和key

/* Test_and_Set C.S. example */
repeat 
 waiting[i] = true //表明在等
 key = true // 拿著鑰匙
 while(waiting[i] and key) do key = Test_and_Set(Lock); //必須沒鎖才能進
 waiting[i] = false // 進入，不用等了
   critical section
 j = (i+1)mod n // 找下一個想進的
 while(j!=i and not waiting[j]) do j = (j+1)mod n // 直到找到有在等的
 if(j==i) // 找了一圈沒找到有人在等，解鎖
   Lock = false
 else // 找到下一個在等的，叫它進來
   waiting[j] = False; //exit
  remainder section
until false

hardware solution 缺點 (特指 TAS 和 SWAP)

只有kernel mode 能用
need time
多處理機上會失效(因為其他顆的CPU沒disable interrupt)，單處理機上不好(busy waiting)

Semaphore

Semaphore 是一個同步物件，用於保持在 0 至指定最大值之間的一個計數值。(Semaphore do not require busy waiting, using waiting queue)

當執行緒完成一次對該 semaphore 物件等待 (wait(S) / P(S)) 時，該計數值 S-1；
當執行緒完成一次對semaphore 物件釋放 (signal(S) / V(S)) 時，計數值 S+1。
當計數值為 0，則執行緒等待該 semaphore 物件直至該 semaphore 物件變成 signaled (>0)狀態。

用途設置：

Sequencing (event) : value = 0
Mutex : value = 1
Capacity control : value = n_capacity

1. 例題 : Sequencing

傑克和羅絲相約去看電影，兩人約在電影院門口見面，如果有人先到的話要等另一人到了才可以進入電影院。

R=0;J=0;
jack(){
   signal(J); //自己到了，一定要先 signal 再 wait 不然會有 deadlock。
   wait(R); //等 
   // see the movie
}
ross() { 
   signal(R); 
   wait(J);
   // see the movie
}

2. 例題 : Mutex 和 Capacity control

A DMA controller offers 4 DMA channels for simultaneous data transfers.

S=4; T=1; c[4]={F,F,F,F};proc() { 
wait(S);  //容量控制(一個房間最多4人)
wait(T);  //保護c[4]避免複寫(一次只有一個人找位子坐)// pick one unused channel among c[0],c[1],c[2],c[3] 
// setup DMA transfer signal(T);// wait for DMA completion signal(S);}

Deadlock 簡介

Deadlock 意思是系統中存在一組 process 陷入互相等待對方所擁有的資源的情況，造成所有的 process 無法往下執行，使得 CPU 利用度大幅降低。

Deadlock 發生須符合以下四項充要條件 :

Mutual exclusion：某些資源在同一個時間點最多只能被一個 process 使用
Hold and wait：某 process 持有部分資源，並等待其他 process 正在持有的資源
No preemption：process 不可以任意強奪其他 process 所持有的資源
Circular waiting：系統中存在一組 processes P=P0,P1,…,Pn，其中 P0 等待 P1 所持有的資源 … Pn 等待 P0 所持有的資源，形成循環式等待。(因此，deadlock不會存在於single process環境中)

[用心去感覺] Deadlock vs Starvation

Deadlock 的處理方法

Deadlock 三種處理方法：

Deadlock prevention
Deadlock avoidance
Deadlock detection & recovery

prevention 和 avoidance 保證系統不會進入 Deadlock，但資源利用度低；而 detection 資源利用度較高，但若 Deadlock 需要做 recovery，則 cost 極高。

1. Deadlock prevention

打破必要條件四項之一，即可保證 Deadlock 永不發生。

打破 Mutual exclusion：為資源與生俱來之性質，無法打破。
打破 Hold and wait：系統產能低。

除非 proces 可以一次取得所有工作所需的資源，才允許持有資源。
process 執行之初可持有部分資源，但要再申請資源前，要先釋放手中所有資源。

打破 Preemption : 讓高優先 process 搶低優先 process 的資源，會造成 starvation。
打破 Circular waiting：Process須按照資源編號遞增方式申請資源。

2. Deadlock avoidance

當 process 提出資源申請時，OS 會執行Banker algorithm 來判斷系統在「假設核准該申請後」是否處於 Safe state，是則核准，否則請 process 等待。

safe state : 存在 safe sequence
unsafe state : 可能有 deadlock

[重要] Banker Algorithm

設所有 process 在 set P 中；n 為 process 數目，m 為資源種類。

一維陣列：

R_i[m] : process i 提出的資源申請量。
Avail[m] : 系統目前各類資源的可用數量。
Finish[n] : 各個 process 是否完成。

二維陣列：

Alloc[n,m] : 目前各 process 持有的資源量。
Max[n,m] : 各 process 需要多少資源才可以完成工作。
Need[n,m] : 還要多少資源才可以完成工作。 (Need = Max — Alloc)

虛擬碼：

while( Finish is not all TRUE ){
    found = FALSE;
    foreach (i in process set P) {
        if ( Need[i,:] <= Avail ) {
             Avail = Avail + Alloc[i,:];
             P = P - {i};
             found = TRUE;
        }
    }
    if (!found) return FAIL;
}
return OK;

例題：

// 基本變數設置 Allocation　　　Max　　　Available
 　　ＡＢＣＤ　　ＡＢＣＤ　　ＡＢＣＤ
 P1　００１４　　０６５６　　１５２０　
 P2　１４３２　　１９４２　
 P3　１３５４　　１３５６
 P4　１０００　　１７５０// 算出 need NEED
 ＡＢＣＤ
 ０６４２　
 ０５１０
 ０００２
 ０７５０// 宣告確認是否完成的變數 FINISH
 false
 false
 false
 false// loop : 持續找出可以釋放的 process 並更新 finish
// 直到找不到或 finish 全為 true NEED　  　Available
 ＡＢＣＤ　　ＡＢＣＤ
 ０６４２　　１５２０
 ０５１０<-
 ０００２
 ０７５０ NEED　　  Available
 ＡＢＣＤ　　ＡＢＣＤ
 ０６４２　　１５２０
 ００００　＋１４３２
 ０００２－－－－－－－
 ０７５０　　２９５２ FINISH
 false
 true
 false
 false