# 2018q1 第 11 週測驗題 (下)

### 測驗 `1`

考慮以下 C 程式:

#include <pthread.h>

typedef struct node {
    int val;
    struct node *link;
    pthread_mutex_t lock;
} node_t;

node_t ListHead = { .val = 0 };

node_t *node_delete(int val) {
    node_t *prev, *current;
    prev = &ListHead;

    pthread_mutex_lock(&prev->lock);
    while ((current = prev->link)) {
        pthread_mutex_lock(&current->lock);
        if (current->val == val) {
            prev->link = current->link;
            current->link = NULL;
            return current;
        }
        pthread_mutex_unlock(&prev->lock);
        prev = current;
    }
    pthread_mutex_unlock(&prev->lock);
    return NULL;
}

這是個目標能在多執行緒環境運作的 singly-linked list 實作，我們忽略新增節點的函式，並且聚焦在 `delete` 函式，後者的作用是從 linked list 中移除某個數值，演算法如下：
1. first search the list starting at ListHead (which itself is never removed) until the desired node is found.
2. To protect this search from the effects of concurrent deletions, lock each node before any of its contents are accessed.
3. Because all searches start at ListHead, there is never a deadlock because the locks are always taken in list order.
4. When the desired node is found, lock both the node and its predecessor since the change involves both nodes.
5. Because the predecessor's lock is always taken first, you are again protected from deadlock.

指出這個函式是否能符合演算法一般的運作，在下方挑出最接近的描述選項。

==作答區==

K = ?
* `(a)` 可以運作，一看就知道是「慣 C」上乘之作;
* `(b)` 無法運作，應該在第 25 行後補上 `pthread_mutex_unlock(&current->lock);`
* `(c)` 無法運作，應該將第 23 行換成 `pthread_mutex_unlock(&current->lock);`
* `(d)` 無法運作，應該在第 19 行後補上 `pthread_mutex_unlock(&current->lock); pthread_mutex_unlock(&prev->lock);`
* `(e)` 無法運作，應該在第 19 行後補上 `pthread_mutex_unlock(&current->lock);`

參考資訊:
* [why does POSIX have recursive mutexes? Because of a dare.](https://www.reddit.com/r/programming/comments/qrju5/why_does_posix_have_recursive_mutexes_because_of/)
* [Linus Torvalds 談論 recursive mutex](http://yarchive.net/comp/linux/recursive_locks.html)

:::success
延伸問題:
1. 為何需要兩個 mutex lock 呢？在 Linux 核心原始程式碼舉出類似用法的程式碼並解說;
2. Recursive lock 又是怎麼一回事呢？舉出實際案例並給予充份的測試
:::