Cha8 虚拟存储器要求掌握
程序的局部性，抖动
页表和段表的支持
地址转换过程
快表
替换策略分页与分段管理的突破
运行时动态的地址转换
允许程序在内存中分散存放
程序不必全部进入内存驻留集 resident set
程序执行
a1
a1
1 OS
p1
2
b2
a3
3
4
a3
5
6
1程序部分进入内存
2页表显示内存错误
3OS启动读盘
4OS调度另个作业
5读入要用的页
6结束时发出中断唤醒原进程实存与虚存
实存 real memory
虚存 virtual memory
内存中存放更多的进程
进程长度可以大于内存程序的局部性原理
减少程序占用内存
减少挂起时的传输量
抖动 thrashing
– 刚刚被换出的页面很快又要用到
– CPU忙于调出和调入页面
OS根据最近的历史猜测将来不会用到的页面典型的内存管理格式页号 偏移量
P M 其他 页框号虚地址页表项仅仅分页段号 偏移量虚地址段表项仅仅分段段号 页号 偏移量其他 长度 基地址虚地址段表项分段和分页结合
P M 其他 页框号页表项
P M 其他 长度 基地址修改位存在位页表结构－两级页表
……
……
……
用户地址空间
4G
用户页表
4M
根页表
4K
页面长度 4K
页表项 4字节两级分页系统的地址转换
10位 10位 12位根页表指针
＋
页框 偏移量二级页表一级页表
＋
页表结构－反向页表页号 表项 指针页号 偏移量 页框 偏移量
Hash表 反向页表
Hash函数快速页表 tranlation lookaside buffer
虚地址实地址快表页表
TLB命中
TLB失败页面错误
I/O
内存外存相关问题
TLB的关联映射
Cache问题
TLB
部分页表全部页表页表项
cache
内存外存指令具备快表机制的分页算法 开始
CPU检查 TLB
TLB命中访问页表页在内存更新 TLB
内存满
OS启动读页读页替换算法更新页表形成实地址
Y
Y
关于页面长度的设计
内部碎片的大小
页表的长度
辅存设备的特性
页面错误
物理内存大小
新的编程方法页面错误页面长度 页框数缺页率段式结构的优点
简化增长的数据结构的处理
允许程序独立修改和编译
方便共享和保护分段与分页的结合段号 页号 偏移量段表地址＋
＋
页框 偏移量段表页表
Os的存储管理设计
是否使用虚存
采用分页还是分段
实现各项内存管理要求的算法
OS虚存管理策略
取策略
放置策略
替换策略
驻留集管理
清除策略
装入控制取策略
请求式页面调度 demand paging
– 只调入需要的页面
预约式页面调度 prepaging
– 预先调入若干页面替换策略
每个进程分配多少页框
从本进程还是所有进程替换
换出哪一页驻留集管理
最佳 OPT
最近最少使用 LRU
先进先出 FIFO
时钟 Clock
锁定帧算法对比
2 3 2 1 5 2 4 5 3 2 5 2
OPT 2 2 2 2 2 2 4 4 4 2 2 2
3 3 3 3 3 3 3 3 3 3 3
1 5 5 5 5 5 5 5 5
LRU 2 2 3 3 2 1 5 2 4 5 3 3
3 2 2 1 5 2 4 5 3 2 5
1 5 2 4 5 3 2 5 2
FIFO 2 2 2 2 3 1 5 5 2 2 4 3
3 3 3 1 5 2 2 4 4 3 5
1 5 2 4 4 3 3 5 2
算法对比
2 3 2 1 5 2 4 5 3 2 5 2
clock 2 2 2 2 5 5 5 5 3 3 3 3
3 3 3 3 2 2 2 2 2 2 2
1 1 1 4 4 4 4 5 5
Clock策略
p19
u=1 p1u=1
p45
u=1
p191
u=1
p556
u=0p13
u=0
p67
u=1
p33
u=1
p222
u=0
p9
u=1
p19
u=1 p1u=1
p45
u=0
p191
u=0
p727
u=1p13
u=0
p67
u=1
p33
u=1
p222
u=0
p9
u=1
Clock算法的改进使用位 u 修改位 m
U=0 m=0
U=0 m=1
U=1 m=0
U=1 m=1
扫描寻找 u=0 m=0的页扫描寻找 u=0 m=1的页把经过的 u=1改为 0
算法性能比较分配的页框数
6 8 10 12 14
FIFO
clock
LRU
OPT
缺页率页缓冲自由页表－页面内容未改过修改页表－页面内容修改过驻留集管理局部替换 全局替换固定分配 进程的页框数固定从本进程选择替换页 不可能可变分配 进程的页框数可变从本进程选择替换页 进程的页框数可变从所有进程选择替换页工作集 W(时刻，长度 )
2 3 4 5
24 24 24 24 24
15 24 15 24 15 24 15 24 15
18 15 18 24 15 18 24 15 18 24 15 18
23 18 23 15 18 23 15 18 23 24 15 18 23 24
24 23 24 18 23 24 。 。
17 24 17 15 18 23 24 17
18 17 18
24 24 18
18 。
17 17 18
17 17
15 17 15
24 15 24
17 24 17
24 。
18 24 18
利用工作集决定驻留集
监视进程的工作集
周期性修改驻留集
进程的工作集在内存时才执行工作集策略的问题
工作集经常变化
无法为每个进程测量工作集
时间窗口长度的最优值未知
缺页频率算法 PFF
– 缺页率? 驻留集?
– 缺页率? 驻留集?
缺页频率算法上次缺页时间 本次缺页时间被访问的页面 u=1
a b
b-a<F 增加该页到驻留集
b-a>F 淘汰所有 u=0的页所有 u=0
……
所有 u=0
局部性过渡期间效果不好
VSWS策略
Variable-interval sampled working set
可变间隔采样的工作集策略
M－采样间隔上限
L－采样间隔下限
Q－采样间隔的缺页量
t>M
t<M但达到 Q
t<L
t>L
扫描 u等待当前时间－上次采样时间＝ t
清除策略
请求式清除
– 成对的读写操作
预约式清除
– 重复写出与页缓冲技术相结合自由页表修改页表成批写多道程序效果
L=S缺页间隔＝缺页处理时间
CPU使用率页面调度设备的使用率为 50％
Clock扫描速度太慢 增加多道程序级别挂起进程的选择
如果要挂起进程，可以选择 ……
– 优先级最低的
– 缺页的
– 最后被激活的
– 驻留集最小的
– 最大的
– 剩余执行窗口最大的
程序的局部性，抖动
页表和段表的支持
地址转换过程
快表
替换策略分页与分段管理的突破
运行时动态的地址转换
允许程序在内存中分散存放
程序不必全部进入内存驻留集 resident set
程序执行
a1
a1
1 OS
p1
2
b2
a3
3
4
a3
5
6
1程序部分进入内存
2页表显示内存错误
3OS启动读盘
4OS调度另个作业
5读入要用的页
6结束时发出中断唤醒原进程实存与虚存
实存 real memory
虚存 virtual memory
内存中存放更多的进程
进程长度可以大于内存程序的局部性原理
减少程序占用内存
减少挂起时的传输量
抖动 thrashing
– 刚刚被换出的页面很快又要用到
– CPU忙于调出和调入页面
OS根据最近的历史猜测将来不会用到的页面典型的内存管理格式页号 偏移量
P M 其他 页框号虚地址页表项仅仅分页段号 偏移量虚地址段表项仅仅分段段号 页号 偏移量其他 长度 基地址虚地址段表项分段和分页结合
P M 其他 页框号页表项
P M 其他 长度 基地址修改位存在位页表结构－两级页表
……
……
……
用户地址空间
4G
用户页表
4M
根页表
4K
页面长度 4K
页表项 4字节两级分页系统的地址转换
10位 10位 12位根页表指针
＋
页框 偏移量二级页表一级页表
＋
页表结构－反向页表页号 表项 指针页号 偏移量 页框 偏移量
Hash表 反向页表
Hash函数快速页表 tranlation lookaside buffer
虚地址实地址快表页表
TLB命中
TLB失败页面错误
I/O
内存外存相关问题
TLB的关联映射
Cache问题
TLB
部分页表全部页表页表项
cache
内存外存指令具备快表机制的分页算法 开始
CPU检查 TLB
TLB命中访问页表页在内存更新 TLB
内存满
OS启动读页读页替换算法更新页表形成实地址
Y
Y
关于页面长度的设计
内部碎片的大小
页表的长度
辅存设备的特性
页面错误
物理内存大小
新的编程方法页面错误页面长度 页框数缺页率段式结构的优点
简化增长的数据结构的处理
允许程序独立修改和编译
方便共享和保护分段与分页的结合段号 页号 偏移量段表地址＋
＋
页框 偏移量段表页表
Os的存储管理设计
是否使用虚存
采用分页还是分段
实现各项内存管理要求的算法
OS虚存管理策略
取策略
放置策略
替换策略
驻留集管理
清除策略
装入控制取策略
请求式页面调度 demand paging
– 只调入需要的页面
预约式页面调度 prepaging
– 预先调入若干页面替换策略
每个进程分配多少页框
从本进程还是所有进程替换
换出哪一页驻留集管理
最佳 OPT
最近最少使用 LRU
先进先出 FIFO
时钟 Clock
锁定帧算法对比
2 3 2 1 5 2 4 5 3 2 5 2
OPT 2 2 2 2 2 2 4 4 4 2 2 2
3 3 3 3 3 3 3 3 3 3 3
1 5 5 5 5 5 5 5 5
LRU 2 2 3 3 2 1 5 2 4 5 3 3
3 2 2 1 5 2 4 5 3 2 5
1 5 2 4 5 3 2 5 2
FIFO 2 2 2 2 3 1 5 5 2 2 4 3
3 3 3 1 5 2 2 4 4 3 5
1 5 2 4 4 3 3 5 2
算法对比
2 3 2 1 5 2 4 5 3 2 5 2
clock 2 2 2 2 5 5 5 5 3 3 3 3
3 3 3 3 2 2 2 2 2 2 2
1 1 1 4 4 4 4 5 5
Clock策略
p19
u=1 p1u=1
p45
u=1
p191
u=1
p556
u=0p13
u=0
p67
u=1
p33
u=1
p222
u=0
p9
u=1
p19
u=1 p1u=1
p45
u=0
p191
u=0
p727
u=1p13
u=0
p67
u=1
p33
u=1
p222
u=0
p9
u=1
Clock算法的改进使用位 u 修改位 m
U=0 m=0
U=0 m=1
U=1 m=0
U=1 m=1
扫描寻找 u=0 m=0的页扫描寻找 u=0 m=1的页把经过的 u=1改为 0
算法性能比较分配的页框数
6 8 10 12 14
FIFO
clock
LRU
OPT
缺页率页缓冲自由页表－页面内容未改过修改页表－页面内容修改过驻留集管理局部替换 全局替换固定分配 进程的页框数固定从本进程选择替换页 不可能可变分配 进程的页框数可变从本进程选择替换页 进程的页框数可变从所有进程选择替换页工作集 W(时刻，长度 )
2 3 4 5
24 24 24 24 24
15 24 15 24 15 24 15 24 15
18 15 18 24 15 18 24 15 18 24 15 18
23 18 23 15 18 23 15 18 23 24 15 18 23 24
24 23 24 18 23 24 。 。
17 24 17 15 18 23 24 17
18 17 18
24 24 18
18 。
17 17 18
17 17
15 17 15
24 15 24
17 24 17
24 。
18 24 18
利用工作集决定驻留集
监视进程的工作集
周期性修改驻留集
进程的工作集在内存时才执行工作集策略的问题
工作集经常变化
无法为每个进程测量工作集
时间窗口长度的最优值未知
缺页频率算法 PFF
– 缺页率? 驻留集?
– 缺页率? 驻留集?
缺页频率算法上次缺页时间 本次缺页时间被访问的页面 u=1
a b
b-a<F 增加该页到驻留集
b-a>F 淘汰所有 u=0的页所有 u=0
……
所有 u=0
局部性过渡期间效果不好
VSWS策略
Variable-interval sampled working set
可变间隔采样的工作集策略
M－采样间隔上限
L－采样间隔下限
Q－采样间隔的缺页量
t>M
t<M但达到 Q
t<L
t>L
扫描 u等待当前时间－上次采样时间＝ t
清除策略
请求式清除
– 成对的读写操作
预约式清除
– 重复写出与页缓冲技术相结合自由页表修改页表成批写多道程序效果
L=S缺页间隔＝缺页处理时间
CPU使用率页面调度设备的使用率为 50％
Clock扫描速度太慢 增加多道程序级别挂起进程的选择
如果要挂起进程，可以选择 ……
– 优先级最低的
– 缺页的
– 最后被激活的
– 驻留集最小的
– 最大的
– 剩余执行窗口最大的
