《存储器管理》PPT课件.ppt

第四章 存储器管理,* 存储器的层次： 分为寄存器、主存（内存）和 辅存（外存）三个层次。 主存：高速缓冲存储器、主存储器、磁盘缓冲存储器， 主存又称为可执行存储器； 辅存：固定磁盘存储器、可移动的外部存储器； 其可长期保存数据，但不能被处理器直接访问。 本章针对的是主存（内存）的管理,* 存储器管理的主要功能 内存（主存）空间的分配与回收 逻辑地址到物理地址的转换 内存信息（数据）的共享与保护 内存的逻辑扩充（虚拟存储器的实现）,一、相关概念 逻辑地址：目标代码的相对编址 物理地址：内存存储单元的编址 逻辑地址空间：目标代码用逻辑地址编址对应的区域 内存存储空间：内存若干存储单元用物理地址编址对应 的区域 重定位：逻辑地址转换为物理地址的操作（过程）, 为什么要进行重定位 例：, 若不进行地址转换，将会发生运行错误。, 重定位的方式 静态重定位：目标代码装入内存时，一次性进行 逻辑地址到物理地址的地址转换。 动态重定位：目标代码装入内存时，先不进行地址 转换（即原代码装入），在执行时, 再实施地址转换。,二、程序的链接与装入 * 程序的链接（模块拼接） 静态链接：装入前先链接 动态链接：装入时（或在执行时）才进行链接 * 程序的装入 绝对装入：目标代码与装入位置地址相一致; 静态重定位装入：一边装入，一边实现地址转换; 动态重定位装入：原代码装入，待执行时再进行 地址转换。,无论采用何种方式装入，均涉及到内存共享与分配问题 * 分配方式 连续分配：为作业（进程）分配地址连续的存储空间 离散分配：为作业（进程）分配不连续存储空间 三、连续分配存储管理方式 单一连续分配 固定分区分配 可变（动态）分区分配 可重定位分区分配,1）单一连续分配 适用于早期单用户单任务OS,2）固定分区分配 * 算法思想 内存可用区划分成若干个大小固定的存区，每个存区分别装入一道作业的代码（数据）。 * 算法实现 建立分区说明表，记录各分区大小、地址及分配情况 例：,分配：查分区说明表，找到一个足够大 的空闲分区分配之； 回收：将回收分区对应的分区说明表状 态改为“空闲”。,* 优、缺点： 内存可同时装入多道作业代码，算法实现简单； 存在浪费（分区一次性全部分配出去）。,3）动态（可变）分区分配 * 算法思想 事先不划分分区，待作业需要分配内存时，再按需分配划分分区（分区的大小及个数不固定）。 * 算法实现 建立相关数据结构，根据分配策略（或算法）设定算法程序。,数据结构 空闲分区表或 空闲分区链表 例：,记录空闲分区的大小、地址等数据,空闲分区链表情况：,分配：查空闲分区链表，找到第一个足够大的 分区，将其一分为二分配之； 回收：先将回收分区与相邻空闲分区合并再修 改空闲分区链表。 例：回收作业4先与空闲区3合并，再修改链表,分配策略（算法） 首次适应算法 循环首次适应算法 最佳适应算法 最差适应算法 分配程序 实现分配的算法程序 回收算法 前邻接合并 后邻接合并 前、后邻接合并 不邻接处理,实为空闲分区的排列方法,* 优、缺点 按需分配，可解决浪费问题； 分配算法复杂，会产生碎片； 邻接合并系统开销大。 * 碎片问题 碎片:可变分区分配过程中形成的若干个非常小的无法 再利用的小分区。 解决方法:,自然消除（邻接合并） 拼接技术（可重定位分区分配） 离散分配（分页或分段分配）,4）可重定位分区分配 * 算法思想 在可变分区分配算法的基础上，采用动态重定位方式装入程序（数据）。当无足够大的分区供分配时，若总空闲存储容量够用，则将各分区中的内容向内存一端移动（紧凑），使另一端形成一个大的空闲分区，然后再分配。,例：前例若要为作业10分配120k的存储空间，因无足够 大分区（总空闲容量290k），则先进行合并处理。,合并后空闲分区链为：,此时，就可为作业10分配分区空间,* 算法实现 为每个作业（分区）设置一个重定位寄存器，用以 存放对应分区首地址；在进行移动拼接后，只需将 重定位寄存器的值修改为新的地址即可； 为方便移动（搬家）建立相应的数据结构（静态链表、作业表等）。 * 优、缺点 既可实现动态分区分配，又适时解决了碎片问题； 但移动内存需增加系统开销。 可采用离散分配方式解决此问题,四、基本分页存储管理方式 1）算法思想和算法实现 * 算法思想 作业（进程）地址空间被分成大小相同的若干页 内存存储空间被分成大小与页相同的若干块 将连续的页分配并存放到不连续的若干内存块中 建立页表，记录每一页对应的存储块的块号,例：,* 算法实现 建立辅助数据结构 页表：每个作业（进程）一张表 空闲块链表：记录所有未分配空闲块情况（供分配用） 存储分块表：记录内存每一块的使用情况 确定分页的页面大小 太大：存在页内碎片 太小：页表占用空间太多 采用动态重定位装入作业（进程）代码 即在执行时才进行地址转换,2）地址变换过程和地址变换机构 * 工作原理 考察逻辑地址2056，假定一页大小为1K（1024B）,可计算得到物理地址： 逻辑地址/页大小 取整页号 块号 逻辑地址/页大小 取余页内位移量 块号*页大小+页内位移量 物理地址,查页表,* 转换过程分析 逻辑地址机内表示（以16位为例）,若用块号值代替高位的页号值，则,无需计算，只需用块号代替高位的页号，就可立即得到对应的物理地址,* 地址变换机构,* 地址变换过程及改进的地址变换机构 逻辑地址截取高位获得页号用页号查页表， 得到块号拼接地址 此过程需增加一次内存访问（查页表） 利用快表（具有并行查寻能力的一组高速缓冲寄存器） 存放页表（或存放常用的部分表项） 具有快表的地址变换机构如P133图4-14所示： * 两级和多级页表（不要求）,3）内存的分配与回收 * 分配过程 计算作业（进程）所需的页面数查存储分块表， 是否有足够块数的内存供分配 查空闲块链表，分配 内存块分配页表空间，建立页表 修改存储分块表 对应表项数据。 * 回收过程 根据页表，回收（释放）各内存块 回收页表 修改存储分块表等表格。,若够,4）分页分配不足之处 分割分配并存放，使逻辑上完整的模块物理上不完整 不利于内存信息（数据）共享和保护。,五、基本分段存储管理方式,1）算法思想 作业（进程）地址空间按用户设计的逻辑结构分成若干自然段（每一段逻辑上是完整的）； 采用可变分区分配算法为每一段分配分区空间，段与段之间不一定连续存放； 建立段表，记录每一段的段长及段在内存的起始地址（又称基址）。,例：,2）地址结构和地址变换机构 * 地址空间与地址结构 二维空间和地址：,例：,物理地址：50k+12k=62k,* 地址变换机构,* 改进的地址变换机构 与分页系统类似，即用一组寄存器存放段表（快表）,3）分页与分段存储管理的相同与不同之处 *共同点： 采用离散分配解决“碎片”问题 采用动态重定位及地址变换机构实现地址转换,*不同之处（138补充） 分页 分段 地址空间划分 物理（系统） 逻辑（用户） 存储空间分配 不连续的块 不连续的分区 地址空间结构 一维 二维 地址变换 块号与页内位 段始地址与段内 移量拼接 相对地址相加 碎片问题 基本解决 仍存在碎片 共享（保护） 不利于共享 利于共享（保护）,六、段页式存储管理方式 *算法思想 作业地址空间先分段，每段再分页 内存存储空间按页的大小分块 为每段的若干页分配存储块空间，并分块存放 建立段表、页表记录作业段、页与内存块的对应信息 *算法实现 段表存放段号、对应页表始址和页表长度 逻辑地址采用二维结构 建立地址变换机构实现地址转换,*地址变换机构,存储分配与管理方式小结 连续分配：单一连续分配 固定分区分配 动态分区分配 可重定位分区分配 离散分配：基本分页分配 基本分段分配 段页式分配 共同点：作业必须一次性全部装入内存,问题：容量超过内存总容量的作业无法运行； 多道作业总容量超过内存容量，无法同时 装入内存运行。 解决：物理扩充存储器（容量）； 逻辑扩充内存虚拟存储器。,七、虚拟存储器的基本概念与实现 1）局部性原理 在一段时间内，运行的作业程序仅访问（涉及到）一部分作业代码，即不会涉及整个地址空间。 即在一段时间间隔内，仅装入一部分代码,作业照样能正常运行 2）虚拟存储器的引入 作业（进程）运行时，仅装入其代码的一部分到内存，待需要时再装入其余部分，同时还可将不再运行的部分调出内存。 变相地扩充了内存容量,即实现了虚拟存储器。,3）虚存的概念与定义 呈现在用户面前的比实际内存大得多的经逻辑扩充的存储器。 或： 仅将作业（进程）的一部分调入内存，通过调进、调出操作（交换技术），确保作业正常运行的存储器系统。,4）虚存的实现 覆盖与交换技术 请求分页存储管理 请求分段存储管理,例：,八、请求分页存储管理 1）算法思想与实现 * 算法思想 作业分页，内存分块，页与块的大小相等 先装入部分页到内存 待运行需要时再调入新的页，淘汰旧的页（交换）,* 算法实现 软、硬件支持： 系统有足够大的外存及内存；增加相关管理软件。 扩充页表功能（增加页表表项） 增加缺页中断和缺页中断处理功能 扩充后的页表表项如下：,* 地址变换及缺页中断处理 地址变换流程：,缺页中断处理流程：,2）内存块的分配和调进调出处理 所分配的最小内存块数应能保证进程的正常运行。 * 分配策略 固定分配：分配固定数目的内存块给作业,以后不再改变。 可变分配：分配给作业的块数不固定，可动态改变。 * 分配方法 平均分配 按比例分配 根据优先权分配 分配策略、方法的好坏直接影响到系统的工作效率。,* 页的调进方式 初始调入 请求调入 提前（预）调入 * 页的淘汰与调出 又称之为“置换”，是该部分重点讨论的问题。 置换方式 置换的位置 置换的算法,3）页的置换方式 固定分配，局部置换 可变分配，全局置换 可变分配，局部置换 4）置换页在外存的位置 外存文件区 外存对换区,5）页面置换（淘汰）算法 基本原则：被淘汰的页今后或短时间内不会再被调入 常用算法： 最佳算法 先进先出（FIFO）算法 最近最久未使用（LRU）算法 最近最少使用（LFU）算法,* 最佳算法举例 假设某作业访问页面引用序列为： 7, 0, 1, 2, 0, 3, 0, 4, 2, 3, 0, 3, 2, 1, 2, 0, 1, 7, 0, 1 采用固定分配，局部置换淘汰方式（分配三个内存块）,* 先进先出算法举例 (P150-151改错),最佳算法置换6次，先进先出算法置换12次。 最佳算法需知晓页面引用序列，难以实现； 先进先出算法尽管简单、直观，但性能较差。,* 最近最久未使用算法举例 7 0 1 2 0 3 0 4 2 3 0 3 2 1 2 0 1 7 0 1 最近最久未使用算法置换9次。,采用栈结构实现，假定分配5个内存块 页面引用序列为：4, 7, 0, 7, 1, 0, 1, 2, 1, 2, 6。,6）对换 为了提高内存空间的利用率，亦可将暂时不用的页或 暂时不在运行的进程换到外存对换区，在需要或内存容量 宽裕时再将其换到内存，称此操作为对换。 * 整体对换：以进程为单位。 * 部分对换：以页面为单位。 * 换出进程的选择： 可选择优先级最低的进程或处于阻塞状态的进程换到外存。 * 换入进程的选择： 可选择就绪状态的进程或换出时间最久的进程将其换 入内存。,九、请求分段存储管理 1）算法思想与实现 * 算法思想 在基本分段存储管理算法基础上，增加“缺段”中断及处理功能。 * 算法实现 关键是扩充段表功能和缺段中断处理。 扩充后的段表表项如下：,* 地址变换及缺段中断处理 地址变换流程：,缺段中断处理流程：,2）段的保护 越界检查 存取控制 其他措施,3）段的共享 * 基本共享方法,要求： 共享段之代码为“可重入代码”，即不允许任何进程对其进行修改的代码； 段主对应进程不能随意调出共享段。,* 改进后的共享方法 建立一个共享段表，记录每个共享段及所有共享进程的信息。,段存储空间的分配与回收： 分配：第一个使用该段的进程将对应段调入内存，建立 共享段表,表项计数为1； 回收：某进程不需要该段时，仅将计数减1，直至计数 为0，才可回收该段的内存空间。,十、本章小结 1）存储器管理的对象及主要功能 管理对象：内存 主要功能：内存的分配与管理 地址的转换 内存信息的共享与保护 内存的逻辑扩充,2）相关概念和术语 逻辑地址，物理地址 地址空间，存储空间 重定位，静态重定位，动态重定位 碎片，页表，段表，共享段表，快表 虚拟存储器，置换算法 3）分配方式 连