# 2021q1 Week5/6/8/9

:::warning
課堂問答簡記
請填入你的 GitHub 帳號名稱
:::

## linD026
> [**3/23 code review**](https://hackmd.io/@linD026/note#0323---code-review)

* [hash table](https://en.wikipedia.org/wiki/Hash_table)
* [碰撞處理](https://en.wikipedia.org/wiki/Hash_table#Collision_resolution)：Separate chaining 和 Open addressing
* [concurrent hash table](https://en.wikipedia.org/wiki/Concurrent_hash_table)
* 在多執行緒下，保持資料正確性的調整
* 執行順序
* 函式結構
* 資料儲存結構
> [Reader and Writer problem](https://github.com/angrave/SystemProgramming/wiki/Synchronization%2C-Part-7%3A-The-Reader-Writer-Problem)
> [C11 - Atomic operations library](https://en.cppreference.com/w/c/atomic)
> [並行和多執行緒程式設計 (6)](https://www.youtube.com/watch?v=6LnGZ_1MfDo&list=WL)
* 空間效率的最佳化
* [Copy on write](https://en.wikipedia.org/wiki/Copy-on-write)
* xs ( fbstring )

:question: 關於維基百科的 [寫入時複製](https://zh.wikipedia.org/wiki/%E5%AF%AB%E5%85%A5%E6%99%82%E8%A4%87%E8%A3%BD) 對 C++11 為了提高並列性取消 `std::string` 中的CoW一提。
請問為什麼要提高並行度？應該說，並行度有什麼重要性質需要取消 CoW 這個能對空間使用效率提高的機制。
> 針對技術用語時，**不要**查閱 Wikipedia 中文詞目，並且該以詞目的源頭資訊為主，即 [Concurrency Modifications to Basic String](http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2008/n2534.html)

## XDEv11

> **[quiz5](https://hackmd.io/@sysprog/linux2021-quiz5)**

### 測驗 `1`

#### vector 功能是什麼？
一個會自動擴展記憶體空間的容器，類似 C++ std::vector，不過沒有做記憶體的自動釋放。

#### 記憶體要釋放的話，要如何做？
size 小於 capacity 的四分之一時，讓 capacity 減半或者直接變為四分之一；如果變為二分之一時即進行釋放，會導致連續執行放入與移除元素時，一直進行記憶體配置，導致效能低落。

#### `v(int, 2, vec2, 13, 42);` 是如何給予不同數量的初始元素？數量過多時會有問題嗎？
這邊使用到[不定參數](https://en.cppreference.com/w/c/language/variadic)，如果數量過多時，array 的 brace-enclosed lists，在編譯時期就會報錯。

#### `NEXT_POWER_OF_2(s)` 的作用？
找到下一個大於等於 s 且為二的冪的數字，這邊不需要用分支，可透過 `((size_t) 1 << (64 - __builtin_clzl(s - 1))` 運算，這邊用到 gnu extension [`__builtin_clzl`](https://gcc.gnu.org/onlinedocs/gcc/Other-Builtins.html)，傳入 0 為非定義行為；
注意到 `s` 為 0 時會得到非預期結果，而 1 時結果為未定義，如果需要用到，還需額外判斷。

#### `_Static_assert(s <= 8, "it is too big");` 的功能？
[_Static_assert](https://en.cppreference.com/w/c/language/_Static_assert) 在編譯時期確保某些條件為真，`s` 需為編譯時期可知的常數。

### 測驗 `2`

#### `for (;;)` 看起來像無限迴圈，為何可以正常運作？
`cr_wait` 為 marco，當中有 `return;`，語意為，當等待條件不成立時，函數就直接返回；因此這邊的問題，也可單純從佇列的語意進行回答。

---

## jonathanyang0227
[Producer–consumer problem](https://en.wikipedia.org/wiki/Producer%E2%80%93consumer_problem) 為了解決 multi-process synchronization 的問題
* bounded buffer :
* problem: 若 buffer 沒有東西，必須停止 comsumer ，若 buffer 滿了，要停止 producer
* solution: the producer go to sleep or discard data if the buffer is full. The next time the consumer removes an item from the buffer, it notifies the producer, who starts to fill the buffer again.
* unbounded buffer :
* problem : 若 buffer 為空，必須停止 comsumer

web sever 去描述 comsumer producer
* client 發出 request 給 server (producer)
* server 解析 request 並回傳 respond 回 server (comsumer)

[How can a web server handle multiple user's imcoming request](https://stackoverflow.com/questions/16952625/how-can-a-web-server-handle-multiple-users-incoming-requests-at-a-time-on-a-sin) -以選課系統為例
文章提到[TPC](https://en.wikipedia.org/wiki/Transmission_Control_Protocol) 可以獨立紀錄每個 connection
另外或許可以利用 threads 來處理，若 thread 看到 request 就把課程用 lock 鎖起來，餘額-1
## yellow951321
example for unbounded buffer producer consumer problem
> 網頁伺服器作為示範，HTTP request vs. response

* client 為 producer ， server 為 consumer 。 client 不會停止傳輸 request ， 但當沒有 request 時 server 會停止 response 。 符合上述 unbounded buffer 對於 producer 和 consumer 的描述。

## chiehen
解釋 Edge Triggered (ET, 邊緣觸發) 與 Level Triggered (LT, 條件觸發)

trigger (觸發) : 使一個事件開始執行
* 邊緣觸發: 當電位從低電位變為高電位 (正緣觸發) 或電位從高電位變為低電位 (負緣觸發)的瞬間將會觸發事件
* 條件觸發:當電位在特定水平時，會觸發事件，通常會確認此電位有維持一段時間，以避免偵測到不穩定的脈充充（glitch)

在電路中，電位的轉換並不是發生在一瞬間而是需要一段時間，而這段時間稱為 [Propagation delay](https://en.wikipedia.org/wiki/Propagation_delay)

---

## YOYOPIG
[Homework 6 (quiz 6 測驗二)](https://hackmd.io/@sysprog/linux2021-quiz6#%E6%B8%AC%E9%A9%97-2)
* Hash table 實作為何選擇使用 list？
傳統使用一個很大的 2d array 做為 hash table，但這樣的方法對記憶體不友善，使用 list 在需要的時候再 malloc 可避免浪費不必要的空間。

* Collision 發生時的處理方式
在 insertion 時，若發生 collision （原本 list 中已有元素），就將其加入 hash list 的頭部，將原先 list 中的其他元素接在新 node 的後面。同時，透過指標的指標 `pprev` 幫助紀錄起始位置。

* Hash function 的實作方法
將數值乘上一個常數（通常是相當大的數值），保留其高位元，使最後 hash 出來的結果儘量分散，以避免碰撞。

* `GOLDEN_RATIO_32` 的選擇
使用 φ 做為選定的常數，其特性能讓連續數值的 hash 結果儘量分散。Linux kernel 中又進一步使用 (1-φ) 取代 φ，透過減小乘數的方式加速。

---

## WayneLin1992

[Homework6(quiz6 測驗`1`)](https://hackmd.io/@sysprog/linux2021-quiz6#%E6%B8%AC%E9%A9%97-1)

* 講解一下`bn_mul`做了什麼
`UTYPE_TMP intermediate = a->array[i] * (UTYPE_TMP) b->array[j];` 將原本 UTYPE 32 bits 的字串相乘後使用 UTYPE_TMP 64 bits 存取，存入 `intermediate`。

* `bn_from_int` 又做了什麼?
將 `intermediate` 偏移 32 存入 array 當中，這樣會使他有上半跟下半，這樣就能以 32 bits 存去。

* 偏移 32 bits 可能發生什麼問題?
當執行 8 進位時就會出現錯誤，所以要使用不同的偏移量，才能正常執行。

* 我們在什麼情況，需要使用 8 進位表示?
>36 進位比 8 進位更早發展，但為什麼 C 語言卻內建 8 進位， 10 進位是人類的表示方式，但為什麼需要 8 進位

在 file mode 描述 [chmod](https://linux.die.net/man/1/chmod) 由 8 位元來表示。

---

## jhan1998
:question: Process 和 Thread 的差別
* 在沒有最佳化的狀況下，建立 Process 的成本較高

* Process 會有獨立的定址空間 (address space)，而 Thread 間共享定址空間。

* 根據 [What is the difference between scheduling a thread and scheduling a process?](https://www.quora.com/What-is-the-difference-between-scheduling-a-thread-and-scheduling-a-process) 底下的回答，在 linux kernel 底下會被排程的 entity 叫做 task (`task_struct`)，Kernel threads, user threads 和 single threaded processes 會被歸類在此，其中 prcoess 和 thread 會在 task 建立時用不同的 flags 來區分，所以在排程時不同的 flags 就會有不同的排程演算法。

* Thread 之間由於空間是共用的，所以可以利用共用的空間來做 communication 速度也比較快，process 之間由於都是獨立的就要利用一些 system call 做溝通，速度較慢。
> 要討論 signal 對 process vs. thread 的差異

* signal 有其對應的設置，這些設置在 threads 之間是共享的，雖然單一一個 thread 可以設置 signal mask 去阻擋 signals 但當 signals 的設定被改變，這些改變會影響到所有 thread。而 process 可以利用 signal system call 去改變 signal 預設的動作，但不會影響到其他 process。