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 (englisch Semaphore telegraph).
- 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 zu 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
sind bei Multithreadanwendungen genauso zutreffend wie bei einfacheren Applikationen. Aber es sind einige Besonderheiten zu beachten:
Praxistest
Fehler wegen Multithreading treten möglicherweise unter normalen Betriebsbedingungen überhaupt nicht auf. Eine Aussage Test fehlerfrei, also Software fehlerfrei ist nicht schlüssig. Fehler treten möglicherweise dann auf, wenn Bedingungen geändert werden, die scheinbar mit dem betreffenden Programmteil nichts zu tun haben. Die Ursache sind Timingverschiebungen, Veränderung in Nutzung von Ressourcen oder dergleichen. Dann erst wird der vorhandene Fehler stimuliert. Man muss einen Praxistest also unter sehr vielen wechselnden Betriebsbedingungen vornehmen, um eine verlässliche Testaussage zu bekommen.
Modultest
Der klassische Modultest soll die Richtigkeit eines Algorithmus prüfen. Das ist typischerweise eine Single-Thread-Angelegenheit. Man kann aber in einem Modultest zielgerichtet Multithread-Test-Bedingungen einbauen, in dem durch Zusatzbefehle an bekannten kritischen Stellen ein Threadwechsel erzwungen wird. Der andere Thread ist dann beispielsweise derart zu programmieren, dass zielgerichtet auf dasselbe Betriebsmittel zugegriffen wird. Damit ist im Modultest testbar, ob der programmierte Mutexalgorithmus greift.
In C oder C++ kann man über Makros oder Compilerschalter diese Codeteile im Quelltext belassen, ohne dass sie beim Kompilieren der End-Anwendung zu Laufzeiteffektivitätsverlusten führen:
EnterCriticalSection(semaphore)
{
myValues->x = 5;
TEST_Threadswitch(25);
...
}
Das Makro
TEST_Threadswitch()
kann im Produktionscode leer definiert werden. Für Tests kann es beliebige Befehle enthalten.
In anderen Programmiersprachen wie Java, in denen es die Makro-Möglichkeit nicht gibt, kann man über Aufruf von Interface-Methoden solche Threadwechselstimuli in einer Testumgebung implementieren, Im Praxiseinsatz sind dann diese Interfacemethoden mit leeren Implementierungen ersetzbar oder wie im Beispiel der Zeiger null:
synchronized(myValues)
{
if(testThreadswitch != null){ testThreadswitch.doit(25); }
...
}
Der Test-Code soll gegebenenfalls nicht in der Produktivsoftware bleiben. Das ist ähnlich zu bewerten wie das Belassen von Testadapter-Steckern auf Hardwarebaugruppen: Es kommt auf die Stückzahl an. Bei hoher Stückzahl kann und muss man sich einen ausgiebigen Typtest leisten, so dass das Endprodukt ohne Testadaptionen gefertigt werden kann. Ist die Stückzahl jedoch niedriger und Umarbeitungen nicht ausgeschlossen, dann sollten Testanweisungen darin bleiben. Damit kann man immer wieder die Tests wiederholen wenn nötig.
Codereview
Mit einem Codereview kann systematisch geprüft werden, ob alle Datenzugriffe auf eine bestimmte Instanz oder eine Klasse bzw. einen Strukturtyp mit einem Mutex versehen sind. Womöglich ist dieser an einer Stelle vergessen worden. Das fällt beim Modultest deshalb nicht auf, weil es eben überhaupt nicht betrachtet wurde. Beim Praxistest tritt der kritische Fall zunächst nicht auf, weil es eine eher versteckte Bedingung ist. Das systematische Durchforsten aller Zugriffe auf die betreffenden Daten bringt aber das Problem zutage. Dabei können bestimmte Hilfsprogramme helfen.
In C oder C++ ist so etwas mit Zusatzprogrammen wie lint zu erreichen. In moderneren Programmiersprachen wie Java sind oder werden Eigenschaften der Codeanalyse schon eher Sprachbestandteile. In Java kann man ein synchronized-Schlüsselwort um einen Datenzugriff vergessen. Eine Methode, die als synchronized deklariert ist, ist aber automatisch bezüglich der eigenen Klasse Thread-sicher: Alle Zugriffe auf Daten der eigenen Instanz erfolgen unter einem Mutex. Jedoch ist dies kein Allheilmittel, da synchronized-Methoden gegebenenfalls zu viel blockieren. Möglicherweise braucht nicht die gesamte Methode unter einem Mutex abzulaufen.
Probleme im Zusammenhang mit Mutex
Der gegenseitige Ausschluss birgt die Gefahr von Verklemmungen (Deadlocks), bei denen keiner der Prozesse mehr fortfahren kann, weil jeweils ein Prozess den anderen blockiert. Ein anschauliches Beispiel dafür ist das Philosophenproblem. Solche Verklemmungen können durch eine geeignete Planung des Programmablaufs vermieden werden, zum Beispiel nach dem Peterson-Algorithmus oder dem Dekker-Algorithmus.
Ein weiteres Problem ist die meist nicht einheitliche Implementierung oder Definition des Verhaltens bei mehrfachem (rekursivem) Aufruf eines Mutex-Locks aus einem Thread. Bei einigen Systemen wird hier ein Zähler benutzt, um dieses Verhalten zu handhaben. Andere Systeme blockieren den Thread (ähnlich wie eine Semaphore), geben eine Fehlermeldung zurück oder sind im Verhalten einstellbar.
Außerdem existiert auch noch die Problematik, dass bei mindestens drei Threads mit unterschiedlichen Prioritäten der Thread mit mittlerer Priorität den mit höchster Priorität blockieren kann, wenn der Thread mit der niedrigsten Priorität gerade Zugriff auf eine Ressource hat. Diese Problematik nennt man Prioritätsinversion.
Literatur
- Rainer Oechsle: Parallele Programmierung mit Java Threads. 1. Auflage. Fachbuchverlag Leipzig, 2001, ISBN 978-3-446-21780-5, S. 176.
- Andrew S. Tanenbaum: Moderne Betriebssysteme (= Pearson Studium - IT). 3. aktualisierte Auflage. Addison-Wesley, 2009, ISBN 978-3-8273-7342-7, S. 1248 (englisch: Modern Operating Systems.).
- James H. Anderson, Yong-Jik Kim, Ted Herman: Shared-memory mutual exclusion: major research trends since 1986. In: Distrib. Comput. Band 16, Nr. 2-3. Springer-Verlag, September 2003, ISSN 0178-2770, S. 75–110, doi:10.1007/s00446-003-0088-6.
- M. Raynal, D. Beeson: Algorithms for mutual exclusion. MIT Press, Cambridge MA 1986, ISBN 0-262-18119-3.
