第三章 处理机调度与死锁

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.83.8 死锁的检测与解除死锁的检测与解除 CPUCPU是计算机系统中的一个十分重要的资是计算机系统中的一个十分重要的资源，对它进行高效的调度是操作系统设计的源，对它进行高效的调度是操作系统设计的中心问题之一。中心问题之一。 对于大型系统运行时的性能，如系统吞对于大型系统运行时的性能，如系统吞吐量、资源

2、利用率、作业周转时间或响应的吐量、资源利用率、作业周转时间或响应的及时性等在很大程度上都取决于处理机调度及时性等在很大程度上都取决于处理机调度性能的好坏。因而，处理机调度便成为性能的好坏。因而，处理机调度便成为OSOS中中至关重要的部分。至关重要的部分。 （作业调度、长程调度、接纳调度）（作业调度、长程调度、接纳调度）1 1、作业和作业步、作业和作业步作业：包含程序、数据和作业说明书作业：包含程序、数据和作业说明书。作业步：作业执行过程中的每一个加工步骤：编译、链接装配、作业步：作业执行过程中的每一个加工步骤：编译、链接装配、 运行运行作业流：作业进入系统，依次存于外存形成作业流作业流：作业进

3、入系统，依次存于外存形成作业流2 2、作业控制块（、作业控制块（JCBJCB）n它是作业在系统中存在的标志，其中保存了系统它是作业在系统中存在的标志，其中保存了系统 对作业进行管理和调度所需的全部信息。对作业进行管理和调度所需的全部信息。n内容：内容：n作业标识，用户名，作业类型，作业状态，调度信息等作业标识，用户名，作业类型，作业状态，调度信息等n进入系统进入系统 建立建立JCB-JCB-插入相应作业后备队列插入相应作业后备队列-作业作业调度调度-作业控制作业控制 作业结束作业结束 回收资源回收资源用户作业录入提交收容完成运行就绪等待作业调度执行作业调度 批处理系统中作业处理及状态批处理系统

4、中作业处理及状态3 3、作业调度、作业调度n将外存作业调入内存，创建将外存作业调入内存，创建PCBPCB等，插入就绪队等，插入就绪队列。列。n一般用于批处理系统，分一般用于批处理系统，分/ /实时系统一般直接入实时系统一般直接入内存，无此环节内存，无此环节。n调度特性调度特性n接纳作业数（内存驻留数，多道程序度）接纳作业数（内存驻留数，多道程序度）太多太多 周转时间周转时间T T长长太少太少 系统效率低系统效率低n接纳策略：即采用何种调度算法：接纳策略：即采用何种调度算法：FCFSFCFS、短作业、短作业优先等优先等（进程调度，短程调度）（进程调度，短程调度）主要是决定就绪队列中的哪个进程应获

5、得处理机，主要是决定就绪队列中的哪个进程应获得处理机，然后由分派程序（然后由分派程序（DispatcherDispatcher）分派处理机。）分派处理机。1.1.低级调度的功能：低级调度的功能：n保存处理机现场信息保存处理机现场信息n按某种算法选取进程按某种算法选取进程n把处理机分配给进程把处理机分配给进程2.2.进程调度的三个进步机制进程调度的三个进步机制n排队器排队器n分派器分派器n上下文切换机制：两对切换上下文切换机制：两对切换3.3.进程调度方式：进程调度方式：1)1)非抢占方式：非抢占方式：简单、系统开销小，实时性差简单、系统开销小，实时性差 ( (如如win31)win31)2)2

6、)抢占方式抢占方式（1 1）优先权原则）优先权原则（2 2）短进程优先原则）短进程优先原则（3 3）时间片原则）时间片原则n引起进程调度的因素有哪些引起进程调度的因素有哪些？n进程正常终止或异常终止进程正常终止或异常终止n进程因某种原因阻塞：进程因某种原因阻塞：I/OI/O请求；请求；waitwait操作等操作等n时间片用完时间片用完n抢占方式下，就绪队列中某进程的优先权比当前执行抢占方式下，就绪队列中某进程的优先权比当前执行的进程高的进程高运行频率运行频率n低低 中中 高高。1.1.仅有进程调度的队列模型仅有进程调度的队列模型就绪队列就绪队列CPU阻塞队列阻塞队列交互用户交互用户时间片完时间

7、片完进程调度进程调度进程完成进程完成等待事件等待事件事件出现事件出现图 2-5 进程的三种基本状态及其转换 就绪阻塞执行时间片完进程调度I/O完成I/O请求2.2.具有高、低级调度的队列模型具有高、低级调度的队列模型就绪队列就绪队列CPU阻塞队列阻塞队列时间片完时间片完进程调度进程调度进程进程完成完成等待事件等待事件1事件事件1出现出现后备队列后备队列阻塞队列阻塞队列等待事件等待事件2事件事件2出现出现作业调度作业调度图 2-6 具有挂起状态的进程状态图 活动就绪静止就绪执行挂起激活释放挂起活动阻塞静止阻塞挂起激活释放请求I/O就绪队列就绪队列CPU就绪、挂起队列就绪、挂起队列时间片完时间片完

8、进程调度进程调度进程进程完成完成后备队列后备队列阻塞、挂起队列阻塞、挂起队列事件出现事件出现作业调度作业调度阻塞队列阻塞队列等待事件等待事件挂起挂起事件出现事件出现中级调度中级调度交互型作业交互型作业 1 1、面向用户的目标、面向用户的目标（1 1）周转时间短（常用于批处理系统）周转时间短（常用于批处理系统）概念：作业从提交概念：作业从提交 完成的时间。完成的时间。分为：分为：n驻外存等待调度时间驻外存等待调度时间n驻内存等待调度时间驻内存等待调度时间n执行时间执行时间n阻塞时间阻塞时间1 1、面向用户的目标、面向用户的目标n平均周转时间平均周转时间n平均带权平均带权 n可见带权可见带权w w

9、越小越好越小越好,Ts,Ts为实际服务时间。为实际服务时间。11niiTnT11niisiTWnT1 1、面向用户的目标、面向用户的目标（2 2）响应时间快：（对交互性作业、分时系统）响应时间快：（对交互性作业、分时系统）概念：键盘提交请求到首次响应时间概念：键盘提交请求到首次响应时间n输入传送时间输入传送时间n处理时间处理时间n响应传送时间响应传送时间（3 3）截止时间的保证（特别是实时系统）截止时间的保证（特别是实时系统）（4 4）优先权准则：（即需要抢占调度）优先权准则：（即需要抢占调度）2 2、面向系统的准则、面向系统的准则（1 1）吞吐量高（特别是批处理）：单位时）吞吐量高（特别是批

10、处理）：单位时间完成作业数间完成作业数（2 2）处理机利用率好：（因）处理机利用率好：（因CPUCPU贵，特别贵，特别是大中型多用户系统）是大中型多用户系统）（3 3）各类资源的平衡利用。）各类资源的平衡利用。（4 4）策略强制执行。）策略强制执行。 处理机调度算法处理机调度算法3.3.13.3.1先来先服务和短作业（进程）优先调度算法先来先服务和短作业（进程）优先调度算法1.1.先来先服务调度算法（先来先服务调度算法（FCFSFCFS）n特点：简单，有利于长作业（进程）特点：简单，有利于长作业（进程） 即即CPUCPU繁忙繁忙性作业性作业, ,不利于短作业（进程）不利于短作业（进程）2.2.

11、短作业（进程）优先调度算法：短作业（进程）优先调度算法：SJ(P)FSJ(P)Fn提高了平均周转时间和平均带权周转时间（从而提高了平均周转时间和平均带权周转时间（从而提高了系统吞吐量）提高了系统吞吐量）n特点：对长作业不利，有可能得不到服务特点：对长作业不利，有可能得不到服务n估计时间不易确定估计时间不易确定 先来先服务算法实例先来先服务算法实例图图3-4 FCFS3-4 FCFS和和SJ(P)FSJ(P)F比较比较1.1.优先权调度算法类型优先权调度算法类型n非抢占式优先权算法非抢占式优先权算法n抢占式优先权算法，实时性更好。抢占式优先权算法，实时性更好。1) 非抢占式优先权算法 在这种方式

12、下，系统一旦把处理机分配给就绪队列中优先权最高的进程后，该进程便一直执行下去，直至完成； 或因发生某事件使该进程放弃处理机时，系统方可再将处理机重新分配给另一优先权最高的进程。这种调度算法主要用于批处理系统中；也可用于某些对实时性要求不严的实时系统中。 2) 抢占式优先权调度算法 在这种方式下，系统同样是把处理机分配给优先权最高的进程，使之执行。但在其执行期间，只要又出现了另一个其优先权更高的进程，进程调度程序就立即停止当前进程(原优先权最高的进程)的执行，重新将处理机分配给新到的优先权最高的进程。因此，在采用这种调度算法时，是每当系统中出现一个新的就绪进程i时，就将其优先权Pi与正在执行的进

13、程j的优先权Pj进行比较。如果PiPj，原进程Pj便继续执行；但如果是PiPj, 则立即停止Pj的执行，做进程切换，使i进程投入执行。显然，这种抢占式的优先权调度算法，能更好地满足紧迫作业的要求，故而常用于要求比较严格的实时系统中， 以及对性能要求较高的批处理和分时系统中。 2.2.优先权类型：优先权类型：1 1）静态优先权：）静态优先权： 静态优先权是在创建进程时确定的，且在进程的整个运行期间保持不变。一般地，优先权是利用某一范围内的一个整数来表示的，例如，07或0255中的某一整数， 又把该整数称为优先数。只是具体用法各异：有的系统用“0”表示最高优先权，当数值愈大时，其优先权愈低；而有的

14、系统恰恰相反。 n进程优先权在整个运行期不变。进程优先权在整个运行期不变。n确定优先权依据确定优先权依据n进程类型进程类型n进程对资源的需求；进程对资源的需求；n根据用户需求。根据用户需求。n特点：简单，但低优先权作业可能长期不被调度特点：简单，但低优先权作业可能长期不被调度（饥饿）。（饥饿）。 2) 动态优先权 动态优先权是指，在创建进程时所赋予的优先权，是可以随进程的推进或随其等待时间的增加而改变的，以便获得更好的调度性能。例如，我们可以规定，在就绪队列中的进程，随其等待时间的增长，其优先权以速率a提高。若所有的进程都具有相同的优先权初值，则显然是最先进入就绪队列的进程，将因其动态优先权变

15、得最高而优先获得处理机，此即FCFS算法。若所有的就绪进程具有各不相同的优先权初值，那么，对于优先权初值低的进程，在等待了足够的时间后，其优先权便可能升为最高，从而可以获得处理机。当采用抢占式优先权调度算法时，如果再规定当前进程的优先权以速率b下降，则可防止一个长作业长期地垄断处理机。 3. 高响应比优先调度算法高响应比优先调度算法 要求服务时间要求服务时间等待时间优先权优先权的变化规律可描述为： 由于等待时间与服务时间之和，就是系统对该作业的响应时间，故该优先权又相当于响应比RP。据此，又可表示为： 要求服务时间响应时间要求服务时间要求服务时间等待时间优先权3.3.高响应比优先调度算法：高响

16、应比优先调度算法：n响应比响应比RpRp= =（Tw+TsTw+Ts）/Ts/Tsn特点：特点：n（1 1）短作业）短作业R RP P大。大。n（2 2）TsTs（要求服务时间）相同的进程间相当于（要求服务时间）相同的进程间相当于FCFSFCFS。n（3 3）长作业等待一段时间仍能得到服务。）长作业等待一段时间仍能得到服务。l 先来先服务算法（先来先服务算法（FCFSFCFS：First Come First ServeFirst Come First Serve）l 最短作业优先算法（最短作业优先算法（SJFSJF：Shortest Job FirstShortest Job First）l

17、 最短剩余时间优先（最短剩余时间优先（SRTF: Shortest Remaining SRTF: Shortest Remaining Time FirstTime First）l 最高响应比优先算法（最高响应比优先算法（HRRFHRRF：Highest Response Highest Response Ratio FirstRatio First）响应比响应比 R R = 响应时间/要求服务时间 =（等待时间+要求服务时间）/要求服务时间 = 1 +（等待时间/要求服务时间）l基于优先数调度算法基于优先数调度算法（HPF：Highest Priority First）（a）由用户规定优先

18、数（外部优先数）用户提交作业时，根据急迫程度规定适当的优先数，作业调度程序根据JCB优先数决定进入内存的次序。（b）由系统计算优先数（内部优先数）例：可按如下公式计算作业的优先数：优先数= 用户规定优先数作业处理时间+ 作业等待时间输出量3.2.3 基于时间片的轮转调度算法基于时间片的轮转调度算法 1. 时间片轮转法时间片轮转法 在早期的时间片轮转法中，系统将所有的就绪进程按先来先服务的原则，排成一个队列，每次调度时，把CPU分配给队首进程，并令其执行一个时间片。时间片的大小从几ms到几百ms。当执行的时间片用完时，由一个计时器发出时钟中断请求，调度程序便据此信号来停止该进程的执行，并将它送往

19、就绪队列的末尾；然后，再把处理机分配给就绪队列中新的队首进程，同时也让它执行一个时间片。这样就可以保证就绪队列中的所有进程，在一给定的时间内，均能获得一时间片的处理机执行时间。1.1.时间片轮转时间片轮转n时间片大小的确定时间片大小的确定n太大：退化为太大：退化为FCFSFCFS；n太小：系统开销过大太小：系统开销过大n系统对响应时间的要求；系统对响应时间的要求；T=T=nqnqn就绪队列中进程的数目；就绪队列中进程的数目；n系统的处理能力：（应保证一个时间片处系统的处理能力：（应保证一个时间片处理完常用命令）理完常用命令）2. 多级反馈队列调度算法多级反馈队列调度算法 (1) 应设置多个就绪

20、队列，并为各个队列赋予不同的优先级。 第一个队列的优先级最高，第二个队列次之，其余各队列的优先权逐个降低。该算法赋予各个队列中进程执行时间片的大小也各不相同，在优先权愈高的队列中，为每个进程所规定的执行时间片就愈小。例如，第二个队列的时间片要比第一个队列的时间片长一倍，第i+1个队列的时间片要比第i个队列的时间片长一倍。 图 3-5 是多级反馈队列算法的示意。 就绪队列就绪队列1 1至至CPUS1就绪队列就绪队列2 2S2至至CPU就绪队列就绪队列3 3S3至至CPU就绪队列就绪队列n nSn至至CPU时间片：时间片：S1S2S3图图35多级队列反馈调度算法多级队列反馈调度算法 (2) 当一个

21、新进程进入内存后，首先将它放入第一队列的末尾，按FCFS原则排队等待调度。当轮到该进程执行时，如它能在该时间片内完成，便可准备撤离系统；如果它在一个时间片结束时尚未完成，调度程序便将该进程转入第二队列的末尾，再同样地按FCFS原则等待调度执行；如果它在第二队列中运行一个时间片后仍未完成，再依次将它放入第三队列，如此下去，当一个长作业(进程)从第一队列依次降到第n队列后，在第n队列中便采取按时间片轮转的方式运行。 (3) 仅当第一队列空闲时，调度程序才调度第二队列中的进程运行； 仅当第1(i-1) 队列均空时，才会调度第i队列中的进程运行。如果处理机正在第i队列中为某进程服务时，又有新进程进入优

22、先权较高的队列(第1(i-1)中的任何一个队列)，则此时新进程将抢占正在运行进程的处理机，即由调度程序把正在运行的进程放回到第i队列的末尾，把处理机分配给新到的高优先权进程。 2.2.多级反馈队列调度多级反馈队列调度n特点：长、短作业兼顾，有较好的响应时特点：长、短作业兼顾，有较好的响应时间间n短作业一次完成；短作业一次完成；n中型作业周转时间不长；中型作业周转时间不长；n大型作业不会长期不处理。大型作业不会长期不处理。作业调度与进程调度作业调度与进程调度有一个具有两道作业的批处理系统，作业调度采用短作业优先的调度算法，进程调度采用以优先数为基础的抢占式调度算法。如下表所示(作业的优先数即为进

23、程的优先数，优先数越小越好)。（1）列出所有作业进入内存时刻及结束时刻？（2）计算平均周转时间？作业名作业名 到达时间到达时间 估计运行时间估计运行时间优先数优先数A10:00405B10:20303C10:30504D10:50206解：（1）作业A、B、C、D进入内存时刻分别为：10:00、10:20、11:10、10:50。它们的结束时刻为：11:10、10:50、12:00、12:20。（2） 作业A、B、C、D的周转时间分别为70，30，90，90分钟，平均周转时间为70分钟。ABCD3 3.3.1.3.1实现实时调度的基本条件实现实时调度的基本条件1 1提供必要的调度信息提供必要的

24、调度信息（1 1）就绪时间；）就绪时间；（2 2）开始）开始/ /完成截止时间；完成截止时间；（3 3）处理时间；）处理时间；（4 4）资源要求；）资源要求；（5 5）优先级；）优先级；2 2系统处理能力强系统处理能力强NPCPCmiiimiii111Ci为处理时间，为处理时间，Pi为周期时间（基于周期性实时任务）为周期时间（基于周期性实时任务）3 3.3.1.3.1实现实时调度的基本条件实现实时调度的基本条件3.3.采用抢占调度方式采用抢占调度方式n剥夺方式：一般都采用此方式剥夺方式：一般都采用此方式n非剥夺方式（实现简单）：一般应使实时任务非剥夺方式（实现简单）：一般应使实时任务较小，以及

25、时放弃较小，以及时放弃CPUCPU。4.4.具有快速切换机制具有快速切换机制n具有快速响应外部中断能力。具有快速响应外部中断能力。n快速任务分派快速任务分派1.1.非抢占式调度算法非抢占式调度算法n时间片轮转时间片轮转 秒级秒级n非抢占优先权（协同）非抢占优先权（协同） 秒秒- -毫秒级毫秒级2.2.抢占式调度算法抢占式调度算法n时钟中断抢占优先权时钟中断抢占优先权 毫秒级毫秒级n基于抢占点抢占基于抢占点抢占n立即抢占立即抢占immediate preemption immediate preemption 毫秒毫秒- -微秒级微秒级n只要不在临界区即抢占（中断引发）只要不在临界区即抢占（中断

26、引发）进程1进程2进程n实时进程调度时间调度时间实时进程请求调度实时进程请求调度调度实时进程运行调度实时进程运行a 非抢占式轮转调度非抢占式轮转调度当前进程实时进程实时进程请求调度实时进程请求调度当前进程运行完成当前进程运行完成b 非抢占式优先权调度非抢占式优先权调度调度时间调度时间c 基于时钟中断抢占的优先权调度基于时钟中断抢占的优先权调度当前进程实时进程实时进程请求调度实时进程请求调度实时进程抢占当前实时进程抢占当前进程，并立即执行进程，并立即执行d 立即抢占的优先权调度立即抢占的优先权调度当前进程实时进程实时进程请求调度实时进程请求调度时钟中断到来时时钟中断到来时调度时间调度时间调度时间

27、调度时间1.1.最早截止时间优先最早截止时间优先EDFEDF（earliest deadline earliest deadline first)first)算法算法n根据任务的截止时间来确定任务的优先级根据任务的截止时间来确定任务的优先级n截止时间越早，优先级越高截止时间越早，优先级越高n可以是抢占式或非抢占式可以是抢占式或非抢占式最早截止时间优先EDF例1342134212 34t开始截止时间开始截止时间任务到达任务到达任务执行任务执行图图37 EDF算法用于非抢占调度方式算法用于非抢占调度方式2 2. . 最低松弛度优先最低松弛度优先LLFLLF算法算法n松弛度：松弛度：n根据任务紧急（

28、或松弛）的程度，来确定任务的优先级。根据任务紧急（或松弛）的程度，来确定任务的优先级。任务的紧急程度越高，该任务的优先级就越高，使之优任务的紧急程度越高，该任务的优先级就越高，使之优先执行。先执行。n若若A A进程进程需在需在200ms200ms时完成，其本身运行需要时完成，其本身运行需要100ms100ms，当，当前时刻是前时刻是10ms10ms，则，则A A的松弛度为：的松弛度为：20020010010010109090n主要用于可抢占的调度方式中主要用于可抢占的调度方式中n例：见教材例：见教材P101-P102P101-P102例子例子 课堂反馈课堂反馈 进程调度算法进程调度算法对下表，

29、分别采用先来先服务（对下表，分别采用先来先服务（FCFS）、非抢）、非抢占及抢占的短进程优先（占及抢占的短进程优先（SPF）、高响应比优先）、高响应比优先（HRRF）、时间片轮转（）、时间片轮转（RR,时间片时间片q=1）、）、多级反馈队列（多级反馈队列（FB，第，第i级队列的时间片级队列的时间片=2i-1）调度算法进行调度算法进行CPU调度，求出各进程的执行情调度，求出各进程的执行情况以及平均周转时间和平均带权周转时间。况以及平均周转时间和平均带权周转时间。进程到达时间服务时间A03B26C44D65E82 FCFS 的调度性能 TW进程到达时间Tin服务时间Tr开始时间Ts 结束时间Tc周

30、转时间T带权周转时间WA0303TA=3WA=1B2639TB=7WB=1.17C44913TC=9WC=2.25D651318TD=12WD=2.40.E821820TE=12WE=6平均 =8.60 = 2.56同样，看到进程同样，看到进程E的不利情况。的不利情况。 先来先服务（先来先服务（FCFS） 短作业短作业/进程优先（进程优先（SJ(P)F） 降低对长进程有利的一种方法就是短进程优先策略： 表 SPF 的调度性能 WT进程到达时间Tin服务时间Tr开始时间Ts 结束时间Tc = =1.841.840 03 3111115159 93 39 9151520201111T TA A=3

31、=3T TB B=7=7T TC C=11=11T TD D=14=14T TE E=3=3= =7.607.608 83 36 64 45 52 22 20 04 46 6ABCDEW WE E=1.50=1.50W WA A=1=1W WB B=1.17=1.17W WC C=2.75=2.75W WD D=2.80=2.80E EC CD DA AB B周转时间周转时间T=T=结束时间结束时间T Tc c- -到达时间到达时间T Tinin=3-0=3=3-0=3周转时间周转时间 T T带权周转时间带权周转时间W W= =周转周转时间时间T/T/服务时间服务时间T Tr r=3/3=1=

32、3/3=1带权周转时带权周转时 间间W W平均平均结束结束下下一一步步下下一一步步下下一一步步下下一一步步下下一一步步下下一一步步下下一一步步 SJF对短作业有利，明显的作业E提前接受了服务，并且整体性能也得到了提高；SJF的问题： n SJF需要事先知道或至少需要估计每个作业所需估计每个作业所需的处理机时间的处理机时间。n 只要不断的有短作业进入系统，就有可能使长作业长期得不到运行而“饿死”。 n SJF 偏向短作业，不利于分时系统（由于不可抢占性）。 短作业短作业/进程优先（进程优先（SJF） 表 HRRN的调度性能 WT进程到达时间Tin服务时间Tr开始时间Ts 结束时间Tc =2=2.

33、14.140 03 39 9151513133 39 9131320201515T TA A=3=3T TB B=7=7T TC C=9=9T TD D=14=14T TE E=7=7= =8.008.008 83 36 64 45 52 22 20 04 46 6ABCDE W WE E=3.50=3.50W WA A=1=1W WB B=1.17=1.17W WC C=2.25=2.25W WD D=2.80=2.80E EC CD DA AB B周转时间周转时间T=T=结束时间结束时间T Tc c- -到达时间到达时间T Tinin=3-0=3=3-0=3周转时间周转时间 T T带权周转

34、时间带权周转时间W W= =周转周转时间时间T/T/服务时间服务时间T Tr r=3/3=1=3/3=1带权周转时带权周转时 间间W W平均平均=(9-4)+4/4=2.25=(9-6)+5/5=1.6=(9-8)+2/2=1.5RCRDRERD=(13-6)+5/5=2.4RE=(13-8)+2/2=3.5结束结束下下一一步步下下一一步步下下一一步步下下一一步步下下一一步步 最高响应比（最高响应比（HRRNHRRN）不同调度算法对的性能分析不同调度算法对的性能分析:W进程到达时间Tin服务时间Tr从平均周转时间及其平从平均周转时间及其平均带权周转时间来看，均带权周转时间来看，HRRN 刚好介

35、于刚好介于FCFS与与SPF之间，即好于之间，即好于FCFS，次于，次于SPF。 A A0 03B B2 26C C4 44D D6 65E E8 82FCFS8.602.56SPF7.601.84HRRN8.002.14TFCFSSPF(非抢占)SPF(抢占)HRRFRR(q=1)FB(q=2i-1)进程ABCDE平均FCFS完成时间周转时间带权周转时间331.0971.171392.2518122.420126.08.62.56SPF（非抢占）完成时间周转时间带权周转时间331.0971.1715112.7520142.81131.57.61.84SPF（抢占）完成时间周转时间带权周转时间

36、331.015132.16841.020142.81021.07.21.59HRRN完成时间周转时间带权周转时间331.0971.171392.2520142.81573.582.14RR（q=1 ）完成时间周转时间带权周转时间441.3318162.6717133.2520142.81573.510.82.71FB( q=2i-1)完成时间周转时间带权周转时间33117152.518143.520142.81463.010.42.56n在一个动态系统中，资源请求与释放是经常性发生的进程行为。对于每类系统资源，操作系统需要确定一个分配策略，资源分配策略可能是公平的(fair)；资源分配策略也可

37、能是不公平的(unfair)，即不能保证等待时间上界的存在。在后一种情况下，即使系统没有发生死锁，某些进程也可能会长时间等待。当等待时间给进程推进和响应带来明显影响时，称发生了进程饥饿(starvation)，当饥饿到一定程度的进程所赋予的任务即使完成也不再具有实际意义时称该进程被饿死(starve to death)。 n饿死与死锁有一定联系：二者都是由于竞争资源而引起的，但又有明显差别，主要表现在如下几个方面：n(1) 死锁进程等待永远不会被释放的资源，饿死进程等待会被释放但却不会分配给自己的资源，表现为等待时限没有上界(排队等待或忙式等待)；n(2) 死锁一定发生了循环等待，而饿死则不然

38、。这也表明通过资源分配图可以检测死锁存在与否，但却不能检测是否有进程饿死；n(3) 死锁一定涉及多个进程，而饥饿或被饿死的进程可能只有一个。3 3.5.5.1.1产生死锁的原因。产生死锁的原因。1 1、竞争资源引起死锁。、竞争资源引起死锁。1 1）可剥夺（）可剥夺（CPUCPU、内存）和非剥夺性（打印机，、内存）和非剥夺性（打印机，磁带机）资源磁带机）资源2 2）竞争非剥夺性资源）竞争非剥夺性资源可造成死锁可造成死锁 p1p2R1R2图3-12 I/O设备共享时的死锁情况3 3）竞争可消耗（临时性）资源）竞争可消耗（临时性）资源n可消耗（临时性）资源是指由一个进程产生，可消耗（临时性）资源是指

39、由一个进程产生，被另一个进程使用一段时间后便无用的资源。被另一个进程使用一段时间后便无用的资源。P1P3S3S1P2S2图3-13进程之间通信时的死锁产生产生接收接收2 2、进程推进顺序不当引起死锁。、进程推进顺序不当引起死锁。213DP2Req(R2)P2Req(R1)P1Req(R1) P1Req(R2)P2Rel(R2)P2Rel(R1)P1Rel(R1) P1Rel(R2)4Release, Request1 1互斥条件（资源的临界性）互斥条件（资源的临界性）2 2请求和保持条件请求和保持条件3 3不可抢占（不剥夺）条件不可抢占（不剥夺）条件4 4环路等待条件环路等待条件 1 1预防死

40、锁：预防死锁： 破坏破坏4 4个条件之一：有效，使资源利用率低。个条件之一：有效，使资源利用率低。2 2避免死锁：防止进入不安全态。避免死锁：防止进入不安全态。3 3检测死锁：检测到死锁再清除。检测死锁：检测到死锁再清除。4 4解除死锁：与解除死锁：与“检测检测”配套。配套。 3.6.1 3.6.1 死锁预防死锁预防 1 1、互斥条件是资源固有属性，不能避免。、互斥条件是资源固有属性，不能避免。2 2、摒弃请求和保持条件、摒弃请求和保持条件全分配，全释放（全分配，全释放（ANDAND同步同步p43p43）优点：简单且安全优点：简单且安全缺点：（缺点：（1 1）延迟进程运行）延迟进程运行（2 2

41、）资源严重浪费）资源严重浪费3 3、摒弃、摒弃“不剥夺不剥夺”条件条件增加系统开销，且进程前段工作可能失效。增加系统开销，且进程前段工作可能失效。 3.6.1 3.6.1 死锁预防死锁预防 4 4、摒弃、摒弃“环路环路”条件条件有序资源分配法：为资源编号，申请时需按编号进行。有序资源分配法：为资源编号，申请时需按编号进行。规定每个进程必须按序号递增的顺序请求资源。规定每个进程必须按序号递增的顺序请求资源。缺点：缺点：（1 1）新增资源不便，（原序号已排定）新增资源不便，（原序号已排定）（2 2）资源与进程使用顺序不同造成浪费）资源与进程使用顺序不同造成浪费（3 3）用户不自由）用户不自由在在“

42、避免死锁避免死锁”方法中的判断条件方法中的判断条件 n1. 安全状态安全状态n 在避免死锁的方法中，允许进程动态地申请资源，但系统在进行资源分配之前，应先计算此次资源分配的安全性。若此次分配不会导致系统进入不安全状态，则将资源分配给进程； 否则，令进程等待。n 所谓安全状态，是指系统能按某种进程顺序(P1, P2, ，Pn)(称P1, P2, , Pn序列为安全序列)，来为每个进程Pi分配其所需资源，直至满足每个进程对资源的最大需求，使每个进程都可顺利地完成。如果系统无法找到这样一个安全序列，则称系统处于不安全状态。 2.2.安全状态例安全状态例进程进程最大需求最大需求已分配已分配可用可用P1

43、1053P242P392安全序列：安全序列：p2p2p1p1p3 p3 3 3安全安全不安全的转换不安全的转换 n上例中，若上例中，若P3P3再申请一台，则不安全再申请一台，则不安全 进程进程最大需求最大需求已分配已分配可用可用P11052P242P393例 3个进程共享4个同类型的资源，每个进程最大需要2个资源，请问该系统是否会因为竞争该资源而死锁？例 n个进程共享m个同类资源，若每个进程若每个进程都需要该类资源都需要该类资源，而且各进程对该类资源的最大需求量之和小于m+n，说明该系统会不会因为竞争该类资源而阻塞？3.6.3 利用银行家算法避免死锁利用银行家算法避免死锁 1. 银行家算法中的

44、数据结构银行家算法中的数据结构 (1) 可利用资源向量Available。这是一个含有m个元素的数组，其中的每一个元素代表一类可利用的资源数目，其初始值是系统中所配置的该类全部可用资源的数目，其数值随该类资源的分配和回收而动态地改变。如果Availablej=K，则表示系统中现有Rj类资源K个。 (2) 最大需求矩阵Max。这是一个nm的矩阵，它定义了系统中n个进程中的每一个进程对m类资源的最大需求。如果Maxi,j=K，则表示进程i需要Rj类资源的最大数目为K。 (3) 分配矩阵Allocation。这也是一个nm的矩阵，它定义了系统中每一类资源当前已分配给每一进程的资源数。如果Alloca

45、tioni,j=K，则表示进程i当前已分得Rj类资源的数目为K。 (4) 需求矩阵Need。这也是一个nm的矩阵，用以表示每一个进程尚需的各类资源数。如果Needi,j=K，则表示进程i还需要Rj类资源K个，方能完成其任务。 Needi,j=Maxi,j-Allocationi,j 2. 银行家算法银行家算法 设Requesti是进程Pi的请求向量，如果Requestij=K，表示进程Pi需要K个Rj类型的资源。当Pi发出资源请求后，系统按下述步骤进行检查： (1) 如果RequestijNeedi,j，便转向步骤2；否则认为出错，因为它所需要的资源数已超过它所宣布的最大值。 (2) 如果Re

46、questijAvailablej，便转向步骤(3)；否则， 表示尚无足够资源，Pi须等待。 (3) 系统试探着把资源分配给进程Pi，并修改下面数据结构中的数值： Availablej =Availablej-Requestij; Allocationi,j =Allocationi,j+Requestij; Needi,j =Needi,j-Requestij; (4) 系统执行安全性算法，检查此次资源分配后，系统是否处于安全状态。若安全，才正式将资源分配给进程Pi，以完成本次分配；否则， 将本次的试探分配作废，恢复原来的资源分配状态，让进程Pi等待。 3. 安全性算法安全性算法 (1) 设

47、置两个向量： 工作向量Work: 它表示系统可提供给进程继续运行所需的各类资源数目，它含有m个元素，在执行安全算法开始时，Work =Available; Finish: 它表示系统是否有足够的资源分配给进程，使之运行完成。开始时先做Finishi =false; 当有足够资源分配给进程时， 再令Finishi =true。 (2) 从进程集合中找到一个能满足下述条件的进程： Finishi=false; Needi,jWorkj； 若找到， 执行步骤(3)， 否则，执行步骤(4)。 (3) 当进程Pi获得资源后，可顺利执行，直至完成，并释放出分配给它的资源，故应执行： Workj =Work

48、j+Allocationi,j; Finishi =true; go to step 2; (4) 如果所有进程的Finishi=true都满足， 则表示系统处于安全状态；否则，系统处于不安全状态。 4. 银行家算法之例银行家算法之例 假定系统中有五个进程P0, P1, P2, P3, P4和三类资源A, B, C，各种资源的数量分别为10、5、7，在T0时刻的资源分配情况如图 3-15 所示。 图 3-15 T0时刻的资源分配表 (1) T0时刻的安全性： 图 3-16 T0时刻的安全序列 (2) P1请求资源：P1发出请求向量Request1(1，0，2)，系统按银行家算法进行检查： Re

49、quest1(1, 0, 2)Need1(1, 2, 2) Request1(1, 0, 2)Available1(3, 3, 2) 系统先假定可为P1分配资源，并修改Available, Allocation1和Need1向量，由此形成的资源变化情况如图 3-15 中的圆括号所示。 再利用安全性算法检查此时系统是否安全。 图 3-17 P1申请资源时的安全性检查 (3) P4请求资源：P4发出请求向量Request4(3，3，0)，系 统按银行家算法进行检查： Request4(3, 3, 0)Need4(4, 3, 1); Request4(3, 3, 0) Available(2, 3, 0)不成立，让P4等待。 (4)