操作系统讲义-第三章处理机调度与死锁.ppt

2019年11月22日,操作系统讲义,1,第三章处理机调度与死锁,2019年11月22日,第二章进程管理,2,主要内容,3.1处理机调度的层次3.2调度队列模型和调度准则3.3几种调度算法3.4实时调度3.5产生死锁的原因和必要条件3.6预防死锁的方法3.7死锁的检测和解除,2019年11月22日,第二章进程管理,3,3.1处理机调度的层次,作业的基本概念,1.高级调度（HighLevelScheduling）,主要功能：根据某种算法，把外存中把处于后备队列中的那些作业调入内存，当作业完成时做善后处理。,作业（Job）：包含通常的程序和数据，并且配有作业说明书；作业步（JobStep）：“编译”-“连接装配”-“运行”；作业流：若干个作业在系统外存形成的输入流。,作业控制块JCB（JobControlBlock）,通常包含：作业标识、用户名称、用户账户、作业类型（CPU繁忙，I/O繁忙，批量型，终端型）、作业状态、调度信息（优先级，作业运行时间）、资源需求（运行时间，内存，I/O类型数量）、进入系统时间、开始处理时间、作业完成时间、作业退出时间、资源使用情况。,2019年11月22日,第二章进程管理,4,3.1处理机调度的层次,1.高级调度（HighLevelScheduling）,作业调度：是根据作业控制块中的信息，审查系统能否满足用户作业的资源需求，以及按照一定的算法，从外存后备队列中选取某些作业调入内存，为他们创建进程、分配必要的资源，然后将进程插入就绪队列，准备执行。,目的：提高内存利用率和系统吞吐量，使那些暂时不能运行的进程不再占用内存，把它们调至外存（存储管理中的对换功能）。,1）接收多少个作业到内存取决于多道程序度2）接收哪些作业取决于调度算法最简单：先来先服务调度算法最常用：短作业优先调度算法较常用：优先级调度算法比较好：响应比高者优先调度算法,2.中级调度（IntermediateLevelScheduling）,2019年11月22日,第二章进程管理,5,3.1处理机调度的层次,3.低级调度（LowLevelScheduling）,它所调度的对象是进程（或内核级线程），当CPU需要重新分配时，利用一定的算法把它分配给进程，它是最基本的调度。,进程调度的功能（1）保存处理机的现场信息；（2）按照某种算法选择进程（如优先数算法，轮转算法）（3）把处理器分配给进程。,进程调度的三个基本机制（1）排队器：事先将系统所有就绪进程排成一个队列，方便调度程序最快找到它；（2）分派器（分派程序）：把进程调度程序选定的进程从就绪队列移出，切换上下文，然后把CPU分配给它；（3）上下文切换机制：保存当前程序的上下文，装入分配程序的上下文；移出分派程序，装入新选进程的CPU信息；,2019年11月22日,第二章进程管理,6,3.1处理机调度的层次,进程调度方式,3.低级调度（LowLevelScheduling）,非抢占方式：一旦处理机分配给某个进程，不管它要运行多长时间，都让它一直运行下去，决不会因为其他原因而抢占正在运行进程的处理机。这种方式下引起进程调度的因素包括：执行完毕或者发生某事件不能再执行执行进程提出I/O请求而暂停执行在进程通信或者同步过程中执行了某种原语操作，如P，Block等优点：实现简单，系统开销小，适用于大多数批处理系统；缺点：难以满足紧急任务要求，可能造成难以预料的后果。,2019年11月22日,第二章进程管理,7,3.1处理机调度的层次,进程调度方式,3.低级调度（LowLevelScheduling）,抢占方式：允许调度程序根据某种原则去暂停某个正在执行的进程，这些原则主要包括：优先权原则短作业优先原则时间片原则优点：防止一个长进程长时间占用处理机，公平服务，适合实时任务的需求；缺点：需要付出较大的开销。,2019年11月22日,第二章进程管理,8,3.2调度队列模型和调度准则,仅有进程调度的调度队列模型通常在分时系统中只设置进程调度，每个用户建立一个进程，系统利用堆栈，树或者链表来管理就绪进程队列。,1.调度队列模型,进程执行时可能出现的三种情况：在给定时间片完成，释放处理机进入完成状态；本次时间片内未完成，放入就绪队列尾部；因为某事件被阻塞，放入阻塞队列。,就,绪,队,列,CPU,阻,塞,队,列,交互用户,时间片完,进程调度,等待事件,进程完成,事件出现,2019年11月22日,第二章进程管理,9,3.2调度队列模型和调度准则,具有高级和低级调度的调度队列模型作业调度按照一定的算法从外存的后备队列选择一批作业调入内存，建立进程，送入就绪队列，然后按照一定的进程调度算法选择进程，分配CPU。,1.调度队列模型,就,绪,队,列,CPU,阻,塞,队,列,作业调度,时间片完,进程调度,等待事件1,进程完成,事件1出现,队,列,后,备,阻,塞,队,列,阻,塞,队,列,等待事件2,等待事件n,事件2出现,事件n出现,队,2019年11月22日,第二章进程管理,10,3.2调度队列模型和调度准则,同时具有三级调度的调度队列模型可把进程的就绪状态分成内存就绪和外存就绪，类似地，阻塞状态也可进一步分成内存阻塞和外存阻塞，调出操作可使进程状态由内存就绪转为外存就绪，内存阻塞转为外存阻塞；中级调度可是外存就绪转为内存就绪。,1.调度队列模型,就,绪,队,列,CPU,绪,挂,起,队,列,就,作业调度,时间片完,进程调度,进程完成,事件出现,队,列,后,备,塞,挂,队,队,列,阻,阻,塞,队,列,等待事件,起,批量作业,挂起,事件出现,中级调度,2019年11月22日,第二章进程管理,11,3.2调度队列模型和调度准则,面向用户的准则（1）周转时间短平均周转时间T的计算如下：平均带权周转时间W的计算如下：（2）响应时间快：从用户通过键盘提交一个请求开始，直到系统首次响应未知的时间尽量快；（3）截止时间的保证：是指某任务必须开始执行的最迟时间，或必须完成的最迟时间必须有保证，这是评价实时系统性能的重要指标；（4）优先权准则：遵循优先权准则让某些紧急的作业得到及时处理。,2.选择调度方式和算法的若干准则,2019年11月22日,第二章进程管理,12,3.2调度队列模型和调度准则,面向系统的准则,2.选择调度方式和算法的若干准则,（1）系统吞吐量高：这个是评价批处理系统性能的另一个重要指标，因此是选择批处理作业调度的重要准则。对于大型作业，一般吞吐量为每小时一道作业，对于中、小型作业，其吞吐量可能达到数十道。,（2）处理机利用率好：CPU价格昂贵，利用率成为衡量系统性能的重要指标，一般CPU的利用率在40%到90%之间比较合理。,（3）各类资源的平衡利用：不仅要使处理机利用率高，还要有效地利用其他各类资源，如内存、外存和I/O设备，适当的调度方式和算法可以使系统中的各类资源处于忙碌状态。,2019年11月22日,第二章进程管理,13,3.3调度算法,是一种最简单的调度算法，适用于作业调度和进程调度，每次调度都是从后备队列中选择一个或者多个最先进入该队列的作业，将它们调入内存，分配资源，创建进程，然后放入就绪队列。,1.先来先服务调度算法FCFS（FirstComeFirstService）,FCFS算法比较有利于长作业（进程），不利于短作业（进程）,2019年11月22日,第二章进程管理,14,3.3调度算法,是指对短作业或者短进程优先调度的算法，适用于作业调度和进程调度，SJF算法就是从后备队列中选择一个运行时间最短的作业，然后把它们调入内存运行。,2.短作业优先调度算法SJF（ShortJobFirst）,SJF的优点：能有效地降低作业的平均等待时间，提高系统吞吐量；,SJF的缺点：1）对长作业不利；2）未考虑作业的紧迫度；3）用户估计执行时间的不准确性。,2019年11月22日,第二章进程管理,15,3.3调度算法,3.FCFS和SJF的性能比较,2019年11月22日,第二章进程管理,16,3.3调度算法,是为了照顾紧迫型作业，使之在进入系统后便获得优先处理，该算法会把处理机分配给优先级最高的作业（或者进程）。1）非抢占式优先权调度算法，适用于批处理系统或实时性要求不高的系统；2）抢占式优先权调度算法，能更好地满足紧迫作业，适合于严格的实时系统或者对性能要求较高的批处理和分时系统中。,4.高优先权优先调度算法（PriorityJobFirst）,2019年11月22日,第二章进程管理,17,3.3调度算法,4.高优先权优先调度算法（PriorityJobFirst）,优先权的类型静态优先权：创建进程时确定，在整个运行期间保持不变；进程类型，系统进程要比用户进程优先级高；进程对资源的要求，要求少的优先级高；用户要求，用户进程的紧迫程度。优点：简单易行，系统开销小缺点：不够精确，优先权低的作业（进程）长期得不到调度动态优先权：创建时赋予，可以随着进程的而推进或随其等待事件的增加而改变，以便获得更好的调度性能。优点：使调度更加公平，调度性能高缺点：系统开销稍大,2019年11月22日,第二章进程管理,18,3.3调度算法,高响应比优先调度算法每个作业的优先级动态计算，作业的优先级随等待时间的增加而不断提高。,4.高优先权优先调度算法（PriorityJobFirst）,结论：如果作业等待事件相同，要求服务时间越短，优先级越高，该算法利于短作业；如果要求服务时间相同，那么等待时间越长，优先权越高，它实现的是先来先服务；对于长作业，作业的优先级随着等待时间的增加而提高，如果等待时间足够长也可以获得处理机。优点：既照顾了短作业，又考虑了作业的先后顺序，使长作业也可以得到服务；缺点：但优先级的计算增加了系统的开销。,响应比RP=,等待时间+要求服务时间,要求服务时间,=,响应时间,要求服务时间,2019年11月22日,第二章进程管理,19,3.3调度算法,基本原理系统将所有就绪进程按照先来先服务的原则排成一个队列，每次调度把CPU分配给队首进程，并令其执行一个时间片，当执行时间片用完，调度程序停止其执行，并把它送到队列尾部。,5.基于时间片的轮转调度算法（RoundRobin）,时间片大小如果太小利于短作业，但是会频繁中断，进程上下文切换，增加系统开销；如果太大则每个进程都能在时间片内完成，则退化为FCFS算法，无法满足交互式用户的需求。,2019年11月22日,第二章进程管理,20,3.3调度算法,5.基于时间片的轮转调度算法（RoundRobin）,(a)q=1,(b)q=4,123456789101112131415161718,A,B,C,D,E,C,2019年11月22日,第二章进程管理,21,3.3调度算法,5.时间片轮转法RR,2019年11月22日,第二章进程管理,22,3.3调度算法,调度算法的实施过程设置多个就绪队列，赋予不同的优先级，各个队列优先级递减，时间片递增；新进程放入第一个队列尾部，FCFS原则排队调度，时间片内完成则撤离系统，如果没完则转入下个队列尾部，以此类推，在第n个队列采取时间片轮转调度；第一队列空闲，调度第二队列，以此类推，新进程如果优先级高，可抢占处理机。,6.多级反馈队列调度算法（RoundRobinWithMultipleFeedback）,2019年11月22日,第二章进程管理,23,3.3调度算法,6.多级反馈队列调度算法（RoundRobinWithMultipleFeedback）,算法的性能终端型作业用户，大多数交互性，作业小；短批处理作业用户，周转时间短；长批处理用户，不用担心作业长期得不到处理。,就绪队列1,就绪队列2,就绪队列3,就绪队列4,至CPU,至CPU,至CPU,至CPU,S1,S2,S3,（时间片：S1S2S3）,新进程,2019年11月22日,第二章进程管理,24,3.4实时调度,提供必要的信息就绪时间，任务就绪的起始时间；开始截止时间和完成截止时间；处理时间，一个任务从开始执行直至完成所需的时间；资源要求，任务执行的时候需要的一组资源；优先级，对紧迫任务设置“绝对”优先级，松弛任务设置“相对”优先级。,1.实现实时调度的基本条件,2019年11月22日,第二章进程管理,25,3.4实时调度,1.实现实时调度的基本条件,具有快速切换机制对外部中断的快速响应能力；快速的任务分派能力。,系统处理能力强,采用抢占式调度机制,采用单处理机系统，增强处理能力，减少每个任务处理时间；采用多处理剂调度,单处理机实时调度条件：,2019年11月22日,第二章进程管理,26,3.4实时调度,非抢占式调度算法非抢占式轮转调度算法；非抢占式优先级调度算法。抢占式调度算法基于时钟中断的调度算法立即抢占的调度算法,2.实时调度算法分类,最早截止时间优先EDF（EarliestDeadlineFirst）算法,3.常用的几种实时调度算法,最低松弛度优先级LLF（LeastLaxityFirst）算法任务的松弛度=必须完成时间-其本身运行时间-当前时间松弛度=0表示该任务必须马上执行，否则会造成严重后果。,2019年11月22日,第二章进程管理,27,3.5产生死锁的原因和必要条件,竞争资源：多个进程共享资源，资源数目不足所引起进程对资源的竞争；可剥夺资源和非可剥夺性资源竞争非剥夺性资源竞争临时性资源,1.产生死锁的原因,死锁（Deadlock）：是指多个进程在运行过程中因争夺资源而造成的一种僵局（DeadlyEmbrace），当进程出于这种僵持状态时，若无外力作用，它们将无法再向前推进。,2019年11月22日,第二章进程管理,28,3.5产生死锁的原因和必要条件,1.产生死锁的原因,进程推进顺序非法：请求和释放资源顺序不当。1）进程推进顺序合法2）进程推进顺序非法,P1：Request(R1);Request(R2);P1：Release(R1);Release(R2);P2：Request(R1);Request(R2);P2：Release(R1);Release(R2);,P1：Request(R1);P2：Request(R2);P1：Request(R2);P2：Request(R1);,P1,P2,R1,R2,2019年11月22日,第二章进程管理,29,3.5产生死锁的原因和必要条件,（1）互斥条件，一段时间内某资源只能由一个进程占用；（2）请求和保持条件，部分分配资源；（3）不剥夺条件，进程已获得资源不能被剥夺；（4）环路等待条件，发生死锁时必然存在进程-资源的环形链。,2.产生死锁的必要条件,（1）预防死锁：通过设置某些限制条件，去破坏产生死锁的四个必要条件中的一个或者几个，预防死锁的发生；（2）避免死锁：在资源的动态分配过程中，用某种方法去防止系统进入不安全状态，从而避免发生死锁；（3）检测死锁：通过系统所设置的检测机制，及时地检测出死锁的发生，并精确地确定与死锁有关的进程和资源；（4）解除死锁：与死锁检测配合，通过撤销和挂起一些进程，以便回收一些资源，再将这些资源分配给处于阻塞状态的进程，使之就绪，以继续运行。,3.处理死锁的基本方法,2019年11月22日,第二章进程管理,30,3.6预防死锁的方法,（1）摒弃“请求和保持”条件，部分分配资源；（2）摒弃“不剥夺”条件，进程已获得资源不能被剥夺；（3）摒弃“环路等待”条件，发生死锁时必然存在进程-资源的环形链。,1.预防死锁,安全状态是指系统能按某种进程顺序（P1，P2，Pn），来为没个进程Pi分配其所需资源，直至满足每个进程对资源的最大需求，使每个进程都顺利执行。安全状态实例:假设系统中有三个进程P1，P2，P3，共12台磁带机。,2.系统安全状态,2019年11月22日,第二章进程管理,31,3.6预防死锁的方法,数据结构,3.银行家算法,（1）可利用资源向量Available（m个元素的数组），其中Availablej=k，表示系统中Rj类资源有k个。（2）最大需求矩阵Max（nm）的矩阵，Maxi,j=k，表示进程Pi请求Rj类资源的最大数据是k个。（3）分配矩阵Allocation（nm）的矩阵，Allocationi,j=k，表示Pi已经分得Rj类资源的数目是k个。（4）需求矩阵Need（nm）的矩阵，Needi,j=k，表示Pi请求Rj类资源的数目是k个。上述关系：Needi,j=Maxi,j-Allocationi,j；,2019年11月22日,第二章进程管理,32,3.6预防死锁的方法,算法描述,3.银行家算法,假设Requesti是Pi的请求向量，Requestij=k表示Pi请求k个Rj类资源，Pi申请后，系统进行检查：（1）如果RequestijNeedi,j，则转（2），否则出错（需要资源超过它宣布的最大值）。（2）如果RequestijAvailablej，则转（3），否则尚无足够的资源，Pi必须等待。（3）系统为Pi分配资源（试探性的分配）：Availablej=Availablej-Requestij;Allocationi,j=Allocationi,j+Requestij;Needi,j=Needi,j-Requestij;（4）执行安全性算法，若安全则分配（为Pi），否则不分配，令Pi等待。,2019年11月22日,第二章进程管理,33,3.6预防死锁的方法,安全性算法,3.银行家算法,（1）设置两个向量：工作向量Work，表示系统可提供给进程急需运行所需的各类资源数目，含有m个元素，初始work=Available；向量Finish，表示系统是否有足够的资源分配给进程，使之运行完成，初始时Finish=false，有足够资源分配时，Finish=true；（2）在进程集合中找到一个能满足下述条件的进程：a）Finishii=false;b）Needi,jWorkj；如果找到则转（3），否则转（4）；（3）进程Pi获得资源可顺利完成，并释放资源，则执行Workj=Workj+Allocationi,j;Finishi=true;转（2）；（4）如果所有进程的Finishi=true都满足，表示系统处于安全状态，否则系统进入不安全状态。,2019年11月22日,第二章进程管理,34,3.6预防死锁的方法,假设系统中有五个进程P0,P1,P2,P3,P4和三类资源A,B,C，各种资源的数量分别为10、5、7，在T0时刻的资源分配情况下表：,4.银行家算法的实例,2019年11月22日,第二章进程管理,35,3.6预防死锁的方法,4.银行家算法的实例,(1)T0时刻的安全性：存在安全序列P1,P3,P4,P2,P0。,2019年11月22日,第二章进程管理,36,3.6预防死锁的方法,4.银行家算法的实例,(2)P1请求资源，发出请求向量Request1(1,0,2)，进行检查Request1(1,0,2)Need1(1,2,2);Request1(1,0,2)Available1(3,3,2);存在安全序列P1,P3,P4,P0,P2。,(3)P4请求资源，发出请求向量Request4(3,3,0)，检查Request4(3,3,0)Need4(4,3,1);Request4(3,3,0)Available4(2,3,0);让P4等待。,2019年11月22日,第二章进程管理,37,3.6预防死锁的方法,4.银行家算法的实例,(4)P0请求资源，发出请求向量Request0(0,2,0)，进行检查Request0(0,2,0)Need0(7,4,3);Request0(0,2,0)Available0(2,3,0);假定为P0分配资源。,(5)进行安全性检查，Available(2,1,0)已不能满足任何进程需要，故系统进入不安全状态。,2019年11月22日,第二章进程管理,38,3.7死锁的检测与解除,资源分配图（ResourceAllocationGraph）RAG是由一组结点N和一组边E组成的一个对偶RAG=（N，E），对它的约定如下：（1）P=p1,p2,pnR=r1,r2,rnP和R是两个互斥的子集，N=PR（2）eE，它连接P中的一个结点和R中的一个结点e=（pi,rj)资源请求边（pi指向rj）表示pi请求一个单位的rj；e=（rj,pi)资源请求边（rj指向pi）表示pi分配到一个单位的rj；,1.死锁的检测,P1,P2,R1,R2,2019年11月22日,第二章进程管理,39,3.7死锁的检测与解除,资源分配图的简化（1）从RAG中找出既不阻塞又不是孤点的进程Pi，消去由Pi出发的和指向Pi的所有边（请求边和分配边），这等价于Pi获得它所需的资源，不断向前推进，一直运行完毕，释放出它们所占有的全部资源。（2）进程Pi所释放的资源可以唤醒某些阻塞于该资源的进程Pj