[{"@context":"http:\/\/schema.org\/","@type":"BlogPosting","@id":"https:\/\/wiki.edu.vn\/wiki18\/2020\/12\/31\/monitor-synchronisation-wikipedia\/#BlogPosting","mainEntityOfPage":"https:\/\/wiki.edu.vn\/wiki18\/2020\/12\/31\/monitor-synchronisation-wikipedia\/","headline":"Monitor (Synchronisation) – Wikipedia","name":"Monitor (Synchronisation) – Wikipedia","description":"before-content-x4 Bei der gleichzeitigen Programmierung (auch als parallele Programmierung bezeichnet) a Monitor ist ein Synchronisationskonstrukt, das es Threads erm\u00f6glicht, sich","datePublished":"2020-12-31","dateModified":"2020-12-31","author":{"@type":"Person","@id":"https:\/\/wiki.edu.vn\/wiki18\/author\/lordneo\/#Person","name":"lordneo","url":"https:\/\/wiki.edu.vn\/wiki18\/author\/lordneo\/","image":{"@type":"ImageObject","@id":"https:\/\/secure.gravatar.com\/avatar\/44a4cee54c4c053e967fe3e7d054edd4?s=96&d=mm&r=g","url":"https:\/\/secure.gravatar.com\/avatar\/44a4cee54c4c053e967fe3e7d054edd4?s=96&d=mm&r=g","height":96,"width":96}},"publisher":{"@type":"Organization","name":"Enzyklop\u00e4die","logo":{"@type":"ImageObject","@id":"https:\/\/wiki.edu.vn\/wiki4\/wp-content\/uploads\/2023\/08\/download.jpg","url":"https:\/\/wiki.edu.vn\/wiki4\/wp-content\/uploads\/2023\/08\/download.jpg","width":600,"height":60}},"image":{"@type":"ImageObject","@id":"https:\/\/wikimedia.org\/api\/rest_v1\/media\/math\/render\/svg\/488f6823f7546dbbcf1ad23afad080383b2755ae","url":"https:\/\/wikimedia.org\/api\/rest_v1\/media\/math\/render\/svg\/488f6823f7546dbbcf1ad23afad080383b2755ae","height":"","width":""},"url":"https:\/\/wiki.edu.vn\/wiki18\/2020\/12\/31\/monitor-synchronisation-wikipedia\/","wordCount":18176,"articleBody":" (adsbygoogle = window.adsbygoogle || []).push({});before-content-x4Bei der gleichzeitigen Programmierung (auch als parallele Programmierung bezeichnet) a Monitor ist ein Synchronisationskonstrukt, das es Threads erm\u00f6glicht, sich gegenseitig auszuschlie\u00dfen 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\u00fcllt 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\u00fcr Threads, um den exklusiven Zugriff vor\u00fcbergehend aufzugeben, um zu warten, bis eine bestimmte Bedingung erf\u00fcllt 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\u00dft, um mehr als einem Thread den sicheren Zugriff auf eine Methode oder Variable zu erm\u00f6glichen. Das definierende Merkmal eines Monitors ist, dass seine Methoden unter gegenseitigem Ausschluss ausgef\u00fchrt werden: Zu jedem Zeitpunkt kann h\u00f6chstens ein Thread eine seiner Methoden ausf\u00fchren. Durch die Verwendung einer oder mehrerer Bedingungsvariablen k\u00f6nnen Threads auch auf eine bestimmte Bedingung warten (wobei die obige Definition von a verwendet wird) “Monitor”). F\u00fcr 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]Table of Contents Gegenseitiger Ausschluss[edit]Bedingungsvariablen[edit]Problemstellung[edit]Fallstudie: Klassisches Problem zwischen Produzenten und Verbrauchern[edit]Ohne Synchronisation falsch[edit]Spin-Warten[edit]Bedingungsvariablen[edit]\u00dcberwachen Sie die Nutzung[edit]L\u00f6sung des begrenzten Produzenten- \/ Konsumentenproblems[edit]Synchronisationsprimitive[edit]Beispiel f\u00fcr 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\u00fchrende Literatur[edit]Externe Links[edit]Gegenseitiger Ausschluss[edit]Betrachten Sie als einfaches Beispiel ein threadsicheres Objekt zum Ausf\u00fchren von Transaktionen auf einem Bankkonto:monitor class Account { private int balance\u00a0:= 0 invariant balance >= 0 public method boolean withdraw(int amount) precondition amount >= 0 { if balance < amount { return false } else { balance\u00a0:= balance - amount return true } } public method deposit(int amount) precondition amount >= 0 { balance\u00a0:= balance + amount }}W\u00e4hrend ein Thread eine Methode eines thread-sicheren Objekts ausf\u00fchrt, 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\u00f6chstens ein Thread das Objekt belegen. Die Sperre, die anf\u00e4nglich entsperrt ist, wird zu Beginn jeder \u00f6ffentlichen Methode gesperrt und bei jeder R\u00fcckkehr von jeder \u00f6ffentlichen Methode entsperrt.Beim Aufrufen einer der Methoden muss ein Thread warten, bis kein anderer Thread eine der Methoden des thread-sicheren Objekts ausf\u00fchrt, bevor er mit der Ausf\u00fchrung seiner Methode beginnt. Beachten Sie, dass ohne diesen gegenseitigen Ausschluss im vorliegenden Beispiel zwei Threads dazu f\u00fchren k\u00f6nnen, dass Geld ohne Grund verloren geht oder gewonnen wird. Zum Beispiel k\u00f6nnten zwei Threads, die 1000 vom Konto abheben, beide true zur\u00fcckgeben, w\u00e4hrend der Kontostand wie folgt nur um 1000 sinkt: Zuerst rufen beide Threads den aktuellen Kontostand ab, finden ihn gr\u00f6\u00dfer als 1000 und subtrahieren 1000 davon; Dann speichern beide Threads den Saldo und kehren zur\u00fcck.Der syntaktische Zucker “Klasse \u00fcberwachen” Im obigen Beispiel wird die folgende grundlegende Darstellung des Codes implementiert, indem die Ausf\u00fchrung jeder Funktion in Mutexe eingeschlossen wird: class Account { private lock myLock private int balance\u00a0:= 0 invariant balance >= 0 public method boolean withdraw(int amount) precondition amount >= 0 { myLock.acquire() try { if balance < amount { return false } else { balance\u00a0:= balance - amount return true } } finally { myLock.release() } } public method deposit(int amount) precondition amount >= 0 { myLock.acquire() try { balance\u00a0:= balance + amount } finally { myLock.release() } }}Bedingungsvariablen[edit]Problemstellung[edit]F\u00fcr viele Anwendungen reicht ein gegenseitiger Ausschluss nicht aus. Threads, die eine Operation versuchen, m\u00fcssen m\u00f6glicherweise bis zu einem bestimmten Zustand warten P. gilt wahr. Eine gesch\u00e4ftige Warteschleifewhile not( P ) do skipfunktioniert nicht, da durch gegenseitigen Ausschluss verhindert wird, dass andere Threads in den Monitor gelangen, um die Bedingung zu erf\u00fcllen. Andere “L\u00f6sungen” Es gibt beispielsweise eine Schleife, die den Monitor entsperrt, eine bestimmte Zeit wartet, den Monitor sperrt und den Zustand \u00fcberpr\u00fcft 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\u00df und reagiert anscheinend nicht mehr. Was ben\u00f6tigt wird, ist eine M\u00f6glichkeit, den Thread zu signalisieren, wenn die Bedingung P wahr ist (oder k\u00f6nnten wahr sein).Fallstudie: Klassisches Problem zwischen Produzenten und Verbrauchern[edit]Ein klassisches Parallelit\u00e4tsproblem ist das der gebundener Produzent \/ Konsument, in dem sich eine Warteschlange oder ein Ringpuffer mit Aufgaben mit maximaler Gr\u00f6\u00dfe befindet, wobei sich ein oder mehrere Threads befinden “Produzent” Threads, die der Warteschlange Aufgaben hinzuf\u00fcgen, 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\u00fcssen die Producer-Threads blockiert werden, bis Platz f\u00fcr die Dequeueing-Aufgaben von Consumer-Threads vorhanden ist. Wenn andererseits die Warteschlange leer ist, m\u00fcssen die Consumer-Threads blockiert werden, bis mehr Aufgaben verf\u00fcgbar sind, da Producer-Threads sie hinzuf\u00fcgen.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\u00f6nnten verschachtelt durch willk\u00fcrliche Kontextwechsel Zwischen Threads auf demselben Prozessor oder durch gleichzeitiges Ausf\u00fchren 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\u00e4ftigt 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\u00f6nnen. Das queue.enqueue und queue.dequeue Methoden haben wahrscheinlich Anweisungen zum Aktualisieren der Mitgliedsvariablen der Warteschlange, wie z. B. Gr\u00f6\u00dfe, 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\u00e4hrend der Aufrufe zum Enqueue \/ Dequeue verschachtelt werden d\u00fcrfen, kann ein inkonsistenter Status der Warteschlange angezeigt werden, was zu Race-Bedingungen f\u00fchrt. 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\u00fchrt. 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\u00e4ndige Warteschlange hinzuzuf\u00fcgen, was zu einem Fehler f\u00fchrt.Spin-Warten[edit]Ein naiver Ansatz, um eine Synchronisation zu erreichen, wie oben erw\u00e4hnt, 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\u00fcfung 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\u00f6tigen Wartens. Selbst wenn die Warteschlange leer ist und Producer-Threads lange Zeit nichts hinzuzuf\u00fcgen haben, warten Consumer-Threads immer unn\u00f6tig. Auch wenn die Verbraucher bei der Bearbeitung ihrer aktuellen Aufgaben f\u00fcr l\u00e4ngere Zeit blockiert sind und die Warteschlange voll ist, warten die Hersteller immer. Dies ist ein verschwenderischer Mechanismus. Was ben\u00f6tigt wird, ist eine M\u00f6glichkeit, Produzenten-Threads zu blockieren, bis die Warteschlange nicht mehr voll ist, und eine M\u00f6glichkeit, Consumer-Threads zu blockieren, bis die Warteschlange nicht leer ist.(NB: Mutexe selbst k\u00f6nnen es auch sein Spin-Locks Wir m\u00fcssen davon ausgehen, dass wir viel warten m\u00fcssen, um die Sperre zu erhalten. Um dieses Problem der verschwendeten CPU-Ressourcen zu l\u00f6sen, gehen wir davon aus queueLock ist keine Spin-Sperre und verwendet ordnungsgem\u00e4\u00df eine Blockierungssperre selbst.)Bedingungsvariablen[edit]Die L\u00f6sung ist zu verwenden Bedingungsvariablen. Konzeptionell ist eine Bedingungsvariable eine Warteschlange von Threads, die einem Monitor zugeordnet sind und in der ein Thread m\u00f6glicherweise darauf wartet, dass eine Bedingung erf\u00fcllt wird. Also jede Bedingungsvariable c ist mit einer Behauptung verbunden P.c. W\u00e4hrend ein Thread auf eine Bedingungsvariable wartet, wird nicht davon ausgegangen, dass dieser Thread den Monitor belegt. Daher k\u00f6nnen andere Threads in den Monitor eintreten, um den Status des Monitors zu \u00e4ndern. Bei den meisten Monitortypen k\u00f6nnen diese anderen Threads die Bedingungsvariable signalisieren c um diese Behauptung anzuzeigen P.c ist im aktuellen Zustand wahr.Somit gibt es drei Hauptoperationen f\u00fcr 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\u00e4tigung warten muss P.c ist wahr, bevor Sie fortfahren. W\u00e4hrend der Thread wartet, belegt er den Monitor nicht. Die Funktion und der Grundvertrag der “warten” Betrieb ist, die folgenden Schritte auszuf\u00fchren:Atomar:Lassen Sie den Mutex los m,Bewegen Sie diesen Thread aus dem “Laufen” zu c‘s “Warteschlange” (aka “Schlaf-Warteschlange”) von F\u00e4den undschlaf diesen Thread. (Der Kontext wird synchron zu einem anderen Thread ausgegeben.)Sobald dieser Thread anschlie\u00dfend benachrichtigt \/ signalisiert (siehe unten) und wieder aufgenommen wurde, wird der Mutex automatisch neu erfasst m.Die Schritte 1a und 1b k\u00f6nnen in beliebiger Reihenfolge erfolgen, wobei 1c normalerweise danach erfolgt. W\u00e4hrend der Thread schl\u00e4ft und in cIn der Warteschlange befindet sich der n\u00e4chste auszuf\u00fchrende Programmz\u00e4hler in Schritt 2 in der Mitte des “warten” Funktion \/ Unterprogramm. Somit schl\u00e4ft der Faden und wacht sp\u00e4ter in der Mitte des auf “warten” Betrieb.Die Atomizit\u00e4t der Operationen in Schritt 1 ist wichtig, um Rennbedingungen zu vermeiden, die durch einen vorbeugenden Threadwechsel zwischen ihnen verursacht w\u00fcrden. Ein Fehlermodus, der auftreten k\u00f6nnte, wenn diese nicht atomar w\u00e4ren, ist a verpasstes Aufwachen, in dem der Thread laufen k\u00f6nnte 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\u00e4hler in Schritt 1c, und er schl\u00e4ft und kann nicht wieder geweckt werden, wodurch die Invariante verletzt wird, die er h\u00e4tte aktivieren sollen cist Schlafschlange, wenn es geschlafen hat. Andere Rennbedingungen h\u00e4ngen 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\u00fchrt werden kann. Es wird normalerweise als bew\u00e4hrte Methode angesehen, die “Signal”\/.”benachrichtigen” Betrieb vor dem Loslassen von Mutex m das ist verbunden mit cSolange der Code jedoch ordnungsgem\u00e4\u00df f\u00fcr die Parallelit\u00e4t ausgelegt ist und von der Threading-Implementierung abh\u00e4ngt, ist es h\u00e4ufig auch akzeptabel, die Sperre vor der Signalisierung aufzuheben. Abh\u00e4ngig von der Threading-Implementierung kann die Reihenfolge davon Auswirkungen auf die Planungspriorit\u00e4t haben. (Einige Autoren[who?] Bef\u00fcrworten Sie stattdessen die Aufhebung der Sperre vor dem Signalisieren.) Eine Threading-Implementierung sollte alle besonderen Einschr\u00e4nkungen dieser Reihenfolge dokumentieren.broadcast c, auch bekannt als notifyAll cist eine \u00e4hnliche Operation, die alle Threads in der Warteschlange von c aufweckt. Dadurch wird die Warteschlange geleert. Wenn mehr als eine Pr\u00e4dikatbedingung derselben Bedingungsvariablen zugeordnet ist, erfordert die Anwendung im Allgemeinen \u00dcbertragung Anstatt von Signal weil ein Thread, der auf den falschen Zustand wartet, m\u00f6glicherweise 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\u00e4dikatbedingung eins zu eins mit der damit verbundenen Bedingungsvariablen ist, dann Signal kann effizienter sein als \u00dcbertragung.Als Entwurfsregel k\u00f6nnen mehrere Bedingungsvariablen demselben Mutex zugeordnet werden, jedoch nicht umgekehrt. (Dies ist eine Eins-zu-Viele-Entsprechung.) Dies liegt am Pr\u00e4dikat P.c ist f\u00fcr alle Threads, die den Monitor verwenden, gleich und muss unter gegenseitigem Ausschluss von allen anderen Threads gesch\u00fctzt werden, die m\u00f6glicherweise zu einer \u00c4nderung der Bedingung f\u00fchren oder diese lesen, w\u00e4hrend der betreffende Thread eine \u00c4nderung bewirkt, es k\u00f6nnen jedoch unterschiedliche Threads vorhanden sein die auf eine andere Bedingung f\u00fcr dieselbe Variable warten m\u00f6chten, f\u00fcr die derselbe Mutex verwendet werden muss. In dem oben beschriebenen Producer-Consumer-Beispiel muss die Warteschlange durch ein eindeutiges Mutex-Objekt gesch\u00fctzt werden. m. Das “Produzent” Threads m\u00f6chten mit Lock auf einem Monitor warten m und eine Bedingungsvariable cfull{ displaystyle c_ {full}} die blockiert, bis die Warteschlange nicht mehr voll ist. Das “Verbraucher” Threads m\u00f6chten mit demselben Mutex auf einem anderen Monitor warten m aber eine andere Bedingungsvariable cempty{ displaystyle c_ {leer}} die blockiert, bis die Warteschlange nicht leer ist. Es w\u00e4re (normalerweise) nie sinnvoll, unterschiedliche Mutexe f\u00fcr 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\u00fcr die gleichzeitigen Daten erfordern.\u00dcberwachen Sie die Nutzung[edit]Die ordnungsgem\u00e4\u00dfe 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...\twait(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\u00fchrlicheren Kommentaren, um besser zu erkl\u00e4ren, 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()) \t\/\/ \"p\" is any expression (e.g. variable or \t\t\/\/ function-call) that checks the condition and\t\t\/\/ evaluates to boolean. This itself is a critical\t\t\/\/ section, so you *MUST* be holding the lock when\t\t\/\/ executing this \"while\" loop condition!\t\t\t\t\/\/ 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?{\t\/\/ If this is the first iteration of the loop, then the answer is\t\/\/ \"no\" -- the condition is not ready yet. Otherwise, the answer is:\t\/\/ the latter. This was a spurious wakeup, some other thread occurred\t\/\/ first and caused the condition to become false again, and we must\t\/\/ wait again.\twait(m, cv);\t\t\/\/ Temporarily prevent any other thread on any core from doing\t\t\/\/ operations on m or cv.\t\t\/\/ release(m) \t\t\/\/ Atomically release lock \"m\" so other\t\t\/\/\t\t\t\/\/ code using this concurrent data\t\t\/\/ \t\t\t\/\/ can operate, move this thread to cv's\t\t\/\/\t\t\t\/\/ wait-queue so that it will be notified\t\t\/\/\t\t\t\/\/ sometime when the condition becomes\t\t\/\/ \t\t\t\/\/ true, and sleep this thread. Re-enable\t\t\/\/\t\t\t\/\/ other threads and cores to do \t\t\/\/\t\t\t\/\/ operations on m and cv.\t\t\/\/\t\t\/\/ Context switch occurs on this core.\t\t\/\/\t\t\/\/ At some future time, the condition we are waiting for becomes\t\t\/\/ true, and another thread using this monitor (m, cv) does either\t\t\/\/ a signal\/notify that happens to wake this thread up, or a\t\t\/\/ notifyAll that wakes us up, meaning that we have been taken out\t\t\/\/ of cv's wait-queue.\t\t\/\/\t\t\/\/ During this time, other threads may cause the condition to\t\t\/\/ become false again, or the condition may toggle one or more\t\t\/\/ times, or it may happen to stay true.\t\t\/\/\t\t\/\/ This thread is switched back to on some core.\t\t\/\/\t\t\/\/ acquire(m)\t\t\/\/ Lock \"m\" is re-acquired.\t\t\t\/\/ End this loop iteration and re-check the \"while\" loop condition to make\t\/\/ sure the predicate is still true.\t}\/\/ 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) {\tnotify(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\u00f6sung des begrenzten Produzenten- \/ Konsumentenproblems[edit]Nachdem wir die Verwendung von Bedingungsvariablen eingef\u00fchrt haben, wollen wir sie verwenden, um das klassische Problem des begrenzten Produzenten \/ Konsumenten erneut zu untersuchen und zu l\u00f6sen. Die klassische L\u00f6sung 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; \t\/\/ A mutex for the ring-buffer of tasks. (Not a spin-lock.)global CV queueEmptyCV; \t\/\/ A condition variable for consumer threads waiting for the queue to \t\t\t\t\/\/ become non-empty. \t\/\/ Its associated lock is \"queueLock\".global CV queueFullCV; \t\t\/\/ A condition variable for producer threads waiting for the queue \t\t\t\t\/\/ 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\u00e4t 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\u00f6sung k\u00f6nnte eine einzige Bedingungsvariable f\u00fcr Hersteller und Verbraucher verwenden, die m\u00f6glicherweise benannt wird “queueFullOrEmptyCV” oder “queueSizeChangedCV”. In diesem Fall ist der Bedingungsvariablen mehr als eine Bedingung zugeordnet, sodass die Bedingungsvariable eine schw\u00e4chere Bedingung darstellt als die Bedingungen, die von einzelnen Threads \u00fcberpr\u00fcft werden. Die Bedingungsvariable repr\u00e4sentiert Threads, die darauf warten, dass die Warteschlange nicht voll ist und diejenigen, die darauf warten, dass es nicht leer ist. Dies w\u00fcrde jedoch die Verwendung erfordern notifyAll in allen Threads, die die Bedingungsvariable verwenden und keine regul\u00e4re verwenden k\u00f6nnen Signal. Dies liegt daran, dass die regelm\u00e4\u00dfige Signal M\u00f6glicherweise wird ein Thread des falschen Typs aktiviert, dessen Bedingung noch nicht erf\u00fcllt ist, und dieser Thread wird wieder in den Ruhezustand versetzt, ohne dass ein Thread des richtigen Typs signalisiert wird. Zum Beispiel k\u00f6nnte ein Produzent die Warteschlange voll machen und einen anderen Produzenten anstelle eines Verbrauchers wecken, und der aufgeweckte Produzent w\u00fcrde wieder einschlafen. Im erg\u00e4nzenden Fall k\u00f6nnte ein Verbraucher die Warteschlange leer machen und einen anderen Verbraucher anstelle eines Herstellers wecken, und der Verbraucher w\u00fcrde wieder einschlafen. Verwenden von notifyAll stellt sicher, dass ein Thread des richtigen Typs wie von der Problemstellung erwartet ausgef\u00fchrt 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\u00fctzung bereitgestellt wird und Atomizit\u00e4t bietet. Sperren und Bedingungsvariablen sind \u00fcbergeordnete Abstraktionen \u00fcber diese Synchronisationsprimitive. Auf einem Uniprozessor ist das Deaktivieren und Aktivieren von Interrupts eine M\u00f6glichkeit, Monitore zu implementieren, indem Kontextwechsel w\u00e4hrend der kritischen Abschnitte der Sperren und Bedingungsvariablen verhindert werden. Auf einem Multiprozessor reicht dies jedoch nicht aus. Auf einem Multiprozessor normalerweise spezielles Atom Lesen-\u00c4ndern-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\u00fcr den internen Verriegelungszustand selbst, aber diese Verriegelung ist sehr kurz. Abh\u00e4ngig von der Implementierung k\u00f6nnen die atomaren Lese-, \u00c4nderungs- und Schreibbefehle den Bus f\u00fcr die Zugriffe anderer Kerne sperren und \/ oder die Neuordnung von Befehlen in der CPU verhindern. Hier ist ein Beispiel f\u00fcr 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\u00f6nigt den gr\u00f6\u00dften Teil der Funktionsweise eines Threading-Systems, zeigt jedoch die Teile, die f\u00fcr Mutexe und Bedingungsvariablen relevant sind:Beispiel f\u00fcr 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 0)}”\/>.monitor class Semaphore{ private int s\u00a0:= 0 invariant s >= 0 private Condition sIsPositive \/* associated with s > 0 *\/ public method P() { while s = 0: wait sIsPositive assert s > 0 s\u00a0:= s - 1 } public method V() { s\u00a0:= s + 1 assert s > 0 signal sIsPositive }}Implementiert, um die gesamte Synchronisation anzuzeigen (Entfernen der Annahme einer thread-sicheren Klasse und Anzeigen des Mutex):class Semaphore{ private volatile int s\u00a0:= 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\u00a0:= s - 1 myLock.release() } public method V() { myLock.acquire() s\u00a0:= s + 1 assert s > 0 signal sIsPositive myLock.release() }}Monitor implementiert mit Semaphoren[edit]Umgekehrt k\u00f6nnen 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\u00fcnglicher Thread auf unbestimmte Zeit h\u00e4ngen bleiben, da Broadcast () das Semaphor nur so oft erh\u00f6ht, 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\u00f6nnten: den Thread, der signalisiert, und einen der Threads, die warten. Damit jeweils h\u00f6chstens ein Thread den Monitor belegt, muss eine Auswahl getroffen werden. Es gibt zwei Denkschulen, wie diese Wahl am besten gel\u00f6st werden kann. Dies f\u00fchrt zu zwei Arten von Bedingungsvariablen, die als n\u00e4chstes untersucht werden:Bedingungsvariablen blockieren Geben Sie einem signalisierten Thread Priorit\u00e4t.Nicht blockierende Bedingungsvariablen Geben Sie dem Signalisierungs-Thread Priorit\u00e4t.Bedingungsvariablen blockieren[edit]Die urspr\u00fcnglichen Vorschl\u00e4ge von CAR Hoare und Per Brinch Hansen waren f\u00fcr Bedingungsvariablen blockieren. Bei einer blockierenden Bedingungsvariablen muss der Signalisierungsthread (mindestens) au\u00dferhalb des Monitors warten, bis der signalisierte Thread die Belegung des Monitors aufgibt, indem er entweder zur\u00fcckkehrt oder erneut auf eine Bedingungsvariable wartet. Monitore, die blockierende Bedingungsvariablen verwenden, werden h\u00e4ufig 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 sinde ist die Eingangswarteschlanges ist eine Warteschlange von Threads, die signalisiert haben.Au\u00dferdem nehmen wir das f\u00fcr jede Bedingungsvariable an cgibt es eine Warteschlangec.qDies ist eine Warteschlange f\u00fcr Threads, die auf eine Bedingungsvariable warten cEs 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\u00fchrt wird. Daher werden neu gestartete Threads erst ausgef\u00fchrt, 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 monitorleave the monitor: schedule return from the methodwait c: add this thread to c.q schedule block this threadsignal 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 threadschedule: 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\u00e4hlt den n\u00e4chsten 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\u00fcck Operation, die die Signalisierung mit der R\u00fcckkehr 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 methodIn beiden F\u00e4llen (“Signal und dringendes Warten” oder “signalisieren und warten”) Wenn eine Bedingungsvariable signalisiert wird und mindestens ein Thread auf die Bedingungsvariable wartet, \u00fcbergibt 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\u00e4ge zusammengefasst. In diesen Vertr\u00e4gen ich ist die Invariante des Monitors.enter the monitor: postcondition Ileave the monitor: precondition Iwait c: precondition I modifies the state of the monitor postcondition Pc and Isignal c: precondition Pc and I modifies the state of the monitor postcondition Isignal c and return: precondition Pc and IIn diesen Vertr\u00e4gen wird davon ausgegangen, dass ich und P.c h\u00e4ngen nicht vom Inhalt oder der L\u00e4nge von Warteschlangen ab.(Wenn die Bedingungsvariable nach der Anzahl der in ihrer Warteschlange wartenden Threads abgefragt werden kann, k\u00f6nnen komplexere Vertr\u00e4ge vergeben werden. Ein n\u00fctzliches Vertragspaar, mit dem die Belegung ohne Festlegen der Invariante \u00fcbergeben werden kann, lautet beispielsweise:wait c: precondition I modifies the state of the monitor postcondition Pcsignal c precondition (not empty(c) and Pc) or (empty(c) and I) modifies the state of the monitor postcondition ISiehe Howard[4] und Buhr et al.,[5] f\u00fcr 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\u00dfen 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\u00a0:= 10 private int[capacity] A private int size\u00a0:= 0 invariant 0 (adsbygoogle = window.adsbygoogle || []).push({});after-content-x4"},{"@context":"http:\/\/schema.org\/","@type":"BreadcrumbList","itemListElement":[{"@type":"ListItem","position":1,"item":{"@id":"https:\/\/wiki.edu.vn\/wiki18\/#breadcrumbitem","name":"Enzyklop\u00e4die"}},{"@type":"ListItem","position":2,"item":{"@id":"https:\/\/wiki.edu.vn\/wiki18\/2020\/12\/31\/monitor-synchronisation-wikipedia\/#breadcrumbitem","name":"Monitor (Synchronisation) – Wikipedia"}}]}]