07处理机调度讲解课件

Page12023/7/22第三章处理机调度与死锁钱斌dnhistory@Page22023/7/22处理机调度

1.调度的基本概念

2.调度时机、切换与过程

3.调度的基本准则

4.调度方式

5.典型调度算法先来先服务调度算法;短作业(短进程、短线程)优先调度算法;时间片轮转调度算法;优先级调度算法;高响应比优先调度算法;多级反馈队列调度算法。Page32023/7/22死锁

1.死锁的概念

2.死锁处理策略

3.死锁预防

4.死锁避免系统安全状态：银行家算法。

5.死锁检测和解除Page42023/7/22第三章处理机调度与死锁重点掌握进程调度算法，各适用于何种情况

理解常用的几种实时调度算法

理解产生死锁的原因

掌握银行家算法避免死锁难点多道程序设计中的各种调度算法

响应比高者优先调度算法的计算过程

银行家算法

Page52023/7/22第三章处理机调度与死锁知识点处理机调度及调度算法多处理机环境下的进程（线程）调度方式产生死锁的原因和必要条件预防死锁的方法，死锁的检测与解除银行家算法Page62023/7/22第三章处理机调度与死锁处理机是计算机系统中的重要资源在多道程序环境下，进程数目通常多于处理机的数目系统必须按一定方法动态地把处理机分配给就绪队列中的一个进程处理机利用率和系统性能（吞吐量、响应时间）在很大程度上取决于处理机调度分配处理机的任务是由进程调度程序完成的。它是操作系统设计的中心问题之一。WHAT：按什么原则分配CPU—进程调度算法WHEN：何时分配CPU—进程调度的时机

HOW：如何分配CPU—CPU调度过程（进程的上下文切换）Page72023/7/22第三章处理机调度与死锁

处理机调度的基本概念作业与作业调度算法进程调度实时调度死锁概述预防死锁避免死锁死锁的检测与解除Page82023/7/22处理机调度的基本概念

高级、中级和低级调度进程调度的任务确定算法的原则进程调度方式调度队列模型选择调度方式和调度算法的若干准则Page92023/7/22处理机调度的基本概念作业是用户在一次解题或一个事务处理过程中要求计算机系统所做工作的集合，包括用户程序、所需的数据及命令等作业的状态：一个作业进入系统到运行结束，一般需要经历收容、运行、完成三个阶段，与之相对应的是作业的三种状态后备状态运行状态完成状态Page102023/7/22运行状态处理机调度的基本概念后备状态完成状态就绪阻塞执行I/O完成I/O请求时间片完作业注册作业调度进程调度终止作业作业状态间转换Page112023/7/223.1处理机调度的基本概念3.1.1高级、中级和低级调度1.高级调度(HighScheduling)2.低级调度(LowLevelScheduling)3.中级调度(Intermediate-LevelScheduling)Page122023/7/22高级、中级和低级调度高级调度(HighScheduling)

作业调度或长程调度（Long-TermScheduling）主要任务是按一定的原则对外存上处于后备状态的作业进行选择，给选中的作业分配内存、输入/输出设备等必要的资源，并建立相应的进程，放入就绪队列，以使该作业的进程获得竞争处理机的权利也称为接纳调度（AdmissionScheduling）高级调度的时间尺度通常是分钟、小时或天Page132023/7/22高级、中级和低级调度在每次作业调度时，须决定：接纳多少个作业即允许多少个作业同时在内存中运行，取决于多道程序度（DegreeofMultiprogramming）作业太多服务质量下降作业太少资源利用率低接纳哪些作业

取决于作业调度算法先来先服务短作业优先作业优先权调度响应比调度→周转时间太长→系统吞吐量太低

适当的折衷多道程序度：即允许多少个作业同时在内存中运行。周转时间：从作业被提交给系统开始，到作业完成为止的这段时间间隔。吞吐量：是指在单位时间内系统所完成的作业数。Page142023/7/22高级、中级和低级调度低级调度

进程调度或短程调度（Short-TermScheduling）主要任务是按照某种策略和方法选取一个处于就绪状态的进程，将处理机分配给它常见的低级调度有非抢占式和抢占式两种低级调度的时间尺度通常是毫秒级的。由于低级调度算法的频繁使用，要求在实现时做到高效Page152023/7/22高级、中级和低级调度中级调度(Intermediate-LevelScheduling)

中程调度(Medium-TermScheduling)引入目的是为了提高内存利用率和系统吞吐量。使那些暂时不能运行的进程不再占用宝贵的内存资源，而将它们调至外存上去等待主要任务是按照给定的原则和策略，将处于外存对换区中的重又具备运行条件的就绪进程调入内存，或将处于内存就绪状态或内存阻塞状态的进程交换到外存对换区Page162023/7/22处理机调度的基本概念

高级、中级和低级调度进程调度的任务确定算法的原则进程调度方式调度队列模型选择调度方式和调度算法的若干准则Page172023/7/22进程调度的任务

进程调度的任务是控制、协调进程对CPU的竞争,即按一定的调度算法从就绪队列中选中一个进程，把CPU的使用权交给被选中的进程Page182023/7/22处理机调度的基本概念

高级、中级和低级调度进程调度的任务

确定算法的原则进程调度方式调度队列模型选择调度方式和调度算法的若干准则Page192023/7/22确定算法的原则

具有公平性资源利用率高（特别是CPU利用率）在交互式系统情况下要追求响应时间（越短越好）在批处理系统情况下要追求系统吞吐量Page202023/7/22处理机调度的基本概念

高级、中级和低级调度进程调度的任务确定算法的原则

进程调度方式调度队列模型选择调度方式和调度算法的若干准则Page212023/7/22进程调度方式非抢占方式(Non-preemptiveMode)抢占方式(PreemptiveMode)Page222023/7/22处理机调度的基本概念

高级、中级和低级调度进程调度的任务确定算法的原则进程调度方式

调度队列模型选择调度方式和调度算法的若干准则Page232023/7/22调度队列模型仅有进程调度的调度队列模型具有高级和低级调度的调度队列模型同时具有三级调度的调度队列模型Page242023/7/22调度队列模型仅有进程调度的调度队列模型就绪队列阻塞队列进程调度CPU进程完成等待事件交互用户事件出现时间片完Page252023/7/22调度队列模型进程调度CPU进程完成时间片完就绪队列…12等待事件等待事件等待事件n12n事件出现事件出现…事件出现后备队列作业调度……与上一模型的主要区别：就绪队列的形式；设置多个阻塞队列阻队列塞2阻队列塞n阻队列塞1Page262023/7/22调度队列模型同时具有三级调度的调度队列模型就绪队列进程调度就绪，挂起队列中级调度阻塞，挂起队列阻塞队列等待事件进程完成时间片完作业调度交互型作业后备队列批量作业挂起挂起事件出现事件出现CPUPage272023/7/22处理机调度的基本概念

高级、中级和低级调度进程调度的任务确定算法的原则进程调度方式调度队列模型选择调度方式和调度算法的若干准则如果你是用户，你希望系统如何为你服务，如何考虑？？如果你是调度者，从系统整体角度出发，应如何考虑？？Page282023/7/223.1.3选择调度方式和调度算法的若干准则1.面向用户的准则2.面向系统的准则Page292023/7/223.1.3选择调度方式和调度算法的若干准则1.面向用户的准则(1)周转时间短。

(2)响应时间快。(3)截止时间的保证。(4)优先权准则。Page302023/7/22选择调度方式和调度算法的若干准则面向用户的准则周转时间短平均周转时间带权周转时间：进程（或作业）的周转时间T与系统为它提供服务的时间TS之比，即W=T/TS

。而平均带权周转时间则可表示为:Page312023/7/22选择调度方式和调度算法的若干准则面向用户的准则响应时间快响应时间是指从用户通过键盘提交一个请求开始，直至系统中首次产生响应为止的时间交互式系统用周转时间衡量不是最佳截止时间保证截止时间是指某任务必须开始执行的最迟时间或必须完成的最迟时间截止时间是实时系统中的重要指标Page322023/7/22选择调度方式和调度算法的若干准则面向用户的准则等待时间短等待时间是在就绪队列中等待所花的时间调度算法并不影响进程运行和执行I/O的时间量；只影响进程在就绪队列中等待所花费的时间优先权准则在批处理、实时和分时系统中都可以选择优先权准则，以便让紧急任务先处理有时还选择抢占式调度方式Page332023/7/22选择调度方式和调度算法的若干准则面向系统的准则系统吞吐量高吞吐量指单位时间内系统所完成的作业数作业调度的方式和算法对吞吐量的大小有较大影响处理机利用率高各类资源的平衡利用使内存、外存和I/O设备的利用率高基于这样的准则，你设计操作系统的调度策略应如何？Page342023/7/22第三章处理机调度与死锁处理机调度的基本概念

作业与作业调度算法进程调度实时调度死锁概述预防死锁避免死锁死锁的检测与解除Page352023/7/22调度算法在OS中调度的实质是一种资源分配，因而调度算法是指：根据系统的资源分配策略所规定的资源分配算法问题提出如何制定分配策略：对不同的系统和系统目标，通常采用不同的算法，如短作业优先，时间片轮转等有些算法适用于作业调度，有些适用于进程调度，有些两者皆可Page362023/7/22调度算法

先来先服务和短作业优先算法高优先权优先调度算法基于时间片的轮转调度算法Page372023/7/22先来先服务和短作业优先算法进程名到达时间服务时间开始时间完成时间周转时间带权周转时间平均04A13B25C32D44E044476先来先服务（先进先出）：712101214111418141225.53.592.8AAAABBBCCCCCDDEEEE05101518tPage382023/7/22先来先服务和短作业优先算法

先来先服务（先进先出）优缺点

比较有利于长作业（进程），而不利于短作业（进程）有利于CPU繁忙型作业（进程），而不利于I/O繁忙型作业（进程）用于批处理系统，不适于分时系统Page392023/7/22先来先服务和短作业优先算法进程名到达时间服务时间开始时间完成时间周转时间带权周转时间平均04A13B25C32D44E0441短作业/短进程优先（SJF/SPF）：4633/26988/391399/413181616/540/52.1AAAABBBCCCCCDDEEEE05101518tPage402023/7/22先来先服务和短作业优先算法SJ(P)F调度算法也存在不容忽视的缺点对长作业不利。严重的是，若一长作业(进程)进入系统的后备队列(就绪队列)，由于调度程序总是优先调度那些(即使是后进来的)短作业(进程)，将导致长作业(进程)长期不被调度——饥饿完全未考虑作业(进程)的紧迫程度，因而不能保证紧迫性作业(进程)会被及时处理由于作业(进程)的长短只是根据用户所提供的估计执行时间而定的，而用户又可能会有意或无意地缩短其作业的估计运行时间，致使该算法不一定能真正做到短作业优先调度。Page412023/7/22调度算法先来先服务和短作业优先算法高优先权优先调度算法基于时间片的轮转调度算法Page422023/7/22高优先权优先（HPF，HighestPriorityFirst）调度算法优先权调度算法的类型非抢占式优先权调度算法抢占式优先权调度算法③Page432023/7/22高优先权优先调度算法优先权的类型静态优先权动态优先权Page442023/7/22进程名到达时间服务时间静态优先权开始时间完成时间周转时间带权周转时间平均静态优先权，非抢占式（1为高优先权）高优先权优先调度算法04A413B225C332D544E1044148418111010/311161414/516181515/29.42.93考虑一下抢占式，情况如何？Page452023/7/22高优先权优先调度算法高响应比优先调度算法（HRF）是FCFS和SJF的结合，克服了两种算法的缺点调度策略：响应比最高的作业优先启动因等待时间+服务时间=该作业的响应时间，故该优先权又相当于响应比RP。据此，又可表示为④Page462023/7/22高优先权优先调度算法对HRF的小结等待时间相同的作业，则要求服务的时间愈短，其优先权愈高，要求服务的时间相同的作业，则等待时间愈长，其优先权愈高，长作业，优先权随等待时间的增加而提高，其等待时间足够长时，其优先权便可升到很高，从而也可获得处理机是一种折衷，既照顾了短作业，又考虑了作业到达的先后次序，又不会使长作业长期得不到服务。缺点：要进行响应比计算，增加了系统开销——对短作业有利——是先来先服务——对长作业有利Page472023/7/22调度算法先来先服务和短作业优先算法高优先权优先调度算法基于时间片的轮转调度算法Page482023/7/22基于时间片的轮转调度算法进程名到达时间服务时间开始时间完成时间周转时间带权周转时间平均ABCDEABCDEABCEACEC05101518t04A03B05C02D04E012349121517181515/41111/31616/566/21313/412.22.12若到达时间为0、1、2、3、4，又如何？Page492023/7/22多级反馈队列调度算法设置多个就绪队列，并为各个队列赋予不同的优先级第一个队列的优先级最高，第二个队列次之，其余各队列的优先权逐个降低该算法赋予各个队列中进程执行时间片的大小也各不相同，在优先权愈高的队列中，为每个进程所规定的执行时间片就愈小。例如，第二个队列的时间片要比第一个队列的时间片长一倍，……，第i+1个队列的时间片要比第i个队列的时间片长一倍⑦Page502023/7/22就绪队列1基于时间片的轮转调度算法就绪队列2就绪队列3就绪队列nS1S2S3至CPU至CPU至CPU至CPU(时间片：S1＜S2＜S3)调度方式高低优先级时间片小大Sn按FIFO原则排队等待调度尚未完成转入第二队列的末尾，按FIFO原则等待调度采取按时间片轮转的方式运行因等待而放弃CPU后，进入阻塞队列，一旦等待的事件发生，则回到原来的就绪队列Page512023/7/22进程调度的时机当一个进程运行完毕或由于某种错误而终止运行当一个进程在运行中处于等待状态（等待I/O）分时系统中时间片到当有一个优先级更高的进程就绪（可抢占式）例如：新创建一个进程，一个阻塞进程变成就绪在进程通信中，执行中的进程执行了某种原语操作（P操作，阻塞原语，唤醒原语）Page522023/7/22何时切换进程只要OS取得对CPU的控制，进程切换就可能发生:超级用户调用来自程序的显式请求(如：打开文件)，该进程通常会被阻塞陷阱最末一条指令导致出错，会引起进程移至退出状态中断外部因素影响当前指令的执行，控制被转移至IH（中断处理程序）Page532023/7/22引起进程调度的原因正在执行的进程执行完毕或因发生某事件而不能再继续执行；执行中的进程因提出I/O请求而暂停执行；在进程通信或同步过程中执行了某种原语操作如P操作、阻塞、挂起原语等；在可剥夺式调度中，有比当前进程优先权更高的进程进入就绪队列；在时间片轮转法中，时间片完。通常系统是按先来先服务或优先权形式来组织调度队列。Page542023/7/22第三章处理机调度与死锁处理机调度的基本概念

作业和作业调度算法进程调度实时调度死锁概述预防死锁避免死锁死锁的检测与解除3.4.1实现实时调度的基本条件1．提供必要的调度信息（1）就绪时间；（2）开始/完成截止时间；（3）处理时间；（4）资源要求；（5）优先级；2．系统处理能力强3.4实时调度Ci为处理时间，Pi为周期时间（基于周期性实时任务）3.4.1实现实时调度的基本条件3.采用抢占调度方式剥夺方式：一般都采用此非剥夺方式（实现简单）：一般应使实时任务较小，以及时放弃CPU。4.具有快速切换机制具有快速响应外部中断能力。快速任务分派3.4实时调度3.4.2实时调度算法的分类1非抢占式调度算法时间片轮转 秒级非抢占优先权（协同） 秒~毫秒级2抢占式调度算法时钟中断抢占优先权 毫秒级基于抢占点抢占立即抢占immediatepreemption毫秒~微秒级只要不在临界区即抢占（中断引发）进程1进程2进程n实时进程调度时间实时进程要求调度调度实时进程运行a非抢占轮转调度当前进程实时进程实时进程要求调度当前进程运行完成b非抢占优先权调度调度时间c基于时钟中断抢占的优先权抢占调度当前进程实时进程实时进程要求调度抢占时刻（其它中断）b立即抢占优先权调度当前进程实时进程实时进程要求调度时钟中断到达时调度时间调度时间3.4.3常用的几种实时调度算法1.最早截止时间优先EDF（earliestdeadlinefirst)算法根据任务的截止时间来确定任务的优先级截止时间越早，优先级越高可以是抢占式或非抢占式最早截止时间优先EDF例134213421234t开始截止时间任务到达任务执行图3－6EDF算法用于非抢占调度方式2.最低松弛度优先LLF算法松弛度：若A进程需在200ms时完成，其本身运行需要100ms，当前时刻是10ms，则A的松弛度为：200－100－10＝90主要用于可抢占的调度方式中例：A1A2A3A4A5A6A7A8B1B2B3020406080100120140160t图3－8A/B任务每次必须完成的时间最低松弛度优先LLF算法(2)A1(10)A2(10)A3(10)A4(10)t01020304050607080t1=0B1(20)B1(5)B2(15)B2(10)t1t2t3t4t5t6t7t8Page642023/7/223.5死锁概述死锁的基本概念产生死锁的原因产生死锁的必要条件处理死锁的基本方法Page652023/7/22死锁的基本概念死锁的概念指多个进程因竞争共享资源而造成的一种僵局，若无外力作用，这些进程都将永远不能再向前推进。即：如果一组进程中，每个进程都在等待仅有该组进程中其他进程才能引发的事件，那么该组进程就称为死锁进程。Page662023/7/22死锁的基本概念关于死锁的一些结论参与死锁的进程最少是两个

参与死锁的进程至少有两个已经占有资源参与死锁的所有进程都在等待资源参与死锁的进程是当前系统中所有进程的子集注：如果死锁发生，会浪费大量系统资源，甚至导致系统崩溃。Page672023/7/22产生死锁的原因和必要条件死锁的基本概念产生死锁的原因产生死锁的必要条件处理死锁的基本方法Page682023/7/22产生死锁的原因竞争资源。当系统中供多个进程所共享的资源，不足以同时满足它们的需要时，引起它们对资源的竞争而产生死锁。

(2)进程间推进顺序非法。

进程在运行过程中，请求和释放资源的顺序不当，导致了进程死锁。

所谓死锁（Deadlock），是指多个进程因竞争资源而造成的一种僵局，若无外力作用，这些进程都将永远不能再向前推进。Page692023/7/22产生死锁的原因竞争资源引起进程死锁可剥夺和非剥夺性资源可剥夺性资源是指进程在获得这类资源后，该资源可以再被其他进程或系统剥夺，如处理机、内存等非剥夺性资源是指当系统把这类资源分配给某个进程后，再不能强行收回，只能在进程用完后自行释放，如磁带机、打印机等竞争非剥夺性资源系统中的非剥夺性资源由于数量有限而不能满足进程运行的需要，进程在运行过程中因争夺这些资源而限入僵局竞争临时性资源Page702023/7/22产生死锁的原因I/O设备共享时的死锁情况

若系统中只有一台打印机R1和一台读卡机R2，可供进程P1和P2共享。若形成环路，这样会产生死锁。R1R2P1P2分配分配请求请求Page712023/7/22产生死锁的原因

进程之间通信时的死锁S2P1S3P3S1P2产生P2产生P3产生要求接收要求接收要求接收Page722023/7/22产生死锁的原因进程推进顺序不当引起死锁P2Rel(R1)P2Rel(R2)P2Req(R1)P2Req(R2)P1Req(R1)P1Req(R2)P1Rel(R1)P1Rel(R2)①②③④D不安全区Page732023/7/22产生死锁的原因和必要条件死锁的基本概念产生死锁的原因产生死锁的必要条件处理死锁的基本方法Page742023/7/22产生死锁的必要条件互斥条件

进程对所分配到的资源进行排它性的使用请求和保持条件

进程已经至少保持了一个资源，但又提出了新的资源请求，而该资源又已被其他进程占有不剥夺条件

进程已获得的资源在未使用完之前不能被剥夺环路等待条件在发生死锁时，必然存在一个进程--资源循环等待的环形链Page752023/7/22产生死锁的原因和必要条件死锁的基本概念产生死锁的原因产生死锁的必要条件处理死锁的基本方法Page762023/7/22处理死锁的基本方法预防死锁避免死锁检测死锁解除死锁Page772023/7/22第三章处理机调度与死锁处理机调度的基本概念

作业与作业调度算法进程调度实时调度死锁概述预防死锁避免死锁死锁的检测与解除Page782023/7/223.6预防死锁摒弃“请求和保持”条件所有进程在开始运行之前必须一次性的申请整个运行过程所需的全部资源简单、易于实现、安全资源浪费严重进程延迟运行Page792023/7/22预防死锁摒弃“不剥夺”条件进程逐个地申请所需资源当一个已经保持了某些资源的进程申请新资源而不能得到满足时，必须放弃所有已保持的资源实现复杂、代价高昂延长了进程的周转时间，还增加了系统开销，降低了系统的吞吐量Page802023/7/22预防死锁摒弃“环路等待”条件系统将所有资源按类型分配序号并排队所有进程申请资源必须按序号递增的顺序资源利用率和系统吞吐量较高但在资源管理和资源申请方面仍有问题Page812023/7/223.7避免死锁系统安全状态利用银行家算法避免死锁Page822023/7/22产生死锁的原因进程推进顺序不当引起死锁P2Rel(R1)P2Rel(R2)P2Req(R1)P2Req(R2)P1Req(R1)P1Req(R2)P1Rel(R1)P1Rel(R2)①②③④DPage832023/7/22系统安全状态安全状态在避免死锁的方法中，允许进程动态地申请资源，但系统在进行资源分配之前，应先计算此次资源分配的安全性。若此次分配不会导致系统进入不安全状态，则将资源分配给进程；否则，令进程等待所谓安全状态，是指系统能按某种进程顺序(P1,P2,…，Pn)(称〈P1,P2,…,Pn〉序列为安全序列)，来为每个进程Pi分配其所需资源，直至满足每个进程对资源的最大需求，使每个进程都可顺利地完成。如果系统无法找到这样一个安全序列，则称系统处于不安全状态Page842023/7/223.7.2利用银行家算法避免死锁1.银行家算法中的数据结构(1)可利用资源向量Available。这是一个含有m个元素的数组，其中的每一个元素代表一类可利用的资源数目，其初始值是系统中所配置的该类全部可用资源的数目，其数值随该类资源的分配和回收而动态地改变。如果Available[j]=K，则表示系统中现有Rj类资源K个。

Page852023/7/22(2)最大需求矩阵Max。这是一个n×m的矩阵，它定义了系统中n个进程中的每一个进程对m类资源的最大需求。如果Max[i,j]=K，则表示进程i需要Rj类资源的最大数目为K。

(3)分配矩阵Allocation。这也是一个n×m的矩阵，它定义了系统中每一类资源当前已分配给每一进程的资源数。如果Allocation[i,j]=K，表示进程i当前已分Rj类资源的数目为K。

(4)需求矩阵Need。这也是一个n×m的矩阵，用以表示每一个进程尚需的各类资源数。如果Need[i,j]=K，则表示进程i还需要Rj类资源K个，方能完成其任务。Need[i,j]=Max[i,j]–Allocation[i,j]Page862023/7/22

2.银行家算法设Requesti是进程Pi的请求向量，如果Requesti[j]=K，表示进程Pi需要K个Rj类型的资源。当Pi发出资源请求后，系统按下述步骤进行检查：

(1)如果Requesti[j]≤Need[i,j]，便转向步骤(2)；否则认为出错，因为它所需要的资源数已超过它所宣布的最大值。

(2)如果Requesti[j]≤Available[j]，便转向步骤(3)；否则，表示尚无足够资源，Pi须等待。Page872023/7/22(3)系统试探着把资源分配给进程Pi，并修改下面数据结构中的数值：

Available[j]:=Available[j]-Requesti[j];Allocation[i,j]:=Allocation[i,j]+Requesti[j];Need[i,j]:=Need[i,j]-Requesti[j];(4)系统执行安全性算法，检查此次资源分配后，系统是否处于安全状态。若安全，才正式将资源分配给进程Pi，以完成本次分配；否则，将本次的试探分配作废，恢复原来的资源分配状态，让进程Pi等待。Page882023/7/224.银行家算法之例

假定系统中有五个进程｛P0,P1,P2,P3,P4｝和三类资源｛A,B,C｝，各种资源的数量分别为10、5、7，在T0时刻的资源分配情况如图3-15所示。图3-15T0时刻的资源分配表2C3B11023C31024B21200C01001B32223C32025B404P4639P23707P0022P3123P1AAAAAvailableNeedAllocationMaxNeed[i,j]=Max[i,j]–Allocation[i,j]Page892023/7/22(1)T0时刻的安全性：图3-16T0时刻的安全序列truetruetruetruetrueFinish77532C54443B02210C10010B30112