1、第第3章章 处理机调度与死锁处理机调度与死锁 调度目的：处理机调度的工作是对调度目的：处理机调度的工作是对CPUCPU资源进行合理资源进行合理的分配使用，以提高处理机利用率，并使各用户公平地的分配使用，以提高处理机利用率，并使各用户公平地得到处理机资源得到处理机资源。3.1 3.1 处理机调度基本概念处理机调度基本概念3.1.1 调度类型调度类型 1）低级（短期）调度）低级（短期）调度：确定选择哪个就绪的进程占有确定选择哪个就绪的进程占有CPU，所以也称为，所以也称为处理机调度，进程调度处理机调度，进程调度2）高级（长期、作业）调度：）高级（长期、作业）调度：确定哪些作业从外存调入内存确定哪些
2、作业从外存调入内存作业：作业：（用户）利用计算机进行一次运行所需工作的集合（用户）利用计算机进行一次运行所需工作的集合（比如，编辑、编译，运行等）。要执行一个程序，用户必须比如，编辑、编译，运行等）。要执行一个程序，用户必须先提交一个作业。先提交一个作业。通过批输入设备（卡片、纸带、磁带）通过批输入设备（卡片、纸带、磁带）批处理作业。批处理作业。通过终端启动的作业通过终端启动的作业交互式作业。交互式作业。提交作业方式提交作业方式 ： 注：注： 用户进程在运行过程中，也可能会产生由系统管理的后用户进程在运行过程中，也可能会产生由系统管理的后台作业，比如打印作业。这些作业在条件满足时，由系统调度台
3、作业，比如打印作业。这些作业在条件满足时，由系统调度执行。执行。3 3）中级（中期）调度：）中级（中期）调度：为提高效率，加快进程运行，调节系为提高效率，加快进程运行，调节系统的负荷，统的负荷，有时需要在选择内存中阻塞或就绪的进程暂时放到外存（一有时需要在选择内存中阻塞或就绪的进程暂时放到外存（一般是硬盘），即所谓的般是硬盘），即所谓的挂起挂起。这种内外存的数据交换称为。这种内外存的数据交换称为对对换换。中级调度解决：中级调度解决：在阻塞或就绪的进程中选择哪个（些）进程挂起在阻塞或就绪的进程中选择哪个（些）进程挂起在条件允许下，在外存挂起的进程集合中如何选进程激活在条件允许下，在外存挂起的进程
4、集合中如何选进程激活并调回内存并调回内存外存外存对换对换作业输入作业输入 spooling输入程序输入程序 spooling 作业调度作业调度就就绪绪阻阻塞塞就就绪绪运运行行完完成成阻塞阻塞后后备备作业输出作业输出4）三种调度之间的关系如图）三种调度之间的关系如图低级调度低级调度中级调度中级调度3.1.2 3.1.2 调度队列模型调度队列模型 一、仅有进程调度的调度队列模型一、仅有进程调度的调度队列模型 特点：单就绪、单阻塞队列特点：单就绪、单阻塞队列就就队队 列列绪绪CPU进程调度进程调度进程完成进程完成时间片完时间片完阻阻队队 列列塞塞交互用户交互用户等待事件等待事件事件出现事件出现二、具
5、有高级和低级的调度队列模型二、具有高级和低级的调度队列模型特点特点 ：1)1)具有进程调度、作业调度具有进程调度、作业调度 2)2)根据阻塞原因设置了多个阻塞队列根据阻塞原因设置了多个阻塞队列后后队队 列列备备1阻阻队队 列列塞塞作业调度作业调度就就队队 列列绪绪CPU进程调度进程调度进程完成进程完成时间片完时间片完等待事件等待事件1事件事件1出现出现2阻阻队队 列列塞塞n阻阻队队 列列塞塞等待事件等待事件2等待事件等待事件n事件事件2出现出现事件事件n出现出现三、同时具有三级调度的调度队列模型三、同时具有三级调度的调度队列模型作业调度作业调度就就队队 列列绪绪CPU进程调度进程调度进程完成进
6、程完成时间片完时间片完事件出现事件出现阻阻 塞塞列列、起起 队队挂挂阻阻队队 列列塞塞等待事件等待事件就绪、挂起队列就绪、挂起队列事件出现事件出现挂起挂起中级调度中级调度后后队队 列列备备交互型作业交互型作业批量作业批量作业挂起挂起选择哪种模型应根据系统的规模及目标制定选择哪种模型应根据系统的规模及目标制定3.1.3 3.1.3 选择调度方式和调度算法的若干标准选择调度方式和调度算法的若干标准1、调度目标：、调度目标：1)公平公平确保每个进程获得合理的确保每个进程获得合理的CPU份额份额2)效率效率是百分之百地忙碌是百分之百地忙碌3)响应时间响应时间使交互用户的响应时间尽可能短使交互用户的响应
7、时间尽可能短4)周转时间周转时间使批处理用户等待输出的时间尽可能短使批处理用户等待输出的时间尽可能短5)吞吐量吞吐量使每小时处理的作业数量多使每小时处理的作业数量多以上调度目标有矛盾之处，不可能满足所有情况，取以上调度目标有矛盾之处，不可能满足所有情况，取决于系统设计目标决于系统设计目标2、有关术语及衡量标准、有关术语及衡量标准周转时间周转时间T：批处理系统的一个重要指标。指作业从提交到批处理系统的一个重要指标。指作业从提交到完成（得到结果）所经历的时间。完成（得到结果）所经历的时间。 包括：包括：1）在外存后备队列中等待时间；）在外存后备队列中等待时间；2）CPU上执行时间；上执行时间；3）
8、就绪队列和阻塞队列中等待时间；）就绪队列和阻塞队列中等待时间；4）结果输出等待时间。）结果输出等待时间。周转时间常用以下参数衡量周转时间常用以下参数衡量 （原则上越小越好）（原则上越小越好） 平均周转时间平均周转时间: 带权周转时间带权周转时间 ：niiTnT11nisiiTTnW11 其中其中:Ti/Tsi为第为第i个作业的带权周转时间，个作业的带权周转时间，Tsi系统为第系统为第i个作个作业提供的实际服务时间业提供的实际服务时间响应时间：响应时间：分时系统的一个重要指标。用户输入一个请求分时系统的一个重要指标。用户输入一个请求（如击键）到系统给出首次响应（如屏幕显示）的时间。（如击键）到系
9、统给出首次响应（如屏幕显示）的时间。包括：包括：1 1）从终端的键盘输入的一个请求信息传送到处理机的）从终端的键盘输入的一个请求信息传送到处理机的时间；时间；2 2）处理机对请求的处理时间；）处理机对请求的处理时间；3 3）处理结果送到终端）处理结果送到终端显示器的时间。显示器的时间。吞吐量：吞吐量：批处理系统的一个重要指标。单位时间内所完成的作批处理系统的一个重要指标。单位时间内所完成的作业数。业数。处理机利用率：处理机利用率：大中型主机多用户系统的性能指标，因为系统大中型主机多用户系统的性能指标，因为系统价格昂贵，所以非常重视其价格昂贵，所以非常重视其CPUCPU利用率。利用率。PCPC一
10、般不考虑这个一般不考虑这个指标。指标。各种设备的均衡利用：各种设备的均衡利用：大中型主机多用户系统性能指标。如大中型主机多用户系统性能指标。如CPUCPU繁忙的作业和繁忙的作业和I/OI/O繁忙的作业搭配。对繁忙的作业搭配。对PCPC及实时系统该指及实时系统该指标并不重要。标并不重要。 3. 调度准则 面向用户准则周转时间短；周转时间短；响应时间快；响应时间快；截止时间保证；截止时间保证；优先权准则优先权准则 面向系统的准则系统吞吐量系统吞吐量处理机利用率处理机利用率各类资源的平衡利用各类资源的平衡利用3.2 3.2 调度算法调度算法 一、调度的时机一、调度的时机 调度的时机是与调度方式有关，
11、一般在以下情况下会发生调度的时机是与调度方式有关，一般在以下情况下会发生进程调度：进程调度：（1 1）正在执行的进程正常结束或由于某种错误而终止运行；）正在执行的进程正常结束或由于某种错误而终止运行；（2 2）执行中的进程提出）执行中的进程提出I/OI/O请求，在等待请求，在等待I/OI/O完成前，进程阻塞完成前，进程阻塞，转进程调度；，转进程调度；（3 3）在分时系统中，按照时间片轮转，分给进程的时间片用完）在分时系统中，按照时间片轮转，分给进程的时间片用完时；时； （4 4）按照优先级调度，有更高优先级进程变为就绪时；）按照优先级调度，有更高优先级进程变为就绪时；（5 5）在进程通讯中，执
12、行中的进程执行了某种原语操作，如在进程通讯中，执行中的进程执行了某种原语操作，如P操作、阻塞原语和唤醒原语时，都可能引起进程调度。操作、阻塞原语和唤醒原语时，都可能引起进程调度。二、常用的调度方法二、常用的调度方法1. 1. 先来先服务（先来先服务（FCFSFCFS算法）算法） 按照作业提交或进程变为就绪状态的先后次序，分派按照作业提交或进程变为就绪状态的先后次序，分派CPUCPU；当前作业或进程占用当前作业或进程占用CPUCPU，直到执行完或阻塞，才主动地出让，直到执行完或阻塞，才主动地出让CPUCPU。特点：非常简单，易于实现；但对短作业而言，带权周转时特点：非常简单，易于实现；但对短作业
13、而言，带权周转时间可能太大。间可能太大。按按FCFS原则的进程调度原则的进程调度进程名进程名到达时间到达时间服务时间服务时间开始时开始时间间完成时完成时间间周转时周转时间间带权周带权周转时间转时间A03B26C44D65E823913182037912121.001.172.252.406.000391318特点：特点：比比FCFSFCFS改善了平均周转时间和平均带权周转时间，缩短作业改善了平均周转时间和平均带权周转时间，缩短作业的等待时间，提高了系统的吞吐量；的等待时间，提高了系统的吞吐量；对长作业非常不利，可能长时间得不到执行；对长作业非常不利，可能长时间得不到执行；难以准确估计作业（进程
14、）的执行时间，从而影响调度性能难以准确估计作业（进程）的执行时间，从而影响调度性能2.2.短作业（进程）优先短作业（进程）优先 对执行时间短的作业（进程）优先分派处理机。对执行时间短的作业（进程）优先分派处理机。什么是短作业？什么是短作业？以前没有执行过！以前没有执行过！按什么标准：按什么标准： 时间？时间？程序长度？程序长度？while(1);特点：特点：比比FCFSFCFS改善了平均周转时间和平均带权周转时间，缩短作业改善了平均周转时间和平均带权周转时间，缩短作业的等待时间，提高了系统的吞吐量；的等待时间，提高了系统的吞吐量；对长作业非常不利，可能长时间得不到执行；对长作业非常不利，可能长
15、时间得不到执行；难以准确估计作业（进程）的执行时间，从而影响调度性能难以准确估计作业（进程）的执行时间，从而影响调度性能2.2.短作业（进程）优先短作业（进程）优先 对执行时间短的作业（进程）优先分派处理机。对执行时间短的作业（进程）优先分派处理机。什么是短作业？什么是短作业？ 由用户自己利用由用户自己利用作业控制语言说明程作业控制语言说明程序预计执行时间。序预计执行时间。按非抢占式按非抢占式SJF原则的进程调度原则的进程调度进程名进程名到达时间到达时间服务时间服务时间开始时开始时间间完成时完成时间间周转时周转时间间带权周带权周转时间转时间A03B26C44D65E82031115939152
16、011361114316/311/414/53/2按抢占式按抢占式SJF原则的进程调度原则的进程调度进程名进程名到达时间到达时间服务时间服务时间开始时开始时间间完成时完成时间间周转时周转时间间带权周带权周转时间转时间A03B26C44D65E823. 3. 时间片轮转时间片轮转 主要用于低级调度，是一种主要用于低级调度，是一种最古老、最简单、最公平且最古老、最简单、最公平且使用最广泛使用最广泛的方法。的方法。 将将系统中所有的就绪进程按照系统中所有的就绪进程按照FCFSFCFS原则，排成一个队列原则，排成一个队列。每次调度时将。每次调度时将CPUCPU分派给队首进程，让其执行一个时间片分派给队
17、首进程，让其执行一个时间片。在一个时间片结束时，发生时钟中断。调度程序据此暂停。在一个时间片结束时，发生时钟中断。调度程序据此暂停当前进程的执行，将其送到就绪队列的末尾。（进程可以由当前进程的执行，将其送到就绪队列的末尾。（进程可以由于阻塞或已运行结束，在未用完一个时间片时，主动放弃于阻塞或已运行结束，在未用完一个时间片时，主动放弃CPUCPU）。）。 主要问题：主要问题：如何确定时间片的长短如何确定时间片的长短cpu效率效率=时间片长度时间片长度/(时间片长度时间片长度+调度切换时间调度切换时间) 对一个系统，调度切换时间可近似看成定数。我们可以调对一个系统，调度切换时间可近似看成定数。我们
18、可以调整时间片长度改变整时间片长度改变cpu效率。效率。短：短：比如调度时间需比如调度时间需50ms,50ms,时间片时间片50ms50ms。效率。效率=50%=50%。 用户的一次请求需要多个时间片才能处理完，切换次数增用户的一次请求需要多个时间片才能处理完，切换次数增加。加。长：长：时间片到时间片到500ms500ms，效率，效率=99%=99%。 若有若有1010个进程，这十个用户若几乎同时按下键盘，从第个进程，这十个用户若几乎同时按下键盘，从第1 1个响个响应到他再次轮到运行要等应到他再次轮到运行要等 9 9* *0.5=4.50.5=4.5秒秒远远超出能容忍的远远超出能容忍的时间。时
19、间。 等待时间一般不要超出等待时间一般不要超出1 1秒，因此应该有：秒，因此应该有： (时间片长度时间片长度+调度切换时间调度切换时间)*进程数进程数=1000ms所以：所以：时间片长度时间片长度=1000/进程数进程数-调度切换时间调度切换时间 1000/进程数进程数 对一个分时系统，联机的用户数是变化的。随进程数变化调对一个分时系统，联机的用户数是变化的。随进程数变化调整时间片长度是合理的。但由于进程数的变化几乎是连续不断整时间片长度是合理的。但由于进程数的变化几乎是连续不断的，所以没有必要随着实时的变化，这样系统开销也大。折衷的，所以没有必要随着实时的变化，这样系统开销也大。折衷的办法是
20、：进程数在一个区间范围内用一个时间片，在另一个的办法是：进程数在一个区间范围内用一个时间片，在另一个区间范围内，用另一个时间片。系统可以每间隔一段时间，检区间范围内，用另一个时间片。系统可以每间隔一段时间，检测当前进程数，确定有无必要调整时间片长度。测当前进程数，确定有无必要调整时间片长度。按时间片轮转的进程调度（时间片长为按时间片轮转的进程调度（时间片长为1）进程名进程名到达时间到达时间服务时间服务时间 开始时开始时间间完成时完成时间间周转时周转时间间带权周带权周转时间转时间A03B26C44D65E824 4、优先权调度、优先权调度 前者简单，在实时性要求不高或时间片不很长时可考虑；前者简
21、单，在实时性要求不高或时间片不很长时可考虑；后者适合于实时要求高的场合，但时刻要监视有否更高优后者适合于实时要求高的场合，但时刻要监视有否更高优先权的进程产生。先权的进程产生。1）优先权调度分为：优先权调度分为： 非抢占式：非抢占式：除系统一旦把处理机分配给就绪队列中优先权最高的进除系统一旦把处理机分配给就绪队列中优先权最高的进城后，该进程便一直执行下去，直至完成；或者因发生某件事件使该城后，该进程便一直执行下去，直至完成；或者因发生某件事件使该进程放弃处理机时，系统方可再将处理机重新分配给另一个优先权最进程放弃处理机时，系统方可再将处理机重新分配给另一个优先权最高的进程。高的进程。 抢占方式
22、：抢占方式：系统同样是吧处理机分配给优先权最高的进程，使之执行系统同样是吧处理机分配给优先权最高的进程，使之执行。但在其执行期间，只要有另外一个优先权更高的进程，进程调度程序。但在其执行期间，只要有另外一个优先权更高的进程，进程调度程序就立即停止当前进程的执行，重新将处理机分配给新到的最高优先权进就立即停止当前进程的执行，重新将处理机分配给新到的最高优先权进程。程。抢占方式在实际的操作系统设计中也会有细分：抢占方式在实际的操作系统设计中也会有细分：内核部分可抢占：内核部分可抢占：用户态时可以随时被抢占用户态时可以随时被抢占CPU，但当进程在，但当进程在核心态时则大部分时间都不可以抢用核心态时则
23、大部分时间都不可以抢用CPU，而只在某些时刻（，而只在某些时刻（称为可抢占点，称为可抢占点，Preemption Point），可以抢用），可以抢用CPU。例：。例： UNIX SVR 4。 内核完全不可抢占：内核完全不可抢占：用户态时可以随时被抢占用户态时可以随时被抢占CPU，但当进程，但当进程在核心态时，则完全不可以被抢用在核心态时，则完全不可以被抢用CPU。例：。例：UNIX（SVR 3和和4.3BSD UNIX及其以前的版本）、及其以前的版本）、WINDOWS NT。这些这些OS通通常在系统调用或中断处理时屏蔽大部分中断，系统调用返回或常在系统调用或中断处理时屏蔽大部分中断，系统调用返
24、回或中断返回时再开放大部分中断。中断返回时再开放大部分中断。 完全可抢占或内核完全可抢占：完全可抢占或内核完全可抢占：无论处于用户态还是核心态，无论处于用户态还是核心态，都可以随时被抢占都可以随时被抢占CPU 。例：。例：SUNSUN公司的公司的Solaris 、Windows 2000 / XP。实际上，。实际上，Solaris和和Windows 2000 / XP并不是并不是100%完全可抢占，只是将内核中不可抢占的代码段尽量减少而已。完全可抢占，只是将内核中不可抢占的代码段尽量减少而已。任何任何OS都不可能是都不可能是100%的完全可抢占的。的完全可抢占的。2 2）优先权的类型）优先权的
25、类型静态优先级静态优先级 创建进程时就确定，直到进程终止前都不改变。通常是一个整创建进程时就确定，直到进程终止前都不改变。通常是一个整数。数。 进程类型（系统进程优先级较高）进程类型（系统进程优先级较高） 依据依据 对资源的需求（对对资源的需求（对CPUCPU和内存需求较少的进程，优和内存需求较少的进程，优 先级较高）先级较高） 用户要求（紧迫程度和付费多少）用户要求（紧迫程度和付费多少）动态优先级动态优先级 创建进程时赋予的优先级，在进程运行过程中可以自动改变，创建进程时赋予的优先级，在进程运行过程中可以自动改变，以便获得更好的调度性能（以便获得更好的调度性能（UNIXUNIX中采用）。中采
26、用）。动态优先级的改变原则：动态优先级的改变原则： A A） 在就绪队列中，等待时间延长则优先级提高，从而使优先在就绪队列中，等待时间延长则优先级提高，从而使优先级较低的进程在等待足够的时间后，其优先级得到提高；级较低的进程在等待足够的时间后，其优先级得到提高； B B） 进程每执行一个时间片，就降低其优先级，从而一个进程进程每执行一个时间片，就降低其优先级，从而一个进程持续执行时，其优先级降低到出让持续执行时，其优先级降低到出让CPUCPU。5 5、高响应比优先调度、高响应比优先调度响应比：响应比：R = (R = (等待时间等待时间 + + 要求执行时间要求执行时间) / ) / 要求执行
27、时间要求执行时间是是FCFSFCFS（先来先服务）和（先来先服务）和SJFSJF的折衷：的折衷：作业等待时间相同，服务时间越短，优先权越高作业等待时间相同，服务时间越短，优先权越高-SJF-SJF；要求服务时间相同，等待时间越长，优先权越高要求服务时间相同，等待时间越长，优先权越高-FCFS-FCFS；长；长作业随着等待时间的增加，优先权增加。作业随着等待时间的增加，优先权增加。 6 6、多级队列调度、多级队列调度 使用多个就绪队列，各队列的区别对待，达到综合的调度目使用多个就绪队列，各队列的区别对待，达到综合的调度目标。标。 方法：方法： 根据作业或进程的性质或类型的不同，将就绪队列再分为若
28、根据作业或进程的性质或类型的不同，将就绪队列再分为若干个子队列（如前、后台进程，系统、用户进程等）。干个子队列（如前、后台进程，系统、用户进程等）。 每个作业归入一个队列。每个作业归入一个队列。不同队列可有不同的优先级、时间片不同队列可有不同的优先级、时间片长度、调度策略等；在运行过程中还可改变进程所在队列。长度、调度策略等；在运行过程中还可改变进程所在队列。 7 7、多级反馈队列调度、多级反馈队列调度 时间片轮转和优先级的综合及发展。时间片轮转和优先级的综合及发展。就绪队列就绪队列1 1S1至至CPU就绪队列就绪队列2 2S2至至CPU就绪队列就绪队列3 3S3至至CPU就绪队列就绪队列n
29、nSn至至CPU时间片：时间片：s1s2sn 多个就绪队列，赋予不同的优先级。队列多个就绪队列，赋予不同的优先级。队列1 1的优先级最高。的优先级最高。每个队列执行时间片的长度也不同，规定优先级越低则时间片每个队列执行时间片的长度也不同，规定优先级越低则时间片越长。越长。 新进程进入内存后，先投入队列新进程进入内存后，先投入队列1 1的末尾，按的末尾，按FCFSFCFS算法调算法调度；若一个时间片未完，投入到队列度；若一个时间片未完，投入到队列2 2的末尾，同样按的末尾，同样按FCFSFCFS算算法调度；如此下去，降低到最后的队列。法调度；如此下去，降低到最后的队列。 仅当较高优先级的队列为空
30、，才调度较低优先级的队列仅当较高优先级的队列为空，才调度较低优先级的队列中的进程执行。如果进程执行时有新进程进入较高优先级的中的进程执行。如果进程执行时有新进程进入较高优先级的队列，则抢先执行新进程，并把被抢先的进程投入原队列的队列，则抢先执行新进程，并把被抢先的进程投入原队列的末尾。末尾。8、公平分享调度策略、公平分享调度策略 1986年年Bach提出：按进程组（用户）分配提出：按进程组（用户）分配CPU。以前的做法，按进程分配以前的做法，按进程分配CPU： A用户：用户：1个进程个进程 B用户：用户：6个进程个进程 C用户：用户：3个进程个进程 ，10%的的CPU分额分额 ，60%的的CP
31、U分额分额 ，30%的的CPU分额分额现在现在 ：每个用户都按：每个用户都按1/3的比例分配的比例分配CPU A用户的每个进程，用户的每个进程，1/3的的CPU分额分额 B用户的每个进程，用户的每个进程，1/18的的CPU分额分额 C用户的每个进程，用户的每个进程，1/9的的CPU分额分额 定义：假如在一个进程集合中的每个进程都在等待只能由定义：假如在一个进程集合中的每个进程都在等待只能由该集合中的其它一个进程才能引发的事件，这种状态被看成该集合中的其它一个进程才能引发的事件，这种状态被看成死死锁锁。3.5 3.5 死锁的原因和必要条件死锁的原因和必要条件1 1、产生死锁的原因、产生死锁的原因
32、 A A）竞争不可剥夺资源）竞争不可剥夺资源 典型的打印机，磁带机等。典型的打印机，磁带机等。3.5.1 死锁产生的原因死锁产生的原因p2rel(r1)p2rel(r2)p2req(r2)p2req(r1) p1req(r1) p1req(r2) p1rel (r1) p1rel (r2)死锁区死锁区p1p2tt当进程推进到死锁区，进程必死当进程推进到死锁区，进程必死可通过增加资源来解决死锁，比如有两个可通过增加资源来解决死锁，比如有两个r1和两个和两个r2资源就不资源就不会发生死锁会发生死锁,但现实中是不可取的。但现实中是不可取的。资源不够一定死锁吗？资源不够一定死锁吗？ p1req(r1)
33、 p1req(r2) p1rel (r1) p1rel (r2)p1p2p2rel(r1)p2rel(r2)p2req(r2)p2req(r1)进程没有推进到死锁区，不会发生死锁进程没有推进到死锁区，不会发生死锁tt 定义：假如在一个进程集合中的每个进程都在等待只能由定义：假如在一个进程集合中的每个进程都在等待只能由该集合中的其它一个进程才能引发的事件，这种状态被看成该集合中的其它一个进程才能引发的事件，这种状态被看成死死锁锁。产生死锁的原因：产生死锁的原因： A A）竞争不可剥夺资源）竞争不可剥夺资源 典型的打印机，磁带机等。典型的打印机，磁带机等。B)B)进程推进顺序不当进程推进顺序不当3
34、.5.2 3.5.2 产生死锁的必要条件产生死锁的必要条件 Coffman Coffman等人在等人在19711971年总结了年总结了4 4个死锁的必要条件个死锁的必要条件只有只有4 4个条件都满足时，才会出现死锁。个条件都满足时，才会出现死锁。(1) (1) 互斥：一个资源要么分配给一个进程，要么空闲；互斥：一个资源要么分配给一个进程，要么空闲； (2) (2) 请求和保持：进程可请求其余资源，但不主动释放已请求和保持：进程可请求其余资源，但不主动释放已 经占用的资源（部分分配）经占用的资源（部分分配）(3) (3) 不剥夺：进程已经占用的资源，不会被强制剥夺不剥夺：进程已经占用的资源，不会
35、被强制剥夺(4) (4) 环路等待：系统一定有两个或两个以上的进程组成的环路等待：系统一定有两个或两个以上的进程组成的一条环路，该环路中的每个进程都在等待相邻进程正占用的一条环路，该环路中的每个进程都在等待相邻进程正占用的资源。资源。3.5.3 3.5.3 死锁的解决方法死锁的解决方法一、鸵鸟策略（置之不理）鸵鸟策略（置之不理） 解决死锁的最简单方法就是鸵鸟算法。即像鸵鸟一样解决死锁的最简单方法就是鸵鸟算法。即像鸵鸟一样，当遇到危险时，将头埋进沙子里，假装毫无问题。，当遇到危险时，将头埋进沙子里，假装毫无问题。 当死锁在计算机中很少出现时，比如说每五年或更长时当死锁在计算机中很少出现时，比如说
36、每五年或更长时间才出现一次时，人们就不必花费更多的精力去解决它，间才出现一次时，人们就不必花费更多的精力去解决它，而是采用类似鸵鸟一样的办法忽略它。而是采用类似鸵鸟一样的办法忽略它。 以以UNIXUNIX系统为例，它潜在地存在死锁，但它并不花功系统为例，它潜在地存在死锁，但它并不花功夫去检测和解除死锁，而是忽略不去理它。夫去检测和解除死锁，而是忽略不去理它。 如果死锁不花什么代价就能解决，那么什么问题也没有。如果死锁不花什么代价就能解决，那么什么问题也没有。但实际是代价很大，常会给进程带来很多不便的限制。所以，但实际是代价很大，常会给进程带来很多不便的限制。所以，需要在方便性和正确性之间进行折
37、衷，要充分考虑哪一个更重需要在方便性和正确性之间进行折衷，要充分考虑哪一个更重要，对象是谁，一般很难发现一般性的解决办法。要，对象是谁，一般很难发现一般性的解决办法。二、预防死锁 预防死锁是一种简单直观的方法，通过预防死锁是一种简单直观的方法，通过预先预先设置某些设置某些限制条件，去破坏产生死锁的四个必要条件之一或几个条限制条件，去破坏产生死锁的四个必要条件之一或几个条件，来预防死锁的发生。由于施加的条件过于严格，会导件，来预防死锁的发生。由于施加的条件过于严格，会导致系统资源利用率和系统吞吐量降低。致系统资源利用率和系统吞吐量降低。三、避免死锁 避免死锁指的是在资源动态分配过程中，采用某种方
38、避免死锁指的是在资源动态分配过程中，采用某种方法去防止系统进入不安全的状态，从而避免发生死锁。需法去防止系统进入不安全的状态，从而避免发生死锁。需要事先加以较弱的限制条件。要事先加以较弱的限制条件。目的地目的地危险危险要想过去，必须保证在通过的整个过程中肯定不会要想过去，必须保证在通过的整个过程中肯定不会发生危险！发生危险！保守主义者！保守主义者！目的地目的地危险危险要想过去，那么小心一点，时刻探测下一步是不是要想过去，那么小心一点，时刻探测下一步是不是会遇到危险！会遇到危险！积极者！积极者！目的地目的地只要想过去，就过去，不管有没有危险，碰到危险只要想过去，就过去，不管有没有危险，碰到危险就
39、完蛋！就完蛋！蛮干者！蛮干者！过？过？彻底完彻底完蛋！蛋！过！过！四、检测死锁 检测死锁的功能是利用系统所设置的检测机制，及时检测死锁的功能是利用系统所设置的检测机制，及时的检测出死锁的发生，并精确地确定与死锁有关的进程和的检测出死锁的发生，并精确地确定与死锁有关的进程和资源。资源。五、解除死锁 解除死锁：当检测到系统已经发生了死锁时，必须将解除死锁：当检测到系统已经发生了死锁时，必须将进城从死锁状态中解脱出来。通常会牺牲部分系统利用率进城从死锁状态中解脱出来。通常会牺牲部分系统利用率，甚至会牺牲部分进程。，甚至会牺牲部分进程。3.6 死锁的预防死锁的预防 预防：是采用某种策略，限制并发进程对
40、资源的请求预防：是采用某种策略，限制并发进程对资源的请求，使系统在任何时刻都不满足死锁的必要条件。，使系统在任何时刻都不满足死锁的必要条件。 1）预先静态分配：）预先静态分配： 预先分配所需全部所需资源，这样可保证不等待资源；预先分配所需全部所需资源，这样可保证不等待资源；降低了对资源的利用率（资源分配了可能不用）降低了对资源的利用率（资源分配了可能不用）预先要知道所需资源；预先要知道所需资源；2）资源强制变为）资源强制变为“可剥夺可剥夺”的的 在申请资源得不到时，占用资源也释放。在申请资源得不到时，占用资源也释放。实用中可行实用中可行吗？吗？3）破坏）破坏“环路等待环路等待”条件条件 有序资
41、源使用法：每个独享资源都给一个唯一序号，使用有序资源使用法：每个独享资源都给一个唯一序号，使用只能按序号申请资源，只能按序号申请资源，三、利用银行家算法避免死锁三、利用银行家算法避免死锁1 1、银行家算法思想、银行家算法思想 避免死锁的算法是避免死锁的算法是DijkstraDijkstra在在19651965年提出的，被称为银行年提出的，被称为银行家算法。家算法。 这个算法是用来模拟一个小城镇的银行家为一批顾客贷款这个算法是用来模拟一个小城镇的银行家为一批顾客贷款的问题。的问题。 例：例： 有四个顾客：有四个顾客：A A，B B，C C，D D，每个顾客提出的最大贷，每个顾客提出的最大贷款数量
42、分别为款数量分别为6 6、5 5、4 4、7 7。银行家知道不是所有顾客都马上。银行家知道不是所有顾客都马上需要其全部贷款（需要其全部贷款（6+5+4+7=226+5+4+7=22）。）。因此，他只保留因此，他只保留1010个单位数量个单位数量( (而不是全部而不是全部2222个单位个单位) )为这些为这些顾客服务。顾客服务。顾顾客客拥拥有有最大最大要求要求A06B05C04D07顾顾客客拥拥有有最大最大要求要求A16B15C24D47顾顾客客拥拥有有最最大大要要求求A16B25C24D47银行家拥有量银行家拥有量:10:10当前剩余量当前剩余量: 2: 2当当B B请求请求1 1个时，个时，
43、当前剩余量当前剩余量:1 :1 顾顾客客拥拥有有最最大大要要求求A16B25C24D47当前剩余量当前剩余量:1 :1 现在银行家要破产了，剩余的现在银行家要破产了，剩余的资金贷给谁都不够，因此项目不资金贷给谁都不够，因此项目不能完成，银行家不能收回贷款。能完成，银行家不能收回贷款。错误发生在最后贷款给错误发生在最后贷款给B的的1个亿上个亿上顾顾客客拥拥有有最大最大要求要求A16B15C24D47当前剩余量当前剩余量: 2: 2B B请求：不贷款请求：不贷款C C请求请求2 2个亿：可以贷款个亿：可以贷款 C完成项目后，还出完成项目后，还出4，这个，这个4银行银行家下次可贷给家下次可贷给B，也
44、可贷给，也可贷给D其中的其中的3，不管如何处理，不管如何处理，B或或D都能完成归还都能完成归还5或归还或归还7；最后贷给；最后贷给A所需资金所需资金5。 最终，最终，A、B、C、D都完成了项目，都完成了项目，银行家得到了贷款利润。银行家得到了贷款利润。 存在的安全序列是：存在的安全序列是：C、B、D、A或或C、D、B、A2. 2. 银行家算法银行家算法假定顾客分成若干次借款；并在第一次借款时，假定顾客分成若干次借款；并在第一次借款时，能说明他的最大借款额。能说明他的最大借款额。具体算法：具体算法： 顾客的借款操作依次顺序进行，直到全部操作完成；顾客的借款操作依次顺序进行，直到全部操作完成； 银
45、行家对当前顾客的借款操作进行判断，以确定其银行家对当前顾客的借款操作进行判断，以确定其安全性（能否支持顾客借款，直到全部归还）；安全性（能否支持顾客借款，直到全部归还）； 安全时，贷款；否则，暂不贷款。安全时，贷款；否则，暂不贷款。 银行家算法可陈述如下：银行家算法可陈述如下： 当一个进程提出资源请求时，假定分配给它，并检查系当一个进程提出资源请求时，假定分配给它，并检查系统因此是否仍处于安全状态。如果安全，则满足它的请求。统因此是否仍处于安全状态。如果安全，则满足它的请求。否则，推迟它的请求。否则，推迟它的请求。 为了检查状态是否安全，银行家要检查他是否还有为了检查状态是否安全，银行家要检查
46、他是否还有足够资源满足某一个顾客。如果能满足，这个顾客就能足够资源满足某一个顾客。如果能满足，这个顾客就能很快将贷款归还。重复这一检查过程。如果所有顾客的很快将贷款归还。重复这一检查过程。如果所有顾客的贷款都能满足，系统的这个状态是安全的。可实施实际贷款都能满足，系统的这个状态是安全的。可实施实际的分配。如果不安全，则让其阻塞等待。的分配。如果不安全，则让其阻塞等待。 上述算法可简单归纳如下：上述算法可简单归纳如下：当某进程请求分配资源当某进程请求分配资源时，系统假定先分配给它，之后若能找到一个进程完成时，系统假定先分配给它，之后若能找到一个进程完成序列，说明系统是安全的，可进行实际分配；否则
47、，让序列，说明系统是安全的，可进行实际分配；否则，让申请者等待。申请者等待。3、算法描述：、算法描述： 设有设有n个客户，个客户，max i:第第i个客户的资金总需求数个客户的资金总需求数 alloc i:第第i个客户已得到的资金数，初值为个客户已得到的资金数，初值为0 needi:第第i个客户还需要的资金数，初值为个客户还需要的资金数，初值为maxi (1=i=n)av:银行家目前可以贷出的资金银行家目前可以贷出的资金,开始为总资本开始为总资本三者关系：三者关系： maxi=alloci+needirequesti:第第i个客户当前需要的资金数个客户当前需要的资金数（必需有：（必需有：req
48、uesti=needi)if(requesti=av & requesti=needi) av-=requesti; alloci+=requesti; needi-=requesti; if(check() )资金分配处理；资金分配处理；else 拒绝分配，恢复拒绝分配，恢复av,needi,alloci的值的值;check:安全性检查安全性检查:work=av;finishi=False; i=1,2,nwhile(1) flag=1; for(k=1;k=n;k+) if(finishk=False & needk avi i=1,2,.m代表第代表第i个银行家当前能提供的资金个银行家当
49、前能提供的资金原来的一维数组扩充为二维原来的一维数组扩充为二维(n*m)，如：，如：alloci(i=1,2,.n) :代表第代表第i个客户已得到的资金个客户已得到的资金- alloci,j (i=1,2, n；j=1,2,.m): 代表第代表第i个客户在第个客户在第j个银行家处已得到的资金个银行家处已得到的资金 其它类推。其它类推。 5、存在的问题：要求事先说明最大资源要求，在现实中很困、存在的问题：要求事先说明最大资源要求，在现实中很困难难系统中有5个进程（p0,P1,P2,P3,P4）和三类资源(A,B,C)，各种资源的数量分别为10，5，7，在T0时刻资源分配的情况如下表。Max(最多
50、)A B CALLOC(已分配)A B CNEED(还需)A B CAVA(剩余)A B Cp07 5 30 1 0 7 4 33 3 2P13 2 2P2P3p42 0 01 2 29 0 23 0 26 0 00 1 12 1 12 2 24 3 30 0 24 3 1T0时刻是否安全？找到一个能够把所有进程执行完成的序列即可说明其安全性。Max(最多)A B CALLOC(已分配)A B CNEED(还需)A B CAVA(剩余)A B Cp07 5 30 1 0 7 4 33 3 2P13 2 2P2P3p42 0 01 2 29 0 23 0 26 0 00 1 12 1 12 2
