Gegenseitiger Ausschluss

Der Begriff Wechselseitiger Ausschluss bzw. Mutex (Abk. für engl. mutual exclusion, auf deutsch etwa wechselseitiger Ausschluss) 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/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/Datenstrukturen, so z. B. auch für Client/Server-Systeme mit unabhängigen Client-Prozessen/-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 in der Regel identisch mit einem binären Semaphor.

• Semaphor(e) in der Informatik ist eine Datenstruktur zur Steuerung eines ausschließenden Zugriffs auf Daten, mit oder ohne Verbindung zu einem Task-Scheduler. Die allgemeine Bedeutung von Semaphor ist Signalmast (Formsignal bei der Eisenbahn).
• Monitor ist ein Mechanismus zur Steuerung eines ausschließenden Zugriffs auf Daten in Verbindung mit dem Scheduler eines Echtzeitbetriebssystems 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 Sperre des Zugriffs von anderer Seite während einer laufenden Bearbeitung, beispielsweise File-Locking beim Schreiben in eine Datei oder das Locken 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 ein Lock noch vorliegt 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 muss dabei nicht (und sollte nicht!) hochzyklisch erfolgen. Sinnvoll ist die Kombination des aktiven Wartens mit einer Thread-Abgabe an eine Schedulersteuerung jeweils für eine definierte Zeit mit einem „sleep“ Aufruf.
• 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 insofern synchronisiert werden, dass sie nicht gleichzeitig zugreifen. Eine allgemeingültige 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 dazu 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, wenn ein anderer Thread sich gerade 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 Nichtkonsistenz führen kann,
• ein anderer Prozess während der Bearbeitung die zwischenzeitlich nichtkonsistenten 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. Ist ein RTOS vorhanden, dann wird die Freigabe von dessen Scheduler unterstützt. Es wird getestet, ob andere Threads auf dieses Semaphor warten, diese Threads werden auf 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 incrementW()
{ int a = w;
  a = a + 1;
  w = a;
}

Hier ist die gesamte Methode als kritischer Abschnitt gekennzeichnet. incrementW soll eine Methode der Klasse sein, die w enthält. An der Programmstelle, an der incrementW gerufen wird, braucht man nichts weiter 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

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

Im ersten Fall kann der andere Prozess passiv warten. Die Kontrolle über den 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. Das ist allgemein der Fall bei mehreren Threads eines Prozesses, aber auch bei mehreren Prozessen unter einem gemeinsamen Betriebssystem-Kernel.

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 hochpriorer 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 oder das warten auf eine Eventfreigabe von Betriebssystem (z. B. in Windows-Systemen: WaitForSingleObject(...)) ein zielführender Weg. Letzterer wartet keine festgelegte Anzahl von Millisekunden (und verschwendet dadurch Zeit durch unnötige Abfragen und evtl. zu langes Warten), sondern weist das System an, den Thread einzufrieren bis das Object wieder frei (=gesetzt) ist. Daher kann hier berechtigterweise von Realisierbarkeit im User-Space (in der Anwenderprogrammierung) gesprochen werden.

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, 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 Performance 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 gegebenenfalls 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 einen 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++ hat man die Möglichkeit, über Makros oder Compilerschalter diese Codeteile in der Quelle zu haben ohne dass sie beim Compilieren der End-Anwendung zu Laufzeiteffektivitäsverlusten führen:

 EnterCriticalSection(semphore)
 {
   myValues->x = 5;
   TEST_Threadswitch(25);
   ...
 }

Das Makro TEST_Threadswitch() kann im Produktivcode 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 drin 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 drin bleiben. Damit kann man immer wieder die Tests wiederholen wenn nötig.

Codereview

Mit einem Coderview kann systematisch geprüft werden, ob alle Datenzugriffe auf eine bestimmte Instanz oder eine Klasse / ein Strukturtyp mit einem Mutex versehen ist. 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 zu tage. Dabei können Tools helfen.

In C oder C++ ist so etwas mit Zusatztools wie lint zu haben. In moderneren Programmiersprachen wie Java sind oder werden Eigenschaften der Codeanalyse schon eher Sprachbestandteile. In Java kann man ein synchronized um einen Datenzugriff vergessen. Eine Methode, die als synchronized deklariert ist, ist aber automatisch bezüglich der eigenen Klasse threadsicher: Alle Zugriffe auf Daten der eigenen Instanz erfolgen unter Mutex. Jedoch ist dies kein Allheilmittel, da synchronized-Methoden gegebenenfalls zuviel blocken. Möglicherweise muss nicht die gesamte Methode unter Mutex ablaufen.

Codereview muss mit Kenntnis verbunden sein. Man kann beispielsweise in Java eine Referenz als

 AtomicReference<MyType> ref;

deklarieren. Damit kann man nur mit Atomic, sprich Mutex-Zugriffen darauf arbeiten. Aber möglicherweise wird das verwechselt: Ein Anwender meint, damit sei auch bereits der Zugriff auf die Daten selbst atomic also mutexgeschützt. Man ist hier gegebenenfalls von Scriptsprachen, die sich um viele Dinge automatisch kümmern, verwöhnt. In der Hard-Core-Programmierung hat man die Dinge aber selbst in der Hand, also auch in der Verantwortung. Auch ein lint liefert nicht automatisch fertige Aussagen, sondern muss dem Anwendungszweck gemäß konfiguriert werden. Auch hier gilt nicht der Spruch … – nicht wissen macht nichts, und blindes Vertrauen in Tools kann teuer werden.

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/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.

Des Weiteren 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

Siehe auch

• nichtsequentielle Programmierung
• Transaktionssystem