第七講 進程的同步

第七講進程的同步Background背景TheCritical-SectionProblem臨界區(qū)的問題SynchronizationHardware同步硬件Semaphores信號量ClassicalProblemsofSynchronization同步的經(jīng)典問題CriticalRegions臨界區(qū)Monitors管城SynchronizationinSolaris2&Windows2000Solaris2和Windows2000的同步問題OperatingSystemConceptsBackgroundConcurrentaccesstoshareddatamayresultindatainconsistency.對共享數(shù)據(jù)區(qū)的訪問導(dǎo)致數(shù)據(jù)的不一致性Maintainingdataconsistencyrequiresmechanismstoensuretheorderlyexecutionofcooperatingprocesses.維持數(shù)據(jù)的一致性要求保證合作進程按一定的順序執(zhí)行的機制。Shared-memorysolutiontobounded-bufferproblem(Chapter4)allowsatmostn–1itemsinbufferatthesametime.Asolution,whereallNbuffersareusedisnotsimple.有限緩沖區(qū)問題的共享存儲器解決方案一次在緩沖區(qū)中只容許n-1個項目，Supposethatwemodifytheproducer-consumercodebyaddingavariablecounter,initializedto0andincrementedeachtimeanewitemisaddedtothebufferOperatingSystemConceptsBounded-BufferShareddata

#defineBUFFER_SIZE10typedefstruct{ ...}item;itembuffer[BUFFER_SIZE];intin=0;intout=0;intcounter=0;OperatingSystemConceptsBounded-BufferProducerprocess

itemnextProduced;

while(1){ while(counter==BUFFER_SIZE) ;/*donothing*/ buffer[in]=nextProduced; in=(in+1)%BUFFER_SIZE; counter++; }OperatingSystemConceptsBounded-BufferConsumerprocess

itemnextConsumed;

while(1){ while(counter==0) ;/*donothing*/ nextConsumed=buffer[out]; out=(out+1)%BUFFER_SIZE; counter--; }

OperatingSystemConceptsBoundedBufferThestatements

counter++;

counter--;

mustbeperformedatomically.Atomicoperationmeansanoperationthatcompletesinitsentiretywithoutinterruption.

OperatingSystemConceptsBoundedBufferThestatement“count++”maybeimplementedinmachinelanguageas:

register1=counter register1=register1+1

counter=register1

Thestatement“count—”maybeimplementedas:

register2=counter

register2=register2–1

counter=register2OperatingSystemConceptsBoundedBufferIfboththeproducerandconsumerattempttoupdatethebufferconcurrently,theassemblylanguagestatementsmaygetinterleaved.Interleavingdependsuponhowtheproducerandconsumerprocessesarescheduled.OperatingSystemConceptsBoundedBufferAssumecounterisinitially5.Oneinterleavingofstatementsis:

producer:register1=counter(register1=5)

producer:register1=register1+1(register1=6)

consumer:register2=counter(register2=5)

consumer:register2=register2–1(register2=4)

producer:counter=register1(counter=6)

consumer:counter=register2(counter=4)

Thevalueofcountmaybeeither4or6,wherethecorrectresultshouldbe5.OperatingSystemConceptsRaceCondition

競爭條件Racecondition:Thesituationwhereseveralprocessesaccess–andmanipulateshareddataconcurrently.Thefinalvalueoftheshareddatadependsuponwhichprocessfinisheslast.

競爭條件：幾個進程并行地訪問和操作共享數(shù)據(jù)的情形。最后的結(jié)果取決于最后那一個進程最后完成。Topreventraceconditions,concurrentprocessesmustbesynchronized.為了阻止出現(xiàn)競爭的條件，并行進程必須同步。OperatingSystemConceptsTheCritical-SectionProblem

臨界區(qū)問題nprocessesallcompetingtousesomeshareddatan個進程都需要競爭使用某些共享的數(shù)據(jù)區(qū)。Eachprocesshasacodesegment,calledcriticalsection,inwhichtheshareddataisaccessed.

每個進程有一個代碼段，稱為臨界區(qū)，訪問共享數(shù)據(jù)的代碼都在臨界區(qū)中。Problem–ensurethatwhenoneprocessisexecutinginitscriticalsection,nootherprocessisallowedtoexecuteinitscriticalsection.問題-確保當一個進程在臨界區(qū)中時，沒有其它進程在臨界區(qū)中。OperatingSystemConceptsSolutiontoCritical-SectionProblem

臨界區(qū)問題的解決方案1. MutualExclusion(互斥條件)：IfprocessPiisexecutinginitscriticalsection,thennootherprocessescanbeexecutingintheircriticalsections.2. Progress(進入條件)：Ifnoprocessisexecutinginitscriticalsectionandthereexistsomeprocessesthatwishtoentertheircriticalsection,thentheselectionoftheprocessesthatwillenterthecriticalsectionnextcannotbepostponedindefinitely.3. BoundedWaiting(有限等待的條件)：Aboundmustexistonthenumberoftimesthatotherprocessesareallowedtoentertheircriticalsectionsafteraprocesshasmadearequesttoenteritscriticalsectionandbeforethatrequestisgranted.AssumethateachprocessexecutesatanonzerospeedNoassumptionconcerningrelativespeedofthenprocesses.OperatingSystemConceptsInitialAttemptstoSolveProblem

解決臨界區(qū)問題的初步方案Only2processes,P0andP1僅考慮兩個進程的情形GeneralstructureofprocessPi

(otherprocessPj)

進程中的一般結(jié)構(gòu)

do{

entrysection criticalsection

exitsection remindersection }while(1);Processesmaysharesomecommonvariablestosynchronizetheiractions.進程通過共享一些變量來同步它們的行為。OperatingSystemConceptsAlgorithm1Sharedvariables:intturn;

initiallyturn=0turn-i

PicanenteritscriticalsectionProcessPi

do{

while(turn!=i); criticalsection

turn=j; remindersection }while(1);Satisfiesmutualexclusion,butnotprogressOperatingSystemConceptsAlgorithm2Sharedvariablesbooleanflag[2];

initiallyflag[0]=flag[1]=false.flag[i]=true

PireadytoenteritscriticalsectionProcessPi

do{ flag[i]:=true;

while(flag[j]); criticalsection flag[i]=false;

remaindersection }while(1);Satisfiesmutualexclusion,butnotprogressrequirement.OperatingSystemConceptsAlgorithm3Combinedsharedvariablesofalgorithms1and2.ProcessPi

do{

flag[i]:=true;

turn=j;

while(flag[j]andturn=j); criticalsection

flag[i]=false; remaindersection }while(1);Meetsallthreerequirements;solvesthecritical-sectionproblemfortwoprocesses.OperatingSystemConceptsBakeryAlgorithm

面包師算法Beforeenteringitscriticalsection,processreceivesanumber.Holderofthesmallestnumberentersthecriticalsection.進入臨界區(qū)前，進程得到一個數(shù)字，持有最小數(shù)字的進程獲準進入臨界區(qū)。IfprocessesPiandPjreceivethesamenumber,ifi<j,thenPiisservedfirst;elsePjisservedfirst.如果兩個進程得到相同的數(shù)字，進程號較小者獲準進入臨界區(qū)Thenumberingschemealwaysgeneratesnumbersinincreasingorderofenumeration;i.e.,1,2,3,3,3,3,4,5...永遠以增序的形式產(chǎn)生數(shù)字。Criticalsectionfornprocessesn個進程的臨界區(qū)算法OperatingSystemConceptsBakeryAlgorithm

面包師算法Notation<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];Datastructuresareinitializedtofalseand0respectivelyOperatingSystemConceptsBakeryAlgorithmdo{

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);OperatingSystemConceptsSynchronizationHardwareTestandmodifythecontentofawordatomically

.

booleanTestAndSet(boolean&target){ booleanrv=target; tqrget=true; returnrv; }OperatingSystemConceptsMutualExclusionwithTest-and-SetShareddata:

booleanlock=false;

ProcessPi

do{ while(TestAndSet(lock));

criticalsection lock=false;

remaindersection }OperatingSystemConceptsSynchronizationHardwareAtomicallyswaptwovariables.

voidSwap(boolean&a,boolean&b){ booleantemp=a; a=b; b=temp; }OperatingSystemConceptsMutualExclusionwithSwapShareddata(initializedtofalse):

booleanlock; booleanwaiting[n];

ProcessPi

do{ key=true; while(key==true) Swap(lock,key);

criticalsection lock=false;

remaindersection }OperatingSystemConceptsSemaphoresSynchronizationtoolthatdoesnotrequirebusywaiting.SemaphoreS–integervariablecanonlybeaccessedviatwoindivisible(atomic)operations

wait(S):

whileS0dono-op;

S--;

signal(S):

S++;OperatingSystemConceptsCriticalSectionofnProcessesShareddata: semaphoremutex;//initiallymutex=1

ProcessPi:

do{

wait(mutex);

criticalsection signal(mutex);

remaindersection

}while(1);

OperatingSystemConceptsSemaphoreImplementationDefineasemaphoreasarecord

typedefstruct{ intvalue;

structprocess*L;

}semaphore;

Assumetwosimpleoperations:blocksuspendstheprocessthatinvokesit.wakeup(P)resumestheexecutionofablockedprocessP.OperatingSystemConceptsImplementationSemaphoreoperationsnowdefinedas

wait(S):

S.value--; if(S.value<0){

addthisprocesstoS.L;

block; }

signal(S):

S.value++; if(S.value<=0){

removeaprocessPfromS.L;

wakeup(P); }OperatingSystemConceptsSemaphoreasaGeneralSynchronizationToolExecuteBinPjonlyafterAexecutedinPiUsesemaphoreflaginitializedto0Code: Pi Pj

A

wait(flag)

signal(flag) BOperatingSystemConceptsDeadlockandStarvationDeadlock–twoormoreprocessesarewaitingindefinitelyforaneventthatcanbecausedbyonlyoneofthewaitingprocesses.LetSandQbetwosemaphoresinitializedto1

P0

P1

wait(S); wait(Q);

wait(Q); wait(S);

signal(S); signal(Q);

signal(Q) signal(S);Starvation

–indefiniteblocking.Aprocessmayneverberemovedfromthesemaphorequeueinwhichitissuspended.OperatingSystemConceptsTwoTypesofSemaphoresCountingsemaphore–integervaluecanrangeoveranunrestricteddomain.Binarysemaphore–integervaluecanrangeonlybetween0and1;canbesimplertoimplement.CanimplementacountingsemaphoreSasabinarysemaphore.OperatingSystemConceptsImplementingSasaBinarySemaphoreDatastructures: binary-semaphoreS1,S2; intC:Initialization:

S1=1 S2=0 C=initialvalueofsemaphoreSOperatingSystemConceptsImplementingSwaitoperation

wait(S1); C--; if(C<0){ signal(S1); wait(S2); } signal(S1);

signaloperation

wait(S1); C++; if(C<=0) signal(S2); else signal(S1);OperatingSystemConceptsClassicalProblemsofSynchronizationBounded-BufferProblem

ReadersandWritersProblem

Dining-PhilosophersProblemOperatingSystemConceptsBounded-BufferProblemShareddata

semaphorefull,empty,mutex;

Initially:

full=0,empty=n,mutex=1OperatingSystemConceptsBounded-BufferProblemProducerProcess

do{ …

produceaniteminnextp … wait(empty); wait(mutex); …

addnextptobuffer … signal(mutex); signal(full); }while(1);

OperatingSystemConceptsBounded-BufferProblemConsumerProcess

do{ wait(full) wait(mutex); …

removeanitemfrombuffertonextc … signal(mutex); signal(empty); …

consumetheiteminnextc … }while(1);OperatingSystemConceptsReaders-WritersProblemShareddata

semaphoremutex,wrt;

Initially

mutex=1,wrt=1,readcount=0

OperatingSystemConceptsReaders-WritersProblemWriterProcess

wait(wrt); …

writingisperformed … signal(wrt);OperatingSystemConceptsReaders-WritersProblemReaderProcess

wait(mutex); readcount++; if(readcount==1) wait(rt); signal(mutex);

… readingisperformed …

wait(mutex); readcount--; if(readcount==0) signal(wrt); signal(mutex):OperatingSystemConceptsDining-PhilosophersProblemShareddata

semaphorechopstick[5];Initiallyallvaluesare1OperatingSystemConceptsDining-PhilosophersProblemPhilosopheri:

do{ wait(chopstick[i]) wait(chopstick[(i+1)%5]) …

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

think … }while(1);OperatingSystemConceptsCriticalRegionsHigh-levelsynchronizationconstructAsharedvariablevoftypeT,isdeclaredas:

v:

shared

TVariablevaccessedonlyinsidestatement

region

v

when

B

do

S

whereBisabooleanexpression.

WhilestatementSisbeingexecuted,nootherprocesscanaccessvariablev.OperatingSystemConceptsCriticalRegionsRegionsreferringtothesamesharedvariableexcludeeachotherintime.

Whenaprocesstriestoexecutetheregionstatement,theBooleanexpressionBisevaluated.IfBistrue,statementSisexecuted.Ifitisfalse,theprocessisdelayeduntilBbecomestrueandnootherprocessisintheregionassociatedwithv.OperatingSystemConceptsExample–BoundedBufferShareddata:

structbuffer{ intpool[n]; intcount,in,out; }

OperatingSystemConceptsBoundedBufferProducerProcessProducerprocessinsertsnextpintothesharedbuffer

regionbufferwhen(count<n){

pool[in]=nextp;

in:=(in+1)%n;

count++;

}OperatingSystemConceptsBoundedBufferConsumerProcessConsumerprocessremovesanitemfromthesharedbufferandputsitinnextc

regionbufferwhen(count>0){ nextc=pool[out];

out=(out+1)%n;

count--;

}OperatingSystemConceptsImplementationregionxwhenBdoSAssociatewiththesharedvariablex,thefollowingvariables:

semaphoremutex,first-delay,second-delay;

intfirst-count,second-count;

Mutuallyexclusiveaccesstothecriticalsectionisprovidedbymutex.

IfaprocesscannotenterthecriticalsectionbecausetheBooleanexpressionBisfalse,itinitiallywaitsonthefirst-delaysemaphore;movedtothesecond-delaysemaphorebeforeitisallowedtoreevaluateB.OperatingSystemConceptsImplementationKeeptrackofthenumberofprocesseswaitingonfirst-delayandsecond-delay,withfirst-countandsecond-countrespectively.

ThealgorithmassumesaFIFOorderinginthequeuingofprocessesforasemaphore.

Foranarbitraryqueuingdiscipline,amorecomplicatedimplementationisrequired.OperatingSystemConceptsMonitorsHigh-levelsynchronizationconstructthatallowsthesafesharingofanabstractdatatypeamongconcurrentprocesses.

monitormonitor-name

{ sharedvariabledeclarations

procedurebody

P1

(…){ ... }

procedure

body

P2(…){ ... }

procedurebody

Pn

(…){ ... }

{ initializationcode

} }OperatingSystemConceptsMonitorsToallowaprocesstowaitwithinthemonitor,aconditionvariablemustbedeclared,as

conditionx,y;Conditionvariablecanonlybeusedwiththeoperationswaitandsignal.Theoperation

x.wait();

meansthattheprocessinvokingthisoperationissuspendeduntilanotherprocessinvokes

x.signal();Thex.signaloperationresumesexactlyonesuspendedprocess.Ifnoprocessissuspended,thenthesignaloperationhasnoeffect. OperatingSystemConceptsSchematicViewofaMonitorOperatingSystemConceptsMonitorWithConditionVariablesOperatingSystemConceptsDiningPhilosophersExample

monitordp { enum{thinking,hungry,eating}state[5]; conditionself[5]; voidpickup(inti) //followingslides voidputdown(inti) //followingslides voidtest(inti) //followingslides voidinit(){ for(inti=0;i<5;i++) state[i]=thinking; } }OperatingSystemConceptsDiningPhilosophers

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); }OperatingSystemConceptsDiningPhilosophers

voidtest(inti){ if((state[(I+4)%5]!=eating)&& (state[i]==hungry)&& (state[(i+1)%5]!=eating)){ state[i]=eating; self[i].signal(); } }

OperatingSystemConceptsMonitorImplementationUsingSemaphoresVariables

semaphoremutex;//(initially=1) semaphorenext;//(initially=0) intnext-count=0;

EachexternalprocedureFwillbereplacedby

wait(mutex); … bodyofF; …

if(next-count>0) signal(next) else signal(mutex);

Mutualexclusionwithinamonitorisensured.OperatingSystemConceptsMonitorImplementationForeachconditionvariablex,wehave:

semaphorex-sem;//(initially=0) intx-count=0;

Theoperationx.waitcanbeimple