頭條楓林網
文章摘要： 鎖競爭benchmark 在這次測試中到每個執行緒必須100%的時間持有鎖
譯者按
Preshing 的部落格是學習併發程式設計的不可多得的資料，講解比較詳細。身邊的很多朋友從中受益良多。
我們在和作者溝通後，獲得了授權，著手翻譯了他的部落格，刊登在這裏，以饗朋友諸君。
和一般的翻譯不同，我們加上了獨家的註釋。註釋要麼是糾正錯誤，要麼是輔助理解，要麼是補充擴充套件；相信對大家會大有裨益。
正文翻譯：@Diting0x
審校 && 註釋：@睡眼惺忪的小葉先森
原文地址: Preshing
原文
鎖(也叫互斥量)在很長一段時間都被誤解了。1986年，在Usenet的有關於多執行緒的討論會中，Matthew Dillon說過：大多數人都對鎖有個誤解，認為鎖是慢的。25年後，這種誤解似乎在某一時間段又突然出現了。
在某些平臺上或者當鎖被高度競爭時，鎖確實慢。另外，當你在開發一個多執行緒程式時，由於鎖的引入，給效能帶來巨大的瓶頸是很常見的。但這並不意味著所有的鎖都是緩慢的。我會在這篇文章中解釋，有的時候，使用鎖的策略反而能帶來非常好的效能。
大家對鎖的誤解可能源自於某個最容易忽視的原因：不是所有的程式設計師都會意識到輕量級鎖和核心鎖的區別。我會在下一篇文章中對輕量級鎖做專門介紹:總是使用輕量級鎖。在這篇文章中，假設你在Windows平臺下做C/C++開發，你需要的正是一個Critical Section物件。
有時候，鎖是慢的這個結論是由benchmark支撐的。例如，這篇文章在高負載狀態下來測試鎖的效能：每個執行緒必須持有鎖來完成任何一項任務（高競爭），並且鎖都是在極短的時間間隔下被持有（高頻率）。這種方式似乎很完美，但在實際應用中，卻要避免這種使用鎖的方式注1。基於這種考慮，我設計了一種benchmark，同時包含對鎖使用的最壞情況和最好情況。
由於一些其它的考慮，大家可能不願意用鎖了。存在一系列的技術被稱為無鎖程式設計(或者不含鎖程式設計注2）。無鎖程式設計是極具挑戰性的，但其本身可以在許多實際應用場景下帶來高度的效能回報。據我所知，有些程式設計師會花費許多天甚至幾周的時間來設計某種無鎖演算法，之後再做一系列測試，但在幾個月後才發現隱藏的bug. 風險與回報並存對於相當一部分程式設計師都是有誘惑力的，這當然也包括我，在以後的幾篇文章中會提到這些。有了無鎖程式設計的誘惑，大家開始覺得鎖使用起來很枯燥，緩慢並且非常糟糕。
但也不能把鎖貶的一文不值。在現實軟體中，當大家爲了保護記憶體分配器的時候，鎖就是一個讓人敬仰的東西。Doug Lea的分配器是在遊戲開發中非常著名的記憶體分配器注3，但其只支援單執行緒，這時候我們就必須使用鎖機制來進行保護。在遊戲執行時，經常會碰到多個執行緒搶佔一個記憶體分配器，每秒鐘搶佔次數可達到15000次左右。在載入過程中，每秒鐘會達到100000次甚至更多。雖然這並不是個大問題。但你卻可以看到，鎖能非常出色的來處理這些負載。
鎖競爭benchmark
在這次測試中，我們建立一個執行緒來生成隨機數，採用傳統的Mersenne Twister生成器來實現。此執行緒時而獲取鎖，時而釋放鎖。獲取與釋放鎖的間隔時間是隨機的，但它都很接近我們提前決策出的平均值。舉個例子，假設我們要每秒鐘獲取鎖15000次，讓持有鎖的時間保持在總時間的50%. 下圖是部分的timeline。紅色說明鎖正在被持有，灰色說明鎖被釋放。
這是個泊松分佈過程。如果我們知道生成單個隨機數的平均時間–在2.66GHz的四核Xeon處理器上需要6.349ns–那麼我們用工作單元(work units）而不是秒來衡量時間。可以用我之前的文章中介紹的方法,How to Generate Random Timings for a Poisson Process,算出獲取與釋放鎖的時間間隔有多少個工作單元。下面程式碼是C++的實現。我省略了一些細節，喜歡的話，可以在 這裏 下載完整的原始碼
QueryPerformanceCounter(&start);
for (;;)
{
// Do some work without holding the lock
workunits = (int) (random.poissonInterval(averageUnlockedCount) + 0.5f);
for (int i = 1; i < workunits; i++)
random.integer(); // Do one work unit
workDone += workunits;
QueryPerformanceCounter(&end);
elapsedTime = (end.QuadPart - start.QuadPart) * ooFreq;
if (elapsedTime >= timeLimit)
break;
// Do some work while holding the lock
EnterCriticalSection(&criticalSection);
workunits = (int) (random.poissonInterval(averageLockedCount) + 0.5f);
for (int i = 1; i < workunits; i++)
random.integer(); // Do one work unit
workDone += workunits;
LeaveCriticalSection(&criticalSection);
QueryPerformanceCounter(&end);
elapsedTime = (end.QuadPart - start.QuadPart) * ooFreq;
if (elapsedTime >= timeLimit)
break;
}
現在假設我們執行兩個這樣的執行緒，每個執行緒執行在不同的CPU核心上。當執行任務時，每個執行緒有一半的時間是持有鎖的，但如果其中一個執行緒在另一個執行緒持有鎖的情況下試圖獲取鎖，此執行緒會被強制等待。這就是鎖競爭。
在我看來，這是鎖在實際程式中應用的非常好的例子。當我們執行上述的場景時，可以發現每個執行緒會花費25%的時間在等待，75%的時間在執行實際的任務。與單執行緒相比，兩個執行緒都獲得了1.5X的效能提升。
我在2.66GHZ的四核Xeon處理器上做過不同的測試，從一個執行緒到兩個執行緒，一直到最多四個執行緒的情況，每個執行緒都分別執行在不同的CPU核心上。同時，我還改變鎖被持有的時間，從鎖絕不被持有，到每個執行緒必須100%的時間持有鎖。在所有的case中，鎖頻率保持一個常數–在執行任務過程中，執行緒每秒鐘獲取鎖15000次。
結果很有意思。對於短的鎖持有時間，比如持有時間佔比<10%的情況, 系統可能達到很高的併發性。雖然不是最完美的併發，但很接近。說明鎖是非常快的！
爲了把結果解釋清楚一些，我用這個分析器分析了多執行緒遊戲引擎中的記憶體分配鎖.在遊戲執行時，每秒鐘有15000個鎖來自三個執行緒，鎖的持有時間在2%左右。正好落在圖表中左側的舒適區(comfort zone).
這些結果都表明一旦鎖持有時間超過90%，就沒有必要再使用多執行緒了。這時，單執行緒會表現的更好。同時，最讓人吃驚的是4個執行緒的效能都急劇下降到60%左右。這看起來像是個異常情況，所以我又重新執行這些測試很多次了，甚至還改變了測試順序。得到的結果卻是一樣的。我對此最好的解釋就是，測試可能觸碰到了Windows分配器的盲區，我沒有更進一步的去研究這個問題。
鎖頻率benchmark
一個輕量級鎖也會帶來開銷。正如我的下一篇文章中說的,對Windows Critical Section的lock/unlock成對操作會花費23.5ns（基於上述測試的CPU). 因此可以說明，每秒鐘有15000個鎖已經足夠少了，鎖的開銷並不會在很大程度上影響整個結果。但如果我們提高鎖頻率，又會發生什麼呢？
演算法中，嚴格控制鎖與鎖之間執行的任務數，因此我做了一系列新的測試：鎖與鎖的間隔時間從10ns到最高31ns(相對應每秒鐘大約32000次鎖).每次測試都使用兩個執行緒。
正如你想的那樣，鎖頻率很高的話，鎖本身的開銷就已經高於所執行的任務本身了. 在網上找到的一些benchmarks,包括前面提到的那個分析器， 都落在圖表中的右下角。在這些高頻率下，和一些CPU指令的規模一樣，鎖的間隔比較小。好訊息是，當鎖與鎖之間的任務比較簡單的時候，無鎖程式設計更可行。
與此同時，結果表明當鎖頻率達到每秒鐘32000次時（鎖間隔是3.1us)也是可以接受的。在遊戲開發中，記憶體分配器就可能會在載入過程中達到這個頻率。如果鎖間隔比較短暫，你仍然可以得到1.5X的併發度。
我們已經瞭解了一系列鎖效能的例子：有效能表現的很好的時候，也有效能慢的跟爬蟲似的時候。我已經證明了遊戲引擎中的記憶體分配器一直都能保持非常好的效能。把這個例子運用到實際場景中，不能說鎖是慢的。不得不承認，鎖很容易被濫用，但你不必太害怕–只要經過仔細的分析，任何情況下都能找出導致效能瓶頸的因素。當你正在考慮鎖有多可靠，並去理解鎖的相關優化方法時(相比無鎖程式設計)，鎖有時候表現的真的非常出色。
寫這篇文章的目的是爲了讓鎖得到應有的尊敬–歡迎批評指正。鎖在工業應用程式中有廣泛的應用，至於鎖的效能，並不總是能達到一個很好的均衡。如果你在自己的經驗中發現類似這樣的例子，非常樂意看到你的評論注4。
譯者注
註釋1:一種避免或者降低鎖衝突的科學思想是partition，避免資源集中。例如，對於hashtable，可以由之前的一個hashtable對應一把鎖，改為每個bucket配置一把鎖，這樣衝突將大大降低。再例如，計數程式，如果大家都對同一個全域性變數進行讀寫而加一把鎖，那麼衝突嚴重，可以適當的選擇多個計數器，不同的執行緒累加對應的計數器，一個執行緒負責將這些計數器的值求和。等等等等。
註釋2: 這裏的無鎖程式設計，原文為lock free。不含鎖程式設計，原文為lockless。但是需要注意的是，lock free並不是無鎖的意思，它的本質是說一組執行緒，總有（至少）一個執行緒能make progress，和有沒有鎖沒有本質聯絡。lock free目前一般都翻譯為無鎖（有些地方也翻譯為鎖無關），因此本文也採用這種譯法，但是讀者需要特別注意。另外lockless就是真正的無鎖、不包含鎖的程式設計。
註釋3: Doug Lea是併發程式設計的大牛，《Java併發程式設計實戰》的作者之一，非常樂意分享。他寫的這個分配器非常出名，glibc所採用的記憶體分配器實現就是基於他設計的演算法。
註釋4: 本文的描述和試驗可能讓人有點迷糊，這裏提供一下Paul E. McKenney大叔在他的著作《Is Parallel Programming Hard, And, If So, What Can You Do About It?》中第4章中的例子來解釋，讓讀者更好的理解：
pthread_rwlock_t rwl = PTHREAD_RWLOCK_INITIALIZER;
int holdtime = 0;
int thinktime = 0;
long long *readcounts;
int nreadersrunning = 0;
#define GOFLAG_INIT 0
#define GOFLAG_RUN 1
#define GOFLAG_STOP 2
char goflag = GOFLAG_INIT;
void *reader(void *arg)
{
int i;
long long loopcnt = 0;
long me = (long)arg;
__sync_fetch_and_add(&nreadersrunning, 1);
while (ACCESS_ONCE(goflag) == GOFLAG_INIT) {
continue;
}
while (ACCESS_ONCE(goflag) == GOFLAG_RUN) {
if (pthread_rwlock_rdlock(&rwl) != 0) {
perror("pthread_rwlock_rdlock");
exit(-1);
}
for(i=1;i
其中16-18行等待測試開始的訊號；19行開始測試；holdtime控制臨界區的長短，thinktime用來控制兩次申請鎖之間的間隔。測試的時候有三個變數：holdtime、thinktime、執行緒數（1個、2個、4個、直到核數的兩倍）。試試看。