操作系統(tǒng)教學(xué)課件：Chapter 7 Process Synchronization

Chapter7:ProcessSynchronizationBackground背景TheCritical-SectionProblem臨界區(qū)的問題SynchronizationHardware同步硬件Semaphores信號(hào)量ClassicalProblemsofSynchronization同步的經(jīng)典問題CriticalRegions臨界區(qū)Monitors管程Background不是一個(gè)人在戰(zhàn)斗，關(guān)鍵區(qū)域只能一個(gè)人戰(zhàn)斗Concurrentaccesstoshareddatamayresultindatainconsistency.對(duì)共享數(shù)據(jù)區(qū)的并發(fā)訪問導(dǎo)致數(shù)據(jù)的不一致性Maintainingdataconsistencyrequiresmechanismstoensuretheorderlyexecutionofcooperatingprocesses.維持?jǐn)?shù)據(jù)的一致性要求保證合作進(jìn)程按一定的順序執(zhí)行的機(jī)制。Shared-memorysolutiontobounded-bufferproblem(Chapter4)allowsatmostn–1itemsinbufferatthesametime.Asolution,whereallNbuffersareusedisnotsimple.Supposethatwemodifytheproducer-consumercodebyaddingavariable

counter,initializedto0andincrementedeachtimeanewitemisaddedtothebufferBackground進(jìn)程的同步隱含了系統(tǒng)中并發(fā)進(jìn)程之間存在的兩種相互制約關(guān)系：競(jìng)爭(zhēng)（互斥）與協(xié)作（同步）互斥：兩個(gè)并行的進(jìn)程A、B，如果當(dāng)A進(jìn)行某個(gè)操作時(shí)，B不能做這一操作，進(jìn)程間的這種限制條件稱為進(jìn)程互斥，這是引起資源不可共享的原因。同步：我們把進(jìn)程間的這種必須互相合作的協(xié)同工作關(guān)系，稱為進(jìn)程同步。進(jìn)程之間的互斥是由于共享系統(tǒng)資源而引起的一種間接制約關(guān)系進(jìn)程之間的同步是并發(fā)進(jìn)程由于要協(xié)作完成同一個(gè)任務(wù)而引起的一種直接制約關(guān)系如果無(wú)進(jìn)程在使用共享資源時(shí)，可允許任何一個(gè)進(jìn)程去使用共享資源（即使某個(gè)進(jìn)程剛用過(guò)也允許再次使用），這是通過(guò)進(jìn)程互斥的方式來(lái)管理共享資源如果某個(gè)進(jìn)程通過(guò)共享資源得到指定消息時(shí)，在指定消息未到達(dá)之前，即使無(wú)進(jìn)程在共享資源仍不允許該進(jìn)程去使用共享資源，這是通過(guò)采用進(jìn)程同步的方式來(lái)管理共享資源。Bounded-BufferShareddata

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

itemnextProduced;

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

counter++; }Bounded-BufferConsumerprocess

itemnextConsumed;

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

counter--; }

BoundedBufferThestatements

counter++;

counter--;

mustbeperformedatomically.Atomicoperation（原子操作）meansanoperationthatcompletesinitsentiretywithoutinterruption.

BoundedBufferThestatement“count++”maybeimplementedinmachinelanguageas:

register1=counter register1=register1+1

counter=register1

Thestatement“count--”maybeimplementedas:

register2=counter

register2=register2–1

counter=register2BoundedBufferIfboththeproducerandconsumerattempttoupdatethebufferconcurrently,theassemblylanguagestatementsmaygetinterleaved.Interleavingdependsuponhowtheproducerandconsumerprocessesarescheduled.BoundedBufferAssumecounterisinitially5.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.RaceCondition

競(jìng)爭(zhēng)條件Racecondition:Thesituationwhereseveralprocessesaccess–andmanipulateshareddataconcurrently.Thefinalvalueoftheshareddatadependsuponwhichprocessfinisheslast.

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

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

每個(gè)進(jìn)程有一個(gè)代碼段，稱為臨界區(qū)，訪問共享數(shù)據(jù)的代碼都在臨界區(qū)中。Problem–ensurethatwhenoneprocessisexecutinginitscriticalsection,nootherprocessisallowedtoexecuteinitscriticalsection.問題-確保當(dāng)一個(gè)進(jìn)程在臨界區(qū)中時(shí)，沒有其它進(jìn)程在臨界區(qū)中。你方唱罷我登場(chǎng)臨界區(qū)問題進(jìn)程結(jié)構(gòu)進(jìn)程的一般結(jié)構(gòu)

do{

entrysection

criticalsection

exitsection

remindersection }while(1);SolutiontoCritical-SectionProblem

臨界區(qū)問題的解決方案-滿足三個(gè)條件MutualExclusion(互斥條件)：IfprocessPiisexecutinginitsCS,thennootherprocessescanbeexecutingintheirCSs.Progress(進(jìn)入條件)：IfnoprocessisexecutinginitsCSandsomeprocesseswishtoentertheirCSs,thenonlythoseprocessesthatarenotexecutingintheirRSscanparticipateinthedecisiononwhichwillenteritsCSnext,andthisselectioncannotbepostponedindefinitely.BoundedWaiting(有限等待的條件)：Thereexistsabound,orlimit,onthenumberoftimesthatotherprocessesareallowedtoentertheirCSaafteraprocesshasmadearequesttoenteritsCSandbeforethatrequestisgranted.Assumethateachprocessexecutesatanonzerospeed.Noassumptionconcerningrelativespeedofthenprocesses.InitialAttemptstoSolveProblem

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

(otherprocessPj,j=1-i)

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

do{

entrysection criticalsection

exitsection remindersection }while(1);Processesmaysharesomecommonvariablestosynchronizetheiractions.進(jìn)程通過(guò)共享一些變量來(lái)同步它們的行為。Algorithm1Sharedvariables:intturn;

initiallyturn=0turn=i

PicanenteritscriticalsectionProcessPi

do{

while(turn!=i); criticalsection

turn=j; remindersection }while(1);Satisfiesmutualexclusion,butnotprogress兩進(jìn)程需嚴(yán)格按順序交替執(zhí)行，一個(gè)進(jìn)程在RS就可能使另一個(gè)進(jìn)程不能進(jìn)其CSAlgorithm2Sharedvariablesbooleanflag[2];

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

PireadytoenteritscriticalsectionProcessPi

do{ while(flag[j]);flag[i]=true;

criticalsection flag[i]=false;

remaindersection }while(1);Satisfiesmutualexclusion,butnotprogressrequirement.兩進(jìn)程需嚴(yán)格按一定時(shí)序運(yùn)行，否則可能在ES無(wú)限等待而沒有進(jìn)程能進(jìn)入其CSAlgorithm3Combinedsharedvariablesofalgorithms1and2.ProcessPi

do{

flag[i]=true;

turn=j;

while(flag[j]&&turn=j); criticalsection

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

面包師算法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ū)算法BakeryAlgorithm

面包師算法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];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);SynchronizationHardwareTestandmodifythecontentofawordatomically

.

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

booleanlock=false;

ProcessPi

do{ while(TestAndSet(lock));

criticalsection lock=false;

remaindersection }SynchronizationHardwareAtomicallyswaptwovariables.

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

booleanlock; booleanwaiting[n];

ProcessPi

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

criticalsection lock=false;

remaindersection }SemaphoresSynchronizationtoolthatdoesnotrequirebusywaiting.SemaphoreS

–integervariablecanonlybeaccessedviatwoindivisible(atomic)operations

wait(S):

whileS0dono-op;

S--;

signal(S):

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

ProcessPi:

do{

wait(mutex);

criticalsection signal(mutex);

remaindersection

}while(1);

SemaphoreImplementation能不能聰明一點(diǎn)？Defineasemaphoreasarecord

typedefstruct{ intvalue;

structprocess*L;

}semaphore;

Assumetwosimpleoperations:blocksuspendstheprocessthatinvokesit.wakeup(P)resumestheexecutionofablockedprocessP.ImplementationSemaphoreoperationsnowdefinedas

wait(S):

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

addthisprocesstoS.L;

block; }

signal(S):

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

removeaprocessPfromS.L;

wakeup(P); }SemaphoreasaGeneralSynchronizationToolExecuteBinPjonlyafterAexecutedinPiUsesemaphoreflaginitializedto0Code: Pi Pj

A

wait(flag)

signal(flag) BDeadlockandStarvationDeadlock（死鎖）

–twoormoreprocessesarewaitingindefinitelyforaneventthatcanbecausedbyonlyoneofthewaitingprocesses.LetSandQbetwosemaphoresinitializedto1

P0

P1

wait(S); wait(Q);

wait(Q); wait(S);

signal(S); signal(Q);

signal(Q) signal(S);Starvation（餓死）

–indefiniteblocking.Aprocessmayneverberemovedfromthesemaphorequeueinwhichitissuspended.TwoTypesofSemaphoresCountingsemaphore（計(jì)數(shù)信號(hào)量）

–integervaluecanrangeoveranunrestricteddomain.Binarysemaphore（二元信號(hào)量）

–integervaluecanrangeonlybetween0and1;canbesimplertoimplement.CanimplementacountingsemaphoreSasabinarysemaphore.ClassicalProblemsofSynchronizationBounded-BufferProblem（有界緩存）

ReadersandWritersProblem（讀者-寫者）

Dining-PhilosophersProblem（哲學(xué)家就餐）Bounded-BufferProblemShareddata

semaphorefull,empty,mutex;

Initially:

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

do{

…

produceaniteminnextp

… wait(empty); wait(mutex);

…

addnextptobuffer

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

Bounded-BufferProblemConsumerProcess

do{ wait(full) wait(mutex);

…

removeanitemfrombuffertonextc

… signal(mutex); signal(empty);

…

consumetheiteminnextc

… }while(1);Readers-WritersProblemShareddata

semaphoremutex,wrt;

Initially

mutex=1,wrt=1,readcount=0

Readers-WritersProblemWriterProcess

wait(rd);

wait(wrt);

…

writingisperformed

… signal(wrt);

signal(rd);Readers-WritersProblemReaderProcess

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

… readingisperformed

…

wait(mutex); readcount--; if(readcount==0) signal(wrt); signal(mutex):Readers-WritersProblemWriter正在寫時(shí)，第一個(gè)reader等待writer，其他readers等待第一個(gè)reader只要有readers，writer必須等Writers必須等writer（有writer正在writing）和readers（有readers正在reading）思考：能讓寫者優(yōu)先嗎？能讓兩者公平嗎？Dining-PhilosophersProblemShareddata

semaphorechopstick[5];Initiallyallvaluesare1Dining-PhilosophersProblem（1）Philosopheri:

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

…

eat

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

…

think

… }while(1);Dining-PhilosophersProblem（2）Starvation？Howtodealwith？AboutsynchronizationRaceconditionMustkeepcorrecttimingsequencesUserUsuallytimingerrorsNeedplaytrickbadOsSemaphoreBetterBut，wronguseofsemaphoresresultingintimingerrorsAboutsynchronization(1)Howtodealwitherrorslistedabove？HighlevelsynchronizationconstructmonitorSignal(mutex)

…CSWait(mutex)Nomutualexclusionwait(mutex)

…Wait(mutex)DeadlockMonitorsAmonitorischaracterizedbyasetofprogrammer-definedoperators.Monitor確保一次只有一個(gè)進(jìn)程在monitor內(nèi)活躍。

monitormonitor-name

{ //sharedvariabledeclarations

procedurebody

P1

(…){ ... }

procedure

body

P2(…){ ... }

procedurebody

Pn

(…){ ... } initializationcode(…){

…

} }Monitors如何保證？條件變量Toallowaprocesstowaitwithinthemonitor,aconditionvariablemustbedeclared,as

conditionx,y;Conditionvariablecanonlybeusedwiththeoperationswaitandsignal.Theoperation

x.wait();

meansthattheprocessinvokingthisoperationissuspendeduntilanotherprocessinvokes

x.signal();Thex.signaloperationresumesexactlyonesuspendedprocess.Ifnoprocessissuspended,thenthesignaloperationhasnoeffect. SchematicViewofaMonitorMonitorWithConditionVariablesDiningPhilosophersExample只有同時(shí)拿到左右兩根筷子才能吃

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; } }DiningPhilosophers

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

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

DiningPhilosophersphilosopheridp.pickup(i);…eatdp.putdown(i);SynchronizationexamplesSolaris2:adaptivemutex,conditionvariable,semaphore,reader-writerlock,turnstile(十字轉(zhuǎn)門)WindowsXP:Inkernel-maskinterrupt(uniprocessor),spinlock(multiprocessor)Outsidekernel-dispatcherobjectsMutex,semaphore,event,timerLinux2.6:enable/disablepreemption(uniprocessor),spinlock(multiprocessor)PthreadsAPI:mutexlock,conditionvariable,read-writelockAtomicTransactions原子交易CS-你方唱罷我登場(chǎng)MutualexclusionofcriticalsectionsAT-油鹽壇子，公不離婆秤不離砣HowtomakesureacriticalsectionformsasinglelogicunitofworkEitherperformedinitsentiretyOrnotperformedatallTransaction交易Acollectionofinstructions(oroperations)thatperformsasinglelogicalfunctionAmajorissueinprocessingtransactionsisthepreservationofatomicitydespitethepossibilityoffailureswithinthecomputersystemAsequenceofreadandwriteoperations,terminatedbyacommitorabortoperationAtomicTransactions(1)Commit提交TheeffectofacommittedtransactioncannotbeundonebyabortionofthetransactionAbort終止AnabortedtransactionmusthavenoeffectonthestateofthedataithasalreadymodifiedThestateofthedataaccessedbyanabortedtransactionmustberestoredtowhatitwasjustbeforethetransactionstartedexecuting.如何恢復(fù)？存儲(chǔ)信息。怎么存儲(chǔ)？Torecordonstablestorage,informationdescribingallthemodificationsmadebythetransactiontothevariousdataitaccessedHowtorecordLog-basedrecoveryTransactionnameDataitemnameOldvalueNewvalueCheckpointsToreducethesearchingoverheadConcurrentatomictransactionsSerializabilityLockingprotocolTimestamp-basedprotocolsSummary進(jìn)程的同步隱含了系統(tǒng)中并發(fā)進(jìn)程之間存在的兩種相互制約關(guān)系：競(jìng)爭(zhēng)（互斥）與協(xié)作（同步）互斥：兩個(gè)并行的進(jìn)程A、B，如果當(dāng)A進(jìn)行某個(gè)操作時(shí)，B不能做這一操作，進(jìn)程間的這種限制條件稱為進(jìn)程互斥，這是引起資源不可共享的原因。同步：我們把進(jìn)程間的這種必須互相合作的協(xié)同工作關(guān)系，稱為進(jìn)程同步。進(jìn)程之間的互斥是由于共享系統(tǒng)資源而引起的一種間接制約關(guān)系進(jìn)程之間的同步是并發(fā)進(jìn)程由于要協(xié)作完成同一個(gè)任務(wù)而引起的一種直接制約關(guān)系如果無(wú)進(jìn)程在使用共享資源時(shí)，可允許任何一個(gè)進(jìn)程去使用共享資源（即使某個(gè)進(jìn)程剛用過(guò)也允許再次使用），這是通過(guò)進(jìn)程互斥的方式來(lái)管理共享資源如果某個(gè)進(jìn)程通過(guò)共享資源得到指定消息時(shí)，在指定消息未到達(dá)之前，即使無(wú)進(jìn)程在共享資源仍不允許該進(jìn)程去使用共享資源，這是通過(guò)采用進(jìn)程同步的方式來(lái)管理共享資源。臨界資源：一些被共享的資源，具有一次僅允許一個(gè)進(jìn)程使用的特點(diǎn)臨界區(qū)：并發(fā)進(jìn)程訪問臨界資源的那段必須互斥執(zhí)行的程序?qū)崿F(xiàn)臨界區(qū)互斥一個(gè)遵循的準(zhǔn)則有空讓進(jìn)，臨界區(qū)空閑時(shí)，允許一個(gè)進(jìn)程進(jìn)入執(zhí)行無(wú)空等待，有進(jìn)程在臨界區(qū)執(zhí)行時(shí)，要進(jìn)入的進(jìn)程必須等待讓權(quán)等待，有進(jìn)程在臨界區(qū)執(zhí)行時(shí)，要求進(jìn)入的進(jìn)程必須立即釋放CPU而等待有限等待，不應(yīng)該使進(jìn)入臨界區(qū)的進(jìn)程無(wú)限期地等待在臨界區(qū)之外信號(hào)量及p、v操作經(jīng)典同步問題原子交易作業(yè)1.Thefirstknowncorrectsoftwaresolutiontothecritical-sectionproblemfortwothreadswasdevelopedbyDekker.Thetwothreads,T0andT1,sharethefollowingvariables:Booleanflag[2];/*initiallyfalse*/intturn;ThestructureofthreadTi(i=0or1),withTj(j=1or0)beingtheotherthread,isshownas:

do{ flag[i]=true;

while(flag[j]){if(turn==j){flag[i]=false;while(turn==j);flag[i]=true;}} criticalsectionturn=j; flag[i]=false; remaindersection }while(1);Provethatthealgorithmsatisfiesallthreerequirementsforthecritical-sectionproblem.7-cont.2.Thefirstknowncorrectsoftwaresolutiontothecritical-sectionproblemfornprocesseswithalowerboundonwaitingofn-1turnswaspresentedbyEisenbergandMcGuire.Theprocessessharethefollowingvariables:

enumpstatefidle,wantin,incsg;pstateflag[n];intturn;Alltheelementsofflagareinitiallyidle;theinitialvalueofturnisimmaterial(between0andn-1).ThestructureofprocessPiisshownas:Provethatthealgorithmsatisfiesallthreerequirementsforthecritical-sectionproblem.7-cont.3.Showthat,ifthewaitandsignaloperationsarenotexecutedatomically,the