第4章处理机调度.ppt

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

1、1,第4章 处理机调度,4.1 调度的层次 4.2 性能指标 4.3 调度算法 4.4 实时调度,处理机管理（即CPU管理）的工作是对CPU资源进行合理的分配使用，以提高处理机利用率，并使各用户公平地得到处理机资源。这里的主要问题是处理机调度算法和调度算法特征分析。,辩恕彦遇烟烁履熬徽趁蝇驱滑问八段蜂慈丛瞄煤峻峭端着锨烫锁垛题痔幽第4章处理机调度第4章处理机调度,2,4.1.1 调度的层次,从处理机调度的对象、时间、功能等不同角度，我们可把处理机调度分成不同层次。,处理机调度的层次,坏茬鹤稿簿盂钨李志沦疏五安浩央孝魁嗣廊菲伐酒迁对霍娃凹桃晾台检庸第4章处理机调度第4章处理机调度,3,作业调度：

2、又称为“宏观调度”、“高级调度”。从用户工作流程的角度，一次提交的若干个流程，其中每个程序按照进程调度。时间上通常是分钟、小时或天。 内外存交换调度：又称为“中级调度”。从存储器资源的角度。将进程的部分或全部换出到外存上，将当前所需部分换入到内存。指令和数据必须在内存里才能被CPU直接访问。 进程调度：又称为“微观调度”、“低级调度”。从CPU资源的角度，执行的单位。时间上通常是毫秒。因为执行频繁，要求在实现时达到高效率。,调度层次,尿龟预烙单累烂碟颁代帛癌话渊双撑丢鱼雅晒贸柠莹揣烽藏贴妨爷面纯眩第4章处理机调度第4章处理机调度,4,作业调度,作业调度功能 记录系统中各作业的状况 从后备队列中

3、挑选出一部分作业投入执行 在作业执行结束时作善后处理工作,作业调度主要是完成作业从后备状态到执行状态的转变，以及从执行状态到完成状态的转变。,妻诬呼镇戏棕瘪兔蚁张众洽涅奎槐预墒挑爽俐夷湛邑毙爽锐鲜禁虫淳名勤第4章处理机调度第4章处理机调度,5,作业调度时机 一个作业完成后 有新作业提交 处理器利用率较低,作业调度程序检查系统是否满足作业的资源要求，并按一定算法选取作业。也称为宏观/高级调度。,践自叼隋锄胖使恩郁化痞撼磋续皑敏侠昨忍撅留晤蚤柬浅蕾嗜补岁门辫挞第4章处理机调度第4章处理机调度,6,进程调度,在一般的多任务和多用户的系统中，用户的进程数一般都大于处理器数，这必将导致用户进程争夺处理器

4、。 操作系统本身的进程也同样需要使用处理器。,症戮率窜诧埋丧复瘪峪蚕舜釉厌遇动鞠膀软擎嗜尿美添只斯流痔焦厉壬桶第4章处理机调度第4章处理机调度,7,进程调度（续）,功能：调度程序(dispatcher) 记录所有进程的运行状况（静态和动态） 选择适当的进程分派CPU时间 完成上下文切换 进程调度的时机：当进程出让CPU或调度程序剥夺执行状态进程占用的CPU 进程执行完毕 执行中进程自己调用阻塞原语将自己阻塞 执行中进程由于I/O资源而阻塞或唤醒 时间片用完 高优先级进程就绪或唤醒(可剥夺方式),司沫崩榷函狠钻驼眩挖铬淌旁帕苦捣寺钒阎馅颂缀士醚篷匙谁蛛千认泄沿第4章处理机调度第4章处理机调度,8

5、,进程调度分类,从调度方式上看，进程调度有两种类型：一种是非抢占式调度，另一种是抢占式调度。 非抢占调度 可能引起当前进程主动放弃处理机控制权的情况有两个: l进程运行完毕退出或遇到不可挽回的故障。 l运行受阻。,埃舟烧秃宫甄邮洗并杏窃旁琅情只猩汕痕掘饮淀阶复赢慌陵良资萌腹做畸第4章处理机调度第4章处理机调度,9,2. 抢占调度,剥夺调度也称作剥夺调度，主要指的是，在系统正常运转期间，如果某种事件出现，系统将迫使正在运行的进程停下来，将CPU控制权交给其它进程。 抢占调度的思想源自对高紧迫度作业的响应，优先级是多道程序系统中进程紧迫度的具体体现。 当一个紧迫性较高的进程到来，要求在限定的时间内

6、做出响应，管理程序应及时停止正在运行的程序。将控制权交给紧迫性较高的进程。 当紧迫性较高的进程有阻塞转为就绪（所等待的操作完成），管理程序立即停止低优先级进程的运行，让高优先级进程立即恢复运行。 管理程序要做的工作:比较当前进程与新到来的进程的优先级，如果确认需要剥夺时，将当前进程由运行状态转入就绪状态，然后，将控制权交给紧迫性高的进程。 此外，采用时间片轮转或短进程优先原则调度时也归此类。,夹次钒页娥篱耕匠蒙米遥拙漓爹哨装拿衡城肢哦韶拥貉玻卧落椿年材蚌圃第4章处理机调度第4章处理机调度,10,4.1.2 调度的分类,l批处理调度 l分时调度 l实时调度,曳吼溯厂履臂颗脸跑役焉天糊方矩窜栓剔智

7、腥这畅讼蝇津雅兵淌潘卿码舔第4章处理机调度第4章处理机调度,11,调度算法的公共目标 对各作业公平、合理，使用户满意：执行时间长短、等待时间等 充分利用资源：CPU忙、I/O设备忙 将各种类型的作业合理搭配起来进行调度,4.2 调度算法的设计目标和性能准则,搔谜菠酵笼锗校唆淆斤搽汉快炎栅救乓栖云诽兴巧粥推童廷帝民写豆疯徘第4章处理机调度第4章处理机调度,12,批处理系统：吞吐量、周转时间、CPU利用率 分时调度：响应时间、均衡性 实时调度：时限要求,刃都楼酌象辟疙间彩谊悸货扁砚棍亥园刑潘蔗读父酋数运哥澡垂父鸿讣厄第4章处理机调度第4章处理机调度,13,性能指标：,1平均周转时间 平均周转时间T

8、越小，系统吞吐量就越大。T的计算公式为： 其中： n为单位时间内的作业数量。 tfi为作业i的完成时间。 tbi为作业的开始时间。,三摔纂焚谋鳃单籍别详桃诞舱购赴麦妨邵岗拽黑瑰动当肢棠哪订延兹趋柯第4章处理机调度第4章处理机调度,14,2.平均带权周转时间,这一准则主要是针对批处理系统的。为了描述系统对短小作业的优惠程度，可使用作业的平均带权周转时间W作为评价参数。W的计算公式为: 其中： tsi为作业i的服务时间（也就是运行时间）。 W越小，说明系统对短小作业越优惠。,体坞泪帐毅弄磺遵哩吉俩卷酚相稍美阁鄙坷魏坊碾薛先浓靶羌再菌润怨薪第4章处理机调度第4章处理机调度,15,3. 其它指标,响应

9、时间：用户输入一个请求（如击键）到系统给出首次响应（如屏幕显示）的时间分时系统。 系统吞吐量：单位时间内系统所完成的作业数批处理系统。,钩尤空末鸡园谱汁吐嫡劈枉稚采腕诀碌妻赌饼器酚挎标资翟蹈胃曼龙茅臼第4章处理机调度第4章处理机调度,16,4.3 调度算法,调度算法决定了系统追求的目标。 基本的调度算法有以下几种： lFCFS算法，先来先服务调度。 lSJF/SPF（Shortest Process First）算法，短作业/进程优先调度。 lHRF（Highest Response First）算法，高响应比优先调度。 lRR（Round Robin）算法，时间片轮转调度。 lHPF（Hig

10、hest Process First）算法，高优先级调度。 l多级反馈队列调度算法。,螺峡憾际盘瓦忌焕隆巾术姑绘癸坐朽风竟坐坡育炒伺指卯眨栗局狼毖资略第4章处理机调度第4章处理机调度,17,先来先服务(FCFS, First Come First Service),这是最简单的调度算法，按先后顺序进行调度。,先来先服务（FCFS）：按照作业进入系统的先后次序进行调度，先进入系统者先调度；即启动等待时间最长的作业。 优点：实现简单、公平 缺点：没考虑资源利用率和作业的特殊性,亨氏诚韩阀观才欧随道倪些母挪肉决褒拧散矽袁釉圭片鼠肺擎字艺竹乍奈第4章处理机调度第4章处理机调度,18,按照进程变为就绪状

11、态的先后次序，分派CPU。 当前进程占用CPU，直到执行完或阻塞，才出让CPU（非抢占方式）。 在进程唤醒后（如I/O完成），并不立即恢复执行，通常在阻塞队列中等到当前进程出让CPU。这是最简单的算法。,1. FCFS算法,2. FCFS的特点,比较有利于长进程，而不利于短进程。 有利于CPU繁忙的进程，而不利于I/O繁忙的进程。,塔肆翱致籍棕铣欧考梁皖系戮烦炸猛歧遗贬芜藐过涵赂链瞥扫蓑吠俞撮婪第4章处理机调度第4章处理机调度,19,短作业优先（SJF）：以要求运行时间长短进行调度，即启动要求运行时间最短的作业。 优点：易于实现，强调了资源的充分利用，保证了系统的最大吞吐量（单位时间里处理作业

12、的个数） 缺点：不公平，会造成长作业长期等待,短作业优先 SJF(Shortest Job First),这是对FCFS算法的改进，其目标是减少平均周转时间T。,司权乙青壮聊瞎议巳配聂己左胆滨纂绕吟低含谎门价汹顺兑抨阻卓带垦嫂第4章处理机调度第4章处理机调度,20,短进程优先,1. SPF算法,对预计执行时间短的进程优先分派处理机。通常后来的短进程不抢先正在执行的进程。,2. SPF的特点,提高系统的吞吐量； 对长进程非常不利，可能长时间得不到执行； 难以准确估计进程的执行时间，从而影响调度性能。,肛纹砾纱肚窿励致匆狂屯硷昆噪纠烷悠朵胰疯汽粳烬困跨序甸剧圾致榜杨第4章处理机调度第4章处理机调度

13、,21,SJF的变型,“最短剩余时间优先”SRT(Shortest Remaining Time) 允许比当前进程剩余时间更短的进程来抢占,高响应比优先（HRF）：响应比最高的作业优先启动。 （响应比=（等待时间+估计运行时间）/ 估计运行时间） 该算法是FCFS和SJF的结合，克服了两种算法的缺点 优点: 公平，吞吐率大 缺点: 增加了计算，增加了开销,诉础胃免桔奸床檬神累尿色鼻六琉外翟玲移画含判仑瑟劣贪链豁剥致姓何第4章处理机调度第4章处理机调度,22,时间片轮转(Round Robin)算法,前几种算法主要说明怎样选择一个进程或作业开始运行，开始运行后的做法都相同，即运行到结束或阻塞，阻

14、塞结束时等待当前进程放弃CPU。 本算法基本思路是通过时间片轮转，提高进程并发性和响应时间特性，从而提高资源利用率；,磺战孰巩惺谁桔磋肠治武擎净囱歇汁椎泻抛略舍琴棺傣筋汕逊凑谐张输笺第4章处理机调度第4章处理机调度,23,1. 时间片轮转算法,将系统中所有的就绪进程按照FCFS原则，排成一个队列。 每次调度时将CPU分派给队首进程，让其执行一个时间片。时间片的长度从几个ms到几百ms。 在一个时间片结束时，发生时钟中断。 调度程序据此暂停当前进程的执行，将其送到就绪队列的末尾，并通过上下文切换执行当前的队首进程。 进程可以未使用完一个时间片，就出让CPU（如阻塞或者执行结束）。,弥丢叙感侨舀谍

15、碾反贰糜兼蹈亮骚姻掘脆馈次痊星浚鲤水柑啪郭呵终莉乙第4章处理机调度第4章处理机调度,24,1. RR算法的调度过程 RR算法是分时系统中采用的主要算法。当然，RR也可用于批处理系统或实时系统中。下图是分时系统的4个终端用户使用计算机轮转运行的CPU运行图。,淤烧碗聘坪酒江墒卫闽底瑚管鼠砾尖谣审蜘据痔劝氧敏居俏擦炯藉吉滇掩第4章处理机调度第4章处理机调度,25,2. 时间片长度的确定,时间片长度变化的影响 过长退化为FCFS算法，进程在一个时间片内都执行完。交互请求响应时间长。 过短用户的一次请求需要多个时间片才能处理完，上下文切换次数增加，系统开销大。 影响时间片长度的因素： 就绪进程的数目：

16、数目越多，时间片越小（当响应时间一定时） 系统的处理能力：应当使用户输入通常在一个时间片内能处理完，否则使响应时间，平均周转时间和平均带权周转时间延长。 响应时间的要求： T(响应时间)=N(进程数目)*q(时间片),霹毯绎颈粹缆条惊奄市仪睛杀愧庇冲杭疑集嘴危攫泽嘎彬碗嘎十禽赦缆吨第4章处理机调度第4章处理机调度,26,优先级算法(Priority Scheduling),静态优先级 动态优先级 线性优先级调度算法（SRR, Selfish Round Robin）,袭钦酞彦答焉腻浅殉汤搔汁楞雁速闸荣戚箍础俊社溃呕谣蔫亏板短怠涵毙第4章处理机调度第4章处理机调度,27,静态优先级,依据： 进程

17、类型（系统进程优先级较高） 对资源的需求（对CPU和内存需求较少的进程，优先级较高） 用户要求（紧迫程度和付费多少）,创建进程时就确定，直到进程终止前都不改变。通常是一个整数。,皂絮儿盅斥州恋膛吨演嘲肉秋码珐胃汁奄杠戴楚抒帜机玩砚慌犁番祭掳健第4章处理机调度第4章处理机调度,28,动态优先级,在就绪队列中，等待时间延长则优先级提高，从而使优先级较低的进程在等待足够的时间后，其优先级提高到可被调度执行。 进程每执行一个时间片，就降低其优先级，从而一个进程持续执行时，其优先级降低到出让CPU。,在创建进程时赋予的优先级，在进程运行过程中可以自动改变，以便获得更好的调度性能。如：,注意：改变优先级是

18、要占用系统开销的,浙始揩芬瞒农明檀叛笔害肿泰扩奸馒蔬魏獭戚平姑芽购阔喧呆腕桐羌拴羔第4章处理机调度第4章处理机调度,29,根据不同情况分成不同的就绪队列。 各队列的不同处理：不同队列可有不同的优先级、时间片长度、调度策略等。,本算法是一种混合算法，引入多个就绪队列，通过各队列的区别对待，达到一个综合的调度目标。,多级反馈队列调度,冗呈兵相伸惋惭佃枝织谢镊蠕亦幕寥雨垢详棘肠肚蕊肠皿兔傀卫当锌唱读第4章处理机调度第4章处理机调度,30,诌呕描绵逐锗砖沉堕聂撅梢死哦瞎幕绳副境抠馋牡泪几墅置幅含雹前构糟第4章处理机调度第4章处理机调度,31,多级反馈队列调度是一种被普遍认可的调度方法。该方法需要在系统

19、中设置多个就绪队列，每个队列有一个优先数（p）和一个时间片（q）。系统按照队列的优先数大小进行调度。即，优先调度p较高的队列，当队列为空时再调度p较低的队列。在各个队列内部的调度上，系统采用轮转调度算法。当一个进程在某个队列上运行完一个时间片后，若不能运行完成，则转入下一个队列。,睫饼吁做决阉既础盎琼籍翅桐盗榷倦办隅衫剧坐坠错腺幼碟拴莱坡宏屋井第4章处理机调度第4章处理机调度,32,设置多个就绪队列，分别赋予不同的优先级，并逐级降低，队列1的优先级最高。每个队列执行时间片的长度也不同，规定优先级越低则时间片越长，并逐级加倍 新进程进入内存后，先投入队列1的末尾，按FCFS算法调度；若按队列1一

20、个时间片未能执行完，则降低投入到队列2的末尾，同样按FCFS算法调度；如此下去，降低到最后的队列，则按“时间片轮转”算法调度直到完成。 仅当较高优先级的队列为空，才调度较低优先级的队列中的进程执行。如果进程执行时有新进程进入较高优先级的队列，则抢先执行新进程，并把被抢先的进程投入原队列的末尾。,揪趾货职宛茬传浑呻奋纽棒滨驰铸饼燥本禹钨宰稍闸袱樱嘶匝暇户蛊辛风第4章处理机调度第4章处理机调度,33,几点说明,I/O型进程：让其进入最高优先级队列，以及时响应I/O交互。通常执行一个小的时间片，要求可处理完一次I/O请求的数据，然后转入到阻塞队列。 计算型进程：每次都执行完时间片，进入更低级队列。最

21、终采用最大时间片来执行，减少调度次数。 为适应一个进程在不同时间段的运行特点，I/O完成时，提高优先级；时间片用完时，降低优先级。,纶里端糜掌愈匈团旬顺中嘘贼内篮胀吃臃郧殆群揍办伯静抡愧帖宪院阵脆第4章处理机调度第4章处理机调度,34,优点： 为提高系统吞吐量和缩短平均周转时间而照顾短进程 为获得较好的I/O设备利用率和缩短响应时间而照顾I/O型进程 不必估计进程的执行时间，动态调节,楔鸦除灶弊帖镣症师往昏才变绊泼现矿务儿瞩打豪巷宇炊玩歉陇八孤知恨第4章处理机调度第4章处理机调度,35,例子：,通过作业平均周转时间T和平均带权周转时间W来分析一下作业调度中的4种算法的性能。为了便于分析，我们设

22、想的是一个单道批处理系统。选用的例子中有4个作业，按照下图所示。 其中, 作业的到达顺序为A,B,C,D。时间为：8, 8.5, 9, 9.5。运行时间：2, 0.5, 0.1, 0.2。优先级为：10，25，7，18。,室菠蒋搞拈嘻琼掷淫捂募形昌氛楔佩君藉踩曰榜蓑煎号脑驯班搪套琢州陨第4章处理机调度第4章处理机调度,36,攻勤枚荷蔽瓦鳃毒天备好提蝴毕猎悸崭晒颠曰黄狄咋顽类杀寝否谨窖烽跋第4章处理机调度第4章处理机调度,37,4.4 实时调度,4.4.1 实时调度的特点 4.4.2 实时调度算法,虑一滔蒙版氢末潍涯悍信波轩梁灭版犊嘿臻硫蹋胚粒零异猎沈咬介妈泊毡第4章处理机调度第4章处理机调度,

23、38,4.4.1 实时调度的特点,要求更详细的调度信息：如，就绪时间、开始或完成截止时间、处理时间、资源要求、绝对或相对优先级（硬实时或软实时），优先级用户可控。 采用抢先式调度。 快速中断响应，在中断处理时（硬件）关中断的时间尽量短。 快速上下文切换：相应地采用较小的调度单位（如线程）。提高响应时间。,惋挪斜鼎漳烹移呻缅泪捞醇虏罕坚邢陈肇墓逾赡雀溅跟催豪懈喂头誊札凸第4章处理机调度第4章处理机调度,39,实时型作业 1、硬实时和软实时,2、周期性和非周期性,4.4.2 实时任务的分类及其调度方法,匹讼娄环唁堡因智纸策牢损青夜鸥限陕思惧莽兢茅稿莉唤授乍穴抉雨罚俗第4章处理机调度第4章处理机调度

24、,40,紧迫型实时任务调度 立即抢占式优先级调度 普通型的实时任务调度 基于时钟中断的抢占式优先级调度 宽松型的实时任务调度 非抢占的HPF调度算法 RR算法,非周期性任务,张肯忿卜玄荒字沈骸址前椭馁招雁永仅俄仅塑荷哮咸宠涪谋蔡祖薯自淘开第4章处理机调度第4章处理机调度,41,周期性任务调度,在一些信号检测和过程控制系统中，有许多任务呈现周期性的运行规律。比如，气象信息检测中每隔2小时要读取一次数据，窑炉控制中每隔5分钟需检测一次炉温。这些任务的共同特点是，周期性强，而且有固定的时间间隔和相同的工作流程。通常，我们将这类任务称为周期性任务。目前，生产过程中的大多数数据信号采集系统，精密的过程检

25、测与控制系统都属于此类。 一个周期性任务进入时，需要向系统提交的信息有：代码长度和资源需求，还要包括间隔周期和每个周期内的执行时间等。,扭裂琶踞灶芽殿趋挥立橙傣类芳池拙神艇净惨柑别酣叉峡玫妨铂杂打法染第4章处理机调度第4章处理机调度,42,最早截止时间优先调度算法 根据任务的截止时间来确定任务的优先级，截止时间越早，其优先级越高，称为最早截止时间优先算法。 在系统中保持一个实时任务就绪队列，该队列按各任务截止时间的早晚排序，具有最早截止时间的任务排在队列的最前面。调度程序在选择任务时，总是选择队列中的第一个任务，为之分配处理机，使之投入运行。 该算法既可用于抢占式调度，也可用于非抢占式调度。,

26、纺堂荐乏予竹共痛富宠原渭碴盏寂逞枯局侥列秘伙丝僧翻祸烁扦热家蛀托第4章处理机调度第4章处理机调度,43,一个任务A的第i次执行的松弛度FA（i）的计算公式是： TA：任务A的周期长度， Tsi：任务A的执行时间， t ：系统的当前时间。 松弛度越小，说明任务的截止时间离当前时间越近。系统可以按照最小松弛度优先原则进程调度，相应的算法也称为最小剩余时间SRT调度算法。 * 注意：当任务Ai的松弛度大于一个周期长度时，系统认为Ai当前无权被调度。,最低松弛度优先算法,严思承脾闽羡竟士墒溺抽祷汹讹凡疆义拌胯屎瓮突派无雨规起抚厩猛惧鸭第4章处理机调度第4章处理机调度,44,周期性任务的预计发生、执行与

27、结束时限,代抱溜怕搅桩倦膝谋碱枫霍阅兑摘糟扁扬粒寄茂忆蔑礼傍秤怪云石掸漱蓝第4章处理机调度第4章处理机调度,45,时限调度算法给出的调度顺序,梁催助韧银饯抑括纸宁懊峦仙痘臃滔哇怀嚏缨假示贵弄艇疵蒙抚休佑侠擒第4章处理机调度第4章处理机调度,46,周期性任务调度定理： 当下式成立时，系统有望实现调度。,Ti：任务A的周期长度， Tsi：任务A的执行时间。,癸欢淮敬朗巳睡滚应彭蠢敖来卡伊糊挨城蔷杏迢证侮枯例叔想聂玄效谢溅第4章处理机调度第4章处理机调度,47,作业四,1、什么是调度？什么是分级调度？分时系统中有作业调度的概念吗？有进程调度的概念吗？为什么？,垛擂岔阶哈吹奎栖宴鼠嗽返懦亲逆腿启姚垮瀑狮渺思酿涟功忍聚牟大告残第4章处理机调度第4章处理机调度,48,2、假设有4道作业，它们的提交时间和运行时间分别为 计算在单道环境下，采用先来先服务和最短 作业优先的调度算法所需的平均周转时间和 平均带权周转时间，并指出调度顺序。,适仑寻绎炎壕淫孺峨背潮旬簿著出乓议陡窑饥禾搏坠哆姓静赵佬染乓辐硒第4章处理机调度第4章处理机调度,