Алгоритм Петерсона для предотвращения состояния гонки между потоками

Подробности:

Я реализую алгоритм Петерсона (ниже), чтобы избежать состояния гонки. Я хочу сделать это так: объявить глобальную целочисленную переменную и создать потоки один и два. Всякий раз, когда поток имеет доступ к глобальной переменной, он должен напечатать a и добавить единицу к счетчику глобальной переменной. Когда второй поток имеет доступ к этой глобальной переменной, он должен напечатать b и добавить единицу к счетчику глобальной переменной. Это должно продолжаться до тех пор, пока глобальная переменная не достигнет определенного числа (скажем, 10). После этого я хочу, чтобы поток (какой-либо из двух потоков, который делает последнее добавление к глобальной переменной) сбрасывал глобальную переменную на 1, и оба потока должны выйти. Код, который я реализовал до сих пор, выполняет свою работу, он позволяет избежать состояния гонки, но я не могу выйти из обоих потоков, когда счетчик достигает предела.

Вопрос:

  • Как я могу выйти из обоих потоков, когда счетчик достигает определенного предела.

  • Какова правильная форма выхода из потока, прямо сейчас я использую exit(), что я не думаю, что это очень эффективно.

Алгоритм Петерсона

boolean flag [2];
int turn;
void P0()
{
    while (true) {
         flag [0] = true;
         turn = 1;
         while (flag [1] && turn == 1) /* do nothing */;
         /* critical section */;
         flag [0] = false;
         /* remainder */;
    }
}

void P1()
{
     while (true) {
          flag [1] = true;
          turn = 0;
          while (flag [0] && turn == 0) /* do nothing */;
          /* critical section */;
          flag [1] = false;
          /* remainder */
     }
}

 void main()
 {
       flag [0] = false;
       flag [1] = false;
       parbegin (P0, P1);
 }

Мой код:

EDIT: я понял, что мне нужно поместить оператор if, который проверяет предельное значение счетчика, в критическую секцию (до того, как он изменит флаг на false).

#include<stdlib.h>
#include<stdio.h>
#include<pthread.h>


int counter = 0;

int flag[2];
int turn;

void *func1(void *);
void *func2(void *);

int main(int argc,char *argv[]){

    pthread_t thread1,thread2;
    //int rt1,rt2;

    flag[0] = 0;
    flag[1] = 0;

    //rt1 = pthread_create(&thread1,NULL,&func1,"a");
    //rt2 = pthread_create(&thread2,NULL,&func2,"c");
    pthread_create(&thread1,NULL,&func1,"a");
    pthread_create(&thread2,NULL,&func2,"b");

    pthread_join(thread1,NULL);
    pthread_join(thread2,NULL);

    return 0;
}// End of main function


void *func1(void *message){


    while(1){
        flag[0] = 1;
        turn = 1;
        while(flag[1] && turn == 1);
        printf("%s %d\n",(char *)message,counter);
        counter++;
        flag[0] = 0;        

        if(counter == 10){
            counter = 1;
            printf("exited at func1, with counter %d\n",counter);
            exit(0);
        }   
    }
    return 0;
}

void *func2(void *message){

    while(1){
        flag[1] = 1;
        turn = 0;
        while(flag[0] && turn == 0);
        printf("%s %d\n",(char *)message,counter);
        counter++;
        flag[1] = 0;

        if(counter == 10){
            counter = 1;
            printf("exited at func2, with counter %d\n",counter);
            exit(0);
        }
    }
    return 0;
}

person Neo    schedule 14.11.2014    source источник
comment
Это типичный пример, встречавшийся несколько раз, когда абстрактный алгоритм из литературы реализуется на C без учета предпосылок, которые есть у таких алгоритмов. Наиболее важным здесь является атомарность операций над переменными, что не гарантируется ни C, ни POSIX. Итак, то, что вы пытаетесь здесь, не может работать так. Современный C, также известный как C11, имеет атомарные типы данных и потоки, которые вы могли бы использовать для этой цели, но обычно это не так просто понять для начинающих.   -  person Jens Gustedt    schedule 14.11.2014
comment
@JensGustedt, есть ли какие-нибудь советы о том, как реализовать алгоритм? что учитывать?   -  person Neo    schedule 14.11.2014
comment
Почему вы хотите реализовать этот алгоритм? Это теоретический алгоритм из литературы, с тех пор много воды утекло. Это не имеет отношения к инструментам, которые вы используете. Потоки POSIX поставляются со своими собственными инструментами синхронизации, используйте их.   -  person Jens Gustedt    schedule 14.11.2014
comment
@JensGustedt это часть задания. Я должен был указать это в вопросе, я думаю,   -  person Neo    schedule 14.11.2014
comment
Я боялся этого. Они должны окончательно обновить свои курсы. Чтобы сделать это на самом деле, вам нужно найти компилятор с библиотекой C, который реализует атомарность, самые последние gcc и clang должны предоставить это, и начать оттуда.   -  person Jens Gustedt    schedule 14.11.2014
comment
@JensGustedt Или вы можете создать свою собственную атомарность на основе блокировки и использовать ее. Это не будет эффективно, но это может быть и не важно.   -  person David Schwartz    schedule 14.11.2014
comment
@DavidSchwartz, реализация такого алгоритма с блокировкой была бы действительно странной. Вся цель этого алгоритма состоит в том, чтобы предоставить структуру блокировки, казалось бы, из воздуха.   -  person Jens Gustedt    schedule 15.11.2014
comment
@JensGustedt Обеспечивает структуру блокировки из атомарных операций. Как реализованы эти атомарные операции, особого значения не имеет.   -  person David Schwartz    schedule 15.11.2014


Ответы (1)


Очевидно, что когда один поток сбрасывает глобальный счетчик, другой поток может никогда не увидеть, что глобальный счетчик достигает, например, 10, поэтому он никогда не завершит работу. Что, если вы просто не сбрасываете глобальный счетчик и позволяете потоку завершать работу всякий раз, когда он находит глобальный счетчик, например. 10? Если вы действительно хотите сбросить счетчик, вы делаете это в родительском (основном) потоке (где вы также определяете глобальный счетчик).

Что касается выхода из потока, вы можете либо просто вернуться из основной функции потока (это завершит поток сам по себе), либо вызвать pthread_exit из потока, либо вы можете использовать phtread_cancel из основной функции.

person Community    schedule 14.11.2014
comment
Я использовал return, он просто входит в бесконечный цикл, - person Neo; 14.11.2014
comment
Это потому, что вы сбрасываете счетчик; это первый абзац моего ответа. Если вы ошиблись, вы не можете ожидать, что вторая часть будет работать должным образом. - person ; 14.11.2014
comment
если я это сделаю, то после выполнения потоков он никогда не вернется, я должен убить его с помощью ctl + c. Но я постараюсь разобраться, - person Neo; 14.11.2014
comment
Не проверяйте на counter == 10, проверяйте на counter > 9; один счетчик может увеличить его до 10, а другой — до 11, прежде чем вы получите возможность проверить значение. - person ; 14.11.2014