# 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 的實例如下: ```c 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,考慮以下程式碼: ```c // 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)
×
Sign in
Email
Password
Forgot password
or
By clicking below, you agree to our
terms of service
.
Sign in via Facebook
Sign in via Twitter
Sign in via GitHub
Sign in via Dropbox
Sign in with Wallet
Wallet (
)
Connect another wallet
New to HackMD?
Sign up