OS-04進程同步與互斥

操作系統(tǒng)原理金海溶blue1879@辦公室：2A314操作系統(tǒng)設(shè)計中的核心問題是關(guān)于進程和線程的管理多道程序技術(shù) 管理單處理器系統(tǒng)中的多個進程多處理技術(shù) 管理多處理器系統(tǒng)中的多個進程分布處理技術(shù) 管理多臺分布式計算機系統(tǒng)(集群)中多個進程的執(zhí)行§4.1并發(fā)進程進程并發(fā)要解決的主要問題互斥：進程之間的間接制約關(guān)系。當(dāng)一個進程使用某資源時，另一個進程必須等待——并發(fā)的基本需求實現(xiàn)互斥包括軟件方法(“忙等待”技術(shù))和支持互斥的硬件機制等同步：進程間的的直接制約關(guān)系，進程間的活動有相互依賴和合作的關(guān)系通信：不同進程之間傳播或交換信息進程并發(fā)順序執(zhí)行的特性

順序性，資源獨占，可再現(xiàn)性

并發(fā)執(zhí)行的特點：

不可再現(xiàn)性

制約性

資源共享

回顧順序執(zhí)行和并發(fā)執(zhí)行的特點并發(fā)的例子及并發(fā)后的問題并發(fā)

在同一時間段內(nèi)，多個進程同時運行；宏觀上并發(fā)，微觀上順序執(zhí)行。并發(fā)后產(chǎn)生了資源的競爭和共享問題，而且進程的執(zhí)行速度及進程的執(zhí)行序列都是不可預(yù)測的一個例子與時間有關(guān)的錯誤考慮下面一個字符回顯的的過程voidecho()

{chin=getchar();

chout=do(chin);

putchar(chout);}從鍵盤獲得輸入，每擊一下鍵，輸入字符就保存在變量chin中，然后處理后傳送給變量chout，并回送顯示器任何程序可以重復(fù)地調(diào)用此過程，接收用戶輸入，并在用戶的屏幕上顯示與時間有關(guān)的錯誤考慮一個支持單用戶單處理器、多道程序設(shè)計系統(tǒng)將其當(dāng)作一個共享過程，載入到所有應(yīng)用程序公用的全局存儲區(qū)中。這樣每個應(yīng)用程序都能使用這個過程，由于每個應(yīng)用程序只需使用echo過程的一個副本，從而節(jié)省空間進程間共享主存是非常有用的，它允許進程間有效而緊密的交互，有利于進程的相互通信。但是，共享也可能會帶來一些問題與時間有關(guān)的錯誤

voidecho()

{chin=getchar();

chout=do(chin);

putchar(chout);}考慮下面的順序進程P1調(diào)用echo過程，并在getchar函數(shù)結(jié)束后立即被中斷，此時，最近輸入的字符x被保存在變量chin中進程P2被激活并調(diào)用echo過程，echo過程運行得出結(jié)果，輸入然后在屏幕上顯示單個的字符y進程P1被恢復(fù)。此時chin中值x被寫覆蓋，因此已丟失，而chin中的值y被傳送給chout并顯示出來第一個字符丟失，第2個字符被顯示了兩次與時間有關(guān)的錯誤

voidecho()

{chin=getchar();

chout=do(chin);

putchar(chout);}

getchar（）chinchout

putchar（）P1P2getchar（）XXgetchar（）YYYputchar（）YYY？echo與時間有關(guān)的錯誤錯誤原因之1：進程執(zhí)行交叉;錯誤原因之2：涉及公共變量(chin和chout)。解決方案：一次只允許一個進程調(diào)用echo過程：進程P1調(diào)用echo過程，并在getchar函數(shù)結(jié)束后立即被中斷，此時，最近輸入的字符x被保存在變量chin中進程P2被激活并調(diào)用echo過程。但是，由于P1仍然在echo過程中，盡管當(dāng)前P1處于就緒狀態(tài)，P2仍被阻塞，不能進入這個過程。因此，P2被阻塞，等待echo過程可用一段時間后進程P1被恢復(fù)，完成echo的執(zhí)行，顯示出正確的字符xP1退出echo后，解除了P2的阻塞，P2被恢復(fù)，成功地調(diào)用echo過程與時間有關(guān)的錯誤

voidecho()

{chin=getchar();

chout=do(chin);

putchar(chout);}

P1

voidecho()

{chin=getchar();chout=do(chin);

putchar(chout);}

調(diào)用echo超時，就緒P2調(diào)用echo資源正忙阻塞狀態(tài)調(diào)度運行釋放echo喚醒獲取資源就緒狀態(tài)調(diào)度運行由此可見，解決共享資源的保護，唯一的辦法是互斥的使用共享資源（如變量，代碼等）即：一次只允許一個進程訪問共享資源臨界資源和臨界區(qū)：臨界資源

某些在一段時間內(nèi)只允許一個進程使用的共享資源稱為臨界資源臨界區(qū)（段）訪問臨界資源的程序段稱為臨界區(qū)。即互斥執(zhí)行的程序段進程同步與互斥進程P1和P2共享同一打印機資源，其操作流程如下：

p1:entrycode使用打印機exitcodep2:entrycode使用打印機exitcode系統(tǒng)打印機即為——臨界資源P1和p2的訪問臨界資源打印機的代碼即為——臨界區(qū)進程同步與互斥進程互斥的實現(xiàn)Repeat

臨界區(qū)

其余代碼Untilfalseentrysectionexitsection例：司機-售票員問題司機活動：售票員活動：

do{do{

啟動車輛關(guān)車門正常行駛售票到站停車開車門

}while(1)}while(1)同步的例子互斥：軟件方法Peterson算法Dekker算法Lamport面包店算法Eisenberg/Mcguire算法進程同步與互斥互斥：硬件的支持中斷禁用在單處理器機器中，并發(fā)進程不能重疊,只能交替。此外，一個進程將一直運行，直到它調(diào)用了一個操作系統(tǒng)服務(wù)或被中斷。因此，為保證互斥，只需要保證一個進程不被中斷就可以當(dāng)一個計算機系統(tǒng)包括多個處理器時，在這種情況下，禁止中斷不能保證互斥進程同步與互斥互斥：硬件的支持專門的機器指令在硬件級，對存儲器單元的訪問排斥到相同單元的其他訪問。基于這一點，處理器的設(shè)計者提出了一些機器指令，用于保證兩個動作的原子性，如在一個取指令周期中對一個存儲器單元的讀和寫或者讀和測試。由于這些動作在一個指令周期中執(zhí)行，它們不會受到其他指令的干擾如：test-and-set指令，swap指令等進程同步與互斥信號量（Semaphore）管程(monitor)事件典型同步機制Lock和unlock關(guān)鎖和開鎖是加鎖機制的2個基本操作。在其中設(shè)置一公共變量x代表某個臨界資源的狀態(tài)

X＝1表示資源可用

X＝0表示資源正在被使用進程使用臨界資源必須做如下三個不可分割的操作

進程同步與互斥1)檢查x的值。x=0，資源正在使用，返回繼續(xù)進行檢查；

x=1，資源可以使用，置x為0(關(guān)鎖)2)進入臨界區(qū)，訪問臨界資源3)釋放資源,退出臨界區(qū)，置x為1(開鎖)通過分析，給出關(guān)鎖和開鎖操作的描述關(guān)鎖lock[x] L:ifx=0thengotoLelsex:=0;開鎖unlock[x] x:=1;Lock和unlock缺點：使用了忙等待，當(dāng)一個進程在等待資源時，依然會消耗CPU時間可能會發(fā)生饑餓，有些進程由于長時間得不到資源?？赡軣o法徹底實現(xiàn)互斥，有可能2個及以上的進程進入臨界區(qū)。可能死鎖。當(dāng)?shù)蛢?yōu)先級進程獲取資源的情況下，被高優(yōu)先級進程搶占cpu，且高優(yōu)先級進程申請同一資源，由于互斥機制，高優(yōu)先級進程會進入永遠的忙等待。Lock和unlock信號量（semaphore）：一個與資源有關(guān)的，初值為非負數(shù)的整型變量稱為信號量。用S表示，初值和資源有關(guān)信號量是一種特殊的變量，只能由semWait，semSignal原語進行操作訪問。信號量機制semWait原語（P原語）——semWait（S）/

P(S)S:=S-1；如果S>=0，則表示有資源，該進程繼續(xù)執(zhí)行；如果S<0，則表示已無資源，執(zhí)行原語的進程被置成阻塞狀態(tài)，并使其在S信號量的隊列中等待，直至其他進程在S上執(zhí)行semSignal操作釋放它為止信號量機制semSignal原語（V原語）——semSignal（S）/V(S)S:=S+1如果S>0，則該進程繼續(xù)執(zhí)行如果S<＝0，說明有進程被掛起，則喚醒一阻塞進程，即從S信號量的等待隊列首摘下一個PCB，將其置為就緒狀態(tài)，執(zhí)行semSignal(S)者繼續(xù)執(zhí)行semWait操作可能會引起進程的阻塞，semSignal操作不會引起本身進程狀態(tài)的變化，但可能喚醒其他進程，使其從阻塞狀態(tài)轉(zhuǎn)變到就緒狀態(tài)信號量機制semWait/semSignal原語都是低級通信原語，一個正在執(zhí)行semWait/semSignal

操作的進程，不允許任何其他進程中斷它的操作，這樣就保證了同時只能有一個進程對信號量S施行semWait或semSignal實現(xiàn)互斥的例子與分析

打印機是一種臨界資源，必須互斥使用，則：

semWait(S)使用打印機semSignal(S)信號量機制P1P2P3P4關(guān)于s信號量的阻塞隊列

信號量S的初值為：2semWait(s)S=s-1=1semWait(s)S=s-1=0semWait(s)S=s-1=-1P3semWait(s)S=s-1=-2P4semSignal(s)S=s+1=-1喚醒就緒semSignal(s)S=s+1=0喚醒就緒semSignal(s)S=s+1=1semSignal(s)S=s+1=2用信號量實現(xiàn)同步的例子：司機-售票員問題：司機活動：售票員活動：

Do{Do{

關(guān)車門啟動車輛正常行駛售票到站停車

開車門

}While(1)

}While(1)信號量機制設(shè)置信號量S1,初值為0，用于司機“啟動汽車”和售票員“關(guān)車門”的同步設(shè)置信號量S2,初值為0，用于司機“到站停車”和售票員“開車門”的同步信號量機制（這里我們用pv描述）例子：司機-售票員問題：VARs1,s2:semaphore;(initialvalue0)司機活動：售票員活動：

Do{Do{

P(S1)

關(guān)車門

啟動車輛V(S1)

正常行駛售票到站停車P(S2)

V(S2)開車門

}While(1)}While(1)分析：從以上幾個例子可以看出在semWait中S:=S-1表示進程請求獲得一個資源當(dāng)信號量S>0時，S的值表示某類資源可用的數(shù)量S<0

表示無資源分配給請求的進程，于是將它排在信號量S的等待隊列Q中，這時S的絕對值正好等于信號量隊列Q上的進程數(shù)目semSignal中的S:=S+1可知進程釋放了一個資源信號量機制信號量需要使用隊列來保存在信號量上等待的進程，進程按照某個順序從隊列中移出最公平的策略是先進先出(FIFO):被阻塞時間最久的進程最先從隊列釋放，定義中包括這個策略的信號量稱為強信號量沒有規(guī)定進程從隊列中移出順序的信號量稱為弱信號量強信號量保證不會餓死，是操作系統(tǒng)提供的典型的信號量形式信號量機制一個強信號量的例題：現(xiàn)有四個進程A、B、C、D，進程A、B、C依賴于進程D的結(jié)果，且進程D的一個計算結(jié)果只能作為A、B、C進程其中一個的輸入數(shù)據(jù)分析：進程A、B、C與進程D之間有相互協(xié)作關(guān)系——同步對于進程D的同一個計算結(jié)果，只能給進程A、B、C中的一個使用——某種意義上也是互斥設(shè)置信號量S，表示現(xiàn)有資源數(shù)（即可用的D的計算結(jié)果，設(shè)s當(dāng)前值為1）信號量機制//A、B、C的程序偽代碼whiletruedo{semWait(S);

取得一個D的輸出數(shù)據(jù)；

處理數(shù)據(jù)；

一次處理完畢，sleep(2)；}信號量機制//D的程序偽代碼

whiletruedo{處理數(shù)據(jù)；輸出一數(shù)據(jù)

semSignal(S);

一次任務(wù)完成，sleep(2)；}DCA處理器信號量Bs=0②就緒隊列阻塞隊列semWait(S)semWait(S)處理器①信號量s=1阻塞隊列ABDC就緒隊列BDCAs=0

AS=-1BABD處理器信號量Cs=0④就緒隊列阻塞隊列semSignal(S)semWait(S)處理器③信號量s=-1阻塞隊列CA就緒隊列DBBs=0DBDs=-1CsemWait(S)As=-2ADBs=-2處理器⑤信號量s=-2阻塞隊列DB就緒隊列ACsemSignal(S)處理器⑥信號量s=-2阻塞隊列B就緒隊列DACS=-1ABC生產(chǎn)者/消費者問題是著名的進程同步問題p109問題描述有一組生產(chǎn)者進程和一組消費者進程。生產(chǎn)者進程生產(chǎn)物品（某種類型的數(shù)據(jù)）；消費者進程消費物品。為使生產(chǎn)者和消費者進程并發(fā)執(zhí)行，在它們之間設(shè)置了一個具有n個緩沖區(qū)的緩沖池。生產(chǎn)者將他們生產(chǎn)的物品放入一個緩沖區(qū)中，消費者每次從一個緩沖區(qū)中取一個物品進行消費。生產(chǎn)者和消費之間必須保持一定的同步關(guān)系：不允許消費者進入空的緩沖池取物品，也不允許生產(chǎn)者向已滿的緩沖池中放物品。生產(chǎn)者/消費者問題p1p2p3p4pic1c2c3c4ci......生產(chǎn)者/消費者問題p1p2p3p4pic1c2c3c4ci......生產(chǎn)者/消費者問題管理員，怎么沒東西！消費者對生產(chǎn)者有依賴關(guān)系：只有生產(chǎn)者生產(chǎn)出產(chǎn)品，才能給消費者提供產(chǎn)品消費p1p2p3p4pic1c2c3c4ci......生產(chǎn)者/消費者問題生產(chǎn)者對消費者有依賴關(guān)系：只有消費者消費掉產(chǎn)品，才能給生產(chǎn)者提供存放產(chǎn)品的空間p1p2p3p4pic1c2c3c4ci......生產(chǎn)者/消費者問題p1c1同一時刻只允許一個生產(chǎn)者或者一個消費者進入緩沖池（倉庫）分析生產(chǎn)者與生產(chǎn)者之間——互斥消費者與消費者之間——互斥生產(chǎn)者與消費者之間——即有同步又有互斥設(shè)置信號量（設(shè)初始緩沖池為空，共有n個緩沖區(qū)）用于互斥的公共信號量：s＝1，表示緩沖池可用-倉庫

生產(chǎn)者的私有信號量：empty＝n，表示可用緩沖區(qū)-空位

消費者的私有信號量：full＝0，表示可用數(shù)據(jù)-物品偽代碼實現(xiàn)生產(chǎn)者/消費者問題Procedureproducer(){//生產(chǎn)者進程程序代碼

whiletruedo{producenextproduct;

semWait(empty);

semWait(s);buffer(in):=product;in:=(in+1)modn;

semSignal(full);

semSignal(s);}}生產(chǎn)者/消費者問題Procedureconsumer(){//消費者進程程序代碼whiletruedo{

semWait(full);

semWait(s);goods:=buffer(out);out:=(out+1)modn;

semSignal(empty);

semSignal(s);consumeproduct}}生產(chǎn)者/消費者問題ParbeginProcedureproducer()；Procedureconsumer()；parend生產(chǎn)者/消費者問題生產(chǎn)者和消費者中的兩個semWait語句分別可以互換嗎，為什么？

semWait(empty);semWait(full);semWait(s);semWait(s);生產(chǎn)者/消費者問題想一想讀者和寫者問題一個文件或記錄（即數(shù)據(jù)對象）可被多個進程共享。有些進程只要求讀—reader；有些進程要修改內(nèi)容—writer。允許多個reader進程同時讀一個共享對象；但不允許writer進程和其他writer進程或reader進程同時訪問共享數(shù)據(jù)對象分析：對于writer，只需在訪問數(shù)據(jù)對象前，對信號量做semWait操作，釋放數(shù)據(jù)對象時，做semSignal操作。對于reader，第一個訪問數(shù)據(jù)對象者，要對信號量做一個semWait操作，而semSignal操作，則由最后一個釋放對象的執(zhí)行讀者和寫者問題因此設(shè)置一個變量readcount，以表示正在進行讀操作的進程數(shù)目，初值為0。則進入：每增加一個reader進程，readcount＝readcount+1

readcount＝1，reader進程對讀寫互斥信號量執(zhí)行

semWait操作退出：

每個reader進程退出，則readcount＝readcount-1readcount＝0，reader進程執(zhí)行semSignal操作讀者和寫者問題設(shè)置信號量寫者與其它寫者和讀者的互斥信號量：wrt初值為1；讀者對于readcount的互斥信號量：x,初值為1實現(xiàn)同步互斥關(guān)系

讀者和寫者問題§4.2進程的同步與互斥—信號量writer：P（wrt）writingV（wrt）Reader:P(x)Readcount++P(wrt)V(x)readingP(x)Readcount--V(x)V(wrt)=1!=1=0!=0writer；beginsemWait（wrt）；

writingisperforming；

semSignal（wrt）；

end；讀者和寫者問題reader；

begin

semWait（x）；Readcount＝readcount+1；

ifreadcount==1then

semWait(wrt);

semSignal（x）；

readingisperfoming；

semWait（x）；Readcount＝readcount-1；

ifreadcount==0then

semSignal(wrt);

V（x）；beginreadcount=0;wrt.value=1;x.value=1;cobeginr1:reader;……;rm:reader;w1:writer;……;wn:writer；coendend讀者和寫者問題問題：讀者源源不斷，read_count不歸0，寫者會被餓死。策略：一旦有寫者等待，新到達讀者等待，等正在讀的讀者都結(jié)束后，寫者先進入，即寫者優(yōu)先。實現(xiàn)代碼如下：讀者和寫者問題reader：BeginsemWait(z);semWait(rsem);semWait(x);readcount++;if(readcount==1)semWait(wsem);

semSignal(x);semSignal(rsem);semSignal(z);READUNIT();semWait(x);readcount--;if(readcount==0)

semSignal(wsem);semSignal(x);endwriter：Begin

semWait(y);

writecount++;

if(writecount==1)

semWait(rsem);

semSignal(y);semWait(wsem);WRITEUNIT();semSignal(wsem);semWait(y);

writecount--;

if(writecount==0)

semSignal(rsem);semSignal(y);endbeginreadcount=0;writecount=0;wsem.value=1;rsem.value=1;x.value=1;

y.value=1;cobeginr1:reader;……;rm:reader;w1:writer;……;wn:writer；coendend讀者和寫者問題理發(fā)室椅子入口出口等候室簡單理發(fā)店問題一個理發(fā)店由一個有幾張椅子的等候室、一個放有一張理發(fā)椅的理發(fā)室和一個理發(fā)師組成。若沒有要理發(fā)的顧客，則理發(fā)師就去睡覺；若一顧客走進理發(fā)店且所有的椅子都被占用了，則該顧客就離開理發(fā)店；若理發(fā)師正在為人理發(fā)，則該顧客就找一張空椅子坐下等待;若理發(fā)師在睡覺，則顧客就喚醒他。簡單理發(fā)店問題分析只有當(dāng)顧客坐上理發(fā)椅，理發(fā)師才開始理發(fā)—同步當(dāng)正在理發(fā)的顧客理好發(fā)，等待的顧客才能理發(fā)—同步同一時刻只有一個顧客能理發(fā)——互斥同一時刻只有有限的顧客能在等待室等待——互斥資源與信號量對于理發(fā)師：坐上理發(fā)椅的顧客，信號量barber＝0對于理完發(fā)的顧客：是否有顧客等待，信號量wait＝0對于進入的顧客：是否有人在理發(fā)，及等候室是否已滿，變量count＝0保證對共享變量count的互斥訪問的信號量：entry＝1簡單理發(fā)店問題//共享數(shù)據(jù)結(jié)構(gòu)：

varbarber,wait:semaphore;(初始值=0)

entry:semaphore; (初始值=1)

couter:integer; (初始值=0)//關(guān)于理發(fā)師的代碼段：

whiletruedo{

P(barber);

“Shave”

}簡單理發(fā)店問題//關(guān)于顧客的代碼段：

P(entry);

ifcount=nthen

{V(entry);exit;

} count:=count+1;

ifcount>1then

{V(entry);

P(wait);}簡單理發(fā)店問題elseV(entry);V(barber);

“Shave”

P(entry);

count:=count–1;

ifcount>0thenV(wait);

V(entry);理發(fā)室椅子入口出口等候室簡單理發(fā)店問題barber信號量隊列wait信號量隊列entry信號量隊列理發(fā)師理發(fā)師P（barber）P（entry）P（entry）count=0=1v（entry）喚醒count=1v（entry）Count=2P（wait）V（barber）QQ王國的簡單理發(fā)店問題理發(fā)師barber信號量隊列wait信號量隊列entry信號量隊列P（entry）count=5QQ王國的簡單理發(fā)店問題V（entry）P（entry）count=5count=4V（entry）V（wait）V（barber）P（barber）

解:

vara,b,c,d,e,f,g,h:semaphore(初值=0)

parbegin

beginS1;V(a);V(b);V(c);end;

beginP(a);S2;V(d);V(e);end;

beginP(b);S3;V(f);end;

beginP(c);P(d);S4;V(g);end;

beginP(e);P(f);S5;V(h);end;

beginP(g);P(h);S6;end;

parend例:考慮右圖所示的優(yōu)先圖，請用并發(fā)語句和信號量表達該優(yōu)先圖。習(xí)題S1S3S4S6S5S2abcdefhg桌上有一個空盤，允許存放一個水果。父親可向盤中放蘋果，也可向盤中放橘子，兒子專等吃盤中的橘子，女兒專等吃盤中的蘋果。規(guī)定當(dāng)盤空時一次放一個水果供吃者取用，請用P，V原語實現(xiàn)父親、兒子、女兒三個并發(fā)進程的同步。分析同步/互斥關(guān)系：父親和兒子之間——同步父親和女兒之間——同步習(xí)題設(shè)置信號量父親的私有信號量s，表示盤子是否可用，初值為1兒子的私有信號量orange，表示是否有橘子可吃，初值為0女兒的私有信號量apple，表示是否有蘋果可吃，初值為0習(xí)題father進程：L1：P(S)；將水果放入盤中；if(放入是橘子)

V(orange)；elseV(apple) ；

gotoL1；

習(xí)題daughter進程：L2：P(apple)；從盤中取出蘋果；V(S)；吃蘋果； gotoL2；

son進程：L3：P(orange)；從盤中取出橘子；V(S)；吃橘子； gotoL3；

更為高級的同步機構(gòu)中,最重要的是管程建立管程的基本理由：由于臨界區(qū)的執(zhí)行分散在各進程中，PV操作可能分布在各個程序中，很難看出在信號量上的操作所產(chǎn)生的整體效果；也很難發(fā)現(xiàn)和糾正分散在用戶程序中的對同步原語的錯誤使用等問題，也不便于系統(tǒng)對臨界資源的控制和管理開鎖、關(guān)鎖原語和信號量上的P、V操作，是低級的同步機構(gòu)，很難表示更為復(fù)雜的并發(fā)性問題把分散的各同類臨界區(qū)集中起來，并為每個可共享資源設(shè)立一個專門的管程來統(tǒng)一管理各進程對該資源的訪問，這樣既便于系統(tǒng)管理共享資源，又能保證互斥訪問管程什么是管程？臨界資源的管理者或封裝者，進程必須通過管程訪問臨界資源管程主要由兩部分組成：局部于該管程的共享數(shù)據(jù)，這些數(shù)據(jù)表示了相應(yīng)的資源局部于該管程的局部過程，由這些過程對臨界資源進行操作管程一次只允許一個進程進入其內(nèi)（即訪問管程內(nèi)的某個過程）——這是由編譯系統(tǒng)保證。管程對于cedure-name的調(diào)用都將保證如下操作：

semWait(mutex);

執(zhí)行相應(yīng)的過程或函數(shù)

semSignal（mutex）；

mutex是相對于某個管程的互斥信號量策略：當(dāng)一個進程進入管程后由于某個原因被阻塞，應(yīng)該立即釋放管程。對于阻塞原因設(shè)置條件變量，退出管程的進程到相應(yīng)條件變量的等待隊列上排隊管程用管程實現(xiàn)生產(chǎn)者和消費者問題：為生產(chǎn)者與消費者的共享緩沖區(qū)建立一個管程

monitorbuffer；

procedureentryput(item)；

beginifk=nthenfull.wait；

buffer（in）:=item；

k:=k＋1;in:=(in+1)modn;ifempty.queuethenempty.signal;end;管程procedureentryget(item)；

beginifk＝0thenempty.wait；

goods:=buffer（out）；

k:＝k-1;out:=(out+1)modn;iffull.queuethenfull.signal;end;p1p2p3p4pic2c3c4ci......生產(chǎn)者/消費者問題full.queueempty.queuec1p1p2p3p4pic2c3c4ci......生產(chǎn)者/消費者問題full.queueempty.queuec1p1p2p3p4pic2c3c4ci......生產(chǎn)者/消費者問題full.queueempty.queuec1初值：k＝0；in＝0；out＝0；用管程實現(xiàn)生產(chǎn)者和消費者問題：Producer：beginrepeatproduceanitem；buffer.put（item）；

untilfalse；end；管程Consumer：beginrepeatbuffer.get（item）；

consumetheitem；

untilfalse；

End；進程通訊：進程同步，互斥及信息交換統(tǒng)稱為進程通信低級通訊（簡單信號）高級通訊（交換大宗的信息）進程高級通訊進程通訊模式共享內(nèi)存模式消息傳遞模式進程psend發(fā)送區(qū)（消息）接收區(qū)（消息）進程qreceivehptrmutexsmPCBsptrnptrtextsptrnulltextaddpnulltextpaddpnulltextpnptr直接通信發(fā)送進程將消息連入接受方的消息隊列中；接收進程按先來先服務(wù)原則處理消息隊列中的消息。處理完一個消息之后，向發(fā)送進程回送一個“回答”信號為了能高效率地實現(xiàn)進程通信，操作系統(tǒng)設(shè)計了多種高級通信原語send(R,M)原語和receive(PID,N)原語直接通信send(R,M)(發(fā)送消息)原語send(R,M)原語用來發(fā)送消息，M是發(fā)送進程提供的發(fā)送信息send(R,M)原語先申請一個消息緩沖區(qū)，然后把發(fā)送區(qū)的內(nèi)容復(fù)制到消息緩沖區(qū)中。然后找到接收進程的PCB，把消息緩沖區(qū)連入接收進程的消息緩沖區(qū)隊列中代碼直接通信proceduresend（R,M）；

benginnew（p）；//創(chuàng)建一個空消息緩沖區(qū)將信息寫入消息緩沖區(qū)

尋找到接收者R的PCB;

semWait(mutex);

將消息加入R的消息隊列;

semSignal(sm);semSignal(mutex);

end；發(fā)送原語Send(R,M)receive(PID,N)(讀取消息)原語receive(PID,N)原語用來讀取消息，A是接收進程提供的接收區(qū)起始地址receive(PID,N)原語把消息緩沖區(qū)中的消息內(nèi)容、消息長度以及發(fā)送進程的名字讀取到接收區(qū)，然后把消息緩沖區(qū)從鏈表中去掉，并釋放消息緩沖區(qū)如果沒有消息可讀取，則阻塞接收進程，直至消息發(fā)送來為止直接通信procedurereceive（PID,N）

benginsemWait(Sm);semWait(mutex);