第3章处理机调试与死锁.

1第3章处理机调度与死锁3.1处理机调度的基本概念3.2调度算法3.3实时调度3.4产生死锁的原因和必要条件3.5预防和避免死锁的方法3.6死锁的检测和解除23.1处理机调度的基本概念3.1.1高级、中级和低级调度1．高级调度——又称作业调度或长调度用于决定把外存上后备队列中哪些作业调入内存，并为它们创建进程、分配必要的资源，然后将新创建的进程插入到就绪队列中，准备运行。定义每次作业调度，都需做以下两个决定：●接纳多少个作业——取决于多道程序度▲内存中同时运行的作业数目太多，会影响系统的服务质量。如，周转时间长。▲内存中同时运行的作业数目太少，会导致系统资源利用率和系统吞吐量低。●接纳哪些作业——取决于调度算法33.1处理机调度的基本概念2．低级调度又称进程调度或短调度。是最基本的调度，三种类型OS中，都必须配置此调度。定义用来决定就绪队列中的哪个进程应获得处理机，然后再由分派程序执行把处理机分配给该进程的具体操作。进程调度可采用下述两种调度方式：（1）非抢占方式（2）抢占方式一旦把处理机分配给某进程后，便让它一直执行，直到该进程完成或发生某事件而被阻塞时，才把处理机分配给其它进程，决不允许某进程抢占已经分配出去的处理机。优点：实现简单，系统开销小。缺点：难于满足紧急任务的要求。允许调度程序根据某种原则，暂停某个正在执行的进程，将已分配给该进程的处理机重新分配给另一进程。抢占原则有：优先权原则；短作业优先原则；时间片原则。43.1处理机调度的基本概念3.中级调度挂起和激活，存储器管理中的对换功能。主要目的：为了提高内存的利用率和系统的吞吐量。主要介绍进程调度和作业调度。三种调度相比较：进程调度的运行频率最高作业调度频率最低中级调度界于之间53.1.2调度队列模型三种类型的调度队列模型：1.仅有进程调度的调度队列模型在分时系统中，通常仅设置了进程调度。常把就绪进程组织成FIFO队列形式。阻塞队列一般可能有多个。就绪队列阻塞队列交互用户进程调度CPU时间片完等待事件进程完成事件出现图3-1仅具有进程调度的调度队列模型63.1.2调度队列模型2.具有高级和低级调度的调度队列模型批处理系统中的调度模型比第一种情况多了后备队列就绪队列阻塞队列1作业调度进程调度CPU时间片完等待事件1进程完成图3-2具有高、低两级调度的调度队列模型阻塞队列2等待事件2阻塞队列n等待事件n………事件1出现事件2出现事件n出现后备队列73.1.2调度队列模型3.同时具有三级调度的调度队列模型具有挂起状态的系统。83.1.3选择调度方式和调度算法的若干准则1．面向用户的准则（1）周转时间短。评价批处理系统的准则之一周转时间——是指从作业被提交给系统开始，到作业完成这段时间间隔。平均周转时间举例说明（2）响应时间快评价分时系统的准则之一响应时间——是从用户通过键盘提交一个请求开始，到系统首次产生响应为止的时间。9在批处理、分时和实时系统中选择调度算法时，都可以遵循优先权准则，以便让某些紧急的作业能得到及时处理。在要求严格的场合，往往还须选择抢占式调度方式（4）优先权准则截止时间——是指某任务必须开始执行的最迟时间，或必须完成的最迟时间。（3）截止时间的保证评价实时系统的准则之一103.1.3选择调度方式和调度算法的若干准则2.面向系统的准则（1）系统吞吐量高（2）处理机利用率好（3）各类资源的均衡利用吞吐量——单位时间内系统所完成的作业数调度方式和算法对处理机的利用率起着十分重要的作用对于单用户微机或某些实时系统，该准则并不重要113.2调度算法3.2.1先来先服务调度算法3.2.2短作业(进程)优先调度算法3.2.3高优先权优先调度算法3.2.4高响应比优先调度算法3.2.5基于时间片的轮转调度算法123.2.1先来先服务调度算法FCFS调度算法是一种最简单的调度算法。既可用于作业调度，也可用于进程调度。用于作业调度中：从后备队列作业中，选择一个或几个最先进入该队列的作业，将它们调入内存，为它们分配资源、创建进程，然后放入进程就绪队列。用于进程调度时：从就绪队列中，选择一个最先进入该队列的进程，为之分配处理机，使之投入运行。该进程一直运行到完成或发生某事件而阻塞后，才放弃处理机。——非抢占式13【例3-1】设在单道系统中用FCFS算法调度如下作业，请完成下表。进程名ABCDE平均到达时间9:009:109:3010:0010:15服务时间30分钟1小时10分钟50分钟20分钟完成时间周转时间带权周转时间80分钟9:3030分钟10:3070分钟10:4011:3090分钟11:5095分钟11.3371.84.7573分钟3.176FCFS算法比较有利于长作业（进程），不利于短作业（进程）。有利于CPU繁忙型作业（进程），不利于I/O繁忙型作业（进程）——因非抢占式CPU繁忙型作业——需要大量的CPU时间进行计算，而很少请求I/O。如，科学计算I/O繁忙型作业——是指CPU进行处理时，需频繁地请求I/O。如，大多数事务处理143.2.2短作业(进程)优先调度算法短作业优先（SJF）调度算法——从后备队列中选择一个或几个估计运行时间最短的作业，将它调入内存运行。短进程优先（SPF）调度算法——从就绪队列中选择一个估计运行时间最短的作业，将处理机分配给它，使它立即执行并一直到完成，或发生某事件而被阻塞放弃处理机时，再重新调度。(非抢占式)15【例3-2】设在单道系统中用SJF算法调度如下作业，请完成下表。进程名ABCDE平均到达时间9:009:109:3010:0010:15服务时间30分钟1小时10分钟50分钟20分钟完成时间周转时间在黑板上画此表格，请学生填表。16SJF调度算法的优点：SJF调度算法的缺点：该算法对长作业不利——长作业可能长期不被调度，甚至“饿死”。未考虑作业的紧迫性，不能保证紧迫作业（进程）会被及时调度。由于作业（进程）的长短只是根据用户所提供的估计时间而定的，致使该算法不一定能真正做到短作业优先调度。当多个作业同时到达时，SJF算法可使平均周转时间最短。173.2.3高优先权优先调度算法引入的目的：为了照顾紧迫型作业，使之在进入系统后便获得优先处理。优先权作业调度——系统从后备中选择一个或几个优先权最高的作业，将它调入内存运行。优先权进程调度——系统将处理机分配给就绪队列中一个优先权最高的进程。适用范围：批处理系统的作业调度多种操作系统的进程调度还适用于实时系统181．优先权进程调度算法的类型非抢占式优先权算法抢占式优先权算法非抢占式优先权算法——系统一旦把处理机分配给就绪队列中优先权最高的进程后，该进程便一直执行下去，直到完成，或因发生某事件使该进程放弃处理机时，系统方可再将处理机重新分配给另一个优先权最高的进程。抢占式优先权算法——系统把处理机分配给就绪队列中优先权最高的进程，使之执行，但在其执行期间，只要出现了另一个优先权更高的进程，系统就立即停止当前进程的执行，重新将处理机分配给新的优先权最高的进程。它能更好地满足紧迫作业的要求。常用于实时系统中，以及对实时性能要求较高的批处理系统和分时系统中。192．优先权的类型静态优先权动态优先权1）静态优先权静态优先权——它是在创建进程时确定的，且在进程整个运行期间保持不变。优先权一般用某一范围内的一个整数来表示。有的系统用“0”表示最高优先权，数值越大，优先权越低；有的系统恰恰相反。确定优先权的依据：——常有三方面进程类型系统进程（如接收进程、对换进程、磁盘I/O进程等）的优先权高于一般用户进程的优先权。进程对资源的需求如进程的估计执行时间及内存需求量的多少，对这些要求少的进程赋予较高的优先权。用户要求这是由用户进程的紧迫程度和用户所付费用的多少来确定优先权的。静态优先权的优缺点：优点：简单易行，系统开销小。缺点：优先权低的作业（进程）可能长期得不到调度。202）动态优先权动态优先权——在创建进程时所赋予的优先权，是可以随进程得推进，或随其等待时间的增加而改变的，以便获得更好的调度性。例如：在就绪队列中的进程，随其等待时间的增长，其优先权以速率α提高；在采用抢占式优先权调度算法时，如果再规定当前执行进程以速率β下降，则可防止一个长作业长期垄断处理机。21UNIX采用计算的方法动态改变进程的优先数。在UNIXSystemV版本中，进程优先数p_pri的算式如下：p_pri=p_cpu/2+PUSER+p_nice+NZERO其中，PUSER和NZERO是偏置常数，分别为25和20。p_cpu和p_nice是基本进程控制块中的两个项，分别表示进程使用处理器的情况和用户自己设置的计算优先数的偏置量。系统对正在占用CPU的进程每隔一个时钟周期(20ms)对其p_cpu加1。这使得占用处理器时间长的进程的p_cpu值增大，其优先数也增大，优先权就相应降低。系统每隔1s对所有进程执行p_cpu/2，这使就绪进程优先级提高。p_nice的值允许用户根据任务的轻重缓急程度来设置，其值在0～39之间。一旦一个进程的p_nice设置后，此后用户只能使其值增加。22【例3-3】设有一个最多可有两道作业同时装入内存执行的批处理系统，作业调度采用最短作业优先调度算法，进程调度采用抢占式静态优先权调度算法，今有如下纯计算型作业序列（表中所列进程优先数中，数值越小优先权越高）：(1)列出所有作业进入内存时间及结束时间。(2)计算平均周转时间。作业名到达时间估计运行时间进程优先数J110:1020分钟5J210:2030分钟3J310:3025分钟4J410:5020分钟623作业名提交时间进入时间结束时间周转时间J110:1010:1011:0050分钟J210:2010:2010:5030分钟J310:3011:0011:2555分钟J410:5010:5011:4555分钟平均周转时间=(50+30+55+55)4=47.5(分钟)243.2.4高响应比优先调度算法响应比＝(等待时间+要求服务时间)/要求服务时间（实际上响应比是动态优先权）高响应比优先调度算法——每次要进行作业调度时，系统首先计算后备队列中各作业的响应比，然后选择一个或若干个响应比最高的作业调入内存执行。该算法综合了FCFS和SJF算法的优点——既考虑公平性，又考虑平均周转时间缺点是会增加系统开销——每次调度都要计算响应比。2524．下列进程调度算法中，综合考虑进程等待时间和执行时间的是_____。(2009全国考研第24题)A．时间片轮转调度算法B．短进程优先调度算法C．先来先服务调度算法D．高响应比优先调度算法26【例3-4】设有一个最多可有两道作业同时装入内存执行的批处理系统，作业调度采用高响应比优先调度算法，进程调度采用抢占式静态优先权调度算法，今有如下纯计算型作业序列（假设表中所列进程优先数中，数值越小优先权越高）：(1)列出所有作业进入内存时间及结束时间。(2)计算平均周转时间。作业名到达时间估计运行时间进程优先数J110:1020分钟5J210:2030分钟3J310:3025分钟4J410:5020分钟627J1CPU10:1010:20J210:5010:50J3响应比高，J3调入内存并执行。11:15J311:15J4调入内存，J1恢复执行。J111:25J411:4510:10只有J1一个作业，调入内存执行。10:20J2到达，调入内存，因其优先级高，J2执行。28J1J2J3J1J4CPU10:1010:2010:5011:1511:2511:45作业名到达时间调入时间结束时间周转时间J110:1010:1011:2575分钟J210:2010:2010:5030分钟J310:3010:5011:1545分钟J410:5011:1511:4555分钟平均周转时间=(75+30+45+55)/4=51.25(分钟)293.2.5基于时间片的轮转调度算法用于进程调度。早期，分时系统采用的是简单的时间片轮转法；90年代后，广泛采用多级反馈队列调度算法。1．时间片轮转法系统把