兰斯小窝

Appearance

ch9 虚拟内存 ​

9.1 背景 ​

  • 引言：之前学的分段、分页等内存管理方案都是在作业执行前就将作业全部装入内存，直到作业结束才释放，但是一些数据在作业运行时并不一定会用到 (如异常处理)。之前的存储管理方法浪费内存空间、降低了内存利用率、降低了系统并发度、减少了系统吞吐量、增加了I/O时间。
  1. 局部性原理
    • 时间局部性：若程序的某条指令被执行（或数据被访问），则不久后他可能被再次执行
    • 空间局部性：一旦程序访问了某个存储单元，那么它附近的存储单元也将被访问（数组）
  2. 虚拟内存（虚拟存储器）
    1. 定义：仅仅把作业的一部分装入内存即可执行，具有请求调入功能和置换功能，能在逻辑上对内存空间加以扩充的一种存储器系统
    2. 思想：根据局部性原理，我们只需要将当前要执行的那部分页或段先放入内存执行，其他的先放在磁盘。若程序想要访问的页（或段）没在内存中（或称缺页/缺段），操作系统调用请求调页（或段）功能将所要访问的放入内存。若此时内存已满，则需要利用置换功能将内存中暂时不用的页（段）调出内存，将新的页（段）调入内存。
    3. 优点：使得一个大程序可以在小内存中运行；用户在一个虚拟内存中变成，使得编程不再受内存容量的限制；内存可以装入更多程序并发执行；提高系统的并发度和吞吐量，减少了I/O时间
    4. 进程的虚拟内存你空间是如何在内存中存放的（左图）
    5. 共享库：通过将共享对象映射到一个虚拟地址空间，系统库可以被多个进程共享（右图） alt text

9.2 按需调页（Demand Paging，请求页式） ​

  1. 定义：调用程序时在需要时才调入相应的页，使用懒惰交换（只有在需要页时才调入）
  2. 优点：I/O时间低，所需内存减少，更快响应，并发度更高
  3. 硬件支持：
    1. 页表：需要设置valid/invalid位（标明该页是否在内存中），valid：该页号有效，在内存中；invalid：该页号无效（不在该进程中）或有效但不在内存中
    2. 次级存储器：用于保存不在内存中的项，通常为快速磁盘，常称为交换设备，用于交换的这部分磁盘空间叫交换空间（swap space）
  4. 页面错误（page fault，也成为页面失效或缺页中断）
    1. 定义：所需页不在内存中（标志位为invalid），引发页面错误
    2. 执行：页面发生错误以后，系统对比进程页表和系统页表确定该页是否合法（是否在进程内），若非法则终止，若合法则找到一个空闲帧，调用一个磁盘操作将所需页放入该空闲帧中并修改进程内部表和页表（其中标志位由invalide变为valid），重启当前指令 alt text
    3. 缺页中断和一般中断的区别：普通中断是在CPU完成对该指令的执行后检查和处理中断，而缺页中断时在指令执行期间发现所需指令或数据不在内存时产生和处理的
    4. 重启指令有的时候并不可行：相互重叠的区域中进性块移动指令
      该指令将虚框内的数据移动到 Page n 中，由于虚框跨越两个页面，若指令开始执行时第n+1页不在内存，当将虚框内第 n+1 页中的数据移动到第n 页时，产生缺页中断，当将第n+1页装入到主存后，虚框中第n 页的内容已被修改，重启指令重新进行传送，将导致错误; (复制的是已经修改过的数据) 如下图所示 alt text
  5. 纯粹按需调页（pure demand paging） 所有的页都不在内存中就开始执行该进程，会一直产生缺页中断直到所需的页均在内存中
  6. 性能
    • 缺页中断率p越接近0性能越高
    • 有效访问时间（effective access time）=（1-p）内存访问时间+p平均页错误处理时间
    • 页错误处理时间包括处理页错误中断，页调入、调出时间，重启进程时间等

9.3 写时复制（copy on write，COW） ​

  1. 定义：允许父子进程在初始时共享同一页面，当任何一个进程对页进行写操作时创建一个共享页的副本 alt textalt text
  2. 分配空闲帧 操作系统提供空闲缓冲池，当需要复制时从中取出一个空闲帧进行写入。操作系统采用按需填零（空闲帧在分配前先填0来消除之前的内容）技术分配这些空闲帧

9.4 页面置换（page replacement） ​

  1. 定义：内存已满，当前需求的页无法放入内存，需要把内存中的某个页置换出去形成空闲帧才能放入
  2. 基本页置换
    1. 基本页置换下的页错误处理程序如下：查找空闲帧，若找到则使用；若未找到，则使用页面替换算法来选择一个“牺牲”帧（victim frame），将“牺牲”帧的内容写入磁盘，改变帧表和页表；将所需页写入空闲帧，改变页表和帧表；重启用户进程
    2. 优化：加入修改位（modify bit）或脏位（dirty bit）：当无空闲帧时页错误处理程序需要两次页传输，加入修改位后，当某页被修改后该页的修改位被修改，若该页被替换则需要写回磁盘，两次页传输。若未修改则不需要写回，所需页直接覆盖原数据即可，这样就只需要一次页传输，降低了传输时间
    3. 要实现按需调页，必须开发帧分配算法和页置换算法。
    4. 最小页错误率算法：用于评价页置换算法（帧分配算法也适用）
    • 思想：根据特定内存引用序列，执行某个置换算法，得到错误率。内存引用序列叫做引用串
  3. FIFO页替换（First In First Out，FIFO page replacement）
    1. 思想：最先到的的页会首先作为“牺牲”页
    2. 实现：系统维护一个按照位页面分配物理帧的顺序排序的先进先出队列，后分配的总放在队尾，最先置换队首页
    3. 示例 alt text
    4. 评价
      1. 优点：容易理解与实现
      2. 缺点：性能不好，可能置换出去的时很久以前初始化并且一直在用的变量，存在Belady现象。
  4. 最优替换（Optimal replacement，OPT）
    1. 思想：进行页置换时选择未来最长时间不会用到的页作为“牺牲”页
    2. 实现：因为很难知道未来用哪些页，所以很难实现
    3. 示例 alt text
    4. 评价
      1. 优点：顾名思义它是最优的页置换算法，最小的页面错误率
      2. 缺点：由于需要知道未来的情况，所以难以实现。一般用来评估其他算法。
  5. 最近未使用页（Least Recently Used，LRU）
    1. 思想：根据时间局部性原则，最近访问到的页面近期也会被访问，而最近未被访问的页面近期也不会被访问，所以可以优先置换掉最近最少使用的页
    2. 实现
      1. 计数器：为每个页表关联一个时间域，为CPU增加一个逻辑时钟或者计数器，每次内存引用计数器就加一，始终计数器内容复制到相应的页所对应的页表项的使用时间域中。每次指数按使用时间最小的页（最早使用的页）。此方法需要搜索页表查找时间最小的页，并动态维护页表使用的时间域，必须考虑钟表溢出
      2. 使用页码栈，每次引用一个页就把相应的页放入栈顶，在栈低选择“牺牲”页，可以使用双向链表实现
    3. 示例 alt textalt text
    4. 评价
      1. 优点：和最优置换一样，都没有Belady异常（他们属于同一种算法——栈算法）。效率较高，是一种经常被使用的页置换算法
      2. 缺点：需要硬件的支持（计数器，时钟等）
  6. 近似LRU置换（Approximate LRU，ALRU）
    • 很少有系统可以提供足够的硬件来支持真正的LRU算法，但是LRU总体效率比较高，所以可以用近似LRU置换
    1. 思想：给每个页表项增加引用位，每次引用该表时引用位被置数。根据引用位老进一步选择“牺牲”者
    2. 分类
      1. 附加引用位算法 alt text
      2. 二次机会算法：基础算法时FIFO，且只有一个引用位。要选择“牺牲”页的时候，检测引用位，若为1则将其置0，并将它的到达时间置位当前，若为0则替换出去
        • 实现方法：利用循环队列，指针指向下次要置换的页。要寻找“牺牲”页时，指针向前移动时他将引用位为1的置为0，直到找到引用位为0的页将其置换出去，新页插入该位置
      3. 增强二次机会算法：增加引用位和修改位并将其当作有序对来考虑，即(引用位,修改位)
        • （0，0）：最佳替换
        • （0，1）：该页修改过，所以若要之换掉需要将他回写
        • （1，0）：可能会被再次引用
        • （1，1）：可能会被再次引用，若被置换需要将其回写
      • 置换方法：可使用时钟算法，检查所指页属于哪种类型，置换最低级别的页。与时钟算法的主要区别是在于给已经修改过的页更高的优先级，从而降低所需I/O次数
  7. 基于计数的页置换
    1. 思想：给每个页保留一个用于记录其引用次数的计数器
    2. 分类：
      1. 最不经常使用页置换算法(Least Frequently Used，LFU)
        • 思想：计数小的是访问次数少的，应该予以淘汰，故置换计数最小的页
        • 问题：一个页在进程开始时使用很多，但之后不再使用，但由于开始使用次数很多导致计数很大，故之后也会在内存中
        • 优化：定时器对计数器右移一位形成指数衰减的平均使用次
      2. 最常使用页置换算法（Most Frequently Used，MFU）
        • 思想：访问次数少的可能是刚装入内存的，而访问次数多的可能是装入内存时间较长，应该予以淘汰，故置换掉计数最大的页
  8. 页缓冲算法
    1. 思想：系统维护一个空闲缓冲池，当有页面错误时所需页直接从池中选择一个帧来写入，使得进程尽可能快的被重启，而此算法也会选择“牺牲”页，将该帧回写后放入池中备用
    2. 扩展
      1. 当调页设备空闲时选择一个被改写过的页写回到磁盘上，并更新其修改位
      2. 保留一个空闲帧池，但是这些帧所对应的页号要记住，由于这些帧的内容未被修改，所以当再次需要这些页的时候可以直接从池中取出包含所需页的帧

9.5 帧分配 ​

  • 帧的最少数量：分配给进程的帧的最少数量是由活动体系结构决定的，最大数量是由物理内存决定的
  • 帧分配算法：
    1. 平均分配：将n个帧分配给m个进程，每个进程分配到（n/m）个帧（向下取整），例如93个帧分配给5个进程每个进程分到18个帧，剩余三个放入空闲帧缓冲池中。
    2. 比例分配：按照进程的虚拟内存大小或优先级大小或两者结合的标准按比例分配帧
    3. 全局替换和局部替换：
      1. 全局置换：
        • 特点：进程可以从所有帧中选择一个置换帧，不管这个帧是否已经分派给了别的进程
        • 缺点：进程无法控制其页错误率
        • 优点：进程可以利用其他进程不常用的内存，所以系统吞吐量等大，更为常用
      2. 局部替换：进程只能从分配给自己的帧中选择置换帧
    4. 优先级分配：当一个进程出现页面错误时：
      1. 选择一个已分配给自己的帧作为置换帧
      2. 从优先级比它低的进程中选择置换帧

9.6 抖动（Thrashing，也成为颠簸） ​

  • 定义：进程没有“足够”的帧，需要进行页调度，而调度出去的页再次被需要，所以很快又被调回来，导致进程用于页调度的时间多余执行的时间
  1. 系统抖动的原因：进程没有“足够”的帧，它会不断地进行页调度，导致CPU利用率不高，而系统检测到CPU利用率不高就会加入新的进程执行，新的进程也需要帧，所以它也会不断地进行页调度从而拉低CPU的利用率，形成一个恶性循环 alt text
  2. 解决方案：
    1. 采用局部置换或者优先级置换算法
      • 思想：利用局部置换算法可以保证一个进程抖动时不会从其他进程所占用的帧中选择置换帧，也就不会干扰其他进程导致其他进程跟着抖动。优先级置换算法保证了进程中只能优先级比它低的进程从中选择置换帧，减少了从其他进程中调度帧，减少了对其他进程的干扰
      • 缺点：若进程抖动，则它大部分时间用于等待调度设备，这会使调度设备的等待队列变长。相应的，系统的页面错误处理时间也会变长，所以其他进程的有效访问时间也会变长
    2. 工作集模型
      • 原理：一个经常使用页的集合，一个进程由多个不同的局部构成，局部可能交叠
      • 局部模型：进程由多个局部构成，进程执行时从一个局部移到另一个局部
      • 原理：为了防止抖动，需要提供给进程所需足够多的帧。对于正在运行的进程，如果分配给它的帧不足以容纳它的局部时会出现抖动。所以可以根据它的局部所占内存大小分配帧，分配给每个进程的帧数应不小于该进程的当前局部
      • 思想：基于局部性原理，每个进程近期使用的帧数作为将要使用的帧数的近似值
    3. 一些概念：
      • 工作集窗口：用Δ表示，是固定数目的页引用集合，比如100个页引用
      • 工作集合：最近Δ个页引用集合，用WS表示，若一个页正在使用，那么它就在工作集合内。工作集合是程序局部的近似。工作集合的精度和Δ的大小选择有关，若Δ很小则无法涵盖整个局部，若很大则可能覆盖多个局部
      • WSS：表示该工作集包含的页数目。因为工作集是一个局部近似，以你工作集中包含的页面数WSS是一个局部所需要的页框数，也可以认为是一个程序在近段时间内最少需要得到页框数（帧数）。如果一个进程的可用页框数少于WSS，也就是说封面配给该进程的页框数不能包含进程的某个局部，就会引起颠簸（抖动）。假定系统中每个进程的工作集所包含的页数目为WSSi，那么系统可用页框数D=∑i=1nWSSi（D为总的帧需求量），若D大于可用帧数，则会出现抖动 alt text
    4. 应用：操作系统跟踪每个进程的工作集合，并为进程分配大于其工作集合的帧数，若还有空闲帧，则启动另一进程；若所有的WSSi总和大于可用帧数，则选择暂定一个进程，释放其所占内存给其他进程
    5. 评价：
      • 优点：防止了抖动，尽可能地提高了多道程序度，优化了CPU地的使用率
      • 缺点：工作窗口是移动窗口，难以跟踪
    6. 实现：通过固定定时中断和引用位，可以近似模拟工作集合模型4
  3. 页错误频率策略（Page-Fault Frequency Scheme）
    • 思想：为期望的页错误频率设置上限、下限，当进程的页错误率大于上限时需要给该进程分配更多的帧，而当进程的页错误率小于下限时从该进程中移走帧。其中当错误率增加而无可用帧时可能需要暂停一个进程，并将其所占用的额资源释放分配给其他高页错误率的进程 alt text

9.7 内存映射文件 ​

  1. 基本机制
    • 定义：利用虚拟内存计数将文件I/O当作普通的内存访问操作来对待，称为文件的内存映射
    • 思想： 文件的内存映射可将磁盘块映射到内存的一页（或多页）。开始的文件访问按照普通的请求页来进行，会产生页面错误，这样，一页大小的部分文件从文件系统读入物理页，之后的文件读写按照普通的内存访问执行。对映射到内存中的文件进行写可能不会被立即写回到磁盘上的文件中，有些操作定期建厂文件的内存映射页是否改变以选择是否更新到物理文件。文件的关闭会导致内存映射的数据回写到磁盘，并从进程的虚拟内存中删除
    • 共享：多个进程允许将同一个文件映射到各自的虚拟内存中，以允许共享数据 alt text
  2. 内存映射I/O（Memory-Mapped I/O）
    • 每个I/O控制器包括存放命令及传送数据的寄存器，通常，专用I/O指令郧西寄存器和系统内存之间进行数据传递
    • 内存映射I/O：一组内存地址专门映射到设备寄存器，对这些内存地址的读写如同对设备寄存器的读写

9.8 内核内存的分配 ​

  • 与用户内存的分配不同
  • 通常从空闲内存池种分配内存
    • 内核请求的内存大小有有变化，有的时候小于一个页的大小
    • 有些内核要求内存必须是连续的
  1. Buddy System
    • 从包含物理连续页的固定长度段中分配内存
    • 分配的内存时大小是2的幂；如果请求的内存大小不是2的幂，则分配最接近的2的幂；可以将一个块分成两个以满足更小分配的需求
    • 优点：通过合并可以使两个相邻的buddy块合并成一个更大的块
    • 缺点：由于buddy块的大小是2的幂，所以分配的内存大小不是2的幂时，会浪费一些空间产生碎片 alt text
  2. Slab Allocation
    • Slab指的是一个或多个物理连续的页
    • 缓存中包含了一个或多个Slab
    • 给每一个独一无二的内核数据结构分配一个缓存
      • 每个缓存中储存对象——数据结构的实例化
      • 当缓存倍创建时，填充对象标记为空
      • 当有结构存入时，对象标记为已用
    • 如果Slab已满，则下一个对象将存入空的Slab中
      • 如果没有空的Slab，则分配一个新的Slab
    • 优点：无碎片，快速的内存请求满足

9.9 其他考虑 ​

  1. 预调页（pre-paging） 纯按需调用系统的显著特征是当进程开始时会出现大量页错误，预调页目的在于阻止这种大量的初始调页，采用同时将所有的页一起调入内存。类似于指令预取，在进程引用前将需要的所有或部分页准备好。例如总线空闲时将执行页面之后的页面装入内存（局部性原理）
  2. 页大小：确定页大小要根据以下四点
    1. 页表：对于给定的虚拟内存，页越大，相应的页表和页的数量越小，所以较大的页比较理想
    2. 内存利用率：较小的页可以更好的利用内存
    3. 页读写所需时间：为最小化I/O时间，需要较大的页
    4. 页错误：为降低页错误率，需要较大页
  3. TLB范围（Translation Lookaside Buffer，转译后备缓冲器）
    • 定义：TLB范围指通过TLB可以访问的内存量，等于TLB的条目与页大小的乘积
    • 增加TLB的范围（提高命中率）的方法：
      1. 增加页的大小或提供多种页的大小：增加页的大小可能会有碎片产生；提供多种页的支持，需要操作系统而不是硬件来管理TLB，较为常用
      2. 增加TLB条目数：价格昂贵，而且可能也不足以满足某些大型程序的需要
  4. 反向列表：为帧创建的页表，详见8.5.3

9.10 例题 ​

  1. 概念
    • 虚拟内存
    • 请求页式&缺页中断
    • 页置换
    • 抖动/颠簸
  2. 例题