Thread-Barrier in WinAPI?

[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...

[jesus was black]

Klein und gut: http://zthread.sourceforge.net/ - http://zthread.sourceforge.net/html/classZThread_1_1Barrier.html
Falls es bloated sein soll: http://pocoproject.org/

[hustbaer]

Nicht-so-klein, und nicht-so-gut.

Die ZThread ist leider von äusserst fragwürdiger Implementierungs-Qualität.
D.h. von seltsamen Design-Entscheidungen, über Sachen die um Grössenordnungen langsamer sind als sie sein müssten, bis zu Memory-Leaks und echten Bugs ist da alles zu finden.

Ich würde mich davon fernhalten!

[hustbaer]

Jochen Kalmbach schrieb:

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?

Zum Beispiel, ja.

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...

Sollte, müsste, könnte. Zeig her wenn du was hast!

(Muss nicht super-performant sein, mir reicht völlig wenn es einfach ist, und korrekt. Wie gesagt: ich hab bis jetzt noch keine Variante gefunden, die einfacher wäre, als sich eine Condition-Variable nachzubauen. Und natürlich gilt es nicht die neuen Vista+ Funktionen (SleepConditionVariableCS etc.) zu verwenden.)

[Jochen Kalmbach]

Folgendes sollte Problemlos funktionieren:

#include <windows.h>
#include <stdio.h>
#include <tchar.h>
#include <process.h>
#include <errno.h>

#define PTHREAD_BARRIER_SERIAL_THREAD 1

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

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

int pthread_barrier_wait(pthread_barrier_t *barrier) 
{ 
  if (barrier == NULL) 
    return EINVAL; 
  LONG lLast = InterlockedDecrement(&barrier->lCount); 
  if (lLast == 0) 
  {
    // Stelle sicher, dass nacher alle wieder anhalten...
    ResetEvent(barrier->hEvtSync);
    SetEvent(barrier->hEvt); 
  }

  // Hier kommt immer nur *einer* raus...
  WaitForSingleObject(barrier->hEvt, INFINITE); 

  // So, gehe jetzt wieder anders rum durch, bis ich bei lOrgCount bin
  LONG lLastNext = InterlockedIncrement(&barrier->lCount); 
  if (lLastNext == barrier->lOrgCount)
  {
    // jetzt sind alle wieder drausen, also bin ich wieder synchron...
    SetEvent(barrier->hEvtSync);
  }
  else
  {
    // Hab den Zähler noch nicht erreicht, lasse somit den nächsten raus...
    SetEvent(barrier->hEvt); 
    // ... und warte bis alle drausen sind
    WaitForSingleObject(barrier->hEvtSync, INFINITE); 
  }

  if (lLast == 0)
  {
    return PTHREAD_BARRIER_SERIAL_THREAD; 
  }
  return 0; 
} 

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

void t(void* p)
{
  pthread_barrier_t *b = (pthread_barrier_t*) p;

  printf("1");
  pthread_barrier_wait(b);
  printf("2");
  pthread_barrier_wait(b);
  printf("3");
  pthread_barrier_wait(b);
  printf("4");
  pthread_barrier_wait(b);
  printf("5");
  pthread_barrier_wait(b);
  printf("6");
  pthread_barrier_wait(b);
}

int _tmain()
{
  int cnt = 5;
  pthread_barrier_t b;
  pthread_barrier_init(&b, cnt);

  for(int i=0; i<cnt; i++)
  {
    _beginthread(t, 0, &b);
  }
  while(1) Sleep(100);

  pthread_barrier_destroy(&b);
}

[Martin Richter]

Also bei Deinem Code gibt es auch ein Problem, wenn esmehr als n Threads gibt.
Dann gibt es bei Dir einen Underflow.
Der n+1teThread wird auch angehalten, wird aber sofort wieder von n-then Thread losgelassen.

Oder liege ich da falsch?

Das gleiche Problem, wie bei meiner Semaphore Lösung.
Das Problem ist, dass eigentlich nicht definiert ist was passiert wen es mehr Threads gibt.

[Jochen Kalmbach]

Martin Richter schrieb:

Also bei Deinem Code gibt es auch ein Problem, wenn esmehr als n Threads gibt.

Also, durch Fehlbedienung geht natürlich alles schief... wenn natürlich mehr Threads das Ding aufrufen als beim Erzeugen angegeben wurde, dann besteht eh ein Programmierfehler... oder hab ich da jetzt was in der Docu zu dem barrier übersehen...

[hustbaer]

Pfuh.

Keine Ahnung ob die PTHREADS API erlaubt dass mehr als N Threads da reinfahren.
Allerdings würde ich eine Implementierung immer so auslegen, dass es trotzdem korrekt funktioniert.

[Jochen Kalmbach]

hustbaer schrieb:

Pfuh.

Keine Ahnung ob die PTHREADS API erlaubt dass mehr als N Threads da reinfahren.
Allerdings würde ich eine Implementierung immer so auslegen, dass es trotzdem korrekt funktioniert.

Wie soll denn das gehen?
Es ist das GIGO Prinzip! (Garbage-In-Garbage-Out).

PS: Mir fehlt immer noch Dein Kommentar, ob das jetzt Deinen Wünschen entspricht...

[Martin Richter]

Jochen Kalmbach schrieb:

Es ist das GIGO Prinzip! (Garbage-In-Garbage-Out).

Jein!

Wenn die Regel lautet belieg viele Threads, dann würde folgendes passieren
Thread 1 kommt an wartet auf Thread n, wird 0 zurückgeben
Thread 2 kommt an wartet auf Thread n, wird 0 zurückgeben
...
Thread n-1 kommt an wartet auf Thread n wird 0 zurückgeben

Die nächsten 3 Anrufe sind zeitgleich:
Thread n kommt an und wir den Magic zurückgeben
Thread n+1 kommt an und wartet nun das zum 2n-ten Male die Funktion gerufen wird.
Thread n+2 kommt an und wartet nun das zum 2n-ten Male die Funktion gerufen wird.

Das wäre kein Garbage. Es kommt auf die Definition an.

[Jochen Kalmbach]

So lange es sich gleich verhält wie unter pthreads, hab ich damit keine Probleme

[Probe-Nutzer]

Hallo,

immerhin gibt es das hier (nur als Ergänzung):

http://msdn.microsoft.com/en-us/library/b8t6afft.aspx

MfG,

Probe-Nutzer

[hustbaer]

Jochen Kalmbach schrieb:

hustbaer schrieb:

Pfuh.

Keine Ahnung ob die PTHREADS API erlaubt dass mehr als N Threads da reinfahren.
Allerdings würde ich eine Implementierung immer so auslegen, dass es trotzdem korrekt funktioniert.

Wie soll denn das gehen?
Es ist das GIGO Prinzip! (Garbage-In-Garbage-Out).

PS: Mir fehlt immer noch Dein Kommentar, ob das jetzt Deinen Wünschen entspricht...

Er.
Sorry für die späte Antwort.

Was heisst meinen Wünschen
Ich brauch sowas nicht, ich verwende selbst die Boost.Thread wenn ich was derartiges brauche.

Wenn du meinst ob ich es anerkenne als "einfacher als wenn man sich eine eigene Condition-Variablen Implementierung strickt"... nö. Es ist wesentlich weniger Code, aber dafür (für mich) schwerer zu verstehen. (Und natürlich wesentlich langsamer, was ich aber explizit als Kriterium ausgenommen hatte)