# 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(R) Core(TM) i5-4200U CPU @ 1.60GHz
* L1d cache: 32K
* L1i cache: 32K
* L2 cache: 256K
* L3 cache: 3072K
## 執行看看
* [src](https://github.com/sysprog21/mergesort-concurrent)
```shell
$ 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 之間的亂數。
```shell
$ (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知道自己要做什麼
```clike=
typedef struct _task {
void (*func)(void *);
void *arg;
struct _task *next, *last;
} task_t;
```
* queue：裡面放置著等待要被處理的task們
```clike=
typedef struct {
task_t *head, *tail;
pthread_mutex_t mutex;
pthread_cond_t cond;
uint32_t size;
} tqueue_t;
```
* thread pool：裡面放置了所有thread和job queue
```clike=
typedef struct {
pthread_t *threads;
uint32_t count;
tqueue_t *queue;
} tpool_t;
```
指派第一個task並將之放進job queue裡，`the_list`是前面建好的使用者輸入數列的linked list，而`cut_func()`就是用來切割數列的。
```clike=
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 架構](http://maxim.int.ru/bookshelf/PthreadsProgram/htm/r_19.html)
由一個boss thread去接收input並分派task給其他worker thread。
```graphviz
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出來做。
```graphviz
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。
```clike=
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.txt`sort完後的`sorted.txt`去做比較，如果結果都一樣就輸出「Verified OK」。
### 將輸入改為phonebook的字典檔
* 將字定義的val_t的型態改為字元陣列
```clike
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去判斷執行結果對不對
```clike=
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
## 參考
* [A07: mergesort-concurrent](https://hackmd.io/EwEwHAxgrGCcBmBaAzPMAjRAWAphxAhlhJslLAOwBsqUIy4QA===?view)
* [What is the use of intptr_t?](http://stackoverflow.com/questions/35071200/what-is-the-use-of-intptr-t)
* [TempoJiJi](https://github.com/TempoJiJi/mergesort-concurrent)
* [andy19950](https://github.com/andy19950/mergesort-concurrent)
Sign in with Wallet
Connect another wallet