L3.5 内存换入-请求调页

采用 换入-换出 实现虚拟内存

1、请求调页

• 程序运行时物理内存缺页 -> 中断处理程序：请求调页（从磁盘换入），换入后回到中断位置继续执行程序
• 实现：虚拟内存大小永远为4G，而物理内存可以为512M、1G等，但通过请求调页的方式来实现4G内存
  

2、实际代码

重点在于缺页后的**中断处理**：

1. 申请空闲页
2. 将所需页从磁盘中读到空闲页
3. 建立虚拟地址和物理内存映射

• 获取错误码和缺页地址，压栈后调用do_no_page
  

• 申请一页空间，从磁盘上将需要的页读入，并建立物理内存和逻这一页虚拟地址的映射
  

• 建立映射：修改页表
  

---

L3.6 内存换出

核心是算法选择需要淘汰的页

1、FIFO

显然不合理，评价指标：缺页次数

2、MIN算法

将最远将使用的页淘汰，是最优方案

• 缺点：无法知道将来访问哪一页

3、LRU算法（least recent used）

用过去的历史预测将来：选最近最长一段时间没有使用的页淘汰（最近最少使用） -> 因为程序具有局部性

4、LRU实现

1. 时间戳
   

• 每执行一条指令都要查表并维护时间戳表（代价太大）

2. 页码栈
   

• 每次访问地址都要修改栈

3. 近似实现：SCR（二次机会算法/Clock算法）

• 每页加一个引用位：每执行一条指令只需要修改一位数
  

• 如果缺页很少，容易出现全部R=1，则指针会转一圈，然后都为0后从第一个开始执行，顺序下去，退化为FIFO

• 使用两个指针，一个移动速度快（体现最近）来清除 R 位，用慢指针来选择淘汰页。（双指针clock算法）
  

5、进程分配页框数

• 理论上应该覆盖住一个进程的局部
  

6、换入与换出

• 即安装Ubuntu时的Swap分区