在多道程序环境下，主存中有着多个进程，其数目往往多于处理机数目。这就要求系统能按某种算法，动态地把处理机分配给就绪队列中的一个进程，使之执行。分配处理机的任务是由处理机调度程序完成的。

处理机调度的层次

高级调度

高级调度(High Level Scheduling)又称为作业调度或长程调度(LongTerm Scheduling)。
高级调度是根据某种算法，把外存上处于后备队列中的那些作业调入内存。

作业（job）

作业是一个比程序更为广泛的概念，它不仅包含了通常的程序和数据，而且还应配有一份作业说明书，系统根据该说明书来对程序的运行进行控制。在批处理系统中，是以作业为基本单位从外存调入内存的。

作业控制块（JCB，job control block）

为了管理和调度作业，在多道批处理系统中为每个作业设置了一个作业控制块，如同进程控制块是进程在系统中存在的标志一样，它是作业在系统中存在的标志，其中保存了系统对作业进行管理和调度所需的全部信息。每当作业进入系统时，系统便为每个作业建立一个JCB，根据作业类型将它插入相应的后备队列中。

作业调度

作业调度的主要功能是根据作业控制块中的信息，审查系统能否满足用户作业的资源需求，以及按照一定的算法，从外存的后备队列中选取某些作业调入内存，并为它们创建进程、分配必要的资源。然后再将新创建的进程插入就绪队列，准备执行。

低级调度

通常也把低级调度(Low Level Scheduling)称为进程调度或短程调度(ShortTerm Scheduling)，它所调度的对象是进程(或内核级线程)。进程调度是最基本的一种调度，在多道批处理、分时和实时三种类型的OS中，都必须配置这级调度。

进程调度的三个基本机制

排队器、分派器（分配程序）、上下文切换机制。

进程调度的方式

（1）非抢占方式（nonpreemptive mode）
a. 定义：一旦把处理机分配给某个进程，无论该进程要运行多长时间，都不会因为其他原因而被抢占正在运行进程的处理机。直至该进程完成，自愿释放处理机。
b．优缺点：优点是实现简单，系统开销小，适用于大多数的批处理系统环境。但它难以满足紧急任务的要求——立即执行。
（2）抢占方式（preemptive mode）
a. 定义：根据某种原则去暂停某个正在执行的进程，将已分配给该进程的处理机重新分配给另一进程。
b. 优缺点：优点是，可以防止一个长进程长时间占用处理机，能为大多数进程提供更公平的服务，特别是能满足对响应时间有着较严格要求的实时任务的需求。但抢占方式比非抢占方式调度所需付出的开销较大。
c. 抢占调度方式遵循的原则

优先权原则。通常是对一些重要的和紧急的作业赋予较高的优先权。
短作业(进程)优先原则。短作业(进程)可以抢占当前较长作业(进程)的处理机。
时间片原则。各进程按时间片轮流运行，当一个时间片用完后，便停止该进程的执行而重新进行调度。

中级调度

中级调度(Intermediate Level Scheduling)又称中程调度(Medium-Term Scheduling)。中级调度就是存储器管理中的对换功能。

调度队列模型和调度准则

调度队列模型

仅有进程调度的调度队列模型

具有高级和低级调度的调度队列模型

在批处理系统中，一般作业调度和进程调度都存在，作业调度按照一定的作业调度算法，从外存的后备队列中选择一批作业调入内存，并为他们创建进程，送入就绪队列；而进程调度按照进程调度算法，选择一个进程，将处理机分配给该进程。

就绪队列的形式：在批处理系统中，最常用的是最高优先权优先调度算法，相应地，最常用的就绪队列形式就是优先权队列。其实可以是队列形式，也可以是无序链表形式。

同时具有三级调度的调度队列模型

调度算法

在OS中调度的实质是一种资源分配，因而调度算法是指：根据系统的资源分配策略所规定的资源分配算法。
批处理系统中，为了照顾为数众多的短作业，应采用短作业优先的调度算法；又如在分时系统中，为了保证系统具有合理的响应时间，应采用轮转法进行调度。

FCFS（first come first service，先来先服务）

FCFS既可用于作业调度，也可用于进程调度。FCFS比较利于长作业（或进程），而不利于短作业（或进程）。
缺点：由下面的带权周转时间的公式也可以看出，对于短作业（或进程），其服务时间比较短，则其带权周转时间就会很大，这是不能容忍的。

短作业（或进程）（SJ(P)F，short job（process） first）优先

SJ(P)F是指对短作业或短进程优先调度的算法，这里的“短”是估计的运行时间最短。
缺点：
该算法能有效降低短作业（或进程）的等待时间，但对长作业（或进程）不利。更可能导致长作业长期不会被调用；由于短作业（或进程）只是根据用户提供的估计运行时间而定，但估计也不一定准确。

高优先权优先（FPF，first priority fist）调度算法

当把该算法用于作业调度时，系统将从后备队列中选择若干个优先权最高的作业装入内存。当用于进程调度时，该算法是把处理机分配给就绪队列中优先权最高的进程。
（1）优先权调度算法的类型
a. 非抢占式优先权算法：主要用于批处理系统中，和对实时性要求不严的实时系统中。
b. 抢占式优先权算法：主要用于比较严格的实时系统中，和对性能要求较高的批处理和分时系统中。
（2）优先权类型
a. 静态优先权：在创建进程时确定的，且在进程的整个运行期间保持不变。
确定静态优先权的依据：

系统进程(如接收进程、对换进程、磁盘I/O 进程)的优先权高于一般用户进程的优先权。
对估计的运行时间和内存需求量少的进程应赋予较高的优先权。

b. 动态优先权：在创建进程时所赋予的优先权，是可以随进程的推进或随其等待时间的增加而改变的，以便获得更好的调度性能。

高响应比优先调度算法

在批处理系统中，短作业优先算法是一种比较好的算法，其主要的不足之处是长作业的运行得不到保证。如果我们能为每个作业引入动态优先权，并使作业的优先级随着等待时间的增加而以速率a 提高，则长作业在等待一定的时间后，必然有机会分配到处理机。

$$
优先权 = \frac{周转时间}{服务时间} = \frac{等待时间+服务时间}{服务时间} = \frac{响应时间}{服务时间} = 响应比
$$

由上式可以看出：

如果作业的等待时间相同，则要求服务的时间愈短，其优先权愈高，因而该算法有利于短作业。
当要求服务的时间相同时，作业的优先权决定于其等待时间，等待时间愈长，其优先权愈高，因而它实现的是先来先服务。
对于长作业，作业的优先级可以随等待时间的增加而提高，当其等待时间足够长时，其优先级便可升到很高，从而也可获得处理机。

简言之，该算法既照顾了短作业，又考虑了作业到达的先后次序，不会使长作业长期得不到服务。

基于时间片的轮转调度算法

在分时系统中，为保证能及时响应用户的请求，必须采用基于时间片的轮转式进程调度算法。
（1）时间片轮法（round robin，RR）
a. 基本原理：在早期的时间片轮转法中，系统将所有的就绪进程按先来先服务的原则排成一个队列，每次调度时，把CPU 分配给队首进程，并令其执行一个时间片。时间片的大小从几ms 到几百ms。当执行的时间片用完时，由一个计时器发出时钟中断请求，调度程序便据此信号来停止该进程的执行，并将它送往就绪队列的末尾；然后，再把处理机分配给就绪队列中新的队首进程，同时也让它执行一个时间片。使得系统能在给定的时间内响应所有用户的请求。
b. 时间片大小的确定：当时间片太小，将有利于短作业，但频换切换开销大；如果时间片太长，使得每个进程都能在一个事件片内完成，则时间片轮转算法退化为先来先服务调度算法。
时间片大小最好是一个时间片略大于一次典型交互所需要的时间。
c. 例：进程A、B、C、D需要运行的时间分别为20ms、10 ms、15 ms、5 ms，均在0时刻到达。到达的先后次序为A、B、C、D。如果时间片分别为1ms和5ms，计算各个进程的带权周转时间和平均带权周转时间。
解：采用时间片轮转法进行调度，算法的性能指标如下：

	进程名	到达时间	运行时间	开始时间	完成时间	周转时间	带权周转时间
时间片=1	A	0	20	0	50	50	2.5
	B	0	10	1	34	34	3.4
	C	0	15	2	45	45	3.0
	D	0	5	3	20	20	4.0
						平均周转时间=37.25	平均带权周转时间=3.225
时间片=5	A	0	20	0	50	50	2.5
	B	0	10	5	30	30	3.0
	C	0	15	10	45	45	3.0
	D	0	5	15	20	20	4.0
						平均周转时间=36.25	平均带权周转时间=3.125

（2） 多级反馈队列调度算法
前面介绍的各种用作进程调度的算法都有一定的局限性。如短进程优先的调度算法，仅照顾了短进程而忽略了长进程，而且如果并未指明进程的长度，则短进程优先和基于进程长度的抢占式调度算法都将无法使用。而多级反馈队列调度算法则不必事先知道各种进程所需的执行时间，而且还可以满足各种类型进程的需要，因而它是目前被公认的一种较好的进程调度算法。
a. 实施过程

设置多个就绪队列，并为各个队列赋予不同的优先级，第一个就绪队列的优先级最高，后面的队列优先级逐个降低。赋予各个队列中进程执行时间片的大小也各不相同，在优先权越高的就绪队列中，时间片越小。
当一个新进程进入内存后，首先将它放入第一队列的末尾，按FCFS原则排队等待调度。当轮到该进程执行时，如它能在该时间片内完成，便可准备撤离系统；如果它在一个时间片结束时尚未完成，调度程序便将该进程转入第二队列的末尾，再同样地按FCFS原则等待调度执行。即将长作业分解为短作业，以此类推。
仅当第一队列空闲时，调度程序才调度第二队列中的进程运行；仅当第1～(i-1)队列均空时，才会调度第i队列中的进程运行。

b. 多级反馈队列调度算法性能：多级反馈队列调度算法具有较好的性能，能很好地满足各种类型用户的需要。

终端型作业用户。由于终端型作业用户所提交的作业大多属于交互型作业，作业通常较小。
短批处理作业用户。对于很短的批处理型作业，开始时像终端型作业一样，如果仅在第一队列中执行一个时间片即可完成，便可获得与终端型作业一样的响应时间。对于稍长的作业，通常也只需在第二队列和第三队列各执行一个时间片即可完成，其周转时间仍然较短。
长批处理作业用户。对于长作业，它将依次在第1，2，…，n 个队列中运行，然后再按轮转方式运行，用户不必担心其作业长期得不到处理。

实时调度

前面介绍的多种算法不能很好地满足实时系统对调度的要求，因此引入了实时调度。
硬实时任务和软实时任务：硬实时任务指必须满足最后期限的限制，否则会给系统带来不可接受的破坏或者致命错误。软实时任务也有一个与之关联的最后期限，并希望能满足这个期限的要求，但这并不是强制的，即使超过了最后期限，调度和完成这个任务仍然是有意义的。

实现实时调度的条件

(1) 提供必要的信息。如就绪时间、开始截止时间和完成截止时间、处理时间、资源要求、优先级。
(2) 系统处理能力强。在实时系统中，通常都有着多个实时任务。若处理机的处理能力不够强，则有可能因处理机忙不过来而使某些实时任务不能得到及时处理，从而导致发生难以预料的后果。
(3) 采用抢占式调用机制。在含有硬实时任务的实时系统中，广泛采用抢占机制。当一个优先权更高的任务到达时，允许将当前任务暂时挂起，而令高优先权任务立即投入运行，这样便可满足该硬实时任务对截止时间的要求。但这种调度机制比较复杂。
(4) 具有快速切换机制。

常用的两种种实时调度算法

(1) 最早截止时间优先（earlist deadline first，EDF）算法
根据任务的开始截止时间来确定任务的优先级。开始截止时间愈早，其优先级愈高。
该算法既可用于抢占式调度，也可用于非抢占式调度方式中。

非抢占式调度方式用于非周期实时任务。
抢占调度方式用于周期实时任务。

(2) 最低松弛度优先（least laxity first，LLF）算法
根据任务紧急(或松弛)的程度，来确定任务的优先级。任务的紧急程度愈高，为该任务所赋予的优先级就愈高，以使之优先执行。松弛程度就是说该任务为了在给定某个时间前必须完成，至少需要在哪个时间点开始执行，因此松弛度低的任务排在队列前面。
该算法主要用于抢占调度方式中。

产生死锁的原因和必要条件

死锁(Deadlock)，是指多个进程在运行过程中因争夺资源而造成的一种僵局(DeadlyEmbrace)，当进程处于这种僵持状态时，若无外力作用，它们都将无法再向前推进。

产生死锁的原因

（1）竞争资源
当系统中供多个进程共享的资源如打印机、公用队列等，其数目不足以满足各个进程的需要时，会引起各个进程对资源的竞争而产生死锁。
（2）进程间推进顺序非法。
进程在运行过程中，请求和释放资源的顺序不当，也同样会导致产生进程死锁。如前面的wait和signal操作。
可剥夺资源和不可剥夺资源：可剥夺资源是指，某进程在获得这类资源后，该资源可以再被其他进程或系统剥夺。CPU和主存均属于可剥夺性资源。不可剥夺性资源是指，当系统把这类资源分配给某进程后，再不能强行收回，只能在进程用完后自行释放，如磁带机、打印机等。

产生死锁的必要条件

（1）互斥条件：在一段时间内某资源只由一个进程占用。如果此时还有其它进程请求该资源，则请求者只能等待，直至占有该资源的进程用毕释放。
（2）请求和保持条件：指进程已经保持了至少一个资源，但又提出了新的资源请求，而该资源又已被其它进程占有，此时请求进程阻塞，但又对自己已获得的其它资源保持不放。
（3）不剥夺条件：指进程已获得的资源，在未使用完之前，不能被剥夺，只能在使用完时由自己释放。
（4）环路等待条件：指在发生死锁时，必然存在一个进程——资源的环形链，即进程集合{P0，P1，P2，…，Pn}中的P0正在等待一个P1占用的资源； P1正在等待P2占用的资源，……，Pn正在等待已被P0占用的资源。

处理死锁的基本方法

（1）预防死锁。破坏产生死锁的四个必要条件2、3、4中的任意一个或多个（条件1是设备的固有属性决定的，应该加以保证），来预防发生死锁.
（2）避免死锁。在资源的动态分配过程中，用某种方法去防止系统进入不安全状态，从而避免发生死锁。
a. 安全状态：是指系统能按某种进程顺序(P1，P2，…，Pn)(称〈P1，P2，…，Pn〉序列为安全序列)，来为每个进程Pi分配其所需资源，直至满足每个进程对资源的最大需求，使每个进程都可顺利地完成。如果系统无法找到这样一个安全序列，则称系统处于不安全状态。
b．不安全状态转为进入死锁状态；但只要系统处于安全状态，系统便可避免进入死锁状态。
c. 安全状态序列例题：在当前时刻存在一个下次给进程分配资源的序列，使得下次分配的时候，能满足每个进程的资源需求。
d. 利用银行家算法避免死锁。

（3）检测和解除死锁。允许系统在运行过程中发生死锁。但可通过系统所设置的检测机构，及时地检测出死锁的发生，并精确地确定与死锁有关的进程和资源；然后，须将进程从死锁状态中解脱出来。常用的实施方法是撤消或挂起一些进程，以便回收一些资源，再将这些资源分配给已处于阻塞状态的进程，使之转为就绪状态，以继续运行。