操作系统二版-OS--第三章-课件

1、第三章 存储管理 (Memory Management) 存储器是计算机系统的重要组成部分，所以存储器的管理是操作系统最主要的功能之一。当程序的指令和数据当以文件的形式存放在磁盘上时，是不能被CPU访问的，只有当被调入内存（RAM）里才能被CPU直接访问，程序才能够被执行。虽然目前的RAM芯片的集成度在不断地提高，从原来的几百到现在的几百兆甚至上千兆，价格也在不断地降低，但是软件系统需要的内存容量也在不断地增加，所以内存的容量仍然是计算机硬件中最关键的、且又是最紧张的“瓶颈”资源。如何对存储器进行有效的管理，不仅直接影响到它的利用率，而且还对系统的性能有重大影响。存储管理的主要对象是内存。 教

2、学要求熟悉存储管理目的和功能，掌握地址重定位的概念。熟悉单一连续分配、固定分区分配、动态分区分配实现原理；掌握可变分区分配的数据结构和分配回收算法，熟悉可变分区零头和拼接技术 。熟练掌握分页存储管理原理，熟练掌握分页存储管理基本的地址变换机构和具有快表的地址变换机构。掌握分段存储管理原理和分段地址变换机构，掌握分页和分段比较，熟悉分页和分段的共享，掌握段页式存储管理原理和地址变换机构。教学要求-1掌握虚拟存储器的理论基础和定义，熟悉虚拟存储器实现方式和特征。掌握请求分页的页表机制、缺页中断机构和地址变换机构，熟悉页面的分配和置换策略、页面的分配的算法。熟练掌握最佳置换算法、先进先出（FIFO）

3、置换算法、最近最久未使用置换算法LRU，熟悉Clock置换算法和页面缓冲算法；熟悉有效访问时间计算，了解工作集概念。掌握请求分段的段表机制、缺段中断机构和地址变换机构，熟悉分段的共享和保护。存储管理目录31 存储管理概述311存储层次结构312存储管理的功能313 地址重定位32 存储器的连续分配321单一连续分配322固定分区分配323可变（动态）分区分配33存储器的离散分配331纯分页存储管理332 分段存储管理333 段页式存储管理存储管理目录-134虚拟存储器管理技术341虚拟存储器的基本概念342请求分页存储管理343请求分段存储管理35 Windows2000内存的管理351Int

4、el x86/Pentium系列CPU对内存管理的硬件支持机制352 Windows2000地址空间的划分353 Windows2000用户空间内存分配和使用354页面调度策略355物理内存管理35. 6 Windows 2000高速缓冲管理存储管理目录-236 实验与习题361实验一：在Windows2000下评价内存和缓存使用362 实验2：Windows 2000 内存管理API函数的使用363 选择题364 问答题31 存储管理概述311存储层次结构 存储器是处理器处理的信息的来源与归宿，占据着重要地位。但任何一种存储设备都无法在速度与容量两个方面同时满足用户的需求。为解决速度和容量之

5、间的矛盾，冯诺依曼计算机系统中，采用了三级或更多级的存储器来组成存储层次结构，高一级为CPU寄存器和高速缓存器，中间是主存(可执行的存储器)，最低一级为辅存。通过采用特殊的存储技术，主存与辅存两级可以进一步优化成多级。在存储层次结构中，高层的存储器往往是速度很快、但成本高使容量有限，而接近底部的存储器容量很大、成本低，相对访问速度则慢。各种存储设备组成存储层次结构，如图51所示。 存储层次结构图高速缓存器主存辅存10MB12时钟1GB14时钟绝对地址2150(=2000+150)内容修改：内容100变成2100(=100+2000)。动态重定位 动态重定位是指在程序执行过程中进行地址重定位，即

6、在每次访问内存单元前才进行地址变换。动态重定位可使装配模块不加任何修改就装入内存，但是它需要硬件重定位寄存器的支持。下图给出了动态重定位的示意图。程序的目标模块在装入内存时，与地址有关的指令都无须进行修改，如在图3-4中LOAD 1，2500这条指令中仍保持相对地址2500。当该指令被操作系统取到中央处理器指令寄存器上执行时，操作系统首先把该模块装入的实际起始地址减去目标模块的相对基地址（图3-4中该模块的基地址为0），然后将其差值10000装入重定位寄存器。 动态重定位的示意图LOAD 1，25003650：10025002600程序的地址空间LOAD 1，25003651000010100

7、12500物理地址内存的地址空间重定位寄存重定位寄存器中央处理器CPU指令寄存器LOAD 1,25002500(逻辑地址)MMU(存储管理部件)CPU芯片+10000动态重定位-1当CPU执行该指令时，地址变换硬件逻辑自动将指令中的逻辑地址2500与重定位寄存器中的值相加，再根据和值作为内存的绝对地址去访问该单元的数据，读入的数据送到寄存器1。完成地址变换硬件是属于存储管理部件 MMU，目前它已集成到中央处理器CPU中。 由此可见，动态重定位是在指令执行过程中动态进行，它由硬件完成，这样可以带来两个好处：目标程序装入内存时无需任何修改，所以装入之后再移动也不会影响其正确运行，这便于存储器用紧缩

8、来解决存储器的碎片问题。一个程序由若干个相对独立的目标模块组成时，每个目标模块各装入一个存储区域，这些存储区域可以不相领接，只要各个模块有自己对应的重定位寄存器就可以了。3.链接 静态链接(static-linking)是在生成可执行文件时进行的。在目标模块中记录符号地址(symbolic address)，而在可执行文件中改写为指令直接使用的数字地址。 有一个程序P（如图所示），它既可以被其它程序调用（通过用符号定义的入口点如P, e, d），也可以调用别的程序模块。前一种情况称为内部定义符号，后者称为外部调用符号。一个源程序经编译或汇编后生成的可重定位目标模块必须明显地给出这些内部符号和外

9、部符号，以供连接装入程序使用。每个可重定位目标段相关联的除重定位表（又称重定位词典）或指示字外，还应有一张内部定义符号表和外部调用符号表。链接例-1链接例-2CALL SUB1ADD TIME内部定义符号：P, e, d。外部调用符号：SUB1, TIME。Ped内部定义符号表符号名地址PedSUB1TIMEPeCALL*ADD*d.外部调用符号表重定位词典.代码和数据区链接例-3动态链接动态链接(dynamic-linking)在装入或运行时进行链接。通常被链接的共享代码称为动态链接库(DLL, Dynamic-Link Library)或共享库(shared library)。优点：共享：

10、多个进程可以共用一个DLL，节省内存，减少文件交换。部分装入：一个进程可以将多种操作分散在不同的DLL中实现，而只将当前操作相应的DLL装入内存。便于局部代码修改：即便于代码升级和代码重用；只要函数的接口参数（输入和输出）不变，则修改函数及其DLL，无需对可执行文件重新编译或链接。便于运行环境适应：调用不同的DLL，就可以适应多种使用环境和提供不同功能。如：不同的显示卡只需厂商为其提供特定的DLL，而OS和应用程序不必修改。缺点：链接开销：增加了程序执行时的链接开销；管理开销：程序由多个文件组成，增加管理复杂度。32 存储器的连续分配 321单一连续分配 这是一种最简单的存储管理方式，但只能用

11、于单用户、单任务的操作系统，如在8位和16位微机上CP/M和MS-DOS操作系统。它将内存分为两个区： 系统区：仅供操作系统使用，通常设置在内存的低段； 用户区：指除系统区以外的全部内存空间，提供给用户使用。 这种存储分配方式由于用在单用户、单任务的操作系统中。单一连续分配-1系统区操作系统用户区用户程序 0下限上限基址长度单一连续区存储管理322固定分区(Fixed Partitioning)分配 分区存储管理是能够满足多道程序运行的最简单的存储器管理方案，其基本思想是将内存划分成若干个连续的区域，称为分区。每个分区只能储存一个程序，而且程序也只能在它所驻留的分区中运行。分区存储管理根据分区

12、个数及分区大小的可变性分为固定式分区和可变式分区两种。 固定分区是在作业装入之前，内存就被划分成若干个分区。划分工作可以由系统管理员完成，也可以由操作系统实现。然而一旦划分完成，在系统运行期间不再重新划分，即分区的个数不可变，分区的大小不可变，所以，固定式分区又称为静态分区。 这种分区方式一般将内存的用户区域划分成大小不等的分区，以适应不同大小的作业的需要。系统有一张分区说明表，每个表目说明一个分区的大小、起始地址和是否已分配的使用标志。分区说明表和内存分配图如下所示。 固定分区分配-1区号 大小 起址 标志 1 16KB20K已分配 2 32KB36K已分配 3 64KB68K已分配 4 1

13、24KB 132K 未分配 (a) 分区说明表 固定式分区实现技术简单，但是内存的利用率不高，适用于作业的大小和多少事先都比较清楚的系统中。它用于60年代的IBM-360的MFT操作系统中。0k： 20k： 36k： 68k： 132k： 256k： 内存分配图 操作系统作业A（16k）作业B（26k）作业C（56k）第1分区（16kb）第2分区（32kb） （已分配）第3分区（64kb） （已分配）4分区（124kb ） （未分配） 固定分区分配-2由于每个分区的大小是固定的，所以每个提出运行的作业必须说明所需的最大内存容量。在调度作业时，存储管理程序根据作业所需的内存容量，在分区说明表中找

14、出一个足够大的空闲分区分配给它，然后用重定位装入程序将此作业装入。如果找不到，则通知作业调度模块，选择另外一个作业。图3-6（b）说明了某一时刻，作业A、B、C分别被分配到1，2，3三个分区中，第四个分区尚未分配，操作系统则永久占据内存低地址区20KB的空间。当一个作业结束时，系统又调用存储管理程序查到分区说明表，把所占分区的使用标志修改为未分配状态即可。 固定分区分配-3采用这种技术，虽然可以使多个作业共驻内存，但是一个作业的大小不可能正好等于某个分区的大小，所以每个被分配的分区总有一部分被浪费，我们把这部分被浪费的存储区称为内零头或内碎片。有时这种分配方式浪费相当严重，如图3-6（b）中第

15、3分区未分配的部分还有8KB，加上第4分区的124KB共计132KB，而且这132KB的内存空间在物理上是一个连续的区域，这时如果有一个大小为130KB的作业申请内存，却被拒绝，因为分区的大小是预先划分好的，分区说明表中指出只有第4分区未分配（大小为124K），且不能改变分区的大小。Multiprogramming with Fixed PartitionsFixed memory partitionsseparate input queues for each partitionsingle input queue323可变（动态） (Dynamic Partitioning)分区分配 1.

16、 可变分区概述可变分区是指在作业装入内存时，从可用的内存中划出一块连续的区域分配给它，且分区大小正好等于该作业的大小。可变分区中分区的大小和分区的个数都是可变的，而且是根据作业的大小和多少动态地划分，因此又称为动态分区。这种存储管理技术是固定式分区的改进，既可以获得较大的灵活性，又能提高内存的利用率。系统初始化后，内存被划分成两块，一块用于常驻的操作系统，另一块则是完整的空闲区（用户区）。对于调入的若干个作业，划分几个大小不等的分区给它们，随着作业的调入和撤除，相应的分区被划分和释放，原来整块的存储区形成空闲区和已分配区相间的局面。图3-7（c）给出了可变式分区的示例，512KB内存中除20K

17、B操作系统外，装入作业2、3、4、6四个，有空闲区1、2、3三个。 可变式分区数据结构图表 序号P大小起址状态 132k20k空闲 256k260k空闲 3 116k396k空闲 4空表目 5空表目 （a）空闲分区表前向指针 N+2 00后向指针 N+2 00N个字可用空闲区（56k）作业6（80k）空闲区（116k）空闲区（32k）作业2（64k）作业3（48k）作业4（96k）操作系统(20K)020K52K116K164K260K316K396K512K返回可变分区概述-1可变式分区的分配和释放的基本思想是：在分配时，首先找到一个足够大的空闲分区，即这个空闲区的大小比作业要求的要大，系统

18、则将这个空闲分区分成两部分：一部分成为已分配的分区，剩余的部分仍作为空闲区。在回收撤除作业所占领的分区时，要检查回收的分区是否与前后空闲的分区相领接，若是，则加以合并，使之成为一个连续的大空间。 Example Dynamic PartitioningOperating SystemProcess 1320 KProcess 2Process 3224 K288 K64 KOperating SystemProcess 1320 KProcess 3224 K288 K64 KOperating SystemProcess 1320 KProcess 3288 K64 KProcess 412

19、8 K96 KExample Dynamic Partitioning-1Operating System320 KProcess 3288 K64 KProcess 4128 K96 KOperating SystemProcess 3288 K64 KProcess 4128 K96 KProcess 2224 k96 K动态/可变式分区分配-12. 可变式分区的数据结构 空闲区表形式 空闲分区表为每个尚未分配的分区设置一个表项，包括分区的序号、大小、始址和状态。空闲区链形式 为了实现对空闲分区的分配和链接，在每个分区的起始部分，设置一些用于控制分区分配的信息（如分区的大小和状态位），以及

20、用于链接其它分区的前向指针；在分区尾部，则设置了一个后向指针，为了检索方便也设置了控制分区分配的信息。然后，通过前、后向指针将所有的分区链接成一个双向链表。3. 可变分区分配算法 (Partitioning Placement Algorithm)(1)最佳适应算法BF（Best Fit）：它从全部空闲区中找出能满足作业要求的、且大小最小的空闲分区，这种方法能使碎片尽量小。为适应这种算法，空闲分区表（空闲区链）中的空闲分区要按大小从小到大进行排序，自表头开始查找到第一个满足要求的自由分区分配。该算法保留大的空闲区，但造成许多小的空闲区。(2)首次适应算法FF（First Fit）：从空闲分区表

21、的第一个表目起查找该表，把最先能够满足要求的空闲区分配给作业，这种方法目的在于减少查找时间。为适应这种算法，空闲分区表（空闲区链）中的空闲分区要按地址由低到高进行排序。该算法优先使用低址部分空闲区，在低址空间造成许多小的空闲区，在高地址空间保留大的空闲区。可变分区分配算法-1(3)循环首次适应算法NF(Next Fit)：该算法是首次适应算法的变种，它把空闲分区表（空闲区链）中的空闲分区按地址递增构成一个循环链。在分配内存空间时，不再每次从表头（链首）开始查找，而是从上次找到的空闲区的下一个空闲区开始查找，直到找到第一个能满足要求的的空闲区为止，并从中划出一块与请求大小相等的内存空间分配给作业

22、。该算法能使内存中的空闲区分布得比较均匀。(4)最坏适应法：从所有未分配的分区中挑选最大的且大于和等于作业大小的分区分给要求的作业；空闲分区按大小由大到小排序。该算法使小的空闲区减少，但造成大的空闲区不够大。例：分配一个16KB分区采用空闲分区表结构和首次适应分配算法 空闲分区表数据结构空闲分区表中的空闲分区要按地址从低到高连续排序，最后一个空闲分区中 m_size为0表示以上表目空白。空闲分区表起始地址为coremap分配和释放的基本思想是：在分配时，首先找到一个足够大的空闲分区，即这个空闲区的大小比作业要求的要大，系统则将这个空闲分区分成两部分：一部分成为已分配的分区，剩余的部分仍作为空闲

23、区。在回收撤除作业所占领的分区时，要检查回收的分区是否与前后空闲的分区相领接，若是，则加以合并，使之成为一个连续的大空间。m_addrm_size.m_addrm_size=0.m_addrm_sizem_addrm_sizem_addrm_sizem_addrm_sizeCoremap采用首次适应算法的可变分区的分配流程图 申请分配一个u.size大小的分区从头开始查表是否检索完毕？本次无法分配m.sizeu.size m.size-u.sizesize？从该分区中划出u.size大小的分区继续检索下一个表项将该表目以上的所有表目下移一格将该分区分配给申请者修改有关的数据结构 返 回YNN4

24、. 可变分区回收算法 当一个作业运行完毕释放内存时，系统根据释放区的首地址，从空闲区说明表中找到相应的插入点，此时可能出现下列四种情况（如图3-9所示，其中F1，F2表示回收区的前、后空闲区）：(1)当回收区既不与F1领接，又不与F2领接时（如图3-9（a），应为回收区单独建立一项新表目，填写回收区的起址和大小，并根据其起址，插入到空闲区说明表的适当位置。(2)当回收区只与插入点的前一个分区F1相领接时（如图3-9（b），应将回收区与插入点的前一个分区合并，不再为回收区分配新的表目，而只需修改F1分区表目的大小即可。 可变分区回收算法 -1(3)当回收区只与插入点的后一个分区F2相领接时（如图

25、3-9（c），将把两个空闲区合并，修改F2分区的表目，把回收区的起址作为新空闲区的起址，大小为两个分区之和。(4)当回收区与插入点的前、后两个分区（F1和F2）都相领接时（如图3-9（d），合并三个分区，用F1表目的起址作为新空闲区的起址，修改其大小为三块分区之和，最后取消F2的表目。图3-7（c）内存分配图中作业3、2、4、6分别回收时相当于图3-9（a）、（b）、（c）、（d）内存回收时的情况。 可变分区回收算法 -2 作业Y回收区 作业X F1 F1 回收区 作业Y F2 F1 回收区 F2 作业Y 回收区 F2 作业X 作业Y A B C D可变分区回收算法 -3对于前图所示的可变式分

26、区内存分配图，下列四种情况分别如下图所示： 作业4回收区 作业2空闲区1 空闲区1 回收区 作业3 空闲区2 回收区空闲区3 回收区 空闲区2 作业3 作业6 A B C D作业3回收 作业2回收 作业4回收 作业6回收可变分区回收算法 -4作业3回收前后序号P大小起址状态 132k20k空闲 256k260k空闲 3 116k396k空闲 4空表目 5空表目 （a）空闲分区表序号P 大小 起址 状态 1 32k 20k 空闲 2 48k 116k 空闲 3 56k 260k 空闲 4 116k 396k 空闲 5 空表目 空闲分区表空闲区2（56k）作业6（80k）空闲区3（116k）空闲区

27、1（32k）作业2（64k）作业3（48k） 回收区作业4（96k）操作系统(20K)020K52K116K164K260K316K396K512K空闲区3（56k）作业6（80k）空闲区4（116k）空闲区1（32k） 作业2（64k）空闲区2（48k）作业4（96k）操作系统(20K)020K52K116K164K260K316K396K512K 回收前 回收后空闲区2（56k）作业6（80k）空闲区3（116k）作业3 （48k）作业4（96k）操作系统(20K)020K116K164K260K316K396K512K空闲区2（56k）作业6（80k）空闲区3（116k）空闲区1（32k

28、）作业2（64k） 回收区作业3（48k） 作业4（96k）操作系统(20K)020K52K116K164K260K316K396K512K 回收前 回收后可变分区回收算法 -5作业2回收前后序号P大小起址状态 132k20k空闲 256k260k空闲 3 116k396k空闲 4空表目 5空表目 （a）空闲分区表序号P 大小 起址 状态 1 96k 20k 空闲 2 56k 260k 空闲 3 116k 396k 空闲 4 空表目 5 空表目 空闲分区表空闲区1（96k）可变分区回收算法 -6作业4回收前后序号P大小起址状态 132k20k空闲 256k260k空闲 3 116k396k空闲

29、 4空表目 5空表目 （a）空闲分区表序号P 大小 起址 状态 1 32k 20k 空闲 2 152k 164k 空闲 3 116k 396k 空闲 4 空表目 5 空表目 空闲分区表空闲区2（56k）作业6（80k）空闲区3（116k）空闲区1（32k）作业2（64k）作业3（48k） 作业4（96k） 回收区操作系统(20K)020K52K116K164K260K316K396K512K空闲区2（152k）作业6（80k）空闲区3（116k）空闲区1（32k）作业2（64k）作业3 （48k）操作系统(20K)020K52K116K164K316K396K512K 回收前 回收后可变分区回

30、收算法 -7作业6回收前后序号P大小起址状态 132k20k空闲 256k260k空闲 3 116k396k空闲 4空表目 5空表目 （a）空闲分区表序号P 大小 起址 状态 1 32k 20k 空闲 2 252k 260k 空闲 3 空表目 4 空表目 5 空表目 空闲分区表作业6（80k）空闲区4（116k）空闲区2（56k）作业6-80k回收区空闲区3（116k）空闲区1（32k）作业2（64k）作业3（48k） 作业4（96k）操作系统(20K)020K52K116K164K260K316K396K512K空闲区2（252k）空闲区1（32k）作业2（64k）作业3 （48k）作业4（

31、96k）操作系统(20K)020K52K116K164K260K512K 回收前 回收后可变分区回收算法 -8后空闲区不 D不 A邻 B邻 C前空闲区不邻不邻表目加一/ /减一后空闲区首址/-size撤消后空闲区大小/+size撤消前空闲区首址/前空闲区大小/+size/+size+后空闲区大小5. 可变分区零头和拼接技术 可变分区也有零头问题。在系统不断地分配和回收中，必定会出现一些不连续的小的空闲区，称为外零头或外碎片。虽然可能所有零头的总和超过某一个作业的要求，但是由于不连续而无法分配。解决零头的方法是拼接或紧凑（Compaction），即向一个地址方向（例如向低地址端）移动已分配的作业

32、，使那些零散的小空闲区在另一方向连成一片。分区的拼接技术，一方面是要求能够对作业进行重定位，另一方面系统在拼接时要耗费较多的时间。采用拼接技术的可变分区又称可重定位分区。 动态重定位分区分配例 20k28k88k132k182ko.s作业1(8k)(16k)作业3(24k)(24k)作业(20k)作业4(50k)(74k)64k112k256k(a)初始状态20k202ko.s1324作业5(80k)(54k)122k(c)分配作业5之后(b)移动之后(即浮动)20k28k72ko.s1(8k)3(24k)2(20k)4(50k)(134k)52k122k256k作业580k6. 分区的存储保

33、护 分区的存储保护是用户程序只能访问自己的用户分区，不能访问系统分区和其它程序的分区。分区存储保护常用方法是界地址法或界限寄存器。系统设置一对上、下界寄存器，每当选中某个作业运行时，先将它的界地址装入这对寄存器中，作业运行时形成的每一个访问存储器的地址都要同这两个寄存器的内容进行比较，若超过这个指定范围，就产生越界中断。系统也可以设置一对基址、限长寄存器，此时基址寄存器还起着重定位寄存器的作用，运行进程所在分区的始址和大小分别装入基址和限长寄存器。界限寄存器用硬件实现，它是存储管理部件 MMU的一部分，采用基址、限长寄存器的地址变换和存储保护的存储管理部件 MMU见图310所示。 分区的存储保

34、护 -1界限寄存器重定位寄存器(基址)+CPU=1地址越界地址越界lbSlbSegmentation Hardware5共享 段是信息的逻辑单位,因此分段系统的一个突出的优点是易于实现段的共享。即允许若干个进程共享一个或多个段，而且对段的保护也十分简单。在分页系统中，虽然也能实现程序和数据的共享，但远不如分段系统来得方便。分段系统中，每个进程的段表中设置一个段表项。图是分段系统中共享 editor编辑程序的示意图。在实现段共享时，需要用到可重入代码(Reentrant Code)又称为“纯代码”(Pure Code)。它是一种允许多个进程同时访问的代码，是一种不允许任何进程对其进行修改的代码。

35、但在每个进程中，配以局部数据区，将在执行中可能改变的部分，拷贝到该数据区，这样，程序在执行时，只对该数据区(属于该进程私有)中的内容进行修改，而不去改变共享的代码，这时的可共享代码即成为可重入代码。共享-1 段 表段长 基址 160 80 40 240 editor DATA1 editor DATA2段长 基址160 8040 380 editorDATA1 DATA2进程1进程2 802402803804206分页和分段的主要区别 分页和分段的主要区别-1 333 段页式存储管理 分页和分段存储管理方式都各有其优缺点。如果对两种存储管理方式“各取所长”后，则可以形成一种新的存储管理方式的系

36、统段页式系统。它以分页的方式管理内存，具有分页系统能有效地提高内存利用率的优点；又以分段的方式管理用户的逻辑地址空间，具有分段系统能很好地满足用户需要的长处，显然是一种比较有效的存储管理方式。 1基本原理 段页式系统的基本原理是将内存空间划分成相同大小相同的若干个块，将用户程序先按逻辑完整性分为若干个段，并为每个段赋予一个段名，再把每个段划分成若干个与块大小相同的页，将进程中的若干页离散装入不相邻接的块中。图3-20中示出了一个作业地址空间结构，该作业有四个段，页面大小为4K，四个段的页面数分别为4、2、2、2，总页面数为10页，此时每一页都属于逻辑上完整的一个段。在段页式系统中，其地址结构由

37、段号、段内页号和页内地址三部分组成，作业地址空间的结构如图3-21所示。 基本原理-1 在段页式系统中，为了实现从逻辑地址到物理地址的变换，系统中必需同时配置段表和页表。由于将段中的页进行离散地分配，段表中的内容不再是段的内存始址和段长，而是页表始址和页表长度。下图说明了利用段表和页表进行地址映射的过程。 段号（S） 段内页号（P） 页内地址（W）段页式系统的作业地址空间 段表、页表的作用段表大小段表始址2地址变换过程在段页式系统中，有一个段表寄存器，存放段表始址和段长TL。在进行地址变换时，系统将逻辑地址截成段号S、段内页号P与页内地址W，先用段号S与段长TL进行比较。若 STL，表示段号太

38、大，访问越界，于是产生越界中断信号；若STL，表示未越界，于是利用段表始址和段号求出该段对应的段表项在段表中的位置，从中得到该段的页表始址，并利用逻辑地址中的段内页号P来获得对应页的页表项在页表中位置，从中读出该页所在的物理块号b，再用块号 b和页内地址W拼成物理地址。图3-23说明了段页式系统中的地址变换机构 。地址变换过程-1在段页式系统中，为了获得一条指令或数据，需三次访问内存：第一次访问内存中的段表，从中取得页表始址；第二次访问内存中的页表，从中取出该页所在的物理块号，并将该块号与页内地址一起形成指令或数据的物理地址；第三次访问才是真正根据所得的物理地址取出指令或数据。显然，这使访问内

39、存的次数增加了近两倍。为了提高执行的速度，在地址变换机构中增设一高速缓冲寄存器。每次访问它时，都同时利用段号和页号去检索高速缓存。段页式系统的地址变换机构图 + 段 表0123 页 表0123段表始址 段表长度 +段号（S）段内页号（P）页内地址（W）块 号b 块内地址越界中断段表寄存器CPU逻辑地址物理地址 b页表始址34虚拟存储器管理技术 前面所介绍的各种存储器管理方式，有一个共同的特点，即要求将一个作业全部装入内存才能运行。如果有的作业很大，其所要求的内存空间超过了内存总容量，作业就不能全部被装入内存，致使该作业无法运行；有时大量作业要求运行，但由于内存容量不足以容纳所有这些作业，只能将

40、少数作业装入内存让它们先运行，而将其它大量的作业留在外存上等待。显而易见的一种解决方法，是从物理上增加内存容量，但这往往会受到机器自身的限制，而且无疑要增加系统成本，因此这种方法是受到一定限制的；另一种方法是从逻辑上扩充内存容量，这正是虚拟存储技术所要解决的主要问题。 341虚拟存储器的基本概念 1局部性原理(principle of locality)实际上有许多作业在每次运行时，并非用到其全部程序，那么是否可以仅把作业的一部分装入内存就能运行呢？回答是可以的，我们先来研究虚拟存储器系统实现的理论基础：程序执行的局部性规律。早在1968年PDenning就指出过，程序在执行时将呈现出局部性规

41、律，即在一段时间内，程序的执行仅局限于某个部分；相应地，它所访问的存储空间也局限于某个区域内。局部性原理-1那么程序为什么会出现局部性规律呢？原因可以归结为以下几点：程序在执行时，除了少部分的转移和过程调用指令外，大多数仍是顺序执行的。子程序调用将会使程序的执行由一部分内存区域转至另一部分区域。但在大多数情况下，过程调用的深度都不超过5。程序中存在许多循环结构，循环体中的指令被多次执行。程序中还包括许多对数据结构的处理，如对连续的存储空间数组的访问，往往局限于很小的范围内。局部性原理- 2 所以局限性表现为： 时间局限性：如果程序中的某条指令一旦执行，则不久的将来该指令可能再次被执行；如果某个

42、存储单元被访问，则不久以后该存储单元可能再次被访问。产生时间局限性的典型原因是在程序中存在着大量的循环操作。 空间局限性：一旦程序访问了某个存储单元，则在不久的将来，其附近的存储单元也最有可能被访问。 即程序在一段时间内所访问的地址，可能集中在一定的范围内，其典型原因是程序是顺序执行的。2。虚拟存储器的定义 根据局部性原理，一个作业在运行之前，没有必要把全部作业装入内存，而仅将那些当前要运行的那部分页面或段，先装入内存便可启动运行，其余部分暂时留在磁盘上。程序在运行时如果它所要访问的页（段）已调入内存，便可继续执行下去；但如果程序所要访问的页（段）尚未调入内存（称为缺页或缺段），此时程序应利用

43、操作系统所提供的请求调页（段）功能，将它们调入内存，以使进程能继续执行下去。如果此时内存已满，无法再装入新的页（段），则还须再利用页（段）的置换功能，将内存中暂时不用的页（段）调出至磁盘上，腾出足够的内存空间后，再将所要访问的页（段）调入内存，使程序继续执行下去。这样，便可使一个大的用户程序在较小的内存空间中运行；也可使内存中同时装入更多的进程并发执行。从用户角度看，该系统所具有的内存容量，将比实际内存容量大得多，人们把这样的存储器称为虚拟存储器。 虚拟存储器的定义-1 虚拟存储器是采用请求调入和置换功能，将内存和外存统一管理，达到把作业的一部分装入内存便可运行，给用户提供的一个比内存容量大的

44、一维的逻辑地址空间。 虚拟存储器的逻辑容量由内存和外存容量之和、计算机的地址结构二者所决定，其运行速度接近于内存速度，而每位的成本却又接近于外存。实现虚拟存储技术的物质基础是：一是有相当容量的辅助存储器以存放所有并发作业的地址空间；二是有一定容量的内存来存放运行作业的部分程序；三是有动态地址转换机构，实现逻辑地址到物理地址的转换。可见，虚拟存储技术是一种性能非常优越的存储器管理技术，故被广泛地应用于大、中、小型机器和微型机中。虚拟存储器的定义-2外存内存虚拟存储器逻辑地址虚拟存储器实现方式请求分页系统： 它是在分页系统的基础上，增加了请求调页功能和页面置换功能所形成的页式虚拟存储系统。它允许只

45、装入若干页（而非全部程序）的用户程序和数据，就可以启动运行，以后再通过调页功能和页面置换功能，陆续把将要运行的页面调入内存，同时把暂不运行的页面置换到外存上，置换时以页面为单位。请求分段系统： 它是在分段系统的基础上，增加了请求调段和分段置换功能所形成的段式虚拟存储系统。它允许只装入若干段（而非全部段）的用户程序和数据，就可以启动运行，以后再通过调段功能和置换功能将不运行的段调出，同时调入将要运行的段，置换以段为单位。请求段页式系统：它是在段页式系统的基础上，增加了请求调页和页面置换功能所形成的段页式虚拟存储系统。3。虚拟存储器的特征离散性：指在内存分配时采用离散的分配方式，它是虚拟存储器的最

46、基本的特征。多次性：指一个作业被分成多次调入内存运行，即在作业运行时没有必要将其全部装入，只须将当前要运行的那部分程序和数据装入内存即可。多次性是虚拟存储器最重要的特征。对换性：指允许在作业的运行过程中在内存和外存的对换区之间换进、换出。虚拟性：指能够从逻辑上扩充内存容量，使用户所看到的内存容量远大于实际内存容量。342请求分页存储管理 请求分页存储管理方式是在纯分页系统的基础上，增加了请求调页功能、页面置换功能所形成的页式虚拟存储系统，它是目前常用的一种虚拟存储器的方式。它允许只装人若干页(而非全部页)的用户程序和数据，便可启动运行。以后，再通过调页功能及页面置换功能，陆续地把即将要运行的页

47、面调入内存，同时把暂不运行的页面换出到外存上，置换时以页面为单位。 342请求分页存储管理 1。请求分页中的硬件支持为了能实现请求调页和置换功能，系统必须提供必要的硬件支持：扩充的页表机制和缺页中断机构。 （1）请求分页的页表机制 它是在纯分页的页表机制上形成的，由于只将应用程序的一部分调入内存，还有一部分仍在磁盘上，故需在页表中再增加若干项，供程序(数据)在换进、换出时参考。在请求分页系统中的每个页表项如图所示。 页号 物理块号 状态位P 访问字段A 修改位M 外存地址请求分页中的硬件支持-1其中各字段说明如下：状态位（中断位P）：用于指示该页是否已调入内存，供程序访问时参考。外存地址：用于

48、指出该页在外存上的地址，通常是物理块号，供调入该页时使用。访问字段A：用于记录本页在一段时间内被访问的次数，或最近已有多长时间未被访问，提供给置换算法选择换出页面时参考。修改位M：表示该页在调入内存后是否被修改过。由于内存中的每一页都在外存上保留一份副本，因此，若未被修改，在置换该页时就不需将该页写回到外存上，以减少系统的开销和启动磁盘的次数；若已被修改，则必须将该页重写到外存上，以保证外存中所保留的始终是最新副本。外存地址：用于指出该页在外存上的地址，通常是物理块号，供调入该页时使用 (2)缺页中断机构在请求分页系统中，每当所要访问的页面不在内存时，便要产生一缺页中断，请求OS将所缺页调入内

49、存。与一般中断的主要区别在于：缺页中断在指令执行期间产生和处理中断信号，而一般中断在一条指令执行完后检查和处理中断信号。缺页中断返回到该指令的开始重新执行该指令，而一般中断返回到该指令的下一条指令执行。一条指令在执行期间，可能产生多次缺页中断。(3)地址变换机构 请求分页系统中的地址变换机构，是在分页系统的地址变换机构的基础上，再为实现虚拟存储器而增加了某些功能所形成的，如产生和处理缺页中断，以及从内存中换出一页的功能等等，下图给出了请求分页系统的地址变换过程。 缺页中断处理 是 否 否 是 是 否 产生缺页中 否 是 断请求调页 是 开始（程序请求访问一页)越界中断CPU检索快表页表项是否在

50、快表中？访问页表页是否在内存中？修改快表修改访问位和修改位形成物理地址 地址变换结束保留CPU现场 从外存中找到缺页 页号页表长度？ 内存满否？选择一页换出 该页是否被修改？ 将该页写回外存 将一页从外存换入内存 修改页表 CPU从外存读缺页 启动I/O硬件 2. 请求分页存储管理应考虑的问题 （1）最少物理块数的确定 在为进程分配物理块时，首先应该考虑的问题是：能保证进程能正常运行所需的最少物理块数（称为最小物理块数）。若系统为某进程所分配的物理块数少于此值时，进程将无法运行，这取决于指令的格式、功能和寻址方式。物理块数目的下限，应该是一条指令及其操作数可能涉及的页面数目的上限，以保证每条指

51、令都能被执行。（2）物理块的分配和置换策略 在请求分页系统中，可采取两种分配策略固定和可变分配策略。在进行置换时，也可采取两种策略全局置换和局部置换。于是可组合成以下三种策略。固定分配局部置换策略：它基于进程的类型（交互型或批处理型等），或根据程序员、系统管理员的建议，为每个进程分配一固定页数的内存空间，在整个运行期间都不再改变。如果进程在运行中发现缺页，则只能从该进程在内存的固定页面中选出一页换出，然后再调入另一页，保证分配给该进程的内存空间不变。物理块的分配和置换策略 -1可变分配全局置换策略：系统为每个进程分配一定数目的物理块，而OS本身也保持一个空闲物理块队列。当某进程发现缺页时，由系

52、统从空闲物理块队列中，取出一物理块分配给该进程，并将欲调入的缺页装入其中。当空闲物理块队列中的物理块用完时，OS才能从内存中选择一页调出，该页可能是系统中任一进程的页。可变分配局部置换：根据进程的类型或程序员的要求，为每个进程分配一定数目的内存空间；但当某进程发生缺页时，只允许从该进程在内存的页面中选出一页换出，而不影响其它进程的运行。（3）物理块分配算法 在采用固定分配策略时，可采用以下几种物理块分配方法：平均分配算法：将系统中所有可供分配的物理块，平均分配给各个进程。按比例分配算法：这是根据进程的大小按比例分配物理块。考虑优先权的分配算法：该方法是把内存中可供分配的所有物理块分成两部分：一

53、部分按比例分配给各进程；另一部分则根据各进程的优先权，适当地增加其相应份额后，分配给各进程。（4）调页策略 (fetch policy) 调入页面的时机为了将进程运行时所缺的页面调入内存，可采取预调页策略或请求调页策略两种方法。预调页策略是一种主动的缺页调入策略，即将那些预计在不久的将来会被访问的程序或数据所在的页面，预先调入内存。由于预测的准确率不高（50%），所以这种策略主要用于进程的首次调入。有的系统将预调页策略用于请求调页，例如在VAX/VMS操作系统中，采用了一种称为群页式的调页策略，当系统将进程所请求的页面调入内存时，也同时将其相邻的几个页面调入内存。请求调页策略是指当进程在运行中

54、发生缺页时，就立即提出请求，由系统将缺页调入内存。目前的虚拟存储器中，大多采用此策略。但这种策略在调页时须花费较大的系统开销，如需频繁启动磁盘I/O。 调页策略-1从何处调入页面在虚拟存储系统中，外存（硬盘）常常被分成两部分；文件区（用于存放文件）和对换区（用于存放对换页面）。通常，对换区的磁盘I/O速度比文件区要高。例如在UNIX系统中，在文件系统，为了提高文件区存储空间的利用率，系统采用“成组链接表”方式来组织空闲盘块，并采用离散的分配方式；而在对换区，为了提高页面换进换出的速度，采用连续分配方式。每当进程发出缺页请求时，系统应从何处将缺页调入内存呢？在UNIX系统中，对于从未运行过的页面

55、，都应从硬盘文件区调入；对于曾经运行过而又被换出的页面，可以从对换区调入；对于共享页面，该页面可能已由其它进程调入内存，此时就无须再从对换区调入。 3页面置换算法 （Page Replacement Algorithms） 在进程运行过程中，如果发生缺页，此时内存中又无空闲块时，为了保证进程能正常运行，就必须从内存中调出一页程序或数据送磁盘的对换区。但将哪个页面调出，则须根据一定的页面置换算法来确定。页面置换算法的性能指标：缺页率（ page fault rate ）表示“缺页次数 / 内存访问次数” (比率)或“缺页的平均时间间隔的倒数”。置换算法的好坏将直接影响系统的性能，不适当的算法可能

56、会导致进程发生“抖动”（Thrashing)。即刚被换出的页很快又被访问，需重新调入，导致系统频繁地更换页面，以致一个进程在运行中把大部分时间花费在完成页面置换的工作上，我们称该进程发生了“抖动”。 从理论上讲，应将那些以后不再被访问的页面换出，或把那些在较长时间内不会再被访问的页面换出。下面介绍几种常用的置换算法。 （1）最佳（Optimal、OPT）置换算法它是一种理想化的算法，性能最好，但在实际上难于实现。即选择那些永不使用的，或者是在最长时间内不再被访问的页面置换出去。但是要确定哪一个页面是未来最长时间内不再被访问的，目前来说是很难估计的，所以该算法通常用来评价其它算法。例：假定系统为

57、某进程分配了三个物理块，并考虑有以下的页面号引用串：7，0，l，2，0，3，0，4，2，3，0，3，2，l，2，0，l，7，0，1。如下图所示，进程运行时先将7，0，1三个页面装入内存。当进程访问页面2时，产生缺页中断，此时OS根据最佳置换算法，页面7将在第18次才被访问，是三页中将最久不被访问的页面，所以被淘汰。接着访问页面0时，发现已在内存中，而不会产生缺页中断，以此类推。从图可以看出，采用最佳置换算法，只发生了6次页面置换，9次缺页中断。最佳（OPT）置换算法-1(2)先进先出（FIFO）置换算法实用的置换算法关键是如何以过去页面走向来预测将来的页面走向，以达到最佳置换算法。FIFO算法

58、认为最先进入内存的页面，其不再使用的可能性比最近调入的页面要大。所以该算法总是淘汰最先进入内存的页面，即选择在内存中驻留时间最久的页面予以淘汰。该算法实现简单，只须把一个进程已调入内存的页面，按先后次序链接成一个队列，并设置一个循环替换指针即可。它是一种最直观的算法，但它性能最差，有Belady异常现象：例如对页面访问序列1 2 3 4 1 2 5 1 2 3 4 5 ，当分配的物理块从3块增加到4块，缺页次数反而增加。 先进先出（FIFO）置换算法-1先进先出（FIFO）置换算法-2Beladys 奇异Belady现象：采用FIFO算法时，如果对一个进程未分配它所要求的全部页面，有时就会出现

59、分配的页面数增多，缺页率反而提高的异常现象。对页面访问序列A B C D A B E A B C D E ，物理块从3块增加到4块，缺页次数增加。 FIFO Illustrating Beladys Anamoly（3）最近最久未使用置换算法 LRU（Least Recently Used）该算法是选择最近最久未使用的页面予以淘汰，这是局部性原理的合理近似，性能接近最佳算法。但由于需要记录页面使用时间的先后关系，硬件开销太大。系统在每个页面设置一个访问字段，用以记录这个页面自上次被访问以来所经历的时间T，当要淘汰一个页面时，选择T最大的页面。但在实现时需要硬件的支持（寄存器或栈）。硬件机构如：

60、一个特殊的栈：把被访问的页面移到栈顶，于是栈底的是最久未使用页面。每个页面设立移位寄存器：被访问时左边最高位置1，定期右移并且最高位补0，于是寄存器数值最小的是最久未使用页面。最近最久未使用置换算法-1最近最久未使用置换算法-2利用LRU置换算法对上例进行页面置换的结果如表32，表中用一个特殊栈来保存当前使用的各个页面的页号，栈中物理块的页号按访问先后次序排序，它是通过硬件二个栈的弹出和压入来实现特殊栈的页号变化。当进程访问页面2在内存没有时，页号2从上面压入，从下面挤出页号7。接下进程访问页面0在内存有时，直接在内存访问，物理块中页号0提到最上面，其它的页面2、1仍按原次序排列。可以看出，如