第三章 处理机调度与死锁

3.1 处理机调度的层次和调度算法的目标

3.1.1 处理机调度的层次

调度名称	别名	调度对象/目的	主要功能	作用域	频率
高级调度	长程调度或作业调度	作业	根据某种算法，决定将外存上处于后备队列中的哪几个作业调入内存，为他们创建进程、分配必要的资源，并将它们放入就绪队列	主要用于多通道批处理系统中，在分时和实时系统中不设置高级调度	最低
低级调度	进程调度或短程调度	进程（内核级线程）	根据某种算法，决定就绪队列中的哪个进程应获得处理机，并由分派程序将处理机分配给被选中的进程	最基本的一种调度，在多道批处理、分时和实时三种类型的OS中，都必须配置这级调度	最高
中级调度	内存调度	提高内存利用率和系统吞吐率	将那些暂时不能运行的进程，调至外存等待，此时的状态称为就绪驻外存状态（或挂起状态）将已具备运行条件的就绪进程重新调入内存，并修改为就绪状态，挂在就绪队列上的等待。中级调度实际上就是存储器管理中的对换功能	内存、外存	适中

3.1.2 处理机调度算法的目标

1. 处理机调度算法的共同目标

   （1）资源利用率

   

   （2）公平性

   ​ 目的：使诸进程都获得合理的CPU时间，不会发生饥饿想象。

   ​ 公平性是相对的，对相同类型的进程应获得相同的服务；但对于不同类型的进程，由于其紧急程度或重要性的不同，应提供不同的服务。

   （3）平衡性

   ​ 目的：使系统中的CPU和各种外部设备经常处于忙碌状态。调度算法尽可能保持系统资源使用的平衡性。

   （4）策略强制执行

   ​ 对所制定的策略其中包括安全策略，只要需要，就必须予以准确地执行，即使会造成某些工作的延迟也要执行。

2. 批处理系统的目标

   （1）平均周转时间短

   ​ 周转时间：指从作业被提交给系统开始，到作业完成为止的这段时间间隔。

   ​ 包括四部分：作业在外存后备队列上等待调度的时间；

   ​ 进程在就绪队列上等待进程调度的时间；

   ​ 进程在CPU上执行的时间；

   ​ 进程等待I/O操作完成的时间。

   ​ 平均周转时间：
   ​ 平均带权周转时间：

   ​ T_s：系统为它提供服务的时间；

   （2）系统吞吐量高

   ​ 定义：在单位时间内系统所完成的作业数；

   ​ 单纯提高：尽量多地选择短作业运行（原因：与批处理作业的平均长度有关）；

   （3）处理机利用率高

   ​ 单纯提高：尽量多地选择计算量大的作业运行；

3. 分时系统的目标

   （1）相应时间快

   ​ 响应时间：从用户通过键盘提交一个请求开始，知道屏幕上显示出处理结果为止的一段时间间隔；

   ​ 包括三部分：请求信息从键盘输入开始，直至将其传送到处理机的时间；

   ​ 处理机对请求信息进行处理的时间；

   ​ 将所形成的相应信息回送到终端显示器的时间。

   （2）均衡性

   ​ 定义：指系统响应时间的快慢应与用户所请求服务的复杂性相适应；

4. 实时系统的目标

   （1）截止时间的保证

   ​ 截止时间：某任务必须开始执行的最迟时间或必须完成的最迟时间；

   （2）可预测性

3.2 作业与作业调度

3.2.1 批作业系统中的作业

1. 作业和作业步

   （1）作业：包含了通常的程序和数据，还应配有一份作业说明书，系统根据该说明书来对程序的运行进行控制。在批处理系统中，是以作业为基本单位从外存调入内存的

   （2）作业步：在作业运行期间，每个作业必须经过若干个相对独立，又相互关联的顺序加工步骤才能得到结果。我们将其中每一个加工步骤成为一个作业步

2. 作业控制块（JCB）

   定义：是作业在系统中存在的标志，其中保存了系统对作业进行管理和调度所需的全部信息；

   包含内容：作业标识、用户名称、用户账号、作业类型（CPU繁忙型、I/O繁忙型、批量型、终端型）、作业状态、调度信息（优先级、作业运行时间）、资源需求（预计运行时间、要求内存大小等）、资源使用情况。

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

   （1）收容阶段（后备状态）：将用户提交的作业通过某种方式或 SPOOLing 系统输入到硬盘上，再为其建立 JCB ，并把它放入后备队列中；

   （2）运行阶段：从第一次进入就绪状态开始，直至运行结束前；

   （3）完成阶段：当作业运行完成、或发生异常情况而提前结束时；

3.2.2 作业调度的主要任务

别名：接纳调度

1. 接纳多少个作业：从后备队列中选取多少作业调入内存，取决于多道程序度，即允许多少个作业同时在内存中运行；
2. 接纳哪些作业：取决于所采用的的调度算法；

3.2.3 进程调度的主要任务

1. 进程调度的任务

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

2. 进程调度机制

   • 排队器：为了提高进程调度的效率，应事先将系统中的所有就绪进程按照一定的策略排成一个队列或多个队列，以便调度程序能最快地找到它。

     

   • 分派器

     依据进程调度所选定的进程，将其从就绪队列中取出，然后进行从分派器到新选出进程间的上下文切换，将处理机分配给新选出的进程；

   • 上下文切换器

     在对处理机进行切换是，会发生两队上下文的切换操作

     ① 第一队上下文切换时，OS将保存当前进程的上下文，即把当前进程的处理机寄存器内容保存到该进程的进程控制块内的相应单元，再装入分派程序的上下文，以便分派程序的运行；

     ② 第二队上下文切换是移出分派程序的上下文，而把新选进程的CPU现场信息装入到处理机的各个相应寄存器中，以便新选进程进行；

3. 进程调度方式

   （1）非抢占方式引起的因素：

   ​ ① 正在执行的进程运行完毕，或因发生某事件而使其无法再继续运行；

   ​ ② 正在执行中的进程因提出 I/O 请求而暂停执行；

   ​ ③ 在进程通信或同步进程中，执行了某种原语操作；

   （2）抢占方式的主要原则：

   ​ ① 优先权原则

   ​ ② 断进程优先原则

   ​ ③ 时间片原则

3.2.3 调度算法

1. 先来先服务调度算法（FCFS）

   FCFS调度算法是一种最简单的调度算法，该算法既可以用于作业调度也可以用于进程调度，对于优先进入队列的进行优先调度。

   FCFS算法属于不可剥夺算法；

   FCFS调度算法的特点是算法简单，但效率低；对长作业比较有利，但对短作业不利（相对SJF和高响应比）；有利于CPU繁忙型作业，而不利于I/O繁忙型作业。

2. 短作业优先的调度算法（SJF）

   从后备队列中选取一个或若干个估计运行时间最短的作业，将它们调入内存运行；

   SJF算法可以分别用于作业调度和进程调度；

   SJF算法缺点：

   • 必须预知作业的运行时间；
   • 对长作业非常不利；
   • 在采用FCFS算法时，人机无法实现交互；
   • 该调度算法完全未考虑作业的紧迫程度，故不能保证紧迫性作业能够得到及时处理。

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

   基于作业的紧迫程度，由外部赋予作业相应的优先级，调度算法根据该优先级进行调度的；

   • 作业调度：优先级调度算法每次从后备作业队列中，选择优先级最高的一个或几个作业，将它们调入内存，分配必要的资源，创建进程并放入就绪队列。

   • 进程调度：优先级调度算法每次从就绪队列中选择优先级最高的进程，将处理机分配给它，使之投入运行。

   • 优先级算法的类型

     （1）非抢占式优先级调度算法

     （2）抢占式优先级调度算法

   • 优先级类型

     （1）静态优先级

     ​ ① 进程类型，通常系统进程（接受进程、对换进程）得到优先级高于一般用户进程的优先级；

     ​ ② 进程对资源的需求，对资源要求少的进程应赋予较高的优先级；

     ​ ③ 用户要求，根据进程的紧迫程度及用户所付费用的多少确定优先级；

     静态优先级算法简单易行，系统开销小，但不够精确，可能会出现优先级低得进程长期没有被调度的情况

     （2）动态优先级

     ​ 定义：指在创建进程之初，先赋予其一个优先级，然后其值随进程的推进或等待时间的增加而改变，以便获得更好的调度性能；

4. 高响应比优先调度算法（HRRN）是FCFS算法和SJF算法的一种折中算法
   

5. 时间片转轮调度算法（RR）

   属于可剥夺式算法

   按照固定的时间片，来进行当前进程；

   缺点：时间片很长，有利于短作业，但这也意味着会频繁地执行进程调度和进程上下文的切换，这无疑会增加系统的开销；反之时间太长RR算法便退化为FCFS算法，无法满足短作业和交互式用户的需求；

   时间片的长短通常由以下因素确定：系统的响应时、就绪队列中的进程数目和系统的处理能力；

6. 多队列调度算法

   该算法将系统中的进程就绪队列从一个拆分为若干个，将不同类型或性质的进程固定分配在不同的就绪队列，不同的就绪队列就采用不同的调度算法，一个就绪队列中的进程可以设置不同的优先级，不同的就绪队列本身也可以设置不同的优先级

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

   1. 调度机制

      （1）设置多个就绪队列

      （2）每个队列都采用FCFS算法

      （3）按队列优先级调度

   2. 调度算法的性能

      （1）终端型用户：多作业优先；

      （2）短批处理作业用户：周转时间短；

      （3）长批处理作业用户：经过前面几个队列得到部分执行，不会长期得不到处理；

      

8. 基于公平原则的调度算法

   1. 保证调度算法
   2. 公平分享调度算法

3.3 实时调度

3.3.1 实现实时调度的基本条件

• 提供必要的信息

  1. 就绪时间
  2. 开始截止时间和完成截止时间
  3. 处理时间
  4. 资源要求
  5. 优先级

• 系统处理能力强

  • 必须满足下面的限制条件系统才是可调度的：

    ==例：==假定系统中有m个周期性的硬实时任务HRT，它们的处理时间课表示为C_i，周期时间表示为P_i，则在单处理机情况下，必须满足下面的限制条件系统才是可调度的：

    注：上述限制条件并未考虑到任务切换所花费的时间，因此，当利用上述限制条件是，还应适当地留有余地；

  • 提高系统处理能力的途径：

    1. 采用单处理机系统，但须增强其处理能力，以显著地减少对每一个任务的处理时间；
    2. 采用多处理机系统，假定系统中的处理机数为N，则应将上述的限制条件改为：

• 采用抢占式调度机制

• 具有快速切换机制

  1. 对中断的快速响应能力；

  2. 快速的任务分派能力；

3.4 死锁

3.4.1 资源问题

1. 可重用性资源和消耗性资源

   • 可重用性资源

     1. 每一个可重用次元中的单元只能分配给一个进程使用，不允许多个进程共享。
     2. 进程在使用可重用资源时，须按照这样顺序：① 请求支援 ② 使用资源 ③ 释放资源；
     3. 系统中每一类可重用性资源中的单元数目是相对固定的，进程在运行期间既不能创建也不能删除它；

   • 可消耗性资源（临时性资源）

     性质：
     ① 每一类可消耗性资源的单元数目在进程运行期间是可以不断变化的，有时它可以有许多，有时可能为0；

     ​ ② 进程在运行过程中，可以不断地创造可消耗性资源的单元，将它们放入该资源类的缓冲区中，以增加该资源类的单元数目；

     ​ ③ 进程在运行过程中，可以请求若干个可消耗性资源单元，用于自己的消耗，不再将它们返回给该资源类中。

2. 可抢占性资源和不可枪战性资源

   • 可抢占性资源
   • 不可抢占性资源

3.4.2 计算机中的死锁

1. 竞争不可抢占性资源引起死锁

   P1和P2在分别同时拥有F1和F2后互相抢夺对方（当前F类资源属于可重用且不可抢占性资源）

2. 竞争可消耗资源引起死锁

3. 进程推进顺序不当引起死锁

   • 进程推进顺序合法
   • 进程推进顺序非法

3.4.3 死锁的定义、必要条件和处理方法

• 定义：如果一组进程中的每一个进程都在等待仅有该组进程中的其他进程才能引发的时间，则该组进程是死锁；

• 产生死锁的必要条件

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

• 处理死锁的方法

  1. 预防死锁

  2. 避免死锁

  3. 检测死锁

  4. 解除死锁

     上述方法，对死锁的防范程度逐渐减弱，但对应的是志愿利用率的提高，以及进程因资源因素而阻塞的频度下降（即并发程度提高）

3.5 预防死锁

3.5.1 破坏“请求和保持”条件

1. 第一种协议
   • 该协议规定。所有进程在开始运行前，必须一次性地申请其在整个运行过程中所需的全部资源
   • 优点：简单、易行且安全；
   • 缺点：
     • 资源被严重浪费
     • 使进程经常会发生饥饿现象
2. 第二种协议
   • 对第一种做出了相应的改进，进程申请所需的资源后，在进程运行过程中在逐步释放已分配给自己、且已用毕的全部资源，然后再请求新的所需资源；
   • 优劣：可以提高设备利用率，还可以减少进程发生饥饿的机率；

3.5.2 破坏“不可抢占”条件

• 此方法实现起来比较复杂，且需付出很大的代价。（打印机、CD刻录机的抢占），该策略还可能因为反复地申请和释放资源致使进程的执行被无限地推迟，这不仅延长了进程的周转时间，而且也增加了系统开销，降低了系统吞吐量。

3.5.3 破坏“循环等待”条件

• 前提：对所有资源类型进行线性排序

• 接着规定每个进程必须按序号递增的顺序请求，一个进程在开始时，可以申请某类资源R_i的单元，以后，当切仅当F（R_j）> F（R_i）时，进程才可以请求资源R_j的单元。

• 若需要多个同类资源单元，则必须一起请求；

• 劣势：

  • 为系统中各类资源所规定的序号必须相对稳定，这就限制了新类型设备的增加；
  • 尽管在为资源的类型分配序号是，已经考虑到大多数作业在实际使用这些资源时的顺序，但也经常会发生这种情况：作业使用各类资源的顺序与系统规定的顺序不同，造成对资源的浪费；
  • 为方便用户，系统对用户在编程时所施加的限制条件应尽量少，然而这种按照规定次序申请资源的方法必然会限制用户简单、自主地编程；

3.6 避免死锁

3.6.1 系统安全状态

• 安全状态不是死锁状态

• 安全状态是没有死锁的状态

• 死锁状态是不安全状态

• 不是所有不安全状态都是死锁状态

  

3.6.2 利用银行家算法避免死锁

• 新进程进入系统是，必须申明在运行过程中，可能需要每种资源类型的最大单元数目，其数目不应超过系统所拥有的的资源总量。当进程进一步请求资源时，系统必须首先确定是否有足够的资源分配给该进程。若有，再进一步计算在将这些资源分配给进程后，是否会使系统处于不安全状态，如果不会，才将资源分配给它，反之让进程等待；

• 银行家算法中的数据结构

  1. 可利用资源向量Available
  2. 最大需求矩阵Max
  3. 分配矩阵Allocation
  4. 需求矩阵Need
  5. 工作向量Work[ ]，用于安全检查过程中记录Available[ ]的变化
  6. Finished[ ]，安全检查过程中记录各个进程是否能够完成

• 安全算法Safe( )
  

3.7 死锁的检测与解除

3.7.1 死锁的检测

• 定义：死锁检测算法用于检测系统状态，以确定系统中是否发生了死锁

• 死锁检测中的数据机构：

  1. 可利用资源向量Available，表示m类资源中每一类资源的可用数目；
  2. 把不占用资源的进程（向量Allocation = 0）计入L表中，即L_i∪L；
  3. 从进程集合中找到一个Request_i <= Work的进程，做如下处理：①把其资源分配图简化，释放出资源，增加工作向量Work= Work + Allocation_i；② 将它计入L表中；
  4. 若不能把所有进程都计入L表中，便表明系统状态S的资源分配图是不可完全简化的。因此，该系统状态将发生死锁；

• 算法：
  
  

3.7.2 死锁的解除

（1）抢占资源；

（2）终止（或撤销）进程；

• 终止进程的方法：

  1. 终止所有死进程（付出代价较大）
  2. 逐个终止进程（需考虑如下因素）
     • 进程的优先级大小
     • 进程已执行了多少时间，还需要多少时间方能完成？
     • 进程在运行中已经使用资源的多少，以后还需要多少资源？
     • 进程的性质是交互式还是批处理式

• 付出代价最小的死锁解除算法：

  所花费代价：R(S)_min = min{C_ui} + min{C_uj} + min{C_uk} + ···