进程调度#

工作负载假设#

为了简化问题，我们做出如下的假设：

• 每一个工作运行相同的时间
• 所有的工作同时到达
• 一旦开始每个工作保持运行到完成
• 所有的工作只是cpu进行的
• 每个工作的运行时间是已知的

调度指标#

周转时间： 任务完成时间减去任务到达系统的时间

• $T_{周转} = T_{完成} – T_{到达}$

周转时间是一个性能指标，性能和公平在调度里是矛盾的，优化性能的代价是阻止一些任务的运行，这就降低了公平。

先进先出算法（FIFO）#

特点： 简单，易于实现

例： A,B,C三个任务大概在相同时间T=0时到达系统，a需要100s，b和c只需要10s，假设a略微早一点点，那么周转时间就需要：

• $T = (100+110+120)/3 = 110s$

这是一个比较高的时间，因此fifo并不很好。

最短任务优先（SJF）#

这种情况下运行，理想情况时很快的，上述任务的周转时间只需要：

• $T = (10+20+130)/3 = 50s$

但是当任务不是同时抵达的时候，就会遇到同样的护航问题：

• $T = (100+110-10+120-10)/3 = 103.33s$

最短完成时间优先（STCF）#

和上述的算法不同，最短完成时间是一个抢占式的算法，每当有新的工作进入系统的时候，会确认谁的剩余时间最少，然后调度该工作，因此，在先运行a的时候，即便bc后加入，也会优先进行bc任务的执行，STCF是符合直觉的。