西安交通大学操作系统原理课件第八章.ppt

Chapter8MemoryManagement Background 背景 ContiguousAllocation 连续分配 Paging 分页 Segmentation 分段 SegmentationwithPaging 段页式 Examples 存储层次结构 8 1Background 计算机存储系统的设计主要考虑三个问题 容量 速度和成本 8 1Background Programmustbebroughtintomemoryandplacedwithinaprocessforittobeexecuted 程序要得以运行 必须创建一个进程 并且送入内存 Userprogramsgothroughseveralstepsbeforebeingexecuted 用户程序在执行之前必需经历很多步骤 程序的装入和链接 源程序 编译 目标模块 库 链接程序 装入模块 装入程序 内存 MultistepProcessingofaUserProgram Logicalvs PhysicalAddressSpace AddressSpace地址空间 一个目标程序所限定的地址范围地址空间是逻辑地址的集合Logical Virtualaddress AnaddressviewedbytheuserprocessTheabstractionprovidedbytheOS存储空间是物理地址的集合PhysicaladdressAnaddressviewedbythephysicalmemory 地址重定位 将程序装入到与其地址空间不一致的物理空间 所引起的一系列地址变换过程 静态地址重定位在装入一个作业时 把作业中的指令地址全部转换为绝对地址 在作业执行过程中就无须再进行地址转换工作 动态地址重定位在程序执行过程中 在CPU访问内存之前 将要访问的程序或数据地址转换成内存地址 动态重定位依靠硬件地址变换机构完成 DynamicAddressTranslation UserProcess Translator MMU Physicalmemory Virtualaddress Physicaladdress BindingofInstructionsandDatatoMemory Addressbindingofinstructionsanddatatomemoryaddressescanhappenatthreedifferentstages 指令和数据绑定到内存地址可以在3个不同的阶段发生 Compiletime 编译时期 Ifmemorylocationknownapriori absolutecodecanbegenerated mustrecompilecodeifstartinglocationchanges 如果内存位置已知 可生成绝对代码 如果开始位置改变 需要重新编译代码 Loadtime 装入时期 Mustgeneraterelocatablecodeifmemorylocationisnotknownatcompiletime 如果存储位置在编译时不知道 则必须生成可重定位代码 Executiontime 执行时期 Bindingdelayeduntilruntimeiftheprocesscanbemovedduringitsexecutionfromonememorysegmenttoanother Needhardwaresupportforaddressmaps e g baseandlimitregisters 如果进程在执行时可以在内存中移动 则地址绑定要延迟到运行时 需要硬件对地址映射的支持 例如基址和限长寄存器 Memory ManagementUnit MMU Hardwaredevicethatmapsvirtualtophysicaladdress 实现虚拟地址映射到物理地址的硬件 InMMUscheme thevalueintherelocationregisterisaddedtoeveryaddressgeneratedbyauserprocessatthetimeitissenttomemory 在MMU策略中 当用户进程被装入内存时 基址寄存器中的值被加入到用户进程所产生的每个地址中 Memory ManagementUnit MMU 内外存间的数据交换 overlay覆盖由用户程序控制要求用户清楚地了解程序的结构 并指定各程序段调入内存的先后次序 它是一种早期的主存扩充的方式swapping交换由操作系统控制利用外存空间 进程交换区 通过对进程实体的整体交换 来满足用户进程的内存需要 它的主要特点是打破了进程运行的驻留性 overlay 主程序 30K Swapping Aprocesscanbeswappedtemporarilyoutofmemorytoabackingstore andthenbroughtbackintomemoryforcontinuedexecutionMajorpartofswaptimeistransfertime totaltransfertimeisdirectlyproportionaltotheamountofmemoryswappedModifiedversionsofswappingarefoundonmanysystems i e UNIX Linux andWindows Swapping 操作系统 B C D 操作系统 D C 操作系统 A D C SchematicViewofSwapping 常用的内存信息保护方法有 1上下界地址寄存器2存储键 内存保护 界地址寄存器 界地址寄存器是广泛使用的一种存储保护技术 机制简单 易于实现实现方法 在CPU中设置一对下限寄存器和上限寄存器存放用户作业在主存中的下限和上限地址也可将一个寄存器作为基址寄存器 另一寄存器作为限长寄存器 指示存储区长度 每当CPU要访问主存 硬件自动将被访问的主存地址与界限寄存器的内容进行比较 以判断是否越界如果未越界 则按此地址访问主存 否则将产生程序中断 越界中断 存储保护中断 BaseandBounds Processhasillusionofrunningonitsowndedicatedmachinewithmemory 0 bound Physicalmemory 0 base base bound physicalmemorysize virtualmemory 0 bound 存储键 每个存储块有一个由二进制位组成的存储保护键一用户作业被允许进入主存 OS分给它一个唯一的存储键号 并将分配给该作业各存储块的存储键也置成同样键号当OS挑选该作业运行时 OS将它的存储键号放入程序状态字PSW存储键 钥匙 域中每当CPU访问主存时 都将该主存块的存储键与PSW中的 钥匙 进行比较如果相匹配 则允许访问 否则 拒绝并报警 8 2存储器管理方式 连续分配方式 为一个程序分配一段连续的内存空间 主要有 单一连续区管理方式 多分区管理方式 是一种可用于多道程序的较简单的存储管理方式 又分为 固定分区方式可变分区方式 8 2存储器管理方式 离散分配方式 减少连续分配所产生的碎片 提高内存的利用率 将一个用户程序离散地分配到内存中的多个不相连接的区域中分页存储管理方式分段存储管理方式段页式存储管理方式 虚拟存储管理方式 满足用户对大容量内存的需要 提高内存利用率 请求分页管理方式请求分段管理方式请求段页式管理方式 8 2存储器管理方式 8 2 1ContiguousAllocation Mainmemoryusuallydividedintotwopartitions 主存通常被分为两部分 Residentoperatingsystem usuallyheldinlowmemorywithinterruptvector 为操作系统保留的部分 通常与中断矢量保存在内存低端 Userprocessesthenheldinhighmemory 用户进程保存在内存高端 8 2 1ContiguousAllocation Single partitionallocation单一分区分配Multiple partitionallocation多分区分配FixedPartitioning固定分区DynamicPartitioning可变分区 动态分区DynamicRelocationablePartitioning动态可重定位分区 Single partitionallocation 单一分区分配 内存分成两部分 OS区用户区用户区只能容纳一道作业 存储保护 Relocation registerschemeusedtoprotectuserprocessesfromeachother andfromchangingoperating systemcodeanddata 基址寄存器策略用来保护用户进程 同操作系统代码和数据分开 Relocationregistercontainsvalueofsmallestphysicaladdress limitregistercontainsrangeoflogicaladdresses eachlogicaladdressmustbelessthanthelimitregister 基址寄存器包含最小物理地址的值 限长寄存器包含逻辑地址的范围 每个逻辑地址必须小于限长寄存器的值 Single partitionallocation 单一分区分配 HardwareSupportforRelocationandLimitRegisters FixedPartitioning 固定分区是在作业装入之前 内存就被划分成若干个固定大小的连续分区 划分工作可以由系统管理员完成 也可以由操作系统实现 一旦划分完成 在系统运行期间不再重新划分 即分区的个数不可变 分区的大小不可变 又称为静态分区 FixedPartitioning 划分分区的方法如下 分区大小相等 只适用于多个大小相同程序的并发执行 缺乏灵活性 分区大小不等 多个小分区 适量的中等分区 少量的大分区 根据程序的大小 分配当前空闲的 适当大小的分区 固定分区 大小相同 固定分区 多种大小 FixedPartitioning 一般将内存的用户区域划分成大小不等的分区 可适应不同大小的作业需要 系统有一张分区说明表 每个表目说明一个分区的大小 起始地址和是否已分配的使用标志 FixedPartitioning 分区说明表 内存分配图 FixedPartitioning 优点 易于实现 开销小 缺点 分区大小固定 内碎片分区总数固定 限制并发执行的进程数目 要求Xk大小分区 取分区说明表第一项 状态位置正在使用 取下一表项 无法分配 该分区空闲 分区长度 Xk 表结束 返回分区号 否 否 否 是 是 是 固定分区分配算法 DynamicStorage Allocation Multiple partitionallocation 多分区分配 分区的划分是动态的 不是预先确定的Whenaprocessarrives itisallocatedmemoryfromaholelargeenoughtoaccommodateit 当一个进程到来的时候 它将从一个足够容纳它的分区中分配内存 OS process5 process8 process2 OS process5 process2 OS process5 process2 OS process5 process9 process2 process9 process10 空闲分区的管理 空闲分区表 前向指针 后向指针 空闲分区链 可变分区分配算法 分区分配算法 寻找某个空闲分区 若大于要求 则将该分区分割成两个分区 其中一个分区为要求的大小并标记为 占用 而另一个分区为余下部分并标记为 空闲 分区分配的先后次序通常是从内存低端到高端 分区释放算法 需要将相邻的空闲分区合并成一个空闲分区 这时要解决的问题是 合并条件的判断 可变分区分配算法框图 DynamicStorage AllocationProblem First fit 首次适应 Allocatethefirstholethatisbigenough 分配最先找到的合适的分区 Best fit 最佳适应 Allocatethesmallestholethatisbigenough mustsearchentirelist unlessorderedbysize Producesthesmallestleftoverhole 搜索整个序列 找到适合条件的最小的分区进行分配 Worst fit 最差适应 Allocatethelargesthole mustalsosearchentirelist Producesthelargestleftoverhole 搜索整个序列 寻找最大的分区进行分配 首次适应算法 FirstFit 从空闲分区表的第一个表目开始查找 把找到的第一个满足要求的空闲区分配给作业 目的在于减少查找时间 通常将空闲分区表 空闲区链 中的空闲分区按地址由低到高进行排序 特点 分配和释放的时间性能较好 较大的空闲分区可以被保留在内存高端 随着低端分区不断划分而产生较多小分区 每次分配时查找时间开销会增大 从该空闲区中截取所需大小 修改调整分区表 从空闲分区表第一表目顺序查找 从分区表中移去该表目 调整分区表 取下一表项 无法分配 该空闲区长度 SIZE 该空闲区长度 SIZE 表目查完 返回分配起始地址 否 否 否 是 是 是 First fit 循环首次适应算法 NextFit 循环首次适应算法 是首次适应算法的变种 在分配内存空间时 不再每次从表头 链首 开始查找 而是从上次找到的空闲区的下一个空闲区开始查找 并采用循环查找的方式 直到找到第一个能满足要求的空闲区为止 并从中划出一块与请求大小相等的内存空间分配给作业 特点 算法的分配和释放的时间性能较好 使空闲分区分布得更均匀较大的空闲分区不易保留 最佳适应算法 BestFit 从全部空闲区中找出能满足作业要求的 且最小的空闲分区 能使碎片尽量小为提高查找效率 空闲分区表 空闲区链 中的空闲分区要按从小到大进行排序 自表头开始查找到第一个满足要求的自由分区分配特点 从个别来看 外碎片较小 但从整体来看 会形成较多无法利用的碎片 较大的空闲分区可以被保留 动态分区分配算法举例 Lastallocatedblock 14K 分配前 分配后 8K 8K 12K 12K 22K 18K 6K 6K 8K 8K 14K 14K 6K 2K 36K 20K BestFit FirstFit 例 需分配一个16KB分区 NextFit 动态重定位分区分配 动态分区的碎片问题 在系统不断地分配和回收中 必定会出现一些不连续的小的空闲区 称为外碎片 虽然可能所有碎片的总和超过某一个作业的要求 但是由于不连续而无法分配 解决碎片的方法是拼接 或称紧凑 即向一个方向 例如向低地址端 移动已分配的作业 使那些零散的小空闲区在另一方向连成一片 分区的拼接技术 一方面要求能够对作业进行重定位 另一方面系统在拼接时要耗费较多的时间 Fragmentation 动态重定位分区分配 实现紧凑的技术必须获得硬件支持只有具有动态重定位硬件机构的计算机系统 才有可能采用动态重定位可变分区管理技术 系统的硬件包括重定位寄存器和加法器 8 2 2Paging 分页存储管理是解决存储碎片的一种方法 动态重定位是解决存储碎片问题的一种途径 但要移动大量信息从而浪费处理机时间 代价比较高 这是因为这种分配要求把作业必须安置在一连续存储区内的缘故 而分页存储管理正是要避开这种连续性要求 8 2 2Paging Dividephysicalmemoryintofixed sizedblockscalledframes sizeispowerof2 between512bytesand8192bytes 物理内存分成大小固定的块 称为物理块或页框 Dividelogicalmemoryintoblocksofsamesizecalledpages 逻辑内存也分为固定大小的块 叫做页 Torunaprogramofsizenpages needtofindnfreeframesandloadprogram 运行一个有N页大小的程序 需要找到N个空的页框装入程序 Setupapagetabletotranslatelogicaltophysicaladdresses 建立一个页表 把逻辑地址转换为物理地址 Internalfragmentation 内碎片 PagingModelofLogicalandPhysicalMemory PagingExample Paging AddressTranslationScheme AddressgeneratedbyCPUisdividedinto Pagenumber p usedasanindexintoapagetablewhichcontainsbaseaddressofeachpageinphysicalmemoryPageoffset d combinedwithbaseaddresstodefinethephysicalmemoryaddressthatissenttothememoryunit pagenumber pageoffset p d m n n PagingHardware 地址结构 图中的地址长度为32位 允许地址空间的大小最多为1M个页 程序经过编译链接后形成逻辑地址 对某特定机器其地址结构是一定的 Pagetable 实现从页号到物理块号的映射 ImplementationofPageTable PagetableiskeptinmainmemoryPage tablebaseregister PTBR pointstothepagetablePage tablelengthregister PRLR indicatessizeofthepagetableInthisschemeeverydata instructionaccessrequirestwomemoryaccesses OneforthepagetableOneforthedata instruction ImplementationofPageTable Cont Thetwomemoryaccessproblemcanbesolvedbytheuseofaspecialfast lookuphardwarecachecalledassociativememoryortranslationlook asidebuffers TLBs AssociativeMemory Associativememory parallelsearchAddresstranslation p d Ifpisinassociativeregister getframe outOtherwisegetframe frompagetableinmemory Page Frame PagingHardwareWithTLB EffectiveAccessTime AssociativeLookup timeunit 设联想寄存器的查找需要时间为 Assumememorycycletimeis1microsecond 假设内存一次存取要1微秒 Hitratio 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 基本的地址变换机构 实现从逻辑地址到物理地址的转换 将用户程序中的页号变换成内存中的物理块号地址变换机构 页表寄存器有效地址寄存器 逻辑地址寄存器 物理地址寄存器页表PCB中增加存放页表始址和页表长度的项 地址变换过程 按页的大小分离出页号和位移量 放入有效地址寄存器中将页号与页表长度进行比较 如果页号大于页表长度 越界中断 以页号为索引查找页表 将页表始址与页号和页表项长度的乘积相加 便得到该表项在页表中的位置 于是可从中得到该页的物理块号 将该物理块号装入物理地址寄存器的高址部分 将有效地址寄存器中的位移量直接复制到物理地址寄存器的低位部分 从而形成内存地址 分页地址变换机构工作原理 页式地址变换举例 页式地址变换 虚地址 逻辑地址 程序地址 以十六进制 八进制 二进制的形式给出将虚地址转换成二进制的数 按页的大小分离出页号和位移量 低位部分是位移量 高位部分是页号 将位移量直接复制到内存地址寄存器的低位部分 以页号查页表 得到对应页装入内存的块号 并将块号转换成二进制数填入地址寄存器的高位部分 从而形成内存地址 页式地址变换 虚地址以十进制数给出页号 虚地址 页大小位移量 虚地址mod页大小以页号查页表 得到对应页装入内存的块号内存地址 块号 页大小 位移量 页式地址变换举例 例1 有一系统采用页式存储管理 有一作业大小是8KB 页大小为2KB 依次装入内存的第7 9 A 5块 试将虚地址0AFEH 1ADDH转换成内存地址 虚地址0AFEH0000101011111110P 1W 01011111110MR 0100101011111110 4AFEH 页式地址变换举例 虚地址1ADDH0001101011011101P 3W 01011011101MR 0010101011011101 2ADDH 页式地址变换举例 例2 有一系统采用页式存储管理 有一作业大小是8KB 页大小为2KB 依次装入内存的第7 9 10 5块 试将虚地址7145 3412转换成内存地址 页式地址变换举例 虚地址3412P 3412 2048 1W 3412mod2048 1364MR 9 2048 1364 19796虚地址3412的内存地址是 19796 页式地址变换举例 虚地址7145P 7145 2048 3W 7145mod2048 1001MR 5 2048 1001 11241虚地址7145的内存地址是 11241 MemoryProtection Memoryprotectionimplementedbyassociatingprotectionbitwitheachframe 内存的保护由与每个页框相连的保护位来实现 保护位指出对某一页的访问权限 读 写Valid invalidbitattachedtoeachentryinthepagetable 有效 无效位附在页表的每个表项中 valid indicatesthattheassociatedpageisintheprocess logicaladdressspace andisthusalegalpage 有效 表明相关的页在进程的逻辑地址空间 是一个合法的页 invalid indicatesthatthepageisnotintheprocess logicaladdressspace 无效 表明页不在进程的逻辑地址空间中 MemoryProtection StructureofthePageTable HierarchicalPagingHashedPageTablesInvertedPageTables HierarchicalPageTables BreakupthelogicaladdressspaceintomultiplepagetablesAsimpletechniqueisatwo levelpagetable Two LevelPage TableScheme Intel80386的逻辑地址有232B 如页面大小为4KB 212B 则页表项达1M个 设每个页表项占用4B 则每个进程的页表占用4MB内存空间 还要求是连续的 显然这是不现实的 解决 在80386中 为了减少页表所占用的连续的内存空间 采用了两级页表机制 Two LevelPage TableScheme 将页表进行分页 并进行编号页表分页存放在不同的物理块中外层页表 页表目录 即第一级页表 指出页表分页的物理地址第二级页表 即页表分页 指出每个页对应的物理块号 Two LevelPage TableScheme Two LevelPagingExample Alogicaladdress on32 bitmachinewith4Kpagesize isdividedinto 一个逻辑地址被分为 apagenumberconsistingof20bits 一个20位的页号 apageoffsetconsistingof12bits 一个12位的偏移 Sincethepagetableispaged thepagenumberisfurtherdividedinto 页号被分为 a10 bitpagenumber 一个10位的页号 a10 bitpageoffset 一个10位的偏移 pagenumber pageoffset p1 p2 d 10 10 12 Address TranslationScheme Address translationschemeforatwo level32 bitpagingarchitecture 一个两级32位分页结构的地址转换机制 Three levelPagingScheme MultilevelPagingandPerformance 多级页表的引入 使逻辑地址到物理地址的变换时间增加了许多 二级页表需三次访存 三级页表需四次访存 四级页表需五次访存Cachehitrateof98percentyields 如果TLB的命中率有98 effectiveaccesstime 0 98x120 0 02x520 128nswhichisonlya28percentslowdowninmemoryaccesstime 这只把内存存取时间降低了28 HashedPageTables Commoninaddressspaces 32bitsThevirtualpagenumberishashedintoapagetableThispagetablecontainsachainofelementshashingtothesamelocationVirtualpagenumbersarecomparedinthischainsearchingforamatchIfamatchisfound thecorrespondingphysicalframeisextracted HashedPageTable InvertedPageTable 通常的页表为每个进程设置一张页表 其不足为浪费内存空间解决 倒置页表 按照整个物理内存建造一张表Oneentryforeachrealpageofmemory 内存中的每一块在表中占一项 Entryconsistsofthevirtualaddressofthepagestoredinthatrealmemorylocation withinformationabouttheprocessthatownsthatpage 每项包含进程的逻辑页号和进程标示 InvertedPageTable Decreasesmemoryneededtostoreeachpagetable butincreasestimeneededtosearchthetablewhenapagereferenceoccurs 减少了页表占用的内存空间量 但是增加了查找表的时间 因为页表是按物理块的顺序组织的 而查找是按虚地址进行的 InvertedPageTableArchitecture SharedPagesExample Threeprocessesshareed1 ed2anded3 优点 没有外碎片 每个内碎片不超过页大小 一个程序不必连续存放 缺点 程序全部装入内存 纯分页的特点 8 2 3Segmentation Memory managementschemethatsupportsuserviewofmemory 分段内存管理机制是从用户观点出发的 即为了方便用户 Aprogramisacollectionofsegments Asegmentisalogicalunitsuchas 一个程序是一些段的集合 一个段是一个逻辑单位 如 mainprogram procedure function localvariables globalvariables commonblock stack symboltable arrays User sViewofaProgram LogicalViewofSegmentation 1 3 2 4 userspace physicalmemoryspace Segmentation data stack code Physicalmemory Virtualmemorysegment1 Virtualmemorysegment3 Virtualmemorysegment0 6ff0 4ff0 fff0 46ff4000 2fff2000 4ff0 SegmentationArchitecture Logicaladdressconsistsofatwotuple Segmenttable mapstwo dimensionalphysicaladdresses eachtableentryhas base containsthestartingphysicaladdresswherethesegmentsresideinmemorylimit specifiesthelengthofthesegmentSegment tablebaseregister STBR pointstothesegmenttable slocationinmemorySegment tablelengthregister STLR indicatesnumberofsegmentsusedbyaprogram segmentnumbersislegalifs STLR SegmentationHardware ExampleofSegmentation 地址变换过程 系统将逻辑地址中的段号S与段表长度TL进行比较 若S TL 访问越界 若未越界 则根据段表的始址和该段的段号 计算出该段对应段表项的位置 从中读出该段在内存中的起始地址 然后再检查段内地址d是否超过该段的段长SL 若超过 即d SL 同样发出越界中断信号 若未越界 则将该段的基址与段内地址d相加 得到要访问的内存物理地址 地址变换 SegmentationArchitecture Cont Protection Witheachentryinsegmenttableassociate 保护 每个段表的表项有 validationbit 有效位 0 illegalsegmentread write executeprivileges 读 写 执行权利 Sincesegmentsvaryinlength memoryallocationisadynamicstorage allocationproblem 由于段的各个长度不同 内存分配是一个动态存储分配问题 SegmentationArchitecture Cont Relocation 重定位 dynamic 动态 bysegmenttable 通过段表来执行 Sharing 共享 sharedsegments codesegment datasegmentcodesegment samesegmentnumber 同样的段号 Allocation 分配 firstfit bestfit 首次 最佳适配 externalfragmentation 外碎片 程序通过分段 segmentation 划分为多个模块 如代码段 数据段 共享段 可以分别编写和编译可以针对不同类型的段采取不同的保护可以按段为单位来进行共享 包括通过动态链接进行代码共享优点 没有内碎片 外碎片可以通过内存紧缩来消除 便于改变进程占用空间的大小 缺点 进程全部装入内存 分段的特点 分页和分段比较 8 2 4SegmentationwithPaging 分页和分段存储管理方式都各有其优缺点 结合两种存储管理方式 则形成一种新的存储管理方式 段页式 分页系统 提高内存利用率分段系统 满足用户需要 8 2 4SegmentationwithPaging 基本原理将整个主存划分成大小相等的物理块 页框 把用户程序按程序的逻辑关系分为若干个段 并为每个段赋予一个段名把每个段划分成若干页 以页框为单位离散分配内存 地址结构由段号 段内页号和页内地址三部分组成 段表和页表实现从逻辑地址到物理地址的变换由于将段中的页进行离散地分配 段表中的内容不再是段的内存始址和段长 而是页表始址和页表长度 8 2 4SegmentationwithPaging 段表项 段表