第3章处理机调度与死锁

1、第三章 处理机调度与死锁 第三章第三章 处理机调度与死锁处理机调度与死锁 3.1 3.1 处理机调度的层次和调度算法的目标处理机调度的层次和调度算法的目标 3.2 3.2 作业与作业调度作业与作业调度 3.3 3.3 进程调度进程调度 3.4 3.4 实时调度实时调度 3.5 3.5 死锁概述死锁概述 3.6 3.6 预防死锁预防死锁 3.7 3.7 避免死锁避免死锁 3.8 3.8 死锁的检测与解除死锁的检测与解除 第三章 处理机调度与死锁 3.1 处理机调度的层次和调度算法的目标处理机调度的层次和调度算法的目标 3.1.1 处理机调度的层次处理机调度的层次 1. 高级调度高级调度(High

2、 Scheduling) 也称为也称为作业调度作业调度或宏观调度。用于决定把后备队列中的哪或宏观调度。用于决定把后备队列中的哪 些作业调入内存，为它们分配必要的资源，并创建进程。些作业调入内存，为它们分配必要的资源，并创建进程。 高级调度的高级调度的运行频率比较低运行频率比较低，时间尺度通常是分钟、小时，时间尺度通常是分钟、小时 或天。常用于或天。常用于批处理系统。批处理系统。 在每次执行作业调度时，都须做出以下两个决定在每次执行作业调度时，都须做出以下两个决定： 1 1） 接纳多少个作业接纳多少个作业 2 2） 接纳哪些作业接纳哪些作业 第三章 处理机调度与死锁 2. 低级调度低级调度(Lo

3、w Level Scheduling) (抢占式和非抢占式抢占式和非抢占式) 也称也称微观调度、进程调度微观调度、进程调度/ /线程调度线程调度或短程调或短程调 度。度。指根据某种原则从就绪队列中选择一个进程指根据某种原则从就绪队列中选择一个进程 ( (线程线程) )并把处理机分配给该进程并把处理机分配给该进程(线程线程)的具体操作。的具体操作。 一般类型的操作系统中都一般类型的操作系统中都必须有低级调度。必须有低级调度。 低级调度的低级调度的运行频率很高运行频率很高，时间尺度通常是，时间尺度通常是 毫秒级的，几十毫秒（毫秒级的，几十毫秒（10100ms10100ms）便进行一次。）便进行一次

4、。 思考：思考： 低级调度是否存在调几个、调哪几个的问题？低级调度是否存在调几个、调哪几个的问题？ 第三章 处理机调度与死锁 3. 中级调度中级调度(Intermediate-Level Scheduling) 概念：概念：中级调度又称中级调度又称中程调度中程调度，是指在内存使用情况，是指在内存使用情况 紧张时，将一些暂时不能运行的讲程（就绪紧张时，将一些暂时不能运行的讲程（就绪/ /阻塞）从内存阻塞）从内存 对换到外存上（挂起）等待。当以后内存有足够的空闲空对换到外存上（挂起）等待。当以后内存有足够的空闲空 间时，间时，中级调度中级调度再决定将合适的进程（就绪）重新调入内再决定将合适的进程（

5、就绪）重新调入内 存（激活），并修改其状态为就绪状态，挂在就绪队列上存（激活），并修改其状态为就绪状态，挂在就绪队列上 等待进程调度。等待进程调度。 思考：引人中级调度的主要目的是什么？思考：引人中级调度的主要目的是什么？ 为了提高内存的利用率和系统吞吐量。常用在为了提高内存的利用率和系统吞吐量。常用在分时系分时系 统及具有虚拟存储器的系统统及具有虚拟存储器的系统中。中。 它的它的运行频率介于高级调度和低级调度之间运行频率介于高级调度和低级调度之间。 第三章 处理机调度与死锁 3.1.2 处理机调度算法的目标处理机调度算法的目标 1. 处理机调度算法的共同目标处理机调度算法的共同目标 (1)

6、资源利用率资源利用率 (2) 公平性。公平性是指应使诸进程都获得合理的公平性。公平性是指应使诸进程都获得合理的 CPU 时间，不会发生进程饥饿现象。时间，不会发生进程饥饿现象。 (3) 平衡性。尽可能保持系统资源使用的平衡性。平衡性。尽可能保持系统资源使用的平衡性。 (4) 策略强制执行策略强制执行 第三章 处理机调度与死锁 带权周转时间：带权周转时间：作业的周转时间作业的周转时间T T与系统为它提供服务的时间与系统为它提供服务的时间 T TS S之比，即之比，即W W= =T/TT/TS S=(=(运行时间运行时间 + + 等待时间等待时间)/)/运行时间运行时间 =1 + =1 + 等待时

7、间等待时间/ /运行时间运行时间 平均带权周转时间平均带权周转时间: : (1) 平均周转时间短。平均周转时间短。 平均周转时间平均周转时间描述为：描述为： i i i T n T 1 1 n i Si i T T n W 1 1 周转时间周转时间: :从作业提交到系统开始到完成为止的时间间隔。从作业提交到系统开始到完成为止的时间间隔。 即，运行时间即，运行时间+ +等待时间。等待时间。 2. 批处理系统的目标批处理系统的目标 第三章 处理机调度与死锁 （2 2）系统吞吐量高。）系统吞吐量高。 （3 3）处理机利用率高。）处理机利用率高。 3.3.分时系统的目标分时系统的目标 （1 1）响应时

8、间快。 （2）均衡性。系统响应时间的快慢应与用户所请求服 务的复杂性相适应。 4.4.实时系统的目标实时系统的目标 （1）截止时间的保证。 （2）可预测性。 第三章 处理机调度与死锁 3. 2 作业与作业调度作业与作业调度 作业和作业步 (1) 作业(Job)。程序、数据、作业说明书 (2) 作业步(Job Step)。作业的每一个加工步骤 2. 作业控制块(Job Control Block，JCB) 它是作业在系统中存在的标志存在的标志，其中保存 了系统对作业进行管理和调度所需的全部信息。 在JCB中包含的内容有：作业标识、用户名称、 用户账号、作业类型(CPU 繁忙型、I/O 繁忙型、

9、批量型、终端型)、作业状态、调度信息(优先级、 作业运行时间)、资源需求(预计运行时间、要求 内存大小等)、资源使用情况等。 第三章 处理机调度与死锁 3. 作业运行的三个阶段和三种状态 作业从进入系统到运行结束，通常需要经历收容、 运行和完成三个阶段。相应的作业也就有“后备状态”、 “运行状态”和“完成状态”。 (1) 收容阶段。 (2) 运行阶段。 (3) 完成阶段。 第三章 处理机调度与死锁 5.调度算法调度算法 （1 1） 先来先服务调度算法先来先服务调度算法 该算法总是把处理机分配给最先进入就绪队列的该算法总是把处理机分配给最先进入就绪队列的 进程，一个进程一旦分得处理机，便执行下去

10、，直到进程，一个进程一旦分得处理机，便执行下去，直到 该进程完成或阻塞时，才释放处理机。该进程完成或阻塞时，才释放处理机。用于作业调度用于作业调度 或进程调度。或进程调度。 看一个例子：看一个例子： 4.作业调度的主要任务作业调度的主要任务 根据JCB中的信息，检查系统中的资源能否满足作业对资 源的需求，以及按照一定的调度算法，从外存的后备队列中选 取某些作业调入内存，并为它们创建进程、分配必要的资源。 然后再将新创建的进程排在就绪队列上等待调度。 第三章 处理机调度与死锁 TS T 带权周转时间，带权周转时间， W=T/TS 优点优点: :实现简单实现简单. . 缺点缺点: :没考虑作业（进

11、程）的优先级。利于长作业（进程），没考虑作业（进程）的优先级。利于长作业（进程）， 而不利于短作业（进程）。而不利于短作业（进程）。 算法的衡量算法的衡量平均周转时间平均周转时间/平均带权周转时间平均带权周转时间 第三章 处理机调度与死锁 （2 2） 短作业短作业( (进程进程) )优先调度算法优先调度算法 短作业短作业( (进程进程) )优先调度算法优先调度算法SJ(P)FSJ(P)F，是指对短作业，是指对短作业 或短进程优先调度的算法。它们可以分别用于或短进程优先调度的算法。它们可以分别用于作业调度作业调度 和进程调度。和进程调度。 短作业优先短作业优先(SJF)(SJF)的调度算法的调度

12、算法：是：是从后备队列中选择从后备队列中选择 一个或若干个估计运行时间（一个或若干个估计运行时间（CPUCPU执行期）最短的作业，执行期）最短的作业， 将它们调入内存运行。将它们调入内存运行。 短进程优先短进程优先(SPF)(SPF)调度算法调度算法：则：则是从就绪队列中选出是从就绪队列中选出 一估计运行时间最短的进程，将处理机分配给它，一估计运行时间最短的进程，将处理机分配给它，使它使它 立即执行并一直执行到完成，或发生某事件而被阻塞放立即执行并一直执行到完成，或发生某事件而被阻塞放 弃处理机时，再重新调度。弃处理机时，再重新调度。 第三章 处理机调度与死锁 图图 3-4 FCFS3-4 F

13、CFS和和SJFSJF调度算法的性能调度算法的性能 先来先服务调度算法先来先服务调度算法 短作业（进程）优先调度算法短作业（进程）优先调度算法 第三章 处理机调度与死锁 SJ(P)F SJ(P)F调度算法也存在不容忽视的缺点调度算法也存在不容忽视的缺点： (1) (1) 该算法对长作业不利该算法对长作业不利 (2) (2) 该算法该算法完全未考虑作业的紧迫程度完全未考虑作业的紧迫程度，因而不能保证，因而不能保证 紧迫性作业紧迫性作业( (进程进程) )会被及时处理。会被及时处理。 (3) (3) 由于由于作业作业( (进程进程) )的长短难以准确地知道的长短难以准确地知道，只是根据，只是根据

14、用户所提供的估计执行时间而定的。用户所提供的估计执行时间而定的。 第三章 处理机调度与死锁 （3 3） 优先级调度算法和高响应比优先调度算法优先级调度算法和高响应比优先调度算法 1）优先级调度算法）优先级调度算法(基于作业的紧迫程度基于作业的紧迫程度) 该算法总是把处理机分配给就绪队列中具有最该算法总是把处理机分配给就绪队列中具有最 高优先级的作业（进程）。可用于高优先级的作业（进程）。可用于作业调度或进程作业调度或进程 调度。调度。 2）高响应比优先调度算法）高响应比优先调度算法 要求服务时间 要求服务时间等待时间 优先权 优先权的变化规律可描述为：优先权的变化规律可描述为： 第三章 处理机

15、调度与死锁 由于等待时间与服务时间之和，就是系统对该作业的由于等待时间与服务时间之和，就是系统对该作业的 响应时间，故该优先权又相当于响应比响应时间，故该优先权又相当于响应比RP。 要求服务时间 要求服务时间等待时间 优先权 =1 + 等待时间 要求服务的时间 (1) (1) 如果等待时间相同，则要求服务的时间愈短，其优先权愈如果等待时间相同，则要求服务的时间愈短，其优先权愈 高，因而该算法有利于短作业。高，因而该算法有利于短作业。 (2) (2) 当要求服务的时间相同时，作业的优先权决定于其等待时当要求服务的时间相同时，作业的优先权决定于其等待时 间，等待时间愈长，其优先权愈高，因而它实现的

16、是先来先服务。间，等待时间愈长，其优先权愈高，因而它实现的是先来先服务。 (3) (3) 对于长作业，作业的优先级可以随等待时间的增加而提高，对于长作业，作业的优先级可以随等待时间的增加而提高， 当其等待时间足够长时，其优先级便可升到很高，当其等待时间足够长时，其优先级便可升到很高， 从而也可获得处从而也可获得处 理机。理机。 第三章 处理机调度与死锁 作业作业 到达时间到达时间 运行时间运行时间 1 101 10：00 200 2小时小时 2 102 10：10 110 1小时小时 3 103 10：25 2525 25分钟分钟 一个例子 第三章 处理机调度与死锁 3.3 进程调度进程调度

17、3.3.1 进程调度的任务、机制和方式 1. 进程调度的任务 (1) 保存处理机的现场信息。 (2) 按某种算法选取进程。 (3) 把处理器分配给进程。 第三章 处理机调度与死锁 2. 进程调度机制 为了实现进程调度，在进程调度机 制中，应具有如下三个基本部分，如图 3-1所示。 (1) 排队器。 (2) 分派器。 (3) 上下文切换器。 第三章 处理机调度与死锁 3. 进程调度方式 （1）抢占式 （2）非抢占式 第三章 处理机调度与死锁 3.3.2 轮转调度算法轮转调度算法 1. 1. 时间片轮转法（早期）时间片轮转法（早期） （1 1）所有的就绪进程按）所有的就绪进程按先来先服务先来先服务

18、的原则，排成一个队列的原则，排成一个队列 （2 2）每次调度时，把）每次调度时，把CPUCPU分配给队首进程，并令其执行一个时间片。分配给队首进程，并令其执行一个时间片。 （3 3）当执行的时间片用完时，由一个计时器发出时钟中断请求）当执行的时间片用完时，由一个计时器发出时钟中断请求, ,调度程调度程 序便据此信号来停止该进程的执行，并将它送往就绪队列的末尾；若时序便据此信号来停止该进程的执行，并将它送往就绪队列的末尾；若时 间片没有用完就执行结束了，则立即激活调度程序，启动新的时间片。间片没有用完就执行结束了，则立即激活调度程序，启动新的时间片。 （4 4）重复（）重复（2 2） （5 5）

19、 思考：时间片小了好还是大了好？思考：时间片小了好还是大了好？ 若很小若很小：利于短作业，但中断及切换频繁，增加系统开销。：利于短作业，但中断及切换频繁，增加系统开销。 若很大若很大：退化为：退化为FCFSFCFS算法，无法满足交互式用户的需求。算法，无法满足交互式用户的需求。 第三章 处理机调度与死锁 例子（q=1、4） 第三章 处理机调度与死锁 3.3.4 多队列调度算法多队列调度算法 将一个就绪队列拆成若干个 不同类型或不同性质的进程固定在不同 的就绪队列 不同的就绪队列用不同的调度算法 设置不同的优先级 第三章 处理机调度与死锁 3.3.5多级反馈队列调度算法多级反馈队列调度算法 1.

20、调度机制调度机制 (1) 应设置多个就绪队列，并为各个队列赋予不同的优应设置多个就绪队列，并为各个队列赋予不同的优 先级和时间片。先级和时间片。 第一个队列的优先级最高，第一个队列的优先级最高， 第二个队列次之，第二个队列次之， 其余各队列的优先权逐个降低。其余各队列的优先权逐个降低。 优先权愈高的队列中，执行时间片就愈小。优先权愈高的队列中，执行时间片就愈小。 第三章 处理机调度与死锁 图图 3-5 多级反馈队列调度算法多级反馈队列调度算法 最高优先权 次高优先权 最低优先权 第三章 处理机调度与死锁 (2) 当一个新进程进入内存后，首先将它放入第一队列的末当一个新进程进入内存后，首先将它放

21、入第一队列的末 尾，按尾，按FCFS原则排队等待调度。原则排队等待调度。 (3) 仅当第一队列空闲时，调度程序才调度第二队列中的进仅当第一队列空闲时，调度程序才调度第二队列中的进 程运行；仅当第程运行；仅当第1(i-1) 队列均空时，才会调度第队列均空时，才会调度第i队列中的队列中的 进程运行进程运行 思考：思考：（1）当正在执行）当正在执行i队列的进程时，高优先级的队列来队列的进程时，高优先级的队列来 了新进程，该如何处理？了新进程，该如何处理？ （2）被中断的进程进入哪个就绪队列？）被中断的进程进入哪个就绪队列？ 第三章 处理机调度与死锁 2. 多级反馈队列调度算法的性能多级反馈队列调度算

22、法的性能 终端型作业用户终端型作业用户。大多属于交互型的小作业。大多属于交互型的小作业 ，系统，系统 能使它们在第一队列所规定的时间片内完成。能使它们在第一队列所规定的时间片内完成。 (2)(2)短批处理作业用户短批处理作业用户。很短的批处理作业像终端型作。很短的批处理作业像终端型作 业一样在第一队列即可完成，对于稍长的作业，也业一样在第一队列即可完成，对于稍长的作业，也 只需在第二队列和第三队列各执行一个时间片就可只需在第二队列和第三队列各执行一个时间片就可 完成。完成。 (3)(3)长批处理作业用户长批处理作业用户。它将依次在第。它将依次在第1 1，2 2，n n个队个队 列中运行，最后按

23、轮转方式运行。列中运行，最后按轮转方式运行。 能满足各种类型用户的需要：能满足各种类型用户的需要： 第三章 处理机调度与死锁 3.3.6 基于公平原则的调度算法基于公平原则的调度算法 1. 保证调度算法 保证调度算法是另外一种类型的调度算法，它 向用户所做出的保证并不是优先运行，而是明确的 性能保证，该算法可以做到调度的公平性。一种比 较容易实现的性能保证是处理机分配的公平性。保 证每个进程获得相同的处理机时间。 第三章 处理机调度与死锁 在实施公平调度算法时系统中必须具有这样一些功能： (1) 跟踪计算每个进程自创建以来已经执行的处理时间。 (2) 计算每个进程应获得的处理机时间，即自创建以

24、来的 时间除以n。 (3) 计算进程获得处理机时间的比率，即进程实际执行的 处理时间和应获得的处理机时间之比。 (4) 比较各进程获得处理机时间的比率。 (5) 调度程序应选择比率最小的进程将处理机分配给它， 并让该进程一直运行，直到超过最接近它的进程比率为止。 第三章 处理机调度与死锁 2. 公平分享调度算法 分配给每个进程相同的处理机时间，显然，这对诸进 程而言，是体现了一定程度的公平，但如果各个用户所拥 有的进程数不同，就会发生对用户的不公平问题。 用户A：启动4个进程 用户B：启动1个进程 每个进程获得一个时间，对进程而言很公平，但对用户来 说，A（80%）、B（20%）很不公平 第三

25、章 处理机调度与死锁 3.4 实实 时时 调调 度度 3.4.1 实现实时调度的基本条件实现实时调度的基本条件 1. 提供必要的信息提供必要的信息 就绪时间。就绪时间。 (2) 开始截止时间和完成截止时间。开始截止时间和完成截止时间。 (3) 处理时间。处理时间。 (4) 资源要求。资源要求。 (5) 优先级。优先级。 第三章 处理机调度与死锁 2. 系统处理能力强系统处理能力强 假定系统中有假定系统中有m个周期性的硬实时任务，它们的处理时个周期性的硬实时任务，它们的处理时 间可表示为间可表示为Ci，周期时间表示为，周期时间表示为Pi，则在单处理机情况下，则在单处理机情况下， 必须满足下面的限

26、制条件系统才是可调度的：必须满足下面的限制条件系统才是可调度的： m i i i P C 1 1 即保证每个实时任务在一个周期时间内得到及时处理即保证每个实时任务在一个周期时间内得到及时处理 第三章 处理机调度与死锁 例如例如: :系统中有系统中有6个硬实时任务，它们的周期时间都是个硬实时任务，它们的周期时间都是 50 ms， 而每次的处理时间为而每次的处理时间为 10 ms，则不难算出，此时是不能满足上式，则不难算出，此时是不能满足上式 的，的，(10/50)*6 = 1.21，因而系统是，因而系统是不可调度的不可调度的。 再如再如:一个实时系统要处理一个实时系统要处理3 3个事件，其出现周

27、期分别为个事件，其出现周期分别为 100ms100ms、200ms200ms和和500ms500ms，事件的处理时间分别为，事件的处理时间分别为50ms50ms、30ms30ms和和 100ms100ms，则这个系统是任务，则这个系统是任务可调度的可调度的，因为：，因为：50/100 + 30/200 50/100 + 30/200 + 100/500 =0.85 1 + 100/500 =0.85 1 当然隐含的条件是进程切换的时间足够短，可以忽略不计。当然隐含的条件是进程切换的时间足够短，可以忽略不计。 第三章 处理机调度与死锁 系统不可调度时解决的方法是系统不可调度时解决的方法是提高系统

28、的处理提高系统的处理 能力，其途径有二：能力，其途径有二： 其一其一仍是采用单处理机系统，仍是采用单处理机系统， 但须但须增强其处增强其处 理能力理能力， 以显著地以显著地减少对每一个任务的处理时间减少对每一个任务的处理时间； 其二其二是采用是采用多处理机系统。多处理机系统。假定系统中的假定系统中的处理处理 机数为机数为N N，则应将上述的限制条件改为：，则应将上述的限制条件改为： m i i i N P C 1 第三章 处理机调度与死锁 3. 采用抢占式调度机制采用抢占式调度机制 4. 具有快速切换机制具有快速切换机制 (1) 对外部中断的快速响应能力对外部中断的快速响应能力。要求系统具有快

29、速。要求系统具有快速 硬件中断机构，还应使禁止中断的时间间隔硬件中断机构，还应使禁止中断的时间间隔尽量短尽量短。 (2) 快速的任务分派能力快速的任务分派能力。 第三章 处理机调度与死锁 3.4.2 实时调度算法的分类实时调度算法的分类 1. 1. 非抢占式调度算法非抢占式调度算法 非抢占式轮转调度算法。（如下页图（非抢占式轮转调度算法。（如下页图（a a） (2) (2) 非抢占式优先调度算法。非抢占式优先调度算法。（如下页图（如下页图（b） 可按不同的方式加以分类，如根据任务性质的不可按不同的方式加以分类，如根据任务性质的不 同、调度方式的不同、调度程序调度时间的不同和多同、调度方式的不同

30、、调度程序调度时间的不同和多 处理机环境下的调度等分类。处理机环境下的调度等分类。下面仅按调度方式的不下面仅按调度方式的不 同对调度算法进行分类：同对调度算法进行分类： 简单、易实现。简单、易实现。 第三章 处理机调度与死锁 (a) 非抢占轮转调度 当前进程实时进程 实时进程请求调度 实时进程枪占当前 进程，并立即执行 (d) 立即抢占的优先权调度 调度时间 进程 1进程 2 实时进程要求调度 进程 n实时进程 调度实时进程运行 (b) 非抢占优先权调度 当前进程实时进程 实时进程请求调度当前进程运行完成 调度时间 当前进程 实时进程请求调度时钟中断到来时 调度时间 (c) 基于时钟中断抢占的

31、优先权抢占调度 调度时间 实时进程 2. 抢占式调度算法抢占式调度算法 基于时钟中断的抢占式优先权调度算法。基于时钟中断的抢占式优先权调度算法。( (如下图如下图c)c) (2) (2) 立即抢占的优先权调度算法。立即抢占的优先权调度算法。( (如下图如下图d) d) 图 3-6 实时进程调度 . 第三章 处理机调度与死锁 3.4.3最早截止时间优先即最早截止时间优先即EDF算法算法(开始截至时间开始截至时间) 图图 3-7 EDF3-7 EDF算法用于非抢占调度方式算法用于非抢占调度方式 任务任务1 1的开始截至时间的开始截至时间 1342 时间时间t t 时间 该算法依据截止时间确定任务的

32、优先级，截止 时间越早，优先级越高。 （1）非抢占式调度方式用于非周期性实时任务 第三章 处理机调度与死锁 （1）抢占式调度方式用于周期性实时任务 A：周期20ms 处理时间：10ms B：周期50ms 处理时间：25ms 思考：这两个实时任务的处理轨迹 第三章 处理机调度与死锁 第三章 处理机调度与死锁 2. 2. 最低松弛度优先即最低松弛度优先即LLF(Least Laxity First)LLF(Least Laxity First)算法算法 该算法是根据任务紧急该算法是根据任务紧急( (或松弛或松弛) )的程度，来确定任务的优先级。的程度，来确定任务的优先级。 任务的松弛度任务的松弛度

33、= =任务必须完成时间任务必须完成时间- -其本身的运行时间其本身的运行时间- -当前时间当前时间 该算法主要用于可抢占调度方式中。该算法主要用于可抢占调度方式中。 如上例：如上例：A A和和B B两个周期性任务，它们的周期和处理时间为两个周期性任务，它们的周期和处理时间为A A（20,1020,10）、）、B B （50,2550,25） A1A2A3A4A5A6A7A8 20406080100120140160 B1B2B3 t 0 1070554530 第三章 处理机调度与死锁 执行过程（板书）：执行过程（板书）： t1 A1(10) 10203040506080 t 0 t1 0 B1

34、(20) t2t3 70 A2(10)A3(10)A4(10) t4t5t6t7t8 B1(5)B2(15)B2(10) 第三章 处理机调度与死锁 3.4.5 优先级倒置(priority inversion problem) 1. 优先级倒置的形成 当前OS广泛采用优先级调度算法和抢占方式，然而在系 统中存在着影响进程运行的资源而可能产生“优先级倒置” 的现象，即高优先级进程(或线程)被低优先级进程(或线程) 延迟或阻塞。我们通过一个例子来说明该问题。 P1:P(mutex);CS-1;V(mutex); 优先级最高 P2:program2; 优先级其次 P3: :P(mutex);CS-3

35、;V(mutex); 优先级最底 第三章 处理机调度与死锁 假如P3最先执行，在执行了P(mutex)操作后，进入到临 界区CS-3。在时刻a，P2就绪，因为它比P3的优先级高，P2抢 占了P3的处理机而运行，如图3-10所示。 第三章 处理机调度与死锁 2. 优先级倒置的解决方法 （1）规定：假如进程P3在进入临界区后P3所占用的处 理机就不允许被抢占。 （2）采用动态优先级继承方法。 第三章 处理机调度与死锁 作业 四个作业进入系统， 分别计算在FCFS， SJF和HRRF算法下的 平均周转时间与带权 周转时间（时间用十 进制表示，单位：小 时） 第三章 处理机调度与死锁 3.53.5 死

36、锁概述死锁概述 指指多个多个进程因进程因竞争共享资源竞争共享资源而造成的一种而造成的一种僵僵 局局，若无外力作用，这些进程都将永远不能再，若无外力作用，这些进程都将永远不能再 向前推进。在这些进程中，每个进程都无限等向前推进。在这些进程中，每个进程都无限等 待被该组进程中另一进程所占有的资源，因而待被该组进程中另一进程所占有的资源，因而 永远无法得到的资源，这种现象称为永远无法得到的资源，这种现象称为进程死锁进程死锁， 这一组进程就称为这一组进程就称为死锁进程死锁进程。 3.5.1 3.5.1 产生死锁的原因产生死锁的原因 第三章 处理机调度与死锁 1. 1. 竞争资源引起进程死锁竞争资源引起

37、进程死锁 资源的分类资源的分类：可抢占性资源、不：可抢占性资源、不可抢占性可抢占性资源；可资源；可 重用性（永久性）资源和可消耗性（临时性）资源。重用性（永久性）资源和可消耗性（临时性）资源。 2) 2) 竞争不可抢占性资源竞争不可抢占性资源 3.5.1 3.5.1 产生死锁的原因产生死锁的原因 R1R2 P 1 P 2 进程进程 磁带机磁带机打印机打印机 图图 3-12 I/O3-12 I/O设备共享时的死锁情况设备共享时的死锁情况 第三章 处理机调度与死锁 图图 3-13 3-13 进程之间通信时的死锁进程之间通信时的死锁 3) 3) 竞争可竞争可消耗性消耗性资源资源( (临时性资源临时性

38、资源) ) S 2 P 1 S 3 P 3 S 1 P 2 消息消息 消息消息 消息消息 例如例如：三进程通信，各进程先接收对方的消息，：三进程通信，各进程先接收对方的消息， 再释放自己产生的消息，则可能发生死锁，如下图：再释放自己产生的消息，则可能发生死锁，如下图： 第三章 处理机调度与死锁 2. 进程推进顺序不当引起死锁进程推进顺序不当引起死锁 图图 3-14 3-14 进程推进顺序对死锁的影响进程推进顺序对死锁的影响 第三章 处理机调度与死锁 思考总结：死锁的一些结论思考总结：死锁的一些结论 参与死锁的进程最少是几个？参与死锁的进程最少是几个？ 两个两个 参与死锁的进程至少有几个已经占有

39、资源？参与死锁的进程至少有几个已经占有资源？ 两个两个 参与死锁进程有几个在等待资源？参与死锁进程有几个在等待资源？ 所有死锁进程所有死锁进程 参与死锁的进程构成的集合与是当前系统中所有进参与死锁的进程构成的集合与是当前系统中所有进 程构成的集合什么关系？程构成的集合什么关系？ 子集子集 第三章 处理机调度与死锁 3.5.2 3.5.2 产生死锁的必要条件产生死锁的必要条件 （1 1）互斥条件）互斥条件 （2 2）请求和保持条件）请求和保持条件 （3 3）不剥夺条件）不剥夺条件 （4 4）环路等待条件）环路等待条件 第三章 处理机调度与死锁 3.5.3 3.5.3 处理死锁的基本方法处理死锁的

40、基本方法 预防死锁。预防死锁。 (2) (2) 避免死锁。避免死锁。 (3) (3) 检测死锁。检测死锁。 (4) (4) 解除死锁。解除死锁。 第三章 处理机调度与死锁 3.6 3.6 预防死锁预防死锁 破坏破坏“请求和保持请求和保持”条件。条件。 所有进程开始运行之前，一次性申请其在整个运所有进程开始运行之前，一次性申请其在整个运 行过程中所需要的全部资源。行过程中所需要的全部资源。 缺点缺点资源浪费、饥饿资源浪费、饥饿 允许一个进程只获得运行初期所需要的资源后便允许一个进程只获得运行初期所需要的资源后便 开始运行，运行过程中，逐步释放已分配给自己、开始运行，运行过程中，逐步释放已分配给自

41、己、 且已经使用完毕的全部资源，然后再请求新的所且已经使用完毕的全部资源，然后再请求新的所 需资源。需资源。 在系统设计时确定资源分配算法，保证不在系统设计时确定资源分配算法，保证不 发生死锁。具体的做法是发生死锁。具体的做法是破坏产生死锁的四个破坏产生死锁的四个 必要条件之一。必要条件之一。 第三章 处理机调度与死锁 3.3.破坏破坏“循环等待循环等待”条件条件。 将所有的资源按照类型进行线性排队，并赋予将所有的资源按照类型进行线性排队，并赋予 不同的序号，规定申请资源时要按照序号递增不同的序号，规定申请资源时要按照序号递增 的次序申请资源。的次序申请资源。 缺点：限制新设备的增加、资源浪费

42、、限制用缺点：限制新设备的增加、资源浪费、限制用 户简单、自主地编程。户简单、自主地编程。 2.2.破坏破坏“不可抢占不可抢占”条件条件 。 当某进程新的资源未满足时，释放已占有的所当某进程新的资源未满足时，释放已占有的所 有资源。有资源。 缺点：前段工作丢失、很难保证连续、执行被缺点：前段工作丢失、很难保证连续、执行被 无限推迟）无限推迟） 第三章 处理机调度与死锁 1. 1. 安全状态安全状态 所谓所谓安全状态安全状态，是指系统能按某种进程顺序，是指系统能按某种进程顺序(P(P1 1, P, P2 2, , ， P Pn n)()(称称P P1 1, P, P2 2, , P, , Pn

43、n序列为序列为安全序列安全序列) )，来为每个进程，来为每个进程 P Pi i分配其所需资源，直至满足每个进程对资源的最大需求，分配其所需资源，直至满足每个进程对资源的最大需求， 使每个进程都可顺利地完成。使每个进程都可顺利地完成。 如果系统无法找到这样一个安全序列，则称系统处于如果系统无法找到这样一个安全序列，则称系统处于不不 安全状态安全状态。 当系统进入不安全状态后，当系统进入不安全状态后，可能可能进入死锁状态。但只要进入死锁状态。但只要 系统处于安全状态，就一定不会进入死锁状态。系统处于安全状态，就一定不会进入死锁状态。 3.7 3.7 死锁避免死锁避免 3.7.1 3.7.1 系统安

44、全状态系统安全状态 第三章 处理机调度与死锁 2. 2. 安全状态之例安全状态之例 假定系统中有三个进程假定系统中有三个进程P P1 1、 P P2 2和和P P3 3，共有，共有1212台磁带机。台磁带机。 进程进程P P1 1总共要求总共要求1010台磁带机，台磁带机，P P2 2和和P P3 3分别要求分别要求4 4台和台和9 9台。假台。假 设在设在T T0 0时刻，进程时刻，进程P P1 1、P P2 2和和P P3 3已分别获得已分别获得5 5台、台、2 2台和台和2 2台磁台磁 带机，尚有带机，尚有3 3台空闲未分配，如下表所示：台空闲未分配，如下表所示： 经分析经分析T0时刻系

45、统是安全的，此时存在安全序列时刻系统是安全的，此时存在安全序列 P2P3。 第三章 处理机调度与死锁 3. 3. 由安全状态向不安全状态的转换由安全状态向不安全状态的转换 如果不按照安全序列分配资源，则系统可能会由安全如果不按照安全序列分配资源，则系统可能会由安全 状态进入不安全状态状态进入不安全状态。 例如例如，在，在T T0 0时刻以后，时刻以后，P P3 3又请求又请求1 1台磁带机，若此时系台磁带机，若此时系 统把剩余统把剩余3 3台中的台中的1 1台分配给台分配给P P3 3，则系统便进入不安全状态。，则系统便进入不安全状态。 因为，因为，此时也无法再找到一个安全序列此时也无法再找到

46、一个安全序列 第三章 处理机调度与死锁 3.7.2 3.7.2 利用银行家算法避免死锁利用银行家算法避免死锁 1. 1. 银行家算法中的数据结构银行家算法中的数据结构 (1) (1) 可利用资源向量可利用资源向量AvailableAvailable。 这是一个含有这是一个含有m m个元素的数组，其中的每一个元素代表个元素的数组，其中的每一个元素代表 一类可利用的资源数目，一类可利用的资源数目，其初始值其初始值是系统中所配置的该类是系统中所配置的该类 全部可用资源的数目，其数值随该类资源的分配和回收而全部可用资源的数目，其数值随该类资源的分配和回收而 动态地改变。动态地改变。 如果如果Avail

47、ablej=K，则表示系统中现有，则表示系统中现有R Rj j类资源类资源K K 个。个。 第三章 处理机调度与死锁 (2) (2) 最大需求矩阵最大需求矩阵MaxMax。这是一个。这是一个n nm m的矩阵，它定义了的矩阵，它定义了 系统中系统中n n个进程中的每一个进程对个进程中的每一个进程对m m类资源的最大需求。类资源的最大需求。如果如果 Maxi,j=K, ,则表示进程则表示进程i i需要需要R Rj j类资源的最大数目为类资源的最大数目为K.K. (3) (3) 分配矩阵分配矩阵AllocationAllocation。这也是一个。这也是一个n nm m的矩阵，它的矩阵，它 定义了

48、系统中每一类资源当前已分配给每一进程的资源数。定义了系统中每一类资源当前已分配给每一进程的资源数。如如 果果Allocationi,j=K，则表示进程，则表示进程i i当前已分得当前已分得R Rj j类资源的数类资源的数 目为目为K K。 (4) (4) 需求矩阵需求矩阵NeedNeed。这也是一个。这也是一个n nm m的矩阵，用以表示每的矩阵，用以表示每 一个进程尚需的各类资源数。一个进程尚需的各类资源数。如果如果Needi,j=K，则表示进，则表示进 程程i i还需要还需要R Rj j类资源类资源K K个，方能完成其任务。个，方能完成其任务。 可得：可得：Needi,j= Maxi,j-

49、 Allocationi,j 第三章 处理机调度与死锁 2. 2. 银行家算法银行家算法 设设RequestRequesti i是进程是进程P Pi i的请求向量，的请求向量，如果如果Requestij =K，表示进程，表示进程P Pi i当前时刻请求当前时刻请求K K个个R Rj j类型的资源类型的资源。当。当P Pi i发出发出 资源请求后，系统按下述步骤进行检查：资源请求后，系统按下述步骤进行检查： (1) (1) 如果如果RequestijNeedi,j，便转向步骤便转向步骤2 2； 否则认为出错。否则认为出错。 (2) (2) 如果如果RequestijAvailablej，便转向步

50、骤便转向步骤 (3)(3)；否则，；否则， 表示尚无足够资源，表示尚无足够资源，P Pi i须等待。须等待。 第三章 处理机调度与死锁 (3) (3) 系统试探着把资源分配给进程系统试探着把资源分配给进程P Pi i，并修改下面数据，并修改下面数据 结构中的数值：结构中的数值： Availablej=Availablej-Requestij; Allocationi,j=Allocationi,j+Requestij; Needi,j=Needi,j-Requestij; (4) (4) 系统执行安全性算法系统执行安全性算法，检查此次资源分配后，系统，检查此次资源分配后，系统 是否处于安全状态

51、。是否处于安全状态。若安全，才正式将资源分配给进程若安全，才正式将资源分配给进程P Pi i， 以完成本次分配；以完成本次分配；否则，将本次的试探分配作废否则，将本次的试探分配作废，恢复原来，恢复原来 的资源分配状态，让进程的资源分配状态，让进程P Pi i等待。等待。 第三章 处理机调度与死锁 3. 3. 安全性算法安全性算法 (1) (1) 设置两个向量：设置两个向量： 工作向量工作向量Work:Work: 它表示系统可提供给进程继续它表示系统可提供给进程继续 运行所需的各类资源数目，它含有运行所需的各类资源数目，它含有m m个元素，在执行安个元素，在执行安 全算法全算法开始时，开始时，W

52、ork=Available; ; Finish Finish: : 它表示系统是否有足够的资源分配给它表示系统是否有足够的资源分配给 进程，使之运行完成。开始时先做进程，使之运行完成。开始时先做Finishi=false; ; 当有足够资源分配给进程时，再令当有足够资源分配给进程时，再令Finishi=true。 第三章 处理机调度与死锁 (2) (2) 从进程集合中找到一个能满足下述条件的进程从进程集合中找到一个能满足下述条件的进程： Finishi= =false; Needi,jWorkj； 若找到，执行步骤若找到，执行步骤(3)(3)，否则，执行步骤，否则，执行步骤(4)(4)。 (3

53、) (3) 当进程当进程P Pi i获得资源后，可顺利执行，直至完成，并获得资源后，可顺利执行，直至完成，并 释放出分配给它的资源，释放出分配给它的资源，故应执行：故应执行： Workj=Workj+ Allocationi,j; Finishi=true; go to step 2; (4) (4) 如果所有进程的如果所有进程的FinishFinishi i=true=true都满足，都满足， 则表则表 示系统处于安全状态；否则，系统处于不安全状态。示系统处于安全状态；否则，系统处于不安全状态。 第三章 处理机调度与死锁 4. 4. 银行家算法之例银行家算法之例 假定系统中有五个进程假定系统

54、中有五个进程P P0 0, P, P1 1, P, P2 2, P, P3 3, P, P4 4和三类资源和三类资源 A, B, CA, B, C，各种资源的数量分别为，各种资源的数量分别为1010、5 5、7 7，在，在T T0 0时刻的时刻的 资源分配情况如图资源分配情况如图 3-15 3-15 所示。所示。T T0 0时刻系统安全吗？时刻系统安全吗？ 图图 3-15 3-15 T T0 0时刻的资源分配表时刻的资源分配表 所以所以T T0 0时刻系统是安时刻系统是安 全的，存在安全序列全的，存在安全序列 P1,P3,P4,P0,P2P1,P3,P4,P0,P2 第三章 处理机调度与死锁

55、(1) T0时刻的安全性时刻的安全性 图图 3-16 3-16 T T0 0时刻的安全序列时刻的安全序列 第三章 处理机调度与死锁 (2) P(2) P1 1请求资源请求资源 P P1 1发出请求向量发出请求向量Request1(1，0，2)，系统按银行家算，系统按银行家算 法进行检查：法进行检查： Request1(1, 0, 2)Need1(1, 2, 2) Request1(1, 0, 2)Available1(3, 3, 2) 系统先假定可为系统先假定可为P P1 1分配资源，并修改分配资源，并修改Available, Allocation1和和Need1向量，由此形成的资源变化情况如

56、图向量，由此形成的资源变化情况如图 3-15 3-15 中的圆括号所示。中的圆括号所示。 再利用安全性算法检查此时系统是否安全。再利用安全性算法检查此时系统是否安全。 第三章 处理机调度与死锁 P1 P1发出请求向量发出请求向量Request1(1Request1(1，0 0，2)2)，并进行试，并进行试 分配后分配后形成的资源变化情况如下图中的圆括号所示：形成的资源变化情况如下图中的圆括号所示： 经过安全性算法检查，存在安经过安全性算法检查，存在安 全序列全序列P1,P3,P4,P2,P0, P1,P3,P4,P2,P0, 因因 此系统是安全的，正式分配此系统是安全的，正式分配 第三章 处理

57、机调度与死锁 图图 3-17 P3-17 P1 1申请资源时的安全性检查申请资源时的安全性检查 4. 4. 银行家算法之例银行家算法之例 第三章 处理机调度与死锁 (3) P(3) P4 4请求资源请求资源：P P4 4发出请求向量发出请求向量Request4(3，3，0)，系统，系统 按银行家算法进行检查：按银行家算法进行检查： Request4(3, 3, 0) Need4(4, 3, 1); Request4(3, 3, 0) Available(2, 3, 0)，让让P P4 4等待等待。 (4) P(4) P0 0请求资源请求资源：P P0 0发出请求向量发出请求向量Requst0(

58、0，2，0)，系统，系统 按银行家算法进行检查：按银行家算法进行检查： Request0(0, 2, 0)Needt0 (7, 4, 3); Request0(0, 2, 0)Available(2, 3, 0); 系统暂时先假定可为系统暂时先假定可为P P0 0分配资源，并修改有关数据，分配资源，并修改有关数据， 如图如图 3-18 3-18 所示。所示。 第三章 处理机调度与死锁 图图 3-18 3-18 为为P P0 0分配资源后的有关资源数据分配资源后的有关资源数据 (5)(5)进行安全性检查：进行安全性检查：可用资源可用资源Available(2.1.0)已不能满足任何进已不能满足任

59、何进 程的需要，故程的需要，故系统该进入不安全状态，此时系统不分配资源系统该进入不安全状态，此时系统不分配资源。 4. 4. 银行家算法之例银行家算法之例 第三章 处理机调度与死锁 （1 1）操作系统要定时运行）操作系统要定时运行“死锁检测死锁检测”程序程序 （2 2）解除死锁并以最小的代价恢复操作系统运行解除死锁并以最小的代价恢复操作系统运行。 思考：死锁检测的思考：死锁检测的难点在哪？难点在哪？ 3.8 3.8 死锁的检测与解除死锁的检测与解除 何时运行死锁检测程序？何时运行死锁检测程序？ 1. 1. 当进程等待时检测死锁。当进程等待时检测死锁。 ( (其缺点是系统的开销大）其缺点是系统的开销大） 2. 2. 定时检测。定时检测。 3. 3. 系统资源利用率下降时检测死锁。系统资源利用率下降时检测死锁。 第三章 处理机调度与死锁 3.8.1 死锁的检测死锁的检测 1. 资源分配图资源分配图(Resource Allocation Graph) 图图 3-19 3-19 每类资源有多个时的情况每类资源有多个时的情况 P 1 P 2 r1r2 用用有向图有向图描述进程的死锁比较准确、形象。描述进程的死锁比较准确、形象。 系统由若干类资源构成，一类资源称为一个系统由若干类资源构成，一类资源称为一个资源类资源类； 每个资源类中包含若干个同种资源，称为每