iT邦幫忙

1

【小黑馬作業系統教室】(16) (Ch6)Critical section problem的各種解法

嗨嗨,大家好,我是心原一馬,
在上一篇中,我們給大家介紹了「同步化」的議題,
並講述了critical section problem(以下簡稱CS)應滿足三大條件:

  • mutual exclusion: 若程式在執行「critical section」,
    其它程式都不該進入它們的「critical section」。
    (並不是其它程式不能進入CPU哦,那是不可搶先的概念)
  • progress: 若沒有程式在執行CS,並且有程式想要執行CS,則必須有程式去執行CS
  • bounded waiting: 若一支程式想執行CS,等待的process數量必須是有限的,不能無限被插隊

上一篇: 【小黑馬作業系統教室】(15) (Ch6)什麼是「同步化」議題的超完整解說

CS問題的各種解法解說

假設我們只有兩支程式(process)P0, P1,
欲解決CS問題。

(軟體解)從一個單純的解法看起

int turn;是共享變數。(P0, P1共用的變數)
P0的程式如下:

/* Process 0*/
do{
    while(turn!=0);
        critical section
    turn = 1;
        remainder section
}while(1)

P1的程式如下:

/* Process 1*/
do{
    while(turn!=1);
        critical section
    turn = 0;
        remainder section
}while(1)

這個設計代表說當turn=i時,
Pi便可以進入critical section。
(以P0為例,while(turn!=0);這一行代表說當turn不是0的時候,會被擋在CS外進不去)

那麼,這個解法有沒有滿足CS問題的三個條件呢?我們一一檢查:

  • mutual exclusion: 有的。P0和P1不可能同時進入他們的CS。
  • progress: 沒有。因為在P0的CS結束時,會做turn=1,代表說這兩支程式在順序上強迫輪流執行。如果P0執行上比較快,當P0的CS結束,P1還不想進入CS時,會導致P0想進CS而進不了。
  • bounded waiting: 有的。因為雙方最多等待一支程式便能夠進入CS。

(軟體解)Peterson's solution

讓我們將上述程式改良一下,
即為著名的Peterson's solution。
int turn;boolean flag[2]是共享變數。
(初始值turn=0; flag[0]=flag[1]=false)
P0的程式如下:

/* Process 0*/
do{
    flag[0]=true;
    turn = 1;
    while(flag[1] && turn==1);
        critical section
    flag[0]=false;
        remainder section
}while(1)

P1的程式如下:

/* Process 1*/
do{
    flag[1]=true;
    turn = 0;
    while(flag[0] && turn==0);
        critical section
    flag[1]=false;
        remainder section
}while(1)

我們可以這樣想:
flag[i]代表process i 想執行了,
turn代表輪到誰執行了。

所以P0進CS前做了flag[0]=TRUE;turn = 1
其實是在說「我想執行了,但先讓給對方執行」,
都優先禮讓給對方。(對P0, P1來說都是如此)
這樣便可以克服前一個解沒有 progress的問題。

跟第一個解法比較一下:
在第一個解法中沒有progress的問題就在於「太過禮讓」,
在CS做完後強制讓給對方執行(儘管對方可能還不想執行),
就像以前聽過的一個笑話一樣。

小明出門跑腿前,媽媽叮嚀小明「過馬路要禮讓車子先過」,
結果小明去了一小時都沒回來,
媽媽出門查看,小明委屈的說「等了一小時都沒有車子經過啊。」

這情況就像是在第一個解法中,P0想執行了,
但是一定要等到P1執行完才能執行(好比說「小明想過馬路但一定要給讓車先過」)。

以下證明Peterson's solution可以滿足progress和bounded waiting:

  • 證明 progress:
    在Peterson's solution中改良為flag[i]
    turn兩個變數去控制,
    如果P0想執行但P1不想執行,(flag[0]=trueflag[1]=false的情況),
    即便是輪到P1執行(turn=1),
    也能夠因為P1不想執行而使P0順利進入它的CS。
    因為擋住P0進入它的CS的條件是while(flag[1] && turn==1);
    因此只要flag[1]=false,P0就能進入它的CS。

  • 證明 bounded waiting:
    因為P0進CS前做了flag[0]=TRUE;turn = 1
    做的是「我想執行了,但先讓給對方執行」,
    因此對兩支process來說,
    都不會無限插隊。

(軟體解)Bakery algorithm (n processes)

這是一種類似在郵局排隊領號碼牌的概念,
在每支程式進入它們的CS之前,
都必須先領一張號碼牌,
號碼最小的優先進入CS。
(跟真實郵局不同的地方在於,
由於程式「同時」執行,
可能會同時抽到重複的號碼牌,
譬如依序抽到1, 2, 3, 3, 4, 5, 5)

假設有P0, P1, ..., P(n-1) 共n支程式(Pi的id為i),
共享變數為boolean choose[i]int num[i]
Pi的程式如下:

/* Process i*/
do{
    choose[i]=true;
    num[i] = max(num[0], num[1], ..., num[n-1])+1 //抽號碼牌
    choose[i]=false;
    for(j=0;j<n;j++){
        while(choose[j]); //等待所有想領號碼牌的程式抽號碼牌
        while((num[j]!=0) && (num[j],j)<(num[i],i)); // 等待號碼牌小的程式先執行,若號碼牌相同則程式id小的優先
    }
        critical section
    num[i] = 0; //重置號碼牌為0,待下次重新排隊再抽號碼牌
        remainder section
}while(1)

這個解一樣可滿足 mutual exclusion, progress, bounded waiting。

Note: 為什麼要等待其它程式都領完號碼牌才可進行比較?

在上述解法中,有個令人較難理解的一行while(choose[j]);
為什麼要等待其它程式都領完號碼牌才可進行比較呢?
原因是若P0和P1「同時」抽號碼牌,
但P1恰好比P0早一點點抽完。
P1抽到「6號」,此時發現沒有號碼牌1~5號的程式,
P1便進入它的CS。

稍後,P0在下一個瞬間也領到「6號」號碼牌,
一看沒有人比他小的號碼牌要等待,
(P0和P1的號碼牌相同,但因為P0的id比P1小,由規則不必等待P1)
P0也可進入它的CS。

此時造成P0和P1同時進入CS,違反mutual exclusion。

(硬體解)Atomic TestAndSet

atomic的意思是原子的、不可分割的
用來形容一段程式碼便是這段程式碼在執行的過程中,
保證不會被其它程式打斷。
(atomic與non-preemptive的差別是atomic更為廣義,
它可以泛指不會被中斷的程式碼,
而non-preemptive特別指排程上程式不能在CPU burst time 結束前被打斷)

解法如下:

\*這個函數不可以執行到一半時被中斷,
效果是回傳lock的值並設lock=true*\
bool TestAndSet(bool &lock){
    bool value = lock;
    lock = true;
    return value
}

假設我們只有兩支程式(process)P0, P1,
bool lock;是共享變數,
則P0, P1的程式碼都是相同的,如下:

do{
    while( TestAndSet(bool &lock));
        critical section
    lock = false;
        remainder section
}while(1)

(硬體解)Atomic Swap

假設Swap()函數是不可分割地執行,
假設我們只有兩支程式(process)P0, P1,
bool lock;是共享變數,
則P0, P1的程式碼都是相同的,如下:

do{
    key = true; //key是私有變數而非共享變數
    while(key)
        Swap(key,lock);
        critical section
    lock = false;
        remainder section
}while(1)

<分析>對於硬體解Atomic TestAndSet和Swap來說,
程式碼雖然簡單,
能滿足mutual exclusion和progress,
但是因為沒有限制程式執行的順序而會違反bounded waiting。

先整理到這邊吧。


尚未有邦友留言

立即登入留言