第七讲 进程的同步

第七讲进程的同步Background背景TheCritical-SectionProblem临界区的问题SynchronizationHardware同步硬件Semaphores信号量ClassicalProblemsofSynchronization同步的经典问题CriticalRegions临界区Monitors管城SynchronizationinSolaris2&Windows2000Solaris2和Windows2000的同步问题OperatingSystemConceptsBackgroundConcurrentaccesstoshareddatamayresultindatainconsistency.对共享数据区的访问导致数据的不一致性Maintainingdataconsistencyrequiresmechanismstoensuretheorderlyexecutionofcooperatingprocesses.维持数据的一致性要求保证合作进程按一定的顺序执行的机制。Shared-memorysolutiontobounded-bufferproblem(Chapter4)allowsatmostn–1itemsinbufferatthesametime.Asolution,whereallNbuffersareusedisnotsimple.有限缓冲区问题的共享存储器解决方案一次在缓冲区中只容许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.

竞争条件：几个进程并行地访问和操作共享数据的情形。最后的结果取决于最后那一个进程最后完成。Topreventraceconditions,concurrentprocessesmustbesynchronized.为了阻止出现竞争的条件，并行进程必须同步。OperatingSystemConceptsTheCritical-SectionProblem

临界区问题nprocessesallcompetingtousesomeshareddatan个进程都需要竞争使用某些共享的数据区。Eachprocesshasacodesegment,calledcriticalsection,inwhichtheshareddataisaccessed.

每个进程有一个代码段，称为临界区，访问共享数据的代码都在临界区中。Problem–ensurethatwhenoneprocessisexecutinginitscriticalsection,nootherprocessisallowedtoexecuteinitscriticalsection.问题-确保当一个进程在临界区中时，没有其它进程在临界区中。OperatingSystemConceptsSolutiontoCritical-SectionProblem

临界区问题的解决方案1. MutualExclusion(互斥条件)：IfprocessPiisexecutinginitscriticalsection,thennootherprocessescanbeexecutingintheircriticalsections.2. Progress(进入条件)：Ifnoprocessisexecutinginitscriticalsectionandthereexistsomeprocessesthatwishtoentertheircriticalsection,thentheselectionoftheprocessesthatwillenterthecriticalsectionnextcannotbepostponedindefinitely.3. BoundedWaiting(有限等待的条件)：Aboundmustexistonthenumberoftimesthatotherprocessesareallowedtoentertheircriticalsectionsafteraprocesshasmadearequesttoenteritscriticalsectionandbeforethatrequestisgranted.AssumethateachprocessexecutesatanonzerospeedNoassumptionconcerningrelativespeedofthenprocesses.OperatingSystemConceptsInitialAttemptstoSolveProblem

解决临界区问题的初步方案Only2processes,P0andP1仅考虑两个进程的情形GeneralstructureofprocessPi

(otherprocessPj)

进程中的一般结构

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.进入临界区前，进程得到一个数字，持有最小数字的进程获准进入临界区。IfprocessesPiandPjreceivethesamenumber,ifi<j,thenPiisservedfirst;elsePjisservedfirst.如果两个进程得到相同的数字，进程号较小者获准进入临界区Thenumberingschemealwaysgeneratesnumbersinincreasingorderofenumeration;i.e.,1,2,3,3,3,3,4,5...永远以增序的形式产生数字。Criticalsectionfornprocessesn个进程的临界区算法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