作業系統FCFS排程


先來先服務(FCFS)排程演算法根據其到達時間簡單地排程作業。 就緒佇列中第一個工作將首先獲得CPU。 工作到達時間越少,工作得到的CPU就越快。 如果第一個進程的突發時間是所有作業中最長的,則FCFS排程可能會導致飢餓問題。

FCFS的優勢

  • 簡單
  • 容易
  • 先到先得

FCFS的缺點

  • 排程方法是非搶先式的,該進程將執行到完成。
  • 由於演算法的非搶先性,可能會出現飢餓問題。
  • 儘管實現起來很容易,但由於平均等待時間比其他排程演算法更高,因此效能較差。

範例

我們來看一個FCFS排程演算法的例子。 在下面的時間表中,有5個進程的進程ID為P0P1P2P3P4P0到達時間0P1在時間1P2在時間2P3到達時間3,處理P4在時間4到達就緒佇列。 下表給出了過程及其各自的到達時間和爆發時間。

周轉時間和等待時間通過使用以下公式計算。

Turn Around Time = Completion Time - Arrival Time   
    Waiting Time = Turnaround time - Burst Time

平均等待時間通過將所有過程的各個等待時間相加並且將總和除以過程的總數來確定。

進程ID 到達時間 突發時間 完成時間 轉換時間 等待時間
0 0 2 2 2 0
1 1 6 8 7 1
2 2 4 12 8 4
3 3 9 21 18 9
4 4 12 33 19 17

平均等待時間= 31/5