【正文】 */ parbegin producer:consumer。 signal(e)。 wait(s)。 forever End。 signal(s)。 wait(s)。 /*資源信號量 n，數(shù)據(jù)單元，初始化為 0 */ e:semaphore(:=sizeofbuffer)。 /* 緩沖區(qū)的大小 */ Var s:semaphore(:=1)。 生產(chǎn)一條數(shù)據(jù) 是否可用 是否有空存儲單元 存入一條數(shù)據(jù) 歸還使用權 數(shù)據(jù)單元加 1，喚醒一個消費者 有 是 阻塞等待資源 被喚醒 阻塞等待使用權 被喚醒 否 無 生產(chǎn)者 是否可用 是否有數(shù)據(jù)單元 取一條數(shù)據(jù) 歸還使用權 空單元加 1，喚醒一個生產(chǎn)者 有 是 阻塞等待資源 被喚醒 阻塞等待使用權 被喚醒 否 無 消費數(shù)據(jù) 消費者 Program producer_consumer。 ? 這顯然是不允許的，必須使生產(chǎn)者和消費者互斥進入緩沖區(qū)，即，某時刻只允許一個實體（生產(chǎn)者或消費者）訪問緩沖區(qū)，生產(chǎn)者互斥消費者和其它任何生產(chǎn)者。 ? 消費者從緩沖區(qū)中逐條取走數(shù)據(jù)，一次取一條數(shù)據(jù)，相應的存儲單元變?yōu)椤翱铡?，每取走一條數(shù)據(jù)， out指針向后移一個存儲單元位置。 生產(chǎn)者與消費者循環(huán)使用緩沖區(qū) ?不控制生產(chǎn)者 /消費者 ? 指針 in和 out初始化指向緩沖區(qū)的第一個存儲單元。 ? 假設緩沖區(qū)的大小為 n（存儲單元的個數(shù)），它可以被生產(chǎn)者和消費者循環(huán)使用。} } } 經(jīng)典進程互斥與同步問題 ? 生產(chǎn)者 /消費者問題 ? 讀者 /寫者問題 ? 哲學家進餐問題 生產(chǎn)者與消費者問題 生產(chǎn)者與消費者問題 ? 生產(chǎn)者與消費者是一個廣義的概念，可以代表一類具有相同屬性的進程。wait(g)。} {wait(e)。T5。signal(f)。} {wait(d)。T3。signal(d)。T2。signal(b)。 cobegin { {T1。 procedure2()。 critical section signal(mutex)。 critical section signal(mutex)。 semaphore mutex=1。 進程間的相互作用 ?利用信號量實現(xiàn)進程 互斥 的過程描述 ? 為使多個進程互斥地訪問某個臨界資源 ， 只需為該資源設置一個信號量 ， 并設其初始值為 1， 此時的信號量可以稱為 “ 互斥信號量 ” 。 ? 當僅有兩個并發(fā)進程共享臨界資源時，互斥信號量僅能取值 0、 1，其中， ? =1,表示無進程進入臨界區(qū) ? =0,表示已有一個進程進入臨界區(qū) ? =1,則表示已有一進程正在等待進入臨界區(qū) ? 當用 s來實現(xiàn) n個進程的互斥時， 的取值范圍為 1~ (n1) ? 操作系統(tǒng)內(nèi)核以系統(tǒng)調(diào)用形式提供 wait和 signal原語，應用程序通過該系統(tǒng)調(diào)用實現(xiàn)進程間的互斥。 ? 當 0時，表示已無資源可用，因此請求該資源的進程被阻塞，此時， 于該信號量阻塞隊列中的等待進程數(shù) 。 ? Wait操作用于申請資源（或使用權），進程執(zhí)行 wait原語時，可能會阻塞自己； ? Signal操作用于釋放資源（或歸還資源使用權），進程執(zhí)行 signal原語時，有責任喚醒一個阻塞進程。 ? 互斥信號量用于申請或釋放資源的使用權，常初始化為 1。P(2)。 其余部分 forever End。 臨界區(qū) 。 Procedure P(i:integer)。 const n=…。 ? 一旦其它某個進程執(zhí)行了 sigal(s)原語中的+1操作后，發(fā)現(xiàn) =0，即阻塞隊列中還有被阻塞進程，則調(diào)用喚醒原語，把，送就緒隊列，準備執(zhí)行臨界區(qū)代碼。 Wait、 singal的應用 ? 進程進入臨界區(qū)之前，首先執(zhí)行 wait(s)原語，若0,則進程調(diào)用阻塞原語，將自己阻塞，并插入到 。 Signal(s) :=+1。 定義對信號量的兩個原子操作 ? Wait(s)和 signal(s) ? 早期這兩個原語被稱作 P(s)和 V(s) Wait(s) :=。 信號量定義 Type semaphore=record Count:integer Queue:list of process End。 信號量實現(xiàn)互斥的基本原理 ? 兩個或多個進程可以通過傳遞信號進行合作，可以迫使進程在某個位置暫時停止執(zhí)行（阻塞等待），直到它收到一個可以“向前推進”的信號（被喚醒）。 ? 信號量方法能實現(xiàn)進程互斥與同步，而不必“忙等”。這樣， P1將一直占用臨界區(qū)被中斷， P2一直“忙等”，如果沒有外力的作用，這種“僵持”狀態(tài)將一直保持下去，即系統(tǒng)出現(xiàn)死鎖。若 P2也需要進入該臨界區(qū)，由于臨界區(qū)被 P1占用， P2“忙等”。 互斥與同步解決方法之二：硬件方法 機器指令的缺點 ? 還可能導致死鎖。 ? 可能出現(xiàn)饑餓現(xiàn)象。 進程都需要循環(huán)檢測，等待時機進入臨界區(qū)。 ? 可以分別為臨界區(qū)設置屬于它自己的變量，以實現(xiàn)對多個臨界區(qū)的互斥訪問。 … P(n)。 parbegin P(1)。 其余部分 forever end。 臨界區(qū) 。 begin repeat key:=1。 proceduce P(I:integer)。 const n=…。 r:=temp。 begin temp:=m。var m:memory)。 P(2)。 begin /*主程序 */ bolt:=0。 bolt:=0。 begin repeat repeat {nothing} until testset (bolt)。 const n=…。 end else testset:=false。 begin if i=0 then begin i:=1。 互斥與同步解決方法之二：硬件方法 專用機器指令 ? 利用一些專用機器指令也能實現(xiàn)互斥，機器指令在一個指令周期內(nèi)執(zhí)行，不會受到其它指令的干擾，也不會被中斷。 ? 因為中斷被屏蔽以后，系統(tǒng)將無法響應任何外部請求，也不會響應當前執(zhí)行進程的任何異常及系統(tǒng)故障，嚴重地降低了處理機性能。 打開中斷 。 互斥與同步解決方法之二：硬件方法 屏蔽中斷 Repeat 屏蔽中斷 。 ? 中斷被屏蔽以后，系統(tǒng)時鐘中斷也被屏蔽，處理機將不會被切換到其他進程。 互斥與同步解決方法之二：硬件方法 屏蔽中斷 ? 由于進程切換需要依賴中斷來實現(xiàn)，如果屏蔽中斷，則不會出現(xiàn)進程切換。 ? 軟件方法始終不能解決“忙等”現(xiàn)象，降低系統(tǒng)效率。 互斥與同步解決方法之二：硬件方法 ? 采用 軟件方法 實現(xiàn)進程互斥使用臨界資源是很困難的，它們 通常實現(xiàn)兩個進程互斥 ，很難控制多個進程互斥。 flag[0]:=false。 臨界區(qū) 。 flag[0]:=true。 while flag[1] do if turn=1 then begin flag[0]:=false。 P0執(zhí)行的流程圖 Procedure P0。 flag[1]:=false。 臨界區(qū) 。 flag[1]:=true。 while flag[0] do if turn=0 then begin flag[1]:=false。 Procedure P1。 flag[0]:=false。 臨界區(qū) 。 flag[0]:=true。 while flag[1] do if turn=1 then begin flag[0]:=false。 /*共享的全局變量，表示進入臨界區(qū)的順序 */ Procedure P0。 parend end Var flag:array[0..1] of boolean:false。 parbegin P0。 flag[1]:=false。P1。turn:=1。 begin /*主程序 */ flag[0]:=false。 flag[1]:=false。 臨界區(qū) 。 flag[1]:=true。 while flag[0] do if turn=0 then begin flag[1]:=false。 /*共享的全局變量，表示進入臨界區(qū)的順序 */ Procedure P1。 Var flag:array[0..1] of boolean:false。 flag[0]:=false。 臨界區(qū) 。 flag[0]:=true。 while flag[1] do if turn=1 then begin flag[0]:=false。 Procedure P0。 ? 但是，這種現(xiàn)象也是不希望出現(xiàn)的。 … 分析：第三次改進 ? P0、 P1的“謙讓”可能使它們都不能進入臨界區(qū)。 臨界區(qū) 。 flag[1]:=true。 While flag[0] do Begin flag[1]:=false。 Flag[0]:=false。 End。 延遲一小段時間 。/*共享的全局變量 */ P0 … Flag[0]:=true。 互斥與同步解決方法之一：軟件方法－第三次改進 ? 互斥算法的第二次改進可能導致死鎖，因為Ｐ 0、Ｐ１都“堅持自己的權利，執(zhí)意進入臨界區(qū)，且互不謙讓”． ? 可以考慮，允許進程既表明需要進入臨界區(qū)的“態(tài)度”，又能相互“謙讓”，即首先表示自己需要使用臨界區(qū)，再檢測臨界區(qū)的狀態(tài)，若臨界區(qū)“被占用”，可以等一小段時間再申請。 … … 互斥算法：第二次改進 分析：第二次改進 ? 假設 P0需要進入臨界區(qū)，首先執(zhí)行flag[0]:=true，再執(zhí)行 while flag[1],若 P1正在占用臨界區(qū)，則 P0忙等；否則， P0進入臨界區(qū)。 臨界區(qū) Flag[0]:=false。 flag[1]:=true While flag[1] do {nothing}。 Var flag:array[0..1]of boolean:false。從而，可能出現(xiàn)同時進入臨界區(qū)的現(xiàn)象。 互斥與同步解決方法之一：軟件方法 ——第二次改進 ? 互斥算法的第一次改進不能實現(xiàn)“互斥”。 ? 問題 1：“忙等” ? 問題 2：若進程在臨界區(qū)內(nèi)失敗且相應的Flag為 true，則其他進程永久阻塞。 flag[1]:=false。 flag[1]:=true 臨界區(qū) 。 while flag[0] do {nothing}。 Var flag:array[0..1]of boolean:false。當臨界區(qū)空閑時，任何一個進程都能進入，但此時必須修改臨界區(qū)標志為“被占用”，別的進程就不能進入臨界區(qū)，當臨界區(qū)使用完畢，必須修改該標志為“空閑”。 ? 因為兩個進程相互依賴對方將臨界區(qū)的使用權（順序）進行修改，一旦這種修改不能進行，對方都將因為等待臨界區(qū)而無法推進。這不符和互斥原則，降低了系統(tǒng)性能。 ? 假設 turn的初值為 0，進程 P0正好先請求進入臨界區(qū)，并成功進入臨界區(qū)執(zhí)行，這時，如果 P1申請進入臨界區(qū)，循環(huán)檢測 turn=0，不可以進入，只能“空”循環(huán)，等待。如果進程需要多次使用臨界區(qū)，那么，使用臨界區(qū)頻率低的進程嚴重制約著使用臨界區(qū)頻率高的進程的執(zhí)行進度。