2处理机调度与常见算法

《2处理机调度与常见算法》由会员分享，可在线阅读，更多相关《2处理机调度与常见算法（77页珍藏版）》请在金锄头文库上搜索。

1、*山东农业大学计算机系1第3章 处理机调度与死锁1处理机调度相关基本概念2常用调度算法3实时调度4产生死锁的原因和必要条件5预防死锁的方法6死锁的检测与解除 *山东农业大学计算机系2处理机调度：多道程序环境下，动态的 把处理机分配给就绪队列中的一个进程使之 执行。 提高处理机的利用率、改善系统性能， 很大程度上取决于处理机调度的性能。 处理机调度便成为OS设计的中心问题之 一。分配的任务由处理机调度程序完成。*山东农业大学计算机系3一、处理机调度的基本概念v作业进入系统驻留在外存的后备队列上，再 至调入内存运行完毕，可能要经历下述三级 调度。 高级调度（High Scheduling） 中级调

2、度（Intermediate-Level Scheduling） 低级调度（Low Level Scheduling）*山东农业大学计算机系41、高级调度（High Scheduling）v又称作业调度或长程调度(Long-Term Scheduling),接纳调度(Admission Scheduling) 主要在早期批处理阶段，处理在外存上的作业 。决定外存后备队列中的哪些作业调入内存;为它们创建进程、分配必要的资源;将新创建的进程排在就绪队列上，准备执行。 * 管理的方面比较多。*山东农业大学计算机系5在每次执行作业调度时，都须作出两个决定：v接纳多少作业取决于多道程序度。多道程序度。应

3、根 据系统的规模和运行速度等情况综合考虑。v接纳哪些作业取决于采用的调度算法。采用的调度算法。 如先来先服务，短作业优先等（后面详细介绍 ）* 作业调度决定的细节*山东农业大学计算机系6v批处理系统：作业进入系统后先驻留外存， 故需要有作业调度。v分时系统：为及时响应，作业由终端直接送 入内存，故不需作业调度。v实时系统中，通常也不需作业调度。* 系统运行并不一定存在高级调度*山东农业大学计算机系72、低级调度（Low Level Scheduling ）v也称为进程调度、微观调度或短程调度（ Short-Term Scheduling） 决定内存就绪队列中的哪个进程获得处理 机，进行分配工作

4、。是最基本的一种调度，是最基本的一种调度， 在三种基本在三种基本OSOS中都有。中都有。*山东农业大学计算机系8进程调度方式1）非抢占方式（Non-preemptive Mode） 一旦处理机分配给某进程，该进程一直执行。 决不允许其他进程抢占已分配运行进程的处理机。 2）抢占方式（Preemptive Mode） 允许调度程序根据某种原则，暂停某个正在执 行的进程，将处理机重新分配给另一进程。*山东农业大学计算机系9进程调度方式比较进程调度方式 调度的时机特点 非抢占方式程序完成； 发生某事件阻塞；实现简单、系统开销小； 功能也简单，适用于大多数 批处理OS，但在要求较严格 的实时系统，不宜

5、采用该方 式抢占方式程序完成； 发生某事件阻塞； 新进程出现；抢占的原则有很多种：优 先权高的可以抢占优先级低 的进程的处理机。短作业（ 进程）可以抢占长作业（进 程）的处理机。各进程按时 间片运行，一个时间片用完 时重新进行调度。*山东农业大学计算机系103、中级调度（Intermediate-Level Scheduling）v又称交换调度或中程调度（Medium-Term Scheduling） 引入目的：提高内存利用率和系统吞吐量 。根据条件将一些进程调出或再调入内存。*山东农业大学计算机系11进程调度：运行频率最高，算法不能太复杂， 以免占用太多的CPU时间。分时系统通常 10100

6、ms便进行一次。 作业调度：一个作业运行完毕退出系统时即触 发重新调度一个新作业入内存，周期较长， 大约几分钟一次。因而也允许作业调度算法 花费较多的时间。 中级调度：运行频率基本上介于上述两种调度 之间。三种调度的频率和复杂度*山东农业大学计算机系124、调度队列模型不论高级、中级或者低级调度，都涉及到进程队 列，由此形成了三类调度队列模型。从这三种方式中 体验调度的过程。仅有进程调度的调度队列模型具有高级和低级调度的调度队列模型同时具有三级调度的调度队列模型*山东农业大学计算机系131）仅有进程调度的调度队列模型uu常见情况：常见情况： 分时系统。 通常仅设置进程调度，用户键入的命令和数

7、据，都直接送入内存。 uu调度对象：调度对象： 处于就绪状态的进程。 uu组织形式：组织形式： 栈、树或一个无序链表 用何种形式取决于OS类型和采用的调度算法 。如：分时系统中把就绪进程组织成FIFO队列形式：按 时间片轮转方式运行。 进程调度过程如下图：*山东农业大学计算机系14每个进程在执行时按规定的时间片算法，在给定 时间片内任务有三种执行情况：完成工作，释放处理机进入完成状态完成工作，释放处理机进入完成状态未完成，将该任务再放入就绪队列末尾未完成，将该任务再放入就绪队列末尾因某事件而被阻塞，被因某事件而被阻塞，被OSOS放入阻塞队列放入阻塞队列FIFO 就 绪 队 列时间片完阻 塞 队

8、 列等待 事件CPU进程进程调度调度进程 完成交互 用户事件出现进程管理、状态转换部分的工作进程管理、状态转换部分的工作*山东农业大学计算机系152）具有高级和低级调度的调度队列模型v批处理系统中，还需要作业调度CPU就 绪 队 列时间片完进程 调度等待事件1进程完成后备队列等待事件2等待事件n事件1出现事件2出现事件n出现作业 调度*山东农业大学计算机系163）同时具有三级调度的调度队列模型引入中级调度后，进程的状态变化：v就绪状态：分为内存就绪和外存就绪。v阻塞状态：分为内存阻塞和外存阻塞。 中级调度使进程在上述状态间变化，并使 数据在内外存间互换。*山东农业大学计算机系17就就 绪绪 队

9、队 列列等 待 事 件事件出现就绪、挂起队列事件 出现阻阻 塞塞 队队 列列挂 起交互型作业作业 调度后备队列批 量 作 业时间片完CPU进程 调度进程完成阻塞、挂起队列挂 起中级 调度*山东农业大学计算机系185. 选择调度方式和调度算法的若干准则v什么算法是好算法？ ：不同的情况和对象需求不同，适用的方式和算 法也不同。1)面向用户的准则 2)面向系统的准则*山东农业大学计算机系191)面向用户的准则vv周转时间短：周转时间短： 针对批处理系统的性能指标。作业从提交到完成所经历 的时间。 真正执行用时a总的等待时间b = 在后备队列中等待 + 就绪队列上等待+ CPU上执行 + 阻塞队列中

10、等待（等待I/O操作结果）周转时间T=b+a带权周转时间W= T/a平均周转时间、平均带权周转时间（n个作业求平均）*山东农业大学计算机系20vv响应时间快：响应时间快：针对分时系统。用户输入一个请 求（如击键）到系统给出首次响应（如屏幕显示 ）的时间vv截止时间的保证：截止时间的保证：针对实时系统的性能指标 。开始截止时间和完成截止时间。任务必须按规 定的时间开始或完成，调度方式和算法必须能保 证该要求。vv优先权准则：优先权准则：三大基本OS在调度算法的选择 时都可遵循。可以使关键任务达到更好的指标。*山东农业大学计算机系212)面向系统的准则v系统吞吐量高：批处理系统的重要指标。单位时间

11、内所完成的作业数，跟作业本身 （与作业平均长度密切相关）和调度算法 都有关系；v处理机利用率好(主要针对大中型主机)v各类资源的平衡利用(主要针对大中型主机)*山东农业大学计算机系22第3章 处理机调度与死锁1处理机调度相关基本概念2常用调度算法3实时调度4产生死锁的原因和必要条件5预防死锁的方法6死锁的检测与解除 *山东农业大学计算机系23二、 调度算法v调度的实质就是一种资源分配。不同的系统和系 统目标，通常采用不同的调度算法适合自己 的才是最好的。如批处理系统为照顾为数众多的短作业，应采用短作 业优先的调度算法；如分时系统为保证系统具有合理的响应时间，应采用 轮转法进行调度。目前存在的多

12、种调度算法中，有的算法适用于作业调 度，有的算法适用于进程调度；但有些算法作业调度 和进程调度都可以采用。*山东农业大学计算机系241、先来先服务调度算法FCFS(First Come First Service)一种最简单的调度算法，按先后顺序进行调度。既 可用于作业调度，也可用于进程调度。v按照作业提交，或进程变为就绪状态的先后次 序分派CPU；v新作业只有当当前作业或进程执行完或阻塞才 获得CPU运行v被唤醒的作业或进程不立即恢复执行，通常等 到当前作业或进程出让CPU。 （所以，默认即 是非抢占方式）*山东农业大学计算机系25* 不利于短作业（进程） 时间分析举例：进程 名称到达 时间

13、执行 时间 长度开始 时间完成 时间周转 时间 长度带权 周转 时间abcd=c+bt=d-aw=t/cA010111B110011011001C21101102100100D31001022021991.99*山东农业大学计算机系26v不足：短作业C的带权周转时间竟高达100，这 是不能容忍的；而长作业D的带权周转时间仅为 1.99。v关于应用：有利于CPU繁忙型的作业，而不利 于I/O繁忙的作业（进程）。zI/O繁忙型作业，CPU进行处理时，需频繁的请求I/O， 实际cpu处理时间比较短。FCFS不利于短作业。z目前大多数事务处理都属于I/O繁忙型作业。*山东农业大学计算机系272. 短作

14、业（进程）优先调度算法SJF/SPF2.12.251.51.53.22.671带权周转时间893 31684周转时间1361894完成时间SJF2.83.55.55.5221带权周转时间91411111064周转时间18141274完成时间FCFS42534执行长度43210到达时间平均EDCBA进程名 作业情况 调度算法*山东农业大学计算机系28优点：v通过上表可见采用SJF/SPF算法，平均周转 时间、平均带权周转时间都有明显改善。 SJF/SPF调度算法能有效的降低作业的平均 等待时间，提高系统吞吐量。 方式：v分抢占和非抢占两种方式，上例为简单的非 抢占式。(Shortest Job

15、First) OR (Shortest Process First)*山东农业大学计算机系29作业进入时间 运行时间 A04 B18 C33 D42vSPF（抢占）调度算法的时 间分析举例：0 1 2 3 4 5 6 14 15 16 17ABCD标明关键的时间点 分析时实时画出就绪队列排队情况A就绪队列B就绪队列ABC D就绪队列CAB执行 进程*山东农业大学计算机系30vSJF/SPF的不足： 1. 对短作业有利，但同时造成了对长作 业的不利。2.由于作业（进程）的长短含主观因素， 不一定能真正做到短作业优先。3.未考虑作业的紧迫程度，因而不能保证 紧迫性作业（进程）的及时处理。*山东农业

16、大学计算机系313. 高优先权优先调度算法HPF Highest Priority First 照顾紧迫性作业，使其获得优先处理而引入 调度算法。常用于批处理系统中的作业调度算法 ，以及多种操作系统中的进程调度算法 1) 分两种方式：v非抢占式优先权算法v抢占式优先权算法 关键点：新作业产生时*山东农业大学计算机系322)优先权的类型vv静态优先权：静态优先权：创建进程时确定，整个运行 期间保持不变。一般利用某一范围的一个 整数来表示，又称为优先数。vv动态优先权：动态优先权：创建进程时赋予的优先权可 随进程的推进或随其等待时间的增加而改 变。*山东农业大学计算机系33vv关于进程优先权的确定？依据如下：关于进程优先权的确定？依据如下：1)进程类型：一般来，系统进程高于用户进程。2)进程对资源的需求：如进程的估计时间及内存需 要量的多少，对要求少的进程赋予较高优先权。3)用户要求：由用户进程的紧迫程度及用户所付费 用的多少来确定优先权的。*山东农业大学计算机系343