第3章 同步 (Synchronization)
多工(multiprogramming)、分時(timesharing)與平行處理(parallel processing)的系統都可能會產生多個彼此相關而且同時執行的處理元,對於使用者來說,同一個應用會因為並行的作業而得到一些好處,因為感覺上好像系統的效率提昇了。並行的作業可能存在於CPU與I/O設備之間,或是數個CPUs之間,在軟體方面，問題更複雜,因為並行的處理元會用到共享的資源,衍生出死結(deadlock)、臨界區域(critical sections)與運算的不確定性(nondeterminacy)等問題。
多工(multiprogramming)、分時(timesharing)和平行處理(parallel processing)的特性使作業系統有支援多處理元合作並行(也就是同時執行)的需求。好處是讓CPU與I/O裝置能同時作業,讓多處理器的電腦同時處理多個處理元,並且減少使用者的等待時間。
例如死結(deadlock)、臨界區域(critical section)等問題。這些問題主要來自多個處理元共享資源的結果,解決的辦法是達成同步(synchronization)
同步的問題可以在幾個不同的環境下探討:
1. 單處理器(uniprocessor)的環境。2. 多處理器(multiprocessor)的環境。
3. 網路的環境。
從各種角度來探討作業系統中處理元同步的問題:
1. 作業系統在同步問題上的考量: 作業系統要透過PCB來記載有那些處理元是活躍的,根據記錄來分配或取消處理元對於資源的使用權,每個處理元的資料與資源在作業系統的保護下不受其他處理元的干擾,處理元執行的結果不應該受到執行速率的影響。
2. 處理元之間的互動(process interaction) :處理元在執行的過程中跟其他的處理元之間可能會有一些互動。表3-1整理出處理元之間幾種互動的模式。我們可以看到處理元之間可能有競爭(competition)或合作(cooperation)的關係,合作則可透過共享或是溝通的方式來進行。
當兩個處理元共用一個變數(variable),我們說各處理元使用共用變數時進入了所謂的臨界區域(critical section),在沒有做任何控制的情況下,當這兩個處理元同時執行時,所得到的結果不是確定的(non-determinate),也就是說,同樣的程式每次執行時得到的結果可能都不一樣。我們希望避免這樣的狀況,基本的解決方式是要求任一處理元進入臨界區域時,另外一個處理元就不能同時進入其臨界區域。
互斥是由於某些資源無法同時共享,例如印表機,一定要一個列印工作完成以後才能處理下一個。所以這一類的資源也稱為critical resource,處理元使用這種資源的期間就稱為臨界區間(critical section),既然無法共享,代表共用該資源的處理元的臨界區間必須互斥，也就是不能同時。
實際案例: 假設有兩個處理元P1與P2同時執行,而且使用同一個變數y,例如銀行餘額處理的程式同時變更餘額的數目。
由於以上的例子中同時執行又共用變數的問題存在,使兩個處理元的執行結果無法決定(non-determinate)，也就是說，相同的程式作用於相同的資料上,每次執行得到的結果可能都不一樣。從臨界區域(critical section)的定義上,我們說P1和P2對於共用變數balance的處理各有其臨界區域，P1在臨界區域中計算balance與amount的和,P2在臨界區域中計算balance與amount的差,只要P1和P2不同時進入臨界區域,就不會發生結果錯誤的情況。
解決方法是運用共同的變數(shared variable),由該變數來決定是否能進入臨界區域,共同變數指多個處理元共同存取共同使用的變數,共同變數的值(value)象徵某種意義,當其值改變時代表系統狀態的變化,個別的處理元可由此判定是否可進行某些活動。
互斥的要求可以透過各種方法來達成,例如程式本身自己協調,不依賴作業系統的功能,這屬於軟體的解決辦法,通常需要額外的處理,而且要特別注意程式是否正確。導入特殊的機器指令是另外一種解決方法,可以減輕處理的工作,不過不適合當做通用的解決辦法。運用號誌(semaphore)或監督器(monitor)則是作業系統支援的解決方法。
軟體解決同步的方法可以運用於單處理器的環境,假如要使用於多單處理器的環境,必須有共享的主記憶體。這些方法都假設記憶體層次的存取(memory access level)有基本的互斥機制,也就是說,對同一個記憶體位置的讀(read)與寫(write)的動作會序列化,依序進行。
Share variables :
Dekker’s演算法: 基本上兩個processes要能透過flag陣列來了解對方的狀態,除了達到互斥的目的之外,同時也要避免deadlock與livelock。
Peterson的演算法: Dekker演算法有點複雜,所以也比較難證明。下面列出來的Peterson的演算法簡易多了,大家可以比較一下這兩個演算法有什麼差別,然後把這種解決兩個processes同步的方法改成解決n個processes同步的方法。
就作業系統而言,同步的達成有一些基本的策略:
1. 利用軟體與共用變數。
2. 運用停止中斷(disable interrupt)的方式。
3. 使用硬體或作業系統的特殊功能,例如semaphore。
semaphore包括兩個主要的操作:
1. V(s) : [ s = s+1 ]
2. P(s) : [ while (s==0) {wait}; s = s -1]
運作方式：
-
初始化,給與它一個非負數的整數值。
-
執行P（wait()）,信號標S的值將被減少。企圖進入臨界區間的行程,需要先執行P（wait()）。當信號標S減為負值時,行程會被擋住,不能繼續;當信號標S不為負值時，行程可以獲准進入臨界區段。
-
執行V（signal()）,信號標S的值會被增加。結束離開臨界區間的行程,將會執行V（signal()）。當信號標S不為負值時,先前被擋住的其他行程,將可獲准進入臨界區間
下面的同步問題使用了兩個semaphores,這些semaphore用來交換處理元之間的同步訊號,而不是單純用來解決臨界區域的問題,從這個角度來看,兩個處理元之間其實有合作關係,不是競爭關係。顯示的程式碼中,Proc_A的V(s1)會促成Proc_B的P(s1)執行,所以好像P(s1)在等待來自V(s1)的訊號,同樣的,Proc_B的V(s2)可以讓等待中的Proc_A的P(s2)開始執行。
一種讀取與寫入問題的解決方法,只要有reader在使用資源,其他的reader都可以一起共用資源;而writer則必須暫時等待,只有第1個嘗試使用資源的reader需要與writer爭取資源的使用權，一旦reader取得使用權,會使用readNum來記錄進入critical section的reader有幾個,所有reader都完成資源的使用以後,writer才有機會。因此只有第1個reader會執行P(writeData),最後一個reader會執行V(writeData) 。
號誌算是一種理論上的觀念,真正要在系統上實作(implement)時會有一些額外的考量。號誌可以定義成一種抽象資料型式(abstract data type),具有私有的實作(private implementation)部分與公共的介面(public interface) ,這是純粹從程式語言的角度來描述的。號誌的P與V操作可以實作為作業系統的功能,號誌的實作牽涉到中斷(interrupt)的暫時取消,中斷取消的時間很短,差不多在號誌的值處理的時間範圍內,當處理元因為號誌而暫停時,中斷馬上恢復(enabled) 。從真正的作業系統的原始程式碼裡頭應該可以找到實際的實作方式。
哲學家用餐的問題(Dining Philosophers problem)跟處理元同步的問題有類似的思考,有5位哲學家共同進餐,餐具的擺設如圖3-17所示。哲學家在餐聚時會用餐或是思考,由於只有5根筷子,所以當一個哲學家想用餐時,一次先取一根鄰近的筷子,然後再取另外一根筷子,同時有兩根筷子在手才能用餐，假如鄰近的筷子被隔壁的哲學家拿走,就無法進餐。
上面的解決方式可以確定鄰座的哲學家不會一起進食,不過卻存在著死結的問題,例如5位哲學家同時決定要開始進食,而且都拿起靠自己左邊的筷子,此時chopstick陣列的所有元素都變成0,假如有人想再拿自己右邊的筷子,會因為筷子都在別人手上而拿不到,等於沒有人可以開始進食。下列幾種方式可以解決像這樣的死結問題：
1. 最多只讓4位哲學家同時上桌,等於是減少爭取資源的競爭者。
2. 哲學家必須在其兩邊的筷子都在的情況下才能取筷子,等於要在臨界區間(critical section)一次取得左右兩枝筷子。
3. 將哲學家編號,奇數的哲學家要先拿左邊的筷子、再接著拿右邊的筷子,而偶數的哲學家則先拿右邊的筷子、再接著拿左邊的筷子。
號誌可以用來解決處理元同步(process synchronization)的問題,但是存在著可能發生的錯誤,因為號誌的使用牽涉多個處理元共用變數,有可能發生在某種執行順序下產生錯誤,基本上需要同步的處理元共用一個號誌變數，假設其名稱為mutex,則處理元要先執行wait(mutex)之後才能進入臨界區間,離開臨界區間時要再執行signal(mutex),假如無法保證每個參與的處理元有這樣的執行順序，就會發生錯誤。有些程式錯誤就會引發類似的問題：
1. 假如有處理元先執行signal(mutex)再執行wait(mutex),就有可能有多個處理元會同時進入臨界區間，違反互斥(mutual exclusion)的要求。執行順序如下：
signal(mutex);
………
// 臨界區間
………
wait(mutex);
2. 假如有處理元該執行signal(mutex)時反而執行wait(mutex),由於沒有重設mutex的值為1,會形成死結。執行順序如下：
wait(mutex);
………
//臨界區間
………
wait(mutex);
3. 假如任何一個處理元該執行而未執行wait(mutex)或是signal(mutex),甚至於兩者都略過未執行,則都有可能發生死結或是違反互斥規則。
監督器定義的基本結構如下：
monitor monitor_name
{ // 宣告共用變數
procedure p1 (……) { ……};
procedure p2 (……) { ……};
………
procedure pn (……) { ……};
initialization_code(……) {……};
}
接下來我們可以試著透過監督器來寫解決哲學家用餐問題的程式,共用變數中用pState陣列來描述哲學家的3種狀態：思考、饑餓或是進食。s是所謂的狀態變數(condition variable),用來控制共用資源的取得與釋放。狀態變數只有wait跟signal兩個操作,執行狀態變數的wait操作的處理元會暫停,必須等另外一個處理元執行狀態變數的signal操作才能恢復執行。
monitor dining_philosopher
{
enum {THINK, HUNGRY, EAT} pState[5];
condition s[5];
void pickup(int i) {
pState[i]=HUNGRY;
check(i);
if (pState[i] != EAT)
s[i].wait( );
}
void putdown(int i) {
pState[i]=THINK;
check((i+4)%5);
check((i+1)%5);
}
void check(int i) {
// 先確認兩旁的哲學家沒有在進食
if ((pState[(i+4)%5] != EAT) && (pState[i] == HUNGRY) &&
(pState[(i+1)%5] != EAT)
{
pState[i]=EAT;
s[i].signal( );
}
}
initialization_code( ) {
// 一開始每個哲學家都進入思考的狀態
for (int i=0; i<5 i="" font="">
pState[i] = THINK;
}
}
哲學家執行的順序如下：
dining_philosopher.pickup(i);
………
//eat
………
dining_philosopher.putdown(i);
不過,仔細觀察的話會發現仍然存在可能發生饑餓等待(starve to death)的現象,需要另外再想辦法解決。
字體：小 中 大
