2018q1 第 11 週測驗題 (下)
測驗 1
考慮以下 C 程式:
這是個目標能在多執行緒環境運作的 singly-linked list 實作,我們忽略新增節點的函式,並且聚焦在 delete
函式,後者的作用是從 linked list 中移除某個數值,演算法如下:
- first search the list starting at ListHead (which itself is never removed) until the desired node is found.
- To protect this search from the effects of concurrent deletions, lock each node before any of its contents are accessed.
- Because all searches start at ListHead, there is never a deadlock because the locks are always taken in list order.
- When the desired node is found, lock both the node and its predecessor since the change involves both nodes.
- Because the predecessor's lock is always taken first, you are again protected from deadlock.
指出這個函式是否能符合演算法一般的運作,在下方挑出最接近的描述選項。
作答區
K = ?
(a)
可以運作,一看就知道是「慣 C」上乘之作;
(b)
無法運作,應該在第 25 行後補上 pthread_mutex_unlock(¤t->lock);
(c)
無法運作,應該將第 23 行換成 pthread_mutex_unlock(¤t->lock);
(d)
無法運作,應該在第 19 行後補上 pthread_mutex_unlock(¤t->lock); pthread_mutex_unlock(&prev->lock);
(e)
無法運作,應該在第 19 行後補上 pthread_mutex_unlock(¤t->lock);
參考資訊:
延伸問題:
- 為何需要兩個 mutex lock 呢?在 Linux 核心原始程式碼舉出類似用法的程式碼並解說;
- Recursive lock 又是怎麼一回事呢?舉出實際案例並給予充份的測試