操作系統(tǒng)概念ch6final

Chapter6:ProcessSynchronizationModule6:ProcessSynchronization

進程同步Background背景TheCritical-SectionProblem臨界區(qū)問題Peterson’sSolutionSynchronizationHardware硬件同步Semaphores信號量ClassicProblemsofSynchronization經(jīng)典同步問題Monitors管程SynchronizationExamples同步實例AtomicTransactions原子事務(wù)CooperatingProcesses

進程協(xié)作Independentprocesscannotaffectorbeaffectedbytheexecutionofanotherprocess獨立進程不能影響或被在系統(tǒng)內(nèi)執(zhí)行的其他進程所影響（在邏輯上無任何聯(lián)系的進程）Cooperatingprocesscanaffectorbeaffectedbytheexecutionofanotherprocess協(xié)作進程影響或被在系統(tǒng)內(nèi)執(zhí)行的其他進程所影響（多個并發(fā)進程在邏輯上有某種聯(lián)系）Advantagesofprocesscooperation進程協(xié)作的好處Informationsharing信息共享Computationspeed-up加快計算Modularity模塊化Convenience方便協(xié)同進程的相互作用直接作用：進程間的相互聯(lián)系是有意識安排的，進程各自的執(zhí)行結(jié)果互為對方的執(zhí)行條件。間接作用：進程間要通過某種中介發(fā)生聯(lián)系，是無意識安排的相互感知程度相互關(guān)系一個進程對其他進程的影響相互不感知（完全不了解其它進程的存在）競爭一個進程的操作對其它進程的結(jié)果無影響間接感知（雙方都與第三方交互，如共享資源）通過共享進行協(xié)作一個進程的結(jié)果依賴于從其它進程獲得的信息直接感知（雙方直接交互，如通信）通過通信進行協(xié)作一個進程的結(jié)果依賴于從其它進程獲得的信息ProcessSynchronization進程同步（直接作用）指系統(tǒng)中多個進程中發(fā)生的事件存在某種時序關(guān)系，需要相互合作，共同完成一項任務(wù)。具體的說，一個進程運行到某一點時要求另一伙伴進程為它提供消息，在未獲得消息之前，該進程處于等待狀態(tài)，獲得消息后被喚醒進入就緒態(tài)。Example司機P1While(true){啟動車輛；正常運行；到站停車；}售票員P2While(true){關(guān)門；售票；開門；}MutualExclusion進程互斥（間接作用）由于各進程要求共享資源，而有些資源需要互斥使用，因此各進程間競爭使用這些資源。（無序）Concurrentaccesstoshareddatamayresultindatainconsistency并發(fā)的訪問數(shù)據(jù)可能會導(dǎo)致數(shù)據(jù)的不一致性Maintainingdataconsistencyrequiresmechanismstoensuretheorderlyexecutionofcooperatingprocesses維持數(shù)據(jù)的一致性需要一個保證協(xié)作進程順序執(zhí)行的機制與時間有關(guān)的錯誤搶椅子游戲民航售票與時間有關(guān)的錯誤銀行存款OS的存儲管理與時間有關(guān)的錯誤哲學(xué)家就餐問題Background背景Supposethatwewantedtoprovideasolutiontotheconsumer-producerproblemthatfillsallthebuffers.Wecandosobyhavinganintegercountthatkeepstrackofthenumberoffullbuffers.Initially,countissetto0.Itisincrementedbytheproducerafteritproducesanewbufferandisdecrementedbytheconsumerafteritconsumesabuffer.Producerwhile(true){

/*produceanitemandputinnextProduced*/ while(count==BUFFER_SIZE) ;//donothing buffer[in]=nextProduced; in=(in+1)%BUFFER_SIZE; count++;}Consumer

while(true){ while(count==0) ;//donothing

nextConsumed=buffer[out]; out=(out+1)%BUFFER_SIZE; count--; /*consumetheiteminnextConsumed }RaceConditioncount++couldbeimplementedas

register1=count

register1=register1+1

count=register1count--couldbeimplementedas

register2=count

register2=register2-1

count=register2Considerthisexecutioninterleavingwith“count=5”initially:

S0:producerexecuteregister1=count{register1=5}

S1:producerexecuteregister1=register1+1{register1=6}

S2:consumerexecuteregister2=count{register2=5}

S3:consumerexecuteregister2=register2-1{register2=4}

S4:producerexecutecount=register1{count=6}

S5:consumerexecutecount=register2{count=4}競爭條件（racecondition）：多個進程并發(fā)訪問和操作同一數(shù)據(jù)且執(zhí)行結(jié)果與訪問發(fā)生的特定順序有關(guān)臨界資源criticalresource何謂臨界資源？兩個或兩個以上的進程不能同時使用的資源為臨界資源。臨界資源可能是一些獨占設(shè)備，如打印機、磁帶機等；也可能是一些共享變量、表格、鏈表、文件等。Critical-Section何謂臨界區(qū)Critical-Section？每個進程中訪問臨界資源的那段代碼稱為臨界區(qū)。在臨界區(qū)前面增加一段用于進行檢查的代碼，把這段代碼稱為進入?yún)^(qū)entrysection

；相應(yīng)地，在臨界區(qū)后面再加一段用于退出臨界區(qū)的代碼，稱為退出區(qū)exitsection

。進程中除去上述進入?yún)^(qū)和退出區(qū)，其它部分的代碼，稱為剩余區(qū)remaindersection

。這樣，可將一個訪問臨界資源的進程描述如下：repeat

entrysection

criticalsection

exitsection

remaindersectionuntilfalse;SolutiontoCritical-SectionProblem1. MutualExclusion-IfprocessPiisexecutinginitscriticalsection,thennootherprocessescanbeexecutingintheircriticalsections互斥：一個進程在臨界區(qū)執(zhí)行，其他進程不得進入臨界區(qū)(無空等待)2. Progress-Ifnoprocessisexecutinginitscriticalsectionandthereexistsomeprocessesthatwishtoentertheircriticalsection,thentheselectionoftheprocessesthatwillenterthecriticalsectionnextcannotbepostponedindefinitely前進：有空讓進，多中選一3. BoundedWaiting-Aboundmustexistonthenumberoftimesthatotherprocessesareallowedtoentertheircriticalsectionsafteraprocesshasmadearequesttoenteritscriticalsectionandbeforethatrequestisgranted有限等待：從一個進程做出進入臨界區(qū)的請求，到該請求允許為止，其他進程允許進入臨界區(qū)的次數(shù)有上界AssumethateachprocessexecutesatanonzerospeedNoassumptionconcerningrelativespeedoftheNprocessesTheCritical-SectionProblem:Solution由競爭各方平等協(xié)商引入進程管理者，由管理者來協(xié)調(diào)競爭各方對互斥資源的使用具體方法：softwareapproaches（用編程解決，但常常忙等待）Hardwareapproaches（當(dāng)一個進程進入臨界區(qū)，就屏蔽所有中斷）Semaphores信號量Monitors管程softwareapproaches平等互斥基本思路是在進入?yún)^(qū)檢查和設(shè)置一些標志，如果已有進程在臨界區(qū)，則在進入?yún)^(qū)通過循環(huán)檢查進行等待；在退出區(qū)修改標志其中的主要問題是設(shè)置什么標志和如何檢查標志Peterson’sSolutionTwoprocesssolutionAssumethattheLOADandSTOREinstructionsareatomic;thatis,cannotbeinterrupted.Thetwoprocessessharetwovariables:intturn;Booleanflag[2]Thevariableturnindicateswhoseturnitistoenterthecriticalsection.Theflagarrayisusedtoindicateifaprocessisreadytoenterthecriticalsection.flag[i]=trueimpliesthatprocessPiisready!AlgorithmforProcessPi while(true){

flag[i]=TRUE;turn=j;while(flag[j]&&turn==j);CRITICALSECTION

flag[i]=FALSE;REMAINDERSECTION}

證明算法3滿足臨界區(qū)的要求1.互斥只有當(dāng)flag[j]=false，或turn==i時，Pi才能進入臨界區(qū)當(dāng)flag[0]==flag[1]==true時，P0,P1的循環(huán)條件肯定只能有一個被滿足2.前進條件滿足（空閑讓進）可以證明，只要P0不被允許進入，那么P1必定可以進入；反之依然3.有限等待條件滿足Pi最多等待Pj一次之后即可進入臨界區(qū)實現(xiàn)臨界區(qū)的方法1.兩進程解法(P0,P1)（1）讓兩個進程共享一個普通整數(shù)變量turn，其初值為0(或1)Ifturn==i,thenPi允許在CriticalSection內(nèi)執(zhí)行do{

while(turn!=i);

<臨界區(qū)>turn=j;

剩余區(qū)}while(1);進程Pi的結(jié)構(gòu)其中j=1-iTurn=0,并且p1就緒要進入臨界區(qū)盡管P0此時有可能處于剩余區(qū)，P1也必須等待（違背了空閑讓進的精神）（2）算法2：用數(shù)組booleanflag[2]來替代共享變量turn算法1的問題在于它沒有記住每個進程狀態(tài)的足夠信息在P0實際不處于臨界區(qū)執(zhí)行時，也有可能阻礙P1進入臨界區(qū)do{flag[i]=true;

while(flag[j]);

臨界區(qū)

flag[i]=false;

｝設(shè)置flag[i]為真，表示Pi準備進入臨界區(qū)檢查Pj是否也準備進入臨界區(qū)如果Pj準備進入，Pi等待如果Pj不準備進入，Pi進入臨界區(qū)表明Pi已經(jīng)退出臨界區(qū)進程Pi的結(jié)構(gòu)（其中j=1-i）算法（2）中存在問題要始終記得，P0、P1是并發(fā)執(zhí)行的兩個進程我們來看一下下面這個執(zhí)行順序T0:P0置flag[0]=trueT1:P1置flag[1]=true結(jié)果會怎樣？OK,大家都進不去了，也都無法再往下推進執(zhí)行即使互換設(shè)置flag[i]與檢查flag[j]的語句，問題也得不到解決do{flag[i]=true

while(flag[j]);

臨界區(qū)

flag[i]=false;

｝進程Pi的結(jié)構(gòu)（其中j=1-i）解決多線程同步的面包店算法該算法的基本思想源于顧客在面包店中購買面包時的排隊原理。顧客在進入面包店前,首先抓一個號,然后按照號碼由小到大的次序依次進入面包店購買面包.這里,面包店發(fā)放的號碼是由小到大的,但是兩個或兩個以上的顧客卻有可能得到相同的號碼(使所抓號碼不同需要互斥),如果多個顧客抓到相同的號碼,則規(guī)定按照顧客名字的字典次序進行排序,這里假定顧客是沒有重名的.在計算機系統(tǒng)中,顧客就相當(dāng)于進程,每個進程有一個唯一的標識,我們用P的下面加一個下標來表示.例如:對于Pi和Pj,如果有i<j,則先為Pi服務(wù),即Pi先進入臨界區(qū).解決多線程同步的面包店算法該算法的實現(xiàn)需要如下兩個數(shù)據(jù)結(jié)構(gòu):intchoosing[n]；intnumber[n]；前者表示進程是否正在抓號，正在抓號的進程choosing[i]為1，否則為0,其初值均為0.后者用來記錄各個進程所抓到的號碼,如number[i]為0,則進程Pi沒有抓號,如number[i]不為0,則其正整數(shù)值為進程Pi所抓到的號碼,其初值均為0.為了方便起見,我們定義下述表記法:●(a,b)<(c,d)如果a<cor(a=candb<d).●max(a0,…,an-1)其值為一正整數(shù)k,對于所有i,0≤i≤n-1,k≥ai.2.多進程算法（面包店算法）取號->等待叫號do{

choosing[i]=1;

number[i]=max(number[0],…,number[n-1])+1;

choosing[i]=0;

for(j=0;j<n;j++){

while(choosing[j]);//

wait

until

thread

j

receives

its

number

while((number[j]!=0)&&(number[j],j)<(number[i],i));

//

wait

until

threads

with

smaller

numbers

//

or

with

the

same

number,

but

with

higher

//

priority,

finish

their

work

}

臨界區(qū)

number[i]=0;

剩余區(qū)}while(1);當(dāng)number[i]<number[j],結(jié)果為true;當(dāng)number[j]==number[i]，且j<i，結(jié)果為true軟件方法1Free：臨界區(qū)標志，初始值為falsetrue有進程進入臨界區(qū)

false無進程進入臨界區(qū)

軟件方法2turn;trueP進入臨界區(qū)

falseQ進入臨界區(qū)

軟件方法2pturn，qturn

初值為falseP進入臨界區(qū)條件：pturn，notqturnQ進入臨界區(qū)條件：qturn，notpturn軟件方法3Dekker算法三個變量軟件方法的不足忙等待實現(xiàn)過于復(fù)雜，需要高的編程技巧SynchronizationHardware硬件同步Manysystemsprovidehardwaresupportforcriticalsectioncode很多系統(tǒng)對臨界區(qū)代碼提供硬件支持Uniprocessors–coulddisableinterrupts單處理器：關(guān)中斷Currentlyrunningcodewouldexecutewithoutpreemption非搶占Generallytooinefficientonmultiprocessorsystems在多處理器環(huán)境下效率太低OperatingsystemsusingthisnotbroadlyscalableModernmachinesprovidespecialatomichardwareinstructions現(xiàn)在操作系統(tǒng)提供了特殊的原子硬件指令A(yù)tomic=non-interruptableEithertestmemorywordandsetvalue測試與設(shè)置Orswapcontentsoftwomemorywords交換TestAndndSetInstructionDefinition:

boolean

TestAndSet(boolean*target){

boolean

rv=*target;*target=TRUE;returnrv:}SolutionusingTestAndSetSharedbooleanvariablelock.,initializedtofalse.Solution:

while(true){while(TestAndSet(&lock));/*donothing//criticalsectionlock=FALSE;//remaindersection}

SwapInstructionDefinition:

voidSwap(boolean*a,boolean*b){

booleantemp=*a;*a=*b;*b=temp:}SolutionusingSwapSharedBooleanvariablelockinitializedtoFALSE;EachprocesshasalocalBooleanvariablekey.Solution:

while(true){key=TRUE;while(key==TRUE)Swap(&lock,&key);

//criticalsectionlock=FALSE;//remaindersection}

Bounded-waitingmutualexclusionwithTestAndSetdo{

waiting[i]=true;key=true;while(waiting[i]&&key)key=TestAndSet(lock);

waiting[i]=false;

criticalsectionj=(i+1)%n;while((j!=i)&&!waiting[j])j=(j+1)%n;

if(j==i)lock=false;elsewaiting[j]=false;

remaindersection}while(1);SEMAPHORES(信號量)交通信號燈SemaphoreSynchronizationtoolthatdoesnotrequirebusywaiting不需要忙等待

SemaphoreS–integervariable信號量：整型變量TwostandardoperationsmodifyS:wait()andsignal()OriginallycalledP()and

V()Lesscomplicated

Canonlybeaccessedviatwoindivisible(atomic)operations只能通過兩個原子操作改變信號量的值wait(S){whileS<=0 ;//no-opS--;}signal(S){S++;}SemaphoreasGeneralSynchronizationToolCountingsemaphore–integervaluecanrangeoveranunrestricteddomain計數(shù)信號量：值不受限制Binarysemaphore–integervaluecanrangeonlybetween0

and1;canbesimplertoimplement二進制信號量：0和1Alsoknownasmutexlocks互斥鎖SemaphoreImplementationMustguaranteethatnotwoprocessescanexecutewait()andsignal()onthesamesemaphoreatthesametime需要保證不會有兩個進程同時對同一個信號量做wait()或signal()Thus,implementationbecomesthecriticalsectionproblemwherethewaitandsignalcodeareplacedinthecriticalsection.變成了一個臨界區(qū)問題，wait()或signal()在臨界區(qū)內(nèi)Couldnowhavebusywaitingincriticalsectionimplementation在臨界區(qū)內(nèi)忙等待是否可以Butimplementationcodeisshort

LittlebusywaitingifcriticalsectionrarelyoccupiedNotethatapplicationsmayspendlotsoftimeincriticalsectionsandthereforethisisnotagoodsolution.不應(yīng)該在應(yīng)用中花費太多時間在臨界區(qū)內(nèi)忙等待

SemaphoreImplementationwithnoBusywaiting

Witheachsemaphorethereisanassociatedwaitingqueue.為每個信號量設(shè)置一個等待隊列Structsemaphore{Intvalue;Structprocess*list;}Twooperations:block–placetheprocessinvokingtheoperationontheappropriatewaitingqueue.wakeup–removeoneofprocessesinthewaitingqueueandplaceitinthereadyqueue.

SemaphoreImplementationwithnoBusywaiting

(Cont.)Implementationofwait:

wait(S){

value--; if(value<0){ addthisprocesstowaitingqueue block();}}Implementationofsignal:

Signal(S){ value++; if(value<=0){ removeaprocessPfromthewaitingqueue

wakeup(P);}}信號量與P/V原語基本概念對于一種互斥或者同步關(guān)系，用一個整型變量來描述當(dāng)信號量大于0時，說明“環(huán)境安全”，可繼續(xù)運行當(dāng)信號量小于0時，說明“互斥等待”，只能阻塞推廣到一般情況，信號量可解決復(fù)雜的同步互斥問題原語：OS以關(guān)中斷形式實現(xiàn)的不可打斷操作SEMAPHORES(信號量)Asemaphoremustbeinitializedonce.必須置一次且只能置一次初值A(chǔ)semaphoremustbeinitializedviaanonnegativevalue.初值不能為負數(shù)Theintegervalueofasemaphorecanonlybemodifiedbywait/signal.只能執(zhí)行wait、signal操作MutualExclusionShareddata: semaphoremutex;//initiallymutex=1ProcessPi:

do{

wait(mutex);

criticalsection

signal(mutex);

remaindersection

}while(1);MutualExclusionExample1：Oneprinter，TwoprocessesAB

……PrintPrint……S=1

signal(S)signal(S)

wait(S)wait(S)Semaphores:AsaGeneralSynchronizationToolExample2：A+BProcess1：InputAProcess2：InputB；ExecuteA+BOnlyafterAisinputedinP1,executeA+BinP2P1fasterP2fasterP、V原語的使用使用P、V原語時，關(guān)注于資源/消息是否等待為其他進程著想SynchronizationP1P2InputA

InputB

signal(S)wait(S)A+BS=0疑惑信號量到底怎么用？初值怎么設(shè)？同步信號量：同步時使用，這些信號量只與制約進程和被制約進程有關(guān)而不是與整組并發(fā)進程有關(guān)。互斥信號量：互斥時使用。P、V操作討論信號量的物理意義：S>0表示有S個資源可用S=0表示無資源可用S<0，|S|表示S等待隊列中的進程個數(shù)wait(S)：申請一個資源signal(S)：釋放一個資源例：設(shè)系統(tǒng)中有兩臺打印機，4個進程都要使用，如何使用？CLASSICALPROBLEMSOFSYNCHRONIZATION----Producers-consumersproblem經(jīng)典的生產(chǎn)者、消費者問題同步問題P進程不能往“滿”的緩沖區(qū)中放產(chǎn)品，設(shè)置信號量為S1Q進程不能從“空”的緩沖區(qū)中取產(chǎn)品，設(shè)置信號量S2P:While(true){

生產(chǎn)一個產(chǎn)品；

wait(S1);

送產(chǎn)品到倉庫；

signal(S2);};Q:While(true){wait(S2);

從倉庫中取產(chǎn)品；

signal(S1);

消費產(chǎn)品；};S1初值為1，S2初值為0n個緩沖區(qū)、m個生產(chǎn)者和k個消費者Q:j=0;While(true){P(S2);

P(mutex);

從Buffer[j]取產(chǎn)品；

V(mutex);V(S1);

消費產(chǎn)品；

j=(j+1)%n;}P:i=0;While(true){

生產(chǎn)產(chǎn)品；

P(S1);

P(mutex);

往Buffer[i]放產(chǎn)品；

V(mutex);V(S2);i=(i+1)%n;}？n個緩沖區(qū)、m個生產(chǎn)者和k個消費者Q:While(true){P(S2);

P(mutex);

從Buffer[j]取產(chǎn)品；

j=(j+1)%n;

V(mutex);V(S1);

消費產(chǎn)品；}P:While(true){

生產(chǎn)產(chǎn)品；

P(S1);

P(mutex);

往Buffer[i]放產(chǎn)品；

i=(i+1)%n;

V(mutex);V(S2);}若顛倒兩個P操作的順序？i=0,j=0,S1=n,S2=0，mutex=1多緩沖區(qū)的生產(chǎn)者和消費者Q:j=0;While(true){P(S2);

從Buffer[j]取產(chǎn)品；

V(S1);

消費產(chǎn)品；

j=(j+1)%n;}P:i=0;While(true){

生產(chǎn)產(chǎn)品；

P(S1);

往Buffer[i]放產(chǎn)品；

V(S2);i=(i+1)%n;}無限緩沖區(qū)的生產(chǎn)者和消費者Q:j=0;While(true){P(S2);

從Buffer[j]取產(chǎn)品；消費產(chǎn)品；

j=j+1;}P:i=0;While(true){

生產(chǎn)產(chǎn)品；往Buffer[i]放產(chǎn)品；

V(S2);i=i+1;}示例1：讀者/寫者問題問題陳述：有多個讀進程和多個寫進程對一共享的數(shù)據(jù)庫進行讀寫一組公共數(shù)據(jù)DB

R1……RmW1…...Wnaccessing示例1：讀者/寫者問題進程關(guān)系分析讀操作可以同時進行（R-R）讀操作和寫操作不可以同時進行（R-W，互斥）寫操作和寫操作不可以同時進行（W-W，互斥）Writer：while(true){write();};Reader：

while(true){

read();

};基本問題的偽碼表示示例1：讀者/寫者問題Writer：while(true){

P(mutex);write();

V(mutex);};Reader：

while(true){

P(mutex);

read();

V(mutex);

};存在的問題：互斥條件使用過于嚴厲，讀者之間實際上并不存在互斥關(guān)系，但這里mutex的使用使得讀者之間產(chǎn)生了一種互斥的關(guān)系實現(xiàn)方法1：采用互斥鎖(int

mutex=1)示例1：讀者/寫者問題Writer：while(true){

P(mutex);write();

V(mutex);};Reader：while(true){

P(r_mutex);

r_cnt++;

if(r_cnt==1)P(mutex);

V(r_mutex);read();

P(r_mutex);

r_cnt--;

if(r_cnt==0)V(mutex);

V(r_mutex);};實現(xiàn)方法2：解決共享讀的問題示例1：讀者/寫者問題方案2中存在的問題：多個寫者緊接著過來！那么讀者餓死多個讀者過來，寫者會餓死通常有另一種稱為讀者寫者公平的實現(xiàn)方法示例1：讀者/寫者問題Writer：while(true){

P(rw_mutex);

P(mutex);write();

V(mutex);

V(rw_mutex);};Reader：while(true){

P(rw_mutex);

P(r_mutex);

r_cnt++;

if(r_cnt==1)P(mutex);

V(r_mutex);

V(rw_mutex);read();

P(r_mutex);

r_cnt--;

if(r_cnt==0)V(mutex);

V(r_mutex);};實現(xiàn)方法3：讀者寫者公平示例1：讀者/寫者問題示例2：車站購票問題例1：某車站售票廳，任何時刻最多可容納20名購票者進入，當(dāng)售票廳中少于20名購票者時，廳外的購票者可立即進入，否則需要在外面等待。每個購票者可看成一個進程。分析： 共享資源--售票廳中等待的空位資源容量--20(最多有20個空位)結(jié)論=>設(shè)立信號量s,s的初值設(shè)為20示例2：車站購票問題實現(xiàn)如下：進程Piwhile(TRUE){

P(s);

進入售票廳；購票；退出；

V(s);}ints=20

i=1,2,…示例3：搬運問題任務(wù)：

f,s,t,g:存放記錄的內(nèi)存區(qū)域f，g中可以存放m條記錄s,t均為可存放1條記錄的臨時緩沖進程Get,Copy,Put完成f到g的記錄搬移工作Get負責(zé)從f中搬一條記錄到s中Copy負責(zé)將s中的記錄搬到t中Put負責(zé)將t中的記錄搬到g中示例3：搬運問題不加同步時可能出現(xiàn)的執(zhí)行順序問題：將t中的陳舊數(shù)據(jù)2放到了g中示例3：搬運問題進程之間的合法執(zhí)行順序可以采用下列偏序圖來表示示例3：搬運問題Solution1:Get:While(true){

P(empty_s);Get();//

V(full_s);}copy:

while(true){

P(full_s);

P(empty_t);copy();

V(full_t);

V(empty_s);}put:

while(true){

P(full_t);put();

V(empty_t);}示例3：搬運問題信號量empty_s，表示s中的空位信號量full_t，表示t中的記錄數(shù)信號量full_s，表示s中的記錄數(shù)信號量empty_t，表示t中的空位示例3：搬運問題Solution2Get:While(true){

P(empty_s);Get();//

V(S);}copy:

while(true){

P(S);P(S);copy();

V(full_t);

V(empty_s);}put:

while(true){

P(full_t);put();

V(S);}示例4：公共汽車問題例3：設(shè)在公共汽車上，司機和售票員的活動分別是：司機：啟動車輛，正常行車，到站停車。售票員：上乘客，關(guān)車門，售票，開車門，下乘客。用PV操作對其控制。分析：（1）進程關(guān)系：司機到站停車后，售票員方可開車門售票員關(guān)車門后，司機才能開車（2）確定信號量。例3，解：進程要做的基本動作如下：進程Driverwhile(TRUE){

啟動車輛；

正常行車；

到站停車；}進程Conductorwhile(TRUE){

上乘客；

關(guān)車門；

售票；

開車門；

下乘客；}示例4：公共汽車問題例3，解：進程Driverwhile(TRUE){

P(run);

啟動車輛；

正常行車；

到站停車；

V(stop);}進程Conductorwhile(TRUE){

上乘客；

關(guān)車門；

V(run);

售票；

P(stop);

開車門；

下乘客；}信號量run=0Stop=0示例4：公共汽車問題P、V操作討論互斥信號量必定成對出現(xiàn)：進入臨界區(qū)——臨界區(qū)——退出臨界區(qū)同步信號量未必成對出現(xiàn)，依賴于同步關(guān)系的性質(zhì)當(dāng)為互斥操作時，它們同處于同一進程當(dāng)為同步操作時，則不在同一進程中出現(xiàn)如果P(S1)和P(S2)兩個操作在一起，那么P操作的順序至關(guān)重要，一個同步P操作與一個互斥P操作在一起時，同步P操作在互斥P操作前（互斥信號量永遠緊鄰臨界區(qū)）兩個V操作的順序無關(guān)緊要例：有一個充分大的池子，兩個人分別向池內(nèi)投球。甲投紅球，乙投藍球，一次投一個。開始時池子中有紅藍球各一個。要求池中紅藍球滿足：藍球數(shù)≤紅球數(shù)≤2藍球數(shù)。用P、V操作描述兩個進程。

甲乙

while(true){while(true){

P(r);P(b);

扔一個紅球；扔一個藍球；

V(b);V(r);}V(r);}R初值為1，b初值為0思考1：圍棋問題生產(chǎn)圍棋的工人不小心把相等數(shù)量的黑子和白子混裝載一個箱子里，現(xiàn)要用自動分揀系統(tǒng)把黑子和白子分開，該系統(tǒng)由兩個并發(fā)執(zhí)行的進程組成，功能如下：

（1）進程A專門揀黑子，進程B專門揀白子；

（2）每個進程每次只揀一個子，當(dāng)一個進程 在揀子時不允許另一個進程去揀子；思考1：圍棋問題（3）當(dāng)一個進程揀了一個棋子（黑子或白子）以后，必讓另一個進程揀一個棋子（黑子或白子）。假設(shè)黑子先揀Process撿黑子While(true){

p(b);

p(mutex);

撿黑子；

v(mutex);

v(w);}Process撿白子While(true){

p(w);

p(mutex);撿白子；

v(mutex);

v(b);}思考2：P/V操作解決訂票問題例：假定航空公司有k個航班，票數(shù)分別為A[i],i=1,2,…,k。設(shè)有n個售票窗口，都可以對外售票。設(shè)置互斥信號量mutex，初值mutex:=1;processPiwhile(true){

按旅客定票要求找到A[m]；

P(mutex); Xi=A[m]; ifXi>=1{Xi:=Xi-1;

A[m]:=Xi;

V(mutex);

輸出一張票；} else{

V(mutex);

輸出票已售完；}end;思考2：P/V操作解決訂票問題設(shè)置互斥信號量mutex[i]，i=1,2,…,k.初值mutex[i]:=1;processPiwhile(true){

按旅客定票要求找到A[m]；

P(mutex[m]); Xi=A[m]; ifXi>=1{Xi:=Xi-1;

A[m]:=Xi;

V(mutex[m]);

輸出一張票；} else{

V(mutex[m]);

輸出票已售完；}end;思考3：蘋果桔子問題

桌上有一只盤子，每次只能放入一只水果；爸爸專向盤子中放蘋果(apple)，媽媽專向盤子中放桔子(orange)，一個兒子專等吃盤子中的桔子，一個女兒專等吃盤子里的蘋果信號量sp/*盤子里可以放幾個水果*/sg1/*盤子里有桔子*/sg2/*盤子里有蘋果*/設(shè)初值sp:=1;Sg1,:=0;sg2:=0;processfatherWhile(true){

削一個蘋果；

P(sp);

把蘋果放入plate；

V(sg2);

}processmotherWhile(true){

剝一個桔子；

P(sp);

把桔子放入plate；

V(sg1);}processsonWhile(true){ P(sg1);

從plate中取桔子；

V(sp);

吃桔子；}processdaughterWhile(true){ P(sg2);

從plate中取蘋果；

V(sp);

吃蘋果；}DeadlockandStarvationDeadlock–twoormoreprocessesarewaitingindefinitelyforaneventthatcanbecausedbyonlyoneofthewaitingprocessesLetSandQbetwosemaphoresinitializedto1

P0

P1

wait(S); wait(Q); wait(Q); wait(S); . . . . . . signal(S);

signal(Q); signal(Q);

signal(S);Starvation

–indefiniteblocking.Aprocessmayneverberemovedfromthesemaphorequeueinwhichitissuspended.Dining-PhilosophersProblemShareddataBowlofrice(dataset)Semaphorechopstick[5]initializedto1Dining-PhilosophersProblem(Cont.)ThestructureofPhilosopheri:While(true){wait(chopstick[i]); wait(chopStick[(i+1)%5]);

//eat signal(chopstick[i]); signal(chopstick[(i+1)%5]);

//think}ProblemswithSemaphoresIncorrectuseofsemaphoreoperations:

signal(mutex)….wait(mutex)

wait(mutex)…wait(mutex)Omittingofwait(mutex)orsignal(mutex)(orboth)MonitorsAhigh-levelabstractionthatprovidesaconvenientandeffectivemechanismforprocesssynchronizationOnlyoneprocessmaybeactivewithinthemonitoratatimemonitormonitor-name{ //sharedvariabledeclarations procedureP1(…){….} … procedurePn(…){……}Initializationcode(….){…} … }}SchematicviewofaMonitorConditionVariablesconditionx,y;Twooperationsonaconditionvariable:x.wait()–aprocessthatinvokestheoperationissuspended.x.signal()–

resumesoneofprocesses

(ifany)

that

invoked

x.wait()MonitorwithConditionVariablesSolutiontoDiningPhilosophersmonitorDP{

enum{THINKING;HUNGRY,EATING)state[5]; conditionself[5]; voidpickup(inti){

state[i]=HUNGRY;

test(i); if(state[i]!=EATING)self[i].wait; }

voidputdown(inti){

state[i]=THINKING;//testleftandrightneighbors

test((i+4)%5);

test((i+1)%5);}

SolutiontoDiningPhilosophers(cont) voidtest(inti){ if((state[(i+4)%5]!=EATING)&& (state[i]==HUNGRY)&& (state[(i+1)%5]!=EATING)){

state[i]=EATING;

self[i].signal(); } }

initialization_code(){ for(inti=0;i<5;i++)

state[i]=THINKING;

}}SolutiontoDiningPhilosophers(cont)EachphilosopherIinvokesthe

operationspickup()

andputdown()inthefollowingsequence:

dp.pickup(i)EAT

dp.putdown(i)

MonitorImplementationUsingSemaphoresVariables

semaphoremutex;//(initially=1) semaphorenext;//(initially=0)

intnext-count=0;

EachprocedureFwillbereplacedby

wait(mutex); … bodyofF; … if(next-count>0)

signal(next) else

signal(mutex);

Mutualexclusionwithinamonitorisensured.MonitorImplementationForeachconditionvariablex,wehave:

semaphorex-sem;//(initially=0)

intx-count=0;

Theoperationx.wait

canbeimplementedas:

x-count++; if(next-count>0)

signal(next); else

signal(mutex);

wait(x-sem); x-count--;

MonitorImplementationTheoperationx.signal

canbeimplementedas:

if(x-count>0){ next-count++;

signal(x-sem);

wait(next); next-count--; }

SynchronizationExamplesSolarisWindowsXPLinuxPthreadsSolarisSynchronizationImplementsavarietyoflockstosupportmultitasking,multithreading(includingreal-timethreads),andmultiprocessingUsesadaptivemutexesforefficiencywhenprotectingdatafromshortcodesegmentsUsesconditionvariablesandreaders-writerslockswhenlongersectionsofcodeneedaccesstodataUsesturnstilestoorderthelistofthreadswaitingtoacquireeitheranadaptivemutexorreader-writerlockWindowsXPSynchronizationUsesinterruptmaskstoprotectaccesstoglobalresourcesonuniprocessorsystemsUsesspinlocksonmultiprocessorsystemsAlsoprovidesdispatcherobjectswhichmayactaseithermutexesandsemaphoresDispatcherobjectsmayalsoprovideeventsAneventactsmuchlikeaconditionvariableLinuxSynchronizationLinux:disablesinterruptstoimplementshortcriticalsectionsLinuxprovides:semaphoresspinlocksPthreadsSynchronizationPthreadsAPIisOS-independentItprovides:mutexlocksconditionvariables

Non-portableextensionsinclude:read-writelocksspinlocksAtomicTransactionsSystemModelLog-basedRecoveryCheckpointsConcurrentAtomicTransactionsSystemModelAssuresthatoperationshappenasasinglelogicalunitofwork,initsentirety,ornotatallRelatedtofieldofdatabasesystemsChallengeisassuringatomicitydespitecomputersystemfailuresTransaction-collectionofinstructionsoroperationsthatperformssinglelogicalfunctionHereweareconcernedwithchangestostablestorage–diskTransactionisseriesofreadandwriteoperationsTerminatedbycommit(transactionsuccessful)orabort(transactionfailed)operationAbortedtransactionmustberolledbacktoundoanychangesitperformedTypesofStorageMediaVolatilestorage–informationstoredheredoesnotsurvivesystemcrashesExample:mainmemory,cacheNonvolatilestorage–InformationusuallysurvivescrashesExample:diskandtapeStablestorage–InformationneverlostNotactuallypossible,soapproximatedviareplicationorRAIDtodeviceswithindependentfailuremodesGoalistoassuretransactionatomicitywherefailurescauselossofinformationonvolatilestorage