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算法的执行错误？

回答

相关问题