# 2024q1 Homework5 (assessment)
contributed by < `Hualing-Chiu` >
## 測驗題改進與提問
## 閱讀〈因為自動飲料機而延畢的那一年〉的啟發
在閱讀完此篇文章後讓我感觸很深，並且開始反思自己，作者勇敢的為了創業而選擇延畢，我相信這不是所有人都能擁有的勇氣。
首先，作者在尋找懂機械設計和製造的人時發現了一個問題: 資工系的學生不會寫程式，機械系的學生不會做機械。學校教給學生的理論，有多少人是可以真正把它應用在實作上，派給學生幾個小專案當作作業，相信大多學生的想法都是反正截止日期之前把作業交上去就好，結果對了程式可以跑就好，然後留下了一堆自己看不到的 bug。
再者，「你最大的問題在太害怕失敗了」、「你該學習的不是看到事情要完蛋了就去避免失敗，而是應該學習如何處理與承受失敗，你才能變得比以前更強大。」在文章中看到老師的這些話，彷彿就是在對我說。自己反思過去的求學經歷，確實每次遇到問題都在逃避，害怕自己做不好而不敢挑戰，往往選擇最輕鬆的捷徑。不要害怕失敗，失敗就從中去吸取經驗，這是我現在需要去學習的事情。
## 研讀教材啟發
### [你所不知道的 C 語言：數值系統篇](https://hackmd.io/@sysprog/c-numerics)
#### 電腦不只有二進位
這個部分提到了 balance ternary，與一般三進位不同之處在於 $a = T(-1), 0, 1$，其整數與分數的表示法都跟二進位一樣，但在表示一個數的負數時較二進位方便：
* 二進位
$(6)_{10} = (0110)_2$
$(-6)_{10} = (1010)_2$
* 平衡三進位
$(6)_{10} = (1T0)_{bal3} = 1 \cdot 3^2 + (-1) \cdot 3^1 + 0$
$(-6)_{10} = (T10)_{bal3} = (-1) \cdot 3^2 + (1) \cdot 3^1 + 0$
所以在 balanced ternary 中要取一個數的負數，只要將全部的位元乘以 $-1$ 即可，比二進位的負數操作快速簡單。考慮以下 balanced ternary:
> `+++-0` = (1 * 3^4^) + (1 * 3^3^) + (1 * 3^2^) + (-1 * 3^1^) + 0
> = 81 + 27 + 9 + -3
> = 114
當我們考慮 `-114` 的表示法時，可以發現:
> `---+0` = (-1 * 3^4^) + (-1 * 3^3^) + (-1 * 3^2^) + (1 * 3^1^) + 0
> = -81 + -27 + -9 + 3
> = -114
也就是把所有的 `+` 和 `-` 對調，就不用像在 2 進位表示法中，需要特別考慮 signed 和 unsigned。
balanced ternary 的作用不僅在一致的方式去表達數值，還可用於浮點數。
### [你所不知道的 C 語言: bitwise 操作](https://hackmd.io/@sysprog/c-bitwise)
#### Bitwise Operator
* Set a bit :
```c
unsigned char a |= (1 << n);
```
* Clear a bit :
```c
unsigned char b &= ~(1 << n);
```
* Toggle a bit :
```c
unsigned char c ^= (1 << n);
```
* Test a bit :
```c
unsigned char e = d & (1 << n); //d has the byte value.
```
* The right/left most byte:
```c
unsigned char right = val & 0xff; /* right most (least significant) byte */
unsigned char left = (val >> 8) & 0xff; /* left most (most significant) byte */
```
* sign bit:
```c
bool sign = val & 0x8000; // sign bit
```
### [並行程式設計: 概念](https://hackmd.io/@sysprog/concurrency/%2F%40sysprog%2Fconcurrency-concepts)
#### Concurrency 與 Parallelism
Concurrency 指的是程式架構，將程式拆開成多個可獨立運作的工作，像是驅動程式都可獨立運作，但不需要平行化。
Parallelism 則指程式執行，同時執行多個程式，著重規劃， 將能夠並行的程式，分配給不同硬體單元，使其同時執行。
### [並行程式設計: Atomics 操作](https://hackmd.io/@sysprog/concurrency/%2F%40sysprog%2Fconcurrency-atomics#%E4%B8%A6%E8%A1%8C%E7%A8%8B%E5%BC%8F%E8%A8%AD%E8%A8%88-Atomics-%E6%93%8D%E4%BD%9C)
```c
_Atomic int cnt;
atomic_fetch_add_explicit(&cnt, 1, memory_order_relaxed);
```
> RMW (read-modify-write): 如 `atomic_fetch_add_explicit` 這類的 atomic 操作
通常 CPU 會提供有別於一般 load/store memory 的特殊指令去達成 RMW atomic:
* compare-and-swap (CAS) / swap (SWP):CAS 寫入時同時提供舊值，如果舊值和記憶體裡的相同，就將新值寫入，確保 RMW 的動作完整性
* load-link/store-conditional (LL/SC):這類指令會成對使用，在 LL 讀取記憶體的值，同時標記進入 exclusive 狀態，SC 寫入時清除 exclusive 狀態。在 exclusive 狀態時如有其他 core 較早執行寫入，導致 exclusive 狀態被清除，則忽略這次的寫入並返回失敗。程式可在下一行發現失敗時重新執行 LL/SC 的動作直到成功為止。
#### cache-coherence protocol
這是一個專門處理一至性協定的統稱。在多核處理器的情況下，為了確保所有 CPU 上的 cache 資料是一致的，當某個 CPU 進行寫入操作時，它必須保證其他 CPU 已將資料從他的 cache 中移除 (方可確保一致性)，僅在移除操作完成後，此 CPU 才能安全的修改資料。
### [並行程式設計: 實作輕量級的 Mutex Lock](https://hackmd.io/@sysprog/concurrency-mutex)
Futex 可用於實作使用者空間之同步機制，如 mutex、condition variable 等介面都可以藉此實作。
在多個臨界區段 (critical section，簡稱 CS) 之間，使用 mutex 保證互斥性，但無法滿足不同臨界區段之間的前後順序，因此可使**條件變數（condition variable，簡稱 condvar 或 cond）** 在一個臨界區段 A 中等待另一臨界區段 B 的訊號 (signal)。
condvar 不僅是互斥的同步機制，還要一種方式等待其他執行緒進行某些操作。當我們需要在臨界區段 A 中等待臨界區段 B 先完成某些操作時，可用 condvar。
### [事件驅動伺服器：原理和實例](https://hackmd.io/@sysprog/linux-io-model/https%3A%2F%2Fhackmd.io%2F%40sysprog%2Fevent-driven-server)
#### I/O Model
* Blocking I/O
* 基本上，Linux 中大部分的 socket 都是 blocking 的。
* 當user process 呼叫了 `read` 這個system call時， kernel 就會進入 I/O之第一階段: 等待資料準備。大多數情況下, 這個時間點都還沒有資料到達, 甚至是可能發生錯誤了(通常是system call被interrupt signal中斷)。這時候 user process 就會一直處於 blocking 的狀態, 直到 `read` 回傳準備好的資料, 並將資料從 kernel 複製至 user process的 memory, 最後待kernel回傳 OK 給user process後，user process才解除 blocking 的狀態並且繼續運作.
* Non blocking I/O
* 當user process呼叫 `read` 之後, 若 kernel 的資料還沒有準備好, 就不要 block user process了。反之，立刻回傳一個 `error`。
* nonblocking 其實就是 user process 要不斷地去問 kernel 說資料好了沒。這在 application 中的做法, 基本上就是用一個迴圈去一直呼叫 `read`。
* I/O multiplexing
* I/O multiplexing 就是 select / epoll 的行為
* 這種 model 的好處在於使用單個 process/thread 即可同時處理多個網路連接的 I/O。其原理就是 select / epoll 這類的 function 會一直輪詢其所負責監視的 socket，若當中有某個 socket 已經有資料了，就通知 user process。
:::info
I/O multiplexing 的好處是，只用單一執行緒即可「同時處理」多個網路連接的 I/O
* Asynchronous I/O
#### Reactor Pattern
同步的事件循環搭配 non-blocking I/O 又稱為 Reactor pattern
Reactor pattern 是個設計模式 (design pattern)，針對同時處理多個貨單個服務需求。服務處理任務 (service handler) 將傳入的需求拆解，然後分派給相關的請求端處理任務 (request handler)。
#### Edge vs. Level Triggering
`epoll` 的兩種工作模式談起:
1. Edge Triggered (ET, 邊緣觸發)
2. Level Triggered (LT, 條件觸發)
ET 表示在狀態改變時才通知 (例如: 在邊緣上從低電位到高電位)，LT 表示在這個狀態才通知 (例如: 只要處於低電位就通知)。對應到 epoll，ET 指一旦有心資料就通知 (狀態的改變)，而 LT 是「只要有新資料」就會持續通知，直到緩衝區的資料全數取出。
### [以 sendfile 和 splice 系統呼叫達到 Zero-Copy](https://hackmd.io/@sysprog/linux-io-model/https%3A%2F%2Fhackmd.io%2F%40sysprog%2Flinux2020-zerocopy)
sendfile 系統呼叫的提出，就是克服上述問題，取代 read/write 兩個操作，並減少 context switch 和資料複製的次數:
```c
sendfile(socket, file, len);
```
## 簡述想投入的專案
### 高效網頁伺服器
> 探討從無到有打造 Linux 平台的高效能網頁伺服器，涵蓋是否該將伺服器實作於 Linux 核心內部、並行處理、I/O 模型、epoll、Reactor pattern，和 Web 伺服器在事件驅動架構的考量。
需要研讀的一些教材:
[Linux 核心設計: 針對事件驅動的 I/O 模型演化](https://hackmd.io/@sysprog/linux-io-model/https%3A%2F%2Fhackmd.io%2F%40sysprog%2Fevent-driven-server)
[並行程式設計: 排程器原理](https://hackmd.io/@sysprog/concurrency-sched)
[ktcp](https://hackmd.io/@sysprog/linux2024-ktcp/%2F%40sysprog%2Flinux2024-ktcp-a)
### 開發加速 LLaMA 的 Linux 核心模組
瀏覽今年的期末專案有看到有同學被指派這個題目，我們實驗室本身的研究是對話系統相關的領域，所以 LLaMA 這個大型語言模型在之後的論文或許有機會被應用，因次對這個題目感興趣。
### 並行程式設計
> 回顧[〈並行和多執行緒程式設計〉](https://hackmd.io/@sysprog/concurrency/%2F%40sysprog%2Fconcurrency-concepts)教材和相關測驗題，強化對延伸問題的掌握
---
並行的單向鏈結串列
```c
#include <stdatomic.h>
typedef struct __list {
int val;
struct __list *next;
} list_t;
// **concurrent** add_tail and remove
_Atomic list_t *head = NULL;
```
Head
|
A --> B --> C
|
Tail
1. Remove A
2. Add_tail D (after C)
操作會衝突的狀況：
* 相鄰節點的更新
> TODO: 繼續寫程式並測試
TCP 3-way handshake ?
SYN
https://hackmd.io/@sysprog/SyrtOTNb0
TODO: 第七次作業的 cserv (multiple processes)，試著去執行 (含效能評比，要對照 Nginx)
TODO: https://hackmd.io/@sysprog/linux2024-quiz8 和 https://hackmd.io/@sysprog/concurrency-sched (注意看 neco，是 M:N threading model)
TODO: 改寫 cserv，使得其具備 M:N threading model
Sign in with Wallet
Connect another wallet