c - Peterson 算法的错误实现？

Question

我试图学习一些有关并行编程的知识，因此我尝试实现 Peterson 算法作为一个简单的示例，其中一个共享计数器按 2 个线程递增。我知道彼得森的不是最佳选择，因为忙碌的等待，但我只是出于学习原因尝试了它。

我认为这段代码的关键部分位于线程函数add中，其中共享计数器递增。因此，我在计数器递增之前调用 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);
}

Answer 1

您遇到了几个问题:

• 我们将对变量的访问进行优化，因此您至少必须将它们声明为 volatile 。
• 像这样在没有 POSIX 提供的任何锁数据结构的情况下在线程之间访问数据的算法只有在保证原始操作是原子性的情况下才能工作，而现代处理器上通常无法做到这一点。特别是 ++ 运算符不是原子的。

有多种方法可以解决这个问题，特别是新的 C 标准 C11 提供了原子原语。但如果这确实适合您作为学习并行编程的开始，我强烈建议您首先研究互斥体、条件变量等，以了解 POSIX 的工作原理。