原子操作,內存屏障,鎖
1.原理：CPU提供了原子操作、關中斷、鎖內存總線,內存屏障等機制；OS基於這幾個CPU硬件機制，就能夠實現鎖；再基於鎖，就能夠實現各種各樣的同步機制（信號量、消息、Barrier等等等等）。
2.所有的同步操作最基礎的理論就是原子操作。內存屏障,鎖都是為了保證在不同的平台或者是CPU類型下的原子操作。
3.原子操作在單核，單線程/無中斷，且編譯器不優化的情況下是確定的，是按照C/C++代碼順序執行的，所以不存在異步問題
解釋一下這幾個知識點為什麼會引起異步操作:
首先了解一下cpu處理指令的步驟:
1.早起的處理器為有序處理器，指令處理順序:
a.讀取指令
b.執行指令如果寄存器可寫就從內存取出a的數據到寄存器，寄存器不可寫就等待
c.寄存器處理指令
d.將寄存器結果存入內存
2.現在的處理器大多數為亂序處理器,處理順序：
a.讀取指令
b.指令被劃分到指令隊列
c.指令在隊列中等待,如果寄存器可寫就從內存取出a的數據到寄存器，寄存器不可寫就等待
d.寄存器處理指令
e.將執行結果存入隊列(而不是立即寫入寄存器堆)
f.只有當所有更早的請求執行的指令結果被寫入內存之後，執行的結果才會被存入內存(執行結果重排序，讓執行看起來是有序的)
那麼問題來了：1.一條簡單的a++語句究竟會有這麼多條指令，而這一組指令是可以在任意時候異步執行的(共享數據)
a.單核多線程情況下,線程是存在中斷的，中斷的時候cpu調用另一線程的同一指令組，所以是可能出現交叉執行的可能，也就是說單線程或者關掉中斷可以解決異步問題，但很多時候這種做法並不實際
b.多核多線程情況下共享數據被多個核並行處理，不論哪一種處理器都存在同時執行的可能，這就導致了異步問題
其中以前做游戲服務器開發的時候，一開始不理解很多游戲服務器架構為什麼業務線程都是一條線程處理，因為游戲中很多涉及到共享數據，所以避免不了的要使用各種鎖，但是鎖多了問題反而更多。
c.現在的編譯器都具有優化及自動優化功能，優化之後可能會對共享變臉的訪問順序進行調整，可能會造成與預期不相符的結果。
4.內存屏障的作用：a.在編譯時:拒絕編譯器優化屏障前後的指令,防止內存亂序訪問;b.在運行時:告訴內存地址總線共享數據地址的數據必須同步(當多個線程同時將一個共享數據地址的數據加載到隊列裡的時候,先完成處理從cpu到內存的時候總是通知其他線程跟新隊列中的該共享數據,從而保證一致性)
Memory barrier 常用場合包括：
1.實現同步原語（synchronization primitives）
2.實現無鎖數據結構（lock-free data structures）
3.驅動程序
內存屏障包含4中基本類型:寫屏障，數據依賴屏障(常與寫屏障成對出現),讀屏障,通用內存屏障(包含讀寫屏障)。
內存屏障還有兩種隱式的屏障變種:LOCK和UNLOCK操作(表面上這兩個操作的實際用途和原子操作裡面的Lock解釋有區別，原子操作裡面的lock是鎖內存總線，這裡面的lock是保證執行的執行順序嚴格按照lock前，lock中，lock後的順序執行)
內存屏障按照使用層次可以分為
· 編譯器屏障。
· CPU內存屏障。
· MMIO write屏障。
所以:內存屏障只是一種線程同步的手段，並不會阻塞線程;僅保證了代碼執行順序和多核競爭情況下的數據一致性。
5.鎖:從上面可以看出內存屏障並不是鎖，而鎖是使用了內存屏障實現的一種用戶層的同步處理方式,鎖使用的匯編原語有LOCK,UNLOCK等是內存屏障的一種隱式形式,它們都是LOCK操作和UNLOCK操作的變種，所以幾乎所有的鎖都使用了內存屏障,
鎖包含了:
原子鎖：使用了鎖總線的方式實現原子操作
自旋鎖：while等待,不可搶占的單CPU內核下是無效的，有軟中斷的情況下，必須使用時本地軟中斷失效的方法。自旋鎖更像是一種用戶層控制的while等待處理
讀寫鎖: 讀寫鎖實際是一種特殊的自旋鎖，它把對共享資源的訪問者劃分成讀者和寫者，讀者只對共享資源進行讀訪問，寫者則需要對共享資源進行寫操作
互斥鎖：沉睡/休眠等待,所以互斥鎖比自旋鎖調度耗時。
信號量：用於同一時刻有多個個實例能獲取鎖，可用於表示同時有多少個client請求允許訪問同一個數據塊，允許鎖個數設置為1的時候就是互斥鎖.
讀寫信號量：對同時擁有的讀者數不受限制，只能一個寫者，寫者發現不需要寫的時候降級為讀者。
順序鎖：用於能夠區分讀與寫的場合，並且是讀操作很多、寫操作很少，寫操作的優先權大於讀操作。
讀拷貝鎖：RCU（read-copy-update）(RCU也是用於能夠區分讀與寫的場合，並且也是讀多寫少，但是讀操作的優先權大於寫操作)
rcuclassic：禁止內核搶占的
rcupreempt:允許內核搶占的，實時性更高，和rcuclassic相反
rcutree：和rcuclassic類似
BKL(大內核鎖): 整個內核只有一把這樣的鎖，一旦一個進程獲得大內核鎖，進入了被它保護的臨界區，不但該臨界區被鎖住，所有被它保護的其它臨界區都將無法訪問，直到該進程釋放大內核鎖
注:以下為摘錄整理部分。
詳解:
第一章：從硬件層面解釋原因
1.概念：
從CPU基本原理開始說起，系統性能提升必須以了解CPU基本原理為前提條件，另外，CPU Cache工作原理也是提升系統整體性能的非常重要的方面，所以本文拿出專門章節對其原理進行了詳細介紹。
1. 基本概念
在現代CPU體系設計結構中，一般提供了下面幾種機制來提升系統的整體性能：
1）總線加鎖、cache一致性管理：以實現對系統內存的原子操作、串行化指令(serializing instructions。這些指令僅對pentium4,Intel Xeon, P6,Pentium處理器有效)。
2）處理器芯片內置的高級可編程中斷控制器(APIC)
3）二級緩存(level 2, L2) 對於Pentium4,Intel Xeon, P6處理器,L2 cache已經緊密的封裝到了處理器中。而Pentium,Intel486提供了用於支持外部L2 cache的管腳。
4）超線程技術：它能夠讓一個處理器內核並發的執行兩個或兩個以上的指令流。
這些機制在對稱多處理系統(symmetric-multiprocessing, SMP)中是極其有用的。然而,在RMI這些多核系統中，這些機制也是適用的。
多處理器機制的設計必須滿足下面的需求:
1）保持系統內存的完整性(coherency): 當兩個或多個處理器試圖同時訪問系統內存的同一地址時,必須有某種通信機制或內存訪問協議來提升數據的完整性,以及在某些情況下,允許一個處理器臨時鎖定某個內存區域。
2）保持高速緩存的一致性: 當一個處理器訪問另一個處理器緩存中的數據時,必須要得到正確的數據。如果這個處理器修改了數據,那麼所有的訪問這個數據的處理器都要收到被修改後的數據。
3）允許以可預知的順序寫內存: 在某些情況下,從外部觀察到的寫內存順序必須要和編程時指定的寫內存順序相一致。
4）在一組處理器中派發中斷處理: 當幾個處理器正在並行的工作在一個系統中時,有一個集中的機制是必要的,這個機制可以用來接收中斷以及把他們派發到某一個適當的處理器。
5）采用現代操作系統和應用程序都具有的多線程和多進程的特性來提升系統的性能
2.一致性原因
在多線程編程中，為了保證數據操作的一致性，操作系統引入了鎖機制，用於保證臨界區代碼的安全。通過鎖機制，能夠保證在多核多線程環境中，在某一個時間點上，只能有一個線程進入臨界區代碼，從而保證臨界區中操作數據的一致性。
所謂的鎖，說白了就是內存中的一個整型數，擁有兩種狀態：空閒狀態和上鎖狀態。加鎖時，判斷鎖是否空閒，如果空閒，修改為上鎖狀態，返回成功；如果已經上鎖，則返回失敗。解鎖時，則把鎖狀態修改為空閒狀態。
看起來很簡單，大家有沒有想過，OS是怎樣保證這個鎖操作本身的原子性呢？舉個例子，在多核環境中，兩個核上的代碼同時申請一個鎖，兩個核同時取出鎖變量，同時判斷說這個鎖是空閒狀態，然後有同時修改為上鎖狀態，同時返回成功。。。兩個核同時獲取到了鎖，這種情況可能嗎？
廢話，當然是不可能，可能的話，我們使用鎖還有啥意義。但是，咦？等等，雖然我知道肯定不可能，但是你剛才說的貌似還有點道理，看來OS實現這個鎖還不是看起來這麼簡單，還是有點道道的。
為了弄明白鎖的實現原理，我們首先看看如果OS不采用任何其他手段，什麼情況下會導致上鎖失敗？假如我們把加鎖過程用如下偽碼表示：
1、read lock；
2、判斷lock狀態；
3、如果已經加鎖，失敗返回；
4、把鎖狀態設置為上鎖；
5、返回成功。
明白匯編的同學一看就明白上述每一步都能對應到一條匯編語句，所以我們可以認為每一步本身是原子的。
那麼什麼情況能夠導致兩個線程同時獲取到鎖呢？
1、中斷：假設線程A執行完第一步，發生中斷，中斷返回後，OS調度線程B，線程B也來加鎖並且加鎖成功，這時OS調度線程A執行，線程從第二步開始執行，也加鎖成功。
2、多核：當然了，想想上面舉的例子，描述的就是兩個核同時獲取到鎖的情況。
既然明白鎖失敗的原因，解決手段就很明確了：
先考慮單核場景：
1、既然只有中斷才能把上鎖過程打斷，造成多線程操作失敗。我先關中斷不就得了，在加鎖操作完成後再開中斷。
2、上面這個手段太笨重了，能不能硬件做一種加鎖的原子操作呢？能，大名鼎鼎的“test and set”指令就是做這個事情的。
通過上面的手段，單核環境下，鎖的實現問題得到了圓滿的解決。那麼多核環境呢？簡單嘛，還是“test and set”不就得了，這是一條指令，原子的，不會有問題的。
真的嗎，單獨一條指令能夠保證該指令在單個核上執行過程中不會被中斷打斷，但是兩個核同時執行這個指令呢？。。。我再想想，硬件執行時還是得從內存中讀取lock，判斷並設置狀態到內存，貌似這個過程也不是那麼原子嘛。對，多個核執行確實會存在這個問題。
怎麼辦呢？首先我們得明白這個地方的關鍵點，關鍵點是兩個核會並行操作內存而且從操作內存這個調度來看“test and set”不是原子的，需要先讀內存然後再寫內存，如果我們保證這個內存操作是原子的，就能保證鎖的正確性了。
確實，硬件提供了鎖內存總線的機制，我們在鎖內存總線的狀態下執行test and set操作，就能保證同時只有一個核來test and set，從而避免了多核下發生的問題。
總結一下，在硬件層面，CPU提供了原子操作、關中斷、鎖內存總線的機制；OS基於這幾個CPU硬件機制，就能夠實現鎖；再基於鎖，就能夠實現各種各樣的同步機制（信號量、消息、Barrier等等等等）。
