计算机操作系统（第3版）课件 第5章 CPU调度

第5章CPU调度CPUScheduling本章目标CHAPTEROBJECTIVES介绍CPU调度TointroduceCPUscheduling描述各种调度算法TodescribevariousCPU-schedulingalgorithms

调度的层次一个作业从提交到完成通常要经历多级调度。在不同操作系统中所采用的调度层次不完全相同。有的系统中仅采用一级调度，而在另一些系统中则可能采用两级或三级调度。

处理机的三级调度处理机的三级调度：作业调度进程调度交换调度

调度的层次运行就绪阻塞进程调度挂起阻塞挂起就绪中级调度创建退出作业调度作业调度作业调度又称高级调度、宏观调度或长程调度，其主要任务是按一定的原则从外存上处于后备状态的作业中选择一个或多个作业，给它们分配内存、输入/输出设备等必要的资源，并建立相应的进程，以使该作业具有获得竞争处理机的权利。作业调度的运行频率较低，通常为几分钟一次。

进程调度进程调度又称低级调度、微观调度或短程调度，其主要任务是按照某种策略和方法从就绪队列中选取一个进程，将处理机分配给它。进程调度的运行频率很高，一般几十毫秒要运行一次。

中级调度中级调度又称中程调度或交换调度，其功能是将内存中暂时不用的信息移到外存，以腾出空间给内存中的进程使用，或将需要的信息从外存读入内存。引入中程调度的目的是提高内存利用率和系统吞吐量。中级调度的运行频率介于两者之间。

作业调度作业是用户在一次解题或一个事务处理过程中要求计算机系统所做工作的集合，包括用户程序、所需的数据及命令等。计算机系统在完成一个作业的过程中所做的一项相对独立的工作称为一个作业步。例如，在编制程序过程中通常要进行编辑输入、编译、链接、运行几个作业步。

作业的状态及转换作业从提交到完成要经历四种状态：提交状态：用户作业由输入设备向系统外存输入时作业所处的状态。后备状态：作业输入到外存后，系统为其建立了作业控制块，并把它插入到后备作业队列中等待调度运行。运行状态：作业在内存中执行。完成状态：作业正常或异常结束，但作业占有的资源还未被系统全部回收。作业状态转换图阻塞就绪执行I/O请求I/O完成时间片完提交作业录入后备作业调度进程调度运行状态完成作业调度作业调度的功能作业调度程序主要完成以下工作记录进入系统的各个作业情况。从后备作业中挑选一些作业投入执行。为被选中的作业做好执行前的准备工作。在作业运行结束或运行过程中因某种原因需要撤离时，作业调度程序还要完成作业的善后处理工作。作业控制块为管理作业，系统设置了作业控制块。系统通过JCB感知作业的存在，JCB是作业存在的唯一标志。通常作业控制块中包括的主要内容有：资源要求。资源使用情况。作业的控制方式、类型和优先级等。作业名、作业状态。资源要求资源要求是指作业运行需要的资源情况，包括：估计运行时间、最迟完成时间、需要的内存容量、外设类型及数量等。资源使用情况资源使用情况包括作业进入系统的时间、开始运行时间、已运行时间、内存地址、外设台号等。作业控制方式、类型和优先级作业的控制方式有联机作业控制和脱机作业控制。从不同角度出发可以对作业进行不同的分类，如终端型和批量型，作业的优先级是指作业进入系统运行的优先级别，优先级高的作业可以优先进入系统运行。作业名、作业状态记录作业的标识信息及作业的当前状态。进程调度的功能进程调度程序主要完成以下功能：记录系统中所有进程的状态、优先数和资源情况。选择获得处理机的进程。实施处理机的分配及回收。引起进程调度的原因正在运行进程结束运行进程因某种原因阻塞，如P操作、I/O等从系统调用或中断返回时，有进程进入就绪队列且就绪队列为空，或进程优先级高于当前运行进程且为剥夺调度方式时间片用完5.1基本概念BasicConcepts多道程序的设计目标是在任何时候都有某些进程运行，使CPU利用率最大化。Theobjectiveofmultiprogrammingistohavesomeprocessrunningatalltimes，tomaximizeCPUutilization.5.1.1CPU-I/O区间周期

CPU–I/OBurstCycle

进程执行由CPU执行和I/O等待周期组成。ProcessexecutionconsistsofacycleofCPUexecutionandI/Owait.CPU区间和I/O区间的交替序列

AlternatingSequenceofCPUAndI/OBurstsCPU区间时间曲线图

HistogramofCPU-burstTimes大量测试表明CPU区间长度曲线呈现为大量短CPU区间和少量长CPU区间。

5.1.2CPU调度程序

CPUScheduler当CPU空闲时，操作系统就必须从就绪队列中选择一个进程来执行WhenevertheCPUbecomeidel，theoperatingsystemmustselectoneoftheprocessesinthereadyqueuetobeexecuted选择进程由短程调度程序或CPU调度程序执行。Theselectionprocessiscarriedoutbyshort-termscheduler（orCPUscheduler）5.1.3抢占调度

PreemptiveSchedulingCPU调度可能发生在下述四种情况下:CPUschedulingdecisionsmaytakeplaceunderthefollowingfourcircumstances：从运行状态转到等待状态

Switchesfromrunningtowaitingstate从运行状态转到就绪状态Switchesfromrunningtoreadystate.从等待状态转到就绪状态

Switchesfromwaitingtoreadystate.进程终止

aprocessterminates.

1、4两种情况下的调度称为非抢占式调度2、3两种情况下的调度称为抢占式调度进程调度的方式进程调度有两种方式：抢占方式非抢占方式抢占方式抢占方式：又称剥夺方式、可剥夺方式。这种调度方式是指允许调度程序根据某种原则去停止正在执行的进程，将已分配给该进程的处理机重新分配给其他进程。抢占原则有：优先权、时间片。非抢占方式非抢占方式：又称非剥夺方式、不可剥夺方式、不可抢占方式。这种调度方式是指一旦将处理机分配给某进程后，便让该进程一直执行，直到该进程完成或发生某事件而进入阻塞状态，才把处理机分配给其他进程。非抢占方式中引起进程调度的因素有：进程结束、因某种原因而阻塞、执行同步原语等。特点：简单，系统开销小，但无法处理紧急任务。5.1.4分派程序Dispatcher分派程序用来将对CPU的控制交给由短程调度程序选择的进程，其功能包括:

ThedispatchergivescontroloftheCPUtotheprocessselectedbytheshort-termscheduler，thisfunctioninvolves:切换上下文switchingcontext切换到用户态switchingtousermode跳转到用户程序的适当位置并重新运行之jumpingtotheproperlocationintheuserprogramtorestartthatprogram分派程序2Dispatcher分派延迟：分派程序终止一个进程的运行并启动另一个进程运行所花的时间.

Dispatchlatency：timeittakesforthedispatchertostoponeprocessandstartanotherrunning.也称为调度时间5.2调度准则

SchedulingCriteria由于操作系统的类型及目标不同，因此选择的调度策略及算法也不同。有很多调度性能评价准则，下面介绍几种主要的评价准则：调度准则2

SchedulingCriteriaCPU利用率：使CPU尽可能的忙碌CPUutilization：keeptheCPUasbusyaspossible吞吐量：单位时间内运行完的进程数Throughput：numberofprocessesthatarecompletedpertimeunit

周转时间：进程从提交到运行结束的时间间隔

Turnaroundtime：Theintervalfromthetimeofsubmissionofaprocesstothetimeofcompletion.等待时间：进程在就绪队列中等待调度的时间总和Waitingtime：amountoftimeaprocesshasbeenwaitinginthereadyqueue

调度准则3

SchedulingCriteria响应时间：从提交请求到系统首次产生响应所用的时间。Responsetime：Thetimefromthesubmissionofarequestuntilthefirstresponseisproduced.最优准则：OptimizationCriteria：最大的CPU利用率MaxCPUutilization最大的吞吐量Maxthroughput最短的周转时间Minturnaroundtime最短的等待时间Minwaitingtime最短的响应时间Minresponsetime周转时间作业的周转时间是指从作业提交到作业完成之间的时间间隔。平均周转时间是指多个作业的周转时间的平均值。ｎ个作业的平均周转时间：T=（T1＋T2＋

…

＋Tn）／n（Ti为作业ｉ的周转时间）带权周转时间带权周转时间是指作业周转时间与作业实际运行时间的比。平均带权周转时间是指多个作业的带权周转时间的平均值。ｎ个作业的平均带权周转时间：W＝（W1＋W2＋

…

＋Wn）/n（Wi为作业ｉ的带权周转时间）周转时间及带权周转时间例各作业感受如何?

12.91带权周转时间

6

30

1.5等待时间

1.2

3

3周转时间10.2

11.2

11完成时间0.2

0.12运行时间

9

8.2

8提交时间

C

B

A作业5.3调度算法

SchedulingAlgorithms调度算法是指根据系统资源分配策略所规定的资源分配算法。本节的算法有些适合作业调度，有些适合进程调度，有些适用于两者。5.3.1

先来先服务调度

First-Come,First-ServedScheduling先来先服务：先请求CPU的进程先分配到CPUFirst-come,first-servedscheduling：theprocessthatrequeststheCPUfirstisallocatedtheCPUfirst英文缩写：FCFS例一组进程在时间0到达Process

BurstTime

P124

P23

P3 3

Supposethattheprocessesarriveintheorder:P1,P2,P3。TheGanttChartforthescheduleis:

Waitingtime

forP1=0;P2=24;P3=27Averagewaitingtime:(0+24+27)/3=17P1P2P32427300例续SupposethattheprocessesarriveintheorderP2,P3,P1.TheGanttchartforthescheduleis:

Waitingtime

forP1=6;

P2=0;P3=3Averagewaitingtime:(6+0+3)/3=3比前例好得多。Muchbetterthanpreviouscase.护航效果：短进程在长进程之后。Convoyeffect：shortprocessbehindlongprocess

P1P3P263300先来先服务调度算法先来先服务算法既可用于作业调度，也可用于进程调度。在作业调度中：从后备作业队列中选择一个或多个最先进入该队列的作业，将它们调入内存，为它们分配资源，创建进程，然后放入就绪队列。进程调度中：从就绪队列中选择一个最先进入该队列的进程，为之分配处理机，使之投入运行。该进程一直运行到完成或因等待某一事件而阻塞时才释放处理机。设有4道作业，它们的提交时间及执行时间如下表，若按先来先服务调度算法进行调度，试计算4个作业的平均周转时间和平均带权周转时间。（时间单位：小时，以十进制计算）。先来先服务调度算法例

作业提交时间估计运行时间1102210.21310.40.5410.50.3作业周转时间及带权周转时间的计算平均周转时间T=(2.0＋2.8＋3.1＋3.3)/4=2.8平均带权周转时间W=(1＋2.8＋6.2＋11)/4=5.25116.22.81带权周转时间3.33.12.82周转时间13.813.51312完成时间13.5131210开始时间0.30.512运行时间10.510.410.210提交时间4321作业先来先服务算法特点算法简单，易于实现，但不利于短作业及I/O繁忙型作业。5.3.2最短作业优先调度

Shortest-Job-FirstScheduling最短作业优先：当CPU空闲时，将它赋予具有最短CPU区间的进程Shortest-job-firstscheduling：WhenCPUisavailable，itisassignedtotheprocessthathasthesmallestnextCPUburst.英文缩写：SJF

短作业优先调度算法在作业调度中，从后备队列中选择一个或多个估计运行时间最短的作业，将它们调入内存运行。在进程调度中，从就绪队列中选择一个估计运行时间最短的进程，为之分配处理机，使之投入运行。该进程一直运行到完成或因等待某一事件而阻塞时才释放处理机。（非抢占式调度算法）短作业优先调度算法例平均周转时间T=(2.0＋1.8＋2.4＋3.6)/4=2.45平均带权周转时间W=(1＋6＋4.8＋3.6)/4=3.8564.83.61带权周转时间1.82.43.62周转时间12.312.813.812完成时间1212.312.810开始时间0.30.512运行时间10.510.410.210提交时间4321作业短作业优先调度算法的特点算法调度性能较好，如上例中，先来先服务短作业优先平均周转时间2.82.45平均带权周转时间5.25

3.85但对长作业不利，未考虑作业的紧迫程度，运行时间为估计。最短剩余时间优先调度算法SJF算法可以是抢占的或非抢占的。TheSJFalgorithmcanbeeitherpreemptiveornonpreemptive.抢占SJF调度有时称为最短剩余时间优先调度，PreemptiveSJFschedulingissometimescalledshortest-remaining-time-firstscheduling.若到达新进程的CPU区间短于当前运行进程的剩余时间，则它将抢占CPU。ifanewprocessarriveswithCPUburstlengthlessthanremainingtimeofcurrentexecutingprocess,preempt.最短剩余时间优先算法例时间：1.42.6712.125带权周转时间724417周转时间1026517完成时间51710开始时间5948运行时间3210提交时间

D

C

B

A作业0A12B34510DA1726C最短剩余时间优先算法例（续）平均周转时间T=(17＋4＋24＋7)/4=13平均带权周转时间W=(2.125＋1＋2.67＋1.4)/4=1.81.42.6712.125带权周转时间724417周转时间1026517完成时间51710开始时间5948运行时间3210提交时间

D

C

B

A作业最短平均周转时间当一批作业同时到达时，最短作业优先调度算法才能获得最短平均周转时间。设一组作业p1、p2、…、pn，其运行时间为t1、t2、…、tn，且假定t1<t2<…<tn，则短作业优先调度算法的总周转时间为：t1+（t1+t2）+…+（t1+…+tn）=n*t1+（n-1）t2+…+tn最短平均周转时间（续）可以证明：若a1≤a2≤…≤an且b1≤b2≤…≤bn，则a1bn+a2bn-1+…+anb1≤a1bi1+a2bi2+…+anbin

≤a1b1+a2b2+…+anbn

其中i1、i2、…、in是1、2、…、n的一个排列。5.3.3

优先级调度

PriorityScheduling优先级调度：每个进程都有一个优先级与其关联，CPU分配给具有最高优先级的进程。PriorityScheduling：Apriorityisassociatedwitheachprocess，TheCPUisallocatedtotheprocesswiththehighestpriority.具有相同优先级的进程按FCFS顺序调度。Equal-priorityprocessesarescheduledinFCFSorder.优先级调度算法在作业调度中，从后备作业队列中选择若干优先级高的作业调入内存。在进程调度中，将处理机分配给就绪队列中优先级最高的进程。优先级表示进程的重要性及运行优先性，通常用优先数来衡量。在某些系统中，优先数越大优先级越高；而在另一些系统中，优先数越大优先级越小。按调度方式对优先级调度算法分类非抢占式优先级调度算法：系统一旦将处理机分配给就绪队列中优先级最高的进程后，该进程便一直运行下去，直到完成或因发生某事件使该进程放弃处理机时，系统才将处理机分配给另一个更高优先级的进程。抢占式优先级调度算法：将处理机分配给优先级最高的进程，使之运行。在进程运行过程中，一旦出现了另一个优先级更高的进程时，进程调度程序就停止原运行进程，而将处理机分配给新出现的高优先级进程。

优先级的类型优先级分为两种：静态优先级动态优先级静态优先级静态优先级是在创建进程时确定的，确定之后在整个进程运行期间不再改变。确定依据有：进程类型：系统，用户进程对资源的需求：执行时间，资源数量用户要求：紧迫程度特点：简单易行，系统开销小，但不精确。动态优先级动态优先级是指在创建进程时，根据进程的特点及相关情况确定一个优先级，在进程运行过程中再根据情况的变化调整优先级。确定原则有：占用CPU时间，等待时间。例：优先数=CPU使用时间/2+基本优先数CPU使用时间衰减函数:Decay(CPU使用时间)=CPU使用时间/2存在问题及解决方案问题：饥饿，低优先级的进程可能永远得不到运行Problem：Starvation，lowpriorityprocessesmayneverexecute.解决方法：老化，视进程等待时间的延长提高其优先级Solution：Aging，astimeprogressesincreasethepriorityoftheprocess.5.3.4时间片轮转调度

RoundRobin(RR)每个进程将得到小单位的CPU时间（时间片），通常为10-100毫秒。时间片用完后，该进程将被抢占并插入就绪队列末尾。EachprocessgetsasmallunitofCPUtime(timequantum),usually10-100milliseconds.Afterthistimehaselapsed,theprocessispreemptedandaddedtotheendofthereadyqueue.时间片轮转算法例设有A、B、C、D、E五个进程，其到达时间分别为0、1、2、3、4，要求运行时间依次为3、6、4、5、2，采用时间片轮转调度算法，当时间片大小为1和4时，试计算其平均周转时间和平均带权周转时间。时间片大小为1A、B、C、D、E要求运行时间依次为3、6、4、5、2，到达时间依次为0、1、2、3、4。

1：B运行，A等待；2：A运行，CB等待；3：C运行，BDA等待；4：B运行，DAEC等待；5：D运行，AECB等待；6：A运行，ECBD等待；7：E运行，CBD等待；8：C运行，BDE等待；9：B运行，DEC等待；10：D运行，ECB等待；11：E运行，CBD等待；12：C运行，BD等待；13：B运行，DC等待；14：D运行，CB等待；15：C运行，BD等待；16：B运行，D等待；17：D运行，B等待；18：B运行，D等待；19：D运行，0：A运行；时间片为1的周转时间平均周转时间T=(7＋18＋14＋17+8)/5=12.8平均带权周转时间W=(2.33＋3＋3.5＋3.4+4)/5=3.2463.43.532.33带权周转时间1714187周转时间2016197完成时间5310开始时间5463运行时间3210提交时间

D

C

B

A作业4812724

E时间片大小为4A、B、C、D、E要求运行时间依次为3、6、4、5、2，到达时间依次为0、1、2、3、4。0：A运行，BCD依次到达；3：B运行，CD等待，后E到达；7：C运行，DEB等待；11：D运行，EB等待；15：E运行，BD等待；17：B运行，D等待；19：D运行A、B、C、D、E开始时间依次为0、3、7、11、15；结束时间依次为3、19、11、20、17。时间片为4的周转时间平均周转时间T=(3＋18＋9＋17+13)/5=12平均带权周转时间W=(1＋3＋2.25＋3.4+6.5)/5=3.233.42.2531带权周转时间179183周转时间2011193完成时间11730开始时间5463运行时间3210提交时间

D

C

B

A作业6.513171524

E时间片大小的选择若时间片太大，所有进程都能在一个时间片内完成，则时间片轮转算法退化为先来先服务；若时间片太小，则进程调度频繁，系统开销增加。因此时间片大小选择应适当。现代操作系统的时间片一般为10-100ms，上下文切换时间一般少于10us。确定时间片大小应考虑的因素系统对响应时间的要求：响应时间=时间片*进程数。进程数一定，则时间片与系统响应时间成正比。就绪队列中的进程数目：时间片与就绪进程数成反比。系统处理能力：人所能承受的响应时间一定，系统速度快则时间片可增长。时间片轮转算法的特点及改进对偏重I/O的进程不公平。为此改进为虚拟时间片轮转算法。虚拟时间片轮转算法：新进程基于FCFS进入就绪队列，进程用完时间片后也进入就绪队列，进程因I/O阻塞进入I/O队列，I/O完成时进程进入附加队列，附加队列的优先级高于就绪队列，当进程从附加队列被调度时，其运行时间不超过上次发生中断时剩余的时间。虚拟时间片轮转调度示意图CPU新进程就绪队列调度超时优先级高附加队列I/O队列请求I/OI/O完成高响应比优先调度算法高响应比优先调度算法是对短作业优先调度算法和先来先服务调度算法的一种综合。响应比响应比定义如下：响应比＝作业响应时间/估计运行时间由于响应时间为作业进入系统后的等待时间加上估计运行时间。因此响应比＝1＋作业等待时间/估计运行时间高响应比优先调度算法思想在每次调度作业运行时，先计算后备作业队列中每个作业的响应比，然后挑选响应比最高者投入运行。特点：有利于短作业-----等待时间相同，短作业优先，考虑等待时间----运行时间相同，等待时间长的作业优先运行。最高响应比优先算法例设有A、B、C、D、E五个进程，其到达时间分别为0、1、2、3、4，要求运行时间依次为3、6、4、5、2，采用最高响应比优先调度算法，试计算其平均周转时间和平均带权周转时间。分析作业的调度顺序A、B、C、D、E的到达时间依次为0、1、2、3、4，要求运行时间依次为3、6、4、5、20：A运行，BCD依次到达；3：rB=1+2/6，

rC=1+1/4，

rD=1；B先运行。9：rC=1+7/4，

rD=1+6/5，

rE=1+5/2；E先运行。11：rC=1+9/4，

rD=1+8/5；C先运行。由此可知作业的运行顺序为A、B、E、C、D。周转时间的计算顺序A、B、E、C、D平均周转时间T=(3＋8＋13＋17+7)/5=9.6平均带权周转时间W=(1＋1.33＋3.25＋3.4+3.5)/5=2.4963.43.251.331带权周转时间171383周转时间201593完成时间151130开始时间5463运行时间3210提交时间

D

C

B

A作业3.5711924

E5.3.5

多级队列调度

MultilevelQueueScheduling将就绪队列分为多个独立队列Readyqueueispartitionedintoseveralseparatequeues.根据进程属性，一个进程被永久分配到一个队列。Theprocessesarepermanentlyassignedtoonequeue，basedonsomepropertyoftheprocess.每个队列有自己的调度算法。Eachqueuehasitsownschedulingalgorithm.多级队列调度2

MultilevelQueueScheduling例如，可以将就绪进程队列分为Forexample，separatequeuesmightbeusedfor：前台（交互式）：foreground(interactive)--RR后台（批处理）：background(batch)—FCFS前台作业的优先级高Foregroundprocessesmayhavepriorityoverbackgroundprocesses.MultilevelQueueScheduling5.3.6

多级反馈队列调度

MultilevelFeedbackQueueScheduling进程能在不同的队列间移动。Aprocesscanmovebetweenthevariousqueues.如果进程使用过多CPU时间，那么它会被移到更低优先级队列，IfaprocessusestoomuchCPUtime，itwillbemovedtoalower-priorityqueue.此外在较低优先级队列中等待时间过长的进程会被移到更高优先级队列。Inaddition，aprocessthatwaitstoolonginalower-priorityqueuemaybemovedtoahigt-priorityqueue.多级反馈队列调度2

MultilevelFeedbackQueueScheduling多级反馈队列调度程序由以下参数定义:Multilevel-feedback-queueschedulerdefinedbythefollowingparameters:队列数numberofqueues每一队列的调度算法schedulingalgorithmsforeachqueue

决定进程升级的方法methodusedtodeterminewhentoupgradeaprocess决定进程降级的方法methodusedtodeterminewhentodemoteaprocess决定需要服务的进程将进入哪个队列的方法methodusedtodeterminewhichqueueaprocesswillenterwhenthatprocessneedsserviceMultilevelFeedbackQueues多级反馈队列调度算法应设置多个就绪队列，并为每个队列赋予不同的优先级。第1个队列的优先级最高，第2队列次之，其余队列的优先级逐次降低。每个队列中进程执行的时间片大小也各不相同，进程所在队列的优先级越高，其相应的时间片就越短。多级反馈队列调度算法2当一个新进程进入系统时，首先将它放入第1个队列的末尾，按先来先服务的原则排队等待调度。当轮到该进程执行时，如能在此时间片内完成，便可准备撤离系统；如果它在一个时间片结束时尚未完成，调度程序便将该进程转入第2队列的末尾，再同样地按先来先服务原则等待调度执行。如此下去，最后一个队列中使用时间片轮转调度算法。多级反馈队列调度算法3仅当第1个队列为空时，调度程序才调度第2队列中的进程运行；仅当第1个至第（i－1）个队列均为空时，才会调度第i个队列中的进程运行。当处理机正在为第i个队列中的某进程服务时，若又有新进程进入优先级较高的队列中，则此时新进程将抢占正在运行进程的处理机，即由调度程序把正在执行进程放回第i个队列末尾，重新将处理机分配给新进程。多级反馈队列调度算法示意图就绪队列1CPU就绪队列2就绪队列nCPUCPU完成完成完成多级反馈队列调度算法例设有A、B、C、D、E五个进程，其到达时间分别为0、1、3、4、5，要求运行时间依次为3、8、4、5、7，采用多级反馈队列调度算法，系统中共有3个队列，其时间片依次为1、2和4，试计算其平均周转时间和平均带权周转时间。13：EE运行，BCD等待；调度分析A、B、C、D、E到达时间依次为0、1、3、4、5，要求运行时间依次为3、8、4、5、71：B运行，A等待；2：A运行，B等待；3：C运行，BA等待；4：D运行，BAC等待；5：E运行，BACD等待；6：BB运行，ACDE等待；8：A运行，CDE等待；B等待9：CC运行，DE等待；B等待11：DD运行，E等待；BC等待15：BBBB运行，CDE等待；19：C运行，DEB等待；20：DD运行，EB等待；22：EEEE运行，B等待；0：A运行；26：B运行。周转时间的计算平均周转时间T=(9＋26＋17＋18+21)/5=18.25平均带权周转时间W=(3＋3.25＋4.25＋3.6+3)/5=3.423.64.253.253带权周转时间1817269周转时间2220279完成时间4310开始时间5483运行时间4310提交时间

D

C

B

A作业32126575

E多级反馈队列调度算法的性能多级反馈队列调度算法能较好满足各类用户的需求：终端型用户：大多能在一个时间片内完成，响应时间较短；短批处理作业用户：能在前几个队列完成，周转时间较短；长批处理作业用户：依次在1～n队列中运行，不会长时间得不到处理。公平分享调度算法公平分享调度算法基于进程组来分配CPU时间，其实现思想是对系统中的每个用户赋予某种权值，根据用户权值大小，按比例分配处理机时间。公平分享调度有许多实现方案，本节讲述UNIX中的一种实现方案。UNIX中的公平分享调度UNIX基于优先权调度，优先数越大优先权越低。对进程组k中进程j的优先数计算公式如下：CPUj（i）=CPUj（i-1）/2；进程j在时间段i使用的CPU时间GCPUk（i）=GCPUk（i-1）/2；进程组k在时间段i使用的CPU时间Pj（i）=Basej+CPUj（i）/2+GCPUk（i）/4Wk；进程j在时间段i的优先数，Basej

为进程j的基本优先数，Wk为进程组k的权值。公平分享调度例下例中Wk为0.5，Base为60。相应的优先数计算公式为：CPUj（i）=CPUj（i-1）/2；GCPUk（i）=GCPUk（i-1）/2；Pj（i）=60+CPUj（i）/2+GCPUk（i）/2公平分享调度例进程A进程B

进程C时间

优先数

计数组优先数计数组

优先数

计数组

060006000

60001122

…

…606019030306000

6000

111222

…

…

…606060公平分享调度例（续1）进程A进程B

进程C时间

优先数

计数组优先数计数组

优先数

计数组

2741515903030

7503016161717

…

…75753963737741515

67015

1611617217

…

…

…756075公平分享调度例（续2）进程A进程B

进程C时间

优先数

计数组优先数计数组

优先数

计数组

478181881737

93303719192020

…

…7878598393970318

761518

5.4多处理器调度多处理器调度问题更复杂主要讨论处理器功能相同的系统。负载分配（LoadSharing）非对称多道程序：只有一个处理器访问系统数据结构，减轻了数据共享的需要。5.5线程调度竞争范围：用户级线程和内核级线程不同。Pthread调度5.6操作系统实例Linux调度两种算法：分时与实时分时基于信用度的算法信用度随着定时器中断的发生而降低当所有进程的信用度都为0的时候，则重新计算信用度这种算法似乎混合了两个因素：进程历史和它的优先级实时软实时实现了两种POSIX.1b所要求的实时调度类型：FCFS和RR高优先级的进程总是最先运行5.7算法评估确定性建模：采用特定预先确定的负荷，定义在给定负荷下每个算法的性能。简单快速，给出了确切数字，以允许算法被比较但通常过分特殊且要求过多精确知识，故用处有限排队模型：在许多系统上运行的进程每天都在变化，因此没有静态的进程集合和时间用于确定性建模。n为平均队列长度（不包括正在服务的进程）Ｗ为队列的平均等待时间λ为新进程到达队列的平均到达率n=λ×W(Little公式)可用于比较调度算法，但计算结果的精确性值得怀疑通过模拟来评估CPU调度算法实现即使模拟其精确度也是有限的。针对评估调度算法，惟一完全精确的方法是对它进行程序编码，将其放在操作系统内，并观测它如何工作。主要困难是这种方法的代价对算法编码、修改操作系统以支持该算法用户对不断变化的操作系统的反应另一困难是算法所使用的环境会变化最为灵活的调度算法可以为系统管理员或用户所改变习题习题55.2Explainthedifferencebetweenpreemptiveandnonpreemptivescheduling.5.4Considerthefollowingsetofprocesses,withthelengthoftheCPUbursttimegiveninmilliseconds:ProcessBurstTimePriorityP122P211P384P442P553TheprocessesareassumedtohavearrivedintheorderP1,P2,P3,P4,P5,allattime0.习题a.DrawfourGanttchartsthatillustratetheexecutionoftheseprocessesusingthefollowingschedulingalgorithms:FCFS,SJF,nonpreemptivepriority(alargerprioritynumberimpliesahigherpriority),andRR(quantum=2).b.Whatistheturnaroundtimeofeachprocessforeachoftheschedulingalgo