第4章处理机调度.ppt
《第4章处理机调度.ppt》由会员分享,可在线阅读,更多相关《第4章处理机调度.ppt(48页珍藏版)》请在得力文库 - 分享文档赚钱的网站上搜索。
1、第4章处理机调度 Still waters run deep.流静水深流静水深,人静心深人静心深 Where there is life,there is hope。有生命必有希望。有生命必有希望4.1.1 调度的层次从处理机调度的对象、时间、功能等不同角度,我们可从处理机调度的对象、时间、功能等不同角度,我们可把处理机调度分成不同层次。把处理机调度分成不同层次。处理机调度的层次2作业调度:作业调度:又称为“宏观调度”、“高级调度”。从用户工作流程的角度,一次提交的若干个流程,其中每个程序按照进程调度。时间上通常是分钟、小时或天。内外存交换调度:内外存交换调度:又称为“中级调度”。从存储器资源
2、的角度。将进程的部分或全部换出到外存上,将当前所需部分换入到内存。指令和数据必须在内存里才能被CPU直接访问。进程调度:进程调度:又称为“微观调度”、“低级调度”。从CPU资源的角度,执行的单位。时间上通常是毫秒。因为执行频繁,要求在实现时达到高效率。调度层次3作业调度作业调度功能记录系统中各作业的状况从后备队列中挑选出一部分作业投入执行在作业执行结束时作善后处理工作作业调度主要是完成作业从后备状态到执行状态作业调度主要是完成作业从后备状态到执行状态的转变,以及从执行状态到完成状态的转变。的转变,以及从执行状态到完成状态的转变。4作业调度时机一个作业完成后有新作业提交处理器利用率较低作业调度程
3、序检查系统是否满足作业的资作业调度程序检查系统是否满足作业的资源要求,并按一定算法选取作业。也称为宏观源要求,并按一定算法选取作业。也称为宏观/高级调度。高级调度。5进程调度在一般的多任务和多用户的系统中,用户的进程数一般都大于处理器数,这必将导致用户进程争夺处理器。操作系统本身的进程也同样需要使用处理器。6进程调度(续)功能:功能:调度程序(dispatcher)记录记录所有进程的运行状况(静态和动态)选择选择适当的进程分派CPU时间完成上下文切换切换进程调度的时机:进程调度的时机:当进程出让CPU或调度程序剥夺执行状态进程占用的CPU进程执行完毕执行中进程自己调用阻塞原语将自己阻塞执行中进
4、程由于I/O资源而阻塞或唤醒时间片用完高优先级进程就绪或唤醒(可剥夺方式)7 进程调度分类进程调度分类从调度方式上看,进程调度有两种类型:一种是非抢占式调度,另一种是抢占式调度。1.非抢占调度 可能引起当前进程主动放弃处理机控制权的情况有两个:l进程运行完毕退出或遇到不可挽回的故障。l运行受阻。82.2.抢占调度抢占调度 剥夺调度也称作剥夺调度,主要指的是,在系统正常运转期间,如果某种事件出现,系统将迫使正在运行的进程停下来,将CPU控制权交给其它进程。抢占调度的思想源自对高紧迫度作业的响应,优优先先级级是多道程序系统中进程紧迫度的具体体现。当一个紧迫性较高的进程到来,要求在限定的时间内做出响
5、应,管理程序应及时停止正在运行的程序。将控制权交给紧迫性较高的进程。当紧迫性较高的进程有阻塞转为就绪(所等待的操作完成),管理程序立即停止低优先级进程的运行,让高优先级进程立即恢复运行。管理程序要做的工作:比较当前进程与新到来的进程的优先级,如果确认需要剥夺时,将当前进程由运行状态转入就绪状态,然后,将控制权交给紧迫性高的进程。此外,采用时间片轮转或短进程优先原则调度时也归此类。94.1.2调度的分类调度的分类 l批处理调度 l分时调度 l实时调度10调度算法的公共目标对各作业公平、合理,使用户满意:执行时间长短、等待时间等充分利用资源:CPU忙、I/O设备忙将各种类型的作业合理搭配起来进行调
6、度4.2调度算法的设计目标和性能准则调度算法的设计目标和性能准则11批处理系统:吞吐量、周转时间、CPU利用率分时调度:响应时间、均衡性实时调度:时限要求12性能指标:1平均周转时间平均周转时间T越小,系统吞吐量就越大。T的计算公式为:其中:n为单位时间内的作业数量。tfi为作业i的完成时间。tbi为作业的开始时间。132.平均带权周转时间这一准则主要是针对批处理系统的。为了描述系统对短小作业的优惠程度,可使用作业的平均带权周转时间W作为评价参数。W的计算公式为:其中:tsi为作业i的服务时间(也就是运行时间)。W越小,说明系统对短小作业越优惠。143.其它指标响应时间:响应时间:用户输入一个
7、请求(如击键)到系统给出首次响应(如屏幕显示)的时间分时系统。系统吞吐量:系统吞吐量:单位时间内系统所完成的作业数批处理系统。15 4.3 4.3 调度算法调度算法调度算法决定了系统追求的目标。调度算法决定了系统追求的目标。基本的调度算法有以下几种:基本的调度算法有以下几种:lFCFS算法,先来先服务调度。lSJF/SPF(ShortestProcessFirst)算法,短作业/进程优先调度。lHRF(HighestResponseFirst)算法,高响应比优先调度。lRR(RoundRobin)算法,时间片轮转调度。lHPF(HighestProcessFirst)算法,高优先级调度。l多级
8、反馈队列调度算法。16先来先服务(FCFS,First Come First Service)这是最简单的调度算法,按先后顺序进行调度。这是最简单的调度算法,按先后顺序进行调度。先来先服务(先来先服务(FCFS):):按照作业进入系统的先后次序进行调度,先进入系统者先调度;即启动等待时间最长的作业。优点:实现简单、公平缺点:没考虑资源利用率和作业的特殊性17按照进程变为就绪状态的先后次序,分派CPU。当前进程占用CPU,直到执行完或阻塞,才出让CPU(非抢占方式)。在进程唤醒后(如I/O完成),并不立即恢复执行,通常在阻塞队列中等到当前进程出让CPU。这是最简单的算法。1.FCFS算法算法2.
9、FCFS的特点比较有利于长进程,而不利于短进程。有利于CPU繁忙的进程,而不利于I/O繁忙的进程。18短作业优先(短作业优先(SJF):):以要求运行时间长短进行调度,即启动要求运行时间最短的作业。优点:易于实现,强调了资源的充分利用,保证了系统的最大吞吐量(单位时间里处理作业的个数)缺点:不公平,会造成长作业长期等待短作业优先SJF(ShortestJobFirst)这是对这是对FCFS算法的改进,其目标是减少平均周转时间算法的改进,其目标是减少平均周转时间T。19短进程优先1.SPF算法算法对预计执行时间短的进程优先分派处理机。通常后来的短进程不抢先正在执行的进程。2.SPF的特点的特点提
10、高系统的吞吐量;对长进程非常不利,可能长时间得不到执行;难以准确估计进程的执行时间,从而影响调度性能。20SJF的变型“最短剩余时间优先”SRT(ShortestRemainingTime)允许比当前进程剩余时间更短的进程来抢占高响应比优先(高响应比优先(HRF):):响应比最高的作业优先启动。(响应比(响应比=(等待时间(等待时间+估计运行时间)估计运行时间)/估计运行时间)估计运行时间)该算法是FCFS和SJF的结合,克服了两种算法的缺点优点:公平,吞吐率大缺点:增加了计算,增加了开销21时间片轮转(Round Robin)算法前几种算法主要说明怎样选择一个进程或作业前几种算法主要说明怎样
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 处理机 调度
限制150内