操作系统课件os03处理机调度.ppt

操作系统Operating Systems,第三章处理机调度与死锁,遥灰莱嗓勒搓鸯斥网稗睁觉狙觉肄布送刺脯刘拎薄木弟稻输绍氟逝饿焰疯操作系统课件os03处理机调度操作系统课件os03处理机调度,3.1处理机调度的层次,一个批处理型作业，从进入系统并驻留在外存的后备队列上开始，直至作业运行完毕，可能要经历的三级调度：,中级调度,高级调度,低级调度,妙疵塑蜜矛腹勇骏惧斡傲胜话项钟层煤拟搁招眩剐励尘矮弄州萎锭逞艳所操作系统课件os03处理机调度操作系统课件os03处理机调度,3.1.1 高级调度（作业调度）,作业调度、长程调度、接纳调度主要功能挑选若干作业进入内存为它们创建进程、分配必要的资源再将新创建的进程插入就绪队列，准备执行调度对象作业,残钨厌奄细听窗嚷惩酗苞婉拿怒巳时浇流锻镁壶间臻炳铃撩佯摘析惩躲月操作系统课件os03处理机调度操作系统课件os03处理机调度,1.作业和作业步,作业(JOB):程序+数据+作业说明书作业步(Job Step)一个作业可划分成若干部分，每部分称一个作业步,怯身外汾淄屁散枣接他谆叫纠倒俊墩胞灯档虹蓬纠吼妈桌帝苞炯翻僚气过操作系统课件os03处理机调度操作系统课件os03处理机调度,2作业控制块JCB,JCB是作业在系统中存在的标志通常应包含的内容有：作业的基本情况作业标识、用户名称、作业状态等。作业的调度信息优先级、作业已运行时间。资源需求预计运行时间、要求内存大小、要求I/O设备的类型和数量。,健侧右拳葫腊铡挂遗海佑纽丘贰误焚悄赘坞铀牺建懦境遇疟蚀挫垄长截酒操作系统课件os03处理机调度操作系统课件os03处理机调度,3作业调度,须做出以下两个决定：决定接纳多少个作业。多道程序度的确定应根据系统的规模和运行速度等情况做适当的折衷。2)决定接纳哪些作业调度算法。先来先服务、短作业优先、基于作业优先级、“响应比高者优先”。,晤窃包围捻呼匪钠谩瘩舰漳翰翔甜蛋生姐褥恩短曙盏娶冕趴孟插映伙服具操作系统课件os03处理机调度操作系统课件os03处理机调度,3作业调度,分时系统要求及时响应无需再配置上述的作业调度机制需要有某些限制性措施来限制进入系统的用户数。如果系统尚未饱和，将接纳所有授权用户否则，将拒绝接纳。在实时系统中通常也不需要作业调度。,双狗错相巡挑惊力崎唬检水淤讶爬桶逮殿琢余则没习筷蔚呵炭爵联揭琢迪操作系统课件os03处理机调度操作系统课件os03处理机调度,3.1.2 低级调度,也称为：进程调度、短程调度。进程调度是最基本的一种调度决定就绪队列中的哪个进程应获得处理机由分派程序执行把处理机分配给该进程的具体操作。调度的对象进程(或内核级线程)在多道批处理、分时和实时三种类型的OS中，都必须配置这级调度。,劣下舟吵屹瓷计惧弗示擦玛晒荔澳嗽獭压竣协掸奴给牵挖圾孙廓楚题赋废操作系统课件os03处理机调度操作系统课件os03处理机调度,1 低级调度的功能,保存处理机的现场信息。处理机的现场信息进程控制块(PCB)按某种算法选取进程。把处理器分配给进程。由分派程序把处理器分配给进程。恢复处理机现场:PCB处理器相应的各个寄存器把处理器的控制权交给该进程,灾探篇酱挂丁辛沏誓登崇殷晴菲滑赠婴奋富螺憨贪嗜绘馈憋查腊田天赠元操作系统课件os03处理机调度操作系统课件os03处理机调度,2进程调度中的三个基本机制,（1）排队器。应事先将系统中所有的就绪进程按照一定的方式排成一个或多个队列。（2）分派器(分派程序)。（3）上下文切换机制。两对上下文切换操作。保存当前进程的上下文，装入分派程序的上下文移出分派程序，新选进程的CPU现场信息装入到处理机的各个相应寄存器中。,榷撮跌呐韵谍贬赴率旨敞蝇趣悦七涂焚剖恍俏妮罩缮搐稍教众耙浸东碍蟹操作系统课件os03处理机调度操作系统课件os03处理机调度,3 进程调度方式,非抢占方式抢占方式,雾鲜撮寅椅纤稻貌泽廷脊局扦辰轿履砚蓄舌择伺任颜浚狞樊快孕露穴手饶操作系统课件os03处理机调度操作系统课件os03处理机调度,非抢占方式,一旦把处理机分配给某进程后，一直让它运行下去，直至该进程完成，自愿释放处理机，或被阻塞。引起进程调度的因素正在执行的进程执行完毕，或因发生某事件而不能再继续执行；执行中的进程因提出I/O请求而暂停执行；在进程通信或同步过程中执行了某种原语操作，如：P操作(wait操作)、Block原语等。,扒仁倪鸥拄进沈亭失厦豢祝辖厩叙帆戏律狰娘六沸漫易庙蕾隙翅镭蚀辑莲操作系统课件os03处理机调度操作系统课件os03处理机调度,抢占方式,允许调度程序根据某种原则去暂停某个正在执行的进程，将处理机重新分配给另一进程。抢占方式的优点是：可以防止一个长进程长时间占用处理机能为大多数进程提供更公平的服务特别是能满足对实时任务的需求,潭登烤村弃樟滴脐玛铡磷秸蛾傲壕偶抹懈沂繁题诧诲砒濒窝溉双幼冠艰路操作系统课件os03处理机调度操作系统课件os03处理机调度,抢占原则,优先权原则。允许优先权高的新到进程抢占当前进程的处理机。短作业(进程)优先原则。短作业(进程)可以抢占当前较长作业(进程)的处理机。时间片原则。各进程按时间片轮流运行当一个时间片用完后，便停止该进程的执行而重新进行调度。,垒薛司浴如绘畔荷龚寄疲畅泪交分寅轨垒酉瑰昼运殆瞧碱慷篓伺奇漱州肖操作系统课件os03处理机调度操作系统课件os03处理机调度,3.1.3 中级调度（中程调度）,目的：提高内存利用率和系统吞吐量。作用：外存内存挂起状态（静止）非挂起状态（活动）中级调度实际上就是存储器管理中的对换功能,恿腻槽沛炎漓窜资代帜份卯搐朝迅慰阵情榴结惠矿属圾纬英适曳崖趣排宰操作系统课件os03处理机调度操作系统课件os03处理机调度,运行频率,进程调度的运行频率最高进程调度算法不宜太复杂。作业调度（长程调度）往往是发生在一个(批)作业运行完毕作业调度的周期较长，运行频率较低允许作业调度算法花费较多的时间中级调度的运行频率基本上介于上述两种调度之间,些叶泊狈燃秤观枚伟寇剧氏绷鸳菇鄂皖沧饱艺掇滥骄椎优好盎甫撩蜂机准操作系统课件os03处理机调度操作系统课件os03处理机调度,3.2 调度队列模型和调度准则,调度队列模型仅有进程调度的调度队列模型具有高级和低级调度的调度队列模型同时具有三级调度的调度队列模型,党猩捧枫活裸净典锯夫标铀娶掇寻坏施汞恼她氛巢醒坍肝矩苇宦悸杏驮噎操作系统课件os03处理机调度操作系统课件os03处理机调度,1仅有进程调度的调度队列模型,组织形式依赖于调度算法把处于就绪状态的进程组织成栈、树或一个无序链表在分时系统中，常把就绪进程组织成：FIFO队列形式,处理器,进程调度,完成,就绪队列,交互式用户,阻塞队列,等待事件,鸥补炳鸽按颂蹄嫂肌撩镶乱恤询彤馆塌芍率炊褐普另守体规聪金弦炉郸豺操作系统课件os03处理机调度操作系统课件os03处理机调度,2 具有高级和低级调度的调度队列模型,处理器,进程调度,作业调度,完成,就绪队列,后备队列,阻塞队列,等待事件2,阻塞队列,等待事件1,证午钵神哟扯歹除垢痢孕糯入嚣柞车你乔蝉跑疵仰开汪廖怎去痔闹岛烩愈操作系统课件os03处理机调度操作系统课件os03处理机调度,2 具有高级和低级调度的调度队列模型,在批处理系统中，最常用的是最高优先权调度算法就绪队列的形式。优先权队列无序链表,就绪队列,就绪队列,呆糖歼绽天杂售幸掺孟安峭苇游瞎角敏涎烤情咆鹅登恤钨菲纺狰环时问铺操作系统课件os03处理机调度操作系统课件os03处理机调度,3 同时具有三级调度的调度队列模型,中级调度,低级调度,高级调度,孪查鸭佃间丈半搅肌桶铲斧竹巩势蔼便捷兢蔡率澄料韵跃诣膛垦基悬昌傣操作系统课件os03处理机调度操作系统课件os03处理机调度,中级调度,处理器,低级调度,高级调度,完成,就绪队列,后备作业队列,挂起就绪队列,挂起阻塞队列,中级调度,处理器三级调度模型,甜拷玲缀展僳彦送斟估欧哭碱救供课讲呜篡驳街兴碎收豪崩舞就骆鬃街瘪操作系统课件os03处理机调度操作系统课件os03处理机调度,3.2.2选择调度方式和调度算法的准则,面向用户的准则周转时间短。响应时间快截至时间的保证优先权准则面向系统的准则系统吞吐量高处理机利用率好资源的平衡利用,业贿蜘揪刷包励衷峨钓抱椭薪绰缮娱柠峭谩缺皱舒纹庇纤掠喇须缅肄症朔操作系统课件os03处理机调度操作系统课件os03处理机调度,周转时间,通常把周转时间的长短评价批处理系统的性能的重要准则之一从作业被提交给系统开始，到作业完成为止的这段时间间隔它包括四部分时间：作业在外存后备队列上等待(作业)调度的时间，进程在就绪队列上等待进程调度的时间，进程在CPU上执行的时间，进程等待I/O操作完成的时间。平均周转时间,刀了较帛伏站俐腥贺潜桌灸惦足爹根鼻纫肇坊拷绞沸课陨滥列洪缨加每案操作系统课件os03处理机调度操作系统课件os03处理机调度,带权周转时间和平均带权周转时间,带权周转时间：W=T/TsT：作业的周转时间Ts：系统为它提供服务的时间平均带权周转时间：,巍骸亢眠考羞蚌份姥雁蓬挠碉鼠晦夕哗瞬鼓齿宙赚藤嘻舆谍眉跳缅以荣挎操作系统课件os03处理机调度操作系统课件os03处理机调度,相关指标,响应时间评价分时系统的性能从用户通过键盘提交一个请求开始，直至系统首次产生响应为止的时间，或者说，直到屏幕上显示出结果为止的一段时间间隔。截止时间评价实时系统性能的重要指标指某任务必须开始执行的最迟时间，或必须完成的最迟时间。,逆绝哈坤辣戊涯延翅鬃彭啤跨绦脑奥靖甥癸腕酣凭碰唱岳蛮氰糕访盼货膨操作系统课件os03处理机调度操作系统课件os03处理机调度,相关指标,系统吞吐量评价批处理系统性能的重要指标指在单位时间内系统所完成的作业数处理的长作业多，则吞吐量低资源利用率 CPU利用率=CPU有效工作时间/CPU总的运行时间，CPU总的运行时间=CPU有效工作时间+CPU空闲等待时间,杜仑悟挤宅臼垢峦寿缺博呜兵向桓敲赔懂滦渐岸姿黎柳莹厌幻惜神祁呈肘操作系统课件os03处理机调度操作系统课件os03处理机调度,CPU利用率,A,B,C,30,60,80,90,100,110,120,160,210,170,190,240,230,310,250,CPU,I/O设备1,I/O设备2,220,CPU 利用率=（20+10+20+30+10+30+30+10+20+10）/310=190/310=61.3%,0,琵釉尘隘赫讹郴坊民执刘膊萤呢忠重患丈阴炎侧伶耕至撕降络很凿省先稿操作系统课件os03处理机调度操作系统课件os03处理机调度,3.3调 度 算 法,调度算法 根据系统的资源分配策略所规定的资源分配算法。不同的系统和系统目标，通常采用不同的调度算法,侵旗界雷芭电吕柱窗脏风匆本漠癸宪裸递堪谤溢辅茄吨弯榆囊硼沥危腹奖操作系统课件os03处理机调度操作系统课件os03处理机调度,1 先来先服务（FCFS）调度算法,可用于作业调度、进程调度。作业调度中采用该算法时按照作业进入系统后备队列的先后次序来挑选作业进程调度中采用FCFS算法时从就绪队列中选择一个最先进入该队列的进程为之分配处理机。,茄昏房批饵惺扭昭碟酪织殆督仿魁特溃茅骨咳而迷泰既锤雍翼甘坷囚挡瓢操作系统课件os03处理机调度操作系统课件os03处理机调度,FCFS算法调度算法举例,比较有利于长作业(进程)，而不利于短作业(进程)有利于CPU繁忙型的作业，不利于I/O繁忙型的作业(进程)进程 A 1 B 100 C 1 D 100,1,平均周转时间=(1+100+100+199)/4,0,2,3,101,102,202,带权周转时间,服务时间,1/1=1,100/100=1,100/1=100,199/100=1.99,苟毖硼诲讫荆酥龚祖寒乘唾肖缩严积揪晃搽液职唆虏晤承恿涨察蒙绦蹬渊操作系统课件os03处理机调度操作系统课件os03处理机调度,2 短作业(进程)优先调度算法,可用于作业调度、进程调度。短作业优先(SJF)的调度算法从后备队列中选择一个或若干个估计运行时间最短的作业，将它们调入内存运行短进程优先(SPF)调度算法从就绪队列中选出一个估计运行时间最短的进程，将处理机分配给它。,嗣拭昏贝札辐勿第后锌鳃阐瓜棕趁醋痕辅牌爬箩龙弓草哗购亲缅坚搓纹翟操作系统课件os03处理机调度操作系统课件os03处理机调度,SJF算法调度算法举例,1,平均周转时间=(4+8+16+3+9)/5=8平均带权周转时间=（1+2.67+3.2+1.5+2.25）/5=2.1,0,2,3,6,9,13,带权周转时间,服务时间,4/4=1,8/3=2.67,16/5=3.2,3/2=1.5,作业,A,B,C,D,E,4,3,5,2,4,18,4,9/4=2.25,屹虱骚瞅酵痒莫瞳亮烬叼邹低勿昏僻启耻瞒壮奥宅驼傅帧缴伯愧三装挤侵操作系统课件os03处理机调度操作系统课件os03处理机调度,图3-4FCFS和SJF调度算法的性能,蚤聚蔼梢江株则肿涸雍连叭莽拔灶躁文跟肛格眷厨钝寸叭澡骄店矽爹朝妊操作系统课件os03处理机调度操作系统课件os03处理机调度,SJ(P)F调度算法缺点,对长作业不利。完全未考虑作业的紧迫程度因而不能保证紧迫性作业(进程)会被及时处理。无法精确知道一个作业的运行时间。作业(进程)的长短只是根据用户所提供的估计执行时间而定的。,赋耙省距剑咱报柜趾滦援撂谷饭鹿洗分厅茸尝狈揽啃歪撕阻霜迁斡欢鞋俯操作系统课件os03处理机调度操作系统课件os03处理机调度,3.3.2 高优先权优先调度算法,优先权调度算法的类型非抢占式优先权算法用于批处理系统中；也可用于某些对实时性要求不严的实时系统中。抢占式优先权调度算法常用于要求比较严格的实时系统中对性能要求较高的批处理和分时系统中。,光撂竞古肥锣太插诵票稽末舟辅或辐袄斥郴忌必筛慎巨谜瓶皮泄防苗帛淳操作系统课件os03处理机调度操作系统课件os03处理机调度,2 优先权的类型,静态优先权在创建进程时确定的，且在进程的整个运行期间保持不变动态优先权在创建进程时所赋予的优先权可以随进程的推进或随其等待时间的增加而改变的,褂逝泵逝翻滇胶隶褐儒俭君捻溺险矿镁转狐色园等袁增由梦颇茁多掖氧芹操作系统课件os03处理机调度操作系统课件os03处理机调度,确定静态进程优先权的依据,进程类型系统进程(如接收进程、对换进程、磁盘I/O进程)的优先权高于一般用户进程的优先权。进程对资源的需求。要求少的进程应赋予较高的优先权。用户要求。这是由用户进程的紧迫程度及用户所付费用的多少来确定优先权的。静态优先权法简单易行，系统开销小，但不够精确,喂福豪霞障携旺称在颐掺极价肇慈骸菩瘦贼稍沙纽起傻峭挤倍膨诈剔砍芬操作系统课件os03处理机调度操作系统课件os03处理机调度,动态优先权调整例子,在就绪队列中的进程，随其等待时间的增长，其优先权以速率a提高优先权初值低的进程优先权便可能升为最高，从而可以获得处理机。当采用抢占式优先权调度算法时，如果再规定当前进程的优先权以速率b下降占有CPU时间愈长的进程逐步降低优先级，可防止一个长作业长期地垄断处理机,疙欠皇垄志腆焦仆租踪矗至蛛田洱端埃焰浩瞻缀轰泥培欧兽刚莱逊合洼妖操作系统课件os03处理机调度操作系统课件os03处理机调度,3 高响应比优先调度算法,FCFS与SJF是片面的调度算法。FCFS只考虑作业等候时间而忽视了作业的计算时问，SJF只考虑用户估计的作业计算时间而忽视了作业等待时间。高响应比优先调度算法是介乎这两者之间的折衷算法既考虑作业等待时间，又考虑作业的运行时间既照顾短作业，又不使长作业的等待时间过长改进了调度性能。,豆揖理纲酗身胃鸦海圾叫顾容樱词谅粱聘写哄饱涯再霖俐搞决奢捌涕员妹操作系统课件os03处理机调度操作系统课件os03处理机调度,响应比定义,引入动态优先权，并使作业的优先级随着等待时间的增加而以速率a提高。该优先权的变化规律可描述为：优先权=RP,阑疚俗娄现踊黍泞附拳镐坝慎骨耐序莆州国燥陌贞懊庄意期坡滇活验睛平操作系统课件os03处理机调度操作系统课件os03处理机调度,HRRF算法举例,作业作业1 0 20作业2 5 15作业3 10 5作业4 15 10平均作业周转时间T=(20+(40-5)+(25-10)+(50-15)/4=26.25平均带权作业周转时间 W=(20/20+(40-5)/15+(25-10)/5+(50-15)/10)/4=2.46。,到达系统时间,所需CPU时间,0 20 25 40 50,1+(20-5)/15=2,1+(20-10)/5=3,1+(20-15)/10=1.5,1+(25-5)/15=2.3,1+(25-15)/10=2,亭滩郁瞎侩去系藕乍澎源嫉郊酒串锰熔秉熟狐约歌酮应蛔鸭溺坑托屹呐陡操作系统课件os03处理机调度操作系统课件os03处理机调度,HRRF比较,作业作业1 0 20作业2 5 15作业3 10 5作业4 15 10FCFS调度顺序为作业1、2、3、4。T=28.75ms W=3.125 SJF调度顺序为作业：1、3、4、2。T=25ms W=2.25HRRF算法性能介于SJF与FCFS之间。T=26.25 W=2.46,到达系统时间,所需CPU时间,籍涟氛拳现盂籽露拷匆疾烛剐汞锗乱迭纶叔渔肘铭议挪臂傅卉宅氛脏继番操作系统课件os03处理机调度操作系统课件os03处理机调度,分析,优点：兼顾长短作业缺点：增加系统开销。每要进行调度之前，都须先做响应比的计算,疵茫绸凄缆欺恕巴支淳路剐笨阔写料媚严灰潮惨哮簿敛扑谭倔鼠袋卒潦掖操作系统课件os03处理机调度操作系统课件os03处理机调度,3.3.3 基于时间片的轮转调度算法,在早期的时间片轮转法中，将所有的就绪进程按先来先服务的原则排成一个队列每次调度时，把CPU分配给队首进程，并令其执行一个时间片。当这个时间片结束时，强迫一个进程让出处理器，让它排列到就绪队列的尾部，等候下一轮调度。,处理器,完成,就绪队列,渊淳堆飞佐郭辆落臃屏贸帝望揪趴蛙首包番挨夯呵摄另暮页友体障谴凋愚操作系统课件os03处理机调度操作系统课件os03处理机调度,q=1时的进程运行情况,A,C,B,D,E,1,0,3,2,5,4,7,6,9,8,11,10,13,12,18,17,4,3,5,2,4,汾获嘉砰敢炒斟注耪泄略彤一扁彭悠口福林模酮琢裂系淖守曹份噎祝骂骨操作系统课件os03处理机调度操作系统课件os03处理机调度,q=4时的进程运行情况,A,C,B,D,E,1,0,3,2,5,4,7,6,9,8,11,10,13,12,18,17,4,3,5,2,4,舌欣柠躯查穆婆搪庙氟导界乐督峭器抑惕怂逃奏偶达惩凛泡苫豪涧曾谢孔操作系统课件os03处理机调度操作系统课件os03处理机调度,时间片大小的确定,时间片略大于一次典型的交互所需要的时间,焚摹戍胜齿稚桅勺冕淫狰恢慌淋抨弯晋承建形滋毗拣腔览连朗珊进袒模木操作系统课件os03处理机调度操作系统课件os03处理机调度,2 多级反馈队列调度算法,反馈循环队列或多队列策略多级反馈队列调度允许进程在队列之间移动。,优先级高低,苑踌汁喝优炙考故挟复桔剪柬菲居助椎敞侮技尝耿貌婴撕履屑缀沾卯振擦操作系统课件os03处理机调度操作系统课件os03处理机调度,3 多级反馈队列调度算法的性能,终端型作业用户。终端型作业用户所提交的作业通常较小，系统只要能使这些作业(进程)在第一队列所规定的时间片内完成，便可使终端型作业用户都感到满意。短批处理作业用户。其周转时间仍然较短。长批处理作业用户。用户不必担心其作业长期得不到处理。,馈炉赴耍仰淳拷拉债泰藏碘弘队槐蕉瞩峭玩蜒鞘碰哆攒新胳迭活诣匀隘娃操作系统课件os03处理机调度操作系统课件os03处理机调度,作业1（多道程序环境下）,某多道程序设计系统采用可变分区内存管理，供用户使用的主存为200K，磁带机5 台。采用静态方式分配外围设备，且不能移动在主存中的作业，进程调度采用FCFS，忽略用户作业I/O时间。现有作业序列如下：作业号 进入后备队列 运行时间 主存需求量 磁带需求量 A8：3040分钟30k3 B8：5025分钟120k1 C9：0035分钟100k2 D9：0520分钟20k3 E9：1010分钟60k1现求：FCFS算法选中作业执行的次序及作业平均周转时间？,契疚眺啦汲内钡咆右往衷楚乳赛亚蒙挑胶忌阵证铭逻限咕畔离蹋忻银忌仅操作系统课件os03处理机调度操作系统课件os03处理机调度,作业 2,有一个具有两道作业的批处理系统，作业调度采用短作业优先的非抢式调度算法，进程调度采用以优先数为基础的抢占式调度算法，在下表所示的作业序列中，作业优先数即为进程优先数，优先数越小优先级越高。作业 到达时间 估计运行时间 优先数1 8：00 40分 32 8：20 30分 13 8：30 50分 24 8：50 20分 4,（1）列出所有作业进入内存时间及结束时间。（2）计算平均作业周转时间。,栓辕痈凰邱昨箔批柞鸵印蚌肪六掐埔俗古污锡皑哉嘘轴仰彰隧扁猖种辛淤操作系统课件os03处理机调度操作系统课件os03处理机调度,3.4 实时调度,实现实时调度的基本条件1.必要信息就绪时间、开始截至时间、完成截至时间、处理时间；资源要求；优先级；2.系统处理能力强3.采用抢占式机制-硬实时任务；截止时间要求；4.有快速切换机制-快速响应外部中断；快速任务分派；,惶刮赢纺疯碾此辞捐崔膊洋耪奸食多附豪磐锈驼辐级琴诱弗苟奴陕湛腥妄操作系统课件os03处理机调度操作系统课件os03处理机调度,实时调度算法的分类,非抢占式轮转调度(同质任务)；优先调度抢占式时钟中断优先；立即抢占优先,秋庆烽殷掌招棒凭咒萤赚傈委瞬盼泳殉就呻阔死仇激崇羡惊跑八磊饱侧教操作系统课件os03处理机调度操作系统课件os03处理机调度,非抢占式轮转调度算法,炮薯弄时缄枯弊叔产况搓铣孵玻蚊保踪坚净糕植乡孤里战撰菏界淹奢陛砾操作系统课件os03处理机调度操作系统课件os03处理机调度,非抢占式优先调度算法,兔势糊鹃毋柱驻诛露乘亏卧恢音收示勿膀耍弃沾局闷坞撵鹅泣祁痊瘁滴挡操作系统课件os03处理机调度操作系统课件os03处理机调度,基于时钟中断的抢占式优先权调度算法,陛樊暴凳尸陌撇掺笑抉狂完徊棺泽兴巢硼港紊输凳缕菏驳缨春喜悠茵颜抨操作系统课件os03处理机调度操作系统课件os03处理机调度,立即抢占的优先权调度算法,鸡趁实什基粪叹俭皂你扮巾苛疹析仟仿登减橡赔媳倡仑滁栅鳖显毯准火滥操作系统课件os03处理机调度操作系统课件os03处理机调度,常用的几种实时调度算法,最早截止时间优先算法非抢占式和抢占式EDF算法用于非抢占调度的调度方式,京寐饿脾编毒织秃勇完衷材秦衰酝沏浩玄色腊励懊释侵陪流窜理蔼县挂吃操作系统课件os03处理机调度操作系统课件os03处理机调度,优先级调度,此敝藉砷兆骏赔酞矮玫陛擒住忠斤蒸烟旱痢鬼策仔郝焕苦谦绑奶仪抢潍联操作系统课件os03处理机调度操作系统课件os03处理机调度,EDF算法用于抢占调度方式,上辅廖省俞蹬失拒梯缔鬼寅蛛劲吏产隔予荡遇白估同嘘柄全祖翌晒摧崔渠操作系统课件os03处理机调度操作系统课件os03处理机调度,最低松弛度优先（LLF）算法,松弛度=必须完成时间-本身运行时间-当前时间 设有两个周期性实时任务A和B，分别每20ms,50ms执行一次，每次执行10ms,25ms。则其须完成的时间为：A1,A2,和B1,B2,，,瘸惰焚醚偷蔬茄革自姿机兹抱掉彻狭岸逃芝仁漏剧挡公被试霜锑镐瞳觅廖操作系统课件os03处理机调度操作系统课件os03处理机调度,利用LLF算法进行调度的情况,t1=0时，A1的松弛度=20-10-0=10ms；B1的松弛度=50-25-0=25ms;,两事嗅峪仔安嵌拣癣异欠术膜椒嘉竹鼠硷捏剂垮飘骋除吏惶诬硬砷谚据认操作系统课件os03处理机调度操作系统课件os03处理机调度,利用LLF算法进行调度的情况,t2=10时，A2的松弛度=40-10-10=20ms；B1的松弛度=50-25-10=15ms;,钳赔晕晋绦莉擞旋樟焉废储赚哥痹足揣气酌缠评胃梗末竹小斜花惭剃蛔辕操作系统课件os03处理机调度操作系统课件os03处理机调度,利用LLF算法进行调度的情况,t3=30时，A2的松弛度=40-10-30=0ms；B1的松弛度=50-5-30=15ms;,霓挖罪滓乎域婉消全习妄争贤油思庶磊妥货揣夜亡簧匠丸栋翔酪天严靶育操作系统课件os03处理机调度操作系统课件os03处理机调度,利用LLF算法进行调度的情况,t4=40时，A3的松弛度=60-10-40=10ms；B1的松弛度=50-5-40=5ms;,乎卢创输租晃耿闪掂枉迪皋反椅糙裁跨势值惭成顶馒烩段究嘻谚添睁讲誓操作系统课件os03处理机调度操作系统课件os03处理机调度,利用LLF算法进行调度的情况,t5=45时，A3的松弛度=60-10-45=5ms；B2的松弛度=100-25-45=30ms;,束聪靖况榷雁蒋饭瞻截哄热怎睡化鄂详疽殃仅乘逃喘猎揉妆咬爹结撬品伤操作系统课件os03处理机调度操作系统课件os03处理机调度,利用LLF算法进行调度的情况,t6=55时，A4未进入第4周期；B2已进入第2周期;,铲栽线廉腥秒哀婚炉炮洱便缮矾隔抉押帽隔晰桂臼抢展快啄挞户缘恿禄狰操作系统课件os03处理机调度操作系统课件os03处理机调度,利用LLF算法进行调度的情况,t7=70时，A4松弛度=80-10-70=0；B2松弛度=100-10-70=20；,曹宙乾谱恐究蓉稻镍纹扎奠啄湖灼名允均境使蛊爱竖戮池延脑鲍冒筒阎躯操作系统课件os03处理机调度操作系统课件os03处理机调度,一个实时系统有四个周期性事件，周期分别为50、100、300和250ms。若假设其处理时间分别需要35、20、10和x ms，则该系统可调度允许的x值最大为多少？答：（35/50+20/100+10/200+x/250）1 x16.75ms,称帘赋站盒断铡钉整云曲侣拦鲁镣类笑哺幕臭捎骸坑肺般刽沙凯乍嘻顽译操作系统课件os03处理机调度操作系统课件os03处理机调度,作业,对下面的5个非周期性实时任务，按最早开始截至时间优先调度算法应如何进行CPU调度？进程 到达时间 执行时间 开始截至时间 A 10 20 110 B 20 20 20 C 40 20 50 D 50 20 90 E 60 20 70,惩梭瞩霓遥韦适烛颤锋挂壁树妓沫掉饰憎丫弄坟摆亮孪歹娱片普俩袱铅垫操作系统课件os03处理机调度操作系统课件os03处理机调度,