《操作系统》 处理机管理课件

《《操作系统》 处理机管理课件》由会员分享，可在线阅读，更多相关《《操作系统》 处理机管理课件（29页珍藏版）》请在金锄头文库上搜索。

1、第3章 处理机管理本章目录3.1 处理机调度概述3.1.1 处理机调度的三个层次 3.1.2 进程调度的功能、时机和基本策略3.2 作业调度算法 3.2.1 先来先服务调度算法3.2.2 短作业优先调度算法3.5.3 Linux的进程调度算法3.2.3 最短剩余时间优先调度算法3.1.3 调度算法的性能评价指标3.4 实时处理与实时调度算法 3.4.1 实时处理的特征3.4.2 最早截止时间优先调度算法3.4.3 速率单调调度算法3.5 Linux的处理机调度 3.5.1 涉及调度的进程分类3.5.2 Linux的可运行队列3.2.4 最高响应比调度算法 3.3 进程调度算法 3.3.1 先来

2、先服务调度算法3.3.2 轮转调度算法3.3.3 优先级调度算法3.3.4 多级队列调度算法3.3.5 多级反馈队列调度算法3.1 处理机调度概述 o3.1.1 处理机调度的三个层次 高级调度 1.当系统决定接纳一个作业时，就要为它开辟一个作业控制块（ JCB），以便随时 记录作业的信息。 . . 被系统接纳的作业，在没有投入运行前是以“后备作业”的形式存放在辅存里。所 有后备作业的JCB链接在一起，形成“后备作业队列”。这些作业没有资格参与对处理机 的竞争，但系统从它们的里面去挑选参与CPU竞争的作业。. 高级调度决定哪个后备作业可进入系统去接受处理，它控制着多道程序设计环境 的“度”：进到

3、系统的作业多，资源的利用率提高了，但每个作业获得处理结果的时间可 能会长；进到系统的作业少，每个作业很快就得到自己的处理结果，但资源的利用率可 能会下降。 低级调度 2. 低级调度真正决定CPU下一次执行哪一个进程，它将按照一定的算法，从就绪队 列里挑选出可运行的进程投入运行。低级调度的各种算法，是我们讨论的主要目标。低 级调度也被称为“进程调度” 。中级调度 3. 中级调度是介于高级调度和低级调度之间的一种调度，如果系统为进程 设置有“挂起”状态，那么就会涉及到中级调度。也就是说，中级调度与实施 进程的内、外存交换有关。 CPU就绪队列低级调度释放中级调度 就绪/挂起队列时间片到 高级调度阻

4、塞/挂起队列阻塞队列中级调度事件等待事 件 发 生交互用户作业后备作业队列. 系统中出现过高并发度时，就应将 内存中的某些进程暂时换出 到外存；系统的并发 度较低时，就应该将 外存中的某些进程换 入到内存。进程在内、外存 间的换出和换入，就是中级调度承担的 责任，通过这种交换，以求达到调节和 平衡系统“并发度”的目的。 . 高级调度执行的频繁程度很低，它 只是粗略地决定是否接受一个新进程以 及接受哪一个；中级调度为了实施交换 决策，执行的频率相对要频繁一些；低 级调度要精确地决定执行哪一个进程，因此执行的频度为最高。 返回目录o3.1.2 进程调度的功能、时机和基本策略 1. 进程调度程序的功

5、能 .保护现场 .挑选运行对象 .恢复现场 2. 发生进程调度的时机 当某进程正常完成自己的运行或被终止时，为不让CPU空闲，必须实行调度，以 便从就绪队列里挑选新的进程投入运行。 . . 分时系统中，时钟中断处理程序发现分配给某个进程的时间片用完时，就强制它 交出CPU，重新进行CPU调度。 .运行中的进程提出I/O请求，或要等待别的进程发来消息，于是自己被阻塞。 .执行操作系统提供的某些系统调用命令，如wait()等。 . 某进程的状态从阻塞变为就绪时，要由调度程序决定让哪一个进程投入运行：是 新就绪进程、是正在运行的进程继续运行、还是调度另一个进程运行。 3. 进程调度的基本策略 非抢占

6、式：在把CPU分配给某个进程后，就一直让它使用下去，直到进程完成自 己的工作，或因要等待某事件的发生而交出CPU，否则不允许其他进程夺取CPU。 . . 抢占式：在调度程序把CPU分配给某进程使用后，只要满足某条件，就允许立即 把CPU从运行进程手中夺取过来，分配给满足条件的进程使用。 返回目录特定作业从提交给系统到获取结果所经历的时间间隔。因此，设作业i向系统提交 的时间为Tpi，完成时间是Tci，那么它的周转时间Ti为：Ti = Tci - Tpi 。o3.1.3 调度算法的性能评价指标 1.2.吞吐量 周转时间所谓“吞吐量”，是指单位时间内CPU完成作业的数量。 .有的作业属于“处理机限

7、制”型的，即需要花费大量的CPU时间，很少输入/输出， 也称“CPU繁忙”型；有的属于“I/O限制”型的，即它在运行期间主要是输入/输出，很少进 行计算和处理，也称“I/O繁忙”型。.作业的周转时间 作业的周转时间是指作业的执行时间加上作业的等待时间。设作业i的等待时间为 Twi，执行时间为Tsi，那么它的周转时间Ti为：Ti = Twi + Tsi 。（1）（2）.作业的平均周转时间 n个作业，每个作业的周转时间为Ti，那么它们的平均周转时间为：T=(Ti ) i=1nn1利用平均周转时间，可以基于同一批作业，来衡量不同调度算法的调度性能。 .作业的“带权周转时间”，指该作业的周转时间与所需

8、运行时间之比。 设作业i周转时间为Ti，所需执行时间为Ri，那么它的带权周转时间Wi为： .作业的平均带权周转时间 （3）n个作业，每个作业的带权周转时间为Wi，那么它们的平均周转时间为： .W=( )TiRi1 n利用平均带权周转时间，可基于同一调度算法，对不同批次作业的调度性能做出比 较。 .CPU的利用率 3.所谓“CPU的利用率”，是指在一定的时间区间内，CPU为用户提供服务的时间与其 总运行时间的比率。 作业i的CPU利用率Ui，是指该作业的执行时间Ci与周转时间Ti的比率。即： .Wi=Ti/RiUi=Ci/Ti.如果系统内有n个作业，那么整个系统CPU的平均利用率应为： U=(C

9、i/Ti ) i=1nn1公平性：调度的设计，应该顾及到所有作业或进程对CPU的不同需求，尽量做 到公平合理，不偏不倚。 设计目标：设计目标是决定算法的主要因素，目标不同，要求肯定不一样。比 如批处理系统的调度，应尽量提高各种资源的利用率，以及整个系统的吞吐量；分时系 统的调度，应将对用户提出的请求作出回应的速度，控制在用户能够容忍的范围内；实 时系统的调度，应保证对所发生的的事件做出及时的响应和处理；如此等等。 响应比 4所谓作业的“响应比”，是指一个特定作业的周转时间与它所需的执行时 间之比。 . 作业i的等待时间为Twi，执行时间为Tsi，那么该作业的响应比RRi是： RRi = ( T

10、wi + Tsi ) / Tsi影响调度算法设计的因素 .（1）（2）（3） 均衡性：调度算法应考虑资源使用的均衡性，使系统中的各种资源都能得到充 分地利用。比如，把“处理机限制”和“I/O限制”作业搭配，就有可能收到良好的效果。 （4） 兼顾性：调度算法应既考虑长作业的要求，也考虑短作业的要求；既考虑高优 先级进程的要求，也要顾及低优先级进程的利益。只偏袒某一方，所造成的后果有可能 是严重的，甚至是无法弥补的。 返回目录右示三个作业，按1、2、3的顺序提交给系统，采用 FCFS调度算法。画出它们的“甘特图”，计算每个作业的周转时 间及平均周转时间。（忽略系统调度所需额外的时间开销）作业1第1

11、个被作业调度程序选中运行，花费24个 CPU时间运行完毕，故周转时间是：T1=24-0=24；作业2等待24个CPU时间后被调度运 行，花费3个CPU时间运行完毕，故周转时间是：T2=27-0=27；作业3的周转时间是： T3=30-0=30。这三个作业的平均周转时间为(24+27+30)/3=27。 o3.2.1 先来先服务调度算法 3.2 作业调度算法 先来先服务（FCFS）作业调度算法，基于作业到达后备队列的先后次序以及作业对 系统资源的需求，从中挑选进入内存、成为参与CPU竞争的作业对象。有时也称为先进 先出（FIFO）作业调度算法。 .例3-1 ：作业所需CPU时间1 2 324 3

12、 3 解： 作业1作业2作业32433.所谓“甘特图”，即是指能够反映作业调度顺序及占用CPU时间的一种进度图。 右示五个作业，采用FCFS作业和进程调度算法，可供5个作业使用的内存空间为100KB，需要时按序分配。作业进入内存后，不许在内存中移动。计算每个作业的周转时间 和平均周转时间。（忽略系统调度时间，作业 都没有输入/输出请求）例3-2 ：作业所需CPU时间1 2 3 4 510.1 10.3 10.5 10.6 10.7到达时间所需内存量0.7 0.5 0.4 0.4 0.215KB 70KB 50KB 20KB 10KB解： .各作业的周转时间装入内存时间完成时间10.1 10.3

13、 11.3 11.3 10.7开始运行时间周转时间10.8 11.3 11.9 12.3 11.50.7 1.0 1.4 1.7 0.810.1 10.8 11.5 11.9 10.3.作业运行时的内存分配情况作业1(15KB)作业2(70KB)作业5(10KB)空闲(5KB)(a)到10.7时内存情形空闲(15KB)作业2(70KB)作业5(10KB)空闲(5KB)(b)到10.8作业1完成时内存情形作业3(50KB)作业4(20KB)作业5(10KB)空闲(5KB)(c) 到11.3作业2完成时内存情形空闲(15KB)这批作业的调度顺序是：12534，系统的平均作业周转时间为：(0.7+1

14、.0+1.4+1.7+0.8) / 5 = 1.12.返回目录各自的开始运行时间、完成时间、周转时间以及带 权周转时间如下所示。五个作业的调度顺序是ABECD。 有5个作业AE，情况如表所示，按照SJF进行作 业调度。计算它们各自的开始运行时间、完成时间、周转 时间以及带权周转时间。短作业优先（SJF）调度算法，总是在作业后备队列里选择要求运行 时间最短的、满足其资源需要的作业进入内存，参与对CPU的竞争。 o3.2.2 短作业优先调度算法.例3-4 ：作业所需CPU时间A B C D E0 2 4 6 8到达时间3 6 4 5 2解： 作业调度的gantt图 ：作业A作业B作业C作业E作业D

15、36425.开始运行时间 带权周转时间 0 3 11 15 9完成时间 周转时间3 7 11 14 31 1.17 2.75 2.80 1.503 9 15 20 11返回目录o3.2.3 最短剩余时间优先调度算法 . 最短剩余时间优先（SRTF）作业调度算法，是在调度时从后备作业队 列里挑选所需运行时间最短的作业投入运行。运行过程中，若有运行时间更 短的作业达到，那么它就抢占CPU，让当前正在运行的作业暂停执行。 例3-5 ： 有5个作业AE，情况如表所示，按照SRTF进 行作业调度。计算它们的开始运行时间、完成时间、周 转时间以及带权周转时间。作业所需CPU时间A B C D E0 2 4 6 8到达时间3 6 4 5 2解： . 各自的开始运行时间、完成时间、周转时间以及 带权周转时间如下所示。五个作业的调度顺序是：ABCEBD 。 .作业调度的gantt图 ：.开始运行时间 带权周转时间 0 3 4 15 8完成时间 周转时间3 13 4 14 21 2.17 1.0 2.80 1.03 15 8 20 10ABCEBD0348101520 时间E到达D到达C到达B到达A到达62返回目录各自的开始运行时间、完成时间、周转时间以及 带权周转时间如下所示。有5个作业AE，情况如表所示，按照HRRN进 行作业调度。计算它们的开始运行时间、完成时间、周转