大家好！我是 Akshit Gaur。我目前正在為 Redox OS 的行程排程子系統進行現代化改造，這是一個透過 Redox Summer of Code 計畫獲得贊助的專案。

我們已經將舊的輪詢排程器替換為赤字加權輪詢排程器（Deficit Weighted Round Robin）。因此，我們終於能夠為行程上下文分配不同的優先級。在輕載運行時，您可能不會注意到任何差異，但在重載下，新的排程器效能優於舊的排程器（例如，在 Pixelcannon 3D Redox 示範中約有 150 FPS 的增益，CPU 密集型任務的每秒操作數增加約 1.5 倍，回應速度也有類似的改善（透過 schedrs 測量））。

Redox OS 目前使用簡單的輪詢排程器（RR）。

想像一下，您和幾個朋友坐在酒吧裡，今晚酒吧所有飲料免費，結果就是酒吧人手不足，調酒師的數量遠少於顧客。調酒師從左邊開始，為顧客服務，然後移動到右邊。

有些顧客喝得很慢，調酒師回來時他們可能還有一杯飲料。結果是，即使不是每個顧客每次都需要新飲料，調酒師仍必須檢查他們，這會給系統帶來效率低下。

這個系統運作得還算不錯，顧客要等一段時間，但每個人等待的時間都差不多，而且每個人都高興，或者至少同樣不高興。

不幸的是，對於這些調酒師來說，一位脾氣暴躁、自負的當地政客今天碰巧也是顧客之一。如果這些可憐的調酒師遵循他們平常的協議，並像對待其他人一樣對待這位 VIP，他會立即解僱他們，但受限於協議，他們別無選擇，只能在循環中移動，看著 VIP 勃然大怒。

在作業系統中，這位 VIP 顧客是一個高優先級的 I/O 密集型互動式行程（例如您的音訊堆疊，即使是最小的延遲都可能導致可聽見的瑕疵）。如果它在 CPU 佔用背景任務後面等待 RR佇列，系統會感覺沒有回應，使用者會因沮喪而終止許多子行程。

在酒吧的混亂之後，免費飲料的優惠結束了，但調酒師們非常喜歡給免費飲料，所以他們想出了一個解決方案！

他們設置了 3 個代幣分配器，每個分配器的速度不同，每秒分配 1、2 和 4 個代幣。形成了 3 個佇列（A、B、C），由一個保鑣將每個顧客分配到一個佇列。一杯啤酒的價格被定為兩個代幣，所以站在佇列 A 的顧客等待兩次計時後離開，而佇列 C 的顧客只需一次計時就能買兩杯啤酒。然後顧客離開佇列並「購買」啤酒！

VIP 的問題解決了！一旦 VIP 到達，保鑣就會將他引導到佇列 C，而其他兩個佇列中的所有人都被擱置一旁。

不幸的是，我們現在面臨飢餓問題，因為佇列 C 比 B 離出口更近，而 B 又比 A 更近。如果所有佇列中的人都累積了足夠的代幣並想離開，佇列 C 中的顧客總是第一個離開。這是一個問題！如果佇列 C 中有很多顧客，佇列 A 和 B 中的顧客將沒有機會購買啤酒，並會因飢餓而死亡！

赤字加權輪詢排程器（DWRR）將行程分組到多個佇列中，為每個佇列分配優先級。在每次上下文切換時，它從最高優先級的佇列開始，將其權重加到其餘額中，並從該佇列運行任務，直到其餘額低於某個基本價格，然後排程器才會移動到列表中的下一個佇列。

它正確地優先處理高優先級的行程，但可能導致低優先級行程的飢餓和更高的延遲。

為了在不犧牲 VIP 需求的情況下解決飢餓問題，我們轉向了交錯式方法。排程器不是讓一個佇列一次用完其全部餘額，而是「交錯」工作。

可以想像成調酒師為 VIP 佇列服務一輪，然後立即檢查低優先級佇列中是否有人有足夠的代幣只買一杯飲料，然後再回到 VIP 那裡。

這會導致上下文切換開銷略有增加，但延遲的好處是不可否認的。

設置好 RedoxOS 並確保其可以建置後，請查看此核心 MR，以及第一個註解中提到的所有相關 MR。

對於任何嘗試測試的人，您必須將 redox_syscall 和 libredox 函式庫的儲存庫（在相關 MR 中提供）克隆到 recipes/core 中。

您的目錄應該看起來像這樣：

我暫時為所有 MR 添加了 Cargo.toml 的補丁，在合併前會被移除。

簽出此 MR，然後運行 make rp.renice，或在重建映像檔之前將 renice = {} 添加到您的 desktop.toml 中。

您的設置現在已準備好嘗試新排程器的優點！

nice 和 renice 的用法相當明顯。

為了與不同的排程器進行比較，我建置了一個獨立的測試框架。讓我們看看他們的結果！

在 t=0 時初始化 40,000 個行程，這些行程是 CPU 密集型的且從不阻塞，它們的執行時間足夠長，以至於在我們的模擬時間範圍 100,000 個計時內無法完成，而我們的模擬 CPU 有 16 個核心。

由於這是一個非常理想化的工作流程，唯一重要的指標是平均回應時間，正如我們將進一步看到的，RR 的回應時間最低，但如前所述，我們無法為我們的任務分配不同的優先級。

回應時間是指任務開始運行所需的時間（第一次執行時間 - 到達時間）。

首先，讓我們澄清一下這些欄位 - i. Prio - 任務的優先級 ii. Theor. Weight - 其理論權重。 iii. Avg Execs/Task - 該優先級佇列中的任務平均執行了多少次（高優先級的應該更高）。 iv. Avg Wait/Task - 任務在運行佇列中等待 CPU 拾取的平均時間。（由於任務數量龐大而只有 16 個核心，因此在理想化的工作流程中幾乎相同）。 v. Avg Resp/Task - 任務從首次到達直到第一次在 CPU 上執行的時間。 vi. Samples - 該優先級佇列中的任務數量。

正如您所見，平均回應時間從 1249 上升到 34459，增加了 27 倍！但當我們查看 Avg Execs/Task 和 Avg Resp/Task 時，情況發生了變化，一個 prio 為 39 的任務的執行次數顯著增加，回應時間減少！

儘管如此，我們可以看到低優先級任務的困境和它們的飢餓現象。

平均回應時間明顯低於非交錯式，但另一方面，Avg Execs/Task 不再像 DWRR 那樣極端。任何兩個相鄰優先級之間的 Execs 差異現在相當小，尤其是在極端情況下。

正如您所見，交錯式排程器更加公平，同時仍然為我們提供了一種優先處理某些任務的方法。

這次，在每個時間步長，我們有機會為每個 CPU 核心生成最多 1 個新任務。這個新任務具有隨機的總運行時間（範圍 2..100000），並且它們有一個稱為阻塞機率的屬性（範圍 0..0.001），該屬性決定了任務在每次執行時阻塞的可能性。

再次，我們將比較平均回應時間。

正如我們再次看到的，高優先級任務的統計數據有了非常顯著的改善，而最低優先級任務的統計數據則顯著下降。

平均回應時間現在比標準 DWRR 低 11 倍，而最高優先級佇列的回應時間從 6 個計時增加到 26 個計時。Avg Execs 也確實顯示了高優先級任務的執行次數從約 7000 個計時大幅減少到約 1800 個計時。

我想我到目前為止已經說服您，交錯式 DWRR 是簡單 RR 的公平性與 DWRR 的效能（針對高優先級任務）之間的一個很好的折衷！

目前的簡單輪詢排程器在兩個 CPU 佔用的程式（在 GNU Bash 中為 while; do :; done，或在 C 中為 while (1) printf("Hello!\n");）運行時，提供約 1000 FPS。

另一方面，新的排程器在所有優先級均為 0 的情況下，也能提供約 1000 FPS，誤差範圍內。

如果我們增加 pixelcannon 的優先級（降低 nice 值），並降低兩個 CPU 佔用應用程式的優先級，pixelcannon 現在可提供約 1150 FPS！

這是我重寫的 schbench。正如預期的那樣，這是新排程器特別擅長的領域。要重現我的結果，只需運行兩個 CPU 佔用的程式，然後運行 schedrs。

雖然模擬器向我們展示了理論極限，但實際測試證明了該架構在競爭狀態下按預期工作。

通過運行兩個積極的背景 while(true) CPU 佔用程式，我們迫使系統進入高競爭狀態，從而能夠在負載下比較行為：

DWRR 排程器成功地保護了高優先級和對延遲敏感的任務，使其免受背景噪音的影響。

接下來：用完整的 EEVDF 的動態滯後計算替換靜態佇列邏輯！