伯克利操作系统课件lec03synchronization

CS162

OperatingSystemsand

SystemsProgramming

Lecture3

ConcurrencyandThreadDispatchingSeptember11,2013AnthonyD.JosephandJohnCanny/~cs162GoalsforTodayReview:ProcessesandThreadsThreadDispatchingCooperatingThreadsConcurrencyexamplesNote:Someslidesand/orpicturesinthefollowingareadaptedfromslides©2005Silberschatz,Galvin,andGagne.SlidescourtesyofAnthonyD.Joseph,JohnKubiatowicz,AJShankar,GeorgeNecula,AlexAiken,EricBrewer,RasBodik,IonStoica,DougTygar,andDavidWagner.WhyProcesses&Threads?Multiprogramming:RunmultipleapplicationsconcurrentlyProtection:Don’twantabadapplicationtocrashsystem!Goals:Process:unitofexecutionandallocationVirtualMachineabstraction:giveprocessillusionitownsmachine(i.e.,CPU,Memory,andIOdevicemultiplexing)Solution:Processcreation&switchingexpensiveNeedconcurrencywithinsameapp(e.g.,webserver)Challenge:Thread:DecoupleallocationandexecutionRunmultiplethreadswithinsameprocessSolution:Puttingittogether:ProcessMemoryI/OState(e.g.,file,socketcontexts)CPUstate(PC,SP,registers..)SequentialstreamofinstructionsA(inttmp){if(tmp<2)B();printf(tmp);}B(){C();}C(){A(2);}A(1);…(Unix)ProcessResourcesStackStoredinOSPuttingittogether:Processes…Process1Process2ProcessNCPUsched.OSCPU(1core)1processatatimeCPUstateIOstateMem.CPUstateIOstateMem.CPUstateIOstateMem.Switchoverhead:highCPUstate:lowMemory/IOstate:highProcesscreation:highProtectionCPU:yesMemory/IO:yesSharingoverhead:high(involvesatleastacontextswitch)Puttingittogether:ThreadsProcess1CPUsched.OSCPU(1core)1threadatatimeIOstateMem.…threadsProcessNIOstateMem.…threads…Switchoverhead:low

(onlyCPUstate)Threadcreation:lowProtectionCPU:yesMemory/IO:NoSharingoverhead:low(threadswitchoverheadlow)CPUstateCPUstateCPUstateCPUstatePuttingittogether:Multi-CoresProcess1CPUsched.OSIOstateMem.…threadsProcessNIOstateMem.…threads…Switchoverhead:low

(onlyCPUstate)Threadcreation:lowProtectionCPU:yesMemory/IO:NoSharingoverhead:low(threadswitchoverheadlow)core1Core2Core3Core4CPU4threadsatatimeCPUstateCPUstateCPUstateCPUstatePuttingittogether:Hyper-ThreadingProcess1CPUsched.OSIOstateMem.…threadsProcessNIOstateMem.…threads…Switchoverheadbetweenhardware-threads:very-low

(doneinhardware)ContentionforALUs/FPUsmayhurtperformancecore1CPUcore2core3core48threadsatatimehardware-threads(hyperthreading)CPUstateCPUstateCPUstateCPUstateClassificationRealoperatingsystemshaveeitherOneormanyaddressspacesOneormanythreadsperaddressspaceMach,OS/2,LinuxWinNTto8,Solaris,HP-UX,OSXEmbeddedsystems(Geoworks,VxWorks,JavaOS,etc)JavaOS,Pilot(PC)TraditionalUNIXMS/DOS,earlyMacintoshManyOne#threadsperAS:ManyOne#ofaddrspaces:ThreadStateStatesharedbyallthreadsinprocess/addrspaceContentofmemory(globalvariables,heap)I/Ostate(filesystem,networkconnections,etc)State“private”toeachthreadKeptinTCBThreadControlBlockCPUregisters(including,programcounter)Executionstack–whatisthis?ExecutionStackParameters,temporaryvariablesReturnPCsarekeptwhilecalledproceduresareexecutingReview:ExecutionStackExampleStackholdsfunctionarguments,returnaddressPermitsrecursiveexecutionCrucialtomodernlanguagesA(inttmp){if(tmp<2)B();printf(tmp);}B(){C();}C(){A(2);}A(1);exit;addrX:addrY:addrU:addrV:addrZ:............Review:ExecutionStackExampleStackholdsfunctionarguments,returnaddressPermitsrecursiveexecutionCrucialtomodernlanguagesA(inttmp){if(tmp<2)B();printf(tmp);}B(){C();}C(){A(2);}A(1);exit;StackPointerStackGrowthA:tmp=1ret=addrZaddrX:addrY:addrU:addrV:addrZ:............Review:ExecutionStackExampleStackholdsfunctionarguments,returnaddressPermitsrecursiveexecutionCrucialtomodernlanguagesA(inttmp){if(tmp<2)B();printf(tmp);}B(){C();}C(){A(2);}A(1);exit;StackPointerStackGrowthA:tmp=1ret=addrZaddrX:addrY:addrU:addrV:addrZ:............Review:ExecutionStackExampleStackholdsfunctionarguments,returnaddressPermitsrecursiveexecutionCrucialtomodernlanguagesA(inttmp){if(tmp<2)B();printf(tmp);}B(){C();}C(){A(2);}A(1);exit;StackPointerStackGrowthA:tmp=1ret=addrZaddrX:addrY:addrU:addrV:addrZ:............Review:ExecutionStackExampleStackholdsfunctionarguments,returnaddressPermitsrecursiveexecutionCrucialtomodernlanguagesA(inttmp){if(tmp<2)B();printf(tmp);}B(){C();}C(){A(2);}A(1);exit;StackPointerStackGrowthA:tmp=1ret=addrZB:ret=addrYaddrX:addrY:addrU:addrV:addrZ:............Review:ExecutionStackExampleStackholdsfunctionarguments,returnaddressPermitsrecursiveexecutionCrucialtomodernlanguagesA(inttmp){if(tmp<2)B();printf(tmp);}B(){C();}C(){A(2);}A(1);exit;StackPointerStackGrowthA:tmp=1ret=addrZB:ret=addrYaddrX:addrY:addrU:addrV:addrZ:............Review:ExecutionStackExampleStackholdsfunctionarguments,returnaddressPermitsrecursiveexecutionCrucialtomodernlanguagesA(inttmp){if(tmp<2)B();printf(tmp);}B(){C();}C(){A(2);}A(1);exit;StackPointerStackGrowthA:tmp=1ret=addrZB:ret=addrYC:ret=addrUaddrX:addrY:addrU:addrV:addrZ:............Review:ExecutionStackExampleStackholdsfunctionarguments,returnaddressPermitsrecursiveexecutionCrucialtomodernlanguagesA(inttmp){if(tmp<2)B();printf(tmp);}B(){C();}C(){A(2);}A(1);exit;StackPointerStackGrowthA:tmp=1ret=addrZB:ret=addrYC:ret=addrUaddrX:addrY:addrU:addrV:addrZ:............Review:ExecutionStackExampleStackholdsfunctionarguments,returnaddressPermitsrecursiveexecutionCrucialtomodernlanguagesA(inttmp){if(tmp<2)B();printf(tmp);}B(){C();}C(){A(2);}A(1);exit;A:tmp=2ret=addrVStackPointerStackGrowthA:tmp=1ret=addrZB:ret=addrYC:ret=addrUaddrX:addrY:addrU:addrV:addrZ:............Review:ExecutionStackExampleStackholdsfunctionarguments,returnaddressPermitsrecursiveexecutionCrucialtomodernlanguagesA(inttmp){if(tmp<2)B();printf(tmp);}B(){C();}C(){A(2);}A(1);exit;A:tmp=2ret=addrVStackPointerStackGrowthA:tmp=1ret=addrZB:ret=addrYC:ret=addrUaddrX:addrY:addrU:addrV:addrZ:............Review:ExecutionStackExampleA(inttmp){if(tmp<2)B();printf(tmp);}B(){C();}C(){A(2);}A(1);exit;A:tmp=2ret=addrVStackPointerStackGrowthA:tmp=1ret=addrZB:ret=addrYC:ret=addrUaddrX:addrY:addrU:addrV:addrZ:............Output:2Review:ExecutionStackExampleA(inttmp){if(tmp<2)B();printf(tmp);}B(){C();}C(){A(2);}A(1);exit;StackPointerStackGrowthA:tmp=1ret=addrZB:ret=addrYC:ret=addrUaddrX:addrY:addrU:addrV:addrZ:............Output:2Review:ExecutionStackExampleA(inttmp){if(tmp<2)B();printf(tmp);}B(){C();}C(){A(2);}A(1);exit;StackPointerStackGrowthA:tmp=1ret=addrZB:ret=addrYaddrX:addrY:addrU:addrV:addrZ:............Output:2Review:ExecutionStackExampleA(inttmp){if(tmp<2)B();printf(tmp);}B(){C();}C(){A(2);}A(1);exit;StackPointerStackGrowthA:tmp=1ret=addrZaddrX:addrY:addrU:addrV:addrZ:............Output:21Review:ExecutionStackExampleA(inttmp){if(tmp<2)B();printf(tmp);}B(){C();}C(){A(2);}A(1);exit;addrX:addrY:addrU:addrV:addrZ:............Output:21Single-ThreadedExampleImaginethefollowingCprogram:

main(){ ComputePI(“pi.txt”); PrintClassList(“clist.text”); }Whatisthebehaviorhere?ProgramwouldneverprintoutclasslistWhy?ComputePIwouldneverfinishUseofThreadsVersionofprogramwithThreads:

main(){ CreateThread(ComputePI(“pi.txt”)); CreateThread(PrintClassList(“clist.text”)); }Whatdoes“CreateThread”do?StartindependentthreadrunninggivenprocedureWhatisthebehaviorhere?Now,youwouldactuallyseetheclasslistThisshouldbehaveasiftherearetwoseparateCPUsCPU1CPU2CPU1CPU2TimeCPU1CPU2MemoryFootprintofTwo-ThreadExampleIfwestoppedthisprogramandexamineditwithadebugger,wewouldseeTwosetsofCPUregistersTwosetsofStacksQuestions:Howdowepositionstacksrelativeto

eachother?Whatmaximumsizeshouldwechoose

forthestacks?Whathappensifthreadsviolatethis?Howmightyoucatchviolations?CodeGlobalDataHeapStack1Stack2AddressSpacePerThreadStateEachThreadhasaThreadControlBlock(TCB)ExecutionState:CPUregisters,programcounter(PC),pointertostack(SP)Schedulinginfo:state,priority,CPUtimeVariousPointers(forimplementingschedulingqueues)Pointertoenclosingprocess(PCB)Etc(addstuffasyoufindaneed)OSKeepstrackofTCBsinprotectedmemoryInArray,orLinkedList,or…LifecycleofaThread(orProcess)Asathreadexecutes,itchangesstate:new:Thethreadisbeingcreatedready:Thethreadiswaitingtorunrunning:Instructionsarebeingexecutedwaiting:Threadwaitingforsomeeventtooccurterminated:Thethreadhasfinishedexecution“Active”threadsarerepresentedbytheirTCBsTCBsorganizedintoqueuesbasedontheirstateReadyQueueAndVariousI/ODeviceQueuesThreadnotrunningTCBisinsomeschedulerqueueSeparatequeueforeachdevice/signal/conditionEachqueuecanhaveadifferentschedulerpolicyOtherStateTCB9LinkRegistersOtherStateTCB6LinkRegistersOtherStateTCB16LinkRegistersOtherStateTCB8LinkRegistersOtherStateTCB2LinkRegistersOtherStateTCB3LinkRegistersHeadTailHeadTailHeadTailHeadTailHeadTailReadyQueueSSDUnit0DiskUnit0DiskUnit2EtherNetwk0Administrivia:ProjectSignupProjectSignup:Use“Group/SectionSignup”Link4-5memberstoagroup,everyonemustattendthesamesectionUsePiazzapinnedteammatesearchthread(pleaseclosewhendone!)Onlysubmitoncepergroup!DueThu(1/31)by11:59PMEveryoneingroupmusthaveloggedintotheircs162-xxaccountsoncebeforeyouregisterthegroup,Selectatleast3potentialsectionsNewsectionassignments:Watch“Group/SectionAssignment”LinkAttendnewsectionsNEXTweekSectionTimeLocationTA101Tu10:00A-11:00A6EvansDavid102Tu11:00A-12:00P75EvansDavid103Tu1:00P-2:00P75EvansNeeraja104Tu3:00P-4:00P2070VLSBDaniel105Tu11:00A-12:00P3105EtcheverryDaniel106Tu1:00P-2:00P385LeConteWesley107Tu2:00P-3:00P71EvansNeeraja108Tu6:00P-7:00P71EvansWesleyAdministrivia:ProjectSignupProjectSignup:Use“Group/SectionSignup”Link4-5memberstoagroup,everyonemustattendthesamesectionUsePiazzapinnedteammatesearchthread(pleaseclosewhendone!)Onlysubmitoncepergroup!DueThu(9/12)by11:59PMEveryoneingroupmusthaveloggedintotheircs162-xxaccountsoncebeforeyouregisterthegroup,Selectatleast3potentialsectionsNewsectionassignments:Watch“Group/SectionAssignment”LinkAttendnewsectionsNEXTweekSectionTimeLocationTA101Tu9:00A-10:00A310SodaMatt102Tu10:00A-11:00A75EvansMatt103Tu11:00A-12:00P71EvansGeorge104Tu3:00P-4:00P24WheelerGeorge105We10:00A-11:00A85EvansKevin106We11:00A-12:00P85EvansKevin107TBATBATBA108TBATBATBA5minBreakDispatchLoopConceptually,thedispatchingloopoftheoperatingsystemlooksasfollows:

Loop{ RunThread(); ChooseNextThread(); SaveStateOfCPU(curTCB); LoadStateOfCPU(newTCB); }ThisisaninfiniteloopOnecouldarguethatthisisallthattheOSdoesRunningathreadConsiderfirstportion:RunThread()HowdoIrunathread?Loaditsstate(registers,stackpointer)intoCPULoadenvironment(virtualmemoryspace,etc)JumptothePCHowdoesthedispatchergetcontrolback?Internalevents:threadreturnscontrolvoluntarilyExternalevents:threadgetspreemptedYieldingthroughInternalEventsBlockingonI/OTheactofrequestingI/OimplicitlyyieldstheCPUWaitingona“signal”fromotherthreadThreadaskstowaitandthusyieldstheCPUThreadexecutesayield()ThreadvolunteerstogiveupCPU computePI(){while(TRUE){ComputeNextDigit();yield();}}Notethatyield()mustbecalledbyprogrammerfrequentlyenough!Review:StackforYieldingThreadHowdowerunanewthread?

run_new_thread(){ newThread=PickNewThread(); switch(curThread,newThread); ThreadHouseKeeping();/*deallocatesfinishedthreads*/ }Finishedthreadnotkilledrightaway.Why?Movethemin“exit/terminated”stateThreadHouseKeeping()deallocatesfinishedthreadsyieldComputePIStackgrowthrun_new_threadkernel_yieldTraptoOSswitchReview:StackforYieldingThreadHowdowerunanewthread?

run_new_thread(){ newThread=PickNewThread(); switch(curThread,newThread); ThreadHouseKeeping();/*deallocatesfinishedthreads*/ }Howdoesdispatcherswitchtoanewthread?Saveanythingnextthreadmaytrash:PC,regs,SPMaintainisolationforeachthreadyieldComputePIStackgrowthrun_new_threadkernel_yieldTraptoOSswitchReview:TwoThreadYieldExampleConsiderthefollowingcodeblocks:

procA(){ B(); } procB(){ while(TRUE){ yield(); } }Supposewehavetwothreads:ThreadsSandTThreadSStackgrowthAB(while)yieldrun_new_threadswitchkernel_yieldThreadTAB(while)yieldrun_new_threadswitchkernel_yieldDetour:InterruptControllerInterruptsinvokedwithinterruptlinesfromdevicesInterruptcontrollerchoosesinterruptrequesttohonorMaskenables/disablesinterruptsPriorityencoderpickshighestenabledinterruptSoftwareInterruptSet/ClearedbySoftwareInterruptidentityspecifiedwithIDlineCPUcandisableallinterruptswithinternalflagNon-maskableinterruptline(NMI)can’tbedisabledNetworkIntIDInterruptInterruptMaskControlSoftwareInterruptNMICPUPriorityEncoderTimerIntDisableReview:PreemptiveMultithreadingUsethetimerinterrupttoforceschedulingdecisionsTimerInterruptroutine:

TimerInterrupt(){

DoPeriodicHouseKeeping();

run_new_thread();

}Thisisoftencalledpreemptivemultithreading,sincethreadsarepreemptedforbetterschedulingSolvesproblemofuserwhodoesn’tinsertyield();SomeRoutinerun_new_threadTimerInterruptInterruptswitchStackgrowthWhyallowcooperatingthreads?Peoplecooperate;computershelp/enhancepeople’slives,socomputersmustcooperateByanalogy,thenon-reproducibility/non-determinismofpeopleisanotableproblemfor“carefullylaidplans”Advantage1:ShareresourcesOnecomputer,manyusersOnebankbalance,manyATMsWhatifATMswereonlyupdatedatnight?Embeddedsystems(robotcontrol:coordinatearm&hand)Advantage2:SpeedupOverlapI/OandcomputationMultiprocessors–chopupprogramintoparallelpiecesAdvantage3:ModularityChoplargeproblemupintosimplerpiecesTocompile,forinstance,gcccallscpp|cc1|cc2|as|ldMakessystemeasiertoextendThreadedWebServerMultithreadedversion:serverLoop(){ connection=AcceptCon(); ThreadCreate(ServiceWebPage(),connection); }Advantagesofthreadedversion:Cansharefilecacheskeptinmemory,resultsofCGIscripts,otherthingsThreadsaremuchcheapertocreatethanprocesses,sothishasalowerper-requestoverheadWhatiftoomanyrequestscomeinatonce?ThreadPoolsProblemwithpreviousversion:UnboundedThreadsWhenweb-sitebecomestoopopular–throughputsinksInstead,allocateabounded“pool”ofthreads,representingthemaximumlevelofmultiprogramming

master(){

allocThreads(slave,queue);

while(TRUE){

con=AcceptCon();

Enqueue(queue,con);

wakeUp(queue);

}

}slave(queue){

while(TRUE){

con=Dequeue(queue);

if(con==null)

sleepOn(queue);

else

ServiceWebPage(con);

}

}MasterThreadThreadPoolqueueATMBankServerATMserverproblem:ServiceasetofrequestsDosowithoutcorruptingdatabaseDon’thandouttoomuchmoneyATMbankserverexampleSupposewewantedtoimplementaserverprocesstohandlerequestsfromanATMnetwork:

BankServer(){

while(TRUE){

ReceiveRequest(&op,&acctId,&amount);

ProcessRequest(op,acctId,amount);

}

} ProcessRequest(op,acctId,amount){

if(op==deposit)Deposit(acctId,amount);

elseif…

} Deposit(acctId,amount){

acct=GetAccount(acctId);/*mayusediskI/O*/

acct->balance+=amount;

StoreAccount(acct);/*InvolvesdiskI/O*/

}Howcouldwespeedthisup?MorethanonerequestbeingprocessedatonceMultiplethreads(multi-proc,oroverlapcompandI/O)CanThreadsHelp?Onethreadperrequest!Requestsproceedstocompletion,blockingasrequired:

Deposit(acctId,amount){

acct=GetAccount(actId); /*MayusediskI/O*/

acct->balance+=amount;

StoreAccount(acct); /*InvolvesdiskI/O*/

}Unfortunately,sharedstatecangetcorrupted:

Thread1

Thread2

loadr1,acct->balance

loadr1,acct->balance

addr1,amount2

storer1,acct->balance

addr1,amount1

storer1,acct->balance

Problemisatthe