【正文】 界區(qū) 中國(guó)最大的管理資源中心 44 turn = 1。 flag[0]= false。 其余部分 } } void P1( ) { while (true) { flag [1]= true。 while (flag[0]) if(turn==0) { flag[1] = false。 while ( turn == 0) /* 什么也不做 */ flag [1] = true。 } 臨界區(qū) turn = 0。 flag[1]= false。 其余部分 } } void main( ) { turn = 0。 flag[0] = false。 flag[1] = false。 parbegin(P0( ) , P1( ))。 } flag數(shù)組變量提供所有 進(jìn)程的狀態(tài)，同時(shí)設(shè)置變量 turn用于表示哪個(gè)進(jìn)程應(yīng)堅(jiān)持進(jìn)入。當(dāng) P0希望進(jìn)入自己的臨界區(qū)時(shí)，它把自己的 flag置為 true，然后繼續(xù)檢查 P1的 flag，如果 P1的 flag為 false， P0可以立即進(jìn)入自己的臨界區(qū)，否則 P0檢查 turn，如果它發(fā)現(xiàn) turn=0，那么它知道自己該堅(jiān)持進(jìn)入，從而周期性地檢查 Pl的 flag； Pl在某一點(diǎn)上將注意到應(yīng)把 turn賦為 0，隨后把其 flag 置為 false，允許 P0 進(jìn)入；在 P0 結(jié)束其臨界區(qū)后，把自己的 flag置為 false，釋放臨界區(qū)，并把 turn置為 1，從而把堅(jiān)持進(jìn)入的權(quán)力轉(zhuǎn) 交給 P1。 Peterson算法 : boolean flag [2]={false, false}。 中國(guó)最大的管理資源中心 45 int turn。 void P0( ) { while (true) { flag [0] = true。 turn = 1。 while( flag[1]amp。amp。 turn==l] /*什么也不做 */。 臨界區(qū) flag [0] = false。 /* 其余部分 */。 } } void P1( ) { while (true) { flag [1] = true。 turn = 0。 while( flag[0]amp。amp。 turn==0) /*什么也不做 */。 臨界區(qū) flag [1] = false。 /* 其余部分 */。 } } 全局變量 flag 數(shù)組表示每個(gè)進(jìn)程關(guān)于互斥的位置，全局變量 turn 解決同時(shí)沖突。 考慮進(jìn)程 P0，一旦它把 flag[0]置為 true， Pl不能進(jìn)入其臨界區(qū)；如果 P1已經(jīng)在臨界區(qū)中，則flag[1]=true，且 P0 被阻止進(jìn)入臨界區(qū)。另一方面，還可以防止互相阻塞，假設(shè) P0在它的 while循環(huán)被阻塞， 這意味著 flag[1]為 true 且 turn=l，則當(dāng) flag[1]變成 false 或 turn 變?yōu)?0 時(shí)， P0都可以進(jìn)入自己的臨界區(qū)。 同步機(jī)制 解決同步問(wèn)題有若干種方法，有些方法既可以用作同步，也可以用作互斥。實(shí)際上，進(jìn)程互斥可以看作是進(jìn)程同步的一種特例。 這里介紹三種同步機(jī)制：鎖、信號(hào)量和管程。 1. lock和 unlock 中國(guó)最大的管理資源中心 46 大部分同步方案均采用某個(gè)物理實(shí)體（如鎖、信號(hào)量等）實(shí)現(xiàn)通信，進(jìn)程通信原語(yǔ)中關(guān)鎖（ lock）和開鎖 (unlock)是最簡(jiǎn)單的原語(yǔ)。在這兩個(gè)原語(yǔ)中設(shè)置一個(gè)公共變量 X代表某個(gè)臨界資源的 狀態(tài)。如： 0 資源可用 X= 1 資源正在使用 進(jìn)程使用臨界資源必須做如下三個(gè)不可分割的操作： ① 檢查 X的值。當(dāng) X=1 時(shí)，表示資源正在使用，于是返回繼續(xù)進(jìn)行檢查；當(dāng) X=0時(shí)，表示資源可以使用，則置 X 為 1（關(guān)鎖）。 ② 進(jìn)入臨界區(qū)，訪問(wèn)臨界資源。 ③ 釋放臨界資源，置 X 為 0（開鎖）。 通過(guò)以上分析，可以給出關(guān)鎖和開鎖原語(yǔ)的描述： 關(guān)鎖原語(yǔ) lock(X) { L： if x==1 go to L else x=1。 } 開鎖原語(yǔ) unlock(X)： { X=0； } 值得注意的是，在檢查 X 的值和置 X 為 1(關(guān)鎖 )這兩步之間， X 值不能被其它進(jìn)程所改變。 用 lock 和 unlock 實(shí)現(xiàn)互斥的代碼結(jié)構(gòu)為： int x=0； ?? lock（ x）； 臨界區(qū)： unlock（ x）； ?? 信號(hào)量與 P/V操作 開鎖和關(guān)鎖原語(yǔ)可以解決互斥問(wèn)題，但效率低、浪費(fèi) CPU 資源。這是因?yàn)槿魏蜗脒M(jìn)入臨界區(qū)的進(jìn)程都不能直接進(jìn)入，它們必須不停地循環(huán)檢查 X的值，等待 X 變?yōu)?0。等待的過(guò)程 中國(guó)最大的管理資源中心 47 消耗了有價(jià)值的 CPU 時(shí)間，一直重復(fù)無(wú)意義的工作，降低了系統(tǒng)的速度。 1965 年 引進(jìn) 了比 lock/unlock原語(yǔ)的更一般的形式 P/V操作來(lái)克服這種忙碌等待現(xiàn)象，大大地簡(jiǎn)化了進(jìn)程的同步與互 斥。這是他對(duì)進(jìn)程通信的一個(gè)重要貢獻(xiàn)。 P/V操作由 P 操作原語(yǔ)和 V操作原語(yǔ)組成，其意義是在一個(gè)被稱之為信號(hào)燈變量的 S 上定義了兩個(gè)操作，該變量的值只能由 P 操作和 V操作進(jìn)行修改。并且這兩個(gè)操作均屬于原子操作，不可被中斷。 P 操作原語(yǔ)定義如下： P（ S） { S。 if S0 block ( )； } 即：當(dāng)執(zhí)行 P 操作時(shí)，將信號(hào)燈變量 S 的值減 1，如果 S≥ 0，表示申請(qǐng)的臨界區(qū)資源可用，則該進(jìn) 程占用資源，繼續(xù)執(zhí)行；如果 S0，則執(zhí)行此原語(yǔ)的進(jìn)程被置成阻塞狀態(tài)，并使其在 S 信號(hào)量的隊(duì)列中等待，由調(diào)度程序重新調(diào)度其它進(jìn)程執(zhí)行。 V操作原語(yǔ)定義如下： V（ S） { S++； if S=0 wakeup ( )； } 即：當(dāng)執(zhí)行 V操作時(shí)，表示進(jìn)程釋放資源，將信號(hào)燈變量 S的值加 1，如果 S≤ 0，則喚醒 S 信號(hào)量隊(duì)列隊(duì)首的阻塞進(jìn)程，將其狀態(tài)從阻塞狀態(tài)轉(zhuǎn)變到就緒狀態(tài)，執(zhí)行 V（ S）者繼續(xù)執(zhí)行。如果 S0，則該進(jìn)程也繼續(xù)執(zhí)行。 P/V 操作的物理解釋是：信號(hào)燈變量 S 可以表示某類臨界資源，其值可以看作是可用資源數(shù)，執(zhí) 行一次 P 操作，相當(dāng)于申請(qǐng)一個(gè)資源，執(zhí)行一次 V操作，相當(dāng)于釋放一個(gè)資源。當(dāng)S 的值為負(fù)數(shù)時(shí)，其絕對(duì)值表示等待該資源的進(jìn)程個(gè)數(shù)。 信號(hào)量和 P/V操作是實(shí)現(xiàn)進(jìn)程互斥與同步的非常有效的方法。用信號(hào)量和 P/V操作實(shí)現(xiàn)進(jìn)程互斥與同步的代碼結(jié)構(gòu)為： P（ S）； 臨界區(qū)； V（ S）； 例如，有兩個(gè)進(jìn)程 A和 B， A進(jìn)程向隊(duì)列加入一項(xiàng)， B 進(jìn)程從該隊(duì)列中移出一項(xiàng)。為了不使隊(duì)列指針指向錯(cuò)誤位置，需要嚴(yán)格限制一次只能有一個(gè)進(jìn)程存取該隊(duì)列元素。設(shè) S信號(hào)量的初值為 1，于是 A、 B 進(jìn)程的部分代碼如下： 進(jìn)程 A的程序 進(jìn)程 B 的程序 ┇ ┇ 中國(guó)最大的管理資源中心 48 P(S)； P(S)； 將一項(xiàng)送入隊(duì)列 從隊(duì)列中移出一項(xiàng) V(S)； V(S)； ┇ ┇ 顯然，對(duì)隊(duì)列的操作可以互斥完成。 我們?cè)賮?lái)看一個(gè)用 P/V操作解決進(jìn)程間同步問(wèn)題的例子。如圖 9， P1 進(jìn)程 P2 進(jìn)程 緩沖區(qū) B 圖 9 進(jìn)程間同步問(wèn)題示意圖 進(jìn)程 P1 將信息輸入到緩沖區(qū) B 中，進(jìn)程 P2負(fù)責(zé)從緩沖區(qū) B 中取數(shù)據(jù)輸出，對(duì)于進(jìn)程P1 來(lái)說(shuō)，如果前一次輸入的數(shù)據(jù)尚未取走，則應(yīng)暫時(shí)停止輸入，等待 P2 進(jìn)程取走數(shù)據(jù)后再輸入新數(shù)據(jù)；而對(duì)于進(jìn)程 P2 來(lái)說(shuō)，如果 P1 尚未輸入數(shù)據(jù)，則應(yīng)等待。 P P2 之間存在互斥關(guān)系（兩個(gè)進(jìn)程不能同時(shí)對(duì)緩沖區(qū)進(jìn)行操作），也存在同步關(guān)系（一個(gè)進(jìn)程的能否執(zhí)行與另一個(gè)進(jìn)程密切相關(guān)）。 設(shè) S1和 S2 為信號(hào)量， S1表示是否可向緩沖區(qū)輸入數(shù)據(jù)， S2 表示可從緩沖區(qū)中取數(shù)據(jù)，用 1 表示“是”，用 0 表示“否”，則 S1 的初值為 1， S2的初值為 0， P P2之間的同步關(guān)系可以表示如下： 輸入進(jìn)程 P1： 輸出進(jìn)程 P2： ┇ ┇ P(S1)； P(S2) 讀信息到緩沖區(qū) B 把 B 中的信息輸出 V (S2) V(S1) ┇ ┇ 進(jìn)程 P1 要把信息輸入到緩沖區(qū) B，就執(zhí)行 P(S1)操作，由于 S1的初值為 l，表示可向緩沖區(qū)輸入數(shù)據(jù)，所以執(zhí)行 P(S1)的操作成功，可直接把信息輸送到緩沖區(qū) B中，然后執(zhí)行 V (S2)，使 S2 的值為 1， P2 進(jìn)程可以從緩沖區(qū) B中取出信息輸出。當(dāng) P2進(jìn)程執(zhí)行了 V(S1)操作后，P1進(jìn)程才可向緩沖區(qū) B 輸入下一個(gè)數(shù)據(jù)。 如果 P2進(jìn)程先執(zhí)行，則由于 S2的初值是 0，表示緩沖區(qū)中無(wú)數(shù)據(jù)可取，執(zhí)行 P(S2)操作時(shí)，使 P2進(jìn)程被阻塞掛到等待隊(duì)列上，等待緩沖區(qū)中數(shù)據(jù)的到達(dá)。只有當(dāng) P1進(jìn)程執(zhí)行了 V (S2)后，才能喚醒 P2 進(jìn)程。 用信號(hào)量可以實(shí)現(xiàn)進(jìn)程之間的同步。用 P 原語(yǔ)申請(qǐng)資源時(shí)，可能引起調(diào)用進(jìn)程的等待，而用 V原語(yǔ)釋放資源時(shí)，則可能啟動(dòng)某一等待進(jìn)程。 P/V操作在整個(gè)系統(tǒng)中是一一對(duì)應(yīng)的，這種不可分性保證了信號(hào)量值的完整性。在同一時(shí)刻只允許一個(gè)進(jìn)程執(zhí)行 P 或 V操作。 3. 管程 中國(guó)最大的管理資源中心 49 利用信號(hào)量和 P、 V 操作，雖可有效地解決并發(fā)進(jìn)程之間的同步與互斥問(wèn)題，但要求用戶自己使用同步原語(yǔ)設(shè)計(jì)程序處理同步與互斥關(guān)系，這樣既加重了用戶的編程負(fù)擔(dān)，又難以保證并發(fā)系統(tǒng)的正確性。 1971 年 提出了秘書進(jìn)程的概念 ，后經(jīng) Hansen 和 Hoare改變成管程并加以實(shí)現(xiàn)。管程的基本思想是：把分散在各進(jìn)程中的控制和管理臨界資源的臨界區(qū)集中起來(lái)統(tǒng)一管理。這樣既便于系統(tǒng)管理共享資源，又能保證互斥訪問(wèn)。 Hansen給管程的定義是：一個(gè)管程定義了一個(gè)數(shù)據(jù)結(jié)構(gòu)和在此數(shù)據(jù)結(jié)構(gòu)上能為并發(fā)程序所執(zhí)行的一組操作，這組操作能同步進(jìn)程和改變管程中的數(shù)據(jù)。 一個(gè)管程主要由三部分組成： ① 局部于該管程的共享數(shù)據(jù)，這些數(shù)據(jù)表示了相應(yīng)資源的狀