# 2016q3 Homework3（mergesort-concurrent)
contributed by <`eeuserp`>

## 開發環境
* CPU: Intel(R) Core(TM) i5-3337U CPU @ 1.80GHz
* MEM : 8GB
* cache:
* L1d cache:32K
* L1i cache:32K
* L2 cache:256K
* L3 cache:3072K
* Linux version 4.4.0-21-generic

## POSIX Pthread
### Trace Sample Code
>> 注意: 程式碼的實做可能會存在缺失，導致正確性的議題，請一併提出 [name=jserv]

* * threadpool.h

typedef struct _task { 			//task 的資料結構
    void (*func)(void *);
    void *arg;
    struct _task *next, *last;
} task_t;

typedef struct { 				//task queue 的資料結構
    task_t *head, *tail;
    pthread_mutex_t mutex;
    pthread_cond_t cond;
    uint32_t size; 				//宣告一個 8 byte 的非負整數
} tqueue_t;

typedef struct { 				//thread pool 的資料結構
    pthread_t *threads; 			//宣告 thread id
    uint32_t count;
    tqueue_t *queue; 				//宣告 task queue
} tpool_t;

* threadpool.c

int tqueue_init(tqueue_t *the_queue)		//初始化 task queue
{
    the_queue->head = NULL;
    the_queue->tail = NULL;
    pthread_mutex_init(&(the_queue->mutex), NULL); 	//初始化互斥鎖
    pthread_cond_init(&(the_queue->cond), NULL);	//初始化條件變量
    the_queue->size = 0;
    return 0;
}

task_t *tqueue_pop(tqueue_t *the_queue) 	//把 thread 從 task queue pop 到 thread pool
{
    task_t *ret;
    pthread_mutex_lock(&(the_queue->mutex));  //占有互斥鎖（阻塞操作）
    ret = the_queue->tail;
    if (ret) {
        the_queue->tail = ret->last;	//ret 被 pop 掉了 ， 所以 queue 的尾端 是ret 的上一筆資料 
        if (the_queue->tail) {
            the_queue->tail->next = NULL;
        } else {			//queue 的尾端沒東西 ， 代表整個 queue 都是空的
            the_queue->head = NULL;
        }
        the_queue->size--; 
    }
    pthread_mutex_unlock(&(the_queue->mutex));//解鎖
    return ret;
}

int tqueue_push(tqueue_t *the_queue, task_t *task)
{
    pthread_mutex_lock(&(the_queue->mutex));
    task->last = NULL; 		//要 push 進 queue 的 task 後面沒有東西
    task->next = the_queue->head;	//要 push 進 queue 的 task 的下一筆資料 目前在 queue 的頭
    if (the_queue->head)
        the_queue->head->last = task; // 要 push 進 queue 的 task排在目前最後一筆資料(在 queue 的頭)的後面
    the_queue->head = task;		// 要 push 進 queue 的 task 設為 queue 的頭
    if (the_queue->size++ == 0) 	//假如 queue 為空  
        the_queue->tail = task;       //要 push 進 queue 的 task 設為 queue 的尾
    pthread_mutex_unlock(&(the_queue->mutex));
    return 0;
}

int tpool_init(tpool_t *the_pool, uint32_t tcount, void *(*func)(void *))
{
    the_pool->threads = (pthread_t *) malloc(sizeof(pthread_t) * tcount);
    the_pool->count = tcount;
    the_pool->queue = (tqueue_t *) malloc(sizeof(tqueue_t));
    tqueue_init(the_pool->queue);
    pthread_attr_t attr; 		//宣告 thread 屬性
    pthread_attr_init(&attr);		//初始化 threa 屬性變數
    pthread_attr_setdetachstate(&attr, PTHREAD_CREATE_JOINABLE);//設定 thread  的 detachstate 屬性為 joinable

    for (uint32_t i = 0; i < tcount; ++i)
        pthread_create(&(the_pool->threads[i]), &attr, func, NULL);
    pthread_attr_destroy(&attr);//刪除執行緒的屬性，用無效值覆蓋

    return 0;
}

`pthread_attr_setdetachstate` : thread 可以分為 joinable 或是 detached。joinable thread 可以被其他 thread回收其資源或是銷毀。detached thread不能被其他 thread回收其資源或是銷毀，其占用資源在終止時由系統自動釋放。thread的detachstate決定一個thread以什麼樣的方式終止自己。

`pthread_attr_setdetachstate(&attr, PTHREAD_CREATE_JOINABLE)` : 將 thread 設為 joinable thread ， 原有的 thread 等待建立的 thread 結束。只有當 pthread_join() 函式返回時，建立的thread才算終止，才能釋放自己所占用的資源。建立 thread 時 ， default 為 joinable thread ，所以第 9 行註解掉後實測可以正常執行

`pthread_attr_setdetachstate(&attr, PTHREAD_CREATE_DETACHED)` : 將 thread 設為 detached thread ， detached thread 沒有被其他 thread 等待 ， 自己執行結束 ， thread 立即中止 ， 馬上釋放佔用的系統資源。

## Code Refactoring
* threadpool.c
* `tpool_init` 和 `tpool_free` 中的迴圈的更新值 `++i` 改成 `i++`
* `++i` 是先執行 `i=i+1` 再執行迴圈內的程式碼 ， `i++` 是先執行迴圈內的程式碼再執行`i=i+1`
* `tpool_init` 中的 `pthread_attr_setdetachstate(&attr, PTHREAD_CREATE_JOINABLE);` 可以刪除 ， 因為 <s>創建</s> 建立 thread 時 ， default 為 joinable thread
* `tqueue_pop` 和 `tqueue_push` 中 task 從 head push 進 queue ，從 tail pop 出queue 這是錯的。正確的應是從 tail push 進 queue ，從 head pop 出 queue
>> create 的繁體中文翻譯為「建立」，而非創建，後者是對岸術語 [name=jserv]
>> 我以後參考對岸資料會多加注意，謝謝老師[name=eeuserp]
>> `++i`或`i++`對for迴圈主體沒差吧 [(reference)](http://stackoverflow.com/questions/4706199) [name=mingnus]

## 參考資料
* [pthread_attr_setdetachstate 函數使用](http://blog.csdn.net/sjin_1314/article/details/8023575)
* [argc, argv 解析用法](http://jyhshin.pixnet.net/blog/post/26588000-argc,-argv-%E8%A7%A3%E6%9E%90%E7%94%A8%E6%B3%95)
* [Queue (abstract data type) - Wikipedia ](https://en.wikipedia.org/wiki/Queue_(abstract_data_type))