# 2025-04-22 討論簡記
> [專題想法](https://hackmd.io/@sysprog/S18kgVDJex)

## rota1001
### 問題簡述
在閱讀 Demystifying the Linux CPU Scheduler 時，在看到 pid hash 的時候出現了疑問，這裡簡單來說是需要對於某個 type （PID、TGID、...）和一個數字，快速的找到對應的那些任務。

在第 18 頁有提到，linux 中有 4 個 PID 雜湊表，被內嵌在 `struct task_struct` 中，我判斷它指的是 `struct hlist_node pid_links[PIDTYPE_MAX]`。然而，在 19 頁說在 `struct task_struct` 中有一個 `struct pid`，裡面的 `struct hlist_node pid_chain` 會把 "colliding and different processes" 串起來，我的理解是它就是在雜湊函數出現碰撞的情況，並且配合 Figure 1.7 也可以做出這樣的解釋。

我原本的想像是有個全域的陣列，當我要以某個 type 去查詢的時候會通過這個陣列找到對應的雜湊表，而這個雜湊表是一個 `hlist_head` 的陣列，而一個 `hlist_head` 都能對應到一堆有同樣雜湊值的 `hlist_node`，而他們是內嵌在 `struct task_struct` 中的 `pid_links` 陣列的其中一項，所以可以根據這個找到對應的 `struct task_struct`。然而，我無法理解為何在 `struct pid` 中要有 `pid_chain` 這個元素。

於是我去閱讀了 linux 的程式碼，發現在 [`include/linux/pid.h`](https://github.com/torvalds/linux/blob/fc96b232f8e7c0a6c282f47726b2ff6a5fb341d2/include/linux/pid.h#L55) 中的 `struct pid` 是沒有 `pid_chain` 這個元素的（我看了 v5.* 到 v6.* 的程式碼都沒有），以下討論是使用 v6.14 版本的核心程式碼。首先是去看一下 `pid_links[type]` 這個東西是在哪被使用到，於是看到了 [`do_each_pid_task`](https://github.com/torvalds/linux/blob/fc96b232f8e7c0a6c282f47726b2ff6a5fb341d2/include/linux/pid.h#L190) 巨集：

#define do_each_pid_task(pid, type, task)				\
	do {								\
		if ((pid) != NULL)					\
			hlist_for_each_entry_rcu((task),		\
				&(pid)->tasks[type], pid_links[type]) {

發現對於某個 `struct pid`，它以某個 `type` 去走訪任務的時候，他的 `hlist_head` 是放在 `pid->tasks[type]` 裡面的。

接下來去看一下如果有一個 `nr`（也就是 PID），要怎麼做查詢，發現 `find_get_pid` 可以輸入 `nr` 找到對應的 `struct pid`，先看一下界面的設定：

/*
 * Lookup a PID in the hash table, and return with it's count elevated.
 */
extern struct pid *find_get_pid(int nr);

發現這個函式是用 PID 從雜湊表裡面找到對應 `struct pid`，並且把計數器加一。

追了幾層進去發現他是使用 radix tree 去[實作](https://github.com/torvalds/linux/blob/fc96b232f8e7c0a6c282f47726b2ff6a5fb341d2/lib/idr.c#L174)的：

void *idr_find(const struct idr *idr, unsigned long id)
{
	return radix_tree_lookup(&idr->idr_rt, id - idr->idr_base);
}

可以發現，他的雜湊表實際上是使用樹去查詢，而那些 `hlist_node` 和 `hlist_head` 都沒有用到。

### 小結論

這裡思考出了一種我覺得最合理的流程，就是先用 radix tree 找到對應的 `struct pid`，並且從他的 `task[type]` 對應的鏈結串列去查詢對應的任務，也就是這裡的 `hlist_node` 只是作為鏈結串列的節點使用。以書中的 TGID 的查詢為例好了，我現在要走訪整個 group。因為整個 group 裡面的 TGID 都會和 group leader 的 PID 一樣，如果我們使用 PID 去建一棵樹，我們就可以使用 `find_get_pid` 去找到對應的 `struct pid`。然後使用裡面的 `task[PIDTYPE_TGID]` 去走訪整個 group。下面有另外去說明 PGID 和 SID 是怎麼來的，可以發現同樣這種實作方式是可以運作的。

接下來我去找了使用情境的例子，在 [`kernel/exit.c`](https://github.com/torvalds/linux/blob/9d7a0577c9db35c4cc52db90bc415ea248446472/kernel/exit.c#L375) 中，可以看到使用 `do_each_pid_task` 的案例：

static bool has_stopped_jobs(struct pid *pgrp)
{
	struct task_struct *p;

	do_each_pid_task(pgrp, PIDTYPE_PGID, p) {
		if (p->signal->flags & SIGNAL_STOP_STOPPED)
			return true;
	} while_each_pid_task(pgrp, PIDTYPE_PGID, p);

	return false;
}

以上，它找了一個 process group leader，並且使用 `do_each_pid_task` 去走訪所有這個 process group 裡面的任務。

### 參考 [CPU Scheduling of the Linux Kernel](https://docs.google.com/presentation/d/1qDSFOfhGF-AX3O8CNzoAkQr_5ohr0nMVDlNfPnM9hOI/edit?fbclid=IwY2xjawJzV3JleHRuA2FlbQIxMAABHgp9Sbk6_RFhdvnpMlFpQ0t3pMb0xtDIS4EcYLbp-QrpJ47ix8SYlPEc01EJ_aem_jjtXT0iXR55u5Yh5b4TTzA&slide=id.g11990eefd4b_0_0#slide=id.g11990eefd4b_0_0) 做一些補充
首先是關於這 4 種 type，在簡報裡有更詳細的描述。每個 thread 有一個 PID，而一些 thread 組成一個 thread group，每個 thread group 有個 TGID，在這些 thread 中有一個 thread group leader，他的 PID 等於 TGID，而這個 thread group 其實就是 process。同樣的，一些 process 會組成一個 process group，每個 process group 有一個 PGID，而這些 thread 中（指的是裡面包含的所有 thread）會有一個 process group leader，且這個 thread 必須是 thread group leader，他的 PID 會等於他的 PGID。同樣的，一些 process group 會組成 login session，對應到的是 SID。

接下來去閱讀 [Control groups, part 6: A look under the hood](https://lwn.net/Articles/606925/) 之後發現，他有提到 `do_each_pid_task` 巨集，這段話驗證了我上面的那個猜想：
> Internally, a thread is represented by a struct task_struct and is sometimes referred to as a task. Unfortunately, processes are also sometimes referred to as tasks — there is a do_each_pid_thread() macro that, quite reasonably, iterates over threads. The matching macro for iterating over processes is do_each_pid_task() (both macros are defined in pid.h).

去看一下 `do_each_pid_thread` 的[實作](https://github.com/torvalds/linux/blob/fc96b232f8e7c0a6c282f47726b2ff6a5fb341d2/include/linux/pid.h#L202)：

#define do_each_pid_thread(pid, type, task)				\
	do_each_pid_task(pid, type, task) {				\
		struct task_struct *tg___ = task;			\
		for_each_thread(tg___, task) {

可以發現，他是使用 `do_each_pid_task` 去實作的。譬如說它如果 `type` 是 `PIDTYPE_PGID` 好了，那它會找到這個 process group 裡的所有 process，並且對於裡面的每個 process 都走訪他的所有 thread。

這裡還要補充 namespace 這個概念，每個 namespace 有自己的一堆 PID，一個任務在不同 namespace 可能有不同的 PID。同一個 PID 在不同 namespace 也可能對應不同任務。
上面在講 `find_get_pid` 的時候其實忽略了這個概念，一個 PID 其實不一定會對應到一個 `struct pid`，還要考慮在哪個 namespace 之下，而也可以看到這個函式的[實作](https://github.com/torvalds/linux/blob/9d7a0577c9db35c4cc52db90bc415ea248446472/kernel/pid.c#L322)預設使用現在的 namespace（我只是字面上理解）：

struct pid *find_vpid(int nr)
{
	return find_pid_ns(nr, task_active_pid_ns(current));
}

另外如果需要指定 namespace，可以使用 [`find_ge_pid`](https://github.com/torvalds/linux/blob/fc96b232f8e7c0a6c282f47726b2ff6a5fb341d2/include/linux/pid.h#L127)：

extern struct pid *find_ge_pid(int nr, struct pid_namespace *);

這裡引出了兩種不同的 process ID。linux 中的 process ID 分為 Global ID 和 Local ID，其中 Global ID 是每個任務在整個系統中獨特的 ID，放在 `task_struct` 中的 `pid` 和 `tgid`。而 Local ID 則是在某個 namespace 中的 ID。
### 課堂問題
:::success
問題：fork 之前已經用 pthread_create 建立 thread 了，thread 會複製嗎？
:::
提示：pthread_atfork

首先去做實驗，以下程式碼會先建立兩個新的 thread，並且使用 fork 去建立子行程。

void *thread_func(void *arg) {
    while (1);
}

int main() {
    pthread_t tid1, tid2;
    if (pthread_create(&tid1, NULL, thread_func, NULL))
        exit(1);
    
    if (pthread_create(&tid2, NULL, thread_func, NULL))
        exit(1);

    if (!fork())
        while(1);
    else
        wait(NULL);

    pthread_join(tid1, NULL);
    pthread_join(tid2, NULL);
}

將它執行起來後，使用以下命令先找到有哪些 process（執行檔檔名是 `threadtest`）：

$ ps aux | grep threadtest
rota1001   20147  200  0.0  19080  1632 pts/2    Sl+  00:36   0:03 ./threadtest
rota1001   20150  100  0.0  19080   384 pts/2    R+   00:36   0:01 ./threadtest

可以發現有兩個 process，接下來分別去查看這兩個 process 有哪些 thread：

$ ps -Lf -p 20147         
UID          PID    PPID     LWP  C NLWP STIME TTY          TIME CMD
rota1001   20147   18332   20147  0    3 00:36 pts/2    00:00:00 ./threadtest
rota1001   20147   18332   20148 99    3 00:36 pts/2    00:05:09 ./threadtest
rota1001   20147   18332   20149 99    3 00:36 pts/2    00:05:09 ./threadtest

$ ps -Lf -p 20150         
UID          PID    PPID     LWP  C NLWP STIME TTY          TIME CMD
rota1001   20150   20147   20150 99    1 00:36 pts/2    00:05:13 ./threadtest

LWP（Light Weight Process）很明顯指的是 thread，會發現親代行程有 3 個 thread，而子行程只有 1 個 thread，可以見得預設情況下 fork 的時候 thread 是不會被複製的。

至於要如何實現讓 fork 的時候在這個 process 中的 thread 都被複製過去呢？
根據 [pthread_atfork(3)](https://man7.org/linux/man-pages/man3/pthread_atfork.3.html)，`pthread_atfork` 的用法是輸入 3 個函式，分別代表三個時間點會執行的函式：
- `prepare`
執行 fork 之前的時候執行的
- `parent`
執行 fork 之後在親代行程執行的
- `child`
執行 fork 之後在子行程執行的

所以現在問題就是變成怎麼做到 thread 複製這件事了。如果只是要在子行程同樣的創建一些 thread，執行同樣的一些 callback function 的話，那麼可以單純的用 `pthread_create` 或 `clone` 就完成。但我想這裡的意思應該是要同時滿足與子行程共用地址空間，而且狀態要和親代行程中對應的 thread 的狀態相同，所以要另外複製對應 thread 的 stack 和暫存器的值。

## I-Ying-Tsai
> [kxo](https://hackmd.io/@DX3906/B105-Dxa1e)

### 泰勒展開的誤差上界

對於
$$
\log(1+x) = x - \frac{x^2}{2} + \frac{x^3}{3} - \cdots + (-1)^{n+1}\frac{x^n}{n} + R_{n+1}(x)
$$
其餘項 ： $$R_{n+1}(x)$$可以用「拉格朗日餘項」給上界：

$$
|R_{n+1}(x)| = \left|\frac{f^{(n+1)}(\xi)}{(n+1)!}x^{n+1}\right|
$$

其中 $\xi$ 位於 $0$ 與 $x$ 之間。
對 $\log(1+x)$ 來說，$f^{(n+1)}(x) = (-1)^{n}(n)!/(1+x)^{n+1}$ , 所以
$$
|R_{n+1}(x)| = \left|\frac{(-1)^n n!}{(n+1)!}\cdot\frac{x^{n+1}}{(1+\xi)^{n+1}}\right| = \frac{1}{n+1}\cdot\frac{|x|^{n+1}}{|1+\xi|^{n+1}}
$$
且 $0 < \xi < x$。

---

#### 試著計算 $\log(1.2)$ ，也就是 $x=0.2$ ：

$$
|R_{n+1}(x)| \leq \frac{1}{n+1}\cdot \frac{0.2^{n+1}}{1.2^{n+1}}
$$
我們希望這個誤差 $< 10^{-8}$ 。

**簡化**：對於 $x$ 不大（例如 $|x|<0.5$ ），可以估算：
$$
\frac{0.2^{n+1}}{1.2^{n+1}} = \left(\frac{0.2}{1.2}\right)^{n+1} = (1/6)^{n+1}
$$
所以
$$
\frac{1}{n+1}(1/6)^{n+1} < 10^{-8}
$$

得到**約11項**，能達到8位小數的精度。

---

#### 如果 $x$ 很大（如 $x=1$ ，例如 $\log(2)$ ）：

$$
|R_{n+1}(1)| \leq \frac{1}{n+1}\cdot\frac{1}{2^{n+1}}
$$
設
$$
\frac{1}{n+1}\cdot\frac{1}{2^{n+1}} < 10^{-8}
$$
可以發現
- $n=24$：$$\frac{1}{25} \times \frac{1}{2^{25}} \approx 1.19 \times 10^{-9}$$

所以**25項**可以達到8位小數的精度。

---

#### 若 $|x|<0.1$（如 $x=0.05$ ）：

$$
|R_{n+1}(0.05)| \leq \frac{1}{n+1} (0.05)^{n+1}
$$
- $n=7$ ：$$\frac{1}{8} \times 0.05^8 \approx 1.5 \times 10^{-11}$$

只需要**8項**

---

### 中點對數逼近法的運算成本

[數學推導部份參考了2025 年 Linux 核心設計課程作業 —— kxo (A)](https://hackmd.io/@sysprog/linux2025-kxo-a#Fixed-point-log)

- 精度目標：誤差 $\epsilon < 10^{-8}$（8位小數）。
- 初始區間：假設 $y$ 在 $[2^k, 2^{k+1}]$，最壞情況 $k=31$（32位無號整數）。

#### 計算所需迭代次數 $n$

- 假設最初 $L_0 = 0$，$R_0 = \log_2(\text{max}(y))$，即最大可能為 $2^{31}$，則 $R_0 = 31$。
- 要 $|R_n - L_n| < 10^{-8}$，所以
$$
\frac{31}{2^n} < 10^{-8}
$$
$$
2^n > 31 \times 10^8
$$
$$
n > \log_2 (31 \times 10^8)
$$
- $\log_2 31 \approx 4.95$
- $\log_2 10^8 \approx 8 \times 3.32 = 26.6$
- $4.95 + 26.6 = 31.55$

**所以 $n > 32$，即**：

> **需要至少 32 輪二分運算，才能在 $[1, 2^{31}]$ 的全區間達到 8 位小數的精度**

#### **每輪操作包括：**
- 1 次**定點乘法**（ $L \times R$ ）
- 1 次**定點平方根**（ $\sqrt{L \times R}$ ）
- 1 次**加法與右移（除2）**（ $(L_{\log} + R_{\log})/2$ ）
- 1 次**比較與條件選擇**

#### **總結：**
- 每輪成本是 $O(1)$，主要集中在乘法和開根號，無需高階多項式。

---

## LinMarc1210

> 解釋 [schedsort](https://hackmd.io/@sysprog/linux2025-quiz9) 的運作原理

[程式碼](https://gist.github.com/jserv/f5159c5d23a49f49e5f2d62d5f39c1f2)首先讀取輸入，檢查輸入資料數量，並呼叫 `schedsort` 進行排序，並且動態分配 `max_prio` 的空間如下：

size_t max_prio = (count < 512 ? 512 : (count < 4096 ? 1024 : 2048));

接著透過迴圈尋找輸入資料的最大和最小值，並定義 `val_range = val_max - val_min + 1;` ，作為等等 `fill_ctx_t` 結構的成員值。

整個程式碼並未呼叫排序演算法的 API ，而是透過多個 thread 並行寫入資料至優先級 bucket 中，再將多個 buckets 依順序合併。接下來分配 bucket 的空間，每個 bucket 就像是一個優先權佇列，並且總共有 `max_prio` 個 bucket，三種陣列的用意如下：
- `buckets`：優先級佇列，每個 bucket 就是一種優先級
- `bucket_sizes`：定義每個優先級裡面的資料數量，用 `_Atomic` 關鍵字宣告可以確保資料安全的被寫入 bucket 而不會有 race condition
- `bucket_caps`：定義每個 bucket 的最大容量，用來分配每個 bucket 的空間

:::info
為什麼是 `size_t max_prio = (count < 512 ? 512 : (count < 4096 ? 1024 : 2048));`
為什麼是 `bucket_caps[i] = (count / max_prio) * 2 + 8;` ？
:::

> 排序數量超過 1024 之後，發現有時候會寫排序錯誤，而且是在第一個 index 出錯，但有時候又會正確排序並輸出結果

接下來依照 `N_WORKERS` 數量去創造多個 thread，每個執行緒在執行 `fill_worker` 這個函式，並且把 `fill_ctxs[i]` 的地址當作 `fill_worker` 函式的參數，再將創建出的 thread id 用 `fillers` 陣列存起來。在進行 `pthread_create` 時，執行緒就會開始並行了，並且同步執行 `fill_worker`。主要執行緒，即呼叫 `pthread_create` 的執行緒則會繼續往下執行 `pthread_join`，在指定的執行緒執行完之前，目前的執行緒會阻塞自己。

`fill_worker` 函式負責插入資料到 bucket，而且每個執行緒透過 `i` 和 `stride` 決定要處理哪一段資料，可分為兩步驟：

1. 使用正規化技巧計算優先級，決定要放到哪個 bucket
2. 安全的放入該 bucket 避免並行時覆蓋 bucket 資料

一般正規化縮放整個資料範圍，但如果本來資料分佈就有偏態，在縮放後容易集中映射到少數 bucket，造成多執行緒對少數 bucket 的 atomic 操作競爭，因此 `schedsort` 運用以下正規化的方式減緩叢集效應的發生。

stable_code = ((value - val_min) << 32) | index;
bucket = (stable_code * MAX_PRIO) / ((uint64_t)range << 32);

參考題目說明，stable code 的設計特點包含：
- 穩定性 (stability）：相同值將保留原始順序，因為 `stable_code` 的值會以 index 較小者優先
- 均勻分布：透過將原始資料值減去最小值後左移 32 位元，並與原始索引結合，產生 64-bit 的 stable_code，再進行線性正規化，此映射手法有助於將偏態分布轉化為近似均勻分布，因為生成的 `stable_code` 會是唯一的。

計算完要放進哪個 bucket 後，接下來用 C11 Atomics 提供的操作取得唯一的 index。由於在同個 bucket 內可透過 bucket_sizes 追蹤該 bucket 目前的資料量，為避免覆蓋掉原本的資料，且考慮並行操作，應先取得當前最後一個元素的 index 並放到其後面 (FIFO)，因此 `AAAA` 應填入 `atomic_fetch_add(&ctx->bucket_sizes[norm], 1)`，這個操作會先 fetch 指定的地址所存放的值，再將其加 1 ，整個過程是不可分割的，避免更改值的時候其他執行緒存取值。

size_t index = atomic_fetch_add(&ctx->bucket_sizes[norm], 1);

當所有執行緒結束之後，要確定每個 bucket 的最終 size，因此用 `bucket_sizes_plain` 存放。要取得確定的 size，我們應從 `bucket_sizes` 著手並且賦值。`BBBB` 填入 `atomic_load(&bucket_sizes[i])`，以取得被宣告為 `_Atomic` 的 `bucket_sizes` 元素。

for (size_t i = 0; i < max_prio; i++)
    bucket_sizes_plain[i] = atomic_load(&bucket_sizes[i]);

:::info
這邊換成 `bucket_sizes[i]` 輸出結果也會對，因為同時間沒有其他的執行緒運行中，也就沒有人存取 `bucket_sizes[i]`
:::

而我們要計算每個 bucket 合併時的 offset，存放到 `bucket_sizes_offset` 中，因此使用 prefix sum 來計算。prefix sum 的概念是累加，計算這格時還要再加上前一格的值，因此 `CCCC` 應該填入 `bucket_sizes_plain[p - 1]`，所以 `bucket_sizes_offset[i]` 就會儲存前 `0~(i-1)` 個 bucket 共有幾個元素，作為合併時的 offset。

當資料都被放進 `buckets` 之後，就要將每個 `bucket` 依優先級合併，並將排序後的結果放回 `sorted`。此時也依據 `N_WORKERS` 的數量建立執行緒，此次執行緒是並行處理 `work_func`，共享一個 `sorted` 並將 bucket 的資料合併進去。主程式在建立完執行緒之後，一樣以 `pthread_join` 阻塞自己，直到指定的執行緒結束。

`worker_func` 則是依照 `offset` 和 `size` 直接找到目前 bucket 應該合併的位置，並依序放入資料到 `sorted`，這樣做可以避免多個執行緒競爭資源，而且線性寫入對快取較友善，避免隨機寫入的跳躍存取。

for (int p = ctx->begin_bucket; p < ctx->end_bucket; p++) {
    int *src = ctx->buckets[p];
    size_t len = ctx->bucket_sizes[p];
    size_t offset = ctx->bucket_offsets[p];
    for (size_t i = 0; i < len; i++)
        ctx->result[offset + i] = src[i];
}

執行緒結束後排序完成，將 `sorted` 複製到原 `data` ，並在主程式檢查 `data` 是否被正確排序。

### 統計模型

運用 perf 去做分析排序數量不同的情況，寫以下的腳本 `test.sh` 進行不同排序數量的測試：

> results.txt
for size in $(seq 100 10 8200); do
    input=$(for i in $(seq 1 $size); do echo $i; done)
    result=$(perf stat -e cycles,instructions,cache-misses \
             ./sort $input 2>&1)
    echo "Test results for $size elements:" >> results.txt
    echo "$result" >> results.txt
    echo "--------------------------" >> results.txt
done

並且將輸出使用以下程式 `plot.py` 繪圖：

import re
import matplotlib.pyplot as plt

with open("results.txt", "r") as file:
    lines = file.readlines()

sizes = []
elapsed_times = []
cycles = []
instructions = []
cache_misses = []

size_pattern = re.compile(r"Test results for (\d+) elements:")
time_pattern = re.compile(r"Elapsed time: (\d+\.\d+) us")
cycle_pattern = re.compile(r"\s*([\d,]+)\s*cpu_atom/cycles/")
instruction_pattern = re.compile(r"\s*([\d,]+)\s*cpu_atom/instructions/")
cache_miss_pattern = re.compile(r"\s*([\d,]+)\s*cpu_atom/cache-misses/")

current_size = None
for line in lines:
    if size_pattern.match(line):
        current_size = int(size_pattern.match(line).group(1))
        sizes.append(current_size)

    if time_pattern.match(line):
        elapsed_time = float(time_pattern.match(line).group(1)) / 1000.0 
        elapsed_times.append(elapsed_time)
    if cycle_pattern.match(line):
        cycle_str = cycle_pattern.match(line).group(1)
        cycles.append(int(cycle_str.replace(',', '')))
    if instruction_pattern.match(line):
        instruction_str = instruction_pattern.match(line).group(1)
        instructions.append(int(instruction_str.replace(',', '')))
    if cache_miss_pattern.match(line):
        cache_miss_str = cache_miss_pattern.match(line).group(1)
        cache_misses.append(int(cache_miss_str.replace(',', '')))

plt.figure(figsize=(10, 12))

print(sizes)
plt.subplot(3, 1, 1)
plt.plot(sizes, cycles, label='CPU Cycles', color='b')
plt.xlabel('Number of Elements')
plt.ylabel('CPU Cycles')
plt.title('CPU Cycles vs. Number of Elements')
plt.grid(True)

plt.subplot(3, 1, 2)
plt.plot(sizes, instructions, label='Instructions', color='g')
plt.xlabel('Number of Elements')
plt.ylabel('Instructions')
plt.title('Instructions vs. Number of Elements')
plt.grid(True)

plt.subplot(3, 1, 3)
plt.plot(sizes, cache_misses, label='Cache Misses', color='r')
plt.xlabel('Number of Elements')
plt.ylabel('Cache Misses')
plt.title('Cache Misses vs. Number of Elements')
plt.grid(True)

plt.tight_layout()
plt.savefig("plot.png")

在 `size_t max_prio = (count < 512 ? 512 : (count < 4096 ? 1024 : 2048));` 的情況下跑輸入數量 `count = 100~8200` 的測資，並用 `plot.py` 產生以下圖，但是發現在 `result.txt` 內，`count > 1024` 之後都產生錯誤排序。


試著將 `4096` 改成 `1024` ，`size_t max_prio = (count < 512 ? 512 : (count < 1024 ? 1024 : 2048))`，發現變成從　`count > 2048` 之後會開始排序錯誤。在 `count > max_prio` 的情況會有排序錯誤

## bevmmf

> 解釋 [quiz10 測驗二](https://hackmd.io/@sysprog/linux2025-quiz9) 程式碼之 `bloom_destroy` 為何要使用指向指標的指標。以下是函式原型宣告：

/**
 * @brief Destroy a Bloom filter and free resources.
 * @param filter Pointer to a pointer to a Bloom filter. Will be set to NULL.
 * @param dealloc Optional deallocator. If NULL, a default deallocator is used.
 */
void bloom_destroy(bloom_t **filter, bloom_dealloc_t dealloc);

/*------------------*/
/* Filter operations */
/*------------------*/

使用指向指標的指標 (`**filter`) 的原因是若使用 `*filter` 會有外層指標未 free 到而變身成 [dangling pointer](https://en.wikipedia.org/wiki/Dangling_pointer) 的狀況。若繼續使用 dangling pointer，會導致未定義行為 (undefined behavior)。
接下來可以來討論 dangling pointer 會對系統有什麼影響?首先，現代系統都有記憶體保護機制，此機制會將以釋放的記憶體標記為不可訪問。當試圖讀取或寫入時會導致 segmentation fault。而且，dangling pointer 對於重新配置的問題可能產生
- 如果你讀取這個指標，可能會得到不相關的資料，導致邏輯錯誤。
- 如果你寫入這個指標，可能會覆蓋其他物件的資料，造成資料損壞或程式崩潰。

Docker : 創造輕量級虛擬化技術。

Namespace : 複製好幾組 （不同的 IP 位址）

建立行程以及執行緒的方法相同。

Fork 已經有多個執行緒的行程，會發生什麼事？

pthread_atfork(); 實作 callback

Process 的源頭 ： task_struct

scheduling entity.

process isolation.

group scheduling.

init (PID = 1) ， 一定存在。

CPU bandwidth

namespace 都建立在 PID 之上。

no virtual CPU, use physical CPU.

pid_links 連結 namespace

namespace 與 cgroup 要處理同一目標，即 isolation。

---

## Andrushika, lumynou5

### 為何有了 epoll，還需要用到 select 和 poll？
- epoll 的底層實作是紅黑樹，搜尋時間複雜度為 $O(log N)$
- select 和 poll 在面對 `nfds` 極小的時候效率更好一些
- select 和 poll 其實在 linux kernel 幾乎是同一件事情，時代背景不同的產物

### 從設計者角度思考 `fork` 實作
根據 [man page](https://man7.org/linux/man-pages/man2/fork.2.html) 的描述：
> On success, the PID of the child process is returned in the parent, and 0 is returned in the child. On failure, -1 is returned in the parent, no child process is created, and errno is set to indicate the error.

Questions Behind the Questions -> 為何 `fork` 設計成回傳值為 0 時，表示在 child process 執行？

parent process (本來就知道自己的 PID，就想知道孩子在哪？)
+
|
+ child process (永遠可呼叫 getpid 來知道自己的 PID)
+
|
+--

思考：
1. 需要能透過回傳值區分現在是親代還是子代行程。
2. 子代行程可以透過 `getpid` 得知自己的 PID，不需要在 `fork` 時得到這項資訊，而親代行程需要。
3. （與其他系統呼叫介面設計的聯動）PID 參數特殊值 0 表示呼叫行程自身，因此 `fork` 回傳值在兩個行程中都可以指子行程。

### Zombie Process v.s. Orphan Process
老師在上課時提到 zombie process 的問題，會在作業系統中造成資源洩漏。原先以為 zombie process 只是單純的「親代行程死掉了、子代行程還活著」，即「沒人管的 child process」，但仔細閱讀了文件發現沒有那麼簡單。

#### zombie process
根據 man 中的 [wait(2)](https://man7.org/linux/man-pages/man2/wait.2.html) 描述：
> In the case of a terminated child, performing a wait allows the system to release the resources associated with the child.

> A child that terminates, but has not been waited for becomes a "zombie".

所以 zombie process 實際上「早就死了」，只是因為 parent 沒有呼叫 `wait` 取得子代行程的 exit status，所以 kernel 仍保留子代行程的相關資訊。

`exit(3)`：
> After exit(), the exit status must be transmitted to the parent process. There are three cases:
> - If the parent has set SA_NOCLDWAIT, or has set the SIGCHLD handler to SIG_IGN, the status is discarded and the child dies immediately.
> - If the parent was waiting on the child, it is notified of the exit status and the child dies immediately.
> - Otherwise, the child becomes a "zombie" process: most of the process resources are recycled, but a slot containing minimal information about the child process (termination status, resource usage statistics) is retained in process table. This allows the parent to subsequently use waitpid(2) (or similar) to learn the termination status of the child; at that point the zombie process slot is released.

關於子代行程從退出到親代行程呼叫的 `wait` 回傳之間算不算 zombie 的疑問，第二點說明了，如果在子代行程結束執行前，親代行程就在 `wait` 了，則子代行程會立刻死掉。

而如果親代行程直到結束都沒有呼叫 `wait`，則其 zombie child 會由 `init`「收養」，其將立即呼叫 `wait` 來從 process table 移除對應項目。
> If a parent process terminates, then its "zombie" children (if any) are adopted by init(1), (or by the nearest "subreaper" process as defined through the use of the prctl(2) PR_SET_CHILD_SUBREAPER operation); init(1) automatically performs a wait to remove the zombies.

#### orphan process
依照 zombie 的定義，那最一開始說的「親代行程死掉了、子代行程還活著」就不能算 zombie。後來發現了 [Stack Overflow](https://stackoverflow.com/questions/20688982/zombie-process-vs-orphan-process) 上面有人使用了一個名詞描述這種 process —— orphan（孤兒）。
但我在 man page 和 github 搜尋了很久都找不到相關的名詞解說，只能找到 `reparent` 一詞。最後在 [The Linux Programming Interface](https://broman.dev/download/The%20Linux%20Programming%20Interface.pdf) 中找到相關說明和程式範例 (Chapter 26)：
> If a child’s parent terminates, the child becomes an orphan and is adopted by
the init process, whose process ID is 1.

遇到這樣的狀況時，同樣會由 reaper （通常是 `init` 或 `systemd`）收養這些沒爸沒媽的 orphan，可以透過下方程式碼進行實驗（引用自 [The Linux Programming Interface](https://man7.org/tlpi/code/online/diff/namespaces/orphan.c.html)）：

int main(int argc, char *argv[])
{
    pid_t ppidOrig = getpid();

    pid_t pid = fork();
    if (pid == -1) {
        perror("fork");
        exit(EXIT_FAILURE);
    }

    if (pid != 0) { /* Parent */
        printf("Parent (PID=%ld) created child with PID %ld\n",
                (long) getpid(), (long) pid);
        printf("Parent (PID=%ld; PPID=%ld) terminating\n",
                (long) getpid(), (long) getppid());
        exit(EXIT_SUCCESS);
    }

    /* Child falls through to here */
    
    do {
        usleep(100000);
    } while (getppid() == ppidOrig); /* Am I an orphan yet? */

    printf("\nChild  (PID=%ld) now an orphan (parent PID=%ld)\n",
            (long) getpid(), (long) getppid());

    sleep(1);

    printf("Child  (PID=%ld) terminating\n", (long) getpid());
    exit(EXIT_SUCCESS);
}

## EricccTaiwan
signal 處理
https://hackmd.io/@sysprog/unix-fork-exec

    P1
        |
        ..
        |
        // wants to execute a command
        fork()
            |--- waitpid
            +---- execve() # 會佔據 process ，所以只有失敗會返回值，成功不會返回

[PTHREAD_MUTEX_TIMEDLOCK](https://man7.org/linux/man-pages/man3/pthread_mutex_timedlock.3p.html)
--> 在 userspace 中，對 lock 計時，假設 P1 和 P2 都要這個鎖，且被 P1 持有超過特定時間後，就會觸發 PTHREAD_MUTEX_TIMEDLOCK ，防止行程飢餓。
但 kernel space ，就沒有任何限制，代表使用者要對 kernel 負責。

NP 表示 non-portable (某個作業系統額外設計的機制)

產生 zombie process，其一可能是因為有孤兒，但也可能是 driver 沒寫好所導致行程的停滯，例如第三份作業的 kxo 。

## yy214123

sudo cat /proc/kallsyms | less

> 所有的 symbol 都是「高」位址

addressing (定址)，以 Arm
https://stackoverflow.com/questions/14460752/linux-kernel-arm-translation-table-base-ttb0-and-ttb1 ==> CPU 可決定 U/K 的定址

x86 永遠高地址表示 kernel mode

kernel mode、user mode

arm ttb0

linux 在 arm，kernel 也是高地址。

monolithic kernel 的 kernel 也能很小
> https://github.com/jserv/CuRT
> https://github.com/jserv/mini-arm-os

microkernel 的 kernel 也能很大

arm boot
arm server => UEFI (SystemReady: https://www.arm.com/zh-TW/architecture/system-architectures/systemready-compliance-program )

x86s: https://www.intel.com/content/www/us/en/developer/articles/technical/envisioning-future-simplified-architecture.html

## JeepWay

當程式 crash 時，執行 reset 重新執行 tty。

stty 對於不同的鍵盤輸入有預設的行為，例如 Crtl-C 是 interrupt，Crtl-S 是暫停畫面刷新，Crtl-Q 是恢復畫面刷新，要查看甚麼鍵綁定甚麼可以用 `$ stty -a` 來查看。