处理机的调度与死锁

处理机的调度和调度算法的目标

处理机的调度层次

1. 高级调度（长程调度、作业调度）
   • 场景：通道、作业队列、后备队列
   • 主要用于多道批处理系统中
   • 调度对象：作业：包含不止一个进程
   • 功能：根据某种算法，决定将外存上处于后备队列的哪几个作业调入内存
2. 低级调度（进程调度、短程调度）
   • 场景：内存、就绪队列
   • 进程调度是最基本的一种调度，在所有OS中都必须配置这级调度
   • 调度对象：就绪列表中的进程（或内核级线程）
   • 功能：根据某种算法，决定就绪队列中哪个进程应获得处理机，并由分派程序将处理机分配给被选中的进程
3. 中级调度（内存调度）
   • 场景：外存
   • 调度对象：挂起进程
   • 引入目的：提高内存利用率和系统吞吐量

处理机算法的目标

共同目标

资源利用率、公平性、平衡性、策略强制执行

1. 批处理系统的目标

   1. 平均周转时间短

      周转时间 = 作业在外存后备队列上等待调度的时间+进程在就绪队列上等待进程调度的时间+进程在CPU上执行的时间+进程等待I/O操作完成的时间

      1. 平均周转时间

         $T=\frac{1}{n}[\sum _{i=1}^n{T}_i]$

      2. 平均带权周转时间

         $T=\frac{1}{n}[\sum _{i=1}^n\frac{T_i}{T_s}]>1$

         Ti:作业的周转时间

         Ts：系统为它提供服务的时间

   2. 系统吞吐量高:单位时间内系统所完成的作业数

   3. 处理机利用率高

2. 分时系统的目标

   1. 响应快（及时接收、及时处理）
   2. 均衡性（独立性，多路性）

3. 实时系统的目标

   1. 截止时间保证
   2. 可预测性

作业与作业调度

批处理系统中的作业

1. 作业和作业步

   1. 作业：程序+数据+作业说明书

      在批处理系统中，是以作业为基本单位从外存调入内存

   2. 作业步

      往往是上一个作业步的输出作为下一个作业步的输入

   3. 作业流：

      若干作业进入系统被依次放在外存，便形成了作业流

2. 作业控制块（JCB）：作业在系统中存在的标志

3. 作业运行的三个阶段和三种状态

   1. 收容——后备状态
   2. 运行——运行状态
   3. 完成——完成状态

作业调度算法

主要任务

• 接纳多少个作业

  取决于多道程序度，即允许多少作业同时在内存中运行

• 接纳哪些作业

  取决于采用的调度算法

1. 先来先服务（FCFS）

   1. 优点：简单

   2. 缺点：FCFS 算法比较有利于长作业(进程)，而不利于短作业(进程)，只考虑了等待时间，忽视了作业运行时间。

2. 短作业优先（SJF）

   只考虑了运行时间，忽视了等待时间

   1. 优点：SJF 调度算法能有效地降低作业的平均等待时间，提高系统吞吐量。
   2. 缺点：
      1. 该算法对长作业不利
      2. 该算法完全未考虑作业的紧迫程度
      3. 必须预知作业运行时间，由于作业(进程)的长短只是根据用户所提供的估计执行时间而定的，而用户又可能 会有意或无意地缩短其作业的估计运行时间，致使该算法不一定能真正做到短作业优先调度。

3. 优先级调度算法（PSA）

   基于作业的紧迫程度，保证紧迫性作业（优先运行）

   1. 静态优先权：创建进程时确定，在进程整个运行期间保持不变

      确定进程优先级大小的依据

      • 进程类型：系统 >用户
      • 进程对资源的需求：要求少相应较高
      • 用户要求

   2. 动态优先权：创建进程之初，先赋予一个优先级，然后随进程的推进或等待时间的增加而改变，以便获取更好的调度性能

4. 高响应比优先调度算法

   $优先权=R_p=\frac{等待时间+要求服务时间}{要求服务时间}=\frac{响应时间}{要求服务时间}$

   $R_P$为响应比

   1. 优点：该算法既照顾了短作业，又考虑了作业到达的先后次序，不会使长作业长期得不到服务。因此，该算法实现了一种较好的折衷。
   2. 缺点：在利用该算法时，每要进行调度之前，都须先做响应比的计算，这会增加系统开销。

进程调度

进程调度的任务

保存处理机现场信息、按某种算法选取进程、把处理机分配给进程

进程的调度方式

1. 非抢占式

   一旦处理机分配给进程后，就一直让它运行下去，直到进程完成或被阻塞：引起进程调度的两个因素

2. 抢占式：现代OS的主要方式

   1. 优先权原则
   2. 短进程（作业）优先原则
   3. 时间片原则

进程调度算法

1. 轮转调度算法

   基于时间片的轮转，时间片大小略大于一次典型交互所需要的时间

   选择时间片大小因素

   1. 系统对响应时间的要求
   2. 就绪队列中进程数目
   3. 系统的处理能力

2. 优先级调度算法

   同作业调度中的算法

3. 多级反馈队列调度算法

   前面的算法如果未指明进程长度，则无法使用，而此算法无需知道各种进程所需执行时间

   

   1. 应设置多个就绪队列，并为各个队列赋予不同的优先级。第一个队列的优先级最高， 第二个队列次之，其余各队列的优先权逐个降低。
   2. 当一个新进程进入内存后，首先将它放入第一队列的末尾，按 FCFS 原则排队等待 调度。当轮到该进程执行时，如它能在该时间片内完成，便可准备撤离系统；如果它在一 个时间片结束时尚未完成，调度程序便将该进程转入第二队列的末尾，再同样地按 FCFS 原则等待调度执行；如果它在第二队列中运行一个时间片后仍未完成，再依次将它放入第 三队列，……，如此下去
   3. 仅当第一队列空闲时，调度程序才调度第二队列中的进程运行；仅当第 1～(i-1)队 列均空时，才会调度第 i 队列中的进程运行。

   可以较好的满足各类用户的需要

   1. 终端型作业用户。由于终端型作业用户所提交的作业大多属于交互型作业，作业通常较小，系统只要能使这些作业(进程)在第一队列所规定的时间片内完成，便可使终端型作 业用户都感到满意。
   2. 短批处理作业用户。对于很短的批处理型作业，开始时像终端型作业一样，如果仅在第一队列中执行一个时间片即可完成，便可获得与终端型作业一样的响应时间。对于稍长的作业，通常也只需在第二队列和第三队列各执行一个时间片即可完成，其周转时间仍 然较短。
   3. 长批处理作业用户。对于长作业，它将依次在第 1，2，…，n 个队列中运行，然后 再按轮转方式运行，用户不必担心其作业长期得不到处理。

实时调度

实时调度的基本条件

1. 提供必要的基本信息

   1. 就绪时间

   2. 开始截止时间和完成截止时间

   3. 处理时间

      开始截止时间 + 处理时间 = 完成截止时间

   4. 资源要求

   5. 优先级

2. 系统处理能力强：如果不强，可能会导致某些任务得不到及时处理

   $C_i：处理时间，P_i是周期时间$

   1. 单处理机情况下：

      $\sum _{i=1}^m\frac{C_i}{P_i}<=1$

   2. 在N核处理机的情况下：

      $\sum _{i=1}^m\frac{C_i}{P_i}<=N$

   3. 采用抢占式

实时调度算法

1. 最早截止时间优先EDF

   根据截止时间确定任务的优先级

2. 最低松弛度优先算法LLF

   根据任务的松弛程度

   $松弛度=必须完成时间-其本身的运行时间-当前时间=最早开始时间-当前时间$

死锁

死锁概述

1. 产生死锁原因

   • 竞争不可抢占或可消耗资源
   • 进程推进顺序不当

2. 死锁定义

   如果一组进程中的每一个进程都在等待仅由该组进程中其他进程才能引发的事件，那么该组进程是死锁的

3. 产生死锁的必要条件

   1. 互斥条件
   2. 请求和保持条件
   3. 不可抢占条件
   4. 循环等待条件

4. 处理死锁的方法

   1. 预防死锁：针对必要条件入手，排除产生死锁的可能性
   2. 避免死锁：在资源动态分配过程中，防止系统进入不安全状态，减少产生死锁的可能性
   3. 检测死锁
   4. 解除死锁

预防死锁

1. 破坏“请求和保持”条件

   1. 第一种协议：一次性申请其在整个运行过程中需要的全部资源

      • 优点：简单、易行且安全
      • 缺点：资源浪费
      • 进程常会产生饥饿现象

   2. 第二种协议：在第一种协议的基础上，在运行过程中逐步释放已分配给自己的、且已用毕的全部资源

      提高设备利用率，减少进程发生饥饿现象

2. 破坏“不可抢占”条件

   实现复杂，延长周转时间、增加系统开销、降低了吞吐量

3. 破坏“循环等待”条件

   对系统所有资源类型进行线性排序后、规定每个进程必须按照序号递增的顺序请求资源。

   如果一个进程已经请求了较高的资源后又想请求一个序号低的资源，必须将所有相同或者更高的资源释放掉，才能申请序号低的资源

   1. 优点：较上面两种方法，资源利用率和系统吞吐量都有较明显的改善
   2. 缺点：序号问题带来不便

避免死锁

1. 系统安全状态

   当系统处于安全状态时，可避免发生死锁。反之，当系统处于不安全状态时，则可能进入到死锁状态

   安全状态：系统能按照某种进程推进顺序$（P_1,P_2,...,P_n）$为每个进程$P_i$分配其所需资源，直至满足每个进程对资源的最大需求，使每个进程都可以顺利完成，此时称$（P_1,P_2,...,P_n）$为安全序列

   系统在进行资源分配前，应先计算此次资源分配的安全性

2. 利用银行家算法避免死锁

   1. 数据结构

      • 可利用资源向量Available[n],每个元素代表一类可利用资源数目
      • 需求矩阵Need[m][n]，用以表示每个进程尚需各类资源数
      • 分配矩阵Allocation[m][n],用以表示每个进程已分配各类资源数
      • 最大需求矩阵Max[m][n],定义了系统中每个进程对各资源的最大需求量

      $Need[i][j]=Max[i][j]-Allocation[i][j]$

   2. 银行家算法

      设$Reques{t}_i$是进程$ P_i$的请求向量，$Request_i[j] = K$表示进程$P_i$需要K个$R_j$类型的资源

      1. 合理性检查：$Reques{t}_i[j]<=Need[i][j]$,合理则下一步，否则出错

      2. 可用性检查：$Reques{t}_i[j]<=Available[j]$,有可用资源则下一步，否则等待

      3. 预分配：系统试探着把资源分配给进程$P_i$,并修改数据结构的值

         $$\begin{gathered} Available[j]-=Reques{t}_i[j]; \\ Allocation[i][j]+=Reques{t}_i[j] \\ Need[i][j]-=Reques{t}_i[j] \end{gathered}$$

      4. 执行安全性算法

         1. 设置两个数据结构：1.Work = Available 2.Finish初始化为False,标记是否有足够资源满足进程

         2. 从进程集合中找到一个满足下述条件的进程

            • Finish[i] = False
            • Need[i][j] <= Work[j]

            若找到执行下一步，否则执行步骤4

         3. 当进程$P_i$获得资源后可顺利执行，直至完成，并释放出分配给它的资源

            $$\begin{gathered} Work[j]+=Allocation[i][j] \\ Finish[i]=True \\ gotostep2 \end{gathered}$$

         4. 如果所有进程的Finish[i] = True都满足则表示处于安全状态，否则处于不安全状态

死锁的检测与解除

资源分配图

1. 死锁定理

   1. 在资源分配图中找出一个既不阻塞又非独立的进程结点$P_i$
   2. $P_i$释放后，重复1操作，直到无法释放为止
   3. 经过上述操作，若能去掉图中所有的边，使所有进程结点都成为孤立点，则称该图可完全简化

   当且仅当S状态的资源分配图是不可完全简化的是S为死锁状态的充要条件

2. 死锁的解除

   1. 抢占资源
   2. 终止进程