计算机操作系统-第4章存储管理

清华大学出版社 计算机操作系统 刘 腾 红 主编 Computer Operating System 第 4章 存储管理 要求学生了解存储管理的一般性概念 ;重 点掌握分区式管理、分页式管理、分段 式管理以及段页式管理的原理，在学习 中要注意每种管理方式提出的背景和解 决的问题，还要了解系统内部提供的软 硬件支持。 第 4章 存储管理 4.1 存储管理概述 4.2 简单的存储管理 4.3 分页式存储管理 4.4 请求分页存储管理 4.5 分段存储管理 4.6 段页式存储管理 4.7 Windows XP的内存管理 4.1.1 内存概念与存储器层次 计算机系统由计算子系统（处理机与 CPU）、存储子系统、 I/O子系统组成。 如图 4-1所示 4.1 存储管理概述 I/O接口 CPU 地址总线 数据总线 内存 I/O设备 CPU 设备 I/O系统 内存 图 4 1 计算机系统中内存的位置 4.1.1 内存概念与存储器层次 1存储层次 （如图 4-2所示）。 4.1 存储管理概述 图 4 2 计算机存储层次关系 cache 外存 内存 访 问 频 度 变 大 速 度 增 快 价 格 变 贵 容 量 增 大 4.1.2 存储管理 1.内存空间管理 负责内存区域的分配与回收 2重定位 程序存在名字空间、逻辑地址空间和物 理地址空间（如图 4-3所示） 4.1 存储管理概述 B+N M 0 B N 0 符号指令 数据说明 I/O说明 名字空间 地址空间 存储空间 目标程序 作业 i 图 4-3 程序的名空间 、 逻辑地址空间和物理地址空间 举例 :如图 4-4所示 4.1 存储管理概述 装 入 程 序 地 址 映 射 A = d a t a 1 d a t a 1 : 0 2 3 4 m o v r , 2 5 0 0 2 3 4 m o v r , 2 5 0 0 0 2 3 4 编 译 连 接 地 址 映 射 装 入 逻 辑 地 址 空 间 物 理 地 址 空 间 0 1 0 0 2 5 0 0 7 5 0 0 B A = 5 0 0 0 m o v r , 7 5 0 0 0 2 3 4 7 5 0 0 5 1 0 0 5 1 0 0 方 式 一 方 式 二 图 4 4 进程的寻址要求 2重定位 含义 :由相对地址到物理地址的地址变换 (1)静态重定位 程序运行之前进行重定位 缺点： 一旦程序装入后，不能在内存中移动 它要求分配给程序的内存空间连续 ,不 易实现 不利于多进程共享程序 4.1 存储管理概述 (2)动态重定位 程序运行过程中通过硬件来实现虚 -实地 址变换 ,如图 4-5所示 4.1 存储管理概述 5000 7500 mov r,2500 234 处理器的重 定位寄存器 5000 5100 图 4 5 动态重定位的过程 (2)动态重定位 优点 :高效 内存移动简单 ,为存储空间紧缩与内存 碎片处理提供了可能 一个程序可以存放在连续的内存空间， 有利于充分利用内存。 多个进程共享程序或数据段时，可以 只要一个副本。 4.1 存储管理概述 3内存共享 4存储保护 (1)上下界限保护如图 4-6（ a）所示 , 基址、限长寄存器保护如图 4-6（ b） 4.1 存储管理概述 U 进 程 i D 上 界 寄 存 器 下 界 寄 存 器 U D 内 存 0 M - 1 B 进 程 i L 基 址 寄 存 器 限 长 寄 存 器 内 存 0 M - 1 L B (a)上下界限寄存器保护 (b) 基址、限长寄存器保护 图 4 6 界限寄存器的存储保护 4存储保护 (2) 存储键保护 :如图 4-7所示 4.1 存储管理概述 图 4 7 存储保护键的内存保护 相同 保护键 (锁) 程序状态字PSW 保护键 (钥匙) 访存 存储保护 出错 N 内存 Y 5逻辑组织 程序被逻辑化地组织成一系列的模块 6物理组织 7虚拟存储器 这种技术的实质是将外存作为内存的外延 对于应用程序 ,以为系统提供了一个足以 存放当前系统运行的所有用户进程的程序 与数据集的、比实际内存空间大的多的存 储空间，这个存储空间就是虚拟存储器。 4.1 存储管理概述 4.2.1 单一连续区分配 在个人计算机中，管理方法如图 4-8所示 4.2 简单的存储管理 256KB-1 图 4-8 单一连续区的存储空间的组织 256KB-1 0 RAM中的操作系统 用户程序 ROM中的操作系统 （ a） 操作系统占用低地址区 256KB-1 0 0 RAM中的操作系统 用户程序 用户程序 ROM中的操作系统 （ b） 操作系统占用高地址区 （ c） 操作系统分隔在存储器的两端 4.2.1 单一连续区分配 主要缺点有： （ 1）存储器得不到充分利用 （ 2）处理机的利用率比较低 （ 3）周转时间长 （ 4）缺乏灵活性 4.2 简单的存储管理 4.2.2 分区分配 根据分区方式的不同，可分为 : 1固定式分区 (又称为静态分区 )如图 4-9 4.2 简单的存储管理 图 4-9 固定式分区分配 4.2.2 分区分配 2可变式分区 :如图 4-10所示 4.2 简单的存储管理 图 4-10 可变式分区主存分配情况 2可变式分区 （ 1）分区说明表 如图 4-11所示 :图中的两张表的内容是对 图 4-10(d)情况的描述。 4.2 简单的存储管理 始址 大小 占用标志 20KB 32KB J1 52KB 6KB J6 66KB 58KB J5 130KB 100KB J4 空表目 空表目 始址 大小 占用标志 158KB 8KB 可用 124KB 6KB 可用 230KB 26KB 可用 空表目 空表目 空表目 (a)已分配区表 (b)未分配区表 图 4-11 可变式分区说明 2可变式分区 一个回收区 R邻接空闲区的情况有三种， 如图 4-12所示。 4.2 简单的存储管理 （ c） 回收区 R与上下空闲 区邻接 128KB-1 128KB-1 图 4-12 回收区邻接空闲区的三种情况 0 空闲区 F1 R 空闲区 F2 （ a） 回收区 R与上空闲区 邻接 128KB-1 0 0 空闲区 F1 R 作业 X 作业 X R 空闲区 F2 （ b） 回收区 R与下空闲区 邻接 2可变式分区 （ 2）空闲区链 4.2 简单的存储管理 图 4-13 附有表格信息的分区格式 2可变式分区 常用空闲区链的管理方法有三种： 首次适应算法（ First-Fit） 图 4-11(b)的未分配区表用空闲区链表示 时，变为图 4-14。 4.2 简单的存储管理 图 4-14 首次适应算法的空闲区链 2可变式分区 常用空闲区链的管理方法有三种： 最佳适应算法（ Best-Fit） 图 4-11(b)的未分配区表用空闲区链表示 时，变为图 4-15。 4.2 简单的存储管理 图 4-15 最佳适应算法的空闲区链 2可变式分区 常用空闲区链的管理方法有三种： 最坏适应算法（ Worst-Fit） 图 4-11(b)的未分配区表用空闲区链表示 时，变为图 4-16。 4.2 简单的存储管理 图 4-16 最坏适应算法的空闲区链 4.2.2 分区分配 3分区管理的存储保护 （ 1）存储保护键 （ 2）界限寄存器 上、下界防护 如图 4-17(a) 基址、限长防护 如图 4-17(b) 4.2 简单的存储管理 图 4-17 界限寄存器保护 4.2.2 分区分配 4碎片问题 碎片 :是指在已分配区 之间存在着的一些没有 被充分利用的空闲区 解决办法之一 : 采用拼接技术如图 4-18 所示。 4.2 简单的存储管理 4-18 分区分配中的空闲区拼接 4碎片问题 拼接技术的缺点是： 消耗系统资源，为移动已分配区信息要 花费大量的 CPU时间。 当系统进行拼接时，它必须停止所有其 他的工作。对交互作用的用户，可能导 致响应时间不规律；对实时系统的紧迫 任务而言，由于不能及时响应，可能造 成严重后果。 拼接需要重新定义已存入主存的作业。 4.2 简单的存储管理 5分区管理的优、缺点 主要优点为： 实现了主存的共享 实现分区管理的系统设计相对简单，不 需要更多的系统软硬件开销。 实现存储保护的手段也比较简单。 4.2 简单的存储管理 5分区管理的优、缺点 主要缺点为： 主存利用仍不够充分 ,存在严重的碎片 问题 不能实现对主存的“扩充” 和单一连续区分配一样，要求一个作业 运行之前必须全部装入主存。 4.2 简单的存储管理 4.2.3 覆盖与交换 1虚拟存储器 部分装入程序 实现虚拟存储技术要求：外存、主存、 地址变换机构 2覆盖 覆盖：是指同一主存区可以被不同的程 序段重复使用 覆盖的基本原理可用图 4-19加以说明。 4.2 简单的存储管理 2覆盖 覆盖的基本原理可用图 4-19加以说明。 4.2 简单的存储管理 图 4-19 覆盖示例 3交换 采用交换技术，实际上是用辅存作缓冲， 让用户在较小的存储空间中通过不断地换 出作业而运行较大的作业，以提高作业周 转速度和主存利用率。 交换主要是在作业间进行，而覆盖主要 是在作业内进行。 4.2 简单的存储管理 4.3.1页面与物理块 1虚拟存储器 内存物理块或块： 从地址 0开始递增编 号 页或页面： 与内存块大小相等的逻辑地 址空间，也从地址 0开始顺序编号。 按照分页式的概念： 逻辑地址 =页号 +页内地址 如图 4-20所示 4.3 分页式存储管理 页0 页1 1042 0KB 1KB 2KB . 000001 0000010010 页号 页内地址 逻辑地址空间 1042 1 18 图 4 20 逻辑地址空间的分页 4.3.2 页表 对于图 4-21中的作业 2的页表，如图 4-21所示 4.3 分页式存储管理 内 存 作 业 2 的 逻 辑 地 址 空 间 m o v r , 2 5 0 0 0 2 0 0 3 K B 1 K B 2 K B 2 3 4 2 5 0 0 作 业 2 的 页 表 （ 在 内 存 ） m o v r , 2 5 0 0 1 6 K B 8 K B 2 3 4 0 K B 3 K B 4 K B 页 号 物 理 帧 0 1 2 3 8 4 . . . . . . . . . . . . . . . . . . 图 4 21 内存的分页和页表 4.3.3 分页式系统的地址变换 4.3 分页式存储管理 页 号 0 3 1 8 2 4 P C B 处 理 机 的 页 表 寄 存 器 页 号 P 页 内 地 址 W B W 帧 号 1 2 4 作 业 2 的 页 表 m o v r , 2 5 0 0 0 2 0 0 3 K B 1 K B 2 K B 2 3 4 m o v r , 2 5 0 0 1 6 K B 8 K B 2 3 4 0 K B 3 K B 4 K B . . . . . . . . . . . . . . . . . . 3 页 表 首 址 0 作 业 2 的 逻 辑 地 址 空 间 内 存 图 4 22 分页系统的地址变换示意图 4.3.4 采用快表的地址变换 4.3 分页式存储管理 页 表 寄 存 器 P W W b 主 存 中 的 页 表 快 表 （ 联 想 存 储 器 ） 优 先 查 找 内 存 快 表 不 匹 配 再 查 页 表 p b p b + 逻 辑 地 址 物 理 地 址 图 4-23 分页系统中采用快表的地址变换 4.4.1页表 页表应该包括下列信息： 4.4请求分页存储管理 页号 内存块号 状态位 修改位 引用位 保护信息 4.4.2 请求分页系统的地址变换与缺页中断处理 请求分页系统的地址变换如图 4-24所示 请求的页 3被调入后的情况如图 4 25所示 请求页式系统的地址变换与缺页中断处理如图 4 26所示 作 业 2 的 地 址 空 间 作 业 2 的 页 表 页 表 寄 存 器 2 4 5 2 W b 快 表 内 存 0 1 K B 2 K B 3 K B 逻 辑 地 址 物 理 地 址 2 5 0 0 0 . . . 81 3 - . . . 0 3 - 1 -3 2 8 1 0 0 1 3 K B 4 K B 8 K B m o v r , 2 5 0 0 页 0 页 1 m o v r , 2 5 0 0 a d d r , 4 0 9 5 1 2 3 2 3 4 . . . . . . . . . . . . . . . . . . 页 2 将 放 置 的 块 图 4 24 请求页式的地址变换 图 4 25 请求的页 3被调入后的情况 块 号 与 页 内 地 址 形 成 物 理 地 址 还 有 内 存 可 用 ？ 从 页 的 磁 盘 位 置 读 入 可 用 内 存 块 更 新 页 表 执 行 页 面 替 换 访 存 指 令 的 逻 辑 地 址 页 号 页 内 地 址 检 查 联 想 存 储 器 中 的 快 表 访 问 页 表 快 表 匹 配 由 状 态 位 判 页 在 内 存 ？ Y N N Y 缺 页 中 断 唤 醒 阻 塞 更 新 快 表 图 4 26 请求页式系统的地址变换与缺页中断处理 4.4.3 页面淘汰算法 1最佳算法： 如图 4 27(a) 选择距下次被引用时间间隔最大的页来淘汰 2先进先出算法： 如图 4 27(b) 3最近最久未使用算法： 如图 4 27(c)所示 把到目前为止最长时间没有被使用的页淘汰 近似的 LRU算法： 如图 4 27(d)所示 4时钟算法 时钟算法是寻找一个从上次检查以来没有被访 问过的页面 4.4请求分页存储管理 2 3 2 1 5 2 4 5 3 2 5 2 2 2 2 2 2 2 4 4 4 2 2 2 3 3 3 3 3 3 3 3 3 3 3 1 5 5 5 5 5 5 5 5 F F F 2 2 2 2 3 1 5 5 2 2 4 3 3 3 3 1 5 2 2 4 4 3 5 1 5 2 4 4 3 3 5 2 F F F F F F 2 2 2 2 3 1 5 2 4 5 3 3 3 3 3 1 5 2 4 5 3 2 5 1 5 2 4 5 3 2 5 2 F F F F F 2 2 2 2 3 1 5 2 4 3 3 3 3 3 3 1 5 2 4 3 2 2 5 1 5 2 4 5 5 5 5 2 F F F F F （ a）最佳算法 （ b）先进先出算法 （ c）最近最久未使用算法 （ d）近似的 LRU算法 图 4 27 不同淘汰算法对同一页面请求序列的效果 4.5.1 有关分段的基本概念 1.分段 每个分段是由从 0开始编址的连续的地址空间， 它的长度由逻辑信息的内容多少决定 分段系统中 逻辑地址 =段号 S+段内地址 W 4.5 分段存储管理 段号 S 段内地址 W 段号 内存起始地址 段长 2.段表 4.5.2 段式系统的地址变换 1.地址变换： 如图 4-28所示 4.5 分段存储管理 段 号 段 长 内 存 首 址 段 表 寄 存 器 段 表 长 度 寄 存 器 段 号 段 内 地 址 作 业 的 段 表 内 存 逻 辑 地 址 s s w l A A 物 理 地 址 图 4 28分段存储管理的地址变换 4.5.2 段式系统的地址变换 2段表扩展 段在内存首址外还增加： 状态位、访问位、修改位、存取方式、外存 起址、增补位 这样段表中包括了缺段中断处理时所要的各 项信息。 4.5 分段存储管理 3缺段中断： 如图 4-29所示 4.5 分段存储管理 空 闲 区 容 量 足 够 本 段 用 空 白 区 拼 接 ， 形 成 一 个 大 的 空 白 区 淘 汰 一 个 或 几 个 段 以 形 成 一 个 合 适 空 白 区 唤 醒 请 求 进 程 访 存 ， 逻 辑 地 址 段 号 段 内 地 址 段 在 内 存 首 址 段 内 地 址 形 成 物 理 地 址 访 存 由 状 态 位 判 段 在 内 存 Y N N Y 访 问 段 表 内 存 有 合 适 空 闲 区 供 本 段 用 从 外 存 地 址 处 读 入 段 S 修 改 段 表 及 内 存 空 白 块 链 阻 塞 请 求 进 程 N 缺 段 中 断 处 理 图 4 29 分段管理的内存访问与缺段处理 4.5.3 分段式系统共享与保护 1段的共享 4.5 分段存储管理 作 业 i 的 段 表 内 存 段 在 内 存 起 始 地 址 0 1 2 作 业 j 的 段 表 地 址 A 共 享 段 的 内 存 映 象 0 1 2 图 4 30 分段的共享 4.5.3 分段式系统共享与保护 2段的保护 分段存储管理中段的保护主要： 1）地址越界保护 2）存取方式控制 4.5 分段存储管理 4.6.1 基本概念 在段页式系统中， 逻辑地址 =段号 +段内页号 +页内地址 4.6 段页式存储管理 段号 s 段内页号 p 页内地址 w 4.6.2 段页式系统地址变换 4.6 段页式存储管理 段 内 地 址 段 表 首 址 段 表 长 度 段 表 寄 存 器 段 号 页 号 P 页 内 地 址 作 业 2 的 段 表 页 号 段 号 内 存 块 号 b 段 0 的 页 表 段 1 的 页 表 段 2 的 页 表 段 号 0 1 2 3 2 2 物 理 地 址 内 存 b w s p 页 表 长 度 本 段 页 表 首 址 图 4 31 段页式存储管理的地址变换 4.7.1 Windows XP的虚地址映射 默认情况下， 32位的 Windows XP系统能提供 4G的地址空间，如图 4-32所示 4.7 Windows XP的内存管理 0 xFFFFFFFF 0 64KB的区域，用于空 指针赋值（不可访问） 64KB的区域 ， 用于坏 指针赋值 （ 不可访问 ） 2GB的用户地址空间 （ 可使用 ） 2GB的区域 ， 用于操 作系统 （ 不可访问 ） 图 4-32 Windows XP默认的虚拟地址空间 4.7.2 Windows XP中进程页面的状态 Windows XP采用分页管理技术管理系统内存 Windows XP的一个进程页面状态： 1）空闲 2）保留：可通过 Win32 VirtualAlloc和 VirtualAllocEx函数实现 3）提交 4.7 Windows XP的内存管理 4.7.3 Windows XP分页系统的数据结构与地 址变换 Windows XP分页系统采用了二级页表结构， 其虚拟地址结构如图 4-33所示 4.7 Windows XP的内存管理 0 12 11 22 21 31 页目录索引 页表索引 字节索引 虚页号 图 4-33 32位虚拟地址结构 4.7.3 Windows XP分页系统的数据结构与地 址变换 Windows XP虚拟地址变换过程（图 4-34）如下： 1）由页目录寄存器的内容确定当前进程的页 目录在内存中的位置。 2）利用虚拟地址中的“页目录索引”找到所 需页表在页目录中对应的页目录项。页目录 项中包含有对应页表在内存中的物理页框号， 由此查找指定页表在内存中的位置。 4.7 Windows XP的内存管理 4.7.3 Windows XP分页系统的数据结构与地 址变换 Windows XP虚拟地址变换过程（图 4-34）如下： 3）再利用虚拟地址中的“页表索引”查找指 定页面在该页表中对应的页表项。页表项中 包含有指定页面在内存中的物理页框号。 4）最后，利用虚拟地址中的“字节索引”查 找指定数据在物理页框中的位置。 Windows XP分页系统的主要数据结构除了页目 录和页表以外，还有支持快速地址变换的快表 TLB。 4.7 Windows XP的内存管理 物理页 物理内存 页表集 页目录 页目录索引 页表索引 字节索引 页目录寄存器 页框号 页框号 图 4-34 虚拟地址转换为物理地址的变换过程 4.7.4 Windows XP的内存分配技术 1）用户空间存储分配技术： 以页为单位的虚拟内存分配方法、内存映射 文件方法、内存堆栈方法 2）系统空间存储分配技术： 系统初始化时，内存管理程序会创建两种动 态大小的内存缓冲池， 非分页缓冲池和分页缓 冲池。 3）快速内存分配机制，称为后备链表（ Look- Aside List） 4.7 Windows XP的内存管理 4.7.5 Windows XP的缺页中断处理过程 引起缺页错误的情形： 1）用户空间存储分配 技术： 1）进程访问的页面在磁盘上的某个页文件或 映射文件中，尚未进入内存。 处理： 为进程分配一个物理页框，将所需的 页面从外存装入，并放入进程的工作集。 2）所访问的页面在后备链表或修改链表中 处理： 将该页移到进程或系统的工作集中。 4.7 Windows XP的内存管理 3）所访问的页面不包含在进程页目录中，但 该页面存在于系统空间且有效。 处理： 从主系统页目录结构复制相应的页目 录项，并消除异常。 4）对于一个写时复制的页面执行写操作。 处理： 为进程复制一个私有页面备份。 5）几类属于非法访问的操作 4.7 Windows XP的内存管理 4.7.5 Windows XP的缺页中断处理过程 线程也可能发生同样的缺页错误。 类似情况包括： 1）冲突页错误； 2）页面可能已经从虚拟地址空间中删除，并 重新映射； 3）页面的保护权限可能已经被修改等。 4.7 Windows XP的内存管理 4.7.6 Windows XP的页面调度策略 Windows XP采用了请求调页技术，并以簇为 单位装入页面。 当线程发生缺页中断时的“置页策略” 页面置换： 在多处理机系统中， Windows XP 采用了局部“先进先出”置换策略。在单处理 机系统中， Windows XP采用了类似“最近最久 未用（ LRU）”置换策略。 Windows XP采用了可变工作集管理策略。 4.7 Windows XP的内存管理 4.7.7 Windows XP的工作集管理 Windows XP使用的工作集管理采用“可变分 配，局部置换”策略 工作集的调整只能局限在默认最小和最大尺 寸之间 进程工作集和系统工作集 4.7 Windows XP的内存管理 本章首先介绍存储管理的一般性概念， 然后从存储管理解决问题的过程与技术发 展分别讨论了分区式管理、分页式管理、 分段式管理以及段页式管理的原理，学习 中要注意每种管理方式提出的背景和解决 的问题，还要了解系统内部提供的软硬件 支持。 4.8小结