[其他] 多線程無鎖同步

參考：​​https://docs.microsoft.com/zh-cn/windows/win32/dxtecharts/lockless-programming?redirectedfrom=MSDN​​

小結：

1）Volatile 無法保證無鎖同步；

2）windows下鎖的是通過 memory barrier 實作的，掌握了記憶體屏障的使用便掌握了無鎖同步；

3）DirectX提供了LockFreePipe，此管道隻接受 “一個生産者，一個消費者” 模型；

4）Windows下，MemoryBarrier 提供了一個硬體記憶體屏障，使用此屏障可以防止CPU和編譯器進行亂序執行；

5）Windows下，InterlockedIncrement 提供了一個絕對原子自增 32位變量的手段；64位變量可使用64位版本 InterlockedIncrement64

6）如果操作共享資源不會太耗時的話(比如被鎖包裹的代碼端就幾條指令)，可以考慮使用帶自旋鎖的Critical Section (InitializeCriticalSectionAndSpinCount)，自旋鎖可以讓線程在指定的指令周期範圍(注意這裡是指令周期，是以時間會非常短)内獨占CPU一段時間，然後在這段時間内反複檢查是否可以獲得鎖（這也從側面說明此方法不适用隻有一個CPU核心的場景，而此函數也明确了在單CPU核心場景下不适用，畢竟如果就一個CPU核心又被獨占的話，其他線程将無法得到執行），這樣可以提高加鎖速度。自旋鎖的計數值是需要手工指定的，如果過大則會導緻線程長時間獨占cpu（很危險，會導緻程式無響應，不過一般都是幾千個指令周期，換算成時間可以忽略不計，參考上下文切換的指令周期不會超過1W），如果過小則無法達到效果，具體取值參照 InitializeCriticalSectionAndSpinCount 。

7）Windows下，可使用線程獨享堆來解決多線程從同一塊記憶體池中申請/釋放記憶體時需要加鎖的的問題，這是一種無鎖同步政策。過多的線程共享同一個資源畢竟造成糟糕的競争場景，如果能夠将資源細分則可按照資源相關性安排線程組，這是業務層面的優化，恰巧Windows 提供了 線程獨享堆 來幫助完成這種優化。

ps：幾種同步手段的效率

• ​​MemoryBarrier​​ was measured as taking 20-90 cycles.
• ​​InterlockedIncrement​​ was measured as taking 36-90 cycles.
• Acquiring or releasing a critical section was measured as taking 40-100 cycles.
• Acquiring or releasing a mutex was measured as taking about 750-2500 cycles.

Critical Section 的内部組成：

msdn：Acquiring or releasing a critical section consists of a memory barrier, an InterlockedXxx operation, and some extra checking to handle recursion and to fall back to a mutex, if necessary. You should be wary of implementing your own critical section, because spinning in a loop waiting for a lock to be free, without falling back to a mutex, can waste considerable performance. 

Critiacal Section 内部自帶遞歸鎖機制，這樣可以防止因為目前線程對同一個Critical Section重複加鎖導緻死鎖。

Recommendations：

• Use locks when possible because they are easier to use correctly.
• Avoid locking too frequently, so that locking costs do not become significant.
• Avoid holding locks for too long, in order to avoid long stalls.
• Use lockless programming when appropriate, but be sure that the gains justify the complexity.
• Use lockless programming or spin locks in situations where other locks are prohibited, such as when sharing data between deferred procedure calls and normal code.
• Only use standard lockless programming algorithms that have been proven to be correct.
• When doing lockless programming, be sure to use volatile flag variables and memory barrier instructions as needed.
• When usingInterlockedXxxon Xbox 360, use theAcquireandReleasevariants.

解讀：

• 盡可能使用鎖，因為鎖是絕對安全的；
• 不要頻繁地加鎖；
• 不要過長時間持有鎖；(這條和上一條有點沖突，需要自己平衡)
• 如果使用無鎖同步，要衡量帶來的代碼複雜性是否值得帶來的性能提升；
• 有些場景下必須明确 鎖 是禁止的，這個時候就必須使用無鎖同步 或者 自旋鎖，比如在延遲過程調用 和 正常代碼 之間共享資料 的場景。
• 盡量使用系統提供的無鎖同步元件，盡量不要自己造輪子；
• 在進行無鎖程式設計時，在必要的時候一定要使用 volatile 關鍵字 和 記憶體屏障；
• InterlockedXxx在Xbox 360上要配合Acquire 和Release。

對于InitializeCriticalSectionAndSpinCount具體描述：

實際上對 CRITICAL_SECTION 的操作非常輕量，為什麼還要加上旋轉鎖的動作呢？其實這個函數在單cpu的電腦上是不起作用的，隻有當電腦上存在不止一個cpu，或者一個cpu但多核的時候，才管用。

如果臨界區用來保護的操作耗時非常短暫，比如就是保護一個reference counter，或者某一個flag，那麼幾個時鐘周期以後就會離開臨界區。可是當這個thread還沒有離開臨界區之前，另外一個thread試圖進入此臨界區——這種情況隻會發生在多核或者smp的系統上——發現無法進入，于是這個thread會進入睡眠，然後會發生一次上下文切換。我們知道 context switch是一個比較耗時的操作，據說需要數千個時鐘周期，那麼其實我們隻要再等多幾個時鐘周期就能夠進入臨界區，現在卻多了數千個時鐘周期的開銷，真是是可忍孰不可忍。