# linux2021: tungtylee

## $\beta$ - 1

align_up 程式碼如下：

#include <stdint.h>

static inline uintptr_t align_up(uintptr_t sz, size_t alignment)
{
    uintptr_t mask = alignment - 1;
    if ((alignment & mask) == 0) {  /* power of two? */
        return MMM;       
    }
    return (((sz + mask) / alignment) * alignment);
}

`align_up` 的目的是回傳一個數字，其值大於等於 `sz` 且為 `alignment` 的倍數。我們可以透過如下一步步拆解了解到，為什麼程式碼可以達成如此目的。

核心算式為 Line 9: `(((sz + mask) / alignment) * alignment)`

* `sz / alignment`: 為無條件捨去
* `(sz / alignment) * alignment`: 便為產生小於等於 `sz` 且為 `alignment` 倍數的數字。
* 由於 `sz % alignment != 0` 時， `((sz / alignment) * alignment)` 便會小於 `sz`。我們只要 `sz` 加上`alignment - 1` 便能保證大於 `sz`
* `(((sz + mask) / alignment) * alignment)` 對於 `sz % alignment == 0` 是沒有影響的，因為加上的`mask` 不足 `alignment` 將會被無條件捨去

Line 7: `MMM` 的解說
* `MMM` = `(sz + mask) & ~mask`
* 在 `alignment` 為 2 的指數時 我們可以簡化原本算式，利用位元運算避免乘除法，在大多數的平台上，有可能會有加速的效果。
* Line 6 為何可以偵測 2 的指數？
* 2 的指數在二進位表示法中，只會有一個1
* 二進位數減去一，會需要將二進位表示法中最低位的 1 改成 0 ，並在右方的所有 0 改為 1
* 因此若 `alignment > 1` 且為 $2^i$，其在第 $i$ 個位元是 1 ， 而 `mask` 是在 第 $i-1$ 個 到 第 0 個 位元為 1。所以做完 `&` 必定為零
* 若 `alignment > 1` 且不為 2 的指數，必定有兩個以上的位元為 1 ， 假設最小的 1 在第 $i$ 個位元，次小的在第 $j$ 個位元。 `mask` 會清除掉第 $i$ 個位元，卻保留第 $j$ 個位元。因此進行 `&` 操作後必定大於 $2^j$ 不會為零。
* 一旦確定 `alignment` 是 2 的指數 $2^i$， `mask` 便在第 $i-1$ 個 到 第 0 個 位元為 1。`sz & ~mask` 便等價 `((sz / alignment) * alignment)`
* 由於我們是要大於等於 `sz` 的值，我們就加上 `mask` 即可，因此 `MMM` = `(sz + mask) & ~mask`

## $\gamma$ - 1

如下程式碼，輸出`-`個數為 $NNN * 2^{NNN}$。

#include <stdio.h>
#include <unistd.h>

int main(void)
{
    for (int i = 0; i < NNN; i++) {
        fork();
        printf("-");                         
    }

    fflush(stdout);
    return 0;
}

解說主要原因是：Buffered I/O，若沒有遇到
* $maxlen$
* `EOF`
* `\n`
輸出將不會立刻被輸出，而是有一個指標指出那些已經被處理，而哪些還沒。經由 `fork` 這些資訊也傳給之後的 `process` ，造成先前 `printf` 的 `-` 在子 process 也當未輸出留著。

可由下列過程推理出`-`個數：
* `NNN==1`: 兩個 process 各有一個 `-`
* `NNN==2`: 跑完第一次 Loop 後。兩個 process 再各自產生一個process，因此有 $2^2$ 個 processes。每個 process 有未輸出的 2 個`-`
* `NNN`: 共會有$2^{NNN}$ 個 processes，有未輸出的 `NNN` 個 `-` 。 因此總共$NNN * 2^{NNN}$

## $\delta$ - 1

考慮以下 C11 程式碼，實作並行 (concurrent) 的多個生產者、多個消費者的佇列 (multi-producer, multi-consumer queue)，列表如下: (檔名: `queue.c`)

我的答案如下，但是這個版本有嚴重的問題，一是沒有保證隨時都有 `dummy`，另一個是是無法把所有 POP 都終止掉：

`AAA` = `queue->last->next = node`
`BBB` = `node->value`
`CCC` = `queue->first = new_header`

想改進的部分：
未來我會想要引入 `if` 來處理特殊的狀況。因為 `queue.c` 在建構中，一開始會加入一個 `dummy` ，這讓人很困擾，首先誰要清除這個`dummy` 。 這個 `dummy` 應該要一直留著才對。

在註解中， `con_push` 寫到 `The client is responsible for freeing elementsput`。所以我決定 `con_push` 完全不管 `dummy` 。因此有新的 `node` 會接在 `queue->last->next`。

那就要在 `con_pop` 處理 `dummy` 問題，或是確定`pop_thread` 不會出錯即可。由於 `pop_thread` 會檢查回傳是否為 `NULL` 。 所以我在 `con_pop` 就把 `dummy` 直接回傳。不會有 `dummy` 沒有釋放的問題，但是會造成這個 `queue` 的不一致，有可能有 `dummy`，有可能沒有。