操作系统第4章

1、第四章第四章 调度与死锁调度与死锁4.1 调度的类型与模型调度的类型与模型4.2 调度算法调度算法4.3 实时系统中的调度实时系统中的调度4.6 死锁的基本概念死锁的基本概念4.7 死锁的预防和避免死锁的预防和避免4.8 死锁的检测和解除死锁的检测和解除4.1 调度的类型和模型调度的类型和模型一、调度类型一、调度类型二、调度模型二、调度模型 4.1 4.1 调度类型和模型调度类型和模型一、调度类型一、调度类型 1. 高级调度（也称作业调度、长程调度）高级调度（也称作业调度、长程调度）作用：作用：选择外存上处于后备队列中的一个或几个作业调入内存，选择外存上处于后备队列中的一个或几个作业调入内存，

2、 并为它们创建进程，分配必要的资源，然后，再将新创建并为它们创建进程，分配必要的资源，然后，再将新创建 的进程排在就绪队列，准备执行。的进程排在就绪队列，准备执行。使用系统：使用系统：批处理系统（分时系统和实时系统不需要）。批处理系统（分时系统和实时系统不需要）。作业调度时要决定：作业调度时要决定： 1. 一次选择多少个作业：取决于多道程序度和资源使用情况。一次选择多少个作业：取决于多道程序度和资源使用情况。 2. 选择哪些作业：取决于作业调度算法和资源使用情况。选择哪些作业：取决于作业调度算法和资源使用情况。何时执行作业调度功能：何时执行作业调度功能： 1. 有作业退出系统时；有作业退出系统

3、时； 2. 系统负荷不足时。系统负荷不足时。执行频率：执行频率：几分钟或几秒种一次。几分钟或几秒种一次。 4.1 4.1 调度类型和模型调度类型和模型一、调度类型一、调度类型 2. 低级调度（也称进程调度、短程调度）低级调度（也称进程调度、短程调度）作用：作用：从就绪队列中选择一个进程，然后，由分派程序将处理机从就绪队列中选择一个进程，然后，由分派程序将处理机 分配给该进程。分配给该进程。使用系统：使用系统：各种系统均需要。各种系统均需要。进程调度时只决定：进程调度时只决定： 选择哪个就绪进程：取决于进程调度算法。选择哪个就绪进程：取决于进程调度算法。执行频率：执行频率：几十毫秒一次。几十毫秒

4、一次。 4.1 4.1 调度类型和模型调度类型和模型一、调度类型一、调度类型何时执行进程调度功能：何时执行进程调度功能： 出现下列四种情况时，进程调度功能被执行：出现下列四种情况时，进程调度功能被执行： 1. 当进程从执行态转换到阻塞态时（例如提出当进程从执行态转换到阻塞态时（例如提出I/O请求或等待子请求或等待子 进程结束）。进程结束）。 2. 当进程从执行态转换到就绪态时（例如发生时钟中断）。当进程从执行态转换到就绪态时（例如发生时钟中断）。 3. 当进程从阻塞态转换到就绪态时（例如当进程从阻塞态转换到就绪态时（例如I/O操作结束）。操作结束）。 4. 当一个进程终止时当一个进程终止时。

5、4.1 4.1 调度类型和模型调度类型和模型一、调度类型一、调度类型进程调度方式：进程调度方式： 1.非抢占方式非抢占方式(nonpreemptive)： 一旦把处理机分配给某个进程，便让该进程一直执行，直至一旦把处理机分配给某个进程，便让该进程一直执行，直至 该进程完成或发生某事件而阻塞时，才把处理机分配给其它该进程完成或发生某事件而阻塞时，才把处理机分配给其它 进程。（即仅在情况进程。（即仅在情况1和和4下，才进行进程调度）下，才进行进程调度） 2.抢占方式抢占方式(preemptive)： 允许调度程序根据某种原则，去停止某个正在执行的进程，允许调度程序根据某种原则，去停止某个正在执行的

6、进程， 将已分配给该进程的处理机，重新分配给另一进程。（即在将已分配给该进程的处理机，重新分配给另一进程。（即在 情况情况1、2、3、4时均可调度）时均可调度） 时间片原则时间片原则 抢占原则抢占原则 优先权原则优先权原则 短进程优先原则短进程优先原则 4.1 4.1 调度类型和模型调度类型和模型一、调度类型一、调度类型分派程序的主要功能：分派程序的主要功能： 1. 进行进程切换；进行进程切换； 2. 转到用户态；转到用户态； 3. 开始执行被选中的进程。开始执行被选中的进程。 进程进程P P0 0 操作系统操作系统 进程进程P P1 1 执行执行执行执行将将P P0 0信息信息保存在保存在P

7、CBPCB0 0从从PCBPCB1 1中恢复中恢复P P1 1信息信息进程进程切换切换示意图示意图 4.1 4.1 调度类型和模型调度类型和模型一、调度类型一、调度类型 3. 中级调度（也称中程调度）中级调度（也称中程调度）作用：作用：负责进程在内存和外存对换区之间换进负责进程在内存和外存对换区之间换进/换出。换出。是内存对换功能的一部分。是内存对换功能的一部分。目的：目的：提高内存利用率和系统吞吐量。提高内存利用率和系统吞吐量。执行频率：执行频率：介于作业调度和进程调度之间。介于作业调度和进程调度之间。 4.1 4.1 调度类型和模型调度类型和模型二、调度模型二、调度模型仅有进程仅有进程调度

8、的调度队列模型调度的调度队列模型阻阻 塞塞 队队 列列 1 1就就 绪绪 队队 列列CPU进程调度进程调度进程完成进程完成交互用户交互用户等待事件等待事件1 1事件出现事件出现时间片用完时间片用完阻阻 塞塞 队队 列列 2 2等待事件等待事件2 2阻阻 塞塞 队队 列列 n n等待事件等待事件n n事件出现事件出现事件出现事件出现 4.1 4.1 调度类型和模型调度类型和模型二、调度模型二、调度模型具有作业调度和进程具有作业调度和进程调度的调度队列模型调度的调度队列模型阻阻 塞塞 队队 列列 1 1就就 绪绪 队队 列列CPU进程调度进程调度进程完成进程完成后备队列后备队列等待事件1事件出现时

9、间片用完时间片用完阻阻 塞塞 队队 列列 2 2等待事件2阻阻 塞塞 队队 列列 n n等待事件n事件出现事件出现 作业作业调度调度交互用户交互用户批处理批处理作业作业一、先来先服务调度算法一、先来先服务调度算法二、二、短作业（进程）优先调度算法短作业（进程）优先调度算法三、时间片轮转调度算法三、时间片轮转调度算法四、优先权调度算法四、优先权调度算法五、高响应比优先调度算法五、高响应比优先调度算法六、多级队列调度六、多级队列调度七、多级反馈队列调度算法七、多级反馈队列调度算法4.2 4.2 调度算法调度算法缩写：缩写：FCFS（First Come First Served）既适用于作业调度，

10、又适用于进程调度（非抢占方式）。既适用于作业调度，又适用于进程调度（非抢占方式）。后备作业队列、就绪队列按后备作业队列、就绪队列按FIFO排列，调度时选择处于排列，调度时选择处于 队首的作业或进程。队首的作业或进程。优点：简单、易于实现。优点：简单、易于实现。 缺点：缺点：1 1）有利于长的作业或进程，不利于短的。）有利于长的作业或进程，不利于短的。 2 2）有利于）有利于CPU繁忙型的作业或进程，不利于繁忙型的作业或进程，不利于 I/O繁忙型的。繁忙型的。例：例： 4.2 4.2 调度算调度算法法一、先来先服务调度算法一、先来先服务调度算法 4.2 4.2 调度算法调度算法一、先来先服务调度

11、算法（例）一、先来先服务调度算法（例）进程名进程名 到达时间到达时间 服务时间服务时间 A 0 4 B 1 5 C 2 2 D 3 4A B C D0 4 9 11 15 0 4 9 11 15 开始时间开始时间 完成时间完成时间 周转时间周转时间 带权周转时间带权周转时间 0 4 4 1 4 9 8 1.6 9 11 9 4.5 11 15 12 3平均平均 8.25 2.5258.25 2.525缩写：缩写：SJF（Shortest Job First）/SPF（Process)既适用于作业调度，又适用于进程调度既适用于作业调度，又适用于进程调度从后备作业队列、就绪队列中选择估从后备作业队

12、列、就绪队列中选择估 计运行时间最短的作业或进程。计运行时间最短的作业或进程。例：例： 4.2 4.2 调度算法调度算法二、短作业二、短作业/ /短进程优先调度算法短进程优先调度算法优点：调度性能较好。优点：调度性能较好。 缺点：缺点：1 1）不利于长的作业或进程。）不利于长的作业或进程。 2 2）不考虑作业或进程的紧迫程度。）不考虑作业或进程的紧迫程度。 3 3）估计运行时间很难准确获得。）估计运行时间很难准确获得。非抢占方式非抢占方式抢占方式抢占方式 4.2 4.2 调度算法调度算法二、短进程优先调度算法（例二、短进程优先调度算法（例1）进程名进程名 到达时间到达时间 服务时间服务时间 A

13、 0 4 B 1 5 C 2 2 D 3 4A C D B0 4 6 10 15 0 4 6 10 15 开始时间开始时间 完成时间完成时间 周转时间周转时间 带权周转时间带权周转时间 0 4 4 1 10 15 14 2.8 4 6 4 2 6 10 7 1.75平均平均 7.25 1.88757.25 1.8875非抢占方式非抢占方式 4.2 4.2 调度算法调度算法二、短进程优先调度算法（例二、短进程优先调度算法（例2）进程名进程名 到达时间到达时间 服务时间服务时间 A 0 3 B 0 5 C 0 3 D 0 4 E 8 3抢占方式抢占方式1 1、基于最短服务时间抢占、基于最短服务时间

14、抢占：A C D E D B0 3 6 8 11 13 18 0 3 6 8 11 13 18 A C D E B0 3 6 10 13 18 0 3 6 10 13 18 非抢占方式非抢占方式2 2、基于最短剩余服务时间抢占、基于最短剩余服务时间抢占：A C D E B0 3 6 10 13 18 0 3 6 10 13 18 缩写：缩写：RR（Round Robin）仅适用于进程调度（抢占方式）。仅适用于进程调度（抢占方式）。主要为分时系统设计。主要为分时系统设计。就绪队列按就绪队列按FIFO排列，调度时排列，调度时选择队首进程。但该进程选择队首进程。但该进程 占用占用CPU至多执行一个时

15、间片，便放弃至多执行一个时间片，便放弃CPU。例：例： 4.2 4.2 调度算法调度算法三、时间片轮转调度算法三、时间片轮转调度算法关键：时间片大小的确定关键：时间片大小的确定 太大：退化为太大：退化为FCFS 太小：系统效率降低太小：系统效率降低特点：假设所有进程都是同等重要的。特点：假设所有进程都是同等重要的。 4.2 4.2 调度算法调度算法三、时间片轮转调度算法（例）三、时间片轮转调度算法（例）进程名进程名 到达时间到达时间 服务时间服务时间 A 0 4 B 0 5 C 0 2 D 0 4开始时间开始时间 完成时间完成时间 周转时间周转时间 带权周转时间带权周转时间 0 10 10 2

16、.5 2 15 15 3 4 6 6 3 6 14 14 3.5A B C D A B D B0 2 4 6 8 10 12 14 15 0 2 4 6 8 10 12 14 15 时间片时间片=2=2既适用于作业调度，又适用于进程调度既适用于作业调度，又适用于进程调度选择具有最高优先权的后备作业或就绪进程。选择具有最高优先权的后备作业或就绪进程。例：例： 4.2 4.2 调度算法调度算法四、优先权调度算法四、优先权调度算法优先权的类型：优先权的类型： 1.1.静态优先权：创建进程时确定，进程运行期间保持不变。静态优先权：创建进程时确定，进程运行期间保持不变。 简单易行，系统开销小，但不够精确

17、。简单易行，系统开销小，但不够精确。 2.2.动态优先权：创建进程时确定初值，运行期间基于某种原则动动态优先权：创建进程时确定初值，运行期间基于某种原则动 态改变。例如，优先权可随占用态改变。例如，优先权可随占用CPUCPU时间加长而降时间加长而降 低。低。 灵活，调度性能好，但系统开销大。灵活，调度性能好，但系统开销大。 非抢占方式非抢占方式抢占方式抢占方式 4.2 4.2 调度算法调度算法四、优先权调度算法（例）四、优先权调度算法（例）进程名进程名 到达时间到达时间 服务时间服务时间 优先权优先权 A 0 10 3 B 0 1 5 C 0 5 2 D 5 3 4B A D C 0 1 11

18、 14 19 非抢占方式非抢占方式B A D A C 0 1 5 8 14 19 抢占方式抢占方式主要用于作业调度主要用于作业调度选择具有最高响应比的后备作业。选择具有最高响应比的后备作业。 响应比响应比= =1+等待时间等待时间/ /要求服务时间要求服务时间例：例： 4.2 4.2 调度算法调度算法五、高响应比优先调度算法五、高响应比优先调度算法优点：既照顾了作业到来的先后，又考虑了要求服务时间优点：既照顾了作业到来的先后，又考虑了要求服务时间 的长短，是的长短，是FCFS和和SJF的很好的折衷。的很好的折衷。 缺点：算法较为复杂；每次调度时，均要重新计算响应比。缺点：算法较为复杂；每次调度

19、时，均要重新计算响应比。 4.2 4.2 调度算法调度算法五、高响应比优先调度算法五、高响应比优先调度算法作业名作业名J1J2J3到达时间到达时间8:008:309:30服务时间服务时间2小时小时1小时小时0.25小时小时三个作业在一台处理机上单道运行，三个作业在一台处理机上单道运行，9:40 9:40 进行作业调度，问三个作业的执进行作业调度，问三个作业的执行次序？行次序？9:40 9:40 调度时：调度时：J1J1：1+100/120 = 1+5/61+100/120 = 1+5/6J2J2：1+70/60 = 1+7/61+70/60 = 1+7/6J3J3：1+10/15 = 1+4/

20、61+10/15 = 1+4/6选择选择J2J2作业调度作业调度10:4010:40（J2J2完成）调度时：完成）调度时：J1J1：1+160/120 = 1+4/31+160/120 = 1+4/3J3J3：1+70/15 = 1+14/31+70/15 = 1+14/3选择选择J3J3作业调度作业调度执行次序：执行次序：J2J2、J3J3、J1J1适用于进程调度。适用于进程调度。调度方式：调度方式： 1.1.按性质和类型将就绪队列分为若干子队列，每个就绪按性质和类型将就绪队列分为若干子队列，每个就绪 进程固定地分属于一个子队列，每个队列有自己的调进程固定地分属于一个子队列，每个队列有自己的

21、调 度算法。度算法。 2.2.各队列间的调度方式或采用固定优先权抢占调度，或各队列间的调度方式或采用固定优先权抢占调度，或 为各队列分配一定比例的为各队列分配一定比例的CPU时间。时间。 4.2 4.2 调度算法调度算法六、多级队列调度六、多级队列调度适用于进程调度适用于进程调度-抢占方式。抢占方式。实施过程：实施过程： 4.2 4.2 调度算法调度算法七、多级反馈队列调度算法七、多级反馈队列调度算法就绪队列就绪队列1 1（FCFS）s1CPU结束或结束或阻塞阻塞就绪队列就绪队列2 2（FCFS）s2CPU就绪队列就绪队列n（RR）snCPU提交提交高高优优先先权权低低（时间片（时间片s1s2

22、 sn ）结束或结束或阻塞阻塞结束或结束或阻塞阻塞一、对实时系统的要求一、对实时系统的要求二、二、实时调度算法实时调度算法三、实时调度实例三、实时调度实例4.3 4.3 实时系统中的调度实时系统中的调度一、对实时系统的要求一、对实时系统的要求实时系统与其他普通的系统之间的最大的不同之处就是要实时系统与其他普通的系统之间的最大的不同之处就是要满足处理与时间的关系。满足处理与时间的关系。在实时计算中，系统的正确性不仅仅依赖于计算的逻辑结在实时计算中，系统的正确性不仅仅依赖于计算的逻辑结果而且依赖于结果产生的时间。果而且依赖于结果产生的时间。对于实时系统来说最重要的要求就是实时操作系统必须有对于实时

23、系统来说最重要的要求就是实时操作系统必须有满足在一个事先定义好的时间限制中对外部或内部的事件进满足在一个事先定义好的时间限制中对外部或内部的事件进行响应和处理的能力。行响应和处理的能力。实时系统可以定义为实时系统可以定义为“一个能够在事先指定或确定的时间一个能够在事先指定或确定的时间内完成系统功能和对外部或内部、同步或异步事件作出响应内完成系统功能和对外部或内部、同步或异步事件作出响应的系统的系统 。（。（* *Real_Time UNIX Systems Design and Real_Time UNIX Systems Design and Application Guide )Appli

24、cation Guide )一、对实时系统的要求一、对实时系统的要求由于实时系统在设计时与应用的关系非常强，所以有许多由于实时系统在设计时与应用的关系非常强，所以有许多分类的方法。各种分类的侧重点不同。分类的方法。各种分类的侧重点不同。方法一方法一 分为周期性的和非周期性的（分为周期性的和非周期性的（periodicperiodic和和aperiodicaperiodic）。）。周期性的就是系统通过传感器或其他设备周期性的探测外周期性的就是系统通过传感器或其他设备周期性的探测外部环境的变化，在周期内对探测到的变化作出反应。比如化部环境的变化，在周期内对探测到的变化作出反应。比如化工厂中的反应炉

25、的控制。工厂中的反应炉的控制。非周期性的指外部事件是循环性的发生的，但不是有规律非周期性的指外部事件是循环性的发生的，但不是有规律的或者是突发事件。比如一架客机飞入一个空中交通管制的的或者是突发事件。比如一架客机飞入一个空中交通管制的管制范围所产生的事件。管制范围所产生的事件。一、对实时系统的要求一、对实时系统的要求方法二方法二 分为硬实时和软实时（分为硬实时和软实时（hard real_timehard real_time和和soft soft realtimerealtime）。硬实时系统就是系统必须及时的对事件作出反）。硬实时系统就是系统必须及时的对事件作出反应，绝对不能发生错过事件处理

26、的应，绝对不能发生错过事件处理的deadlinedeadline的情况。在硬实的情况。在硬实时系统中一旦发生了这种情况就意味着巨大的损失和灾难。时系统中一旦发生了这种情况就意味着巨大的损失和灾难。比如控制核电站的系统，如果没有对堆芯过热作出及时的处比如控制核电站的系统，如果没有对堆芯过热作出及时的处理，后果不堪想象。理，后果不堪想象。在软实时系统中，当系统在重负载的情况下允许发生错在软实时系统中，当系统在重负载的情况下允许发生错过过deadlinedeadline的情况而不会造成非常大的危害。比如在通信系的情况而不会造成非常大的危害。比如在通信系统中允许统中允许105105个电话中有一个接不通

27、。个电话中有一个接不通。对于软实时系统基于优先级调度的调度算法可以满足要对于软实时系统基于优先级调度的调度算法可以满足要求，提供高速的响应和大的系统吞吐率；而对于硬实时系统求，提供高速的响应和大的系统吞吐率；而对于硬实时系统则完成则完成timely responsetimely response是必须的。是必须的。一、对实时系统的要求一、对实时系统的要求作为实时系统其特性决定了传统的性能衡量标准对其是作为实时系统其特性决定了传统的性能衡量标准对其是不适用的。对传统的通用系统的要求是大的系统吞吐量，合不适用的。对传统的通用系统的要求是大的系统吞吐量，合理的响应速度，对每个系统用户相对公平的进行计

28、算资源的理的响应速度，对每个系统用户相对公平的进行计算资源的分配。然而在实时系统中，以上这些要求都不再适用或者是分配。然而在实时系统中，以上这些要求都不再适用或者是不再占重要位置。实时系统中系统的一切动作都以实时任务不再占重要位置。实时系统中系统的一切动作都以实时任务为中心。为次，系统应该向调度程序提供的一些是信息：为中心。为次，系统应该向调度程序提供的一些是信息：就绪时间就绪时间开始截止时间和完成截止时间开始截止时间和完成截止时间处理时间处理时间资源要求资源要求优先级优先级子任务结构子任务结构一、对实时系统的要求一、对实时系统的要求z 调度方式：调度方式：大部分采用抢占式调度方式，具有教高的

29、灵活性，较小大部分采用抢占式调度方式，具有教高的灵活性，较小的延迟，但算法复杂，开销比较大。要求不太严格的系统中，的延迟，但算法复杂，开销比较大。要求不太严格的系统中，也可以采用非剥夺调度方式，以简化系统。也可以采用非剥夺调度方式，以简化系统。z 快速响应外部中断的能力快速响应外部中断的能力紧迫事件出现时，系统可以及时响应。系统需具有快速紧迫事件出现时，系统可以及时响应。系统需具有快速硬件中断机构，使中断间隔尽量短。硬件中断机构，使中断间隔尽量短。z 快速任务分派快速任务分派任务的切换应该尽量快速，使得消耗的时间尽量少任务的切换应该尽量快速，使得消耗的时间尽量少二、二、实时调度算法实时调度算法

30、实时调度是计算机科学中最活跃的研究领域之一。实时调度是计算机科学中最活跃的研究领域之一。z 时间片轮转调度算法时间片轮转调度算法z 非抢占优先权调度算法非抢占优先权调度算法z 基于时钟中断抢占的优先权算法基于时钟中断抢占的优先权算法z 立即抢占的优先权算法立即抢占的优先权算法二、二、实时调度算法实时调度算法z 时间片轮转调度算法时间片轮转调度算法 这种调度算法的基本思想是将处理器的时间分为这种调度算法的基本思想是将处理器的时间分为“帧帧”。一个帧就是一个系统内部时钟触发时钟中断的基本时间。一个帧就是一个系统内部时钟触发时钟中断的基本时间。每个实时任务都在帧中占一段时间。仔细设计帧的大小每个实时

31、任务都在帧中占一段时间。仔细设计帧的大小可以保证系统中所有的实时任务都能在可以保证系统中所有的实时任务都能在deadlinedeadline之前完成。之前完成。而事件触发的实时任务则在每个帧中最后一个周期性实时任而事件触发的实时任务则在每个帧中最后一个周期性实时任务完成之后到帧结束这段时间内得以运行。这种算法在系统务完成之后到帧结束这段时间内得以运行。这种算法在系统相对简单，任务数少，又可以事先定义任务的执行顺序的情相对简单，任务数少，又可以事先定义任务的执行顺序的情况下很有效。况下很有效。二、二、实时调度算法实时调度算法z 非抢占优先权调度算法非抢占优先权调度算法优先级队列算法。这种算法从优

32、先级队列算法。这种算法从FIFOFIFO发展而来。给每个任发展而来。给每个任务设定优先级，然后在务设定优先级，然后在FIFOFIFO中按照优先级排列。这种算法保中按照优先级排列。这种算法保证了高优先级的任务的完成，但是对于低优先级的任务很可证了高优先级的任务的完成，但是对于低优先级的任务很可能无法满足时间的正确性。而且对低优先级的任务来说等待能无法满足时间的正确性。而且对低优先级的任务来说等待的时间是无法预知的。的时间是无法预知的。我们无法知道在什么情况下会发生时间正确性上的错误。我们无法知道在什么情况下会发生时间正确性上的错误。而且必须在设计时仔细的检查任务优先级的设定，要保证不而且必须在设

33、计时仔细的检查任务优先级的设定，要保证不会因为低优先级的任务无法按时完成而破坏整个系统的完整会因为低优先级的任务无法按时完成而破坏整个系统的完整性。这个算法也是与特定应用有关的。当环境或情况变化时性。这个算法也是与特定应用有关的。当环境或情况变化时系统无法随之变化。系统无法随之变化。二、二、实时调度算法实时调度算法z 基于时钟中断抢占的优先权算法基于时钟中断抢占的优先权算法这种算法用于抢先式多任务的实时操作系统。该算法的这种算法用于抢先式多任务的实时操作系统。该算法的基本思想是在系统中使用优先级驱动的可抢先的调度算法。基本思想是在系统中使用优先级驱动的可抢先的调度算法。也就是系统首先调度高优先

34、级的任务运行。低优先级的任务也就是系统首先调度高优先级的任务运行。低优先级的任务在高优先级的任务运行时不能抢先；在高优先级的任务运行时不能抢先；CPUCPU由高优先级进程独由高优先级进程独占。占。当中断发生时，正在运行的任务被中断，进入中断处理。当中断发生时，正在运行的任务被中断，进入中断处理。如果中断引起的操作是属于一个较低优先级的任务的，那么如果中断引起的操作是属于一个较低优先级的任务的，那么为了保证中断被及时的处理，此低优先级进程暂时继承原来为了保证中断被及时的处理，此低优先级进程暂时继承原来当中断发生时正在运行的高优先级任务的优先级。当处理完当中断发生时正在运行的高优先级任务的优先级。

35、当处理完关键区域后，此低优先级任务恢复原来的优先级并被挂起，关键区域后，此低优先级任务恢复原来的优先级并被挂起，然后恢复原来高优先级任务的运行。然后恢复原来高优先级任务的运行。二、二、实时调度算法实时调度算法z 立即抢占的优先权算法立即抢占的优先权算法与算法三的区别在于立即进行调度，而不等待时钟的中与算法三的区别在于立即进行调度，而不等待时钟的中断发生。断发生。三、实时调度实例三、实时调度实例1.具有开始截止时间的非周期实时任务的调度具有开始截止时间的非周期实时任务的调度 在事先知道各任务的开始截止时间，且对调度时延不太在事先知道各任务的开始截止时间，且对调度时延不太严格的请情况下，可采用最早

36、截止时间优先的非剥夺调度策严格的请情况下，可采用最早截止时间优先的非剥夺调度策略。略。例：例：任务到达时间开始截止时间执行时间A024B2155C365D6104调度结果是调度结果是A AC CD DB B 0 4 9 13 17 0 4 9 13 17三、实时调度实例三、实时调度实例2.具有完成截止时间的周期性实时任务的调度具有完成截止时间的周期性实时任务的调度例：一个系统，从两个传感器例：一个系统，从两个传感器A和和B中收集并处理数据。传中收集并处理数据。传感器感器A收集数据的最后期限必须是每收集数据的最后期限必须是每10ms一次，一次，B的最的最后期限是每后期限是每50ms一次。处理每个

37、来自一次。处理每个来自A的数据样本需要的数据样本需要10ms,处理每个来自处理每个来自B的数据样本需要的数据样本需要25ms（包括操作（包括操作系统的开销）。系统的开销）。 如何调度如何调度A、B处理进程？处理进程？进程进程到达时间到达时间执行时间执行时间最后结束期限最后结束期限A(1)01020A(2)201040A(3)401060A(4)601080A(5)8010100B(1)02550B(2)5025100启动最后期限启动最后期限 10305070902575A1A1A2A2B1B1A3A3A4A4B2B20 10 20 30 40 50 60 70 80 90 100 110B1B

38、1B2B2A5A5实时系统的其他问题实时系统的内存和外围设备管理实时系统的内存和外围设备管理实时系统的通信实时系统的通信实时操作系统的内核实时操作系统的内核一、产生死锁的原因一、产生死锁的原因二、二、产生死锁的必要条件产生死锁的必要条件三、处理死锁的四种策略三、处理死锁的四种策略四、鸵鸟算法四、鸵鸟算法.死锁（死锁（Deadlock）：）：假若在一个进程集合中的每个进程都在假若在一个进程集合中的每个进程都在 等待只能由该集合中的其它一个进程才能引发的事件，等待只能由该集合中的其它一个进程才能引发的事件， 那么这种状态被看成是死锁。那么这种状态被看成是死锁。.多数情况下，进程是在等待该集合中的另

39、一个进程正占有的多数情况下，进程是在等待该集合中的另一个进程正占有的 资源。但由于所有进程都在等待，都不能运行，因而无法释资源。但由于所有进程都在等待，都不能运行，因而无法释 放任何资源，于是该集合中的所有进程都不能被唤醒。放任何资源，于是该集合中的所有进程都不能被唤醒。4.6 4.6 死锁的基本概念死锁的基本概念竞争资源引起死锁竞争资源引起死锁 4.6 4.6 死锁的基本概念死锁的基本概念一、产生死锁的原因一、产生死锁的原因资源：资源：在任何时候都只能被一个进程使用的任何对象。在任何时候都只能被一个进程使用的任何对象。资源分类：资源分类： 可剥夺资源：可从拥有它的进程中剥夺而不会产生任何副作

40、用。可剥夺资源：可从拥有它的进程中剥夺而不会产生任何副作用。 不可剥夺资源：从拥有它的进程中剥夺会产生错误。不可剥夺资源：从拥有它的进程中剥夺会产生错误。资源使用顺序：资源使用顺序： 申请资源申请资源使用资源使用资源释放资源。释放资源。 l 某进程申请资源失败，则转为阻塞状态，进入资源等待队列。某进程申请资源失败，则转为阻塞状态，进入资源等待队列。l 申请资源的命令与系统有关。有些系统提供的是申请资源的命令与系统有关。有些系统提供的是request命令；命令； 有些系统则将资源看作特殊文件，用有些系统则将资源看作特殊文件，用open命令打开来表示进命令打开来表示进 程申请资源。另外，程申请资源

41、。另外，P/V操作也可表示对资源的申请和释放。操作也可表示对资源的申请和释放。竞争资源引起死锁竞争资源引起死锁 4.6 4.6 死锁的基本概念死锁的基本概念一、产生死锁的原因一、产生死锁的原因竞争不可剥夺资源可能引发死锁。竞争不可剥夺资源可能引发死锁。例：例：系统中只有一台打印机和一台磁带机。系统中只有一台打印机和一台磁带机。 进程进程p1 进程进程p2 1. request(打印机打印机); 3. request(磁带机磁带机); 2. request(磁带机磁带机); 4. request(打印机打印机); 使用使用; 使用使用; release(打印机打印机); release(打印机打

42、印机); release(磁带机磁带机); release(磁带机磁带机); 进程进程p1和和 进程进程p2交交替占用替占用CPU执行时，执行时，顺序为顺序为1234或或3412 不会出错。但为不会出错。但为 1324 时，会死锁。时，会死锁。进程推进顺序不当引发死锁进程推进顺序不当引发死锁 4.6 4.6 死锁的基本概念死锁的基本概念一、产生死锁的原因一、产生死锁的原因例：进程进程p1和进程和进程p2交替占用交替占用CPU执行时，执行时，顺序为顺序为1或或2或或3时，不会出错。时，不会出错。但为但为 4 时，会时，会死锁。死锁。p1 req(r1) p1 req(r2) p1 rel(r1)

43、 p2 rel(r2)p2 rel(r1)p2 rel(r2)p2 req(r1)p2 req(r2)4 41 12 23 3互斥条件互斥条件 每个资源要么已分配给了一个进程，要么空闲。每个资源要么已分配给了一个进程，要么空闲。请求和保持条件请求和保持条件 已经得到资源的进程可以申请新的资源，申请失败时变为阻塞状已经得到资源的进程可以申请新的资源，申请失败时变为阻塞状 态，此时它仍然保持着原有资源不放。态，此时它仍然保持着原有资源不放。不剥夺条件不剥夺条件 已经分配给一个进程的资源不能被剥夺，只能由占有它的进程主已经分配给一个进程的资源不能被剥夺，只能由占有它的进程主 动释放。动释放。环路等待

44、条件环路等待条件 系统一定有两个或两个以上的进程组成的一条环路，该环路中的系统一定有两个或两个以上的进程组成的一条环路，该环路中的 每个进程都在等待着相邻进程正占用着的资源。每个进程都在等待着相邻进程正占用着的资源。 4.6 4.6 死锁的基本概念死锁的基本概念二、产生死锁的必要条件二、产生死锁的必要条件预防死锁预防死锁 通过破除死锁的四个必要条件之一，来防止通过破除死锁的四个必要条件之一，来防止 死锁产生。死锁产生。避免死锁避免死锁 仔细地对资源进行动态分配，以避免死锁发生。仔细地对资源进行动态分配，以避免死锁发生。检测与解除死锁检测与解除死锁 检测系统中是否出现死锁，若出现则解除掉。检测系

45、统中是否出现死锁，若出现则解除掉。忽略该问题忽略该问题 4.6 4.6 死锁的基本概念死锁的基本概念三、处理死锁的四种策略三、处理死锁的四种策略假装死锁假装死锁永不发生永不发生保证系统保证系统永远不会永远不会发生死锁发生死锁允许系统允许系统发生死锁发生死锁然后解除然后解除思想：思想：不采取任何措施，对死锁视而不见。不采取任何措施，对死锁视而不见。实例：实例：UNIX系统（还有其它许多系统）。系统（还有其它许多系统）。由于不预防、避免死锁，故系统中可能发生死锁。而发由于不预防、避免死锁，故系统中可能发生死锁。而发 生时又无法知道（因不检测），造成系统崩溃，需要重生时又无法知道（因不检测），造成系

46、统崩溃，需要重 启。启。之所以被某些系统采用，是因为死锁不常发生。之所以被某些系统采用，是因为死锁不常发生。 4.6 4.6 死锁的基本概念死锁的基本概念四、鸵鸟算法四、鸵鸟算法一、死锁的预防一、死锁的预防二、二、死锁的避免死锁的避免4.7 4.7 死锁的预防和避免死锁的预防和避免如果能够保证四个必要条件中至少有一个不成立，那么如果能够保证四个必要条件中至少有一个不成立，那么 死锁将不会产生。（死锁将不会产生。（Havender,1968Havender,1968）但其中的但其中的“互斥互斥”条件不能破除。条件不能破除。 4.7 4.7 死锁的预防和避免死锁的预防和避免一、预防死锁一、预防死锁

47、破除破除“请求和保持请求和保持”条件条件 4.7 4.7 死锁的预防和避免死锁的预防和避免一、预防死锁一、预防死锁方法：方法：规定进程在执行前要一次性地申请运行所需全部规定进程在执行前要一次性地申请运行所需全部 资源。只有资源全部到手，进程方可运行，否则资源。只有资源全部到手，进程方可运行，否则 进程等待。进程等待。优点：优点：简单、易于实现。简单、易于实现。 缺点：缺点：1.1.资源利用率低。资源利用率低。 2.2.进程运行被延迟。进程运行被延迟。破除破除“不剥夺不剥夺”条件条件 4.7 4.7 死锁的预防和避免死锁的预防和避免一、预防死锁一、预防死锁方法：方法：保持资源的进程申请新资源失败

48、时，在转为阻塞状态之保持资源的进程申请新资源失败时，在转为阻塞状态之 前，必须释放其占用的全部资源。而该进程自身则必须前，必须释放其占用的全部资源。而该进程自身则必须 等到重新获得原有资源及新资源后，才能重新运行。等到重新获得原有资源及新资源后，才能重新运行。缺点：缺点：实现复杂，代价大。实现复杂，代价大。适用范围：适用范围：资源的状态能够很方便的保存和恢复，例如资源的状态能够很方便的保存和恢复，例如CPUCPU寄寄 存器和存储空间。存器和存储空间。破除破除“环路等待环路等待”条件条件 4.7 4.7 死锁的预防和避免死锁的预防和避免一、预防死锁一、预防死锁方法方法1 1：保证每个进程在任何时

49、候只能占用一个资源。要用第二保证每个进程在任何时候只能占用一个资源。要用第二 个，必须先释放第一个。个，必须先释放第一个。方法方法2 2：将系统中所有资源赋予一个全局编号，进程申请资源时，将系统中所有资源赋予一个全局编号，进程申请资源时， 必须按编号递增顺序进行。必须按编号递增顺序进行。缺点：缺点：1.1.找不出一种人人满意的编号顺序。找不出一种人人满意的编号顺序。 2.2.仍存在资源浪费。仍存在资源浪费。 3.3.用户编程受到限制。用户编程受到限制。思路：思路： 4.7 4.7 死锁的预防和避免死锁的预防和避免二、避免死锁二、避免死锁允许进程动态的申请资源。允许进程动态的申请资源。将系统状态

50、分为将系统状态分为 安全状态：不会发生死锁安全状态：不会发生死锁 不安全状态：可能发生死锁不安全状态：可能发生死锁 避免系统进入不安全状态！避免系统进入不安全状态！做法：做法：每次进行资源分配时，首先检测一下每次进行资源分配时，首先检测一下资源分配后资源分配后系统处系统处 于何种状态，若处于于何种状态，若处于安全安全状态，则正式实施本次状态，则正式实施本次分配分配； 若处于若处于不安全不安全状态，则状态，则不予分配不予分配，申请资源的进程阻塞。，申请资源的进程阻塞。系统的安全状态：系统的安全状态： 4.7 4.7 死锁的预防和避免死锁的预防和避免二、避免死锁二、避免死锁安全状态：安全状态：指系

51、统能按某种顺序如指系统能按某种顺序如（称序列称序列为安全序列），来为每个进程分配其所需资源，为安全序列），来为每个进程分配其所需资源， 直至最大需求，使每个进程都可顺序完成。若系统不存在直至最大需求，使每个进程都可顺序完成。若系统不存在 这样一个安全序列，则称系统处于这样一个安全序列，则称系统处于不安全状态不安全状态。例子：例子：系统有三个进程系统有三个进程P1、P2和和P3 ，共用，共用12台磁带机。台磁带机。 在在T0和和T1时刻，系统的资源分配情况分别如下表时刻，系统的资源分配情况分别如下表a和和b。进程进程 最大需求最大需求 已分配已分配 可用可用 P1 10 5 3 P2 4 2 P

52、3 9 2进程进程 最大需求最大需求 已分配已分配 可用可用 P1 10 5 2 P2 4 2 P3 9 3a ab b 4.7 4.7 死锁的预防和避免死锁的预防和避免二、避免死锁二、避免死锁结果：结果：T0时刻系统处于安全状态。（安全序列时刻系统处于安全状态。（安全序列）P1P2 P3可用可用 5(5)2(2)2(7)35(5)4(0)2(7)15(5)2(7)510(0)2(7)02(7)109(0)312结果：结果：T1时刻系统处于不安全状态。时刻系统处于不安全状态。P1P2 P3可用可用 5(5)2(2)3(6)25(5)4(0)3(6)05(5)3(6)4利用银行家算法避免死锁（利

53、用银行家算法避免死锁（Dijkstra提出提出) ) 4.7 4.7 死锁的预防和避免死锁的预防和避免二、避免死锁二、避免死锁数据结构：数据结构：n个进程（个进程（P1,P2, ,Pn），），m类资源（类资源（R1,R2, ,Rm） 1.可利用资源向量可利用资源向量Available（m） Availablej表示表示Rj类资源的可用数目。类资源的可用数目。 2.最大需求矩阵最大需求矩阵Max（n m） Maxi, j表示进程表示进程Pi对对Rj类资源的最大需求量。类资源的最大需求量。 3.分配矩阵分配矩阵Allocation（n m） Allocation i, j表示已分配给进程表示已分配

54、给进程Pi的的Rj类资源的数目。类资源的数目。 4.需求矩阵需求矩阵Need（n m） Need i, j表示进程表示进程Pi对对Rj类资源的剩余需求量。类资源的剩余需求量。 5.Requesti ：进程进程Pi的请求向量的请求向量 4.7 4.7 死锁的预防和避免死锁的预防和避免二、避免死锁二、避免死锁银行家算法：银行家算法：进程进程Pi发出资源请求发出资源请求RequestiRequesti Needi ?Requesti Availablei ? 试分配：试分配： Available:= Available Requesti Allocationi:= Allocationi + Req

55、uestiNeedi:= Needi Requesti 执行安全性算法，检查分配后的系统状态执行安全性算法，检查分配后的系统状态正式分配正式分配将试分配作废；将试分配作废；恢复原资源分配状态；恢复原资源分配状态；进程进程Pi阻塞。阻塞。状态安全状态安全是是是是状态状态不安全不安全错误错误否否否否进程进程Pi阻塞阻塞 4.7 4.7 死锁的预防和避免死锁的预防和避免二、避免死锁二、避免死锁安全性算法：安全性算法：Work:=Available;Finish i :=false ( i=1,2,n);找一满足下列条件的进程：找一满足下列条件的进程：Finish i =false 且且 Needi

56、Work Work:=Work+Allocationi ; Finish i :=true; 所有进程的所有进程的Finish i =true？找到找到找不到找不到是是不是不是系统系统状态状态安全安全系统系统状态状态不安全不安全 4.7 4.7 死锁的预防和避免死锁的预防和避免二、避免死锁二、避免死锁例：例：系统中有五个进程系统中有五个进程 P0 , P1 , P2 , P3 , P4和三类资源和三类资源A , B , C， 每类资源的数量分别为每类资源的数量分别为10、5、7，在在T0时刻的资源分配情时刻的资源分配情 况如下表。问：况如下表。问：P1发出请求向量发出请求向量Request1

57、(1 ,0 ,2)，能否分配？，能否分配？Process Max Allocation Need Available A B C A B C A B C A B C P0 7 5 3 0 1 0 7 4 3 3 3 2 P1 3 2 2 2 0 0 1 2 2 P2 9 0 2 3 0 2 6 0 0 P3 2 2 2 2 1 1 0 1 1 P4 4 3 3 0 0 2 4 3 1 4.7 4.7 死锁的预防和避免死锁的预防和避免二、避免死锁二、避免死锁结果：结果：因分配后的因分配后的系统状态安全，故可以系统状态安全，故可以 立即将立即将P1所申请的资源分配给它。所申请的资源分配给它。 Pr

58、ocess Max Allocation Need Available P0 7 5 3 0 1 0 7 4 3 3 3 2 P1 3 2 2 2 0 0 1 2 2 P2 9 0 2 3 0 2 6 0 0 P3 2 2 2 2 1 1 0 1 1 P4 4 3 3 0 0 2 4 3 1 Request1 (1 ,0 ,2)试分配试分配（结果见（结果见绿字绿字）2 3 00 2 03 0 2安全性算法：安全性算法：Work= 2 3 0 Finish = falsefalsefalsefalsefalsetrue5 3 27 4 3true7 4 5true10 4 7true10 5 7

59、true一、死锁的检测一、死锁的检测二、二、死锁的解除死锁的解除4.8 4.8 死锁的检测与解除死锁的检测与解除资源分配图资源分配图RAG（Resource Allocation Graph） 4.8 4.8 死锁的检测与解除死锁的检测与解除一、死锁的检测一、死锁的检测 RAG=(N,E)，其中其中: : 结点集结点集N=P R 进程结点子集进程结点子集P=p1,p2, ,pn，用，用 表示。表示。 资源结点子集资源结点子集R=r1,r2, ,rm，用，用 表示，每表示，每 类资源中的一个单位用一个类资源中的一个单位用一个 表示。表示。 请求边请求边 ：进程请求一个单位的资：进程请求一个单位的

60、资 边集边集E包括包括 源并正在等待。源并正在等待。 分配边分配边 ：一个单位的资源已分配：一个单位的资源已分配 给进程。给进程。pirjrjpi死锁定理死锁定理 4.8 4.8 死锁的检测与解除死锁的检测与解除一、死锁的检测一、死锁的检测死锁定理：死锁定理：S为为死锁死锁状态的充分条件是，当且仅当状态的充分条件是，当且仅当S状态的资源状态的资源 分配图是分配图是不可完全简化不可完全简化的。的。RAG的简化过程：的简化过程： 1.找只有分配边而没有请求边相连的进程结点，将其分配边删掉。找只有分配边而没有请求边相连的进程结点，将其分配边删掉。 2.找虽有请求边，但请求边可立即全部转化成分配边的进