1、第三章第三章 处理机调度与死锁处理机调度与死锁第一节第一节处理机调度的层次处理机调度的层次第二节第二节调度队列模型和调度准则调度队列模型和调度准则第三节第三节 调度算法调度算法第四节第四节 实时调度实时调度第五节第五节产生死锁的原因和必要条件产生死锁的原因和必要条件第六节第六节 预防死锁的方法预防死锁的方法第七节第七节 死锁的检测和解除死锁的检测和解除13.1处理机调度的层次处理机调度的层次高级调度高级调度低级调度低级调度中级调度中级调度23.1.1、高级调度、高级调度高级调度高级调度（作业调度（作业调度/长程调度）长程调度）l决定把外存上处于后备队列中的哪些作业调入内决定把外存上处于后备队列
2、中的哪些作业调入内存。存。l调度对象：作业调度对象：作业1、作业和作业步、作业和作业步l作业：程序+数据+作业说明书l作业步：作业运行期间的每个加工步骤例如：编译例如：编译连结装配连结装配运行运行32、作业控制块、作业控制块（JCB）lJCB：保存了系统对作业进行管理和调度所需的保存了系统对作业进行管理和调度所需的全部信息。作业在系统中存在的全部信息。作业在系统中存在的标志标志。lJCB包含的内容有：包含的内容有：作业标识、用户名称、用户作业标识、用户名称、用户账号、作业类型、作业状态、调度信息、资源需账号、作业类型、作业状态、调度信息、资源需求、时间信息、资源使用情况等。求、时间信息、资源使
3、用情况等。lJCB的创建和回收的创建和回收43、高级调度（作业、高级调度（作业/长程长程/接纳调度）接纳调度）l概念：概念：决定把外存上处于后备队列中的哪些作业决定把外存上处于后备队列中的哪些作业调入内存，并为它们创建进程、分配必要的资源，调入内存，并为它们创建进程、分配必要的资源，准备执行。准备执行。l多用于批处理系统多用于批处理系统l每次调度时要考虑：每次调度时要考虑：l(1)接纳多少作业：取决于多道程序度接纳多少作业：取决于多道程序度l(2)接纳哪些作业：取决于调度算法接纳哪些作业：取决于调度算法l作业调度运行频率低，几分钟一次作业调度运行频率低，几分钟一次系统规模系统规模运行速度运行速
4、度5低级调度低级调度（进程（进程/短程调度）短程调度）l决定就绪队列中的哪个进程应获得处理机，然后再决定就绪队列中的哪个进程应获得处理机，然后再由分派程序执行把处理机分配给该进程的具体操作由分派程序执行把处理机分配给该进程的具体操作是是最基本最基本的调度，在三种类型的的调度，在三种类型的OS中都必须配置中都必须配置3.1.2、低级调度、低级调度1、低级调度的功能、低级调度的功能l保存处理机的现场信息保存处理机的现场信息l按照某种算法选取进程按照某种算法选取进程l把处理机分配给进程把处理机分配给进程62、进程调度中的三个基本机制、进程调度中的三个基本机制l排队器排队器l分派器（分派程序）分派器（
5、分派程序）l上下文切换机制上下文切换机制3、进程调度方式、进程调度方式l非抢占方式非抢占方式l抢占方式抢占方式71）非抢占方式：）非抢占方式：l一旦进程获得处理机，则一直执行，直到该进程完一旦进程获得处理机，则一直执行，直到该进程完成或被阻塞成或被阻塞l此方式下，可能此方式下，可能引起进程调度的因素引起进程调度的因素：（1）正在执行的进程执行完毕，或因发生某事件不）正在执行的进程执行完毕，或因发生某事件不能再继续执行能再继续执行（2）执行中的进程因提出）执行中的进程因提出I/O请求而暂停执行请求而暂停执行（3）在进程通信或同步过程中执行了某原语，）在进程通信或同步过程中执行了某原语，P操操作等
6、作等l优点：优点：简单、系统开销小，适合大多数批处理系统简单、系统开销小，适合大多数批处理系统l缺点：缺点：无法满足紧急任务的需要，不适合实时系统无法满足紧急任务的需要，不适合实时系统82）抢占方式：）抢占方式：l允许调度程序根据某原则，暂停正在执行的进程，允许调度程序根据某原则，暂停正在执行的进程，将处理机重新分配将处理机重新分配抢占原则：抢占原则：l优先权原则优先权原则 就绪的高优先权进程有权抢占低优先权进程的就绪的高优先权进程有权抢占低优先权进程的CPUl短作业优先原则短作业优先原则 就绪的短作业就绪的短作业(进程进程)有权抢占长作业有权抢占长作业(进程进程)的的CPUl时间片原则时间片
7、原则 一个时间片用完后，系统重新进行进程调度一个时间片用完后，系统重新进行进程调度9中级调度（中程调度）中级调度（中程调度）l目的：目的：提高内存利用率和系统吞吐量提高内存利用率和系统吞吐量l按一定的算法将外存上已具备运行条件的挂起进按一定的算法将外存上已具备运行条件的挂起进程换入内存，挂到就绪队列上，准备执行；而将程换入内存，挂到就绪队列上，准备执行；而将内存中处于阻塞状态的某些进程换出至外存。内存中处于阻塞状态的某些进程换出至外存。3.1.3、中级调度、中级调度10调度队列模型调度队列模型选择调度方式和调度算法的若干准则选择调度方式和调度算法的若干准则3.2、调度队列模型、调度队列模型11
8、3.2.1、调度队列模型、调度队列模型仅具有进程调度的调度队列模型仅具有进程调度的调度队列模型就就绪绪队队列列阻阻塞塞队队列列CPU时间片完时间片完交互用户交互用户进程调度进程调度进程完成进程完成等待事件等待事件事件发生事件发生具有高、低两级调度的调度队列模型具有高、低两级调度的调度队列模型就就绪绪队队列列阻阻塞塞队队列列CPU时间片完时间片完作业作业调度调度进程调度进程调度进程完成进程完成等待事件等待事件1阻阻塞塞队队列列阻阻塞塞队队列列等待事件等待事件2等待事件等待事件n事件事件1发生发生事件事件2发生发生事件事件n发生发生后后备备队队列列具有高、低、中三级调度的调度队列模型具有高、低、中
9、三级调度的调度队列模型就就 绪绪 队队 列列绪绪就就、挂挂 起起 队队 列列CPU时间片完时间片完作业作业调度调度进程调度进程调度进程完成进程完成事件出现事件出现阻阻 塞塞 队队 列列挂起挂起等待事件等待事件中级中级调度调度事件发生事件发生后后 备备 队队 列列塞塞阻阻、挂挂 起起 队队 列列挂起挂起123.2.2、选择调度方式和算法的选择准则、选择调度方式和算法的选择准则1、面向用户的准则、面向用户的准则l（1）周转时间短）周转时间短评价批处理系统评价批处理系统 周转时间：周转时间：是指从作业被提交系统开始，到作业是指从作业被提交系统开始，到作业完成为止的这段时间间隔。完成为止的这段时间间隔
10、。包括四部分时间：包括四部分时间：1）等待作业调度时间）等待作业调度时间2）等待进程调度时间）等待进程调度时间3）执行时间）执行时间4）进程等待）进程等待I/O操作完成时间操作完成时间13平均周转时间：平均周转时间：niTinT11带权周转时间：带权周转时间：TsTW 周转时间周转时间服务时间服务时间niTsTinW11平均带权周转时间：平均带权周转时间：14（2）响应时间快）响应时间快评价分时系统评价分时系统响应时间：响应时间：从用户通过键盘提交一个请求开始直从用户通过键盘提交一个请求开始直至系统首次产生响应为止。至系统首次产生响应为止。包括三部分时间：包括三部分时间：1）从键盘输入的请求信
11、息传送到处理机的时间）从键盘输入的请求信息传送到处理机的时间2）处理时间）处理时间3）响应信息回送终端的时间）响应信息回送终端的时间15（3）截止时间保证）截止时间保证评价实时系统评价实时系统截止时间：截止时间：任务必须开始执行的最迟时间，任务必须开始执行的最迟时间，或必须完成的最迟时间。或必须完成的最迟时间。（4）优先权准则）优先权准则三种系统中皆适用三种系统中皆适用162、面向系统的准则、面向系统的准则l系统吞吐量高系统吞吐量高评价批处理系统评价批处理系统l处理机利用率好处理机利用率好针对大中型系统针对大中型系统l各类资源的平衡利用各类资源的平衡利用对大中型系统对大中型系统173.3调度算
12、法调度算法先来先服务和短作业（进程）优先调度先来先服务和短作业（进程）优先调度算法算法高优先权先调度算法高优先权先调度算法基于时间片的轮转调度算法基于时间片的轮转调度算法183.2.1、先来先服务和短作业（进程）优先先来先服务和短作业（进程）优先调度算法调度算法1、先来先服务（、先来先服务（FCFS）调度算法）调度算法可用于作业调度和进程调度可用于作业调度和进程调度用于作业调度：用于作业调度：l每次从后备作业队列中选择最先进入的作业，将每次从后备作业队列中选择最先进入的作业，将它们调入内存，为它们分配资源、创建进程，然它们调入内存，为它们分配资源、创建进程，然后挂到就绪进程队列上。后挂到就绪进
13、程队列上。19用于进程调度：用于进程调度：l每次从就绪进程队列中选择最先进入的进程，为每次从就绪进程队列中选择最先进入的进程，为之分配处理机，使之投入运行。之分配处理机，使之投入运行。l直到运行完成进程才会让出处理机直到运行完成进程才会让出处理机-非抢占式。非抢占式。l有利于长作业，而不利于短作业。有利于长作业，而不利于短作业。20进程进程名名到达到达时间时间服务服务时间时间开始执开始执行时间行时间完成完成时间时间周转周转时间时间带权周带权周转时间转时间A010111B110011011001C21101102100100D31001022021991.99性能评价：性能评价：l周转时间周转时
14、间 =完成时间完成时间 到达时间到达时间l带权周转时间带权周转时间 =周转时间周转时间/服务（运行）时间服务（运行）时间212、短作业、短作业/进程优先（进程优先（SJF/SPF）短作业优先（短作业优先（SJF）l从后备队列中选择估计运行时间最短的作业，调从后备队列中选择估计运行时间最短的作业，调入内存运行。入内存运行。短进程优先（短进程优先（SPF）l从就绪队列中选出估计运行时间最短的进程，将从就绪队列中选出估计运行时间最短的进程，将处理机分配给它，使它立即执行。处理机分配给它，使它立即执行。l直到运行完成进程才会让出处理机直到运行完成进程才会让出处理机-非抢占式。非抢占式。缺点：缺点：l对
15、长作业不利，有可能长期不被调度；对长作业不利，有可能长期不被调度；l完全没考虑作业的紧迫程度（某些特殊的）；完全没考虑作业的紧迫程度（某些特殊的）；l用户做出的估计时间带有很大的主观性。用户做出的估计时间带有很大的主观性。222.259133.5141844E3.116182101252C2.678926731B1.5365.5111423D2.11带权周转时间带权周转时间84周转时间周转时间4完成时间完成时间FJS2.81带权周转时间带权周转时间94周转时间周转时间4完成时间完成时间FCFS4服务时间服务时间0到达时间到达时间平均平均A进程名进程名 作作调调业业度度情情算算况况法法l周转时间
16、周转时间 =完成时间完成时间 到达时间到达时间l带权周转时间带权周转时间 =周转时间周转时间/服务时间服务时间233.3.2、高优先权先调度算法、高优先权先调度算法既能用于作业调度，也可用于进程调度。既能用于作业调度，也可用于进程调度。作业调度：从后备队列中选择若干个优先权最高的作业调度：从后备队列中选择若干个优先权最高的作业装入内存。作业装入内存。进程调度：把处理机分配给就绪队列中优先权最高进程调度：把处理机分配给就绪队列中优先权最高的进程的进程两种占用两种占用CPU的方式：非抢占式优先权算法的方式：非抢占式优先权算法抢占式优先权算法抢占式优先权算法1、优先权调度算法的类型、优先权调度算法的
17、类型24非抢占式优先权算法非抢占式优先权算法l系统一旦把处理机分配给就绪队列中优先权最高系统一旦把处理机分配给就绪队列中优先权最高的进程后，该进程就一直执行下去，直至完成；的进程后，该进程就一直执行下去，直至完成；或因发生某事件使该进程放弃处理机时，系统方或因发生某事件使该进程放弃处理机时，系统方可再将处理机重新分配给另一优先权最高的进程。可再将处理机重新分配给另一优先权最高的进程。l主要用于批处理系统主要用于批处理系统25抢占式优先权算法抢占式优先权算法l新的就绪进程新的就绪进程i，优先权，优先权Pi。正在执行的进程。正在执行的进程j，优，优先权先权Pj。若。若PiPj，做进程切换。新进程做
18、进程切换。新进程i执行。执行。l优点：优点：能更好的满足紧迫作业的要求。主要用于能更好的满足紧迫作业的要求。主要用于比较严格的实时系统。比较严格的实时系统。262、优先权的类型、优先权的类型 1）静态优先权）静态优先权 在进程创建时确定的，在进程整个运行期间保持不变在进程创建时确定的，在进程整个运行期间保持不变优先权优先权利用某一范围的利用某一范围的整数整数来表示，该整数称为优来表示，该整数称为优先数。如：先数。如：07，0255确定优先权的依据：确定优先权的依据：（1）进程类型）进程类型（2）进程对资源的需求）进程对资源的需求（3）用户要求）用户要求27注：规定优先数越小，其优先权越高注：规
19、定优先数越小，其优先权越高4/348334C15/81517482B119118D带权周转时间带权周转时间周转时间周转时间155完成时间完成时间2优先权优先权非抢占式优非抢占式优先权算法先权算法5服务时间服务时间0到达时间到达时间A进程名进程名 作作调调业业度度情情算算况况法法平均平均6.251.3例：非抢占式优先权算法例：非抢占式优先权算法28t(等待等待)优先权优先权t(运行运行)优先权优先权l2)动态优先权动态优先权在进程创建时创立的优先权，可随进程的推进或等待在进程创建时创立的优先权，可随进程的推进或等待时间的增加而改变。如等待时间长，优先权升高。时间的增加而改变。如等待时间长，优先权
20、升高。29等待时间等待时间+要求服务时间要求服务时间优先权优先权=-要求服务时间要求服务时间等待时间等待时间+要求服务时间要求服务时间响应时间响应时间响应比响应比(Rp)=-=-要求服务时间要求服务时间要求服务时间要求服务时间3、高响应比优先调度算法、高响应比优先调度算法(HRRN)l为每个进程引入动态优先权，随着等待时间增为每个进程引入动态优先权，随着等待时间增加优先权提高。加优先权提高。优点：优点：等待时间相同，短作业优先权高等待时间相同，短作业优先权高(即即SPF)要求服务时间相同，等待时间长，优先权高要求服务时间相同，等待时间长，优先权高(即即FCFS)对于长作业，在等待足够时间后，可
21、获得处理机对于长作业，在等待足够时间后，可获得处理机303.571528E2.2591344C1.177962B2.8142056D2.141带权周转时间带权周转时间83周转时间周转时间3完成时间完成时间3服务时间服务时间0到达时间到达时间平均平均A进程名进程名 作作调调业业度度情情算算况况法法RC1+(9-4)/4=2.25RD1+(9-6)/5=1.6RE1+(9-8)/2=1.5RD1+(13-6)/5=2.4RE1+(13-8)/2=3.5执行顺序：执行顺序：ABCEDHRRN（R大，大，优先权高优先权高）313.3.3、基于时间片的轮转调度算法、基于时间片的轮转调度算法1、时间片轮转
22、法、时间片轮转法1）基本原理）基本原理系统将所有的就绪进程按系统将所有的就绪进程按FIFO原则排成一个队原则排成一个队列，将列，将CPU分配给分配给队首队首进程，执行进程，执行一个时间片一个时间片。在时间片内进程未完，则插入在时间片内进程未完，则插入就绪队列未尾就绪队列未尾，CPU交给下一个进程。交给下一个进程。2）时间片大小的确定）时间片大小的确定时间片略大于一次典型的交互所需要的时间。时间片略大于一次典型的交互所需要的时间。323.3313173.33131744E2.259113.5141642C2673.67111231B5101336923D带权周转时间带权周转时间2.58.4周转时
23、间周转时间144完成时间完成时间RRq=4带权周转时间带权周转时间3.4611.8周转时间周转时间3.751515完成时间完成时间RRq=14服务时间服务时间0到达时间到达时间平均平均A进程名进程名 作作调调业业度度情情算算况况法法l周转时间周转时间 =完成时间完成时间 到达时间到达时间l带权周转时间带权周转时间 =周转时间周转时间/服务时间服务时间332、多级反馈队列调度算法、多级反馈队列调度算法 原理：原理：l设置多个就绪队列设置多个就绪队列，并为各个队列赋予不同的优，并为各个队列赋予不同的优先级和不同长度的时间片；先级和不同长度的时间片；l新创建的进程新创建的进程挂到第一优先级的队列后，
24、然后按挂到第一优先级的队列后，然后按 FCFS 原则排队等待调度。当轮到其执行时，如原则排队等待调度。当轮到其执行时，如它能在时间片内完成，便撤离系统；如果不能完它能在时间片内完成，便撤离系统；如果不能完成，便被挂入第二级队列后，成，便被挂入第二级队列后，最后一级最后一级队队列采用列采用时间片轮转法时间片轮转法；l仅当第一级队列空闲时仅当第一级队列空闲时，调度程序才调度第二级，调度程序才调度第二级队列中的进程运行，依次类推队列中的进程运行，依次类推；新进程可抢；新进程可抢占低级进程的处理机。占低级进程的处理机。34多级反馈队列调度算法示意图多级反馈队列调度算法示意图CPU时间时间片完片完进程进
25、程调度调度进程完成进程完成就就绪绪队队列列一一就就绪绪队队列列二二就就绪绪队队列列三三就就绪绪队队列列 n时间时间片完片完时间时间片完片完35就就级级1绪绪 队队 列列空空就就级级2绪绪 队队 列列就就级级3绪绪 队队 列列运行运行等待等待12354时间片时间片小小大大优先级优先级高高低低36多级反馈队列调度算法的性能多级反馈队列调度算法的性能 多级反馈队列调度算法能较好地满足各种类型用多级反馈队列调度算法能较好地满足各种类型用户（进程）的需要：户（进程）的需要：l终端（交互）型作业用户终端（交互）型作业用户l短批处理作业用户短批处理作业用户l长批处理作业用户长批处理作业用户373.3.4、基
26、于公平原则的调度算法、基于公平原则的调度算法1、保证调度算法、保证调度算法如果系统中有如果系统中有n个相同类型的进程同时运行，保个相同类型的进程同时运行，保证每个进程都获得相同的处理机时间证每个进程都获得相同的处理机时间1/n。2、公平分享调度算法、公平分享调度算法使所有用户能获得相同的处理机时间。使所有用户能获得相同的处理机时间。383.4 实时调度实现实时调度的基本概念和条件实时调度算法的分类常见的几种实时调度算法391.实时调度实时调度是为了完成实时处理任务而分配处理机是为了完成实时处理任务而分配处理机的调度方法。的调度方法。2.2.硬实时任务要求计算机系统必须在用户给定的硬实时任务要求
27、计算机系统必须在用户给定的时时限内限内完成完成 3.3.软实时任务允许计算机系统在用户给定的软实时任务允许计算机系统在用户给定的时限左时限左右右处理完毕。处理完毕。提供更详细的调度信息：提供更详细的调度信息：就绪时间、开始截止时间或完成截止时间、处理时间就绪时间、开始截止时间或完成截止时间、处理时间、资源要求、优先级等；、资源要求、优先级等；含有硬实时任务的实时系统中，广泛采用基于优先级含有硬实时任务的实时系统中，广泛采用基于优先级的抢占式调度策略的抢占式调度策略40l实时调度算法分类：实时调度算法分类：n非抢占式轮转调度算法：非抢占式轮转调度算法：只适用于一般实时信息处理系统只适用于一般实时
28、信息处理系统n非抢占式优先级调度算法：非抢占式优先级调度算法：优先级最高的实时任务排在就优先级最高的实时任务排在就绪队列队首，当前任务终止或完成后才被调度。绪队列队首，当前任务终止或完成后才被调度。n 基于时钟中断抢占式优先级调度算法：基于时钟中断抢占式优先级调度算法：新到的实时任务新到的实时任务的优先级高于当前任务时，并不立即抢占的优先级高于当前任务时，并不立即抢占CPUCPU，而是等到时，而是等到时钟中断到来，才进行切换。用于大多数的实时系统中。钟中断到来，才进行切换。用于大多数的实时系统中。n 立即抢占的优先级调度算法：立即抢占的优先级调度算法：这种算法适用于实时要求这种算法适用于实时要
29、求比较严格的实时控制系统。比较严格的实时控制系统。41常用的几种实时调度算法常用的几种实时调度算法1、最早截止时间优先算法（、最早截止时间优先算法（EDF）该算法根据任务的该算法根据任务的开始截止时间开始截止时间来确定任务的优先来确定任务的优先级。截止时间越早，优先级越高。级。截止时间越早，优先级越高。该算法要求实时任务的就绪队列按任务该算法要求实时任务的就绪队列按任务截止时间截止时间的的早晚排序。调度程序总选择队首的任务执行。早晚排序。调度程序总选择队首的任务执行。该算法可用于抢占式和非抢占式调度。该算法可用于抢占式和非抢占式调度。t任务到达任务到达任务执行任务执行开始截止时间开始截止时间1
30、34211224433非抢占式调度方式非抢占式调度方式422、最低松弛度优先算法（、最低松弛度优先算法（LLF）该算法根据任务的松弛度来确定任务的优先级。松该算法根据任务的松弛度来确定任务的优先级。松弛度越低，优先级越高。弛度越低，优先级越高。松弛度任务必须完成的时间运行时间当前时间松弛度任务必须完成的时间运行时间当前时间该算法要求实时任务的就绪队列按松弛度排序。调该算法要求实时任务的就绪队列按松弛度排序。调度程序总选择队首的任务执行。度程序总选择队首的任务执行。该算法主要用于该算法主要用于抢占式抢占式调度方式。调度方式。43松弛度任务必须完成的时间运行时间当前时间松弛度任务必须完成的时间运行
31、时间当前时间例：例：实时系统中有两个周期性实时任务实时系统中有两个周期性实时任务A、B，任务，任务A每每20ms执行一次，执行时间执行一次，执行时间10ms；任务；任务B每每50ms执行执行一次，执行时间一次，执行时间25ms。采用抢占式。采用抢占式LLF算法：算法：t020406080100120140160A1A2A3A4A5A6A7A8B1B2B3任务任务AB每次必须完成的时间每次必须完成的时间松弛度松弛度t010203040455055607080A1=10B1=25A2=20B1=15A2=0B1=15A3=10B1=5A3=5B2=30此时执此时执行行B2A4=0B2=20A4完完
32、B2=10443、优先级倒置问题、优先级倒置问题（1）问题的形成）问题的形成即即OS中广泛采用的优先级调度算法和抢占方式。中广泛采用的优先级调度算法和抢占方式。举例举例:三个独立进程三个独立进程P1、P2、P3，优先级由高到低。，优先级由高到低。P1、P3共享临界资源进行交互。代码：共享临界资源进行交互。代码：P1：.P(mutex);CS-1;V(mutex).;P2:.program2.;P3:.P(mutex);CS-3;V(mutex).;执行顺序：执行顺序：P3P2(抢占抢占)P1（阻塞）（阻塞）P2(执行执行结束结束)P3(执行结束执行结束)P1(执行结束执行结束)问题：问题：P1
33、优先级最高，但最后执行结束优先级最高，但最后执行结束453、优先级倒置问题（续）、优先级倒置问题（续）（2）问题的解决方案）问题的解决方案方案方案2：建立在动态优先级继承基础上。：建立在动态优先级继承基础上。规定：规定：P1阻塞时由阻塞时由P3继承继承P1的优先级，一直保持到的优先级，一直保持到P3退出临界区。目的：防止退出临界区。目的：防止P2进程插进来，延缓进程插进来，延缓P3退出退出临界区。临界区。方案方案1：P3进入临界区后不允许处理机被抢占。进入临界区后不允许处理机被抢占。适用情况：系统中临界区较短且不多。适用情况：系统中临界区较短且不多。463.5产生死锁的原因和必要条件产生死锁的
34、原因和必要条件产生死锁的原因产生死锁的原因产生死锁的必要条件产生死锁的必要条件处理死锁的基本方法处理死锁的基本方法473.5.13.5.1、产生死锁的原因、产生死锁的原因一、死锁（一、死锁（Deadlock）定义：）定义：l死锁是指两个或两个以上的进程在运行过程中，死锁是指两个或两个以上的进程在运行过程中，因争夺资源而造成的一种互相等待（谁也无法因争夺资源而造成的一种互相等待（谁也无法再继续推进）的现象，若无外力作用，它们都再继续推进）的现象，若无外力作用，它们都将无法推进下去。将无法推进下去。二、产生死锁的原因：二、产生死锁的原因：l1、竞争资源l2、进程间推进顺序非法481、竞争资源引起进
35、程死锁、竞争资源引起进程死锁 1.1 资源的两种分类：资源的两种分类：可抢占性资源：CPU、RAM等；不可抢占性资源：打印机、磁带机等；可重用性资源：打印机可消耗性资源：进程通信中的消息、数据等49l1.2 竞争不可抢占性资源引起死锁：系统中配备的非剥夺性资源的数量不能满足诸进程运行的需要时，会使进程因争夺资源而陷入僵局。打印机打印机P1磁带机磁带机P21.3 竞争可消耗资源引起死锁：502 2、进程间推进顺序不当引起死锁、进程间推进顺序不当引起死锁l进程推进顺序进程推进顺序合法合法不会导致死锁不会导致死锁l进程推进顺序进程推进顺序非法非法可能会导致死可能会导致死图图1：顺序合法：顺序合法消息
36、消息1P1消息消息2P2P3消息消息3图图2：顺序非法：顺序非法消息消息1P1消息消息2P2P3消息消息3513.5.2、产生死锁的必要条件、产生死锁的必要条件1、互斥条件、互斥条件l一个资源一次只能被一个进程使用。一个资源一次只能被一个进程使用。2、请求和保持条件（部分分配）、请求和保持条件（部分分配）l保留已经得到的资源，还要求其它的资源。保留已经得到的资源，还要求其它的资源。3、不可抢占条件、不可抢占条件l资源只能被占有者释放，不能被其它进程强资源只能被占有者释放，不能被其它进程强行抢占。行抢占。4、循环等待循环等待条件（循环等待）条件（循环等待）l系统中的进程形成了环形的资源请求链。系
37、统中的进程形成了环形的资源请求链。523.5.3、处理死锁的基本方法、处理死锁的基本方法（1）预防死锁）预防死锁（2）避免死锁）避免死锁（3）检测死锁）检测死锁（4）解除死锁）解除死锁533.6预防死锁的方法预防死锁的方法预防死锁预防死锁系统安全状态系统安全状态利用银行家算法避免死锁利用银行家算法避免死锁543.6.1、预防死锁、预防死锁一、预防死锁的实质：一、预防死锁的实质：l通过设置某些限制条件，预防发生死锁。通过设置某些限制条件，预防发生死锁。二、预防死锁的方法：二、预防死锁的方法：“互斥条件互斥条件”由资源的性质决定。由资源的性质决定。1、摒弃、摒弃“请求和保持请求和保持”条件条件l在
38、开始运行前（创建时），一次性分配给进程它在开始运行前（创建时），一次性分配给进程它所需的所需的“全部全部”资源。资源。l简单易实现，安全性高；资源浪费。简单易实现，安全性高；资源浪费。552、摒弃、摒弃“不可抢占不可抢占”条件条件l当进程有新的资源请求时，如果得不到满足，要当进程有新的资源请求时，如果得不到满足，要先先释放释放原先占有的资源，待以后重新申请。原先占有的资源，待以后重新申请。l等价于此进程等价于此进程“被剥夺被剥夺”了已经占有的资源。了已经占有的资源。3、摒弃、摒弃“循环等待循环等待”条件条件l把系统资源按把系统资源按类型类型排序，进程要按照资源的序号排序，进程要按照资源的序号递
39、增递增的次序提出资源申请。的次序提出资源申请。l较上述两种方法的综合性能要好；但系统配置资较上述两种方法的综合性能要好；但系统配置资源的序号要稳定，固定的访问顺序不一定合理。源的序号要稳定，固定的访问顺序不一定合理。56例例1：进程进程A占有占有3号资源，现在又申请号资源，现在又申请5号资源号资源占有占有资源号小于申请资源号，此申请可以满足。资源号小于申请资源号，此申请可以满足。进程进程B占有占有5号资源，现在又申请号资源，现在又申请3号资源号资源由于由于53，所以此申请不能满足。进程，所以此申请不能满足。进程B要想得到要想得到3号资号资源，必须先放弃源，必须先放弃5号以及所有编号比号以及所有
40、编号比3大的资源。大的资源。57例例2 2：哲学家就餐：哲学家就餐给哲学家和筷子编号给哲学家和筷子编号04信号量定义：信号量定义：varchopstick0,4ofsemaphore;信号量初值均为信号量初值均为1；第第i(i=0,1,2,3)位哲学家活动描述：位哲学家活动描述：第第4位哲学家活动描述位哲学家活动描述:while(true)while(true)P(chopsticki);P(chopstick0);P(chopstick(i+1);P(chopstick4);eating;eating;V(chopsticki);V(chopstick0);V(chopstick(i+1);
41、V(chopstick4);thinking;thinking;583.6.2、系统安全状态、系统安全状态不安全状态不安全状态安全状态安全状态死锁死锁实质：实质：把系统的状态分为安全状态和不安全状态，只把系统的状态分为安全状态和不安全状态，只要能使系统始终处于安全状态，便可避免发生死锁要能使系统始终处于安全状态，便可避免发生死锁591、安全状态安全状态l允许进程动态的申请资源，但在分配前，应先计允许进程动态的申请资源，但在分配前，应先计算分配的安全性。算分配的安全性。l所谓所谓“安全状态安全状态”：指系统能按某种进程顺序：指系统能按某种进程顺序(P1,P2,Pn)，来为每个进程，来为每个进程P
42、i分配其所需资源，分配其所需资源，直至最大需求，使直至最大需求，使每个每个进程都可以进程都可以顺利顺利完成。反完成。反之，则系统处于之，则系统处于不安全状态。不安全状态。l 不安全状态不一定发生死锁，但死锁一定属于不安全状态不一定发生死锁，但死锁一定属于不安全状态。不安全状态。60进程进程 最大最大需求需求已已分分配配系统系统可用可用P1P2P310495223系统资源总数：系统资源总数：12进程进程最大最大需求需求已已分分配配系统系统可用可用P1P2P310495232系统资源总数：系统资源总数：122、安全状态之例：、安全状态之例：转化转化61l该算法能用于银行系统现金贷款的发放而得名该算
43、法能用于银行系统现金贷款的发放而得名l银行家算法的银行家算法的实质实质就是要设法保证系统动态分配资就是要设法保证系统动态分配资源后仍然保持安全状态，从而避免死锁的发生。源后仍然保持安全状态，从而避免死锁的发生。l要求进程预先告知自己的最大资源需求，并且假设要求进程预先告知自己的最大资源需求，并且假设系统拥有固定的资源总量。系统拥有固定的资源总量。3.6.2、利用银行家算法避免死锁利用银行家算法避免死锁621、相关的数据结构：、相关的数据结构：可用资源向量可用资源向量Available最大需求矩阵最大需求矩阵Max分配矩阵分配矩阵Allocation需求矩阵需求矩阵Need资源请求向量资源请求向
44、量Requesti3、安全性算法：、安全性算法：工作向量工作向量Work、Finish2、银行家算法：、银行家算法：（1）Requesti=Need?（2）Requesti=Available?（3）修改相关向量的值）修改相关向量的值（4）执行安全性算法）执行安全性算法63MaxAllocationNeedAvailableA B CA B CA B CA B CP0P1P2P3P47 5 33 2 29 0 22 2 24 3 30 1 02 0 03 0 22 1 10 0 27 4 31 2 26 0 00 1 14 3 13 3 2资源总数资源总数 10 5 7进程进程资源资源某时刻系
45、统资源分配情况某时刻系统资源分配情况A B CWork AllocationA B CA B CA B CFinishAllocationNeedWork进程进程资源资源安全序列安全序列(1)该时刻该时刻T0系统是安全的吗？系统是安全的吗？解：利用安全性算法解：利用安全性算法对该时刻的资源分配情况对该时刻的资源分配情况进行分析，方法如下图：进行分析，方法如下图：122200532true011211743true431211745true6003021047true7430101057true3325327437451047P1P3P4P2P064(2)若此时若此时P1请求资源，发出请求向量请
46、求资源，发出请求向量Request1(1,0,2)系统可以为满足请求吗？系统可以为满足请求吗？解：系统按银行家算法进行检查：解：系统按银行家算法进行检查：Request1(1,0,2)=Need1(1,2,2)Request1(1,0,2)=Available(3,3,2)系系统先假定可为统先假定可为P1分配资源，分配资源，修改相关修改相关向量值：向量值：利用利用安全性算法安全性算法检查此时系统是否安全。具体检查此时系统是否安全。具体：MaxAllocationNeedAvailableA B CA B CA B CA B CP0P1P2P3P47 5 33 2 29 0 22 2 24 3
47、30 1 02 0 03 0 22 1 10 0 27 4 31 2 26 0 00 1 14 3 13 3 2资源总数资源总数 10 5 7进程进程资源资源某时刻资源分配情况某时刻资源分配情况302020230655 3 27 4 37 4 57 5 510 5 7A B CWork AllocationA B CA B CA B Ctruetruetruetruetrue3 0 22 1 10 0 20 1 03 0 20 2 00 1 14 3 17 4 36 0 02 3 05 3 27 4 37 4 57 5 5P1P3P4P0P2FinishAllocationNeedWork进程
48、进程资源资源安全序列安全序列MaxAllocationNeedAvailableA B CA B CA B CA B CP0P1P2P3P47 5 33 2 29 0 22 2 24 3 30 1 02 0 03 0 22 1 10 0 27 4 31 2 26 0 00 1 14 3 13 3 2资源总数资源总数 10 5 7302020230进程进程资源资源某时刻资源分配情况某时刻资源分配情况66A B CA B CA B CA B C3 3 2资源总数资源总数10 5 77 4 31 2 26 0 00 1 14 3 10 1 02 0 03 0 22 1 10 0 27 5 33 2
49、29 0 22 2 24 3 3P0P1P2P3P4AvailableNeedAllocationMax进程进程资源资源某时刻资源分配情况某时刻资源分配情况302020230（3）若此时）若此时P4请求资源，发出请求向量请求资源，发出请求向量Request4(3,3,0)系统可以满足请求吗？系统可以满足请求吗？解：系统按银行家算法进行检查：解：系统按银行家算法进行检查：Request4(3,3,0)Available(2,3,0)因此，让因此，让P4等待。等待。67A B CA B CA B CA B C3 3 2资源总数资源总数10 5 77 4 31 2 26 0 00 1 14 3 10
50、 1 02 0 03 0 22 1 10 0 27 5 33 2 29 0 22 2 24 3 3P0P1P2P3P4AvailableNeedAllocationMax进程进程资源资源某时刻资源分配情况某时刻资源分配情况302020230（4）若此时）若此时P0请求资源，发出请求向量请求资源，发出请求向量Request0(0,2,0)系统可以满足请求吗？系统可以满足请求吗？解：系统按银行家算法进行检查：解：系统按银行家算法进行检查：Request0(0,2,0)=Need0(7,4,3)Request0(0,2,0)=Available(2,3,0)系统系统暂时先假定暂时先假定可为可为P0分
