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

第三章处理机调度与死锁1处理机调度的基本概念在多道程序环境下，进程数目往往多于处理机数目。这就要求系统能够按某种算法，动态的把处理机分配给就绪队列中的一个进程，使之执行。分配处理机的任务是由处理机调度程序完成的。由于处理机是最重要的计算机资源，提高处理机的利用率及改善系统性能，在很大程度上取决于处理机调度的性能。因此，处理机调度便成为OS设计的中心问题之一。3.1处理机调度的层次和调度算法的目标3.1.1处理机调度的层次P85一个批处理型作业，从进入系统并驻留在外存的后备队列上开始，直至作业运行完毕，可能要经历下述三级调度。（期中考过！！要记住别称也要知道！！！）1.高级调度（HighScheduling），又称为作业调度或长程调度或接纳调度用于决定把外存上处于后备队列中的哪些作业调入内存，并为它们创建进程、分配必要的资源，然后将新创建的进程排在就绪队列上，准备执行。因此有时也称作业调度为接纳调度。在批处理系统中，因作业进入系统后先驻留在外存，故需要有作业调度，即高级调度。在分时系统中为做到及时响应，作业被直接送入内存，故不需作业调度，即高级调度。在实时系统中，通常也不需作业调度，即高级调度。在每次执行作业调度时，都须作出两个决定：P891)接纳多少作业——每次接纳多少作业进入内存，即允许多少个作业同时在内存中运行---多道程序度。其确定应根据系统的规模、运行速度等情况综合考虑。2)接纳哪些作业——应接纳哪些作业从外存调入内存，取决于所采用的调度算法。如先来先服务，短作业优先等，在§3.2中详细介绍。2、低级调度（LowLevelScheduling），也称为进程调度或短程调度用来决定就绪队列中的哪个进程应获得处理机，然后再由分派程序把处理机分配给该进程。为最基本的一种调度，三种OS（批处理、分时、实时。）中都有。进程调度可采用下述两种调度方式：P921)非抢占方式（Non-preemptiveMode）一旦把处理机分配给某进程后，便让该进程一直执行，直至该进程完成或发生某事件而被阻塞时，才把处理机分配给其他进程，决不允许进程抢占已分配出去的处理机。评价：实现简单、系统开销小；适用于大多数的批处理OS，但在要求比较严格的实时系统中，不宜采用这种调度方式2)抢占方式（PreemptiveMode）允许调度程序根据某种原则，去暂停某个正在执行的进程，将处理机重新分配给另一进程。抢占的原则：a)优先权原则：优先权高的可以抢占优先级低的进程的处理机。b)短作业（进程）优先原则：短作业（进程）可以抢占长作业（进程）的处理机。c)时间片原则：各进程按时间片运行，一个时间片用完时，停止该进程执行重新进行调度。第三章处理机调度与死锁23、中级调度（Intermediate-LevelScheduling），又称中程调度。引入目的是为了提高内存利用率和系统吞吐量。为此，应使那些暂时不能运行的进程不再占用宝贵的内存资源，而将它们调之外存去等待，把此时的进程状态称为就绪驻外存状态或挂起状态。当这些进程重又具备运行条件、且内存又稍有空闲时，由中级调度来决定把外存上的哪些又具备运行条件的就绪进程，重新调入内存，并修改其状态为就绪状态，挂在就绪队列上等待进程调度。中级调度实际上就是存储器管理中的对换功能，将在§4.4中详述。三种调度方式的运行频率：1)进程调度的运行频率最高，在分时系统中通常是10~100ms便进行一次进程调度，因而进程调度算法不能太复杂，以免占用太多的CPU时间。2)作业调度是发生在一个作业运行完毕，退出系统，而需要重新调度一个作业进入内存时，故作业调度的周期较长，大约几分钟一次。因而也允许作业调度算法花费较多的时间。3)中级调度的运行频率，基本上介于进程调度和作业调度之间。调度队列模型：（课本上没有！！）不论高级、中级或者低级调度，都涉及到进程队列，由此形成了三种类型的调度队列模型：1)仅有进程调度（即低级调度）的调度队列模型在分时系统中，通常仅设置进程调度。系统可以把处于就绪状态的进程组织成栈、树或一个无序链表，形式取决于OS类型和所采用的调度算法。在分时系统中就绪进程组织成FIFO队列形式，按时间片轮转方式运行。2)具有高级和低级调度的调度队列模型在批处理系统中，不仅需要进程调度，而且还需要作业调度，由作业调度按一定的调度算法，从外存的后备队列中选择一批作业调入内存，并为它们建立进程，送入就绪队列，然后才由进程调度算法按照一定的进程调度算法，选择一个进程，把处理机分配给该进程。第三章处理机调度与死锁33)同时具有三级调度的调度队列模型当在OS中引入中级调度后，可以把进程的就绪状态分为内存就绪和外存就绪。也可以把阻塞状态分为内存阻塞和外存阻塞两种状态。在调出操作的作用下，可使进程状态由内存就绪转变为外存就绪，由内存阻塞转变为外存阻塞；在中级调度的作用下，又可使外存就绪转变为内存就绪。3.1.2处理机调度的算法的目标在一个OS（操作系统）的设计中，应如何选择调度方式和算法，很大程度上取决于OS的类型和目标。如，在批处理系统、分时系统和实时系统中，通常都采用不同的调度方式和算法。选择的准则，有的是面向用户的，有的是面向系统的。1.处理机调度算法的共同目标1)资源利用率2)公平性3)平衡性4)策略强制执行2.批处理系统的目标P861)周转时间短（以下4个概念，课本P86，必须要掌握！！！）经常让计算！！！周转时间；平均周转时间带权周转时间；平均带权周转时间2)系统吞吐量高3)处理机利用率好3.分时系统的目标1)响应时间快；响应时间p87，概念要掌握！！2)均衡性4.实时系统的目标1)截止时间的保证：截止时间p87，概念要掌握！！2)可预测性第三章处理机调度与死锁43.2作业与作业调度（即高级调度或长程调度或接纳调度）在批处理系统中，因作业进入系统后先驻留在外存，故需要有作业调度。在分时系统中为做到及时响应，作业被直接送入内存，故不需作业调度。在实时系统中，通常也不需作业调度。在每次执行作业调度（即高级调度）时，都须作出两个决定：1)接纳多少作业2)接纳哪些作业在OS中调度的实质是一种资源分配，因而调度算法是指：根据系统的资源分配策略所规定的资源分配算法。对于不同的系统和系统目标，通常采用不同的调度算法：例如，在批处理系统中为照顾为数众多的短作业，应采用短作业优先的调度算法；又如在分时系统中，为了保证系统具有合理的响应时间，应采用轮转法进行调度。目前存在的多种调度算法中，有的算法适用于作业调度，有的算法适用于进程调度；但有些算法作业调度和进程调度都可以采用。作业调度算法：P893.2.3和P903.2.4“重要！！会考！！！”(一)先来先服务和短作业优先和短进程优先（课本上没有！！）调度算法1）先来先服务调度算法（FCFS）——照顾长作业。是一种最简单的调度算法，既可用于作业调度，也可用于进程调度。当在作业调度中采用FCFS算法时，每次调度都是从后备作业队列中，选择一个或多个最先进入该队列的作业，将它们调入内存，为它们分配资源、创建进程，然后放入就绪队列。在进程调度采用FCFS算法时，则每次调度是从就绪队列中选择一个最先进入该队列的进程，为之分配处理机，使之运行。FCFS算法比较有利于长作业（进程），而不利于短作业（进程）。例：下表列出了A、B、C、D四个作业分别到达系统的时间、要求服务的时间、开始执行的时间及各自的完成时间，并计算出各自的周转时间和带权周转时间。从表上可以看出，其中短作业C的带权周转时间竟高达100，这是不能容忍的；而长作业D的带权周转时间仅为1.99。FCFS调度算法有利于CPU繁忙型的作业，而不利于I/O繁忙型的作业（进程）CPU繁忙型作业：如通常的科学计算。I/O繁忙型作业：指CPU进行处理时，需频繁的请求I/O。2）短作业优先调度算法（SJF）——照顾短作业。“用于作业调度”“作业越短，其优先级越高！！”是从后备队列中选择一个或若干个估计运行时间最短的作业，将它们调入内存运行。3）短进程优先调度算法（SPF）“用于进程调度！！”（课本上没有！！！）是从就绪队列中选出一估计运行时间最短的进程，将处理机分配给它，使它立即执行并一直执行到完成，或发生某事件而被阻塞放弃处理机时，再重新调度。第三章处理机调度与死锁5例：采用SJF算法后，不论是平均周转时间还是平均带权周转时间，都较FCFS调度算法有较明显的改善，尤其是对短作业D。而平均带权周转时间从2.8降到了2.1。这说明SJF调度算法能有效的降低作业的平均等待事件，提高系统吞吐量。SJF调度算法的优缺点：优点：有效降低作业的平均等待时间，提高系统吞吐量。缺点：1)对长作业不利。2)该算法完全未考虑作业的紧迫程度，因而不能保证紧迫性作业（进程）会被及时处理。3)由于作业（进程）的长短含主观因素，不一定能真正做到短作业优先。(二)高优先权调度算法和高响应比优先调度算法4）高优先权优先调度算法P90和P943.3.3为照顾紧迫性作业，使之在进入系统后便获得优先处理，引入了最高优先权优先（FPF）调度算法。此算法常被用于批处理系统中，作为作业调度算法，也作为多种操作系统中的进程调度算法，还可用于实时系统中。它分为两种：P94a)非抢占式优先权算法b)抢占式优先权调度算法优先权的类型P94对于最高优先权优先调度算法，关键在于：1）、使用静态优先权、动态优先权；2）、如何确定进程的优先权。静态优先权：在创建进程时确定的，在进程的整个运行期间保持不变。一般利用某一范围的一个整数来表示，又称为优先数。动态优先权：在创建进程时所赋予的优先权可以随进程的推进或随其等待时间的增加而改变。确定进程优先权的依据有如下三个方面：进程类型：一般来说系统进程高于用户进程。进程对资源的需求：如进程的估计时间及内存需要量的多少，对要求少的进程赋予较高优先权。用户要求：由用户进程的紧迫程度及用户所付费用的多少来确定优先权的。SJF调度算法的优缺点：优点：有效降低作业的平均等待时间，提高系统吞吐量。缺点：1)对长作业不利。2)该算法完全未考虑作业的紧迫程度，因而不能保证紧迫性作业（进程）会被及时处理。3)由于作业（进程）的长短含主观因素，不一定能真正做到短作业优先。第三章处理机调度与死锁65）高响应比优先调度算法P90在批处理系统中，短作业优先算法是一种比较好的算法，其主要不足是长作业的运行得不到保证。我们为每个作业引入动态优先权，并使作业的优先级随着等待时间的增加而以速率a提高，则可解决问题。见下式：优先权=(等待时间+要求服务时间)/要求服务时间由于等待时间与服务时间之和就是系统的响应时间，故上式又表示为：Rp=响应时间/要求服务时间由上式（优先权=(等待时间+要求服务时间)/要求服务时间）可以看出：a)如作业等待时间相同，则要求服务的时间愈短优先权愈高，所以该算法利于短作业。b)当要求服务的时间相同，作业优先权的高低决定于其等待时间的长短，所以是先来先服务。c)对于长作业，作业的优先级可以随等待时间的增加而提高，当其等待时间足够长也可获得处理机。3.2作业假如有四道作业，它们的进入时间和运行时间由下表给出，在单道程序环境下，分别填写先来先服务和短作业优先情况的完成时间和平均周转时间。第三章处理机调度与死锁73.3进程调度——在3.1.1节“处理机调度的层次”介绍过进程调度。低级调度通常也称为进程调度或短程调度，用来决定就绪队列中的哪个进程应获得处理机，然后再由分派程序把处理机分配给该进程。为最基本的一种调度，三种OS中都有。进程调度（即低级调度）可采用下述两种调度方式：P921)非抢占方式（Non-preemptiveMode）2)抢占方式（PreemptiveMode）抢占的原则：P921)优先权原则：优先权高的可以抢占优先级低的进程的处理机。2)短作业（进程）优先原则：短作业（进程）可以抢占长作业（进程）的处理机。3)时间片原则：各进程按时间片运行，一个时间片用完时，停止该进程执行重新进行调度。进程调度算法在分时系统中，为保证能及时响应用户的请求，必须采用1）、基