虚拟内存
硬件和控制结构
- 运行时访问地址动态转换为物理地址——一个进程可被换入或换出内存，在执行的不同时刻占据内存的不同区域
- 一个进程可以被划分为多个块（页或段），这些块不需要连续地位于内存中
- 在一个进程的执行过程中，该进程不需要所有的页或段在内存中
常驻集（resident set）：进程执行的任何时候都在内存的部分
所需地址不在内存中：发生缺页中断→OS阻塞进程（要想继续执行这个进程，OS必须把这个逻辑地址读入内存）
- 发出磁盘I/O读请求
- 在这个过程中可以调度另一个进程
- 从磁盘读入所需的块后，产生一个I/O中断，原来被阻塞的进程置为就绪态
前面要产生中断效率较低，提高系统利用率的方法有：
- 在内存中保留多个进程：只载入每个进程的部分，在任何时刻至少有一个处于就绪态
- 进程可以比内存的全部空间还大
对于第二种方法，增加一个虚拟内存（通常在磁盘上）
- 支持更有效的系统并发度
- 解除用户和进程之间没有必要的紧密约束
局部性和虚拟内存
局部性原理：程序和数据访问的集簇倾向
基于局部性原理 在一个短时间片内，只需要一部分进程片段，可以猜测最近可能会访问的块，表明虚存方案可行
系统抖动（thrashing）：一个块正好在将要用到之前换出，OS不得不很快地取回它
分页
每个进程有自己的页表，每个页表项（page table entry）包含与内存中的页框相对应的页框号
P位：所对应的页是否在内存中 M位：相应页的内容从上次装入内存到现在是否已改变
未改变时，则在需要换出该页（写入磁盘）时，无需用页框中的内容更新该页
分页的地址转换系统
页表太大时会占用太多主存，因此大多数页表存储在虚存中，部分页表存在主存中
32位地址的两级页表方案
虚拟地址前10位检索根页表，中间10位检索用户页表项页
前面的页表缺点是：页表大小与虚拟地址空间大小成正比；故采用反向页表（inverted page table），将虚拟地址中的页号用一个简单的散列函数映射到为hash值，指向反向页表；这样页表的大小只与实存相关
反向页表包括
- 页号：虚拟地址的页号
- 进程标志符
- 控制位
- 链指针
原则上每次虚存访问会导致2次物理内存访问：一次取页表项，一次取数据（内存访问时间加倍）
为克服这个问题，为页表项使用一个特殊的高速缓存称为TLB，包含有最近用过的页表项
给一个虚拟地址后的步骤
- 检查TLB，命中则得到页框号并形成实地址；若未命中则用页号去检索进程的页表
- 检查页是否在内存中，不在产生缺页错误；在，从页表中得到页框号并形成实地址，同时更新TLB（包含这个新页表项）
页尺寸/大小
- 页越小，内部碎片越少
- 页越小，每个进程需要的页数量越多，页表更大（对大程序来说，部分页表在虚存中而非内存中）
图a解释
页尺寸小时，每个进程在内存中有较多的页，一段时间后内存中的页都包含有最近访问的部分，缺页率较低
页尺寸增加时，每页包含的单元和任何一个最近访问过的单元越来越远，局部性原理被削弱，缺页率开始增长
当页尺寸接近整个进程大小时，缺页率下降
图b解释
缺页率还取决于分配给一个进程的页框的数量，越多缺页率越低
分段
段的大小不等且动态分配，内存访问以段号和偏移量的形式组成地址
优点：
- 简化了对不断增长的数据结构的处理
- 允许程序独立地改变或重新编译
- 有助于进程间的共享
- 有助于保护
每个进程有自己的段表，每个段表包含段在内存中的起始地址和段的长度，也有存在位和修改位
段页式
- 分页对程序员是透明的，消除了外部碎片
- 分段对程序员是可见的，具有分段的优点
- 段页式每段分为固定大小的页，每个进程有一个段表和多个页表，每个段有一个页表
OS软件
读取策略
读取策略决定某页何时取入内存，常用的方法是请求分页式（demand paging）和预先分页式（prepaging）
请求分页式：只有当访问到某页的一个单元时才将该页取入内存
预先分页式：读取的页并非缺页中断请求的页，利用了大多数辅存设备有寻道时间和合理的延迟的特性
放置策略
放置策略决定一个进程块驻留在实存的什么位置
置换策略
置换策略决定置换当前内存中的哪一页，目标是移出最近最不可能访问的页（预测将来行为）
页框锁定（frame locking）：一个页框被锁定时，当前保存在该页框中的页不能被置换
eg：OS内核、重要控制结构、I/O缓冲区
基本算法
- OPT（optimal，最佳）：选择置换下次访问距当前时间最长的那些页，导致的缺页中断最少，但要求OS必须知道将来发生的事，不可能实现
- LRU（least recently used，最近最少使用）：置换内存中最长时间未被引用的页（也是最近最不可能访问到的页），难以实现，加了时间戳后开销很大
- FIFO（first in first out，先进先出）：把分配给进程的页框视为一个循环缓冲区，并按循环方式移动页，只需要一个指针，实现简单，隐含逻辑是置换驻留在内存中时间最长的页（但通常推断错误，需要反复换入换出某些页）
- Clock（时钟策略）：为每个页框关联一个使用位（use bit）的附加位。当某页首次装入内存时，使用位置1；该页随后被访问时，使用位也会置1；当需要置换页时，第一个遇到的页框使用位为0的被置换；在搜寻置换的页过程中，每个使用位为1的被置为0
（星号表示使用位为1）
在时钟策略中考虑修改位（m），与使用位（u）一起有四种情况：
- u=0，m=0
- u=1，m=0
- u=0，m=1
- u=1，m=1
修改算法为：
- 从指针当前位置出发，扫描页框缓冲区，扫描过程中不对使用位做修改，选择遇到的第一个页框u=m=0的用于置换
- 若第一步失败，重新扫描，查找u=0，m=1的页框，选择第一个遇到的用于置换
- 若第二步失败，指针回到最初位置，，所有页框使用位置0，重复第一步
页缓冲
使用FIFO的置换算法时，FIFO存在的问题是置换一个被修改过的页，代价比置换未被修改的页的代价要大，因为前者需要写回辅存
故采用页缓冲：不丢弃置换出的页，而是分配到：
- 空闲页链表：未被修改
- 修改页链表：已被修改
驻留集管理
对于分页式虚存，准备执行时不需要也没必要把一个进程的所有页都读入内存，因此OS必须决定读取多少页，并分配相应的内存空间
- 固定分配策略：为一个进程分配固定数量的页框
- 可变分配策略：允许分配给一个进程的页框在该进程的生命周期中不断的发生变化
置换范围
- 局部置换：仅在产生这次缺页的进程的驻留页中选择
- 全局置换：把内存中所有未被锁定的页都作为置换的候选页
三种驻留集管理方案
- 固定分配+局部置换：事先确定分配给进程的总页框数，分配过少缺页率很高，分配过多内存中只能又很少的几个程序
- 可变分配+全局置换：最容易实现，被很多OS采用
- 可变分配+局部置换：
清除策略
清除策略用于确定何时将已修改的一页写回辅存
- 请求式清除：只有当一页被选择用于置换时才被写回辅存
- 预约式清除：将已修改的多页在需要它们所占据的页框之前成批写回辅存
加载控制
- 决定驻留在内存中的进程数目
- 太少，所有进程都处于阻塞态的概率较大，用于时间增加
- 太多，导致系统抖动
