Mutex

Der Begriff wechselseitiger Ausschluss bzw. Mutex (Abk. für englisch mutual exclusion) bezeichnet eine Gruppe von Verfahren, mit denen das Problem des kritischen Abschnitts gelöst wird. Mutex-Verfahren verhindern, dass nebenläufige Prozesse bzw. Threads gleichzeitig oder zeitlich verschränkt gemeinsam genutzte Datenstrukturen unkoordiniert verändern, wodurch die Datenstrukturen in einen inkonsistenten Zustand geraten können, auch wenn die Aktionen jedes einzelnen Prozesses oder Threads für sich betrachtet konsistenzerhaltend sind. Mutex-Verfahren koordinieren den zeitlichen Ablauf nebenläufiger Prozesse/Threads derart, dass andere Prozesse/Threads von der Ausführung kritischer Abschnitte ausgeschlossen sind, wenn sich bereits ein Prozess/Thread im kritischen Abschnitt befindet (die Datenstruktur verändert).

Mutex-Verfahren sind der Klasse der Verfahren zur Prozess- oder Thread-Synchronisation zugeordnet und sind von zentraler Bedeutung für jegliche Systeme nebenläufig ablaufender Prozesse/Threads mit modifizierendem Zugriff auf gemeinsam genutzte Daten oder Datenstrukturen, so z. B. auch für Client/Server-Systeme mit unabhängigen Client-Prozessen oder -Threads, die gleichzeitig bzw. zeitlich verschränkt auf einen Datenbank-Server zugreifen.

Abgrenzung Der Begriff des Mutex ist nicht einheitlich definiert. Oft wird er in der Theoretischen Informatik auch anders verwendet als in konkreten Programmiersprachen. Dieser Abschnitt versucht, die üblichste Definition der Begriffe wiederzugeben. Mutex: Das Verfahren zum Sicherstellen des gegenseitigen Ausschlusses (siehe Artikeleinleitung). Ein Objekt (bzw. eine Datenstruktur), das gegenseitigen Ausschluss erzwingt. Die meisten Programmiersprachen, die nebenläufige Prozesse unterstützen, kennen ein solches. Es ist keineswegs identisch mit einem binären Semaphor, da Semaphore von anderen Aktivitätsträgern freigegeben werden dürfen.

Semaphor ist eine Datenstruktur zur Steuerung eines ausschließenden Zugriffs auf Daten, mit oder ohne Verbindung zu einem Task-Scheduler. Die allgemeine Bedeutung von Semaphor geht zurück auf die Optische Telegrafie mit Signalmasten (). Monitor ist ein Mechanismus zur Steuerung eines ausschließenden Zugriffs auf Daten in Verbindung mit der Rechenzeitverteilung (scheduler) eines Echtzeitbetriebssystems (RTOS) oder einer Sprache, die Multithread-Verarbeitungen unterstützt, wie z. B. in Java. Konzeptionell sind die Semaphor- und Monitor-Technik verwandt. Lock-Mechanismen dienen der Zugriffssperre von anderer Seite während einer laufenden Bearbeitung, beispielsweise Dateisperren (file locks) beim Schreiben in eine Datei oder das Sperren einer bestimmten Revision in einem Versionsverwaltungssystem. Ein kritischer Abschnitt (engl. critical section oder critical region) ist derjenige Teil im ausführbaren Code, in dem ein wegen des Mutex ungestörter Zugriff auf Daten erfolgt. Ein kritischer Abschnitt darf nicht unterbrochen werden von einem anderen Thread, der auf dieselben über Mutex geschützten Daten zugreifen will, von einem anderen Thread, der den Mutex-Zugriff möglicherweise unzulässig verlängern würde, da er den zugreifenden Thread längere Zeit unterbricht.

Begriffsdefinitionen Polling ist in der Informatik ein Mechanismus zum fortwährenden Abfragen, beispielsweise ob eine Sperre (lock) noch aktiv ist oder ob ein Semaphor frei ist. Polling ist eine Alternative zur Steuerung über einen Scheduler. Aktives Warten (engl. busy-waiting) ist ein fortwährendes Polling auf eine Mutex-Freigabe. Das Polling braucht dabei nicht (und sollte nicht!) unnötig häufig erfolgen. Sinnvoll ist die Kombination des aktiven Wartens mit einer Thread-Abgabe an eine Scheduler-Steuerung jeweils für eine definierte Zeit mit einem „sleep“-Aufruf (zur Abgabe von Rechenzeit bzw. zum Stromsparen). Spinlock ist die Kombination von Lock mit Polling. Prozesssynchronisation ist der allgemeine Begriff für die Koordinierung des zeitlichen Ablaufes mehrerer nebenläufiger Prozesse bzw. Threads. Dabei ist es unerheblich, ob es sich um Threads in einem Programm, um Programme auf einem Computer oder um Prozesse in einem Verteilten System handelt. In Bezug auf Mutex müssen die Prozesse nur für den jeweils kurzen Zeitraum des Mutex-Zugriffes und nur dahingehend synchronisiert werden, dass sie nicht gleichzeitig zugreifen. Eine allgemeine Prozesssynchronisation ist damit nicht verbunden. Interprozesskommunikation ist der Sammelbegriff für Methoden zum Datenaustausch zwischen Prozessen und zum Erreichen einer Prozesssynchronisation. Ein Mutex selbst ist nicht Mittel der Interprozesskommunikation, sondern der Datenaustausch, der gegebenenfalls über einen Mutex geschützt ist, kann ein solches Mittel sein.

Mechanismen zur Realisierung eines Mutex

Semaphor oder Monitor

Um den gegenseitigen Ausschluss zu erreichen, wird dem Datenobjekt ein Kontrollelement zugeordnet, das von einem Prozess (bzw. einem Thread) immer dann beachtet werden muss, wenn er einen Programmcode ausführt, der auf dieses Datenobjekt zugreift (so genannte kritische Abschnitte). Der Effekt ist, dass der Prozess warten muss, wenn gerade ein anderer auf diese Daten zugreift. Es muss verhindert werden, dass

die Bearbeitung beginnt, sobald ein anderer Thread sich in einer Bearbeitung oder auch nur in einem konsistenten Lesen der Daten befindet, die Bearbeitung unterbrochen wird und ein anderer Thread konkurrierende Bearbeitungen vornimmt, die zu einer Inkonsistenz führen können sowie ein anderer Prozess während der Bearbeitung die zwischenzeitlich inkonsistenten Daten verwendet.

Über ein Semaphor wird angezeigt, dass der Thread mit der Bearbeitung beginnt. Zuvor wird getestet, ob das Semaphor nicht von einem anderen Thread besetzt ist. In diesem Fall muss der Thread warten. Er kann entweder mit zyklischem Polling das Semaphor abfragen, bis es frei ist, oder der Thread hinterlegt am Semaphor in dessen Warteschlange seine eigene Thread-Identifizierung und geht in den Wartezustand.

Ist das Semaphor frei, wird es belegt. Andere Threads, die nun zugreifen wollen, werden wie oben beschrieben daran gehindert. Die Bearbeitung der Daten muss in einem begrenzten Zeitraum vollzogen werden, damit es im gesamten System nicht zu einer Verklemmung kommt.

Nach Beenden der Datenbearbeitung muss das Semaphor wieder freigegeben werden. In einem Echtzeitbetriebssystem wird die Freigabe von dessen Scheduler unterstützt. Es wird getestet, ob andere Threads auf dieses Semaphor warten, diese Threads werden auf „bereit“ (engl. readyToRun) gesetzt und entsprechend ihrer Priorität abgearbeitet.

In der Programmiersprache Java gibt es für dieses Problem eine Standardlösung, die fester Bestandteil der Programmiersprache ist. Das wird im folgenden Beispiel gezeigt:

synchronized(obj) { int a = obj.w; a = a + 1; obj.w = a;

In dem zu synchronized gehörenden Programmblock in {} ist die Bearbeitung der Daten notiert. Das ist ein kritischer Abschnitt. Die Verhinderung des konkurrierenden Zugriffes erfolgt mittels des Objektes obj, das auch die betreffenden Daten (hier die Variable w) enthält. Jeder andere Thread, der ebenfalls synchronized(obj) aufruft, muss bis zur Beendigung dieses Programmabschnittes warten. Am Objekt obj, genauer an dessen Basisklasse, die in Java Object heißt, hängt eine Semaphore mit Anschluss an den Scheduler der Java Virtual Machine, die wiederum entsprechend ihrer konkreten Implementierung am Scheduler des RTOS hängt. In der Java-Original-Dokumentation wird bezüglich dieses Konzeptes der Begriff Monitor benutzt.

Eine andere Variante in Java ist die Kennzeichnung einer Methode als synchronized:

synchronized void increment(int w) { int a = w; a = a + 1; w = a;

Hier ist die gesamte Methode als kritischer Abschnitt gekennzeichnet. increment(w) soll eine Methode der Klasse sein, die den Parameter w entgegennimmt. An der Programmstelle, an der increment(w) aufgerufen wird, braucht man nichts weiter zu tun.

Lock

Ein Lock-Mechanismus ist ähnlich dem Monitor- oder Semaphoren-Mechanismus, aber insbesondere auf den Zugriff mehrerer Prozesse in verteilten Systemen abgestimmt. Das Konzept lässt sich mittels Read-Write-Locks so verfeinern, dass sich Prozesse, die nur Daten lesen, gegenseitig nicht behindern – das ist besonders für den Zugriff auf Dateien und Datenbanken verbreitet.

Aktives und passives Warten Ist ein Mutex ausgesprochen, dann darf ein anderer Prozess oder Thread nicht zugreifen. Der andere Prozess/Thread kann dann

nichts weiter ausführen, als auf den Zugriff zu warten, der unter Mutex steht, oder andere Aufgaben ausführen und auf den Zugriff warten oder den Zugriff verwerfen.

Im ersten Fall kann der andere Thread passiv warten. Die Kontrolle über den wartenden Thread kann an einen Scheduler abgegeben werden, der Thread wird erst dann wieder fortgesetzt, wenn der Mutex frei ist. Das setzt aber voraus, dass auch derjenige Thread, der den Mutex belegt, im selben Scheduler eingebunden ist, sowie, dass der Scheduler den Mutex und dessen Freigabe erkennt. Das ist meist der Fall bei mehreren Threads eines Prozesses, kann aber auch bei mehreren Prozessen unter einem gemeinsamen Betriebssystem-Kernel umgesetzt sein.

Im zweiten Fall kann es sein, dass der andere Thread keinesfalls passiv warten darf, da die anderen Aufgaben sonst nicht ausgeführt werden. Beispiel: Ein hochpriorisierter Thread hat eine Regelung zyklisch auszuführen. Zusätzlich muss er Messwerte einem anderen Thread übergeben, die dieser unter dem Schutz eines Mutex (wegen Datenkonsistenz) ausliest. Wenn der auslesende Thread den Mutex ausspricht, dann darf der Regelungs-Thread zwar die Werte nicht ablegen, muss aber seine Regelungs-Aufgaben ausführen. Folglich muss er im jeweils folgenden Zyklus den Mutex abfragen und die Werte später ablegen. Der zweite Fall führt immer zu einer zyklischen Abfrage (Polling).

Auch im ersten Fall kann ein Polling notwendig sein, und zwar genau dann, wenn die beiden Prozesse keine Verbindung über einen gemeinsamen Scheduler haben. Im Falle eines Locks führt das zur notwendigen Verwendung des Spinlock. Allgemein wird von aktivem Warten (busy waiting) gesprochen, was eine Form des Pollings ist. Beim aktiven Warten ist eine hochzyklische Abfrage des Mutex-Steuerelements zu vermeiden. In der Regel ist ein wait(millisekunden)-Aufruf ein zielführender Weg.

Der dritte Fall, das Verwerfen des Zugriffs, wird i. d. R. dann angewendet, wenn ein späterer Wert den ursprünglichen Eintrag überschreiben würde – in der Kenntnis dieses zukünftigen Zustandes kann dann sofort der aktuell nicht schreibbare Wert verworfen werden.

Unterstützung von Mutex seitens Programmiersprachen und Betriebssystemen

Einige Programmiersprachen unterstützen Mutex als Teil der Sprache selbst, insbesondere Concurrent Pascal, Ada, Java oder C#. Für fast alle Sprachen gibt es Bibliotheken, die ein Mutex-System implementieren (z. B. pthreads in C), häufig ist dies sogar Teil der Standard-API bzw. der Laufzeitumgebung.

Eine gute Implementierung von Mutex ist nur mit einem Betriebssystem möglich, dessen Scheduler solche Konzepte unterstützt. Auf anderen Systemen (insbesondere Echtzeitsystemen) muss auf Spinlocks zurückgegriffen werden, die die Systemleistung durch Busy Waiting erheblich beeinträchtigen.

Grundsätzlich reicht es aus, wenn ein Betriebssystem oder eine Laufzeitumgebung ein Subset aus Mutex, Semaphor, Monitor, Lock oder Critical Section anbietet. Jedes dieser Prinzipien kann durch ein beliebiges anderes aus der Gruppe modelliert werden.

Testen in Anwendungen mit Mutex-Codeteilen (in Multithread-Anwendungen)

Die drei klassischen Testmöglichkeiten von Software

Modultest: Test eines Algorithmus mit definierten Eingangsbedingungen, oft als Einzelschritt-Test von Anweisungen, um möglichst alle Anwendungsfälle zu erfassen, Codereview: Überprüfung der Software nach formellen Kriterien und mit kritischem Blick, Praxistest: Test der Software unter realen Bedingungen