处理机调剂无功课谜底和习题整理PPT学习教案

1、会计学1处理机调剂无功课谜底和习题整理处理机调剂无功课谜底和习题整理2021-12-132内容概述3.1 处理机调度的基本概念 3.2 调度算法 3.3 实时调度 3.4 多处理机系统中的调度 3.5 产生死锁的原因和必要条件 3.6 预防死锁的方法 3.7 死锁的检测与解除 操作系统中离不开调度。处理机是计算机系统中最为重要的资源之一。处理机调度的主要任务是分配处理机。在多道程序环境下,进程数目通常多于处理机的数目。系统必须按一定方法动态地把处理机分配给就绪队列中的一个进程。处理机利用率和系统性能(吞吐量、响应时间)在很大程度上取决于处理机调度。付露懒烈扼戈瘩见辐艘莆宋尹展露斩婚篙竖喻奖疹盖

2、骆将希压奇讫旧辣缠第3章处理机调度(无作业答案和习题)第3章处理机调度(无作业答案和习题)第1页/共133页2021-12-133政穆枢欢标放篷凰拇粤刘竣柑翅撬陌础拥垣侈性拽潮枫迢詹哄氓任恫琴勺第3章处理机调度(无作业答案和习题)第3章处理机调度(无作业答案和习题)第2页/共133页2021-12-1343.1.1 高级、中级和低级调度1.高级调度(High Scheduling)又称为作业调度或长程调度(Long-Term Scheduling) 将外存上处于后备队列上的作业调入内存,并创建进程、分配资源,安排在就绪队列上有时也称为接纳调度(Admission Scheduling)方淄敏窜

3、柿浸瑚饿叹语最鳃倔政蓉贩搭霄绍陷盎殴搔食同镰肛估耍帝窄哀第3章处理机调度(无作业答案和习题)第3章处理机调度(无作业答案和习题)第3页/共133页2021-12-135短作业优先优先权高优先订邮蹈户母锈剂技哥何郸把翘纲帽腆和丛范蚕衙赛卧奥恬啦右垣猜亦贬抢第3章处理机调度(无作业答案和习题)第3章处理机调度(无作业答案和习题)第4页/共133页2021-12-136正在执行的进程执行完毕,或因发生某事件而不能再继续执行执行中的进程因提出I/O请求而暂停执行;在进程通信或同步过程中执行了某种原语操作,如P操作(wait操作)、Block原语等优点:简单,系统开销小缺点:不适合时间要求严格的实时系统

4、霹琉龟袋髓申沥停硫盂窝版掐妙颗掳匣令窗戴蜕矛赢剩阮赴消皮这环蓟冉第3章处理机调度(无作业答案和习题)第3章处理机调度(无作业答案和习题)第5页/共133页2021-12-137(2)抢占方式(Preemptive Mode)(剥夺方式) 允许调度程序根据某种原则,暂停正在执行的进程,将处理机分配给其他进程抢占式调度主要有以下原则优先权原则:重要作业赋予高优先权,优先占用处理机短作业(进程)优先原则:执行时间短的进程优先执行时间片原则:时间片用完后停止执行,适用于分时系统特点:它增加了进程调度的次数,增加了系统的开销,但保证了系统的实时性晃隘洒曰吸永绑亚绞冈都宽唐尤殷忍殉星笛泪赠漓扯唉殷择播叠床

5、恋毙荔第3章处理机调度(无作业答案和习题)第3章处理机调度(无作业答案和习题)第6页/共133页2021-12-138中级调度又称中程调度(Medium-Term Scheduling)引入中级调度的主要目的,是为了提高内存利用率和系统吞吐量使那些暂时不能运行的进程不再占用宝贵的内存资源,而将它们调至外存上去等待,把此时的进程状态称为就绪驻外存状态或挂起状态。当这些进程重又具备运行条件、且内存又稍有空闲时,由中级调度来决定把外存上的哪些又具备运行条件的就绪进程,重新调入内存,并修改其状态为就绪状态,挂在就绪队列上等待进程调度对换功能厩捻采红毖啥又涛绢掐珠筷差贱炒是挠锣痛灼泉颜丽匆蔓汛杖宰变畏悼

6、皖第3章处理机调度(无作业答案和习题)第3章处理机调度(无作业答案和习题)第7页/共133页2021-12-139曳塘触伟旬框诊慨涕矛臼陋审伞妈换俊税歌廊膏侩饱沙节怕奄氯腺谭梨抬第3章处理机调度(无作业答案和习题)第3章处理机调度(无作业答案和习题)第8页/共133页2021-12-1310耀螟荡争睛葬策藏顾曙锅灵坪抠北疤志征沏碑俗祖髓精怒谤丑痒算矿欣硬第3章处理机调度(无作业答案和习题)第3章处理机调度(无作业答案和习题)第9页/共133页2021-12-13113.1.2 调度队列模型在分时系统中,通常仅设有进程调度,用户键入命令和数据,都直接进入内存,系统可以把就绪进程组织成一个队列每个

7、进程在执行时,可能有以下三种情况 进程在给定时间片内已完成,释放处理机后为完成状态 进程在时间片内未完成,进入就绪队列末尾 进程在执行期间因某事件而阻塞,进入阻塞队列彼玩童币酪掇蛰畴踊谗锭咯芒柜急搅隧头避磕赐耪滩祝蓉紫狐包草恒员阜第3章处理机调度(无作业答案和习题)第3章处理机调度(无作业答案和习题)第10页/共133页2021-12-1312图3-1 仅具有进程调度的调度队列模型 奉汁责魏遭锈棚窘贝规缝充翔杜苦馒航觉葛撮雁戎毒练葫输胀逼透蒋嗣佣第3章处理机调度(无作业答案和习题)第3章处理机调度(无作业答案和习题)第11页/共133页2021-12-1313在批处理系统中,不仅需要进程调度,

8、而且还要有作业调度该模型与上一模型主要区别在于: (1)就绪队列的形式 在批处理系统中,常用优先权队列。进程进入就绪队列时,按优先权高低插入相应位置 (2)设置多个阻塞队列 根据事件的不同设置多个队列提高效率刽蓝梦吵程游费莆鉴瓷扮阻胡饵柠惩信焦拥坞彝赏圃傅损宴顾肝于忠极爽第3章处理机调度(无作业答案和习题)第3章处理机调度(无作业答案和习题)第12页/共133页2021-12-1314图3-2 具有高、低两级调度的调度队列模型 旧赎芳仟独朴囱广往贿戳孤恶净狗络闲串邮迸虹泅俞九抗夏孝挨肪壤占淫第3章处理机调度(无作业答案和习题)第3章处理机调度(无作业答案和习题)第13页/共133页2021-1

9、2-1315图3-2 两级调度简化调度队列模型图翼乌扩鸭增棵慰挛命札俩砧魔照砚曼榆抱甄缀列脉奢候循漾框瞄育蠢岛碌第3章处理机调度(无作业答案和习题)第3章处理机调度(无作业答案和习题)第14页/共133页2021-12-1316 在引入中级调度后,可把就绪分为内存就绪和外存就绪(就绪挂起);阻塞也可分为内存阻塞和外存阻塞(阻塞挂起) 图3-3 具有三级调度时的调度队列模型 氯颅黄奇棕迄桑凋楔题蚁牵祷幅奢弹狈麓懂鞘仟珠颊雕曳纽盆菌咽座岗陈第3章处理机调度(无作业答案和习题)第3章处理机调度(无作业答案和习题)第15页/共133页2021-12-1317缕悠气诉没寸彭特道城川然倚惧敦裹百祸舒击篷枪

10、哨愧唐洋尼古馅魔汽聂第3章处理机调度(无作业答案和习题)第3章处理机调度(无作业答案和习题)第16页/共133页2021-12-13183.1.3 选择调度方式和调度算法的若干准则1. 面向用户的准则(1) 周转时间短。 可把平均周转时间描述为: n11iiTnTniSiiTTnW11作业的周转时间T与系统为它提供服务的时间TS之比,即W=T/TS ,称为带权周转时间,而平均带权周转时间则可表示为: 帛硒捻涨脖腋牧晒陈拌吐戮觉搐傅咀结赶椅悯律辛妖铀赘壮昼点耸欺挑葛第3章处理机调度(无作业答案和习题)第3章处理机调度(无作业答案和习题)第17页/共133页2021-12-1319面向用户的准则

11、(2)响应时间快 响应时间是指从用户通过键盘提交一个请求开始,直至系统中首次产生响应为止的时间。 响应时间包括键盘输入请求信息传送到处理机的时间、处理机对请求的处理时间和响应信息送回到终端的时间(3)截止时间保证 截止时间是指某任务必须开始执行的最迟时间或必须完成的最迟时间 截止时间是实时系统中的重要指标(4)优先权准则 在批处理、实时和分时系统中都可以选择优先权准则,以便让紧急任务先处理 有时还选择抢占式调度方式常用于评价分时系统谢灶诞控耀痪奴媚稗产拱韶判仙泽纷裹庞肠硷遗金嘛蹲詹去懈容示卉军庶第3章处理机调度(无作业答案和习题)第3章处理机调度(无作业答案和习题)第18页/共133页2021

12、-12-13202. 面向系统的准则 (1)系统吞吐量高吞吐量指单位时间内系统所完成的作业数作业调度的方式和算法对吞吐量的大小有较大影响(2)处理机利用率高(3)各类资源的平衡利用使内存、外存和I/O设备的利用率高凿仓蛆贱蕉筹嘘碘酱面化锡爵娱相悯棠真钨啊愚素蛾羊敦籍螟惕蜘羔惨粪第3章处理机调度(无作业答案和习题)第3章处理机调度(无作业答案和习题)第19页/共133页2021-12-1321内容概述3.1 处理机调度的基本概念 3.2 调度算法 3.3 实时调度 3.4 多处理机系统中的调度 3.5 产生死锁的原因和必要条件 3.6 预防死锁的方法 3.7 死锁的检测与解除 伪词移真竿役炉兄并

13、遣究狸拾梧靠章拢瑶逝伴收闸厂检惠嗓正忌慰吴裙爵第3章处理机调度(无作业答案和习题)第3章处理机调度(无作业答案和习题)第20页/共133页2021-12-1322判度柬赃邦澎科藤邀挎缩牢糖估染杜甫弥贼猛望鲍孪蹦劝肄盂粉尺眺侵扁第3章处理机调度(无作业答案和习题)第3章处理机调度(无作业答案和习题)第21页/共133页2021-12-132350K D10:36 24分10K E10:42 12分20K周转时间=结束执行时间-进入磁盘时间带权周转时间=周转时间/服务时间高响应比=(等待时间+服务时间)/服务时间 或=等待时间/服务时间十瓤原他闽租揖倍抉趟孪淖因酶氛影岳辆愉挛悯饵商舞赏其邑贡桑陇扇

14、西第3章处理机调度(无作业答案和习题)第3章处理机调度(无作业答案和习题)第22页/共133页2021-12-1324帮杏愉捷糠种皆智村茹氨伎彻蓑荷学锤蛛傻喻调节舌雪菠征笑燥南邻碧钧第3章处理机调度(无作业答案和习题)第3章处理机调度(无作业答案和习题)第23页/共133页2021-12-13253.2.1 先来先服务和短作业(进程)优先调度算法 1.1.先来先服务调度算法先来先服务调度算法(FCFS)(FCFS)按照作业进入系统的先后次序进行调度按照作业进入系统的先后次序进行调度, ,先进入系统者先调先进入系统者先调度度; ;即启动等待时间最长的作业即启动等待时间最长的作业是一种最简单的调度

15、算法是一种最简单的调度算法, ,即可用于作业调度即可用于作业调度, ,也可用于进也可用于进程调度程调度FCFSFCFS算法比较有利于长作业算法比较有利于长作业( (进程进程),),而不利于短作业而不利于短作业( (进程进程) )栗哩前昔砚譬砚巳镭卸闽骇江划虾余琶稿归啮氦倡妙组息匪石孪赡退榆粗第3章处理机调度(无作业答案和习题)第3章处理机调度(无作业答案和习题)第24页/共133页2021-12-1326内存无限大内存无限大, ,作业调度和进程调度都采用作业调度和进程调度都采用FCFSFCFS作业名作业名 进入磁盘进入磁盘 需要服务需要服务 装入主存装入主存 开始执行开始执行 结束执行结束执行

16、 周转周转 带权周转带权周转时间时间 时间时间 时间时间 时间时间 时间时间 时间时间 时间时间 A A 0 1 0 1 B B 1 1 100 100 C C 2 2 1 1 D D 3 3 100 100执行顺序执行顺序:A-B-C-D:A-B-C-D周转时间周转时间= =结束执行时间结束执行时间- -进入磁盘时间进入磁盘时间带权周转时间带权周转时间= =周转时间周转时间/ /服务时间服务时间0011113110110012102202199101102100100先来先服务调度算法(FCFS)平均值:100恤盼命份臭痔旬切堤借成捌凿绸饱陛昭回幌碱言鹃服氏隙既涣门盈情永趣第3章处理机调度(

17、无作业答案和习题)第3章处理机调度(无作业答案和习题)第25页/共133页2021-12-1327内存总量内存总量:100K,:100K,采用不移动的可变分区方式。采用不移动的可变分区方式。作业调度和进程调度都采用作业调度和进程调度都采用FCFSFCFS作业名作业名 进入磁盘进入磁盘 需要服务需要服务 主存量主存量 装入主存装入主存 开始执行开始执行 结束结束执行执行 周转周转 带权周转带权周转时间时间 时间时间 要求要求 时间时间 时间时间 时时间间 时间时间 时间时间 A A10:06 4210:06 42分分 15K15K B B10:1810:18 30 30分分 60K60K C C

18、10:3010:30 24 24分分 50K50K D D10:3610:36 24 24分分 10K10K E E10:4210:42 12 12分分 20K20K执行顺序执行顺序:A-B-D-C-E:A-B-D-C-E周转时间周转时间= =结束执行时间结束执行时间- -进入磁盘时间进入磁盘时间带权周转时间带权周转时间= =周转时间周转时间/ /服务时间服务时间10:0610:0610:4842110:1810:3610:4811:1860211:1811:1811:1811:426611:4212:0696412:0612:18968先来先服务调度算法(FCFS)平均值: 72揖啪妖馆狄找

19、卜个操搽挖咀宾汰栽窒站泽铝身斑昏利架诌毯侯脊助基邯特第3章处理机调度(无作业答案和习题)第3章处理机调度(无作业答案和习题)第26页/共133页2021-12-13282.2.短作业短作业( (进程进程) )优先调度算法优先调度算法SJ(P)FSJ(P)F短作业短作业( (进程进程) )优先调度算法优先调度算法SJ(P)F,SJ(P)F,以要求运行时间长短进以要求运行时间长短进行调度行调度, ,即启动要求运行时间最短的作业即启动要求运行时间最短的作业可以分别用于作业调度和进程调度可以分别用于作业调度和进程调度短作业优先短作业优先(SJF)(SJF)的调度算法的调度算法, ,是从后备队列中选择一

20、个或是从后备队列中选择一个或若干个估计运行时间最短的作业若干个估计运行时间最短的作业, ,将它们调入内存运行将它们调入内存运行; ;而短进程优先而短进程优先(SPF)(SPF)调度算法调度算法, ,则是从就绪队列中选出一则是从就绪队列中选出一估计运行时间最短的进程估计运行时间最短的进程, ,将处理机分配给它将处理机分配给它, ,使它立即使它立即执行并一直执行到完成执行并一直执行到完成, ,或发生某事件而被阻塞放弃处或发生某事件而被阻塞放弃处理机时理机时, ,再重新调度再重新调度剖如娇零指惜劫阀迁犯燕公拜孕层碰锗符菊慧耿饥倍章系讲酝昔赶外励晒第3章处理机调度(无作业答案和习题)第3章处理机调度(

21、无作业答案和习题)第27页/共133页2021-12-1329内存无限大内存无限大, ,作业调度和进程调度都采用作业调度和进程调度都采用FCFSFCFS作业名作业名 进入磁盘进入磁盘 需要服务需要服务 装入主存装入主存 开始执行开始执行 结束执行结束执行 周转周转 带权周转带权周转时间时间 时间时间 时间时间 时间时间 时间时间 时间时间 时间时间 A A 0 4 0 4 B B 1 1 3 3 C C 2 2 5 5 D D 3 3 2 2 E E 4 4 4 4执行顺序执行顺序:A-B-C-D-E:A-B-C-D-E作业调度作业调度FCFSFCFS和进程调度都采用和进程调度都采用SJFSJ

22、F A A 0 4 0 4 B B 1 1 3 3 C C 2 2 5 5 D D 3 3 2 2 E E 4 4 4 4周转时间周转时间= =结束执行时间结束执行时间- -进入磁盘时间进入磁盘时间带权周转时间带权周转时间= =周转时间周转时间/ /服务时间服务时间004411347622121411712102短作业(进程)优先调度算法SJ(P)F414181400441136988/3246313181616/5491399/4平均值: 9平均值: 8执行顺序:A-D-B-E-C腆缔赖踏险表敬酬陶宛韭姿约万匈讣茎集春照慕烂聋摹利醉胳勇愚同吗覆第3章处理机调度(无作业答案和习题)第3章处理机

23、调度(无作业答案和习题)第28页/共133页2021-12-1330内存总量内存总量:100K,:100K,采用不移动的可变分区方式。采用不移动的可变分区方式。作业调度采用作业调度采用SJFSJF和进程调度采用和进程调度采用FCFSFCFS作业名作业名 进入磁盘进入磁盘 需要服务需要服务 主存量主存量 装入主存装入主存 开始执行开始执行 结束结束执行执行 周转周转 带权周转带权周转时间时间 时间时间 要求要求 时间时间 时间时间 时时间间 时间时间 时间时间 A A10:06 4210:06 42分分 15K15K B B10:1810:18 30 30分分 60K60K C C10:3010

24、:30 24 24分分 50K50K D D10:3610:36 24 24分分 10K10K E E10:4210:42 12 12分分 20K20K执行顺序执行顺序:A-B-D-E-C:A-B-D-E-C周转时间周转时间= =结束执行时间结束执行时间- -进入磁盘时间进入磁盘时间带权周转时间带权周转时间= =周转时间周转时间/ /服务时间服务时间高响应比高响应比=(=(等待时间等待时间+ +服务时间服务时间)/)/服务时间服务时间 或或= =等待时间等待时间/ /服务时间服务时间10:0610:0610:4842110:1810:3610:4811:1860211:1811:1811:18

25、11:426611:5412:1810811:4211:54726短作业(进程)优先调度算法SJ(P)F芥辆憎耸缺溅舟柄捂硫陕持耳核彭尺车便拇诚挥梗嘛亢入句苛讫沈耳识造第3章处理机调度(无作业答案和习题)第3章处理机调度(无作业答案和习题)第29页/共133页2021-12-1331 SJ(P)F调度算法也存在不容忽视的缺点: (1)该算法对长作业不利,如作业C的周转时间由10增至16,其带权周转时间由2增至3.2。更严重的是,如果有一长作业(进程)进入系统的后备队列(就绪队列),由于调度程序总是优先调度那些(即使是后进来的)短作业(进程),将导致长作业(进程)长期不被调度。 (2)该算法完全

26、未考虑作业的紧迫程度,因而不能保证紧迫性作业(进程)会被及时处理。 (3)由于作业(进程)的长短只是根据用户所提供的估计执行时间而定的,而用户又可能会有意或无意地缩短其作业的估计运行时间,致使该算法不一定能真正做到短作业优先调度。赤宙强琳甥签处淳讫焰旅烘胜厕悲笑仁株疫思倦呈翁易勿酷腊姐蓝苍宏南第3章处理机调度(无作业答案和习题)第3章处理机调度(无作业答案和习题)第30页/共133页2021-12-1332狄箩蠢刘挥窟活殖吠映苇仕掣据黔柏蛔挤妆萌肯框厢雷后倦涌汀尧球朱及第3章处理机调度(无作业答案和习题)第3章处理机调度(无作业答案和习题)第31页/共133页2021-12-13333.2.2

27、 高优先权优先调度算法1.优先权调度算法的类型 (1)(1)非抢占式优先权算法非抢占式优先权算法系统一旦把处理机分配给就绪队列中优先权最高的进程后系统一旦把处理机分配给就绪队列中优先权最高的进程后, ,该进程便一直执行下去该进程便一直执行下去, ,直至完成直至完成; ;或因发生某事件使该或因发生某事件使该进程放弃处理机时进程放弃处理机时, ,系统方可再将处理机重新分配给另系统方可再将处理机重新分配给另一优先权最高的进程。一优先权最高的进程。主要用于批处理系统中主要用于批处理系统中, ,也可用于某些对实时性要求不严的也可用于某些对实时性要求不严的实时系统中。实时系统中。碾夸佩羹资泄碗是殃夸味铁呀

28、军勤仑范尽尖惭誓锨耐憨静北镭阑成叶径琅第3章处理机调度(无作业答案和习题)第3章处理机调度(无作业答案和习题)第32页/共133页2021-12-1334(2)(2)抢占式优先权调度算法抢占式优先权调度算法系统同样是把处理机分配给优先权最高的进程系统同样是把处理机分配给优先权最高的进程, ,使之执行。使之执行。但在其执行期间但在其执行期间, ,只要又出现了另一个其优先权更高的只要又出现了另一个其优先权更高的进程进程, ,进程调度程序就立即停止当前进程进程调度程序就立即停止当前进程( (原优先权最高原优先权最高的进程的进程) )的执行的执行, ,重新将处理机分配给新到的优先权最高重新将处理机分配

29、给新到的优先权最高的进程。的进程。在采用这种调度算法时在采用这种调度算法时, ,每当系统中出现一个新的就绪进程每当系统中出现一个新的就绪进程i i时时, ,就将其优先权就将其优先权PiPi与正在执行的进程与正在执行的进程j j的优先权的优先权PjPj进进行比较。如果行比较。如果PiPj,PiPj,原进程原进程PjPj便继续执行便继续执行; ;但如果是但如果是PiPiPj, Pj, 则立即停止则立即停止PjPj的执行的执行, ,做进程切换做进程切换, ,使使i i进程投入进程投入执行。执行。抢占式的优先权调度算法抢占式的优先权调度算法, ,能更好地满足紧迫作业的要求能更好地满足紧迫作业的要求,

30、,故而常用于要求比较严格的实时系统中故而常用于要求比较严格的实时系统中, , 以及对性能要以及对性能要求较高的批处理和分时系统中。求较高的批处理和分时系统中。按惭赁喘腕蹦良撩被绕腔焚效泽扬邓智谰犁殊初乱疲译淄珐取袖疤堂投减第3章处理机调度(无作业答案和习题)第3章处理机调度(无作业答案和习题)第33页/共133页2021-12-1335 1)静态优先权 静态优先权是在创建进程时确定的,且在进程的整个运行期间保持不变。一般地,优先权是利用某一范围内的一个整数来表示的,例如,07或0255中的某一整数,又把该整数称为优先数。只是具体用法各异:有的系统用“0”表示最高优先权,当数值愈大时,其优先权愈

31、低;而有的系统恰恰相反。拓愧蝇旨慎坚艳标脯涌骚邀柔基奔竹窃宣瑞则捧箩爽用厉囤近哼退来眩沽第3章处理机调度(无作业答案和习题)第3章处理机调度(无作业答案和习题)第34页/共133页2021-12-1336确定进程优先权的依据有如下三个方面:(1)进程类型系统进程优先级高于用户进程(2)进程对资源的需求执行时间短,内存要求小的进程,有较高优先权。 (3)用户要求根据用户进程紧迫程度及用户所付费用的多少来确定。静态优先权特点:(1)系统简单易行。(2)系统开销小。(3)不够精确。(4)一般用在要求不高的系统中。痔郴舀堵涪湘券何哮默盗内画赴菱毖诗投辟睦坞烤芬藏辐丽默岗瘴揍摇找第3章处理机调度(无作业

32、答案和习题)第3章处理机调度(无作业答案和习题)第35页/共133页2021-12-13372)2)动态优先权动态优先权在创建进程时所赋予的优先权在创建进程时所赋予的优先权, ,是可以随进程的推进或随其是可以随进程的推进或随其等待时间的增加而改变的等待时间的增加而改变的, ,以便获得更好的调度性能。以便获得更好的调度性能。例如例如, ,我们可以规定我们可以规定, ,在就绪队列中的进程在就绪队列中的进程, ,随其等待时间的随其等待时间的增长增长, ,其优先权以速率其优先权以速率a a提高。提高。若所有的进程都具有相同的优先权初值若所有的进程都具有相同的优先权初值, ,则显然是最先进入则显然是最先

33、进入就绪队列的进程就绪队列的进程, ,将因其动态优先权变得最高而优先获将因其动态优先权变得最高而优先获得处理机得处理机, ,此即先来先服务此即先来先服务FCFSFCFS算法。算法。若所有的就绪进程具有各不相同的优先权初值若所有的就绪进程具有各不相同的优先权初值, ,那么那么, ,对于对于优先权初值低的进程优先权初值低的进程, ,在等待了足够的时间后在等待了足够的时间后, ,其优先权其优先权便可能升为最高便可能升为最高, ,从而可以获得处理机从而可以获得处理机当采用抢占式优先权调度算法时当采用抢占式优先权调度算法时, ,如果再规定当前进程的优如果再规定当前进程的优先权以速率先权以速率b b下降下

34、降, ,则可防止一个长作业长期地垄断处理则可防止一个长作业长期地垄断处理机。机。坠诚昆鲁啦纠殖篱耻孜画坝袁挥汝络因仅琳董碌镁腕淑驳啥比柜河墙西擒第3章处理机调度(无作业答案和习题)第3章处理机调度(无作业答案和习题)第36页/共133页2021-12-13383.3.高响应比优先调度算法高响应比优先调度算法(HRF)(HRF)该算法是该算法是FCFSFCFS和和SJFSJF的结合的结合, ,克服了两种算法的缺点克服了两种算法的缺点响应比最高的作业优先启动响应比最高的作业优先启动由于等待时间与服务时间之和由于等待时间与服务时间之和, ,就是系统对该作业的响应时就是系统对该作业的响应时间间, ,故

35、该优先权又相当于响应比故该优先权又相当于响应比RPRP。据此。据此, ,又可表示为又可表示为要求服务时间要求服务时间等待时间优先权要求服务时间响应时间要求服务时间要求服务时间等待时间优先权誊篓已佳吗报舍希掠闷捣趟赏肾醉菊绅痊乐釉蝇尾刊缸椭逊敛猛浴僚忧刨第3章处理机调度(无作业答案和习题)第3章处理机调度(无作业答案和习题)第37页/共133页2021-12-1339作业名作业名 进入磁盘时间进入磁盘时间 需要服务时间需要服务时间 响应比响应比1 1 响响应比应比2 2 A A 8:50 90 8:50 90分分 B B 9:00 9:00 24 24分分 C C 9:30 9:30 60 60

36、分分 高响应比高响应比1 =1 =等待时间等待时间/ /服务时间服务时间高响应比高响应比2 =(2 =(等待时间等待时间+ +服务时间服务时间)/)/服务时间服务时间40/90=4/9高响应比优先调度算法(40+90)/90=4/9+130/24=5/4(30+24)/24=5/4+10/60=0(0+60)/60=1设9:30进行调度:作业名作业名 进入磁盘时间进入磁盘时间 需要服务时间需要服务时间 响应比响应比1 1 响响应比应比2 2 A A 8:50 90 8:50 90分分 C C 9:30 9:30 60 60分分 64/90=32/45(64+90)/90=32/45+124/6

37、0=2/5(24+60)/60=2/5+1当B执行完后,又要在9:54进行调度:梦岭赤若束模掠参害肚艾此经盖滴饰前缩倘忙柱切颂澳拯错弓锹峻龙虏伟第3章处理机调度(无作业答案和习题)第3章处理机调度(无作业答案和习题)第38页/共133页2021-12-1340对高响应比优先调度算法(HRF)的解释 (1)如果作业的等待时间相同,则要求服务的时间愈短,其优先权愈高,因而该算法有利于短作业。 (2)当要求服务的时间相同时,作业的优先权决定于其等待时间,等待时间愈长,其优先权愈高,因而它实现的是先来先服务。 (3)对于长作业,作业的优先级可以随等待时间的增加而提高,当其等待时间足够长时,其优先级便可

38、升到很高,从而也可获得处理机。高响应比1 =等待时间/服务时间孩两驯务偏哩炮熙碉茂抉顾橇配籽情非惯扳盆负弓诵戌褂熊腾腥锡滔搔遥第3章处理机调度(无作业答案和习题)第3章处理机调度(无作业答案和习题)第39页/共133页2021-12-1341泥迎开疑讳蜘全惟抨檬帖仓阮预驻串赖取揉凯逝烬抒修杠竹迫荚壤恼凤鹿第3章处理机调度(无作业答案和习题)第3章处理机调度(无作业答案和习题)第40页/共133页2021-12-13423.2.3 基于时间片的轮转调度算法 在早期的时间片轮转法中在早期的时间片轮转法中, ,系统将所有的就绪进程按先来先系统将所有的就绪进程按先来先服务的原则服务的原则, ,排成一个

39、队列排成一个队列, ,每次调度时每次调度时, ,把把CPUCPU分配给分配给队首进程队首进程, ,并令其执行一个时间片并令其执行一个时间片, ,时间片的大小从几时间片的大小从几msms到几百到几百msms当执行的时间片用完时当执行的时间片用完时, ,由一个计时器发出时钟中断请求由一个计时器发出时钟中断请求, ,调度程序便据此信号来停止该进程的执行调度程序便据此信号来停止该进程的执行, ,并将它送往并将它送往就绪队列的末尾就绪队列的末尾; ;然后然后, ,再把处理机分配给就绪队列中再把处理机分配给就绪队列中新的队首进程新的队首进程, ,同时也让它执行一个时间片同时也让它执行一个时间片可以保证就绪

40、队列中的所有进程可以保证就绪队列中的所有进程, ,在一给定的时间内在一给定的时间内, ,均能均能获得一时间片的处理机执行时间获得一时间片的处理机执行时间软伺拈民懒峡扫怎案辛澈屈鸳亢额疹炸筐叭端氮炼升沼累霹矮防逛蒙康特第3章处理机调度(无作业答案和习题)第3章处理机调度(无作业答案和习题)第41页/共133页2021-12-1343内存无限大。作业调度采用内存无限大。作业调度采用FCFSFCFS和进程调度采用时间片的轮转和进程调度采用时间片的轮转q=1q=1作业进入作业进入 需要需要 装入装入 开始开始 执行执行 执行执行 开始开始 执行执行 执行执行 开始开始 执执行行 执行执行 开始开始 执

41、行执行 执行执行 完成完成 周转周转 带权带权名名 磁盘磁盘 服务服务 主存主存 执行执行 时间时间 后后 执行执行 时间时间 后后 执行执行 时时间间 后后 执行执行 时间时间 后后 周转周转A 0 4A 0 4 B 1 3B 1 3 C 2 4C 2 4 D 3 2D 3 2 E 4 4E 4 4 完成顺序完成顺序:D-B-A-C-E:D-B-A-C-E周转时间周转时间= =结束执行时间结束执行时间- -进入磁盘时间进入磁盘时间带权周转时间带权周转时间= =周转时间周转时间/ /服务时间服务时间高响应比高响应比=(=(等待时间等待时间+ +服务时间服务时间)/)/服务时间服务时间 或或=

42、=等待时间等待时间/ /服务时间服务时间001131124312141时间片的轮转124355687911111679810101112131111111213141415161111516179631211151517131614潘为碧幅务尔雪轩馁琶柬呸洋梭辗叶焚诸钉杰悍朗琶喇淳星咳彦袁喊暇紫第3章处理机调度(无作业答案和习题)第3章处理机调度(无作业答案和习题)第42页/共133页2021-12-1344内存无限大。作业调度采用内存无限大。作业调度采用FCFSFCFS和进程调度采用时间片的轮转和进程调度采用时间片的轮转q=4q=4作业进入作业进入 需要需要 装入装入 开始开始 执行执行 执

43、行执行 开始开始 执行执行 执行执行 开始开始 执执行行 执行执行 开始开始 执行执行 执行执行 完成完成 周转周转 带权带权名名 磁盘磁盘 服务服务 主存主存 执行执行 时间时间 后后 执行执行 时间时间 后后 执行执行 时时间间 后后 执行执行 时间时间 后后 周转周转A 0 4A 0 4 B 1 3B 1 3 C 2 4C 2 4 D 3 2D 3 2 E 4 4E 4 4 完成顺序完成顺序:A-B-C-D-E:A-B-C-D-E周转时间周转时间= =结束执行时间结束执行时间- -进入磁盘时间进入磁盘时间带权周转时间带权周转时间= =周转时间周转时间/ /服务时间服务时间高响应比高响应比

44、=(=(等待时间等待时间+ +服务时间服务时间)/)/服务时间服务时间 或或= =等待时间等待时间/ /服务时间服务时间00413432411274134时间片的轮转47131117131057624411713119昨隙迭翁乎川开赐略诬捞宴味咋喜淫辊纶遣爱怕断奸届瓣潭坡囱常迈便帅第3章处理机调度(无作业答案和习题)第3章处理机调度(无作业答案和习题)第43页/共133页2021-12-1345图3-5 多级反馈队列调度算法 优先级高历吭帅迂趁俘辛进雕乙箕许豫冉珍缠狂锈悄蚜望演猿聂吭谎颈记底奢伦膳第3章处理机调度(无作业答案和习题)第3章处理机调度(无作业答案和习题)第44页/共133页202

45、1-12-1346设置多个就绪队列设置多个就绪队列, ,并为各个队列赋予不同的优先级并为各个队列赋予不同的优先级第一个队列的优先级最高第一个队列的优先级最高, ,第二个队列次之第二个队列次之, ,其余各队列的其余各队列的优先权逐个降低。优先权逐个降低。该算法赋予各个队列中进程执行时间片的大小也各不相同该算法赋予各个队列中进程执行时间片的大小也各不相同, ,在优先权愈高的队列中在优先权愈高的队列中, ,为每个进程所规定的执行时间为每个进程所规定的执行时间片就愈小。例如片就愈小。例如, ,第二个队列的时间片要比第一个队列第二个队列的时间片要比第一个队列的时间片长一倍的时间片长一倍,第第i+1i+1

46、个队列的时间片要比第个队列的时间片要比第i i个个队列的时间片长一倍。队列的时间片长一倍。调度方式调度方式当一个新进程进入内存后当一个新进程进入内存后, ,首先将它放入第一队列的末尾首先将它放入第一队列的末尾, ,按按FCFSFCFS原则排队等待调度原则排队等待调度当轮到该进程执行时当轮到该进程执行时, ,如它能在该时间片内完成如它能在该时间片内完成, ,便可准备便可准备撤离系统撤离系统; ;如果它在一个时间片结束时尚未完成如果它在一个时间片结束时尚未完成, ,调度程调度程序便将该进程转入第二队列的末尾序便将该进程转入第二队列的末尾, ,再同样地按再同样地按FCFSFCFS原原则等待调度执行则

47、等待调度执行; ;如果它在第二队列中运行一个时间片如果它在第二队列中运行一个时间片后仍未完成后仍未完成, ,再依次将它放入第三队列再依次将它放入第三队列,如此下去如此下去, ,当一个长作业当一个长作业( (进程进程) )从第一队列依次降到第从第一队列依次降到第n n队列后队列后, ,在在第第n n队列中便采取按时间片轮转的方式运行。队列中便采取按时间片轮转的方式运行。还躯跑借把暇蛋鱼配郧涝频徘啤统影继竭日剧吩灭傀狐所存识昼嗣阔沉邦第3章处理机调度(无作业答案和习题)第3章处理机调度(无作业答案和习题)第45页/共133页2021-12-1347仅当第一队列空闲时仅当第一队列空闲时, ,调度程序

48、才调度第二队列中的进程运调度程序才调度第二队列中的进程运行行; ;仅当第仅当第1(i-1) 1(i-1) 队列均空时队列均空时, ,才会调度第才会调度第i i队列中的队列中的进程运行。进程运行。如果处理机正在第如果处理机正在第i i队列中为某进程服务时队列中为某进程服务时, ,又有新进程进又有新进程进入优先权较高的队列入优先权较高的队列( (第第1(i-1)1(i-1)中的任何一个队列中的任何一个队列),),则则此时新进程将抢占正在运行进程的处理机此时新进程将抢占正在运行进程的处理机, ,即由调度程即由调度程序把正在运行的进程放回到第序把正在运行的进程放回到第i i队列的末尾队列的末尾, ,把

49、处理机分把处理机分配给新到的高优先权进程。配给新到的高优先权进程。邵纵蟹除颈蛤插颜敦茧钞末觅锥捣署泥歌自端循疚蔼塌篷治倍拖傣返厚熏第3章处理机调度(无作业答案和习题)第3章处理机调度(无作业答案和习题)第46页/共133页2021-12-1348(1)(1)终端型作业用户终端型作业用户终端型作业用户所提交的作业多属于交互型作业终端型作业用户所提交的作业多属于交互型作业, ,通常较小通常较小, ,系统只要能使这些作业在第一队列所规定的时间片内完系统只要能使这些作业在第一队列所规定的时间片内完成即可成即可(2)(2)短批处理作业用户短批处理作业用户若在第若在第1 1队列中执行一个时间片即可完成队列

50、中执行一个时间片即可完成, ,便可获得与终端便可获得与终端型作业一样的响应时间型作业一样的响应时间如在第一个队列中不能完成如在第一个队列中不能完成, ,只需在第只需在第2 2、3 3队列中各执行一队列中各执行一个时间片个时间片(3)(3)长批处理作业用户长批处理作业用户长作业将依次在第长作业将依次在第1,2,3,n1,2,3,n队列中执行队列中执行, ,最终按轮转方式最终按轮转方式运行运行穆灸魔浦硫怔危财寓思徊屑珍嫂盔俘桓综途镣慌帛魂桐央挤队芽纽岭镣沸第3章处理机调度(无作业答案和习题)第3章处理机调度(无作业答案和习题)第47页/共133页2021-12-1349内容概述3.1 处理机调度的

51、基本概念 3.2 调度算法 3.3 实时调度 3.4 多处理机系统中的调度 3.5 产生死锁的原因和必要条件 3.6 预防死锁的方法 3.7 死锁的检测与解除 他恃鼻守堑棒颠爱籽官鳃戌擂瘁逸表冈每档鄙靛戍批敷布象关渝吊撑畸跳第3章处理机调度(无作业答案和习题)第3章处理机调度(无作业答案和习题)第48页/共133页2021-12-13503.3.1 3.3.1 实现实时调度的基本条件实现实时调度的基本条件3.3.2 3.3.2 实时调度算法的分类实时调度算法的分类3.3.3 3.3.3 常用的几种实时调度算法常用的几种实时调度算法凡素粪瓣捻卖惑柑路勺寻芹淑返崔当板温嘿棠孩厩叠粮塑豫疆尝千丈渺蜀

52、第3章处理机调度(无作业答案和习题)第3章处理机调度(无作业答案和习题)第49页/共133页2021-12-13513.3.1 实现实时调度的基本条件(1)就绪时间该任务成为就绪状态的起始时间。(2)开始截止时间和完成截止时间(3)处理时间指一个任务从开始执行直至完成所需要的时间。(4)资源要求执行时所需资源。(5)优先级重大任务,赋予“绝对”优先级,无重大影响,可赋予“相对”优先级。始又瘩蛤鸥硷媳棉践盼桐羊社纬屎油狙惋打殿隶抹迅溉呛丛翰底隆悦场饭第3章处理机调度(无作业答案和习题)第3章处理机调度(无作业答案和习题)第50页/共133页2021-12-1352 在实时系统中,通常都有着多个实

53、时任务。若处理机的处理能力不够强,则有可能因处理机忙不过来而使某些实时任务不能得到及时处理,从而导致发生难以预料的后果。假定系统中有m个周期性的硬实时任务,它们的处理时间可表示为Ci,周期时间表示为Pi,则在单处理机情况下,必须满足下面的限制条件,系统才是可调度的。miiiPC11撅没赁潘秀侧晴逼帕绕独钒刊揩珠腿腋獭硒著瓦椭邓扳盅宴快常删蛹喝盲第3章处理机调度(无作业答案和习题)第3章处理机调度(无作业答案和习题)第51页/共133页2021-12-1353 假如系统中有6个硬实时任务,它们的周期时间都是50 ms,而每次的处理时间为10 ms,则不难算出,此时是不能满足上式的,因而系统是 的

54、。 解决的方法是提高系统的处理能力,其途径有二:其一仍是采用单处理机系统,但须增强其处理能力,以显著地减少对每一个任务的处理时间;其二是采用多处理机系统。假定系统中的处理机数为N,则应将上述的限制条件改为: miiiNPC1不可调度舟芽堡少踞市擒兵碘瞪拯饱夺舅贬示躲切柔戍佣库蒂痢畸抵户楚顷读时漆第3章处理机调度(无作业答案和习题)第3章处理机调度(无作业答案和习题)第52页/共133页2021-12-1354 当一个优先权更高的任务到达时,允许将当前任务暂时挂起,而令高优先权任务立即投入运行,这样便可满足该硬实时任务对截止时间的要求。但这种调度机制比较复杂。 对于一些小的实时系统,如果能预知任

55、务的开始截止时间,则对实时任务的调度可采用非抢占调度机制,以简化调度程序和对任务调度时所花费的系统开销。但在设计这种调度机制时,应使所有的实时任务都比较小,并在执行完关键性程序和临界区后,能及时地将自己阻塞起来,以便释放出处理机,供调度程序去调度那种开始截止时间即将到达的任务。 绷紧币继贝陪抢哉好阀农豹荣燥木讳殊遂涸宙枢脓呐拦于臣淄跌级皇韧皱第3章处理机调度(无作业答案和习题)第3章处理机调度(无作业答案和习题)第53页/共133页2021-12-1355 该机制应具有如下两方面的能力: (1)对外部中断的快速响应能力。 为使在紧迫的外部事件请求中断时系统能及时响应,要求系统具有快速硬件中断机

56、构,还应使禁止中断的时间间隔尽量短,以免耽误时机(其它紧迫任务)。 (2)快速的任务分派能力。 在完成任务调度后,便应进行任务切换。为了提高分派程序进行任务切换时的速度,应使系统中的每个运行功能单位适当的小,以减少任务切换的时间开销。 疹蝉湿汇郎礼汽堑份瞩庚摊沛盲阂幢晚碘叫乳寂诱臣坷师裹磨涅歹决裙馏第3章处理机调度(无作业答案和习题)第3章处理机调度(无作业答案和习题)第54页/共133页2021-12-13563.3.1 3.3.1 实现实时调度的基本条件实现实时调度的基本条件3.3.2 3.3.2 实时调度算法的分类实时调度算法的分类3.3.3 3.3.3 常用的几种实时调度算法常用的几种

57、实时调度算法挤垫畜俞辈琼朝补警康化枢淮巧垛鼎帧吼盾拈墩湛骡漾血扑哟钳翘邻凰帕第3章处理机调度(无作业答案和习题)第3章处理机调度(无作业答案和习题)第55页/共133页2021-12-13573.3.2 实时调度算法的分类 根据实时任务性质的不同根据实时任务性质的不同, ,可将实时调度算法分为可将实时调度算法分为: :(1)(1)硬实时调度算法硬实时调度算法(2)(2)软实时调度算法软实时调度算法按调度方式的不同按调度方式的不同, ,可将实时调度算法分为可将实时调度算法分为: :(1)(1)非抢占调度算法非抢占调度算法(2)(2)抢占调度算法抢占调度算法因调度程序调度时间的不同因调度程序调度时

58、间的不同, ,可将实时调度算法分为可将实时调度算法分为: :(1)(1)静态调度算法静态调度算法(2)(2)动态调度算法动态调度算法在多处理机环境下在多处理机环境下, ,可将实时调度算法分为可将实时调度算法分为: :(1)(1)集中式调度算法集中式调度算法(2)(2)分布式调度算法分布式调度算法耙药远翠哨卞咐纲据去靛剁廓衡扶缅柏鉴谚辟纂泻扼辗癸狠盐讣惊遂智佩第3章处理机调度(无作业答案和习题)第3章处理机调度(无作业答案和习题)第56页/共133页2021-12-1358(1)(1)非抢占式轮转调度算法非抢占式轮转调度算法 常用于工业生产的群控系统中常用于工业生产的群控系统中调度程序每次选择队

59、列中的第一个任务运行调度程序每次选择队列中的第一个任务运行一个任务运行后排在轮转队列的末尾一个任务运行后排在轮转队列的末尾, ,等待下次调度等待下次调度可用于要求不太严格的实时控制系统中可用于要求不太严格的实时控制系统中可获得仅数秒至数十秒的响应时间可获得仅数秒至数十秒的响应时间按调度方式的不同,可将实时调度算法分为:图3-6 实时进程调度 纯誊盎钨恰步增怯叮侣署佑浚擎撤韶缉叼督耕厕憋刘克沫渗直埠涟湖耍穆第3章处理机调度(无作业答案和习题)第3章处理机调度(无作业答案和习题)第57页/共133页2021-12-1359(1)(1)(2)(2)非抢占式优先调度算法非抢占式优先调度算法为时间要求严

60、格的任务分配较高优先级为时间要求严格的任务分配较高优先级当优先权高的实时任务到来时当优先权高的实时任务到来时, ,排在就绪队列的队首等待调排在就绪队列的队首等待调度度有可能获得仅数秒至数百毫秒级的响应时间有可能获得仅数秒至数百毫秒级的响应时间图3-6 实时进程调度 (b) 非抢占优先权调度非抢占优先权调度当前进程当前进程实时进程实时进程实时进程请求调度实时进程请求调度当前进程运行完成当前进程运行完成调度时间调度时间就邦捂抉形箕啸次森根蠕森膀俐捕亥碘名釉岁侮赐缨门查街兄屋羊恤矫凶第3章处理机调度(无作业答案和习题)第3章处理机调度(无作业答案和习题)第58页/共133页2021-12-1360图