Technologieaustausch

한어Русский языкEnglishFrançaisIndonesianSanskrit日本語DeutschPortuguêsΕλληνικάespañolItalianoSuomalainenLatina

04.07.2024: Studiennotizen zur Betriebssystemsynchronisierung und zum gegenseitigen Ausschluss

---

Gleichzeitige Prozesse oder Programme verlieren ihren Abschluss, wenn sie ausgeführt werden. Das heißt, wenn zwei Programme eine gemeinsame Ressource in separaten Bereichen verwenden, können die Ergebnisse jeder Ausführung unterschiedlich sein.

Der Grund dafür ist, dass wir die gemeinsam genutzte Ressource x, auf die sowohl Programm a als auch Programm b zugreifen müssen, nicht geschützt haben.

---

9.1 Grundkonzepte von Synchronisation und gegenseitigem Ausschluss

9.1.1 Synchronisationsbeziehung

Die sich gegenseitig einschränkende Beziehung ist Synchronisation. Ein einfaches Verständnis von Synchronisation besteht darin, dass es eine Reihenfolge bei der Ausführung von Prozessen geben muss.

---

9.1.2 Gegenseitig ausschließende Beziehung

Die Beziehung, die sich gegenseitig indirekt einschränkt, wird als sich gegenseitig ausschließende Beziehung bezeichnet, z

---

9.1.3 Kritische Ressourcen

• Ressourcen, auf die nur ein Prozess innerhalb eines bestimmten Zeitraums zugreifen darf, werden als kritische Ressourcen (oder exklusive Ressourcen) bezeichnet.
• Für die gemeinsame Nutzung kritischer Ressourcen sollte der gegenseitige Ausschluss zwischen Prozessen genutzt werden

„Produzenten- und Verbrauchermodell“
Zähler+ +

首先把变量放到寄存器里面
register1 = counter;
接下来对寄存器进行一个自增
register1 = register1 + 1;
再把结果返回到counter里
counter = register1;
1
2
3
4
5
6

Schalter- -

首先把变量放到寄存器里面
register2 = counter;
接下来对寄存器进行一个自减
register2 = register2 - 1;
再把结果返回到counter里
counter = register2;
1
2
3
4
5
6

Lösung: Behandeln Sie den Zähler als kritische Ressource und erlauben Sie dem Prozess, gegenseitig auf den variablen Zähler zuzugreifen (den Synchronisierungsmechanismus erfahren Sie später).

---

9.1.4 Kritischer Abschnitt

Unabhängig davon, ob es sich um eine hardwarekritische Ressource oder eine softwarekritische Ressource handelt, müssen mehrere Prozesse gegenseitig darauf zugreifen.

Bei diesen Bereichen handelt es sich im Wesentlichen um Codes

• Eingangsbereich
• Kritischer Abschnitt
• Ausgangsbereich
• verbleibende Fläche

---

9.1.5 Synchronisationsmechanismen sollten Regeln folgen

• Freier Einlass

Wenn sich kein Prozess im kritischen Abschnitt befindet, bedeutet dies, dass die Ressourcen des kritischen Abschnitts inaktiv sind. Ein Prozess, der den Zugriff auf den kritischen Abschnitt anfordert, sollte sofort in seinen eigenen kritischen Abschnitt eintreten dürfen, um die Ressourcen effektiv zu nutzen.

• Wenn Sie beschäftigt sind, warten Sie

Wenn ein vorhandener Prozess den kritischen Abschnitt betritt, zeigt dies an, dass auf die kritische Ressource zugegriffen wird. Daher müssen andere Prozesse, die versuchen, in den kritischen Abschnitt einzudringen, warten, um den gegenseitigen Zugriff auf die kritische Ressource sicherzustellen.

• begrenzte Wartezeit

Bei Prozessen, die Zugriff auf kritische Ressourcen erfordern, sollten sie sicherstellen, dass sie innerhalb einer begrenzten Zeit in ihren eigenen kritischen Abschnitt gelangen können, um zu vermeiden, dass sie in einen „Warten auf den Tod“-Zustand geraten.

• Gib nach und warte

Wenn ein Prozess seinen eigenen kritischen Abschnitt nicht betreten kann, sollte der Prozessor (CPU) sofort freigegeben werden, um zu verhindern, dass der Prozess in einen „Beschäftigt-Warten“-Zustand fällt.

---

9.2 Software-Synchronisationsmechanismus

9.2.1 Einzelmarkenmethode

• Legen Sie eine öffentliche Ganzzahlvariable fest, um anzugeben, ob sich im kritischen Abschnitt bereits ein Prozess befindet, und wartet auf eine Schleifenprüfung im Eingangsbereich, nachdem der Prozess den kritischen Abschnitt verlassen hat wird im Ausgangsbereich geändert.
• Die Single-Flag-Methode legt eine öffentliche Ganzzahlvariable turn fest, um die Prozessnummer anzugeben, die den kritischen Abschnitt betreten darf. Wenn turn=0, darf Prozess P0 den kritischen Abschnitt betreten.
• Wenn turn=1, darf Prozess P1 den kritischen Abschnitt betreten, und beim Verlassen des kritischen Abschnitts wird das Recht zur Nutzung des kritischen Abschnitts einem anderen Prozess übertragen (wenn Pi den kritischen Abschnitt verlässt, sei turn=j).

两个进程必须交替进入临界区，若一个进程不再进入临界区，则另一个进程也无法进入临界区，违背了“空闲让进”准则

---

9.2.2 Methode der ersten Doppelmarkierung

Die Double-Flag-Erstprüfungsmethode setzt ein boolesches Array-Flag[2], um die Bereitschaft jedes Prozesses zu markieren, den kritischen Abschnitt zu betreten. flag[i]=true bedeutet, dass Pi den kritischen Abschnitt betreten möchte.

• Bevor Pi den kritischen Abschnitt betritt, prüfen Sie zunächst, ob die andere Partei den kritischen Abschnitt betreten hat. Wenn ja, warten Sie
• Andernfalls setzen Sie flag[i] auf true, bevor Sie den kritischen Abschnitt betreten
• Wenn Pi den kritischen Abschnitt verlässt, setzen Sie Flag[i] auf „false“.

• Die while-Schleife entspricht dem Ampelmechanismus
• Das Setzen der Flagge der anderen Partei ist gleichbedeutend mit dem Ändern der Ampel der anderen Partei.
• Da jedoch beide Prozesse zuerst die Flagge prüfen [zuerst auf die Ampel schauen] und beide zunächst falsch sind [beide grüne Ampeln], ist es möglich, dass die beiden Prozesse gleichzeitig die Ampel passieren und gemeinsam in den kritischen Abschnitt gelangen .

---

9.2.3 Methode der Doppelmarkierung nach der Inspektion

Die Nachprüfungsmethode mit doppelter Flagge überprüft die Flagge der anderen Partei und setzt dann ihre eigene. Diese beiden Vorgänge können nicht gleichzeitig ausgeführt werden, sodass die beiden Prozesse möglicherweise gleichzeitig in den kritischen Abschnitt gelangen Es wurde eine Methode entwickelt, die zuerst die eigene Flagge setzt und dann die Flagge der anderen Partei überprüft. Wenn die Flagge der anderen Partei wahr ist, wird andernfalls der kritische Abschnitt eingegeben

---

9.2.4 Peterson-Algorithmus

Petersons Algorithmus kombiniertEinzelmarkierungsmethodeUndMethode zur Nachprüfung mit doppelter MarkierungDie Idee besteht darin, flag[] zu verwenden, um das sich gegenseitig ausschließende Zugriffsproblem zu lösen, und turn, um das Hungerproblem zu lösen.

Wenn beide Parteien um den Eintritt in den kritischen Abschnitt konkurrieren, kann der Prozess zugelassen werden, um der anderen Partei die Möglichkeit zu geben, in den kritischen Abschnitt einzutreten.
Bevor jeder Prozess den kritischen Abschnitt betritt, setzt er seine eigene Flagge und die Wendeflagge, die eintreten darf. Danach erkennt er gleichzeitig die Flagge und die Wende der anderen Partei, um sicherzustellen, dass nur ein Prozess eintreten darf Beide Parteien beantragen gleichzeitig den Zutritt zum kritischen Abschnitt.

Unterlassener Verzicht auf das Warterecht

---

9.3 Hardware-Synchronisationsmechanismus

Für Software ist es schwierig, das Problem des gegenseitigen Ausschlusses jedes Prozesses vom Eintritt in den kritischen Abschnitt zu lösen, und es gibt große Einschränkungen. Daher stellt der Computer einige spezielle Hardwareanweisungen zur Lösung des Problems bereit.

9.3.1 Interrupts ausschalten

(1) Definition des Ausschaltens von Interrupts

• Das Ausschalten von Interrupts wurde in den Prinzipien der Computerkomposition besprochen. Es bezieht sich auf das Ändern eines Bits im PSW-Register in der CPU. Dieses Bit steuert, ob die aktuelle CPU auf den entsprechenden Interrupt reagiert. Nicht maskierbare Interrupts können nicht gestoppt werden
• Die Planung von Prozessen im Betriebssystem basiert auf Interrupts, beispielsweise Taktinterrupts.
• Während der Ausführung eines Prozesses im kritischen Abschnitt schaltet das Computersystem Interrupts ab, wodurch keine Planung ausgelöst wird und es zu keinem Prozess- oder Threadwechsel kommt.

(2) Nachteile des Ausschaltens von Interrupts

• Der Missbrauch von Endgeräten kann schwerwiegende Folgen haben
• Eine zu lange Abschaltzeit beeinträchtigt die Systemeffizienz.
• Die Methode zum Deaktivieren von Interrupts gilt nicht für Systeme mit mehreren CPUs. Das Deaktivieren von Interrupts auf einem Prozessor verhindert nicht, dass der Prozess denselben kritischen Code auf anderen Prozessoren ausführt.

---

9.3.2 Test-and-Set-Befehl (TS-Befehl)

Der TS-Befehl kann als Funktionsprozess (primitiv) betrachtet werden, dessen Ausführungsprozess unteilbar ist.

• lock hat zwei Zustände:
• • *lock=FALSE gibt an, dass die Ressource frei ist
• • *lock=TRUE zeigt an, dass die Ressource verwendet wird

Verwenden Sie TS, um kritische Abschnitte zu verwalten und eine Sperre für jede kritische Ressource festzulegen.

• Der Anfangswert ist FALSE, was darauf hinweist, dass kritische Ressourcen im Leerlauf sind.
• Bevor der Prozess den kritischen Abschnitt betritt, testet er zunächst die Sperre mit TS. Wenn sie FALSE ist, kann er in die Sperre eintreten und ihr den Wert TRUE zuweisen, wodurch die kritische Ressource geschlossen wird.

---

9.3.3 Swap-Befehl

Es wird als Swap-Anweisung bezeichnet und dient dazu, den Inhalt zweier Wörter auszutauschen.

• Legen Sie für jede kritische Ressource eine globale boolesche Variablensperre mit dem Anfangswert FALSE fest.
• Verwenden Sie die oben genannten Hardwareanweisungen, um den Prozess des gegenseitigen Ausschlusses abzuschließen
• Diese Methode führt jedoch auch dazu, dass der Zugriffsprozess kontinuierlich getestet wird und sich in einem Zustand „Besetztes Warten“ befindet, was nicht dem Prinzip des „Rechtswartens“ entspricht.

---

9.4 Semaphor-Mechanismus

9.4.1 Ganzzahliges Semaphor

Es ist als Ganzzahl S definiert, die zur Darstellung der Anzahl der Ressourcen verwendet wird. Für dieses Ganzzahl-Semaphor gibt es nur drei Operationen: Initialisierung (Zuweisen eines Anfangswerts), Warten (Dekrementieren), Signal (Inkrementieren).

• Sowohl Wait als auch Signal sind atomare Operationen und können während der Ausführung nicht unterbrochen werden.
• Wenn ein Prozess ein Semaphor ändert, kann kein anderer Prozess gleichzeitig das Semaphor ändern.

---

9.4.2 Semaphor aufzeichnen

Prozesssynchronisationsmechanismus ohne „Busy Waiting“-Phänomen

• Zusätzlich zu einem ganzzahligen Variablenwert, der die Anzahl der Ressourcen darstellt
• Es ist außerdem erforderlich, eine prozessverknüpfte Liste L hinzuzufügen, um alle Prozesse zu verknüpfen, die auf die Ressource warten.

• Die Warteoperation entspricht der P-Operation
• Die Signaloperation entspricht der V-Operation
• Nur zwei unterschiedliche Namen, die Funktionen sind genau gleich
• warte(A) = P(A)
• Signal(B) = V(A)

---

(1) Verwenden Sie Semaphore, um den gegenseitigen Ausschluss des Prozesses zu realisieren

Legen Sie einen sich gegenseitig ausschließenden Semaphor-Mutex = 1 fest und platzieren Sie dann den kritischen Abschnitt für jeden Prozess, um auf kritische Ressourcen zuzugreifen, zwischen Wait (Mutex) und Signal (Mutex).

---

(2) Verwenden Sie Semaphoren, um eine Prozesssynchronisation zu erreichen

Setzen Sie ein Synchronisationssemaphor S = 0, sodass zuerst das Anweisungssignal (S) und dann das Warten (S) ausgeführt werden müssen.