Version [22420]
Dies ist eine alte Version von BSys04Synchronisation erstellt von RonnyGertler am 2013-03-26 16:41:06.
Betriebssysteme (Betriebssystemtheorie) - Kapitel 4 - Synchronisation
Inhalte von Dr. E. Nadobnyh
4.1. Einführung
Grundbegriffe
1) Eine Nebenläufigkeit ist die parallele bzw. pseudoparallele Ausführung von Prozessen. Es gibt zwei Formen von
nebenläufigen Prozessen:
- voneinander unabhängige Prozesse, die nur um die gemeinsamen Betriebsmittel konkurrieren,
- voneinander abhängige Prozesse, die zur Erfüllung einer gemeinsamen Aufgabe kooperieren.
2) IPC (interprocess communication) ist eine Kooperation zwischen Prozessen oder Threads. IPC ist ein Oberbegriff für Synchronisation und Kommunikation.
3) Eine Synchronisation ist eine zeitliche Abstimmung der abhängigen Prozesse.
4) Eine Kommunikation ist ein Datenaustausch zwischen abhängigen Prozessen.
Klassifikation
Problem des wechselseitigen Ausschlusses
Synonyme: gegenseitiger Ausschluss, Mutual-Exclusion-Problem, Counter-Problem.
Das Problem entsteht im System mit mehreren Prozessen, die die gemeinsamen Ressourcen ändern können.
Eine verlorene Aktualisierung (Lost-Update) ist ein Datenverlust beim unkoordinierten Zugriff auf eine Ressource von mehreren nebenläufigen Prozessen.
Ein zeitkritischer Ablauf (Race Condition) ist eine Situation, bei der mehrere Prozesse:
- gemeinsame Betriebsmittel nutzen und
- das Ergebnis der Nutzung von der zeitlichen Reihenfolge der Operationen abhängt.
⇒ Demo 1.
Ein kritischer Bereich (kritischer Abschnitt) ist ein Codeabschnitt, in dem der Prozess eine gemeinsame Ressource ändert.
Ein wechselseitiger Ausschluss bedeutet, dass ein kritischer Bereich zu einer Zeit nur durch einen der Prozesse durchlaufen werden darf.
Die zeitliche Reihenfolge von Prozessen, die den kritischen Bereich betreten wollen, und die Betretensanzahl ist unwichtig.
Prozesse, die einen kritischen Abschnitt ausführen wollen, müssen warten, bis dieser frei ist. Es gibt zwei Möglichkeiten das Warten zu realisieren:
- aktives Warten und
- Blockierung.
Sperrvariable
1) Synonyme: Sperre, Lock, Spinlock.
2) Lösungsart. Diese Lösung wurde als Softwarelösung (Selbstverwaltungslösung) benannt. Dabei werden nur die traditionellen programmtechnischen Mittel verwendet.
3) Implementierung. Mehrere Prozesse oder Threads besitzen eine gemeinsame Sperrvariable, z.B.
int lock;
Der Zustand lock=0 bedeutet, dass sich kein Prozess im kritischen Bereich befindet.
4) Eintritt-Operation. Vor dem kritischen Bereich muss jeder Prozess folgende Anweisungen ausführen:
while(lock==1); lock=1;
Beide Anweisungen werden als eine Operation „Sperre testen und setzen“ bezeichnet.
5) Austritt-Operation. Hinter dem kritischen Bereich muss jeder Prozess die Operation „Sperre aufheben“ ausführen:
lock=0;
6) Aktives Warten (busy loop, Polling, Busy Waiting) ist ein ständiges Abfragen der Sperrvariable, z.B. in der Schleife:
while(lock==1);
7) Nachteil der Sperrvariable: Das ist die so genannte naive Lösung mit der gleichen Fehler-Ursache. Die Operation „Sperre testen und setzen“ kann unterbrochen werden und der Prozess kann umgeschaltet werden.
8) Nachteile der Softwarelösungen:
- Sie verwenden aktives Warten.
- Sie führen zu recht komplexen Programmsätzen, besonders bei mehreren Prozessen.
TSL -Befehl
Die meisten Prozessoren unterstützen einen speziellen Maschinenbefehl TSL (Test and Set Lock). Die Operation „Sperre testen und setzen“ wird in einem Befehl ununterbrechbar (atomar) implementiert. Diese Lösungsart wurde als Hardwarelösung benannt.
Die Nachteile:
1)Aktives Warten wird verwendet:
|
enter: |
TSL R1, LOCK | // kopiere LOCK in R1 |
| // und setze LOCK auf 1 | ||
| CMP R1, #0 | // war LOCK = 0 ? | |
| JNZ enter | // falls ≠ 0, zur Wiederholung | |
| // falls LOCK ≠ 0, ist KB gesperrt |
2) Die Lösung ist prozessorabhängig.
3) Der Maschinenbefehl wird vom Anwendungsprogrammierer kaum verwendet.
Prioritätsumkehrung
Ein aktives Warten kann die Ursache für den unendlichen Zyklus sein:
1) Ein Prozess L mit niedriger Priorität hat einen kritischen Bereich (KB) betreten.
2) Danach will ein Prozess H mit höherer Priorität den selben KB betreten.
3) Der Prozess H beginnt aktives Warten.
4) Nach Schedulingregel läuft der Prozess H immer, wenn er bereit ist.
5) Der Prozess L hat keine CPU-Zeit, um KB zu verlassen.
4.2. Semaphor
Definition
(Edsger Dijkstra, 1962)Ein Semaphor ist ein Betriebssystemobjekt für die Synchronisation von Prozessen.
Ein Semaphor realisiert das Eintritts- und Austrittsprotokoll des kritischen Bereiches und wurde zur Lösung des wechselseitigen Ausschlusses entwickelt. Ein Semaphor gehört zur Lösungsart, welche das Betriebssystem verwenden.
Analogie: Eingleisige Strecken im Eisenbahnnetz sind kritische Abschnitte. Eintritt und Austritt von Strecken müssen durch Semaphor geregelt werden.
Struktur
Ein Semaphor besitzt:
1) Eine Identität, z.B. Originalname. Mehrere Prozesse können ein Semaphor verwenden und durch die Identität von anderen Semaphoren unterscheiden.
2) Ein Markenzähler (Semaphorzähler) ist ein ganzzahliges Attribut. Er bestimmt, wie viele Prozesse noch in den kritischen Bereich dürfen. Bei der Semaphorerzeugung erhält der Zähler einen Initialwert.
3) Eine Warteschlange von blockierten Prozessen. Wenn ein Prozess nicht den kritischen Bereich betreten darf, wird er blockiert und in die Warteschlange angefügt.
4) Initialisierungsoperation bzw. Konstruktor, initialisiert den Semaphorzähler bei der Erzeugung.
5) Zwei berühmte Operationen bzw. Methoden: P und V.
Operationen
Die P -und V-Operationen werden als Eintritt- und Austritt-Operationen für einen kritischen Bereich vorgesehen.
Sie können als modernisierte Operationen „Sperre testen und setzen“ und „Sperre aufheben“ betrachtet werden. Prinzipielle Anforderungen an Operationen:
1) Die Operationen müssen unteilbar (atomar, ununterbrechbar) sein.
2) Die Operationen müssen den aufrufenden Prozess blockieren können.
Diese Anforderungen sind erfüllt, wenn die Operationen als Systemaufrufe angesprochen werden.
P – Operation
V – Operation
Legende: MZ-Markenzähler
Operationen-Synonyme
| Eintritt- Operation | Austritt- Operation | |
| von Dijkstra | P | V |
| Übersetzung | passieren | verlassen |
| Unix | sem_wait | sem_post |
| Windows | WaitForSingleObject | ReleaseSemaphore |
| Algol 68 | down | up |
| Java 5 | acquire | release |
| Binärer Semaphor | lock | unlock |
Operationen-Realisierung
Ein Semaphor kann im Betriebssystem oder in systemnaher Bibliothek realisiert werden.
Beispiel 1. Ein Semaphor, der im Betriebssystem Windows realisiert wurde, kann mittels den Systemaufrufen
angesprochen werden:
a) Erzeugung und Initialisierung
s1= CreateSemaphore(…, Initialwert, „Name“);
b) Zugang öffnen
s1 = OpenSemaphore(…, "Name");
c) Aufruf der P-Operation
WaitForSingleObject(s1, …);
d) Aufruf der V-Operation
ReleaseSemaphore(s1, ...);
Beispiel 2. Ein Semaphor, der in systemnaher Bibliothek realisiert wird, kann mittels Methodenaufrufen angesprochen werden:
a) Bibliothek
java.util.concurrent.Semaphore;
b) Erzeugung und Initialisierung
s1 = new Semaphore(Initialwert);
c) Aufruf der P-Operation
s1.acquire();
d) Aufruf der V-Operation
s1.release ();
Semaphortypen
Die Spezialisierung kommt durch den Initialisierungswert (I) des Markenzählers vor.
| I | Name und Beschreibung |
| N | Zählsemaphor (general semaphore). Ein Zählsemaphor wird z.B. in dem Erzeuger- Verbraucher-Problem verwendet. |
| 1 | Binärsemaphor (mutex, mutual exclusion). Ein binärer Semaphor wird zur Lösung des wechselseitigen Ausschlusses verwendet. |
| 0 | Schlafen/Wecken (sleep/wakeup). Der Prozess- Aufrufer wird blockiert bis er durch einen anderen Prozess aufgeweckt wird. Ein mit 0 initialisierter Semaphor wird für den Synchronisationspunkt bzw. Barriere verwendet. |
CategoryBSys
