计算机操作系统：第三章 处理机的调度和死锁

1、v 3.13.1高、中、低三级调度高、中、低三级调度 v 1 1、高级调度（作业调度、长程调度、接纳调度）、高级调度（作业调度、长程调度、接纳调度） 将外存作业调入内存，创建将外存作业调入内存，创建PCBPCB等，插入就绪等，插入就绪队列。队列。 一般用于批处理系统，分一般用于批处理系统，分/ /实时系统一般直接实时系统一般直接入内存，无此环节。入内存，无此环节。 调度特性调度特性 1.1.接纳作业数（内存驻留数）接纳作业数（内存驻留数）太多太多 周转时间周转时间T T长长太少太少 系统效率低系统效率低 2.2.接纳策略：即采用何种调度算法：接纳策略：即采用何种调度算法：FCFSFCFS、短、

2、短作业优先等作业优先等v 2 2、低级调度（进程调度，短程调度）、低级调度（进程调度，短程调度）v 主要是由分派程序（主要是由分派程序（DispatcherDispatcher）分派处理机。）分派处理机。.1 1.非抢占方式：非抢占方式：简单，实时性差简单，实时性差 ( (如如win31)win31).2 2.抢占方式抢占方式（1 1）时间片原则）时间片原则（2 2）优先权原则）优先权原则（3 3）短作业优先原则。）短作业优先原则。 v运行频率：低运行频率：低 中中 高高。 处理机调度状态及其转换图处理机调度状态及其转换图 spoolingspooling系统系统收容收容就绪就绪等待等待交换调

3、度交换调度完完成成作业调度作业调度进程调度进程调度运行运行就绪就绪等待等待外外存存线程调度线程调度内内存存输入井输入井v三种调度被引发的事件？三种调度被引发的事件？v事件的表现方式？事件的表现方式？v一、仅有进程调度的队列模型一、仅有进程调度的队列模型就绪队列就绪队列CPU阻塞队列阻塞队列交互用户交互用户时间片完时间片完进程调度进程调度进程完成进程完成等待事件等待事件事件出现事件出现v二、具有高二、具有高/ /低级模型低级模型就绪队列就绪队列CPU阻塞队列阻塞队列时间片完时间片完进程调度进程调度进程进程完成完成等待事件等待事件1事件事件1出现出现后备队列后备队列阻塞队列阻塞队列等待事件等待事件

4、2事件事件2出现出现作业调度作业调度就绪队列就绪队列CPU就绪、挂起队列就绪、挂起队列时间片完时间片完进程调度进程调度进程进程完成完成后备队列后备队列阻塞、挂起队列阻塞、挂起队列事件出现事件出现作业调度作业调度阻塞队列阻塞队列等待事件等待事件挂起挂起事件出现事件出现中级调度中级调度交互型作业交互型作业v 一、面向用户的准则一、面向用户的准则1 1 周转时间短（常用于批处理系统）周转时间短（常用于批处理系统） 概念：作业从提交概念：作业从提交 完成的时间完成的时间. .分为：分为： （1 1）驻外等待调度时间）驻外等待调度时间 （2 2）驻内等待调度时间）驻内等待调度时间 （3 3）执行时间）执

5、行时间 （4 4）阻塞时间）阻塞时间v 一、面向用户的准则一、面向用户的准则 平均周转时间平均周转时间 平均带权平均带权 可见带权可见带权w w越小越好越小越好,Ts,Ts为实际服务时间。为实际服务时间。11niiTnT11nisiTTnWv 一、面向用户的准则一、面向用户的准则2 2 响应时间快：（对交互性作业）响应时间快：（对交互性作业） 概念：键盘提交请求到首次响应时间概念：键盘提交请求到首次响应时间 （1 1）输入传送时间）输入传送时间 （2 2）处理时间）处理时间 （3 3）响应传送时间）响应传送时间3 3 截止时间的保证（特别于实时系统）截止时间的保证（特别于实时系统）4 4 优先

6、权准则：（即需要抢占调度）优先权准则：（即需要抢占调度）v 二、面向系统的准则二、面向系统的准则1 1 吞吐量高（特别于批处理）：单位时间完成作吞吐量高（特别于批处理）：单位时间完成作业数业数2 2 处理机利用率好：（因处理机利用率好：（因CPUCPU贵，特别于大中型贵，特别于大中型多用户系统）多用户系统）3 3 各类资源的平衡利用。（？折算标准）各类资源的平衡利用。（？折算标准）v3.2.13.2.1先来先服务和短作业（进程）优先调度算法先来先服务和短作业（进程）优先调度算法 1.FCFS1.FCFS特点：简单，有利于长作业特点：简单，有利于长作业 即即CPUCPU繁忙性作业繁忙性作业2.2

7、.短作业进程优先调度算法：短作业进程优先调度算法：SJ(P)FSJ(P)F提高了平均周转时间和平均带权周转时间（从而提提高了平均周转时间和平均带权周转时间（从而提高了系统吞吐量）高了系统吞吐量）特点：对长作业不利，有可能得不到服务（饥饿）特点：对长作业不利，有可能得不到服务（饥饿）估计时间不易确定估计时间不易确定在单道环境下，某批处理系统有四道作业，已知他们的在单道环境下，某批处理系统有四道作业，已知他们的进入系统的时刻、估计运算时间如下：进入系统的时刻、估计运算时间如下：作业作业进入时刻进入时刻(h)运行时间运行时间(h)12348.008.509.009.502.000.500.100.2

8、0用用FCFS算法计算作业的运行情况、平均周转时间和平算法计算作业的运行情况、平均周转时间和平均带权周转时间均带权周转时间FCFSFCFS调度算法调度算法作业作业进入时刻进入时刻 运行时间运行时间开始时刻开始时刻 完成时刻完成时刻 周转时间周转时间 带权周转带权周转12348.008.509.009.502.000.500.100.208.0010.0010.5010.6010.0010.5010.6010.802.002.001.601.301.004.0016.006.50平均周转时间平均周转时间T1.725（h）平均带权周转时间平均带权周转时间T6.875（h）FCFSFCFS调度算法（

9、续）调度算法（续）最短作业优先法（最短作业优先法（SJFSJF）该算法总是优先调度要求运行时间最短的作业该算法总是优先调度要求运行时间最短的作业运行顺序运行顺序 1 3 4 2平均周转时间平均周转时间 T1.55h平均带权周转时间平均带权周转时间T5.15h作业作业 进入时刻进入时刻 运行时间运行时间 开始时刻开始时刻 完成时刻完成时刻 周转时间周转时间 带权周转带权周转1 8.00 2.00 8.00 10.00 2.00 1.00 2 8.50 0.50 10.30 10.80 2.30 4.60 3 9.00 0.10 10.00 10.10 1.10 11.004 9.50 0.20

10、10.10 10.30 0.80 4.50 作业名到达时间服务时间开始执行时间完成时间周转时间带权周转时间A010111B110011011001C21101102100100D31001022021991.99作业作业名名 A B C D E平均平均到达时间到达时间 0 1 2 3 4服务时间服务时间 4 3 5 2 4FCFS完成时间完成时间 4 7 12 14 18周转时间周转时间 4 6 10 11 149带权周转时间带权周转时间 1 2 2 5.5 3.52.8SJF完成时间完成时间 4 9 18 6 13周转时间周转时间 4 8 16 3 98带权周转时间带权周转时间 1 2.67

11、 3.1 1.5 2.252.1v 1.1.优先权调度算法类型优先权调度算法类型 非抢占式优先权算法非抢占式优先权算法 抢占式优先权算法，实时性更好。抢占式优先权算法，实时性更好。v 2.2.优先权类型：优先权类型：（ （1 1）静态优先权：静态优先权： 进程优先权在整个运行期不变。进程优先权在整个运行期不变。 确定优先权依据确定优先权依据（1 1）进程类型）进程类型（2 2）进程对资源的需求；）进程对资源的需求；（3 3）根据用户需求。）根据用户需求。 特点：简单，但低优先权作业可能长期不被特点：简单，但低优先权作业可能长期不被调度。调度。v （2 2）动态优先权：动态优先权： 如：优先权随

12、执行时间而下降，随等待时间而升高。如：优先权随执行时间而下降，随等待时间而升高。 响应比响应比Rp=Rp=（等待时间服务时间）（等待时间服务时间）/ /服务时间服务时间 作为优作为优先权先权 优点：长短兼顾优点：长短兼顾 缺点：需计算缺点：需计算RpRpv 3.3.高响应比优先算法：高响应比优先算法： 特点：特点： 响应比响应比Rp=Rp=（tw+tstw+ts）/ts/ts（ （1 1）短作业）短作业R RP P大。大。（ （2 2）tsts（要求服务时间）相同的进程间相当于（要求服务时间）相同的进程间相当于FCFSFCFS。（ （3 3）长作业等待一段时间仍能得到服务。）长作业等待一段时间

13、仍能得到服务。最高响应比作业优先算法（最高响应比作业优先算法（HRNHRN）作业作业 进入时刻进入时刻 运行时间运行时间 开始时刻开始时刻 完成时刻完成时刻 周转时间周转时间 带权周转带权周转 1 8.00 2.00 8.00 10.00 2.00 1.00 2 8.50 0.50 10.00 10.60 2.10 4.20 3 9.00 0.10 10.50 10.10 1.10 11.00 4 9.50 0.20 10.60 10.80 1.30 6.50 平均周转时间平均周转时间1.625h 带权周转时间带权周转时间 5.675hv 1.1.时间片轮转时间片轮转 时间片大小的确定时间片大

14、小的确定 太大：退化为太大：退化为FCFSFCFS； 太小：系统开销过大太小：系统开销过大 系统对响应时间的要求；系统对响应时间的要求；T=nqT=nq 就绪队列中进程的数目；就绪队列中进程的数目； 系统的处理能力：（应保证一个时间片处理完常用命令）系统的处理能力：（应保证一个时间片处理完常用命令）v 2.2.多级反馈队列调度多级反馈队列调度 特点：长、短作业兼顾，有较好的响应时间特点：长、短作业兼顾，有较好的响应时间 （1 1）短作业一次完成；）短作业一次完成； （2 2）中型作业周转时间不长；）中型作业周转时间不长； （3 3）大型作业不会长期不处理。）大型作业不会长期不处理。就绪队列就绪

15、队列1 1至至CPUS1就绪队列就绪队列2 2S2至至CPU就绪队列就绪队列3 3S3至至CPU就绪队列就绪队列n nSn至至CPU时间片：时间片：S1S2S3图图35多级队列反馈调度算法多级队列反馈调度算法作业名作业名 进入时间进入时间 运行时间（分）运行时间（分） 需内存量需内存量KB A 8:06 42 15 B 8:18 30 60 C 8:30 24 50 D 8:36 24 10 E 8:42 12 20 有用户空间有用户空间100KB，并规定作业相应程序装入内，并规定作业相应程序装入内存连续区域，并不能被移动，作业与进程均采存连续区域，并不能被移动，作业与进程均采用用SJF算法算

16、法作业名作业名 进入时间进入时间 运行时间（分）运行时间（分） 需内存量需内存量KB A 8:06 42 15 B 8:18 30 60 C 8:30 24 50 D 8:36 24 10 E 8:42 12 20 名名 装装 入入 内内 存存 时时 间间 开开 始始 时时 间间 结结 束束 时时 间间 周周 转转 时时 间间 带带 权权 周周 转转 时时 间间 A 8:06 8:06 8:48 42 42/42 B 8:18 8:48 9:18 60 60/30 D 8:36 9:18 9:42 66 66/24 E 9:18 9:42 9:54 96 72/12 C 9:18 9:54 1

17、0:18 108 108/24一个四道作业的操作系统中，设在一段时间内先后到达一个四道作业的操作系统中，设在一段时间内先后到达6个作业，它们的提交时间和运行时间见表个作业，它们的提交时间和运行时间见表作业号作业号 提交时间提交时间 运行时间运行时间 JOB1JOB2JOB3JOB4JOB5JOB68:008:208:258:308:358:4060352025 510系统采用短作业优先的调度算法，作业被调度进入运行后不再退出，但当一作业系统采用短作业优先的调度算法，作业被调度进入运行后不再退出，但当一作业进入运行时，可以调整运行的优先次序。进入运行时，可以调整运行的优先次序。1 按照所选择的调

18、度算法，请分别给出上述按照所选择的调度算法，请分别给出上述6个作业的执行时间次序个作业的执行时间次序2 计算在上述调度算法下作业的平均周转时间计算在上述调度算法下作业的平均周转时间作业作业一个具有两道作业的批处理系统，一个具有两道作业的批处理系统，作业调度采用短作业优作业调度采用短作业优先先的调度算法，的调度算法，进程调度采用以优先数为基础的抢占式调进程调度采用以优先数为基础的抢占式调度算法度算法，如下表的作业序列（表中所有作业优先数即为进，如下表的作业序列（表中所有作业优先数即为进程优先数，数值越小优先级越高）。程优先数，数值越小优先级越高）。1 列出所有作业进入内存时间及结束时间列出所有作

19、业进入内存时间及结束时间2 计算平均周转时间计算平均周转时间作业的执行时间作业的执行时间作业名作业名 到达时间到达时间 估计运算时间估计运算时间 优先数优先数A 10：00 40分分 5B 10：20 30分分 3C 10：30 50分分 4D 10：50 20分分 6作业作业有有5个批处理作业（个批处理作业（A、B、C、D、E）几乎同时到达一个）几乎同时到达一个计算中心，估计的运行时间分别为计算中心，估计的运行时间分别为2，4，6，8、10分钟，分钟，它们的优先级分别为它们的优先级分别为1，2，3，4，5（1为最低优先级），为最低优先级），对下面的每种调度算法，分别计算作业的平均周转时间。对

20、下面的每种调度算法，分别计算作业的平均周转时间。1 最高优先级先最高优先级先2 时间片轮转（时间片为时间片轮转（时间片为2分钟）分钟）3 FIFO（作业到达顺序为（作业到达顺序为C、D、B、E、A）4 短作业优先短作业优先作业作业v 有一个具有两道作业的批处理系统，作业调度采用有一个具有两道作业的批处理系统，作业调度采用FCFS的调度算法，进程调度采用以优先数为基础的抢的调度算法，进程调度采用以优先数为基础的抢占式调度算法。在下表所示的作业序列，作业优先数即占式调度算法。在下表所示的作业序列，作业优先数即为进程优先数，优先数越小优先级越高。为进程优先数，优先数越小优先级越高。作业名到达时间运行

21、时间（分）优先数A10:00405B10:20303C10:30504D10:50206（1）计算平均周转时间。）计算平均周转时间。v设有一组作业，它们德提交时间及运行时间设有一组作业，它们德提交时间及运行时间如下所示：如下所示：作业号提交时间运行时间（分钟）18:007028:403038:501049:105试问在单道方式下，采用响应比高者优先调度算法，试问在单道方式下，采用响应比高者优先调度算法，作业的执行顺序是什么？作业的执行顺序是什么？v 3.3.13.3.1实现实时调度的基本条件实现实时调度的基本条件1 1 提供必要的调度信息提供必要的调度信息 （1 1）就绪时间；）就绪时间； （

22、2 2）开始）开始/ /完成截止时间；完成截止时间； （3 3）处理时间；）处理时间； （4 4）资源要求；）资源要求； （5 5）优先级；）优先级；2 2 系统处理能力强系统处理能力强NPCPCmiiimiii111Ci为处理时间，为处理时间，Pi为周期时间（基于周期性实时任务）为周期时间（基于周期性实时任务）.3 3.采用抢占调度方式采用抢占调度方式 剥夺方式：一般都采用此剥夺方式：一般都采用此 非剥夺方式（实现简单）：一般应使实时任务较小，非剥夺方式（实现简单）：一般应使实时任务较小，以及时放弃以及时放弃CPUCPU。.4 4.具有快速切换机制具有快速切换机制 具有快速响应外部中断能力。

23、具有快速响应外部中断能力。 快速任务分派快速任务分派v 1 1非抢占式调度算法非抢占式调度算法 时间片轮转时间片轮转 秒级秒级 非抢占优先权（协同）非抢占优先权（协同） 秒秒 毫秒级毫秒级v 2 2抢占式调度算法抢占式调度算法 时钟中断抢占优先权时钟中断抢占优先权 毫秒级毫秒级 基于抢占点抢占基于抢占点抢占 立即抢占立即抢占immediate preemption immediate preemption 毫秒毫秒 微秒级微秒级 只要不在临界区即抢占（中断引发）只要不在临界区即抢占（中断引发）进程1进程2进程n实时进程调度时间调度时间实时进程要求调度实时进程要求调度调度实时进程运行调度实时进程

24、运行a 非抢占轮转调度非抢占轮转调度当前进程实时进程实时进程要求调度实时进程要求调度当前进程运行完成当前进程运行完成b 非抢占优先权调度非抢占优先权调度调度时间调度时间c 基于时钟中断抢占的优先权抢占调度基于时钟中断抢占的优先权抢占调度当前进程实时进程实时进程要求调度实时进程要求调度抢占时刻（其它中断）抢占时刻（其它中断）b 立即抢占优先权调度立即抢占优先权调度当前进程实时进程实时进程要求调度实时进程要求调度时钟中断到达时时钟中断到达时调度时间调度时间调度时间调度时间v 1.1.最早截止时间优先最早截止时间优先EDFEDF（earliest deadline first)earliest de

25、adline first)算算法法 根据任务的截止时间来确定任务的优先级根据任务的截止时间来确定任务的优先级 截止时间越早，优先级越高截止时间越早，优先级越高 可以是抢占式或非抢占式可以是抢占式或非抢占式1342134212 34t开始截止时间开始截止时间任务到达任务到达任务执行任务执行图图37 EDF算法用于非抢占调度方式算法用于非抢占调度方式v 松弛度：松弛度： 若若A A进程需在进程需在200ms200ms时完成，其本身运行需要时完成，其本身运行需要100ms100ms，当，当前时刻是前时刻是10ms10ms，则，则A A的松弛度为：的松弛度为：20020010010010109090

26、主要用于可抢占的调度方式中主要用于可抢占的调度方式中例：例：假如在一个实时系统中，有两个周期性实时任务假如在一个实时系统中，有两个周期性实时任务A和和B，任务，任务A要求每要求每 20 ms执行一次，执行时间为执行一次，执行时间为 10 ms；任务任务B只要求每只要求每50 ms执行一次，执行时间为执行一次，执行时间为 25 ms。由此。由此可得知任务可得知任务A和和B每次必须完成的时间分别为：每次必须完成的时间分别为：A1、A2、A3、和和B1、B2、B3、，见图，见图3-8。为保证不遗漏任何。为保证不遗漏任何一次截止时间，应采用最低松弛度优先的抢占调度策略。一次截止时间，应采用最低松弛度优

27、先的抢占调度策略。 A1A2A3A4A5A6A7A8B1B2B3020406080 100120 140160t图图38 A/B任务每次必须完成的时间任务每次必须完成的时间在刚开始时在刚开始时(t1=0)，A1必须在必须在20 ms时完成，而它本身时完成，而它本身运行又需运行又需 10 ms，可算出，可算出A1的松弛度为的松弛度为10 ms；B1必须在必须在50 ms时完成，而它本身运行就需时完成，而它本身运行就需25 ms，可算出，可算出B1的松弛度为的松弛度为25 ms，故调度程序应先调度，故调度程序应先调度A1执行。在执行。在t2=10 ms时，时，A2的松弛度可按下式算出：的松弛度可按

28、下式算出： A2的松弛度的松弛度=必须完成时间必须完成时间- -其本身的运行时间其本身的运行时间- -当前时间当前时间=40 ms- -10 ms- -10 ms=20 ms 类似地，可算出类似地，可算出B1的松弛度为的松弛度为15 ms，故调度程序应选择，故调度程序应选择B2运运行。在行。在t3=30 ms时，时，A2的松弛度已减为的松弛度已减为0(即即40- -10- -30)，而，而B1的松弛度为的松弛度为15 ms(即即50- -5- -30)，于是调度程序应抢占，于是调度程序应抢占B1的处理的处理机而调度机而调度A2运行。在运行。在t4=40 ms时，时，A3的松弛度为的松弛度为10

29、 ms(即即60- -10- -40)，而，而B1的松弛度仅为的松弛度仅为5 ms(即即50- -5- -40)，故又应重新，故又应重新调度调度B1执行。在执行。在t5=45 ms时，时，B1执行完成，而此时执行完成，而此时A3的松弛度已的松弛度已减为减为5 ms(即即60- -10- -45)，而，而B2的松弛度为的松弛度为30 ms(即即100- -25- -45)，于是又应调度，于是又应调度A3执行。在执行。在t6=55 ms时，任务时，任务A尚未进入第尚未进入第4周期，而任务周期，而任务B已进入第已进入第2周期，故再调度周期，故再调度B2执行。在执行。在t7=70 ms时，时，A4的松

30、弛度已减至的松弛度已减至0 ms(即即80- -10- -70)，而，而B2的松弛度为的松弛度为20 ms(即即100- -10- -70)，故此时调度又应抢占，故此时调度又应抢占B2的处理机而调度的处理机而调度A4执行。图执行。图3-12示出了具有两个周期性实时任务的调度情况。示出了具有两个周期性实时任务的调度情况。 A1(10)A2(10)A3(10)A4(10)t01020304050607080t1=0B1(20)B1(5)B2(15)B2(10)t1t2t3t4t5t6t7t8v 1.1.紧密耦合紧密耦合MPSMPS和松弛耦合和松弛耦合MPSMPS 紧密耦合紧密耦合 共享共享RAMR

31、AM和和I/OI/O 高速总线和交叉开关连接高速总线和交叉开关连接 松弛耦合松弛耦合 独立独立RAMRAM和和I/OI/O 通道和通信线路连接通道和通信线路连接v 2.2.对称多处理器系统和非对称多处理器系统对称多处理器系统和非对称多处理器系统 处理器是否结构相同处理器是否结构相同v 1.SMP1.SMP中进程分配方式中进程分配方式 静态分配静态分配 动态分配动态分配 可防止系统中多个处理器忙闲不均可防止系统中多个处理器忙闲不均v 2.2.非非SMPSMP中进程分配方式中进程分配方式 进程调度在主处理器上执行进程调度在主处理器上执行 有潜在的不可靠性有潜在的不可靠性 v 1.1.自调度自调度

32、各个处理机自行在就绪队列中取任务。各个处理机自行在就绪队列中取任务。 特点；简单，分布式调度，调度算法可采用特点；简单，分布式调度，调度算法可采用前述方法，多个前述方法，多个CPUCPU利用率都不错（不会闲）利用率都不错（不会闲） 但：但： 瓶颈问题，（单队列）瓶颈问题，（单队列） 低效性；（需拷贝现场）低效性；（需拷贝现场） 线程切换频繁（当线程合作时线程切换频繁（当线程合作时, ,各线程并各线程并行的条件不容易满足）行的条件不容易满足） v 优点：优点：（1 1）对相互合作的进（线）程组调度，可以减小切换，）对相互合作的进（线）程组调度，可以减小切换，减小系统开销。减小系统开销。（2 2）

33、每次分配一组）每次分配一组CPUCPU，减少了调度频率。，减少了调度频率。v 分配时间分配时间（1 1）面向程序）面向程序（2 2）面向线程：使处理机利用率更高。）面向线程：使处理机利用率更高。 应用程序应用程序A应用程应用程序序BCpu1线程线程1线程线程1Cpu2线程线程2空闲空闲Cpu3线程线程3空闲空闲Cpu4线程线程4空闲空闲时间时间1/21/2浪费浪费37.5%应用程序应用程序A应用程应用程序序BCpu1线程线程1线程线程1Cpu2线程线程2空闲空闲Cpu3线程线程3空闲空闲Cpu4线程线程4空闲空闲时间时间4/51/5浪费浪费15%v 引入：多处理机系统，每个处理已不再属宝贵资源

34、。引入：多处理机系统，每个处理已不再属宝贵资源。v 特点：每个进（线）程专用处理机，使其切换小，特点：每个进（线）程专用处理机，使其切换小，提高效率。提高效率。v 主要用于大型计算，实时系统主要用于大型计算，实时系统3.53.5产生死锁的原因和必要条件产生死锁的原因和必要条件v 3.5.13.5.1产生死锁的原因。产生死锁的原因。v 一、竞争资源引起死锁。一、竞争资源引起死锁。1 1 可剥夺（可剥夺（CPUCPU、内存，）和非剥夺性（打印机，磁、内存，）和非剥夺性（打印机，磁带机）资源带机）资源2 2 竞争非剥夺性资源竞争非剥夺性资源可造成死锁可造成死锁 p1p2R1R2v 3 3竞争临时性资

35、源竞争临时性资源 临时性资源是指由一个进程产生，被另一个进程使用临时性资源是指由一个进程产生，被另一个进程使用一段时间后便无用的资源。一段时间后便无用的资源。213DP2Req(R2)P2Req(R1)P1Req(R1) P1Req(R2)P2Rel(R2)P2Rel(R1)P1Rel(R1) P1Rel(R2)4v死锁死锁Deadlock：是计算机系统中多道程序并发：是计算机系统中多道程序并发执行时，两个或两个以上的进程由于竞争资源执行时，两个或两个以上的进程由于竞争资源而造成的一种互相等待的现象（僵局），如无而造成的一种互相等待的现象（僵局），如无外力作用，这些进程将永远不能再向前推进。外

36、力作用，这些进程将永远不能再向前推进。v陷入死锁状态的进程称为陷入死锁状态的进程称为死锁进程死锁进程，所占用的，所占用的资源或者需要它们进行某种合作的其它进程就资源或者需要它们进行某种合作的其它进程就会相继陷入死锁，最终可能导致整个系统处于会相继陷入死锁，最终可能导致整个系统处于瘫痪状态。瘫痪状态。 v 1 1互斥条件互斥条件: : 进程访问的是临界资源，那个资源一次进程访问的是临界资源，那个资源一次只能被一个进程所使用。只能被一个进程所使用。v 2 2不剥夺条件不剥夺条件: : 一个资源仅能被占有它的进程所释放，一个资源仅能被占有它的进程所释放，而不能被其他进程剥夺。而不能被其他进程剥夺。v

37、 3 3部分分配（请求和保持条件）部分分配（请求和保持条件） : : 一个进程在请求一个进程在请求新的资源的同时，保持对某些资源的占有。新的资源的同时，保持对某些资源的占有。v 4 4环路等待条件环路等待条件: : 存在一个进程的环路链，链中每一存在一个进程的环路链，链中每一个进程占用有着某个或某些资源，又在等待链中的另一个进程占用有着某个或某些资源，又在等待链中的另一个进程占有的资源。个进程占有的资源。死锁模型死锁模型R1R2P1P2申请申请r2已分配给已分配给p2申请申请r1已分配给已分配给P1R2已经分配给已经分配给P1、R1已经分配给已经分配给P2v 1 1预防；破坏预防；破坏4 4个

38、条件之一：有效，使资源个条件之一：有效，使资源利用率低。利用率低。v 2 2避免：防止进入不安全态。避免：防止进入不安全态。v 3 3检测：检测到死锁再清除。检测：检测到死锁再清除。v 4 4解除：与解除：与“检检”配套。配套。v 3.6.1 3.6.1 死锁预防死锁预防 一、互斥条件是资源固有属性，不能避免。一、互斥条件是资源固有属性，不能避免。 二、摒弃请求和保持条件二、摒弃请求和保持条件全分配，全释放（全分配，全释放（ANDAND）缺点：（缺点：（1 1）延迟进程运行）延迟进程运行（2 2）资源严重浪费）资源严重浪费 三、摒弃三、摒弃“不剥夺不剥夺”条件条件增加系统开销，且进程前段工作可

39、能失效。增加系统开销，且进程前段工作可能失效。v 3.6.1 3.6.1 死锁预防死锁预防 四、摒弃四、摒弃“环路环路”条件条件有序资源分配法：为资源编号，申请时需按编号进有序资源分配法：为资源编号，申请时需按编号进行。行。缺点：缺点：（1 1）新增资源不便，（原序号已排定）新增资源不便，（原序号已排定）（2 2）用户不自由）用户不自由（3 3）资源与进程使用顺序不同造成浪费）资源与进程使用顺序不同造成浪费v在在“避免死锁避免死锁”方法中的判断条件方法中的判断条件 v1. 1. 安全状态安全状态v 安全状态：指系统能按照某种顺序如安全状态：指系统能按照某种顺序如(称为称为序列为安全序列序列为安

40、全序列)，为每个进程分配，为每个进程分配所需的资源，直至最大需求，使得每个进程都能顺利完所需的资源，直至最大需求，使得每个进程都能顺利完成。成。 v 非安全状态：即在某个时刻系统中不存在一个安全序非安全状态：即在某个时刻系统中不存在一个安全序列，则称系统处于不安全状态或非安全状态列，则称系统处于不安全状态或非安全状态。v 能找到安全序列的状态为安全状态。能找到安全序列的状态为安全状态。v2.2.安全状态例安全状态例进程进程最大需求最大需求已分配已分配可用可用P11053P242P392安全序列：安全序列：p2p2p1p1p3 p3 v3 3安全安全不安全的转换不安全的转换 上例中，若上例中，若

41、P3P3再申请一台，则不安全再申请一台，则不安全 进程进程最大需求最大需求已分配已分配可用可用P11052P242P393u银行家算法是最有代表性的避免死锁银行家算法是最有代表性的避免死锁算法，是算法，是Dijkstra提出的银行家算法。提出的银行家算法。这是由于该算法能用于银行系统现金这是由于该算法能用于银行系统现金贷款的发放而得名。为实现银行家算贷款的发放而得名。为实现银行家算法，系统中必须设置若干数据结构。法，系统中必须设置若干数据结构。v 1 1数据结构数据结构 availablej=k: availablej=k: 系统现有系统现有RjRj类资源类资源k k个；个； maxi,j=k

42、: maxi,j=k: 进程进程i i需要需要RjRj的最大数的最大数k k个；个； alloci,j=k: alloci,j=k: 进程进程i i已得到已得到RjRj类资源类资源k k个；个； needi,j=k:needi,j=k: 进程进程i i需要需要RjRj类资源类资源k k个个 有：有：needi,j= maxi,jneedi,j= maxi,jalloci,jalloci,j requestirequesti进程进程i i请求资源数请求资源数 workiworki：进程：进程i i执行完后系统应有资源数（也即可用数）执行完后系统应有资源数（也即可用数） finishifinish

43、i：布尔量，表进程：布尔量，表进程i i能否顺序完成。能否顺序完成。 v 2 2银行家算法银行家算法 reqi=needierrorreqi=availiblockavail=avail-reqialloci=alloci+reqineedi=needi-reqifinishi=.F.needi=workwork=work+allocifinishi=.T.v 银行家算法银行家算法 设设Requesti是进程是进程Pi的请求向量，如果进程的请求向量，如果进程Pi需要需要K个个Rj类资源，当类资源，当Pi发出资源请求后，系统按下述步骤进行检发出资源请求后，系统按下述步骤进行检查：查：1 如果如果

44、RequestiNeedi,则转向步骤则转向步骤2；否则认为出错。；否则认为出错。（因为它所需要的资源数已超过它所宣布的最大值。（因为它所需要的资源数已超过它所宣布的最大值。2 如果如果RequestiAvailable,则转向步骤则转向步骤3；否则，表示；否则，表示系统中尚无足够的资源，系统中尚无足够的资源，Pi必须等待必须等待3 系统试探把要求的资源分配给进程系统试探把要求的资源分配给进程Pi，并修改下面数据，并修改下面数据结构中的数值：结构中的数值：Available:=Available-Requesti;Allocation:=Allocation+Requesti;Needi:=

45、Needi- Requesti;4 系统执行安全性算法，检查此次资源分配后，系统是否系统执行安全性算法，检查此次资源分配后，系统是否处于安全状态。若安全，正式将资源分配给进程处于安全状态。若安全，正式将资源分配给进程Pi，以，以完成本次分配；否则，将试探分配作废，恢复原来的资完成本次分配；否则，将试探分配作废，恢复原来的资源分配状态，让进程源分配状态，让进程Pi等待。等待。 安全性算法安全性算法系统所执行的安全性算法可描述如下：系统所执行的安全性算法可描述如下：1 设置两个向量设置两个向量工作向量工作向量Work.Work.它表示系统可提供给进程继续运行所需要的各类资它表示系统可提供给进程继续

46、运行所需要的各类资源 的 数 目 ， 它 含 有源 的 数 目 ， 它 含 有 m m 个 元 素 ， 执 行 安 全 算 法 开 始 时 ，个 元 素 ， 执 行 安 全 算 法 开 始 时 ，Work:=AvailableWork:=Available。Finish.Finish.它表示系统是否有足够的资源分配给进程，使之运行完成它表示系统是否有足够的资源分配给进程，使之运行完成。开始时先做。开始时先做Finishi:=falseFinishi:=false；当有足够的资源分配给进程时；当有足够的资源分配给进程时，令，令Finishi:=true.Finishi:=true.2 从 进 程

47、 集 合 中 找 到 一 个 能 满 足 下 述 条 件 的 进 程 ：从 进 程 集 合 中 找 到 一 个 能 满 足 下 述 条 件 的 进 程 ：Finishi=false; Finishi=false; NeediWork. Work. 如找到，执行步骤如找到，执行步骤3 3；否；否则执行步骤则执行步骤4 4。3 当进程当进程Pi获得资源后，可顺利执行，直至完成，并释放出分配给获得资源后，可顺利执行，直至完成，并释放出分配给它的资源，故执行：它的资源，故执行：Work:=Work+Allocation;Finishi:=true;Finishi:=true;Goto step2;Go

48、to step2;4 如果所有进程的如果所有进程的Finishi=trueFinishi=true，则表示系统处于安全状态；否，则表示系统处于安全状态；否则，系统处于不安全状态。则，系统处于不安全状态。 Max A B C Allocation A B C Need A B C Available A B C p0 7 5 3 0 1 0 7 4 3 3 3 2(2 3 0) p1 3 2 2 2 0 0(3 0 2) 1 2 2(0 2 0) 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 1T0时刻的资源分配表时刻的

49、资源分配表Work A B CNeed A B C Alloc A B CWork+alloc A B C Finish p1 3 3 2 1 2 2 2 0 0 5 3 2 true p3 5 3 2 0 1 1 2 1 1 7 4 3 true p4 7 4 3 4 3 1 0 0 2 7 4 5 true p2 7 4 5 6 0 0 3 0 2 10 4 7 true p0 10 4 7 7 4 3 0 1 0 10 5 7 trueT0时刻的安全序列时刻的安全序列Work A B CNeed A B C Alloc A B CWork+alloc A B C Finish p1 2

50、3 0 0 2 0 3 0 2 5 3 2 true p3 5 3 2 0 1 1 2 1 1 7 4 3 true p4 7 4 3 4 3 1 0 0 2 7 4 5 true p0 7 4 5 7 4 3 0 1 0 7 5 5 true p2 7 5 5 6 0 0 3 0 2 10 5 7 trueP1申请资源申请资源(1,0,2)时安全性检查时安全性检查(安全安全) Allocation A B C Need A B C Available A B C p0 0 3 0 7 2 3 2 1 0 p1 3 0 2 0 2 0 p2 3 0 2 6 0 0 p3 2 1 1 0 1 1

51、 p4 0 0 2 4 3 1为为P0分配（分配（0，2，0）后的情况（不安全）后的情况（不安全）v3.7.13.7.1检测检测v1.1.资源分配图资源分配图（RAG）p1p2资源分配图（资源分配图（RAG）v 系统死锁可用系统死锁可用资源分配图资源分配图来描述，该图是由一组结来描述，该图是由一组结点点N和一组边和一组边E所组成的一对偶所组成的一对偶G=(N,E)。（用圆圈。（用圆圈代表一个进程，用方框代表一类资源，由于一种类代表一个进程，用方框代表一类资源，由于一种类型的资源可能有多个，可用方框中的一个点代表一型的资源可能有多个，可用方框中的一个点代表一类资源中的一个资源）类资源中的一个资源

52、）几个概念：请求边，分配边几个概念：请求边，分配边 P1P2r1r2请求请求r2资源分配图资源分配图u封锁进程封锁进程：是指某个进程由于请求了超过了系统中现有：是指某个进程由于请求了超过了系统中现有的未分配资源数目的资源，而被系统封锁的进程。的未分配资源数目的资源，而被系统封锁的进程。u非封锁进程非封锁进程：即没有被系统封锁的进程。：即没有被系统封锁的进程。u资源分配图的化简方法：资源分配图的化简方法：假设某个假设某个RAG中存在一个进程中存在一个进程Pi，此刻，此刻Pi是非封锁进程，那么可以进行如下化简：当是非封锁进程，那么可以进行如下化简：当Pi有请求边时，首先将其请求边变成分配边有请求边

53、时，首先将其请求边变成分配边(即满足即满足Pi的的资源请求资源请求)，而一旦，而一旦Pi的所有资源请求都得到满足，的所有资源请求都得到满足，Pi就就能在有限的时间内运行结束，并释放其所占用的全部资能在有限的时间内运行结束，并释放其所占用的全部资源，此时源，此时Pi只有分配边，删去这些分配边（实际上相当只有分配边，删去这些分配边（实际上相当于消去了于消去了Pi的所有请求边和分配边），使的所有请求边和分配边），使Pi成为孤立结成为孤立结点。（反复进行）点。（反复进行）P1P2r1r2P1P2r1r2P1P2r1r2资源分配图的化简资源分配图的化简2.2.死锁定理死锁定理简化资源分配图简化资源分配图

54、，若能完全简化则消去所有的边。若能完全简化则消去所有的边。定理：死锁状态的充分条件，资源分配图不可完全简化定理：死锁状态的充分条件，资源分配图不可完全简化3.3.检测死锁的算法：检测死锁的算法：Work= availableL:=Li| alloci=0 reqi=0 (孤立进程点孤立进程点)For all Li L doBeginFor all reqi =work doBeginWork=work+allociL=LiLendEndDeadlock= (L=p1 pn)v 检测到死锁后，回退到上一状态（要进行资源剥夺，检测到死锁后，回退到上一状态（要进行资源剥夺，且需保存以前状态的分配信息），重新分配，若不且需保存以前状态的分配信息），重新分配，若不行，继续回退行，继续回退，v1（北大（北大95）一个）一个OS有有20个进程，竞争使个进程，竞争使用用65个同类资源，申请方式是逐个进行的，一个同类资源，申请方式是逐个进行的，一旦某个进程获得它所需要的全部资源，则立即旦某个进程获得它所需要的全部资源，则立即归还所有资源。每个进程最多使用三个资源。归还所有资源。每个进程最多使用三个资源。若仅考虑这类资源，该系统有无可能产生死锁若仅考虑这类