線程1和2在執行Lamport的烘焙算法時非常重視

Question

我正在實施Lamport's bakery algorithm。

我的輸出顯示線程1和2比其他線程要優先。我的實施如下。

#include(pthread.h) 
#include(stdio.h> 
#include(unistd.h> 
#include (assert.h> 
volatile int NUM_THREADS = 10; 
volatile int Number[10] = {0}; 
volatile int count_cs[10] = {0}; 
volatile int Entering[10] = {0}; 

int max() 
{ 
    int i = 0; 
    int j = 0; 
    int maxvalue = 0; 
    for(i = 0; i < 10; i++) 
    { 
     if ((Number[i]) > maxvalue) 
     { 
       maxvalue = Number[i]; 
     } 
    } 
    return maxvalue; 
} 

lock(int i) 
{ 
    int j; 
    Entering[i] = 1; 
    Number[i] = 1 + max(); 
    Entering[i] = 0; 
    for (j = 1; j <= NUM_THREADS; j++) 
    { 
     while (Entering[j]) { } /* Do nothing */ 
     while ((Number[j] != 0) && 
       ((Number[j] < Number[i]) || 
       ((Number[j] == Number[i]) && (j < i)))) { } 
    } 
} 

unlock(int i) { 
    Number[i] = 0; 
} 

void Thread(int i) { 
    while (1) { 
     lock(i); 
     count_cs[i+1] = count_cs[i+1] + 1 ; 
     //printf("critical section of %d\n", i+1); 
     unlock(i); 
    } 
} 

int main() 
{ 
    int duration = 10000; 
    pthread_t threads[NUM_THREADS]; 
    int rc; 
    long t; 
    for(t = 0; t < NUM_THREADS; t++){ 
     printf("In main: creating thread %ld\n", t+1); 
     rc = pthread_create(&threads[t], NULL, Thread, (int)t); 
     if (rc){ 
      printf("ERROR; return code from pthread_create() is %d\n", rc); 
      exit(-1); 
     } 
    } 
    usleep(duration*1000); 
    for(t=0; t < NUM_THREADS; t++) 
    { 
    printf("count of thread no %d is %d\n",t+1,count_cs[t+1]); 
    } 
    return 0; 
} 

如果我在臨界區打印某些值，那麼對於所有線程我都會得到幾乎相同的計數值。爲什麼我在輸出中得到這種改變？

輸出，而不在關鍵部分print語句：

count of thread no 1 is 5 
count of thread no 2 is 6 
count of thread no 3 is 5 
count of thread no 4 is 5 
count of thread no 5 is 5 
count of thread no 6 is 5 
count of thread no 7 is 4 
count of thread no 8 is 4 
count of thread no 9 is 4 
count of thread no 10 is 4 

爲了避免內存模型問題，我限制我的線程來單：

count of thread no 1 is 551013 
count of thread no 2 is 389269 
count of thread no 3 is 3 
count of thread no 4 is 3 
count of thread no 5 is 3 
count of thread no 6 is 3 
count of thread no 7 is 3 

count of thread no 8 is 3 
count of thread no 9 is 3 
count of thread no 10 is 3 

在關鍵節報表打印輸出CPU並使用taskset 0x00000001 ./a.out在Linux上運行我的程序。

Answer 1

這有幾個問題。

首先，pthread_create需要很多時間：當然比快速鎖定/增加計數/解鎖迭代更重要。因此，第一個線程比其他線程有更大的優勢，因爲它首先運行，第二個線程獲得更小的優勢，等等。當您將printf固定在循環中時，這會減慢線程的速度，因此優勢更小。

在相關說明中，僅僅因爲pthread_create已返回，線程並不一定開始。這只是意味着調度程序現在會考慮它。

第三，你的鎖實現是一個繁忙的等待循環。因此，無論哪個線程正在運行，它都會佔用所有可用的CPU時間。由於您正在單核上運行您的代碼，因此如果擁有該鎖的線程被掛起，那麼其他線程將花費所有時間片忙於等待，然後帶鎖的線程可以恢復，解鎖，嘗試並獲取再次鎖定。

最後，在鎖的爭用情況下，該算法優先考慮數字最小的線程，所以線程0將獲得比其他線程更多的鎖，因爲所有線程都在忙於等待，因此在那裏是很高的爭議。

嘗試在lock()的循環中放入一些sched_yield()調用，以允許帶鎖的線程有更多機會運行。

Answer 2

我看到您正在單個CPU上運行，因此您正在避免以下問題。不過，記住它。

請注意，與Microsoft的編譯器不同，GCC不會給volatile提供特殊的非標準SMP線程含義。因此你不能依靠它來在CPU之間進行排序。這意味着，如果假設Number和Entering位於不同的高速緩存行上，則CPU-0可以自由寫入Number和Entering，它們的排列順序與您認爲它們寫入的順序不同。

要解決這個問題，你需要使用原子操作。海灣合作委員會已經建立了這些。