第九章：虚拟内存
虚拟内存技术允许执行进程不必完全在内存中。虚拟内存的优点是可以使执行的程序比物理内存大。
虚拟内存将内存抽象为一个巨大的，统一的存储数组，进而将用户看到的逻辑内存与物理内存分开
9.1 背景
在第八章的情形下，执行指令必须在内存中，因此要将整个进程放入内存中
但是将指令全部放入物理内存中就意味着程序的大小被限制在物理内存的大小以内。而实际上，在很多时候，并不需要将整个程序放入内存中
使用虚拟内存的好处
- 使程序不再受现有的物理内存空间限制。用户可以为一个巨大的虚拟地址空间编写程序，简化了编程工作量
- 每个用户程序使用了更少的物理内存，有更多程序可以并发执行，CPU使用率增加
虚拟内存将用户逻辑和物理内存分开，使物理内存有限的情况下，为程序员提供了巨大的虚拟内存
9.2 按需调页
执行程序从磁盘载入内存有两种方式
- 在程序执行时，将整个程序载入到内存
- 只有在需要时才调入相应的页，这种技术被称为按需调页
按需调页的方法经常被虚拟内存系统采用，只有程序执行需要时才载入页，从未访问过的页不会进入物理内存
按需调页系统类似于使用交换的分页系统，进程通常驻留在二级存储器上，需要只能执行进程时，将它换入内存。这种交换使用的是懒惰交换，懒惰交换只有在需要页时，才将它调入内存
交换程序对整个进程进行操作，而调页程序只对进程的单个页进程操作
9.2.1 基本概念
首先，换入进程，此时调页程序会推测该进程再次换出之前会用到哪些页。调页程序不是调入整个进程，而是把那些必须的页调入内存。
需要一定的硬件支持来区分哪些页在内存中，哪些页在磁盘上。可以使用之前的有效-无效位达到这个目的
当设为有效时，表示该页合法且在内存中
当设为无效时，可能有两种情况。一种是这个页不在进程的逻辑空间中，另一种情况是该页有效，但是不在内存中，在磁盘中
当进程试图访问那些尚未调入内存的页时，会产生页错误陷阱。这种陷阱是由于操作系统未能将所需的页调入内存引起的
处理这种页错误的步骤
- 检查进程的内部页表，确定该引用是合法的还是非法的
- 如果引用非法，则终止进程。如果引用有效但尚未调入页面，则现在调入
- 找到一个空闲帧
- 将页从磁盘中调出，将该页调入刚分配的帧
- 当磁盘读操作完成后，修改进程的内部表和页表（修改有效位），表示该页已在内存中
- 重新开始因陷阱而中断的指令
9.2.2 按需调页的性能
关于按需调页过程中内存的有效访问时间（EAT）
内存访问时间：ma
如果没有出现页错误，有效访问时间=内存访问时间
如果出现页错误，就必须从磁盘先读入页，再访问所需要的字
设页错误的概率为p，则 有效访问时间 = (1-p) * ma + p * 页错误时间
一个计算有效内存访问时间的例子
对于按需调页而言，降低页错误率是很重要的。否则有效访问时间增加，会显著降低进程的执行速度
9.3 写时复制
如果采用页面共享的技术，在创建进程的开始阶段可能不需要按需调页。
比如采用fork创建进程的开始阶段可能不需要按需调页
在使用fork时，理论上fork为子进程创建一个父进程地址空间的副本，复制属于父进程的页。
但实际上，许多子进程在创建之后通常马上会执行系统调用exec()，所以父进程地址空间的复制可能没有必要。
采用写时复制技术可以允许父进程和子进程在开始时共享同一页面，这些页面被标记为写时复制页，如果任意一个进程需要对页进行写操作，就创建一个共享页的副本
假设子进程试图修改某一页，且操作系统识别出该页被设置为写时复制页，那么操作系统就会创建一个该页的副本，并将它映射到子进程的地址空间内。这样，子进程会修改其复制的页，而不是父进程的页。采用写时复制技术，很显然只有能被进程修改的页才会被复制:所有非修改页可为父进程和子进程所共享。注意只有可能修改的页才需要标记为写时复制。不能修改的页(即包含可执行代码的页)可以为父进程和子进程所共享。
当确定一个页要采用写时复制时，操作系统一般会提供空闲缓冲池为其分配空闲页
操作系统一般采用按需填零的技术以分配这些页，按需填零页在分配之前先填零，清除了之前的内容
9.4 页面置换
内存的过度分配会出现以下问题。当一个用户进程执行时，如果发生一个页错误，操作系统会确定所需页在磁盘上的位置，但却发现空闲帧列表上没有空闲帧，所有内存都已被使用
操作系统可以选择页置换的方法解决这种问题
9.4.1 基本页置换
缺页错误的完整过程
1.查找所需页在磁盘上的位置
2.查找一个空闲帧
- 如果有空闲帧，就使用它
- 如果没有空闲帧，就使用页置换算法选择一个牺牲帧
- 将牺牲帧的内容写到磁盘上，改变页表和帧表
3.将所需页读入新的空闲帧，改变页表和帧表
4.重启用户进程
然而，上面的这种方式增加了有效访问时间
可以使用修改位或脏位以降低额外开销。每页或每帧可以有一个修改位，通过硬件与之关联。当该页被修改时，硬件会设置该修改位，表示该位已被修改。如果修改位已设置，就可以知道自从磁盘读入后该页已发生了修改。在这种情况下，如果该页被选择为替换页，就必须把该页写到磁盘上
为了实现按需调页，必须解决两个问题：帧分配算法和页置换算法
对于不同的页置换算法，评判的标准是，通常采用最小页错误率的算法
内存的引用序列称为引用串
9.4.2 FIFO页置换
最简单的页置换算法是FIFO算法。FIFO页置换算法为每个页记录着该页调入内存的时间。当必须置换一页时，将选择最旧的页。注意并不需要记录调入一页的确切时间。可以创建一个FIFO队列来管理内存中的所有页。队列中的首页将被置换。当需要调入页时，将它加到队列的尾部。
FIFO页置换算法的图解和说明
Belady异常：对有页置换算法，页错误率可能会随着所分配的帧数的增加而增加。而人们通常以为为进程增加内存会改善其性能
9.4.3 最优置换
最优页置换算法（OPT） 会置换最长时间不会使用的页。它是所有算法中产生页错误率最低的
图解及说明
核心思想：向后看，离当前位置最远的那个页被置换
但这种算法的缺点是，操作系统很难预料未来要用到哪些引用串
9.4.4 LRU页置换
最近最少使用算法（LRU），置换最长时间没有使用过的页
核心思想：向前看，离当前位置最远的那个页被置换
图解及说明
LRU算法的具体实现这里就不再赘述了，只介绍基本过程。
9.4.5 近似LRU页置换
由于许多硬件不支持真正的LRU算法，只能采用增加引用位的方式近似实现LRU算法
所有引用位的初值为0，当被引用时，引用为置为1
1.附加引用位算法
在规定时间内记录引用位，从而获取额外顺序信息
使用8位移位寄存器存储该页在最近8个时间周期内的使用情况
如果移位寄存器为00000000，则该页在8个时间周期内没有使用
如果移位寄存器为11111111，则该页在8个时间周期内都至少使用过一次
将8位字节作为无符号整数，则具有最小值的页为LRU页，可以被置换
2.二次机会算法
当选择一个页时，如果引用位为0，则直接置换该位。如果引用位为1，则给该页二次机会，其引用位清0。
一种实现二次机会算法(有时称为时钟算法)的方法是采用循环队列。用一个指针表示下次要置换哪一页。当需要一个帧时，指针向前移动直到找到一个引用位为0的页。向前移动时，它将清除引用位(见图9.17) 。一旦找到牺牲页，就置换该页，新页就插入到循环队列的该位置。
3.增强型二次机会算法
通过采用引用位和修改位的一对有序对来考虑，改进二次机会算法，采用这两个位，有四种可能类型
- （0，0）：最近未使用且未修改
- （0，1）：最近没有使用但修改过
- （1，0）：最近使用过但没有修改
- （1，1）：最近使用过且修改过
每个页都属于这四种类型之一。当页需要置换时，可使用时钟算法
9.5 帧分配
本节主要研究如何在各个进程中分配帧的问题？
9.5.1 帧的最少数量
帧的最少数量是由计算机的指令决定的
（可能）
9.5.2 分配算法
1.平均分配
在n个进程中分配m个帧，给每个进程m/n个帧。这种方案称为平均分配
2.按比例分配
根据进程大小，按比例将可用内存分配给每个进程
3.按进程优先级分配
按比例分配，但不是根据进程的大小，而是根据进程的优先级
9.6 系统颠簸
如果进程没有它活跃所需要的足够的帧，那么它会很快产生页错误。这时，它必须置换某个页。如果它的所有页都在使用，它置换一个页，但又立刻再需要这个页。因此它会一次又一次地产生页错误
这种频繁的页调度行为被称为颠簸。如果一个进程在换页上用的时间多于执行时间，这个进程就处于颠簸状态
9.6.1 系统颠簸的原因
操作系统会监督CPU的使用率，如果CPU使用率过低，会向系统中引入新进程。
但如果此时引入新进程，可能会导致新进程试图在有限的内存中拿到其它帧，从而引发更多页错误，形成更长的调页设备的队列。这将导致CPU使用率进一步降低，而操作系统再引入进程，导致恶性循环
通过局部置换算法能限制系统颠簸。采用局部置换，如果一个进程开始颠簸，那么它不能从其它进程拿到帧，且不能使后者也颠簸
为了防止颠簸，需要提供进程所需的足够多的帧。可用采用工作集合策略研究一个进程实际上正在使用多少帧。这种方法定义了进程执行的局部模型
9.6.2 工作集合模型
图解及说明
t1时刻的工作集合为{1,2,5,6,7}
t2时刻的工作集合为{3,4}
工作集合的属性是其大小。系统内每个工作进程的工作集合为WSSi，则总帧需求量D为
如果总的需求量D大于可用帧的数量m，那么有的进程就会得不到足够的帧，从而出现颠簸
9.6.3 页错误频率
可用使用页错误频率的策略来控制颠簸
颠簸具有高错误率，因此需要控制页错误率。当页错误率太高时，进程需要更多帧。如果页错误率太低，进程可能有太多帧
因此可用设置页错误率的上限和下限，如果实际页错误率超过上限，则为进程分配更多的帧，如果页错误率低于下限，则可以从该进程中移走帧
9.7 内存映射文件
如果采用标准的open()，read()和write()，文件每次访问时都需要一个系统调用和磁盘访问。
而采用内存映射机制可以将文件的访问作为普通内存访问，这种方法称为文件的内存映射
它允许一部分虚拟内存与文件逻辑相关联
9.7.1 基本机制
文件的内存映射可将磁盘块映射成内存的一页或多页。开始的文件访问与普通的请求页面类似，会产生页错误，之后文件的读写就按通常的内存访问来处理
由于采用内存操作文件，而不采用read()和write()，简化了文件的访问和使用
对映射到内存中的文件进行写操作，可能不会立即写到磁盘的文件中。操作系统可能采用定期检查并更新的方式
图例
转载：https://blog.csdn.net/weixin_46841376/article/details/117386265