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

第3章处理机管理本章目录3.1处理机调度概述3.1.1处理机调度的三个层次3.1.2进程调度的功能、时机和基本策略3.2作业调度算法3.2.1先来先服务调度算法3.2.2短作业优先调度算法3.5.3Linux的进程调度算法3.2.3最短剩余时间优先调度算法3.1.3调度算法的性能评价指标3.4实时处理与实时调度算法3.4.1实时处理的特征3.4.2最早截止时间优先调度算法3.4.3速率单调调度算法3.5Linux的处理机调度3.5.1涉及调度的进程分类3.5.2Linux的可运行队列3.2.4最高响应比调度算法3.3进程调度算法3.3.1先来先服务调度算法3.3.2轮转调度算法3.3.3优先级调度算法3.3.4多级队列调度算法3.3.5多级反馈队列调度算法3.1处理机调度概述3.1.1处理机调度的三个层次高级调度1.当系统决定接纳一个作业时，就要为它开辟一个作业控制块（JCB），以便随时记录作业的信息。..被系统接纳的作业，在没有投入运行前是以“后备作业”的形式存放在辅存里。所有后备作业的JCB链接在一起，形成“后备作业队列”。这些作业没有资格参与对处理机的竞争，但系统从它们的里面去挑选参与CPU竞争的作业。.高级调度决定哪个后备作业可进入系统去接受处理，它控制着多道程序设计环境的“度”：进到系统的作业多，资源的利用率提高了，但每个作业获得处理结果的时间可能会长；进到系统的作业少，每个作业很快就得到自己的处理结果，但资源的利用率可能会下降。低级调度2..低级调度真正决定CPU下一次执行哪一个进程，它将按照一定的算法，从就绪队列里挑选出可运行的进程投入运行。低级调度的各种算法，是我们讨论的主要目标。低级调度也被称为“进程调度”。中级调度3..中级调度是介于高级调度和低级调度之间的一种调度，如果系统为进程设置有“挂起”状态，那么就会涉及到中级调度。也就是说，中级调度与实施进程的内、外存交换有关。CPU就绪队列低级调度释放中级调度就绪/挂起队列时间片到高级调度阻塞/挂起队列阻塞队列中级调度事件等待事件发生交互用户作业后备作业队列.系统中出现过高并发度时，就应将内存中的某些进程暂时换出到外存；系统的并发度较低时，就应该将外存中的某些进程换入到内存。进程在内、外存间的换出和换入，就是中级调度承担的责任，通过这种交换，以求达到调节和平衡系统“并发度”的目的。.高级调度执行的频繁程度很低，它只是粗略地决定是否接受一个新进程以及接受哪一个；中级调度为了实施交换决策，执行的频率相对要频繁一些；低级调度要精确地决定执行哪一个进程，因此执行的频度为最高。返回目录3.1.2进程调度的功能、时机和基本策略1.进程调度程序的功能.保护现场.挑选运行对象.恢复现场2.发生进程调度的时机当某进程正常完成自己的运行或被终止时，为不让CPU空闲，必须实行调度，以便从就绪队列里挑选新的进程投入运行。..分时系统中，时钟中断处理程序发现分配给某个进程的时间片用完时，就强制它交出CPU，重新进行CPU调度。.运行中的进程提出I/O请求，或要等待别的进程发来消息，于是自己被阻塞。.执行操作系统提供的某些系统调用命令，如wait()等。.某进程的状态从阻塞变为就绪时，要由调度程序决定让哪一个进程投入运行：是新就绪进程、是正在运行的进程继续运行、还是调度另一个进程运行。3.进程调度的基本策略非抢占式：在把CPU分配给某个进程后，就一直让它使用下去，直到进程完成自己的工作，或因要等待某事件的发生而交出CPU，否则不允许其他进程夺取CPU。..抢占式：在调度程序把CPU分配给某进程使用后，只要满足某条件，就允许立即把CPU从运行进程手中夺取过来，分配给满足条件的进程使用。返回目录特定作业从提交给系统到获取结果所经历的时间间隔。因此，设作业i向系统提交的时间为Tpi，完成时间是Tci，那么它的周转时间Ti为：Ti=Tci-Tpi。3.1.3调度算法的性能评价指标1.2.吞吐量周转时间所谓“吞吐量”，是指单位时间内CPU完成作业的数量。.有的作业属于“处理机限制”型的，即需要花费大量的CPU时间，很少输入/输出，也称“CPU繁忙”型；有的属于“I/O限制”型的，即它在运行期间主要是输入/输出，很少进行计算和处理，也称“I/O繁忙”型。..作业的周转时间作业的周转时间是指作业的执行时间加上作业的等待时间。设作业i的等待时间为Twi，执行时间为Tsi，那么它的周转时间Ti为：Ti=Twi+Tsi。（1）（2）.作业的平均周转时间n个作业，每个作业的周转时间为Ti，那么它们的平均周转时间为：T=(∑Ti)×─i=1nn1利用平均周转时间，可以基于同一批作业，来衡量不同调度算法的调度性能。..作业的“带权周转时间”，指该作业的周转时间与所需运行时间之比。设作业i周转时间为Ti，所需执行时间为Ri，那么它的带权周转时间Wi为：.作业的平均带权周转时间（3）n个作业，每个作业的带权周转时间为Wi，那么它们的平均周转时间为：.W=(∑)×TiRi1n利用平均带权周转时间，可基于同一调度算法，对不同批次作业的调度性能做出比较。..CPU的利用率3.所谓“CPU的利用率”，是指在一定的时间区间内，CPU为用户提供服务的时间与其总运行时间的比率。作业i的CPU利用率Ui，是指该作业的执行时间Ci与周转时间Ti的比率。即：.Wi=Ti/RiUi=Ci/Ti.如果系统内有n个作业，那么整个系统CPU的平均利用率应为：U=(∑Ci/Ti)×─i=1nn1公平性：调度的设计，应该顾及到所有作业或进程对CPU的不同需求，尽量做到公平合理，不偏不倚。设计目标：设计目标是决定算法的主要因素，目标不同，要求肯定不一样。比如批处理系统的调度，应尽量提高各种资源的利用率，以及整个系统的吞吐量；分时系统的调度，应将对用户提出的请求作出回应的速度，控制在用户能够容忍的范围内；实时系统的调度，应保证对所发生的的事件做出及时的响应和处理；如此等等。响应比4..所谓作业的“响应比”，是指一个特定作业的周转时间与它所需的执行时间之比。.作业i的等待时间为Twi，执行时间为Tsi，那么该作业的响应比RRi是：RRi=(Twi+Tsi)/Tsi影响调度算法设计的因素.（1）（2）（3）均衡性：调度算法应考虑资源使用的均衡性，使系统中的各种资源都能得到充分地利用。比如，把“处理机限制”和“I/O限制”作业搭配，就有可能收到良好的效果。（4）兼顾性：调度算法应既考虑长作业的要求，也考虑短作业的要求；既考虑高优先级进程的要求，也要顾及低优先级进程的利益。只偏袒某一方，所造成的后果有可能是严重的，甚至是无法弥补的。返回目录右示三个作业，按1、2、3的顺序提交给系统，采用FCFS调度算法。画出它们的“甘特图”，计算每个作业的周转时间及平均周转时间。（忽略系统调度所需额外的时间开销）作业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：作业所需CPU时间1232433解：作业1作业2作业32433.所谓“甘特图”，即是指能够反映作业调度顺序及占用CPU时间的一种进度图。右示五个作业，采用FCFS作业和进程调度算法，可供5个作业使用的内存空间为100KB，需要时按序分配。作业进入内存后，不许在内存中移动。计算每个作业的周转时间和平均周转时间。（忽略系统调度时间，作业都没有输入/输出请求）例3-2：作业所需CPU时间1234510.110.310.510.610.7到达时间所需内存量0.70.50.40.40.215KB70KB50KB20KB10KB解：.各作业的周转时间装入内存时间完成时间10.110.311.311.310.7开始运行时间周转时间10.811.311.912.311.50.71.01.41.70.810.110.811.511.910.3.作业运行时的内存分配情况作业1(15KB)作业2(70KB)作业5(10KB)空闲(5KB)(a)到10.7时内存情形空闲(15KB)作业2(70KB)作业5(10KB)空闲(5KB)(b)到10.8作业1完成时内存情形作业3(50KB)作业4(20KB)作业5(10KB)空闲(5KB)(c)到11.3作业2完成时内存情形空闲(15KB)这批作业的调度顺序是：1→2→5→3→4，系统的平均作业周转时间为：(0.7+1.0+1.4+1.7+0.8)/5=1.12.返回目录各自的开始运行时间、完成时间、周转时间以及带权周转时间如下所示。五个作业的调度顺序是A→B→E→C→D。有5个作业A~E，情况如表所示，按照SJF进行作业调度。计算它们各自的开始运行时间、完成时间、周转时间以及带权周转时间。短作业优先（SJF）调度算法，总是在作业后备队列里选择要求运行时间最短的、满足其资源需要的作业进入内存，参与对CPU的竞争。3.2.2短作业优先调度算法...例3-4：作业所需CPU时间ABCDE02468到达时间36452解：作业调度的gantt图：作业A作业B作业C作业E作业D36425.开始运行时间带权周转时间0311159完成时间周转时间371114311.172.752.801.5039152011返回目录3.2.3最短剩余时间优先调度算法.最短剩余时间优先（SRTF）作业调度算法，是在调度时从后备作业队列里挑选所需运行时间最短的作业投入运行。运行过程中，若有运行时间更短的作业达到，那么它就抢占CPU，让当前正在运行的作业暂停执行。例3-5：有5个作业A~E，情况如表所示，按照SRTF进行作业调度。计算它们的开始运行时间、完成时间、周转时间以及带权周转时间。作业所需CPU时间ABCDE02468到达时间36452解：.各自的开始运行时间、完成时间、周转时间以及带权周转时间如下所示。五个作业的调度顺序是：A→B→C→E→B→D。.作业调度的gantt图：.开始运行时间带权周转时间034158完成时间周转时间313414212.171.02.801.031582010ABCEBD0348101520时间E到达D到达C到达B到达A到达62返回目录各自的开始运行时间、完成时间、周转时间以及带权周转时间如下所示。有5个作业A~E，情况如表所示，按照HRRN进行作业调度。计算它们的开始运行时间、完成时间、周转时间以及带权周转时间。最高响应比（HRRN）调度算法，是在进行新一次调度时，计算后备作业队列里所有作业当前的响应比RR，挑选出响应比最高者参与对CPU的竞争。3.2.4最高响应比调度算法.例3-6：作业所需CPU时间ABCDE02468到达时间36452解：.开始运行时间带权周转时间0391513完成时间周转时间37914711.172.252.803.539132015作业调度的gantt图：.作业A作业B作业C作业E作业D36425.时刻9作业B完成后，作业C、D、E都到达系统。计算它们三个的响应比，即：RRC=((9-4)+4)/4=2.25RRD=((9-6)+5)/5=1.6RRE=((9-8)+2)/2=1.5比较后知，这时作业C的响应比最高，所以应调度它运行。五个作业调度顺序是：A→B→C→E→D。返回目录3.3进程调度算法3.3.1先来先服务调度算法进程的先来先服务调度算法作用在就绪队列上。进程就绪时，将PCB插入到就绪队列尾部；调度时，总是把CPU分配给就绪队列之首的进程使用。它一直占用CPU，除非运行结束自愿释放，或因等待某事件的发生交出CPU。这是一种非抢占式的调度算法