# 2025q1 Homework5 (assessment)
contributed by < `Andrewtangtang` >

## 作業上遇到的問題
### Lab0 dudect
在原作者的[程式碼](http://github.com/oreparaz/dudect/tree/master/src)中，，作者為了排除作業系統中斷等雜訊，先將所有執行時間排序，再對 1 % ~ 99 % 各百分位數（percentile）設定一條上界，把落在右側尾端的樣本裁掉， 對每一條裁剪後的資料集都重新做 Welch’s t-test。只要任一次測試拒絕統計的虛無假設，就判定存在 timing leakage。

#### 我的疑問
裁剪目的是剔除極端值（特別是因中斷而變長的 outliers），降低雜訊對檢定力的影響。所以說保留越多樣本會可能包含更含雜訊也就會導致檢定失敗機率變高。如果程式在未經裁切或者是僅裁切一小部分的資料點的情況下仍能通過 t‑test，不就已充分顯示它具常數時間特性？那為何作者的程式碼要對 1 %~99 % 每一個 percentile 都裁剪並重複檢定？既然越窄的裁剪只會使用更少樣本、檢定力更低，為何反而要把它們全部列入「只要有一次失敗就整體失敗」的規則？

:::danger
翻閱統計學課本，進行解讀，也該思考，為何作業系統的量化分析會用到統計學。
:::

### KXO
看到同學 HeatCrab 在討論區有一篇在探討 softirq 是否具有 task_struct 的 [文章](https://hackmd.io/@HeatCrab/Sy7tM2Kegx?fbclid=IwY2xjawKKl0NleHRuA2FlbQIxMQBicmlkETFlenJBcnRKQzM2NmxRZ2trAR48lTvaAp5lhG-6HdBItS8msJap3z2363_HaoKUcLGtddF-1Bdj7eanrs9Jtw_aem_dAlHrxD7SbcKYxXg2IWYEg) ，文中有說到 softirq 的其中一個觸發情況是，在 hardirq 處理完成後，核心檢查是否有 pending 的 softirq 並執行，假設當前正在執行 softirq 時，又發生了新的 hardirq，由於 hardirq 具有更高的優先權，會直接搶佔正在執行的 softirq。但文章中也提到 softirq 沒有獨立的 context（沒有 task_struct）且不能進入睡眠狀態。那當執行完 hardirq 要如何回到 softirq 之前正在執行的狀態？

## 〈Demystifying the Linux CPU Scheduler〉問題
### 2.1
書籍中在p40講 priority 的分數時我試著執行以下的指令想看看我電腦中 process 的 priority 與 rtprio 的數值是多少

$ ps -eo pid,comm,cls,rtprio,pri,ni,psr
    PID COMMAND         CLS RTPRIO PRI  NI PSR
      1 systemd          TS      -  19   0   5
      2 kthreadd         TS      -  19   0   6
      3 pool_workqueue_  TS      -  19   0   4
      4 kworker/R-rcu_g  TS      -  39 -20   0
      5 kworker/R-sync_  TS      -  39 -20   0
      6 kworker/R-slub_  TS      -  39 -20   0
      7 kworker/R-netns  TS      -  39 -20   0
      9 kworker/0:0H-ev  TS      -  39 -20   0
     12 kworker/R-mm_pe  TS      -  39 -20   0
     13 rcu_tasks_kthre  TS      -  19   0   0
     14 rcu_tasks_rude_  TS      -  19   0   2
     15 rcu_tasks_trace  TS      -  19   0   0
     16 ksoftirqd/0      TS      -  19   0   0
     17 rcu_preempt      TS      -  19   0   6
     18 rcu_exp_par_gp_  TS      -  19   0   0
     19 rcu_exp_gp_kthr  TS      -  19   0   6
     20 migration/0      FF     99 139   -   0
     21 idle_inject/0    FF     50  90   -   0

這邊我觀察到一個有疑問的地方，根據課本上所說
> real-time priority ranging from 0 (lowest priority) to 99 (highest priority). Internally, Linux adopts yet another convention, using an integer in the range 0 ≤ priority ≤ 139, as shown in Figure 2.3. The greatest priority value in this case is 0, while the least is 139.

所以 rtprio 的優先級分數越高代表說應該優先級越高，但是看看我以上的輸出結果，`pid = 20` 的 process rtprio=99 (代表是高優先及的任務) 對應到的 prio 是 139 數字最大的值，反觀`pid = 21` 的 process rtprio=50 對應到的 prio 卻是 90，雖然觀察 `pid = 20` 的 process 名字叫 migration 可以理解是非常需要即時執行的任務所以優先度應該是要非常高沒有錯，但是它 PRIO 的那個欄位的數字讓我十分疑惑，而我想到 `/proc` 檔案下應該也可以看到 process 的資訊，所以我又執行了以下的指令

$ cat /proc/20/stat
20 (migration/0) S 2 0 0 0 -1 69238848 0 0 0 0 0 1 0 0 -100 0 1 0 13 0 0 18446744073709551615 0 0 0 0 0 0 0 2147483647 0 0 0 0 17 0 99 1 0 0 0 0 0 0 0 0 0 0 0

搭配 [linux man-pages](https://man7.org/linux/man-pages/man5/proc_pid_stat.5.html) 對於各個欄位的定義，可得知第18個值是 -100
> (18) priority %ld
(Explanation for Linux 2.6) For processes running a
real-time scheduling policy (policy below; see
sched_setscheduler(2)), this is the negated
scheduling priority, minus one; that is, a number in
the range -2 to -100, corresponding to real-time
priorities 1 to 99. For processes running under a
non-real-time scheduling policy, this is the raw
nice value (setpriority(2)) as represented in the
kernel. The kernel stores nice values as numbers in
the range 0 (high) to 39 (low), corresponding to the
user-visible nice range of -20 to 19.
Before Linux 2.6, this was a scaled value based on
the scheduler weighting given to this process.

查看 [proc](https://github.com/torvalds/linux/blob/master/fs/proc/array.c) 顯示 process status 的核心程式碼，發現 proc 在顯示 priority 時會呼叫 [task_prio（）](https://github.com/torvalds/linux/blob/master/kernel/sched/syscalls.c#L191)

/**
 * task_prio - return the priority value of a given task.
 * @p: the task in question.
 *
 * Return: The priority value as seen by users in /proc.
 *
 * sched policy         return value   kernel prio    user prio/nice
 *
 * normal, batch, idle     [0 ... 39]  [100 ... 139]          0/[-20 ... 19]
 * fifo, rr             [-2 ... -100]     [98 ... 0]  [1 ... 99]
 * deadline                     -101             -1           0
 */
int task_prio(const struct task_struct *p)
{
	return p->prio - MAX_RT_PRIO;
}

來獲取 priority，所以真正在核心內部的 pid=20 的 priority 是 0 ，最後在看了 [ps man-page](https://man7.org/linux/man-pages/man1/ps.1.html) 才了解他的顯示方法
> pri PRI priority of the process. Higher number
means higher priority.

但我還是很好奇為什麼 ps 為什麼把 0 轉成 139？ 這樣轉換把原本核心的 priority 轉換成相反過來讓使用者看有什麼意義嗎？

### 2.3.3
CFS 排程策略透過比較 vruntime 的大小來決定要執行的任務。當任務實際執行時，vruntime 會在 scheduling point 根據公式 `vruntime += delta_exec × NICE_0_LOAD / task_weight` 進行累加。由於排程器優先挑選 vruntime 較小的任務執行，長時間來看，系統中各個任務的 vruntime 數值將會持續增加。我查閱了 `struct sched_entity`，發現 vruntime 是以 64-bit 無號整數 (u64) 儲存，但當系統長時間運行且未重啟的情況下， vruntime 不斷遞增是否有可能導致 overflow ？ Linux 核心是否針對這種情況設計了額外的處理機制避免過大數值帶來的精度和比較問題？

> Q: 為何 CFS 要總是要挑出最小的 vruntime 作為下個任務？(vruntime 是否有範圍？)
⇒ vruntime 不斷遞增是否有可能導致 overflow
vruntime 是用來表示某個任務在理想多處理器系統中已經執行了多久的時間。雖然在真實情況下會受到 context switch 等因素影響，無法完全實現理想狀態，但為了實現 CFS 所追求的 fairness，目標就是讓所有任務的 vruntime 盡可能接近。任務在實際執行時，其 vruntime 會根據 nice 值的權重而有所增長，這代表在考慮權重之後，該任務已經獲得了更多的 CPU 資源。為了讓每個任務的　vruntime　最終趨於一致，排程器應該選擇 vruntime 最小的任務來執行。

> GPS 模型提供了一個理想的流體模型，假設 CPU 的資源可以無限細分，並同時可以服務多個任務，每個任務可以依照權重比例持續推進。但在實際的硬體架構中，CPU 一次只能執行一個任務，無法真正做到同時運行。因此 CFS 採用了 WFQ 的概念，根據每個任務的 nice 值換算出對應的 weight，決定它在 GPS 模型下任務推進的速率，並用 vruntime 來記錄在 GPS 理想模型下每個任務在特定時刻下已經獲得了多少的服務量。而 CFS 不會在任意時刻動態切換任務，而是每次在 scheduling tick 或 time slice 結束時，離散地更新 vruntime，並從中挑選出 vruntime 最小（也就是最落後）的任務來執行。這些離散的調度決策在長期累積下來，會讓每個任務的 CPU 使用時間趨近於其權重比例，從而逼近 GPS 所定義的 fairness。

## 想要投入的專案

### 運用並行處理來強化既有的應用場景
- [Linux 核心專題: 並行化的 Redis 實作](https://hackmd.io/@sysprog/B1W2HKTER)

### 高性能網頁伺服器
- 寫作業 ktcp

### Linux 排程器研究
- [Linux 核心專題: CPU 排程器研究](https://hackmd.io/@sysprog/linux2024-projects?stext=2934%3A35%3A0%3A1746969027%3AuXXr46)

## 閱讀 〈自動販賣機而延畢的那一年〉觀後心得
看完了筆者這一系列的文章，其實不禁讓我十分感慨我們對於身邊許多物品能夠順利動起來似乎已經視為理所當然，就如同老師上課時常講到，我們天天在用手機，但當問我們手機手機拿起來螢幕要自動亮起來、手機通訊時這些訊號要怎麼被轉換時，我們其實一無所知，甚至也從來沒有思考過。筆者在開發飲料機時也深刻體會到了這件事，要讓整個機器可以自動化的動起來，每個細節的零件都必須相當的精確，尤其是他為了去計算到底冰塊的儲備量需要用多少時，他將飲料店過去兩年的冰塊使用數據直接翻出來繪製成圖表分析，從這件小事情其實可以看到筆者創業絕對不是只有熱情而是對於每個細節都相當重視，對應到如今我們要開發重要的軟體實務，我卻如此忽略細節，導致數學、程式能力低下也屬實是咎由自取。

面對失敗的態度：文章中有一段話讓我印象尤為深刻，「你不能現在就放棄，要是現在就放棄的話，你這輩子日後遇到這種等級的困難，就只會想逃避而已。」，我認為導致我讀了三年的資工系，導致我這個也不會，那個也不會有一部分很大的元兇就是我如同筆者遇到困難時先掙扎一下，後來又想放棄這個面對困難的態度相當雷同。系上的每一門課的學問其實深究到底都可以在linux kernel 看到其影子，但我們在選課的時候其實往往並不是在乎我們到底學了什麼知識，而是這堂課可不可以讓我拿90分，導致我們只要遇到困難的問題、困難的考試我們就用退選來逃避我們其實不會也不想學會的這個事實，我認為老師與學生互動這個模式，可以讓我們學習到的重點是問題的背後往往不是三言兩語可以解釋的，需要許多數學的驗證，作業系統跟硬體知識，就像老師問我為什麼 Redis 要使用 skip list 一開始我對這個資料結構一無所知，記錄問題並深入理解的過程中，許多的設計的考量例如和 B+ tree 在現代記憶體的設計比較，在多核的系統中如何減少 lock 的使用，這些衍生的問題都讓我意識到單一問題的背後都有更多的課題要去理解，也讓我意識到要用更謹慎更嚴肅的態度面對軟體開發的原理與細節。