操作系统第五章-虚拟存储系统

虚拟存储器的基本概念
- 虚拟存储器的引入
  - 常规存储器管理方式的特征
    - 一次性：作业在运行前需一次性地全部装入内存
    - 驻留性：作业装入内存后，便一直驻留在内存中，直至作业运行结束。
  - 局部性原理
    - 程序的执行总是呈现局部性。即，在一个较短的时间段内，程序的执行仅限于某个部分；相应的，它所访问的存储空间也局限于某个区域。
    - 时间局限性：如果程序中的某条指令一旦执行，则不久以后该指令可能再次执行；如果某数据被访问过，则不久以后该数据可能再次被访问。
    - 空间局限性：一旦程序访问了某个存储单元，在不久之后，其附近的存储单元也将被访问;
- 实现虚拟存储的一般过程
  - 进程运行之前，仅需要将一部分页面或段装入内存，便可启动运行，其余部分暂时保留在磁盘上。
  - 进程运行时，如果它所需要访问的页面（段）已经装入内存，则可以继续执行下去；
  - 如果其所需要访问的页面（段）尚未装入内存，则发生缺页（段）中断，进程阻塞。
  - 此时，系统将启动请求调页（段）功能，将进程所需的页（段）装入内存。
  - 如果当前内存已满，无法装入新的页（段），则还需要利用页（段）置换功能，将内存中暂时不用的页（段）交换到磁盘上，以腾出足够的内存空间。
  - 再将进程所需的页（段）装入内存，唤醒阻塞的进程，使之重新参与调度执行。
- 虚拟存储器的定义和特征
  - 虚拟存储器：是指具有请求调入功能和置换功能，能从逻辑上对内存容量加以扩充的一种存储器系统，其逻辑容量由内存容量和外存容量之和所决定，其运行速度接近于内存速度，而每位的成本却又接近于外存。
  - 特征
    - 多次性：一个作业被分为多次调入内存运行
    - 对换性：作业的运行过程中进行换进、换出
    - 虚拟性：能够从逻辑上扩充内存容量，使用户所看到的内存容量远大于实际内存容量。
- 虚拟存储管理的实现方法
  - 请求分页存储管理
  - 请求分段系统
请求分页存储管理
- 工作原理：作业运行时，只将当前的一部分装入内存其余的放在辅存，一旦发现访问的页不在主存中，则发出缺页中断，由OS将其从辅存调入主存，如果内存无空块，则根据某种算法选择一个页淘汰以便装入新的页面。
- 硬件支持
  - 页表机制
    - 页表项：页号、物理块号、状态位、访问位、修改位、外存地址
    - 状态位：也称存在位，标志该页是否驻留内存。
    - 访问位：记录一段时间内该页被访问的情况，如一段时间内该页被访问的次数或者多长时间未被访问。
    - 修改位：标记该页是否被修改过。注：为减少置换开销，通常选择未被修改过的页面置换。
    - 外存地址：用于记录该页在外存上的存储地址。
  - 缺页中断机构
  - 地址变换机构
- 内存分配策略和分配算法
  - 最小物理块数的确定：能保证进程正常运行所需的最小物理块数
  - 物理块的分配策略
    - 固定分配局部置换
      - 为每个进程分配一定数目的物理块，在整个运行期间都不再改变。
      - 实现这种策略的困难在于：应为每个进程分配多少个物理块难以确定。
    - 可变分配全局置换（常用）
      - 在采用这种策略时，先为系统中的每个进程分配一定数目的物理块，而OS自身也保持一个空闲物理块队列。
      - 当某进程发现缺页时，由系统从空闲物理块队列中，取出一个物理块分配给该进程，并将欲调入的（缺）页装入其中。
      - 仅当空闲物理块队列中的物理块用完时，OS才能从内存中选择一页调出，该页可能是系统中任一进程的页，这样，自然又会使那个进程的物理块减少，进而使其缺页率增加。
    - 可变分配局部置换
      - 为每个进程分配一定数目的物理块，但当某进程发现缺页时，只允许从该进程在内存的页面中选出一页换出，这样就不会影响其它进程的运行。
  - 物理块分配算法
    - 平均分配算法
      - 将系统中所有可供分配的物理块，平均分配给各个进程。
    - 按比例分配算法
      - 根据进程的大小按比例分配物理块的算法
    - 考虑优先权的分配算法
      - 通常采取的方法是把内存中可供分配的所有物理块分成两部分：
        一部分按比例地分配给各进程；
        另一部分则根据各进程的优先权，适当地增加其相应份额后，分配给各进程。
- 调页策略
  - 系统应当在何时把一个页面装入内存
    - 预调页
      - 可采用一种以预测为基础的预调页策略，将那些预计在不久之后便会被访问的页面，预先调入内存。
    - 请求调页
      - 仅当进程执行过程中，通过检查页表发现相应页面不在内存时，才装入该页面。
  - 从何处调入页面
    - 在请求分页系统中的外存分为两部分：
      - 用于存放文件的文件区
      - 用于存放对换页面的对换区
    - 调页情况
      - （1）系统拥有足够的对换区空间，这时可以全部从对换区调入所需页面，以提高调页的速度。
      - （2）系统缺少足够的对换区空间，这时凡是不会被修改的文件，都直接从文件区调入；
      - （3）UNIX方式。由于与进程有关的文件都放在文件区，应从文件区调入。故凡是未运行过的页面，都应从文件区调入。而对于曾经运行过但又被换出的页面，由于是被放在对换区，因此在下次调入时，应从对换区调入。
  - 页面调入过程
    - ① 每当程序所要访问的页面未在内存时，便向CPU发出一缺页中断。
    - ② 中断处理程序首先保留CPU环境，分析中断原因后，转入缺页中断处理程序。
    - ③ 如果内存已满，则须先按照某种置换算法从内存中选出一页准备换出；如果此页已被修改，则必须将它写回磁盘。
    - ④ 然后再把所缺的页调入内存，并修改页表中的相应表项，置其存在位为“1”，并将此页表项写入快表中。
    - ⑤ 形成所要访问数据的物理地址，再去访问内存数据。
- 页面置换算法
  - 最佳置换OPT算法
    - 从主存中移出永远不再需要的页面；如无这样的页面存在，则应选择最长时间不需要访问的页面。
  - 先进先出FIFO页面置换算法
    - 总是选择作业中驻留时间最长(即最老)的一页淘汰。即：先进入主存的页面先退出主存。
  - 最近最久未使用LRU置换算法
    - 选择最近最久未使用的页面予以淘汰。该算法赋予每个页面一个访问字段，用来记录一个页面自上次被访问以来所经历的时间t，当须淘汰一个页面时，选择现有页面中其t值最大的，即最近最久未使用的页面予以淘汰。
    - 硬件支持
      - 移位寄存器
        为了记录某进程在内存中各页的使用情况，须为每个在内存中的页面配置一个移位寄存器可表示为：R=Rn-1Rn-2Rn-3···R2R1RO
        当进程访问某物理块时，要将相应寄存器的最高位Rn-1位置成1。系统每隔一定时间（例如100 ms）将寄存器右移一位。
      - 栈
        可利用一个特殊的栈来保存当前使用的各个页面的页面号。每当进程访问某页面时，便将该页面的页面号从栈中移出，将它压入栈顶。
        栈顶始终是最新被访问页面的编号，而栈底则是最近最久未使用页面的页面号。
  - Clock置换算法NRU
    - 当采用简单clock算法时，为每页设置一位访问位，再将内存中的所有页面都通过链接指针链接成一个循环队列。
    - 当某页被访问时，其访问位被置1。
    - 置换程序从上次停止位置开始检查页面的访问位。
      - 如果是0，就选择该页换出；
      - 若为1，则重新将它置0，暂不换出，而给该页第二次驻留内存的机会。
    - 由于该算法是循环地检查各页面的使用情况，故称为clock算法。置换时是将未使用过的页面换出去，故又把该算法称为最近未用算法NRU。
  - 改进型Clock置换算法
    - 系统把一个页面移出内存时，如果该页面驻留内存期间没有被修改过，那么不必把它写回辅存，否则系统必须把它写回辅存。这表明，换出未修改过的页面比换出被修改过的页面开销小。
    - 显然，我们可以依据上述结论改进CLOCK算法。改进后的CLOCK算法将在置换范围内首选：
      - 在最近没有被使用过；
      - 在驻留内存期间没有被修改过的页面
    - 执行过程
      - （1）从指针所指示的当前位置开始，扫描循环队列，寻找A=0且M=0的第一类页面，将所遇到的第一个页面作为所选中的淘汰页。在第一次扫描期间不改变访问位A。
      - （2）如果第一步失败，即查找一周后未遇到第一类页面，则开始第二轮扫描，寻找A=0且M＝1的第二类页面，将所遇到的第一个这类页面作为淘汰页。在第二轮扫描期间，将所有扫描过的页面的访问位A都置0。
      - （3）如果第二步也失败，亦即未找到第二类页面，则将指针返回到开始的位置，并将所有的访问位复0。然后重复第一步，如果仍失败，必要时再重复第二步，此时就一定能找到被淘汰的页.
  - 其它置换算法
    - 最少使用LFU算法
    - 页面缓存算法PBA
- 访问内存的有效时间
  - 设内存读写周期为t，查找快表时间为λ，缺页中断处理时间为ɛ
  - 页面在内存且页表项在快表中：只需一次访问内存。 EAT= λ + t
  - 页面在内存但页表项不在快表中：需两次访问内存，一次读取页表，一次读取数据，另外还需更新快表。EAT= λ + t + t + λ=2(λ + t)
  - 页面不在内存：考虑查找快表时间、查找页表时间、缺页中断处理时间、更新快表时间、访问实际物理地址时间。EAT= λ + t +ɛ + λ + t = ɛ + 2(λ + t)
  - 引入快表命中率为α，缺页中断率为f，则有效访问内存时间为：EAT=λ +α t + (1- α)[ f(t +ɛ +λ) + (1-f)(t +λ) + t]
抖动与工作集
- 抖动：如果运行进程的大部分时间都用于页面的换入/换出，而几乎不能完成任何有效的工作，则称此进程处于抖动状态。抖动又称为颠簸。
  - 局部抖动
  - 全局抖动
- 工作集：指进程在执行过程中，从时间t开始的某段时间间隔Δ里进程实际访问的页面集合，记为w（t，Δ）。时间间隔Δ是工作集的窗口尺寸。
- 抖动产生的原因
  - 进程分配的物理块太少
  - 置换算法选择不当
  - 全局置换使抖动传播
- 抖动的预防
  - 采取局部置换策略
  - 引入工作集的算法
  - L=S准则。L缺页之间的平均时间，S平均缺页服务时间
  - 选择暂停的进程
请求分段存储管理
- 硬件支持
  - 在请求分段系统中，程序运行之前，只需先调入若干个分段（不必调入所有的分段），便可启动运行。当所访问的段不在内存中时，可请求OS将所缺的段调入内存。
  - 段表机制
    - 段表项：段名+段长+段的基址+存取方式+访问字段A+修改位M+存在位P+增补位+外存始址
  - 缺段中断机构
  - 地址变换机构
- 分段的共享与保护
  - 共享段表
    - 为了实现分段共享，可在系统中配置一张共享段表，所有各共享段都在共享段表中占有一表项
  - 共享段的分配与回收
    - 共享段的分配
      - 在为共享段分配内存时，对第一个请求使用该共享段的进程，由系统为该共享段分配一物理区，再把共享段调入该区，同时将该区的始址填入请求进程的段表的相应项中，还须在共享段表中增加一表项，填写有关数据，把count置为1；
      - 之后，当又有其它进程需要调用该共享段时，由于该共享段已被调入内存，故此时无须再为该段分配内存，而只需在调用进程的段表中，增加一表项，填写该共享段的物理地址；在共享段表中，填上调用进程的进程名、存取控制等，再执行count：＝count＋1操作，以表明有两个进程共享该段。
    - 共享段的回收
      - 当共享此段的某进程不再需要该段时，应将该段释放，包括撤消该进程段表中共享段所对应的表项，以及执行count:=count-1操作。
      - 若count结果为0，则须由系统回收该共享段的物理内存，以及取消在共享段表中该段所对应的表项，表明此时已没有进程使用该段；否则(减1结果不为0)，则只是取消调用者进程在共享段表中的有关记录。
  - 分段保护
    - 越界检查
    - 存储控制检查
    - 环保护机构