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

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 語言：遞迴呼叫篇

字串反轉

其中提到的 in-place string reverse 想法：一直 swap '\0'之前的character 。但在描述演算法處，在把頭尾互換之後，需要再把尾端和 '\0' 互換，重複以上步驟直到 '\0' 至於字串的中間，這裡不太理解的是為什麼不能直接互換頭尾，直到頭端位置大於等於尾端，為什麼要去動到 '\0' ？

你所不知道的 C 語言：技巧篇

善用 GNU extension 的 typeof
在巨集中，因為無法知道參數的型態，所以運用 typeof 去宣告變數會是一個很好的手法。

第 4 週

你所不知道的 C 語言：編譯器和最佳化原理篇

Pointer Aliasing

void foo(int *i1, int *i2, int *res)
{
    for (int i = 0; i < 10; i++) {
        *res += *i1 + *i2;
    }
}

如果改成下面這種形式，則可以減少在每次迴圈時需要先將 i1 和 i2 相加步驟。

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 ⟹ - x < - y (F a l s e)$
若
$x$ 為 int_max 而
$y$ 為 int_min 則
$x > y$ 成立。
此時
$- x =$ 1_0000…_0001 而
$- y =$ 1_0000…_0000 則應為
$- x > - y$ 。
故上述條件式為
$(F a l s e)$ 。

想投入的專案

實作高效記憶體配置器
排程器 / 並行

期末專題

期末專題

TODO: 閱讀並行程式設計: 實作輕量級的 Mutex Lock 並重現實驗，紀錄問題

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 內建網頁伺服器: 單工 (執行路徑明確)