# 2017q1 team7 mergesort-concurrent
contributed by <`zmke`、`petermouse`、`0xff07`>
## 使程式能接受字串輸入
參考 [0xff07](https://hackmd.io/s/H154LN6og) 的筆記，修改成可以接受字串輸入
## 建立字串輸入的驗證機制
```cmake
check-words: sort
@uniq test_data/words.txt | sort -R | tail -n $(NUM_OF_DATA) > $(TEST_DATA_FILE)
@sort -d $(TEST_DATA_FILE) > $(SORTED_DATA_FILE)
@./sort $(THREADS) $(TEST_DATA_FILE) | tail -n +4 > $(SORTED_RESULT)
@bash scripts/compare.sh $(SORTED_DATA_FILE) $(SORTED_RESULT)
```
## mutrace 分析
```
mutrace: Showing statistics for process sort (pid 4217).
mutrace: 3 mutexes used.
Mutex #2 (0x0x2407670) first referenced by:
/usr/lib/mutrace/libmutrace.so(pthread_mutex_init+0xf2) [0x7fc25fb344b2]
./sort(tqueue_init+0x46) [0x4014ca]
./sort(tpool_init+0x6a) [0x40172e]
./sort(main+0xe5) [0x401ee4]
/lib/x86_64-linux-gnu/libc.so.6(__libc_start_main+0xf0) [0x7fc25f56b830]
Mutex #0 (0x0x7fc25d13a860) first referenced by:
/usr/lib/mutrace/libmutrace.so(pthread_mutex_lock+0x49) [0x7fc25fb346b9]
/lib/x86_64-linux-gnu/libgcc_s.so.1(_Unwind_Find_FDE+0x2c) [0x7fc25cf36fec]
[(nil)]
Mutex #1 (0x0x603140) first referenced by:
/usr/lib/mutrace/libmutrace.so(pthread_mutex_init+0xf2) [0x7fc25fb344b2]
./sort(main+0xab) [0x401eaa]
/lib/x86_64-linux-gnu/libc.so.6(__libc_start_main+0xf0) [0x7fc25f56b830]
mutrace: Showing 3 most contended mutexes:
Mutex # Locked Changed Cont. tot.Time[ms] avg.Time[ms] max.Time[ms] Flags
2 282836 93324 81938 29.010 0.000 0.016 Mx.--.
0 20 16 5 0.003 0.000 0.001 M-.--.
1 6 4 0 0.001 0.000 0.000 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 1119.388 ms.
mutrace: Results for SMP with 4 processors.
```
`Locked` : mutex 鎖了幾次
`Changed` : mutex 在不同 thread 之間切換的次數
`Cont.` : thread 嘗試要求已鎖住的 mutex 的次數
`tot.Time[ms]` : mutex 鎖住的總時間
`avg.Time[ms]` : 平均鎖住 mutex 的時間
`max.Time[ms]` : 持有 mutex 的最大時間
可以發現到 `Mutex #2` 在使用上非常的頻繁！thread 之間常需要搶奪 mutex，也常因此等待
追蹤原程式碼的 `Mutex #2` 出現的位置 (`$ addr2line -e sort 0x4014ca`)
第一次存取出現在 `/mergesort-concurrent/threadpool.c:45`
```clike=44
pthread_mutex_init(&(the_queue->mutex), NULL);
pthread_cond_init(&(the_queue->cond), NULL);
the_queue->size = 0;
the_queue->num_of_consumed = 0;
```
(每個 mutex 實際對應到程式碼會差一行，不知道為什麼)
可以發現是 threadpool 中負責保護 queue pop 與 push 的 Mutex
## lock-free threadpool 實作
讀完 [A Pragmatic Implementation of Non-Blocking Linked-Lists](https://www.cl.cam.ac.uk/research/srg/netos/papers/2001-caslists.pdf) 的演算法之後想先動手實作看看，關於演算法的解釋 [0xff07](https://hackmd.io/s/H154LN6og) 的筆記有詳細的說明
### Compare And Swap
`bool __sync_bool_compare_and_swap (type *ptr, type oldval type newval, ...)`
`type __sync_val_compare_and_swap (type *ptr, type oldval type newval, ...)`
當 `ptr` 和 `oldval` 相同的時候，會把 `ptr` 的內容改寫成 `newval` ，並回傳 `oldval`
[Built-in functions for atomic memory access](https://gcc.gnu.org/onlinedocs/gcc-4.1.2/gcc/Atomic-Builtins.html) 的解釋如下
These builtins perform an atomic compare and swap. That is, if the current value of *ptr is oldval, then write newval into *ptr.
The “bool” version returns true if the comparison is successful and newval was written. The “val” version returns the contents of *ptr before the operation.
### tqueue_pop()
首先從 `tqueue_pop()` 開始著手修改，目標是把 `tqueue_pop()` 的 mutex 拿掉，參考 [hungry-birds](https://github.com/jserv/hungry-birds) 的實作，並引用 concurrent-ll 內的 `atomic_ops_if.h`
先判斷 queue 裡面是否只有一個 node (head 和 tail 相同)，如果只有一個 node 就嘗試把 tail 和 head 設成 NULL ，如果不只一個 node 嘗試把 head 設成 head->next
```clike=
task_t *tqueue_pop(tqueue_t * const the_queue)
{
task_t *ret;
ret = the_queue->head;
if (ret) {
if(CAS_PTR(&(the_queue->tail), ret, NULL) == ret) {
if(CAS_PTR(&(the_queue->head), ret, NULL) == ret) {
FAD_U32(&(the_queue->size));
FAI_U32(&(the_queue->num_of_consumed));
return ret;
} else {
return NULL;
}
} else {
if(ret->next) {
if(CAS_PTR(&(the_queue->head), ret, ret->next) == ret) {
FAD_U32(&(the_queue->size));
FAI_U32(&(the_queue->num_of_consumed));
return ret;
} else {
return NULL;
}
} else {
return NULL;
}
}
}
return ret;
}
```
`$ make check-words` 結果為 `Passed!`
再用 mutrace 測試一次
`$ mutrace ./sort 4 random.txt`
```
mutrace: Showing statistics for process sort (pid 15836).
mutrace: 3 mutexes used.
Mutex #2 (0x0x7f720a85b860) first referenced by:
/usr/lib/mutrace/libmutrace.so(pthread_mutex_lock+0x49) [0x7f720d2556b9]
/lib/x86_64-linux-gnu/libgcc_s.so.1(_Unwind_Find_FDE+0x2c) [0x7f720a657fec]
[(nil)]
Mutex #0 (0x0xa43670) first referenced by:
/usr/lib/mutrace/libmutrace.so(pthread_mutex_init+0xf2) [0x7f720d2554b2]
./sort(tqueue_init+0x46) [0x4014ca]
./sort(tpool_init+0x6a) [0x40173d]
./sort(main+0xe5) [0x401ef3]
/lib/x86_64-linux-gnu/libc.so.6(__libc_start_main+0xf0) [0x7f720cc8c830]
Mutex #1 (0x0x603140) first referenced by:
/usr/lib/mutrace/libmutrace.so(pthread_mutex_init+0xf2) [0x7f720d2554b2]
./sort(main+0xab) [0x401eb9]
/lib/x86_64-linux-gnu/libc.so.6(__libc_start_main+0xf0) [0x7f720cc8c830]
mutrace: Showing 3 most contended mutexes:
Mutex # Locked Changed Cont. tot.Time[ms] avg.Time[ms] max.Time[ms] Flags
2 20 17 6 0.003 0.000 0.000 M-.--.
0 13 9 1 0.004 0.000 0.001 Mx.--.
1 6 5 0 0.002 0.000 0.000 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 1057.670 ms.
mutrace: Results for SMP with 4 processors.
```
發現只有更改 `tqueue_pop()` 就讓 `Mutex #0` (從 address 可以看出就是前面的 `Mutex #2` )的使用率大幅下降
### tqueue_push()
`tqueue_push()` 一開始不知道要怎麼改變 `tqueue_tail->next` 並改變 `tqueue_tail` 之值，最後也是參考到 [hungry-birds](https://github.com/jserv/hungry-birds) 的寫法，才有些想法
其實兩個的操作並不是不行切割，而是可以先選擇改變 `tail` 之值，確定成功之後，取得舊的 `tail` ，再將舊的 `tail` node 指向新的 `tail` 。
```clike=
int tqueue_push(tqueue_t * const the_queue, task_t *task)
{
task_t *tail = NULL, *head = NULL, *tail_next = NULL;
task->next = NULL;
do {
tail = the_queue->tail;
if (CAS_PTR(&(the_queue->tail), tail, task) == tail)
break;
} while(1);
if (tail) {
do {
tail_next = tail->next;
if (CAS_PTR(&(tail->next), tail_next, task) == tail_next)
break;
} while(1);
} else {
do {
head = the_queue->head;
if (CAS_PTR(&(the_queue->head), head, task) == head)
break;
} while(1);
}
FAI_U32(&(the_queue->size));
return 0;
}
```
## 整合後發生的問題
我們發現程式碼大多數時候可以成功執行，但有時候 thread 沒有接收到中止的 task 使 thread 中止運作，導致進入無窮迴圈
之後讓程式重複執行500次，發現中間出現 core dumped，用`$ addr2line -e ./sort` 找到
`threadpool.c` 的 `tqueue_free`
`free(cur);`
可能發生重複 free 同一塊記憶體，或是 free 到沒有被 malloc 的記憶體
```
*** Error in `./sort': double free or corruption (fasttop): 0x00007f5f000009c0 ***
======= Backtrace: =========
/lib/x86_64-linux-gnu/libc.so.6(+0x777e5)[0x7f5f091987e5]
/lib/x86_64-linux-gnu/libc.so.6(+0x7fe0a)[0x7f5f091a0e0a]
/lib/x86_64-linux-gnu/libc.so.6(cfree+0x4c)[0x7f5f091a498c]
./sort(tqueue_free+0x41)[0x4016cb]
./sort(tpool_free+0x65)[0x401841]
./sort(main+0x132)[0x401f5f]
/lib/x86_64-linux-gnu/libc.so.6(__libc_start_main+0xf0)[0x7f5f09141830]
./sort(_start+0x29)[0x4011a9]
======= Memory map: ========
00400000-00403000 r-xp 00000000 08:0b 525385 /home/ke/mergesort-concurrent/sort
00602000-00603000 r--p 00002000 08:0b 525385 /home/ke/mergesort-concurrent/sort
00603000-00604000 rw-p 00003000 08:0b 525385 /home/ke/mergesort-concurrent/sort
00ce9000-0224f000 rw-p 00000000 00:00 0 [heap]
7f5ef0000000-7f5ef0021000 rw-p 00000000 00:00 0
7f5ef0021000-7f5ef4000000 ---p 00000000 00:00 0
7f5ef8000000-7f5ef8021000 rw-p 00000000 00:00 0
7f5ef8021000-7f5efc000000 ---p 00000000 00:00 0
7f5efc000000-7f5efc021000 rw-p 00000000 00:00 0
7f5efc021000-7f5f00000000 ---p 00000000 00:00 0
7f5f00000000-7f5f00021000 rw-p 00000000 00:00 0
7f5f00021000-7f5f04000000 ---p 00000000 00:00 0
7f5f06f07000-7f5f06f1d000 r-xp 00000000 08:0a 136909 /lib/x86_64-linux-gnu/libgcc_s.so.1
7f5f06f1d000-7f5f0711c000 ---p 00016000 08:0a 136909 /lib/x86_64-linux-gnu/libgcc_s.so.1
7f5f0711c000-7f5f0711d000 rw-p 00015000 08:0a 136909 /lib/x86_64-linux-gnu/libgcc_s.so.1
7f5f0711d000-7f5f0711e000 ---p 00000000 00:00 0
7f5f0711e000-7f5f0791e000 rw-p 00000000 00:00 0
7f5f0791e000-7f5f0791f000 ---p 00000000 00:00 0
7f5f0791f000-7f5f0811f000 rw-p 00000000 00:00 0
7f5f0811f000-7f5f08120000 ---p 00000000 00:00 0
7f5f08120000-7f5f08920000 rw-p 00000000 00:00 0
7f5f08920000-7f5f08921000 ---p 00000000 00:00 0
7f5f08921000-7f5f09121000 rw-p 00000000 00:00 0
7f5f09121000-7f5f092e0000 r-xp 00000000 08:0a 148362 /lib/x86_64-linux-gnu/libc-2.23.so
7f5f092e0000-7f5f094e0000 ---p 001bf000 08:0a 148362 /lib/x86_64-linux-gnu/libc-2.23.so
7f5f094e0000-7f5f094e4000 r--p 001bf000 08:0a 148362 /lib/x86_64-linux-gnu/libc-2.23.so
7f5f094e4000-7f5f094e6000 rw-p 001c3000 08:0a 148362 /lib/x86_64-linux-gnu/libc-2.23.so
7f5f094e6000-7f5f094ea000 rw-p 00000000 00:00 0
7f5f094ea000-7f5f09502000 r-xp 00000000 08:0a 149114 /lib/x86_64-linux-gnu/libpthread-2.23.so
7f5f09502000-7f5f09701000 ---p 00018000 08:0a 149114 /lib/x86_64-linux-gnu/libpthread-2.23.so
7f5f09701000-7f5f09702000 r--p 00017000 08:0a 149114 /lib/x86_64-linux-gnu/libpthread-2.23.so
7f5f09702000-7f5f09703000 rw-p 00018000 08:0a 149114 /lib/x86_64-linux-gnu/libpthread-2.23.so
7f5f09703000-7f5f09707000 rw-p 00000000 00:00 0
7f5f09707000-7f5f0972d000 r-xp 00000000 08:0a 148365 /lib/x86_64-linux-gnu/ld-2.23.so
7f5f09908000-7f5f0990b000 rw-p 00000000 00:00 0
7f5f09929000-7f5f0992c000 rw-p 00000000 00:00 0
7f5f0992c000-7f5f0992d000 r--p 00025000 08:0a 148365 /lib/x86_64-linux-gnu/ld-2.23.so
7f5f0992d000-7f5f0992e000 rw-p 00026000 08:0a 148365 /lib/x86_64-linux-gnu/ld-2.23.so
7f5f0992e000-7f5f0992f000 rw-p 00000000 00:00 0
7fff9c1a7000-7fff9c1c8000 rw-p 00000000 00:00 0 [stack]
7fff9c1e0000-7fff9c1e2000 r--p 00000000 00:00 0 [vvar]
7fff9c1e2000-7fff9c1e4000 r-xp 00000000 00:00 0 [vdso]
ffffffffff600000-ffffffffff601000 r-xp 00000000 00:00 0 [vsyscall]
已經終止 (core dumped)
```
## week 10 改進方向
之前的程式還有很多有待改進的空間
* 程式的正確性
* 之前的程式是錯的!!!!!
* 也許我們也忘記了 ABA 問題
* 驗證 lock-free 的方式有誤
* 我們一開始只驗證 lock-free 的 push 或 pop 其中一邊 , 另一邊維持著 mutex , 這樣反而造成了 race condition
* memory leak
* 現在不建議使用 `__sync_val_compare_and_swap` 了
* 應改用 [C11 `_Atomic`](http://en.cppreference.com/w/c/atomic)
老師提到的改善方法
* 可以參考 [LockLess](https://github.com/DeYangLiu/LockLess) 與 [ring](https://github.com/shramov/ring) 的作法
* 提供 benchmark 程式
## 參考 lock-free queue 實作方法
這邊我們參考了 [Simple, Fast, and Practical Non-Blocking and Blocking Concurrent Queue Algorithms](https://www.research.ibm.com/people/m/michael/podc-1996.pdf) 論文，看到很多 lock-free queue 程式碼都建立在這篇論文的基礎上實作，像是 [Boost](https://github.com/boostorg/lockfree/blob/develop/include/boost/lockfree/queue.hpp) 也參考了這篇實作出 lock-free queue
```clike
structure pointer_t { ptr: pointer to node_t, count: unsigned integer }
structure node_t { value: data type, next: pointer_t }
structure queue_t { Head: pointer t, Tail: pointer_t }
```
原文中有個中介的資料結構叫做 `pointer_t` ，這個資料結構去指向真正的 node (`node_t`) 以及存放一個變數名稱 `count` 代表 reference counting 的次數，可以用來避免 ABA 問題
```clike
initialize(Q: pointer to queue_t)
node = new_node() // Allocate a free node
node->next.ptr = NULL // Make it the only node in the linked list
Q->Head.ptr = Q->Tail.ptr = node // Both Head and Tail point to it
```
比較特別的是， 一開始初始化 lock-free queue 就會新建一個 node ，這個 node 並沒有任何的作用， head 與 tail 會間接指向這個 node ， lock-free queue 至少有一個 node 的存在。
```clike
enqueue(Q: pointer to queue_t, value: data type)
E1: node = new_node() // Allocate a new node from the free list
E2: node->value = value // Copy enqueued value into node
E3: node->next.ptr = NULL // Set next pointer of node to NULL
E4: loop // Keep trying until Enqueue is done
E5: tail = Q->Tail // Read Tail.ptr and Tail.count together
E6: next = tail.ptr->next // Read next ptr and count fields together
E7: if tail == Q->Tail // Are tail and next consistent?
// Was Tail pointing to the last node?
E8: if next.ptr == NULL
// Try to link node at the end of the linked list
E9: if CAS(&tail.ptr->next, next, <node, next.count+1>)
E10: break // Enqueue is done. Exit loop
E11: endif
E12: else // Tail was not pointing to the last node
// Try to swing Tail to the next node
E13: CAS(&Q->Tail, tail, <next.ptr, tail.count+1>)
E14: endif
E15: endif
E16: endloop
// Enqueue is done. Try to swing Tail to the inserted node
E17: CAS(&Q->Tail, tail, <node, tail.count+1>)
```
push 時去確保
[E7] `Q->tail` 還是 `Q->tail`
[E8] `Q->tail` 的 `next.ptr` 為 `NULL`
再去嘗試做 [E9] CAS ， 失敗重來
特別的是 [E8] 失敗時，也嘗試去更新 `Q->tail` 為 `Q->tail->next.ptr`，失敗就算了沒關係(好隨便啊！)
[E17] 試著改變 tail 之值，失敗也沒關係，代表已經被其他人更新
```clike
dequeue(Q: pointer to queue_t, pvalue: pointer to data type): boolean
D1: loop // Keep trying until Dequeue is done
D2: head = Q->Head // Read Head
D3: tail = Q->Tail // Read Tail
D4: next = head.ptr->next // Read Head.ptr->next
D5: if head == Q->Head // Are head, tail, and next consistent?
D6: if head.ptr == tail.ptr // Is queue empty or Tail falling behind?
D7: if next.ptr == NULL // Is queue empty?
D8: return FALSE // Queue is empty, couldn't dequeue
D9: endif
// Tail is falling behind. Try to advance it
D10: CAS(&Q->Tail, tail, <next.ptr, tail.count+1>)
D11: else // No need to deal with Tail
// Read value before CAS
// Otherwise, another dequeue might free the next node
D12: *pvalue = next.ptr->value
// Try to swing Head to the next node
D13: if CAS(&Q->Head, head, <next.ptr, head.count+1>)
D14: break // Dequeue is done. Exit loop
D15: endif
D16: endif
D17: endif
D18: endloop
D19: free(head.ptr) // It is safe now to free the old node
D20: return TRUE // Queue was not empty, dequeue succeeded
```
先前提到 queue 會有一個 node ， head 會指向這個 dummy node ，所以 pop 會先去抓取 dummy node 的下一個 node， 釋放指向 dummy node 的 pointer (`ptr_t`) ， 再去將取得的 node 作為 dummy node ，交給下一次 pop 的釋放 `ptr_t`
確保 [D5] `Q->head` 還是原本的 `Q->head`
[D6] `Q->head.ptr` 若等於先前抓到的 `Q->tail.ptr` [D7]，代表 queue 可能是空的， 這時進一步去檢查 `tail->next.ptr` 有值也嘗試更新 `Q->tail` ，失敗也是沒關係算了
然而如果 [D6] 是錯的 [D11] ，把值取出，並改變 head， head 可能改變失敗代表其他 thread 已經改變 head ，一切重新來過
## 實作 [Simple, Fast, and Practical Non-Blocking and Blocking Concurrent Queue Algorithms](https://www.research.ibm.com/people/m/michael/podc-1996.pdf)
這邊我們使用 C11 `atomic_compare_exchange_weak` 來替換 `__sync_val_compare_and_swap` ，與論文不同的是我們並沒有使用中介結構來操作
在 `tqueue_init()` 進行初始化的時候先新增一個 `dummy_node` ，並讓 `head` 和 `tail` 指向這個 node
``` clike=
task_t *dummy_node = task_new(dummy_function, NULL);
dummy_node->next = NULL;
the_queue->head = dummy_node;
the_queue->tail = dummy_node;
```
### tqueue_pop()
``` clike=
task_t *tqueue_pop(tqueue_t * const the_queue)
{
task_t *head = NULL, *tail = NULL, *next = NULL, *ret = NULL;
while(1) {
head = the_queue->head;
tail = the_queue->tail;
next = head->next;
if(head == the_queue->head) {
if(head == tail) {
if(next == NULL) {
return NULL;
}
atomic_compare_exchange_weak(&(the_queue->tail), &tail, next);
} else {
ret = next;
if(atomic_compare_exchange_weak(&(the_queue->head), &head, next)) {
break;
}
}
}
}
atomic_fetch_sub(&(the_queue->size), 1);
atomic_fetch_add(&(the_queue->num_of_consumed), 1);
return ret;
}
```
### tqueue_push()
``` clike=
int tqueue_push(tqueue_t * const the_queue, task_t *task)
{
task_t *tail = NULL, *tail_next = NULL;
task->next = NULL;
while(1) {
tail = the_queue->tail;
tail_next = tail->next;
if(tail == the_queue->tail) {
if(tail_next == NULL) {
if(atomic_compare_exchange_weak(&(tail->next), &tail_next, task)) {
if(atomic_compare_exchange_weak(&(the_queue->tail), &tail, task)) {
}
break;
}
} else {
if(atomic_compare_exchange_weak(&(the_queue->tail), &tail, tail_next)) {
}
}
}
}
atomic_fetch_add(&(the_queue->size), 1);
return 0;
}
```
### 整合結果
整合後發現最後一個 task 無法正確被 pop ，導致程式無法終止，把原本 `task_run()` 內的 `tqueue_push(pool->queue, _task);` 改成 `tqueue_push(pool->queue, task_new(NULL, NULL));` 就能正確執行了，不知道原因為何
`$ mutrace ./sort 4 random.txt`
```
mutrace: Showing statistics for process sort (pid 5998).
mutrace: 3 mutexes used.
Mutex #1 (0x0x7f71cf274860) first referenced by:
/usr/lib/mutrace/libmutrace.so(pthread_mutex_lock+0x49) [0x7f71d1c6e6b9]
/lib/x86_64-linux-gnu/libgcc_s.so.1(_Unwind_Find_FDE+0x2c) [0x7f71cf070fec]
[(nil)]
Mutex #2 (0x0x603140) first referenced by:
/usr/lib/mutrace/libmutrace.so(pthread_mutex_init+0xf2) [0x7f71d1c6e4b2]
./sort(main+0xab) [0x4020bb]
/lib/x86_64-linux-gnu/libc.so.6(__libc_start_main+0xf0) [0x7f71d16a5830]
mutrace: Showing 2 most contended mutexes:
Mutex # Locked Changed Cont. tot.Time[ms] avg.Time[ms] max.Time[ms] Flags
1 20 14 7 0.003 0.000 0.001 M-.--.
2 6 5 0 0.003 0.000 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 1110.494 ms.
mutrace: Results for SMP with 4 processors.
```
原本的 mutex 已經消失了
## 存在的問題
* memory leak
根據原本的寫法，我們會 pop 每一個 task 並在 task 做完後 free task，但是最一開始的 dummy node 並沒有 free 掉且再也無法取得
如果 threadpool 被設計成可以中途停止的話，剩下在 task queue 中的 task 也無法被釋放記憶體
* ABA 問題
這個問題我們目前還沒有遇到，但是有可能發生，還不曉得要怎麼解決，可能的解決方式有:
* [hazard pointer](https://en.wikipedia.org/wiki/Hazard_pointer)
* [reference counting](https://en.wikipedia.org/wiki/Reference_counting)
* **效率比原本的還差**
pop 與 push 做的事情相當單純，反而 lock-free queue 要不斷地去嘗試 pop 與 push ，過度競爭的狀況使得效益上不減反增，我們對於 lock-free 的結構想得太簡化了，也許要回到每個 thread 有自己的 workqueue 的形式並搭配 ondition variable 等來實現有效率的 lock-free thread pool
```
52.08% sort sort [.] tqueue_pop
16.94% sort sort [.] task_run
4.71% sort sort [.] split_n_merge
4.39% sort sort [.] sort_n_merge
4.08% sort [kernel.kallsyms] [k] queue_work_on
3.45% sort libc-2.23.so [.] __strcmp_sse2_unaligned
3.45% sort [kernel.kallsyms] [k] tty_ldisc_deref
3.14% sort [kernel.kallsyms] [.] native_irq_return_iret
2.82% sort sort [.] list_get
2.51% sort [kernel.kallsyms] [k] update_blocked_averages
2.20% sort libc-2.23.so [.] vfprintf
```
## 參考資料
1. [A Pragmatic Implementation of Non-Blocking Linked-Lists](https://www.cl.cam.ac.uk/research/srg/netos/papers/2001-caslists.pdf)
2. [0xff07 筆記](https://hackmd.io/s/H154LN6og)
3. [hungry-birds](https://github.com/jserv/hungry-birds/blob/master/queue.c)
4. [Built-in functions for atomic memory access](https://gcc.gnu.org/onlinedocs/gcc-4.1.2/gcc/Atomic-Builtins.html)
5. [Compare-and-swap](https://en.wikipedia.org/wiki/Compare-and-swap)
6. [Acquire and Release Semantics](http://preshing.com/20120913/acquire-and-release-semantics/)
7. [Toward Concurrency](https://hackmd.io/s/H10MXXoT)
8. [Simple, Fast, and Practical Non-Blocking and Blocking Concurrent Queue Algorithms](https://www.research.ibm.com/people/m/michael/podc-1996.pdf)
9. [Simple, Fast, and Practical Non-Blocking and Blocking
Concurrent Queue Algorithms ppt](http://web.cecs.pdx.edu/~walpole/class/cs510/winter2008/slides/4a.pdf)
10. [intro-to-lock-free-wait-free-and-aba](http://www.hergert.me/blog/2009/12/25/intro-to-lock-free-wait-free-and-aba.html)
11. [Boost lockfree queue](https://github.com/boostorg/lockfree/blob/develop/include/boost/lockfree/queue.hpp)
12. [Lock Free Concurrent Data Structures,
CAS and the ABA Problem ](http://users.minet.uni-jena.de/~nwk/LockFree.pdf)
13. [lfqueue](https://github.com/mitghi/lfqueue)
Sign in with Wallet
Connect another wallet