阅读更多
1 虚拟存储技术
所谓虚拟存储技术是指：当进程运行时，先将其一部分装入内存，另一部分暂留在磁盘，当要执行的指令或访问的数据不在内存时，由操作系统自动完成将它们从磁盘调入内存的工作
虚拟地址空间即为分配给进程的虚拟内存
虚拟地址：是在虚拟内存中指令或数据的位置，该位置可以被访问，仿佛它是内存的一部分
1.1 存储器层次结构
1.2 虚拟内存与存储体系
把内存与磁盘有机地结合起来使用，从而得到一个容量很大的“内存”，即虚存
虚存是对内存的抽象，构建在存储体系之上，由操作系统协调各存储器的使用
虚存提供了一个比物理内存空间大得多的地址空间
1.3 存储保护
- 确保每个进程有独立的地址空间
- 确保进程访问合法的地址范围
- 确保进程的操作是合法的
1.4 虚拟页式
虚拟存储技术 + 页式存储管理方案
→ 虚拟页式存储管理系统
基本思想
- 进程开始运行之前，不是装入全部页面，而是装入一个或零个页面
- 之后，根据进程运行的需要，动态装入其他页面
- 当内存空间已满，而又需要装入新的页面时，则根据某种算法置换内存中的某个页面，以便装入新的页面(以CPU时间和磁盘空间换取昂贵内存空间，这是操作系统中的资源转换技术)
具体有两种方式
- 请求调页（demand paging）
- 预先调页（prepaging）
2 页表及页表项的设计
2.1 页表表项设计
页表由页表项组成
页表项包括
- 页框号（内存块号、物理页面号、页帧号）
- 有效位（驻留位、中断位）：表示该页是在内存还是在磁盘
- 访问位：引用位
- 修改位：此页在内存中是否被修改过
- 保护位：读/可读写
2.2 关于页表
32位虚拟地址空间的页表规模？
- 页面大小为4K；页表项大小为4字节
- 一个进程地址空间有2^20页
- 其页表需要占1024页（页表页）
64位虚拟地址空间
- 页面大小为4K；页表项大小为8字节
- 页表规模： 32,000 TB
页表页在内存中若不连续存放，则需要引入页表页的地址索引表 → 页目录（Page Directory）
2.3 二级页表结构及地址映射
在此结构下，虚地址分为三部分
- 页目录偏移
- 页表偏移
- 页内偏移
查询过程
- 首先从寄存器中获取页目录地址
页目录地址 + 页目录偏移查找页表地址页表地址 + 页表偏移查找页框地址页框地址 + 页内偏移查找物理地址
2.4 CORE I7页表结构
2.5 I386页目录项和页表项
页目录项：页目录由页目录项构成
页表项：页表由页表项构成
- PFN(Page Frame Number)：页框号
- P(Present)：有效位
- A(Accessed)：访问位
- D(Dirty)：修改位
- R/W(Read/Write)：只读/可读写
- U/S(User/Supervisor)：用户/内核
- PWT(Page Write Through)：缓存写策略
- PCD(Page Cache Disable)：禁止缓存
- PS(Page Size)：大页4M
2.6 反转（倒排）页表
待补充
3 地址转换过程及TLB引入
3.1 地址转换过程示意
内存管理单元
地址转换（映射）
3.2 快表
3.2.1 快表TLB的引入
问题
- 页表 → 两次或两次以上的内存访问
- CPU的指令处理速度与内存指令的访问速度差异大，CPU的速度得不到充分利用
如何加快地址映射速度，以改善系统性能？
- 程序访问的局部性原理 → 引入快表(TLB)
3.2.2 快表是什么
TLB — Translation Look-aside Buffers
- 相联存储器（associative memory）
- 在CPU中引入的高速缓存（Cache），可以匹配CPU的处理速率和内存的访问速度
- 一种随机存取型存储器，除连线寻址机制外，还有接线逻辑，能按特定的匹配标志在一个存储周期内对所有的字同时进行比较
快表特点：按内容并行查找
- 保存正在运行进程的页表的子集(部分页表项)
3.2.3 加入快表后的地址转换过程示意
4 页错误
页错误又称页面错误、页故障、页面失效，即地址转换过程中硬件产生的异常
具体原因
- 所访问的虚拟页面没有调入物理内存 → 缺页异常
- 页面访问违反权限（读/写、用户/内核）
- 错误的访问地址 → 访问越界
4.1 缺页异常处理
在地址映射过程中，硬件检查页表时发现所要访问的页面不在内存，则产生该异常——缺页异常。处理过程如下：
- 操作系统执行缺页异常处理程序：获得磁盘地址，启动磁盘，将该页调入内存
- 如果内存中有空闲页框，则分配一个页框，将新调入页装入，并修改页表中相应页表项的有效位及相应的页框号
- 若内存中没有空闲页框，则要置换内存中某一页框；若该页框内容被修改过，则要将其写回磁盘
5 软件相关策略
5.1 驻留集
所谓驻留集，是指在某段时间间隔内，进程要访问的页面集合
那么该给每个进程分配多大的驻留集最佳呢
- 固定分配策略
- 进程创建时确定
- 可以根据进程类型（交互、批处理、应用类）或者基于程序员或系统管理员的需要来确定
- 可变分配策略
- 根据缺页率评估进程局部性表现
- 缺页率高 → 增加页框数
- 缺页率低 → 减少页框数
- 系统开销
5.2 置换问题
置换范围
计划置换页面的集合是局限在产生缺页中断的进程，还是所有进程的页框？
置换策略
在计划置换的页框集合中，选择换出哪一个页框？
5.3 置换范围
局部置换策略：仅在产生本次缺页的进程的驻留集中选择
全局置换策略：将内存中所有未锁定的页框都作为置换的候选
对于可变分配策略的局部置换策略
- 当一个新进程装入内存时，给它分配一定数目的页框，然后填满这些页框
- 当发生一次缺页异常时，从产生缺页异常进程的驻留集中选择一页用于置换
- 不断重新评估进程的页框分配情况，增加或减少分配给它的页框，以提高整体性能
5.4 置换策略
决定置换当前内存中的哪一个页框
所有策略的目标：置换最近最不可能访问的页
根据局部性原理，最近的访问历史和最近将要访问的模式间存在相关性，因此，大多数策略都基于过去的行为来预测将来的行为
注意：置换策略设计得越精致、越复杂，实现的软硬件开销就越大
约束：不能置换被锁定的页框
5.5 页框锁定
为什么要锁定页面？
- 采用虚存技术后：开销 → 使进程运行时间变得不确定
如何实现
- 给每一页框增加一个锁定位
- 通过设置相应的锁定位，不让操作系统将进程使用的页面换出内存，避免产生由交换过程带来的不确定的延迟
- 例如：操作系统核心代码、关键数据结构、I/O缓冲区
5.6 清除策略
清除：从进程的驻留集中收回页框
虚拟页式系统工作的最佳状态：发生缺页异常时，系统中有大量的空闲页框
结论：在系统中保存一定数目的空闲页框供给比使用所有内存并在需要时搜索一个页框有更好的性能
设计一个分页守护进程（paging daemon），多数时间睡眠着，可定期唤醒以检查内存的状态
- 如果空闲页框过少，分页守护进程通过预定的页面置换算法选择页面换出内存
- 如果页面装入内存后被修改过，则将它们写回磁盘。分页守护进程可保证所有的空闲页框是“干净”的
当进程需要使用一个已置换出的页框时，如果该页框还没有被新的内容覆盖，将它从空闲页框集合中移出即可恢复该页面，这里用到了页缓冲技术
- 不丢弃置换出的页，将它们放入两个表之一：如果未被修改，则放到空闲页链表中，如果修改了，则放到修改页链表中
- 被修改的页定期写回磁盘(不是一次只写一个，大大减少I/O操作的数量，从而减少了磁盘访问时间)
- 被置换的页仍然保留在内存中，一旦进程又要访问该页，可以迅速将它加入该进程的驻留集合(代价很小)
6 置换算法
页面置换算法有以下几种
- 最佳算法
- 先进先出
- 第二次机会
- 时钟算法
- 最近未使用
- 最近最少使用
- 最不经常使用
- 老化算法
- 工作集
- 工作集时钟
6.1 最佳页面置换算法
设计思想：置换以后不再需要的或最远的将来才会用到的页面
该置换算法基本不可实现，因为依赖于系统以后的状态，但是可以作为一种标准来衡量其他算法的性能
6.2 先进先出算法
选择在内存中驻留时间最长的页并置换它
实现：页面链表法
6.3 第二次机会算法（SCR）
按照先进先出算法选择某一页面，检查其访问位R，如果为0，则置换该页；如果为1，则给第二次机会，并将访问位置0
6.4 时钟算法
尽管第二次机会算法是一个比较合理的算法，但它经常要在链表中移动页面，既降低了效率又不是很有必要。一个更好的办法是把所有的页面都保存在一个类似钟面的环形链表中，一个表针指向最老的页面
当发生缺页中断时，算法首先检查表针指向的页面
- 如果它的R位是0就淘汰该页面，并把新的页面插入这个位置，然后把表针前移一个位置
- 如果R位是1就清除R位并把表针前移一个位置，重复这个过程直到找到了一个R位为0的页面为止
6.5 最近未使用算法
选择在最近一段时间内未使用过的一页并置换
实现：设置页表表项的两位
- 访问位（R）
- 修改位（M）
- 启动一个进程时，R、M位置0
- R位被定期清零（复位）
发生缺页中断时，操作系统检查R，M：
- 第1类：无访问，无修改
- 第2类：无访问，有修改（R会被定期清零，因此可能出现这种情况）
- 第3类：有访问，无修改
- 第4类：有访问，有修改
最近未使用算法也可以配合时钟算法来实现
- 从指针的当前位置开始，扫描页框缓冲区，选择遇到的第一个页框（r=0；m=0）用于置换(本扫描过程中，对使用位不做任何修改)
- 如果第1步失败，则重新扫描，选择第一个（r=0；m=1）的页框(本次扫描过程中，对每个跳过的页框，将其使用位设置成0)
- 如果第2步失败，指针将回到它的最初位置，并且集合中所有页框的使用位均为0。重复第1步，并且，如果有必要，重复第2步。这样将可以找到供置换的页框
6.6 最近最少使用算法
算法思想：选择最后一次访问时间距离当前时间最长的一页并置换，即置换未使用时间最长的一页
该算法性能接近OPT
实现：
生成时间戳 或 维护一个访问页的栈 → 开销大
6.7 最不经常使用算法
算法思想：选择访问次数最少的页面置换。这是LRU的一种软件解决方案
实现：
- 软件计数器，一页一个，初值为0
- 每次时钟中断时，计数器加R
- 发生缺页中断时，选择计数器值最小的一页置换
6.8 老化算法
算法思想：老化算法是对LRU算法的一种有效近似。每个页面保留一个计数值，计数器在加R前先右移一位，R位加到计数器的最左端。衰减之前计数值的影响，提高本次R位的影响
6.9 工作集算法
影响缺页次数的因素有以下几种
- 页面置换算法
- 页面本身的大小
- 程序的编制方法
- 分配给进程的页框数量
颠簸（Thrashing，抖动）：虚存中，页面在内存与磁盘之间频繁调度，使得调度页面所需的时间比进程实际运行的时间还多，这样导致系统效率急剧下降，这种现象称为颠簸或抖动
6.9.1 页面尺寸问题
确定页面大小对于分页的硬件设计非常重要，而对于操作系统是个可选的参数
要考虑的因素：
- 内部碎片
- 页表长度
- 辅存的物理特性
Intel 80x86/Pentium：4096 或 4M
多种页面尺寸：为有效使用TLB带来灵活性，但给操作系统带来复杂性
6.9.2 分配给进程的页框数和缺页率的关系
6.9.3 工作集模型
基本思想：
- 根据程序的局部性原理，一般情况下，进程在一段时间内总是集中访问一些页面，这些页面称为活跃页面，如果分配给一个进程的物理页面数太少了，使该进程所需的活跃页面不能全部装入内存，则进程在运行过程中将频繁发生中断
- 如果能为进程提供与活跃页面数相等的物理页面数，则可减少缺页中断次数
工作集：一个进程当前正在使用的页框集合
- 工作集W（t，Δ）= 该进程在过去的Δ个虚拟时间单位中访问到的页面的集合
内容取决于三个因素：
- 访页序列特性
- 时刻t
- 工作集窗口长度(Δ)
基本思路：找出一个不在工作集中的页面并置换它
设计：
- 每个页表项中有一个字段：记录该页面最后一次被访问的时间
- 设置一个时间值T
- 判断：根据一个页面的访问时间是否落在“当前时间-T”之前或之中决定其在工作集之外还是之内
实现：扫描所有页表项，执行操作
- 如果一个页面的R位是1，则将该页面的最后一次访问时间设为当前时间，将R位清零
- 如果一个页面的R位是0，则检查该页面的访问时间是否在“当前时间-T”之前
- 如果是，则该页面为被置换的页面
- 如果不是，记录当前所有被扫描过页面的最后访问时间里面的最小值。扫描下一个页面并重复1、2
6.10 小结
| 算法 | 评价 |
|---|---|
| OPT | 不可实现，但可作为基准 |
| NRU | LRU的很粗略的近似 |
| FIFO | 可能置换出重要的页面 |
| Second Chance | 比FIFO有很大的改善 |
| Clock | 实现简单 |
| LRU | 很优秀，但很难实现 |
| NFU | LRU的相对粗略的近似 |
| Aging | 非常近似LRU的有效算法 |
| Working set | 实现起来开销很大 |
7 其他相关技术
7.1 内存文件映射
基本思想：进程通过一个系统调用（mmap）将一个文件（或部分）映射到其虚拟地址空间的一部分，访问这个文件就象访问内存中的一个大数组，而不是对文件进行读写
在多数实现中，在映射共享的页面时不会实际读入页面的内容，而是在访问页面时，页面才会被每次一页的读入，磁盘文件则被当作后备存储
当进程退出或显式地解除文件映射时，所有被修改页面会写回文件
7.2 写时复制技术
基本思想
- 只有读操作时，多个进程可以共享同一份数据
- 有写操作时，才会为该进程生成一份私有的数据。新复制的页面对执行写操作的进程是私有的，对其他共享写时复制页面的进程是不可见的
8 参考
- 《MOOC-操作系统原理-陈向群》