第8讲 处理机调度与死锁之处理机调度的基本概念e.doc

《第8讲 处理机调度与死锁之处理机调度的基本概念e.doc》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、第八讲处理机调度与死锁之处理机调度的基本概念与调度算法引言处理机管理可以归结为进程管理。在多道程序环境下，进程数目往往多于处理机数目，就会竞争使用处理机，这样就要求系统采用某种算法，合理的分配处理机给那些就绪态进程，使之能够执行。分配处理机的任务是由处理机调度程序也就是进程调度程序来完成的，此为操作系统的核心问题之一。1调度的层次一个作业，从进入系统并驻留在外存的后备队列上开始，直到作业运行完，要经历三级调度：高级调度，低级调度和中级调度。也就是一个作业从提交到完成要经历三级调度。调度的层次如图所示：1.1高级调度（HighScheduling）(作业/

2、长程/宏观调度)1.1.1任务用于把外存上处于后备队列中的作业调入内存，并为它们创建进程、分配必要资源，再讲新创建的进程挂在就绪队列。注意：a)在批处理系统中，大多配有作业调度；分时/实时系统中，一般不配置。b)作业调度执行频率很低，甚至几分钟一次，甚至更久。1.1.2高级调度需要解决的问题a)接纳多少个作业？主要任务是从外存后备队列中选择多少作业进入就绪队列或挂起就绪，也就是允许多少作业同时在内存中运行，它决定着多道程序的“道或度”。若作业太多，则可能会影响系统的服务质量（如周转时间太长），若太少，又将导致系统资源利用率和吞吐量的下降。因此，应根据系统

3、的规模和运行速度来确定，同时要求I/O型进程与CPU型进程中和调度。b)接纳哪些作业？应将哪些作业从外存调入内存，将取决于调度算法（先来先服务、短作业优先等算法）1.2低级调度（lowlevelscheduling）（短程/CPU/进程/微观调度）1.2.1任务主要任务就是从就绪队列中选择一个进程来执行并给其分配处理机。注意：a)是OS中最基本的调度。b)调度频率非常高，一般几十毫秒一次。c)常采用非抢占（非剥夺）方式和抢占（剥夺）方式两种。1.2.2进程调度方式a)非抢占式（preemptivemode）原理：处理机分配给某进程后，便让该进程一直执行，

4、直到该进程完成或因某事件而被阻塞，才再把处理机分配给其它进程，决不允许某进程抢占已分配出去的处理机。特点：现简单，系统开销小，常用于批处理系统；但不利于处理紧急任务，故实时、分时系统不宜采用b)抢占式（preemptivemode）原理：度程序根据某种原则（时间片、优先权、短进程优先），停止正在执行的进程，而将处理机重新分配给另一进程。特点：处理紧急任务，故实时与分时系统中常采用。时间片、优先权、短进程优先原则见课本P71。例1，有三个进程P1、P2、P3先后到达，它们分别需要20、4和2个单位时间运行完毕。假如它们就按P1、P2、P3的顺序执行，且不可

5、剥夺，则三进程各自的周转时间分别为20、24、26个单位时间，平均周转时间是23.33个时间单位。假如用时间片原则的抢占式调度方式，可得到：02468101226P1P2P3P1P2P1P1...P12222216可见：P1、P2、P3的周转时间分别为26、10、6个单位时间，平均周转时间为14个单位时间。补充：衡量进程调度性能的指标有：周转时间、响应时间、截止时间。概念：u周转时间：作业从提交到完成（得到结果）所经历的时间。平均周转时间T。见课本74平均带权周转时间（带权周转时间W是T(周转)/T(CPU执行)〕u响应时间：用户输入一个请求（如击键）到

6、系统给出首次响应（如屏幕显示）的时间u截止时间：是指某任务必须开始执行的最迟时间，或必须完成的最迟时间。与周转时间有些相似。1.2中级调度（intermediate-levelscheduling）(中程/交换调度)1.2.1任务在内存和外存对换区之间按照给定的原则和策略选择进程对换，以解决内存紧张问题，从而提高内存的利用率和系统吞吐量，常用于分时系统或具有虚拟存储器的系统中。详见P72。2、调度队列模型在OS中的任何一种调度中，都将涉及到进程队列，由此形成了三种类型的调度队列模型。2.1仅有进程调度的调度队列模型仅有进程调度的调度队列模型2.2具有高级

7、和低级调度的调度队列模型2.3同时具有三级调度的调度队列模型3选择调度方式和算法的若干准则3.1面向用户的准则周转时间短、响应时间快、截止时间的保证、优先权准则3.2面向系统的准则系统吞吐量、处理机利用率好、各类资源平衡利用3.3最优准则最大的CPU利用率、最大的吞吐量、最短的周转时间、最短的等待时间、最短的响应时间4调度算法调度算法：是指根据系统的资源分配策略所规定的资源分配算法。这里所谓的调度算法，是指批处理系统、分时系统的调度，而不包括实时系统的调度。4.1先来先服务和短作业（进程）优先调度算法FCFS,FirstComeFirstService；

8、SJF,ShortestJobFirst；SPF，ShortestProcess