操作系统备忘录-虚拟存储器

1. 虚拟存储器概述

内存扩容的方式

  • 物理
  • 逻辑——虚拟存储管理

局部性原理

发现

  • 程序执行时，除了少部分的转移和过程调用指令外，在大多数情况下仍是顺序执行的
  • 过程调用将会使程序的执行轨迹由一部分区域转至另一部分区域，但经研究看出，过程调用的深度在大多数情况下都不超过5
  • 程序中存在许多循环结构，这些虽然只由少数指令构成，但是它们将多次执行
  • 程序中还包括许多对数据结构的处理， 如对数组进行操作，它们往往都局限于很小的范围内

特点

  • 时间局限性
    • 如果程序中的某条指令一旦执行，则不久以后该指令可能再次执行；如果某数据被访问过，则不久以后该数据可能再次被访问。产生时间局限性的典型原因，是由于在程序中存在着大量的循环 操作
  • 空间局限性
    • 一旦程序访问了某个存储单元，不久之后其附近的存储单元也将被访问，即程序在一段时间内所访问的地址，可能集中在一定的范围之内，其典型情况便是程序的顺序执行

定义

  • 虚拟存储器，是指具有请求调入功能和置换功能，能从逻辑上对内存容量加以扩充的一种存储器系统

    页面置换：在地址映射过程中，若在页面中发现所要访问的页面不再内存中，则产生缺页中断(page fault)。当发生缺页中断时操作系统必须在内存选择一个页面将其移出内存，以便为即将调入的页面让出空间

    • 虚拟性
      • 从逻辑上扩充内存容量，用户看到的内存容量大于实际物理内存容量

原理

  • 基于局部性原理，不是把作业或进程的程序和数据全部装入内存后才开始执行，而是只装入核心和反复调用执行的部分；其它部分在执行过程中动态调入

实现

  • 请求分页系统
  • 请求分段系统

与传统存储器的对比

  • 多次性
    • 传统的方式是一次装入
  • 对换性
    • 无须在作业运行时常驻内存

2. 请求分页存储管理方式

扩展页表

3. 硬件支持

  • 请求页表机制
  • 缺页中断机构
  • 地址变换机构

3.1. 缺页中断机构

缺页：所要访问的页尚未调入内存

  • 访问的页不在内存时，发生缺页中断
  • 在指令执行期间产生和处理中断信号

3.2. 地址变换机构

  • 产生和处理缺页中断

  • 从内存中置换页

  • 输入请求页号，输出物理地址

4. 内存分配与置换

单进程的最小物理块数的确定

  • 保证进程正常运行所需的最小物理块数
  • 与计算机的硬件结构有关，如单地址指令且采用直接寻址方式，则所需的最少物理块数为2：存放指令的页面、存放数据的页面

进程间的块的置换策略

  • 固定分配局部置换
    • 为每个进程分配一组固定数量的物理块，进程运行时不再改变。若发生缺页，从分配的$N$个页面中选出一页换出，调入下一页
  • 可变分配全局置换
    • 只要某进程发生缺页，都将获得新的物理块，仅当空闲块用完时，系统才选择一个未锁定的页面调出
  • 可变分配局部置换
    • 当该进程发生缺页时，只允许从自己的物理块中选出一个进行换出外存

进程间的块分配算法

  • 平均分配算法
  • 按比例分配算法
  • 考虑优先权的分配算法

5. 调入策略

何时

  • 预调页策略
    • 预测不久以后被访问的页调入内存
    • 主要用于首次调入
  • 请求调页策略
    • 运行中，访问的页不在内存时，由OS调入
    • 容易实现，但每次调入一页，开销大

何处

外存组织

  • 存放文件的文件区
    • 离散
  • 存放对换页面的对换区
    • 连续，故快

UNIX

  • 由于与进程有关的文件都放在文件区，故凡是未运行过的页面，都应从文件区调入
  • 对于曾经运行过但又被换出的页面，由于是被放在对换区，因此在下次调入时，从对换区调入
  • 由于UNIX系统允许页面共享，因此，某进程所请求的页面有可能已被其它进程调入内存，此时也就无须再从对换区调入

6. 页面置换算法

目的

  • 如访问页不在内存，且内存无空闲空间需从内存调出一页至硬盘对换区
    • 理论上将以后不再访问的页面换出
    • 实际上淘汰被访问概率最低的页

算法

  • 最佳(Optimal)

    • 淘汰以后永不使用的， 或许是在 最长(未来)时间内不再被访问的页面
      • 无法实现，因为实际上无法预知将来的访问次序

  • 先进先出(FIFO)

    • 淘汰在内存最久的页面
      • 与实际运行规律不符
      • 页面调入的先后不能反映页面的使用情况，性能较差

  • 最近最久未使用及最少使用 (Least Recently Used, LRU)

    • 记录每个页面距离上次被访问的时间$t$,淘汰$t$最大的页面

  • Clock

    • 简单Clock

      给每个页帧关联一个使用位。当该页第一次装入内存或者被重新访问到时，将使用位置为1。每次需要替换时，查找使用位被置为0的第一个帧进行替换。在扫描过程中，如果碰到使用位为1的帧，将使用位置为0，在继续扫描。如果所有帧的使用位都为0，则替换第一个帧。

    • 改进Clock

      考虑置换代价，页面是否被修改

      • 1类(A=0, M=0): 表示该页最近既未被访问， 又未被 修改， 是最佳淘汰页
      • 2类(A=0, M=1)： 表示该页最近未被访问， 但已被修 改， 并不是很好的淘汰页
      • 3类(A=1, M=0)： 最近已被访问， 但未被修改， 该 页有可能再被访问
      • 4类(A=1, M=1): 最近已被访问且被修改， 该页可能再被访问
      • 图源见水印

7. 抖动与工作集模型

前面介绍的各种页面置换算法，都是基于一个前提, 即程序的局部性原理。但是此原理是否成立?

抖动

如果分配给一个进程的物理页面太少，不能包含整个工作集，即$驻留集\subset 工作集$，则进程将会造成很多缺页中断，需要频繁地在内存与外存之间替换页面，从而使进程的运行速度变得很慢，这种状态称为“抖动”

  • 工作集：一个进程当前正在使用的逻辑页面集合

  • 驻留集：在当前时刻，进程实际驻留在内存当中的页面集合

8. 请求分段存储管理方式

  • 请求页表机制

  • 缺页中断机构

  • 地址变换机构

9. 分段的共享与保护

共享段表

为了实现分段共享，可在系统中配置一张共享段表，所有各共享段都在共享段表中占有一表项。表项中记录了共享段的段号、段长、内存、始址、存在位（是否已调入内存）等信息，并记录了共享此分段的每个进程的情况

共享段的分配

  • 第一个请求使用该共享段的进程，系统为该共享段分配一物理区， 再把共享段调入，同时将该区的始址填入请求进程的段表，在共享 段表中增加一表项，填写有关数据，把count置为1
  • 其它进程需要调用该共享段时，而只需在调用进程的段表中，增加 一表项，填写该共享段的物理地址；在共享段的段表中，为此进程 增加一表项，再执行count=count+1操作

共享段的回收

  • 当共享此段的某进程不再需要该段时，在进程段表中撤销相应表项， 撤销共享段表中该段表项中这一进程的信息，以及执行count=count-1 操作
  • 若结果为0，则须由系统回收该共享段的物理内存，以及取消在共享 段表中该段所对应的表项， 表明此时已没有进程使用该段；否则(减 1结果不为0)， 则只是取消调用者进程在共享段表中的有关记录

10. 例题

页面大小为 4KB，一次内存的访问时间是100ns，一次快表（TLB）的访问时间是 10ns，处理一次缺页的平均时间为 108ns（已含更新 TLB 和页 表的时间）， 进程的驻留集大小固定为 2，采用最近最少使用置换算法（LRU）和局部淘汰策 略。

假设①TLB 初始为空；②地址转换时先访问 TLB， 若 TLB 未命中，再访问页 表（忽略访问页表之后 的 TLB 更新时间）；③有效位为 0 表示页面不在内存，产生缺页中断，缺页中断处理后，返回到产生 缺页中断的指令处重新执行。

设有虚地址访问序列 2362H、1565H、 25A5H，请问：
（1）依次访问上述三个虚地址，各需多少时间？给出计算过程。
（2）基于上述访问序列，虚地址 1565H 的物理地址是多少？请说明理由。