2017q1 Team8(B07: phonebook-concurrent) === contribute by <`Cayonliow`、`king1224`、`csielee#`> ###### tags: `sysprog2017` [github](https://github.com/sysprog2017team8/phonebook-concurrent) / [youtube 4/25](https://www.youtube.com/watch?v=yPdjzWUlizk) / [yotube 5/1](https://www.youtube.com/watch?v=F9hKspTdSQ0) ## 當周 youtube {%youtube F9hKspTdSQ0 %} ## 上課問題 2017/5/24 :::info 1. 5分31秒 - `__sync` 開頭是舊版，不推薦使用。建議使用 C11 `__Atomic` 2. 6分39秒 - append 的程式碼有極大的優化空間，可以縮減 while 迴圈的範圍 3. 7分07秒 - 注意 lockfree 標記問題 4. 總結 - 先建立執行緒再進行測試 - 注意正確性 - code 很醜就要改 - 參考論文：[A Pragmatic Implementation Of Non-Blocking Linked-Lists](https://timharris.uk/papers/2001-disc.pdf) - 參考筆記：[Concurrent Linked List 研究](https://hackmd.io/s/rkhBeeZyx) ::: ## 上課紀錄 2017/5/24 :::success - lock_if.h 的 if 是 interface 的意思 - 重新定義 uint32_t ptlock_t 是為了方便可以更換成 pthread_mutex 等等其他 lock 的實作 - static inline 是個特別的方法，能夠將 function 展開，就像 macro 的效果 - 兩大考量 - 程式優雅度 -- 好看好讀 - 型態檢查 -- 用 macro 不會幫忙檢查 ::: ## 任務要求 - 比照 [B07: phonebook-concurrent](https://hackmd.io/s/rkOExTOoe) 要求，實作出刪除 (remove) 特定資料的功能，並且分析 concurrent insert/delete 對效能的影響。留意 race condition 和正確性議題。 ## 討論紀錄 2017/04/15 - 創造 github - 研究 concurrent linked-list lock/lock-free - 初步重構 - 實作 concurrent linked-list lock/lock-free 2017/04/21 - 確認實作方向，先完成 phonebook 使用 append / remove - 下週一錄影 - 持續實作 2017/04/24 - 實作 lock/lockfree 的 Remove 功能 - 撰寫 hackmd - 錄製影片 ## Concurrent linked-list 在多執行緒當中執行 linked-list 的 Append / Remove 會有 Race condition 的問題 主要是因為，當不同執行緒同時對某一個 node 進行操作 順序的不同，可能導致不同結果 這樣就不符合我們的期望 也可以說，在 linked-list 當中的 node 資源具有排他性 因此執行緒之間需競爭( race ) 底下是 Race condition 的一個例子 當 2 個 thread 都想 Append ```sequence participant ThreadA participant ThreadB Note over ThreadA: node *tmp = new_node(); Note over ThreadB: node *tmp = new_node(); Note over ThreadA: list->tail->next = tmp; Note over ThreadB: list->tail->next = tmp; Note over ThreadB: list->tail = tmp; Note over ThreadA: list->tail = tmp; ``` 可以看到因為同時操作 node 會導致 linked-list 的結構造成錯誤 為了避免這樣的競爭造成錯誤 有了 lock(mutex) 的機制讓同一個資源只能夠讓一個執行緒使用 但是 lock(mutex) 在實作上要非常小心，因為不當的操作都有可能造成 deadlock 因此有了 lock-free 這樣的想法 不使用 lock(mutex) ，改用底層的 atomic opreation 將底層可能產生的錯誤用 atomic opreation 處理掉 也就是在一段執行中不會被打斷/分割，就像是最基本原子不可被分割 但是在程式撰寫上就要考慮到資源是不是已經被其他執行緒處理過 而要不要重新執行 ## lock ### 介紹 lock 保護 linked list 的手法就是讓一個區塊的資料，同時只能有一個 thread 進入進行修改或存取。 好像門的概念，當一條 thread 進入這個區塊 並 lock 起來，像是把門關上，其他 threads 必須在門外等候，直到門被打開 （unlock），第二條 threads 才能進入 可是要注意的是第二條 threads 進入以後也會把門關上， 其餘的 threads 需要繼續在門外等待。 也就是說，每次只能有一條 thread 在 lock 與 unlock 之間的區塊。 lock [實作方法](https://github.com/jserv/concurrent-ll/tree/master/src/lock) ```clike typedef struct __PHONE_BOOK_ENTRY { char *lastName; struct __PHONE_BOOK_ENTRY *pNext; pdetail dtl; ptlock_t *lock; } entry; ``` ```clike //LOCK static inline uint32_t lock_lock(volatile ptlock_t *l) { while (CAS_U32(l, (uint32_t)0, (uint32_t)1) == 1) ; return 0; } ``` ```clike //UNLOCK static inline uint32_t lock_unlock(volatile ptlock_t *l) { *l = (uint32_t)0; return 0; } ``` lock 的執行時間會相較長，因爲在同一塊區塊只能有一條thread 在工作， 所以會有其餘的 threads 在等待。 因爲有等待的時間，所以執行時間會變得很久 ## lock-free ### 介紹 若使用 lock 來保護住資料，若同時多個 thread 要對同一資料做改變，當一個 thread 將資料 lock 住之後，其餘所有需要此資源的 thread 都會停等下來，等待資源被 unlock。 因此有 lock-free 的方法出現，當資源無法使用時，thread 也不會卡在那邊不做事，在某些情況下可以更有效率的利用 cpu cycle。 lock-free [實作方法](http://novoland.github.io/%E5%B9%B6%E5%8F%91/2014/07/26/Lock-Free%20%E7%AE%97%E6%B3%95.html) * 自旋 * 以無限迴圈包住 * 在成功達成目的之前不斷嘗試 * 若失敗則繼續嘗試 * 觀察新值、舊值 * 對於想要更新的對象先取得舊值 * 算出新值 * CAS (compare and swap) * compare 要更動的變數是否仍為舊值 * 若為舊值則可以更新為新值 * 若已被更動過則從新計算新值 ### 如何確保 CAS 成功 － Atomic Builtins 可以利用標準函式庫中支援的原子操作，即使在多線程的情況下，這些操作都會保證正確性，而 CAS 則在 [Atomic Builtins for memory access](https://gcc.gnu.org/onlinedocs/gcc-4.1.0/gcc/Atomic-Builtins.html) 的歸類中 主要用到的函式是： `type __sync_val_compare_and_swap (type *ptr, type oldval, type newval)` 將一個要更新的變數傳入，同時傳入舊值與新值，若變數內仍為舊值，則更新為新值，若變數內已不是舊值，則不做任何更動，且不論何種情況都會回傳舊值。 範例： ```clike= int main(){ int a,b,c,d; a = 3; b = 5; c = 1; d = __sync_val_compare_and_swap(&a, b, c); printf("%d %d %d %d\n",a,b,c,d); b = 3; d = __sync_val_compare_and_swap(&a, b, c); printf("%d %d %d %d\n",a,b,c,d); return 0; } ``` results： ``` 3 5 1 3 1 3 1 3 ``` ### 過程 在對[ lockfree 範例程式碼](https://github.com/jserv/concurrent-ll/tree/master/src/lockfree)略懂略懂之後，本實作經歷了三個主要階段 * 我相信我可以 * 區區一個 link-list，一定不用半天就可以搞定了 * 但 Bug 多到不知道從哪裡開始找起 * 依樣畫葫蘆 * 還是模仿 ~~(照抄)~~ 範例程式碼中的實作方式 * 成功朝著夢想一步一步邁進 * 感覺差最後一步時卡住半天 * 認真學習 * 從頭檢視並理解程式碼詳細實作原理 * 再無限的 `core dump` 之後，今天開始學著使用 [GDB](https://www.puritys.me/docs-blog/article-329-%E5%A6%82%E4%BD%95%E4%BD%BF%E7%94%A8-GDB-Debug.html) 指令，~~之前只查到進階指令，看不懂就馬上關掉了~~ * 在 gdb 的幫助下，果然成功了呢！ ### 程式碼 [csielee 大大](https://github.com/orgs/sysprog2017team8/people/csielee) 先用 [csielee](https://github.com/csielee/phonebook-concurrent) 的方式幫我們整理重構了原始程式碼，因此需要改變的部份主要分成三個函式 * search 在整個 link-list 中搜尋目標 entry，若有已被刪除的函數也在這裡移除鏈結，在 remove 中僅做標記，回傳目標 entry 或 link-list 的尾巴，並將其中一個 call by reference 的 entry 參數設成目標之前一項，方便 caller 使用 ```clike= while( is_marked_ref(j_next) || strncasecmp(str,j->lastName,len)!=0 ) { if(!is_marked_ref(j_next)) { __sync_val_compare_and_swap(&tmpHead,tmpHead,j); (*left_entry) = j; left_next = j_next; } j = get_unmarked_ref(j_next); if(j == entrytail) break; j_next = j->pNext; } ``` 若該項被標記或與目標不符，則繼續往後搜尋，且每次需拿未標記的位址，否則對標記過得位址存取 data 會 core dump 而其中 strncasecmp 函式只能比較前 len 個字元，當一個字串恰好是另一個的前綴時該怎麼辦？ ```clike= int len = strlen(str); if(strlen(j->lastName) == len) break; ``` 再包上一層迴圈，若 strncasecmp 回傳 0 且兩字串長度相等，才能確定兩字串是真正完全一樣而離開迴圈 ```clike= if(left_next == right) { if(!is_marked_ref(right->pNext)) return right; } else if(__sync_val_compare_and_swap(&((*left_entry)->pNext), left_next, right) == left_next ) { if(!is_marked_ref(right->pNext)) { return right; } } ``` left 為目標前一項，right 為目標，left_next 與 right 相等則表示資料沒被更動過，反之則代表中間有很多被標記為刪除的資料，則將 right 接到 left 之後 * append 將新的 data 接到 link-list 末端，因總資料量太大，因此無檢查是否有重複 ```clike= while(1) { right = search(i, &left, tmpHead); if(strncasecmp(right->lastName,i,len) == 0 && strlen(right->lastName) == len) break; j->pNext = right; if(__sync_val_compare_and_swap(&(left->pNext), right, j) == right) break; } ``` 若得到的目標資料已存在，則不做任何事離開，但我在這邊傳入的 link-list entry 非 link-list 的 head，因此在 search 時並不是從頭開始檢查，即使有重複也檢查不出來 ( right 永遠是 link-list tail ) 若成功更新後就離開迴圈，否則重新計算新值，取得 tail 的前一項 * remove 搜尋目標並在刪除後回傳 1，若搜尋不到則不做任何事並回傳 0 ```clike= while(1) { right = search(lastName, &left, entryHead); if(right == NULL || strncasecmp(right->lastName,lastName,len) != 0){ return 0; } right_succ = right->pNext; if(!is_marked_ref(right_succ)) { if(__sync_val_compare_and_swap(&(right->pNext), right_succ, get_marked_ref(right_succ)) == right_succ){ return 1; } } } ``` 將目標的 pNext 中的資料標記起來 參考： [SMP中多线程程序的性能衰退现象之False Sharing](http://www.voidcn.com/blog/yockie/article/p-6328160.html) [Frank Tan's Blog](http://www.cnblogs.com/FrankTan/archive/2010/12/11/1903377.html) ## 分析 |結構|執行方式|資料來源| |:---:|:---:|:---:| |linked-list|多執行緒<br>分區塊執行|append:人名資料<br>remove:前一萬筆人名| |concurrent linked-list<br>lock|多執行緒<br>分區塊執行|append:人名資料<br>remove:前一萬筆人名| |concurrent linked-list<br>lock-free|多執行緒<br>分區塊執行|append:人名資料<br>remove:前一萬筆人名| ### 執行狀況 因為我們想要專注在 concurrent linked-list 上對效能的影響 因此我們都傳入已經對齊好的文字檔案 並且都一次 malloc 好需要的記憶體，讓效能影響的變因減少 能夠好好研究 concurrent linked-list 的效能議題 <br> - 呈獻在不同 linked-list 下的 AppendByFile / RemoveByFile 時間 :::warning 因為在 linked-list 難以實作多執行緒的刪除 因此時間均為 0 ::: ![](https://i.imgur.com/UcTLasU.png) :::info 觀察後發現 在 Append ，lock / lockfree 都有上升 推測是因為要處理 race condition 的問題 因此執行緒無法全力執行，必定有等待的時間 <br> 而在 Remove lock 的 Remove 時間異常的長 lockfree 的 Remove 時間也比 Append 來得長 這部份感覺還需要調整一下 跟預期的想像不一樣 ::: ## lock-free 優化部份 主要優化了兩個部份 * thread_args * 針對 thread_args 使用 memory pool 來實作，一次取得所有會用到的空間，減少 system lock 的情況 * append * 將 append 中一些不需要的程式碼移除，讓各 threads 可以從任何地方 append，不用彼此搶著從同一個地方 append，減少 CAS 的失敗率 #### thread_args memory pool ```clike thread_args_pool = (thread_arg *) malloc(sizeof(thread_arg) * THREAD_NUM); ``` 一次將所需要的空間 malloc 出來，減少 malloc 的呼叫次數 ```clike thread_args[i] = createThread_arg(map + MAX_LAST_NAME_SIZE * i,map + file_size, i,THREAD_NUM, entry_pool + i, thread_args_pool + i); ``` 在 create 新的參數時，傳入事先取得的空間直接使用 ```clike= static thread_arg *createThread_arg(char *data_begin, char *data_end, int threadID, int numOfThread, entry *entryPool,thread_arg *argPool) { argPool->data_begin = data_begin; argPool->data_end = data_end; argPool->threadID = threadID; argPool->numOfThread = numOfThread; argPool->lEntryPool_begin = entryPool; argPool->lEntry_head = argPool->lEntry_tail = entryPool; return argPool; } ``` 從 memory pool 直接取一條 thead_arg 出來使用，取代每次都重新 malloc 空間的方法 #### append ```clike= static void append(void *arg) { thread_arg *t_arg = (thread_arg *) arg; int count = 0, len; entry *left, *right,*tmpHead; entry *j = t_arg->lEntryPool_begin; tmpHead = entryHead; for (char *i = t_arg->data_begin; i < t_arg->data_end; i += MAX_LAST_NAME_SIZE * t_arg->numOfThread, j += t_arg->numOfThread, count++) { left = right = NULL; if(i[strlen(i)-1]=='\n') i[strlen(i)-1] = '\0'; j->lastName = i; while(1) { right = tmpHead->pNext; j->pNext = right; if(__sync_val_compare_and_swap(&(tmpHead->pNext), right, j) == right) break; } tmpHead = j; DEBUG_LOG("thread %d t_argend string = %s\n", t_arg->threadID, new -> lastName); } pthread_exit(NULL); } ``` 每個 threads 都是從 entryHead 開始，但各個 threads 會不斷的將要插入的位置更新為自己上一次插入的 entry 之後，而每個 threads 插入的 entry 位置都不同，因此任兩個 threads 幾乎不會有同時搶著對同一個位置做改變的情況 <br> ## 遇到問題 - 有 memory leak 的問題 - lock 的刪除有正確性的問題 - 無法充份表現 concurrent linked-list - 嘗試用 ThreadSanitizer 去驗證正確性議題 - lock 可以嘗試改用 pthread_mutex <br> ## interface Refactor :::info TODO ::: 統一 lniked-list 的介面 ```clike insertEach(entry *new_element); removeEach(char *name); getuserdata(char *name); ``` <!-- 網頁 CSS 樣式 --> <style> .markdown-body h2 { padding-top : 0.15em; padding-bottom : 0.15em; padding-left : 0.2em; background-color : DarkGrey; border: 1px solid transparent; border-radius: 4px; } .markdown-body { } </style>
Last changed by  
 
李東霖
363
Published on HackMD