操作系统 3.处理机调度与死机

重点

调度层次和调度队列模型；

处理机调度算法及其运用；

如何理解实时调度的“实时”含义；

实时调度算法；

死锁概念的理解，产生死锁的原因；

产生死锁的必要条件；

死锁解决措施。

3.1 处理机调度的层次

3.1.1三级调度

• 高级调度：即作业调度，宏观调度或长程调度。其任务是对那些提交给系统后被收容的作业, 按照一定策略选择出某些作业, 为其分配内存等必要的资源, 建立与之对应的进程, 并将进程的PCB表放入就绪队列中, 使其具备参与竞争使用CPU的权利。作业状态变迁如图

  

• 低级调度：即进程调度，微观调度或短程调度。其任务是在进入内存并处于就绪队列的进程中, 确定哪个进程真正获得CPU及其使用CPU的时间。用执行指针指向选中进程的PCB表，将它从就绪队列移出并重布现场，使其运行。进程状态变迁如图

  

• 中级调度：将就绪状态细化为内存就绪和外存就绪状态， 阻塞状态细化为内存阻塞和外存阻塞状态后，中级调度完成进程在内存与外存之间的对换。其任务是周期性地将那些在内存中暂时不用的进程换出并放到外存，而将那些在外存上需要运行的进程换入到内存。进程状态变迁如图

  

• 三级调度模型

  

3.1.2进程调度的功能

• 在某一给定时刻，决定哪个就绪进程运行、运行多长时间以及如何保证进程的运行，就是进程调度的主要工作
  • 记录系统中所有进程的状态、优先数和资源的需求情况。
  • 确定调度算法。决定将CPU分配给哪个进程及多长时间。
  • 分配处理机给进程。进行CPU现场的保护和移交，并实现CPU使用权的移交。

3.1.3进程调度方式

• 1.非抢占方式：在非抢占方式下，调度程序一旦把 CPU分配给某一进程后便让它一直运行下去，直到进程完成或发生某事件而不能运行时，才将CPU分给其它进程。这种调度方式通常用在批处理系统中。它的主要优点是简单、系统开销小。
• 2.抢占方式：当一个进程正在执行时，系统可以基于某种策略剥夺CPU给其它进程。剥夺的原则有：优先权原则、短进程优先原则和时间片原则。这种调度方式多用在分时系统和实时系统中，以便及时响应各进程的请求。

3.1.4 引起进程调度的时机（因素）

• 进程调度的时机是与进程调度的方式有关的。通常当发现以下情况时，当前运行进程的CPU被收回，需要重新进行进程调度：
  • 正在执行的进程正确完成,或由于某种错误而终止运行(陷阱或中断)；
  • 执行中的进程提出I/O请求, 等待I/O完成时;
  • 在分时系统中，分给进程的时间片用完时；
  • 按照优先级调度时,有更高优先级进程变为就绪时(抢占方式)；
  • 在进程通信或进程同步过程中,执行中的进程执行了某种原语操作, 如P （wait）操作、阻塞原语和唤醒原语时, 都可能引起进程调度。

3.2 调度评价准则

• 1）面向系统的调度性能准则

  • 系统吞吐量：单位时间内处理的进程数。
  • 处理机利用率：CPU利用率=CPU有效工作时间/CPU总的运行时间
  • 各种设备的均衡利用：如CPU繁忙的作业和I/O繁忙（指次数多，每次时间短）的作业搭配。

• 2） 面向用户的调度性能准则

  • 周转时间：作业从提交到完成所经历的时间——批处理系统。（公式中Tsi为实际运行时间）。

    

  • 响应时间：用户输入一个请求（如击键）到系统给出首次响应（如屏幕显示）的时间——分时系统

  • 截止时间：开始截止时间和完成截止时间——实时系统。

  • 公平性：不因作业或进程本身的特性而使上述指标过分恶化。如长作业等待很长时间。

  • 优先级：可以使关键任务达到更好的指标。

3.3 调度算法

1.先来先服务FCFS(先进先出调度算法，FIFO)

• 【算法思想】：最简单的算法

  • 按照进程进入就绪队列的先后次序，分派CPU；
  • 当前进程占用CPU，直到执行完或阻塞，才出让CPU（非抢占方式）。
  • 在进程唤醒后（如I/O完成），并不立即恢复执行，通常等到当前进程让出CPU。

• 【特点】：

  • 比较有利于长作业，而不利于短作业。
  • 有利于CPU繁忙的作业，而不利于I/O繁忙的作业。

• 结构图&&算法流程

  

• 【例题】

  • 题目：系统中现有5 个作业A、B、C、D、E同时提交（到达顺序也为ABCDE），其预计运行时间分别10、1、2、1、5个时间单位，如表所示，计算FCFS调度下作业的平均周转时间和平均带权周转时间

    

  • 解答：设作业到达时刻为0，根据定义计算，系统运行情况

    

2.短进程优先调度算法(SJF,SPF)

• 【算法思想】：选择就绪队列中估计运行时间最短的进程投入运行。通常后来的短作业不抢先正在执行的作业。

• 【优点】：

  • 比FCFS改善平均周转时间和平均带权周转时间，缩短作业的等待时间；
  • 提高系统的吞吐量；

• 【缺点】：

  • 对长作业非常不利，可能长时间得不到执行；
  • 未能依据作业的紧迫程度来划分执行的优先级；
  • 难以准确估计作业（进程）的执行时间，从而影响调度性能。

• 【例题】

  • 问题：同FCFS题目

  • 解答：采用SJF算法调度作业

    

3.最短剩余时间优先（Shortest Remaining Time First，SRTF）

• 【算法思想】：若一就绪状态的新作业所需的CPU时间比当前正在执行的作业剩余任务所需CPU时间还短，SRTF将打断正在执行作业，将执行权分配给新作业

• 【特点】：

  • 长进程仍有可能出现饥饿现象
  • 必须计算运行、剩余时间，系统开销增大
  • 因抢占式调度，系统性能会比SJF要好

• 【例题】

  • 问题：作业A、B、C、D需要运行的时间分别为20ms、15ms、10ms、5ms。A作业在0ms到达，B作业在1ms到达，C作业在2ms到达，D作业在3ms到达。计算SRTF调度下作业的平均周转时间和平均带权周转时间

  • 解答：如图

    

4.高响应比优先（Highest Response Ratio First，HRRF）

• 【算法思想】：是FCFS与SJF两种算法的折衷——既考虑作业等待时间，又考虑作业的运行时间，既照顾短作业又不使长作业等待过久，改善了调度性能，仍属于非抢占式算法

  • 响应比为作业的响应时间与作业所需运行时间之比，简化为：响应比 ＝1 +（已等待的时间 / 估计运行时间）

• 【适用性】

  • 由定义可知，短作业容易得到较高响应比，长作业在等待了足够长的时间后，也将获得足够高的响应比，因此不会发生饥饿现象
  • 需要经常计算作业的响应比，导致额外的开销
  • HRRF算法的平均周转时间和平均带权周转时间都介于FCFS与SJF算法之间，比SJF算法差，比FCFS算法优
  • 虽然HRRF算法的平均周转时间和平均带权周转时间不及SJF算法，但是，在现实中其可以实现，结果也比较可靠
  • 如果在算法中引入抢占调度，则算法过程会更复杂。因为所有作业的响应比是动态变化的，抢占时间的计算需要解多个方程得到

• 【例题】

  • 问题：系统中现有3 个作业A、B、C先后提交（到达），其参数如表所示，计算HRRF调度下作业的平均周转时间和平均带权周转时间

    

  • 解答：如图

    

5.优先级调度算法(HPF—Highest Priority First)

• 【算法思想】：优先选择就绪队列中优先级最高的进程投入运行。分为：

  • 非抢占式优先级算法：仅发生在进程放弃CPU。
  • 抢占式优先级算法：可剥夺当前运行进程CPU。

• 【优先权的类型】

  • 静态优先级：在进程创建时指定优先级,在进程运行时优先数不变。
  • 动态优先级：在进程创建时创立一个优先级，但在其生命周期内优先数可以动态变化。如等待时间长优先数可改变。

• 【确定优先级的依据】

  • 进程类型、对资源的需求、根据用户要求。

• 【确定优先级的原则】

  • 静态优先数的确定：
    • 用户要求：用户可以根据作业情况提出自己的优先级要求；
    • 资源利用率：请求I/O服务密集的进程优先级较高；
    • 系统内部要求：系统进程的优先级高于用户进程的优先级。
  • 动态优先数的确定：
    • 进程运行前被赋予一个优先数。运行中根据进程等待时间的长短、执行时间的多少、输入与输出信息量的大小等，通过计算得到新的优先数。每次调度时，仍然是从就绪队列中选择优先级最高的进程率先调度，同级的采用先来先服务（FCFS）。

• 【例题】

  • 问题：系统的进程调度采用抢占式优先权调度算法，优先数越小优先级越高，其参数如表所示，求平均周转时间和平均等待时间

    

  • 解答：如图

    

6.时间片轮转

• 【算法思想】：通过时间片轮转，提高进程并发性和响应时间特性，从而提高资源利用率。
  • 将系统中所有的就绪进程按照FCFS原则，排成一个队列。
  • 每次调度时将CPU分派给队首进程，让其执行一个时间片。时间片的长度从几个ms到几百ms。
  • 在一个时间片结束时，发生时钟中断。
  • 调度程序据此暂停当前进程的执行，将其送到就绪队列的末尾，并通过CPU现场切换执行当前的队首进程。
  • 进程可以未使用完一个时间片，就出让CPU（如阻塞）。
• 【时间片长度变化的影响】：
  • 过长－>退化为FCFS算法，进程在一个时间片内都执行完，响应时间长。
  • 过短－>用户的一次请求需要多个时间片才能处理完，CPU现场切换次数增加，响应时间长。
• 【对响应时间的要求】：
  • (响应时间)=N(进程数目)*q(时间片)
• 【时间片长度的影响因素】：
  • 就绪进程的数目：数目越多，时间片越小（当响应时间一定时）。
  • 系统的处理能力：应当使用户输入通常在一个时间片内能处理完，否则使响应时间，平均周转时间和平均带权周转时间延长。

7.1多级队列调度算法

• 【基本思想】

  • 根据进程的类型不同，将进程就绪队列分为若干个独立的就绪队列，不同的就绪队列采用不同的调度算法，同一个就绪队列采用同一种进程调度算法。

  • 按照用户作业的性质不同，就绪队列进行不同组织。

    • 如：按照进程优先级组织的多个进程就绪队列：

      

7.2多级反馈队列算法(多队列轮转法MFQ)

• 【算法思想】：
  • 设置多个就绪队列，分别赋予不同的优先级，队列1的优先级最高，其他逐级降低。每队列分配不同的时间片，规定优先级越低则时间片越长。
  • 新进程就绪后，先投入队列1的末尾，按FCFS算法调度。若一个时间片未能执行完，则降低投入到队列2的末尾；依此类推，降低到最后的队列，则按“时间片轮转”算法调度直到完成。
  • 进程由于等待事件而放弃CPU后,进入等待队列, 一旦等待的事件发生, 则回到原来的就绪队列。
  • 仅当较高优先级的队列为空，才调度较低优先级的队列中的进程执行。如果进程执行时有新进程进入较高优先级的队列，则抢先执行新进程，并把被抢先的进程投入原队列的末尾。
• 【补充说明】
  • I/O型进程：让其进入最高优先级队列，以及时响应I/O交互。通常执行一个小时间片，要求可处理完一次I/O请求的数据，然后转入到阻塞队列。
  • 计算型进程：每次都执行完时间片，进入更低级队列。最终采用最大时间片来执行，减少调度次数。
  • I/O次数不多，而主要是CPU处理的进程：在I/O完成后，放回优先I/O请求时离开的队列，以免每次都回到最高优先级队列后再逐次下降。
  • 时间片的增加和优先级的降低体现了反馈；
• 【算法优点】：
  • 为提高系统吞吐量和缩短平均周转时间而照顾短进程。
  • 为获得较好的I/O设备利用率和缩短响应时间而照顾I/O型进程。
  • 不必估计进程的执行时间，动态调节。

各算法总结

在所学的调度算法中，对所有进程和作业都是公平合理的调度算法是 (1) ；最有利于提高系统吞吐量的作业调度算法是 (2) ；能兼顾作业等待时间和作业执行时间调度算法是 (5) ；最有利于提高资源的使用率、能使短作业、长作业及交互作业用户都比较满意的调度算法是 (4) ；为实现人机交互作用应采用调度算法是 (3) ；能对紧急作业进行及时处理的调度算法是 (6) 。

• A—F：(1)FCFS调度算法； (2)短作业优先调度算法；(3)时间片轮转法； (4)多级反馈队列调度算法；(5)高响应比优先算法；(6)基于优先权的剥夺调度算法。

3.4 实时调度

• 所谓实时是指系统能够对外部请求做出即时响应，外部请求是指与系统相连的设备提出的服务要求和数据采集。与前面介绍的进程调度算法相比，主要是及时响应和及时处理，即满足实时任务的时间要求。

1.实时调度的基本条件

• ⑴ 就绪时间。
• ⑵ 开始截止时间和完成截止时间。
• ⑶ 处理时间。
• ⑷ 资源要求。
• ⑸ 优先级。

2.实时调度的时机与算法

⑴时间片轮转调度算法：

当一个实时任务到达时，它被挂在轮转队列的末尾，用于分时系统中。这种调度算法能获得数秒至数十秒的响应时间，只适用于一般实时信息处理系统。

⑵非抢占优先级调度算法

系统为每一个实时任务都赋予一个相应的优先级，当实时任务到达时，将依据它的优先级高低插入到就绪队列中。紧迫的实时任务有可能获得数秒至数百毫秒级的响应时间，故该方法可用于要求不太严格的实时控制系统中。

⑶抢占式优先级调度算法

在该方法中，若到达的实时任务优先级高于当前任务的优先级，则该实时任务就可以抢夺CPU。调度程序可由时钟中断触发，也可由代表紧迫任务的外部中断触发。这要求操作系统具有快速响应外部事件中断的能力。这种调度算法能获得很好的响应效果，其调度延迟可降为几十毫秒至100微秒，因此它可用于大多数的实时系统中。

【实时调度的时机】

3.实时调度实例

【最早开始截止时间优先】

如图

【剥夺式调度】

如图，在该例中，设C的开始截止时间是5，则在t＝5时，A还没有运行完，但C的开始截止时间已到，为了保证任务的时效性，就要采用可剥夺式调度。既在t＝5时改调度C任务运行，在t＝10时再调度A任务执行剩余的部分，这样A、B两个任务均在指定时间内完成了。

3.5 死锁

一个进程集合中的每个进程都在等待只能由该集合中的其它一个进程才能引发的事件，则称一组进程或系统此时发生了死锁

死锁产生的原因

• 并发进程对临界资源的竞争
• 并发进程推进顺序不当、

死锁产生的必要条件

• 1）互斥条件（Mutual exclusion）——资源的使用是互斥的
• 2）请求与保持条件（Hold and wait）——已经得到某些资源的进程可以再申请新的资源。
• 3）不剥夺条件（No pre-emption）——系统或其它进程不能剥夺进程已经获得的资源。
• 4）环路等待条件（Circular wait）——系统中若干进程间形成等待环路

死锁的解决方法

解决方法分为预防和避免

①死锁的预防

在系统运行之前就采取措施，即在系统设计时确定资源分配算法，消除发生死锁的任何可能性。

• 1．静态资源分配法（摒弃“占有并请求条件”）
  • 系统规定每一个进程在开始运行前，都必须一次性地申请其在整个运行过程所需的全部资源。此时，若系统有足够的资源，便把进程想要的全部资源一次性地分配给它；若不能全部满足进程的资源请求，则一个资源也不分给它。
  • 简单、安全、易实现。（1）资源被严重浪费；（2）进程延迟运行。
• 2．摒弃“不可剥夺条件”
  • 进程在需要资源时才提出请求。即：一个已经保持了某些资源的进程，当它再提出新的资源要求而不能立即得到满足时，必须释放它已经保持的所有资源，待以后再需要时再重新申请。
  • 采用剥夺式调度方法，只适用于CPU和内存分配；实现起来比较复杂；进程的周转时间较长，系统开销大。
• 3．有序资源使用法（摒弃“循环等待条件”）
  • 系统中的所有资源按类都被赋予一个唯一的编号，每个进程只能按编号的升序申请资源。
  • 安全且资源利用率比静态资源分配法有所提高；实现较困难，因为难给出合适的资源编号；仍有一定的资源浪费现象

系统资源分配图

• 圆圈表示进程，资源类用方框表示，框中的圆点代表单个该类资源，有向边连接进程和资源

• 申请边从进程指向资源类方框，表示进程正在等待资源；分配边从单个资源圆点指向进程，表示进程已经获得资源

• 根据进程-资源分配图定义得出如下结论

  
  • 1）如果进程-资源分配图中无环路，则此时系统没有发生死锁
  • 2）如果进程-资源分配图中有环路，且每个资源类中仅有一个资源，则系统中发生了死锁，此时，环路是系统发生死锁的充要条件，环路中的进程便为死锁进程
  • 3）如果进程-资源分配图中有环路，且涉及的资源类中有多个资源，则环路的存在只是产生死锁的必要条件而不是充分条件

系统为死锁状态的充分条件是：当且仅当该状态的进程-资源分配图是不可完全简化的——死锁定理。

② 死锁的避免

• 系统在运行过程中采取动态的资源分配策略，保证系统不进入可能导致系统陷入死锁状态的所谓不安全状态，以避免死锁发生。

• 系统状态

  • 1.安全状态

    • 若在某一时刻，系统能按某种进程顺序，如<P1,P2,…,Pn>，来为每个进程分配其所需的资源，直至最大需求，使每个进程均可顺利完成。则称此时系统的状态为安全状态，称这样的一个进程序列<P1,P2,…,Pn>为安全序列。

    • 安全序列的实质是：序列中的每一个进程Pi（i=1,2,…,n）到以后运行完成尚需要的资源量不超过系统当前剩余的资源量与所有在序列中排在它前面的进程当前所占有的资源量之和。

    • 举例

      

  • 2.不安全状态

    • 若在某一时刻，系统不按照安全序列分配资源，导致系统中不存在一个安全序列，则称系统处于不安全状态。

  • 1）系统在某一时刻的安全状态可能不唯一，但这不影响对系统安全性的判断。

  • 2）安全状态是非死锁状态，而不安全状态并不一定是死锁状态。即系统处于安全状态一定可以避免死锁，而系统处于不安全状态则仅仅可能进入死锁状态。

银行家算法

【思路】

• 1）在某一时刻，各进程已获得所需的部分资源。有一进程提出新的资源请求，系统将剩余资源试探性地分配给该进程。
• 2）如果此时剩余资源能够满足余下的某些进程的需求，则将剩余资源分配给能充分满足的、资源需求缺口最大的进程，运行结束后释放的资源再并入系统的剩余资源集合。
• 3）反复执行第2步，直到所有的进程都能够获得所需而运行结束。说明第1步的进程请求是可行的，系统处于安全状态，相应的进程执行序列称为系统的安全序列。如果所有的进程都试探过而不能将资源分配给进程，即不存在安全序列，则系统是不安全的。

【银行家算法中所用的主要数据结构】

• (1)可利用资源向量Available
• (2)最大需求矩阵Max：资源最大需求量
• (3)Allocation：已分配的资源
• (4)需求矩阵Need：Need=Max－Allocation
• (5)请求向量Request：记录某个进程当前对各类资源的申请量，是银行家算法的入口参数

【算法步骤】

• 当Pi发出资源请求后，系统按下述步骤进行检查：
  • 1.判断请求向量Request的有效性——如果Request[i] >该进程 i 的总需求，则出错。
  • 2.如果Request[i]>Available,则Pi阻塞；
  • 3.系统试探把要求的资源分配给进程Pi，并修改下面数据结构中的数值：
    • Available[i]=Available[i]-Request[i]；Allocation[i]=Allocation[i]+Request[i]；Need[i] =Need[i]-Request[i];
  • 4.系统执行安全性算法，检查此次资源分配后，系统是否处于安全状态。若安全，正式将资源分配给进程Pi，以完成本次分配；否则，将试探分配作废，恢复原来的资源分配状态，让进程Pi等待。

【子算法描述】

• 1.设置两个向量
  • ①工作向量Work：表示系统可提供给进程继续运行所需要的各类资源的数目，开始时，Work:=Available。
  • ②Finish：它表示系统是否有足够的资源分配给进程，使之运行完成。开始时先做Finish[i]:=false；当有足够的资源分配给进程时，令Finish[i]:=true。
• 2.执行过程的描述
  • (1)初始化：work=available；finish=false；
  • (2)若按进行编号顺序找到了一个可加入安全序列的进程
    • 即：满足条件finishi=false且need[i]≤work的进程Pi
    • 则①假设该进程不久将完成任务归还资源，置work=work+allocationi和finishi=true
    • ②重复执行这一步；
  • (3)若所有进程的可完成标志finish为真，则返回逻辑真值（表示系统处于安全状态）；
  • (4)否则，返回逻辑假值（表示不安全）；

【银行家算法示例】

• 假定系统中有四个进程{P1、P2、P3、P4}和三种类型的资源{R1，R2，R3}，资源的数量分别为9、3、6，在T0时刻的资源分配情况如图：

  

• 解决方案：可以看出{ P2、P1、P3、P4 }是一个安全的执行序列

  

③ 死锁的检测和恢复

死锁的检测

• 死锁的检测算法可以采用基于死锁定理的检测，也可以采用类似于银行家算法中的安全性测试算法
• 在系统中，需要决定死锁检测的频率。如果检测太频繁，会花大量的时间检测死锁，浪费CPU的处理时间；如果检测的频率太低，死锁进程和系统资源被锁定的时间过长，资源浪费大。
• 通常的方法是在CPU的使用率下降到一定的阈值时实施检测。当死锁发生次数多，死锁进程数增加到一定程度时，CPU的处理任务减少，CPU空闲时间增多。

死锁的解除

• 重启：重新启动死锁进程，甚至重启操作系统。
• 撤销：撤销死锁进程，回收资源，优先选择占用资源最多或者撤销代价最小的，撤销一个不行就继续选择撤销进程，直至解除死锁。
• 剥夺：剥夺死锁进程资源再分配，选择原则同上。
• 回滚：根据系统保存的检查点，使进程或系统回退到死锁前的状态。