# 2024q1 Homework5 (assessment) contributed by < `LindaTing0106` > ## 因為自動飲料機而延畢的那一年 看完此篇文章不經讓我思考，其實很多現在在我們日常中隨手可見的物品，一定也是經過前人不斷失敗，再不斷嘗試，最終才成為改善我們生活品質的物品。我想這也恰恰是老師從課程一開始就一直跟我們講的事情：「要誠實面對自己。」，正是因為可以誠實面對自己，才可以坦然接受失敗，再從失敗中改進並且學習。 ## 研讀第 1 到第 6 週「課程教材」和 CS:APP 3/e ### 第 2 週 #### 你所不知道的 C 語言：數值系統 - [ ] DETECT 巨集 提到的 DETECT 巨集，偵測是否有 NULL 。 而在 strlen() ，也有使用到 '\0' 來判斷字串長度。其計算方式是透過迴圈，在指標遇到字元 '\0' 前，將長度 + 1 。但這樣明顯會有時間複雜度為 n 的問題。使用 (((X) - 0x01010101) & ~(X) & 0x80808080) 我們可以直接得到 '\0' 在 X 中的位置。 藉由此例子可以看出懂得運用 bit-wise 可以節省函式所需要的時間。 #### C 語言的 bit-field ```c struct foo { int a : 3; int b : 2; int : 0; /* Force alignment to next boundary */ int c : 4; int d : 3; }; int main() { int i = 0xFFFF; struct foo *f = (struct foo *) &i; printf("a=%d\nb=%d\nc=%d\nd=%d\n", f->a, f->b, f->c, f->d); return 0; } ``` 其中 `int : 0;` 會導致 c 和 d 應該去對齊下一個 4 bytes ，也就導致 c 和 d 不是存取到 i 的地址，而是存取到其他地址，故每次執行時的值也會不一樣。 ### 第 3 週 #### 你所不知道的 C 語言：遞迴呼叫篇 - [ ] [字串反轉](https://hackmd.io/@sysprog/c-recursion#%E6%A1%88%E4%BE%8B%E5%88%86%E6%9E%90%EF%BC%9A%E5%AD%97%E4%B8%B2%E5%8F%8D%E8%BD%89) :::info 其中提到的 in-place string reverse 想法：一直 swap '\0'之前的character 。但在描述演算法處，在把頭尾互換之後，需要再把尾端和 '\0' 互換，重複以上步驟直到 '\0' 至於字串的中間，這裡不太理解的是為什麼不能直接互換頭尾，直到頭端位置大於等於尾端，為什麼要去動到 '\0' ？ ::: #### 你所不知道的 C 語言：技巧篇 - [ ] 善用 GNU extension 的 typeof 在巨集中，因為無法知道參數的型態，所以運用 typeof 去宣告變數會是一個很好的手法。 ### 第 4 週 #### 你所不知道的 C 語言：編譯器和最佳化原理篇 - [ ] Pointer Aliasing ```c void foo(int *i1, int *i2, int *res) { for (int i = 0; i < 10; i++) { *res += *i1 + *i2; } } ``` 如果改成下面這種形式，則可以減少在每次迴圈時需要先將 i1 和 i2 相加步驟。 ```c void foo(int *i1, int *i2, int *res) { int tmp = *i1 + *i2; for (int i = 0; i < 10; i++) { *res += tmp; } } ``` 但若考慮到這樣寫 foo(&var, &var, &var) 來呼叫 foo() ，也就是在傳入的三個參數的地址為一樣的情況下，這兩段程式碼的執行結果則會天差地遠。 先假設 var = 1 - 上方程式碼中 `*res += *i1 + *i2` 後 *res 會等於 3 ，而由於這三個引數的地址相同，則 *i1 和 *i2 的值也會是 3 ，故下一次運算後 *res 則變為 9 ，以此類推。 - 下方程式碼中 `*res += *i1 + *i2` 後 *res 會等於 3 ，而由於這三個引數的地址相同，則 *i1 和 *i2 的值也會是 3 ，但由於 tmp 已經把最一開始 *i1 和 *i2 的值相加並存取下來，故之後每次運算其實只是在對 *res += 2。 由於上述兩種情況對於運算的結果有極大的不同，所以此時編譯器不會對此程式碼做最佳化。 - [ ] [ Page 69 ] > 編譯器可刪去沒在使用的 static global variable 以節省空間，但不能刪去 (目前) 沒在使用的 non-static global variable，因為無法確定其他的 Compilation Unit 是否會用到此變數 > 這是為何建議 local function 要宣告成 static 的用意！ ### CS:APP 第 2 章重點提示和練習 > 算術位移的應用，若要判斷一個 int 型態的變數 n 是否為正數，可用 `n >> 31` 其等價於 `n >=0 ? 0: -1` 這是利用在編譯器中右移往往採用算數位移的關係，將負數向右位移 31 bit 後，即該數變為 $n = 1111...1111$ 或是 $0000...0000$ 。 >若 n 是 32-bit 整數，那麼 `abs(n)` 等同於 `((n >> 31) ^ n) - (n >> 31)` - [ ] Integer C Puzzles $x > y \Longrightarrow -x < -y　(False)$ 若 $x$ 為 int_max 而 $y$ 為 int_min 則 $x > y$ 成立。 此時 $-x =$ 1_0000..._0001 而 $-y =$ 1_0000..._0000 則應為 $-x > -y$ 。 故上述條件式為 $(False)$ 。 ## 想投入的專案 - [ ] 實作高效記憶體配置器 - [ ] 排程器 / 並行 --- ## 期末專題 - [期末專題](https://hackmd.io/@LindaTing/linux2024-final_project) TODO: 閱讀 [並行程式設計: 實作輕量級的 Mutex Lock](https://hackmd.io/@sysprog/concurrency/%2F%40sysprog%2Fconcurrency-mutex) 並重現實驗，紀錄問題 TODO: 閱讀 https://www.doc.ic.ac.uk/~afd/homepages/papers/pdfs/2023/SPIN.pdf | https://github.com/mc-imperial/modelcheckingfutexes 重現實驗 (原本用 C++) 並紀錄問題 TODO: 用 C11 futex 重寫 https://github.com/mc-imperial/modelcheckingfutexes/tree/main/cpp 程式碼 --- ## 與老師一對一約談紀錄 Q : 第三周的字串反轉範例，為什麼一定要和字串結尾的 '\0' 做更改呢？ A : 這是某間公司的面試題目，是為了考驗面試者能不能在 in-place 的限制下，將字串反轉，其實一般字串反轉也不是一定只能這樣實作，但這就只是面試規定。 Q : 在 lab0 中，希望我們將 tic-tac-toe 加入作業中，並且加入 ai vs ai 模式和處理鍵盤事件，我發現許多人都是使用搶占式的方式加入，所以我自己是使用協同式的方式，但結果發現使用協同式會導致每個 task 都需要等待一段時間才會開始工作，所以想問老師這個作業是其實一定要使用搶占式的模式嗎？另外如果使用起來搶占式的運作比較流暢，那為什麼還需要有協同式的存在呢？ A : 此作業的目的在於希望同學可以試著將一段程式加入多工運作，因此只要有加入都可以，但程度較好的同學當然可以在做改進，但至少應該要做到加入多工這件事。另外像 lab0-c 中的網路伺服器則適合使用協同式的方式運作，因為他的執行路徑明確，不會一件事做到一半突然要去做其他事。 preempt (搶佔) lab0-c 內建網頁伺服器: 單工 (執行路徑明確)