changed 8 years ago  
Linked with GitHub

2016q3 Homework3 (mergesort-concurrent)

contributed <shelly4132>

開發環境

  • Ubuntu 16.04 LTS
$ lscpu
  • Architecture: x86_64
  • CPU op-mode(s): 32-bit, 64-bit
  • Byte Order: Little Endian
  • CPU(s): 4
  • Model name: Intel® Core™ i5-4200U CPU @ 1.60GHz
  • L1d cache: 32K
  • L1i cache: 32K
  • L2 cache: 256K
  • L3 cache: 3072K

執行看看

$ make
$ ./sort 4 8
input unsorted data line-by-line
5
2
11
65
1
9
30
0

sorted results:
[0] [1] [2] [5] [9] [11] [30] [65]

後面兩個參數分別填上thread的數量和總共要排序多少數字，輸入完後再將要排序的數字一行一行打上去，最後就會顯示排序好的數列。

如果不想自己手動打的話也可以利用$RANDOM環境變數取得介於 0~32767 之間的亂數。

$ (for i in {1..8}; do echo $RANDOM; done) | ./sort 4 8
input unsorted data line-by-line

sorted results:
[1623] [2036] [3472] [3809] [11126] [23029] [28806] [30389]

理解code

  • task：讓thread知道自己要做什麼





typedef struct _task {
    void (*func)(void *);
    void *arg;
    struct _task *next, *last;
} task_t;
  • queue：裡面放置著等待要被處理的task們






typedef struct {
    task_t *head, *tail;
    pthread_mutex_t mutex;
    pthread_cond_t cond;
    uint32_t size;
} tqueue_t;
  • thread pool：裡面放置了所有thread和job queue





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

指派第一個task並將之放進job queue裡，the_list是前面建好的使用者輸入數列的linked list，而cut_func()就是用來切割數列的。





task_t *_task = (task_t *) malloc(sizeof(task_t));
_task->func = cut_func;
_task->arg = the_list;
tqueue_push(pool->queue, _task);

  • intptr_t：
    可pointer轉換成integer型態，能做位元運算與加減法等等。但如果要做位元運算的話無號的uintptr_t會是比較好的選擇。

  • merge_list()傳入兩個list，然後去比較2個list最小的那個再一一挑出，放到新的list裡面，直到其中一個list的數被挑完，還有數字的list就接到已排序好的list後面。

  • merge_sort()如果傳入的list size小於2直接回傳該list，否則就將他從中間分成2個list之後丟進merge_list()做排序並回傳排序好的list。

  • merge裡面去判斷現在的list總共串了幾個，如果小於輸入的資料數，就繼續做排序串起來，不然就設置終止task然後印出排序好的list。

發現cut_func()跟merge_sort()都是再做切割list，而cut_func裡面判斷cut_count是否小於max_cut其實沒有必要，所以把cut_count等相關變數刪掉，也把merge_sort()刪掉，留下cut_func()就好。

manager-worker 架構

由一個boss thread去接收input並分派task給其他worker thread。

digraph hierarchy {
    nodesep=0.5 // increases the separation between nodes
    node [color=black,fontname=Courier,shape=box] //All nodes will this shape and colour
    edge [color=black, style=dashed] // All the lines look like this
    Manager->{Worker1 Worker2 Worker3}
}

將我們要做的事寫成task，放進job queue裡，空閒的thread會從queue裡拿task出來做。

digraph {
開始Process[shape="box", style=rounded];
是否為結束Task[shape="diamond"];
結束Process[shape="box", style=rounded];
開始Process->提取Task->是否為結束Task
是否為結束Task->重發結束Task[label="是"]
重發結束Task->結束Process
是否為結束Task->執行Task[label="否"]
執行Task->提取Task;
}

去queue裡面提取task。


















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

Verify code

新增一個test_input.c會產生亂數於test_input.txt裡，原本的程式去讀取他後去做merge sort將結果輸出於output.txt中，最後再將output.txt與由output.txtsort完後的sorted.txt去做比較，如果結果都一樣就輸出「Verified OK」。

將輸入改為phonebook的字典檔

  • 將字定義的val_t的型態改為字元陣列
typedef char val_t[16];

  • 使用uniq words.txt | sort -R > words_input.txt讓原本排序好的words.txt順序打亂，變成merge sort新的輸入。

  • 在merge_list()裡的比大小改為用strcmp(a->head->data, b->head->data)的回傳值去做判斷，若前者較大回傳值大於0，等於回傳0，否則回傳負值。

建立checker.c去判斷執行結果對不對









while (fgets(answer, sizeof(answer), fp1) != NULL) {
    fgets(output, sizeof(output), fp2);
    if (strcmp(answer, output) != 0) {
        printf("Wrong Answer!\n");
        return 0;
    }
}
printf("Verified OK\n");
  • 不同thread數目執行時間

Lock Free Thread Pool

參考

Select a repo