[管理学]第4章 存储管理.ppt

1、第4章 存储管理 内容提要内容提要 本章首先概述了计算机存储系统的层次结构、存储 管理的几个基本概念，然后简要介绍了分区存储管理方 案，详细介绍了分页、分段与段页式存储管理方案，并 详述了虚拟存储管理技术的有关概念、方法和具体实现 技术。 教学目标 1计算机系统的分级存储体系。 2掌握地址映射的基本概念与方法。 3理解分区存储管理的有关概念与方法。 4掌握分页存储管理、的有关概念与方法。 5掌握请求页式存储管理的概念和页面置换算法。 6理解分段、段页式存储管理的概念和相关技术。 第4章 存储管理 众所周知众所周知, ,存存储储器是计算机的重要资源。器是计算机的重要资源。 它不仅要为它不仅要为C

2、PUCPU提供执行的指令和数据提供执行的指令和数据, ,而且而且 还要与还要与I/OI/O系统频繁地进行数据交换。因此系统频繁地进行数据交换。因此, , 如何管理存贮器，使它得到充分利用，这是如何管理存贮器，使它得到充分利用，这是 操作系统的重要课题。操作系统的重要课题。 重要资源 “瓶颈”：关键、 紧张 帕金森定律 内存多大，程序多长 4.1 存储管理概述 4.1.1 计算机存储系统分层结构计算机存储系统分层结构 容量 小 大 速度 高 低 成本 高 低 存取 频度 高 低 在辅助硬件与操作系统的支持下,将不同速度、价 格、容量的存储介质构成为统一的整体,使整个存储子 系统达到了性能与价格的

3、很好权衡。 4.1.2 用户程序的处理过程 用户的程序处理可分为三个阶段 (1) 编译 (2) 链接 (3) 装入 1 1 逻辑地逻辑地址址 用户的程序经过编译后形成目标用户的程序经过编译后形成目标 代码，目标代码通常采用相对地址的代码，目标代码通常采用相对地址的 形式。其形式。其首地址为首地址为0 0，其余指令中的，其余指令中的 地址都地址都相对于首地址相对于首地址0 0来编址。逻辑来编址。逻辑 地址也叫做地址也叫做相对地址相对地址或或虚地址。虚地址。 源程序源程序经编译或连接后，目标代经编译或连接后，目标代 码所限定的地址域叫该程序的码所限定的地址域叫该程序的地址空地址空 间间。 4.1.

4、3 存储管理的几个基本概念存储管理的几个基本概念 2 2 物理地址物理地址 内存中存储单元的地址是内存中存储单元的地址是物理地址物理地址。物理。物理 地址也叫地址也叫绝对地址绝对地址, ,或或实地址实地址。 存存储储空间空间是指物理存是指物理存储储器中全部物理单元的集器中全部物理单元的集 合所限定的空间。合所限定的空间。 思考题思考题: : 地址空间大小由谁决定地址空间大小由谁决定? ? 存储空间大小由谁决定存储空间大小由谁决定? ? 程序可以在地址空间中运行吗程序可以在地址空间中运行吗? ? 4.1.3 存储管理的几个基本概念存储管理的几个基本概念 。 。 。 。 Load A, Data

5、Data 3456 源程序源程序 Load A ,200 3456 0 100 200 编译连接编译连接 逻辑地址空间逻辑地址空间 逻辑地址、物理地址和地址映射 3 3 地址重定位地址重定位(Relocation)(Relocation) Load A, 200 地址映射地址映射 1000 34561200 物理地址空间物理地址空间 1100 4.1.3 存储管理的几个基本概念存储管理的几个基本概念 由于地址空间的逻辑地址往往与分配到的 存储空间的物理地址不一致,而处理机执行用 户程序时,所要访问的指令和数据地址必须是 实际的物理地址。这样必须把逻辑地址转换为 物理地址。 这种把程序相对地址空

6、间的逻辑地址转换 为存储空间的物理地址的工作叫地址重定位, 又叫地址映射或地址变换。 根据用户程序地址变换的时间和所采用的 技术不同,地址重定位的方式可分为静态重定 位和动态重定位两种。 3 3 地址重定位地址重定位(Relocation)(Relocation) (1) 静态重定位 系统需要一个静态 重定位程序。在作业装入时，装入程序 把用户程序地址空间中的指令和数据的 相对地址全部转换成存贮空间的绝对地 址。由于地址转换工作是在程序执行前 集中一次完成，这样在程序执行时要访 问的地址就是实际主存的地址。我们把 这种由装入程序进行的地址变换叫静态 重定位。 3 3 地址重定位地址重定位(Re

7、location)(Relocation) 。 。 静态重定位静态重定位 3 3 地址重定位地址重定位(Relocation)(Relocation) 地址映射地址映射 1000 Load A, 1200 34561200 物理地址空间物理地址空间 Load A, 200 3456 0 100 200 逻辑地址空间逻辑地址空间 1100 3 3 地址重定位地址重定位(Relocation)(Relocation) 静态重定位的优点：静态重定位的优点： 静态重定位不需要硬件支持静态重定位不需要硬件支持, ,因而容易因而容易 实现。实现。 缺点：缺点： 静态重定位是在程序装入时进行的静态重定位是在

8、程序装入时进行的, ,要要 求程序求程序占有连续的存储区；占有连续的存储区；不能实现存储器不能实现存储器 共享共享, ,程序执行时也不允许其代码在主存程序执行时也不允许其代码在主存移移 动动。主存利用率较低主存利用率较低。 (2)(2)动态重定位动态重定位 动态重定位是靠硬件的地动态重定位是靠硬件的地 址转换机构来实现的。址转换机构来实现的。 通常采用的办法是设置一个通常采用的办法是设置一个重定位寄存器重定位寄存器。 在存储管理为程序分配一个主存区域后，装在存储管理为程序分配一个主存区域后，装 入程序把程序和数据入程序把程序和数据原样原样装入到分配的存储装入到分配的存储 区中，然后把这个存储区

9、的起始地址送入区中，然后把这个存储区的起始地址送入重重 定位寄存器定位寄存器中。中。在程序执行时，当访问指令在程序执行时，当访问指令 或数据时或数据时, ,都要进行逻辑地址到绝对地址的转都要进行逻辑地址到绝对地址的转 换换。由于这种。由于这种定位方式是在程序执行过程中定位方式是在程序执行过程中 进行的进行的，所以叫，所以叫动态重定位动态重定位。 3 3 地址重定位地址重定位(Relocation)(Relocation) 假定一个程序装入到起始地址为1000的内 存区中。当CPU执行取指令操作“LOAD A,200” 时,该指令所在的地址为100。这样CPU地址寄 存器的内容为100。为了执行

10、取指令,首先系 统对其进行地址重定位。重定位装置将相对 地址100与重地位寄存器中的1000相加,生成 绝对地址,并将该地址送内存地址寄存器,实 现取指令的操作。 执行该指令时，取操作数也需要进行地址 变换，操作数的逻辑地址为200，变换为物理 地址1200。如下图所示 3 3 地址重定位地址重定位(Relocation)(Relocation) 3 3 地址重定位地址重定位(Relocation)(Relocation) 1100 1200 物理地址空间物理地址空间 + 1000 RR . . . . . . . . . LOAD A , 200 3456 200 1000 1200 Loa

11、d A ,200 3456 0 100 200 逻辑地址空间逻辑地址空间 与静态重定位相比，动态重定位有如下优点： 主存利用率高。 为了充分利用主存,系统可将用户程序从一 个区域移到在主存的另一个区域。移动后,只要 修改重定位寄存器即可。 程序不必占有连续的存贮空间。 便于多用户共享存贮器中的同一程序。 3 3 地址重定位地址重定位(Relocation)(Relocation) 4 存储共享 内存共享：两个或多个进程共用内存中相 同区域 目的： 节省内存空间，提高内存利用率 实现进程通信（数据共享） 共享内容： 代码共享，要求代码为纯代码 数据共享 保护目的： 为多个程序共享内存提供保障,

12、使在内存中的各道程序, 只能访问它自己的区 域，避免各道程序间相互干扰，特别是当一道 程序发生错误时, 不致于影响其他程序的运行。 通常由硬件完成保护功能，由软件辅助实现。 保护系统程序区不被用户侵犯(有意或无意 的) 不允许用户程序读写不属于自己地址空间的 数据 (系统区地址空间，其他用户程序的地址 空间) 5 存储保护与安全 保护过程-防止地址越界 每个进程都有自己独立的进程空间，如果一 个进程在运行时所产生的地址在其地址空间之 外，则发生地址越界。即当程序要访问某个内 存单元时，由硬件检查是否允许，如果允许则 执行，否则产生地址越界中断，由操作系统进 行相应处理。 一般由硬件提供一对寄存

13、器： 基址寄存器：存放起始地址 限长寄存器：存放长度 （上界寄存器/下界寄存器） 5 存储保护与安全 对于允许多个进程共享的存储区域， 每个进程都有自己的访问权限。如果一个 进程对共享区域的访问违反了权限规定， 则发生操作越权。 即读写保护。 5 存储保护与安全 通过虚拟存储技术实现 用户在编制程序时，不应该受内存容量限制, 所以要采用一定技术来“扩充”内存的容量,使 用户得到比实际内存容量大的多的内存空间。 具体实现是在硬件支持下，软硬件相互协 作，将内存和外存结合起来统一使用。通过这 种方法对内存“扩充”，使用户在编制程序时 不受内存限制。 6 内存“扩充” 7 地址映射（地址重定位，地址

14、变换） (1) 逻辑地址（相对地址，虚地址） (2) 物理地址（绝对地址，实地址） (3) 地址映射 4.2.1 单一连续分配 单用户系统在一段时间内，只有一个进程 在内存，故内存分配管理十分简单，内存利用 率低。内存分为两个区域，一个供操作系统使 用，一个供用户使用。 最简单，适用于单用户、单任务的最简单，适用于单用户、单任务的OS。 优点优点：易于管理。：易于管理。 缺点缺点：对要求内存空间少的程序，造成内存浪费；：对要求内存空间少的程序，造成内存浪费； 程序全部装入，很少使用的程序部分也占用内存。程序全部装入，很少使用的程序部分也占用内存。 4.2 分区存储管理 4.2.1 单一连续分配

15、 4.2.2 固定式分区存储管理 分区分配的存贮管理是为了适应多道程分区分配的存贮管理是为了适应多道程 序设计技术而产生的最简单的存贮管理。序设计技术而产生的最简单的存贮管理。 它把主存划分成若干个区域，每个用户占它把主存划分成若干个区域，每个用户占 有一个。根据分区情况，又分为固定式分有一个。根据分区情况，又分为固定式分 区和可变式分区区和可变式分区。 特点：适用于多道程序系统和分时系统特点：适用于多道程序系统和分时系统 支持多个程序并发执行支持多个程序并发执行 难以进行内存共享难以进行内存共享。 固定式分区是适合多道程序的最简单存贮固定式分区是适合多道程序的最简单存贮 管理。它把主存预先划

16、分成几个大小不等的分管理。它把主存预先划分成几个大小不等的分 区。区。分区的划分由计算机的操作员或者由操作 系统给出，并给出分区说明表。 固定式分区管理方案在固定式分区管理方案在IBM 360IBM 360计算机上计算机上 曾使用多年，由操作人员在每天早上根据当天曾使用多年，由操作人员在每天早上根据当天 情况，把存贮器划分成若干个分区。这种方法情况，把存贮器划分成若干个分区。这种方法 简单，易于实现。简单，易于实现。 4.2.2 固定式分区存储管理 举例 某系统的内 存容量为256K, 操作系统占用 低地址的20K, 其余空间划分 成4个固定大小 的分区。 分区号大小始址状态 18 KB20已

17、分配 232 KB28已分配 364 KB60已分配 4132 KB124未分配 4.2.2 固定式分区存储管理 采用这种技术，虽然可采用这种技术，虽然可使多个作业共享使多个作业共享 主存，但主存利用是主存，但主存利用是不充分的不充分的。因为作业的。因为作业的 大小不可能刚好等于某个分区的大小。大小不可能刚好等于某个分区的大小。 小结：小结： 优点优点：易于实现，开销小。：易于实现，开销小。 缺点缺点： 内碎片造成浪费内碎片造成浪费 分区总数固定，限制了并发执行的程序数目。分区总数固定，限制了并发执行的程序数目。 4.2.2 固定式分区存储管理 4.2.3 可变式分区存储管理 动态创建分区：在

18、装入程序时按其初始要求 分配，或在其执行过程中通过系统调用进行分 配或改变分区大小。 优点：没有内碎片。 缺点：有外碎片 Operating System 128 K 896 K Operating System Process 1 320 K 576 K Operating System Process 1 320 K Process 2224 K 352 K Process 1: 320K Process 2 : 224K Process 3: 288K Process 4: 128K 4.2.3 可变式分区存储管理 Operating System Process 1 320 K Pro

19、cess 2 Process 3 224 K 288 K 64K Operating System Process 1 320 K Process 3 224 K 288 K 64K Operating System Process 1 320 K Process 3 288 K 64 K Process 4128 K 96 K 4.2.3 可变式分区存储管理 Operating System 320 K Process 3288 K 64 K Process 4 128 K 96 K Operating System Process 3288 K 64 K Process 4 128 K 9

20、6 K Process 2224 k 96 K Process 5需要100K的空间， 能满足吗？ 4.2.3 可变式分区存储管理 内存紧缩内存紧缩(compaction)(compaction)：将各个占用分区向：将各个占用分区向 内存一端移动。使各个空闲分区聚集在另一内存一端移动。使各个空闲分区聚集在另一 端，然后将各个空闲分区合并成为一个空闲端，然后将各个空闲分区合并成为一个空闲 分区。分区。 对占用分区进行内存数据搬移占用对占用分区进行内存数据搬移占用CPUCPU时时 间间 如果对占用分区中的程序进行如果对占用分区中的程序进行 浮动浮动 ， 则其重定位需要硬件支持。则其重定位需要硬件支

21、持。 紧缩时机紧缩时机：每个分区：每个分区释放后释放后，或内存分，或内存分 配配找不到满足条件的空闲分区时找不到满足条件的空闲分区时 4.2.3 可变式分区存储管理 实现动态分区需要的数据结构实现动态分区需要的数据结构 在动态分区存储管理中，要有相应的数据在动态分区存储管理中，要有相应的数据 结构来登记空闲区的说明信息，它包括空闲区结构来登记空闲区的说明信息，它包括空闲区 的大小和位置。的大小和位置。 不同系统根据设计要求采用不同的结构。不同系统根据设计要求采用不同的结构。 常用的有常用的有表结构和队列结构表结构和队列结构。 系统还要设置了系统还要设置了等待分区队列等待分区队列，当系统中，当系

22、统中 无空闲区或无满足要求的空闲区时，则把申请无空闲区或无满足要求的空闲区时，则把申请 者送入等待队列中，等待别的进程释放内存之者送入等待队列中，等待别的进程释放内存之 后再唤醒队列中的进程。后再唤醒队列中的进程。 空闲区表和空闲区队列举例空闲区表和空闲区队列举例 动态分区的分配和回收 1、分区的分配 在采用分区存储管理的系统中，系统初启后。在采用分区存储管理的系统中，系统初启后。 除操作系统占用一个分区外，其余存储区为一个除操作系统占用一个分区外，其余存储区为一个 大的空闲区。大的空闲区。 分区的分配是指系统根据用户的请求，在空闲分区的分配是指系统根据用户的请求，在空闲 区表或空闲区队列中寻

23、找一个满足用户要求的空区表或空闲区队列中寻找一个满足用户要求的空 闲区，把这个空闲区分配给用户。闲区，把这个空闲区分配给用户。 以空闲区表为例以空闲区表为例，当用户要求一个大小为当用户要求一个大小为SIZE 的存储空间时，系统查询空闲区表，找一个大于的存储空间时，系统查询空闲区表，找一个大于 或等于或等于SIZE的空闲区。的空闲区。 分配时的三种情况 其一其一是系统中无满足要求的空闲区，则分配失败。是系统中无满足要求的空闲区，则分配失败。 其二其二是空闲区大小与是空闲区大小与SIZESIZE相等，则修改空闲区表相等，则修改空闲区表 相应表目，向用户返回该空闲区首址，表示此空闲相应表目，向用户返

24、回该空闲区首址，表示此空闲 区已分给了要求的用户。区已分给了要求的用户。 其三是空闲区大于SIZE,这时将空闲区一分为二。 将一个空闲区分成二部分有两种办法： 一是从空闲区的上部开始划出SIZE大小的 空闲区给用户； 二是从空闲区的底部开始向上划出SIZE大 小的空闲区给用户。 一般常采用第二种办法,因为这样划分时, 余 下 的 部 分 在 空 闲 区 表 中 的 首 地 址 不 变 , 只 需要修改一下大小就行了。 2、分区的回收 当某个进程释放某存储区时，系统首先当某个进程释放某存储区时，系统首先 检查释放区是否与系统中的空闲区相邻，检查释放区是否与系统中的空闲区相邻， 若相邻则把释放区合

25、并到相邻的空闲区中若相邻则把释放区合并到相邻的空闲区中 去，否则把释放区作为一个空闲区插入到去，否则把释放区作为一个空闲区插入到 空闲区表的适当位置。空闲区表的适当位置。 释放区与空闲区相邻的四种情况 说明 释放区与前空闲区相邻：将释放区与前空闲区释放区与前空闲区相邻：将释放区与前空闲区 合并为一个空闲区。其首址仍为前空闲区首址，合并为一个空闲区。其首址仍为前空闲区首址， 大小为释放区大小与空闲区大小之和。大小为释放区大小与空闲区大小之和。 释放区与前后两个空闲区相邻：将这三个区合释放区与前后两个空闲区相邻：将这三个区合 为一个空闲区，其首址为前空闲区首址，大小为为一个空闲区，其首址为前空闲区

26、首址，大小为 这三个区大小之和，并取消原后空闲区表目。这三个区大小之和，并取消原后空闲区表目。 释放区与后空闲区相邻：则把释放区合并到后释放区与后空闲区相邻：则把释放区合并到后 空闲，首地址为释放区首地址，大小为二者大小空闲，首地址为释放区首地址，大小为二者大小 之和。之和。 释放区不与任何空闲区相邻：将释放区作为一释放区不与任何空闲区相邻：将释放区作为一 个空闲区，将其大小和首址插入到空闲区表的适个空闲区，将其大小和首址插入到空闲区表的适 当位置。当位置。 4.3 覆盖技术与交换技术 1 为什么引入？ 在多道环境下扩充内存的方法，用以解决在 较小的存储空间中运行较大程序时遇到的矛盾。 覆盖技

27、术主要用在早期的操作系统中。 交换技术被广泛用于小型分时系统中，交换 技术的发展导致了虚存技术的出现 2 覆盖技术 把程序划分为若干个功能上相对独立的把程序划分为若干个功能上相对独立的程程 序段序段，按照其自身的逻辑结构将那些不会同时，按照其自身的逻辑结构将那些不会同时 执行的程序段执行的程序段共享同一块内存区域。共享同一块内存区域。 程序段先保存在磁盘上，当有关程序段的程序段先保存在磁盘上，当有关程序段的 前一部分执行结束，把后续程序段调入内存，前一部分执行结束，把后续程序段调入内存， 覆盖前面的程序段（内存覆盖前面的程序段（内存“扩大扩大”了）了） 覆盖覆盖：一个作业的若干程序段，共享某一

28、：一个作业的若干程序段，共享某一 个存储空间个存储空间 一般要求作业各模块之间有明确的调用结一般要求作业各模块之间有明确的调用结 构，构，程序员要向系统指明覆盖结构，然后由操程序员要向系统指明覆盖结构，然后由操 作系统完成自动覆盖。作系统完成自动覆盖。 A 8K E 8K F 10K C 10K B 8K D 12K 作业作业X的调用结构的调用结构 作业作业X X的常驻区的常驻区 A A（8K8K） 覆盖区覆盖区0 （10K） 覆盖区覆盖区1 （12K） BC C D E F 2 覆盖技术 作业大小：56K 仅需30K存储空间 缺点： 对用户不透明，增加了用户负担 例：目前这一技术用于小型系统

29、中的系统程 序的内存管理上，MS-DOS的启动过程中，多 次使用覆盖技术；启动之后，用户程序区TPA的 高端部分与COMMAND.COM暂驻模块也是一 种覆盖结构 分析 3 交换技术 引入：多个程序并发执行，可以将暂时不能 执行的程序送到外存中，从而获得空闲内存空 间来装入新程序，或读入保存在外存中而目前 到达就绪状态的进程。交换单位为整个进程的 地址空间。常用于多道程序系统或小型分时系 统中。又称作对换或滚进/滚出(roll-in/roll- out)； 程序暂时不能执行的可能原因：处于 阻塞状态，低优先级（确保高优先级程序 执行）. 原理：暂停执行内存中的进程，将整个进程 的地址空间保存到

30、外存的交换区中（换出 swap out），而将外存中由阻塞变为就绪的 进程的地址空间读入到内存中，并将该进程 送到就绪队列（换入swap in）。 3 交换技术 优点：增加并发运行的程序数目，并且给用户提 供适当的响应时间；编写程序时不影响程序结构. 缺点：对换入和换出的控制增加处理机开销；程 序整个地址空间都进行传送，没有考虑执行过程 中地址访问的统计特性。 考虑的问题： n程序换入时的重定位； n减少交换中传送的信息量，特别是对大程序； n对外存交换区空间的管理. 3 交换技术 4.4 4.4 页式存贮管理页式存贮管理 在分区存储管理中，不论采用什么办法在分区存储管理中，不论采用什么办法

31、都会出现碎片问题，从而降低了内存的利用都会出现碎片问题，从而降低了内存的利用 率。虽然采用压缩存储区的方法可以解决碎率。虽然采用压缩存储区的方法可以解决碎 片问题，但系统开销太大，而无实用价值，片问题，但系统开销太大，而无实用价值， 必须寻求新的技术来解决这一问题，于是分必须寻求新的技术来解决这一问题，于是分 页技术产生了。页技术产生了。 分页技术是由曼彻斯特大学提出，并于分页技术是由曼彻斯特大学提出，并于 19601960年前后在年前后在AtlasAtlas计算机上实现。计算机上实现。这种技这种技 术对操作系统的发展产生了深远影响。术对操作系统的发展产生了深远影响。 1 用户程序划分 把用户

32、程序按逻辑页划分成大小相等的部分,称为 页(page)。从0开始编制页号,页内地址是相对于0 编址 2 逻辑地址 用户程序的划分是由系统自动完成的,对用户是 透明的。一般,一页的大小为2的整数次幂,因此,地 址的高位部分为页号,低位部分为页内地址. 0 111231 页号页号P页内位移量页内位移量W 4.4 4.4 页式存贮管理页式存贮管理 3 内存空间 按页的大小划分为大小相等的区域，称为 块或内存块（物理页面，页框） 4 内存分配 以页为单位进行分配，并按作业的页数多少 来分配。逻辑上相邻的页，物理上不一定相 邻 4.4 4.4 页式存贮管理页式存贮管理 为了实现动态地址变换，还要为该作业

33、建立为了实现动态地址变换，还要为该作业建立 一个页表一个页表，用来记录作业的逻辑页与主存块的映，用来记录作业的逻辑页与主存块的映 射关系。射关系。 n页表包含以下几个表项：页表包含以下几个表项： n页号：登记程序地址空页号：登记程序地址空 间的页号。间的页号。 n块号：登记相应的页所块号：登记相应的页所 对应的内存块号对应的内存块号 n其它：登记与存储信息其它：登记与存储信息 保护有关的信息。保护有关的信息。 页号块号其它 05 165 213 5 页表 4.4 4.4 页式存贮管理页式存贮管理 为作业建立的页表放在为作业建立的页表放在主存主存。页表在主。页表在主 存的存的始址始址和和页表长度

34、页表长度还要保存在进程或作业还要保存在进程或作业 的控制块中。的控制块中。 在页式管理中，系统为每个处理机设立在页式管理中，系统为每个处理机设立 一个一个控制寄存器控制寄存器，用以记录现运行作业的页，用以记录现运行作业的页 表始址和页表长度表始址和页表长度。在作业被选中将要运行。在作业被选中将要运行 前，操作系统中负责恢复现场程序把该作业前，操作系统中负责恢复现场程序把该作业 的页表始址和页表长度送入该控制寄存器，的页表始址和页表长度送入该控制寄存器， 以便地址转换时使用。以便地址转换时使用。 6 6 地址变换地址变换 4.4 4.4 页式存贮管理页式存贮管理 页表长度页表地址 控制寄存器 页

35、号页面号 有效地址 02 13 28 21C4 物理地址 81C4 硬件动态地址转换机构硬件动态地址转换机构工作如下：工作如下： 1 1 把该作业的页表始址和页表长度放入控制把该作业的页表始址和页表长度放入控制 寄存器中。寄存器中。 2 2 将程序计数器内容的页号部分将程序计数器内容的页号部分P P与控制寄存器中与控制寄存器中 的页表长度相比较的页表长度相比较, ,若页号若页号 =L p p . 快表快表 B + 页号页号p p 页内地址页内地址d Pd 物理地址物理地址 页表地址寄存器页表地址寄存器页表长度寄存器页表长度寄存器逻辑地址逻辑地址 具有快表的地址转换机构具有快表的地址转换机构 快

36、速存储器应设计多大才能满足要求呢？快速存储器应设计多大才能满足要求呢？ 多大都是不够的多大都是不够的, ,因为程序会更大因为程序会更大 快速存储器非常昂贵快速存储器非常昂贵 1616个页表表目的快速存储器够吗？个页表表目的快速存储器够吗？ 硬件根据需要将页表中当前需要的少量表目读硬件根据需要将页表中当前需要的少量表目读 入快表，其它表目仍留在内存的页表中入快表，其它表目仍留在内存的页表中, ,当需要时读当需要时读 入新的表目，并淘汰适当的表目。入新的表目，并淘汰适当的表目。 当调度合理时当调度合理时, ,可以达到可以达到9797的效率。也就是说的效率。也就是说 访问页表的速度大致相当了访问快表

37、的速度访问页表的速度大致相当了访问快表的速度, ,考虑到考虑到 快表的速度是内存速度的数倍或数十倍，那么相对快表的速度是内存速度的数倍或数十倍，那么相对 于内存速度，访问页表的时间可以忽略不计。也就于内存速度，访问页表的时间可以忽略不计。也就 是说页地址变换不会造成进程运行速度的下降。是说页地址变换不会造成进程运行速度的下降。 8 8 深入一点的讨论深入一点的讨论 4.4 4.4 页式存贮管理页式存贮管理 优点：解决了碎片问题 便于管理 缺点：不易实现共享 不便于动态连接 9 页式存储管理方案小结 4.4 4.4 页式存贮管理页式存贮管理 4.5 4.5 请求页式存贮管理请求页式存贮管理 1

38、1 虚拟存储器虚拟存储器 前面的存贮管理的特点是作业运行时， 整个作业的地址空间必须全部装入主存。而 当作业的地址空间大于主存可用空间时，该 作业就无法运行。这种存贮管理技术叫实存 管理技术。 与实存管理技术相对应的是虚拟存贮技 术。现在许多功能较强的计算机，无论是微 型、小型、中大型机，均采用了虚拟存贮技 术。 1 1 虚拟存储器虚拟存储器 1)1)、问题的提出：、问题的提出： a a 程序大于内存程序大于内存 b b 程序暂时不执行或运行完是否还要程序暂时不执行或运行完是否还要 占用内存占用内存 4.5 4.5 请求页式存贮管理请求页式存贮管理 虚拟存储器的虚拟存储器的基本思想基本思想是：

39、程序、数是：程序、数 据、堆栈的大小可以超过内存的大小，操据、堆栈的大小可以超过内存的大小，操 作系统把作系统把程序当前使用的部分保留在内存程序当前使用的部分保留在内存， 而把而把其它部分保存在磁盘其它部分保存在磁盘上，并在需要时上，并在需要时 在在内存和磁盘之间动态交换内存和磁盘之间动态交换。 虚拟存储器支持多道程序设计技术。虚拟存储器支持多道程序设计技术。 1 1 虚拟存储器虚拟存储器 4.5 4.5 请求页式存贮管理请求页式存贮管理 1 1 虚拟存储器虚拟存储器 CPU MMU 内存内存 磁盘磁盘 控制器控制器 总线总线 处理机中的存储管理单元处理机中的存储管理单元 4.5 4.5 请求

40、页式存贮管理请求页式存贮管理 1 1 虚拟存储器虚拟存储器 2) 程序局部性原理程序局部性原理 局部性原理局部性原理(principle of locality)：指程：指程 序在执行过程中的一个较短时期序在执行过程中的一个较短时期, ,所执行的所执行的 指令地址和指令的操作数地址指令地址和指令的操作数地址, ,分别局限于分别局限于 一定区域。表现为：一定区域。表现为： 时间局部性时间局部性：一条指令被执行了，则一条指令被执行了，则 在不久的将来它可能再被执行在不久的将来它可能再被执行； 空间局部性空间局部性：若某一存储单元被使用，若某一存储单元被使用， 则在一定时间内，与该存储单元相邻的则在

41、一定时间内，与该存储单元相邻的 单元可能被使用单元可能被使用。 4.5 4.5 请求页式存贮管理请求页式存贮管理 1 1 虚拟存储器虚拟存储器 3) 3) 虚拟存储技术虚拟存储技术 虚存虚存：把内存与外存有机的结合起来使：把内存与外存有机的结合起来使 用，从而得到一个容量很大的用，从而得到一个容量很大的“内存内存”，这，这 就是就是虚存虚存。 实现思想实现思想：当进程运行时，先将一部分：当进程运行时，先将一部分 程序装入内存，另一部分暂时留在外存，当程序装入内存，另一部分暂时留在外存，当 要执行的指令不在内存时，由系统要执行的指令不在内存时，由系统自动完成自动完成 将它们从外存调入内存工作。将

42、它们从外存调入内存工作。 4.5 4.5 请求页式存贮管理请求页式存贮管理 请求页式存储管理是在前面介绍的页式存请求页式存储管理是在前面介绍的页式存 储管理基础上产生的。储管理基础上产生的。 请求页式管理与页式管理的主要区别请求页式管理与页式管理的主要区别是将是将 作业信息的副本存放在磁盘一类的快速辅助作业信息的副本存放在磁盘一类的快速辅助 存贮器中，当作业被调度运行时，先将作业存贮器中，当作业被调度运行时，先将作业 的较少页装入主存，在执行过程中，访问不的较少页装入主存，在执行过程中，访问不 在主存页时，再将其装入。在主存页时，再将其装入。 在这种情况下，在这种情况下，每个作业地址空间的页每

43、个作业地址空间的页 有的在主存，有的在辅存有的在主存，有的在辅存，为此要修改页表。，为此要修改页表。 2 2 页式虚拟存储管理实现原理页式虚拟存储管理实现原理 4.5 4.5 请求页式存贮管理请求页式存贮管理 l首先增加一个驻留位首先增加一个驻留位, ,用来指示某页是否在用来指示某页是否在 主存。主存。该位为该位为1 1表示该页在主存表示该页在主存, ,为为0 0，则表示，则表示 该页不在主存。在作业执行中访问某页时该页不在主存。在作业执行中访问某页时, ,在在 进行地址转换查页表时进行地址转换查页表时, ,先检查该页对应的先检查该页对应的驻驻 留位留位, ,若为若为1,1,就与静态页式管理一

44、样，完成正就与静态页式管理一样，完成正 常的地址变换。若该页的常的地址变换。若该页的驻留位驻留位为为0,0,则由硬则由硬 件发出一个件发出一个缺页中断缺页中断, ,转操作系统转操作系统, ,负责缺页负责缺页 的处理。的处理。 2 2 页式虚拟存储管理实现原理页式虚拟存储管理实现原理 4.5 4.5 请求页式存贮管理请求页式存贮管理 为了有效选择被淘汰的页，通常页表中为了有效选择被淘汰的页，通常页表中再再 增加两个标志位增加两个标志位：访问位访问位和和修改位修改位。 访问位访问位指示该页最近是否被访问过。指示该页最近是否被访问过。“1”1” 表示访问，表示访问，“0”0”表示没有被访问。表示没有

45、被访问。 修改位修改位指示该页调入主存后是否被修改过。指示该页调入主存后是否被修改过。 “1”1”表示修改过，表示修改过，0 0表示未修改过。表示未修改过。 选择一页淘汰时，要选择访问位为选择一页淘汰时，要选择访问位为0 0、修、修 改位也为改位也为0 0的页。若这样的页没有找到，则选的页。若这样的页没有找到，则选 择访问位为择访问位为0 0修改位为修改位为1 1的页淘汰。的页淘汰。当淘汰这当淘汰这 样一页时，要将被淘汰的页写回到辅存上去，样一页时，要将被淘汰的页写回到辅存上去， 以保证信息的一致性。以保证信息的一致性。 2 2 页式虚拟存储管理实现原理页式虚拟存储管理实现原理 4.5 4.5

46、 请求页式存贮管理请求页式存贮管理 3、页表表项 页号、驻留位、内存块号、外存地址、访 问位、修改位 驻留位（中断位）：表示该页是在内存还 是在外存 访问位：根据访问位来决定淘汰哪页（由 不同的算法决定） 修改位：查看此页是否在内存中被修改过 4.5 4.5 请求页式存贮管理请求页式存贮管理 4 缺页中断 在地址映射过程中在地址映射过程中,所访问的页不在内存所访问的页不在内存,则则 产生产生缺页中断。缺页中断。操作系统接到此中断信号后操作系统接到此中断信号后,就就 调用调用缺页中断处理程序缺页中断处理程序,根据页表中给出的外存根据页表中给出的外存 地址地址,将该页调入内存将该页调入内存,使作业

47、继续运行下去。使作业继续运行下去。由由 于从外存向主存调入一页需要的时间较长于从外存向主存调入一页需要的时间较长,故在故在 调页过程中应将请求调页的进程置为调页过程中应将请求调页的进程置为阻塞状态阻塞状态。 直到该页装入主存再将其唤醒。直到该页装入主存再将其唤醒。另外另外, ,在产生缺在产生缺 页中断时页中断时, ,一条指令并没有执行完一条指令并没有执行完, ,这样在操作这样在操作 系统进行缺页中断处理后系统进行缺页中断处理后, ,应重新执行被中断的应重新执行被中断的 指令。指令。当重新执行时当重新执行时, ,由于要访问的页已在主存由于要访问的页已在主存, , 因此就可以正常地执行下去。因此就

48、可以正常地执行下去。 4.5 4.5 请求页式存贮管理请求页式存贮管理 如果内存中有空闲块，则分配一页，如果内存中有空闲块，则分配一页， 将新调入页装入内存，并修改页表中相应将新调入页装入内存，并修改页表中相应 页表项目的驻留位及相应的内存块号。页表项目的驻留位及相应的内存块号。 若此时内存中没有空闲块，则要若此时内存中没有空闲块，则要淘汰淘汰 某页某页，若该页在内存期间被修改过，则要，若该页在内存期间被修改过，则要 将其写回外存。将其写回外存。 4 缺页中断 4.5 4.5 请求页式存贮管理请求页式存贮管理 4 缺页中断 由图可知，由图可知， 当主存容量增加当主存容量增加 时，缺页中断次时，

49、缺页中断次 数减少，但主存数减少，但主存 容量增加到容量增加到80KB80KB 以后，缺页中断以后，缺页中断 次数的减少就不次数的减少就不 明显了。大多数明显了。大多数 程序都有一个这程序都有一个这 样的特定点样的特定点 试验分析表明：对试验分析表明：对 所有程序来说，要所有程序来说，要 使其有效地工作，使其有效地工作， 它在主存中的页面它在主存中的页面 数应不低于它的总数应不低于它的总 页面数的一半页面数的一半 0 1000 2000 3000 4000 5000 6000 7000 8000 9000 10000 243248648096112128160192 主存大小 M（KB） 缺页

50、次数F 存储容量与缺页中断次数的关系存储容量与缺页中断次数的关系 理想淘汰算法理想淘汰算法最佳页面算法（最佳页面算法（OPTOPT） 淘汰淘汰以后不再需要以后不再需要的或的或最远的将来最远的将来才会用才会用 到的页面到的页面 先进先出页面淘汰算法（先进先出页面淘汰算法（FIFOFIFO） 最简单最简单的算法是先进先出淘汰算法。当淘的算法是先进先出淘汰算法。当淘 汰一页时汰一页时, ,选择在主存选择在主存驻留时间最长驻留时间最长的那一页。的那一页。 为此为此, ,操作系统维护一张当前页表。表的长度操作系统维护一张当前页表。表的长度 为当前运行作业分配的主存块数。另外设置为当前运行作业分配的主存块

51、数。另外设置 一个指针指向最早进入的页。当需要淘汰一一个指针指向最早进入的页。当需要淘汰一 页时，就选择指针所指的页。页时，就选择指针所指的页。 FIFOFIFO算法算法较易实现，但会出现较易实现，但会出现抖动抖动。 5 页面淘汰算法页面淘汰算法 4.5 4.5 请求页式存贮管理请求页式存贮管理 例1：计算缺页次数及命中率 某程序在内存中分配三个页面,初始为空,页 面走向为4,3,2,1,4,3,5,4,3,2,1,5。 先进先出页面淘汰算法（先进先出页面淘汰算法（FIFOFIFO） FIFO 4 3 2 1 4 3 5 4 3 2 1 5 页1 4 4 4 1 1 1 5 5 5 5 5 5

52、 页2 3 3 3 4 4 4 4 4 2 2 2 页3 2 2 2 3 3 3 3 3 1 1 x x x x x x x v v x x v 共缺页中断9次 命中率=3/12*100%=25% FIFO FIFO算法虽然易于实现，但出现抖动外，还算法虽然易于实现，但出现抖动外，还 会有一种会有一种异常现象异常现象。BeladyBelady在在19691969年发现，采用年发现，采用 FIFOFIFO算法时，算法时，为作业分配的主存块越多，反而缺为作业分配的主存块越多，反而缺 页中断次数越多页中断次数越多。这种奇怪的现象就叫做。这种奇怪的现象就叫做BeladyBelady 异常异常。下面举例

53、说明这一异常。某作业有。下面举例说明这一异常。某作业有5 5个页个页 面，执行时引用的页序列为：面，执行时引用的页序列为： 0,1,2,3,0,1,4,0,1,2,3,40,1,2,3,0,1,4,0,1,2,3,4。共访问。共访问1212个页面。个页面。 下图给出该作业的页面踪迹。图中下图给出该作业的页面踪迹。图中(a)(a)给出分配给出分配3 3 个存贮块个存贮块时的页面访问情况，共产生时的页面访问情况，共产生9 9次缺页中次缺页中 断。图中断。图中(b)(b)是是4 4个主存块个主存块时却产生了时却产生了1010次中断。次中断。 缺页用缺页用“x”x”成功用成功用“v”v”表示。表示。

54、先进先出页面淘汰算法（先进先出页面淘汰算法（FIFOFIFO） 先进先出页面淘汰算法（先进先出页面淘汰算法（FIFOFIFO） 图图 采用采用FIFOFIFO的的BeladyBelady异常异常. . 0 1 2 3 0 1 4 0 1 2 3 4 x x x x x x x v v x x v 444443330004 22 33 2 1 0 1 0 1 0 1 0 1 0 2 1 2 1 2 1 （a)分配三个内存块时，缺页9次。 0 2 x x x x v v x x x x x x 3 4 11 0 3 222 1 0 44 0 1 33 2 0 44 1 2 33 2 1 00 1

55、2 33 2 1 000 11 0 1 2 3 0 1 4 0 1 2 3 4 （b)分配四个内存块时，缺页10次 最近最少使用的页面淘汰算法最近最少使用的页面淘汰算法(LRU)(LRU)这种这种 算法是淘汰在最近一段时间里算法是淘汰在最近一段时间里最少使用最少使用的页的页 面。它是根据程序执行时所具有的局部性原面。它是根据程序执行时所具有的局部性原 理考虑的。所谓理考虑的。所谓局部性原理局部性原理，是指在一段时，是指在一段时 间，进程集中在一组子程序或循环中执行，间，进程集中在一组子程序或循环中执行， 导致所有的存贮器访问局限于进程地址空间导致所有的存贮器访问局限于进程地址空间 的一个固定子

56、集。的一个固定子集。 LRULRU算法算法是较好的一个算法。但为实现是较好的一个算法。但为实现LRULRU， 系统的开销太大。系统的开销太大。 最近最少使用的页面淘汰算法最近最少使用的页面淘汰算法(LRU)(LRU) 多少多少- -有无有无 最近最久未使用页面淘汰算法最近最久未使用页面淘汰算法 仍然难以实现仍然难以实现-现在一般采用近拟现在一般采用近拟LRULRU算法算法 最近最少使用的页面淘汰算法最近最少使用的页面淘汰算法(LRU)(LRU) 例2：计算缺页次数 某程序在内存中分配三个页面,初始为空,页 面走向为4,3,2,1,4,3,5,4,3,2,1,5。 LRU 4 3 2 1 4 3

57、 5 4 3 2 1 5 页1 4 4 4 1 1 1 5 5 5 2 2 2 页2 3 3 3 4 4 4 4 4 4 1 1 页3 2 2 2 3 3 3 3 3 3 5 x x x x x x x v v x x x 共缺页中断10次 命中率=2/12*100%=16.7% 最近最少使用的页面淘汰算法最近最少使用的页面淘汰算法(LRU)(LRU) LRULRU近似算法近似算法： 在页表中增加一访问位，每当访问一页时， 将该页的访问位由硬件置1，软件周期（T）性 地将所有访问位置0。在时间T内，访问过的页 其访问位为1，反之为0，淘汰为0 的页。 缺点：T难定。太小，访问位为0的页相当多，

58、 所选的不一定是最久未用的。太大，所有页的 引用位可能都为1，找不到合适的淘汰页。 练习 某程序在内存中分配四个块，访问页的 走向为4，2，3，2，4，5，2，4，2，3， 1，4，按LRU 、 FIFO、OPT算法分别计 算缺页次数,假设开始时所有页均不在内存。 在虚存中，页面在内存与外存之间频繁在虚存中，页面在内存与外存之间频繁 调度，以至于调度页面所需时间比进程实调度，以至于调度页面所需时间比进程实 际运行的时间还多，此时系统效率急剧下际运行的时间还多，此时系统效率急剧下 降，甚至导致系统崩溃。这种现象称为降，甚至导致系统崩溃。这种现象称为颠颠 簸簸或或抖动抖动 原因：原因： 页面淘汰算法不合理页面淘汰算法不合理 分配给进程的物理页面数太少分配给进程的物理页面数太少 6、颠簸（抖动） 4.5 4.5 请求页式存贮管理请求页式存贮管理 4.6 4.6 段式存储管理段式存储管理 1 段式存储管理基本思想 用户程序划分 按程序自身的逻辑关系划分为若干个程序 段，每个程序段都有一个段名，且有一个段号。 段号从0开始，每一段段内也从0开始编址，段 内地址是连续的 逻辑地址 段号 段内地址 1 段式存储管理基本思想 内存划分 内存空间被动态地划分为若干个长度不相 同的区域，称为物