日常学习

现代操作系统 内存篇

May 25, 2021
oslinux

内存管理

因为： 不管存储器多大，程序都可以将其填满。
所以： 分层存储器体系： 在这个体系中，存在 MB 的快速、昂贵、易失性的高速缓存，GB的速度价格适中的同样易失的内存 ，以及 TB的低速、廉价、非易失的磁盘存储。

操作系统的工作之一 就是 将层次存储系统体系 抽象成为一个 有用的模型 并管理这个抽象。

分层存储器系统称为 存储管理系统： 他的任务是 有效的管理内存，即记录哪些 内存是正在使用的，哪些 是空闲的， 在进程需要时候为其分配内存 ，不需要时释放内存。

探索 内存抽象方案：

无存储器抽象： 最简单的存储器抽象 即 没有抽象。 早期的大型机、小型计算机 都没有存储抽象。 每一个程序 都直接访问物理内存。

因此 那时候呈现给编程人员的存储器 即是： 从0到某个上限的地址集合，每个地址 对应一个 可容纳 一定数目（通常是 8位）的二进制数据。
指令 Move Register1， 100 即：将 100的物理内存的内容，复制到 register1中。

该种方案下， 系统中同时运行两个程序 是不可能的。如果进程 A在 地址 100位置写入数据，进程 2 在稍后的时间中 对地址 100进行了改写，可能导致 进程A的崩溃。

无内存抽象 模式下 内存的布局方式有以下三种：

第二种方案 经常用在 一些掌上电脑，和嵌入式系统中。
第三种方案 用于早期的个人计算机中， ROM中的系统部分 为 BIOS（basic input output system）

如何 在没有存储器抽象的情况下 同时运行多个程序？

操作系统 只需要 把当前的内存中的内容 保存到磁盘上 ，然后将下一个程序 读入到内存中 再次运行即可。 只要在同一时刻 内存中只有一个程序 即可。

历史中 IBM 360 的做法：
  1. 内存被划分为 大小2KB的块。
  2. 每个块 分配一个 4位的保护键， 保护键 存储在cpu PSW中的特殊寄存器中。
    • 所以： 一个运行中的进程如果访问保护码 与 PSW中的不同的内存，硬件将会捕获该事件。 因为只有系统可以修改保护键，这样就可以 防止 用户进程 之间、用户和操作系统之间的相互干扰。
  3. 静态重定位技术： 即便 存在保护键，依然无法解决 两个进程 使用重复的绝对地址的问题，我们希望每个进程使用一套自己私有的内存地址来进行内存访问。
    IBM 360 采用的方法 即：在第二个 程序 装载到内存 100地址时， 常数100将被 加到 程序的每一个 程序地址上。

缺少存储器抽象在嵌入式系统中 依然非常常见， 比如 洗衣机、微波炉 此类设备 都已经完全被ROM形式的软件控制。 这种情况下，软件都采用 绝对地址寻址的方式，因为 所有运行的程序 都可以被事先确定， 用户不需要运行自己的软件。

存储器抽象： 地址空间

直接暴露物理地址的问题： 1） 用户程序可以简单的寻址内存地址，很容易地破坏 操作系统。 2） 同时运行多个程序将非常困难。

地址空间的概念：

要多个应用程序 同时处于内存 而不互相影响 需要解决两个问题： 1）保护 2）重定位 。
IBM 360的办法 实际效果并不好，因为 其 静态重定位 技术，不仅缓慢，还需要 额外的标记 来确定 哪些地址 需要被加。（比如 相对地址指令并不需要 + 程序的起始位置

就像 进程的概念 创造了 cpu的抽象 为 进程使用 一样。
地址空间: 为程序 创造了一种抽象 的内存，地址空间 是一个进程可以用于寻址内存的地址集合。每个进程都有自己的地址空间，独立于 其他的进程地址空间。

地址空间的概念非常常见： 比如 电话号码、url等。

动态重定位： (简单实现) 给cpu配置两个寄存器： 基址寄存器 、界限寄存器。 使程序装载期间无需重定位。 此方法可以简单实现存储器抽象。

具体做法：

  1. 当一个进程运行时 程序的起始地址装载到基址寄存器中，程序的长度 装载到 界限寄存器中。
  2. 每次 进程访问内存，取一条指令、读写一个内存地址时: 读写地址 —> 地址 + 基址寄存器 —> 检查 是否在 界限寄存器范围内 —> 发送到 内存总线 (cpu硬件会将 地址发送到内存总线 之前， 自动把基址寄存器的数值 + 进程发出的地址上。 同时检查结果是否在界限寄存器范围内。 超过了界限则捕获错误。

基址寄存器 16384， 界限寄存器： 17000 指令 jmp 28 被翻译成 jmp 16412(16384 + 28)

如何解决 程序需要的内存 > 实际物理内存 ？ (两种处理内存超载的方法)
  1. 交换技术：(最简单的策略)
    • 将进程完整的调入内存中，多个进程同时运行，
    • 当前内存不能满足新进程的内存需要时候，将空闲进程 换出到磁盘中， 通过对进程 内存到磁盘 的换入换出 操作，来实现 同时运行多个进程。
  2. 虚拟内存： 使程序只有一部分被调入内存的情况下运行。

空闲内存管理 （不同于 交换技术 预留分配空间， 因为 物理内存是有限的，系统 在有限的物理内存 上构建无限的虚拟内存， 系统或程序 都需要动态分配内存，所以需要对 动态区域进行管理）

动态分配内存时， 操作系统 必须 对其进行管理 ，一般有两种办法： 1） 位图 2） 空闲区链表

  1. 使用位图的存储管理：
    • 内存可能被划分为 几个字 或 几千字的分配单位，每个分配单位 对应于图中的一位。0表示空闲，1表示占用。
    • 分配单元的大小是一个重要的设计元素， 分配单元小 则位图大，位图占用的内存空间的比例就会提升。分配单元大 ，则位图小。但进程分配的存在更多的浪费。

    位图： 可以使用一块固定大小的内存空间，来管理无限大小的内存。（只是分配单位或大或小）
    位图主要的问题是： 在决定分配一个 大小 为k个分配单元的进程调入内存时，存储管理器 必须搜索位图 已找到 k个连续的0串，因为 位图中该串可能跨越字的边界。 查找位图中 特定长度的连续0串是一个耗时操作。

  2. 使用链表的存储管理： 维护一个记录已分配内存段和空闲内存段的链表。 有几种方法 为 新创建的进程 分配内存：
    • 首次匹配算法： 沿着链表进行搜索， 直到找到一个足够大的空闲区间。 除非空闲空间与需要分配的空间大小一样，否则将该空闲区分为两部分，一部分供进程使用，一部分成为新的空闲区。 速度非常快的算法，因为它可以尽可能少的搜索节点。
    • 最佳适配算法：搜索整个链表， 找到能够容纳新进程的最小空闲区间。该算法试图找到最接近实际需要的空闲区。
    • 其他算法： 快速适配法

虚拟内存： 虽然 基址寄存器 + 界限寄存器 能够很好的应对内存抽象管理要求，但是 随着软件的膨胀 需要运行的程序往往大到内存 无法容纳， 而系统必须能够支撑起多个程序的同时运行， 即使内存仅仅 可以满足其中一个的程序需要。

总体来看 程序对内存的需求超过了实际内存大小。交换技术并不是一个很好的方案，因为一个典型的SATA磁盘的峰值传输效率 只有几百兆每秒，这意味着需要好几秒 才能换入 一个1GB的程序。

因为： 交换技术太过缓慢。所以： 虚拟内存技术

即便是在计算机发展早期该类问题就已经出现了，初始的简单解决办法为：覆盖 （overlay）

  1. 把程序分割成为许多片段
  2. 程序开始，将覆盖管理模块转入内存，该管理模块立即 装并运行程序的片段0，在系统需要时 将由 管理模块 程序片段1装载到内存中，
  3. 覆盖管理模块允许多个 片段 同时在内存中，部分在磁盘上，在需要时候动态的换入换出。

覆盖 （overlay） 存在的缺点： 虽然有管理模块来负责 换入换出操作，但是依然需要程序员将程序 分割成多个片段，最后人们将这种费事重复性的操作 交给了计算机去做。
采用的这个方法 称为:

虚拟内存

基本思想为：

非常适合， 在多道程序系统中使用（多个程序片段能够共同存在内存中（可能是部分），并运行）

分页（Paging 技术）： 大部分 虚拟内存使用的技术

Move reg, 1000
将内存地址 1000 的内存复制到 reg中，其中的1000地址 可以由 索引、基址寄存器、段寄存器 或其他方式产生。

由程序产生的地址称为虚拟地址（virtual address） 它们构成了一个虚拟地址空间。 没有虚拟内存的计算机上，虚拟地址 就是 内存物理地址， 使用虚拟内存的情况下， 虚拟地址 并不直接传送到内存总线上，而是 先传到 内存管理单元（memory management unit MMU） mmu将虚拟地址映射称为 物理内存地址 ，在传送到物理内存地址总线上。

地址转换过程： 指令地址(virtual address) —-> mmu —–> 总线

页面的定义 + 相关概念

虚拟地址 被划分为 固定大小划 称为 页面 （page）的单元， 物理内存中对应的为 页框（page frame） RAM与磁盘之间的交换总是以整个页面为单元进行的。

页面（Page）：虚拟地址，固定大小 连续地址 的空间， page 通常等于 page frame
页框（Page frame）： 物理内存， 对应的page 单元
Ram 与 disk 之间的交换大小单位 为 page

x86: page大小 可选为 4kb 2mb 1Gb （page 的可选大小 需要硬件支持）
混合使用： 用户程序 page 为4kb ， 内核程序 page 为1gb

分页中 虚拟地址到物理地址的转换过程:

程序执行 指令 MOV REG，0
虚拟地址 --> MMU ( MMU 根据地址 找到 页面 --> 找到对应的 物理地址 页框 ) --> 转换为 物理地址
详细的转换论述过程: 将虚拟地址 0 送到MMU， MMU 看到虚拟地址落在页面0，根据映射结果 该页面对应得是页框是2（8192-12287） 因此 MMU把地址变换为8192 并将地址 8192发送到总线上，内存对MMU一无所知，他知道看到一个读写地址 8192 的请求并执行它，MMU从而有效的将 程序虚拟地址空间0-4095 映射到 8192-12287。

如何解决： 虚拟地址空间 >> 物理内存空间的问题（Virtual address > Ram address

将无限的虚拟页面 映射到 有限的物理页框中(缺页中断)

MMU内部结构如下：

可以将16位的虚拟地址，划分为 4位的 页号 + 12 位的便宜里那个。 4位的页号 可以表达16个 页面 ， 12位的偏移地址 可以为一页内部的全部4096个字节编码。
使用页号作为页表的索引。以找出对于该虚拟页面的页框号， 如果 不在 则 引发一个缺页中断， 如果在 ，则 将在页表中查找到的 页框号 + 虚拟地址的偏移量 构成一个 物理地址。 输出到物理内存地址总线上。

如何将 page 映射到 page frame ？ 页表 （Page table）

最简单的实现（也是 最普遍的实现）： 虚拟地址 被划分为 虚拟页号（高地址位） + 偏移量（低地址位）
16位地址 和 4KB的页面大小： 高4位 是 虚拟页号（指定page 通过 page table 找到 page frame）， 低12位 位偏移量。

虚拟页号 作为 页表(page table)索引，找到 虚拟页 对应 的 页表(page)项目， 页表项目 找到页框号(page frame)， 然后 将页框号 于 低位的偏移地址 拼接 作为 物理内存的物理地址

页表项目的结构：

|(高速缓存禁止位)|访问位| 修改位\｜保护位\｜在/不在 位\｜ 页框号 \｜

重要的： 如页面不在 页表中，page在disk中的位置，并不是 页表的 组成部分（页表只保存 将虚拟地址转换为物理地址所必需的信息）。所以 需要 os来进行保存。
虚拟内存本质： 通过 将 地址空间划分为 页（page） 来 在 物理内存空间上 建立一个 抽象 虚拟地址空间

加速分页过程： 分页系统中都需要解决两个问题： 1） 虚拟地址 到 物理地址 的转换速度需要 非常快 2） 页表大小，如果虚拟地址空间非常大，则 页表项目 也非常大 。

第一点： 很多指令都会访问内存 ，如果指令的执行时间 为1ns，则 页表查询 必须在0.2ns内完成，否则 地址转换 将成为瓶颈。
第二点： 假设页面大小 为4KB， 则32位的机器 的页表项数目位 100w， 64位机器的页表项将多到无法想象。另外每个进程都存在自己的页表。

所以 构建大而快的页表 成为了分页式虚拟内存的重要约束

可能的设计方法：

  1. 使用特殊硬件（快速寄存器阵列） 组成页表， 每次进程切换 os将 进程页表加载到寄存器中， 每次指令访问内存 进行地址转换 都不需要再次访问内存。简单、快速，缺点 是代价高。
  2. 将整个页表存在内存中 + 一个指向页表内存起始位置的寄存器。 这样在进程切换时，只需要将 表内存地址装载到寄存器即可。简单，但是 每次访问内存，都需要多访问一次 页表项（内存）。
TLB:

实际中的加速方法： 转换检测缓冲区： 基于(2/8原则或局部性)大多数程序总是对少量的页面进行多次的访问，而不是相反。 因此只有少量的页表项 会反复的访问。

所以： 设立一个小的硬件设备，将 虚拟地址 直接映射到物理地址，而不必再访问内存中的页表 即: 转换检测缓冲区（translation lookaside buffer TLB） 又称为 快表。
该设备 存在 MMU中，包含少量的页表项 ，实践中 一般不会超过 256个， 每个表项 记录着 简单的数据信息 以减少存储 。

TLC 的MMU 地址转换方式：

？ 问题: 首次 程序装载时候，TLB 中是否存在数据？ 主动装载 还是 被动装载。

TLB 缺失 处理：
  1. TLB 缺失 错误:
    • 之前 ，TLB的管理、TLB未命中 都是由 MMU硬件实现的。
    • 现在， TLB 一般是由 os（在软件中）实现的。TLB 被操作系统 显式的 装载。 当发生 TLB （TLB未命中）生成一个TLB 失效 中断 交给os处理，os必须找到该页面，然后从TLB 中删除一个项目，装载该项目，然后重新执行指令。 该操作需要在几个指令间完成，因为 TLB失效中断 比 缺页中断 更加频繁。

？ 这里面的TLB失效，具体含义是什么？ 是TLB中不存在， page table中存在吗？，还是两个都不存在， 1 种情况 将简单的将页表项 装载到TLB中， 第二种情况则 可能发生 page fault。 这其中的 硬件 系统之间的交互 将比较复杂。

  1. 在TLB失效 中断的处理程序中，需要遍历页表 以找到 缺失的页表项，但是 页表可能也不再TLB中，造成 额外的TLB失效。一般需要 在TLB表项中固定 页表的内存地址 ，以减少 TLB失效。
    ？ 这里面的意思是， TLB 失效 完全由 os托管，而非 部分的硬件的来寻找 页表项，然后在交由 os处理。

  2. TLB失效的两种类型： 1） 软失效（soft miss） 即：页面在内存中而不在 TLB中，只需要 进行 页表项的查找，并更新TLB即可， 消耗在10-20个机器指令范围。2）硬失效（hard miss） 即页面不在内存中，需要一次磁盘读取来换取该页面， 处理时间 总是 软失效的 百万倍， 几毫秒内。

段错误： 程序访问了一个非法地址，根本不需要更新TLB， 属于程序错误。

构建更大的页表： TLB 可以加快虚拟地址到 物理地址的转换，解决的是第一个问题 ，第二个问题的解决方案为：

  1. 多级页表： 引入多级页表的原因： 避免将全部页表一直保存在内存中， 所以可以扩大页表项的数目， 比如 32位的虚拟地址 被划为 10位的PT1 10的PT2， 以及 12 的 偏移量 offset， 页面大小位 4KB，共 2 ** 20 个页面。
  2. 倒排页表： 该设计中 实际内存中的每个页框对应一个页表项，而不是每个虚拟页对应一个页表项。 虽然减少了 页表的大小（在 虚拟地址空间 比 物理内存 空间大得多的时候） 但是 将导致 虚拟地址 到物理地址 的转换变的困难，因为不能简单的 通过 地址作为索引来寻找页表项， 而是变量 页表 来找到表项。 使用TLB能够有效的 减缓这种情况的发生。
    ？ 这里没有明白， 倒排页表 实际的存储结构，以及内容。页表 的功能 依然是 从 虚拟地址 转换到 物理地址吧，为什么 他存储的 是每个页框对应的页表项呢？ 前面存储的也是这样的啊，因为页表的大小存储是有限的，所以才会发生 页表项的 淘汰与替换呢啊。

页面置换算法： 缺页中断时候， 操作系统 如何选择 高效 的 置换页面 能够显著的提高系统性能

页面置换问题 在计算机的其他领域 依然存在， 比如web 服务器 将经常访问的 页面 放到 内存中，但是内存存储是有限的，当新的页面需要缓存时， 就会遇到同样的问题

  1. 最优页面置换算法： 很容易描述，但是无法实现。
    • 描述如下：在缺页中断发生时， 我们知晓 存在内存中的页面 在未来 多少个指令后 将要被访问，则最优置换算法为： 选取 最大的指令 过后 才会访问的 页面进行替换。 即： 选择替换 未来 最近不需要访问的页面， 将 因为访问而再次发生页面中断 推迟，越久越好。
    • 该算法无法实现， 因为os并不知道将来 页面在下一次访问的时间。但是可以作为 衡量其他算法的标准。
  2. 最近未使用页面置换算法：（ Not Recently Used 最近未使用） 页表项设定有 读写位 + 修改位， M 位有硬件进行设定， R 位 被os周期性的进行重置。 所以最终的页表项的状态集为：
       0： 没有访问，没有修改
       1： 没有访问，已被修改
       2:  已被访问，没有修改
       3: 已被访问， 已被修改

 * 该算法将 按照 编号 从小到大的 页面集合中 随机选取 淘汰页面。 
 * 该算法 认为 类目从小到大 在将来访问的可能性依次增大
 * 实现简单 易于理解。虽然性能不是最好的。
  1. 先进先出页面置换算法：
    • 该算法采用先进先出（FIFO first in first out） 思想， os维护一个 当前内存中的页面链表， 最新进入的放在表尾，最早进入的在表头， 发生缺页中断时候， 淘汰 表头的页面，并将新加入的页面放到表尾
  2. 第二次机会页面置换算法： 对FIFO算法的改进， FIFO算法可能回把经常使用的页面置换出去。该算法对FIFO算法进行一个简单的改进。 即： 淘汰表头的页面时 检查其 读写位， 如果是 0 则 该页面 最近没有被读取过，既老又没用，简单的淘汰掉。 如果是1 则 将 读写位 重置， 当作 新页面一样 放入到链表 末尾， 然后继续搜索。（即第二次机会）
  3. 时钟页面置换算法： FIFO算法 + 第二次机会算法 都需要经常在链表中移动，并移动页面。 一个更好的算法是 将所有的页面 保存为 环形链表中， 使用一个指针 指向 最老的页面。（淘汰页面）
    • 缺页中断时， 首先检查 指针指向的页面， 读写位 为 0 则淘汰页面，替换为新页面， 并将指针位置 + 1， 如果读写位 为1， 则 重置 读写位，指针 + 1，继续寻找 淘汰页面。
  4. 最近最少使用页面置换算法： 对最有算法的一个很好的近似： 是 前面频繁使用的页面 在后面也经常被使用，该思想 描述了 一个可以实现的算法。 即： 缺页中断时， 置换未使用时间最长的页面。 该算法成为 LRU least recently used
    • 该算法 理论上可实现，但是代价很高， 完全的实现 需要维护 一个 所有页的 以及对应的 访问次数。
    • 硬件实现： 在页表项中添加访问次数，每次 页面被访问，访问次数+ 1，以上由硬件实现，缺页中断时 os检查所有页面中的访问次数数值最小的一个。即 最近最少使用的页面。
      硬件费用较高。
  5. NFU 因为 LRU 在软件实现中无法跟硬件一样 实现对页面访问的精确统计， 所以 采用 NFU not frequently Used 算法
    • 将每个页面与一个软件计数器相关联，初始值为0， 每次时钟中断时，os扫描所有页面，如果页面 别读过 则将 计数器+1， 这个计数器大概能够反映 每个页面 被访问的频繁程度。缺页中断时， 置换计数器 最小的页面。
    • NFU 的问题 在于 总不会忘记过去，可以加入老化算法来优化 该算法。
    • 优化的点在于： 在扫描页面累加计数器时，首先 先将计数器右移一位， 然后将R 位加入到计数器最左端的位。
    • 缺页中断时： 选择计数器数值最小的页面。
    • 与LRU的区别在于： NFU的老化算法 的计数器只有有限的位置。即 发生的时间过长 将不会被记忆。
  6. 工作集 页面置换算法：

    单纯的分页系统中，启动进程时候， 在内存中并没有页面， cpu取第一条指令 即会发生缺页中断，其他的全局变量 和堆栈 引起的缺页中断 会紧接着发生。进程 运行一段时间后， 其需要的大部分页面就都已经存在内存中了。

根据程序的局部性访问行为， 进程运行的任何阶段，只需要访问一小部分页面。
为此我们设定了 工作集的概念：进程正在使用的页面集合称为 工作集。

如果整个工作集 都在内存中，那么我们可以预期 在进程运行的下一个阶段之前， 不会产生很多的缺页中断
如果内存太小无法容纳下整个工作集，那么在进程运行的下一个阶段之前， 进程可能会产生大量的缺页中断， 导致运行速度变慢， 可能会每执行几条指令 就发生一次缺页中断， 我们称这种现象为 颠簸。

多道程序系统中，在有限的内存空间中，会将进程的页面转移到磁盘中，以让其他的进程拥有cpu， 当该进程重新调入内存时，该如何处理？ 可以什么都不做，只需要处理缺页中断 ，即可，一直到 进程的工作集全部 调入内存。 然而 缺页中断的处理 太过耗时。
进程在缺少页面时运行，这个策略被称为 请求调页（demand paging） 即: 页面在需要时被调入，区分于 预先装入。

工作集模型： 不少分页系统中跟踪 进程的工作集。 以确保进程在运行前， 他的工作集就已经在内存中了，目的在于大大减少缺页中断率。

在进程运行前预先装入其工作集 页面 成为预先调页(pre paging)
注意 进程的 工作集 是随时间变化的

工作集 定义： w（k， t） 任意时刻 t，存在一个集合，包含所有最近k次内存访问的页面 的集合。
该集合 单调递增，但是不会无限的变大。 其图形如下。
[image]
？ 并没有绘制出 w（k， t） 随时间变化的曲线， 程序随时间变化是 没有规律的吗？

所以图片的 x 轴 是 时间or k？ 应该是k， 而 直接论断 工作集 随时间变化缓慢的结论，
因为工作集随时间变化很慢， 那么当程序重新开始执行时，可以根据 程序上次结束的工作集 对本次的工作集 做一个合理的推测， 预先调入 工作集中的页面，以减少缺页中断。
？ 即便是 预先调入进程的页面 vs 缺页中断调入， 不一样的浪费 cpu时间吗？ 如果想让 预先调入变得有用的话，则需要 cpu 在空闲时间 调入 或者 用DMA 进行（不占用cpu时间） 调入。

然而很难精确的计算工作集。存在几种近似方案：

将最近k次，转化为时间，即 求最近 x ms内，访问的内存页面集合。 具体如下：

  1. 维护一个 记录 页面最近访问时间 以及 硬件的R位。
  2. 定期清理R位
  3. 发生缺页中断时，遍历页面，寻找 R位 为 0 以及 最近访问时间不在 xms 内的 页面（因为该页面 在 xms内 没有被访问过，所以不在工作集内） 进行淘汰。

该算法的一个改进，即 不采用链表的方法来 维护 页面信息，而是采用 clock，工作集时钟方式 ，称为工作集时钟（WSClock） 因为 其实现简单、性能好，而在实践中得到广泛应用。 （因为时钟区分于 链表 不需要 对链表进行移动 以保持顺序，只需要简单的移动指针即可）

  1. 工作集时钟页面置换算法
    页面置换中的问题： 应尽量的避免 将脏页面 换出，因为 同样会存在 IO操作，所以？ 何时对 脏页面进行换出？以及 如何控制 换出可能导致的磁盘 阻塞？ 是否应将此类问题 提高一层面，交给 os处理？

页面置换算法小结：
[image]

分页系统中的实际问题：

  1. 置换算法的 局部分配与全局分配：
    • 局部即为进程内部分配内存， 全局则为在竞争的进程间分配内存。
    • 全局性的页面置换算法能够 在进程之间动态的分配页框（page frame） 因此 各个进程的页框数 是随时间变化的，而 局部性的 置换算法则是固定不变的。
      全局性算法通常 优于局部性算法， 尤其是在进程的工作集大小 随时间变化时，此种算法 需要监控进程工作集大小
  2. 可以采用单独的算法来为进程分配页框：
    • 公平分配，为所有 进程 分配相同等额大小的 内存空间。
    • PFF（Page Fault Frequently） 缺页中断率算法
  3. 缺页中断率：
    • 缺页中断率会随着 分配页框的增加而降低， 缺页中断率指出了何时增加或降低进程的分配页框。 但是不能当作 缺页中断时的页面置换算法。因为不能用该算法用来确定应该被淘汰的页面。
    • 缺页中断率： 可以采用 连续平均法： 当前数值 + 之前连续平均数值 / 2 来老化之前的影响

分页系统中的设计问题：

  1. 置换算法的 局部分配 与 全局分配： 局部即为 进程内部分配内存， 全局则为 在竞争的进程间分配内存。 全局性的页面置换算法 能够 在 进程之间动态的分配页框（page frame） 因此 各个进程的页框数 是随时间变化的，而 局部性的 置换算法 则 是固定不变的。

全局性算法 通常 优于 局部性算法， 尤其是在 进程的工作集大小 随时间变化时，此种算法 需要监控进程工作集大小。

可以采用单独的算法 来 为 进程分配页框：

  1. 公平分配，为所有 进程 分配相同等额大小的 内存空间。
  2. PFF（Page Fault Frequently） 缺页中断率算法：

缺页中断率会随着 分配页框的增加而降低， 缺页中断率指出了何时增加或降低 进程 的分配页框。 但是 不能当作 缺页中断时的页面置换算法。因为 不能用该算法用来确定应该被淘汰的页面。

缺页中断率： 可以采用 连续平均法： 当前数值 + 之前连续平均数值 / 2

工作集算法 于 工作集时钟算法 只适用于 局部算法， 即进程内部的内存置换。

负载控制： 即便是采用了最优页面置换算法， 并对进程采用理想的全局页框分配， 系统依然可能发生颠簸， 事实上 一旦所有进程 的组合工作集 超出了内存的容量限制，就可能发生颠簸。 PFF 算法的假设 指出 进程需要更多的内存， 但是没有进程需要更少的内存。 没有任何办法 能够在 不影响 其他进程的情况下，满足进程更多对内存的需要。 唯一的解决办法 即是： 将部分进程从内存交换出去。

具体方法为： 将部分进程交换到磁盘中，并释放其占用的内存，这样其页框就可以被颠簸的进程使用，如果颠簸结束则停止操作，否则继续此操作 直到颠簸停止。

页面大小： 需要权衡的因素：

因素有： 1. 页框的内存碎片，即 分配一个页框， 而无法完全占满 页框的情况。2. 页表大小

页面小： 有利于减少 页框的内存碎片，提高内存的利用率， 但 需要更大的页表。 占用的TLB 更大。
页面大： 增大 内存碎片，减少页表大小。

总结： 实践情况为： 内核使用大页面，而 用户进程 使用小页面。 普遍的页面大小 为 4KB， 8KB

工作集算法与工作集时钟算法 只适用于局部算法， 即进程内部的内存置换

页面大小： 需要权衡的因素： 1) 页框的内存碎片，即 分配一个页框， 而无法完全占满 页框的情况。2) 页表大小

共享页面：

多个进程AB 共享相同的页框 可能存在问题， 如果 进程A 因为调度决策 或者 进程结束 导致 进程 A 的内存被释放， 则会引起与 A共享内存的B 发生大量的缺页中断，把共享页框重新调入 才能继续运行。

考察一个页面 是否存在共享， 便利 page table 代价较大， 需要单独的 为 共享页面 保存数据结构。

linux 中的 写时复制 能够 共享 代码 与 数据。fork系统调用后， 进程 分配 自己的页表，但是指向 同一个页面集合，页表项目 都是只读，当发生 数据修改时，就会触发只读保护， 引发 系统陷阱， 然后生成 页面的副本，实现各自的修改。

共享库： DLL（Dynamic Link Library） 链接 命令中指定多个 目标文件， 会将 目标文件中 使用、调用 但是未定义的外部函数 在 目标文件中 进行寻找， 并在输出的目标文件中 记录 函数调用的存根。 在操作系统 加载该目标文件时， 会根据 存根 找到 需要加载的目标文件 并加载之，如果该文件 已经被 其他的程序 使用并加载了 则 不需要重新加载， 创建新的页表 映射到 对应的内存地址。

因为共享库 可能被不同程序 加载到不同的 内存位置， 则 在共享库代码中 不能够使用绝对地理位置， 需要使用 地址无关代码 编写 才能在各个 内存位置正确运行。

共享库 是 更为 通用的 内存映射文件 memory-mapped file 技术的一个特例。 进程发起系统调用，将 文件映射称为 虚拟地址空间的一部分 。访问内存时 内存页面会 一页一页的加载。 磁盘文件作为 后备存储。 进程退出 或 显式的解除映射 关系时候， 内存的改动会 被写会到磁盘。

提供了一种IO 模型， 可以将文件 映射称为 一个大的内存字符数组 进行访问。

多个进程 映射同一文件， 他们就可以使用 共享内存进行通讯，一个进程的修改在其他的进程能立即生效， 该机制提供了一个 进程之间的高速带宽。

分页守护进程（paging daemon）： 为保证系统中存在 足够的空闲页框（一定数目的 页框供给比）， 以使 分页系统保持最佳状态。 该进程 多数时间在休眠，周期性唤醒 以检查内存状态， 空闲页框过少，则 使用 预定的 页面置换算法 将页面换出内存。

实现的实际问题：

os 需要与分页有关的工作时间点： 进程创建、进程 执行， 缺页中断、进程终止。
缺页中断的 细节：
  1. 硬件陷入内核， 在堆栈 中 保存pc， cpu的各种状态 保存在寄存器 中。
  2. 执行汇编代码，保存 通用寄存器 等信息，以避免被 os 破坏，该 程序 将 os作为 函数调用
  3. os 发现 一个缺页中断 发生时， 尝试发现需要哪个页面 ， 通常一个硬件寄存器 包含了 该信息， 如果没有的话，os必须 检索 pc， 软件分析 该指令， 已获得 发生缺页中断的 虚拟地址。
  4. os检查该地址是否有效（包括 范围 以及 保护位），如果 出现错误（地址越界 等） 则 os向 进程发送信号 杀死进程。否则， os 检查是否 有空闲页框， 如果没有空闲页框， 执行页面置换算法 淘汰一个页面。
  5. 如果 选择的页框 被修改过，则 安排该页面写回磁盘， 并发生一次 上下文切换，挂起产生缺页中断的 进程， 让其他进程运行直到 磁盘传输结束，无论如何，该页框被标记为 忙， 以免 因为其他原因 被其他进程占用。
  6. 一旦 页框 干净 后 ， os查找所需页面在磁盘上的位置， 通过磁盘操作将其装入， 该页面被装入时， 产生缺页中断的 进程 被挂起。
  7. 磁盘中断发生时，表明该页 已经被装入， 页表被更新， 页框 也标记为正常状态。
  8. 恢复发生缺页中断 指令以前的状态， 重新执行该指令
  9. 调度引发 缺页中断的 进程，os返回调用它 的汇编程序例程
  10. 该例程 恢复 寄存器 和其他的 状态信息， 返回到用户空间继续执行，就好像 缺页中断 未曾发生 一样。

？ 这里面发生了几次的调用切换， 程序 指令 导致 硬件陷入 内核 ，执行 一段汇编代码 （汇编代码 执行低级指令， 保存pc 状态信息等） 该汇编代码 call os函数， os代码只存在一份， 需要在 该代码中 确定 发生什么， 在这里 需要确定 缺页中断， 然后执行 缺页中断 的处理程序， 缺页中断程序 需要确定 引起发生 缺页中断的 虚拟地址， 并 将需要的页面 调入内存中（其中 可能发生 页面置换，即 页面别换入或换出）， 页面调入内存中， 需要 os 通过进程表中记录的 磁盘地址，将 磁盘内容读到 内存中 已实现 页面的调入，
磁盘的读取 会浪费cpu时间， cpu可以切换到 其他进程的执行，以有效利用cpu。 磁盘读取完毕 发生 中断调用， 中断调用程序 需要确定发生的情况， 已重新执行 os函数代码，并返回到 汇编代码， 重新执行 引发 缺页中断 的中断。

问题：

执行备份： 引起缺页中断的指令 会中途停止 引发 os的陷阱， 等待 os 调入 页面的内容后， 并重新执行 指令。然而 实现该结果 并不简单。

例如 move A1, A0 该指令， 引起引起 缺页中断， 但是在该指令 中， 访问了内存3次： 一次指令本身地址 + 2个内存操作数， 如果是操作数内存访问引起的 缺页中断，os 是无法弄清楚 完整的指令的， 因为 os 无法判断 引起缺页中断的内存地址 的具体含义（即 是 参数 还是 指令）

为此 cpu的 设计者 提供了一种简单的 处理方法： 提供 一个隐藏的内容寄存器， 在每条指令执行之前， 把程序计数器的内容 复制到 该寄存器。 通过此信息， os可以消除 引起缺页中断指令 造成的影响。

锁定内存中的页面：

进程 A: 通过系统调用 从文件或其他设备 读取到其 内存空间中的缓冲区， 在等待IO过程中，被挂起。进程B执行
进程 B： 产生一个缺页中断

如果分页算法 是全局算法， 则 IO 缓冲区的 内存 则有可能 被 选中换出内存，IO 设备正在对该页面进行DMA 传输过程中， 页面 被换出，将导致 部分数据写入 IO映射的内存， 部分写入到新的页面中。？ 因为 cpu 无法考量 内存是否 正在DMA吗？

两种方法： 1） 将正在进行IO的内存 钉住（Pinning） 以保证其不会被 换出， 移出内存。2） 在内核缓冲区中 完成所有IO操作，然后 再将 数据复制到 用户页面。
？ 两种操作 本质应该是一样的吧， 所以内核缓冲区不会被 置换算法 选中？ 现在 linux 应该采用的 是 第二种方法。

后备存储： 我们已经知道了 如何选择 换出内存的页面，但是 没有讨论 被换出的页面 如何存储在 磁盘上。

交换分区： 在磁盘上分配 页面空间的最简单的方法， 从文件系统划分一块独立的 磁盘 ， 大多数的Unix 是如此处理的（swap分区） 该分区 不是普通的文件系统，而是 使用 直接的相应的分区块号， 取消了文件偏移量 到 块地址的映射 步骤。

进程表中记录着每个进程对应交换区的 磁盘地址。

两种 进程交换区初始化方式： 1） 初始化什么也不做，在页面被换出时候，为其分配磁盘空间， 换入时候 回首磁盘空间。 缺点为： 进程表 需要记录每个页面对应的磁盘地址。
2） 初始化 创建出 与进程空间同样大的 交换区， 每个页面都存在对应的磁盘空间， 映射也非常简单， 进程的交换区 起始块地址 + 页面偏移量。缺点是：磁盘空间占用大。

虚拟内存的分段实现：

分段： 在编译器 编译程序的过程中， 会划分出 许多的段， 符号表段，源程序正文段， 变量表段 etc。 而对应的计算机 虚拟内存实现中，除了 分页的实现方式之外，还存在另类的 分段 实现设计。

段 segment 每个段 范围是 0 到 最大的地址空间， 每个段 是独立的 地址空间， 其增长或者减小，对其他的段不会造成影响。
其 与 分页 存在本质的不同， 分页是定长的，而 段 不是。

MULTICS系统采用了分段 + 分页 的虚拟内存实现方式。 将每个段视为虚拟内存 并对其进行分页。 以结合两者的优点。 在使用段的一部分时， 并不需要把整个段 加载进来。

每个 程序 都存在一个段表， 段表 存在 25W 个表项， 所以段表本身 也会被分页。 每个表项 对应一个描述符，其 包含的标记有： 该段是否在内存中（ 该段的 任何一个 页面 存在内存中 即被认为 该段在内存中） 一个指向 对应页表的指针， 段大小， 保护位 以及其他的一些条目。
、
multics中的 地址 由两部分构成： 段 + 段内地址。 段内地址 分为 页号 + 页内地址。 执行内存访问时 执行如下算法（理想状况下，不考虑 段表的缺页中断）

  1. 根据段号 找到 段表项（段描述符）
  2. 检查页表是否在内存中， 不在 则产生一个段错误， 在 则找到对应的位置。
  3. 检查 地址对应的页表项， 检查该页面是否在内存中，不在 则产生 一个缺页中断， 在 则 取出对应的页框地址
  4. 将偏移量 + 页框地址， 既是内存地址

TLB 缓存 映射结果。

Intel x86: 硬件的实现细节：

虚拟内存的核心两张表： LDT local descriptor table 局部描述符表， GDT global descriptor table 全局描述符表， 每个进程 都存在自己的 LDT， 存储 自己的代码、数据、堆栈等。 GDT 则 在所有进程间共享，存储包括 操作系统 在内 的信息。

x86 cs ds 寄存器 为 段选择子。包含 段表项 地址 + gdt/ldt + 特权级。 下面是 将 描述地址： 选择子 + 偏移量 转化为 物理地址的过程：

  1. 根据 对应的 段选择子 将 从LDT 或 GDT 中 段表项（段描述符） 取出 转入到 微程序寄存器中， 以便快速访问
  2. 将段描述的 基址 添加到 偏移量

  3. 如何解释 相加之后得到的 地址： 存在 两种情况： 是否允许分页。

  4. 禁止分页： 线性地址 被解释为物理地址 ，直接被送往 存储器
  5. 允许分页： 线性地址 被解释为 虚拟地址， 通过页表映射到 物理地址 。

这里采用了 二级映射， 因为 32为虚拟地址 页面大小为 4kb 的情况下， 需要的页表项 太多。

线性的虚拟地址 被解释为 ： 10 位的 页目录 + 10位的 页表项 + 12位 偏移量。

通过 页目录 找到 对应的页表的指针，再通过 页表项 找到 页表项 对应的 物理页框 地址 + 偏移量 = 物理地址

为了避免 重复的内存访问， intel使用 TLB 将 （页目录，页表项） 直接 映射到页框地址。

这里面依然 可以使用 不分段的 纯粹分页的 虚拟内存实现。 即 将所有的段寄存器 使用一个 数值 进行设置。 即： 程序 只是用 一个 段，段 被设定为最大，加上 指令偏移 即是 虚拟地址， 使用分页 进行 到 物理地址的转换。 既是 纯粹的 分页。

因为 Unix + Windows 都未曾 使用其 分段 设计（ 为 x86 单独使用存储模型，回破坏系统 的可移植性）， 导致 intel 最后 剔除了 对 分段的支持。

总结： 本章 主要讲解了 虚拟内存的实现 的一些技术

交换技术： 通过交换技术， 可以使 系统同时运行 超过物理内存大小的 多个进程，如果 一个进程没有空间可用，则可以将它 周期性的交换到磁盘上 来运行。
内存和磁盘的空闲空间: 可以使用 位图 或 空闲区链表 来记录。

为了减少程序对于物理内存的需求，并提供一个 无限制大小的 内存抽象。 技术有：

将进程的地址空间 划分为同等大小的称为页面的块。 对应与物理内存 称为页框。 通过也部分程序 需要的页面 加载到内存中，即可实现 部分程序在内存中即可运行。
而因为物理内存是有限的， 则需要在 一定时机将页面 换入换出来使用有限的物理内存 建立无限的内存抽象。

页面置换算法:

为了使分页系统良好工作 。还需要关注更多的全局性问题， 比如 程序工作集大小的确定， 程序间的内存分配策略 以及其所需的页面大小等。

除了通过分页方案来构建虚拟内存 抽象之外 分段也是一个选择，然而因为几乎没有操作系统的开发者 喜欢分段系统。导致分段 无人问津， intel x86 的64位版本 也取消对分段的支持。

重要的问题：

  1. 虚拟内存的抽象 建立的目的 是啥， 需要复习
  2. 交换技术 存在的目的 又是为了什么？ 采用分页系统之后 依然需要 交换技术吗？ 是否依然有必要 记录 物理内存的空闲区呢？
  3. 分页系统中， 页表的 存储地方 在哪里？ 内存 还是专门的 硬件设备？ 如果 是的话，又存在什么问题？ 不是的话 又是 如何解决的？ 为何 需要 TLB 其解决的问题的目的是啥？
  4. 为什么 存在页面置换算法？ 算法存在的根本目的是啥？ 各个算法 考虑的点 是什么？ 什么才是最优的页面置换算法？ 置换算法 是否仅考虑 单个进程即可？ 进程间对于 系统 物理内存的 争抢 如何解决？ 工作集的概念 又是为了解决什么问题？

虚拟内存共享： 允许多个进程 共享同一部分内存， 使高带宽 进程 消息传递称为可能。 可用来实现高性能的 消息传递系统。 传递消息的方式：