第04章_存储管理(完整)

1、第四章 存 储 管 理n存储器的层次结构存储器的层次结构n程序的装入和链接程序的装入和链接n连续分配式连续分配式n对对 换换 技技 术术n分分 页页 技技 术术n分分 段段 技技 术术n段页式技术段页式技术n虚拟存储器虚拟存储器第四章存储管理n请求分页技术请求分页技术n页面置换算法页面置换算法n内存块的分配和抖动内存块的分配和抖动问题问题n请求分段技术请求分段技术第四章存储管理 4 4.1.1 引言引言4.1.1 存储器的层次结构n在现代计算机系统中，在现代计算机系统中，存储器是信息外理的来源与归存储器是信息外理的来源与归宿，占据重要位置。但是，在现有技术条件下，任何宿，占据重要位置。但是，在

2、现有技术条件下，任何一种存储装置，都无法同时从速度与容量两方面，满一种存储装置，都无法同时从速度与容量两方面，满足用户的需求。实际上它们组成了一个速度由快到慢，足用户的需求。实际上它们组成了一个速度由快到慢，容量由小到大的存储装置层次。容量由小到大的存储装置层次。 4.1.1 存储器的层次结构4.1.2 存储管理的目的1)1)主存的分配和管理：当用户需要内存时主存的分配和管理：当用户需要内存时, ,系统为之分配相应的存储空间；不需要系统为之分配相应的存储空间；不需要时，及时回收，以供其它用户使用。时，及时回收，以供其它用户使用。2)2)存储共享：不仅能使多道程序动态地共存储共享：不仅能使多道程

3、序动态地共享主存，提高主存利用率，最好还能共享主存，提高主存利用率，最好还能共享主存中某个区域的信息。享主存中某个区域的信息。存储管理的目的（续）3) 3) 存储保护：确保多道程序都在各自分配到存存储保护：确保多道程序都在各自分配到存储区域内操作，互不干扰，防止一道程序破储区域内操作，互不干扰，防止一道程序破坏其它作业或系统文件的信息。坏其它作业或系统文件的信息。4) 4) “扩充扩充”主存容量：为用户提供比主存物理主存容量：为用户提供比主存物理空间大得多的地址空间，以至使用户感觉他空间大得多的地址空间，以至使用户感觉他的作业是在这样一个大的存储器中运行。的作业是在这样一个大的存储器中运行。4

4、.2程序的装入和链接4.2 程序的装入和链接 1编译阶段编译阶段 2链接阶段链接阶段 3装入阶段装入阶段 链链接接器器库存储器库存储器模块模块#1模块模块#2模块模块#n装装入入模模块块装装入入程程序序x存存 储储 器器编译程序产生编译程序产生的目标模块的目标模块编译编译链接链接装入装入4.2.1重定位n逻辑地址空间逻辑地址空间n物理地址空间物理地址空间n相对地址相对地址n绝对地址绝对地址4.2.1重定位n逻辑地址空间逻辑地址空间n用户在编辑源程序时，不考虑作业之间用户在编辑源程序时，不考虑作业之间的存储空间分配，而是将其源程序存于的存储空间分配，而是将其源程序存于程序员建立的符号名字空间内。

5、程序员建立的符号名字空间内。n当对源程序进行编译时，把语言的符号当对源程序进行编译时，把语言的符号名转换成计算机的指令和数据串组成的名转换成计算机的指令和数据串组成的目标程序，并用地址代码替换符号地址。目标程序，并用地址代码替换符号地址。4.2.1重定位n逻辑地址空间逻辑地址空间n编译后一个目标程序所限定的地址范围编译后一个目标程序所限定的地址范围称为该作业的逻辑地址空间。称为该作业的逻辑地址空间。n通常，编译程序对一个源程序进行编译通常，编译程序对一个源程序进行编译时总是从零号单元开始为其分配地址。时总是从零号单元开始为其分配地址。逻辑地址空间中的所有地址都是相对起逻辑地址空间中的所有地址都

6、是相对起始地址始地址“0”的，因而，逻辑地址称为的，因而，逻辑地址称为相对地址。相对地址。4.2.1重定位n物理地址空间物理地址空间n物理地址空间是指主存中物理单元的集物理地址空间是指主存中物理单元的集合。这些单元的编号称为物理地址或绝合。这些单元的编号称为物理地址或绝对地址。对地址。逻辑地址空间逻辑地址空间物理地址空间物理地址空间4.2.1重定位n地址重定位地址重定位n为了保证程序的正确运行，必须把程序为了保证程序的正确运行，必须把程序和数据的逻辑地址转换为物理地址，这和数据的逻辑地址转换为物理地址，这一过程称为地址重地位。一过程称为地址重地位。重定位的类型n静态重定位静态重定位n动态重定位

7、动态重定位1. 1. 静态重定位静态重定位 当用户程序被装入内存时，一次当用户程序被装入内存时，一次性实现逻辑地址到物理地址的转换，性实现逻辑地址到物理地址的转换，以后不再转换（一般在装入内存时由以后不再转换（一般在装入内存时由软件完成）软件完成）作业作业i i在执行前一次变址，在执行前一次变址，直到该作业完成退出内存为止。直到该作业完成退出内存为止。2. 2. 动态重定位动态重定位 在程序运行过程中要访问数据时再进在程序运行过程中要访问数据时再进行地址变换。由地址变换机构进行的地址行地址变换。由地址变换机构进行的地址变换，硬件上需要重定位寄存器的支持。变换，硬件上需要重定位寄存器的支持。动态

8、重定位的实现方式n重定位寄存器重定位寄存器：在执行一条指令取操作在执行一条指令取操作数时，要将指令给出的有效地址数时，要将指令给出的有效地址(500)(500)与与重定位寄存器中的内容（重定位寄存器中的内容（10001000）相加，）相加，得访问地址（得访问地址（15001500），从而实现了地址），从而实现了地址动态修改。动态修改。n映象方式映象方式：采用页表来描述虚、实页面采用页表来描述虚、实页面的对应关系的对应关系 。4.2.2程序的链接n链接链接: 将经过编译得到的一组目标模块将经过编译得到的一组目标模块以及它们需要的库函数，装配成一个完以及它们需要的库函数，装配成一个完整的装入模块的

9、操作。整的装入模块的操作。4.2.2程序的链接n根据链接时间的不同，可把链接分成三种根据链接时间的不同，可把链接分成三种: n静态链接静态链接n装入时动态链接装入时动态链接n运行时动态链接运行时动态链接4.2.2程序的链接n静态链接：在程序运行之前事先进行的链接。静态链接：在程序运行之前事先进行的链接。n修改目标模块的相对地址修改目标模块的相对地址n变换外部调用符号变换外部调用符号调用调用B;返回返回调用调用C;返回返回返回返回长度长度L目标模块目标模块模块模块A模块模块B模块模块C0L-1LL+M-1L+ML+M+N-1模模块块A模模块块B模模块块C长度长度M长度长度N调用调用L调用调用L+

10、M加载模块加载模块相对相对地址地址链链接接器器000L-1M-1N-1相对相对地址地址4.2.2程序的链接n装入时动态链接：将编译后的目标模块装入装入时动态链接：将编译后的目标模块装入内存时，采用边装入边链接的方式。内存时，采用边装入边链接的方式。n便于版本的更新便于版本的更新n便于实现目标模块的共享便于实现目标模块的共享4.2.2程序的链接n运行时动态链接：将某些目标模块的链接推运行时动态链接：将某些目标模块的链接推迟到程序执行时再进行。即在程序执行过程迟到程序执行时再进行。即在程序执行过程中，若发现被调用模块尚未装入内存，可以中，若发现被调用模块尚未装入内存，可以找到该模块将它装入内存，并

11、链接到调用模找到该模块将它装入内存，并链接到调用模块上。块上。第4章存储器管理 4.3 单用户系统的存储管理方式 单一连续分配方式n在单道环境下，不管是单用户系统还是单道批处在单道环境下，不管是单用户系统还是单道批处理系统，进程（作业）执行时除了系统占用一部理系统，进程（作业）执行时除了系统占用一部分主存外，剩下的主存区域全部归它占用。主存分主存外，剩下的主存区域全部归它占用。主存可以划分为三部分：可以划分为三部分： 系统区、用户区、空闲区系统区、用户区、空闲区。用户占用区是一个连续的存储区所以又称单一连用户占用区是一个连续的存储区所以又称单一连续区存储管理续区存储管理。n单用户系统在一段时间

12、内，只有一个进程在内存，单用户系统在一段时间内，只有一个进程在内存，故内存分配管理十分简单，内存利用率低。内存故内存分配管理十分简单，内存利用率低。内存分为两个区域，一个供操作系统使用，一个供用分为两个区域，一个供操作系统使用，一个供用户使用户使用用户程序用户程序位于位于RAM中的中的操作系统操作系统0 xFFF.0位于位于ROM中的中的操作系统操作系统用户程序用户程序0ROM中的中的设备驱动程序设备驱动程序用户程序用户程序位于位于RAM中的中的操作系统操作系统0图图 单一连续区存储分配示意图单一连续区存储分配示意图工作流程 单一连续区分配采用静态分配和静态重单一连续区分配采用静态分配和静态重

13、定位方式，亦即作业或进程一旦进入主存，定位方式，亦即作业或进程一旦进入主存，就一直等到它运行结束后才能释放主存。就一直等到它运行结束后才能释放主存。如下图所示的主存分配与回收法。并且由如下图所示的主存分配与回收法。并且由装入程序检查其绝对地址是否超越，即可装入程序检查其绝对地址是否超越，即可达到保护系统的目的。达到保护系统的目的。工作流程(续)单用户系统缺点n不支持多道。不支持多道。n主存利用率不高。主存利用率不高。n程序的运行受主存容量限制。程序的运行受主存容量限制。 4.4 分区分配存储管理方式 分区式管理分区式管理是满足多道程序的最简是满足多道程序的最简单的存储管理方案。它的基本思想是将

14、单的存储管理方案。它的基本思想是将内存划分成若干个连续区域，称为分区。内存划分成若干个连续区域，称为分区。每个分区只能存储一个程序，而且程序每个分区只能存储一个程序，而且程序也只能在它所驻留的分区中运行。也只能在它所驻留的分区中运行。 4.4.1 固定分区存储管理 n 预先把可分配的主存储器空间分割成预先把可分配的主存储器空间分割成若干个连续区域，称为一个分区。每若干个连续区域，称为一个分区。每个分区的大小可以相同也可以不同，个分区的大小可以相同也可以不同，如图所示。但分区大小固定不变，每如图所示。但分区大小固定不变，每个分区装一个且只能装一个作业个分区装一个且只能装一个作业1. 固定分区基本

15、思想n各分区大小相同各分区大小相同n各分区大小不等各分区大小不等 2. 分区大小：OS：OSn如果有一个空闲区如果有一个空闲区, , 则分配给进程则分配给进程n多个输入队列法多个输入队列法n单一输入队列法单一输入队列法3. 存储分配分区分区4分区分区3分区分区2分区分区1操作系统操作系统多个等待队列多个等待队列单个等待队列单个等待队列分区分区4分区分区3分区分区2分区分区1操作系统操作系统图图 固定分区示意图固定分区示意图100K150K300K120K120K300K150K100K135K3.内存分配图 固定分区使用表通过设置内存分配表，内存分配简单通过设置内存分配表，内存分配简单缺点：内

16、存利用率不高缺点：内存利用率不高 4.4.2 可变分区存储管理n 基本思想：内存不是预先划分好的，基本思想：内存不是预先划分好的，而是当进程装入时，根据进程的需求而是当进程装入时，根据进程的需求和内存空间的使用情况来决定是否分和内存空间的使用情况来决定是否分配。若有足够的空间，则按需要分割配。若有足够的空间，则按需要分割一部分分区给该进程；否则令其等待一部分分区给该进程；否则令其等待主存空间主存空间 4.4.2 可变分区存储管理n内存管理：设置内存空闲块表内存管理：设置内存空闲块表记记录了空闲区起始地址和长度录了空闲区起始地址和长度n内存分配：动态分配内存分配：动态分配n内存回收：当某一块归还

17、后，前后空内存回收：当某一块归还后，前后空间合并，修改内存空闲块表间合并，修改内存空闲块表1.分区分配中的数据结构n空闲分区表空闲分区表n空闲分区链空闲分区链图 空闲分区表n空闲分区表空闲分区表1.分区分配中的数据结构n空闲分区链空闲分区链n使用链指针将所有空闲分区链接成一条链。使用链指针将所有空闲分区链接成一条链。状态位状态位分区大小分区大小 2.分区分配算法按空闲块链接的方式不同，可有以下算法：按空闲块链接的方式不同，可有以下算法：n最佳适应法最佳适应法n最坏适应法最坏适应法n首次适应法首次适应法n下次适应法下次适应法1 1) )最佳适应算法最佳适应算法n空闲表以空闲块大小为序，按增量形空

18、闲表以空闲块大小为序，按增量形式排列。接到内存申请时，在空闲块式排列。接到内存申请时，在空闲块表中找到一个不小于请求的最小空闲表中找到一个不小于请求的最小空闲块进行分配块进行分配n为作业选择分区时总是寻找其大小最为作业选择分区时总是寻找其大小最接近于作业所要求的存储区域。接近于作业所要求的存储区域。n特点：用最小空间满足要求特点：用最小空间满足要求2 2) )最坏适应算法最坏适应算法n与最佳适应算法相反，在为作业选择与最佳适应算法相反，在为作业选择存储区域时，总是选择最大的空间，存储区域时，总是选择最大的空间，因此，分割后剩余的空间比较大，便因此，分割后剩余的空间比较大，便于后面的分配。于后面

19、的分配。n缺点：经过若干次分配后，较大的空缺点：经过若干次分配后，较大的空白区都相应减小，当有大的作业申请白区都相应减小，当有大的作业申请空间时，无法满足其要求。空间时，无法满足其要求。 3 3) )首次适应法分配算法首次适应法分配算法n空闲表按位置排列（空闲块地址小，在空闲表按位置排列（空闲块地址小，在表中的序号也小）。表中的序号也小）。n分配内存时，在各空闲分区中查找满足分配内存时，在各空闲分区中查找满足大小要求的可用块。找到第一个可满足大小要求的可用块。找到第一个可满足要求的空闲块就停止查找，并进行分配要求的空闲块就停止查找，并进行分配n若空闲空间全部占用则从空闲表取消该若空闲空间全部占

20、用则从空闲表取消该项，若有剩余，则余下部分仍保留在空项，若有剩余，则余下部分仍保留在空闲表中，并更新分区大小和分区地址闲表中，并更新分区大小和分区地址4 4) )下次适应算法下次适应算法n接到内存申请时，在空闲块表中，上接到内存申请时，在空闲块表中，上次找到的可用分区的下一个空闲分区次找到的可用分区的下一个空闲分区开始查找可满足大小要求的第一个空开始查找可满足大小要求的第一个空闲分区。闲分区。图 分配16 KB内存块之前和之后的内存配置 3.内存分配与回收n内存分配内存分配 3.内存分配与回收n内存回收内存回收4.4.3可重定位分区分配n经过一段时间的分配回收后，内存中存经过一段时间的分配回收

21、后，内存中存在很多很小的空闲块。它们每一个都很在很多很小的空闲块。它们每一个都很小，不足以满足分配要求；但其总和满小，不足以满足分配要求；但其总和满足分配要求。这些空闲块被称为碎片。足分配要求。这些空闲块被称为碎片。n造成存储资源的浪费造成存储资源的浪费1.碎片问题碎片问题n内部碎片与外部碎片内部碎片与外部碎片n在一个分区内部出现的碎片（即被浪费在一个分区内部出现的碎片（即被浪费的空间）称做内部碎片，如固定分区法的空间）称做内部碎片，如固定分区法会产生内部碎片。会产生内部碎片。n在所有分区之外新增的碎片称做外部碎在所有分区之外新增的碎片称做外部碎片片.1.碎片问题碎片问题1.碎片问题碎片问题内

22、部碎片内部碎片1.碎片问题碎片问题外部碎片外部碎片2.紧缩紧缩n移动某些已分配区的内容，使所有进程移动某些已分配区的内容，使所有进程的分区紧挨在一起，而把空闲区留在另的分区紧挨在一起，而把空闲区留在另一端。这种技术称为紧缩（或拼凑）。一端。这种技术称为紧缩（或拼凑）。图 可重定位分区的紧缩n什么时候进行紧缩？有两种方案什么时候进行紧缩？有两种方案n当进程结束、释放所占用的分区时当进程结束、释放所占用的分区时n在分配进程的分区时进行在分配进程的分区时进行2.紧缩紧缩3. 动态重定位动态重定位n动态重定位经常用硬件实现。动态重定位经常用硬件实现。n硬件支持硬件支持n重定位寄存器重定位寄存器4. 可

23、重定位分区法的优缺点可重定位分区法的优缺点n优点优点:可以消除碎片，能够分配更多的分可以消除碎片，能够分配更多的分区，有助于多道程序设计，提高内存的区，有助于多道程序设计，提高内存的利用率。利用率。n缺点缺点：紧缩花费了大量：紧缩花费了大量CPU时间；当进时间；当进程大于整个空闲区时，仍要浪费一定的程大于整个空闲区时，仍要浪费一定的内存；进程的存储区内可能放有从未使内存；进程的存储区内可能放有从未使用的信息；进程之间无法对信息共享。用的信息；进程之间无法对信息共享。4.4.4 存储保护存储保护n为为了防止一道作业有意或无意地破坏操了防止一道作业有意或无意地破坏操作系统或其它作业。一般说来，采用

24、硬作系统或其它作业。一般说来，采用硬件支持，实现有效的存储保护。通常可件支持，实现有效的存储保护。通常可采取采取界限寄存器方式进行保护。界限寄存器方式进行保护。n硬件支持硬件支持n基址寄存器：基址寄存器：存放用户程序在内存的起始存放用户程序在内存的起始地址地址n限长寄存器：限长寄存器：存放用户程序逻辑地址的最存放用户程序逻辑地址的最大范围大范围4.4.4 存储保护存储保护存储保护防止地址越界n60K 60K 访问地址访问地址 =124K =124K，则产生访问则产生访问地址越界中断地址越界中断存储保护防止地址越界n相对地址相对地址 限长寄存器的值，则产生访限长寄存器的值，则产生访问地址越界中断

25、问地址越界中断图 动态重定位的实现过程存储保护防止操作越权 对于允许多个进程共享的存储区对于允许多个进程共享的存储区域，每个进程都有自己的访问权限。域，每个进程都有自己的访问权限。如果一个进程对共享区域的访问违如果一个进程对共享区域的访问违反了权限规定，则发生操作越权，反了权限规定，则发生操作越权，即读写保护。即读写保护。思考n在一个使用交换技术的系统中，按地址在一个使用交换技术的系统中，按地址从低到高排列的空闲内存空间长度是从低到高排列的空闲内存空间长度是10KB, 4KB, 20KB, 18KB, 7KB, 9KB, 12KB, 15KB。对于下列顺序的段请求。对于下列顺序的段请求(1)

26、12KB (2) 10KB (3)15KB (4) 18KB (5) 12KB分别使用首次适配、最佳适配和下次适分别使用首次适配、最佳适配和下次适配算法说明空间的使用情况，并说明对配算法说明空间的使用情况，并说明对暂不能分配情况的处理方法。暂不能分配情况的处理方法。思考n首次适配首次适配n(1) 12KB 2n(2) 10KB 0n(3) 15KB 3n(4) 18KB 失败失败n(5) 12KB 6思考n最佳适配最佳适配n(1) 12KB 6n(2) 10KB 0n(3) 15KB 7n(4) 18KB 3n(5) 12KB 2思考n下次适配下次适配n(1) 12KB 2n(2) 10KB

27、3n(3) 15KB 7n(4) 18KB 失败失败n(5) 12KB 6思考n当出现暂时不能分配情况时，系统可以当出现暂时不能分配情况时，系统可以采用紧凑技术，将内存中的进程移动到采用紧凑技术，将内存中的进程移动到存储器的一端，使夹杂于其间的空闲小存储器的一端，使夹杂于其间的空闲小空间移动到另一端，形成一个较大的可空间移动到另一端，形成一个较大的可用空间，以满足用户的需求。用空间，以满足用户的需求。4.5 对换技术对换技术n多道程序环境下的对换技术多道程序环境下的对换技术n对换空间管理对换空间管理n进程的换进换出进程的换进换出4.5 对对 换换 技技 术术图 对换两个进程4.5 对换技术对换

28、技术n多道程序环境下的对换技术多道程序环境下的对换技术n根据对换对象的特点划分，对换分类根据对换对象的特点划分，对换分类n整体对换整体对换n部分对换部分对换4.5 对换技术对换技术n辅存分为文件区和对换区。辅存分为文件区和对换区。n对换空间管理对换空间管理n分配方式：换出的进程采用连续分配方式分配方式：换出的进程采用连续分配方式n分配算法：最佳、最坏、首次适应、下次适分配算法：最佳、最坏、首次适应、下次适应算法应算法n存储方式：空闲分区表、空闲分区链存储方式：空闲分区表、空闲分区链n回收方式：回收方式：4.5 对换技术对换技术n进程的换进换出进程的换进换出n进程的换出进程的换出n选择处于阻塞状

29、态的进程选择处于阻塞状态的进程n当前无阻塞进程，则选择优先级最低的就绪当前无阻塞进程，则选择优先级最低的就绪进程进程n进程的换入进程的换入n选择就绪挂起进程选择就绪挂起进程4.6分页技术1. 分页技术的引入分页技术的引入n在动态分区的存储空间中，在动态分区的存储空间中， 存在存在“碎碎片片”问题。问题。尽管采用尽管采用“ “紧凑紧凑” ”技术可以解技术可以解决这个问题，但要为移动大量信息花去决这个问题，但要为移动大量信息花去不少的处理机时间，代价较高。不少的处理机时间，代价较高。n分页技术：允许一个进程的存储空间不分页技术：允许一个进程的存储空间不必连续，可以分散地放在各个空闲的内必连续，可以

30、分散地放在各个空闲的内存区域中。解决了碎片，并提高了内存存区域中。解决了碎片，并提高了内存的利用率。的利用率。4.6 分分 页页 技技 术术2. 分页存储管理的实现原理分页存储管理的实现原理n逻辑空间分页逻辑空间分页n把进程的逻辑地址空间划分成若干个大小把进程的逻辑地址空间划分成若干个大小相等的部分，每个部分称为页。相等的部分，每个部分称为页。n每个页有一个编号。从每个页有一个编号。从0 0开始编制页号。开始编制页号。n页内地址是相对于页内地址是相对于0 0编址。编址。4.6 分分 页页 技技 术术0页2页3页4页n-1页1页进程进程1的逻辑地址空间的逻辑地址空间4.6 分分 页页 技技 术术

31、2. 分页存储管理的实现原理分页存储管理的实现原理n内存空间分块内存空间分块n内存按页的大小划分为大小相等的区域，内存按页的大小划分为大小相等的区域，称为内存块称为内存块n每个块有一个编号。从每个块有一个编号。从0 0开始编制块号。开始编制块号。4.6 分分 页页 技技 术术0块2块3块4块m-1块1块内存物理地址空间内存物理地址空间4.6 分分 页页 技技 术术n页面（或块）的大小是由硬件（系统）页面（或块）的大小是由硬件（系统）确定的。确定的。n一般，页面大小应是一般，页面大小应是2的若干次幂的若干次幂 逻辑地址结构逻辑地址结构n对某特定机器，其地址结构是一定的。对某特定机器，其地址结构是

32、一定的。若给定一个逻辑地址空间中的地址为若给定一个逻辑地址空间中的地址为A，页面的大小为页面的大小为L，则页号，则页号P和页内地址和页内地址d可按下式求得：可按下式求得：np = INTA/L , d = A MOD L123456780页长：页长：4B页页0页页1页页20,00,10,20,31,01,11,21,32,0内存分配原则内存分配原则n在为进程分配内存时，以块为单位将在为进程分配内存时，以块为单位将进程中的若干个页分别装入到多个可进程中的若干个页分别装入到多个可以不相邻接的物理块中。以不相邻接的物理块中。图 分页存储管理系统5页进程进程1地址空间地址空间图 分页存储管理系统5页进

33、程进程1地址空间地址空间5页n页表的作用页表的作用是实现从页号到物理块号的是实现从页号到物理块号的地址映射。地址映射。页表页表存储保护（1）利用页表本身进行保护）利用页表本身进行保护（2）设置存取控制位）设置存取控制位页表图 分页存储管理系统n整个系统有一个内存块表。每个内存块整个系统有一个内存块表。每个内存块在内存块表中占一项，表明该块当前空在内存块表中占一项，表明该块当前空闲还是已分出去了。闲还是已分出去了。内存块表内存块表n当把某一个作业按机器确定的大小分页当把某一个作业按机器确定的大小分页后，一般地，总会存在一个作业页不能后，一般地，总会存在一个作业页不能完全占用一个页面，因而产生完全

34、占用一个页面，因而产生内部碎片内部碎片。n页面选择得小页面选择得小n页面选择得大页面选择得大n页面的大小应适中。通常，页面大小是页面的大小应适中。通常，页面大小是2的幂，一般在的幂，一般在512B到到4KB范围内选择。范围内选择。页面大小页面大小3.分页系统中的地址转换4.联想存储器n通常将页表保存在内存中。通常将页表保存在内存中。n带来存取速度下降的矛盾。带来存取速度下降的矛盾。n快表（或快表（或Translation Lookaside Buffer, TLB）。快表每项包括键号和值两部分，）。快表每项包括键号和值两部分，键号是当前进程正在使用的某个页面号，键号是当前进程正在使用的某个页面

35、号，值是该页面所对应的物理块号。值是该页面所对应的物理块号。图 利用快表实现地址转换5.页表的构造多级页表多级页表n大多数现代计算机系统都支持非常大的大多数现代计算机系统都支持非常大的逻辑地址空间，如逻辑地址空间，如232 264。在这种情况。在这种情况下，只用一级页表会使页表变得非常大。下，只用一级页表会使页表变得非常大。n一种方法是利用两级页表，即把页表本一种方法是利用两级页表，即把页表本身也分页。身也分页。 图 两级页表地址结构图5-19 两级页表结构图5-20 两级页表结构的地址转换图5-21 三级页表地址结构反置页表反置页表n按内存块号排序，每个内存块占有一按内存块号排序，每个内存块

36、占有一个表项。每个表项包括存放在该内存个表项。每个表项包括存放在该内存块中页面的虚拟页号和拥有该页面的块中页面的虚拟页号和拥有该页面的进程标识符。进程标识符。反置页表反置页表图 反置页表6.页面共享页面共享6.页面共享页面共享n分页系统中实现页的共享比较困难分页系统中实现页的共享比较困难4.7 虚拟存储器虚拟存储器4.7.1 局部性和虚拟存储器的概念局部性和虚拟存储器的概念n程序的执行过程具有局部性。程序的执行过程具有局部性。n大部分程序结构是顺序的，只有少数部分为大部分程序结构是顺序的，只有少数部分为转移或过程调用转移或过程调用n过程调用一般不超过过程调用一般不超过5层层n程序中存在循环，反

37、复执行程序中存在循环，反复执行n对于数组的处理将局限于较小范围对于数组的处理将局限于较小范围4.7 虚拟存储器虚拟存储器4.7.1 虚拟存储器的概念虚拟存储器的概念n程序局部性原理程序局部性原理n在一段时间内一个程序的执行往往呈现出在一段时间内一个程序的执行往往呈现出高度的局部性，表现在时间与空间两方面高度的局部性，表现在时间与空间两方面n时间局部性时间局部性: :一条指令被执行了，则在不久的一条指令被执行了，则在不久的将来它可能再被执行将来它可能再被执行n空间局部性空间局部性: :若某一存储单元被使用，则在一若某一存储单元被使用，则在一定时间内，与该存储单元相邻的单元可能被定时间内，与该存储

38、单元相邻的单元可能被使用使用4.7 虚拟存储器虚拟存储器4.7.1 虚拟存储器的概念虚拟存储器的概念n考虑只把当前运行需要的部分程序和数据考虑只把当前运行需要的部分程序和数据装入内存，即启动程序，其他部分暂放在装入内存，即启动程序，其他部分暂放在外存上，需要时再调入外存上，需要时再调入n用户编制程序时不必考虑内存容量的限制用户编制程序时不必考虑内存容量的限制n在一定容量的内存中就可同时装入更多的进在一定容量的内存中就可同时装入更多的进程程n虚拟存储器定义：虚拟存储器定义：n虚拟存储器是指具有部分装入和部分虚拟存储器是指具有部分装入和部分对换功能，能从逻辑上对内存容量进对换功能，能从逻辑上对内存

39、容量进行大幅度扩充的一种存储器。行大幅度扩充的一种存储器。4.7.2 虚拟存储器的特征虚拟存储器的特征 离散性。离散性。 多次性。多次性。 对换性。对换性。 虚拟性。虚拟性。 4.8 请求分页存储管理技术请求分页存储管理技术n请求分页存储管理技术是在单纯分页技术请求分页存储管理技术是在单纯分页技术基础上发展起来的，二者的根本区别在于基础上发展起来的，二者的根本区别在于请求分页提供虚拟存储器。请求分页提供虚拟存储器。n基本思想是：当一个进程的部分页面在内基本思想是：当一个进程的部分页面在内存时就可调度它运行；在运行过程中若用存时就可调度它运行；在运行过程中若用到的页面尚未在内存，则把它们动态换入

40、到的页面尚未在内存，则把它们动态换入内存。内存。请求分页存储管理的基本思想请求分页存储管理的基本思想n为了标示进程的页面是否已在内存，在每为了标示进程的页面是否已在内存，在每个页表项中增加一个标志位。个页表项中增加一个标志位。 4.8.1 页表机制页表机制n页表项通常包含下列页表项通常包含下列5种信息：种信息：页号页号物理块号物理块号 状态位状态位访问字段访问字段修改位修改位 外存地址外存地址n状态位：指示该页是否已调入内存状态位：指示该页是否已调入内存n访问字段：记录本页在一段时间内被访问访问字段：记录本页在一段时间内被访问的次数，或本页已有多长时间未被访问。的次数，或本页已有多长时间未被访

41、问。 n修改位：指示该页在调入内存后是否被修修改位：指示该页在调入内存后是否被修改过。改过。n外存地址：指出该页在外存上的地址，供外存地址：指出该页在外存上的地址，供调入该页时使用。调入该页时使用。n需解决的问题：需解决的问题：n页面装入问题页面装入问题n页面所处位置页面所处位置n页面置换策略页面置换策略4.8.2 请求分页存储管理的实现原理请求分页存储管理的实现原理缺缺页页中中断断机机构构请求分页技术的性能请求分页技术的性能n令令p表示缺页中断的概率（表示缺页中断的概率（0p1），简称），简称缺页率，它等于缺页次数与全部访问内存缺页率，它等于缺页次数与全部访问内存次数之比。次数之比。n请求式

42、调度请求式调度n预调式调度预调式调度4.8.3 页面装入策略页面装入策略4.8.4 页面置换算法页面置换算法n页页面面置置换换过过程程页面走向页面走向n“”：若采用的置换算法不合适，：若采用的置换算法不合适，可能出现这样的现象：刚被换出的页可能出现这样的现象：刚被换出的页，很快又被访问，为把它调入而换出，很快又被访问，为把它调入而换出另一页，之后又访问刚被换出的页，另一页，之后又访问刚被换出的页，如此频繁地更换页面。如此频繁地更换页面。n存储访问序列也叫存储访问序列也叫。页面走向页面走向n对于给定的页面大小，仅考虑其页号，不关对于给定的页面大小，仅考虑其页号，不关心完整的地址。心完整的地址。n

43、如果当前对页面如果当前对页面p进行了访问，那么，马上又进行了访问，那么，马上又对该页访问就不会缺页。这样连续出现的同对该页访问就不会缺页。这样连续出现的同一页号就简化为一个页号。一页号就简化为一个页号。 页面走向页面走向 0100，0432，0101，0612，0102，0103，0104，0101，0611，0102，0103，0104，0101，0610，0102，0103，0104，0101，0609，0102，0105n若每页若每页100个字节，则页面走向简化为：个字节，则页面走向简化为： 1，4，1，6，1，6，1，6，1，6，1n一般来说，随着可用块数的增加，缺页数一般来说，随着可

44、用块数的增加，缺页数将减少。将减少。n为说明页面置换算法，统一采用下述为说明页面置换算法，统一采用下述页面走向：页面走向： 7，0，1，2，0，3，0，4，2，3， 0，3，2，1，2，0，1，7，0，1n并且假定每个作业只有三个内存块可并且假定每个作业只有三个内存块可供使用。供使用。4.8.4.1 先进先出法（先进先出法（FIFO）n总是淘汰在内存中停留时间最长的一页，即总是淘汰在内存中停留时间最长的一页，即先进入内存的页，先被换出。先进入内存的页，先被换出。n优点优点:容易理解且方便程序设计。容易理解且方便程序设计。n缺点缺点:n性能并不很好性能并不很好n存在存在Belady异常现象，即缺

45、页率随内存块增异常现象，即缺页率随内存块增加而增加。加而增加。4.8.4.2 最佳置换法（最佳置换法（OPT）n最佳置换算法最佳置换算法（Optimal Replacement, OPT）实质实质：为调入新页面而必须预先淘汰某个老页：为调入新页面而必须预先淘汰某个老页面时，所选择的老页面应在面时，所选择的老页面应在将来不被使用将来不被使用，或者是在最远的将来才被访问，或者是在最远的将来才被访问。 4.8.4.2 最佳置换法（最佳置换法（OPT）OPT算法在实现上有困难算法在实现上有困难4.8.4.2 最佳置换法（最佳置换法（OPT）n通过最佳置换算法可对其他可实现的算法通过最佳置换算法可对其他

46、可实现的算法的性能进行比较的性能进行比较 4.8.4.3 最近最少使用置换法最近最少使用置换法(LRU)n思想：当需要置换一页时，选择在最近一段思想：当需要置换一页时，选择在最近一段时间里最久没有使用过的页面予以淘汰。时间里最久没有使用过的页面予以淘汰。需要硬件开销，实现代价很高需要硬件开销，实现代价很高4.8.4.3 时钟置换法（时钟置换法（Clock）1简单时钟置换法简单时钟置换法4.8.4.3 时钟置换法（时钟置换法（Clock）n2改进的时钟置换法改进的时钟置换法n操作系统为收集有关哪些页面正被使用，操作系统为收集有关哪些页面正被使用，哪些页面没被使用的统计信息，系统为每哪些页面没被使

47、用的统计信息，系统为每个页面设置了引用位和修改位。个页面设置了引用位和修改位。n当启动一个进程时，它的所有页面的引用当启动一个进程时，它的所有页面的引用位和修改位由设置为。位和修改位由设置为。n引用位可在每次时钟中断时清零，以区别引用位可在每次时钟中断时清零，以区别最近没有被访问的页面和被访问的页面。最近没有被访问的页面和被访问的页面。n修改位在页面被修改过后标记为修改位在页面被修改过后标记为1，并不被，并不被时钟中断修改。时钟中断修改。4.8.4.3 时钟置换法（时钟置换法（Clock）n2改进的时钟置换法改进的时钟置换法n当发生缺页时，检查所有的页面并当发生缺页时，检查所有的页面并根据它们

48、当前的引用位和修改位的值，根据它们当前的引用位和修改位的值，将页面分为种情况：将页面分为种情况：最近未访问，没有被修改：最近未访问，没有被修改：最近未访问，已被修改：最近未访问，已被修改：最近被访问，没被修改：最近被访问，没被修改：最近被访问，已被修改：最近被访问，已被修改n内存中的每个页面必定是上述四类中的内存中的每个页面必定是上述四类中的一类。一类。引用位被时钟引用位被时钟中断清零后就中断清零后就成了第类成了第类4.8.4.3 时钟置换法（时钟置换法（Clock）n2改进的时钟置换法改进的时钟置换法n从指针所指示的当前位置开始，从指针所指示的当前位置开始， 扫描循环队扫描循环队列，列， 将

49、所遇到的第一个第类页面作为所选将所遇到的第一个第类页面作为所选中的淘汰页。中的淘汰页。 在第一次扫描期间不改变引用在第一次扫描期间不改变引用位。位。n如果查找一周后未遇到第类页面，如果查找一周后未遇到第类页面， 则开始则开始第二轮扫描，寻找第类页面，将所遇到的第二轮扫描，寻找第类页面，将所遇到的第一个这类页面作为淘汰页。在第二轮扫描第一个这类页面作为淘汰页。在第二轮扫描期间，将所有扫描过的页面的引用位都置期间，将所有扫描过的页面的引用位都置0n如果也未找到第类页面，则将指针返回到如果也未找到第类页面，则将指针返回到开始的位置，并将所有的引用位复开始的位置，并将所有的引用位复0。 然后重然后重复第一步，如果仍失败，必要时再重复第二复第一步，如果仍失败，必要时再重复第二步，此时就一定能找到被淘汰的页。步，此时就一定能找到被淘汰的页。4.9 请求分段存储管理方式请求分段存储管理方式4.9.1 分段存储管理的基本概念分段存储管理的基本概念1分段分段每段都有自己的名字和长度。每段都有自己的名字和长度。2段的地址结构段的地址结构n逻辑地址要用两个成分来表示：段号逻辑地址要用两个成分来表示：段号s和段和段内地址内地址d。图5-26 分段技术地址结构3段表和段表地址寄存器段表和段表地址寄存器n系