《操作系统》处理机管理.ppt

《《操作系统》处理机管理.ppt》由会员分享，可在线阅读，更多相关《《操作系统》处理机管理.ppt（29页珍藏版）》请在三一办公上搜索。

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()等。,.,某进程的状态从阻塞变为就绪时，要由调度程序决定让哪一个进程投入运行：是新就绪进程、是正在运行的进程继续运行、还是调度另一个进程运行。,3.

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

7、有的作业属于“处理机限制”型的，即需要花费大量的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的比率。即：,.,Wi=Ti/Ri,Ui=Ci/Ti,.,如果系统内

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

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

11、（忽略系统调度所需额外的时间开销）,作业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竞争的作业对象。有时也称为先进先出（FIFO）作业调度算法。,.,例3-1：,

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

13、间,装入内存时间,完成时间,10.110.311.311.310.7,开始运行时间,周转时间,10.811.311.912.311.5,0.71.01.41.70.8,10.110.811.511.910.3,.,作业运行时的内存分配情况,作业1(15KB),作业2(70KB),作业5(10KB),空闲(5KB),到10.7时 内存情形,空闲(15KB),作业2(70KB),作业5(10KB),空闲(5KB),到10.8作业1 完成时内存情形,作业3(50KB),作业4(20KB),作业5(10KB),空闲(5KB),(c)到11.3作业2 完成时内存情形,空闲(15KB),这批作业的调度顺序

14、是：12534，系统的平均作业周转时间为：(0.7+1.0+1.4+1.7+0.8)/5=1.12,.,返回目录,各自的开始运行时间、完成时间、周转时间以及带权周转时间如下所示。,五个作业的调度顺序是ABECD。,有5个作业AE，情况如表所示，按照SJF进行作业调度。计算它们各自的开始运行时间、完成时间、周转时间以及带权周转时间。,短作业优先（SJF）调度算法，总是在作业后备队列里选择要求运行时间最短的、满足其资源需要的作业进入内存，参与对CPU的竞争。,3.2.2 短作业优先调度算法,.,.,.,例3-4：,作业,所需CPU时间,ABCDE,02468,到达时间,36452,解：,作业调度的

15、gantt图：,作业A,作业B,作业C,作业E,作业D,3,6,4,2,5,.,开始运行时间,带权周转时间,0311159,完成时间,周转时间,3711143,11.172.752.801.50,39152011,返回目录,3.2.3 最短剩余时间优先调度算法,.,最短剩余时间优先（SRTF）作业调度算法，是在调度时从后备作业队列里挑选所需运行时间最短的作业投入运行。运行过程中，若有运行时间更短的作业达到，那么它就抢占CPU，让当前正在运行的作业暂停执行。,例3-5：,有5个作业AE，情况如表所示，按照SRTF进行作业调度。计算它们的开始运行时间、完成时间、周转时间以及带权周转时间。,作业,所

16、需CPU时间,ABCDE,02468,到达时间,36452,解：,.,各自的开始运行时间、完成时间、周转时间以及带权周转时间如下所示。,五个作业的调度顺序是：ABCEBD。,.,作业调度的gantt图：,.,开始运行时间,带权周转时间,034158,完成时间,周转时间,3134142,12.171.02.801.0,31582010,A,B,C,E,B,D,0,3,4,8,10,15,20,时间,E到达,D到达,C到达,B到达,A到达,6,2,返回目录,各自的开始运行时间、完成时间、周转时间以及带权周转时间如下所示。,有5个作业AE，情况如表所示，按照HRRN进行作业调度。计算它们的开始运行时

17、间、完成时间、周转时间以及带权周转时间。,最高响应比（HRRN）调度算法，是在进行新一次调度时，计算后备作业队列里所有作业当前的响应比RR，挑选出响应比最高者参与对CPU的竞争。,3.2.4 最高响应比调度算法,.,例3-6：,作业,所需CPU时间,ABCDE,02468,到达时间,36452,解：,.,开始运行时间,带权周转时间,0391513,完成时间,周转时间,379147,11.172.252.803.5,39132015,作业调度的gantt图：,.,作业A,作业B,作业C,作业E,作业D,3,6,4,2,5,.,时刻9作业B完成后，作业C、D、E都到 达系统。计算它们三个的响应比，

18、即：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 进程调度算法,3.3.1 先来先服务调度算法,进程的先来先服务调度算法作用在就绪队列上。进程就绪时，将PCB插入到就绪队列尾部；调度时，总是把CPU分配给就绪队列之首的进程使用。它一直占用CPU，除非运行结束自愿释放，或因等待某事件的发生交出CPU。这是一种非抢占式的调度算法。,.,3.3.2 轮转调度算法,系统时钟周期性地产生中断。中断发生时，迫使当前正在运行的进程中止运

19、行，到就绪队列里排队，调度程序按FCFS从就绪队列里选择就绪进程投入运行。因此每个运行进程在被抢占前，最多运行一个规定的时间长度，这个时间长度被称为“时间片”。,.,分配给进程A的一个时间片q,分配给进程B的一个时间片q,分配给进程A的另一个时间片q,时钟中断,时钟中断,时钟中断,用户A一次交互结束,.,RR调度算法的关键是时间片设置的大小。若时间片q设置得小，那么长作业可能需要经若干个时间片才能完成一次交互活动，从而增加了系统在进程间切换时的开销；若时间片q设置得长，长到每个交互只需要一个时间片就能够完成时，那么RR就成FCFS了。所以，时间片的尺寸最好是略大于一次典型交互活动所需的时间。,

20、q=4 时，五个进程的调度顺序是：ABCDBED,q=1 时，五个进程的调度顺序是：AAABBCBDCBEDCBEDCBDD,五个作业AE的情况如右所示，对进程实施两次RR调度算法，时间片分别为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

21、,20,5,10,15,进程B到达,进程A到达,进程C到达,进程D到达,进程E到达,例3-7：,作业,所需CPU时间,ABCDE,02468,到达时间,36452,.,.,解：,返回目录,就绪队列里有如右所示五个进程P1P5，实施HPF调度算法，试计算平均等待时间。,3.3.3 优先级调度算法,.,优先级调度（HPF）算法，是基于进程优先级进行的调度算法。在需要调度时，HPF算法总是从就绪队列里挑选优先级最高者投入运行。,进程的PCB里，都会记录进程的优先级。优先级常用数字表示，比如07，或04095。不过，数字0到底表示最高还是最低，各个操作系统不尽相同。有的系统以数字越小表示优先级越高，有

22、的则以数字越大表示优先级越高。本书规定数字越小优先级越高。,.,例3-8：,进程,所需CPU时间,P1P2P3P4P5,101215,优先级,31452,它们的调度顺序是：P2P5P1P3P4。,.,解：,.,相应的gantt图如下所示。,P2,P5,P1,P3,P4,0,1,6,16,18,19,抢占式优先级调度算法：一个新进程抵达就绪队列时，若优先级高于当前运行进程，那就让当前进程暂停运行进入就绪队列，把CPU分配给新进程使用，实现抢占。,.,非抢占式优先级调度算法：就绪队列基于进程优先级进行排队，优先级高的排在前面，优先级低的排在后面。调度时，总是把就绪队列的首进程作为分配CPU的对象。

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

24、(4),根据对资源的要求。系统资源有处理机、内存储器、外部设备等。可按照一个进程所需资源的类型和数量，确定它的优先级。比如给予占用CPU时间短或内存容量少的进程以较高的优先级，这样可以提高系统的吞吐量。,(5),根据用户的请求。系统可以根据用户的请求，给予它的作业及其相应进程很高的优先级，作“加急”处理。,.,进程优先级的分类：所谓“静态”优先级，即指在进程的整个生命期内优先数保持不变；所谓“动态”优先级，是指在进程的整个生命期内可随时修正它的优先级别，以适应系统环境和条件的变化。,返回目录,3.3.4 多级队列调度算法,.,多级队列（MQ）调度算法，是把就绪进程按不同的性质组合成若干个就绪队

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

26、占，把CPU让给交互进程使用。,返回目录,系统从第1个队列开始调度；只有在前i-1个队列都空时，才调度第i个队列里的进程。当更高级别的队列到达进程时，系统将立即转去运行级别高的那个进程。,系统设多个就绪队列，有自己的优先级，第1个队列的优先级最高，越往下队列的优先级依次降低。,多级反馈队列（MFQ）调度算法，是在多级队列调度算法基础上加入队列间的反馈措施构成的，它允许进程在不同的就绪队列里移动。“反馈”，是依据进程使用CPU的时间长短进行的。,.,3.3.5 多级反馈队列调度算法,CPU,调度,阻塞，就绪,时间片到,CPU,调度,阻塞，就绪,完成,完成,时间片到,CPU,调度,阻塞，就绪,时间

27、片到,完成,到达,级1(先来先服务),级2(先来先服务),级n(轮转或先来先服务),.,多级反馈队列的做法,(1),(2),为就绪队列分配不同时间片，在优先级高的队列里的进程，获得的CPU服务时间短；在优先级低的队列里的进程，获得的CPU服务时间长。,(3),n个队列都实施FCFS调度算法，最后一个队列也可实施RR调度算法。新进程抵达时，先进入第1个就绪队列。进程在某个队列里获得时间片后，若用完时间片前被阻塞，仍回原队列末尾排队；若耗尽时间片后仍未做完工作，则将其移入低一级就绪队列排队，直至队列n。,(4),返回目录,所谓“任务速率”，是该任务周期T（单位为秒）的倒数。比如，如果一个任务的周期

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

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

30、就绪队列,.,优先级非抢占式调度：出现对实时进程的请求时，赋予它最高的优先级。这样，只要当前进程阻塞或完成，实时进程就可获得CPU。,当前进程,来自实时进程的请求,进程1,实时进程,实时进程被添加到就绪队列首,调度时间,就绪队列,当前进程阻塞或完成,.,基于优先级和时钟中断相结合的调度算法：通过时钟按照规则产生抢占点。在到达一个抢占点时，如果有更高优先级的进程在等待，那么就进行对CPU的抢占。,当前进程,来自实时进程的请求,进程1,实时进程,等待下一个抢占点,调度时间,下一个抢占点,就绪队列,当前进程,来自实时进程的请求,进程1,实时进程,实时进程抢占当前进程立即运行,.,立即抢占调度算法：操

31、作系统几乎是立即响应来自对实时进程的请求，以使调度的延迟时间降到最小。,返回目录,有三个都已就绪的实时任务A、B、C，利用最早截止时间优先（EDF）调度算法对它们实施调度。,3.4.2 最早截止时间优先调度算法,.,最早截止时间优先（EDF）算法，是通过任务最早截止时间所确定的优先级来进行调度，截止时间越早，其优先级就越高。,.,调度具体做法：记录每个任务每一次的最早截止时间；到达某任务的最早截止时间时，就产生该任务的一个实例，并进入就绪队列；有新任务进入就绪队列时，按照各任务当时的最早截止时间进行优先调度。,0,20,40,60,80,100,120,140,A1,B1,C1,A2,A3,A

32、4,A5,B2,B3,B4,C2,C3,A1截止时间,B1截止时间,C1截止时间,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：,实时任务,所需执行时间,ABC,10ms15ms5ms,周期,30ms40ms50ms,解：,返回目录,3.4.3 速率单调调度算法,.,速率单调调度（RMS）算法，基于任务的周期确定出任务的优先级，然后根据优先级进行

33、调度。周期越短，优先级越高。,.,调度具体做法：将任务的周期转化成它的速率，成为该任务的静态优先级；到达某个任务的最早截止时间时，产生该任务的一个实例，并进入就绪队列；有新任务进入就绪队列时，按照各个任务的优先级实施调度。,有三个都已就绪的实时任务A、B、C，利用速率单调调度（RMS）算法对它们实施调度。,例3-12：,解：,实时任务,所需执行时间,ABC,10ms15ms5ms,周期,30ms40ms50ms,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

34、截止时间,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,基本信息,速率单调调度(RMS),B3,B3,返回目录,实时进程：那些需要极快得到响应、有很强调度要求的进程为实时进程。这些进程如果得不到很快的响应，就可能会产生不可预料的后果。,3.5 Linux的处理机调度,3.5.1 涉及调度的进程分类,1.,根据性质分类,交互式进程：那些经常要与用户进行交互会话的进程为交互式进程。特点是要花费很多时间等待用户在键盘和鼠标上进行的操作

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

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

37、（最低优先级）。系统将根据进程的静态优先级、睡眠（等待）时间，计算出它的动态优先级。,(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为活动和过期进程 各维护

38、一个可运行进程 链表，每个链表按进程的优先级（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位的、5

39、个字组成的优先级位图，当且仅当某个优先级的进程队列不空时，对应的标志位为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是调

40、度程序中最重要的数据结构，它维护着活动进程和过期进程的可运行进程链表，随时记录着系统调度时所需的各种信息。,.,.,runqueue里涉及可运行进程的有关字段如下：,(1),curr：指向当前正在运行进程的PCB。,(2),active：指向活动进程的可运行链表指针。,(3),expired：指向过期进程的可运行链表指针。,(4),.,runqueue与prio_array_t 之间的关系，如图示。,返回目录,一个新的可运行进程到达可运行链表中的队列，如果它的优先级很高，或是一个实时进程，那么将会通过调用调度程序，使其先得到运行。,当进程状态发生转换，需要等待事件发生或被终止时，调用sleep

41、_on()和exit()等函数，这些函数都主动调用Linux的进程调度程序。,3.5.3 Linux的进程调度算法,1.,Linux进程的调度时机,进程调度程序是名为schedule()的函数，被调用的频率极高，由它来做出决定：是否要进行进程间的切换，以及切换到哪一个进程。,.,.,Linux系统进程调度的几种时机,(1),(2),当前运行进程时间片用完，意味着必须重新进行调度，因此主动调用Linux的进程调度程序。,(3),(4),系统处理中断或系统调用时，都有可能引起进程状态的变化。因此从内核态返回到用户态时，必须检查是否有必要重新进行调度。,把CPU分配给进程后，除非发生特殊情况（另一个

42、具有更高优先级的FIFO进程成为可运行；正在执行的FIFO进程因等待一事件而阻塞；正在执行的FIFO进程自动放弃CPU），系统不会中断正在执行的进程。,SCHED_FIFO,2.,Linux进程的三种调度算法,.,CHED_RR,.,(1),(2),一个FIFO进程被中断后，仍回到与其优先级相关联的队列中。,(3),当一个FIFO进程就绪、且优先级高于正在执行的进程时，就抢占CPU运行。,(4),调度时，若有多个相同高优先级的进程时，选择等待时间最长的进程投入运行。,.,SCHED_NORMAL,这是一种适用于普通进程（优先级从100139）的多级反馈调度算法，每个优先级队列采用轮转调度方式。

43、,这是一种适用于实时进程（优先级从199）的时间片轮转调度算法。进程在PCB的time_slice字段里，记录自己的时间片。用完时间片后，它被放回到相应队列的末尾，等待下一次调度。,这是一种适用于实时进程（优先级从199）的抢占式先进先出调度算法。所遵守的规则为：,静态优先级,3.,普通进程的优先级,.,普通进程都有自己的静态优先级（100139），默认值是120，它被记录在进程PCB的static_prio字段里。,(1),(2),最初，一个新进程的静态优先级是通过继承父进程的静态优先级得到的，它所持有的时间片是与父进程平分所剩余的时间片。,(3),一个进程用完了以前的时间片时，系统就会通过它的静态优先级，按照下面的公式计算出下一个时间片的长度：,时间片=,(140-静态优先级)20，若静态优先级=120,进程的等待时间与动态优先级,.,进程进入TASK_INTERRUPTIBLE和TASK_UNINTERRUPTIBLE等状态，表示开始等待。随进程等待时间的不同，Linux将在进程静态优先级的基础上，计算该进程被唤醒时应具有的动态优先级。,(1),(2),计算公式为：动态优先级=max（100，min（静态优先级-bonus+5，139）,.,总之，Linux是以优先级进行调度的，无论实施哪种调度算法，都遵循“先调度优先级高的进程，再调度优先级低的进程”的原则。,返回目录,