操作系统之进程调度

聚焦考研复习：操作系统的最难一章《进程调度》！本思维导图归纳总结了进程概述，进程的状态与转换，进程控制，进程通信、线程、多线程模型，处理机调度概念、层次、进程调度的时机、切换与过程、调度方式等25块知识点。很细致，欢迎采纳，一起学习吧！

进程管理

• 1. 进程概述
  • 定义
    • 进程是进程实体的运行过程，是系统进行资源分配和调度的一个独立单位
  • 组成
    • PCB
      • 进程描述信息
      • 进程控制和管理信息
      • 资源分配清单
      • 处理机相关信息
    • 程序段
      • 存放要执行的程序代码
    • 数据段
      • 存放程序运行过程中处理的各种数据
  • 组织形式
    • 链接方式
      • 按进程状态将PCB分为多个队列
    • 索引方式
      • 按照进程状态建立几张索引表，各表项指向一个PCB
  • 特征
    • 动态性
      • 进程的最基本特征
    • 并发性
    • 独立性
      • 进程是系统进行资源分配、调度的独立单位
    • 异步性
      • 各进程以不可预知的速度向前推进，可能导致运行结果的不确定性
    • 结构性
• 2. 进程的状态与转换
  • 状态
    • 运行状态
      • 有CPU 有其他所需资源
    • 就绪状态
      • 无CPU 有其他所需资源
    • 阻塞状态
      • 无CPU 无其他所需资源
    • 创建状态
      • 操作系统为新进程分配资源，创建PCB
    • 终止状态
      • 操作系统回收进程的资源、撤销PCB
  • 进程状态间的转换
    • 就绪态到》运行态
      • 进程被调度
    • 运行态》就绪态
      • 时间片到，或CPU被其他更高优先级的进程抢占
    • 运行态》阻塞态
      • 等待系统资源分配，或等待某事件发生（主动行为）
    • 阻塞态》就绪态
      • 资源分配到位，等待的事件发生（被动行为）
    • 创建态》就绪态
      • 系统完成创建进程相关的工作
    • 运行态》终止态
      • 进程运行结束，或运行过程中遇到不可修复的错误
• 3. 进程控制
  • 基本概念
    • 进程控制就是要实现进程状态之间的转换
    • 进程控制用原语来实现
      • 原语用关/开中断来实现
      • 原语是一种特殊的程序
      • 原语的执行必须一气呵成，不可中断
  • 相关原语
    • 进程的创建
    • 进程的终止
    • 进程的阻塞
    • 进程的唤醒
    • 阻塞和唤醒要成对出现
    • 进程的切换
• 4. 进程通信
  • 共享存储
    • 设置一个共享空间
    • 要互斥的访问共享空间
    • 两种方式
      • 基于数据结构（低级
      • 基于存储区的共享（高级
  • 管道通信
    • 设置一个特殊的共享文件（管道），其实就是一个缓冲区
    • 一个管道只能实现半双工通信
    • 实现双向同时通信要建立两个管道
    • 各进程要互斥的访问管理
    • 写满时，不能在写。读空时，不能再读
    • 没写满，不能读。没读空，不能写
  • 消息传递
    • 传递结构化的消息（消息头/消息体）
    • 系统提供“发送/接受原语”
    • 两种方式
      • 直接通信方式
        • 消息直接挂到接收方的消息队列里
      • 间接（信箱）通信方式
        • 消息先发送到中间体（信箱）
• 5. 线程、多线程模型
  • 什么是线程，为什么要引入线程？
    • 可理解为“轻量级进程”
    • 可增加并发度，减少并发带来的开销
  • 引入线程机制后，有什么变化？
    • 资源分配、处理机调度
    • 并发性
    • （实现并发的）系统开销
  • 线程有哪些重要的属性
    • 线程是处理机调度的单位，进程是资源分配的单位
    • 同一进程的各线程共享进程拥有的资源
    • 同一进程内的线程切换不会导致进程切换
  • 线程的实现方式
    • 用户级线程
      • 从用户视角看的线程
    • 内核级线程
      • 从操作系统视角看的进程（内核级线程才是处理机分配的单位）
    • 组合方式
      • 上述两种方式的组合
  • 多线程模型
    • 多对一模型
      • 进程管理开销小效率高
      • 一个线程阻塞会导致整个进程都被阻塞（并发度低）
    • 一对一
      • 进程管理开销大
      • 各个线程可分配到多核处理机并行执行，并发度高
    • 多对多
      • 取二者之所长
• 6. 处理机调度概念、层次
  • 基本概念
    • 按某种算法选择一个进程将处理机分配给它
    • 三个层次
      • 高级调度（作业调度）
        • 按照某种规则，从后备队列中选择合适的作业将其调入内存，并为其创建进程
      • 中级调度（内存调度）
        • 按照某种规则，从挂起队列中选择合适的进程将其数据调回内存
      • 低级调度（进程调度）
        • 按照某种规则，从就绪队列中选择一个进程为其分配处理机
    • 三层调度的联系、对比
      • 高级调度
        • 外存》内存（面向作业）
        • 发生频率：最低
      • 中级调度
        • 外存》内存（面向进程）
        • 发生频率：中等
      • 低级调度
        • 内存》CPU
        • 发生频率：最高
    • 补充
      • 为减轻系统负载，提高资源利用率，暂时不执行的进程会被调到外存从而变为挂起态
      • 七状态模型：在五状态模型的基础上加入了 就绪挂起 和 阻塞挂起 两种状态
• 7. 进程调度的时机 切换与过程 调度方式
  • 时机
    • 什么时候需要进程调度
      • 主动放弃
        • 进程正常终止
        • 运行过程中发生异常而终止
        • 主动阻塞（如等待I/O）
      • 被动放弃
        • 分给进程的时间片用完
        • 有更紧急的事情需要处理（如I/O）中断
        • 有更高优先级的进程进入就绪队列
    • 什么时候不能进行进程调度
      • 在处理机中断的过程中
      • 进程在操作系统内核程序临界区中
      • 原子操作过程中（原语）
  • 切换与过程
    • 狭义的调度和切换的区别
    • 切换过程
      • 对原来运行进程各种数据的保存
      • 对新的进程各种数据的恢复
    • 重要理论：进程调度、切换是有代价的，并不是调度越频繁，并发度就越高
  • 方式
    • 非剥夺调度方式（非抢占式
      • 只能由当前运行的进程主动放弃CPU
    • 剥夺调度方式（抢占式）
      • 可由操作系统剥夺当前进程的CPU使用权
• 8. 调度算法的评价指标
  • CPU利用率
    • 也有题目会让我们计算某设备的利用率
    • 利用率=忙碌的时间/总时间
  • 系统吞吐量
    • 系统吞吐量=总共完成了多少道作业/总共花了多少时间
  • 周转时间
    • 周转时间=作业完成时间-作业提交时间
    • 平均周转时间=各作业周转时间之和/作业数
    • 带权周转时间=作业周转时间/作业实际运行的时间
    • 平均带权周转时间=各作业带权周转时间之和/作业数
  • 等待时间
    • 进程/作业 等待被服务的时间之和
    • 平均等待时间即各个进程/作业 等待时间的平均值
  • 响应时间
    • 从用户提交请求到首次产生响应所用的时间
• 9. 调度算法
  • 先来先服务 FCFS
    • 主要从公平的角度考虑
    • 按照作业/进程到达的先后顺序进行服务
    • 用于作业调度时，考虑的是哪个作业先到达后备队列；用于进程调度时，考虑是哪个进程先进入就绪队列
    • 非抢占式的算法
    • 公平、算法实现简单
    • 排在长作业后面的短作业需要等待很长时间，带权周转时间很大，对短作业来说用户体验不好。对场作业有利，对短作业不利
    • 不会饥饿
  • 短作业优先 SJF
    • 追求最少的平均等待时间，最少的平均周转时间，最少的平均带权周转时间
    • 最短的作业/进程优先得到服务
    • 即可用于作业调度，也可用于进程调度，用于进程调度时称为段进成优先算法
    • SJF 和 SPF是非抢占式的算法，但也有抢占式的版本--最短剩余时间优先算法 SRTN
    • 最短的平均等待时间、平均周转时间
    • 不公平，对短作业有利，对长作业不利。可能产生饥饿现象。另外，运行时间是用户提供的，并不一定真实，不一定做到真正的短作业优先
    • 会饥饿。如果一直得不到服务，则称为饿死
  • 高响应比优先 HRRN
    • 要综合考虑作业/进程的等待时间和要求服务的时间
    • 在每次调度时先计算各个作业/进程的响应比，选择响应比最高的作业/进程为其服务
      • 响应比=（等待时间+要求服务时间）/要求服务时间
    • 既可用于作业调度，又可进程调度
    • 非抢占式。因此只有当前运行的作业/进程主动放弃处理机时，才需要调度，才需要计算响应比
    • 综合考虑了等待时间和运行时间。等待时间相同时，要求服务时间短的优先，要求服务时间相同时，等待时间长的优先
    • 不会饥饿
• 10. 调度算法2
  • 时间片轮转调度RR
    • 公平的、轮流的为各个进程服务，让每个进程在一定时间间隔内都可以得到响应
    • 按照各进程到达就绪队列的顺序，轮流让各个进程执行一个时间片。若进程未在一个时间片内执行完，则剥夺处理机，将进程重新放到就绪队列队尾重新排队
    • 用于进程调度（只有作业放入内存建立了相应的进程后，才能分配处理机时间片
    • 若进程未能在时间片内运行完，将被强行剥夺处理机使用权，因此时间片轮转调度算法属于抢占式的算法，由时钟装置发出时钟中断来通知CPU时间片已到
    • 公平 响应快 适用于分时操作系统
    • 由于高频率的进程切换，因此有一定开销；不区分任务的紧急程度
    • 不会饥饿
    • 时间片太大或太小分别有什么影响
  • 优先级调度算法
    • 随着计算机的发展，特别是实时操作系统的出现，越来越多的应用场景需要根据任务的紧急程度来决定处理顺序
    • 每个进程/作业都有自己的优先级，调度时选择优先级最高的作业/进程
    • 既可用于作业调度，也可用于进程调度。甚至，还会在之后会学习的I/O调度中
    • 抢占式、非抢占式都有。非抢占式只需在进程主动放弃处理机时进行调度即可，而抢占式还需在就绪队列变化时，检查是否会发生抢占
    • 在优先级区分紧急程度、重要程度，适用于实时操作系统。可灵活的调整对各种作业/进程的偏好程度
    • 若源源不断的有高优先级进程到来，则可能导致饥饿
    • 会饥饿
  • 多级反馈队列调度算法
    • 对其他调度算法的折中权衡
    • 规则
      • 设置多级就绪队列，各级队列优先级从高到低，时间片从小到大
      • 新进程到达时先进入第一级队列，按FCFS原则排队等地啊被分配时间片，若用完时间片进程还未结束，则进程进入下一级队列队尾，如果此时已经是在最下级的队列，则重新放回该队列队尾
      • 只有第k级队列为空时迷彩灰为k+1级队头的进程分配时间片
    • 用于进程调度
    • 抢占式。在k级队列的进程运行过程中，若更上级的队列（1-k-1级）中进入了一个新进程，则由于新进程处于优先级更高的队列中，因此新进程会抢占处理机，原来运行的进程放回k级队列队尾
    • 对各类进程相对公平
    • 会饥饿
• 11. 进程同步 进程互斥
  • 进程同步
    • 并发性带来了异步性，有时需要通过进程同步解决这种异步问题
    • 有的进程之间需要相互配合的完成工作，各进程的工作推进需要遵循一定的先后顺序
  • 进程互斥
    • 对临界区的访问，需要互斥的进行，即统一时间段内只能允许一个进程访问该资源
    • 四个部分
      • 进入区
        • 检查是否可进入临界区，若可进入，需要上锁
      • 临界区
        • 访问临界资源的那段代码
      • 退出区
        • 负责解锁
      • 剩余区
        • 其余代码部分
    • 需要遵循的原则
      • 空闲让进
        • 临界区空闲时，应允许一个进程访问
      • 忙则等待
        • 临界区正在被访问时，其他试图访问的进程需要等待
      • 有限等待
        • 要在有限时间内进入临界区，保证不会饥饿
      • 让权等待
        • 进入了临界区的进程，要释放处理机，防止忙等
• 12. 进程互斥的软件实现方法
  • 单标志法
    • 在进入区只做检查，不上锁
    • 在退出区把临界区的使用权转交给另一个进程，相当于在退出区既给另一进程解锁，又给自己上锁
    • 主要问题
      • 不遵循空闲让进原则
  • 双标志先检查
    • 在进入区先检查后上锁，退出区解锁
    • 主要问题
      • 不遵循忙则等待
  • 双标志后检查
    • 在进入区先加锁后检查，退出区解锁
    • 主要问题
      • 不遵循空闲让进、优先等待。可能导致饥饿
  • Peterson算法
    • 在进入区主动争取-主动谦让-检查对方是否想进、己方是否谦让
    • 主要问题
      • 不遵循让权等待原则，会发生忙等
• 13. 进程互斥的硬件实现方法
  • 中断屏蔽方法
    • 使用开关中断指令实现
    • 简单高效
    • 只适用于单处理机，只适用于操作系统内核进程
  • TestSndSet (TS指令/TSL指令）
    • old记录是否已被上锁
    • 再将lock设为true
    • 检查临界区是否已被上锁
    • 若已上锁，则循环重复前几步
    • 实现简单；适用于多处理机环境
    • 不满足让权等待
  • Swap指令（XCJG指令）
• 14. 信号量机制
  • 整型信号量
    • 用一个整数型变量作为信号量，数值表示某种资源数
    • 整型信号量与普通整型变量的区别：对信号量只能执行初始化 P V 三种操作
    • 整型信号量存在的问题：不满足让权等待原则
  • 记录型信号量
    • 大题、小题超高频出题点
    • S.value表示某种资源数，S.L指向等待该资源的队列
    • P操作中，一定是先S.value--，之后可能需要执行block原语
    • V操作中，一定是先S.value++，之后可能需要执行wakeup原语
    • 注意：要能够自己推断在什么条件下需要执行block或wakeup
    • 可以用记录型信号量实现系统资源的申请和释放
    • 可以用记录型信号量实现进程互斥、进程同步
• 15. 用信号量机制实现进程互斥、通步、前驱关系
  • 除了互斥、同步问题之外，还会考察有多少个资源的问题，有多少资源就把信号量初值设为多少，申请资源时进行P操作，释放资源时进行V操作即可
  • 实现进程互斥
    • 互斥问题，信号量初值为1
    • 分析问题，确定临界区
    • 设置互斥信号量，初值为1
    • 临界区之前对信号量执行P操作
    • 临界区之后对信号量执行V操作
  • 实现进程同步
    • 同步问题，信号量初值为0
    • 分析问题，找出哪里需要实现 一前一后 的同步关系
    • 设置同步信号量，初始值为0
    • 在前操作之后执行V操作
    • 在后操作之前执行P操作
  • 实现进程的前驱关系
    • 前驱关系问题，本质上就是更复杂的同步问题
    • 分析问题，画出前驱图，把每一对前驱关系都看成一个同步问题
    • 为每一对前驱关系设置同步信号量，初值为0
    • 在每个前操作之后执行V操作
    • 在每个后操作之前执行P操作
• 16. 生产者消费者问题
• 17. 多生产者多消费者问题
• 18. 吸烟者问题
• 19. 读者-写者问题
• 20. 哲学家进餐问题
• 21. 管程
  • 为什么要引入管程
    • 解决信号量机制编程麻烦、易出错的问题
  • 组成
    • 共享数据结构
    • 对数据结构初始化的语句
    • 一组用来访问数据结构的过程（函数）
  • 基本特征
    • 各外部进程\线程只能通过管程提供的特定“入口”才能访问共享数据
    • 每次仅允许一个进程在管程内执行某个内部过程
  • 补充
    • 各进程必须互斥的访问管程的特性是由编译器实现的
    • 可在管程中设置条件变量及等待/唤醒操作以解决同步问题
• 22. 死锁的概念
  • 什么是死锁
    • 各进程互相等待对方手里的资源，导致各进程都阻塞，无法向前推进
    • 死锁 饥饿 死循环的区别
      • 死锁：至少是两个进程一起死锁，死锁进程处于阻塞态
      • 饥饿：可以只有一个进程饥饿，饥饿进程可能阻塞也可能就绪
      • 死循环：可能只有一个进程发生死循环，死循环的进程可上处理机
      • 死锁和饥饿是操作系统要解决的问题，死循环是应用程序员要解决的
    • 死锁产生的必要条件
      • 互斥条件
        • 对必须互斥使用的资源的争抢才会导致死锁
      • 不剥夺条件
        • 进程保持的资源只能主动释放，不可强行剥夺
      • 请求和保持条件
        • 保持着某些资源不放的同时，请求别的资源
      • 循环等待条件
        • 存在一种进程资源的循环等待链
        • 循环等待未必死锁，死锁一定有循环等待
    • 什么时候会发生死锁
      • 对不可剥夺资源的不合理分配，可能导致死锁
    • 死锁的处理策略
      • 预防死锁
        • 破坏死锁产生的四个必要条件
      • 避免死锁
        • 避免系统进入不安全状态（银行家算法）
      • 死锁的检测和解除
        • 允许死锁发生，系统负责检测出死锁并解锁
• 23. 死锁的处理-预防死锁
  • 破坏互斥条件
    • 将临界资源改造为可共享使用的资源（如SPOOLing技术）
    • 缺点：可行性不高，很多时候无法破坏互斥条件
  • 破坏不剥夺条件
    • 方案一，申请的资源得不到满足时，立即释放拥有的资源
    • 方案二，申请的资源被其他进程占用时，由操作系统协助剥夺（考虑优先级）
    • 缺点：实现复杂；剥夺资源可能导致部分工作失效；反复申请和释放导致系统开销大；可能导致饥饿
  • 破坏请求和保持条件
    • 运行前分配好所需要的资源，之后一直保持
    • 缺点：资源利用率低，可能导致饥饿
  • 破坏循环等待条件
    • 给资源编号，必须按编号从小到大的顺序申请资源
    • 缺点：不方便增加新设备；会导致资源浪费；用户编程麻烦
• 24. 死锁的处理-避免死锁
  • 什么是安全序列
  • 什么是系统的不安全状态，与死锁有何联系
  • 如何避免系统进入不安全状态-银行家算法
• 25. 死锁的处理-检测和解除
  • 死锁的检测
    • 数据结构：资源分配图
      • 两种节点
        • 进程节点
        • 资源节点
      • 两种边
        • 进程结点》资源节点（请求边）
        • 资源节点》进程结点（分配边）
    • 死锁检测算法
      • 依次消除与不阻塞进程相连的边，知道无边可消
      • 注：所谓不阻塞进程是指其申请的资源数还足够的进程
      • 死锁定理：若资源分配图是不可完全简化的，说明发生了死锁
        • 题中一般会给出资源分配图，不过也要小心与数据结构结合来考察
  • 死锁的解除
    • 资源剥夺法
    • 撤销进程法（终止进程法）
    • 进程回退法