操作系统中几种最最最常见的调度算法（适用于软件设计师考试与期末考试复习）

admin 管理员组

文章数量: 887017

号外号外，我最近发现了一个非常棒的人工智能学习网站，它的内容通俗易懂，风趣幽默，让人印象深刻。我想和大家分享这个网站，点击链接即可访问。 

目录

一、页面置换算法

1、先进先出置换算法（FIFO）

2、最近最少未使用置换算法（LRU）

3、最佳置换算法（OPT）

二、磁盘调度算法

1、先来先服务（FCFS）

2、最短寻道时间优先（SSTF）

3、扫描算法（SCAN）

4、循环扫描算法（C - SCAN）

三、进程调度算法

1、先来先服务(FCFS)

2、短作业优先(SIF)

 3、轮转法(Round Robin)

4、优先级算法(Priority Scheduling)

一、页面置换算法

在页面置换算法中分别有：先进先出置换算法（First In first Out，FIFO)、最近最少未使用置换算法（Least Recently Used，LRU）、最佳置换算法（OPtimal Replacement Algrithm，OPT）。

1、先进先出置换算法（FIFO）

先进先出置换算法我们可以理解为排队准则（谁先来，谁就先运行）先来先到原则。该算法总是淘汰最先进入主页的页面，即选择在主存中驻留时间最久的页面淘汰。该算法简单，只要把一个进程调入主存的页面，然后按照先后链接一个队列，并设置一个指针即可。它是一个最直观、性能最差的算法，会有 Belady 现象（是指一个进程未分配它所要求的全部页面，有时就会出现分配的页面数增多但缺页率反而提高的异常现象）。

现在来看看先进先出置换算法的例题吧

假定系统中某进程访问页面的顺序为 “0，7， 6， 5，7，4，7，3，5，4，7， 4，5，6，5” 利用FIFO 算法对上例进行页面置换的结果如图所示。

在图中我们可以看出，发生了 12 次 缺页中断，缺页率为 12 / 15 =  80%。

2、最近最少未使用置换算法（LRU）

最近最少未使用置换算法可以理解为最近访问就不会淘汰，系统在每个页面设置一个访问字段，用于记录这个页面自上次被访问以来所经历的时间 T，当要淘汰一个页面时，选择 T 最大的页面。这里要注意一点，在实现时需要硬件的支持，现在我们来看看最近最少未使用置换算法的效果图吧。

同样的我们例子和上面一样（“0，7， 6， 5，7，4，7，3，5，4，7， 4，5，6，5” ），结果如图所示。

在图中我们可以看出，发生了 11 次 缺页中断，缺页率为 12 / 15 =  73.33%。 

3、最佳置换算法（OPT）

最佳置换算法又叫预言家算法，没错，你没听错，这是一种理想化的算法，即选着哪一些永不使用的，或者在内存中最长时间内不在被访问的页面的置换出去。这种方法性能最好，very very good的一个算法，但实现上难于实现。但，注意，这里要注意，该算法通常用来评价其他算法，因为这个要确认哪个页面时未来时间内不在被访问是很难得（所以才叫预言家算法），那么现在我们来看看这最佳置换算法吧。

 在图中我们可以看出，发生了 7 次 缺页中断，缺页率为 7 / 15 =  46.66%。 

二、磁盘调度算法

在磁盘调度算法中分别有：先来先服务（first come first service，FCFS）、最短寻道时间优先(Shortest Seek Time First, SSTF)、扫描算法（SCAN）、循环扫描算法（C - SCAN）。

1、先来先服务（FCFS）

刚刚我们在页面置换算法里讲解了先进先出置换算法（FIFO），现在来看看先来先服务（FCFS）是不是已经才到了一些呢？哈哈哈，没错，你真聪明，这个原理理解也是一样，谁先来就先轮到谁。

先来先服务的磁盘调度算法是根据进程请求访问请求磁盘的先后次序进行调度。这算法优点是实现简单，每个进程都能一次处理，不会出现某一进程长期不响应的情况。但是，这里要注意，该算法主要不足是未对寻道方法进行优化，是使得平均寻道时间比较长。

下面我们来看看具体例子

我们现在有一个磁盘请求队列，涉及的柱面号为 98、183、37、122、14、124、65、67（也是请求的顺序），磁头的初始柱面位置是 53 。

那么它的平均移动时间是 （45 + 85 + 146 + 85 + 108 + 110 + 59 + 2） = 640 / 8 = 80

注意：我们看 第一项 45 是怎样来的呢？答案（98 - 53），85是怎样来的呢？答案（183 - 98）……

2、最短寻道时间优先（SSTF）

看到这个最短，是不是联想到啥？是不是距离谁最短就访问谁？哈哈哈，没错，答对了。

最短寻道时间优先（SSTF）是指磁盘调度算法每次选择要求访问的磁道与当前磁头所在的磁道距离最近的进程，这样就可以确保每次的寻道时间最短。

缺点：是可能导致队列中某些寻道请求长时间得不到服务而发生“饥饿”现象。因为只要不断有新进程的请求到达，且其所有要访问的磁道与磁头当前所在的磁道的距离较近,这种新进程的磁盘请求必然被优先满足。

那么来看看效果图吧

那么它的平均移动时间只有 208 / 8 = 26

3、扫描算法（SCAN）

扫描算法又叫电梯算法（电梯大家都坐过吧？电梯是怎么运行的呢？假如楼层有 18 层，你现在在 7 楼，现在，电梯在往上升，有人按了，9楼，11楼，6楼，3楼。那么电梯是不是先到9楼，然后再到 11 楼，最后判断一下，唉？上面还有人按吗？没有的话就下去咯~，好，没人，电梯改为下降状态，先到 6 楼，再到 3 楼。）这看懂了吗？所以我们的扫描算法，就是这样的。

扫描算法不仅考虑欲访问的磁道与当前磁道间的距离,更优先考虑磁头当前的移动方向。该算法是将磁头从磁盘的一端开始向另一端移动 ，沿途响应访问请求，直至到达了磁盘的另一端，此时磁头反向移动并继续响应服务请求，所以叫电梯算法。该算法能有效地避免“饥饿”现象。

但缺点是不利于远离磁头一端的访问请求。

我们来看看效果图吧

那么它的平均移动时间只有 222 / 8 = 27.75

4、循环扫描算法（C - SCAN）

SCAN 算法既能获得较好的寻道性能又能防止“饥饿”现象,因此被广泛用于磁盘调度中。但是 SCAN 算法中当磁头移动越过请求位置之后又有新进程加人请求该位置的队列中,进程必须等待，导致该进程的请求被延迟。为了减少这种延迟,可以采用循环扫描算法(C - SCAN)。

我们来看看效果图吧（这里用线性的不太好表示，所以我这里用了园状来表示）

这里从 53 开始，顺时针访问各个时间（53 -> 65 -> 67 -> 98 -> 122 -> 124 -> 183 -> 199 -> 0 -> 14 -> 37）

 那么它的平均移动时间有 382 / 8 = 47.75

三、进程调度算法

在进程调度算法常见的算法有：先来先服务(FirstComeFirstServed，FCFS)、短作业优先(Shortest Job First, SIF)、轮转法(Round Robin)、优先级算法(Priority Scheduling)

1、先来先服务(FCFS)

看到这不用我做过多的解释了吧？哈哈哈，和上面的一样谁先来就先执行谁。

先来先服务即按作业到来或进程变为就绪状态的先后次序分派处理机，属于非抢占方式，当前作业或进程直到执行完或阻塞,才出让处理机，它是最简单的调度算法,但算法性能很差，比较有利于长作业，而不利于短作业;有利于处理机繁忙的作业，而不利于I/O繁忙的作业。FCFS算法现已很少做主要的调度策略，常被结合在其他的调度策略中使用。

我们直接来看效果图

遵循谁先来谁就执行，那么执行顺序是 1 -> 2 -> 3。

作业 1 的周转时间是 21（0 + 21） ;作业 2 的周转时间是 27 （0 + 21 + 6）;作业3的周转时间是 33 （0 + 21 + 6 + 6）;平均周转时间是(21 + 27 + 33) / 3 = 27。

2、短作业优先(SIF)

和上面一样谁最短就先执行谁。

短作业优先(SIF)又称为“短进程优先" (SPN);这是对FCFS算法的改进,其目的是减少平均周转时间。作业的长短是指作业要求运行时间的多少。SJF 算法从后备队列中选择估计运行时间最短的作业，把处理机分给它。短进程优先是从就绪队列中选择估计运行时间最短的进程,将处理机分配给它,使之执行直到完成或因发生某事件而阻塞放弃处理机时,再重新调度。

我们来看看效果图

遵循谁执行的时间短谁就执行，那么执行顺序是 2 -> 3 -> 1。

注意：这里有个小知识，当它们的时间都一样时，遵循先来先服务，比如这里2、3 执行时间都一样，但 2 先来，所以先执行2，在执行3。

平均周转时间是（6 + 12 + 33）/ 3 = 17。

 3、轮转法(Round Robin)

轮转法(Round Robin)主要是为分时系统设计的，是种剥夺式的进程调度法。 将处理机的时间分成固定大小的时间片,不能取得过大或者过小,通常为10~100ms数量级。处理机调度程序按照FCFS原则,轮流地把处理机分给就绪队列中的每个进程,时间长度都是一个时间片。 在一个时间片结束时，发生时钟中断:调度程序据此暂停当前进程的执行,将其送到就绪队列的末尾,并通过上下文切换执行当前的队首进程。时间片的长度可以从几毫秒到几百毫秒，选择方法一般有以下两种。

（1）固定时间片：分配给每个进程相同的时间片，是所有的进程都公平执行，它是一种简单有效的方法（通俗易懂）。

（2）可变时间片：根据进程不同的要求对时间片的大小实时修改，可以更好地提高效率。

4、优先级算法(Priority Scheduling)

优先级算法(Priority Scheduling)：是目前操作系统广泛采用的一种进程调度算法，系统按一定规则赋予每个进程-个调度优先级，把处理机分配给就绪队列中具有最高优先级的进程。优先级算法平衡各进程对响应时间的要求,适用于作业调度和进程调度,可分成抢先式和非抢先式。
这种调度算法的关键在于如何确定进程的优先级、一个进程的优先级确定之后是固定的，还是随着该进程运行情况的变化而变化。

（1）静态优先级：进程的优先级在创建时确定，直到进程终止都不会改变。通常根据以下因素确定优先级:进程类型(如系统进程优先级较高)、对资源的需求(如对CPU和内存需求较少的进程优先级较高)、用户要求(如紧迫程度和付费多少)。

（2）动态优先级：在创建进程时赋予一个优先级，在进程运行过程中还可以改变，以便获得更好的调度性能。例如，在就绪队列中，随着等待时间增长，优先级将提高。这样，对于优先级较低的进程在等待足够的时间后，其优先级提高到可被调度执行。进程每执行一个时间片，就降低其优先级，从而当一个进程持续执行时， 其优先级会降低到让出CPU。

本文标签： 适用于 几种 最常见 算法 期末考试