一個無鎖消息隊列引發的血案：怎樣做一個真正的程序員？（一）——地：起因
一個無鎖消息隊列引發的血案：怎樣做一個真正的程序員？（二）——月：自旋鎖
在復制好上面那一行我就先停下來了，算是先占了個位置，雖然我知道大概要怎麼寫，不過感覺還是很亂。
我突然想到，既然那麼糾結，那麼混亂，那麼不知所措，我們不如換個視角。記得高中時看過的為數不多的長篇小說《穆斯林的葬禮》，作者是：霍達（女），故事描寫了兩個發生在不同時代、有著不同的內容卻又交錯扭結的愛情悲劇，一個是“玉”的故事，一個是“月”的故事。結構上采取交叉的模式，一章寫“玉”，一章寫“月”，分別寫兩代人的命運，手法新穎，別有一番風味，用電影語言來講，就是平行蒙太奇。用在這裡再好不過了，就這麼決定了！
之所以會想到這個，源自於昨天下午還沒開始寫第一篇後半部分之前，我本著對讀者負責的態度，特意搜索了一下“自旋鎖”這個關鍵詞，雖然說不陌生，但想到從來沒有通過搜索引擎認真研究過這個詞，還是有些必要。搜索的結果，有用的信息的確並不多(不是說完全沒用，是基本沒用)，但有一條還是不錯的，這也給我解釋自旋鎖提供了良好的思路和理論依據。
這篇文章就是《自旋鎖代替互斥鎖的實踐》，這是一篇譯文，原文的鏈接是：Practice of using spinlock instead of mutex ，說句題外話，昨天我研究 disruptor ，搜索的一些重要的文章也是在 並發編程網(ifeve.com) ，而且 disruptor 更新了，文章也會跟著更新，雖然跟不上 disruptor 的更新速度：（
這裡解釋一下，我把兩個時空定義為：“地球”和“月球”，地球：喧鬧而嘈雜，到處充滿著競爭，這條線主要寫事情的經過和free-lock(無鎖編程)，我偶爾也會噴一下人；月球：代表著寧靜和理性，杳無人跡，也遠離那些塵世的紛爭，這條線主要描述自旋鎖（混合自旋鎖，hybrid spinlocks），同時，月亮也是一種美的象征（我本來想選火星，可是火星太不美了……而且“火星人”別有他意，你懂的）。
好啦，我們開始吧，菠蘿菠蘿蜜！
你好，歡迎來到月球。
下面我們來談一談自旋鎖。為什麼要談自旋鎖，我們之前不是在講無鎖消息隊列嗎？對的，可是分析了 q3.h 後，發現其實其大致相當於兩個自旋鎖在運作。
至於為什麼相當於兩個自旋鎖，我們後面再講，先來研究一下 互斥鎖(mutex locks) 和 自旋鎖(spin locks)。
互斥鎖 和 自旋鎖 是 多線程編程 中的重要概念。我們用它們來鎖住一些共享資源，以防止並發訪問這些共享數據時可能導致的數據不一致性問題。但是它們的不同之處在哪裡？ 我們應該在什麼時候用 自旋鎖 來代替 互斥鎖 呢？
我們在使用 互斥鎖 的時候，假設 互斥鎖 已經被某個線程持有（鎖住了），那麼另一個線程在嘗試加鎖的時候會失敗，然後進入休眠狀態以等待其他線程的運行。這個線程會一直休眠到持有鎖的線程釋放了鎖以後，才會被喚醒。那麼我們來看看 自旋鎖，如果一個線程在嘗試持有一個 自旋鎖 的時候，如果持有沒有成功（即有其他線程已經先持有該鎖了，已鎖住了），該線程會一直嘗試持有改鎖（通過在用戶態自旋實現的），那麼它將不允許其他線程在該線程所在的CPU核心上運行，因為一個核心同一時刻只能跑一個線程（當然，操作系統可以通過中斷或線程的時間片用完後強制轉換到別的線程上運行）。
互斥鎖 存在的問題是，線程的休眠和喚醒都是相當昂貴的操作，它們需要大量的CPU指令，因此需要花費一些時間。如果 互斥量 僅僅被鎖住很短的一段時間，用來使線程休眠和喚醒線程的時間會比該線程睡眠的時間還長，甚至有可能比不斷在 自旋鎖 上輪訓的時間還長。而 自旋鎖 的問題是，如果 自旋鎖 被持有的時間過長，其它嘗試獲取 自旋鎖 的線程會一直輪訓自旋鎖的狀態，這將非常浪費CPU的執行時間，很關鍵的一點是這些浪費的輪訓時間都是無用功，這時候該線程睡眠會是一個更好的選擇。
在 單核 / 單CPU 的系統上使用 自旋鎖 是沒有意義的，因為它就一個運行線程/核心，你占著不放，那麼其他線程將得不到運行，其他線程得不到運行，這個鎖就不能被解鎖。換句話說，在 單核 / 單CPU 系統使用 自旋鎖，除了浪費點時間外沒有一點好處。這時如果讓這個線程（記為線程A）休眠，其他線程就得以運行，然後就可能會解鎖這個 自旋鎖，線程A就可能在重新被喚醒後，如願以償的持有鎖。
在 多核 / 多CPU 的系統上，特別是大量的線程只會短時間的持有鎖的時候，這時如果使用 互斥鎖，在使線程睡眠和喚醒上浪費大量的時間，也許會顯著降低程序的運行性能。使用 自旋鎖，線程可以充分利用系統調度程序分配的時間片(經常阻塞很短的時間，不用休眠，然後馬上繼續它們後面的工作了)，以達到更高的處理能力和吞吐量。
程序員往往並不能事先知道哪種方案更好，比如，不知道運行環境CPU的核心數，不能很好的預估被鎖區域的持續時間。操作系統也不能分辨哪些指令是特別針對單核或多核CPU做過優化的，所以大部分操作系統不嚴格區分 互斥鎖 和 自旋鎖 。實際上，絕大多數現在操作系統采用的是 混合型互斥鎖 (hybrid mutexes) 和 混合型自旋鎖 (hybrid spinlocks)。 它們是什麼意思呢？
混合型互斥鎖，在多核系統上，它的表現起初跟 自旋鎖 一樣，如果一個線程不能獲取(持有) 互斥鎖，它不會馬上進入休眠狀態，因為互斥量可能很快就被解鎖，所以這時表現得跟 自旋鎖 一樣。只有當嘗試一段時間以後(或者一定次數，或其他指標)，還不能持有改鎖，它就會被切換到休眠狀態。如果運行在 單核/單CPU 的系統上時，這種機制將不會自旋，也不該自旋（原因就像前面講的，一點好處都沒有）。
最好的例子就是Windows上的臨界區，有一個 API 叫 InitializeCriticalSectionAndSpinCount(mutex, dwSpinCount)，該函數的 dwSpinCount 值，Windows 默認推薦是 4000 (相信很多熟悉Windows開發的人都知道)，即自旋 4000 次，而這 4000 次是怎麼自旋的，以何種指令的形式自旋我們不得而知，但是它的確是先嘗試自旋 dwSpinCount 次後仍未能夠持有 互斥量 才真正進入休眠狀態。
混合型自旋鎖，起初表現得跟正常的 自旋鎖 一樣，但是為了避免浪費大量的CPU時間做無用功，會有一個折中的策略。這個策略有可能不會切換到休眠狀態或者盡量很晚才切換到休眠狀態，先自旋一段時間，自旋多久，以何種形式自旋將是這種類型自旋鎖的核心之一；此外，另一個更核心的內容是，你還可以決定是否放棄當前線程的執行(馬上放棄或等一段時間再放棄，等的時間由自旋策略決定)，把時間片讓給別的線程，這樣提高了別的線程解鎖 自旋鎖 的可能性（當然，線程切換導致上下文的切換甚至可能切換到別的CPU核心上從而導致緩存失效，這可能並不一定比線程進入休眠再喚醒的時間短，這個很難權衡，但是好處是其他線程得以運行，你進入休眠後讓出時間片，本質上也會遇到同樣的問題）。
作者自己寫的 RingQueue 裡用的就是這種 混合型自旋鎖，只是 混合型自旋鎖 裡講究的是休眠的策略，策略不同，CPU的占用率，執行效率都有很大區別。例如，著名的 Intel 多線程並行庫 tbb (Intel Threading building blocks) 裡的 spin_mutex(即spin_lock) 采用的是 spin_count *= 2，自旋次數依次增大兩倍，而休眠策略則在 Windows 下是 SwitchToThread() (這個有很大的缺陷，以後會講)，Linux下是 sched_yiled() (Linux下使用這個合理很多，但是那個但……，也不足夠好，從細節上來說，Windows 和 Linux 下都各有優劣，且都存在缺陷，後面會說到，不過這個函數的好處就是基本Linux只有這麼一個接口，而不像Windows下細節太多且不全面而容易出現致命的缺陷)
再比如 pthread 裡的 pthread_spin_lock()，不過這是個不折不扣的 自旋鎖，沒有休眠策略。然後還有 boost 裡提供的幾個 spin_lock，boost/smart_ptr下面有一個，策略還是比較得當的，自旋策略正常，但是Windows下，使用了Sleep(0)和Sleep(1)，而沒使用SwitchToThread()，另外一個地方，好像是 boost/log 下面的，休眠策略只使用了 SwithToThread()，而沒有Sleep(0)和Sleep(1)。當然還有 Facebook 的 folly 裡的 SpinLock.h 和 SmallLocks.h，自旋策略OK，但休眠策略使用的類似Sleep(1)的形式。
混合型自旋鎖 的性能好壞直接由你將要鎖住的資源的處理時間長短，以及你的 自旋鎖 的具體休眠策略而決定，性能好壞可能很難界定，不過還是能給出一些相對硬性的指標，比如 總體運行時間 和 總的CPU占用率，雖然這兩個指標是相互矛盾的，但是如果你的運行時間短，占用CPU的比率又低，那肯定就是更好的 自旋鎖 啦，也就是我們常說的，既想牛兒吃的是草，又想牛兒擠出的是牛奶，效率上最低不能低於 互斥鎖，這也是檢驗 混合型自旋鎖 優劣的一個參考指標。
好了，今天就寫到這裡，我也要開始休眠了。其實昨天晚上我研究了一晚上 disruptor，因此耽誤了寫這篇文章的時間。你在看上面文章內容的時候，肯定會在想，為什麼要用 自旋鎖 或 互斥鎖，我用 disruptor 不是更好嗎？通過我的理解和研究，事實上並不是那樣的，disruptor 好是好，但是是有局限的，它並沒有規避多線程編程的真正問題，它只是把問題簡化，盡量使用單線程，或最大程度的避免緩存、總線和資源間的爭用，盡量使用單一線程來處理問題。所以它是鼓勵使用 單生產者 模式的，這樣就有效的規避了一些多線程爭用的問題，所以我用 disruptor 嘗試了 多生成者，多消費者 的模式，試驗的結果跟一般的自旋鎖沒有太大的區別，可能線程數多了，還要更慢一些，所以 disruptor 的解決方案和我們的問題基本上可以講是兩個不同的命題，不是一個維度的東西，雖然看起來好像有那麼一點雷同。但是兩者都可以相互借鑒，disruptor 裡面也定義了很多休眠策略，可是實際的效果並不理想。關於 disruptor，以後可能會花一點篇幅來講。
RingQueue 的GitHub地址是：https://github.com/shines77/RingQueue，也可以下載UTF-8編碼版：https://github.com/shines77/RingQueue-utf8。 我敢說是一個不錯的混合自旋鎖，你可以自己去下載回來看看，支持Makefile，支持CodeBlocks， 支持Visual Studio 2008, 2010, 2013等，還支持CMake，支持Windows, MinGW, cygwin, Linux, Mac OSX等等，當然可能不支持ARM，沒測試環境。
（未完待續……敬請期待……）
