Thread-Barrier in WinAPI?

theta

@hustbaer: Sind die InterlockedXXX(..) Funktionen keine Barriers?

Jochen Kalmbach

hust schrieb:

Jochen. Eine CRITICAL_SECTION ist keine Barrier.

Was hat "WaitForMultipleObject" mit einer Critial Section zu tun?

hustbaer

theta schrieb:

@hustbaer: Sind die InterlockedXXX(..) Funktionen keine Barriers?

Wohl, aber nicht solche von denen hier die Rede ist.
Die Interlocked Funktionen sind Memory-Barriers ("fences").

Hier ist aber von Barriers im Sinn von "pthread_barrier_wait" die Rede. Das sind Teile wo man als Thread drauf warten kann, und wenn der Nte Thread ankommt, werden alle aufgeweckt.

Beispiel:

Angenommen z.B. du hast 3 Worker-Threads, die 3 Teile von irgendeinem Datenstück bearbeiten. Nun willst du wenn alle fertig sind die drei bearbeiteten Teile zusammenfügen. Also machst du eine Barrier mit Count=3, und jeder der 3 Threads wartet auf die Barrier nachdem er seinen Teil fertig bearbeitet hat.
Nachdem die Threads geweckt wurden (also wenn alle drei fertig sind), bekommt einer vom dem Wait-Aufruf "true" zurück, und die anderen beiden "false".

Derjenige Thread der "true" bekommen hat, nimmt dann die drei Teile, und steckt sie in die Queue für einen vierten Thread, der die dann zusammensetzt.
Danach krallt sich jeder der drei Threads jeweils "seinen" Teil vom nächsten Datenstück, und das Spiel geht von vorne lost.

theta

Klingt danach als könnte man das mit Semaphoren lösen, nicht?
(Ist reine Neugier, hat wohl nicht mehr direkt mit dem Topic zu tun.)
Simon

hustbaer

Sehe nicht wie.
Haste einen konkreten Vorschlag?

[quote="hustbaer"]Hab ich noch nie vermisst.

Ich brauche das zugegebenermaßen auch zum ersten mal, effektiv ist es aber ein sehr nützliches Werkzeug - und eher aufwändig von Hand zu implementieren, wenn das System sowas nicht schon mitbringt.

[quote="hustbaer"]Der riesen Vorteil an der Boost.Thread ist aber gerade, dass es fertige Implementierungen für Linux und Windows gibt (Mac glaube ich auch), und dass die alle das gleiche Interface haben.

Da sehe ich keinen echten Vorteil: Die POSIX-Systeme bringen diese Funktionalität ja schon mit, d.h. wenn ich hier auch noch diese Lib verwenden würde, wäre das eine Speicherplatzverschwendung, da so etwas ja schon existiert (und erzähle mir jetzt bitte keiner was davon, dass auf seiner Festplatte noch 119 GBytes frei sind - meine Applikation ist für Embedded Systeme gedacht).

hustbaer schrieb:

Du könntest also vermutlich einen Haufen #ifdef einsparen, wenn du gleich alles auf die Boost.Thread umstellst.

Nö, dann doch lieber ein paar #ifdefs an wenigen, klar umrissenen Stellen

Um noch mal kurz zum Thema zurück zu kommen: Boost ist NUR für die Verwendung einer Barrier nicht zu gebrauchen, die entsprechende Klasse hat 'zig Abhängigkeiten nach sonsto in der Bibliothek.

D.h. wenn sich nix besseres findet (die Phtreads-Library für windows ist ja leider auch so ein Klotz), wird die Windows-Variante meiner Software halt ein wichtiges Feature schlichtweg nicht haben...

hustbaer

TomoT schrieb:

Um noch mal kurz zum Thema zurück zu kommen: Boost ist NUR für die Verwendung einer Barrier nicht zu gebrauchen, die entsprechende Klasse hat 'zig Abhängigkeiten nach sonsto in der Bibliothek.

D.h. wenn sich nix besseres findet (die Phtreads-Library für windows ist ja leider auch so ein Klotz), wird die Windows-Variante meiner Software halt ein wichtiges Feature schlichtweg nicht haben...

Wenn du dir irgendwo eine Condition-Variable Implementierung für Windows raussuchst, ist der Boost-Code der Thread-Barrier in 5 Minuten portiert. (Das Ding braucht nur ne Mutex + Condition-Variable.)
Und wenn du mit PTHREADS arbeitest, für Windows aber keine Condition-Variable Implementierung hast, dann fragt ich mich, wie du überhaupt irgendwas auf Windows zu laufen bekommst. Condition-Variablen braucht man doch dauernd irgendwo wenn man mit PTHREADS programmiert...

hustbaer

TomoT schrieb:

Da sehe ich keinen echten Vorteil: Die POSIX-Systeme bringen diese Funktionalität ja schon mit, d.h. wenn ich hier auch noch diese Lib verwenden würde, wäre das eine Speicherplatzverschwendung, da so etwas ja schon existiert (und erzähle mir jetzt bitte keiner was davon, dass auf seiner Festplatte noch 119 GBytes frei sind - meine Applikation ist für Embedded Systeme gedacht).

Die ganze Boost.Thread braucht bei mir als DLL 56kB (VC80, Release, DLL-Runtime).
Du könntest einfach mal ausprobieren, was es bei dir um ist -- auf dem System wo du am wenigsten Speicher zur Verfügung hast.

Alternativ könntest du eigene "Thin-Wrapper" schreiben, die auf den Systemen mit wenig Speicher 1:1 auf PTHREADS gehen, und auf Windows eben Boost.Thread verwenden. (Die Boost.Thread ist zwar eigentlich schon recht "thin", aber ein paar Byte lassen sich sicher rausholen wenn man es selbst strickt, und nur das implementiert was man auch wirklich braucht)

Warum nicht WaitForMultipleObjects benutzen?????????????? Lest ihr überhaupt was die Leute schreiben???????????

hustbaer schrieb:

Und wenn du mit PTHREADS arbeitest, für Windows aber keine Condition-Variable Implementierung hast, dann fragt ich mich, wie du überhaupt irgendwas auf Windows zu laufen bekommst. Condition-Variablen braucht man doch dauernd irgendwo wenn man mit PTHREADS programmiert...

Tue ich ja bisher nicht - PThreads kommt jetzt nur in Zusammenhang mit der Barrier ins Spiel. Un PThreads kosten unter *NIX eben nichts extra, weil standardmäßig vorhanden.

Aber es wird wohl jetzt darauf hinauslaufen, dass ich die pthreads-win32 verwende, die ist doch schlanker als gedacht - und so kommt auch ein bissl ordendlicher POSIX-Standard in das Windowssystem

WinAPI-Profi schrieb:

Warum nicht WaitForMultipleObjects benutzen??????????????

Weil mit WaitForMultipleObjects 1. keine echte Barrier ist 2. und sämtliche Frickeleien um damit eine Barrier hinzubekommen nicht sauber Thread-safe wären.

Jochen Kalmbach

Wenn man die Doku zur Funktion liest wäre wohl ein semaphor das richtige...
http://www.mkssoftware.com/docs/man3/pthread_barrier_wait.3.asp

Warten tut man abber damit immer noch mit den "WaitFor*" Funktionen...

Martin Richter

Ich sehe auch einen Semaphore als Lösung, wenn alles es richtig verstanden habe.

Wir brauchen einen Semaphore und ein Ready Event.
1. Der Semaphore wird angelegt mit der Größe n-1, Anfangszähler 0. Der Ready Event ist non signaled.
2. Jeder Thread der fertig ist mach ein WaitForSingleObject auf den Semaphore, Wartezeit==0.
2.1. Der Semaphore ist noch verfügbar, prima, da sind noch andere Threads die laufen. Wir machen einen INFINITE WaitForSingleObject auf das Ready Event.
Wenn das Ready Event gesetzt wird gibt diese Funktion 0 zurück für diesen Thread.
2.2. Der Semaphore ist nicht mehr verfügbar. D.h. n-1 Threads sind fertig und warten brav auf das Ready Event. Prima! Unser Thread setzt das Event. Und bekommt selbst PTHREAD_BARRIER_SERIAL_THREAD signalisiert. Er ist der Thread der nun die Sachen zusammenfassen darf.
Und das ist schön so, denn wir haben keinen Kontextswitch und der letzte Thread macht nun die Arbeit.
3. Alle Semaphoren werden natürlich released bei Funktionende.

Korrekt?

hustbaer

Nein, nicht korrekt, da du beim letzten Thread eine Race-Condition hast.
Was wenn zwei threads gleichzeitig ankommen?
Dann glauben beide der letzte Thread zu sein. -> *Bumm*

Martin Richter

hustbaer schrieb:

Nein, nicht korrekt, da du beim letzten Thread eine Race-Condition hast.
Was wenn zwei threads gleichzeitig ankommen?
Dann glauben beide der letzte Thread zu sein. -> *Bumm*

Nein! Der eine bekommt der Semaphore (Thread n-1), der n-te Thread bekommt ihn eben nicht mehr. Der bekommt ein Timeout durch den Wait!

Der Semaphore macht genau das:
http://msdn.microsoft.com/en-us/library/ms682438(VS.85).aspx

Zitat:
The state of a semaphore is signaled when its count is greater than zero and nonsignaled when it is zero. The count is decreased by one whenever a wait function releases a thread that was waiting for the semaphore. The count is increased by a specified amount by calling the ReleaseSemaphore function.

Jochen Kalmbach

hustbaer schrieb:

Nein, nicht korrekt, da du beim letzten Thread eine Race-Condition hast.
Was wenn zwei threads gleichzeitig ankommen?
Dann glauben beide der letzte Thread zu sein. -> *Bumm*

Nee... Mit Semaphoren gibt es keine Race-Condition... Irgendeiner ist immer der letzte...
Die Zählung erfolgt immer korrekt; somit kann jeder Thread entscheiden, ob er der letzte war oder nicht...

Jochen Kalmbach

Wobei ich sagen muss:
Das Semaphor macht es genau anders herum

Somit muss man es doch selber bauen mittels "InterlockedDecrement" und "CreateEvent" und "WaitForSingleObject"

So in der Form:

typedef struct 
{
  HANDLE hEvt;
  volatile LONG lCount;
} pthread_barrier_t;

int pthread_barrier_init(pthread_barrier_t* barrier, unsigned count)
{
  barrier->hEvt = CreateEvent(NULL, TRUE, FALSE, NULL);
  barrier->lCount = count;
}

int pthread_barrier_wait(pthread_barrier_t *barrier)
{
  if (barrier != NULL)
    return EINVAL;
  LONG lLast = InterlockedDecrement(&barrier->lCount);
  if (lLast == 0)
    SetEvent(barrier->hEvt);
  WaitForSingleObject(barrier->hEvt);
  if (lLast == 0) return PTHREAD_BARRIER_SERIAL_THREAD;
  return 0;
}

int pthread_barrier_destroy(pthread_barrier_t *barrier)
{
  CloseHandle(barrier->hEvt);
}

hustbaer

@Jochen/Martin:
Das Problem ist nicht der Nte Thread, sondern der (N+1)te (und (N+2)te und (N+3)te usw.).

@Jochen:
Das funktioniert soweit als "one time barrier".

Eine PTHREADS barrier resettet sich aber automatisch, nachdem der N. thread "durchgelaufen" ist.

Falls du das auch ohne grossen Aufwand lösen kannst will ich sehen
(Ich hab bisher keine wirklich einfache Lösung gefunden -- also nichts was wesentlich einfacher ist, als wenn man sich gleich eine Condition-Variable nachstrickt. Was nicht wirklich ganz einfach ist.)

Jochen Kalmbach

Du meinst, wenn sowas gemacht wird?

int ThreadProc()
{
   pthread_barrier_wait(..);
   pthread_barrier_wait(..);
   pthread_barrier_wait(..);
   pthread_barrier_wait(..);
   pthread_barrier_wait(..);
   pthread_barrier_wait(..);
   pthread_barrier_wait(..);
   pthread_barrier_wait(..);
   pthread_barrier_wait(..);
   pthread_barrier_wait(..);
}

Und der Thread eben x-Mal gestartet wird?
Das sollte sich mit Events relativ einfach nachbauen lassen... einfacher geht es vermutlich noch, wenn man vor dem return noch ein Semaphor macht, wo wieder alle Durch müssen... dann kann man vorher den Event wieder resetten...