# 2020q3 期末自評題目
contributed by < `CW-B-W` >

###### tags: `sysprog2020`

---

[TOC]

---

### a) 知道 x - y < 0 敘述為何不能寫為 x < y 嗎？ (CS:APP 第 2 章)
舉例：
考慮 $x$, $y$ 為 32bit 數字
$x = -2^{31}$
$y = 2^{31}-1$
則 $x < y$ 為 $True$
但 $x - y$ 運算後為 $1$，$1 < 0$ 為 $False$

考慮到 Overflow 的可能性，$x - y < 0$ 與 $x < y$ 不等價

---

### b) 知道 C 語言規格書如何解釋 ptr++ 和 *ptr++ 行為的差異嗎？

---

### c) 知道 void (*signal(int sig, void (*handler)(int))) (int); 這樣的宣告該如何解讀嗎？

void (*signal(int sig, void (*handler)(int))) (int);

參考
[What's the meaning of this piece of code? void (*signal(int sig, void (*func)(int)))(int);](https://stackoverflow.com/questions/3706704/whats-the-meaning-of-this-piece-of-code-void-signalint-sig-void-funcin)

得知可以被解讀為如下

typedef void (*sighandler_t)(int);
sighandler_t signal(int sig, sighandler_t func);

即 signal 是一個 `function`
其兩個參數為 `int` 與 `void (*)(int)`
並回傳指向`以 void 為回傳值; 以 int 為參數的 function` 的 function pointer

---

### d) 知道 Linux 核心 < include/linux/list.h> 裡頭 #define list_for_each_prev(pos, head) for (pos = (head)->prev; pos != (head); pos = pos->prev) 這樣的巨集到底在做什麼？以及 head 使用時需要加小括號，為何？

---

### e) 知道從 color space RGBA8888 轉換為 8-bit 灰階的程式如何撰寫，又如何透過 SIMD 進行最佳化嗎？

---

### f) 知道如何對 linked list 進行 merge sort 嗎？真實世界中的應用場景為何？

---

### g) 知道 memory misalignment 對程式正確性和效能的影響嗎？

---

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

---

### i) 知道 C 語言規格書中如何定義 object 的生命週期嗎？能否舉出至少兩相對應的 CVE 呢？

---

### j) 知道如何寫出時間複雜度和空間複雜度皆為 O(1) 的 abs64 嗎？(沒有分支) 這樣的 abs64 又可用於真實世界哪邊？

---

### k) 知道 C 語言編譯器如何做 Tail Call Optimization (TCO) 嗎？以 gcc 來說，什麼樣的遞迴程式可做 TCO，又有什麼樣的遞迴程式無法呢？

---

### l) 知道 page fault 嗎？Segmentation fault 的訊息是如何顯示出來，請以 GNU/Linux 為例解說

---

### m) 知道 fixed point 嗎？相較於 floating point，這樣的機制有何優缺點呢？知道真實世界如何運用嗎？

---

### n) 知道 Poisson distribution 在本學期的課程主題中，出現在哪？以及為何工程議題需要考慮機率統計，能舉例嗎？

---

### o) 知道 LRU replacement policy 對程式碼效能的影響嗎？如何撰寫程式去驗證某個處理器的 cache 行為呢？

---

### p) 看懂 CS:APP 第 9 章講虛擬記憶體的描述嗎？知道 Linux 如何處理嗎？

---

### q) 知道傅立葉分析在通訊領域的應用嗎？舉例說明

---

### r) 知道如何用 gcc 內建的 __builtin_ctz 改寫 GCD (最大公因數) 求值程式嗎？做了這樣的最佳化，預期在 x86_64 上可省下多少 cycle 呢？

---

### s) 知道如何實作無失真資料壓縮嗎？你知道有哪些相關演算法？

---

### t) 知道 Bloom filter 嗎？以你寫過或用過的程式，舉例說明這機制帶來的好處

---

### u) 知道 ARMv7-A 指令的 conditional execution 嗎？請舉例說明其用法。

---

### v) 本學期課程內容中，讓你印象最深刻、顛覆過往認知的部分是什麼？請舉例說明

---

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

---