並行編程中的內存回收Hazard Pointer

杜老師說 2022-01-07 08:40:44 阅读数:851

回收 hazard pointer

感謝同事【kevinlynx】在本站發錶此文

接上篇使用RCU技術實現讀寫線程無鎖,在沒有GC機制的語言中,要實現Lock free的算法,就免不了要自己處理內存回收的問題。

Hazard Pointer是另一種處理這個問題的算法,而且相比起來不但簡單,功能也很强大。鎖無關的數據結構與Hazard指針中講得很好,Wikipedia Hazard pointer也描述得比較清楚,所以我這裏就不講那麼細了。

一個簡單的實現可以參考我的github haz_ptr.c

 

原理

基本原理無非也是讀線程對指針進行標識,指針(指向的內存)要釋放時都會緩存起來延遲到確認沒有讀線程了才對其真正釋放。

<Lock-Free Data Structures with Hazard Pointers>中的描述:

Each reader thread owns a single-writer/multi-reader shared pointer called “hazard pointer.” When a reader thread assigns the address of a map to its hazard pointer, it is basically announcing to other threads (writers), “I am reading this map. You can replace it if you want, but don’t change its contents and certainly keep your deleteing hands off it.”

關鍵的結構包括:Hazard pointerThread Free list

Hazard pointer:一個讀線程要使用一個指針時,就會創建一個Hazard pointer包裝這個指針。一個Hazard pointer會被一個線程寫,多個線程讀。

struct HazardPointer { void *real_ptr; // 包裝的指針 ... // 不同的實現有不同的成員 }; void func() { HazardPointer *hp = accquire(_real_ptr); ... // use _real_ptr release(hp); }

Thread Free List:每個線程都有一個這樣的列錶,保存著將要釋放的指針列錶,這個列錶僅對應的線程讀寫

void defer_free(void *ptr) { _free_list.push_back(ptr); }

當某個線程要嘗試釋放Free List中的指針時,例如指針ptr,就檢查所有其他線程使用的Hazard pointer,檢查是否存在包裝了ptr的Hazard pointer,如果沒有則說明沒有讀線程正在使用ptr,可以安全釋放ptr

void gc() { for(ptr in _free_list) { conflict = false for (hp in _all_hazard_pointers) { if (hp->_real_ptr == ptr) { confilict = true break } } if (!conflict) delete ptr } }

以上,其實就是Hazard Pointer的主要內容。

Hazard Pointer的管理

上面的代碼中沒有提到_all_hazard_pointersaccquire的具體實現,這就是Hazard Pointer的管理問題。

《鎖無關的數據結構與Hazard指針》文中創建了一個Lock free的鏈錶來錶示這個全局的Hazard Pointer List。每個Hazard Pointer有一個成員標識其是否可用。這個List中也就保存了已經被使用的Hazard Pointer集合和未被使用的Hazard Pointer集合,當所有Hazard Pointer都被使用時,就會新分配一個加進這個List。當讀線程不使用指針時,需要歸還Hazard Pointer,直接設置可用成員標識即可。要gc()時,就直接遍曆這個List。

要實現一個Lock free的鏈錶,並且僅需要實現頭插入,還是非常簡單的。本身Hazard Pointer標識某個指針時,都是用了後立即標識,所以這個實現直接支持了動態線程,支持線程的掛起等。

nbds項目中也有一個Hazard Pointer的實現,相對要弱一點。它為每個線程都設置了自己的Hazard Pointer池,寫線程要釋放指針時,就訪問所有其他線程的Hazard Pointer池。

typedef struct haz_local { // Free List pending_t *pending; // to be freed int pending_size; int pending_count; // Hazard Pointer 池,動態和靜態兩種 haz_t static_haz[STATIC_HAZ_PER_THREAD]; haz_t **dynamic; int dynamic_size; int dynamic_count; } __attribute__ ((aligned(CACHE_LINE_SIZE))) haz_local_t; static haz_local_t haz_local_[MAX_NUM_THREADS] = {};

每個線程當然就涉及到haz_local_索引(ID)的分配,就像使用RCU技術實現讀寫線程無鎖中的一樣。這個實現為了支持線程動態創建,就需要一套線程ID的重用機制,相對複雜多了。

附錄

最後,附上一些並行編程中的一些概念。

Lock Free & Wait Free

常常看到Lock FreeWait Free的概念,這些概念用於衡量一個系統或者說一段代碼的並行級別,並行級別可參考並行編程——並發級別。總之Wait Free是一個比Lock Free更牛逼的級別。

我自己的理解,例如《鎖無關的數據結構與Hazard指針》中實現的Hazard Pointer鏈錶就可以說是Lock Free的,注意它在插入新元素到鏈錶頭時,因為使用CAS,總免不了一個busy loop,有這個特征的情况下就算是Lock Free,雖然沒鎖,但某個線程的執行情况也受其他線程的影響。

相對而言,Wait Free則是每個線程的執行都是獨立的,例如《鎖無關的數據結構與Hazard指針》中的Scan函數。“每個線程的執行時間都不依賴於其它任何線程的行為”

鎖無關(Lock-Free)意味著系統中總存在某個線程能够得以繼續執行;而等待無關(Wait-Free)則是一個更强的條件,它意味著所有線程都能往下進行。

ABA問題

在實現Lock Free算法的過程中,總是要使用CAS原語的,而CAS就會帶來ABA問題。

在進行CAS操作的時候,因為在更改V之前,CAS主要詢問“V的值是否仍然為A”,所以在第一次讀取V之後以及對V執行CAS操作之前,如果將值從A改為B,然後再改回A,會使基於CAS的算法混亂。在這種情况下,CAS操作會成功。這類問題稱為ABA問題。

Wiki Hazard Pointer提到了一個ABA問題的好例子:在一個Lock free的棧實現中,現在要出棧,棧裏的元素是[A, B, C]head指向棧頂,那麼就有compare_and_swap(target=&head, newvalue=B, expected=A)。但是在這個操作中,其他線程把AB都出棧,且删除了B,又把A壓入棧中,即[A, C]。那麼前一個線程的compare_and_swap能够成功,此時head指向了一個已經被删除的B。stackoverflow上也有個例子Real-world examples for ABA in multithreading

對於CAS產生的這個ABA問題,通常的解决方案是采用CAS的一個變種DCAS。DCAS,是對於每一個V增加一個引用的錶示修改次數的標記符。對於每個V,如果引用修改了一次,這個計數器就加1。然後再這個變量需要update的時候,就同時檢查變量的值和計數器的值。

但也早有人提出DCAS也不是ABA problem 的銀彈

written by Kevin Lynx  posted athttp://codemacro.com

原創文章,轉載請注明: 轉載自並發編程網 – ifeve.com本文鏈接地址: 並行編程中的內存回收Hazard Pointer

FavoriteLoading添加本文到我的收藏
版权声明:本文为[杜老師說]所创,转载请带上原文链接,感谢。 https://gsmany.com/2022/01/202201070840439157.html