虚拟内存管理
虚拟内存的基本概念
虚拟内存是计算机系统内存管理的一种工作。它使得应用程序认为它拥有连续的可用的内存(一个连续完整的地址空间),而实际上,它通常是被分隔成多个物理内存碎片,还有部分暂时存储在外部磁盘存储器上,在需要时进行数据交换。
传统存储管理方式的特征、缺点
局部性原理
虚拟内存的定义和特征
如何实现虚拟内存工作
小结
请求分页管理方式
页表机制
缺页中断机构
地址变换机构
关于第5点
在具有快表机构的请求分页系统中,访问一个逻辑地址时,若发生缺页,则地址变换步骤是: 查快表(未命中)——查慢表(发现未调入内存)——调页(调入的页面对应的表项会直接加入快表)——查快表(命中)——访问目标内存单元
小结
页面置换算法
最佳置换算法(OPT)
最佳置换算法可以保证最低的缺页率,但实际上,只有在进程执行的过程中才能知道接下来会访问到的是哪个页面。操作系统无法提前预判页面访问序列。因此,最佳置换算法是无法实现的。
先进先出算法(FIFO)
最近最久未使用置换算法(LRU)
LRU淘汰的是最早被使用的Cache,算法可以分为两种实现:
A.时间戳
硬件记录最近一次访问时间,每次淘汰遍历求最早访问的Cache。
B.链表
Algorithm 4th:著名的前移编码策略,假设最近访问过的元素很有可能再次访问,因此可以用于缓存、数据压缩等许多场景。
这里将所有可能被淘汰的Cache用一张线性链表存储,当查询时,每次被查询到的Cache节点将会被移除出链表并且插入表头。如此一来,链表头将会是最新被访问的数据,而链表尾则会被淘汰。
这样一来,淘汰最早访问的Cache则非常方便,代价则是需要链表的结构是可修改的。
在硬件层,这两种实现都具有巨大的开销,因此难以用于实践。
时钟置换算法(CLOCK)
LRU->NRU: 对于Cache来说,能找到最早访问的固然好,但是宽容一点,不是最早,但是也很早被访问的被淘汰问题也不大,只要不淘汰最近被访问的破坏locality就好了。而这种近似,是必然存在的对现实的妥协,也是工业界必不可少的生存智慧。
改进型的时钟置换算法
需要扫描4轮的只有一种情况, 都是(1, 1)
小结
页面分配策略
驻留集
指请求分页存储管理中给进程分配的物理块的集合。 在采用了虚拟存储工作的系统中,驻留集大小一般小于进程的总大小。
若驻留集太小,会导致缺页频繁,系统要花大量的时间来处理缺页,实际用于进程推进的时间很少;
驻留集太大,又会导致多道程序并发度下降,资源利用率降低。所以应该选择一个合适的驻留集大小。
页面分配、置换策略
固定分配:操作系统为每个进程分配一组固定数目的物理块,在进程运行期间不再改变。即,驻留集大小不变
可变分配:先为每个进程分配一定数目的物理块,在进程运行期间,可根据情况做适当的增加或减少。 即,驻留集大小可变
局部置换:发生缺页时只能选进程自己的物理块进行置换。
全局置换:可以将操作系统保留的空闲物理块分配给缺页进程,也可以将别的进程持有的物理块置换到外存,再分配给缺页进程。
局部置换 | 全局置换 | |
---|---|---|
固定分配 | √ | - |
可变分配 | √ | √ |
全局置换意味着一个进程拥有的物理块数量必然会改变,因此不可能是固定分配
固定分配局部置换
可变分配全局置换
系统会锁定一些页面,这些页面中的内容不能置换出外存(如:重要的内核数据可以设为“锁定”)