Niewłaściwa wartość zmiennej - błąd synchronizacji?

Witam. Zgodnie z radą założyłem nowy wątek. Napisałem program, który w założeniu ma działać zgodnie z algorytmem piekarnianym. Pojawił się jednak pewien problem, którego przyczyny nie jestem w stanie odnaleźć. Końcowa wartość zmiennej globalnej powinna być równa sumie przejść wszystkich wątków do sekcji krytycznej. Tymczasem, zamiast wartości np. 15 (dla 3 wątków), otrzymuję wartość 10 lub 11. Co może być nie tak?

Dołączam także fragment kodu, w którym znajduje się błąd:

#include "func.h"

void gotoxy(unsigned x, unsigned y) //nie kasuje zawartości wiersza, w którym zamierza pisać
{
  printf("\033[%d;%dH", y, x);
}

void* algorytm(void* arg)
{
    long thread=(long)arg;
    srand(time(NULL));

    for(int i=0; i<LOOP; ++i)
    {
        int tm=(rand()%MAX_SL)+MIN_SL;  //czas uśpienia
        
        int temp=0;

        choosing[thread]=true;

        for(int j=0; j<tms; ++j)
        {
            number[j]>temp ? number[j] : temp;
        }
        number[thread]=temp+1;

        choosing[thread]=false;

        for(int other=0; other<tms; ++other)
        {
            while(choosing[other]) {};
            while(number[other]!=0 && (number[other]<number[thread] || (number[other]==number[thread] && other<thread))) {};
        }

        sleep(tm);  //uśpienie

        gotoxy(POZ_C, (++poz_b_kryt));  //prawa strona - sekcja krytyczna
        printf("S. kr. w.: %ld po raz: %d", thread, i+1);  //komunikat sekcji krytycznej
        fflush(stdout);

        int counter=zmienna_globalna;   //przypisanie prywatnemu licznikowi wartości zmiennej globalnej
        ++counter;  //preinkrementacja licznika

        sleep(SLV); //uśpienie przed zapisem
        zmienna_globalna=counter;   //przypisanie zmiennej globalnej wartości licznika
        number[thread]=0;

        gotoxy(POZ_A, (++poz_b_priv));  //lewa strona - sekcja prywatna
        printf("S. pr. w.: %ld po raz: %d |", thread, i+1);  //komunikat sekcji prywatnej
        fflush(stdout);

    }

    return NULL;    //funkcja zwraca wskaźnik
}

1. Jakiego typu jest zmienna globalna? Zadeklarowałeś ją jako volatile?

2. Problem w tym, że te fragment (usunąłem zbędne komentarze, każdy wie, że ++counter to preinkrementacja licznika ;) ):

        int counter=zmienna_globalna;
        ++counter;

        sleep(SLV);
        zmienna_globalna=counter;

interpretuję tak, że zmienna globalna jest zmieniana w innym wątku między preinkrementacją licznika a przypisaniem wartości tego licznika zmiennej. Jesteś pewien, że Twój problem leży w tylko tym fragmencie, który nam pokazałeś?

3. Ze zmiennymi globalnymi ogólnie trzeba baaardzo uważać. Gdy na tym forum (i wszędzie indziej, mam nadzieję) usłyszysz by starać się nie używać zmiennych globalnych to uprzedzający będą mieli na myśli właśnie takie problemy. Może zrób sobie strukturę przechowującą to co chcesz mieć w zmiennej globalnej i inne informacje o niej i jej wykorzystaniu?

4. Czepiam się:
Taka funkcja: void* algorytm(void* arg) zwracająca jedynie NULL na samym końcu to złe rozwiązanie. Ta funkcja może nic nie zwracać, po co NULL?

Co może być nie tak?

Kompletny brak synchronizacji:

  int counter = zmienna_globalna; 
  ++counter; 

  zmienna_globalna = counter; 

Co się stanie, jeśli dwa lub więcej wątków wykona w tym samym czasie pierwszą linię?


Poczytaj o operacjach atomowych i synchronizacji za pomocą muteksów/sekcji krytycznych.

Pisząc program, postępowałem zgodnie z algorytmem, który zamieściłem w tym temacie. Wg niego, fragment wyszczególniony przez @_0x666_ powinien znajdować się w sekcji krytycznej, czyli dostęp do zmiennej globalnej powinien w danej chwili mieć tylko jeden wątek. Chyba, że coś źle zrozumiałem...
Co do zmiennej globalnej - mam z góry narzucone, że każdy wątek ma najpierw przypisać własnemu licznikowi wartość zmiennej globalnej, zwiększyć jego wartość i przypisać ją zmiennej globalnej.
@Bartosz36: Mam świadomość, że na końcu może w ogóle nie być return. Dałem go tam w zasadzie tylko po to, by kompilator nie wyrzucał ostrzeżenia "control reaches end of non-void function".

Zmienna globalna jest zwykłym int-em. Dla zainteresowanych dołączam paczkę z całym kodem źródłowym :)

Mówiąc, że:

Ta funkcja może nic nie zwracać,

miałem na myśli także jej typ. Dlaczego nie zrobisz jej po prostu: void algorytm(long thread);?

Dlaczego masz narzucone zmienne globalne? Założenie prowadzącego zajęcia? Jeśli nie, to tak ja jak i kolega @_0x666_ piszemy Ci, że zastosowanie globalnej jest złym pomysłem i najpewniej właśnie to powoduje błędy.

Dodałem volatile do zmiennej globalnej. Znalazłem też i naprawiłem jeden błąd. Zamiast:

for(int j=0; j<tms; ++j)
        {
            number[j]>temp ? number[j] : temp;
        }

powinno być:

for(int j=0; j<tms; ++j)
        {
            temp=number[j]>temp ? number[j] : temp;
        }

Niestety, ta zmiana nie wpłynęła na działanie programu.

@Bartosz36: Tak, zgodnie z założeniami prowadzącego, wątki mają zmieniać wartość zmiennej globalnej.

Wg niego, fragment wyszczególniony przez @_0x666_ powinien znajdować się w sekcji krytycznej

Albo zrób tak:

sleep(SLV);
__sync_add_and_fetch(&zmienna_globalna, 1); // dla gcc

Prawdopodobnie będziesz musiał to samo zrobić z poz_b_kryt.

Problem polega na tym, że ten kod to groch z kapustą. Za dużo się dzieje w jednej funkcji.
Dodatkowo algorytm ten wcale nie oznacza, że synchronizacja wątków nie jest potrzebna jest ona po prostu przeniesiona na inne elementy związane z algorytmem piekarni.

Moja rada podziel problem na mniejsze:

• coś co realizuję kolejkę w sposób wątkowo bezpieczny. Potrzebujesz funkcjonalności:

  • dodajesz zadanie (klienta) do kolejki
  • pobierasz pierwsze zadanie (klienta) z kolejki
  • kolejka musi być synchronizowana*

• coś co stworzy n wątków, które będą pobierać zadania z kolejki a następnie je wykonywać. Jeśli kolejka jest pusta wątek ma czekać na nowe zadania.

• coś co będzie dodawać zadania do kolejki

• same zadania do wykonania

Jaki kompilator używasz?
Jeśli jest to clang to polecam przełącznik: -fsanitize=thread, to ładnie stworzy raport opisujący na czym polega problem.

@kst142: widzę, że zaakceptowałeś mój post, ale w zasadzie nie rozwiązuje on głównego problemu. Przyjrzałem się twoim źródłom i jest tu trochę błędów. Pierwsza sprawa: źle definiujesz zmienne globalne. W func.h powinno być:

extern bool choosing[MAX_TIMES];
extern int number[MAX_TIMES];
extern int zmienna_globalna;   
extern int tms;

a w main.c:

bool choosing[MAX_TIMES] = { false };
int number[MAX_TIMES] = { 0 };
int zmienna_globalna = 0;
int tms = 0;

Następny błąd:

if(pthread_create((thread_id+i), NULL, algorytm, (void*)((long)(i+1)))!=0)

Numery wątków dajesz licząc od jednego, a algorytm napisany jest tak, jakby były liczone od zera. Powinno być:
```cpp
if(pthread_create((thread_id+i), NULL, algorytm, (void*)((long)(i)))!=0)

No i teraz sam algorytm:

void* algorytm(void* arg)
{
	long thread=(long)arg;
	srand(time(NULL));

	for(int i=0; i<LOOP; ++i)
	{
		int tm = (rand() % MAX_SL) + MIN_SL;  

		choosing[thread] = true;
		__sync_synchronize();

		int temp = number[0];

		for(int j = 1; j < tms; ++j)
		{
			int v = number[j];
			temp = v > temp ? v : temp;
		}

		++temp;
		
		number[thread] = temp;
		__sync_synchronize();
		choosing[thread] = false;
		__sync_synchronize();

		for(int other = 0; other < tms; ++other)
		{
			while(choosing[other]) { sched_yield(); };
			__sync_synchronize();

			while(number[other] != 0 && 
					(number[other] < number[thread] || 
						(number[other] == number[thread] && other < thread))) { sched_yield(); };
		}

		/*** enter CS ***/

		sleep(SLV); 
		int x = zmienna_globalna;
		++x;
		sleep(tm);
		zmienna_globalna = x;

		/*** leave CS ***/
		number[thread] = 0;
		__sync_synchronize();

	}

	return NULL;
}

Zastosowałem bramy pamięciowe, co by kompilator i procesor nie poprzestawiał kolejności odczytów-z/zapisów-do pamięci. U mnie działa.

@_0x666_: Dzięki wielkie :)
Wprawdzie oddałem już program, ale będę stosował się do Twoich rad :)