Umfassende Analyse von Synchronisationsprimitiven in Betriebssystemen
- 不言Original
- 2018-09-17 15:27:271407Durchsuche
Dieser Artikel bietet Ihnen eine umfassende Analyse der Synchronisationsprimitive im Betriebssystem. Ich hoffe, dass er für Freunde hilfreich ist.
Race-Bedingung
In einem allgemeinen Betriebssystem können sich verschiedene Prozesse einen gemeinsamen Speicherbereich teilen, z. B. Speicher oder Dateien auf der Festplatte. Diese Prozesse dürfen in diesen Bereichen ausgeführt werden und weiterschreiben.
Das Betriebssystem hat einige Aufgaben, die Prozesse mithilfe des gemeinsamen Bereichs zu koordinieren, um die gewünschten Vorgänge korrekt auszuführen. Diese Prozesse müssen miteinander kommunizieren und Diskussionen führen, um sicherzustellen, dass die Aktionen eines Prozesses die normalen Aktionen eines anderen Prozesses nicht beeinträchtigen, was dazu führt, dass der Prozess nach der Ausführung nicht die erwarteten Ergebnisse erzielt. Im Betriebssystemkonzept wird üblicherweise der Begriff IPC (Inter Process Communication) verwendet, um die Kommunikation zwischen mehreren Prozessen darzustellen.
Um zu erklären, was eine Race-Bedingung ist, führen wir ein einfaches Beispiel zur Veranschaulichung ein:
Eine Zahl n ist in einer Datei gespeichert, und sowohl Prozess A als auch Prozess B möchten diese Datei lesen und 1 hinzufügen zu dieser Nummer hinzufügen und wieder in der Datei speichern. Unter der Annahme, dass der Anfangswert von n 0 ist, sollte in unserem Idealfall nach der Ausführung von Prozess A und Prozess B der Wert von n in der Datei 2 sein, aber tatsächlich kann es vorkommen, dass der Wert von n 1 ist. Wir können dabei überlegen, welche Schritte jeder Prozess durchlaufen muss:
Lesen Sie den Wert von n in der Datei
Sei n = n + 1
Speichern Sie den neuen n-Wert wieder in der Datei.
Bevor wir die Rennbedingungen weiter erläutern, müssen wir zunächst einige Wissenspunkte in Betriebssystemkonzepten überprüfen:
Prozesse können gleichzeitig ausgeführt werden, auch wenn sie vorhanden sind ist nur eine CPU)
Die Taktunterbrechung des Betriebssystems führt zu einer Neuplanung des laufenden Prozesses,
Zusätzlich zur Uhr Interrupt, Interrupts von anderen Geräten führen ebenfalls dazu, dass der Prozess neu geplant wird
Angenommen, ein Taktinterrupt tritt auf, wenn Prozess A die Ausführung der Schritte 1 und 2 abgeschlossen hat, aber noch nicht mit der Ausführung von Schritt 3 begonnen hat . Zu diesem Zeitpunkt plant das Betriebssystem die Ausführung von Prozess B. Wenn Prozess B Schritt 1 ausführt, stellt es fest, dass der Wert von n 0 ist, und führt daher die Schritte 2 und 3 aus und speichert schließlich n = 1 in einer Datei . Wenn Prozess A später weiterläuft, schreibt Prozess A ebenfalls n = 1 zurück in die Datei, weil er vor der Ausführung von Schritt 3 nicht weiß, dass Prozess B den Wert in der Datei geändert hat. Dies ist das Problem, während Prozess A ausgeführt wird, andere Prozesse verarbeiten die von ihm verarbeiteten Daten.
Die einzige Möglichkeit, n = 2 zu erreichen, besteht darin, zu erwarten, dass Prozess A und Prozess B alle Schritte der Reihe nach vollständig ausführen .
Wir können eine Race-Bedingung definieren
Zwei oder mehr Prozesse lesen und schreiben bestimmte gemeinsame Daten, und das Endergebnis hängt vom genauen Zeitpunkt der Ausführung des Prozesses ab, der als Race-Bedingung bezeichnet wird.
Im obigen Text verwenden wir den Prozess als Objekt zur Erörterung der Race-Bedingungen. Dasselbe gilt hier für Threads, einschließlich Kernel-Threads und Benutzer-Threads. Denn im Betriebssystem sind Prozesse tatsächlich auf Threads angewiesen, um Programme auszuführen. Darüber hinaus gilt in der Thread-Sicherheit der Java-Sprache auch das Konzept der Race Conditions. (Siehe Kapitel 2 von „Java Concurrent Programming in Practice“)
Gegenseitiger Ausschluss und kritische Abschnitte
Um Race Conditions zu vermeiden, müssen wir einige Mittel einsetzen, um sicherzustellen, dass ein Prozess ausgeführt wird Mit einer gemeinsam genutzten Variablen oder Dateien können andere Prozesse nicht den gleichen Vorgang ausführen. Mit anderen Worten, wir benötigen einen „gegenseitigen Ausschluss“.
Am Beispiel des obigen Beispiels können wir das Programmfragment aus den Schritten 1 bis 3 als kritischen Abschnitt definieren. Der kritische Abschnitt bedeutet, dass dieser Bereich sensibel ist, denn sobald der Prozess in diesen Bereich läuft, bedeutet dies, dass er öffentlich ist Das Bearbeiten eines Bereichs oder einer Datei bedeutet auch, dass möglicherweise andere Prozesse im kritischen Bereich ausgeführt werden. Wenn geeignete Maßnahmen ergriffen werden, damit sich die beiden Prozesse nicht gleichzeitig in kritischen Abschnitten befinden, können Race Conditions vermieden werden.
Mit anderen Worten: Wir müssen darüber nachdenken, wie wir „gegenseitigen Ausschluss“ erreichen können.
System zum gegenseitigen Ausschluss
Der Kern des gegenseitigen Ausschlusses besteht darin, zu verhindern, dass mehrere Prozesse gleichzeitig in den kritischen Bereich gelangen
Unterbrechungen maskieren
Im zuvor genannten Beispiel konnte Prozess B in den kritischen Abschnitt gelangen, da Prozess A im kritischen Abschnitt unterbrochen wurde. Wenn wir Prozess A bitten, alle Interrupts unmittelbar nach dem Betreten des kritischen Abschnitts zu maskieren und erst nach Verlassen des kritischen Abschnitts auf Interrupts zu reagieren, wechselt die CPU selbst dann nicht zu anderen Prozessen, wenn ein Interrupt auftritt, sodass Prozess A ihn sicher ändern kann Inhalte der Datei, ohne befürchten zu müssen, dass andere Prozesse die Arbeit beeinträchtigen.
Diese Idee ist zwar schön, aber tatsächlich nicht realisierbar. Erstens: Wenn mehrere CPUs vorhanden sind, kann Prozess A keine Interrupts für andere CPUs maskieren. Er kann nur die CPU maskieren, die ihn plant, sodass von anderen CPUs geplante Prozesse weiterhin in den kritischen Abschnitt gelangen können von blockierenden Interrupts an den Benutzerprozess gegeben werden? Wenn dieser Prozess Interrupts maskiert und nie auf Interrupts reagiert, kann es sein, dass ein Prozess das gesamte Betriebssystem blockiert.
Sperrvariable
Vielleicht können Sie ihren Anfangswert auf 0 setzen, indem Sie ein Sperrflag setzen. Wenn ein Prozess den kritischen Abschnitt betreten möchte, prüfen Sie zunächst, ob der Wert der Sperre 0 ist. Wenn es 0 ist, setzen Sie es auf 1, geben Sie dann den kritischen Abschnitt ein und ändern Sie den Wert der Sperre nach dem Verlassen des kritischen Abschnitts auf 0. Wenn der Wert der Sperre bei der Überprüfung bereits 1 ist, bedeutet dies, dass andere Prozesse vorhanden sind bereits im kritischen Abschnitt, daher durchläuft der Prozess eine Schleife. Warten Sie und überprüfen Sie den Wert der Sperre weiter, bis er 0 wird.
Aber es gibt auch eine Race-Bedingung bei dieser Methode. Der Grund dafür ist, dass, wenn ein Prozess den Wert der Sperre als 0 liest, bevor er seinen Wert auf 1 setzt, ein anderer Prozess geplant wird und dieser auch den Wert von liest lock ist 0, daher gibt es eine Situation, in der sich beide Prozesse gleichzeitig im kritischen Abschnitt befinden.
Strikte Rotationsmethode
Der Grund für ein Problem mit der Sperrvariablen liegt tatsächlich darin, dass die Änderung der Sperrvariablen von 0 auf 1 von dem Prozess ausgeführt wird, der die Sperrvariable erhalten möchte sperren. Wenn wir diese Aktion so ändern, dass sie von dem Prozess ausgeführt wird, der die Sperre erhalten hat, liegt keine Racebedingung vor.
Legen Sie zunächst eine Variable turn fest, die angibt, wer derzeit die Sperre erhalten darf. Die Logik von Prozess A lautet wie folgt:
while (turn != 0){// 如果还没轮到自己获取锁，则进入循环等待
}
do_critical_region();// 执行临界区的程序
turn = 1;// 由获得锁的一方将锁变量修改为其它值，允许其它进程获得锁
do_non_critical_region();// 执行非临界区的程序
Die Logik von Prozess B ist wie folgt :
while (turn != 1) {// 如果还没轮到自己获取锁，则进入循环等待
}
do_critical_region();// 执行临界区的程序
turn = 0;// 由获得锁的一方将锁变量修改为其它值，允许其它进程获得锁
do_non_critical_region();// 执行非临界区的程序
Angenommen, do_non_critical_region() von Prozess A muss über einen längeren Zeitraum ausgeführt werden, nämlich die Logik des unkritischen Bereichs von Prozess A Die Ausführung muss lange dauern, während die Logik des unkritischen Bereichs von Prozess B schnell ausgeführt wird. Nach der Ausführung ist es offensichtlich, dass Prozess A seltener in den kritischen Bereich eintritt als Prozess B. Idealerweise wird Prozess B ausgeführt sollte den kritischen Abschnitt mehrmals betreten. Da Prozess B jedoch turn auf 0 setzt, bevor er die Logik des unkritischen Abschnitts ausführt, wird festgestellt, dass nach der schnellen Ausführung der Logik des unkritischen Abschnitts, wenn er zurückkommt, um den Wert von turn zu überprüfen Der Wert von turn war nie 1. Der Wert erfordert, dass Prozess A ihn auf 1 setzt, aber Prozess A führt derzeit einen langen Logikcode für einen nicht kritischen Abschnitt aus, sodass Prozess B den kritischen Abschnitt nicht betreten kann.
Dies zeigt, dass eine strikte Rotation keine gute Idee ist, wenn ein Prozess viel langsamer ist als ein anderer.
Peterson-Algorithmus
Das Problem mit der strikten Rotationsmethode liegt im Wort strikt, das heißt, dass mehrere Prozesse abwechselnd in den kritischen Abschnitt gelangen. Der grundlegende Grund ist der Prozess, der das erhalten möchte lock Es muss sich auf andere Prozesse verlassen, um die Sperrvariable zu ändern, und andere Prozesse müssen zuerst die Logik des unkritischen Abschnitts ausführen, bevor sie die Sperrvariable ändern.
Die Turn-Variable in der strikten Rotationsmethode wird nicht nur verwendet, um anzugeben, wer an der Reihe ist, die Sperre zu erhalten, sondern bedeutet auch, dass sie, bevor sich ihr Wert ändert, immer noch verhindert, dass andere Prozesse in den kritischen Abschnitt gelangen Es kommt vor, dass ein Prozess immer den Wert der Umdrehung erst ändert, nachdem er die Logik des unkritischen Abschnitts durchlaufen hat.
Daher können wir zwei Variablen verwenden, um es darzustellen. Eine Variable stellt dar, wer gerade an der Reihe ist, die Sperre zu erhalten, und die andere Variable stellt dar, dass der aktuelle Prozess den kritischen Abschnitt verlassen hat. das von der niederländischen Mathematik entwickelt wurde, vorgeschlagen von T. Dekker.
static final int N = 2;
int turn = 0;
boolean[] interested = new boolean[N];
void enter_region(int process) {
int other = 1 - process;
interested[process] = true;
turn = process;
while(turn == process && !interested[other]) {
}
}
void exit_region(int process) {
interested[process] = false;
}
Wenn ein Prozess den kritischen Abschnitt betreten muss, ruft er zuerst enter_region auf und ruft nach Verlassen des kritischen Abschnitts exit_region auf. Der Peterson-Algorithmus bewirkt, dass der Prozess nach Verlassen des kritischen Abschnitts sein „Interesse“ am kritischen Abschnitt sofort beseitigt, sodass andere Prozesse anhand des Turn-Werts beurteilen können, ob sie den kritischen Abschnitt legal betreten können.
TSL-Anweisung
Erinnern Sie sich an die zuvor erwähnte Methode „Variable sperren“: Einer ihrer schwerwiegenden Mängel besteht darin, dass die Statusvariable geändert wird, z. B. wenn sie von 0 auf 1 oder von 1 auf 0 geändert wird kann durch Interrupts unterbrochen werden, es liegt also eine Race-Bedingung vor.
Später haben wir basierend auf der Sperrvariablen vorgeschlagen, dass die Sperrvariable nicht durch den Prozess geändert wird, der in den kritischen Abschnitt eintreten möchte, sondern durch den Prozess, der den kritischen Abschnitt nach dem Eintritt in den kritischen Abschnitt verlassen möchte Race-Bedingungen können vermieden werden, was zur strikten Rotationsmethode führt und den Peterson-Algorithmus auf Basis der strikten Rotationsmethode verbessert. Diese Methoden werden alle aus einer Softwareperspektive betrachtet. Tatsächlich kann mit der Unterstützung der Hardware-CPU sichergestellt werden, dass Änderungen an Sperrvariablen nicht unterbrochen werden, was Sperrvariablen zu einer guten Methode zur Lösung des gegenseitigen Prozessausschlusses macht.
Die meisten aktuellen Computer-CPUs unterstützen den TSL-Befehl, der Test and Set Lock heißt. Er liest eine Speichervariable (Wort) in das Register RX und speichert dann einen Wert ungleich Null an der gelesenen Speicheradresse Vorgänge und Schreibvorgänge sind auf Hardwareebene garantiert unterbrechungsfrei, also atomar. Die verwendete Methode besteht darin, den Speicherbus beim Ausführen des TSL-Befehls zu sperren und so zu verhindern, dass andere CPUs auf den Speicher zugreifen, bevor der TSL-Befehl endet. Dies wird auch oft als CAS (Compare And Set) bezeichnet.
Wenn Sie die Sperrvariable von 0 auf 1 ändern müssen, kopieren Sie zuerst den Speicherwert in das Register, setzen Sie den Speicherwert auf 1 und prüfen Sie dann, ob der Registerwert 0 ist. Wenn er 0 ist, ist die Operation erfolgreich Wenn es nicht 0 ist, wiederholen Sie die Erkennung, bis der Registerwert 0 wird. Wenn der Registerwert 0 wird, bedeutet dies, dass ein anderer Prozess den kritischen Abschnitt verlassen hat. Wenn der Prozess den kritischen Abschnitt verlässt, muss er den Wert dieser Variablen im Speicher auf 0 setzen.
Beschäftigtes Warten
Der oben erwähnte Peterson-Algorithmus und die TSL-Methode haben tatsächlich eine Funktion, nämlich das Besetzt-Warten, wenn sie auf den Eintritt in den kritischen Abschnitt warten. Wir nennen es auch oft Spin . Der Nachteil besteht darin, dass dadurch CPU-Zeitscheiben verschwendet werden und Probleme mit der Prioritätsumkehr auftreten können.
Stellen Sie sich einen Computer mit zwei Prozessen vor, wobei H eine höhere Priorität und L eine niedrigere Priorität hat. Die Planungsregeln besagen, dass H ausgeführt werden kann, solange es sich im Bereitschaftszustand befindet. Zu einem bestimmten Zeitpunkt befindet sich L im kritischen Bereich und H befindet sich in einem Bereitschaftszustand und ist betriebsbereit. Aber H muss damit beschäftigt sein, zu warten, und L kann aufgrund seiner niedrigen Priorität nicht eingeplant werden und kann daher den kritischen Abschnitt nicht verlassen. Daher wird H ewig damit beschäftigt sein, zu warten, und L kann den kritischen Abschnitt niemals verlassen. Diese Situation wird als Prioritätsumkehrproblem (Prioritätsumkehrproblem) bezeichnet.
Blockieren und Aufwecken des Prozesses
Das Betriebssystem bietet einige Grundelemente, Schlaf und Aufwachen.
Der vom Kernel für Aufrufe außerhalb des Kerns bereitgestellte Prozess oder die Funktion wird zu einem Grundelement, und Grundelemente erlauben keine Unterbrechung während der Ausführung.
sleep ist ein Systemaufruf, der den aufrufenden Prozess blockiert, bis ein anderer Prozess die Wakeup-Methode aufruft, wobei der blockierte Prozess als Parameter zum Aufwecken verwendet wird. Der größte Unterschied zwischen Blockieren und Besetztwarten besteht darin, dass die CPU ihm nach dem Blockieren des Prozesses keine Zeitscheibe zuweist, während Besetztwarten immer im Leerlauf ist und die Zeitscheibe der CPU verbraucht.
Semaphor
Das erste, was Sie verstehen müssen, ist, welches Problem das Semaphor zu lösen scheint, da die Blockierung und das Erwachen eines Prozesses in verschiedenen Prozessen verursacht werden, zum Beispiel ruft Prozess A sleep() auf Geben Sie die Blockierung ein, und der Aufruf von Prozess B an wakeup(A) weckt Prozess A auf. Da es in unterschiedlichen Prozessen durchgeführt wird, besteht auch das Problem der Unterbrechung. Gemäß der Logik muss Prozess A beim Beitreten den Ruhezustand aufrufen, um in den Blockierungszustand zu gelangen. Aufgrund der Taktunterbrechung beginnt Prozess B jedoch mit der Ausführung ruft die Methode wakeup() auf, um Prozess A aufzuwecken. Da Prozess A jedoch noch nicht in den Blockierungszustand eingetreten ist, geht das Wecksignal verloren weckt es auf.
Daher sollte eine zusätzliche Variable eingeführt werden, um das Blockieren und Erwachen des Prozesses aufzuzeichnen. Diese Variable zeichnet die Anzahl der Erweckungen auf. Bei jedem Erwachen wird der Wert der Variablen um 1 erhöht. Mit dieser Variablen wird der Weckvorgang in der Variablen aufgezeichnet, auch wenn der Weckvorgang vor dem Ruhezustand erfolgt. Wenn der Prozess in den Ruhezustand wechselt, wird davon ausgegangen, dass der Prozess nicht in die Blockierung eintreten muss, da andere Prozesse bereits aufgewacht sind Zustand.
Diese Variable wird im Betriebssystemkonzept als Semaphor bezeichnet, eine Methode, die 1965 von Dijkstra vorgeschlagen wurde.
Es gibt zwei Operationen für Semaphoren: nach unten und nach oben.
Der Down-Vorgang entspricht tatsächlich dem Ruhezustand. Er erkennt zunächst, ob der Wert des Semaphors größer als 0 ist. Wenn er größer als 0 ist, wird er um 1 verringert. Der Prozess muss zu diesem Zeitpunkt nicht blockiert werden. Dies entspricht dem Verbrauch eines Weckvorgangs. Wenn das Semaphor 0 ist, tritt der Prozess in einen Blockierungszustand ein.
Der Up-Vorgang entspricht dem Aufwecken. Wenn festgestellt wird, dass ein Prozess auf diesem Semaphor blockiert ist, wählt das System einen der Prozesse aus, um ihn aufzuwecken Es ist keine Änderung erforderlich, aber es ist bereits ein Prozess weniger auf dem Semaphor vorhanden. Wenn während des Up-Vorgangs kein Prozess blockiert wird, erhöht sich der Wert des Semaphors um 1.
An manchen Stellen werden die Abwärts- und Aufwärtsoperationen als PV-Operationen bezeichnet. Dies liegt daran, dass in Dijkstras Artikel P und V zur Darstellung von Abwärts- bzw. Aufwärtsoperationen verwendet werden.
Die Abwärts- und Aufwärtsoperationen von Semaphoren sind Grundelemente, die vom Betriebssystem unterstützt werden. Sie sind atomare Operationen und werden nicht unterbrochen.
Mutex
Ein Mutex ist eigentlich ein Sonderfall eines Semaphors. Seine Werte sind nur 0 und 1. Wenn wir die Zählfähigkeit des Semaphors nicht nutzen müssen, können wir dies tun Verwenden Sie einen Mutex, was tatsächlich bedeutet, dass der Wert des kritischen Abschnitts nur den gleichzeitigen Eintritt eines Prozesses zulässt, während das Semaphor mehreren Prozessen den gleichzeitigen Eintritt in den kritischen Abschnitt ermöglicht.
Das obige ist der detaillierte Inhalt vonUmfassende Analyse von Synchronisationsprimitiven in Betriebssystemen. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!