Zähler mit pthreads falsch

[shutdown]

Hallo,

ich versuche momentan "nebenher" ein bisschen C zu lernen, da die Sprache doch sehr weit verbreitet ist und es eigentlich nur von Vorteil sein kann, sich damit als interessierter Linuxuser ein bisschen auszukennen.
Man könnte das Ganze auch einfach Hobby nennen.

Beim Herumspielen mit pthreads bzw der Umstellung eines Programms zur Berechnung von Primzahlen auf pthreads ist mir nun etwas sehr seltsames aufgefallen.
Hier erstmal mein Programm:


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

#define MAXNUM 200000
#define MINNUM 1
#define THREAD_NUM 8

int primcnt[THREAD_NUM+1];
int primcount=0;

void *thread_main( void *ptr ) {
int i,*tid,tmax,tmin,trange,tmodulo;
tid = (int *) ptr;

/*
* Calculate the range of numbers each thread has to process;
* calculate the starting and ending number for each thread.
*/
trange=((MAXNUM-MINNUM)+1)/THREAD_NUM;
tmin=(trange*(*tid))+MINNUM;
tmax=tmin+trange-1;

/* If the division for range calculation returns a rest, let the last thread do the extra job */
if (*tid == THREAD_NUM-1) {
tmax=tmax+(((MAXNUM-MINNUM)+1)%THREAD_NUM);
trange=trange+(((MAXNUM-MINNUM)+1)%THREAD_NUM);
}

/* Give some feedback so we can see everything is all right so far */
printf("This is thread %d. Range is %d, starting at %d, ending at %d.\n",*tid,trange,tmin,tmax);

/* Check if a number within the threads range is a prime number */
for (i=tmin;i<=tmax;i++) {
if (isprim(i) == 0) {
/*
* If we've found a prime number, raise the counter.
* Interesting part: We've got 2 counters, a in-thread counter and a global one.
* This will be quite interesting later...
*/
primcnt[*tid]++;
primcount++;
}
}

return 0;
}


int isprim(int number) {
/*
* Function to see if a given number is a prime number.
* This method seems to be pretty fast and accurate.
*/
int divisor=2;

while (divisor*divisor <= number) {
if (number % divisor == 0) {
return 1; /* Not a prime number */
}
divisor++;
}
return 0; /* Prime number found :) */
}


main() {
int i,*threadid[THREAD_NUM],tid[THREAD_NUM],iret[THREAD_NUM];
pthread_t thread[THREAD_NUM];

/* Prepare some IDs to pass to the threads */
for (i=0;i<THREAD_NUM;i++) {
tid[i]=i;
threadid[i]=&tid[i];
}

/* Run independent threads */
for (i=0;i<THREAD_NUM;i++) {
iret[i] = pthread_create( &thread[i], NULL, thread_main, (void*) threadid[i]);
}

/* Wait for threads to finish */
for (i=0;i<THREAD_NUM;i++) {
pthread_join( thread[i], NULL);
}

/* Let's see how many prime numbers each thread has found. Further we can see if the number of hits will change here */
for (i=0;i<THREAD_NUM;i++) {
printf("Thread %d returned %d prime numbers.\n",i,primcnt[i]);
primcnt[THREAD_NUM]=primcnt[THREAD_NUM]+primcnt[i];
}

/* Let's see how many prime numbers we've counted.
* AND let's see, if the sum of all in-thread counters is equal to our global counter.
* I can tell you it won't be, so print the offset as well.
* The offset seems to be *always* >0, so our global counter must be missing some counts.
* Dunno why this happens, seems quite impossible to me.
*/
printf("\n\n%d prime numbers found\n",primcnt[THREAD_NUM]);
printf("Alternative number is %d. Offset is %d\n",primcount,primcnt[THREAD_NUM]-primcount);
return 0;
}


Nun zum eigentlichen Phänomen: Ich starte mehrere threads, die je einen gewissen Zahlenraum nach Primzahlen absuchen. Jeder der Threads hat einen eigenen Zähler für Funde, zudem habe ich einen globalen Zähler.
Die Zähler innerhalb der Threads habe ich erst zur Fehlersuche hinzugefügt, da der globale Zähler bei jedem Programmaufrauf einen etwas anderen Wert zurückliefert.

Hier mal 2 Beispielausgaben des Programms, die Merkwürdigkeit ist einfach offensichtlichst:

This is thread 0. Range is 25000, starting at 1, ending at 25000.
This is thread 1. Range is 25000, starting at 25001, ending at 50000.
This is thread 2. Range is 25000, starting at 50001, ending at 75000.
This is thread 5. Range is 25000, starting at 125001, ending at 150000.
This is thread 3. Range is 25000, starting at 75001, ending at 100000.
This is thread 6. Range is 25000, starting at 150001, ending at 175000.
This is thread 4. Range is 25000, starting at 100001, ending at 125000.
This is thread 7. Range is 25000, starting at 175001, ending at 200000.
Thread 0 returned 2763 prime numbers.
Thread 1 returned 2371 prime numbers.
Thread 2 returned 2260 prime numbers.
Thread 3 returned 2199 prime numbers.
Thread 4 returned 2142 prime numbers.
Thread 5 returned 2114 prime numbers.
Thread 6 returned 2068 prime numbers.
Thread 7 returned 2068 prime numbers.


17985 prime numbers found
Alternative number is 17928. Offset is 57

This is thread 0. Range is 25000, starting at 1, ending at 25000.
This is thread 1. Range is 25000, starting at 25001, ending at 50000.
This is thread 2. Range is 25000, starting at 50001, ending at 75000.
This is thread 3. Range is 25000, starting at 75001, ending at 100000.
This is thread 4. Range is 25000, starting at 100001, ending at 125000.
This is thread 5. Range is 25000, starting at 125001, ending at 150000.
This is thread 6. Range is 25000, starting at 150001, ending at 175000.
This is thread 7. Range is 25000, starting at 175001, ending at 200000.
Thread 0 returned 2763 prime numbers.
Thread 1 returned 2371 prime numbers.
Thread 2 returned 2260 prime numbers.
Thread 3 returned 2199 prime numbers.
Thread 4 returned 2142 prime numbers.
Thread 5 returned 2114 prime numbers.
Thread 6 returned 2068 prime numbers.
Thread 7 returned 2068 prime numbers.


17985 prime numbers found
Alternative number is 17952. Offset is 33

Was ich hier offset getauft habe ändert sich bei jedem Aufruf des Programms, und nun meine eigentliche Frage: Warum?

Welchen wahrscheinlich blöden Anfängerfehler mache ich, dass das passiert? Ich suche den Fehler nun seit 2 Tagen und finde ihn nicht...
Verzeiht mir meine Ahnungslosigkeit, aber es macht mich einfach irre!

Ach ja: Übersetzt habe ich mein Werk mit "gcc -o threads ./threads.c -pthread"

Peter

PS: Falls jemand einen Vorschlag hat, den Quellcode fürs nächste Programm übersichtlicher zu machen oder "Stilfehler" bemängeln will, macht es bitte! Das ist das erste C-Programm von mir, das ich jemand anderen als mich lesen lasse ;)

[tribad]

Du benutzt deine globalen Variablen in jedem Thread und sorgst nicht dafür, das sie nicht gleichzeitig von mehreren Threads manipuliert werden können.

Mutex heißt das bei pthreads glaube ich auch.

Immer wenn auf gemeinsame Daten zugegriffen wird, muß man dafür sorge tragen, das wirklich nur ein Thread die Daten manipuliert. Das machst du eben nicht.

Es gibt auch sowas wie critical-sections. Trifft es eigentlich besser. Der Thread der zuerst eine solche critical-section betritt markiert das. Alle anderen Threads werden beim versuch ebenfalls in die critical-section einzutreten blockiert, bis der erste Thread sie wieder verläsßt und diesen Bereich wieder freigibt.
Dann ist der nächste Thread dran.
Die pthread-libs sorgen dafür, das das auch wirklich so funktioniert.

Einfach mal schauen. mutex/critical-section

[shutdown]

OK das erklärt natürlich einiges...das heisst also im Klartext dass mein sog. offset angibt, wie oft die Threads sich in die Quere gekommen sind.

Auf jeden Fall vielen Dank für den Hinweis, werde mich da mal schlaulesen :D

Peter

[RHBaum]

Mutex ist das Object (BS) womit man Sicherstellt, das nur ein Thread einen "Codeabschnitt" betreten (den mutex passieren) kann.
"Critical Section" bezeichnet man eigentlich den Code Abschnitt selber, den nur ein Thread aufs mal betreten kann. Also der bereich zwischen anziehen und wieder loesen des Mutex ....

Warum nun Microsoft angefangen hat, Mutexe als Critical Sections zu bezeichnen bzw. als implementierungsspezifische Form eines Mutex zu behandeln, darueber kann man nur philosophieren ...

Also Mutex und Critical Seciton gehoeren eng zusammen.

Mutexe koennen ueber mehrere Wege realisiert werden ... ueber atomare Operationen, Signale, Events (BS Events). Entscheidet aber meistens die MT Bib die du verwendest, fuer dich ....

Ciao ....

[tribad]

Soweit mir bekannt, ist ein Mutex ein Prozessübergreifender Mechanismus, der daher auch Systemweit verwaltet werden muß.
Eine Critical-Section ist ein nur innerhalb des Prozess angewendeter, und damit nur zur Synchronisierung von Threads in einem Prozess verwendbarer mechanismus.
Ich weiß nicht ob das auch für PThreads so gilt. Die Unterscheidung wird sinnig, wenn du shared-memory verwendest, und dann mehrere Prozesse synchronisierst.
Aber nun gut. Da ich mich eigentlich nie wirklich um den Unterschied gekümmert habe sondern nur Mutexe verwende, habe ich ja auch geschrieben das man nachlesen soll.
Da wird dann der wissbegierige Leser auch den Unterschied zwischen einem Mutex und einer critical-section finden.

[anda_skoa]

Soweit mir bekannt, ist ein Mutex ein Prozessübergreifender Mechanismus, der daher auch Systemweit verwaltet werden muß.


Nein. Mutex, Lock, Semphore, usw. sind lediglich Konzepte. Oft gibt es für eine Art der Parallelisierung, z.B. Threads, Implementierungen von mehr als nur einem, einfach um in bestimmten Situationen die jeweiligen Vorzügen nutzen zu können.

Die Critical Section ist dann die mit einem der Ausschlußkonzepten realisierter Verarbeitungsabschnitt, der immer nur von einem der beteiligeten parallelen Verarbeitungseinheiten durchlaufen wird.

Ciao,
_

[RHBaum]

Glaub auch gelesen zu haben, das bei den Begriffen keine Implementierungsdetails bzw. Gueltigkeitsbereich dahinter stehen.

natuerlich gibt es unter windows lokale (multithreading), und (prozess)globale (multiprocessing) Mutexe, welche natuerlich anders implementiert sind. Vielleicht macht windows deshalb den unterschied. aber das ist halt windows problem.

unter pthread heissen die Sperren z.b. auch mutex, obwohl sie da lokal sind und laut windows philosophie wahrscheinlich critical sections heissen muessten.

ciao ...