Monitor (Synchronisation) - Monitor (synchronization)

Bei der gleichzeitigen Programmierung (auch als parallele Programmierung bezeichnet) ist ein Monitor ein Synchronisationskonstrukt, das es Threads ermöglicht , sowohl gegenseitigen Ausschluss als auch die Möglichkeit zu haben, zu warten (blockieren), bis eine bestimmte Bedingung falsch wird. Monitore verfügen auch über einen Mechanismus, um anderen Threads zu signalisieren, dass ihre Bedingung erfüllt ist. Ein Monitor besteht aus einem Mutex-(Sperr-) Objekt und Bedingungsvariablen . Eine Bedingungsvariable ist im Wesentlichen ein Container von 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 Bedingung erfüllt ist, bevor sie den exklusiven Zugriff wiedererlangen und ihre Aufgabe wieder aufnehmen.

Eine andere Definition von monitor ist eine threadsichere Klasse , ein Objekt oder ein Modul , das einen Mutex umschließt, um den Zugriff auf eine Methode oder Variable durch mehr als einen Thread sicher zu ermöglichen . Das charakteristische Merkmal eines Monitors ist, dass seine Methoden unter gegenseitigem Ausschluss ausgeführt werden : Zu jedem Zeitpunkt darf höchstens ein Thread eine seiner Methoden ausführen . Durch die Verwendung einer oder mehrerer Bedingungsvariablen kann es auch Threads die Möglichkeit bieten, auf eine bestimmte Bedingung zu warten (also unter Verwendung der obigen Definition eines "Monitors"). Für den Rest dieses Artikels wird diese Bedeutung von „Monitor“ als „thread-sicheres Objekt/Klasse/Modul“ bezeichnet.

Monitore wurden von Per Brinch Hansen und CAR Hoare erfunden und zuerst in Brinch Hansens Concurrent Pascal Sprache implementiert.

Gegenseitiger Ausschluss

Betrachten Sie als einfaches Beispiel ein Thread-sicheres 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 Faden wird ein Verfahren zur Herstellung eines faden sicheren Objekts ausgeführt wird , wird gesagt , zu besetzen , das Objekt durch seinen Halt Mutex (lock) . Thread-sichere Objekte werden implementiert, um zu erzwingen, dass zu jedem Zeitpunkt höchstens ein Thread das Objekt belegen darf . Die anfänglich entsperrte Sperre wird beim Start 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 threadsicheren 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önnten, dass ohne Grund Geld verloren oder gewonnen wird. Zum Beispiel könnten zwei Threads, die 1000 vom Konto abheben, beide true zurückgeben, während der Saldo wie folgt um nur 1000 sinkt: Zuerst rufen beide Threads den aktuellen Saldo ab, finden ihn über 1000 und ziehen 1000 davon ab; dann speichern beide Threads den Saldo und kehren zurück.

Die syntaktische Zucker- "Monitor-Klasse" im obigen Beispiel implementiert die folgende grundlegende Darstellung des Codes, indem sie die Ausführung jeder Funktion in Mutexes verpackt: 

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

Problemstellung

Für viele Anwendungen reicht ein gegenseitiger Ausschluss nicht aus. Threads, die eine Operation versuchen, müssen möglicherweise warten, bis eine Bedingung P wahr ist. Eine busy waiting Schleife 

while not( P ) do skip

funktioniert nicht, da gegenseitiger Ausschluss verhindert, dass andere Threads in den Monitor eintreten, um die Bedingung wahr zu machen. Andere "Lösungen" existieren, wie beispielsweise eine Schleife, die den Monitor entsperrt, eine gewisse Zeit wartet, den Monitor sperrt und auf die Bedingung P prüft . Theoretisch funktioniert es und wird nicht blockiert, aber es treten Probleme auf. Es ist schwer, eine angemessene Wartezeit zu bestimmen, zu klein und der Thread wird die CPU belasten, zu groß und er wird anscheinend nicht reagieren. Was wir brauchen , ist ein Weg , um den Faden zu signalisieren , wenn die Bedingung P wahr (oder könnte wahr sein).

Fallstudie: klassisches Bounded Producer/Consumer Problem

Ein klassisches Parallelitätsproblem ist das des begrenzten Producer/Consumer , bei dem es eine Warteschlange oder einen Ringpuffer von Aufgaben mit einer maximalen Größe gibt, wobei ein oder mehrere Threads "Produzenten"-Threads sind, die Aufgaben zur Warteschlange hinzufügen, und einer oder mehrere or andere Threads sind "Consumer"-Threads, die Aufgaben aus der Warteschlange nehmen. Es wird davon ausgegangen, dass die Warteschlange selbst nicht Thread-sicher ist und sie 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 Consumer-Threads ist, die Aufgaben aus der Warteschlange entfernen. Auf der anderen Seite müssen die Consumer-Threads immer dann blockiert werden, wenn die Warteschlange leer ist, bis mehr Aufgaben verfügbar sind, da sie von Producer-Threads hinzugefügt werden.

Da die Warteschlange ein gleichzeitiges Objekt ist, das von Threads gemeinsam genutzt wird, müssen Zugriffe darauf atomar erfolgen , da die Warteschlange im Verlauf des Warteschlangenzugriffs in einen inkonsistenten Zustand versetzt werden kann, der niemals zwischen Threads offengelegt werden sollte. Somit stellt jeder Code, der auf die Warteschlange zugreift, einen kritischen Abschnitt dar , der durch gegenseitigen Ausschluss synchronisiert werden muss. Wenn Code- und Prozessoranweisungen in kritischen Codeabschnitten, die auf die Warteschlange zugreifen, durch willkürliche Kontextwechsel zwischen Threads auf demselben Prozessor oder durch gleichzeitig ausgeführte Threads auf mehreren Prozessoren verschachtelt werden könnten, besteht die Gefahr, dass inkonsistente Zustände offengelegt werden und Race-Conditions verursacht werden .

Falsch ohne Synchronisation

Ein naiver Ansatz besteht darin, den Code mit Busy-Waiting und ohne Synchronisierung zu entwerfen , wodurch der Code Race-Conditions 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 weist insofern ein ernsthaftes Problem auf, als Zugriffe auf die Warteschlange unterbrochen und mit den Zugriffen anderer Threads auf die Warteschlange verschachtelt werden können. Die Methoden queue.enqueue und queue.dequeue enthalten wahrscheinlich Anweisungen zum Aktualisieren der Mitgliedsvariablen der Warteschlange, wie Größe, Anfangs- und Endpositionen, Zuweisung und Zuweisung von Warteschlangenelementen usw. Darüber hinaus verfügen die Methoden queue.isEmpty() und queue.isFull () -Methoden lesen auch diesen gemeinsamen Zustand. Wenn Erzeuger-/Verbraucher-Threads während der Aufrufe zum Einreihen/Ausreihen aus der Warteschlange verschachtelt werden dürfen, kann ein inkonsistenter Zustand der Warteschlange offengelegt werden, was zu Racebedingungen führt. Wenn ein Verbraucher die Warteschlange leer macht, während ein anderer Verbraucher das Besetzt-Warten verlässt und "Warteschlange entfernen" aufruft, dann wird der zweite Verbraucher versuchen, aus einer leeren Warteschlange auszusteigen, was zu einem Fehler führt. Wenn ein Producer die Warteschlange voll macht, während ein anderer Producer das Besetzt-Warten verlässt und "enqueue" aufruft, dann wird der zweite Producer versuchen, zu einer vollen Warteschlange hinzuzufügen, was zu einem Fehler führt.

Spin-Wartezeit

Ein naiver Ansatz, um eine Synchronisation zu erreichen, wie oben erwähnt, ist die Verwendung von " Spin-Waiting ", bei dem ein Mutex verwendet wird, um die kritischen Abschnitte des Codes zu schützen und Busy-Waiting weiterhin verwendet wird, wobei die Sperre erworben und freigegeben wird zwischen jeder Besetzt-Warte-Prüfung. 

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 Zustand auftritt, verschwendet jedoch CPU-Ressourcen aufgrund des unnötigen Beschäftigt-Wartens. Selbst wenn die Warteschlange leer ist und Producer-Threads lange Zeit nichts hinzuzufügen haben, sind Consumer-Threads immer damit beschäftigt, unnötig zu warten. Auch wenn Consumer lange Zeit bei der Bearbeitung ihrer aktuellen Aufgaben blockiert sind und die Warteschlange voll ist, warten die Produzenten immer fleißig. Dies ist ein verschwenderischer Mechanismus. Was benötigt wird, ist eine Möglichkeit, Erzeuger-Threads zu blockieren, bis die Warteschlange nicht voll ist, und eine Möglichkeit, Verbraucher-Threads zu blockieren, bis die Warteschlange nicht leer ist.

(Hinweis: Mutexe selbst können auch Spin-Locks sein, die ein Beschäftigt -Warten beinhalten, um die Sperre zu erhalten, aber um dieses Problem der verschwendeten CPU-Ressourcen zu lösen, gehen wir davon aus, dass QueueLock kein Spin-Lock ist und eine Blockierung richtig verwendet Warteschlange selbst sperren.)

Bedingungsvariablen

Die Lösung besteht darin, Bedingungsvariablen zu verwenden . Eine Bedingungsvariable ist konzeptionell eine Warteschlange von Threads, die einem Mutex zugeordnet sind, in der ein Thread warten kann, bis eine Bedingung wahr wird. Somit ist jede Bedingungsvariable c einer Behauptung P c zugeordnet . Während ein Thread auf eine Bedingungsvariable wartet, wird davon ausgegangen, dass dieser Thread den Monitor nicht belegt, und daher können andere Threads den Monitor betreten, um den Status des Monitors zu ändern. Bei den meisten Arten von Monitoren können diese anderen Threads der Bedingungsvariablen c signalisieren, um anzuzeigen, dass die Behauptung P c im aktuellen Zustand wahr ist.

Somit gibt es drei Hauptoperationen für Bedingungsvariablen:

  • wait c, m, wobei ceine Bedingungsvariable und mein Mutex (Sperre) ist , der dem Monitor zugeordnet ist. Diese Operation wird von einem Thread aufgerufen, der warten muss, bis die Behauptung P c wahr ist, bevor er fortfährt. Während der Thread wartet, belegt er den Monitor nicht. Die Funktion und der grundlegende Vertrag der Operation "Warten" besteht darin, die folgenden Schritte auszuführen:
    1. Atomar :
      1. lass den Mutex los m,
      2. Verschieben Sie diesen Thread aus der "Running"- in cdie "Wait-Queue" (auch bekannt als "Sleep-Queue") von Threads, und
      3. schlafe diesen Thread. (Der Kontext wird synchron an einen anderen Thread übergeben.)
    2. Sobald dieser Thread anschließend benachrichtigt/signalisiert wird (siehe unten) und wieder aufgenommen wird, wird der Mutex automatisch erneut abgerufen m.
    Die Schritte 1a und 1b können in beliebiger Reihenfolge ausgeführt werden, wobei 1c normalerweise danach erfolgt. Während der Thread schläft und sich in cder Warte-Warteschlange befindet, befindet sich der nächste auszuführende Programmzähler bei Schritt 2, in der Mitte der "Wait"-Funktion/ Subroutine . Somit schläft der Thread und wacht später mitten in der "Warten"-Operation auf.
    Die Atomarität der Operationen in Schritt 1 ist wichtig, um Race-Conditions zu vermeiden, die durch einen präemptiven Threadwechsel dazwischen verursacht würden. Ein Fehlermodus , der auftreten könnte, wenn diese nicht atomar wären , ist ein verpasstes Aufwachen , bei dem sich der Thread in der cSleep-Warteschlange von befinden und den Mutex freigegeben haben könnte, aber ein präventiver Threadwechsel erfolgte, bevor der Thread in den Ruhezustand wechselte, und ein anderer Thread eine Signal-/Benachrichtigungsoperation (siehe unten) beim cZurückschieben des ersten Threads aus der cWarteschlange von aufgerufen . Sobald auf den ersten fraglichen Thread zurückgeschaltet wird, befindet sich sein Programmzähler auf Schritt 1c, und er schläft und kann nicht wieder aufgeweckt werden, wodurch die Invariante verletzt wird, dass er in der cSleep-Warteschlange von hätte sein sollen es hat geschlafen. Andere Race-Bedingungen hängen von der Reihenfolge der Schritte 1a und 1b ab und hängen davon ab, wo ein Kontextwechsel stattfindet.
  • signal c, auch bekannt als notify c, wird von einem Thread aufgerufen, um anzuzeigen, dass die Behauptung P c wahr ist. Je nach Typ und Implementierung des Monitors verschiebt dieser einen oder mehrere Threads aus cder Sleep-Queue von in die "Ready Queue" oder andere Warteschlangen, damit sie ausgeführt werden. Es wird normalerweise als bewährte Methode angesehen, den Vorgang "signal"/"notify" auszuführen, bevor der mmit verknüpfte Mutex freigegeben wird c, aber solange der Code ordnungsgemäß für die Parallelität ausgelegt ist und abhängig von der Threading-Implementierung, ist dies oft auch akzeptabel Entriegeln Sie die Sperre vor dem Signalisieren. Abhängig von der Threading-Implementierung kann die Reihenfolge davon Auswirkungen auf die Planungspriorität haben. (Einige Autoren plädieren stattdessen dafür, die Sperre vor der Signalisierung freizugeben.) Eine Threading-Implementierung sollte alle speziellen Einschränkungen dieser Reihenfolge dokumentieren.
  • broadcast c, auch bekannt als notifyAll c, ist eine ähnliche Operation, die alle Threads in der Warteschlange von c aufweckt. Dadurch wird die Warteschlange geleert. Wenn mehr als eine Prädikatsbedingung mit derselben Bedingungsvariablen verknüpft ist, erfordert die Anwendung im Allgemeinen Broadcast anstelle eines Signals, da ein Thread, der auf die falsche Bedingung wartet, möglicherweise aufgeweckt und dann sofort wieder in den Ruhezustand versetzt wird, ohne einen wartenden Thread aufzuwecken die richtige Bedingung, die gerade wahr geworden ist. Andernfalls, wenn die Prädikatsbedingung eins zu eins mit der ihr zugeordneten Bedingungsvariablen ist, dann kann signal effizienter sein als Broadcast .

Als Entwurfsregel können mehrere Bedingungsvariablen mit demselben Mutex verknüpft werden, aber nicht umgekehrt. (Dies ist eine Eins-zu-Viele- Entsprechung.) Dies liegt daran, dass das Prädikat P c für alle Threads, die den Monitor verwenden, gleich ist und unter gegenseitigem Ausschluss von allen anderen Threads geschützt werden muss, die eine Änderung der Bedingung verursachen könnten oder die möglicherweise Lesen Sie es, während der betreffende Thread die Änderung veranlasst, aber es kann verschiedene Threads geben, die auf eine andere Bedingung für dieselbe Variable warten möchten, die die Verwendung desselben Mutex erfordert. Im oben beschriebenen Producer-Consumer-Beispiel muss die Warteschlange durch ein eindeutiges Mutex-Objekt geschützt werden, m. Die "Produzenten"-Threads werden auf einem Monitor warten wollen, der eine Sperre mund eine Bedingungsvariable verwendet, die blockiert, bis die Warteschlange nicht voll ist. Die "Consumer"-Threads möchten auf einem anderen Monitor warten, der denselben Mutex, aber eine andere Bedingungsvariable verwendet, die blockiert, bis die Warteschlange nicht leer ist. Es wäre (normalerweise) nie sinnvoll, verschiedene Mutexe für dieselbe Bedingungsvariable zu haben, aber dieses klassische Beispiel zeigt, warum es oft durchaus 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 keine Bedingungsvariablen verwendet (und ihn einfach ohne Warte-/Signaloperationen erwirbt/freigibt), wenn diese kritischen Abschnitte nicht auftreten zu erfordern, auf eine bestimmte Bedingung für die gleichzeitigen Daten zu warten. m

Überwachen Sie die Nutzung

Die richtige 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 derselbe 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 beschränkten Produzenten-/Konsumentenproblems

Nachdem wir die Verwendung von Bedingungsvariablen eingeführt haben, verwenden wir sie, um das klassische beschränkte Producer/Consumer-Problem erneut zu betrachten und zu lösen. Die klassische Lösung besteht darin, zwei Monitore zu verwenden, die aus zwei Bedingungsvariablen bestehen, 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 Producer- und Consumer-Threads sicher, die sich die Aufgabenwarteschlange teilen, und blockiert die Threads, die nichts zu tun haben, anstatt beschäftigt zu warten, wie im oben genannten Ansatz mit Spin-Locks gezeigt.

Eine Variante dieser Lösung könnte eine einzige Bedingungsvariable sowohl für Produzenten als auch für Konsumenten verwenden, möglicherweise mit dem Namen "queueFullOrEmptyCV" oder "queueSizeChangedCV". In diesem Fall ist der Bedingungsvariable mehr als eine Bedingung zugeordnet, so dass die Bedingungsvariable eine schwächere Bedingung darstellt als die von einzelnen Threads geprüften Bedingungen. Die Bedingungsvariable stellt Threads dar, die darauf warten, dass die Warteschlange nicht voll ist, und Threads, die darauf warten, dass sie nicht leer ist. Dies würde jedoch die Verwendung von noticeAll in allen Threads erfordern, die die Bedingungsvariable verwenden, und kann kein reguläres Signal verwenden . Dies liegt daran, dass das reguläre Signal möglicherweise einen Thread des falschen Typs aufweckt, dessen Bedingung noch nicht erfüllt ist, und dieser Thread würde wieder in den Ruhezustand zurückkehren, ohne dass ein Thread des richtigen Typs signalisiert wird. Ein Producer könnte beispielsweise die Warteschlange voll machen und einen anderen Producer anstelle eines Consumers aufwecken, und der aufgeweckte Producer würde wieder schlafen gehen. Im komplementären Fall könnte ein Verbraucher die Warteschlange leer machen und einen anderen Verbraucher anstelle eines Produzenten aufwecken, und der Verbraucher würde wieder schlafen gehen. Durch die Verwendung von notificationAll wird sichergestellt, dass ein Thread des richtigen Typs wie von der Problemanweisung erwartet ausgeführt wird.

Hier ist die Variante, die nur eine Bedingungsvariable und notificationAll 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.
    }
}

Synchronisierungsprimitive

Das Implementieren von Mutexes und Bedingungsvariablen erfordert eine Art von Synchronisationsprimitiven, die von der Hardwareunterstützung bereitgestellt werden, die Atomizität bietet . Sperren und Bedingungsvariablen sind Abstraktionen auf höherer Ebene über diese Synchronisationsprimitiven. Auf einem Einzelprozessor 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, aber dies ist auf einem Multiprozessor nicht ausreichend. Auf einem Multiprozessor werden normalerweise spezielle atomare Read-Modify-Write- Befehle wie test-and-set , Compare-and-Swap usw. verwendet, je nachdem, was der ISA bereitstellt. Diese erfordern normalerweise das Aufschieben des Spin-Locking für den internen Lock-Zustand selbst, aber dieses Locking ist sehr kurz. Abhängig von der Implementierung können die atomaren Lese-Modifizier-Schreib-Befehle den Bus vor Zugriffen anderer Kerne sperren und/oder eine Neuordnung von Befehlen in der CPU verhindern. Hier ist ein Beispiel einer Pseudocode-Implementierung von Teilen eines Threading-Systems und von Mutexes und Bedingungsvariablen im Mesa-Stil unter Verwendung von Test-and-Set und einer First-Come-First-Served-Richtlinie. Dies beschönigt den Großteil der Funktionsweise eines Threading-Systems, zeigt jedoch die Teile, die für Mutexe und Bedingungsvariablen relevant sind:

Beispielimplementierung eines Mesa-Monitors mit Test-and-Set

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

Betrachten Sie als Beispiel eine threadsichere Klasse, die einen 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 ganze Zahl positiv ist. Wir verwenden eine Bedingungsvariable sIsPositivemit einer zugehörigen Assertion von . 

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
    }
}

Implementiert, um alle Synchronisationen anzuzeigen (die Annahme einer threadsicheren Klasse wird entfernt und der Mutex angezeigt): 

class Semaphore
{
    private volatile int s := 0
    invariant s >= 0
    private ConditionVariable sIsPositive /* associated with s > 0 */
    private Mutex myLock /* Lock on "s" */

    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

Umgekehrt können aus Semaphoren auch Sperren und Bedingungsvariablen abgeleitet werden, wodurch Monitore und Semaphoren aufeinander reduziert werden können:

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 inkrementiert, wie bereits wartende Threads sind. 

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 an einer Bedingungsvariablen auftritt, auf die mindestens ein anderer Thread wartet, gibt es mindestens zwei Threads, die den Monitor belegen könnten: der Thread, der das Signal sendet, und einer der wartenden Threads. Damit zu jedem Zeitpunkt höchstens ein Thread den Monitor belegt, muss eine Auswahl getroffen werden. Es gibt zwei Denkschulen, wie man diese Wahl am besten lösen kann. Dies führt zu zwei Arten von Bedingungsvariablen, die als nächstes untersucht werden:

  • Das Blockieren von Bedingungsvariablen gibt einem signalisierten Thread Priorität.
  • Nicht blockierende Bedingungsvariablen geben dem Signalisierungs-Thread Priorität.

Bedingungsvariablen blockieren

Die ursprünglichen Vorschläge von CAR Hoare und Per Brinch Hansen waren für Bedingungsvariablen blockiert . Bei einer blockierenden Bedingungsvariablen muss der signalisierende Thread (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 oft als Hoare- Monitore oder Signal-und-Dringend-Warte- Monitore bezeichnet.

Ein Monitor im Hoare-Stil mit zwei Bedingungsvariablen aund b. Nachdem Buhr et al.

Wir gehen davon aus, dass jedem Monitorobjekt zwei Warteschlangen von Threads zugeordnet sind

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

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

  • c.q, das ist eine Warteschlange für Threads, die auf die Bedingungsvariable c . warten

Für alle Warteschlangen wird normalerweise garantiert, dass sie fair sind, und in einigen Implementierungen kann garantiert werden, dass sie First-in-First-out sind .

Die Implementierung jeder Operation ist wie folgt. (Wir gehen davon aus, dass jede Operation unter gegenseitigem Ausschluss der anderen ausgeführt wird; daher beginnen neu gestartete Threads nicht mit der Ausführung, bis 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)

Die scheduleRoutine wählt den nächsten Thread aus, um den Monitor zu belegen, oder entsperrt den Monitor, wenn keine Kandidaten-Threads vorhanden sind.

Die resultierende Signalisierungsdisziplin ist als "Signal and dringendes Warten" bekannt, da der Signalgeber warten muss, aber Priorität gegenüber Threads in der Eingangswarteschlange erhält. Eine Alternative ist "Signal and Wait", bei der es keine sWarteschlange gibt und der Signalgeber estattdessen in der Warteschlange wartet .

Einige Implementierungen stellen eine Signal- und Rückkehroperation bereit , 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 "Signal und Warten"), wenn eine Bedingungsvariable signalisiert wird und mindestens ein Thread auf die Bedingungsvariable wartet, übergibt der signalisierende Thread die Belegung nahtlos an den signalisierten Thread, also dass kein anderer Thread dazwischen Platz gewinnen kann. Wenn P c zu Beginn jeder Signal- c- Operation wahr ist, ist es am Ende jeder Warte- c- Operation wahr . Dies wird durch die folgenden Verträge zusammengefasst . In diesen Verträgen ist I 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 Pc and I

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

signal c and return:
    precondition Pc and I

In diesen Verträgen wird angenommen, dass I und P c nicht vom Inhalt oder der Länge irgendwelcher Warteschlangen abhängen.

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

wait c:
    precondition I
    modifies the state of the monitor
    postcondition Pc

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

(Siehe Howard und Buhr et al. für mehr.)

Es ist hier wichtig zu beachten, dass die Behauptung P c vollständig dem Programmierer überlassen bleibt; er oder sie muss einfach konsistent sein, was es ist.

Wir schließen diesen Abschnitt mit einem Beispiel für eine threadsichere Klasse ab, die einen Blockierungsmonitor verwendet, der einen begrenzten, threadsicheren Stack 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 Stack intern einen Mutex bereitstellt, der wie im früheren Producer/Consumer-Beispiel von beiden Bedingungsvariablen geteilt wird, die unterschiedliche Bedingungen für dieselben gleichzeitigen Daten prüfen. Der einzige Unterschied besteht darin, dass das Producer/Consumer-Beispiel von einer regulären, nicht Thread-sicheren Warteschlange ausgegangen ist und einen eigenständigen Mutex und Bedingungsvariablen verwendet, ohne dass diese Details des Monitors wie hier abstrahiert werden. Wenn in diesem Beispiel die Operation "wait" aufgerufen wird, muss sie irgendwie mit dem Mutex des Thread-sicheren Stapels versorgt werden, beispielsweise wenn die Operation "wait" ein integrierter Bestandteil der "Monitor-Klasse" ist. Abgesehen von dieser Art von abstrahierter Funktionalität muss ein "roher" Monitor immer einen Mutex und eine Bedingungsvariable enthalten, mit einem eindeutigen Mutex für jede Bedingungsvariable.

Nichtblockierende Bedingungsvariablen

Bei nicht blockierenden Bedingungsvariablen (auch als "Mesa-Style" -Bedingungsvariablen oder "Signal and Continue " -Bedingungsvariablen bezeichnet) führt die Signalisierung nicht dazu, dass der Signalisierungs-Thread die Belegung des Monitors verliert. Stattdessen werden die signalisierten Threads in die eWarteschlange verschoben . Die sWarteschlange ist nicht erforderlich .

Ein Monitor im Mesa-Stil mit zwei Bedingungsvariablen aundb

Bei nicht - blockierenden Zustandsgrößen, das Signal wird Betrieb oft genannt benachrichtigen - eine Terminologie , die wir hier folgen. Es ist auch üblich, eine Benachrichtigungsoperation bereitzustellen , die alle Threads, die auf eine Bedingungsvariable warten, in die eWarteschlange verschiebt.

Die Bedeutung der verschiedenen Operationen wird hier angegeben. (Wir gehen davon aus, dass jede Operation unter gegenseitigem Ausschluss der anderen ausgeführt wird; daher beginnen neu gestartete Threads nicht mit der Ausführung, bis 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 Warteschlange mit dem Namen verschoben werden w, die Priorität gegenüber hat e. Siehe Howard und Buhr et al. zur weiteren Diskussion.

Es ist möglich, jeder Bedingungsvariablen c eine Zusicherung P c zuzuordnen, so dass P c bei der Rückkehr von sicher wahr ist . Allerdings muss man dafür sorgen , dass P c aus der Zeit, wird das mitteilen ing Fadenbelegung gibt , bis der benannte Thread wieder in den Monitor ausgewählt ist. Zwischen diesen Zeiten kann es zu Aktivitäten anderer Bewohner kommen. Daher ist es üblich, dass P c einfach wahr ist . wait c

Aus diesem Grund ist es normalerweise notwendig, jede Warteoperation in eine Schleife wie diese einzuschließen

while not( P ) do
    wait c

wobei P eine Bedingung ist, die stärker ist als P c . Die Operationen und werden als "Hinweise" behandelt, dass P für einen wartenden Thread wahr sein kann. Jede Iteration einer solchen Schleife nach der ersten repräsentiert eine verlorene Benachrichtigung; Daher muss bei nicht blockierenden Monitoren darauf geachtet werden, dass nicht zu viele Benachrichtigungen verloren gehen. notify cnotify all c

Betrachten Sie als Beispiel für "Hinweise" ein Bankkonto, bei dem ein abhebender Thread wartet, bis das Konto über ausreichende Mittel verfügt, bevor er fortfährt 

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 abzuhebenden Betrags, so dass es für einen einzahlenden Thread unmöglich ist zu wissen, dass er eine solche Bedingung wahr gemacht hat. In diesem Fall ist es sinnvoll, jeden wartenden Thread (einer nach dem anderen) in den Monitor zu lassen, um zu überprüfen, ob seine Behauptung wahr ist.

Implizite Zustandsvariablenmonitore

Ein Monitor im Java-Stil

In der Sprache Java kann jedes Objekt als Monitor verwendet werden. Methoden, die einen gegenseitigen Ausschluss erfordern, müssen explizit mit dem Schlüsselwort synchronisiert gekennzeichnet werden . Codeblöcke können auch durch synchronisierte markiert werden .

Anstatt explizite Bedingungsvariablen zu haben, ist jeder Monitor (dh jedes Objekt) zusätzlich zu seiner Eingangswarteschlange mit einer einzigen Warteschlange ausgestattet. Alle Wartezeiten werden in dieser einzelnen Warteschlange ausgeführt, und alle Operationen benachrichtigen und benachrichtigenAll gelten für diese Warteschlange. Dieser Ansatz wurde in anderen Sprachen übernommen, beispielsweise in C# .

Implizite Signalisierung

Ein weiterer Ansatz zur Signalisierung ist der wegzulassen Signalbetrieb. Immer wenn ein Thread den Monitor verlässt (durch Zurückkehren oder Warten), werden die Assertionen aller wartenden Threads ausgewertet, bis einer als wahr befunden wird. In einem solchen System werden keine Bedingungsvariablen benötigt, aber die Zusicherungen müssen explizit codiert werden. Der Wartevertrag ist 

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

Geschichte

Brinch Hansen und Hoare entwickelten das Monitorkonzept Anfang der 1970er Jahre, basierend auf früheren eigenen Ideen und von Edsger Dijkstra . Brinch Hansen veröffentlichte die erste Monitornotation, übernahm das Klassenkonzept von Simula 67 und erfand einen Warteschlangenmechanismus. Hoare verfeinerte die Regeln für die Wiederaufnahme des Prozesses. Brinch Hansen hat die erste Implementierung von Monitoren in Concurrent Pascal erstellt . Hoare demonstrierte ihre Äquivalenz zu Semaphoren .

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

Zu den Programmiersprachen mit unterstützten Monitoren gehören:

Es wurden eine Reihe von Bibliotheken geschrieben, die es ermöglichen, Monitore in Sprachen zu erstellen, die sie nicht nativ unterstützen. Bei Bibliotheksaufrufen ist es Sache des Programmierers, Start und Ende des ausgeführten Codes unter gegenseitigem Ausschluss explizit zu markieren. Pthreads ist eine solche Bibliothek.

Siehe auch

Anmerkungen

Weiterlesen

Externe Links