调度和死锁OS04-C

《调度和死锁OS04-C》由会员分享，可在线阅读，更多相关《调度和死锁OS04-C（71页珍藏版）》请在装配图网上搜索。

1、(Scheduling and Deadlock)第二章 进程管理（C）调度和死锁4/21/20231教学目的 在多道程序系统中，一个作业从提交到执行完成，要经历多级调度，调度的好坏要影响系统的运行性能，因此调度是多道系统的关键。为了改善系统资源的利用率和提高系统处理能力，多道程序系统中采用多个进程的并发执行，但它也可能发生死锁的危险，研究死锁的原因和产生条件，采用预防死锁、避免死锁、检测死锁和解除死锁等多种方法防止死锁是多道程序系统重要的研究课题。4/21/20232教学要求：n熟悉处理机三级调度概念和处理机调度模型，掌握作业的状态和作业调度的功能。n掌握进程调度的方式和功能，熟悉调度方式和

2、算法的选择准则，掌握七种调度算法及适合范围。n掌握死锁的定义和产生死锁的原因，掌握死锁的四个必要条件；熟悉预防死锁的方法，熟练掌握银行家算法及其在死锁避免中的应用；掌握资源分配图的简化及其死锁定理，熟悉解除死锁的方法。4/21/20233（一）调度(Scheduling)（1）处理机三级调度）处理机三级调度1 1。高级。高级(Long-term)调度调度作业调度作业调度 作业调度用于决定把外存输入井上处于作业后备队列上的哪些作业调入内存，并为它们创建进程、分配必要的资源，然后再将新创建的进程排在就绪队列上，准备执行。在批处理系统中，作业是先驻留在外存的输入井上的，因此需要有作业调度。然而在分时

3、系统中，通过键盘输入的命令和数据直接进入内存，无需作业调度。2 2。低级。低级(Short-term)调度调度进程调度进程调度 进程调度决定就绪队列中哪个进程将获得处理机，然后由分派程序执行把处理机分配给该进程的操作。进程调度是最基本的调度，任何操作系统都有进程调度。4/21/20234处理机三级调度-13 3。中级。中级(Medium-term)调度调度对换对换 引入中级调度的目的是为了提高主存利用率和系统吞吐量。由于在进程并发执行过程中，为了充分发挥内存的效能，需将那些暂时不能运行的进程从内存调到外存盘交换区去等待，而将那些在盘交换区的等待事件已经发生急需调度运行的进程从盘交换区调入内存。

4、在UNIX系统中中级调度就是存储管理中的对换，采用虚拟存储技术的分时系统往往设立中级调度。4/21/20235处理机三级调度图：作业调度 作业运行状态 外存(盘)交换区作业后备状态作业提交状态作 业完成状态终止作业就 绪态阻 塞态主存 进程调度运 行态就绪态阻 塞态外存中级调度4/21/20236（2）作业调度1 1。作业的状态。作业的状态 作业从进入到运行结束，一般需要经历“提交”、“后备”、“运行”和“完成”四个阶段。n提交状态提交状态 一个作业被提交给机房后正在通过SPOOLing系统进行输入或用户通过终端向计算机中键入其作业时所处于的状态为提交状态。n后备状态后备状态 作业已经过SPO

5、OLing系统输入到磁盘输入井磁盘输入井，等待调入内存运行，此时作业处于后备状态。为了管理和调度作业，为每个作业设置一个作业控制块作业控制块（JCBJCB）。作业控制块记录了作业类型和资源要求等有关信息。作业控制块按作业类型组成一个或多个后备作业队列后备作业队列。4/21/20237作业调度-1n运行状态运行状态 一个在后备作业队列的作业被作业调度程序选中后，分配必要的资源，建立一组相应的进程后，调入内存，该作业就进入运行状态。进程各状态（进程运行态、内存进程就绪态、内存阻塞态、外存进程就绪态、外存进程阻塞态等）都对应作业运行状态。n完成状态完成状态 当进程正常运行结束或因发生错误而终止时，作

6、业进入完成状态。终止作业程序将负责善后处理。4/21/20238作业调度-22 2。作业状态的转换。作业状态的转换n作业调度作业调度 作业调度程序按一定算法从后备作业队列中选一个满足资源要求的作业，分配它所要求的资源，建立一组相应的进程，设置该进程状态为就绪态，并将该进程插入内存就绪队列，参加CPU争夺。n终止作业终止作业 当进程正常运行结束或因发生错误终止时，调用终止作业程序，它负责将输出文件缓冲输出到输出井，并调用SPOOLing系统输出进程将作业输出文件在打印机输出。同时回收作业所使用内、外存、I/O设备等各种资源，最后调用记帐程序结清作业费用。4/21/20239（3）处理机调度模型1

7、 1。仅有进程调度的调度队列模型。仅有进程调度的调度队列模型 在分时系统中通常仅设置了进程调度。此时系统有一个就绪队列，每个进程运行一个时间片，进程运行一个时间片后如未完成，则被放在就绪队列末尾。如进程运行中因等待某事件（例如申请I/O而等待I/O完成），则需排入阻塞队列，系统因阻塞的原因不同可设几个阻塞队列。2 2。具有进程调度和中级调度队列模型。具有进程调度和中级调度队列模型 在具有虚拟存储器技术的分时系统中（例如UNIX系统等），一般采用具有进程调度和中级调度的调度模型。在该模型中比第一种模型增加了中级调度，则相对于上模型也增加了外存进程就绪队列和外存进程阻塞队列。中级调度时或从内存就绪

8、队列调到外存的就绪队列，或从内存阻塞队列调到外存阻塞队列，或从外存进程就绪队列调到内存就绪队列。4/21/202310处理机调度模型-13 3。具有高级调度和低级调度的调度队列模型。具有高级调度和低级调度的调度队列模型 在多道批处理系统中，一般处理机管理设置作业和进程两级调度。它比第一个模型增加了高级调度。模型增加了在磁盘的作业后备队列，作业调度的任务是从作业后备队列中选一个作业为它创建至少一个进程，并分配资源，将它排入内存进程就绪队列末尾。4 4。同时具有三级调度的调度队列模型。同时具有三级调度的调度队列模型 在通用系统的多模式OS中，一般采用具有三级调度的调度队列模型，由于多模式OS同时支

9、持批处理、分时和实时处理，所以它必须具有以上模型，具有三级调度的调度队列模型是第二、三两模型的综合，见图所示。4/21/202311具有三级调度队形模型图：具有三级调度队形模型图：中中级级调调度度调出调出CPU交互型作业交互型作业分时间片完分时间片完等等待待事事件件完成完成内存进程就绪队列内存进程就绪队列外存进程就绪队列外存进程就绪队列外存进程阻塞队列外存进程阻塞队列内存进程阻塞队列内存进程阻塞队列事事件件发发生生作业调度作业调度后备作业队列后备作业队列批批量量作业作业中中级级调调度度调入调入中中级级调调度度调出调出磁盘磁盘4/21/202312（4）进程调度1 1。进程调度的方式。进程调度的

10、方式非抢占方式非抢占方式 采用这种调度方式时，一旦把处理机分配给某进程后，便让进程一直执行，直到该进程完成或发生某事件而被阻塞时，才把处理机分配给其它进程，决不允许某进程抢占已经分配出去的处理机。这种调度方式的优点是实现简单、系统开销小，适用于大多数批处理系统环境。缺点是难以满足紧急任务的要求，不适用于实时、分时系统要求。4/21/202313进程调度-1抢占方式抢占方式（Preemptive modePreemptive mode）这种调度方式，允许进程调度程序根据某个原则，去仃止某个正在执行的进程，将已分配给进程的处理机，重新分配给另一个进程。抢占的原则有：n时间片原则。各进程按时间片运行

11、，当一个时间片用完后，便仃止该进程的执行而重新进行调度。这个原则适用于分时系统。n优先权原则。通常是对一些重要的和紧急的进程赋予较高的优先权。当这种进程进入就绪队列时，例如由阻塞态转换为就绪态，或从静止就绪态转为活动就绪态时，或新创建进入就绪态的进程进入就绪队列时，如果其优先权比正在执行的进程优先权高，便仃止正在执行的进程，将处理机分配给优先权高的进程，使之执行。4/21/2023142.进程调度的功能n记录系统中所有进程的执行情况 进程管理模块在各进程的PCB表中记录系统各进程的执行情况和状态特征，并将各PCB表根据进程状态特征和资源要求排成相应的队列，并进行动态队列转换。n选择占有处理机进

12、程 进程调度的主要功能是按照一定的策略（由它决定的调度算法），选择一个处于就绪态的进程，使其获得处理机执行。n进行进程上下文切换 进程上下文实际上是进程执行活动全过程的静态描述，一个进程的执行是在进程上下文中执行。当正在执行的进程由于某种原因要让出处理机时，系统要做上下文切换，以使另一个进程得以执行。4/21/202315(5)调度方式和算法的选择准则1.面向用户的准则和评价面向用户的准则和评价（周转时间短周转时间短:（它是评价批处理系统的重要性能指标。作业周转时间Ti是指从作业提交给系统开始，到作业完成为止的这段时间间隔。平均周转时间T=1/n 平均带权周转时间 W=1/n 一个作业的带权周

13、转时间Wi=Ti/Tsi（作业的周转时间Ti/实际服务时间Tsi）（响应时间快响应时间快 响应时间是评价分时系统的性能指标。响应时间是从用户通过键盘提交一个请求开始，直至系统首次产生响应为止的时间。4/21/202316调度方式和算法的选择准则-1n截止时间的保证截止时间的保证 它是用来评价实时系统的重要指标，截止时间是某任务必须执行的最迟时间，或完成的最迟时间。（优先权准则优先权准则 在选择批处理、分时和实时系统的调度算法时，都可引用优先权准则，以便让那些紧急的作业（或事件），得到及时的处理。在要求较严格的场合，往往还需选择抢占调度方式，才能保证紧急作业得到及时的处理。2。面向系统的准则面向

14、系统的准则（达到系统设计目标达到系统设计目标 系统的设计目标是选择算法的主要依据。例如批处理系统所追求的是充分发挥和提高计算机的效率，分时系统则侧重于保护用户的请求及时给予响应，实时系统所关心的是不要丢失实时信息并给予处理。4/21/202317调度方式和算法的选择准则-2n系统吞吐量大系统吞吐量大 这是用来评价批处理系统的重要指标。系统吞吐量是单位时间内完成的作业数，它与批处理作业的平均长度具有密切关系。（处理机利用率高处理机利用率高 对于大中型多用户系统，由于CPU价格十分昂贵，所以处理机利用率成为衡量大、中型系统性能的重要指标，但对单用户微机或某些实时系统，该准则就不那么重要。（各类资源

15、的平衡利用各类资源的平衡利用 在大中型系统中，有效地利用各类资源（包括CPU、外存、I/O设备等）也是一个重要指标，对于微型机和某些实时系统，该准则也不重要。4/21/202318（6）作业进程调度算法1 1。先来先服务。先来先服务First-Come-First-Served （FCFSFCFS）（作业进程）（作业进程）调度算法调度算法 FCFS是一种最简单的调度算法，可用于作业或进程调度。此算法的原则是按照作业到达后备作业队列（或进程进入就绪队列）的先后次序来选择作业（或进程）。FCFS算法属于非抢占方式，一旦一个进程占有处理机，它就一直运行下去，直到该进程完成或者因等待某事件而不能继续运

16、行时才释放处理机。FCFS算法易于实现，表面上很公平。2 2。短作业进程优先。短作业进程优先(SJF/(SJF/Shortest Process Next)调度算法调度算法 这种调度算法主要用于作业调度，它从作业后备队列中挑选所需运行时间（估计值）最短的作业进入主存运行。这一算法有利于短作业，对长作业不利。采用SJF有利于系统减少平均周转时间和平均带权周转时间。4/21/202319作业进程调度算法-13 3。时间片轮转。时间片轮转Round-Robin（RRRR）调度算法）调度算法 它用于进程调度，是分时系统采用的主要调度算法。进程调度程序总是选择就绪队列中第一个进程，允许其占有处理机一个时

17、间片的时间。当执行的时间片用完时，调度程序便仃止该进程的执行，并将它送就绪队列的末尾，等待分配下一时间片再执行。然后把处理机分配给就绪队列中新的队首进程，同时也让它执行一个时间片。这样就可以保证就绪队列中的所有进程，在一给定的时间内，均能获得一时间片处理机执行时间。在RR算法中，时间片的大小对系统性能有很大的影响。4/21/202320作业进程调度算法-24 4。高响应比优先。高响应比优先 Highest Response Ratio Next(HRRN)(作作业业)调度算法调度算法 按照高响应比优先的原则，在每次选择作业投入运行时，先计算此时后备作业队列中每个作业的响应比RP然后选择其值最大

18、的作业投入运行。RP值定义为：RP（已等待时间要求运行时间）要求运行时间 1已等待时间要求运行时间。HRN算法实际上是FCFS算法和STF算法的折衷。4/21/202321作业进程调度算法-3例：例：假定在一个处理机上执行以下五个作业：作业号 A B C D E 到达时间 0 1 2 3 4 运行时间 4 3 5 2 4分别采用FCFS、SJF、RR（时间片1）和HRN(响应比高者优先)四种调度算法时，试做：（1）画出调度图；（2）计算每个作业的周转时间和带权周转时间；（3）计算平均周转时间和平均带权周转时间。调度图：T 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 1

19、5 16 17 18T 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 FCFS A A A A B B B C C C C C D D E E E E FCFS A A A A B B B C C C C C D D E E E E SJF A A A A D D B B B E E E E C C C C C SJF A A A A D D B B B E E E E C C C C C RR A B C D E A B C D E A B C E A C E C RR A B C D E A B C D E A B C E A C E C H

20、RN A A A A B B B D D C C C C C E E E E HRN A A A A B B B D D C C C C C E E E E4/21/202322例解：4/21/202323例解-14/21/202324例解-2n高响应比优先(HRRN)(作业)调度算法计算：T=0：只有作业A已到达，调度作业A运行。T=4：作业A完成，作业B、C、D、E已到达，计算作业B、C、D、E响应比RP分别为：1+3/3、1+2/5、1+1/2、1+0/4，作业B响应比最大调度运行。T=7：作业B完成，作业C、D、E已到达，计算作业C、D、E响应比RP分别为：1+5/5、1+4/2、1+

21、3/4，作业D响应比最大调度运行。T=9：作业D完成，作业C、E已到达，计算作业C、E响应比RP分别为：1+7/5、1+5/4，作业C响应比最大调度运行。T=14：作业C完成，只有作业E未完成，调度作业E运行。4/21/202325作业进程调度算法-4 5.5.优先权优先权(Priority)调度算法调度算法 按照进程的优先权大小来调度，使高优先权进程得到优先按照进程的优先权大小来调度，使高优先权进程得到优先处理的调度策略称为优先权调度算法处理的调度策略称为优先权调度算法。进程的优先权的设置可以是静态的，也可以是动态的。n静态优先权静态优先权在进程创建时确定，且的在整个生命期中保持不变。确定进

22、程优先权的依据有：进程类型，通常系统进程（例如对换进程）的优先权高于一般用户态进程的优先权；进程对资源的需求，如进程执行时间及内存需要省的进程应赋予较高的优先权；根据用户要求，由用户的紧迫程度及用户所付费用的多少来确定进程的优先权。n动态优先权动态优先权是指在创建进程时所赋予的优先权，可以随进程的推进而改变，以便获得更好的调度性能。改变优先权的因数，随系统不同而不同，最常考虑的因素的进程的等待时间，已使用处理机的时间，或者资源使用情况等。4/21/202326作业进程调度算法-5n在UNIXUNIX系统V中，一类是因等待磁盘I/O、等待缓冲器等不可中断优先权最高，而另一类因等待TTY输入输出等

23、可中断优先权其次。处于用户态的优先权相对较低，用户态优先权又分为n+1级优先权。优先数为0级的优先权最高，优先数为n级的优先权最低。用户态优先权是可变的，它随着占用CPU时间的增加而降低。核心每隔1秒钟便按下述公式对各进程重新计算其用户优先数（优先数与优先权成反比关系）。优先数最近使用CPU的时间2基本用户优先数。6 6多级队列调度算法多级队列调度算法n多队列调度是根据作业的性质和类型的不同，将就绪队列再分为若干个子队列，所有的作业（或进程）按其性质排入相应的队列中，而不同的就绪队列采用不同的调度算法。4/21/202327作业进程调度算法-6 例如前后台系统可以建立两个就绪队列，批处理作业所

24、建立进程进入后台就绪队列；交互型作业所建立的进程进入前台就绪队列。前台采用时间片轮转算法，进程按FCFS等策略排序，后台采用优先权高优先的调度算法或者短作业优先的调度算法。对多级就绪队列调度策略有两种，一种是各就绪队列按进程性质赋予不同的优先权，这样，只有较高优先权的就绪队列都空时才调度最低优先权就绪队列的进程。另一种调度就绪队列的方式是为每个队列分配一定的占用CPU时间的比例。如在上例中为前台队列分配80的CPU时间，给后台队列分配20的CPU时间。4/21/202328作业进程调度算法-7 7 7。多级反馈。多级反馈(Feedback)队列调度算法队列调度算法n多级反馈队列调度算法，不必事

25、先知道各种进程所需的执行时间 n WindowsNT采用可抢占动态优先级多级就绪队列调度算法。NT执行体支持32级优先级，并将它们分成两类，实时优先级（1631）和可变优先级（115），0级为系统保留。每个优先级一个就绪队列，高序号队列为高优先级，调度程序从高优先级的队列开始往下找，如高优先级队列为空时才再往下找，直至找到一个线程。4/21/202329作业进程调度算法-8 各个就绪队列中进程执行时间片的大小也各不相同，在优先级越高的队列中，每个进程的执行时间片就规定得越小。n当一个线程执行完一个完整的时间段后被中断抢占处理器，而被抢占的线程优先级降低一级而进入下级就绪队列，如此继续，直至降到

26、线程的基本优先级。n而一个线程从阻塞态变为就绪态时要提高优先级，提高的幅度与等待的事件有关。如等待键盘输入所提高的幅度要大于等待磁盘I/O。在NT中，交互式线程处于高优先级，I/O型线程处于中间优先级，计算型线程处于低优先级，系统还设置一个空闲线程，其优先级为0，是优先级最低的线程，只要处理空闲，就执行该线程。4/21/202330图：多级反馈队列就绪队列就绪队列1 时间片时间片S1时间片完时间片完时间片完时间片完就绪队列就绪队列2 时间片时间片S2S1运行运行运行运行运行运行就绪队列就绪队列n 时间片时间片SnSn-1完成完成完成完成完成完成时间片完时间片完阻塞队列阻塞队列i阻塞阻塞阻塞阻塞

27、阻塞阻塞事件发生事件发生4/21/202331n1 1实现实时调度的基本条件实现实时调度的基本条件na a提供必要的调度信息提供必要的调度信息n（1 1）就绪时间；）就绪时间；n（2 2）开始）开始/完成截止时间；完成截止时间；n（3 3）处理时间；）处理时间；n（4 4）资源要求；）资源要求；n（5 5）优先级；）优先级；nb b系统处理能力强系统处理能力强（6 6）实时调度）实时调度Ci为处理时间，为处理时间，Pi为周期时间（基于周期性实时任务）为周期时间（基于周期性实时任务）4/21/202332n1 1实现实时调度的基本条件实现实时调度的基本条件nc.c.采用抢占调度方式采用抢占调度方

28、式n剥夺方式：一般都采用此剥夺方式：一般都采用此n非剥夺方式（如果能预知任务的开始截止时间）：非剥夺方式（如果能预知任务的开始截止时间）：一般应使实时任务较小，以及时放弃一般应使实时任务较小，以及时放弃CPUCPU。nd.d.具有快速切换机制具有快速切换机制n具有快速响应外部中断能力。具有快速响应外部中断能力。n快速任务分派快速任务分派4/21/2023332 2实时调度算法的分类实时调度算法的分类n非抢占式调度算法非抢占式调度算法n时间片轮转时间片轮转 秒级秒级n非抢占优先权（协同）非抢占优先权（协同）秒秒 毫秒级毫秒级n抢占式调度算法抢占式调度算法n时钟中断抢占优先权时钟中断抢占优先权 毫

29、秒级毫秒级n基于抢占点抢占基于抢占点抢占n立即抢占立即抢占immediate preemption immediate preemption 毫秒毫秒 微秒级微秒级n只要不在临界区即抢占（中断引发）只要不在临界区即抢占（中断引发）4/21/202334进程1进程2进程n实时进程调度时间调度时间实时进程要求调度实时进程要求调度调度实时进程运行调度实时进程运行a 非抢占轮转调度非抢占轮转调度当前进程实时进程实时进程要求调度实时进程要求调度当前进程运行完成当前进程运行完成b 非抢占优先权调度非抢占优先权调度调度时间调度时间4/21/202335c 基于时钟中断抢占的优先权抢占调度基于时钟中断抢占的优

30、先权抢占调度当前进程实时进程实时进程要求调度实时进程要求调度抢占时刻（其它中断）抢占时刻（其它中断）b 立即抢占优先权调度立即抢占优先权调度当前进程实时进程实时进程要求调度实时进程要求调度时钟中断到达时时钟中断到达时调度时间调度时间调度时间调度时间4/21/2023363 3常用的几种实时调度算法常用的几种实时调度算法na.a.最早截止时间优先最早截止时间优先EDFEDF（earliest deadline earliest deadline first)first)算法算法n根据任务的截止时间来确定任务的优先级根据任务的截止时间来确定任务的优先级n截止时间越早，优先级越高截止时间越早，优先级

31、越高n可以是抢占式或非抢占式可以是抢占式或非抢占式4/21/202337最早截止时间优先最早截止时间优先EDFEDF例例1342134212 34t开始截止时间开始截止时间任务到达任务到达任务执行任务执行图图37 EDF算法用于非抢占调度方式算法用于非抢占调度方式4/21/202338b.b.最低松弛度优先最低松弛度优先LLFLLF算法算法n松弛度：松弛度：n若若A A进程需在进程需在200ms200ms时完成，其本身运行需要时完成，其本身运行需要100ms100ms，当，当前时刻是前时刻是10ms10ms，则，则A A的松弛度为：的松弛度为：20020010010010109090n主要用于

32、可抢占的调度方式中主要用于可抢占的调度方式中n例：例：A A每每20ms20ms做一次（做一次（10ms10ms）B B每每50ms50ms做一次（做一次（25ms25ms）A1A2A3A4A5A6A7A8B1B2B3020406080 100120 140160t图图38 A/B任务每次必须完成的时间任务每次必须完成的时间4/21/202339最低松弛度优先最低松弛度优先LLFLLF算法算法(2)(2)A1(10)A2(10)A3(10)A4(10)t01020304050607080t1=0B1(20)B1(5)B2(15)B2(10)t1t2t3t4t5t6t7t84/21/202340

33、（7 7）多处理机系统中的调度）多处理机系统中的调度n1.多处理机系统的类型多处理机系统的类型na.a.紧密耦合紧密耦合MPSMPS和松弛耦合和松弛耦合MPSMPSn紧密耦合紧密耦合n共享共享RAMRAM和和I/OI/On高速总线和交叉开关连接高速总线和交叉开关连接n松弛耦合松弛耦合n独立独立RAMRAM和和I/OI/On通道和通信线路连接通道和通信线路连接nb.b.对称多处理器系统和非对称多处理器系统对称多处理器系统和非对称多处理器系统n处理器是否结构相同处理器是否结构相同4/21/2023412 2进程分配方式进程分配方式na.SMPa.SMP中进程分配方式中进程分配方式n静静态态分分配配

34、：进进程程从从运运行行到到结结束束只只能能分分配配到到一一个处理器中个处理器中n动态分配：进程可分配到任一个处理器中动态分配：进程可分配到任一个处理器中n可防止系统中多个处理器忙闲不均可防止系统中多个处理器忙闲不均nb.b.非非SMPSMP中进程分配方式中进程分配方式n进程调度在主处理器上执行进程调度在主处理器上执行n有潜在的不可靠性有潜在的不可靠性4/21/2023423 3进程（线程）调度方式进程（线程）调度方式 na.a.自调度自调度n各个处理机自行在就绪队列中取任务。各个处理机自行在就绪队列中取任务。n特点；简单，分布式调度，调度算法可采用特点；简单，分布式调度，调度算法可采用前述方法

35、，多个前述方法，多个CPUCPU利用率都不错（不会闲）利用率都不错（不会闲）n但：但：n瓶颈问题，（单队列）瓶颈问题，（单队列）n低效性；（需拷贝现场）低效性；（需拷贝现场）n线程切换频繁（当线程合作时线程切换频繁（当线程合作时,各线程并行各线程并行的条件不容易满足）的条件不容易满足）4/21/202343b.b.成组调度成组调度 n优点：优点：（1 1）对相互合作的进（线）程组调度，可以减小切换，）对相互合作的进（线）程组调度，可以减小切换，减小系统开销。减小系统开销。（2 2）每次分配一组）每次分配一组CPUCPU，减少了调度频率。，减少了调度频率。n分配时间分配时间（1 1）面向程序）面

36、向程序（2 2）面向线程：使处理机利用率更高。）面向线程：使处理机利用率更高。4/21/202344b.b.成组调度成组调度浪费浪费37.5%浪费浪费15%4/21/202345c.c.专用处理机分配专用处理机分配 n引入：多处理机系统，每个处理已不再属宝引入：多处理机系统，每个处理已不再属宝贵资源。贵资源。n特点：每个进（线）程专用处理机，使其切特点：每个进（线）程专用处理机，使其切换小，提高效率。换小，提高效率。n主要用于大型计算，实时系统主要用于大型计算，实时系统4/21/202346（二）进程死锁（1）死锁的原因和条件）死锁的原因和条件1。死锁的原因。死锁的原因n竞争资源引起死锁竞争资

37、源引起死锁 在多道程序系统，多个进程共享系统的资源。系统资源分为二类，一类是不可抢占的资源，如打印机、磁带机等。当系统把这类资源分配给某进程后，再不能强行收回，只能在进程用完后自动释放。另一类是可抢占的资源，如CPU、内存等。由于系统拥有的不可抢占的资源有限，多个进程共享竞争不可抢占的资源就可能引起死锁。n进程推进顺序不当引起死锁进程推进顺序不当引起死锁 在多道程序系统中，并发执行的进程推进序列不可予测，有些推进顺序，进程可以顺利完成，这些推进顺序是合法的；而有的推进顺序会引起进程无限期地等待永远不会发生的条件而不能向前推进，造成了死锁。4/21/202347死锁的原因和条件-1n进程推进顺序

38、不当引起死锁例：进程P和Q并发执行，进程P和Q程序如下：Process P Process Q.Get A Get B.Get B Get A.Release A Release B.Release B Release A.进程P和Q按路径1、2、5、6推进顺序合法，按3、4推进顺序非法，见下图：4/21/202348进程推进顺序不当引起死锁例：Progressof QReleaseAReleaseBGet AGet BGet A Get B Release ARelease BProgressof PARequiredB RequiredARequiredBRequireddeadlocki

39、nevitable123456P and Qwant BP and Qwant A49死锁的原因和条件-12 2。产生死锁的必要条件（。产生死锁的必要条件（Conditions for Deadlock ）n互斥（互斥（Mutual exclusion ）条件）条件：一个资源一次只能被一个进程所使用，即是排它性使用。n不可抢占（不可抢占（No preemption ）条件）条件：一个资源仅能被占有它的进程所释放，而不能被别的进程强占。n请求和保持（请求和保持（Hold-and-wait ）条件）条件：进程已经保持了至少一个资源，但又提出了新的资源要求，而该资源又已被其它进程占有，此时请求进程阻

40、塞，但又对已经获得的其它资源保持不放。n环路等待（环路等待（Circular wait ）条件）条件：当每类资源只有一个时，在发生死锁时，必然存在一个进程-资源的环形链。如一系统状态的资源分配图所示，P1正在等待一个P2 占用的资源R2，P2正在等待一个P1占用的资源R1。4/21/202350死锁的原因和条件-2n资源分配图由结点和边组成。结点有二类，一类是进程结点，用园圈表示；另一类是资源结点，用小方框表示一类资源，用方框中的小圈表示资源数。边也有二类，一类是分配边，它由资源结点指向进程结点，另一类是申请边，它由进程结点指向资源结点。R1R2 P1P24/21/202351死锁的原因和条件

41、-33。处理。处理死锁的基本方法死锁的基本方法a.死锁的预防 静态方法：在进程执行前采取的措施，通过设置某些限制条件，去破坏产生死锁的四个必要条件之一，防止发生死锁。B.死锁的避免 动态的方法：在进程执行过程中采取的措施，不需事先采取限制措施破坏产生死锁的必要条件，而是在进程申请资源时用某种方法去防止系统进入不安全状态，从而避免发生死锁。C.死锁的检测和解除 这种方法预先并不采用任何限制措施，允许系统在运行过程中发生死锁，但可通过系统设置的检测机构及时检测死锁的发生，如检测到死锁，则采用撤消进程等死锁解除方法使系统正常工作。4/21/202352（2）死锁的预防(Deadlock Preven

42、tion)预防死锁的方法是破坏四个产生死锁的必要条件之一。1。破坏互斥条件破坏互斥条件 互斥使用是资源本身特征所决定的。使用硬软件结合可改变资源本身特性，例如采用SPOOLing技术可将“独享”打印机改变为“共享”的打印机。2。破坏不可抢占条件破坏不可抢占条件 抢占式调度法主要用于处理机和存贮器资源调度，它们的状态容易保存和恢复。但此法对外部设备和私存数据不宜使用。4/21/202353死锁的预防-13。破坏请求和保持条件破坏请求和保持条件 系统可采用资源静态予分配方式资源静态予分配方式来破坏请求保持条件。系统要求所有进程一次性地申请在整个运行过程中全部资源，若系统有足够资源满足给进程，则在运

43、行前，一次性将其所需要的所有资源分配给该进程。这样该进程在整个运行期间，便不再提出资源要求，从而摒弃了请求条件。这种预防死锁的方法，优点是简单、易予实现且很安全，但其资源利用率很低，进程也延迟运行。4。破坏循环等待条件破坏循环等待条件n 有序资源使用法有序资源使用法 该方法将所有的资源按类型进行线性排队，并赋予不同的序号。例如令输入机的序号为1，打印机序号为2，磁盘机序号为3等。4/21/202354死锁的预防-2 所有进程对资源的请求必须严格按资源序号递增的次序提出。这样在所形成的资源分配图中不可能再出现环路，因而摒弃了“环路等待”条件，在采用这种策略时总有一个进程占据了较高序号的资源，它继

44、续请求的资源必然是空闲的，因而进程可以一直向前推进。这种预防死锁的策略可以提高资源利用率，但在进程使用各类资源的顺序与系统规定的顺序不同时会造成资源浪费的情况。n资源按级分配法资源按级分配法 该方法是把资源递增排序成若干等级（如L1、L2.Lm），其中每级可包含几类资源，要求每个进程在获得了Lj级中资源之后，它才能申请更高级的LK（LKLj）级中的资源；如果它还需申请比LK级低的LI级（LI 4 P2 4 2 2 =4 因为找不到一个安全序列使所有进程顺序地一个个地运行完毕，所以T1状态是不安全状态，由于实施分配给1台磁带机给P3的操作会引起系统状态由安全状态T0向不安全状态下的转换，所以为了

45、避免死锁，上述的分配只是安全检测，检测后判定这样的申请不能满足，P3为申请1台磁带机而必须阻塞等待。4/21/2023583.利用银行家算法避免死锁 最具代表的避免死锁算法是Dijkstra的银行家算法，这是由于该算法用于银行系统现金贷款的发放而得名。银行家算法的数据结构银行家算法的数据结构可用资源向量 Available m m为系统中资源种类数，Availablej=k表示系统中第j类资源数为k个。最大需求矩阵Maxn，m n为系统中进程数，Maxi,j=k表示进程i对j类资源的最大需求数为中k。分配矩阵Allocationn，m 它定义了系统中每一类资源当前已分配给每一进程资源数，All

46、ocationi,j=k表示进程i已分得j类资源的数目为k个。4/21/202359利用银行家算法避免死锁-1需求矩阵Needn,m 它表示每个进程尚需的各类资源数，Needi,j=k 表示进程i还需要j类资源k个。Needi,j=Maxi,j-Allocationi,j银行家算法银行家算法n假设在进程并发执行时进程i提出请求j类资源k个后，表示为Requestij=k。系统按下述步骤进行安全检查：如果RequestiNeedi则继续以下检查，否则显示需求申请超出最大需求值的错误。如果RequestiAvailable则继续以下检查，否则显示系统无足够资源，Pi阻塞等待。系统试探把要求的资源分

47、配给进程i并修改有关数据结构的值：Available =Available-Requesti；Allocationi=Allocationi+Requesti；Needi=Needi-Requesti ；4/21/202360利用银行家算法避免死锁-2 系统执行安全性算法，检查此次资源分配后，系统是否处于安全状态，若安全，才正式将资源分配给进程i，以完成本次分配；否则将试探分配作废，恢复原来的资源分配状态，让进程Pi等待。安全性算法安全性算法安全性算法执行步骤如下：A.初始化设置工作向量Workm表示系统可提供的各类资源数目，用以保护原数据结构有关值。Work=Available，设置完成标志

48、向量 Finishn。Finishi=false 表示i进程尚末完成，如值为true则表示进程i已完成。B.从进程集合n中找到一个能满足下述二个条件:Finishi=false和NecdiWork，如找到则执行步骤C，如找不到同时满足以上二条件的进程则执行步骤D。4/21/202361利用银行家算法避免死锁-3C.当进程i获得资源后可顺利执行直到完成，并释放出分配给它的资源，表示如下：work=work+Allocationi；Finishi=true；转执行步骤B。D.如果所有的Finishiture，则表示系统处于安全状态，否则系统处于不安全状态。4/21/202362银行家算法例：假定系

49、统中有五个进程P0、P1、P2、P3、P4和三种类型资源A、B、C，每一种资源的数量分别为10、5、7。各进程的最大需求、T0时刻资源分配情况如下 所示。Max Allocation Need Available A B CA B C A B C A B C P0 7 5 3 0 1 0 7 4 3 3 3 2 P1 3 2 2 2 0 0 1 2 2P2 9 0 2 3 0 2 6 0 0P3 2 2 2 2 1 1 0 1 1P4 4 3 3 0 0 2 4 3 1试问：T0时刻是否安全？P1请求资源Request1(1,0,2)是否允许？P4请求资源Request4(3,3,0)是否允许

50、？4/21/202363银行家算法例-1nT0时刻是否安全？从表中可找出一个序列(P1、P3、P4、P2、P0）使各进程顺序地一个个地执行完成。MaxMax Allocation Need Available Available (分配资源前分配资源前)(释放释放资源资源后）后）A B C A B C A B C A B C A B CP0 7 5 3 0 1 0 7 4 3 =10 4 7 10 5 7P1 3 2 2 2 0 0 1 2 2 =3 3 2 5 3 2P2 9 0 2 3 0 2 6 0 0 =7 4 5 10 4 7P3 2 2 2 2 1 1 0 1 1 =5 3 2 7

51、 4 3P4 4 3 3 0 0 2 4 3 1 =7 4 3 7 4 5安全序列为P1、P3、P4、P2、P0，T0时刻系统是安全的。nP1请求资源Request1(1,0,2)可否允许？4/21/202364银行家算法例-2Request1(1,0,2)Need1(1,2,2)，P1请求在最大需求范围内。Request1(1,0,2)Available(3,3,2)，可用资源可满足P1请求需要。试探把要求的资源分配给进程P1并修改有关数据结构的数值：Available=Available(3，3，2)Request1(1,0,2)=Available(2,3,0)；Need1=Need1(

52、1,2,2)Request1(1,0,2)=Need1(0,2,0)；Allocation1=Allocation1(2,0,0)+Request1(1,0,2)=Allocation1(3,0,2)；利用安全性算法检查试探将资源分配后状态的安全性如下：4/21/202365银行家算法例-3 Max Max Allocation Need Available Available (分配资源前分配资源前)(释放释放资源资源后）后）A B C A B C A B C A B C A B CP0 7 5 3 0 1 0 7 4 3 =10 4 7 10 5 7P1 3 2 2 3 0 2 0 2 0

53、 =2 3 0 5 3 2P29 0 2 3 0 2 6 0 0 =7 4 5 10 4 7P32 2 2 2 1 1 0 1 1 =5 3 2 7 4 3P44 3 3 0 0 2 4 3 1 =7 4 3 7 4 5 因为先分配资源给P1进程符合按安全序列P1、P3、P4、P2、P0分配资源，所以试探将资源分配给进程P1后的状态是安全的，可将资源分配给进程P1。nP4请求资源Request4(3,3,0)是否允许？Request4(3,3,0)Need4(4,3,1)，P4请求在最大需求范围内。Request4(3,3,0)Available(2,3,0)不成立，即可用资源暂不能满足P4请

54、求资源需要，P4阻塞等待。4/21/202366（4）死锁的检测(Deadlock Detection)死锁的避免算法增加了系统的开销，死锁的检测采用资源分配图的简化判断是否发生了不安全状态。如发现系统处于不安全状态时，即执行死锁解除的策略，采用此法开销相对减少。1 1。资源分配图的简化。资源分配图的简化：在资源分配图中找一个既不阻塞又非孤立的进程结点PI（如某进程既无已分配的资源也不需申请资源，即既无分配边又无申请边，则该进程结点是孤立结点），让它获得所需资源而继续运行直至完毕，再释放它拥有的所有的资源，这相当于取消PI的分配边和请求边，使它成为孤立结点。经过以上简化，如所有的进程结点都是孤

55、立结点则称资源分配图是可完全简化的。若不能通过任何过程使该图完全简化，则该图是不可完全简化的。资源分配图简化如下图：4/21/202367 R R1 1 R R2 2 R R1 1 R R2 2 。P1资源分配图的简化例：。P1P2。P1P2。P2。R R1 1 R R2 24/21/202368死锁的检测-12 2。死锁定理：。死锁定理：S为死锁状态的充分条件是：尚且仅当S状态的资源分配图是不可完全简化的，该充分条件称为死锁定理。3。死锁检测的数据和算法。死锁检测的数据和算法类似于银行家算法。4/21/202369（5）死锁的解除n当检测死锁的软件判别死锁存在时判别死锁存在时，就要解除死锁就

56、要解除死锁，使系统从死锁中恢复。n第一种是强制性地从系统中撤消一个或多个死锁的进程以断第一种是强制性地从系统中撤消一个或多个死锁的进程以断开循环等待链开循环等待链，并收回分配给终止进程的全部资源供剩下的进程使用。借助于撤消进程来解除死锁可以使用两种方法。一种是撤消全部的死锁进程，这显然会断开死锁环路，但代价太大。另一种方法是逐个撤消死锁的进程直至死锁环路消除。这里存在一个按照什么原则进行逐个撤消进程的问题。目前较实用而又简便的方法是撤消那些代价最小的进程。所谓影响一个进程的撤消代价因素有该进程的优先权，该进程运行到今的运行代价（包括CPU时间，使用资源的种类和时间等）、与相关的作业类型和外部代价等。4/21/202370死锁的解除-1n死锁恢复的另一种办法是使用一个有效的挂起和解除机构死锁恢复的另一种办法是使用一个有效的挂起和解除机构来挂起一些死锁的进程来挂起一些死锁的进程，其实质是从被挂起的进程那里抢占资源以解除死锁，许多学者认为在此领域的研究工作比起其它死锁恢复的办法更为重要。例如一个系统提供了检查点和重新启动的便利的话，我们可以暂时仃止一个系统，而后从各进程的最近的检查点（系统保留了检查点的状态）逐次地重新启动。这既可以从死锁中恢复，又使进程损失最小（从检查点以后的损失）。但许多系统还没有此功能，在IBM4300系列等机器上提供了此类功能。4/21/202371