通過CAS操作免鎖設計：
- CAS原子 操作（Compare & Set）：包含三個操作數，內存值V、舊的預期值 oldval、要修改的新值newval，當且僅當內存V中的值和舊值oldval相同時，將內存V修改為newval。
- 數組隊列是一個循環數組，隊列少用一個元素，當頭等於尾標示隊空，尾加1等於頭標示隊滿。
- 數組的元素用EMPTY（無數據，標示可以入隊）和FULL（有數據，標示可以出隊）標記指示，數組一開始全部初始化成 EMPTY標示空隊列。
- EnQue 操作：如果當前隊尾位置為EMPTY，標示線程可以在當前位置入隊，通過CAS原子操作把該位置設置為FULL，避免其它線程操作這個位置，操作完後修改隊尾位置。各個線程競爭新的隊尾位置。如下圖所示：
- 線程T1/T2競爭隊尾位置。
- T1競爭成功，首先設置FULL標記，然後對該位置進行操作。
- T2輪詢該位置標識為FULL繼續輪詢。
- T1操作完成後將隊尾位置後移。
- T1/T2又開始競爭新的隊尾。
- DeQue 操作：如果當前隊頭位置為FULL，標示線程可以在當前位置出隊，通過CAS原子操作把該位置設置為EMPTY，避免其它線程操作這個位置，操作完後修改隊頭位置。各個線程競爭新的隊頭位置。
- 操作沒有加鎖，每個線程都假設沒有衝突的去完成操作，如果因為衝突失敗就重試。
通過CAS、FAA、FAS操作免鎖設計：
- FAA操作：原子加1操作，返回更新前的值。
- FAS操作：原子減1操作，返回更新前的值。
- 增加writeableCnt指示隊列還可以寫入元素個數，readableCnt指示隊列中存在的元素個數。用來控制可以併發操作的線程個數。
- EnQue 操作：通過原子加操作給每個要求操作的線程分配為唯一一個位置信息存放在局部變量pos中，各個線程並行的操作對應位置的信息，不再需要輪詢等待。如下圖所示：
- T1/T2線程初始操作隊尾的兩個位置。
- T1操作完後直接操作下一個隊尾位置。
- DeQue 操作：如果當前隊頭位置為FULL，標示線程可以在當前位置出隊，通過CAS原子操作把該位置設置為EMPTY，避免其它線程操作這個位置，操作完後修改隊頭位置。各個線程競爭新的隊頭位置。
- 多個線程可以同時進行入隊，避免了在同一個位置等待輪詢，對效率有明顯提升。
分享到:
閱讀更多 cpp軟件架構獅 的文章
