[第六章]虚拟存储器

概述

局部性原理

• 时间局部性
• 指令执行后一段时间可能还会执行

• 空间局部性
• 程序访问存储单元，一段时间后可能还会访问

核心思想

• 大程序划分成多个小部分

• 使用局部空间，局部时间仍然保证程序正常运行

• 通过替换、覆盖、调度来进入下一个“局部”

原始的虚拟存储—覆盖技术

• 程序分为若干块，动态覆盖先前块

• 块划分、内存保护困难

虚拟页式存储管理

概述

基本思想

• 分页

• 不装入全部页面，动态装入需要页面

• 当需要装入新页面但内存已满，淘汰某个页面

页表

• 状态位：是否在内存

• 访问位：淘汰的依据

• 修改位：是否修改

缺页中断

• 与一般中断区别
• 一般：指令执行完中断
• 缺页：指令执行过程中断（缺页的指令无法执行完

页面分配策略和算法

最小物理块

内存分配策略

• 分配策略：固定分配、可变分配

• 置换策略：全局置换、局部置换

1. 固定分配局部置换
• 每个进程分配一定数目的内存空间，运行期间不再改变
• 缺页时在内存中置换一项

2. 可变分配全局置换
• 每个进程分配一定数目的物理块，系统设置一个空闲物理块队列
• 缺页时从物理块队列中去除物理块分配给进程，并将调入的缺页装入
• 空闲队列用完选一页调出

3. 可变分配局部置换
• 每个进程分配一定数目的物理块
• 缺页时在内存中置换一项
• 若频繁中断则增加物理块，反之减少

物理块分配算法

1. 平均分配算法

2. 按比例分配算法
进程大小的比例

3. 考虑优先权的分配算法

页面调入算法

调入时机

• 预调页
• 预测，预先调入
• 首次调入程序员指明调入内容
• 缺点：准确率只有一半

• 请求调页
• 发现所需不在，立即请求调入
• 缺点：每次只调入一页，增加磁盘I/O的启动频率，系统开销大

调入位置

• 系统有足够对换区空间
• 执行前将所有有关文件拷贝到对换区，从对换区调入

• 缺少最够多对换区空间
• 不被修改的文件从文件区调入，换出不写回
• 对可能修改部分，换出到对换区，从对换区调入

• UNIX方式
• 未运行过的从文件区调入
• 曾经运行过的被放入对换区，再次调入从对换区调入
• 允许页面共享，某进程请求的页面有可能已被其它进程调入内存，不用再从对换区调入

调入过程

1. 要访问的页面未在内存

2. 发出缺页中断

3. 中断处理程序保留CPU环境，分析中断原因

4. 转入缺页处理程序

页面淘汰算法⭐

• 页面号引用串
• 页号串

• 评判指标
• 缺页率：缺页数/判断缺页的次数
• 预装载参与缺页率计算，参与装载，算不缺页
• 如果说“运行之初页面都不在内存”则预装载参与缺页率计算，且参与装载，算缺页

最佳页面算法（理想淘汰算法）（OPT）

• 最好的性能
• 固定分配页面方式中最低缺页率

• 难以实现
• 选择条件不可知

先进先出淘汰算法(FIFO)

• 性能差

• 实现
• 把已调入的页面按次序链接成队列（先进先出），设置一个替换指针，指向最老页面

• 物理块增多，缺页率不降反升Belady现象

最近最久未使用页面淘汰算法（LRU）

• 性能

• 实现
• 硬件
1. 为每页设一个寄存器R
2. 访问：该页对应的R最高位置1
3. 每个时间间隔所有R右移一位
• 淘汰：R值最小的
• 软件
• 设置页号栈
• 访问：入栈，如果之前访问过，将原本位置改成栈顶
• 淘汰：栈底出栈，栈顶入栈

LRU近似算法：简单Clock算法

• 循环队列

• R初值为0

• 访问，访问位置1

• 淘汰
• 第一个访问位为0，换出
• 遍历访问位为1的置0

改进型Clock页面置换算法

• 循环队列

• R初值为0，M初值为0

• 访问，R置1；修改，M置1

• 淘汰
1. 指针位置开始遍历（R=0,M=0），第一个淘汰。失败进下一步
2. 指针位置开始遍历（R=0,M=1），第一个淘汰。失败进下一步
3. 遍历访问位全置0，再运行1.2.

最少使用淘汰算法（LFU）

页面缓冲算法（PBA）

• 被淘汰页面放在两个链表
• 未修改→放到空闲链表，可覆盖
• 所在物理块挂在空闲链表的末尾
• 已修改→放到已修改链表，统一回写

影响缺页率的因素

• 物理块数

• 页本身大小
• 页太小，经常缺页中断

• 程序编制方法

• 页淘汰算法

虚拟段式存储管理

基本机制

段表

• 存在位：是否已调入内存

• 增补位：是否进行过动态增长。

缺段中断

1. if有足够内存空间 装入;

2. if空闲区总和满足要求 {紧缩技术；转1.}

3. 淘汰算法，转1

淘汰算法

分段共享

共享段表

• 存取控制字段：不同进程采用不同存取控制方式

• 段号：不同的进程可以使用不同的段号去共享该段

• 共享进程计数count：整型变量，记录共享该分段的进程数，为0回收共享段

共享段分配

• 首次请求，放入物理区，新增共享段表项，count=1

• 其他进程请求该段，调用者段表中只需填入共享表段的物理地址

• 共享段段表填上进程名、存取控制、count++

共享段回收

• 取消调用者进程在共享表中的记录，共享段表count- -

• if(0 == count) 取消共享段表表项;

环保护机构

• 低编号环具有高优先权

• 程序可以访问同环或低环

• 调用铜环或高环