contributed by < vax-r > Reviewed by Vincent550102 將多個實作細節分別提交為獨立的，以便未來的追蹤與 rebase 操作更加便捷與清晰。 commit 41264c5 :::warning [name=I-HSIN Cheng] 針對您的 review ，我的回覆如下 感謝您建議要做的改進，確實是我在提交 commit 偷懶的結果，為了養成良好的習慣您提出的改動是必要。

Error Handling Rust 的錯誤大致分為兩種主要的種類， recoverable 和 unrecoverable ，對於 recoverable errors 例如找不到對應檔案，最有可能的處理方式是回報該問題並且重新嘗試該操作，對於 unrecoverable error 來說，那總是代表 bugs 的特徵，此情況會立即將程式停止。 panic! macro 實際上有兩種方式來造成 panic ，一種是做了某些造成整個程式 panic 的操作例如嘗試存取超過 array 範圍的記憶體空間，或者是我們自行呼叫 panic! macro 。 不管是哪種方式，這些 panics 都會回傳一個錯誤訊息然後 unwind ，之後清空 stack 然後結束程式。 預設來說當 panic 發生時程式會自動開始 unwind ，代表 Rust 會從尾部走回到 stack 頭部並清空所有函式當中使用的資料，但這樣的 walking 成本昂貴，因此 Rust 提供另一個機制稱為 aborting ，會直接將程式終止而不會 clean up 。 至於程式原本使用的記憶體資源則會交給作業系統來清除，如果你寫出的程式最後編譯的 binaries 非常小，則我們可以從 unwinding 改成 aborting ，透過 panic = 'abort' 在 Cargo.toml 檔案當中。

Introduction 電腦系統當中把排程任務的基本單元稱為行程，每個行程之間的記憶體位址是互相獨立且分離的，除非特定操作不然不允許行程之間互相存取，這使得行程之間的溝通或者 concurrency 的實現方法會變得昂貴。相較之下，執行緒共享相同的記憶體位址，使得同一個 thread group 底下的執行緒可以利用 shared memory 來進行溝通，實現 concurrency 變得更容易且執行上更快速。 閱讀〈Concurrency Primer〉 既然執行緒之間利用共享記憶體空間來溝通並實現 concurrency ，同步就會是非常重要的議題，重點在執行緒對共享記憶體進行寫入或存取的順序 。我們從組合語言甚至硬體架構， CPU pipeline 的角度切入試圖了解 concurrency 的各種問題與實作方式，不僅僅是將任務切分成數個細小區塊切換執行這麼單純。 在現代電腦架構當中，記憶體架構時常有很多層，多核心處理器也是非常常見的，每個核心會有自己的 store buffer ，如此一來寫入的操作不會阻塞住其他指令的執行，這裡的難點在如何讓整個系統的記憶體保持 coherent ，也就是每個核心的每個寫入動作對於其他核心而言都是可見的。你會想，指令的順序不就是我們寫程式各項指令的順序嗎？其實不然，在現代硬體架構與編譯器優化的影響下，實際程式執行的指令順序、執行哪些指令，早就不是我們閱讀原始檔就能理解的。 Atomic 在 C 語言當中引入 <stdatomic.h> 即可使用 atomic 類型的資料型態，最主要的影響是它帶來 single total modification order ，編譯器保證不會改變 atomic variable 周圍其他變數的 loads and stores 順序。整個程式的執行順序依舊可能和你想像的不同，但它保證執行後的結果會和程式碼所寫的順序相同，稱為 sequential consistency 。 但這一切是建立在執行緒之間共享的變數是 atomic 且真的具有 atomicity 的情況，什麼情況可能違反呢？試想如果兩個跑在 32-bit machine 上的執行緒之間共享一個 64-bit integer 的 counter ，則我們不可能在滿足 atomicity 條件下存取這個 counter ，因此我們也應該確保任何共享變數的大小都不該大於 CPU word size 。但如果很不巧的你的共享變數 T 大於 CPU word size ，我們可以透過補上 _Atomic 使得編譯器在 runtime 時會自動將該變數的讀取與寫入用 lock 圍繞住。

Design/Architecture eBPF 和原先的 BPF 十分相似，特別的地方在於 eBPF map ，它是一種能夠儲存多種不同資料型態的資料結構，在當中每種不同資料型態被當成不同的二進位記憶體區塊來看待，因此使用者只需要告訴 eBPF map 想儲存的 key size 和 value size 即可。 user process 可以透過 file descriptor 來使用 eBPF map 同時可以創建多個 eBPF map ，對於同一個 eBPF map 而言，也允許多個 eBPF program 對它進行平行存取。 其中有一種特別的 map type 稱為 program array ，這種形態的 map 當中儲存的 file descriptor 是指向其他的 eBPF program ，當一個 eBPF program 對此 map 進行 lookup 後，程式執行會導向另一個 eBPF program 的開端且不會再 return 到原先的 calling program ，不過不允許無限的 nested call ，頂多 32 層。所有存在 program array map 當中的 eBPF program 都需要事先透過 bpf() 系統呼叫載入 kernel 當中，若 map lookup 失敗則原先的程式會繼續執行。 eBPF program 在載入 kernel 前需要先通過 in-kernel verifier 的靜態檢測，它會判斷該程式是否會終止還有是否每個指令都是安全的。而 eBPF program 可以被附加在多種不同事件上，不管是監聽網路封包、追蹤事件、透過 network queueing disciplines 進行事件分類還是其他任務。相關事件的發生會觸發 eBPF program 的執行。 System call

:::warning Mainly for cgroups v2 ::: Overview 什麼是 cgroups 官方的定義是 cgroup 將 tasks 集合映射到子系統 (subsystem) 的集合上。 subsystem 定義是利用 cgroups 提供的 task grouping facilities 使這群 tasks 的行為被特別規範，也稱為 resource controller ，可以針對特定某個或某些 cgroup 或一群 process 做資源的限制。 cgroups 的結構可以想像成一顆樹，稱為hierarchy ，任何 task 都會剛好位在一個 cgroup 當中，還有一群 subsystem 的集合當中。所有 hierarchy 都有一個 cgroup virtual filesystem instance 。 為何需要 cgroups

Overview sched_ext kernel branch 提供給 scx 一個完整的 bpf 介面得以讓使用者利用 scx 撰寫自己的排程器，相較於將完整排程策略實作在 kernel space 當中， sched_ext 僅僅是提供一個雛形，有預設的排程策略，但實際上會利用 scx 載入的排程器。同時 EXT scheduling class 的優先權和 fair class 是相同的。 Related files /tools/sched_ext/ /tools/testing/selftests/sched_ext/ /kernel/sched/ext.c /kernel/sched/ext.h Big picture of Linux schedulers

Overview 透過更嚴謹的檢查在編譯時期就能除去許多錯誤發生的可能，讓程式在執行時期更加安全穩定，和許多程式語言不同， rust 要通過編譯就非常困難，但執行時期會發生的許多錯誤都能因此避免，是一個非常適合撰寫底層程式的程式語言。 Common Programming Concepts Vairables and Mutability Rust 當中變數預設是 immutable ，也就是一但變數初始化之後其值就不能更改，用以下的程式為例 fn main() { let x = 5; println!("The value of x is: {x}");

Introduction 在利用 sched_ext 撰寫我們的 custom scheduler 之前，先理解現有排程器如何實作，解析相關工具的使用並探討是否有改進空間。 架構分析 以 scheds/c/ 底下包含的排程器來說，不外乎是一個 userspace program 搭配一個 bpf program ，而 bpf program 又會透過 libbpf 解析行程 skeleton file ，因此使用者層級程式碼都是 include skel.h 標頭檔來和 bpf application 進行互動。以下先以架構最簡單的 scx_simple 為例。 使用者層級程式 先看到 main 函式當中，透過 libbpf API libbpf_set_print 來設定如何印出 libbpf warning 和 informational messages 。此處是設定為 libbpf_print_fn ，而 libbpf_print_fn 實作如下 static int libbpf_print_fn(enum libbpf_print_level level, const char *format, va_list args)

scx_rusty overview scx_rusty 身為 scx 專案目前收錄的一個排程器，將 CPU 分到不同 domain 當中，在 bpf program 當中實作主要的排程邏輯，而特別的是透過一個使用者層級的 load balancer 來幫助進行負載平衡，定時進行 load balance 運算並將資料透過 BPF map 更新， bpf program 進行 select_cpu 或 enqueue, dispatch 等行為時可透過讀取 BPF map 當中的資訊而得知是否改進行負載平衡。 Userspace part 使用者層級的程式透過 Rust 程式語言實作，主要負責兩個部分，第一個是提供 higher frequency tuning decision 。找出當前負載不沉重的 CPU 並將他們標記起來，使得他們可以從過載的 CPU 當中進行 task pull 。 第二個部分是運行 lower frequency load balancing ，透過比較 domain 之間的 load averages 來決定是否進行 load balancing 。如果 load difference 夠大則會檢查最多 1024 個 task 來判斷哪個 task 應該被移動（這也是我們可以優化之處）。 在使用者層級的操作成本低，而且負載平衡成本也不像過往高，進行的頻率也低，不過 work-conservation 依舊透過 tuning 和 greedy execution 來進行。

Overview scx 當中的排程器對於 load balance 部分多數沒有特別實作，除了 scx_rusty 有實作一個使用者層級的 load balancer 。我們希望可以量化來評估排程器對於負載平衡的機制是好還是壞。 CPU load unbalance CPU 排程器在任務挑選 CPU 時其實就會嘗試讓 CPU load 是平衡的，因此我們要找到適當的 workload 和場景讓 CPU load 出現不平衡，以此觸發 task migration ，在其中比較 task migration 次數，或者 migration 成本等等。 其中一個情況會是 CPU-bound load 和 I/O bound load 大量混雜的情況，由於 I/O bound 的任務要對 disk 進行讀取會導致 CPU waiting ，同時間 CPU-bound 的任務會大量使用 CPU 資源，導致 CPU load unbalance 出現。以實際案例來說有以下幾種場景可能導致上述現象發生 File server : NAS server 等會進行大量 I/O 操作的系統 Log processing : 處理系統 log 時可能在邊讀取進行 I/O 時對資料進行分析，分析是 CPU bound 的任務

Overview 利用 sched_ext 作為框架撰寫一個將所有任務全部塞給指定 CPU core 執行的排程器！參考 scx_central 與 scx_simple 。 Implementation 在初始化函式 randmigrate_init 當中只需要做兩件事，讓該排程器排程所有任務以及建立一個 FALLBACK_DSQ 。 int BPF_STRUCT_OPS_SLEEPABLE(randmigrate_init) { int ret;

Paper site 論文內容摘要 Linux 核心 採用的 Completely Fair Scheduler 所採取的排程策略是每次挑選當前 virtual runtime 最小的 sched_entity 來執行，並且盡量平衡每個 CPU 的 utilization ，但這樣的作法並未考量到不同任務之間對於硬體資源的需求不同造成競爭帶來的負擔。本論文引入機器學習模型來做到以下幾件事 模擬原先 Linux 核心 的負載平衡 機器學習模型會將硬體資源需求納入考量 針對資源用量大與高度競爭的情境來訓練 利用 Reinforcement Learning 來加強負載平衡的表現

userspace tools and scheduler implementation : scx kernel branch : sched_ext Building & Setup 若你的電腦作業系統版本是 ubuntu 22.04 ，可以先按照 sched_ext/.github/workflows/test-kernel.yml 的流程安裝試試看，由於我進行實驗的 host machine 是 ubuntu 20.04 focal 版本，許多套件上有衝突或過舊的問題，因此以下採取許多 workaround 。 首先取得原始程式碼 $ git clone git@github.com:sched-ext/sched_ext.git $ cd sched_ext

contributed by < vax-r > 自我檢查清單 [ ] 研讀〈Linux 核心設計: RCU 同步機制〉並測試相關 Linux 核心模組以理解其用法 Ans : Concurrency 筆記 : RCU [ ] 如何測試網頁伺服器的效能，針對多核處理器場景調整 [ ] 如何利用 Ftrace 找出 khttpd 核心模組的效能瓶頸，該如何設計相關實驗學習。搭配閱讀《Demystifying the Linux CPU Scheduler》第 6 章 Answer : ftrace 顧名思義是 function tracer ，追蹤函式又是怎麼達成的呢？首先搞清楚 tracing 代表的是在執行時期紀錄事件的數據，也稱為 software profiling ，在 ftrace 當中是透過 code instrumentation 。 Instrumentation 又可以分為兩種Function tracing, 利用 gcc 等編譯器在編譯時期做 code instrumentation Event tracing, 在 source code 當中利用 tracepoints 來達成

contributed by < vax-r > 自我檢查清單 [X] 實體電腦運行 GNU/Linux [X] 閱讀〈Linux 核心模組運作原理〉並對照 Linux 核心原始程式碼 (v6.1+)，解釋 insmod 後，Linux 核心模組的符號 (symbol) 如何被 Linux 核心找到 (使用 List API)、MODULE_LICENSE 巨集指定的授權條款又對核心有什麼影響 (GPL 與否對於可用的符號列表有關)，以及藉由 strace 追蹤 Linux 核心的掛載，涉及哪些些系統呼叫和子系統？ Ans : 在 Linux kernel v6.8.5 當中，巨集 MODULE_LICENSE() 在 /include/linux/module.h 定義如下​​​​#define MODULE_LICENSE(_license) MODULE_FILE MODULE_INFO(license, _license) 免費的模組標記是 GPL, GPL v2, GPL and additional rights, Dual BSD/GPL, Dual MIT/GPL, Dual MPL/GPL ，非免費的是 Proprietary 。 GPL, GPL v2 這兩個標記是授權符號都代表模組是註冊在 GPL v2 底下，有這兩個版本是由於歷史因素，主要是要讓 Proprietary 標記能使用並避免讓非免費模組使用 EXPORT_SYMBOL_GPL 已經使用的 symbol 。這些標記存在的理由有以下數個使 modinfo 可以顯示 licencse info 讓使用者確認他們使用的模組是免費的。 使開發者社群可以忽略模組顯示的錯誤回報。 在編譯完核心模組並利用 insmod 命令將核心模組載入的過程中，透過 strace 命令觀察呼叫的系統呼叫，注意到會進行 finit_module 系統呼叫，並在 idempotent_init_module 當中的 init_module_from_file 呼叫 load_module ，值得注意的是 load_module 當中的 simplify_symbols 會透過一系列操作與函式呼叫將核心模組的 symbols 給載入，當中呼叫 resolve_symbol_wait 再呼叫 resolve_symbol 再呼叫 find_symbol ，特別注意到在 find_symbol 當中有用到 List API list_for_each_entry_rcu 來設定 module 當中的為雙向鍵結串列，也可以注意到搜尋 symbol 的函式 find_exported_symbol_in_section 利用到一個特殊的搜尋方式 bsearch() ，需進一步探討實作，還有尋找 symbol 的過程有用到 mutex lock ，許多 lock 機制的使用方式或許有改進空間。並且發現 insmod 大量使用了 mmap 系統呼叫，重複的進行 openat(), read(), newfstatat(), mmap(), close() 一系列系統呼叫。

Introduction 閱讀 commit b5c56e0 提及之三篇論文並思考 merge sort 與其變形之優劣勢，並嘗試提示洞見與可能的改進。該 commit 提及的論文分別如下 Bottom-up Mergesort: A Detailed Analysis The cost distribution of queue-mergesort, optimal mergesorts, and power-of-two rules Queue-Mergesort Bottom-up Mergesort $C(N)$ 表示排序 $N$ 個元素最少需要做幾次比較，這項指標對排序演算法的效能影響最大。 Divide-and-conquer 演算法幾乎都存在週期性現象， merge sort 也不例外。該論文首先定義 $C_{b,td}(N), C_{w,td}(N), C_{a, td}(N)$ 這三個參數表示 top-down mergesort 在 best case, worst case 與 average case 所需要的比較次數。 $C_{w,td}(N)$ 還可以因為其週期性性質而歸納出以下公式 $$

contributed by < vax-r > 第三週測驗 測驗一 測驗中程式碼利用 digit-by-digit calculation 做為基礎來運算 x 的平方根。 基本原理很單純，透過 $(x + y)^2 = x^2 + 2xy + y^2$ 並隨著項次層層拆解，以下假設 $x = N^2$ ， $N$ 即是我們想求的答案，先透過二進位表示法將 $N$ 表示為 $$ N = \sum_{i=0}^n a_i $$

contributed by < vax-r > 第一週測驗題 程式碼 測驗一 :::warning 不用將參考答案列出，你應該著重在自己的觀察、疑惑討論，和相關的實驗。 [name=I-HSIN Cheng] 好的收到

Introduction 最基本的 RL 可以利用 Markov Decision Process 來描述，也就是有一個 set of states $S$ 、 a set of actions $A$ ，透過 action $a$ 從 state $s$ 轉移到 state $s'$ 的機率為 $P_a(s, s') = Pr(S_{t+1} = s' | S_t =s, A_t = a)$ ，並且定義從透過 $a$ 從 $s$ 轉移到 $s'$ 的獎勵是 $R_a(s, s')$ 。 RL 、 supervised-learning 和 unsupervised-learning 可以將機器學習方法分類為這三大類，其他 RL 特別適合用來解決一些難以做 label 並且人類不知道正確答案為何的問題。以下我們先從數學角度切入試圖理解 RL 。 Markov Decision Process Markov Property Describe the memoryless property of a stochastic process, it's future evolution is independent of its history. 描述成數學式為以下 $$ Pr(X_n = x_n | X_{n-1} = x_{n-1} , \cdots , X_0 = x_0) = Pr(X_n = x_n | X_{n-1} = x_{n-1}) $$

contributed by < vax-r > 閱讀〈因為自動飲料機而延畢的那一年〉與課程啟發 閱讀心得 作者很勇敢在學生時期選擇延畢創業，過程中遇到的問題跟心路歷程帶給我很大 的啟發。首先是解決真實世界的問題，跟在學校課程當中解決問題、考試或做實驗那是完全不同的，或許這也是現在教育的問題，不教學生真的東西，老師們自己都在自欺欺人，領域換來換去一個禮拜就可以變成深度學習專家。不過身為學生的我們沒必要把成長的機會浪費掉，這個作者在做自動飲料機的過程，從一開始發現真的要做出一台飲料機，需要的知識實在太多，從寫程式、機械、電路設計到飲料的銷售都要懂，一個人怎麼可能懂這麼多，所以他過程中找了很多不同人來幫忙，這讓我覺得社會把各種科系分貴賤的風氣有很大的問題，我們談到醫學系學生自然覺得他很聰明有能力，談到土木系學生就覺得他應該素質平庸，確實就考上對應科系的難度差非常多，但這不代表我們在解決真實問題的時候就只需要特定某些科系的學生，反之，這會使得這個社會更加不能解決問題，因為想做出某個產品，我們不可能只懂某個領域，但現在的社會好像就在倡導我們這樣做，包括我自己也是其中的信徒。 更做到後期的時候作者還談到了跟創業朋友的溝通與爭吵，還有跟許久沒聯絡的父親因為這件事再度有交集，還有一直到最後飲料機終於做出來的時候，他的內心感到的不是狂喜，而是比任何人都平靜，他比起任何人都知道這個成品背後每個零件的由來，還有各種取捨與可能存在的問題，親手做事的人永遠知道自己的作品不是完美的，往往只有外行人才會有對於某個產品是完美的這種評價。 課程心得 Linux 核心實作課程經過了五週，這堂課是我進入資工系研究所後最期待的課，我很期待從這堂課可以學到很多東西，本來就對於貢獻開源軟體有憧憬的我，一開始參加這門課的目的十分明確，讓自己具備能力貢獻 Linux Kernel 程式碼，而不是來每次測驗考 100 分。這堂課算是真的讓我感受到我有在真實的學習成長，每個作業每個問題都沒有標準答案，他們是真實世界的問題，當然還是有經過包裝避免難度太誇張，以便讓只是學生的我們有機會慢慢著手發展解決真實問題的能力。從第一份作業 la0-c 開始讓我重頭審視自己對於 C 語言的理解，真的是零，沒讀規格書怎麼會知道指標、 function specifier 存在的意義、例外用法等等，每種程式語言都有自己的特色與定位，不閱讀規格書怎麼能說自己理解該程式語言，頂多說會打字。每次課堂測驗老師都不會事先讓我們知道題目，當場問就像面試場合一樣，老師說不會也沒關係畢竟缺什麼補什麼，當然不會怎麼可能沒關係，印象中我考了三次零分，這可是會算進我 GPA 的怎麼可能沒關係，但是我清楚考零分代表我不會，這種強烈的不足感會驅使我去學習，這比分數寶貴多了，我寧願把那些分數當成讓我真正學會這些題目背後原理的代價，也不要靠某些伎倆拿 100 分但是根本不會。