# 4/16 一對一問題回復

## linux 核心的 `list_sort` 實作考量

在 linux 核心的 `list_sort` 使用 buttom-up merge sort 實作排序，buttom-up 與 top-down 的差異在於 buttom-up 少了 partition 這一步驟。

此作法可以省去 recursive 和 stack 的使用（會佔用大量記憶體的寫法，並且會較常去 catch 記憶體更新 cache 內容）

其效能比較根據如下（`q_sort` 為 lab0-c 實作之排序）：

- `q_sort`
| #node | cache-misses | branches | instructions | context-switch |
| ------- | ------------ | ----------- | ------------ | -------------- |
| 1000 | 3469 | 77,9884 | 516,0401 | 0 |
| 10000 | 3,3403 | 621,9374 | 4305,8950 | 0 |
| 100000 | 543,0532 | 6326,2119 | 4,3295,3471 | 0 |
| 1000000 | 7491,5547 | 4,6974,1917 | 31,6153,3055 | 10 |

- `list_sort`
| #node | cache-misses | branches | instructions | context-switch |
|-------|--------------|----------|--------------|-----------------|
|1000|2489|77,7798|519,9240|0|
|10000|4,1257|614,2028|4329,3845|0|
|100000|439,1922|6258,0696|4,3642,0292|3|
|1000000|5824,6891|4,6028,3507|31,6579,3448|9|

可以看到 cache-misses 在資料量大的時候差距愈大，代表硬體處理時間也相對少了。
## Linux 核心的 clone 系統呼叫作用

在 man page 中， `clone` 的敘述為
> clone, __clone2, clone3 - create a child process

linux 並未明確定義 process 和 thread，而是以 `task_struct` 表示，在 linux 上可以依照 PID 和 TGID 來分辨 process 和 thread，同一個 process 的 thread 其 TGID 是一樣的，而不同的 Thread 有不同的 PID，因此在呼叫 `getpid()` 時回傳此 thread 的 TGID (其定義上較符合 process)，而 `gettid()` 則會回傳 PID。

至於為何 `clone` 可以創造 process 也可以創造 thread，clone 可以設定 new process 與 parent process 共享同一個位址空間的資源，這就跟 thread 的定義一樣了，同一個 process 內的 thread 可以共享同一個位址空間的資源。

## NFA v.s DFA in compiler

NFA 和 DFA 代表有限自動機的分類，分別為「非確定性」和「確定性」
- 確定性（deterministic）：此有限自動機在任何狀態的同一個輸出下只會有一種狀態變化。
- 非確定性（non-deterministic）：同一個輸出可能有兩種以上的狀態變化。

其在 Compiler 裡有兩種應用情境：
1. Regex matching（正規表示式匹配）
Regex（Regular Expression）可以表示在程式裡合法的單詞集合（由一連串的文字與符號組成），而每一個程式語言的 Regex 早已規定在 compiler 裡面，在編譯語法之前，編譯器就會先將程式內部出現的單詞（變數、函式、巨集等）進行 Regex matching，查看是否符合表示式規範。
2. Syntax Analysis（語法分析）
語法分析的有限自動機與 Regex 一樣根據不同語言有固定的語法規範，而語法分析的主要目的是將程式碼轉為抽象語法樹（Abstract Syntax Tree）以便後續編譯過程效率增加。