操作系統(tǒng) 存儲管理 cch09-1

Module9:MemoryManagementBackground（背景）LogicalversusPhysicalAddressSpace（邏輯與物理地址空間）Swapping（交換）ContiguousAllocation（連續(xù)分配）Paging（分頁） Segmentation（分段）SegmentationwithPaging（段頁式）AppliedOperatingSystemConceptsBackgroundProgrammustbebroughtintomemoryandplacedwithinaprocessforittobeexecuted.（程序必需放入一個進程，并且送入內(nèi)存才能被執(zhí)行）Inputqueue–collectionofprocessesonthediskthatarewaitingtobebroughtintomemoryforexecution.（輸入隊列—磁盤上等待進入內(nèi)存并執(zhí)行的進程的集合）Userprogramsgothroughseveralstepsbeforebeingexecuted.（用戶程序在執(zhí)行之前必需經(jīng)歷很多步驟）AppliedOperatingSystemConceptsBindingofInstructionsandDatatoMemoryCompiletime（編譯時期）:Ifmemorylocationknownapriori,absolutecodecanbegenerated;mustrecompilecodeifstartinglocationchanges.（如果內(nèi)存位置已知，可生成絕對代碼；如果開始位置改變，需要重新編譯代碼）Loadtime（裝入時期）:Mustgeneraterelocatablecodeifmemorylocationisnotknownatcompiletime.（如果存儲位置在編譯時不知道，則必須生成可重定位代碼）Executiontime（執(zhí)行時期）:Bindingdelayeduntilruntimeiftheprocesscanbemovedduringitsexecutionfromonememorysegmenttoanother.Needhardwaresupportforaddressmaps(e.g.,baseandlimitregisters).（如果進程在執(zhí)行時可以在內(nèi)存中移動，則地址綁定要延遲到運行時。需要硬件對地址映射的支持，例如基址和限長寄存器）Addressbindingofinstructionsanddatatomemoryaddressescan

happenatthreedifferentstages.（指令和數(shù)據(jù)結(jié)合到內(nèi)存地址可以在三個不同的階段發(fā)生。）AppliedOperatingSystemConceptsDynamicLoadingRoutineisnotloadeduntilitiscalled.（例程在調(diào)用之前并不執(zhí)行）Bettermemory-spaceutilization;unusedroutineisneverloaded.（更好的內(nèi)存空間利用率；沒有被使用的例程不被載入。）Usefulwhenlargeamountsofcodeareneededtohandleinfrequentlyoccurringcases.（當(dāng)需要大量的代碼來處理不經(jīng)常發(fā)生的事情時是非常有用的。）Nospecialsupportfromtheoperatingsystemisrequiredimplementedthroughprogramdesign.（不需要操作系統(tǒng)的特別支持，通過程序設(shè)計實現(xiàn)）AppliedOperatingSystemConceptsDynamicLinkingLinkingpostponeduntilexecutiontime.（鏈接被推遲到執(zhí)行時期）Smallpieceofcode,stub,usedtolocatetheappropriatememory-residentlibraryroutine.（小的代碼片-存根，用來定位合適的保留在內(nèi)存中的庫程序。）Stubreplacesitselfwiththeaddressoftheroutine,andexecutestheroutine.（存根用例程地址來替換自己，以及執(zhí)行例程。）Operatingsystemneededtocheckifroutineisinprocesses’memoryaddress.（操作系統(tǒng)需要檢查例程是否在進程的內(nèi)存空間）AppliedOperatingSystemConceptsOverlaysKeepinmemoryonlythoseinstructionsanddatathatareneededatanygiventime.（只是在內(nèi)存中保留那些在特定時間所需要的指令和數(shù)據(jù)）Neededwhenprocessislargerthanamountofmemoryallocatedtoit.（當(dāng)進程比所分配的內(nèi)存大時，覆蓋是必需的）Implementedbyuser,nospecialsupportneededfromoperatingsystem,programmingdesignofoverlaystructureiscomplex.（由用戶執(zhí)行，不需要操作系統(tǒng)的特別支持，覆蓋結(jié)構(gòu)的程序設(shè)計很復(fù)雜。）AppliedOperatingSystemConceptsLogicalvs.PhysicalAddressSpaceTheconceptofalogicaladdressspacethatisboundtoaseparatephysical

addressspaceiscentraltopropermemorymanagement.（邏輯地址空間的概念同物理地址空間想關(guān)聯(lián)，它是正確內(nèi)存管理的中心。）Logicaladdress–generatedbytheCPU;alsoreferredtoasvirtualaddress.（邏輯地址—由CPU產(chǎn)生；也叫做虛擬空間。）Physicaladdress–addressseenbythememoryunit.（物理地址—內(nèi)存設(shè)備所讀入的地址）Logicalandphysicaladdressesarethesameincompile-timeandload-timeaddress-bindingschemes;logical(virtual)andphysicaladdressesdifferinexecution-timeaddress-bindingscheme.（邏輯和物理地址在編譯時期和裝入時期的地址綁定策略是相同的，而在執(zhí)行時間的地址綁定策略是不同的。）AppliedOperatingSystemConceptsMemory-ManagementUnit(MMU)Hardwaredevicethatmapsvirtualtophysicaladdress.（硬件把虛擬地址映射到物理地址）InMMUscheme,thevalueintherelocationregisterisaddedtoeveryaddressgeneratedbyauserprocessatthetimeitissenttomemory.（在MMU策略中，基址寄存器中的值在其送入內(nèi)存的時候被加入到由一個用戶進程所產(chǎn)生的每個地址中。）Theuserprogramdealswithlogicaladdresses;itneverseestherealphysicaladdresses.（用戶程序所對應(yīng)到的是邏輯地址，物理地址對它從來都不可見。）AppliedOperatingSystemConceptsSwappingAprocesscanbeswappedtemporarilyoutofmemorytoabackingstore,andthenbroughtbackintomemoryforcontinuedexecution.（一個進程可以暫時被交換到內(nèi)存外的一個備份區(qū)，隨后可以被換回內(nèi)存繼續(xù)執(zhí)行。）Backingstore–fastdisklargeenoughtoaccommodatecopiesofallmemoryimagesforallusers;mustprovidedirectaccesstothesememoryimages.（備份區(qū)—是一個固定的足夠大的可以容納所有用戶內(nèi)存映像的拷貝；對于可以讓這些內(nèi)存映像直接存取。）AppliedOperatingSystemConceptsSwappingRollout,rollin–swappingvariantusedforpriority-basedschedulingalgorithms;lower-priorityprocessisswappedoutsohigher-priorityprocesscanbeloadedandexecuted.（滾入，滾出—交換由于基于優(yōu)先級的算法而不同，低優(yōu)先級的進程被換出，這樣高優(yōu)先級的進程可以被裝入和執(zhí)行。）Majorpartofswaptimeistransfertime;totaltransfertimeisdirectlyproportionaltotheamountofmemoryswapped.（交換時間的主要部分是轉(zhuǎn)移時間，總的轉(zhuǎn)移時間直接同交換的內(nèi)存的數(shù)量成比例。）Modifiedversionsofswappingarefoundonmanysystems,i.e.,UNIXandMicrosoftWindows.（在許多系統(tǒng)如：UNIX，Windows中，可以找到一些被修正過的交換措施。）AppliedOperatingSystemConceptsSchematicViewofSwappingAppliedOperatingSystemConceptsContiguousAllocationMainmemoryusuallydividedintotwopartitions:（主存通常被分為兩部分）Residentoperatingsystem,usuallyheldinlowmemorywithinterruptvector.（為操作系統(tǒng)保留的部分，通常用中斷矢量保存在內(nèi)存低端。）Userprocessesthenheldinhighmemory.（用戶進程保存在內(nèi)存高端。）Single-partitionallocation（單獨分區(qū)分配）Relocation-registerschemeusedtoprotectuserprocessesfromeachother,andfromchangingoperating-systemcodeanddata.（基址寄存器策略由來保護用戶進程（同其他進程和改變的操作系統(tǒng)代碼和數(shù)據(jù)分開。）Relocationregistercontainsvalueofsmallestphysicaladdress;limitregistercontainsrangeoflogicaladdresses–eachlogicaladdressmustbelessthanthelimitregister.（基址寄存器包含最小物理地址的值；限長寄存器包含邏輯地址的范圍，每個邏輯地址必需比限長寄存器的值小。）AppliedOperatingSystemConceptsContiguousAllocation(Cont.)Multiple-partitionallocation（多分區(qū)分配）Hole–blockofavailablememory;holesofvarioussizearescatteredthroughoutmemory.（分區(qū)—可用的內(nèi)存塊，不同大小的分區(qū)分布在整個內(nèi)存中。）Whenaprocessarrives,itisallocatedmemoryfromaholelargeenoughtoaccommodateit.（當(dāng)一個進程到來的時候，它將從一個足夠容納它分區(qū)中分配內(nèi)存。）Operatingsystemmaintainsinformationabout（操作系統(tǒng)包含以下信息）:a)allocatedpartitions（分配的分區(qū)）b)freepartitions(hole)（空的分區(qū)）OSprocess5process8process2OSprocess5process2OSprocess5process2OSprocess5process9process2process9process10AppliedOperatingSystemConceptsDynamicStorage-AllocationProblemFirst-fit（首先適應(yīng)）:Allocatethefirstholethatisbigenough.（分配最先找到的合適的分區(qū)。）Best-fit（最佳適應(yīng)）:Allocatethesmallestholethatisbigenough;mustsearchentirelist,unlessorderedbysize.Producesthesmallestleftoverhole.（搜索整個序列，找到適合條件的最小的分區(qū)進行分配。）Worst-fit（最差適應(yīng)）:Allocatethelargesthole;mustalsosearchentierlist.Producesthelargestleftoverhole.（搜索整個序列，尋找最大的分區(qū)進行分配。）Howtosatisfyarequestofsizenfromalistoffreeholes.（怎樣從一個空的分區(qū)序列中滿足一個申請需要。）First-fitandbest-fitbetterthanworst-fitintermsofspeedandstorageutilization.（在速度和存儲的利用上，首先適應(yīng)和最佳適應(yīng)要比最差適應(yīng)好。）AppliedOperatingSystemConceptsFragmentationExternalfragmentation（外碎片）–totalmemoryspaceexiststosatisfyarequest,butitisnotcontiguous.（整個內(nèi)存空間用來滿足一個請求，但它不是連續(xù)的。）Internalfragmentation（內(nèi)碎片）–allocatedmemorymaybeslightlylargerthanrequestedmemory;thissizedifferenceismemoryinternaltoapartition,butnotbeingused.（分配的內(nèi)存可能比申請的內(nèi)存大一點，這兩者之間的差別是內(nèi)部不被使用的簇）Reduceexternalfragmentationbycompaction（通過壓縮來減少內(nèi)碎片）Shufflememorycontentstoplaceallfreememorytogetherinonelargeblock.（把一些小的空閑內(nèi)存結(jié)合成一個大的塊。）Compactionispossibleonlyifrelocationisdynamic,andisdoneatexecutiontime.（只有重置是動態(tài)的時候，才有可能進行壓縮，壓縮在執(zhí)行時期進行）I/Oproblem（I/O問題）LatchjobinmemorywhileitisinvolvedinI/O.（當(dāng)I/O的時候，把工作鎖定在內(nèi)存中。）DoI/OonlyintoOSbuffers.（只對操作系統(tǒng)的緩沖區(qū)進行I/O。）AppliedOperatingSystemConceptsPagingLogicaladdressspaceofaprocesscanbenoncontiguous;processisallocatedphysicalmemorywheneverthelatterisavailable.（進程的邏輯地址空間可能是不連續(xù)的，如果有可用的物理內(nèi)存，它將分給進程。）Dividephysicalmemoryintofixed-sizedblockscalledframes(sizeispowerof2,between512bytesand8192bytes).（把物理內(nèi)存分成大小固定的塊。）Dividelogicalmemoryintoblocksofsamesizecalledpages.（把邏輯內(nèi)存也分位固定大小的塊，叫做頁。）Keeptrackofallfreeframes.（保留一個頁的記錄。）Torunaprogramofsizenpages,needtofindnfreeframesandloadprogram.（運行一個有N頁大小的程序，需要找到N個空的頁框讀入程序。）Setupapagetabletotranslatelogicaltophysicaladdresses.（建立一個頁表，把邏輯地址轉(zhuǎn)換為物理地址。）Internalfragmentation.（內(nèi)碎片。）AppliedOperatingSystemConceptsAddressTranslationSchemeAddressgeneratedbyCPUisdividedinto（CPU產(chǎn)生的地址被分為）:Pagenumber

(p)（頁號）–usedasanindexintoapage

tablewhichcontainsbaseaddressofeachpageinphysicalmemory.（它包含每個頁在物理內(nèi)存中的基址，用來作為頁表的索引。）Pageoffset

(d)（偏移）–combinedwithbaseaddresstodefinethephysicalmemoryaddressthatissenttothememoryunit.（同基址相結(jié)合，用來確定送入內(nèi)存設(shè)備的物理內(nèi)存地址。）AppliedOperatingSystemConceptsAddressTranslationArchitectureAppliedOperatingSystemConceptsPagingExampleAppliedOperatingSystemConceptsImplementationofPageTablePagetableiskeptinmainmemory.（主存中的頁表）table

baseregister(PTBR)pointstothepagetable.（頁表基址寄存器指向頁表）tablelengthregister(PRLR)indicatessizeofthepagetable.（頁表限長寄存器表明頁表的長度）Inthisschemeeverydata/instructionaccessrequirestwomemoryaccesses.Oneforthepagetableandoneforthedata/instruction.（在這個機制中，每一次的數(shù)據(jù)/指令存取需要兩次內(nèi)存存取，一次是存取頁表，一次是存取數(shù)據(jù)）Thetwomemoryaccessproblemcanbesolvedbytheuseofaspecialfast-lookuphardwarecachecalledassociativeregistersortranslationlook-asidebuffers

(TLBs).(通過一個聯(lián)想寄存器，可以解決兩次存取的問題）AppliedOperatingSystemConceptsAssociativeRegisterAssociativeregisters–parallelsearch（聯(lián)想寄存器—并行查找）

Addresstranslation(A′,A′′)（地址轉(zhuǎn)換）IfA′isinassociativeregister,getframe#out.（如果A’在聯(lián)想寄存器中，把頁框#取出來。）Otherwisegetframe#frompagetableinmemory.（否則從內(nèi)存中的頁表中取出頁框#。）Page#Frame#AppliedOperatingSystemConceptsEffectiveAccessTimeAssociativeLookup=timeunit（聯(lián)想寄存器的查找需要時間）Assumememorycycletimeis1microsecond（假設(shè)內(nèi)存一次存取要1微秒）Hitration–percentageoftimesthatapagenumberisfoundintheassociativeregisters;rationrelatedtonumberofassociativeregisters.（命中率—在聯(lián)想寄存器中找到頁號的比率，比率與聯(lián)想寄存器的大小有關(guān)。）Hitratio=EffectiveAccessTime(EAT)（有效存取時間）

EAT=(1+)+(2+)(1–) =2+–

AppliedOperatingSystemConceptsMemoryProtectionMemoryprotectionimplementedbyassociatingprotectionbitwitheachframe.（內(nèi)存的保護由與每個頁框相連的保護位來執(zhí)行。）Valid-invalidbitattachedtoeachentryinthepagetable（有效-無效位附在頁表的每個表項中）:“valid”indicatesthattheassociatedpageisintheprocess’logicaladdressspace,andisthusalegalpage.（“有效”表明相關(guān)的頁在進程的邏輯地址空間，以及是一個合法的頁。）“invalid”indicatesthatthepageisnotintheprocess’logicaladdressspace.（“無效”表明頁不在進程的邏輯地址空間中。）AppliedOperatingSystemConceptsTwo-LevelTableSchemeAppliedOperatingSystemConceptsTwo-LevelPagingExampleAlogicaladdress(on32-bitmachinewith4Kpagesize)isdividedinto（一個邏輯地址被分為）:apagenumberconsistingof20bits.（一個20位的頁號。）apageoffsetconsistingof12bits.（一個12位的偏移。）Sincethepagetableispaged,thepagenumberisfurtherdividedinto（頁表頁被分為）:a10-bitpagenumber.（一個10位的頁號。）a10-bitpageoffset.（一個10位的偏移。）Thus,alogicaladdressisasfollows（因此，一個邏輯地址表示如下）:

wherepiisanindexintotheouterpagetable,andp2isthedisplacementwithinthepageoftheouterpagetable.pagenumberpageoffsetpip2d101012AppliedOperatingSystemConceptsAddress-TranslationSchemeAddress-translationschemeforatwo-level32-bitpagingarchitecture（一個兩級32位分頁結(jié)構(gòu)的地址轉(zhuǎn)換機制）AppliedOperatingSystemConceptsMultilevelPagingandPerformanceSinceeachlevelisstoredasaseparatetableinmemory,coveringalogicaladdresstoaphysicalonemaytakefourmemoryaccesses.（由于每一級都分開的以表的形式存儲在內(nèi)存中，把一個邏輯地址轉(zhuǎn)換為一個物理地址可能要進行4次內(nèi)存存取。）Eventhoughtimeneededforonememoryaccessisquintupled,cachingpermitsperformancetoremainreasonable.（盡管每次內(nèi)存存取的時間是很大的，高速緩存使執(zhí)行的時間還是可以接受的。）Cachehitrateof98percentyields（緩存的命中率使98%）則:

effectiveaccesstime=0.98x120+0.02x520 =128nanoseconds.

whichisonlya28percentslowdowninmemoryaccesstime.（這只把內(nèi)存存取時間降低了28%。）AppliedOperatingSystemConceptsInvertedPageTableOneentryforeachrealpageofmemory.（一個內(nèi)存中頁的表項。）Entryconsistsofthevirtualaddressofthepagestoredinthatrealmemorylocation,withinformationabouttheprocessthatownsthatpage.（表項包含真正內(nèi)存地址的頁的虛擬地址，它包括擁有這個頁的進程的信息。）Decreasesmemoryneededtostoreeachpagetable,butincreasestimeneededtosearchthetablewhenapagereferenceoccurs.（減少內(nèi)存需要儲存每個頁表，但是當(dāng)訪問一個頁時，尋找頁表需要增加時間。）Usehashtabletolimitthesearchtoone—oratmostafew—tableentries.（使用哈希表來減少搜索。）AppliedOperatingSystemConceptsInvertedPageTableArchitectureAppliedOperatingSystemConceptsSharedPagesSharedcode（共享代碼）Onecopyofread-only(reentrant)codesharedamongprocesses(i.e.,texteditors,compilers,windowsystems).（一個只讀（可再入）代碼可由進程共享。）Sharedcodemustappearinsamelocationinthelogicaladdressspaceofallprocesses.（共享代碼出現(xiàn)在所有進程的邏輯地址空間的相同位置。）Privatecodeanddata（私有代碼和數(shù)據(jù)）Eachprocesskeepsaseparatecopyofthecodeanddata.（每個進程保留一個代碼和數(shù)據(jù)的私有拷貝。）Thepagesfortheprivatecodeanddatacanappearanywhereinthelogicaladdressspace.（私有代碼和數(shù)據(jù)的頁可以出現(xiàn)在邏輯地址空間的任何地方。）AppliedOperatingSystemConceptsSharedPagesExampleAppliedOperatingSystemConceptsSegmentationMemory-managementschemethatsupportsuserviewofmemory.（內(nèi)存管理機制支持用戶觀點的內(nèi)存。）Aprogramisacollectionofsegments.Asegmentisalogicalunitsuchas（一個程序是一些段的集合，一個段是一個邏輯單位，如：）:

mainprogram, procedure, function, localvariables,globalvariables, commonblock, stack, symboltable,arraysAppliedOperatingSystemConceptsLogicalViewofSegmentation13241423userspacephysicalmemoryspaceAppliedOperatingSystemConceptsSegmentationArchitectureLogicaladdressconsistsofatwotuple（一個邏輯地址是兩個向量的集合）: <segment-number,offset>,Segmenttable–mapstwo-dimensionalphysicaladdresses;eachtableentryhas（段表-映射二維物理地址，每個表項包括）:base–containsthestartingphysicaladdresswherethesegmentsresideinmemory.（基址-包括內(nèi)存中段物理地址的起始地址。）limit–specifiesthelengthofthesegment.（限長-指定段的長度。）Segment-tablebaseregister(STBR)pointstothesegmenttable’slocationinmemory.（段表基址寄存器指向段表在內(nèi)存中的地址。）Segment-tablelengthregister(STLR)indicatesnumberofsegmentsusedbyaprogram;（段表限長寄存器表明被一個程序所使用的段的數(shù)目。）

segmentnumbersislegalifs<STLR.AppliedOperatingSystemConceptsSegmentationArchitecture(Cont.)Relocation.（重定位）dynamic（動態(tài)）bysegmenttable（由段表來執(zhí)行）Sharing.（共享）sharedsegments（共享的段）samesegmentnumber（同樣的段號）Allocation.（分配）firs