簡介
單寫多讀,簡單說,就是對資源的訪問分為兩種狀態,一種是讀操作,另一種是寫操作。由應用程式提示鎖應該做哪種操作。當為讀模式時,所有的寫動作被懸掛,而讀請求被允許通過,而寫動作時,所有操作被懸掛。並且,讀寫切換時,有足夠的狀態等待,直到真正安全時,才會切換動作。
單寫多讀鎖作為解決並行安全高效問題的利器,在很多場合都在使用。以筆者自己的工程實例來說,一個簡單的記憶體池,在使用傳統鎖的時候,效率約為每秒7500次分配或釋放動作,但一旦改為單寫多讀鎖,則效率暴漲到每秒27500次左右。當然,這不是線性關係,也和業務訪問的密集度相關,不過至少說明單寫多讀鎖效能很高。
Linux 多執行緒 ”一寫多讀” 模式
在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 的讀寫進行同步。使用自旋鎖的原因有兩個:
指針訪問丟失
上面已經介紹了指針訪問丟失的情形,即在兩個指針切換時,多個讀執行緒可能正在使用ptr。為了避免出現讀執行緒會讀取到無效數據,本文使用的方法是利用共享指針的引用計數來實現指針的延遲互換。
解決ptr 的競爭條件和指針訪問丟失問題後,就可以安全的使用雙buffer 方案了。
最終的代碼如下,其中 map_ptr_ 就是主map 指針,bak_ptr_ 是備份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(bak_ptr_) 之後,即使程式一直處在while 循環中,再有新的執行緒通過 map_ptr_ 來訪問主map 的數據時,使用的已經是新的數據了。while 循環是為了解決指針訪問丟失問題。當引用次數為1時,即 unique 為真時,表示已經沒有讀執行緒再使用舊的 map 了,只剩下SwitchMapPtr 中old_map_ptr 這一個引用了,這時可以安全的釋放舊的map,並把它清空當作備份map繼續進行數據的更新操作。
從上面可以看出,通過使用雙buffer和共享指針,避免了在一寫多讀模式中對數據的讀寫頻繁加鎖,實現了”無鎖“ 的設計。
延伸
即然雙buffer可以很好的用於一寫多讀模式,那么對於”多寫一讀“或”多寫多讀“模式,是否也可以引入雙buffer 模式呢?
在含有多執行緒寫同一變數的情形下下,其實是不太適合使用雙buffer 方案的。主要原因是:
多寫的情形下,需要在 bak_map 的多個寫操作之間通過鎖來同步,雖然避免了對讀寫互斥情形的加鎖,但是多執行緒寫時通常對數據的實時性要求較高,如果使用雙buffer,所有新數據必須要等到指針切換時才能被使用,很可能達不到實時性要求。
多執行緒寫時若用雙buffer,則在指針切換時也需要給bak_map 加鎖,並且也要用類似於上面的while 循環來保證沒有執行緒在執行寫入操作時才能進行指針切換,而且此時也要等待多讀的完成才能進行切換,這時就會出現對 bak_map 的鎖定時間過長,在數據更新頻繁的情況下是不合適的。
因而,在多寫的模式下,還是優先用讀寫鎖等作業系統提供的同步機制。