最長作業優先 (LJF) CPU排程演算法

---

最長作業優先 (LJF) 是一種 CPU 排程演算法，它根據程序的爆發時間 (burst time) 來優先安排程序。在 LJF 中，爆發時間最長的程序優先於爆發時間較短的程序。此演算法基於非搶佔式，這意味著一旦程序啟動，它將一直執行直到完成，任何其他程序都不能搶佔它。

要實現 LJF 演算法，程序根據其爆發時間以降序排列在就緒佇列中。選擇並處理在到達該時間點之前所有程序中爆發時間最長的程序。此過程持續到所有程序都執行完畢。

LJF 的搶佔式版本，稱為最長剩餘時間優先 (LRTF)，類似但允許在新的程序到達且具有更長爆發時間時搶佔正在執行的程序。

最長作業優先的特性

以下是最長作業優先 (LJF) CPU 排程演算法的特性，特別是對於其非搶佔式版本：

• 程序根據其爆發時間優先順序排序，最長程序具有最高優先順序。

• 正在執行的程序不能被其他程序搶佔，這意味著它將一直執行直到完成其整個爆發時間。

• 如果兩個程序具有相同的爆發時間，則應用先到先服務 (FCFS) 規則，這意味著先到達的程序將先被處理。

• LJF 可以實現為搶佔式和非搶佔式排程演算法，但非搶佔式版本確保在最長作業或程序完全完成之前，任何其他程序都不能執行。

優點

• 爆發時間最長的程序具有最高優先順序，確保在最長作業或程序完全完成之前，任何其他程序都不能執行。

• 所有程序大約在同一時間完成，這在特定場景中可能是有益的。

缺點

• 對於給定的程序集，LJF 演算法可能導致較高的平均等待時間和平均週轉時間，這可能會對系統性能產生負面影響。

• 可能會出現車隊效應，這意味著短程序必須等待長程序完成，從而導致不必要的延遲。

• 短程序可能永遠無法執行，系統不斷執行較長程序，這會降低系統效率。

• LJF降低了處理速度，導致系統效率和利用率降低。

最長作業優先 CPU 排程演算法

• 按程序到達時間的升序排列程序。

• 在到達該時間點之前所有程序中，選擇具有最長爆發時間的程序。

• 執行選定的程序，直到完成其整個爆發時間。

• 檢查當前程序執行期間是否有其他程序到達。

• 如果新的程序到達，則將其爆發時間與當前程序的剩餘時間進行比較。如果新程序的爆發時間更長，則停止當前程序並執行新程序。如果新程序的爆發時間較短，則將其放入就緒佇列，並繼續執行當前程序直到完成。

• 重複步驟 2-5，直到所有程序都執行完畢。

示例

首先，讓我們根據它們的到達時間對程序進行排序：

程序	到達時間	爆發時間
P1	1	2
P2	2	5
P3	3	3
P4	4	8

現在，讓我們根據最長作業優先排程建立甘特圖：

程序	P1	P2	P4	P3
時間	3	8	16	19

注意 - 由於在給定時間間隔內沒有可用程序，因此 CPU 將在 0 到 1 個時間單位內處於空閒狀態。

解釋

• 在 t=1 時，唯一可用的程序是 P1，其爆發時間為 2。因此，首先執行 P1 2ms。

• 在 t = 3 時，即 P1 執行後，可用的程序為 P2 和 P3。正如你所看到的，P2 的爆發時間比 P3 更長。因此，選擇 P2 並執行 5ms。

• 在 t = 8 時，即 P2 執行後，可用的程序為 P3 和 P4。正如你所看到的，P4 的爆發時間比 P3 更長。因此，選擇 P4 並執行 8ms。

• 在 t=16 時，只有 P3 可用，它被執行 3ms。

• 最後，P4 再次執行剩餘的 4ms。

現在，讓我們計算每個程序的等待時間和週轉時間：

由於完成時間 (C.T) 可以直接從甘特圖中確定，並且

週轉時間 (TAT)

= (完成時間) – (到達時間)

還有等待時間 (WT)

= (週轉時間) – (爆發時間)

程序	到達時間	爆發時間	完成時間	週轉時間 週轉時間 = 完成時間 – 到達時間	等待時間 等待時間 = 週轉時間 – 爆發時間
P1	1	2	3	3-1=2	2-2=0
P2	2	5	8	8-2=6	6-5=1
P3	3	3	19	19-3=16	16-3=13
P4	4	8	16	16-4=12	12-8=4

輸出

總週轉時間 = 36 毫秒

因此，平均週轉時間 = 36/4 = 9.00 毫秒

而且，總等待時間 = 18 毫秒

因此，平均等待時間 = 18/4 = 4.5 毫秒

結論

最長作業優先 (LJF) CPU 排程演算法透過賦予爆發時間最長的程序最高優先順序來工作。但是，LJF 有一些缺點，包括潛在的高平均等待時間、車隊效應的可能性以及降低的系統效率。雖然 LJF 可以實現為搶佔式或非搶佔式，但非搶佔式版本確保在最長作業完成之前任何其他程序都不能執行。需要注意的是，LJF 可能不是最有效的排程演算法，並且可能不適用於所有情況。