操作系统学习笔记三 处理机调度与死锁

• 处理机的调度层次
  • 高级调度
  • 低级调度
  • 中级调度
• 调度模型和调度准则
  • 调度模型
  • 调度准则
• 调度算法
  • 先来先服务FCFS
  • 短作业优先调度SJ(P)F
  • 优先级调度算法
  • 基于时间片的轮转调度算法
• 实时调度
  • 实时系统基本条件
• 产生死锁的原因和必要条件
  • 死锁原因
  • 必要条件
  • 处理的基本方法：
• 预防死锁的方法
  • 预防死锁
  • 系统安全状态
  • 银行家算法避免死锁
• 死锁的检测与解除
  • 死锁的检测
  • 死锁的解除

本节主要讨论处理机的调度机制，提高处理机的利用率和改善系统性能（吞吐量、响应时间）等。另外还有处理机死锁方面的介绍。

处理机的调度层次

高级调度

• 又称为长程调度，作业调度等。根据某种算法，将后备队列中的作业调入到内存。批处理系统中会需要从外存将作业调入内存。
• 作业：通常包含程序，数据，作业说明书（用以控制程序）。作业是从外存调度到内存的基本单位。
• 作业步：作业运行完成工作的步骤。典型的作业步：编译->链接装配->运行。
• 作业流：若干个作业此次存放在外存形成作业流。
• 作业控制块 JCB，Job Control Block：作业在系统中的标识。包含作业的相关信息（用以控制和标识作业）。
• 作业调度：根据 JCB，检查能否满足作业资源，按照一定算法为作业创建进程和分配资源，插入就绪队列。也叫接纳调度。要做两个决定：
  • 接纳多少作业：取决于多少个作业能同时运行。
  • 接纳哪些作业：决定哪些作业从外存进入内存。例如：先来先服务，短作业优先，基于作业优先级调度，“响应比高优先”
• 特例：分时系统，用户输入数据或命令是直接送入内存，无需高级调度，但有时需要限制进入系统的用户数。实时系统中不需要作业调度。

低级调度

• 也称为进程调度，短程调度。调度对象为进程。批处理、实时系统和分时系统都必须配置。
• 低级调度：决定哪个进程（内核级线程，后续省略）获得相应的处理机。作用：保存处理机现场信息，选取进程，将处理器分配给进程。
• 进程调度三个机制：
  • 排队器：按照一定的方式将就绪队列排成一个或多个队列。
  • 分配器：将从就绪队列中选出。
  • 上下文切换机制：保存上一个进程的 CPU 寄存器和程序计数器内容，在 CPU 寄存器中恢复下一个进程的上下文内容，程序计数器指向下一个进程被中断时的位置。
• 进程调度方式
  • 非抢占方式：不会被其他进程抢占，仅因自己执行完毕，程序错误，I/O 请求，通信或同步等原语操作等会被阻塞。实现简单，系统开销小。
  • 抢占方式：其他进程根据某种原则可以暂停当前运行进程。原则：优先权原则，短作业优先原则，时间片原则。

中级调度

• 目的：提高内存利用率和系统吞吐量，将哪些暂时不能运行的进程不再占用宝贵的内存资源，转为就绪驻外状态或挂起状态。实际是存储器的对换功能。

调度模型和调度准则

调度模型

• 仅有进程调度的调度模型
• 高级和低级调度模型（增加后备队列，中级调度）
• 同时具有三级调度（增加挂起队列）

调度准则

• 面向用户准则：
  • 周转周期短：平均周转时间，带权平均周转时间。
  • 响应速度快
  • 截止时间的保证
  • 优先权准则
• 面向系统准则：
  • 系统吞吐量：单位时间完成的作业数。

调度算法

先来先服务FCFS

• First-Come，First-Served Scheduling：先来的进程先进行服务，直到完成或发生事件而阻塞后才放弃处理器。
• 有利于长作业（进程）。短作业带权周转时间过长。

短作业优先调度SJ(P)F

• 从后备队列中选择一个或若干个运行时间最短的作业（进程），调入内存运行。
• 对长作业不利。可能导致长作业长时间不被调度。
• 未考虑紧迫性。
• 作业时间长短是用户预估的，用户可能预估不准确。导致作业并非短作业优先。

优先级调度算法

• 不同抢占类型：
  • 非抢占式优先级：已分配处理器的进程使用结束后调度优先级最高的进程。用于对实时性要求不高的系统。
  • 抢占式优先级：当新建进程优先级更高时，立即切换当前进程，执行优先级最高进程。
• 优先权的类型
  • 静态优先权；优先权在创建时确定，进程的整个运行期间不变。
  • 动态优先权：进程推荐或随等待时间的增加而改变。

基于时间片的轮转调度算法

• 时间片轮转法：每个进程执行一个时间片，执行完毕后，调度程序停止该进程送至就绪队列末尾，分配给新进程处理器。
• 多级反馈队列调度算法：
  • 设置多个就绪队列：不同就绪队列优先级不同（优先级降低），运行时间片长度不同（时间片增加）。
  • 进队顺序：新进进程都进入第一个队列队末，每次执行后未完成则进入下一个队列队末。
  • 队列执行顺序：当某一个队列的前面的所有队列都空闲时，才执行该队列的进程。当高优先级进程在入队时，抢占式执行，但原运行进程送回原有队列。

实时调度

实时系统基本条件

• 需要一些必要信息：就绪时间，开始截止时间或结束截止时间，处理时间，资源需求，优先级。
• 系统处理能力强
• 适当的抢占调度机制
• 快速切换能力：对外部中断响应快，快速的任务分派能力。
• 分类方式：非抢占式轮转调度算法，非抢占式优先调度算法，基于时钟中断的抢占式优先权调度算法，立即抢占的优先权调度算法。
• 几种实例：最早截止时间优先算法 EDF(Earliest Deadline First)，最低松弛度优先级算法（最晚开始时间）。

产生死锁的原因和必要条件

死锁原因

• 资源竞争和进程推进顺序非法

必要条件

• 互斥条件
• 请求和保持条件
• 不剥夺条件
• 环路等待条件

处理的基本方法：

• 预防死锁：破坏四个必要条件
• 避免死锁：在资源分配时，避免进入这种不安全区的状态，从而避免死锁。
• 检测死锁：后两者配合在死锁之后采取措施解决问题。
• 解除死锁：

预防死锁的方法

预防死锁

• 摒弃“请求和保持”条件：一次性检测所有临界资源，不满足则等待
• 摒弃“不剥夺”条件：可能导致前一程序开始阶段工作无效
• 摒弃“环路等待”条件：对所有资源按类型进行现行排队，赋予不同序号。申请资源时必须按照次序申请。

系统安全状态

• 安全状态：系统以某种顺序为每个进程进行资源分配，直至满足每个进程对资源的最大需求，使得每个进程能够顺利地完成，如果不能找到这种顺序，则称为不安全状态。

银行家算法避免死锁

• 数据结构
  • 可利用资源变量 Available[j]
  • 最大需求矩阵 Max[i, j]
  • 分配矩阵 Allocation[i, j]
  • 需求矩阵 Need[i, j]
  • 存在关系 Need[i, j] = Max[i, j] - Allocation[i, j]
• 银行家算法
  1. Request_i[j] <= Need[i, j] 则转向 2。不满足则选部需求资源超过所宣布的最大值。
  2. Request_i[j] <= Available[j] 尚无足够资源，进程 i 等待。
  3. 尝试性分配资源给进程 i，并修改数据 Available[j]:=Available[j] - Request_i[j]; Allocation[i,j]:=Allocation[i,j]+Request_i[j]; Need[i,j]:=Need[i,j]-Request_i[j];
  4. 执行安全性算法，检查如果安全则分配，不安全则不分配，让 i 进程等待。
• 安全性算法
  • 设置变量
    1. 工作向量 Work:=Available
    2. 标记向量 Finish:= all false，标记：进程是否执行。
  • 寻找满足条件的进程，找到执行下一步，未找到执行最后一步
    1. Finish[i]:=flase 进程未完成
    2. Need[i, j] <= Work[j] 进程需求资源小于现有资源
  • 当进程或则资源顺利执行并释放资源
    1. 循环 j 执行 Work[j]:=Work[j] + Allocation[i, j] 释放资源
    2. Finish[i]:=true 标记程序已执行
  • 检查所有 Finish 若都为 true 则表示系统安全，否则处于不安全状态。

死锁的检测与解除

死锁的检测

• 资源分配图
  • 结点：$N = P \cup R$，P 进程，R 资源。
  • 边：p->r 资源请求，r->p 已完成的资源分配。一条线均为一个单位的分配量或请求量。
• 死锁定理
  • 资源分配图简化：将即不阻塞也不独立运行的结点 P，去掉，去除相关的所有边。
  • 通过不同的简化顺序得到的不可简化图是相同的。
  • 当前状态 S 为死锁等价于当且仅当 S 状态的资源分配图是不可完全简化的。

死锁的解除

• 剥夺资源
• 撤销进程