处理机调度与死锁

处理机调度的层次

高级调度/作业调度/长程调度

• 作用：将外存后备队列中的作业调入内存
• 对象：作业

作业：比程序更泛的一个概念，通常包含程序、数据以及作业说明书，批处理系统中，以作业为基本单位从外存调入内存

作业步：作业中的步骤

作业流：进入系统后，在外存中排队的作业，形成输入作业流，在系统控制下进行处理，形成处理作业流

作业控制块：JCB，是作业在系统中存在的标志，保存了系统对作业进行管理和调度所需要的全部信息

低级调度/进程调度/短程调度

• 作用：决定哪个进程应该获得处理机
• 对象：进程
• 基本机制
  • 排队器：提高进程调度的效率，将就绪的进程按照一定的方法排成一个或者多个队列
  • 分派器：把由进程调度所选中的进程，从就绪队列中取出，然后进行上下文切换，将处理机分配给它
  • 上下文切换机制：当对处理机进行切换时，会执行两次上下文切换，1. 保存当前进程的上下文，载入分派程序上下文，2. 移出分派进程，载入新选进程的上下文信息
• 调度方式
  • 非抢占式方式：只要进程在执行，则不抢占其处理机
  • 抢占方式
    • 优先权原则：允许优先权高的进程抢占当前进程的处理机
    • 短作业/进程优先
    • 时间片原则

中级调度/中程调度

• 作用：提高内存利用率和系统吞吐量，将暂时不能运行的进程调至外存上等待，也就是将其挂起
• 对象：进程

调度队列模型和调度准则

调度队列模型

• 仅有进程调度的调度队列模型
• 具有高级和低级调度的调度队列模型
  • 就绪队列一般采用高优先权优先调度算法
  • 设置多个阻塞队列
• 同时具有三级调度的调度队列模型

选择调度方式和调度算法的准则

• 面向用户的准则
  • 周转时间短
    • 周转时间：作业从被提交到作业完成这段时间(作业在外存后备队列等待调度的时间，进程就绪队列上等待时间，进程在CPU上执行的时间，进程等待I/O操作完成的时间)
    • 平均带权周转时间：W = 1/n * sum(Ti/Ts) 其中Ti 指的是作业的周转时间，Ts指的是作业的服务时间
  • 响应时间快
    • 响应时间：从请求发出到收到回应的时间
  • 截止时间的保证
    • 截止时间：任务必须开始执行的最迟时间
  • 优先权保证
• 面向系统的准则
  • 系统吞吐量高
    • 吞吐量：单位时间内完成的作业数
  • 处理机利用率好
  • 各类资源的平均使用

调度算法

先来先服务调度算法(FCFS)

• 应用场景：作业调度、进程调度
• 运作方式
  • 作业调度：每次调度都是从后备队列中选择一个或者多个最先进入该队列的作业，将其调入内存
  • 进程调度：从就绪队列中选择一个最先进入该队列的进程，为其分配处理机
• 特性：有利于长作业/进程，不利于短作业/进程

• 案例

  
  
  先来先服务调度算法
  
  

  可以看到，D的要求服务时间只有2，但是其带权周转时间到达5.5，而长作业C的周转时间则只有2，可以得出结论，先来先服务调度算法有利于CPU繁忙型的作业

短作业/进程优先调度算法(SJF/SPF)

• 应用场景：作业调度、进程调度
• 运行方式
  • 作业调度：从后备队列中选择一个或若干个估计运行时间最短的作业，将其调入内存运行
  • 进程调度：从就绪队列中选出一个估计运行时间最短的进程，将处理机分配给它，使其一直执行到完成，或者因某事而被阻塞放弃处理机时再重新调度
• 特性：有效降低作业的平均等待时间，提高系统的吞吐量

• 案例

  
  
  短作业优先调度算法
  
  

  可以看到，无论是平均周转时间还是带权平均周转时间，短作业优先调度算法均低于先来先服务调度算法，尤其是短作业D的带权周转时间，从5.5下降到1.5

• 缺点：对长作业不利，可能导致长作业一直未能分配到处理机，完全未考虑作业的紧迫程度，作业长短只是估计值，并不一定准确

高优先权优先调度算法(FPF)

• 应用场景：作业调度、进程调度
• 运行方式
  • 作业调度：从后备队列中选择若干个优先权最高的作业装入内存
  • 进程调度：把处理机分配给就绪队列中优先权最高的进程
• 细分
  • 非抢占式优先权调度算法
    • 一旦把处理机分配给就绪队列中优先权最高的进程后，该进程便可以一直执行下去，直至完成；或者因某事而主动放弃处理机
  • 抢占式优先权调度算法
    • 在执行期间，如果出现了另一个优先权更高的进程，进程调度程序立即停止当前进程，重新将处理机分配给新来的优先权最高的进程
• 优先权类型
  • 静态优先权：创建进程时确定，并且在进程运行期间一直保持不变
  • 动态优先权：在运行期间可以动态改变进程的进程的优先权
• 高响应比优先调度算法
  • 动态地调整优先权的一种基于抢占式的调度算法
  • 响应比：Rp = (等待时间+要求服务时间)/要求服务时间 = (响应时间)/要求服务时间
  • 特点：既照顾了短作业、也考虑了作业到达次序，也能保证长作业能够得到服务，但是每次调度前，都需要做响应比计算

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

时间片轮转法

多级反馈调度算法

1. 设置多个就绪队列，并为各个队列赋予不同的优先级，第一个队列优先级最高，依次递减，各个队列的执行时间片也不同，优先权越高，时间片越短，依次增加一倍
2. 当一个新的进程进入内存之后，将其放入第一队列的末尾，按照FCFS原则排队等待调度，如果在指定时间内未能完成，则转入第二队列的末尾...
3. 只有当第一队列为空时，调度程序才会启动第二队列中的进程运行，仅当第1_{i-1队列中均为空时，才会调度第i队列中，如果处理机此时在为i队列某进程服务，有新的进程进入1}i-1中任意队列，则发生调度，先执行该进程，并且把当前进程放入i队列的末尾

性能：满足多种作业的需求。

实时调度

实现实时调度的基本条件

• 提供必要的信息
  • 就绪时间
  • 开始截止时间和完成截止时间
  • 处理时间
  • 资源要求
  • 优先级
• 系统处理能力强
• 假设有m个硬实时任务，则需要满足 sum(ci/pi) <=1 ci为执行该进程所需时间，pi为该进程的周期时间
• 采用抢占式调度机制
• 具有快速切换机制
  • 对外部中断的快速响应能力
  • 快速的任务分派能力

实时调度算法的分类

• 非抢占式调度算法(小型实时系统、要求不太严格的实时控制系统)
  • 非抢占式轮转调度算法
  • 非抢占式优先调度算法
• 抢占式调度算法(要求比较严格)
  • 基于时钟中断的抢占式优先权调度算法：时钟中断到来才发生切换
  • 立即抢占的优先权调度算法

常用的实时调度算法

• 最早截止时间优先(EDF)算法
• 非抢占式调度方式用于非周期性实时任务
• 抢占式调度方式用于周期性实时任务
• 最低松弛度/紧急程度优先(LLF)算法
  • 松弛度 = 截止时间 - 完成该任务所需要的时间 - 当前时间
  • 松弛程度越低越先调度

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

死锁：多个进程在运行过程中因争夺资源而造成的一种僵局，在没有外力的作用下，它们都无法再向前进

产生死锁的原因

• 竞争资源：共享资源数量不足以满足进程的需要
• 进程间的推进顺序非法：请求和释放资源的顺序不当

产生死锁的必要条件

• 互斥条件：一段时间内某个资源只能被一个进程占用
• 请求和释放：进程至少拥有一个资源，并且又请求了其他资源
• 不剥夺资源：进程已经拥有的资源，在未使用完之前，不能别剥夺，只能使用完自己释放
• 环路等待：发生死锁时，必然存在一个进程-资源的环形链

预防死锁的产生

所谓预防死锁，其实就是破坏产生死锁的四个必要条件之一，使得死锁条件不成立，从而达到预防死锁的目的

• 摒弃请求和保持条件：一次性申请所需要的全部资源，只要有一种资源不满足，则先等待
  • 缺点：资源利用率低，进程延迟运行
• 摒弃不剥夺条件：当一个进程申请资源不满足时，释放自己拥有的所有资源，以后重新申请
  • 缺点：复杂、代价大
• 摒弃环路等待条件：所有资源进行线性排队，赋予不同的序号，请求资源时，只能按照资源序号递增的次序提出
  • 缺点：资源序号必须稳定、限制编程的简单性

避免死锁的产生

把系统的状态分为安全状态和不安全状态，只要能使系统处理安全状态，就可以避免死锁

• 安全状态

  • 允许系统动态地申请资源，但系统在进行资源分配之前，应先计算此次资源分配的安全性
  • 安全状态：系统能按照某种进程顺序(p1, p2, p3, ...)称其为安全序列来为每个进程Pj分配其所需要的资源

• 银行家算法 -- 避免死锁的有效方法

  • 数据结构
    • 可利用资源向量 Available：m个元素的数组，初始值为系统中所分配的该类全部可用资源的数目
    • 最大需求矩阵 Max：n*m矩阵，定义了n个进程中每个进程对m类资源的最大需求
    • 分配矩阵 Allocation：n*m矩阵，定义了系统中每一类资源当前已经分配给进程的资源数
    • 需求矩阵 Need：n*m矩阵，用于表示每一个进程尚需的各类资源数
    • Need[i, j] = Max[i, j] - Allocation[i, j]
  • 银行家算法
    • 假设：Ri是进程Pi的请求向量，若Ri[j] = k， 则表示Pi需要k个Rj类型的资源
    1. 如果Ri[j] <= Need[i, j]，则转向2，否则出错：请求资源多于需要的资源
    2. 如果Ri[j] <= Available[j]，转向3，否则，表示目前暂无资源可用，Pi需要等待
    3. 系统尝试分配资源给Pi，并且修改下面信息
    • Available[j]：= Avaliale[j] - Ri[j]
    • Allocation[i,j] = Allcation[i, j] + Ri[j]
    • Need[i, j] = Need[i, j] - Ri[j]
    4. 执行安全性算法，检查此次分配后系统是否处于安全状态，如果安全，才真正将资源分配给进程Pi，否则，将资源恢复为原来的状态，让Pi等待
  • 安全性算法
    1. 设置两个向量
    • 工作向量Work，表示系统可提供给进程所需的各类资源数目，含有m个元素，开始时，Work：= Available
    • Finish，表示系统是否有足够的资源分配给进程，使之运行完成，初始值为Finish[i]：= false，当有足够资源时，再令Finish[i]：= true
    2. 从进程集合中找到一个能满足下述条件的进程
    • Finish[i]：= false
    • Need[i ,j] <= Work[j]， 若找到，执行下面步骤3，否则，执行步骤4
    3. 当进程Pi获得资源后，可顺利执行，直至完成，并释放出给它的资源
    • Work[j]：= Work[j] + Allocation[i ,j]
    • Finish[i]：= true
    • 继续执行步骤2
    4. 如果所有的Finish[i] = true 满足，则表示系统处于安全状态；否则，系统处于不安全状态

  • 案例

    
    
    t0时刻资源分配情况
    
    

    求问t0时刻的安全性：

    
    
    一种可行的分配顺序
    
    从而可以得出一种满足条件的顺序，也就是说明当前状态是安全的
    如果P1发出请求向量req(1, 0, 2)，问是否可以分配
    

    先检查 req(1, 0, 2) <= Need(1, 2, 2) 满足，
    再检查req(1, 0, 2) <= Available(3, 3, 2) 满足，尝试将该请求的资源进行分配，然后重新计算一下能否满足安全算法即可，这里省略

死锁的检测与解除

• 资源分配图：圆圈代表进程，方框代表资源，方框中的点代表资源的数量
• 死锁定理：如果能将该资源分配图简化到所有的节点都是孤立节点，则说明不存在死锁，否则，存在死锁

死锁解除

• 剥掉资源：从其他进程剥夺资源，分配给死锁进程，使其打破死锁
• 撤销进程
  • 撤销所有死锁进程
  • 每次选择代价最小的进程进行撤销，直至死锁解除