第三章 处理机调度_new.ppt

1、1,在多道程序环境中，主存中有多个进程，其数目往往多于处理机数目，这就要求系统能按某种算法，动态地把处理机分配给就绪队列中的一个进程，使之执行，分配处理机的任务是由处理机调度程序完成的。 由于处理机是重要的资源，提高处理机的利用率及改善系统的性能，在很大程度上取决于处理机调度性能的好坏。,第3章 处理机调度*,2,处理机调度的层次 进程调度,第3章 处理机调度*,3,高级调度 低级调度 中级调度,（一）处理机调度的层次,4,1、高级调度,高级调度又称为作业调度，主要功能是根据某种算法，把外存上处于后备队列中的那些作业调入内存，调度的对象是作业。 作业：作业是比程序更为广泛的概念，它不仅包含了通

2、常的程序和数据，还配有一个作业说明书，系统根据作业说明书来对程序的运行进行控制。 在批处理系统中，是以作业为基本单位从外存调入内存的。,5,1、高级调度,作业控制块JCB：它包括作业名、作业类型、资源要求、当前状态、资源使用情况以及该作业的优先级等。,每当作业进入系统时，系统便为每个作业建立一个JCB，根据作业类型把它插入相应的后备队列中，作业调度程序根据一定的调度算法来调度它们，被调度到的作业将会装入内存。进入内存的作业，将为它们创建进程，分配必要的资源，然后将新创建的进程插入到就绪队列中。,6,1、高级调度,在每次执行作业调度时，都须做出以下两个决定。 1) 接纳多少个作业：即允许多少个作

3、业同时在内存中运行。当内存中同时运行的作业数目太多时，可能会影响到系统的服务质量。 2) 接纳哪些作业：应将哪些作业从外存调入内存，这取决于所采用的调度算法。,7,2、低级调度,低级调度也称为进程调度。 低级调度用于决定就绪队列中的哪个进程获得处理机。,8,3、中级调度,中级调度又称中程调度。 引入中级调度的主要目的，是为了提高内存利用率和系统吞吐量。 为此，应使那些暂时不能运行的进程不再占用宝贵的内存资源，而将它们调至外存上去等待，把此时的进程状态称为就绪驻外存状态或挂起状态。当这些进程重又具备运行条件、且内存又稍有空闲时，由中级调度来决定把外存上的哪些又具备运行条件的就绪进程，重新调入内存

4、，并修改其状态为就绪状态，挂在就绪队列上等待进程调度。,9,4、调度队列模型,仅有进程调度的调度队列模型 具有高级和低级调度的调度队列模型 同时具有三级调度的调度队列模型,10,（1）仅有进程调度的调度队列模型,11,（2）具有高级和低级调度的调度队列模型,12,（3）同时具有三级调度的调度队列模型,13,（二）进程调度*,进程调度需要解决三个主要问题： （1）什么时候分配处理机，即需要确定处理机调度时机； （2）按什么原则分配处理机，即需要确定处理机调度算法； （3）如何分配处理机，即需要给出处理机调度过程。,14,在单处理机多道程序设计系统中，进程被作为占用处理机运行的执行单位。由于处理机

5、是最重要的计算机资源，所以合理、有效地选择进程占有处理机是进程调度的重要任务。提高处理机的利用率及改善系统响应时间、吞吐率，在很大程度上取决于进程调度性能的好坏。,15,进程调度,进程调度的任务是控制协调进程对CPU的竞争，即按一定的调度算法从就绪队列中选中一个进程，把CPU的使用权交给被选中的进程。,16,调度目标：,公平保证每个进程得到合理的CPU 时间 高效使CPU 保持忙碌状态即总是有进程在CPU 上运行 响应时间使交互用户的响应时间尽可能短 周转时间使批处理用户等待输出的时间尽可能短 吞吐量使单位时间内处理的进程尽可能多 由于这些目标的相互冲突，任一调度算法要想同时满足上述目标是不可

6、能的。,17,不同系统调度目标也不同：,在多道批处理系统中，为了提高处理机的效率和吞吐量，当调度一批作业运行时，尽可能使作业搭配合理，充分利用资源。 在分时系统中，由于用户使用交互式会话的工作方式，系统必须要有较快的响应时间，使得每个用户都感到如同只有他自己一人在使用计算机，因此考虑的是公平性。 在实时系统中，首先要保证截止时间，即某任务必须开始执行的最迟时间，或必须完成的最迟时间。,18,调度性能评价,定性衡量：调度的可靠性、简洁性 可靠性：一次进程调度是否可能引起数据结构的破坏，这要求对调度时机的选择和保存CPU现场十分谨慎。 简洁性：调度会涉及到多个进程和上下文切换，如果调度程序过于繁琐

7、和复杂，会耗去较大的系统开销。 定量评价：CPU的利用率评价、进程在就绪队列中的等待时间与执行时间之比等。,19,衡量调度策略的最常用的几个指标是： 周转时间：指将一个作业提交给计算机系统开始，到作业完成为止的这段时间间隔。 吞吐量：指在单位时间内，一个计算机系统所完成的作业数。 响应时间：指从用户向计算机提交一个请求开始，直至系统首次产生响应为止的时间。,20,1. 周转时间： 作业i的周转时间Ti为 Ti=Tei-Tsi 其中Tei为作业i的完成时间，Tsi为作业的提交时间。 对于被测定作业流所含有的n（n=1）个作业来说，其平均周转时间为： 一个作业的周转时间说明了该作业在系统内停留的时

8、间，包含两部分：等待时间；执行时间，即： Ti=TwiTri 这里，Twi主要指作业i等待处理机的时间。,21,2. 带权周转时间 作业的周转时间包含了两个部分，即等待时间和执行时间。为了更进一步反映调度性能，使用带权周转时间的概念。带权周转时间是作业周转时间与作业执行时间的比： Wi=Ti/Tri 对于被测定作业流所含有的几个作业来说，其平均带权周转时间为： 对于分时系统，除了要保证系统吞吐量大、资源利用率高之外，还应保证有用户能够容忍的响应时间。因此，在分时系统中，仅仅用周转时间或带权周转时间来衡量调度性能是不够的。,22,对于分时系统和实时系统来说，,仅用周转时间或带权周转时间衡量调度性

9、能是不够的，需要加平均响应时间作为衡量调度策略优劣的标准。 响应时间：指从用户向计算机提交一个请求开始，直至系统首次产生响应为止的时间。,23,评价指标：,批处理系统来说，主要的性能指标是 周转时间，平均周转时间（等待时间、平均等待时间） 带权周转时间，平均带权周转时间 分时系统来说，主要的性能指标是 响应时间，平均响应时间 实时系统来说，主要的性能指标是 截止时间,24,进程调度,何时调度？ 选择谁运行调度算法？ 调度时需要做什么？,25,一、何时调度进程调度的原因,(1) 正在执行的进程执行完毕。 (2) 执行中进程自己调用阻塞原语将自己阻塞起来进入睡眠等待状态。 (3) 执行中进程调用了

10、P原语操作，从而因资源不足而被阻塞；或调用了V原语操作激活了等待资源的进程队列进入就绪队列，并请求重新调度。 (4) 执行中进程提出IO请求后被阻塞。,26,以上都是在CPU执行不可剥夺方式下所引起进程调度的原因。在CPU执行方式是可剥夺时，还有： (5) 在分时系统中时间片已经用完。 (6) 就绪队列中的某进程的优先级变得高于当前执行进程的优先级，从而也将引发进程调度。,27,二、调度时需要做什么进程调度的功能,1保存“下降”进程现场 2选择将要运行的进程“上升”进程 3恢复“上升”进程的现场,28,三、调度算法,引入多道程序系统的直接目的就是想让处理机“忙”，一直以来处理机都是计算机系统中

11、的瓶颈资源之一，特别是在单处理机系统中，处于就绪状态的多个进程竞争使用一台处理机，所以当处理机空闲时，系统需要从多个就绪进程中挑选一个使其投入运行。选择哪一个呢？这需要按某一种算法。调度算法的实质就是一种资源分配。 从资源的角度来看，该算法确定了处理机的分配策略，故称其为处理机调度算法； 而从资源使用者的角度看，该算法确定了进程运行的次序，故也称进程调度算法。,29,不可抢占方式：在这种方式下，一旦把处理机分配给某进程后，便让他一直运行下去，直到进程完成或发生某事件而阻塞时，才把处理机分配给另一进程。但存在明显的缺点：如当一个紧急任务到达时，不能立即投入运行，实时性差。,进程调度有两种基本方式

12、：,不可抢占方式与可抢占方式,30,可抢占方式：在这种方式下，某个进程正在运行时可以被系统以某种原则抢占已分配给它的处理机，将处理机分配给其他进程。抢占原则可以是优先权原则，即高优先级进程可以剥夺低优先级的进程运行，也可以是时间片原则，在运行进程的时间片用完后被剥夺处理机，重新参与调度。,31,基本的处理机调度算法有先来先服务法、优先级法和时间片轮转法等，现在也有些操作系统使用综合性的调度算法，比如多级反馈队列调度算法等。,32,1先来先服务调度算法（First Come First Served，FCFS）,该算法按照进程进入就绪队列的先后顺序选择最先进入该队列的进程，把处理机分配给它，使之

13、投入运行。一旦一个进程占有了处理机就一直运行下去，直到该进程完成或因等待某事件而不能继续运行才释放处理机。,D,C,B,A,CPU,完成,33,在单道环境下，某批处理有四道作业，已知他们的进入系统的时刻、估计运算时间如下：,进程,到达时刻,执行时间,开始时刻,完成时刻,周转时间,带权周转,A,B,C,D,0,1,2,3,1,100,1,100,0,1,101,102,1,101,102,202,1,100,100,199,1,1,100,1.99,短作业C的带权周转时间高达100。 长作业D的带权周转时间仅为1.99,34,这是一种不可抢占方式的调度算法，优点是实现简单，缺点是后来的进程等待C

14、PU的时间较长。即有利于长进程，不利于短进程。 在当今系统中，先进先出很少作为调度模式，而是常常嵌套在其它的调度模式中。 例如，许多调度模式根据优先级将处理机分配给进程，但具有相同优先级的进程却按先进先出进行分配。,35,2.最短进程优先法（Shortest Process/Job First，SPF/SJF）,SPF/SJF:从就绪队列中选择估计运行时间最短的进程，先将处理机分配给它，使它立即执行。 非抢占式。 优点：减少了在就绪队列中等待的进程数，同时也降低了进程的平均等待时间，提高了系统的吞吐量。 缺点：没有考虑到某些进程的紧迫程度。 用户作出的估计时间并不准确，带有很大的主观性。,36

15、,例：,假设有5道作业，它们的提交时间及运行时间由下表给出：作业 提交时间（时） 运行时间（小时）1 9 2 2 925 13 1005 0754 1225 055 125 025若采用FCFS和SJF两种调度算法，指出作业被调度顺序及平均周转时间。,37,3.最高响应比优先算法（ Highest Response Ratio Next， HRN）,是对FCFS方式和SJF方式的一种综合平衡响应比。 FCFS只考虑了每个作业的等待时间而未考虑执行时间的长短，而SJF只考虑执行时间而未考虑等待时间的长短。 HRN算法同时考虑每个作业的等待时间长短和估计需要的执行时间长短，从中选出响应比最高的作业

16、投入执行。,38,3.最高响应比优先算法,响应比： R(作业等待时间需运行时间)/ 需运行时间 1已等待时间 / 需运行时间 1W/T 由于R与要求运行时间成反比，故对短作业是有利的，另一方面，因R与等待时间成正比，故长作业随着其等待时间的增长，也可获的较高的响应比。这就克服了短作业优先数法的缺点，既照顾了先来者，又优待了短作业，是上述两种算法的一种较好的折中。,39,4优先级调度算法（Priority Driven，PD）,总是选择具有最高优先级的进程首先使用处理机。在这种算法中，首先考虑的问题是如何确定进程的优先数。 分为： 静态优先级：在创建进程的时候便确定的，且在进程的运行期间保持不变

17、。（简单易行，系统开销小，但不够精确，很可能出现优先权低的进程长期不被调度的情况。所以只在要求不太高的系统中，才使用静态优先级） 动态优先级：在创建进程时所赋予的优先级，可以随进程的推进而改变，以便获得更好的调度性能,40,这是一种可抢占方式的调度算法，可防止一个长进程长期的垄断处理机。,若所有的进程具有相同的优先级初值，则按照FCFS算法，最先进入就绪队列的进程最先获得处理机。若所有的就绪进程具有各不相同的优先级初值，对于优先级初值低的进程，在等待足够的时间后，其优先级可能升为最高，从而获得处理机执行。,41,进程的静态优先级确定原则可以是：,(1) 系统根据进程要求资源情况确定优先级。例如

18、根据估计所需处理机时间、内存量大小、IO设备类型及数量等，确定进程的优先级。 (2) 按进程的类型给予不同的优先级。例如，在有些系统中，进程被划分为系统进程和用户进程。系统进程享有比用户进程高的优先级。,42,进程的动态优先级一般根据以下原则确定：,(1) 根据进程占有CPU时间的长短来决定。一个进程占有处理机的时间愈长，则在被阻塞之后再次获得调度的优先级就越低，反之，其获得调度的可能性就会越大。 (2) 根据就绪进程等待CPU的时间长短来决定。一个就绪进程在就绪队列中等待的时间越长，则它获得调度选中的优先级就越高。 由于动态优先级随时间的推移而变化，系统要经常计算各进程的优先级，因此，系统要

19、为此付出一定的开销。,43,例： 有5个进程P1、P2、P3、P4、P5，它们同时依次进入就绪队列，它们的优先数和需要的处理机时间如下：,进程 处理机时间 优先数 P1 10 3 P2 1 1 P3 2 3 P4 1 4 P5 5 2,44,忽略进程调度所花的时间，要求：,（1）分别写出采用先来先服务调度算法和静态优先级调度算法中进程的执行次序； （2）分别计算各进程在就绪队列中的等待时间和平均等待时间。 解：（1）采用先来先服务调度算法时各进程的执行次序为：P1P2P3P4P5。 采用静态优先级调度算法时各进程的执行次序为： P4P1P3P5P2。,45,（2）FCFS中，平均等待时间（0+

20、10+11+13+14）/59.6；静态优先级法中，平均等待时间（1+18+11+0+13）/58.6,进程 处理机时间 FCFS等待时间 静态优先级法等待时间 P1 10 0 1 P2 1 10 18 P3 2 11 11 P4 1 13 0 P5 5 14 13,46,5时间片轮转调度算法Round-Robin (RR),基本思想：系统把所有的就绪进程按FCFS原则排成一个队列，且规定一个时间片作为进程每次使用处理机的最长时间单位，按时间片把处理机轮流分配给当前位于就绪队列队首的进程使用，当该进程的时间片用完以后，系统产生时钟中断，剥夺该进程的执行，将它送到就绪队列队尾，等待下一轮次的调度

21、。同时处理机调度程序又去调度当前就绪队列的队首进程，也让它运行给定的时间片，如此循环往复。,47,F,C,B,A,.,CPU,完成,A,B C,时间片轮转算法图示,这就使得就绪队列中所有的进程，都能在一有限的时间内，轮流获得一个时间片的执行时间。 该算法适合分时系统使用。,48,时间片选择,在轮转法中，时间片长度的选取非常重要。首先，时间片长度的选择会直接影响系统开销和响应时间。如果时间片长度过短，则调度程序剥夺处理机的次数增多。这将使进程上下文切换次数也大大增加，从而加重系统开销。反过来，如果时间片长度选择过长，比方说一个时间片能保证就绪队列中所需执行时间最长的进程能执行完毕，则轮转法变成了

22、先来先服务法。,49,最佳时间片的确定,这个最佳的时间片值是多少呢？显然，它将随系统而异。随负载而异，同时也随进程而异。 时间片的选取是实现各种调度算法的关键之处，而时间片的选定通常应考虑终端数目，处理机能力、各终端任务的急迫程度、外存传输速度等方面的因素。,50,例： 有5个进程P1、P2、P3、P4、P5，它们同时依次进入就绪队列，请写出使用轮转法调度时的调度次序，各进程的周转时间和等待时间，其中时间片为2：,进程 处理机时间 P1 10 P2 1 P3 2 P4 1 P5 5,51,RR算法,每个进程被分配一个时间段，称作它的时间片，即该进程允许运行的时间。如果在时间片结束时进程还在运行

23、，则CPU将被剥夺并分配给另一个进程。如果进程在时间片结束前阻塞或结束，则CPU当即进行切换。,52,6多级反馈队列调度算法,以上介绍的算法，都存在一定的局限性。 现在主流的操作系统，如UNIX、Windows NT、Linux等，都使用一种综合性的调度算法多级反馈队列调度算法。该算法综合了上述算法以及多队列调度算法的思想和优点，总体调度性能优越，但其实现也比较复杂。,53,算法的基本思想（实施过程）是：,首先：系统按进程优先级设置了多级（比如n级，n2）就绪进程队列，从第一级队列到最后一级队列，优先级越来越低。 其次：每一级就绪队列对应一个不同的时间片。优先级越高的队列，进程的时间片越小。

24、再次：当一个新进程进入内存后，首先被放到第一级队列的队尾。按照FCFS原则排队等待调度。当轮到该进程执行时，如能在时间片内完成，便可准备撤离系统；如果在时间片内未完成，调度程序便将该进程转入第二队列的末尾，再依次按照FCFS原则等待调度。,54,最后：仅当第一级队列为空时，才调度第二级队列中的进程；如此下去，仅当前面的n-1级队列全部为空时，才去调度最后第n级队列中的进程。 如果处理机正在第I队列中为某进程服务时，又有新的进程进入优先级高的队列（第1I-1中任何一队列），则系统抢占正在运行的进程的处理机，由调度程序把正在运行的进程放回到刚才所在第I队列的队尾，重新进行处理机调度。,55,实时系

25、统调度方法 一、实时系统的特点： 实时系统与其他系统的最大区别在于，其处理和控制的正确性不仅仅取决于计算的逻辑结果，而且取决于计算和处理结果产生的时间。 实时系统中处理的外部事件可分为硬实时任务和软实时任务。硬实时任务要求系统必须完全满足任务的时限要求。软实时任务则允许系统对任务的时限要求有一定的延迟，其时限要求只是一个相对条件。,56,一般来说，实时操作系统具有以下特点： (1) 有限等待时间 (2) 有限响应时间 (3) 可靠性高 (4) 系统出错处理能力强,57,上述特性要求实时操作系统具有下述能力： (1) 很快的进程切换速度 (2) 快速的外部中断响应能力 (3) 基于优先级的抢先式

26、调度策略,58,二、实时调度算法的分类 (1) 静态表格驱动Time Driven(TD算法) (2) 频率单调调度算法Rate Monotonic（RM算法） (3) 最早时间限优先调度算法Early Deadline First （EDF算法）,59,三、最早时间限优先调度算法与频率单调调度算法 最早时间限优先调度算法是一种以满足用户要求的时限为调度原则的算法。 (1) 任务就绪时间或事件到达时间 (2) 开始时限 (3) 完成时限 (4) 处理时间 (5) 资源需求 (6) 优先级,60,最早时间限优先调度算法的基本思想是：按用户的时限要求顺序设置优先级，优先级高者占据处理机，也就是说，时限要求最近的任务优先占有处理机。 例子：设实时系统从两个不同的数据源DA和DB周期性地收集数据并进行处理，其中DA的时限要求以30 ms为周期，DB的时限要求以75 ms为周期。设DA所需处理时限为15 ms，DB所需处理时限为38 ms。,61,图4.11 周期性任务的预计发生、执行与结束时限,62,如果使用最早时间限优先调度算法，并按最近结束时限优先级最高的方法进行排列，可以给出图所示各进程的调度顺序和相对时间。,63,在开始时，进程DA（1）和DB（1）的结束时限比较结果，DA