虚拟内存管理
虚拟内存的基本概念
虚拟内存是计算机系统内存管理的一种工作。它使得应用程序认为它拥有连续的可用的内存(一个连续完整的地址空间),而实际上,它通常是被分隔成多个物理内存碎片,还有部分暂时存储在外部磁盘存储器上,在需要时进行数据交换。
传统存储管理方式的特征、缺点
局部性原理
虚拟内存的定义和特征
如何实现虚拟内存工作
小结
请求分页管理方式
页表机制
缺页中断机构
地址变换机构
关于第5点
在具有快表机构的请求分页系统中，访问一个逻辑地址时，若发生缺页，则地址变换步骤是： 查快表(未命中)——查慢表(发现未调入内存)——调页(调入的页面对应的表项会直接加入快表)——查快表(命中)——访问目标内存单元
小结
页面置换算法
最佳置换算法(OPT)
最佳置换算法可以保证最低的缺页率，但实际上，只有在进程执行的过程中才能知道接下来会访问到的是哪个页面。操作系统无法提前预判页面访问序列。因此，最佳置换算法是无法实现的。
先进先出算法(FIFO)
最近最久未使用置换算法(LRU)
LRU淘汰的是最早被使用的Cache，算法可以分为两种实现：
A.时间戳
硬件记录最近一次访问时间，每次淘汰遍历求最早访问的Cache。
B.链表
Algorithm 4th：著名的前移编码策略，假设最近访问过的元素很有可能再次访问,因此可以用于缓存、数据压缩等许多场景。
这里将所有可能被淘汰的Cache用一张线性链表存储，当查询时，每次被查询到的Cache节点将会被移除出链表并且插入表头。如此一来，链表头将会是最新被访问的数据，而链表尾则会被淘汰。
这样一来，淘汰最早访问的Cache则非常方便，代价则是需要链表的结构是可修改的。
在硬件层，这两种实现都具有巨大的开销，因此难以用于实践。
时钟置换算法(CLOCK)
LRU->NRU: 对于Cache来说，能找到最早访问的固然好，但是宽容一点，不是最早，但是也很早被访问的被淘汰问题也不大，只要不淘汰最近被访问的破坏locality就好了。而这种近似，是必然存在的对现实的妥协，也是工业界必不可少的生存智慧。
改进型的时钟置换算法
需要扫描4轮的只有一种情况， 都是(1, 1)
小结
页面分配策略
驻留集
指请求分页存储管理中给进程分配的物理块的集合。 在采用了虚拟存储工作的系统中，驻留集大小一般小于进程的总大小。
若驻留集太小，会导致缺页频繁，系统要花大量的时间来处理缺页，实际用于进程推进的时间很少；
驻留集太大，又会导致多道程序并发度下降，资源利用率降低。所以应该选择一个合适的驻留集大小。
页面分配、置换策略
固定分配：操作系统为每个进程分配一组固定数目的物理块，在进程运行期间不再改变。即，驻留集大小不变
可变分配：先为每个进程分配一定数目的物理块，在进程运行期间，可根据情况做适当的增加或减少。 即，驻留集大小可变
局部置换：发生缺页时只能选进程自己的物理块进行置换。
全局置换：可以将操作系统保留的空闲物理块分配给缺页进程，也可以将别的进程持有的物理块置换到外存，再分配给缺页进程。
| 局部置换 | 全局置换 | |
|---|---|---|
| 固定分配 | √ | - |
| 可变分配 | √ | √ |
全局置换意味着一个进程拥有的物理块数量必然会改变，因此不可能是固定分配
固定分配局部置换
可变分配全局置换
系统会锁定一些页面，这些页面中的内容不能置换出外存（如：重要的内核数据可以设为“锁定”)
可变分配局部置换
调入页面的时机
从何处调页
抖动(颠簸)现象
工作集
小结
