vorige Seite
 
Originalskript
 

 
Das sogenannte ,,Erzeuger-Verbraucher-Problem`` beruht auf zwei (pseudoparallelen) Prozessen, die über einen gemeinsam genutzten Speicher Daten übertragen. Ein Erzeugerprozeß erzeugt Daten und legt sie in einem dem Verbraucher zugänglichen Speicherbereich -- hier durch globale Variablen angedeutet -- ab; ein Verbraucher liest diese Daten und verarbeitet sie weiter. Als Erzeuger ist etwa ein Anwendungprogramm denkbar, welches Daten an den Druckertreiber, den Verbraucher, überträgt. Das Problem besteht nun darin, die beiden Prozesse so miteinander zu ,,synchronisieren``, daß einerseits eine Operation eines Prozesses auf dem gemeinsamen Speicher nicht durch eine Operation des anderen Prozesses unterbrochen wird und so  inkonsistente Speicherzustände auftreten und andererseits der Pufferspeicher nicht überläuft, indem der Erzeuger Daten wesentlich schneller produziert als der Verbraucher sie verarbeiten kann. 

Ein Lösungsansatz besteht darin, dem Erzeuger und Verbraucher einen gemeinsamen Speicher, der als Ringpuffer organisiert ist, zuzuteilen. Im folgenden Programm betrachten wir einen Ringpuffer mit n Einträgen, der als globales Array repräsentiert wird. Die globale Variable e gibt die Anzahl der Einträge im Puffer an. Die Prozedur erzeuger legt nun Elemente im Ringpuffer ab, falls er noch nicht gefüllt ist (e<n). Die Prozedur verbraucher konsumiert Elemente aus dem Ringpuffer, falls dieser nicht leer ist (e 0). Damit ergibt sich das folgende Programm. 

program Erzeuger_Verbraucher; 
const n = ...; 
type eintrag = ...; 
var r: array[0..n-1] of eintrag; 
    e: integer; 

procedure erzeuger; 
var elem: eintrag; 
    ze: integer; 
    i: integer; 
begin 
  i := 0; 
  repeat 
    ... (* Erzeuge Element elem *) 
    while e = n do nothing; 
    r[i] := elem; 
    i := (i + 1) mod n; 
    ze := e; (* Zugriff auf globale Variable *) 
    e := ze + 1; 
  until false; 
end; 

procedure verbraucher; 
var elem: eintrag; 
    zv: integer; 
    i: integer; 
begin 
  i := 0; 
  repeat 
    while e = 0 do nothing; 
    elem := r[i]; 
    i := (i + 1) mod n; 
    zv := e; (* Zugriff auf globale Variable *) 
    e := zv - 1; 
    ... (* Verbrauche Element elem *) 
  until false; 
end; 

begin           (* Hauptprogramm *) 
  e := 0;  
  parbegin erzeuger, verbraucher parend; 
end. 

Das obige Programm verwendet zur Koordination der beiden Prozesse die globale Variable e. Auf diese Variable greifen die Prozesse zu, indem sie zuerst den Wert lesen und danach den um eins inkrementierten bzw. dekrementierten Wert ablegen. Diese umständliche Schreibweise verdeutlicht, daß die Zuweisung e := e + 1 nicht notwendigerweise als atomare Operation übersetzt wird, sondern im compilierten Programm eventuell durch zwei oder mehr atomare Einzeloperationen der Maschinensprache dargestellt wird. 

Die Erfahrungen mit dem Programm increment geben Anlaß zu der Vermutung, daß die globale Variable e hier nicht korrekt behandelt wird, denn bei einer ungüngstig geschachtelten Ausführung der Zugriffe auf e kann ein Fehler entstehen. Dazu denken wir uns z.B. das Szenario, daß etwa ein Element in dem Puffer vorhanden ist. Der Verbraucher greift auf dieses Element zu und liest den Wert 1 der globalen Variablen e, um ihn zu dekrementieren. Bevor der aktuelle Wert 0 abgelegt wird, legt der Erzeuger ein neues Element im Ringpuffer ab und inkrementiert die globale Variable e, so daß e den Wert 2 annimmt. Schließlich speichert jetzt der Verbraucher den inzwischen veralteten Wert 0 in e ab. Damit ist ein Fehler entstanden, denn tatsächlich ist ein Element im Ringpuffer vorhanden. Zur Verdeutlichung dient Abbildung 1.1, die die oben beschriebene Verschachtelung der Befehle beschreibt. 

 figure49 
Abbildung 1.1:   Ablauftabelle zum Erzeuger-Verbraucher-Programm 

Um dieses fehlerhafte Verhalten zu unterbinden, ist es erforderlich, den Zugriff auf die globale Variable e derart zu schützen, daß ein Prozeß nach dem Lesen dieser Variablen nicht unterbrochen werden darf, bis er den Wert wieder zurückgeschrieben hat. Im nächsten Abschnitt betrachten wir geeignete Konzepte, dieses Problem des wechselseitigen Ausschlusses zu lösen.

 

 
vorige Seite