自旋鎖spinlock剖析與改進
1， spinlock介紹
spinlock又稱自旋鎖，線程通過busy-wait-loop的方式來獲取鎖，任時刻只有一個線程能夠獲得鎖，其他線程忙等待直到獲得鎖。spinlock在多處理器多線程環境的場景中有很廣泛的使用，一般要求使用spinlock的臨界區盡量簡短，這樣獲取的鎖可以盡快釋放，以滿足其他忙等的線程。Spinlock和mutex不同，spinlock不會導致線程的狀態切換(用戶態->內核態)，但是spinlock使用不當(如臨界區執行時間過長)會導致cpu busy飆高。
2， spinlock與mutex對比
2.1，優缺點比較
spinlock不會使線程狀態發生切換，mutex在獲取不到鎖的時候會選擇sleep。
mutex獲取鎖分為兩階段，第一階段在用戶態采用spinlock鎖總線的方式獲取一次鎖，如果成功立即返回；否則進入第二階段，調用系統的futex鎖去sleep，當鎖可用后被喚醒，繼續競爭鎖。
Spinlock優點：沒有昂貴的系統調用，一直處于用戶態，執行速度快。
Spinlock缺點：一直占用cpu，而且在執行過程中還會鎖bus總線，鎖總線時其他處理器不能使用總線。
Mutex優點：不會忙等，得不到鎖會sleep。
Mutex缺點：sleep時會陷入到內核態，需要昂貴的系統調用。
2.2，使用準則
Spinlock使用準則：臨界區盡量簡短，控制在100行代碼以內，不要有顯式或者隱式的系統調用，調用的函數也盡量簡短。例如，不要在臨界區中調用read,write,open等會產生系統調用的函數，也不要去sleep；strcpy，memcpy等函數慎用，依賴于數據的大小。
3， spinlock系統實現
spinlock的實現方式有多種，但是思想都是差不多的，現羅列一下：
3.1，glibc-2.9中的實現方法：
{
asm ("\n"
"1:\t" LOCK_PREFIX "decl %0\n\t"
"jne 2f\n\t"
".subsection 1\n\t"
".align 16\n"
"2:\trep; nop\n\t"
"cmpl $0, %0\n\t"
"jg 1b\n\t"
"jmp 2b\n\t"
".previous"
: "=m" (*lock)
: "m" (*lock));
return 0;
}
執行過程：
1，lock_prefix 即 lock。lock decl %0，鎖總線將%0(即lock變量)減一。Lock可以保證接下來一條指令的原子性。
2， 如果lock=1，decl的執行結果為lock=0，ZF標志位為1，直接跳到return 0；否則跳到標簽2。也許要問，為啥能直接跳到return 0呢？因為subsection和previous之間的代碼被編譯到別的段中，因此jne之后緊接著的代碼就是 return 0 (leaveq;retq)。Rep nop在經過編譯器編譯之后被編譯成 pause。
3， 如果跳到標簽2，說明獲取鎖不成功，循環等待lock重新變成1，如果lock為1跳到標簽1重新競爭鎖。
該實現采用的是AT&T的匯編語法，更詳細的執行流程解釋可以參考“五竹”大牛的文檔。
3.2，系統自帶(glibc-2.3.4)spinlock反匯編代碼：
系統環境：
(gdb) disas pthread_spin_lock
Dump of assembler code for function pthread_spin_lock:
//eax寄存器清零，做返回值
0x0000003056a092f0 <pthread_spin_lock+0>: xor %eax,%eax
//rdi存的是lock鎖地址，原子減一
0x0000003056a092f2 <pthread_spin_lock+2>: lock decl (%rdi)
//杯了個催的，加鎖不成功，跳轉，開始busy wait
0x0000003056a092f5 <pthread_spin_lock+5>: jne 0x3056a09300 <pthread_spin_lock+16>
//終于夾上了…加鎖成功，返回
0x0000003056a092f7 <pthread_spin_lock+7>: retq
……………………………………….省略若干nop……………………………………….
0x0000003056a092ff <pthread_spin_lock+15>: nop
//pause指令降低CPU功耗
0x0000003056a09300 <pthread_spin_lock+16>: pause
//檢查鎖是否可用
0x0000003056a09302 <pthread_spin_lock+18>: cmpl $0×0,(%rdi)
//回跳，重新鎖總線獲取鎖
0x0000003056a09305 <pthread_spin_lock+21>: jg 0x3056a092f2 <pthread_spin_lock+2>
//長夜漫漫，愛上一個不回家的人，繼續等~
0x0000003056a09307 <pthread_spin_lock+23>: jmp 0x3056a09300 <pthread_spin_lock+16>
0x0000003056a09309 <pthread_spin_lock+25>: nop
……………………………………….省略若干nop……………………………………….
End of assembler dump.
Glibc的匯編代碼還是很簡潔的，沒有多余的代碼。
4， Pause指令解釋（from intel）：
Description
Improves the performance of spin-wait loops. When executing a “spin-wait loop,” a Pentium 4 or Intel Xeon processor suffers a severe performance penalty when exiting the loop because it detects a possible memory order violation. The PAUSE instruction provides a hint to the processor that the code sequence is a spin-wait loop. The processor uses this hint to avoid the memory order violation in most situations, which greatly improves processor performance. For this reason, it is recommended that a PAUSE instruction be placed in all spin-wait loops.
提升spin-wait-loop的性能，當執行spin-wait循環的時候，笨死和小強處理器會因為在退出循環的時候檢測到memory order violation而導致嚴重的性能損失，pause指令就相當于提示處理器哥目前處于spin-wait中。在絕大多數情況下，處理器根據這個提示來避免violation，藉此大幅提高性能，由于這個原因，我們建議在spin-wait中加上一個pause指令。
名詞解釋(以下為本人猜想)：memory order violation，直譯為-內存訪問順序沖突，當處理器在(out of order)亂序執行的流水線上去內存load某個內存地址的值(此處是lock)的時候，發現這個值正在被store，而且store本身就在load之前，對于處理器來說，這就是一個hazard，流水流不起來。
在本文中，具體是指當一個獲得鎖的工作線程W從臨界區退出，在調用unlock釋放鎖的時候，有若干個等待線程S都在自旋檢測鎖是否可用，此時W線程會產生一個store指令，若干個S線程會產生很多load指令，在store之后的load指令要等待store在流水線上執行完畢才能執行，由于處理器是亂序執行，在沒有store指令之前，處理器對多個沒有依賴的load是可以隨機亂序執行的，當有了store指令之后，需要reorder重新排序執行，此時會嚴重影響處理器性能，按照intel的說法，會帶來25倍的性能損失。Pause指令的作用就是減少并行load的數量，從而減少reorder時所耗時間。
An additional function of the PAUSE instruction is to reduce the power consumed by a Pentium 4 processor while executing a spin loop. The Pentium 4 processor can execute a spin-wait loop extremely quickly, causing the processor to consume a lot of power while it waits for the resource it is spinning on to become available. Inserting a pause instruction in a spin-wait loop greatly reduces the processor’s power consumption.
Pause指令還有一個附加作用是減少笨死處理器在執行spin loop時的耗電量。當笨死探測鎖是否可用時，笨死以飛快的速度執行spin-wait loop，導致消耗大量電量。在spin-wait loop中插入一條pause指令會顯著減少處理器耗電量。
This instruction was introduced in the Pentium 4 processors, but is backward compatible with all IA-32 processors. In earlier IA-32 processors, the PAUSE instruction operates like a NOP instruction. The Pentium 4 and Intel Xeon processors implement the PAUSE instruction as a pre-defined delay. The delay is finite and can be zero for some processors. This instruction does not change the architectural state of the processor (that is, it performs essentially a delaying no-op operation).
該指令在笨死中被引入，但是向后兼容所有IA-32處理器，在早期的IA-32處理器中，pause指令以nop的方式來運行，笨死和小強以一個預定義delay的方式來實現pause，該延遲是有限的，在某些處理器上可能是0，pause指令并不改變處理器的架構（位？）狀態（也就是說，它是一個延遲執行的nop指令）。至于Pause指令的延遲有多大，intel并沒有給出具體數值，但是據某篇文章給出的測試結果，大概有38~40個clock左右（官方數字：nop延遲是1個clock），一下子延遲40個clock，intel也夠狠的。
This instruction’s operation is the same in non-64-bit modes and 64-bit mode.
該指令在64位與非64位模式下的表現是一致的。
5， spinlock改進
根據上一小節的分析，pause指令最主要的作用是減低功耗和延遲執行下一條指令。所以我們可以有這樣的猜想：如果在spin-wait的過程中，記錄下加鎖失敗的次數，對失敗的加鎖行為進行懲罰(failure penalty)，讓等待時間和失敗次數成正比，即失敗次數越多等待時間越長、執行的pause指令越多。
- 這樣的好處有：
A，在鎖競爭很激烈的情況下，通過增加延遲來降低鎖總線的次數，當鎖總線次數降低時，系統其它程序對內存的競爭減少，提高系統整體吞吐量。
B，在鎖競爭很激烈的情況下，減少計算指令的執行次數，降低功耗，低碳低碳！！！
C，當鎖競爭不激烈時，還能獲得和原來一樣的性能。
- 但是帶來的問題有：
A，如果競爭鎖失敗次數越多，pause次數越多的話，會導致有些線程產生starvation。
B，在某些特殊的場景下，鎖競爭很小的時候，failure penalty可能會導致程序執行時間變長，進而導致總的加鎖次數不一定減少。
- 解決方案：
當失敗次數超過一個閾值的時候，將失敗次數清零，使線程以潔白之軀重新參與競爭；對于少數failure penalty導致執行時間延長的情況，可以先忽略。
- 基于failure penalty的改進實現：
為了便于區分，起了很山寨的名字叫newlock，對比對象是sim_spin_lock，sim_spin_lock與pthread_spin_lock算法一致，實現細節基本一致，之所以加入這種對比是為了更加精確地衡量新算法的效果。ecx寄存器記錄下本次加鎖過程的失敗次數。
__asm__(
//eax清零，記錄當前lock次數
"xor %%eax,%%eax\n\t"
//ecx清零，記錄總的lock次數
"xor %%ecx,%%ecx\n\t"
//記錄加鎖次數
"1:incl %%ecx\n\t"
//記錄當前加鎖次數
"incl %%eax\n\t"
//鎖總線，開始加鎖，rdi寄存器存儲的是lock變量的地址
"lock decl(%%rdi)\n\t"
//加鎖不成功
"jne 2f\n\t"
//加鎖成功，將鎖總線次數作為返回值返回
"movl %%ecx,%%eax\n\t"
"leave\n\t"
"retq\n\t"
"nop\n\t"
"nop\n\t"
//pause跳轉標簽
"5:pause\n\t"
"4:pause\n\t"
"3:pause\n\t"
"2:pause\n\t"
//探測鎖是否可用
"cmpl $0x0,(%%rdi)\n\t"
//鎖可用，重新加鎖
"jg 1b\n\t"
//加鎖次數與4取模
"and $0x3,%%eax\n\t"
//根據結果進行跳轉
"cmpl $0x0,%%eax\n\t"
"je 2b\n\t"
"cmpl $0x1,%%eax\n\t"
"je 3b\n\t"
"cmpl $0x2,%%eax\n\t"
"je 4b\n\t"
"je 5b\n\t"
"nop\n\t"
"nop\n\t"
:
:"D"(lock)
:"%eax","%ecx","%edx");
}
- 與pthread_spin_lock算法相同的sim_spin_lock:
__asm__(
//eax清零，記錄當前lock次數
"xor %%eax,%%eax\n\t"
//ecx清零，記錄總的lock次數
"xor %%ecx,%%ecx\n\t"
//記錄加鎖次數
"1:incl %%ecx\n\t"
//記錄當前加鎖次數
"incl %%eax\n\t"
//鎖總線，開始加鎖，rdi寄存器存儲的是lock變量的地址
"lock decl(%%rdi)\n\t"
//加鎖不成功
"jne 2f\n\t"
//加鎖成功，將鎖總線次數作為返回值返回
"movl %%ecx,%%eax\n\t"
"leave\n\t"
"retq\n\t"
"nop\n\t"
"nop\n\t"
//pause跳轉標簽
"2:pause\n\t"
//探測鎖是否可用
"cmpl $0x0,(%%rdi)\n\t"
//鎖可用，重新加鎖
"jg 1b\n\t"
"jmp 2b\n\t"
"nop\n\t"
"nop\n\t"
:
:"D"(lock)
:"%eax","%ecx","%edx");
}
6， 性能對比
- 測試環境：
處理器：8Core Intel(R) Xeon(R) CPU E5410 @ 2.33GHz
Glibc版本：glibc-2.3.4-2.43
GCC版本：3.4.6
- 測試程序：
#include <pthread.h>
#include <stdlib.h>
#include <sys/time.h>
#include "liblock.h"
#define MAX_LOOP 1000000
#define CODE_LEN 10
pthread_spinlock_t mylock;
long g_count =0;
int thread_count =20;
int _nlock =0;
int lock_count =0;
int loop_count =1000000;
int code_len =1;
void*func(void*arg){
int j, k, m;
for(int i=0; i< loop_count; i++){
if(_nlock ==0){
lock_count += sim_spin_lock(&mylock);
//pthread_spin_lock(&mylock);
}else{
lock_count += newlock(&mylock);
//newlock(&mylock);
}
g_count++;
//下面這幾句代碼之間有很強的依賴性，流水hazard比較多
//每句代碼都要依賴上一句的執行結果，而且都是store操作
//用于模仿實際情況中的臨界區代碼
for(int i=0; i< code_len; i++){
j = k;
m = j;
k = m;
m = j+1;
k = m+2;
j = m+k;
}
pthread_spin_unlock(&mylock);
}
return NULL;
}
int get_process_time(struct timeval *ptvStart)
{
struct timeval tvEnd;
gettimeofday(&tvEnd,NULL);
return ((tvEnd.tv_sec - ptvStart->tv_sec)*1000+(tvEnd.tv_usec - ptvStart->tv_usec)/1000);
}
int main(int argc, char*argv[]){
if(argc <3){
return0;
}
int ms_time =0;
struct timeval tvStart;
_nlock = atoi(argv[1]);
thread_count = atoi(argv[2]);
loop_count = atoi(argv[3]);
code_len = atoi(argv[4]);
pthread_t *tid = (pthread_t*)malloc(sizeof(pthread_t)*thread_count);
pthread_spin_init(&mylock, 0);
gettimeofday(&tvStart,NULL);
for(int i=0; i<thread_count; i++){
pthread_create(&tid[i], NULL, func, NULL);
}
void*tret;
for(int i=0; i<thread_count; i++){
int ret = pthread_join(tid[i], &tret);
if(ret !=0){
printf("cannot join thread1");
}
}
ms_time = get_process_time(&tvStart);
fprintf(stderr, "g_count:%ld\tlock_count:%ld\tloop_count:%d\tcode_len:%d\ttime:%.2f\n", \
g_count, lock_count, loop_count, code_len, ms_time/1000.0f);
return0;
}
- Benchmark設置：
>輸入參數：
線程數量：1，2，3，5，7，8，10，12，14，16，18，20，25，30，35，40
每個線程加鎖（循環）次數：5000000
臨界區長度：1，1+1*6，1+3*6，1+5*6，1+10*6，1+20*6，1+50*6，1+100*6
case執行次數：每個case執行10次，盡量減少誤差
> 輸出參數：
執行時間：平均執行時間
鎖總線次數：平均鎖總線次數
- 執行時間對比：
- 鎖總線次數對比：
還有若干圖，囿于篇幅和時間，親們我就不貼了
7， 實驗結果分析
- 定義：
競爭因子：競爭因子=線程數量/處理器個數。以本文為例，假設有16個線程，處理器為8核，那么競爭因子為2
- 競爭因子與執行時間的關系：
當競爭因子為1/8，也就是只有一個線程的時候，很明顯兩種算法的執行時間是一致的，因為此時沒有其他線程競爭鎖；當競爭因子在1/8~4/8之間的時候，在某些情況下（依賴于臨界區長度）新算法性能低于老算法；當競爭因子大于4/8的時候，新算法性能優于老算法。
- 競爭因子與鎖總線次數的關系：
當競爭因子為1/8的時候，新老算法一致（原理同上）；當競爭因子在1/8~4/8之間的時候，大部分情況下老算法性能優于新算法；當競爭因子大于4/8的時候，新算法性能優于老算法，由于鎖總線次數基數比較大，在圖上可能比較難看出來。
- 拐點：
細心的同學可能會發現有一個拐點：就是當臨界區的長度為 1+50*6 的時候，也就是臨界區有300行代碼的時候，新算法鎖總線次數要比老算法多，而且執行時間也長一些，這就牽扯到新算法的一個缺點：在某些情況下，當鎖可用，需要去競爭鎖的時候，由于線程還在pause中，只有等pause結束才能去競爭，而pause結束時，鎖很可能不可用（被其他線程獲取），根據新算法，加鎖失敗線程又要多pause一次，導致整體的鎖總線次數和執行時間增加。這個拐點依賴于競爭因子、具體的處理器、具體的臨界區代碼、pause執行周期。
- 不足：
由于時間的關系，試驗做的不是很足；指令回避那塊可以做優化（目前只是簡單的cmpl和jmp）；到底最大pause次數是多少需要試驗來支撐，目前是4次；個人感覺pause的處理器實現粒度還是比較粗的，應該是intel的一個經驗值，接下來的試驗可以用nop來代替pause，這樣得出來的數據應該會更為平滑一些，控制也更為細膩。
- 總結：
當競爭比較激烈的時候，新算法在絕大部分情況下優于老算法（除了拐點），大概有2-5%的提升；當處理器競爭比較小的時候，尤其是競爭因子為3/8的時候，新算法不如老算法；如果用nop替代pause應該會有更好的表現。
留言列表
