资源预览内容
第1页 / 共102页
第2页 / 共102页
第3页 / 共102页
第4页 / 共102页
第5页 / 共102页
第6页 / 共102页
第7页 / 共102页
第8页 / 共102页
第9页 / 共102页
第10页 / 共102页
亲,该文档总共102页,到这儿已超出免费预览范围,如果喜欢就下载吧!
资源描述
第3章 处理机调度与死锁,本章学习目标 掌握处理机的三级调度 掌握作业调度及进程调度的概念 理解调度算法的评价准则 掌握并灵活运用常用的几种作业调度、进程调度算法 掌握死锁的概念、产生的原因及死锁的必要条件 掌握死锁的预防方法及利用银行家算法避免死锁的方法 掌握死锁的检测与恢复的方法,并能灵活运用,第 3章 处理机调度与死锁,1,教学内容,3.1 分级调度 3.2 作业调度 3.3 进程调度 3.4 调度算法 3.5 LINUX系统的调度算法 3.6 死锁问题 3.7 死锁的预防与避免 3.8 利用银行家算法避免死锁 3.9 死锁的检测与解除,3.1 分级调度,一个批处理型作业,从进入系统并驻留在外存的后备队列上开始,直至作业运行完毕,可能要经历以下三级调度:即作业调度、对换和进程调度。,第 3章 处理机调度与死锁,3,3.1.1 调度的层次,1作业调度 作业调度又称为高级调度或长调度,用于选择把外存上处于后备队列中的哪些作业调入内存,并为它们创建进程、分配必要的资源。然后,再将新创建的进程排在就绪队列上,准备执行。在批处理系统中,需要有作业调度的过程,以便将它们分批地装入内存。无须再配置作业调度机制。在分时系统和实时系统中,通常也不需要作业调度。,第 3章 处理机调度与死锁,4,一个作业从提交给计算机系统到执行结束退出系统,一般都要经历提交、后备、执行和完成等4个状态。 提交状态:一个作业在其处于从输入设备进入外部存储设备的过程称为提交状态。 后备状态:也称为收容状态。若一个作业的全部信息已全部被输入进输入井,则在它还未被调度去执行之前,该作业处于后备状态。 执行状态:作业调度程序从后备作业中选取若干个作业到内存投入运行。它为被选中作业建立进程并分配必要的资源,这时,这些被选中的作业处于执行状态。 完成状态:当作业运行完毕,但它所占用的资源尚未全部被系统回收时,该作业处于完成状态。,第 3章 处理机调度与死锁,5,2对换,又称交换调度或中级调度。其主要任务是按照给定的原则和策略,将处于外存交换区中的就绪状态或等待状态的进程调入内存,或把处于内存就绪状态或内存等待状态的进程交换到外存交换区。,第 3章 处理机调度与死锁,6,3进程调度,进程调度又称为低级调度或微观调度。其主要任务是按照某种策略和算法,将处理机分配给一个处于就绪状态的进程。进程调度可分为下列两种方式: (1) 非抢占方式:非抢占方式不允许进程抢占已经分配出去的处理机。 (2) 抢占方式 :抢占调度方式允许调度程序根据某种原则,暂停某个正在执行的进程,将处理机收回,重新分配给另一个进程。,第 3章 处理机调度与死锁,7,第 3章 处理机调度与死锁,作业是用户向计算机提交任务的任务实体。一个作业是指在一次应用业务处理过程中,从输入开始到输出结束,用户要求计算机所做的有关该次业务处理的全部工作。一个作业总是由一个或多个进程组成的。作业分解为进程的过程是:系统首先为一个作业创建一个根进程。然后,在执行作业控制语句时,根据任务要求,系统或根进程为其创建相应的子进程。最后,进行进程调度,为各子进程分配资源和调度各子进程执行,以完成作业要求的工作。,3.1.2 作业与进程的关系,9,3.2 作业调度,作业调度主要是完成作业从后备状态到执行状态的转换,以及从执行状态到完成状态的转换。,第 3章 处理机调度与死锁,10,3.2.1 作业调度的功能,1记录系统中各作业的状态 图- 作业控制块,第 3章 处理机调度与死锁,11,2从后备队列中挑选出一部分作业投入执行。作业调度程序根据选定的调度算法,从后备作业队列中挑选出若干作业去投入执行。 3为被选中作业做好执行前的准备工作。作业调度程序为选中的作业建立相应的进程,并为这些进程分配它们所需要的系统资源,如分配给它们内存、外存、外设等。 4在作业执行结束时做好善后处理工作。包括输出作业管理信息;回收该作业所占用的资源;撤销与该作业有关的全部进程和该作业的作业控制块等等。 作业从后备状态到执行状态以及从执行状态到完成状态的转换过程如图-3所示。,第 3章 处理机调度与死锁,12,按调度算法,从后备 作业中选出一作业,调用存储管理、设备管理程序,审核资源要求,分配资源,调用进程管理 程序建立进程,进程调度,放弃该 作业,调用存储管理, 设备管理回收 分配给该作业 的全部资源,调用会计程序,计算 该作业的执行费用,撤销该作业的所有 进程及作业的JCB,调度下一个作业,后备作业 队列空,资源要求 能满足?,是,出口,否,否,图3-3 (a) 作业从后备状态到执行状态 (b)作业从执行状态到完成状态,是,第 3章 处理机调度与死锁,13,3.2.2 调度算法的评价及准则,1面向用户的准则 2面向系统的准则,14,1面向用户的准则 (1)周转时间短 周转时间:是指作业被提交给系统开始,到作业终止为止的这段时间间隔,也称为作业周转时间。它包括四部分时间: a作业在外存后备队列上等待调度的时间。 b进程在就绪队列上等待进程调度的时间。 c进程占用CPU执行的时间。 d进程等待I/O操作完成的时间。,第 3章 处理机调度与死锁,15,作业i的周转时间Ti可定义为: Ti=TeiTsi 其中,Tei为作业i的完成时间,Tsi为作业i的提交时间。 平均周转时间为: T= 作业的周转时间T与系统为它提供服务的时间(即作业要求运行时间)Ts之比,称为带权周转时间,即:,第 3章 处理机调度与死锁,16,带权周转时间 WTs 因为周转时间 T=等待时间+运行时间Ts, 因此,W也可表示为: W1+等待时间运行时间 从公式可以看出,W1,即W的最小值为1。可以看出,带权周转时间越接近1,则该作业相对等待时间越短,系统性能越高。 而平均带权周转时间可表示为: W=,第 3章 处理机调度与死锁,17,()响应时间快,所谓响应时间,是指从用户提交一个作业请求开始,直至系统首次产生响应为止的时间。它包括三部分时间: 从键盘输入的请求信息传送到处理机的时间。 处理机执行响应处理的时间。 将所形成的响应信息在终端显示器上显示出来的时间。 ()截止时间的保证。所谓截止时间,是指某任务必须开始执行的最晚时间,或必须完成的最晚时间。 ()优先权准则。调度程序根据任务的优先权确定先选中哪个作业。,第 3章 处理机调度与死锁,18,2面向系统的准则,()系统的吞吐量。 ()处理机的利用率。 ()各类资源的平衡利用。,第 3章 处理机调度与死锁,19,3.3 进程调度,3.3.1 进程调度的功能 进程调度的功能可总结为如下几个方面: 1记录系统中所有进程的执行情况 2从就绪态队列中选择一个进程 3进行进程上下文的切换,第 3章 处理机调度与死锁,20,3.3.2 进程调度的时机,在并发执行的环境下,引起进程调度的事件有: 1完成任务 2等待资源 3运行时间到 4进入睡眠状态 5发现标志 6优先级变化,第 3章 处理机调度与死锁,21,3.3.3 进程上下文的切换,进程的上下文由正文段、数据段、硬件寄存器的内容以及有关的数据结构组成。进程上下文的切换主要包括以下四个方面: 1决定是否要做及是否允许做上下文切换 2保存当前执行进程的上下文 3选择一个处于就绪态的进程 4使被选中的进程执行,第 3章 处理机调度与死锁,22,3.3.4 Linux系统中进程调度发生的时机,通常,Linux系统中的进程调度发生的时机有以下几种: 1用户创建一个新的进程时。 2正在执行的进程在申请资源或者等待某个事件的发生,得不到满足时。 3分时系统中,进程执行完一定的时间片之后,释放CPU资源。 4Linux系统提供了两级保护,当进程从核心态返回到用户态时,将会调用调度函数,发生调度。,第 3章 处理机调度与死锁,23,3.4 调度算法,3.4.1 单道批处理系统的调度算法 1先来先服务(FCFS)调度算法 先来先服务(FCFS)调度算法既可用于作业调度,也适用于进程调度。该算法是按照作业或进程到达的先后次序来进行调度。 2短作业(进程)优先调度算法 短作业调度算法(SJF)或短进程调度算法(SPF),是指对短作业或短进程优先调度的算法。 短作业优先调度算法对短作业带来明显的改善,同时降低了作业的平均周转时间,提高了整个系统的性能。,第 3章 处理机调度与死锁,24,SJ(P)F调度算法也存在一些不容忽视的缺点: (1)该算法对长作业不利。 (2)该算法未考虑作业的紧迫度,因而不能保证紧迫作业的及时处理。 (3)致使不一定保证做到真正意义上的短作业优先调度。,第 3章 处理机调度与死锁,25,3高响应比优先调度算法,高响应比优先调度算法又称为HRN调度算法。响应比R可定义如下: R(已等待时间要求服务时间)要求服务时间 即:R1已等待时间要求服务时间 对于同样长度的作业,其R值可以从其等待调度的时间长短来区分;同样等待时间的作业,要求执行时间少的作业R值高。因此,它既照顾了短作业,又考虑了作业的等待时间。当然,在利用该算法时,每次在进行调度之前,都要先计算相应比,因此增加了系统的开销,第 3章 处理机调度与死锁,26,3.4.2 多道批处理系统的调度算法,大多数多道程序系统的作业调度采用以下策略:1基于先来先服务调度。 2基于优先级调度。 3分时和优先级相结合调度。 4综合考虑资源要求调度。,第 3章 处理机调度与死锁,27,3.4.3 优先级调度算法,优先级调度算法也叫做优先权调度算法,可做为作业调度或进程调度策略。这种算法可用于批处理系统,也可用于实时系统中 。 1优先级调度算法的类型 (1)非抢占式优先级调度算法 (2)抢占式优先级调度算法 2. 优先级的类型 在优先级调度算法中,优先级用来表示作业或进程所享有的调度优先权。该算法的关键是确定进程或作业的优先级。确定优先级的方法有两类:,第 3章 处理机调度与死锁,28,(1) 静态优先级 静态优先级是在创建进程时确定的,且在进程的整个运行期间保持不变。 确定进程优先级的依据有如下三个方面: (2)动态优先级 动态优先级是指,在创建进程时所赋予的优先级,是随进程的推进或随其等待时间的增加而改变的,以便获得更好的调度性能。,第 3章 处理机调度与死锁,29,例3:有一个具有两道作业的批处理系统,作业调度采用短作业优先的调度算法,进程调度采用以优先数为基础的抢占式调度算法,假设优先数小的优先级别高。如下表所示的作业序列。 (1)列出所有作业进入内存的时间及作业结束时间。 (2)计算平均周转时间。,第 3章 处理机调度与死锁,30,解: (1)各作业进入时间和结束时间如下:,第 3章 处理机调度与死锁,31,(2)根据周转时间=完成时间提交时间,可得各作业的周转时间为: TA=11:1010:00=70(分钟) TB=10:5010:20=30(分钟) TC=12:0010:30=90(分钟) TD=12:2010:50=90(分钟) 平均周转时间(TA + TB + TC + TD )/4=70(分钟),第 3章 处理机调度与死锁,32,3.4.4 轮转调度算法,1时间片轮转法 时间片轮转法(RR算法)主要用于分时系统中的进程调度。系统把所有就绪进程按先入先出的原则排成一个队列。新来的进程加到就绪队列末尾。每当执行进程调度时,就绪队列的队首进程总是先被调度程序选中,让它在CPU上运行一个时间片的时间。,第 3章 处理机调度与死锁,33,例4:考虑下述四个进程A、B、C和D的执行情况。设它们依次进入就绪队列,但前后时间忽略不计。四个进程分别需要运行12,5,3和6个时间单位。如下表所示。 计算当时间片分别为q=1、q=4时各进程的开始运行时间、完
网站客服QQ:2055934822
金锄头文库版权所有
经营许可证:蜀ICP备13022795号 | 川公网安备 51140202000112号