第4章调度与死锁1.ppt

《第4章调度与死锁1.ppt》由会员分享，可在线阅读，更多相关《第4章调度与死锁1.ppt（68页珍藏版）》请在三一文库上搜索。

1、第4章 调度与死锁,处理机调度需要解决的问题： 多任务以何种方式共享处理机； 各任务处理机时间的分配和使用处理机时间长短的确定； 处理机的分配策略； 交换控制权的频繁程度和开销之间必须权衡。,4.1 调度的层次与性能评价,一个作业从提交到完成通常要经历多级调度。 在不同操作系统中所采用的调度层次不完全相同。 有的系统中仅采用一级调度，而在另一些系统中则可能采用两级或三级调度。,处理机的三级调度,处理机的三级调度： 作业调度 进程调度 交换调度,1.调度的层次,运行,就绪,阻塞,进程调度,挂起阻塞,挂起就绪,中级调度,创建,退出,作业调度,作业调度,作业调度又称高级调度、宏观调度或长程调度，其主

2、要任务是按一定的原则从外存上处于后备状态的作业中选择一个或多个作业，给它们分配内存、输入/输出设备等必要的资源，并建立相应的进程，以使该作业具有获得竞争处理机的权利。然后将新创建的进程排入就绪队列，准备执行。进程经过若干次状态转换后，作业执行结束。 一般要经历提交、收容、运行和完成等四个阶段。,作业调度,作业调度的运行频率较低，通常为几分钟一次。 在批处理系统中或通用系统批处理部分，新提交的作业先存放在磁盘上，因此需要作业调度，将它们分批装入内存。而在其他类型的操作系统中不需要配置作业调度。,进程调度,进程调度又称低级调度、微观调度或短程调度，其主要任务是按照某种策略和方法从就绪队列中选取一个

3、进程，将处理机分配给它。 进程调度的运行频率很高，一般几十毫秒要运行一次。 是最基本的调度，在一般os中都配置。,中级调度,中级调度又称中程调度或交换调度，其功能是将内存中暂时不用的信息移到外存，以腾出空间给内存中的进程使用，或将需要的信息从外存读入内存。 引入中程调度的目的是提高内存利用率和系统吞吐量。它实际上是存储器管理中的交换功能。 中级调度的运行频率介于两者之间。,2. 调度性能评价,由于操作系统的类型及目标不同，因此选择的调度策略及算法也不同。 调度算法的好坏直接影响系统的性能，影响调度算法的因素很多，常互相矛盾，所以实际采用的调度算法往往依赖系统的设计目标。,系统设计应达到的目标,

4、系统的处理能力高。使系统每天运行尽可能多的作业。 系统资源利用充分。使处理机保持忙碌状态，使设备保持忙碌状态，以达到充分利用系统资源的目的。 算法对所有的作业公平合理。使所有用户感到满意。 同时满足不可能，根据需要兼顾某些目标。,确定调度算法时应考虑因素,设计目标：系统选择的调度算法应与系统的总体设计目标一致。如分时系统应保证用户所能忍受的响应时间 。 资源使用的均衡性：例如I/O和CPU搭配 平衡系统和用户的要求：如任何用户都希望自己的作业一进入系统就立即执行，而系统却要考虑综合效益。因此对用户而言应该保证作业在截止时间内完成，而系统应该缩短作业的平均周转时间。,调度性能的评价准则,有很多评

5、价准则，下面介绍几种主要的评价准则： CPU利用率高。一般在40%-90%之间。CPU利用率CPU有效工作时间/CPU总的运行时间 系统吞吐量大。系统吞吐量表示单位时间内CPU完成作业的数量。 周转时间短。 响应时间快。响应时间是指从用户提交请求到系统首次产生响应所用的时间。这是分时系统和实时系统衡量调度性能的一个重要指标。,周转时间,作业的周转时间是指从作业提交到作业完成之间的时间间隔。 平均周转时间是指多个作业的周转时间的平均值。个作业的平均周转时间： T =（T1T2 Tn）n（Ti为作业的周转时间）,带权周转时间,带权周转时间是指作业周转时间与作业实际运行时间的比。 平均带权周转时间是

6、指多个作业的带权周转时间的平均值。个作业的平均带权周转时间： W （W1W2 Wn）/n（Wi为作业的带权周转时间）,这些因素一般无法全部满足，因为它们有时相互矛盾。 分时系统： 重点考虑响应时间、公平性 批处理系统： 重点考虑吞吐率、周转时间 实时系统： 要求CPU能及时响应。,4.2 作业调度,作业是用户在一次解题或一个事务处理过程中要求计算机系统所做工作的集合，包括用户程序、所需的数据及命令等。 计算机系统在完成一个作业的过程中所做的一项相对独立的工作称为一个作业步。 例如，在编制程序过程中通常要进行编辑输入、编译、链接、运行几个作业步。,作业的状态及转换,作业从提交到完成要经历四种状态

7、： 提交状态：用户作业由输入设备向系统外存输入时作业所处的状态。 后备状态：作业输入到外存后，系统为其建立了作业控制块，并把它插入到后备作业队列中等待调度运行。从作业输入开始到放入后备队列这一过程称为收容阶段，也称为作业注册。 运行状态：作业在内存中执行。不一定真正占有处理机 完成状态：作业正常或异常结束，但作业占有的资源还未被系统全部回收。 此时，os将JCB从作业队列中删除，并且收回资源，将运行结果存入输出文件输出。,作业状态转换图,阻塞,就绪,执行,I/O请求,I/O完成,时间片完,提交,作业录入,后备,作业调度,进程调度,运行状态,完成,作业调度,SPOOLING技术,SPOOLING

8、技术 , 也称作假脱机技术,实现原理是在硬盘中开辟出一块称之为输入井和输出井的空间,将多个用户作业随机存储在输入井中,各个用户作业之间相互隔离,互不干扰。当系统要调度用户作业执行时，不是从输入设备上得到该作业，而是直接从输入井中提取。这样就缩短了用户作业提交的时间。同样，当需要把执行作业过程中的数据向慢速的外部I/O设备输出时，不是直接向外部设备输出，而是写入到输出井中，然后再从输出井向外部设备输出。通过外部设备的频繁工作，提高了系统的效率。,2.作业调度,作业调度程序主要完成以下工作 记录进入系统的各个作业情况。 从后备作业中挑选一些作业投入执行。数量有限，一般4或10个。 为被选中的作业做

9、好执行前的准备工作。例如创建进程，分配资源。 在作业运行结束或运行过程中因某种原因需要撤离时，作业调度程序还要完成作业的善后处理工作。例如把作业的一些如运行时间、执行情况等信息输出，回收资源，撤销进程和JCB。,作业控制块,为管理作业，系统设置了作业控制块。系统通过JCB感知作业的存在，JCB是作业存在的唯一标志。 通常作业控制块中包括的主要内容有： 资源要求。 资源使用情况。 作业的控制方式、类型和优先级等。 作业名、作业状态。,资源要求,资源要求是指作业运行需要的资源情况，包括：估计运行时间、最迟完成时间、需要的内存容量、外设类型及数量等。,资源使用情况,资源使用情况包括作业进入系统的时间

10、、开始运行时间、已运行时间、内存地址、外设台号等。,作业控制方式、类型和优先级,作业的控制方式有联机作业控制(直接控制)和脱机作业控制（自动控制）。 从不同角度出发可以对作业进行不同的分类，如终端型和批量型，I/O繁忙型和CPU繁忙型。 作业的优先级是指作业进入系统运行的优先级别，优先级高的作业可以优先进入系统运行。,作业名、作业状态,记录作业的标识信息及作业的当前状态。,4.3 进程调度,进程调度程序主要完成以下功能： 记录系统中所有进程的状态、优先数和资源情况。进程调度程序通过PCB的变化来掌握系统所有的执行情况和状态特征。 选择获得处理机的进程。按照一定的策略选择一个处于就绪状态的进程。

11、 实施处理机的分配及回收。当正在执行的进程要放弃CPU时，进程调度程序要保护CPU现场，将状态由执行改为就绪或阻塞，并插入到相应队列中，同时从就绪队列中挑选一个进程移出，恢复其CPU现场，并且将状态改为执行。,引起进程调度的原因,正在运行进程结束。正常结束或出现错误异常结束。 运行进程因某种原因阻塞，如I/O等 执行某种原语操作，如P操作、阻塞原语等 从系统调用或中断返回时，有进程进入就绪队列且就绪队列为空，或进程优先级高于当前运行进程且为剥夺调度方式 时间片用完,2. 进程调度方式,进程调度有两种方式： 抢占方式 非抢占方式,抢占方式,抢占方式：又称剥夺方式、可剥夺方式。这种调度方式是指允许

12、调度程序根据某种原则去停止正在执行的进程，将已分配给该进程的处理机重新分配给其他进程。 抢占原则有：优先权、时间片。,非抢占方式,非抢占方式：又称非剥夺方式、不可剥夺方式、不可抢占方式。这种调度方式是指一旦将处理机分配给某进程后，便让该进程一直执行，直到该进程完成或发生某事件而进入阻塞状态，才把处理机分配给其他进程。 非抢占方式中引起进程调度的因素有：进程结束、因某种原因而阻塞、执行同步原语等。 特点：简单，系统开销小，但无法处理紧急任务。,4.4 调度算法,调度算法是指根据系统资源分配策略所规定的资源分配算法。 本章的算法有些适合作业调度，有些适合进程调度，有些适用于两者。,1先来先服务调度

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

14、.8 平均带权周转时间W=(12.86.211)/4=5.25,11,6.2,2.8,1,带权周转时间,3.3,3.1,2.8,2,周转 时间,13.8,13.5,13,12,完成 时间,13.5,13,12,10,开始 时间,0.3,0.5,1,2,运行 时间,10.5,10.4,10.2,10,提交 时间,4,3,2,1,作业,先来先服务算法特点,算法简单，易于实现， 但不利于短作业及I/O繁忙型作业。,2.短作业优先调度算法,在作业调度中，从后备队列中选择一个或多个估计运行时间最短的作业，将它们调入内存运行。 在进程调度中，从就绪队列中选择一个估计运行时间最短的进程，为之分配处理机，使之

15、投入运行。该进程一直运行到完成或因等待某一事件而阻塞时才释放处理机。,短作业优先调度算法例,平均周转时间 T=(2.01.82.43.6)/4=2.45 平均带权周转时间 W=(164.83.6)/4=3.85,6,4.8,3.6,1,带权周转时间,1.8,2.4,3.6,2,周转 时间,12.3,12.8,13.8,12,完成 时间,12,12.3,12.8,10,开始 时间,0.3,0.5,1,2,运行 时间,10.5,10.4,10.2,10,提交 时间,4,3,2,1,作业,短作业优先调度算法的特点,算法调度性能较好， 如上例中， 先来先服务 短作业优先 平均周转时间 2.8 2.45

16、 平均带权周转时间 5.25 3.85 但对长作业不利，未考虑作业的紧迫程度，运行时间为估计。,最短平均周转时间,当一批作业同时到达时，最短作业优先调度算法才能获得最短平均周转时间。 设一组作业p1、p2、pn，其运行时间为t1、t2、 、tn，且假定t1t2 tn，则短作业优先调度算法的总周转时间为： t1+（t1+t2）+ +（t1+ +tn） =n*t1+（n-1）t2+ +tn,最短平均周转时间（续）,可以证明：若a1 a2 an且b1b2 bn，则 a1bn+a2bn-1 +anb1 a1bi1+a2bi2 +anbin a1b1+a2b2 +anbn 其中i1、i2、 、in 是1

17、、2、 、n的一个排列。,3.优先级调度算法,在作业调度中，从后备作业队列中选择若干优先级高的作业调入内存。 在进程调度中，将处理机分配给就绪队列中优先级最高的进程。 优先级表示进程的重要性及运行优先性，通常用优先数来衡量。在某些系统中，优先数越大优先级越高；而在另一些系统中，优先数越大优先级越小。,按调度方式对优先级调度算法分类,非抢占式优先级调度算法：系统一旦将处理机分配给就绪队列中优先级最高的进程后，该进程便一直运行下去，直到完成或因发生某事件使该进程放弃处理机时，系统才将处理机分配给另一个更高优先级的进程。 抢占式优先级调度算法：将处理机分配给优先级最高的进程，使之运行。在进程运行过程

18、中，一旦出现了另一个优先级更高的进程时，进程调度程序就停止原运行进程，而将处理机分配给新出现的高优先级进程。,优先级的类型,优先级分为两种： 静态优先级 动态优先级,静态优先级,静态优先级是在创建进程时确定的，确定之后在整个进程运行期间不再改变。 确定依据有： 进程类型：系统进程，用户进程；前台进程高于后台进程（分时用户的响应时间） 进程对资源的需求：执行时间，资源数量 用户要求：紧迫程度（防止都设为高优先，可高优先级高收费） 特点：简单易行，系统开销小，但不精确。,动态优先级,动态优先级是指在创建进程时，根据进程的特点及相关情况确定一个优先级，在进程运行过程中再根据情况的变化调整优先级。 确

19、定原则有：占用CPU时间，等待时间。 例：优先数=CPU使用时间/2+基本优先数 CPU使用时间衰减函数: Decay(CPU使用时间)=CPU使用时间/2,4. 时间片轮转调度算法,时间片轮转法：系统将所有就绪进程按到达时间的先后次序排成一个队列，每次调度时把CPU分配给队首进程，并令其执行一个时间片。当时间片用完时，停止该进程的执行，将它送至就绪队列末尾等待下一次执行，然后再把处理机分配给就绪队列中的新队首进程。如此不断循环，直至完成为止。,时间片轮转算法例,设有A、B、C、D、E五个进程，其到达时间分别为0、1、2、3、4，要求运行时间依次为3、6、4、5、2，采用时间片轮转调度算法，当

20、时间片大小为1和4时，试计算其平均周转时间和平均带权周转时间。,时间片大小为1,A、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运

21、行，B等待；,18：B运行，D等待；,19：D运行，,0：A运行；,时间片为1的周转时间,平均周转时间 T=(7181417+8)/5=12.8 平均带权周转时间 W=(2.3333.53.4+4)/5=3.246,时间片大小为4,A、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、

22、17。,时间片为4的周转时间,平均周转时间 T=(318917+13)/5=12 平均带权周转时间 W=(132.253.4+6.5)/5=3.23,时间片大小的选择,若时间片太大，所有进程都能在一个时间片内完成，则时间片轮转算法退化为先来先服务； 若时间片太小，则进程调度频繁，系统开销增加。 因此时间片大小选择应适当。,确定时间片大小应考虑的因素,系统对响应时间的要求：响应时间=时间片*就绪队列中进程数，进程数一定，则时间片与系统响应时间成正比。 就绪队列中的进程数目：响应时间固定情况下，时间片与就绪进程数成反比。 系统处理能力：人所能承受的响应时间一定，系统速度快则时间片可增长。（通常常用

23、命令一个时间片处理完，计算机速度越快，时间片越短）,5. 高响应比优先调度算法,最高响应比优先调度算法是对短作业优先调度算法和先来先服务调度算法的一种综合。,响应比,响应比定义如下： 响应比作业响应时间/估计运行时间 由于响应时间为作业进入系统后的等待时间加上估计运行时间。因此 响应比1作业等待时间/估计运行时间,高响应比优先调度算法思想,在每次调度作业运行时，先计算后备作业队列中每个作业的响应比，然后挑选响应比最高者投入运行。 特点： 有利于短作业-等待时间相同，短作业优先， 考虑等待时间-运行时间相同，等待时间长的作业优先运行。,最高响应比优先算法例,设有A、B、C、D、E五个进程，其到达

24、时间分别为0、1、2、3、4，要求运行时间依次为3、6、4、5、2，采用最高响应比优先调度算法，试计算其平均周转时间和平均带权周转时间。,分析作业的调度顺序,A、B、C、D、E的到达时间依次为0、1、2、3、4，要求运行时间依次为3、6、4、5、2,0：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

25、81317+7)/5=9.6 平均带权周转时间 W=(11.333.253.4+3.5)/5=2.496,3.4,3.25,1.33,1,带权周转时间,17,13,8,3,周转 时间,20,15,9,3,完成 时间,15,11,3,0,开始 时间,5,4,6,3,运行 时间,3,2,1,0,提交 时间,D,C,B,A,作业,3.5,7,11,9,2,4,E,6.多级队列调度算法,实现思想：根据作业性质或类型不同，将进程就绪队列分为多个，每个队列采用不同的调度算法。每个进程固定属于一个队列。 例如：终端型作业为前台作业，批处理作业为后台作业。前台采用时间片轮转算法，后台采用先来先服务，前台作业的

26、优先级高。,7.多级反馈队列调度算法（1）,应设置多个就绪队列，并为每个队列赋予不同的优先级。第1个队列的优先级最高，第2队列次之，其余队列的优先级逐次降低。 每个队列中进程执行的时间片大小也各不相同，进程所在队列的优先级越高，其相应的时间片就越短。,多级反馈队列调度算法（2）,当一个新进程进入系统时，首先将它放入第1个队列的末尾，按先来先服务的原则排队等待调度。当轮到该进程执行时，如能在此时间片内完成，便可准备撤离系统；如果它在一个时间片结束时尚未完成，调度程序便将该进程转入第2队列的末尾，再同样地按先来先服务原则等待调度执行。如此下去，最后一个队列中使用时间片轮转调度算法。,多级反馈队列调

27、度算法（3）,仅当第1个队列为空时，调度程序才调度第2队列中的进程运行；仅当第1个至第（i1）个队列均为空时，才会调度第i个队列中的进程运行。 当处理机正在为第i个队列中的某进程服务时，若又有新进程进入优先级较高的队列中，则此时新进程将抢占正在运行进程的处理机，即由调度程序把正在执行进程放回第i个队列末尾，重新将处理机分配给新进程。,多级反馈队列调度算法示意图,就绪队列1,CPU,就绪队列2,就绪队列n,CPU,CPU,完成,完成,完成,多级反馈队列调度算法例,设有A、B、C、D、E五个进程，其到达时间分别为0、1、3、4、5，要求运行时间依次为3、8、4、5、7，采用多级反馈队列调度算法，系

28、统中共有3个队列，其时间片依次为1、2和4，试计算其平均周转时间和平均带权周转时间。,13：EE运行，BCD等待；,调度分析,A、B、C、D、E到达时间依次为0、1、3、4、5，要求运行时间依次为3、8、4、5、7,1：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=(9261718+21)/5=18.25 平均带权周转时间 W=(33.254.253.6+3)/5=3.42,多级反馈队列调度算法的性能,多级反馈队列调度算法能较好满足各类用户的需求： 终端型用户：大多能在一个时间片内完成，响应时间较短； 短批处理作业用户：能在前几个队列完成，周转时间较短； 长批处理作业用户：依次在1n队列中运行，不会长时间得不到处理。但是可能会“饥饿”，解决方法是提高在低优先队列中等了很长时间的进程的优先级。,