同步問題 Synchronization

名詞解釋 — 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,以下介紹兩種方法

  1. 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:系統產能低。
  1. 除非 proces 可以一次取得所有工作所需的資源,才允許持有資源。
  2. 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
  ABCD  ABCD  ABCD
P1 0014  0656  1520 
P2 1432  1942 
P3 1354  1356
P4 1000  1750
// 算出 need NEED
ABCD
0642 
0510
0002
0750
// 宣告確認是否完成的變數 FINISH
false
false
false
false
// loop : 持續找出可以釋放的 process 並更新 finish
// 直到找不到或 finish 全為 true
NEED   Available
ABCD  ABCD
0642  1520
0510<-
0002
0750
NEED   Available
ABCD  ABCD
0642  1520
0000 +1432
0002-------
0750  2952
FINISH
false
true
false
false

3. Deadlock Detection

Allow system to enter deadlock state.

Detection algorithm :

  • Single instance : topological sort (using wait-for graph)
  • 使用 adjcent matrix : O(n²)
  • 使用 adjcent list : O(V+E)
  • Several instance : 用 Banker algorithm 判斷系統是否已經在 unsafe state

Recovery scheme :

  • 終止 process (成本都高)
  • 全部刪除
  • 一次刪一個 process,直到打破 deadlock。
  • 資源搶奪
  • 剝奪 victim process 資源 (可能造成 starvation)
  • 恢復無該資源前狀態 (cost 高)

[重要] Resource allocation graph

Some facts about RAG :

  • If graph contains no cycles => no deadlock.
  • If graph contains a cycle
  • one instance <=> deadlock.
  • several instances, possibility of deadlock. ( deadlock => cycle )

Reference:
https://mropengate.blogspot.com/2015/01/operating-system-ch6-synchronization.html
https://www.rapitasystems.com/blog/race-condition-testing
https://mropengate.blogspot.com/2015/01/operating-system-ch7-deadlock.html

Reference:
https://mropengate.blogspot.com/2015/01/operating-system-ch6-synchronization.html
https://www.rapitasystems.com/blog/race-condition-testing

Hi I am Samuel

Hi I am Samuel