四章节存储管理.ppt

《四章节存储管理.ppt》由会员分享，可在线阅读，更多相关《四章节存储管理.ppt（108页珍藏版）》请在三一文库上搜索。

1、 第四章 存储管理 4.1 引言 4.2 存储管理的功能 4.3 实存管理 4.4虚拟存储器管理 4.5 碎片与抖动问题 o 存储管理是指存储器资 源（主要指内存并涉及 外存）的管理。 n 存储器资源的组织（ 如内存的组织方式） n 地址变换（逻辑地址 与物理地址的对应关 系维护） n 虚拟存储的调度算法 4.1 存储组织 o 存储器的功能是保存数据，存储器的发展方向是高速、大 容量和小体积。 n 内存在访问速度方面的发展 n 硬盘技术在大容量方面的发展 n 存储组织是指在存储技术和CPU寻址技术许可的范围内组织 合理的存储结构。 n 其依据是访问速度匹配关系、容量要求和价格。 n “寄存器-

2、内存-外存”结构 n “寄存器-缓存-内存-外存”结构； o 微机中的存储层次组织： n 访问速度越慢，容量越大，价格越便宜； 返回 存储层次结构 o 快速缓存： n Data Cache n TLB(Translation Lookaside Buffer) o 内存：DRAM, SDRAM等； o 外存：软盘、硬盘、光盘、磁带等； 4.2 存储管理的功能 o 存储分配和回收：分配和回收算法及相应的数据结 构。 o 地址变换： n 可执行文件生成中的链接技术 n 程序加载(装入)时的重定位技术 n 进程运行时硬件和软件的地址变换技术机构 o 存储共享和保护： n 代码和数据共享 n 地址空间

3、访问权限（读、写、执行） o 存储器扩充：存储器的逻辑组织和物理组织； 4.2.1 内存的分配与回收 内存分配按分配的时机不同，可分为静态存储方式和动态存储 方式。 静态存储分配：指内存分配是在作业运行之前各目标模块连接 后，把整个作业一次性全部装入内存，并在作业运行过程中， 不允许作业再申请其它内存空间，或是在内存中移动位置。内 存分配在作业运行前一次性完成。 动态存储分配：作业要求的基本内存空间是 在目标模块装入内存时分配，但在作业运行 过程中，允许作业申请附加的内存空间，或 是在内存中移动，即分配工作可以在作业运 行前及运行过程中逐步完成。 动态存储分配具有较大灵活性，内存利用率 高。

4、4.2.2 地址重定位 重定位：把逻辑地址(编写程序时使用的 地址)转变为内存的物理地址的过程,由操 作系统中的装入程序loader来完成。 返回 1. 逻辑地址、物理地址和地址映射 o 逻辑地址（相对地址，虚地址）：用户的程序经过汇编或编 译后形成目标代码，目标代码通常采用相对地址的形式。 n 其首地址为0，其余指令中的地址都相对于首地址来编址 n 不能用逻辑地址在内存中读取信息。 o 物理地址（绝对地址，实地址）：内存中存储单元的地址。 物理地址可直接寻址。 o 地址映射：将用户程序中的逻辑地址转换为运行时由机器直 接寻址的物理地址。 n 当程序装入内存时, 操作系统要为该程序分配一个合适

5、的内存 空间，由于程序的逻辑地址与分配到内存物理地址不一致, 而 CPU执行指令时，是按物理地址进行的，所以要进行地址转 换。 逻辑地址、物理地址和地址映射 地址映射 BA=1000 Mov R1 200 3456 。 。 。 1200 物理地址空间 Mov R1, data 3456 源程序 Mov R1 200 3456 0 100 200 编译连接 逻辑地址空间 地址映射 300 0 100 200 . . . . . . . . . Mov R1 200 3456 逻辑地址空间 1000 1200 1300 物理地址空间 200 VR + 1000 BR Mov R1 1200 110

6、0 3456 2. 地址重定位 o 优点：不需硬件支持，可以装入有限多道程序 o 缺点：一个程序通常需要占用连续的内存空间， 程序装入内存后不能移动，不易实现共享，内存 利用率低。 地址重定位分为：静态地址重定位和动态地址重定位 。 静态地址重定位：在可执行文件中，列出各个需要重 定位的地址单元和相对地址值。当用户程序被装入内 存时，一次性实现逻辑地址到物理地址的转换，以后 不再转换（一般在装入内存时由软件完成）。即：装 入时根据所定位的内存地址去修改每个重定位地址项 ，添加相应偏移量。 可执行文件在内存中的重定位 o说明：重定位表中列出所有修改的位置。如：重定位表的150表示 相对地址150

7、处的内容为相对地址(即100为从0起头的相对位置)。 在装入时，要依据重定位后的起头位置(2000)修改相对地址。 n重定位修改：重定位表中的150-绝对地址2150(=2000+150) n内容修改：内容100变成2100(=100+2000)。 jmp 150 100150 . Relocation Table 0 jmp 2150 21002150 . 2000 动态重定位 动态运行时的装入程序，在把装入模块装入内存后，并不 立即把装入模块中的相对地址转换为绝对地址，而是把这种地 址转换推迟到程序真正要执行时才进行,通过硬件机构来完成 ，硬件机构一般采用的是重定位寄存器，完成虚拟地址到实

8、际 内存地址的变换。因此， 装入内存后的所有地址都仍是相对 地址。 动态重定位的实现 在每次进行存储器访问时，对取出的逻辑地址加上重定位寄存 器的内容，形成内存地址，重定位寄存器的内容是程序装入内 存的起始地址。 LOAD1,2500 365 0 100 2500 5000 2500 相对地址 10000 重定位寄存器 LOAD1,2500 365 10000 10100 12500 15000 作业J 主存 o 优点： n OS不要求将程序装入连续的内存空间，可以将 一个程序分散存放于不连续的内存空间，内存 中程序可以移动，有利于实现共享。 n 部分地装入程序 ，也便于作业共享同一程序副 本

9、。 o 缺点：需要硬件支持（通常是CPU），OS实现 较复杂。它是虚拟存储的基础。 4.2.3 存储保护 在多道程序设计环境中，要保证各道程序只能在自 己的存储区中活动，不能对别的程序产生干扰和破 坏，不能破坏操作系统的内存区。 由于存储保护检查是针对每个存储访问操作进行的 ，必须由相应的处理器硬件机构支持。 o 存储保护的目的： n 保护系统程序区不被用户侵犯（有意或无意的） n 不允许用户程序读写不属于自己地址空间的数据（ 系统区地址空间，其他用户程序的地址空间） 普遍采用的硬件界限寄存器保护法： （1）上、下界存储保护：是一种简单的存储保护技术 。系统为每一个作业设置一对上、下界寄存器，

10、分 别用来存放当前运行作业在内存空间的上、下边界 地址，来限制用户程序的活动范围。 （2）基址限长存储保护：系统为每个作业设一个基 址寄存器和一个限长寄存器，基址寄存器存放该作 业在内存的首址，限长寄存器存放该作业的长度。 对于存储保护除了防止越界外，还可对某一 区域指定专门的保护。常见的对某一区域的 保护方式有四种： （1）禁止做任何操作 （2）只执行 （3）只读 （4） 读/写 4.2.4 虚拟存储器 o 内存不够用的矛盾。 o 作业全部装入内存造成浪费。 o 程序执行具有局部性规律。 返回 1. 问题的引出 o 在程序装入时，不必将其全部读入到内存，而只需将当 前需要执行的部分页或段读入

11、到内存，就可让程序开始 执行。 o 在程序执行过程中，如果需执行的指令或访问的数据尚 未在内存（称为缺页或缺段），则由处理器通知操作系 统将相应的页或段调入到内存，然后继续执行程序。 o 另一方面，操作系统将内存中暂时不使用的页或段调出 保存在外存上，从而腾出空间存放将要装入的程序以及 将要调入的页或段。只需程序的一部分在内存就可执行 。 返回 2. 虚拟存储的基本原理 3. 虚拟存储器定义 所谓虚拟存储器， 是指具有请求调入功能和置换功能, 能从逻辑上对内存容量加以扩充的一种存储器系统。其运 行速度接近于内存速度，而每位的成本却又接近于外存。 可见，虚拟存储技术是一种性能非常优越的存储器管理

12、技 术，故被广泛地应用于大、 中、 小型机器和微型机中。 在虚拟存储管理中,一般将硬盘作为外存,并且其逻辑地 址空间大小与物理内存大小没有直接关系,由计算机系统的 地址结构决定. 4. 引入虚拟存储技术的好处 o 大程序：可在较小的可用内存中执行较大的 用户程序； o 大的用户空间：提供给用户可用的虚拟内存 空间通常大于物理内存(real memory) o 并发：可在内存中容纳更多程序并发执行； o 易于开发：不必影响编程时的程序结构 4.3 实存管理 实存管理与虚存管理相对应，其特点是作业运行时 ，整个作业的逻辑地址空间必须全部装入内存，当 作业尺寸大于主存可用空间时，该作业无法运行。 常

13、见的实存管理技术有固定分区存储管理、可变式 分区存储管理和纯分页存储管理。 内存分为两个区域：系统区，用户区。系统区仅提 供给OS使用，通常是放在内存的低址部分；用户 区是指除系统区以外的全部内存空间， 提供给用 户使用,应用程序装入到用户区，可使用用户区全 部空间。 4.3.1 固定分区存储管理 基本思想：在作业未装入内存之前，就由操作员或操作 系统把内存划分为若干个固定大小的存储区，除操作系 统占用一个区外，其余区域为操作系统中多个用户共享 ，在系统运行期间，分区大小、数目都不变。 在固定分区存储管理系统中，每个用户作业运行时可分 配到一块足够大的区域，用户作业一次性装入到分配区 ，并限制

14、只能在这个区中运行。 o 特点：适用于多道程序系统和分时系统 n 支持多个程序并发执行 n 难以进行内存分区的共享。 o 问题：可能存在内碎片和外碎片。 n 内碎片：占用分区之内未被利用的空间 n 外碎片：占用分区之间难以利用的空闲分区（通常 是小空闲分区）。 为了进行分区的分配和回收，在固定分区存储管理系统 中，有一张记录 内存配和使用情况的说明表，分区说明 表用来记录各分区的起始地址、分区大小和分区分配状 态。 固定分区分配中的分区表 o 优点：易于实现，开销小。 o 缺点： n 内碎片造成浪费 n 分区总数固定，限制了并发执行的程序数 目。 o 采用的数据结构：分区表记录分区的 大小和使

15、用情况 4.3.2 可变分区存储管理 在作业装入时，按其对内存空间的实际要求 要求进行分配，每个分区的尺寸与进入它的 作业大小相同。 o 优点：没有内碎片。 o 缺点：有外碎片。 在可变式存储管理中，常把空闲区组织成空闲分区表和空闲 分区链表 。 (1) 空闲分区表。 空闲分区包括分区序号、分区起始地址、分区大小的数据 ，空闲分区表要占用一定数量的存储单元存放表，增加了 系统开销。 (2) 空闲分区链表。 空闲分区链表的组织形式：在每个空闲分区的起始部分开 辟出一个单元，存放一个链表指针和该分区的大小，链表 指针指向下一个空闲分区。系统中用一个固定单元作为空 闲分区链表的链表头指针，指向第一块

16、空闲分区首指针， 最后一块空闲分区的链表指针存放链尾标志。链表按空闲 分区在内存的位置顺序由小到大链接起来。空闲分区链表 的组织时，空闲分区的信息放在空闲区内，不会额外增加 系统开销。 1. 空闲分区的组织形式 2.内存的分配和回收 内存的分配 在可变式分区存储管理中，当作业要求一个Xk 大 小的存储空间时，系统从链表头指针开始依次检索 空闲区，找到第一个大于等于Xk的空间。若系统 中所有空闲区都小于Xk，无法分配。若有空闲区 等于Xk大小，则修改链表指针，取消该空闲块， 并向用户返回该空闲区首地址。若该空闲区大于 Xk，则将空闲区一分为二，一个为Xk，分给用户 ，另一个为余下部分，仍留在空闲

17、分区链表中，修 改相应链表指针所指向的地址和空闲区大小。 o 分区释放算法：系统进行回收时，应该检查回收区 与内存中前后空闲区是否相邻，若相邻，需要将相 邻的空闲分区合并成一个空闲分区。若不相邻，应 将空闲区插入到空闲区链表的适当位置。 分区回收 3. 分区分配算法 o 分区分配算法：寻找某个空闲分区，其大小需 大于或等于程序的要求。若是大于要求，则将 该分区分割成两个分区，其中一个分区为要求 的大小并标记为“占用”，而另一个分区为余下 部分并标记为“空闲”。分区的先后次序通常是 从内存低端到高端。 返回 o 首次适应法(first-fit)：将空闲分区按照地址递增的顺 序组织成空闲分区链.为

18、作业分配内存时,系统根据作业 大小, 从头查找，找到符合要求的第一个分区，如果不 等于分区大小，将其分为两部分，一部分给作业，另一 部分仍留在空闲区链表中。 n 该算法的分配和释放的时间性能较好，较大的空闲分区 可以被保留在内存高端。 n 但随着低端分区不断划分而产生较多小分区，每次分配 时查找时间开销会增大。 o 最佳适应法(best-fit)：把空闲分区链表按照分区大小 由小到大进行组织。当有作业申请内存时，扫描整个分 区链,找到进程满足的最小分区(其大小与要求相差最小 的空闲分区) n 从个别来看，外碎片较小，但从整体来看，会形成较多 外碎片。较大的空闲分区可以被保留。 n 回收一个分区

19、时，为了把它插入到空闲区链表的合适位 置，比较费时间。 o 最坏适应算法(worst-fit)：把空闲区按大小 递减的顺序组织成空闲区链表。当用户申请 一个存储区时，检查空闲区链表的第一个空 闲区是否满足要求，若不满足，分配失败； 若满足，则将空闲分区分配给用户，然后修 改和调整空闲区链表。 o 优点是：查询简单，每次分配的总是最大的 空闲区。缺点是：基本不留下小空闲分区， 但较大的空闲分区不被保留。 o 内存紧凑(compaction)：改变进程在内存中 的位置，移动存储器中某些已分配分区中的信 息，使分散在内存中的碎片能汇集成一片，能 分配给其他进程使用。 n 增加了系统开销 n 影响了进

20、程正常运行 n 需要重新定义内存地址 内存紧凑 4.可变式分区的地址重定位 o 可变式分区的地址重定位采用静态重定位，内存中 不能再分配利用的小碎片会越来越多。解决这个问 题的办法就是采用紧凑技术，即把小碎片集中起来 使之成为一个大的分区。实现的方法是移动各用户 分区中的程序，是他们集中于内存的一端，而使碎 片集中于另一端。从而将空闲的碎片连成一个较大 的分区，共需求的作业使用。 o 可变式分区的地址重定位采用动态重定位，在执行 内存分配时，如无足够大空闲块，可实现紧凑操作 。 可变分区的存储保护采用基址限长存储保 护方式。 可变分区存储管理的优点：可以有效解决固 定式分区的内部碎片问题，能有

21、效利用主存 空间，提高多道程序对内存的共享。缺点是 容易产生外部碎片问题，要解决外部碎片问 题增加了计算机硬件成本。 4.3.3 分页存储管理 页式和段式存储管理是通过引入进程的逻辑 地址，把进程地址空间与实际存储位置分离 ，从而增加存储管理的灵活性。分页存储管 理的思想：可以将一个作业分配到几个不连 续的区域内，从而不需要移动主存原有的信 息，可以有效地解决碎片问题。 基本原理 1. 页面 (1) 页面和物理块 分页存储管理，是将一个进程的逻辑地址空间分成若干个大小相等的 页，称为页面或页，并为各页加以编号，从0开始，如第0页、第1页等。程 序加载时，分配其所需的所有页，这些页不必连续。需要

22、CPU的硬件支持。 相应地，也把内存空间分成与页面相同大小的若干个存储块，称为(物理) 块或页框(frame)， 也同样为它们加以编号，如0块、1块等等。在为进程 分配内存时，以块为单位将进程中的若干个页分别装入到多个可以不相邻 接的物理块中。由于进程的最后一页经常装不满一块而形成了不可利用的 碎片，称之为“页内碎片”。 分页式存储管理 (2) 页面大小 在分页系统中的页面其大小应适中。页面若太 小，一方面虽然可使内存碎片减小，从而减少了内 存碎片的总空间， 有利于提高内存利用率，但另一 方面也会使每个进程占用较多的页面，从而导致进 程的页表过长，占用大量内存； 此外，还会降低页 面换进换出的

23、效率。然而，如果选择的页面较大， 虽然可以减少页表的长度，提高页面换进换出的速 度，但却又会使页内碎片增大。因此，页面的大小 应选择得适中，且页面大小应是2的幂，通常为512 B4MB。 小内碎片小；大页表短，管理开销小 ，交换时对外存I/O效率高。 2.分页存储管理中存储块的分配和回收 当作业有存储分配请求时，可以根据逻辑地址 的大小计算出需要的存储块，然后将空闲块 分配给作业使用，记录空闲存储块的方法： 位示图和链表法。 （1）位图法是用存储单元中的二进制位与 存储块相对应，某位的值为0，表示对应的 存储块空闲，其值为1，表示已分配。将这 些二进制位组合在一块，就构成一张位图。 特点：方法

24、简单查找空闲块费时，但回收比 较简单。 （2）链表法 系统设定一个空闲块链表头指针指向链表的 第一个空闲块，在每一个空闲块中包含下一 个空闲块的指针信息。当用户申请内存时， 根据链表头指针顺序分配，回收时，只需将 该块插入表头。 2. 地址结构 分页地址中的地址结构如下： 页号P页内地址W 15 1090 对某特定机器，其地址结构是一定的。若给定一个逻 辑地址空间中的地址为A，页面的大小为L，则页号P和页 内地址d可按下式求得： 页表 用于记录进程的一个页面和对应的内存物理块号. 借助于页表可以实现逻辑地址与物理地址之间的转换. 图 4-11 页表的作用 o 指令所给出地址分为两部分：逻辑页号

25、，页 内偏移地址查进程页表，得物理块号 物理地址，把页表放入内存，存取一个数 据至少要两次访问内存。 3. 地址变换机构 基本的地址变换机构 页式地址变换举例 快表 为缩短查找时间，可以将内存中的页表中最 常用的页号和与之对应物理块号装入到关联 存储器(TLB, Translation Lookaside Buffer)，按内容查找(associative mapping)，即逻辑页号物理页号，和 页表具有并行查找的能力。 具有快表的地址变换机构 将最近访问的页面的页表信息存放在高速缓存中,其中的页表 就是快表.访问快表的速度远远大于访问内存中页表的速度. 存储保护 (1)进行地址变换时，产生

26、的页号应小于页表 长度，否则视为越界。 （2）在页表中增加存取控制和存储保护的信 息，对每一个存储块，可允许四个保护方式 ：禁止做任何操作、只执行、只读 、读/写 ，当要访问某页时，先判断该页的存取控制 和存储保护信息是否允许。 o 优点： n 没有外碎片，每个内碎片不超过页大小。 n 一个程序不必连续存放。 n 主存利用率高，内存分配和回收算法简单。 o 缺点： 程序全部装入内存。 分段存储管理方式的引入 引入分段存储管理方式， 主要是为了满足用户和程序员 的下述一系列需要： 1) 方便编程 2) 信息共享 3) 信息保护 4) 动态增长 5) 动态链接 4.3.4 分段式存储管理 返回 页

27、式管理是把内存视为一维线性空间；而段式管理是 把内存视为二维空间，与进程逻辑相一致。每个作业 由若干个逻辑分段组成，每一分段是一组逻辑意义完 整的信息集合。 简单段式管理的基本原理 分段存储管理是以段为基本存储单位分配内存，每 一段必须是连续的内存空间，将程序的地址空间划 分为若干个段(segment)，程序加载时，分配其所需 的所有段（内存分区），这些段长度不一致且不必 连续；物理内存的管理采用动态分区。需要CPU的 硬件支持。 o 程序通过分段(segmentation)划分为多个模 块，如代码段、数据段、共享段。 n 可以分别编写和编译 n 可以针对不同类型的段采取不同的保护 n 可以按

28、段为单位来进行共享，包括通过动态链 接进行代码共享 o 优点： n 没有内碎片，外碎片可以通过内存紧缩来消除 n 便于改变进程占用空间的大小。 o 缺点： n 进程全部装入内存。 返回 段号段内地址 31 16 15 0 分段存储管理中的逻辑地址具有如下结构： 1. 段表 内存分配: 以段为单位分配,每段各占一块内存区,各段可以离散的 放入内存. 2. 段表 地址变换机构 段表控制寄存器 段表始址段表长度 2100 段号S 越界 1 K 段长 600 段号 0 1 2 3 6 K 4 K 500 200 8 K 9200 基址 位移量W 8292 8K 8292 8692 主存 物理地址 逻辑

29、地址 页式管理和段式管理的比较 (1) 页是信息的物理单位，分页是为实现离散分配方 式，以消减内存的外零头， 提高内存的利用率。或者说 ，分页是出于系统管理的需要，分段是出于用户应用的需 要。段则是信息的逻辑单位，它含有一组意义相对完整的 信息。 分段的目的是为了能更好地满足用户的需要。一 条指令或一个操作数可能会跨越两个页的分界处，而不会 跨越两个段的分界处。 (2) 页的大小固定且由系统决定，由系统把逻辑地址划 分为页号和页内地址两部分，是由机器硬件实现的，因而 在系统中只能有一种大小的页面；而段的长度却不固定， 决定于用户所编写的程序，通常由编译程序在对源程序进 行编译时，根据信息的性质

30、来划分。 (3)逻辑地址表示： 分页的作业地址空间是一维的，各个模块在链接时必须组 织成同一个地址空间；而分段的作业地址空间则是二维的 ，既需给出段名， 又需给出段内地址。 （4）分页的优点体现在内存空间的管理上， 而分段的优点体现在地址空间的管理上。 4.4 虚拟存储器管理 o 内存不够用的矛盾。 o 作业全部装入内存造成浪费。 o 程序执行具有局部性规律。 返回 1. 问题的引出 o 虚拟存储器的基本思想：把内存和外存统一管理形 成一级存储器，作业运行时，只把必须的一部分信 息调入内存，其余部分仍放在外存，当需要时，由 系统自动将其从外存调入内存。 o 程序局部性原理(principle

31、of locality)：指在一 段时间内，程序执行过程中往往是集中地访问某一 部分内存区域中的指令或数据。所以一个大的作业 ，只需要装入其中的一部分就可以正常运行。 返回 虚拟存储器定义 所谓虚拟存储器， 是指具有请求调入功能和置换功能 ， 能从逻辑上对内存容量加以扩充的一种存储器系统。其 运行速度接近于内存速度，而每位的成本却又接近于外存 。可见，虚拟存储技术是一种性能非常优越的存储器管理 技术。 在虚拟存储管理中,一般将硬盘作为外存,并且其逻辑地 址空间大小与物理内存大小没有直接关系,由计算机系统的 地址结构决定. 引入虚拟存储技术的好处 o 大程序：可在较小的可用内存中执行较大的 用户

32、程序； o 大的用户空间：提供给用户可用的虚拟内存 空间通常大于物理内存(real memory) o 并发：可在内存中容纳更多程序并发执行； o 易于开发：与覆盖技术比较，不必影响编程 时的程序结构 虚拟存储技术的特征 o 离散性：物理内存分配的不连续，虚拟地址空间使用 的不连续（数据段和栈段之间的空闲空间，共享段和 动态链接库占用的空间） o 多次性:虚拟存储器在实现上需要将一个作业分多次装 入内存运行 o 对换性：虚拟存储的调入和调出是对部分虚拟地址空 间进行的； o 虚拟性：通过物理内存和快速外存相结合，提供大范 围的虚拟地址空间,从逻辑上扩充内存容量 4.4.1请求分页虚拟存储管理

33、基本思想：在进程开始执行之前，首先从外 存将进程的一部分装入内存开始执行，在执 行过程中若发现要访问的数据或指令不在内 存，便由硬件产生缺页中断信息，动态地装 入相应的页面。当内存无空闲块或分配给该 进程的物理块已用完，而有新的页面需要装 入时，根据某种置换算法淘汰已在内存的某 个页面，装入新的页面，进程继续运行。 动态地址重定位 请求分页中的硬件支持 1. 页表机制 o需要在进程页表中添加若干项 状态位(present bit）：指示该页是否在内存，状态位为0，该页不在内存，状态位 为1，该也在内存。 引用位 ：用于标志页面在内存时是否被访问；置换算法换出页面时作为参考 修改位(modifi

34、ed bit) ：指示该页调入内存是否被修改过。 外存地址：用于指出该页在外存的地址，供调入该页时使用。 在简单页式存储管理的基础上，增加请求调页和页面置换功能。 页号 物理块号 状态位P 引用位 修改位M外存地址 请求分页存储管理中的地 址重定位和缺页中断 由处理器的地 址变换机构产 生缺页中断， 然后调用操作 系统提供的中 断处理例程。 缺页中断处理 保留CPU现场 从外存中找到缺页 内存满否？ 选择一页换出 该页被修改否？ 将该页写回外存 OS命令CPU从外存读缺页 启动I/O硬件 将一页从外存换入内存 修改页表 否 是 是 否 页表项在快表中？ CPU检索快表 访问页表 否 页在内存？

35、 修改访问位和修改位 形成物理地址 地址变换结束 否 页号页表长度? 开始 程序请求访问一页 产生缺页中 断请求调页 修改快表 是 越界中断 是 是 缺页中断的特殊性 o 缺页中断的发生和处理在指令执行期 间产生和进行处理，而不是在一条指 令执行完毕之后。所缺的页面调入之 后，重新执行被中断的指令。 o 一条指令的执行可能产生多次缺页中 断,CPU都会及时处理。 o 发生缺页中断时应保存指令执行的中 间结果。 o 对新分配的物理块应上锁，防止同一 物理块分配给多个进程。 页面分配策略 操作系统为进程分配内存空间时，需要考虑的 因素： （1）分配给一个进程的空间越小，内存中存 放进程越多，减少进

36、程交换时间。 （2）如果进程只有一小部分在内存，缺页中 断率会相当高。 （3）因为程序的局部性原理，分配给一个进 程的主存超过一定限度后，再增加主存空间 ，也不会明显降低进程的缺页率。 在请页式系统中，可采用两种策略分配页框 给进程：固定分配和可变分配。 固定分配：如果进程生命周期中，保持页框 数固定不变，各进程平均分配，根据程序大 小按比例分配，优先权。 可变分配：如果进程生命周期中，页框数目 发生变化，按照缺页率动态调整（高或低 增大或减小常驻集），性能较好。增加算 法运行的开销。 内存置换策略 o 全局替换 将分配给所有进程的内存块固定,让所有进程共享 这些内存块.如果有页面需要换入内存

37、,系统会从所 有的进程中选择合适的页面换出内存。可以在运行 进程之间动态地分配页框。 o 局部替换 如果页面置换算法的作用局限于本进程，当进程有 页面需要换入内存时，只能从当前需要的页面的进 程中选择页面换出到外存。 o 常驻集大小和置换范围的配合： 常驻集指虚拟页式管理中给进程分配的物理页面数目。 n 固定分配+局部置换：这时的主要问题进程开始前要依据 进程类型决定分配多少页面。多了会影响并发水平，少 了会使缺页率过高。 n 可变分配+全局置换：这是采用较多的的一种分配和替换 算法，这时OS会一直维持一定数目的空闲页面，添加到 它的驻留集中，增加中断进程的主存空间，以降低缺页 率，这时的主要

38、问题是置换策略的选择，如何决定哪个 进程的页面将被调出。较好的选择是页面缓冲算法。 n 可变分配+局部置换：新进程装入主存时，根据应用类型 、程序要求，分配一定数目的页框，可用请页式或预调 式完成这个分配，当产生缺页中断时，从产生缺页中断 的进程的驻留集中选一个页面替换，连续评价新进程的 分配，增加或减少分配给进程的页框以改善系统的性能 。 分页虚拟存储的调入策略、分配策略 o 请求页调入 (demand paging)：只调入发生缺页 时所需的页面。 n 优点：容易实现。 n 缺点：对外存I/O次数多，开销较大 o 预先页调入 (prepaging)：在发生缺页需要调入 某页时，一次调入该页

39、以及相邻的几个页。 n 优点：提高调页的I/O效率。 n 缺点：基于预测，若调入的页在以后很少被访问， 则效率低。常用于程序装入时的调页。 返回 1. 调入策略 (fetch policy) 调入策略确定在外存中的页面调入时机。在虚拟页式 管理中有两种常用策略。 2. 从何处调入页面 在请求分页系统中的外存分为两部分：用于存放文件的 文件区和用于存放对换页面的对换区。通常，由于对换区是 采用连续分配方式，而事件是采用离散分配方式，故对换区 的磁盘I/O速度比文件区的高。这样，每当发生缺页请求时 ，系统应从何处将缺页调入内存，可分成如下三种情况： (1) 系统拥有足够的对换区空间，这时可以全部从

40、对换 区调入所需页面，以提高调页速度。为此，在进程运行前， 需要将与该进程有关的文件，从文件区拷贝到对换区。 (2) 系统缺少足够的对换区空间，这时凡是不会被修改 的文件，都直接从文件区调入；而当换出这些页面时，由于 它们未被修改而不必再将它们换出，以后再调入时，仍从文 件区直接调入。但对于那些可能被修改的部分，在将它们换 出时，便须调到对换区，以后需要时，再从对换区调入。 (3) UNIX方式。由于与进程有关的文件都放在文件区， 故未运行过的页面，都应从文件区调入。而对于曾经运行过 但又被换出的页面，由于是被放在对换区，因此在下次调入 时，应从对换区调入。由于UNIX系统允许页面共享，因此

41、，某进程所请求的页面有可能已被其它进程调入内存，此时 也就无须再从对换区调入。 3. 页面调入过程 每当程序所要访问的页面未在内存时，便向CPU发出一 缺页中断，中断处理程序首先保留CPU环境，分析中断原因 后， 转入缺页中断处理程序。该程序通过查找页表，得到该 页在外存的物理块后， 如果此时内存能容纳新页，则启动磁 盘I/O,将所缺的页调入内存，然后修改页表。如果内存已满， 则须先按照某种置换算法从内存中选出一页准备换出；如果 该页未被修改过，可不必将该页写回磁盘；但如果此页已被 修改， 则必须将它写回磁盘，然后再把所缺的页调入内存， 并修改页表中的相应表项，置其存在位为“1”，并将此页表项

42、 写入快表中。在缺页调入内存后，利用修改后的页表，形成 所要访问数据的物理地址，再去访问内存数据。 4.4.2页面置换算法 4.4.2.1 缺页率 4.4.2.2 页面置换算法 4.4.2.1 缺页率(page fault rate) 缺页率表示“缺页次数 / 内存访问次数”(比率)或“缺 页的平均时间间隔的倒数”；是衡量页面置换算法 的指标。 下面我们用到的是局部范围内的置换算法，即系 统为每个作业规定最大的内存占有数，当已占满 规定的内存块数而又有新页面调入时，就从自身 空间中置换一个页面，不允许替换别的作业的页 面。 4.4.2.2 页面置换算法 o 功能：需要调入页面时，选择内存中哪个

43、物理页面被置 换。 o 目标：把未来不再使用的或短期内较少使用的页面调出 ，通常只能在局部性原理指导下依据过去的统计数据进 行预测。 返回 页面置换：把一个页面从内存调换到磁盘的对换区。 1. 最佳(Optimal)置换算法 最佳置换算法所选择的被淘汰页面，选择“未来不再使 用的”或“以后最长时间内不需要访问的页”或“在离当前最远 位置上出现的”页面被置换。采用最佳置换算法，通常可保 证获得最低的缺页率。 这是一种理想情况，是实际执行中 无法预知的，因而不能实现。可用作性能评价的依据。 假定系统为某进程分配了三个物理块， 并考虑有以下 的页面号引用串： 7，0，1，2，0，3，0，4，2，3，

44、0，3，2，1，2，0，1，7，0， 1 进程运行时， 先将7，0，1三个页面装入内存。 以后 ， 当进程要访问页面2时， 将会产生缺页中断。此时OS 根据最佳置换算法， 将选择页面7予以淘汰。 引用串 70 77 0 1 7 0 1 2 2 0 1 03 2 0 3 04 2 4 3 230321 2 0 1 2017 7 0 1 01 页框(物理块） 2 0 3 2. 先进先出页面置换算法(FIFO) 选择最先进入内存或驻留时间最长的页面,应该首先被淘 汰，性能较差。 引用串 70 77 0 1 7 0 1 2 2 0 1 03 2 3 1 04 4 3 0 230321 0 1 3 20

45、17 7 0 2 01 页框 2 3 0 4 2 0 4 2 3 0 2 3 0 1 2 7 1 2 7 0 1 1 进程P有5页程序访问页的顺序为：1, 2, 3, 4, 1, 2, 5, 1, 2, 3, 4, 5； 如果在内存中分配3个页面，则缺页情况如下： 12次访问中有缺页9次； 如果在内存中分配4个页面，则缺页情况如下： 12次访问中有缺页10次； 3. 最近最久未使用页面置换算法(LRU） 选择内存中最近一段时间最久未使用的页面被 置换。这是局部性原理的合理近似，性能接近 最佳算法。 引用串 70 77 0 1 7 0 1 2 2 0 1 03 2 0 3 04 4 0 3 23

46、0321 1 3 2 2017 1 0 7 01 页框 4 0 2 4 3 2 0 3 2 1 0 2 LRU置换算法的硬件支持 (1) 计数器方式 为了记录某进程在内存中各页的使用情况，须为每个 在内存中的进程的页表添加一项,用于记录该页已经使用过 的时间。每使用一次页面,逻辑时钟或计数器的内容被烤贝 到页表时间记录中。 由于需要记录页面使用时间的先后关系，硬件开销太大 (2) 堆栈方式 用栈保存当前使用页面时栈的变化情况 把被访问的页面移到栈顶，于是栈底的是最久未使用页面。 4 Clock置换算法 1. 简单的Clock置换算法 2. 改进型Clock置换算法 由引用位R和修改位M可以组合

47、成下面四种类型的页面： 1类(R=0, M=0): 表示该页最近既未被访问， 又未被修改 ， 是最佳淘汰页。 2类(R=0, M=1)： 表示该页最近未被访问， 但已被修改， 并不是很好的淘汰页。 3类(R=1, M=0)： 最近已被访问， 但未被修改， 该页有 可能再被访问。 4类(R=1, M=1): 最近已被访问且被修改， 该页可能再被 访问。 其执行过程可分成以下三步： (1) 从指针所指示的当前位置开始， 扫描循环队列， 寻 找R=0且M=0的第一类页面， 将所遇到的第一个页面作为所 选中的淘汰页。 在第一次扫描期间不改变引用位R。 (2) 如果第一步失败，即查找一周后未遇到第一类页

48、面， 则开始第二轮扫描，寻找R=0且M=1的第二类页面，将所遇 到的第一个这类页面作为淘汰页。在第二轮扫描期间，将所 有扫描过的页面的引用位都置0。 (3) 如果第二步也失败，亦即未找到第二类页面，则将指 针返回到开始的位置，并将所有的引用位复0。 然后重复第 一步，如果仍失败，必要时再重复第二步，此时就一定能找 到被淘汰的页。 5. 置换算法举例 某程序在内存中分配三个页面，初始为空，页面走向 为4，3，2，1，4，3，5，4，3，2，1，5。 OPT 4 3 2 1 4 3 5 4 3 2 1 5 页1 4 3 2 1 1 1 5 5 5 2 1 1 页2 4 3 3 3 3 3 3 3

49、5 5 5 页3 4 4 4 4 4 4 4 4 4 4 x x x x 3 3 x 3 3x x 3 共缺页中断7次 LRU 4 3 2 1 4 3 5 4 3 2 1 5 页1 4 3 2 1 4 3 5 4 3 2 1 5 页2 4 3 2 1 4 3 5 4 3 2 1 页3 4 3 2 1 4 3 5 4 3 2 x x x x x x x 3 3x x x 共缺页中断10次 FIFO 4 3 2 1 4 3 5 4 3 2 1 5 页1 4 3 2 1 4 3 5 5 5 2 1 1 页2 4 3 2 1 4 3 3 3 5 2 2 页3 4 3 2 1 4 4 4 3 5 5 x x x x x x x 3 3x x 3 共缺页中断9次 缺页率的影响因素 n 页面大小： o 页面很小页表大，页内碎片小，缺页率高 o 页面很大页表小，页内碎片大，缺页率低； n 页面置换算法 n 程序设计的质量 设计程序时要求程序的局部化程度很高，这样缺 页中断次数减少。 局部性原理包括时间局部化和空 间局部化。 时间局部化：一条指令的一次执行和下次执行，一 个数据的一次访问和下次访问都集中在一个