操作系统第五章

这是一个关于操作系统第五章的思维导图，可以保证最低的缺页率，但实际上，只有在进程执行的过程中才能知道接下来会访问到的是哪个页面，无法提前预判页面访问序列。因此是无法实现的。

虚拟存储器

• 虚拟存储器概述
  • 传统存储区管理
    • 组成
      • 连续分配，非连续分配
    • 特征和缺点
      • 一次性：作业必须一次性全部装入内存后才能开始运行。 造成问题：①作业很大时，不能全部装入内存，导致大作业无法运行； ②当大量作业要求运行时，由于内存无法容纳所有作业，因此只有少量作业能运行，导致多道程序并发度下降。
      • 驻留性：一旦作业被装入内存，就会一直驻留在内存中，直至作业运行结束。事实上，在一个时间段内，只需访问作业的一小部分数据即可正常运行，这就导致了内存中会驻留大量的、暂时用不到的数据，浪费了宝贵的内存资源
  • 局部性原理
    • 时间局部性：如果执行了程序中的某条指令，那么不久后这条指令很有可能再次执行；如果某个数据被访问过，不久之后该数据很可能再次被访问。（因为程序中存在大量的循环）
    • 空间局部性：一日程序访问了某个存储单元，在不久之后，其附近的存储单元也很有可能被访问。(因为很多数据在内存中都是连续存放的，并且程序的指令也是顺序地在内存中存放的)
    • 高速缓存技术，把近期频繁访问到的数据放到更高速的存储器中，反之 局部性原理：应用快表机构将近期常访问的页表项副本放到更高速的联想寄存器中
  • 虚拟内存的定义和特征
    • 定义
      • 基于局部性原理： 在程序装入时，可以将程序中很快会用到的部分装入内存，暂时用不到的部分留在外存，就可以让程序开始执行。 在程序执行过程中，当所访问的信息不在内存时，由操作系统负责将所需信息从外存调入内存，然后继续执行程序 若内存空间不够，由操作系统负责将内存中暂时用不到的信息换出到外存。 在操作系统的管理下，在用户看来似乎有一个比实际内存大得多的内存，这就是虚拟内存
        • 有一个易混点：
        • 操作系统虚拟性的一个体现，实际的物理内存大小没有变，只是在逻辑上进行了扩充。
    • 特征
      • 多次性：无需在作业运行时一次性全部装入内存，而是允许被分成多次调入内存。
      • 对换性：在作业运行时无需一直常驻内存，而是允许在作业运行过程中，将作业换入、换出。
      • 虚拟性：从逻辑上扩充了内存的容量，使用户看到的内存容量，远大于实际的容量。
  • 如何实现虚拟内存技术
    • 虚拟内存的实现
      • 请求分页存储管理
      • 请求分段存储管理
      • 请求段页式存储管理
    • 在程序执行过程中，当所访问的信息不在内存时，由操作系统负责将所需信息从外存调入内存，然后继续执行程序（请求调页）
    • 若内存空间不够，由操作系统负责将内存中暂时用不到的信息换出到外存。（页面置换）
• 请求分页存储管理方式
  • 页表机制
  • 缺页中断机构
    • • 如果内存中有空闲块，则为进程分配一个空闲块，将所缺页面装入该块，并修改页表中相应的页表项。
      • 如果内存中没有空闲块，则由页面置换算法选择一个页面淘汰，若该页面在内存期间被修改过，则要将其写回外存。未修改过的页面不用写回外存。
    • 中断分类
      • • 缺页中断是因为当前执行的指令想要访问的目标页面未调入内存而产生的，因此属于内中断 一条指令在执行期间，可能产生多次缺页中断。（如：copy A to B,即将逻辑地址A中的数据复制到逻辑地址B,而A、B属于不同的页面，则有可能产生两次中断)
    • 缺页中断未必会进行页面置换，若还有可用的空闲块，则不必发生页面置换
    • 缺页率：缺页中断次数/访问页面次数
  • 地址变换机构
    • • 找到页表项是需要检查页面是否在内存中
      • 若页面不再内存中，需要请求调页
      • 若内存空间不够，还需换出页面
      • 页面调入内存后，需要修改相应页表项
• 页面置换算法
  • 最佳置换算法OPT
    • 算法思想
      • 每次选择淘汰的页面将是以后永不使用，或者在最长时间内不再被访问的页面，这样可以保证最低的缺页率
    • 优缺点
      • 可以保证最低的缺页率，但实际上，只有在进程执行的过程中才能知道接下来会访问到的是哪个页面，无法提前预判页面访问序列。因此是无法实现的。
  • 先进先出置换算法FIFO
    • 算法思想
      • 每次选择淘汰的页面是最早进入内存的页面，把调入内存的页面根据调入的先后顺序排成一个队列，换出页面时选择队头页面。队列最大长度取决于系统为进程分配了多少个内存块。
    • 优缺点
      • Belady异常一一当为进程分配的物理块数增大时，缺页次数不减反增的异常现象 只有FIFO算法会产生Belady异常。FIFO算法虽然实现简单，但与进程实际运行时的规律不适应，因为先进入的页面也有可能最经常被访问。故算法性能差
  • 最近最久未使用置换算法LRU
    • 算法思想
      • 每次淘汰的页面是最近最久未使用的页面，赋予每个页面对应的页表项中，用访问字段记录该页面自上次被访问以来所经历的时间t当需要淘汰一个页面时，选择现有页面中t值最大的，即最近最久未使用的页面。
    • 优缺点
      • 该算法是最接近OPT的，但是算法的实现需要专门的硬件支持，实现困难，开销大
  • 时钟置换算法CLOCK
    • 算法思想
      • 为每个页面设置一个访问位，再将页面通过链接指针链接成一个循环队列。 被访问时，访问位置为1。 访问的页面在内存时，不需要转动指针。当需要淘汰一个页面时，如果是0，就选择该页换出；如果是1，则将它置为0，暂不换出，继续检查下一个页面。若第一轮扫描中所有页面都是1，则进行第二轮扫描（第二轮扫描中一定会有访问位为0的页面，因此简单的CLOCK算法选择一个淘汰页面最多会经过两轮扫描)
  • 改进型时钟置换算法
    • 原算法的缺点
      • 简单的时钟置换算法仅考虑到一个页面最近是否被访问过。而被淘汰的页面没有被修改过，就不需要执行IO操作写回外存。只有被淘汰的页面被修改过时，才需要写回外存。 因此，除了考虑最近有没有被访问之外，还应考虑有没有被修改。在条件都相同时，应优先淘汰没有修改过的页面，避免IO操作 修改位=0，表示没有被修改过。用（访问位，修改位）的形式表示各页面状态
    • 改进型算法思想
      • 将所有可能被置换的页面排成一个循环队列 第一轮：从当前位置开始扫描到第一个(0,0)的帧用于替换。本轮不修改任何标志位 第二轮：若第一轮扫描失败，则重新扫描，查找第一个(0,1)的帧用于替换。本轮将所有扫描过的帧访问位设为0 第三轮：若第二轮扫描失败，则重新扫描，查找第一个(0,0)的帧用于替换。本轮扫描不修改任何标志位 第四轮：若第三轮扫描失败，则重新扫描，查找第一个(0,1)的帧用于替换 由于第二轮已将所有帧的访问位设为0，因此经过第三四轮扫描一定会有一个帧被选中，因此最多会进行四轮扫描
• 页面分配策略
  • 驻留集（最小物理块数）
    • 指请求分贝存储管理中给进程分配的物理块的集合，驻留集大小一般小于进程的总大小。 驻留集太小，会导致缺页频繁，系统要花大量的时间来处理缺页，实际用于进程推进的时间很少； 驻留集太大，又会导致多道程序并发度下降，资源利用率降低。
  • 页面分配、置换策略
    • 固定分配VS可变分配：区别在于进程运行期间驻留集大小是否可变 局部置换VS全局置换：区别在于发生缺页时是否只能从进程自己的页面中选择一个换出
      • 固定分配V可变分配：区别在于进程运行期间驻留集大小是否可变 局部置换V全局置换：区别在于发生缺页时是否只能从进程自己的页面中选择一个换出
    • 固定分配局部置换
      • 为每个进程分配一定数量的物理块不改变。若发生缺页，则只能从该进程中选出一页换出，然后再调入需要的页面
      • 缺点
        • 缺点：很难在刚开始就确定应为每个进程分配多少个物理块才算合理。（可以根据进程大小、优先级、或是根据程序员给出的参数来确定为一个进程分配的内存块数)
    • 可变分配局部置换
      • 刚开始为每个进程分配一定数量的物理块。操作系统保持一个空闲物理块队列 当发生缺页时，从空闲物理块中取出一块分配给该进程；若已无空闲物理块，则选择一个未锁定的页面换出外存，再将该物理块分配给缺页的进程。 只要某进程发生缺页，都将获得新的物理块，仅当空闲物理块用完时，系统才选择一个未锁定的页面调出。被选择调出的页可能是系统中任何一个进程中的页，因此这个被选中的进程拥有的物理块会减少，缺页率会增加。
    • 可变分配全局置换
      • 刚开始会为每个进程分配一定数量的物理块。当发生缺页时，只允许从该进程自己的物理块中选出一个进行换出外存。如果进程在运行中频繁地缺页，系统会为该进程多分配几个物理块，直至该进程缺页率趋势适当程度；反之
  • 调入页面的时机
    • 运行前调入
      • 预调页策略：根据局部性原理，一次调入若干个相邻的页面可能比一次调入一个页面更高效。但如果提前调入的页面中大多数都没被访问过，则又是低效的。因此可以预测不久之后可能访问到的页面，将它们预先调入内存，但目前预测成功率只有50%左右。 这种策略主要用于进程的首次调入
        • 主要指空间局部性，即：如果当前访问了某个内存单元，在之后很有可能会接着访问与其相邻的那些内存单元。
    • 运行中调入
      • 请求调页策略：进程在运行期间发现缺页时才将所缺页面调入内存。 由这种策略调入的页面一定会被访问到，但由于每次只能调入一页，而每次调页都要磁盘I/O操作，因此开销较大
  • 从何处调页
    • 系统拥有足够的对换区空间： 页面的调入、调出都是在内存与对换区之间进行，保证页面的调入、调出速度很快。在进程运行前，需将进程相关的数据从文件区复制到对换区
    • 系统缺少足够的对换区空间： 凡是不会被修改的数据都直接从文件区调入，由于这些页面不会被修改，换出时不必写回磁盘，下次需要时从文件区调入即可。对于可能被修改的部分，换出时需写回磁盘对换区，下次需要时从对换区调入。
    • UNX方式： 运行之前进程有关的数据全部放在文件区，故未使用过的页面，都可从文件区调入。若被使用过的页面需要换出，则写回对换区，下次需要时从对换区调入。
  • 抖动
    • 定义
      • 刚刚换出的页面马上又要换入内存，刚刚换入的页面马上又要换出外存，这种频繁的页面调度行为
    • 产生原因
      • 进程频繁访问的页面数目高于可用的物理块数（分配给进程的物理块不够)
        • 为进程分配的物理块太少，会使进程发生抖动现象。 为进程分配的物理块太多，又会降低系统整体的并发度，降低某些资源的利用率
  • 工作集
    • 定义
      • 指在某段时间间隔里，进程实际访问页面的集合。操作系统会根据“窗口尺寸”来算出工作集。
    • 计算