搜索
计算机操作系统南京工业大学信息学院第三章处理机调度与死锁3.1处理机调度的基本概念3.2调度算法3.3产生死锁的原因和必要条件3.4预防和避免死锁的方法3.5死锁的检测和解除3.1处理机调度的基本概念3.1.1高级、中级和低级调度1．高级调度——又称作业调度或长调度用于决定把外存上后备队列中哪些作业调入内存，并为它们创建进程、分配必要的资源，然后将新创建的进程插入到就绪队列中，准备运行。定义每次作业调度，都需做以下两个决定：●接纳多少个作业——取决于多道程序度▲内存中同时运行的作业数目太多，会影响系统的服务质量。如，周转时间长。▲内存中同时运行的作业数目太少，会导致系统资源利用率和系统吞吐量低。●接纳哪些作业——取决于调度算法3.1处理机调度的基本概念2．低级调度又称进程调度或短调度。是最基本的调度，三种类型OS中，都必须配置此调度。定义用来决定就绪队列中的哪个进程应获得处理机，然后再由分派程序执行把处理机分配给该进程的具体操作。进程调度可采用下述两种调度方式：（1）非抢占方式（2）抢占方式一旦把处理机分配给某进程后，便让它一直执行，直到该进程完成或发生某事件而被阻塞时，才把处理机分配给其它进程，决不允许某进程抢占已经分配出去的处理机。优点：实现简单，系统开销小。缺点：难于满足紧急任务的要求。允许调度程序根据某种原则，暂停某个正在执行的进程，将已分配给该进程的处理机重新分配给另一进程。抢占原则有：优先权原则；短作业优先原则；时间片原则。3.1处理机调度的基本概念3.中级调度挂起和激活，存储器管理中的对换功能。主要目的：为了提高内存的利用率和系统的吞吐量。主要介绍进程调度和作业调度。三种调度相比较：进程调度的运行频率最高作业调度频率最低中级调度界于之间3.1.2调度队列模型三种类型的调度队列模型：1.仅有进程调度的调度队列模型在分时系统中，通常仅设置了进程调度。常把就绪进程组织成FIFO队列形式。阻塞队列一般可能有多个。3.1.2调度队列模型2.具有高级和低级调度的调度队列模型批处理系统中，需要进程调度，也需要作业调度。批处理系统中，最常用的是最高优先权优先调度算法，其进程就绪队列…比第一种情况多了后备队列3.1.2调度队列模型3.同时具有三级调度的调度队列模型具有挂起状态的系统。3.1.3选择调度方式和调度算法的若干准则1．面向用户的准则（1）周转时间短。评价批处理系统的准则之一周转时间——是指从作业被提交给系统开始，到作业完成这段时间间隔。平均周转时间举例说明（2）响应时间快评价分时系统的准则之一响应时间——是从用户通过键盘提交一个请求开始，到系统首次产生响应为止的时间。（3）截止时间的保证评价实时系统的准则之一截止时间——是指某任务必须开始执行的最迟时间，或必须完成的最迟时间。（4）优先权准则在批处理、分时和实时系统中选择调度算法时，都可以遵循优先权准则，以便让某些紧急的作业能得到及时处理。在要求严格的场合，往往还须选择抢占式调度方式3.1.3选择调度方式和调度算法的若干准则2.面向系统的准则（1）系统吞吐量高（2）处理机利用率好（3）各类资源的均衡利用吞吐量——单位时间内系统所完成的作业数调度方式和算法对处理机的利用率起着十分重要的作用对于单用户微机或某些实时系统，该准则并不重要3.2调度算法3.2.1先来先服务调度算法FCFS调度算法是一种最简单的调度算法。既可用于作业调度，也可用于进程调度。用于作业调度中：从后备队列作业中，选择一个或几个最先进入该队列的作业，将它们调入内存，为它们分配资源、创建进程，然后放入进程就绪队列。用于进程调度时：从就绪队列中，选择一个最先进入该队列的进程，为之分配处理机，使之投入运行。该进程一直运行到完成或发生某事件而阻塞后，才放弃处理机。——非抢占式【例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。如，大多数事务处理3.2.2短作业（进程）优先调度算法短作业优先（SJF）调度算法——从后备队列中选择一个或几个估计运行时间最短的作业，将它调入内存运行。短进程优先（SPF）调度算法——从就绪队列中选择一个估计运行时间最短的作业，将处理机分配给它，使它立即执行并一直到完成，或发生某事件而被阻塞放弃处理机时，再重新调度。(非抢占式)例3-1中，调度算法改为SJF时，请完成该表格的填写。【例3-2】SJF调度算法的优点：SJF调度算法的缺点：该算法对长作业不利——长作业可能长期不被调度，甚至“饿死”。未考虑作业的紧迫性，不能保证紧迫作业（进程）会被及时调度。由于作业（进程）的长短只是根据用户所提供的估计时间而定的，致使该算法不一定能真正做到短作业优先调度。当多个作业同时到达时，SJF算法可使平均周转时间最短。3.2.3高优先权优先调度算法引入的目的：为了照顾紧迫型作业，使之在进入系统后便获得优先处理。优先权作业调度——系统从后备中选择一个或几个优先权最高的作业，将它调入内存运行。优先权进程调度——系统将处理机分配给就绪队列中一个优先权最高的进程。适用范围：批处理系统的作业调度多种操作系统的进程调度还适用于实时系统1．优先权进程调度算法的类型非抢占式优先权算法抢占式优先权算法非抢占式优先权算法——系统一旦把处理机分配给就绪队列中优先权最高的进程后，该进程便一直执行下去，直到完成，或因发生某事件使该进程放弃处理机时，系统方可再将处理机重新分配给另一个优先权最高的进程。抢占式优先权算法——系统把处理机分配给就绪队列中优先权最高的进程，使之执行，但在其执行期间，只要出现了另一个优先权更高的进程，系统就立即停止当前进程的执行，重新将处理机分配给新的优先权最高的进程。它能更好地满足紧迫作业的要求。常用于实时系统中，以及对实时性能要求较高的批处理系统和分时系统中。2．优先权的类型静态优先权动态优先权1）静态优先权静态优先权——它是在创建进程时确定的，且在进程整个运行期间保持不变。优先权一般用某一范围内的一个整数来表示。有的系统用“0”表示最高优先权，数值越大，优先权越低；有的系统恰恰相反。确定优先权的依据：——常有三方面进程类型系统进程（如接收进程、对换进程、磁盘I/O进程等）的优先权高于一般用户进程的优先权。进程对资源的需求如进程的估计执行时间及内存需求量的多少，对这些要求少的进程赋予较高的优先权。用户要求这是由用户进程的紧迫程度和用户所付费用的多少来确定优先权的。静态优先权的优缺点：优点：简单易行，系统开销小。缺点：优先权低的作业（进程）可能长期得不到调度。2）动态优先权动态优先权——在创建进程时所赋予的优先权，是可以随进程得推进，或随其等待时间的增加而改变的，以便获得更好的调度性。例如：在就绪队列中的进程，随其等待时间的增长，其优先权以速率α提高；在采用抢占式优先权调度算法时，如果再规定当前执行进程以速率β下降，则可防止一个长作业长期垄断处理机。【例3-3】设有一个最多可有两道作业同时装入内存执行的批处理系统，作业调度采用最短作业优先调度算法，进程调度采用抢占式静态优先权调度算法，今有如下纯计算型作业序列（表中所列进程优先数中，数值越小优先权越高）：(1)列出所有作业进入内存时间及结束时间。(2)计算平均周转时间。作业名到达时间估计运行时间进程优先数J110:1020分钟5J210:2030分钟3J310:3025分钟4J410:5020分钟63.2.4高响应比优先调度算法响应比＝等待时间＋要求服务时间要求服务时间（实际上响应比是动态优先权）高响应比优先调度算法——每次要进行作业调度时，系统首先计算后备队列中各作业的响应比，然后选择一个或若干个响应比最高的作业调入内存执行。该算法综合了FCFS和SJF算法的优点——既考虑公平性，又考虑平均周转时间缺点是会增加系统开销——每次调度都要计算响应比。【例3-4】与例3-3相同，只是作业调度改为高响应比优先调度算法。3.2.5基于时间片的轮转调度算法用于进程调度。早期，分时系统采用的是简单的时间片轮转法；90年代后，广泛采用多级反馈队列调度算法。1．时间片轮转法系统把就绪队列中的所有进程，按先来先服务的原则，排成一个队列；每次调度时，把CPU分配给队首进程，并让它执行一个时间片；每当执行的时间片用完，调度程序便停止该进程的执行，将其送入就绪队列尾部；然后进行下一次进程调度。时间片的大小：几ms～几百ms。2．多级反馈队列调度算法不必事先知道各进程所需的执行时间而且还可以满足各种类型进程的需要目前被公认的一种较好的进程调度算法3.5产生死锁的原因和必要条件死锁定义——多个进程在运行过程中因争夺资源而造成的一种僵局，当进程处于这种僵局状态时，若无外力作用，它们都将无法再向前推进。死锁定义——一组进程处于死锁状态是指：如果在一个进程集合中的每一个进程都在等待只能由该集合中的其它一个进程才能引发的事件，则称一组进程或系统发生了死锁。——孙钟秀主编《操作系统教程》死锁定义：一组竞争系统资源或相互通信的进程间相互的“永久”阻塞。——[美]WilliamStallings著《操作系统——内核与设计原理(第四版）》3.5.1产生死锁的原因可归结为两点：竞争资源进程间推进顺序非法解释之3.5.2产生死锁的必要条件四个必要条件：互斥条件请求和保持条件不剥夺条件环路等待条件解释之。说明为什么不是充分条件。3.5.3处理死锁的基本方法可归结为四种：预防死锁、避免死锁、检测死锁、解除死锁预防死锁——通过设置某些限制条件，去破坏产生死锁的四个必要条件中的一个或几个条件，来预防发生死锁。缺点：可能导致系统资源利用率和系统吞吐量的降低。——较严格的限制条件避免死锁——并不需要事先采取各种限制措施去破坏产生死锁的四个必要条件，而是在资源动态分配过程中，用某种方法防止系统进入不安全状态，从而避免死锁。目前在较完善的系统中，常用此方法来避免死锁。——只要较弱的限制条件3.5.3处理死锁的基本方法(续)检测死锁解除死锁——并不事先采取任何限制措施，也不必检查系统是否已经进入不安全区，允许系统在运行过程中发生死锁，但可通过系统设置的检测机构，及时检测出死锁的发生，然后采取适当的措施，从系统中将已发生的死锁清除掉。——这是与检测死锁相配套的措施。常用的方法是撤消或挂起一些进程，以便回收一些资源，分配给已处于阻塞状态的进程，使之转为就绪状态，以继续运行。——实现上难度最大。3.6预防和避免死锁的方法3.6.1预防死锁方法是使四个必要条件中的一个或几个条件不能成立，来防止死锁的发生。2．屏弃“请求并保持”条件资源的一次性分配（静态分配）优点：简单，易实现。缺点：资源利用率低；使进程延迟运行（仅当能获得全部资源时，才能开始运行）1．破坏“互斥”条件书上没有介绍采用Spooling技术，可以允许若干个进程同时产生输出。不足：Spooling技术并不适用于所有资源，而且它对磁盘空间的竞争也可能引起死锁。3．屏弃“不剥夺”条件4．屏弃“环路等待”条件采用资源“按号分配”缺点：限制了新类型设备的增加；经常发生进程使用资源的顺序与系统规定的顺序不同，造成资源浪费；会限制用户简单、自主地编程。缺点：▲实现起来比较复杂且要付出很大代价。（前后两次打印输出的信息，中间有一段是另一进程的）▲可能因为反复申请资源而使进程的执行被无限地推迟，增加了系统开销，降低了系统吞吐