处理器调度

《处理器调度》由会员分享，可在线阅读，更多相关《处理器调度（33页珍藏版）》请在金锄头文库上搜索。

1、,处理机调度,概述,CPU是计算机系统中十分重要的资源。早期的计算机系统中，对它的管理十分简单，因为那时它和其他系统资源一样，为一个作业所独占。 随着多道程序设计技术和各种不同类型操作系统的出现，也出现了各种不同的CPU的管理方法。,6.1 处理机的多级调度,2,处理机调度 四个层次： 高级调度(作业调度、宏观调度) 中级调度(交换调度) 低级调度(进程调度,微观调度) 线程调度不同类型的操作系统往往采用不同的处理机分配方法,2. 批处理系统中的处理机调度处理机调度分为两级：作业调度和进程调度 作业调度 宏观调度任务对存放在辅存设备上的大量作业，以一定的策略进行挑选，分配主存等必要的资源，建立

2、作业对应的进程，使其投入运行。,进程调度 微观调度任务对进入主存的所有进程，确定哪个进程在什么时候获得处理机，使用多长时间。,4,多任务操作系统中的处理机调度 进程调度 多线程操作系统中的处理机调度 线程调度：当处理机空闲时，以某种策略选择一个就绪线程去运行，并分配处理机时间。,6.2 针对作业的调度,1 作业的状态 一个作业从提交给计算机系统开始到返回执行结果为止，一般要经历提交、收容、执行、完成四个状态。,正从输入设备进入外存,全部进入外存，但还未被作业调度程序选中,被作业调度程序被选中，建立进程并分配必要资源，投入运行,运行完毕，但未释放全部资源,8,确定数据结构建立作业控制块jcb (

3、job conrol block)。作业控制块记录了每个作业类型、状态、资源请求及分配情况。 确定调度策略与调度算法,2. 作业调度的功能,分配资源为选中的作业分配所需要的系统资源。 善后处理收回该作业所占用的全部资源，撤消作业控制块以及与该作业有关的全部进程资源。,周转时间一个作业提交给计算机系统到该作业的结果返回给用户所需要的时间。 定义 ti = tci - tsiti作业i的周转时间 tsi作业i的提交时间tci作业i的完成时间 意义 说明作业 i 在系统中停留时间的长短 平均周转时间 t =,3. 作业调度算法性能的衡量的功能采用平均周转时间和平均带权周转时间衡量作业调度算法性能的好

4、坏。,带权周转时间 定义：一个作业的周转时间与其运行时间的比值 wi =意义 说明作业 i 在系统中相对等待时间平均带权周转时间 w =,先来先服务调度算法(FCFS) 策略：按作业来到的先后次序进行调度。 特点： 简单，易实现。 讨论：先来先服务调度算法下的周转时间、带权周转时间,4. 常用的作业调度算法,先来先服务调度算法(FCFS) 作业 提交时间 执行时间 开始时间 完成时间 周转时间 带权周转时间1 8.00 2.00 2 8.50 0.50 3 9.00 0.104 9.50 0.20,短作业优先调度算法 策略：按作业请求运行的时间长短进行调度。 特点： 易实现，系统吞吐量高。 讨

5、论：短作业优先调度算法下的周转时间与带权周转时间,短作业优先(SFS) 作业 提交时间 执行时间 开始时间 完成时间 周转时间 带权周转时间1 8.00 2.00 2 8.50 0.50 3 9.00 0.104 9.50 0.20,平均周转时间 t = 平均带权周转时间 w =,8.00 10.00 2.00 1,10.30 10.80 2.30 4.6,10.00 10.10 1.10 11,10.10 10.30 0.80 4,1.725,6.875,1.55,5.15,相应比高者优先优先,这种方法是对FCFS方式和SJF方式的一种综合平衡。当需要从就绪队列中选择进程投入运行时，先计算这

6、个进程的响应比，选择响应比最高的进程运行。响应比R的定义：R = ( W + T) /T = 1 + W/T W：为该作业等待时间T：为该作业估计需要的执行时间,平均周转时间：（2+1.1+2.1+1.30)/4 =1.625 平均带权周转时间：（1+11+4.2+6.5)/4 =5.675,6.3 进程调度,调度在众多处于就绪状态的进程中，按一定的原则选择一个进程。 分派 当处理机空闲时，移出就绪队列中第一个进程，并赋予它使用处理机的权利。,1. 调度分派结构,进程管理的数据结构 决定调度策略 优先调度 就绪队列按进程优先级高低排序 先来先服务 就绪队列按进程来到的先后次序排序 实施处理机的

7、分配和回收,2. 进程调度的功能,17,什么是调度方式当一进程正在处理机上执行时，若有某个更为“重要而紧迫”的进程需要运行，系统如何分配处理机。 非剥夺方式让正在执行的进程继续执行，直到该进程完成或发生某事件而进入“完成”或“阻塞”状态时，才把处理机分配给“重要而紧迫”的进程。,3. 进程调度的方式,3. 进程调度的方式,剥夺方式当“重要而紧迫”的进程一到，便暂停正在执行的进程，立即把处理机分配给优先级更高的进程。,进程优先数调度算法 什么是进程优先数调度算法预先确定各进程的优先数，系统把处理机的使用权赋予就绪队列中具备最高优先权(优先数和一定的优先级相对应)的就绪进程。 优先数的分类及确定静

8、态优先数在进程被创建时确定，且一经确定后在整个进程运行期间不再改变。,4. 进程调度算法,静态优先数的确定 优先数根据进程所需使用的资源来计算 优先数基于程序运行时间的估计 优先数基于进程的类型 动态优先数进程优先数在进程运行期间可以改变。动态优先数的确定 进程使用CPU超过一定数值时，降低优先数 进程I/O操作后，增加优先数 进程等待时间超过一定数值时，提高优先数,5. 循环轮转调度算法 什么是循环轮转调度算法当CPU空闲时，选取就绪队列首元素，赋予一个时间片，当时间片用完时，该进程转为就绪态并进入就绪队列末端。该队列排序的原则是什么？,简单循环轮转调度算法就绪队列中的所有进程以等速度向前进

9、展。q = t/nt 为响应时间，n为进入系统的进程数目。q 值的影响? q太小，进程切换要消耗很多的时间，q太大，退化为FIFO,循环轮转调度算法的发展： 可变时间片轮转调度：每一轮开始，系统根据就绪队列中已有的进程数目计算一下q值，然后进行轮转。在此期间到达的进程暂时不进入就绪队列，等待此轮轮转完毕后再一次进入。此时再重新计算q的值。 多重时间片循环调度,6.多重时间片循环调度,系统从第一级开始调度，当第一级为空时，系统转向第二级队列，.。进程用完一个时间片放弃CPU时，进入下一级队列； 等待进程被唤醒时，进入原来的就绪队列；进程第一次就绪时，进入第一级队列。,就绪队列1,I,/,O,至,

10、CPU,S,1,就绪队列2,至,CPU,S,2,就绪队列3,至,CPU,S,3,就绪队列n,至,CPU,Sn,（,时间片,：,S,1,S,2,S,3,）,7. 调度用的进程状态变迁图,一个调度用的进程状态变迁图的实例,见P139,较复杂进程状态变迁的讨论,8 进程调度的时机,引起进程调度的原因和时机进程执行完毕；进程调用阻塞原语将自己阻塞起来；进程调用P操作，因资源不足而被阻塞，或调用V操作激活了等待资源的进程；,进程提出了I/O请求后被阻塞； 在分时系统中时间片已经用完； 在执行完系统调用后返回用户程序时，可能选择新进程执行； 就绪队列中进程的优先级高于当前进程，引起进程调度。 当出现上述七种情况之一时，发生处理机调度,处理机的多级调度 作业调度 进程调度,