一、基本原理

• 建立在基本分页机制之上

  • 程序的逻辑空间划分为若干固定大小的页面
  • 物理内存划分为若干固定大小的页框
  • 页面可以载入任意页框——页表记录载入情况

• 引入请求调页和页面置换功能

  • 部分页面载入内存
  • 对换机制
  • 以页面作为换入或换出的基本单位

二、硬件支持

1. 页表机制

• 状态位P：用于指示该页是否已调入内存。

• 访问字段A：用于记录本页在一段时间内被访问的次数，或记录本页最近已有多长时间未被访问。

• 修改位M：表示该页在调入内存后是否被修改过。

• 外存地址：用于指出该页在外存上的地址。

2. 缺页中断机制

每当所要访问的页面不在内存时，便产生一缺页中断，请求OS将所缺之页调入内存。缺页中断与普通中断相比，其特殊性表现在两个方面：

1. 在指令执行期间产生和处理中断信号

2. 一条指令在执行期间，可能产生多次缺页中断

3. 地址转换机制

• 带快表的基本分页地址转换部分

• 缺页中断处理部分

• 页面换出部分

地址转换练习

在缺页处理过程中，操作系统执行的操作可能是（）

A 修改页表

B 磁盘I/O

C 分配页框

答案

A、B、C

二、虚拟内存的操作系统策略

• 读取策略：决定某页何时取入内存

  • 请求分页（demanding paging）
  • 预先分页（preparing）

• 放置策略：决定一个进程块驻留在实存中的什么位置

• 必须读取一个新页时应该置换内存中的哪一页

  • 驻留集管理：如何为每个进程分配页面
  • 置换策略：在计划置换的页集中，选择换出哪一页

1. 读取策略

决定某页何时取入内存

请求分页（demanding paging）

• 只有当访问到某页中的一个单元时才将该页取入内存

• 调入发生缺页的页面

• 发现缺页再调入，系统开销大

预先分页（preparing）

• 调入邻近页面

• 准确性不高

调页的位置

• 对换区：修改过的页被换出时入对换区，快

• 文件区：稍慢

2. 置换策略

选择换出页面的算法

局部置换

发生缺页时选择进程自己的物理块置换

全局置换

可以将os的空闲物理块分配给缺页进程，也可以别的进程持有的物理块置换到外存后分配给缺页进程

3. 驻留集管理

固定分配策略

进程分配到的物理块在进程运行期间不再改变

可变分配策略

进程运行期间根据情况增加或减少物理块

Info

可组合出以下三种适用的策略

• 固定分配局部置换（Fixed Allocation，Local Replacement）

• 可变分配局部置换（Variable Allocation，Local Replacem）

• 可变分配全局置换（Variable Allocation，Global Replacem）

4. 页面置换的基本过程

• 查找所需页在磁盘上的位置

• 查找一个空闲页框

  • 如果有空闲页框，就使用它
  • 如果没有空闲页框，就选择一个页面并淘汰之

• 将淘汰页面的内容写到磁盘上，改变页表

• 将所需页读入(新)空闲页框，改变页表

• 重启用户进程

三、置换算法

• 概念

  • 选择换出页面的算法

• 评价标准

  • 页面的交换频率

• 设计目标

  • 换出不再访问的页面
  • 换出最久不访问的页面

• 设计原则

  • 基于过去的页面访问行为预测将来的页面访问行为

1. 最优置换算法（OPT）

基本思想

• 换出不再访问的页面

• 换出最久不访问的页面

例子

假设系统为某进程分配了3个页框，其页面走向如下：6 4 0 2 1 4 2 5 6 2 5 3 2 5 2 6 2 3 2 求采用OPT页面淘汰算法时缺页中断次数。

算法讨论

• 理想算法

  • 通过未来页面走向选择被淘汰的页面，可以保证最少的缺页中断次数

• 评价标准

  • 需要知道未来的访问顺序，不可能实现，可以作为其它算法的评价参考

2. 先进先出置换算法（FIFO）

基本思想

换出最早调入内存的页面

例子

假设系统为某进程分配了3个页框，其页面走向如下：6 4 0 2 1 4 2 5 6 2 5 3 2 5 2 6 2 3 2 求采用FIFO页面淘汰算法时缺页中断次数

算法实现

可以采用链表结构

算法讨论

• 简单易于实现

• 未考虑程序的时间局部性原理由于全局变量、常用函数等的存在，某些页面需要经常访问

• 存在Belady异常现象

Belady现象

• 分配的页框数越多，缺页中断次数越少?

  • 一个进程的页面走向为：1 2 3 4 1 2 5 1 2 3 4 5
  • 页面走向中的页面数为12，进程的页面数为5

• Belady异常现象

  • 随着分配的页框数增加,缺页中断次数有时反而增加

• 例子

  • 一个进程的页面走向为：1 2 3 4 1 2 5 1 2 3 4 5
  • 页框数为3时，缺页中断次数为9
  • 页框数为4时，缺页中断次数为10

3. 最近最久未使用算法（LRU）

基本思想

• 如果某一页面被访问了，那么它很可能马上又被访问。

• 如果某一页面很久未被访问，那么最近很可能不会被访问。

算法

选择最近一段时间内最长时间未被访问过的页面予以淘汰

例子

假设系统为某进程分配了3个页框，其页面走向如下：6 4 0 2 1 4 2 5 6 2 5 3 2 5 2 6 2 3 2 求采用LRU页面淘汰算法时缺页中断次数。

算法实现

• 寄存器表

  • 为每个驻留页面分配一个寄存器
  • 数据格式：R=R_n-1R_n-2R_n-3… R₂R₁R₀
  • 页面被访问一次，最高位R_n-1置1
  • 每隔一定时间，每个寄存器右移一位
  • R值最小的页面是被置换页面

• 双向链表

算法讨论

• 性能低于OPT算法

  • OPT算法：基于真实的未来页面走向
  • LRU算法：基于过去页面走向来预测将来页面走向

• 性能较好

  • 程序的时间局部性原理

• 开销太大

  • 需要统计所有页面的访问时间信息，从而获得最久未使用页面。

4. 时钟置换算法（CLOCK，Not Recently Used）

基本思想

• LRU算法的简化近似算法

• 换出最近未访问过页面，NRU算法

算法实现

• 每个页面设置一个访问位，访问该页面时置1。

• 所有页面保存在环形链表中。

• 发生缺页中断时，首先检查表针指向页面，如果R为0，则新页面替换之；如果R为1，则清0，表针前移一个位置，重复上述过程。

例子

假设系统为某进程分配了3个页框，其页面走向如下：7 0 1 2 0 3 0 4，求采用CLCOK页面淘汰算法时缺页中断的次数

算法讨论

• 算法比较简单

• 性能与置换间的间隔密切相关

  • 间隔过大，随机选择换出页面
  • 间隔过小，随机选择换出页面

• 未考虑页面修改情况

5. 改进型时钟置换算法

基本思想

考虑页面的修改情况

页面分类

• 1类(A=0, M=0)：最近未被访问，又未被修改，最佳淘汰页。

• 2类(A=0, M=1)：最近未被访问，但已被修改页。

• 3类(A=1, M=0)：最近已被访问，但未被修改。

• 4类(A=1, M=1)：最近已被访问且被修改，最不应淘汰页。

算法实现

1. 选择最佳淘汰页面(A=0,M=0)

2. 如果1失败，寻找第2类页面(A=0, M=1)，并把所扫描过的页面的访问位A置0。

3. 如果2失败，回到步骤1。

算法讨论

实现简单，性能比较理想，被广泛采用。

6. 置换算法示例

设某计算机的逻辑地址空间和物理地址空间均为64KB，按字节编址。若某进程最多需要6页存储空间，页的大小为1KB。操作系统采用固定分配局部置换为此进程分配4个页框(Page Frame)，如下表所示

若该进程执行到260时刻时，要访问逻辑地址为17CAH的数据，请回答

1. 该逻辑地址对应的页号是多少?

2. 若采用先进先出(FIFO)置换算法，该逻辑地址对应的物理地址是多少? 要求给出计算过程。

3. 若采用时钟(CLOCK)置换算法，该逻辑地址对应的物理地址是多少?要求给出计算过程(设搜索下一页的指针沿着顺时针方向移动，且当前指向2号页框，如上图所示)

答案

17CA = 0001 0111 1100 1010

页的大小为1KB，所以页内偏移为10位，11 1100 1010

物理地址空间为64KB，所以物理地址为16位。

页号16-10=6位，即000101，所以页号为5。

页面走向为0，3，2，1，5

采用FIFO算法时的页面置换情况为：

所以页框号为7，则物理地址为0001 1111 1100 1010，即1FCAH

所以页框号为2，则物理地址为0000 1011 1100 1010，即0BCAH

四、缺页率

发生缺页的次数与总访问次数的比值。

1. 影响因素

• 页面置换算法

• 页面的大小

• 进程所占的页框数

• 程序的特性

• 即编写程序的方法对缺页中断次数有影响

2. 程序编写方式对缺页率的影响示例

有一矩阵int a[100][100]以行优先进行存储。有一请求分页存储管理系统，物理内存共有3页，其中1页用来存放程序，其余2页用于存放数据。假设程序已在内存中占1页，其余2页空闲；数组中的元素按行编址存放。

// 程序A
for (i=0; i<=99; i++) 
    for (j=0; j<=99; j++) 
        a[i][j]=0;

// 程序B

for (j=0; j<=99; j++)
    for (i=0; i<=99; i++)
        a[i][j]=0;

若每页可存放200个整数，程序A和程序B的执行过程各会发生多少次缺页，这说明了什么问题?

(1)数组大小：100*100=10000，2个内存页存放数据，每页存放200个整数。

(2)数组中的元素按行编址，程序A对数组的访问顺序与存储顺序一致，每访问2行数组元素就会产生一次缺页中断，故缺页中断次数为100/2=50程序B对数组的访问顺序与存储顺序不一致，每访问2个数组元素就会产生一次缺页中断，故缺页中断次数为10000/2=5000

(3)缺页中断次数和数据的存放方法以及程序访问数据的方法有很大关系。

3. 平均访问时间（有效访问时间）

若缺页率为p，内存的访问时间为ma，发生缺页时的访问时间为da，则平均访问时间为(1-p)*ma+p*da

构成

• 1ms

  • 缺页服务时间
  • 进程重新执行时间

• 20ms

  • 页面调入时间=寻道时间+旋转时间+数据传送时间

Note

由于ma很小(<10ns)，因此很低的缺页率也会导致很大的平均访问时间。

有效访问时间示例

1. 假设内存的访问时间为10ns，发生缺页的访问时间为21ms，若因为缺页而出现的性能降低不超过10%，则缺页率的最大数值为多少?(1s=10³ms=10⁶μs=10⁹ns)

答案

有效访问时间EAT=(1-p)*0.01+21000*p，单位为μs

EAT<=(1+10%)*0.01

p<= 0.000 000 05

2. 请求分页管理系统中，假设某进程的页表内容如下：

页号	页框号	有效位
0	101H	1
1	-	0
2	254H	1

页面大小为4KB，一次内存的访问时间是100ns，一次快表(TLB)的访问时间是10ns，处理一次缺页的平均时间为108ns(已含更新TLB和页表的时间)，进程的驻留集大小固定为2，采用最近最少使用置换算法(LRU)和局部淘汰策略。假设：

1. TLB初始为空

2. 地址转换时先访问TLB，若TLB未命中，再访问页表(忽略访问页表之后的TLB更新时间)

3. 有效位为0表示页面不在内存，产生缺页中断，缺页中断处理后，返回到产生缺页中断的指令处重新执行

设有虚地址访问序列2362H、1565H 、25A5H。

1. 依次访问上述三个虚地址，各需要多少时间?

2. 基于上述访问序列，虚地址1565H的物理地址是多少?

答案

页面大小L=4KB=1000H个字节

虚地址A1=2362H的页号为：(int)(2362H/1000H)=2

虚地址A2=1565H的页号为：(int)(1565H/1000H)=1

虚地址A3=25A5H的页号为：(int)(25A5H/1000H)=2

页面置换情况：

1. 虚地址A1的访问时间=访问TLB的时间+访问页表时间+访问内存单元的时间=10ns+100ns+100ns=210ns

虚地址A2的访问时间=访问TLB的时间+访问页表时间+调页时间+访问TLB的时间+访问内存单元的时间=10ns+100ns+100000000+10ns+100ns=100000220ns

虚地址A3的访问时间=访问TLB的时间+访问内存单元的时间=10ns+100ns=110ns

2. 1565H的页号为1，对应的页框号为101H，其页内偏移量为565H，故物理地址为101565H

4. 工作集

缺页率与物理块数的关系：

• 进程对地址空间的访问是不均匀的，即在确定的一段时间内，进程往往只访问固定的几个页面。

• 工作集的概念(Peter Denning @ 1968) 在某段时间间隔内，进程实际要访问的页面的集合。

• 进程分配的页框数不能小于工作集的大小

• 不同时刻，进程的工作集大小可能不同

Info

系统根据缺页率动态调整进程分配的页框数

五、虚拟存储的问题：抖动/颠簸（thrashing）

现象

• 页面被频繁地换入换出，缺页率急剧增加

• 内存有效存取时间加长

-系统吞吐量骤减，系统已基本不能完成什么任务。

表面原因

CPU利用率太低→调度程序就会增加多道程序度→新进程启动运行→内存不足→缺页→I/O忙碌，CPU空闲

根本原因

多道程序度过高，每个进程分配的页框数目过少。

CPU利用率与多道程序度的关系示例

抖动的预防

控制系统的多道程序度

• 采用局部置换策略当某进程发生缺页时，仅在自己的内存空间范围内置换页面，并且新创建的进程不会挤占其它进程的内存空间。

• 在CPU调度程序中运用工作集算法防止过多调入新任务，保证每个进程具有超过其工作集大小的页框数目。

• L=S准则(Denning @1980) 发生缺页的平均时间L等于处理缺页故障的平均时间S，此时系统具有最好的多道程序度。

• 挂起若干进程

六、请求分页存储管理方式的优缺点

1. 优点

• 存在页内碎片，但碎片相对较小，内存利用率较高

• 实现了离散分配

• 无外部碎片

• 提供了虚拟存储器，使大作业可以在较小的实际内存中运行

• 并发度高

缺点

• 必须有相应的硬件支持，例如地址转换机构、缺页中断机构和淘汰页面等都需要硬件的支持

• 不支持动态链接，不易实现共享

• 可能因为作业地址空间过大或多道程序的道数过多，造成系统抖动现象的发生