前言

基本假设：进程的代码和数据只有部分装入内存
虚拟内存技术允许将大逻辑地址空间映射到小的物理内存。虚拟内存允许极大的进程运行，且提高了多道程序的程度，增加了CPU利用率。它使得程序员不必考虑内存可用性。另外，虚拟内存允许进程共享系统库与内存。当父子进程共享内存页时，虚拟内存也允许写时复制来创建进程。

一、 背景

有些情况下不需要将整个程序放入内存中：

1. 程序中有处理异常错误条件的代码
2. 数组、链表和表通常分配了比实际所需要的更多的内存
3. 程序某些选项可能很少使用

虚拟内存的好处：

1. 使程序不再受现有的物理内存空间限制
2. 提高了多道程序的程度，增加了CPU利用率
3. 虚拟内存也允许文件和内存通过共享页而为两个或多个进程所共享，这带来了以下优点：
   a) 通过将共享对象映射到虚拟地址空间，系统库可为多个进程所共享。
   b) 虚拟内存允许进程共享内存
   c) 虚拟内存可允许在系统调用fork()创建进程期间共享页，从而加快进程创建

二、 按需调页：在需要时才调入相应的页

1. 交换程序对整个进程进行操作，而调页程序只是对进程的单个页进行操作（采用懒惰交换，只有在需要页的时候，才将其调入内存）
2. 当换入进程时，调页程序推测在该进程再次换出之前会用到哪些页。这样就可以避免读入那些不适用的页，也减少了交换时间和所需的物理内存空间
3. 有效-无效位：1表示页合法且在内存中，0表示页无效且在磁盘上。初始值为0，试图访问为0的页时会发生页错误陷阱（在内存管理中1表示有效，0表示无效）。当访问无效页面时，不会对MMU进行地址转换
4. 对标记为无效的访问会产生页错误陷阱。分页硬件，在通过页表转换地址时，将发现已设置了无效位，会陷入操作系统。这种陷阱是由于操作系统未能将所需的页调入内存引起的。
5. 是否合法需要在中断程序中判断
6. 长期调度的时候会决定哪些页放入内存，哪些放在磁盘
7. 页错误陷阱的处理：
   a) 检查进程的内部页表（通常与PCB一起保存），以确定该引用是合法还是非法的地址访问。该判断在中断程序中进行。
   b) 如果引用非法，那么终止进程。如果引用有效但是尚未调入页面，那么现在应调入。
   c) 找到一个空闲帧（例如，从空闲帧列表中选取一个）。
   d) 调度一个磁盘操作，以便将所需要的页调入刚分配的帧。是磁盘I/O采用DMA方式进行，会将进程放入等待队列
   e) 当磁盘读操作完成后，修改进程的内部表和页表，以表示该页已在内存中。I/O完成
   f) 重新开始因陷阱而中断的指令。进程现在能访问所需的页，就好像它似乎总在内存中。进程状态改变
   
8. 通过第一次中断（缺页异常引发的中断）陷入操作系统，操作系统启动I/O操作，I/O操作完成引发第二次中断
9. 有的指令（如MOV）可能会访问多个（三个）页的内存（一页指令，两页数据）
10. 页表：该表能通过有效无效位将条目设置为有效/无效
11. 次级存储器：存储不在内存的页，一般为快速磁盘，即交换空间
12. 请求调页的关键是能够在页错误之后重新执行指令
13. 性能：设P为页错误的概率（0≤P≤1），如果P等于0，则不存在页错误，如果P等于1，则每次访问都存在页错误。有效访问时间（EAT）=（1-P）内存访问时间+P页错误时间
14. 交换空间的两种使用方法：
    a) 进程在创建时将整个文件镜像复制到交换空间中，并从交换空间进行按页调度
    b) 从文件系统中按需调页，页置换时将页写入交换空间
15. 页错误会引起如下序列的动作产生：
    a) 陷入到操作系统
    b) 保存用户寄存器和进程状态
    c) 确定中断是否为页错误
    d) 检查页引用是否合法并确定页所在磁盘的位置
    e) 从磁盘读入页到空闲帧中
    i. 在该磁盘队列中等待，直到处理完读请求
    ii. 等待磁盘的寻道和或延迟时间
    iii. 开始将磁盘的页传到空闲帧
    f) 在等待时，将CPU分配给其他用户（CPU调度，可选）
    g) 从I/O子系统接收到中断（以示I/O完成）
    h) 保存其他用户的寄存器和进程状态（如果执行了第6步）
    i) 确定中断是否来自磁盘
    j) 修正页表和其他表以表示所需页现已在内存中
    k) 等待CPU再次分配给本进程
    l) 恢复用户寄存器、进程状态和新页表，再重新执行中断的指令
16. 以上不是所有的步骤都是必须的。
17. 三个主要的页错误处理时间：
    a) 处理页错误中断
    b) 读入页
    c) 重新启动进程

三、 写时复制

(1) 允许父子进程开始时共享同一页面，如果任一进程需要对该页进行写操作，则创建一个共享页的拷贝。所有非修改页会被父进程和子进程共享
(2) 写时复制需要的空闲页来自一个空闲缓冲池，该池中的页在分配前先填充0，以清除之前的内容（按需填零）
Vfork()（虚拟内存fork）是系统调用fork()的变种，操作不同于写时复制的fork()，vfork()会将父进程挂起，子进程使用父进程的地址空间。由于vfork()不使用写时复制，因此如果子进程修改父进程地址空间的任何页，那么这些修改过的页在父进程重启时是可见的。所以，vfork()必须小心使用，以确保子进程不修改父进程的地址空间。Vfork()主要用于在子进程被创建后立即调用exec()的情况

四、 页面置换

（1） 基本页面置换

1. 查找所需页在磁盘上的位置
2. 查找一个空闲帧：
    如果有空闲帧，那么就使用它
    如果没有空闲帧，那么就使用页置换算法以选择一个**“牺牲”帧**
    将“牺牲”帧的内容写到磁盘上，改变页表和帧表
3. 将所需页读入（新）空闲帧，改变页表和帧表
4. 重启用户进程
    通过修改位或脏位来降低开销，表示是否需要重写到磁盘上的副本
    需要开发帧分配算法与页置换算法，分别决定一个进程分配多少帧以及如何选择要置换的页
    通过运行一个特殊字符串（引用串）来检验算法并计算页错误率

（2）FIFO页置换

1. 记录每个页进入内存的时间，并选择最老的页换出
2. Belady异常：页错误率可能会随着分配帧的数目的增加而增加，而不是一般情况下的降低

（3）最优页置换，OPT/MIN

1. 是所有算法中产生页错误率最低的，且不会有Belady异常的情况
2. 置换最长时间不会被使用的页（向前看）
3. 缺点：程序在执行时不知道未来要访问的页，所以难以实现

（4） LRU页置换：

即最近最少使用算法，没有Belady异常，和最优置换一样属于栈算法

1. 置换最长时间内没有被使用的页，这种策略为向后看（而不是向前看）最优页置换算法
2. 计数器：可以通过为每一个页表项关联一个时间域，并给CPU增加一个计数器，每次内存引用，为对应页表项的时间域进行更新，置换最小的页
3. 栈：或者通过页码栈，每次将被引用的页从栈中删除并重新放回顶部，这样栈的顶不必定时最近使用的页，而底部为LRU页

（5） 近似LRU页置换

1、附加引用位算法：每页关联一个引用位，初始化为0，当页被引用的时候，改为被设置为1。引用位可以有多个，比方说有8位引用位，就表示着该页在最近8个时间周期内被使用的情况。而11000100比01110111的页更为最近使用。每次选择8位最小的一个页为LRU页，进行置换。
2、二次机会算法：基于FIFO算法。当选择时，检查引用位，如果为0则直接进行置换，否则会给第二次机会，并将引用位清零，到达时间设置为当前时间。

（6）基于计数的页置换

为每个页保留一个用于记录其引用次数的计数器，有两种算法：
① 最不经常使用页置换算法（LFU）
② 最常使用页置换算法（MFU）

五、 帧分配：

即每个进程正常执行都需要一个最小的帧数，性能和页置换

1. 给每个进程分配最低数量的页，必须有足够的帧容纳所有单个指令所引用的页，而帧的最少数量是由计算机定义的。
2. 指令是6字节，可能跨2页
3. 要移动的字符的块和要移动到目的的区域也可能都要跨页。
4. 有两种主要的分配方法：
   ①固定分配
   ②优先级分配

（一）、固定分配

1. 有两种：
   ①平均分配
   ②按比例分配
2. 每个进程所分配的数量会随着多道程序的级别而改变，多道程序的程度增加（内存中进程的数量增加），那么每个进程会失去一些帧来给新的进程

（二）、优先级分配

1. 按优先级比例而不是进程大小来分配
2. 如果一个进程产生了一个页错误，那么可以：
   ①从自身的帧中选择用于替换
   ②从比自身优先级低的进程中选取帧用于替换

三）、全局分配与局部分配

1. 全局置换：允许一个进程从所有帧集合中选择一个置换帧，而不管该帧是否已分配给其他进程；一个进程可以从另一个进程中取帧。通常会有更好的系统吞吐量，且更为常用
2. 局部置换：要求每个进程仅从其自己的分配帧中进行选择

六、 系统颠簸

1. 如果一个进程没有足够的页，那么会一直忙于将页面换进换出，页错误率就会非常高。这会导致CPU使用率低，新的进程会加入到系统中来。
2. OS发现CPU使用率低，会加大多道程序程度，使更多进程加入到内存，使页错误率更高，最终系统无法完成工作
3. 局部置换可以限制颠簸在进程之间传递与扩散，而不能解决
4. 工作集合策略研究一个进程实际正在使用多少帧，定义了进程执行的局部模型。
5. 当进程执行时，它从一个局部移向另一个局部。局部是一个经常使用页的集合。一个程序通常由多个不同局部组成，它们可能重叠。
6. 当一个子程序（函数）调用的时候，就定义了一个新局部
7. 局部是由程序结构与数据结构来定义的，如果分配的帧少于局部的大小，进程会颠簸

（一）、工作集合模型：基于局部性假设

1. 定义工作集合窗口，检查最近a个页面的引用，即工作集合。如果正在使用，则保留，否则，会在上次引用的a个时间单位后删除
2. 工作集合模型是程序局部的近似
3. 精确度与a的大小有关，如果a太小，则不能包含整个局部。若太大，可能包含多个局部
4. WSSi (进程Pi的工作集) = 最近所引用的所有页面的总数（不同时刻值不同）
5. D ＝ ∑WSSi 表示总的帧需求量。如果 D 大于可用帧数量，那么有的进程就得不到足够帧，从而会出现颠簸
6. 这时可以悬挂某些进程，以消除颠簸现象
7. OS会跟踪每个进程的工作集合，并分配大于其工作集合的帧数。如果有空闲帧，则可以启动另一个进程
8. 通过固定定时中断和引用位，能够近似模拟工作集合模型

（二）、页错误频率

1. 可以灵活地控制颠簸
2. 如果实际的页错误频率太高，则分配更多的帧，如果太低，就可以从进程中拿走帧
3. 如果太高而又没有可用的空闲帧，那么就选择一个进程进行暂停，将其的帧进行释放，并分配给错误率高的进程

七、 其他考虑

1. 页的大小如何选择：
   ①若考虑碎片，则需要小页
   ②若考虑页表大小，则需要大页
   ③若考虑I/O开销，则需要大页
   ④若考虑局部性，会有两个极端的矛盾。更小的页应用导致更少的I/O和更少的总的分配内存；而为了降低页错误数量，需要大页。
2. TLB范围：通过TLB可访问的内存量
3. 在理想的时候，一个进程所有的工作集合均在TLB中