2016q3 Homework3 (mergesort-concurrent)

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

挑戰題

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

閱讀程式碼

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) 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
thread_state
- pthread_attr_setdetachstate
- detached v.s. joined