OS-04進(jìn)程同步與互斥

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

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

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

不可再現(xiàn)性

制約性

資源共享

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

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

{chin=getchar();

chout=do(chin);

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

voidecho()

{chin=getchar();

chout=do(chin);

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

voidecho()

{chin=getchar();

chout=do(chin);

putchar(chout);}

getchar（）chinchout

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

voidecho()

{chin=getchar();

chout=do(chin);

putchar(chout);}

P1

voidecho()

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

putchar(chout);}

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

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

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

臨界區(qū)

其余代碼Untilfalseentrysectionexitsection例：司機(jī)-售票員問題司機(jī)活動(dòng)：售票員活動(dòng)：

do{do{

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

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

X＝1表示資源可用

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

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

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

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

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

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

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

信號量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用信號量實(shí)現(xiàn)同步的例子：司機(jī)-售票員問題：司機(jī)活動(dòng)：售票員活動(dòng)：

Do{Do{

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

開車門

}While(1)

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

Do{Do{

P(S1)

關(guān)車門

啟動(dòng)車輛V(S1)

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

V(S2)開車門

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

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

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

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

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

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

semSignal(S);

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

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

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

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

whiletruedo{producenextproduct;

semWait(empty);

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

semSignal(full);

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

semWait(full);

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

semSignal(empty);

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

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

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

semWait操作退出：

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

讀者和寫者問題§4.2進(jìn)程的同步與互斥—信號量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，寫者會(huì)被餓死。策略：一旦有寫者等待，新到達(dá)讀者等待，等正在讀的讀者都結(jié)束后，寫者先進(jìn)入，即寫者優(yōu)先。實(shí)現(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ā)店問題一個(gè)理發(fā)店由一個(gè)有幾張椅子的等候室、一個(gè)放有一張理發(fā)椅的理發(fā)室和一個(gè)理發(fā)師組成。若沒有要理發(fā)的顧客，則理發(fā)師就去睡覺；若一顧客走進(jìn)理發(fā)店且所有的椅子都被占用了，則該顧客就離開理發(fā)店；若理發(fā)師正在為人理發(fā)，則該顧客就找一張空椅子坐下等待;若理發(fā)師在睡覺，則顧客就喚醒他。簡單理發(fā)店問題分析只有當(dāng)顧客坐上理發(fā)椅，理發(fā)師才開始理發(fā)—同步當(dāng)正在理發(fā)的顧客理好發(fā)，等待的顧客才能理發(fā)—同步同一時(shí)刻只有一個(gè)顧客能理發(fā)——互斥同一時(shí)刻只有有限的顧客能在等待室等待——互斥資源與信號量對于理發(fā)師：坐上理發(fā)椅的顧客，信號量barber＝0對于理完發(fā)的顧客：是否有顧客等待，信號量wait＝0對于進(jìn)入的顧客：是否有人在理發(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信號量隊(duì)列wait信號量隊(duì)列entry信號量隊(duì)列理發(fā)師理發(fā)師P（barber）P（entry）P（entry）count=0=1v（entry）喚醒count=1v（entry）Count=2P（wait）V（barber）QQ王國的簡單理發(fā)店問題理發(fā)師barber信號量隊(duì)列wait信號量隊(duì)列entry信號量隊(duì)列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ā)語句和信號量表達(dá)該優(yōu)先圖。習(xí)題S1S3S4S6S5S2abcdefhg桌上有一個(gè)空盤，允許存放一個(gè)水果。父親可向盤中放蘋果，也可向盤中放橘子，兒子專等吃盤中的橘子，女兒專等吃盤中的蘋果。規(guī)定當(dāng)盤空時(shí)一次放一個(gè)水果供吃者取用，請用P，V原語實(shí)現(xiàn)父親、兒子、女兒三個(gè)并發(fā)進(jìn)程的同步。分析同步/互斥關(guān)系：父親和兒子之間——同步父親和女兒之間——同步習(xí)題設(shè)置信號量父親的私有信號量s，表示盤子是否可用，初值為1兒子的私有信號量orange，表示是否有橘子可吃，初值為0女兒的私有信號量apple，表示是否有蘋果可吃，初值為0習(xí)題father進(jìn)程：L1：P(S)；將水果放入盤中；if(放入是橘子)

V(orange)；elseV(apple) ；

gotoL1；

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

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

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

semWait(mutex);

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

semSignal（mutex）；

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

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)者/消費(fèi)者問題full.queueempty.queuec1p1p2p3p4pic2c3c4ci......生產(chǎn)者/消費(fèi)者問題full.queueempty.queuec1p1p2p3p4pic2c3c4ci......生產(chǎn)者/消費(fèi)者問題full.queueempty.queuec1初值：k＝0；in＝0；out＝0；用管程實(shí)現(xiàn)生產(chǎn)者和消費(fèi)者問題：Producer：beginrepeatproduceanitem；buffer.put（item）；

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

consumetheitem；

untilfalse；

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

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

尋找到接收者R的PCB;

semWait(mutex);

將消息加入R的消息隊(duì)列;

semSignal(sm);semSignal(mutex);

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

benginsemWait(Sm);semWait(mutex);