OUC操作系统第三章处理机调度与死锁

《OUC操作系统第三章处理机调度与死锁》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、1第三章处理机调度与死锁3.1处理机调度的基本概念3.2调度算法3.3实时调度3.4多处理机系统中的调度(略)3.5产生死锁的原因和必要条件3.6预防死锁的方法3.7死锁的检测与解除3.1处理机调度的基本概念处理机调度的概念采用一定的算法(方法、规则)，从就绪队列中选择一个进程，让CPU来执行它。调度的三个级别高级调度（作业调度）中级调度（与挂起状态有关）低级调度（进程调度）23.1.1高级、中级和低级调度高级调度批处理系统特有的调度(分时、实时没有)作用决定把后备队列中的哪些作业调入内存，并为其创建进程、分配资源，并将其

2、插入到就绪队列。执行作业调度时，须作两个决定(考虑两个问题)：接纳多少作业——不易过多，也不能太少接纳哪些作业——取决于调度算法3低级调度（进程调度）三种操作系统都必须有的调度作用决定把CPU分配给就绪队列中的哪个进程，具体分派CPU的操作由分派程序执行。两种调度方式非抢占方式抢占方式注：进程调度比较频繁，因此进程调度算法不能太复杂，以免占用太多CPU时间4非抢占方式一旦将CPU分配给某进程，便让它一直运行，直到它完成或阻塞，才让另一个来执行可能引起调度的原因进程执行完毕，或因某事件不能执行下去提出I/O请求而暂停执行wa

3、it、block等原语优点实现简单、系统开销小，适用于大多数的批处理系统环境缺点难以满足紧急任务的要求——立即执行，因而可能造成难以预料的后果在要求比较严格的实时系统中，不宜采用5抢占方式允许按照某种原则暂停正在执行的进程，让另一个来执行抢占的原则优先权原则短作业(进程)优先原则时间片原则6中级调度引入的目的提高内存利用率和系统吞吐量作用把暂时不运行的进程放到外存等待，留出内存给其他进程使用在外存上的进程称为“挂起状态”当这些进程又具备运行条件、且内存有空位时，便选择一些调入内存，进入就绪状态78处理机的三级调度3.1.2

4、调度队列模型仅有进程调度的调度队列模型9就绪队列阻塞队列CPU进程完成进程调度等待事件交互用户事件出现时间片完就绪状态的进程常组织成栈、树、无序链表分时系统中，常组织成FIFO队列来了一个新进程，便放到队尾，并按时间片执行具有高级调度和低级调度的调度队列模型10就绪队列阻塞队列CPU进程完成进程调度等待事件1事件1出现时间片完阻塞队列阻塞队列等待事件2等待事件n事件2出现事件3出现后备队列作业调度批处理系统具有三级调度的调度队列模型11就绪队列就绪挂起队列CPU进程完成进程调度等待事件时间片完阻塞挂起队列阻塞队列事件出现后

5、备队列作业调度挂起事件出现中级调度3.1.3选择调度方式和调度算法的若干准则主要取决于OS的类型和目标面向用户的准则周转时间短——批处理系统响应时间快——分时系统截止时间的保证——实时系统优先权准则——适用于三种OS系统面向系统的准则系统吞吐量高——批处理系统CPU利用率好各类资源的平衡利用123.2调度算法调度的实质是一种资源分配调度算法的定义根据系统的资源分配策略所规定的资源分配算法调度算法的选择根据OS的类型和目标13先来先服务(FCFS)调度算法最简单的算法，可用于作业调度、进程调度基本思想谁先来，先为谁服务(类似

6、食堂排队打饭)特点有利于长作业(进程)，不利于短作业(进程)因为长作业的带权周转时间短14进程名到达时间服务时间开始执行时间完成时间周转时间带权周转时间A010111B110011011001C(短作业)21101102100100D(长作业)31001022021991.9915长作业有利的例子短作业(进程)优先调度算法(SJF、SPF)可用于作业调度、进程调度基本思想哪个估计运行时间最短，先运行哪个优点有效降低平均等待时间，提高系统吞吐量和FCFS相比，SJ(P)F中，平均周转时间、平均带权周转时间有明显改善缺点对长作

7、业(进程)不利没考虑作业(进程)的紧急程度由于是估计的运行时间，所以不一定能真正做到短的优先16高优先权优先调度算法(FPF)目的照顾紧迫型作业，使之进入系统后能被优先处理两种类型非抢占式一旦选择了优先权最高的进程执行，直到它结束或阻塞后，才选另一个执行抢占式若出现优先权更高的，则让出CPU这样可更好的满足紧迫性FPF算法的关键优先权是静态的，还是动态的？如何确定进程的优先权？17优先权类型静态优先权基本思想：创建进程时分配，保持不变确定优先权的依据进程类型：系统进程的>一般用户的进程对资源的需求：估计执行时间、内存需求少

8、的，优先权高用户要求：根据用户的紧迫度、用户所付费用来确定优点：简单易行、系统开销小缺点：不精确,优先权低的可能长时间无法执行适用：要求不高的系统18动态优先权基本思想随进程的执行或等待时间的增加而改变优先权低的等待一定时间后，优先权会提高规定当前执行的进程优先权随时间下降优点在抢占方式下，可防止长进程