TheCityCollegeOfJiLinArchitecturalAndCivilEngineeringInstituteDepartmentofComputerScience&Technology操作系統(tǒng)原理PrinciplesofOperatingSystem1第四章并發(fā)控制目的與要求：了解并行程序的高級(jí)語(yǔ)言表示與操作系統(tǒng)支持下的實(shí)現(xiàn)；了解同步與互斥問(wèn)題。理解互斥問(wèn)題的硬件實(shí)現(xiàn)方法；掌握信號(hào)量機(jī)制及使用它解決進(jìn)程同步互斥問(wèn)題的方法。掌握信號(hào)量解決進(jìn)程同步互斥問(wèn)題的方法；掌握進(jìn)程通信的基本實(shí)現(xiàn)方法。了解死鎖的定義，掌握死鎖預(yù)防，了解死鎖避免，死鎖檢測(cè)，死鎖恢復(fù)的方法。重點(diǎn)與難點(diǎn)：并行程序中的同步與互斥，信號(hào)量實(shí)現(xiàn)及使用。信號(hào)量的典型應(yīng)用，通訊實(shí)現(xiàn)。死鎖預(yù)防法則的使用，死鎖避免和檢測(cè)算法。作業(yè)：1，2，3，4，6，11，13，14，15，21，23，28，3124.1并發(fā)進(jìn)程4.1.1順序程序及其特性順序性內(nèi)部順序性：如：P1

:a=x+y;b=a-z;c=a+b;d=c+5;外部順序性：輸入，計(jì)算，打印特性連續(xù)性：一個(gè)程序的指令連續(xù)執(zhí)行封閉性：P獨(dú)占全部資料，不受外界影響可再現(xiàn)性：執(zhí)行結(jié)果只與初始條件有關(guān)3例：圖書(shū)借閱系統(tǒng)（x:某種書(shū)冊(cè)數(shù)，設(shè)當(dāng)前x:=1.）終端1：終端2：CYCLECYCLE等待借書(shū)者；等待借書(shū)者；IFx>=1ThenIFx>=1ThenBeginBeginx:=x-1;x:=x-1;借書(shū)借書(shū)EndEndElse無(wú)書(shū)Else無(wú)書(shū)EndEnd4.1.3與時(shí)間有關(guān)的錯(cuò)誤1234中斷中斷54.1.3與時(shí)間有關(guān)的錯(cuò)誤(Cont.)錯(cuò)誤原因之1：進(jìn)程執(zhí)行交叉(interleave);錯(cuò)誤原因之2：涉及公共變量(x)。Remarks:某些交叉結(jié)果不正確;必須去掉導(dǎo)致不正確結(jié)果的交叉。定義：并發(fā)進(jìn)程的執(zhí)行實(shí)際上是進(jìn)程活動(dòng)的某種交叉，某些交叉次序可能得到錯(cuò)誤結(jié)果。由于具體交叉的形成與進(jìn)程的推進(jìn)速度有關(guān)，而速度是時(shí)間的函數(shù)，因而將這種錯(cuò)誤稱(chēng)為與時(shí)間有關(guān)的錯(cuò)誤。64.2同步與互斥4.2.1進(jìn)程互斥互斥關(guān)系（亦稱(chēng)間接制約關(guān)系）即進(jìn)程間因相互競(jìng)爭(zhēng)使用獨(dú)占型資源（互斥資源）所產(chǎn)生的制約關(guān)系。例2：P1、P2兩進(jìn)程使用同一打印機(jī)。如果不互斥使用會(huì)交叉輸出Entrycodeexitcode使用打印機(jī)P1Entrycodeexitcode使用打印機(jī)P27……balance=balance+amountbalance=balance-amount……機(jī)器指令：A(amount)B(amount){R1=balance;{R1=balance;R2=amount;R2=amount;R1=R1+R2;R1=R1-R2;balance=R1;balance=R1;};};例3:進(jìn)程P1處理存款業(yè)務(wù)，進(jìn)程P2處理借貸業(yè)務(wù)。它們?nèi)绾卧L問(wèn)共享變量balance？互斥執(zhí)行中斷進(jìn)程互斥的硬件實(shí)現(xiàn)1.硬件提供“測(cè)試并建立”(“讀后置“1””)指令booleantest_and_set(boolean&target){booleanrv=target;/*讀取參數(shù)傳過(guò)來(lái)的地址中的值*/target=true;/*將參數(shù)值置“1”*/return(rv);}實(shí)現(xiàn)互斥的使用方法：1）對(duì)一組公共變量,設(shè)置一變量：booleanlock=false;

/*表示無(wú)進(jìn)程在臨界區(qū)*/2）Pi進(jìn)入:While(test_and_set(&lock));

/*lock=true*/

臨界區(qū)3）Pi離開(kāi)：lock=false;10booleanlock=false;Pi進(jìn)入:While(test_and_set(&lock));

/*lock=true*/

臨界區(qū)Pi離開(kāi)：lock=false;Pj進(jìn)入:While(test_and_set(&lock));

/*lock=true*/

臨界區(qū)Pj離開(kāi)：lock=false;Lock=falsePj的時(shí)間片到Lock=truePi忙式等待存在忙式等待現(xiàn)象：不進(jìn)入等待狀態(tài)的等待稱(chēng)為~。即空耗處理機(jī)資源。11為何開(kāi)關(guān)中斷進(jìn)程互斥方法僅在單CPU系統(tǒng)中是有效的？答：關(guān)中斷方法不適用于多CPU系統(tǒng)，因?yàn)殛P(guān)中斷只能保證CPU不由一個(gè)進(jìn)程切換到另外一個(gè)進(jìn)程，從而防止多個(gè)進(jìn)程并發(fā)地進(jìn)入公共臨界區(qū)域。但即使關(guān)中斷后，不同進(jìn)程仍可以在不同CPU上并行執(zhí)行關(guān)于同一組共享變量的臨界區(qū)代碼。13例：司機(jī)-售票員問(wèn)題P1：司機(jī)活動(dòng)：P2：售票員活動(dòng)：do{do{關(guān)車(chē)門(mén)啟動(dòng)車(chē)輛正常行駛售票到站停車(chē)開(kāi)車(chē)門(mén)}while(1)}while(1)12344.2.2進(jìn)程同步14同步關(guān)系（亦稱(chēng)直接制約關(guān)系）指完成同一任務(wù)的伙伴進(jìn)程間，因需要在某些位置上協(xié)調(diào)它們的工作而等待、傳遞信息所產(chǎn)生的制約關(guān)系。4.2.2進(jìn)程同步15信號(hào)量機(jī)構(gòu)的組成：“信號(hào)量”、“P、V操作”。信號(hào)量S：一整型變量，只能被兩個(gè)原語(yǔ)訪問(wèn)。P操作(原語(yǔ))：P(S){While（S≤0） ；空操作S=S-1；}V操作(原語(yǔ))：V(S){S=S＋1；}P、V操作是兩條原語(yǔ)，即保證P、V操作對(duì)變量S的訪問(wèn)是互斥操作。4.2.3信號(hào)量申請(qǐng)資源釋放資源17一.原語(yǔ)概念與實(shí)現(xiàn)原語(yǔ)定義：指完成某種功能且不被分割或不被中斷執(zhí)行的操作序列。原語(yǔ)可通過(guò)硬件實(shí)現(xiàn)不可中斷性；或通過(guò)實(shí)現(xiàn)臨界段的元方法達(dá)到不被中斷。實(shí)現(xiàn)臨界段的元方法:屏蔽中斷(只用于單機(jī))利用“test-and-set”指令18下面我們用屏蔽中斷方法實(shí)現(xiàn)P（s）和V（s）的原子性。 P（s）V（s）{{

disableInterrupt();

disableInterrupt(); while（s≤0）{

enableInterrupt();

disableInterrupt();

}； s=s-1；s=s+1；

enableInterrupt();enableInterrupt(); }}循環(huán)忙等時(shí)可響應(yīng)中斷19解決互斥問(wèn)題：有n個(gè)進(jìn)程均要訪問(wèn)的臨界段。設(shè)n進(jìn)程共享一個(gè)信號(hào)量mutex,初值為1，semaphoremutex;任一進(jìn)程Pi的結(jié)構(gòu)為：P(mutex)V(mutex)臨界段非臨界段do{}while（1）進(jìn)入臨界段前執(zhí)行P操作；離開(kāi)臨界段后執(zhí)行V操作；關(guān)于同一個(gè)信號(hào)量的P、V操作處理同一個(gè)進(jìn)程中！21semaphoremutex=1;Pi進(jìn)入:P(mutex){While(mutex≤0)；

mutex=mutex-1；}

臨界區(qū)Pi離開(kāi):V(mutex){mutex=mutex+1;}Pj進(jìn)入:P(mutex){While(mutex≤0);

mutex=mutex-1；}

臨界區(qū)Pj離開(kāi)：V(mutex);mutex=1mutex=022解決同步問(wèn)題：例1：有P1、P2兩進(jìn)程，必須在P1執(zhí)行完S1語(yǔ)句后，P2才能執(zhí)行S2。設(shè)同步的兩進(jìn)程共享信號(hào)量synch，初值為0。semaphoresynch=0;S1S2P1：P2：P2():{P1():{……S1;V(synch);……};……P(synch);S2;……};申請(qǐng)資源執(zhí)行P；釋放資源執(zhí)行V；P、V在不同進(jìn)程中！23例2：兩個(gè)進(jìn)程P1和P2，其中，進(jìn)程P1依次運(yùn)行S1，S2，S4，S5，S7子任務(wù)，進(jìn)程P2依次運(yùn)行S3，S6子任務(wù)。Semaphores13,s46,s67;s13=0;s46=0;s67=0;S1S2S3S4S5S6S7P1:……S1;V(s13);S2;S4;V(s46);S5;P(s67);S7;……P2:……P(s13);S3;P(s46);S6;V(s67);

……25三.信號(hào)量的具體實(shí)現(xiàn)及P、V操作的改進(jìn)改進(jìn)原因：硬件方法和原有的P、V操作存在“忙等”現(xiàn)象。26無(wú)忙等的信號(hào)量的P、V操作1、信號(hào)量定義（E.W.Dijkstra,1965.） typedefstruct{ intvalue；

structprocess*L;/*等待隊(duì)列*/}semaphore；S.valueS.LsemaphoreS;29無(wú)忙等的信號(hào)量的P、V操作2、P操作voidP(Semaphores){S.Value=S.value–1;if(S.value<0){保存現(xiàn)場(chǎng)，將執(zhí)行該P(yáng)操作的進(jìn)程掛入S.L隊(duì)列；block();}}S.valueS.LPCB1PCB2PCBnFIFO若s.value=1，執(zhí)行P(S)的進(jìn)程p1是否等待？S.value=?若s.value=0，執(zhí)行P(S)的進(jìn)程p1是否等待？S.value=?0-1注意：當(dāng)s.value<0時(shí)，則s.L隊(duì)列中有等待狀態(tài)的進(jìn)程！30無(wú)忙等的信號(hào)量的P、V操作3、V操作voidV(Semaphores){S.value=S.value+1ifS.value≤0then{從S.L隊(duì)列取一進(jìn)程，掛入就緒隊(duì)列。wakeup();}}S.valueS.LPCBPCBPCBs.value=-1s.value=-2s.value=-ns.value=0若s.value=-1，執(zhí)行v(S)的進(jìn)程p是否進(jìn)行喚醒操作？S.value=?031信號(hào)量和P、V操作的規(guī)定P(S):表示申請(qǐng)一個(gè)資源V(S):表示釋放一個(gè)資源。信號(hào)量的初值必須且只能置一次初值，且應(yīng)該大于等于0P.V操作必須成對(duì)出現(xiàn)，有一個(gè)P操作就一定有一個(gè)V操作對(duì)信號(hào)量只能執(zhí)行P操作和V操作，所有其它操作非法。32規(guī)定和結(jié)論幾個(gè)有用的結(jié)論：當(dāng)s.value>=0時(shí)，有s.values個(gè)資源可用，且s.L隊(duì)列為空；當(dāng)s.value<0時(shí)，|s.value|為隊(duì)列s.L的長(zhǎng)度(即隊(duì)列中等待狀態(tài)的進(jìn)程的個(gè)數(shù))；當(dāng)s->value初=1時(shí)，可以實(shí)現(xiàn)進(jìn)程互斥；當(dāng)s->value初=0時(shí)，可以實(shí)現(xiàn)進(jìn)程同步；當(dāng)s->value初=正整數(shù)時(shí)，表示系統(tǒng)中資源的個(gè)數(shù)，可用來(lái)管理同種類(lèi)組合資源。334.2.4進(jìn)程同步與互斥舉例互斥舉例：進(jìn)入臨界段前執(zhí)行P操作；離開(kāi)臨界段后執(zhí)行V操作；關(guān)于同一個(gè)信號(hào)量的P、V操作處理同一個(gè)進(jìn)程中！34例2：P1、P2兩進(jìn)程使用同一打印機(jī)。設(shè)一個(gè)信號(hào)量：semaphores;s.value=1;Entrycodeexitcode使用打印機(jī)P1Entrycodeexitcode使用打印機(jī)P2P(s)P(s)V(s)V(s)互斥舉例35Pj進(jìn)入:P(s){S.value=S.value-1；if(s.value<0){入等待隊(duì)列；block();}

臨界區(qū)Pi離開(kāi)：V(S){S.value=S.value+1;if(s.value<=0){出等待隊(duì)列；wakeup(Pj);}semaphores.value=1;Pi進(jìn)入:P(s){S.value=S.value-1；if(s.value<0){入等待隊(duì)列；block();}

臨界區(qū)Pi離開(kāi)：V(S){S.value=S.value+1;if(s.value<=0){

出等待隊(duì)列；wakeup(Pj);}S.value=1S.value=0S.value=-1S.valueS.LnullPCBjnull36

balance=balance+amountbalance=balance-amountA(amount)B(amount){R1=balance;{R1=balance;R2=amount;R2=amount;R1=R1+R2;R1=R1-R2;balance=R1;balance=R1;};};例3:進(jìn)程P1處理存款業(yè)務(wù)，進(jìn)程P2處理借貸業(yè)務(wù)。它們?nèi)绾卧L問(wèn)共享變量balance？互斥執(zhí)行P(mutex)P(mutex)V(mutex)V(mutex)semaphoremutex.value=1;37互斥例子：借書(shū)系統(tǒng)(revisited)semaphoremutex;mutex.value=1;終端1：終端2：while(1){while(1){等待借書(shū)者；等待借書(shū)者；

P(mutex);P(mutex);if(x>=1)if(x>=1){{x=x-1;x=x-1;V(mutex);V(mutex);

借書(shū)借書(shū)}}elseV(mutex);無(wú)書(shū);elseV(mutex);無(wú)書(shū);}}38同步舉例：司機(jī)-售票員問(wèn)題申請(qǐng)資源執(zhí)行P；釋放資源執(zhí)行V；P、V在不同進(jìn)程中！39用信號(hào)燈實(shí)現(xiàn)進(jìn)程同步例子：司機(jī)-售票員問(wèn)題：semaphores1.value=0,s2.value=0;司機(jī)活動(dòng)：售票員活動(dòng)：while(1)while(1){P(S1){關(guān)車(chē)門(mén)啟動(dòng)車(chē)輛V(S1)正常行駛售票到站停車(chē)P(S2)

V(S2)開(kāi)車(chē)門(mén)}}是否關(guān)門(mén)了是否停車(chē)了40Classicalsynchronizationproblems1.Producersandconsumersproblem2.Readersandwritersproblem3.Diningphilosophersproblem4.Cigarettesmokersproblem5.Sleepybarbersproblemetc.41例1.生產(chǎn)者/消費(fèi)者問(wèn)題1箱子，容量1intb;1個(gè)生產(chǎn)者1個(gè)消費(fèi)者生產(chǎn)物品放入b中b中取物品消費(fèi)之42問(wèn)題分析生產(chǎn)者活動(dòng)：消費(fèi)者活動(dòng)：do{do{

加工一件物品箱中取一物品物品放入箱中消耗這件物品}while(1)}while(1)資源：箱子(同種組合)

資源：物品(同種組合)semaphoreempty;semaphorefull;

empty.value=1;full.value=0;放前：P（empty）取前：P（full）放后：V（full）取后：V（empty）43同步生產(chǎn)者活動(dòng)：消費(fèi)者活動(dòng)：do{do{

加工一件物品P(full)

P(empty)

箱中取一物品物品放入箱中V(empty)

V(full)

消耗這件物品}while(1)}while(1)44例1.生產(chǎn)者/消費(fèi)者問(wèn)題01……k-1箱子，容量kintb[k]m個(gè)生產(chǎn)者n個(gè)消費(fèi)者生產(chǎn)物品放入b中b中取物品消費(fèi)之45互斥生產(chǎn)者活動(dòng)：消費(fèi)者活動(dòng)：do{do{

加工一件物品P(full)

P(empty)

P(mutex)

P(mutex)

箱中取一物品物品放入箱中V(mutex)

V(mutex)

V(empty)

V(full)

消耗這件物品}while(1)}while(1)46semaphoreempty.value=k,full.value=0,mutex.value=1;voidproducer(){while(1){加工一個(gè)產(chǎn)品

P(empty);

P(mutex);

獲得一個(gè)緩沖區(qū);產(chǎn)品放入緩沖區(qū);

V(mutex);

V(full);}}voidconsumer(){while(1){P(full);

P(mutex);

獲得一個(gè)滿緩沖區(qū);取緩沖區(qū)中的產(chǎn)品;

V(mutex);V(empty);}}P(mutex);

P(empty);

47voidproducer(){while(1){加工一個(gè)產(chǎn)品

P(empty);

P(mutex);

獲得一個(gè)緩沖區(qū);產(chǎn)品放入緩沖區(qū);

V(mutex);

V(full);}}voidconsumer(){while(1){P(full);

P(mutex);

獲得一個(gè)滿緩沖區(qū);取緩沖區(qū)中的產(chǎn)品;

V(mutex);V(empty);}}P(mutex);

P(empty);

若，當(dāng)前緩沖區(qū)滿，則empty.value=0,full.value=k,mutex.value=1生產(chǎn)者：mutex.value=0,empty.value=-1消費(fèi)者：full.value=k-1,mutex.value=-1死鎖48注意注意：如果P(S1)和P(S2)兩個(gè)操作在一起，那么P操作的順序至關(guān)重要,一個(gè)同步P操作與一個(gè)互斥P操作在一起時(shí)同步P操作在互斥P操作前而兩個(gè)V操作無(wú)關(guān)緊要49并發(fā)性提高策略生產(chǎn)者和消費(fèi)者：關(guān)注不同的緩沖區(qū)生產(chǎn)者關(guān)注：空的緩沖區(qū)消費(fèi)者關(guān)注：滿的緩沖區(qū)semaphoremutex1,mutex2;mutex1.value=1;mutex2.value=1;？50互斥生產(chǎn)者活動(dòng)：消費(fèi)者活動(dòng)：do{do{

加工一件物品P(full)

P(empty)

P(mutex2)

P(mutex1)

箱中取一物品物品放入箱中V(mutex2)

V(mutex1)

V(empty)

V(full)

消耗這件物品}while(1)}while(1)51例2.讀者/寫(xiě)者問(wèn)題P.T.Courtois1971CommunicationoftheACM,Vol.14,667-669.ACM:AssociationforComputingMachinery解法1：寫(xiě)者可能餓死解法2：寫(xiě)者優(yōu)先52例2.讀者/寫(xiě)者問(wèn)題ProblemStatement:一組公共數(shù)據(jù)DBR1……RmW1…...Wn要求：（1）R-R可以同時(shí)（2）R-W不可同時(shí)（3）W-W不可同時(shí)accessing53Solution1:不考慮R-R不互斥semaphorer_w_w.value=1;Reader：Writer:

P(r_w_w);P(r_w_w)

{讀操作}{寫(xiě)操作}V(r_w_w);V(r_w_w)分析：(1)寫(xiě)者活動(dòng)正確；(2)R-R不能同時(shí)。改進(jìn)：最先進(jìn)入的R執(zhí)行P；最后離開(kāi)的R執(zhí)行V；54Solution2:考慮R-R不互斥intreadercount=0;Reader:readercount=readercount+1;if(readercount==1)P(r_w_w);{讀操作}readercount=readercount-1;if(readercount==0)V(r_w_w);問(wèn)題：對(duì)Readercount操作的互斥問(wèn)題。55Solution3:正確解法semaphorereadercount_mutex.value=1;

Reader:

P(readercount_mutex);readercount=readercount+1;if(readercount==1)P(r_w_w);

V(readercount_mutex);{讀操作}

P(readercount_mutex);readercount=readercount-1;if(readercount==0)V(r_w_w);

V(readercount_mutex);讀者等待在何處？讀者如何被喚醒？56程序intreadercount=0;semaphorer_w_w.value=1;semaphorereadercount_mutex.value=1;writer(){while(1){……

P(r_w_w);<寫(xiě)操作>

V(r_w_w)}}57程序（Cont.）reader(){while(1){……

P(readercount_mutex);readercount=readercount+1;if(readercount==1)P(r_w_w);

V(readercount_mutex);

<讀操作>

P(readercount_mutex);readercount=readercount-1;if(readercount==0)V(r_w_w);

V(readercount_mutex);}}58分析（w1,w2,r1,w3,r2,r3）①初始狀態(tài)readercount_mutex

1NULLreadercount=0r_w_w1NULL訪問(wèn)文件者：無(wú)圖4-1②w1請(qǐng)求readercount_mutex1NULLreadercount=0r_w_w0NULL訪問(wèn)文件者：w1圖4-259請(qǐng)求序列：w1,w2,r1,w3,r2,r3③w2請(qǐng)求readercount_mutex1NULLreadercount=0r_w_w-1w2訪問(wèn)文件者：w1圖4-3④r1請(qǐng)求readercount_mutex0NULLreadercount=1r_w_w-2w2,r1訪問(wèn)文件者：w1圖4-460⑤w3請(qǐng)求readercount_mutex0NULLreadercount=1r_w_w-3w2,r1,w3訪問(wèn)文件者：w1圖4-5⑥r(nóng)2請(qǐng)求readercount_mutex-1r2readercount=1r_w_w-3w2,r1,w3訪問(wèn)文件者：w1圖4-6請(qǐng)求序列：w1,w2,r1,w3,r2,r361⑦r3請(qǐng)求readercount_mutex-2r2,r3readercount=1r_w_w-3w2,r1,w3訪問(wèn)文件者：w1圖4-7⑧w1結(jié)束，喚醒w2readercount_mutex-2r2,r3readercount=1r_w_w-2r1,w3訪問(wèn)文件者：w2圖4-8請(qǐng)求序列：w1,w2,r1,w3,r2,r362readercount_mutex-1r3readercount=1r_w_w-1w3訪問(wèn)文件者：r1圖4-9readercount_mutex0NULL

readercount=2r_w_w-1w3訪問(wèn)文件者：r1,r2圖4-10⑨w2結(jié)束喚醒r1,r1喚醒r2,r2入就緒隊(duì)列⑩r2運(yùn)行,r2喚醒r3,r3入就緒隊(duì)列請(qǐng)求序列：w1,w2,r1,w3,r2,r363⑩r3運(yùn)行readercount_mutex1NULL

readercount=3r_w_w-1w3訪問(wèn)文件者：r1,r2,r3圖4-11⑩r1,r2,r3結(jié)束,喚醒w3readercount_mutex1NULL

readercount=0r_w_w0NULL

訪問(wèn)文件者：w3圖4-12請(qǐng)求序列：w1,w2,r1,w3,r2,r364⑩w3結(jié)束readercount_mutex1NULL

readercount=0r_w_w1NULL

訪問(wèn)文件者：無(wú)圖4-13請(qǐng)求序列：w1,w2,r1,w3,r2,r365分析：?jiǎn)栴}：讀者源源不斷，readcount不歸0，寫(xiě)者會(huì)被餓死。初始:w1,w2,r1,w3,r2,r3實(shí)際:w1,w2,r1,r2,r3,w3策略：一旦有寫(xiě)者等待，新到達(dá)讀者等待，正在讀的讀者都結(jié)束后，寫(xiě)者進(jìn)入。Furtherimprovementislefttointerestedstudents.66寫(xiě)者優(yōu)先算法semaphorer_w_w.value=1;semaphorereader_wait.value=1;semaphorefirst_reader_wait.value=1;semaphorereadercount_mutex.value=1;semaphorewritercount_mutex.value=1;intwritercount=0;intreadercount=0;67reader(){

P(reader_wait);P(first_reader_wait);

P(readercount_mutex);readercount++;if(readercount==1)P(r_w_w);

V(readercount_mutex);

V(reader_wait);

V(first_reader_wait);讀文件;68

P(readercount_mutex);readercount--;if(readercount==0)V(r_w_w);

V(readercount_mutex);}69writer(){

P(writercount_mutex);

writercount++;if(writercount==1)

P(first_reader_wait);

V(writercount_mutex);

P(r_w_w);寫(xiě)文件;70

V(r_w_w);

P(writercount_mutex);writercount--;if(writercount==0)

V(first_reader_wait);

V(writercount_mutex);}71無(wú)優(yōu)先算法semaphorer_w_w.value=1;semaphorewait.value=1;

semaphorereadercount_mutex.value=1;intreadercount=0;72reader(){

P(wait);P(readercount_mutex);if(readercount==0)

P(r_w_w);readercount++;

V(readercount_mutex);

V(wait);讀文件;73

P(readercount_mutex);readercount--;if(readercount==0)

V(r_w_w);

V(readercount_mutex);}74writer(){

P(wait);

P(r_w_w);寫(xiě)文件;

V(r_w_w);

V(wait);}75例3.哲學(xué)家就餐問(wèn)題DiningPhilosophersProblemProposedandsolvedbyE.W.Dijkstra,in196576例3.哲學(xué)家就餐問(wèn)題Roomph0ph4ph3ph2ph1f0f4f3f2f177例3.哲學(xué)家就餐問(wèn)題哲學(xué)家活動(dòng)：while(1){思考進(jìn)食}進(jìn)食：需要“筷子”筷子：不同種組合資源為每個(gè)筷子設(shè)置一個(gè)信號(hào)量fork[i],0<=i<=4哲學(xué)家活動(dòng)（包含資源活動(dòng)）while(1){思考取左筷取右筷進(jìn)食放左筷放右筷}78例3.哲學(xué)家就餐問(wèn)題Semaphorefork[i].value=1哲學(xué)家活動(dòng)（包含資源活動(dòng)）while(1){思考p(&fork[i]);取左筷，

p(&fork[(i+1)%5]);取右筷進(jìn)食放左筷，v(&fork[i]);放右筷v(&fork[(i+1)%5]);}死鎖情況：每位哲學(xué)家拿到左叉，等待右叉。79習(xí)題1.設(shè)有一個(gè)售票大廳，可容納200人購(gòu)票。如果廳內(nèi)不足200人，則允許進(jìn)入，超過(guò)則在廳外等候；售票員某時(shí)只能給一個(gè)購(gòu)票者服務(wù)，購(gòu)票者習(xí)完票后就離開(kāi)。試問(wèn)：購(gòu)票者之間是同步關(guān)系還是互斥關(guān)系？用P、V操作描述購(gòu)票者的工作過(guò)程。80答（1）購(gòu)票者間是互斥關(guān)系。（2）semaphoreempty.value=200;semaphoremutex.value=1;購(gòu)票者{p(empty);p(mutex);購(gòu)票；v(empty);v(mutex);}81例4理發(fā)師睡覺(jué)問(wèn)題理發(fā)師問(wèn)題的描述：

一個(gè)理發(fā)店接待室有n張椅子，工作室有1張椅子；

沒(méi)有顧客時(shí)，理發(fā)師睡覺(jué)；

第一個(gè)顧客來(lái)到時(shí)，必須將理發(fā)師喚醒；

顧客來(lái)時(shí)如果還有空座的話，他就坐在一個(gè)座位上等待；

如果顧客來(lái)時(shí)沒(méi)有空座位了，他就離開(kāi)，不理發(fā)了；

當(dāng)理發(fā)師處理完所有顧客，而又沒(méi)有新顧客來(lái)時(shí)，他又開(kāi)始睡覺(jué)。

82顧客的活動(dòng){如果沒(méi)有空椅子，離開(kāi)；否則，坐在椅子上等候；從椅子上起來(lái)；坐在理發(fā)椅上；}資源：理發(fā)師的活動(dòng){睡覺(jué)；理發(fā)；

}資源：有沒(méi)有等待的顧客；83Windows2000/XP互斥同步機(jī)制CRITICAL_SECTION類(lèi)型InitializeCriticalSection:初始化EnterCriticalSection:等待進(jìn)入TryEnterCriticalSection:非等待，失敗返回0LeaveCriticalSection:離開(kāi)DeleteCriticalSection:清除844.3進(jìn)程高級(jí)通訊進(jìn)程通訊：進(jìn)程之間的相互作用。低級(jí)通訊（簡(jiǎn)單信號(hào)）進(jìn)程互斥進(jìn)程同步高級(jí)通訊（大宗信息）高級(jí)通訊memorysharingvs.messagepassingdirectvs.indirectsymmetricvs.non-symmetricbufferingvs.non-buffering4.3.1進(jìn)程通訊概念85P14.3.2進(jìn)程通訊模式1.共享內(nèi)存模式(sharedmemory)：2.消息傳遞模式(messagepassing)：P2OS提供：（1）公共內(nèi)存（2）互斥同步機(jī)制P1P2Msendreceive直接：進(jìn)程-進(jìn)程間接：進(jìn)程-信箱-進(jìn)程原語(yǔ)系統(tǒng)調(diào)用命令864.3.3消息傳遞模式(messagepassing)對(duì)稱(chēng)形式(senderandreceivernameeachother)send(R,message)receive(S,message)…Send(R,M)...…Receive(S,N)...S:R:1.消息傳遞原語(yǔ)形式：一對(duì)一87非對(duì)稱(chēng)形式(onlysendernamesreceiver)send(R,message)receive(pid,message)…receive(pid,N)...…send(R,M1)...…send(R,M2)...C/SmodelR:S1:S2:多對(duì)一信息是如何傳送的？4.3.3消息傳遞模式(messagepassing)882.消息傳遞方法直接通信法基本思想：進(jìn)程在發(fā)送和接收消息時(shí)直接指明接收者或發(fā)送者進(jìn)程ID。缺點(diǎn)：必須指定接收進(jìn)程ID。（UNIX的信號(hào)機(jī)制類(lèi)似這種形式）分類(lèi)無(wú)緩沖途徑有緩沖途徑4.3.3消息傳遞模式(messagepassing)89間接通訊法（信箱命名法〕基本思想：設(shè)立一個(gè)通信參與者共享的邏輯實(shí)體，如信箱。系統(tǒng)為每個(gè)信箱設(shè)一個(gè)消息隊(duì)列，發(fā)送者只向信箱發(fā)消息，接收者只從信箱取消息。4.3.3消息傳遞模式(messagepassing)MailboxSend(mb,m)Receive(mb,n)...90有緩沖途徑消息傳遞過(guò)程PCB…send(R,M)…sizetext...PCB…receive(pid,N)…

...M:發(fā)送區(qū)N:msgmsg...發(fā)送者S:接收者R:bufbufbuf...bufbuf...bufmsgmsgmsgbufbufmsg91Send(R,M)

根據(jù)R找接收者；

P(Sb);//是否有空buf

P(b_mutex);//互斥用buf

取一空buf;

V(b_mutex);text,size,sender=>buf

P(m_mutex);//互斥用消息鏈

消息入鏈尾；

V(m_mutex);

V(Sm);

//消息數(shù)量加1

發(fā)送-接收原語(yǔ)PCB…send(R,M)…sizetext...M:發(fā)送區(qū)發(fā)送者S:bufbufbuf...PCB…receive(pid,N)…

...N:msgmsgmsg...接收者R:semaphoreSb.value=k，b_mutex.value=1,

Sm.value=0,m_mutex.value=1;92發(fā)送-接收原語(yǔ)PCB…send(R,M)…sizetext...M:發(fā)送區(qū)發(fā)送者S:bufbufbuf...PCB…receive(pid,N)…

...N:msgmsgmsg...接收者R:Receive(pid,N)P(Sm);//是否有消息

P(m_mutex);//互斥用消息鏈

頭消息出鏈;

V(m_mutex);text,size=>Nsender=>pid

P(b_mutex);//互斥用buf

空buf入鏈；

V(b_mutex);V(Sb);//空buf數(shù)量加1semaphoreSb.value=k，b_mutex.value=1,

Sm.value=0,m_mutex.value=1;93Send(R,M)根據(jù)R找接收者；

P(Sb);P(b_mutex);取一空buf;

V(b_mutex);text,size,sender=>buf

P(m_mutex);

消息入鏈尾；

V(m_mutex);

V(Sm);

Receive(pid,N)

P(Sm);

P(m_mutex);頭消息出鏈;

V(m_mutex);text,size=>Nsender=>pid

P(b_mutex);

空buf入鏈；

V(b_mutex);V(Sb);semaphoreSb.value=k，b_mutex.value=1,

Sm.value=0,m_mutex.value=1;申請(qǐng)緩沖區(qū)釋放緩沖區(qū)入消息隊(duì)列從消息隊(duì)列取消息94Remarks：Send/receive為高級(jí)通訊原語(yǔ)，可用低級(jí)原語(yǔ)實(shí)現(xiàn)；Send/receive不是真正意義的原語(yǔ)，可以被中斷。954.4死鎖

4.4.1死鎖示例日常生活中的例子進(jìn)程死鎖的例子競(jìng)爭(zhēng)外部設(shè)備競(jìng)爭(zhēng)輔存空間編程錯(cuò)的例子964.4.2死鎖定義定義：一組進(jìn)程中的每一個(gè)進(jìn)程，均無(wú)限期地等待此組進(jìn)程中某個(gè)其他進(jìn)程占有的，因而永遠(yuǎn)無(wú)法得到的資源，這種現(xiàn)象稱(chēng)為進(jìn)程死鎖。定義死鎖時(shí)刻：無(wú)限等待發(fā)生時(shí)；等待發(fā)生前（已注定死鎖）。97由定義得到的結(jié)論幾個(gè)有用的結(jié)論：參與死瑣的進(jìn)程至少有二個(gè)；每個(gè)參與死鎖的進(jìn)程均等待資源；參與死鎖的進(jìn)程中至少有兩個(gè)進(jìn)程占有資源；死鎖進(jìn)程是系統(tǒng)中當(dāng)前進(jìn)程集合的一個(gè)子集。984.4.3死鎖類(lèi)型DBACW:直行E:左轉(zhuǎn)S:左轉(zhuǎn)1.競(jìng)爭(zhēng)資源引起的死鎖（1）不同種資源（2）同種資源4臺(tái)打印機(jī)，申請(qǐng):a,釋放aP1:aaaaaaaaP2:aaaa994.4.3死鎖類(lèi)型(Cont.)2.進(jìn)程通訊引起的死鎖P1：receive(P2,M1);P2:receive(P3,M2);P3:receive(P1,M3);其它原因引起的死鎖Afteryou/afteryou1004.4.4死鎖的條件Coffman條件（必要條件）資源獨(dú)占（mutualexclusion互斥）同一時(shí)刻，一個(gè)資源只能分配給一個(gè)進(jìn)程不可搶占（nonpreemption非剝奪）申請(qǐng)者不能強(qiáng)行搶奪別人的資源保持申請(qǐng)（holdandwait占有等待）P占有資源又申請(qǐng)資源循環(huán)等待（circularwait）第四個(gè)條件是前三個(gè)同時(shí)存在的結(jié)果。破壞上述任意一個(gè)條件可以消除死鎖。1014.4.5資源分配圖資源分配圖的定義定義:G=(V,E),V是點(diǎn)的集合

V=PR,P={p1,p2,…,pn},R={r1,r2,…,rm},E是邊的集合

E={(pi,rj)}{(rj,pi)},piP,rjR.

申請(qǐng)邊(pi,rj):pi申請(qǐng)rj；

分配邊(rj,pi):rj分配pi;102例子（無(wú)環(huán)路，無(wú)死鎖）例1.P={p1,p2,p3},R={r1(1),r2(2),r3(1),r4(3)}E={(p1,r1),(p2,r3),(r1,p2),(r2,p1),(r2,p2),(r3,p3),(r4,p3)}p1p2p3r1r3r2r4103例子（有環(huán)路，有死鎖）增加邊（p3,r2)p1p2p3r1r3r2r4104例子（有環(huán)路，無(wú)死鎖）r1r2p1p2p31054.4.5資源分配圖結(jié)論:無(wú)環(huán)路,一定無(wú)死鎖有環(huán)路,且每個(gè)資源類(lèi)中均只有唯一的一個(gè)資源實(shí)例,則死鎖有環(huán)路,且存一個(gè)所有資源類(lèi)所構(gòu)成集合子集,該子集中每一個(gè)資源類(lèi)均只有唯一的一個(gè)資源實(shí)例,則死鎖1064.4.5資源分配圖資源分配圖的約簡(jiǎn)步驟:（1）尋找非孤立且無(wú)請(qǐng)求邊的進(jìn)程節(jié)點(diǎn)Pi,若無(wú)結(jié)束;（2）去除所有Pi的分配邊使Pi成為一個(gè)孤立節(jié)點(diǎn)；（3）尋找所有請(qǐng)求邊均可滿足的進(jìn)程Pj,將Pj的請(qǐng)求邊全部改為分配邊；（4）轉(zhuǎn)（1）。判斷系統(tǒng)是否死鎖10資源分配圖的約簡(jiǎn)p1p2p3r1r3r2r4定理：S為死鎖狀態(tài)的充分必要條件是S的資源分配圖不可完全約簡(jiǎn)。10資源分配圖的約簡(jiǎn)p1p2p3r1r3r2r41094.4.6死鎖的處理不讓死鎖發(fā)生：死鎖預(yù)防（deadlockprevention）-靜態(tài)所有進(jìn)程都遵守某種資源使用協(xié)議死鎖避免（deadlockavoidance）--動(dòng)態(tài)實(shí)時(shí)檢測(cè)資源申請(qǐng)命令，拒絕不安全請(qǐng)求允許死鎖發(fā)生再處理：死鎖檢測(cè)（deadlockdetection）死鎖恢復(fù)（deadlockrecovery）1104.4.7死鎖預(yù)防主要思想：破壞死鎖的四個(gè)必要條件邏輯公式：D→C1∧C2∧C3∧C4

C1∨C2∨C3∨C4→D其中：D：死鎖Ci：死鎖的必要條件111破壞互斥占用條件 讓資源共享使用（但有些資源必須互斥）破壞占有等待條件將進(jìn)程所要資源一次性分給進(jìn)程，要么沒(méi)分到一個(gè)資源，要么全部滿足（適合廉價(jià)資源的分配,如外存空間分配）進(jìn)程在提出申請(qǐng)資源前，必須釋放所占的所有資源(用完一個(gè)再用下一個(gè))112破壞非剝奪條件(用于內(nèi)存管理、CPU管理等)當(dāng)進(jìn)程Pi申請(qǐng)ri類(lèi)資源時(shí)，若有則分配，若沒(méi)有則剝奪（釋放）Pi占有的所有資源；當(dāng)進(jìn)程Pi申請(qǐng)ri類(lèi)資源時(shí)，若有則分配，若無(wú)則剝奪（淘汰）占有ri類(lèi)資源進(jìn)程所占的ri類(lèi)資源分配給Pi；或看占用ri類(lèi)資源的Pk處于什么狀態(tài)，若處于等資源狀態(tài)，則剝奪其資源，否則讓Pi等待,等于剝奪Pi的資源。113破壞循環(huán)等待條件 采用資源順序分配方法：給每類(lèi)資源編號(hào)，進(jìn)程只能按序號(hào)由小到大的順序申請(qǐng)資源，若不滿足則拒絕分配。反證：若出現(xiàn)循環(huán)等待，則必會(huì)有小序號(hào)資源序號(hào)>大序號(hào)資源序號(hào)。114死鎖預(yù)防：對(duì)進(jìn)程有關(guān)資源的申請(qǐng)命令施加限制。死鎖避免：對(duì)進(jìn)程發(fā)出的每一個(gè)系統(tǒng)能夠滿足的資源申請(qǐng)命令實(shí)施動(dòng)態(tài)檢查。4.4.8死鎖避免(動(dòng)態(tài)的)檢測(cè)可滿足請(qǐng)求分配不分配安全不安全1154.4.8死鎖避免1.銀行家算法的提出依據(jù)：116例：設(shè)銀行家有10萬(wàn)貸款，P,Q,R分別需要8,3,9萬(wàn)元搞項(xiàng)目(假設(shè)任何人滿足資金總額后都會(huì)歸還所有貸款)。描述格式：P(已擁有的)：申請(qǐng)的第一種情況：存在安全的貸款序列：QPR102P(4):4Q(2):1R(2):71P(4):4Q(3)R(2):74P(4):4R(2):70P(8)R(2):7P:4Q:2R:28R(2):71R(9)10Q(2):1Q歸還P(4):4P歸還R(2):7R歸還返回117分析銀行家考慮：當(dāng)顧客申請(qǐng)資金時(shí)，能否給予滿足的關(guān)鍵是－－這次提供的資金會(huì)不會(huì)給今后其它貸款造成障礙。算法實(shí)質(zhì)：通過(guò)確保系統(tǒng)隨時(shí)處于安全狀態(tài)來(lái)避免死鎖。如：上例方法中，存在安全的貸款序列：QPR，所以系統(tǒng)處于安全狀態(tài)。118第二種情況:不存在安全的貸款序列，所以系統(tǒng)不安全。101P(4):4Q(2):1R(3):60P(4):4Q(3)R(3):63P(4):4R(3):6P:4Q:2R:3Q(2):1Q歸還死鎖1194.4.8死鎖避免(動(dòng)態(tài)的)定義：系統(tǒng)處于安全狀態(tài)：存在安全進(jìn)程序列<p1,p2,…,pn>設(shè)系統(tǒng)中有n個(gè)進(jìn)程，若存在一個(gè)序列〈P1，P2…Pn〉使得Pi(i＝1，2…n)以后還需要的資源可以通過(guò)系統(tǒng)現(xiàn)有資源加上所有Pj(j＜i)占有的資源來(lái)滿足，則稱(chēng)這個(gè)系統(tǒng)處于安全狀態(tài),序列<P1，P2…Pn〉稱(chēng)為安全序列。安全不安全死鎖2.安全狀態(tài)與安全進(jìn)程序列p1,p2,…,pn可依次進(jìn)行完。例1203.銀行家算法的提出Banker’salgorithm,E.W.Dijkstra.進(jìn)程：事先申明所需資源最大量（并不分配）系統(tǒng)：對(duì)每個(gè)可滿足的資源申請(qǐng)命令進(jìn)行安全性檢查。

P={p1,p2,…,pn};R={r1(k1),r2(k2),…,rm(km)};121銀行家算法(Cont.)數(shù)據(jù)結(jié)構(gòu)：intAvailable[m]//系統(tǒng)可用資源intClaim[n,m]//進(jìn)程最大需求intAllocation[n,m]//當(dāng)前分配intNeed[n,m]//尚需資源intRequest[n,m]//當(dāng)前請(qǐng)求臨時(shí)變量：intWork[m]//記錄可用資源intFinish[n]//進(jìn)程是否完成其中:Claim[n,m]=Allocation[n,m]+Need[n,m]122銀行家算法(Cont.)設(shè)X,Y為下標(biāo)1..l的一維數(shù)組：XYj(1jl),X[j]Y[j]X=Yj(1jl),X[j]:=Y[j]X=cj(1jl),X[j]:=cX±Yj(1jl),X[j]±Y[j]123算法1銀行家算法--資源分配算法Pi請(qǐng)求資源請(qǐng)求超量，錯(cuò)返Request[i]Available不滿足，等待Available=Available-Request[i]

Allocation[i]=Allocation[i]+Request[i]Need[i]=Need[i]-Request[i]安全確認(rèn)，pi繼續(xù)FTFTTFRequest[i]Need[i]Available=Available+Request[i]

Allocation[i]=Allocation[i]-Request[i]Need[i]=Need[i]+Request[i]pi等待124算法2銀行家算法--安全性檢測(cè)算法Work=Available;Finish=false;Finish[i]=true;Work=Work+Allocation[i]有滿足條件的i:Finish[i]=falseNeed[i]WorkTi,finish[i]=trueFTF安全不安全125銀行家算法例子例1R={A(10),B(5),C(7)}P={p0,p1,p2,p3,p4}Claim

Allocation

Need

Available

Work

FinishABCABCABCABCABC753010743332322200122902302600222211011433002431P0:p1:p2:p3:p4:問(wèn)：(1)系統(tǒng)是安全的嗎？

(2)若p1請(qǐng)求：Request[1]=(1,0,2)，可否滿足？332<532<743<745(1)運(yùn)行安全性檢測(cè)算法，令Work=Available=(3,3,2)Finish[1]=false，并且Need[1]=(1,2,2)<Work,則Work=Work+Allocation[1]=(3,3,2)+(2,0,0)=(5,3,2);Finish[1]=true；Finish[3]=false，并且Need[3]=(0,1,1)<Work,則Work=Work+Allocation[3]=(5,3,2)+(2,1,1)=(7,4,3);Finish[3]=true；

；Finish[4]=false，并且Need[4]=(4,3,1)<Work,則Work=Work+Allocation[4]=(7,4,3)+(0,0,2)=(7,4,5)；Finish[4]=true；Finish[2]=false，并且Need[2]=(6,0,0)<Work,則Work=Work+Allocation[2]=(7,4,5)+(3,0,2)=(10,4,7)；Finish[2]=true；1047<Finish[0]=false,并且Need[0]=(7,4,3)<Work,則Work=Work+Allocation[0]=(10,4,7)+(0,1,0)=(10,5,7)；Finish[0]=true；126解：(1)運(yùn)行安全性檢測(cè)算法，令Work=Available=(3,3,2)Finish[1]=false并且Need[1]=(1,2,2)<Work,則Work=Work+Allocation[1]=(3,3,2)+(2,0,0)=(5,3,2);

Finish[1]=true；Finish[3]=false并且Need[3]=(0,1,1)<Work,則Work=Work+Allocation[3]=(5,3,2)+(2,1,1)=(7,4,3);

Finish[3]=true；127Finish[4]=false并且Need[4]=(4,3,1)<Work,則Work=Work+Allocation[4]=(7,4,3)+(0,0,2)=(7,4,5)；Finish[4]=true；Finish[2]=false并且Need[2]=(6,0,0)<Work,則Work=Work+Allocation[2]=(7,4,5)+(3,0,2)=(10,4,7)；

Finish[2]=true；Finish[0]=false并且Need[0]=(7,4,3)<Work,則Work=Work+Allocation[0]=(10,4,7)+(0,1,0)=(10,5,7)；

Finish[0]=true；128可以找到一個(gè)安全進(jìn)程序列<p1,p3,p4,p2,p0>，它使Finish[i]=true，對(duì)于所有0≤i≤4，因而可以斷言系統(tǒng)當(dāng)前處于安全狀態(tài)．129銀行家算法例子例1R={A(10),B(5),C(7)}P={p0,p1,p2,p3,p4}Claim

Allocation