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

第三章处理机调度与死锁•【教学目的】了解处理机调度的基本概念、调度算法和类型及死锁的概念、产生条件及检测与解除。•【教学重点】1、处理机调度原理及算法。2、死锁的产生原因及检测与解除。•【分配课时】进度计划6学时第三章处理机调度与死锁3.1处理机调度的基本概念3.2进程调度算法3.3实时调度3.4多处理机系统中的调度3.5产生死锁的原因和必要条件3.6预防死锁的方法和死锁避免3.7死锁的检测和解除第一节调度的类型和模型一、调度类型1、高级调度（HighlevelScheduling）（或作业//长程//接纳调度）（1）定义把外存上处于后备队列中的那些作业调入内存，并为它们创建进程、分配必要的资源，然后，再将新创建的进程排在就绪队列上，准备执行。在批处理系统中，是先驻留在外存上的，因此需要有作业调度，以将它们分批装入内存。在分时系统中，为了能及时响应，用户通过键盘输入的命令或数据等，都是直接送入内存，因而无需配置作业调度。（2）决定作业调度的两个因素①接纳多少个作业作业调度每次要接纳多少个作业进入内存，取决于多道程序度（DegreeofMultiprogramming）,即允许有多少个作业同时在内存中运行。②接纳哪些作业应将哪些作业从外存调入内存，将取决于所采用的调度算法。最简单的是先来先服务调度算法，较常用的一种是短作业优先调度算法，还有基于作业优先权的调度算法、响应比高者优先的调度算法等。第一节调度的类型和模型2、低级调度（LowLevelScheduling）低级调度通常又称为进程调度、短程调度（Short-TermScheduling）在三种类型的OS中都必须配置这级调度。进程调度可采取下述两种方法：(1)非抢占方式（Non-PreemptiveMode）采取调度方式时，一旦处理机分配某进程后，便让该进程一直执行，直至该进程完成或发生某事件而被阻塞时，才再把处理机分配给其它进程，决不允许某进程抢占已经分配出去的处理机。这种调度方式的优点是实现简单、系统开销小，适用大于多数的批处理系统环境。但它难于满足紧急任务的要求。(2)抢占方式（PreemptiveMode）这种调度方式，允许调度程序根据某种原则，去停止某个正在执行的进程，将已分配给该进程的处理机，重新分陪另一进程。第一节调度的类型和模型抢占的原则有：①时间片原则各进程按时间片运行，当一个时间片用完后，便停止该进程的执行而重新进姓调度。这种原则适用于分时系统、大多数实时系统，以及要求较高的批处理系统。②优先权原则通常是对一些重要的和紧急的作业赋予较高的优先权。当这种作业到达时，如果其优先权比正在执行进程的优先权高，便停止正在执行的进程，将处理机分配给优先权高的进程，使之执行。③短作业（进程）优先原则当新到达的作业（进程）比正在执行的作业（进程）明显地短时，将剥夺长作业（进程）的执行，将处理机分配给作业（进程），使之优先执行。第一节调度的类型和模型3、中级调度又称中程调度(1)引入中级调度的目的是为了提高内存的利用率和系统吐量。(2)定义应使那些暂时不能运行的进程不再占用宝贵的内存空间，而将它们调至外存上去等待，称此时的进程状态为就绪驻外存状态，或挂起状态。当这些进程重又举备运行条件，且内存又稍有空闲时，由中级调度决定，将外存上的那些重又具备运动条件的就绪进程重新调入内存，并修改其状态为就绪态，挂在就绪队列上，等待进程调度。第一节调度的类型和模型在上述三种调度中，进程调度的运行频率最高，在分时系统中通常是10-100ms便进行一次进程调度，因而进程调度算法不能太复杂，以免占用太多的CPU时间。作业调度往往是发生在一个（批）作业运行完毕，退出系统又需要重新调入一个（批）作业进入内存时，故作业调度的周期校长，大约几分钟一次。因而也允许作业调度算法花费较多时间，中级调度的运行频率基本上介入于上述两种调度之间。第一节调度的类型和模型二、调度队列模型1、仅有进程调度的调度队列模型在分时系统中通常仅设置了进程调度。用户键入的命令和数据，都直接送入内存。对于命令，由OS为之建立一个进程，并将它排在就绪队列的末尾，然后按时间片轮转方式执行。每个进程执行时，都可能出现这样三种可能。（1）该任务在该时间片内已经完成，该进程释放处理机后进入完成状态；（2）任务在本其对应的时间内尚未完成，OS便将任务放在就绪队列的后面；（3）在执行期间，进程因某事件而被阻塞后，OS将它们放入阻塞队列。1.进程调度模型1)只有进程调度的调度队列模型图3-1仅具有进程调度的调度队列模型2、具有高级和低级调度的调度队列模型（见P99图4-2）（1）在OS中不仅引入了进程调度，而且还进入了作业调度。后者从外存的后备队列中选择一批作业调入内存，为之创建进程后，送入就绪队列；（2）在OS中设置多个阻塞队列。当系统中仅设置一个阻塞队列时，可能会使该队列很长，尤其当系统较大时，该队列中可能数百个进程。为了提高队列的操作效率，通常都设置若干个（1，2,...,n）阻塞队列，每个队列对应于一种引起进程阻塞的事件。。2)具有高低级调度的调度队列模型图3-2具有高、低两级调度的调度队列模型3、同时具有三级调度的调度队列模型当在OS中引入中级调度后，可把就绪态分为内存就绪状态、外存就绪状态。可把阻塞状态进一步分成内存阻塞和外存阻塞两种状态。在调出操作的情况下，可使内存就绪转变为外存就绪、内存阻塞转变为外存阻塞；在中级调度的作用下，外存就绪转变为内存就绪。3)具有三级调度的调度队列模型图3-3具有三级调度时的调度队列模型三、选择调度方式和算法的若干准则•面向用户的准则：周转时间短；响应时间快；截止时间的保证；优先权准则•面向系统的准则：系统吞吐量高；处理机利用率好；各类资源的平衡利用•1、面向用户的准则（1）周转时间短通常把周转时间作为评价批处理系统的性能、选择作业调度方法与算法的准则。①定义是指从作业提交给系统开始，到作业完成为止这段时间间隔（称为作业周转时间）。它包括：Ø作业在外存后备队列上等待（作业）调度的时间；Ø进程在就绪队列上等待进程调度的时间；Ø进程在CPU上执行的时间；Ø等待I/O操作完成的时间。其中，第（2）、（3）、（4）项在一个作业处理过程中，可能发生多次。对每个用户而言，作业的周转时间最短。但作为计算计系统的管理者，希望平均周转时间最短；这不仅会有效地提高资源利用率，而且还可使大多数用户满意。平均周转时间：T=[]带权周转时间:作业周转时间T与系统为它提供的实际服务时间Ts之比，即W=T/Ts称为。而平均带周转时间可表示为：W=[]（2）响应时间快响应时间是从用户通过键盘提交一个请求开始，直到在屏幕上显示出结果为止的一段时间间隔。它包括：（1）从键盘输入的要求信息传送到处理机的时间；（2）处理机对请求信息进行处理的时间；（3）将所行成的响应回送到终端显示器的时间；（3）截止时间的保证它是用来评价实时系统性的重要指标，因而是选择实时调度算法的重要准则。①定义截止时间：指某任务必须开始执行的最迟时间，或必须完成的最迟时间，对于严格的实时系统，其调度方式和调度算法必须保证这点。否则将可能引起难以预料的后果。（4）优先权准则让紧急的作业，得到及时的处理。第二节调度算法•调度算法是指：根据系统的资源分配策略所规定的资源分配算法，对于不同的系统和系统目标，通常采用不同的调度算法。调度算法•先进先出(FIFO)算法•最短CPU运行期优先调度算法•最高优先权优先调度算法•轮转法•多级反馈队列一、先来先服务调度算法一、先来先服务（FCFS）调度算法1、原理当在作业调度中采用该算法时，每次调度是从后备作业队列中，选择一个或多个最先进入该队列的作业，将它们调入内存，为它们分配资源、创建进程，然后放入就绪队列。在进程调度中，采用FCFS调度算法时，每次调度是从就绪队列中，选择一个最先进入该进程，把处理分配给它，使之投入运行。该进程一直运行到完或发生某事件阻塞后，才放弃处理机。2、优缺点（1）FCFS算法比较有利于作业（进程），而不利于短作业（进程）。下表列出了A、B、C、D四个作业分别到达系统的时间、要求服务的时间、开始执行的时间及各自的完成的时间，并计算出各自的周转时间和带权周转时间。从上表可以看出：其中短作业C的带权周转时间竞高达100，这是不能容忍的；而长作业D的带权周转时间仅为1.99。据此可知：（2）FCFS调度算法有利于CPU繁忙型的作业，而不利于I/O繁忙型的作业进程。CPU繁忙型作业：是指该类作业需要大量的CPU时间进行计算，而很少请求I/O。通常的科学计算便属于CPU繁忙行作业。I/O繁忙行作业：是指CPU进行处理时，又需频繁地请求I/O，而每次I/O的操作时间却又很短。目前的大多数的事务处理，都属于I/O繁忙行作业。1.先进先出(FIFO)算法该算法总是把处理机分配给最先进入就绪队列的进程，一个进程一旦分得处理机，便执行下去，直到该进程完成或阻塞时，才释放处理机。优点:实现简单.缺点:没考虑进程的优先级2.最短CPU运行期优先调度算法•该算法从就绪队列中选出“下一个CPU执行期”最短的进程，为之分配处理机。•该算法虽可获得较好的调度性能，但难以准确地知道下一个CPU执行期，而只能根据每一个进行的执行历史来预测。图3-4FCFS和SJF调度算法的性能3.FCFS和SJF的性能比较优点（1）短作业（SJF）的调度算法可以照顾到实际上在所有作业中占很大比例的短作业，使它能比长作业优先执行。（2）SJF调度算法能有效地降低作业的平均等待时间和提高系统的吐量。缺点（1）该算法对长作业非常不利来的）短作业（进程），将致使长作业（进程）得不到调度。（2）该算法完全未考虑作业的紧迫程度，因而不能保证紧迫性作业（进程），回得到及时处理；（3）由于作业（进程）的长短只是根据用户所提供的估计执行时间而定，而用户又可能会有意或无意地缩短其作业的估计执行时间，致使该算法不一定能真正做到短作业优先调度。一、优先权调度算法的类型（1）非抢占式优先权算法（2）抢占式优先权调度算法4.最高优先权优先调度算法二、优先权的类型（1）静态优先权静态优先权是在创建进程时确定的，切规定它在进程的整个运行期间保持不便，。一般，优先权是利用某一范围内的一个整数来表示。确定进程优先权的依据是：•进程类型。•进程对资源的需求。•如进程的估计执行时间及内存需要量少的进程，应赋予较高的优先权。优缺点①静态优先权法简单易行、系统开销小。②但不够精确，很可能出现优先权低的作业（进程），长期没有调度的情况，因此，仅在要求不太高的系统中，才使用静态优先权。（2）动态优先权动态优先权是指在创建进程时所赋予的优先权，可以随进程的推进而改变，以变获得更好的性能。5.高响应比优先调度算法优先权的变化规律可描述为：由于等待时间与服务时间之和，就是系统对该作业的响应时间，故该优先权又相当于响应比RP。据此，又可表示为：由上式可以看出：（1）如果作业的等待时间相同，则要求服务的时间愈短，其优先权愈高，因而该算法有利于短作业；（2）当要求服务的时间相同时，作业的优先权决定于其等待时间，因而实现了先来先服务；（3）对于长作业，当其等待时间足够长时，其优先权便可升到很高，从而也可获得处理机。该算法既照顾了短作业，又考虑了作业到达的先后顺序，也不会使作业长期得不到服务。因此，该算法实现了一种较好的折衷。当然，再利用该算法时，每要进行调度之前，都需先进行响应应比的计算，这会增加系统的开销3.2练习假如有四道作业，它们的进入时间和运行时间由下表给出，在单道程序环境下，分别填写先来先服务、短作业优先和高响应比优先调度算法的完成时间和周转时间，并求出平均周转时间和平均带权周转时间。作业号进入时间(时)运行时间(小时)FCFSSJF完成时间(时)周转时间(小时)完成时间(时)周转时间(小时)110:000.4210:101310:200.6410:300.26.轮转法在通常的轮转法中，系统将所有的就绪进程按先来先服务原则，排成一个队列，每次调度时把CPU分配给对手进程，并令其执行一个时间片。时间