2024q1 Homework5 (assessment)

contributed by < Hualing-Chiu >

測驗題改進與提問

閱讀〈因為自動飲料機而延畢的那一年〉的啟發

在閱讀完此篇文章後讓我感觸很深，並且開始反思自己，作者勇敢的為了創業而選擇延畢，我相信這不是所有人都能擁有的勇氣。
首先，作者在尋找懂機械設計和製造的人時發現了一個問題: 資工系的學生不會寫程式，機械系的學生不會做機械。學校教給學生的理論，有多少人是可以真正把它應用在實作上，派給學生幾個小專案當作作業，相信大多學生的想法都是反正截止日期之前把作業交上去就好，結果對了程式可以跑就好，然後留下了一堆自己看不到的 bug。
再者，「你最大的問題在太害怕失敗了」、「你該學習的不是看到事情要完蛋了就去避免失敗，而是應該學習如何處理與承受失敗，你才能變得比以前更強大。」在文章中看到老師的這些話，彷彿就是在對我說。自己反思過去的求學經歷，確實每次遇到問題都在逃避，害怕自己做不好而不敢挑戰，往往選擇最輕鬆的捷徑。不要害怕失敗，失敗就從中去吸取經驗，這是我現在需要去學習的事情。

研讀教材啟發

你所不知道的 C 語言：數值系統篇

電腦不只有二進位

這個部分提到了 balance ternary，與一般三進位不同之處在於

a = T (- 1), 0, 1

，其整數與分數的表示法都跟二進位一樣，但在表示一個數的負數時較二進位方便：

二進位

$(6)_{10} = (0110)_{2}$

$(- 6)_{10} = (1010)_{2}$
平衡三進位

$(6)_{10} = (1 T 0)_{b a l 3} = 1 \cdot 3^{2} + (- 1) \cdot 3^{1} + 0$

$(- 6)_{10} = (T 10)_{b a l 3} = (- 1) \cdot 3^{2} + (1) \cdot 3^{1} + 0$

所以在 balanced ternary 中要取一個數的負數，只要將全部的位元乘以

- 1

即可，比二進位的負數操作快速簡單。考慮以下 balanced ternary:

+++-0 = (1 * 3⁴) + (1 * 3³) + (1 * 3²) + (-1 * 3¹) + 0
= 81 + 27 + 9 + -3
= 114

當我們考慮 -114 的表示法時，可以發現:

---+0 = (-1 * 3⁴) + (-1 * 3³) + (-1 * 3²) + (1 * 3¹) + 0
= -81 + -27 + -9 + 3
= -114

也就是把所有的 + 和 - 對調，就不用像在 2 進位表示法中，需要特別考慮 signed 和 unsigned。

balanced ternary 的作用不僅在一致的方式去表達數值，還可用於浮點數。

你所不知道的 C 語言: bitwise 操作

Bitwise Operator

Set a bit :

unsigned char a |= (1 << n);

Clear a bit :

unsigned char b &= ~(1 << n);

Toggle a bit :

unsigned char c ^= (1 << n);

Test a bit :

unsigned char e = d & (1 << n); //d has the byte value.

The right/left most byte:

unsigned char right = val & 0xff; /* right most (least significant) byte */
unsigned char left = (val >> 8) & 0xff; /* left most (most significant) byte */

sign bit:

bool sign = val & 0x8000; // sign bit

並行程式設計: 概念

Concurrency 與 Parallelism

Concurrency 指的是程式架構，將程式拆開成多個可獨立運作的工作，像是驅動程式都可獨立運作，但不需要平行化。
Parallelism 則指程式執行，同時執行多個程式，著重規劃，將能夠並行的程式，分配給不同硬體單元，使其同時執行。

並行程式設計: Atomics 操作

_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

Futex 可用於實作使用者空間之同步機制，如 mutex、condition variable 等介面都可以藉此實作。

在多個臨界區段 (critical section，簡稱 CS) 之間，使用 mutex 保證互斥性，但無法滿足不同臨界區段之間的前後順序，因此可使條件變數（condition variable，簡稱 condvar 或 cond） 在一個臨界區段 A 中等待另一臨界區段 B 的訊號 (signal)。

condvar 不僅是互斥的同步機制，還要一種方式等待其他執行緒進行某些操作。當我們需要在臨界區段 A 中等待臨界區段 B 先完成某些操作時，可用 condvar。

事件驅動伺服器：原理和實例

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。
I/O multiplexing 的好處是，只用單一執行緒即可「同時處理」多個網路連接的 I/O
Asynchronous I/O

Reactor Pattern

同步的事件循環搭配 non-blocking I/O 又稱為 Reactor pattern

Image Not Showing Possible Reasons

The image was uploaded to a note which you don't have access to
The note which the image was originally uploaded to has been deleted

Learn More →

Reactor pattern 是個設計模式 (design pattern)，針對同時處理多個貨單個服務需求。服務處理任務 (service handler) 將傳入的需求拆解，然後分派給相關的請求端處理任務 (request handler)。

Edge vs. Level Triggering

epoll 的兩種工作模式談起:

Edge Triggered (ET, 邊緣觸發)
Level Triggered (LT, 條件觸發)

ET 表示在狀態改變時才通知 (例如: 在邊緣上從低電位到高電位)，LT 表示在這個狀態才通知 (例如: 只要處於低電位就通知)。對應到 epoll，ET 指一旦有心資料就通知 (狀態的改變)，而 LT 是「只要有新資料」就會持續通知，直到緩衝區的資料全數取出。

以 sendfile 和 splice 系統呼叫達到 Zero-Copy

sendfile 系統呼叫的提出，就是克服上述問題，取代 read/write 兩個操作，並減少 context switch 和資料複製的次數:

sendfile(socket, file, len);

簡述想投入的專案

高效網頁伺服器

探討從無到有打造 Linux 平台的高效能網頁伺服器，涵蓋是否該將伺服器實作於 Linux 核心內部、並行處理、I/O 模型、epoll、Reactor pattern，和 Web 伺服器在事件驅動架構的考量。

需要研讀的一些教材:
Linux 核心設計: 針對事件驅動的 I/O 模型演化
 並行程式設計: 排程器原理
 ktcp

開發加速 LLaMA 的 Linux 核心模組

瀏覽今年的期末專案有看到有同學被指派這個題目，我們實驗室本身的研究是對話系統相關的領域，所以 LLaMA 這個大型語言模型在之後的論文或許有機會被應用，因次對這個題目感興趣。

並行程式設計

回顧〈並行和多執行緒程式設計〉教材和相關測驗題，強化對延伸問題的掌握

並行的單向鏈結串列

#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

Remove A
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