最長剩餘時間優先 (LRTF) 或搶佔式最長作業優先 CPU 排程演算法

---

最長剩餘時間優先 (LRTF) 排程演算法是先來先服務 (LJF) 演算法的一種變體，作業系統使用它來排程傳入的程序。在 LRTF 中，剩餘執行時間最長的程序具有最高優先順序，並被首先排程執行。在一定的時間間隔內，例如每單位時間，系統都會檢查是否有另一個具有更長突發時間的程序到達。如果存在這樣的程序，則會在繼續執行當前程序之前將其排程執行。該演算法旨在最大限度地提高處理器的利用率並最小化程序的等待時間。

最長剩餘時間優先 (LRTF) 排程演算法的特性

• 最長剩餘時間優先 (LRTF) 是一種常用的 CPU 排程演算法，用於以系統的方式確定傳入程序的執行順序。

• LRTF 演算法採用搶佔式方法，其中 CPU 僅分配給固定的時間片，並選擇具有最大突發大小的程序進行執行。

• 具有最大突發大小的程序允許執行一個固定的時間片，之後再次進行選擇過程。

• 然而，由於其較高的平均等待時間，LRTF 不是最佳排程演算法。

• LRTF 演算法優先處理長時間執行的程序，導致較短的程序等待，從而導致平均等待時間增加。

優點

• LRTF 演算法易於實現和理解，因此廣泛應用於各種作業系統。

• 幾乎所有程序的完成時間都在最長作業完成之前。

• LRTF 演算法是無飢餓的，這意味著所有程序都能公平地獲得 CPU 資源。

缺點

• LRTF 演算法的上下文切換會佔用本來可以更有效地用於執行程序的 CPU 時間。

• 較低優先順序的程序可能必須等待 CPU 完成執行具有更大突發大小的較長程序。

• 儘管每個程序的突發時間較小，但 LRTF 演算法具有更高的平均等待時間和平均週轉時間。

最長剩餘時間優先 (LRTF) CPU 排程演算法

• 按程序的到達時間遞增順序排序。

• 選擇到達時間最早但突發時間最長的程序。

• 執行所選程序一個單位時間。

• 檢查是否有新的程序到達，如果有，則將其剩餘的突發時間與當前程序進行比較。如果新程序具有更長的剩餘突發時間，則搶佔當前程序並開始執行新程序。

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

最長剩餘時間優先 (LRTF) 示例

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

程序	到達時間	突發時間
P1	0	3
P2	1	6
P3	3	2
P4	5	3

現在，讓我們根據最長剩餘時間優先排程建立甘特圖：

解釋

• 在 t=0 時刻，唯一可用的程序是 P1，其突發時間為 3。因此，P1 開始執行。

• 在 t=1 時刻，P2 到達，其突發時間為 6，但 P1 仍然有 2 個單位的剩餘時間。但與 P1 相比，P2 具有更多單位。因此，P2 被新增到就緒佇列。

• 因此，這裡 P2 重複到 t=5，之後與 P1、P2、P3 和 P4 相比，P4 具有更多單位。因此，P4 被新增到就緒佇列。

• 在 t = 6（即 P4 執行之後），我們重複相同的過程，直到所有程序都已執行完畢。

• 在 t=14 時刻，P2 完成執行，所有程序都已完成。

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

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

週轉時間 (TAT)

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

此外，等待時間 (WT)

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

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

輸出

總週轉時間 = 36 毫秒

因此，平均週轉時間 = 44/4 = 11 毫秒

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

因此，平均等待時間 = 32/4 = 8 毫秒

結論

最長剩餘時間優先 (LRTF) 排程演算法通常由作業系統使用，以確保處理器得到有效利用並且程序不必等待太長時間。它的工作原理是優先處理剩餘完成時間最長的程序。但是，該演算法並不完美，因為較小的程序可能必須等待較大的程序完成更長時間。儘管如此，LRTF 演算法易於理解和實現，並且它通常會在最長程序完成之前完成大多數程序。LRTF 演算法確保所有程序都有公平的機會使用 CPU。但是，根據系統的需求，其他排程演算法可能更適合某些系統。