Skip to content

Readme.md

Latest commit

 

History

History
125 lines (78 loc) · 4.17 KB

Readme.md

File metadata and controls

125 lines (78 loc) · 4.17 KB

Das Erzeuger-Verbraucher Problem
(Producer Consumer Pattern)

Zurück

Inhalt

Verwendete Werkzeuge

Klassen:

  • Klassen std::mutex

  • Klassen std::counting_semaphore

  • Klassen std::lock_guard

  • Klassen std::condition_variable

  • Klassen std::unique_lock

Quellcode

Erzeuger-Verbraucher-Problem mit Bedingungsvariablen.
Erzeuger-Verbraucher-Problem mit Semaphoren.

Allgemeines

Das Erzeuger-Verbraucher Problem entsteht, wenn ein Erzeuger Daten produziert und diese irgendwo ablegen muss, bis ein Verbraucher in der Lage ist, diese zu verarbeiten. Sind keine Daten vorhanden, kann ein Verbraucher nicht arbeiten.

Das Nadelöhr zwischen dem Erzeuger und dem Verbraucher ist ein Puffer. Dieser stellt das Bindeglied zwischen Erzeuger und Verbraucher dar.

Die Länge eines solchen Puffers kann bei seiner Erzeugung möglicherweise variabel eingestellt werden, letzten Endes haben wir aber immer die Situation vorliegen, dass ein solcher Puffer eine begrenzte, maximale Länge besitzt:

Abbildung 1: Das Erzeuger-Verbraucher Problem

  • Der Erzeuger speichert Informationen in einem längenmäßig begrenzten Puffer.
  • Der Verbraucher liest Informationen aus diesem Puffer.

In der Realisierung steht man nun vor zwei Problemen:

  • Der Puffer ist leer: Wenn der Puffer leer ist, muss der Verbraucher warten, bis der Erzeuger ein Element im Puffer abgelegt hat. Erst dann kann der Verbraucher weiter arbeiten.

  • Der Puffer ist voll: Wenn der Puffer voll ist, muss der Erzeuger warten, bis der Verbraucher ein Element aus dem Puffer abgeholt hat. Erst dann kann der Erzeuger weiter arbeiten.

Da im Regelfall der Erzeuger und der Verbraucher im Kontext unterschiedlicher Threads arbeiten, benötigen wir zusätzlich die Werkzeuge der nebenläufigen Programmierung. Desweiteren sollte noch erwähnt werden, dass es sowohl mehrere Erzeuger als auch mehrere Verbraucher geben kann – die aber alle gleichzeitig auf einem Puffer operieren.

Lösungsansätze

Für das Erzeuger-Verbraucher Problem gibt es vor diesem Hintergrund betrachtet mehrere Lösungsansätze:

  • Mit Bedingungsvariablen (std::condition_variable)
  • Mit Semaphoren (std::counting_semaphore)

In jedem Fall wollen wir vermeiden, dass wir für das Überprüfen eines Pufferzustands (leer, voll) zuviel Rechenzeit verwenden. Wir differenzieren hier zwischen zwei Ansätzen:

  • Aktives Warten (Busy Waiting):
    Diese Variante des Wartens kann man im Regelfall in Wiederholungsschleifen beobachten. Eine solche Schleife wird solange ausgeführt, bis eine Variable einen bestimmten Wert angenommen hat. Dies hat zur Folge, dass ein Thread aktiv sein muss und die CPU solange belegt, bis die betrachtete Variable ihren Wert geändert hat.

  • Passives Warten (Idle Waiting):
    In dieser Variante wird ein Thread blockiert (suspendiert) und wartet auf ein Ereignis, das ihn wieder in den Zustand „bereit” versetzt. Der blockierte Thread besitzt keine CPU-Rechenzeit. Ein anderer Thread muss das Auslösen eines Ereignisses bewirken. Beim Eintreten des Ereignisses wird der blockierte Thread geweckt. Zur Umsetzung dieses Ansatzes benötigt man Hilfsmittel des unterlagerten Betriebssystems, rein mit den Mitteln gängiger Programmiersprache lässt sich passives Warten nicht realisieren.

Im Quellcode zu diesem Abschnitt finden Sie zwei Realisierungen des Problems vor:

  1. Umsetzung mit Bedingungsvariablen (wait / notify).

  2. Umsetzung mit Semaphoren (acquire / release).

Literaturhinweise

Die Realisierung des Erzeuger-Verbraucher-Problems mit Semaphoren lehnt sich an den Artikel

Blocking queue

aus dem C++ Blog von Martin Vorbrodt an.

Dieser Artikel demonstriert unter anderem, wie der Puffer über die Technik des Placement new verwaltet werden kann.

Zurück