第二节存储管理剖析.

《第二节存储管理剖析.》由会员分享，可在线阅读，更多相关《第二节存储管理剖析.（67页珍藏版）》请在金锄头文库上搜索。

1、第二节 存储器管理,2.1 存储管理的功能 2.2 实存管理 2.3 虚拟存储器管理 2.4 碎片与抖动问题,本节的主要内容如下：,(1)存储管理的有关概念。 (2)实存管理中讲述了固定分区存储管理、可变式分区存储管理、纯分页存储管理三种存储管理方案的实现原理 (3)虚存管理以请求式分页存储管理为重点 (4)总结各种存储管理方案中存在的碎片和抖动问题及解决方法,图2.1 多级存储器体系示意图,2.1 存储管理的功能,2.1.1 内存的分配与回收 2.1.2 地址重定位 2.1.3 存储保护 2.1.4 虚拟存储器,2.1.1 内存的分配与回收,内存分配按分配时机的不同，可分为两种方式。 （1）

2、静态存储分配：指内存分配是在作业运行之前各目标模块连接后，把整个作业一次性全部装入内存，并在作业的整个运行过程中，不允许作业再申请其他内存，或在内存中移动位置。也就是说，内存分配是在作业运行前一次性完成的。 （2）动态存储分配：作业要求的基本内存空间是在目标模块装入内存时分配的，但在作业运行过程中，允许作业申请附加的内存空间，或是在内存中移动，即分配工作可以在作业运行前及运行过程中逐步完成。,2.1.2 地址重定位,1内存空间（或物理空间） 2逻辑空间 3地址重定位,1内存空间（或物理空间）,内存是由若干个存储单元组成的，每个存储单元有一个编号，这种编号可唯一标识一个存储单元，称为内存地址（或

3、物理地址）。,2逻辑空间,源程序经过汇编或编译后，形成目标程序，每个目标程序都是以0为基址顺序进行编址的，原来用符号名访问的单元用具体的数据单元号取代。这样生成的目标程序占据一定的地址空间，称为作业的逻辑地址空间，简称逻辑空间。在逻辑空间中每条指令的地址和指令中要访问的操作数地址统称为逻辑地址。,图2.2 作业的名空间、逻辑地址空间和装入后的物理空间,3地址重定位,(1)静态地址重定位 静态地址重定位是在程序执行之前由操作系统的重定位装入程序完成的。 (2)动态地址重定位 动态地址重定位是在程序执行期间进行的。,（b）采用动态重定位时内存空间及地址重定位示意图,（a）采用静态重定位后的内存空间

4、,图2.3 静态地址重定位和动态地址重定位示意图,2.1.3 存储保护,（1）上、下界存储保护：上、下界保护是一种简单的存储保护技术。系统可为每个作业设置一对上、下界寄存器，分别用来存放当前运行作业在内存空间的上、下边界地址，用它们来限制用户程序的活动范围。 （2）基址限长存储保护：上、下界保护的一个变种是采用基址限长存储保护。,图2.4 界限寄存器的两种存储保护方式,2.1.4 虚拟存储器,对内存进行逻辑上的扩充，现在普遍采用虚拟存储管理技术。 虚拟存储技术的基本思想是把有限的内存空间与大容量的外存统一管理起来，构成一个远大于实际内存的、虚拟的存储器。此时，外存是作为内存的直接延伸，用户并不

5、会感觉到内、外存的区别，即把两级存储器当作一级存储器来看待。一个作业运行时，其全部信息装入虚存，实际上可能只有当前运行的必需一部分信息存入内存，其他则存于外存，当所访问的信息不在内存时，系统自动将其从外存调入内存。,2.2 实存管理,2.2.1 单一连续分配 2.2.2 固定分区存储管理 2.2.3 可变式分区存储管理 2.2.4 可重位分区分配 2.2.5 覆盖技术 2.2.6 交换技术,2.2.1 单一连续分配,操作系统区,用户区,图2.5,2.2.2 固定分区存储管理,固定分区存储管理是实现多道程序设计的最简单的一种存储管理技术。其基本思想是，在作业未进入内存之前，就由操作员或操作系统把

6、内存可用空间划分成若干个固定大小的存储区，除操作系统占用一个区域外，其余区域为系统中多个用户共享，因为在系统运行期间，分区大小、数目都不变，所以固定式分区也称为静态分区。,图2.6 固定式分区内存分配示意图（a）和（b）固定式分区说明表,2.2.3 可变式分区存储管理,1空闲分区的组织形式 2内存的分配与回收 3常用的分配算法 4可变式分区的地址重定位,图2.7 可变式分区内存使用情况示意图,1空闲分区的组织形式,空闲分区链表的组织是这样的：在每个空闲分区的起始部分开辟出一个单元，存放一个链表指针和该分区的大小，链表指针指向下一个空闲分区。系统中用一个固定单元作为空闲分区链表的链表头指针，指向

7、第一块空闲分区首地址，最后一块空闲分区的链表指针存放链尾标志。,2内存的分配与回收,当某一个用户作业完成释放所占分区时，系统应进行回收。在可变式分区中，应该检查回收区与内存中前后空闲区是否相邻，若相邻，则应进行合并，形成一个较大的空闲区，并对相应的链表指针进行修改；若不相邻，应将空闲区插入到空闲区链表的适当位置。,图2.8 首次适应算法的空闲分区链表组织形式,3常用的分配算法,（1）首次适应算法 （2）最佳适应算法 （3）最差适应算法,图2.9 最佳适应算法的空闲分区链表组织形式,图2.10 最差适应算法的空闲分区链表组织形式,图2.11 内存使用情况,图2.12 用三种适应算法处理同一作业序

8、列,2.2.4 可重定位分区分配,可重定位可采用静态重定位，也可采用动态重定位。如采用静态重定位，因用户作业进入内存后，程序的逻辑地址实现了重定位，不能在内存中再进行移动，经过一段时间的运行，内存中不能再分配利用的小碎片会越来越多。有时可能会出现这种情况，即当一个作业申请一定数量的内存时，虽然此时空闲区的总和大于新作业的内存要求，但却没有单个的空闲区足以装下该作业。 采用动态重定位的可变式分区管理技术，在执行内存分配时，如无足够大空闲块，应考虑实现紧凑操作。其分配算法如图2.13所示 。,图2.13 采用动态重定位的分配算法,2.2.5 覆盖技术,当用户作业大于地址空间大于主存可用空间时，该作

9、业就无法运行，这样限制了大程序的运行。但我们知道一个大程序往往有多个模块构成，而且不每时每刻都要在内存中，这样几个模块在不同时间内装入内存时可以用同一块内容，即可以进行覆盖运行。具体情况如图2.14,A (20KB),B (50KB),C (20KB),D (40KB),E (20KB),F (20KB),20KB,50KB,40KB,图 2.14,原来需170K，现在需要110KB,2.2.5 交换技术,交换技术同样是解决内存不足问题。在分时、实时系统及批处理系统中均有应用。 它的基本思想是：只允许一个或几个用户作业保留在内存中。当内存不够时，以整个作业为单位进行内外存交换。 * 缺点是作业

10、较大时花费的代价较大。,2.3 虚拟存储器管理,2.3.1 虚拟存储器的概念 2.3.2 分页存储管理与动态地址重定位 2.3.3 现代计算机系统改进的动态地址重定位 2.3.4 页面置换算法 2.3.5 请求式分页存储管理性能分析举例 2.3.6 请求式分段存储管理,2.3.1 虚拟存储器的概念,（1）程序中往往会有一些彼此互斥的部分。 （2）在一个完整的程序中，会有一些诸如出错处理这样的子程序，在作业正常运行情况下不会执行这些程序，没有必要把它们调入内存。 基于程序局部性原理和上述情况，就没有必要把一个作业一次性全部装入内存再开始运行。而是可以把程序当前执行所涉及的信息放入内存中，其余部分

11、可根据需要临时调入，由操作系统和硬件相配合来完成主存和辅存之间信息的动态调度。这样的计算机系统好像为用户提供了一个存储容量比实际主存大得多的存储器，就称为虚拟存储器。,2.3.2 分页存储管理,1）什么是分页,2）页面、页架号及其大小,3）分页系统中地址的构成,2-4KB,p,d,p：页号,d：页内地址,1、基本概念,）页表和页表地址寄存器,页表地址寄存器,n,页表,页号,页架号,状态,2分页存储管理的地址重定位问题,分页存储管理中的地址重定位是非常重要的，要使不连续的、分散的用户程序能正常运行，须采用动态地址重定位。此时，可采用重定位寄存器方式，如分页太多，则重定位寄存器用得太多。通常可在内

12、存中为每个作业开辟一块特定区域，建立起作业的逻辑页与存储块之间的对应表格关系，这种表常称为页面映象表，简称页表。,图.1 分页存储管理示意图,地址转换过程,从上面介绍的地址变换过程可以看出：如果把页表全部放在内存，那么存取一个数据时，至少要访问二次内存。一次是访问页表，形成实际内存地址；另一次是根据形成的内存地址存取数据。显然，这比通常执行指令的速度要慢得多，使计算机的运行速度几乎降低一半。,图.1 分页存储管理地址重定位实现过程,图.1 采用快表和页表相结合的分页地址变换过程示意图,4存储保护,四种保护方式：禁止做任何操作，只能执行，只能读，能读/写，当要访问某页时，先判断该页的存取控制和存

13、储保护信息是否允许。 添加了存取控制信息的页表表目如下图所示：,状 态,、分页式存储分配方法的特点：,、优点：,）较好地解决了片问题,）作业地址空间不受内存的限制,、缺点：,）硬件支持 ）要进行页表管理,2.3.3 现代计算机系统改进的动态地址重定位,（1）如何合理地组织管理相当大的页表？ 在Windows NT中，为解决第一个问题，对页表本身进行了改进，将庞大的页表本身也采取分页措施，采用了两级页表结构。即把页表本身按固定大小分成一个个小页表，每个小页表由210=1024个页表表目构成，每个表目占4字节，所以每个小页表刚好占一个页面（页面大小为212=4kb）。一共有210=1k个小页表。为

14、了对这1k个小页表进行管理和索引查找，设置了一个页表目录，也称之为顶级页表或一级页表，该页目录包含有1k个表目项，分别指出每个次级小页表所在的物理块号和其他有关状态信息。这样，每个作业有一个页目录（一级页表），它的每个表目指向一个二级页表。页目录本身也刚好是一个页面大小（210=1k，每个表目4个字节）。,图.20 Windows NT两级页表地址变换示意图,（2）面对大的页表，地址的映射怎样才能比较快地实现？,（1）使用快表：即利用前面我们已介绍的高速缓冲存储器来存放经常使用的页表表目，以提高页表的查询速度。 （2）使用高速缓冲存储器：在微处理器和主存之间设置32kb或64kb的高速缓冲存储

15、器，大部分的指令和数据取自高速缓存（命中率为98%），所以存取数据和指令速度相当高，达到与处理器速度完全相匹配。,2.3.4 页面置换算法,1最优算法（OPT算法） 2先进先出算法（FIFO算法） 3最久未使用页面置换算法（LRU算法） 4LRU近似算法,1最优算法（OPT算法）,最理想的页面置换算法是：从内存中移出以后不再使用的页面；如无这样的页面，则选择以后最长时间内不需要访问的页。这就是最优算法的思想。 这种算法本身不是一种实际的方法，因为页面访问的顺序是很难预知的。但是，可把它作为一种评价标准，比较其他实用方法的优劣，所以，最优算法只具有理论上的意义。,2先进先出算法（FIFO算法）,

16、这种算法的基本思想是：总是先淘汰那些驻留在内存时间最长的页面，即先进入内存的页面先被置换掉。理由是：最先进入内存的页面不再被访问的可能性最大。,3最久未使用页面置换算法（LRU算法）,这种算法的基本思想是，如果某一页被访问了，那么它很可能马上又被访问；反之，如果某一页很长时间没有被访问，那么最近也不太可能会被访问。这种算法考虑了程序设计的局部性原理。其实质是，当需要置换一页时，选择在最近一段时间最久未使用的页面予以淘汰。 实现这种算法可通过周期性地对“引用位”进行检查，并利用它来记录一页面自上次被访问以来所经历的时间t，淘汰时选择t最大的页面。,4LRU近似算法,这种算法，只要在存储分块表（或页表）中设一个“引用位”，当存储分块表中的某一页被访问时，该位由硬件自动置1，并由页面管理软件周期性把所有引用位置0。这样，在一个时间周期T内，某些被访问过的页面其引用位为1，而未被访问