# 2025q1 Homework1 (ideas)
contributed by < `Andrushika` >

{%hackmd NrmQUGbRQWemgwPfhzXj6g %}

## 還政於民的 sched_ext 及機器學習如何幫助 CPU 排程 - `vax-r`

### SCX
* Scheduler extension and tools
* 可以讓使用者實作模擬 kernel thread 排程器、可以動態載入
* 透過 eBPF 載入運行
* 在 linux kernel 中運行的小型程式
* 不修改 kernel 的狀況下從 user space 載入擴充功能
* 可以攔截、觀察、修改系統行為
* e.g. 丟棄封包、監控流量
* 優點：加速排程策略的實驗速度、安全（不需修改 kernel，寫錯不會 crash）

### 引入 Machine Learning
#### 目標
* 用 Machine Learning 協助 task migration 的決策
（task migration: 一個 task 是否應該被放到另一個 CPU 上運行）
#### 相關工具
* kprobe: 監測 kernel function 執行狀況、累積訓練資料
* stress-ng: 創造 task 負載

#### 訓練資料的累積
* 製造出 CPU imabalance - 大量混雜 I/O bound task 和 CPU bound task
* 評估指標
* kernel compilation time (main metric)
* number of task migrations
* runq length difference

### 我的反思
* 除了上述提到的 metric 外，還有什麼可以用來衡量 CPU 排程的表現？
* cache hit/miss rate - 特別是在 task migration 議題上，頻繁更換執行的 CPU 可能不是好事
* I/O waiting time - 實驗時若混雜了大量 CPU bound 和 I/O bound task，那麼評估時是否兩種 task 的 metric 是否都應該考慮，而非只專注降低 CPU bound task 的 turn around time？
* 引入 machine learning 改善排程策略，或許也要考慮 model 本身會不會「太肥」；否則就算達成了完美的排程策略，model 本身卻吃掉了絕大部分的效能
* 是否可能引入 reinforcement learning？(動態學習、調整排程策略)
* 任何排程策略都免不了面臨不同硬體配置的問題，不同 core 數、是否有 GPU 等
* 使用者的用電腦習慣不同，可以觀察使用者的常用 task，動態改變優先級
* 該學長成為了 SCX top 10 contributor，仍自謙僅做了 refactor 和效能改進；我覺得開源的世界裡任何貢獻都是重要的
* 老師的名言：路見不平，拿 patch 來填

## 從 CFS, EAS, 到 EEVDF - `Kuanch`, `devarajabc`
### 觀察 CPU 行為的方法
* 使用 QEMU 模擬 Linux 系統
* QEMU 可用來模擬不同 CPU 架構的開源工具，搭配 KVM 可以做為 Hypervisor
* 使用 GDB 觀察核心行為
* 可以用 breakpoint 讓 kernel 停在某個狀態，更容易了解其行為
### CFS (Completely Fair Scheduler)
* 較關注 Fairness，依比例公平分配資源
* 最小 vruntime 者會優先得到 CPU 資源
* 多個 task 有相同 vruntime 時，採用 round robin
* 使用紅黑樹進行排列
* 可能會造成 starving
* 如果玩原神，可能會掉幀 (？)
#### virtual runtime
$$vruntime = delta\_exec \times \frac{weight\_nice\_0}{task\_weight}$$
* `delta_exec`：實際運行時間
* `weight_nice_0`：基準權重，`nice = 0` 時的權重
`nice` (-20~19) 決定優先級，`nice` 越小，權重越大
* `task_weight`：process 的權重
$$task\_weight =1024 \times 2^{\frac{nice}{5}}$$

### EEVDF (Earliest eligible virtual deadline first scheduling)
* 相較於 CFS，加上了急迫性考量 (deadline)，較小的 latency
* 有最小 daedline 的 task 會優先得到 CPU 資源
* 加入了 latency-nice 機制
* nice 表示 task 對 CPU 的數量需求
* latency-nice 表達 task 的頻率需求

### EAS (Energy Aware Scheduling)
* Linux Kernel 很多 benchmark 主要考量伺服器應用，而不貼近終端應用
* 終端設備需要考量功耗
* **並非排程器的一種**；可以掛在 EEVDF, CFS 上，讓那些排程策略以其擁有評判效率的機制
* 設備上會同時有大核、小核，應該要依據情況選擇功率最佳的核心去執行

### 我的反思
一開始的疑問是，為何 `task_weight` 的計算公式是長這樣，還需要用到指數計算？如果改成線性函數，會是甚麼樣子？
$$task\_weight = 1024 - (nice \times k)$$

我的猜測是，若使用線性函數，則不同的 nice 值所代表的權重可能會差異過大；所以使用指數函數，讓 nice 值去影響相對比例，而非固定的增加或減少。
（依據 CFS 的 `task_weight` 公式，每增加/減少 5 nice 值，權重會相差一半）

## 開發具體而微的 Linux 檔案系統 - `HotMercury`, `jason50123`
兩位作者從無到有開發了一個檔案系統 - SimpleFS
> 很喜歡他們報告的副標題 - "simple but not easy to me"

### 效能實驗
* rw: write
* runtime: 60 seconds
* direct: 1 (direct I/O，繞過 page cache)
* bs: 4KB (單次 I/O 操作的 Block Size)
* size: 10MB (測試總大小)

使用以上參數，測試連續的寫檔表現，得到以下結論：
* IOPS 意外的比現存的成熟 file system ext4, btrfs 等等還高
* 因為是 Blocking 操作，CPU 占用率非常高
* 直接操作讀寫 disk，所以 issued rwts 相當高

### 分區結構
> 講者未深入介紹，依據現行檔案系統實作慣例補充
* super block: 儲存整個檔案系統的基本資訊
* inode store: 儲存所有 inode 的地方，inode 將用來作為檔案或目錄 data blocks 的索引
* inode bitmap: 標記 inode 的使用狀況，每個 bit 代表一個 inode
例如：`1 1 0 0 1 0 1 0` (inode `0`, `1`, `4`, `6` 被使用了)
* block bitmap: 標記 data blocks 的使用狀況
* data blocks: 存放實際檔案數據的區塊，如文字或圖片等等

### 刪除資料操作
原先刪除資料的操作，會需要讓後方剩餘的檔案去「填補」刪除後空缺出來的空間。
:::info
例：
**1 -> 2 -> 3 -> 4 -> x** （原先的檔案結構）
若要刪除 `1`，則需要將 `2, 3, 4` 向前移動。
變成： **2 -> 3 -> 4 -> x -> x**
但這樣是相當耗費效能的操作；SimpleFS 的實作方法，是直接將刪除的 node 打上刪除標記，這樣就不必每次將後方的檔案 align 到新位置。
變成：**~~1~~ -> 2 -> 3 -> 4 -> x**
:::

### Journal
加入日誌系統，可以紀錄每次的操作，也能幫助 file system 從無預警的 crash 中復原。使用 jbd2 API 協作，分成三步驟：
1. 寫入檔案到 disk 的新區塊
2. 更新 journal 的 metadata（紀錄操作）
3. 更新 disk 的 metadata (inode 指向剛剛寫入的新區塊)


這樣可以保障做到一半 crash 時，有完善的恢復機制。
1~2 的過程 crash 時，因 journal 和 disk metadata 都還指向舊區塊，所以資料還是完好的、尚未寫入前的狀態。
2~3 的過程 crash，則可以透過 replay journal 來復原檔案。

> 關於講者提到的兩個 symlink bug，好像都是在 `rm` 之後發生，是否可能跟 rm 沒有正確更新 metadata 有關？

## 運用並行處理來強化網站資料存取的效率 - `yeh-sudo`
### Redis
* in-memory database，檢索資料更快
* 使用 key-value 儲存資料
* single threaded 資料庫，在並行處理情況下有效能瓶頸

### RCU (Read-Copy-Update)
* linux kernel 裡的一種同步機制
* 允許同時多 reader，單一 writer 更新資料
* 在 linux 中，現存的 spinlock 和 semaphore 皆存在效能瓶頸
* User Space RCU，簡稱 URCU，不須強制運行在 kernel space 中
* URCU 共有五種 flavors，原作者使用 Single-based RCU
* Single-based RCU：當 writer 寫入時，對所有的 reader 發送更新信號

### 執行緒數量影響效能
發現執行緒增加時，效能不一定會隨之增加。透過實驗可以發現，可能是受到 cache miss 和 context switch 的影響。
解法：加入 CPU affinity 的設定，發現可以提升吞吐量。
（圖：加入 CPU affinity 設定前後的吞吐量比較）

### 我的反思
講者在後續講解 CPU affinity 與並行 Redis 效能的關係時，並沒有提到他用來測試的 task 為何。以 RCU 的機制來說，不同 reader/writer 比例狀況下，吞吐量、延遲應該都會有所不同。尤其在若有大量 writer 的狀況下，RCU 所提供的效能提升應該相當有限。這部分應該在講解的時候定義清楚比較好。

## 高性能網頁伺服器 - `fatcatorange`
### CMWQ
* 欲改善的問題：現有系統透過 kthread 來服務用戶，當請求發生時，每次都會需要創建新的 thread；這樣會造成很大的效能瓶頸
* 引進 CMWQ 之後，會預先創建 thread pool 並等待 task 分發
### Directory Listing
* 原先在做目錄存取的時候，每次點擊不同的目錄，都需要發送請求給 server
* 使用 content cache，第一次存取目錄的時候就先全部放到快取中；後續直接從快取讀取即可，免去了每次都發送請求給 server 的時間成本
### 引入 Timer 釋放逾時連結及快取
* 使用 priority queue 來維護已建立的節點資訊，包含過期的時間等等
* 隨時間經過，同時檢查 priority queue 中節點是否過期；若過期則執行 callback function、進行刪除

### 我的反思
* CMWQ 部分，若是採用預先創建好的 thread pool，可能會造成 thread 數量和請求數量對不上的情況，若有大量請求時，latency 可能會很高；而沒什麼請求時背景也會有 thread 持續占用著系統資源。可以考慮加上「隨著流量動態調整 worker 數量」的機制去改善這點。
* 在測試 directory listing 的 cache 改善效果時只固定存取了同一路徑，應該要加入不同的路徑、隨機產生順序並進行多次測試比較準確。
（固定存取同一路徑，cache hit rate 一直保持在 100%，但現實情況不可能這麼理想）
* Timer 部分，持續去檢查 priority 中的節點是否過期，是否會占用系統資源？在什麼樣的 time interval 下持續檢查，會達到最好的效能、同時確保過期的 node 不佔用記憶體資源太久？

## 實作多核 RISC-V 處理器模擬環境並運作 Linux 核心 - `ranvd`
### 目標
基於 semu（由老師開發的 RISC-V 系統模擬器），去實作 hart state management，以達成**多核** RISC-V 系統模擬；最終使用 Linux 來驗證正確性。

### 專有名詞
* hart: 指的是硬體執行緒 (hardware thread)，即 CPU core
* SBI (Supervisor Binary Interface): 作業系統和 SEE 之間的 API 介面，確保無論 SEE 的實作如何抽換，SBI 提供的函式都能達到一樣的功能
* SEE (Supervisor Execution Environment): 在 Machine mode 下運行的軟體環境，負責實作 SBI 提供的函式功能
* semu: 輕量化的 RISC-V 系統模擬器。不同於其他模擬器，不需要執行韌體，可以直接在模擬器中提供 OS SBI 的函式使用

### 開機方式
#### RISCV_BOOT_SPINWAIT
Firmware 會將全部的 harts 給 kernel，由 kernel 決定其中一個 hart 來進行開機動作。
#### Ordered booting
Firmware 只將其中一個 hart 給 kernel 執行開機動作，再由 linux kernel 透過 HSM 將其他 kernel 喚醒。

### SBI HSM Extension
hart 可以分為以下三個狀態：
* stopped: hart 不在 supervisor mode 或更低優先權的模式運行；也可以是沒有在執行指令 or 斷電
* started: hart 正在運行
* suspended: 低功耗模式 or 沒有在執行指令
有以下四種方法可以控制 hart：
`sbi_hart_start`, `sbi_hart_stop`, `sbi_hart_suspend`, `sbi_hart_get_status`

### CLINT/ACLINT
兩者皆為 RISC-V 平台上常見用來送 hardware & software interrupt 的硬體。
* ACLINT 可以產生 supervisor-level 和 software-level 的 interrupt
* CLINT 只能產生 machine-level interrupt
* ACLINT 更為模組化，不同功能硬體的 memory map 分離

### PLIC
* interrupt controller，用來處理外部裝置的 interrupt
* 可以控制要將 interrupt 送到哪個 hart
* 作者將程式改版，原實作方式僅支援單核處理

### Atomic instructions
#### Atomic Memory Operations
確保單一操作不會被其他指令打擾、中斷。
> 因為只有一條指令，所以不會失敗，但操作受限

#### LR/SC
* LR (Load-Reserved): 讀取記憶體中的值後，設置一個 Reservation 保護標記
* SC (Store Conditional): 如果原地址的值未被修改 (即 Reservation 存在)，則可以成功寫入；否則寫入失敗
> 用兩條指令完成，引入了錯誤重試的機制，提供更多操作靈活性

## 打造具備網路連線的精簡虛擬機器 - `jimmylu890303`
### 目標
在運行虛擬機時，為 Guest OS 和 Host OS 之間創立網路連線的橋梁。
### 虛擬機器的分類
* System VM: 需要提供整個作業系統所需要的功能，涵蓋硬體 (CPU, Memory, peripheral device) 虛擬化技術
* Process VM: 僅需要提供虛擬環境給 Process，例如 JVM

### Hypervisor 的分類
#### Type-1 （裸機式）
* 直接運行在硬體上
* 效率較高
#### Type-2 （宿主式）
* 運行在作業系統上
* 存取硬體資源須透過作業系統，有延遲問題

> 老師提及，影響效能的是實作手段，並非 Type-2 的效能一定較低

### 名詞解釋
* KVM: 可將 kernel 轉換為 Hypervisor 的工具
* VirtIO: 虛擬化的 I/O device interface
* VirtIO-net: VirtIO 提供的虛擬網路裝置
* TAP (TunAble Packet Interface)，是 Linux 提供的虛擬網路介面，
有如 Guest OS 和 Host OS 之間的網路橋樑

### Virtqueue 的三大區域
Guest OS 會透過 Virtqueue 向 Host OS 提出 I/O 請求，以下三個區塊可以協助兩個 OS 知道 I/O task 處理的狀態。

#### Descriptor Area
存放 I/O 資料的描述資訊，用來指向 Guest OS 記憶體中的 I/O buffer。
當 Guest OS 有新的 I/O 請求時，會在這裡建立新的資料。

struct virtq_desc {
    le64 addr;  // 記憶體位址（指向 I/O Buffer）
    le32 len;   // Buffer len
    le16 flags; 
    le16 next;  // next descriptor
};

#### Available Area
會用來記錄尚未被處理的 I/O 請求，將可用的 Descriptor 的 idx 紀錄在此。

struct virtq_avail {
    le16 flags;
    le16 idx;
    le16 ring[];
    le16 used_event;
};

#### Used Area
用來記錄 Hypervisor 已經完成的請求的區域，讓 Guest OS 知道已處理完畢。

struct virtq_used_elem {
    le32 id;
    le32 len; // 已處理的數據 len
};

struct virtq_used {
    le16 flags;
    le16 idx; // descriptor idx
    struct virtq_used_elem ring[]; //queue
    le16 avail_event;
};

>疑問：`virtq_avail` 為何需要一個 `used_event` 欄位，以及 `virtq_used` 為何也需要 `avail_event` 欄位？兩個欄位看起來都和該 struct 的用途無關，一時也看不出用途，是否可以拿掉？

### Guest OS 的資料收發處理
使用兩個 thread 分別管理資料收發，兩者分別的任務如下：
* 接收資料 (RX Thread)：檢查 TAP 裝置是否有寫入事件；若有，則寫入到 virtqueue 中
* 傳送資料 (TX Thread)：檢查 virtqueue 是否有資料要進行傳輸及 TAP 是否可寫；若兩者條件皆符合，則寫入到 TAP 裝置中

### Virtio-net 工作流程
1. User appilication 欲傳送資料，先傳送給 driver
2. driver 將資料寫入 available buffer
3. virtio-net device 從 available buffer 讀取欲傳送的資料
4. 傳送資料到 Host OS Kernel space 中的 TAP 裝置
5. Network Stack 將資料傳送出去