第5章处理器调度.ppt

,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,第5章处理器调度,引言,处理器是计算机系统中一个十分重要的资源。随着多道程序设计技术出现，处理器的管理也日趋复杂。对于不同类型的操作系统，处理器的管理方法各不相同。不同的处理器管理方法将为用户提供不同性能的操作系统。因此，根据,操作系统目标,的不同，,处理器的管理策略,是不尽相同的。,本章将以处理器管理为核心，讨论与处理器调度有关的概念，并介绍常用的调度算法。,5,1,三级调度的概念,在多道程序系统中，一个作业被提交后，并不一定能立即执行，必须经过处理器调度，方可为其创建进程，分配内存，从而进入执行状态，称为作业调度或高级调度。而作业的执行归结为进程的调度，又称为低级调度。在比较完善的系统中，为了提高内存的利用率，往往还设置了对换调度，即中级调度。,5,1,1,作业的状态及其转换,作业,是用户在一次解题或一个事务处理过程中要求计算机系统所做的工作的集合。,作业由用户,程序、所需的数据及作业说明书,三部分组成。,计算机系统完成一个作业过程中所做的一项相对独立的工作称为一个,作业步,。,在多道程序系统中，一个作业在它的生命期内要经历,提交、后备、运行和完成,四个主要的阶段。,5,1,1,作业的状态及其转换,提交状态：,当用户将自己的作业提交给操作员，操作员通过某种输入方式将用户提交的作业输入到外存上时，称此阶段为作业处于提交状态。作业输入方式通常有,5,种：,联机输入方式：,该方式大多用在交互式系统中，用户和系统通过交互式会话来输入作业。在联机方式中，外围设备直接和主机相连接，一台主机可连接一台或多台外围设备。,脱机输入方式：,脱机输入方式利用低档,I/O,处理器作为外围处理器进行输入处理，提高了主机的资源利用率。,5,1,1,作业的状态及其转换,联机输入方式：,该方式大多用在交互式系统中，用户和系统通过交互式会话来输入作业。在联机方式中，外围设备直接和主机相连接，一台主机可连接一台或多台外围设备。,脱机输入方式：,脱机输入方式利用低档,I/O,处理器作为外围处理器进行输入处理，提高了主机的资源利用率。,5,1,1,作业的状态及其转换,直接耦合方式：,该方式是把主机和外围低档机通过一个公用的大容量外存直接耦合起来，从而省去了在脱机输入时依靠人工干预来传递给后援存储器的过程。,SPOOLing,系统：,在,SPOOLing,系统中，多台外围设备通过通道或,DMA,器件将主机与外存连接起来，作业的输入过程由主机中的操作系统控制。,网络输入方式：,该方式以上述几种输入方式为基础。当用户需要把在网络中某一台主机上输入的信息传递到同一网络中的另一台主机上进行操作或执行时，就构成了网络输入方式。,5,1,1,作业的状态及其转换,后备状态：,当操作系统为输入并存放在外存输入井上的作业建立一个作业控制块（,JCB,，,Job Control Block,）之后，作业就进入了后备状态。作业从建立,JCB,到被作业调度程序选中运行，所处的状态叫做后备状态。,运行状态：,作业调度程序从处于后备状态的作业队列中按一定的算法选中一个作业调入内存，并为之建立相应的进程后，由于此时的作业已具有独立运行的资格，如果处理器空闲，便可立即开始执行，称此时的作业进入了运行状态。,完成状态：,当作业（进程）运行正常完成或异常结束时，便自我终止（正常完成），或被迫终止（异常终止），此时作业便进入完成状态。,5,1,1,作业的状态及其转换,作业状态及其转换如下图所示：,提交状态,后备状态,完成状态,作业注册,作业调度,进程调度,作业结束,阻塞,就绪,运行,运行状态,5,1,2,调度的层次,高级调度：,高级调度又称作业调度。作业调度程序决定把哪些后备队列中的作业调入内存，并为其创建进程，分配必要的资源，最后将所创建的进程插入就绪队列，以使该作业的进程获得竞争处理器的权利。在批处理系统中或者是操作系统中的批处理部分都配有作业调度。,中级调度：,中级调度又称交换调度，它的主要功能是按一定的算法在内存和外存之间进行进程对换，其目的是为了使内存紧张的情况得以缓解。交换调度的主要工作是将内存中处于阻塞状态的某些进程换至外存，腾出内存空间以便将外存上已具备运行条件的进程换入内存，准备运行。进程在其整个生命期间可能要经历多次换进换出，在分时系统中常采用交换调度。,5,1,2,调度的层次,低级调度：,低级调度又称进程调度。其主要任务是按照某种策略和方法选取一个处于就绪状态的进程占用处理器。它决定就绪队列中哪个进程先获得处理器，然后再由分派程序执行将处理器分配给进程的操作。,5,1,3,调度模型,从上述操作系统的调度类型可知，虽然操作系统的调度机制不尽相同，有的操作系统仅设有低级调度，有的操作系统则拥有高级调度和低级调度，有的操作系统三级调度一应俱全。但是操作系统中的任何一种调度都涉及进程队列，因此根据操作系统的不同性能，一般有三种相应的调度队列模型。,5,1,2,调度的层次,一级调度队列模型：,一级调度模型仅设置了进程调度。在这种调度模型中，用户输入的命令和数据都直接送入内存。操作系统会为每一个作业建立一个或多个进程，并将它们插入就绪队列，然后按照时间片轮转方式进行调度。一级调度队列模型如下图所示：,5,1,2,调度的层次,CPU,就绪队列,阻塞队列,进程调度,时间片完,事件发生,等待事件,交互用户,进程完成,5,1,2,调度的层次,二级调度队列模型：,在二级调度队列中，不仅有进程调度，还有作业调度。作业调度从外存中选择一批作业调入内存，为其创建进程并送入就绪队列。同时，当操作系统任务较多时，阻塞队列有可能很长。为了提高执行效率，通常设置若干个阻塞队列，不同队列对应于引起进程阻塞的不同原因。二级调度队列模型如下图所示：,5,1,2,调度的层次,：,后备作业队列,等待事件,2,阻塞队列,2,就绪队列,事件,1,发生,等待事件,1,阻塞队列,1,时间片完,事件,2,发生,等待事件,n,阻塞队列,n,事件,n,发生,作业调度,进程调度,：,CPU,5,1,2,调度的层次,三级调度队列模型：,三级调度队列模型同时拥有作业调度，交换调度和进程调度。在引入交换调度之后，可以把处于静止就绪和静止阻塞的进程从内存交换到外存上，以使内存紧张的状况得以缓解。三级调度队列模型如下图所示：,5,1,2,调度的层次,交换调度,(,外存,),进程完成,后备作业队列,就绪队列,静止就绪队列,时间片完,等待事件,阻塞队列,n,事件发生,作业调度,静止阻塞队列,进程调度,CPU,5,2,作业调度,只有批处理系统才必须具有作业调度。在分时系统和实时系统中都没有作业调度的概念。因为在分时系统中，由于要进行人机交互，系统必须能及时响应，为此应把用户从终端输入的作业直接送入内存而不是建立在外存上，因此，不再需要专门用于把作业从外存调入内存的作业调度过程。对于实时系统中的实时任务，因为通常对其响应的时间更为严格，故也不需要作业调度。,5,2,1,作业调度的功能,作业调度主要是完成作业从后备状态到运行状态的转变，以及从运行状态到完成状态的转变。其主要功能如下：,记录系统中各作业的状况：,作业调度程序要能挑选出一个作业投入运行，并且在运行中对其进行管理。它必须掌握作业在各个状态，包括运行阶段的有关情况。为此，系统为每个作业建立一个作业控制块,JCB,（,Job Control Block,）来记录这些有关信息。,JCB,的主要内容包括作业名、作业类型、资源要求、当前状态、资源使用情况以及该作业的优先级等。与系统感知进程存在时要通过进程控制块,PCB,一样，系统通过,JCB,而感知作业的存在。,5,2,1,作业调度的功能,从后备队列中挑选出一部分作业投入执行,：,作业调度程序根据选定的调度算法，从后备作业队列中挑选出若干作业去投入运行。,为被选中的作业做好运行前的准备工作,：,作业调度程序为选中的作业建立相应的进程，并为这些进程分配它们所需要的全部资源，如分配给它们内存、外存、外设等。,在作业运行结束时做善后处理工作,：,善后处理主要是输出作业管理信息，例如执行时间等。再就是回收该作业所占用的资源，撤消与该作业有关的全部进程和该作业的作业控制块等。,5,2,2,作业调度的目标与性能衡量,面向系统的准则,：,不同的操作系统有不同的要求，为了满足系统功能的要求，在设计操作系统时，应遵循一些准则，最重要的有以下几点：,吞吐量大：,这是用来评价批处理系统的重要指标。吞吐量是单位时间内完成的作业数，它与批处理作业的平均长度有着密切关系。但作业调度的方式和算法，对吞吐量的大小也将产生较大的影响。,CPU,利用率高：,对于大中型多用户系统，由于,CPU,价格十分昂贵，所以,CPU,的利用率成为衡量大中型系统性能的十分重要的指标。而调度方式和算法，对,CPU,的利用率起着十分重要的作用。,5,2,2,作业调度的目标与性能衡量,各类资源的平衡利用：,在大中型系统中，有效地利用各类资源（如,CPU,、内存、外存和,I/O,设备等），也是一个重要指标。对于微机和某些实时系统，该准则也不那么重要。,5,2,2,作业调度的目标与性能衡量,面向用户的准则,：,为了满足用户对操作系统的要求，应满足如下准则：,周转时间短：,周转时间是评价批处理系统的一个重要性能指标。作业周转时间是指从作业提交给系统开始，到作业完成为止的时间间隔。,平均周转时间：,计算机系统为使大多数用户对周转时间感到满意，引入了平均周转时间,T,的评价指标。对于有,n,个作业的系统，平均周转时间可描述为：,5,2,2,作业调度的目标与性能衡量,式中，,n,是系统中的作业个数，,Ti,是第,i,个作业的周转时间，,Tei,是作业的完成时间，,Tsi,是作业的提交时间。,平均带权周转时间：周转时间没有考虑作业的运行时间，不能准确反映作业周转时间与作业运行时间的关系。为此引入了平均带权周转时间。一个作业的带权周转时间定义为作业的周转时间与系统为它提供的实际服务时间之比，即,W=Ti/Tri,。,n,个作业的平均带权周转时间为：,式中，,Tri,是系统为作业,i,提供的实际服务时间。,5,2,2,作业调度的目标与性能衡量,响应时间快：,响应时间是评价分时系统的性能指标。它是从用户通过键盘提交一个请求开始，直至系统首次产生响应为止的时间，或者说直到屏幕显示结果为止的时间。,截止时间的保证：,在实时系统中，截止时间是衡量系统性能好坏的重要指标。截止时间是指某任务必须完成的最迟时间。对于严格的实时系统，其调度方式和调度算法必须保证这一点，否则将可能引起难以预料的后果。,优先权准则：,在批处理、分时、实时和多模式系统中，都可使用优先权准则，以便让那些紧急的作业得到及时的处理。在要求较严格的场合，往往还需要选择抢占调度方式，才能保证紧急作业得到及时的处理。,5,3,进程调度,进程调度的任务是控制、协调多个进程对处理器的竞争，即按照一定的调度算法从就绪队列中选中一个进程，并把处理器的使用权交给被选中的进程。操作系统为了对进程进行有效的监控，需要维护一些与进程相关的数据结构，记录所有进程的运行情况，并在进程让出处理器或调度程序剥夺运行状态进程占用处理器时，选择适当的进程分派处理器，完成上下文的切换。我们把操作系统内核中完成这些功能的部分称为进程调度程序（,scheduler,），它所使用的算法称为调度算法（,scheduling algorithm,）。,5,3,进程调度,进程调度的任务是控制、协调多个进程对处理器的竞争，即按照一定的调度算法从就绪队列中选中一个进程，并把处理器的使用权交给被选中的进程。操作系统为了对进程进行有效的监控，需要维护一些与进程相关的数据结构，记录所有进程的运行情况，并在进程让出处理器或调度程序剥夺运行状态进程占用处理器时，选择适当的进程分派处理器，完成上下文的切换。我们把操作系统内核中完成这些功能的部分称为进程调度程序（,scheduler,），它所使用的算法称为调度算法（,scheduling algorithm,）。,5,3,1,进程调度的功能,进程调度的功能：,作为进程调度的准备，进程管理模块必须将系统中各进程的执行情况和状态特征记录在各进程的,PCB,中，作为管理进程的依据。,选择占有处理器的进程：,进程调度的主要功能是按照一定的策略选择一个处于就绪状态的进程，使其获得处理器运行。根据不同的系统设计目标，有各种各样的选择策略。,进行进程上下文的切换,：,进程的上下文是进程执行活动全过程的静态描述。一个进程的上下文包括进程的状态、有关变量和数据结构的值、机器寄存器的值和,PCB,以及有关程序、数据等。一个进程的执行是在进程的上下文中执行的。当正在运行的进程由于某种原因要让出处理器时，系统要做进程上下文切换，以使另一个进程得以运行。,5,3,2,进程调度方式,非剥夺调度方式：,调度程序一旦把处理器分配给某进程，该进程就将一直运行下去，只有当进程完成或发生其事件而阻塞时，系统才把处理器分配给另一进程的调度方式称为非剥夺调度，也称非抢占方式（,nonpreemptive,scheduling,）方式。在此调度方式下，系统不得以任何理由剥夺现行进程所占用的处理器。该调度方式的优点是简单、系统开销小，但却可能导致系统性能的恶化，表现为：,当一个紧急任务到达时，不能立即投入运行，以至于延误时机；,若干个后到的短作业，需要等待先到的长作业运行完毕后才能运行，致使短作业的周转时间较长。,5,3,2,进程调度方式,剥夺调度方式：,进程的另一种调度方式是剥夺调度方式，或称抢占方式（,preemptive scheduling,），这是指进程正在运行时，系统可根据某种原则，剥夺已分配给它的处理器，并将处理器再分配给其他进程的一种调度方式。剥夺的原则有：,优先权原则。优先权高的进程可以剥夺优先权低的进程的运行；,短进程优先原则。短进程到达后可以剥夺长进程的运行；,时间片原则。一个时间片运行完后重新调度。,5,3,3,进程调度的时机,进程调度发生的时机，与引起进程调度的原因以及进程调度的方式有关。引起进程调度的原因有以下几类：,正在执行的进程执行完毕或由于某种错误而异常中止。,执行中的进程自己调用阻塞原语将自己阻塞起来而进入等待状态（如等待某一事件而事件未发生或调用了,wait,原语而资源不足等）。,分时系统中的时间片用完。,在执行完系统调用等系统程序后返回用户进程时，这时可看作系统进程运行完毕，从而可选择一新的用户进程执行。,5,3,3,进程调度的时机,在基于优先级调度的策略时，就绪队列中的某进程的优先级变得高于当前运行进程的优先级，从而也将引发进程调度。,以上,1,4,条是在剥夺和不可剥夺情况下引起进程调度的原因，而第,5,条是在剥夺情况下引起调度的原因。,5,4,常用的调度算法,调度算法是指：根据系统的资源分配策略所规定的资源分配算法。对于不同的系统和系统目标，通常采用不同的调度算法。目前存在着多种调度算法，有的算法适用于作业调度，有的算法适用于进程调度，但也有些调度算法，既可用于作业调度，也可用于进程调度。,5,4,1,先来先服务调度算法,实现方法：,先来先服务,FCFS,（,First Come First Serve,，,FCFS,）调度算法是一种最简单的调度算法。其基本思想是：将用户作业或就绪进程按提交或变为就绪状态的先后次序排成队列，调度时总是选择队首作业或进程投入运行。该算法既可用于作业调度，也可用于进程调度。,优缺点：,虽然,FCFS,调度算法易于实现，表面上也公平，但服务质量不佳，对短作业用户不公平。,使用场合：,FCFS,算法很少作为进程调度的主调度算法，但常作为一种辅助调度算法。,5,4,1,先来先服务调度算法,【,例,5-1】,假设有五道作业，它们的进入时间和运行时间由下表给出：,作业号,进入时间,运行时间,1,0,4,2,1,3,3,2,6,4,3,2,5,4,4,在不剥夺方式的单道环境下，采用,FCFS,调度算法，试说明它们的调度顺序，并计算在该种调度算法下的平均周转时间和平均带权周转时间。,5,4,1,先来先服务调度算法,解：采用,FCFS,调度算法，调度顺序是,1,，,2,，,3,，,4,，,5,五道作业的执行时间、完成时间和周转时间如下表所示：,作业号,进入时间,运行时间,1,0,4,2,1,3,3,2,6,4,3,2,5,4,4,作业号,进入时间,运行时间,开始执行时间,完成时间,周转时间,1,0,4,0,4,4,2,1,3,4,7,6,3,2,6,7,13,11,4,3,2,13,15,12,5,4,4,15,19,15,平均周转时间,T,（,4+6+11+12+15,）,/5=9.8,小时,平均带权周转时间,W=(4/4+6/3+11/6+12/2+15/4)/5=2.92,5,4,2,短作业（进程）优先调度算法,实现方法：,SJF,调度算法是从后备队列中选择一个或若干个估计运行时间最短的作业，将它们调入内存运行。该调度算法可以照顾到实际上在所有作业中占很大比例的短作业，使它们能比长作业优先执行。,优缺点：,这种算法能有效地降低作业的平均周转时间，提高系统的吞吐量，但是，它们存在着不容忽视的缺点：,该算法对长作业不利。由于系统状态是动态的，如果不断地有短作业进入，则可能导致长作业长时间得不到响应；,该算法未考虑作业的紧迫程度；,5,4,2,短作业（进程）优先调度算法,由于作业（进程）的长短只是根据用户所提供的估计运行时间而定，而用户又可能会有意或无意地缩短其作业的估计执行时间，致使该算法不一定能真正做到短作业优先调度。,5,4,2,短作业（进程）优先调度算法,【,例,5-2】,仍采用例,5-1,的题目，在不剥夺方式的单道环境下，采用,SJF,调度算法，试说明它们的调度顺序，并计算在该种调度算法下的平均周转时间和平均带权周转时间。,作业号,进入时间,运行时间,1,0,4,2,1,3,3,2,6,4,3,2,5,4,4,5,4,2,短作业（进程）优先调度算法,解：采用,SJF,调度算法，调度顺序是,1,，,4,，,2,，,5,，,3,五道作业的执行时间、完成时间和周转时间如下表所示：,作业号,进入时间,运行时间,1,0,4,2,1,3,3,2,6,4,3,2,5,4,4,作业号,进入时间,运行时间,开始执行时间,完成时间,周转时间,1,0,4,0,4,4,4,3,2,4,6,3,2,1,3,6,9,8,5,4,4,9,13,9,3,2,6,13,19,17,平均周转时间,T,（,4+3+8+9+17,）,/5=8.2,小时,平均带权周转时间,W=(4/4+3/2+8/3+9/4+17/6)/5=2.05,5,4,3,时间片轮转调度算法,实现方法：,时间片轮转法,RR,（,Round Robin,）是将,CPU,的处理时间分成固定大小的时间片，且采用剥夺调度方式。在简单轮转法中，系统将所有就绪进程按先进先出规则排成一个环形队列，把,CPU,分配给队首进程，并规定它执行一个时间片。当时间片用完时，系统剥夺该进程的运行并将它送到就绪队列末尾，重新把处理器分配给就绪队列中新的队首进程。,5,4,3,时间片轮转调度算法,【,例,5-3】,假设有五道作业，它们的进入时间和运行时间由下表给出：,作业号,进入时间,运行时间,A,0,4,B,1,2,C,2,5,D,3,3,E,4,3,画出当时间片分别为,q=1,和,q=4,时的调度图，并计算该种调度算法时的平均周转时间和平均带权周转时间。,5,4,3,时间片轮转调度算法,时刻,运行进程,排队进程,时刻,运行进程,排队进程,0,1,A,9,10,D,AEC,1,2,B,A,10,11,A,ECD,2,3,A,CB,11,12,E,CD,3,4,C,BDA,12,13,C,DE,4,5,B,DAEC,13,14,D,EC,5,6,D,AEC,14,15,E,C,6,7,A,ECD,15,16,C,7,8,E,CDA,16,17,C,8,9,C,DAE,解：当时间片,q=1,时，列出下表，找出运行序列：,5,4,3,时间片轮转调度算法,根据上表，画出调度图如下图所示：,A,B,C,D,E,0,1,2,3,4,5,6,7,8,9,11,10,12,13,14,15,16,17,5,4,3,时间片轮转调度算法,从上图得出的五道作业的完成时间和周转时间如下表所示：,作业号,进入时间,运行时间,完成时间,周转时间,A,0,4,11,11,B,1,2,5,4,C,2,5,17,15,D,3,3,14,11,E,4,3,15,11,平均周转时间,T,（,11+4+15+11+11,）,/5=10.4,平均带权周转时间,W=(11/4+4/2+15/5+11/3+11/3)/5=3.02,5,4,3,时间片轮转调度算法,当时间片,q=4,时，调度图如下图所示：,A,B,C,D,E,0,1,2,3,4,5,6,7,8,9,11,10,12,13,14,15,16,17,5,4,3,时间片轮转调度算法,如果一个作业的时间片没有用完，剩余时间可由下一个作业使用。从上图得出的五道作业的完成时间和周转时间如下表所示：,作业号,进入时间,运行时间,完成时间,周转时间,A,0,4,4,4,B,1,2,6,5,C,2,5,11,9,D,3,3,14,11,E,4,3,17,13,平均周转时间,T,（,4+5+9+11+13,）,/5=8.4,平均带权周转时间,W=(4/4+5/2+9/5+11/3+13/3)/5=2.66,5,4,4,高优先权优先调度算法,实现方法：,为了使紧急的作业得到优先调度，在许多系统中，每个作业或进程都被指定一个优先级，调度程序总是选择相应队列中具有最高优先权的作业或进程，这就是高优先权优先（,First Priority First,，,FPF,）调度算法。,优先权确定方法：,静态优先权：,静态优先权是在创建进程时确定的，在整个运行期间不再改变。基于静态优先权的调度算法实现简单，系统开销小。但由于静态优先权一旦确定之后，直到运行结束为止始终保持不变，从而使优先级低的进程长时间得不到调度。,5,4,4,高优先权优先调度算法,动态优先权：,动态优先权是基于某种原则，使进程的优先权随时间而改变，例如在就绪队列中的进程，其优先权以速度,a,增加，若再令正在执行进程的优先权以速度,b,下降，便可防止一个长作业长期垄断处理器这种情况的发生。,优先数与优先级的关系,；,在,UNIX,和许多其他的系统中，优先级数值越大，表示的进程优先权越低；而在某些系统中的用法则刚好相反，如,Windows,，大数值表示高优先级。,5,4,4,高优先权优先调度算法,【,例,5-4】,假设有五道作业，它们的进入时间、运行时间和静态优先数由下表给出：,作业号,进入时间,运行时间,优先数,1,0,4,6,2,1,3,4,3,2,6,2,4,3,2,5,5,4,4,3,假定优先数越高，优先级越低，系统采用静态,FPF,调度算法，且不可剥夺，试计算采用该调度算法时的平均周转时间和平均带权周转时间。,5,4,4,高优先权优先调度算法,解：,采用静态,FPF,调度算法，调度顺序是,1,，,3,，,5,，,2,，,4,。,五道作业的执行时间、完成时间和周转时间如下表所示：,作业号,进入时间,运行时间,开始执行时间,完成时间,周转时间,1,0,4,0,4,4,3,2,6,4,10,8,5,4,4,10,14,10,2,1,3,14,17,16,4,3,2,17,19,16,平均周转时间,T,（,4+8+10+16+16,）,/5=10.8,小时,平均带权周转时间,W=(4/4+8/6+10/4+16/3+16/2)/5=3.63,5,4,5,最高响应比优先调度算法,响应比计算公式：,最高响应比优先（,Highest,Response_ratio,Next,，,HRN,）调度算法是,FCFS,和,SJF,的一种折衷。,HRN,调度算法同时考虑每个作业的等待时间和估计的运行时间。设响应比为,R,，则作业,p,的响应比为：,式中，,W,为作业的等待时间，,T,为作业的估计运行时间。,5,4,5,最高响应比优先调度算法,算法思想：,在当前进程完成或被阻塞时，选择,Rp,值最大的就绪进程投入运行。,优点：,即考虑了作业的等待时间，又照顾了短作业。,5,4,5,最高响应比优先调度算法,【,例,5-4】,假设有五道作业，它们的进入时间、运行时间由下表给出：,系统采用,HRN,调度算法，试计算采用该调度算法时的平均周转时间和平均带权周转时间。,作业号,进入时间,运行时间,1,0,6,2,1,4,3,2,4,4,3,1,5,4,3,5,4,5,最高响应比优先调度算法,解：,采用,HRN,调度算法，应在每次调度时计算各作业的响应比，选择响应比高的作业进入运行状态。,在时刻,0,，由于只有作业,1,，因此调度,作业,1,投入运行，作业,1,运行到时刻,6,结束，在时刻,6,时进行调度；,在时刻,6,，计算各作业的响应比为：,作业,2,的响应比：,R,2,=1+,（,6-1,）,/4=2.25,作业,3,的响应比：,R,3,=1+,（,6-2,）,/4=2,作业,4,的响应比：,R,4,=1+,（,6-3,）,/1=4,作业,5,的响应比：,R,5,=1+,（,6-4,）,/3=1.67,选择,作业,4,投入运行，作业,4,运行到时刻,7,时结束，在时刻,7,时进行调度；,5,4,5,最高响应比优先调度算法,在时刻,7,，计算各作业的响应比为：,作业,2,的响应比：,R,2,=1+,（,7-1,）,/4=2.5,作业,3,的响应比：,R,3,=1+,（,7-2,）,/4=2.25,作业,5,的响应比：,R,5,=1+,（,7-4,）,/3=2,选择,作业,2,投入运行，作业,2,运行到时刻,11,时结束，在时刻,11,时进行调度；,作业,3,的响应比：,R,3,=1+,（,11-2,）,/4=3.25,作业,5,的响应比：,R,5,=1+,（,11-4,）,/3=3.33,选择,作业,5,投入运行，作业,5,运行到时刻,14,时结束，在时刻,14,时进行调度；,在时刻,14,，只有作业,3,等待运行，因此五道作业的调度顺序是,1,，,4,，,2,，,5,，,3,。,5,4,5,最高响应比优先调度算法,五道作业的执行时间、完成时间和周转时间如下表所示：,作业号,进入时间,运行时间（小时）,开始执行时间,完成时间,周转时间,1,0,6,0,6,6,4,3,1,6,7,4,2,1,4,7,11,10,5,4,3,11,14,10,3,2,4,14,18,16,平均周转时间,T,（,6+4+10+10+16,）,/5=9.2,小时,平均带权周转时间,W=(6/6+4/1+10/4+10/3+16/4)/5=2.97,5,4,6,多级队列调度算法,多级队列调度算法（,Multiple-level Queue,，,MQ,）的基本思想是引入多个就绪队列，通过各队列的区别对待，达到一个综合的调度目标。在多级队列调度算法中，根据作业或进程的性质或类型的不同，将就绪队列再分成若干个子队列，每个作业固定归入一个队列，例如，系统进程、用户交互进程、批处理进程等不同队列。不同队列可有不同的优先级、时间片长度、调度策略等。,5,4,7,多级反馈队列调度算法,多级反馈队列（,Round Robin with Multiple Feedback,，,RRMF,）调度算法是时间片轮转算法和优先级调度算法的综合和发展。在多级反馈队列调度算法中，通常设置多个就绪队列，并赋予各队列不同的优先级。如队列,1,的优先级最高，然后逐级降低。每个队列的执行时间片长度也不同，如规定优先级越低则时间片越长。,5,4,7,多级反馈队列调度算法,多级反馈队列调度算法如下图所示：,第一级队列,（,FIFO,）,完成,第二级队列,（,FIFO,）,完成,第,n,级队列,（,FIFO,）,完成,：,CPU,CPU,CPU,5,5,实例分析：,UNIX,进程调度,UNIX System V,的进程调度涉及调度时机、调度标记设置、优先数计算、调度的实现等。下面分别说明。,5,5,1,调度时机,UNIX System V,在以下,5,种情况之一发生时进行进程调度：,现行进程自己调用,sleep,或,wait,等进入睡眠状态时；,现行进程调用,exit,自我终止时；,现行进程的时间片到期且优先级低于其它就绪进程时；,现行进程在完成中断和陷入处理后返回用户态时，它的优先级已低于其它就绪进程或者调度标记被置位；,现行进程从系统调用执行结束后返回用户态时，它的优先级已低于其它就绪进程或者调度标记被置位。,5,5,2,调度标记设置,runrun,是要求进行进程调度时的标记。若,wakeup,，,setrun,以及,setpri,（设置优先级）命令发现某进程的优先级高于现行进程时，置,runrun,为,1,。另外在秒中断处理过程中也将检查各就绪进程的优先级，发现优先级高于现行进程时，同样置,runrun,为,1,。,5,5,3,优先数计算,传统的,UNIX System V,采用动态优先数调度策略，优先数越大优先级越低。调度程序从内存就绪队列中选取优先数最小的进程作为上行进程。优先数基于进程类型和运行历史，计算公式如下：,其中，,PUSER,和,NZERO,分别取常数,25,和,20,，称它们为基本用户优先数的阈值，,p_CPU,为进程最近一次使用,CPU,的时间。当进程使用,CPU,时，系统每个时钟周期对该进程的,p_CPU,加,1,，该值最多可达,80,。此外，秒中断时对,p_CPU,执行除以,2,的衰减操作。这样，如果系统的时钟周期为,16.667ms,的话，则遇秒中断时,p_CPU,将由,60,变为,30,。,5,5,3,优先数计算,p_nice,是系统允许用户使用,nice,系统调用影响进程优先数的偏移值，范围在,040,之间。但一旦设置后，普通用户只能作递增修改。,5,5,4,调度的实现,UNIX,系统的进程调度是由,swtch,过程实现的，,swtch,过程是进程,0,的一部分。,首先，,调度程序把现行进程的上下文（主要是寄存器上下文和栈指针）保存到核心栈或,user,结构内的,u_rsav,，,u_pcb,字段中，这是由过程,save,（,u.u_rsav,）完成的。,其次，,按计算优先数的公式从内存就绪队列中寻找优先级最高的进程作为上行进程。若内存就绪队列中没有这样的进程存在，就调用空闲进程等待某进程变成就绪状态。清除,runrun,标记。,最后，,调用,resume,过程恢复上行进程的上下文，恢复核心栈或,user,结构内的,u_rsav,及,u_pcb,，从而使上行进程变成现行进程。,