# [2021 Linux 核心設計] 期末自我評量填寫
contributed by < `ccs100203` >
###### tags: `linux2021`
## a) 知道 x - y < 0 敘述為何不能寫為 x < y 嗎？ (CS:APP 第 2 章)
- overflow 時就會出問題
- 又假設 x 跟 y 都是 signed-integer
x 是任一正數, y 是 signed-integer 所能表達的最小的數值。那麼 $x - y < 0$ 恆成立，因為 $y==-y$，則 $y < x$ 必然成立，就會與題目的判斷式相違背。
## b) 知道 C 語言規格書如何解釋 ptr++ 和 *ptr++ 行為的差異嗎？
#### ptr++
根據 c99 6.5.2.4.2
> The side effect of updating the stored value of the operand shall occur between the previous and the next sequence point.
```c=
int i = 0;
int *ptr = &i;
printf("%x\n", ptr++);
printf("%x\n", ptr);
```
- result
```
90520084
90520088
```
可以看出第三行印出位置後，ptr 才會做 + 1，並且在下一次的 output 體現出來。
#### *ptr++
由於 `++` 的 precedence 高於 `*`，所以可以理解為 `*(ptr++)`
```c=
int i[3] = {3,6,9};
int *ptr = i;
printf("%x\n", ptr);
printf("%x\n", *ptr++);
printf("%x\n", ptr);
printf("%x\n", *ptr);
```
- result
```
9b317844
3
9b317848
6
```
可以看出第四行先執行 `ptr++` 後，會對 0x9b317844 做 dereference，在 `printf` 結束後再把 `ptr + 1`，所以可以看到第五行的 `ptr` 已經指到了下一個位置。
## c) 知道 void (*signal(int sig, void (*handler)(int))) (int); 這樣的宣告該如何解讀嗎？
- 宣告一個 function `signal()`
- ```void (*handler)(int)``` 是一個 function pointer，傳入 int 然後 return void.
- ```signal(int sig, void (*handler)(int))``` 是一個 function，傳入 int sig, void (*handler)(int) 並 ruturn 一個 function pointer.
- 假設 singal 回傳的變數為 fp, 那麼就會變成```void (*fp) (int); ```, 可以看出最後我們會得到一個 function pointer.
## d) 知道 Linux 核心 < include/linux/list.h> 裡頭，這樣的巨集到底在做什麼？以及 head 使用時需要加小括號，為何？
```c
#define list_for_each_prev(pos, head)
for (pos = (head)->prev; pos != (head); pos = pos->prev)
```
This macro will iterate over a list backwards.
- `pos` is a loop cursor.
- `head` is the head of list.
If we don't use parenthesis, we will suffer some problems.
e.g. ```list_for_each_prev(pos, head + 1)```
If I pass `head + 1` into the macro, but I don't use parenthesis. Because of the operator precedence, it's execution order is ```(head + (1 -> prev))```, and the compiler will report the error.
## e) 知道如何對 linked list 進行 merge sort 嗎？真實世界中的應用場景為何？
在 [lab0 q_sort()](https://hackmd.io/@cccccs100203/linux2020-lab0#q_sort) 時有實作過 merge sort。
e.g. Sorted() is a function in python, which uses Timsort as its algorithm, and Timsort is a hybrid algorithm of insertion sort and merge sort.
## g) 知道 memory misalignment 對程式正確性和效能的影響嗎？
- 當我所存取的資料位置不在 4 的倍數上時，processor 會先讀取上半邊的區塊，篩掉不需要的資料，再讀取下半邊的區塊，一樣過濾掉不需要的資料，最後再將兩者整合再一起，完成一次的存取。很明顯的這樣多了一次的操作，於是就會對效能產生影響。
- Atomic instruction 是不可分割的，當 processor 執行 atomic instruction 時，如果所需存取的資料存放在不同的 page 上，又其中一個 page 在記憶體裡，而另一個不在。此時會發生 page fault，並且執行 virtual memory management。這樣會導致 atomicity 被破壞，正確性會有疑慮。 e.g. PowerPC 上要求 atomic instruction 存取的資料至少要對齊 4 byte。
參考 [Data alignment: Straighten up and fly right](https://developer.ibm.com/technologies/systems/articles/pa-dalign/)
## f) 知道如何用 bit-wise operator 實作 clz / ctz (count leading/tailing zero) 嗎？
TODO
https://hackmd.io/@UI2u7JOVTlu-J6Ny5jZ5hA/B18nZp1Jl
不是我寫的，需要微調
```cpp
int clz(int x){
int n = 32;
unsigned y;
y = x >>16; if (y != 0) { n = n -16; x = y; }
y = x >> 8; if (y != 0) { n = n - 8; x = y; }
y = x >> 4; if (y != 0) { n = n - 4; x = y; }
y = x >> 2; if (y != 0) { n = n - 2; x = y; }
y = x >> 1; if (y != 0) return n - 2;
return n - x;
}
int ctz(int x) {
int n = 0;
unsigned y;
y = x & 0x0000ffff; if (y == 0) { n += 16; x >>= 16; }
y = x & 0x000000ff; if (y == 0) { n += 8; x >>= 8; }
y = x & 0x0000000f; if (y == 0) { n += 4; x >>= 4; }
y = x & 0x00000003; if (y == 0) { n += 2; x >>= 2; }
y = x & 0x00000001; if (y == 0) return n + 1;
return n;
}
```
## g) 知道 C 語言規格書中如何定義 object 的生命週期嗎？能否舉出至少兩相對應的 CVE 呢？
## h) 知道如何寫出時間複雜度和空間複雜度皆為 O(1) 的 abs64 嗎？(沒有分支) 這樣的 abs64 又可用於真實世界哪邊？
```c
#define abs(num) (((num >> 63) ^ num) - (num >> 63))
```
#### 程式概念:
- 遇到負數的話就先將他轉變成一補數，然後再做 +1 轉換成二補數，如果是正數或 0，則不需改變他。
- `number ^ 1` 會是 Toggle，而 `number ^ 0` 不會有任何改變。
- `(num >> 63)`可以做出全部都是 1 或 0 的 mask
- 正數以及 0: 得到 0
- 負數: 得到 -1, 即為 111...1111
- ```((num >> 63) ^ num)```
- 正數以及 0: 會得到相同的數字
- 負數: 會得到 1 補數
- ```(num >> 63)```
- 正數以及 0: 會得到 0
- 負數: 會得到 -1
## i) 知道 C 語言編譯器如何做 Tail Call Optimization (TCO) 嗎？以 gcc 來說，什麼樣的遞迴程式可做 TCO，又有什麼樣的遞迴程式無法呢？
- [Tail Call Optimization](https://en.wikipedia.org/wiki/Tail_call) (TCO)，好處是不用保留上一層 stack 的資訊，可以把他當作一個 for loop 使用，這樣會比原本的 recursion 還省空間，更不容易 stackoverflow。
- 引用 2020q3 [quiz7](https://hackmd.io/@sysprog/2020-quiz7#測驗-2)
```c=
int *global_var;
void f(void)
{
int x = 3;
global_var = &x;
...
/* Can the compiler perform TCO here? */
g();
}
```
- 要是 `g()` 對 `global_var` 做 dereference，代表 `f` 內的資料需要保存而不能提前從 stack pop。
- 要是 `g()` 沒有對 `global_var` 做 dereference，那麼就有機會做 TCO.
## j) 知道 page fault 嗎？Segmentation fault 的訊息是如何顯示出來，請以 GNU/Linux 為例解說
## k) 知道 fixed point 嗎？相較於 floating point，這樣的機制有何優缺點呢？知道真實世界如何運用嗎？ (例如 Linux 核心的 CFS)
#### fixed point
將小數點的位置固定，以固定量的 bit 數目表達整數與小數的部分。
優點是運算快速省效能，缺點是表達的範圍很小。
#### floating point
以 [IEEE 754 single-precision](https://en.wikipedia.org/wiki/Single-precision_floating-point_format#IEEE_754_single-precision_binary_floating-point_format:_binary32) 為標準，他所能表達的數值範圍比較廣，但缺點是在極大與極小值的精度較差，且計算效率較差。
## l) 知道 Poisson distribution 在本學期的課程主題中，出現在哪？以及為何工程議題需要考慮機率統計，能舉例嗎？
## m) 知道 LRU replacement policy 對程式碼效能的影響嗎？如何撰寫程式去驗證某個處理器的 cache 行為呢？
## n) 看懂 CS:APP 第 9 章講虛擬記憶體的描述嗎？知道 Linux 如何處理嗎？
## o) 知道如何用 gcc 內建的 __builtin_ctz 改寫 GCD (最大公因數) 求值程式嗎？做了這樣的最佳化，預期在 x86_64 上可省下多少 cycle 呢？
https://hackmd.io/@cccccs100203/linux2020-quiz3#%E6%B8%AC%E9%A9%97-4
## p) 知道 locality of reference 嗎？請以本學期教材或作業的程式碼，說明 locality 對於 cache 的影響
Take the matrix transpose in [lab7](https://cs61c.org/su20/labs/lab07) of Computer Architecture for example:
It compares two situations: careful locality (cache blocking) and careless locality (naive method)
- This is a careful locality situation
```c
void transpose_blocking(int n, int blocksize, int *dst, int *src) {
for (int i = 0; i < n; i += blocksize) {
for (int j = 0; j < n; j += blocksize) {
for (int k = i; k < blocksize + i && k < n; k++) {
for (int l = j; l < blocksize + j && l < n; l++) {
dst[l + k * n] = src[k + l * n];
}
}
}
}
}
```
- n: 1000, blocksize: 20
```
Testing naive transpose: 1.651 milliseconds
Testing transpose with blocking: 0.914 milliseconds
```
The careful locality program got a better performance.
## q) 知道 cache thrashing 和 false-sharing 嗎？請以 Linux 核心原始程式碼作為解說
## r) 請舉例說明 lock-free data structure，搭配 Linux 核心原始程式碼解說
## s) 讀完授課教師撰寫的 Linux scheduler 電子書了嗎？你學到什麼呢？
目前只讀完 Chapter 1
有做一份[筆記](https://hackmd.io/9OGZ3m97RYGXdzWe4Hglng?view)
## t) 能否自行撰寫 SPSC, MPSC, SPMC, MPMC 程式碼呢？請用 lock-free 程式設計
自行撰寫的能力目前還不足夠
## v) 本學期課程內容中，讓你印象最深刻、顛覆過往認知的部分是什麼？請舉例說明
Sign in with Wallet
Connect another wallet