標籤:

多線程」一寫多讀」模式下的無鎖設計

佇倚危樓風細細。 望極春愁, 黯黯生天際。 草色煙光殘照里。 無言誰會憑闌意。

擬把疏狂圖一醉。 對酒當歌, 強樂還無味。 衣帶漸寬終不悔。 為伊消得人憔悴。

——蝶戀花 柳永

緣起

在linux多線程環境下對同一變數進行讀寫時,經常會遇到讀寫的原子性問題,即會出現競爭條件。為了解決多個線程對同一變數訪問時的競爭條件問題,操作系統層面提供了鎖、信號量、條件變數等幾種線程同步機制。如果對變數的每次訪問都使用上述機制,由於系統調用會陷入內核空間,需要頻繁的進行上下文切換,這就導致了程序的時間開銷比較大。

自然的,我們就想到,在多線程環境中,在某些情況下是否能減少甚至避免使用系統調用?答案是肯定的。

如果對多線程下的變數訪問進行分析,可以看到,線程對變數的訪問可以分為以下幾類:

  • 一個線程寫,另一個線程讀,簡稱一寫一讀
  • 多個線程寫,一個線程讀,簡稱多寫一讀
  • 一個線程寫,多個線程讀,簡稱一寫多讀。
  • 多個線程寫,多個線程讀,簡稱多寫多讀。

在linux 系統中,多個線程同時讀一個變數是不需要同步的,而多個線程同時寫一個變數或一個線程寫而其他線程讀某個變數,是需要同步的,可以總結為:」多讀不互斥,而讀寫和多寫互斥「。

由於多個線程對同一變數的讀不需要同步,因而一寫多讀和一寫一讀並無本質區別,進而可以把多線程下對變數訪問依據是否需要同步而合併成如下三類:

  • 一寫多讀
  • 多寫一讀
  • 多寫多讀

解決上面所有的互斥,都可以使用系統調用。上面已經提到,在某些情況下我們是可以避免使用代價高昂的系統調用的。而「一寫多讀」就是這些特殊情況中的一種。

雙buffer 「無鎖」 設計

使用系統調用進行同步的主要問題在於頻繁切換上下文耗時較長,而後台系統的處理速度又是除正確性之外最為關鍵的指標。為提高系統的運行速度,我們可以使用用其他系統資源來換取時間的辦法,從而避免使用鎖之類系統調用。在這些方法中,最常見的就是用空間換取時間。

針對一寫多讀的情況,可以使用」雙 buffer「 及共享指針機制來實現對同一變數高效訪問,同時又能保證不會出現競爭條件。這一實現的技術關鍵點在於以下兩個方面:

  • 雙 buffer 的備份機制,避免了同時讀寫同一變數。雙buffer 就是指對於通常要被多個線程訪問的變數,再額外定義一個備份變數。由於是一寫多讀,寫線程只向備份變數中寫入,而所有的讀線程只需要訪問主變數本身即可。當寫進程對備份變數的寫操作完成後,會觸發主變數指針和備份變數指針的互換操作,即指針切換,從而將原變數和備份變數的身份進行互換,達到數據更新的目的。
  • 共享指針 shared_ptr,由於其記錄了對變數的引用次數,因而可以避免指針切換時的「訪問丟失」問題。

為了便於理解,本文使用 C++ 中的 map 類型變數作為示意,當然,本文的方法可以推廣到一寫多讀模式下任意數據類型的更新中。使用雙 buffer 的示意圖如下:

注意ptr 和 bak_ptr 都是整個map 的指針,上面藍色箭頭表示通過兩個指針訪問 map 中的元素,ptr 和bak_ptr 本身並不指向元素。

在系統啟動時,把兩個智能指針分別初始化為一個主map 和一個備份 map。之後把全部數據更新到主map中開始對外提供服務。當外部需要讀取數據時(多讀),全部通過主map 的智能指針 ptr 來實現。而數據的更新全部通過備份map 的指針bak_ptr 來實現。由此可以看出,由於使用了兩個map,即雙buffer,使得數據的讀和寫進行了分離,互不影響,不會出現競爭條件,避免了鎖的使用。

指針的切換

由於讀寫分離,雙buffer機制下的數據讀寫不會出現競爭條件。在備份map 中數據更新完成時,必然需要一種方式,使得新數據能被使用到。這裡需要做的就是把主map和備份map 的共享指針指向的內容互換,即ptr 和bak_ptr 指向的內容互換。指針切換如下圖所示:

那麼,在指針互換時,會出現什麼問題呢?

在指針的切換過程中,會出現如下兩個問題:

  • 由於對主map 的讀是多線程的讀,會出現多線程同使用主map 共享指針ptr 的情形,而互換指針時,需要對主map 的指針進行寫操作,那麼對同一指針 ptr 的讀和寫的競爭條件如何解決?

  • 在準備互換ptr 和 bak_ptr 指向的內容時,如果某個讀線程正在使用 ptr 訪問主map,直接互換就可能出現讀線程再通過ptr獲取數據時訪問失效的問題,嚴重的情況下會訪問到無效內存導致程序崩潰。這一問題本文簡稱為」指針訪問丟失「問題,類似於常規指針中出現的野指針或懸垂指針的問題。

ptr 競爭條件的解決

當指針切換時,單線程對 bak_ptr 的寫操作已經完成,因而對其可以隨便讀寫。但由於多個讀線程可能還在使用ptr,切換指針時對 ptr 的讀寫就要十分的小心。為了避免對 ptr 的讀寫出現競爭條件,本文使用了自旋鎖來對ptr 的讀寫進行同步。使用自旋鎖的原因有兩個:

  • 只在指針切換時使用鎖,而不是在讀寫兩個map 時使用鎖,因而鎖的使用頻率會非常的低,由此導致的上下文切換的代價是可接受的。
  • 由於指針切換時 ptr 處於的情形是一寫多讀,指針互換準備對 ptr 進行寫操作時,要獲取鎖的等待時間並不長,並不會有長時間的鎖等待出現,因而可以使用代價更小的自旋鎖,而不是使用代價更高的讀寫鎖。

指針訪問丟失

上面已經介紹了指針訪問丟失的情形,即在兩個指針切換時,多個讀線程可能正在使用ptr。為了避免出現讀線程會讀取到無效數據,本文使用的方法是利用共享指針的引用計數來實現指針的延遲互換。

解決ptr 的競爭條件和指針訪問丟失問題後,就可以安全的使用雙buffer 方案了。

最終的代碼如下,其中 mapptr 就是主map 指針,bakptr 是備份map 的指針:

class UpdateData { public: UpdateData():flag_(0) { } void PeriodTask(); void SetFlag(int i) { flag_ = i; } private: shared_ptr<map> map_ptr_; SpinLock map_rwspinlock_; shared_ptr<map> bak_map_ptr_; int flag_; shared_ptr<map> GetMainMapPtr(); void SetMainMapPtr(shared_ptr<map> new_map_ptr); void SwitchMapPtr(); void PeriodTask(); void GetData(shared_ptr<map> ptr) { ptr["abc"] = "def"; ... }};// 獲取主map 指針shared_ptr<map> UpdateData::GetMainMapPtr() { Lock(map_rwspinlock_); // 加自旋鎖,避免對 ptr 訪問出現競爭條件 return map_ptr_; // 主map 指針}// 設置主map 指針void UpdateData::SetMainMapPtr(shared_ptr<map> new_map_ptr) { Lock(map_rwspinlock_); // 加自旋鎖,避免對 ptr 訪問出現競爭條件 map_ptr_ = new_map_ptr;}// 真正的切換指針void UpdateData::SwitchMapPtr() { shared_ptr<map> old_map_ptr = GetMainMapPtr(); SetMainMapPtr(bak_ptr_); // 這裡新數據已經可以被使用了 // 用引用次數來解決訪問丟失問題 while (old_map_ptr.unique() { ::usleep(10000); // 指針延遲互換 } bak_map_ptr_ = old_map_ptr; bak_map_ptr_->clear();}// 定時任務void UpdateData::PeriodTask() { while(flag) { ::sleep(300); // 每5分鐘更新一次數據 GetData(bak_ptr_); // 新數據寫到備份 map 中 SwitchMapPtr(); }}

需要注意的是,SwitchMapPtr 中調用 SetMainMapPtr(bakptr) 之後,即使程序一直處在while 循環中,再有新的線程通過 mapptr 來訪問主map 的數據時,使用的已經是新的數據了。while 循環是為了解決指針訪問丟失問題。當引用次數為1時,即 unique 為真時,表示已經沒有讀線程再使用舊的 map 了,只剩下SwitchMapPtr 中old_map_ptr 這一個引用了,這時可以安全的釋放舊的map,並把它清空當作備份map繼續進行數據的更新操作。

從上面可以看出,通過使用雙buffer和共享指針,避免了在一寫多讀模式中對數據的讀寫頻繁加鎖,實現了」無鎖「 的設計。

延伸

即然雙buffer可以很好的用於一寫多讀模式,那麼對於」多寫一讀「或」多寫多讀「模式,是否也可以引入雙buffer 模式呢?

在含有多線程寫同一變數的情形下下,其實是不太適合使用雙buffer 方案的。主要原因是:

  • 多寫的情形下,需要在 bak_map 的多個寫操作之間通過鎖來同步,雖然避免了對讀寫互斥情形的加鎖,但是多線程寫時通常對數據的實時性要求較高,如果使用雙buffer,所有新數據必須要等到指針切換時才能被使用,很可能達不到實時性要求。
  • 多線程寫時若用雙buffer,則在指針切換時也需要給bak_map 加鎖,並且也要用類似於上面的while 循環來保證沒有線程在執行寫入操作時才能進行指針切換,而且此時也要等待多讀的完成才能進行切換,這時就會出現對 bak_map 的鎖定時間過長,在數據更新頻繁的情況下是不合適的。

因而,在多寫的模式下,還是優先用讀寫鎖等操作系統提供的同步機制。

結語

雙buffer 方案在多線程環境下能較好的解決 「一寫多讀」 時的數據更新問題,特別是適用於數據需要定期更新,且一次更新數據量較大的情形。而這種情形在後台開發中十分常見。

對技術的不斷探索與思考往往會有新的收穫,我們誤闖入的世界,也往往能帶給我們不一樣的精彩。

我思故我在。

我就是我,疾馳中的企鵝。

我就是我,不一樣的焰火。


推薦閱讀:

多線程是否有意義?
UDP socket能否被多線程同時調用sendto來發送數據?
[Perl][threads]多線程循環處理任務
CLion 鏈接庫?如 lpthread 怎麼設置?
為什麼在同一進程中創建不同線程,但線程各自的變數無法在線程間互相訪問?

TAG:多线程 | Linux |