Linux 核心專題: 並行程式設計

執行人: WeiHongWi

:question: 提問清單

• ?

任務簡述

回顧〈並行和多執行緒程式設計〉教材，以課程測驗題給定的並行程式碼為基礎，著手改進，並確保以 C11 Atomics 撰寫出正確且有效的程式碼，所有程式碼應當通過 Thread Sanitizer 的執行時期檢測。

TODO: Concurrent Hashtable

重做第 12 週測驗題，包含延伸問題。

用 C11 atomics 改寫

解讀 bsd_queue.c

裡頭包含 4 個資料結構 , 有 singly-linked list 和 tail singly-linked list , queue , tail queue,在 hashtable 裡用到的是 double linked tail queue , 這裡就介紹 function

TAILQ_ENTRY 和 TAILQ_HEAD

TAILQ_FOREACH_SAFE

TAILQ_REMOVE

解讀 hashtable.c

第一個資料結構為 ht_item_t , 其中包含 key 和 value 以及長度 , 且這些 item 用一個 double linked tail queue 去做連接.如以下程式碼:

typedef struct _ht_item {
    uint32_t hash;
    char kbuf[32];
    void *key;
    size_t klen;
    void *data;
    size_t dlen;
    TAILQ_ENTRY(_ht_item) next;
} ht_item_t;

第二個資料結構為 ht_items_list_t , 其中包含了 spinlock 和 ht_item_t 的 double linked tail queue , 另外也用 double linked tail queue 來連接其他的 ht_item_list. 如以下程式碼:

typedef struct _ht_item_list {
    TAILQ_HEAD(, _ht_item) head;
    pthread_spinlock_t lock;
    size_t index;
    TAILQ_ENTRY(_ht_item_list) iterator_next;
} ht_items_list_t;

第三個資料結構則為 hashtable_t , 其中也用 mutex 去避免競爭 hash table 的問題,加上前面提到屬於 struct ht_item_list 的 spinlock ,關於如何使用這兩個 lock 來達到並行, 我用 ht_clear() 這個函式做範例:

void ht_clear(hashtable_t *table)
{
    ...
    MUTEX_LOCK(table->iterator_lock);
    ...
    TAILQ_FOREACH_SAFE(list, &table->iterator_list->head, iterator_next,
                       tmplist)
    {
        SPIN_LOCK(list->lock);

        ht_item_t *item = NULL;
        ht_item_t *tmp;

        TAILQ_FOREACH_SAFE(item, &list->head, next, tmp)
        {
            ...
        }

        ...
        SPIN_UNLOCK(list->lock);
        SPIN_DESTROY(list->lock);
        free(list);
    }
    MUTEX_UNLOCK(table->iterator_lock);

    ATOMIC_CAS(table->status, HT_STATUS_CLEAR, HT_STATUS_IDLE);
}

在第 6 和第 14 行的 TAILQ_FOREACH_SAFE() 用來走訪整個 double linked tail queue

第一個搜尋屬於 struct ht_iterator_list 的 TAILQ ,在搜尋前用 MUTEX_LOCK()讓其他 thread 的競爭者無法使用

第二個搜尋屬於 struct ht_items_list 的 TAILQ , 在搜尋前用 SPIN_LOCK()讓其他 thread 的競爭者無法使用.

ht_init 和 PRNG 改寫

ht_grow_table() 和 internal preallocated bufferpool 改寫

TODO: MPMC

重做第 9 週測驗題的測驗一，包含延伸問題。