操作系统中调度算法(FCFS、SJF、SPN、PSA、HRRN、SRTF, RR) 原创

LUOLEI 2020.06.23 09:53:40 阅读数：1184

操作系统中调度算法

FCFS 先来先服务(first-come first-served，FCFS)
SJF、SPN 短作业优先(short job first，SJF) , 又称短进程优先(Shortest Process Next, SPN)
PSA 优先级调度算法(priority-scheduling algorithm，PSA)
HRRN 高响应比优先调度算法(Highest Response Ratio Next，HRRN)
SRTF 最短剩余时间优先算法(shortest remaining time first, SRTF)
轮转调度算法（Round Robin, RR）

先来先服务(FCFS)和短作业优先(SJF)调度算法

1. 先来先服务(first-come first-served，FCFS)调度算法

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

2. 短作业优先(short job first，SJF)的调度算法，又称短进程优先(Shortest Process Next, SPN)

由于在实际情况中，短作业(进程)占有很大比例，为了能使它们能比长作业优先执行，而产生了短作业优先调度算法。
1) 短作业优先算法
SJF算法是以作业的长短来计算优先级，作业越短，其优先级越高。作业的长短是以作业所要求的运行时间来衡量的。SJF算法可以分别用于作业调度和进程调度。在把短作业优先调度算法用于作业调度时，它将从外存的作业后备队列中选择若干个估计运行时间最短的作业，优先将它们调入内存运行。

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

优先级调度算法和高响应比优先调度算法

3. 优先级调度算法(priority-scheduling algorithm，PSA)

我们可以这样来看作业的优先级，对于先来先服务调度算法，作业的等待时间就是作业的优先级，等待时间越长，其优先级越高。对于短作业优先调度算法，作业的长短就是作业的优先级，作业所需运行的时间越短，其优先级越高，优先将它们调入内存运行。但上述两种优先级都不能反映作业的紧迫程度。

4. 高响应比优先调度算法(Highest Response Ratio Next，HRRN)

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

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

优先权 = （等待时间 + 要求服务时间） / 要求服务时间

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

优先权Rp = （等待时间 + 要求服务时间） / 要求服务时间 = 响应时间 / 要求服务时间

5.最短剩余时间优先算法(shortest remaining time first, SRTF)

SRTF把SJF算法改为抢占式的。一个新作业进入就绪状态，如果新作业需要的CPU时间比当前正在执行的作业剩余下来还需的CPU时间短，SRTF强行赶走当前正在执行作业。称最短剩余时间优先算法
此算法不但适用于JOB调度，同样也适用于进程调度。

6. 轮转调度算法（Round Robin, RR）

1. 轮转法的基本原理
轮转（Round Robin, RR）轮转也称时间片技术(time slicing,SL),

在轮转(RR)法中，系统将所有的就绪进程按FCFS策略排成一个就绪队列。系统可设置每隔一定时间(如30 ms)便产生一次中断，去激活进程调度程序进行调度，把CPU分配给队首进程，并令其执行一个时间片。当它运行完毕后，又把处理机分配给就绪队列中新的队首进程，也让它执行一个时间片。这样，就可以保证就绪队列中的所有进程在确定的时间段内，都能获得一个时间片的处理机时间。

2. 进程切换时机
在RR调度算法中，应在何时进行进程的切换，可分为两种情况：
① 若一个时间片尚未用完，正在运行的进程便已经完成，就立即激活调度程序，将它从就绪队列中删除，再调度就绪队列中队首的进程运行，并启动一个新的时间片。
② 在一个时间片用完时，计时器中断处理程序被激活。如果进程尚未运行完毕，调度程序将把它送往就绪队列的末尾。

3. 时间片大小的确定
在轮转算法中，时间片的大小对系统性能有很大的影响。

图3-2示出了时间片大小对响应时间的影响，其中图(a)是时间片略大于典型交互的时间，而图(b)是时间片小于典型交互的时间。图3-3示出了时间片分别为q = 1和q = 4时对平均周转时间的影响。

图3-2 时间片大小对响应时间的影响