[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.




int i = 0;
int *ptr = &i;
printf("%x\n", ptr++);
printf("%x\n", ptr);

result

90520084
90520088

可以看出第三行印出位置後，ptr 才會做 + 1，並且在下一次的 output 體現出來。

*ptr++

由於 ++ 的 precedence 高於 *，所以可以理解為 *(ptr++)






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

可以看出第四行先執行 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 使用時需要加小括號，為何？

#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() 時有實作過 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 對程式正確性和效能的影響嗎？

Image Not Showing Possible Reasons

The image file may be corrupted
The server hosting the image is unavailable
The image path is incorrect
The image format is not supported

Learn More →

當我所存取的資料位置不在 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

f) 知道如何用 bit-wise operator 實作 clz / ctz (count leading/tailing zero) 嗎？

TODO
https://hackmd.io/@UI2u7JOVTlu-J6Ny5jZ5hA/B18nZp1Jl
不是我寫的，需要微調

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 又可用於真實世界哪邊？

#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 (TCO)，好處是不用保留上一層 stack 的資訊，可以把他當作一個 for loop 使用，這樣會比原本的 recursion 還省空間，更不容易 stackoverflow。
引用 2020q3 quiz7









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)

Image Not Showing Possible Reasons

The image file may be corrupted
The server hosting the image is unavailable
The image path is incorrect
The image format is not supported

Learn More →

fixed point

將小數點的位置固定，以固定量的 bit 數目表達整數與小數的部分。
優點是運算快速省效能，缺點是表達的範圍很小。

floating point

以 IEEE 754 single-precision 為標準，他所能表達的數值範圍比較廣，但缺點是在極大與極小值的精度較差，且計算效率較差。

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#測驗-4

p) 知道 locality of reference 嗎？請以本學期教材或作業的程式碼，說明 locality 對於 cache 的影響

Take the matrix transpose in lab7 of Computer Architecture for example:

It compares two situations: careful locality (cache blocking) and careless locality (naive method)

This is a careful locality situation

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.

r) 請舉例說明 lock-free data structure，搭配 Linux 核心原始程式碼解說

s) 讀完授課教師撰寫的 Linux scheduler 電子書了嗎？你學到什麼呢？

目前只讀完 Chapter 1
有做一份筆記

t) 能否自行撰寫 SPSC, MPSC, SPMC, MPMC 程式碼呢？請用 lock-free 程式設計

自行撰寫的能力目前還不足夠