《处理机调度 》PPT课件.ppt

第三章 处理机调度,1 调度级别2 调度的功能、时机及方式3 调度原则与评估标准4 调度算法5 调度的实现,调 度 级 别,.高级调度 即作业调度。它决定允许哪些作业可参与竞争和其它系统资源，从状态观点，就是将一个或一批作业从后备状态变为运行状态。一个作业一旦被高级调度选中，便可获得所需要的基本内存和设备资源，并被装入内存，此后就以进程形式参与并发运行，与其它进程竞争。换言之，高级调度决定给哪个作业分配一台虚拟处理机，获得虚拟处理机的作业将在该虚拟处理机上顺序执行。从这个意义上说，高级调度进行的是虚拟处理机的分配，即的宏观调度，故高级调度亦称宏观调度。,中级调度 中级调度决定哪些进程可参与竞争，从状态观点，就是将进程从活动态变为静止的挂起态，或者将进程从挂起态变为就绪态或等待态。这主要是为了短期调整系统负荷，以缓和内存使用紧张的矛盾。中级调度的实质是执行“挂起”和“激活”操作；挂起一个进程是把该进程的实体（程序和数据）从内存迁移到外存的专门区域，称为交换区，并释放该进程占用的用户内存区，这称为“换出”；反之，激活一个进程是把该进程的实体从外存交换区迁移到内存，这称为“换进”。故中级调度也常称为进程交换，通常仅用于分时系统。,低级调度 即进程调度。它决定哪个进程可获得物理，从状态观点，就是将某个进程从就绪态变为执行态。被低级调度选中的进程将实际获得，并可立即在物理上执行它的程序。因此，低级调度是处理机三级调度中的终结调度，亦称的微观调度。,图-处理机的三级调度,调度的功能、时机及方式,.作业调度的功能与时机,（）按照某种调度算法（即调度策略），根据系统资源的当前使用情况和后备作业对资源的需求，挑选一个或多个后备作业投入运行；（）为选中的作业分配基本的内存和设备资源，这通过调用内存分配程序和设备分配程序来完成；（）为选中的作业建立进程，将进程实体装入内存，这通过调用建立进程原语来实现。,一般来说，在下列情况下将启动作业调度：（）设为系统支持的在主机上运行的最大作业数（也称道数），为在主机上运行的当前作业数。如果，且存在后备作业，则启动作业调度；（）当一作业运行终止而被撤销后，如果存在后备作业，则立即启动作业调度崐；（）在分时系统中，当一用户在某终端上通过交互会话被核准其注册的登录作业名及其口令后，立即启动作业调度。,.进程调度的功能与时机,启动进程调度的时机可归结为：（）现行进程执行完它的当前时值时，这包括现行进程执行完毕而终止或现行进程因等待某个事件而自行阻塞，此时需要将分配给一个新的就绪进程；（）在采用剥夺调度方式的系统中，当发生了某种剥夺事件，例如，当发生了时间片中断或有比现行进程具有更高优先级的进程进入了就绪队列时，此时系统要回收现行进程占用的并进行重新调度。,.调度方式,一进程在上的一次连续执行过程称为该进程的一个周期。一个周期由进程自我终止。当进程需等待某个事件而进入等待态时，便终止了它的当前周期。待等待事件发生后，进程将开始下一个周期。进程执行完毕进入停止状态则终止了它的最后一个周期。一个进程在其并发运行过程中通常有若干个离散的且长短不等的周期。例如，一进程需要在上执行的总时间为，在、的执行点处它分别要等待三个事件而暂停执行，即该进程有四个分别为、以及 的周期时值。当现行进程执行完它的一个周期时，系统应及时把转交给另一个进程去执行它的周期，这是导致进程调度的基本原因，也是实现多部件并行和多进程并发的基本要求。,进程调度方式包括剥夺式与非剥夺式。在剥夺方式下，当现行进程正在执行它的一个周期期间，系统有权强行分割该进程的当前时值，即强行剥夺现行进程正占用的，并把分配给另一进程，换言之，如果一个进程的一个周期可能被分割成两个或更多个周期，则系统采用的是剥夺式调度。反之，在非剥夺方式下，一个进程一旦获得便一直执行下去，直到完成它的当前周期，系统才重新调度，换言之，系统无权分割进程的任一周期。,调度原则与评估标准,一般需综合考虑以下四个基本调度原则：（）尽量提高系统的吞吐量，系统吞吐量是指在单位时间内完成的平均作业数；（）均衡利用资源，使与外设尽量都保持“忙”状态；（）对所有的作业都应公平，任何一个作业的完成都不能被无限延迟；（）如果支持优先级，应对优先级高的作业或进程给予优先服务。,下面是几项主要的评估标准：（）平均周转时间 作业从提交时刻is到完成时刻ic所经历的时间称为该作业的周转时间，即icis；进程从进入就绪队列的时刻ir到执行完本次周期的时刻ic称为该进程的周转时间i，即iicir。于是，个作业的平均周转时间或个进程的平均周转时间为：,（）平均带权周转时间 作业的周转时间Ti与其实际运行时间i之比 称为该作业的带权周转时间，即，同样，进程的周转时间与其本次周期的时值之比 称为该进程的带权周转时间。于是，个作业或个进程的平均带权周转时间为：,（）平均等待时间 进程从进入就绪队列那一时刻ir到获得的那一时刻ip所经历的时间称为它的等待时间i，即iipir，那么个进程的平均等待时间为：,通常，用来衡量不同调度算法对同一作业流或同一进程集的调度性能，用来衡量不同进程调度算法对同一进程集的调度性能，而用来衡量同一调度算法对不同作业流或不同进程集的调度性能。,调 度 算 法,.先来先服务,假定有四个作业，它们的进入、估计运行和完成时间以及平均周转时间和平均带权周转时间如表-所示。,考虑三个进程、和，它们的本次周期的时值分别为、和，且以、的次序处于就绪队列中，不妨认为它们进入就绪队列的相对时刻均为。于是，在调度下，其执行过程可表示如下：,0,21,27,30,、和的等待时间分别为、和，周转时间分别为、和，故它们的平均等待时间和平均周转时间分别为：,算法本质上是非剥夺式的，如果可剥夺，则不能保证原则的实施。例如，对上述三个进程，若按时间片进行剥夺式调度，且规定时间片，则执行过程可表示如下：,0,21,27,30,6,12,15,.最短者优先,.最高响应比者优先,HRN（Highest-Response-ratio-next)）算法是为了克服算法和算法的缺点而提出的，是这两种算法的一种折衷。一个作业或进程的响应比定义为：响应时间需运行时间（已等待时间需运行时间）需运行时间 已等待时间需运行时间,调度程序开始调度时，首先计算各个后备作业或各个就绪进程的响应比，然后选择值最大的作业或进程。响应比既是需运行时间的函数，也是等待时间的函数。由于与需运行时间成反比，故短作业或短进程可获得较 高的响应比；另一方面，因与等待时间成正比，故长作业或长进程随着其等待时间的增长，也可获得较高的响应比。这就是说，算法既优待了短作业或短进程，又照顾了先来者。,.轮转法,（）算法是一种剥夺式的进程调度算法，它依据公平服务的原则，将时间划分成一个个的时间片（记为S），并以为单位，轮转地为各个就绪进程一次分配一个时间片。,以前述的三个进程为例，考察算法的执行情况及其调度性能。设，则有：,0,4,8,11,15,17,21,25,29,30,进程首先执行一个时间片并被剥夺，其周期所剩余的 放到以后执行；执行一个时间片后也被剥夺；的时值为，不足一个时间片。第二轮开始，又由先执行一个时间片后被剥夺；这次只执行。至此，和的周期已先后完成，故随后连续个时间片都分给了，直至完成，在最后一个时间片里，只执行了。容易算出，该例的平均等待时间和平均周转时间分别为：,其中，为系统的响应时间上限，为系统中的进程数目上限。例如，设，则0.1。,.最高优先级法,优先级通常是用一个整型数来表示，称为优先数。对于不同的系统，既可以用较大的数也可以用较小的数来表示较高的优先级，这并无统一的规定。例如，中的优先数的取值范围为，且规定优先数愈小其表示的优先级愈高。优先级的设置分为静态和动态两种方式：（）静态设置方式（）动态设置方式,设有五个就绪进程，它们各自的本次周期的长度、初始优先数及进入就绪队列的相对时刻如下所示：,在非剥夺的静态设置方式下，执行情况如下：,0,4,36,52,60,62,在进程执行完时，已进入就绪队列，因其优先级较高，故先于和之前执行。可算得这些进程的平均等待时间、平均周转时间以 及平均带权周转时间分别为：,.多级反馈队列,多级反馈队列就是综合了、和的 一种进程调度算法，其基本思想如下：（）系统按优先级别设置个就绪进程队列，第一级队列的优先级最高，以下逐级降低，第级队列的优先级最低；（）每个就绪队列对应有一个时间片Si（i，2,，n），且有，一般有2Si；（）除对第级队列按调度外，对其余各级队列均按调度；,（）系统每次总是调度级别较高的队列中的进程，仅当该队列为空时，才去 调度下一级队列中的进程；（）当现行进程正在执行它的周期时，如果发生了时间片中断或有进 程进入更高级的就绪队列时将引起剥夺，对前一种情况，现行进程将进入下一 级队列，对后一种情况，现行进程则进入本级队列末尾。当一进程被唤醒时，它进入的是原先离开的那个队列，即与其当前优先级对应的就绪队列。可见，一个进程的优先级被降低，仅发生在因时间片中断而被剥夺的时候。,图-多级反馈队列,调 度 的 实 现,进程调度程序是内核原语，当发生了引起调度的某种事件时，由有关的内核程序转入。例如：当发生时间片中断后，由时钟中断处理程序转入；当现行进程 因等待某个事件而进入等待队列时，由阻塞原语转入；当现行进程崐执行完毕自我停止后，由停止原语转入；当一进程被唤醒后，由唤醒 原语转入。,