虚拟存储器的思想

把内存中暂时不能运行或者暂时不用的程序、数据调动外存上。或者说把程序的一部分放入内存、一部分放在外存。程序运行时，如果所需要访问的页（段）已调入内存，便可继续执行下去；但如果程序所要访问的页（段）尚未调入内存（即缺页或缺段），则程序利用 OS 所提供的请求调页（段）功能，将它们调入内存，以使进程继续执行；如果此时，内存已满，则需利用页（段）置换功能。

  • 置换分类：
    页面对换－－请求分页存储管理(基本分页+页面对换)
    分段对换－－请求分段存储管理(基本分段+分段对换)

请求分页系统

基本思想

  • 在基本分页基础上，增加调页功能和页面置换功能；每次调入和换出的基本单位都是长度固定的页面

硬件支持

要想在基本分页的基础上实现虚拟存储管理，需要

  • 页表机制
  • 缺页中断机构
    请求分页系统中、每当发现要访问的页面不在内存、便产生中断通知 os 调入缺页。
    要经过 保护 CPU 现场、分析中断原因、执行缺页中断程序、执行完毕恢复现场 等步骤。
  • 与一般中断相比，缺页中断有着明显的不同，主要表现在以下两个方面：
    (1)通常，CPU 是在一条指令执行完后，才检查是否有中断请求到达。若有，便去响应；否则，继续执行下一条指令。然而，缺页中断则是在指令执行期间，发现所要访问的指令或数据不在内存时所产生和处理的。
    (2)一条指令在执行期间，可能产生多次缺页中断。

页面置换算法

最佳置换算法

  • 思想：被置换的页面是以后永远不使用或以后长时间不使用的
  • 举例：
    系统为某个进程（有 8 个页面）只分配了 3 个物理块、进程有如下的页面号引用 7，0，1，2，0，3，0，4，2，3，0，3，2，1，2，0，1，7，0，1 求该进程在最佳置换算法下执行完毕缺页多少次? 中断多少次？缺页率为多少？页面置换多少次？

先进先出置换算法(FIFO first in first out)

  • 思想：淘汰最先进入内存的页面、即选择在内存中驻留时间最久的页面给予淘汰。

最近最久未使用的置换算法(LRU lease recently used)

  • 思想：选择和现在相比最长时间没有使用的页面进行置换。
  • 硬件：
    寄存器：记录某进程在内存中各页的使用情况
    栈：用来保存当前使用的各个页面的页面号

CLOCK 置换算法

  • LRU 算法是较好的一种算法，但由于它要求有较多的硬件支持，故在实际应用中，大多采用 LRU 的近似算法。Clock 算法就是用得较多的一种 LRU 近似算法。
  • 思想：为每页设置一位访问位，再将内存中的所有页面都通过链接指针链接成一个循环队列。当某页被访问时，其访问位被置为 1.置换算法选择一位淘汰时，只需检查页的访问位。如果是 0，就选择该页换出；若为 1，则重新将它置 0，暂不换出，而给该页第二次驻留内存的机会，在按照 FIFO 算法检查下一个页面。