操作系统之页面分配策略（驻留集、工作集、置换策略、抖动）

来源：https://www.bilibili.com/video/BV1YE411D7nH

驻留集

概念：请求分页存储管理中给进程分配的内存块的集合（由于采用了虚拟存储技术，驻留集的大小一般小于进程的大小）。若驻留集太小，会导致频繁缺页；太大，则会导致多道程序并发度降低，资源利用率下降。

要知道固定分配局部置换、可变分配全部置换、可变分配局部置换的意思，首先需要知道以下几个概念：

1、 固定分配：操作系统为每个进程分配一组固定数目大小的物理块。在程序运行过程中，不允许改变！即驻留集大小固定不变。

2、可变分配：先为每个进程分配一定大小的物理块，在程序运行过程中，可以动态改变物理块的大小。即，驻留集大小可变

3、局部置换：进程发生缺页时，只能选择当前进程中的物理块进行置换

4、全局置换：可以将操作系统进程中保留的空闲物理块分配给缺页进程，还可以将别的进程持有的物理块置换到外存，再将这个物理块分配给缺页的进程

固定分配局部置换

概念：系统为每个进程分配一定数量的内存块（物理块），在整个运行期都不改变。若进程在运行过程中发生了缺页，则只能在本进程的内存页面中选出一个进行换出，然后再调用需要的页面。

缺点：很难确定一个进程到底应该分配多大的实际内存才合理

可变分配全局置换

概念：系统为每个进程分配一定数量的内存块（物理块）。操作系统还会保持一个空闲物理块的队列。若某进程发生缺页，可以从空闲物理块中取出一块分配给该进程。如果空闲物理块没有了，那么会选择一个未锁定（不是那么重要）的页面换出到外存，再将物理块分配给缺页的进程。

缺点：在空闲物理块没有的情况下，如果将其他进程的页面调出到外存，那么这个进程就会拥有较小的驻留集，如此会导致该进程的缺页率上升

可变分配局部置换

概念：刚开始会为每个进程分配一定数量的物理块。当进程发生缺页时，只允许从当前进程的物理块中选出一个换出外存。如果当前进程在运行的时候频繁缺页，系统会为该进程动态增加一些物理块，直到该进程缺页率趋于适中程度；如果说一个进程在运行过程中缺页率很低或者不缺页，则可以适当减少该进程分配的物理块。通过这些操作可以保持多道程序的并发度较高。

可变分配全局置换和可变分配局部置换的区别

可变分配全局置换：只要发生缺页，就会分配新的物理块

可变分配局部置换：根据缺页率动态增加或者减少物理块的数量

页面调入的时机

1. 预调页策略：基于局部性原理，一次调入若干个相邻页面可能比一次调入一个页面更高效。

   缺点：如果调入的若干页面是不会被马上访问的，那么这样效率又会很低。

2. 请求调页策略：只有在进程处于运行期，且发生缺页的时候才被调入内存。

   缺点：缺页时每次只会调入一页，每次从外存到内存的调入都会进行I/O操作，因此I/O开销较大。

从何处调入页面

​ 外存（磁盘）一般分为对换区和文件区，对换区的读写速度较快，且采用连续分配方式；文件区读写速度较慢，采用离散分配方式。

​ 1、在系统拥有足够大的对换区空间时，页面的调入、调出都在内存和对换区中进行。注：在进程运行前，需要将进程相关的数据从文件区复制到对换区。

​ 2、当对换区空间不够大时：凡是不会在运行过程中不会被修改的数据就直接从文件区调入（不会被修改，那么到时候就不会再次被写入到磁盘）；对于可能会被修改的数据，交换时需要写回对换区，下次从对换区调入。

​ 3、UNIX系统采用的方式：进程有关的数据都存放在文件区。未使用过的页面都会从文件区调入。被使用的页面在进行置换时放到对换区，下次使用时从对换区调入。

页面抖动（颠簸现象）

概念：刚刚换出到外存的页面马上要换入内存，刚刚换入的页面马上要调入到外存。

产生原因：系统为进程分配的物理块大小不足

导致的问题：系统会花大量时间进行换入、换出操作，而真正用于进程实际运行的时间大大减少

为了解决抖动问题，提出了==工作集==的概念

工作集：在某段时间间隔内，进程实际访问页面的集合（区别于驻留集，驻留集是指请求分页管理存储中给进程分配的物理块大小）

操作系统会根据"窗口尺寸"来算出工作集。如：某进程的页面访问序列是：24，15，18，23，24，12，17，18，14，18，17，若窗口尺寸为3，那么对于18来说，其工作集就是24 15 18，对于12来说，其工作集就是23 24 12。

工作集的大小可能会小于窗口尺寸。比如对于15来说，其工作集大小为24 15。实际应用中，操作系统会统计某个进程的工作集大小，根据工作集大小为进程分配物理块。一般来说驻留集的大小不能小于工作集大小，否则会导致频繁缺页。