如果覺得文章對你有所啟發，可以考慮用 🌟 支持 Gthulhu 專案，短期目標是集齊 300 個 🌟 藉此被 CNCF Landscape 採納 [ref]。

在前一篇文章中我們介紹了 sched_ext 的概念，而本篇文章會聚焦在 Scheduling Cycle，讓各位了解透過 struct_ops 定義的 callback functions（eBPF programs）會在哪些時間點被呼叫。

Dispatch Queue

Kernel 在 sched_ext 引入 Dispatch Queue（DSQ）的概念，我們可以藉由多個 DSQ 達到 FIFO 或是 priority queue 的運作方式：

• 預設情況下，系統會有一個 global DSQ SCX_DSQ_GLOBAL 以及每個 CPU 分別持有一個 local DSQ SCX_DSQ_LOCAL 。
• BPF Scheduler 可以利用 scx_bpf_create_dsq() 建立其他 DSQ，並且使用 scx_bpf_destroy_dsq() 銷毀它們。
• CPU 永遠從 local DSQ 取得任務來執行，其他 DSQ 之中的任務要被執行需要將該任務移動到 local DSQ。

此外，還需要注意 DSQ 有兩種 policy，分別是 priority queue 以及 FIFO：

• FIFO DSQ 僅適用 scx_bpf_dsq_insert。
• priority queue DSQ 僅適用 scx_bpf_dsq_insert_vtime。

也就是說，若 DSQ 存在 FIFO task 則無法用 scx_bpf_dsq_insert_vtime 對該 DSQ 插入新任務。反之，若 DSQ 存在 priority queue task 則無法用 scx_bpf_dsq_insert 對該 DSQ 插入新任務。
若違反以上規定，eBPF scheduler 就會被 kernel 踢出。

進入正題

介紹完 Dispatch Queue 之後，讓我們重新回到 Scheduling Cycle 上：

1. 當任務被喚醒，會進入到 select cpu 環節，這時 .select_cpu 對應的 eBPF program 會被執行。如果這個步驟選擇的 CPU 為 idle，則會將該 CPU 喚醒。此外，如果 task 有 cpu_mask，這個選擇可能會無效。
2. 選擇 target cpu 後，進入 .enqueue 環節，這時 .enqueue 對應的 eBPF program 會被執行。該環節可以選擇將任務：
   1. 呼叫 scx_bpf_dispatch() 將任務插入 global DSQ SCX_DSQ_GLOBAL 或是 CPU 的 Local DSQ SCX_DSQ_LOCAL
   2. 存入到自定義的資料結構中
   3. 將任務插入至自定義的 DSQ。
3. 當 CPU 準備好接受任務，會檢查自己持有的 Local DSQ，若有任務存在於 DSQ 將任務從 DSQ 取出並執行。若否，則檢查 Global DSQ，將任務取出並執行。
4. 如果 Local DSQ 或 Global DSQ 都沒有可以執行的任務存在，會進入 dispatch 環節，執行 .dispatch 對應的 eBPF program。dispatch eBPF program 可以透過：
   1. scx_bpf_dispatch 將指定的任務派發至任一個 DSQ
   2. 透過 scx_bpf_consume 將任務從指定的 DSQ 轉移到 local DSQ。
5. .dispatch 結束後，會再次對 local DSQ 與 global DSQ 進行檢查，若有任務存在則將其取出並執行。
6. 如果步驟 4 有派發任務，會跳入 .enqueue 環節嘗試取得任務。反之，如果前一個任務屬於 SCX task 且仍可被執行，則繼續執行該任務。最後，若前面的嘗試都失敗，則 cpu 進入 idle。

此外，kernel 的官方文件有提到：

The CPU selected by ops.select_cpu() is an optimization hint and not binding. The actual decision is made at the last step of scheduling. However, there is a small performance gain if the CPU ops.select_cpu() returns matches the CPU the task eventually runs on.

但沒有明確地指出為何會有 small performance gain，筆者猜測背後的原因是 select_cpu 通常會為 process 選擇一個當下最適合的 cpu（可能考慮 CPU Domain、Cache Domain 或是 workloads），如果最終執行 task 的 cpu 與當初選擇的不同，可能會有額外的開銷浪費 cpu 時間（如：cache miss）。

總結

到目前為止，我們已經學習了基本的 eBPF 開發技巧，以及開發 scx 排程器所需要的基本知識。
接下來我們會選擇幾個目前 scx 內建的排程器進行解說，讓大家對 scx 有更深刻的了解後，再進入 Gthulhu 的開發環節。

References

• https://docs.kernel.org/scheduler/sched-ext.html