Peterson算法的執行錯誤？

我想了解一些關於並行編程的知識，所以我試圖用一個簡單的例子來實現Peterson的算法，其中一個共享計數器增加了2個線程。我知道彼得森不是最佳的，因爲忙着等待，但我只是爲了學習的原因才嘗試過。Peterson算法的執行錯誤？

我認爲這段代碼的關鍵部分在線程函數add中共享counter遞增。所以我在計數器增量之前調用enter_section函數，之後我調用leave_function。這部分是錯的嗎？我評估了關鍵部分是否錯誤？問題在於，當這兩個線程完成時，計數器有時會給出不可預期的值。它必須是線程之間的同步問題，但我只是沒有看到它......感謝您的幫助。

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

int counter; /* global shared counter */ 
int flag[2] = {0, 0}; /* Variables for Peterson's algorithm */ 
int turn = 0; 

typedef struct threadArgs 
{ 
    pthread_t thr_ID; 
    int num_of_repeats; 
    int id; 
} THREADARGS; 

void enter_section (int thread) { 
    int other = 1 - thread; 

    flag[thread] = 1; 
    turn = thread; 

    while ((turn == thread) && (flag[other] == 1)); 

    return; 
} 

void leave_section (int thread) { 
    flag[thread] = 0; 

    return; 
} 


void * add (void * arg) { 

    int i; 
    THREADARGS * a = (THREADARGS *) arg; 

    for (i = 0; i < a->num_of_repeats; i++) { 
     enter_section(a->id); 
     counter++; 
     leave_section(a->id); 
    } 

    return NULL; 
} 

int main() { 
    int i = 1; 
    pthread_attr_t thrAttr; 
    THREADARGS threadargs_array[2]; 

    pthread_attr_init (&thrAttr); 
    pthread_attr_setdetachstate (&thrAttr, PTHREAD_CREATE_JOINABLE); 

    /* creating 1st thread */ 

    threadargs_array[0].id = 0; 
    threadargs_array[0].num_of_repeats = 1000000; 

    pthread_create(&threadargs_array[0].thr_ID, &thrAttr, add, &threadargs_array[0]); 

    /* creating 2nd thread */ 

    threadargs_array[1].id = 1; 
    threadargs_array[1].num_of_repeats = 2000000; 

    pthread_create(&threadargs_array[1].thr_ID, &thrAttr, add, &threadargs_array[1]); 

    /* free resources for thread attributes */ 
    pthread_attr_destroy (&thrAttr); 

    /* waiting for 1st thread */ 
    pthread_join (threadargs_array[0].thr_ID, NULL); 
    printf("First thread is done.\n"); 

    /* waiting for 2nd thread */ 
    pthread_join (threadargs_array[1].thr_ID, NULL); 
    printf("Second thread is done.\n"); 


    printf("Counter value is: %d \n", counter); 
    return (EXIT_SUCCESS); 
}

來源

2012-02-25 Štěpán Heller

在http://bartoszmilewski.com/2008/11/05/who-ordered-memory-fences-on-an-x86/上有關於Peterson同步會發生什麼的描述。雖然我可以發誓，但是'保護區'就足夠了，另外，你需要編譯器的屏障，我將它放在'mfence/sfence'上，並且在'while'循環的每一次迭代中。 – ninjalj 2012-02-27 19:49:20

如果你仍然對此感興趣，可以參考http://stackoverflow.com/questions/11588514/a-tested-implementation-of-peterson-lock-algorithm/11656926#11656926 – ninjalj 2012-07-25 19:26:40

您有幾個問題在這裏：

訪問您的變量將我們受到的優化，所以你必須聲明它們volatile，至少。
像這樣的算法可以在沒有任何由POSIX提供的鎖定數據結構的情況下訪問線程之間的數據，只有在基本操作保證爲原子的情況下才能工作，而這些原子操作通常不在現代處理器上。特別是++運算符是而不是原子。

有幾種方法可以解決這個問題，特別是新的C標準C11提供原子基元。但是，如果這真的意味着你開始學習並行編程，我強烈建議你首先研究互斥鎖，條件變量等，以瞭解POSIX是如何工作的。

來源

2012-02-25 11:32:28

這裏有另外一個討論，它會更好用編譯器屏障（GCC中的__asm__ __volatile __（「」:::「memory」））而不是volatile。無論如何，在'enter_section'和'leave_section'中插入適當的CPU和編譯器屏障似乎很難，所以除非我有適當的睡眠，否則我不會這樣做。 – ninjalj 2012-02-26 22:10:07

更好的辦法是使用C11的適當語言結構，以便對重新排序提供適當的保證，而不是用編譯器擴展來欺騙:)在任何情況下，最好遠離諸如並行編程入門之類的東西。 – 2012-02-26 22:17:16

Peterson算法的執行錯誤？

回答

相關問題