Алгоритм Петерсона (ошибка в коде)

Question

Я попытался реализовать алгоритм Петерсона. В моем main я получаю после времени больше не результат 20000. Не могли бы вы объяснить мне такое поведение? Я не совсем уверен, правильно ли я реализовал алгоритм.

Приветствие

// Implementing Peterson Algorithm 

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

volatile int turn = 0; 
volatile int flag[2] = { 0 }; 
int num = 0; 

pthread_t thread[2]; 

void *count0(void *t) { 
    flag[0] = 1; 
    turn = 1; 
    while (flag[1] == 1 && turn == 1) continue; 
    for (int i = 0; i < 10000; i++) { 
     num++;      // critical section 
    } 
    flag[0] = 0; 
} 

void *count1(void *t) { 
    flag[1] = 1; 
    turn = 0; 
    while (flag[0] == 1 && turn == 0) continue; 
    for (int i = 0; i < 10000; i++) { 
     num++; 
    } 
    flag[1] = 0; 
} 

int main() { 
    while (1) { 
     pthread_create(&thread[0], NULL, count0, NULL); 
     pthread_create(&thread[1], NULL, count1, NULL); 

     pthread_join(thread[0], NULL); 
     pthread_join(thread[1], NULL); 
     printf("num = %d\n", num); 
     if (num != 20000) { printf("!!!!!!"); exit(0); } 
     num = 0; 
    } 
    return 0; 
} 

Answer 1

Петерсен алгоритм был разработан в 1981 году, он работает правильно для простых процессоров, но он больше не подходит для современных процессоров, которые могут изменить порядок доступа к памяти, если конкретные меры не будут приняты, чтобы обеспечить в которые требуют нестандартных языковых расширений.

Цитируя статью Википедии: https://en.wikipedia.org/wiki/Peterson%27s_algorithm

Примечание

При работе на аппаратном уровне, алгоритм Петерсона, как правило, не требуется для достижения атомарного доступа. Некоторые процессоры имеют специальные инструкции, такие как test-and-set или compare-and-swap, которые, блокируя шину памяти, могут использоваться для обеспечения взаимного исключения в SMP-системах.

Большинство современных процессоров переупорядочивают доступ к памяти для повышения эффективности выполнения (см. Порядок памяти для разрешенных типов переупорядочения). Такие процессоры неизменно дают некоторый способ принудительного упорядочения в потоке доступа к памяти, как правило, с помощью инструкции барьера памяти. Реализация алгоритмов Петерсона и связанных с ними алгоритмов на процессорах, которые изменяют порядок доступа к памяти, обычно требует использования таких операций для правильной работы, чтобы последовательные операции не выполнялись в неправильном порядке. Обратите внимание, что переупорядочение доступа к памяти может происходить даже на процессорах, которые не изменяют порядок инструкций (например, процессор PowerPC в Xbox 360).

Большинство таких ЦП также имеют какую-то гарантированную атомную операцию, такую ​​как XCHG на процессорах x86 и load-link/store-conditional на Alpha, MIPS, PowerPC и других архитектурах. Эти инструкции предназначены для того, чтобы обеспечить способ создания примитивов синхронизации более эффективно, чем это можно сделать с использованием чистых подходов к общей памяти.