# 2024q1 Homework5 (assessment)
contributed by < [yuyuan0625](https://github.com/yuyuan0625) >

## 閱讀〈[因為自動飲料機而延畢的那一年](https://blog.opasschang.com/the-story-of-auto-beverage-machine-1/)〉的啟發
作者在大學畢業前自行研發自動飲料機，途中就是不斷的遇到問題並且需要在有限的資源、設備之下解決。 令我印相深刻的是 Jserv 告訴作者: 「青春很貴，你也知道實習會發生什麼事，公司不會指派重要的工作給你，他們只會指派低風險的工作，你學習到的東西並不會比你現在多。你該學習的不是看到事情要完蛋了就去避免失敗，而是應該學習如何處理與承受失敗，你才能變得比以前更強大。」 我們在大學甚至研究所時期幾乎都只有應付學校中大大小小的考試和期末專題，從來沒有真正的解決生活周遭的事情，缺乏解決問題的能力。

---

## 研讀第 1 到第 6 週「[課程教材](https://wiki.csie.ncku.edu.tw/sysprog/schedule)」和 [CS:APP 3/e](https://csapp.cs.cmu.edu)

### 第二週

#### [C 語言: 數值系統](https://hackmd.io/@sysprog/c-numerics)

**運用 bit-wise operator**
- `x & (x - 1) == 0` 在 C 語言中表示：
- power of two
e.g. $4_{10} = 1\ 0\ 0_2$ , $3_{10} = 0\ 1\ 1_2$ , $1\ 0\ 0_2$ & $0\ 1\ 1_2 = 0\ 0\ 0_2$
- signed v.s. unsigned

- 將字元轉成小寫: 免除使用分支
- ' '(空格)的 [ASCII碼](https://zh.wikipedia.org/zh-tw/ASCII) 為 $32_{10} = 1\ 0\ 0\ 0\ 0\ 0_2$
- A = $0\ 1\ 0\ 0\ 0\ 0\ 0\ 1_2$ , a = $0\ 1\ 1\ 0\ 0\ 0\ 0\ 1_2$
- 英文大寫和小寫的 ASCII 剛好差 32 ，因此利用`\ ' '` 即可讓代表 32 的位元設為 1 ，達到大寫轉小寫的作用。
- 同理，也可利用 `& '_'` （ _ = $0\ 1\ 0\ 1\ 1\ 1\ 1\ 1\ 1_2$）, `^ ' '` 來分別達到將字元轉為大寫和大小寫互轉

('a' | ' ') // 得到 'a'
('A' | ' ') // 得到 'a'

#### [Linux 核心的 hash table 實作](https://hackmd.io/@sysprog/linux-hashtable)
**常見雜湊函數作法**：
1. Division method
2. Mid-square
3. Folding addition
4. Multiplication Method

:::warning
TODO
想比照比較同頁面下方 "golden ratio 與非 golden ratio" 的實驗方法，觀察這四值種 hash function 在輸入為亂數時發生碰撞的情形
:::

### 第三週

#### [你所不知道的 C 語言：遞迴呼叫篇](https://hackmd.io/@sysprog/c-recursion#Fibonacci-sequence)

- C 語言命名慣例
- 大寫結構體: 和作業系統、所屬環境有關
- 小寫結構體: 在文件中有定義的話就可以將它的成員取出來做特定操作

#### [你所不知道的 C 語言：技巧篇](https://hackmd.io/@sysprog/c-trick)

- C 語言中會將程式模組化，將程式分為 .h 檔 (header file) 和 .c 檔
- 編譯器一次只編譯一個檔案，每個檔案都是一個編譯單元，會有個別對應的 scope ，若 function 前面加上 `static` 表示該 function 的有效範圍僅在同一個檔案內，避免到時候 linking 的時候有多個檔案擁有相同的函式名稱，造成重複定義。

### 第四週

#### [你所不知道的 C 語言：編譯器和最佳化原理篇](https://hackmd.io/@sysprog/c-compiler-optimization)
Static Single Assignment, SSA
- 每個被 assign 的變數都只會出現一次

在編譯器最佳化中程式碼可能會被**重新排列**

### 第七週

#### [Linux 核心設計: 不僅是個執行單元的 Process](https://hackmd.io/@sysprog/linux-process)

Threads
- 建立 threads 的成本比建立 process 更低
- multitasking
- 切換成本較 process 低
- Linux Thread State Transition

#### [Linux 核心設計: 淺談同步機制](https://hackmd.io/@sysprog/linux-sync)

- mutex 和 semophore 的比較
- mutex 確保數個 process 在一個時間點上，只能有一個 process 存取單項資源
- semaphore 讓數個 producer 與數個 consumer 在計數器的基礎上進行合作: **總量控管**
:::danger
兩者應用場景不同、不要問題放一起比較
:::
| | mutex | semophore |
| -------- | -------- | -------- |
| 出現時間 | 較晚 (2.6.16版) | 較早
| 解鎖 | 只能由上鎖的 thread 解鎖 | 可由原本的 thread 或是另外一個 thread 解開 |
| 可進入 critical section 之 thread 數量 | 1個 | 多個
| 應用場景 | 常使用在 critical section 只能有一個 thread 進入，而且要避免 priority inversion 的時候 | 常用在同步兩個 thread 或功能上面，因為 Semaphore 實際上使用的是 signal 的 up 與 down，讓 Semaphore 可以變成是一種 notification 的作用，例如 A thread 執行到某個地方時 B thread 才能繼續下去
| priority inversion | 無 | 有

#### [並行和多執行緒程式設計-POSIX Thread](https://hackmd.io/@sysprog/concurrency/%2F%40sysprog%2Fposix-threads)

- thread-local storage (tls): 給 thread 一個專屬的空間 (不和其他 thread 共享)
- 例如可記錄 errno (error number)
- 硬體協助
- 無硬體協助

- Native POSIX Thread Library (NPTL): 一對一

- semophore
- sysv semaphore
- posix semaphore (現在系統, sem_ 開頭)

- 用 semaphore 控制總量、 nutex 控制 mutual exclusion

## 課堂提問
第二週 [C 語言: 數值系統](https://hackmd.io/@sysprog/c-numerics)
- **[Count Leading Zero](https://hackmd.io/@sysprog/c-numerics#Count-Leading-Zero)**
::: info
不明白為何 lookup table 的內容是這樣設計，也無法理解為何是乘上0x07C4ACDD 並向右位移 27 位元，想請老師幫忙解惑
:::

const int tab32[32] = {
     0,  9,  1, 10, 13, 21,  2, 29,
    11, 14, 16, 18, 22, 25,  3, 30,
     8, 12, 20, 28, 15, 17, 24,  7,
    19, 27, 23,  6, 26,  5,  4, 31
};
int log2_32 (uint32_t value)
{
    value |= value >> 1;
    value |= value >> 2;
    value |= value >> 4;
    value |= value >> 8;
    value |= value >> 16;
    return tab32[(uint32_t)(value*0x07C4ACDD) >> 27];
}

如果不用查表，要存2^32 -1 個
1. 建表格(64)、找規律
value*0x07C4ACDD 為 hash (夠大的整數)

TODO: 嘗試建立表格並引入規則來縮減

4 * 32 = 128 = 2 * cacheline (64B)

第七週 [並行程式設計: 實作輕量級的 Mutex Lock](https://hackmd.io/@sysprog/concurrency/%2F%40sysprog%2Fconcurrency-mutex)

::: info
futex 可用於實作使用者空間之同步機制，因此相較於 pthread mutex 每次都需要進行系統呼叫<s>調用</s>來的更節省資源，那 futex 是否有什麼使用限制或是 pthread mutex 有什麼優點呢，為何不全面使用 futex就好了? 想請問老師 pthread mutex 和 futex 各自適合的使用情境
:::
> https://hackmd.io/@sysprog/it-vocabulary

<s>
目前想到 pthread mutex 的優點:
1. 實作較簡單
2. 幾乎所有的 Unix-like 系統都支持 pthread，相容性高
</s>

pthread 是一個標準，每個作業系統有不同的實作方式
futex 使用限制?
- futex linux 特有

condition variable 的作用 : 通知 lock 的狀態
A, B, C <-- shared resource

futex_wake, futex_wait

mutex 是 ownership，如果所有執行序都要看 lock

## 簡述想投入的專案
並行程式設計

TODO: 研究 RCU // 閱讀去年的 userspace RCU: https://hackmd.io/@sysprog/ry_6RHgS3 並紀錄問題和重現實驗