伯克利操作系统课件lec02concurency

CS162

OperatingSystemsand

SystemsProgramming

Lecture2

Concurrency:

Processes,Threads,andAddressSpacesSeptember9,2013AnthonyD.JosephandJohnCanny/~cs162VirtualMachines(Recap)SoftwareemulationofanabstractmachineGiveprogramsillusiontheyownthemachineMakeitlooklikehardwarehasfeaturesyouwantTwotypesofVMsSystemVM:supportstheexecutionofanentireOSanditsapplications(e.g.,VMWareFusion,ParallelsDesktop,Xen)ProcessVM:supportstheexecutionofasingleprogram;thisfunctionalityistypicallyprovidedbyOSSystemVMs:LayersofOSs(Recap)UsefulforOSdevelopmentWhenOScrashes,restrictedtooneVMCanaidtestingprogramsonotherOSsYouwillbeworkingwithNachosSimulationenvironment:Hardware,interrupts,I/OExecutionofUserProgramsrunningonthisplatformSeethe“ProjectsandNachos”linkoffthecoursehomepageNachos:VirtualOSEnvironment(Recap)OperatingSystemRoles(Recap)OSasaTrafficCop:ManagesallresourcesSettlesconflictingrequestsforresourcesPreventerrorsandimproperuseofthecomputerOSasafacilitator(“useful”abstractions):Providesfacilities/servicesthateveryoneneedsStandardlibraries,windowingsystemsMakeapplicationprogrammingeasier,faster,lesserror-proneSomefeaturesreflectbothtasks:Filesystemisneededbyeveryone(Facilitator)……butFilesystemmustbeprotected(TrafficCop)VeryBriefHistoryofOSSeveralDistinctPhases:HardwareExpensive,HumansCheapEniac,…MulticsHardwareCheaper,HumansExpensivePCs,Workstations,RiseofGUIsHardwareReallyCheap,HumansReallyExpensiveUbiquitousdevices,WidespreadnetworkingRapidChangeinHardwareLeadstochangingOSBatchMultiprogrammingTimesharingGraphicalUIUbiquitousDevicesGradualMigrationofFeaturesintoSmallerMachinesSituationtodayismuchlikethelate60sSmallOS:100Klines/Large:10Mlines(5Mbrowser!)100-1000people-yearsMigrationofOSConceptsandFeaturesGoalsforTodayHowdoweprovidemultiprogramming?Whatareprocesses?Howaretheyrelatedtothreadsandaddressspaces?Note:Someslidesand/orpicturesinthefollowingareadaptedfromslides©2005Silberschatz,Galvin,andGagne.SlidescourtesyofAnthonyD.Joseph,JohnKubiatowicz,AJShankar,GeorgeNecula,AlexAiken,EricBrewer,RasBodik,IonStoica,DougTygar,andDavidWagner.ThreadsUnit(“thread”)ofexecution:IndependentFetch/Decode/ExecuteloopUnitofschedulingOperatinginsomeaddressspaceFetchExecR0…R31F0…F30PC…Data1Data0Inst237Inst236…Inst5Inst4Inst3Inst2

Inst1Inst0Addr0Addr232-1Recall(61C):Whathappensduringexecution?Executionsequence:FetchInstructionatPC

DecodeExecute(possiblyusingregisters)Writeresultstoregisters/memPC=NextInstruction(PC)RepeatPCPCPCPCUniprogramingvs.MultiprogramingUniprogramming:onethreadatatimeMS/DOS,earlyMacintosh,batchprocessingEasierforoperatingsystembuilderGetridofconcurrency(onlyonethreadaccessingresources!)Doesthismakesenseforpersonalcomputers?Multiprogramming:morethanonethreadatatimeMultics,UNIX/Linux,OS/2,WindowsNT–8,MacOSX,Android,iOSOftencalled“multitasking”,butmultitaskinghasothermeanings(talkaboutthislater)ManyCoreMultiprogramming,right?ChallengesofMultiprogramingEachapplicationwantstoownthemachinevirtualmachineabstractionApplicationscompetewitheachotherforresourcesNeedtoarbitrateaccesstosharedresourcesconcurrencyNeedtoprotectapplicationsfromeachotherprotectionApplicationsneedtocommunicate/cooperatewitheachotherconcurrencyProcessesProcess:unitofresourceallocationandexecutionOwnsmemory(addressspace)Ownsfiledescriptors,filesystemcontext,…Encapsulateoneormorethreadssharingprocessresources

Whyprocesses?NavigatefundamentaltradeoffbetweenprotectionandefficiencyProcessesprovidesmemoryprotectionwhilethreadsdon’t(shareaprocessmemory)Threadsmoreefficientthanprocesses(later)ApplicationinstanceconsistsofoneormoreprocessesTheBasicProblemofConcurrencyThebasicproblemofconcurrencyinvolvesresources:Hardware:singleCPU,singleDRAM,singleI/OdevicesMultiprogrammingAPI:processesthinktheyhaveexclusiveaccesstosharedresourcesOShastocoordinateallactivityMultipleprocesses,I/Ointerrupts,…Howcanitkeepallthesethingsstraight?BasicIdea:UseVirtualMachineabstractionSimplemachineabstractionforprocessesMultiplextheseabstractmachinesDijkstradidthisforthe“THEsystem”Fewthousandlinesvs1millionlinesinOS360(1Kbugs)Howcanwegivetheillusionofmultipleprocessors?vCPU3vCPU2vCPU1SharedMemoryAssumeasingleprocessor.Howdoweprovidetheillusionofmultipleprocessors?Multiplexintime!Eachvirtual“CPU”needsastructuretohold:ProgramCounter(PC),StackPointer(SP)Registers(Integer,Floatingpoint,others…?)HowswitchfromonevirtualCPUtothenext?SavePC,SP,andregistersincurrentstateblockLoadPC,SP,andregistersfromnewstateblockWhattriggersswitch?Timer,voluntaryyield,I/O,otherthingsvCPU1vCPU2vCPU3vCPU1vCPU2TimePropertiesofthissimplemultiprogrammingtechniqueAllvirtualCPUssharesamenon-CPUresourcesI/OdevicesthesameMemorythesameConsequenceofsharing:Eachthreadcanaccessthedataofeveryotherthread(goodforsharing,badforprotection)Threadscanshareinstructions

(goodforsharing,badforprotection)CanthreadsoverwriteOSfunctions?This(unprotected)modeliscommonin:EmbeddedapplicationsWindows3.1/EarlyMacintosh(switchonlywithyield)Windows95—ME(switchwithbothyieldandtimer)ModernTechnique:

SimultaneousMultiThreading/HyperthreadingHardwaretechniqueExploitnaturalproperties

ofsuperscalarprocessors

toprovideillusionof

multipleprocessorsNeedtoreplicateregisters,

buthigherutilizationof

processorresourcesCanscheduleeachthread

asifwereseparateCPUBut,non-linearspeedup!Originaltechniquecalled“SimultaneousMultithreading”See/research/smt/index.html

SPARC,Pentium4/Xeon(“Hyperthreading”),Power5Howtoprotectthreadsfromoneanother?ProtectionofmemoryEverythreaddoesnothaveaccesstoallmemoryProtectionofI/OdevicesEverythreaddoesnothaveaccesstoeverydeviceProtectionofaccesstoprocessor:preemptiveswitchingfromthreadtothreadUseoftimerMustnotbepossibletodisabletimerfromusercodeProgramAddressSpaceRecall:Program’sAddressSpaceAddressspacethesetofaccessibleaddresses+associatedstates:Fora32-bitprocessorthereare232=4billionaddressesWhathappenswhenyoureadorwritetoanaddress?PerhapsnothingPerhapsactslikeregularmemoryPerhapsignoreswritesPerhapscausesI/Ooperation(Memory-mappedI/O)Perhapscausesexception(fault)ProvidingIllusionofSeparateAddressSpace:

LoadnewTranslationMaponSwitchProg1VirtualAddressSpace1Prog2VirtualAddressSpace2CodeDataHeapStackCodeDataHeapStackData2Stack1Heap1OSheap&StacksCode1Stack2Data1Heap2Code2OScodeOSdataTranslationMap1TranslationMap2PhysicalAddressSpaceAdministriviaWeareusingPiazzainsteadofthenewsgroupGotto/berkeley/fall2013/cs162MakeanaccountandjoinBerkeley,CS162PleaseaskquestionsonPiazzainsteadofemailingTAsAlreadyregisteredandneedanaccountform?SeeaTAafterclass/sectionoremailcs162@coryDepartmentwillprocessthewaitlistuntilWednesdayDon’tknowJavawell?TakeCS9Gself-pacedJavacourseReadDavidEck’sfreeJavabookWemayhavepopquizzes…Administrivia:ProjectSignupProjectSignup:Use“Group/SectionSignup”Link4-5memberstoagroup,everyonemustattendthesamesectionThesectionsassignedtoyoubyTelebearsaretemporary!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:00P85EvansKevin107TBATBATBA108TBATBATBAAdministrivia:ProjectsFirsttwoprojectsarebasedonNachosStartreadingwalkthroughandcodeNOWSecondtwoprojectswilladdmoreOSandsystemscomponents:in-memorykey-valuestoreProject3:singleserverkey-valuestore:PUT/GETRPCs,in-memoryhash-tablemanagementProject4:distributedkey-valuestore:Twophasecommitforreplication,data/communicationencryptionAdministrivia:Laptop/SmartphonePolicyDiscussionsections:closed-laptop/smartphonepolicyLecture:Closedlaptopsandsmartphones,highlypreferredIfyoureallyhavetousealaptop,pleasestayinthebackoftheclass(tominimizedisruption)5minBreakTraditionalUNIXProcessProcess:OperatingsystemabstractiontorepresentwhatisneededtorunasingleprogramOftencalleda“HeavyWeightProcess”Formally:asingle,sequentialstreamofexecutioninitsownaddressspaceTwoparts:SequentialprogramexecutionstreamCodeexecutedasasingle,sequentialstreamofexecution(i.e.,thread)IncludesStateofCPUregistersProtectedresources:Mainmemorystate(contentsofAddressSpace)I/Ostate(i.e.filedescriptors)Important:ThereisnoconcurrencyinaheavyweightprocessProcess

ControlBlockHowdoweMultiplexProcesses?Thecurrentstateofprocessheldinaprocesscontrolblock(PCB):Thisisa“snapshot”oftheexecutionandprotectionenvironmentOnlyonePCBactiveatatimeGiveoutCPUtimetodifferentprocesses(Scheduling):Onlyoneprocess“running”atatimeGivemoretimetoimportantprocessesGivepiecesofresourcestodifferentprocesses(Protection):Controlledaccesstonon-CPUresourcesExamplemechanisms:MemoryMapping:GiveeachprocesstheirownaddressspaceKernel/Userduality:ArbitrarymultiplexingofI/OthroughsystemcallsCPUSwitchFromProcesstoProcessThisisalsocalleda“contextswitch”CodeexecutedinkernelaboveisoverheadOverheadsetsminimumpracticalswitchingtimeLessoverheadwithSMT/Hyperthreading,but…contentionforresourcesinsteadLifecycleofaProcessAsaprocessexecutes,itchangesstate:new:Theprocessisbeingcreatedready:Theprocessiswaitingtorunrunning:Instructionsarebeingexecutedwaiting:Processwaitingforsomeeventtooccurterminated:TheprocesshasfinishedexecutionProcessSchedulingPCBsmovefromqueuetoqueueastheychangestateDecisionsaboutwhichordertoremovefromqueuesareSchedulingdecisionsManyalgorithmspossible(fewweeksfromnow)Whatdoesittaketocreateaprocess?MustconstructnewPCBInexpensiveMustsetupnewpagetablesforaddressspaceMoreexpensiveCopydatafromparentprocess?(Unixfork())SemanticsofUnixfork()arethatthechildprocessgetsacompletecopyoftheparentmemoryandI/OstateOriginallyveryexpensiveMuchlessexpensivewith“copyonwrite”CopyI/Ostate(filehandles,etc)MediumexpenseProcess=?ProgramMoretoaprocessthanjustaprogram:ProgramisjustpartoftheprocessstateIrunemacsonlectures.txt,yourunitonhomework.java–sameprogram,differentprocessesLesstoaprocessthanaprogram:Aprogramcaninvokemorethanoneprocessccstartsupcpp,cc1,cc2,as,andldmain(){…;}A(){…}main(){…;}A(){…}HeapStackAmainProgramProcessMultipleProcessesCollaborateonaTaskNeedCommunicationmechanism:SeparateaddressspacesisolatesprocessesShared-MemoryMappingAccomplishedbymappingaddressestocommonDRAMReadandWritethroughmemoryMessagePassingsend()andreceive()messagesWorksacrossnetworkProc1Proc2Proc3SharedMemoryCommunicationProg1VirtualAddressSpace1Prog2VirtualAddressSpace2Data2Stack1Heap1Code1Stack2Data1Heap2Code2SharedCommunicationoccursby“simply”reading/writingtosharedaddresspageReallylowoverheadcommunicationIntroducescomplexsynchronizationproblemsCodeDataHeapStackSharedCodeDataHeapStackSharedInter-processCommunication(IPC)MechanismforprocessestocommunicateandtosynchronizetheiractionsMessagesystem–processescommunicatewitheachotherwithoutresortingtosharedvariablesIPCfacilityprovidestwooperations:send(message)–messagesizefixedorvariablereceive(message)IfPandQwishtocommunicate,theyneedto:establishacommunication

channelbetweenthemexchangemessagesviasend/receiveImplementationofcommunicationlinkphysical(e.g.,sharedmemory,hardwarebus,syscall/trap)logical(e.g.,logicalproperties)Modern“Lightweight”ProcesswithThreadsThread:asequentialexecutionstreamwithinprocess(Sometimescalleda“Lightweightprocess”)ProcessstillcontainsasingleAddressSpaceNoprotectionbetweenthreadsMultithreading:asingleprogrammadeupofanumberofdifferentconcurrentactivitiesSometimescalledmultitasking,asinAda…Whyseparatetheconceptofathreadfromthatofaprocess?Discussthe“thread”partofaprocess(concurrency)Separatefromthe“addressspace”(protection)HeavyweightProcessProcesswithonethreadSingleandMultithreadedProcessesThreadsencapsulateconcurrency:“Active”componentAddressspacesencapsulateprotection:“Passive”partKeepsbuggyprogramfromtrashingthesystemWhyhavemultiplethreadsperaddressspace?ExamplesofmultithreadedprogramsEmbeddedsystemsElevators,Planes,Medicalsystems,WristwatchesSingleProgram,concurrentoperationsMostmodernOSkernelsInternallyconcurrentbecausehavetodealwithconcurrentrequestsbymultipleusersButn