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

Chapter6:ProcessSynchronizationModule6:ProcessSynchronization

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

進(jìn)程協(xié)作Independentprocesscannotaffectorbeaffectedbytheexecutionofanotherprocess獨(dú)立進(jìn)程不能影響或被在系統(tǒng)內(nèi)執(zhí)行的其他進(jìn)程所影響（在邏輯上無任何聯(lián)系的進(jìn)程）Cooperatingprocesscanaffectorbeaffectedbytheexecutionofanotherprocess協(xié)作進(jìn)程影響或被在系統(tǒng)內(nèi)執(zhí)行的其他進(jìn)程所影響（多個(gè)并發(fā)進(jìn)程在邏輯上有某種聯(lián)系）Advantagesofprocesscooperation進(jìn)程協(xié)作的好處Informationsharing信息共享Computationspeed-up加快計(jì)算Modularity模塊化Convenience方便協(xié)同進(jìn)程的相互作用直接作用：進(jìn)程間的相互聯(lián)系是有意識(shí)安排的，進(jìn)程各自的執(zhí)行結(jié)果互為對方的執(zhí)行條件。間接作用：進(jìn)程間要通過某種中介發(fā)生聯(lián)系，是無意識(shí)安排的相互感知程度相互關(guān)系一個(gè)進(jìn)程對其他進(jìn)程的影響相互不感知（完全不了解其它進(jìn)程的存在）競爭一個(gè)進(jìn)程的操作對其它進(jìn)程的結(jié)果無影響間接感知（雙方都與第三方交互，如共享資源）通過共享進(jìn)行協(xié)作一個(gè)進(jìn)程的結(jié)果依賴于從其它進(jìn)程獲得的信息直接感知（雙方直接交互，如通信）通過通信進(jìn)行協(xié)作一個(gè)進(jìn)程的結(jié)果依賴于從其它進(jìn)程獲得的信息ProcessSynchronization進(jìn)程同步（直接作用）指系統(tǒng)中多個(gè)進(jìn)程中發(fā)生的事件存在某種時(shí)序關(guān)系，需要相互合作，共同完成一項(xiàng)任務(wù)。具體的說，一個(gè)進(jìn)程運(yùn)行到某一點(diǎn)時(shí)要求另一伙伴進(jìn)程為它提供消息，在未獲得消息之前，該進(jìn)程處于等待狀態(tài)，獲得消息后被喚醒進(jìn)入就緒態(tài)。Example司機(jī)P1While(true){啟動(dòng)車輛；正常運(yùn)行；到站停車；}售票員P2While(true){關(guān)門；售票；開門；}MutualExclusion進(jìn)程互斥（間接作用）由于各進(jìn)程要求共享資源，而有些資源需要互斥使用，因此各進(jìn)程間競爭使用這些資源。（無序）Concurrentaccesstoshareddatamayresultindatainconsistency并發(fā)的訪問數(shù)據(jù)可能會(huì)導(dǎo)致數(shù)據(jù)的不一致性Maintainingdataconsistencyrequiresmechanismstoensuretheorderlyexecutionofcooperatingprocesses維持?jǐn)?shù)據(jù)的一致性需要一個(gè)保證協(xié)作進(jìn)程順序執(zhí)行的機(jī)制與時(shí)間有關(guān)的錯(cuò)誤搶椅子游戲民航售票與時(shí)間有關(guān)的錯(cuò)誤銀行存款OS的存儲(chǔ)管理與時(shí)間有關(guān)的錯(cuò)誤哲學(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）：多個(gè)進(jìn)程并發(fā)訪問和操作同一數(shù)據(jù)且執(zhí)行結(jié)果與訪問發(fā)生的特定順序有關(guān)臨界資源criticalresource何謂臨界資源？兩個(gè)或兩個(gè)以上的進(jìn)程不能同時(shí)使用的資源為臨界資源。臨界資源可能是一些獨(dú)占設(shè)備，如打印機(jī)、磁帶機(jī)等；也可能是一些共享變量、表格、鏈表、文件等。Critical-Section何謂臨界區(qū)Critical-Section？每個(gè)進(jìn)程中訪問臨界資源的那段代碼稱為臨界區(qū)。在臨界區(qū)前面增加一段用于進(jìn)行檢查的代碼，把這段代碼稱為進(jìn)入?yún)^(qū)entrysection

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

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

。這樣，可將一個(gè)訪問臨界資源的進(jìn)程描述如下：repeat

entrysection

criticalsection

exitsection

remaindersectionuntilfalse;SolutiontoCritical-SectionProblem1. MutualExclusion-IfprocessPiisexecutinginitscriticalsection,thennootherprocessescanbeexecutingintheircriticalsections互斥：一個(gè)進(jìn)程在臨界區(qū)執(zhí)行，其他進(jìn)程不得進(jìn)入臨界區(qū)(無空等待)2. Progress-Ifnoprocessisexecutinginitscriticalsectionandthereexistsomeprocessesthatwishtoentertheircriticalsection,thentheselectionoftheprocessesthatwillenterthecriticalsectionnextcannotbepostponedindefinitely前進(jìn)：有空讓進(jìn)，多中選一3. BoundedWaiting-Aboundmustexistonthenumberoftimesthatotherprocessesareallowedtoentertheircriticalsectionsafteraprocesshasmadearequesttoenteritscriticalsectionandbeforethatrequestisgranted有限等待：從一個(gè)進(jìn)程做出進(jìn)入臨界區(qū)的請求，到該請求允許為止，其他進(jìn)程允許進(jìn)入臨界區(qū)的次數(shù)有上界AssumethateachprocessexecutesatanonzerospeedNoassumptionconcerningrelativespeedoftheNprocessesTheCritical-SectionProblem:Solution由競爭各方平等協(xié)商引入進(jìn)程管理者，由管理者來協(xié)調(diào)競爭各方對互斥資源的使用具體方法：softwareapproaches（用編程解決，但常常忙等待）Hardwareapproaches（當(dāng)一個(gè)進(jìn)程進(jìn)入臨界區(qū)，就屏蔽所有中斷）Semaphores信號量Monitors管程softwareapproaches平等互斥基本思路是在進(jìn)入?yún)^(qū)檢查和設(shè)置一些標(biāo)志，如果已有進(jìn)程在臨界區(qū)，則在進(jìn)入?yún)^(qū)通過循環(huán)檢查進(jìn)行等待；在退出區(qū)修改標(biāo)志其中的主要問題是設(shè)置什么標(biāo)志和如何檢查標(biāo)志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時(shí)，Pi才能進(jìn)入臨界區(qū)當(dāng)flag[0]==flag[1]==true時(shí)，P0,P1的循環(huán)條件肯定只能有一個(gè)被滿足2.前進(jìn)條件滿足（空閑讓進(jìn)）可以證明，只要P0不被允許進(jìn)入，那么P1必定可以進(jìn)入；反之依然3.有限等待條件滿足Pi最多等待Pj一次之后即可進(jìn)入臨界區(qū)實(shí)現(xiàn)臨界區(qū)的方法1.兩進(jìn)程解法(P0,P1)（1）讓兩個(gè)進(jìn)程共享一個(gè)普通整數(shù)變量turn，其初值為0(或1)Ifturn==i,thenPi允許在CriticalSection內(nèi)執(zhí)行do{

while(turn!=i);

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

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

while(flag[j]);

臨界區(qū)

flag[i]=false;

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

while(flag[j]);

臨界區(qū)

flag[i]=false;

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

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

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

falseQ進(jìn)入臨界區(qū)

軟件方法2pturn，qturn

初值為falseP進(jìn)入臨界區(qū)條件：pturn，notqturnQ進(jìn)入臨界區(qū)條件：qturn，notpturn軟件方法3Dekker算法三個(gè)變量軟件方法的不足忙等待實(shí)現(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只能通過兩個(gè)原子操作改變信號量的值wait(S){whileS<=0 ;//no-opS--;}signal(S){S++;}SemaphoreasGeneralSynchronizationToolCountingsemaphore–integervaluecanrangeoveranunrestricteddomain計(jì)數(shù)信號量：值不受限制Binarysemaphore–integervaluecanrangeonlybetween0

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

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

SemaphoreImplementationwithnoBusywaiting

Witheachsemaphorethereisanassociatedwaitingqueue.為每個(gè)信號量設(shè)置一個(gè)等待隊(duì)列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)系，用一個(gè)整型變量來描述當(dāng)信號量大于0時(shí)，說明“環(huán)境安全”，可繼續(xù)運(yùn)行當(dāng)信號量小于0時(shí)，說明“互斥等待”，只能阻塞推廣到一般情況，信號量可解決復(fù)雜的同步互斥問題原語：OS以關(guān)中斷形式實(shí)現(xiàn)的不可打斷操作SEMAPHORES(信號量)Asemaphoremustbeinitializedonce.必須置一次且只能置一次初值A(chǔ)semaphoremustbeinitializedviaanonnegativevalue.初值不能為負(fù)數(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原語時(shí)，關(guān)注于資源/消息是否等待為其他進(jìn)程著想SynchronizationP1P2InputA

InputB

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

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

wait(S1);

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

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

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

signal(S1);

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

P(mutex);

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

V(mutex);V(S1);

消費(fèi)產(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個(gè)緩沖區(qū)、m個(gè)生產(chǎn)者和k個(gè)消費(fèi)者Q:While(true){P(S2);

P(mutex);

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

j=(j+1)%n;

V(mutex);V(S1);

消費(fèi)產(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);}若顛倒兩個(gè)P操作的順序？i=0,j=0,S1=n,S2=0，mutex=1多緩沖區(qū)的生產(chǎn)者和消費(fèi)者Q:j=0;While(true){P(S2);

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

V(S1);

消費(fèi)產(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)者和消費(fèi)者Q:j=0;While(true){P(S2);

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

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

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

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

R1……RmW1…...Wnaccessing示例1：讀者/寫者問題進(jìn)程關(guān)系分析讀操作可以同時(shí)進(jìn)行（R-R）讀操作和寫操作不可以同時(shí)進(jìn)行（R-W，互斥）寫操作和寫操作不可以同時(shí)進(jìn)行（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);

};存在的問題：互斥條件使用過于嚴(yán)厲，讀者之間實(shí)際上并不存在互斥關(guān)系，但這里mutex的使用使得讀者之間產(chǎn)生了一種互斥的關(guān)系實(shí)現(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);};實(shí)現(xiàn)方法2：解決共享讀的問題示例1：讀者/寫者問題方案2中存在的問題：多個(gè)寫者緊接著過來！那么讀者餓死多個(gè)讀者過來，寫者會(huì)餓死通常有另一種稱為讀者寫者公平的實(shí)現(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);};實(shí)現(xiàn)方法3：讀者寫者公平示例1：讀者/寫者問題示例2：車站購票問題例1：某車站售票廳，任何時(shí)刻最多可容納20名購票者進(jìn)入，當(dāng)售票廳中少于20名購票者時(shí)，廳外的購票者可立即進(jìn)入，否則需要在外面等待。每個(gè)購票者可看成一個(gè)進(jìn)程。分析： 共享資源--售票廳中等待的空位資源容量--20(最多有20個(gè)空位)結(jié)論=>設(shè)立信號量s,s的初值設(shè)為20示例2：車站購票問題實(shí)現(xiàn)如下：進(jìn)程Piwhile(TRUE){

P(s);

進(jìn)入售票廳；購票；退出；

V(s);}ints=20

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

f,s,t,g:存放記錄的內(nèi)存區(qū)域f，g中可以存放m條記錄s,t均為可存放1條記錄的臨時(shí)緩沖進(jìn)程Get,Copy,Put完成f到g的記錄搬移工作Get負(fù)責(zé)從f中搬一條記錄到s中Copy負(fù)責(zé)將s中的記錄搬到t中Put負(fù)責(zé)將t中的記錄搬到g中示例3：搬運(yùn)問題不加同步時(shí)可能出現(xiàn)的執(zhí)行順序問題：將t中的陳舊數(shù)據(jù)2放到了g中示例3：搬運(yùn)問題進(jìn)程之間的合法執(zhí)行順序可以采用下列偏序圖來表示示例3：搬運(yùn)問題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：搬運(yùn)問題信號量empty_s，表示s中的空位信號量full_t，表示t中的記錄數(shù)信號量full_s，表示s中的記錄數(shù)信號量empty_t，表示t中的空位示例3：搬運(yùn)問題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è)在公共汽車上，司機(jī)和售票員的活動(dòng)分別是：司機(jī)：啟動(dòng)車輛，正常行車，到站停車。售票員：上乘客，關(guān)車門，售票，開車門，下乘客。用PV操作對其控制。分析：（1）進(jìn)程關(guān)系：司機(jī)到站停車后，售票員方可開車門售票員關(guān)車門后，司機(jī)才能開車（2）確定信號量。例3，解：進(jìn)程要做的基本動(dòng)作如下：進(jìn)程Driverwhile(TRUE){

啟動(dòng)車輛；

正常行車；

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

上乘客；

關(guān)車門；

售票；

開車門；

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

P(run);

啟動(dòng)車輛；

正常行車；

到站停車；

V(stop);}進(jìn)程Conductorwhile(TRUE){

上乘客；

關(guān)車門；

V(run);

售票；

P(stop);

開車門；

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

甲乙

while(true){while(true){

P(r);P(b);

扔一個(gè)紅球；扔一個(gè)藍(lán)球；

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

（1）進(jìn)程A專門揀黑子，進(jìn)程B專門揀白子；

（2）每個(gè)進(jìn)程每次只揀一個(gè)子，當(dāng)一個(gè)進(jìn)程 在揀子時(shí)不允許另一個(gè)進(jìn)程去揀子；思考1：圍棋問題（3）當(dāng)一個(gè)進(jìn)程揀了一個(gè)棋子（黑子或白子）以后，必讓另一個(gè)進(jìn)程揀一個(gè)棋子（黑子或白子）。假設(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個(gè)航班，票數(shù)分別為A[i],i=1,2,…,k。設(shè)有n個(gè)售票窗口，都可以對外售票。設(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)，一個(gè)兒子專等吃盤子中的桔子，一個(gè)女兒專等吃盤子里的蘋果信號量sp/*盤子里可以放幾個(gè)水果*/sg1/*盤子里有桔子*/sg2/*盤子里有蘋果*/設(shè)初值sp:=1;Sg1,:=0;sg2:=0;processfatherWhile(true){

削一個(gè)蘋果；

P(sp);

把蘋果放入plate；

V(sg2);

}processmotherWhile(true){

剝一個(gè)桔子；

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