执行错误Peterson算法的？ [英] Wrong implementation of Peterson's algorithm?

问题描述

我想学习一些关于并行编程，所以我试图实现Peterson算法一个简单的例子，其中一个共享计数器由2个线程递增。我知道，彼得森不是最佳由于忙等待，但我想这只是学习的原因。

我认为这code的关键部分是在线程函数添加其中共享计数递增。所以我称之为 enter_section 功能计数器递增之前和之后我叫 leave_function 。这是部分错了吗？难道我的驴关键部分错了吗？问题是，计数器有时给出了一个不可预料的值，当这些2个线程完成。它必须是线程间的同步问题，但我只是不明白它...感谢您的帮助。

 的#include＆LT;＆stdio.h中GT;
＃包括LT＆;＆stdlib.h中GT;
＃包括LT＆;＆pthreads.h中GT;INT计数器; / *全局共享计数器* /
INT标志[2] = {0,0}; / *为Peterson算法变量* /
INT转弯= 0;typedef结构threadArgs
{
    的pthread_t thr_ID;
    INT num_of_repeats;
    INT ID;
} THREADARGS;无效enter_section（INT螺纹）{
    int之外= 1  - 螺纹;    标志[主题] = 1;
    转=螺纹;    而（（转==线程）及及（标志[其他] == 1））;    返回;
}无效leave_section（INT螺纹）{
    标志[线索] = 0;    返回;
}
void *的增加（无效* ARG）{    INT I;
    THREADARGS * A =（THREADARGS *）ARG;    对于（i = 0; I＆LT; A-＆GT; num_of_repeats;我++）{
        enter_section（A-和SEQ ID）;
        反++;
        leave_section（A-和SEQ ID）;
    }    返回NULL;
}诠释主（）{
    INT I = 1;
    pthread_attr_t thrAttr;
    THREADARGS threadargs_array [2];    pthread_attr_init（安培; thrAttr）;
    pthread_attr_setdetachstate（安培; thrAttr，PTHREAD_CREATE_JOINABLE）;    / *创建线程1 * /    threadargs_array [0] .ID = 0;
    threadargs_array [0] .num_of_repeats = 1000000;    在pthread_create（安培; threadargs_array [0] .thr_ID，＆安培; thrAttr，添加和放大器; threadargs_array [0]）;    / *创建第二线程* /    threadargs_array [1] .ID = 1;
    threadargs_array [1] .num_of_repeats = 2000000;    在pthread_create（安培; threadargs_array [1] .thr_ID，＆安培; thrAttr，添加和放大器; threadargs_array [1]）;    / *线程释放资源属性* /
    pthread_attr_destroy（安培; thrAttr）;    / *等待1线程* /
    在pthread_join（threadargs_array [0] .thr_ID，NULL）;
    的printf（第一线程完成\\ n）;    / *等待第二个线程* /
    在pthread_join（threadargs_array [1] .thr_ID，NULL）;
    的printf（第二线程完成\\ n）;
    的printf（计数器值数：％d \\ n，计数器）;
    回报（EXIT_SUCCESS）;
}
 

解决方案

这里有几个问题：

• 将访问您的变量将我们受到的优化，所以你必须声明它们挥发性，至少。


• 这样的访问线程之间的数据没有任何POSIX所提供的锁数据结构算法只有当你的基本操作，保证是原子工作，他们通常不是现代处理器。尤其是 ++ 经营者的不的原子。

有会解决这个几个方面，特别是新的C标准C11提供了原子原语。但如果这真的意味着你作为一个开始学习并行编程，我强烈建议你先看看互斥体，条件变量等，学习POSIX是如何打算工作。

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.

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.\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);
}

解决方案

You have several problems here:

• 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.

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.

这篇关于执行错误Peterson算法的？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！