BARRIER - Synchronisation paralleler Tasks

• wichtige Synchronisations-Funktion:

alle (oder eine Gruppe von) Threads warten, bis alle an einer Stelle angekommen sind.

• Interface:

Datentyp barrier_t

• "opaque", d.h. nur Pointer darauf kommen vor

int barrier_init(barrier_t *bp, int max);

• Initialisierung, Anzahl der mitmachenden Threads als Parameter

int barrier_wait(barrier_t *bp );

• Synchronisation: warte, bis alle da sind

int barrier_destroy(barrier_t *bp );

• Freigabe der Ressourcen
• Implementation, 1. Versuch (fehlerhaft)

Sourcen:

barrier1.h	Header für 1. Version
barrier1.c	Implementierung

Barrier-Typ enthält:

• Bedingungsvariable: Sind alle angekommen ?
• zugehörigen Lock
• Gesamtzahl der beteiligten Threads
• Anzahl cnt der bereits angekommenen Threads

barrier_wait:

      lock
      inkrementiere Anzahl cnt der angekommenen Threads
      Wenn ich der letzte bin:
        setze cnt = 0 (für die nächste Barrier)
        wecke alle anderen
      sonst
        warte bis zum Wecken
        (cnt muß dann 0 sein!)
      unlock

• Fehler dieser Implementation:

Race-Condition bei einer zweiten Barrier:

        maxcnt = 2,

            Thread 0          Thread 1            cnt
         
            barrier1          barrier1             0
             lock
             cnt++                                 1
             wait/unlock
                               lock
                               cnt++               2
                               max -> cnt = 0      0
                               broadcast
                               unlock

                              barrier2
                               lock
            wird wach, 
            lock besetzt    
                               cnt++               1
                               wait/unlock
            bekommt lock
            while (cnt>0)
            wait/unlock

                     DEADLOCK  !

Problem: cnt ist gleichzeitig Zähler der Wartenden und in cnt==0 die Durchschaltbedingung für die Barrier. Bei einer zweiten Barrier geraten beide Funktionen in Konflikt.

Lösung: zusätzliche Variable barrier->phase als Durchschaltbedingung. Dadurch ist der neue Wert cnt=1 für die anderen irrelevant

• Implementation, verbesserte Version:

Sourcen:

barrier.h	Header für korrigierte Version
barrier.c	Implementierung

barrier_wait:

      lock
      merke dir den Wert von phase
      inkrementiere Anzahl cnt der angekommenen Threads
      Wenn ich der letzte bin:
        setze cnt = 0 (für die nächste Barrier)
        toggle phase
        wecke alle anderen
      sonst
        warte bis zum Wecken
        (phase muß sich geändert haben!)
      unlock

zum Vergleich:

            Thread 0          Thread 1            cnt    phase

            barrier1          barrier1             0       0
             lock
             my_phase=0
             cnt++                                 1
             wait/unlock
                               lock
                               my_phase=0
                               cnt++               2
                               max -> cnt = 0      0
                               phase = 1-phase             1
                               broadcast
                               phase != my_phase
                                -> unlock

                              barrier2
                               lock
            wird wach, 
            lock besetzt    
                               my_phase=1
                               cnt++               1
                               wait/unlock
            bekommt lock
            phase != my_phase
             -> unlock