# 2016q3 Homework3 (mergesort-concurrent)

###### tags: `sysprog-hw` `mergesort-concurrent`

## 挑戰題
* 引入 C11 本身的 thread.h 實作多執行並用 `_Atomic` 改寫。參考資料:
* [Atomics in C programming](https://www2.informatik.hu-berlin.de/~keil/docs/keil_-_c11_atomics_20140202.pdf)
* [You Can Do Any Kind of Atomic Read-Modify-Write Operation](http://preshing.com/20150402/you-can-do-any-kind-of-atomic-read-modify-write-operation/)
* [Boost atomic examples](http://www.boost.org/doc/libs/1_61_0/doc/html/atomic/usage_examples.html)

---

# 閱讀程式碼

- [ ] `intptr_t` 使用

先看看 stdint.h 中對 intptr_t 的定義，可以發現 intptr_t 在不同平台中是對應到不同長度，而且都更指標的長度一樣，因此可以使用他來儲存資料也可以使用它來當指標。

/* Types for `void *' pointers.  */
#if __WORDSIZE == 64
# ifndef __intptr_t_defined
typedef long int        intptr_t;
#  define __intptr_t_defined
# endif
typedef unsigned long int   uintptr_t;
#else
# ifndef __intptr_t_defined
typedef int         intptr_t;
#  define __intptr_t_defined
# endif
typedef unsigned int        uintptr_t;
#endif

>> 延伸閱讀: [Fixed width integer types (since C99)](http://en.cppreference.com/w/c/types/integer) [name=jserv]

---

- [ ] `pthread_attr_setdetachstate` 的使用

再 man 之中就有其詳盡的說明，大致上將 thread 分為 detachable (可分離) 與 joinable (可加入？) ，而這兩者的差異說明則是在 pthread_create 的 man 裡面被提及。簡單來說，便是 thread 的結束方法不同。

> 

---

# TODO

- [ ] 我發現這裡的 task_run 在拿取 task 時，是透過　busy-waiting 的方式不斷詢問是否有工作，透過 signal、pipe 等實作來改變獲取工作的方式！
- [ ] thread pool -> lock less thread pool
- [ ] 字串排序的演算法？

# 修改

## 引入35筆資料

為了將 word.txt 導入程式中，因此將 node_t 的 struct 修改為儲存 char* 的結構

typedef struct node {
    char *data;
    struct node *next;
} node_t;

並修改 merge 中對於資料大小判斷的方法(畢竟變成字串了)

while (a->size && b->size) {

  llist_t *small;

  for(int i = 0; i < 14; i++){
    if(a->head->data[i] > b->head->data[i]){
      small = b;
      break;
    }else if(a->head->data[i] < b->head->data[i]){
      small = a;
      break;
    }else{
    
    }
  }
}

`Execution Time:0.101397`

## 使用 pipe

試著新增喚醒 thread 的機制 pipe，但發現速度反而變慢了，想了一下，這種喚醒 thread 的機制在這次的案例之中是不適合的，因為 mergesort 只要還有資料就必須不斷進行運算，也因此增加這種機制反而會讓執行變慢。

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

    /* use pipe */
    struct {
        int in;
        int out;
    } pipe;

    unsigned int run;

} tpool_t;

`Execution time:0.135903`

# Mutrace使用

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

輸出如下：

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

Mutex #2 (0x0xcac590) first referenced by:
	/usr/lib/mutrace/libmutrace.so(pthread_mutex_init+0xf2) [0x7fac7ca584b2]
	./sort(tqueue_init+0x38) [0x40128d]
	./sort(tpool_init+0x6b) [0x4014e3]
	./sort(main+0x152) [0x401c78]
	/lib/x86_64-linux-gnu/libc.so.6(__libc_start_main+0xf5) [0x7fac7c493f45]

Mutex #0 (0x0x7fac7a061a80) first referenced by:
	/usr/lib/mutrace/libmutrace.so(pthread_mutex_lock+0x49) [0x7fac7ca586b9]
	/lib/x86_64-linux-gnu/libgcc_s.so.1(_Unwind_Find_FDE+0x2a) [0x7fac79e5e0da]
	[(nil)]

Mutex #1 (0x0x603120) first referenced by:
	/usr/lib/mutrace/libmutrace.so(pthread_mutex_init+0xf2) [0x7fac7ca584b2]
	./sort(main+0x10e) [0x401c34]
	/lib/x86_64-linux-gnu/libc.so.6(__libc_start_main+0xf5) [0x7fac7c493f45]

mutrace: Showing 3 most contended mutexes:

 Mutex #   Locked  Changed    Cont. tot.Time[ms] avg.Time[ms] max.Time[ms]  Flags
       2      147       32       24        0.158        0.001        0.002 Mx.--.
       0       20        8        6        0.018        0.001        0.002 M-.--.
       1       13        8        2        0.014        0.001        0.002 M-.--.
                                                                           ||||||
                                                                           /|||||
          Object:                                     M = Mutex, W = RWLock /||||
           State:                                 x = dead, ! = inconsistent /|||
             Use:                                 R = used in realtime thread /||
      Mutex Type:                 r = RECURSIVE, e = ERRRORCHECK, a = ADAPTIVE /|
  Mutex Protocol:                                      i = INHERIT, p = PROTECT /
     RWLock Kind: r = PREFER_READER, w = PREFER_WRITER, W = PREFER_WRITER_NONREC 

mutrace: Note that the flags column R is only valid in --track-rt mode!

mutrace: Total runtime is 0.935 ms.

mutrace: Results for SMP with 12 processors.

其中資訊包含了，共使用了幾次 mutex 、mutex 被呼叫的位置、mutex 被呼叫的時間，透過這些資訊可以幫助我，實作 lock-less 的 thread pool。

---

# 參考文獻

- [intptr](http://www.cnblogs.com/Anker/p/3438480.html)
- thread_state
- [pthread_attr_setdetachstate](http://man7.org/linux/man-pages/man3/pthread_attr_setdetachstate.3.html)
- [detached v.s. joined](http://man7.org/linux/man-pages/man3/pthread_create.3.html)