培训第二天进程同步

OperatingSystemConceptsChapter7:ProcessSynchronization

进程同步7.1Background背景7.2TheCritical-SectionProblem临界区问题7.3SynchronizationHardware同步的硬件实现7.4Semaphores

信号量7.5ClassicalProblemsofSynchronization

经典同步问题7.6CriticalRegions临界区7.7Monitors

管程7.8OSSynchronization操作系统的同步机制7.9AtomicTransactions

原子事务处理OperatingSystemConcepts7.1Background

背景Concurrentaccesstoshareddatamayresultindatainconsistency.对共享数据的并发访问可能导致数据的不一致性Maintainingdataconsistencyrequiresmechanismstoensuretheorderlyexecutionofcooperatingprocesses.要保持数据的一致性，就需要一种保证并发进程的正确执行顺序的机制OperatingSystemConcepts

Background(Cont.)Shared-memorysolutiontobounded-butterproblem(Chapter4)allowsatmostn–1itemsinbufferatthesametime.Asolution,whereallNbuffersareusedisnotsimple.第4章中解决有限缓冲区问题的共享内存方法…Supposethatwemodifytheproducer-consumercodebyaddingavariablecounter,initializedto0andincrementedeachtimeanewitemisaddedtothebuffer

假定我们通过增加一个计数器变量修改生产者-消费者代码，初始值为0，在缓冲区增加一个项目（数据）计数器加1OperatingSystemConceptsBounded-Buffer

有界缓冲区Shareddata

#defineBUFFER_SIZE10typedefstruct{ ...}item;itembuffer[BUFFER_SIZE];intin=0;intout=0;intcounter=0;OperatingSystemConceptsBounded-Buffer(Cont.-1)Producerprocess itemnextProduced;

while(1){ while(counter==BUFFER_SIZE) ;/*donothing*/ buffer[in]=nextProduced; in=(in+1)%BUFFER_SIZE; counter++; }OperatingSystemConceptsBounded-Buffer(Cont.-2)Consumerprocess itemnextConsumed;

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

OperatingSystemConceptsBoundedBuffer(Cont.-3)Thestatements

counter++;

counter--;

mustbeperformedatomically.Atomicoperationmeansanoperationthatcompletesinitsentiretywithoutinterruption.

OperatingSystemConceptsBoundedBuffer(Cont.-4)Thestatement“count++”maybeimplementedinmachinelanguageas:

register1=counter register1=register1+1

counter=register1

Thestatement“count—”maybeimplementedas:

register2=counter

register2=register2–1

counter=register2OperatingSystemConceptsBoundedBuffer(Cont.-5)Ifboththeproducerandconsumerattempttoupdatethebufferconcurrently,theassemblylanguagestatementsmaygetinterleaved.

如果生产者和消费者并发地更新缓冲区,汇编语言语句可以得到的交替存取Interleavingdependsuponhowtheproducerandconsumerprocessesarescheduled.

交替取决于生产者和消费者进程如何调度OperatingSystemConceptsBoundedBuffer(Cont.-6)Assumecounterisinitially5.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:Thesituationwhereseveralprocessesaccessandmanipulateshareddataconcurrently.Thefinalvalueoftheshareddatadependsuponwhichprocessfinisheslast.eofexecutiondependsontheparticularorderinwhichtheaccesstakesplace.

竞争条件：若干进程并发地访问并且操纵共享数据的情况。 共享数据的值取决于哪个进程最后完成Topreventraceconditions,concurrentprocessesmustbesynchronized.

防止竞争条件，并发进程必须被同步OperatingSystemConcepts7.2TheCritical-SectionProblem

临界区问题nprocessesallcompetingtousesomeshareddata

所有n个进程竞争使用一些共享的数据。Eachprocesshasacodesegment,calledcriticalsection,inwhichtheshareddataisaccessed.

每个进程有一个代码段,称为临界区,在哪儿共享数据被访问。Problem–ensurethatwhenoneprocessisexecutinginitscriticalsection,nootherprocessisallowedtoexecuteinitscriticalsection.

问题-

保证当一个进程正在临界区执行时，没有另外的进程进入临界区执行OperatingSystemConceptsSolutiontoCritical-SectionProblemmustsatisfy

解决临界区问题需满足1.

MutualExclusion:IfprocessPiisexecutinginitscriticalsection,thennootherprocessescanbeexecutingintheircriticalsections.互斥：假定进程Pi在其临界区内执行，其他任何进程将被排斥在自己的临界区之外2. Progress：Ifnoprocessisexecutinginitscriticalsectionandthereexistsomeprocessesthatwishtoentertheircriticalsection,thentheselectionoftheprocessesthatwillenterthecriticalsectionnextcannotbepostponedindefinitely.有空让进：临界区虽没有进程执行，但有些进程需要进入临界区，不能无限期地延长下一个要进入临界区进程的等待时间.OperatingSystemConceptsSolutiontoCritical-SectionProblemmustsatisfy(Cont.)3. BoundedWaiting.Aboundmustexistonthenumberoftimesthatotherprocessesareallowedtoentertheircriticalsectionsafteraprocesshasmadearequesttoenteritscriticalsectionandbeforethatrequestisgranted.有限等待。在一个进程提出进入临界区的请求和该请求得到答复的时间内，其他进程进入临界区前的等待时间必须是有限的.Assumethateachprocessexecutesatanonzerospeed假定每个进程都以非零的的速率执行.Noassumptionconcerningrelativespeedofthenprocesses.没有任何关于这n个进程相对执行速率的假定OperatingSystemConceptsFig7.1GeneralstructureofatypicalprocessPi

GeneralstructureofprocessPi

(otherprocessPj) do{

entrysection进入区 criticalsection临界区

exitsection退出区 remindersection剩余区 }while(1);Processesmaysharesomecommonvariablestosynchronizetheiractions.OperatingSystemConcepts7.2.1Two-ProcessSolutions

Algorithm1Only2processes,P0andP1Sharedvariables:intturn;

initiallyturn=0turn-iPicanenteritscriticalsectionProcessPi do{

while(turn!=i); criticalsection

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

initiallyflag[0]=flag[1]=false.flag[i]=truePireadytoenteritscriticalsectionProcessPi 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.OperatingSystemConceptsDekker算法–7.4题varboolranflag[2];flag[0]=flag[1]=false;intturn;turn=0/1;Pi:do{flag[i]=true;whileflag[j]{ifturn=j{flag[i]=false;whileturn=j;flag[i]=true;}}CriticalSectioniturn=j;flag[i]=false;RemainderSection}while(1);OperatingSystemConcepts7.2.2Multiple-ProcessSolutions

BakeryAlgorithm(面包房算法)Beforeenteringitscriticalsection,processreceivesanumber.Holderofthesmallestnumberentersthecriticalsection. 在进入临界区前，进程接收一个数字，最小数字的持有者进入临界区IfprocessesPiandPjreceivethesamenumber,ifi<j,thenPiisservedfirst;elsePjisservedfirst.Thenumberingschemealwaysgeneratesnumbersinincreasingorderofenumeration;i.e.,1,2,3,3,3,3,4,5...AlgorithmofsolvingtheCriticalsectionfornprocessesOperatingSystemConceptsBakeryAlgorithmDefinethefollowingNotationorder:(a,b)--(ticket#,processid#)(a,b)<(c,d)ifa<corifa=candb<dmax(a0,…,an-1)isanumber,k

suchthatk

aifori-0,…,n–1Shareddata booleanchoosing[n]; intnumber[n];Datastructuresareinitializedtofalseand0respectivelyOperatingSystemConceptsFig7.5ThestructureofprocessPiintheBakeryAlgorithm

do{ 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);OperatingSystemConcepts7.3SkynchronizationHardware

同步的硬件实现Hardwarefeaturescanmaketheprogrammingtaskeasierandimprovesystemefficiency.Hardwareinstruction:Testandmodifythecontentofawordatomically. booleanTestAndSet(boolean&target){ booleanrv=target; target=true; returnrv; }OperatingSystemConceptsFig7.7MutualExclusionwithTest-and-SetShareddata:

booleanlock=false;

ProcessPi do{ while(TestAndSet(lock)); criticalsection lock=false; remaindersection }while(1);OperatingSystemConceptsFig7.8ThedefinitionofSwapinstruction

Atomicallyswaptwovariables.

voidSwap(boolean&a,boolean&b){ booleantemp=a; a=b; b=temp; }OperatingSystemConceptsFig7.9MutualExclusionwithSwapShareddata(initializedtofalse):

booleanlock; booleanwaiting[n];

ProcessPi do{ key=true; while(key==true) Swap(lock,key); criticalsection lock=false; remaindersection }OperatingSystemConceptsFig7.10Bounded-waitingmutualexclusionwithTestAndSetBooleanwaiting[n],lock;tobeinitializetofalseDo{waiting[i]=true;key=true;while(waiting[i]&&key)key=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;remaindersection;}while(1)OperatingSystemConceptsBounded-waitingmutualexclusionwithTestAndSetThisalgorithmsatisfiesallthecriticalsectionrequirement.Toprovethatthemutual-exclusionrequirementismet,wenotethatprocessPicanenteritscriticalsectiononlyifeitherwaiting[i]==falseorkey==false.ThevalueofkeycanefalseonlyiftheTestAndSetisexecuted.ThefirstprocesstoexecutetheTestAndSetwillfindkey==false;allothersmustwait.Thevariablewaiting[i]canefalseonlyifanotherprocessleavesitscriticalsection;onlyonewaiting[i]issettofalse,maintainingthemutual-exclusionrequirement.OperatingSystemConcepts7.4Semaphores信号量Synchronizationtoolthatdoesnotrequirebusywaiting.一种不需要忙等待的同步工具.SemaphoreS–integervariable信号量S–整型变量canonlybeaccessedviatwoindivisible(atomic)operations仅能通过两个不可分割的[原子]操作访问

wait(S): whileS0dono-op;

S--;

signal(S):

S++;OperatingSystemConceptsFig7.11Multual-exclusionwithsemaphoresShareddata: semaphoremutex;//initiallymutex=1

ProcessPi:

do{

wait(mutex);

criticalsection signal(mutex);

remaindersection

}while(1);

OperatingSystemConcepts7.4.2SemaphoreImplementationDefineasemaphoreasarecord 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) B……OperatingSystemConcepts7.4.3DeadlockandStarvationDeadlock–twoormoreprocessesarewaitingindefinitelyforaneventthatcanbecausedbyonlyoneofthewaitingprocesses.

死锁–两个或多个进程无限期地等待一个事件的发生，而该事件正是由其中的一个等待进程引起的LetSandQbetwosemaphoresinitializedto1

S和Q是两个初值为1的信号量

P0

P1

wait(S); wait(Q);

wait(Q); wait(S);

signal(S); signal(Q);

signal(Q) signal(S);OperatingSystemConceptsDeadlockandStarvationStarvation–indefiniteblocking.Aprocessmayneverberemovedfromthesemaphorequeueinwhichitissuspended.

饥饿–无限期地阻塞。进程可能永远无法从它等待的信号量队列中移去OperatingSystemConcepts7.4.4TwoTypesofSemaphoresCountingsemaphore–integervaluecanrangeoveranunrestricteddomain.计数信号量–变化范围没有限制的整型值Binarysemaphore–integervaluecanrangeonlybetween0and1;canbesimplertoimplement.

二值信号量–变化范围仅限于0和1的信号量；容易实现OperatingSystemConceptsImplementingSasaBinarySemaphoreAcountingsemaphoreScanbeimplementedusingbinarysemaphore.计数信号量S可以用二值信号量实现Datastructures: 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);S>0：表示可用资源数目

S=0：即无可用资源也无进程等待

S<0：绝对值表示等待的进程数OperatingSystemConcepts7.5ClassicalProblemsofSynchronization

经典同步问题7.5.1Bounded-BufferProblem

有限缓冲区问题7.5.2ReadersandWritersProblem

读者写者问题7.5.3Dining-PhilosophersProblem哲学家就餐问题OperatingSystemConcepts7.5.1Bounded-BufferProblem

有限缓冲区问题Shareddata

semaphorefull,empty,mutex;

Initially:

full=0,empty=n,mutex=1OperatingSystemConceptsFig7.12ThestructureofProducerProcess

do{ … produceaniteminnextp …

… addnextptobuffer …

}while(1);

OperatingSystemConceptsFig7.13structureoftheConsumerProcess

do{

… removeanitemfrombuffertonextc …

… consumetheiteminnextc … }while(1);OperatingSystemConceptsFig7.12ThestructureofProducerProcess

do{ … produceaniteminnextp …

wait(mutex); … addnextptobuffer … signal(mutex);

}while(1);

OperatingSystemConceptsFig7.13structureoftheConsumerProcess

do{

wait(mutex); … removeanitemfrombuffertonextc … signal(mutex);

… consumetheiteminnextc … }while(1);OperatingSystemConceptsFig7.12ThestructureofProducerProcess

do{ … produceaniteminnextp …

wait(empty); wait(mutex); … addnextptobuffer … signal(mutex);

signal(full); }while(1);

OperatingSystemConceptsFig7.13structureoftheConsumerProcess

do{

wait(full); wait(mutex); … removeanitemfrombuffertonextc … signal(mutex);

signal(empty); … consumetheiteminnextc … }while(1);OperatingSystemConcepts7.5.2TheReaders-WritersProblem

读者写者问题Shareddata

semaphoremutex,wrt;

Initially

mutex=1,wrt=1,readcount=0

OperatingSystemConceptsFig7.14ThestructureofaWriterProcess引人互斥信号量wrt

wait(wrt); … writingisperformed … signal(wrt);OperatingSystemConceptsFig7.15ThestructureofaReaderProcess

第一个读者到时 wait(rt);

… readingisperformed …

最后一个读者离开时 signal(wrt);

OperatingSystemConceptsFig7.15ThestructureofaReaderProcess

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

… readingisperformed …

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

OperatingSystemConceptsFig7.15ThestructureofaReaderProcess引人互斥信号量mutex

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

signal(mutex); … readingisperformed …

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

signal(mutex)；OperatingSystemConcepts7.5.3Dining-PhilosophersProblem

哲学家就餐问题Shareddata semaphorechopstick[5];Initiallyallvaluesare1OperatingSystemConceptsFig7.17ThestructureofPhilosophersi

Philosopheri: do{ wait(chopstick[i]) wait(chopstick[(i+1)%5]) … eat … signal(chopstick[i]); signal(chopstick[(i+1)%5]); … think … }while(1);OperatingSystemConcepts7.6CriticalRegions

临界区High-levelsynchronizationconstructAsharedvariablevoftypeT,isdeclaredas:

v:sharedTVariablevaccessedonlyinsidestatement regionvwhenBdoS

whereBisabooleanexpression.

WhilestatementSisbeingexecuted,nootherprocesscanaccessvariablev.

OperatingSystemConcepts7.6(conditional)CriticalRegionsRegionsreferringtothesamesharedvariableexcludeeachotherintime.

访问区域相同共享变量同时互斥。Whenaprocesstriestoexecutetheregionstatement,theBooleanexpressionBisevaluated.IfBistrue,statementSisexecuted.Ifitisfalse,theprocessisdelayeduntilBestrueandnootherprocessisintheregionassociatedwithv.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--;

}OperatingSystemConceptsImplementationregionxwhenBdoSTheconditionalcriticalregioncouldbeimplementedbyacompiler.Associatewiththesharedvariablex,thefollowingvariables: semaphoremutex,first-delay,second-delay;

intfirst-count,second-count;Mutuallyexclusiveaccesstothecriticalsectionisprovidedbymutex.

mutex提供互斥访问临界区。IfaprocesscannotenterthecriticalsectionbecausetheBooleanexpressionBisfalse,itinitiallywaitsonthefirst-delaysemaphore;movedtothesecond-delaysemaphorebeforeitisallowedtoreevaluateB.

如果因为布尔表达式B是false，进程不能进入临界区，它开始 等待first-delay信号量;在它被允许再计算B以前，改到second-delay信号量。OperatingSystemConceptsImplementationregionxwhenBdoS(Cont.)wait(mutex);while(!B){first_count++;if(second_count>0)signal(second_delay);elsesignal(mutex);wait(first_delay);first_count--;second_count++;if(first_count>0)signal(first_delay);elsesignal(second_delay);wait(second_delay);second_count--;}S;OperatingSystemConceptsImplementationregionxwhenBdoS(Cont.)If(first_count>0)signal(first_delay);elseif(second_count>0)signal(second_delay);elsesignal(mutex);OperatingSystemConceptsImplementationKeeptrackofthenumberofprocesseswaitingonfirst-delayandsecond-delay,withfirst-countandsecond-countrespectively.

记录等待first-delayandsecond-delay的进程数 与first-countandsecond-count分别地。ThealgorithmassumesaFIFOorderinginthequeuingofprocessesforasemaphore.

算法假定信号量进程队列为一个FIFOForanarbitraryqueuingdiscipline,amorecomplicatedimplementationisrequired.

为任意队列要求，需要更复杂的实现OperatingSystemConcepts7.7Monitors管程High-levelsynchronizationconstructthatallowsthesafesharingofanabstractdatatypeamongconcurrentprocesses. 高级的同步机构允许并发进程间一种抽象的数据类型安全共享。Amonitorischaracterizedbyasetofprogramming-definedoperators

一个管程表示一个编程定义操作的集合Themonitorconstructensuresthatonlyoneprocessatatimecanbeactivewithinmonitor.

管程结构保证在某一时刻仅仅一个进程运行在管程里。

OperatingSystemConceptsMonitors(Cont.)Thesyntaxofamonitor:管程的语法

monitormonitor-name

{ sharedvariabledeclarations procedurebodyP1(…){... } procedurebodyP2(…){... }

procedurebodyPn(…){ ... } { initializationcode } }OperatingSystemConceptsMonitors(Cont.-1)Toallowaprocesstowaitwithinthemonitor,aconditionvariablemustbedeclared,as

允许一个进程在管程里等待（阻塞），一个条件变量必须被声明 conditionx,y;Conditionvariablecanonlybeusedwiththeoperationswaitandsignal.

条件变量只能使用wait和signal操作

OperatingSystemConceptsMonitors(Cont.-2)Theoperationx.wait()

meansthattheprocessinvokingthisoperationissuspendeduntilanotherprocessinvokesx.signal();

操作x.wait()表示调用这操作的进程挂起，直到另外的进程调用x.signal()Thex.signaloperationresumesexactlyonesuspendedprocess.Ifnoprocessissuspended,thenthesignaloperationhasnoeffect. x.signal()操作恢复（唤醒）被挂起进程。如果没有进程被挂起，那么signal操作没有效果。

OperatingSystemConceptsFig7.20SchematicViewofaMonitorOperatingSystemConceptsFig7.21MonitorWithConditionVariablesOperatingSystemConceptsStructureofMonitorEntranceQueueofEnteringProcessesMonitiorWaitingArea

Conditionc1C1.wait...conditioncn...Cn.waitUrgentQueueCx.signalExitM0NITOR

LocalDataConditionVariablesProcedure1ProcedurekInitializationCodeOperatingSystemConcepts

Monitors(Cont.-2)Whenthex.signal()operationisinvokedbyprocessP,thereisasuspendedprocessQassociatedwithconditionX.Twopossibilitiesexist: 当x.signal()操作被进程P调用,有一个与条件便变量X相关的被挂进程Q。存在二个可能性：PeitherwaitsuntilQleavesthemonitor,orwaitsforanothercondition. P等待直到Q离开管程，或等另外的条件。2.QeitherwaitsuntilPleavesthemonitor,orwaitsforanothercondition. Q等待直到P离开管程，或等另外的条件。OperatingSystemConceptsFig7.22AmonitorsolutiontotheDining-Philosophers

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; } }OperatingSystemConceptsFig7.22AmonitorsolutiontotheDining-Philosophers(Cont.)

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); }OperatingSystemConceptsFig7.22AmonitorsolutiontotheDining-Philosophers(Cont.-1)

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

Philosopher[I]:Do{dp.pickup(I);eatdp.putdown(I);think}while(1)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.waitcanbeimplementedas:

x-count++; if(next-count>0) signal(next); else signal(mutex); wait(x-sem); x-count--;

OperatingSystemConceptsMonitorImplementationTheoperationx.signalcanbeimplementedas:

if(x-count>0){ next-count++; signal(x-sem); wait(next); next-count--; }

OperatingSystemConceptsMonitorImplementationConditional-waitconstruct:x.wait(c);c–integerexpressionthatisevaluatedwhenthewaitoperationisexecuted.valueofc(aprioritynumber)storedwiththenameoftheprocessthatissuspended.whenx.signalisexecuted,processwithsmallestassociatedprioritynumberisresumednext.OperatingSystemConceptsMonitorImplementation(cont.)Checktwoconditionstoestablishcorrectnessofsystem:系统建立正确性要检查2个条件：Userprocessesmustalwaysmaketheircallsonthemonitorinacorrectsequence. 用户进程必须正确的顺序调用管程。Mustensurethatanuncooperativeprocessdoesnotignorethemutual-exclusiongatewayprovidedbythemonitor,andtrytoaccessthesharedresourcedirectly,withoutusingtheaccessprotocols. 必须保证不同步进程不忽略管程提供了的互斥网关，并且试图直接存取共享资源,没有使用存取协议。OperatingSystemConcepts7.8OSSynchronization

操作系统的同步机制7.8.1SynchronizationinSolaris2

Implementsavarietyoflockstosupportmultitasking,multithreading(includingreal-timethreads),andmultiprocessing. 实现各种锁支持多任务、多线程(包括实时线程)、和多进程Usesadaptivemutexesforefficiencywhenprotectingdatafromshortcodesegments.

当保护数据短代码段时，在效率使用可变互斥量Usesconditionvariablesandreaders-writerslockswhenlongersectionsofcodeneedaccesstodata. 当代码的更长部分需要访问到数据时，使用条件变量和读者-写者锁Usesturnstilestoorderthelistofthreadswaitingtoacquireeitheranadaptivemutexorreader-writerlock.

使用turnstiles排列等待需要适应互斥或读者-写者锁的线程列表OperatingSystemConcepts7.8.2Windows2000SynchronizationUsesinterruptmaskstoprotectaccesstoglobalresourcesonuniprocessorsystems.

在单处理机系统上使用中断掩模保护存取全局资源Usesspinlocksonmultiprocessorsystems.

在多处理机系统上使用自旋锁。Providesdispatcherobjectsforthreadsynchronizationoutsideofthekernel.

为内核外线程同步提供调度器对象

。OperatingSystemConceptsWindows2000Synchronization(cont.)Usingadispatcherobjects,athreadcansynchronizeaccordingtoseveraldifferentmechanismsincludemutexes、semaphoresandevent.Aneventactsmuchlikeaconditionvariable. 使用一个调度器对象,一个线程能根据不同的机制包括互斥、信号量和事件而同步。一个事件类似一个条件变量。Dispatcherobjectsmaybeineitherasignaledornonsignaledstate. 调度器对象可以在任何一个signaled可用或nonsignaled不可用状态。OperatingSystemConceptsWindows2000/XP的进程互斥和同步返回对象状态可分成可用和不可用两种。对象可用(signaledstate)表示该对象不被任何线程使用或所有；而对象不可用(nonsignaledstate)表示该对象被某线程使用。对象名称是由用户给出的字符串。不同进程中用同样的名称来创建或打开对象，从而获得该对象在本进程的句柄。在Windows2000/XP中提供了互斥对象、信号量对象和事件对象等三种同步对象和相应的系统调用，用于进程和线程同步。从本质上讲，这组同步对象的功能是相同的，它们的区别在于适用场合和效率会