Try   HackMD

2025q1 Homework1 (ideas)

contributed by < Andrushika >

作業書寫規範:

  • 無論標題和內文中，中文和英文字元之間要有空白字元 (對排版和文字搜尋有利)
  • 文字訊息 (尤其是程式執行結果) 請避免用圖片來表示，否則不好搜尋和分類
  • 共筆書寫請考慮到日後協作，避免過多的個人色彩，用詞儘量中性
  • 不要在筆記內加入 [TOC] : 筆記左上方已有 Table of Contents (TOC) 功能，不需要畫蛇添足
  • 不要變更預設的 CSS 也不要加入任何佈景主題: 這是「開發紀錄」，用於評分和接受同儕的檢閱
  • 當在筆記中貼入程式碼時，避免非必要的行號，也就是該手動將 c= 或 cpp= 變更為 c 或 cpp。行號只在後續討論明確需要行號時，才要出現，否則維持精簡的展現。可留意「你所不知道的 C 語言: linked list 和非連續記憶體」裡頭程式碼展現的方式
  • HackMD 不是讓你張貼完整程式碼的地方，GitHub 才是！因此你在開發紀錄只該列出關鍵程式碼 (善用 diff 標示)，可附上對應 GitHub commit 的超連結，列出程式碼是為了「檢討」和「便於他人參與討論」
  • 留意科技詞彙的使用，請參見「資訊科技詞彙翻譯」及「詞彙對照表」
  • 不要濫用 :::info, :::success, :::warning 等標示，儘量用清晰的文字書寫。:::danger 則僅限授課教師作為批注使用
  • 避免過多的中英文混用，已有明確翻譯詞彙者，例如「鏈結串列」(linked list) 和「佇列」(queue)，就使用該中文詞彙，英文則留給變數名稱、人名，或者缺乏通用翻譯詞彙的場景
  • 在中文敘述中，使用全形標點符號，例如該用「，」，而非 ","。注意書名號的使用，即 〈 和 〉，非「小於」和「大於」符號
  • 避免使用不必要的 emoji 字元

還政於民的 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×weight_nice_0task_weight

  • delta_exec：實際運行時間
  • weight_nice_0：基準權重，nice = 0 時的權重
    nice (-20~19) 決定優先級，nice 越小，權重越大
  • task_weight：process 的權重
    task_weight=1024×2nice5

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×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: 存放實際檔案數據的區塊，如文字或圖片等等

刪除資料操作

原先刪除資料的操作，會需要讓後方剩餘的檔案去「填補」刪除後空缺出來的空間。

例：
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 指向剛剛寫入的新區塊)

Image Not Showing Possible Reasons
  • The image was uploaded to a note which you don't have access to
  • The note which the image was originally uploaded to has been deleted
Learn More →

這樣可以保障做到一半 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 設定前後的吞吐量比較）

Image Not Showing Possible Reasons
  • The image was uploaded to a note which you don't have access to
  • The note which the image was originally uploaded to has been deleted
Learn More →

我的反思

講者在後續講解 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 將資料傳送出去

image

Last changed by 
 
Andrew Chang
0
52

Read more

2025q1 Homework2 (quiz1+2)

contributed by &lt;Andrushika&gt;

Mar 17, 2025
2025q1 Homework1 (lab0)

contributed by &lt; andrew99154 &gt;

Mar 9, 2025
Read more from Andrew Chang
Published on HackMD