操作系統(tǒng)教學(xué)課件：Chapter 9 Memory Management

Chapter9MemoryManagement內(nèi)存是計(jì)算機(jī)系統(tǒng)的最重要的資源之一。為提高響應(yīng)速度及CPU的利用率，必須將多個(gè)進(jìn)程同時(shí)放入內(nèi)存，多進(jìn)程共享內(nèi)存。本章介紹內(nèi)存管理方法。內(nèi)存管理方法很多，但內(nèi)容主要涉及下述三個(gè)方面：內(nèi)存分配回收方法地址映射和重定位內(nèi)存保護(hù)內(nèi)存管理算法在不同的系統(tǒng)中有不同的方案，每種方案有自己的優(yōu)點(diǎn)與缺點(diǎn)，選擇某種方案取決于多種因素，尤其依賴于系統(tǒng)的硬件設(shè)計(jì)因素。Chapter9:MemoryManagementBackground（背景）LogicalversusPhysicalAddressSpace（邏輯與物理地址空間）Swapping（交換）ContiguousAllocation（連續(xù)分配）Paging（分頁(yè)） Segmentation（分段）SegmentationwithPaging（帶分頁(yè)的分段）BackgroundProgrammustbebroughtintomemoryandplacedwithinaprocessforittobeexecuted.（程序必需放入一個(gè)進(jìn)程，并且送入內(nèi)存才能被執(zhí)行）Inputqueue

–collectionofprocessesonthediskthatarewaitingtobebroughtintomemoryforexecution.（輸入隊(duì)列—磁盤上等待進(jìn)入內(nèi)存并執(zhí)行的進(jìn)程的集合）Userprogramsgothroughseveralstepsbeforebeingexecuted.（用戶程序在執(zhí)行之前必需經(jīng)歷很多步驟）2.4StorageHierarchyP34Storagesystemsorganizedinhierarchy.SpeedCostVolatilityCaching

–copyinginformationintofasterstoragesystem;mainmemorycanbeviewedasalastcacheforsecondarystorage.Storage-DeviceHierarchyBindingofInstructionsandDatatoMemory當(dāng)很多程序都要求程序調(diào)入內(nèi)存時(shí)：程序進(jìn)入等待隊(duì)列根據(jù)策略選擇一個(gè)進(jìn)入程序執(zhí)行時(shí)候，從內(nèi)存取得指令﹔執(zhí)行后，釋放所占有的內(nèi)存空間地址轉(zhuǎn)換的步驟：原始程序中地址位置：以符號(hào)表示編譯器：將符號(hào)所指的地址綁定（binding）到一可重新定址的相對(duì)地址鏈接器：將可重新定址的地址綁定到主存中的絕對(duì)物理地址

Addressbindingofinstructionsanddatatomemoryaddressescanhappenatthreedifferentstages.（指令和數(shù)據(jù)綁定到內(nèi)存地址可以在三個(gè)不同的階段發(fā)生。）

對(duì)于同一個(gè)指令而言，所謂的“地址”是隨著時(shí)間而改變的。

BindingofInstructionsandDatatoMemoryBindingofInstructionsandDatatoMemoryCompiletime（編譯階段）:Ifmemorylocationknownapriori,absolutecodecanbegenerated;mustrecompilecodeifstartinglocationchanges.編譯階段已經(jīng)確定程序要在內(nèi)存的某個(gè)物理地址執(zhí)行當(dāng)起始地址改變，程序必須重新編譯，以產(chǎn)生新的絕對(duì)地址。例，簡(jiǎn)單的引導(dǎo)代碼

org 07c00h ;告訴編譯器程序加載到7c00處

mov ax,cs mov ds,ax mov es,ax call DispStr ;調(diào)用顯示字符串例程

jmp $ ;無(wú)限循環(huán)DispStr: mov ax,BootMessage mov bp,ax ;ES:BP=串地址

mov cx,16 ;CX=串長(zhǎng)度

mov ax,01301h ;AH=13,AL=01h mov bx,000ch ;頁(yè)號(hào)為0(BH=0)黑底紅字(BL=0Ch,高亮) mov dl,0 int 10h ;10h號(hào)中斷

retBootMessage: db "Hello,OSworld!"times 510-($-$$) db 0 ;填充剩下的空間，使生成的二進(jìn)制代碼恰好為512字節(jié)dw 0xaa55 ;結(jié)束標(biāo)志BindingofInstructionsandDatatoMemoryLoadtime（載入階段）:Mustgeneraterelocatablecodeifmemorylocationisnotknownatcompiletime.載入階段不知道程序?qū)⒃趦?nèi)存何處執(zhí)行程序必須編譯成可重新定址的程序代碼，但起始地址改變必須重新改變靜態(tài)重定位BindingofInstructionsandDatatoMemoryExecutiontime（執(zhí)行階段）:Bindingdelayeduntilruntimeiftheprocesscanbemovedduringitsexecutionfromonememorysegmenttoanother.Needhardwaresupportforaddressmaps(e.g.,baseandlimitregisters).執(zhí)行階段如果在執(zhí)行時(shí)，程序會(huì)從一個(gè)地址移動(dòng)到另一塊地址﹔或是含有執(zhí)行時(shí)才能確定的數(shù)據(jù)地址動(dòng)態(tài)重定位BindingofInstructionsandDatatoMemory數(shù)據(jù)和指令binding可在三個(gè)階段中的任意階段中執(zhí)行

編譯和載入的地址綁定，采用靜態(tài)載入和靜態(tài)重定位，程序大小受實(shí)際內(nèi)存大小限制執(zhí)行時(shí)的地址綁定，采用動(dòng)態(tài)載入和動(dòng)態(tài)綁定，動(dòng)態(tài)載入時(shí)，所有例程都以邏輯地址可重定位方式存儲(chǔ)在磁盤上DynamicLoadingRoutineisnotloadeduntilitiscalled.（例程在調(diào)用之前并不執(zhí)行）Bettermemory-spaceutilization;unusedroutineisneverloaded.(更好的內(nèi)存空間利用率；沒有被使用的例程不被載入。）Usefulwhenlargeamountsofcodeareneededtohandleinfrequentlyoccurringcases.（當(dāng)需要大量的代碼來(lái)處理不經(jīng)常發(fā)生的事情時(shí)是非常有用的。）Nospecialsupportfromtheoperatingsystemisrequiredimplementedthroughprogramdesign.(不需要操作系統(tǒng)的特別支持）DynamicLoadingLogicalandphysicaladdressesarethesameincompile-timeandload-timeaddress-bindingschemes;logical(virtual)andphysicaladdressesdifferinexecution-timeaddress-bindingscheme.（邏輯和物理地址在編譯時(shí)期和載入時(shí)期的地址綁定策略中是相同的，而在執(zhí)行時(shí)間的地址綁定策略中是不同的。）DynamicLinkingLinkingpostponeduntilexecutiontime.（鏈接被推遲到執(zhí)行時(shí)期）Smallpieceofcode,stub,usedtolocatetheappropriatememory-residentlibraryroutine.（小的代碼片、存根，用來(lái)定位合適的保留在內(nèi)存中的庫(kù)程序。）Stubreplacesitselfwiththeaddressoftheroutine,andexecutestheroutine.（存根用例程地址來(lái)替換自己，以及執(zhí)行例程。）Operatingsystemneededtocheckifroutineisinprocesses’memoryaddress.（操作系統(tǒng)需要檢查例程是否在進(jìn)程的內(nèi)存空間）程式執(zhí)行前的處理過(guò)程原始程序printf.c原始程式main.c目標(biāo)文件printf.o目標(biāo)文件main.o編譯器鏈接編譯器其他庫(kù)文件裝載main裝載器內(nèi)存StaticrelocationanddynamicrelocationStaticrelocation靜態(tài)重定位，由載入程序把用戶程序中的指令和數(shù)據(jù)的地址全部轉(zhuǎn)換成內(nèi)存中的絕對(duì)地址。程序執(zhí)行時(shí)無(wú)需進(jìn)行地址轉(zhuǎn)換。靜態(tài)重定位不需要硬件支持，但不允許程序在主存移動(dòng)Dynamicrelocation動(dòng)態(tài)重定位靠硬件的地址轉(zhuǎn)換機(jī)構(gòu)實(shí)現(xiàn)（MMU）Logicalvs.PhysicalAddressSpaceTheconceptofalogicaladdressspacethatisboundtoaseparatephysical

addressspaceiscentraltopropermemorymanagement.（邏輯地址空間與物理地址空間相相綁定）Logicaladdress

–generatedbytheCPU;alsoreferredtoasvirtualaddress.（邏輯地址—由CPU產(chǎn)生，也叫做虛擬空間。）Physicaladdress

–addressseenbythememoryunit.（物理地址—內(nèi)存單元所見的地址，內(nèi)存的內(nèi)存地址寄存器）編譯時(shí)地址綁定和裝載時(shí)地址綁定產(chǎn)生相同的邏輯地址和物理地址，執(zhí)行時(shí)地址綁定產(chǎn)生的邏輯地址與物理地址不同Memory-ManagementUnit(MMU)Hardwaredevicethatmapsvirtualtophysicaladdress.（硬件把虛擬地址映射到物理地址）InMMUscheme,thevalueintherelocationregisterisaddedtoeveryaddressgeneratedbyauserprocessatthetimeitissenttomemory.（在MMU策略中，基址寄存器中的值在其送入內(nèi)存的時(shí)候，與由一個(gè)用戶進(jìn)程所產(chǎn)生的每個(gè)地址的值相加）Theuserprogramdealswithlogicaladdresses;itneverseestherealphysicaladdresses.（用戶程序所對(duì)應(yīng)到的是邏輯地址，物理地址對(duì)它從來(lái)都不可見。）Logicalvs.PhysicalAddressSpace執(zhí)行程序時(shí)，邏輯地址與物理地址的轉(zhuǎn)換裝載器（loader）：在主存中尋找一塊可供使用的使用的內(nèi)存空間來(lái)存儲(chǔ)程序基址寄存器（baseregister）：又名重定向寄存器，存放邏輯地址轉(zhuǎn)換成物理地址的基底值內(nèi)存管理單元（memorymanagementunit,MMU）：負(fù)責(zé)將邏輯地址加上基址，以轉(zhuǎn)換成物理地址。MMUOverlaysNeededwhenprocessislargerthanamountofmemoryallocatedtoit.（當(dāng)進(jìn)程比所分配的內(nèi)存大時(shí)，覆蓋是必需的）Implementedbyuser,nospecialsupportneededfromoperatingsystem,programmingdesignofoverlaystructureiscomplex.(由用戶執(zhí)行，不需要操作系統(tǒng)的特別支持，覆蓋結(jié)構(gòu)的程序設(shè)計(jì)很復(fù)雜。）Fig9.3Overlays目的：解決內(nèi)存的容量限制做法：Keepinmemoryonlythoseinstructionsanddatathatareneededatanygiventime.在編譯時(shí)，將程序與數(shù)據(jù)分成多個(gè)獨(dú)立的區(qū)域；在執(zhí)行的時(shí)候，在內(nèi)存中保留需要的區(qū)域。Overlays缺陷：

多重重疊：造成程序員負(fù)擔(dān)，一般避免使用，因?yàn)椋簠^(qū)域分割太多置換次數(shù)過(guò)多降低程序執(zhí)行效率區(qū)域分割太少可重疊的程序部分過(guò)少內(nèi)存可能不夠，系統(tǒng)效能降低除外：嵌入式系統(tǒng)（內(nèi)存有限，沒有虛擬存儲(chǔ)系統(tǒng)）SwappingMotive:系統(tǒng)無(wú)足夠空間容納所有的程序Method:非執(zhí)行中的程序暫時(shí)移到備份存儲(chǔ)，要執(zhí)行的時(shí)候在搬回備份存儲(chǔ)：一般而言指diskAprocesscanbeswappedtemporarilyoutofmemorytoabackingstore,andthenbroughtbackintomemoryforcontinuedexecution.（一個(gè)進(jìn)程可以暫時(shí)被交換到內(nèi)存外的一個(gè)備份區(qū)，隨后可以被換回內(nèi)存繼續(xù)執(zhí)行。）交換方式：Rollout,rollin–swappingvariantusedforpriority-basedschedulingalgorithms;lower-priorityprocessisswappedoutsohigher-priorityprocesscanbeloadedandexecuted.（滾入，滾出—交換由于基于優(yōu)先級(jí)的算法而不同，低優(yōu)先級(jí)的進(jìn)程被換出，這樣高優(yōu)先級(jí)的進(jìn)程可以被載入和執(zhí)行。）Majorpartofswaptimeistransfertime;totaltransfertimeisdirectlyproportionaltotheamountofmemoryswapped.（交換時(shí)間的主要部分是轉(zhuǎn)移時(shí)間，總的轉(zhuǎn)移時(shí)間直接同交換的內(nèi)存的數(shù)量成比例。）SwappingSchematicViewofSwappingSchematicViewofSwapping缺陷：產(chǎn)生切換的額外負(fù)擔(dān)時(shí)間浪費(fèi)在資料傳輸上為了提高效率程序必須隨時(shí)告知程序?qū)?nèi)存的要求ContiguousAllocation連續(xù)分配Mainmemoryusuallydividedintotwopartitions:（主存通常被分為兩部分）Residentoperatingsystem,usuallyheldinlowmemorywithinterruptvector.（為操作系統(tǒng)保留的部分，通常用中斷矢量保存在內(nèi)存低端。）Userprocessesthenheldinhighmemory.（用戶進(jìn)程保存在內(nèi)存高端。）ContiguousAllocationSingle-partitionallocation（單獨(dú)分區(qū)分配）Relocation-registerschemeusedtoprotectuserprocessesfromeachother,andfromchangingoperating-systemcodeanddata.（基址寄存器策略由來(lái)保護(hù)用戶進(jìn)程（同其他進(jìn)程和改變的操作系統(tǒng)代碼和數(shù)據(jù)分開。）Relocationregistercontainsvalueofsmallestphysicaladdress;limitregistercontainsrangeoflogicaladdresses–eachlogicaladdressmustbelessthanthelimitregister.（基址寄存器包含最小物理地址的值；限長(zhǎng)寄存器包含邏輯地址的范圍，每個(gè)邏輯地址必需比限長(zhǎng)寄存器的值小。）Single-partitionallocationContiguousAllocationMultiple-partitionallocation（多分區(qū)分配）Hole

–blockofavailablememory;holesofvarioussizearescatteredthroughoutmemory.（分區(qū)—可用的內(nèi)存塊，不同大小的分區(qū)分布在整個(gè)內(nèi)存中。）Whenaprocessarrives,itisallocatedmemoryfromaholelargeenoughtoaccommodateit.（當(dāng)一個(gè)進(jìn)程到來(lái)的時(shí)候，它將從一個(gè)足夠容納它分區(qū)中分配內(nèi)存。）Operatingsystemmaintainsinformationabout（操作系統(tǒng)包含以下信息）:a)allocatedpartitions（分配的分區(qū)）b)freepartitions(hole)（空的分區(qū)）OSprocess5process8process2OSprocess5process2OSprocess5process2OSprocess5process9process2process9process10MemoryprotectionCPU主內(nèi)存基址寄存器界限寄存器定址地址是否邏輯地址物理地址＜＋MemoryAllocationFirst-fit(首先適應(yīng)）:Allocatethefirstholethatisbigenough.（分配最先找到的合適的分區(qū)。）Best-fit（最佳適應(yīng)）:Allocatethesmallestholethatisbigenough;mustsearchentirelist,unlessorderedbysize.Producesthesmallestleftoverhole.（搜索整個(gè)序列，找到適合條件的最小的分區(qū)進(jìn)行分配。）Worst-fit（最差適應(yīng)）:Allocatethelargesthole;mustalsosearchentierlist.Producesthelargestleftoverhole.（搜索整個(gè)序列，尋找最大的分區(qū)進(jìn)行分配。）Howtosatisfyarequestofsizenfromalistoffreeholes.（怎樣從一個(gè)空的分區(qū)序列中滿足一個(gè)申請(qǐng)需要。）First-fitandbest-fitbetterthanworst-fitintermsofspeedandstorageutilization.（在速度和存儲(chǔ)的利用上，首先適應(yīng)和最佳適應(yīng)要比最差適應(yīng)好。）FragmentationExternalfragmentation（外碎片）–totalmemoryspaceexiststosatisfyarequest,butitisnotcontiguous.（整個(gè)內(nèi)存空間用來(lái)滿足一個(gè)請(qǐng)求，但它不是連續(xù)的。）Internalfragmentation（內(nèi)碎片）–allocatedmemorymaybeslightlylargerthanrequestedmemory;thissizedifferenceismemoryinternaltoapartition,butnotbeingused.（分配的內(nèi)存可能比申請(qǐng)的內(nèi)存大一點(diǎn)，這兩者之間的差別是內(nèi)部不被使用的簇）FragmentationCompactionofdynamicstorage-allocationReduceexternalfragmentationbycompaction（通過(guò)壓縮來(lái)減少內(nèi)碎片）Shufflememorycontentstoplaceallfreememorytogetherinonelargeblock.（把一些小的空閑內(nèi)存結(jié)合成一個(gè)大的塊。）Compactionispossibleonlyifrelocationisdynamic,andisdoneatexecutiontime.（只有重置是動(dòng)態(tài)的時(shí)候，才有可能進(jìn)行壓縮，壓縮在執(zhí)行時(shí)期進(jìn)行）I/Oproblem（I/O問(wèn)題）LatchjobinmemorywhileitisinvolvedinI/O.（當(dāng)I/O的時(shí)候，把工作鎖定在內(nèi)存中。）DoI/OonlyintoOSbuffers.（只對(duì)操作系統(tǒng)的緩沖器進(jìn)行I/O。）Charpt9:MemoryManagementBackground（背景）LogicalversusPhysicalAddressSpace（邏輯與物理地址空間）Swapping（交換）ContiguousAllocation（連續(xù)分配）Paging（分頁(yè)） Segmentation（分段）SegmentationwithPaging（帶分頁(yè)的分段）PagingLogicaladdressspaceofaprocesscanbenoncontiguous;processisallocatedphysicalmemorywhereverthelatterisavailable.Pagingisamemory-managementschemethatpermitsthephysical-addressspaceofaprocesstobenoncontiguous.程序可被不連續(xù)放置，沒有碎片問(wèn)題將載入的程序分割成固定大小的分頁(yè)（page）物理內(nèi)存也分割成固定大小的頁(yè)框（frame），大小與分頁(yè)相同執(zhí)行程序時(shí)，把程序所有的分頁(yè)放入物理內(nèi)存中任何可用的頁(yè)框中PagingDividephysicalmemoryintofixed-sizedblockscalledframes(sizeispowerof2,between512bytesand8192bytes).（把物理內(nèi)存分成大小固定的塊，叫做頁(yè)框。）Dividelogicalmemoryintoblocksofsamesizecalledpages.（把邏輯內(nèi)存也分位固定大小的塊，叫做頁(yè)面。）Keeptrackofallfreeframes.（跟蹤所有空閑頁(yè)框的記錄。）Torunaprogramofsizenpages,needtofindnfreeframesandloadprogram.（運(yùn)行一個(gè)有N頁(yè)大小的程序，需要找到N個(gè)空的頁(yè)框讀入程序。）BasicMethodAddressgeneratedbyCPUisdividedinto（CPU產(chǎn)生的地址被分為）:Pagenumber

(p)

（頁(yè)號(hào)）–usedasanindexintoapage

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

(d)

（偏移）–combinedwithbaseaddresstodefinethephysicalmemoryaddressthatissenttothememoryunit.（同基址相結(jié)合，用來(lái)確定送入內(nèi)存設(shè)備的物理內(nèi)存地址。）BasicMethod頁(yè)數(shù)p頁(yè)偏移d邏輯地址f分頁(yè)表pf頁(yè)偏移d物理地址物理內(nèi)存

AddressTranslationArchitecturePagingExamplePagingexamplefora32-bytememorywith4-bytepagesFreeframes,beforeallocationsandafterallocations勘誤P291Eachtableentryisusually4byteslong,butthatsizecanvaryaswell.A32-bitentrycanpointtooneof232physicalpageframes.Ifaframeis4KB,thenasystemwith4-byteentriescanaddress236ofphysicalmemory244

232*212=244Hardwaresupport頁(yè)表每次轉(zhuǎn)換都要找頁(yè)表，所以也表很關(guān)鍵，影響地址轉(zhuǎn)換的性能ImplementationofPageTablePagetableiskeptinmainmemory.（主存中的頁(yè)表。）table

baseregister(PTBR)pointstothepagetable.（頁(yè)表基址寄存器指向頁(yè)表。）tablelengthregister(PRLR)indicatessizeofthepagetable.（頁(yè)表限長(zhǎng)寄存器表明頁(yè)表的長(zhǎng)度。）Inthisschemeeverydata/instructionaccessrequirestwomemoryaccesses.Oneforthepagetableandoneforthedata/instruction.（在這個(gè)機(jī)制中，每一次的數(shù)據(jù)/指令存取需要兩次內(nèi)存存取，一次是存取頁(yè)表，一次是存取數(shù)據(jù)。）Hardwaresupport加快頁(yè)表Associativeregisters–parallelsearch（聯(lián)想寄存器—平行查找）

Addresstranslation(A′,A′′)（地址轉(zhuǎn)換）IfA′isinassociativeregister,getframe#out.（如果A’在聯(lián)想寄存器中，把頁(yè)框#取出來(lái)。）Otherwisegetframe#frompagetableinmemory.（否則從內(nèi)存中的頁(yè)表中取出頁(yè)框#。）Page#Frame#PaginghardwarearewithTLBs旁查表PaginghardwarearewithTLBsThetwomemoryaccessproblemcanbesolvedbytheuseofaspecialfast-lookuphardwarecachecalledassociativeregistersortranslationlook-asidebuffers

(TLBs).(通過(guò)一個(gè)聯(lián)想寄存器，可以解決兩次存取的問(wèn)題。）EffectiveAccessTimeAssociativeLookup=timeunit（聯(lián)想寄存器的查找需要時(shí)間）Assumememorycycletimeist

（假設(shè)內(nèi)存一次存取要

t）Hitratio–percentageoftimesthatapagenumberisfoundintheassociativeregisters;rationrelatedtonumberofassociativeregisters.（命中率—在聯(lián)想寄存器中找到頁(yè)號(hào)的比率，比率與存器的大小有關(guān)。）Hitratio=EffectiveAccessTime(EAT)（有效存取時(shí)間） EAT=(t+)+(2t+)(1–)

例，=20ns，t=100ns，=80%EAT=(100+20)x0.8+(2x100+20)x(1-0.8)=140ns

MemoryProtectionMemoryprotectionimplementedbyassociatingprotectionbitwitheachframe.（內(nèi)存的保護(hù)由與每個(gè)頁(yè)框相連的保護(hù)位來(lái)執(zhí)行。）Valid-invalidbitattachedtoeachentryinthepagetable（有效-無(wú)效位附在頁(yè)表的每個(gè)入口中）:“valid”indicatesthattheassociatedpageisintheprocess’logicaladdressspace,andisthusalegalpage.（“有效”表明相關(guān)的頁(yè)在進(jìn)程的邏輯地址空間，以及是一個(gè)合法的頁(yè)。）“invalid”indicatesthatthepageisnotintheprocess’logicaladdressspace.（“無(wú)效”表明頁(yè)不在進(jìn)程的邏輯地址空間中。）Validorinvalidbitinapagetable頁(yè)表結(jié)構(gòu)HierarchicalpagingHashedPageTablesInvertedpageTableSharedPages

Two-LevelPagingScheme因地址位過(guò)長(zhǎng)，連續(xù)頁(yè)表空間太大Alogicaladdress(on32-bitmachinewith4Kpagesize)isdividedinto（一個(gè)邏輯地址被分為）:apagenumberconsistingof20bits.（一個(gè)20位的頁(yè)號(hào)。）apageoffsetconsistingof12bits.（一個(gè)12位的偏移。）Sincethepagetableispaged,thepagenumberisfurtherdividedinto（頁(yè)表頁(yè)被分為）:a10-bitpagenumber.（一個(gè)10位的頁(yè)號(hào)。）a10-bitpageoffset.（一個(gè)10位的偏移。）Thus,alogicaladdressisasfollows（因此，一個(gè)邏輯地址表示如下）:

wherepiisanindexintotheouterpagetable,andp2isthedisplacementwithinthepageoftheouterpagetable.頁(yè)表的連續(xù)空間只需1kpagenumberpageoffsetpip2d101012Two-LevelPagingSchemeMotive:不希望頁(yè)表占用連續(xù)的內(nèi)存空間想把頁(yè)表分成較小的存儲(chǔ)單元121010P1P2d頁(yè)偏移內(nèi)層分頁(yè)外層分頁(yè)P(yáng)1P2內(nèi)存外層分頁(yè)＋內(nèi)層分頁(yè)Two-LevelTableExampleAddress-TranslationSchemeAddress-translationschemeforatwo-level32-bitpagingarchitecture（一個(gè)兩級(jí)32位分頁(yè)結(jié)構(gòu)的地址轉(zhuǎn)移機(jī)制）MultilevelPagingandPerformanceSinceeachlevelisstoredasaseparatetableinmemory,coveringalogicaladdresstoaphysicalonemaytakefourmemoryaccesses.（由于每一級(jí)都分開的以表的形式存儲(chǔ)在內(nèi)存中，把一個(gè)邏輯地址轉(zhuǎn)換為一個(gè)物理地址可能要進(jìn)行4次內(nèi)存存取。）性能低（EAT太大），怎么辦？Cacheorhash

關(guān)于64位機(jī)MultilevelPagingandPerformanceCacheEventhoughtimeneededforonememoryaccessisquintupled,cachingpermitsperformancetoremainreasonable.（盡管每次內(nèi)存存取的時(shí)間是很大的，緩存使執(zhí)行的時(shí)間還是可以接受的。）Cachehitrateof98percentyields（緩存的命中率使98%）=20ns，t=100ns則:

EAT=0.98x120+0.02x520 =128ns.

whichisonlya28percentslowdowninmemoryaccesstime.HashedPageTables地址位太長(zhǎng)Commoninaddressspaces>32bits.Thevirtualpagenumberishashedintoapagetable.Thispagetablecontainsachainofelementshashingtothesamelocation.Virtualpagenumbersarecomparedinthischainsearchingforamatch.Ifamatchisfound,thecorrespondingphysicalframeisextracted.HashedPageTableHashedPageTable這是一個(gè)鏈表，每個(gè)元素包含兩項(xiàng)（page和frame）先搜素第一個(gè)元素HashedPageTable第一個(gè)沒找到，再搜索第二個(gè)元素HashedPageTable第二個(gè)元素找到p，對(duì)應(yīng)frame是rHashedPageTable完成地址映射InvertedPageTable每個(gè)進(jìn)程一個(gè)頁(yè)表還是整個(gè)系統(tǒng)只用一個(gè)頁(yè)表IPT‘sMotive：解決頁(yè)表空間太多、太大的問(wèn)題，整個(gè)系統(tǒng)僅用一個(gè)分頁(yè)表Oneentryforeachrealpageofmemory.（每個(gè)內(nèi)存頁(yè)幀只有一入口。）Entryconsistsofthevirtualaddressofthepagestoredinthatrealmemorylocation,withinformationabouttheprocessthatownsthatpage.（入口包含該頁(yè)幀中的虛擬地址頁(yè)，以及擁有該頁(yè)的進(jìn)程信息。）Decreasesmemoryneededtostoreeachpagetable,butincreasestimeneededtosearchthetablewhenapagereferenceoccurs.Usehashtabletolimitthesearchtoone—oratmostafew—tableentries.（使用哈稀表來(lái)減少搜索。）InvertedPageTablePIDPd邏輯地址i主存反轉(zhuǎn)分頁(yè)表PIDPid物理地址InvertedPageTableArchitectureSharedPagesSharedcode（共享代碼）Onecopyofread-only(reentrant)codesharedamongprocesses(i.e.,texteditors,compilers,windowsystems).（一個(gè)只讀（可再入）代碼可由進(jìn)程共享。）Sharedcodemustappearinsamelocationinthelogicaladdressspaceofallprocesses.（共享代碼必須出現(xiàn)在所有進(jìn)程的邏輯地址空間的相同位置。）Privatecodeanddata（私有代碼和數(shù)據(jù)）Eachprocesskeepsaseparatecopyofthecodeanddata.（每個(gè)進(jìn)程保留一個(gè)代碼和數(shù)據(jù)的私有拷貝。）Thepagesfortheprivatecodeanddatacanappearanywhereinthelogicaladdressspace.（私有代碼和數(shù)據(jù)的頁(yè)可以出現(xiàn)在邏輯地址空間的任何地方。）SharedPagesExampleSegmentation用戶怎么看內(nèi)存？Memory-managementschemethatsupportsuserviewofmemory.（內(nèi)存管理機(jī)制支持用戶觀點(diǎn)的內(nèi)存。）用戶并不關(guān)心內(nèi)存是怎么組織的，線性矩陣？鏈表？不關(guān)心，也不愿意管其形式，用戶更多的是看他所編寫的程序，而一個(gè)程序是一些段（segment）的集合，一個(gè)段是一個(gè)邏輯單位，如：

mainprogram,

procedure,

function,

localvariables,globalvariables,

commonblock,

stack,

symboltable,arraysLogicalViewofSegmentation13241423userspacephysicalmemoryspaceSegmentationArchitectureLogicaladdressconsistsofatwotuple（一個(gè)邏輯地址是兩個(gè)向量的集合）: <segment-number,offset>,Segmenttable–mapstwo-dimensionalphysicaladdresses;eachtableentryhas（段表-映射二維物理地址，每個(gè)表入口包括）:base–containsthestartingphysicaladdresswherethesegmentsresideinmemory.（基址-包括內(nèi)存中段物理地址的起始地址。）limit

–specifiesthelengthofthesegment.（限長(zhǎng)-指定段的長(zhǎng)度。）Segment-tablebaseregister(STBR)

pointstothesegmenttable’slocationinmemory.（段表基址寄存器指向段表在內(nèi)存中的地址。）Segment-tablelengthregister(STLR)

indicatesnumberofsegmentsusedbyaprogram;（段表限長(zhǎng)寄存器表明被一個(gè)程序所使用的段的數(shù)目。） segmentnumbersislegalifs<STLR.SegmentationArchitecture主存分段表分段編號(hào)s段偏移d邏輯地址長(zhǎng)度起始位址d<長(zhǎng)度定址錯(cuò)誤是否＋SegmentationArchitecture(Cont.)Relocation.（重置）dynamic（動(dòng)態(tài)）bysegmenttable（由段表來(lái)執(zhí)行）Sharing.（共享）sharedsegments（共享的段）samesegmentnumber（同樣的段號(hào)）Allocation.（分配）firstfit/bestfit（首先/最佳試配）externalfragmentation（外碎片）SegmentationArchitecture(Cont.)Protection.Witheachentryinsegmenttableassociate（保護(hù)，每個(gè)段表的入口有）:validationbit（有效位）=0illegalsegmentread/write/executeprivileges（讀/寫/執(zhí)行權(quán)利）Protectionbitsassociatedwithsegments;codesharingoccursatsegmentlevel.（保護(hù)位同段相聯(lián)系，在段的級(jí)別進(jìn)行代碼共享。）Sincesegmentsvaryinlength,memoryallocationisadynamicstorage-allocationproblem.（由于段的各個(gè)長(zhǎng)度不同，內(nèi)存分配是一個(gè)動(dòng)態(tài)存儲(chǔ)-分配問(wèn)題。）Asegmentationexampleisshowninthefollowingdiagram（下面的是一個(gè)段的例子）SegmentationwithPaging–Intel386(補(bǔ)充)Asshowninthefollowingdiagram,theIntel386usessegmentationwithpagingformemorymanagementwithatwo-levelpagingscheme.（如下圖所示，Intel386使用段頁(yè)結(jié)合來(lái)進(jìn)行二級(jí)分頁(yè)的內(nèi)存管理。）selector:16bitsoffset:32bitssgp1312s:segmentnumberg:GDTorLDTp:protection6個(gè)段寄存器GDT、LDT入口是8bytes6個(gè)8-byte微程序寄存器GDT、LDT實(shí)現(xiàn)進(jìn)程之間內(nèi)存的共享與否，當(dāng)g為GDT時(shí)，表示訪問(wèn)共享內(nèi)存Example:TheIntelPentiumSupportsbothsegmentationandsegmentationwithpagingCPUgenerateslogicaladdressGiventosegme