《第3章处理机调度课件.ppt》由会员分享，可在线阅读，更多相关《第3章处理机调度课件.ppt（57页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、第三章第三章 处理机调度处理机调度(CPU调度调度)无论在多道批处理系统还是分时系统中无论在多道批处理系统还是分时系统中,系统中系统中的用户进程数都远远超过处理机数的用户进程数都远远超过处理机数,除用户进程要占除用户进程要占用处理机外用处理机外,操作系统还要建立若干个系统进程完成操作系统还要建立若干个系统进程完成系统功能。这么多的进程竞争处理机系统功能。这么多的进程竞争处理机,就要求系统提就要求系统提供进程调度功能供进程调度功能,以便采用一些策略以便采用一些策略,将处理机动态将处理机动态地分配给系统中的各个就绪进程地分配给系统中的各个就绪进程,使之执行。分配处使之执行。分配处理机的任务是由处理
2、机调度程序完成的理机的任务是由处理机调度程序完成的;处理机是计处理机是计算机最重要的资源算机最重要的资源,如何提高处理机的利用率及改善如何提高处理机的利用率及改善系统性能系统性能,在很大程度上取决于处理机调度性能的好在很大程度上取决于处理机调度性能的好坏坏,处理机调度成为操作系统设计中心工作。处理机调度成为操作系统设计中心工作。牺铱翻投塘锄惶馈域卵柯坦暑蒸目郊抽穷匠恿蜗扶逗脉汾侯封逝回拭佛棠第3章处理机调度第3章处理机调度要解决的问题要解决的问题WHAT：按什么原则分配按什么原则分配CPU 进程调度算法进程调度算法WHEN：何时分配何时分配CPU 进程调度的时机进程调度的时机HOW：如何分配如
3、何分配CPU CPU调度过程（进程的上下文切换）调度过程（进程的上下文切换）硫弯乡诉普滑蛀恰旭汀涸彩魔纫账谴丢脚滑并旗彰软附黔挂遇絮谢蜂蛋酞第3章处理机调度第3章处理机调度 一批作业从进入系统到作业运行完毕可能经历三级一批作业从进入系统到作业运行完毕可能经历三级调度调度高级、低级和中级调度。高级、低级和中级调度。一一.高级调度高级调度(High Scheduling)又称为作业调度接纳调度或长程调度又称为作业调度接纳调度或长程调度,用于批处理用于批处理系统系统,确定将外存后备队列中哪些作业调入内存确定将外存后备队列中哪些作业调入内存,并为并为它们创建进程。实时系统和分时系统的前台作业不需要它们
4、创建进程。实时系统和分时系统的前台作业不需要作业调度。每次作业调度时作业调度。每次作业调度时,都必须做出两个决定都必须做出两个决定:1)接纳多少个作业接纳多少个作业:取决于多道程序度。取决于多道程序度。2)接纳哪些作业接纳哪些作业(用什么调度算法用什么调度算法):先来先服务、短作业优先、优先权、响应比优先。先来先服务、短作业优先、优先权、响应比优先。3.1 处理机调度的基本概念处理机调度的基本概念 3.1.1 高级、低级和中级调度高级、低级和中级调度响应响应/运行运行舰鞍泰当严药伐善违怒腐宛斑绦烘猖咎后泰名穴逢孩疡魏孪征詹罕单寇冤第3章处理机调度第3章处理机调度二二.低级调度低级调度(进程调度
5、进程调度,短程调度短程调度)进程调度的任务是控制协调进程对进程调度的任务是控制协调进程对CPU的竞争的竞争,即即按照一定的调度算法从就绪队列中选中一个进程，把按照一定的调度算法从就绪队列中选中一个进程，把CPU的使用权交给被选中的进程。它是最基本的一种的使用权交给被选中的进程。它是最基本的一种调度调度,批处理系统批处理系统,实时系统和分时系统都必须有进程实时系统和分时系统都必须有进程调度。它通过进程调度程序来完成。调度。它通过进程调度程序来完成。1.进程调度程序的主要功能可描述如下：进程调度程序的主要功能可描述如下：(1)记录系统中各进程的状况记录系统中各进程的状况 为了很好地实现进程调度为了
6、很好地实现进程调度,进程调度程序首先必须进程调度程序首先必须管理系统中各进程的管理系统中各进程的PCB，将进程的状态变化及资源，将进程的状态变化及资源需求情况及时地记录到需求情况及时地记录到PCB中。通过中。通过PCB变化来准确变化来准确地掌握系统中所有进程的地掌握系统中所有进程的状态特征和执行情况状态特征和执行情况。翔旷耪往或均迎阉苯岿碧街怯蛇些汐竹竿筐势韧滥历岭盈败浊拙另肌鸳挡第3章处理机调度第3章处理机调度(2)选择进程真正占有选择进程真正占有CPU 这这是是进进程程调调度度的的实实质质,即即按按照照系系统统规规定定的的调调度度策策略略从从就就绪绪队队列列中中选选择择一一个个进进程程占占
7、有有CPU执执行行。进进程程调调度度依依据据的的算算法法与与系系统统的的设设计计目目标标相相一一致致。对对于于不不同同的的系系统统,通通常常采采用用不不同同的的调调度度策策略略。对对于于批批处处理理系系统统常常采采用用短短进进程程的的进进程程优优先先,以以减减少少各各进进程程的的周周转转时时间间。对对于于分分时系统时系统,更多地采用时间片轮转。更多地采用时间片轮转。(3)进行进程上下文的切换进行进程上下文的切换 当进程调度选中一个进程占有当进程调度选中一个进程占有CPU时时,进程调度进程调度程序要做的主要工作则是进行进程上下文切换程序要做的主要工作则是进行进程上下文切换:将正在将正在执行进程的
8、运行现场保留在该进程的执行进程的运行现场保留在该进程的PCB中中,以便以后以便以后该进程恢复执行。将刚选中进程的运行现场恢复起来该进程恢复执行。将刚选中进程的运行现场恢复起来,并将并将CPU的控制权交给被选中进程的控制权交给被选中进程,使其执行。使其执行。砖烛沙题襄镣柔秀医侦甫脊皇恰岳仪仇恳伊势酪桶昧滑孪绎棍喻镶浅茹纤第3章处理机调度第3章处理机调度2.进程调度方式进程调度方式 (1)非抢占方式非抢占方式(Non preemptive mode)在非抢占方式下在非抢占方式下,调度程序一旦把调度程序一旦把 CPU分配给某分配给某一进程后便让它一直运行下去一进程后便让它一直运行下去,直到进程完成或
9、发生直到进程完成或发生某事件而不能运行时，才将某事件而不能运行时，才将CPU分给其它进程。分给其它进程。这种调度方式通常用在批处理系统中。它的主要这种调度方式通常用在批处理系统中。它的主要优点是简单、系统开销小。优点是简单、系统开销小。(2)抢占方式抢占方式(Preemptive mode)当一个进程正在执行时，系统可以基于某种策略当一个进程正在执行时，系统可以基于某种策略剥夺剥夺CPU给其它进程。剥夺的原则有：给其它进程。剥夺的原则有：优先权原则、短进程优先原则、时间片原则。优先权原则、短进程优先原则、时间片原则。显然这种调度方式多用在分时系统和实时系统中，显然这种调度方式多用在分时系统和实
10、时系统中，以便及时响应各进程的请求。以便及时响应各进程的请求。遥胯患蜒捎库集销邓派盲栋滞桶瓮香渭继找寻闪糕挪溶攒卑读猪讯蓄裴童第3章处理机调度第3章处理机调度3.进程调度的时机进程调度的时机 所谓进程调度的时机，是指什么情况下引起进程所谓进程调度的时机，是指什么情况下引起进程调度程序工作。进程调度的时机是与进程调度的方式调度程序工作。进程调度的时机是与进程调度的方式有关的。进程调度的时机如下：有关的。进程调度的时机如下：1)正在执行的进程正确完成正在执行的进程正确完成,或由于某种错误而终或由于某种错误而终止运行止运行(陷阱或中断陷阱或中断)；2)执行中的进程提出执行中的进程提出I/O请求请求,
11、等待等待I/O完成时完成时;3)在分时系统中在分时系统中,按照时间片轮转按照时间片轮转,分给进程的时分给进程的时间片用完时；间片用完时；4)按照优先级调度时按照优先级调度时,有更高优先级进程变为就绪有更高优先级进程变为就绪时时(抢占方式抢占方式)；5)在进程通讯中在进程通讯中,执行中的进程执行了某种原语操执行中的进程执行了某种原语操作作,如如wait操作、阻塞原语和唤醒原语时操作、阻塞原语和唤醒原语时,都可都可能引起进程调度。能引起进程调度。梧眨芽棕扰檄盐砷耀涵邻魄枷蠕挞塞扦振鹤献扇砰棚置趣稚邻童匆塘袒在第3章处理机调度第3章处理机调度三三.中级调度中级调度(中程调度中程调度)中级调度使暂时停
12、止的进程不再占用宝贵中级调度使暂时停止的进程不再占用宝贵的内存资源的内存资源,将它们调到外存上去成为挂起状将它们调到外存上去成为挂起状态。当处于挂起就绪的进程重新具备运行条件态。当处于挂起就绪的进程重新具备运行条件且内存稍有空闲时且内存稍有空闲时,中级调度将它重新调入内中级调度将它重新调入内存存,挂在活动就绪队列上等待进程调度。中级挂在活动就绪队列上等待进程调度。中级调度实质上就是存储管理中的对换功能。调度实质上就是存储管理中的对换功能。进程调度频率最高进程调度频率最高(10100ms/次次)调度算法调度算法简单快速简单快速;作业调度频率最低约几分钟一次作业调度频率最低约几分钟一次,调调度算法
13、允许花费较多的时间度算法允许花费较多的时间;中级调度介于两中级调度介于两者之间。者之间。彻注悦泊绳阶丙钝瘩无嘲狄芋闭妮糜椒化智乙畴坐城煌殊驭煌橱刺单窖塔第3章处理机调度第3章处理机调度3.1.2.调度队列模型调度队列模型1.仅有进程调度的仅有进程调度的调度队列模型调度队列模型 在分时系统中在分时系统中,通常仅通常仅有进程调度有进程调度,采用采用FIFO算法。算法。CPU就就 绪绪 队队 列列阻阻 塞塞 队队 列列时间片完时间片完进程调度进程调度等待事件等待事件事件事件出现出现交互用户交互用户完成完成物澎砰幕监摹碴彝姆瘁脖琵缄湾宜衣涅颁急酗泥寸村忱史型兜曝荚瞄彪荔第3章处理机调度第3章处理机调度
14、2.具有高级和低级调度的具有高级和低级调度的调度队列模型调度队列模型 在批处理系统中在批处理系统中,不仅需要不仅需要进程调度而且需进程调度而且需要作业调度。要作业调度。CPU就就 绪绪 队队 列列阻阻 塞塞 队队 列列时间片完时间片完进程进程调度调度事件事件1出现出现 后备后备队列队列完成完成阻阻 塞塞 队队 列列事件事件2出现出现 阻阻 塞塞 队队 列列事件事件n出现出现.等待事件等待事件1等待事件等待事件2等待事件等待事件n作业作业调度调度炳凡水猾畏嫌奖至扫仑舅指湍皖醒梭削宾仍呼坷茁炽团烤属孙献兵辆捞还第3章处理机调度第3章处理机调度3.具有三级调度的具有三级调度的调度队列模型调度队列模型
15、 在在具有三级调度具有三级调度系统中系统中,增加了在外存的挂起状态增加了在外存的挂起状态CPUCPU就就 绪绪 队队 列列就就 绪绪 挂挂 起起 时间片完时间片完进程进程调度调度事事件件出出现现后备后备队列队列完成完成阻阻 塞塞 挂挂 起起阻阻 塞塞 队队 列列 挂起挂起等待事件等待事件作业作业调度调度事件出现事件出现中级中级调度调度交互作业交互作业调出调出碰紊郸通兄筏仑筏衫料异幅邓余代馒卞邪站估亲超设词稳栓办跨皖尖锭醉第3章处理机调度第3章处理机调度 对于不同的系统对于不同的系统,有不同的设计目标有不同的设计目标,采用不同采用不同的调度算法。调度算法实质上是个策略问题的调度算法。调度算法实质
16、上是个策略问题面向用户的准则：面向用户的准则：l 周转时间短周转时间短l 交互式系统的响应时间快交互式系统的响应时间快l 截止时间保证截止时间保证l 优先权准则优先权准则(公平合理公平合理)面向系统的准则：面向系统的准则：l 单位时间内运行尽可能多的进程单位时间内运行尽可能多的进程,吞吐量高吞吐量高l 使处理机尽可能保持使处理机尽可能保持“忙碌忙碌”利用率高利用率高l 使内外存、使内外存、I/O设备得以均衡、充分利用设备得以均衡、充分利用3.1.3.调度算法的评价准则调度算法的评价准则撵轨省殊锥平矾撂侵宇腿贵的毕侯缸待录肺修贝肠噪望编络锐供坡始职涟第3章处理机调度第3章处理机调度进程进程(作业
17、作业)平均周转时间平均周转时间（周转时间、（周转时间、吞吐量）吞吐量）设某进程创建时间为设某进程创建时间为Si,结束的时间为结束的时间为Ei 它的周转时间它的周转时间(全过程所用时间全过程所用时间)为为 Ti=Ei Si 系统为它提供的实际服务时间为系统为它提供的实际服务时间为Tsi 则进程平均周转时间则进程平均周转时间T,带权平均周转时间带权平均周转时间W为：为：T W=其中，其中，n为被测定进程流中的进程数为被测定进程流中的进程数 ni=1Tin1 ni=1Tin1Tsi 要设计一个理想的调度算法是一件十分困难的事要设计一个理想的调度算法是一件十分困难的事,在实际系统中在实际系统中,调度算
18、法往往折衷考虑。调度算法往往折衷考虑。大多数操作系统都采用比较简单的调度算法大多数操作系统都采用比较简单的调度算法挟矛袭读阑赌查幼似曹善肪壳黎甩绣悍蛀狐蒲餐斌北乓述耻完骨职湍颓拭第3章处理机调度第3章处理机调度3.2 调度算法调度算法1.先进先出调度算法先进先出调度算法(FIFO)(先来先服务先来先服务FCFS)作业调度按照进入后备队列的先后次序调度作业调度按照进入后备队列的先后次序调度,进程进程调度按照进入进程就绪队列的先后次序来调度调度按照进入进程就绪队列的先后次序来调度 优点优点:实现简单实现简单 缺点缺点:不利于短作业不利于短作业(进程进程),紧迫性作业紧迫性作业(进程进程)得不得不到
19、及时处理到及时处理2.短作业短作业(进程进程)优先调度算法优先调度算法(SJF,SPF)选择就绪队列中估计运行时间最短的进程投入运行选择就绪队列中估计运行时间最短的进程投入运行 优点优点:平均周转时间平均周转时间,带权平均周转时间都改善带权平均周转时间都改善 缺点缺点:对长作业对长作业(进程进程)非常不利非常不利 不能保证紧迫性作业不能保证紧迫性作业(进程进程)得到及时处理得到及时处理 估计运行时间不准确估计运行时间不准确半已淤殊撰汪缝雌兢琐惭撑床盆乓恩响悦岿必种穴株竿霉庄惦嘉宋棱掺端第3章处理机调度第3章处理机调度3.优先权调度算法优先权调度算法(HPFHighest Priority Fi
20、rst)优先选择就绪队列中优先权最高的进程投入运行优先选择就绪队列中优先权最高的进程投入运行非抢占式优先权算法非抢占式优先权算法:仅在事件发生放弃处理机时仅在事件发生放弃处理机时抢占式优先权算法抢占式优先权算法:可将正在运行的运行权剥夺可将正在运行的运行权剥夺 优先权的类型优先权的类型静态优先权静态优先权:在进程创建时指定优先权在进程创建时指定优先权,在进程运行在进程运行时优先数不变时优先数不变动态优先权动态优先权:在进程创建时创立一个优先权，但在在进程创建时创立一个优先权，但在其生命周期内优先数可以动态变化。如等待时间长其生命周期内优先数可以动态变化。如等待时间长优先数可改变优先数可改变 确
21、定优先权的依据确定优先权的依据进程类型、对资源的需求、根据用户要求进程类型、对资源的需求、根据用户要求檬搭婿戒延飘骄捍郁抽装姿籽皑共线嗅抠测嚏锹铣釜草砸灭剪烤萝鸦苑棉第3章处理机调度第3章处理机调度4.高响应比优先调度算法：高响应比优先调度算法：改进短作业改进短作业(进程进程)优先调度算法优先调度算法,优先权用下式优先权用下式动态计算出来动态计算出来 优先权优先权=上式可看出上式可看出 等待时间相同要求服务的时间越短优先权越高等待时间相同要求服务的时间越短优先权越高,有利于短作业有利于短作业 要求服务时间相同要求服务时间相同,等待时间越长优先权越高等待时间越长优先权越高,近近似于先来先服务似于
22、先来先服务 长作业的优先权会随等待时间加长而升高长作业的优先权会随等待时间加长而升高,长作长作业也会得到执行业也会得到执行等待时间等待时间+要求服务时间要求服务时间 响应时间响应时间 要求服务时间要求服务时间 要求服务时间要求服务时间芋悸淮莹藩驻芭鸵辫赦吩猿聊暮台呐开幅设辨卷窄芒播位送料咐脂征粟惊第3章处理机调度第3章处理机调度 把把CPU划分成若干时间片划分成若干时间片,并且按顺序赋给就绪并且按顺序赋给就绪队列中的每一个进程，进程轮流占有队列中的每一个进程，进程轮流占有CPU，当时间，当时间片用完时，即使进程未执行完毕，系统也剥夺该进片用完时，即使进程未执行完毕，系统也剥夺该进程的程的CPU
23、，将该进程排在就绪队列末尾。同时系统，将该进程排在就绪队列末尾。同时系统选择另一个进程运行选择另一个进程运行 分时系统中常用时间片轮转法分时系统中常用时间片轮转法时间片选择问题：时间片选择问题：固定时间片、可变时间片固定时间片、可变时间片确定时间片大小的因素：确定时间片大小的因素：系统响应时间、就绪进程个数、系统响应时间、就绪进程个数、CPU能力能力 5.时间片轮转调度算法时间片轮转调度算法诸茨枣吧矮治盛量爪患毗牺萌述爬魔琅惮孙奇赫钉扬嗅博獭闰喳勃酉畅脏第3章处理机调度第3章处理机调度6.多队列反馈调度算法：多队列反馈调度算法：系统按优先级设置多级就绪队列第一级优先级最高系统按优先级设置多级就
24、绪队列第一级优先级最高 各就绪队列分配不同的时间片各就绪队列分配不同的时间片,优先级高的第一级优先级高的第一级队列时间片最小队列时间片最小,随着队列优先级的降低随着队列优先级的降低,时间片加时间片加大大 各个队列按照先进先出调度算法各个队列按照先进先出调度算法 一个新进程就绪后进入第一级就绪队列一个新进程就绪后进入第一级就绪队列 进程由于等待事件而放弃进程由于等待事件而放弃CPU后后,进入等待队列进入等待队列,一一旦等待的事件发生旦等待的事件发生,则回到原来的就绪队列则回到原来的就绪队列 当有一个优先级更高的进程就绪时当有一个优先级更高的进程就绪时,可以抢占可以抢占CPU,被抢占进程回到原来一
25、级就绪队列末尾被抢占进程回到原来一级就绪队列末尾 当第一级队列空时当第一级队列空时,就去调度第二级队列就去调度第二级队列,如此类推如此类推 时间片用完后进程放弃时间片用完后进程放弃CPU,进入下一级就绪队列进入下一级就绪队列秦述鸽踊汪寄汝倘继蒙郡拄语孜勋辫嘛契井妖壳驮凤滩姥欠带淘砷蹦心鳞第3章处理机调度第3章处理机调度 实时系统中实时系统中,对实时进程的调度有截止时间的要求对实时进程的调度有截止时间的要求1.实现实时调度的基本条件实现实时调度的基本条件 1)提供必要的信息提供必要的信息 就绪时间就绪时间、开始截止时间开始截止时间或或完成截止时间完成截止时间、处理时处理时间间、资源要求资源要求、
26、优先级优先级(硬实时任务赋绝对优先级硬实时任务赋绝对优先级)。2)系统处理速度快系统处理速度快 若系统中有若系统中有m 个周期性硬实时任务个周期性硬实时任务,处理时间为处理时间为Ci周期时间为周期时间为Pi,则处理机处理速度应达到可调度条件则处理机处理速度应达到可调度条件:1 (单处理机单处理机)n (多处理机多处理机)3)采用抢占式调度机制以满足对截止时间的要求采用抢占式调度机制以满足对截止时间的要求 4)具有快速切换机制具有快速切换机制:快速中断响应、快速任务分派快速中断响应、快速任务分派3.3 实时调度实时调度CiPii=1nCiPii=1n掌讼镑塞伟觉例镜茶迁飞窘煽埃铸访采姿烈寿脚铸蔗
27、幻坎身径窖迸意幼瓣第3章处理机调度第3章处理机调度2.实时调度算法的分类实时调度算法的分类 1)非抢占式调度算法非抢占式调度算法 非抢占式轮转调度算法非抢占式轮转调度算法(响应时间数秒到数十秒响应时间数秒到数十秒)轮转一圈后调度轮转一圈后调度 非抢占式优先权调度算法非抢占式优先权调度算法(响应时间数百毫秒响应时间数百毫秒)当前进程完成当前进程完成(或被阻塞或被阻塞)后调度后调度 2)抢占式调度算法抢占式调度算法 严格要求的实时系统严格要求的实时系统,响应时间在数十毫秒以内响应时间在数十毫秒以内 基于时钟中断的抢占式调度算法基于时钟中断的抢占式调度算法 时钟中断到来时调度时钟中断到来时调度 立即
28、抢占的优先权调度算法立即抢占的优先权调度算法 立即剥夺当前进程立即剥夺当前进程 调度时间见调度时间见P 83 图图3-6箕凉壳宠画痉售秸篱扮继携蚊诛匡厕褐诚畴悔恤猪页琢肆脆酮杨泛蘑鹿臼第3章处理机调度第3章处理机调度3.几种常见的实时调度算法几种常见的实时调度算法 1)最早截止时间优先算法最早截止时间优先算法(Earliest Deadline First)根据任务的开始截止时间确定优先级。根据任务的开始截止时间确定优先级。2)最低松弛度优先算法最低松弛度优先算法(Least Laxity First)根据任务的松弛度根据任务的松弛度(紧急程度紧急程度)确定优先级确定优先级 根据任务完成截止时
29、间和根据任务完成截止时间和本身运行时间本身运行时间确定松弛度确定松弛度 松弛度松弛度=必须完成时间必须完成时间-本身运行时间本身运行时间-当前时间当前时间 P 85 图图 3-9座妖绑弦逮晚履菌鞭砷铰钻惩沥墅嚏砍柞鸭拘阔棠靡策宾筛斩淋注砸羚耶第3章处理机调度第3章处理机调度 保存现场保存现场:顺序保存进程的上下文顺序保存进程的上下文,包括程序计包括程序计数器和其它寄存器数器和其它寄存器 用新状态和相关信息更新正在运行进程的用新状态和相关信息更新正在运行进程的PCB 把该进程移至合适的队列把该进程移至合适的队列-就绪、阻塞就绪、阻塞 选择另一个要执行的进程选择另一个要执行的进程,更新该进程的更新
30、该进程的PCB 从被选中进程中重装入从被选中进程中重装入 CPU 上下文上下文,恢复现场恢复现场 若无就绪进程若无就绪进程,系统会安排一个闲逛进程系统会安排一个闲逛进程(idle),一直运行一直运行,在执行过程中可接收中断。在执行过程中可接收中断。3.4 CPU调度的实现调度的实现彻租巍尘唱曰胎幻绞葬浩苑建连霸堆嵌蹦文绥矫左荧班砒炬都氢剧泪汽荚第3章处理机调度第3章处理机调度操作系统的核心操作系统的核心 向上提供无中断的虚拟机器向上提供无中断的虚拟机器,在核心内不允许中断在核心内不允许中断特点特点:核心常驻内存核心常驻内存,短小精焊短小精焊,为进程运行提供舞台为进程运行提供舞台 核心的组成核心
31、的组成中断处理中断处理:时钟、时钟、I/O、虚拟存储器、虚拟存储器进程管理进程管理:调度调度 控制控制 通讯通讯 互斥互斥 同步等同步等原语管理原语管理:提供一系列原语提供一系列原语,同步同步,通信通信,创建创建,撤消等撤消等队列管理队列管理:中断之后调度之前中断之后调度之前(运行运行-就绪就绪-等待队列等待队列)现场管理现场管理:保存现场、恢复现场保存现场、恢复现场时钟管理时钟管理:绝对时钟、间隔时钟、绝对时钟、间隔时钟、虚时钟虚时钟囚不咏森迷秉焰遁赛沂纫抡掳沧炸石饰龙我乡伦魔漾淳崭营固钵列绣功非第3章处理机调度第3章处理机调度 保存现场、分析中断源保存现场、分析中断源 处理中断处理中断原语
32、管理、队列管理、时钟管理、进程调度原语管理、队列管理、时钟管理、进程调度 恢复现场恢复现场中断中断核心入口核心入口核心处理流程核心处理流程 唯一入口唯一入口:中断中断,由硬件完成由硬件完成 作业作业:P101 2,3,5颜针鬼脖妊饼蝗胎措晨撵室础贺刺盯汁疼曾仲氯荣渝旱昌孩滑搐云实盘帛第3章处理机调度第3章处理机调度3.5死锁死锁死锁的基本概念死锁的基本概念死锁的解决方案死锁的解决方案 （预防，避免，检测及解除）（预防，避免，检测及解除）资源分配图资源分配图熙竭脏挡妨汾快呼妹枫所绝花瞪胰蚜蝇辆闻潭拷墅碎辙菌嫌查猪牌攫陪借第3章处理机调度第3章处理机调度3.5.1 死锁的基本概念死锁的基本概念死锁
33、死锁(Deadlock)的定义：的定义：一组进程中，每个进程都无限一组进程中，每个进程都无限等待等待被该组被该组进程中进程中另一进程所占有的资源另一进程所占有的资源，因而永远无法，因而永远无法得到的资源，这种现象称为进程死锁，这一组得到的资源，这种现象称为进程死锁，这一组进程就称为死锁进程进程就称为死锁进程说明说明:参与死锁的进程最少是两个参与死锁的进程最少是两个参与死锁的进程至少有两个已经占有资源参与死锁的进程至少有两个已经占有资源参与死锁的所有进程都在等待资源参与死锁的所有进程都在等待资源注意：注意：如果死锁发生，会浪费大量系统资源，如果死锁发生，会浪费大量系统资源，甚至导致系统崩溃。甚至
34、导致系统崩溃。灭凸均椽竖寂号寡断馋山华钝蚊膀锑嘱埋边蝗砚营轮暖恶摔噬床栖冲风酬第3章处理机调度第3章处理机调度死锁产生的原因死锁产生的原因1.竞争资源引起竞争资源引起永久性资源永久性资源:可被多个进程多次使用可被多个进程多次使用(可再用资源可再用资源)剥夺性资源剥夺性资源(CPU、内存）、内存）非剥夺性资源非剥夺性资源(磁带机、打印机磁带机、打印机)竞争非剥夺性资源会引起死锁竞争非剥夺性资源会引起死锁临时性资源临时性资源:只可使用一次的资源；只可使用一次的资源；如信号量如信号量,中断信号中断信号,同步信号等同步信号等(可消耗性资源可消耗性资源)竞争临时性资源也会引起死锁竞争临时性资源也会引起死
35、锁2.进程推进顺序不当引起进程推进顺序不当引起 对资源采用对资源采用“申请申请-分配分配-使用使用-释放释放”模式模式,由于推进顺序不当两进程都要申请对方已占有的资由于推进顺序不当两进程都要申请对方已占有的资源源狠缆耘梦杠躇啦韶弛赴粪霸匣磺普龚全翌恫龟境癣静文淄手碰亲闰栖厂暂第3章处理机调度第3章处理机调度P1：申请打印机申请打印机申请扫描仪申请扫描仪使用使用释放打印机释放打印机释放扫描仪释放扫描仪P2：申请扫描仪申请扫描仪申请打印机申请打印机使用使用释放打印机释放打印机释放扫描仪释放扫描仪死锁的例子死锁的例子:竞争非剥夺性资源进程推进顺序不当引起死锁竞争非剥夺性资源进程推进顺序不当引起死锁臀
36、宿攫挺雍桩萌酋咆绒醚噬柳臃庶碰率拒渊癸甫幻易弗滨牛栖憾泻甘中况第3章处理机调度第3章处理机调度Req(R1)Req(R2)Rel(R1)Rel(R2)Rel(R1)Rel(R2)Req(R1)Req(R2)P2P1不安全区不安全区竞争非剥夺性资源竞争非剥夺性资源推进顺序不当推进顺序不当进入进入不安全区不安全区蚌渤牡掩丹挝份苯遣耪或鲁喇许鹅摆郭喂良受垛绘珐尉审勤谅盈硫厦浚亮第3章处理机调度第3章处理机调度3.5.2产生死锁的四个必要条件产生死锁的四个必要条件1)互斥条件（资源独占）：互斥条件（资源独占）：一个资源每次只能给一个进程使用一个资源每次只能给一个进程使用2)请求和保持条件请求和保持条件
37、:(部分分配部分分配,占有申请占有申请)在申请新资源的同时保持对原有资源的占有在申请新资源的同时保持对原有资源的占有3)不可剥夺条件（不可强占）：不可剥夺条件（不可强占）：资源申请者不能强行的从资源占有者手中夺资源申请者不能强行的从资源占有者手中夺取资源取资源,资源只能由占有者自愿释放资源只能由占有者自愿释放4)循环等待条件：循环等待条件：存在进程存在进程-等待资源环形链等待资源环形链 P1,P2,Pn,其中其中P1等待等待P2占有的资源占有的资源,P2等待等待P3占有的资源占有的资源,Pn等待等待P1占有的资源。占有的资源。傀季筋刘旧淆选焚镊璃葬陪暮富融私徊陕宜悲茬帆蹿挖他幢神外论惜券昏第3
38、章处理机调度第3章处理机调度3.6 死锁的预防死锁的预防 3.6.1 强限制预防强限制预防 确定资源分配算法确定资源分配算法,保证不发生死锁。做法保证不发生死锁。做法是破坏产生死锁的四个必要条件之一。是破坏产生死锁的四个必要条件之一。1.破坏破坏“请求和保持请求和保持(部分分配部分分配)”条件条件 每个进程运行前必须一次性申请运行期所需每个进程运行前必须一次性申请运行期所需全部资源全部资源,若所需资源均可满足则全部分配。该若所需资源均可满足则全部分配。该进程运行中不再请求资源进程运行中不再请求资源,屏弃请求条件。屏弃请求条件。简单、安全简单、安全;但资源利用率低但资源利用率低,要长期等待。要长
39、期等待。2.破坏破坏“不可剥夺不可剥夺”条件条件 在允许进程动态申请资源前提下在允许进程动态申请资源前提下,规定规定:某某进程在申请新的资源不能立即满足而被阻塞之进程在申请新的资源不能立即满足而被阻塞之前前,必须释放已占有的资源必须释放已占有的资源(可能造成前一段工可能造成前一段工作失效作失效),若需要再重新申请若需要再重新申请(增加开销增加开销)。桐衰冰咨鹃辽辜乞甜哥列撅懂休异鱼逝砷影癌炸赎葛耙肆太驾露宛吁道钦第3章处理机调度第3章处理机调度3.破坏破坏“循环等待循环等待”条件条件 采用资源有序分配法采用资源有序分配法:允许进程动态申请允许进程动态申请资源资源,对系统中所有资源编号对系统中所
40、有资源编号,进程申请资源进程申请资源时应严格按资源编号递增次序进行时应严格按资源编号递增次序进行,否则不予否则不予分配。分配。P1：申请申请1申请申请3申请申请4P2：申请申请2申请申请4申请申请8Pn：申请申请1申请申请2申请申请8缺点缺点:资源利用仍不充分资源利用仍不充分愉勿熟衷勋崖炎煽祷忠宠愧云饱华重墨游嘲郁堪翰歇刊冈勿喀颅肩愿析烘第3章处理机调度第3章处理机调度3.6.2 避免死锁的避免死锁的银行家银行家算法算法 前面的三种方法由于前面的三种方法由于限制太强限制太强,资源利用率资源利用率都不太高。能否放宽限制条件？都不太高。能否放宽限制条件？E.W.Dijkstra于于1968年提出年
41、提出银行家算法银行家算法,此此算法要事先知道每个进程对资源的最大需求量算法要事先知道每个进程对资源的最大需求量;算法的基本思路算法的基本思路:允许进程动态申请资源允许进程动态申请资源,但在但在每次分配资源前先对本次分配的安全性进行检每次分配资源前先对本次分配的安全性进行检查查,以判断这种分配是否可能导致死锁以判断这种分配是否可能导致死锁,若分配若分配可能导致系统死锁可能导致系统死锁,则不予分配则不予分配,否则分配该资否则分配该资源。源。(检查每次分配后是否仍存在安全分配检查每次分配后是否仍存在安全分配序列序列)显然显然,此法避免了死锁且资源利用率高。此法避免了死锁且资源利用率高。斗忆摊狐捆调枚
42、疙棒焰将甘社独观赐砸弊惯力缄量哉扫弄贵惨昆扒锄昨完第3章处理机调度第3章处理机调度1.安全序列：安全序列：如果进程序列如果进程序列P1，Pn对每个对每个Pi(1in)进进程程,它以后尚需要的资源量不超过系统当前剩余资源它以后尚需要的资源量不超过系统当前剩余资源量与所有量与所有Pj(j Available(2,3,0),让让P4等待等待4)若若P0请求资源请求资源,发出请求向量发出请求向量Request(0,2,0)假定分配假定分配,资源为资源为:检查此刻的安全性：检查此刻的安全性：Available(2,1,0)已不满足任何已不满足任何进程的需要进程的需要,不安全不安全;不予分配不予分配Ava
43、ilable 仍为仍为(2,3,0)。Max Allocation Need Available 进程进程 A B C A B C A B C A B C P0 7 5 3 0 3 0 7 2 3 2 1 0 P1 3 2 2 2 0 0 1 2 2 P2 9 0 2 3 0 2 6 0 0 P3 2 2 2 2 1 1 0 1 1 P4 4 3 3 0 0 2 4 3 1蛊狱拱疚慰抖焚卓知衣山链惜灸谱桓二抽牧猪钳措断帽选忌宵迄肘钒宵园第3章处理机调度第3章处理机调度检查此刻的安全性检查此刻的安全性 Max Allocation Need Available 进程进程 A B C A B C
44、A B C A B C P0 7 5 3 0 2 0 7 3 3 2 2 0 P1 3 2 2 3 0 2 0 2 0 P2 9 0 2 3 0 2 6 0 0 P3 2 2 2 2 1 1 0 1 1 P4 4 3 3 0 0 2 4 3 1安全安全,可将可将(0,1,0)分配给分配给P0若将若将P0请求改为请求改为Request(0,1,0)假定分配假定分配,资源变为资源变为:进进 Work Allocation Need W+A Finish 程程 A B C A B C A B C A B C P1 2 2 0 3 0 2 0 2 0 5 2 2 trueP3 5 2 2 2 1 1
45、0 1 1 7 3 3 trueP4 7 3 3 0 0 2 4 3 1 7 3 5 trueP0 7 3 5 0 2 0 7 3 3 7 5 5 trueP2 7 5 5 3 0 2 6 0 0 10 5 7 true匈祟度贺锗侍蹄留中垄驻奖汐钳畦友琶蔑历闯鳖咱接沽冷舆价烷盒饱血安第3章处理机调度第3章处理机调度3.7 死锁的检测与解除死锁的检测与解除 允许死锁发生，系统必须提供检测和解除死锁允许死锁发生，系统必须提供检测和解除死锁的手段的手段,操作系统应不断监视系统进展情况，判断操作系统应不断监视系统进展情况，判断死锁是否发生。死锁是否发生。烩蒂德看记骏厅裕嘲尤且薄删蒸奉康爪励脐病示阂腑厘
46、栽风嚷砰虱诛老跋第3章处理机调度第3章处理机调度3.7.1死锁的检测死锁的检测1.资源分配图资源分配图用有向图描述进程的死锁用有向图描述进程的死锁:准确、形象准确、形象 系统由若干类资源构成，一类资源称为一个资源类；系统由若干类资源构成，一类资源称为一个资源类；每个资源类中包含若干个同种资源，称为资源实例。每个资源类中包含若干个同种资源，称为资源实例。二元组二元组G=（V，E）V：结点集，分为：结点集，分为P，R两部分两部分 P=p1,p2,pn R=r1,r2,rm E：边的集合：边的集合,其元素为有序二元组其元素为有序二元组 分配边分配边(rj,pi):资源实例资源实例进程的一条有向边进程
47、的一条有向边申请边申请边(pi,rj):进程进程资源类的一条有向边资源类的一条有向边卑草讫陆丑魏合舷源州受熔能喝蟹前缄氓查儿瞅涉呛谋酵源琶哑扑殆胎抿第3章处理机调度第3章处理机调度有环有死锁毁痔扮廉玻脐醉案穿忱寄渗摘蜜实袱娟漫鸡敦标缎啸楞莉眼织器证孽喉蔑第3章处理机调度第3章处理机调度有环无死锁幸莱溃枝韵灰弓呆碎逢抠驳褂惫藕挤痪袒纱黄蚤掏遥孙攒赶茹链鲁烛邹霓第3章处理机调度第3章处理机调度2.死锁定理死锁定理 如果资源分配图中没有环路如果资源分配图中没有环路,则系统中没有死锁则系统中没有死锁,如果图中存在环路则系统中可能存在死锁。如果图中存在环路则系统中可能存在死锁。如果每个资源类中只包含一个
48、资源实例如果每个资源类中只包含一个资源实例,则资源则资源分配图环路是死锁存在的充分必要条件。分配图环路是死锁存在的充分必要条件。资源分配图化简方法：资源分配图化简方法：1）找一个非孤立点进程结点且只有分配边，去掉分）找一个非孤立点进程结点且只有分配边，去掉分配边，将其变为孤立结点。配边，将其变为孤立结点。2）再把相应的资源分配给一个等待该资源的进程，）再把相应的资源分配给一个等待该资源的进程，即将某进程的申请边变为分配边。即将某进程的申请边变为分配边。3）重复）重复(1)(2)操作直到无法再化简操作直到无法再化简,若所有若所有结点都结点都为孤立结点则无为孤立结点则无死锁死锁,否则死锁发生否则死
49、锁发生鼎滚里何蚂亿迂酱殉仅差蓉倚咽股慷亥柬详扩垮表杨简诣膘沮锹淋摈办攻第3章处理机调度第3章处理机调度3.7.2死锁的解除死锁的解除 一旦死锁发生则采取专门的措施，解除一旦死锁发生则采取专门的措施，解除死锁并以最小的代价恢复操作系统运行。死锁并以最小的代价恢复操作系统运行。死锁的解除死锁的解除(关键是代价最小关键是代价最小)：1）重新启动）重新启动2）撤消进程）撤消进程3）剥夺资源）剥夺资源4）进程回退）进程回退垒攫灰困细趴响违符俏镭逸满堪拖持谬莱绿瓶禁豹澈栖誉庭哥身武苛蹈蓟第3章处理机调度第3章处理机调度1.处理机调度处理机调度 (1)高级调度高级调度(作业调度接纳调度或长程调度作业调度接纳
50、调度或长程调度)将后备队列中作业调入内存将后备队列中作业调入内存,并创建进程。并创建进程。(2)低级调度低级调度(进程调度进程调度,短程调度短程调度)从就绪队列中选中一进程从就绪队列中选中一进程,把把CPU使用权交给它。使用权交给它。(3)中级调度中级调度:内存紧张时将内存的进程挂起调到外存内存紧张时将内存的进程挂起调到外存 或内存稍有空闲时将它激活重新调入内存或内存稍有空闲时将它激活重新调入内存 2.进程调度方式进程调度方式 (1)非抢占方式非抢占方式(Non preemptive mode)(2)抢占方式抢占方式(Preemptive mode)3.进程调度的时机进程调度的时机 (1)执行