Es gibt zwei wesentliche Konzepte zum Erstellen von konkurrierenden Programmen - Synchronisierung und wechselseitiger Ausschluss. Wir werden sehen, wie diese beiden Arten von Sperren (Semaphore sind im allgemeinen eine Art Sperrmechanismus) uns helfen, Synchronisation und gegenseitigen Ausschluss zu erreichen.
Ein Semaphor besteht aus zwei Teilen: einem Zähler und einer Liste von Aufgaben, die auf den Zugriff auf eine bestimmte Ressource warten. Ein Semaphor führt zwei Operationen aus: Warten (P) [das ist wie das Erlangen einer Sperre] und Freigabe (V) [ähnlich dem Freigeben einer Sperre] - dies sind die einzigen zwei Operationen, die man an einem Semaphor ausführen kann. In einem binären Semaphor geht der Zähler logisch zwischen 0 und 1. Sie können sich vorstellen, dass er ähnlich einer Sperre mit zwei Werten ist: offen/geschlossen. Ein Zählsemaphor hat mehrere Werte für die Zählung.
Was wichtig zu verstehen ist, ist, dass der Semaphorzähler die Anzahl der Aufgaben verfolgt, die nicht blockiert werden müssen, d. H. Sie können Fortschritte machen. Aufgaben blockieren und fügen sich nur dann zur Liste des Semaphors hinzu, wenn der Zähler Null ist. Daher wird eine Aufgabe in der P() - Routine zur Liste hinzugefügt, wenn sie nicht fortgeführt werden kann, und mit der V() - Routine "befreit".
Nun ist es ziemlich offensichtlich zu sehen, wie binäre Semaphore verwendet werden können, um Synchronisation und gegenseitigen Ausschluss zu lösen - sie sind im Wesentlichen Sperren.
ex. Synchronisation:
thread A{
semaphore &s; //locks/semaphores are passed by reference! think about why this is so.
A(semaphore &s): s(s){} //constructor
foo(){
...
s.P();
;// some block of code B2
...
}
//thread B{
semaphore &s;
B(semaphore &s): s(s){} //constructor
foo(){
...
...
// some block of code B1
s.V();
..
}
main(){
semaphore s(0); // we start the semaphore at 0 (closed)
A a(s);
B b(s);
}
In dem obigen Beispiel kann B2 nur ausführen nach B1 Ausführung beendet hat. Angenommen, Thread A kommt zuerst - ruft sem.P() ab und wartet, da der Zähler 0 (geschlossen) ist. Thread B kommt, beendet B1 und gibt dann Thread A frei - der dann B2 vervollständigt. So erreichen wir die Synchronisation.
Nun wollen sie mit einer binären Semaphore bei mutual exclusion aussehen:
thread mutual_ex{
semaphore &s;
mutual_ex(semaphore &s): s(s){} //constructor
foo(){
...
s.P();
//critical section
s.V();
...
...
s.P();
//critical section
s.V();
...
}
main(){
semaphore s(1);
mutual_ex m1(s);
mutual_ex m2(s);
}
Die gegenseitige Ausgrenzung ist auch ganz einfach - m1 und m2 in dem kritischen Abschnitt in der gleichen Zeit nicht eingeben. Daher verwendet jeder Thread den gleichen Semaphor, um einen gegenseitigen Ausschluss für seine zwei kritischen Abschnitte bereitzustellen. Ist es nun möglich, eine größere Parallelität zu haben? Hängt von den kritischen Abschnitten ab. (Denken Sie darüber nach, wie sonst könnte man Semaphore verwenden gegenseitigen Ausschluss zu erreichen .. Hinweis: Muss ich unbedingt nur ein Semaphore benutzen?)
Counting Semaphore: Eine Semaphore mit mehr als einem Wert. Schauen wir uns an, was das bedeutet - ein Schloss mit mehr als einen Wert? So offen, geschlossen und ... hmm. Welchen Nutzen hat eine mehrstufige Sperre für wechselseitigen Ausschluss oder Synchronisation?
Lassen Sie uns die einfachere der beiden nehmen:
Synchronisation eine Zählung Semaphore mit: Lasst uns sagen, Sie haben drei Aufgaben - # 1 und 2, die Sie nach dem 3. ausgeführt möchten, wie Sie Ihre Synchronisation entwerfen würde?
thread t1{
...
s.P();
//block of code B1
thread t2{
...
s.P();
//block of code B2
thread t3{
...
//block of code B3
s.V();
s.V();
}
Also, wenn Ihr Semaphore geschlossen beginnt, können Sie diesen T1- und T2-Block sicherzustellen, auf die Semaphore der Liste hinzugefügt. Dann kommt alles Wichtige t3, beendet sein Geschäft und befreit t1 und t2. In welcher Reihenfolge werden sie freigegeben? Hängt von der Implementierung der Semaphor-Liste ab. Könnte FIFO sein, könnte eine bestimmte Priorität, etc. (Hinweis: darüber nachdenken, wie Sie Ihre P und V anordnen würden; s, wenn Sie T1 und T2 wollten in einer bestimmten Reihenfolge ausgeführt werden, und wenn Sie sind von der Umsetzung des Semaphore nicht bekannt)
(Finden Sie heraus,: Was passiert, wenn die Zahl der V geschieht, ist größer als die Anzahl von P)
Mutual Exclusion Zählen Semaphoren: ich würde Sie gerne Ihren eigenen Pseudo-Code für diese konstruieren (macht man die Dinge verstehen besser!) - aber das Grundkonzept ist das: ein Zähl-Semaphor von counter = N erlaubt N Aufgaben den freien Bereich frei zu betreten. Was das bedeutet ist, dass Sie N Aufgaben (oder Threads, wenn Sie möchten) den kritischen Abschnitt betreten, aber die N + 1te Aufgabe wird blockiert (geht auf unsere Lieblingsliste mit blockierten Aufgaben) und wird nur durchgelassen, wenn jemand V der Semaphor ist mindestens einmal. Also geht der Semaphor-Zähler, statt zwischen 0 und 1 zu schwingen, jetzt zwischen 0 und N, wodurch N Aufgaben frei ein- und ausgehen können und niemanden blockieren!
Nun, warum würden Sie solch ein bizarres Schloss brauchen?Ist das nicht der Sinn des gegenseitigen Ausschlusses, dass nicht mehr als ein Typ auf eine Ressource zugreifen darf? Denken. (Hint ... Sie müssen nicht immer nur eine-Laufwerk in Ihrem Computer, nicht wahr ...?)
zu denken: Ist mutual exclusion erreicht, indem eine Zählung mit Semaphore allein? Was ist, wenn Sie 10 Instanzen einer Ressource haben und 10 Threads (über den Zähl-Semaphor) hereinkommen und versuchen, die erste Instanz zu verwenden?
Ein guter Anwendungsfall für einen Zähl-Semaphor ist, wenn Sie nur nach mehreren abgeschlossenen Ereignissen fortfahren möchten. Zum Beispiel startet Ihr Programm 5 verschiedene asynchrone Datenbanklesevorgänge und initiiert sie, und sollte erst fortgesetzt werden, wenn alle 5 abgeschlossen sind. Sie würden den Semaphor zu Beginn jedes Lesevorgangs inkrementieren und sofort 'Semaphore == 0' blockieren. Nach Abschluss jedes Lesevorgangs dekrementieren Sie den Semaphor. Ihr Start wird nach Abschluss der Datenladung fortgesetzt. –