第九章单处理器调度浙江工业大学.ppt

* 进程名 到达 时间 服务时间 开始执行时间 完成时间 周转时间 带权周转时间 Ａ ０ ３ 0 4 Ｂ ２ ６ 2 Ｃ ４ ４ 4 Ｄ ６ ５ 6 Ｅ ８ ２ 时刻7: 时钟中断， D暂停，D排到RQ1队列 RQ0:（队头） RQ1： （队头） CD RQ2： （队头） B C执行 * 进程名 到达 时间 服务时间 开始执行时间 完成时间 周转时间 带权周转时间 Ａ ０ ３ 0 4 Ｂ ２ ６ 2 Ｃ ４ ４ 4 Ｄ ６ ５ 6 Ｅ ８ ２ 8 时刻8:E到达 时钟中断， C暂停，C排到RQ2队列 RQ0:（队头）E RQ1： （队头） D RQ2： （队头） BC E执行…… * 进程名 到达 时间 服务时间 开始执行时间 完成时间 周转时间 带权周转时间 Ａ ０ ３ 0 4 4 1.33 Ｂ ２ ６ 2 20 18 3 Ｃ ４ ４ 4 16 12 3 Ｄ ６ ５ 6 19 13 2.6 Ｅ ８ ２ 8 11 3 1.5 * * * 例题 分别采用FCFS、SPN和HRRN调度算法填充空白处。 * FCFS * SPN * HRRN * 作业 P301 9.2 P303 9.16 * 本章结束！ * 作业的基本概念 作业: 包含程序、数据和一份作业说明书，系统根据说明书来对程序的运行进行控制。 作业步： 在作业的运行期间，每个作业都必须经过若干个相对独立又相互关联的顺序加工步骤才能得到结果，我们把其中的每一步称为一个作业步。 一个典型的作业可分为三步：“编译”作业步、“连结装配”作业步、“运行”作业步。 作业控制块： 多道程序系统为每个作业设置一个作业控制块，它是作业在系统中存在的标志，其中保存了系统对作业进行管理和调度所需的全部信息。 * 作业的三个阶段和三种状态 收容阶段------后备状态 操作员把用户提交的作业，通过某种输入方式或SPOOLing系统，输入到磁盘上，再为该作业建立作业控制块，并把它放入作业后备队列中。此时作业的状态为后备状态。 运行阶段------运行状态 当作业被作业调度选中后，便为它分配必要的资源和建立进程，并将它放入就绪队列。一个作业从第一次进入就绪状态开始，直到它运行结束，为运行阶段，在此期间都处于运行状态。 完成阶段------完成状态 当作业运行完成，或发生异常情况而提前结束时，作业便进入完成阶段。相应地，作业状态为完成状态。 Back * 优先权的变化可描述为： 响应比 要求服务时间 响应时间 要求服务时间 要求服务时间 等待时间 优先权 = = + = R 该算法既照顾了短作业，又考虑了作业到达的先后次序，也不会使长作业长期得不到服务，是介于FCFS与SJF之间的一种算法，由于每次调用前，都要先进行响应比的计算，这会增加系统的开销。 Back 人有了知识，就会具备各种分析能力， 明辨是非的能力。 所以我们要勤恳读书，广泛阅读， 古人说“书中自有黄金屋。 ”通过阅读科技书籍，我们能丰富知识， 培养逻辑思维能力； 通过阅读文学作品，我们能提高文学鉴赏水平， 培养文学情趣； 通过阅读报刊，我们能增长见识，扩大自己的知识面。 有许多书籍还能培养我们的道德情操， 给我们巨大的精神力量， 鼓舞我们前进。 * 在多道程序环境下，系统中有多个就绪进程，进程数往往多于处理机数，操作系统必须决定哪个进程先执行，这就是调度。 * 就绪/挂起到就绪的转换：内存中没有就绪进程或当前处于就绪/挂起状态的进程比处于就绪态的任何进程的优先级都高 阻塞/挂起到阻塞的转换：一个进程终止，释放了一些内存，阻塞/挂起队列中有一个进程比处于就绪/挂起队列中任何进程的优先级都高，且操作系统相信这个进程的阻塞事件很快就会发生。 * 抄在黑板上 * 可与优先级调度算法相结合：调度程序可以维护多个队列，每个优先级一个队列，每个队列的调度基于FCFS * 为了减少在FCFS策略下短作业的不利情况，可采用基于时钟的抢占策略。 * 受CPU限制（ processor-bound）进程执行完一个时间片后，立即返回就绪队列。充分利用时间片。而受I/O限制（ I/O- bound）进程只使用很少的CPU时间(时间片未用完)，就被阻塞，等待I/O操作完成，然后加入就绪队列。体现出不公平的使用处理机时间. * 增加一个辅助队列，接收I/O阻塞完成的进程，调度优先于就绪队列，但占用的处理机时间等于基本时间片长减去上次运行的部分时间片。 * 减少FCFS固有的对长进程的偏向的另一种方法是最短进程优先策略。 * 针对SPN增加抢占机制，采用SRT。 *