324_页面分配策略
# 3.2_4_页面分配策略
在这个小节中我们会学习页面分配策略相关的一系列知识点，首先我们会学习什么是驻留集，之后我们会学习考试中需要掌握的三种页面分配置换的策略。
另外页面应该在什么时候被调入，应该从什么地方调入，应该调出到什么位置？这些也是我们之后会探讨的问题，最后我们又会学习什么是进程抖动或者叫进程颠簸这种现象。
为了解决进程抖动，又引入了工作集这个概念，我们会按照从上至下的顺序依次讲解。
# 驻留集
首先来看一下什么是驻留集，所谓的驻留集其实很简单，就是指请求分页存储管理当中给进程分配的物理块的集合，或者说内存块页框的集合，在采用了虚拟存储技术的系统当中，为了从逻辑上提提高内存的利用率，驻留级的大小一般是要小于进程的总大小的。
接下来我们来考虑一个比较极端的问题，如果一个进程总共有 100 个页面，进程的驻留集大小，如果是也和页面的数量相同，也就是大小为 100 的话，也就意味着进程所有的数据在刚开始就可以被全部放入内存，并且运行期间就不会再发生任何一次缺页。
但如果驻留集太小的话，比如说驻留级大小为 1，进程它可能会使用到 100 个页面，所以如果说进程只有一个物理块可以使用，那么进程在运行的期间肯定会产生大量的频繁的缺页。
所以从极端的例子当中，我们可以看到，如果说驻留集选择的太小的话，就会导致进程缺乏频繁，系统就需要花很大的时间来处理缺页，而实际用于进程运行的时间又很少。但是如果驻留集太大的话，又会导致多道程序的并发度下降，使系统的某些资源利用率不高
为什么资源利用率会降低，可以这么考虑，比如说像系统当中的 CPU，还有 IO 设备，这两种资源理论上是可以并行的工作的，如果说多道程序并发度下降，就意味着 CPU 和 IO 设备这两种资源并行工作的这种几率就会小很多，所以资源的利用率当然就会有所降低。
所以系统应该为进程选择一个合适的驻留集大小，针对于驻留集的大小是否可变这个问题，人们提出了固定分配和可变分配这两种分配策略。
固定分配就是系统在刚开始的时候就给进程分配一组固定数目的物理块，并且在运行期间不再改变。也就是驻留集的大小是刚开始就确定了之后就不再改变了。
可变分配刚开始会给它进程分配一定数目的物理块，但是在运行期间可以根据情况适当的增加或者减少，所以可变分配其实指的就是驻留级的大小是可以动态的改变可以调整的。
另外当页面置换的时候，置换的范围应该是什么？根据这个问题，人们又提出了局部置换和全局置换，这两种置换范围的策略。
局部置换就是指当发生缺页的时候，只能选择进程自己的物理块进行置换，而如果采用的是全局置换的话，当发生缺页的时候，操作系统会把自己保留的空闲物理块分配给这个缺页的进程，当然也可以将别的进程所持有的物理块给置换到外存去，然后再把物理块分配给现在缺页的进程。所以局部置换和全局置换的区别就在于当某个进程发生缺页，并且需要置换出某个页面的时候，置换处的页面是不是只能是自己的，
把这两种分配和置换的策略两两结合，可以得到这样的三种分配和置换的策略，分别是固定分配局部置换、可变分配局部置换和可变分配全局置换，但是大家会发现其实并不存在固定分配、全局置换这种策略，因为从全局置换的规则，我们也可以知道，如果使用的是全局置换的话，就意味着一个进程所拥有的物理快是必然会改变的，而固定分配又规定着进程的驻留集大小不变，也就是这进程所拥有的物理快速是不能改变的，所以固定分配全局置换这种分配置换策略是不存在的。
# 三种分配和置换的策略
接下来我们依次介绍存在的这三种分配和置换的策略。
固定分配局部置换是指系统会为各个进程分配一定数量的物理快，并且在整个运行期间，这些物理块数都不再改变。如果说进程在运行的过程中发生了缺页的话，那么就只能从进程在内存当中的某个页面当中选出一页进行换出，然后再调入需要的页面。
所以这种策略也有一个很明显的缺点，就是很难在刚开始的时候就确定应该为每个进程分配多少个物理块才算合适。不过在实际应用中，一般如果说采用这种策略的系统，它会根据进程大小，进程优先级或者是程序员提出的一些参数来确定到底要给每个进程分配多少个物理块，不过这个数量一般来说是不太合理的，因为驻留集的大小不可变，所以固定分配局部置换这种策略的灵活性相对来说是比较低的。
第二种叫做可变分配全局置换，因为是可变分配，所以说系统刚开始会为进程分配一定数量的物理快，但是之后在进程运行期间，物理块的数量是可以改变的，那操作系统会保持一个空闲物理块的队列，如果说一个进程发生缺页的时候，就会从空闲物理快当中取出一个分配给进程。如果说此时空闲物理块都已经用完了，那就可以选择一个系统当中未锁定的页面，外出外存，再把物理块分配给缺页的进程。
这个地方所谓的未锁定的页面指的是什么？其实系统会锁定一些很重要的就是不允许被换出外存需要常驻内存的页面，比如说系统当中的某些很重要的内核数据就有可能是被锁定的。另外一些可以被置换出外存的页面，就是所谓的未锁定的页面，当然这个地方只是做一个拓展，在考试当中应该不会考察。
通过刚才对这个策略的描述，大家也会发现在这种策略当中，只要进程发生缺页的话，它必定会获得一个新的物理块。如果说空闲物理块没有用完，新的物理块就是从空闲物理块队列当中选择一个给它分配，如果说空闲物理快用完了，系统才会选择一个未锁定的页面换出外存，但是未锁定的页面有可能是任何一个进程的页面，所以进程的页面被换出的话，那么它所拥有的物理块就会减少，它的缺页率就会有所增加。那显然只要进程发生了缺页，就给它分配一个新的物理块，这种方式其实也是不太合理的，
所以之后人们又提出了可变分配局部置换的策略，在刚开始会给进程分配一定数量的物理块，因为是可变分配，所以之后物理块的数量也是会改变的。由于是局部置换，所以当进程发生缺页的时候，只允许进程从自己的物理块当中选出一个进行换出。如果说操作系统在进程运行的过程中发现它频繁的缺页，那就会给进程多分配几个物理块，直到进程的确页率会到一个适当的程度。相反的如果一个进程在运行当中确页率特别低的话，那么系统会适当的减少给进程所分配的物理快，这样的话就可以让系统的多道程序并发度也保持在一个相对理想的位置。
这三种策略当中最难分辨的是可变分配全局置换，和可变分配局部置换，大家需要抓住他们俩最大的一个区别。如果采用的是全局置换策略的话，那么只要缺页就会给进程分配新的物理块。
但是如果说采用的是这种局部置换的策略的话，系统会根据缺页的频率来动态的增加或者减少一个进程所拥有的物理块，这是三种我们需要掌握的页面分配策略，有可能在选择题当中进行考察。
# 何时调入页面
接下来我们再来讨论下一个问题，我们应该在什么时候调入所需要的页面？一般来说有这样的两种策略，第一种叫做预调页策略，根据我们之前学习的局部性原理，特别是空间局部性的原理，我们知道如果说当前访问了某一个内存单元的话，那么很有可能在之后不久的将来，会接着访问与内存单元相邻的那些内存单元。
所以根据这个思想，我们自然而然的也会想到，如果说我们访问了某一个页面的话，那么是不是在不久的之后就也有可能会访问与它相邻的那些页面呢？因此基于这个方面的考虑，如果我们能够依次调入若干个相邻的页面，那么可能会比一次调入一个页面会更加高效。因为我们一次调入一堆页面的话，那么我们启动磁盘 l 的次数肯定就会少很多，这样的话就可以提升掉页的效率。
不过另一个方面，如果说我们提前调入的这些页面，在之后没有被访问过的话，那么预调又是一种很低效的行为，所以我们可以用某种方法预测，不久之后可能会访问到的页面，将这些页面预先的调入内存，但是目前预测的成功率不高，只有 50% 左右。
所以在实际应用当中，预调页策略主要是用于进程首次调入的时候，由程序员指出哪些部分应该是先调入内存的，比如说我可以告诉系统把 main 函数相关的那些部分先调入内存，所以预调页策略是在进程运行前就进行调入的一种策略。
第二种就是请求调页策略，这也是咱们之前一直在学习的请求调页方式。只有在进程运行期间发现缺页的时候，才会把所缺的页面调入内存，所以这种策略其实在进程运行期间才进行页面的调入，并且被调入的页面肯定在之后是会被访问到的。但是由于每次只能调入一个页面，所以每次调页都需要启动磁盘 IO 操作，因此 IO 开销是比较大的。在实际应用当中，预调页策略和请求调页策略都会结合着来使用，预调页用于进程运行前的调入，而请求调页策略是在进程运行期间使用的，这是调入页面的时机问题。
# 从何处调入页面
接下来我们再来看一下我们应该从什么地方调入页面。之前我们有简单的介绍过，磁盘当中的存储区域分为兑换区和文件区这样两两个部分，其中对换区采用的是连续分配的方式，读写的速度更快，而文件区的读写速度是更慢的，它采用的是离散分配的方式，什么是离散分配，什么是连续分配，这个是咱们在之后的章节会学习的内容，这个地方先不用管，有个印象就可以。在本章中大家只需要知道对换区的读写速度更快，而文件区的读写速度更慢就可以了，
一般来说文件区的大小要比对换区要更大，平时我们的程序在没有运行的时候，相关的数据都是存放在文件区的，由于对换区的读写速度更快，所以如果说系统拥有足够的对换区空间的话，那么页面的调入调出都是内存与对换区之间进行的，
所以系统中如果有足够的对换区空间，刚开始在运行之前会把我们的进程相关的那一系列数据，从文件区先复制到对换区之后，把这些需要的页面从对换区调入内存。相应的如果内存空间不够的话，可以把内存中的某些页面调出到对换区当中，页面的调入调出都是内存和对换区更高速的区域进行的，这是在对换区大小足够的情况下使用的一种方案。
如果说系统中缺少足够的对换区空间的话，凡是不会被修改的数据，都会从文件区直接调入内存，由于这些数据是不会被修改的，所以当调出这些数据的时候并不需要重新写回磁盘，如果说某些页面被修改过的话，把它调出的时候就需要写回到对换区，而不是写回到文件区，因为文件区的读写速度更慢，相应的如果之后还需要再使用到这些被修改的页面的话，那就是从对换区再换入内存。
第三种 UNIX 使用的是这样的一种方式，如果说一个页面还没有被使用过，也就是这个页面第一次被使用的话，那么它是从文件区直接调入内存，但是之后如果内存空间不够，需要把某些页面换出外存的话，那么是换出到对换区当中，如果这个页面需要再次被使用的话，要从对换区再换回内存，这是 UNIX 系统采用的一种方式。
# 抖动
接下来我们再来介绍一个很常考的概念，叫做抖动或者叫颠簸现象。所谓的抖动或者颠簸就是指刚刚换出的页面，马上又要换入内存，刚刚换入的页面马上又要换出外存，所以这种频繁的页面调度行为就是所谓的动或者叫颠簸。
产生这个现象的主要原因是在于进程频繁访问的页面数目要高于可用的物理块数，也就是说分配给进程的物理块是不够的。如果说发生了抖动现象的话，系统会用大量的时间来处理进程页面的换入换出，而实际用于进程执行的时间就变得很少。所以我们要尽量避免抖动现象的发生
为了防止抖动的发生，就需要为进程分配足够的物理快，但是如果说物理块分配的太多的话，又会降低系统整体的并发度，降低某些资源的利用率。所以为了研究应该为每个进程分配多少个物理块，有一个科学家在一九六几年提出了进程工作集的概念
# 工作集
所谓的工作集就是指进程在某段时间间隔内实际访问的页面的集合，注意它和驻留集其实是有区别的。驻留集是指在请求分页存储管理当中给进程分配的内存块的集合。
我们直接来看一个例子，一般来说操作系统会设置一个所谓的窗口尺寸来算出工作集，假设一个进程对页面的访问序列是这样的一个序列，如果此时访问到了这个页面，并且窗口尺寸为 4 的话，那么就会从此时访问的页面开始，往前寻找之前访问过的 4 个页号，由此来确定工作集的内容。所以在这个时刻进程的工作集应该是 24 15 18 23。
此时如果访问到的是 17 这个页面，同样的再往前看 4 个页号，会发现此时的工作集是 18 ，24 ，17 这样 3 个页面，所以从这个地方会发现，工作集的大小可能会小于窗口的尺寸，在实际应用当中窗口尺寸一般会设置的更大一些，比如说设置 10，50，100 这样的数字，对于一些局部性很好的进程来说，工作集的大小一般是要比窗口尺寸的大小要更小的，比如说窗口尺寸为 5，但是经过一段时间的监测，发现某个进程的工作集最大只会为三，那么就说明进程是拥有很好的局部性的，系统可以给进程分配三个或者三个以上的内存块，就可以满足进程的运行需要了。
所以系统可以根据监测工作集的大小来决定到底要给进程分配多少个内存块。换一个说法就是根据工作集的大小来确定驻留集的大小到底是多少。
一般来说驻留集的大小不能小于工作集的大小，如果说更小的话，那就有可能会对发生频繁的缺页，也就是发生抖动现象。
另外在有的系统当中也会根据工作集的概念来设计一种页面置换算法，比如说如果说进程需要置换出某个页面的话，完全就可以选择一个不在工作集当中的页面进行淘汰，这些知识点只是作为一个拓展，大家只要有个印象就可以了。
# 小结
那么这个小节我们介绍了页面分配策略相关的一系列知识点，需要特别注意驻留集这个概念。在之前咱们讲过的那些内容当中，经常会遇到某些题目，告诉我们一个条件就是说系统为某个进程分配了 n 个物理块，这种说法其实也可以改变一种等价的表述方式，也可以说成是某个进程的驻留集大小是 n。如果说题目中的条件是用驻留集大小这种方式给出的话，大家也需要知道它所表述的到底是什么意思。
另外大家需要注意，这三种分配置换策略在真题当中是进行考察过的，并且在有的大题当中有可能会告诉大家，一个进程采用固定分配局部置换的策略，这个条件就是为了告诉大家系统为一个进程分配的物理块数是不会改变的。大家在做课后习题的时候可以注意一下，很多大题都会给出这样的一个条件，我们需要知道这个条件背后隐含的一系列的信息
这个地方还需要注意，并不存在固定分配全局置换这种策略，因为全局置换意味着一个进程所拥有的物理块数肯定是会改变的，而固定分配又要求一个进程拥有的物理块数是不能改变的。所以固定分配和全局置换这两个条件本身就是相互矛盾的，因此并不存在固定分配全局置换这种方式
之后介绍的内容何时调入页面，应该从何处调入页面，这些能有个印象就可以了。
最后大家还需要重点关注抖动，颠簸这个现象，产生抖动的主要原因是分配给进程的物理块不够，所以如果要解决抖动问题的话，那么肯定用某种方法给进程分配更多的物理块，这一点在咱们的课后习题当中也会遇到，我们还对工作集的概念做了一系列的拓展，不过一般来说工作集这个概念不太容易进行考察，但是大家需要注意的是，驻留集的大小一般来说不能小于工作集的大小，如果更小的话，那就会产生抖动现象。
这个小节的内容一般来说只会在选择题当中进行考察，但是在考试当中也有可能用某些概念作为大题当中的一个条件进行给出，所以大家还需要通过课后习题进行进一步的巩固。
