[C] Problema con i thread su ubuntu

[masmil1988]

Ho un problema con un piccolo programmino (codice).

Il programma semplicemente crea due thread che incrementano la variabile globale contatore.
Ogni thread dovrebbe, in mutua esclusione, incrementare la variabile 50.000 volte, e il valore finale della variabile dovrebbe quindi essere infine 100.000 ...

La mutua esclusione sembra essere correttamente realizzata tramite le variabili t1vuolescrivere e t2vuolescrivere... In pratica ognuno dei thread dice che vuole scrivere (ovvero vuole incrementare la variabile), controlla che l'altro thread non voglia scrivere, se l'altro vuole scrivere aspetta per un breve periodo prima di riprovare, altrimenti scrive...

Ho provato il codice su un dual-core e su un mono-processore e la situazione è ancora più grave nel secondo...
Nel primo l'errore si presenta una trentina di volte su 100.000, nel secondo siamo sull'ordine delle 20.000 ...

Sapete aiutarmi a capire dove sta il problema?

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

int contatore=0;
int t1vuolescrivere=0;
int t2vuolescrivere=0;

void* incrementa1(void* niente) {
	int i;
	for (i=0; i<50000; ++i) {
		t1vuolescrivere=1;
		while (t2vuolescrivere) {
			t1vuolescrivere=0;
			sleep(0.01);
			t1vuolescrivere=1;
		}
		contatore++;		// sezione critica
		t1vuolescrivere=0;
	}
}

void* incrementa2(void* niente) {
	int i;
	for (i=0; i<50000; ++i) {
		t2vuolescrivere=1;
		while (t1vuolescrivere) {
			t2vuolescrivere=0;
			sleep(0.01);
			t2vuolescrivere=1;
		}
		contatore++;		// sezione critica
		t2vuolescrivere=0;
	}
}

int main() {
	pthread_t t1;
	pthread_t t2;
	
	pthread_create(&t1,NULL,&incrementa1,NULL);
	pthread_create(&t2,NULL,&incrementa2,NULL);
	pthread_join(t1,NULL);
	pthread_join(t2,NULL);
	printf("Valore finale del contatore: %d\n",contatore);

	return 0;
}

[shodan]

Devi proteggere le variabili globali con mutex.

[masmil1988]

Si, so come si usano i mutex... Però a parte l'utilizzo dei mutex o dei semafori il programma dovrebbe funzionare ugualmente perchè non dovrebbe poter esserci possibilità di accesso contemporaneo dei due thread alla sezione critica...

[shodan]

Guarda che non c'è nessuna sezione critica in quel codice e contatore++ non è un'operazione atomica.

[masmil1988]

Lo so......
Però se guardi il codice dovresti convincerti facilmente che non è possibile per i due thread accedere insieme all'istruzione contatore++ ...
E' una variante dell'algoritmo di Dekker per l'accesso in mutua esclusione senza uso di mutex e semafori... E dovrebbe funzionare... L'ho implementato in Java e funziona correttamente, in C invece mi crea problemi... Non capisco quindi da cosa possa dipendere...

[shodan]

Ho dato un'occhiata all'algoritmo (che non conoscevo) e in teoria dovrebbe essere corretto.
Però non fa i conti con i compilatori C ( e C++ ) che, introducendo ottimizzazioni sparse, riordinano il codice come gli pare meglio. In altre parole, quello che scrivi tu può non essere quello che produce il compilatore, quindi quel codice di fatto diventa inutilizzabile.

Da wikipedia:

Additionally, many optimizing compilers can perform transformations that will cause this algorithm to fail regardless of the platform. In many languages, it is legal for a compiler to detect that the flag variables f0 and f1 are never accessed in the loop. It can then remove the writes to those variables from the loop, using a process called Loop-invariant code motion. It would also be possible for many compilers to detect that the turn variable is never modified by the inner loop, and perform a similar transformation, resulting in a potential infinite loop. If either of these transformations is performed, the algorithm will fail, regardless of architecture.

To alleviate this problem, volatile variables should be marked as modifiable outside the scope of the currently executing context. For example, in C# or Java, one would annotate these variables as 'volatile'. Note however that the C/C++ "volatile" attribute only guarantees that the compiler generates code with the proper ordering; it does not include the necessary memory barriers to guarantee in-order execution of that code.

http://en.wikipedia.org/wiki/Dekker%27s_algorithm

Problema per altro che affligge chiunque cerchi di scivere un singleton multithreading decente.

[XWolverineX]

Insomma, devi spipparti una critical section.

[YuYevon]

Magari prova a cambiare algoritmo (tipo Peterson, che tra l'altro dovrebbe essere una versione migliorata di Dekker). Comunque stai compilando con gcc? Quale versione? Ho provato il codice su un single core con Slackware 12.2 qualche centinaio di migliaio di volte (con un ciclo in bash) e ottengo sempre 100000 come risultato. Compilo con gcc 4.2.4, tra l'altro ho anche provato a forzare ottimizzazioni a più livelli con le opzioni apposite e ottengo sempre il risultato corretto.

[masmil1988]

Benissimo, allora sarà un problema di compilazione......
Sapete consigliarmi un compilatore diverso da gcc allora?

Grazie a tutti

[simo_us]

E NON OFFENDERE GCC MANNAGGIA A TE!!!!

Il tuo programma funziona come lo hai programmato..

Valore finale del contatore: 100000