9.虚拟内存

• 基本特征
  • 大的用户空间：给用户的虚拟空间通常大于实际的内存空间
  • 部分交换：与交换技术相比较，虚拟内存技术调入和调出是对部分虚拟地址空间进行的
  • 不连续性：物理内存分配的不连续

虚拟页式内存管理

在页式内存管理的基础上增加请求调页和页面置换功能

Physical memory +Disk = Virtual Memory

[图片上传中...(2.png-f7e7da-1511267159060-0)]

• 基本思路：

  • 当一个用户程序要调入内存运行时，不是将程序所有页面都装入内存，而是只装入部分的页面，就可以启动程序运行
  • 在运行过程中，如果发现要运行的程序或要访问的数据不在内存，则向系统发出缺页中断请求，系统在处理这个中断时，将外存中相应的页面调入内存，使得该程序能够继续运行

• 页表表项：

  • 驻留位：该页是在内存还是在外存，如果该位为1，表示该页位于内存中，如果为0，表示还在外存中，如果访问该页表项，将导致缺页中断
  • 保护位：表示允许对该页做何种类型的访问
  • 修改位：表明此页在内存中是否被修改过。当系统回收该物理页面时，根据此位来决定是否把它的内容写回外存
  • 访问位：如果该页面被访问过（包括读写操作），如果被访问过就被设置为1。用于页面置换算法

• 缺页中断处理：

  1. 如果在内存中有空闲的物理页帧，则分配一物理页帧f，然后转第4步； 否则转第2步
  2. 采用某种页面置换算法，选择一个将被替换的物理frame，它所对应的逻辑页为q。如果该页在内存期间被修改过，则需要把它写回外存
  3. 对q对应的页表项进行修改，把驻留位设置为0
  4. 将需要访问的页p装入到物理页面页帧f当中
  5. 修改p所对应的页表项的内容，把驻留位设置为1，把物理页帧设置为f

  6. 重新运行被中断的指令

     
     缺页中断处理过程

• EAT（Effective memory Access Time ）=访存时间 * 页表命中率 + page fault处理时间 * page fault几率

  
  EAT例子

页面置换算法

• 功能：当缺页中断发生，需要调入新的页面而内存已满，选择内存当中哪个物理页面被置换
• 目标：尽可能减少页面的换入换出次数（硬盘访问速度太慢）。具体来说，把未来不再使用的或短期内较少使用的页面换出，通常只能在局部性原理指导下依据过去的统计数据来进行预测
• 页面锁定frame locking ：用于描述必须常驻内存的操作系统的关键部分或时间关键的应用程序。实现的方法是：在页表中添加锁定标志位。
• 最优页面置换算法（OPT）
  • 基本思路：当一个缺页中断发生时，对于保存在内存当中的每一个逻辑页面，计算在它的下一次访问之前，还需要等待多长时间，从总选择等待时间最长的那个，作为被置换的页面。
  • 这只是一种理想情况，在实际系统中是无法实现的，因为操作系统无从知道每个页面要等待多长时间以后才能会被再次访问。

  • 可用作其他算法的性能评价的依据

    
    最优页面置换算法

• 先进先出算法(FIFO)
  • 基本思路：选择在内存中驻留时间最长的页面并淘汰之。具体来说，系统维护者一个链表，记录了所有位于内存当中的逻辑页面。从链表的排列顺序来看，链表首的页面淘汰出局，并把新页面添加到链表的末尾。

  • 性能较差，调出的页面可能是经常要访问的页面，并把新的页面添加到链表的末尾

    
    先进先出算法
  • FIFO算法可能会产生Belady异常

  • Bleady现象的原因：FIFO算法的置换特征与进程访问内存的动态特征是矛盾的，与置换算法的目标是不一致的（替换较少使用的页面），因此，被他置换出来的页面并不一定是进程不会访问的。

    
    Belady异常
    Belady1
    Belady2

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

  • LRU算法需要记录各个页面使用的先后顺序，开销比较大。两种可能的实现方法是：1.系统维护一个页面链表，最近刚刚使用过的页面作为首结点，最久未使用的页面作为尾结点。每一次访问内存时，找到相应的页面，把它从链表中摘下来，再移动到链表之首。每次缺页中断发生时，淘汰链表末尾的页面。2.设置一个活动页面栈，当访问某页时，将此页压入栈顶，然后，考察栈内是否有与此页相同的页号，若有则抽出。当需要淘汰一个页面时，总是选择栈底的页面，它就是最久未被使用的。

    
    最近最久未使用算法

• 时钟页面置换算法

  • 基本思路：需要用到页表项中的访问位，当一个页面被装入内存时，把该位初始化为0.然后如果这个页面被访问，则把该位设置为1；把各个页面组织成环形链表，把指针指向最老的页面；当发生一个缺页中断时，考察指针所指向的最老页面，若它的访问位为0，立即淘汰；若访问位为1，则把该位设置为0，然后指针向下移动一格。如此下去，直到找到被淘汰的页面，然后把指针移动到它的下一个。

    
    时钟页面置换实现
    时钟页面置换算法

• 二次机会法

  • dirty bit的设置，在时钟页面置换算法的基础上。

    
    二次机会法

• 最不常用算法（LFU）

  • 基本思路：当一个缺页中断发生时，选择访问次数最少的那个页面，并淘汰之。
  • 实现方法：对每个页面设置一个访问计数器，每当一个页面被访问时，该页面的访问计数器+1。在发生缺页中断时，淘汰计数值最小的那个页面。
  • LRU和LFU的区别：LRU考察的是多久未访问，时间越短越好；而LFU考察的是访问的次数或频率，访问次数越多越好。

• LRU、FIFO和Clock的比较

  • LRU算法和FIFO本质上都是先进先出的思路，只不过LRU是针对页面最近访问时间来进行排序的，所以需要在每一次访问页面的时候动态调整各个也你按之间的先后顺序；而FIFO是针对页面进入内存的时间来进行排序，这个时间是固定不变的，所以各页面之间的先后顺序是固定的。如果一个页面在进入内存后没有被访问，那么他的最近访问时间就是他进入内存的时间。换句话说，如果内存当中所有页面都未曾被访问过，那么LRU算法就退化为FIFO算法
  • LRU算法性能较好，但系统开销大
  • FIFO算法系统开销小，但可能会发生Belady现象
  • 因此，折中的办法就是Clock算法，在每一次页面访问时，他不必去动态调整该页面在链表当中的顺序，而仅仅是做一个标记，然后等到发生缺页中断的时候，再把它移动到链表末尾。对于内存当中那些未被访问的页面，Clock算法的表现和LRU算法一样好；而对于那些曾经被访问过的页面，他不能像LRU算法那样，记住它们的准确位置。

• 工作集：一个进程当前正在使用的逻辑页面集合，可以用一个二元函数W（t，delt）来表示

  • t是当前的执行时刻
  • delt称为工作集窗口，一个定长的页面访问的时间窗口

  • W（t，delt）=在当前时刻t之前的delt时间窗口当中的所有页面所组成的集合（加绝对值就是工作集的大小，也就是页面数目）