A07: mergesort-concurrent

tags: `sysprog2016`

主講人: jserv / 課程討論區: 2016 年系統軟體課程

Image Not Showing Possible Reasons

The image file may be corrupted
The server hosting the image is unavailable
The image path is incorrect
The image format is not supported

Learn More →

返回「進階電腦系統理論與實作」課程進度表

預期目標

作為 concurrency 的展示案例
學習 POSIX Thread Programming，特別是 synchronization object
為日後效能分析和 scalability 研究建構基礎建設
學習程式品質分析和相關的開發工具

案例分析: mergesort-concurrent (對單向 Linked List)

兩大重點:

排序的對象是 singly-linked list
利用 POSIX Thread 處理，需要一併操作 synchronization object

取得程式碼並測試:

$ git clone https://github.com/sysprog21/mergesort-concurrent
$ cd mergesort-concurrent
$ make
$ ./sort

程式輸出，提示以下用法:

usage: ./sort [thread_count] [input_count]

比方說 ./sort 4 8，執行後會看到 "input unsorted data line-by-line" 提示訊息，請輸入 8 組數字，每個都用 Enter (換行) 分隔。之後即可看到輸出。

在 GNU bash 中，可善用 $RANDOM 環境變數，取得介於 0~32767 之間的亂數，於是我們可透過以下指令來作自動測試:

$ (for i in {1..8}; do echo $RANDOM; done) | ./sort 4 8

輸出的 "sorted results" 訊息後方應該有 8 組數值，由小到大排列。

延伸閱讀: 第十章、認識與學習BASH，《鳥哥的 Linux 私房菜》

manager-worker 架構

示意圖如下：

為了分配工作，在 worker thread 實作 Task 的機制。每個主要的操作會先被放進 task queue 裡頭，空閒的 thread 再從 task queue 裡頭提取 task 執行，如下面的步驟:

只要把我們的操作寫成 task，就能順利執行。

Linked List

Linked list 是由各個 node，透過指標串聯而成。先定義 node_t 型別

typedef intptr_t val_t; /* 不僅可放數值，也能放指標 */
typedef struct node {
    val_t data; /* 欲儲存的資料 */
    struct node *next; /* next 指標 */
} node_t;

node 建立後，就可繼續定義 llist_t:

typedef struct llist {
    node_t *head;
    uint32_t size;
} llist_t;

定義完型別，接著是各種操作:














// 建立新的 list 物件
llist_t *list_new();

// 從 list 插入給定資料
int list_add(llist_t *the_list, val_t val);

// 逐一印列 list 內容
void list_print(llist_t *the_list);

// 產生新的節點
node_t *new_node(val_t val, node_t *next);

// 取得某個 index 的節點資訊
node_t *list_get(llist_t *the_list, uint32_t index);

Thread pool

定義 task_t 來封裝 task:

typedef struct _task {
    void (*func)(void *); /* 對應到最終執行的函式 */
    void *arg; /* 傳入的參數 */
    struct _task *next, *last;
    /* 因為 queue 要用 doubly-linked list，
       需要儲存 next 和 last */
} task_t;

定義Task的free操作

int task_free(task_t *the_task);

再來是 thread pool 所需的 queue 結構:

typedef struct {
    task_t *head, *tail;
    pthread_mutex_t mutex;
    pthread_cond_t cond;
    uint32_t size;
} tqueue_t;

int tqueue_init(tqueue_t *the_queue);
task_t *tqueue_pop(tqueue_t *the_queue);
uint32_t tqueue_size(tqueue_t *the_queue);
int tqueue_push(tqueue_t *the_queue, task_t *task);
int tqueue_free(tqueue_t *the_queue);

接著把 queue 和 thread 包裝成 thread pool:

typedef struct {
    pthread_t *threads;
    uint32_t count;
    tqueue_t *queue;
} tpool_t;

int tpool_init(tpool_t *the_pool, uint32_t count,
               void *(*func)(void *));
int tpool_free(tpool_t *the_pool);

之後實做task_run 作為稍早提到流程圖的主迴圈 (main-loop)

void *task_run(void *data)
{
    task_t *cur_task = NULL;
    while (1) {
        cur_task = tqueue_pop(pool->queue);
        if (cur_task){
            if (!cur_task->func) {
                tqueue_push(pool->queue, cur_task);
                break;
            } else{
                curTask->func(cur_task->arg);
                task_free(cur_task);
            }
        }
    }
    pthread_exit(NULL);
}

有了這樣的基礎建設，我們的 mergesort 就很容易透過 task 這樣的包裝，加入 thread pool 中。前述程式碼已經用到物件導向的設計模式，可見你所不知道的C語言：物件導向程式設計篇。

分析 mutex contention

mutrace 可用來偵測 lock contention，使用很方便，不需要重新編譯程式碼。

$ sudo apt-get install mutrace

搭配前述亂數輸入自動測試，執行以下命令:

$ (for i in {1..8}; do echo $RANDOM; done) | mutrace ./sort 4 8

mutrace 的輸出:

mutrace: Showing statistics for process sort (pid 8978).
mutrace: 3 mutexes used.

Mutex #0 (0x0x559cfdae59b0) first referenced by:
	/usr/lib/mutrace/libmutrace.so(pthread_mutex_init+0xec) [0x7f8d7fc3862c]
	./sort(tqueue_init+0x38) [0x559cfc426315]
	./sort(tpool_init+0x6a) [0x559cfc42656a]
	./sort(main+0x16b) [0x559cfc426d32]
	/lib/x86_64-linux-gnu/libc.so.6(__libc_start_main+0xf1) [0x7f8d7f6703f1]

Mutex #1 (0x0x7f8d7d23f380) first referenced by:

Mutex #2 (0x0x559cfc6280a0) first referenced by:
	/usr/lib/mutrace/libmutrace.so(pthread_mutex_init+0xec) [0x7f8d7fc3862c]
	./sort(main+0x125) [0x559cfc426cec]
	/lib/x86_64-linux-gnu/libc.so.6(__libc_start_main+0xf1) [0x7f8d7f6703f1]

mutrace: Showing 3 most contended mutexes:

其中 tqueue_init+0x38 就是實際執行的地址，可用 addr2line 來找出對原始程式碼的對應，注意，要確保編譯時加入 -g 參數，確保包含 debug info 的執行檔正確產生。以這個地址來說，對應的原始程式碼為:

$ addr2line -e sort 0x38
mergesort-concurrent/main.c:167

GraphViz

[ source ] Graphviz 是個依據給定指令的製圖軟體，不過說是繪圖軟體，它能繪的圖並不是一般人想像中的漫畫或 logo，而是數學意義上的 "graph"，比較通俗的說法就是「關係圖」。

舉例來說，像是下面這種圖，展示 Unix 家族：

用手畫會很痛苦，而 Graphviz 可以替使用者搞定它。Graphviz 提供一套語言，讓您能直接陳述圖片上的節點、邊、方向等性質。之後，由它來為您產生整張圖片。

Graphviz 能畫的圖片有許多種，可在官方網站找到更多範例。

HackMD 已經支援 GraphViz，本頁 mergesort 的圖例就是用該工具繪製。按右上方之後再按左上方，查看 GraphViz 的使用。

Git Hooks

[ source ] Git 和其他版本控制系統一樣，可在某些重要事件發生時，自動觸發自訂腳本。Git hook 可分客戶端和伺服器端，這邊我們只解說客戶端 hooks 如何自動化工作流程。

每個 Git repository 中都有一個 .git/hooks 目錄，裡面的內容如下：

applypatch-msg.sample  pre-applypatch.sample      pre-push.sample
commit-msg.sample      pre-commit.sample          pre-rebase.sample
post-update.sample     prepare-commit-msg.sample  update.sample

這是 Git 提供給我們的 sample script，讓我們參考用的，script 的檔名就是對應的事件，這邊有一份完整可以使用的事件 list。

如果我們想要安裝一個 hook，在每次 commit 前讓他自動執行某個腳本，就在這個目錄中，新增一個名為 pre-commit 的 script file（注意沒有副檔名，檔案要設為可執行），這樣在 commit 前就會自動執行這個腳本。

pre-commit 大概是最多人使用的 hook，他可以讓我們在 commit 前對我們的修正做些檢查，例如用靜態分析工具 (如jshint）先行掃描，以便確保程式的品質。

延伸閱讀: Customizing Git - Git Hooks

mergesort-concurrent 提供一份特製的 Git pre-commit hook，可在每次提交修改時，自動檢查程式排版風格是否一致，並且檢驗 C 語言程式是否存在潛在的錯誤。使用前，記得先安裝 astyle 和 cppcheck 套件:

$ sudo apt-get install astyle cppcheck

之後只要在 mergesort-concurrent 所在的目錄執行以下指令即可安裝特製的 Git hooks:

$ scripts/install-git-hooks

接著我們來測試。在 thread.c 中有一段程式碼:

int task_free(task_t *the_task)
{
    free(the_task->arg);
    free(the_task);
    return 0;
}

如果我們在 free(the_task); 後面追加一行一樣的敘述，也就是重複呼叫 free()，這就會導致 double free。當我們貿然將這樣的程式碼提交給 Git 時，特製的 Git pre-commit hook 就會偵測並回報給我們：

$ git commit -a
[thread.c:7]: (error) Memory pointed to by 'the_task' is freed twice.

Fail to pass static analysis.

關於指標的注意須知，可參考你所不知道的C語言：指標篇。類似 cppcheck 的靜態分析工具很多，像是 Clang Static Analyzer。

UNIX 指令組合的魔法

phonebook-concurrent 裡頭的 dictionary/words.txt 複製出來，然後透過 UNIX 指令打亂順序，之後重新導向到另一個檔案

$ uniq words.txt | sort -R > input.txt

這樣我們就有新的資料輸入。

作業要求

將 merge sort 的實做改為可接受 phonebook-concurrent 的 35 萬筆資料輸入的資料檔
- 字典檔資料需要事先用 sort -R 處理過
- 思考如何得到均勻分佈的亂數排列，並且設計自動測試的機制
研究 thread pool 管理 worker thread 的實做，提出實做層面的不足，並且參照 concurrent-ll，提出 lock-free 的實做
學習 concurrent-ll (concurrent linked-list 實作) 的 scalability 分析方式，透過 gnuplot 製圖比較 merge sort 在不同執行緒數量操作的效能
- 注意到 linked list 每個節點配置的記憶體往往是不連續，思考這對效能分析的影響
一併嘗試重構 (refactor) 給定的程式碼，使得程式更容易閱讀和維護。延續 A05: introspect，不只是在共筆上用文字提出良性詳盡的批評，也該反映在程式碼的變革
共筆的內容儘量用 GraphViz 製作
截止日期：
- 08:00AM Oct 7, 2016 (含) 之前
- 越早在 GitHub 上有動態、越早接受 code review，評分越高

挑戰題

引入 C11 本身的 thread.h 實作多執行並用 _Atomic 改寫。參考資料: