虚拟存储

操作系统

虚拟存储

基本概念

存储：容量、速度、价格、非易失性
覆盖：应用程序池需要的指令和数据库存到内存中
交换：操作系统自动地将不执行的程序保存到外存中
虚拟内存：有限容量内存中，以页位单位自动装入更大的程序。
整个内存的换入换出：
- 交换时机：内存不够
- 交换区大小：所有内存映像
- 程序换入重定位：动态地址映射

局部性原理

时间局部性
空间局部性（相邻指令数据）
分支局部性（指令执行，跳到相同内存）

虚拟存储

缺页中断
装载程序：需要的页面、段
缺页：操作系统通知调入
暂时不用的页段-->外存
特点：
不连续、大用户空间、部分交换
技术：
硬件：地址转换
操作系统：换入换出

虚拟页式存储

页式存储加上请求调页和页面置换：装入页面、缺页、页面调入。

页表项结构：
驻留位：是否在内存
修改位：被修改过
访问位：页面置换算法
保护位：读、写、执行

缺页异常处理：替换-->装入-->执行

外存管理：
对换区
--|外存选择
----| 代码：可执行二进制文件
----| 共享程序段：动态调用库文件
----| 其他段：交换区
文件特殊格式

虚拟页式存储性能：
有效存储访问时间EAT=访存时间*（1-p）+缺页异常处理时间*(缺页率p)

页面置换算法

基本概念

选择被置换物理页面：
尽可能减少页面调入调出次数，不访问页面调出
页面锁定：
常驻逻辑页面，系统关键部分，相应的代码和数据，锁定标志位（lock bit）
评价：记录访问页面轨迹，缺页更少，更好的性能

局部置换算法（仅限当前进程物理页面）

• 最优算法OPT
  计算页面下一次访问时间，选择未来最长不访问页面，无法预测，作为其它算法评价依据
• 先进先出FIFO
  内存驻留时间最长页面进行置换（逻辑页面链表），性能较差，很少单独使用
• 最近最久未使用算法LRU
  最长未被引用置换，近似最优算法（开销大）：
  页面链表：按访问时间的链表
  活动页面栈：页号压栈，相同抽出
• 时钟置换算法Clock
  访问大致统计：页面访问位，环形链表指针指向调入页面，访问记录情况，缺页顺序查找，LRU和FIFO折中，扫描置零
  改进：减少开销，修改位（写-->修改位+访问位，跳过修改位）
• 最不常用算法LFU
  置换访问次数少的页面，定期右移。

全局页面置换（所有可换出物理页面）

进程差异：可变物理页面数目
工作集：进程逻辑页面集合W（t，δ），δ访问窗口，|W(t,δ)|页面数目
--|常驻集：换出不在工作集页面：访存链表
--|缺页率、缺页间隔：缺页平均时间间隔（置换算法、物理页面数目页面大小、调整常驻集大小，引用标志位，缺页间隔）

抖动：
进程太多，物理页面太小，不能包含工作集，大量进行缺页处理
负载控制：
调节并发数

进程数目
缺页间隔MTBF>缺页异常处理时间（PFST）

Belady现象

分配物理页增多，缺页次数升高，FIFO有此现象，OPT、LRU无此现象

LRU/FIFO/Clock

LRU：访问时间排序
FIFO：页面进入内存顺序
LRU动态调整，LRU退化为FIFO
Clock：标记，缺页移到末尾

LRU：性能好，开销大
FIFO：开销小，发生Belady现象。