文档介绍：第三章处理机调度与死锁
处理机调度的基本概念
调度算法
实时调度
多处理机系统中的调度
产生死锁的原因和必要条件
预防死锁的方法
死锁的检测与解除
处理机调度的基本概念
高级、中级和低级调度
1. 高级调度(High Scheduling)
在每次执行作业调度时,都须做出以下两个决定。
1) 接纳多少个作业
2) 接纳哪些作业
2. 低级调度(Low Level Scheduling)
1) 非抢占方式(Non-preemptive Mode)
在采用非抢占调度方式时,可能引起进程调度的因素可归结为这样几个:①正在执行的进程执行完毕, 或因发生某事件而不能再继续执行; ②执行中的进程因提出I/O请求而暂停执行;③在进程通信或同步过程中执行了某种原语操作,如P操作(wait操作)、Block原语、Wakeup原语等。这种调度方式的优点是实现简单、系统开销小,适用于大多数的批处理系统环境。但它难以满足紧急任务的要求——立即执行,因而可能造成难以预料的后果。显然,在要求比较严格的实时系统中,不宜采用这种调度方式。
2) 抢占方式(Preemptive Mode)
抢占的原则有:
优先权原则。
(2) 短作业(进程)优先原则。
(3) 时间片原则。
3. 中级调度(Intermediate-Level Scheduling)
中级调度又称中程调度(Medium-Term Scheduling)。引入中级调度的主要目的,是为了提高内存利用率和系统吞吐量。为此,应使那些暂时不能运行的进程不再占用宝贵的内存资源,而将它们调至外存上去等待,把此时的进程状态称为就绪驻外存状态或挂起状态。当这些进程重又具备运行条件、且内存又稍有空闲时,由中级调度来决定把外存上的哪些又具备运行条件的就绪进程,重新调入内存,并修改其状态为就绪状态,挂在就绪队列上等待进程调度。
调度队列模型
1. 仅有进程调度的调度队列模型
图 3 - 1 仅具有进程调度的调度队列模型
2. 具有高级和低级调度的调度队列模型
图 3-2 具有高、低两级调度的调度队列模型
就绪队列的形式。
(2) 设置多个阻塞队列。
图 3-2 示出了具有高、低两级调度的调度队列模型。该模型与上一模型的主要区别在于如下两个方面。
3. 同时具有三级调度的调度队列模型
图 3-3 具有三级调度时的调度队列模型
选择调度方式和调度算法的若干准则
1. 面向用户的准则
(1) 周转时间短。
可把平均周转时间描述为:
作业的周转时间T与系统为它提供服务的时间TS之比,即W=T/TS,称为带权周转时间,而平均带权周转时间则可表示为: