操作系统第四章-2016

1、1 4 4 存储器管理存储器管理 存储器是计算机的重要组成部分存储器是计算机的重要组成部分, ,存储器存储器是一种宝贵且紧俏的资源是一种宝贵且紧俏的资源, ,如何对存储器有效如何对存储器有效的管理不但直接影响到存储器的利用率的管理不但直接影响到存储器的利用率, ,还影还影响到系统的性能响到系统的性能. .本章讨论的主要对象是内存。本章讨论的主要对象是内存。由于对外存的管理与对内存的管理相似，只是由于对外存的管理与对内存的管理相似，只是用途不同，而外存主要用来存放文件，故将在用途不同，而外存主要用来存放文件，故将在磁盘存储器管理中介绍。磁盘存储器管理中介绍。23 4.1 存储器的层次结构存储器的

2、层次结构 在计算机执行时，几乎每一条指令都涉及对在计算机执行时，几乎每一条指令都涉及对存储器的访问，因此要求对存储器的访问速度能跟存储器的访问，因此要求对存储器的访问速度能跟的上处理机的运行速度。此外还要求存储器具有非的上处理机的运行速度。此外还要求存储器具有非常大的容量，而且存储器的价格还应很便宜。对于常大的容量，而且存储器的价格还应很便宜。对于这样十分严格的三个条件，目前是无法同时满足的。这样十分严格的三个条件，目前是无法同时满足的。于是，在现代计算机系统中都无一例外地采用了多于是，在现代计算机系统中都无一例外地采用了多层结构的存储器系统。层结构的存储器系统。44.1.1 多层结构的存储器

3、系统多层结构的存储器系统n对于通用计算机而言，存储层次至少应对于通用计算机而言，存储层次至少应具有三级：最高层为寄存器，中具有三级：最高层为寄存器，中间为主存，最底层是辅存。间为主存，最底层是辅存。n在较高档的计算机中，还可以根据具体在较高档的计算机中，还可以根据具体的功能细分为寄存器、高速缓存、主存的功能细分为寄存器、高速缓存、主存储器、磁盘缓存、固定磁盘、可移动存储器、磁盘缓存、固定磁盘、可移动存储介质等层。储介质等层。5计算机系统存储层次示意图如右图所示：在存储器层次中，如右图所示：在存储器层次中，层次越高（越靠近），存层次越高（越靠近），存储介质的访问速度越快，价格也储介质的访问速度越

4、快，价格也越高，相对所配置的存储容量也越高，相对所配置的存储容量也越小。越小。其中，寄存器、高速缓存、主存储器和磁盘缓存均属于操其中，寄存器、高速缓存、主存储器和磁盘缓存均属于操作系统存储管理的管辖范畴，掉电后，它们中存储的信息作系统存储管理的管辖范畴，掉电后，它们中存储的信息不再存在。而低层的固定磁盘和可移动存储介质则属于设不再存在。而低层的固定磁盘和可移动存储介质则属于设备管理的管理范畴，它们存储的信息将被长期保存。备管理的管理范畴，它们存储的信息将被长期保存。64.1.24.1.2主存储器与寄存器主存储器与寄存器n 主存储器和寄存器又被称为可执行存储器；主存储器和寄存器又被称为可执行存储

5、器；n 主存储器简称内存或主存，用于保存进程运主存储器简称内存或主存，用于保存进程运行时的程序和数据；行时的程序和数据；n 寄存器具有与处理机相同的速度，故对寄存寄存器具有与处理机相同的速度，故对寄存器的访问速度最快，完全能与协调工器的访问速度最快，完全能与协调工作，但价格十分昂贵，且容量较小；作，但价格十分昂贵，且容量较小；7.1.3.1.3高速缓存和磁盘缓存高速缓存和磁盘缓存n 高速缓存：介于寄存器和存储器之间的存储高速缓存：介于寄存器和存储器之间的存储器，主要用于备份主存中较常用的数据，以器，主要用于备份主存中较常用的数据，以减少处理机对主存储器的访问次数，大幅度减少处理机对主存储器的访

6、问次数，大幅度提高程序执行速度。提高程序执行速度。n 高速缓存容量远大于寄存器，比内存约小两高速缓存容量远大于寄存器，比内存约小两到三个数量级左右，访问速度快于主存储器。到三个数量级左右，访问速度快于主存储器。n 磁盘缓存：暂时存放频繁使用的一部分磁盘磁盘缓存：暂时存放频繁使用的一部分磁盘数据和信息，以减少访问磁盘的次数。数据和信息，以减少访问磁盘的次数。n 与高速缓存不同，磁盘缓存本身不是一种实与高速缓存不同，磁盘缓存本身不是一种实际存在的存储器。际存在的存储器。8 . 程序的装入和链接程序的装入和链接在多道程序环境下在多道程序环境下,程序要运行必须创建进程。程序要运行必须创建进程。创建进程

7、的第一件事就是将程序和数据装入内存。创建进程的第一件事就是将程序和数据装入内存。9 如何将一个用户源程序变成一个可以在内存如何将一个用户源程序变成一个可以在内存中执行的程序？中执行的程序？编译编译:由编译程序将用户源代码译成若干个目由编译程序将用户源代码译成若干个目标模块。标模块。链接链接:由链接程序将编译后形成的目标模块以由链接程序将编译后形成的目标模块以及它们所需要的库函数链接在一起及它们所需要的库函数链接在一起,形成一个形成一个装入模块。装入模块。1.装入装入:由装入程序将装入模块装入内存。由装入程序将装入模块装入内存。10对用户程序的处理步骤对用户程序的处理步骤11前前置置处处理理器器

8、编编译译器器优优化化器器汇汇编编程程序序器器连接连接/载入载入程序程序程 序 库程 序 库文件文件目的目的文件文件可可执执行行文文件件源源文文件件包含的头包含的头文件文件汇 编 语 言汇 编 语 言源文件源文件程序处理步骤 可执行程序生成过程可执行程序生成过程:12程序地址程序地址: 相对地址相对地址(逻辑地址逻辑地址):相对于本可执行程序起始相对于本可执行程序起始地址地址. 由于编译程序不能预知编译的目标模块在内由于编译程序不能预知编译的目标模块在内存的具体位置存的具体位置,因此目标模块的起始地址通常都是因此目标模块的起始地址通常都是从从0开始计算开始计算. 绝对地址绝对地址(物理地址物理地

9、址):存放在存储介质上的地址存放在存储介质上的地址.13.程序的装入程序的装入单个目标模块的装入过程可采用三种方式：单个目标模块的装入过程可采用三种方式：n绝对装入方式绝对装入方式n可重定位方式可重定位方式n动态运行时的装入方式动态运行时的装入方式14(1)(1)绝对装入方式绝对装入方式:由装入程序根据模块中的地址由装入程序根据模块中的地址,将程序和数据装入内存。将程序和数据装入内存。 适合单道程序环境。适合单道程序环境。符号地址符号地址程序JUMP iLOAD jDATAijA 目标模块目标模块绝对地址绝对地址JUMP1424LOAD222410241424B绝对装入模块绝对装入模块1200

10、4000相对地址相对地址JUMP400LOAD1200C相对装入模块相对装入模块15(2)(2)可可重定位装入方式重定位装入方式:由装入程序根据内存当时由装入程序根据内存当时的实际使用情况的实际使用情况,将装入模块装入到内存适当地方。将装入模块装入到内存适当地方。不允许在内存中移位不允许在内存中移位,适用多道程序环境。适用多道程序环境。定义：定义：把装入时对目标程序中的指令和数据地址的把装入时对目标程序中的指令和数据地址的修改过程称为重定位。修改过程称为重定位。 0100025005000 365load1250010000load125001250036515000作业地址空间作业地址空间内

11、存空间内存空间16(3)(3)动态运行时动态运行时装入方式装入方式 定义：定义：把装入模块装入内存后，并不立即把把装入模块装入内存后，并不立即把装入模块中的相对地址装换为绝对地址，而是装入模块中的相对地址装换为绝对地址，而是推迟到程序要真正执行时才进行。推迟到程序要真正执行时才进行。 地址转换要借助硬件完成才能不影响指令的地址转换要借助硬件完成才能不影响指令的执行速度。执行速度。174.2.2 程序的链接程序的链接功能：功能：将经过编译或汇编后所得到的一组目标将经过编译或汇编后所得到的一组目标模块以及它们所需要的库函数装配成一个完整模块以及它们所需要的库函数装配成一个完整的装入模块。的装入模块

12、。实现：实现：n静态链接；静态链接；n装入时动态链接：装入时动态链接：n运行时动态链接。运行时动态链接。18(1)(1)静态链接静态链接 将几个目标模块链接成一个装入将几个目标模块链接成一个装入模块模块, ,要运行时直接装入内存。要运行时直接装入内存。由以下两步完成由以下两步完成: : 对相对地址修改对相对地址修改; ; 变换外部调用符号。变换外部调用符号。优点优点: :简单简单19(2)(2)装入时动态链接装入时动态链接: :将几个目标模块边装入边链接。将几个目标模块边装入边链接。若发生外部调用若发生外部调用, ,将引起装入程序去将引起装入程序去找出相应的外部目标模块找出相应的外部目标模块,

13、 ,并将它装并将它装入内存。入内存。优点优点: :便于软件版本的修改和更新；便于软件版本的修改和更新；便于实现目标模块的共享。便于实现目标模块的共享。20(3)(3)运行时动态链接运行时动态链接: :将几个目标模块边运行边链接。将几个目标模块边运行边链接。若没有运行的模块不在链接。若没有运行的模块不在链接。优点优点: :节约内存；节约内存；程序运行效率更高。程序运行效率更高。问题问题: :运行时实现装入过程。运行时实现装入过程。214.3 连续分配存储管理方式连续分配存储管理方式连续分配：连续分配：是指为一个用户程序分配一个连续是指为一个用户程序分配一个连续的内存空间。的内存空间。连续分配方式

14、可分为四类：连续分配方式可分为四类：n单一连续分配；单一连续分配；n固定分区分配；固定分区分配；n动态分区分配；动态分区分配；n动态可重定位分区分配算法。动态可重定位分区分配算法。224.3.1 单一连续分配方式单一连续分配方式l只能用于单用户，单任务的操作系统中。只能用于单用户，单任务的操作系统中。l内存分为两个区：内存分为两个区：（1 1）系统区）系统区: :仅提供给操作系统使用，可以停仅提供给操作系统使用，可以停留在内存的低址部分，也可以在高址部分。留在内存的低址部分，也可以在高址部分。（2 2）用户区）用户区: :指除系统区以外的全部内存空间，指除系统区以外的全部内存空间，提供给用户使

15、用。提供给用户使用。23图图45：地址映射和地址保护：地址映射和地址保护否CPUu.size?继续检索下一个表项从头开始查表检索完否？返回 分配内存分配内存NNN35 F1回收区回收区回收区回收区F2回收区回收区 F1F2n 回收内存回收内存: 回收区与插入点的前一个分区邻接回收区与插入点的前一个分区邻接F1; 回收区与插入点的后一个分区邻接回收区与插入点的后一个分区邻接F2; 回收区与插入点的前后分区邻接回收区与插入点的前后分区邻接F1,F2; 回收区既不与回收区既不与F1邻接又不与邻接又不与F2邻接邻接;364.3.4 4.3.4 基于顺序搜索的动态分区分配算法基于顺序搜索的动态分区分配算

16、法基于顺序搜索的动态分区分配算法有如下基于顺序搜索的动态分区分配算法有如下四种：四种：首次适应算法首次适应算法循环首次适应算法循环首次适应算法最佳适应算法最佳适应算法最坏适应算法最坏适应算法37n首次适应算法首次适应算法FF:FF:空闲分区链以地址递增的次序链接。空闲分区链以地址递增的次序链接。每次分配时从链首开始顺序查找每次分配时从链首开始顺序查找, ,直到找到一个直到找到一个能满足大小要求的空闲分区为止。能满足大小要求的空闲分区为止。按照作业的大小按照作业的大小, ,从该分区中划分出一块内存空从该分区中划分出一块内存空间分配给请求者。间分配给请求者。余下的空闲分区仍留在空闲链中。余下的空闲

17、分区仍留在空闲链中。特点特点: :优先利用内存低址部分优先利用内存低址部分, ,为大作业分配大的内存为大作业分配大的内存空间创造了条件。空间创造了条件。留下了很多难以利用的很小的空间。留下了很多难以利用的很小的空间。38n 循环首次适应算法循环首次适应算法: : 在在FFFF算法的基础上算法的基础上, ,不在每次从链首开始查找不在每次从链首开始查找, ,而是从上次找到的空闲分区的下一个空闲分区开而是从上次找到的空闲分区的下一个空闲分区开始查找始查找, ,直到找到一个能满足大小要求的空闲分区直到找到一个能满足大小要求的空闲分区为止为止. .按照作业的大小按照作业的大小, ,从该分区中划分出一块内

18、从该分区中划分出一块内存空间分配给请求者。存空间分配给请求者。实现方法实现方法: :设置一起始查询指针指示下一次起始查设置一起始查询指针指示下一次起始查询的空闲分区询的空闲分区, ,并采用循环查找方式。并采用循环查找方式。 特点特点: :使空闲分区分布均匀；使空闲分区分布均匀； 减少查找空闲分区开销；减少查找空闲分区开销； 缺乏大的空闲分区。缺乏大的空闲分区。39n 最佳适应算法最佳适应算法: : 将所有的空闲区按其大小递增的顺序形成一将所有的空闲区按其大小递增的顺序形成一空闲区链。这样第一次找到的空闲区必然是空闲区链。这样第一次找到的空闲区必然是最优的。最优的。 特点特点: :找到的空闲区既

19、是满足要求又是最小的。找到的空闲区既是满足要求又是最小的。 每次分配割下的剩余部分总是最小每次分配割下的剩余部分总是最小, ,这些小的这些小的空间难以利用。空间难以利用。 40n 最坏适应算法最坏适应算法: : 在扫描整个空闲分区表或链表时，总是挑选在扫描整个空闲分区表或链表时，总是挑选一个最大的空闲分区，从中分割一部分存储一个最大的空闲分区，从中分割一部分存储空间给作业使用，以至于存储器中缺乏大的空间给作业使用，以至于存储器中缺乏大的空闲分区。空闲分区。特点特点: :可使剩下的空闲区不至于太小，产生碎片的可使剩下的空闲区不至于太小，产生碎片的可能性最小，对中、小作业有利。可能性最小，对中、小

20、作业有利。查找效率高查找效率高 414.3.5 4.3.5 基于索引搜索的动态分区分配算法基于索引搜索的动态分区分配算法目前常用的基于索引搜索的动态分区分目前常用的基于索引搜索的动态分区分配算法包括：配算法包括：l 快速适应算法快速适应算法l 伙伴系统伙伴系统l 哈希算法哈希算法42n 快速适应算法快速适应算法又称为分类搜索法，是将空闲分区根据其容量大又称为分类搜索法，是将空闲分区根据其容量大小进行分类，对于每一类具有相同容量的所小进行分类，对于每一类具有相同容量的所有空闲分区，单独设立一个空闲分区链表，有空闲分区，单独设立一个空闲分区链表，这样系统中存在多个空闲分区链表。这样系统中存在多个空

21、闲分区链表。执行步骤：执行步骤：根据进程的长度，从索引表中去寻找到能容根据进程的长度，从索引表中去寻找到能容纳它的最小空闲区链表；纳它的最小空闲区链表；从链表中取下第一块进行分配。从链表中取下第一块进行分配。优点：优点：查找效率高查找效率高缺点：缺点：系统开销大；为进程所分配的分区中，存系统开销大；为进程所分配的分区中，存在一定浪费。在一定浪费。43n 伙伴系统伙伴系统 优缺点：优缺点：回收空闲分区时，需要对空闲分区进行合并，回收空闲分区时，需要对空闲分区进行合并，所以其时间性能比快速适应算法差，但由于它所以其时间性能比快速适应算法差，但由于它采用索引搜索算法，比顺序搜索算法好。采用索引搜索算

22、法，比顺序搜索算法好。空间性能优于快速适应算法，比顺序搜索法略空间性能优于快速适应算法，比顺序搜索法略差。差。44n 哈希算法哈希算法 哈希算法利用哈希快速查找的优点，以及哈希算法利用哈希快速查找的优点，以及空闲分区在可利用空闲区表中的分布规律，建空闲分区在可利用空闲区表中的分布规律，建立哈希函数，构造一张以空闲分区大小为关键立哈希函数，构造一张以空闲分区大小为关键字的哈希表，该表的每一个表项纪录了一个对字的哈希表，该表的每一个表项纪录了一个对应的空闲分区链表表头指针。应的空闲分区链表表头指针。 当进行空闲分区分配时，根据所需空闲分当进行空闲分区分配时，根据所需空闲分区大小，通过哈希函数计算，

23、即得到在哈希表区大小，通过哈希函数计算，即得到在哈希表中的位置，从中得到相应的空闲分区链表，实中的位置，从中得到相应的空闲分区链表，实现最佳分配策略。现最佳分配策略。454.3.6 4.3.6 动态动态重定位分区分配重定位分区分配(1)(1)紧凑紧凑: : 零头零头( (碎片碎片):):作业之间作业之间( (主存中主存中) )不能充分利用的不能充分利用的 存储碎块。存储碎块。 紧凑紧凑: :将内存中的所有作业进行移动，使它们相将内存中的所有作业进行移动，使它们相 邻接邻接. .原来分散的多个小分区拼结成一个大原来分散的多个小分区拼结成一个大 分区。分区。46 操作系统操作系统 用户程序用户程序

24、1 1 10KB10KB 用户程序用户程序3 3 30KB30KB 用户程序用户程序6 6 14KB14KB 用户程序用户程序9 9 26KB26KB 操作系统操作系统 用户程序用户程序1 1 用户程序用户程序3 3 用户程序用户程序6 6 用户程序用户程序9 9 80KB80KB紧凑前 紧凑后47(2)(2)动态重定位动态重定位: 用用RR(RR(重定位寄存器重定位寄存器):):硬件完成硬件完成. . 程序执行时真正访问的内存地址是相对程序执行时真正访问的内存地址是相对地址与重定位寄存器中的地址相加而形成的地址与重定位寄存器中的地址相加而形成的. . 动态重定位动态重定位: : 地址变换过程

25、是在程序执行期间地址变换过程是在程序执行期间, ,随着随着对每条指令和数据的访问而自动进行的对每条指令和数据的访问而自动进行的, ,这这就是动态重定位就是动态重定位. .48250010000LOAD1,2500365LOAD1,2500365010025005000作业j相对地址重定位寄存器10000101001250015000主存处理机一侧存储器一侧动态重定位示意图动态重定位示意图49(3)(3)动态重定位分区分配算法动态重定位分区分配算法 与动态分区分配算法基本相同，差别仅在于：与动态分区分配算法基本相同，差别仅在于：在这种分配算法中，增加了紧凑的功能。在这种分配算法中，增加了紧凑的功

26、能。当该算法不能找到一个足够大的空闲分区当该算法不能找到一个足够大的空闲分区以满足用户需求时，如果所有小的空闲分以满足用户需求时，如果所有小的空闲分区的容量总和大于用户的要求，这是便须区的容量总和大于用户的要求，这是便须对内存进行对内存进行“紧凑紧凑”，将经紧凑后多得到，将经紧凑后多得到的大空闲分区分配给用户。的大空闲分区分配给用户。如果所有小空闲分区的容量总和仍小于用如果所有小空闲分区的容量总和仍小于用户的需求，则返回分配失败信息。户的需求，则返回分配失败信息。50(3)(3)动态分区分配算法流程动态分区分配算法流程: : 无法分配返回空闲分区总和u.xize进行紧凑形成连续空闲区修改有关的

27、数据结构请求分配u.xize分区检索空闲分区链 找到大于u.xize的可用区否？按动态分区方式进行分配修改有关的数据结构返回分区号及首址否否是是51IBM-PC微机中的存储管理方式微机中的存储管理方式(1)(1)段存储器和作业的分段段存储器和作业的分段: : 采用多重定位的存储器管理方式采用多重定位的存储器管理方式. . 设置四个段寄存器设置四个段寄存器: : 代码段寄存器代码段寄存器CSCS 数据段寄存器数据段寄存器DSDS 栈段寄存器栈段寄存器SSSS 附加段寄存器附加段寄存器ES.ES.52程序分为四个段程序分为四个段: : 代码段代码段, ,数据段数据段, ,栈段栈段, ,附加段附加段

28、. . 这几个段的地址空间可以邻接也可以分开这几个段的地址空间可以邻接也可以分开; ;也可部分或全部重叠也可部分或全部重叠. . 一个作业的最大地址空间可为一个作业的最大地址空间可为256KB.256KB.每一每一个段可以存放在内存用户区的任何位置个段可以存放在内存用户区的任何位置. . IBM-PC IBM-PC机的最大寻址范围为机的最大寻址范围为1MB,201MB,20位地址位地址. .而每段地址位而每段地址位1616位位, ,剩余剩余4 4位位( (低低4 4位全为位全为0).0).因此因此把高把高1616位的内容放入段寄存器中位的内容放入段寄存器中. .53(2)(2)形成访问内存物理

29、地址形成访问内存物理地址: : 段寄存器内容左移段寄存器内容左移4 4位再与位再与1616位的地址偏位的地址偏移量相加就是移量相加就是2020位的物理地址位的物理地址. .(3)(3)多重定位的实现多重定位的实现: : 由于有四个段寄存器，可以实现四重分由于有四个段寄存器，可以实现四重分区。一个用户程序分为四段，每段可以放在区。一个用户程序分为四段，每段可以放在用户区的任何位置，也允许在内存中移动。用户区的任何位置，也允许在内存中移动。544.4 4.4 对换对换n也称为交换也称为交换(Swaping)(Swaping)技术。技术。n最早用在麻省理工学院的兼容分时系统最早用在麻省理工学院的兼容

30、分时系统CTSSCTSS中中. .该系统是单用户系统该系统是单用户系统, ,在内存中只留一道用户作在内存中只留一道用户作业业, ,其它作业都驻留在外存后备队列其它作业都驻留在外存后备队列, ,每次只调入每次只调入一个作业进入内存运行一个作业进入内存运行, ,此作业的时间片用完后此作业的时间片用完后调至外存。再从外存后备队列再调入下一个作业调至外存。再从外存后备队列再调入下一个作业进入内存。这样进入内存。这样, , 解决了内存的不足解决了内存的不足, ,增加了作增加了作业的多道度。业的多道度。n这种早期的交换技术由于这种早期的交换技术由于CPUCPU空闲时间太长今天空闲时间太长今天已经不用。已经

31、不用。 554.4.1 4.4.1 多道程序环境下的兑换技术多道程序环境下的兑换技术对换概念对换概念: : 将主存中暂时不能运行的进程（程序，数据）将主存中暂时不能运行的进程（程序，数据）调到外存，腾出主存空间把外存的进程（程序，调到外存，腾出主存空间把外存的进程（程序，数据）调入主存投入运行。数据）调入主存投入运行。对换类型：对换类型：n如果对换以整个进程为单位如果对换以整个进程为单位, ,则称为则称为“整体对换整体对换”或或“进程对换进程对换”, ,在分时系统中应用最多。在分时系统中应用最多。n如果对换以页或段为单位如果对换以页或段为单位, ,则称为则称为“页面对换页面对换”或或“分段对换

32、分段对换”, ,也称为也称为“部分对换部分对换”。564.4.2 4.4.2 对换空间的管理对换空间的管理1.1.对换空间管理的主要目标对换空间管理的主要目标 1 1）对文件区管理的主要目标）对文件区管理的主要目标 主要目标是提高文件存储空间的利用率，然后才主要目标是提高文件存储空间的利用率，然后才是提高对文件的访问速度。是提高对文件的访问速度。 2 2）对对换空间管理的主要目标）对对换空间管理的主要目标 主要目标是提高进程换入和换出的速度，然后才主要目标是提高进程换入和换出的速度，然后才是提高文件存储空间的利用率。是提高文件存储空间的利用率。574.4.2 4.4.2 对换空间的管理对换空间

33、的管理2.2.对换区空闲盘块管理中的数据结构对换区空闲盘块管理中的数据结构 使用空闲分区表或空闲分区链，在空闲分区表使用空闲分区表或空闲分区链，在空闲分区表的每个表目中，应包含：对换区的首址及其大小，的每个表目中，应包含：对换区的首址及其大小，分别用盘块号和盘块数表示。分别用盘块号和盘块数表示。584.4.2 4.4.2 对换空间的管理对换空间的管理 594.4.34.4.3 进程的换出与换入进程的换出与换入(1)(1)进程的换出进程的换出: :n选出被换出的进程选出被换出的进程: : 状态状态: :阻塞或睡眠；阻塞或睡眠； 优先级最低；优先级最低； 在内存中的驻留时间。在内存中的驻留时间。n

34、换出过程换出过程: :非共享的程序或数据直接换出；非共享的程序或数据直接换出；共享的程序或数据换出前必须判断引用计数减共享的程序或数据换出前必须判断引用计数减1 1后是否为后是否为0,0,不为不为0,0,则不能换出；则不能换出；可以换出时，在申请对换空间成功后换出，同时可以换出时，在申请对换空间成功后换出，同时释放内存。释放内存。60(2)(2)进进程的换入程的换入:n当对换进程或程序去执行对换操作时，便检查当对换进程或程序去执行对换操作时，便检查PCBPCB集合中所有进程的状态。从中找出集合中所有进程的状态。从中找出“就绪且就绪且换出换出”状态的进程。状态的进程。n当存在多个这样的进程时，首

35、先把其中换出时间当存在多个这样的进程时，首先把其中换出时间（必须大于规定时间）最久的进程作为换入进程（必须大于规定时间）最久的进程作为换入进程. .n根据进程大小为其申请内存。根据进程大小为其申请内存。n成功，直接将进程换入。成功，直接将进程换入。n失败，先将内存中某些进程换出，再换入该进程。失败，先将内存中某些进程换出，再换入该进程。614.54.5 分页存储管理方式分页存储管理方式离散分配内存方式离散分配内存方式: : 克服连续分配方式会产生碎片；克服连续分配方式会产生碎片； 避免紧凑开销太大。避免紧凑开销太大。离散分配内存分为三种方式离散分配内存分为三种方式n分页存储管理分页存储管理n分

36、段存储管理分段存储管理n段页式存储管理段页式存储管理624.5.1 4.5.1 分页存储管理的基本方法分页存储管理的基本方法(1)(1)页面和物理块页面和物理块n页面：在分页存储管理方式中将一个进程的逻辑页面：在分页存储管理方式中将一个进程的逻辑地址空间分成若干个大小相等的片，称为页面或地址空间分成若干个大小相等的片，称为页面或页。页。n物理块：内存空间也分成和页相同大小的若干个物理块：内存空间也分成和页相同大小的若干个存储块，称为物理块或页框。存储块，称为物理块或页框。n页内碎片页内碎片: :最后一页装不满时形成。最后一页装不满时形成。n页面大小：适中的页面大小为页面大小：适中的页面大小为2

37、 2的幂，通常为的幂，通常为1KB8KB1KB8KB。634.5.1 4.5.1 分页存储管理的基本方法分页存储管理的基本方法(2)(2)地址结构地址结构页号页号 P (1MB) P (1MB) 位移量位移量W (4KB)W (4KB)31 12 11 0 31 12 11 0 它含有两部分。前一部分为页号它含有两部分。前一部分为页号P P，后一部分为位移量，后一部分为位移量W W，即页内地址。即页内地址。 对某特定机器，其地址结构是一定的。对某特定机器，其地址结构是一定的。 若给定一个逻辑空间中的地址为若给定一个逻辑空间中的地址为A,A,页面大小为页面大小为L L，则页号，则页号P P和页内

38、地址和页内地址d d可按下式求得：可按下式求得： P=INTA/LP=INTA/L， d=AMOD Ld=AMOD L64 0 0页页 1 1页页 2 2页页 3 3页页 4 4页页 5 5页页 N N页页 0 0 2 2 1 1 3 3 2 2 6 6 3 3 8 8 4 4 9 9 5 5 (3)(3)页表页表: :实现从页号到物理块号的映射。实现从页号到物理块号的映射。页号页号 块号块号内存内存 01 23456789用户程序用户程序页表的作用页表的作用654.5.2 地址变换机构地址变换机构 基本任务：基本任务： 实现逻辑地址到物理地址的转换，即将逻辑实现逻辑地址到物理地址的转换，即将

39、逻辑地址中的页号转换为内存中的物理块号。地址中的页号转换为内存中的物理块号。n基本的地址变换机构。基本的地址变换机构。n具有块表的地址变换机构。具有块表的地址变换机构。66(1)(1)基本的地址变换机构基本的地址变换机构: : 页表寄存器页表寄存器: :由于页表大多数驻留在内存中由于页表大多数驻留在内存中, ,在内存中设置一个页表寄存器存放页表在内在内存中设置一个页表寄存器存放页表在内存中的始址和长度。存中的始址和长度。 在单处理机环境下只需一个页表寄存器。在单处理机环境下只需一个页表寄存器。 分页地址变换机构分页地址变换机构: :将逻辑地址分为页号与页内地址；将逻辑地址分为页号与页内地址；比

40、较页号与页表长度比较页号与页表长度: :大于大于, ,越界；越界；否则否则: :页表始址页表始址+ +页号页号* *页表项长度页表项长度= =在页表中的位置；在页表中的位置；在页表中的位置中得到该页的物理块号；在页表中的位置中得到该页的物理块号；物理块的始址物理块的始址+ +页内偏移页内偏移= =物理地址。物理地址。67页表始址页表始址页表长度页表长度页号页号3 3页内地址页内地址 1 1 b b越界中断页号块号0123页表物理地址页表寄存器逻辑地址基本的地址变换机构基本的地址变换机构: :68(2)(2)具有快表的地址变换机构具有快表的地址变换机构: : 由于页表大多数在内存中由于页表大多数

41、在内存中,CPU,CPU存取一个数据要存取一个数据要两次访问内存两次访问内存, ,使计算机的处理速度降低使计算机的处理速度降低1/2,1/2,代价高。代价高。 在地址变换机构中增加一个具有并行查询能力在地址变换机构中增加一个具有并行查询能力的特殊高速缓冲存储器的特殊高速缓冲存储器, ,称为称为“联想寄存器联想寄存器”或或“快快表表”，用来存放当前访问的表项。用来存放当前访问的表项。地址变换机构地址变换机构: : 自动将页号自动将页号P P送入高速缓冲存储器中送入高速缓冲存储器中, ,并将该页并将该页号与缓冲存储器中的页号比较号与缓冲存储器中的页号比较, ,若有若有, ,则页表项在快则页表项在快

42、表中表中, ,直接得到物理块号直接得到物理块号; ;若无则在内存中若无则在内存中, ,再访问内再访问内存。存。 69页表始址页表始址 页表长度页表长度页号页号页内地址页内地址bbd+输入寄存器输入寄存器页表寄存器页表寄存器逻辑地址逻辑地址物理地址物理地址越界中断越界中断页号页号 块号块号页表页表页号页号 块号块号快表快表具有快表的地址变换机构具有快表的地址变换机构 70 由于高速缓存的成本很高由于高速缓存的成本很高, ,不可能做很大不可能做很大, ,通常存放通常存放1651216512个页表项。个页表项。 Molorola 68030 Molorola 68030处理器有处理器有2222个；个

43、； Intel 80486 Intel 80486处理器有处理器有3232个；个； 中、小型作业可能把全部页表项放入快表中、小型作业可能把全部页表项放入快表中中, ,大型作业只能放入一部分。大型作业只能放入一部分。71命中率命中率(%)(%)有效访问时间有效访问时间T=hT=h* *t1+(1-h)ts(ns)t1+(1-h)ts(ns) 0 0 50 50 80 80 90 90 98 98T=0T=0* *120+1120+1* *220=220220=220T=0.5T=0.5* *120+0.5120+0.5* *220=170220=170T=0.8T=0.8* *120+0.212

44、0+0.2* *220=140220=140T=0.9T=0.9* *120+0.1120+0.1* *220=130220=130T=0.98T=0.98* *120+0.02120+0.02* *220=122220=122 通常通常, ,联想寄存器的命中率为联想寄存器的命中率为80%90%,80%90%,有效访问有效访问时间只比单周期增加了时间只比单周期增加了30%40%,30%40%,如果不引入则访问时如果不引入则访问时间延长一倍间延长一倍. .4.5.3 4.5.3 访问内存的有效时间访问内存的有效时间724.5.4 4.5.4 两级和多级页表两级和多级页表 现代的大多数计算机系统，

45、都支持非常大现代的大多数计算机系统，都支持非常大的逻辑地址空间，页表应非常大。的逻辑地址空间，页表应非常大。 如如:32:32位地址空间位地址空间, ,页面大小为页面大小为1212位位(4KB)(4KB)时时, ,则页数为则页数为1M,1M,即页表项为即页表项为1M.1M.如果一个页表项占如果一个页表项占用用4 4个字节个字节, ,故每个进程只是页表就要占用故每个进程只是页表就要占用4MB4MB的的内存空间内存空间, ,并且这些内存空间还必须是连续的。并且这些内存空间还必须是连续的。 对于内存来说对于内存来说, ,要有大的连续空间用于页表要有大的连续空间用于页表不现实。不现实。73通过两个方面

46、来解决这一问题：通过两个方面来解决这一问题：n对页表所需的内存空间，采用离散分配对页表所需的内存空间，采用离散分配方式来解决难以找到一块连续的大内存空方式来解决难以找到一块连续的大内存空间问题间问题. .n只将当前需要的部分页表调入内存只将当前需要的部分页表调入内存, ,其余其余的页表仍然驻留在磁盘上的页表仍然驻留在磁盘上, ,只有需要时再只有需要时再调入内存。调入内存。74(1)(1)两级页表两级页表: 为了避免页表需要大的连续内存空间为了避免页表需要大的连续内存空间, ,利利用将页表进行分页的办法。用将页表进行分页的办法。n页表的页面大小等于内存物理块的大小；页表的页面大小等于内存物理块的

47、大小；n对页表的页面进行编号；对页表的页面进行编号；n为分散的页表再建立一张页表为分散的页表再建立一张页表, ,称为外层页称为外层页表；表；n在外层页表中记录有页表页面号与页表所在外层页表中记录有页表页面号与页表所在物理块的首址。在物理块的首址。75例例:32:32位物理地址空间位物理地址空间. .页面大小为页面大小为4KB,4KB,一个页一个页表项长度为表项长度为1 1个字节。如果连续页表则需要个字节。如果连续页表则需要1MB1MB的连续空间的连续空间. . 现在用两级页表现在用两级页表: :n 对对1MB1MB的页表进行分页的页表进行分页, ,每页每页4KB,4KB,则需则需250250页

48、；页；n 外层页表则需要外层页表则需要250250项项, ,如果一项为如果一项为4 4个字节个字节, ,外层页表需占用外层页表需占用1KB1KB的内存空间。的内存空间。n 在外层页表中有页表的页面号与页面所在物在外层页表中有页表的页面号与页面所在物理块号映射。理块号映射。n 只要知道进程某页在页表中的页面只要知道进程某页在页表中的页面, ,则可从外则可从外层页面上查到页表页面所在的物理块首址层页面上查到页表页面所在的物理块首址, ,在该在该物理块中相应行得到进程的该页所在物理块号。物理块中相应行得到进程的该页所在物理块号。76101110781742146第一页页表第一页页表114115第第n

49、页页表页页表1468012外部页表外部页表第第0页页表页页表内存空间内存空间0123456711411514680 1 2102301210230121023101110111078107877两级页表的地址变换两级页表的地址变换: :n 在原来的地址变换机构中增加一个外层页表在原来的地址变换机构中增加一个外层页表寄存器寄存器, ,用于存放外层页表的始址用于存放外层页表的始址; ;n 并利用逻辑地址中的外层页号并利用逻辑地址中的外层页号, ,作为外层页表作为外层页表的索引的索引, ,从中找到指定页表分页的首址从中找到指定页表分页的首址; ;n 从页表分页中得到所找页在页表中的项从页表分页中得到

50、所找页在页表中的项; ;n 项中的内容得到物理块号项中的内容得到物理块号. .78具有两级页表的地址变换机构具有两级页表的地址变换机构: p1 p1 p2 p2 p3 p3外部页号 外部页内地址 页内地址逻辑地址外部页表寄存器外部页表页表 db物理地址79(2)(2)多多级页表结构级页表结构: 对于对于3232位位, ,从前面可见两级页表可以解决从前面可见两级页表可以解决. . 对于对于6464位机器，必须采用多级页表，将位机器，必须采用多级页表，将16GB16GB的外层页表再进行分页，也是将各个分页离散地的外层页表再进行分页，也是将各个分页离散地分配到不邻接的物理块中，再利用第二级的外层分配

51、到不邻接的物理块中，再利用第二级的外层页表来映射它们之间的关系。页表来映射它们之间的关系。 SUNSUN公司的公司的SPARCSPARC处理器支持三级页表结构，处理器支持三级页表结构， MotorolaMotorola的的6803068030处理器，则支持四级页表处理器，则支持四级页表结构。结构。804.5.5 反置页表反置页表 在分页系统中为每个进程配置一张页表在分页系统中为每个进程配置一张页表, ,进进程逻辑地址空间中的每一页，在页表中都对应有程逻辑地址空间中的每一页，在页表中都对应有一个页表项。一个页表项。 现代计算机系统进程的逻辑地址空间非常大现代计算机系统进程的逻辑地址空间非常大, ,相应的页表中存在很多项。相应的页表中存在很多项。 但是不是所有的物理块都会放入内存中。这但是不是所有的物理块都会放入内存中。这样引入了反置页表。它为每一个物理