Неправильная реализация алгоритма Петерсона? - PullRequest
Новая
       9

Неправильная реализация алгоритма Петерсона?

2 голосов
/ 25 февраля 2012

Я пытался узнать кое-что о параллельном программировании, поэтому я попытался реализовать алгоритм Петерсона для простого примера, когда один общий счетчик увеличивается на 2 потока. Я знаю, что у Петерсона неоптимальный вариант из-за напряженного ожидания, но я попробовал его только для учебы.

Я предположил, что критическая секция этого кода находится в функции потока add, где общий counter увеличивается. Поэтому я вызываю функцию enter_section до увеличения счетчика, а после нее я вызываю leave_function. Эта часть не так? Я правильно оценил критическую секцию? Проблема в том, что счетчик иногда дает неожиданное значение, когда эти 2 потока завершены. Это должно быть проблема синхронизации между потоками, но я просто не вижу этого ... Спасибо за любую помощь. 

#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);
}

1 Ответ

4 голосов
/ 25 февраля 2012

У вас есть несколько проблем:

  • доступ к вашим переменным будет подвергнут оптимизации, поэтому вам нужно будет объявить их volatile, как минимум.
  • Подобные алгоритмы, которые осуществляют доступ к данным между потоками без какой-либо из структур данных блокировки, предоставляемых POSIX, могут работать только в том случае, если ваши примитивные операции гарантированно являются атомарными, чего обычно нет на современных процессорах.В частности, оператор ++ является , а не атомарным.

Было бы несколько способов обойти это, в частности новый C-стандарт C11 предлагает атомарные примитивы.Но если это действительно предназначено для вас, чтобы начать изучать параллельное программирование, я настоятельно рекомендую вам сначала изучить мьютексы, условные переменные и т. Д., Чтобы узнать, как POSIX предназначен для работы.

...