片方向リンクリストの入れ子のロック

例 4-4 と例 4-5 で、一度に 3 つのロックを獲得する場合を説明します。この例では、デッドロックを防ぐために規定された順序でロックします。

例 4-4 片方向リンクのリスト構造体

typedef struct node1 {
    int value;
    struct node1 *link;
    pthread_mutex_t lock;
} node1_t;

node1_t ListHead;

この例で使用する片方向リンクのリスト構造体は、各ノードに相互排他ロックを含んでいます。このリストから特定のノードを削除する場合は、最初に ListHead (これが削除されることはない) の位置からリストを辿って目的のノードを探します。

この検索を同時並行的に行われる削除から保護するために、各ノードをロックしてからノードの内容をアクセスしなければなりません。すべての検索が ListHead の位置から開始されるので、常にリストの順序でロックされます。このため、デッドロックは決して発生しません。

目的のノードが見つかった時は、この変更がそのノードと直前のノードの両方に影響を与えるため、両方をロックします。直前のノードのロックが常に最初に獲得されるので、ここでもデッドロックの心配はありません。

例 4-5 は、片方向リンクリストから特定のノードを削除する C コードを示しています。

例 4-5 片方向リンクリストの入れ子のロック

node1_t *delete(int value)
{
    node1_t *prev, *current;

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