next up previous contents index
Next: 3.5 Bedingungsvariablen und Mutual Up: 3 POSIX threads Previous: Lösung in FORTRAN

3.4 Beginn und Ende von Mutual exclusion

Im folgenden wollen wir das Sprachkonstrukt

atomic tex2html_wrap_inline2217 end
implementieren.  Zur Verfügung stehen uns die Pthread-Funktionen lock  und unlock  mit den folgenden Spezifikationen:
int pthread_mutex_lock (pthread_mutex_t* mux);
locken eines mutexes.

int pthread_mutex_unlock(pthread_mutex_t* mux);
unlocken eines mutexes.

int pthread_mutex_init (pthread_mutex_t* mux,
                        pthread_mutexattr_t attr);
Initialisierung eines mutex mit gew. Attributen.
    

Die Datentypen pthread_mutex_t  und pthread_mutexattr_t  sowie die Funktionen werden im Header File pthread.h deklariert. Als Attribut kann man ein default-Attribut  verwenden.

        pthread_mutexattr_t pthread_mutexattr_default;
und schon initialisiert ist. Nur falls man spezielle Eigenschaften der Mutexe haben möchte, muß man sich diese Attribute mit den entsprechenden Funktionen selbst erzeugen. Im Gegensatz zu Pthreads müssen Mutexe vor der Benutzung initialisiert werden.

Mutexe  dienen der Serialisierung des Zugangs verschiedener Pthreads  zu atomaren Bereichen. lock  beginnt einen atomaren Bereich  und unlock  verläßt den atomaren Bereich. Falls ein Pthread sich in einem atomaren Bereich befindet (zwischen lock und unlock) wird ein anderer Pthread, der einen lock verlangt, blockiert. Nach Ausführung von unlock erhält genau ein anderer Pthread, der auf einen lock wartet, den lock. Welcher das ist, wird vom Betriebssystem festgelegt. Falls die Aufrufe erfolgreich sind, wird als Error code 0 zurückgegeben, sonst ein Wert < 0.

Im Gegensatz zu unserer ursprünglichen Definition vom atomaren Bereich, bieten die Mutexe die Freiheit, verschiedene kritische Bereiche zu definieren, die sich überlappen können. Einem atomaren Bereich (in der ursprünglichen Definition) entspräche die Verwendung von genau einem Mutex für alle kritischen Bereiche. Bei der Implementierung des atomic Sprachkonstrukts haben wir somit die Freiheit, verschiedene Mutexe zu verwenden und somit verschiedene kritische Bereiche zu definieren.

Damit ist atomic tex2html_wrap_inline2217 end tex2html_wrap_inline2396

       pthread_mutex_t globalmux;
       e= pthread_mutex_init (&globalmux, pthread_mutexattr_default); 
       e= pthread_mutex_lock (&globalmux);
       S1; ...; Sn;
       e= pthread_mutex_unlock(&globalmux);
 

Diese Implementierung ist allerdings nicht ganz korrekt, z.B. müßte

con z:= x + y; atomic x:= 1; y:= 2 end end
als
con atomic z:= x + y end; atomic x:= 1; y:= 2 end end
implementiert werden, damit die Zwischenzustände wirklich nicht sichtbar sind.

Wichtig: Bei der Implementierung besteht also zusätzlich die Aufgabe, den auszuschließenden Gegenpart  zu identifizieren und mit dem Mutex auszuschließen.

aufgabe656

Lösungsvorschlag in C++.  Die Statements werden hier auf die zwei Funktionen P1 und P2 aufgeteilt. Innerhalb dieser Funktionen erfolgt jeweils ein lock bevor das Statement ausgeführt wird. Und nach der Ausführung wird der lock wieder freigegeben. Im Hauptprogramm wird (nach den Deklarationen) zu erst der Mutex mux initialisiert und dann werden wie schon bekannt, die Pthreads gestartet. Nach der Beendigung der Pthreads werden dann wieder die Ergebnisse ausgegeben.

          #include <iostream.h>
          #include <pthread.h>
          
          int x, u, v, w; 
          pthread_mutex_t mux;
          
          void *P1 (void * arg)
          {
             int e; 
             e = pthread_mutex_lock(&mux); 
             x = u + v + w; 
             e = pthread_mutex_unlock(&mux); 
             return arg;
          }
          
          void *P2 (void * arg)
          {
             int e; 
             e = pthread_mutex_lock(&mux); 
             u = 3; 
             v = 4;
             w = 5; 
             e = pthread_mutex_unlock(&mux); 
             return arg;
          }
          
          int main()
          {
              pthread_t t1, t2;
              long int i1, i2;
              void *o1, *o2;
          
              i1 = 1; i2 = 2; 
              int i = 0; int e;  
          
              e = pthread_mutex_init(&mux, pthread_mutexattr_default); 
          
              while (i < 10) { i++;
                    u = 0; v = 1; w = 2;    
          
                    e = pthread_create(&t1, pthread_attr_default, P1, &i1); 
                    e = pthread_create(&t2, pthread_attr_default, P2, &i2); 
          
                    e = pthread_join(t1, &o1); 
                    e = pthread_join(t2, &o2); 
          
                    cout << " u = " << u; 
                    cout << " v = " << v; 
                    cout << " w = " << w;
                    cout << " x = " << x; 
                    cout << "\n";
              };
              return 0;
          }

Die Ausgabe könnte etwa wie folgt aussehen. Es kommen jetzt nur die beiden Werte x = 3 und x = 12 vor. Die Ausgabe x = 3 zeigt, daß die Summe u + v + w vor den Zuweisungen an die Variablen berechnet wurde. Die Ausgabe x = 12 zeigt, daß zu erst die Zuweisungen an die Variablen ausgeführt wurden und dann die Summe u + v + w berechnet wurde.

                 u = 3 v = 4 w = 5 x = 3
                 u = 3 v = 4 w = 5 x = 3
                 u = 3 v = 4 w = 5 x = 3
                 u = 3 v = 4 w = 5 x = 12
                 u = 3 v = 4 w = 5 x = 3
                 u = 3 v = 4 w = 5 x = 3
                 u = 3 v = 4 w = 5 x = 3
                 u = 3 v = 4 w = 5 x = 3
                 u = 3 v = 4 w = 5 x = 12
                 u = 3 v = 4 w = 5 x = 3
                 u = 3 v = 4 w = 5 x = 12
                 u = 3 v = 4 w = 5 x = 3
                 u = 3 v = 4 w = 5 x = 3
                 u = 3 v = 4 w = 5 x = 3

aufgabe665

D.h. implementiere

 VAR    A: ARRAY [1..m] OF INTEGER;

tex2html_wrap_inline2449 : INTEGER;

(* Initialisiere A *)

tex2html_wrap_inline2451 ;

con S(1); S(2); S(3) end;

print( tex2html_wrap_inline2449 );

Wobei S(i) tex2html_wrap_inline2396

 VAR     tex2html_wrap_inline2463 : INTEGER;

b, e, j: INTEGER;

tex2html_wrap_inline2467 ;

tex2html_wrap_inline2469 ;

tex2html_wrap_inline2471 ;

if i = 3 then e:=m end;

for j:=b to e do

tex2html_wrap_inline2481 ; end;

atomic tex2html_wrap_inline2241 end;

Lösungsvorschlag in C++.  Der Programmteil S(i) wird von der Funktion sfunc ausgeführt. In sfunc werden zunächst die Arbeitsbereiche (abängig von i) bestimmt (Berechnung von e und b). Dann wird lokal die Summe über den entsprechenden Bereich gebildet und anschliessend (mit lock auf den Mutex pmt) die lokale Summe zu der globalen Summe hinzuaddiert. Im Hauptprogramm wird zunächst der Mutex pmt und das Array a initialisiert (mit Bildung einer Kontrollsumme). Dann werden 7 Pthreads gestartet (in dem Feld ia wird der Arbeitsindex i mitgeteilt) und wieder auf ihre Beendigung gewartet.

          #include <iostream.h>
          #include <pthread.h>
          
          const int ANZ_PTHREADS=7;
          const wsize=2000;
          long int a[wsize];
          long int sum=0;
          long int xsum=0; 
          
          pthread_mutex_t pmt;
          pthread_t pt[ANZ_PTHREADS];
          
          void *sfunc(void  *arg)
          {
            long int lsum=0;
            long int j, b, e, i =*((long int *)arg);
          
            b=(wsize/ANZ_PTHREADS)*(i-1);
            e=(wsize/ANZ_PTHREADS)*i;
            if (i==ANZ_PTHREADS) e=wsize;
            cout << " i=" << i << " b=" << b << " e=" << e << "\n";
            
            for ( j=b; j<e; j++) lsum+=a[j];
          
            pthread_mutex_lock(&pmt);
            sum+=lsum;
            pthread_mutex_unlock(&pmt);
            return arg;
          }
          
          main(){
             void* return_pointer[ANZ_PTHREADS];
             long int ia[ANZ_PTHREADS];
             long int j, l;
          
          pthread_mutex_init(&pmt,pthread_mutexattr_default);
          for ( j=0; j<wsize; j++)
            {
               a[j]=j; xsum+=j;  
            }
          
          for ( l=0; l<ANZ_PTHREADS; l++)
            {
               ia[l]=l+1; 
               pthread_create(&pt[l], pthread_attr_default, 
                                      sfunc, (void *) &ia[l]);
            }
          
          for ( l=0; l<ANZ_PTHREADS; l++)
            {
               pthread_join(pt[l], &return_pointer[l]);
            }
          
             cout << "Summe ist  " << sum << "\n";
             cout << "Summe soll " << xsum << "\n";
             return 0;
          }

Die Ausgabe könnte etwa wie folgt aussehen. Die Anzeige von i = zeigt, daß die Arbeitsschritte in der Reihenfolge 1, 4, 3, 2, 6, 7 und 5 begonnen wurden. Das Ergebnis ist wie erwartet.

                   i=1 b=0 e=285
                   i=4 b=855 e=1140
                   i=3 b=570 e=855
                   i=2 b=285 e=570
                   i=6 b=1425 e=1710
                   i=7 b=1710 e=2000
                   i=5 b=1140 e=1425
                  Summe ist  1999000
                  Summe soll 1999000


next up previous contents index
Next: 3.5 Bedingungsvariablen und Mutual Up: 3 POSIX threads Previous: Lösung in FORTRAN

parallel@rz.uni-mannheim.de
Mon Okt 28 14:38:25 PST 1996