搶佔式優先順序CPU排程演算法

---

在計算機作業系統中佔據主導地位，CPU排程演算法是一種廣泛用於程序排程的機制。其目的是確保最重要的程序優先訪問CPU，從而最大限度地提高系統響應能力和效率。

在搶佔式優先順序排程中，每個程序都分配一個優先順序值，該值通常由當前作業的性質和重要性決定。當一個更高優先順序的程序就緒時，當前正在執行的程序會被搶佔，更高優先順序的程序取而代之。優先順序最高的程序首先獲得CPU的訪問權。

此演算法確保重要且時間敏感的程序能夠快速有效地執行，而低優先順序程序可能需要等待直到高優先順序程序完成。在即時系統中，當響應能力和及時性至關重要時，它是一種常用的演算法。

搶佔式優先順序排程演算法

搶佔式優先順序排程是一種CPU排程機制，根據作業的重要性為每個程序分配優先順序等級。優先順序越高，作業完成速度越快。

• 該演算法選擇優先順序最高的程序並執行它，直到它完成或被更高優先順序的程序中斷。

• 在這個過程中，如果到達一個更高優先順序的程序，CPU會中斷當前正在執行的程序並執行新的程序。這種中斷當前程序的過程稱為搶佔。

• 在即時系統中，當關鍵任務延遲完成可能產生災難性後果時，搶佔式優先順序排程確保高優先順序任務優先執行。

然而，這種方法的一個缺點是低優先順序作業可能會餓死。如果有很多高優先順序任務佔用所有可用時間，低優先順序作業可能會無限期等待。

• 一些搶佔式優先順序排程方法使用“老化”來解決這個問題。等待在就緒佇列中的程序的優先順序隨著等待時間的增加而提高，最終獲得執行的機會。

• 作為一種排程方法，搶佔式優先順序排程在某些作業比其他作業更重要的系統中非常有用。但是，必須謹慎使用它，以防止低優先順序作業餓死。

優先順序等級

在計算機系統中，任務執行的順序由它們的優先順序等級決定。任務的優先順序等級通常由任務的重要性、緊急程度和資源需求來定義。優先順序等級較高的任務通常先完成，而優先順序等級較低的任務只有在沒有等待完成的更高優先順序任務時才完成。

在搶佔式優先順序排程中，任務根據其相關性被分配優先順序等級。高優先順序任務優先執行，低優先順序任務只有在沒有需要完成的高優先順序任務時才執行。優先順序等級通常用整數表示，數值越高表示優先順序越高。

實現

搶佔式優先順序排程的實現方式多種多樣，這取決於使用的硬體和作業系統。搶佔式優先順序排程的實現通常包含以下步驟：

根據重要性分配任務優先順序等級：為每個任務分配一個優先順序等級。

優先執行最高優先順序任務：排程程式首先執行優先順序等級最高的作業。如果有多個作業具有相同的最高優先順序等級，排程程式可以使用不同的排程策略來做出決策。

中斷低優先順序任務：當更高優先順序的任務就緒時，排程程式會中斷低優先順序任務並執行高優先順序任務。

更改任務優先順序等級：可以根據任務的重要性或資源需求動態調整任務優先順序等級。

示例1

考慮以下程序：

程序	到達時間	突發時間	優先順序
P1	0	4	2
P2	1	3	1
P3	2	1	3
P4	3	5	4

假設這些程序使用搶佔式優先順序CPU排程演算法進行排程。

在排程這些程序之前，我們需要按照優先順序順序排列它們，從優先順序最高的開始：

程序	到達時間	突發時間	優先順序
P1	1	3	1
P2	0	4	2
P3	2	1	3
P4	3	5	4

我們可以看到，P2首先被分配CPU，因為它具有最高的優先順序。一旦P2運行了一個單位時間，CPU將轉到P1，它具有下一個最高的優先順序。儘管P1將在1個單位時間後完成，但P2將繼續執行，因為它還有2個單位的突發時間剩餘，少於P1的4個單位。

P2完成後，CPU將被交給P1。P1運行了三個單位時間後，P3將獲得CPU，它具有下一個最高的優先順序。但是，P1將繼續執行直到完成，因為它在3個單位時間後仍然有1個單位的突發時間剩餘，少於P3的1個單位突發時間。

P1完成後，CPU將傳遞給P3。P3運行了一個單位時間後，P4將被分配CPU，它是剩餘程序中優先順序最高的，然後P4將繼續執行直到完成。

甘特圖可以繪製如下：

時間	0	1	2	3	4	5	6	7	8	9
程序	P2	P2	P2	P1	P1	P1	P4	P4	P4	P4

這些程序的平均等待時間為(0+3+1+6)/4 = 2.5。

示例2

考慮以下程序：

程序	到達時間	突發時間	優先順序
P1	0	7	3
P2	1	5	2
P3	2	2	1
P4	3	4	4

假設這些程序使用搶佔式優先順序CPU排程演算法進行排程。

在排程這些程序之前，我們需要按照優先順序順序排列它們，從優先順序最高的開始：

程序	到達時間	突發時間	優先順序
P3	2	2	1
P2	1	5	2
P1	0	7	3
P4	3	4	4

我們可以看到，P3首先被分配CPU，因為它具有最高的優先順序。一旦P3運行了2個單位時間，CPU將轉到P2，它具有第二高的優先順序。但是，P3將在2個單位時間後完成，而P2將繼續執行直到完成，因為它在2個單位時間後還有0個單位的突發時間剩餘，少於P2的5個單位突發時間。

P2完成後，CPU將被分配給P1，它具有下一個最高的優先順序。P1將繼續執行直到完成。此時，P4將獲得CPU並執行程式直到完成。

甘特圖可以繪製如下：

時間	程序
0	P3
1	P3
2	P2
3	P2
4	P2
5	P2
6	P2
7	P1
8	P1
9	P1
10	P1
11	P1
12	P1
13	P4
14	P4
15	P4
16	P4

這些程序的平均等待時間為(6+3+0+5)/4 = 3.5

與其他排程演算法的比較

與傳統的排程演算法相比，搶佔式優先順序排程允許更高優先順序等級的作業中斷低優先順序等級的程序。此功能確保在需要及時完成某些作業的系統中，高優先順序任務優先執行。

其他排程演算法，如輪詢排程和先到先服務排程，不考慮任務的優先順序。輪詢排程為每個作業執行一定的時間段，而不管作業的重要性如何。先到先服務排程按到達順序執行作業，而不管其重要性如何。

結論

任務優先順序是作業系統的一個重要方面，尤其是在多工系統中，多個任務同時執行。作業系統使用稱為搶佔式優先順序排程的排程方法來根據重要性對任務進行排序。在此方法中，每個作業都分配一個優先順序級別，排程程式從具有最高級別的任務開始。

與傳統的排程演算法相比，搶佔式優先順序排程允許更高優先順序等級的作業中斷低優先順序等級的程序。此功能確保在需要及時完成某些作業的系統中，高優先順序任務優先執行。

許多現實世界的應用程式，包括即時系統、多媒體系統和作業系統核心，都使用搶佔式優先順序排程來確保任務按時完成。透過使用搶佔式優先順序排程，這些系統可以確保高優先順序級別的作業優先完成，從而使系統能夠高效有效地執行。