段页式存储管理与动态地址重定位

1、段页式存储管理与动态地址重定位本章学习目标本章学习目标 存储管理的目的和四大基本功能。 实存管理中讲述了固定分区存储管理、可变式分区存储管理、纯分页存储管理三种存储管理方案的实现原理，内存的分配与回收方法. 虚存管理以请求式分页存储管理为重点，讲述其实现原理和动态地址重定位过程. 总结各种存储管理方案中存在的碎片和抖动问题及解决方法 第1页/共81页4.1 存储管理的功能存储管理的功能 4.1.1 内存的分配与回收 4.1.2 地址重定位 4.1.3 存储保护 4.1.4 虚拟存储器 返回首页第2页/共81页图4.1 多级存储器体系示意图第3页/共81页4.1.1 内存的分配与回收内存的分配与

2、回收 内存分配按分配时机的不同，可分为两种方式。（1）静态存储分配（2）动态存储分配 返回本节第4页/共81页4.1.2 地址重定位地址重定位 1内存空间（或物理空间） 2逻辑空间（如图4.2所示） 3地址重定位（分为：静态地址重定位和动态地址重定位） 第5页/共81页图4.2 作业的名空间、逻辑地址空间和装入后的物理空间第6页/共81页图4.3 静态地址重定位和动态地址重定位示意图（b）采用动态重定位时内存空 间及地址重定位示意图（a）采用静态重定位后的内存空间返回本节第7页/共81页4.1.3 存储保护存储保护（1）上、下界存储保护：上、下界保护是一种简单的存储保护技术。如图4.4（a）所

3、示 （2）基址限长存储保护：上、下界保护的一个变种是采用基址限长存储保护。如图4.4（b）所示。 第8页/共81页（a）上、下界保 （b）基址限长保护图4.4 界限寄存器的两种存储保护方式返回本节第9页/共81页4.1.4 虚拟存储器虚拟存储器 虚拟存储技术的基本思想是把有限的内存空间与大容量的外存统一管理起来，构成一个远大于实际内存的、虚拟的存储器。即把两级存储器当作一级存储器来看待。 对用户而言，感觉到系统提供了一个大容量的内存，供用户使用，但这样大容量的内存实际上并不存在，是一种虚拟的存储器，因此把具有这种功能的存储管理技术称为虚拟存储管理。返回本节第10页/共81页4.2 实存管理实存

4、管理 4.2.1 固定分区存储管理 4.2.2 可变式分区存储管理 4.2.3 纯分页存储管理 4.2.4 纯分段存储管理 返回首页第11页/共81页4.2.1 固定分区存储管理固定分区存储管理 固定分区存储管理是实现多道程序设计的最简单的一种存储管理技术。 其基本思想是，在作业未进入内存之前，就由操作员或操作系统把内存可用空间划分成若干个固定大小的存储区，除操作系统占用一个区域外，其余区域为系统中多个用户共享，因为在系统运行期间，分区大小、数目都不变，所以固定式分区也称为静态分区（如图4.5所示）。 第12页/共81页图4.5 固定式分区内存分配示意图（a）和（b）固定式分区说明表返回本节第

5、13页/共81页4.2.2 可变式分区存储管理可变式分区存储管理 1空闲分区的组织形式 2内存的分配与回收 3常用的分配算法 4可变式分区的地址重定位第14页/共81页图4.6 可变式分区内存使用情况示意图 第15页/共81页1空闲分区的组织形式空闲分区的组织形式 在可变式分区存储管理中，常把空闲区组成空闲分区表或空闲分区链表的形式。 空闲分区链表的组织是这样的：在每个空闲分区的起始部分开辟出一个单元，存放一个链表指针和该分区的大小，链表指针指向下一个空闲分区。 第16页/共81页图4.7 首次适应算法的空闲分区链表组织形式 第17页/共81页2内存的分配与回收内存的分配与回收 当某一个用户作

6、业完成释放所占分区时，系统应进行回收。在可变式分区中，应该检查回收区与内存中前后空闲区是否相邻，若相邻，则应进行合并，形成一个较大的空闲区，并对相应的链表指针进行修改；若不相邻，应将空闲区插入到空闲区链表的适当位置。第18页/共81页3常用的分配算法常用的分配算法 （1）首次适应算法 （2）最佳适应算法 （3）最差适应算法 第19页/共81页图4.8 最佳适应算法的空闲分区链表组织形式第20页/共81页图4.9 最差适应算法的空闲分区链表组织形式第21页/共81页图4.10 内存使用情况第22页/共81页图4.11 用三种适应算法处理同一作业序列第23页/共81页4可变式分区的地址重定位可变式

7、分区的地址重定位 可变式分区的地址重定位可采用静态重定位，也可采用动态重定位。采用动态重定位的可变式分区管理技术，在执行内存分配时，如无足够大空闲块，应考虑实现紧凑操作。其分配算法如图4.12所示。 可变式分区的存储保护可采用基址限长存储保护方式。第24页/共81页图4.12 采用动态重定位的可变式分区分配算法返回本节第25页/共81页4.2.3 纯分页存储管理纯分页存储管理 1纯分页存储管理中存储块的分配与回收 2纯分页存储管理的地址重定位问题 3联想存储器 4存储保护返回本节第26页/共81页1纯分页存储管理中存储块的分配与回收纯分页存储管理中存储块的分配与回收 纯分页存储管理中，存储块的

8、分配与回收算法比较简单。当作业有存储分配请求时，可以根据逻辑地址的大小计算出需要多少存储块，然后将空闲块分配给它们使用。通常有两种记录空闲存储块的方法：位图法和链表法。第27页/共81页操作系统操作系统作业1 作业2 作业2作业1 作业2 作业1 作业2 1110100110101010（a）存储块使用情况 （b）存储块使用情况的位图表示图4.13 存储块的位图管理法第28页/共81页2纯分页存储管理的地址重定位问题纯分页存储管理的地址重定位问题 要使不连续的、分散的用户程序能正常运行，须采用动态地址重定位。此时，可采用重定位寄存器方式，如分页太多，则重定位寄存器用得太多。 通常可在内存中为每

9、个作业开辟一块特定区域，建立起作业的逻辑页与存储块之间的对应表格关系，这种表常称为页面映像表，简称页表（如图4.144.15所示）。第29页/共81页图4.14 纯分页存储管理示意图第30页/共81页图4.15 纯分页存储管理地址重定位实现过程第31页/共81页3联想存储器联想存储器 为了提高查表的速度，人们在分页地址变换机构中，加入一组高速缓冲存储器，用来存放当前作业的最常用的页号和与之相应的物理块号。一般称这样的寄存器组为快表或联想存储器。采用联想存储器和内存中页表相结合的分页地址变换过程如图4.16所示。 应用联想存储器和页表相结合的方式，可有效地提高系统动态地址转换的速度，是一种行之有

10、效的方法。第32页/共81页利用快表查找 利用页表查找 利用页表中查找到的页号、块号更新快表图4.16 采用快表和页表相结合的分页地址变换过程示意图第33页/共81页4存储保护存储保护 存储信息保护可从两个方面实现: 在进行地址变换时，产生的页号应小于页表长度，否则视为越界访问，这类似于基址限长存储保护； 可在页表中增加存取控制和存储保护的信息，对每一个存储块，可允许四种保护方式：禁止做任何操作，只能执行，只能读，能读/写，当要访问某页时，先判断该页的存取控制和存储保护信息是否允许。返回本节第34页/共81页4.2.4 纯分段存储管理纯分段存储管理 1分段管理的基本思想 2地址变换 3分段与分

11、页的区别返回本节第35页/共81页1分段管理的基本思想分段管理的基本思想 分段存储管理是以段为基本单位分配内存，且每一段必须连续的内存空间，但各段之间不要求连续。由于各段的长度不一样，所以分配的内存空间大小也不一样。分段存储管理的逻辑地址结构如下：段号段号S段内位移段内位移W第36页/共81页2地址变换地址变换图4.17 分段存储管理的地址变换示意图 第37页/共81页表4.1 段表段号内存起始地址段长02105001235020210090表4.2 逻辑地址段号段内位移04301102500第38页/共81页3分段与分页的区别分段与分页的区别（1）页是信息的物理单位。段是信息的逻辑单位。（2

12、）分页存储管理的作业地址空间是一维的，而分段存储管理的是二维的。（3）页的大小固定且由系统确定，是等长的。而段的长度不定，它是由具有相对完整意义的信息长度确定。（4）分页的优点体现在内存空间的管理上，而分段的优点体现在地址空间的管理上。返回本节第39页/共81页4.3 虚拟存储器管理虚拟存储器管理 4.3.1 虚拟存储器的概念 4.3.2 请求式分页存储管理与动态地址重定位 4.3.3 页面置换算法 4.3.4 请求式分页存储管理性能分析举例 4.3.5 请求式分段存储管理与动态地址重定位 4.3.6 段页式存储管理与动态地址重定位 返回首页第40页/共81页4.3.1 虚拟存储器的概念虚拟存

13、储器的概念 虚拟存储器就是为用户提供了一个存储容量比实际主存大得多的存储器。 用户在编程时可以不考虑实际内存的大小，认为自己编写多大程序就有多大的虚拟存储器对应。每个用户可以在自己的逻辑地址空间中编程，在各自的虚拟存储器上运行。 采用虚拟存储管理技术，提供存储扩充的功能。 返回本节第41页/共81页4.3.2 请求式分页存储管理与动态地址重定位请求式分页存储管理与动态地址重定位 先把内存空间划分成大小相等的块，将用户逻辑地址空间划分成与块相等的页，每页可装入到内存中任一块中，这都类似于纯分页式存储管理。在请求式分页存储管理的地址重定位时，可能会出现所需页面不在主存的情况，如图4.18所示是请求

14、式分页存储管理的存储映像。 请求式分页存储管理中的地址重定位和缺页中断处理过程如图4.19所示。 第42页/共81页图4.18 请求式分页存储管理示意图第43页/共81页图4.19 请求式分页存储管理缺页中断处理过程示意图返回本节第44页/共81页4.3.3 页面置换算法页面置换算法 1最优算法（OPT算法） 2先进先出算法（FIFO算法） 3最久未使用页面置换算法（LRU算法） 4LRU近似算法第45页/共81页1最优算法（最优算法（OPT算法）算法） 最理想的页面置换算法是：从内存中移出以后不再使用的页面；如无这样的页面，则选择以后最长时间内不需要访问的页。这就是最优算法的思想。第46页/

15、共81页2先进先出算法（先进先出算法（FIFO算法）算法） 这种算法的基本思想是：总是先淘汰那些驻留在内存时间最长的页面，即先进入内存的页面先被置换掉。理由是：最先进入内存的页面不再被访问的可能性最大。这种算法实现起来比较简单。如图4.20所示 第47页/共81页图4.20 先进先出算法存储分块表构造 第48页/共81页3最久未使用页面置换算法（最久未使用页面置换算法（LRU算法）算法） 这种算法的基本思想是，如果某一页被访问了，那么它很可能马上又被访问；反之，如果某一页很长时间没有被访问，那么最近也不太可能会被访问。这种算法考虑了程序设计的局部性原理。其实质是，当需要置换一页时，选择在最近一

16、段时间最久未使用的页面予以淘汰。第49页/共81页4LRU近似算法近似算法 这种算法，只要在存储分块表（或页表）中设一个“引用位”，当存储分块表中的某一页被访问时，该位由硬件自动置1，并由页面管理软件周期性把所有引用位置0。这样，在一个时间周期T内，某些被访问过的页面其引用位为1，而未被访问过的页面其引用位为0。 根据引用位的状态来判别各页面最近的使用情况。当需要置换一页面时，选择其引用位为0的页，如图4.214.22所示的算法。第50页/共81页图4.21 LRU近似算法流程第51页/共81页图4.22 LRU近似算法举例返回本节第52页/共81页4.3.4 请求式分页存储管理性能分析举例请

17、求式分页存储管理性能分析举例 1程序设计的质量 2页面的大小 3分配的内存块数 4页面置换算法性能（如图4.244.24所示） 第53页/共81页图4.23 FIFO算法性能分析（m=3） 图4.24 FIFO算法性能分析（m=4）第54页/共81页图4.25 LRU算法性能分析（m=3）第55页/共81页图4.26 LRU算法性能分析（m=4） 返回本节第56页/共81页4.3.5 请求式分段存储管理与动态地址重定位请求式分段存储管理与动态地址重定位 1程序的逻辑地址结构 2段表 3请求式分段动态地址变换过程 4请求式分段存储管理的优、缺点第57页/共81页图4.27 分段的逻辑地址空间第5

18、8页/共81页1程序的逻辑地址结构程序的逻辑地址结构 请求式分段存储管理的逻辑地址结构由段号s和段内位移量d组成，如下图所示。用户逻辑地址空间的大小，由组成段号和段内位移量的二进制位数来决定。段号(s)段内位移量(d)23 16 15 0第59页/共81页2段表段表 为了实现动态地址变换和存储保护，系统要为每一个作业建立一张段表。段表中的每一个表目对应着作业地址空间的一个程序段，其一般格式为：段号段长状态位引用位改变位RWEA起始地址第60页/共81页3请求式分段动态地址变换过程请求式分段动态地址变换过程图4.28 请求式分段动态地址变换第61页/共81页4请求式分段存储管理的优、缺点请求式分

19、段存储管理的优、缺点 请求式分段存储管理有如下优点： （1）可提供大容量的虚存 （2）允许动态增加段的长度 （3）便于段的动态链接 （4）便于实现程序段的共享 （5）便于实现存储保护第62页/共81页 请求分段存储管理的缺点是进行地址变换和实现紧凑操作要花费处理机时间，为管理各分段要设立若干表格，需提供额外的存储空间，而且也会像请求分页存储管理一样出现系统抖动现象。返回本节第63页/共81页4.3.6 段页式存储管理与动态地址重定位段页式存储管理与动态地址重定位（1）作业地址空间进行段式管理。（2）每段内再分成若干大小固定的页，每段都从零开始为自己的各页依次编写连续的页号。（3）对内存空间的管

20、理仍然和分页存储管理一样，将其分成若干个和页面大小相同的物理块。（4）作业的逻辑地址包括3个部分：段号、页号和页内位移。（5）为实现地址变换，段页式系统设立了段表和页表。第64页/共81页图4.29 段表、页表和内存的关系 返回本节第65页/共81页4.4 碎片与抖动问题碎片与抖动问题 分区存储管理分为固定式分区和可变式分区存储管理两种。对于固定式分区存储管理来说，其分区大小是固定的，而一个作业的大小不可能与固定的分区大小刚好相等，所以容易产生内碎片问题，即已分配给某作业的固定分区中有作业使用不到的空闲内存区域。而可变式分区存储管理较好地解决了内碎片问题，一个作业需要多大内存就分配给它多大内存

21、。 返回首页第66页/共81页 解决碎片问题的比较好的方法是采用分页技术，在纯分页存储管理系统中，因存储区划分成固定大小的块，而用户作业也划分成与块相等的若干页，每个作业调入内存时，除最后一个页面可能有页内碎片出现外，其余页不存在碎片问题，一般来说，平均每个作业可能有半页的内碎片。 纯分页存储管理技术较为有效地利用了内存空间。 第67页/共81页 避免抖动现象最根本的方法是控制多道程序的道数，使得每个用户作业都有足够的内存空间可供使用。但作业的个数又不能太少，否则，会影响处理机的利用率。最好是使处理机利用率较高，又不致于使系统发生抖动，这是一个很难解决的问题，牵扯到程序的局部性问题，并需借助于

22、工作集模型。第68页/共81页 对请求式分段存储管理系统而言，它考虑了编程时的逻辑结构，把程序分成若干段，以段为单位调入内存运行。这样，在内存分配和回收时，类似于可变式分区操作，容易造成外部碎片问题。而在实现段的调入、调出问题上，又类似于请求式分页存储管理，可能造成系统的抖动现象，所以请求式分段存储管理系统是比较复杂的。返回本节第69页/共81页本章小结本章小结 存储管理的研究对象主要是中央处理器能直接访问的主存储器，其目的一方面是为了在多道程序环境下，提高主存资源的利用率；另一方面也方便用户对主存储器这一关键性资源的使用。第70页/共81页 请求式分页存储管理的性能可从程序设计的质量、页面的

23、大小、分配的内存块数和页面置换算法的性能等几个角度来考虑。 请求式分页存储管理提供了大容量的虚存，更有效地利用了内存，方便了用户。缺点是为了处理缺页中断，增加了处理机开销，而且可能出现抖动问题，降低系统的效率。第71页/共81页 总之，存储管理技术是在不断发展着的，随着现代技术的日新月异，大规模、超大规模集成技术的飞跃发展，也随着人们对计算机应用的不断深入，必会对存储管理提出更多新的问题，存储管理技术也必将在新技术的带动下，得到进一步的发展、完善，为人们更好地、更有效地使用计算机提供帮助。第72页/共81页4.1.1 内存的分配与回收内存的分配与回收 内存分配按分配时机的不同，可分为两种方式。（1）静态存储分配（2）动态存储分配 返回本节第73页/共81页图4.3 静态地址重定位和动态地址重定位示意图（b）采用动态重定位时内存空 间及地址重定位示意图（a）采用静态重定位后的内存空间返回本节第74页/共81页4.2.1 固定分区存储管理固定分区存储管理 固定分区存储管理是实现多道程序设计的最简单的一种存储管理技术。 其基本思想是，在作业未进入内存之前，就由操作员或操作系统把内存可用空间划分成若干个固定大小的存储区，除操作系统占用一个区域外，其余区域为系统中多个