明确先来先服务FCFS、时间片轮转RR、优先级三种常用的调度算法的实现思想，并在此基础上计算周转时间、带权周转时间、平均周转时间和平均带权周转时间。

（一）先来先服务

先来先服务（First-Come，First-Served，FCFS）方法是最简单的一种调度算法。它的实现思想就是“排队买票”的办法。对于作业调度来说，按照先来先服务法，是每次调度从后备作业队列（按进入时间先后为序）中选择队头的一个或几个作业，把它们调入内存，分配相应的资源，创建进程，然后把进程放入就绪队列。

对于进程调度算法来说，采用先来先服务法，就是每次调度从就绪队列中选择一个最先进入该队列的进程，把CPU分给它，令其投入运行。该进程一直运行下去，直至完成或者由于某些原因而阻塞，才放弃CPU。这样，当一个进程进入就绪队列时，它的PCB就链入就绪队列的末尾。每次进程调度时就把队头进程从该队列中摘下，分给它CPU，使它运行。

设有3个作业，编号为1，2，3，各作业分别对应一个进程。各作业依次到达，相差一个时间单位。图示出采用FCFS方式调度时这3个作业的执行顺序。

FCFS调度算法示意图

根据图，可算出各作业的周转时间和带权周转时间等，如表所示。

表 FCFS调度算法性能

由表可以看出，FCFS算法比较有利于长作业（进程），而不利于短作业（进程）。因为短作业运行时间很短，如果让它等待较长时间才得到服务，它的带权周转时间就会很长。

另外，FCFS调度算法对CPU繁忙型作业（指需要大量CPU时间进行计算的作业）较有利，而不利于I/O繁忙型作业（指需要频繁请求I/O的作业）。因为在执行I/O操作时，往往该作业（进程）要放弃对CPU的占有。当I/O完成后要进入就绪队列排队，可能要等待相当长一段时间，才得到较短时间的CPU服务，从而使这种作业的周转时间和带权周转时间都很大。

FCFS调度算法容易实现，但它的效率较低。

（二）时间片轮转法

时间片轮转法（Round-Robin，RR）主要用于分时系统中的进程调度。为实现轮转调度，系统把所有就绪进程按先入先出的原则排成一个队列。新来的进程加到就绪队列末尾。每当执行进程调度时，进程调度程序总是选出就绪队列的队首进程，让它在CPU上运行一个时间片的时间。

时间片是一个小的时间单位，通常为10至100毫秒数量级。当进程用完分给它的时间片后，系统的计时器发出时钟中断，调度程序便停止该进程的运行，并把它放入就绪队列的末尾；然后，把CPU分给就绪队列的队首进程，同样也让它运行一个时间片，如此往复。

例如，考虑如下4个进程A、B、C和D的执行情况。设它们依次进入就绪队列，但彼此相差时间很少，可以近似认为“同时”到达。四个进程分别需要运行12，5，3和6个时间单位。图3-6示出时间片q=1和q=4时它们运行的情况。

RR法（q=1和q=4时进程运行情况）

由图可以看出，在轮转法中，一次轮回时间内分给任何进程的CPU时间都不会大于一个时间片。如果一个进程在一个时间片内没有做完自己的事情，那么在时间片用完后，该进程就失去对CPU的控制权，被放到就绪队列的末尾。所以，一个运行较长时间的进程需要经过多次轮转才能完成。

可见，时间片的大小对轮转法的性能有很大影响。如果时间片太长，每个进程都在这段时间内运行完毕，那么时间片轮转法就退化为先来先服务算法。很显然，对用户的响应时间必然加长。如果时间片太短，CPU在进程间的切换工作就非常频繁，从而导致系统开销增加。因为在每个时间片末尾，都产生时钟中断，操作系统要处理这个中断，在把CPU分给另一个进程之前，要为“老”的进程保留全部寄存器的内容，还要为新选中的进程装配所有寄存器的值。这一工作无疑加大了系统开销。

时间片的长短通常由以下4个因素确定：

（1）系统的响应时间。在进程数目一定时，时间片的长短直接正比于系统对响应时间的要求。

（2）就绪队列进程的数目。当系统要求的响应时间一定时，时间片的大小反比于就绪队列中的进程数。

（3）进程的转换时间。若执行进程调度时的转换时间为t，时间片为q，为保证系统开销不大于某个标准，应使比值t/q不大于某一数值，如1/10。

（4）CPU运行指令速度。CPU运行速度快，则时间片可以短些；反之，则应取长些。

（三）优先级法

“急事先办”、“重要的事先办”，这是大家都熟知的办事原则。先办就是优先处理，表明急事、重要的事有最高的优先级。在操作系统中也经常使用优先级法作为作业调度和进程调度的算法。利用优先级调度算法进行进程调度时，是从就绪队列中选出优先级最高的进程，把CPU分给它使用。

在进程调度时，当前就绪队列中有最高优先级的那个进程获得CPU的使用权。以后在该进程的运行过程中，如果在就绪队列中出现优先级更高的进程时，怎么办？有两种不同的处理方式。

（1）非抢占式优先级法。这种办法就是：当前占用CPU的进程一直运行下去，直到完成任务或者因等待某事件而主动让出CPU时，系统才让另一个优先级高的进程占用CPU。

（2）抢占式优先级法。这种办法就是：当前进程在运行过程中，一旦有另一个优先级更高的进程出现在就绪队列中，进程调度程序就停止当前进程的运行，强行将CPU分给那个进程。

进程的优先级如何确定呢？一般说来，进程优先级可由系统内部定义或由外部指定。内部决定优先级是利用某些可度量的量来定义一个进程的优先级。例如，进程类型、进程对资源的需求（时间限度、需要内存大小、打开文件的数目、I/O平均工作时间与CPU平均工作时间的比值等），用它们来计算优先级。外部优先级是按操作系统以外的标准设置的，例如，使用计算机所付款的类型和总数，使用计算机的部门以及其他的外部因素。

进程的优先级是“一定终身”、还是“随机应变”？这涉及两种确定进程优先级的方式：静态方式和动态方式。

（1）静态优先级是在创建进程时就确定下来的，而且在进程的整个运行期间保持不变。往往利用上述的内部定义或外部指定的办法规定进程的静态优先级。

优先级一般用某个固定范围内的整数表示，例如0～7或0～4095中的某一个数。这种整数称作优先数。注意，优先级与优先数的对应关系因系统而异，在有些系统中优先数越大，优先级越高；而另外一些系统则恰恰相反，优先数越小，优先级越高，如UNIX/linux系统就是这样。本书采用“优先数小、优先级高”的表示方式。

静态优先级调度算法易于实现，系统开销小。但其主要问题是会出现“饥饿”现象。即某些低优先级的进程无限期地等待CPU。在负载很重的计算机系统中，如果高优先级的进程很多，形成一个稳定的进程流，就使得低优先级进程任何时候也得不到CPU。

（2）动态优先级是随着进程的推进而不断改变的。解决低优先级进程“饥饿”问题的一种办法是“论年头”。这种办法使系统中等待CPU很长时间的进程逐渐提升其优先级。例如在UNIX系统中，正在运行的用户进程随着占用CPU时间的加长，其优先数也逐渐增加（优先级降低）；而在就绪队列中的用户进程随着等待CPU时间的加长，其优先数递减（优先级渐升）。经过一段时间后，原来级别较低的进程的优先级就升上去，而正在运行进程的级别就降下来，从而实现“负反馈”作用—— 防止一个进程长期占用CPU，也避免发生“饥饿”现象。

对于作业调度同样可采用优先级法，即系统从后备作业队列中选择一批优先级相对高的作业调入内存。

设有如下一组进程，它们都在时刻0到达，依次为P1，P2，…，P5，各自的运行时间和优先数如表所示。采用优先级调度算法，这5个进程的执行顺序如图所示。可以算出，这5个进程的平均周转时间是12个时间单位。

优先级调度算法执行顺序