LWN：可擴展scheduler class！

關(guān)注了就能看到更多這么棒的文章哦～

The extensible scheduler class

By Jonathan Corbet
February 10, 2023
DeepL assisted translation
https://lwn.net/Articles/922405/

總是有人試圖將 BPF 引入內(nèi)核的 CPU 調(diào)度器領(lǐng)域，這只是一個時間問題。1月底，Tejun Heo 發(fā)布了一個由 30 個 patch 組成的改動的第二版，這個 patch set 是與 David Vernet、Josh Don 和 Barret Rhoden 共同編寫的，實現(xiàn)了 CPU 調(diào)度方面采用 BPF。顯然，通過將調(diào)度決策推遲到 BPF 程序就可以做一些有趣的事情，但要說服整個開發(fā)社區(qū)采用這個想法可能需要不少工作。

BPF 的核心理念是允許在運行時從用戶空間加載程序到內(nèi)核；使用 BPF 進行調(diào)度有可能會使調(diào)度行為跟現(xiàn)在的 Linux 系統(tǒng)非常不一樣。"可插拔（pluggable）" 調(diào)度器的想法并不新鮮，比如在 2004 年 Con Kolivas 對另一組注定會失敗的 patch 的討論中就出現(xiàn)了。當時，可插拔調(diào)度器（pluggable scheduler）的想法被人們強烈反對。人們認為只有把精力集中在一個調(diào)度器上，開發(fā)社區(qū)才有可能找到可以適配所有工作場景的方案，也就是不需要用亂七八糟的各種特殊用途調(diào)度器來塞到內(nèi)核里。

當然，內(nèi)核只有一個 CPU 調(diào)度器的這個想法并不十分準確；實際上是存在幾個調(diào)度器的，包括 realtime 調(diào)度器和 deadline 調(diào)度器等，應(yīng)用程序可以從中選擇。但是，幾乎 Linux 系統(tǒng)上的所有工作都采用了默認的 "完全公平調(diào)度器， completely fair scheduler" 下運行的，從嵌入式系統(tǒng)到超級計算機的各種工作負載的管理方面它的工作確實很可靠。人們總是希望有更好的性能，但是多年來幾乎沒有人提出要求建立一個可插拔的調(diào)度器機制。

那么，為什么現(xiàn)在要提出 BPF 機制呢？很明顯是預(yù)期到了會有長篇討論，這組 patch 的封面郵件中以很大的篇幅描述了這項工作背后的動機。簡而言之，主要觀點是在 BPF 中編寫調(diào)度策略的能力大大降低了試驗新的調(diào)度方法的難度。自從 completely fair scheduler 引入以來，我們的工作場景和它們所運行的系統(tǒng)都變得更復(fù)雜了。人們需要通過實驗來開發(fā)適合當前系統(tǒng)的調(diào)度算法。BPF scheduling class 就可以采用安全的方式進行實驗，甚至不需要重新啟動測試機。BPF 編寫的調(diào)度器還可以提高小眾的工作場景的性能畢竟這些工作場景可能不值得在 mainline kernel 中實現(xiàn)相關(guān)支持，而且還更容易部署到大型系統(tǒng)中。

scheduling with BPF

這個 patch set 增加了一個新的調(diào)度類（scheduling class），叫做 SCHED_EXT，可以像其他大多數(shù)調(diào)度類一樣，通過 sched_setscheduler()調(diào)用來選擇（選擇 SCHED_DEADLINE 的步驟要復(fù)雜一點）。它是一個非特權(quán)類（unprivileged class），意味著任何進程都有權(quán)限把自己放入 SCHED_EXT 中。SCHED_EXT 在優(yōu)先級堆棧中被置于 idle class（SCHED_IDLE）和 completely fair scheduler（SCHED_NORMAL）之間。這樣就確保了 SCHED_EXT 調(diào)度器方式的進程都不可能阻塞采用 SCHED_NORMAL 運行的普通 shell 會話進而強制接管系統(tǒng)。這也表明，在使用 SCHED_EXT 的系統(tǒng)上，人們實際上是希望大部分 workload 都采用該 class 來運行。

BPF 編寫的調(diào)度器對整個系統(tǒng)來說是全局的；沒有規(guī)定不同的進程組可以加載它們自己的調(diào)度器。如果沒有加載 BPF 調(diào)度器，那么任何被放入 SCHED_EXT 類中的進程將被當作 SCHED_NORMAL 類來運行。不過，一旦加載了一個 BPF 調(diào)度器，它將接管所有 SCHED_EXT 任務(wù)的責(zé)任。還有一個神奇的函數(shù)，BPF 調(diào)度器可以調(diào)用（scx_bpf_switch_all()），它將把所有運行在實時優(yōu)先級以下的進程移到 SCHED_EXT 中。

實現(xiàn)調(diào)度程序的 BPF 程序通常會管理一組調(diào)度隊列，每個隊列可能包含等待 CPU 執(zhí)行的可運行的任務(wù)。默認情況下，系統(tǒng)中每個 CPU 都有一個調(diào)度隊列，還有一個全局隊列。當一個 CPU 準備好運行一個新的任務(wù)時，調(diào)度器會從相關(guān)的調(diào)度隊列中抽出一個任務(wù)并將其交給 CPU。調(diào)度器的 BPF 端主要實現(xiàn)為一組通過操作結(jié)構(gòu)調(diào)用的回調(diào)，每個回調(diào)都會通知 BPF 代碼一個事件或一個需要做出的決定。這個列表很長；完整的列表可以在 SCHED_EXT 代碼分支的 include/sched/ext.h 中找到。這個列表包括：

• prep_enable()
  

• enable()
  第一個回調(diào)通知調(diào)度器有一個新的任務(wù)正在進入 SCHED_EXT；調(diào)度器可以在這里設(shè)置該任務(wù)相關(guān)的任何數(shù)據(jù)。prep_enable() 允許阻塞，也就可以進行內(nèi)存分配。 enable()不能阻塞，就是實際上啟用新任務(wù)的調(diào)度的動作。
  

• select_cpu()
  為一個剛剛被喚醒的任務(wù)選擇一個 CPU；它應(yīng)該返回將任務(wù)放在哪個 CPU 上的對應(yīng)的 CPU 編號。這個設(shè)計可能會在任務(wù)真正運行之前再重新檢查一下，這個 API 也會用來在調(diào)度器選擇了當前空閑的 CPU 的時候喚醒所選的 CPU。
  

• enqueue()
  將一個任務(wù)排入調(diào)度器來進行執(zhí)行。通常這個 callback 會調(diào)用 scx_bpf_dispatch()，將任務(wù)放入選定的調(diào)度隊列中，最終從那里運行。此外，該調(diào)用提供了 task 運行后應(yīng)給予它的時間片的長度。如果時間片長度是 SCX_SLICE_INF，那么當該任務(wù)運行時，CPU 將進入 tickless mode。
  

  值得注意的是，enqueue() 并不一定會把任務(wù)放到任何調(diào)度隊列中；如果任務(wù)不應(yīng)該立即運行的話，它可以暫時把這個任務(wù)放在某個地方。不過內(nèi)核會持續(xù)跟蹤它，確保沒有 task 會被遺忘掉；如果一個 task 擱置太久（默認為 30 秒，不過可以縮短這個超時時間），BPF 調(diào)度器就會被 unload 掉。
  

• dispatch()
  在 CPU 的調(diào)度隊列為空時會被調(diào)用；它應(yīng)該將任務(wù)調(diào)度到該隊列中從而保持 CPU 繁忙。如果調(diào)度隊列仍然是空的，調(diào)度器就會嘗試從全局隊列中抓取 task。
  

• update_idle()
  當 CPU 進入或離開 idle 狀態(tài)時，這個 callback 會通知調(diào)度器。
  

• runnable()
  

• running()
  

• stopping()
  

• quiescent()
  這些都是用來通知調(diào)度器一個 task 的狀態(tài)變化；當一個 task 變成 runnable 狀態(tài)、或者開始在 CPU 上運行、從 CPU 上退下來、不再 runnable 時，就會分別被調(diào)用。
  

• cpu_acquire()
  

• cpu_release()
  通知調(diào)度器這個系統(tǒng)中 CPU 的狀態(tài)。當一個 CPU 變得可供 BPF 調(diào)度器管理時，對 cpu_acquire()的調(diào)用就會通知到它。當一個 CPU 不再可用時（比如可能有一個 realtime scheduling class 的 task 占用了這個 CPU）就會通過 cpu_release()來通知。
  

還有許多其他的回調(diào)函數(shù)，用來管理 cgroup、CPU affinity、core scheduling （CPU 核心管理）等等。還有一組函數(shù)供調(diào)度器使用來影響調(diào)度決策。例如 scx_bpf_kick_cpu()可以用來搶占一個運行在指定 CPU 上的 task，并回調(diào)到調(diào)度器中挑選一個新的 task 在那里運行。

Examples

最終得到的是一個 framework，可以在 BPF 代碼中實現(xiàn)各種各樣的調(diào)度策略。為了證明這一點，這組 patch 也包括一些調(diào)度器的例子。有一個 patch 提供了一個最小的 "dummy" 調(diào)度器，對所有的 callback 都使用默認值；它還實現(xiàn)了一個基本的調(diào)度器，實現(xiàn)了五個優(yōu)先級，并展示了如何將 task 放到 BPF map 里。"雖然不是很實用，但這作為一個簡單的例子是很有用的，可以演示不同的功能"。

除此之外，還有一個 "central" 調(diào)度器，它將一個 CPU 專用于調(diào)度決策，讓所有其他的 CPU 都自由地運行 workload。后來的一個 patch 就給該調(diào)度器增加了 tickless 支持，并得出結(jié)論：

雖然 scx_example_central 本身太簡陋以至于不能作為生產(chǎn)環(huán)境中的調(diào)度器來用，但可以用同樣的方法建立一個功能更強的 central scheduler。谷歌的經(jīng)驗表明，這樣的方法對某些應(yīng)用（如 VM hosting）來說有很大的好處。

如果覺得這還不夠的話，scx_example_pair 實現(xiàn)了一種使用 control groups 的 core scheduling 功能。scx_example_userland 調(diào)度器 "在用戶空間實現(xiàn)了一個相當簡單直接的排序列表 vruntime 調(diào)度器，以證明大多數(shù)調(diào)度決策可以委托給用戶空間來做"。這組 patch 最終實現(xiàn)了 Atropos 調(diào)度器，它有一部分是用 Rust 編寫的很復(fù)雜的用戶空間的組件。封面郵件中還描述了一個 scx_example_cgfifo，但是沒有包含在這組 patch 中，因為它還是依賴一些尚未合入的 BPF rbtree 補丁。它 "為單個 workload 提供了 FIFO 策略，并為 cgroups 提供了一個扁平化的分層的 vtree"，而且顯然在 Apache 網(wǎng)絡(luò)服務(wù) benchmark 中測得了比 SCHED_NORMAL 更好的性能。

Prospects

這組 patch set 已經(jīng)是第二次發(fā)布了，到目前為止，還沒有引來大量的評論；也許是它太大了的原因。不過，Scheduler 維護者 Peter Zijlstra 對第一個版本做出過回應(yīng)，他說："我討厭這一切。Linus 在過去多次對 loadable scheduler 進行過拒絕（NAK），而這又是一個這樣的工作，并且還是基于 BPF 的，這是一個新增的缺點”。不過，他接著 review 了許多部分的 patch，這表明他可能不打算直接拒絕這項工作。

即便如此，BPF scheduler class 對于 core kernel 社區(qū)來說影響顯然很大。它增加了超過 1 萬行的核心代碼，并暴露了許多迄今為止一直被隱藏在內(nèi)核深處的調(diào)度細節(jié)。這相當于是承認通用調(diào)度器不能讓所有的 workload 都滿意；一些人可能會擔(dān)心，這將標志著為實現(xiàn)這一目標而進行的 completely fair scheduler 工作就此結(jié)束，以及在 Linux 系統(tǒng)中增加碎片化的實現(xiàn)。BPF 調(diào)度的開發(fā)者的觀點恰恰相反，自由試驗調(diào)度模型的能力反而會加速對 completely fair scheduler 的改進。

后續(xù)會如何發(fā)展還是很難預(yù)測，只能說到目前為止，這個 BPF 巨無霸已經(jīng)成功地克服了它所遇到的幾乎所有反對意見。將核心內(nèi)核功能局限在內(nèi)核本身的日子似乎就要結(jié)束了。很期待能看到這個子系統(tǒng)啟用哪些新的調(diào)度方法。

全文完
LWN 文章遵循 CC BY-SA 4.0 許可協(xié)議。

長按下面二維碼關(guān)注，關(guān)注 LWN 深度文章以及開源社區(qū)的各種新近言論～