操作系统-fs ch课件

Chapter8:MainMemory

内存ObjectivesToprovideadetaileddescriptionofvariouswaysoforganizingmemoryhardware不同的内存硬件使用（组织）方法Todiscussvariousmemory-managementtechniques,includingpagingandsegmentation不同的内存管理技术，包括分页和分段Chapter8:MemoryManagementBackground背景Swapping交换ContiguousMemoryAllocation连续内存分配Segmentation分段Paging分页StructureofthePageTable页表结构Example:TheIntel32and64-bitArchitecturesBackgroundProgrammustbebrought(fromdisk)intomemoryandplacedwithinaprocessforittoberun程序只有装入内存、植入一个进程结构后才能运行MainmemoryandregistersareonlystorageCPUcanaccessdirectly只有内存和寄存器是两类CPU能够访问的存储介质Memoryunitonlyseesastreamofaddresses+readrequests,oraddress+dataandwriterequests内存单元可以看做是一系列的地址+读请求，或者地址+数据和写请求RegisteraccessinoneCPUclock(orless)访问寄存器只要一个时钟周期，甚至更短Mainmemorycantakemanycycles,causingastall访问内存需要多个时钟周期Cache

sitsbetweenmainmemoryandCPUregistersCache是内存和CPU寄存器的中间桥梁Protectionofmemoryrequiredtoensurecorrectoperation内存保护要求使用正确的操作。实现保护的基本方法

BaseandLimitRegisters基地址和限长寄存器Apairofbase

and

limit

registersdefinethelogicaladdressspace一组基地址和限长寄存器定义了一个逻辑地址空间CPUmustcheckeverymemoryaccessgeneratedinusermodetobesureitisbetweenbaseandlimitforthatuserCPU必须检测所有在用户模式产生的内存访问请求，确保该访问处于基地址和限长寄存器范围内。HardwareAddressProtectionAddressBinding地址绑定Programsondisk,readytobebroughtintomemorytoexecuteformaninputqueueWithoutsupport,mustbeloadedintoaddress0000如果没有任何保护措施，就必须放置到0000地址Inconvenienttohavefirstuserprocessphysicaladdressalwaysat0000Howcanitnotbe?Further,addressesrepresentedindifferentwaysatdifferentstagesofaprogram’slife在一个程序的生命周期的不同阶段，地址可以用不同的方式表示Sourcecodeaddressesusuallysymbolic源代码使用符号地址Compiledcodeaddressesbindtorelocatableaddresses编译后的代码地址与可重装地址绑定i.e.“14bytesfrombeginningofthismodule”Linkerorloaderwillbindrelocatableaddressestoabsoluteaddresses链接器或者加载程序把可重装地址与绝对地址绑定i.e.74014Eachbindingmapsoneaddressspacetoanother每次绑定都是把一个地址空间映射到另一个地址空间BindingofInstructionsandDatatoMemoryAddressbindingofinstructionsanddatatomemoryaddressescanhappenatthreedifferentstages指令和数据的地址绑定可以发生在不同的三个阶段Compiletime:Ifmemorylocationknownapriori,absolutecodecanbegenerated;mustpilecodeifstartinglocationchanges编译期Loadtime:Mustgeneraterelocatablecodeifmemorylocationisnotknownatcompiletime装入期Executiontime:Bindingdelayeduntilruntimeiftheprocesscanbemovedduringitsexecutionfromonememorysegmenttoanother运行期Needhardwaresupportforaddressmaps(e.g.,baseandlimitregisters)MultistepProcessingofaUserProgramLogicalvs.PhysicalAddressSpace

逻辑地址空间和物理地址空间Theconceptofalogicaladdressspacethatisboundtoaseparatephysicaladdressspace

iscentraltopropermemorymanagement与一个物理地址空间绑定的逻辑地址空间是正确进行内存管理的核心概念Logicaladdress

–generatedbytheCPU;alsoreferredtoasvirtualaddress逻辑地址空间：由CPU产生，往往称为虚地址Physicaladdress

–addressseenbythememoryunit物理地址，物理内存地址Logicalandphysicaladdressesarethesameincompile-timeandload-timeaddress-bindingschemes;logical(virtual)andphysicaladdressesdifferinexecution-timeaddress-bindingscheme在编译期和装入期绑定机制中逻辑地址和物理地址是相同的；在执行期进行绑定的机制汇总，逻辑地址和物理地址是不同的LogicaladdressspaceisthesetofalllogicaladdressesgeneratedbyaprogramPhysicaladdressspaceisthesetofallphysicaladdressesgeneratedbyaprogram关于创建子进程的其他情况Linux－－－copyonwrite#include<stdio.h>intmain(){pid_tpid;char*str=(char*)malloc(sizeof(char)*10);memset(str,0x00,10);intvar=88;printf("str=%s,strAdd=%x,var=%d,varAdd=%x",str,str,var,&var);printf("\n");if((pid=fork())<0)printf("forkfailed!\n");elseif(pid==0){strcpy(str,"child");var++;}else{sleep(4);strcpy(str,"parent");}printf("\n");printf("str=%s,strAdd=%x,var=%d,varAdd=%x",str,str,var,&var);}思考题：为什么两个进程的字符串地址是相同的？Memory-ManagementUnit(MMU)

内存管理单元Hardwaredevicethatatruntimemapsvirtualtophysicaladdress子运行时把虚地址映射为物理地址的硬件设备Manymethodspossible,coveredintherestofthischapterTostart,considersimpleschemewherethevalueintherelocationregisterisaddedtoeveryaddressgeneratedbyauserprocessatthetimeitissenttomemory从简单方法开始：当一个用户进程装入到内存时，一个重定位寄存器包含的地址加到该用户进程的每一个地址上BaseregisternowcalledrelocationregisterMS-DOSonIntel80x86used4relocationregistersTheuserprogramdealswithlogicaladdresses;itneverseestherealphysicaladdresses用户程序只和逻辑地址打交道，永远不会看到逻辑地址Execution-timebindingoccurswhenreferenceismadetolocationinmemoryLogicaladdressboundtophysicaladdressesDynamicrelocationusingarelocationregister

使用重定位寄存器的动态加载Routineisnotloadeduntilitiscalled例程只有在调用时才会被加载Bettermemory-spaceutilization;unusedroutineisneverloaded提高内存空间的利用率AllroutineskeptondiskinrelocatableloadformatUsefulwhenlargeamountsofcodeareneededtohandleinfrequentlyoccurringcasesNospecialsupportfromtheoperatingsystemisrequiredImplementedthroughprogramdesignOScanhelpbyprovidinglibrariestoimplementdynamicloadingDynamicLinking动态链接Staticlinking–systemlibrariesandprogramcodecombinedbytheloaderintothebinaryprogramimage静态链接系统库与程序代码由加载器链接为一个二值程序镜像Dynamiclinking–linkingpostponeduntilexecutiontime动态链接：链接推迟到执行时进行Smallpieceofcode,stub,usedtolocatetheappropriatememory-residentlibraryroutine使用一段很小的代码，即存根（stub），来定位何时的内存中存在的库函数例程Stubreplacesitselfwiththeaddressoftheroutine,andexecutestheroutine存根使用库函数例程对的地址替代存根自己，执行库函数Operatingsystemchecksifroutineisinprocesses’memoryaddressOS检查是否例程存在于进程的内存地址空间中Ifnotinaddressspace,addtoaddressspace如果不在，则加载到该地址空间DynamiclinkingisparticularlyusefulforlibrariesSystemalsoknownassharedlibrariesConsiderapplicabilitytopatchingsystemlibrariesVersioningmaybeneededChapter8:MemoryManagementBackground背景Swapping交换ContiguousMemoryAllocation连续内存分配Segmentation分段Paging分页StructureofthePageTable页表结构Example:TheIntel32and64-bitArchitecturesSwapping置换Aprocesscanbeswappedtemporarilyoutofmemorytoabackingstore,andthenbroughtbackintomemoryforcontinuedexecution一个进程可能被临时性地从内存交换到外存上，后续可能再被交换到内存中继续执行Totalphysicalmemoryspaceofprocessescanexceedphysicalmemory所有进程的总物理空间可以超过内存的物理大小Backingstore–fastdisklargeenoughtomodatecopiesofallmemoryimagesforallusers;mustprovidedirectaccesstothesememoryimages后备外存Rollout,rollin–swappingvariantusedforpriority-basedschedulingalgorithms;lower-priorityprocessisswappedoutsohigher-priorityprocesscanbeloadedandexecuted滚出、滚入Majorpartofswaptimeistransfertime;totaltransfertimeisdirectlyproportionaltotheamountofmemoryswapped交换的时间主要是传输时间。Systemmaintainsareadyqueueofready-to-runprocesseswhichhavememoryimagesondiskSwapping(Cont.)Doestheswappedoutprocessneedtoswapbackintosamephysicaladdresses?换出的进程在换入时，是否还回到同一个物理地址？Dependsonaddressbindingmethod取决于采用的地址绑定方法PlusconsiderpendingI/Oto/fromprocessmemoryspace如果一个进程正在等待IO，怎么办？Modifiedversionsofswappingarefoundonmanysystems(i.e.,UNIX,Linux,andWindows)在很多系统中都存在修改版的swapping技术Swappingnormallydisabled一般禁止swappingStartedifmorethanthresholdamountofmemoryallocated当空闲内存数量低于一个阈值时，进行swappingDisabledagainoncememorydemandreducedbelowthreshold当空闲内存高于阈值时再次禁止swappingSchematicViewofSwappingContextSwitchTimeincludingSwapping

包含swapping的上下文切换IfnextprocessestobeputonCPUisnotinmemory,needtoswapoutaprocessandswapintargetprocess如果下一个要放到CPU上运行的进程不在内存，就需要换出一个进程再换入目标进程Contextswitchtimecanthenbeveryhigh这就导致上下文切换时间变得非常高100MBprocessswappingtoharddiskwithtransferrateof50MB/secSwapouttimeof2000msPlusswapinofsamesizedprocessTotalcontextswitchswappingcomponenttimeof4000ms(4seconds)Canreduceifreducesizeofmemoryswapped–byknowinghowmuchmemoryreallybeingused只交换那些必要的内存SystemcallstoinformOSofmemoryuseviarequest_memory()andrelease_memory()ContextSwitchTimeandSwapping(Cont.)OtherconstraintsaswellonswappingPendingI/O–can’tswapoutasI/Owouldoccurtowrongprocess正在等待完成的IO—不能交换该进程到外存OralwaystransferI/Otokernelspace,thentoI/Odevice或者先把IO数据传输到内核空间Knownasdoublebuffering,addsoverheadStandardswappingnotusedinmodernoperatingsystemsButmodifiedversioncommonSwaponlywhenfreememoryextremelylowSwappingonMobileSystems

移动系统中的交换机制Nottypicallysupported一般不支持交换机制FlashmemorybasedSmallamountofspaceLimitednumberofwritecyclesPoorthroughputbetweenflashmemoryandCPUonmobileplatformInsteaduseothermethodstofreememoryiflow当可用内存较少时，使用其他方法释放内存iOSasksappstovoluntarilyrelinquishallocatedmemoryRead-onlydatathrownoutandreloadedfromflashifneededFailuretofreecanresultinterminationAndroidterminatesappsiflowfreememory,butfirstwritesapplicationstatetoflashforfastrestartBothOSessupportpagingasdiscussedbelowChapter8:MemoryManagementBackground背景Swapping交换ContiguousMemoryAllocation连续内存分配Segmentation分段Paging分页StructureofthePageTable页表结构Example:TheIntel32and64-bitArchitecturesContiguousAllocation连续分配MainmemorymustsupportbothOSanduserprocesses内存必须既支持OS又支持用户程序的运行Limitedresource,mustallocateefficiently由于资源有限，必须高效分配Contiguousallocationisoneearlymethod在早期的系统中连续分配是主流内存分配方法Mainmemoryusuallyintotwopartitions:内存一般被分为两部分Residentoperatingsystem,usuallyheldinlowmemorywithinterruptvector驻留操作系统，与中断矢量一起在内存的低地址端Userprocessesthenheldinhighmemory用户进程在内存高地址端Eachprocesscontainedinsinglecontiguoussectionofmemory每个进程放入到一个连续内存空间区域中ContiguousAllocation(Cont.)Relocationregistersusedtoprotectuserprocessesfromeachother,andfromchangingoperating-systemcodeanddata重定位寄存器用于保护用户进程之间不相互干扰，以及用户进程不干扰系统代码和数据Baseregistercontainsvalueofsmallestphysicaladdress基址寄存器保存最低的物理地址Limitregistercontainsrangeoflogicaladdresses–eachlogicaladdressmustbelessthanthelimitregister限长寄存器保存逻辑地址的范围每一个逻辑地址都必须比现场寄存器的值要小MMUmapslogicaladdressdynamicallyCanthenallowactionssuchaskernelcodebeingtransientandkernelchangingsizeHardwareSupportforRelocationandLimitRegistersMultiple-partitionallocation多分区分配

Multiple-partitionallocationDegreeofmultiprogramminglimitedbynumberofpartitions多道程序的度由分区数目决定Variable-partitionsizesforefficiency(sizedtoagivenprocess’needs)分区大小可以根据进程的大小调整，提高使用效率Hole–blockofavailablememory;holesofvarioussizearescatteredthroughoutmemory在不断的分配过程中会形成空洞这些孔洞是可用的内存，但是不连续的分布在整个内存空间上Whenaprocessarrives,itisallocatedmemoryfromaholelargeenoughtomodateitProcessexitingfreesitspartition,adjacentfreepartitionscombinedOperatingsystemmaintainsinformationabout:

a)allocatedpartitionsb)freepartitions(hole)DynamicStorage-AllocationProblem

动态存储分配的问题First-fit:Allocatethefirstholethatisbigenough首次适应分配方法Best-fit:Allocatethesmallestholethatisbigenough;mustsearchentirelist,unlessorderedbysize最佳适应分配方法ProducesthesmallestleftoverholeWorst-fit:Allocatethelargesthole;mustalsosearchentirelist最差适应分配方法ProducesthelargestleftoverholeHowtosatisfyarequestofsizenfromalistoffreeholes?First-fitandbest-fitbetterthanworst-fitintermsofspeedandstorageutilization与最差适应方法相比，首次和最佳适应方法在速度和利用率上更好一些Fragmentation碎片ExternalFragmentation

–totalmemoryspaceexiststosatisfyarequest,butitisnotcontiguous外部碎片总的空闲空间可以满足一个请求，但是这些空间是不连续的InternalFragmentation

–allocatedmemorymaybeslightlylargerthanrequestedmemory;thissizedifferenceismemoryinternaltoapartition,butnotbeingused内部碎片—分配的内存空间比要求的空间略大；这个大出来的差值就是内碎片，不能再被其他进程使用FirstfitanalysisrevealsthatgivenNblocksallocated,0.5Nblockslosttofragmentation对首次适应分配方法的分析表明：如果分配N各块，大概有0.5N个块的空间会成为碎片，而不能使用。1/3maybeunusable->50-percentruleFragmentation(Cont.)Reduceexternalfragmentationbycompaction可以通过紧缩方法来减少外碎片Shufflememorycontentstoplaceallfreememorytogetherinonelargeblock通过重新放置内存中的数据，把所有空闲内存合并为一个大块Compactionispossibleonlyifrelocationisdynamic,andisdoneatexecutiontime使用紧缩技术的前提是系统支持重定位技术，而且是运行时重定位I/OproblemLatchjobinmemorywhileitisinvolvedinI/ODoI/OonlyintoOSbuffersNowconsiderthatbackingstorehassamefragmentationproblemsChapter8:MemoryManagementBackground背景Swapping交换ContiguousMemoryAllocation连续内存分配Segmentation分段Paging分页StructureofthePageTable页表结构Example:TheIntel32and64-bitArchitecturesSegmentation分段Memory-managementschemethatsupportsuserviewofmemory支持从用户视角来使用（管理）内存Aprogramisacollectionofsegments一个程序往往是多个段的集合Asegmentisalogicalunitsuchas: mainprogram procedure function method object localvariables,globalvariables commonblock stack symboltable arraysUser’sViewofaProgramLogicalViewofSegmentation13241423userspacephysicalmemoryspaceSegmentationArchitecture分段的结构Logicaladdressconsistsofatwotuple:段的逻辑地址是一个二元组 <segment-number,offset>,Segmenttable

–mapstwo-dimensionalphysicaladdresses;eachtableentryhas:段表实现二维物理地址的映射；每个段的条目包含两个内容base

–containsthestartingphysicaladdresswherethesegmentsresideinmemory段的基地址limit

–specifiesthelengthofthesegment段的长度Segment-tablebaseregister(STBR)

pointstothesegmenttable’slocationinmemory段表基地址寄存器Segment-tablelengthregister(STLR)

indicatesnumberofsegmentsusedbyaprogram;段表长度寄存器 segmentnumbersislegalifs<STLRSegmentationArchitecture(Cont.)Protection段的保护机制Witheachentryinsegmenttableassociate:validationbit=0illegalsegment合法标志位read/write/executeprivileges读、写、执行权限Protectionbitsassociatedwithsegments;codesharingoccursatsegmentlevel每个段都有保护位；在段的层面上可以实现代码共享。Sincesegmentsvaryinlength,memoryallocationisadynamicstorage-allocationproblemAsegmentationexampleisshowninthefollowingdiagramSegmentationHardwareChapter8:MemoryManagementBackground背景Swapping交换ContiguousMemoryAllocation连续内存分配Segmentation分段Paging分页StructureofthePageTable页表结构Example:TheIntel32and64-bitArchitecturesExample:ARMArchitecturePaging分页Physicaladdressspaceofaprocesscanbenoncontiguous;processisallocatedphysicalmemorywheneverthelatterisavailable通过分页技术一个进程的物理地址可以不再是连续的；只要有空闲的物理内存就可以分配给进程Avoidsexternalfragmentation避免外碎片Avoidsproblemofvaryingsizedmemorychunks避免不同尺寸的内存块引发的问题Dividephysicalmemoryintofixed-sizedblockscalledframes把物理内存分成固定大小的块，称为帧Sizeispowerof2,between512bytesand16MbytesDividelogicalmemoryintoblocksofsamesizecalledpages把逻辑内存分成同样大小的块，称为页。Keeptrackofallfreeframes对所有空闲的帧保持纪录TorunaprogramofsizeN

pages,needtofindNfreeframesandloadprogramSetupapagetabletotranslatelogicaltophysicaladdresses设置一个页表实现逻辑地址到物理地址的转换BackingstorelikewisesplitintopagesStillhaveInternalfragmentation仍然存在内碎片AddressTranslationScheme地址转换机制AddressgeneratedbyCPUisdividedinto:CPU生成的地址分为两部分Pagenumber(p)

–usedasanindexintoapagetablewhichcontainsbaseaddressofeachpageinphysicalmemory页号Pageoffset(d)

–combinedwithbaseaddresstodefinethephysicalmemoryaddressthatissenttothememoryunit页内便宜Forgivenlogicaladdressspace2mandpagesize

2nPagingHardware分页的硬件支持PagingModelofLogicalandPhysicalMemory

分页模型的逻辑和物理内存PagingExamplen=2andm=432-bytememoryand4-bytepagesPaging(Cont.)Calculatinginternalfragmentation计算一个进程使用分页技术产生的内碎片Pagesize=2,048bytesProcesssize=72,766bytes35pages+1,086bytesInternalfragmentationof2,048-1,086=962bytesWorstcasefragmentation=1frame–1byteOnaveragefragmentation=1/2framesizeSosmallframesizesdesirable?ButeachpagetableentrytakesmemorytotrackPagesizesgrowingovertime在过去这些年，页面大小一直在增长Solarissupportstwopagesizes–8KBand4MBProcessviewandphysicalmemorynowverydifferent使用了分页技术后，现在进程的视角和物理内存的实际分配情况差别很大ByimplementationprocesscanonlyaccessitsownmemoryFreeFramesBeforeallocationAfterallocationImplementationofPageTable页表的实现Pagetableiskeptinmainmemory页表放置在内存中tablebaseregister(PTBR)

pointstothepagetabletablelengthregister(PTLR)

indicatessizeofthepagetableInthisschemeeverydata/instructionaccessrequirestwomemoryaccesses使用分页机制后，每次对数据或指令的访问都需要访问两次内存Oneforthepagetableandoneforthedata/instruction一次访问页表，一次访问数据或指令Thetwomemoryaccessproblemcanbesolvedbytheuseofaspecialfast-lookuphardwarecachecalledassociativememoryortranslationlook-asidebuffers(TLBs)该问题可以通过使用搞一个特殊的快速查找硬件设备解决TLBsImplementationofPageTable(Cont.)SomeTLBsstore

address-spaceidentifiers(ASIDs)

ineachTLBentry–uniquelyidentifieseachprocesstoprovideaddress-spaceprotectionforthatprocess有些TLBs存储ASIDs，其唯一地确定一个进程；当一个进程要访问某页时，必须要TLBs中该页对应的ASIDs与该进程的ASIDs相同，否则视为miss。Otherwiseneedtoflushateverycontextswitch防止上下文切换后新调度执行的进程使用错误的地址转换。TLBstypicallysmall(64to1,024entries)OnaTLBmiss,valueisloadedintotheTLBforfasteraccessnexttimeReplacementpoliciesmustbeconsideredSomeentriescanbewireddownforpermanentfastaccess某些内核代码可能常驻TLBs中AssociativeMemory联想寄存器Associativememory–parallelsearchAddresstranslation(p,d)Ifpisinassociativeregister,getframe#outOtherwisegetframe#frompagetableinmemoryPagingHardwareWithTLBEffectiveAccessTime有效访问时间AssociativeLookup=timeunit联想寄存器查找时间Canbe<10%ofmemoryaccesstimeHitratio=命中率Hitratio–percentageoftimesthatapagenumberisfoundintheassociativeregisters;ratiorelatedtonumberofassociativeregistersConsider=80%,=20nsforTLBsearch,100nsformemoryaccessEAT=0.80x100+0.20x200=120nsConsidermorerealistichitratio->=99%,=20nsforTLBsearch,100nsformemoryaccessEAT=0.99x100+0.01x200=101nsMemoryProtection内存保护Memoryprotectionimplementedbyassociatingprotectionbitwitheachframetoindicateifread-onlyorread-writeaccessisallowed内存保护的实现：每个帧都有bit位表示其读写权限Canalsoaddmorebitstoindicatepageexecute-only,andsoonValid-invalid

bitattachedtoeachentryinthepagetable:在页表中有一个bit位表示页面的合法性“valid”indicatesthattheassociatedpageisintheprocess’logicaladdressspace,andisthusalegalpage合法表示该页面在进程的逻辑地址空间“invalid”indicatesthatthepageisnotintheprocess’logicaladdressspace非法表示该页面不在进程的逻辑地址空间Orusetablelengthregister(PTLR)AnyviolationsresultinatraptothekernelValid(v)orInvalid(i)BitInAPageTableSharedPages共享页面Sharedcode共享代码Onecopyofread-only(reentrant)codesharedamongprocesses(i.e.,texteditors,compilers,windowsystems)只读（可重入）代码可以进程之间共享Similartomultiplethreadssharingthesameprocessspace类似于多个线程共享同一进程空间Alsousefulforinterprocesscommunicationifsharingofread-writepagesisallowedPrivatecodeanddata进程私有代码和数据

EachprocesskeepsaseparatecopyofthecodeanddataThepagesfortheprivatecodeanddatacanappearanywhereinthelogicaladdressspaceSharedPagesExampleChapter8:MemoryManagementBackground背景Swapping交换ContiguousMemoryAllocation连续内存分配Segmentation分段Paging分页StructureofthePageTable页表结构Example:TheIntel32and64-bitArchitecturesStructureofthePageTable页表结构Memorystructuresforpagingcangethugeusingstraight-forwardmethodsConsidera32-bitlogicaladdressspaceasonmoderncomputersPagesizeof4KB(212)Pagetablewouldhave1millionentries(232/212)Ifeachentryis4bytes->4MBofphysicaladdressspace/memoryforpagetablealoneThatamountofmemoryusedtocostalotDon’twanttoallocatethatcontiguouslyinmainmemoryHierarchicalPaging分层页表HashedPageTables哈希页表InvertedPageTables反转页表HierarchicalPageTablesBreakupthelogicaladdressspaceintomultiplepagetables把逻辑地址空间分为多个页表Asimpletechniqueisatwo-levelpagetable最简单的是两层页表WethenpagethepagetableTwo-LevelTableSchemeTwo-LevelPagingExampleAlogicaladdress(on32-bitmachinewith1Kpagesize)isdividedinto:apagenumberconsistingof22bitsapageoffsetconsistingof10bitsSincethepagetableispaged,thepagenumberisfurtherdividedinto:a12-bitpagenumbera10-bitpageoffsetThus,alogicaladdressisasfollows:

wherep1isanindexintotheouterpagetable,andp2isthedisplacementwithinthepageoftheinnerpagetableKnownasforward-mappedpagetableAddress-TranslationScheme64-bitLogicalAddressSpaceEventwo-levelpagingschemenotsufficientIfpagesizeis4KB(212)Thenpagetablehas252entriesIftwolevelscheme,innerpagetablescouldbe2104-byteentriesAddresswouldlooklikeOuterpagetablehas242entriesor244bytesOnesolutionistoadda2ndouterpagetableButinthefollowingexamplethe2ndouterpagetableisstill234bytesinsizeAndpossibly4memoryaccesstogettoonephysicalmemorylocationThree-levelPagingSchemeHashedPageTables哈希页表Commoninaddressspaces>32bitsThevirtualpagenumberishashedintoapagetableThispagetablecontainsachainofelementshashingtothesamelocation该页表包含一个链表，该链表保存哈希到同样地址的页面Eachelementcontains(1)thevirtualpagenumber(2)thevalueofthemappedpageframe(3)apointertothenextelementVirtualpagenumbersarecomparedinthischainsearchingforamatchIfamatchisfound,thecorrespondingphysicalframeisextractedVariationfor64-bitaddressesisclusteredpagetablesSimilartohashedbuteachentryreferstoseveralpages(suchas16)ratherthan1Especiallyusefulforsparseaddressspaces(wherememoryreferencesarenon-contiguousandscattered)HashedPageTableInvertedPageTable反转页表Ratherthaneachprocesshavingapagetableandkeepingtrackofallpossiblelogicalpages,trackallphysicalpages保持对所有物理页面的跟踪，而不是为每个进程分配一个页表并追踪所有逻辑页面Oneentryforeachrealpage