CCH09_Memory Management(操作系统).ppt

Module9 MemoryManagement Background 背景 LogicalversusPhysicalAddressSpace 逻辑与物理地址空间 ContiguousAllocation 连续分配 Paging 分页 Segmentation 分段 SegmentationwithPaging 段页式 Swapping 交换 存储层次结构 Background Background Programmustbebroughtintomemoryandplacedwithinaprocessforittobeexecuted 程序必需放入一个进程 并且送入内存才能被执行 Inputqueue collectionofprocessesonthediskthatarewaitingtobebroughtintomemoryforexecution 输入队列 磁盘上等待进入内存并执行的进程的集合 Userprogramsgothroughseveralstepsbeforebeingexecuted 用户程序在执行之前必需经历很多步骤 Background 源程序 编译 目标模块 库 链接程序 装入模块 装入程序 内存 Logicalvs PhysicalAddressSpace 重定位Theconceptofalogicaladdressspacethatisboundtoaseparatephysicaladdressspaceiscentraltopropermemorymanagement 逻辑地址空间的概念同物理地址空间相关联 它是正确内存管理的中心 Logicaladdress generatedbytheCPU alsoreferredtoasvirtualaddress 逻辑地址 由CPU产生 也叫做虚拟空间 Physicaladdress addressseenbythememoryunit 物理地址 内存设备所读入的地址 Logicalandphysicaladdressesarethesameincompile timeandload timeaddress bindingschemes logical virtual andphysicaladdressesdifferinexecution timeaddress bindingscheme 逻辑和物理地址在编译时期和装入时期的地址绑定策略是相同的 而在执行时间的地址绑定策略是不同的 BindingofInstructionsandDatatoMemory Compiletime 编译时期 Ifmemorylocationknownapriori absolutecodecanbegenerated mustrecompilecodeifstartinglocationchanges 如果内存位置已知 可生成绝对代码 如果开始位置改变 需要重新编译代码 Loadtime 装入时期 Mustgeneraterelocatablecodeifmemorylocationisnotknownatcompiletime 如果存储位置在编译时不知道 则必须生成可重定位代码 Executiontime 执行时期 Bindingdelayeduntilruntimeiftheprocesscanbemovedduringitsexecutionfromonememorysegmenttoanother Needhardwaresupportforaddressmaps e g baseandlimitregisters 如果进程在执行时可以在内存中移动 则地址绑定要延迟到运行时 需要硬件对地址映射的支持 例如基址和限长寄存器 Addressbindingofinstructionsanddatatomemoryaddressescanhappenatthreedifferentstages 指令和数据绑定到内存地址可以在三个不同的阶段发生 地址重定位 将程序装入到与其地址空间不一致的物理空间 所引起的一系列地址变换过程 静态地址重定位在装入一个作业时 把作业中的指令地址全部转换为绝对地址 在作业执行过程中就无须再进行地址转换工作 动态地址重定位 动态地址重地位是在程序执行过程中 在CPU访问内存之前 将要访问的程序或数据地址转换成内存地址 动态重定位依靠硬件地址变换机构完成 Memory ManagementUnit MMU Hardwaredevicethatmapsvirtualtophysicaladdress 硬件把虚拟地址映射到物理地址 InMMUscheme thevalueintherelocationregisterisaddedtoeveryaddressgeneratedbyauserprocessatthetimeitissenttomemory 在MMU策略中 基址寄存器中的值在其送入内存的时候被加入到用户进程所产生的每个地址中 Theuserprogramdealswithlogicaladdresses itneverseestherealphysicaladdresses 用户程序所对应到的是逻辑地址 物理地址对它从来都不可见 Memory ManagementUnit MMU Overlays Keepinmemoryonlythoseinstructionsanddatathatareneededatanygiventime 只是在内存中保留那些在特定时间所需要的指令和数据 Neededwhenprocessislargerthanamountofmemoryallocatedtoit 当进程比所分配的内存大时 覆盖是必需的 Implementedbyuser nospecialsupportneededfromoperatingsystem programmingdesignofoverlaystructureiscomplex 由用户执行 不需要操作系统的特别支持 覆盖结构的程序设计很复杂 要求用户清楚地了解程序的结构 并指定各程序段调入内存的先后次序 它是一种早期的主存扩充的方式 Overlays DynamicLoading Routineisnotloadeduntilitiscalled 例程在调用之前并不执行 Bettermemory spaceutilization unusedroutineisneverloaded 更好的内存空间利用率 没有被使用的例程不被载入 Usefulwhenlargeamountsofcodeareneededtohandleinfrequentlyoccurringcases 当需要大量的代码来处理不经常发生的事情时是非常有用的 Nospecialsupportfromtheoperatingsystemisrequiredimplementedthroughprogramdesign 不需要操作系统的特别支持 通过程序设计实现 DynamicLinking Linkingpostponeduntilexecutiontime 链接被推迟到执行时期 Smallpieceofcode stub usedtolocatetheappropriatememory residentlibraryroutine 小的代码片 存根 用来定位合适的保留在内存中的库程序 Stubreplacesitselfwiththeaddressoftheroutine andexecutestheroutine 存根用例程地址来替换自己 以及执行例程 Operatingsystemneededtocheckifroutineisinprocesses memoryaddress 操作系统需要检查例程是否在进程的内存空间 Swapping Aprocesscanbeswappedtemporarilyoutofmemorytoabackingstore andthenbroughtbackintomemoryforcontinuedexecution 一个进程可以暂时被交换到内存外的一个备份区 随后可以被换回内存继续执行 Backingstore fastdisklargeenoughtoaccommodatecopiesofallmemoryimagesforallusers mustprovidedirectaccesstothesememoryimages 备份区 是一个固定的足够大的可以容纳所有用户内存映像的拷贝 可以提供对这些内存映像的直接存取 由操作系统控制 利用外存空间 进程交换区 通过对进程实体的整体交换 来满足用户进程的内存需要 它的主要特点是打破了进程运行的驻留性 Swapping Rollout rollin swappingvariantusedforpriority basedschedulingalgorithms lower priorityprocessisswappedoutsohigher priorityprocesscanbeloadedandexecuted 滚入 滚出 交换由于基于优先级的算法而不同 低优先级的进程被换出 这样高优先级的进程可以被装入和执行 Majorpartofswaptimeistransfertime totaltransfertimeisdirectlyproportionaltotheamountofmemoryswapped 交换时间的主要部分是转移时间 总的转移时间直接同交换的内存的数量成比例 Modifiedversionsofswappingarefoundonmanysystems i e UNIXandMicrosoftWindows 在许多系统如 UNIX Windows中 可以找到一些被修正过的交换措施 SchematicViewofSwapping ContiguousAllocation Mainmemoryusuallydividedintotwopartitions 主存通常被分为两部分 Residentoperatingsystem usuallyheldinlowmemorywithinterruptvector 为操作系统保留的部分 通常用中断矢量保存在内存低端 Userprocessesthenheldinhighmemory 用户进程保存在内存高端 ContiguousAllocation 连续分配方式 为一个程序分配一段连续的内存空间 主要有 单独分区管理方式 多分区管理方式 是一种可用于多道程序的较简单的存储管理方式 又分为 固定分区方式可变分区方式Single partitionallocation 单独分区分配 Relocation registerschemeusedtoprotectuserprocessesfromeachother andfromchangingoperating systemcodeanddata 基址寄存器策略由来保护用户进程 同其他进程和改变的操作系统代码和数据分开 Relocationregistercontainsvalueofsmallestphysicaladdress limitregistercontainsrangeoflogicaladdresses eachlogicaladdressmustbelessthanthelimitregister 基址寄存器包含最小物理地址的值 限长寄存器包含逻辑地址的范围 每个逻辑地址必需比限长寄存器的值小 ContiguousAllocation 固定分区 FixedPartitioning 分配 固定式分区是在作业装入之前 内存就被划分成若干个固定大小的连续分区 划分工作可以由系统管理员完成 也可以由操作系统实现 一旦划分完成 在系统运行期间不再重新划分 即分区的个数不可变 分区的大小不可变 所以 固定式分区又称为静态分区 划分分区的方法如下 分区大小相等 只适用于多个相同程序的并发执行 处理多个类型相同的对象 缺乏灵活性 分区大小不等 多个小分区 适量的中等分区 少量的大分区 根据程序的大小 分配当前空闲的 适当大小的分区 固定分区 大小相同 固定分区 多种大小 固定分区 FixedPartitioning 分配 一般将内存的用户区域划分成大小不等的分区 可适应不同大小的作业的需要系统有一张分区说明表 每个表目说明一个分区的大小 起始地址和是否已分配的使用标志分区说明表和内存分配图如下所示 分区说明表 内存分配图 固定分区分配 优点 易于实现 开销小 缺点 分区大小固定 内碎片分区总数固定 限制并发执行的进程数目 采用的数据结构 分区表 记录分区的大小和使用情况 ContiguousAllocation Cont Multiple partitionallocation 多分区分配 Hole blockofavailablememory holesofvarioussizearescatteredthroughoutmemory 分区 可用的内存块 不同大小的分区分布在整个内存中 Whenaprocessarrives itisallocatedmemoryfromaholelargeenoughtoaccommodateit 当一个进程到来的时候 它将从一个足够容纳它分区中分配内存 Operatingsystemmaintainsinformationabout 操作系统包含以下信息 a allocatedpartitions 分配的分区 b freepartitions hole 空的分区 OS process5 process8 process2 OS process5 process2 OS process5 process2 OS process5 process9 process2 process9 process10 空闲分区的管理 空闲分区表 前向指针 后向指针 空闲分区链 ContiguousAllocation Cont DynamicStorage AllocationProblem First fit 首先适应 Allocatethefirstholethatisbigenough 分配最先找到的合适的分区 Best fit 最佳适应 Allocatethesmallestholethatisbigenough mustsearchentirelist unlessorderedbysize Producesthesmallestleftoverhole 搜索整个序列 找到适合条件的最小的分区进行分配 Worst fit 最差适应 Allocatethelargesthole mustalsosearchentierlist Producesthelargestleftoverhole 搜索整个序列 寻找最大的分区进行分配 Howtosatisfyarequestofsizenfromalistoffreeholes 怎样从一个空的分区序列中满足一个申请需要 First fitandbest fitbetterthanworst fitintermsofspeedandstorageutilization 在速度和存储的利用上 首先适应和最佳适应要比最差适应好 首次适应算法 FirstFit 从空闲分区表的第一个表目开始查找 把找到的第一个满足要求的空闲区分配给作业 目的在于减少查找时间 通常将空闲分区表 空闲区链 中的空闲分区要按地址由低到高进行排序 特点 分配和释放的时间性能较好 较大的空闲分区可以被保留在内存高端 随着低端分区不断划分而产生较多小分区 每次分配时查找时间开销会增大 在系统不断地分配和回收中 必定会出现一些不连续的小的空闲区 称为外碎片 虽然可能所有碎片的总和超过某一个作业的要求 但是由于不连续而无法分配 最佳适应算法 BestFit 从全部空闲区中找出能满足作业要求的 且最小的空闲分区 能使碎片尽量小为提高查找效率 空闲分区表 空闲区链 中的空闲分区要按从小到大进行排序 自表头开始查找到第一个满足要求的自由分区分配特点 从个别来看 外碎片较小 但从整体来看 会形成较多无法利用的碎片 较大的空闲分区可以被保留 ContiguousAllocation Cont Fragmentation Externalfragmentation 外碎片 totalmemoryspaceexiststosatisfyarequest butitisnotcontiguous 整个内存空间用来满足一个请求 但它不是连续的 Internalfragmentation 内碎片 allocatedmemorymaybeslightlylargerthanrequestedmemory thissizedifferenceismemoryinternaltoapartition butnotbeingused 分配的内存可能比申请的内存大一点 这两者之间的差别是内部不被使用的簇 紧缩Reduceexternalfragmentationbycompaction 通过压缩来减少外碎片 Shufflememorycontentstoplaceallfreememorytogetherinonelargeblock 把一些小的空闲内存结合成一个大的块 Compactionispossibleonlyifrelocationisdynamic andisdoneatexecutiontime 只有重置是动态的时候 才有可能进行压缩 压缩在执行时期进行 I Oproblem I O问题 LatchjobinmemorywhileitisinvolvedinI O 当I O的时候 把工作锁定在内存中 DoI OonlyintoOSbuffers 只对操作系统的缓冲区进行I O Fragmentation 实现紧凑的技术必须获得硬件支持 只有具有动态重定位硬件机构的计算机系统 才有可能采用动态重定位可变分区管理技术 系统的硬件包括重定位寄存器和加法器 Paging 分页存储管理是解决存储碎片的一种方法 Logicaladdressspaceofaprocesscanbenoncontiguous processisallocatedphysicalmemorywheneverthelatterisavailable 进程的逻辑地址空间可能是不连续的 如果有可用的物理内存 它将分给进程 Dividephysicalmemoryintofixed sizedblockscalledframes sizeispowerof2 between512bytesand8192bytes 把物理内存分成大小固定的块 Dividelogicalmemoryintoblocksofsamesizecalledpages 把逻辑内存也分为固定大小的块 叫做页 Keeptrackofallfreeframes 保留一个页的记录 Torunaprogramofsizenpages needtofindnfreeframesandloadprogram 运行一个有N页大小的程序 需要找到N个空的页框读入程序 Setupapagetabletotranslatelogicaltophysicaladdresses 建立一个页表 把逻辑地址转换为物理地址 Internalfragmentation 内碎片 AddressTranslationScheme AddressgeneratedbyCPUisdividedinto CPU产生的地址被分为 Pagenumber p 页号 usedasanindexintoapagetablewhichcontainsbaseaddressofeachpageinphysicalmemory 它包含每个页在物理内存中的基址 用来作为页表的索引 Pageoffset d 偏移 combinedwithbaseaddresstodefinethephysicalmemoryaddressthatissenttothememoryunit 同基址相结合 用来确定送入内存设备的物理内存地址 Forgivenlogicaladdressspace2mandpagesize2n pagenumber pageoffset p d m n n AddressTranslationArchitecture 地址结构 图中的地址长度为32位 允许地址空间的大小最多为1M个页 P A L 整除 W AMODL 取余 程序经过编译链接后形成逻辑地址 对某特定机器其地址结构是一定的 若给定一个逻辑地址为A 十进制 页面大小为L 则页号P和页内地址W可按下式求得 PagingExample PagingExample ImplementationofPageTable Pagetableiskeptinmainmemory 页表被保存在主存中 Page tablebaseregister PTBR pointstothepagetable 页表基址寄存器指向页表 Page tablelengthregister PRLR indicatessizeofthepagetable 页表限长寄存器表明页表的长度 Inthisschemeeverydata instructionaccessrequirestwomemoryaccesses Oneforthepagetableandoneforthedata instruction 在这个机制中 每一次的数据 指令存取需要两次内存存取 一次是存取页表 一次是存取数据 Thetwomemoryaccessproblemcanbesolvedbytheuseofaspecialfast lookuphardwarecachecalledassociativeregistersortranslationlook asidebuffers TLBs 通过一个联想寄存器 可以解决两次存取的问题 ImplementationofPageTable AssociativeRegister Associativeregisters parallelsearch 联想寄存器 并行查找 Addresstranslation A A 地址转换 IfA isinassociativeregister getframe out 如果A 在联想寄存器中 把页框 取出来 Otherwisegetframe frompagetableinmemory 否则从内存中的页表中取出页框 Page Frame EffectiveAccessTime AssociativeLookup timeunit 联想寄存器的查找需要时间 Assumememorycycletimeis1microsecond 假设内存一次存取要1微秒 Hitration percentageoftimesthatapagenumberisfoundintheassociativeregisters rationrelatedtonumberofassociativeregisters 命中率 在联想寄存器中找到页号的比率 比率与联想寄存器的大小有关 Hitratio EffectiveAccessTime EAT 有效存取时间 EAT 1 2 1 2 EffectiveAccessTime 例如 假设检索联想存储器的时间为20ns 访问内存的时间为100ns 访问联想存储器的命中率为85 则CPU存取一个数据的平均时间 T 0 85 120 0 15 220 135ns 访问时间只增加35 如果不引入联想存储器 其访问将延长一倍 达200ns 页式地址变换 虚地址 逻辑地址 程序地址 以十六进制 八进制 二进制的形式给出将虚地址转换成二进制的数 按页的大小分离出页号和位移量 低位部分是位移量 高位部分是页号 虚地址以十进制数给出页号 虚地址 页大小位移量 虚地址mod页大小以页号查页表 得到对应页装入内存的块号内存地址 块号 页大小 位移量 举例 例1 有一系统采用页式存储管理 有一作业大小是8KB 页大小为2KB 依次装入内存的第7 9 A 5块 试将虚地址0AFEH 1ADDH转换成内存地址 虚地址0AFEH0000101011111110P 1W 01011111110MR 0100101011111110 4AFEH虚地址1ADDH0001101011011101P 3W 01011011101MR 0010101011011101 2ADDH MemoryProtection Memoryprotectionimplementedbyassociatingprotectionbitwitheachframe 内存的保护由与每个页框相连的保护位来执行 Valid invalidbitattachedtoeachentryinthepagetable 有效 无效位附在页表的每个表项中 valid indicatesthattheassociatedpageisintheprocess logicaladdressspace andisthusalegalpage 有效 表明相关的页在进程的逻辑地址空间 以及是一个合法的页 invalid indicatesthatthepageisnotintheprocess logicaladdressspace 无效 表明页不在进程的逻辑地址空间中 MemoryProtection Two LevelPage TableScheme 将页表进行分页 每个页面的大小与内存物理块的大小相同 并为它们进行编号 可以离散地将各个页面分别存放在不同的物理块中 为此再建立一张页表 称为外层页表 页表目录 即第一级页表 其中的每个表目是存放某个页表的物理地址 第二级才是页表 其中每个物理块上的页表叫做页表分页 其中的每个表目所存放的才是页的物理块号 Two LevelPage TableScheme Two LevelPagingExample Alogicaladdress on32 bitmachinewith4Kpagesize isdividedinto 一个逻辑地址被分为 apagenumberconsistingof20bits 一个20位的页号 apageoffsetconsistingof12bits 一个12位的偏移 Sincethepagetableispaged thepagenumberisfurtherdividedinto 页表页被分为 a10 bitpagenumber 一个10位的页号 a10 bitpageoffset 一个10位的偏移 Thus alogicaladdressisasfollows 因此 一个逻辑地址表示如下 wherepiisanindexintotheouterpagetable andp2isthedisplacementwithinthepageoftheouterpagetable pagenumber pageoffset pi p2 d 10 10 12 Address TranslationScheme Address translationschemeforatwo level32 bitpagingarchitecture 一个两级32位分页结构的地址转换机制 MultilevelPagingandPerformance Sinceeachlevelisstoredasaseparatetableinmemory coveringalogicaladdresstoaphysicalonemaytakefourmemoryaccesses 由于每一级都分开的以表的形式存储在内存中 把一个逻辑地址转换为一个物理地址可能要进行4次内存存取 Eventhoughtimeneededforonememoryaccessisquintupled cachingpermitsperformancetoremainreasonable 尽管每次内存存取的时间是很大的 高速缓存使执行的时间还是可以接受的 Cachehitrateof98percentyields 如果缓存的命中率有98 则 effectiveaccesstime 0 98x120 0 02x520 128nanoseconds whichisonlya28percentslowdowninmemoryaccesstime 这只把内存存取时间降低了28 InvertedPageTable Oneentryforeachrealpageofmemory 一个内存中页的表项 Entryconsistsofthevirtualaddressofthepagestoredinthatrealmemorylocation withinformationabouttheprocessthatownsthatpage 表项包含真正内存地址的页的虚拟地址 它包括拥有这个页的进程的信息 Decreasesmemoryneededtostoreeachpagetable butincreasestimeneededtosearchthetablewhenapagereferenceoccurs 减少内存需要储存每个页表 但是当访问一个页时 寻找页表需要增加时间 Usehashtabletolimitthesearchtoone oratmostafew page tableentries 使用哈希表来减少搜索 InvertedPageTableArchitecture SharedPages Sharedcode 共享代码 Onecopyofread only reentrant codesharedamongprocesses i e texteditors compilers windowsystems 一个只读 可再入 代码可由进程共享 Sharedcodemustappearinsamelocationinthelogicaladdressspaceofallprocesses 共享代码出现在所有进程的逻辑地址空间的相同位置 Privatecodeanddata 私有代码和数据 Eachprocesskeepsaseparatecopyofthecodeanddata 每个进程保留一个代码和数据的私有拷贝 Thepagesfortheprivatecodeanddatacanappearanywhereinthelogicaladdressspace 私有代码和数据的页可以出现在逻辑地址空间的任何地方 SharedPagesExample Segmentation Memory managementschemethatsupportsuserviewofmemory 内存管理机制支持用户观点的内存 Aprogramisacollectionofsegments Asegmentisalogicalunitsuchas 一个程序是一些段的集合 一个段是一个逻辑单位 如 mainprogram procedure function localvariables globalvariables commonblock stack symboltable arrays LogicalViewofSegmentation userspace physicalmemoryspace SegmentationHardware SegmentationArchitecture Logicaladdressconsistsofatwotuple 一个逻辑地址是两个向量的集合 Segmenttable mapstwo dimensionalphysicaladdresses eachtableentryhas 段表 映射二维物理地址 每个表项包括 base containsthestartingphysicaladdresswherethesegmentsresideinmemory 基址 包括内存中段物理地址的起始地址 limit specifiesthelengthofthesegment 限长 指定段的长度 Segment tablebaseregister STBR pointstothesegmenttable slocationinmemory 段表基址寄存器指向段表在内存中的地址 Segment tablelengthregister STLR indicatesnumberofsegmentsusedbyaprogram 段表限长寄存器表明被一个程序所使用的段的数目 segmentnumbersislegalifs STLR SegmentationArchitecture Cont Relocation 重定位 dynamic 动态 bysegmenttable 由段表来执行 Sharing 共享 sharedsegments 共享的段 samesegmentnumber 同样的段号 Allocation 分配 firstfit bestfit 首先 最佳适配 externalfragmentation 外碎片 SegmentationArchitecture Cont Protection Witheachentryinsegmenttableassociate 保护 每个段表的表项有 validationbit 有效位 0 illegalsegmentread write executeprivileges 读 写 执行权利 Protectionbitsassociatedwithsegments codesharingoccursatsegmentlevel 保护位同段相联系 在段的级别进行代码共享 Sincesegmentsvaryinlength memoryallocationisadynamicstorage allocationproblem 由