《操作系统设计与实现第四章》由会员分享，可在线阅读，更多相关《操作系统设计与实现第四章（103页珍藏版）》请在金锄头文库上搜索。
1、操作系统设计与实现操作系统设计与实现主讲教师：徐战亚主讲教师：徐战亚主讲教师：徐战亚主讲教师：徐战亚Email Email ：第四章第四章 存储器管理存储器管理一、存储器在操作系统中的地位一、存储器在操作系统中的地位是计算机不可缺少的部分，存在的方式也是计算机不可缺少的部分，存在的方式也多种多样。多种多样。 对于操作者、程序设计者、系统开发者对于操作者、程序设计者、系统开发者都希望能拥有无穷大的、高速的、内容不发生都希望能拥有无穷大的、高速的、内容不发生变化的存储器，最根本的还是能以很低的成本变化的存储器，最根本的还是能以很低的成本来使用。来使用。由于技术的原因，我们无法满足我们的由于技术的原
2、因，我们无法满足我们的需求，因此，大部分的计算机都以一种层次结需求，因此，大部分的计算机都以一种层次结构来进行存储器的管理。构来进行存储器的管理。高速、价格昂贵、易失信息的高速、价格昂贵、易失信息的高速、价格昂贵、易失信息的高速、价格昂贵、易失信息的CacheCache一般单位几百一般单位几百一般单位几百一般单位几百KBKB；中速、中等价格、易变化的中速、中等价格、易变化的中速、中等价格、易变化的中速、中等价格、易变化的RAMRAM，一般单位为几百，一般单位为几百，一般单位为几百，一般单位为几百MM；低速、低廉价格、不易丢失信息的磁盘，一般单位为低速、低廉价格、不易丢失信息的磁盘，一般单位为低
3、速、低廉价格、不易丢失信息的磁盘，一般单位为低速、低廉价格、不易丢失信息的磁盘，一般单位为GG；存储存储存储存储器层器层器层器层次结次结次结次结构构构构对于操作系统，它本身提供一个存储管理模块对于操作系统，它本身提供一个存储管理模块对于操作系统，它本身提供一个存储管理模块对于操作系统，它本身提供一个存储管理模块来管理它本身的这个层次性的存储器系统。来管理它本身的这个层次性的存储器系统。来管理它本身的这个层次性的存储器系统。来管理它本身的这个层次性的存储器系统。Memory managerMemory manager 由操作系统协调这些存储器的使用由操作系统协调这些存储器的使用重要性：直接存取要
4、求内存速度尽量快到与重要性：直接存取要求内存速度尽量快到与CPU取指速度相匹配，大到能装下当前运行取指速度相匹配，大到能装下当前运行的程序与数据，否则的程序与数据，否则CPU执行速度就会受到执行速度就会受到内存速度和容量的影响而得不到充分发挥。内存速度和容量的影响而得不到充分发挥。 内存：内存： 是由存储单元（字节或字）组成的一维连续的地址是由存储单元（字节或字）组成的一维连续的地址空间，简称内存空间。用来存放当前正在运行程序的代空间，简称内存空间。用来存放当前正在运行程序的代码及数据，是程序中指令本身地址所指的、亦即程序计码及数据，是程序中指令本身地址所指的、亦即程序计数器所指的存储器。数器
5、所指的存储器。 可以分为：可以分为： 系统区：用于存放操作系统系统区：用于存放操作系统 用户区：用于装入并存放用户程序和数据。用户区：用于装入并存放用户程序和数据。 操作系统存储管理目的操作系统存储管理目的- 用户对内存的使用要求用户对内存的使用要求1、充分利用内存，为多道程序并发执行提供存储基础；、充分利用内存，为多道程序并发执行提供存储基础；2、尽可能方便用户使用：、尽可能方便用户使用： 自动装入用户程序；自动装入用户程序； 用户程序中不必考虑硬件细节；用户程序中不必考虑硬件细节；3、系统能够解决程序空间比实际内存空间大的问题；、系统能够解决程序空间比实际内存空间大的问题；4、程序在执行时
6、可以动态伸缩；、程序在执行时可以动态伸缩；5、内存存取速度快；、内存存取速度快；6、存储保护与安全；、存储保护与安全；7、共享与通信；、共享与通信；8、了解有关资源的使用状况；、了解有关资源的使用状况；9、实现的性能和代价。、实现的性能和代价。操作系统存储管理的任务操作系统存储管理的任务前提前提: 引入多道程序设计技术，满足用户要求引入多道程序设计技术，满足用户要求1. 内存空间的管理、分配与回收内存空间的管理、分配与回收 记录内存的使用情况记录内存的使用情况 设置相应的内存分配表（见下页）设置相应的内存分配表（见下页） （内存分配回收的依据）（内存分配回收的依据） 内存空间划分问题？内存空间
7、划分问题？ 静态或动态，等长或不等长静态或动态，等长或不等长 内存分配表内存分配表 位示图表示法：用一位（位示图表示法：用一位（bit）表示一个空闲页面表示一个空闲页面（0：空闲，：空闲，1：占用）；：占用）；0 0.1 11 10 0.第第第第0 0页第页第页第页第1 1页页页页 第第第第i i页页页页 第第第第n-1n-1页页页页 空闲页面表：包括首页面号和页面个数，连续若空闲页面表：包括首页面号和页面个数，连续若干的页面作为一组登记在表中干的页面作为一组登记在表中 空闲块表：空闲块首址和空闲块长度，没有记录空闲块表：空闲块首址和空闲块长度，没有记录的区域即为进程所占用；的区域即为进程所占
8、用； 空闲块链表：将所有的空闲块链成一个链表。空闲块链表：将所有的空闲块链成一个链表。 确定分配算法确定分配算法 实施内存分配实施内存分配 回收内存回收内存 分配回收方式分配回收方式: 静态分配与动态分配静态分配与动态分配 连续性连续性 ； 离散性离散性 驻留性驻留性 ； 交换性交换性 一次性；一次性； 多次性多次性2. 存储共享存储共享 内存共享：两个或多个进程共用内存中相同区域内存共享：两个或多个进程共用内存中相同区域 目的：目的： 节省内存空间，提高内存利用率节省内存空间，提高内存利用率 实现进程通信（数据共享）实现进程通信（数据共享） 共享内容：共享内容： 代码共享，要求代码为纯代码代
9、码共享，要求代码为纯代码 数据共享数据共享3. 存储保护与安全存储保护与安全 保护目的：保护目的： 为多个程序共享内存提供保障为多个程序共享内存提供保障,使在内存中的各道使在内存中的各道程序程序, 只能访问它自己的区域，避免各道程序间只能访问它自己的区域，避免各道程序间相互干拢，特别是当一道程序发生错误时相互干拢，特别是当一道程序发生错误时, 不致不致于影响其他程序的运行。通常由硬件完成保护功于影响其他程序的运行。通常由硬件完成保护功能，由软件辅助实现。（特权指令不能完成存储能，由软件辅助实现。（特权指令不能完成存储保护。）保护。）存储保护存储保护 保护系统程序区不被用户侵犯保护系统程序区不被
10、用户侵犯; （有意或无意的）（有意或无意的） 不允许用户程序读写不属于自己地址空间的数据不允许用户程序读写不属于自己地址空间的数据; （系统区地址空间，其他用户程序的地址空间）（系统区地址空间，其他用户程序的地址空间）保护过程保护过程-防止地址越防止地址越界界 每个进程都有自己独立的进程空间，如果一个每个进程都有自己独立的进程空间，如果一个进程在运行时所产生的地址在其地址空间之外，则进程在运行时所产生的地址在其地址空间之外，则发生地址越界。即当程序要访问某个内存单元时，发生地址越界。即当程序要访问某个内存单元时，由硬件检查是否允许，如果允许则执行，否则产生由硬件检查是否允许，如果允许则执行，否
11、则产生地址越界中断，由操作系统进行相应处理。地址越界中断，由操作系统进行相应处理。一般由硬件提供一对寄存器：一般由硬件提供一对寄存器： 基址寄存器：存放起始地址基址寄存器：存放起始地址 限长寄存器：存放长度限长寄存器：存放长度 （上界寄存器上界寄存器/下界寄存器）下界寄存器）保护过程保护过程-防止操作越权防止操作越权 对于允许多个进程共享的存储区域，每个进程对于允许多个进程共享的存储区域，每个进程都有自己的访问权限。如果一个进程对共享区域的都有自己的访问权限。如果一个进程对共享区域的访问违反了权限规定，则发生操作越权。访问违反了权限规定，则发生操作越权。 即读写保护。即读写保护。4 .内存内存
12、“扩充扩充” 通过虚拟存储技术实现通过虚拟存储技术实现 用户在编制程序时，不应该受内存容量限制，所用户在编制程序时，不应该受内存容量限制，所以要采用一定技术来以要采用一定技术来扩充扩充内存的容量，使用户得到内存的容量，使用户得到比实际内存容量大的多的内存空间。比实际内存容量大的多的内存空间。内存内存“扩充扩充” 具体实现是在硬件支持下，软硬件相互协作，将具体实现是在硬件支持下，软硬件相互协作，将内存和外存结合起来统一使用。通过这种方法把内内存和外存结合起来统一使用。通过这种方法把内存扩充，使用户在编制程序时不受内存限制。存扩充，使用户在编制程序时不受内存限制。5 . 地址映射（地址重定位，地址
13、变换）地址映射（地址重定位，地址变换）(1) 逻辑地址（相对地址，虚地址）逻辑地址（相对地址，虚地址）(2) 物理地址（绝对地址，实地址）物理地址（绝对地址，实地址）(3) 地址映射地址映射(1)逻辑地址（相对地址，虚地址逻辑地址（相对地址，虚地址） 用户的程序经过汇编或编译后形成目标代码，用户的程序经过汇编或编译后形成目标代码，目标代码通常采用相对地址的形式，其首地址为目标代码通常采用相对地址的形式，其首地址为0，其余指令中的地址都相对于首地址而编址。，其余指令中的地址都相对于首地址而编址。 不能用逻辑地址在内存中读取信息。不能用逻辑地址在内存中读取信息。(2)物理地址（绝对地址，实地址）物
14、理地址（绝对地址，实地址） 内存中存储单元的地址，可直接寻址。内存中存储单元的地址，可直接寻址。(3)地址映射地址映射 为了保证为了保证CPU执行指令时可正确访问存储单元，执行指令时可正确访问存储单元，需将用户程序中的逻辑地址转换为运行时由机器直需将用户程序中的逻辑地址转换为运行时由机器直接寻址的物理地址，这一过程称为地址映射。接寻址的物理地址，这一过程称为地址映射。地址映射地址映射地址映射地址映射BA=1000BA=1000BA=1000BA=1000Load A 200Load A 200Load A 200Load A 200 3456 3456 3456 3456 。 。 。12001
15、20012001200物理地址空间物理地址空间物理地址空间物理地址空间Load A data1Load A data1Load A data1Load A data1data1 3456data1 3456data1 3456data1 3456源程序源程序源程序源程序Load A 200Load A 200Load A 200Load A 200 3456 3456 3456 34560 0 0 0100100100100200200200200编译连接编译连接编译连接编译连接逻辑地址空间逻辑地址空间逻辑地址空间逻辑地址空间0100200300.LOAD A 2003456逻辑地址空间逻辑地
16、址空间110012001300物理地址空间物理地址空间200VR+ +1000BR*重定位和保护重定位和保护 多道程序导致了分区的产生，而分区也导致了多道程序导致了分区的产生，而分区也导致了多道程序导致了分区的产生，而分区也导致了多道程序导致了分区的产生，而分区也导致了新的问题，即程序的重新定位和保护。新的问题，即程序的重新定位和保护。新的问题，即程序的重新定位和保护。新的问题，即程序的重新定位和保护。 如果多个作业都是为某如果多个作业都是为某如果多个作业都是为某如果多个作业都是为某一一一一个程序服务，当主程序个程序服务，当主程序个程序服务，当主程序个程序服务，当主程序调用这些作业的时候，就需
17、要定位到这些作业，保调用这些作业的时候，就需要定位到这些作业，保调用这些作业的时候，就需要定位到这些作业，保调用这些作业的时候，就需要定位到这些作业，保证程序的运行（主函数和分别编译好的子函数）。证程序的运行（主函数和分别编译好的子函数）。证程序的运行（主函数和分别编译好的子函数）。证程序的运行（主函数和分别编译好的子函数）。这时，链接的时候，链接器按照我们的分区机制来这时，链接的时候，链接器按照我们的分区机制来这时，链接的时候，链接器按照我们的分区机制来这时，链接的时候，链接器按照我们的分区机制来定位程序。定位程序。定位程序。定位程序。定位和保护的常见方法：定位和保护的常见方法：定位和保护的
18、常见方法：定位和保护的常见方法： 原因原因: 当程序装入内存时当程序装入内存时, 操作系统要为该程序分操作系统要为该程序分配一个合适的内存空间，由于程序的逻辑地址与配一个合适的内存空间，由于程序的逻辑地址与分配到内存物理地址不一致分配到内存物理地址不一致, 而而CPU执行指令时，执行指令时，是按物理地址进行的，所以要进行地址转换是按物理地址进行的，所以要进行地址转换。静态重定位静态重定位 当用户程序被装入内存时，一次性实现逻辑当用户程序被装入内存时，一次性实现逻辑地址到物理地址的转换，以后不再转换（一般在地址到物理地址的转换，以后不再转换（一般在装入内存时由软件完成）。装入内存时由软件完成）。
19、动态重定位动态重定位 在程序运行过程中要访问数据时再进行地址变在程序运行过程中要访问数据时再进行地址变换（即在逐条指令执行时完成地址映射。一般为了换（即在逐条指令执行时完成地址映射。一般为了提高效率，此工作由硬件地址映射机制来完成。硬提高效率，此工作由硬件地址映射机制来完成。硬件支持，软硬件结合完成）。件支持，软硬件结合完成）。 硬件上需要一对寄存器的支持。硬件上需要一对寄存器的支持。4.1 基本的内存管理基本的内存管理在运行时进程可以在内存和磁盘之间进行移在运行时进程可以在内存和磁盘之间进行移动（交换和分页技术）的系统；动（交换和分页技术）的系统；运行时进程不能够移动的系统，较为简单。运行时
20、进程不能够移动的系统，较为简单。交换和分页技术的目的是由于没有足交换和分页技术的目的是由于没有足够的主存来同时容纳所有的进程而被引入。够的主存来同时容纳所有的进程而被引入。随着硬件的发展，现有的良好的管理方案也随着硬件的发展，现有的良好的管理方案也会可能变成过时的技术而被淘汰。会可能变成过时的技术而被淘汰。4.1.1无交换和分页的单道程序无交换和分页的单道程序 此方案是指同一个时刻和操作系统共享存储器。此方案是指同一个时刻和操作系统共享存储器。此方案是指同一个时刻和操作系统共享存储器。此方案是指同一个时刻和操作系统共享存储器。用户程序用户程序用户程序用户程序位于位于位于位于RAMRAM中的中的
21、中的中的操作系统操作系统操作系统操作系统0xFFF.0xFFF.0 0位于位于位于位于RAMRAM中的中的中的中的操作系统操作系统操作系统操作系统用户程序用户程序用户程序用户程序0 0ROMROM中的中的中的中的设备驱动程序设备驱动程序设备驱动程序设备驱动程序用户程序用户程序用户程序用户程序位于位于位于位于RAMRAM中的中的中的中的操作系统操作系统操作系统操作系统0 0A AB BC C 对于对于对于对于A A图，操作系统位于主存最底部的图，操作系统位于主存最底部的图，操作系统位于主存最底部的图，操作系统位于主存最底部的RAMRAM，即随机存取存储器中，用户程序位于主存的上部。即随机存取存储
22、器中，用户程序位于主存的上部。即随机存取存储器中，用户程序位于主存的上部。即随机存取存储器中，用户程序位于主存的上部。 对于对于对于对于B B图，操作系统位于主存最高端的只读存图，操作系统位于主存最高端的只读存图，操作系统位于主存最高端的只读存图，操作系统位于主存最高端的只读存储器里（储器里（储器里（储器里（ROMROM）, ,（其实本身属于一种映像（其实本身属于一种映像（其实本身属于一种映像（其实本身属于一种映像区域，映像了主板上的基本的输入输出系统）。区域，映像了主板上的基本的输入输出系统）。区域，映像了主板上的基本的输入输出系统）。区域，映像了主板上的基本的输入输出系统）。 对于对于对于
23、对于C C图，设备的驱动程序位于内存最高端的图，设备的驱动程序位于内存最高端的图，设备的驱动程序位于内存最高端的图，设备的驱动程序位于内存最高端的ROMROM中，操作系统的其余部分位于低端的中，操作系统的其余部分位于低端的中，操作系统的其余部分位于低端的中，操作系统的其余部分位于低端的RAMRAM中，中，中，中，中间是用户的应用程序。如中间是用户的应用程序。如中间是用户的应用程序。如中间是用户的应用程序。如MS-DOSMS-DOS系统。系统。系统。系统。 对于对于对于对于IBMIBM操作系统，系统位于操作系统，系统位于操作系统，系统位于操作系统，系统位于ROMROM中的部分即中的部分即中的部分
24、即中的部分即为为为为BIOSBIOS。 对于这种方式，不管是哪一个图，操作对于这种方式，不管是哪一个图，操作系统每次把需要的程序从磁盘复制到存储系统每次把需要的程序从磁盘复制到存储器里并执行，当程序结束时，系统提示结器里并执行，当程序结束时，系统提示结束，当有新的命令时，系统加载新的程序束，当有新的命令时，系统加载新的程序到存储器中，覆盖原来的程序，继续新的到存储器中，覆盖原来的程序，继续新的执行。执行。 可以满足早期一般的小型的操作系统的可以满足早期一般的小型的操作系统的需求，但随着硬件性能的提高，这种方式需求，但随着硬件性能的提高，这种方式逐渐被淘汰。逐渐被淘汰。4.1.2 固定分区的多道
25、程序固定分区的多道程序 对于常见的系统，我们希望能够支持更多的对于常见的系统，我们希望能够支持更多的对于常见的系统，我们希望能够支持更多的对于常见的系统，我们希望能够支持更多的程序，当某个程序处于等待程序，当某个程序处于等待程序，当某个程序处于等待程序，当某个程序处于等待I/OI/O的时候，可以让的时候，可以让的时候，可以让的时候，可以让CPUCPU为别的程序服务，来提高系统整体的性能。为别的程序服务，来提高系统整体的性能。为别的程序服务，来提高系统整体的性能。为别的程序服务，来提高系统整体的性能。 因此可以用划分分区的方法来同时加载多个因此可以用划分分区的方法来同时加载多个因此可以用划分分区
26、的方法来同时加载多个因此可以用划分分区的方法来同时加载多个程序，可以把主存分为几个大小不同的分区，根程序，可以把主存分为几个大小不同的分区，根程序，可以把主存分为几个大小不同的分区，根程序，可以把主存分为几个大小不同的分区，根据程序的不同，来把他们加载到不同的分区中。据程序的不同，来把他们加载到不同的分区中。据程序的不同，来把他们加载到不同的分区中。据程序的不同，来把他们加载到不同的分区中。而同时，程序也可按照单个输入队列的方式进行而同时，程序也可按照单个输入队列的方式进行而同时，程序也可按照单个输入队列的方式进行而同时，程序也可按照单个输入队列的方式进行输入，也可以按照多个输入队列的方式进行
27、输入。输入，也可以按照多个输入队列的方式进行输入。输入，也可以按照多个输入队列的方式进行输入。输入，也可以按照多个输入队列的方式进行输入。分区分区分区分区4 4 4 4分区分区分区分区3 3 3 3分区分区分区分区2 2 2 2分区分区分区分区1 1 1 1操作系统操作系统操作系统操作系统多个输入队列多个输入队列多个输入队列多个输入队列单个输入队列单个输入队列单个输入队列单个输入队列分区分区分区分区4 4 4 4分区分区分区分区3 3 3 3分区分区分区分区2 2 2 2分区分区分区分区1 1 1 1操作系统操作系统操作系统操作系统700K700K700K700K400K400K400K400
28、K100K100K100K100K0 0 0 0 对于左图，由于作业的大小类似的时候，而且对于左图，由于作业的大小类似的时候，而且对于左图，由于作业的大小类似的时候，而且对于左图，由于作业的大小类似的时候，而且众多的作业大小都类似，而此时分区的大小固定，众多的作业大小都类似，而此时分区的大小固定，众多的作业大小都类似，而此时分区的大小固定，众多的作业大小都类似，而此时分区的大小固定，我们该选择合适大小的分区来运行这个作业，这样我们该选择合适大小的分区来运行这个作业，这样我们该选择合适大小的分区来运行这个作业，这样我们该选择合适大小的分区来运行这个作业，这样的话，类似的作业就被分到了一起，而那些
29、与作业的话，类似的作业就被分到了一起，而那些与作业的话，类似的作业就被分到了一起，而那些与作业的话，类似的作业就被分到了一起，而那些与作业的大小不一致的分区，就必然会出现空闲状态，那的大小不一致的分区，就必然会出现空闲状态，那的大小不一致的分区，就必然会出现空闲状态，那的大小不一致的分区，就必然会出现空闲状态，那些分到一起的进程却不得不等待，等待要分到内存些分到一起的进程却不得不等待，等待要分到内存些分到一起的进程却不得不等待，等待要分到内存些分到一起的进程却不得不等待，等待要分到内存空间。忙得忙，闲的闲。空间。忙得忙，闲的闲。空间。忙得忙，闲的闲。空间。忙得忙，闲的闲。如分区一和分区三。如分
30、区一和分区三。如分区一和分区三。如分区一和分区三。 对于右图，所有的作业都被放入一个队列，每对于右图，所有的作业都被放入一个队列，每对于右图，所有的作业都被放入一个队列，每对于右图，所有的作业都被放入一个队列，每次当有分区被释放的时候，就从等待队列中寻找，次当有分区被释放的时候，就从等待队列中寻找，次当有分区被释放的时候，就从等待队列中寻找，次当有分区被释放的时候，就从等待队列中寻找，最适合这个分区大小的进程，这样做是为了避免把最适合这个分区大小的进程，这样做是为了避免把最适合这个分区大小的进程，这样做是为了避免把最适合这个分区大小的进程，这样做是为了避免把大的分区分给那小的作业，免得资源被浪
31、费，但这大的分区分给那小的作业，免得资源被浪费，但这大的分区分给那小的作业，免得资源被浪费，但这大的分区分给那小的作业，免得资源被浪费，但这样却常常把小的作业推到了后面；但对于操作系统，样却常常把小的作业推到了后面；但对于操作系统，样却常常把小的作业推到了后面；但对于操作系统，样却常常把小的作业推到了后面；但对于操作系统，我们做普通的要求就是简单的操作能被最快的反馈我们做普通的要求就是简单的操作能被最快的反馈我们做普通的要求就是简单的操作能被最快的反馈我们做普通的要求就是简单的操作能被最快的反馈给我们，即小的作业能够被最快的处理，因此，为给我们，即小的作业能够被最快的处理，因此，为给我们，即小
32、的作业能够被最快的处理，因此，为给我们，即小的作业能够被最快的处理，因此，为了总能够满足用户的这个要求，一般要专门保证总了总能够满足用户的这个要求，一般要专门保证总了总能够满足用户的这个要求，一般要专门保证总了总能够满足用户的这个要求，一般要专门保证总有一个小的分区，专门来处理那些小的事件、作业，有一个小的分区，专门来处理那些小的事件、作业，有一个小的分区，专门来处理那些小的事件、作业，有一个小的分区，专门来处理那些小的事件、作业，免得被大的作业抢去分区。免得被大的作业抢去分区。免得被大的作业抢去分区。免得被大的作业抢去分区。 或者通过加权来判断作业被推后的次数，到了或者通过加权来判断作业被推
33、后的次数，到了或者通过加权来判断作业被推后的次数，到了或者通过加权来判断作业被推后的次数，到了一定的程度，就不再跳过而是立即执行。一定的程度，就不再跳过而是立即执行。一定的程度，就不再跳过而是立即执行。一定的程度，就不再跳过而是立即执行。4.2 交换交换 固定分区的方案在批处理系统中是种简单高效固定分区的方案在批处理系统中是种简单高效固定分区的方案在批处理系统中是种简单高效固定分区的方案在批处理系统中是种简单高效的方案，每一个作业都在队列中一直到被分配到某的方案，每一个作业都在队列中一直到被分配到某的方案，每一个作业都在队列中一直到被分配到某的方案，每一个作业都在队列中一直到被分配到某个分区，
34、然后被执行完毕。只要能够放入内存，能个分区，然后被执行完毕。只要能够放入内存，能个分区，然后被执行完毕。只要能够放入内存，能个分区，然后被执行完毕。只要能够放入内存，能够使够使够使够使CPU CPU 繁忙，就能满足要求。繁忙，就能满足要求。繁忙，就能满足要求。繁忙，就能满足要求。 但在分时系统中，或者个人的但在分时系统中，或者个人的但在分时系统中，或者个人的但在分时系统中，或者个人的PCPC中，这种方案就中，这种方案就中，这种方案就中，这种方案就不太实际，会常常由于主存不够，需要把进程保存不太实际，会常常由于主存不够，需要把进程保存不太实际，会常常由于主存不够，需要把进程保存不太实际，会常常由
35、于主存不够，需要把进程保存到磁盘，同样的，也需要常常动态地把进程从磁盘到磁盘，同样的，也需要常常动态地把进程从磁盘到磁盘，同样的，也需要常常动态地把进程从磁盘到磁盘，同样的，也需要常常动态地把进程从磁盘调入内存。调入内存。调入内存。调入内存。 这时就需要有新的技术，即交换技术这时就需要有新的技术，即交换技术这时就需要有新的技术，即交换技术这时就需要有新的技术，即交换技术(swapping)(swapping)和虚拟内存技术的引入。和虚拟内存技术的引入。和虚拟内存技术的引入。和虚拟内存技术的引入。OSOSOSOSOSOSAAABBBBCCCCDD ab c d e fOSCDE 进程依次进入，并
36、获得到自己所进程依次进入，并获得到自己所进程依次进入，并获得到自己所进程依次进入，并获得到自己所需要的内存空间，当某个进程执行完需要的内存空间，当某个进程执行完需要的内存空间，当某个进程执行完需要的内存空间，当某个进程执行完毕后便离开，它原来的占用的内存资毕后便离开，它原来的占用的内存资毕后便离开，它原来的占用的内存资毕后便离开，它原来的占用的内存资源便得到释放，当新的进程到来的时源便得到释放，当新的进程到来的时源便得到释放，当新的进程到来的时源便得到释放，当新的进程到来的时候，又可以从这个被释放的空间中划候，又可以从这个被释放的空间中划候，又可以从这个被释放的空间中划候，又可以从这个被释放的
37、空间中划分新的空间，因此主存的利用变得很分新的空间，因此主存的利用变得很分新的空间，因此主存的利用变得很分新的空间，因此主存的利用变得很高效。（理想上的）高效。（理想上的）高效。（理想上的）高效。（理想上的） g 上图中的内存分配与固定分区的不同，上图中的内存分配与固定分区的不同，它是一种可变分区的内存分配，这时内存中它是一种可变分区的内存分配，这时内存中的分区的数目和大小都是在随时随着进程的的分区的数目和大小都是在随时随着进程的变化而变化的。变化而变化的。实际上，内存空间在不断划分的时候，本身实际上，内存空间在不断划分的时候，本身的分布也在变化的越来越复杂，越来越不便的分布也在变化的越来越复
38、杂，越来越不便于管理。于管理。 迫切需要一个机制去整理这个零碎的空迫切需要一个机制去整理这个零碎的空间。即空闲区域的合并间。即空闲区域的合并-内存紧缩。内存紧缩。(低效低效的操作，耗时的操作，耗时)*新的问题新的问题 如果根据进程需要给它分配内存，而且，如果根据进程需要给它分配内存，而且，进程运行的时候大小不再变化，那么分配就进程运行的时候大小不再变化，那么分配就简单，根据需要的大小分配即可；简单，根据需要的大小分配即可； 如果进程运行时，该进程的数据段增如果进程运行时，该进程的数据段增长，就需要分配新的内存，那进程所需的空长，就需要分配新的内存，那进程所需的空间就开始变大，上图中，如果相邻区
39、域是空间就开始变大，上图中，如果相邻区域是空洞，则直接分配给它，但如果是进程时？交洞，则直接分配给它，但如果是进程时？交换，将某一进程移出，但此时内存满了，磁换，将某一进程移出，但此时内存满了，磁盘交换分区也满了，某进程则必须等待或杀盘交换分区也满了，某进程则必须等待或杀死。死。*新问题的解决带来的矛盾：新问题的解决带来的矛盾： 多数的进程都需要动态的空间，且申请新的内存空多数的进程都需要动态的空间，且申请新的内存空多数的进程都需要动态的空间，且申请新的内存空多数的进程都需要动态的空间，且申请新的内存空间，频繁的交换导致大量的进程等待和时间开销。间，频繁的交换导致大量的进程等待和时间开销。间，
40、频繁的交换导致大量的进程等待和时间开销。间，频繁的交换导致大量的进程等待和时间开销。*矛盾的解决矛盾的解决 在每个进程申请空间的时候分配一些多余的内在每个进程申请空间的时候分配一些多余的内在每个进程申请空间的时候分配一些多余的内在每个进程申请空间的时候分配一些多余的内存空间；（存空间；（存空间；（存空间；（A A） 或者对于具有两个可增长数据部分的进程，采或者对于具有两个可增长数据部分的进程，采或者对于具有两个可增长数据部分的进程，采或者对于具有两个可增长数据部分的进程，采用在进程的分区内分开放置的方式管理。（用在进程的分区内分开放置的方式管理。（用在进程的分区内分开放置的方式管理。（用在进程
41、的分区内分开放置的方式管理。（B B）OSOSA AB BA A为增长内存为增长内存为增长内存为增长内存准备的内存准备的内存准备的内存准备的内存实际使用的实际使用的实际使用的实际使用的内存内存内存内存为增长内存为增长内存为增长内存为增长内存准备的内存准备的内存准备的内存准备的内存实际使用的实际使用的实际使用的实际使用的内存内存内存内存OSOSA-PROGA-PROGA-DATAA-DATAA-STACKA-STACKB-DATAB-DATAB-STACKB-STACKB-PROGB-PROGB B为增长内存为增长内存为增长内存为增长内存准备的内存准备的内存准备的内存准备的内存为增长内存为增长内
42、存为增长内存为增长内存准备的内存准备的内存准备的内存准备的内存4.2 .1 使用位图的内存管理使用位图的内存管理 由于操作系统需要对内存进行分配管理和回由于操作系统需要对内存进行分配管理和回由于操作系统需要对内存进行分配管理和回由于操作系统需要对内存进行分配管理和回收，所以，它必须很好地对内存进行跟踪，常用收，所以，它必须很好地对内存进行跟踪，常用收，所以，它必须很好地对内存进行跟踪，常用收，所以，它必须很好地对内存进行跟踪，常用的是位图法和自由链表：的是位图法和自由链表：的是位图法和自由链表：的是位图法和自由链表：A AB BC CD DE E(a) 对于位图方法，位图的大小与内存的大小和分
43、配对于位图方法，位图的大小与内存的大小和分配对于位图方法，位图的大小与内存的大小和分配对于位图方法，位图的大小与内存的大小和分配的单位的大小相关，内存不变时，被分配的单个单的单位的大小相关，内存不变时，被分配的单个单的单位的大小相关，内存不变时，被分配的单个单的单位的大小相关，内存不变时，被分配的单个单元越小，则位图就越大。元越小，则位图就越大。元越小，则位图就越大。元越小，则位图就越大。 位图的组织结构简单，便于管理，且占用的内位图的组织结构简单，便于管理，且占用的内位图的组织结构简单，便于管理，且占用的内位图的组织结构简单，便于管理，且占用的内存很小但也有缺陷：定位的速度受限，由于每个位存
44、很小但也有缺陷：定位的速度受限，由于每个位存很小但也有缺陷：定位的速度受限，由于每个位存很小但也有缺陷：定位的速度受限，由于每个位图单元代表一个被分配的单元，所以连续性不强，图单元代表一个被分配的单元，所以连续性不强，图单元代表一个被分配的单元，所以连续性不强，图单元代表一个被分配的单元，所以连续性不强，对于某个需要几个分配单元大小的进程就很难快速对于某个需要几个分配单元大小的进程就很难快速对于某个需要几个分配单元大小的进程就很难快速对于某个需要几个分配单元大小的进程就很难快速在位图中找到这样连续的空间。故实际不很常用。在位图中找到这样连续的空间。故实际不很常用。在位图中找到这样连续的空间。故
45、实际不很常用。在位图中找到这样连续的空间。故实际不很常用。4.2 .2 使用链表的内存管理使用链表的内存管理 这种方法是通过一个链表来管理已经分配的和这种方法是通过一个链表来管理已经分配的和这种方法是通过一个链表来管理已经分配的和这种方法是通过一个链表来管理已经分配的和尚未分配的内存段，通过对链表的维护达到对内存尚未分配的内存段，通过对链表的维护达到对内存尚未分配的内存段，通过对链表的维护达到对内存尚未分配的内存段，通过对链表的维护达到对内存的管理。这里的内存段可以使被某个进程所占用，的管理。这里的内存段可以使被某个进程所占用，的管理。这里的内存段可以使被某个进程所占用，的管理。这里的内存段可
46、以使被某个进程所占用，也可以是个空洞，即尚未分配的区域。也可以是个空洞，即尚未分配的区域。也可以是个空洞，即尚未分配的区域。也可以是个空洞，即尚未分配的区域。 表的内容包括段的性质、开始地址、长度、长表的内容包括段的性质、开始地址、长度、长表的内容包括段的性质、开始地址、长度、长表的内容包括段的性质、开始地址、长度、长度和指向下一个表项的指针。这是一般，链表的组度和指向下一个表项的指针。这是一般，链表的组度和指向下一个表项的指针。这是一般，链表的组度和指向下一个表项的指针。这是一般，链表的组织都按照地址来排列，这样的进程切换会很直观，织都按照地址来排列，这样的进程切换会很直观，织都按照地址来排
47、列，这样的进程切换会很直观，织都按照地址来排列，这样的进程切换会很直观，更有效的方法是采用双向链表来记录。更有效的方法是采用双向链表来记录。更有效的方法是采用双向链表来记录。更有效的方法是采用双向链表来记录。 但这时就需要对空洞进行处理。但这时就需要对空洞进行处理。但这时就需要对空洞进行处理。但这时就需要对空洞进行处理。A AB BX XA AX XA AB BB BX XX XA AB B变为变为变为变为变为变为变为变为变为变为变为变为变为变为变为变为（a a）（b b）（c c）（d d）对于某进程对于某进程对于某进程对于某进程X X结束的时候同邻居合并的四种方式结束的时候同邻居合并的四种
48、方式结束的时候同邻居合并的四种方式结束的时候同邻居合并的四种方式 对于这种内存的组织和管理方法，我们需要讨对于这种内存的组织和管理方法，我们需要讨对于这种内存的组织和管理方法，我们需要讨对于这种内存的组织和管理方法，我们需要讨论如何用合理的方法来为新创建的进程和新换进来论如何用合理的方法来为新创建的进程和新换进来论如何用合理的方法来为新创建的进程和新换进来论如何用合理的方法来为新创建的进程和新换进来的进程分配大小：的进程分配大小：的进程分配大小：的进程分配大小：*最简单的分配算法最简单的分配算法最简单的分配算法最简单的分配算法首次适配算法首次适配算法首次适配算法首次适配算法存储管理器沿内存段链
49、表从头开始寻找足够存储管理器沿内存段链表从头开始寻找足够存储管理器沿内存段链表从头开始寻找足够存储管理器沿内存段链表从头开始寻找足够的空间来装载进程，除非找到的这个区域的大小刚的空间来装载进程，除非找到的这个区域的大小刚的空间来装载进程，除非找到的这个区域的大小刚的空间来装载进程，除非找到的这个区域的大小刚好和进程相同，否则就要把这个空间拆为两部分，好和进程相同，否则就要把这个空间拆为两部分，好和进程相同，否则就要把这个空间拆为两部分，好和进程相同，否则就要把这个空间拆为两部分，一部分来装进程，另一部分依然为空。一部分来装进程，另一部分依然为空。一部分来装进程，另一部分依然为空。一部分来装进程
50、，另一部分依然为空。属于快速算法，搜索的开销很小。属于快速算法，搜索的开销很小。属于快速算法，搜索的开销很小。属于快速算法，搜索的开销很小。*首次适配的变形首次适配的变形首次适配的变形首次适配的变形下次适配下次适配下次适配下次适配 工作方式与首次适配相同，区别在于每次搜索工作方式与首次适配相同，区别在于每次搜索工作方式与首次适配相同，区别在于每次搜索工作方式与首次适配相同，区别在于每次搜索完毕后记录当前的位置，下次搜索时从此处开始搜完毕后记录当前的位置，下次搜索时从此处开始搜完毕后记录当前的位置，下次搜索时从此处开始搜完毕后记录当前的位置，下次搜索时从此处开始搜索。索。索。索。*最佳适配算法最
51、佳适配算法最佳适配算法最佳适配算法每次搜索整个链表中最适合该进程大小的内存每次搜索整个链表中最适合该进程大小的内存每次搜索整个链表中最适合该进程大小的内存每次搜索整个链表中最适合该进程大小的内存空间，没有完全相同就寻找次之的；每次都要搜索空间，没有完全相同就寻找次之的；每次都要搜索空间，没有完全相同就寻找次之的；每次都要搜索空间，没有完全相同就寻找次之的；每次都要搜索整个链表故速度很慢，而且每次都可能拆分内存，整个链表故速度很慢，而且每次都可能拆分内存，整个链表故速度很慢，而且每次都可能拆分内存，整个链表故速度很慢，而且每次都可能拆分内存，而且生成的新的内存空间会很小。而且生成的新的内存空间会
52、很小。而且生成的新的内存空间会很小。而且生成的新的内存空间会很小。*放弃最佳适配算法放弃最佳适配算法放弃最佳适配算法放弃最佳适配算法采用最差适配算法采用最差适配算法采用最差适配算法采用最差适配算法采用最差，即每次找最大的内存空间分给进程采用最差，即每次找最大的内存空间分给进程采用最差，即每次找最大的内存空间分给进程采用最差，即每次找最大的内存空间分给进程，这样就不会产生大量的极小的内存空洞，即被分，这样就不会产生大量的极小的内存空洞，即被分，这样就不会产生大量的极小的内存空洞，即被分，这样就不会产生大量的极小的内存空洞，即被分开后剩余的那部分仍然足够大，可以继续被使用。开后剩余的那部分仍然足够
53、大，可以继续被使用。开后剩余的那部分仍然足够大，可以继续被使用。开后剩余的那部分仍然足够大，可以继续被使用。对于这四种算法，都不是很有效的方法，对于这四种算法，都不是很有效的方法，如果把表示进程占用的内存段和表示空闲的如果把表示进程占用的内存段和表示空闲的内存段分开放到两个链表中，这样检索效率内存段分开放到两个链表中，这样检索效率会提高很多，但这样的带来的新的麻烦就是会提高很多，但这样的带来的新的麻烦就是控制过程的复杂化和内存释放过程的延长，控制过程的复杂化和内存释放过程的延长，不得不把释放的内存从一个链表中清除再放不得不把释放的内存从一个链表中清除再放到另一个中去。到另一个中去。*一些改进思
54、路一些改进思路一些改进思路一些改进思路* * 进程和空洞存放在两个链表中，针对最佳适进程和空洞存放在两个链表中，针对最佳适进程和空洞存放在两个链表中，针对最佳适进程和空洞存放在两个链表中，针对最佳适配算法的缺陷，将空洞的组织不按地址，而是按照配算法的缺陷，将空洞的组织不按地址，而是按照配算法的缺陷，将空洞的组织不按地址，而是按照配算法的缺陷，将空洞的组织不按地址，而是按照大小来组织，这样就减小了搜索时的开销。大小来组织，这样就减小了搜索时的开销。大小来组织，这样就减小了搜索时的开销。大小来组织，这样就减小了搜索时的开销。*进程和空洞存放在两个链表中，用空洞本身进程和空洞存放在两个链表中，用空洞
55、本身进程和空洞存放在两个链表中，用空洞本身进程和空洞存放在两个链表中，用空洞本身来存放这个链表，第一个字存放空洞的大小，第二来存放这个链表，第一个字存放空洞的大小，第二来存放这个链表，第一个字存放空洞的大小，第二来存放这个链表，第一个字存放空洞的大小，第二个字存放下一个空洞的地址。个字存放下一个空洞的地址。个字存放下一个空洞的地址。个字存放下一个空洞的地址。*快速适配法，按照常见进程需要的空间大小快速适配法，按照常见进程需要的空间大小快速适配法，按照常见进程需要的空间大小快速适配法，按照常见进程需要的空间大小设置单独的链表，这种算法就根据进程所需空间的设置单独的链表，这种算法就根据进程所需空间
56、的设置单独的链表，这种算法就根据进程所需空间的设置单独的链表，这种算法就根据进程所需空间的大小快速在这些特殊的空洞链表中查找空内存。它大小快速在这些特殊的空洞链表中查找空内存。它大小快速在这些特殊的空洞链表中查找空内存。它大小快速在这些特殊的空洞链表中查找空内存。它需要将所有的空洞进行排序，即进程换出时的空洞需要将所有的空洞进行排序，即进程换出时的空洞需要将所有的空洞进行排序，即进程换出时的空洞需要将所有的空洞进行排序，即进程换出时的空洞合并判断。合并判断。合并判断。合并判断。4.3 虚拟存储器虚拟存储器 交换技术与覆盖技术是交换技术与覆盖技术是交换技术与覆盖技术是交换技术与覆盖技术是在多道环
57、境下扩充内存的在多道环境下扩充内存的在多道环境下扩充内存的在多道环境下扩充内存的方法，用以解决在较小的存储空间中运行较大程序时方法，用以解决在较小的存储空间中运行较大程序时方法，用以解决在较小的存储空间中运行较大程序时方法，用以解决在较小的存储空间中运行较大程序时遇到的矛盾。遇到的矛盾。遇到的矛盾。遇到的矛盾。 覆盖技术主要用在早期的操作系统中；覆盖技术主要用在早期的操作系统中；覆盖技术主要用在早期的操作系统中；覆盖技术主要用在早期的操作系统中； 交换技术被广泛用于小型分时系统中，交换技术交换技术被广泛用于小型分时系统中，交换技术交换技术被广泛用于小型分时系统中，交换技术交换技术被广泛用于小型
58、分时系统中，交换技术的发展导致了虚存技术的出现。的发展导致了虚存技术的出现。的发展导致了虚存技术的出现。的发展导致了虚存技术的出现。交换技术与覆盖技术共同点：交换技术与覆盖技术共同点： 进程的程序和数据主要放在外存，当前需要执行进程的程序和数据主要放在外存，当前需要执行进程的程序和数据主要放在外存，当前需要执行进程的程序和数据主要放在外存，当前需要执行的部分放在内存，内外存之间进行信息交换。的部分放在内存，内外存之间进行信息交换。的部分放在内存，内外存之间进行信息交换。的部分放在内存，内外存之间进行信息交换。 覆盖：一个作业的若干程序段，或几个作业的某些覆盖：一个作业的若干程序段，或几个作业的
59、某些覆盖：一个作业的若干程序段，或几个作业的某些覆盖：一个作业的若干程序段，或几个作业的某些部分共享某一个存储空间。部分共享某一个存储空间。部分共享某一个存储空间。部分共享某一个存储空间。 把程序划分为若干个功能上相对独立的程序段，把程序划分为若干个功能上相对独立的程序段，把程序划分为若干个功能上相对独立的程序段，把程序划分为若干个功能上相对独立的程序段，按照其自身的逻辑结构将那些不会同时执行的程序段按照其自身的逻辑结构将那些不会同时执行的程序段按照其自身的逻辑结构将那些不会同时执行的程序段按照其自身的逻辑结构将那些不会同时执行的程序段共享同一块内存区域。共享同一块内存区域。共享同一块内存区域
60、。共享同一块内存区域。 程序段先保存在磁盘上，当有关程序段的前一部程序段先保存在磁盘上，当有关程序段的前一部程序段先保存在磁盘上，当有关程序段的前一部程序段先保存在磁盘上，当有关程序段的前一部分执行结束，把后续程序段调入内存，覆盖前面的程分执行结束，把后续程序段调入内存，覆盖前面的程分执行结束，把后续程序段调入内存，覆盖前面的程分执行结束，把后续程序段调入内存，覆盖前面的程序段（内存序段（内存序段（内存序段（内存“ “扩大扩大扩大扩大” ”了）。了）。了）。了）。 一般要求作业各模块之间有明确的调用结构，程一般要求作业各模块之间有明确的调用结构，程一般要求作业各模块之间有明确的调用结构，程一般
61、要求作业各模块之间有明确的调用结构，程序员要向系统指明覆盖结构，然后又由操作系统完成序员要向系统指明覆盖结构，然后又由操作系统完成序员要向系统指明覆盖结构，然后又由操作系统完成序员要向系统指明覆盖结构，然后又由操作系统完成自动覆盖。自动覆盖。自动覆盖。自动覆盖。A A8K8KE E4K4KF F10K10KC C10K10KB B8K8KD D12K12K作业作业作业作业X X的调用结构的调用结构的调用结构的调用结构作业作业作业作业X X X X的常驻区的常驻区的常驻区的常驻区 A A A A（8K8K8K8K）覆盖区覆盖区覆盖区覆盖区0 0（10K10K）覆盖区覆盖区覆盖区覆盖区1 1（12
62、K12K）B BC C C CD DE EF F缺点：对用户不透明，增加了用户负担。缺点：对用户不透明，增加了用户负担。缺点：对用户不透明，增加了用户负担。缺点：对用户不透明，增加了用户负担。 例子：目前这一技术用于小型系统中的系统程例子：目前这一技术用于小型系统中的系统程例子：目前这一技术用于小型系统中的系统程例子：目前这一技术用于小型系统中的系统程序的内存管理上，序的内存管理上，序的内存管理上，序的内存管理上，MS-DOSMS-DOS的启动过程中，多次的启动过程中，多次的启动过程中，多次的启动过程中，多次使用覆盖技术；启动之后，用户程序区使用覆盖技术；启动之后，用户程序区使用覆盖技术；启动
63、之后，用户程序区使用覆盖技术；启动之后，用户程序区TPATPA的高的高的高的高端部分与端部分与端部分与端部分与COMMAND.COMCOMMAND.COM暂驻模块也是一种覆暂驻模块也是一种覆暂驻模块也是一种覆暂驻模块也是一种覆盖结构。盖结构。盖结构。盖结构。虚拟存储器的基本思想是：虚拟存储器的基本思想是：虚拟存储器的基本思想是：虚拟存储器的基本思想是： 程序、数据、堆栈的大小可以超过内存的大小，程序、数据、堆栈的大小可以超过内存的大小，程序、数据、堆栈的大小可以超过内存的大小，程序、数据、堆栈的大小可以超过内存的大小，操作系统把程序当前使用的部分保留在内存，而把操作系统把程序当前使用的部分保留
64、在内存，而把操作系统把程序当前使用的部分保留在内存，而把操作系统把程序当前使用的部分保留在内存，而把其它部分保存在磁盘上，并在需要时在内存和磁盘其它部分保存在磁盘上，并在需要时在内存和磁盘其它部分保存在磁盘上，并在需要时在内存和磁盘其它部分保存在磁盘上，并在需要时在内存和磁盘之间动态交换。之间动态交换。之间动态交换。之间动态交换。 虚拟存储器支持多道程序设计技术。虚拟存储器支持多道程序设计技术。虚拟存储器支持多道程序设计技术。虚拟存储器支持多道程序设计技术。虚存：虚存： 把内存与外存有机的结合起来使用，把内存与外存有机的结合起来使用，从而得到一个容量很大的从而得到一个容量很大的“内存内存”，这
65、就，这就是虚存。是虚存。实现思想：实现思想： 当进程运行时，先将一部分程序装入当进程运行时，先将一部分程序装入内存，另一部分暂时留在外存，当要执行内存，另一部分暂时留在外存，当要执行的指令不在内存时，由系统自动完成将它的指令不在内存时，由系统自动完成将它们从外存调入内存工作们从外存调入内存工作。4.3.1 分页分页 虚拟存储器常用的技术，在这种虚拟存储器虚拟存储器常用的技术，在这种虚拟存储器虚拟存储器常用的技术，在这种虚拟存储器虚拟存储器常用的技术，在这种虚拟存储器系统中，内存管理单元负责地址的计算和重新定系统中，内存管理单元负责地址的计算和重新定系统中，内存管理单元负责地址的计算和重新定系统
66、中，内存管理单元负责地址的计算和重新定位。它是一组或一个芯片，完成地址映射的功能。位。它是一组或一个芯片，完成地址映射的功能。位。它是一组或一个芯片，完成地址映射的功能。位。它是一组或一个芯片，完成地址映射的功能。CPUCPUCPUCPUMMUMMUMMUMMU内存内存内存内存磁盘磁盘磁盘磁盘控制器控制器控制器控制器总线总线MMUMMUMMUMMU把物理地址送给存储器把物理地址送给存储器把物理地址送给存储器把物理地址送给存储器CPUCPUCPUCPU把虚拟地址送给把虚拟地址送给把虚拟地址送给把虚拟地址送给MMUMMUMMUMMU内存管内存管内存管内存管理单元理单元理单元理单元X X60K-64
67、K60K-64KX X56K-60K56K-60KX X52K-56K52K-56KX X48K-52K48K-52K7 744K-48K44K-48KX X40K-44K40K-44K5 536K-40K36K-40KX X32K-36K32K-36KX X28K-32K28K-32KX X24K-28K24K-28K3 320K-24K20K-24K4 416K-20K16K-20K0 012K-16K12K-16K6 6 8K-12K 8K-12K1 1 4K-8K 4K-8K2 2 0K-4K 0K-4KX XX X3 34 40 06 61 12 228K-32K28K-32K24K
68、-28K24K-28K20K-24K20K-24K16K-20K16K-20K12K-16K12K-16K 8K-12K 8K-12K 4K-8K 4K-8K 0K-4K 0K-4K虚地址空间虚地址空间虚地址空间虚地址空间物理地址空间物理地址空间物理地址空间物理地址空间 虚页虚页虚页虚页页框页框页框页框虚地址中虚地址中虚地址中虚地址中称作页称作页称作页称作页物理地址中物理地址中物理地址中物理地址中称作页框称作页框称作页框称作页框程序程序程序程序 MOV REG , 0MOV REG , 0MMUMMUMOV REG,8192MOV REG,8192MMUMMUMOV REG,224576MOV
69、 REG,224576MOV REG,8192MOV REG,8192*隐含的问题：隐含的问题：隐含的问题：隐含的问题： 程序不知道实际的存储器的大小，由于页和页框程序不知道实际的存储器的大小，由于页和页框程序不知道实际的存储器的大小，由于页和页框程序不知道实际的存储器的大小，由于页和页框的大小一样，则必然有些程序中的地址是没有经过的大小一样，则必然有些程序中的地址是没有经过的大小一样，则必然有些程序中的地址是没有经过的大小一样，则必然有些程序中的地址是没有经过映射的，即虚拟存储器中有空页，他没有和实际的映射的，即虚拟存储器中有空页，他没有和实际的映射的，即虚拟存储器中有空页，他没有和实际的映
70、射的，即虚拟存储器中有空页，他没有和实际的物理内存对应起来。虚页是否被对应了都专门有一物理内存对应起来。虚页是否被对应了都专门有一物理内存对应起来。虚页是否被对应了都专门有一物理内存对应起来。虚页是否被对应了都专门有一位来存储这个信息。位来存储这个信息。位来存储这个信息。位来存储这个信息。如：如：如：如：MOV REG,32780MOV REG,32780这时会发现在虚页这时会发现在虚页这时会发现在虚页这时会发现在虚页8 8里没有对应的物理地址，这是里没有对应的物理地址，这是里没有对应的物理地址，这是里没有对应的物理地址，这是MMUMMU就无法处理此时的问题。这是的故障就叫做缺就无法处理此时的
71、问题。这是的故障就叫做缺就无法处理此时的问题。这是的故障就叫做缺就无法处理此时的问题。这是的故障就叫做缺页故障。操作系统需要找到一个页框将其内容一到页故障。操作系统需要找到一个页框将其内容一到页故障。操作系统需要找到一个页框将其内容一到页故障。操作系统需要找到一个页框将其内容一到磁盘，把刚才需要引用的页取到这个页框中，并修磁盘，把刚才需要引用的页取到这个页框中，并修磁盘，把刚才需要引用的页取到这个页框中，并修磁盘，把刚才需要引用的页取到这个页框中，并修改映射，然后重新启动刚才的指令。改映射，然后重新启动刚才的指令。改映射，然后重新启动刚才的指令。改映射，然后重新启动刚才的指令。MMUMMU的内
72、部结构及工作方法的内部结构及工作方法的内部结构及工作方法的内部结构及工作方法0 00 01 10 00 00 00 00 00 00 00 00 00 01 10 00 01 11 10 00 00 00 00 00 00 00 00 00 01 10 00 0110110在在在在/ /不在内存不在内存不在内存不在内存页表页表页表页表虚地址虚地址虚地址虚地址81968196物理地址物理地址物理地址物理地址24580245800000000 015150000000 014140000000 013130000000 012121111111 111110000000 010101011011
73、1 9 90000000 0 8 80000000 0 7 70000000 0 6 60110111 1 5 51001001 1 4 40000001 1 3 31101101 1 2 20010011 1 1 10100101 1 0 02 2 = =16164 42 2 = =4096409612124.3.2 页表页表 （page table） 页表是用来索引页面的，通过判断页表的存页表是用来索引页面的，通过判断页表的存页表是用来索引页面的，通过判断页表的存页表是用来索引页面的，通过判断页表的存在位，判断这个虚页在物理内存中是否有对应的页在位，判断这个虚页在物理内存中是否有对应的页在
74、位，判断这个虚页在物理内存中是否有对应的页在位，判断这个虚页在物理内存中是否有对应的页框，当有的时候，就直接通过页表函数获得实际的框，当有的时候，就直接通过页表函数获得实际的框，当有的时候，就直接通过页表函数获得实际的框，当有的时候，就直接通过页表函数获得实际的物理地址来定位到实际的物理内存，如果没有，就物理地址来定位到实际的物理内存，如果没有，就物理地址来定位到实际的物理内存，如果没有，就物理地址来定位到实际的物理内存，如果没有，就通知操作系统，引发陷入，去找空页框来装入这个通知操作系统，引发陷入，去找空页框来装入这个通知操作系统，引发陷入，去找空页框来装入这个通知操作系统，引发陷入，去找空
75、页框来装入这个虚页。虚页。虚页。虚页。0 00 01 10 00 00 00 00 00 00 00 00 00 01 10 00 02 2 = =16164 42 2 = =409640961212定位页面定位页面定位页面定位页面根据页面，加上偏移地址完成实际的地址定位根据页面，加上偏移地址完成实际的地址定位根据页面，加上偏移地址完成实际的地址定位根据页面，加上偏移地址完成实际的地址定位对于对于对于对于1616位指令系统的一种方案位指令系统的一种方案位指令系统的一种方案位指令系统的一种方案地址映射在实际应用中的问题：地址映射在实际应用中的问题：地址映射在实际应用中的问题：地址映射在实际应用中
76、的问题： 现代计算机的虚地址一般最少都现代计算机的虚地址一般最少都现代计算机的虚地址一般最少都现代计算机的虚地址一般最少都3232位，如果按位，如果按位，如果按位，如果按照页面照页面照页面照页面4K4K来处理，则对此系统来说，就是有来处理，则对此系统来说，就是有来处理，则对此系统来说，就是有来处理，则对此系统来说，就是有 的页面大小，同时又有的页面大小，同时又有的页面大小，同时又有的页面大小，同时又有 个页表记录。而个页表记录。而个页表记录。而个页表记录。而6464位系统的更为庞大位系统的更为庞大位系统的更为庞大位系统的更为庞大. 即问题主要是页表的庞大导致了索引不再高效；即问题主要是页表的庞
77、大导致了索引不再高效；即问题主要是页表的庞大导致了索引不再高效；即问题主要是页表的庞大导致了索引不再高效； 另外，从虚地址到物理地址的映射的频繁执行，另外，从虚地址到物理地址的映射的频繁执行，另外，从虚地址到物理地址的映射的频繁执行，另外，从虚地址到物理地址的映射的频繁执行，现有的庞大页表无法完成快速的查找定位现有的庞大页表无法完成快速的查找定位现有的庞大页表无法完成快速的查找定位现有的庞大页表无法完成快速的查找定位. 即问题是地址映射相应变慢。即问题是地址映射相应变慢。即问题是地址映射相应变慢。即问题是地址映射相应变慢。2 =40962 =409612122 =1048562 =104856
78、2020问题的解决：问题的解决：问题的解决：问题的解决：一、利用硬件配合解决一、利用硬件配合解决一、利用硬件配合解决一、利用硬件配合解决 -CPU-CPU端端端端 将页表装入寄存器中，避免进程运行时访问内存，将页表装入寄存器中，避免进程运行时访问内存，将页表装入寄存器中，避免进程运行时访问内存，将页表装入寄存器中，避免进程运行时访问内存，对页表的检查也直观。但这样当页表大的时候，就要对页表的检查也直观。但这样当页表大的时候，就要对页表的检查也直观。但这样当页表大的时候，就要对页表的检查也直观。但这样当页表大的时候，就要多的硬件寄存器来存放，代价昂贵。每次进程切换时多的硬件寄存器来存放，代价昂贵
79、。每次进程切换时多的硬件寄存器来存放，代价昂贵。每次进程切换时多的硬件寄存器来存放，代价昂贵。每次进程切换时候都要装入内存中的页表，开销也会很大。候都要装入内存中的页表，开销也会很大。候都要装入内存中的页表，开销也会很大。候都要装入内存中的页表，开销也会很大。二、另一种极端，全放入内存二、另一种极端，全放入内存二、另一种极端，全放入内存二、另一种极端，全放入内存 这时的硬件开销就很小，只需要指向页表起始地址这时的硬件开销就很小，只需要指向页表起始地址这时的硬件开销就很小，只需要指向页表起始地址这时的硬件开销就很小，只需要指向页表起始地址的寄存器即可。环境切换时，改变这个寄存器里的东的寄存器即可
80、。环境切换时，改变这个寄存器里的东的寄存器即可。环境切换时，改变这个寄存器里的东的寄存器即可。环境切换时，改变这个寄存器里的东西即可。但缺点是执行每条指令时都要一次或多次访西即可。但缺点是执行每条指令时都要一次或多次访西即可。但缺点是执行每条指令时都要一次或多次访西即可。但缺点是执行每条指令时都要一次或多次访问内存。故很少单纯使用。问内存。故很少单纯使用。问内存。故很少单纯使用。问内存。故很少单纯使用。*多级页多级页多级页多级页表表表表 为了不将庞大的页表全放内存，引入了多级页表为了不将庞大的页表全放内存，引入了多级页表为了不将庞大的页表全放内存，引入了多级页表为了不将庞大的页表全放内存，引入
81、了多级页表技术：技术：技术：技术：对于此例：对于此例：对于此例：对于此例：3232位虚地址分为了位虚地址分为了位虚地址分为了位虚地址分为了1010位的位的位的位的PT1PT1域，域，域，域，1010位的位的位的位的PT2PT2域，每个页的大小是域，每个页的大小是域，每个页的大小是域，每个页的大小是1212位。位。位。位。 每一个进程都拥有自己的页表，即每个进程都可以拥每一个进程都拥有自己的页表，即每个进程都可以拥每一个进程都拥有自己的页表，即每个进程都可以拥每一个进程都拥有自己的页表，即每个进程都可以拥有有有有4G4G的虚存空间。的虚存空间。的虚存空间。的虚存空间。当一个虚地址定位的时候，具体
82、过程如下：当一个虚地址定位的时候，具体过程如下：当一个虚地址定位的时候，具体过程如下：当一个虚地址定位的时候，具体过程如下：1010位位位位1010位位位位1212位位位位虚地址虚地址虚地址虚地址根页表指针根页表指针根页表指针根页表指针帧号帧号帧号帧号偏移量偏移量偏移量偏移量页页页页帧帧帧帧 根页表根页表根页表根页表10241024个个个个PTEPTE 页表页表页表页表10241024个个个个PTEPTE物理内存物理内存物理内存物理内存当用户的页不在主存中，当用户的页不在主存中，当用户的页不在主存中，当用户的页不在主存中，就会发生缺页故障，由操就会发生缺页故障，由操就会发生缺页故障，由操就会发
83、生缺页故障，由操作系统完成换页的工作。作系统完成换页的工作。作系统完成换页的工作。作系统完成换页的工作。*页表分页表分页表分页表分析析析析禁用缓存禁用缓存禁用缓存禁用缓存访问访问访问访问( (引用引用引用引用) )修改修改修改修改保护保护保护保护在在在在/ /不在不在不在不在页框号页框号页框号页框号页框号：具体对应的物理内存的位置页框号：具体对应的物理内存的位置页框号：具体对应的物理内存的位置页框号：具体对应的物理内存的位置在在在在/ /不在位：表示是否会发生缺页不在位：表示是否会发生缺页不在位：表示是否会发生缺页不在位：表示是否会发生缺页保护位：表示这个页所允许的操作保护位：表示这个页所允许
84、的操作保护位：表示这个页所允许的操作保护位：表示这个页所允许的操作 ，表示此页所允许的操作，表示此页所允许的操作，表示此页所允许的操作，表示此页所允许的操作修改位：表示此页被修改的情况（上一次的操作）修改位：表示此页被修改的情况（上一次的操作）修改位：表示此页被修改的情况（上一次的操作）修改位：表示此页被修改的情况（上一次的操作）-dirty bit-dirty bit引用位：此页被访问的情况，页面替换算法的重要依据引用位：此页被访问的情况，页面替换算法的重要依据引用位：此页被访问的情况，页面替换算法的重要依据引用位：此页被访问的情况，页面替换算法的重要依据禁用缓存：特殊使用，保证数据的及时更
85、新禁用缓存：特殊使用，保证数据的及时更新禁用缓存：特殊使用，保证数据的及时更新禁用缓存：特殊使用，保证数据的及时更新4.3.3 TLB-转换后援存储器转换后援存储器 用硬件手段来解决庞大的页表的问题，由于页表用硬件手段来解决庞大的页表的问题，由于页表用硬件手段来解决庞大的页表的问题，由于页表用硬件手段来解决庞大的页表的问题，由于页表使用的不均匀性，小部分页表被大量频繁的使用，另使用的不均匀性，小部分页表被大量频繁的使用，另使用的不均匀性，小部分页表被大量频繁的使用，另使用的不均匀性，小部分页表被大量频繁的使用，另一些则很少被使用，故专门用硬件一些则很少被使用，故专门用硬件一些则很少被使用，故专
86、门用硬件一些则很少被使用，故专门用硬件TLB(TranslationTLB(Translation LookasideLookaside Buffer) Buffer)来存放常用的页号，并不停的保来存放常用的页号，并不停的保来存放常用的页号，并不停的保来存放常用的页号，并不停的保持持持持TLBTLB中页号的更新。中页号的更新。中页号的更新。中页号的更新。工作时，当有虚地址需要转换时，先到工作时，当有虚地址需要转换时，先到工作时，当有虚地址需要转换时，先到工作时，当有虚地址需要转换时，先到TLBTLB中中中中去作判断，如果不在去作判断，如果不在去作判断，如果不在去作判断，如果不在TLBTLB中，
87、就去页表中查询，并在中，就去页表中查询，并在中，就去页表中查询，并在中，就去页表中查询，并在获得后更新获得后更新获得后更新获得后更新TLBTLB中的页号数据，淘汰一个条目，将其中的页号数据，淘汰一个条目，将其中的页号数据，淘汰一个条目，将其中的页号数据，淘汰一个条目，将其信息写回内存中的页表项，把新的条目加入；如果虚信息写回内存中的页表项，把新的条目加入；如果虚信息写回内存中的页表项，把新的条目加入；如果虚信息写回内存中的页表项，把新的条目加入；如果虚页号在页号在页号在页号在TLBTLB中，则判断保护情况，合法就直接取出使中，则判断保护情况，合法就直接取出使中，则判断保护情况，合法就直接取出使
88、中，则判断保护情况，合法就直接取出使用，不用查询页表，不合法时，就出现保护故障。用，不用查询页表，不合法时，就出现保护故障。用，不用查询页表，不合法时，就出现保护故障。用，不用查询页表，不合法时，就出现保护故障。*软件软件TLB管管理理 现代很多大型操作系统的缺页故障不再由现代很多大型操作系统的缺页故障不再由现代很多大型操作系统的缺页故障不再由现代很多大型操作系统的缺页故障不再由MMUMMU处理，而是交给处理，而是交给处理，而是交给处理，而是交给TLBTLB，而，而，而，而TLBTLB也是由操作系统装入的，也是由操作系统装入的，也是由操作系统装入的，也是由操作系统装入的，因此，因此，因此，因此
89、，TLBTLB的缺页故障比的缺页故障比的缺页故障比的缺页故障比MMUMMU的高得多，但通过设的高得多，但通过设的高得多，但通过设的高得多，但通过设置置置置TLBTLB的大小，可以很有效提高页面的命中率，而此的大小，可以很有效提高页面的命中率，而此的大小，可以很有效提高页面的命中率，而此的大小，可以很有效提高页面的命中率，而此时时时时MMUMMU的设计就可以简化很多，从而使的设计就可以简化很多，从而使的设计就可以简化很多，从而使的设计就可以简化很多，从而使CPUCPU可以更可以更可以更可以更好地设计自己所需的其他部件。好地设计自己所需的其他部件。好地设计自己所需的其他部件。好地设计自己所需的其他
90、部件。 并且操作系统可以根据进程的性质，自动预装进并且操作系统可以根据进程的性质，自动预装进并且操作系统可以根据进程的性质，自动预装进并且操作系统可以根据进程的性质，自动预装进程可能需要的页面这样，就是进程的缺页率大大减程可能需要的页面这样，就是进程的缺页率大大减程可能需要的页面这样，就是进程的缺页率大大减程可能需要的页面这样，就是进程的缺页率大大减少。少。少。少。4.3.4 逆向页表逆向页表 若对于若对于若对于若对于6464位计算机，页框如果仍然位计算机，页框如果仍然位计算机，页框如果仍然位计算机，页框如果仍然4K4K，此时页，此时页，此时页，此时页表项就变得更加庞大，不可能去管理好，故用了
91、逆表项就变得更加庞大，不可能去管理好，故用了逆表项就变得更加庞大，不可能去管理好，故用了逆表项就变得更加庞大，不可能去管理好，故用了逆向的思路来处理即每一个物理页框对应了一个页表向的思路来处理即每一个物理页框对应了一个页表向的思路来处理即每一个物理页框对应了一个页表向的思路来处理即每一个物理页框对应了一个页表项，用对应的函数来处理他们之间的关系。节省了项，用对应的函数来处理他们之间的关系。节省了项，用对应的函数来处理他们之间的关系。节省了项，用对应的函数来处理他们之间的关系。节省了大量的物理空间。大量的物理空间。大量的物理空间。大量的物理空间。 弱点是虚地址到实际物理地址转换很困难，不弱点是虚
92、地址到实际物理地址转换很困难，不弱点是虚地址到实际物理地址转换很困难，不弱点是虚地址到实际物理地址转换很困难，不能根据虚地址查物理地址，而是在逆向表中查进程能根据虚地址查物理地址，而是在逆向表中查进程能根据虚地址查物理地址，而是在逆向表中查进程能根据虚地址查物理地址，而是在逆向表中查进程对应的表项。对应的表项。对应的表项。对应的表项。( (散列散列散列散列) )页号页号页号页号偏移量偏移量偏移量偏移量虚地址虚地址虚地址虚地址散列表散列表散列表散列表页号页号页号页号表项表项表项表项链链链链反向页表反向页表反向页表反向页表帧号帧号帧号帧号帧号帧号帧号帧号偏移量偏移量偏移量偏移量实地址实地址实地址实
93、地址4.4 页面替换算法页面替换算法页的置换算法：当发生缺页，而主存中已无空闲页架页的置换算法：当发生缺页，而主存中已无空闲页架时，需选一页淘汰。选取淘汰页的方法叫页的置换算时，需选一页淘汰。选取淘汰页的方法叫页的置换算法。法。抖动：刚被淘汰出去的页，不久又被访问，又需把它抖动：刚被淘汰出去的页，不久又被访问，又需把它调入而将另一页淘汰出去，很可能又把刚调入的或很调入而将另一页淘汰出去，很可能又把刚调入的或很快要用的页淘汰出去了。如此反复更换页面，以至系快要用的页淘汰出去了。如此反复更换页面，以至系统大部分机时花在页面的调度和传输上，系统的实际统大部分机时花在页面的调度和传输上，系统的实际效率
94、很低。这种现象称为效率很低。这种现象称为“抖动抖动”。缺页率：缺页率：f = (缺页次数缺页次数/访问页面总数访问页面总数)%常见的页面置换算法：常见的页面置换算法： 最佳置换算法最佳置换算法 OPT；先进先出置换算法先进先出置换算法FIFO；最近最最近最少使用置换算法少使用置换算法LRU；最近未使用置换算法最近未使用置换算法NUR；工；工作集作集.4.4.1 最佳置换算法最佳置换算法 OPT（Optimum Strategy）基本原则：基本原则： 淘汰在将来再也不被访问，或者是在最远的淘汰在将来再也不被访问，或者是在最远的将来才能被访问的页。将来才能被访问的页。特点：特点： 无法预测作业将用
95、到哪些页！所以此算法是无法预测作业将用到哪些页！所以此算法是无法实现的无法实现的理论上的算法。理论上的算法。例：某进程分配页架数为例：某进程分配页架数为3，其运行期间页面，其运行期间页面访问序列：访问序列：A,B,C,D,A,B,E,A,B,C,D,E，分析分析其按照其按照OPT算法进行页面置换时的缺页情况。算法进行页面置换时的缺页情况。（堆栈式算法）（堆栈式算法）最佳置换算法最佳置换算法OPT页面访问序列页面访问序列页面访问序列页面访问序列A BC D A BEA BCD EA A A A BA A BEEEEBB BA BB EBCD DC D D D EA A BC C+缺页次数缺页次数
96、缺页次数缺页次数=7； 缺页率缺页率缺页率缺页率=7/12=58%4.4.2最近未使用置换算法最近未使用置换算法 （Not used Recently）NUR页表扩充：为每个页面设置两个硬件位页表扩充：为每个页面设置两个硬件位访问位访问位和修改位。和修改位。访问位访问位= 0：该页尚未被访问过：该页尚未被访问过R:读写时设置读写时设置 = 1：该页已经被访问过：该页已经被访问过修改位修改位= 0：该页尚未被修改过：该页尚未被修改过 M:修改时设置修改时设置 = 1：该页已经被修改过：该页已经被修改过基本原则：淘汰最近未使用的页，且希望其在主存逗基本原则：淘汰最近未使用的页，且希望其在主存逗留期
97、间页面内的数据未被修改过！留期间页面内的数据未被修改过！过程：过程：开始时所有页的访问位，修改位都为开始时所有页的访问位，修改位都为0。访问。访问/修改修改时再置时再置1。当选择淘汰页时，当选择淘汰页时，按照按照 访问位访问位 0 0 1 1 的顺序淘汰。的顺序淘汰。 修改位修改位 0 1 0 1周期性地对访问位清零！周期性地对访问位清零！即对应的四类情况为：即对应的四类情况为：即对应的四类情况为：即对应的四类情况为：* *第第第第0 0类：未被访问，没有被修改类：未被访问，没有被修改类：未被访问，没有被修改类：未被访问，没有被修改* *第第第第1 1类：未被访问，已被修改类：未被访问，已被修
98、改类：未被访问，已被修改类：未被访问，已被修改-（由第（由第（由第（由第3 3类产生类产生类产生类产生) )* *第第第第2 2类：已被访问，没有被修改类：已被访问，没有被修改类：已被访问，没有被修改类：已被访问，没有被修改* *第第第第3 3类：被访问，被修改类：被访问，被修改类：被访问，被修改类：被访问，被修改4.4.3 先进先出置换算法先进先出置换算法FIFO (first-in,first-out)基本原则：选择最早进入主存的页面淘汰。基本原则：选择最早进入主存的页面淘汰。理由：最早进入的页面其不再使用的可能性比最近理由：最早进入的页面其不再使用的可能性比最近调入的页面要大。调入的页面
99、要大。实现简单：把进入主存的各页面按进入主存的时间实现简单：把进入主存的各页面按进入主存的时间次序构成队列（链表或表格），总是淘汰队头的页次序构成队列（链表或表格），总是淘汰队头的页面。面。缺点：缺点：只有按照线性顺序访问地址空间时才是理想的，只有按照线性顺序访问地址空间时才是理想的，否则效率不高。否则效率不高。异常现象：对于一些特定的访问序列，随分配页异常现象：对于一些特定的访问序列，随分配页架数增加，缺页频率反而增加！架数增加，缺页频率反而增加！先进先出置换算法先进先出置换算法先进先出置换算法先进先出置换算法FIFOFIFO页面访问序列页面访问序列页面访问序列页面访问序列A A B BC
100、C D D A A B BE EA A B BC C D D E EA A B BC C D D A A B BE EE EE EC C D D D DA A B BC C D D A A B BB BB BE EC C C CA A B BC C D D A A A A A A B BE EE E+ + + + + + + + + +缺页次数缺页次数缺页次数缺页次数= =9 9； 缺页率缺页率缺页率缺页率 f f= =9 9/12=/12=7 75%5%页面访问序列页面访问序列页面访问序列页面访问序列A A B BC C D D A A B BE EA A B BC C D D E EA A
101、 B BC C D D D D D D E EA A B BC C D D E EA A B BC C C C C C D D E EA A B BC C D DA A B BB BB BC C D D E EA A B BC CA A A A A A B BC C D D E EA A B B+ + + + + + + + + + +缺页次数缺页次数缺页次数缺页次数= =1010； 缺页率缺页率缺页率缺页率 f f= =1010/12=/12=8383%4.4.4 第二次机会页面替换算法第二次机会页面替换算法 由于由于由于由于FIFOFIFO会把经常使用的页面换掉，故需要会把经常使用的页面换
102、掉，故需要会把经常使用的页面换掉，故需要会把经常使用的页面换掉，故需要一次改进，对页面的引用位进行检查，来判断这个一次改进，对页面的引用位进行检查，来判断这个一次改进，对页面的引用位进行检查，来判断这个一次改进，对页面的引用位进行检查，来判断这个页的使用情况，如果未被引用，则替换掉此页，如页的使用情况，如果未被引用，则替换掉此页，如页的使用情况，如果未被引用，则替换掉此页，如页的使用情况，如果未被引用，则替换掉此页，如果不为果不为果不为果不为0 0，表示此页被使用过，则清除，表示此页被使用过，则清除，表示此页被使用过，则清除，表示此页被使用过，则清除R R位，并放位，并放位，并放位，并放入队列
103、最后，将它当作新的页面来对待，从而保证入队列最后，将它当作新的页面来对待，从而保证入队列最后，将它当作新的页面来对待，从而保证入队列最后，将它当作新的页面来对待，从而保证了经常使用的页面能够被保持下来。了经常使用的页面能够被保持下来。了经常使用的页面能够被保持下来。了经常使用的页面能够被保持下来。 该算法其实就是查找从上一次检查以来没有引该算法其实就是查找从上一次检查以来没有引该算法其实就是查找从上一次检查以来没有引该算法其实就是查找从上一次检查以来没有引用过的页面，如果都被引用了，它就成了用过的页面，如果都被引用了，它就成了用过的页面，如果都被引用了，它就成了用过的页面，如果都被引用了，它就
104、成了FIFOFIFO算算算算法。法。法。法。A AB BC CD DE EF FGGH H最先加载的页最先加载的页最先加载的页最先加载的页最新加载的页最新加载的页最新加载的页最新加载的页0 03 37 78 81212141415151818B BC CD DE EF FGGH HA A3 37 78 812121414151518182020 当在时间到了当在时间到了当在时间到了当在时间到了 2020的时候，此时发生了页面故障，的时候，此时发生了页面故障，的时候，此时发生了页面故障，的时候，此时发生了页面故障，需要淘汰一个老的页面，首先对需要淘汰一个老的页面，首先对需要淘汰一个老的页面，首先
105、对需要淘汰一个老的页面，首先对A A页面进行判断，如页面进行判断，如页面进行判断，如页面进行判断，如果果果果A A页面的引用位是页面的引用位是页面的引用位是页面的引用位是0 0，则，则，则，则A A就被淘汰出去，要么被直就被淘汰出去，要么被直就被淘汰出去，要么被直就被淘汰出去，要么被直接丢弃，要么被写回硬盘。如果引用位是接丢弃，要么被写回硬盘。如果引用位是接丢弃，要么被写回硬盘。如果引用位是接丢弃，要么被写回硬盘。如果引用位是1 1，A A页面页面页面页面将被放入队列的尾部，同时它的引用位将被清零。将被放入队列的尾部，同时它的引用位将被清零。将被放入队列的尾部，同时它的引用位将被清零。将被放入
106、队列的尾部，同时它的引用位将被清零。4.4.5 时钟页面替换算法时钟页面替换算法 由于第二次机会算法需要在链表中移动页面，由于第二次机会算法需要在链表中移动页面，由于第二次机会算法需要在链表中移动页面，由于第二次机会算法需要在链表中移动页面，导致了不必要的开销，故用时钟页面替换算法来提导致了不必要的开销，故用时钟页面替换算法来提导致了不必要的开销，故用时钟页面替换算法来提导致了不必要的开销，故用时钟页面替换算法来提高效率。高效率。高效率。高效率。A AB BC CD DE EF FGGH HI IJ JK KL L原理同第二次机原理同第二次机原理同第二次机原理同第二次机会算法一样，但会算法一样
107、，但会算法一样，但会算法一样，但只是实现方法不只是实现方法不只是实现方法不只是实现方法不一样而已。一样而已。一样而已。一样而已。4.4.6 最久最少使用页面替换算法最久最少使用页面替换算法(LRU)基本原则：选择最近一段时间内最长时间没有被访基本原则：选择最近一段时间内最长时间没有被访问过的页面淘汰。问过的页面淘汰。基本理由：认为过去一段时间里不曾被访问过的页，基本理由：认为过去一段时间里不曾被访问过的页，在最近的将来也可能不再会被访问。在最近的将来也可能不再会被访问。实现困难：需为每个页设置一个特定单元，记录上实现困难：需为每个页设置一个特定单元，记录上次访问后到现在的时间量次访问后到现在的
108、时间量 t，并选择，并选择 t 最大的页淘最大的页淘汰。无论硬件还是软件实现开销都很大！汰。无论硬件还是软件实现开销都很大！LRULRU的硬件实现：矩阵方法实现的硬件实现：矩阵方法实现的硬件实现：矩阵方法实现的硬件实现：矩阵方法实现页面页面页面页面K K被使用，则将被使用，则将被使用，则将被使用，则将K K行全置行全置行全置行全置1 1，然后，将，然后，将，然后，将，然后，将K K列全置列全置列全置列全置0 0，如果，如果，如果，如果需要淘汰的时候按照行来判断。需要淘汰的时候按照行来判断。需要淘汰的时候按照行来判断。需要淘汰的时候按照行来判断。4.4.7 软件仿真的软件仿真的LRU算法算法 用
109、计数器跟踪每个页面被访问的频繁程度，被访用计数器跟踪每个页面被访问的频繁程度，被访用计数器跟踪每个页面被访问的频繁程度，被访用计数器跟踪每个页面被访问的频繁程度，被访问一次就将计数器累加一次，当发生需要淘汰页面的问一次就将计数器累加一次，当发生需要淘汰页面的问一次就将计数器累加一次，当发生需要淘汰页面的问一次就将计数器累加一次，当发生需要淘汰页面的情况的时候，将计数器值最小的页面淘汰掉即可。情况的时候，将计数器值最小的页面淘汰掉即可。情况的时候，将计数器值最小的页面淘汰掉即可。情况的时候，将计数器值最小的页面淘汰掉即可。即软件的即软件的即软件的即软件的NFU (not frequently u
110、sed) NFU (not frequently used) 算法。算法。算法。算法。弊端：保留了每次的访问信息，会影响到以后的页面弊端：保留了每次的访问信息，会影响到以后的页面弊端：保留了每次的访问信息，会影响到以后的页面弊端：保留了每次的访问信息，会影响到以后的页面的访问信息。的访问信息。的访问信息。的访问信息。改进方案：计数器累加前先右移一位，改进方案：计数器累加前先右移一位，改进方案：计数器累加前先右移一位，改进方案：计数器累加前先右移一位，R R位累加到计位累加到计位累加到计位累加到计数器的前端而不是后端。数器的前端而不是后端。数器的前端而不是后端。数器的前端而不是后端。4.5 分页
111、系统中的设计问题分页系统中的设计问题 如何从整体把握分页模块的设计，各个细节在模如何从整体把握分页模块的设计，各个细节在模如何从整体把握分页模块的设计，各个细节在模如何从整体把握分页模块的设计，各个细节在模型中的重要性和设计需求型中的重要性和设计需求型中的重要性和设计需求型中的重要性和设计需求.4.5.1 工作集模型工作集模型请调策略：根据需求将需要的页面调入内存中的工请调策略：根据需求将需要的页面调入内存中的工请调策略：根据需求将需要的页面调入内存中的工请调策略：根据需求将需要的页面调入内存中的工作方式称为请调；作方式称为请调；作方式称为请调；作方式称为请调；访问局部性：进程对页面访问的局部
112、性，而且对于访问局部性：进程对页面访问的局部性，而且对于访问局部性：进程对页面访问的局部性，而且对于访问局部性：进程对页面访问的局部性，而且对于所有进程都有此特性；所有进程都有此特性；所有进程都有此特性；所有进程都有此特性；工作集：一个进程当前使用的页的集合叫做此进程工作集：一个进程当前使用的页的集合叫做此进程工作集：一个进程当前使用的页的集合叫做此进程工作集：一个进程当前使用的页的集合叫做此进程的工作集。的工作集。的工作集。的工作集。颠簸：进程执行过程当中，一个隔几个指令就发生颠簸：进程执行过程当中，一个隔几个指令就发生颠簸：进程执行过程当中，一个隔几个指令就发生颠簸：进程执行过程当中，一个
113、隔几个指令就发生一次页面故障的程序成为在颠簸。一次页面故障的程序成为在颠簸。一次页面故障的程序成为在颠簸。一次页面故障的程序成为在颠簸。指令执行通常需几个纳秒，读入页面一般需要几十指令执行通常需几个纳秒，读入页面一般需要几十指令执行通常需几个纳秒，读入页面一般需要几十指令执行通常需几个纳秒，读入页面一般需要几十毫秒。毫秒。毫秒。毫秒。进程在换出内存然后又被调入，这样的过程使得系进程在换出内存然后又被调入，这样的过程使得系进程在换出内存然后又被调入，这样的过程使得系进程在换出内存然后又被调入，这样的过程使得系统的性能花费在页面的移动上，由于每次装入的请统的性能花费在页面的移动上，由于每次装入的请
114、统的性能花费在页面的移动上，由于每次装入的请统的性能花费在页面的移动上，由于每次装入的请调策略，使得开始执行的时候程序颠簸很厉害，故调策略，使得开始执行的时候程序颠簸很厉害，故调策略，使得开始执行的时候程序颠簸很厉害，故调策略，使得开始执行的时候程序颠簸很厉害，故利用工作集的方法来解决这个问题。将常用的页作利用工作集的方法来解决这个问题。将常用的页作利用工作集的方法来解决这个问题。将常用的页作利用工作集的方法来解决这个问题。将常用的页作标识，则移出后之保留，进行跟踪，以后再调入的标识，则移出后之保留，进行跟踪，以后再调入的标识，则移出后之保留，进行跟踪，以后再调入的标识，则移出后之保留，进行跟
115、踪，以后再调入的时候，根据这些信息来快速调入，时候，根据这些信息来快速调入，时候，根据这些信息来快速调入，时候，根据这些信息来快速调入，- -预调。预调。预调。预调。4.5.2 局部与全局分配策略局部与全局分配策略 一直讨论的是某一个进程发生缺页故障，而实一直讨论的是某一个进程发生缺页故障，而实一直讨论的是某一个进程发生缺页故障，而实一直讨论的是某一个进程发生缺页故障，而实际上内存中存在的是多个进程的页面，当其中某个际上内存中存在的是多个进程的页面，当其中某个际上内存中存在的是多个进程的页面，当其中某个际上内存中存在的是多个进程的页面，当其中某个进程发生缺页故障的时候，实际的替换应该有很多进程
116、发生缺页故障的时候，实际的替换应该有很多进程发生缺页故障的时候，实际的替换应该有很多进程发生缺页故障的时候，实际的替换应该有很多种方法，即涉及到了对某个进程的页面替换还是对种方法，即涉及到了对某个进程的页面替换还是对种方法，即涉及到了对某个进程的页面替换还是对种方法，即涉及到了对某个进程的页面替换还是对整个内存中页面的替换的问题。整个内存中页面的替换的问题。整个内存中页面的替换的问题。整个内存中页面的替换的问题。 对于某个进程发生了缺页故障，替换页面时只对于某个进程发生了缺页故障，替换页面时只对于某个进程发生了缺页故障，替换页面时只对于某个进程发生了缺页故障，替换页面时只从此进程拥有的页面中淘
117、汰的方法叫做局部页面替从此进程拥有的页面中淘汰的方法叫做局部页面替从此进程拥有的页面中淘汰的方法叫做局部页面替从此进程拥有的页面中淘汰的方法叫做局部页面替换策略（其实对应的是在内存中为每个进程分配了换策略（其实对应的是在内存中为每个进程分配了换策略（其实对应的是在内存中为每个进程分配了换策略（其实对应的是在内存中为每个进程分配了固定的内存片断）；从内存中只关心页面的年龄来固定的内存片断）；从内存中只关心页面的年龄来固定的内存片断）；从内存中只关心页面的年龄来固定的内存片断）；从内存中只关心页面的年龄来进行淘汰的方法叫做全局页面替换策略（其实对应进行淘汰的方法叫做全局页面替换策略（其实对应进行淘
118、汰的方法叫做全局页面替换策略（其实对应进行淘汰的方法叫做全局页面替换策略（其实对应了每个进程的页框数是可以变化的）。了每个进程的页框数是可以变化的）。了每个进程的页框数是可以变化的）。了每个进程的页框数是可以变化的）。OriginalOriginalconfigurationconfigurationLocal page Local page replacementreplacementGlobal page Global page replacementreplacement局部与全局的优劣性的比较：局部与全局的优劣性的比较：局部与全局的优劣性的比较：局部与全局的优劣性的比较：一般来说，全局
119、比局部较优一般来说，全局比局部较优一般来说，全局比局部较优一般来说，全局比局部较优局部：当内存中有空页框的时候，仍然在自己固定的局部：当内存中有空页框的时候，仍然在自己固定的局部：当内存中有空页框的时候，仍然在自己固定的局部：当内存中有空页框的时候，仍然在自己固定的段内替换，会导致很高缺页率；工作集增大，颠簸变段内替换，会导致很高缺页率；工作集增大，颠簸变段内替换，会导致很高缺页率；工作集增大，颠簸变段内替换，会导致很高缺页率；工作集增大，颠簸变大，工作集变小，内存又会被浪费。大，工作集变小，内存又会被浪费。大，工作集变小，内存又会被浪费。大，工作集变小，内存又会被浪费。全局：系统需要不断确定
120、该给不同的进程多少页框，全局：系统需要不断确定该给不同的进程多少页框，全局：系统需要不断确定该给不同的进程多少页框，全局：系统需要不断确定该给不同的进程多少页框，但是由于工作集变化的过快，跟踪年龄位也很难实现。但是由于工作集变化的过快，跟踪年龄位也很难实现。但是由于工作集变化的过快，跟踪年龄位也很难实现。但是由于工作集变化的过快，跟踪年龄位也很难实现。可以定期为当前进程平均分配同等页框，但进程的大可以定期为当前进程平均分配同等页框，但进程的大可以定期为当前进程平均分配同等页框，但进程的大可以定期为当前进程平均分配同等页框，但进程的大小不同，这种分配仍不合理；也可按照进程大小来分小不同，这种分配
121、仍不合理；也可按照进程大小来分小不同，这种分配仍不合理；也可按照进程大小来分小不同，这种分配仍不合理；也可按照进程大小来分配；或者为每个进程规定最小页框数，这样可保证每配；或者为每个进程规定最小页框数，这样可保证每配；或者为每个进程规定最小页框数，这样可保证每配；或者为每个进程规定最小页框数，这样可保证每个进程都可以执行。个进程都可以执行。个进程都可以执行。个进程都可以执行。无论何种方案都是为了减少颠簸，因此有需要将颠簸无论何种方案都是为了减少颠簸，因此有需要将颠簸无论何种方案都是为了减少颠簸，因此有需要将颠簸无论何种方案都是为了减少颠簸，因此有需要将颠簸直接控制，即直接控制，即直接控制，即直
122、接控制，即PFFPFF算法（算法（算法（算法（page fault frequencypage fault frequency）A A表示故障率过高，表示故障率过高，表示故障率过高，表示故障率过高，B B表示故障率过低，过高表示页框太少，表示故障率过低，过高表示页框太少，表示故障率过低，过高表示页框太少，表示故障率过低，过高表示页框太少，需要增加分配；过低表示页框过多，需要减少页框。需要增加分配；过低表示页框过多，需要减少页框。需要增加分配；过低表示页框过多，需要减少页框。需要增加分配；过低表示页框过多，需要减少页框。4.5.3 页面大小页面大小页面大小的选择，会影响内存的利用率。页面大小的选
123、择，会影响内存的利用率。页面大小的选择，会影响内存的利用率。页面大小的选择，会影响内存的利用率。内零头的产生：由于分页存储，且页面有大小，当内零头的产生：由于分页存储，且页面有大小，当内零头的产生：由于分页存储，且页面有大小，当内零头的产生：由于分页存储，且页面有大小，当一个页被写入了数据，就认为此页被使用了，别的一个页被写入了数据，就认为此页被使用了，别的一个页被写入了数据，就认为此页被使用了，别的一个页被写入了数据，就认为此页被使用了，别的进程就不会再来用这个页面，因此，就产生了内零进程就不会再来用这个页面，因此，就产生了内零进程就不会再来用这个页面，因此，就产生了内零进程就不会再来用这个
124、页面，因此，就产生了内零头，且平均大小为头，且平均大小为头，且平均大小为头，且平均大小为 段数段数段数段数 页长页长页长页长/2/2。EgEg：一个程序被分为八个部分执行，每次需要：一个程序被分为八个部分执行，每次需要：一个程序被分为八个部分执行，每次需要：一个程序被分为八个部分执行，每次需要4k4k的内存，则页长为的内存，则页长为的内存，则页长为的内存，则页长为32k32k时，就分配了时，就分配了时，就分配了时，就分配了32k32k，16k16k时时时时就分配了就分配了就分配了就分配了16k16k，4k4k时就分配了时就分配了时就分配了时就分配了4k4k。过大浪费即越。过大浪费即越。过大浪费
125、即越。过大浪费即越大。过小的话，页表就变得庞大，装入时就使大大。过小的话，页表就变得庞大，装入时就使大大。过小的话，页表就变得庞大，装入时就使大大。过小的话，页表就变得庞大，装入时就使大量时间花在了寻道上，每次装入页面就耗费大量量时间花在了寻道上，每次装入页面就耗费大量量时间花在了寻道上，每次装入页面就耗费大量量时间花在了寻道上，每次装入页面就耗费大量的时间。的时间。的时间。的时间。页表大小的选择：页表大小的选择：页表大小的选择：页表大小的选择：设平均进程大小为设平均进程大小为设平均进程大小为设平均进程大小为s s字节，页面大小是字节，页面大小是字节，页面大小是字节，页面大小是p p字节，每个
126、字节，每个字节，每个字节，每个页表项需要页表项需要页表项需要页表项需要e e字节，则进程需要页数大约是字节，则进程需要页数大约是字节，则进程需要页数大约是字节，则进程需要页数大约是s/ps/p，占，占，占，占用的页表空间是用的页表空间是用的页表空间是用的页表空间是se/pse/p，由于内零头的存在，故总的，由于内零头的存在，故总的，由于内零头的存在，故总的，由于内零头的存在，故总的内存开销为：内存开销为：内存开销为：内存开销为：se/pse/pp/2p/2，通过求导，得到，通过求导，得到，通过求导，得到，通过求导，得到 se/p se/p 1/21/20 0 p= 2se p= 2se故根据故
127、根据故根据故根据s s和和和和e e的大小，就可以得到最优页面的大小，的大小，就可以得到最优页面的大小，的大小，就可以得到最优页面的大小，的大小，就可以得到最优页面的大小，但这个大小实际应用中可以调整。但这个大小实际应用中可以调整。但这个大小实际应用中可以调整。但这个大小实际应用中可以调整。2 24.6 分段分段 段式虚拟存储器，允许程序员把存储器看成段式虚拟存储器，允许程序员把存储器看成段式虚拟存储器，允许程序员把存储器看成段式虚拟存储器，允许程序员把存储器看成多个地址空间或段组成，段的大小不等，且是多个地址空间或段组成，段的大小不等，且是多个地址空间或段组成，段的大小不等，且是多个地址空间
128、或段组成，段的大小不等，且是动态变化的，通过分段就把原来的一维性的组动态变化的，通过分段就把原来的一维性的组动态变化的，通过分段就把原来的一维性的组动态变化的，通过分段就把原来的一维性的组织方式改变了，使得数据的组织更加具有逻辑织方式改变了，使得数据的组织更加具有逻辑织方式改变了，使得数据的组织更加具有逻辑织方式改变了，使得数据的组织更加具有逻辑性。性。性。性。 对于一个编译程序，我们用原来组织方法对于一个编译程序，我们用原来组织方法对于一个编译程序，我们用原来组织方法对于一个编译程序，我们用原来组织方法需要在内存中组织数据。需要在内存中组织数据。需要在内存中组织数据。需要在内存中组织数据。当
129、各个部分在当各个部分在当各个部分在当各个部分在一维空间中增一维空间中增一维空间中增一维空间中增长的时候，会长的时候，会长的时候，会长的时候，会进入到邻接块进入到邻接块进入到邻接块进入到邻接块中，而且某一中，而且某一中，而且某一中，而且某一部分会增长迅部分会增长迅部分会增长迅部分会增长迅速，填满自己速，填满自己速，填满自己速，填满自己的空间，而其的空间，而其的空间，而其的空间，而其他部分仍有大他部分仍有大他部分仍有大他部分仍有大量空余空间。量空余空间。量空余空间。量空余空间。这时在机器上提供多个相互独立的地址空间段，这时在机器上提供多个相互独立的地址空间段，这时在机器上提供多个相互独立的地址空间
130、段，这时在机器上提供多个相互独立的地址空间段，且段的长度会动态改变且段的长度会动态改变且段的长度会动态改变且段的长度会动态改变 ，这样就可以将上图改成下，这样就可以将上图改成下，这样就可以将上图改成下，这样就可以将上图改成下图的方式：图的方式：图的方式：图的方式：符号表符号表源正文源正文常量常量语法树语法树调用栈调用栈用户程序划分用户程序划分 按程序自身的逻辑关系划分为若干个程序段，按程序自身的逻辑关系划分为若干个程序段，每个程序段都有一个段名，且有一个段号。段号从每个程序段都有一个段名，且有一个段号。段号从0开始，每一段也从开始，每一段也从0开始编址，段内地址是连续的开始编址，段内地址是连续
131、的。段号段号段号段号 段内地址段内地址段内地址段内地址逻辑地址逻辑地址.0S工作区段工作区段工作区段工作区段BB主程序段主程序段主程序段主程序段MM.0 0E EP P子程序段子程序段子程序段子程序段XX0 0K K.CALL X ECALL X E.CALL Y FCALL Y FCALL A 116CALL A 116数组数组数组数组AA12345.B B0 0S SA A0 0N NY Y0 0L LX X0 0P PMM0 0KK逻辑段号逻辑段号逻辑段号逻辑段号0 01 12 23 34 4作业作业作业作业1 1的地址空间的地址空间的地址空间的地址空间10001000320032005
132、00050006000600080008000P PKKS SL LN N主存主存主存主存K 3200K 3200P 1500P 1500L 6000L 6000N 8000N 8000S 5000S 5000长度长度长度长度 段地址段地址段地址段地址0 01 12 23 34 4操作系统操作系统操作系统操作系统段的特点：段的特点：段的特点：段的特点： 段的长度可以在运行期间进行改变，堆栈段的长度段的长度可以在运行期间进行改变，堆栈段的长度段的长度可以在运行期间进行改变，堆栈段的长度段的长度可以在运行期间进行改变，堆栈段的长度可以随着数据的压入进行增长，数据弹出时也同样减可以随着数据的压入进行
133、增长，数据弹出时也同样减可以随着数据的压入进行增长，数据弹出时也同样减可以随着数据的压入进行增长，数据弹出时也同样减小。小。小。小。 段是逻辑实体，并为程序员所知，段可以容纳一个段是逻辑实体，并为程序员所知，段可以容纳一个段是逻辑实体，并为程序员所知，段可以容纳一个段是逻辑实体，并为程序员所知，段可以容纳一个过程、一个过程或者一些数值变量，但每个段中的数过程、一个过程或者一些数值变量，但每个段中的数过程、一个过程或者一些数值变量，但每个段中的数过程、一个过程或者一些数值变量，但每个段中的数据都相对单一。据都相对单一。据都相对单一。据都相对单一。 段是逻辑实体，每部分的内容都相对单一，因此可段是
134、逻辑实体，每部分的内容都相对单一，因此可段是逻辑实体，每部分的内容都相对单一，因此可段是逻辑实体，每部分的内容都相对单一，因此可以对不同的段进行不同的控制，如，某些段内容只许以对不同的段进行不同的控制，如，某些段内容只许以对不同的段进行不同的控制，如，某些段内容只许以对不同的段进行不同的控制，如，某些段内容只许读，另一部分段内容只许执行等等。因此程序中的错读，另一部分段内容只许执行等等。因此程序中的错读，另一部分段内容只许执行等等。因此程序中的错读，另一部分段内容只许执行等等。因此程序中的错误判断可以通过对段标志的进行。误判断可以通过对段标志的进行。误判断可以通过对段标志的进行。误判断可以通过
135、对段标志的进行。段的特点：段的特点：段的特点：段的特点： 分段便于单独进行编译、链接，也同样便于修改，分段便于单独进行编译、链接，也同样便于修改，分段便于单独进行编译、链接，也同样便于修改，分段便于单独进行编译、链接，也同样便于修改，且重新编译时只需要编译需要修改的过程即可，不相且重新编译时只需要编译需要修改的过程即可，不相且重新编译时只需要编译需要修改的过程即可，不相且重新编译时只需要编译需要修改的过程即可，不相关的过程也不会受到影响，也不要进行重新编译，因关的过程也不会受到影响，也不要进行重新编译，因关的过程也不会受到影响，也不要进行重新编译，因关的过程也不会受到影响，也不要进行重新编译，
136、因此总的开销也会变得很小。此总的开销也会变得很小。此总的开销也会变得很小。此总的开销也会变得很小。 共享库的使用：由于段的实现，可以使多个进程共共享库的使用：由于段的实现，可以使多个进程共共享库的使用：由于段的实现，可以使多个进程共共享库的使用：由于段的实现，可以使多个进程共享同一部分数据或过程，节省了地址空间享同一部分数据或过程，节省了地址空间享同一部分数据或过程，节省了地址空间享同一部分数据或过程，节省了地址空间。4.6.1 纯分段系统的实现纯分段系统的实现 分段和分页的根本差别就是页定长而段非分段和分页的根本差别就是页定长而段非分段和分页的根本差别就是页定长而段非分段和分页的根本差别就是
137、页定长而段非定长，所以系统在运行了一段时间以后，内存定长，所以系统在运行了一段时间以后，内存定长，所以系统在运行了一段时间以后，内存定长，所以系统在运行了一段时间以后，内存便变得混乱，被分为了很多块，有的是段，有便变得混乱，被分为了很多块，有的是段，有便变得混乱，被分为了很多块，有的是段，有便变得混乱，被分为了很多块，有的是段，有的是空洞，我们称这种现象为跳棋盘，由于空的是空洞，我们称这种现象为跳棋盘，由于空的是空洞，我们称这种现象为跳棋盘，由于空的是空洞，我们称这种现象为跳棋盘，由于空洞浪费了内存，故需要通过紧缩来解决。洞浪费了内存，故需要通过紧缩来解决。洞浪费了内存，故需要通过紧缩来解决。
138、洞浪费了内存，故需要通过紧缩来解决。段段段段0 0（4k4k）段段段段1 1（8k8k）段段段段2 2（5k5k）段段段段3 3（8k8k）段段段段4 4（7k7k）段段段段0 0（4k4k）段段段段3 3（8k8k）段段段段4 4（7k7k）段段段段2 2（5k5k）段段段段7 7（5k5k）（3k3k）段段段段0 0（4k4k）段段段段3 3（8k8k）段段段段2 2（5k5k）（3k3k）段段段段7 7（5k5k）段段段段5 5（4k4k）（3k3k）段段段段0 0（4k4k）段段段段2 2（5k5k）（3k3k）（3k3k）（4k4k）段段段段6 6（4k4k）段段段段7 7（5k5k
139、）段段段段5 5（4k4k）段段段段0 0（4k4k）段段段段7 7（5k5k）段段段段2 2（5k5k）段段段段6 6（4k4k）段段段段5 5（4k4k）（10k10k）a ab bc cd de e4.6.2 分段和分页结合分段和分页结合 当段变得大的时候，我们也遇到了分页里的问当段变得大的时候，我们也遇到了分页里的问当段变得大的时候，我们也遇到了分页里的问当段变得大的时候，我们也遇到了分页里的问题，即无法将整个段装入内存，因此也开始把这个题，即无法将整个段装入内存，因此也开始把这个题，即无法将整个段装入内存，因此也开始把这个题，即无法将整个段装入内存，因此也开始把这个段进行分页，每次把
140、真正需要的页调入内存。段进行分页，每次把真正需要的页调入内存。段进行分页，每次把真正需要的页调入内存。段进行分页，每次把真正需要的页调入内存。分页与分段的实例：分页与分段的实例：分页与分段的实例：分页与分段的实例：MULTICSMULTICS为了实现分页和分段的共同的优点：为了实现分页和分段的共同的优点：为了实现分页和分段的共同的优点：为了实现分页和分段的共同的优点：分页：统一的页面大小，只用段的一部分时，并不用分页：统一的页面大小，只用段的一部分时，并不用分页：统一的页面大小，只用段的一部分时，并不用分页：统一的页面大小，只用段的一部分时，并不用全部调入内存；全部调入内存；全部调入内存；全部
141、调入内存；分段：易于编程、模块化、保护和共享。分段：易于编程、模块化、保护和共享。分段：易于编程、模块化、保护和共享。分段：易于编程、模块化、保护和共享。 每个每个每个每个MULTICSMULTICS程序都有一个段表，每个段对程序都有一个段表，每个段对程序都有一个段表，每个段对程序都有一个段表，每个段对应一个页描述符，因为段表可能会很大，所以段表应一个页描述符，因为段表可能会很大，所以段表应一个页描述符，因为段表可能会很大，所以段表应一个页描述符，因为段表可能会很大，所以段表自己也是一个段并被分页，段描述符包含段是否在自己也是一个段并被分页，段描述符包含段是否在自己也是一个段并被分页，段描述符
142、包含段是否在自己也是一个段并被分页，段描述符包含段是否在内存的标志，内存的标志，内存的标志，内存的标志，18189 91 11 1 1 13 33 3页表的主存地址页表的主存地址页表的主存地址页表的主存地址段长度（以页为单位）段长度（以页为单位）段长度（以页为单位）段长度（以页为单位）页长：页长：页长：页长：0 010241024字，字，字，字，1 1 64 64 字字字字0 0本段分页，本段分页，本段分页，本段分页，1 1本段不分页本段不分页本段不分页本段不分页其他位其他位其他位其他位保护位保护位保护位保护位段描述符段描述符段描述符段描述符MULTICSMULTICS的地址由两部分组成：段和
143、段内地址的地址由两部分组成：段和段内地址的地址由两部分组成：段和段内地址的地址由两部分组成：段和段内地址 进行内存访问时，执行的算法是：进行内存访问时，执行的算法是：进行内存访问时，执行的算法是：进行内存访问时，执行的算法是：1.1.由段号找段描述符；由段号找段描述符；由段号找段描述符；由段号找段描述符；2.2.判断段的页表是否在内存中，如果在，就找到位置，判断段的页表是否在内存中，如果在，就找到位置，判断段的页表是否在内存中，如果在，就找到位置，判断段的页表是否在内存中，如果在，就找到位置，如果不在，就发出段故障，如果违反保护要求就发出如果不在，就发出段故障，如果违反保护要求就发出如果不在，
144、就发出段故障，如果违反保护要求就发出如果不在，就发出段故障，如果违反保护要求就发出故障；故障；故障；故障；3.3.检查所请求虚页的页表项，页面不在内存就发出一检查所请求虚页的页表项，页面不在内存就发出一检查所请求虚页的页表项，页面不在内存就发出一检查所请求虚页的页表项，页面不在内存就发出一个页面故障，在就从页表项中取出此页在主存中的起个页面故障，在就从页表项中取出此页在主存中的起个页面故障，在就从页表项中取出此页在主存中的起个页面故障，在就从页表项中取出此页在主存中的起始地址；始地址；始地址；始地址；4.4.将偏移地址加到页的起始地址上得到字主存中的地将偏移地址加到页的起始地址上得到字主存中的地将偏移地址加到页的起始地址上得到字主存中的地将偏移地址加到页的起始地址上得到字主存中的地址；址；址；址；5.5.最后进行读或写操作。最后进行读或写操作。最后进行读或写操作。最后进行读或写操作。
