第四章-调度与死锁---jxhncunet8083ppt课件

1、第四章 调度与死锁,教学目的与要求： 1. 掌握调度与死锁的基本概念 2. 理解个调度算法和死锁地解决策略 3. 了解OS/2操作系统的调度 重点与难点： 1. 调度类型与调度算法 2. 多级反馈队列调度算法 3. 死锁的预防与银行家算法,2,主要内容： 4.1 调度的类型和模型 4.2 调度算法 4.3 实时系统中的调度 4.4 多处理机调度 4.6 死锁的基本概念 4.7 死锁的检测和解除 4.8 死锁的预防和避免 4.9 作业,3,4.1 调度的类型和模型,4.1.1 调度类型 作业从进入系统并驻留在外存的后备队列上开始，到作业运行完毕，可能要经历下述三级调度 一高级调度，也叫作业调度或

2、长期调度，主要问题有 1.接纳多少个作业 2.接纳哪些作业 二低级调度，也叫进程调度或者短期调度 低级调度可采用非抢占方式和抢占方式两种 三中级调度，也叫中期调度 主要目的是为了提高内存的使用效率和系统吞吐量,4,4.1.2 调度队列模型 在OS中的任何一种调度都涉及到进程队列，由此形成了三种类型的调度队列模型： 1仅有进程调度的调度队列模型 2具有高级和低级调度的调度队列模型 3同时具有三级调度的调度队列模型 4.1.3 选择调度方式和算法的若干准则 一、 面向用户的准则 1.周转时间短,5,周转时间：是指从作业提交给系统开始到作业完成为止的这段时间间隔。包括四个部分： （1）作业在外存后备

3、队列上等待调度的时间； （2）进程在就绪队列上等待调度的时间； （3）进程在CPU上运行的时间； （4）等待I/O操作完成的时间 2.响应时间快 响应时间：是从用户通过键盘提交一个请求开始，直到系统首次产生响应为止的时间。包括三部分：,6,（1）请求信息传送到处理机的时间； （2）处理机处理信息的时间； （3）将形成的响应（处理结果）回送终端显示器的时间。 3.截止时间的保证 截止时间：是指某任务必须开始执行的最迟时间（即开始截止时间），或必须完成的最迟时间（即完成截止时间）。 4.优先权准则 优先权：是为了及时处理某些紧急作业而采取的一种措施。,7,二、 面向系统的准则（大中型系统中考虑较多

4、） 1.系统吞吐量高，即单位时间内完成较多的作业 2.处理机利用率好 3.各类资源的平衡利用,8,4.2调度算法,所谓调度算法，就是根据系统的资源分配策略所规定的资源分配算法。 一 先来先服务（FCFS）调度算法 1将用户作业和就绪进程按提交顺序或变为就绪状态的先后排成队列，并按照先来先服务的方式进行调度处理，是一种最普遍和最简单的方法。 2对于那些执行时间较短的作业或进程来说，如果它们在某些执行时间很长的作业或进程之后到达，则它们将等待很长时间。,9,3在实际操作系统中，尽管很少单独使用FCFS算法，但和其他一些算法配合起来，FCFS算法还是使用得相当多的。 二 时间片轮转调度算法 1轮转法

5、的基本思路是让每个进程在就绪队列中的等待时间与享受服务的时间成比例。轮转法的基本概念是将CPU的处理时间分成固定大小的时间片。 2轮转法只能用来调度分配那些可以抢占的资源。将它们随时剥夺再分配给别的进程。作业调度不使用轮转法。,10,3在轮转法中，时间片长度的选取非常重要。时间片长度的选择会直接影响系统开销和响应时间。如果时间片长度过短，则调度程序剥夺处理机的次数增多。这将使进程切换次数也大大增加，从而加重系统开销。如果时间片长度选择过长，比方说一个时间片能保证就绪队列中所需执行时间最长的进程能执行完毕，则轮转法变成了先来先服务法。 三 多级反馈轮转调度算法 1对加入到就绪队列的进程区别对待，

6、即不同的情况给予不同的优先级和时间片，以进一步改善系统服务质量和效率。,11,这样，当一个进程在执行完它的时间片之后，或从睡眠中被唤醒以及被创建之后，将进入不同的就绪队列。 2多级反馈轮转法与优先级法在原理上的区别是，一个进程在它执行结束之前，可能需要反复多次通过反馈循环执行，而不是优先级法中的一次执行。 四优先权调度算法 1优先级法可被用作作业或进程的调度策略。该算法的核心是确定进程或作业的优先级。,12,2确定优先级的方法可分为静态法和动态法。静态法根据作业或进程的静态特性，在作业或进程开始执行之前就确定它们的优先级，一旦开始执行之后就不能改变。动态法则不然，它把作业或进程的静态特性和动态

7、特性结合起来确定作业或进程的优先级，随着作业或进程的执行过程，其优先级不断变化。 3基于静态优先级调度算法实现简单，系统开销小，但由于静态优先级一旦确定之后，直到执行结束为止始终保持不变，从而系统效率较低，调度性能不高。现在的操作系统中，如果使用优先级调度的话，则大多采用动态优先级的调度策略。,13,进程的动态优先级一般根据以下原则确定： (1) 根据进程占有CPU时间的长短来决定。一个进程占有处理机的时间愈长，则在被阻塞之后再次获得调度的优先级就越低，反之，其获得调度的可能性就会越大。 (2) 根据就绪进程等待CPU的时间长短来决定。一个就绪进程在就绪队列中等待的时间越长，则它获得调度选中的

8、优先级就越高。 五. 最短作业优先调度算法（SJF） 1选择那些估计需要执行时间最短的作业投入执行，为它们创建进程和分配资源，已获得较好的吞吐量。,14,2最短作业优先法有可能使得那些长作业永远得不到调度执行的机会。产生饥饿现象。 六. 最高响应比优先调度算法（HRN） 1最高响应比优先法是对FCFS方式和SJF 方式的一种综合平衡。HRN调度策略同时考虑每个作业的等待时间长短和估计需要的执行时间长短，选出响应比最高的作业投入执行。 2响应比R定义如下： R=(W+T)/T=1+W/T 其中T为该作业估计需要的执行时间，W为作业在后备状态队列中的等待时间。,15,3每当要进行作业调度时，系统计

9、算每个作业的响应比，选择其中R最大者投入执行。 4 HRN吞吐量将小于采用SJF 法时的吞吐量。 5由于每次调度前要计算响应比，系统开销也要相应增加。,16,4.3 实时系统中的调度,4.3.1 对实时系统的要求 1.提供必要的调度信息 （1）就绪时间。（2）开始截止时间和完成截止时间。（3）处理时间。（4）资源要求。（5）优先级。 2.调度方式 在实时控制系统中，广泛采用抢占调度方式。 3.具有快速响应外部中断的能力 4.快速任务分派,17,4.3.2 实时调度算法 1.时间片轮转调度算法 2.非抢占优先权调度算法 3.基于时钟中断抢占的优先权调度算法 4.立即抢占的优先权调度,18,4.3

10、.3 实时调度实例 一、具有开始截止时间的非周期实时任务的调度 在事前能知道各实时任务的开始截止时间，且对调度时延要求不太严格的情况下，系统采用最早截止时间优先的非剥夺调度策略。 任务1、2、3、4的调度 二、具有完成截止时间的周期性实时任务的调度 A：每20ms执行一次，执行时间为10ms。 B：每50ms执行一次，执行时间为25ms,19,4.4 多处理机调度,4.4.1 进程调度 一、同构型多处理机系统中的进程调度 1.静态分配（Static Assignment） 2.动态分配（Dynamic Assignment） 3.自调度（Self-Scheduling） 二、异构型多处理机系统

11、中的进程调度,20,4.4.2 自调度 1.自调度方式。系统中有一个公共的线程或进程的就绪队列，所有的处理机在空闲时，都可自己从该队列中取出一个进程或线程运行。 2.成组调度。这时由系统将一组相关的进程或线程，同时分配到组处理机上运行，进程或线程与处理机一对应。 3.专用处理机分配方式。它是将同属于一个应用程序的一组线程，分配到一组处理机上，在应用程序末结束前，处理机专用于处理这组线程。,21,4.4.3 成组调度 这时由系统将一组相关的进程或线程，同时分配到一组处理机上运行，进程或线程与处理机一一对应。 1.面向所有的应用程序平均分配处理机时间 2.面向所有的线程平均分配处理机时间 4.4.

12、4 专用处理机分配 它是将同属于一个应用程序的一组线程，分配到一组处理机上，在应用程序末结束前，处理机专用于处理这组线程。 把这种调度方式用于并发程度相当高的多处理机环境，是根据下述一些理由：,22,（1）在具有数十个乃至数百个处理机的高度并行的系统中，单个处理机的利用率已远不像在单机系统中那么重要。 （2）可以避免了进程或线程的切换，从而可大大地加速程序的完成。 根据实践证明：在同时加工的应用程序中，其线程数的总和不应超过系统中处理机的数目。,23,4.6 死锁的基本概念,死锁的定义: 所谓死锁（Deadlock），是指多个进程因竞争资源而造成的一种僵局，若无外力作用，这些进程都将永远不能再

13、向前推进。,24,4.6.1 产生死锁的原因 产生死锁的原因可归结为两点： 1.竞争资源，当系统中各进程所共享的资源不足以同满足个共享进程的需要时，则可能引发竞争而导致死锁。 2.进程推进顺序非法，导致请求和释放资源的顺序不当，从而引发死锁。 一、竞争资源引起死锁 1.可剥夺和非剥夺性资源 可剥夺性资源，如：处理机和主存； 非剥夺性资源，如：磁带机、打印机等等,25,2.竞争非剥夺性资源和临时性资源 由于资源的动态分配，各进程获得一部分资源同时又请求别的资源，由于资源的非剥夺性，往往造成循环等待的死锁局面。 二、进程推进顺序不当引起死锁 1.进程推进顺序合法 进程在其它进程释放共享资源之后才对

14、该资源提出请求。 2.进程推进顺序非法,26,4.6.2 产生死锁的必要条件 死锁的起因是并发进程的资源竞争。产生死锁的根本原因在于系统提供的资源个数少于并发进程所要求的该类资源数。显然，由于资源的有限性，不可能为所有要求资源的进程无限制地提供资源。但是，可以采用适当的资源分配算法，以达到消除死锁的目的。为此，先看看产生死锁的四个必要条件： 1.互斥条件：共享资源的互斥使用 2.请求和保持条件：资源的部分分配原因 3.不剥夺条件：进程已获得的资源在未使用完之前，不允许被剥夺 4.环路等待条件：当死锁产生时，必然形成环路等待链。,27,4.6.3 处理死锁的基本方法 1.预防死锁 2.避免死锁

15、3. 死锁的检测与解除 死锁的检测和解除措施，有可能使系统获得较好的资源利用宰相系统吞吐量，但在实现上难度也最大。,28,4.7 死锁的预防和避免,4.7.1 死锁的预防 1摒弃“请求和保持”条件 这种方法不能解决访问那些不允许被同时访问的资源时所带来的死锁问题。 2摒弃”不剥夺”条件 即预先分配各并发进程所需要的全部资源。此法有如下缺点： (1) 一般情况下，一个进程在执行之前很难获得它所需要的全部资源。,29,(2) 无论所需资源何时用到，一个进程只有在所有要求资源都得到满足之后才开始执行。 (3) 对于那些不经常使用的资源，进程在生存过程期间一直占用它们是一种极大的浪费。 (4) 降低了

16、进程的并发性。 3摒弃“环路等待”条件 即把资源分类按顺序排列，使进程在申请、保持资源时不形成环路。,30,4.7.2 系统的安全状态 一、安全状态 所谓安全状态，是指系统能按某种顺序如（称序列为安全序列），来为每个进程分配其所需资源，直至最大需求，使每个进程都可顺序完成。若系统不存在这样一个安全序列，则称系统处于不安全状态。 虽然并非所有不安全状态都是死锁状态，但当系统进入不安全状态后，便可能进而进入死锁状态；反之，只要系统处于安全状态，系统便可避免进入死锁状态。因此，避免死锁的实质在于：如何使系统不进入不安全状态。,31,二、安全状态举例 我们通过一个例子来说明安全性。假定系统有三个进程P

17、1、P2和P3，共有12台磁带机。进程P1总共要求10台磁带机，P2和P3分别要求4台和9台。设在T0时刻，进程Pl、P2和P3已分别获得5台、2台和2台，尚有3台空闲未分，如下表所示： 进程 最大需求 已分配 可用 P1 10 5 3 P2 4 2 P3 9 2,32,三、由安全状态向不安全状态的转换 如果不按照安全序列分配资源，则系统可能会由安全状态进入不安全状态。,33,4.7.3 利用银行家算法避免死锁 一、银行家算法中的数据结构 1.可利用资源向量Available 它是一个含有m个元素的数组，其中的每一个元素代表一类可利用的资源数目，其初始值是系统中所配置的该类全部可用资源数目。其

18、数值随该类资源的分配和回收而动态地改变。 2.最大需求矩阵Max 这是个nm的矩阵，它定义了系统中n个进程中的每一个进程对m类资源的最大需求。如果Max(i，j)k，表示进程i需要Rj类资源的最大数目为k。,34,3.分配短阵Allocation 这是一个nm的矩阵，它定义了系统中每一类资源当前已分配给每个进程的资源数。如果Allocation(i,j)k，表示进程i当前已分得Rj类资源的数目为k。 4.需求矩阵：Need 它是一个nm的矩阵，用以表示每一个进程尚需的各类资源数，如果 ，表示进程i还需要Rj类资源k个，方能完成其任务。 上述三个矩阵间存在下述关系： Needi,j=Maxi,j

19、-Allocationi,j,35,二、银行家算法 设Requesti是进程Pi的请求向量。如果Requestijk，表示进程只需要k个Rj类型的资源。当Pi发出资源请求后，系统按下述步骤进行检查： （1）如果Requesti=Needi ，则转向步骤2；否则，认为出错，因为它所需要的资源数已超过它所宣布的最大值。 （2）如果 Requesti =Available ，则转向步骤3；否则，表示系统中尚无足够的资源，Pi必须等待。,36,（3）系统试探把要求的资源分配给进程P，并修改下面数据结构中的数值： Available:=Available - Requesti Allocation:=A

20、llocation +Requesti; Needi:= Needi - Requesti （4）系统执行安全性算法，检查此次资源分配后，系统是否处于安全状态。若安全，才正式将资源分配给进程Pi，以完成本次分配；否则，将试探分配作废，恢复原来的资源分配状态，让进程Pi等待,37,三、安全性算法 系统所执行的安全性算法可描述如下： （1）设置两个向量 工作向量Work,它表示系统可提供给进程继续运行所需要的各类资源数目，它含有m个元素，执行安全算法开始时，Work = Available。 Finish,它表示系统是否有足够的资源分配给进程，使之运行完成，开始时将Finishi:=false ；

21、当有足够资源分配给进程时，再执行 Finishi:=true 。,38,（2）从进程集合中找到一个能满足下述条件的进程： Finishi:=false Needi=Work 如找到，执行步骤（3）；否则，执行步骤（4）。 （3）当进程Pi获得资源后，可顺利执行，直至完成，并释放出分配给它的资源，故应执行： Work:=Work+Allocationi; Finishi:=true; go to step 2； （4）如果所有进程的Finishi:=true ，则表示系统处于安全状态；否则，系统处于不安全状态。,39,四、银行家算法举例 假定系统中有五个进程：P0，P1，P2，P3，P4和三种类型的资源A，B，C，每一种资源的数量分别为10、5、7，在T0时刻的资源分配情况如图417(见教材P127)所示。 1. T0时刻的安全性 2. P1请求资源: Request1=(1,0,2) 3. P4请求资源: Request4=(3,3,0) 4. P0请求资源: Request0=(0,2,0),40,4.8 死锁的检测和解除,4.8.1 死锁的检测 当系统为进程分配资源时，若未采取任何限制性措施，则系统必须提供检测和解除死锁的手段。为此，系统必须： （1）保存有关资源