# 2024q1 Homework5
contributed by < `yqt2000` >
## 閱讀〈因為自動飲料機而延畢的那一年〉的啟發

## 研讀教材啟發
::: info
在研讀[你所不知道的 C 語言：數值系統](https://hackmd.io/@sysprog/c-numerics)對於其中的這句話有所疑問。

"當我們計算 $log_{2}N$ (以 2 為底的對數) 時, 其實只要算高位有幾個 0's bits. 再用 31 減掉即可。"

假設取 N = 7 則 $log_{2}7$ = 2.807XXXX...
$7_{(10)}$ = 0x00000007 => 31 - 高位有 29 個 0's bits = 2

N = 29, $log_{2}29$ = 4.857XXXX...
$29_{(10)}$ = 0x0000001d => 31 - 高位有 27 個 0's bits = 4

所以單純是指整數部分

:::

### 研讀[並行程式設計](https://hackmd.io/@sysprog/concurrency/)，紀錄見解及疑惑

#### [事件驅動伺服器：原理和實例](https://hackmd.io/@sysprog/event-driven-server)
::: info
其中提到的名詞
1. 核心`fd`: file descriptor縮寫

2. `fcntl`: performs one of the operations described below on the open file descriptor fd. 參照[fcntl(2) — Linux manual page](https://man7.org/linux/man-pages/man2/fcntl.2.html)

3. 高效伺服器的實作 [lwan](https://github.com/lpereira/lwan)，在 [lwan-readahead.c](https://github.com/lpereira/lwan/blob/f51cd6cc6f929107c283ec3dfda9bab431a14d87/src/lib/lwan-readahead.c#L120) 中前見運用 non-blocking IO 的實例如下:

while (true) {
    struct lwan_readahead_cmd cmd[16];
    ssize_t n_bytes = read(readahead_pipe_fd[0], cmd, sizeof(cmd));
    ssize_t cmds;

    if (UNLIKELY(n_bytes < 0)) {
        if (errno == EAGAIN || errno == EINTR)
            continue;
        lwan_status_perror("Ignoring error while reading from pipe (%d)",
                           readahead_pipe_fd[0]);
        continue;
#if PIPE_DIRECT_FLAG
    } else if (UNLIKELY(n_bytes % (ssize_t)sizeof(cmd[0]))) {
        lwan_status_warning("Ignoring readahead packet read of %zd bytes",
                            n_bytes);
        continue;
#endif
    }

參照[errno(3) — Linux manual page](https://man7.org/linux/man-pages/man3/errno.3.html)，其中 errno == EAGAIN 和 errno == EINTR 代表意義如下
EAGAIN: Resource temporarily unavailable (POSIX.1-2001).
EWOULDBLOCK: Operation would block
EINTR: Interrupted function call (POSIX.1-2001);
:::

### [並行程式設計: Atomics 操作](https://hackmd.io/@sysprog/concurrency/%2F%40sysprog%2Fconcurrency-atomics#Atomic-%E6%93%8D%E4%BD%9C%EF%BC%9A%E9%9D%9E%E9%98%BB%E5%A1%9E%E5%BC%8F%E5%90%8C%E6%AD%A5%E7%9A%84%E5%9F%BA%E7%9F%B3)

在設計並形程式實驗時，因攸關記憶體操作(存取快取)，在建立成員變數時就應注意 cacheline size 等細節。

#### Memory Barriers
out-of-order execution 在單一處理器，不考慮編譯器優化，多執行緒執行不存在記憶體亂序存取的議題。然而考慮多核處理器在 store buffer 以及 invalid queue 的架構上運行多執行緒程式，即須考慮記憶體亂序存取的議題

在實作層面可以藉由 memory barrier 來約束與 store buffer 和 invalidate queue，考慮以下程式碼:

// cpu0, cpu1 共享變數 a, b，
// foo 負責寫，bar 則是等 b 被更新為 1 後，想要 a 是被正確更新為 1。 

void foo() // cpu0 執行此程式
{ 
    a = 1;
    // 寫入 a 後，應確保 cpu0 store buffer 有更新 a=1 至 cpu0 cache
    smp_mb();    
    b = 1;
}
void bar() // cpu1 執行此程式 
{
    while(b == 0) 
        continue;
    // 讀取 a 前，應確認 cpu1 invalid queue 已處理完畢，
    // 確保存取 a 的值前是否有 invalid a 尚未處理。
    smp_mb(); 
    assert(a == 1);
}

為了約束 store buffer 和 invalidate queue，當 CPU 執行指令中如果遇到 `smp_mb`，則需要處理 store buffer 和 invalidate queue。 於是寫軟體的人在需要的時候可以用 memory barrier 確保關鍵的資料有依正確的順序更新 (無法保證更新的時間)。CPU 在多數情況下仍能避免閒置。到此可理解為何這二種操作搭配，較符合現代處理器架構：
* 一個執行緒「先 write X，後執行 write memory barrier」
* 另一個執行緒「先執行 read memory barrier，後 read X」

二者合起來構成 happens-before 關係。

但其實從程式碼來看，`foo( )` 中的 `smp_mb` 其實只需要處理 store buffer 的部分，而 `bar( )` 中的則只需要處理 invalidate queue ，顯然只處理其中之一肯定比同時處理二者效率要高。因此硬體設計者在設計 CPU 時，進一步`smp_mb`，細分為以下:
1. read memory barrier => 只處理 invalidate queue
2. write memory barrier => 只處理 store buffer

不過約束更少，取而代之的可能的行為也就越多。

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

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

3. 開發用以加速 LLaMA 的 Linux 核心模組
實驗室是作自然語言處理相關的，LLaMa 作為近期熱門的模型，想再多了解題目的細節是甚麼。

TODO: 高效網頁伺服器 (針對靜態) https://hackmd.io/@sysprog/linux2024-ktcp

開發紀錄：[Linux 核心專題: 高效網頁伺服器(靜態)](https://hackmd.io/@Brandon2000/HkUVkANVR)