Monitor (Synchronisation) – Wikipedia

Posted on December 31, 2020 by lordneo

before-content-x4

Bei der gleichzeitigen Programmierung (auch als parallele Programmierung bezeichnet) a Monitor ist ein Synchronisationskonstrukt, das es Threads ermöglicht, sich gegenseitig auszuschließen und zu warten (zu blockieren), bis eine bestimmte Bedingung falsch wird. Monitore haben auch einen Mechanismus, um anderen Threads zu signalisieren, dass ihre Bedingung erfüllt wurde. Ein Monitor besteht aus einem Mutex (Lock) -Objekt und Bedingungsvariablen. EIN Bedingungsvariable Im Wesentlichen handelt es sich um einen Container mit Threads, die auf eine bestimmte Bedingung warten. Monitore bieten einen Mechanismus für Threads, um den exklusiven Zugriff vorübergehend aufzugeben, um zu warten, bis eine bestimmte Bedingung erfüllt ist, bevor sie den exklusiven Zugriff wiedererlangen und ihre Aufgabe wieder aufnehmen.

Eine andere Definition von Monitor ist ein fadensicher Klasse, Objekt oder Modul, das einen Mutex umschließt, um mehr als einem Thread den sicheren Zugriff auf eine Methode oder Variable zu ermöglichen. Das definierende Merkmal eines Monitors ist, dass seine Methoden unter gegenseitigem Ausschluss ausgeführt werden: Zu jedem Zeitpunkt kann höchstens ein Thread eine seiner Methoden ausführen. Durch die Verwendung einer oder mehrerer Bedingungsvariablen können Threads auch auf eine bestimmte Bedingung warten (wobei die obige Definition von a verwendet wird) “Monitor”). Für den Rest dieses Artikels ist dieser Sinn von “Monitor” wird als bezeichnet “Thread-sicheres Objekt / Klasse / Modul”.

Monitore wurden von Per Brinch Hansen erfunden^[1] und CAR Hoare,^[2] und wurden zuerst in Brinch Hansens Concurrent Pascal-Sprache implementiert.^[3]

Gegenseitiger Ausschluss[edit]

Betrachten Sie als einfaches Beispiel ein threadsicheres Objekt zum Ausführen von Transaktionen auf einem Bankkonto:

monitor class Account {
    private int balance := 0
    invariant balance >= 0

    public method boolean withdraw(int amount)
        precondition amount >= 0
    {
        if balance < amount {
            return false
        } else {
            balance := balance - amount
            return true
        }
    }

    public method deposit(int amount)
        precondition amount >= 0
    {
        balance := balance + amount
    }
}

Während ein Thread eine Methode eines thread-sicheren Objekts ausführt, wird dies gesagt besetzen das Objekt, indem Sie seinen Mutex (Schloss) halten. Thread-sichere Objekte werden implementiert, um dies zu erzwingen Zu jedem Zeitpunkt darf höchstens ein Thread das Objekt belegen. Die Sperre, die anfänglich entsperrt ist, wird zu Beginn jeder öffentlichen Methode gesperrt und bei jeder Rückkehr von jeder öffentlichen Methode entsperrt.

Beim Aufrufen einer der Methoden muss ein Thread warten, bis kein anderer Thread eine der Methoden des thread-sicheren Objekts ausführt, bevor er mit der Ausführung seiner Methode beginnt. Beachten Sie, dass ohne diesen gegenseitigen Ausschluss im vorliegenden Beispiel zwei Threads dazu führen können, dass Geld ohne Grund verloren geht oder gewonnen wird. Zum Beispiel könnten zwei Threads, die 1000 vom Konto abheben, beide true zurückgeben, während der Kontostand wie folgt nur um 1000 sinkt: Zuerst rufen beide Threads den aktuellen Kontostand ab, finden ihn größer als 1000 und subtrahieren 1000 davon; Dann speichern beide Threads den Saldo und kehren zurück.

Der syntaktische Zucker “Klasse überwachen” Im obigen Beispiel wird die folgende grundlegende Darstellung des Codes implementiert, indem die Ausführung jeder Funktion in Mutexe eingeschlossen wird:

class Account {
    private lock myLock

    private int balance := 0
    invariant balance >= 0

    public method boolean withdraw(int amount)
       precondition amount >= 0
    {
        myLock.acquire()
        try {
            if balance < amount {
                return false
            } else {
                balance := balance - amount
                return true
            }
        } finally {
            myLock.release()
        }
    }

    public method deposit(int amount)
       precondition amount >= 0
    {
        myLock.acquire()
        try {
            balance := balance + amount
        } finally {
            myLock.release()
        }
    }
}

Bedingungsvariablen[edit]

Problemstellung[edit]

Für viele Anwendungen reicht ein gegenseitiger Ausschluss nicht aus. Threads, die eine Operation versuchen, müssen möglicherweise bis zu einem bestimmten Zustand warten P. gilt wahr. Eine geschäftige Warteschleife

while not( P ) do skip

funktioniert nicht, da durch gegenseitigen Ausschluss verhindert wird, dass andere Threads in den Monitor gelangen, um die Bedingung zu erfüllen. Andere “Lösungen” Es gibt beispielsweise eine Schleife, die den Monitor entsperrt, eine bestimmte Zeit wartet, den Monitor sperrt und den Zustand überprüft P.. Theoretisch funktioniert es und wird nicht blockieren, aber es treten Probleme auf. Es ist schwer, eine angemessene Wartezeit zu bestimmen, die zu klein ist, und der Thread belastet die CPU, ist zu groß und reagiert anscheinend nicht mehr. Was benötigt wird, ist eine Möglichkeit, den Thread zu signalisieren, wenn die Bedingung P wahr ist (oder könnten wahr sein).

Fallstudie: Klassisches Problem zwischen Produzenten und Verbrauchern[edit]

Ein klassisches Parallelitätsproblem ist das der gebundener Produzent / Konsument, in dem sich eine Warteschlange oder ein Ringpuffer mit Aufgaben mit maximaler Größe befindet, wobei sich ein oder mehrere Threads befinden “Produzent” Threads, die der Warteschlange Aufgaben hinzufügen, und ein oder mehrere andere Threads “Verbraucher” Threads, die Aufgaben aus der Warteschlange entfernen. Es wird angenommen, dass die Warteschlange selbst nicht threadsicher ist und leer, voll oder zwischen leer und voll sein kann. Immer wenn die Warteschlange voller Aufgaben ist, müssen die Producer-Threads blockiert werden, bis Platz für die Dequeueing-Aufgaben von Consumer-Threads vorhanden ist. Wenn andererseits die Warteschlange leer ist, müssen die Consumer-Threads blockiert werden, bis mehr Aufgaben verfügbar sind, da Producer-Threads sie hinzufügen.

Da es sich bei der Warteschlange um ein gleichzeitiges Objekt handelt, das von Threads gemeinsam genutzt wird, muss der Zugriff darauf atomar erfolgen, da die Warteschlange in ein Objekt gestellt werden kann inkonsistenter Zustand im Verlauf des Warteschlangenzugriffs, der niemals zwischen Threads offengelegt werden sollte. Somit bildet jeder Code, der auf die Warteschlange zugreift, a Kritischer Abschnitt das muss durch gegenseitigen Ausschluss synchronisiert werden. Wenn Code- und Prozessoranweisungen in kritischen Codeabschnitten, die auf die Warteschlange zugreifen, sein könnten verschachtelt durch willkürliche Kontextwechsel Zwischen Threads auf demselben Prozessor oder durch gleichzeitiges Ausführen von Threads auf mehreren Prozessoren besteht die Gefahr, dass ein inkonsistenter Status angezeigt wird und Race-Bedingungen verursacht werden.

Ohne Synchronisation falsch[edit]

Ein naiver Ansatz besteht darin, den Code mit zu entwerfen beschäftigt zu warten und keine Synchronisation, wodurch der Code den Rennbedingungen unterliegt:

global RingBuffer queue; // A thread-unsafe ring-buffer of tasks.

// Method representing each producer thread's behavior:
public method producer() {
    while (true) {
        task myTask = ...; // Producer makes some new task to be added.
        while (queue.isFull()) {} // Busy-wait until the queue is non-full.
        queue.enqueue(myTask); // Add the task to the queue.
    }
}

// Method representing each consumer thread's behavior:
public method consumer() {
    while (true) {
        while (queue.isEmpty()) {} // Busy-wait until the queue is non-empty.
        myTask = queue.dequeue(); // Take a task off of the queue.
        doStuff(myTask); // Go off and do something with the task.
    }
}

Dieser Code hat insofern ein ernstes Problem, als Zugriffe auf die Warteschlange unterbrochen und mit den Zugriffen anderer Threads auf die Warteschlange verschachtelt werden können. Das queue.enqueue und queue.dequeue Methoden haben wahrscheinlich Anweisungen zum Aktualisieren der Mitgliedsvariablen der Warteschlange, wie z. B. Größe, Anfangs- und Endposition, Zuweisung und Zuweisung von Warteschlangenelementen usw. queue.isEmpty () und queue.isFull () Methoden lesen auch diesen gemeinsamen Zustand. Wenn Producer / Consumer-Threads während der Aufrufe zum Enqueue / Dequeue verschachtelt werden dürfen, kann ein inkonsistenter Status der Warteschlange angezeigt werden, was zu Race-Bedingungen führt. Wenn ein Verbraucher die Warteschlange zwischen dem Verlassen und Warten eines anderen Verbrauchers leer macht “aus der Warteschlange”Dann versucht der zweite Verbraucher, sich aus einer leeren Warteschlange zu entfernen, was zu einem Fehler führt. Ebenso, wenn ein Produzent die Warteschlange zwischen dem Verlassen und dem Anrufen eines anderen Produzenten voll macht “Enqueue”Dann versucht der zweite Produzent, eine vollständige Warteschlange hinzuzufügen, was zu einem Fehler führt.

Spin-Warten[edit]

Ein naiver Ansatz, um eine Synchronisation zu erreichen, wie oben erwähnt, ist die Verwendung “Spin-Warten“, in dem ein Mutex zum Schutz der kritischen Codeabschnitte verwendet wird und das Warten auf Besetzt weiterhin verwendet wird, wobei die Sperre zwischen jeder Prüfung auf Besetzt erworben und freigegeben wird.

global RingBuffer queue; // A thread-unsafe ring-buffer of tasks.
global Lock queueLock; // A mutex for the ring-buffer of tasks.

// Method representing each producer thread's behavior:
public method producer() {
    while (true) {
        task myTask = ...; // Producer makes some new task to be added.

        queueLock.acquire(); // Acquire lock for initial busy-wait check.
        while (queue.isFull()) { // Busy-wait until the queue is non-full.
            queueLock.release();
            // Drop the lock temporarily to allow a chance for other threads
            // needing queueLock to run so that a consumer might take a task.
            queueLock.acquire(); // Re-acquire the lock for the next call to "queue.isFull()".
        }

        queue.enqueue(myTask); // Add the task to the queue.
        queueLock.release(); // Drop the queue lock until we need it again to add the next task.
    }
}

// Method representing each consumer thread's behavior:
public method consumer() {
    while (true) {
        queueLock.acquire(); // Acquire lock for initial busy-wait check.
        while (queue.isEmpty()) { // Busy-wait until the queue is non-empty.
            queueLock.release();
            // Drop the lock temporarily to allow a chance for other threads
            // needing queueLock to run so that a producer might add a task.
            queueLock.acquire(); // Re-acquire the lock for the next call to "queue.isEmpty()".
        }
        myTask = queue.dequeue(); // Take a task off of the queue.
        queueLock.release(); // Drop the queue lock until we need it again to take off the next task.
        doStuff(myTask); // Go off and do something with the task.
    }
}

Diese Methode stellt sicher, dass kein inkonsistenter Status auftritt, verschwendet jedoch CPU-Ressourcen aufgrund des unnötigen Wartens. Selbst wenn die Warteschlange leer ist und Producer-Threads lange Zeit nichts hinzuzufügen haben, warten Consumer-Threads immer unnötig. Auch wenn die Verbraucher bei der Bearbeitung ihrer aktuellen Aufgaben für längere Zeit blockiert sind und die Warteschlange voll ist, warten die Hersteller immer. Dies ist ein verschwenderischer Mechanismus. Was benötigt wird, ist eine Möglichkeit, Produzenten-Threads zu blockieren, bis die Warteschlange nicht mehr voll ist, und eine Möglichkeit, Consumer-Threads zu blockieren, bis die Warteschlange nicht leer ist.

(NB: Mutexe selbst können es auch sein Spin-Locks Wir müssen davon ausgehen, dass wir viel warten müssen, um die Sperre zu erhalten. Um dieses Problem der verschwendeten CPU-Ressourcen zu lösen, gehen wir davon aus queueLock ist keine Spin-Sperre und verwendet ordnungsgemäß eine Blockierungssperre selbst.)

Bedingungsvariablen[edit]

Die Lösung ist zu verwenden Bedingungsvariablen. Konzeptionell ist eine Bedingungsvariable eine Warteschlange von Threads, die einem Monitor zugeordnet sind und in der ein Thread möglicherweise darauf wartet, dass eine Bedingung erfüllt wird. Also jede Bedingungsvariable $c$ ist mit einer Behauptung verbunden $P. c$ . Während ein Thread auf eine Bedingungsvariable wartet, wird nicht davon ausgegangen, dass dieser Thread den Monitor belegt. Daher können andere Threads in den Monitor eintreten, um den Status des Monitors zu ändern. Bei den meisten Monitortypen können diese anderen Threads die Bedingungsvariable signalisieren $c$ um diese Behauptung anzuzeigen $P. c$ ist im aktuellen Zustand wahr.

Somit gibt es drei Hauptoperationen für Bedingungsvariablen:

wait c, m, wo c ist eine Bedingungsvariable und m ist ein Mutex (Schloss), der dem Monitor zugeordnet ist. Diese Operation wird von einem Thread aufgerufen, der bis zur Bestätigung warten muss P._c ist wahr, bevor Sie fortfahren. Während der Thread wartet, belegt er den Monitor nicht. Die Funktion und der Grundvertrag der “warten” Betrieb ist, die folgenden Schritte auszuführen:
1. Atomar:
  Lassen Sie den Mutex los m,
  
  Bewegen Sie diesen Thread aus dem “Laufen” zu c‘s “Warteschlange” (aka “Schlaf-Warteschlange”) von Fäden und
  
  schlaf diesen Thread. (Der Kontext wird synchron zu einem anderen Thread ausgegeben.)
2. Sobald dieser Thread anschließend benachrichtigt / signalisiert (siehe unten) und wieder aufgenommen wurde, wird der Mutex automatisch neu erfasst m.
Die Schritte 1a und 1b können in beliebiger Reihenfolge erfolgen, wobei 1c normalerweise danach erfolgt. Während der Thread schläft und in cIn der Warteschlange befindet sich der nächste auszuführende Programmzähler in Schritt 2 in der Mitte des “warten” Funktion / Unterprogramm. Somit schläft der Faden und wacht später in der Mitte des auf “warten” Betrieb.

Die Atomizität der Operationen in Schritt 1 ist wichtig, um Rennbedingungen zu vermeiden, die durch einen vorbeugenden Threadwechsel zwischen ihnen verursacht würden. Ein Fehlermodus, der auftreten könnte, wenn diese nicht atomar wären, ist a verpasstes Aufwachen, in dem der Thread laufen könnte c‘s Schlaf-Warteschlange und haben den Mutex freigegeben, aber ein vorbeugender Thread-Wechsel trat auf, bevor der Thread in den Ruhezustand ging, und ein anderer Thread rief eine Signal / Benachrichtigungs-Operation (siehe unten) auf c Bewegen Sie den ersten Faden wieder heraus cWarteschlange. Sobald der erste fragliche Thread wieder auf geschaltet wird, befindet sich sein Programmzähler in Schritt 1c, und er schläft und kann nicht wieder geweckt werden, wodurch die Invariante verletzt wird, die er hätte aktivieren sollen cist Schlafschlange, wenn es geschlafen hat. Andere Rennbedingungen hängen von der Reihenfolge der Schritte 1a und 1b ab und davon, wo ein Kontextwechsel stattfindet.
signal c, auch bekannt als notify cwird von einem Thread aufgerufen, um anzuzeigen, dass die Behauptung $P. c$ ist wahr. Je nach Typ und Implementierung des Monitors werden ein oder mehrere Threads verschoben cSchlafschlange an die “Warteschlange bereit” oder andere Warteschlangen, damit es ausgeführt werden kann. Es wird normalerweise als bewährte Methode angesehen, die “Signal”/.”benachrichtigen” Betrieb vor dem Loslassen von Mutex m das ist verbunden mit cSolange der Code jedoch ordnungsgemäß für die Parallelität ausgelegt ist und von der Threading-Implementierung abhängt, ist es häufig auch akzeptabel, die Sperre vor der Signalisierung aufzuheben. Abhängig von der Threading-Implementierung kann die Reihenfolge davon Auswirkungen auf die Planungspriorität haben. (Einige Autoren^[who?] Befürworten Sie stattdessen die Aufhebung der Sperre vor dem Signalisieren.) Eine Threading-Implementierung sollte alle besonderen Einschränkungen dieser Reihenfolge dokumentieren.
broadcast c, auch bekannt als notifyAll cist eine ähnliche Operation, die alle Threads in der Warteschlange von c aufweckt. Dadurch wird die Warteschlange geleert. Wenn mehr als eine Prädikatbedingung derselben Bedingungsvariablen zugeordnet ist, erfordert die Anwendung im Allgemeinen Übertragung Anstatt von Signal weil ein Thread, der auf den falschen Zustand wartet, möglicherweise geweckt wird und dann sofort wieder einschlafen kann, ohne einen Thread aufzuwecken, der auf den richtigen Zustand wartet, der gerade wahr geworden ist. Andernfalls, wenn die Prädikatbedingung eins zu eins mit der damit verbundenen Bedingungsvariablen ist, dann Signal kann effizienter sein als Übertragung.

Als Entwurfsregel können mehrere Bedingungsvariablen demselben Mutex zugeordnet werden, jedoch nicht umgekehrt. (Dies ist eine Eins-zu-Viele-Entsprechung.) Dies liegt am Prädikat $P. c$ ist für alle Threads, die den Monitor verwenden, gleich und muss unter gegenseitigem Ausschluss von allen anderen Threads geschützt werden, die möglicherweise zu einer Änderung der Bedingung führen oder diese lesen, während der betreffende Thread eine Änderung bewirkt, es können jedoch unterschiedliche Threads vorhanden sein die auf eine andere Bedingung für dieselbe Variable warten möchten, für die derselbe Mutex verwendet werden muss. In dem oben beschriebenen Producer-Consumer-Beispiel muss die Warteschlange durch ein eindeutiges Mutex-Objekt geschützt werden. m. Das “Produzent” Threads möchten mit Lock auf einem Monitor warten m und eine Bedingungsvariable

{ displaystyle c_ {full}}

$c_ {full}$ die blockiert, bis die Warteschlange nicht mehr voll ist. Das “Verbraucher” Threads möchten mit demselben Mutex auf einem anderen Monitor warten m aber eine andere Bedingungsvariable

{ displaystyle c_ {leer}}

$c_ {leer}$ die blockiert, bis die Warteschlange nicht leer ist. Es wäre (normalerweise) nie sinnvoll, unterschiedliche Mutexe für dieselbe Bedingungsvariable zu haben, aber dieses klassische Beispiel zeigt, warum es oft sicher sinnvoll ist, mehrere Bedingungsvariablen mit demselben Mutex zu verwenden. Ein Mutex, der von einer oder mehreren Bedingungsvariablen (einem oder mehreren Monitoren) verwendet wird, kann auch mit Code geteilt werden, der dies tut nicht Verwenden Sie Bedingungsvariablen (die diese einfach ohne Warte- / Signaloperationen erfassen / freigeben), wenn diese kritischen Abschnitte nicht das Warten auf eine bestimmte Bedingung für die gleichzeitigen Daten erfordern.

Überwachen Sie die Nutzung[edit]

Die ordnungsgemäße grundlegende Verwendung eines Monitors ist:

acquire(m); // Acquire this monitor's lock.
while (!p) { // While the condition/predicate/assertion that we are waiting for is not true...
	wait(m, cv); // Wait on this monitor's lock and condition variable.
}
// ... Critical section of code goes here ...
signal(cv2); -- OR -- notifyAll(cv2); // cv2 might be the same as cv or different.
release(m); // Release this monitor's lock.

Genauer gesagt ist dies der gleiche Pseudocode, jedoch mit ausführlicheren Kommentaren, um besser zu erklären, was vor sich geht:

// ... (previous code)
// About to enter the monitor.
// Acquire the advisory mutex (lock) associated with the concurrent
// data that is shared between threads, 
// to ensure that no two threads can be preemptively interleaved or
// run simultaneously on different cores while executing in critical
// sections that read or write this same concurrent data. If another
// thread is holding this mutex, then this thread will be put to sleep
// (blocked) and placed on m's sleep queue.  (Mutex "m" shall not be
// a spin-lock.)
acquire(m);
// Now, we are holding the lock and can check the condition for the
// first time.

// The first time we execute the while loop condition after the above
// "acquire", we are asking, "Does the condition/predicate/assertion
// we are waiting for happen to already be true?"

while (!p()) 	// "p" is any expression (e.g. variable or 
		// function-call) that checks the condition and
		// evaluates to boolean.  This itself is a critical
		// section, so you *MUST* be holding the lock when
		// executing this "while" loop condition!
				
// If this is not the first time the "while" condition is being checked,
// then we are asking the question, "Now that another thread using this
// monitor has notified me and woken me up and I have been context-switched
// back to, did the condition/predicate/assertion we are waiting on stay
// true between the time that I was woken up and the time that I re-acquired
// the lock inside the "wait" call in the last iteration of this loop, or
// did some other thread cause the condition to become false again in the
// meantime thus making this a spurious wakeup?

{
	// If this is the first iteration of the loop, then the answer is
	// "no" -- the condition is not ready yet. Otherwise, the answer is:
	// the latter.  This was a spurious wakeup, some other thread occurred
	// first and caused the condition to become false again, and we must
	// wait again.

	wait(m, cv);
		// Temporarily prevent any other thread on any core from doing
		// operations on m or cv.
		// release(m) 		// Atomically release lock "m" so other
		//			// code using this concurrent data
		// 			// can operate, move this thread to cv's
		//			// wait-queue so that it will be notified
		//			// sometime when the condition becomes
		// 			// true, and sleep this thread. Re-enable
		//			// other threads and cores to do 
		//			// operations on m and cv.
		//
		// Context switch occurs on this core.
		//
		// At some future time, the condition we are waiting for becomes
		// true, and another thread using this monitor (m, cv) does either
		// a signal/notify that happens to wake this thread up, or a
		// notifyAll that wakes us up, meaning that we have been taken out
		// of cv's wait-queue.
		//
		// During this time, other threads may cause the condition to
		// become false again, or the condition may toggle one or more
		// times, or it may happen to stay true.
		//
		// This thread is switched back to on some core.
		//
		// acquire(m)		// Lock "m" is re-acquired.
		
	// End this loop iteration and re-check the "while" loop condition to make
	// sure the predicate is still true.
	
}

// The condition we are waiting for is true!
// We are still holding the lock, either from before entering the monitor or from
// the last execution of "wait".

// Critical section of code goes here, which has a precondition that our predicate
// must be true.
// This code might make cv's condition false, and/or make other condition variables'
// predicates true.

// Call signal/notify or notifyAll, depending on which condition variables'
// predicates (who share mutex m) have been made true or may have been made true,
// and the monitor semantic type being used.

for (cv_x in cvs_to_notify) {
	notify(cv_x); -- OR -- notifyAll(cv_x);
}
// One or more threads have been woken up but will block as soon as they try
// to acquire m.

// Release the mutex so that notified thread(s) and others can enter their critical
// sections.
release(m);

Lösung des begrenzten Produzenten- / Konsumentenproblems[edit]

Nachdem wir die Verwendung von Bedingungsvariablen eingeführt haben, wollen wir sie verwenden, um das klassische Problem des begrenzten Produzenten / Konsumenten erneut zu untersuchen und zu lösen. Die klassische Lösung besteht darin, zwei Monitore zu verwenden, die zwei Bedingungsvariablen umfassen, die sich eine Sperre in der Warteschlange teilen:

global volatile RingBuffer queue; // A thread-unsafe ring-buffer of tasks.
global Lock queueLock;  	// A mutex for the ring-buffer of tasks. (Not a spin-lock.)
global CV queueEmptyCV; 	// A condition variable for consumer threads waiting for the queue to 
				// become non-empty.
                        	// Its associated lock is "queueLock".
global CV queueFullCV; 		// A condition variable for producer threads waiting for the queue 
				// to become non-full. Its associated lock is also "queueLock".

// Method representing each producer thread's behavior:
public method producer() {
    while (true) {
        task myTask = ...; // Producer makes some new task to be added.

        queueLock.acquire(); // Acquire lock for initial predicate check.
        while (queue.isFull()) { // Check if the queue is non-full.
            // Make the threading system atomically release queueLock,
            // enqueue this thread onto queueFullCV, and sleep this thread.
            wait(queueLock, queueFullCV);
            // Then, "wait" automatically re-acquires "queueLock" for re-checking
            // the predicate condition.
        }
        
        // Critical section that requires the queue to be non-full.
        // N.B.: We are holding queueLock.
        queue.enqueue(myTask); // Add the task to the queue.

        // Now the queue is guaranteed to be non-empty, so signal a consumer thread
        // or all consumer threads that might be blocked waiting for the queue to be non-empty:
        signal(queueEmptyCV); -- OR -- notifyAll(queueEmptyCV);
        
        // End of critical sections related to the queue.
        queueLock.release(); // Drop the queue lock until we need it again to add the next task.
    }
}

// Method representing each consumer thread's behavior:
public method consumer() {
    while (true) {
        queueLock.acquire(); // Acquire lock for initial predicate check.
        while (queue.isEmpty()) { // Check if the queue is non-empty.
            // Make the threading system atomically release queueLock,
            // enqueue this thread onto queueEmptyCV, and sleep this thread.
            wait(queueLock, queueEmptyCV);
            // Then, "wait" automatically re-acquires "queueLock" for re-checking
            // the predicate condition.
        }
        // Critical section that requires the queue to be non-empty.
        // N.B.: We are holding queueLock.
        myTask = queue.dequeue(); // Take a task off of the queue.
        // Now the queue is guaranteed to be non-full, so signal a producer thread
        // or all producer threads that might be blocked waiting for the queue to be non-full:
        signal(queueFullCV); -- OR -- notifyAll(queueFullCV);

        // End of critical sections related to the queue.
        queueLock.release(); // Drop the queue lock until we need it again to take off the next task.

        doStuff(myTask); // Go off and do something with the task.
    }
}

Dies stellt die Parallelität zwischen den Produzenten- und Konsumententhreads sicher, die sich die Taskwarteschlange teilen, und blockiert die Threads, die nichts zu tun haben, anstatt zu warten, wie im oben genannten Ansatz gezeigt, unter Verwendung von Spin-Locks.

Eine Variante dieser Lösung könnte eine einzige Bedingungsvariable für Hersteller und Verbraucher verwenden, die möglicherweise benannt wird “queueFullOrEmptyCV” oder “queueSizeChangedCV”. In diesem Fall ist der Bedingungsvariablen mehr als eine Bedingung zugeordnet, sodass die Bedingungsvariable eine schwächere Bedingung darstellt als die Bedingungen, die von einzelnen Threads überprüft werden. Die Bedingungsvariable repräsentiert Threads, die darauf warten, dass die Warteschlange nicht voll ist und diejenigen, die darauf warten, dass es nicht leer ist. Dies würde jedoch die Verwendung erfordern notifyAll in allen Threads, die die Bedingungsvariable verwenden und keine reguläre verwenden können Signal. Dies liegt daran, dass die regelmäßige Signal Möglicherweise wird ein Thread des falschen Typs aktiviert, dessen Bedingung noch nicht erfüllt ist, und dieser Thread wird wieder in den Ruhezustand versetzt, ohne dass ein Thread des richtigen Typs signalisiert wird. Zum Beispiel könnte ein Produzent die Warteschlange voll machen und einen anderen Produzenten anstelle eines Verbrauchers wecken, und der aufgeweckte Produzent würde wieder einschlafen. Im ergänzenden Fall könnte ein Verbraucher die Warteschlange leer machen und einen anderen Verbraucher anstelle eines Herstellers wecken, und der Verbraucher würde wieder einschlafen. Verwenden von notifyAll stellt sicher, dass ein Thread des richtigen Typs wie von der Problemstellung erwartet ausgeführt wird.

Hier ist die Variante, die nur eine Bedingungsvariable und notifyAll verwendet:

global volatile RingBuffer queue; // A thread-unsafe ring-buffer of tasks.
global Lock queueLock; // A mutex for the ring-buffer of tasks.  (Not a spin-lock.)
global CV queueFullOrEmptyCV; // A single condition variable for when the queue is not ready for any thread
                              // -- i.e., for producer threads waiting for the queue to become non-full 
                              // and consumer threads waiting for the queue to become non-empty.
                              // Its associated lock is "queueLock".
                              // Not safe to use regular "signal" because it is associated with
                              // multiple predicate conditions (assertions).

// Method representing each producer thread's behavior:
public method producer() {
    while (true) {
        task myTask = ...; // Producer makes some new task to be added.

        queueLock.acquire(); // Acquire lock for initial predicate check.
        while (queue.isFull()) { // Check if the queue is non-full.
            // Make the threading system atomically release queueLock,
            // enqueue this thread onto the CV, and sleep this thread.
            wait(queueLock, queueFullOrEmptyCV);
            // Then, "wait" automatically re-acquires "queueLock" for re-checking
            // the predicate condition.
        }
        
        // Critical section that requires the queue to be non-full.
        // N.B.: We are holding queueLock.
        queue.enqueue(myTask); // Add the task to the queue.

        // Now the queue is guaranteed to be non-empty, so signal all blocked threads
        // so that a consumer thread will take a task:
        notifyAll(queueFullOrEmptyCV); // Do not use "signal" (as it might wake up another producer instead).
        
        // End of critical sections related to the queue.
        queueLock.release(); // Drop the queue lock until we need it again to add the next task.
    }
}

// Method representing each consumer thread's behavior:
public method consumer() {
    while (true) {
        queueLock.acquire(); // Acquire lock for initial predicate check.
        while (queue.isEmpty()) { // Check if the queue is non-empty.
            // Make the threading system atomically release queueLock,
            // enqueue this thread onto the CV, and sleep this thread.
            wait(queueLock, queueFullOrEmptyCV);
            // Then, "wait" automatically re-acquires "queueLock" for re-checking
            // the predicate condition.
        }
        // Critical section that requires the queue to be non-full.
        // N.B.: We are holding queueLock.
        myTask = queue.dequeue(); // Take a task off of the queue.

        // Now the queue is guaranteed to be non-full, so signal all blocked threads
        // so that a producer thread will take a task:
        notifyAll(queueFullOrEmptyCV); // Do not use "signal" (as it might wake up another consumer instead).

        // End of critical sections related to the queue.
        queueLock.release(); // Drop the queue lock until we need it again to take off the next task.

        doStuff(myTask); // Go off and do something with the task.
    }
}

Synchronisationsprimitive[edit]

Das Implementieren von Mutexen und Bedingungsvariablen erfordert eine Art Synchronisationsprimitiv, das von der Hardwareunterstützung bereitgestellt wird und Atomizität bietet. Sperren und Bedingungsvariablen sind übergeordnete Abstraktionen über diese Synchronisationsprimitive. Auf einem Uniprozessor ist das Deaktivieren und Aktivieren von Interrupts eine Möglichkeit, Monitore zu implementieren, indem Kontextwechsel während der kritischen Abschnitte der Sperren und Bedingungsvariablen verhindert werden. Auf einem Multiprozessor reicht dies jedoch nicht aus. Auf einem Multiprozessor normalerweise spezielles Atom Lesen-Ändern-Schreiben Anweisungen auf dem Speicher wie Test-and-Set, vergleichen und tauschenusw. werden verwendet, je nachdem, was die ISA bereitstellt. Diese erfordern normalerweise das Aufschieben der Spin-Verriegelung für den internen Verriegelungszustand selbst, aber diese Verriegelung ist sehr kurz. Abhängig von der Implementierung können die atomaren Lese-, Änderungs- und Schreibbefehle den Bus für die Zugriffe anderer Kerne sperren und / oder die Neuordnung von Befehlen in der CPU verhindern. Hier ist ein Beispiel für eine Pseudocode-Implementierung von Teilen eines Threading-Systems sowie von Mutexen und Bedingungsvariablen im Mesa-Stil unter Verwendung von Test-and-Set und eine First-Come-First-Served-Politik. Dies beschönigt den größten Teil der Funktionsweise eines Threading-Systems, zeigt jedoch die Teile, die für Mutexe und Bedingungsvariablen relevant sind:

Beispiel für eine Mesa-Monitor-Implementierung mit Test-and-Set[edit]

// Basic parts of threading system:
// Assume "ThreadQueue" supports random access.
public volatile ThreadQueue readyQueue; // Thread-unsafe queue of ready threads.  Elements are (Thread*).
public volatile global Thread* currentThread; // Assume this variable is per-core.  (Others are shared.)

// Implements a spin-lock on just the synchronized state of the threading system itself.
// This is used with test-and-set as the synchronization primitive.
public volatile global bool threadingSystemBusy = false;

// Context-switch interrupt service routine (ISR):
// On the current CPU core, preemptively switch to another thread.
public method contextSwitchISR() {
    if (testAndSet(threadingSystemBusy)) {
        return; // Can't switch context right now.
    }

    // Ensure this interrupt can't happen again which would foul up the context switch:
    systemCall_disableInterrupts();

    // Get all of the registers of the currently-running process.
    // For Program Counter (PC), we will need the instruction location of
    // the "resume" label below.  Getting the register values is platform-dependent and may involve
    // reading the current stack frame, JMP/CALL instructions, etc.  (The details are beyond this scope.)
    currentThread->registers = getAllRegisters(); // Store the registers in the "currentThread" object in memory.
    currentThread->registers.PC = resume; // Set the next PC to the "resume" label below in this method.

    readyQueue.enqueue(currentThread); // Put this thread back onto the ready queue for later execution.
    
    Thread* otherThread = readyQueue.dequeue(); // Remove and get the next thread to run from the ready queue.
    
    currentThread = otherThread; // Replace the global current-thread pointer value so it is ready for the next thread.

    // Restore the registers from currentThread/otherThread, including a jump to the stored PC of the other thread
    // (at "resume" below).  Again, the details of how this is done are beyond this scope.
    restoreRegisters(otherThread.registers);

    // *** Now running "otherThread" (which is now "currentThread")!  The original thread is now "sleeping". ***

    resume: // This is where another contextSwitch() call needs to set PC to when switching context back here.

    // Return to where otherThread left off.

    threadingSystemBusy = false; // Must be an atomic assignment.
    systemCall_enableInterrupts(); // Turn pre-emptive switching back on on this core.
}

// Thread sleep method:
// On current CPU core, a synchronous context switch to another thread without putting
// the current thread on the ready queue.
// Must be holding "threadingSystemBusy" and disabled interrupts so that this method
// doesn't get interrupted by the thread-switching timer which would call contextSwitchISR().
// After returning from this method, must clear "threadingSystemBusy".
public method threadSleep() {
    // Get all of the registers of the currently-running process.
    // For Program Counter (PC), we will need the instruction location of
    // the "resume" label below.  Getting the register values is platform-dependent and may involve
    // reading the current stack frame, JMP/CALL instructions, etc.  (The details are beyond this scope.)
    currentThread->registers = getAllRegisters(); // Store the registers in the "currentThread" object in memory.
    currentThread->registers.PC = resume; // Set the next PC to the "resume" label below in this method.

    // Unlike contextSwitchISR(), we will not place currentThread back into readyQueue.
    // Instead, it has already been placed onto a mutex's or condition variable's queue.
    
    Thread* otherThread = readyQueue.dequeue(); // Remove and get the next thread to run from the ready queue.
    
    currentThread = otherThread; // Replace the global current-thread pointer value so it is ready for the next thread.

    // Restore the registers from currentThread/otherThread, including a jump to the stored PC of the other thread
    // (at "resume" below).  Again, the details of how this is done are beyond this scope.
    restoreRegisters(otherThread.registers);

    // *** Now running "otherThread" (which is now "currentThread")!  The original thread is now "sleeping". ***

    resume: // This is where another contextSwitch() call needs to set PC to when switching context back here.

    // Return to where otherThread left off.
}

public method wait(Mutex m, ConditionVariable c) {
    // Internal spin-lock while other threads on any core are accessing this object's
    // "held" and "threadQueue", or "readyQueue".
    while (testAndSet(threadingSystemBusy)) {}
    // N.B.: "threadingSystemBusy" is now true.
    
    // System call to disable interrupts on this core so that threadSleep() doesn't get interrupted by
    // the thread-switching timer on this core which would call contextSwitchISR().
    // Done outside threadSleep() for more efficiency so that this thread will be sleeped
    // right after going on the condition-variable queue.
    systemCall_disableInterrupts();
 
    assert m.held; // (Specifically, this thread must be the one holding it.)
    
    m.release();
    c.waitingThreads.enqueue(currentThread);
    
    threadSleep();
    
    // Thread sleeps ... Thread gets woken up from a signal/broadcast.
    
    threadingSystemBusy = false; // Must be an atomic assignment.
    systemCall_enableInterrupts(); // Turn pre-emptive switching back on on this core.
    
    // Mesa style:
    // Context switches may now occur here, making the client caller's predicate false.
    
    m.acquire();
}

public method signal(ConditionVariable c) {
    // Internal spin-lock while other threads on any core are accessing this object's
    // "held" and "threadQueue", or "readyQueue".
    while (testAndSet(threadingSystemBusy)) {}
    // N.B.: "threadingSystemBusy" is now true.
    
    // System call to disable interrupts on this core so that threadSleep() doesn't get interrupted by
    // the thread-switching timer on this core which would call contextSwitchISR().
    // Done outside threadSleep() for more efficiency so that this thread will be sleeped
    // right after going on the condition-variable queue.
    systemCall_disableInterrupts();
    
    if (!c.waitingThreads.isEmpty()) {
        wokenThread = c.waitingThreads.dequeue();
        readyQueue.enqueue(wokenThread);
    }
    
    threadingSystemBusy = false; // Must be an atomic assignment.
    systemCall_enableInterrupts(); // Turn pre-emptive switching back on on this core.
    
    // Mesa style:
    // The woken thread is not given any priority.
}

public method broadcast(ConditionVariable c) {
    // Internal spin-lock while other threads on any core are accessing this object's
    // "held" and "threadQueue", or "readyQueue".
    while (testAndSet(threadingSystemBusy)) {}
    // N.B.: "threadingSystemBusy" is now true.
    
    // System call to disable interrupts on this core so that threadSleep() doesn't get interrupted by
    // the thread-switching timer on this core which would call contextSwitchISR().
    // Done outside threadSleep() for more efficiency so that this thread will be sleeped
    // right after going on the condition-variable queue.
    systemCall_disableInterrupts();
    
    while (!c.waitingThreads.isEmpty()) {
        wokenThread = c.waitingThreads.dequeue();
        readyQueue.enqueue(wokenThread);
    }
    
    threadingSystemBusy = false; // Must be an atomic assignment.
    systemCall_enableInterrupts(); // Turn pre-emptive switching back on on this core.
    
    // Mesa style:
    // The woken threads are not given any priority.
}

class Mutex {
    protected volatile bool held = false;
    private volatile ThreadQueue blockingThreads; // Thread-unsafe queue of blocked threads.  Elements are (Thread*).
    
    public method acquire() {
        // Internal spin-lock while other threads on any core are accessing this object's
        // "held" and "threadQueue", or "readyQueue".
        while (testAndSet(threadingSystemBusy)) {}
        // N.B.: "threadingSystemBusy" is now true.
        
        // System call to disable interrupts on this core so that threadSleep() doesn't get interrupted by
        // the thread-switching timer on this core which would call contextSwitchISR().
        // Done outside threadSleep() for more efficiency so that this thread will be sleeped
        // right after going on the lock queue.
        systemCall_disableInterrupts();

        assert !blockingThreads.contains(currentThread);

        if (held) {
            // Put "currentThread" on this lock's queue so that it will be
            // considered "sleeping" on this lock.
            // Note that "currentThread" still needs to be handled by threadSleep().
            readyQueue.remove(currentThread);
            blockingThreads.enqueue(currentThread);
            threadSleep();
            
            // Now we are woken up, which must be because "held" became false.
            assert !held;
            assert !blockingThreads.contains(currentThread);
        }
        
        held = true;
        
        threadingSystemBusy = false; // Must be an atomic assignment.
        systemCall_enableInterrupts(); // Turn pre-emptive switching back on on this core.
    }        
        
    public method release() {
        // Internal spin-lock while other threads on any core are accessing this object's
        // "held" and "threadQueue", or "readyQueue".
        while (testAndSet(threadingSystemBusy)) {}
        // N.B.: "threadingSystemBusy" is now true.
        
        // System call to disable interrupts on this core for efficiency.
        systemCall_disableInterrupts();
        
        assert held; // (Release should only be performed while the lock is held.)

        held = false;
        
        if (!blockingThreads.isEmpty()) {
            Thread* unblockedThread = blockingThreads.dequeue();
            readyQueue.enqueue(unblockedThread);
        }
        
        threadingSystemBusy = false; // Must be an atomic assignment.
        systemCall_enableInterrupts(); // Turn pre-emptive switching back on on this core.
    }
}

struct ConditionVariable {
    volatile ThreadQueue waitingThreads;
}

Semaphor[edit]

Betrachten Sie als Beispiel eine thread-sichere Klasse, die ein Semaphor implementiert. Es gibt Methoden zum Inkrementieren (V) und Dekrementieren (P) einer privaten Ganzzahl s. Die Ganzzahl darf jedoch niemals unter 0 dekrementiert werden. Daher muss ein Thread, der versucht zu dekrementieren, warten, bis die Ganzzahl positiv ist. Wir verwenden eine Bedingungsvariable sIsPositive mit einer damit verbundenen Behauptung von

{ displaystyle P _ { mathtt {sIsPositive}} = (s> 0)}

${ displaystyle P _ { mathtt {sIsPositive}} = (s> 0)}”/>. <pre>monitor class Semaphore { private int s := 0 invariant s >= 0 private Condition sIsPositive /* associated with s > 0 */ public method P() { while s = 0: wait sIsPositive assert s > 0 s := s - 1 } public method V() { s := s + 1 assert s > 0 signal sIsPositive } } </pre> Implementiert, um die gesamte Synchronisation anzuzeigen (Entfernen der Annahme einer thread-sicheren Klasse und Anzeigen des Mutex): <pre>class Semaphore { private volatile int s := 0 invariant s >= 0 private ConditionVariable sIsPositive /* associated with s > 0 */ private Mutex myLock /* Lock on$ public method P() { myLock.acquire() while s = 0: wait(myLock, sIsPositive) assert s > 0 s := s - 1 myLock.release() } public method V() { myLock.acquire() s := s + 1 assert s > 0 signal sIsPositive myLock.release() } }

Monitor implementiert mit Semaphoren[edit]

Umgekehrt können Sperren und Bedingungsvariablen auch aus Semaphoren abgeleitet werden, wodurch Monitore und Semaphore untereinander reduzierbar werden:

Die hier angegebene Implementierung ist falsch. Wenn ein Thread nach dem Aufruf von Broadcast () wait () aufruft, kann ein ursprünglicher Thread auf unbestimmte Zeit hängen bleiben, da Broadcast () das Semaphor nur so oft erhöht, bis Threads bereits warten.

public method wait(Mutex m, ConditionVariable c) {
    assert m.held;

    c.internalMutex.acquire();
    
    c.numWaiters++;
    m.release(); // Can go before/after the neighboring lines.
    c.internalMutex.release();

    // Another thread could signal here, but that's OK because of how
    // semaphores count.  If c.sem's number becomes 1, we'll have no
    // waiting time.
    c.sem.Proberen(); // Block on the CV.
    // Woken
    m.acquire(); // Re-acquire the mutex.
}

public method signal(ConditionVariable c) {
    c.internalMutex.acquire();
    if (c.numWaiters > 0) {
        c.numWaiters--;
        c.sem.Verhogen(); // (Doesn't need to be protected by c.internalMutex.)
    }
    c.internalMutex.release();
}

public method broadcast(ConditionVariable c) {
    c.internalMutex.acquire();
    while (c.numWaiters > 0) {
        c.numWaiters--;
        c.sem.Verhogen(); // (Doesn't need to be protected by c.internalMutex.)
    }
    c.internalMutex.release();
}

class Mutex {
    protected boolean held = false; // For assertions only, to make sure sem's number never goes > 1.
    protected Semaphore sem = Semaphore(1); // The number shall always be at most 1.
                                          // Not held <--> 1; held <--> 0.

    public method acquire() {
        sem.Proberen();
        assert !held;
        held = true;
    }
    
    public method release() {
        assert held; // Make sure we never Verhogen sem above 1.  That would be bad.
        held = false;
        sem.Verhogen();
    }
}

class ConditionVariable {
    protected int numWaiters = 0; // Roughly tracks the number of waiters blocked in sem.
                                // (The semaphore's internal state is necessarily private.)
    protected Semaphore sem = Semaphore(0); // Provides the wait queue.
    protected Mutex internalMutex; // (Really another Semaphore.  Protects "numWaiters".)
}

Wenn ein Signal Wenn eine Bedingungsvariable auftritt, auf die mindestens ein anderer Thread wartet, gibt es mindestens zwei Threads, die dann den Monitor belegen könnten: den Thread, der signalisiert, und einen der Threads, die warten. Damit jeweils höchstens ein Thread den Monitor belegt, muss eine Auswahl getroffen werden. Es gibt zwei Denkschulen, wie diese Wahl am besten gelöst werden kann. Dies führt zu zwei Arten von Bedingungsvariablen, die als nächstes untersucht werden:

Bedingungsvariablen blockieren Geben Sie einem signalisierten Thread Priorität.
Nicht blockierende Bedingungsvariablen Geben Sie dem Signalisierungs-Thread Priorität.

Bedingungsvariablen blockieren[edit]

Die ursprünglichen Vorschläge von CAR Hoare und Per Brinch Hansen waren für Bedingungsvariablen blockieren. Bei einer blockierenden Bedingungsvariablen muss der Signalisierungsthread (mindestens) außerhalb des Monitors warten, bis der signalisierte Thread die Belegung des Monitors aufgibt, indem er entweder zurückkehrt oder erneut auf eine Bedingungsvariable wartet. Monitore, die blockierende Bedingungsvariablen verwenden, werden häufig aufgerufen Hoare-Stil Monitore oder Signal-und-Dringlichkeit-Warten Monitore.

Ein Hoare-Monitor mit zwei Bedingungsvariablen a und b. Nach Buhr et al.

Wir gehen davon aus, dass jedem Monitorobjekt zwei Thread-Warteschlangen zugeordnet sind

e ist die Eingangswarteschlange
s ist eine Warteschlange von Threads, die signalisiert haben.

Außerdem nehmen wir das für jede Bedingungsvariable an $c$ gibt es eine Warteschlange

$c$ .qDies ist eine Warteschlange für Threads, die auf eine Bedingungsvariable warten $c$

Es wird normalerweise garantiert, dass alle Warteschlangen fair sind, und in einigen Implementierungen kann garantiert werden, dass sie zuerst an erster Stelle stehen.

Die Implementierung jeder Operation ist wie folgt. (Wir gehen davon aus, dass jede Operation in gegenseitigem Ausschluss mit den anderen ausgeführt wird. Daher werden neu gestartete Threads erst ausgeführt, wenn die Operation abgeschlossen ist.)

enter the monitor:
    enter the method
    if the monitor is locked
        add this thread to e
        block this thread
    else
        lock the monitor

leave the monitor:
    schedule
    return from the method

wait  $c$ :
    add this thread to  $c$ .q
    schedule
    block this thread

signal  $c$ :
    if there is a thread waiting on  $c$ .q
        select and remove one such thread t from  $c$ .q
        (t is called "the signaled thread")
        add this thread to s
        restart t
        (so t will occupy the monitor next)
        block this thread

schedule:
    if there is a thread on s
        select and remove one thread from s and restart it
        (this thread will occupy the monitor next)
    else if there is a thread on e
        select and remove one thread from e and restart it
        (this thread will occupy the monitor next)
    else
        unlock the monitor
        (the monitor will become unoccupied)

Das schedule Die Routine wählt den nächsten Thread aus, der den Monitor belegen soll, oder entsperrt den Monitor, wenn keine Kandidatenthreads vorhanden sind.

Die resultierende Signaldisziplin ist bekannt a “Signal und dringendes Warten,” da der Signalgeber warten muss, aber Vorrang vor Threads in der Eingangswarteschlange hat. Eine Alternative ist “signalisieren und warten,” in dem gibt es keine s Warteschlange und Signalgeber warten auf die e Warteschlange stattdessen.

Einige Implementierungen bieten a signalisieren und zurück Operation, die die Signalisierung mit der Rückkehr von einer Prozedur kombiniert.

signal  $c$  and return:
    if there is a thread waiting on  $c$ .q
        select and remove one such thread t from  $c$ .q
        (t is called "the signaled thread")
        restart t
        (so t will occupy the monitor next)
    else
        schedule
    return from the method

In beiden Fällen (“Signal und dringendes Warten” oder “signalisieren und warten”) Wenn eine Bedingungsvariable signalisiert wird und mindestens ein Thread auf die Bedingungsvariable wartet, übergibt der Signalisierungs-Thread die Belegung nahtlos an den signalisierten Thread, so dass kein anderer Thread dazwischen eine Belegung erhalten kann. Wenn $P. c$ ist am Anfang von jedem wahr Signal $c$ Operation wird es am Ende von jedem wahr sein warten $c$ Betrieb. Dies wird durch die folgenden Verträge zusammengefasst. In diesen Verträgen $ich$ ist die Invariante des Monitors.

enter the monitor:
    postcondition  $I$ 

leave the monitor:
    precondition  $I$ 

wait  $c$ :
    precondition  $I$ 
    modifies the state of the monitor
    postcondition  $P c$  and  $I$ 

signal  $c$ :
    precondition  $P c$  and  $I$ 
    modifies the state of the monitor
    postcondition  $I$ 

signal  $c$  and return:
    precondition  $P c$  and  $I$

In diesen Verträgen wird davon ausgegangen, dass $ich$ und $P. c$ hängen nicht vom Inhalt oder der Länge von Warteschlangen ab.

(Wenn die Bedingungsvariable nach der Anzahl der in ihrer Warteschlange wartenden Threads abgefragt werden kann, können komplexere Verträge vergeben werden. Ein nützliches Vertragspaar, mit dem die Belegung ohne Festlegen der Invariante übergeben werden kann, lautet beispielsweise:

wait  $c$ :
    precondition  $I$ 
    modifies the state of the monitor
    postcondition  $P c$ 

signal  $c$ 
    precondition (not empty( $c$ ) and  $P c$ ) or (empty( $c$ ) and  $I$ )
    modifies the state of the monitor
    postcondition  $I$

Siehe Howard^[4] und Buhr et al.,^[5] für mehr).

Es ist wichtig anzumerken, dass die Behauptung $P. c$ liegt ganz beim Programmierer; er oder sie muss einfach konsequent sein, was es ist.

Wir schließen diesen Abschnitt mit einem Beispiel einer thread-sicheren Klasse ab, die einen Blockierungsmonitor verwendet, der einen begrenzten, thread-sicheren Stapel implementiert.

monitor class SharedStack {
    private const capacity := 10
    private int[capacity] A
    private int size := 0
    invariant 0 <= size and size <= capacity
    private BlockingCondition theStackIsNotEmpty /* associated with 0 < size and size <= capacity */
    private BlockingCondition theStackIsNotFull /* associated with 0 <= size and size < capacity */

    public method push(int value)
    {
        if size = capacity then wait theStackIsNotFull
        assert 0 <= size and size < capacity
        A[size] := value ; size := size + 1
        assert 0 < size and size <= capacity
        signal theStackIsNotEmpty and return
    }

    public method int pop()
    {
        if size = 0 then wait theStackIsNotEmpty
        assert 0 < size and size <= capacity
        size := size - 1 ;
        assert 0 <= size and size < capacity
        signal theStackIsNotFull and return A[size]
    }
}

Beachten Sie, dass in diesem Beispiel der thread-sichere Stapel intern einen Mutex bereitstellt, der wie im vorherigen Beispiel für Hersteller / Verbraucher von beiden Bedingungsvariablen gemeinsam genutzt wird, die unterschiedliche Bedingungen für dieselben gleichzeitigen Daten prüfen. Der einzige Unterschied besteht darin, dass das Producer / Consumer-Beispiel eine reguläre, nicht threadsichere Warteschlange angenommen hat und einen eigenständigen Mutex und Bedingungsvariablen verwendet hat, ohne dass diese Details des Monitors wie hier abstrahiert wurden. In diesem Beispiel, wenn die “warten” Wenn die Operation aufgerufen wird, muss sie irgendwie mit dem Mutex des thread-sicheren Stacks geliefert werden, z “warten” Betrieb ist ein integraler Bestandteil der “Klasse überwachen”. Abgesehen von dieser Art von abstrahierter Funktionalität, wenn a “roh” Monitor wird verwendet, wird es immer müssen einen Mutex und eine Bedingungsvariable enthalten, mit einem eindeutigen Mutex für jede Bedingungsvariable.

Nicht blockierende Bedingungsvariablen[edit]

Mit nicht blockierende Bedingungsvariablen (auch genannt “Mesa-Stil” Bedingungsvariablen oder “signalisieren und fortfahren” Bedingungsvariablen), Signalisierung führt nicht dazu, dass der Signalisierungsthread die Belegung des Monitors verliert. Stattdessen werden die signalisierten Threads in die verschoben e Warteschlange. Es besteht keine Notwendigkeit für die s Warteschlange.

Ein Monitor im Mesa-Stil mit zwei Bedingungsvariablen a und b

Bei nicht blockierenden Bedingungsvariablen wird die Signal Operation wird oft genannt benachrichtigen – eine Terminologie, der wir hier folgen werden. Es ist auch üblich, a alle benachrichtigen Operation, die alle auf eine Bedingungsvariable wartenden Threads in die verschiebt e Warteschlange.

Die Bedeutung verschiedener Operationen wird hier angegeben. (Wir gehen davon aus, dass jede Operation in gegenseitigem Ausschluss mit den anderen ausgeführt wird. Daher werden neu gestartete Threads erst ausgeführt, wenn die Operation abgeschlossen ist.)

enter the monitor:
    enter the method
    if the monitor is locked
        add this thread to e
        block this thread
    else
        lock the monitor

leave the monitor:
    schedule
    return from the method

wait  $c$ :
    add this thread to  $c$ .q
    schedule
    block this thread

notify  $c$ :
    if there is a thread waiting on  $c$ .q
        select and remove one thread t from  $c$ .q
        (t is called "the notified thread")
        move t to e

notify all  $c$ :
    move all threads waiting on  $c$ .q to e

schedule :
    if there is a thread on e
        select and remove one thread from e and restart it
    else
        unlock the monitor

Als Variation dieses Schemas kann der benachrichtigte Thread in eine aufgerufene Warteschlange verschoben werden w, die Vorrang vor e. Siehe Howard^[4] und Buhr et al.^[5] zur weiteren Diskussion.

Es ist möglich, eine Behauptung zuzuordnen $P. c$ mit jeder Bedingungsvariablen $c$ so dass $P. c$ ist sicher, bei der Rückkehr von wahr zu sein wait $c$ . Das muss man aber sicherstellen $P. c$ ist aus der Zeit der erhalten benachrichtigenDer Thread gibt die Belegung auf, bis der benachrichtigte Thread ausgewählt wird, um wieder in den Monitor einzutreten. Zwischen diesen Zeiten kann es zu Aktivitäten anderer Insassen kommen. So ist es üblich für $P. c$ einfach sein wahr.

Aus diesem Grund ist es normalerweise notwendig, jedes einzuschließen warten Operation in einer Schleife wie dieser

while not(  $P$  ) do
    wait c

wo $P.$ ist ein Zustand stärker als $P. c$ . Die Operationen notify $c$ und notify all $c$ werden behandelt als “Hinweise” Das $P.$ kann für einen wartenden Thread zutreffen. Jede Iteration einer solchen Schleife nach der ersten stellt eine verlorene Benachrichtigung dar; Daher muss bei nicht blockierenden Monitoren darauf geachtet werden, dass nicht zu viele Benachrichtigungen verloren gehen.

Als Beispiel für “Andeutung” Stellen Sie sich ein Bankkonto vor, auf dem ein abhebender Thread wartet, bis das Konto über ausreichend Guthaben verfügt, bevor Sie fortfahren

monitor class Account {
    private int balance := 0
    invariant balance >= 0
    private NonblockingCondition balanceMayBeBigEnough

    public method withdraw(int amount)
        precondition amount >= 0
    {
        while balance < amount do wait balanceMayBeBigEnough
        assert balance >= amount
        balance := balance - amount
    }

    public method deposit(int amount)
        precondition amount >= 0
    {
        balance := balance + amount
        notify all balanceMayBeBigEnough
    }
}

In diesem Beispiel ist die Bedingung, auf die gewartet wird, eine Funktion des abzuziehenden Betrags, so dass es für einen Einzahlungsfaden unmöglich ist, dies zu tun kennt dass es eine solche Bedingung wahr machte. In diesem Fall ist es sinnvoll, jedem wartenden Thread (einzeln) zu erlauben, zu überprüfen, ob seine Behauptung wahr ist.

Implizite Zustandsvariablenmonitore[edit]

In der Java-Sprache kann jedes Objekt als Monitor verwendet werden. Methoden, die einen gegenseitigen Ausschluss erfordern, müssen ausdrücklich mit dem gekennzeichnet werden synchronisiert Stichwort. Codeblöcke können auch mit gekennzeichnet sein synchronisiert.

Anstatt explizite Bedingungsvariablen zu haben, ist jeder Monitor (dh das Objekt) zusätzlich zu seiner Eingangswarteschlange mit einer einzigen Warteschlange ausgestattet. Das gesamte Warten erfolgt in dieser einzelnen Warteschlange benachrichtigen und notifyAll Operationen gelten für diese Warteschlange. Dieser Ansatz wurde in anderen Sprachen übernommen, beispielsweise in C #.

Implizite Signalisierung[edit]

Ein anderer Ansatz zur Signalisierung besteht darin, das wegzulassen Signal Betrieb. Immer wenn ein Thread den Monitor verlässt (durch Zurückgeben oder Warten), werden die Aussagen aller wartenden Threads ausgewertet, bis festgestellt wird, dass einer wahr ist. In einem solchen System werden Bedingungsvariablen nicht benötigt, aber die Zusicherungen müssen explizit codiert werden. Der Vertrag für das Warten ist

wait P:
    precondition I
    modifies the state of the monitor
    postcondition P and I

Geschichte[edit]

Brinch Hansen und Hoare entwickelten das Monitorkonzept in den frühen 1970er Jahren auf der Grundlage früherer eigener Ideen und von Edsger Dijkstra.^[6] Brinch Hansen veröffentlichte die erste Monitor-Notation und übernahm das Klassenkonzept von Simula 67,^[1] und erfand einen Warteschlangenmechanismus.^[7] Hoare verfeinerte die Regeln für die Wiederaufnahme des Prozesses.^[2] Brinch Hansen hat in Concurrent Pascal die erste Implementierung von Monitoren erstellt.^[6] Hoare demonstrierte ihre Gleichwertigkeit mit Semaphoren.

Monitore (und Concurrent Pascal) wurden bald verwendet, um die Prozesssynchronisation im Solo-Betriebssystem zu strukturieren.^[8]^[9]

Zu den Programmiersprachen, die Monitore unterstützen, gehören:

Es wurde eine Reihe von Bibliotheken geschrieben, mit denen Monitore in Sprachen erstellt werden können, die sie nicht nativ unterstützen. Wenn Bibliotheksaufrufe verwendet werden, ist es Sache des Programmierers, den Anfang und das Ende des ausgeführten Codes explizit mit gegenseitigem Ausschluss zu markieren. Pthreads ist eine solche Bibliothek.

Siehe auch[edit]

^ ^ein ^b Brinch Hansen, Per (1973). “7.2 Klassenkonzept” (PDF). Betriebssystemprinzipien. Prentice Hall. ISBN 978-0-13-637843-3.
^ ^ein ^b Hoare, CAR (Oktober 1974). “Monitore: Ein Konzept zur Strukturierung des Betriebssystems”. Comm. ACM. 17 (10): 549–557. CiteSeerX 10.1.1.24.6394. doi:10.1145 / 355620.361161. S2CID 1005769.
^ Hansen, PB (Juni 1975). “Die Programmiersprache Concurrent Pascal” (PDF). IEEE Trans. Softw. Eng. SE-1 (2): 199–207. doi:10.1109 / TSE.1975.6312840. S2CID 2000388.
^ ^ein ^b Howard, John H. (1976). “Signalisierung in Monitoren”. ICSE ’76 Proceedings der 2. internationalen Konferenz über Software Engineering. Internationale Konferenz für Software Engineering. Los Alamitos, CA, USA: IEEE Computer Society Press. S. 47–52.
^ ^ein ^b Buhr, Peter A.; Fortier, Michel; Sarg, Michael H. (März 1995). “Überwachung der Klassifizierung”. ACM Computing-Umfragen. 27 (1): 63–107. doi:10.1145 / 214037.214100. S2CID 207193134.
^ ^ein ^b Hansen, Per Brinch (1993). “Monitore und gleichzeitiger Pascal: eine persönliche Geschichte”. HOPL-II: Die zweite ACM SIGPLAN-Konferenz zur Geschichte der Programmiersprachen. Geschichte der Programmiersprachen. New York, NY, USA: ACM. S. 1–35. doi:10.1145 / 155360.155361. ISBN 0-89791-570-4.
^ Brinch Hansen, Per (Juli 1972). “Strukturierte Multiprogrammierung (Invited Paper)”. Mitteilungen der ACM. 15 (7): 574–578. doi:10.1145 / 361454.361473. S2CID 14125530.
^ Brinch Hansen, Per (April 1976). “Das Solo-Betriebssystem: ein Concurrent Pascal-Programm” (PDF). Software – Praxis und Erfahrung.
^ Brinch Hansen, Per (1977). Die Architektur gleichzeitiger Programme. Prentice Hall. ISBN 978-0-13-044628-2.

Weiterführende Literatur[edit]

Externe Links[edit]

after-content-x4

Monitor (Synchronisation) – Wikipedia

Gegenseitiger Ausschluss[edit]

Bedingungsvariablen[edit]

Problemstellung[edit]

Fallstudie: Klassisches Problem zwischen Produzenten und Verbrauchern[edit]

Ohne Synchronisation falsch[edit]

Spin-Warten[edit]

Bedingungsvariablen[edit]

Überwachen Sie die Nutzung[edit]

Lösung des begrenzten Produzenten- / Konsumentenproblems[edit]

Synchronisationsprimitive[edit]

Beispiel für eine Mesa-Monitor-Implementierung mit Test-and-Set[edit]

Semaphor[edit]

Monitor implementiert mit Semaphoren[edit]

Bedingungsvariablen blockieren[edit]

Nicht blockierende Bedingungsvariablen[edit]

Implizite Zustandsvariablenmonitore[edit]

Implizite Signalisierung[edit]

Geschichte[edit]

Siehe auch[edit]

Weiterführende Literatur[edit]

Externe Links[edit]

Recent Posts

Recent Comments

Archives

Categories

Meta