text: 第三章 内存管理
  SJ_Sniper
  参考书籍:左万利《计算机操作系统教程(第4版)》 在第三章第一节中的内存管理的功能中讲到存储扩充的三种技术:覆盖、交换、虚拟存储。
  传统内存空间管理的各种方式:
  都有一个共同的问题，即当一个参与并发执行的进程运行时， 整个程序必须都在内存中 。
  因而， 假若进程的程序比内存可用空间还大，则该程序无法运行 。
  由于程序的局部性，一个进程在运行的任意一个阶段只需使用所占存储空间的一部分 ，这样 暂未用到的内存区域便会被浪费 。
  虚拟存储管理之所以能够工作，是基于局部性原理(principle of Iocality) 的，包括 时间上的局部性和 空间上的局部性 。
  时间上的局部性。
  程序中存在大量循环操作， 一条指令的执行与该指令下一次执行，以及一个数据的一次访问与下一次访问，在时间上是相对集中的。
  空间上的局部性。
  程序中相邻的指令与相邻的数据通常会被集中执行。
  高速缓存技术: 将近期会频繁访问到的数据放到更高速的存储器中，相对的，用不到的数据放在更低速的存储器中。
  定义:虚拟存储是一种借助于外存空间，允许一个进程在其运行过程中部分装入内存的技术。
  (注:虚拟存储的部分装入内存，部分(或全部)装入外存，运行中访问外存部分时动态调入，内存空间不够时用 置换算法 淘汰)
  多次性:分成部分多次调入内存。
  对换性:允许作业需要时换入、换出。
  虚拟性:逻辑上扩充，用户看到的内存容量远大于实际容量。
  虚拟存储系统 将内存和存储器有机地结合在一起，从而得到一个容量相当于外存储器、速度接近于内存的存储体系。
  (王道)虚拟内存的实现: 请求分页 、 请求分段 、 请求段页式存储管理 。
  虚拟存储管理涉及到外存空间的管理。
  外存空间是指磁盘等存储型设备上的存储区域，通常逻辑上可以划分为4个主要部分: 交换空间 、文件空间、输入井、输出井。
  而 交换空间 是用于实现虚拟存储的外存空间(内存的一种扩充)。
  【交换空间的另一个功能是还可用于中级调度】
  此处的外存储器的管理主要是对于Swap空间的管理。
  静态等长划分，2^i，称为一块(block) ， 块 是外存分配的基本单位，也是IO传输的基本单位。
  原则上，外存储器的分配可以采用与内存相仿的方法，基本单位是唯一的差别。
  外存空间的分配可以采用以下3种方法之一:空闲块表
  空闲块链
  位图(用1代表一个块的状态)
  为了实现调入调出功能， 需要知道:页面是否已经调入内存( 状态位 )
  页面在外存的存放位置( 外存地址 )
  为实现内存满时的置换功能，需要知道一些指标:
  要访问的页不在内存时，便产生一个 缺页中断 ，然后由操作系统的缺页中断处理程序 处理中断。
  (缺页中断由指令中指定的页面未在内存中引起，属于内中断)
  在处理缺页中断中， ① 如果内存中有空闲页框， 内存就读入 所需 页面 ， 并更新页表和快表 ; ②如果内存已满， 由页面 置换算法 选择一个 页面淘汰 ， 若 该页面在内存期间 被修改过 ，则要将其 写回外存 。
  未修改的页面不写回。
  ① 快表命中时，只需更新快表，只有当快表中的快表项删除时，才需要写回内存中的慢表。
  ② 缺页中断也需保存CPU现场。
  ③ 换入/换出页面都需要慢速的I/O操作，换入/换出太频繁，会有很大开销。
  好的置换算法应该追求更少的缺页率。
  淘汰策略:淘汰将来最长时间以后才能用到的页面。
  缺点: 然而， 因为进程在运行时无法准确预期页面“将来”的被访问情况，所以它是不能实现 的。
  意义: 效率最高，可用于与其他算法的比较，来判断一个算法的优劣。
  淘汰策略:最先调入内存的页面。
  依据:先进入的页面可能已经使用完毕。
  例外:有些公共的走子程序从始至终都要用到。
  实现方法:采用队列的形式 。
  按调入内存的次序排成一个队列，每次选择队头页面换出，换入的页面放在队尾。
  Belady异常 -- 当为进程分配的物理块数增大时，缺页次数不减反增的异常情况。
  虽然FIFO算法 简单 ，但换出的也有可能是最经常访问的页面，因此， 算法性能最差 。
  淘汰策略:淘汰最近一次访问距当前时间最长的页面。
  实现方式: 特殊的栈。
  缺页栈不满，压入栈顶;不缺页就将此页面调到栈顶;缺页且栈已满就淘汰掉栈底的页面。
  LRU算法性能好，最接近最佳置换算法，但实现困难，开销大，需要硬件资源加持。
  实现方法:为每个页面设置一个 访问位 ，再将内存中的页面通过链接指针 链接成一个循环队列 。
  6号页替换1号页，指针指向下一个。
  此时指针依然指向3号页，只有发生缺页时才移动。
  然后指针指向下一个 。
  简单时钟只考虑最近未被访问的页面，事实上，只有被淘汰的页面 被修改过 ， 才需要写回外存 。
  因此在其他条件相同时，还应该 优先淘汰 未被修改过的页面( 淘汰策略 )
  (访问位，修改位)
  第一轮 :替换第一个(0, 0)，即 最近未访问 但未被修改过的页面。
  本轮无标志位变化。
  第二轮 :替换第一个(0, 1)，即 最近未访问 且 已被修改过的页面。
  第四轮 :替换第一个(0, 1)。
  需一轮: 需两轮: 需三轮: 需四轮: 驻留集:请求分页存储管理中 ，进程在运行时是部分装入内存，而 给进程分配的物理块的集合就叫 驻留集。
  在虚拟存储管理的系统中， 驻留集大小一般小于进程总大小。
  但是， 若驻留集太小 ，会频繁缺页，系统需要花大量时间处理缺页; 若驻留集太大 ，会导致多道程序并发度下，降资源利用率降低。
  1️⃣ 固定分配: 操作系统分配固定数目页框，驻留集大小不变。
  (1)没有反映程序结构。
  不同的分支可能占用的内存块不同
  (2)没有反映程序在不同时刻的行为特性。
  在时间段之内，进程完全顺序执行，没有逻辑控制判断。
  2️⃣ 可变分配: 先分配一定数目页框，运行期间，视情况做适当增减，驻留集大小可变。
  页面置换有局部和全局之分。
  全局置换算法 :在内存的所有页框集合中选择淘汰页面。
  局部置换算法 :在当前缺页进程的页框集合中选择淘汰页面。
  (之前的置换算法全为 局部置换 )
  1️⃣固定分配局部置换
  系统为每个进程分配固定数量的物理块，运行期间各进程只能用自己的内存空间中置换页。
  缺点: 很难确定分配多少物理块给一个进程才算合理。
  2️⃣可变分配全局置换
  也开始分配物理块后，系统保持一个空闲物理块队列。
  发生缺页时:
  若队列不空，分配给该进程。
  若无空闲物理块，系统选择根据算法选择一个页面调出， 被选择的页面可能是系统中任何一个进程中的页。
  缺点: 被选中的进程，物理块减少，缺页率增加。
  3️⃣可变分配局部置换
  分配固定数量物理块后，若发生缺页，只能从自己的物理块中选择页面置换。
  系统会调节分配给各个进程的物理块数量。
  对于频繁发生缺页的进程，系统会为其多分配几个物理块，直至缺页率适度;反之，对于缺页率低的进程，分配的物理块就适当减少。
  页面调入时机是指何时将一个页面由外存储器调入内存。
  可以有两种方式 : 请调和 预调 。
  1.请调
  请求调入 ，即在运行期间 发生缺页中断时才将所缺页面动态调入内存。
  显然，被调入内存的页面一定会被用到，即不会发生无意义的页面调度。
  缺点: 从缺页中断发生到所需页面调入的期间， 进程需要等待 ，影响进程进度。
  2.预调
  预先调入， 缺页中断发生之前进行调度， 即提前调入可能会被访问的页面。
  (局部性原理)
  缺点: 不一定百分之百准确。
  由于程序中存在转移语句，可能预先调入的页面无意义，不会被用到。
  因此， 预调策略 主要用于进程的首次调入 ，由程序员指出调入的部分。
  而在 运行期间 发生缺页中断应 辅以 请调策略 。
  1.静态分配(通常采用的方法，在外存，永远保存进程的全部页面)
  进程运行之前， 将其所有页面全部装入外存储器 。
  页面 调入内存时 ， 外存 中 不释放 该页面。
  优点: 速度快，若淘汰的页面在内存中未修改，则不需要写回外存(外存有副本)。
  缺点: 浪费外存空间。
  进程运行之前， 仅将未装入内幕才能的那部分页面装入外存储器 。
  页面调入内存时， 外存释放所占页面 。
  这样，页面被淘汰后，无论是否修改过，都需要 重新申请外存空间 ，然后将页面写回外存储器。
  优点: 节省外存空间。
  缺点: 速度慢，淘汰时必须写回外存。
  在第4节外存储器管理技术中谈到交换空间(对换区)与文件空间(文件区)。
  1️⃣系统拥有足够的对换区空间
  2️⃣系统的对换区空间不足
  凡不会被修改的数据，从文件区调入，换出时不需写回磁盘。
  被修改的数据换出到对换区，并从对换区调入。
  3️⃣UNIX方式
  颠簸/抖动:页面在内存与外存之间频繁地换入换出。
  (大部分时间都处理换入换出IO操作，实际执行进程的时间很少。)
  产生颠簸的原因:
  分配给进程的物理页框数过少 (系统自身问题)
  淘汰算法不合理 (系统自身问题)
  程序结构不好 (编程人员需要注意)
  颠簸的处理:
  适当增加物理框架数 ( 为研究每个进程分配多少物理块，提出 “工作集” )
  改进淘汰算法
  改善程序结构，避免滥用转移指令、分散的全局变量、大型数组等。
  研究分配给进程多少物理块比较合适。
  一个进程从时刻(t-Δ)到时刻 t 的时间段内所访问页面的集合 WS (t, Δ) 称为该进程的工作集，其中 Δ 称为 窗口尺寸(window size) 。
  为使程序有效运行，工作集应能放入内存，分配的物理块数 (驻留集) 不少于 工作集 就行了。
  Δ 过小:活动页面不能全部装入内存，页故障率高;
  Δ过大:内存浪费。
  工作集模型能够非常成功地知道页面的分配，从而防止颠簸。
  不过，它的实现开销大，使用存在困难。
  颠簸是由于页故障率(缺页率)引起的，系统可以利用页故障率的反馈信息来动态地调整页面的分配，这就是页故障率反馈模型的思想。
  具体地说，可以规定一个页故障率的上界和下届。