第三章 进程调度与死锁
进程调度的功能与时机
进程调度的功能
进程调度的功能由操作系统的 进程调度程序 来完成。
按照某种策略和算法 从就绪进程中为当前空闲的CPU选择在其上运行的新进程。
进程调度的时机
- 进程正常结束；
- 进程异常结束；
- 进程阻塞；
- 有更高优先级进程到来；
- 时间片用完；
进程调度算法
进程调度算法和输入/输出设备的速度都会影响系统的 响应时间。
选择调度方式和算法的若干准则
- 周转时间短；
- 响应时间快；
- 截止时间的保证；
- 系统吞吐量高；
- 处理机利用率好；
周转时间的相关计算
：CPU执行的时间
响应时间，用户提交一个请求直至系统首次产生响应的时间。包括：
- 输入设备输入的请求信息传送到处理机的时间；
- 处理机对请求信息进行处理的时间；
- 将所形成的响应信息回送到终端显示器的时间；
调度算法
先来先服务算法
英文：First-Come，First-Served，FCFS
含义：从就绪队列的队首 选择最先到达就绪队列的进程，为该进程分配CPU。
适合：长进程、CPU繁忙进程
短进程优先调度算法
英文：Shortest-Porcess-First，SPF
含义：从就绪队列中 选择估计运行时间最短的进程，为该进程分配CPU。
优点：与FCFS算法相比，短进程优先算法能有效 降低进程的平均等待时间，提高系统吞吐量。
缺点：
- 对长进程不利；
- 不能保证紧迫进程的处理；
- 进程长短由用户估计，不一定准确；
优先权调度算法
英文：Priority-Scheduling Lgorithm
含义：该算法中，系统将CPU分配给就绪队列中 优先级最高的进程。
存在的问题：无穷阻塞（饥饿问题）。
解决的方案：增加等待时间很长的进程的优先级 —— 老化技术。
类型：
- 非抢占式：运行期间，有更高优先级的进程到来，也 不能 剥夺CPU；
- 抢占式：运行期间，有更高优先级的进程到来，就 可以 剥夺CPU；
优先权类型：
- 静态优先权：创建时确定，运行期间 保持不变；
- 根据 进程的类型、进程需要的资源数量和用户的要求 来决定；
- 动态优先权：创建时确定，随着进程推进或等待时间增加而 改变；
时间片轮转调度算法
英文：Round-Robin，RR
含义：每次把CPU分给队首进程，令其执行一个时间片。
时间片大小：10-100ms
时间片很大 = 先来先服务调度程序
时间片很小：增大CPU对进程切换和调度的开销
时间片大小的 确定条件：
- 系统对 响应时间 的要求：响应时间要求越短，时间片越小；
- 就绪队列 中进程的数目：进程数量越多，时间片越小；
- 系统的 处理能力：处理能力越好，时间片越小；
linux 2.4 的时间片为：50ms
多级队列调度算法
含义：将就绪队列分成多个独立队列，每个队列都有自己的调度算法。
不足：不够灵活，对低优先级进程会存在无穷阻塞（饥饿）问题。
Minix 把对任务进程和服务进程采用 基于优先权的非抢占式调度。
多级反馈队列调度算法
含义：建立多个优先级不同的就绪队列，每个队列有大小不同的时间片。
优点：相对灵活，不会出现无穷阻塞（饥饿）问题。
实时系统中的调度
实时系统计算的 正确性 取决于 计算的逻辑结果的正确性 和 计算的时间。
实时调度的基本条件
- 提供必要的调度信息：
- 就绪时间；
- 开始截止时间；
- 完成截止时间；
- 处理时间；
- 资源要求；
- 优先级；
- 系统处理能力强；
- 采用抢占式调度机制；
- 具有快速切换机制：
- 对外部中断的快速响应能力：快速的硬件中断机构、中断的时间间隔尽可能短；
- 快速的进程切换能力：减少进程切换的开销；
常用的实时调度算法
- 最早截止时间优先算法 EDF：开始截止时间 越早，进程优先级越高，越优先获得CPU；
- 最低松弛度优先算法 LLF：进程的 紧迫程度 越小，进程优先级越高；
松弛度：表示一个实时进程的紧迫程度。
：完成截止时间
：当前时间
：处理完该任务需要的时间
进程切换
进程切换的含义
当前正在执行的进程成为被替换进程，让出其所使用的CPU，以运行被进程调度程序选择的新进程，这个过程称为 进程切换。
进程切换的步骤
- 保存CPU上下文环境；
- 更新进程1的进程控制块；
- 修改进程1的进程状态；（执行态 -> 就绪态或阻塞态）
- 移动进程1的进程控制块到就绪队列或阻塞队列；
- 调度新程序，更新进程2的进程控制块；
- 更新内存管理的数据结构；
- 恢复进程的硬件上下文；
多处理器调度
多处理器系统的类型
根据处理器的 耦合程度 分类：
- 紧密耦合 多处理器系统：共享主存储器（内存）和I/O设备；
- 松弛耦合 多处理器系统：有各自的存储器和I/O设备；
根据处理器的 结构功能是否相同 分类：
- 对称 多处理器系统：处理单元（CPU）功能和结构相同；
- 非对称 多处理器系统：有多种类型的处理单元，一个主处理器，多个从处理器；
多处理器系统的进程分配方式
对称系统分配方式
- 静态分配：
- 就绪队列的进程只能在与就绪队列对应的处理器上运行；
- 优点：进程调度的开销小；
- 动态分配：
- 进程随机地被分配到当时处于空闲状态的某一处理器上执行；
- 所有就绪进程都放在一个 公共的就绪队列 中；
- 优点：考虑服务器的 负载平衡问题，分配给空闲进程；
非对称系统分配方式
- 主-从式操作系统；
进程（线程）的调度方式
- 自调度；
- 成组调度；
- 专用处理器分配；
自调度
最常用最简单 的方式。
自调度的 优点：
- 易移植：很容易将单处理器环境下所用的调度机制移植到多处理器环境中；
- 有利于 提高CPU的利用率：不会出现处理器空闲或忙闲的情况；
自调度的 缺点：
- 瓶颈问题：处理器数量很多时；
- 低效性：多次更换处理器；
- 线程切换频繁：某些线程因其合作的线程未获得处理器而阻塞导致进程切换；
成组调度
系统将一组相互合作的进程或线程同时分配到同一组处理器上运行，进程或线程与处理器一一对应。
成组调度的 优点：
- 减少线程切换；
- 减少调度开销；
成组调度采用两种方式为应用程序分配处理器时间：
- 面向所有的 应用程序 平均分配处理器时间；
- 面向所有的 线程 平均分配处理器时间；
专用处理器分配
在程序执行期间，专门为该程序分配一组处理器，每个线程一个。
专用处理器分配的 优点：
- 加成程序运行速度；
- 避免进程切换；
专用处理器分配的 缺点：
- 处理器资源严重浪费；
死锁
死锁的定义
由于 多个进程竞争共享资源 而引起的 进程不能向前推进 的僵死状态称为 死锁。
产生死锁的原因
竞争 共享资源且分配资源的 顺序不当。
产生的必要条件
- 互斥条件；
- 请求和保持条件；
- 不剥夺条件；
- 环路等待条件；
只有当 四个条件同时满足 时才会产生死锁。
处理死锁的基本方法
- 死锁的 预防：通过 破环死锁的产生条件 来保证不发生死锁；
- 死锁的 避免：通过 算法合理分配资源 来保证不发生死锁；
- 死锁的 检测：检索当前系统是否出现死锁；
- 死锁的 解除：检索到系统有死锁后进行解除；
- 死锁的 忽略；
死锁的预防
保证产生死锁的必要条件中，至少其中一个条件不成立。
- 摒弃 请求和保持条件：要求进程一次性 申请 需要的 全部资源，申请其他资源前 释放 已经占用的资源；
-
摒弃 不剥夺条件：系统 抢占 被占用的资源分配给需要的进程；
- 缺点：实现复杂，代价高；
-
摒弃 环路等待条件：进程必须 按规定的顺序 申请 资源（打印机、磁盘）；
- 缺点：限制了新设备的增加，资源浪费，用户编程麻烦；
死锁的避免
通过资源合理分配使系统处于 安全状态。
安全状态 ？：能够找到一个进程 执行序列，按照这个序列会每个进程分配资源，就可以保证进程资源分配和执行顺利完成，不会发生死锁。
设系统有一类数量为 M 的独占性资源，系统中有 N 个进程竞争该类资源，每个进程对资源的最大需求为 W。当满足 时，系统处于安全状态。
银行家算法：一个进程提出资源请求后，系统先进行资源的试分配，分配后检测系统是否安全。
任何时刻都能至少保证一个进程获得所需要的全部资源。
死锁的检测
何时调用 检测算法 ？：
- 死锁可能发生的 频率；
- 死锁发生时受影响的 进程数量；
资源分配图：
死锁定理：S为死锁状态 的充分条件是当前仅当S状态的 资源分配图是不可完全简化的（上图的资源分配图是可以被简化的）。
死锁定理用于检测系统所处的资源分配状态是否为死锁状态。
死锁的解除
-
进程终止：
- 终止所有死锁进程；
- 一次只终止一个处于死锁状态的进程，直到死锁接触；
-
资源抢占：
- 逐步从进程中抢占资源给其他进程使用直到死锁被打破为止；
抢占的代价最小，死锁进程拥有的资源数量、死锁进程到目前为止已经消耗的执行时间。
