这个算法的强大之处在于易于理解和编程,在这个算法中,一个单链表记录了所有就绪进程。要选取一个进程运行,只要从该队列的头部移走一个进程即可;要添加一个新的作业或者阻塞一个进程,只要把这个作业或进程附加在队列的末尾即可。这是很简单的一种实现。
不过,先来先服务也是有缺点的,那就是没有优先级的关系,试想一下,如果有 100 个 I/O 进程正在排队,第 101 个是一个 CPU 密集型进程,那岂不是需要等 100 个 I/O 进程运行完毕才会等到一个 CPU 密集型进程运行,这在实际情况下根本不可能,所以需要优先级或者抢占式进程的出现来优先选择重要的进程运行。
最短作业优先批处理中,第二种调度算法是 最短作业优先(Shortest Job First),我们假设运行时间已知。例如,一家保险公司,因为每天要做类似的工作,所以人们可以相当精确地预测处理 1000 个索赔的一批作业需要多长时间。当输入队列中有若干个同等重要的作业被启动时,调度程序应使用最短优先作业算法
如上图 a 所示,这里有 4 个作业 A、B、C、D ,运行时间分别为 8、4、4、4 分钟。若按图中的次序运行,则 A 的周转时间为 8 分钟,B 为 12 分钟,C 为 16 分钟,D 为 20 分钟,平均时间内为 14 分钟。
现在考虑使用最短作业优先算法运行 4 个作业,如上图 b 所示,目前的周转时间分别为 4、8、12、20,平均为 11 分钟,可以证明最短作业优先是最优的。考虑有 4 个作业的情况,其运行时间分别为 a、b、c、d。第一个作业在时间 a 结束,第二个在时间 a + b 结束,以此类推。平均周转时间为 (4a + 3b + 2c + d) / 4 。显然 a 对平均值的影响最大,所以 a 应该是最短优先作业,其次是 b,然后是 c ,最后是 d 它就只能影响自己的周转时间了。
需要注意的是,在所有的进程都可以运行的情况下,最短作业优先的算法才是最优的。
最短剩余时间优先最短作业优先的抢占式版本被称作为 最短剩余时间优先(Shortest Remaining Time Next) 算法。使用这个算法,调度程序总是选择剩余运行时间最短的那个进程运行。当一个新作业到达时,其整个时间同当前进程的剩余时间做比较。如果新的进程比当前运行进程需要更少的时间,当前进程就被挂起,而运行新的进程。这种方式能够使短期作业获得良好的服务。
交互式系统中的调度交互式系统中在个人计算机、服务器和其他系统中都是很常用的,所以有必要来探讨一下交互式调度
轮询调度一种最古老、最简单、最公平并且最广泛使用的算法就是 轮询算法(round-robin)。每个进程都会被分配一个时间段,称为时间片(quantum),在这个时间片内允许进程运行。如果时间片结束时进程还在运行的话,则抢占一个 CPU 并将其分配给另一个进程。如果进程在时间片结束前阻塞或结束,则 CPU 立即进行切换。轮询算法比较容易实现。调度程序所做的就是维护一个可运行进程的列表,就像下图中的 a,当一个进程用完时间片后就被移到队列的末尾,就像下图的 b。
优先级调度事实情况是不是所有的进程都是优先级相等的。例如,在一所大学中的等级制度,首先是院长,然后是教授、秘书、后勤人员,最后是学生。这种将外部情况考虑在内就实现了优先级调度(priority scheduling)
它的基本思想很明确,每个进程都被赋予一个优先级,优先级高的进程优先运行。
但是也不意味着高优先级的进程能够永远一直运行下去,调度程序会在每个时钟中断期间降低当前运行进程的优先级。如果此操作导致其优先级降低到下一个最高进程的优先级以下,则会发生进程切换。或者,可以为每个进程分配允许运行的最大时间间隔。当时间间隔用完后,下一个高优先级的进程会得到运行的机会。
最短进程优先