处理机调.pptx
《处理机调.pptx》由会员分享,可在线阅读,更多相关《处理机调.pptx(56页珍藏版)》请在咨信网上搜索。
1、要解决的问题要解决的问题WHAT:按什么原则分配按什么原则分配CPU 进程调度算法进程调度算法WHEN:何时分配何时分配CPU 进程调度的时机进程调度的时机HOW:如何分配如何分配CPU CPU调度过程(进程的上下文切换)调度过程(进程的上下文切换)一批作业从进入系统到作业运行完毕可能经历三级一批作业从进入系统到作业运行完毕可能经历三级调度调度高级、低级和中级调度。高级、低级和中级调度。一一.高级调度高级调度(High Scheduling)又称为作业调度接纳调度或长程调度又称为作业调度接纳调度或长程调度,用于批处理用于批处理系统系统,确定将外存后备队列中哪些作业调入内存确定将外存后备队列中哪
2、些作业调入内存,并为它并为它们创建进程。实时系统和分时系统的前台作业不需要作们创建进程。实时系统和分时系统的前台作业不需要作业调度。每次作业调度时业调度。每次作业调度时,都必须做出两个决定都必须做出两个决定:1)接纳多少个作业接纳多少个作业:取决于多道程序度。取决于多道程序度。2)接纳哪些作业接纳哪些作业(用什么调度算法用什么调度算法):先来先服务、短作业优先、优先权、响应比优先。先来先服务、短作业优先、优先权、响应比优先。3.1 处理机调度的基本概念处理机调度的基本概念 3.1.1 高级、低级和中级调度高级、低级和中级调度响应响应/运行运行二二.低级调度低级调度(进程调度进程调度,短程调度短
3、程调度)进程调度的任务是控制协调进程对进程调度的任务是控制协调进程对CPU的竞争的竞争,即即按照一定的调度算法从就绪队列中选中一个进程,把按照一定的调度算法从就绪队列中选中一个进程,把CPU的使用权交给被选中的进程。它是最基本的一种的使用权交给被选中的进程。它是最基本的一种调度调度,批处理系统批处理系统,实时系统和分时系统都必须有进程实时系统和分时系统都必须有进程调度。它通过进程调度程序来完成。调度。它通过进程调度程序来完成。1.进程调度程序的主要功能可描述如下:进程调度程序的主要功能可描述如下:(1)记录系统中各进程的状况记录系统中各进程的状况 为了很好地实现进程调度为了很好地实现进程调度,
4、进程调度程序首先必须进程调度程序首先必须管理系统中各进程的管理系统中各进程的PCB,将进程的状态变化及资源,将进程的状态变化及资源需求情况及时地记录到需求情况及时地记录到PCB中。通过中。通过PCB变化来准确变化来准确地掌握系统中所有进程的地掌握系统中所有进程的状态特征和执行情况状态特征和执行情况。(2)选择进程真正占有选择进程真正占有CPU 这这是是进进程程调调度度的的实实质质,即即按按照照系系统统规规定定的的调调度度策策略略从从就就绪绪队队列列中中选选择择一一个个进进程程占占有有CPU执执行行。进进程程调调度度依依据据的的算算法法与与系系统统的的设设计计目目标标相相一一致致。对对于于不不同
5、同的的系系统统,通通常常采采用用不不同同的的调调度度策策略略。对对于于批批处处理理系系统统常常采采用用短短进进程程的的进进程程优优先先,以以减减少少各各进进程程的的周周转转时时间间。对对于于分分时系统时系统,更多地采用时间片轮转。更多地采用时间片轮转。(3)进行进程上下文的切换进行进程上下文的切换 当进程调度选中一个进程占有当进程调度选中一个进程占有CPU时时,进程调度程进程调度程序要做的主要工作则是进行进程上下文切换序要做的主要工作则是进行进程上下文切换:将正在执将正在执行进程的运行现场保留在该进程的行进程的运行现场保留在该进程的PCB中中,以便以后该以便以后该进程恢复执行。将刚选中进程的运
6、行现场恢复起来进程恢复执行。将刚选中进程的运行现场恢复起来,并并将将CPU的控制权交给被选中进程的控制权交给被选中进程,使其执行。使其执行。2.进程调度方式进程调度方式 (1)非抢占方式非抢占方式(Non preemptive mode)在非抢占方式下在非抢占方式下,调度程序一旦把调度程序一旦把 CPU分配给某分配给某一进程后便让它一直运行下去一进程后便让它一直运行下去,直到进程完成或发生直到进程完成或发生某事件而不能运行时,才将某事件而不能运行时,才将CPU分给其它进程。分给其它进程。这种调度方式通常用在批处理系统中。它的主要这种调度方式通常用在批处理系统中。它的主要优点是简单、系统开销小。
7、优点是简单、系统开销小。(2)抢占方式抢占方式(Preemptive mode)当一个进程正在执行时,系统可以基于某种策略当一个进程正在执行时,系统可以基于某种策略剥夺剥夺CPU给其它进程。剥夺的原则有:给其它进程。剥夺的原则有:优先权原则、短进程优先原则、时间片原则。优先权原则、短进程优先原则、时间片原则。显然这种调度方式多用在分时系统和实时系统中,显然这种调度方式多用在分时系统和实时系统中,以便及时响应各进程的请求。以便及时响应各进程的请求。3.进程调度的时机进程调度的时机 所谓进程调度的时机,是指什么情况下引起进程所谓进程调度的时机,是指什么情况下引起进程调度程序工作。进程调度的时机是与
8、进程调度的方式调度程序工作。进程调度的时机是与进程调度的方式有关的。进程调度的时机如下:有关的。进程调度的时机如下:1)正在执行的进程正确完成正在执行的进程正确完成,或由于某种错误而终或由于某种错误而终止运行止运行(陷阱或中断陷阱或中断);2)执行中的进程提出执行中的进程提出I/O请求请求,等待等待I/O完成时完成时;3)在分时系统中在分时系统中,按照时间片轮转按照时间片轮转,分给进程的时分给进程的时间片用完时;间片用完时;4)按照优先级调度时按照优先级调度时,有更高优先级进程变为就绪有更高优先级进程变为就绪时时(抢占方式抢占方式);5)在进程通讯中在进程通讯中,执行中的进程执行了某种原语操执
9、行中的进程执行了某种原语操作作,如如wait操作、阻塞原语和唤醒原语时操作、阻塞原语和唤醒原语时,都可能都可能引起进程调度。引起进程调度。三三.中级调度中级调度(中程调度中程调度)中级调度使暂时停止的进程不再占用宝贵中级调度使暂时停止的进程不再占用宝贵的内存资源的内存资源,将它们调到外存上去成为挂起状将它们调到外存上去成为挂起状态。当处于挂起就绪的进程重新具备运行条件态。当处于挂起就绪的进程重新具备运行条件且内存稍有空闲时且内存稍有空闲时,中级调度将它重新调入内中级调度将它重新调入内存存,挂在活动就绪队列上等待进程调度。中级挂在活动就绪队列上等待进程调度。中级调度实质上就是存储管理中的对换功能
10、。调度实质上就是存储管理中的对换功能。进程调度频率最高进程调度频率最高(10100ms/次次)调度算法调度算法简单快速简单快速;作业调度频率最低约几分钟一次作业调度频率最低约几分钟一次,调调度算法允许花费较多的时间度算法允许花费较多的时间;中级调度介于两中级调度介于两者之间。者之间。3.1.2.调度队列模型调度队列模型1.仅有进程调度的仅有进程调度的调度队列模型调度队列模型 在分时系统中在分时系统中,通常仅通常仅有进程调度有进程调度,采用采用FIFO算法。算法。CPU就就 绪绪 队队 列列阻阻 塞塞 队队 列列时间片完时间片完进程调度进程调度等待事件等待事件事件事件出现出现交互用户交互用户完成
11、完成2.具有高级和低级调度的具有高级和低级调度的调度队列模型调度队列模型 在批处理系统中在批处理系统中,不仅需要不仅需要进程调度而且需进程调度而且需要作业调度。要作业调度。CPU就就 绪绪 队队 列列阻阻 塞塞 队队 列列时间片完时间片完进程进程调度调度事件事件1出现出现 后备后备队列队列完成完成阻阻 塞塞 队队 列列事件事件2出现出现 阻阻 塞塞 队队 列列事件事件n出现出现.等待事件等待事件1等待事件等待事件2等待事件等待事件n作业作业调度调度3.具有三级调度的具有三级调度的调度队列模型调度队列模型 在在具有三级调度具有三级调度系统中系统中,增加了在外存的挂起状态增加了在外存的挂起状态CP
12、UCPU就就 绪绪 队队 列列就就 绪绪 挂挂 起起 时间片完时间片完进程进程调度调度事事件件出出现现后备后备队列队列完成完成阻阻 塞塞 挂挂 起起阻阻 塞塞 队队 列列 挂起挂起等待事件等待事件作业作业调度调度事件出现事件出现中级中级调度调度交互作业交互作业调出调出 对于不同的系统对于不同的系统,有不同的设计目标有不同的设计目标,采用不同采用不同的调度算法。调度算法实质上是个策略问题的调度算法。调度算法实质上是个策略问题面向用户的准则:面向用户的准则:l 周转时间短周转时间短l 交互式系统的响应时间快交互式系统的响应时间快l 截止时间保证截止时间保证l 优先权准则优先权准则(公平合理公平合理
13、)面向系统的准则:面向系统的准则:l 单位时间内运行尽可能多的进程单位时间内运行尽可能多的进程,吞吐量高吞吐量高l 使处理机尽可能保持使处理机尽可能保持“忙碌忙碌”利用率高利用率高l 使内外存、使内外存、I/O设备得以均衡、充分利用设备得以均衡、充分利用3.1.3.调度算法的评价准则调度算法的评价准则进程进程(作业作业)平均周转时间平均周转时间(周转时间、吞吐量)(周转时间、吞吐量)设某进程创建时间为设某进程创建时间为Si,结束的时间为结束的时间为Ei 它的周转时间它的周转时间(全过程所用时间全过程所用时间)为为 Ti=Ei Si 系统为它提供的实际服务时间为系统为它提供的实际服务时间为Tsi
14、 则进程平均周转时间则进程平均周转时间T,带权平均周转时间带权平均周转时间W为:为:T W=其中,其中,n为被测定进程流中的进程数为被测定进程流中的进程数 ni=1Tin1 ni=1Tin1Tsi 要设计一个理想的调度算法是一件十分困难的事要设计一个理想的调度算法是一件十分困难的事,在实际系统中在实际系统中,调度算法往往折衷考虑。调度算法往往折衷考虑。大多数操作系统都采用比较简单的调度算法大多数操作系统都采用比较简单的调度算法3.2 调度算法调度算法1.先进先出调度算法先进先出调度算法(FIFO)(先来先服务先来先服务FCFS)作业调度按照进入后备队列的先后次序调度作业调度按照进入后备队列的先
15、后次序调度,进程进程调度按照进入进程就绪队列的先后次序来调度调度按照进入进程就绪队列的先后次序来调度 优点优点:实现简单实现简单 缺点缺点:不利于短作业不利于短作业(进程进程),紧迫性作业紧迫性作业(进程进程)得不到得不到及时处理及时处理2.短作业短作业(进程进程)优先调度算法优先调度算法(SJF,SPF)选择就绪队列中估计运行时间最短的进程投入运行选择就绪队列中估计运行时间最短的进程投入运行 优点优点:平均周转时间平均周转时间,带权平均周转时间都改善带权平均周转时间都改善 缺点缺点:对长作业对长作业(进程进程)非常不利非常不利 不能保证紧迫性作业不能保证紧迫性作业(进程进程)得到及时处理得到
16、及时处理 估计运行时间不准确估计运行时间不准确3.优先权调度算法优先权调度算法(HPFHighest Priority First)优先选择就绪队列中优先权最高的进程投入运行优先选择就绪队列中优先权最高的进程投入运行非抢占式优先权算法非抢占式优先权算法:仅在事件发生放弃处理机时仅在事件发生放弃处理机时抢占式优先权算法抢占式优先权算法:可将正在运行的运行权剥夺可将正在运行的运行权剥夺 优先权的类型优先权的类型静态优先权静态优先权:在进程创建时指定优先权在进程创建时指定优先权,在进程运行在进程运行时优先数不变时优先数不变动态优先权动态优先权:在进程创建时创立一个优先权,但在在进程创建时创立一个优先
17、权,但在其生命周期内优先数可以动态变化。如等待时间长其生命周期内优先数可以动态变化。如等待时间长优先数可改变优先数可改变 确定优先权的依据确定优先权的依据进程类型、对资源的需求、根据用户要求进程类型、对资源的需求、根据用户要求4.高响应比优先调度算法:高响应比优先调度算法:改进短作业改进短作业(进程进程)优先调度算法优先调度算法,优先权用下式动优先权用下式动态计算出来态计算出来 优先权优先权=上式可看出上式可看出 等待时间相同要求服务的时间越短优先权越高等待时间相同要求服务的时间越短优先权越高,有利于短作业有利于短作业 要求服务时间相同要求服务时间相同,等待时间越长优先权越高等待时间越长优先权
18、越高,近近似于先来先服务似于先来先服务 长作业的优先权会随等待时间加长而升高长作业的优先权会随等待时间加长而升高,长作长作业也会得到执行业也会得到执行等待时间等待时间+要求服务时间要求服务时间 响应时间响应时间 要求服务时间要求服务时间 要求服务时间要求服务时间 把把CPU划分成若干时间片划分成若干时间片,并且按顺序赋给就绪并且按顺序赋给就绪队列中的每一个进程,进程轮流占有队列中的每一个进程,进程轮流占有CPU,当时间,当时间片用完时,即使进程未执行完毕,系统也剥夺该进片用完时,即使进程未执行完毕,系统也剥夺该进程的程的CPU,将该进程排在就绪队列末尾。同时系统,将该进程排在就绪队列末尾。同时
19、系统选择另一个进程运行选择另一个进程运行 分时系统中常用时间片轮转法分时系统中常用时间片轮转法时间片选择问题:时间片选择问题:固定时间片、可变时间片固定时间片、可变时间片确定时间片大小的因素:确定时间片大小的因素:系统响应时间、就绪进程个数、系统响应时间、就绪进程个数、CPU能力能力 5.时间片轮转调度算法时间片轮转调度算法6.多队列反馈调度算法:多队列反馈调度算法:系统按优先级设置多级就绪队列第一级优先级最高系统按优先级设置多级就绪队列第一级优先级最高 各就绪队列分配不同的时间片各就绪队列分配不同的时间片,优先级高的第一级队优先级高的第一级队列时间片最小列时间片最小,随着队列优先级的降低随着
20、队列优先级的降低,时间片加大时间片加大 各个队列按照先进先出调度算法各个队列按照先进先出调度算法 一个新进程就绪后进入第一级就绪队列一个新进程就绪后进入第一级就绪队列 进程由于等待事件而放弃进程由于等待事件而放弃CPU后后,进入等待队列进入等待队列,一一旦等待的事件发生旦等待的事件发生,则回到原来的就绪队列则回到原来的就绪队列 当有一个优先级更高的进程就绪时当有一个优先级更高的进程就绪时,可以抢占可以抢占CPU,被抢占进程回到原来一级就绪队列末尾被抢占进程回到原来一级就绪队列末尾 当第一级队列空时当第一级队列空时,就去调度第二级队列就去调度第二级队列,如此类推如此类推 时间片用完后进程放弃时间
21、片用完后进程放弃CPU,进入下一级就绪队列进入下一级就绪队列 实时系统中实时系统中,对实时进程的调度有截止时间的要求对实时进程的调度有截止时间的要求1.实现实时调度的基本条件实现实时调度的基本条件 1)提供必要的信息提供必要的信息 就绪时间就绪时间、开始截止时间开始截止时间或或完成截止时间完成截止时间、处理时处理时间间、资源要求资源要求、优先级优先级(硬实时任务赋绝对优先级硬实时任务赋绝对优先级)。2)系统处理速度快系统处理速度快 若系统中有若系统中有m 个周期性硬实时任务个周期性硬实时任务,处理时间为处理时间为Ci周期时间为周期时间为Pi,则处理机处理速度应达到可调度条件则处理机处理速度应达
22、到可调度条件:1 (单处理机单处理机)n (多处理机多处理机)3)采用抢占式调度机制以满足对截止时间的要求采用抢占式调度机制以满足对截止时间的要求 4)具有快速切换机制具有快速切换机制:快速中断响应、快速任务分派快速中断响应、快速任务分派3.3 实时调度实时调度CiPii=1nCiPii=1n2.实时调度算法的分类实时调度算法的分类 1)非抢占式调度算法非抢占式调度算法 非抢占式轮转调度算法非抢占式轮转调度算法(响应时间数秒到数十秒响应时间数秒到数十秒)轮转一圈后调度轮转一圈后调度 非抢占式优先权调度算法非抢占式优先权调度算法(响应时间数百毫秒响应时间数百毫秒)当前进程完成当前进程完成(或被阻
23、塞或被阻塞)后调度后调度 2)抢占式调度算法抢占式调度算法 严格要求的实时系统严格要求的实时系统,响应时间在数十毫秒以内响应时间在数十毫秒以内 基于时钟中断的抢占式调度算法基于时钟中断的抢占式调度算法 时钟中断到来时调度时钟中断到来时调度 立即抢占的优先权调度算法立即抢占的优先权调度算法 立即剥夺当前进程立即剥夺当前进程 调度时间见调度时间见P 83 图图3-63.几种常见的实时调度算法几种常见的实时调度算法 1)最早截止时间优先算法最早截止时间优先算法(Earliest Deadline First)根据任务的开始截止时间确定优先级。根据任务的开始截止时间确定优先级。2)最低松弛度优先算法最
24、低松弛度优先算法(Least Laxity First)根据任务的松弛度根据任务的松弛度(紧急程度紧急程度)确定优先级确定优先级 根据任务完成截止时间和根据任务完成截止时间和本身运行时间本身运行时间确定松弛度确定松弛度 松弛度松弛度=必须完成时间必须完成时间-本身运行时间本身运行时间-当前时间当前时间 P 85 图图 3-9 保存现场保存现场:顺序保存进程的上下文顺序保存进程的上下文,包括程序计包括程序计数器和其它寄存器数器和其它寄存器 用新状态和相关信息更新正在运行进程的用新状态和相关信息更新正在运行进程的PCB 把该进程移至合适的队列把该进程移至合适的队列-就绪、阻塞就绪、阻塞 选择另一个
25、要执行的进程选择另一个要执行的进程,更新该进程的更新该进程的PCB 从被选中进程中重装入从被选中进程中重装入 CPU 上下文上下文,恢复现场恢复现场 若无就绪进程若无就绪进程,系统会安排一个闲逛进程系统会安排一个闲逛进程(idle),一直运行一直运行,在执行过程中可接收中断。在执行过程中可接收中断。3.4 CPU调度的实现调度的实现操作系统的核心操作系统的核心 向上提供无中断的虚拟机器向上提供无中断的虚拟机器,在核心内不允许中断在核心内不允许中断特点特点:核心常驻内存核心常驻内存,短小精焊短小精焊,为进程运行提供舞台为进程运行提供舞台 核心的组成核心的组成中断处理中断处理:时钟、时钟、I/O、
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 处理机
1、咨信平台为文档C2C交易模式,即用户上传的文档直接被用户下载,收益归上传人(含作者)所有;本站仅是提供信息存储空间和展示预览,仅对用户上传内容的表现方式做保护处理,对上载内容不做任何修改或编辑。所展示的作品文档包括内容和图片全部来源于网络用户和作者上传投稿,我们不确定上传用户享有完全著作权,根据《信息网络传播权保护条例》,如果侵犯了您的版权、权益或隐私,请联系我们,核实后会尽快下架及时删除,并可随时和客服了解处理情况,尊重保护知识产权我们共同努力。
2、文档的总页数、文档格式和文档大小以系统显示为准(内容中显示的页数不一定正确),网站客服只以系统显示的页数、文件格式、文档大小作为仲裁依据,平台无法对文档的真实性、完整性、权威性、准确性、专业性及其观点立场做任何保证或承诺,下载前须认真查看,确认无误后再购买,务必慎重购买;若有违法违纪将进行移交司法处理,若涉侵权平台将进行基本处罚并下架。
3、本站所有内容均由用户上传,付费前请自行鉴别,如您付费,意味着您已接受本站规则且自行承担风险,本站不进行额外附加服务,虚拟产品一经售出概不退款(未进行购买下载可退充值款),文档一经付费(服务费)、不意味着购买了该文档的版权,仅供个人/单位学习、研究之用,不得用于商业用途,未经授权,严禁复制、发行、汇编、翻译或者网络传播等,侵权必究。
4、如你看到网页展示的文档有www.zixin.com.cn水印,是因预览和防盗链等技术需要对页面进行转换压缩成图而已,我们并不对上传的文档进行任何编辑或修改,文档下载后都不会有水印标识(原文档上传前个别存留的除外),下载后原文更清晰;试题试卷类文档,如果标题没有明确说明有答案则都视为没有答案,请知晓;PPT和DOC文档可被视为“模板”,允许上传人保留章节、目录结构的情况下删减部份的内容;PDF文档不管是原文档转换或图片扫描而得,本站不作要求视为允许,下载前自行私信或留言给上传者【精****】。
5、本文档所展示的图片、画像、字体、音乐的版权可能需版权方额外授权,请谨慎使用;网站提供的党政主题相关内容(国旗、国徽、党徽--等)目的在于配合国家政策宣传,仅限个人学习分享使用,禁止用于任何广告和商用目的。
6、文档遇到问题,请及时私信或留言给本站上传会员【精****】,需本站解决可联系【 微信客服】、【 QQ客服】,若有其他问题请点击或扫码反馈【 服务填表】;文档侵犯商业秘密、侵犯著作权、侵犯人身权等,请点击“【 版权申诉】”(推荐),意见反馈和侵权处理邮箱:1219186828@qq.com;也可以拔打客服电话:4008-655-100;投诉/维权电话:4009-655-100。