第四章调度与死锁.ppt.ppt

第四章 调度与死锁 教学目的与要求： 1. 掌握调度与死锁的基本概念 2. 理解个调度算法和死锁地解决策略 3. 了解OS/2操作系统的调度 重点与难点： 1. 调度类型与调度算法 2. 多级反馈队列调度算法 3. 死锁的预防与银行家算法 主要内容： 4.1 调度的类型和模型 4.2 调度算法 4.3 实时系统中的调度 4.4 多处理机调度 4.6 死锁的基本概念 4.7 死锁的检测和解除 4.8 死锁的预防和避免 4.9 作业 4.1 调度的类型和模型 4.1.1 调度类型 作业从进入系统并驻留在外存的后备队列上开始，到作业运行完毕，可能要经历下述三级调度 一．高级调度，也叫作业调度或长期调度，主要问题有 1.接纳多少个作业 2.接纳哪些作业 二．低级调度，也叫进程调度或者短期调度 低级调度可采用非抢占方式和抢占方式两种 三．中级调度，也叫中期调度 主要目的是为了提高内存的使用效率和系统吞吐量 4.1.2 调度队列模型 在OS中的任何一种调度都涉及到进程队列，由此形成了三种类型的调度队列模型： 1．仅有进程调度的调度队列模型 2．具有高级和低级调度的调度队列模型 3．同时具有三级调度的调度队列模型　 ? 4.1.3 选择调度方式和算法的若干准则 一、 面向用户的准则 1.周转时间短 周转时间：是指从作业提交给系统开始到作业完成为止的这段时间间隔。包括四个部分： （1）作业在外存后备队列上等待调度的时间； （2）进程在就绪队列上等待调度的时间； （3）进程在CPU上运行的时间； （4）等待I/O操作完成的时间 2.响应时间快 响应时间：是从用户通过键盘提交一个请求开始，直到系统首次产生响应为止的时间。包括三部分： （1）请求信息传送到处理机的时间； （2）处理机处理信息的时间； （3）将形成的响应（处理结果）回送终端显示器的时间。 3.截止时间的保证 截止时间：是指某任务必须开始执行的最迟时间（即开始截止时间），或必须完成的最迟时间（即完成截止时间）。 4.优先权准则 优先权：是为了及时处理某些紧急作业而采取的一种措施。 二、 面向系统的准则（大中型系统中考虑较多） 1.系统吞吐量高，即单位时间内完成较多的作业 2.处理机利用率好 3.各类资源的平衡利用 4.2调度算法 所谓调度算法，就是根据系统的资源分配策略所规定的资源分配算法。 一． 先来先服务（FCFS）调度算法 1．将用户作业和就绪进程按提交顺序或变为就绪状态的先后排成队列，并按照先来先服务的方式进行调度处理，是一种最普遍和最简单的方法。 2．对于那些执行时间较短的作业或进程来说，如果它们在某些执行时间很长的作业或进程之后到达，则它们将等待很长时间。 3．在实际操作系统中，尽管很少单独使用FCFS算法，但和其他一些算法配合起来，FCFS算法还是使用得相当多的。 二． 时间片轮转调度算法 1．轮转法的基本思路是让每个进程在就绪队列中的等待时间与享受服务的时间成比例。轮转法的基本概念是将CPU的处理时间分成固定大小的时间片。 2．轮转法只能用来调度分配那些可以抢占的资源。将它们随时剥夺再分配给别的进程。作业调度不使用轮转法。 3．在轮转法中，时间片长度的选取非常重要。时间片长度的选择会直接影响系统开销和响应时间。如果时间片长度过短，则调度程序剥夺处理机的次数增多。这将使进程切换次数也大大增加，从而加重系统开销。如果时间片长度选择过长，比方说一个时间片能保证就绪队列中所需执行时间最长的进程能执行完毕，则轮转法变成了先来先服务法。 三． 多级反馈轮转调度算法 1．对加入到就绪队列的进程区别对待，即不同的情况给予不同的优先级和时间片，以进一步改善系统服务质量和效率。 这样，当一个进程在执行完它的时间片之后，或从睡眠中被唤醒以及被创建之后，将进入不同的就绪队列。 2．多级反馈轮转法与优先级法在原理上的区别是，一个进程在它执行结束之前，可能需要反复多次通过反馈循环执行，而不是优先级法中的一次执行。 四．优先权调度算法 1．优先级法可被用作作业或进程的调度策略。该算法的核心是确定进程或作业的优先级。 2．确定优先级的方法可分为静态法和动态法。静态法根据作业或进程的静态特性，在作业或进程开始执行之前就确定它们的优先级，一旦开始执行之后就不能改变。动态法则不然，它把作业或进程的静态特性和动态特性结合起来确定作业或进程的优先级，随着作业或进程的执行过程，其优先级不断变化。 3．基于静态优先级调度算法实现简单，系统开销小，但由于静态优先级一旦确定之后，直到执行结束为止始终保持不变，从而系统效率较低，调度性能不高。现在的操作系统中，如果使用优先级调度的话，则大多采用动态优先级的调度策略