操作系統(tǒng)原理：CH09-Memory Management

Module9:MemoryManagementBackground（背景）LogicalversusPhysicalAddressSpace（邏輯與物理地址空間）ContiguousAllocation（連續(xù)分配）Paging（分頁） Segmentation（分段）SegmentationwithPaging（段頁式）Swapping（交換）存儲層次結構

BackgroundBackgroundProgrammustbebroughtintomemoryandplacedwithinaprocessforittobeexecuted.（程序必需放入一個進程，并且送入內(nèi)存才能被執(zhí)行）Inputqueue–collectionofprocessesonthediskthatarewaitingtobebroughtintomemoryforexecution.（輸入隊列—磁盤上等待進入內(nèi)存并執(zhí)行的進程的集合）Userprogramsgothroughseveralstepsbeforebeingexecuted.（用戶程序在執(zhí)行之前必需經(jīng)歷很多步驟）Background源程序編譯目標模塊庫…..鏈接程序裝入模塊裝入程序內(nèi)存Logicalvs.PhysicalAddressSpace重定位

Theconceptofalogicaladdressspacethatisboundtoaseparatephysical

addressspaceiscentraltopropermemorymanagement.（邏輯地址空間的概念同物理地址空間相關聯(lián)，它是正確內(nèi)存管理的中心。）Logicaladdress–generatedbytheCPU;alsoreferredtoasvirtualaddress.（邏輯地址—由CPU產(chǎn)生；也叫做虛擬空間。）Physicaladdress–addressseenbythememoryunit.（物理地址—內(nèi)存設備所讀入的地址）Logicalandphysicaladdressesarethesameincompile-timeandload-timeaddress-bindingschemes;logical(virtual)andphysicaladdressesdifferinexecution-timeaddress-bindingscheme.（邏輯和物理地址在編譯時期和裝入時期的地址綁定策略是相同的，而在執(zhí)行時間的地址綁定策略是不同的。）BindingofInstructionsandDatatoMemoryCompiletime（編譯時期）:Ifmemorylocationknownapriori,absolutecodecanbegenerated;mustrecompilecodeifstartinglocationchanges.（如果內(nèi)存位置已知，可生成絕對代碼；如果開始位置改變，需要重新編譯代碼）Loadtime（裝入時期）:Mustgeneraterelocatablecodeifmemorylocationisnotknownatcompiletime.（如果存儲位置在編譯時不知道，則必須生成可重定位代碼）Executiontime（執(zhí)行時期）:Bindingdelayeduntilruntimeiftheprocesscanbemovedduringitsexecutionfromonememorysegmenttoanother.Needhardwaresupportforaddressmaps(e.g.,baseandlimitregisters).（如果進程在執(zhí)行時可以在內(nèi)存中移動，則地址綁定要延遲到運行時。需要硬件對地址映射的支持，例如基址和限長寄存器）Addressbindingofinstructionsanddatatomemoryaddressescan

happenatthreedifferentstages.（指令和數(shù)據(jù)綁定到內(nèi)存地址可以在三個不同的階段發(fā)生。）地址重定位將程序裝入到與其地址空間不一致的物理空間，所引起的一系列地址變換過程。靜態(tài)地址重定位在裝入一個作業(yè)時，把作業(yè)中的指令地址全部轉(zhuǎn)換為絕對地址,在作業(yè)執(zhí)行過程中就無須再進行地址轉(zhuǎn)換工作。動態(tài)地址重定位：動態(tài)地址重地位是在程序執(zhí)行過程中，在CPU訪問內(nèi)存之前,將要訪問的程序或數(shù)據(jù)地址轉(zhuǎn)換成內(nèi)存地址.動態(tài)重定位依靠硬件地址變換機構完成。Memory-ManagementUnit(MMU)Hardwaredevicethatmapsvirtualtophysicaladdress.（硬件把虛擬地址映射到物理地址）InMMUscheme,thevalueintherelocationregisterisaddedtoeveryaddressgeneratedbyauserprocessatthetimeitissenttomemory.（在MMU策略中，基址寄存器中的值在其送入內(nèi)存的時候被加入到用戶進程所產(chǎn)生的每個地址中。）Theuserprogramdealswithlogicaladdresses;itneverseestherealphysicaladdresses.（用戶程序所對應到的是邏輯地址，物理地址對它從來都不可見。）Memory-ManagementUnit(MMU)OverlaysKeepinmemoryonlythoseinstructionsanddatathatareneededatanygiventime.（只是在內(nèi)存中保留那些在特定時間所需要的指令和數(shù)據(jù)）Neededwhenprocessislargerthanamountofmemoryallocatedtoit.（當進程比所分配的內(nèi)存大時，覆蓋是必需的）Implementedbyuser,nospecialsupportneededfromoperatingsystem,programmingdesignofoverlaystructureiscomplex.（由用戶執(zhí)行，不需要操作系統(tǒng)的特別支持，覆蓋結構的程序設計很復雜。）要求用戶清楚地了解程序的結構，并指定各程序段調(diào)入內(nèi)存的先后次序，它是一種早期的主存擴充的方式OverlaysDynamicLoadingRoutineisnotloadeduntilitiscalled.（例程在調(diào)用之前并不執(zhí)行）Bettermemory-spaceutilization;unusedroutineisneverloaded.（更好的內(nèi)存空間利用率；沒有被使用的例程不被載入。）Usefulwhenlargeamountsofcodeareneededtohandleinfrequentlyoccurringcases.（當需要大量的代碼來處理不經(jīng)常發(fā)生的事情時是非常有用的。）Nospecialsupportfromtheoperatingsystemisrequiredimplementedthroughprogramdesign.（不需要操作系統(tǒng)的特別支持，通過程序設計實現(xiàn)）DynamicLinkingLinkingpostponeduntilexecutiontime.（鏈接被推遲到執(zhí)行時期）Smallpieceofcode,stub,usedtolocatetheappropriatememory-residentlibraryroutine.（小的代碼片-存根，用來定位合適的保留在內(nèi)存中的庫程序。）Stubreplacesitselfwiththeaddressoftheroutine,andexecutestheroutine.（存根用例程地址來替換自己，以及執(zhí)行例程。）Operatingsystemneededtocheckifroutineisinprocesses’memoryaddress.（操作系統(tǒng)需要檢查例程是否在進程的內(nèi)存空間）SwappingAprocesscanbeswappedtemporarilyoutofmemorytoabackingstore,andthenbroughtbackintomemoryforcontinuedexecution.（一個進程可以暫時被交換到內(nèi)存外的一個備份區(qū)，隨后可以被換回內(nèi)存繼續(xù)執(zhí)行。）Backingstore–fastdisklargeenoughtoaccommodatecopiesofallmemoryimagesforallusers;mustprovidedirectaccesstothesememoryimages.（備份區(qū)—是一個固定的足夠大的可以容納所有用戶內(nèi)存映像的拷貝；可以提供對這些內(nèi)存映像的直接存取。）由操作系統(tǒng)控制，利用外存空間（進程交換區(qū)），通過對進程實體的整體交換，來滿足用戶進程的內(nèi)存需要。它的主要特點是打破了進程運行的駐留性SwappingRollout,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中，可以找到一些被修正過的交換措施。）SchematicViewofSwapping存儲管理方式連續(xù)分配方式：為一個程序分配一段連續(xù)的內(nèi)存空間，主要有：單一連續(xù)區(qū)管理方式；多分區(qū)管理方式，是一種可用于多道程序的較簡單的存儲管理方式，又分為:固定分區(qū)方式可變分區(qū)方式ContiguousAllocationMainmemoryusuallydividedintotwopartitions:（主存通常被分為兩部分）Residentoperatingsystem,usuallyheldinlowmemorywithinterruptvector.（為操作系統(tǒng)保留的部分，通常用中斷矢量保存在內(nèi)存低端。）Userprocessesthenheldinhighmemory.（用戶進程保存在內(nèi)存高端。）ContiguousAllocationSingle-partitionallocation（單獨分區(qū)分配）用戶區(qū)只能容納一道作業(yè)Relocation-registerschemeusedtoprotectuserprocessesfromeachother,andfromchangingoperating-systemcodeanddata.（基址寄存器策略由來保護用戶進程（同其他進程和改變的操作系統(tǒng)代碼和數(shù)據(jù)分開。）Relocationregistercontainsvalueofsmallestphysicaladdress;limitregistercontainsrangeoflogicaladdresses–eachlogicaladdressmustbelessthanthelimitregister.（基址寄存器包含最小物理地址的值；限長寄存器包含邏輯地址的范圍，每個邏輯地址必需比限長寄存器的值小。）ContiguousAllocation固定分區(qū)(FixedPartitioning)分配固定式分區(qū)是在作業(yè)裝入之前，內(nèi)存就被劃分成若干個固定大小的連續(xù)分區(qū)。劃分工作可以由系統(tǒng)管理員完成，也可以由操作系統(tǒng)實現(xiàn)。一旦劃分完成，在系統(tǒng)運行期間不再重新劃分，即分區(qū)的個數(shù)不可變，分區(qū)的大小不可變，所以，固定式分區(qū)又稱為靜態(tài)分區(qū)。劃分分區(qū)的方法如下：分區(qū)大小相等：只適用于多個相同程序的并發(fā)執(zhí)行（處理多個類型相同的對象），缺乏靈活性。分區(qū)大小不等：多個小分區(qū)、適量的中等分區(qū)、少量的大分區(qū)。根據(jù)程序的大小，分配當前空閑的、適當大小的分區(qū)。固定分區(qū)(大小相同)固定分區(qū)(多種大小)

固定分區(qū)(FixedPartitioning)分配一般將內(nèi)存的用戶區(qū)域劃分成大小不等的分區(qū)，可適應不同大小的作業(yè)的需要系統(tǒng)有一張分區(qū)說明表，每個表目說明一個分區(qū)的大小、起始地址和是否已分配的使用標志分區(qū)說明表和內(nèi)存分配圖如下所示。區(qū)號大小起址標志116K20K已分配232K36K已分配364K68K已分配4124K132K未分配分區(qū)說明表內(nèi)存分配圖固定分區(qū)分配優(yōu)點：易于實現(xiàn)，開銷小。缺點：分區(qū)大小固定:內(nèi)碎片分區(qū)總數(shù)固定:限制并發(fā)執(zhí)行的進程數(shù)目。采用的數(shù)據(jù)結構：分區(qū)表－－記錄分區(qū)的大小和使用情況ContiguousAllocation(Cont.)Multiple-partitionallocation（多分區(qū)分配）分區(qū)的劃分是動態(tài)的,不是預先確定的Hole–blockofavailablememory;holesofvarioussizearescatteredthroughoutmemory.（分區(qū)—可用的內(nèi)存塊，不同大小的分區(qū)分布在整個內(nèi)存中。）Whenaprocessarrives,itisallocatedmemoryfromaholelargeenoughtoaccommodateit.（當一個進程到來的時候，它將從一個足夠容納它分區(qū)中分配內(nèi)存。）Operatingsystemmaintainsinformationabout（操作系統(tǒng)包含以下信息）:a)allocatedpartitions（分配的分區(qū)）b)freepartitions(hole)（空的分區(qū)）OSprocess5process8process2OSprocess5process2OSprocess5process2OSprocess5process9process2process9process10空閑分區(qū)的管理序號大小起址狀態(tài)148K116K空閑2252K260K空閑3空表目4空表目5空表目空閑分區(qū)表N個字節(jié)可用前向指針后向指針空閑分區(qū)鏈ContiguousAllocation(Cont.)可變分區(qū)分配分區(qū)分配算法：尋找某個空閑分區(qū)，其大小需大于或等于程序的要求。若是大于要求，則將該分區(qū)分割成兩個分區(qū)，其中一個分區(qū)為要求的大小并標記為“占用”，而另一個分區(qū)為余下部分并標記為“空閑”。分區(qū)的先后次序通常是從內(nèi)存低端到高端。分區(qū)釋放算法：需要將相鄰的空閑分區(qū)合并成一個空閑分區(qū)。(這時要解決的問題是：合并條件的判斷)DynamicStorage-AllocationProblemFirst-fit（首先適應）:Allocatethefirstholethatisbigenough.（分配最先找到的合適的分區(qū)。）Best-fit（最佳適應）:Allocatethesmallestholethatisbigenough;mustsearchentirelist,unlessorderedbysize.Producesthesmallestleftoverhole.（搜索整個序列，找到適合條件的最小的分區(qū)進行分配。）Worst-fit（最差適應）:Allocatethelargesthole;mustalsosearchentierlist.Producesthelargestleftoverhole.（搜索整個序列，尋找最大的分區(qū)進行分配。）Howtosatisfyarequestofsizenfromalistoffreeholes.（怎樣從一個空的分區(qū)序列中滿足一個申請需要。）First-fitandbest-fitbetterthanworst-fitintermsofspeedandstorageutilization.（在速度和存儲的利用上，首先適應和最佳適應要比最差適應好。）首次適應算法（FirstFit）從空閑分區(qū)表的第一個表目開始查找，把找到的第一個滿足要求的空閑區(qū)分配給作業(yè)，目的在于減少查找時間。通常將空閑分區(qū)表（空閑區(qū)鏈）中的空閑分區(qū)要按地址由低到高進行排序。特點：分配和釋放的時間性能較好，較大的空閑分區(qū)可以被保留在內(nèi)存高端。隨著低端分區(qū)不斷劃分而產(chǎn)生較多小分區(qū)，每次分配時查找時間開銷會增大。在系統(tǒng)不斷地分配和回收中，必定會出現(xiàn)一些不連續(xù)的小的空閑區(qū)，稱為外碎片。雖然可能所有碎片的總和超過某一個作業(yè)的要求，但是由于不連續(xù)而無法分配。最佳適應算法（BestFit）從全部空閑區(qū)中找出能滿足作業(yè)要求的、且最小的空閑分區(qū).能使碎片盡量小為提高查找效率，空閑分區(qū)表（空閑區(qū)鏈）中的空閑分區(qū)要按從小到大進行排序，自表頭開始查找到第一個滿足要求的自由分區(qū)分配特點：從個別來看，外碎片較小，但從整體來看，會形成較多無法利用的碎片。較大的空閑分區(qū)可以被保留。動態(tài)分區(qū)分配算法舉例Lastallocatedblock(14K)分配前分配后8K8K12K12K22K18K6K6K8K8K14K14K6K2K36K20KFreeblock空閑區(qū)域Allocatedblock已分配區(qū)域BestFitFirstFit例：需分配一個16KB分區(qū)NextFit可變式分區(qū)的碎片問題:在系統(tǒng)不斷地分配和回收中，必定會出現(xiàn)一些不連續(xù)的小的空閑區(qū)，稱為外碎片。雖然可能所有碎片的總和超過某一個作業(yè)的要求，但是由于不連續(xù)而無法分配。解決碎片的方法是拼接（或稱緊湊），即向一個方向（例如向低地址端）移動已分配的作業(yè)，使那些零散的小空閑區(qū)在另一方向連成一片。分區(qū)的拼接技術，一方面要求能夠?qū)ψ鳂I(yè)進行重定位，另一方面系統(tǒng)在拼接時要耗費較多的時間。ContiguousAllocation(Cont.)FragmentationExternalfragmentation（外碎片）–totalmemoryspaceexiststosatisfyarequest,butitisnotcontiguous.（整個內(nèi)存空間用來滿足一個請求，但它不是連續(xù)的。）Internalfragmentation（內(nèi)碎片）–allocatedmemorymaybeslightlylargerthanrequestedmemory;thissizedifferenceismemoryinternaltoapartition,butnotbeingused.（分配的內(nèi)存可能比申請的內(nèi)存大一點，這兩者之間的差別是內(nèi)部不被使用的簇）Reduceexternalfragmentationbycompaction（通過緊縮來減少外碎片）Shufflememorycontentstoplaceallfreememorytogetherinonelargeblock.（把一些小的空閑內(nèi)存結合成一個大的塊。）Compactionispossibleonlyifrelocationisdynamic,andisdoneatexecutiontime.（只有重定位是動態(tài)的時候，才有可能進行緊縮，緊縮在執(zhí)行時期進行）I/Oproblem（I/O問題）LatchjobinmemorywhileitisinvolvedinI/O.（當I/O的時候，把工作鎖定在內(nèi)存中。）DoI/OonlyintoOSbuffers.（只對操作系統(tǒng)的緩沖區(qū)進行I/O。）Fragmentation實現(xiàn)緊湊的技術必須獲得硬件支持。只有具有動態(tài)重定位硬件機構的計算機系統(tǒng)，才有可能采用動態(tài)重定位可變分區(qū)管理技術，系統(tǒng)的硬件包括重定位寄存器和加法器。paging分頁存儲管理是解決存儲碎片的一種方法。動態(tài)重定位是解決存儲碎片問題的一種途徑，但要移動大量信息從而浪費處理機時間,代價比較高,這是因為這種分配要求把作業(yè)必須安置在一連續(xù)存儲區(qū)內(nèi)的緣故,而分頁存儲管理正是要避開這種連續(xù)性要求。PagingLogicaladdressspaceofaprocesscanbenoncontiguous;processisallocatedphysicalmemorywheneverthelatterisavailable.（進程的邏輯地址空間可能是不連續(xù)的，如果有可用的物理內(nèi)存，它將分給進程。）Dividephysicalmemoryintofixed-sizedblockscalledframes(sizeispowerof2,between512bytesand8192bytes).（把物理內(nèi)存分成大小固定的塊。）Dividelogicalmemoryintoblocksofsamesizecalledpages.（把邏輯內(nèi)存也分為固定大小的塊，叫做頁。）Keeptrackofallfreeframes.（保留一個頁的記錄。）Torunaprogramofsizenpages,needtofindnfreeframesandloadprogram.（運行一個有N頁大小的程序，需要找到N個空的頁框讀入程序。）Setupapagetabletotranslatelogicaltophysicaladdresses.（建立一個頁表，把邏輯地址轉(zhuǎn)換為物理地址。）Internalfragmentation.（內(nèi)碎片。）PagingExampleAddressTranslationSchemeAddressgeneratedbyCPUisdividedinto（CPU產(chǎn)生的地址被分為）:Pagenumber

(p)（頁號）–usedasanindexintoapage

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

(d)（偏移）–combinedwithbaseaddresstodefinethephysicalmemoryaddressthatissenttothememoryunit.（同基址相結合，用來確定送入內(nèi)存設備的物理內(nèi)存地址。）Forgivenlogicaladdressspace2mandpagesize2npagenumberpageoffsetpdm-nnAddressTranslationArchitecture地址結構圖中的地址長度為32位，允許地址空間的大小最多為1M個頁。P=A/L（整除）W=AMODL（取余）程序經(jīng)過編譯鏈接后形成邏輯地址，對某特定機器其地址結構是一定的。若給定一個邏輯地址為A(十進制)，頁面大小為L，則頁號P和頁內(nèi)地址W可按下式求得：PagingExampleImplementationofPageTablePagetableiskeptinmainmemory.（頁表被保存在主存中）table

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

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

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

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

EffectiveAccessTime例如，假設檢索聯(lián)想存儲器的時間為20ns，訪問內(nèi)存的時間為100ns，訪問聯(lián)想存儲器的命中率為85%，則CPU存取一個數(shù)據(jù)的平均時間:T=0.85*120+0.15*220=135ns，訪問時間只增加35%。如果不引入聯(lián)想存儲器，其訪問將延長一倍（達200ns）。

基本的地址變換機構實現(xiàn)從邏輯地址到物理地址的轉(zhuǎn)換:將用戶程序中的頁號變換成內(nèi)存中的物理塊號地址變換機構：頁表寄存器有效地址寄存器（邏輯地址寄存器）物理地址寄存器頁表PCB中增加存放頁表始址和頁表長度的項地址變換過程按頁的大小分離出頁號和位移量，放入有效地址寄存器中將頁號與頁表長度進行比較，如果頁號大于頁表長度，越界中斷；以頁號為索引查找頁表:將頁表始址與頁號和頁表項長度的乘積相加，便得到該表項在頁表中的位置，于是可從中得到該頁的物理塊號；將該物理塊號裝入物理地址寄存器的高址部分；將有效地址寄存器中的位移量直接復制到物理地址寄存器的低位部分，從而形成內(nèi)存地址。分頁地址變換機構工作原理頁式地址變換舉例頁式地址變換虛地址（邏輯地址、程序地址）以十六進制、八進制、二進制的形式給出將虛地址轉(zhuǎn)換成二進制的數(shù)；按頁的大小分離出頁號和位移量（低位部分是位移量，高位部分是頁號）；將位移量直接復制到內(nèi)存地址寄存器的低位部分；以頁號查頁表，得到對應頁裝入內(nèi)存的塊號，并將塊號轉(zhuǎn)換成二進制數(shù)填入地址寄存器的高位部分，從而形成內(nèi)存地址。頁式地址變換虛地址以十進制數(shù)給出頁號＝虛地址％頁大小位移量＝虛地址

mod頁大小以頁號查頁表，得到對應頁裝入內(nèi)存的塊號內(nèi)存地址＝塊號×頁大小＋位移量頁式地址變換舉例例1：有一系統(tǒng)采用頁式存儲管理，有一作業(yè)大小是8KB，頁大小為2KB，依次裝入內(nèi)存的第7、9、A、5塊，試將虛地址0AFEH，1ADDH轉(zhuǎn)換成內(nèi)存地址。虛地址0AFEH0000101011111110P＝1W＝01011111110MR＝0100101011111110＝4AFEH頁式地址變換舉例虛地址1ADDH0001101011011101P＝3W＝01011011101MR＝0010101011011101＝2ADDH頁式地址變換舉例例2：有一系統(tǒng)采用頁式存儲管理，有一作業(yè)大小是8KB，頁大小為2KB，依次裝入內(nèi)存的第7、9、10、5塊，試將虛地址7145，3412轉(zhuǎn)換成內(nèi)存地址。頁式地址變換舉例虛地址3412P＝3412％2048＝1W＝3412mod2048＝1364MR=9*2048+1364=19796虛地址3412的內(nèi)存地址是：19796頁式地址變換舉例虛地址7145P＝7145％2048＝3W＝7145mod2048＝1001MR=5*2048+1001=11241虛地址7145的內(nèi)存地址是：11241MemoryProtectionMemoryprotectionimplementedbyassociatingprotectionbitwitheachframe.（內(nèi)存的保護由與每個頁框相連的保護位來執(zhí)行。）Valid-invalidbitattachedtoeachentryinthepagetable（有效-無效位附在頁表的每個表項中）:“valid”indicatesthattheassociatedpageisintheprocess’logicaladdressspace,andisthusalegalpage.（“有效”表明相關的頁在進程的邏輯地址空間，以及是一個合法的頁。）“invalid”indicatesthatthepageisnotintheprocess’logicaladdressspace.（“無效”表明頁不在進程的邏輯地址空間中。）MemoryProtectionTwo-LevelTableScheme80386的邏輯地址有232B，如頁面大小為4KB（212B），則頁表項達1M個，設每個頁表項占用4B，則每個進程的頁表占用4MB內(nèi)存空間，還要求是連續(xù)的，顯然這是不現(xiàn)實的。解決:在80386中，為了減少頁表所占用的連續(xù)的內(nèi)存空間，采用了兩級頁表機制.Two-LevelTableScheme將頁表進行分頁。每個頁面的大小與內(nèi)存物理塊的大小相同，并為它們進行編號，可以離散地將各個頁面分別存放在不同的物理塊中，為此再建立一張頁表，稱為外層頁表（頁表目錄），即第一級頁表，其中的每個表目是存放某個頁表的物理地址。第二級才是頁表（其中每個物理塊上的頁表叫做頁表分頁），其中的每個表目所存放的才是頁的物理塊號。Two-LevelTableSchemeTwo-LevelPagingExampleAlogicaladdress(on32-bitmachinewith4Kpagesize)isdividedinto（一個邏輯地址被分為）:apagenumberconsistingof20bits.（一個20位的頁號。）apageoffsetconsistingof12bits.（一個12位的偏移。）Sincethepagetableispaged,thepagenumberisfurtherdividedinto（頁表頁被分為）:a10-bitpagenumber.（一個10位的頁號。）a10-bitpageoffset.（一個10位的偏移。）Thus,alogicaladdressisasfollows（因此，一個邏輯地址表示如下）:

wherepiisanindexintotheouterpagetable,andp2isthedisplacementwithinthepageoftheouterpagetable.pagenumberpageoffsetpip2d101012Address-TranslationSchemeAddress-translationschemeforatwo-level32-bitpagingarchitecture（一個兩級32位分頁結構的地址轉(zhuǎn)換機制）Three-levelPagingSchemeMultilevelPagingandPerformanceSinceeachlevelisstoredasaseparatetableinmemory,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%。）HashedPageTablesCommoninaddressspaces>32bitsThevirtualpagenumberishashedintoapagetableThispagetablecontainsachainofelementshashingtothesamelocationVirtualpagenumbersarecomparedinthischainsearchingforamatchIfamatchisfound,thecorrespondingphysicalframeisextractedHashedPageTableInvertedPageTable通常的頁表為每個進程設置一張頁表，其不足之處是浪費內(nèi)存空間解決：倒置頁表，按照整個物理內(nèi)存建造一張表Oneentryforeachrealpageofmemory.（內(nèi)存中的每一塊在表中占一項。）Entryconsistsofthevirtualaddressofthepagestoredinthatrealmemorylocation,withinformationabouttheprocessthatownsthatpage.（每項包含存儲在物理內(nèi)存的進程的邏輯頁號和進程標示。）Decreasesmemoryneededtostoreeachpagetable,butincreasestimeneededtosearchthetablewhenapagereferenceoccurs.（減少了頁表占用的內(nèi)存空間量,但是增加了查找表的時間，因為頁表是按物理塊的順序組織的，而查找是按虛地址進行的。）Usehashtabletolimitthesearchtoone—oratmostafew—tableentries.（使用哈希表來減少搜索。）InvertedPageTableArchitectureSharedPagesSharedcode（共享代碼）Onecopyofread-only(reentrant)codesharedamongprocesses(i.e.,texteditors,compilers,windowsystems).（一個只讀（可再入）代碼可由進程共享。）Sharedcodemustappearinsamelocationinthelogicaladdressspaceofallprocesses.（共享代碼出現(xiàn)在所有進程的邏輯地址空間的相同位置。）Privatecodeanddata（私有代碼和數(shù)據(jù)）Eachprocesskeepsaseparatecopyofthecodeanddata.（每個進程保留一個代碼和數(shù)據(jù)的私有拷貝。）Thepagesfortheprivatecodeanddatacanappearanywhereinthelogicaladdressspace.（私有代碼和數(shù)據(jù)的頁可以出現(xiàn)在邏輯地址空間的任何地方。）SharedPagesExample優(yōu)點：沒有外碎片，每個內(nèi)碎片不超過頁大小。一個程序不必連續(xù)存放。缺點：程序全部裝入內(nèi)存。純分頁的特點SegmentationMemory-managementschemethatsupportsuserviewofmemory.（內(nèi)存管理機制支持用戶觀點的內(nèi)存。）Aprogramisacollectionofsegments.Asegmentisalogicalunitsuchas（一個程序是一些段的集合，一個段是一個邏輯單位，如：）:

mainprogram, procedure, function, localvariables,globalvariables, commonblock, stack, symboltable,arraysUser’sViewofaProgramLogicalViewofSegmentation1423physicalmemoryspace1324userspaceSegmentationHardwareSegmentationArchitectureLogicaladdressconsistsofatwotuple（一個邏輯地址是兩個向量的集合）:

<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.ExampleofSegmentation地址變換過程系統(tǒng)將邏輯地址中的段號S與段表長度TL進行比較。若S≥TL，訪問越界；若未越界，則根據(jù)段表的始址和該段的段號，計算出該段對應段表項的位置，從中讀出該段在內(nèi)存中的起始地址；然后再檢查段內(nèi)地址d是否超過該段的段長SL。若超過，即d≥SL，同樣發(fā)出越界中斷信號；若未越界，則將該段的基址與段內(nèi)地址d相加，得到要訪問的內(nèi)存物理地址。地址變換SegmentationArchitecture(Cont.)Relocation.（重定位）dynamic（動態(tài)）bysegmenttable（由段表來執(zhí)行）Sharing.（共享）sharedsegments（共享的段）samesegmentnumber（同樣的段號）Allocation.（分配）firstfit/bestfit（首先/最佳適配）externalfragmentation（外碎片）SegmentationArchitecture(Cont.)Protection.Witheachentryinsegmenttableassociate（保護，每個段表的表項有）:validationbit（有效位）=0illegalsegmentread/write/executeprivileges（讀/寫/執(zhí)行權利）Protectionbitsassociatedwithsegments;codesharingoccursatsegmentlevel.（保護位同段相聯(lián)系，在段的級別進行代碼共享。）Sincesegmentsvaryinlength,memoryallocationisadynamicstorage-allocationproblem.（由于段的各個長度不同，內(nèi)存分配是一個動態(tài)存儲-分配問題。）Asegmentationexampleisshowninthefollowingdiagram（下面的是一個段的共享例子）程序通過分段(segmentation)劃分為多個模塊，如代碼段、數(shù)據(jù)段、共享段?？梢苑謩e編寫和編譯可以針對不同類型的段采取不同的保護可以按段為單位來進行共享，包括通過動態(tài)鏈接進行代碼共享優(yōu)點：沒有內(nèi)碎片，外碎片可以通過內(nèi)存緊縮來消除。便于改變進程占用空間的大小。缺點：進程全部裝入內(nèi)存。分段的特點分頁和分段比較SegmentationwithPaging段頁式分頁和分段存儲管理方式都各有其優(yōu)缺點。如果對兩種存儲管理方式“各取所長”后，則可以形成一種新的存儲管理方式的系統(tǒng)——段頁式系統(tǒng)。既具有分頁系統(tǒng)能有效地提高內(nèi)存利用率的優(yōu)點，又具有分段系統(tǒng)能很好地滿足用戶需要的長處，是一種有效的存儲管理方式。SegmentationwithPaging基本原