处理机调度基本概念

在处理机调度上可以分为三个层次，级别从低到高

• 哪些资源分给CPU（低）
• 选择哪些进程到外存中（中）
• 哪些作业放入内存（高）

处理机的调度实际上就是用不同的算法来将我们的作业合理分配，提高CPU的利用率。达到公平性、平衡性。

先来先服务算法FCFS

按照作业提交或进程变为就绪状态的先后次序,分派CPU；

当前作业或进程占用CPU，直到执行完或阻塞，才出让CPU(非抢占方式)。

在作业或进程唤醒后(如I/O完成)，并不立即恢复执行，通常等到当前作业或进程出让CPU。是最简单的算法。

谁先来，就谁先执行

短进程/作业优先算法SJF

短进程优先调度算法(Shortest Process First, SPF)，是指对短进程优先的算法。利用该算法，可以从就绪队列中选择一个估计运行时间最短的进程，并为之分配CPU，使其立即执行直到完成，或者在运行期间由于发生IO事件使该进程阻塞，并让出CPU，重新发生进程调度。

短作业优先调度算法SJF(Shortest Job First)，是指对短作业优先调度的算法。利用该算法，可以从后备队列中选择若干估计运行最短的作业，投入内存运行

谁用的时间少、就先执行谁

1)优点

• 1)比FCFS改善平均周转时间和平均带权周转时间，缩短作业的等待时间；假定所有任务同时到达，平均等待时间最短。
• 2)提高系统的吞吐量。

2)缺点

• 1)对长作业非常不利，可能长时间得不到执行；长作业可能被饿死。
• 2)未能依据作业的紧迫程度来划分执行的优先级。
• 3)难以准确估计作业(进程)的执行时间，从而影响调度性能。

最高响应比优先算法HRN

最高响应比优先法(Highest Response_ratio Next，HRN)是对FCFS方式和SJF方式的一种综合平衡

FCFS方式只考虑每个作业的等待时间而未考虑执行时间的长短，而SJF方式只考虑执行时间而未考虑等待时间的长短。

因此，这两种调度算法在某些极端情况下会带来某些不便。

HRN调度策略同时考虑每个作业的等待时间长短和估计需要的执行时间长短，从中选出响应比最高的作业投入执行。

是SJF和FCFS的综合平衡，其公式是这样子的：

(1)优点

• 1)同时到达任务，短者优先。等待时间相等时，服务时间越短，优先级越高，符合SJF思想。
• 2)长作业随等待时间增加响应比增加。服务时间相等时，等待时间越长，优先级越高。对于长作业，只要其等待时间足够长，也能获得处理机。

(2)缺点

• 1)吞吐量降低。这种算法是介于FCFS和SJF之间的一种折中算法。由于长作业也有机会投入运行，在同一时间内处理的作业数显然要少于SJF法，从而采用HRN方式时其吞吐量将小于采用SJF法时的吞吐量。
• 2)系统开销增加。原因在于每次调度前要计算响应比。

最高优先数算法

在进程调度中，每次调度时，系统把处理机分配给就绪队列中优先数最高的进程。它又分为两种：非抢占式优先数算法和抢占式优先数算法。

• 在非抢占式优先数算法下，系统一旦把处理机分配给就绪队列中优先数最高的进程后，这个进程就会一直运行，直到完成或发生某事件使它放弃处理机，这时系统才能重新将处理机分配给就绪队列中的另一个优先数最高的进程。
• 在抢占式优先数算法下，系统先将处理机分配给就绪队列中优先数最高的进程度让它运行，但在运行的过程中，如果出现另一个优先数比它高的进程，它就要立即停止，并将处理机分配给新的高优先数进程。
• 在抢占式优先数算法下会麻烦一些。

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

轮转(Round Robin，RR)调度算法是让每个进程在就绪队列中的等待时间与享受服务的时间成正比例。该算法适用于分时系统

• 每个进程所享受的CPU处理时间都是一致的。

过程：

1)将系统中所有的就绪进程按照FCFS原则，排成一个队列。

2)每次调度时将CPU分派给队首进程，让其执行一个时间片。时间片的长度从几个ms到几百ms。

3)在一个时间片结束时，发生时钟中断。

4)调度程序据此暂停当前进程的执行，将其送到就绪队列的末尾，并通过上下文切换执行当前的队首进程。

5)进程可以未使用完一个时间片，就出让CPU，如进程阻塞时。

最短剩余时间优先算法

最短剩余时间优先(Shortest Remaining Time Next，SRTN)调度算法多用于剥夺式的调度中。

在进程调度中，每次调度时，系统把处理机分配给就绪队列中运行完所需时间最短的进程。

最短剩余时间优先算法也可用于不剥夺式调度方式中，此时退化为短作业优先算法。

也就是短作业优先算法的升级版，只不过它是抢占式的。

多级反馈排队算法

• 1)设置多个就绪队列，分别赋予不同的优先级，如逐级降低，队列1的优先级最高。每个队列执行时间片的长度也不同，规定优先级越低则时间片越长，如逐级加倍。
• 2)新进程进入内存后，先投入队列1的末尾，按FCFS算法调度；若按队列1一个时间片未能执行完，则降低投入到队列2的末尾，同样按FCFS算法调度；如此下去，降低到最后的队列，则按“时间片轮转”算法调度直到完成。
• 3)仅当较高优先级的队列为空，才调度较低优先级的队列中的进程执行。如果进程执行时有新进程进入较高优先级的队列，则抢先执行新进程，并把被抢先的进程投入原队列的末尾。

选择调度方式和调度算法的准则