操作系統(tǒng)原理：第七章 進(jìn)程同步

Chapter7:進(jìn)程同步Outline為什么需要進(jìn)程同步?臨界區(qū)問(wèn)題Racecondition解決方案?Peterson’s方案同步硬件方案:TestAndSet,Swap信號(hào)量管程經(jīng)典同步問(wèn)題并發(fā)事務(wù)Serializability2-PhaselockingMotivation同一程序順序執(zhí)行時(shí)是正確的，但并發(fā)執(zhí)行卻會(huì)發(fā)生錯(cuò)誤的結(jié)果.共享數(shù)據(jù)的并發(fā)訪(fǎng)問(wèn)可能導(dǎo)致數(shù)據(jù)的不一致維護(hù)數(shù)據(jù)的一致性需要能夠保證協(xié)作進(jìn)程順序執(zhí)行的機(jī)制Let’slookatanexample:生產(chǎn)者-消費(fèi)者問(wèn)題生產(chǎn)者-消費(fèi)者問(wèn)題Producerwhile(true){

/*produceanitemandputinnextProduced*/while(count==BUFFER_SIZE);//donothingbuffer[in]=nextProduced;in=(in+1)%BUFFER_SIZE;

count++;}count:thenumberofitemsinthebuffer(initializedto0)Consumerwhile(true){while(count==0);//donothing

nextConsumed=buffer[out];out=(out+1)%BUFFER_SIZE;

count--;

//consumetheiteminnextConsumed}在并行執(zhí)行中會(huì)產(chǎn)生什么錯(cuò)誤?競(jìng)爭(zhēng)條件count++couldbeimplementedas

register1=count

register1=register1+1

count=register1count--couldbeimplementedas

register2=count

register2=register2-1

count=register2在“count=5”的前提下考慮如下執(zhí)行順序:

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}在并行執(zhí)行中counter還有哪些可能的值?Howtopreventracecondition?在進(jìn)程中定義臨界區(qū)Readingandwritingcommonvariables.保證同一時(shí)刻只有一個(gè)進(jìn)程能訪(fǎng)問(wèn)臨界區(qū).Whatsynccodetoputintotheentry&exitsectionstopreventracecondition?do{ entrysection criticalsection exitsection remaindersection}while(TRUE);SolutiontoCritical-SectionProblem互斥-IfprocessPiisexecutinginitscriticalsection,thennootherprocessescanbeexecutingintheircriticalsections有空讓進(jìn)-Ifnoprocessisexecutinginitscriticalsectionandthereexistsomeprocessesthatwishtoentertheircriticalsection,thentheselectionoftheprocessesthatwillenterthecriticalsectionnextcannotbepostponedindefinitely有限等待-AboundmustexistonthenumberoftimesthatotherprocessesareallowedtoentertheircriticalsectionsafteraprocesshasmadearequesttoenteritscriticalsectionandbeforethatrequestisgrantedPeterson’sSolution2-進(jìn)程

解決方案假定LOAD和STORE等指令是原子的，;也即,這些指令不允許被中斷.2個(gè)進(jìn)程共享2個(gè)變量:intturn;Booleanflag[2]變量

turn

表示哪個(gè)進(jìn)程將進(jìn)入臨界區(qū).數(shù)組

flag

用于表示哪些進(jìn)程準(zhǔn)備進(jìn)入臨界區(qū).flag[i]=true暗示進(jìn)程Pi

準(zhǔn)備進(jìn)入臨界區(qū)AlgorithmforProcessPi

while(true){

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

flag[i]=FALSE;REMAINDERSECTION}

互斥Onlyoneprocessenterscriticalsectionatatime.Proof:canbothprocessespassthewhileloop(andentercriticalsection)atthesametime?有空讓進(jìn)Selectionforwaiting-to-enter-critical-sectionprocessdoesnotblock.Proof:canPiwaitatthewhileloopforever(afterPjleavescriticalsection)?有限等待Limitedtimeinwaitingforotherprocesses.Proof:canPjwinthecriticalsectiontwicewhilePiwaits?EntrySectionExitSectionAlgorithmforProcessPi

while(true){

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

flag[i]=FALSE;REMAINDERSECTION}

EntrySectionExitSectionwhile(true){

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

flag[j]=FALSE;REMAINDERSECTION}

面包師算法Beforeenteringitscriticalsection,processreceivesanumber.Holderofthesmallestnumberentersthecriticalsection.進(jìn)入臨界區(qū)前，進(jìn)程得到一個(gè)數(shù)字，持有最小數(shù)字的進(jìn)程獲準(zhǔn)進(jìn)入臨界區(qū)。IfprocessesPiandPjreceivethesamenumber,ifi<j,thenPiisservedfirst;elsePjisservedfirst.如果兩個(gè)進(jìn)程得到相同的數(shù)字，進(jìn)程號(hào)較小者獲準(zhǔn)進(jìn)入臨界區(qū)Thenumberingschemealwaysgeneratesnumbersinincreasingorderofenumeration;i.e.,1,2,3,3,3,3,4,5...永遠(yuǎn)以增序的形式產(chǎn)生數(shù)字。Criticalsectionfornprocessesn個(gè)進(jìn)程的臨界區(qū)算法BakeryAlgorithmNotation<lexicographicalorder(ticket#,processid#)(a,b)<(c,d)ifa<corifa=candb<dmax(a0,…,an-1)isanumber,k,suchthatk

aifori：0,

…,n–1Shareddata

booleanchoosing[n];

intnumber[n];Datastructuresareinitializedtofalseand0respectivelyBakeryAlgorithmdo{

choosing[i]=true; number[i]=max(number[0],number[1],…,number[n–1])+1; choosing[i]=false;

for(j=0;j<n;j++){ while(choosing[j]); while((number[j]!=0)&&((number[j],j)<(number[i],i))); } criticalsection

number[i]=0; remaindersection}while(1);同步硬件許多系統(tǒng)都提供了對(duì)臨界區(qū)代碼的硬件支持單處理器–關(guān)中斷CurrentlyrunningcodewouldexecutewithoutpreemptionGenerallytooinefficientonmultiprocessorsystemsOperatingsystemsusingthisnotbroadlyscalable現(xiàn)代計(jì)算機(jī)提供了一些特殊的原子執(zhí)行的硬件指令原子的=不被中斷TestAndSet(target):測(cè)試內(nèi)存字target并設(shè)定其值Swap(a,b):交換2個(gè)內(nèi)存字的內(nèi)容TestAndSetInstruction定義:

boolean

TestAndSet(boolean*target){

boolean

rv=*target;*target=TRUE;returnrv:}SolutionusingTestAndSet共享

boolean

變量lock,并初始化為false.解決方案:

while(true){while(TestAndSet(&lock));/*donothing//criticalsectionlock=FALSE;//remaindersection}上述方案滿(mǎn)足互斥要求嗎?有空讓進(jìn)和有限等待呢?如何解決?

EntrySectionExitSection有限等待版

TestAndSet共享變量

boolean

waiting[n];

booleanlock;//initializedfalse.解決方案:do{

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

waiting[i]=FALSE;//criticalsection j=(i+1)%n; while((j!=i)&&!waiting[j]) j=(j+1)%n; If(j==i)lock=FALSE; elsewaiting[j]=FALSE;//remindersection}while(TRUE);

互斥Proof:cantwoprocessespassthewhileloop(andentercriticalsection)atthesametime?有限等待Limitedtimeinwaitingforotherprocesses.Whatiswaiting[]for?Whendoeswaiting[i]settoFALSE?Proof:howlongdoesPi’swaittillwaiting[i]becomesFALSE?有空讓進(jìn)Proof:exitsectionunblocksatleastoneprocess’swaiting[]orsetthelocktoFALSE.EntrySectionExitSectionSwapInstruction定義:

voidSwap(boolean*a,boolean*b){

booleantemp=*a;*a=*b;*b=temp:}SolutionusingSwapSharedBooleanvariablelockinitializedtoFALSE;EachprocesshasalocalBooleanvariablekey.解決方案:

while(true){key=TRUE;while(key==TRUE)Swap(&lock,&key); //criticalsectionlock=FALSE; //remaindersection}互斥滿(mǎn)足嗎?有空讓進(jìn)和有限等待呢?NoticeaperformanceproblemwithSwap&TestAndSetsolutions?

EntrySectionExitSectionSharedBooleanvariablelockinitializedtoFALSE;EachprocesshasalocalBooleanvariablekey.解決方案:

while(true){key=TRUE;while(key==TRUE)Swap(&lock,&key); //criticalsectionlock=FALSE; //remaindersection}互斥滿(mǎn)足嗎?有空讓進(jìn)和有限等待呢?NoticeaperformanceproblemwithSwap&TestAndSetsolutions?

Semaphore（信號(hào)量）除了要保證正確性以外，還要考慮簡(jiǎn)化編程的問(wèn)題.HW/SWsolutionstothecriticalsectionproblemaretheyeasytouse&program?引入一個(gè)同步抽象—信號(hào)量easytouseandunderstandSemaphore信號(hào)量S–整型變量2個(gè)標(biāo)準(zhǔn)操作修改信號(hào)量S:wait():firsttestS<=0,thendecrementS. wait(S){whileS<=0 ;//no-opS--;}signal():incrementS. signal(S){S++;}對(duì)信號(hào)量整數(shù)值的修改必須不可分地執(zhí)行SemaphoreasGeneralSynchronizationTool計(jì)數(shù)式

信號(hào)量–integervaluecanrangeoveranunrestricteddomain二進(jìn)制

信號(hào)量–integervaluecanrangeonlybetween0

and1;canbesimplertoimplementAlsoknownasmutexlocks是否能用二進(jìn)制信號(hào)量來(lái)實(shí)現(xiàn)計(jì)數(shù)式信號(hào)量ProvidesmutualexclusionSemaphoreS;//initializedto1wait(S);CriticalSectionsignal(S);BinarySemaphore(0/1value)SemaphoreS;//initializedto1wait(S);//Entrysection

CriticalSectionsignal(S);//Exitsection_____________________wait(S){ whileS<=0;//no-op S--;}signal(S){ S++;}

MutualexclusionOnlyoneprocessenterscriticalsectionatatime.ProgressSelectionforwaiting-to-enter-critical-sectionprocessdoesnotblock.BoundedWaitingLimitedtimeinwaitingforotherprocesses.Problems:BoundedwaitingBusywaiting克服忙等待的信號(hào)量實(shí)現(xiàn)重新實(shí)現(xiàn)

wait(S)&signal(s)每一個(gè)信號(hào)量都有一個(gè)相關(guān)的等待隊(duì)列.

typedef

struct{

intvalue;

structprocess*list;}semaphore;新增兩個(gè)操作:阻塞–placetheprocessinvokingtheoperationontheappropriatewaitingqueue.喚醒

–removeoneofprocessesinthewaitingqueueandplaceitinthereadyqueue.

wait(S){ value--; if(value<0){ addthisprocesstowaitingqueue

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

wakeup(P); }}Doesitsolvebusywaitingandboundedwaiting?死鎖和饑餓死鎖

–2個(gè)或更多的進(jìn)程無(wú)限地等待一個(gè)事件，而該事件只能由這些等待進(jìn)程之一來(lái)產(chǎn)生LetSandQbetwosemaphoresinitializedto1

P0

P1

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

–無(wú)限阻塞.一個(gè)進(jìn)程永遠(yuǎn)無(wú)法從信號(hào)量等待隊(duì)列中刪除，即進(jìn)程在信號(hào)量?jī)?nèi)無(wú)窮等待的情況.經(jīng)典的同步問(wèn)題有限緩沖問(wèn)題Bounded-BufferProblem讀者和寫(xiě)者問(wèn)題ReadersandWritersProblem哲學(xué)家就餐問(wèn)題Dining-PhilosophersProblem有限緩沖區(qū)問(wèn)題有限緩沖共享內(nèi)存循環(huán)數(shù)組邏輯指針in&out（buffersize-1）計(jì)數(shù)器counter(buffersize)有限緩沖問(wèn)題的通用結(jié)構(gòu)Nbuffers,eachcanholdoneitemSemaphoremutexinitializedtothevalue1Semaphorefullinitializedtothevalue0SemaphoreemptyinitializedtothevalueN.BoundedBufferProblem(Cont.)Thestructureoftheproducerprocess

while(true){ //produceanitem wait(empty); wait(mutex); //addtheitemtothebuffer signal(mutex); signal(full);}Thestructureoftheconsumerprocesswhile(true){ wait(full); wait(mutex); //removeanitemfrombuffer signal(mutex); signal(empty);

//consumetheremoveditem}MutexFullEmpty讀者-寫(xiě)者問(wèn)題AdatasetissharedamongmanyconcurrentprocessesReaders–onlyreadthedatasetandnowrite.Writers–canbothreadandwrite.Problem–allowmultiplereaderstoreadatthesametime.Onlyonesinglewritercanaccesstheshareddataatthesametime.SharedDataDatasetSemaphoremutexinitializedto1.Semaphorewrtinitializedto1.Integerreadcountinitializedto0.Readers-WritersProblem(Cont.)Thestructureofawriterprocesswhile(true){ wait(wrt); //writingisperformed signal(wrt);}Attention:寫(xiě)者在臨界區(qū)時(shí)一個(gè)讀者在wrt等待其他讀者在mutex上等待Thestructureofthereaderprocesswhile(true){ wait(mutex);

readcount++; if(readcount==1)wait(wrt); signal(mutex) //readingisperformed

wait(mutex);

readcount--; if(readcount==0)signal(wrt);

signal(mutex);}High-levelstrategyNoconcurrentread&writeHigh-levelstrategy?UnblockwriteifnecessaryMutexWrtReadcount哲學(xué)家就餐問(wèn)題PhilosophersthinkPhilosophersbecomehungryPickuptwochopstickstoeatPhilosophersasconcurrentprocessesandchopsticksasshareddataBowlofrice(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}What’swrongwiththis?Althoughguaranteethatnotwoneighborscaneatatthesametime,deadlockmayoccur.Howtosolvedeadlockproblem?Howtosolvethedeadlineproblem?Allowatmost4philosophersonthetableatatimeAllowaphilosophertopickupherchopsticksonlyifbothchopsticksareavailableOddphilosopherpicksupfirstherleftchopstickandthenherrightchopstick(evenphilosopherdoestheopposite).Others?

解決死鎖無(wú)法消除饑餓ProblemswithSemaphoresCommonwronguseofsemaphoreoperations:signal(mutex)…criticalsection…wait(mutex)Whatwouldhappen?wait(mutex)…criticalsection…wait(mutex)Whatwouldhappen?Omittingofwait(mutex)orsignal(mutex)(orboth)Whatwouldhappen?Sometimes,errorsarenotre-producible.MakedebuggingdifficultMonitorsAhigh-levelabstractionprovidesaconvenientandeffectivemechanismforprocesssynchronizationOnlyoneprocessmaybeactivewithinthemonitoratatimemonitormonitor-name{ //sharedvariabledeclarations

procedureP1(…){….} … procedurePn(…){……}Initializationcode(….){…} … }}包含一組變量和函數(shù)的實(shí)現(xiàn)SchematicviewofaMonitorConditionVariablesconditionx,y;Twooperationsonaconditionvariable:x.wait()–aprocessthatinvokestheoperationissuspended.x.signal()–

resumesoneofprocesses

(ifany)

thatinvoked

x.wait()Similartosemaphoresignal()except

x.signal()doesnothingwhennoprocessisblocked.MonitorwithConditionVariablesSolutiontoDiningPhilosophers(cont)Allowaphilosop