操作系统课程第3章处理机调度.ppt
《操作系统课程第3章处理机调度.ppt》由会员分享,可在线阅读,更多相关《操作系统课程第3章处理机调度.ppt(161页珍藏版)》请在三一办公上搜索。
1、Page 1,2023/10/27,第三章 处理机调度与死锁,Page 2,2023/10/27,第三章 处理机调度与死锁,处理机调度的基本概念 处理机调度的目标充分有效地利用处理机(CPU)资源 调度算法 实时调度 产生死锁的原因和必要条件 预防死锁的方法 死锁的检测与解除,Page 3,2023/10/27,3.1 处理机调度的基本概念,操作系统调度级别进程调度的任务确定算法的原则进程调度方式调度队列模型选择调度方式和调度算法的若干准则,Page 4,2023/10/27,3.1 处理机调度的基本概念,3.1.1 操作系统调度级别,1.高级调度,2.低级调度,3.中级调度,Page 5,2
2、023/10/27,3.1.1 高级、中级和低级调度,1.高级调度 又称作业调度主要任务是按一定的原则对外存上处于后备状态的作业进行选择,给选中的作业分配内存、输入/输出设备等必要的资源,并建立相应的进程,插入就绪队列,以使该作业的进程获得竞争处理机的权利,作 业 调 度,作业是用户在一次解题或一个事务处理过程中要求计算机系统所做工作的集合,包括用户程序、所需的数据及命令等作业状态:作业从提交给系统,直到完成任务后退出系统前,在整个活动过程中它会处于不同的状态。通常,作业状态分为四种:提交、后备、执行和完成,如图3-1所示。,Page 7,2023/10/27,作 业 调 度,后备状态,完成状
3、态,就绪,阻塞,执行,I/O完成,I/O请求,时间片完,作业状态间转换,图3-1 作业的基本状态,Page 8,2023/10/27,(1)提交状态即用户向系统提交一个作业时,该作业所处的状态。(2)后备状态即用户作业经输入设备(如读卡机)送入输入井(磁盘)中存放,等待进入内存时所处的状况。(3)执行状态即作业分配到所需的资源,被调入内存,并且在处理机(CPU)上执行相应的程序时所处的状况。(4)完成状态即作业完成了计算任务,结果由打印机输出,最后由系统回收分配给它的全部资源,准备退出系统时的作业状况。,作业状态,作业控制块(JCB)在多道批处理系统中通常有上百个作业被收容在输入井(磁盘)中。
4、为了管理和调度作业,系统为每个作业设置了一个作业控制块(JCB),它记录该作业的有关信息。JCB的主要内容如图3-2所示。,作 业 调 度,图3-2 作业控制块,作业调度的功能 作业调度的主要任务是完成作业从后备状态到执行状态和从执行状态到完成状态的转换。(1)记录系统中各个作业的情况。(2)按照某种调度算法从后备作业队列中挑选作业。(3)为选中的作业分配内存和外设等资源。(4)为选中的作业建立相应的进程。(5)作业结束后进行善后处理工作,如输出必要的信息,收回该作业所占用的全部资源,撤消与该作业相关的全部进程和该作业的JCB。,Page 13,2023/10/27,高级、中级和低级调度,在每
5、次作业调度时,须决定:接纳多少个作业 即允许多少个作业同时在内存中运行作业太多 服务质量下降作业太少 资源利用率低接纳哪些作业 取决于作业调度算法先来先服务短作业优先作业优先权调度响应比调度,周转时间太长,系统吞吐量太低,适当的折衷,周转时间:从作业被提交给系统开始,到作业完成为止的这段时间间隔。吞吐量:是指在单位时间内系统所完成的作业数。,Page 14,2023/10/27,3.1.1 高级、中级和低级调度,2.中级调度目的:是为了提高内存利用率和系统吞吐量。功能:暂时不能运行的进程挂起,释放宝贵的内存资源。具备条件时:把外存上的就绪进程,重新调入内存,挂在就绪队列上等待进程调度。,Pag
6、e 15,2023/10/27,3.1.1 高级、中级和低级调度,3.低级调度 进程调度主要任务是按照某种策略和方法选取一个处于就绪状态的进程,将处理机分配给它常见的低级调度有非抢占式和抢占式两种,Page 16,2023/10/27,处理机调度的层次,Page 17,2023/10/27,作业调度又称为1,它决定将那些在外存储器上的处于2状态的作业调入主机内存,系统经作业调度程序选中一个或多个作业后,就为它们分配必要的内存、设备及软资源。然后控制权就交给了3,由3将它们变为一个或一组4。1():A、高级调度 B、低级调度 C、中级调度 D、进城调度 2():A、就绪 B、阻塞 C、提交 D、
7、后备 3():A、存储管理模块 B、处理机管理模块 C、文件管理模块 D、设备管理模块 4():A、指令 B、子程序 C、进程 D、程序段,Page 18,2023/10/27,处于后备状态的作业存放在()中。A、外存 B、内存 C、A和B D、扩展内存在操作系统中,作业处于()状态时,已处于进程的管理之下。A、后备 B、阻塞 C、执行 D、完成,Page 19,2023/10/27,3.1处理机调度的基本概念,高级、中级和低级调度 进程调度的任务 确定算法的原则 进程调度方式 调度队列模型 选择调度方式和调度算法的若干准则,Page 20,2023/10/27,3.1.2 进程调度的任务,进
8、程调度的任务 是控制、协调进程对CPU的竞争,即按一定的调度算法从就绪队列中选中一个进程,把CPU的使用权交给被选中的进程,Page 21,2023/10/27,处理机调度的基本概念,高级、中级和低级调度 进程调度的任务 确定算法的原则 进程调度方式 调度队列模型 选择调度方式和调度算法的若干准则,Page 22,2023/10/27,3.1.3 确定算法的原则,具有公平性 资源利用率高(特别是CPU利用率)在交互式系统情况下要追求响应时间(越短越好)在批处理系统情况下要追求系统吞吐量,Page 23,2023/10/27,处理机调度的基本概念,高级、中级和低级调度 进程调度的任务 确定算法的
9、原则 进程调度方式 调度队列模型 选择调度方式和调度算法的若干准则,Page 24,2023/10/27,进程调度方式,非抢占方式抢占方式,Page 25,2023/10/27,进程调度方式,非抢占方式(Non-preemptive Mode)引起进程调度的因素正在执行的进程执行完毕,或因发生某事件而不能再继续执行执行中的进程因提出I/O请求而暂停执行;在进程通信或同步过程中执行了某种原语操作,如wait、Block、Wakeup原语,优点:算法简单,系统开销小缺点:紧急任务不能及时响应;短进程到达要等待长进程运行结束,Page 26,2023/10/27,进程调度方式,抢占方式 抢占式调度主
10、要有以下原则优先权原则 允许高优先权的新到进程抢占当前进程的处理机短作业(进程)优先原则允许执行时间短的新到进程抢占当前进程的处理机 时间片原则 时间片用完后停止执行,重新进行调度,适用于分时系统,优点:适于时间要求严格的实时系统缺点:调度算法复杂,系统开销大,Page 27,2023/10/27,3.1处理机调度的基本概念,高级、中级和低级调度 进程调度的任务 确定算法的原则 进程调度方式 调度队列模型 选择调度方式和调度算法的若干准则,Page 28,2023/10/27,3.1.5 调度队列模型,仅有进程调度的调度队列模型具有高级和低级调度的调度队列模型同时具有三级调度的调度队列模型,P
11、age 29,2023/10/27,3.1.5 调度队列模型,仅有进程调度的调度队列模型在分时系统中,通常仅设有进程调度系统把这些进程组织成一个就绪队列每个进程在执行时,可能有以下几种情况进程获得CPU正在执行任务在给定时间片内已完成,释放处理机后为完成状态任务在时间片内未完成,进入就绪队列末尾在执行期间因某事件而阻塞,Page 30,2023/10/27,3.1.5 调度队列模型,仅有进程调度的调度队列模型,进程调度,进程完成,等待事件,交互用户,时间片完,Page 31,2023/10/27,3.1.5 调度队列模型,具有高级和低级调度的调度队列模型在批处理系统中,不仅需要进程调度,而且还
12、要有作业调度就绪队列的形式在批处理系统中,常用高优先权队列。进程进入就绪队列时,按优先权高低插入相应位置,调度程序总是把处理机分配给就绪队首进程设置多个阻塞队列根据事件的不同设置多个队列提高效率,Page 32,2023/10/27,3.1.5 调度队列模型,进程调度,进程完成,时间片完,与上一模型的主要区别:就绪队列的形式;设置多个阻塞队列,Page 33,2023/10/27,3.1.5 调度队列模型,同时具有三级调度的调度队列模型,进程调度,中级调度,等待事件,进程完成,时间片完,作业调度,交互型作业,批量作业,挂起,事件出现,事件出现,Page 34,2023/10/27,3.1 处理
13、机调度的基本概念,高级、中级和低级调度 进程调度的任务 确定算法的原则 进程调度方式 调度队列模型选择调度方式和调度算法的若干准则,如果你是用户,你希望系统如何为你服务,如何考虑?如果你是调度者,从系统整体角度出发,应如何考虑?,Page 35,2023/10/27,3.1.6 选择调度方式和调度算法的若干准则,1.面向用户的准则,2.面向系统的准则,Page 36,2023/10/27,3.1.6 选择调度方式和调度算法的若干准则,1.面向用户的准则,(1)周转时间短。,(2)响应时间快。(3)截止时间的保证。(4)优先权准则。,Page 37,2023/10/27,选择调度方式和调度算法的
14、若干准则,面向用户的准则周转时间短平均周转时间,带权周转时间:进程(或作业)的周转时间T与系统为它提供服务的时间TS之比,即W=T/TS。而平均带权周转时间则可表示为:,Page 38,2023/10/27,通常把周转时间作为评价批处理系统的性能、选择作业调度方式与算法的准则。所谓周转时间,是指从作业提交给系统开始,到作业完成为止的这段时间间隔(称为作业周转时间)。它包括:(1)作业在外存后备队列上等待(作业)调度的时间;(2)进程在就绪队列上等待进程调度的时间;(3)进程在CPU上执行的时间;(4)等待IO操作完成的时间。其中,第(2)、(3)、(4)项在一个作业的处理过程中,可能发生多次。
15、,Page 39,2023/10/27,可把平均周转时间描述为:,作业的周转时间T与系统为它提供服务的时间TS之比,即W=T/TS,称为带权周转时间,而平均带权周转时间则可表示为:,系统以多个用户都满意为目标,周转时间服务时间周转时间完成时间到达时间,Page 40,2023/10/27,选择调度方式和调度算法的若干准则,面向用户的准则响应时间快响应时间是指从用户通过键盘提交一个请求开始,直至系统中首次产生响应为止的时间截止时间保证截止时间是指某任务必须开始执行的最迟时间或必须完成的最迟时间截止时间是实时系统中的重要指标,Page 41,2023/10/27,选择调度方式和调度算法的若干准则,
16、面向用户的准则等待时间短等待时间是在就绪队列中等待所花的时间调度算法并不影响进程运行和执行I/O的时间量;只影响进程在就绪队列中等待所花费的时间优先权准则在批处理、实时和分时系统中都可以选择优先权准则,以便让紧急任务先处理有时还选择抢占式调度方式,Page 42,2023/10/27,选择调度方式和调度算法的若干准则,面向系统的准则系统吞吐量高吞吐量指单位时间内系统所完成的作业数作业调度的方式和算法对吞吐量的大小有较大影响处理机利用率高各类资源的平衡利用使内存、外存和I/O设备的利用率高,基于这样的准则,你设计操作系统的调度策略应如何?,Page 43,2023/10/27,()是指从作业提交
17、给系统到作业完成的时间间隔。A周转时间 B、响应时间 C、等待时间 D、运行时间 作业从进入后备队列到被调度程序选中的时间间隔成为()。A周转时间 B、响应时间 C、等待时间 D、触发时间在批处理系统中,周转时间是()。A、作业运行时间 B、作业等待时间和运行时间之和 C、作业的相对等待时间 D、作业被调度进入内存到运行完毕的时间,Page 44,2023/10/27,第三章 处理机调度与死锁,处理机调度的基本概念 调度算法 实时调度 产生死锁的原因和必要条件 预防死锁的方法 死锁的检测与解除,Page 45,2023/10/27,3.2 调度算法,在OS中调度的实质是一种资源分配,因而调度算
18、法是指:根据系统的资源分配策略所规定的资源分配算法问题提出如何制定分配策略:对不同的系统和系统目标,通常采用不同的算法,如短作业优先,时间片轮转等有些算法适用于作业调度,有些适用于进程调度,有些两者皆可,Page 46,2023/10/27,调度算法,先来先服务和短作业优先算法 高优先权优先调度算法 基于时间片的轮转调度算法,Page 47,2023/10/27,先来先服务和短作业优先算法,先来先服务(FCFS)/先进先出(FIFO)调度算法按照作业/进程进入系统的先后次序进行调度,先进入系统者先调度;即启动等待时间最长的作业/进程是一种最简单的调度算法,即可用于作业调度,也可用于进程调度几个
19、术语到达时间、服务时间、开始时间完成时间、等待时间周转时间:完成时间-到达时间带权周转时间:周转时间/服务时间,Page 48,2023/10/27,先来先服务和短作业优先算法,0,4,4,4,7,6,先来先服务(先进先出):,7,12,10,12,14,11,14,18,14,Page 49,2023/10/27,先来先服务和短作业优先算法,先来先服务(先进先出)优缺点,比较有利于长作业(进程),而不利于短作业(进程)有利于CPU繁忙型作业(进程),而不利于I/O繁忙型作业(进程)用于批处理系统,不适于分时系统,Page 50,2023/10/27,先来先服务和短作业优先算法,短作业(进程)
20、优先调度算法SJ(P)F短作业(进程)优先调度算法SJ(P)F,以要求运行时间长短进行调度,即启动要求运行时间最短的作业可以分别用于作业调度和进程调度短作业优先(SJF)的调度算法,是从后备队列中选择一个或若干个估计运行时间最短的作业,将它们调入内存运行;而短进程优先(SPF)调度算法,则是从就绪队列中选出一估计运行时间最短的进程,将处理机分配给它,使它立即执行并一直执行到完成,或发生某事件而被阻塞放弃处理机时,再重新调度,Page 51,2023/10/27,先来先服务和短作业优先算法,0,4,4,1,短作业/短进程优先(SJF/SPF):,4,6,3,3/2,6,9,8,8/3,9,13,
21、9,9/4,13,18,16,16/5,40/5,2.1,Page 52,2023/10/27,FCFS/SJF调度算法的性能,先来先服务和短作业优先算法,SJF平均周转时间和平均带权周转时间明显改善,Page 53,2023/10/27,SJF的特点,优点:比FCFS改善平均周转时间和平均带权周转时间,缩短作业的等待时间;提高系统的吞吐量。缺点:对长作业非常不利,可能长时间得不到执行;未能依据作业的紧迫程度来划分执行的优先级;难以准确估计作业(进程)的执行时间,从而影响调度性能。,Page 54,2023/10/27,调度算法,先来先服务和短作业优先算法高优先权优先调度算法基于时间片的轮转调
22、度算法,Page 55,2023/10/27,高优先权优先(HPF,Highest Priority First)调度算法,优先权调度算法的类型非抢占式优先权调度算法抢占式优先权调度算法,Page 56,2023/10/27,高优先权优先(HPF,Highest Priority First)调度算法,优先权调度算法的类型非抢占式优先权调度算法特点:系统一旦把处理机分配给就绪队列中优先权最高的进程后,该进程便一直执行下去,直至完成,或因发生某事件使该进程放弃处理机时,系统才将处理机重新分配给另一优先权最高的进程主要用于批处理系统中,也可用于某些对实时性要求不严的实时系统中,Page 57,20
23、23/10/27,高优先权优先调度算法,优先权调度算法的类型抢占式优先权调度算法把处理机分配给优先权最高的进程,但在执行期间,只要出现另一个优先权更高的进程,则进程调度程序就立即停止当前进程的执行,并将处理机分配给新到的优先权最高的进程注意:只要系统中出现一个新的就绪进程,就进行优先权比较该调度算法,能更好地满足紧迫作业的要求,故而常用于要求比较严格的实时系统中,以及对性能要求较高的批处理和分时系统中,Page 58,2023/10/27,高优先权优先调度算法,优先权的类型静态优先权动态优先权,Page 59,2023/10/27,高优先权优先调度算法,优先权的类型静态优先权静态优先权在创建进
24、程时确定,且在进程的整个运行期间保持不变。一般地,优先权是利用某一范围内的一个整数来表示的,例如,07或0255,又把该整数称为优先数确定进程静态优先权的依据进程类型:系统进程,用户进程进程对资源的需求(对CPU和内存需求较少的进程,优先级较高)用户要求(紧迫程度和付费多少),Page 60,2023/10/27,高优先权优先调度算法,动态优先权在创建进程时赋予的优先级,在进程运行过程中可以自动改变,以便获得更好的调度性能。可规定,在就绪队列中的进程,随其等待时间的增长,其优先权以速率a提高具有相同优先权初值的进程,则最先进入就绪队列,其将因其动态优先权变得最高而优先获得处理机,此即FCFS算
25、法具有各不相同的优先权初值的就绪进程,则优先权初值低的进程,在等待了足够的时间后,其优先权便可能升为最高,从而可以获得处理机当采用抢占式优先权调度算法时,如果再规定当前进程的优先权以速率b下降,则可防止一个长作业长期地垄断处理机,Page 61,2023/10/27,静态优先权,非抢占式(1为高优先权),高优先权优先调度算法,0,4,4,1,4,8,4,1,8,11,10,10/3,11,16,14,14/5,16,18,15,15/2,9.4,2.93,考虑一下抢占式,情况如何?,Page 62,2023/10/27,高优先权优先调度算法,高响应比优先调度算法(HRF)是FCFS和SJF的结
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 操作系统 课程 处理机 调度
链接地址:https://www.31ppt.com/p-6399276.html