操作系统内存最全解析！！！(14) _操作系统

LRU 与老化之前的第 2 个区别是，在老化期间，计数器具有有限数量的位（这个例子中是 8 位），这就限制了以往的访问记录。如果两个页面的计数器都是 0 ，那么我们可以随便选择一个进行置换。实际上，有可能其中一个页面的访问次数实在 9 个时钟周期以前，而另外一个页面是在 1000 个时钟周期之前，但是我们却无法看到这些。在实际过程中，如果时钟周期是 20 ms，8 位一般是够用的。所以我们经常拿 20 ms 来举例。
工作集页面置换算法在最单纯的分页系统中，刚启动进程时，在内存中并没有页面。此时如果 CPU 尝试匹配第一条指令，就会得到一个缺页异常，使操作系统装入含有第一条指令的页面。其他的错误比如全局变量和堆栈引起的缺页异常通常会紧接着发生。一段时间以后，进程需要的大部分页面都在内存中了，此时进程开始在较少的缺页异常环境中运行。这个策略称为请求调页(demand paging)，因为页面是根据需要被调入的，而不是预先调入的。
在一个大的地址空间中系统的读所有的页面，将会造成很多缺页异常，因此会导致没有足够的内存来容纳这些页面。不过幸运的是，大部分进程不是这样工作的，它们都会以局部性方式(locality of reference) 来访问，这意味着在执行的任何阶段，程序只引用其中的一小部分。
一个进程当前正在使用的页面的集合称为它的工作集(working set)，如果整个工作集都在内存中，那么进程在运行到下一运行阶段（例如，编译器的下一遍扫面）之前，不会产生很多缺页中断。如果内存太小从而无法容纳整个工作集，那么进程的运行过程中会产生大量的缺页中断，会导致运行速度也会变得缓慢。因为通常只需要几纳秒就能执行一条指令，而通常需要十毫秒才能从磁盘上读入一个页面。如果一个程序每 10 ms 只能执行一到两条指令，那么它将需要很长时间才能运行完。如果只是执行几条指令就会产生中断，那么就称作这个程序产生了颠簸(thrashing) 。
在多道程序的系统中，通常会把进程移到磁盘上（即从内存中移走所有的页面），这样可以让其他进程有机会占用 CPU。有一个问题是，当进程想要再次把之前调回磁盘的页面调回内存怎么办？从技术的角度上来讲，并不需要做什么，此进程会一直产生缺页中断直到它的工作集被调回内存。然后，每次装入一个进程需要 20、100 甚至 1000 次缺页中断，速度显然太慢了，并且由于 CPU 需要几毫秒时间处理一个缺页中断，因此由相当多的 CPU 时间也被浪费了。
因此，不少分页系统中都会设法跟踪进程的工作集，确保这些工作集在进程运行时被调入内存。这个方法叫做工作集模式(working set model) 。它被设计用来减少缺页中断的次数的。在进程运行前首先装入工作集页面的这一个过程被称为预先调页(prepaging)，工作集是随着时间来变化的。
根据研究表明，大多数程序并不是均匀的访问地址空间的，而访问往往是集中于一小部分页面。一次内存访问可能会取出一条指令，也可能会取出数据，或者是存储数据。在任一时刻 t，都存在一个集合，它包含所哟欧最近 k 次内存访问所访问过的页面。这个集合 w(k,t) 就是工作集。因为最近 k = 1次访问肯定会访问最近 k > 1 次访问所访问过的页面，所以 w(k,t) 是 k 的单调递减函数。随着 k 的增大，w(k,t) 是不会无限变大的，因为程序不可能访问比所能容纳页面数量上限还多的页面。

文章插图

事实上大多数应用程序只会任意访问一小部分页面集合，但是这个集合会随着时间而缓慢变化，所以为什么一开始曲线会快速上升而 k 较大时上升缓慢。为了实现工作集模型，操作系统必须跟踪哪些页面在工作集中。一个进程从它开始执行到当前所实际使用的 CPU 时间总数通常称作当前实际运行时间。进程的工作集可以被称为在过去的 t 秒实际运行时间中它所访问过的页面集合。
下面来简单描述一下工作集的页面置换算法，基本思路就是找出一个不在工作集中的页面并淘汰它。下面是一部分机器页表