抖动与工作集
目录
参考资料：
1 多道程序度与“抖动”
1.1 多道程序度与处理机的利用率
由于虚拟存储器系统能从逻辑上扩大内存，这时，只需装入一个进程的部分程序和数据便可开始运行，故人们希望在系统中能运行更多的进程，即增加多道程序度，以提高处理机的利用率。但处理机的实际利用率却下图中的实线所示。
缺页率 -> 抖动
其中横轴表示多道程序的数量，纵轴表示相应的处理机的利用率。在横轴的开始部分，随着进程数目的增加，处理机的利用率急剧增加；但到达 N1 时，其增速就明显地减慢了，当到达 N(max) 时，处理机的利用率达到最大，以后先开始缓慢下降，当到达 N2 点时，若再继续增加进程数，利用率将加速下降而趋于 0，见图中的 N3 点，之所以会发生在后面阶段利用率趋于 0 的情况是因为在系统中已发生了 “抖动”。
抖动会使处理机的利用率显著下降
1.2 产生“抖动”的原因
发生“抖动”的根本原因是，同时在系统中运行的进程太多，由此分配给每一个进程的物理块太少，不能满足进程正常运行的基本要求，致使每个进程在运行时，频繁地出现缺页，必须请求系统将所缺之页调入内存。这会使得在系统中排队等待页面调进/调出的进程数目增加。显然，对磁盘的有效访问时间也随之急剧增加，造成每个进程的大部分时间都用于页面的换进/换出，而几乎不能再去做任何有效的工作，从而导致发生处理机的利用率急剧下降并趋于 0 的情况。我们称此时的进程是处于抖动状态。
2 工作集
2.1 工作集的基本概念
进程发生缺页率的时间间隔与进程所获得的物理块数有关。下图展示了缺页率与物理块数之间的关系。
从图中可以看出，缺页率随着所分配物理块数的增加明显地减少，当物理块数超过某个数目时，再为进程增加一物理块，对缺页率的改善已不明显。可见，此时已无必要再为它分配更多的物理块。反之，当为某进程所分配的物理块数低于某个数目时，每减少一块，对缺页率的影响都变得十分明显，此时又应为该进程分配更多的物理块。
缺页率和物理块有关系
基于程序运行时的局部性原理得知，程序在运行期间，对页面的访问是不均匀的，在一段时间内仅局限于较少的页面，在另一段时间内，又可能仅局限于对另一些较少的页面进行访问。这些页面被称为活跃页面。如果能够预知程序在某段时间间隔内要访问哪些页面，并将它们调入内存，将会大大降低缺页率，从而可显著地提高处理机的利用率。
工作集理论出现的背景
2.2 工作集的定义
所谓工作集，是指在某段时间间隔里，进程实际所要访问页面的集合。
虽然程序只需要少量的几页在内存便可运行，但为了较少地产生缺页，应将程序的全部工作集装入内存中。然而我们无法事先预知程序在不同时刻将访问哪些页面，故仍只有像置换算法那样，用程序的过去某段时间内的行为作为程序在将来某段时间内行为的近似。
工作集只是一个对过去行为预估的页面集合，并不一定能准确的反应将来的情况
3 “抖动”的预防
为了保证系统具有较大的吞吐量，必须防止“抖动”的发生。
少抖动 -> 高吞吐量
3.1 局部置换策略
在页面分配和置换策略中，如果采取的是可变分配方式，则为了预防发生“抖动”可采取局部置换策略。根据这种策略，当某进程发生缺页时，只能在分配给自己的内存空间内进行置换，不允许从其它进程去获得新的物理块。这样，即使该进程发生了“抖动”也不会对其它进程产生影响，于是可把该进程“抖动”所造成的影响限制在较小的范围内。
把抖动限制在单个进程内
该方法虽然简单易行，但效果不是很好，因为在某进程发生“抖动”后，它还会长期处在磁盘 I/O 的等待队列中，使队列的长度增加，这会延长其它进程缺页中断的处理时间，也就是延长了其它进程对磁盘的访问时间。
实际效果不好，还是会影响整体性能
3.2 把工作集算法融入到处理机调度中
当调度程序发现处理机利用率低下时，它将试图从外存调入一个新作业进入内存，来改善处理机的利用率。如果在调度中融入了工作集算法，则在调度程序从外存调入作业之前，必须先检查每个进程在内存的驻留页面是否足够多。如果都已足够多，此时便可以从外存调入新的作业，不会因新作业的调入而导致缺页率的增加；反之，如果有些进程的内存页面不足，则应首先为那些缺页率居高的作业增加新的物理块，此时将不再调入新的作业。
3.3 利用“L=S”准则调节缺页率
“L=S”的准则：其中 L 是缺页之间的平均时间，S 是平均缺页服务时间，即用于置换一个页面所需的时间。如果是 L 远比 S 大，说明很少发生缺页，磁盘的能力尚未得到充分的利用；反之，如果是 L 比 S 小，则说明频繁发生缺页，缺页的速度已超过磁盘的处理能力。只有当 L 与 S 接近时，磁盘和处理机都可达到它们的最大利用率。理论和实践都已证明，利用“L=S”准则，对于调节缺页率是十分有效的。
3.4 选择暂停的进程
当多道程序度偏高时，已影响到处理机的利用率，为了防止发生“抖动”，系统必须减少多道程序的数目。此时应基于某种原则选择暂停某些当前活动的进程，将它们调出到磁盘上，以便把腾出的内存空间分配给缺页率发生偏高的进程。系统通常都是采取与调度程序一致的策略，即首先选择暂停优先级最低的进程，若需要，再选择优先级较低的进程。当内存还显拥挤时，还可进一步选择暂停一个并不十分重要、但却较大的进程，以便能释放出较多的物理块，或者暂停剩余执行时间最多的进程等。
减少进程数
//一个系统的进程数是有限的，不可能无限量的增加，进程间切换会增加系统开销，进程数量过多也会造成系统抖动，但是抖动应该由系统层去解决