处理机调度

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

对于大型系统运行时的性能，如系统吞吐量、资源利用率、作业周转时间或响应的及时性等，在很大程度上都取决于处理机调度性能的好坏。因而，处理机调度便成为OS中至关重要的部分。

调度的层次

在多道程序系统中，调度的实质是一种资源分配，处理机调度是对处理机资源进行分配。处理机调度算法是指根据处理机分配策略所规定的处理机分配算法。

在多道批处理系统中，一个作业从提交到获得处理机执行，直至作业运行完毕，可能需要经历多级处理机调度，下面先来了解处理机调度的层次。

高级调度

高级调度又称长程调度或作业调度，它的调度对象是作业。其主要功能是根据某种算法，决定将外存上处于后备队列中的哪几个作业调入内存，为它们创建进程、分配必要的资源，并将它们放入就绪队列。

高级调度主要用于多道批处理系统中，而在分时和实时系统中不设置高级调度。

低级调度

低级调度又称为进程调度或短程调度，它的调度对象是进程（或内核级线程）。其主要功能是根据某种算法，决定就绪队列中的哪个进程应获得处理机，并由分派程序将处理机分配给被选中的进程。

进程调度是最基本的一种调度，在多道批处理、分时和实时三种类型的OS中，都必须配置这级调度。

中级调度

中级调度又称为内存调度。引入中级调度的主要目的是，提高内存的利用率和系统的吞吐量。为此，应把那些暂时不能运行的进程，调至外存等待，此时进程的状态称为就绪驻外存状态（或挂起状态）。当它们已具备运行条件且内存又稍有空闲时，由中级调度来决定，把外存上的那些已具备运行条件的就绪进程再重新调入内存，并修改其状态为就绪状态，挂在就绪队列上等待。

中级调度实际上就是存储器管理中的对换功能（swap），

调度的算法

先来先服务

FCFS（first-come first-served，FCFS，先来先服务调度算法）是最简单的调度算法，该算法既可用于作业调度，也可用于进程调度。

当在作业调度中采用 FCFS 调度算法时，系统将按照作业到达的先后次序来进行调度，或者说它是优先考虑在系统中等待时间最长的作业，而不管该作业所需执行时间的长短，从作业的后备队列中选择几个最先进入该队列的作业，将它们调入内存，为它们分配资源和创建进程。然后把它放入就绪队列。

当在进程调度中采用 FCFS 调度算法时，每次调度是从就绪的进程队列中选择一个最先进入该队列的进程，为之分配处理机，使之投入运行。该进程一直运行到完成或发生某事件而阻塞后，进程调度程序才将处理机分配给其它进程。

FCFS 调度算法在单处理机系统中已很少作为主调度算法，但经常把它与其它调度算法相结合使用，形成一种更为有效的调度算法。例如，可以在系统中按进程的优先级设置多个队列，每个优先级一个队列，其中每一个队列的调度都基于 FCFS 调度算法。

短作业优先

由于在实际情况中，短作业（进程）占有很大比例，为了使它们能比长作业优先执行，而产生了短作业优先调度算法（short job first，SJF）。

SJF 调度算法是以作业的长短来计算优先级，作业越短，其优先级越高。作业的长短是以作业所要求的运行时间来衡量的。

SJF 调度算法可以分别用于作业调度和进程调度。在把 SJF 调度算法用于作业调度时，系统将从外存的作业后备队列中选择若干个估计运行时间最短的作业，优先将它们调入内存运行。

SJF 调度算法较之 FCFS 调度算法有了明显的改进，但 SJF 调度算法仍然存在不容忽视的缺点：

• 必须预知作业的运行时间。在采用这种调度算法时，要先知道每个作业的运行时间。即使是程序员也很难准确估计作业的运行时间，如果估计过低，系统就可能按估计的时间终止作业的运行，但此时作业并未完成，故一般都会偏长估计。
• 对长作业非常不利，长作业的周转时间会明显地增长。更严重的是，该调度算法完全忽视作业的等待时间，可能使作业等待时间过长，出现饥饿现象。
• 在采用 FCFS 调度算法时，人机无法实现交互。
• SJF 调度算法完全未考虑作业的紧迫程度，故不能保证紧迫性作业能得到及时处理。

优先级调度算法

优先级调度算法（priority-scheduling algorithm，PSA）

我们可以这样来看作业的优先级：

• 对于先来先服务调度算法，作业的等待时间就是作业的优先级，等待时间越长，其优先级越高。
• 对于短作业优先调度算法，作业的长短就是作业的优先级，作业所需运行的时间越短，其优先级越高。

但上述两种优先级都不能反映作业的紧迫程度。而在优先级调度算法中，则是基于作业的紧迫程度，由外部赋予作业相

应的优先级，调度算法是根据该优先级进行调度的。这样就可以保证紧迫性作业优先运行。

优先级调度算法可以分别用于作业调度和进程调度。当把优先级调度算法用于作业调度时，系统将从外存的作业后备队列中选择若干个优先级最高的作业，优先将它们调入内存运行。

高响应比优先

高响应比优先调度算法（Highest Response Ratio Next，HRRN）

在批处理系统中，FCFS 调度算法所考虑的只是作业的等待时间，而忽视了作业的运行时间。而 SJF 调度算法正好与之相反，只考虑作业的运行时间，而忽视了作业的等待时间。高响应比优先调度算法则是既考虑了作业的等待时间，又考虑了作业运行时间的调度算法，因此既照顾了短作业，又不致使长作业的等待时间过长，从而改善了处理机调度的性能。

高响应比优先调度算法是如何实现的呢？如果我们能为每个作业引入一个动态优先级，即优先级是可以改变的，令它随等待时间延长而增加，这将使长作业的优先级在等待期间不断地增加，等到足够的时间后，必然有机会获得处理机。该优先级的变化规律可描述为：

由于等待时间与服务时间之和就是系统对该作业的响应时间，故该优先级又相当于响应比Rp。据此，优先又可表示为：

由上式可以看出：

• 如果作业的等待时间相同，则要求服务的时间愈短，其优先权愈高，因而类似于 SJF 算法，有利于短作业。
• 当要求服务的时间相同时，作业的优先权又决定于其等待时间，因而该算法又类似于 FCFS 算法。
• 对于长作业的优先级，可以随等待时间的增加而提高，当其等待时间足够长时，也可获得处理机。

因此该调度算法实现了较好的折中。当然在利用该调度算法时，每次要进行调度之前，都需要先做响应比的计算，显然会增加系统开销。

参考资料

《计算机操作系统》（第四版）3.2 作业与作业调度