執行人: wu81177
kevinzxc1217
這裡僅介紹各函式功能,希望有關於如何運用這些函式來進行節點標的流程說明。
節點標記相關的函式有三個
可以參考 concurrent-ll 專案的 src/lockfree/list.c,在 list_search
中:
當判斷 t_next
沒有被標記,就更新 left_node
和 left_node_next
到下一個值來走訪
get_unmarked_ref
是用來取得沒被標記的版本幫助被困在已移除節點的執行緒脫困
get_marked_ref
則是用來取得標記移除的指標,用來把指標修改成標記的版本
stevendd543
想請問 add_tail
中有實作鏈結串列 traversal 的部分,若失敗將會 re-traversal,但在並行環境下如果 prev 被刪掉了是否會造成 dangling pointer 這部分要如何在這個狀況下解決並且維持 lock-free。
若仿照〈A Pragmatic Implementation of Non-Blocking Linked Lists〉論文的方法,prev 被刪掉只是將指標沒用到的 bit 做修改來表示被移除,停留在被移除節點的執行緒還是可以將被標記的指標還原然後離開
youjiaw
可以使用更多效能分析工具來討論修改後的鏈結串列有哪些方面的效能提升。
好的,想請問有建議使用哪些工具嗎
Shiang1212
commit : f635ed
commit : d48b945
在撰寫 commit message 時,應參考如何寫一個 Git Commit Message,試著簡述你每次 commit 的修改內容與考量,保持良好的 commit message 撰寫習慣,能提高專案的可維護性。
了解,感謝提醒
以 Linux 核心的環狀雙向鏈結串列為範本,開發 lock-free 的實作,並探究其效能表現。
針對鏈結串列,研究 lock-based 和 lock-free 實作手法、重現實驗,並理解其 scalability 表現。
不使用 lock 的前提之下常常會看到兩個詞, lockfree 和 lockless,定義如下:
為了探討在 concurrent-ll 程式碼 lock 和 lock-free 版本的差異,老師在 4 核心處理器上做測試:
你要重現實驗,而非引用。
可以看到這張圖顯示了 lock-free 和 lock-based 這兩種不同同步機制在多執行緒環境中的效能差異。綠色線條代表的 lock-free 機制,其效能會隨著執行緒數量的增加而顯著提升,這表示 lock-free 在高並行情況下能更好地利用多核心處理器的資源。相較之下,紅色線條代表的 lock-based 機制,其效能幾乎沒有隨著執行緒數量的增加而提升,這顯示了在高並行情境下,lock-based 機制的瓶頸效應,使得它無法充分利用多核心處理器的優勢
而上面的實作基礎是一篇 2001 年的論文〈A Pragmatic Implementation of Non-Blocking Linked Lists〉
linked list 翻譯為「鏈結串列」。
裡面提到當鏈結串列在很近的時間做 insert 和 remove 如果不考慮 concurrent 有可能會發生錯誤
如圖, remove 10 比 insert 20 早一點發生,就出現了這種錯誤,因此〈A Pragmatic Implementation of Non-Blocking Linked Lists〉中提出先將欲刪除的節點標記等到之後再拆除的做法
注意用語:
由於結構定址會對齊,在64位 位元系統會對齊 8 個字節 位元組,所以底下結構的最後一個 bit 不會用到,可以用來標記是否移除
節點標記相關的函式有三個
is_marked_ref
會判斷最後一個 bit 是否為 1,如果是代表節點被標記移除
get_unmarked_ref
會取得當前節點最後一個 bit 為 0 的值,方便讀取鍵值
get_marked_ref
可取得最後一個 bit 為 1 的值,也就是標記的值
注意用語:
務必使用本課程教材規範的術語。
而在這裡會用到的 atomic operation 有兩種,第一種是 compare and swap (CAS),行為如下,如果 a 指向舊值就會換成新值,如果 a 被其他線程執行緒改為不如預期的東西,就會回傳方便查看
改進你的漢語表達。
注意書寫規範:
實際使用如下
atomic 不能翻譯為「原子」!
參見: https://hackmd.io/@sysprog/it-vocabulary
首先使用了 GNU 擴展中的 __extension__
來避免特定編譯器警告。程式碼的步驟如下,接著使用 GCC 內建函數 __atomic_compare_exchange
進行原子 不可分割的比較並交換操作,0 代表 strong 比較交換,會一直試到成功, __ATOMIC_SEQ_CST
代表使用最強 the strongest memory order。
weak 和 strong 不能直接翻譯。
區分「函數」和「函式」,留意用語。
另一個 atomic operation 是 __atomic_fetch_add
作用是將指向 a 所指向的變數的值加1,並返回該變數在加1之前的值
__ATOMIC_RELAXED
是指定記憶體順序的標志,在這裡使用的是 relaxed ordering ,表示這個加法操作不需要進行同步或排序保證,它僅僅是對變數值進行加法操作,且不對其他執行緒可見的內存操作進行任何排序約束。
參考 lockfree/list.c ,差別是將插入到排序位置的 list_add
改為新增到尾部的 add_tail
,串列鍵值沒有排序的版本。
在中文敘述中,使用全形標點符號,例如該用「,」,而非 ","
list_search
注意書寫規範:
首先理解原版
注意用語:
若進入 while 有兩種原因,t->data < val
比好理解,就是迴圈跑到了要插入的位置,就算一直跑到 tail 也會被它的鍵值 INT_MAX
擋下來
而另外一個條件 is_marked_ref(t_next)
則是用來跳過已被標記要刪除的節點,用 t = get_unmarked_ref(t_next);
來正確 訪問 存取下一個節點
改進你的漢語表達。
而在我的版本中由於是用在未排序的串列,可以做一些簡化
再來是做以下修改讓它可以找到對應鍵值
add_tail
注意書寫規範:
由於是加到尾部,不像 list_add
需要用到 list_search
add_tail
& list_search
闡明你的測試計畫。
區分「函數」和「函式」,務必詳閱: https://hackmd.io/@sysprog/it-vocabulary
撰寫 test.c 用 add_tail
插入數個節點然後用 list_search
找看看剛加入的節點
編譯遇到的第一個問題是在 atomics.h 中使用 typeof 時沒有聲明這個函數
在 Makefile 中將編譯器標準從 -std=c11
改成 -std=gnu99
,這樣才可以確保 GCC 擴展(如 typeof)被正確使用
改成 -std=gnu11
再來是函式外部引用的問題
正常來說因為 list_search
不會被外部函式引用,所以可以前綴 static ,但是在測試的時候應該要先拿掉才能被測試函式直接引用
改進漢語表達。
成功編譯之後執行遇到 Segmentation fault
於是使用 GNU GDB 找錯
先確認了 found_node
不是 NULL ,覺得很奇怪,經過一段時間的嘗試,發現關鍵問題
bit 是「位元」,而非「位」,後者是量詞。
bit 之所以翻譯為「位元」,是避免歧異,例如 "32-bit integer" 在簡體中文寫作「三十二位整数」,bit 乍看就成為量詞,與本意牴觸。
return right_node 是 list_search
要回傳給 found_node
的指標,但高 32 位 被捨棄了,經過查找
資料
查閱第一手材料,避免參照良莠不齊的 CSDN
發現如果64位系統中使用函式的檔案沒有包含那個函式的原型,雖然 GCC 能夠順利編譯,但在回傳指標的時候會被截斷成32位,因此將 list_search
的原型寫進標頭檔裡就能解決這個問題,但如果不是為了在 test.c 中測試 list_search
也沒必要多加這行原型,測試完成後可以刪掉,並且加上 static 關鍵字,維持符號限定於所處的編譯單元。
注意用語。「封閉性」可能是數學的專有名詞,本專題可能會有數學證明,因此你該避免濫用詞彙。
commit 8777d6f
list_remove
原版的 list_remove 適用於存在沒有相同鍵值的串列,這裡我希望修改成可移除多個相同鍵值
注意書寫規範:
經過測試會在 list_search
中陷入無窮迴圈,嘗試除錯多時無果,暫時放棄
commit : f635ed
修正為 clang-format
commit:d48b945
開發 lock-based 和 lock-free 且符合 Liux 核心風格的環狀雙向鏈結串列,附上完整測試和效能分析。
應當證明你的實作能夠正確運作,參照課程教材提及的論文,提供其數學和正規證明。
需要使用 ThreadSanitizer 排除並行程式的潛在問題。
目標是將 lockfree/list.c 修改為符合 Linux 風格的 circular doubly-linked list
下圖展現 list_head
中包含 next 和 prev 雙向連接其他 list_head 一個 link list 中會有一個 list_head 單獨存在當 head 其他則是被包含在 node_t 物件裡面
主要的改變是捨棄原本 list_t
結構的定義:
因為 list head 就足以代表一個 linux like 的串列
然後 node_t
的定義也跟著改成以下這樣
list_search
& list_insert
list_search
因為捨棄單向鏈結串列中 head 和 tail 的定義,所以要先排除單個和零個成員的情況
這裡照理說有兩種修改方式,一種是定義 left, right為 node_t 的指標或間接指標,這樣的優點是取 data 不用經過 list_entry
,另一中種方式是 將 left, right 定義成 list_head 指標或間接指標類型,優點是移動到下一個節點比較方便
我原先是嘗試第一種,但在 list_search
上遇到問題,照理說 CAS_PTR 第一個輸入值類型是後面的指標,於是我像以下這樣對 list_entry
的值取指標:
之所以編譯失敗,是因為你沒搞清楚指標型態,回去看 C 語言規格書。
但就是編譯不過,所以我改成將左右節點的類型定義為 list_head
的方式
經過修改可以順利編譯了但是遇到 Segmentation fault
commit:25b00d7
嘗試用 GDB 尋找問題,發現是在插入第一個節點時就在 list_insert
第 100 行發生錯誤:
經過兩個修改,第一個是改變 list_search
在沒有在空串列的情況,改成回傳 head 而不是 NULL,並且刪掉單節點的情況,應該不用分開討論
令一個改變是分開討論 list_insert
插入第一個節點的情況:
經過這樣修改只能應付絕對遞增依序加入節點的情況
commit: a3e2f61
經過一些修改,現在沒遇到 Segmentation fault 但會在 list_search 的 while(1) 中無限循環,代表 left_node_next != right_node
commit:782de28
接著我意識到如果加回原版有最小和最大鍵值的 head 和 tail 可以少考慮很多邊界條件
所以我把 list_new
改成以下這樣
使用精準的詞彙。
建立串列的同時會置入兩個分別有最小和最大值 極值 的節點
在加上一些小修正,終於使 list_insert
正常工作
commit:d8cd6bb
隨後又發現其實只有順行正確,逆行 從開頭往 next 的方向正確,往 prev 的方向接不起來,所以在 list_insert
做了以下修正
避免說「順行」和「逆行」。
以環狀雙向鏈結串列的節點存取角度來看,只有「從開頭往 next
的方向」和「從開頭往 prev
的方向」,二者並非「順」和「逆」的關聯。
用語精準是工程人員的必要素養之一。
改進你的漢語表達。
在插入新節點 new_elem 後,用 whlie 確保 right 的 prev 指向新節點,如果 CAS_PTR 操作失敗,則重複嘗試,直到成功為止,後面則是多做一些重複動作確保在並行環境下不會出錯
commit:818f790
list_remove
一樣也是把原版做一些修正,像是 node_t 改成 list_head 等等,但發現在移除的時候
list_search
又出現問題了
由於我是移除最一個節點所以在這行出現問題
經過一些思考發現是我上一行犯了一個錯誤,前一行 t = t_next
應該改為 t = get_marked_ref(list_entry(t_next, node_t, list));
這樣才能讀到原始的指標,但是經過這樣修正後印出串列會陷入 -2147483648 20 33 的無限循環,其中 -2147483648 是 INT_MIN ,測試的內容是插入 20 10 40 然後移除 40 ,不知道 33 是從哪裡來的
commit:88e91ac
然後我又發現,其實剛剛的 t = t_next
不用改掉,因為這和原版 singly 的狀況大不同,原本串列的連接是依靠 node_t 裡面的 next 成員來連接,但是在這裡是用裡面的 list_head 來串接,所以 node_t 的 bit 被改寫不會影響 list_head 的連接
由於卡關多時,我又回去複習了一下這個演算法的精神
使用 Graphviz 重新製圖。
發現我在這個版本中應該標記的是 list_head 的指標才對,而不是 node_t,否則沒有地方把標記的指標存起來
但如果要修改就要先檢查 list_head 的對齊狀況,複習了一下 你所不知道的 C 語言:記憶體管理、對齊及硬體特性 並且測試實際狀況
輸出:
可以看到我的電腦是以 8 bytes 去對齊的,代表 list_head 指標最低 3 個 bits 保證是 0,可以用來標記
確定策略後先回頭修改 list_search:
commit:d4fbde7
接著完成了 list_remove 從開頭往 next 的方向的部份,然後往 prev 方向回去看被移除的節點的 next 是否最低位為 1
可以看到確實是 1 沒錯
commit : 38e6af8
此處鏈結串列是「環狀」且「雙向」的鏈結串列,哪來「逆向」呢?
你需要定義操作。
再來就是完成從開頭往 prev 的方向的部份
commit:a229811
目前為止完成了單執行緒的測試
更改為 clang-format
commit:368bca0
善用課程提到的效能分析工具,提出上述程式碼的後續效能改善。
首先要在 Makefile 裡面加上這兩行
CFLAGS 是編譯器選項變數,用於指定編譯階段的編譯器選項,第一行的作用是在編譯階段啟用 ThreadSanitizer,使得編譯時插入額外的程式碼來檢測執行緒相關的錯誤
LDFLAGS 是連結器選項變數,用於指定連結階段的連結器選項,第二行使得連結器在生成最終的可執行文件 檔案時包含 ThreadSanitizer 所需的運行時 runtime library 庫 和支援程式碼
注意用語:
注意書寫規範:
再來是撰寫測試程式:
這裡會建立四個執行緒,每個執行緒會連續插入和移除 i
值 100 次
而 pthread_join
是用來確保主執行緒 main 在所有加入的執行緒結束後才結束
以下是 ThreadSanitizer 輸出結果
這四個 data race 警告都在講同一個地方,只是是在不同執行緒遇到
上方所標記之處是在 list_search
中的 t_next = t->next
,用來走訪鏈節串列
然而這就是這個演算法的關鍵所在
注意用語:
如圖,當有一個執行緒在其他執行緒存取 10 的時候把它移除了,那個執行緒便會用 get_unmarked_ref(t_next)
去訪問 存取下一個節點 30 ,所以雖然它是 racing 但不影響使用
commit:32fbf52
在這個實作裡面 head
的 next
和 prev
分別會有存放 INT_MIN
和 INT_MAX
的節點,雖然這樣做可以簡化程式的邊界條件撰寫,但是每次走訪就要多經過一個節點,如果這個鏈節串列大部分的使用情況是只存放數個節點,那多經過那兩個節點的時間佔比就很可觀,也許以後可以修改成不用這兩個節點的版本
另外就是我這次實作是把原本的單向鏈節串列修改為符合 Linux 風格的環狀雙向鏈結串列,但是並沒有發揮環狀和雙向的優勢,程式架構幾乎和原版一樣,也許可以做一些統計,像是紀錄鍵值平均,然後判斷要往 next
還是 prev
方向去走訪,如果節點操作都是在靠近中後段的的地方這樣可以節省大量走訪時間,充分利用雙向的特性