操作系统之内存管理2.ppt

Chapter8partII:内存管理,Chapter8:MemoryManagement,8.1Background8.2Swapping8.3ContiguousMemoryAllocationPagingStructureofthePageTableSegmentationExample:TheIntelPentium,外部碎片（InternalFragmentation）vs.内部碎片内部碎片的典型例子：固定分区分配中出现,图中阴影部分不再能够被使用。,碎片（Fragmentation）,首次适应方法和最佳适应方法都有外部碎片问题（externalfragmentation）碎片问题：当总的可用内存之和可以满足内存申请请求，但是所有空闲内存都以不连续的状态出现，并且单片空闲内存不足以满足当前的申请请求,Size=2,P1,Size=2,P2,当前提出申请内存大小=3,外部碎片的50%规则,采用首次适应方法，不管怎么优化，假定有N个可分配块，那么可能有0.5N个为外部碎片外部碎片是实际分配的块数的一般左右是为50%原则,外部碎片问题解决方法,(1)Compaction(紧缩)类似于“磁盘整理”并不是任何情况下都能够实施紧缩的如果采取的是在编译(CompileTime)或装载（LoadTime)完成的静态重定位，是不可以进行紧缩的采取动态重定位时，可以在运行时实行内存紧缩(2)允许物理空间分配以非连续的方式进行分段分页,8.4Paging分页,分页内存管理方案允许进程的物理地址空间是非连续的分页支持需要由硬件来处理,=解决外部碎片问题,8.4Paging分页,分页机制中，物理内存被划分为固定大小的块，称为帧（frame）而将逻辑内存也划分为同样大小的块，称为页（Page）页面尺寸一般是：1K-16K,8.4.1基本方法,AddressTranslationScheme分页中的地址转换,AddressgeneratedbyCPUisdividedinto:在分页的情况下，由CPU产生的地址就成为:Pagenumber(p)usedasanindexintoapagetablewhichcontainsbaseaddressofeachpageinphysicalmemory页号(p)-页号被用作对页表的索引。/页表中存放了每一个逻辑页面对应物理内存中页框的基地址,pagenumber,pageoffset,p,d,m-n,n,Forgivenlogicaladdressspace2mandpagesize2n,AddressTranslationScheme分页中的地址转换,AddressgeneratedbyCPUisdividedinto:在分页的情况下，由CPU产生的地址就成为:Pagenumber(p)usedasanindexintoapagetablewhichcontainsbaseaddressofeachpageinphysicalmemory页号(p)-页号被用作对页表的索引。/页表中存放了每一个逻辑页面对应物理内存中页框的基地址Pageoffset(d)combinedwithbaseaddresstodefinethephysicalmemoryaddressthatissenttothememoryunit页内偏移（d）-将物理页面的基地址与页内偏移加起来，得到物理地址（内存硬件接收到的地址）Forgivenlogicaladdressspace2mandpagesize2n,pagenumber,pageoffset,p,d,m-n,n,分页机制下的地址翻译,从虚地址中获取VirtualPageNumber以虚拟页号为索引查找页表，找到相应的页表项，得到物理页号计算物理地址,8.4Paging分页,分页硬件支持,8.4.1基本方法,分页实例,这里面涉及到一个逻辑地址空间与物理地址空间编址的问题假设逻辑地址与物理地址的长度都是8逻辑地址0 x06,4字节的页面,问题：如何利用分页硬件将0 x06这个逻辑地址转换到物理地址（完成逻辑地址的动态重定位）,分页实例,这里面涉及到一个逻辑地址空间与物理地址空间编址的问题假设逻辑地址与物理地址的长度都是8逻辑地址0 x06,4字节的页面,Step1:确定地址中页号部分与页内偏移部分的划分,pagenumber,pageoffset,p,d,m-n,n,其中m=8,n=2,=p=0 x01,d=0 x10,分页实例,这里面涉及到一个逻辑地址空间与物理地址空间编址的问题假设逻辑地址与物理地址的长度都是8逻辑地址0 x06,4字节的页面,Step2:利用p=0 x01作为索引查页表虚页1-物理页3物理页开始地址0 x0C偏移0 x02物理地址=?,0 x0E,PagingModelofLogicalandPhysicalMemory,在逻辑上连续的页面，在物理内存中可能是分散的。,PagingExample,32-bytememoryand4-bytepages,如果逻辑空间确定为4个页面，每个页面大小4字节，物理内存大小为32字节怎么编址？页号占地址几位？页偏移需要占用地址中几个位？,FreeFrames,Beforeallocation,Afterallocation,分配之后形成页表,每个进程有一个页表,ImplementationofPageTable页表实现,Pagetableiskeptinmainmemory（页表是放在主存中的）Page-tablebaseregister(PTBR)pointstothepagetable（指向页表的基地址）Page-tablelengthregister(PRLR)indicatessizeofthepagetable（记录页表长度）在PTBR+PRLR的这种实现模式下，每次对指令和数据的访问都会涉及到几次内存访问？2次。一次访问页表，一次访问指令和数据所在的内存地址,ImplementationofPageTable页表实现,对页表的两次访问，会带来效率方面的问题Thetwomemoryaccessproblemcanbesolvedbytheuseofaspecialfast-lookuphardwarecachecalledassociativememoryortranslationlook-asidebuffers(TLBs)解决问题的方法：用TLB(快表)来储存经常被访问的页表项，TLB是特别实现的硬件Cache，其访问速度比访存速度要快很多SomeTLBsstoreaddress-spaceidentifiers(ASIDs)ineachTLBentryuniquelyidentifieseachprocesstoprovideaddress-spaceprotectionforthatprocessTLB还可以在实现时通过记录记录进程地址空间标识，来实现对进程地址空间的保护,AssociativeMemory,AssociativememoryparallelsearchAddresstranslation(p,d)Ifpisinassociativeregister,getframe#outOtherwisegetframe#frompagetableinmemory,Page#,Frame#,PagingHardwareWithTLB,EffectiveAccessTime,下面是对基于TLB的内存访问速度的估计AssociativeLookup=timeunitAssumememorycycletimeis1microsecondHitratiopercentageoftimesthatapagenumberisfoundintheassociativeregisters;ratiorelatedtonumberofassociativeregistersTLB命中率=EffectiveAccessTime(EAT)EAT=(1+)+(2+)(1)=2+,MemoryProtection内存保护,Memoryprotectionimplementedbyassociatingprotectionbitwitheachframe内存保护是通过与每个页框关联上保护位来实现的Valid-invalidbit(有效位)attachedtoeachentryinthepagetable:“valid”indicatesthattheassociatedpageisintheprocesslogicaladdressspace,andisthusalegalpage“invalid”indicatesthatthepageisnotintheprocesslogicaladdressspace,Valid(v)orInvalid(i)BitInAPageTable,SharedPages页面共享,Sharedcode(共享代码)Onecopyofread-only(reentrant)codesharedamongprocesses(i.e.,texteditors,compilers,windowsystems).SharedcodemustappearinsamelocationinthelogicaladdressspaceofallprocessesPrivatecodeanddata(私有代码和数据)EachprocesskeepsaseparatecopyofthecodeanddataThepagesfortheprivatecodeanddatacanappearanywhereinthelogicaladdressspace,SharedPagesExample,8.5StructureofthePageTable,HierarchicalPagingHashedPageTablesInvertedPageTables,HierarchicalPageTables多层页表,Breakupthelogicaladdressspaceintomultiplepagetables将逻辑地址空间划分成若干个页表Asimpletechniqueisatwo-levelpagetable,Two-LevelPage-TableScheme,Two-LevelPagingExample,Alogicaladdress(on32-bitmachinewith1Kpagesize)isdividedinto:apagenumberconsistingof22bitsapageoffsetconsistingof10bitsSincethepagetableispaged,thepagenumberisfurtherdividedinto:a12-bitpagenumbera10-bitpageoffsetThus,alogicaladdressisasfollows:wherepiisanindexintotheouterpagetable,andp2isthedisplacementwithinthepageoftheouterpagetable,pagenumber,pageoffset,pi,p2,d,12,10,10,Address-TranslationScheme,Three-levelPagingScheme,HashedPageTables,Commoninaddressspaces32bits地址空间超过32位时常用（比如64位）Thevirtualpagenumberishashedintoapagetable.Thispagetablecontainsachainofelementshashingtothesamelocation.逻辑页号被做了一层哈希（因为逻辑页号也比较大）Virtualpagenumbersarecomparedinthischainsearchingforamatch.Ifamatchisfound,thecorrespondingphysicalframeisextracted.,HashedPageTable,InvertedPageTable反置页表,Oneentryforeachrealpageofmemory每个物理内存页拥有一个页表项。Entryconsistsofthevirtualaddressofthepagestoredinthatrealmemorylocation,withinformationabouttheprocessthatownsthatpage,InvertedPageTableArchitecture,InvertedPageTable反置页表,Decreasesmemoryneededtostoreeachpagetable,butincreasestimeneededtosearchthetablewhenapagereferenceoccurs查页表的时候需要一个搜索的过程Usehashtabletolimitthesearchtooneoratmostafewpage-tableentries,8.6Segmentation分段,Logicaladdressconsistsofatwotuple:,Segmenttablemapstwo-dimensionalphysicaladdresses;eachtableentryhas:basecontainsthestartingphysicaladdresswherethesegmentsresideinmemorylimitspecifiesthelengthofthesegmentSegment-tablebaseregister(STBR)pointstothesegmenttableslocationinmemorySegment-tablelengthregister(STLR)indicatesnumberofsegmentsusedbyaprogram;segmentnumbersislegalifsSTLR,8.6Segmentation,逻辑地址格式,例如：地址是32位长度，段号占12位，段内地址占20位，则地址0 x014ceaf8所处段号为0 x14，段内地址为0 xceaf8,8.6Segmentation分段,Segmenttable(段表)mapstwo-dimensionalphysicaladdresses;每个段表项中的内容包括:Base(段基址)containsthestartingphysicaladdresswherethesegmentsresideinmemoryLimit(段内偏移)specifiesthelengthofthesegment实现段表的时候，提供两个基本的寄存器：Segment-tablebaseregister(STBR)指向段表在内存中的基地址Segment-tablelengthregister(STLR)记录段表的长度段号s合法的条件：sSTLR,Segme