操作系统基本算法

发表于 | 分类于

操作系统基本算法

调度

对于操作系统来讲，何时调度是一个问题。一般来说，分为以下几种情况。1）在创建一个新进程后需要决定运行父进程还是子进程。2）在一个进程退出时做出调度决策。3）当一个进程阻塞在I/O和信号量上或由于其他原因阻塞时，必须选择另一个进程运行。4）在一个I/O中断发生时，必须做出调度决策。如果中断来自I/O设备，而现在设备完成了工作，某些被阻塞的等待该I/O的进程就成为了可运行的就绪进程了，具体运行哪个进程取决于操作系统对调度的实现。

调度算法的分类

批处理

运行批处理作业的大型计算中心的管理者通常检查三个指标：

吞吐量、周转时间以及CPU利用率。1）吞吐量是单位时间完成的作业数量。2）周转时间是一个作业完成的平均时间。3）CPU利用率。吞吐量的优秀不代表周转时间优秀。

常用的批处理调度算法：

  • 先来先服务(FCFS): 很好理解，最先到的作业，先完成它。后来的排在后面。好处是实现起来比较容易，缺点是可能让其他进程的周转时间过长。
  • 最短作业优先(SJF): 由于在当前作业完成前，其它的作业都在等待你，因此让完成时间最短的作业先执行可以减少其他作业的等待时间。
  • 最短剩余时间优先(shortest remaining time next): 相比于SJF，这种算法表现出了抢占性，并且有着更好的周转时间。
交互式

  • 轮转调度(round robin): 轮转调度为每个进程分配了时间片，允许进程在时间片内运行。如果时间片结束，由计时器发出时钟中断，调度程序便停止进程的执行，并把它送往队尾。

    时间片轮转算法的效率和时间片关系很大：时间片大小，导致进程切换频繁，在进程切换上花费时间巨大。如果时间片过长，实时性就不能得到保证。

  • 优先级调度：为每个进程分配一个优先级，按优先级进行调度。为了放置低优先级的进程永远得不到调度，可以随着时间的推移增加等待进程的优先级。

  • 多级反馈队列：一个进程需要执行 100 个时间片，如果采用时间片轮转调度算法，那么需要交换 100 次。

    多级队列是为这种需要连续执行多个时间片的进程考虑，它设置了多个队列，每个队列时间片大小都不同，例如 1,2,4,8,..。进程在第一个队列没执行完，就会被移到下一个队列。这种方式下，之前的进程只需要交换 7 次。

    每个队列优先权也不同，最上面的优先权最高。因此只有上一个队列没有进程在排队，才能调度当前队列上的进程。

    可以将这种调度算法看成是时间片轮转调度算法和优先级调度算法的结合。

实时

实时系统要求一个请求在一个确定时间内得到相应，非为硬实时和软实时，前者必须满足绝对的截至时间，后者可以容忍一定的超时。

页面置换算法

最佳置换算法(OPT)

所选择的被换出页面是最长时间内不再被访问，通常可以保证获得最低的缺页率。是一种理论上的算法。因为无法知道一个页面多长时间不再被访问。举例：一个系统为某进程分配了三个物理块，并有如下页面引用序列：70120304230321201701.

开始运行时，先将 7, 0, 1 三个页面装入内存。当进程要访问页面 2 时，产生缺页中断，会将页面 7 换出，因为页面 7 再次被访问的时间最长。

最近最久未使用(LRU)

虽然无法知道将来要使用的页面情况，但是可以知道过去使用页面的情况。LRU 将最近最久未使用的页面换出。

为了实现 LRU，需要在内存中维护一个所有页面的链表。当一个页面被访问时，将这个页面移到链表表头。这样就能保证链表表尾的页面是最近最久未访问的。

因为每次访问都需要更新链表，因此这种方式实现的 LRU 代价很高。

最近未使用(NRU)

每个页面都有两个状态位：R 与 M，当页面被访问时设置页面的 R=1，当页面被修改时设置 M=1。其中 R 位会定时被清零。可以将页面分成以下四类：1)R=0，M=0,2)R=0，M=1,3)R=1，M=0，4)R=1，M=1

当发生缺页中断时，NRU 算法随机地从类编号最小的非空类中挑选一个页面将它换出。

NRU 优先换出已经被修改的脏页面（R=0，M=1），而不是被频繁使用的干净页面（R=1，M=0）。

第二次机会算法

FIFO 算法可能会把经常使用的页面置换出去，为了避免这一问题，对该算法做一个简单的修改：

当页面被访问 (读或写) 时设置该页面的 R 位为 1。需要替换的时候，检查最老页面的 R 位。如果 R 位是 0，那么这个页面既老又没有被使用，可以立刻置换掉；如果是 1，就将 R 位清 0，并把该页面放到链表的尾端，修改它的装入时间使它就像刚装入的一样，然后继续从链表的头部开始搜索。

img

时钟置换算法

第二次机会算法需要在链表中移动页面，降低效率。时钟算法使用环形链表将页面链接起来，再使用指针指向最老页面。

img

工作集页面置换算法

一个进程当前正在使用的页面的集合叫做工作集。如果工作集都被装入了内存，那么进程在运行到下一阶段前，不会产生很多缺页中断。如果内存太小无法容纳整个工作集，运行过程会发生大量的换入换出，这叫做颠簸。（有点类似于虚拟内存的抖动现象）不少分页系统会跟踪进程的工作集，在进程运行前预先装入工作集页面也成为预先调页。

磁盘臂调度算法

读写一个磁盘块的时间影响因素有：

  • 旋转时间（主轴转动盘面，使得磁头移动到适当的扇区上）
  • 寻道时间（制动手臂移动，使得磁头移动到适当的磁道上）
  • 实际的数据传输时间

其中寻道时间最长，磁盘调度的主要目标是使磁盘的平均寻道时间最短。

先来先服务（FCFS）

按照磁盘请求的顺序调度。

优点是公平和简单。缺点是未对寻道做任何优化，使平均寻道时间较长。

最短寻道时间优先（SSTF）

优先调度与当前磁头所在磁道距离最近的磁道。

虽然平均寻道时间比较低，但是不够公平。如果新到达的磁道请求总是比一个在等待的磁道请求近，那么在等待的磁道请求会一直等待下去，也就是出现饥饿现象。具体来说，两端的磁道请求更容易出现饥饿现象。

电梯算法（SCAN）

电梯总是保持一个方向运行，直到该方向没有请求为止，然后改变运行方向。

电梯算法（扫描算法）和电梯的运行过程类似，总是按一个方向来进行磁盘调度，直到该方向上没有未完成的磁盘请求，然后改变方向。

因为考虑了移动方向，因此所有的磁盘请求都会被满足，解决了 SSTF 的饥饿问题。