9.1 背景
虚拟地址空间：进程在内存中存放的逻辑视图。如图所示。
虚拟内存：是一种内存管理技术，它会使程序自己认为自己拥有一块很大且连续的内存，然而，这个程序在内存中不是连续的，并且有些还会在磁盘上，在需要时进行数据交换 。
允许随着动态内存分配，堆向上生长；允许随着子程序的不断调用，栈向下生长。只有在堆和栈生长时，才需要实际的物理页。包括空白的虚拟地址空间成为稀地址空间。其优点是：随着程序的执行，栈或堆段的生长或需要载入动态链接库（或共享对象）时，这些空白可以填充。
虚拟内存也允许文件和内存通过共享页而为两个或多个进程所共享。如图所示：
9.2 按需调页 在需要时才调入相应的页（可视为懒惰交换）
区分：交换程序是对整个进程操作（因此这里是懒惰交换），调页程序只是对进程的单个页进行操作，按需调页使用的是调页程序。
有效位和无效位：有效：表示相关的页既合法也在内存中；无效：表示该页不在进程的逻辑地址空间内(有的博客说此时应显示NULL)或有效但是在磁盘中。如图所示：
Q:当进程试图访问未调入内存（在磁盘上）的页，将会如何？
A:对这些标记为无效的页，将产生页错误陷阱。由于操作系统未能将所需的页调入内存而产生。处理流程：
(1)检查进程的内部页表(通常与PCB一起保存)，以确定该引用是合法的还是非法的地址访问；
(2)若引用非法，则终止进程。若引用有效但尚未调入页面，则现在应调入；
(3)找到一个空闲帧（如从空闲链表中选一个）；
(4)调度一个磁盘操作，以便将所需要的页调入刚分配的帧；
(5)当磁盘读操作完成后，修改进程的内部表和页表，以表示该页已在内存中；
(6)重新开始因陷阱而中断的指令，进程现在可以访问所需页。如图所示：
极端情况：所有的页都不在内存中，成为纯粹按需调页：只有在需要时才将页调入内存。
原理：局部性：
空间局部性：电脑中某一块内存在使用时，在不久的将来会使用内存地址相近的一块内存区域。
时间局部性：电脑中某一条指令在使用完之后，在不久的将来有很大可能再次使用它。
因此，有的程序的单个指令可能访问多个页的内存，从而一个指令可能产生多个页错误。不过由于局部性，这种情况很少见。
硬件支持：（1）页表：该表能够通过有效-无效位或保护位的特定值，将条目设为无效；
（2）次级存储器：保存不在内存中的页，通常为快速磁盘，通常称为交换设备，用于交换的这部分磁盘通常称为交换空间。
关键：能够在页错误后重新执行指令，出现页错误时，保存中断进程的状态(寄存器、条件代码、指令计数器)，必须能够按完全相同的位置和地址重新开始执行进程。
性能分析：计算按需调页内存的有效访问时间：
设p为页错误的概率(0<=p<=1)，则有效访问时间为：
有效访问时间 = （1-p）*ma + p*页错误时间 ma：内存访问时间
9.3 写时复制
fork():为子进程创建一个父进程地址空间的副本，复制属于父进程的页。但由于许多子进程在创建之后立即执行exec()，所以父进程地址空间的复制可能没有很必要。
exec():
fork()函数通过系统调用创建一个与原来进程（父进程）几乎完全相同的进程（子进程是父进程的副本，它将获得父进程数据空间、堆、栈等资源的副本。注意，子进程持有的是上述存储空间的“副本”，这意味着父子进程不共享这些存储空间。linux将复制父进程的地址空间内容给子进程，因此，子进程由了独立的地址空间。），也就是这两个进程做完全相同的事。
在fork后的子进程中使用exec函数族，可以装入和运行其它程序（子进程替换原有进程，和父进程做不同的事）。
exec函数族可以根据指定的文件名或目录名找到可执行文件，并用它来取代原调用进程的数据段、代码段和堆栈段。在执行完后，原调用进程的内容除了进程号外，其它全部被新程序的内容替换了。另外，这里的可执行文件既可以是二进制文件，也可以是Linux下任何可执行脚本文件。
写时复制技术：允许父进程与子进程开始时共享同一页面，这些页面被标记为写时复制页，即如果任何一个进程需要对页进行写操作，就创建一个共享页的副本。如图所示：
假设子进程试图修改含有部分栈的页，且操作系统可识别出该页为写时复制页(注意：只有可能修改的页才需要被标记为写时复制，不能修改的页(即包含可执行代码的页)可以为父进程与子进程所共享)，则 OS创建一个该页的副本，将其映射到紫禁城的地址空间内，这样，子进程会修改自己的页，而非父进程的页。
Q：如何选择一个空闲页被分配用于写时复制？
A:OS提供了空闲缓冲池。这些空闲页在进程栈或堆必须扩展时用于分配，或用于管理写时复制页。OS通常采用按需填零的技术分配页。即这些页在分配之前先填零，清除以前内容。
扩展：vfork()?(fork()的变种，虚拟内存fork)
vfork()会将父进程挂起，子进程使用父进程的地址空间。vfork不采用写时复制，若子进程修改父进程地址空间的任何页，则这些修改后的页在父进程重启后可见。
fork()与vfork()的区别：https://blog.csdn.net/ValDC_Morning/article/details/77414826
9.4 页面置换
Q:当出现内存的过度分配时怎么办？过度分配：当一个用户进程执行时，一个页错误发生。OS会确定所需页在磁盘上的位置，但发现空闲帧列表上没有空闲帧，所有内存都在使用。
A:采用页置换。
9.4.1 基本页面置换
若没有空闲帧，则查找当前没有使用的帧，将其释放。释放方法：将其内容写到交换空间，并改变页表(和所有其他页表)以表示该页不在内存中。
现在页错误处理程序应包括页置换：
(1)查找所需页在磁盘上的位置；
(2)查找一个空闲帧：
a.若有空闲帧，则使用它；
b.若没有，则使用页置换算法选择一个牺牲帧；
c.将牺牲帧的内容写到磁盘上，改变页表和帧表。
(3)将所需页读入(新)空闲帧，改变页表和帧表；
(4)重启用户进程。
可以通过修改位/脏位降低额外开销。当页内的任何字或字节被写入时，硬件会设置该页的修改位表示该页已修改。通过查看该位被设置可知自从磁盘读入后该页已发生修改。这样，当发生页面置换时，如果该位未被设置，说明该页未被修改，故不需将其写回磁盘上。
实现按需调页，主要解决两个问题：帧分配算法 && 页置换算法
9.4.2 FIFO页置换
选最旧的页来置换。
存在Belady异常：页错误率可能会随着所分配的帧数的增加而增加。
9.4.3 最优置换 OPT/MIN optimal pape-replacement algorithm
置换（未来）最长时间不会使用的页。（看未来）。确保对于给定数量的帧会产生最低可能的页错误率。难以实现，主要用于比较研究。
9.4.4 LRU页置换 最近最少使用算法 least-recently-used algorithm
使用离过去最近作为不远将来的近似，可置换最长时间没使用的页。（过去距离现在越远，越应该被替换）
硬件实现：用计数器or栈。
9.4.5 近似LRU页置换
页表中每项关联一个引用位，每当引用一个页时（无论是对页的字节进行读/写），相应页表的引用位会被硬件置位。
二次机会算法：
基本算法是FIFO算法。当要选择一个页时，检查其引用位，如果其值为0，则直接置换该页。若引用位为1，则给该页第二次机会，并将其引用位清零，且其到达时间设为当前时间，并选择下一个FIFO页。如图所示：
9.4.6 基于计数的页置换 为每个页保留一个用于记录其引用次数的计数器。
最不经常使用页置换算法：LFU 置换计数最小的页
最常使用页置换算法 ： MFU 置换计数最大的页： 基于理论：具有最小次数的页可能刚调进来，且还没有使用。
