20140523 ＣＰＵ排程

CPU排程的演算法


先來先做 (First-Come，First-Served，簡稱FCFS)
最短的工作先做 (Shortest Job First，簡稱SJF)
循環分配 (Round Robin，簡稱RR)
優先權

FCFS演算法

以行程到達的先後順序來執行，先來的先做

行程　所需時間單位
　P1　　　40
　P2　　　75
　P3　　　20
　P4　　　80
　P5　　　25

平均的回復時間 = (40 + 115 + 135 + 215 + 240) / 5，等於149

SJF演算法
所有行程所需執行時間從小排到大，由時間最短的開始執行

行程　所需時間單位
　P1　　　40
　P2　　　75
　P3　　　20
　P4　　　80
　P5　　　25 

執行順序：P3、P5、P1、P2 、 P4 

平均的回復時間 = (20 + 45 + 85 + 160 + 240) / 5，等於110



RR演算法
事先定義固定的時間配額，每個行程輪流分配。
若是無法執行完成，則下一次就再分配一次

行程　所需時間單位
　P1　　　40
　P2　　　75
　P3　　　20
　P4　　　80
　P5　　　25 

平均回復時間 = (60 + 120 + 165 + 220 + 240) / 5，等於161

優先權演算法

依事先決定的優先權定義，計算優先順序，照著優先順序的先後給予CPU使用權

行程　所需時間單位　優先順序
　P1　　　40 　　　　　3
　P2　　　75 　　　　　1
　P3　　　20 　　　　　4
　P4　　　80 　　　　　5
　P5　　　25 　　　　　2

執行順序：P2、P5、P1、P3 、 P4

平均的回復時間 = (75 + 100 + 140 + 160 + 240) / 5，等於143