【正文】 中國最大的管理資源中心 42 bolt =0。 exchange指令定義如下： void exchange(int register, int memory) { int temp。 } 該指令交換一個(gè)寄存器和一個(gè)存儲器單元的內(nèi)容。 while ( 1 ) { keyi = 1。 parbegin(P⑴ , P⑵ .... ,P(n))。 ? 非常簡單且易于證明。 ? 可能發(fā)生餓死現(xiàn)象。如果 P2試圖使用與 P1 相同的資源，由于互斥機(jī)制，它將被拒絕訪問。 int turn。 } 臨界區(qū) 中國最大的管理資源中心 44 turn = 1。 while ( turn == 0) /* 什么也不做 */ flag [1] = true。 flag[0] = false。當(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。 turn = 1。 臨界區(qū) flag [0] = false。 while( flag[0]amp。 /* 其余部分 */。 同步機(jī)制 解決同步問題有若干種方法，有些方法既可以用作同步，也可以用作互斥。在這兩個(gè)原語中設(shè)置一個(gè)公共變量 X代表某個(gè)臨界資源的 狀態(tài)。 ③ 釋放臨界資源，置 X 為 0（開鎖）。這是因?yàn)槿魏蜗脒M(jìn)入臨界區(qū)的進(jìn)程都不能直接進(jìn)入，它們必須不停地循環(huán)檢查 X的值，等待 X 變?yōu)?0。 P/V操作由 P 操作原語和 V操作原語組成，其意義是在一個(gè)被稱之為信號燈變量的 S 上定義了兩個(gè)操作，該變量的值只能由 P 操作和 V操作進(jìn)行修改。 V操作原語定義如下： V（ S） { S++； if S=0 wakeup ( )； } 即：當(dāng)執(zhí)行 V操作時(shí)，表示進(jìn)程釋放資源，將信號燈變量 S的值加 1，如果 S≤ 0，則喚醒 S 信號量隊(duì)列隊(duì)首的阻塞進(jìn)程，將其狀態(tài)從阻塞狀態(tài)轉(zhuǎn)變到就緒狀態(tài)，執(zhí)行 V（ S）者繼續(xù)執(zhí)行。 信號量和 P/V操作是實(shí)現(xiàn)進(jìn)程互斥與同步的非常有效的方法。 我們再來看一個(gè)用 P/V操作解決進(jìn)程間同步問題的例子。當(dāng) P2進(jìn)程執(zhí)行了 V(S1)操作后，P1進(jìn)程才可向緩沖區(qū) B 輸入下一個(gè)數(shù)據(jù)。用 P 原語申請資源時(shí)，可能引起調(diào)用進(jìn)程的等待，而用 V原語釋放資源時(shí)，則可能啟動某一等待進(jìn)程。 1971 年 提出了秘書進(jìn)程的概念 ，后經(jīng) Hansen 和 Hoare改變成管程并加以實(shí)現(xiàn)。 一個(gè)管程主要由三部分組成： ① 局部于該管程的共享數(shù)據(jù)，這些數(shù)據(jù)表示了相應(yīng)資源的狀態(tài)； ② 局部于該管程的一組操作過程，每個(gè)過程完成對上述數(shù)據(jù)的某種規(guī)定操作； ③ 對局部于該管程的數(shù)據(jù)的初始化。為了實(shí)現(xiàn)對臨界資源的互斥訪問，管程每次只允許一個(gè)進(jìn)程進(jìn)入其內(nèi)（即訪問管程內(nèi)的某個(gè)過程），這是由編譯系統(tǒng)保證的。對于條件變量 x 有兩種操作： 和 ，其中 x 為條件變量。事實(shí)上，計(jì)算機(jī) 系統(tǒng)中的許多問題都可歸結(jié)為生產(chǎn)者與消費(fèi)者問題，例如：對于需要輸出打印文件的某用戶進(jìn)程和相對于打印機(jī)的管理進(jìn)程，對各臨界資源的各種操作 中國最大的管理資源中心 50 該用戶進(jìn)程是生產(chǎn)者，而后者便是消費(fèi)者；同理，若該用戶進(jìn)程需要讀入一個(gè)磁盤文件，相對于磁盤管理進(jìn)程，該用戶進(jìn)程是消費(fèi)者，而磁盤管理進(jìn)程則是生產(chǎn)者。這里既存在合作同步問題，也存在臨界區(qū)互斥問題。 滿 j i 空 圖 11 生產(chǎn)者與消費(fèi)者問題 下面給出基于環(huán)形緩沖區(qū)的生產(chǎn)者與消費(fèi)者關(guān)系的形式描述，設(shè)： ① 公用信號量 mutex：初值為 1，用于實(shí)現(xiàn)臨界區(qū)互斥； ② 生產(chǎn)者私用信號量 empty：初值為 n，指示空緩沖塊數(shù)目； ③ 消費(fèi)者私用信號量， full初值為 0，指示滿緩沖塊數(shù)目； ④ 整型量 i和 j：初值均為 0， i指示空緩沖塊序號頭指針， j指示滿 緩沖塊序號頭指針。 } } void consumer( ) /*消費(fèi)者進(jìn)程 */ { while⑴ { P(full)； P(mutex)； product =buffer[j]； j=(j+1) % n； V(mutex)。 注意：在此模塊中無論是生產(chǎn)者還是消費(fèi)者，關(guān)于 P 操作的次序不能顛倒，否則可能造成死鎖。 condition notfull, notempty 。 count++。 out =(out+l) % n。 PC. put(item)。 } 由此可見，利用管程機(jī)制解決進(jìn)程同步問題，大大簡化了程序員的工作，減少了出錯(cuò)機(jī)會，同時(shí)也可以避免死鎖的發(fā)生。 所有類似的這類問題都可歸結(jié)為“讀者 — 寫者問題”。 readcount++。 P(mutex)。 } } void writer( ) { while ⑴ { P(wsem)。 中國最大的管理資源中心 54 } 其中： 變量 readcount 記錄當(dāng)前正在訪問該對象的讀者個(gè)數(shù)； 互斥信號量 mutex 用來互斥對 readcount 的修改； 互斥信號量 wsem 用于寫者互斥， 它也可由當(dāng)前第一個(gè)要求訪問該對象的讀者和最后一個(gè)退出訪問的讀者使用，但它不被中間的那些讀者使用。隨后其它的讀者到來，這樣只要 有一個(gè)讀者活躍，隨后而來的讀者都被允許訪問數(shù)據(jù)庫。 對于修改頻繁的問題，應(yīng)采用寫者優(yōu)先算法。 P(rsem)。 V(mrc)。 readcount。 writecount++。 WRITE。, V(mwc)。 V(mrc)。 READ。 readcount++。 semaphore mrc=l, mwc= 1, wr=1, wsem=1, rsem=l。假如每 2秒鐘來一個(gè)讀者，而 該 操作時(shí)間為 5 秒鐘，則寫者將永遠(yuǎn)不能訪問數(shù)據(jù)庫，或者說寫者發(fā)生了饑餓現(xiàn)象。 設(shè)想當(dāng)一個(gè)讀者在使用數(shù)據(jù)庫時(shí)，另一個(gè)讀者也來訪問數(shù)據(jù)庫，由于同時(shí)允許多個(gè)讀者同時(shí)進(jìn)行讀操作， 所 以第二個(gè)讀者也被允許進(jìn)入，同理第三個(gè)及隨后更多的讀者都被允許進(jìn)入。 V(wsem)。 if (readcount == 0) V(wsem)。 V(mutex)。下面給出讀者進(jìn)程與寫者進(jìn)程的解法： 讀者優(yōu)先 : int readcount=0； semaphore mutex = 1, wsem=1。顯然，如果有兩個(gè)甚至更多個(gè)讀者同時(shí)訪問這個(gè)可共享數(shù)據(jù)對象，那么任何一個(gè)讀者的訪問結(jié)果都 是正確的。 consume the item in nexte。 if 。 中國最大的管理資源中心 52 } void get(item) . { if (count= 0) 。 buffer [in]=nextp。 { int in= 0,out=0,count=0 。 consume the product； } } void main( ) { parbegin (producer( ), consumer( ))。 void producer( ) /*生產(chǎn)者進(jìn)程 */ { while⑴ { produce next product； P(empty)； P(mutex)； buffer[i]=product； i=(i+1) % n； 中國最大的管理資源中心 51 V(mutex)。這是相互合作同步。每個(gè)生產(chǎn)者可不斷地每次往緩沖池中送一個(gè)生產(chǎn)的產(chǎn)品，而每個(gè)消費(fèi)者則可不斷地每次從緩沖池中取出一個(gè)產(chǎn)品。 經(jīng)典同步問題 把同步問題歸納為幾個(gè)典型的范例，就是經(jīng)典的同步問題。為此，引入了條件 (condition)變量及其操作的概念。因此管程就如同一堵圍墻把關(guān)于某個(gè)共享資源的抽象數(shù)據(jù)結(jié) 構(gòu)以及對這些數(shù)據(jù)施行特定操作的若干過程圍了起來。這樣既便于系統(tǒng)管理共享資源，又能保證互斥訪問。在同一時(shí)刻只允許一個(gè)進(jìn)程執(zhí)行 P 或 V操作。只有當(dāng) P1進(jìn)程執(zhí)行了 V (S2)后，才能喚醒 P2 進(jìn)程。 P P2 之間存在互斥關(guān)系（兩個(gè)進(jìn)程不能同時(shí)對緩沖區(qū)進(jìn)行操作），也存在同步關(guān)系（一個(gè)進(jìn)程的能否執(zhí)行與另一個(gè)進(jìn)程密切相關(guān)）。為了不使隊(duì)列指針指向錯(cuò)誤位置，需要嚴(yán)格限制一次只能有一個(gè)進(jìn)程存取該隊(duì)列元素。 P/V 操作的物理解釋是：信號燈變量 S 可以表示某類臨界資源，其值可以看作是可用資源數(shù)，執(zhí) 行一次 P 操作，相當(dāng)于申請一個(gè)資源，執(zhí)行一次 V操作，相當(dāng)于釋放一個(gè)資源。 P 操作原語定義如下： P（ S） { S。 1965 年 引進(jìn) 了比 lock/unlock原語的更一般的形式 P/V操作來克服這種忙碌等待現(xiàn)象，大大地簡化了進(jìn)程的同步與互 斥。 } 開鎖原語 unlock(X)： { X=0； } 值得注意的是，在檢查 X 的值和置 X 為 1(關(guān)鎖 )這兩步之間， X 值不能被其它進(jìn)程所改變。當(dāng) X=1 時(shí)，表示資源正在使用，于是返回繼續(xù)進(jìn)行檢查；當(dāng) X=0時(shí)，表示資源可以使用，則置 X 為 1（關(guān)鎖）。 這里介紹三種同步機(jī)制：鎖、信號量和管程。 考慮進(jìn)程 P0，一旦它把 flag[0]置為 true， Pl不能進(jìn)入其臨界區(qū)；如果 P1已經(jīng)在臨界區(qū)中，則flag[1]=true，且 P0 被阻止進(jìn)入臨界區(qū)。 turn==0) /*什么也不做 */。 } } void P1( ) { while (true) { flag [1] = true。amp。 中國最大的管理資源中心 45 int turn。 parbegin(P0( ) , P1( ))。 flag[1]= false。 其余部分 } } void P1( ) { while (true) { flag [1]= t