《处理机调度》PPT课件

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,操作系统,Operating System,北方工业大学计算机系,North China University of Technology,Department of Computer,授课教师：宋丽华,Email： Tel:88803939 五教1102,为什么要管理处理机?,处理机是计算机中最宝贵的资源，处理机调度策略是否合适直接,影响,着计算机的,性能,。,在批处理系统用户一旦将作业提交就失去了对作业的控制，用户希望系统的,周转时间尽量短,。交互式系统中用户以交互方式工作，好象整个计算机都为一个用户工作，这时希望系统的,响应时间快,。,由此可以看出，不同的操作系统类型和用户要求，处理机的,管理策略应该有所不同,。,衡量调度策略的指标,周转时间,一个作业从投入计算机到结束所使用的,时间,。,吞吐量,在给定的时间内，一个计算机系统所完成的总的,工作量,。,响应时间,从用户向计算机发出指令到计算机将结果返回给用户需要的时间。,设备利用率,主要指输入输出设备的使用情况。,-小,-大,-短,-高,第四章 处理机调度,4.1,分级调度,4.2 作业调度,4.3,进程调度,4.4 调度算法,4.1 分级调度,操作系统中一个程序运行相关的概念：,作业、进程、线程,。它们是程序在计算机中不同运行阶段的不同体现，为此应该有不同的调度程序。,程序的各种状态及相应的调度方式,提交状态,：一个作业从,输入设备,进入,外存,的过程叫做提交状态，这时的作业,不能被调度,。,后备状态,：当一个作业的全部都已经进入了,输入井,，,未运行之前,叫做后备状态（,收容状态,）。,运行状态,：作业调度程序从后备作业中选择一个作业到,内存运行,，并为它,创建进程,和,分配资源,。这些被选中的作业处于执行状态，执行状态的作业并不一定占用处理机，哪个进程占用处理机由进程调度程序决定。这个状态中还包括：,就绪状态、执行状态,和,等待状态,。,完成状态：,当作业运行完毕后，它所占用的资源并未全部释放。,4.1 分级调度,处理机调度分四个级别,作业调度,（,高级,）：按一定的原则从作业输入井中选择作业，为其创建进程、分配资源，当作业运行完毕后回收作业占用的资源。,交换调度,（,中级,）：按某种策略将处于,外存,交换区的就绪进程调入,内存,、把内存中就绪状态或等待状态的进程调出内存。,4.1 分级调度,处理机调度分四个级别,进程调度,（,低级,）：按某种策略选择一个就绪进程占用处理机，在确定了占用处理机的进程后，必须进行进程上下文切换，以便为运行进程准备好执行环境。,线程调度,（,微级,）：负责各个线程的调度。,第四章 处理机调度,4.1,分级调度,4.2 作业调度,4.3,进程调度,4.4 调度算法,4.2 作业调度,作业调度程序的功能,作业调度程序的目标和性能衡量,4.2.1 作业调度程序的功能,记录已经进入系统的各个作业的情况,。作业调度要记录作业进入系统时的一些,信息,，并跟踪作业在运行中的状态,变化情况,。这些信息记录在作业控制块,JCB,，它,建立和撤消,都是由作业调度程序完成的。,选择作业。,从,输入井,中,选择,符合“条件”的作业送到,内存,的作业缓冲区中，使这些作业的状态由“后备”状态变为“运行”状态。,4.2.1 作业调度程序的功能,为被选中的作业做执行前的准备。,建立进程，,分配作业运行需要的资源,，如内存和外部设备。作业调度程序只能保证该作业具有使用处理机的资格,，而不能分配处理机资源。,作业运行结束后的善后处理和资源回收。,统计作业的运行时间，作业执行状态等信息的输出。,撤消该作业的所有进程和该作业的JCB,。,作业调度程序的处理流程,例 题,当作业进入完成状态，操作系统（）,A 将删除该作业并收回其所占资源，同时输出结果；,B收回其所占资源，输出结果，并将该作业的控制块从当前作业队列中删除；,C 将收回该作业所占资源并输出结果；,D 将输出结果并删除内存中的作业。,B,4.2.2 作业调度算法的目标和性能衡量,调度目标：,1）对所有的作业应该是公平合理的。,2）应使设备有较高的利用率。,3）单位时间内执行尽可能多的作业。,4）有快的响应时间。,由于这些目标的相互冲突，任一调度算法要想同时满足上述目标是不可能的。,周转时间,=,作业完成时间,作业提交时间,。,Ti=Tei Tsi,平均周转时间,：,注意：,一个作业的周转时间说明了它在系统内部停留的时间，应该包括两部分：,等待时间,和,执行时间。,Ti=,Twi,+,Tri,Twi：是作业由,后备状态,到,执行状态,的,等待时间,，不包括作业进入执行状态后的等待时间。,Tri：是作业在,执行状态,的时间。,4.2.2 作业调度算法的目标和性能衡量,带权周转时间,=作业的周转时间,作业执行时间,如果有多个作业同时进入系统，则,平均带权周转时间,：,4.2.2 作业调度算法的目标和性能衡量,一般来说，作业的平均周转时间短，说明作业在,系统的时间短,，用户,等待的时间短,，系统的,利用率高,，所以，应该选择平均周转时间短的作业调度算法。,Wi=Ti/Tri,第四章 处理机调度,4.1,分级调度,4.2 作业调度,4.3,进程调度,4.4 调度算法,4.3 进程调度,进程调度程序的功能,进程调度的时机,进程调度性能评价,4.3.1 进程调度程序的功能,1）,记录和保持系统中所有进程的有关情况和状态特征,：由进程调度模块管理PCB表的内容，记录进程状态。,2）,选择占用处理机的进程,：在处理机空闲时，根据一定的原则选择一个进程来运行。,3）,进行进程上下文切换：,上下文切换时首先检查是否可以做切换，然后,保存,被切换进程的上下文，由,调度,程序选择一个进程，装载该进程的上下文，控制转向该进程，从刚,恢复,的程序计数器所指示的指令地址开始执行。,4.3.2 进程调度的时机,引起进程调度的原因有以下7类：,一个进程,完成其任务,时。,执行中的进程,自己调用阻塞原语,，进入等待状态。,执行了一次,P操作,，资源不满足；执行,V操作,激活了等待队列的进程。,执行的进程,提出I/O请求,后,被阻塞,。,在分时系统中,时间片已经用完,。,执行完,系统调用,，系统返回用户态之前，由于系统进程结束，需求调度新的进程。,在采用,可剥夺调度,方式的系统中，当具有更高优先级的进程要求处理机时。,【13年考研28题】,下列选项中，会导致用户进程从用户态切换到内核态的操作是(),I.整数除以零 II.sin()函数调用 III.read 系统调用,A.仅I、II B.仅I、III C.仅II、III D.I、II和III,B,4.3.2 进程调度的时机,可剥夺方式：,在就绪队列中一旦有优先级高于当前执行进程的进程存在便立即发生进程调度，转让处理机。,而,不可剥夺方式,即使在就绪队列存在有优先级高于当前执行进程时，当前进程仍将继续占有处理机，直到该进程自己因调用原语操作或等待I/O而进入阻塞状态，或时间片用完时才重新发生调度让出处理机。,4.3.3 进程调度性能评价,进程调度策略的好坏直接影响作业调度的性能。,作业调度性能评价,周转时间,平均周转时间,带权周转时间,平均带权周转时间,4.3.3进程调度性能评价,进程调度性能评价,定性,调度的可靠性,简洁性,定量,CPU的利用率,进程在就绪队列中等待时间与执行时间之比,第四章 处理机调度,4.1,分级调度,4.2 作业调度,4.3,进程调度,4.4 调度算法,4.4 调度算法,先来先服务,轮转法,多级反馈轮转法,优先级法,最短作业优先法,最高响应比优先法,4.4 调度算法,思想：,按作业和就绪进程到来的次序进行调度。这种算法优先考虑在系统中等待时间最长的作业，而不管它要求运行时间的长短。,优点：,算法简单，公平，容易实现,缺点：,对于短作业或短进程，等待时间长,作业调度算法FCFS,（First come first serve）,4.4 调度算法,作业调度算法FCFS,下面是4个作业在系统中从提交、运行的信息。,作业,提交,时间,运行时间,开始,时间,完成,时间,周转,时间,带权周转时间,1,8,2,2,8.5,0.5,3,9,0.1,4,9.5,0.2,平均周转时间：T=1.725 平均带权周转时间W=6.875,8,10,10.5,10.6,10,10.5,10.6,10.8,2,2,1.6,1.3,1,4,16,6.5,4.4 调度算法,思想：,比较作业缓冲区中的作业预计的运行时间，选择,预计时间最短的作业,进入运行状态。,优点：,算法简单，可得到最大系统吞吐率，效率高。,缺点：,主要问题是对长作业不利，如果系统不断地接收短作业，就会使长作业长时间等待。,短作业优先算法SJF,（shortest job first）,4.4 调度算法,短作业优先算法SJF,作业,提交,时间,运行时间,开始,时间,完成,时间,周转,时间,带权周转时间,1,8,2,2,8.5,0.5,3,9,0.1,4,9.5,0.2,平均周转时间：T=1.55 平均带权周转时间W=5.15,8,10.3,10,10.1,10,10.8,10.1,10.3,2,2.3,1.1,0.8,1,4.6,11,4,4.4 调度算法,响应比=响应时间/预计执行时间,响应时间=等待时间+预计执行时间,所以响应比为：,1+作业等待时间/预计执行时间,思想,：当需要从就绪队列中选择进程投入运行时，先计算每个进程的,响应,比，选择,响应,比最高的进程运行,优点,：短作业响应比高，执行时间短；长作业响应比随着等待时间增加而提高，不会过长等待。既照顾了短作业、也考虑到了长作业。,缺点,：每次调度前计算响应比增加了系统开销。,最高响应比优先HRN,（highest response-ratio next）,4.4 调度算法,作业,提交,时间,运行时间,开始,时间,完成,时间,周转,时间,带权周转时间,1,8,2,2,8.5,0.5,3,9,0.1,4,9.5,0.20,平均周转时间：T=1.625 W=5.675,最高响应比优先HRN,8,10.1,10,10.6,10,10.6,10.1,10.8,2,2.1,1.1,1.3,1,4.2,11,6.5,4.4 调度算法,算法描述：,根据分配给进程的优先数来决定运行进程。,算法的核心,：是确定进程或作业的优先级,静态法,：静态优先权是在创建进程时确定的，且在进程的整个运行期间保持不变。,动态法,：动态优先权是指，在创建进程时所赋予的优先权可以随进程的推进或随其等待时间的增加而改变的，以便获得更好的调度性能。,优先级法,HPF,（highest priority first）,特点,：静态优先级法简单，但缺点是公平性差，可能会造成优先级低的长期等待；动态优先级法资源利用率高，公平性好，缺点是系统开销较大，实现复杂。,4.4 调度算法,静态法,作业调度确定优先级原则,由用户根据作业的紧急程度输入一个适当的优先级；,由系统或操作员根据作业的类型确定；,系统根据作业要求的资源确定优先级。,进程调度确定优先级原则,按照进程的类型确定；,将作业的优先级作为它所属进程的优先级。,优先级法,HPF,（highest priority first）,4.4 调度算法,动态法优先级确定原则,根据,进程占有CPU时间长短,确定,占用的时间越,长,，下次调度的优先级越,低,；,占用的时间越,短,，下次调度的优先级越,高,。,根据,就绪进程等待CPU的时间长短,确定,等待时间越,长,，优先级越,高,；,等待时间越,短,，优先级越,低,。,优先级法,HPF,（highest priority first）,4.4 调度算法,算法描述：,将CPU的处理时间分成,固定大小,的时间片。如果一个进程在被调度选中之后用完了系统规定的时间片，但未完成要求的任务，则它自行释放自己所占有的CPU而,排到就绪队列的末尾,，等待下一次调