課堂問答簡記
請填入你的 GitHub 帳號名稱
Reader and Writer problem
C11 - Atomic operations library
並行和多執行緒程式設計 (6)
std::string
中的CoW一提。針對技術用語時,不要查閱 Wikipedia 中文詞目,並且該以詞目的源頭資訊為主,即 Concurrency Modifications to Basic String
1
一個會自動擴展記憶體空間的容器,類似 C++ std::vector,不過沒有做記憶體的自動釋放。
size 小於 capacity 的四分之一時,讓 capacity 減半或者直接變為四分之一;如果變為二分之一時即進行釋放,會導致連續執行放入與移除元素時,一直進行記憶體配置,導致效能低落。
v(int, 2, vec2, 13, 42);
是如何給予不同數量的初始元素?數量過多時會有問題嗎?這邊使用到不定參數,如果數量過多時,array 的 brace-enclosed lists,在編譯時期就會報錯。
NEXT_POWER_OF_2(s)
的作用?找到下一個大於等於 s 且為二的冪的數字,這邊不需要用分支,可透過 ((size_t) 1 << (64 - __builtin_clzl(s - 1))
運算,這邊用到 gnu extension __builtin_clzl
,傳入 0 為非定義行為;
注意到 s
為 0 時會得到非預期結果,而 1 時結果為未定義,如果需要用到,還需額外判斷。
_Static_assert(s <= 8, "it is too big");
的功能?_Static_assert 在編譯時期確保某些條件為真,s
需為編譯時期可知的常數。
2
for (;;)
看起來像無限迴圈,為何可以正常運作?cr_wait
為 marco,當中有 return;
,語意為,當等待條件不成立時,函數就直接返回;因此這邊的問題,也可單純從佇列的語意進行回答。
Producer–consumer problem 為了解決 multi-process synchronization 的問題
web sever 去描述 comsumer producer
How can a web server handle multiple user's imcoming request -以選課系統為例
文章提到TPC 可以獨立紀錄每個 connection
另外或許可以利用 threads 來處理,若 thread 看到 request 就把課程用 lock 鎖起來,餘額-1
example for unbounded buffer producer consumer problem
網頁伺服器作為示範,HTTP request vs. response
解釋 Edge Triggered (ET, 邊緣觸發) 與 Level Triggered (LT, 條件觸發)
trigger (觸發) : 使一個事件開始執行
在電路中,電位的轉換並不是發生在一瞬間而是需要一段時間,而這段時間稱為 Propagation delay
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-φ) 取代 φ,透過減小乘數的方式加速。
講解一下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 由 8 位元來表示。
在沒有最佳化的狀況下,建立 Process 的成本較高
Process 會有獨立的定址空間 (address space),而 Thread 間共享定址空間。
根據 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 的差異