1 第四章存储器管理 4 1存储器的层次结构4 2程序的装入和链接4 3连续分配方式4 4基本分页存储管理方式4 5基本分段存储管理方式4 6虚拟存储器的基本概念4 7请求分页存储管理方式4 8页面置换算法4 9请求分段存储管理方式 2 第四章存储器管理 为多道程序的运行提供良好的环境 主要任务 方便用户使用存储器 提高存储器的利用率 逻辑上扩充内存 内存分配 主要功能 内存保护 地址映射 内存扩充 3 4 1存储器的层次结构 4 1 1多级存储器结构 图4 1计算机系统存储系统结构 4 4 1存储器的层次结构 4 1 1多级存储器结构 图4 1计算机系统存储系统结构 5 4 1存储器的层次结构 4 1 2主要存储器 1 主存储器 内存 主要存放CPU当前使用的程序和数据 寄存器 6 3 高速缓存 存放CPU在当前一小段时间内多次使用的程序和数据 2 辅助存储器 外存 存放大量的后备程序和数据 4 磁盘缓存 7 4 2程序的装入和链接 图4 2对用户程序的处理步骤 8 4 2程序的装入和链接 4 2 1程序的装入 9 4 2程序的装入和链接 4 2 1程序的装入 10 4 2 1程序的装入 1 绝对装入方式 AbsoluteLoadingMode 1 程序中使用绝对地址 2 程序装入内存指定地址段 3 程序员熟悉内存的使用情况 4 程序动态修改或装入困难 11 2 可重定位装入方式 RelocationLoadingMode 图4 3作业装入内存时的情况 LOAD1 12500 12 3 动态运行时装入方式 DenamleRun timeLoading 把相对地址到绝对地址的转换推迟到程序真正执行时才进行 重定位 装入时对目标程序中指令和数据地址的修改过程 静态重定位 只在程序装入时进行一次地址变换 动态重定位 地址变换过程在程序执行期间 随着对每条指令或数据的访问而自动进行 13 4 2 2程序的链接 图4 3程序链接示意图 程序链接 将几个目标模块装配成一个装入模块 14 需要解决两个问题 1 对相对地址进行修改 2 变换外部调用符号 4 2 2程序的链接 1 静态链接方式 StaticLinking 2 装入时动态链接 Load timeDynamicLinking 装入时动态链接的优点 1 便于修改和更新 2 便于实现对目标模块的共享 3 运行时动态链接 Run timeDynamicLinking 15 4 3连续分配方式 4 3 1单一连续分配 1 只能用于单用户 单任务操作系统 2 内存分为系统区和用户区两部分 4 3 2固定分区分配 1 划分分区的方法 1 分区大小相等 2 分区大小不等 16 4 3 2固定分区分配 1 划分分区的方法 1 分区大小相等 2 分区大小不等 17 2 内存分配 图4 5固定分区使用表 4 3 2固定分区分配 18 19 MultiprogrammingwithFixedPartitions 20 4 3 3动态分区分配 1 分区分配中的数据结构 空闲分区表 2 空闲分区链 图4 5空闲链结构 21 22 23 2 分区分配算法 1 首次适应算法 FirstFit 2 循环首次适应算法 NextFit 3 最佳适应算法 BestFit 4 最坏适应算法 WorstFit 5 快速适应算法 QuickFit 分类搜索算法 4 3 3动态分区分配 24 25 3 分区分配操作 1 分配内存 图4 7内存分配流程 26 2 回收内存 图4 8内存回收时的情况 空闲块合并 27 4 3 6可重定位分区分配 1 动态重定位的引入 图4 9紧凑的示意 28 2 动态重定位的实现 图4 10动态重定位示意图 29 3 动态重定位分区分配算法 图4 11动态分区分配算法流程图 30 1 紧凑的基本概念 2 动态重定位 重定位寄存器 零头 碎片 地址变换 内存地址 相对地址 重定位地址 物理地址 逻辑地址 重定位地址 物理地址 相对地址 基址地址 实地址 虚地址 基地址 3 重定位分区分配算法 紧凑的使用 4 优 缺点 4 3 6可重定位分区分配 31 4 3 7对换 Swapping 1 对换的引入 对换 把内存中暂时不能运行的进程或者暂时不用的程序和数据 调出到外存上 对换是提高内存利用率的有效措施 32 2 对换空间的管理 1 空闲分区表 2 空闲分区链 4 3 7对换 Swapping 3 进程的换出与换入 33 4 4基本分页存储管理方式 离散分区分配 将一个进程 或作业 直接分散地分配到许多不必相邻接的分区中 而不需要进行 紧凑 1 分页存储管理 2 分段存储管理 3 段页式存储管理 离散分区分配方式 包括 34 4 4 1页面与页表 1 将一个进程的逻辑地址空间分成若干个大小相等的片 称为页面或页 并加以编号 2 把内存空间分成与页面相同大小的若干个存储块 称为 物理 块或页框 frame 同样加以编号 3 分配内存时 以块为单位将进程中的若干个页分别装入到多个可以不相邻接的物理块中 4 由于进程的最后一页经常装不满一块而形成了不可利用的碎片 称之为 页内碎片 1 页面 5 页面大小应是2的幂 通常为512B 8KB 35 36 2 分页管理中的地址结构 1 对某特定机器 其地址结构是一定的 2 若给定一个逻辑地址空间中的地址为A 页面的大小为L 则页号P和页内地址d可按下式求得 37 3 页表 图4 12页表的作用 38 4 4 2地址变换机构 1 基本的地址变换机构 图4 13分页系统的地址变换机构 越界中断 39 2 具有快表的地址变换机构 图4 13具有快表的地址变换机构 40 4 4 3两级和多级页表 页表的问题 1 逻辑地址空间越来越大 232 264 2 页表也就变得非常大 占用内存空间越来越大 3 页表要求连续的内存空间存储 解决方案 采用离散分配方式来解决难以找到一块连续的大内存空间的问题 只将当前需要的部分页表项调入内存 其余的页表项仍驻留在磁盘上 需要时再调入 即多级页表 41 1 两级页表 Two LevelPageTable 逻辑地址结构 42 图4 15两级页表结构 43 图4 16具有两级页表的地址变换机构 44 4 5基本分段存储管理方式 4 5 1分段存储管理方式的引入 引入分段存储管理方式 主要是为了满足用户和程序员的下述一系列需要 1 方便编程 2 信息共享3 信息保护4 动态增长 5 动态链接 45 4 5 1分段存储管理方式的引入 46 Segmentation data code 虚地址空间 常数表 代码段 词法树 符号表 调用栈 2K0K 10K0K 16K0K 12K0K 20K0K 第0段 第1段 第2段 第3段 第4段 虚空间 虚空间 虚空间 虚空间 虚空间 a 纯粹分段 程序占一个虚空间 b 分段管理 程序占多个虚空间 47 4 5 2分段系统的基本原理 1 分段 分段管理中的地址结构 3116150 48 图4 17利用段表实现地址映射 2 段表 49 图4 18分段系统的地址变换过程 3 地址变换机构 50 4 分页和分段的主要区别 a 页是信息的物理单位 分页是为实现离散分配方式 以消减内存的外零头 提高内存的利用率 分页仅仅是由于系统管理的需要而不是用户的需要 b 段是信息的逻辑单位 它含有一组其意义相对完整的信息 分段的目的是为了能更好地满足用户的需要 1 划分目的不同 51 a 页的大小固定 由系统决定 是由机器硬件实现的 在一个系统中只能有一种大小的页面 b 段的长度不固定 决定于用户所编写的程序 通常由编译程序在对源程序进行编译时 根据信息的性质来划分 4 分页和分段的主要区别 2 大小和属性不同 52 a 分页的作业地址空间是一维的 即单一的线性地址空间 程序员只需利用一个记忆符 即可表示一个地址 b 分段的作业地址空间则是二维的 程序员在标识一个地址时 既需给出段名 又需给出段内地址 4 分页和分段的主要区别 3 描述方式不同 53 4 5 3信息共享 图4 19分页系统中共享editor的示意图 54 图4 20分段系统中共享editor的示意图 4 4 3信息共享 可重入代码 纯代码 55 4 4 3信息共享 可重入代码 纯代码 56 4 5 4段页式存储管理方式 1 基本原理 图4 21段页式管理的地址空间和地址结构 57 Segmentnumber 18 Segmentnumber Pagetable Page Pagenumber Descriptorsegment offset 4 5 4段页式存储管理方式 58 图4 22利用段表和页表实现地址映射 4 5 4段页式存储管理方式 59 2 地址变换过程 图4 23段页式系统中的地址变换机构 60 ComparePagingandSegmentation 61 连续分配与离散分配的性能比较 62 1 存储系统存在的问题 作业很大 其所求的内存空间超过了内存的部容量 内存容量不足 难以容纳较大量需要运行的作业 2 解决问题的途径 物理上增加内存容量 逻辑上扩充内存容量 4 6虚拟存储器的基本概念 63 1 常规存储器管理方式的特征 1 装入的一次性 2 作业的驻留性 3 运行的局部性 4 6 1虚拟存储器的引入 2 局部性原理 局部性规律 在一较短时间内 程序的执行仅限于某个部分 相应地 它所访问的存储空间也局限于某个区域 1 基本概念 64 2 局部性原理 2 主要原因 顺序性 顺序执行 模块性 循环结构 函数 过程 重复性 过程调用 循环执行 结构性 数据块 结构体 功能块 3 主要表现 时间局限性 空间局限性 65 3 虚拟存储器定义 所谓虚拟存储器 是指具有请求调入功能和置换功能 能从逻辑上对内存容量加以扩充的一种存储器系统 4 虚拟存储器的特点 从用户角度看 系统所具有的内存容量比实际内存容量大得多 但物理上 并非如此 仅把作业一部分装入内存变能运行 逻辑容量由内存容量和外存容量之和所决定 其运行速度接近于内存速度 而每位的成本却又接近于外存 66 5 虚拟存储器的基本条件 内存作业采用段 页 式管理 具有请求调段 页 功能 具有段 页 置换功能 硬件条件 足够大的辅助存储器一定容量的主存虚 实地址映象机构 67 4 6 2虚拟存储器的实现方法 1 分页请求系统 分页系统 请求调页 页面置换 页式虚拟存储器 2 分段请求系统 分段系统 请求调段 分段置换 段式虚拟存储器 3 段页请求系统 段页系统 请求调页 页面置换 段页式虚拟存储器 68 4 6 3虚拟存储器的特征 大容量 只是一种感觉 是虚的 是逻辑上的扩容 运行速度接近于内存速度 而位成本接近于外存 逻辑容量由内存容量与外存容量之和决定 最大容量由地址结构决定 69 4 6 3虚拟存储器的特征 1 离散性 2 多次性 3 对换性 4 虚拟性 相关概念 虚拟地址 实地址 虚拟地址空间 实地址空间 动态地址映象机构 70 4 7请求分页存储管理方式 4 7 1请求分页中的硬件支持 1 页表机制 Typicalpagetableentry 71 2 缺页中断机构 图4 24涉及6次缺页中断的指令 72 4 7 2内存分配策略和分配算法 1 最小物理块数的确定 1 能保证进程正常运行所需的最小物理块数 2 进程应获得的最少物理块数与计算机的硬件结构有关 取决于指令的格式 功能和寻址方式 2 物理块的分配策略 分配策略 固定分配和可变分配置换策略 全局置换和局部置换 1 固定分配局部置换 2 可变分配全局置换 3 可变分配局部置换 73 3 物理块分配算法 1 平均分配算法 2 按比例分配算法 如果系统中共有n个进程 每个进程的页面数为Si 则系统中各进程页面数的总和S为 又假定系统中可用的物理块总数为m 则每个进程所能分到的物理块数为bi 将有 b应该取整 它必须大于最小物理块数 3 考虑优先权的分配算法 74 4 7 3调页策略 1 何时调入 1 预调页策略 2 请求调页策略