2 内存管理
2.1 逻辑地址和物理地址
背景
- CPU能直接访问的存储仅内存和寄存器
- 内存单元只能看到地址流，不知道其如何产生，分别是什么数据的地址
基地址与界限地址
由于每个进程中仅使用逻辑地址来寻址，需要在PCB中包含这些逻辑地址的基地址和界限地址
- 基地址寄存器：含有最小的合法物理地址
- 界限地址寄存器：指定了范围的大小（scale）
取指的第一步，先取基地址
内存空间保护
通过硬件实现，比较用户模式下产生的地址与寄存器的地址相对大小
当用户试图访问其他进程的内存时，系统将其视作致命错误
逻辑到物理
由MMU的硬件完成，映射方法很多
- 最简单：重定位寄存器，基地址加偏移地址
用户程序看不到真实的物理地址
2.2 分段
分段：将连续的逻辑地址分配到不连续的物理地址空间内；通常用于代码段，数据段这样的划分
程序是一组段的集合，分段的优点是：灵活，可扩展段数据
通过<段名，段偏移>这组有序对来确定段，使用段表来进行二维元组-物理地址映射
2.3 分页
固定分区
孔：一整块可用的内存，可以分配给一个完整的进程
分配方式
- 首次适应：分配首个足够大的孔
- 最优适应：分配最小的足够大的孔；遍历列表，会产生最小剩余孔
- 最差适用：分配最大的孔；遍历列表，产生最大剩余孔
外部碎片：存储空间被分为了大量的小孔
内部碎片：为了避免小孔，进程分配的内存比需要的大，二者之差称为内部碎片
分页：将每个段分为很多页（逻辑page，物理frame）；先分段，再分页
通过页表将page翻译为frame，page和frame的大小是一致的，因此页偏移很好算，减去页码就行
对于逻辑地址为50的内存单元，其位于0page50，对应1frame50
一般而言，一页4K，也就是末12bit地址作为页偏移，前面都是页码
页表存放在内存中，因此进程访问一次内存实际需要访问两次，一次查页表，一次干正事
为了加快，使用高速缓存存储，称为转换表缓冲区（TLB），和Cache很像，硬件实现
2.4 多级页表
页表的开销也很大，一个32bit按字节编址内存，4KB的页表一共有1M条，需要4MB内存来存放页表；根本原因在于很多页是不会用到但必须编址的，如果页表在物理地址内不连续，就会增加查找开销（本来是哈希）
可以用一个表来查询页表，就不用连续分配这个页表
蓝色的空间没有分配，页表的开销减小
内存地址被划分为三块：p1用于索引一级页表，p2索引二级页表，d索引偏移
2.5 虚拟内存
虚拟内存
程序很大，内存放不下；直接放硬盘运行的速度太慢
允许程序大于物理内存，实际内存对用户透明；逻辑内存与物理内存分离，不在物理内存中的数据通过请求调页来实现
请求调页：仅在需要时将磁盘中的页面调出到内存中
有效位：避免读入不使用的页，区分内存/磁盘中的页面，用1bit来表示
- valid，bit=1，在内存中
- invalid，bit=0，不是这个进程的内容，或是但在磁盘中
当访问invalid的页面时，会发生缺页错误，发出请求调页中断
页面的有效访问时间与缺页错误率正比
页面置换
当内存没有空闲帧时，从内存换出一个页面，从磁盘拿入一个页面
实现了逻辑内存和物理内存的分离
步骤如下：
- 选择替换页面
- 将该页面有效位CLR
- 将该页面写入磁盘
- 修改页表和帧表
- 将目标页面从磁盘换入内存
- 将目标页面有效位set
- 缺页错误中断返回，继续用户进程
读入读出两倍的时间，耗时长；可以用修改位（脏位）减小开销：
- 设置一个由硬件管理的脏位
- 当页面被修改时，置位
- 若置位，则一定要写回内存；否则，不需要写回去，直接替换就行
降低一半I/O时间
页面置换算法
- FIFO：维护一个队列
- 最优页面置换：后续最长时间不会使用的页面，仅存在于理论分析中
- LRU：最近最少使用的页面，看前面
- 可以用计数器的方法为每一个页面设置最近使用时间
- 也可以用堆栈的方法将最近使用的页面置于顶端
- 近似LRU算法：硬件资源不能支持完全LRU
- 引用位：被引用的页面set
- 额外引用位：8bit的引用位，包含最近8个时钟周期的页面使用情况，每个时钟周期向右移动1bit，更新MSB；替换时将最小的换出去
- 第二次机会：引用位=0，直接替换；=1，置为0，给第二次机会，选择下一个页面；所哟引用位都是1，就退化为FIFO
Belady现象
使用FIFO算法时，增加物理内存的帧数反而导致缺页率上升；原因在于FIFO总是淘汰最早进入的页面，而某些关键页面就是会更早进入，从而导致了错误替换
系统抖动
一个进程的调页时间大于执行时间，称为系统抖动
原因：CPU看到自己的利用率降低，增加更多进程，每个进程分配到的页面更小，产生更多缺页错误，进一步降低利用率
工作集
一个进程当前正在使用的逻辑页面集合，用二元函数\(W(t,\Delta)\)表示
表示\(\Delta\)时间段内使用过的页面序号，\(|W|\)越小，表面进程的局部性越好