作業系統 - 彩票程序排程

在多道程式設計環境中，CPU排程演算法是決定就緒佇列中哪個程序應該接下來執行的策略。與試圖最佳化週轉時間或等待時間的傳統排程演算法不同，彩票程序排程旨在為每個程序提供一定比例的CPU時間。

什麼是彩票程序排程？

彩票程序排程遵循機率排程方法。排程程式將彩票分配給系統中的程序，這些程序透過彩票分配CPU時間。彩票可能不會均勻分配。如果一個程序擁有更多彩票，它就有相對較高的選擇機率。因此，擁有更多彩票的程序具有更高的優先順序。為了使所有程序都具有相同的優先順序，排程程式會向它們分配相同數量的彩票。

這種排程也稱為比例共享排程和公平共享排程。

彩票程序排程具有以下實現步驟：

彩票分配 - 最初，系統中的每個程序都被分配一些數量的彩票。每張彩票都有一個唯一的號碼，並且系統中分配的彩票總數始終相同。
抽獎 - 排程程式透過抽取一張隨機彩票進行抽獎。通常，使用隨機數生成器在系統中分配的所有彩票號碼中生成一個彩票號碼。
排程和執行 - 擁有中獎彩票號碼的程序將在下一個時間段內被選中執行。所選程序要麼執行到完成，要麼執行到時間段結束，以較小者為準。如果沒有程序擁有中獎彩票，則再次進行抽獎。
彩票調整 - 所有被分配彩票的程序都執行完成之後，排程程式結束當前執行。如果新的程序進入系統，排程程式將從頭開始重新啟動整個過程。

彩票通常根據每個程序的優先順序進行操作。高優先順序程序分配的彩票比低優先順序程序多，從而增加了它們被選中執行的機會。但是，在彩票排程中操作彩票有幾種不同的方法：

在這種方法中，分配給每個程序的彩票數量是固定的，並且不會隨著時間的推移而改變。例如，高優先順序程序可能會被分配100張彩票。另一方面，低優先順序程序可能只被分配10張彩票。這種方法易於實現，但可能不會導致最有效或最公平的資源分配。

在這種方法中，分配給每個程序的彩票總數可能會隨著時間的推移而根據系統的行為而波動。例如，如果一個高優先順序程序正在佔用資源並使其他程序處於飢餓狀態，則可以減少其彩票數量，以使其他程序有更大的機會被選中。儘管此方法具有更高的計算開銷，但它可能導致更有效和更公平的資源分配。

在這種方法中，分配給每個程序的彩票總數由優先順序以外的其他因素決定。其他因素，包括它已經消耗的處理能力數量，也起作用。即使具有相同的優先順序，已經消耗大量處理能力的程序分配的彩票數量可能少於使用很少CPU時間的程序。這種方法可能難以實現，但可以幫助防止程序獨佔資源。

讓我們考慮一個有三個程序P0、P1和P2的情況，排程程式已向它們分配了總共100張彩票，如下表的前兩列所示：

程序	彩票號碼	彩票比例 $\mathrm{= \: \frac{分配的彩票數}{彩票總數} \: \times \: 100}$
P0	0-10, 41-50	20/100 = 20%
P1	11-40	30/100 = 30%
P2	51-60	50/100 = 50%

程序

彩票號碼

彩票比例

$\mathrm{= \: \frac{分配的彩票數}{彩票總數} \: \times \: 100}$

0-10, 41-50

20/100 = 20%

11-40

30/100 = 30%

51-60

50/100 = 50%

在第三列中，我們計算了分配給每個程序的彩票比例。

假設彩票排程程式為前25次抽獎生成以下彩票號碼：

12, 34, 78, 55, 01, 23, 44, 54, 64, 94, 29, 89, 05, 36, 76, 62, 22, 32, 42, 51, 73, 85, 18, 81, 25

生成的排程將是：

P0、P1、P2、P2、P0、P1、P0、P2、P2、P2、P1、P2、P0、P1、P2、P2、P1、P1、P0、P2、P2、P2、P1、P2、P1

程序的比例份額計算如下：

$$\mathrm{PX的比例份額 \: = \: \frac{PX的中獎次數}{抽獎總數} \: \times \: 100}$$

使用此公式，我們得到每個程序的比例份額如下：

$$\mathrm{P0的比例份額 \: = \: \frac{5}{25} \: \times \: 100 \: = \: 20 \%}$$

$$\mathrm{P1的比例份額 \: = \: \frac{8}{25} \: \times \: 100 \: = \: 32 \%}$$

$$\mathrm{P2的比例份額 \: = \: \frac{12}{25} \: \times \: 100 \: = \: 48 \%}$$

我們可以觀察到，程序的CPU時間比例份額非常接近分配給它們的彩票比例。隨著抽獎次數的增加，這些值會接近完美。

列印頁面