操作系统内存管理
一、内存管理策略
1. 背景
基本硬件(基地址与界限地址)
地址绑定(编译时、加载时、运行时)
逻辑地址空间与物理地址空间
动态加载
动态链接与共享库(与静态库对比)
2. 交换(内存与磁盘间)
维护着一个可运行进程就绪队列,进行内存与磁盘间线程的载入与存出。
3. 连续内存分配
内存分区之 可变分区 的思想,将内存分成一个个孔(hole),使用一张表维护 hole 的使用情况。
存在碎片问题(分为外碎片与内碎片)
- 首次适应– 首个足够大的孔(50% 规则,描述碎片多)
- 最优适应– 最小合适的孔
- 最差适应– 最大孔
外部碎片大,解决思路有 紧缩 与 分页、分段(运行物理地址不连续的策略)
4. 分段
将内存分为不同长度的段,维护分段硬件支持段表
< 段名称 s,段偏移 d >
5. 分页
物理内存分为固定大小的块,称为帧。逻辑内存也分为同样大小的块,称为页。
< 页码 p,页偏移 > 与对应的页表
TLB 带 Hash 页表 – 转换表缓冲区
保护机制与共享页
6. 页表结构补充
分层页表
哈希页表(数组 + 链表)
倒置页表
二、虚拟内存管理
1. 背景
使用虚拟内存来逻辑内存容量 – 分配出去但未使用的内存空间,通过伪分配实现扩容。
2. 请求调页
概念:仅在需要时,才加载页面。
调页程序 – 惰性变换器实现
一般缺页错误的处理很简单:
- 检查这个进程的内部表,以确认该引用是有效的还是无效的内存访问。
- 如果引用无效,那么终止进程。如果引用有效但是没有调入内存,那么现在就调入。
- 找到一个空闲帧。
- 调度一个磁盘操作,以将所需页面读到刚分配的帧。
- 磁盘读取完成,修改进程内部表和页表。以指示该页现在处于内存中。
- 重新启动被陷入中断的指令。该进程能访问所需要的页面,就好像原来他就在内存中一样。
缺页处理的时间花费主要体现在:处理缺页中断、读入页面、重新启动进程
3. 写时复制(父子进程间)
4. 页面置换
当用户进程在执行时,可能发生缺页错误。操作系统确定所需要页面的磁盘位置,但是却发现内存上没有空闲的帧。所有内存都在使用。此时,它会选择交换出一个进程,以释放它在所有帧并降低多道程序。
在没有空闲帧的情况下,那么就要查找当前不在使用的一个帧,并释放它,牺牲帧 ,他被换出到交换空间,并修改它的页表。可以看到当没有空闲帧的情况下,需要两个页面传输(一个传入,一个传出)。这种情况世界加倍了缺页错误处理时间,并增加了有效的访问时间。为了减少置换的时间,系统提供了一个 修改位,两者的关联采用硬件。每当一个页面内的任何字节被写入时,它的页面修改位会由硬件来设置,以表示该页面被修改过。当要选择一个页面置换时,它会先看这个页面或者帧有没有被修改过,如果没有修改过就不用将它换出,直接进行换入,将它的空间覆盖。
页面置换算法
- FIFO 先进先出
- OPT/MIN 最优置换
- LRU 最近最少使用
-
近似 LRU
- 额外引用位算法(多位标志位)
- 第二次机会算法(1 位标志位)
- 增强型第二次机会算法 - 分类(元组分类出最近使用与需要写回)
-
基于计数
- LFU 最不经常使用
-
MFU 最经常使用
搭配上 页面缓冲算法– 最近被淘汰的页面被放置在高速磁盘区,减少淘汰错误页面下次换回的代价
5. 帧分配
分配算法 –平均与比例
全局分配与局部分配(区别,是否面向所有进程的内存暑假页)
6. 系统抖动
频繁发生页面置换