目录
- 全局页面置换算法
- 工作集和常驻集
- 工作集页置换算法
- 缺页率页面置换算法
- 抖动问题
正文
全局页面置换算法
工作集和常驻集
局部页面置换算法都针对一个程序/进程来进行操作的，然而OS可以同时执行多个程序，如果每一个程序都采取一个固定的局部页面置换算法会带来一些问题，所以我们引入全局页面置换算法。
程序的访问特征是可变的，可能一开始需要的内存比较多，中间可能需要的很少，结束时又很多，也就说对物理内存的需求是可变的。而前面的局部页面置换算法都有一个大前提：分配的物理页帧是固定的。
由于OS可以同时跑多个程序，那么这时候如果给每一个程序分配一个固定的物理页帧，就限制了程序的灵活性。我们想要根据程序进行的不同阶段，动态分配给其不同的物理内存大小。这就是我们全局页面置换算法要考虑到的。
接下来要介绍的所有算法，都基于一个大前提。
如果一个算法要有效，那么我们需要这个程序具有局部性。程序局部性原理越好，LRU/clock算法就会产生更少的缺页次数。所以我们想要表现和分析局部性——工作集
起始时间是t1,△是从过去到现在一固定长度。表示了程序在不同运行阶段对内存访问特点的展现，t2的工作集的局部性就很好，t1相对于t2的局部性稍差，但是仍然具有一定的局部性。
下图便于理解：
工作集在执行过程中会随着程序执行的特点而变化。可能一开始访问的页不具有局部性，但是到访问到一定区域他的工作集大小也会比较稳定。
常驻是常驻内存的意思，常驻集是当前时刻正在运行的程序驻留在内存中的页面集合。如果说工作集体现了运行中程序在运行过程中在对页面访问的属性，是程序本身的固有属性；常驻集是OS和计算机系统给应用程序分配的物理页-空间的大小，以及采取的页面置换算法来决定到底将哪些页面放入内存。工作集表示要访问的页面有哪些，这些页面有可能不在内存中，这是和常驻集的最大不同。我们希望工作集的页都在常驻集里，一旦工作集中某些页不在常驻集，就会产生缺页中断，所以我们希望这两个集合尽量是重叠的，这样会使得缺页率较小。OS在程序运行时可以分配的常驻集大小是不定的，分配的物理页不是越多越好，可能当物理页多到一定程度时，意义不大了，此时我们想将多余的页分配给其他程序，动态调整物理页大小使得整体的缺页率较低。只要整体缺页次数少，则整体系统性能就会高。
工作集页置换算法
工作集窗口里的页代表当前这段时间内被访问的页，如果其中的页需要替换时，需要替换不在工作集中的页；随着程序执行，窗口在挪动，评议过程中某个页不再在国工作集窗口内，则这个页也需要丢掉，并不是一定要等到缺页时再置换出去。
看一个例子：【个人感觉用链表理解更加容易】
工作集窗口τ=4
| 阶段 | 工作集窗口内容 |
| 0 |
|
| 1 |
|
| 2 |  |
| 3 |
|
4 |
|
5 |
|
6 |
|
7 |
|
8 |
|
9 |
|
10 |
|
它和前面的局部页面替换算法相比，最大的变化是取决于工作集窗口。所以超出窗口的老页被换出，保证物理内存中始终有足够多的页存在，给其他运行的程序提供更多的内存，从而减少页面置换次数。从整个系统的层面上减少缺页率。
缺页率页面置换算法
若运行程序缺页率高我们会增加工作集，希望他访问的页尽量在内存中，可以降低缺页率。如果缺页率过低，意味着可能分配的内存比较多，则可以减少工作集来减少程序需要的物理页面（意味着常驻集也被减少），使得每个程序的缺页率保持在一个合理的范围内。整体系统的性能从而平衡地提高。
T是一个阈值，如果缺页与上次缺页之间的时间间隔是大的，则说明缺页率低，应该减少工作集空间。如果缺页与上次缺页之间的时间间隔是小的，说明缺页率高，应该增加工作集空间。
例子：设阈值T=2。工作集窗口τ=4
与工作集页置换算法的必须在分配的物理空间满时才替换出去相比，该算法即便空间不满在满足一定条件是也会清理一部分空间。从而整体来说使得一些经常访问的页驻留在内存中，对于OS而言，要应对多个正在运行的程序，那么采取全剧页替换算法要优于局部页替换算法。
抖动问题
简单来说，如果常驻集包含于工作集，也就意味着在访问内存时，需要频繁进行页面置换，从而增大开销与运行速度。我们需要一个合适的常驻集，尽量使二者一致，这样产生的缺页就会很少且并发程序可以更多。
x轴：有多少程序在跑
y轴：CPU利用率
一般情况下CPU利用率是比较高的，但是如果在某段时间内进行大量页面换入换出，使得程序进程变慢，CPU利用率大量降低。
分析图标，随着同时执行的程序增多，内存很快就用完了，然后会产生大量缺页，OS需要大量的换入换出操作或者中断处理操作。因为频繁执行IO操作，这时候所有的CPU时间都去用来做置换页面的操作，程序利用率大大降低，机器越来越慢。
因此我们希望能将其维持在峰值，找到一个平衡点。我们希望两个缺页产生的平均时间MTBF和完成一次缺页的中断服务的时间PFST尽量相等，二者比值越大意味着缺页频度低，此时CPU大部分时间用于跑程序。随着后来程序增多，缺页次数越来越多。在NIO-balance点，并发执行的程序个数比较多且系统整体利用率比较高。OS可以根据当前CPU利用率来动态调整应该让系统里放多少程序，只要个数合适，就可以领内存抖动现象得到改善。即便只有一个程序运行，如果占据内存足够多，那么也有可能产生抖动现象。
我们希望通过OS管理，整个系统利用率高且跑的程序尽量多。
