第三章 内存管理
「内存管理」主要功能
五个主要功能
- 内存空间的分配与回收（OS完成主存空间分配回收）
- 地址转换（物理、逻辑地址）
- 内存空间的扩充（虚拟技术逻辑扩充）
- 内存共享（多进程访问）
- 存储保护（各作业有各自存储空间）
「内存管理」程序的链接与装入
- 创建进程要将程序和数据装入内存。
将用户源程序转化为可在内存中执行程序的步骤
- 编译：由编译程序将用户源代码编译成若干目标模块。
- 链接：由链接程序将编译后形成的一组目标模块及它们所需的库函数链接在一起，形成一个完整的装入模块。
- 装入：由装入程序将装入模块装入内存运行。
程序链接的三种方式
- 静态链接🔗
- 装入时动态链接
- 运行时动态链接
内存的装入模块装入内存时的三种方式
- 绝对装入（单道环境，装入绝对地址）
- 可重定位装入（多道环境，对装入地址修改）
- 重定位：装入时对目标程序中指令和数据地址的修改过程。
- 静态重定位：地址变换在进程装入时一次完成。
- 动态运行时装入（也称动态重定位，程序在内存中移动）
- 将相对地址转化为绝对地址的过程推迟到程序执行时进行。
- 需要一个重定位寄存器支持。
- 动态重定位优点：
- 可将程序分配到不连续的存储区。
- 程序运行前可只装入部分代码即可运行，运行期间，动态申请分配内存。
- 便于程序段的共享。
「内存管理」逻辑地址与物理地址
各种定义
- 逻辑地址空间：虚拟地址空间
- 物理地址空间：内存中物理单元的集合，它是地址转换的最终地址。
- 地址重定位：地址转换将逻辑地址转换成物理地址的过程。
「内存管理」进程的内存映像
进程内存映像的五个要素
- 代码段：程序二进制代码；只读；多进程共享；
- 数据段：程序运行时加工对象；全局变量；静态变量；
- 程序控制块（PCB）：存放在系统区；系统控制；
- 堆：存放动态分配的变量；调用malloc()动态向高地址分配空间；
- 栈：实现函数调用；从用户空间高地址向低地址增长；
「内存管理」内存保护
用来确保每个进程都有一个单独的内存空间。
内存保护的两种方法
- 在CPU中设置一对上、下限寄存器，用来判断有无越界。
- 用重定位寄存器（基地址寄存器）和界地址寄存器（限长寄存器）。
- 重定位寄存器含最小物理地址值。
- 界地址寄存器含逻辑地址最大值。
- 内存管理结构把逻辑地址和界地址寄存器比较判断越界，若未越界，加重定位寄存器值映射为物理地址。
注意事项
- 重定位寄存器用来 加，逻辑地址 + 重定位寄存器值 = 物理地址。
- 界地址寄存器用来 比，比较界地址寄存器值和逻辑地址值判断是否越界。
- 加载重定位寄存器和界地址寄存器时必须用特权指令。
「内存管理」内存共享
程序执行时，可为进程配局部数据区，执行中可变部分放入该区域，这样进程可只改动私有局部数据区的内存，不改动共享的代码。
名词解释
- 内存共享：不是所有进程内存空间可共享，是只读区域共享。
- 可重入代码：纯代码，允许多进程访问，不允许进程修改。
「内存管理」内存分配与回收
存储管理方式的发展
- 单一连续分配
固定分区分配 动态分区分配 离散分配方式（页式存储）
「覆盖与交换」覆盖
覆盖的基本思想
- 进程总是只会访问数据的一部分区域，故把用户空间分为一个固定区 + 若干覆盖区。
- 常用部分放入固定区，不常用部分按调用关系分段。
- 即将访问部分放入覆盖区，其他部分放外存，需要时调入覆盖区。
覆盖的特点
- 不需要进程所有信息调入内存就能运行，但是同时运行的代码量不能大于主存容量。
- 内存中能更新的地方只有覆盖区的段，不再覆盖区的段常住内存。
- 覆盖技术对用户和程序员透明。
「覆盖与交换」交换
交换的基本思想
- 换出：等待状态的程序从主存移到辅存。
- 换入：准备竞争CPU运行的程序从辅存移到主存。
注意事项
- 交换 用于不同进程（或作业）之间进行，仍然存活。
- 覆盖 用于同一个程序或进程中，目前已被虚拟内存技术替代，成为历史。
「连续分配管理」单一连续分配
- 内存分为系统区和用户区
- 系统区：仅供操作系统使用，低地址
- 用户区：内存的用户空间被一个程序独占
单一连续分配的优缺点
- 优点：简单、无外部碎片、无须内存保护
- 缺点：仅用于单用户、单任务操作系统，有内部碎片，存储器利用率低
「连续分配管理」固定分区分配
- 最简单的多道存储管理方式
- 用户空间划分若干固定大小区域，每区域只装入一道作业。
划分分区的两种方法
- 分区大小相等：程序太小浪费，程序太大无法装入。
- 分区大小不等：划分多个小分区，适量中分区，少量大分区。
什么是分区使用表？
- 用来方便内存分配，常按分区大小分配，包含各表项包括每个分区的起始地址、大小即状态（是否已分配）。
固定分区的问题
- 程序太大无法放进分区，需要使用覆盖技术使用内存。
- 程序小于分区大小，也要占用一个完整分区，空间浪费，称之为 内部碎片。
「连续分配管理」动态分区分配
- 又称 可变分区分配。
- 根据装入内存的进程实际需要动态分配内存。
- 系统中分区大小和数量是可变的。
- 设置一张空闲分区链(表)，并按始址排序。分配内存时，检索空闲分区链，找到所需的分区，若其大小大于请求大小，便从该分区中按请求大小分割一块空间分配给装入进程(若剩余部分小到不足以划分，则无须分割)，余下部分仍留在空闲分区链中。
动态分区的问题
- 最初的分区是最好的，随时间推移内存中会产生越来越多小的内存块。
- 这些小内存块被称之为 外部碎片。
内部碎片与外部碎片
- 内部碎片（固定分区产生）：
- 分区内部空间有剩余。
- 外部碎片（动态分区产生）：
- 分区外部空间有剩余。
- 用紧凑技术克服，操作系统对进程移动和整理。
动态分区的分配策略
- 首次适应（First Fit）算法
- 空闲分区以地址递增的次序链接。
- 分配内存时，从链首开始顺序查找，找到大小能满足要求的第一个空闲分区分配给作业。
- 临近适应（Next Fit）算法
- 又称循环首次适应算法，由首次适应算法演变而成。
- 不同之处是，分配内存时从上次查找结束的位置开始继续查找。
- 最佳适应（Best Fit）算法
- 空闲分区按容量递增的次序形成空闲分区链，找到第一个能满足要求且最小的空闲分区分配给作业。
- 最坏适应（Worst Fit）算法
- 空闲分区以容量递减的次序链接，找到第一个能满足要求的，即最大的分区，从中分割一部分存储空间给作业。
各种分配策略的优缺点
- 首次适应（First Fit）算法
- 最简单，通常是最好和最快的。
- 使内存低地址出现许多小的空闲分区，每次分配查找都要经过这些分区，增加开销。
- 临近适应（Next Fit）算法
- 试图解决首次适应算法的问题，但是通常比首次适应算法要差。
- 常常导致在内存空间的尾部（因为在一遍扫描中，内存前面部分使用后再释放时，不会参与分配）分裂成小碎片。
- 最佳适应（Best Fit）算法
- 性能通常很差
- 每次最佳的分配会留下很小的难以利用的内存块，会产生最多的外部碎片。
- 最坏适应（Worst Fit）算法
- 性能非常差
- 选择最大的可用块，把最大的连续内存划分开，会很快导致没有可用的大内存块。
动态分区回收内存过程中的几种情况
- 系统根据回收分区的始址，从空闲分区链中找到相应的插入点
- 回收区与插入点的前一空闲分区相邻，将这两个分区合并，并修改前一分区表项的大小为两者之和。
- 回收区与插入点的后一空闲分区相邻，将这两个分区合并，并修改后一分区表项的始址和大小
- 回收区同时与插入点的前、后两个分区相邻，此时将这三个分区合并，修改前一分区表项的大小为三者之和，取消后一分区表项。
- 回收区没有相邻的空闲分区，此时应为回收区新建一个表项，填写始址和大小，并插入空闲分区链。
「非连续分配管理」分页存储管理
分页存储的几个概念
- 页面和页面大小
- 页或页面(Page)：进程中的块；
- 页框或页帧(Page Frame)：内存中的块。
- 块或盘块(Block)：外存以块为划分。
- 地址结构（分页存储管理的逻辑地址结构）
- 页表
- 作用：实现页号到物理块号的地址映射。
- 构成：页表由页表项组成
- 页表项 = 页号 + 物理内存中的块号
- 地址 = 页号 + 页内偏移
页面分配的注意事项
- 页面大小为2的整数幂；
- 页面大小要适中
- 页面太小：会使进程页面过多，页表过长，占用大量内存，增加硬件地址转换开销，降低页面换入/换出效率。
- 页面太大：会使页内碎片过多，降低内存利用率。
基本地址变换结构
- 作用：逻辑地址转换为内存中的物理地址。
- 地址变换借助页表实现，由硬件自动完成。
具有快表的地址变换机构
- 快表（相连存储器）
- 具有并行查找能力的高速缓冲存储器。
- 快表的有效性基于局部性原理。
- 慢表：主存中的页表。
什么是段表？
- 段表的内容
- 段表映射示意图
段表存储的地址变换机构
段的共享与保护
- 段的共享
- 通过两个作业的段表中相应表项指向被共享的段的同一个物理副本实现。
- 纯代码/可重入代码（非临界资源）
- 是不能修改的代码和不能修改的数据 可以共享。
- 可修改的代码和数据 不能共享。
- 段的保护
- 存取控制保护：
- 地址越界保护（越界中断）：
- 将段表寄存器中的段表长度与逻辑地址中的段号比较。
- 将段表项中的段长和逻辑地址中的段内偏移进行比较。
页式管理和段式管理的不同
- 与页式管理不同，段式管理不能通过给出一个整数便确定对应的物理地址，因为每段的长度是不固定的，无法通过整数除法得出段号，无法通过求余得出段内偏移，所以段号和段内偏移一定要显式给出（段号，段内偏移），因此分段管理的地址空间是二维的。 ::
⚠️注意事项
- 页式系统中，逻辑地址的页号和页内偏移量对用户是透明的。
- 段式系统中，段号和段内偏移量必须由用户显式提供。
「非连续分配管理」段页式存储管理
什么是段页式系统？
- 作业的地址空间首先被分成若干逻辑段，每段都有自己的段号，然后将每段分成若干大小固定的页。
- 对内存空间的管理仍然和分页存储管理一样，将其分成若干和页面大小相同的存储块，对内存的分配以存储块为单位。
- 段页式系统的逻辑地址：段号 + 页号 + 页内偏移量。
- 段页式系统的页表结构：段号 + 页表长度 + 页表始址。
- 段页式系统的地址变换：1 进程 = 1 段表 = n 分段 = n 页表。
- 段页式系统的段表寄存器：指出作业段表始址和段表长度。
注意事项
- 在一个进程中，段表只有一个，而页表可能有多个。
段页式系统地址变换过程
- 首先通过段表查到页表始址，然后通过页表找到页帧号，最后形成物理地址。
- 进行一次访问实际需要三次访问主存，可使用快表来加快查找速度，其关键字由段号、页号组成，值是对应的页帧号和保护码。
「虚拟内存管理」虚拟内存
虚拟内存基本概念
- 传统存储管理方式的特征
- 一次性：作业必须一次装入内存。
- 驻留性：作业装入内存后，必须驻留内存。
- 局部性原理
- 时间局部性
- 空间局部性
- 虚拟存储器的三个主要特征
- 多次性：作业无须一次全部装入内存。
- 对换性：作业无须一直驻留内存，可多次调入。
- 虚拟性：逻辑上扩充内存容量。
虚拟内存技术的实现的三种方式
- 请求分页存储管理
- 请求分段存储管理
- 请求段页式存储管理
虚拟内存实现方式需要的硬件支持
- 一定容量的内存或外存
- 页表机制（或段表机制），作为主要数据结构
- 中断机构，当用户程序要访问的部分尚未调入内存，产生中断。
- 地址变换机构，逻辑地址转换为物理地址。
「请求管理方式」请求分页管理
页表机制及字段说明
- 状态位
- 用于指示该页是否已调入内存，供程序访问时参考。
- 访问字段
- 用于记录本页在一段时间内被访问的次数，或记录本页最近已有多长时间未被访问，供置换算法换出页面时参考。
- 修改位
- 标识该页在调入内存后是否被修改过，以确定页面置换时是否写回外存。
- 外存地址
- 用于指出该页在外存上的地址，通常是物理块号，供调入该页时参考。
缺页中断与一般的中断相比的两个区别
- 在指令执行期间而非一条指令执行完后产生和处理中断信号，属于内部异常。
- 一条指令在执行期间，可能产生多次缺页中断。
请求分页的地址变换机构
- 在分页系统地址变换机构的基础上，为实现虚拟内存，又增加了某些功能而形成的，如产生和处理缺页中断，及从内存中换出一页的功能等等。
「请求管理方式」页框分配
什么是驻留集？
- 操作系统决定读取多少页，就给特定的进程分配多少页框，一个进程分配的物理页框的集合就是这个进程的驻留集。
驻留集大小的影响
- 分配给一个进程的页框越少，驻留在主存中的进程就越多，从而可提高CPU 的利用率。
- 若一个进程在主存中的页面过少，则尽管有局部性原理，缺页率仍相对较高。
- 若分配的页框过多，则由于局部性原理，对该进程的缺页率没有太明显的影响。
内存分配策略
- 固定分配局部置换
- 可变分配全局置换
- 可变分配局部置换
物理块调入算法
- 平均分配算法
- 按比例分配算法
- 优先权分配算法
调入页面的时机
- 预调页策略
- 请求调页策略
从何处调入页面
- 系统拥有足够的对换区空间
- 系统缺少足够的对换区空间
- UNIX方式
如何调入页面
「页面置换算法」最佳置换（OPT）
INFO
- 选择的被淘汰页面是以后永不使用的页面，或是在最长时间内不再被访问的页面，以便保证获得最低的缺页率。
- 该算法无法实现，但可利用该算法去评价其他算法。
「页面置换算法」先进先出 (FIFO)
INFO
优先淘汰最早进入内存的页面,即淘汰在内存中驻留时间最久的页面。
Belady 异常
- FIFO 算法还会产生所分配的物理块数增大而页故障数不减反增的异常现象。
- 只有 FIFO 算法可能出现 Belady 异常，LRU 和 OPT 算法永远不会出现 Belady 异常。
「页面置换算法」最近最久未使用 (LRU)
INFO
- 选择最近最长时间未访问过的页面予以淘汰。
- 该算法为每个页面设置一个访问字段，用来记录页面自上次被访问以来所经历的时间，淘汰页面时选择现有页面中值最大的予以淘汰。
- LRU 算法性能较好，但是需要寄存器和栈的硬件支持。
「页面置换算法」简单时钟置换 (CLOCK)
简单时钟算法原理
- 性能接近 OPT 算法，但实现起来的开销大。
- 为每帧设置一位访问位，当某页首次被装入或被访问时，其访问位被置为 1。
- 对于替换算法，将内存中的所有页面视为一个循环队列，并有一个替换指针与之相关联，当某一页被替换时，该指针被设置指向被替换页面的下一页。
- 在选择一页淘汰时，只需检查页的访问位。
- 若为 0，就选择该页换出。
- 若为 1，则将它置为 0，暂不换出，给予该页第二次驻留内存的机会，再依次顺序检查下一个页面。
- 当检查到队列中的最后一个页面时，若其访问位仍为1，则返回到队首去循环检查。
- 由于该算法是循环地检查各个页面的使用情况，故称 CLOCK 算法。
- 但是，因为该算法只有一位访问位，而置换时将未使用过的页面换出，故又称最近未用(NRU)算法。
算法执行步骤
「页面置换算法」改进时钟置换 (CLOCK)
改进的时钟置换算法原理
换出的选择：对于修改过的页面，替换代价大。在选择页面换出时，优先考虑既未使用过又未修改过的页面。
换出后：将一个页面换出时，若该页已被修改过，则要将该页写回磁盘，若该页未被修改过，则不必将它写回磁盘。
在改进型 CLOCK 算法中，除考虑页面使用情况外，还增加了置换代价——修改位。
由访问位 A 和修改位 M 可以组合成下面四种类型的页面：
- 1 类 A=0，M=0：最近未被访问且未被修改，是最佳淘汰页。
- 2 类 A=0，M=1：最近未被访问，但已被修改，不是很好的淘汰页。
- 3 类 A=1，M=0：最近已被问，但未被修改，可能再被访问。
- 4 类 A=1，M=1：最近已被访问且己被修改，可能再被访问。
算法执行步骤
- 从指针的当前位置开始，扫描循环队列，寻找 A=0 且 M=0 的 1 类页面，将遇到的第一个 1 类页面作为选中的淘汰页。在第一次扫描期间不改变访问位A。
- 若第 1) 步失败，则进行第二轮扫描，寻找 A=0 且 M=1 的2类页面。将遇到的第一个2类页面作为淘汰页。在第二轮扫描期间，将所有扫描过的页面的访问位都置 0。
- 若第 2) 步也失败，则将指针返回到开始的位置，并将所有帧的访问位复0。重复第 1) 步，并且若有必要，重复第 2) 步，此时一定能找到被淘汰的页。
改进型CLOCK算法和简单CLOCK的比较
- 改进型CLOCK相比于简单CLOCK，减少了磁盘的IO次数，但是为了找到可置换的页，可能需要几轮扫描，增加开销。
「抖动和工作集」抖动（颠簸）
什么是抖动或颠簸？
- 刚换出的页面马上又换入主存，刚换入的页面马上又换出主存。
- 这种频繁的页面调度行称为抖动或颠簸。
「抖动和工作集」工作集
什么是工作集？
- 工作集是指在某段时间间隔内，进程很有可能会频繁访问的页面集合。
- 基于局部性原理，可以用最近访问过的页面来确定工作集。
如何确定工作集的大小？
- 分配给进程的物理块小于工作集大小，则该进程就很有可能频繁缺页，所以为了防止这种抖动现象，一般来说分配给进程的物理块数（即驻留集大小）要大于工作集大小。
「内存映射文件」磁盘到内存的映射
什么是内存映射文件（Memory-Mapped Files)？
- 和虚拟内存类似，将磁盘区域内容映射到内存，使进程能够直接访问被映射文件。
- 所有操作均是以内存地址形式对内存中文件访问，无磁盘IO，速度很块。
- 当进程退出或解除映射后，改动页面写回磁盘。
- 多个进程可并发映射统一文件，允许数据共享。
「虚拟存储器」性能影响因素
局部性原理的影响
- 页面大，缺页率低，减少页表长度，页内碎片大。
- 页面小，缺页率高，减少内存碎片，页表过长，占内存。
- 给进程的物理块数越多，缺页率越低。
- 物理块超过阈值，缺页率改善不明显。
「地址翻译」与计组结合
待解决