03处理机调度与死锁严军勇

1、processes scheduling and deadlock april 2012 , caixia wang第三章第三章processes scheduling and deadlock april 2012 , caixia wang执行执行活动活动就绪就绪静止静止就绪就绪活动活动阻塞阻塞静止静止阻塞阻塞激活激活挂起挂起接纳接纳新建新建终止终止分派分派/调度调度时间片用完时间片用完激活激活挂起挂起事件发生事件发生完成完成事件发生事件发生事件等待事件等待processes scheduling and deadlock april 2012 , caixia wang1、调度类型、调度

2、类型2、调度准则、调度准则3、调度算法、调度算法4、实时调度、实时调度5、死锁与饥饿、死锁与饥饿processes scheduling and deadlock april 2012 , caixia wangby the end of this lecture you should be able to:v 解释什么是响应时间解释什么是响应时间, 周转时间周转时间, 截至时间，吞吐量截至时间，吞吐量v 理解进程调度的目标、类型、原则理解进程调度的目标、类型、原则v 理解决策方式理解决策方式: 非抢占非抢占 &抢占抢占v 分析掌握主要调度算法：分析掌握主要调度算法：fcfs, 时间片

3、轮转，短作业时间片轮转，短作业优先，高优先权优先优先，高优先权优先， 高响应比优先，反馈高响应比优先，反馈v 理解理解实时系统及类型实时系统及类型v 实时操作系统的特征实时操作系统的特征v 理解掌握：实时调度，截止调度理解掌握：实时调度，截止调度v 理解理解死锁条件、预防死锁死锁条件、预防死锁 、 避免死锁、避免死锁、 检测死锁、检测死锁、 解除死锁解除死锁, 银行家算法银行家算法 (安全状态安全状态 vs. 不安全状态不安全状态 )processes scheduling and deadlock april 2012 , caixia wangvresponse time（响应时间）（响应

4、时间）vthroughput（系统吞吐量）（系统吞吐量）vprocessor efficiency（处理机效率）（处理机效率）vfairness(公平性，防止进程饥饿公平性，防止进程饥饿)processes scheduling and deadlock april 2012 , caixia wangv按调度的层次划分：按调度的层次划分： long-term scheduling（长程调度）长程调度） medium-term scheduling（中程调度）中程调度） short-term scheduling（短程调度）短程调度）processes scheduling and deadl

5、ock april 2012 , caixia wang 又称为高级调度、作业调度又称为高级调度、作业调度，它为被调度作业或用户程，它为被调度作业或用户程序创建进程、分配必要的系统资源，并将新创建的进序创建进程、分配必要的系统资源，并将新创建的进程插入程插入就绪队列就绪队列，等待短程调度，等待短程调度v 作业：比程序更广泛，包含通常的程序和数据，还配作业：比程序更广泛，包含通常的程序和数据，还配有一份作业说明书，系统根据作业说明书对程序的运有一份作业说明书，系统根据作业说明书对程序的运行进行控制。在批处理系统中，是以作业为基本单位行进行控制。在批处理系统中，是以作业为基本单位从外存调入内存的。

6、从外存调入内存的。v 作业步：在作业运行期间，每个作业都必须经过若干作业步：在作业运行期间，每个作业都必须经过若干个相对独立又相互关联的顺序加工步骤才能得到结果，个相对独立又相互关联的顺序加工步骤才能得到结果，把其中的每一个加工步骤成为一个作业步。把其中的每一个加工步骤成为一个作业步。v 作业步一般分成：编译、连接装配、运行。作业步一般分成：编译、连接装配、运行。processes scheduling and deadlock april 2012 , caixia wangv 作业控制块（作业控制块（jcb）：作业在系统中的标志，其中保存）：作业在系统中的标志，其中保存了系统对作业进行管理

7、和调度所需的全部信息。了系统对作业进行管理和调度所需的全部信息。v 每当作业进入系统时，系统便为每个作业建立一个每当作业进入系统时，系统便为每个作业建立一个pcb，根据作业类型将它插入相应的后备队列中。作业调度程根据作业类型将它插入相应的后备队列中。作业调度程序依据一定的调度算法来调度它们，被调度到的作业将序依据一定的调度算法来调度它们，被调度到的作业将会装入内存。会装入内存。v 在作业运行期间，系统就按照在作业运行期间，系统就按照jcb中的信息对作业进行中的信息对作业进行控制。控制。v 当一个作业执行结束进入完成状态时，系统负责回收分当一个作业执行结束进入完成状态时，系统负责回收分配给它的资

8、源，撤销它的作业控制块配给它的资源，撤销它的作业控制块。processes scheduling and deadlock april 2012 , caixia wangv 作业调度功能：根据作业控制块中的信息，审查系统能否满作业调度功能：根据作业控制块中的信息，审查系统能否满足用户作业的资源需求，以及按照一定的算法，从外存的后足用户作业的资源需求，以及按照一定的算法，从外存的后备队列中选取某些作业调入内存，并为它们创建进程、分配备队列中选取某些作业调入内存，并为它们创建进程、分配必要的资源。然后再将新创建的进程插入就绪队列，准备执必要的资源。然后再将新创建的进程插入就绪队列，准备执行。行。

9、v 作业进入系统后，先驻留在磁盘上（批处理队列中）。长程作业进入系统后，先驻留在磁盘上（批处理队列中）。长程调度从该队列中选择作业，为之创建进程。在每次执行作业调度从该队列中选择作业，为之创建进程。在每次执行作业调度时，都须做出以下两个决定：调度时，都须做出以下两个决定： 1) 接纳多少个作业：太多或太少都不可接纳多少个作业：太多或太少都不可 2) 接纳哪些作业接纳哪些作业 ：调度算法：调度算法processes scheduling and deadlock april 2012 , caixia wangv又称为进程调度、低级调度又称为进程调度、低级调度，调度内存中的就绪进程执行。调度内存

10、中的就绪进程执行。v 功能功能:决定就绪队列决定就绪队列whichwhich进程将获得处理机进程将获得处理机 1 1、保存处理机的现场信息，、保存处理机的现场信息， 2 2、按某种算法选取进程，、按某种算法选取进程， 3 3、把处理机分配给进程。、把处理机分配给进程。v 进程调度中的三个基本机制进程调度中的三个基本机制 1 1、排队器、排队器 2 2、分派器、分派器 3 3、上下文切换机制、上下文切换机制v 进程调度方式进程调度方式 非抢占方式：非抢占方式： 简单，实时性差简单，实时性差 抢占方式抢占方式: :时间片原则、优先权原则、短作业优先原则。时间片原则、优先权原则、短作业优先原则。pr

11、ocesses scheduling and deadlock april 2012 , caixia wang 又称为中级调度又称为中级调度，它调度换出到磁盘的进程进入内，它调度换出到磁盘的进程进入内存，准备执行存，准备执行v中程调度中程调度配合配合对换技术对换技术使用。使用。v其目的是其目的是为了提高内存的利用率和系统吞吐量为了提高内存的利用率和系统吞吐量。v在多道程序度允许的情况下，从外存选择一个挂起在多道程序度允许的情况下，从外存选择一个挂起状态的进程调度到内存（换入）状态的进程调度到内存（换入） processes scheduling and deadlock april 2012

12、 , caixia wang短程短程调度调度中程中程调度调度新建新建就绪就绪执行执行长程长程调度调度阻塞阻塞/ /挂起挂起阻塞阻塞图图3-1 3-1 调度与进程状态转换调度与进程状态转换就绪就绪/ /挂起挂起总结总结外存外存内存内存占用占用cpuprocesses scheduling and deadlock april 2012 , caixia wangv一、仅有进程调度的队列模型一、仅有进程调度的队列模型就绪队列就绪队列cpu阻塞队列阻塞队列交互用户交互用户时间片完时间片完进程调度进程调度进程完成进程完成等待事件等待事件事事件件出出现现processes scheduling and

13、deadlock april 2012 , caixia wangv二、具有高二、具有高/ /低级模型低级模型就绪队列就绪队列cpu阻塞队列阻塞队列时间片完时间片完进程调度进程调度进程进程完成完成等待事件等待事件1事件事件1出现出现后备队列后备队列阻塞队列阻塞队列等待事件等待事件2事件事件2出现出现作业调度作业调度processes scheduling and deadlock april 2012 , caixia wang就绪队列就绪队列cpu就绪、挂起队列就绪、挂起队列时间片完时间片完进程调度进程调度进程进程完成完成后备队列后备队列阻塞、挂起队列阻塞、挂起队列事件出现事件出现作业调度作

14、业调度阻塞队列阻塞队列等待事件等待事件挂起挂起事件出现事件出现中级调度中级调度交互型作业交互型作业processes scheduling and deadlock april 2012 , caixia wangv 一、面向用户的准则一、面向用户的准则1 1 周转时间短（常用于批处理系统）周转时间短（常用于批处理系统） 概念：作业从提交概念：作业从提交 完成的时间完成的时间. .分为：分为： （1 1）驻外等待调度时间）驻外等待调度时间 （2 2）驻内等待调度时间）驻内等待调度时间 （3 3）执行时间）执行时间 （4 4）阻塞时间）阻塞时间processes scheduling and d

15、eadlock april 2012 , caixia wangv 一、面向用户的准则一、面向用户的准则 平均周转时间平均周转时间 平均带权周转时间平均带权周转时间 可见带权可见带权w w越小越好越小越好,ts,ts为实际服务时间。为实际服务时间。11niitnt11nisittnwprocesses scheduling and deadlock april 2012 , caixia wangv 一、面向用户的准则一、面向用户的准则2 2 响应时间快：（对交互性作业）响应时间快：（对交互性作业） 概念：键盘提交请求到首次响应时间概念：键盘提交请求到首次响应时间 （1 1）输入传送时间）输入

16、传送时间 （2 2）处理时间）处理时间 （3 3）响应传送时间）响应传送时间3 3 截止时间的保证：即某任务开始执行的最迟时截止时间的保证：即某任务开始执行的最迟时间或必须完成的最迟时间。（特别于实时系统）间或必须完成的最迟时间。（特别于实时系统）4 4 优先权准则：（即需要抢占调度）优先权准则：（即需要抢占调度）processes scheduling and deadlock april 2012 , caixia wangv 二、面向系统的准则二、面向系统的准则1 1 吞吐量高（特别于批处理）：单位时间完成作吞吐量高（特别于批处理）：单位时间完成作业数业数2 2 处理机利用率好：（因处理

17、机利用率好：（因cpucpu贵，特别于大中型贵，特别于大中型多用户系统）多用户系统）3 3 各类资源的平衡利用。（？折算标准）各类资源的平衡利用。（？折算标准）processes scheduling and deadlock april 2012 , caixia wangv.1先来先服务和短作业（进程）优先调度算法先来先服务和短作业（进程）优先调度算法 1.fcfs1.fcfs特点：简单，有利于长作业特点：简单，有利于长作业, ,即即cpucpu繁忙性作业繁忙性作业; ;不不利于短作业。利于短作业。2.2.短作业进程优先调度算法：短作业进程优先调度算法：sj(p)fsj(p

18、)f提高了平均周转时间和平均带权周转时间（从而提提高了平均周转时间和平均带权周转时间（从而提高了系统吞吐量）高了系统吞吐量）特点：特点：对长作业不利，有可能得不到服务（饥饿）对长作业不利，有可能得不到服务（饥饿）未考虑作业的紧迫程度，不能保证紧急作业被及时未考虑作业的紧迫程度，不能保证紧急作业被及时处理。处理。估计执行时间不易确定估计执行时间不易确定processes scheduling and deadlock april 2012 , caixia wang进程名进程名到达时间到达时间 服务时间服务时间 开始执行开始执行时间时间完成时间完成时间 周转时间周转时间=完成时间完成时间-到达时

19、到达时间间带权周转带权周转时间时间=周转时间周转时间/服务时服务时间间a01b1100c21d31000111110110011011021001001022021991.99processes scheduling and deadlock april 2012 , caixia wang 进程名进程名 a b c d e平均平均到达时间到达时间 0 1 2 3 4服务时间服务时间 4 3 5 2 4fcfs完成时间完成时间 周转时间周转时间 带权周转时间带权周转时间sjf完成时间完成时间 周转时间周转时间带权周转时间带权周转时间调度算法调度算法作业情况作业情况471214184610111

20、491225.5 3.52.8491861348163981 2.67 3.2 1.5 2.25 2.1processes scheduling and deadlock april 2012 , caixia wangv 1.1.优先权调度算法类型优先权调度算法类型 非抢占式优先权算法非抢占式优先权算法 抢占式优先权算法，实时性更好。抢占式优先权算法，实时性更好。v 2.2.优先权类型：优先权类型：1 1 静态优先权：静态优先权： 进程优先权在整个运行期不变。进程优先权在整个运行期不变。 确定优先权依据确定优先权依据（1 1）进程类型）进程类型（2 2）进程对资源的需求；）进程对资源的需求；

21、（3 3）根据用户需求。）根据用户需求。 特点：简单，但低优先权作业可能长期不被调度。特点：简单，但低优先权作业可能长期不被调度。processes scheduling and deadlock april 2012 , caixia wangv 2 2动态优先权：动态优先权： 如：优先权描述为如：优先权描述为可见：优先权随执行时间而下降，随等待时间可见：优先权随执行时间而下降，随等待时间而升高。而升高。 响应比响应比服务时间服务时间（等待时间服务时间）（等待时间服务时间）rp=服务时间服务时间（等待时间服务时间）（等待时间服务时间）优先权优先权=服务时间服务时间响应时间响应时间=proce

22、sses scheduling and deadlock april 2012 , caixia wang 优点：长短兼顾。优点：长短兼顾。 主要体现在以下几个方面：主要体现在以下几个方面： （1 1）如果作业的等待时间相同时，则要求服务的时间愈短，）如果作业的等待时间相同时，则要求服务的时间愈短，其优先权愈高，因而该算法有利于短作业。其优先权愈高，因而该算法有利于短作业。（2 2）当要求服务的时间相同时，作业的优先权决定于其等）当要求服务的时间相同时，作业的优先权决定于其等待时间，等待时间愈长，其优先权愈高，因而它实现的待时间，等待时间愈长，其优先权愈高，因而它实现的是先来先服务。是先来先服

23、务。（3 3）对于长作业，作业的优先级可以随等待时间的增加而）对于长作业，作业的优先级可以随等待时间的增加而提高，当其等待时间足够长时，其优先级便可升到很高，提高，当其等待时间足够长时，其优先级便可升到很高，从而也可获得处理机。从而也可获得处理机。 缺点：需计算缺点：需计算rprp，增加系统开销。，增加系统开销。服务时间服务时间（等待时间服务时间）（等待时间服务时间）rp=服务时间服务时间响应时间响应时间=processes scheduling and deadlock april 2012 , caixia wangv 1.1.时间片轮转时间片轮转 时间片大小的确定时间片大小的确定 太大（

24、每个进程都能在一个时间片内完成）：退化为太大（每个进程都能在一个时间片内完成）：退化为fcfsfcfs； 太小：有利于短作业，频繁地发生中断、进程上下文的太小：有利于短作业，频繁地发生中断、进程上下文的切换，系统开销过大切换，系统开销过大 系统对响应时间的要求；系统对响应时间的要求；t=nt=nq q 就绪队列中进程的数目；就绪队列中进程的数目； 系统的处理能力：（应保证一个时间片处理完常系统的处理能力：（应保证一个时间片处理完常用命令）用命令） 例题：见书例题：见书p95,p96p95,p96processes scheduling and deadlock april 2012 , cai

25、xia wangprocesses scheduling and deadlock april 2012 , caixia wang 进程名进程名 a b c d e平均平均到达时间到达时间 0 1 2 3 4服务时间服务时间 4 3 4 2 4rrq=1完成时间完成时间 周转时间周转时间 带权周转时间带权周转时间rrq=4完成时间完成时间 周转时间周转时间带权周转时间带权周转时间时间片时间片作业情况作业情况15121691715111461311.83.753.67 3.533.333.464711131746910138.4122.2553.33 2.5processes scheduli

26、ng and deadlock april 2012 , caixia wangv 2.2.多级反馈队列调度多级反馈队列调度调度实施过程：调度实施过程：（1 1）设置多个就绪队列，并为各个队列赋予不同的优先级。）设置多个就绪队列，并为各个队列赋予不同的优先级。在优先级愈高的队列中，为进程执行的时间片愈小。在优先级愈高的队列中，为进程执行的时间片愈小。就绪队列就绪队列1 1至至cpus1就绪队列就绪队列2 2s2至至cpu就绪队列就绪队列3 3s3至至cpu就绪队列就绪队列n nsn至至cpu时间片：时间片：s1s2s3processes scheduling and deadlock apri

27、l 2012 , caixia wang图图37 多级队列反馈调度算法多级队列反馈调度算法（2）当一个新进程进入内存后，首先将它放入第一队列）当一个新进程进入内存后，首先将它放入第一队列的末尾，按的末尾，按fcfs原则排队等待调度。当轮到该进程执行原则排队等待调度。当轮到该进程执行时，如它能在该时间片内完成，便可准备撤离系统，否则时，如它能在该时间片内完成，便可准备撤离系统，否则进入紧邻的后续队列。进入紧邻的后续队列。（3）仅当第一队列空闲时，调度程序才调度第二队列中）仅当第一队列空闲时，调度程序才调度第二队列中的进程运行；仅当第的进程运行；仅当第1-（i-1）队列均为空时）队列均为空时,才会

28、调度第才会调度第i队列中的进程运行。如果处理机正在第队列中的进程运行。如果处理机正在第i队列中为某进程队列中为某进程服务时，又有新进程进入优先级较高的队列，则此时新进服务时，又有新进程进入优先级较高的队列，则此时新进程将抢占正在运行进程的处理机。程将抢占正在运行进程的处理机。特点：长、短作业兼顾，有较好的响应时间特点：长、短作业兼顾，有较好的响应时间（1）短作业一次完成；）短作业一次完成；（2）中型作业周转时间不长；）中型作业周转时间不长；（3）大型作业不会长期不处理。）大型作业不会长期不处理。processes scheduling and deadlock april 2012 , cai

29、xia wangv 1、周转时间、带权周转时间、周转时间、带权周转时间v 2、fcfs：对短作业不公平：对短作业不公平v 3、短作业：长作业饥饿、短作业：长作业饥饿v 4、高优先权：低优先权的可能长期不调度。、高优先权：低优先权的可能长期不调度。v 5、高响应比：须计算相应比，增加开销。、高响应比：须计算相应比，增加开销。v 6、时间片轮转：时间片长短不易确定。太长等同于、时间片轮转：时间片长短不易确定。太长等同于fcfs，太短频繁中断，增加开销。太短频繁中断，增加开销。v 7、多级反馈：最好的调度算法。按不同的优先级设在不同、多级反馈：最好的调度算法。按不同的优先级设在不同的就绪队列。同一队

30、列按的就绪队列。同一队列按fcfs调度。不同队列按优先级高调度。不同队列按优先级高低进行调度。优先级高的时间片设置短些。低进行调度。优先级高的时间片设置短些。processes scheduling and deadlock april 2012 , caixia wangv .1实现实时调度的基本条件实现实时调度的基本条件1 1 提供必要的调度信息提供必要的调度信息 （1 1）就绪时间；）就绪时间； （2 2）开始）开始/ /完成截止时间；完成截止时间； （3 3）处理时间；）处理时间； （4 4）资源要求；）资源要求； （5 5）优先级；）优先级；2 2系统处理能力强系统处

31、理能力强npcpcmiiimiii111ci为处理时间，为处理时间，pi为周期时间（基于周期性实时任务）为周期时间（基于周期性实时任务）processes scheduling and deadlock april 2012 , caixia wang例例: :如果一个单处理器实时系统中有如果一个单处理器实时系统中有3 3个周期性任务，个周期性任务，它们的周期分别为它们的周期分别为80ms80ms、40ms40ms和和240ms240ms，需要，需要cpucpu处理处理的时间分别为的时间分别为20ms20ms、10ms10ms和和40ms40ms，问该实时系统，问该实时系统能否调度这能否调度这

32、3 3个周期性任务？个周期性任务？所以，该系统可调度这所以，该系统可调度这3 3个周期性实时任务。个周期性实时任务。但是，如果这但是，如果这3 3个周期性实时任务需要处理器处理个周期性实时任务需要处理器处理的时间分别变为的时间分别变为30ms30ms、20ms20ms和和60ms60ms时，则：时，则：12404060602404040108020pcm1iii124060120902406040208030pcm1iii系统不能调度这系统不能调度这3 3个周期性实时任务。个周期性实时任务。processes scheduling and deadlock april 2012 , caixi

33、a wang如果将该单处理器系统变为具有两个处理器的系统，如果将该单处理器系统变为具有两个处理器的系统，则：则：则双处理器系统可以调度这则双处理器系统可以调度这3 3个周期性实时任务。个周期性实时任务。224027024060120902406040208030pcm1iiiprocesses scheduling and deadlock april 2012 , caixia wangv .1实现实时调度的基本条件实现实时调度的基本条件.3 3.采用抢占调度方式采用抢占调度方式 剥夺方式：一般都采用此剥夺方式：一般都采用此 非剥夺方式（实现简单）：一般应使实时任务较小，非剥

34、夺方式（实现简单）：一般应使实时任务较小，以及时放弃以及时放弃cpucpu。.4 4.具有快速切换机制具有快速切换机制 具有快速响应外部中断能力。具有快速响应外部中断能力。 快速任务分派能力快速任务分派能力processes scheduling and deadlock april 2012 , caixia wangv 1.1.非抢占式调度算法非抢占式调度算法 时间片轮转时间片轮转 秒级秒级 非抢占优先权（协同）非抢占优先权（协同） 秒秒-毫秒级毫秒级v 2.2.抢占式调度算法抢占式调度算法 时钟中断抢占优先权时钟中断抢占优先权 毫秒级毫秒级 基于抢占点抢占基于抢占点抢占 立即抢占立即抢占

35、immediate preemption immediate preemption 毫秒毫秒-微秒级微秒级 只要不在临界区即抢占（中断引发）只要不在临界区即抢占（中断引发）进程1进程2进程n实时进程调度时间调度时间实时进程要求调度实时进程要求调度调度实时进程运行调度实时进程运行a 非抢占轮转调度非抢占轮转调度当前进程实时进程实时进程要求调度实时进程要求调度当前进程运行完成当前进程运行完成b 非抢占优先权调度非抢占优先权调度调度时间调度时间c 基于时钟中断抢占的优先权抢占调度基于时钟中断抢占的优先权抢占调度当前进程实时进程实时进程要求调度实时进程要求调度抢占时刻（其它中断）抢占时刻（其它中断）d

36、 立即抢占优先权调度立即抢占优先权调度当前进程实时进程实时进程要求调度实时进程要求调度时钟中断到达时时钟中断到达时调度时间调度时间调度时间调度时间processes scheduling and deadlock april 2012 , caixia wangv 1.1.最早截止时间优先最早截止时间优先edfedf（earliest deadline first)earliest deadline first)算算法法 根据任务的截止时间来确定任务的优先级根据任务的截止时间来确定任务的优先级 截止时间越早，优先级越高截止时间越早，优先级越高 可以是抢占式或非抢占式可以是抢占式或非抢占式pro

37、cesses scheduling and deadlock april 2012 , caixia wang1342134212 34t开始截止时间开始截止时间任务到达任务到达任务执行任务执行图图39 edf算法用于算法用于非抢占非抢占调度方式调度方式1)非抢占非抢占调度方式用于非周期实时任务调度方式用于非周期实时任务processes scheduling and deadlock april 2012 , caixia wang2) 抢占抢占调度方式用于周期实时任务调度方式用于周期实时任务a的周期时间是的周期时间是20ms，每个周期的处理时间是，每个周期的处理时间是10ms; b的周期时

38、间是的周期时间是50ms，每个周期的处理时间是，每个周期的处理时间是25ms; a的到达时间为的到达时间为0，20，40， 最后期限为最后期限为20，40，60， b的到达时间为的到达时间为0，50，100， 最后期限为最后期限为50，100，150，具体执行情况将教材具体执行情况将教材p101图图3-10。processes scheduling and deadlock april 2012 , caixia wangprocesses scheduling and deadlock april 2012 , caixia wangv 松弛度：截止时间松弛度：截止时间- -运行时间运行时间

39、- -当前时间当前时间 若若a a进程需在进程需在200ms200ms时完成，其本身运行需要时完成，其本身运行需要100ms100ms，当，当前时刻是前时刻是10ms10ms，则，则a a的松弛度为：的松弛度为：20020010010010109090 主要用于可抢占的调度方式中主要用于可抢占的调度方式中 例：例：a1a2a3a4a5a6a7a8b1b2b3020406080 100120 140160t图图311 a/b任务每次必须完成的时间任务每次必须完成的时间processes scheduling and deadlock april 2012 , caixia wanga1(10)a

40、2(10)a3(10)a4(10)t01020304050607080t1=0b1(20)b1(5)b2(15)b2(10)t1t2t3t4t5t6t7t8图图312 利用利用llf算法进行调度的情况算法进行调度的情况注意：当一个任务结束注意：当一个任务结束或者有任务的松弛度为或者有任务的松弛度为0时时才进行比较才进行比较processes scheduling and deadlock april 2012 , caixia wangv .1产生死锁的原因产生死锁的原因 a a、竞争资源、竞争资源 b b、进程间推进顺序非法、进程间推进顺序非法v 一、竞争资源引起死锁。一、竞

41、争资源引起死锁。1 1 可剥夺（可剥夺（cpucpu、内存，）和非剥夺性（打印机，磁、内存，）和非剥夺性（打印机，磁带机）资源带机）资源2 2 竞争非剥夺性资源竞争非剥夺性资源可造成死锁可造成死锁 p1p2r1r2processes scheduling and deadlock april 2012 , caixia wangv 3 3竞争临时性资源竞争临时性资源 临时性资源是指由一个进程产生，被另一个进程使用临时性资源是指由一个进程产生，被另一个进程使用一段时间后便无用的资源。一段时间后便无用的资源。 如如s1,s2,s3s1,s2,s3为临时性资源。为临时性资源。p1p3s3s1s2p2

42、p1:release(s1);request(s3);p2:release(s2);request(s1);p3:release(s3);request(s2);p1: request(s3);release(s1);p2: request(s1);release(s2);p3: request(s2);release(s3);processes scheduling and deadlock april 2012 , caixia wang例如：进程例如：进程p1,p2并发执行，推进顺序如下：并发执行，推进顺序如下：vp1: request(r1);request(r2);vp1: rele

43、ase(r1);release(r2);vp2: request(r2); request(r1);vp2: release(r2); release(r1);processes scheduling and deadlock april 2012 , caixia wang213dp2req(r2)p2req(r1)p1req(r1) p1req(r2)p2rel(r2)p2rel(r1)p1rel(r1) p1rel(r2)4processes scheduling and deadlock april 2012 , caixia wangv 1 1互斥条件（资源的临界性）互斥条件（资源的

44、临界性）v 2 2请求和保持条件请求和保持条件v 3 3不剥夺条件不剥夺条件v 4 4环路等待环路等待v 只要同时具备上述只要同时具备上述4 4个个必要条件必要条件，系统就会，系统就会发生发生死锁死锁，只要上述条件之一不满足，系，只要上述条件之一不满足，系统就不会发生统就不会发生死锁死锁。 processes scheduling and deadlock april 2012 , caixia wangv 1 1预防；破坏预防；破坏4 4个条件之一：有效，使资源个条件之一：有效，使资源利用率低。利用率低。v 2 2避免：防止进入不安全态。避免：防止进入不安全态。v 3 3检测：检测到死锁再清

45、除。检测：检测到死锁再清除。v 4 4解除：与解除：与“检检”配套。配套。processes scheduling and deadlock april 2012 , caixia wangv 3.6.1 3.6.1 死锁预防死锁预防 一、互斥条件是资源固有属性，不能避免一、互斥条件是资源固有属性，不能避免? ? 二、摒弃请求和保持条件二、摒弃请求和保持条件全分配，全释放（全分配，全释放（andand）缺点：（缺点：（1 1）延迟进程运行）延迟进程运行（2 2）资源严重浪费）资源严重浪费 三、摒弃三、摒弃“不剥夺不剥夺”条件条件增加系统开销，且进程前段工作可能失效。增加系统开销，且进程前段工作

46、可能失效。processes scheduling and deadlock april 2012 , caixia wangprocesses scheduling and deadlock april 2012 , caixia wangv 3.6.1 3.6.1 死锁预防死锁预防 四、摒弃四、摒弃“环路环路”条件条件有序资源分配法：为资源编号，申请时需按编号进有序资源分配法：为资源编号，申请时需按编号进行。行。缺点：缺点：（1 1）新增资源不便，（原序号已排定）新增资源不便，（原序号已排定）（2 2）用户不自由）用户不自由（3 3）资源与进程使用顺序不同造成浪费）资源与进程使用顺序不同造

47、成浪费processes scheduling and deadlock april 2012 , caixia wangv在在“避免死锁避免死锁”方法中的判断条件方法中的判断条件 v1. 1. 安全状态安全状态按某种顺序并发进程都能达到获得最大资源而顺序按某种顺序并发进程都能达到获得最大资源而顺序完成的序列为安全序列。完成的序列为安全序列。能找到安全序列的状态为安全状态。能找到安全序列的状态为安全状态。processes scheduling and deadlock april 2012 , caixia wangv2.2.安全状态例安全状态例: :共有共有1212台磁带机，分配情况如下表

48、。台磁带机，分配情况如下表。进程进程最大需求最大需求已分配已分配可用可用p11053p242p392安全序列：安全序列：p2p2p1p1p3 p3 processes scheduling and deadlock april 2012 , caixia wangv3 3 安全安全不安全的转换不安全的转换 上例中，若上例中，若p3p3再申请一台，则不安全再申请一台，则不安全 进程进程最大需求最大需求已分配已分配可用可用p11052p242p393processes scheduling and deadlock april 2012 , caixia wangv 1 1数据结构数据结构 ava

49、ilablej=k: availablej=k: 系统现有系统现有rjrj类资源类资源k k个；个； maxi,j=k: maxi,j=k: 进程进程i i需要需要rjrj的最大数的最大数k k个；个； allocationi,j=k: allocationi,j=k: 进程进程i i已得到已得到rjrj类资源类资源k k个；个； needi,j=k:needi,j=k: 进程进程i i还需要还需要rjrj类资源类资源k k个个 有：有：needi,j= maxi,jneedi,j= maxi,jallocationi,jallocationi,j requestrequesti ij=k:j

50、=k:进程进程i i请求请求k k个个rjrj类资源类资源 workiworki：进程：进程i i执行完后系统应有资源数（也即可用数）执行完后系统应有资源数（也即可用数） finishifinishi：布尔量，表进程：布尔量，表进程i i能否顺序完成。能否顺序完成。 processes scheduling and deadlock april 2012 , caixia wangv 2 2银行家算法银行家算法 reqi=needierrorreqi=availiblockftftprocesses scheduling and deadlock april 2012 , caixia wan

51、gavail=avail-reqialloci=alloci+reqineedi=needi-reqifinishi=.f.neediprocesses scheduling and deadlock april 2012 , caixia wangwork a b cneed a b c alloc a b cwork+alloc a b c finish p1 p3 p4 p2 p0 t0时刻的安全序列时刻的安全序列3 3 21 2 22 0 05 3 2true5 3 20 1 12 1 17 4 3true7 4 34 3 10 0 27 4 57 4 56 0 03 0 210 4

52、710 4 77 4 30 1 010 5 7truetruetrueprocesses scheduling and deadlock april 2012 , caixia wangwork a b cneed a b c alloc a b cwork+alloc a b c finish p1 p3 p4 p0 p2 p1申请资源申请资源(1,0,2)时安全性检查时安全性检查(安全安全)2 3 00 2 03 0 25 3 25 3 20 1 12 1 17 4 37 4 34 3 10 0 27 4 57 4 57 4 30 1 07 5 57 5 56 0 03 0 210 5 7

53、truetruetruetruetrueprocesses scheduling and deadlock april 2012 , caixia wang allocation a b c need a b c available a b c p0 p1 p2 p3 p4 为为p0分配（分配（0，2，0）后的情况（不安全）后的情况（不安全）0 3 07 2 33 0 20 2 03 0 26 0 02 1 10 1 10 0 24 3 12 1 0processes scheduling and deadlock april 2012 , caixia wang3.7.1 3.7.1 死锁的

54、检测死锁的检测 当系统为进程分配资源时，若没有采取任何限制性当系统为进程分配资源时，若没有采取任何限制性的措施，则系统必须提供检测和解除死锁的手段，为此，的措施，则系统必须提供检测和解除死锁的手段，为此，系统必须：系统必须：（1 1）保存有关资源的请求和分配信息）保存有关资源的请求和分配信息（2 2）提供一种算法，以利用这些信息来监测系统是否进入）提供一种算法，以利用这些信息来监测系统是否进入死锁状态死锁状态3.7 死锁的检测与解除死锁的检测与解除processes scheduling and deadlock april 2012 , caixia wang1. 资源分配图资源分配图(resource allocation graph) 该图是由一组节点该图是由一组节点n和一组边和一组边e所组成的一个对偶所组成的一个对偶g=(n,e),它它具有下述形式的定义和限制：具有下述形式的定义和限制：(1) 把节点把节点n分成两个互斥的子集，即一组进程节点分成两个互斥的子集，即一组进程节点p和一组和一组资源节点资源节点r, n=p u r。例如右图。例如右图 p=p1,p2,r=r1,r2