内存分配

• 前提：操作系统也存放在内存中：通常存放在低内存，也可以存放在高内存
• 细节：
  • 决定操作系统存放位置的因素是 ==中断向量== 的位置
  • 操作系统可以利用 ==暂时的操作系统代码== 在进程执行过程中动态 ==改变操作系统的大小==
    • 暂时的操作系统代码：操作系统中 ==并不常用的服务== 可以暂时并不保存在内存中，空闲出来的内存用于其他目的

内存保护

• 定义：进程 禁止 访问不属于它的内存

  • 宏观：

    • 进程不可以访问其他进程的内存空间

    • 进程不可以访问操作系统的内存空间

    • 进程不可以无限制地占有一片内存空间(不可以无限制地运行下去)

      进程如果访问了其他进程的内存空间会导致 越界中断

  • 微观：

    • 进程不可以访问不属于自己逻辑空间的页面：

      解释：这种错误源于调度器分配了过多帧给进程，进程页面数少于帧数，但是页表的项数和帧数是一致的，所以可能访问到无效页，但是实际上不会发生

    • 进程不可以访问没有加载进入内存的页面：进程如果访问没有加载进入内存的页面会产生 缺页中断

• 方式：

  • 内存管理单元
  • 有效-无效位

• 方式：内存管理单元确保进程不会访问不属于它的内存

  • 处理器提供的逻辑地址处于界限地址的范围内
  • 逻辑地址和物理地址的映射关系是正确的

连续分配

固定分区方法

• 定义：系统将内存区域被分为多个 ==固定大小== 的分区 （静态）

• 过程：调度程序在某个 ==分区空闲== 时可以将 ==作业队列== 中的进程调入该分区

  注：每个分区同一时刻只能够运行一个进程

• 优点 & 缺点

  • 优点：实现简单，操作系统的开销极少

  • 缺点：(1) 进程需要的内存过大导致无法运行 (2) 进程需要的内存很少导致产生 内部碎片问题

    注：固定分区方法显然是不会产生外部碎片问题的

• 细节：

  • 确保分区能够容纳最大的进程
  • 多道程序系统的 最大度数 取决于分区的数量
  • 用于早期的 IBM OS/360 操作系统

可变分区方法

• 定义：系统根据进程 ==需要的内存== 和 ==内存的使用情况== 确定每个分区的大小 （动态）

  注：操作系统会采用表的数据结构记录当前内存的使用情况

• 空闲内存：内存中分散在不同处的多个 ==孔的== 集合

• 孔：==连续的可用的内存块称作孔==

  • 每个孔的大小可能不一样

  • 各种大小不同的孔分散在内存各处

    解释：所以并不因为是连续分配的方式，孔就只有一个，进程的结束和换出都有可能导致出现新的孔

  

• 过程：系统比较 ==孔的大小== 和进程 ==需要的内存大小==：如果能够容纳该进程就为其分配内存；如果不能容纳就让该进程继续在就绪队列中等待

  1. 每个进程获得的内存大小是和自己需要的内存大小一致

  2. 需要的内存大小是和每个孔的大小比较而不是空闲内存

  解释：多个孔大小之和（空闲内存）可能能够容纳一个进程，但是这些孔很可能并不是连续的，单个孔完全有可能无法容纳一个进程

• 选择孔的方式：

  • 引入：内存中分散着多个孔，可能存在多个孔都可以容纳当前的进程，如何比较并选择？

  • 方式：

    • 首次适配：每次选择 ==首个== 能够容纳当前进程的孔

      1. 每次查找可以从头开始，也可以从上次首次适配结束的位置开始

      2. 首次适配如果从上次结束的位置开始也被称为下次适配

    • 最优适配：每次选择能够容纳当前进程的 ==最小== 的孔

      首次适配和最优适配在执行时间和利用空间方面优于最差适配

    • 最差适配：每次选择能够容纳当前进程的 ==最大== 的孔

    • 快速适配：维护常用大小的孔链表，每次选择都从 ==孔链表== 查找能够容纳当前进程的孔

• 优点 & 缺点：

  • 优点：避免造成 ==内部碎片== 问题
  • 缺点：容易产生 ==外部碎片== 问题

碎片问题

• 定义：==无法容纳任何进程== 的孔被称作碎片

• 分类：

  • 外部碎片：空闲内存能够容纳一个进程，但是构成空闲内存的各个孔 ==并不连续== 且都不能 ==单独容纳进程==，这些孔都被称为外部碎片
  • 内存碎片：进程获取的内存超过需要的内存，多余出来的空闲内存被称为内部碎片
  

• 解决方式：

  • 外部碎片：

    • 压缩：移动所有的进程使得所有的非连续孔组成连续的空闲内存

      注：只有采用动态地址绑定才可以采用压缩的方式

      解释：压缩需要改变进程的基地址，而只有动态绑定可以改变进程的基地址

    • 分页

  • 内存碎片：

非连续分配

分页

分页概述

• 定义：将 ==物理内存==和 ==逻辑内存==（虚拟内存）分为 ==大小相等== 的块

• 概念：

  • 帧：系统将物理内存分为大小相等的块，每块称为帧

  • 帧表：记录 ==已分配帧== 和 ==空闲帧== 的数据结构

  • 页：系统将逻辑地址空间分为大小相等的块，每块称为页

    • 页码：每个页都具有的编号

    • 页偏移：页中的 每个逻辑地址 相对于 页地址 的偏移量

      (1) 页地址：每页的第一个逻辑地址就是页地址（其实之前画图已经提到了）

      (2) 偏移量最大值 = 每页的逻辑地址数量

  • 页表：记录每个页和每个帧的 ==映射关系== 的数据结构

    每个页和帧的大小都是 相等的 且由 硬件 决定的

  • 页面大小

    • 从 页表大小 考虑
    • 从 I/O负载 考虑
    • 从 碎片 考虑
    • 从 局部性 考虑

  • 有效-无效位：

    • 判断索引的页号是否存在于逻辑空间中：这种情况几乎不会出现
    • 判断当前页是否加载进入内存中(主要)：如果没有加载进入就会被标记为 无效（不可访问）；如果加载进入就会被标记为 有效（可以访问）

• 查找过程：

  1. 处理器将 逻辑地址 交付给内存管理单元

  2. 内存管理单元根据 页面大小 计算得到 页号 + 页偏移量

  3. 内存管理单元查询 页表 找到页码对应的 映射关系

  4. 内存管理单元检查 映射关系的 有效-无效位

     • 如果有效-无效位是 有效 的：跳转到第 5 步
     • 如果有效-无效位是 无效 的：处理 页错误

  5. 内存管理单元利用 帧号 和 页偏移量 计算得到 物理地址

  6. 内存管理单元将内存中的内容交付给处理器

  <a style="color:red;">公式：帧号 * 页面大小 + 页偏移量</a>
  

• 细节：

  • 分页将程序员视图的内存和物理内存完全分离

    解释：在程序员眼中所有的内存都是连续，而在实际的存储中进程的可能在内存中是分散存储的

  • 分页不会产生外部碎片问题，但是会造成内部碎片问题

    解释：页和帧的大小是固定的，但是进程需要的内存大小可能 ==无法被页大小整除== ，导致多余的内存仍然需要一页保存，造成内部碎片

    每页大小为 2^11^ B 进程需要的大小是 2^14^ + 114 B，显然剩下的内存仍然需要一页来保存

  • 处理器能够访问的逻辑地址空间可以大于实际的物理内存

    解释：64 位操作系统能够，但是物理内存小于 2^64^ B：因为并不是进程的每页都会立刻加载到内存中去，可能只有最后一页加载进入了，处理器使用的是

    ​ 逻辑地址，但是实际访问的是内存管理单元映射之后的物理地址

  • 每个进程都拥有单独的页表；并且在进程控制块保存页表指针

  • 页表通常都是存储在操作系统的 内核 中

  • 部分处理器内核支持多种页大小（Solaris）

帧分配

• 定义：为每个进程分配物理帧

• 方式：

  • 固定分配

    • 平均分配：每个进程都获取 ==相同数量== 的物理帧

    • 按进程大小分配：大进程获取的物理帧数量多，小进程获取的物理帧数量少
      $$
      s_i: \text{表示每个进程的大小};s = \sum{s_i} \text{表示所有进程的大小之和}; m: \text{表示物理帧的数量} \
      \text{公式: 分配的物理帧数量} = \frac{s_i}{s} * m
      $$

  • 优先级分配：具有 ==高优先级== 的进程可以被分配更多物理帧

• 细节：每个进程被分配的最小帧数是由计算机体系结构决定的；被分配的最大帧数是由 可用物理内存 决定的

• 策略：

  • 全局分配
  • 局部分配

• 颠簸

页表保存

• 引入：页表中每项记录了逻辑地址和物理地址的映射关系 -> 显然这些映射关系需要在实际的硬件设备上保存

• 硬件实现：

  • 寄存器：使用高速逻辑电路构造的寄存器用于保存页表

    • 优点：处理器获取页表中的映射关系的 ==速度非常快==
    • 缺点：寄存器存储的映射关系 ==数量相对较少==

    1. 修改和加载寄存器中的映射关系只能够利用特权指令完成

    2. 寄存器仍然是设计在处理器内部的

  • 内存：内存中分配相应的空间用于保存页表

    • 优点：相比于寄存器存储的映射关系数量增加很多

    • 缺点：造成 ==二次访问== 问题

      解释：处理器首先会访问存放在内存中的页表获取到映射关系，然后需要再次访问内存获取数据，相当于获取一次有效数据，两次访问内存

    处理器中设计页表基地址寄存器（PTBR）用于保存页表的在内存中的物理地址；设计页表长度寄存器（PTLR）用于保存页表长度

  • 转换表缓冲区(TLB)：使用高速缓冲硬件存放页表中部分 ==常用的映射关系==（所有的映射关系仍然是保存在内存中）

    • 优点：(1) 解决二次访问问题 (2) ==提升== 访问页表映射关系的 ==速度==

    • 缺点：(1) 访问 TLB 中不存在的映射关系时，仍然需要去内存中查询 -> 这种情况称为 ==TLB未命中== (2) 造价比较昂贵

    • 细节：

      • TLB 中重要的内核映射关系都是 ==固定== 的；其余映射关系都是可以采用 ==替换策略== 进行替换的

      • TLB 在上下文切换时也需要更新为当前进程常用的映射关系 -> TLB 中的所有映射关系都是属于同一进程的同一张页表

        注：部分 TLB 允许维护不同进程的常用映射关系

      • 现代操作系统提供多级 TLB

• 访问时间：(TLB 访问时间 + 内存访问时间) * 命中率 +  (TLB 访问时间 + 内存访问时间 * 2) * 未命中率​

  (1) 处理器首先去 TLB 中查询是否存在相应的映射关系

  ​ -> 如果存在，则称命中 TLB，然后处理器还需要从内存中去获取相应的数据（所以记得加上内存时间）

  ​ -> 如果不存在，则称未命中 TLB

  (2) 处理器再去内存中查找相应的映射关系，查找到之后再次访问内存获得相应的数据

页表结构

• 引入：

  • 现代计算机通常都是 32位 或者 64位 的操作系统，支持的最大逻辑地址为 2^32^ 或 2^64^
  • 如果每张页表大小为 2^12^ B，那么一共会有 2^20^ 或者 2^52^ 页，这些页面如果全部 连续存储 在内存中显然也不是很合理
  • 所以希望采用一定的结构将页表分散存储在内存中

• 分层分页：

  • 定义：将页表再次进行分页

    

  • 查找方式：

    1. 内存管理单元首先查找 外部页表 (高级页表)
    2. 内存管理单元再根据外部页表再索引到 内部页表 (低级页表)
    3. 内存管理单元最后根据内存页表索引到 内存中的数据

  • 细节：

    • 多级页表并不是所有级别的页表都存储在内存中：通常只有高级页表存储在内存中，利用高级页表查询到低级页表时，才会将低级页表载入内存
    • 多级页表并不适用于 64 位操纵系统：需要分的页实在太多，导致多级页表的访问效率非常低
    • 多级分页后逻辑地址也会相应地做出分化；页表中的表项不会发生变化
  

• 哈希分页：

  • 定义：设计哈希函数将虚拟页号映射到哈希表相应的位置中去

  • 核心：哈希表采用 数组链表 实现：每个哈希表中每个数组元素实际上都是一个页表

  • 查找方式：

    • 内存管理单元用虚拟页号和链表中的第一个元素进行匹配

      -> 匹配成功，则就是用这个元素的物理地址

      -> 匹配失败，则继续遍历使用接下来的元素的物理地址

  • 细节：

    • 每个表项新增一项内容：指向下一个节点的指针
    • 64 位操作系统需要使用 聚簇页表
  

• 倒置页表：

  • 定义：倒置页表仅维护 真正存在 于物理内存中的页对应的映射关系

    解释：在之后的虚拟内存中会看到，并不是所有的进程的页面都会被加载进入内存中，操作系统没有必要去维护不存在于内存中的页面的映射关系

  

  • 核心：整个操作系统仅维护 一张页表；页表的表项新增 进程标识符

  • 缺陷：

    • 需要额外维护不存在于内存中的页面的映射关系(外部页表)：

      解释：因为进程可能在运行过程中需要使用到没有加载到内存中页面，如果没有这个页表那就根本找不到在磁盘上的页面

    • 查找时间相对增多，实现共享页面较为困难

  • 细节：倒置页表是通过减少不必要的表项来降低页表大小而不是通过分散存储

  倒置页表

分段