虚拟内存管理

虚拟内存管理

页面置换算法

• 功能和目标：
  • 功能：当缺页中断发生，需要调入新的页面而内存已经满时，选择内存当中哪个物理页面被置换。
  • 目标：尽可能的减少页面的换进换出次数（即缺页中断的次数）。具体来说，把未来不再使用或者短期内较少使用的页面换出，通常只能在局部性原理指导下依据过去的统计数据来进行预测
  • 页面锁定：用于描述必须常驻内存的操作系统的关键部分或时间关键的应用进程。实现方法是在页表中添加锁定标志位。

最优页面置换算法

• 基本思路：当一个缺页中断发生时，对于保存在内存当中的每一个逻辑页面，计算在它的下一次访问之前，还需要等待多长时间，从中选择等待时间最长的那个，作为被置换的页面。
• 这知识一种理想情况，在实际系统中是无法实现的，因此操作系统无从知道每一个页面要等待多长时间之后才会再次被访问
• 可以用作其他算法的性能评价依据

先进先出算法

• 基本思路：选择在内存中驻留时间最长的页面并淘汰之。具体来说，系统维护一个链表，记录了所有位于内存当中的逻辑页面，从链表的排列顺序来看，链首页面的驻留时间最长，链尾页面的驻留时间最短。当发生一个缺页中断时，链首页面淘汰出局，并把新的页面添加到链表末尾。
• 性能较差：调出的页面有可能是经常要访问的页面，并且有belady现象，FIFO很少单独使用。

最近最久未使用

• 基本思路：当一个缺页发生中断时，选择醉酒未使用的那个页面，并且淘汰之
• 他是对最优页面置换算法的一个近似，其依据是程序的局部性原理，即在最近一小段时间内，如果某些页面被频繁的访问，那么在将来的一小段时间内，他们还可能会再一次被频繁的访问。反过来说，如果在过去某些页面长时间未被访问，那么在将来它们还可能很长时间得不到访问。

时钟页面置换算法

• Clock页面置换算法，LRU的近似，对FIFO的一种改进
• 基本思路：
  • 需要用到页表项当中的访问位，当一个页面被装入内存时，把该位初始化为0，如果这个页面被访问，把该位置置为1；
  • 把各个页面组成环形列表(类似时钟表面)，把指针指向最老的页面（最先进来）
  • 当发生一个缺页中断时，考察指针所指向的最老页面，若它的访问位为0，立即淘汰；若访问位为1，则把该位置为0，然后指针往下移动一格。如此下去，直到找到被淘汰的页面，然后把指针移动到它的下一格

二次机会法

最不常用法

• 基本思路：当一个缺页中断发生时，选择访问次数最少的那个页面，并淘汰之

• 实现方法：对每一个页面设置一个访问计数，每当一个页面被访问时候计数器加1.当发生缺页中断时，淘汰计数器值最小的那个页面

Belady现象\LRU\FIFO\Clock比较

• Belady现象：在采用FIFO算法的时候，有时会出现分配的物理页面数增加，缺页率反而提高的异常现象

  • 产生原因：FIFO算法的置换特征与进程访问内存的动态特征是矛盾的，与置换算法的目标是不一致的，因此，被他置换出去的页面并不一定是进程不会访问的。

• LRU和FIFO本质上都是先进先出的思路，只不过LRU针对的是页面的最近访问时间来进行排序，所以需要对每一次页面访问的时候动态调整页面之间的先后顺序；而FIFO是针对页面进入内存时间来进行排序的，这个时间时固定不变的，所以各个页面之间的先后顺序是固定的。如果一个页面进入内存之后没有被访问，那么它的最近访问时间就是它进入内存的时间。换句话说，如果内存当中的所有页面都未曾访问过，那么LRU算法就会退化为FIFO算法。

工作集模型

工作集：一个进程当前正在使用的逻辑页面的集合。

常驻集：指的是当前时刻，进程实际驻留在内存当中的页面的集合

• 工作集是进程在运行过程中的固有性质，而常驻集取决于系统分配给进程的物理页面数目，以及所采用的页面置换算法

抖动问题

• 如果分配给一个进程的物理页面太少，不能包含整个的工作集，即常驻集属于工作集，那么进程将会造成很多的缺页中断，需要频繁的在内存与外村之间替换页面，从而使得进程的运行速度变的很慢，我们把这种状态称为抖动。
• 产生抖动的原因：随着驻留内存的进程数目增加，分配给每个进程的芜劣页面数不断减小，缺页率不断上升。所以OS要选择一个适当的进程数目和进程需要的帧数，以便在并发水平和缺页率之间达到一个平衡。