彼得森算法的错误实现? [英] Wrong implementation of Peterson's algorithm?
问题描述
我试图学习一些有关并行编程的知识，因此我尝试实现 Peterson 算法作为一个简单示例，其中一个共享计数器增加 2 个线程.我知道由于忙于等待，彼得森不是最佳选择，但我只是出于学习原因才尝试过.
I was trying to learn something about parallel programming, so I tried to implement Peterson's algorithm for an easy example where one shared counter is incremented by 2 threads. I know that Peterson's isn't optimal due to busy waiting but I tried it only for study reasons.
我认为这段代码的临界区在线程函数 add 中，其中共享 counter 递增.所以我在计数器递增之前调用 enter_section 函数，在它之后调用 leave_function.这部分有错吗?我评估临界区错了吗?问题是当这两个线程完成时，计数器有时会给出一个意想不到的值.它必须是线程之间的同步问题，但我只是没有看到它...感谢您的帮助.
I supposed that the critical section of this code is in the thread function add where the shared counter is incremented. So i call the enter_section function before the counter incrementation and after it I called the leave_function. Is this part wrong? Did I asses the critical section wrong? Problem is that the counter sometimes gives an unexpectable value when these 2 threads are done. It has to be a synchronization problem between threads but I just don't see it... Thanks for any help.
#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.
");
/* waiting for 2nd thread */
pthread_join (threadargs_array[1].thr_ID, NULL);
printf("Second thread is done.
");
printf("Counter value is: %d
", counter);
return (EXIT_SUCCESS);
}
推荐答案
这里有几个问题:
- 对您的变量的访问将受到优化，因此您必须至少将它们声明为
volatile. - 这样的算法在没有 POSIX 提供的任何锁定数据结构的情况下访问线程之间的数据，只有在保证原始操作是原子性的情况下才能工作，而现代处理器通常不具备这种原子性.特别是
++操作符不是原子的.
- the access to your variables will we subject to optimization, so you'd have to declare them
volatile, at least. - Algorithms like this that access data between threads without any of the lock data structures that are provided by POSIX can only work if your primitive operations are guaranteed to be atomic, which they usually aren't on modern processors. In particular the
++operator is not atomic.
有几种方法可以解决这个问题，特别是新的 C 标准 C11 提供了原子原语.但如果这真的是为了让您开始学习并行编程，我强烈建议您首先研究互斥锁、条件变量等，以了解 POSIX 的工作原理.
There would be several ways around this, in particular the new C standard C11 offers atomic primitives. But if this is really meant for you as a start to learn parallel programming, I'd strongly suggest that you first look into mutexes, condition variables etc, to learn how POSIX is intended to work.
这篇关于彼得森算法的错误实现?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
