伯克利操作系统课件lec12io

CS162

OperatingSystemsand

SystemsProgramming

Lecture12

Kernel/User,I/OOctober14,2013AnthonyD.JosephandJohnCanny/~cs162DemandpagingleveragesseveralPTEbits“V”:Valid/NotValid“V=1”:ValidPageinmemory,PTEpointsatphysicalpage“V=0”:NotValidPagenotinmemory;useinfoinPTEtofindpageondiskifnecessary“D=1”:PagemodifiedNeedtowriteitbacktodiskbeforereplacingit“U=1”:PagereferencedGivepageasecondchancebeforebeingreplacedwhenusingSecondChancealgorithmSomeotherPTEbits:“R/W”:specifieswhetherthepagecanbemodifiedorisreadonlyPageAccessCount:implementmoreaccurateLRUalgorithmsReview:DemandPagingMechanismsSupposeuserreferencespagewithinvalidPTE?MemoryManagementUnit(MMU)trapstoOSResultingtrapisa“PageFault”WhatdoesOSdoonaPageFault?:ChooseanoldpagetoreplaceIfoldpagemodified(“D=1”),writecontentsbacktodiskChangeitsPTEandanycachedTLBtobeinvalidLoadnewpageintomemoryfromdiskUpdatepagetableentry,invalidateTLBfornewentryContinuethreadfromoriginalfaultinglocationTLBfornewpagewillbeloadedwhenthreadcontinued!Whilepullingpagesoffdiskforoneprocess,OSrunsanotherprocessfromreadyqueueSuspendedprocesssitsonwaitqueueCacheReview:DemandPagingMechanismsFinishDemandPaging:TrashingandWorkingSetsDualModeOperation:KernelversusUserModeI/OSystemsHardwareAccessDeviceDriversDiskPerformanceHardwareperformanceparametersNote:Someslidesand/orpicturesinthefollowingareadaptedfromslides©2005Silberschatz,Galvin,andGagne.ManyslidesgeneratedfrommylecturenotesbyKubiatowicz.GoalsforTodayThrashingIfaprocessdoesnothave“enough”pages,thefaultrateisveryhigh.Thisleadsto:lowCPUutilizationoperatingsystemspendsmostofitstimeswappingtodiskThrashingaprocessisbusyswappingpagesinandoutQuestions:HowdowedetectThrashing?WhatisbestresponsetoThrashing?ProgramMemoryAccessPatternshavetemporalandspatiallocalityGroupofPagesaccessedalongagiventimeslicecalledthe“WorkingSet”WorkingSetdefinesminimumnumberofpagesneededforprocesstobehavewellNotenoughmemoryforWorkingSetThrashingBettertoswapoutprocess?LocalityInAMemory-ReferencePatternWorking-SetModelworking-setwindowfixednumberofpagereferencesExample:10,000instructionsWSi(workingsetofProcessPi)=totalsetofpagesreferencedinthemostrecent(variesintime)iftoosmallwillnotencompassentirelocalityiftoolargewillencompassseverallocalitiesif=willencompassentireprogramD=|WSi|totaldemandframesifD>physical

memoryThrashingPolicy:ifD>physicalmemory,thensuspend/swapoutprocessesThiscanimproveoverallsystembehaviorbyalot!WhataboutCompulsoryMisses?Recallthatcompulsorymissesaremissesthatoccurthefirsttimethatapageisseen PagesthataretouchedforthefirsttimePagesthataretouchedafterprocessisswappedout/swappedbackinClustering:Onafault,bringinmultiplepages“around”thefaultingpageSinceefficiencyofdiskreadsincreaseswithsequentialreads,makessensetoreadseveralsequentialpagesTradeoff:Prefetchingmayevictotherin-usepagesfornever-usedprefetchedpagesWorkingSetTracking:UsealgorithmtotrytotrackworkingsetofapplicationWhenswappingprocessbackin,swapinworkingsetReview:ExampleofGeneralAddressTranslationProg1VirtualAddressSpace1Prog2VirtualAddressSpace2CodeDataHeapStackCodeDataHeapStackData2Stack1Heap1OSheap&StacksCode1Stack2Data1Heap2Code2OScodeOSdataTranslationMap1TranslationMap2PhysicalAddressSpaceDual-ModeOperationCananapplicationmodifyitsowntranslationmapsorPTEbits?Ifitcould,couldgetaccesstoallofphysicalmemoryHastoberestrictedsomehowToassistwithprotection,hardwareprovidesatleasttwomodes(Dual-ModeOperation):“Kernel”mode(or“supervisor”or“protected”)“User”mode(Normalprogrammode)Modesetwithbitsinspecialcontrolregisteronlyaccessibleinkernel-modeIntelprocessorsactuallyhavefour“rings”ofprotection:PL(PrivilegeLevel)from0–3PL0hasfullaccess,PL3hasleastTypicalOSkernelsonIntelprocessorsonlyusePL0(“kernel”)andPL3(“user”)ForProtection,LockUser-ProgramsinAsylumIdea:Lockuserprogramsinpaddedcell

withnoexitorsharpobjectsCannotchangemodetokernelmodeCannotmodifytranslationmapsLimitedaccesstomemory:cannot

adverselyeffectotherprocessesWhatelseneedstobeprotected?AcoupleofissuesHowtoshareCPUbetweenkernelanduserprograms?Howdoesoneswitchbetweenkernelandusermodes?OSuser(kernelusermode):gettingintocellUserOS(userkernelmode):gettingoutofcellHowtogetfromKernelUserWhatdoesthekerneldotocreateanewuserprocess?AllocateandinitializeprocesscontrolblockReadprogramoffdiskandstoreinmemoryAllocateandinitializetranslationmapPointatcodeinmemorysoprogramcanexecutePossiblypointatstaticallyinitializeddataRunProgram:SetmachineregistersSethardwarepointertotranslationtableSetprocessorstatuswordforusermodeJumptostartofprogramHowdoeskernelswitchbetweenprocesses(welearnedaboutthis!)?Samesaving/restoringofregistersasbeforeSave/restorehardwarepointertotranslationmapUserKernel(SystemCall)Can’tletinmate(user)getoutofpaddedcellonownWoulddefeatpurposeofprotection!So,howdoestheuserprogramgetbackintokernel?Systemcall:VoluntaryprocedurecallintokernelHardwareforcontrolledUserKerneltransitionCananykernelroutinebecalled?No!OnlyspecificonesSystemcallIDencodedintosystemcallinstructionIndexforceswell-definedinterfacewithkernelI/O:open,close,read,write,lseekFiles:delete,mkdir,rmdir,chownProcess:fork,exit,joinNetwork:socketcreate,selectSystemCall(cont’d)Aresystemcallsthesameacrossoperatingsystems?Notentirely,buttherearelotsofcommonalitiesAlsosomestandardizationattempts(POSIX)Whathappensatbeginningofsystemcall?Onentrytokernel,setssystemtokernelmodeHandleraddressfetchedfromtable,andHandlerstartedSystemCallargumentpassing:Inregisters(notverymuchcanbepassed)Writeintousermemory,kernelcopiesintokernelmemoryEveryargumentmustbeexplicitlychecked!UserKernel(Exceptions:TrapsandInterrupts)Systemcallinstr.causesasynchronousexception(or“trap”)Infact,oftencalledasoftware“trap”instructionOthersourcesofSynchronousExceptions:Dividebyzero,Illegalinstruction,Buserror(badaddress,e.g.unalignedaccess)SegmentationFault(addressoutofrange)PageFaultInterruptsareAsynchronousExceptionsExamples:timer,diskready,network,etc….Interruptscanbedisabled,trapscannot!SUMMARY–Onsystemcall,exception,orinterrupt:HardwareenterskernelmodewithinterruptsdisabledSavesPC,thenjumpstoappropriatehandlerinkernelForsomeprocessors(x86),processoralsosavesregisters,changesstack,etc.ModernI/OSystemsWhatistheRoleofI/O?WithoutI/O,computersareuseless(disembodiedbrains?)But…thousandsofdevices,eachslightlydifferentHowcanwestandardizetheinterfacestothesedevices?Devicesunreliable:mediafailuresandtransmissionerrorsHowcanwemakethemreliable???Devicesunpredictableand/orslowHowcanwemanagethemifwedon’tknowwhattheywilldoorhowtheywillperform?AdministriviaProject2DesignDocdueThursday10/17at11:59PMMidtermexamTBAin2roomsClosedbook,nocalculatorsCoverslectures/readings#1-13(Wednesday)andprojectoneOnedouble-sidedhandwrittenpageofnotesallowedReviewsession:TBAPleasefilltheanonymouscoursesurveyatXXXXXXWe’lltrytomakechangesthissemesterbasedonyourfeedback5minBreakOperationalParametersforI/ODatagranularity:Bytevs.BlockSomedevicesprovidesinglebyteatatime(e.g.,keyboard)Othersprovidewholeblocks(e.g.,disks,networks,etc.)Accesspattern:Sequentialvs.RandomSomedevicesmustbeaccessedsequentially(e.g.,tape)Otherscanbeaccessedrandomly(e.g.,disk,cd,etc.)Transfermechanism:Pollingvs.InterruptsSomedevicesrequirecontinualmonitoringOthersgenerateinterruptswhentheyneedserviceExampleDevice-TransferRates(SunEnterprise6000)DeviceRatesvaryovermanyordersofmagnitudeSystembetterbeabletohandlethiswiderangeBetternothavehighoverhead/byteforfastdevices!BetternotwastetimewaitingforslowdevicesTheGoaloftheI/OSubsystemProvideuniforminterfaces,despitewiderangeofdifferentdevicesThiscodeworksonmanydifferentdevices:

FILEfd=fopen(“/dev/something”,“rw”);

for(inti=0;i<10;i++){

fprintf(fd,“Count%d\n”,i);

}

close(fd);Why?Becausecodethatcontrolsdevices(“devicedriver”)implementsstandardinterfaceWewilltrytogetaflavorforwhatisinvolvedinactuallycontrollingdevicesinrestoflectureCanonlyscratchsurface!

WantStandardInterfacestoDevicesBlockDevices:

e.g.,

diskdrives,tapedrives,DVD-ROMAccessblocksofdataCommandsincludeopen(),read(),write(),seek()RawI/Oorfile-systemaccessMemory-mappedfileaccesspossibleCharacter/ByteDevices:

e.g.,

keyboards,mice,serialports,someUSBdevicesSinglecharactersatatimeCommandsincludeget(),put()LibrarieslayeredontopallowlineeditingNetworkDevices:e.g.,

Ethernet,Wireless,BluetoothDifferentenoughfromblock/charactertohaveowninterfaceUnixandWindowsincludesocketinterfaceSeparatesnetworkprotocolfromnetworkoperationIncludesselect()

functionalityHowDoesUserDealwithTiming?BlockingInterface:“Wait”Whenrequestdata(e.g.,

read()

systemcall),putprocesstosleepuntildataisreadyWhenwritedata(e.g.,

write()

systemcall),putprocesstosleepuntildeviceisreadyfordataNon-blockingInterface:“Don’tWait”ReturnsquicklyfromreadorwriterequestwithcountofbytessuccessfullytransferredtokernelReadmayreturnnothing,writemaywritenothingAsynchronousInterface:“TellMeLater”Whenrequestingdata,takepointertouser’sbuffer,returnimmediately;laterkernelfillsbufferandnotifiesuserWhensendingdata,takepointertouser’sbuffer,returnimmediately;laterkerneltakesdataandnotifiesuserDeviceControllerreadwritecontrolstatusAddressableMemoryand/orQueuesRegisters(port0x20)HardwareControllerMemoryMappedRegion:0x8f008020BusInterfaceHowDoestheProcessorTalktoDevices?CPUinteractswithaControllerContainsasetofregistersthat

canbereadandwrittenMaycontainmemoryforrequest

queuesorbit-mappedimagesRegardlessofthecomplexityoftheconnectionsandbuses,processoraccessesregistersintwoways:I/Oinstructions:in/outinstructions(e.g.,Intel’s0x21,AL)MemorymappedI/O:load/storeinstructionsRegisters/memoryappearinphysicaladdressspaceI/OaccomplishedwithloadandstoreinstructionsAddress+DataInterruptRequestProcessorMemoryBusCPURegularMemoryOtherDevicesorBusesInterruptControllerBusAdaptorBusAdaptorExample:Memory-MappedDisplayControllerMemory-Mapped:HardwaremapscontrolregistersanddisplaymemoryintophysicaladdressspaceAddressessetbyhardwarejumpersorprogrammingatboottimeSimplywritingtodisplaymemory(alsocalledthe“framebuffer”)changesimageonscreenAddr:0x8000F000—0x8000FFFFWritinggraphicsdescriptiontocommand-queueareaSayenterasetoftrianglesthatdescribesomesceneAddr:0x80010000—0x8001FFFFWritingtothecommandregistermaycauseon-boardgraphicshardwaretodosomethingSayrendertheabovesceneAddr:0x0007F004CanprotectwithaddresstranslationDisplayMemory0x8000F0000x80010000PhysicalAddressSpaceStatus0x0007F000Command0x0007F004GraphicsCommandQueue0x80020000TransferringDataTo/FromControllerProgrammedI/O:Eachbytetransferredviaprocessorin/outorload/storePro:Simplehardware,easytoprogramCon:ConsumesprocessorcyclesproportionaltodatasizeDirectMemoryAccess:GivecontrolleraccesstomemorybusAskittotransferdatato/frommemorydirectlySampleinteractionwithDMAcontroller(frombook):I/ODeviceNotifyingtheOSTheOSneedstoknowwhen:TheI/OdevicehascompletedanoperationTheI/OoperationhasencounteredanerrorI/OInterrupt:DevicegeneratesaninterruptwheneveritneedsservicePro:handlesunpredictableeventswellCon:interruptsrelativelyhighoverheadPolling:OSperiodicallychecksadevice-specificstatusregisterI/OdeviceputscompletioninformationinstatusregisterPro:lowoverheadCon:maywastemanycyclesonpollingifinfrequentorunpredictableI/OoperationsActualdevicescombinebothpollingandinterruptsForinstance–High-bandwidthnetworkadapter:InterruptforfirstincomingpacketPollforfollowingpacketsuntilhardwarequeuesareemptyI/OPerformanceResponseTime=Queue+I/OdeviceservicetimeUserThreadQueue[OSPaths]ControllerI/OdevicePerformanceofI/OsubsystemMetrics:ResponseTime,ThroughputContributingfactorstolatency:Softwarepaths(canbelooselymodeledbyaqueue)HardwarecontrollerI/OdeviceservicetimeQueuingbehavior:Canleadtobigincreasesoflatencyasutilizationapproaches100%100%ResponseTime(ms)Throughput(Utilization)(%totalBW)01002003000%Q1:True_False_Withanasynchronousinterface,thewritermayneedtoblockuntilthedatais