[OS复习]虚拟存储管理技术2

1.虚拟存储系统的软件策略

现代操作系统几乎都采用虚拟存储管理系统。一些特殊的操作系统和一些较老的操作系统没有采用虚拟存储技术。例如，MS DOS和早期的UNIX操作系统等。大多采用分段与分页相结合的段页式管理系统。下面以分页存储管理为例，介绍虚拟存储系统采用的软件策略。主要从以下几个方面进行分析：
驻留集管理(Resident Set Management)
放置策略(Placement Policy)
获取策略(Fetch Policy)
置换策略(Replacement Policy)
清除策略(Cleaning Policy)
负载控制(Load Control)

2.驻留集的管理

进程的驻留集指：虚拟存储系统中，每个进程驻留在内存的页面集合，或进程分到的物理页框集合。驻留集管理主要解决的问题是，系统应当为每个活跃进程分配多少个页框。

2.1影响页框分配的主要因素

分配给每个活跃进程的页框数越少，同时驻留内存的活跃进程数就越多，进程调度程序能调度就绪进程的概率就越大。然而，这将导致进程发生缺页中断的概率较大；为进程分配过多的页框，并不能显著地降低其缺页中断率。

2.2基本的驻留集管理策略 

固定分配策略：
为每个进程分配固定数量的页框。即每个活跃进程的驻留集尺寸在运行期间固定不变。为进程分配多少个页框是合理的呢以由系统根据进程的类型确定，也可以由编程人员或系统管理员指定。
可变分配策略：
为每个活跃进程分配的页框数在进程的生命周期内是可变的。即系统可以首先给进程分配一定数量的页框。进程运行期间，可以增加或减少页框。系统可以根据进程的缺页率调整进程的驻留集。当进程的缺页率很高时，驻留集太小，需要增加页框；当缺页率一段时间内都保持很低时，可以在不会明显增加进程缺页率的前提下，回收其一部分页框，减小进程的驻留集。
两种策略的评价： 可变分配策略比固定分配策略更灵活，既可以提高系统的吞吐量，又能保证内存的有效利用。可变分配要求统计进程的缺页率，增加系统额外开销。而准确判断进程缺页率的高低，确定缺页率的阈值是非常困难的。可变分配策略不仅需要操作系统软件专门的支持，而且，还需要处理机平台提供的硬件支持。

2.3页面放置策略

解决的问题：系统应当在内存的什么位置为活跃进程分配页框span style=”color:#6633ff”>一般地，对于一个分页系统或段页式系统，将进程的一个页面装入哪一个页框无关紧要。对于分段系统，需要考虑将一个程序段装入哪一个合适的分区中，可采用的分配算法包括首次适应法、下次适应法、最佳适应法或最差适应法等。

2.4页面获取策略

解决的问题：系统应当在何时把一个页面装入内存br> 请求调页：
仅当进程执行过程中，通过检查页表发现相应页面不在内存时，才装入该页面。当进程刚开始执行时，由于预先未装入进程的页面，故需要频繁地申请装入页面。执行一段时间以后，进程的缺页率将下降。采用请求调页方式，一次装入请求的一个页面，磁盘I/O的启动频率较高，系统的开销较大。
预调页方式：
当进程创建时，预先为进程装入多个页面。缺页中断时，系统为进程装入指定的页面以及与之相临的多个页面。若局部性很差，预先装入的很多页面不会很快被引用，并会占用大量的内存空间，反而降低系统的效率。

2.5页面置换策略 

当发生缺页中断且无足够的内存空间时，需要置换已有的某些（个）页面。应该解决的基本问题：1.当系统欲把一个页面装入内存时，应当在什么范围内判断已经没有空闲页框供分配.当指定的范围内没有空闲页框时，应当从指定的范围内选择哪个页面移出内存以采用局部置换或全局置换策略。 局部置换： 系统在进程自身的驻留集中判断当前是否存在空闲页框，并在其中进行置换。
全局置换策略：
在整个内存空间内判断有无空闲页框，并允许从其它进程的驻留集中选择一个页面换出内存。

2.6分配模式与置换模式对比

固定分配策略-> 局部置换策略 
全局置换策略 -> 可变分配策略
可变分配策略+局部置换策略:即可增加或减少分配给每个活跃进程的页框数；当进程的页框全部用完，而需要装入一个新的页面时，系统将在该进程的当前驻留集中选择一个页面换出内存。  

3.页面置换算法

页面置换算法是指在指定的置换范围内，决定将哪一个页面换出内存。置换算法的好坏将直接影响系统的性能，不适当的置换算法可能导致系统出现“抖动”现象。常用的页面置换算法：最佳置换算法、最近最少使用算法、先进先出算法和时钟算法等

3.1最佳置换算法 (Optimal Algorithm，OPT) 

基本思想：被置换的页面是将来不再访问，或在最远的将来才被访问的页面。若采用固定分配策略，最佳置换算法可以保证系统的缺页率最低。但是，无法预知一个进程在内存的若干页面中，哪一个页面是将来不再访问的，甚至最长时间内将不再被访问的，因而该算法是无法实现的。该算法可以用于评价其它置换算法的性能。
示例：
假设系统分配给某进程3个页框，且进程开始运行时，这3个页框是空的。考虑下列页面 引用序列：2、3、2、1、5、2、4、5、3、2、5、2

3.3先进先出置换算法 (First-in First-out Algorithm，FIFO)

5.1如何判断系统的负载 

L=S准则
通过调整多道程序的度，使发生两次缺页之间的平均时间等于处理一次缺页所需要的平均时间。即，平均地，一次缺页处理完毕，再发生下一次缺页。此时，处理机的利用率将达到最大。
50%准则  当分页设备的利用率保持在50%左右时，处理机的利用率将达到最大。
如果系统使用基于CLOCK置换算法的全局置换策略，那么，可以通过监视扫描指针的移动速率来调整系统负载。如果扫描指针的移动速率低于某个给定的阀值，那么意味着近期页面失败的次数较少或者近期没有被引用的页面数较多；此时，系统可以放心地增加驻留内存的活动进程数。如果扫描指针的移动速率超出某个给定的阀值，那么意味着近期页面失败的次数较多或者近期没有被引用的页面数较少；此时，系统应当减少驻留内存的活动进程数。

5.2可以挂起的进程

优先级最低的进程；
缺页进程：因为发生缺页中断的进程处于阻塞状态，暂时不需要竞争处理机的使用权。而且，挂起一个缺页进程时，挂起和激活操作需要的数据交换将消除页替换的开销；
最后一个被激活的进程 ：因为为此类进程装入的页面较少。将其挂起的开销较小；
驻留集最小的进程：将该类进程挂起以后，激活所需的开销较小；
最大的进程：挂起最大的进程将获得最多的内存空间，可以满足内存中的进程申请空闲页框的需要，使它们能尽快执行完成；
剩余执行时间最多的进程：对应于剩余时间最短者优先的进程调度算法，将剩余执行时间最多的进程挂起对其响应时间的影响不明显。