在互斥體實現中的死鎖和競態條件

我想在C中使用原子組裝指令「bts」實現一個互斥體，以原子方式設置一個位並返回原始值。然而，當我運行下面的代碼，它偶爾會死鎖和常可見競爭條件：在互斥體實現中的死鎖和競態條件

#include <stdio.h> 
#include <stdlib.h> 
#include <pthread.h> 

typedef unsigned char mutex; 
#define MUTEX_FREE 0 
#define MUTEX_BUSY 1 

// adapted from http://www.acm.uiuc.edu/sigops/roll_your_own/i386/atomic.html 
mutex testAndSet(mutex *m) { 
    int result; 
    asm ("bts $0, %1; sbbl %0, %0" 
     :"=r" (result) 
     :"m" (*m) 
     :"memory"); 
    return (result & 1); 
} 

void P(mutex *m) { 
    // Must use atomic testAndSet to avoid race conditions 
    while(testAndSet(m) == MUTEX_BUSY) 
     usleep(10); 
} 

void V(mutex *m) { 
    *m = MUTEX_FREE; 
} 

////////////// 
// Test: 
////////////// 

const int NTHREADS = 100; 
const int NINCS = 100; 

int counter = 0; 
mutex m = MUTEX_FREE; 

void criticalSection() { 
    int i; 
    for(i=0;i<NINCS;i++) { 
     P(&m); 
     counter++; 
     V(&m); 
    } 
} 

int main() { 
    int i; 
    pthread_t threads[NTHREADS]; 
    for(i=0; i<NTHREADS; i++) { 
     pthread_create(&threads[i], NULL, (void *) &criticalSection, NULL); 
    } 
    for(i=0; i<NTHREADS; i++) { 
     pthread_join(threads[i], NULL); 
    } 
    printf("got counter=%d, expected=%d\n", counter, NTHREADS*NINCS); 
}

代碼似乎如果我使用了「xchgb」指令，而不是「BTS」的如下工作：

mutex testAndSet(mutex *m) { 
    unsigned char result = MUTEX_BUSY; 
    asm ("xchgb %1, %0" 
      :"=m" (*m), "=r" (result) 
      :"1" (result) 
      :"memory"); 
    return result; 
}

原始代碼中的競態條件在哪裏？「bts」指令不應該是原子的，保證線程安全嗎？

此外，我的修改解決方案實際上是否正確？

（我運行OS X 10.8和用gcc編譯。）

來源

2012-11-07 tba

你從哪裏讀到'bts'是原子的？（我對x86彙編不是很熟悉，但是我不記得讀過了。） – Mat

添加x86和彙編標記，以便獲得更多幫助 – RedComet

這裏是我讀「bts」是原子的地方（至少對於i386）：http://www.acm.uiuc.edu/sigops/roll_your_own/i386/atomic.html – tba

嘗試使用LOCK prefix鎖定內存總線：

asm ("lock bts $0, %1; ...");

的xchg指令工作，因爲它總是斷言LOCK#信號無論是否存在LOCK前綴。

來源

2012-11-07 20:13:45

在互斥體實現中的死鎖和競態條件

回答

相關問題