Erzeuger-Verbraucher-Problem

Milly Krenz Dezember 24, 2016 E 16 0
FONT SIZE:
fontsize_dec
fontsize_inc

In der Computersprache ist die Erzeuger-Verbraucher-Problem, ein klassisches Beispiel für ein Multi-Prozess-Synchronisierungsproblem. Das Problem beschreibt zwei Verfahren, die Erzeuger und Verbraucher, die ein gemeinsames, Puffer fester Größe als Warteschlange verwendet zu teilen. Aufgabe des Herstellers ist es, einen Teil der Daten zu generieren, legen Sie sie in den Puffer und erneut starten. Zugleich ist der Verbraucher diese Daten aufnimmt einem Stück zu einer Zeit. Das Problem ist, um sicherzustellen, dass der Hersteller nicht versuchen, Daten in den Puffer hinzuzufügen, wenn er voll ist, und dass der Verbraucher nicht versuchen, Daten aus einem leeren Puffer zu entfernen.

Die Lösung für den Hersteller ist es, entweder schlafen oder zu verwerfen Daten, wenn der Puffer voll ist. Das nächste Mal, wenn der Verbraucher ein Element entfernt von dem Puffer, benachrichtigt er den Produzenten, der um den Puffer wieder zu füllen beginnt. Auf die gleiche Weise kann der Verbraucher gehen zu schlafen, wenn er feststellt, der Puffer leer sein. Das nächste Mal, der Produzent legt Daten in den Puffer, wacht es auf den schlafenden Verbraucher. Die Lösung kann mit Hilfe von Interprozess-Kommunikation erreicht werden kann, typischerweise unter Verwendung von Semaphoren. Eine unzureichende Lösung könnte in einer Sackgasse, wo beide Prozesse warten darauf, geweckt zu werden führen. Das Problem kann auch verallgemeinert werden, um mehrere Erzeuger und Verbraucher werden.

Unzureichende Umsetzung

Um das Problem zu lösen, könnte ein weniger erfahrener Programmierer kommen mit einer unten Lösung. In der Lösung zwei Bibliotheksroutinen verwendet, und. Wenn der Schlaf aufgerufen wird, wird der Anrufer blockiert, bis ein anderer Prozess weckt es auf, indem Sie die Wake-up-Routine. Die globale Variable hält die Anzahl der Elemente in dem Puffer.

Das Problem bei dieser Lösung ist, dass es eine Race Condition, die in eine Sackgasse führen kann enthält. Stellen Sie sich folgendes Szenario vor:

  • Der Verbraucher hat gerade lesen Sie die Variable, bemerkte es ist null und ist gerade dabei, innerhalb des Blocks zu bewegen.
  • Gerade vor dem Aufruf von Schlaf, ist der Verbraucher unterbrochen und die Produzenten wieder aufgenommen wird.
  • Der Hersteller erstellt ein Element, bringt es in den Puffer und erhöht.
  • Da der Puffer leer war vor dem letzten Außerdem versucht der Hersteller zum Aufwecken des Verbrauchers.
  • Leider wurde der Verbraucher noch nicht schlafen, und der Weckruf ist verloren. Wenn der Verbraucher wieder, es geht um zu schlafen und wird nie wieder geweckt werden. Dies ist, weil der Verbraucher lediglich durch den Hersteller geweckt, als gleich 1 ist.
  • Der Produzent Schleife, bis der Puffer voll ist, nach dem es auch schlafen gehen.

Da beide Prozesse werden für immer schlafen, haben wir in eine Sackgasse führen. Diese Lösung ist daher unbefriedigend.

Eine alternative Analyse besteht, dass, wenn die Programmiersprache nicht die Semantik der gleichzeitige Zugriffe auf gemeinsam genutzte Variablen definieren, ohne Verwendung von Synchronisation, dann ist die Lösung nicht zufriedenstellend ist aus diesem Grund, ohne dass explizit eine Race-Bedingung zu demonstrieren.

Verwendung Semaphore

Semaphore lösen das Problem der verlorenen Weckrufe. Bei der Lösung unter verwenden wir zwei Semaphore und, um das Problem zu lösen. ist die Anzahl der Einzelteile bereits im Puffer und zum Lesen zur Verfügung, während die Anzahl verfügbarer Plätze in dem Puffer, in dem Einträge geschrieben werden konnte. inkrementiert und dekrementiert, wenn ein neues Element in den Puffer gestellt. Wenn der Hersteller versucht, verringern, wenn sein Wert Null ist, ist der Hersteller in den Ruhezustand. Das nächste Mal ein Element verbraucht ist, wird erhöht, und der Produzent aufwacht. Der Verbraucher funktioniert analog.

Die Lösung oben funktioniert gut, wenn es nur einen Hersteller und Verbraucher. Mit mehreren Herstellern, die denselben Speicherraum für die Artikel Puffer oder mehreren Verbrauchern, die denselben Speicherplatz enthält diese Lösung ein ernstes Wettlaufsituation, die in zwei oder mehrere Prozesse Lesen oder Schreiben in den gleichen Schlitz zur gleichen Zeit führen könnte. Um zu verstehen, wie dies möglich ist, sich vorzustellen, wie das Verfahren durchgeführt werden kann. Es könnte zwei Aktionen enthalten, eine Bestimmung des nächsten freien Steckplatz und die andere schriftlich hinein. Wenn das Verfahren kann gleichzeitig von mehreren Herstellern ausgeführt werden soll, dann ist das folgende Szenario möglich:

  • Zwei Hersteller Dekrement
  • Einer der Produzenten ermittelt den nächsten freien Steckplatz im Puffer
  • Zweite Produzenten ermittelt den nächsten freien Steckplatz und erhält das gleiche Ergebnis wie die erste Produzent
  • Sowohl die Hersteller in den gleichen Steckplatz schreiben

Um dieses Problem zu überwinden, müssen wir einen Weg, um sicherzustellen, dass nur einen Hersteller zu einem Zeitpunkt ausgeführt wird. In anderen Worten brauchen wir einen Weg, um einen kritischen Abschnitt mit gegenseitigem Ausschluss auszuführen. Um dies zu erreichen verwenden wir eine binäre Semaphore genannt Mutex. Da der Wert eines binären Semaphore nur entweder Eins oder Null sein kann nur ein Prozeß zwischen und Ausführung werden. Die Lösung für mehrere Erzeuger und Verbraucher ist unten gezeigt.

Feststellen, dass die Reihenfolge, in der verschiedene Semaphore werden inkrementiert oder dekrementiert ist wesentlich: Änderung der Reihenfolge kann zu einem Deadlock führen kann.

Verwenden von Monitoren

Der folgende Pseudocode zeigt eine Lösung für die Erzeuger-Verbraucher-Problem mit Monitoren. Seit gegenseitigen Ausschluss ist implizit mit Monitoren, keine zusätzliche Anstrengungen erforderlich sind, um den kritischen Abschnitt zu schützen. Mit anderen Worten, die unten gezeigte Lösung arbeitet mit einer beliebigen Anzahl von Produzenten und Konsumenten ohne Modifikationen. Bemerkenswert ist auch, dass mit Monitoren macht Rennbedingungen sehr viel weniger wahrscheinlich als bei Verwendung von Semaphoren.

Beachten Sie die Verwendung der Angaben in dem obigen Code, sowohl bei der Prüfung, ob der Puffer voll oder leer ist. Mit mehreren Verbrauchern, gibt es eine Race-Bedingung, wo ein Verbraucher wird mitgeteilt, dass ein Element in den Puffer gestellt worden, aber ein anderer Verbraucher wartet schon auf den Monitor so entfernt sie aus dem Puffer statt. Wenn das war stattdessen ein, vielleicht zu viele Elemente in den Puffer gestellt werden oder ein Entfernen könnte auf einen leeren Puffer versucht werden.

Ohne Semaphore oder Monitore

Die Erzeuger-Verbraucher-Problem, insbesondere im Fall eines einzelnen Produzenten und Einzel Verbraucher betrifft stark auf die Implementierung einer FIFO oder einen Kommunikationskanal. Die Erzeuger-Verbraucher-Muster kann hocheffiziente Datenkommunikation, ohne sich auf Semaphore, Mutexe, oder Monitore für die Datenübertragung zur Verfügung. Verwendung dieser Grundelemente können Performance-Probleme geben, wie sie teuer zu implementieren sind. Kanälen und FIFOs sind beliebt, nur weil sie die Notwendigkeit vermeiden für die Ende-zu-Ende-Atom Synchronisation. Ein einfaches Beispiel C codiert ist unten gezeigt. Beachten Sie, dass:

  • Atomaren Lesen-Modifizieren-Schreib-Zugriff auf gemeinsam genutzten Variablen vermieden wird: jede der beiden Variablen nur durch einen einzigen Thread aktualisiert. Diese Variablen sind nur dann inkrementiert. Dies bleibt richtig, wenn ihr Wert wickelt-around auf Integer-Überlauf.
  • Dieses kompakte Beispiel sollten für eine tatsächliche Umsetzung durch Zugabe einer Speicher Barriere zwischen der Linie, die die Pufferzugriffe und der Linie, die die Variable aktualisiert verfeinert werden.
  • Dieses Beispiel nicht einem Gewinde in den Schlaf, die je nach Systemkontext in Ordnung sein könnte. Das gibt es nur verhalten nett und konnte entfernt werden. Thread-Bibliotheken benötigen in der Regel Semaphore oder Zustandsgrößen, um den Sleep / Wake-up der Threads steuern. In einem Multi-Prozessor-Umgebung würde Gewinde Schlaf- / Weck viel seltener als die Weitergabe der Daten-Token auftritt, so vermeidet atomare Operationen auf Datenübergang ist vorteilhaft.
  • In diesem Beispiel wird nicht für mehrere Hersteller und / oder Verbrauchern zu arbeiten, weil es eine Race Condition bei der Kontrolle des Staates. Zum Beispiel, wenn nur ein Token im Speicherpuffer und zwei Verbraucher den Puffer nicht leer zu finden, dann würden beide die selbe Token verbrauchen und möglicherweise die Anzahl der verbrauchten Token über produziert Zähler erhöhen.
  • Dieses Beispiel, wie geschrieben, setzt voraus, dass durch teilbar; wenn es nicht teilbar ist, produziert die falsche Pufferindex nach Wraps Vergangenheit zurück auf Null. Eine alternative Lösung ohne diese Einschränkung verwendet zwei zusätzliche Variablen, um die aktuellen Pufferindex für den Kopf und Schwanz verfolgen. Diese Variablen werden anstelle von verwendet wird, und jeder von ihnen zur gleichen Zeit wie die jeweilige Variable erhöht inkrementiert werden, wie folgt :.
  Like 0   Dislike 0
Vorherige Artikel Panzer II
Bemerkungen (0)
Keine Kommentare

Fügen Sie einen Kommentar

smile smile smile smile smile smile smile smile
smile smile smile smile smile smile smile smile
smile smile smile smile smile smile smile smile
smile smile smile smile
Zeichen übrig: 3000
captcha