操作系统设计与实现第四章.ppt

《操作系统设计与实现第四章.ppt》由会员分享，可在线阅读，更多相关《操作系统设计与实现第四章.ppt（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.存储共享存储共享 内存共享：两个或多个进程共用内存中相同区域内存共享：两个或多个进程共用内存中相同区域 目的：目的：节省内存空间，提高内存利用率节省内存空间，提高内存利用率 实现进程通信（数据共享）实现进程通信（数据共享）共享内容：共享内容：代码共享，要求代码为纯代码代码共享，要求代码为纯代码 数据共享数据共享3.存储保

9、护与安全存储保护与安全 保护目的：保护目的：为多个程序共享内存提供保障为多个程序共享内存提供保障,使在内存中的各道使在内存中的各道程序程序,只能访问它自己的区域，避免各道程序间只能访问它自己的区域，避免各道程序间相互干拢，特别是当一道程序发生错误时相互干拢，特别是当一道程序发生错误时,不致不致于影响其他程序的运行。通常由硬件完成保护功于影响其他程序的运行。通常由硬件完成保护功能，由软件辅助实现。（特权指令不能完成存储能，由软件辅助实现。（特权指令不能完成存储保护。）保护。）存储保护存储保护 保护系统程序区不被用户侵犯保护系统程序区不被用户侵犯;（有意或无意的）（有意或无意的）不允许用户程序读写

10、不属于自己地址空间的数据不允许用户程序读写不属于自己地址空间的数据;（系统区地址空间，其他用户程序的地址空间）（系统区地址空间，其他用户程序的地址空间）保护过程保护过程-防止地址越防止地址越界界 每个进程都有自己独立的进程空间，如果一个每个进程都有自己独立的进程空间，如果一个进程在运行时所产生的地址在其地址空间之外，则进程在运行时所产生的地址在其地址空间之外，则发生地址越界。即当程序要访问某个内存单元时，发生地址越界。即当程序要访问某个内存单元时，由硬件检查是否允许，如果允许则执行，否则产生由硬件检查是否允许，如果允许则执行，否则产生地址越界中断，由操作系统进行相应处理。地址越界中断，由操作系

11、统进行相应处理。一般由硬件提供一对寄存器：一般由硬件提供一对寄存器：基址寄存器：存放起始地址基址寄存器：存放起始地址 限长寄存器：存放长度限长寄存器：存放长度（上界寄存器上界寄存器/下界寄存器）下界寄存器）保护过程保护过程-防止操作越权防止操作越权 对于允许多个进程共享的存储区域，每个进程对于允许多个进程共享的存储区域，每个进程都有自己的访问权限。如果一个进程对共享区域的都有自己的访问权限。如果一个进程对共享区域的访问违反了权限规定，则发生操作越权。访问违反了权限规定，则发生操作越权。即读写保护。即读写保护。4.内存内存“扩充扩充”通过虚拟存储技术实现通过虚拟存储技术实现 用户在编制程序时，不

12、应该受内存容量限制，所用户在编制程序时，不应该受内存容量限制，所以要采用一定技术来以要采用一定技术来扩充扩充内存的容量，使用户得到内存的容量，使用户得到比实际内存容量大的多的内存空间。比实际内存容量大的多的内存空间。内存内存“扩充扩充”具体实现是在硬件支持下，软硬件相互协作，将具体实现是在硬件支持下，软硬件相互协作，将内存和外存结合起来统一使用。通过这种方法把内内存和外存结合起来统一使用。通过这种方法把内存扩充，使用户在编制程序时不受内存限制。存扩充，使用户在编制程序时不受内存限制。5.地址映射（地址重定位，地址变换）地址映射（地址重定位，地址变换）(1)逻辑地址（相对地址，虚地址）逻辑地址（

13、相对地址，虚地址）(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 。1200120012001200物理地址空间物理地址空间物理地址空间物理地址空间Load A data1Loa

15、d 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逻辑地址空间逻辑地址空间110012001300物理地址空间物理地址空间200VR+1000BR*重定位和保护重定位和

16、保护 多道程序导致了分区的产生，而分区也导致了多道程序导致了分区的产生，而分区也导致了多道程序导致了分区的产生，而分区也导致了多道程序导致了分区的产生，而分区也导致了新的问题，即程序的重新定位和保护。新的问题，即程序的重新定位和保护。新的问题，即程序的重新定位和保护。新的问题，即程序的重新定位和保护。如果多个作业都是为某如果多个作业都是为某如果多个作业都是为某如果多个作业都是为某一一一一个程序服务，当主程序个程序服务，当主程序个程序服务，当主程序个程序服务，当主程序调用这些作业的时候，就需要定位到这些作业，保调用这些作业的时候，就需要定位到这些作业，保调用这些作业的时候，就需要定位到这些作业，

17、保调用这些作业的时候，就需要定位到这些作业，保证程序的运行（主函数和分别编译好的子函数）。证程序的运行（主函数和分别编译好的子函数）。证程序的运行（主函数和分别编译好的子函数）。证程序的运行（主函数和分别编译好的子函数）。这时，链接的时候，链接器按照我们的分区机制来这时，链接的时候，链接器按照我们的分区机制来这时，链接的时候，链接器按照我们的分区机制来这时，链接的时候，链接器按照我们的分区机制来定位程序。定位程序。定位程序。定位程序。定位和保护的常见方法：定位和保护的常见方法：定位和保护的常见方法：定位和保护的常见方法：原因原因:当程序装入内存时当程序装入内存时,操作系统要为该程序分操作系统要

18、为该程序分配一个合适的内存空间，由于程序的逻辑地址与配一个合适的内存空间，由于程序的逻辑地址与分配到内存物理地址不一致分配到内存物理地址不一致,而而CPU执行指令时，执行指令时，是按物理地址进行的，所以要进行地址转换。是按物理地址进行的，所以要进行地址转换。静态重定位静态重定位 当用户程序被装入内存时，一次性实现逻辑当用户程序被装入内存时，一次性实现逻辑地址到物理地址的转换，以后不再转换（一般在地址到物理地址的转换，以后不再转换（一般在装入内存时由软件完成）。装入内存时由软件完成）。动态重定位动态重定位 在程序运行过程中要访问数据时再进行地址变在程序运行过程中要访问数据时再进行地址变换（即在逐

19、条指令执行时完成地址映射。一般为了换（即在逐条指令执行时完成地址映射。一般为了提高效率，此工作由硬件地址映射机制来完成。硬提高效率，此工作由硬件地址映射机制来完成。硬件支持，软硬件结合完成）。件支持，软硬件结合完成）。硬件上需要一对寄存器的支持。硬件上需要一对寄存器的支持。4.1 基本的内存管理基本的内存管理在运行时进程可以在内存和磁盘之间进行移在运行时进程可以在内存和磁盘之间进行移动（交换和分页技术）的系统；动（交换和分页技术）的系统；运行时进程不能够移动的系统，较为简单。运行时进程不能够移动的系统，较为简单。交换和分页技术的目的是由于没有足交换和分页技术的目的是由于没有足够的主存来同时容纳

20、所有的进程而被引入。够的主存来同时容纳所有的进程而被引入。随着硬件的发展，现有的良好的管理方案也随着硬件的发展，现有的良好的管理方案也会可能变成过时的技术而被淘汰。会可能变成过时的技术而被淘汰。无交换和分页的单道程序无交换和分页的单道程序 此方案是指同一个时刻和操作系统共享存储器。此方案是指同一个时刻和操作系统共享存储器。此方案是指同一个时刻和操作系统共享存储器。此方案是指同一个时刻和操作系统共享存储器。用户程序用户程序用户程序用户程序位于位于位于位于RAMRAM中的中的中的中的操作系统操作系统操作系统操作系统0 xFFF.0 xFFF.0 0位于位于位于位于RAMRAM中的中的中的中的操作系

21、统操作系统操作系统操作系统用户程序用户程序用户程序用户程序0 0ROMROM中的中的中的中的设备驱动程序设备驱动程序设备驱动程序设备驱动程序用户程序用户程序用户程序用户程序位于位于位于位于RAMRAM中的中的中的中的操作系统操作系统操作系统操作系统0 0A AB BC C 对于对于对于对于A A图，操作系统位于主存最底部的图，操作系统位于主存最底部的图，操作系统位于主存最底部的图，操作系统位于主存最底部的RAMRAM，即随机存取存储器中，用户程序位于主存的上部。即随机存取存储器中，用户程序位于主存的上部。即随机存取存储器中，用户程序位于主存的上部。即随机存取存储器中，用户程序位于主存的上部。对

22、于对于对于对于B B图，操作系统位于主存最高端的只读存图，操作系统位于主存最高端的只读存图，操作系统位于主存最高端的只读存图，操作系统位于主存最高端的只读存储器里（储器里（储器里（储器里（ROMROM）,（其实本身属于一种映像（其实本身属于一种映像（其实本身属于一种映像（其实本身属于一种映像区域，映像了主板上的基本的输入输出系统）。区域，映像了主板上的基本的输入输出系统）。区域，映像了主板上的基本的输入输出系统）。区域，映像了主板上的基本的输入输出系统）。对于对于对于对于C C图，设备的驱动程序位于内存最高端的图，设备的驱动程序位于内存最高端的图，设备的驱动程序位于内存最高端的图，设备的驱动程

23、序位于内存最高端的ROMROM中，操作系统的其余部分位于低端的中，操作系统的其余部分位于低端的中，操作系统的其余部分位于低端的中，操作系统的其余部分位于低端的RAMRAM中，中，中，中，中间是用户的应用程序。如中间是用户的应用程序。如中间是用户的应用程序。如中间是用户的应用程序。如MS-DOSMS-DOS系统。系统。系统。系统。对于对于对于对于IBMIBM操作系统，系统位于操作系统，系统位于操作系统，系统位于操作系统，系统位于ROMROM中的部分即中的部分即中的部分即中的部分即为为为为BIOSBIOS。对于这种方式，不管是哪一个图，操作对于这种方式，不管是哪一个图，操作系统每次把需要的程序从磁

24、盘复制到存储系统每次把需要的程序从磁盘复制到存储器里并执行，当程序结束时，系统提示结器里并执行，当程序结束时，系统提示结束，当有新的命令时，系统加载新的程序束，当有新的命令时，系统加载新的程序到存储器中，覆盖原来的程序，继续新的到存储器中，覆盖原来的程序，继续新的执行。执行。可以满足早期一般的小型的操作系统的可以满足早期一般的小型的操作系统的需求，但随着硬件性能的提高，这种方式需求，但随着硬件性能的提高，这种方式逐渐被淘汰。逐渐被淘汰。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操作系统操作系统操作系统操作系统700K700K700K700K400K400K400K400K100K100K100K100K0 0 0 0 对于左图，由于作业的大小类似的时候，而且对于左图，由于作业的大小类似的时候，而且对于左

28、图，由于作业的大小类似的时候，而且对于左图，由于作业的大小类似的时候，而且众多的作业大小都类似，而此时分区的大小固定，众多的作业大小都类似，而此时分区的大小固定，众多的作业大小都类似，而此时分区的大小固定，众多的作业大小都类似，而此时分区的大小固定，我们该选择合适大小的分区来运行这个作业，这样我们该选择合适大小的分区来运行这个作业，这样我们该选择合适大小的分区来运行这个作业，这样我们该选择合适大小的分区来运行这个作业，这样的话，类似的作业就被分到了一起，而那些与作业的话，类似的作业就被分到了一起，而那些与作业的话，类似的作业就被分到了一起，而那些与作业的话，类似的作业就被分到了一起，而那些与作

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）或者对于具有两个可增长数据部分的进程，采或者对于具有两个可增长数据部分的进程，采或者对于具有两个可增长数据部分的进程，采或者对于具有两个可增长数据部分的进程，采用在进程的分区内分开放置的方式管理。（用在进程的分区内分开放置的方式管理。（用在进程的分区内分开放置的方式管理。（用在进程的分区内分开放置的方式管理。（B B）OSOSA AB BA A为增长内存为增长内存为增长内存为增长内存准备的内存准备的内存准备的内存准备的内存实际使用的

41、实际使用的实际使用的实际使用的内存内存内存内存为增长内存为增长内存为增长内存为增长内存准备的内存准备的内存准备的内存准备的内存实际使用的实际使用的实际使用的实际使用的内存内存内存内存OSOSA-PROGA-PROGA-DATAA-DATAA-STACKA-STACKB-DATAB-DATAB-STACKB-STACKB-PROGB-PROGB B为增长内存为增长内存为增长内存为增长内存准备的内存准备的内存准备的内存准备的内存为增长内存为增长内存为增长内存为增长内存准备的内存准备的内存准备的内存准备的内存4.2.1 使用位图的内存管理使用位图的内存管理 由于操作系统需要对内存进行分配管理和回由于

42、操作系统需要对内存进行分配管理和回由于操作系统需要对内存进行分配管理和回由于操作系统需要对内存进行分配管理和回收，所以，它必须很好地对内存进行跟踪，常用收，所以，它必须很好地对内存进行跟踪，常用收，所以，它必须很好地对内存进行跟踪，常用收，所以，它必须很好地对内存进行跟踪，常用的是位图法和自由链表：的是位图法和自由链表：的是位图法和自由链表：的是位图法和自由链表：A AB BC CD DE E(a)对于位图方法，位图的大小与内存的大小和分配对于位图方法，位图的大小与内存的大小和分配对于位图方法，位图的大小与内存的大小和分配对于位图方法，位图的大小与内存的大小和分配的单位的大小相关，内存不变时，

43、被分配的单个单的单位的大小相关，内存不变时，被分配的单个单的单位的大小相关，内存不变时，被分配的单个单的单位的大小相关，内存不变时，被分配的单个单元越小，则位图就越大。元越小，则位图就越大。元越小，则位图就越大。元越小，则位图就越大。位图的组织结构简单，便于管理，且占用的内位图的组织结构简单，便于管理，且占用的内位图的组织结构简单，便于管理，且占用的内位图的组织结构简单，便于管理，且占用的内存很小但也有缺陷：定位的速度受限，由于每个位存很小但也有缺陷：定位的速度受限，由于每个位存很小但也有缺陷：定位的速度受限，由于每个位存很小但也有缺陷：定位的速度受限，由于每个位图单元代表一个被分配的单元，所

44、以连续性不强，图单元代表一个被分配的单元，所以连续性不强，图单元代表一个被分配的单元，所以连续性不强，图单元代表一个被分配的单元，所以连续性不强，对于某个需要几个分配单元大小的进程就很难快速对于某个需要几个分配单元大小的进程就很难快速对于某个需要几个分配单元大小的进程就很难快速对于某个需要几个分配单元大小的进程就很难快速在位图中找到这样连续的空间。故实际不很常用。在位图中找到这样连续的空间。故实际不很常用。在位图中找到这样连续的空间。故实际不很常用。在位图中找到这样连续的空间。故实际不很常用。4.2.2 使用链表的内存管理使用链表的内存管理 这种方法是通过一个链表来管理已经分配的和这种方法是通

45、过一个链表来管理已经分配的和这种方法是通过一个链表来管理已经分配的和这种方法是通过一个链表来管理已经分配的和尚未分配的内存段，通过对链表的维护达到对内存尚未分配的内存段，通过对链表的维护达到对内存尚未分配的内存段，通过对链表的维护达到对内存尚未分配的内存段，通过对链表的维护达到对内存的管理。这里的内存段可以使被某个进程所占用，的管理。这里的内存段可以使被某个进程所占用，的管理。这里的内存段可以使被某个进程所占用，的管理。这里的内存段可以使被某个进程所占用，也可以是个空洞，即尚未分配的区域。也可以是个空洞，即尚未分配的区域。也可以是个空洞，即尚未分配的区域。也可以是个空洞，即尚未分配的区域。表的

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、变形首次适配的变形首次适配的变形下次适配下次适配下次适配下次适配 工作方式与首次适配相同，区别在于每次搜索工作方式与首次适配相同，区别在于每次搜索工作方式与首次适配相同，区别在于每次搜索工作方式与首次适配相同，区别在于每次搜索完毕后记录当前的位置，下次搜索时从此处开始搜完毕后记录当前的位置，下次搜索时从此处开始搜完毕后记录当前的位置，下次搜索时从此处开始搜完毕后记录当前的位置，下次搜索时从此处开始搜索。索。索。索。*最佳适配算法最佳适配算法最佳适配算法最佳适配算法每次搜索整个链表中最适合该进程大小的内存每次搜索整个链表中最适合该进程大小的内存每次搜索整个链表中最适合该进程大小的内存每次搜索整个