memory操作系统原理

《memory操作系统原理》由会员分享，可在线阅读，更多相关《memory操作系统原理（79页珍藏版）》请在装配图网上搜索。

1、第5章 存储管理n 内存是现代计算机系统的中心，是指内存是现代计算机系统的中心，是指CPUCPU能直接存取指令和数能直接存取指令和数据的存储器，据的存储器，CPUCPU和和I/OI/O设备都要和内存打交道。设备都要和内存打交道。n 内存由很大的一组字或字节所组成，每个字或字节都有它们自内存由很大的一组字或字节所组成，每个字或字节都有它们自己的编号，称为内存地址。己的编号，称为内存地址。n 对内存的访问是通过一系列对指定地址单元进行读写来实现的。对内存的访问是通过一系列对指定地址单元进行读写来实现的。5.1.1 5.1.1 存储空间的分配和回收存储空间的分配和回收 内存的分配与回收是内存管理的主

2、要功能之一。用户程内存的分配与回收是内存管理的主要功能之一。用户程序通常以文件的形式保存在计算机外存上，为了执行用户程序通常以文件的形式保存在计算机外存上，为了执行用户程序，用户程序必须全部或部分装入内存，因此在内外存之间序，用户程序必须全部或部分装入内存，因此在内外存之间必须不断交换数据。能否把外存中的数据和程序调入内存，必须不断交换数据。能否把外存中的数据和程序调入内存，取决于能否在内存中为它们安排合适的位置。因此，存储管取决于能否在内存中为它们安排合适的位置。因此，存储管理模块要为每一个并发执行的进程分配内存空间。另外，当理模块要为每一个并发执行的进程分配内存空间。另外，当进程执行结束之

3、后，存储管理模块又要及时回收该进程所占进程执行结束之后，存储管理模块又要及时回收该进程所占用的内存资源，以便给其他进程分配空间。用的内存资源，以便给其他进程分配空间。5.1.2 5.1.2 地址转换（映射）地址转换（映射）n 内存的每个存储单元都有一个编号，这种编号称为内存地内存的每个存储单元都有一个编号，这种编号称为内存地址（或称为物理地址，绝对地址）。内存地址的集合称为址（或称为物理地址，绝对地址）。内存地址的集合称为内存空间（或物理地址空间）内存空间（或物理地址空间）。n 源程序经过汇编或编译后，形成目标程序，每个目标程序源程序经过汇编或编译后，形成目标程序，每个目标程序都是以都是以0

4、0为基址顺序进行编址的，原来用符号名访问的单元为基址顺序进行编址的，原来用符号名访问的单元用具体的数据用具体的数据单元号取代。这样生成的目标程序占据单元号取代。这样生成的目标程序占据一定的地址空间，称为作业的逻辑地址空间，简称逻辑空一定的地址空间，称为作业的逻辑地址空间，简称逻辑空间。在逻辑空间中每条指令的地址和指令中要访问的操作间。在逻辑空间中每条指令的地址和指令中要访问的操作数地址统称为逻辑地址。数地址统称为逻辑地址。地址映射地址映射Load A 200 3456 。1200物理地址空间物理地址空间Load A data1data1 3456源程序源程序Load A 200 3456010

5、0200编译编译连接连接逻辑地址空间逻辑地址空间BA=1000n 我们把用户程序装入内存时对有关指令的地址部分的修改我们把用户程序装入内存时对有关指令的地址部分的修改定义为从程序地址到内存地址的地址映射，或称为地址重定义为从程序地址到内存地址的地址映射，或称为地址重定位。定位。n 地址映射的方式：地址映射的方式：1 1、静态地址重定位、静态地址重定位u程序被装入内存时由操作系统的连接装入程序完成程序的程序被装入内存时由操作系统的连接装入程序完成程序的逻辑地址到内存地址的转换。逻辑地址到内存地址的转换。u假定程序装入内存的首地址为假定程序装入内存的首地址为BRBR，程序地址为程序地址为VRVR，

6、内存地内存地址为址为MRMR，则地址映射按下式进行：则地址映射按下式进行：MR=BR+VR MR=BR+VR。2 2、动态重定位、动态重定位u动态地址重定位是在程序执行的过程中，每次访问内存之前，动态地址重定位是在程序执行的过程中，每次访问内存之前，将要访问的程序地址转换为内存地址。将要访问的程序地址转换为内存地址。u动态重定位依靠硬件地址变换机构完成。地址重定位机构需动态重定位依靠硬件地址变换机构完成。地址重定位机构需要一个要一个(或多个或多个)基地址寄存器基地址寄存器BRBR和一个和一个(或多个或多个)程序虚拟地程序虚拟地址寄存器址寄存器VRVR。指令或数据的内存地址。指令或数据的内存地址

7、MAMA与逻辑地址的关系为：与逻辑地址的关系为：MA=(BR)+(VR)MA=(BR)+(VR)这里，这里，(BR)(BR)与与(VR)(VR)分别表示寄存器分别表示寄存器BRBR与与VRVR中的内容。中的内容。5.1.3 5.1.3 主存空间的共享和保护主存空间的共享和保护 在多道程序设计环境下，内存中的许多用户或系统在多道程序设计环境下，内存中的许多用户或系统程序和数据段可供不同的用户进程共享。这种资源程序和数据段可供不同的用户进程共享。这种资源共享将会提高内存的利用率。但是，反过来说，除共享将会提高内存的利用率。但是，反过来说，除了被允许共享的部分之外，又要限制各进程只在自了被允许共享的

8、部分之外，又要限制各进程只在自己的存储区活动，各进程不能对别的进程的程序和己的存储区活动，各进程不能对别的进程的程序和数据段产生干扰和破坏，因此须对内存中的程序和数据段产生干扰和破坏，因此须对内存中的程序和数据段采取保护措施。数据段采取保护措施。n 内存保护的方式：内存保护的方式：（1 1）上、下界存储保护：上、下界保护是一种简单）上、下界存储保护：上、下界保护是一种简单的存储保护技术。系统可为每个作业设置一对上、的存储保护技术。系统可为每个作业设置一对上、下界寄存器，分别用来存放当前运行作业在内存空下界寄存器，分别用来存放当前运行作业在内存空间的上、下边界地址，用它们来限制用户程序的活间的上

9、、下边界地址，用它们来限制用户程序的活动范围。动范围。（2 2）基址）基址限长存储保护：上、下界保护的一个变限长存储保护：上、下界保护的一个变种是采用基址种是采用基址限长存储保护。限长存储保护。5.1.4 5.1.4 主存空间的扩充主存空间的扩充u对内存进行逻辑上的扩充，现在普遍采用虚拟存储管理技术。对内存进行逻辑上的扩充，现在普遍采用虚拟存储管理技术。u虚拟存储技术的基本思想是把有限的内存空间与大容量的外虚拟存储技术的基本思想是把有限的内存空间与大容量的外存统一管理起来，构成一个远大于实际内存的、虚拟的存储存统一管理起来，构成一个远大于实际内存的、虚拟的存储器。此时，外存是作为内存的直接延伸

10、，用户并不会感觉到器。此时，外存是作为内存的直接延伸，用户并不会感觉到内、外存的区别，即把两级存储器当作一级存储器来看待。内、外存的区别，即把两级存储器当作一级存储器来看待。一个作业运行时，其全部信息装入虚存，实际上可能只有当一个作业运行时，其全部信息装入虚存，实际上可能只有当前运行的必需一部分信息存入内存，其他则存于外存，当所前运行的必需一部分信息存入内存，其他则存于外存，当所访问的信息不在内存时，系统自动将其从外存调入内存。访问的信息不在内存时，系统自动将其从外存调入内存。5.2.1 5.2.1 分区管理的基本原理分区管理的基本原理n 分区管理的基本原理是给每一个内存中的进程划分一块适当分

11、区管理的基本原理是给每一个内存中的进程划分一块适当大小的存储区大小的存储区,以连续存储各进程的程序和数据，使各进程得以连续存储各进程的程序和数据，使各进程得以并发执行。以并发执行。n 按分区的时机，分区管理可以分为固定分区和动态分区两种按分区的时机，分区管理可以分为固定分区和动态分区两种方法。方法。1 1、固定分区法：、固定分区法：n把内存区固定地划分为若干个大小不等的区域。划分的原则把内存区固定地划分为若干个大小不等的区域。划分的原则由系统操作员或操作系统决定。分区一旦划分结束，在整个由系统操作员或操作系统决定。分区一旦划分结束，在整个执行过程中每个分区的长度和内存的总分区个数将保持不变。执

12、行过程中每个分区的长度和内存的总分区个数将保持不变。n 某系统的内存容量为某系统的内存容量为256256K K，操作系统占用低地址的操作系统占用低地址的2020K K，其其余空间划分成余空间划分成4 4个固定大小的分区。如下图：个固定大小的分区。如下图：2 2、动态分区法、动态分区法n动态分区法在作业执行前并不建立分区，分区的建动态分区法在作业执行前并不建立分区，分区的建立是在作业的处理过程中进行的，且其大小可随作立是在作业的处理过程中进行的，且其大小可随作业或进程对内存的要求而改变。业或进程对内存的要求而改变。这就改变了固定分这就改变了固定分区法中那种即使是小作业也要占据大分区的浪费现区法中

13、那种即使是小作业也要占据大分区的浪费现象，从而提高了内存的利用率。象，从而提高了内存的利用率。n采用动态分区法，在系统初启时，除了操作系统中采用动态分区法，在系统初启时，除了操作系统中常驻内存部分之外，只有一个空闲分区。随后，分常驻内存部分之外，只有一个空闲分区。随后，分配程序将该区依次划分给调度选中的作业或进程。配程序将该区依次划分给调度选中的作业或进程。5.2 5.2 连续内存分配连续内存分配n在动态分区存储管理中，要有相应的数据结构来登记空闲区在动态分区存储管理中，要有相应的数据结构来登记空闲区的说明信息，它包括空闲区的大小和位置。的说明信息，它包括空闲区的大小和位置。n不同系统根据设计

14、要求采用不同的结构。常用的有表结构和不同系统根据设计要求采用不同的结构。常用的有表结构和队列结构。队列结构。n空闲区表的每个表目记录一个空闲区，主要参数包括区号、空闲区表的每个表目记录一个空闲区，主要参数包括区号、长度和起始地址。空闲区队列则是利用每个内存空闲区的头长度和起始地址。空闲区队列则是利用每个内存空闲区的头几个单元存放本空闲区的大小及下个空闲区的起始地址，从几个单元存放本空闲区的大小及下个空闲区的起始地址，从而把所有的空闲区链接起来。而把所有的空闲区链接起来。5.2.2 5.2.2 分区的分配和回收分区的分配和回收1.1.固定分区的分配和回收固定分区的分配和回收 当用户程序要装入执行

15、当用户程序要装入执行时，存储管理程序根据时，存储管理程序根据用户程序的大小查询分用户程序的大小查询分区说明表，从中找出一区说明表，从中找出一个满足要求的空闲分区，个满足要求的空闲分区，并将其分配给申请者。并将其分配给申请者。2 2、动态分区的分配和回收、动态分区的分配和回收（1 1）分区的分配）分区的分配u当用户要求一个大小为当用户要求一个大小为SIZE的存储空间时，系统查询空闲区的存储空间时，系统查询空闲区表或空闲分区队列，找一个大于或等于表或空闲分区队列，找一个大于或等于SIZE的空闲区。的空闲区。u分配时会出现以下三种情况：一是系统中无满足要求的空闲分配时会出现以下三种情况：一是系统中无

16、满足要求的空闲区，则分配失败。二是空闲区大小与区，则分配失败。二是空闲区大小与SIZESIZE相等，则修改空闲相等，则修改空闲区表相应表目，向用户返回该空闲区首址。三是空闲区大于区表相应表目，向用户返回该空闲区首址。三是空闲区大于SIZESIZE，这时将空闲区一分为二。这时将空闲区一分为二。u将一个空闲区分成二部分有两种办法：一是从空闲区的上部将一个空闲区分成二部分有两种办法：一是从空闲区的上部开始划出开始划出SIZESIZE大小的空闲区给用户；二是从空闲区的底部开大小的空闲区给用户；二是从空闲区的底部开始向上划出始向上划出SIZESIZE大小的空闲区给用户。大小的空闲区给用户。u分配算法：分

17、配算法：（1 1）首次适应算法：）首次适应算法：要求空闲区按首址递增的次序组织空闲区表（队列）。要求空闲区按首址递增的次序组织空闲区表（队列）。（2 2）最佳适应算法：）最佳适应算法：要求按空闲区大小从小到大的次序组成空闲区表（队列）。要求按空闲区大小从小到大的次序组成空闲区表（队列）。（3 3）最坏适应算法）最坏适应算法 要求空闲区按大小递减的顺序组织空闲区表（或队列）。要求空闲区按大小递减的顺序组织空闲区表（或队列）。例例5-15-1：有作业序列：作业：有作业序列：作业A A要求要求1818K K；作业作业B B要求要求2525K K，作业作业C C要要求求3030K K。系统中空闲区按三

18、种算法组成的空闲区队列系统中空闲区按三种算法组成的空闲区队列.（2 2）动态分区的内存回收）动态分区的内存回收 当某一个用户作业完成释放所占分区时，系当某一个用户作业完成释放所占分区时，系统应进行回收。在可变式分区中，应该检查回收统应进行回收。在可变式分区中，应该检查回收区与内存中前后空闲区是否相邻，若相邻，则应区与内存中前后空闲区是否相邻，若相邻，则应进行合并，形成一个较大的空闲区，并对相应的进行合并，形成一个较大的空闲区，并对相应的链表指针进行修改；若不相邻，应将空闲区插入链表指针进行修改；若不相邻，应将空闲区插入到空闲区链表的适当位置。到空闲区链表的适当位置。5.2.3 5.2.3 碎片

19、问题碎片问题u在连续内存分配中，必须把一个系统程序或用户程序装入一在连续内存分配中，必须把一个系统程序或用户程序装入一个连续的内存空间中。由于各个进程不但的申请和释放内存，个连续的内存空间中。由于各个进程不但的申请和释放内存，导致在内存中出现大量的分散的小空闲区。内存中这种容量导致在内存中出现大量的分散的小空闲区。内存中这种容量太小、无法利用的小分区称做太小、无法利用的小分区称做“碎片碎片”或或“零头零头”。u根据碎片出现的位置，可以分为内部碎片和外部碎片两种。根据碎片出现的位置，可以分为内部碎片和外部碎片两种。在一个分区内部出现的碎片（即被浪费的空间）称做内部碎在一个分区内部出现的碎片（即被

20、浪费的空间）称做内部碎片。在所有分区之外新增的碎片称做外部碎片。片。在所有分区之外新增的碎片称做外部碎片。u解决碎片问题最简单的方法是定时或在分配内存时把所有碎解决碎片问题最简单的方法是定时或在分配内存时把所有碎片合并为一个连续区。实现的方法是移动某些已分配区的内片合并为一个连续区。实现的方法是移动某些已分配区的内容，使所有进程的分区紧挨在一起，而把空闲区留在另一端，容，使所有进程的分区紧挨在一起，而把空闲区留在另一端，这种技术称为紧缩（或拼凑）。这种技术称为紧缩（或拼凑）。例题例题5-2:5-2:某操作系统采用可变分区分配存储管理方法某操作系统采用可变分区分配存储管理方法,用户区用户区大小为

21、大小为512K512K且初始值为且初始值为0,0,用空闲分区表管理空闲分区。若分用空闲分区表管理空闲分区。若分配时采用分配空闲区低地址部分的方案，且初始时用户区的配时采用分配空闲区低地址部分的方案，且初始时用户区的512K512K空间空闲，对于下列申请序列：空间空闲，对于下列申请序列：申请申请300K300K，申请，申请100K100K，释放，释放300K300K，申请，申请150K150K，申请，申请30K30K，申请申请40K40K，申请，申请60K60K，释放，释放30K30K 回答下列问题：回答下列问题：（1 1）请分别画出采用首次适应算法、最佳适应算法进行内）请分别画出采用首次适应算

22、法、最佳适应算法进行内存分配和回收后的内存使用状态。存分配和回收后的内存使用状态。（2 2）如果再申请）如果再申请100K100K，针对上述两种算法会有什么结果？，针对上述两种算法会有什么结果？例题例题5-25-2解答如下：解答如下：150K150K作业作业40K40K作业作业60K60K作业作业100K100K作业作业0 0150K150K180K180K220K220K280K280K300K300K400K400K512K-1512K-1首次适应算法首次适应算法150K150K作业作业60K60K作业作业100K100K作业作业40K40K作业作业0 0150K150K210K210K3

23、00K300K400K400K430K430K470K470K512K-1512K-1最佳适应算法最佳适应算法5.3.1 5.3.1 覆盖覆盖 覆盖技术是基于这样一种思想提出来的：一个程序并不覆盖技术是基于这样一种思想提出来的：一个程序并不需要一开始就把它的全部指令和数据都装入内存后再执行。需要一开始就把它的全部指令和数据都装入内存后再执行。在单在单CPUCPU系统中，每一时刻事实上只能执行一条指令。因此，系统中，每一时刻事实上只能执行一条指令。因此，不妨把程序划分为若干个功能上相对独立的程序段，按照程不妨把程序划分为若干个功能上相对独立的程序段，按照程序的逻辑结构让那些不会同时执行的程序段共

24、享同一块内存序的逻辑结构让那些不会同时执行的程序段共享同一块内存区。通常，这些程序段都被保存在外存中，当有关程序段的区。通常，这些程序段都被保存在外存中，当有关程序段的先头程序段已经执行结束后，再把后续程序段调入内存覆盖先头程序段已经执行结束后，再把后续程序段调入内存覆盖前面的程序段。这使得用户看来，好像内存扩大了，从而达前面的程序段。这使得用户看来，好像内存扩大了，从而达到了内存扩充的目的。到了内存扩充的目的。例如，设某进程的程序正文段由例如，设某进程的程序正文段由A，B，C，D，E和和F等等6个个程序段组成。它们之间的调用关系如下图所示，程序段程序段组成。它们之间的调用关系如下图所示，程序

25、段A调调用程序段用程序段B和和C，程序段，程序段B又调用程序段又调用程序段F,程序段程序段C调用程序调用程序段段D和和E。5.3.2 5.3.2 交换技术交换技术 交换是指先将内存某部分的程序或数据写入外存交换区，再交换是指先将内存某部分的程序或数据写入外存交换区，再从外存交换区中调入指定的程序或数据到内存中来，并让其从外存交换区中调入指定的程序或数据到内存中来，并让其执行的一种内存扩充技术执行的一种内存扩充技术 。5.4.1 5.4.1 分页管理的基本原理分页管理的基本原理n 把用户程序的地址空间划分成若干大小相等的区域，每个区把用户程序的地址空间划分成若干大小相等的区域，每个区域称作页面或

26、页。每个页都有一个编号，叫做页号。页号一域称作页面或页。每个页都有一个编号，叫做页号。页号一般从般从0开始编号，如开始编号，如0，1，2，等。等。n 把内存空间划分成若干和页大小相同的物理块，这些物理块把内存空间划分成若干和页大小相同的物理块，这些物理块叫叫“帧帧”(frame)或内存块。同样，每个物理块也有一个编或内存块。同样，每个物理块也有一个编号，块号从号，块号从0开始依次顺序排列。开始依次顺序排列。n 以页为单位进行内存分配，并按作业的页数多少来分配。逻以页为单位进行内存分配，并按作业的页数多少来分配。逻辑上相邻的页，物理上不一定相邻。辑上相邻的页，物理上不一定相邻。n 在分页系统中，

27、页面的大小是由硬件的地址结构所决定的。在分页系统中，页面的大小是由硬件的地址结构所决定的。机器确定、页面大小便确定了。一般来说，页面的大小选择机器确定、页面大小便确定了。一般来说，页面的大小选择为为2的若干次幂，根据计算机结构的不同，其大小从的若干次幂，根据计算机结构的不同，其大小从512B到到16MB不等。不等。n 在分页系统中，由在分页系统中，由CPU生成的每个地址被硬件分成两个部生成的每个地址被硬件分成两个部分：页号（分：页号（p）和页内偏移（）和页内偏移（w）。通常，如果逻辑地址空间）。通常，如果逻辑地址空间为为2m，且页的大小为，且页的大小为2n单元（字节或词），那么逻辑地址的单元（

28、字节或词），那么逻辑地址的高高mn位表示页号，而低位表示页号，而低n位表示页偏移。这样，一个地址位表示页偏移。这样，一个地址长度为长度为20位的计算机系统，如果每页的大小为位的计算机系统，如果每页的大小为1KB(210)，那那么可以有么可以有210个页。个页。0111231页号页号P页内位移量页内位移量W编号编号01048575相对地址相对地址04095 对于某台具体机器来说，其地址结构是一定的。如果给定的对于某台具体机器来说，其地址结构是一定的。如果给定的逻辑地址是逻辑地址是A A，页面的大小为，页面的大小为L L，则页号，则页号p p和页内地址和页内地址w w可按下可按下式求得：式求得：p

29、=INTA/L，w=A MOD L 其中，其中，INTINT是向下整除的函数，是向下整除的函数，MODMOD是取余函数。例如，设系是取余函数。例如，设系统的页面大小为统的页面大小为1KB,A=3456,1KB,A=3456,则则p=INT(3456/1024)=3p=INT(3456/1024)=3，w=w=3456 MOD 1024=3843456 MOD 1024=384。n在分页系统中，允许将进程的各页离散地装入内存的任何空在分页系统中，允许将进程的各页离散地装入内存的任何空闲块中，这样就出现进程页号连续，而块号不连续的情况。闲块中，这样就出现进程页号连续，而块号不连续的情况。为了找到每

30、个页面在内存中对应的物理块，系统为每个进程为了找到每个页面在内存中对应的物理块，系统为每个进程设立一张页面映射表，简称设立一张页面映射表，简称页表。页表。n进程的所有页依次在页表中有一个页表项，其中记载了相应进程的所有页依次在页表中有一个页表项，其中记载了相应页面在内存中对应的物理块号。进程执行时，按照逻辑地址页面在内存中对应的物理块号。进程执行时，按照逻辑地址中的页号查找页表中对应的项，找到该页在内存中物理块号。中的页号查找页表中对应的项，找到该页在内存中物理块号。n页表的作用就是实现页号到物理块号的地址映射。页表的作用就是实现页号到物理块号的地址映射。5.4.2 5.4.2 地址映射地址映

31、射设页长为设页长为1 1K K，程序地址字长为程序地址字长为1616位，用户程序空间和页表如图。位，用户程序空间和页表如图。例题与习题：例题与习题：例例5-15-1：设有：设有8 8页的逻辑地址空间，每页有页的逻辑地址空间，每页有10241024个字节，它们被个字节，它们被映射到映射到3232块的的物理存储区，那么逻辑地址的有效为是多少，块的的物理存储区，那么逻辑地址的有效为是多少，物理地址至少多少位？物理地址至少多少位？例例5-25-2：在一分页系统中，逻辑地址的长度为：在一分页系统中，逻辑地址的长度为1616位，页面大小位，页面大小为为40964096字节，现有一逻辑地址字节，现有一逻辑地

32、址2F6AH2F6AH，且第，且第0 0、1 1、2 2页依次存页依次存放在物理块放在物理块5 5、1010、1111中，问相应的物理地址是多少？中，问相应的物理地址是多少？例例5-35-3：在某分页系统，主存的容量为：在某分页系统，主存的容量为64K64K，页面的大小为，页面的大小为1K1K，对于一个对于一个4 4页大的作业，其页大的作业，其0 0、1 1、2 2、3 3页分别被分配到主存页分别被分配到主存的的2 2、4 4、6 6、7 7块中，试将十进制的逻辑地址块中，试将十进制的逻辑地址10231023、25002500、35003500和和45004500转化成物理地址。转化成物理地址

33、。n快表和联想寄存器快表和联想寄存器 由于页表是驻留在内存的某个固定区域中，而取数据或指令由于页表是驻留在内存的某个固定区域中，而取数据或指令又必须经过页表变换才能得到实际物理地址。因此，取一个又必须经过页表变换才能得到实际物理地址。因此，取一个数据或指令至少要访问内存两次以上。一次访问页表以确定数据或指令至少要访问内存两次以上。一次访问页表以确定所取数据或指令的物理地址，另一次是根据地址取数据或指所取数据或指令的物理地址，另一次是根据地址取数据或指令，这比通常执行指令的速度慢了一倍。令，这比通常执行指令的速度慢了一倍。解决这个问题的一种方法是把页表放在一组快速存储器中解决这个问题的一种方法是

34、把页表放在一组快速存储器中（CacheCache），），从而加快访问内存的速度。我们把这种快速存从而加快访问内存的速度。我们把这种快速存储器组成的页表称为储器组成的页表称为快表快表，把存放在内存中的页表称为慢表。，把存放在内存中的页表称为慢表。快表又叫相联快表又叫相联(联想联想)存储器（存储器（associative memoryassociative memory）。n关于联想寄存器的讨论关于联想寄存器的讨论:一个程序可能会很大，如一个程序可能会很大，如1 1M M，若页长为若页长为1 1K K，则该程序则该程序有有10001000个页，则该程序的页表就需要个页，则该程序的页表就需要1000

35、1000个表项，当程序个表项，当程序更大时，页表会更大，那么我们应该有一个多大的快速存更大时，页表会更大，那么我们应该有一个多大的快速存储器才能满足要求呢？这会遇到两个问题：储器才能满足要求呢？这会遇到两个问题：可能快速存储器多大都是不够的，因为程序可能会更大。可能快速存储器多大都是不够的，因为程序可能会更大。快速存储器是非常非常昂贵的。快速存储器是非常非常昂贵的。实际上我们并不需要一个很大的快速存储器，有一个能存实际上我们并不需要一个很大的快速存储器，有一个能存放放1616个页表表目的快速存储器就够了个页表表目的快速存储器就够了。例题例题:假定访问主存时间为假定访问主存时间为100100毫微

36、秒，访问相联存储器时间为毫微秒，访问相联存储器时间为2020毫微秒，相联存储器为毫微秒，相联存储器为3232个单元时快表命中率可达个单元时快表命中率可达90%90%，按逻辑地址存取的平均时间为：，按逻辑地址存取的平均时间为：（1001002020）90%90%(100+100+20)(100+100+20)(1-90%)(1-90%)130130毫微秒毫微秒 比两次访问主存的时间比两次访问主存的时间100100毫微秒毫微秒2 2200200毫微秒下毫微秒下降了四成多。降了四成多。p页表页表地址越界地址越界 l比较比较P=1pp.快表快表 b+页号页号p p 页内地址页内地址dPd物理地址物理地

37、址页表地址寄存器页表地址寄存器页表长度寄存器页表长度寄存器逻辑地址逻辑地址5.4.3 5.4.3 页表的结构页表的结构nCPUCPU具有具有3232位地址时位地址时 ,使用使用2 23232逻辑地址空间的分页系统逻辑地址空间的分页系统,规定规定页面页面4KB4KB时时,每个进程页表的表项有每个进程页表的表项有1 1兆兆(2(22020)个个,若表项占用若表项占用4 4个字节个字节,则每个进程需要占用则每个进程需要占用4KB4KB连续内存空间存放页表。连续内存空间存放页表。n多级页表概念：页表和页面一样也进行分页，内存仅存放当多级页表概念：页表和页面一样也进行分页，内存仅存放当前使用的页表前使用

38、的页表,暂时不用部分放在磁盘上暂时不用部分放在磁盘上,待用到时再行调进。待用到时再行调进。n具体做法：把整个页表进行分页具体做法：把整个页表进行分页,分成一张张小页表分成一张张小页表(称为页称为页表页表页),),小页表的大小与页框相同，为进行索引查找小页表的大小与页框相同，为进行索引查找,应该为应该为这些小页表建一张页目录表这些小页表建一张页目录表,其表项指出小页表所在页框号及其表项指出小页表所在页框号及相关信息。相关信息。n系统为每个进程建一张页目录表系统为每个进程建一张页目录表,它的每个表项对应一个页它的每个表项对应一个页表页表页,而页表页的每个表项给出了页面和页框的对应关系而页表页的每个

39、表项给出了页面和页框的对应关系,页页目录表是一级页表目录表是一级页表,页表页是二级页表。页表页是二级页表。n逻辑地址结构有三部分组成：页目录、页表页和位移。逻辑地址结构有三部分组成：页目录、页表页和位移。n在具有两级页表结构的系统中，地址转换的方法是：利用外在具有两级页表结构的系统中，地址转换的方法是：利用外层页号层页号p1p1检索外层页表，从中找到相应内层页表的基址，在检索外层页表，从中找到相应内层页表的基址，在利用利用p2p2作为该内层页表的索引，找到该页面在内存的块号，作为该内层页表的索引，找到该页面在内存的块号，用该块号和页内地址用该块号和页内地址d d拼接起来形成访问物块内存的物理地

40、拼接起来形成访问物块内存的物理地址。址。5.4.4 5.4.4 页面的共享页面的共享n设想一下这样的系统，有设想一下这样的系统，有40个用户，每个用户都执行一个文个用户，每个用户都执行一个文本编辑器。如果文本编辑器有本编辑器。如果文本编辑器有150KB代码段和代码段和50KB数据段，数据段，需要需要8000KB来支持来支持40个用户。个用户。n如果代码是可重入代码，那么就可以共享。可重入代码（或如果代码是可重入代码，那么就可以共享。可重入代码（或纯代码）是在其执行过程中本身不做任何修改的代码，通常纯代码）是在其执行过程中本身不做任何修改的代码，通常由指令和常数组成。由指令和常数组成。n共享页面

41、时只需要在物理内存中保存一个编辑器的拷贝。每共享页面时只需要在物理内存中保存一个编辑器的拷贝。每个用户的页表映射到编辑器的同一物理拷贝，而数据页映射个用户的页表映射到编辑器的同一物理拷贝，而数据页映射到不同的帧。到不同的帧。5.5.1 5.5.1 分段存储管理的基本原理分段存储管理的基本原理n用户程序划分：按程序自身的逻辑关系划分为若干个程序段，用户程序划分：按程序自身的逻辑关系划分为若干个程序段，每个程序段都有一个段名，且有一个段号。段号从每个程序段都有一个段名，且有一个段号。段号从0 0开始，每开始，每一段段内也从一段段内也从0 0开始编址，段内地址是连续的。开始编址，段内地址是连续的。n

42、逻辑地址：逻辑地址：段号 段内地址n内存划分：内存空间被动态的划分为若干个长度不相同的内存划分：内存空间被动态的划分为若干个长度不相同的区域，称为物理段，每个物理段由起始地址和长度确定。区域，称为物理段，每个物理段由起始地址和长度确定。n内存分配：以段为单位分配内存，每一个段在内存中占据内存分配：以段为单位分配内存，每一个段在内存中占据连续空间（内存随机分割，需要多少分配多少），但各段连续空间（内存随机分割，需要多少分配多少），但各段之间可以不连续存放。之间可以不连续存放。.0S工作区段工作区段B主程序段主程序段M.0EP子程序段子程序段X0K.CALL X E.CALL Y FCALL A

43、116.0FL子程序段子程序段Y0116N数组数组A12345.5.5.2 5.5.2 分段存储管理的地址映射分段存储管理的地址映射n 分段存储存储管理的地址转换过程：分段存储存储管理的地址转换过程：u 一个逻辑地址由两部分组成：段号一个逻辑地址由两部分组成：段号s和段内地址和段内地址d。系统。系统根据段表地址寄存器的内容（表示段表的起始地址）找根据段表地址寄存器的内容（表示段表的起始地址）找到进程的段表，以段号为索引查找相应的表项，得出该到进程的段表，以段号为索引查找相应的表项，得出该段的长度段的长度limit及该段在内存的起始地址及该段在内存的起始地址base。u将段内地址将段内地址d与段

44、长与段长limit进行比较。如果进行比较。如果d不小于不小于limit，这表示地址越界，系统发出地址越界中断，终止程序的这表示地址越界，系统发出地址越界中断，终止程序的执行；如果执行；如果d小于小于limit，则表示地址合法，将段内地址，则表示地址合法，将段内地址d与该段的内存始址与该段的内存始址base相加，得到所要访问单元的内存相加，得到所要访问单元的内存地址。地址。n 例题：在一分段存储系统中，其段表如下：例题：在一分段存储系统中，其段表如下：段号段号内存起始地址内存起始地址段长段长01234210235010013501938500209059095试求下列逻辑地址对应的物理地址是什么

45、？试求下列逻辑地址对应的物理地址是什么？（1 1）00：430430；（；（2 2）11：1010；（；（3 3）22：500500；（4 4）33：400400；（；（5 5）44：112112；（；（6 6）55：32325.5.3 5.5.3 段的共享和保护段的共享和保护分段和分页的比较：分段和分页的比较：（1）页是信息的物理单位，而段是信息的逻辑单位。分页时为）页是信息的物理单位，而段是信息的逻辑单位。分页时为了实现离散分配方式，以减少内存碎片，提高内存利用率。了实现离散分配方式，以减少内存碎片，提高内存利用率。或者说，分页仅仅是由于系统管理的需要，而不是用户的需或者说，分页仅仅是由于

46、系统管理的需要，而不是用户的需要。段则是信息的逻辑单位，它含有一组其意义相对完整的要。段则是信息的逻辑单位，它含有一组其意义相对完整的信息。分段的目的是为了能更好地满足用户的需要。信息。分段的目的是为了能更好地满足用户的需要。（2）页的大小是由系统确定的，由系统把逻辑地址划分成页号）页的大小是由系统确定的，由系统把逻辑地址划分成页号和页内地址两部分，整个系统只能有一种大小的页面；而段和页内地址两部分，整个系统只能有一种大小的页面；而段的长度却不固定，决定于用户的程序。通常由编译程序在对的长度却不固定，决定于用户的程序。通常由编译程序在对源码进行编译时，根据信息的性质来划分。源码进行编译时，根据

47、信息的性质来划分。（3）分页的进程地址空间是一维的，即单一的线性空间；而分）分页的进程地址空间是一维的，即单一的线性空间；而分段的进程地址空间是二维的，有段号和段内地址两部分组成。段的进程地址空间是二维的，有段号和段内地址两部分组成。5.5.4 5.5.4 段页式存储管理段页式存储管理1.1.基本思想基本思想:（1）作业地址空间进行段式管理。）作业地址空间进行段式管理。（2）每段内再分成若干大小固定的页，每段都从零开始为自）每段内再分成若干大小固定的页，每段都从零开始为自己的各页依次编写连续的页号。己的各页依次编写连续的页号。（3）对内存空间的管理仍然和分页存储管理一样，将其分成）对内存空间的

48、管理仍然和分页存储管理一样，将其分成若干个和页面大小相同的物理块。若干个和页面大小相同的物理块。（4）作业的逻辑地址包括）作业的逻辑地址包括3个部分：段号、页号和页内位移。个部分：段号、页号和页内位移。（5）为实现地址变换，段页式系统设立了段表和页表。）为实现地址变换，段页式系统设立了段表和页表。2.2.地址转换过程地址转换过程:前面所介绍的各种存储管理方式，有一个共同的特点，前面所介绍的各种存储管理方式，有一个共同的特点，即它们都要求将一个作业全部装入内存后才能运行，于是，即它们都要求将一个作业全部装入内存后才能运行，于是，就可能出现以下情况：就可能出现以下情况：(1)有的作业很大，其所要求

49、内存空间超过了内存容量，有的作业很大，其所要求内存空间超过了内存容量，从而导致作业不能全部被装入内存，以至于该作业无法运从而导致作业不能全部被装入内存，以至于该作业无法运行。行。(2)有多个作业要求运行，但可用的内存空间不足以容有多个作业要求运行，但可用的内存空间不足以容纳所有的作业，只能将少数的作业装入内存让它们先运行，纳所有的作业，只能将少数的作业装入内存让它们先运行，而将其他的作业留在外存等待。而将其他的作业留在外存等待。5.6.1 5.6.1 虚拟存储器的概念虚拟存储器的概念 虚拟内存（虚拟内存（Virtual Memory）是指在具有层次结）是指在具有层次结构存储器的计算机系统中，采

50、用自动实现部分装构存储器的计算机系统中，采用自动实现部分装入和部分对换功能，为用户提供一个比物理主存入和部分对换功能，为用户提供一个比物理主存容量大得多的可寻址的一种容量大得多的可寻址的一种“主存储器主存储器”。它使。它使用户逻辑存储器与物理存储器分离，是操作系统用户逻辑存储器与物理存储器分离，是操作系统给用户提供的一个比真实内存空间大得多的地址给用户提供的一个比真实内存空间大得多的地址空间空间。n实现虚拟存储器的物质基础是二级存储器结构和动态地址实现虚拟存储器的物质基础是二级存储器结构和动态地址转换机构。经过操作系统的改造，把计算机的内存与外存转换机构。经过操作系统的改造，把计算机的内存与外

51、存有机的结合起来使用，从而得到一个容量很大的有机的结合起来使用，从而得到一个容量很大的“内存内存”，这就是虚存。这就是虚存。n虚拟存储器实质上是把用户地址空间和实际的存储空间区虚拟存储器实质上是把用户地址空间和实际的存储空间区分开来，当作两个不同的概念。它的容量主要受到两方面分开来，当作两个不同的概念。它的容量主要受到两方面的限制：（的限制：（1 1）指令中表示地址的字长。一个虚拟存储器）指令中表示地址的字长。一个虚拟存储器的最大容量是由计算机的地址结构确定的。如：若的最大容量是由计算机的地址结构确定的。如：若CPUCPU的的有效地址长度为有效地址长度为3232位，则程序可以寻址范围是位，则程

52、序可以寻址范围是0 02 232 32-1-1，即虚存容量为即虚存容量为 4GB4GB。(2)(2)外存的容量。虚拟存储器的容量外存的容量。虚拟存储器的容量与主存的实际大小没有直接的关系，而是由主存与辅存的与主存的实际大小没有直接的关系，而是由主存与辅存的容量之和所确定。容量之和所确定。5.6.2 5.6.2 虚拟内存的特征虚拟内存的特征n虚拟性。虚拟内存不是扩大实际的物理内存，而是扩充逻虚拟性。虚拟内存不是扩大实际的物理内存，而是扩充逻辑内存的容量。辑内存的容量。n部分装入。每个进程不是全部装入内存，而是分成若干个部分装入。每个进程不是全部装入内存，而是分成若干个部分。当进程需要执行时，才将

53、当前运行所需要的程序和部分。当进程需要执行时，才将当前运行所需要的程序和数据装入内存。数据装入内存。n对换性。在一个进程运行期间，它所需要的程序和数据可对换性。在一个进程运行期间，它所需要的程序和数据可以分多次调入。每次仅仅调入一部分，以满足当前程序执以分多次调入。每次仅仅调入一部分，以满足当前程序执行的需要。而且，在内存中那些暂时不使用的程序和数据行的需要。而且，在内存中那些暂时不使用的程序和数据可以换到外存的交换区存放，以腾出尽量多的内存空间供可以换到外存的交换区存放，以腾出尽量多的内存空间供可运行进程使用。可运行进程使用。5.7.1 5.7.1 请求分页存储管理的基本思想请求分页存储管理

54、的基本思想n请求式分页也称虚拟页式存储管理，它的基本思想是：在请求式分页也称虚拟页式存储管理，它的基本思想是：在进程开始运行之前，不是装入全部页面，而是装入一个或进程开始运行之前，不是装入全部页面，而是装入一个或零个页面，之后根据进程运行的需要，动态装入其它页面；零个页面，之后根据进程运行的需要，动态装入其它页面；当内存空间已满，而又需要装入新的页面时，则根据某种当内存空间已满，而又需要装入新的页面时，则根据某种算法淘汰某个页面，以便装入新的页面。算法淘汰某个页面，以便装入新的页面。n为了实现页式虚存，系统需要解决下面三个问题：为了实现页式虚存，系统需要解决下面三个问题：（1 1）系统如何获知

55、进程当前所需页面不在主存。）系统如何获知进程当前所需页面不在主存。（2 2）当发现缺页时，如何把所缺页面调入主存。）当发现缺页时，如何把所缺页面调入主存。（3 3）当主存中没有空闲的页框时，为了要接受一个新页，）当主存中没有空闲的页框时，为了要接受一个新页，需要把老的一页淘汰出去，根据什么策略选择欲淘汰的页需要把老的一页淘汰出去，根据什么策略选择欲淘汰的页面。面。l驻留位（中断位）：表示该页是在内存还是在外驻留位（中断位）：表示该页是在内存还是在外存存l访问位：根据访问位来决定淘汰哪页（由不同的访问位：根据访问位来决定淘汰哪页（由不同的算法决定）算法决定）l修改位：查看此页是否在内存中被修改过

56、修改位：查看此页是否在内存中被修改过页号页号中断位中断位 内存块号内存块号外存地址外存地址访问位访问位 修改位修改位n 页表的扩充页表的扩充 程序在执行时，首先检查页表，当存在位指示该程序在执行时，首先检查页表，当存在位指示该页不在主存时，则引起一个缺页中断发生，相应页不在主存时，则引起一个缺页中断发生，相应的中断处理程序把控制转向缺页中断子程序。执的中断处理程序把控制转向缺页中断子程序。执行此子程序，即把所缺页面装入主存。然后处理行此子程序，即把所缺页面装入主存。然后处理机重新执行缺页时打断的指令。这时，就将顺利机重新执行缺页时打断的指令。这时，就将顺利形成物理地址。缺页中断的处理过程是由硬

57、件和形成物理地址。缺页中断的处理过程是由硬件和软件共同实现的。软件共同实现的。n 缺页中断缺页中断缺页中断同一般中断都是中断，相同点是：缺页中断同一般中断都是中断，相同点是：n 保护现场保护现场 中断处理中断处理 恢复现场恢复现场不同点：不同点：n一般中断是一条指令完成后中断，缺页中断是一般中断是一条指令完成后中断，缺页中断是一条指令执行时中断一条指令执行时中断n一条指令执行时可能产生多个缺页中断。如指一条指令执行时可能产生多个缺页中断。如指令可能访问多个内存地址，这些地址在不同的令可能访问多个内存地址，这些地址在不同的页中。页中。5.7.2 5.7.2 页面置换算法页面置换算法1.1.最佳置

58、换算法最佳置换算法n最佳置换算法是由最佳置换算法是由BeladyBelady于于19661966年提出的一种理论上的算年提出的一种理论上的算法。法。其所选择的被淘汰页面，将是以后永不使用的，或其所选择的被淘汰页面，将是以后永不使用的，或许是在最长许是在最长(未来未来)时间内不再被访问的页面。采用最佳置时间内不再被访问的页面。采用最佳置换算法，通常可保证获得最低的缺页率。换算法，通常可保证获得最低的缺页率。n假定系统为某进程分配了三个物理块，并考虑有以下的页假定系统为某进程分配了三个物理块，并考虑有以下的页面号引用串：面号引用串：7，0，1，2，0，3，0，4，2，3，0，3，2，1，2，0，1

59、，7，0，1 2.2.先进先出先进先出(FIFO)(FIFO)页面置换算法页面置换算法 nFIFO算法是最早出现的页面置换算法。该算法总是淘汰算法是最早出现的页面置换算法。该算法总是淘汰最先进入内存的页面，即选择在内存中停留时间最长（年最先进入内存的页面，即选择在内存中停留时间最长（年龄最老）的一页予以淘汰龄最老）的一页予以淘汰。n 为了说明为了说明FIFOFIFO页面置换算法相关的可能问题，考虑一下页面置换算法相关的可能问题，考虑一下引用串：引用串：1 1，2 2，3 3，4 4，1 1，2 2，5 5，1 1，2 2，3 3，4 4，5 5。n注意到对注意到对4 4个可用内存块的缺页次数（

60、个可用内存块的缺页次数（1010）比）比3 3个内存块的缺个内存块的缺页次数（页次数（9 9）还要大。这种令人难以相信的结果称为）还要大。这种令人难以相信的结果称为BeladyBelady异常现象，即缺页次数随内存块增加而增加。异常现象，即缺页次数随内存块增加而增加。3.3.最近最久未使用最近最久未使用(LRU)置换算法置换算法 n最近最久未使用置换算以最近最久未使用置换算以“最近的过去最近的过去”作为作为“不久将来不久将来”的近似，选择最近一段时间内最久没有使用的页面淘汰掉。的近似，选择最近一段时间内最久没有使用的页面淘汰掉。它的实质是：当需要置换一页时，选择在最近一段时间里它的实质是：当需

61、要置换一页时，选择在最近一段时间里最久没有使用过的页面予以淘汰最久没有使用过的页面予以淘汰 。4.4.LRU的近似算法的近似算法（1）附加引用位算法）附加引用位算法n 通过在规定时间间隔里记录引用位，能获得额外顺序信息。可以为位通过在规定时间间隔里记录引用位，能获得额外顺序信息。可以为位于内存中的每个页表中的每一页保留一个于内存中的每个页表中的每一页保留一个8 bit的字节。在规定的时间的字节。在规定的时间间隔（如，每间隔（如，每100ms）内，时钟定时器产生中断并将控制权交给操作）内，时钟定时器产生中断并将控制权交给操作系统。操作系统把每个页的引用位转移到其系统。操作系统把每个页的引用位转移

62、到其8 bit字节的高位，而将其字节的高位，而将其他位右移，并抛弃最低位。这些他位右移，并抛弃最低位。这些8 bit移位寄存器包含着该页在最近移位寄存器包含着该页在最近8个时间周期内的使用情况。如果移位寄存器含有个时间周期内的使用情况。如果移位寄存器含有00000000，那么该页，那么该页在在8个时间周期内没有使用；如果移位寄存器的值为个时间周期内没有使用；如果移位寄存器的值为11111111，那么，那么该页在过去每个周期内都至少使用过一次。该页在过去每个周期内都至少使用过一次。n 具有值为具有值为11000100的移位寄存器的也要比值为的移位寄存器的也要比值为01110111的页使用更为的页

63、使用更为频繁。如果将这频繁。如果将这8 bit字节作为无符号整数，那么具有最小值的页为字节作为无符号整数，那么具有最小值的页为LRU页，可以被置换出去。如果这个数字不惟一，可以置换所有具有页，可以被置换出去。如果这个数字不惟一，可以置换所有具有最小值的页或在这些页之间采用最小值的页或在这些页之间采用FIFO来选择替换。来选择替换。（2）第二次机会置换法）第二次机会置换法 第二次机会置换法（第二次机会置换法（Second Chance Page Replacement,SCR）是对是对FIFO算法的改进，以避免把经常使用的页面置换出去。算法的改进，以避免把经常使用的页面置换出去。当选择某一页面置

64、换时，就检查最老页面的引用位：如果是当选择某一页面置换时，就检查最老页面的引用位：如果是0，就立即淘汰该页；如果该引用位是，就立即淘汰该页；如果该引用位是1，就给它第二次机会，就给它第二次机会，并选择下一个并选择下一个FIFO页。当一个页获得第二次机会时，其引页。当一个页获得第二次机会时，其引用位清零，到达时间设为当前时间。因此，获得第二次机会用位清零，到达时间设为当前时间。因此，获得第二次机会的页，在所有其他页置换（或获得第二次机会）之前，是不的页，在所有其他页置换（或获得第二次机会）之前，是不会被置换的。另外，如果一个页经常使用，它的引用位总保会被置换的。另外，如果一个页经常使用，它的引用

65、位总保持为持为1，那么它就不会被置换。，那么它就不会被置换。（3）改进型二次机会置换法）改进型二次机会置换法 由访问位由访问位A和修改位和修改位M可以组合成下面四种类型的页面：可以组合成下面四种类型的页面：n 1类类(A=0,M=0)：表示该页最近既未被访问，又未被修改，：表示该页最近既未被访问，又未被修改，是最佳淘汰页。是最佳淘汰页。n 2类类(A=0,M=1)：表示该页最近未被访问，但已被修改，：表示该页最近未被访问，但已被修改，并不是很好的淘汰页。并不是很好的淘汰页。n 3类类(A=1,M=0)：最近已被访问，但未被修改，该页有可：最近已被访问，但未被修改，该页有可能再被访问。能再被访问

66、。n 4类类(A=1,M=1)：最近已被访问且被修改，该页可能再被：最近已被访问且被修改，该页可能再被访问。访问。在进行页面置换时，需要同时检查访问位和修改位，以确在进行页面置换时，需要同时检查访问位和修改位，以确定该页是四类页面中的那一种。其执行过程可分成以下三步：定该页是四类页面中的那一种。其执行过程可分成以下三步：n 从指针所指示的当前位置开始，扫描循环队列，寻找从指针所指示的当前位置开始，扫描循环队列，寻找A=0且且M=0的第一类的第一类页面，将所遇到的第一个页面作为所选中的淘汰页。在第一次扫描期间页面，将所遇到的第一个页面作为所选中的淘汰页。在第一次扫描期间不改变访问位不改变访问位A。n 如果第一步失败，即查找一周后未遇到第一类页面，则开始第二轮扫描，如果第一步失败，即查找一周后未遇到第一类页面，则开始第二轮扫描，寻找寻找A=0且且M=1的第二类页面，将所遇到的第一个这类页面作为淘汰页。的第二类页面，将所遇到的第一个这类页面作为淘汰页。在第二轮扫描期间，将所有扫描过的页面的访问位都置在第二轮扫描期间，将所有扫描过的页面的访问位都置0。n 如果第二步也失败，亦即未找到第二类页面