Memory Management.ppt

Chapter9MemoryManagement,BackgroundLogicalversusPhysicalAddressSpaceSwappingContiguousAllocationPagingSegmentationSegmentationwithPaging,Background,Programmustbebroughtintomemoryandplacedwithinaprocessforittobeexecuted.Inputqueuecollectionofprocessesonthediskthatarewaitingtobebroughtintomemoryforexecution.Userprogramsgothroughseveralstepsbeforebeingexecuted.(forexample),Multistepprocessingofauserprogram,BindingofInstructionsandDatatoMemory,Compiletime:Ifmemorylocationknownapriori,absolutecodecanbegenerated;mustrecompilecodeifstartinglocationchanges.Loadtime:Mustgeneraterelocatablecodeifmemorylocationisnotknownatcompiletime.Executiontime:Bindingdelayeduntilruntimeiftheprocesscanbemovedduringitsexecutionfromonememorysegmenttoanother.Needhardwaresupportforaddressmaps(e.g.,baseandlimitregisters).,Logicalvs.PhysicalAddressSpace,Theconceptofalogicaladdressspacethatisboundtoaseparatephysicaladdressspaceiscentraltopropermemorymanagement.LogicaladdressgeneratedbytheCPU;alsoreferredtoasvirtualaddress.Physicaladdressaddressseenbythememoryunit.(forexample)Logicalandphysicaladdressesarethesameincompile-timeandload-timeaddress-bindingschemes;logical(virtual)andphysicaladdressesdifferinexecution-timeaddress-bindingscheme.,Example,0LOADAX,6；AXValue62ADDAX,8；AXAX+Value84SROREAX,10；Value10AX6A8B10A+B,Relocation,ModifythecontentsrelatedtotheaddressesinuserprogramBindtheselogicaladdressestophysicaladdressesTwotypesofrelocations:Staticrelocation:Programsmustberelocatedbycompiler/linkerbeforeenteringmemory.Dynamicrelocation:Programsmaynotberelocateduntilexecutingthecommandsrelatedtoaddresses.,Examples,Dynamicrelocationusingarelocationregister,DynamicLoading,Routineisnotloadeduntilitiscalled.Bettermemory-spaceutilization;unusedroutineisneverloaded.Usefulwhenlargeamountsofcodeareneededtohandleinfrequentlyoccurringcases.Nospecialsupportfromtheoperatingsystemisrequiredimplementedthroughprogramdesign.,DynamicLinking,Linkingpostponeduntilexecutiontime.Smallpieceofcode,stub,usedtolocatetheappropriatememory-residentlibraryroutine.Stubreplacesitselfwiththeaddressoftheroutine,andexecutestheroutine.Operatingsystemneededtocheckifroutineisinprocessesmemoryaddress.,Overlays,Keepinmemoryonlythoseinstructionsanddatathatareneededatanygiventime.Neededwhenprocessislargerthanamountofmemoryallocatedtoit.Implementedbyuser,nospecialsupportneededfromoperatingsystem,programmingdesignofoverlaystructureiscomplex.,Overlaysforatwo-passassembler,Memory-ManagementUnit(MMU),Hardwaredevicethatmapsvirtualtophysicaladdress.InMMUscheme,thevalueintherelocationregisterisaddedtoeveryaddressgeneratedbyauserprocessatthetimeitissenttomemory.Theuserprogramdealswithlogicaladdresses;itneverseestherealphysicaladdresses.,Swapping,Aprocesscanbeswappedtemporarilyoutofmemorytoabackingstore,andthenbroughtbackintomemoryforcontinuedexecution.Backingstorefastdisklargeenoughtoaccommodatecopiesofallmemoryimagesforallusers;mustprovidedirectaccesstothesememoryimages.,Swapping,Rollout,rollinswappingvariantusedforpriority-basedschedulingalgorithms;lower-priorityprocessisswappedoutsohigher-priorityprocesscanbeloadedandexecuted.Majorpartofswaptimeistransfertime;totaltransfertimeisdirectlyproportionaltotheamountofmemoryswapped.Modifiedversionsofswappingarefoundonmanysystems,i.e.,UNIXandMicrosoftWindows.,SchematicViewofSwapping,ContiguousAllocation,Mainmemoryusuallydividedintotwopartitions:Residentoperatingsystem,usuallyheldinlowmemorywithinterruptvector.Userprocessesthenheldinhighmemory.Single-partitionallocationRelocation-registerschemeusedtoprotectuserprocessesfromeachother,andfromchangingoperating-systemcodeanddata.Relocationregistercontainsvalueofsmallestphysicaladdress;limitregistercontainsrangeoflogicaladdresseseachlogicaladdressmustbelessthanthelimitregister.,ContiguousAllocation(Cont.),Multiple-partitionallocationHoleblockofavailablememory;holesofvarioussizearescatteredthroughoutmemory.Whenaprocessarrives,itisallocatedmemoryfromaholelargeenoughtoaccommodateit.Operatingsystemmaintainsinformationabout:a)allocatedpartitionsb)freepartitions(hole),Datastructure:Freepartitionstable,Processlist：A(10),B(45),C(25),D(30).,OS,1/A,2/C,3/B,4/,30K,45K,75K,125K,225K,0K,#length(kb)begin(k)state41001250,freepartitionstable,allocatedpartitionstable,ExampleforContiguousAllocation,ExampleforContiguousAllocation(Cont.),Ifp6(80k)come,howtoallocate?,100k,300k,260k,DynamicStorage-AllocationProblem,First-fit（首次适应）:Allocatethefirstholethatisbigenough.Best-fit（最佳适应）:Allocatethesmallestholethatisbigenough;mustsearchentirelist,unlessorderedbysize.Producesthesmallestleftoverhole.Worst-fit（最差适应）:Allocatethelargesthole;mustalsosearchentierlist.Producesthelargestleftoverhole.,First-fitandbest-fitbetterthanworst-fitintermsofspeedandstorageutilization.,DynamicpartitionallocationExample,Proglist：,A（10）,B（50）,C（25）,B,D（48）,#length(kb)begin(k)state1610300234.,OS,0,30,640,A（10）,60040,B（50）,40,90,55090,C（25）,115,525115,5040525115,0,D（48）,288525115,ALLOCATIONOVER,C,55288,OVER,Releasepartitions,Fragmentation,Externalfragmentation（外碎片）totalmemoryspaceexiststosatisfyarequest,butitisnotcontiguous.Internalfragmentation（内碎片）allocatedmemorymaybeslightlylargerthanrequestedmemory;thissizedifferenceismemoryinternaltoapartition,butnotbeingused.ReduceexternalfragmentationbycompactionShuffle整理memorycontentstoplaceallfreememorytogetherinonelargeblock.Compactionispossibleonlyifrelocationisdynamic,andisdoneatexecutiontime.Whendocompaction?,Compact,Paging,Whyneedpaging?NeedcontiguousmemoryFragmentCompactingcostSolutionChangecontiguousallocationintononcontiguousallocationProblemCanlogicaladdressspaceofaprocessbenoncontiguous?Processisallocatedphysicalmemorywheneverthelatterisavailable.,Paging(cont),Dividephysicalmemoryintofixed-sizedblockscalledframes(sizeis2n),number0,1,2Dividelogicalmemoryintoblocksofsamesizecalledpages.number0,1,2Logicaladdress:v=(P,d),(v=p*size+d)Keeptrackofallfreeframes.Torunaprogramofsizenpages,needtofindnfreeframesandloadprogram.,Paging(cont),Setupapagetabletotranslatelogicaltophysicaladdresses.Setupapagetableregisterinclude:Page-tablebaseregister页表基址寄存器(PTBR)Page-tablelengthregister页表限长寄存器(PRLR)indicte:beginaddrandlengthofcurrentprogresspagetable,PagingExample,Processlogicaladdrspace,PagingExample,.,frames,0,1,2,3,4,5,6,7,8,9,10,11,12,0123,02132638,page#frame#,ProcessA,A0,A1,A2,A3,012,ProB,0417212,page#frame#,B0,B1,B2,OVER,AddressTranslationScheme,AddressgeneratedbyCPUisdividedinto:Pagenumber(p)（页号）usedasanindexintoapagetablewhichcontainsbaseaddressofeachpageinphysicalmemory.Pageoffset(d)（偏移）combinedwithbaseaddresstodefinethephysicalmemoryaddressthatissenttothememoryunit.,AddressTranslationArchitecture,AddressTranslationexample,Frames,0,1,3,4,5,6,7,8,9,10,11,12,A0,A1,A2,A3,2,02132638,page#frame#,V=(2,d),PTR,BL,L,(6，d),Offsetd,Logicaladdressv,V=2130,pagesize=1k,physicaladdr=?,Problem,Pagetableiskeptinmainmemory.Inthisschemeeverydata/instructionaccess,howmanymemoryaccessesarerequired?,Two:Oneforthepagetableandoneforthedata/instruction.,Thetwomemoryaccessproblemcanbesolvedbytheuseofaspecialfast-lookuphardwarecachecalledassociativeregistersortranslationlook-asidebuffers变换后备存储器TLBs,AssociativeRegister,Associativeregisters联想寄存器parallelsearchAddresstranslation(A,A)IfAisinassociativeregister,getframe#out.Otherwisegetframe#frompagetableinmemory.,PaginghardwarewithTLB,EffectiveAccessTime,AssociativeLookup=timeunitAssumememorycycletimeis1microsecondHitrationpercentageoftimesthatapagenumberisfoundintheassociativeregisters;rationrelatedtonumberofassociativeregisters.Hitratio=EffectiveAccessTime(EAT)EAT=(1+)+(2+)(1)=2+,MemoryProtection,Memoryprotectionimplementedbyassociatingprotectionbitwitheachframe.Valid-invalidbit有效-无效位attachedtoeachentryinthepagetable:“valid”indicatesthattheassociatedpageisintheprocesslogicaladdressspace,andisthusalegalpage.“invalid”indicatesthatthepageisnotintheprocesslogicaladdressspace.,Valid(v)orinvalid(i)bitinaPagetable,Two-LevelPage-TableScheme,Two-LevelPagingExample,Alogicaladdress(on32-bitmachinewith4Kpagesize)isdividedinto:apagenumberconsistingof20bits.apageoffsetconsistingof12bits.Sincethepagetableispaged,thepagenumberisfurtherdividedinto:a10-bitpagenumber.a10-bitpageoffset.Thus,alogicaladdressisas:wherepiisanindexintotheouterpagetable,andp2isthedisplacementwithinthepageoftheouterpagetable.,Address-TranslationScheme,Address-translationschemeforatwo-level32-bitpagingarchitecture,MultilevelPagingandPerformance,Sinceeachlevelisstoredasaseparatetableinmemory,coveringalogicaladdresstoaphysicalonemaytake4memoryaccesses.Eventhoughtimeneededforonememoryaccessisquintupled,cachingpermitsperformancetoremainreasonable.Cachehitrate命中率of98percentyields:effectiveaccesstime=0.98x120+0.02x520=128nanoseconds.whichisonlya28percentslowdowninmemoryaccesstime.,InvertedPageTable,Oneentryforeachrealpageofmemory.Entryconsistsofthevirtualaddressofthepagestoredinthatrealmemorylocation,withinformationabouttheprocessthatownsthatpage.Decreasesmemoryneededtostoreeachpagetable,butincreasestimeneededtosearchthetablewhenapagereferenceoccurs.Usehashtable哈希表tolimitthesearchtooneoratmostafewpage-tableentries.,InvertedPageTableArchitecture,SharedPages,SharedcodeOnecopyofread-only(reentrant可重入)codesharedamongprocesses(i.e.,texteditors,compilers,windowsystems).Sharedcodemustappearinsamelocationinthelogicaladdressspaceofallprocesses.PrivatecodeanddataEachprocesskeepsaseparatecopyofthecodeanddata.Thepagesfortheprivatecodeanddatacanappearanywhereinthelogicaladdressspace.,SharedPagesExample,Segmentation,Memory-managementschemethatsupportsuserviewofmemory.Aprogramisacollectionofsegments.Asegmentisalogicalunitsuchas:mainprogram,procedure,function,localvariables,globalvariables,commonblock,stack,symboltable,arrays,LogicalViewofSegmentation,SegmentationArchitecture,Logicaladdressconsistsofatwotuple2元组:,Segmenttable段表mapstwo-dimensionalphysicaladdresses;eachtableentryhas:base基址containsthestartingphysicaladdresswherethesegmentsresideinmemory.limit限长specifiesthelengthofthesegment.Segment-tablebaseregister(STBR)pointstothesegmenttableslocationinmemory.Segment-tablelengthregister(STLR)indicatesnumberofsegmentsusedbyaprogram;segmentnumbersislegalifsSTLR.,Segmentationhardware,SegmentationArchitec