目录
0.前言
1.硬件和控制结构
1.1 局部性原理Locality
1.2 分页Paging
1.2.1 多级页表Multi-level Paging System
1.2.2 反向页表/倒排页表Inverted Page Table
1.2.3 快表Translation Lookaside Buffer(TLB)
1.2.4 页尺寸
1.3 分段Segment
1.4 段页混合式Combined Paging and Segmentation
2.操作系统软件
2.1 读取策略Fetch Policy
2.2 放置策略Placement Policy
2.3 置换算法Replacement Policy
①最佳置换算法Optimal policy(OPT)
②最近最少使用Least Recently Used(LRU)
③先进先出First-in, first-out(FIFO)
④时钟置换算法Clock Policy
⑤增强二次机会法Clock Policy Using Use Bit and Modified Bit
2.4 驻留集管理
①Fixed Allocation，Local Scope(固定分配，局部置换)
②Variable Allocation，Global Scope(可变分配，全局置换)
③Variable Allocation，Local Scope(可变分配，局部置换)
2.5 清除策略Cleaning Policy
2.6 加载控制Load Control
0.前言
本系列文章旨在记录操作系统的知识点，可用于期末复习，笔者理解尚浅，文中不正之处静待批正。加粗高亮部分为重点。
1.硬件和控制结构
虚拟内存的定义：
一种存储分配方案，其中辅存可以像主存的一部分一样被寻址。程序用于引用内存的地址与内存系统用于标识物理存储位置的地址不同，程序生成的地址会自动转换为相应的机器地址。虚拟存储的大小受计算机系统的寻址方案和可用的辅存数量限制，而不是受主存的实际数量限制。
- 内存+部分辅存
- 逻辑和物理地址自动转换
- 尺寸不受内存限制，受计算机寻址和可用辅存限制
当一个地址不在内存中时
- 会产生缺页中断(page default)
- 会被放入阻塞态
- 访问I/O，将逻辑地址压入内存
- 回到就绪态
虚拟内存的优缺点
优点
- 主存中可有多个进程
- 解除了用户于与主存之间的紧密约束(支持大于主存的进程)
缺点：会带来系统抖动(Thrashing)，在进程切换时容易产生
1.1 局部性原理Locality
1.2 分页Paging
每个进程都有一个页表
PTE(page table entry 页表项)包含内存中相应页的帧号
两个控制位：
- 存在位(Present Bit)：表明页是否在主存，若不在主存的地址被访问会产生缺页中断(存在位有效帧号才有效)
- 修改位(Modified Bit)：表明当分页载入主存时是否被修改；若被修改，则当其被换出时须写进硬盘
分页的地址转换系统：
地址转换的过程：首先，逻辑地址由页号和偏移量组成，系统中设有一个页表寄存器(PTR)，它存储了页表在内存中的起始地址F和页表长度M，判断页号是否在合理范围内，如果页号大于页表长度M，则会产生越界中断；若页号合理，则将页号加上起始地址F，得到页表项地址，然后查询对应页表项，得到内存块号或帧号，最后用帧号和偏移量得到物理地址，找到主存中的目标单元。
例：假设物理内存大小为1G, 共有32个进程，每个进程为4G，每页大小为4k， 每个页表项为4字节，那么存储所有页表需要多少空间？
4G=2^32 4k=2^12
4G/4K=2^20 2^20*4=4MB
4MB*32=128MB
内存占有率：128MB/1GB=12.5%
一次对内存的访问需要访问两次内存：
- 读内存中的页表项
- 读物理地址中需要的数据
- 页表大小与虚拟地址空间成比例增加，可能会很大
- 页表自身在虚存
- 部分页表在主存
1.2.1 多级页表Multi-level Paging System
多级页表地址转换系统：
转换过程：与单级页表类似，只不过多一个根页表，存储二级页表的起始地址。先访问根页表，再访问二级页表，最后找到物理地址。
两级页表的访问，需要访问三次内存：
- 读内存中的根页表
- 读内存中的二级页表
- 读物理地址中的数据
判断需要几级页表：根页表要刚好装下一帧
- 判断进程需要多少页表项X
- 判断每页可以存多少页表项Y
- 计算需要几级页表L=[X/Y]向上取整
1.2.2 反向页表/倒排页表Inverted Page Table
进程号(PID) + 虚拟页号(VPN) + 页内偏移(offset)---> 物理页框(PPN) + 页内偏移(offset)
线性反向页表：表项由三部分组成，进程ID(PID)，虚拟页号(VPN)，信息位(INFO)。(必须包含进程ID)
为了加快地址转换速度，可以在线性转换表前增加一层散列表。散列表的输入是PID和VPN，输出是倒排页表的索引。
散列倒排页表的PTE：页号+进程ID+控制位+链指针(运用哈希函数计算页号，输出指向倒排表)
地址转换系统：
- 虚拟地址的页码部分被映射为哈希值
- 哈希值指向反向页表
多级页表和倒排页表都是为了解决页表项占用过多内存的问题。
1.2.3 快表Translation Lookaside Buffer(TLB)
快表的思想：缓存页表项，由特殊硬件实现，加速地址变换的过程
快表的地址转换系统：
转换过程：首先，根据页号查找快表中是否有对应页表项的缓存(最近使用过的页表项会放入快表)，若命中，则不用访问内存直接找到对应的帧号，得到物理地址；若未命中，则需要查询内存中的页表，从而得到帧号，同时要更新TLB。如果页表不在主存中，则产生缺页中断，需要访问I/O，将页面从硬盘(辅存)中转移至内存中，同时会直接加入TLB，最后访问TLB即可。如果内存已满则使用置换算法；若未满则更新页表，重新进行判断。
TLB运用的是关联映射，而普通的页表使用直接映射
若TLB未命中则需访问内存两次，命中则只用一次
1.2.4 页尺寸
- 页越小，内部碎片越少
- 页越小，每个进程需要的页越多，进程的页表就越大
- 页表越大，占用虚存越多，传递效率越高(DMA传递大块效率高)
- 正常情况下，页越小，缺页率越低
- 页越小，进程在内存中的页越多
- 页尺寸与页数量共同影响缺页率和并发度
- 常见页大小：4kb
1.3 分段Segment
分段的大小可能不相等，STE(段表项)也有存在位和修改位，还包含了段长和段基址
分段的地址转换系统(两次访问内存)：
转换过程：段表寄存器(STP)存储了段表起始地址F和段表长度M。首先，判断段号是否越界，若段号大于段表长度，则产生越界中断。然后将段号加上段表起始地址找到对应段表项，检查偏移量是否大于段长，若大于则产生越界中断，最后将段基址加上偏移量得到物理地址。
分段的优势：
- 简化不断增长的数据结构的处理
- 允许程序独立的修改和编译
- 有助于进程间共享
- 有利于保护
分页与分段的区别：
- 分页：对用户不可见，大小固定，对用户是一维
- 分段：对用户可见，大小不固定，对用户是二维
1.4 段页混合式Combined Paging and Segmentation
- 分页对程序员透明
- 分段对程序员是可见的
- 每个分段都分成固定大小的页面
- 每个进程都有一个段表和多个段
- 每个段都有一个页表
段页式的地址转换系统(三次访问内存)：
需要注意的是通过段表去索引页表，并且仍需要进行越界判断
- 段号的位数决定每个进程最多可分为几个段
- 页号的位数决定了每个段最大有多少页
- 页内偏移量决定页面大小
2.操作系统软件
2.1 读取策略Fetch Policy
目的：决定页面何时被换入内存
- 请求分页式Demand paging：需要换入时才换入(刚开始缺页率较高，运行时调入)
- 预约分页式Prepaging：首次调入加载超过需求量的分页数(运行前调入)
2.2 放置策略Placement Policy
决定进程片段在内存中的驻留位置，对NUMA处理器影响大(对分段影响大)
2.3 置换算法Replacement Policy
Frame Locking帧锁定：被锁定的帧不能被替换(lock bit)
置换的原则：
- 简单高效
- 置换最近访问可能性最小的页
- 基于过去的行为预测未来的行为
①最佳置换算法Optimal policy(OPT)
原理：选择以后用不使用或最长时间不被访问的页面
假想的算法，无法实现，主要用于评估其他算法
②最近最少使用Least Recently Used(LRU)
原理：选择最近最久未使用的页面(性能好，但开销大)
③先进先出First-in, first-out(FIFO)
原理：选择最早进入内存的页面(类似队列或循环缓冲区)(性能差)
缺点：会发生Belady现象，当分配的物理块数增加，缺页次数不减反增
④时钟置换算法Clock Policy
原理：引入使用位(use bit)，将内存中的页面链接成循环队列
- 当页面首次载入内存，使用位置为1
- 当页面被访问，使用位置为1
- 当内存已满，需要进行页面替换时，检查页面的使用位，若为0，则换出，指针向后移一位；若为1，则将该页使用位置为0，继续检查下一页面，首个使用位为0的页会被替换(最多经过两轮扫描)
- 只有缺页才移动指针，命中只修改使用位，不移动指针
效率：OPT>LRU>ClOCK>FIFO
⑤增强二次机会法Clock Policy Using Use Bit and Modified Bit
原理：选择未被修改过的页面(开销小，性能不错)
页缓冲Page Buffering：
减少时间开销，维护一个空闲帧缓冲池，被替换的页添加到下面两个链表之一：
- 空闲页链表(Free page)：页面未被修改
- 修改页链表(Modified pages)：被修改的页以集群(in cluster)方式写入
2.4 驻留集管理
- Working Set工作集：进程P正在访问的页面集合称为它的工作集w(k,t)，表示在任意时刻t，前k次访问内存的页面的集合
- Resident Set驻留集：驻留在OS分配的N个页帧物理内存中的页，如下时刻7，驻留集为2，4，5
- 驻留集大小必须大于工作集大小，否则将频繁缺页
驻留集大小分为固定分配(Fixed-allocation)和可变分配(Variable-allocation)
替换范围：
- 局部置换Local Replace Policy：发生缺页时只能置换进程自己的物理块(只能置换驻留集中的)
- 全局置换Global Replace Policy：在主存中所有未被上锁的页均可被置换(全局置换不可能采用固定分配)
①Fixed Allocation，Local Scope(固定分配，局部置换)
- 事先确定给进程分配多少页
- 如果太少，导致高缺页率
- 如果分配太多，内存中驻留的程序会过少
②Variable Allocation，Global Scope(可变分配，全局置换)
- 易实现
- 利用页面缓冲中的空闲链表，只要缺页就给分配新的物理块
- 只要前K次不访问就换出，在K次内访问过的页驻留
③Variable Allocation，Local Scope(可变分配，局部置换)
- 每隔一段时间要评估是否要增加或减少分配
- 要根据发生缺页的频率来动态增加或减少进程的物理块
Page fault frequency(PFF)缺页率的影响因素：
- 置换算法
- 程序局部性
- Page size
- 分配给进程的Frame数量
缺页发生的间隔等于一个缺页中断服务的时间时，系统响应效率较好(缺页率越大，运行越慢)
2.5 清除策略Cleaning Policy
- 请求式清除Demand cleaning：只有被选择替换时才会被写出(内存较满时才用)
- 预约式清除Precleaning：在被需求之前就写出
2.6 加载控制Load Control
确定驻留在主存中的进程数：太多进程会导致抖动，太少会使所有进程阻塞
进程挂起优先级：
- 最低优先级进程
- 页错误进程
- 最后被激活的进程
- 驻留集最小的进程
- 占用空间最大的进程
- 具有最大剩余执行窗口的进程
