5分鐘了解並發編程中的『鎖』

• 2020 年 3 月 6 日
• 筆記

城邊編程 phplog

寫文章耗時

10

分鐘

讀完僅需5分鐘

疫情期間我完成了『PHP非侵入式監控平台』的重構與開源，請點擊閱讀原文獲取項目。

電腦中有一門經典的課程叫『作業系統』，裡面花很少的篇幅講了『鎖』，鎖是在執行多執行緒時用於強行限制資源訪問的同步機制，即用於在並發控制中保證對互斥要求的滿足。雖然字不多，但事大，特別是在人人都要懂高並發的今天，『鎖』變成了高級程式設計師的必備技能。

為什麼需要鎖？

早期的CPU只有單核，同一時間只能做一件事，我們稱為順序執行。雖然作業系統在軟體層通過時間片劃分能模擬出多執行緒，但本質上還是串列，此時鎖的應用場景非常少。當CPU發展成多核之後真正的並發執行開始出現，電腦真正意義上實現同一時間做多件事。

相比順序執行，並發執行讓電腦的計算能力再次飛躍，比如『天河一號』就是利用多核CPU的並行計算能力。並發執行雖然快但首先要解決的問題是資源同步。比如我們使用2個CPU執行緒並行去計算1000個耗時的演算法題，如何分配資源？我們將2個CPU執行緒用A，B字母代替，演算法題總數用V代替。

因為不希望AB計算同一題，所以當A拿到第一題後，B就不能再拿到第一題。於是在A準備拿第一題時先將總數V鎖住，拿完題後將V減一，最後釋放鎖。B拿題時發現V被鎖住，於是阻塞或者輪詢，直到V被解鎖後再重複A的操作。這樣做能解決AB不計算同一題的問題，但也帶來了一系列隱患，下文將展開討論。

並行計算場景中有無數資源需要同步給各個CPU執行緒，鎖無處不在。

使用鎖時的常見問題

上文說了AB執行緒如何利用『鎖』解決資源V同步的問題，但有些隱患。這些隱患無論是在執行緒之間，還是分散式架構下都客觀存在，是程式設計師們要努力解決的問題，也是面試官要學習的問題。

1. A鎖住V後，A執行緒崩潰導致V的鎖無法釋放，B永遠拿不到資源V；

這個問題非常難解決，近幾十年科學家們都沒給出一個完美方案，但給了一系列折中辦法。常見辦法之一就是使用『CAS+自旋』樂觀鎖，它利用CPU提供的硬體級指令讓A執行緒對V資源的變更變成一個原子操作，原子操作的好處就是要麼成功要麼失敗，不會被中斷。另一種常見辦法是給鎖加時間限制，比如每個執行緒只能鎖住資源1秒。還有一種辦法是給B執行緒加權，比如B執行緒嘗試10次後系統直接讓B執行緒獲取資源V。這些辦法都非常經典，下文會具體討論。

2. A給V加的鎖是互斥鎖，它保證了資源被獨佔。這種鎖用在頻繁更新的資源上會造成大量的阻塞喚醒和資源浪費。

優化此類問題有兩點技巧，一是減少鎖資源的時間（不要將執行耗時的程式碼放到數據臨界區），二是減少更新資源的次數（讀鎖不會阻塞）。對於V這種資源使用消息隊列更合適，提前將1000個演算法題按編號存入消息隊列，AB執行緒只需要調用隊列的讀介面獲取數據，不用觸發更新操作，也就不會加互斥鎖。當然消息隊列也需要考慮鎖的問題，但無鎖消息隊列的技術實現已經非常成熟。

為了解決鎖帶來的CPU資源浪費/死鎖/飢餓等問題，下面列舉了常見的解決方案和使用場景。

樂觀鎖

樂觀鎖很樂觀，對其他執行緒毫無防備之心，不會鎖資源，是個老好人。技術上一般通過CAS自旋實現。CAS是CPU提供的原子操作，指令大致如下`cmpxchg B V A` B是新值，V是記憶體位置，A是預期原值(比如要把變數V從90改為100，對應的指令為`cmpxchg 100 &V 90`)。如果V記憶體位置的值與預期原值90相匹配，那麼處理器會自動將該位置值更新為新值100，否則處理器不做任何操作。一般我們不希望CAS失敗，所以會不停的重試直到成功，這種方式就叫自旋。

我們經常聽到無鎖版隊列、無鎖版鏈表、無鎖版數據結構和演算法等，他們的名字都很響亮但技術並沒有多高深，基本上都通過CAS實現。記憶體屏障也可用來實現無鎖技術，感興趣的朋友請自行Google。

樂觀鎖是一個深藏功與名的技術，因為世界上最厲害的鎖就是無鎖勝有鎖。CAS雖然高效，但也存在三大問題（當前這三大問題都有很成熟的解決方案）。

1. ABA問題。

CAS需要在操作值的時候檢查記憶體值是否發生變化，沒有發生變化才會更新記憶體值。但是如果記憶體值原來是A，後來變成了B，然後又變成了A，那麼CAS進行檢查時會發現值沒有發生變化，但是實際上是有變化的。ABA問題的解決思路就是在變數前面添加版本號，每次變數更新的時候都把版本號加一，這樣變化過程就從「A－B－A」變成了「1A－2B－3A」。

2. 循環時間長開銷大。

CAS操作如果長時間不成功，會導致其一直自旋，給CPU帶來非常大的開銷。所以需要根據實際需求選擇要不要用樂觀鎖。

3. 只能保證一個共享變數的原子操作。

對一個共享變數執行操作時，CAS能夠保證原子操作，但是對多個共享變數操作時，CAS是無法保證操作的原子性的。

悲觀鎖

悲觀鎖很悲觀，因為不想被其他執行緒打擾所以會對資源加鎖，是個孤獨的王者。悲觀鎖能解決很多難題，相比樂觀鎖他的擴展性極強。上文AB執行緒中的『互斥鎖』就是悲觀鎖的一種。悲觀鎖雖然功能強大但很容易導致大量CPU切換，資源死鎖等問題。操作難度MAX，常用來鑒別高級程式設計師與普通程式設計師。下面說說悲觀如何解決阻塞執行緒與造成死鎖的問題。

使用自旋鎖優化CPU上下文切換 – 執行緒被阻塞或喚醒需要作業系統切換CPU狀態來完成，這種狀態轉換需要耗費處理器時間。但大多數情況下執行緒進入阻塞然後再喚醒的時間比資源被鎖住後釋放的時間長的多。為了讓當前執行緒「稍等一下」，我們需讓當前執行緒進行自旋，如果在自旋完成後前面鎖定同步資源的執行緒已經釋放了鎖，那麼當前執行緒就可以不必阻塞直接獲取同步資源，從而避免切換執行緒的開銷。這就是自旋鎖，合理的引入自旋鎖能幫助我們優化執行緒切換的開銷。

使用公平鎖與非公平鎖來平衡飢餓與CPU上下文切換問題：

1. 公平鎖- 當多個執行緒搶佔同一個資源時，大家按先後順序排隊獲取，符合核心價值觀。帶來的好處是等待鎖的執行緒不會餓死，總會排到資源。缺點是整體吞吐效率相對非公平鎖要低，等待隊列中除第一個執行緒以外的所有執行緒都會阻塞，CPU喚醒阻塞執行緒的開銷比非公平鎖大。

2. 非公平鎖 – 當多個執行緒搶佔同一個資源時，資源釋放時哪個執行緒發起了搶佔就給哪個執行緒，可以理解為插隊，但程式設計師允許他插隊。這樣做可以減少喚起執行緒的開銷，整體的吞吐效率高，因為執行緒有幾率不阻塞直接獲得鎖，CPU不必喚醒所有執行緒。缺點是處於等待隊列中的執行緒可能會餓死，或者等很久才會獲得鎖。

智慧鎖

文章寫到這裡會發現鎖對程式設計師很不友好，小明只想實現一個簡單的並發功能，結果考慮用什麼鎖就耗費了幾天。好在程式設計師都喜歡封裝程式碼，比如JAVA官方就封裝了一套好用的"智慧鎖"，不用考慮過多細節，直接用。他的實現原理大致如下：

1. 偏向鎖 – 當執行緒A訪問臨界資源時，系統會為執行緒A加上偏向鎖，"偏向於第一個獲得它的執行緒"的鎖。執行數據更新之後，執行緒並不會釋放偏向鎖，第二次再訪問該臨界資源時就不用加鎖了，可以理解為超級通行證，如果至始至終都沒有其他執行緒來搶佔資源，偏向鎖性能極高。

2. 輕量級鎖 – 當有其他執行緒B來搶佔資源時，偏向鎖就升級為輕量級鎖。B會通過自旋去判斷A執行緒是否釋放了資源。此時有兩種可能，一是A執行緒被銷毀了，那麼B自動成為偏向鎖。二是A執行緒還存在，那麼A執行緒會升級為輕量級鎖，B執行緒等待A執行緒釋放資源。

3. 重量級鎖 – B執行緒的等待是有限度的，不能一直自旋。系統會判斷B執行緒的自旋次數，如果大於10次會將B執行緒升級為重量級鎖。其他執行緒必須釋放鎖然後掛起，等B執行緒更新完數據並釋放鎖後再繼續執行。

通過這種智慧鎖，程式設計師幾句程式碼就能享受安全，高效的鎖。

最後

鎖的原理並不難，但實現起來不容易。主要原因是程式設計師多年培養的編程思維都是基於順序執行的，如果用順序執行的思維方式去寫並發執行的程式碼很容易踩坑。

說下並發編程的三個概念和對應的挑戰：

1. 原子性問題 – 即一個操作或者多個操作要麼全部執行，要麼就都不執行，並且執行的過程不會被任何因素打斷，通常原子性問題要通過硬體來實現，比如CAS。需要對硬體指令了解。

2. 可見性問題 – 當多個執行緒訪問同一個變數時，一個執行緒修改了這個變數的值，其他執行緒能夠立即看得到修改的值。比如執行`100-1`後其他執行緒看到的是不是99？大部分情況下是99，但在某些極端情況下會出問題，比如CPU多級快取中的某一級快取返回的快取值為100。需要對CPU的快取機制熟悉。

3. 有序性問題 – 通常程式會按順序執行，但原始程式通過編譯器優化或者CPU指令重排後可能不會按照我們程式碼的順序執行，特別是在並發執行的程式碼下。需要對編譯器和CPU指令重排熟悉。

那些精通並發編程的大神，真的可以封神。

家中尚有餘糧-無需打賞