计算机操作系统(第03章)

《计算机操作系统(第03章)》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、第三章处理机调度与死锁3.1处理机调度的基本概念3.2调度算法3.3实时调度3.4多处理机系统中的调度3.5产生死锁的原因和必要条件3.6预防死锁的方法3.7死锁的检测与解除3.1处理机调度的基本概念3.1.1高级、中级和低级调度1.高级调度(HighScheduling)在每次执行作业调度时，都须做出以下两个决定。1)接纳多少个作业2)接纳哪些作业2.低级调度(LowLevelScheduling)1)非抢占方式(Non-preemptiveMode)在采用非抢占调度方式时，可能引起进程调度的因素可归结为这样几个：①正在执行的进程执行完

2、毕，或因发生某事件而不能再继续执行；②执行中的进程因提出I/O请求而暂停执行；③在进程通信或同步过程中执行了某种原语操作，如P操作(wait操作)、Block原语、Wakeup原语等。这种调度方式的优点是实现简单、系统开销小，适用于大多数的批处理系统环境。但它难以满足紧急任务的要求——立即执行，因而可能造成难以预料的后果。显然，在要求比较严格的实时系统中，不宜采用这种调度方式。2)抢占方式(PreemptiveMode)抢占的原则有：优先权原则。(2)短作业(进程)优先原则。(3)时间片原则。3.中级调度(Intermediate-Leve

3、lScheduling)中级调度又称中程调度(Medium-TermScheduling)。引入中级调度的主要目的，是为了提高内存利用率和系统吞吐量。为此，应使那些暂时不能运行的进程不再占用宝贵的内存资源，而将它们调至外存上去等待，把此时的进程状态称为就绪驻外存状态或挂起状态。当这些进程重又具备运行条件、且内存又稍有空闲时，由中级调度来决定把外存上的哪些又具备运行条件的就绪进程，重新调入内存，并修改其状态为就绪状态，挂在就绪队列上等待进程调度。3.1.2调度队列模型1.仅有进程调度的调度队列模型图3-1仅具有进程调度的调度队列模型2.具有高级

4、和低级调度的调度队列模型图3-2具有高、低两级调度的调度队列模型就绪队列的形式。(2)设置多个阻塞队列。图3-2示出了具有高、低两级调度的调度队列模型。该模型与上一模型的主要区别在于如下两个方面。3.同时具有三级调度的调度队列模型图3-3具有三级调度时的调度队列模型3.1.3选择调度方式和调度算法的若干准则1.面向用户的准则(1)周转时间短。可把平均周转时间描述为：作业的周转时间T与系统为它提供服务的时间TS之比，即W=T/TS，称为带权周转时间，而平均带权周转时间则可表示为:(2)响应时间快。(3)截止时间的保证。(4)优先权准则。2.面向

5、系统的准则系统吞吐量高。(2)处理机利用率好。(3)各类资源的平衡利用。3.2调度算法3.2.1先来先服务和短作业(进程)优先调度算法1.先来先服务调度算法图3-4FCFS和SJF调度算法的性能2.短作业(进程)优先调度算法短作业(进程)优先调度算法SJ(P)F，是指对短作业或短进程优先调度的算法。它们可以分别用于作业调度和进程调度。短作业优先(SJF)的调度算法，是从后备队列中选择一个或若干个估计运行时间最短的作业，将它们调入内存运行。而短进程优先(SPF)调度算法，则是从就绪队列中选出一估计运行时间最短的进程，将处理机分配给它，使它立即

6、执行并一直执行到完成，或发生某事件而被阻塞放弃处理机时，再重新调度。SJ(P)F调度算法也存在不容忽视的缺点：(1)该算法对长作业不利，如作业C的周转时间由10增至16，其带权周转时间由2增至3.1。更严重的是，如果有一长作业(进程)进入系统的后备队列(就绪队列)，由于调度程序总是优先调度那些(即使是后进来的)短作业(进程)，将导致长作业(进程)长期不被调度。(2)该算法完全未考虑作业的紧迫程度，因而不能保证紧迫性作业(进程)会被及时处理。(3)由于作业(进程)的长短只是根据用户所提供的估计执行时间而定的，而用户又可能会有意或无意

7、地缩短其作业的估计运行时间，致使该算法不一定能真正做到短作业优先调度。3.2.2高优先权优先调度算法1.优先权调度算法的类型非抢占式优先权算法在这种方式下，系统一旦把处理机分配给就绪队列中优先权最高的进程后，该进程便一直执行下去，直至完成；或因发生某事件使该进程放弃处理机时，系统方可再将处理机重新分配给另一优先权最高的进程。这种调度算法主要用于批处理系统中；也可用于某些对实时性要求不严的实时系统中。2)抢占式优先权调度算法在这种方式下，系统同样是把处理机分配给优先权最高的进程，使之执行。但在其执行期间，只要又出现了另一个其优先权更高的进程，

8、进程调度程序就立即停止当前进程(原优先权最高的进程)的执行，重新将处理机分配给新到的优先权最高的进程。因此，在采用这种调度算法时，是每当系统中出现一个新的就绪进程i