《操作系统》3处理机管理课件

1、第3章 处理机管理,本章目录,3.1 处理机调度概述,3.1.1 处理机调度的三个层次,3.1.2 进程调度的功能、时机和基本策略,3.2 作业调度算法,3.2.1 先来先服务调度算法,3.2.2 短作业优先调度算法,3.5.3 Linux的进程调度算法,3.2.3 最短剩余时间优先调度算法,3.1.3 调度算法的性能评价指标,3.4 实时处理与实时调度算法,3.4.1 实时处理的特征,3.4.2 最早截止时间优先调度算法,3.4.3 速率单调调度算法,3.5 Linux的处理机调度,3.5.1 涉及调度的进程分类,3.5.2 Linux的可运行队列,3.2.4 最高响应比调度算法,3.3 进

2、程调度算法,3.3.1 先来先服务调度算法,3.3.2 轮转调度算法,3.3.3 优先级调度算法,3.3.4 多级队列调度算法,3.3.5 多级反馈队列调度算法,3.1 处理机调度概述,3.1.1 处理机调度的三个层次,高级调度,1.,当系统决定接纳一个作业时，就要为它开辟一个作业控制块（ JCB），以便随时记录作业的信息。,.,.,被系统接纳的作业，在没有投入运行前是以“后备作业”的形式存放在辅存里。所有后备作业的JCB链接在一起，形成“后备作业队列”。这些作业没有资格参与对处理机的竞争，但系统从它们的里面去挑选参与CPU竞争的作业。,.,高级调度决定哪个后备作业可进入系统去接受处理，它控制

3、着多道程序设计环境的“度”：进到系统的作业多，资源的利用率提高了，但每个作业获得处理结果的时间可能会长；进到系统的作业少，每个作业很快就得到自己的处理结果，但资源的利用率可能会下降。,低级调度,2.,.,低级调度真正决定CPU下一次执行哪一个进程，它将按照一定的算法，从就绪队列里挑选出可运行的进程投入运行。低级调度的各种算法，是我们讨论的主要目标。低级调度也被称为“进程调度” 。,中级调度,3.,.,中级调度是介于高级调度和低级调度之间的一种调度，如果系统为进程设置有“挂起”状态，那么就会涉及到中级调度。也就是说，中级调度与实施进程的内、外存交换有关。,CPU,就绪队列,低级调度,释放,中级调

4、度,就绪/挂起队列,时间片到,高级调度,阻塞/挂起队列,阻塞队列,中级调度,事件等待,事 件 发 生,交互用户,作业,后备作业队列,.,系统中出现过高并发度时，就应将内存中的某些进程暂时换出 到外存；系统的并发 度较低时，就应该将 外存中的某些进程换 入到内存。进程在内、外存 间的换出和换入，就是中级调度承担的责任，通过这种交换，以求达到调节和平衡系统“并发度”的目的。,.,高级调度执行的频繁程度很低，它 只是粗略地决定是否接受一个新进程以 及接受哪一个；中级调度为了实施交换 决策，执行的频率相对要频繁一些；低 级调度要精确地决定执行哪一个进程，因此执行的频度为最高。,返回目录,3.1.2 进

5、程调度的功能、时机和基本策略,1.,进程调度程序的功能,.,保护现场,.,挑选运行对象,.,恢复现场,2.,发生进程调度的时机,当某进程正常完成自己的运行或被终止时，为不让CPU空闲，必须实行调度，以便从就绪队列里挑选新的进程投入运行。,.,.,分时系统中，时钟中断处理程序发现分配给某个进程的时间片用完时，就强制它交出CPU，重新进行CPU调度。,.,运行中的进程提出I/O请求，或要等待别的进程发来消息，于是自己被阻塞。,.,执行操作系统提供的某些系统调用命令，如wait()等。,.,某进程的状态从阻塞变为就绪时，要由调度程序决定让哪一个进程投入运行：是新就绪进程、是正在运行的进程继续运行、还

6、是调度另一个进程运行。,3.,进程调度的基本策略,非抢占式：在把CPU分配给某个进程后，就一直让它使用下去，直到进程完成自己的工作，或因要等待某事件的发生而交出CPU，否则不允许其他进程夺取CPU。,.,.,抢占式：在调度程序把CPU分配给某进程使用后，只要满足某条件，就允许立即把CPU从运行进程手中夺取过来，分配给满足条件的进程使用。,返回目录,特定作业从提交给系统到获取结果所经历的时间间隔。因此，设作业i向系统提交的时间为Tpi，完成时间是Tci，那么它的周转时间Ti为：Ti = Tci - Tpi 。,3.1.3 调度算法的性能评价指标,1.,2.,吞吐量,周转时间,所谓“吞吐量”，是指

7、单位时间内CPU完成作业的数量。,.,有的作业属于“处理机限制”型的，即需要花费大量的CPU时间，很少输入/输出，也称“CPU繁忙”型；有的属于“I/O限制”型的，即它在运行期间主要是输入/输出，很少进行计算和处理，也称“I/O繁忙”型。,.,.,作业的周转时间,作业的周转时间是指作业的执行时间加上作业的等待时间。设作业i的等待时间为Twi，执行时间为Tsi，那么它的周转时间Ti为：Ti = Twi + Tsi 。,（1）,（2）,.,作业的平均周转时间,n个作业，每个作业的周转时间为Ti，那么它们的平均周转时间为：,T=(Ti ),i=1,n,n,1,利用平均周转时间，可以基于同一批作业，来

8、衡量不同调度算法的调度性能。,.,.,作业的“带权周转时间”，指该作业的周转时间与所需运行时间之比。设作业i周转时间为Ti，所需执行时间为Ri，那么它的带权周转时间Wi为：,.,作业的平均带权周转时间,（3）,n个作业，每个作业的带权周转时间为Wi，那么它们的平均周转时间为：,.,W=( ),Ti,Ri,1,n,利用平均带权周转时间，可基于同一调度算法，对不同批次作业的调度性能做出比较。,.,.,CPU的利用率,3.,所谓“CPU的利用率”，是指在一定的时间区间内，CPU为用户提供服务的时间与其总运行时间的比率。,作业i的CPU利用率Ui，是指该作业的执行时间Ci与周转时间Ti的比率。即：,.

9、,Wi=Ti/Ri,Ui=Ci/Ti,.,如果系统内有n个作业，那么整个系统CPU的平均利用率应为：,U=(Ci/Ti ),i=1,n,n,1,公平性：调度的设计，应该顾及到所有作业或进程对CPU的不同需求，尽量做到公平合理，不偏不倚。,设计目标：设计目标是决定算法的主要因素，目标不同，要求肯定不一样。比如批处理系统的调度，应尽量提高各种资源的利用率，以及整个系统的吞吐量；分时系统的调度，应将对用户提出的请求作出回应的速度，控制在用户能够容忍的范围内；实时系统的调度，应保证对所发生的的事件做出及时的响应和处理；如此等等。,响应比,4.,.,所谓作业的“响应比”，是指一个特定作业的周转时间与它所

10、需的执行时间之比。,.,作业i的等待时间为Twi，执行时间为Tsi，那么该作业的响应比RRi是： RRi = ( Twi + Tsi ) / Tsi,影响调度算法设计的因素,.,（1）,（2）,（3）,均衡性：调度算法应考虑资源使用的均衡性，使系统中的各种资源都能得到充分地利用。比如，把“处理机限制”和“I/O限制”作业搭配，就有可能收到良好的效果。,（4）,兼顾性：调度算法应既考虑长作业的要求，也考虑短作业的要求；既考虑高优先级进程的要求，也要顾及低优先级进程的利益。只偏袒某一方，所造成的后果有可能是严重的，甚至是无法弥补的。,返回目录,右示三个作业，按1、2、3的顺序提交给系统，采用FCF

11、S调度算法。画出它们的“甘特图”，计算每个作业的周转时间及平均周转时间。（忽略系统调度所需额外的时间开销）,作业1第1个被作业调度程序选中运行，花费24个 CPU时间运行完毕，故周转时间是：T1=24-0=24；作业2等待24个CPU时间后被调度运行，花费3个CPU时间运行完毕，故周转时间是：T2=27-0=27；作业3的周转时间是：T3=30-0=30。这三个作业的平均周转时间为(24+27+30)/3=27。,3.2.1 先来先服务调度算法,3.2 作业调度算法,先来先服务（FCFS）作业调度算法，基于作业到达后备队列的先后次序以及作业对系统资源的需求，从中挑选进入内存、成为参与CPU竞争

12、的作业对象。有时也称为先进先出（FIFO）作业调度算法。,.,例3-1 ：,作业,所需CPU时间,1 2 3,24 3 3,解：,作业1,作业2,作业3,24,3,3,.,所谓“甘特图”，即是指能够反映作业调度顺序及占用CPU时间的一种进度图。,右示五个作业，采用FCFS 作业和进程调度算法，可供5个作业 使用的内存空间为100KB，需要时按 序分配。作业进入内存后，不许在内 存中移动。计算每个作业的周转时间和平均周转时间。（忽略系统调度时间，作业都没有输入/输出请求）,例3-2 ：,作业,所需CPU时间,1 2 3 4 5,10.1 10.3 10.5 10.6 10.7,到达时间,所需内存

13、量,0.7 0.5 0.4 0.4 0.2,15KB 70KB 50KB 20KB 10KB,解：,.,各作业的周转时间,装入内存时间,完成时间,10.1 10.3 11.3 11.3 10.7,开始运行时间,周转时间,10.8 11.3 11.9 12.3 11.5,0.7 1.0 1.4 1.7 0.8,10.1 10.8 11.5 11.9 10.3,.,作业运行时的内存分配情况,作业1(15KB),作业2(70KB),作业5(10KB),空闲(5KB),到10.7时 内存情形,空闲(15KB),作业2(70KB),作业5(10KB),空闲(5KB),到10.8作业1 完成时内存情形,作

14、业3(50KB),作业4(20KB),作业5(10KB),空闲(5KB),(c) 到11.3作业2 完成时内存情形,空闲(15KB),这批作业的调度顺序是： 12534， 系统的平均作业周转时间为： (0.7+1.0+1.4+1.7+0.8) / 5 = 1.12,.,返回目录,各自的开始运行时间、完成时间、周转时间以及带权周转时间如下所示。,五个作业的调度顺序是ABECD。,有5个作业AE，情况如表所示，按照SJF进行作业调度。计算它们各自的开始运行时间、完成时间、周转时间以及带权周转时间。,短作业优先（SJF）调度算法，总是在作业后备队列里选择要求运行时间最短的、满足其资源需要的作业进入内

15、存，参与对CPU的竞争。,3.2.2 短作业优先调度算法,.,.,.,例3-4 ：,作业,所需CPU时间,A B C D E,0 2 4 6 8,到达时间,3 6 4 5 2,解：,作业调度的gantt图 ：,作业A,作业B,作业C,作业E,作业D,3,6,4,2,5,.,开始运行时间,带权周转时间,0 3 11 15 9,完成时间,周转时间,3 7 11 14 3,1 1.17 2.75 2.80 1.50,3 9 15 20 11,返回目录,3.2.3 最短剩余时间优先调度算法,.,最短剩余时间优先（SRTF）作业调度算法，是在调度时从后备作业队列里挑选所需运行时间最短的作业投入运行。运行

16、过程中，若有运行时间更短的作业达到，那么它就抢占CPU，让当前正在运行的作业暂停执行。,例3-5 ：,有5个作业AE，情况如表所示，按照SRTF进行作业调度。计算它们的开始运行时间、完成时间、周转时间以及带权周转时间。,作业,所需CPU时间,A B C D E,0 2 4 6 8,到达时间,3 6 4 5 2,解：,.,各自的开始运行时间、完成时间、周转时间以及带权周转时间如下所示。,五个作业的调度顺序是：ABCEBD 。,.,作业调度的gantt图 ：,.,开始运行时间,带权周转时间,0 3 4 15 8,完成时间,周转时间,3 13 4 14 2,1 2.17 1.0 2.80 1.0,3

17、 15 8 20 10,A,B,C,E,B,D,0,3,4,8,10,15,20,时间,E到达,D到达,C到达,B到达,A到达,6,2,返回目录,各自的开始运行时间、完成时间、周转时间以及带权周转时间如下所示。,有5个作业AE，情况如表所示，按照HRRN进行作业调度。计算它们的开始运行时间、完成时间、周转时间以及带权周转时间。,最高响应比（HRRN）调度算法，是在进行新一次调度时，计算后备作业队列里所有作业当前的响应比RR，挑选出响应比最高者参与对CPU的竞争。,3.2.4 最高响应比调度算法,.,例3-6 ：,作业,所需CPU时间,A B C D E,0 2 4 6 8,到达时间,3 6 4

18、 5 2,解：,.,开始运行时间,带权周转时间,0 3 9 15 13,完成时间,周转时间,3 7 9 14 7,1 1.17 2.25 2.80 3.5,3 9 13 20 15,作业调度的gantt图 ：,.,作业A,作业B,作业C,作业E,作业D,3,6,4,2,5,.,时刻9作业B完成后，作业C、D、E都到 达系统。计算它们三个的响应比，即： RRC = (9-4) + 4)/4=2.25 RRD = (9-6) + 5)/5=1.6 RRE = (9-8) + 2)/2=1.5 比较后知，这时作业C的响应比最高，所以应调度它运行。五个作业调度顺序是：ABCED。,返回目录,3.3 进

19、程调度算法,3.3.1 先来先服务调度算法,进程的先来先服务调度算法作用在就绪队列上。进程就绪时，将PCB插入到就绪队列尾部；调度时，总是把CPU分配给就绪队列之首的进程使用。它一直占用CPU，除非运行结束自愿释放，或因等待某事件的发生交出CPU。这是一种非抢占式的调度算法。,.,3.3.2 轮转调度算法,系统时钟周期性地产生中断。中断发生时，迫使当前正在运行的进程中止运行，到就绪队列里排队，调度程序按FCFS从就绪队列里选择就绪进程投入运行。因此每个运行进程在被抢占前，最多运行一个规定的时间长度，这个时间长度被称为“时间片”。,.,分配给进程A 的一个时间片q,分配给进程B 的一个时间片q,

20、分配给进程A 的另一个时间片q,时钟中断,时钟中断,时钟中断,用户A一次 交互结束,.,RR调度算法的关键是时间片设置的大小。若时间片q设置得小，那么长作业可能需要经若干个时间片才能完成一次交互活动，从而增加了系统在进程间切换时的开销；若时间片q设置得长，长到每个交互只需要一个时间片就能够完成时， 那么RR就成FCFS了。 所以，时间片的尺寸最 好是略大于一次典型交 互活动所需的时间。,q=4 时，五 个进程的调度顺 序是：ABCDB ED,q=1 时，五 个进程的调度顺序是： AAABB CBDC BEDC BEDC BDD,五个作业AE的情况如右所示，对进程实施两次RR调度算法，时间片分别

21、为1个CPU时间单位和4个CPU时间单位。求各进程的开始运行时间、完成时间、周转时间、带权周转时间、平均周转时间以及带权平均周转时间。,.,RR进程调度是个多路开关，通过它把一个CPU分配给多个进程使用，产生出有多个逻辑CPU的空幻印象，只是每个逻辑CPU的运行速度要比真正的物理CPU来得慢罢了。,0,20,5,10,15,A,B,C,D,E,轮转q=1 (RR),A,B,C,D,E,轮转q=4 (RR),0,20,5,10,15,进程B 到达,进程A到达,进程C 到达,进程D 到达,进程E 到达,例3-7 ：,作业,所需CPU时间,A B C D E,0 2 4 6 8,到达时间,3 6 4

22、 5 2,.,.,解：,返回目录,就绪队列里有如右所示五个进程P1P5 ，实施HPF调度算法，试计算平均等待时间。,3.3.3 优先级调度算法,.,优先级调度（HPF）算法，是基于进程优先级进行的调度算法。在需要调度时，HPF算法总是从就绪队列里挑选优先级最高者投入运行。,进程的PCB里，都会记录进程的优先级。优先级常用数字表示，比如07，或04095。不过，数字0到底表示最高还是最低，各个操作系统不尽相同。有的系统以数字越小表示优先级越高，有的则以数字越大表示优先级越高。本书规定数字越小优先级越高。,.,例3-8 ：,进程,所需CPU时间,P1 P2 P3 P4 P5,10 1 2 1 5,

23、优先级,3 1 4 5 2,它们的调度顺序是：P2P5P1P3P4 。,.,解：,.,相应的gantt图如下所示。,P2,P5,P1,P3,P4,0,1,6,16,18,19,抢占式优先级调度算法：一个新进程抵达就绪队列时，若优先级高于当前运行进程，那就让当前进程暂停运行进入就绪队列，把CPU分配给新进程使用，实现抢占。,.,非抢占式优先级调度算法：就绪队列基于进程优先级进行排队，优先级高的排在前面，优先级低的排在后面。调度时，总是把就绪队列的首进程作为分配CPU的对象。,.,.,确定进程优先级的因素,根据进程的类型。比如由于系统进程完成的任务是提供系统服务，分配系统资源，因此给予系统进程较高

24、的优先级，不仅合乎情理，而且也能够提高系统的工作效率。,(1),(2),根据进程执行任务的重要性。每个进程所完成的任务，其重要性和紧迫性肯定是不一样的。比如，赋予报警进程高的优先级，一旦紧急事件发生时，让它立即抢占CPU投入运行，这是理所当然的事情。,(3),根据进程程序的性质。一个“处理机限制”进程，由于需占用较长的运行时间，影响系统整体效率的发挥，因此只能给予较低的优先级；一个“I/O限制”进程，给予它较高的优先级后，就能充分发挥CPU和外部设备之间的并行工作能力。,(4),根据对资源的要求。系统资源有处理机、内存储器、外部设备等。可按照一个进程所需资源的类型和数量，确定它的优先级。比如给

25、予占用CPU时间短或内存容量少的进程以较高的优先级，这样可以提高系统的吞吐量。,(5),根据用户的请求。系统可以根据用户的请求，给予它的作业及其相应进程很高的优先级，作“加急”处理。,.,进程优先级的分类：所谓“静态”优先级，即指在进程的整个生命期内优先数保持不变；所谓“动态”优先级，是指在进程的整个生命期内可随时修正它的优先级别，以适应系统环境和条件的变化。,返回目录,3.3.4 多级队列调度算法,.,多级队列（MQ）调度算法，是把就绪进程按不同的性质组合成若干个就绪队列，每个队列实行不同的进程调度算法。,系统进程就绪队列,实时进程就绪队列,交互进程就绪队列,批处理进程就绪队列,优先级,高,

26、低,.,可按进程的类型组建各种就绪队列：系统进程就绪队列、实时进程就绪队列、交互进程就绪队列、批处理进程就绪队列等。每个队列都执行自己的调度算法。,.,两个队列间获得CPU的权利要有先后次序。比如，根据每个队列的优先级不同，越往上的队列，获得CPU的优先级越高；越往下的队列，获得CPU的优先级越低。这样，只有在系统进程就绪队列和实时进程就绪队列为空的前提下，才能够去调度交互进程就绪队列里的进程；当一个批处理进程执行时，若有一个交互进程抵达了就绪队列，那么批处理进程就将被抢占，把CPU让给交互进程使用。,返回目录,系统从第1个队列开始调度；只有在前i-1个队列都空时，才调度第i个队列里的进程。当

27、更高级别的队列到达进程时，系统将立即转去运行级别高的那个进程。,系统设多个就绪队列，有自己的优先级，第1个队列的优先级最高，越往下队列的优先级依次降低。,多级反馈队列（MFQ）调度算法，是在多级队列调度算法基础上加入队列间的反馈措施构成的，它允许进程在不同的就绪队列里移动。“反馈”，是依据进程使用CPU的时间长短进行的。,.,3.3.5 多级反馈队列调度算法,CPU,调度,阻塞，就绪,时间片到,CPU,调度,阻塞，就绪,完成,完成,时间片到,CPU,调度,阻塞，就绪,时间片到,完成,到达,级1 (先来先服务),级2 (先来先服务),级n (轮转或先来先服务),.,多级反馈队列的做法,(1),(

28、2),为就绪队列分配不同时间片，在优先级高的队列里的进程，获得的CPU服务时间短；在优先级低的队列里的进程，获得的CPU服务时间长。,(3),n个队列都实施FCFS调度算 法，最后一个队列也可实施RR调度 算法。新进程抵达时，先进入第1个 就绪队列。进程在某个队列里获得时间片后，若用完时间片前被阻塞，仍回原队列末尾排队；若耗尽时间片后仍未做完工作，则将其移入低一级就绪队列排队，直至队列n。,(4),返回目录,所谓“任务速率”，是该任务周期T（单位为秒）的倒数。比如，如果一个任务的周期是50ms，那么它的速率是20次/秒。一个任务的“执行时间”C，是指该任务所需要的CPU时间总量。在单处理器系统

29、中，任务的执行时间C必须小于它的周期T。一个任务如果在执行期间没被打断，那么它的CPU利用率应该是U=C/T。比如说，一个任务的周期是80ms，执行时间是55ms，那么它的CPU利用率为55/80=0.6875。,3.4 实时处理与实时调度算法,3.4.1 实时处理的特征,1.,实时处理的特征,“时限性”：每个实时任务都有一个期限，指明任务的开始时间或结束时间，也就是最晚何时须开始（最早截止时间），或最晚何时候须完成（最晚截止时间）。根据时限要求，可分为“硬实时任务”和 “软实时任务”两类。,(1),(2),“周期性”： “周期性任务”是指一个任务过一定的时间间隔T就做一次（称一个“实例”）。

30、也就是说，每隔T个CPU单位时间做一次。所谓“非周期性任务”，是指那些只有开始或结束的时限约束的任务。,任务P,任务P的一个周期,任务P,任务P的一个周期,任务P,空闲,空闲,时间,一个实例,一个实例,(3),2.,实时进程的几种处理方式,.,时间片轮转的抢占式调度：出现对实时进程的请求时，该进程被添加到就绪队列等待它时间片的到来。这种调度对于实时进程来说，通常是难以接受的。,当前进程,进程1,进程n,实时进程,来自实时 进程的请求,实时进程被添加到就绪队列 中，等待它的下一个时间片,调度时间,进程2,就绪队列,.,优先级非抢占式调度：出现对实时进程的请求时，赋予它最高的优先级。这样，只要当前

31、进程阻塞或完成，实时进程就可获得CPU。,当前进程,来自实时 进程的请求,进程1,实时进程,实时进程被添加 到就绪队列首,调度时间,就绪队列,当前进程阻塞或完成,.,基于优先级和时钟中断相结合的调度算法：通过时钟按照规则产生抢占点。在到达一个抢占点时，如果有更高优先级的进程在等待，那么就进行对CPU的抢占。,当前进程,来自实时 进程的请求,进程1,实时进程,等待下一 个抢占点,调度时间,下一个抢占点,就绪队列,当前进程,来自实时 进程的请求,进程1,实时进程,实时进程抢占 当前进程立即运行,.,立即抢占调度算法：操作系统几乎是立即响应来自对实时进程的请求，以使调度的延迟时间降到最小。,返回目录

32、,有三个都已就绪的实时任务A、B、C，利用最早截止时间优先（EDF）调度算法对它们实施调度。,3.4.2 最早截止时间优先调度算法,.,最早截止时间优先（EDF）算法，是通过任务最早截止时间所确定的优先级来进行调度，截止时间越早，其优先级就越高。,.,调度具体做法 ：记录每个任务每一次的最早截止时间；到达某任务的最早截止时间时，就产生该任务的一个实例，并进入就绪队列；有新任务进入就绪队列时，按照各任务当时的最早截止时间进行优先调度。,0,20,40,60,80,100,120,140,A1,B1,C1,A2,A3,A4,A5,B2,B3,B4,C2,C3,A1截 止时间,B1截 止时间,C1截

33、 止时间,A2截 止时间,B2截 止时间,A3截 止时间,C2截 止时间,A4、B3 截止时间,A1,B1,C1,A2,B2,C2,A3,A4,C3,A5,B4,时间(ms),时间(ms),A1、B1、C1 开始时间,10,30,50,70,90,110,130,基本信息,最早截止时间 优先(EDF),B3,例3-11 ：,实时任务,所需执行时间,A B C,10ms 15ms 5ms,周期,30ms 40ms 50ms,解：,返回目录,3.4.3 速率单调调度算法,.,速率单调调度（RMS）算法，基于任务的周期确定出任务的优先级，然后根据优先级进行调度。周期越短，优先级越高。,.,调度具体做

34、法 ：将任务的周期转化成它的速率，成为该任务的静态优先级；到达某个任务的最早截止时间时，产生该任务的一个实例，并进入就绪队列；有新任务进入就绪队列时，按照各个任务的优先级实施调度。,有三个都已就绪的实时任务A、B、C，利用速率单调调度（RMS）算法对它们实施调度。,例3-12 ：,解：,实时任务,所需执行时间,A B C,10ms 15ms 5ms,周期,30ms 40ms 50ms,0,20,40,60,80,100,120,140,A1,B1,C1,A2,A3,A4,A5,B2,B3,B4,C2,C3,A1截 止时间,B1截 止时间,C1截 止时间,A2截 止时间,B2截 止时间,A3截

35、止时间,C2截 止时间,A4、B3 截止时间,A1,B1,C1,A2,B2,C2,A3,A4,C3,A5,B4,时间(ms),时间(ms),A1、B1、C1 开始时间,10,30,50,70,90,110,130,基本信息,速率单调 调度(RMS),B3,B3,返回目录,实时进程：那些需要极快得到响应、有很强调度要求的进程为实时进程。这些进程如果得不到很快的响应，就可能会产生不可预料的后果。,3.5 Linux的处理机调度,3.5.1 涉及调度的进程分类,1.,根据性质分类,交互式进程：那些经常要与用户进行交互会话的进程为交互式进程。特点是要花费很多时间等待用户在键盘和鼠标上进行的操作；接收到

36、用户的输入后，应在50150ms之间唤醒进程，并对用户做出回应，否则就超出了用户的忍耐度。,.,.,批处理进程：那些无需与用户进行交互、经常被安排在后台运行的进程为批处理进程 。,.,2.,根据使用CPU的情况分类,.,活动进程：上次没有使用完自己的时间片的那些进程被视为活动进程。既然上次没有使用完一个时间片，表明该进程是I/O繁忙的，因此应该尽快让它投入运行。,.,过期进程：上次使用完了属于自己的时间片的那些进程被视为过期进程。既然上次使用完了时间片，表明该进程是CPU繁忙的。为能够获得更长的CPU服务时间，它就必须投入更长时间的等待，等到所有活动进程都过期时才得以运行。,返回目录,poli

37、cy：指明对进程实行的调度类型，如SCHED_FIFO（先进先出的实时进程调度）； SCHED_RR（时间片轮转的实时进程调度）； SCHED_NORMAL（普通的分时进程调度）。,time_slice：记录进程时间片中还剩余的时钟节拍数。,3.5.2 Linux的可运行队列,1.,PCB中与调度程序相关的字段,state：记录每个进程的当前状态 。,static_prio：静态优先级，取值范围100（最高优先级）139（最低优先级）。新进程创建时，总是继承父进程的静态优先级。用户可以通过系统调用，改变自己的静态优先级。,(1),(2),prio ：动态优先级，取值范围100（最高优先级）13

38、9（最低优先级）。系统将根据进程的静态优先级、睡眠（等待）时间，计算出它的动态优先级。,(3),(4),next_run：指向进程所属运行队列链表中的下一个进程。,(5),prev_run：指向进程所属运行队列链表中的前一个进程。,(6),array：指向进程所在运行队列的prio_array_t结构。,(7),sleep_avg：进程的平均睡眠时间。,(8),(9),(10),rt_priority：记录进程的实时优先级 ，每个实时进程都与一个范围从1（最高优先级）99（最低优先级）的实时优先级数值相关。,2.,数据结构prio_array_t,为提高调度效率， Linux为活动和过期进程

39、各维护一个可运行进程 链表，每个链表按进程的优先级（0139），开设140个可运行队列。可运行进程的PCB，通过PCB里的next_run和prev_run两个字段链接在这样的队列里，成为140个双向队列。,.,.,通过prio_array_t型数据结构，形成两个可运行链表、每个里面有140个可运行队列。,prio_array_t各字段的内容与含义,.,32位/字,5个字,bitmap位图,1,1,1,0,1,2,139,127,优先级0,优先级2,优先级127,PCB,PCB,PCB,PCB,PCB,PCB,(1),nr_active：链表中PCB的个数；,(2),bitmap：由字长32位

40、的、5个字 组成的优先级位图，当且仅当某个优先 级的进程队列不空时，对应的标志位为1；,(3),queue：140个优先级队列的头结点数组。,queue,arrays：有两个元素的数组，一个是活动进程的可运行链表（由active指向），一个是过期进程的可运行 链表（由expired指向）。,3.,数据结构runqueue,runqueue,active,expired,arrays0,arrays1,一个 prio_array_t,一个 prio_array_t,PCB,PCB,PCB,PCB,PCB,PCB,PCB,PCB,PCB,PCB,优先级0,优先级0,优先级139,优先级139,runqueue是调度程序中最重要的数据结构，它维护着活动进程和过期进程的可运行进程链表，随时记录着系统调度时所需的各种信息。,.,.,runqueue里涉及可运行进程的有关字段如下 ：,(1),curr：指向当前正在运行进程的PCB。,(2),active：指向活动进程的可运行链表指针。,(3),expired：指向过