Mutex
aus Wikipedia, der freien Enzyklopädie
Mutex (Abk. für engl. Mutual Exclusion, „wechselseitiger Ausschluss“) bezeichnet Verfahren, mit denen verhindert wird, dass nebenläufige Prozesse bzw. Threads gleichzeitig auf Daten zugreifen und so unter Umständen inkonsistente Zustände herbeiführen. Dieses Konzept ist von zentraler Bedeutung sowohl für Systeme, deren Software in Threads abläuft, als auch für konkurrierend ablaufende Prozesse im Allgemeinen, beispielsweise quasigleichzeitige Zugriffe auf ein Datenbanksystem aus mehreren unabhängigen Clients.
Inhaltsverzeichnis |
[Bearbeiten] Begriffe im Zusammenhang mit Mutex
- Semaphor 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) ist derjenige Teil im Maschinencode, 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 die selben ü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.
- 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 RTOS-Scheduler.
- Aktives Warten (engl. busy-waiting) ist eine fortwährende Polling-Abfrage auf eine Mutex-Freigabe. Die Polling-Abfrage muss dabei nicht (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 wait(millisec)-Aufruf.
- Spinlock ist die Kombination von Lock mit Polling-Abfrage.
- 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.
- RTOS ist der Sammelbegriff für Echtzeit-Multitask-Betriebssysteme. Der Scheduler eines RTOS hilft, Mutex technisch zu beherrschen.
[Bearbeiten] Mechanismen zur Realisierung eines Mutex
[Bearbeiten] 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.
[Bearbeiten] 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.
[Bearbeiten] Aktives und passives Warten
Ist ein Mutex ausgesprochen, dann darf ein anderer Prozess oder Thread nicht zugreifen. Die Frage ist: Was führt der andere Prozess / Thread stattdessen aus: Es gibt grundsätzlich zwei Möglichkeiten:
- Der andere Thread hat nichts weiter auszuführen als den Zugriff, der unter Mutex steht.
- Der andere Thread hat noch andere Aufgaben.
Im ersten Fall kann der andere Prozess passiv warten. Die Kontrolle über den Thread kann an einen Scheduler eines Echtzeitbetriebssystems 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 anderem Thread übergeben, die dieser unter 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 Polling 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. Dieser wait() setzt zwar eine (einfache) Form eines Echtzeitbetriebssystems voraus, aber keine Verbindung zu dem Mutex-Steuermechanismus. Daher kann hier berechtigterweise von Realisierbarkeit im User-Space (in der Anwenderprogrammierung) gesprochen werden.
[Bearbeiten] Unterstützung von Mutex seitens Programmiersprachen und Betriebssystemen
Einige Programmiersprachen unterstützen Mutex als Teil der Sprache selbst, insbesondere Pascal, Ada und Java. 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.
[Bearbeiten] 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.
