Betriebssysteme (BS)
02. Abstraktionen und Strukturen
https://sys.cs.tu-dortmund.de/DE/Teaching/SS2021/BS/
21.04.2021
Peter Ulbrich
peter.ulbrich@tu-dortmund.de
Basierend auf Betriebssysteme von Olaf Spinczyk, Universität Osnabrück

Inhalt
Ein Blick in die Geschichte
Serielle Verarbeitung und Stapelbetrieb Mehrprogramm- und Dialogbetrieb
■
– –
■
–
Systemabstraktionen im Überblick
Prozesse
–
Speicherverwaltung
●
●
●
CPU-Zuteilung
Synchronisation und Verklemmungen Interprozesskommunikation
●
●
Arbeitsspeicher Hintergrundspeicher
21.04.2021
Betriebssysteme: 02 – Abstraktionen und Strukturen
2 / 36

Am Anfang stand die Lochkarte
Es gibt sie schon seit 1725 – zur Webstuhlsteuerung. Herman Hollerith nutzte sie 1890 für eine Volkszählung
aus seiner Firma und zwei weiteren ging später IBM hervor
■ ■
–
■
Sie wurde bis in die 70er Jahre als vielseitiger Speicher eingesetzt.
21.04.2021 Betriebssysteme: 02 – Abstraktionen und Strukturen 3 / 36

Erste elektronische Universalrechner
Beispiel:
Beispiel:
ENIAC, 1946 ENIAC, 1946
US-Armee, Berechnung
US-Armee, Berechnung
ballistischer Tabellen
ballistischer Tabellen
21.04.2021 Betriebssysteme: 02 – Abstraktionen und Strukturen 4 / 36

Erste elektronische Universalrechner
Ein Rechenmonster!
■ Größe: Größe:
10mx17mx2,7m
■
10m x 17m x 2,7m
■ Gewicht: Gewicht:
27t
■
27t
■ Leistung: Leistung:
174kW (> 17.000 Röhren!)
■
174kW (> 17.000 Röhren!)
■ Preis: Preis:
■ Geschwindigkeit: Geschwindigkeit:
$ 468.000 (heute: ~ $6,36 Mio.)
■
$ 468.000 (heute: ~ $6,36 Mio.)
■
500 Additionen pro Sekunde
Beispiel:
Beispiel:
ENIAC, 1946 ENIAC, 1946
US-Armee, Berechnung
US-Armee, Berechnung
ballistischer Tabellen
ballistischer Tabellen
Ein Rechenmonster!
500 Additionen pro Sekunde
21.04.2021 Betriebssysteme: 02 – Abstraktionen und Strukturen 5 / 36

Serielle Verarbeitung (ab 1945)
Programmierung
i.d.R. in Maschinencode
Eingabe über Lochkartenleser, Ausgaben über Drucker Fehleranzeige durch Kontrolllämpchen
■
– – –
■
–
■
–
■
–
Rechnerzeitzuteilung auf Papierterminkalender
Rechnerzeitverschwendung durch zu großzügige Reservierung oder Abbruch wegen Fehler
Minimale Auslastung der CPU
Die meiste Zeit verbrauchten langsame E/A-Geräte (Lochkarten, Drucker)
Erste Systemsoftware in Form von Programmbibliotheken
Binder, Lader, Debugger, Gerätetreiber, …
21.04.2021 Betriebssysteme: 02 – Abstraktionen und Strukturen 6 / 36

Einfache Stapelsysteme (ab 1955)
Verringerten die Häufigkeit manueller Betriebseingriffe
Die ersten Betriebssysteme: Residente Monitore
Interpretation von Job-Steuerbefehlen Laden und Ausführen von Programmen Geräteansteuerung
$END
■ ■
– – –
$FTN $FTN
$FTN $FTN
$FTN $FTN
$FTN
$RUN $LOAD
Eingabedaten
$FTN
$FTN $JOB
Fortran Programmtext
$FTN $FTN
$FTN $FTN
$FTN $FTN
NEU: Steuerkarten NEU: Steuerkarten
(engl. control cards) (engl. control cards)
21.04.2021
Betriebssysteme: 02 – Abstraktionen und Strukturen
7 / 36
Ein Stapel Lochkarten zur
Ein Stapel Lochkarten zur
Übersetzung und Ausführung
Übersetzung und Ausführung
eines FORTRAN-Programms
eines FORTRAN-Programms

Einfache Stapelsysteme (ab 1955)
Arbeitsspeicher
Der Monitor bliebt dauerhaft Der Monitor bliebt dauerhaft
Gerätetreiber
Gerätetreiber
Sequentielle
Sequentielle
Job-Steuerung
Job-Steuerung
Steuersprach-
Steuersprach-
interpreter
interpreter
Benutzer-
Benutzer-
programm-
programm-
bereich
bereich
im Speicher, während er ein
im Speicher, während er ein
Anwendungsprogramm nach
Anwendungsprogramm nach
dem anderen ausführte.
dem anderen ausführte.
Monitor
21.04.2021 Betriebssysteme: 02 – Abstraktionen und Strukturen 8 / 36

Einfache Stapelsysteme (ab 1955)
Arbeitsspeicher
Der Monitor bliebt dauerhaft Der Monitor bliebt dauerhaft
Gerätetreiber
Gerätetreiber
Sequentielle
Sequentielle
Job-Steuerung
Job-Steuerung
Steuersprach-
Steuersprach-
interpreter
interpreter
Benutzer-
Benutzer-
programm-
programm-
bereich
bereich
■
– –
–
schreibt in den Speicherbereich des residenten Monitors
greift auf den Kartenleser direkt zu und interpretiert Steuerbefehle als Daten.
im Speicher, während er ein
im Speicher, während er ein
Anwendungsprogramm nach
Anwendungsprogramm nach
dem anderen ausführte.
dem anderen ausführte.
Probleme durch fehlerhafte Anwendungen:
Programm terminiert nicht,
Monitor
21.04.2021 Betriebssysteme: 02 – Abstraktionen und Strukturen 8 / 36

Einfache Stapelsysteme (ab 1955) Lösungen:
Zeitgeberbaustein (timer) liefert Unterbrechungen (interrupts)
Fallen (traps) für fehlerhafte Programme
Arbeitsspeicher
Unterbrechungs-
Unterbrechungs-
mechanismus
mechanismus
Gerätetreiber
Gerätetreiber
Sequentielle
Sequentielle
Job-Steuerung
Job-Steuerung
Steuersprach-
Steuersprach-
interpreter
interpreter
Benutzer-
Benutzer-
programm
programm
unbenutzt
unbenutzt
■
■
Monitor
0000
fence register
02FF 0300
0300
0300
– Schutzgatterregister
(engl. fence register)
realisiert primitiven Speicherschutz
Privilegierter Arbeitsmodus
der CPU (supervisor mode)
Deaktivierung des Schutzgatters Ein-/Ausgabe
–
timer
timer
● ●
1FFF
21.04.2021
Betriebssysteme: 02 – Abstraktionen und Strukturen
9 / 36

Der Ein-/Ausgabe-Flaschenhals
Problem: CPU ist schneller als Kartenleser und Drucker
kostbare Rechenzeit wird durch (aktives) Warten verschwendet
■
–
■
– –
Lösung 1: Off-line processing (entkoppelte Ein-/Ausgabe)
dank Bandlaufwerken
Parallelisierung von Ein-/Ausgaben durch mehrere Satellitenrechner
Satellitenrechner für Eingabe
(ggf. mehrere)
CPU (liest/schreibt ausschließlich von/auf Band)
Satellitenrechner für Ausgabe
(ggf. mehrere)
21.04.2021
Betriebssysteme: 02 – Abstraktionen und Strukturen
10 / 36
A. Tanenbaum [2]

Der Ein-/Ausgabe-Flaschenhals
Problem: CPU ist schneller als Kartenleser und Drucker
kostbare Rechenzeit wird durch (aktives) Warten verschwendet
■
–
■
–
– –
Lösung 2: Spooling (Spulen, Puffern)
dank Plattenlaufwerken (wahlfreier Zugriff), Direct Memory Access und Unterbrechungen
Berechnungen und Ein-/Ausgaben werden dabei parallelisiert. Regeln für Prozessorzuteilung
Wartende Jobs Ergebnisdaten
Kartenleser Platte Drucker
CPU
21.04.2021 Betriebssysteme: 02 – Abstraktionen und Strukturen 11 / 36

Mehrprogrammbetrieb (ab 1965)
Trotz spooling nutzt ein einzelnes Programm die CPU nicht effizient
CPU-Stöße (CPU bursts) und E/A-Stöße (I/O bursts), bei denen die CPU warten muss, wechseln sich ab.
■
–
Programm A
Einprogrammbetrieb
CPU
E/A
CPU
E/A
■
Beim Mehrprogrammbetrieb bearbeitet die CPU mehrere Aufträge gleichzeitig:
Mehrprogrammbetrieb
Zeit
CPU
E/A
CPU
E/A
Programm A Programm B AundB
CPU
E/A
CPU
E/A
CPU
CPU
E/A
CPU
CPU
E/A
Zeit
21.04.2021
Betriebssysteme: 02 – Abstraktionen und Strukturen
12 / 36

Mehrprogrammbetrieb (ab 1965)
Trotz spooling nutzt ein einzelnes Programm die CPU nicht effizient
■
–
CPU-Stöße (CPU bursts) und E/A-Stöße (I/O bursts), bei denen die
Das Betriebssystem wird immer komplexer:
Das Betriebssystem wird immer komplexer:
CPU warten muss, wechseln sich ab.
■ Umgang mit nebenläuEfiignepnroEgr/aAm-Amkbteivtirtieäbten Umgang mit nebenläufigen E/A-Aktivitäten
■
Programm A
■ Interne Verwaltung von Programmen in Ausführung (Prozesse) Interne Verwaltung von Programmen in Ausführung (Prozesse)
■ Prozessorzuteilung (scheduling)
Beim MPerohzrepsrsoogrrzaumtemilubnegtr(siecbhebdeualirnbge) itet die CPU mehrere Aufträge
Programm A Programm B AundB
CPU E/A CPU E/A
■ Verwaltung des Arbeitsspeichers für mehrere Programme Verwaltung des Arbeitsspeichers für mehrere Programme
■
■
■
■
Zeit
gleichzeitig:
■ Mehrbenutzerbetrieb: Sicherheit und Abrechnung (accounting) Mehrbenutzerbetrieb: Sicherheit und Abrechnung (accounting)
■
Mehrprogrammbetrieb
CPU
E/A
CPU
E/A
CPU
E/A
CPU
E/A
CPU
CPU
E/A
CPU
CPU
E/A
Zeit
21.04.2021
Betriebssysteme: 02 – Abstraktionen und Strukturen
13 / 36

Mehrprogrammbetrieb (ab 1965)
■
Speicherverwaltung
– Den zu startenden Programmen muss dynamisch freier Speicher zugewiesen werden.
Speicherschutz
– Einfaches Schutzgatter reicht nicht mehr, um einzelne Programme zu isolieren. Lösung: einfache MMU („Memory Management Unit“)
Prozessverwaltung
Jedes „Programm in Ausführung“ besitzt einen Kontext. Beim Prozesswechsel muss dieser ausgetauscht werden.
Arbeitsspeicher
CPU und MMU
■
bounds registers
Lo
Hi
instruction pointer
21.04.2021 Betriebssysteme: 02 – Abstraktionen und Strukturen
14 / 36
Betriebssystem
Betriebssystem
5000
—
—
Programm A
Programm A
(text, data, bss, stack)
(text, data, bss, stack)
(text, data, bss, stack)
F000
62E2
E340
0000
Kontext A
Lo Hi IP SP
4000
Kontext B
Lo Hi IP SP
5000
4000
4000
5000
5000
430A
430A
■
–
3FFF 4000
4FFF 5000
stack pointer
EFFF
FFFF
Programm B
Programm B
(text, data, bss, stack)
4EE0
4EE0
unbenutzt
unbenutzt

Dialogbetrieb (ab 1970)
Neue Ein- und Ausgabegeräte erlauben interaktive Software
Tastatur, Monitor, später Maus
DEC LA36
■
–
■
–
–
■
–
■
Platten und Dateisysteme erlauben jederzeit Zugriff auf Programme und Daten
Time-Sharing-Betrieb
ermöglicht akzeptable Antwortzeiten für interaktive Nutzer
Zeitgeber-Unterbrechungen sorgen für Verdrängung (zu) lang laufender Prozesse
Systemprogramme erlauben auch interaktive SW-Entwicklung
Editor, Shell, Übersetzer, Debugger
Quelle: DIGITAL Computing Timeline
21.04.2021 Betriebssysteme: 02 – Abstraktionen und Strukturen 15 / 36

UNIX-Systemstruktur
Aufruf
Bibliotheken
Systemaufrufschnittstelle
Dateisubsystem
buffer cache
Trap
UNIX-Applikation
UNIX-Applikation
user mode supervisor mode
Zeichen
Block
Gerätetreiber
21.04.2021
Betriebssysteme: 02 – Abstraktionen und Strukturen
16 / 36
Hardwaresteuerung
Prozess- kontroll- subsystem
IPC
Scheduler
Speicher- verwaltung

Windows-Systemstruktur
LPC
Trap
Win16-Klient
Win16-Klient
WoW
user mode
Executive
Sicherheits-
referenz- verwaltung verwaltung Prozedur- Speicher- Ein-/Ausgabe
OS/2-Klient
Win32-Klient
POSIX-Klient
OS/2-Klient
Win32-Klient
POSIX-Klient
OS/2-Subsystem
POSIX-Subsystem
OS/2-Subsystem
POSIX-Subsystem
Win32-Subsystem
monitor
supervisor mode
aufruf
Kernel
Hardware Abstraction Layer (HAL)
verwaltung
Treiber und Dateisystem
Objekt-
Prozess- Lokaler Virtuelle
21.04.2021
Betriebssysteme: 02 – Abstraktionen und Strukturen
17 / 36

Ein Prozess …
Horning/Randell, Process Structuring
■
■
Dennis/van Horn, Programming Semantics for Multiprogrammed Computations
■
Habermann, Introduction to Operating System Design
„… P ist ein Tripel (S, f, s), wobei S einen Zustandsraum, f eine Aktionsfunktion und s ⊂ S die Anfangszustände des Prozesses P bezeichnen. Ein Prozess erzeugt Abläufe, die durch die Aktionsfunktion generiert werden können.“
„… ist das Aktivitätszentrum innerhalb einer Folge von Elementaroperationen. Damit wird ein Prozess zu einer abstrakten Einheit, die sich durch die Instruktionen eines abstrakten Programms bewegt, wenn dieses auf einem Rechner ausgeführt wird.“
„… wird durch ein Programm kontrolliert und benötigt zur Ausführung dieses Programms einen Prozessor.“
21.04.2021 Betriebssysteme: 02 – Abstraktionen und Strukturen 19 / 36

Ein Prozess …
…ist ein Programm in Ausführung
unbekannte Referenz, Informatikfolklore Dazu gehört ein Prozesskontext, i.d.R. …
Speicher: Code-, Daten und Stapelsegment (text, data, stack) Prozessorregisterinhalte
■
–
■
– –
Instruktionszeiger Stapelzeiger Vielzweckregister …
Prozesszustand
Benutzerkennung
Zugriffsrechte
Aktuell belegte Betriebsmittel
Dateien, E/A-Geräte, u.s.w. …
● ● ● ●
wird repräsentiert durch einen
●
wird repräsentiert durch einen
Prozesskontrollblock
Prozesskontrollblock
– – – –
–
(process control block, PCB)
(process control block, PCB)
21.04.2021
Betriebssysteme: 02 – Abstraktionen und Strukturen
20 / 36

Prozessmodell
Mehrprogrammbetrieb
Nebenläufige Prozesse
Multiplexing der CPU Prozess
A
A
B
B
C
C
D
D
Technische Sicht
Technische Sicht
• 1 Instruktionszeiger • 1 Instruktionszeiger
• Kontextwechsel • Kontextwechsel
21.04.2021
Betriebssysteme: 02 – Abstraktionen und Strukturen
21 / 36
ABD
D C B A
Konzeptionelle Sicht
Konzeptionelle Sicht
• 4 unabhängige • 4 unabhängige
sequentielle
sequentielle
Kontrollflüsse
Kontrollflüsse
C
Realzeit-Sicht
• Zu jedem Zeitpunkt • Zu jedem Zeitpunkt
ist nur ein Prozess
ist nur ein Prozess
aktiv (1 CPU)
aktiv (1 CPU)
• Gantt-Diagramm • Gantt-Diagramm
Zeit
Realzeit-Sicht

Prozessverhalten und -zustände (3)
RUNNING
A
Prozesszustände
Prozesszustände
■ RUNNING RUNNING
– Prozess wird gerade ausgeführt Prozess wird gerade ausgeführt
■ READY READY
■
A B C
CPU
BLOCKED
READY
BC
■
■
–
– Prozess ist rechenbereit, wartet Prozess ist rechenbereit, wartet
–
■ BLOCKED BLOCKED
auf die CPU
auf die CPU
– Prozess wartet auf die Prozess wartet auf die
–
Beendigung einer E/A-Aktivität
Beendigung einer E/A-Aktivität
jetzt
Zeit
21.04.2021
Betriebssysteme: 02 – Abstraktionen und Strukturen
22 / 36

Prozessverhalten und -zustände (3)
A B C
21.04.2021
Betriebssysteme: 02 – Abstraktionen und Strukturen
23 / 36
BLOCKED
A
READY
B
RUNNING
C
Prozess A hat einen E/A-Vorgang Prozess A hat einen E/A-Vorgang
gestartet und ist in den Zustand
gestartet und ist in den Zustand
BLOCKED übergegangen. Da A die
BLOCKED übergegangen. Da A die
CPU nun nicht benötigt, hat das
CPU nun nicht benötigt, hat das
Betriebssystem den Prozess C Betriebssystem den Prozess C
ausgewählt und von READY in
ausgewählt und von READY in
RUNNING überführt. Es fand ein
RUNNING überführt. Es fand ein
Kontextwechsel von A zu C statt. Kontextwechsel von A zu C statt.
CPU
E/A
CPU
jetzt Zeit

Prozessverhalten und -zustände (3)
RUNNING
B
C hat die CPU zu lange besessen,
C hat die CPU zu lange besessen,
wurde verdrängt und ist daher wurde verdrängt und ist daher
nun wieder im Zustand READY.
nun wieder im Zustand READY.
BLOCKED
READY
AC
Zeitscheibe abgelaufen
Damit kann jetzt endlich auch
Damit kann jetzt endlich auch
Prozess B bearbeitet werden und Prozess B bearbeitet werden und
wird RUNNING.
wird RUNNING.
CPU
E/A
A B C
CPU
jetzt Zeit
CPU
21.04.2021
Betriebssysteme: 02 – Abstraktionen und Strukturen
24 / 36

Prozessverhalten und -zustände (3)
RUNNING
B
A B C
CPU
BLOCKED
READY
AC
E/A-Operation fertig
CPU
jetzt Zeit
Die E/A-Operation von A ist nun Die E/A-Operation von A ist nun
abgeschlossen. Daraufhin wird A abgeschlossen. Daraufhin wird A
nun READY und wartet auf die
nun READY und wartet auf die
Zuteilung der CPU.
Zuteilung der CPU.
CPU
E/A
21.04.2021
Betriebssysteme: 02 – Abstraktionen und Strukturen
25 / 36

CPU-Zuteilung (Scheduling)
neue Aufträge
beendete Aufträge
21.04.2021
Betriebssysteme: 02 – Abstraktionen und Strukturen
26 / 36
verdrängte Aufträge
Warteschlange
CPU
CPU
Ein einzelner Scheduling-Algorithmus charakterisiert sich durch die Ein einzelner Scheduling-Algorithmus charakterisiert sich durch die
Reihenfolge von Prozessen in der Warteschlange und die Bedingungen,
Reihenfolge von Prozessen in der Warteschlange und die Bedingungen,
unter denen die Prozesse der Warteschlange zugeführt werden.
unter denen die Prozesse der Warteschlange zugeführt werden.

CPU-Zuteilung (Scheduling) (auch Ablaufplanung)
Sorgt für den geordneten Ablauf konkurrierender Prozesse
Grundsätzliche Fragestellungen
Welche Arten von Ereignissen führen zur Verdrängung? In welcher Reihenfolge sollen Prozesse ablaufen?
■ ■
– –
■
– –
Ziele eines Scheduling-Algorithmus
benutzerorientiert, z.B. kurze Antwortzeiten systemorientiert, z.B. optimale CPU-Auslastung
Kein Scheduling-Algorithmus kann alle Bedürfnisse erfüllen 21.04.2021 Betriebssysteme: 02 – Abstraktionen und Strukturen 27 / 36
■

Prozesssynchronisation
Beispiel: unkoordinierter Druckerzugriff
■
Prozess A
Prozess B
…
…
print(“Hallo Otto\n”); print(“Hallo Otto\n”);
print(“Ruf mich an.\n”); print(“Ruf mich an.\n”);
print(“Tel.: 420815\n”); print(“Tel.: 420815\n”);
…
…
…
…
print(“Karl-“); print(“Karl-“);
print(“Ich mag dich.\n”); print(“Ich mag dich.\n”);
…
…
Hallo Karl-Otto Ruf mich an. Ich mag dich. Tel.: 420815
21.04.2021
Betriebssysteme: 02 – Abstraktionen und Strukturen
28 / 36

Prozesssynchronisation
Ursache: Kritische Abschnitte Lösungsmöglichkeit: Gegenseitiger Ausschluss
Mutex-Abstraktion
Prozess A Prozess B
■ ■
–
…
…
lock(&printer_mutex);
lock(&printer_mutex);
print(“Hallo Otto\n”);
print(“Hallo Otto\n”);
print(“Ruf mich an.\n”);
print(“Ruf mich an.\n”);
print(“Tel.: 420815\n”);
print(“Tel.: 420815\n”);
unlock(&printer_mutex);
unlock(&printer_mutex);
…
…
…
…
lock(&printer_mutex);
lock(&printer_mutex);
print(“Karl-“);
print(“Karl-“);
print(“Ich mag dich.\n”);
print(“Ich mag dich.\n”);
unlock(&printer_mutex);
unlock(&printer_mutex);
…
…
Wenn sich einer der Prozesse A oder B zwischen lock und unlock befindet, Wenn sich einer der Prozesse A oder B zwischen lock und unlock befindet,
kann der jeweils andere das lock nicht passieren und blockiert dort, bis der kann der jeweils andere das lock nicht passieren und blockiert dort, bis der
kritische Abschnitt wieder frei ist (unlock). kritische Abschnitt wieder frei ist (unlock).
21.04.2021 Betriebssysteme: 02 – Abstraktionen und Strukturen 29 / 36

Verklemmungen (Deadlocks)
Es gilt: „Rechts vor links!“ Es gilt: „Rechts vor links!“
Kein Auto darf fahren.
Kein Auto darf fahren.
Verklemmungssituationen
Verklemmungssituationen
wie diese kann es auch
wie diese kann es auch
bei Prozessen geben.
bei Prozessen geben.
21.04.2021 Betriebssysteme: 02 – Abstraktionen und Strukturen 30 / 36

Interprozesskommunikation
… ermöglicht die Zusammenarbeit mehrerer Prozesse
lokal (local), z.B. Drucker-Dämon, X-Server
entfernt (remote), z.B. Webserver, Datenbank-Server, ftp-Server
■
– –
■
–
„Client/Server-Systeme“ Abstraktionen/Programmiermodelle
Gemeinsamer Speicher
mehrere Prozesse dürfen gleichzeitig denselben Speicherbereich nutzen
zusätzlich Synchronisation notwendig Nachrichtenaustausch
Semantik eines Faxes (verschickt wird die Kopie einer Nachricht) synchron oder asynchron
–
●
●
●
●
●
21.04.2021 Betriebssysteme: 02 – Abstraktionen und Strukturen 31 / 36

Inhalt
Ein Blick in die Geschichte
Serielle Verarbeitung und Stapelbetrieb Mehrprogramm- und Dialogbetrieb
■
– –
■
–
Systemabstraktionen im Überblick
Prozesse
●
●
●
CPU-Zuteilung
Synchronisation und Verklemmungen Interprozesskommunikation
–
Speicherverwaltung
●
●
Arbeitsspeicher Hintergrundspeicher
21.04.2021
Betriebssysteme: 02 – Abstraktionen und Strukturen
32 / 36

Die Speicherhierarchie
●
steigende Zugriffszeiten
●
●
steigende Kapazität
●
●
sinkender Preis pro Bit
●
steigende Kapazität
sinkender Preis pro Bit
Intern: Register Cache
Vordergrundspeicher: RAM/ROM/FLASH
Hintergrundspeicher: Festplatte, Solid-State-Disk
Wechselspeicher: Magnetband, DVD, Blu-ray, USB-Stick
Netzwerkspeicher: Netzwerklaufwerk/-dateisystem, Cloud-Speicher
durch das
durch das
Speichereigenschaften
Speichereigenschaften
steigende Zugriffszeiten
Lokalitätsprinzip! Lokalitätsprinzip!
21.04.2021
Betriebssysteme: 02 – Abstraktionen und Strukturen
33 / 36
Sehr wirtschaftlich
Sehr wirtschaftlich

Speicherverwaltung
Adressabbildung
Logische Adressen auf physische Adressen
Gestattet Relokation von Code u. Daten Platzierungsstrategie
In welcher Lücke soll Speicher reserviert werden?
Kompaktifizierung verwenden? Wie minimiert man das
Arbeitsspeicher
Betriebssystem
Betriebssystem
Programm A
Programm A
(text, data, bss, stack)
(text, data, bss, stack)
unbenutzt
unbenutzt
Programm B
Programm B
(text, data, bss, stack)
(text, data, bss, stack)
unbenutzt
unbenutzt
Programm C
Programm C
(text, data, bss, stack)
(text, data, bss, stack)
■
–
–
■
–
– –
■
–
0000
Fragmentierungsproblem? Ersetzungsstrategie
Welcher Speicherbereich könnte sinnvoll ausgelagert werden?
?
Programm D
Programm D
(text, data, bss, stack)
(text, data, bss, stack)
FFFF
21.04.2021 Betriebssysteme: 02 – Abstraktionen und Strukturen 34 / 36

Hintergrundspeicher
bin
Abbildung
Das Betriebssystem stellt
Das Betriebssystem stellt
den Anwendungen die
den Anwendungen die
logische Sicht zur logische Sicht zur
Verfügung und muss
Verfügung und muss
diese effizient realisieren.
diese effizient realisieren.
usr
local
/
Logische Sicht
Verzeichnis
pu foo hsc js
Datei
Physikalische Sicht
Rotationsachse
…
home
großer Datenmengen.
großer Datenmengen.
bs.pdf
Festplatte mit
Festplatte mit
6 Oberflächen
Spuren
Schreib-/Leseköpfe
Dateisysteme erlauben die Dateisysteme erlauben die
dauerhafte Speicherung
dauerhafte Speicherung
6 Oberflächen
Sektor
21.04.2021
Betriebssysteme: 02 – Abstraktionen und Strukturen 35 / 36

Fazit: Das Betriebssystem …
verwaltet Betriebsmittel, insbesondere CPU und Speicher
stellt Abstraktionen zur Verfügung, z.B. …
Prozesskonzept
Dateien und Verzeichnisse
■ ■
– –
■
–
ist für ein bestimmtes Anwendungsprofil optimiert
allen Anwendungen 100% gerecht zu werden ist unmöglich
Betriebssysteme, typische Anwendungen und Hardware haben
Betriebssysteme, typische Anwendungen und Hardware haben
sich Hand in Hand im Laufe der vergangenen Jahrzehnte
sich Hand in Hand im Laufe der vergangenen Jahrzehnte
entwickelt. Die heute üblichen Systemabstraktionen sind das entwickelt. Die heute üblichen Systemabstraktionen sind das
Ergebnis einer Evolution, deren Ende nicht in Sicht ist. Ergebnis einer Evolution, deren Ende nicht in Sicht ist.
21.04.2021 Betriebssysteme: 02 – Abstraktionen und Strukturen 36 / 36

Betriebssysteme (BS)
03. Prozesse
https://sys.cs.tu-dortmund.de/DE/Teaching/SS2021/BS/
28.04.2021
Peter Ulbrich
peter.ulbrich@tu-dortmund.de
Basierend auf Betriebssysteme von Olaf Spinczyk, Universität Osnabrück

Wiederholung
Prozesse sind Programme in Ausführung
Dynamisch, nicht statisch Abwechselnde Folge von
■
– –
■
■
–
RUNNING A
CPU-Stößen und E/A-Stößen
benötigen Betriebsmittel des Rechners
– CPU, Speicher, E/A-Geräte haben einen Zustand
READY, RUNNING, BLOCKED
unterliegen der Kontrolle des Betriebssystems
Betriebsmittel-Zuteilung Betriebsmittel-Entzug
BLOCKED
READY BC
■
■
– –
werden konzeptionell als unabhängige, nebenläufige Kontrollflüsse betrachtet
28.04.2021 03 – Prozesse
2

Inhalt
Das UNIX-Prozessmodell
Shells und E/A UNIX-Philosophie Prozesserzeugung Prozesszustände
■
– – – –
■
– – –
■
– –
Leichtgewichtige Prozessmodelle
„Gewicht“ von Prozessen Leichtgewichtige Prozesse Federgewichtige Prozesse
Systeme mit leichtgewichtigen Prozessen
Windows Linux
Tanenbaum
2.1: Prozesse
10.1-10.3: UNIX u. Linux
Silberschatz
3.1-3.3: Process Concept 21.4: Linux
Tanenbaum
2.2: Threads
Silberschatz
4: Multithreaded Prog.
28.04.2021 03 – Prozesse 3

Inhalt
Das UNIX-Prozessmodell
Shells und E/A UNIX-Philosophie Prozesserzeugung Prozesszustände
■
– – – –
■
– – –
Leichtgewichtige Prozessmodelle
„Gewicht“ von Prozessen Leichtgewichtige Prozesse Federgewichtige Prozesse
28.04.2021
03 – Prozesse 4

UNIX (K. Thompson, D. Ritchie, 1968)
■ ■
–
■
–
■
Version 3 in der Programmiersprache C realisiert
Eine lange Geschichte … Ursprung: Bell Labs
Alternative zu „Multics“
Version 1 entstand auf einer DEC PDP 7
Assembler, 8K 18-Bit-Worte
Matias Fjeld, CC BY-SA 3.0
28.04.2021 03 – Prozesse 5

28.04.2021 03 – Prozesse
Eraserhead1, CC BY-SA 3.0
6
Die Geschichte von UNIX

UNIX-Prozesse …
sind primäres Strukturierungskonzept für Aktivitäten
Anwendungsprozesse und Systemprozesse
■
–
■
–
Elternprozess → Kindprozess
■
bilden eine Prozess-Hierarchie: swapper (PID 0)
können leicht und schnell weitere Prozesse erzeugen
Jeder UNIX-Prozess hat eine
Jeder UNIX-Prozess hat eine
eindeutige Nummer (Prozess-ID).
eindeutige Nummer (Prozess-ID).
Die PID des Elternprozesses heißt Die PID des Elternprozesses heißt
PPID. PPID.
Der init-Prozess liest aus /etc/inittab Der init-Prozess liest aus /etc/inittab
die Liste der Terminals und startet für
die Liste der Terminals und startet für
jedes das Programm getty, welches jedes das Programm getty, welches
die Einwahl mittels login erlaubt. die Einwahl mittels login erlaubt.
getty tty0
login
bash
init (PID 1)
getty tty1
firefox
pagedaemon (PID 2)
getty tty2
Auch die Shell nutzt Prozesse: Auch die Shell nutzt Prozesse:
Jedes Kommando wird als eigener
Jedes Kommando wird als eigener
grep BS file.c
Kindprozess ausgeführt.
Kindprozess ausgeführt.
28.04.2021
03 – Prozesse
7

UNIX-Shells
Schale (shell), die den Kern (kernel) umgibt
Eingeführt mit Multics (um 1964) als Dialogstation-Kommandointerpreter
■
–
■
–
Textbasierte Nutzerschnittstelle zum Starten von Kommandos:
Suche im Dateisystem entsprechend $PATH (z.B. /usr/bin:/bin:…)
ulbrich@ios:~$ which emacs ulbrich@ios:~$ which emacs
–
–
–
Jedes ausgeführte Kommando ist ein eigener Kindprozess
Typischerweise blockiert die Shell bis das Kommando terminiert
Man kann aber auch Kommandos stoppen und fortsetzen (job control) oder sie im Hintergrund ausführen …
/usr/bin/emacs
/usr/bin/emacs
28.04.2021 03 – Prozesse 8
Das Kommando which zeigt Das Kommando which zeigt
an, wo ein bestimmtes an, wo ein bestimmtes
Kommando gefunden wird.
Kommando gefunden wird.

UNIX-Shells: Job Control
Ctrl-Z
ulbrich@ios:~$ emacs foo.c ulbrich@ios:~$ emacs foo.c
[1]+ Stopped emacs foo.c
ulbrich@ios:~$ kate bar.c & ulbrich@ios:~$ kate bar.c &
[2] 19504
[2] 19504
ulbrich@ios:~$ jobs ulbrich@ios:~$ jobs
[1]+ Stopped
emacs foo.c
[1]+ Stopped
emacs foo.c
[2]- Running
kate bar.c &
[2]- Running
kate bar.c &
ulbrich@ios:~$ bg %1 ulbrich@ios:~$ bg %1
[1]+ emacs foo.c &
[1]+ emacs foo.c &
ulbrich@ios:~$ jobs ulbrich@ios:~$ jobs
[1]- Running
emacs foo.c &
[1]- Running
emacs foo.c &
[2]+ Running
kate bar.c &
[2]+ Running
kate bar.c &
●
Kommando wird gestartet
●
●
die Shell blockiert die Shell blockiert
●
●
Durch das & am Ende Durch das & am Ende
●
●
bg schickt ein gestopptes bg schickt ein gestopptes
●
Kommando wird gestartet
●
Kommando wird gestoppt
●
●
die Shell läuft weiter die Shell läuft weiter
●
Kommando wird gestoppt
[1]+ Stopped emacs foo.c
wird kate im Hintergrund wird kate im Hintergrund
gestartet
gestartet
●
jobs zeigt alle gestarteten jobs zeigt alle gestarteten
●
Kommandos an
Kommandos an
Kommando in den
Kommando in den
Hintergrund
Hintergrund
28.04.2021
03 – Prozesse 9

Standard-E/A-Kanäle von Prozessen
Normalerweise verbunden mit dem Terminal, in dem die Shell läuft, die den Prozess gestartet hat:
■
–
–
–
Standard-Eingabe
Standard-Ausgabe
Standard-Fehlerausgabe
Zum Lesen von Benutzereingaben (Tastatur)
Textausgaben des Prozesses (Terminal-Fenster)
Separater Kanal für Fehlermeldungen (normalerweise auch das Terminal)
■
■
Praktisch alle Kommandos akzeptieren auch Dateien als Ein- oder Ausgabekanäle (statt des Terminals) → Operatoren
Shells bieten eine einfache Syntax, um die Standard-E/A-Kanäle umzuleiten …
28.04.2021 03 – Prozesse 10

Standard-E/A-Kanäle umleiten
Das gleiche noch etwas kompakter …
28.04.2021 03 – Prozesse 11
Umleitung der Standard-Ausgabe
Umleitung der Standard-Ausgabe
in die Datei d1 mit > in die Datei d1 mit >
ulbrich@ios:~$ ls -l > d1 ulbrich@ios:~$ ls -l > d1
ulbrich@ios:~$ grep “May 4” < d1 > d2 ulbrich@ios:~$ grep “May 4” < d1 > d2
ulbrich@ios:~$ wc < d2 ulbrich@ios:~$ wc < d2 2 18 118 2 18 118 ulbrich@ios:~$ ls -l | grep "May 4" | wc ulbrich@ios:~$ ls -l | grep "May 4" | wc 2 18118 2 18 118 Umleitung der Standard-Eingabe Umleitung der Standard-Eingabe auf die Datei d2 mit < auf die Datei d2 mit < Mit | (pipe) verbindet die Shell die Standard-Ausgabe Mit | (pipe) verbindet die Shell die Standard-Ausgabe des linken mit der Standard-Eingabe des rechten Prozesses. des linken mit der Standard-Eingabe des rechten Prozesses. Die UNIX-Philosophie Doug McIlroy, der Erfinder der UNIX-Pipes, fasste die Philosophie hinter UNIX einmal wie folgt zusammen: “ This is the Unix philosophy: Write programs that do one thing and do it well. Write programs to work together. Write programs to handle text streams, because that is a universal interface.” – – – Für gewöhnlich wird das abgekürzt: Für gewöhnlich wird das abgekürzt: „Do one thing, do it well.“ „Do one thing, do it well.“ 28.04.2021 03 - Prozesse 12 Einige Systemaufrufe der UNIX-Prozesssteuerung Ein erster Überblick ... getpid(2) getppid(2) getuid(2) fork(2) exit(3), _exit(2) wait(2) execve(2) liefert PID des laufenden Prozesses liefert PID des Elternprozesses (PPID) liefert die Benutzerkennung des laufenden Prozesses (UID) erzeugt neuen Kindprozess beendet den laufenden Prozess wartet auf die Beendigung eines Kindprozesses lädt und startet ein Programm im Kontext des laufenden Prozesses ■ ■ ■ ■ ■ ■ ■ 28.04.2021 03 - Prozesse 13 Der fork() Systemaufruf ■ ■ – ■ – – – – System Call: pid_t fork (void) System Call: pid_t fork (void) ■ DupliziertdenlaufendenProzess(Prozesserzeugung!) Dupliziert den laufenden Prozess (Prozesserzeugung!) ■ DerKindprozesserbt... Der Kindprozess erbt ... – Adressraum (code, data, bss, stack) Adressraum (code, data, bss, stack) – Benutzerkennung Benutzerkennung – Standard-E/A-Kanäle Standard-E/A-Kanäle – Prozessgruppe, Signaltabelle (dazu später mehr) Prozessgruppe, Signaltabelle (dazu später mehr) – Offene Dateien, aktuelles Arbeitsverzeichnis (dazu viel später mehr) Offene Dateien, aktuelles Arbeitsverzeichnis (dazu viel später mehr) ■ Nichtkopiertwird... Nicht kopiert wird ... Process ID (PID), Parent Process ID (PPID) Process ID (PID), Parent Process ID (PPID) anhängige Signale, Accounting-Daten, ... anhängige Signale, Accounting-Daten, ... – ? – – – ■ EinProzessruftforkauf,aberzweikehrenzurück! Ein Prozess ruft fork auf, aber zwei kehren zurück! ■ 28.04.2021 03 - Prozesse 14 Verwendung von fork() /* includes */ /* includes */ int main () { int main () { int pid; int pid; printf("Elternpr.: PID %d PPID %d\n", getpid(), getppid()); printf("Elternpr.: PID %d PPID %d\n", getpid(), getppid()); pid = fork(); /* Prozess wird dupliziert! pid = fork(); /* Prozess wird dupliziert! if (pid > 0) if (pid > 0)
printf(“Im Elternprozess, Kind-PID %d\n”, pid);
printf(“Im Elternprozess, Kind-PID %d\n”, pid);
else if (pid == 0) else if (pid == 0)
printf(“Im Kindprozess, PID %d PPID %d\n”,
printf(“Im Kindprozess, PID %d PPID %d\n”,
getpid(), getppid()); getpid(), getppid());
printf(“Oh, ein Fehler!\n”); /* mehr dazu in der TÜ */ printf(“Oh, ein Fehler!\n”); /* mehr dazu in der TÜ */
}
}
else
else
Beide laufen an dieser Stelle weiter. */
Beide laufen an dieser Stelle weiter. */
ulbrich@ios:~$ ./fork ulbrich@ios:~$ ./fork
Elternpr.: PID 7553 PPID 4014 Elternpr.: PID 7553 PPID 4014
Im Kindprozess, PID 7554 PPID 7553 Im Kindprozess, PID 7554 PPID 7553
Im Elternprozess, Kind-PID 7554 Im Elternprozess, Kind-PID 7554
28.04.2021 03 – Prozesse 15

Kosten der Prozesserzeugung
Das Kopieren des Adressraums erzeugt hohe Kosten
Speicher und Ausführungszeit
Insbesondere bei direkt folgendem exec..() pure Verschwendung!
■
– –
■
–
– –
■
–
– – –
Historische Lösung: vfork()
Elternprozess wird suspendiert, bis Kindprozess exec..() aufruft oder mit _exit() terminiert
Kindprozess benutzt Code und Daten des Elternprozesses (kein Kopieren!). Der Kindprozess darf keine Daten verändern
teilweise nicht so einfach: z.B. kein exit() aufrufen, sondern _exit()! Heutige Lösung: copy-on-write
Mit Hilfe der MMU teilen sich Eltern- und Kindprozess dasselbe Code- und Datensegment
Erst wenn der Kindprozess Daten ändert, wird das Segment kopiert Wenn nach dem fork() direkt ein exec..() folgt, kommt das nicht vor fork() mit copy-on-write ist kaum langsamer als vfork()
●
28.04.2021 03 – Prozesse 16

Der _exit() Systemaufruf
System Call: void _exit (int) System Call: void _exit (int)
■ Terminiert den laufenden Prozess und übergibt das Argument als Terminiert den laufenden Prozess und übergibt das Argument als
exit status an den Elternprozess exit status an den Elternprozess
– Aufruf kehrt nicht zurück! Aufruf kehrt nicht zurück!
■ GibtdiebelegtenRessourcendesProzessesfrei Gibt die belegten Ressourcen des Prozesses frei
– offene Dateien, belegter Speicher, … offene Dateien, belegter Speicher, …
■ SendetdemeigenenElternprozessdasSignalSIGCHLD Sendet dem eigenen Elternprozess das Signal SIGCHLD
■ DieBibliotheksfunktionexit(3)räumtzusätzlichnochdievon Die Bibliotheksfunktion exit(3) räumt zusätzlich noch die von
der libc belegten Ressourcen auf der libc belegten Ressourcen auf
– Gepufferte Ausgaben werden beispielsweise herausgeschrieben! Gepufferte Ausgaben werden beispielsweise herausgeschrieben!
■
–
■
–
■
■
–
–
Normale Prozesse sollten exit(3) benutzen, nicht _exit Normale Prozesse sollten exit(3) benutzen, nicht _exit
–
28.04.2021 03 – Prozesse 17

Verwaiste Prozesse
(engl. orphan processes)
Ein UNIX-Prozess wird zum Waisenkind, wenn sein Elternprozess terminiert.
Was passiert mit der Prozesshierarchie?
■
■
init (PID 1)
exit!
firefox
init (PID 1)
getty tty0
login
bash
init (PID 1) adoptiert alle init (PID 1) adoptiert alle
verwaisten Prozesse.
verwaisten Prozesse.
So bleibt die Prozess-
So bleibt die Prozess-
hierarchie intakt.
hierarchie intakt.
firefox
28.04.2021
03 – Prozesse
18

Der wait() Systemaufruf
System Call: pid_t wait (int*) System Call: pid_t wait (int*)
■ DeraufrufendenProzessblockiertbiseinKindprozessterminiert Der aufrufenden Prozess blockiert bis ein Kindprozess terminiert
■ DerRückgabewertistdessenPID Der Rückgabewert ist dessen PID
■ Zeigerargument(wstatus)liefertu.a.denExit-Status Zeigerargument (wstatus) liefert u.a. den Exit-Status
■
■
■
–
Wert kann per Makro geprüft werden (z.B. WIFEXITED(wstatus)) Wert kann per Makro geprüft werden (z.B. WIFEXITED(wstatus))
–
■ Kehrtsofortzurück,fallsbereitseinKindprozessterminiertist Kehrt sofort zurück, falls bereits ein Kindprozess terminiert ist
■
28.04.2021 03 – Prozesse 19

Zombies
Bevor der Exit-Status eines terminierten Prozesses mit Hilfe von wait abgefragt wird, ist er ein Zombie
Die Ressourcen solcher Prozesse können freigegeben werden, aber die Prozessverwaltung muss sie noch kennen
Insbesondere der exit status muss gespeichert werden
■
■
–
ulbrich@ios:~$ ./wait & ulbrich@ios:~$ ./wait &
ulbrich@ios:~$ ps ulbrich@ios:~$ ps
PID TTY
TIME CMD
PID TTY
TIME CMD
4014 pts/4
00:00:00 bash
4014 pts/4
00:00:00 bash
17892 pts/4
00:00:00 wait
17892 pts/4
00:00:00 wait
17895 pts/4
00:00:00 wait
17895 pts/4
00:00:00 wait
17897 pts/4
00:00:00 ps
17897 pts/4
00:00:00 ps
ulbrich@ios:~$ Exit Status: 42
ulbrich@ios:~$ Exit Status: 42
Zombies werden
Zombies werden
von ps als von ps als
dargestellt.
dargestellt.
28.04.2021 03 – Prozesse 20
Beispielprogramm
Beispielprogramm
von eben während
von eben während
der 5 Sekunden
der 5 Sekunden
Wartezeit.
Wartezeit.

Zombies …
Film vom 1968 Regie: G. A. Romero
■ ■
Quelle: Wikipedia (Public Domain)
28.04.2021
03 – Prozesse
21
Wikipedia:
Wikipedia:
In 1999 the Library of Congress In 1999 the Library of Congress
entered it into the United States
entered it into the United States
National Film Registry with other National Film Registry with other
films deemed „historically, culturally
films deemed „historically, culturally
or aesthetically important.“
or aesthetically important.“

Verwendung von wait()
… /* includes, main() { … */ … /* includes, main() { … */
pid = fork(); /* Kindprozess erzeugen */ pid = fork(); /* Kindprozess erzeugen */
if (pid > 0) { if (pid > 0) {
int status; int status;
sleep(5); /* Bibliotheksfunktion: 5 Sek. schlafen */ sleep(5); /* Bibliotheksfunktion: 5 Sek. schlafen */
if (wait(&status) == pid && WIFEXITED(status)) if (wait(&status) == pid && WIFEXITED(status))
printf (“Exit Status: %d\n”, WEXITSTATUS(status)); printf (“Exit Status: %d\n”, WEXITSTATUS(status));
}
}
else if (pid == 0) { else if (pid == 0) {
exit(42); exit(42);
}
}
…
…
Ein Prozess kann auch von außen
Ein Prozess kann auch von außen
getötet werden, d.h. er ruft nicht getötet werden, d.h. er ruft nicht
exit auf. In diesem Fall würde exit auf. In diesem Fall würde
WIFEXITED 0 liefern. WIFEXITED 0 liefern.
ulbrich@ios:~$ ./wait ulbrich@ios:~$ ./wait
Exit Status: 42
Exit Status: 42
28.04.2021 03 – Prozesse 22

UNIX-Prozesse im Detail: execve()
System Call: int execve (const char *kommando, SystemCall: int execve (const char *kommando,
const char *args[], const char *args[],
const char *envp[]) const char *envp[])
■ LädtundstartetdasangegebeneKommando Lädt und startet das angegebene Kommando
■ DerAufrufkehrtnurimFehlerfallzurück Der Aufruf kehrt nur im Fehlerfall zurück
■ DerkompletteAdressraumwirdersetzt Der komplette Adressraum wird ersetzt
■ EshandeltsichaberweiterhinumdenselbenProzess! Es handelt sich aber weiterhin um denselben Prozess!
– Selbe PID, PPID, offenen Dateien, … Selbe PID, PPID, offenen Dateien, …
■ DielibcbieteHilfsfunktionen,dieinternexecveaufrufen: Die libc biete Hilfsfunktionen, die intern execve aufrufen:
– execl,execv,execlp,execvp,… execl, execv, execlp, execvp, …
– UnterscheidensichinArgumenten,Umgebungsvariablen,Suchpfad Unterscheiden sich in Argumenten, Umgebungsvariablen, Suchpfad
■
■
■
■
–
■
–
–
28.04.2021 03 – Prozesse 23

Verwendung von exec..()
… /* includes, main() { … */ … /* includes, main() { … */
char cmd[100], arg[100]; char cmd[100], arg[100];
while (1) { while (1) {
printf (“Kommando?\n”);
printf (“Kommando?\n”);
scanf (“%99s %99s”, cmd, arg);
scanf (“%99s %99s”, cmd, arg);
pid = fork(); /* Prozess wird dupliziert! pid = fork(); /* Prozess wird dupliziert!
if (pid > 0) { if (pid > 0) {
int status; int status;
if (wait(&status) == pid && WIFEXITED(status)) if (wait(&status) == pid && WIFEXITED(status))
printf (“Exit Status: %d\n”, WEXITSTATUS(status)); printf (“Exit Status: %d\n”, WEXITSTATUS(status));
…
…
}
}
}
}
Beide laufen an dieser Stelle weiter. */
Beide laufen an dieser Stelle weiter. */
else if (pid == 0) { else if (pid == 0) {
execlp(cmd, cmd, arg, NULL); execlp(cmd, cmd, arg, NULL);
printf (“exec fehlgeschlagen\n”);
printf (“exec fehlgeschlagen\n”);
}
}
28.04.2021 03 – Prozesse 24

Diskussion: Warum kein forkexec()?
Durch die Trennung von fork und execve hat der Elternprozess mehr Kontrolle:
Operationen im Kontext des Kindprozesses ausführen Voller Zugriff auf die Daten des Elternprozesses
■
– –
■
– –
Shells nutzen diese Möglichkeit zum Beispiel zur …
Umleitung der Standard-E/A-Kanäle Aufsetzen von Pipes
28.04.2021 03 – Prozesse 25

UNIX-Prozesszustände
ein paar mehr als wir bisher kannten …
■
im Benutzer- modus laufend
Unterbrechung, U.-Rückkehr
verdrängt Verdrängung
im Kern laufend
exit Zombie
genug Speicher
bereit, im Spei- cher
fork erzeugt
Auslagerung Einlagerung
nicht genug Speicher
bereit, ausge- lagert
Aufwecken
Aufwecken
schlafend, im Speicher
schlafend, ausgelagert
Bild in Anlehnung an M. Bach „UNIX – Wie funktioniert das Betriebssystem?“
Auslagerung
28.04.2021 03 – Prozesse
26
CPU-Zuteilung
CPU-Zuteilung
Rückkehr
Systemaufruf, Unterbrechung
Schlafen

Das „Gewicht“ von Prozessen
Das Gewicht eines Prozesses ist ein bildlicher Ausdruck für die Größe seines Kontexts und damit die Zeit, die für einen Prozesswechsel benötigt wird.
CPU-Zuteilungsentscheidung alten Kontext sichern
neuen Kontext laden
■
– – –
■
Klassische UNIX-Prozesse sind schwergewichtig.
28.04.2021 03 – Prozesse 28

Leichtgewichtige Prozesse (Threads)
Die 1:1-Beziehung zwischen Kontrollfluss und Adressraum wird aufgebrochen
Eng kooperierende Threads (deutsch „Fäden“)
Adressraum teilen (code + data + bss + heap, aber nicht stack!)
■
– –
■
–
–
– –
●
Typisches Beispiel: Webserver
■
–
Vorteile:
Auslagerung aufwändiger Operationen in einen leichtgewichtigen Hilfsprozess, während der Elternprozess erneut auf Eingabe reagieren kann
Programme, die aus mehreren unabhängigen Kontrollflüssen bestehen, profitieren unmittelbar von Multiprozessor-Hardware
Schneller Kontextwechsel, wenn man im selben Adressraum bleibt Je nach Scheduler eventuell mehr Rechenzeit
Nachteil:
Programmierung ist schwierig:
Zugriff auf gemeinsame Daten muss koordiniert werden.
28.04.2021 03 – Prozesse 29

Federgewichtige Prozesse
(engl. User-Level Threads)
Werden komplett auf der Anwendungsebene implementiert. Das Betriebssystem weiß nichts davon.
Realisiert durch Bibliothek: User-Level Thread Package Im Gegensatz zu Kernel-Level Threads
■
– –
■
–
–
■
–
– –
Vorteile:
Extrem schneller Kontextwechsel: Nur wenige Prozessorregister sind auszutauschen. Ein Trap in den Kern entfällt.
Jede Anwendung kann sich das passende Thread-Package wählen. Nachteile:
Blockierung eines federgewichtigen Prozesses führt zur Blockierung des ganzen Programms.
Kein Geschwindigkeitsvorteil durch Multi-Prozessoren. Kein zusätzlicher Rechenzeitanteil.
28.04.2021 03 – Prozesse 30

Threads in Windows (1)
Prozess
Globale und statische Daten
Stack 1
Code
Stack 2
Stack 3
Stack 4
Ein Prozess enthält 1 bis N Threads, die
Ein Prozess enthält 1 bis N Threads, die
auf denselben globalen Daten operieren.
auf denselben globalen Daten operieren.
28.04.2021 03 – Prozesse 31

Threads in Windows (2)
Prozess: Umgebung und Adressraum für Threads
Ein Win32-Prozess enthält immer mindestens 1 Thread Thread: Code-ausführende Einheit
Jeder Thread verfügt über einen eigenen Stack
und Registersatz (insbes. Instruktionszeiger / PC = program counter)
Threads bekommen vom Scheduler Rechenzeit zugeteilt Alle Threads sind Kernel-Level Threads
User-Level Threads möglich („Fibers“), aber unüblich Strategie: Anzahl der Threads gering halten
Überlappte (asynchrone) E/A
■
–
■
–
–
■
–
■
–
28.04.2021 03 – Prozesse 32

Threads in Linux
Linux implementiert POSIX Threads in Form der pthread-Bibliothek Möglich macht das ein Linux-spezifischer System Call
■ ■
■
–
Linux System Call: Linux System Call:
int clone (int (*fn)(void*), void *stack int clone (int (*fn)(void*), void *stack
int flags, void *arg, …) int flags, void *arg, …)
■ UniverselleFunktion,parametrisiertdurchflags Universelle Funktion, parametrisiert durch flags
– CLONE_VM CLONE_VM
– CLONE_FS CLONE_FS
– CLONE_FILES CLONE_FILES
– CLONE_SIGHAND CLONE_SIGHAND
■
–
Adressraum gemeinsam nutzen
–
Information über Dateisystem teilen
–
Dateideskriptoren (offene Dateien) teilen
–
Gemeinsame Signalbehandlungstabelle
Adressraum gemeinsam nutzen
Information über Dateisystem teilen
Dateideskriptoren (offene Dateien) teilen
Gemeinsame Signalbehandlungstabelle
Für Linux sind alle Threads und Prozesse intern Tasks:
Der Scheduler macht also keinen Unterschied.
28.04.2021 03 – Prozesse 33

Zusammenfassung
Prozesse sind die zentrale Abstraktion für Aktivitäten in heutigen Betriebssystemen
UNIX-Systeme stellen diverse System Calls zur Verfügung, um Prozesse zu erzeugen, zu verwalten und miteinander zu verknüpfen
alles im Sinne der Philosophie: „Do one thing, do it well.“
■
■
–
■
– –
Leichtgewichtige Fadenmodelle haben viele Vorteile
in UNIX-Systemen bis in die 90er Jahre nicht verfügbar in Windows von Beginn an (ab NT) integraler Bestandteil
28.04.2021 03 – Prozesse 34

Betriebssysteme (BS)
04. Ablaufplanung
https://sys.cs.tu-dortmund.de/DE/Teaching/SS2021/BS/
05.05.2021
Peter Ulbrich
peter.ulbrich@tu-dortmund.de
Basierend auf Betriebssysteme von Olaf Spinczyk, Universität Osnabrück

Wiederholung
Prozesse: die zentrale Abstraktion für Aktivitäten in heutigen Betriebssystemen
Konzeptionell unabhängige sequentielle Kontrollflüsse (Folge von CPU- und E/A-Stößen)
Tatsächlich findet ein Multiplexing der CPU statt
■
–
–
■
–
■
– –
UNIX-Systeme stellen diverse System Calls zur Verfügung, um Prozesse zu erzeugen, zu verwalten und miteinander zu verknüpfen.
Moderne Betriebssysteme unterstützen darüber hinaus auch leicht- und federgewichtige Prozesse.
Prozesse unterliegen der Kontrolle des Betriebssystems:
Betriebsmittel-Zuteilung Betriebsmittel-Entzug
05.05.2021 Betriebssysteme: 04 – Ablaufplanung 2

Inhalt
Prozesszustände und Zustandsübergänge
Klassische Planungsstrategien
FCFS…………………………………….. einfach
RR, VRR………………………………… zeitscheibenbasiert SPN (SJF), SRTF, HRRN………….. vorhersagebasiert FB (MLQ, MLFQ)…………………….. prioritätenbasiert
Bewertungskriterien und Vergleich
Beispiele
UNIX (4.3BSD) NT
■ ■
– – – –
■ ■
– –
Tanenbaum
2.5: Scheduling
Silberschatz
5: Process Scheduling
Es geht um Uniprozessor-Scheduling für den Es geht um Uniprozessor-Scheduling für den
05.05.2021
Betriebssysteme: 04 – Ablaufplanung 3
Allgemeinzweckbetrieb. Nicht betrachtet wird:
Allgemeinzweckbetrieb. Nicht betrachtet wird:
●
Multiprozessor-Scheduling
●
●
Echtzeit-Scheduling
●
●
E/A-Scheduling
●
Multiprozessor-Scheduling
Echtzeit-Scheduling
E/A-Scheduling

Prozesszustände vs. Einplanungsebene
Jedem Prozess ist in Abhängigkeit von der Einplanungsebene ein logischer Zustand zugeordnet, der den Prozesszustand zu einem Zeitpunkt angibt:
kurzfristig (short-term scheduling)
bereit, laufend, blockiert
■
–
■
–
■
–
mittelfristig (medium-term scheduling)
ausgelagert bereit, ausgelagert blockiert
langfristig (long-term scheduling)
erzeugt, beendet
05.05.2021 Betriebssysteme: 04 – Ablaufplanung 5

Kurzfristige Einplanung
bereit (READY)
zur Ausführung durch den Prozessor (die CPU)
Prozess ist auf der Bereitliste (ready list) für Einlastung Listenposition bestimmt sich durch das Einplanungsverfahren
■
– –
■
– –
■
– –
laufend (RUNNING)
Zuteilung des Betriebsmittels CPU ist erfolgt
Prozess führt Berechnungen durch, er vollzieht seinen CPU-Stoß
Für jeden Prozessor gibt es zu einem Zeitpunkt nur einen laufenden Prozess
blockiert (BLOCKED)
auf ein bestimmtes Ereignis
Prozess führt „Ein-/Ausgabe“ durch, er vollzieht seinen E/A-Stoß Er erwartet die Erfüllung mindestens einer Bedingung.
05.05.2021 Betriebssysteme: 04 – Ablaufplanung 6

Mittelfristige Einplanung
Prozess ist komplett ausgelagert, d.h. der Inhalt seines gesamten Adressraums wurde in den Hintergrundspeicher verschoben (swap-out) und der von dem Prozess belegte Vordergrundspeicher wurde freigegeben.
Die Einlagerung (swap-in) des Adressraums ist abzuwarten:
ausgelagertbereit(READY SUSPEND)
CPU-Zuteilung („bereit“) ist außer Kraft gesetzt Prozess ist auf der Warteliste für die Speicherzuteilung
■
– –
■
– –
ausgelagertblockiert(BLOCKED SUSPEND)
Prozess erwartet weiterhin ein Ereignis („blockiert“)
Tritt das Ereignis ein, wird der Prozess „ausgelagert bereit“
05.05.2021 Betriebssysteme: 04 – Ablaufplanung 7

Langfristige Einplanung
erzeugt (NEW)
und fertig zur Programmverarbeitung – fork(2)
Prozess ist instanziiert, ihm wurde ein Programm zugeordnet Ggf. steht die Zuteilung des Betriebsmittels „Speicher“ noch aus
■
– –
■
– –
beendet (EXIT) underwartetdieEntsorgung–exit(2) / wait(2)
Prozess ist terminiert, seine Betriebsmittel werden freigegeben
Ggf. muss ein anderer Prozess den „Kehraus“ vollenden (wie z.B. unter UNIX)
05.05.2021 Betriebssysteme: 04 – Ablaufplanung 8

Zustandsübergänge
EXIT
NEW
Long Term
Long Term
READY SUSPEND
BLOCKED SUSPEND
4
RUNNING
1
READY
3
BLOCKED
2
Medium Term
Medium Term
Short Term
Short Term
05.05.2021 Betriebssysteme: 04 – Ablaufplanung 9

Einplanungs- und Auswahlzeitpunkt
Jeder Übergang in den Zustand bereit (READY) aktualisiert die CPU-Warteschlange:
Entscheidung über die Einreihung des Prozesskontrollblocks Ergebnis hängt von Planungsstrategie des Systems ab
■
– –
■
Ein Prozess kann dazu gedrängt werden, die CPU abzugeben → präemptive Ablaufplanung
2 wenn die Kontrolle über die CPU entzogen wird (z.B. Zeitgeberunterbrechung)
Einplanung/Umplanung (scheduling/rescheduling) erfolgt, …
nachdem ein Prozess erzeugt worden ist
2 wenn ein Prozess freiwillig die Kontrolle über die CPU abgibt
3 sofern das von einem Prozess erwartete Ereignis eingetreten ist
4 sobald ein ausgelagerter Prozess wieder aufgenommen wird
■
1
05.05.2021 Betriebssysteme: 04 – Ablaufplanung 10

First-Come First-Served – FCFS
Ein einfaches und gerechtes (?) Verfahren:
„Wer zuerst kommt, mahlt zuerst.“
Einreihungskriterium ist die Ankunftszeit eines Prozesses Arbeitet nicht-verdrängend und setzt kooperative Prozesse voraus Das Verfahren minimiert die Zahl der Kontextwechsel
■
– – –
■
Beispiel
Prozess
Zeiten
Ankunft
Bedienzeit Ts
Start
Ende
Durchlauf Tr
Tr/Ts
A
0
1
0
1
1
1,00
B
1
100
1
101
100
1,00
C
2
1
101
102
100
100,00
D
3
100
102
202
199
1,99
Mittelwert
100
26,00
–
Durchlaufzeit von C steht in einem sehr schlechten Verhältnis zur Bedienzeit Ts → Sehr hohe normalisierte Durchlaufzeit (Tr/Ts)
05.05.2021 Betriebssysteme: 04 – Ablaufplanung 12

FCFS – Der Konvoi-Effekt
Mit dem Problem sind immer kurz laufende E/A-lastige Prozesse konfrontiert, die langen CPU-lastigen Prozessen folgen.
Prozesse mit langen CPU-Stößen werden begünstigt, Prozesse mit kurzen CPU-Stößen werden benachteiligt.
■
– –
■
– –
■
–
Der resultierende Konvoi-Effekt verursacht Probleme:
hohe Antwortzeit „schneller“ Prozesse (warten auf „langsame“) niedriger E/A-Durchsatz (Annahme: kurzer CPU → langer E/A Stoß)
Bei einem Mix von CPU- und E/A-lastigen Prozessen ist FCFS daher ungeeignet.
typischerweise nur in reinen Stapelverarbeitungssystemen
05.05.2021 Betriebssysteme: 04 – Ablaufplanung 13

Round Robin – RR
Verringert die Benachteiligung kurzer CPU-Stöße:
„Jeder gegen jeden“
Die Prozessorzeit wird in Zeitscheiben aufgeteilt (time slicing).
■
–
■
– –
■ ■
– –
Mit Ablauf der Zeitscheibe erfolgt ggf. ein Prozesswechsel:
Der unterbrochene Prozess wird ans Ende der Bereitliste verdrängt, der nächste Prozess wird gemäß FCFS der Bereitliste entnommen.
Zeitgeber bewirkt Unterbrechung am Ende der Zeitscheibe
Zeitscheibenlänge bestimmt Effektivität des Verfahrens
zu lang, Degenerierung zu FCFS; zu kurz, hohe Verwaltungsgemeinkosten Faustregel: etwas länger als die Dauer einer „typischen Interaktion“
05.05.2021 Betriebssysteme: 04 – Ablaufplanung 14

RR – Leistungsprobleme
E/A-lastige Prozesse beenden ihren CPU-Stoß frühzeitig innerhalb ihrer Zeitscheibe
sie blockieren und kommen mit Ende ihres E/A-Stoßes in die Bereitliste
■
–
■
–
■
–
–
CPU-lastige Prozesse schöpfen dagegen ihre Zeitscheibe voll aus
sie werden verdrängt und kommen sofort wieder in die Bereitliste
Die CPU-Zeit ist zu Gunsten CPU-lastiger Prozesse ungleich verteilt!
E/A-lastige Prozesse werden schlecht bedient und dadurch Geräte schlecht ausgelastet
Varianz der Antwortzeit E/A-lastiger Prozesse erhöht sich
05.05.2021 Betriebssysteme: 04 – Ablaufplanung 15

Virtual Round Robin – VRR
Vermeidet die bei RR mögliche ungleiche Verteilung der CPU-Zeiten
Prozesse kommen mit Ende ihrer E/A-Stöße in eine Vorzugsliste Diese Liste wird vor der Bereitliste abgearbeitet.
■
– –
■
–
–
■
Prozessabfertigung ist dadurch im Vergleich zu RR etwas aufwändiger.
VRR arbeitet mit Zeitscheiben unterschiedlicher Längen
Prozesse der Vorzugsliste bekommen keine volle Zeitscheibe zugeteilt: Ihnen wird die Restlaufzeit ihrer vorher nicht voll genutzten Zeit gewährt. Sollte ihr CPU-Stoß länger dauern, werden sie in die Bereitliste verdrängt.
05.05.2021 Betriebssysteme: 04 – Ablaufplanung 16

Shortest Process Next – SPN
Verringert die auftretende Benachteiligung kurzer CPU-Stöße:
„Die Kleinen nach vorne“
Grundlage dafür ist die Kenntnis über die Prozesslaufzeiten Verdrängung findet nicht statt
■
– –
■
– –
■
–
Hauptproblem: Vorhersage der Laufzeiten
Stapelbetrieb: Programmierer geben das erforderliche time limit* vor Dialogbetrieb: Schätzung aus früheren Stoßlängen des Prozesses
Antwortzeiten werden verkürzt und die Gesamtleistung steigt.
Dafür: Gefahr der Aushungerung (starvation) CPU-lastiger Prozesse
*Die Zeitdauer, innerhalb der der Job (wahrscheinlich/hoffentlich) beendet wird, bevor er abgebrochen wird.
05.05.2021 Betriebssysteme: 04 – Ablaufplanung 17

SPN – CPU-Stoßdauer
Basis für die Schätzung ist die Mittelwertbildung über alle bisherigen CPU-Stoßlängen eines Prozesses:
■
■
–
■
–
Problem: gleiche Gewichtung aller CPU-Stöße
Jüngere CPU-Stöße sind jedoch von größerer Bedeutung als ältere und sollten daher auch mit größerer Gewichtung berücksichtigt werden!
Ursache ist das Lokalitätsprinzip
Daten und Instruktionen sind anfangs nicht in CPU-nahen Speichern verfügbar
05.05.2021 Betriebssysteme: 04 – Ablaufplanung 18

SPN – Stoßgewichtung
Zurückliegenden CPU-Stöße sollen weniger Gewicht erhalten:
Für den konstanten Gewichtungsfaktor α gilt dabei: 0 < α < 1 Er drückt die relative Gewichtung einzelner CPU-Stöße der Zeitreihe aus. ■ – – ■ Rekursive Einsetzung führt zu ... fürα=0.8: ■ Dieses statistische Verfahren nennt man auch exponentielle Glättung. Dieses statistische Verfahren nennt man auch exponentielle Glättung. 05.05.2021 Betriebssysteme: 04 - Ablaufplanung 19 Shortest Remaining Time First – SRTF Erweitert den SPN-Ansatz um Verdrängung. Dadurch geeignet für den Dialogbetrieb Führt zu besseren Durchlaufzeiten ■ – – ■ – – ■ – ■ Wie SPN kann auch SRTF Prozesse zum Verhungern bringen. Der laufende Prozess wird verdrängt, wenn gilt: Terw < Trest Terw ist die erwartete CPU-Stoßlänge eines eintreffenden Prozesses Trest ist die verbleibende CPU-Stoßlänge des laufenden Prozesses Anders als RR basiert SRTF nicht auf Zeitgeberunterbrechungen, ist aber präemptiv Dafür müssen allerdings Stoßlängen abgeschätzt werden. 05.05.2021 Betriebssysteme: 04 - Ablaufplanung 20 Highest Response Ratio Next – HRRN Vermeidet das bei SRTF mögliche Verhungern von CPU-lastigen Prozessen. Das Altern (aging), d.h. die Wartezeit von Prozessen, wird berücksichtigt: ■ – ■ Ausgewählt wird immer der Prozess mit dem größten Verhältniswert R. – – w ist die bisherige Wartezeit des Prozesses s ist die erwartete Bedienzeit 05.05.2021 Betriebssysteme: 04 - Ablaufplanung 21 Feedback – FB Begünstigt kurze Prozesse, ohne die relativen Längen der Prozesse abschätzen zu müssen. Grundlage ist die Bestrafung (penalization) von „Langläufern“ Prozesse unterliegen dem Verdrängungsprinzip ■ – – ■ – – – ■ – Mehrere Bereitlisten kommen zum Einsatz, je nach Anzahl von Prioritätsebenen: Wenn ein Prozess erstmalig eintrifft, läuft er auf höchster Ebene. Mit Ablauf der Zeitscheibe kommt er in die nächst niedrigere Ebene. Die unterste Ebene arbeitet nach RR. Kurze Prozesse laufen relativ schnell durch, lange Prozesse können verhungern. Wartezeit kann berücksichtigt werden, um wieder höhere Ebenen zu erreichen (anti-aging) 05.05.2021 Betriebssysteme: 04 - Ablaufplanung 22 FB – Ablaufplanungsmodell 05.05.2021 Betriebssysteme: 04 - Ablaufplanung 23 Diskussion: Prioritäten Prozess-„Vorrang“, der Zuteilungsentscheidungen maßgeblich beeinflusst Statische Prioritäten werden zum Zeitpunkt der Prozesserzeugung festgelegt: Wert kann im weiteren Verlauf nicht mehr verändert werden erzwingen deterministische Ordnung zwischen Prozessen ■ ■ – – ■ – – Dynamische Prioritäten werden während der Prozesslaufzeit aktualisiert: Aktualisierung erfolgt im Betriebssystem, aber auch vom Benutzer aus SPN, SRTF, HRRN und FB sind Spezialfälle dieses Verfahrens 05.05.2021 Betriebssysteme: 04 - Ablaufplanung 24 Kombinationen – Multilevel Scheduling Mehrere Betriebsformen lassen sich nebeneinander betreiben. z.B. gleichzeitige Unterstützung von {Dialog- und Hintergrundbetrieb, Echtzeit- und sonstigem Betrieb} Dialogorientierte bzw. zeitkritische Prozesse werden bevorzugt bedient. ■ – – ■ – – – ■ Die Umsetzung erfolgt typischerweise über mehrere Bereitlisten. Jeder Bereitliste ist eine bestimmte Zuteilungsstrategie zugeordnet, Listen werden typischerweise nach Priorität, FCFS oder RR verarbeitet. Ein höchst komplexes Gebilde → multi-level feedback (MLFB) FB kann als Spezialfall dieses Verfahrens aufgefasst werden. 05.05.2021 Betriebssysteme: 04 - Ablaufplanung 25 Kombinationen – Multilevel Scheduling höchste Priorität Systemprozesse Interaktive Prozesse Stapelverarbeitungsprozesse Studentenprozesse niedrigste Priorität Quelle: Silberschatz 05.05.2021 Betriebssysteme: 04 - Ablaufplanung 26 Inhalt Prozesszustände und Zustandsübergänge Klassische Planungsstrategien FCFS............................................ einfach RR, VRR....................................... zeitscheibenbasiert SPN (SJF), SRTF, HRRN.............. vorhersagebasiert FB (MLQ, MLFQ).......................... prioritätenbasiert Bewertungskriterien und Vergleich Beispiele UNIX (4.3BSD) NT ■ ■ – – – – ■ ■ – – 05.05.2021 Betriebssysteme: 04 - Ablaufplanung 27 Ziele = Bewertungskriterien ■ – – – – Zeit zwischen Eingang und Abschluss eines Prozesses einschließlich der Wartezeit(en) → Stapelverarbeitung Zeit zwischen Benutzereingabe und Antwort → interaktive Systeme Für die Interaktion mit äußeren physikalischen Prozessen sollten Termine eingehalten werden → Echtzeitsysteme Prozesse werden unabhängig von der Last immer gleich bearbeitet → harte Echtzeitsysteme Möglichst viele Prozesse pro Zeiteinheit abarbeiten CPU immer beschäftigen → Verwaltungsgemeinkosten (z.B. Scheduling, Kontextwechsel) vermeiden Kein Prozess soll benachteiligt werden (z.B. Aushungern) Auch E/A-Geräte sollen gleichmäßig ausgelastet werden ■ – – – – Benutzerorientiert Durchlaufzeit Antwortzeit Termineinhaltung Vorhersagbarkeit Systemorientiert Durchsatz Auslastung Fairness Lastausgleich 05.05.2021 Betriebssysteme: 04 - Ablaufplanung 28 Gegenüberstellung – quantitativ Prozess Start Bedienzeit Ts ABCDE 02468 36452 Mittel- wert FCFS Ende Durchlauf Tr Tr/Ts 3 9 13 18 20 3 7 9 12 12 1,00 1,17 2,25 2,40 6,00 8,60 2,56 RR q=1 Ende Durchlauf Tr Tr/Ts 4 18 17 20 15 4 16 13 14 7 1,33 2,67 3,25 2,80 3,50 10,80 2,71 SPN Ende Durchlauf Tr Tr/Ts 3 9 15 20 11 3 7 11 14 3 1,00 1,17 2,75 2,80 1,50 7,60 1,84 SRTF Ende Durchlauf Tr Tr/Ts 3 15 8 20 10 3 13 4 14 2 1,00 2,17 1,00 2,80 1,00 7,20 1,59 HRRN Ende Durchlauf Tr Tr/Ts 3 9 13 20 15 3 7 9 14 7 1,00 1,17 2,25 2,80 3,50 8,00 2,14 FB q=1 Ende Durchlauf Tr Tr/Ts 4 20 16 19 11 4 18 12 13 3 1,33 3,00 3,00 2,60 1,50 10,00 2,29 05.05.2021 Betriebssysteme: 04 - Ablaufplanung 29 Aus William Stallings, „Betriebssysteme – Prinzipien und Umsetzung“ SPN SRTF HRRN FB Gegenüberstellung – qualitativ Strategie FCFS RR präemptiv/ kooperativ kooperativ präemptiv (Zeitgeber) kooperativ präemptiv (bei Eingang) kooperativ präemptiv (Zeitgeber) Vorhersage nötig nein nein ja ja ja nein minimal klein groß größer groß größer Verhungern möglich nein nein ja ja nein ja Auswirkung auf Prozesse Konvoi-Effekt Fair, aber benachteiligt E/A-lastige Prozesse Benachteiligt CPU-lastige Prozesse Benachteiligt CPU-lastige Prozesse Gute Lastverteilung Bevorzugt u.U. E/A-lastige Prozesse In Anlehnung an William Stallings, „Betriebssysteme – Prinzipien und Umsetzung“ Impl.- aufwand 05.05.2021 Betriebssysteme: 04 - Ablaufplanung 30 Inhalt Prozesszustände und Zustandsübergänge Klassische Planungsstrategien FCFS............................................ einfach RR, VRR....................................... zeitscheibenbasiert SPN (SJF), SRTF, HRRN.............. vorhersagebasiert FB (MLQ, MLFQ).......................... prioritätenbasiert Bewertungskriterien und Vergleich Beispiele UNIX (4.3BSD) NT ■ ■ – – – – ■ ■ – – 05.05.2021 Betriebssysteme: 04 - Ablaufplanung 31 UNIX Zweistufiges präemptives Verfahren mit dem Ziel, Antwortzeiten zu minimieren Kein Long-Term Scheduling high-level: mittelfristig mit Ein-/Auslagerung (swapping) arbeitend low-level: kurzfristig präemptiv, MLFB, dynamische Prozessprioritäten Einmal pro Sekunde: Jeder „Tick“ (1/10 s) verringert das Nutzungsrecht über die CPU durch Erhöhung von cpu_usage beim laufenden Prozess ■ ■ ■ ■ – – – ● hohe prio-Zahl = niedrige Priorität 05.05.2021 Betriebssysteme: 04 - Ablaufplanung 32 Das Maß der CPU-Nutzung (cpu_usage) wird über die Zeit gedämpft ● Die Dämpfungs-/Glättungsfunktion variiert von UNIX zu UNIX prio = cpu_usage + p_nice + base UNIX – 4.3 BSD (1) Jeden vierten Tick (40ms) erfolgt die Berechnung der Benutzerpriorität: ■ ■ Pcpu nimmt mit jedem Tick um 1 zu und wird einmal pro Sekunde geglättet: ■ Glättung für erwachte Prozesse, die länger als eine Sekunde blockiert waren: 05.05.2021 Betriebssysteme: 04 - Ablaufplanung 33 UNIX – 4.3 BSD (2) Glättung (decay filter) bei einer angenommenen mittleren Auslastung (load) von 1 gilt Pcpu := 0,66 · Pcpu+Pnice Ferner sei angenommen, ein Prozess sammelt Ti Ticks im Zeitintervall i an und Pnice = 0 ■ ■ ■ Nach 5 Sekunden gehen nur noch 13% „alte“ Auslastung ein. 05.05.2021 Betriebssysteme: 04 - Ablaufplanung 34 Windows NT – Prioritätsklassen Präemptive, prioritäts- und zeitscheibenbasierte Einplanung von Fäden (Threads) Verdrängung erfolgt auch dann, wenn der Faden sich im Kern befindet →nichtsobeiUNIX&Co RR bei gleicher Priorität: 0 reserviert, 1–15 variabel, 16-31 Echtzeit ■ – – ■ – – Die Art des Fadens (Vorder-/Hintergrund) bestimmt das Zeitquantum eines Fadens → Quantum Stretching Quantum (zwischen 6 und 36) vermindert sich mit jedem Tick (10 bzw. 15ms) um 3 oder um 1, falls der Faden in den Wartezustand geht Die Zeitscheibenlänge variiert mit den Prozessen: 20 – 180ms Vordergrund/Hintergrund, Server/Desktop-Konfiguration Zudem variable Priorität: process_priority_class + relative_thread_priority + boost 05.05.2021 Betriebssysteme: 04 - Ablaufplanung 35 ■ ● NT – Prioritätsanpassung Fadenprioritäten werden in bestimmten Situationen dynamisch angehoben: Dynamic Boost Abschluss von Ein-/Ausgabe (Festplatten) +1 Mausbewegung, Tastatureingabe +6 Deblockierung, Betriebsmittelfreigabe (Semaphor, Event, Mutex) +1 Andere Ereignisse (Netzwerk, Pipe, . . . ) +2 Ereignis im Vordergrundprozess +2 Die dynamic boosts werden mit jedem Tick wieder verbraucht Fortschrittsgarantie Verhindert das Aushungern von Threads Alle 3–4 s erhalten bis zu 10 „benachteiligte“ Fäden für zwei Zeitscheiben die Priorität 15 ■ – – – – – ■ ■ – – 05.05.2021 Betriebssysteme: 04 - Ablaufplanung 36 Zusammenfassung Betriebssysteme treffen Planungsentscheidungen auf drei Ebenen: Long-Term Scheduling: Zulassung von Prozessen zum System Medium-Term Scheduling: Aus- und Einlagerung von Prozessen Short-Term Scheduling: kurzfristige CPU-Zuteilung ■ – – – ■ – – – Alle hier betrachteten Verfahren werden dem Short-Term Scheduling zugerechnet. Es gibt diverse benutzer- und systemorientierte Kriterien für die Beurteilung der Eigenschaften eines CPU-Zuteilungsverfahrens. Die Auswahl kommt einer Gratwanderung gleich. Das „beste“ Verfahren lässt sich nur nach einer Analyse des typischen Anwendungsprofils und aller Randbedingungen finden. 05.05.2021 Betriebssysteme: 04 - Ablaufplanung 37 Betriebssysteme (BS) 05. Synchronisation https://sys.cs.tu-dortmund.de/DE/Teaching/SS2021/BS/ 12.05.2021 Peter Ulbrich peter.ulbrich@tu-dortmund.de Basierend auf Betriebssysteme von Olaf Spinczyk, Universität Osnabrück Wiederholung: Prozesse ... sind Programme in Ausführung (unter BS-Kontrolle) Die Abstraktion für Kontrollflüsse in Rechnersystemen Konzeptionell unabhängig Technisch findet ein Multiplexing der CPU statt. Das Betriebssystem bestimmt den Zeitpunkt der Verdrängung und die Ausführungsreihenfolge der rechenbereiten Prozesse. ■ – – – – ■ – ■ – – – haben einen Adressraum Die logischen Adressen in einem Prozess werden durch die Hardware auf physische Speicheradressen abgebildet. können sich auch Code- und Datenbereiche teilen Leicht- und federgewichtige Prozesse arbeiten im selben Adressraum. Das Betriebssystem kann mit Hilfe der MMU auch einen Speicherbereich in mehrere Adressräume einblenden. Die Daten des Betriebssystems werden ebenfalls (kontrolliert) geteilt. 12.05.2021 Betriebssysteme: 05 - Synchronisation 2 Inhalt Einführung und Begriffsbildung Ad-Hoc-Lösungsansätze Aktives Warten – Busy Waiting ■ ■ – ■ – – Hardwareunterstützung Unterbrechungssperre Atomare Operationen ■ – ■ – ■ Betriebssystemunterstützung Semaphore Sprachunterstützung Monitore Zusammenfassung Tanenbaum 2.3: Interprozesskommunikation 2.4: Klassische Probleme der Interprozesskommunikation Silberschatz 5: Synchronization 12.05.2021 Betriebssysteme: 05 - Synchronisation 3 Beispiel: Einfache verkettete Liste in C /* Datentyp für Listenelemente */ /* Datentyp für Listenelemente */ struct element { struct element { char payload; char payload; struct element *next; struct element *next; }; /* Verkettungszeiger */ }; Diese Listenimplementierung ist /* Datentyp für die Verwaltung von Listen */ struct list { struct list { struct element *head; struct element *head; tail nicht auf das letzte Element, tail nicht auf das letzte Element, /* eigentliche “Nutzlast” */ /* eigentliche “Nutzlast” */ /* Verkettungszeiger */ /* Datentyp für die Verwaltung besonders raffiniert. Dadurch, dass vobnesLoinsdterns r*a/ffiniert. Dadurch, dass Einfügen in eine leere Liste. void enqueue (struct list *list, struct element *item) { void enqueue (struct list *list, struct element *item) { item->next = NULL;
item->next = NULL;
*list->tail = item;
*list->tail = item;
list->tail = &item->next;
list->tail = &item->next;
};
};
/* Funktion zum Anhängen eines neuen Elements */
/* Funktion zum Anhängen eines neuen Elements */
}
}
Diese Listenimplementierung ist
sondern den next-Zeiger verweist, sondern den next-Zeiger verweist,
/* erstes Element */
/* erstes Element */
struct element **tail; /* ‘next’ im letzten Element */
struct element **tail; /* ‘next’ im letzten Element */
entfällt eine Sonderbehandlung für
entfällt eine Sonderbehandlung für
Einfügen in eine leere Liste.
12.05.2021 Betriebssysteme: 05 – Synchronisation 4

Beispiel: Einfache verkettete Liste in C Szenario
Faden A
Faden B
‘a’
?
NULL
‘b’
?
Listenelement e1 12.05.2021
globales Listenobjekt l Gemeinsamer Adressraum
Listenelement e2
/* enqueue */
void enqueue (struct list *list,
struct element *item) {
item->next = NULL;
*list->tail = item;
list->tail = &item->next;
}
Gemeinsamer Adressraum
Betriebssysteme: 05 – Synchronisation
5
enqueue(&l,&e2)
Daten Code
enqueue(&l,&e1)

enqueue(&l,&e1)
enqueue(&l,&e1)
NULL
‘a’
NULL
‘b’
?
‘a’
NULL
‘b’
?
‘a’
NULL
‘b’
?
enqueue(&l,&e2)
enqueue(&l,&e2)
‘a’
‘b’
NULL
1. Fall: Faden B nach Faden A
l
item->next = NULL;
*list->tail = item;
list->tail = &item->next;
item->next = NULL;
*list->tail = item;
list->tail = &item->next;
e1
e2
12.05.2021 Betriebssysteme: 05 – Synchronisation
6
…

2. Fall: Faden 2 überlappt Faden 1
l e1 e2
‘a’
NULL
‘b’
?
‘a’
NULL
‘b’
NULL
‘a’
NULL
‘b’
NULL
12.05.2021 Betriebssysteme: 05 – Synchronisation 7
enqueue(&l,&e1)
enqueue(&l,&e1)
item->next = NULL;
*list->tail = item;
list->tail = &item->next;
Prozess- wechsel
Prozess- wechsel
enqueue(&l,&e2)
enqueue(&l,&e2)
item->next = NULL;
*list->tail = item;
list->tail = &item->next;

Wo kommt das sonst noch vor?
Gemeinsamer Speicher zur Kommunikation zwischen Prozessen
Systeme mit Shared Memory-Dienst Leicht- oder federgewichtige Prozesse
Nebenläufiger Zugriff auf dieselben Variablen
■
–
■
–
■
– –
■
–
Betriebssystemdaten, die gebraucht werden, um den Zugriff von Prozessen auf unteilbare Betriebsmittel zu koordinieren
Dateisystemstrukturen, Prozesstabelle, Speicherverwaltung … Geräte (Terminal, Drucker, Netzwerkschnittstellen, …)
Ähnlicher Sonderfall: Unterbrechungssynchronisation
Vorsicht: Verfahren, die sich für die Synchronisation von Prozessen eignen, funktionieren nicht notwendigerweise bei Unterbrechungen!
12.05.2021 Betriebssysteme: 05 – Synchronisation 8

Begriff: Race Condition
(oder auch Wettlaufsituation)
Eine Race Condition ist eine Situation, in der mehrere Prozesse konkurrierend auf gemeinsame Daten zugreifen und mindestens einer diese manipuliert. Der letztendliche Wert der gemeinsamen Daten hängt bei einer Race Condition davon ab, in welcher Reihenfolge die Prozesse darauf zugreifen. Das Ergebnis ist also nicht vorhersagbar und kann im Fall von überlappenden Zugriffen sogar inkorrekt sein!
Um Race Conditions zu vermeiden, müssen konkurrierende Prozesse synchronisiert werden.
■
■
12.05.2021 Betriebssysteme: 05 – Synchronisation 9

Begriff: Synchronisation
Die Koordination der Kooperation und Konkurrenz zwischen Prozessen wird Synchronisation (synchronization) genannt.
● Eine Synchronisation bringt die Aktivitäten verschiedener nebenläufiger Prozesse in eine Reihenfolge.
● Durch sie erreicht man also prozessübergreifend das, wofür innerhalb eines Prozesses die Sequentialität von Aktivitäten sorgt.
Quelle: Herrtwich/Hommel (1989), Kooperation und Konkurrenz, S. 26
12.05.2021 Betriebssysteme: 05 – Synchronisation 10

Begriff: Kritischer Abschnitt
Im Fall von Race Conditions streiten sich N Prozesse um den Zugriff auf gemeinsame Daten. Die Code-Fragmente, in denen auf diese kritischen Daten zugegriffen wird, werden kritische Abschnitte genannt.
Problem
Es muss sichergestellt werden, dass sich immer nur ein Prozess in einem kritischen Abschnitt aufhalten kann.
■
■
12.05.2021 Betriebssysteme: 05 – Synchronisation 11

Lösungsansatz: Schlossvariablen
Lock lock;
Eine Schlossvariable ist ein abstrakter Datentyp Eine Schlossvariable ist ein abstrakter Datentyp
mit 2 Operationen: acquire() und release() mit 2 Operationen: acquire() und release()
/* Eine globale Schlossvariable */
/* Beispielcode: enqueue */
void enqueue (struct list *list, struct element *item) {
item->next = NULL;
acquire (&lock);
*list->tail = item;
list->tail = &item->next;
release (&lock);
}
• verzögert einen Prozess bis • verzögert einen Prozess bis
das zugehörige Schloss offen ist
das zugehörige Schloss offen ist
• verschließt das Schloss dann • verschließt das Schloss dann
von innen
von innen
• öffnet das zugehörige Schloss, • öffnet das zugehörige Schloss,
ohne den aufrufenden Prozess
ohne den aufrufenden Prozess
zu verzögern
zu verzögern
Derartige Implementierungen werden als Schlossalgorithmen bezeichnet. Derartige Implementierungen werden als Schlossalgorithmen bezeichnet.
12.05.2021 Betriebssysteme: 05 – Synchronisation 12

Inhalt
Einführung und Begriffsbildung
Ad-Hoc-Lösungsansätze
Aktives Warten – Busy Waiting
■ ■
–
■
– –
■
–
■
–
■
Hardwareunterstützung
Unterbrechungssperre Atomare Operationen
Betriebssystemunterstützung
Semaphore
Sprachunterstützung
Monitore
Zusammenfassung
12.05.2021 Betriebssysteme: 05 – Synchronisation 13

Naiver Lösungsansatz
/* Schlossvariable (Initialwert 0) */
/* Schlossvariable (Initialwert 0) */
typedef unsigned char Lock;
typedef unsigned char Lock;
/* Kritischen Abschnitt betreten */
/* Kritischen Abschnitt betreten */
void acquire (Lock *lock) {
void acquire (Lock *lock) {
while (*lock)
while (*lock)
; /* Schleifenrumpf leer! */
; /* Schleifenrumpf leer! */
*lock = 1;
*lock = 1;
}
}
/* Kritischen Abschnitt wieder verlassen */
/* Kritischen Abschnitt wieder verlassen */
void release (Lock *lock) {
void release (Lock *lock) {
*lock = 0;
*lock = 0;
}
}
FALSCH!
FALSCH!
12.05.2021 Betriebssysteme: 05 – Synchronisation 14

Naiver Lösungsansatz: Ein Henne-Ei-Problem!
acquire() soll einen kritischen Abschnitt schützen, ist dabei aber selbst kritisch!
Problematisch ist der Moment nach dem Verlassen der Warteschleife und vor dem Setzen der Schlossvariablen.
Bei Verdrängung des laufenden Prozesses in diesem Moment könnte ein anderer Prozess den kritischen Abschnitt frei vorfinden und ebenfalls betreten.
/* Schlossvariable */
/* Schlossvariable */
typedef unsigned char Lock;
typedef unsigned char Lock;
/* K.A. betreten */
/* K.A. betreten */
void acquire (Lock *lock) {
void acquire (Lock *lock) {
while (*lock);
while (*lock);
*lock = 1;
*lock = 1;
}
}
/* K.A. verlassen */
/* K.A. verlassen */
void release (Lock *lock) {
void release (Lock *lock) {
*lock = 0;
*lock = 0;
}
}
■
–
–
Im weiteren Verlauf könnten (mindestens) zwei Prozesse
Im weiteren Verlauf könnten (mindestens) zwei Prozesse
den eigentlich durch acquire() geschützten kritischen den eigentlich durch acquire() geschützten kritischen
Abschnitt überlappt ausführen!
Abschnitt überlappt ausführen!
12.05.2021
Betriebssysteme: 05 – Synchronisation 15

So geht’s: der „Bäckerei-Algorithmus“
(naja, in deutschen Bäckereien ist das eher unüblich)
Bevor ein Prozess den kritischen Abschnitt betreten darf, bekommt er eine Wartenummer.
Die Zulassung erfolgt in der Reihenfolge der Nummern, d.h. wenn der kritische Abschnitt frei ist, darf der Prozess mit der niedrigsten Nummer den kritischen Abschnitt betreten.
Beim Verlassen des kritischen Abschnitts verfällt seine Wartenummer.
Problem:
Der Algorithmus kann nicht garantieren, dass eine Wartenummer nur an einen Prozess vergeben wird.
In diesem Fall entscheidet eine Prozess-ID (0..N-1) die Priorität.
■
■
–
■
–
12.05.2021 Betriebssysteme: 05 – Synchronisation 16

So geht’s: der „Bäckerei-Algorithmus“
typedef struct { /* Schlossvariable (initial alles 0) */
typedef struct { /* Schlossvariable (initial alles 0) */
bool choosing[N]; int number[N];
bool choosing[N]; int number[N];
} Lock;
} Lock;
void acquire (Lock *lock) { /* K.A. betreten */
void acquire (Lock *lock) { /* K.A. betreten */
int j; int i = pid(); int j; int i = pid();
lock->choosing[i] = true;
lock->choosing[i] = true;
lock->number[i] = max(lock->number[0], …number[N-1]) + 1; lock->number[i] = max(lock->number[0], …number[N-1]) + 1;
lock->choosing[i] = false;
lock->choosing[i] = false;
for (j = 0; j < N; j++) { for (j = 0; j < N; j++) { while (lock->choosing[j]);
while (lock->choosing[j]);
while (lock->number[j] != 0 &&
while (lock->number[j] != 0 &&
(lock->number[j] < lock->number[i] ||
(lock->number[j] < lock->number[i] ||
(lock->number[j] == lock->number[i] && j < i))); (lock->number[j] == lock->number[i] && j < i))); void release (Lock *lock) { /* K.A. verlassen */ void release (Lock *lock) { /* K.A. verlassen */ int i = pid(); lock->number[i] = 0;
int i = pid(); lock->number[i] = 0;
}
}
}
}
}
}
Achtung:
Achtung:
Pseudo-Code
Pseudo-Code
12.05.2021 Betriebssysteme: 05 – Synchronisation 17

Diskussion: Bäckerei-Algorithmus
Der Algorithmus ist ein nachweisbar korrekte Lösung für das Problem der kritischen Abschnitte, aber …
In der Regel weiß man vorab nicht, wieviele Prozesse um den Eintritt in einen kritischen Abschnitt konkurrieren werden.
Prozess-IDs liegen nicht im Wertebereich von 0 bis N-1.
die Funktion acquire() hat eine große Laufzeit, auch wenn der kritische Abschnitt frei ist. → O(N)
■
■ ■
Wünschenswert wäre ein korrekter Algorithmus,
Wünschenswert wäre ein korrekter Algorithmus,
der gleichzeitig so einfach wie der naive Ansatz ist!
der gleichzeitig so einfach wie der naive Ansatz ist!
12.05.2021 Betriebssysteme: 05 – Synchronisation 18

Inhalt
Einführung und Begriffsbildung Ad-Hoc-Lösungsansätze
Aktives Warten – Busy Waiting
■ ■
–
■
– –
■
–
■
–
■
Hardwareunterstützung
Unterbrechungssperre Atomare Operationen
Betriebssystemunterstützung
Semaphore
Sprachunterstützung
Monitore
Zusammenfassung
12.05.2021 Betriebssysteme: 05 – Synchronisation 19

Unterbrechungen unterdrücken
Nur durch den Unterbrechungsmechanismus der CPU kann es dazu kommen, dass einem Prozess innerhalb eines kritischen Abschnitts die CPU entzogen wird.
■
■
Durch diese Lösung werden alle Prozesse und das Betriebssystem selbst (Gerätetreiber) beeinträchtigt.
/* K.A. betreten */
/* K.A. betreten */
void acquire (Lock *lock) {
void acquire (Lock *lock) {
asm (“cli”);
asm (“cli”);
}
}
/* K.A. verlassen */
/* K.A. verlassen */
void release (Lock *lock) {
void release (Lock *lock) {
asm (“sti”);
asm (“sti”);
}
}
sti und cli dürfen daher nicht im User-Mode benutzt werden.
12.05.2021 Betriebssysteme: 05 – Synchronisation 20
–
cli und sti werden bei Intel-x86- cli und sti werden bei Intel-x86-
Prozessoren zum Sperren und Prozessoren zum Sperren und
Erlauben von Unterbrechungen Erlauben von Unterbrechungen
verwendet.
verwendet.

Schloss mit atomaren Operationen
Viele CPUs unterstützen unteilbare (atomare) Lese-/Modifikations-/ Schreibzyklen, mit denen sich Schlossalgorithmen implementieren lassen:
Motorola 68K: TAS (Test-and-Set)
Setzt Bit 7 des Zieloperanden und liefert den vorherigen Zustand in Condition Code Bits
■
–
■
–
■
■
PowerPC: LL/SC (Load Linked/Store Conditional) …
Intel x86: XCHG (Exchange)
Tauscht den Inhalt eines Registers mit dem einer Variablen im Speicher
12.05.2021 Betriebssysteme: 05 – Synchronisation 21
acquire TAS lock acquire TAS lock
acquire:
xchg ax,lock xchg ax,lock
acquire:
cmp ax,0
BNE acquire
BNE acquire
mov ax,1
mov ax,1
cmp ax,0
jne acquire
jne acquire

Diskussion: Aktives Warten
Unzulänglichkeit der bisher gezeigten Schlossalgorithmen:
Der aktiv wartende Prozess …
kann selbst keine Änderung der Bedingung herbeiführen, auf die er wartet
behindert daher unnütz Prozesse, die sinnvolle Arbeit leisten könnten
schadet damit letztlich auch sich selbst:
Je länger der Prozess den Prozessor für sich behält, umso länger muss er darauf warten, dass andere Prozesse die Bedingung erfüllen, auf die er selbst wartet.
Nur bei Multiprozessorsystemen tritt dieses Problem nicht auf.
■
■
■
–
–
12.05.2021 Betriebssysteme: 05 – Synchronisation 22

Inhalt
Einführung und Begriffsbildung Ad-Hoc-Lösungsansätze
Aktives Warten – Busy Waiting
■ ■
–
■
– –
Hardwareunterstützung
Unterbrechungssperre Atomare Operationen
■
–
■
–
■
Betriebssystemunterstützung
Semaphore
Sprachunterstützung
Monitore
Zusammenfassung
12.05.2021 Betriebssysteme: 05 – Synchronisation 23

Passives Warten als effizientere Alternative
Prozesse geben die Kontrolle über die CPU ab, während sie auf Ereignisse warten
im Konfliktfall blockiert sich ein Prozess auf ein Ereignis
PCB des Prozesses in eine Warteschlange eingereiht
tritt das Ereignis ein, wird ein darauf wartender Prozess deblockiert
■
–
–
●
■
– – –
■
Mit Beginn der Blockadephase endet der CPU-Stoß des Prozesses.
Die Wartephase eines Prozesses ist als Blockadephase („E/A-Stoß“) ausgelegt:
der Ablaufplan für die Prozesse wird aktualisiert (scheduling)
ein anderer, lauffähiger Prozess wird plangemäß abgefertigt (dispatching) ist kein Prozess mehr lauffähig, läuft die CPU „leer“ (idle phase)
12.05.2021 Betriebssysteme: 05 – Synchronisation 24

Semaphor (semaphore)
Eine „nicht-negative ganze Zahl“,
für die zwei unteilbare Operationen definiert sind:
P (niederländisch prolaag, „erniedrige“; auch down, wait)
hat der Semaphor den Wert 0, wird der laufende Prozess blockiert ansonsten wird der Semaphor um 1 dekrementiert
V (niederländisch verhoog, „erhöhe“; auch up, signal)
auf den Semaphor ggf. blockierter Prozess wird deblockiert ansonsten wird der Semaphor um 1 inkrementiert
■
■
Eine Betriebssystemabstraktion zum Austausch von Synchronisationssignalen zwischen nebenläufig arbeitenden Prozessen.
– –
– –
12.05.2021 Betriebssysteme: 05 – Synchronisation 25

Semaphor (semaphore) – Implementierung
/* Implementierung aus OO-StuBS */
/* Implementierung aus OO-StuBS */
class Semaphore : public WaitingRoom {
class Semaphore : public WaitingRoom {
int counter;
int counter;
public:
public:
Semaphore(int c) : counter(c) {}
Semaphore(int c) : counter(c) {}
void wait() {
void wait() {
if (counter == 0) {
if (counter == 0) {
Customer *life = (Customer*)scheduler.active();
Customer *life = (Customer*)scheduler.active();
}
counter–;
counter–;
}
}
scheduler.block(life, this);
scheduler.block(life, this);
} };
}
else
enqueue(life);
else
enqueue(life);
void signal() {
void signal() {
Customer *customer = (Customer*)dequeue();
Customer *customer = (Customer*)dequeue();
if (customer)
if (customer)
} };
counter++;
counter++;
else
scheduler.wakeup(customer);
else
scheduler.wakeup(customer);
Ein WaitingRoom ist eine Ein WaitingRoom ist eine
Liste von PCBs mit den
Liste von PCBs mit den
Zugriffsmethoden enqueue Zugriffsmethoden enqueue
und dequeue. und dequeue.
Der Scheduler muss drei Der Scheduler muss drei
Operationen zur Verfügung
Operationen zur Verfügung
stellen:
stellen:
• active liefert PCB des • active liefert PCB des
laufenden Prozesses
laufenden Prozesses
• block versetzt einen • block versetzt einen
Prozess in den Zustand
Prozess in den Zustand
BLOCKED.
BLOCKED.
• wakeup setzt einen • wakeup setzt einen
blockierten Prozess
blockierten Prozess
wieder auf die Bereit-Liste
wieder auf die Bereit-Liste
12.05.2021 Betriebssysteme: 05 – Synchronisation 26

Semaphor – Anwendung
Semaphore lock;
Gegenseitiger Ausschluss: Ein mit 1 initialisierter Gegenseitiger Ausschluss: Ein mit 1 initialisierter
Semaphor kann als Schlossvariable fungieren.
Semaphor kann als Schlossvariable fungieren.
/* = 1; Semaphor als Schlossvariable */
/* Beispielcode: euqueue */
void enqueue (struct list *list, struct element *item) {
item->next = NULL;
wait (&lock);
*list->tail = item;
list->tail = &item->next;
signal (&lock);
}
• der erste Prozess, der den • der erste Prozess, der den
kritischen Abschnitt betritt
kritischen Abschnitt betritt
erniedrigt den Zähler auf 0
erniedrigt den Zähler auf 0
• alle weiteren blockieren • alle weiteren blockieren
• beim Verlassen wird entweder • beim Verlassen wird entweder
ein blockierter Prozess geweckt
ein blockierter Prozess geweckt
oder der Zähler wieder auf 1
oder der Zähler wieder auf 1
erhöht
erhöht
… und das ist nicht die einzige Anwendung
… und das ist nicht die einzige Anwendung
12.05.2021 Betriebssysteme: 05 – Synchronisation 27

Semaphor – einfache Interaktionen
Einseitige Synchronisation
■
■
Betriebsmittelorientierte Synchronisation
sonst wie beim gegenseitigen Ausschluss
/* gem. Speicher */
/* gem. Speicher */
Semaphore elem;
Semaphore elem;
struct list l;
struct list l;
struct element e;
struct element e;
void producer() {
void producer() {
enqueue(&l, &e);
enqueue(&l, &e);
signal(&elem);
signal(&elem);
}
}
void consumer() {
void consumer() {
struct element *x;
struct element *x;
wait(&elem);
wait(&elem);
x = dequeue(&l);
x = dequeue(&l);
}
}
/* Initialisierung */
/* Initialisierung */
elem = 0;
elem = 0;
/* gem. Speicher */
/* gem. Speicher */
Semaphore resource;
Semaphore resource;
/* Initialisierung */
/* Initialisierung */
resource = N; /* N > 1 */
resource = N; /* N > 1 */
12.05.2021 Betriebssysteme: 05 – Synchronisation 28

Semaphor – komplexe(re) Interaktionen
Beispiel: Das erste Leser/Schreiber-Problem
■
Wie beim gegenseitigen Ausschluss soll auch in diesem Beispiel ein kritischer Abschnitt geschützt werden. Es gibt allerdings zwei Klassen von konkurrierenden Prozessen:
• Schreiber: Sie ändern Daten und müssen daher gegenseitigen Ausschluss garantiert bekommen.
• Leser: Da sie nur lesen, dürfen mehrere Leser
auch gleichzeitig den kritischen Abschnitt betreten.
12.05.2021 Betriebssysteme: 05 – Synchronisation 29

Semaphor – komplexe(re) Interaktionen
Beispiel: Das erste Leser/Schreiber-Problem
■
/* gem. Speicher */
/* gem. Speicher */
Semaphore mutex;
Semaphore mutex;
Semaphore wrt;
Semaphore wrt;
int readcount;
int readcount;
/* Initialisierung */
/* Initialisierung */
mutex = 1;
mutex = 1;
wrt =1; wrt =1;
readcount = 0;
readcount = 0;
/* Leser */
/* Leser */
wait(&mutex);
wait(&mutex);
readcount++;
readcount++;
if (readcount == 1)
if (readcount == 1)
wait(&wrt);
wait(&wrt);
signal(&mutex);
signal(&mutex);
… lese … lese
wait(&mutex);
wait(&mutex);
readcount–;
readcount–;
if (readcount == 0)
if (readcount == 0)
signal(&wrt);
signal(&wrt);
signal(&mutex):
signal(&mutex):
/* Schreiber */
/* Schreiber */
wait (&wrt);
wait (&wrt);
… schreibe
… schreibe
signal (&wrt);
signal (&wrt);
12.05.2021 Betriebssysteme: 05 – Synchronisation 30

Semaphore – Diskussion
Erweiterungen/Varianten
Binäre Semaphore oder Mutex nicht-blockierendes wait() Timeout
Felder von Zählern
■
– – – –
■
–
–
–
–
●
➔
Unterstützung durch die Programmiersprache
Fehlerquellen
Gefahr von Verklemmungen → nächste Vorlesung
Komplexere Synchronisationsmuster schwierig
Abhängigkeit kooperierender Prozesse
jeder muss die Protokolle exakt einhalten Semaphorbenutzung wird nicht erzwungen
12.05.2021 Betriebssysteme: 05 – Synchronisation 31

Inhalt
Einführung und Begriffsbildung Ad-Hoc-Lösungsansätze
Aktives Warten – Busy Waiting
■ ■
–
■
– –
■
–
■
–
■
Hardwareunterstützung
Unterbrechungssperre Atomare Operationen
Betriebssystemunterstützung
Semaphore
Sprachunterstützung
Monitore
Zusammenfassung
12.05.2021 Betriebssysteme: 05 – Synchronisation 32

Monitor (Hoare 1974, Hansen 1975)
Ein abstrakter Datentyp mit impliziten Synchronisationseigenschaften:
1) mehrseitige Synchronisation an der Schnittstelle zum Monitor
gegenseitiger Ausschluss der Ausführung aller Methoden
2) einseitige Synchronisation innerhalb des Monitors mit Hilfe von Bedingungsvariablen (condition variables)
wait blockiert einen Prozess auf das Eintreten eines Signals/einer Bedingung und gibt den Monitor implizit wieder frei
signal zeigt das Eintreten eines Signals/einer Bedingung an und deblockiert ggf. (genau einen oder alle) darauf blockierte Prozesse
■
■
Sprachgestützter Mechanismus: Concurrent Pascal, PL/I, CHILL, . . . , Java.
–
–
–
12.05.2021 Betriebssysteme: 05 – Synchronisation 33

Monitor – Beispielcode
/* Eine synchronisierte Warteschlange */
/* Eine synchronisierte Warteschlange */
monitor SyncQueue {
monitor SyncQueue {
};
Queue queue;
Queue queue;
condition not_empty;
condition not_empty;
public:
public:
/* Element einhängen */
/* Element einhängen */
void enqueue(Element element) {
void enqueue(Element element) {
queue.enqueue(element);
queue.enqueue(element);
/* Element aushängen */
Element dequeue() {
Element dequeue() {
Pro SyncQueue-Objekt Pro SyncQueue-Objekt
garantiert die Sprache
garantiert die Sprache
Achtung:
gegenseitigen Ausschluss
Achtung:
Pseudo-Code
Pseudo-Code
gegenseitigen Ausschluss
}
not_empty.signal();
not_empty.signal();
}
/* Element aushängen */
} };
}
while (queue.is_empty())
while (queue.is_empty())
not_empty.wait();
not_empty.wait();
return queue.dequeue();
return queue.dequeue();
der Zugriffsmethoden.
der Zugriffsmethoden.
enqueue signalisiert, dass enqueue signalisiert, dass
die Queue nicht mehr die Queue nicht mehr
leer ist. Wenn kein Prozess
leer ist. Wenn kein Prozess
wartet, passiert nichts.
wartet, passiert nichts.
dequeue wartet zunächst dequeue wartet zunächst
darauf, dass mindestens ein
darauf, dass mindestens ein
Element in der Queue ist. Element in der Queue ist.
12.05.2021 Betriebssysteme: 05 – Synchronisation 34

Monitor – Signalisierungssemantik
Im Falle wartender Prozesse sind als Anforderungen zwingend zu erfüllen:
Wenigstens ein Prozess deblockiert an der Bedingungsvariablen und
höchstens ein Prozess rechnet nach der Operation im Monitor weiter
■
–
–
■
–
–
●
Wenn nur einer, dann welcher?
Konflikte mit der CPU-Zuteilungsstrategie sind möglich.
Es gibt verschiedene Lösungsvarianten, jeweils mit unterschiedlicher Semantik
Anzahl der befreiten Prozesse (d.h., alle oder nur einer)
Besitzwechsel des Monitors, kein Besitzwechsel (Besitzwahrung)
●
Wenn kein sofortiger Besitzwechsel erfolgt, muss die Wartebedingung erneut überprüft werden.
12.05.2021
Betriebssysteme: 05 – Synchronisation 35

Monitor – in Java
Schlüsselwort synchronized für gegenseitigen Ausschluss Eine implizite Bedingungsvariable
notify oder notifyAll statt signal, kein Besitzwechsel
■ ■
–
/* Eine synchronisierte Warteschlange */
/* Eine synchronisierte Warteschlange */
class SyncQueue {
class SyncQueue {
private Queue queue;
private Queue queue;
} };
};
/* Element einhängen */
/* Element einhängen */
public synchronized void enqueue(Element element) {
public synchronized void enqueue(Element element) {
queue.enqueue(element);
queue.enqueue(element);
notifyAll();
notifyAll();
}
}
/* Element aushängen */
/* Element aushängen */
public synchronized Element dequeue() {
public synchronized Element dequeue() {
while (queue.empty()) wait();
while (queue.empty()) wait();
return queue.dequeue();
return queue.dequeue();
}
12.05.2021 Betriebssysteme: 05 – Synchronisation 36

Inhalt
Einführung und Begriffsbildung Ad-Hoc-Lösungsansätze
Aktives Warten – Busy Waiting
■ ■
–
■
– –
■
–
■
–
Hardwareunterstützung
Unterbrechungssperre Atomare Operationen
Betriebssystemunterstützung
Semaphore
Sprachunterstützung
Monitore
Zusammenfassung
■
12.05.2021 Betriebssysteme: 05 – Synchronisation 37

Zusammenfassung
Unkontrollierte nebenläufige Zugriffe führen zu Fehlern
Synchronisationsverfahren sorgen für Koordination
Grundsätzlich muss man bei der Implementierung aufpassen, dass die
Auswahlstrategien nicht im Widerspruch zum Scheduler stehen.
■
– –
■
– –
■
–
■
– – –
Ad-hoc-Verfahren: Aktives Warten
Vorsicht! Verschwendung von Rechenzeit
Aber: kurz aktiv Warten ist besser als Blockieren, insbesondere in
Multiprozessorsystemen → Multiprozessor-VL Betriebssystemunterstützte Verfahren: Semaphore
Flexibel (erlaubt viele Synchronisationsmuster), aber fehlerträchtig
Sprachunterstützte Verfahren: Monitore
Weniger vielseitig als Semaphore Teuer durch viele Kontextwechsel Dafür aber sicher
12.05.2021 Betriebssysteme: 05 – Synchronisation 38

Betriebssysteme (BS)
06. Verklemmungen
https://sys.cs.tu-dortmund.de/DE/Teaching/SS2021/BS/
19.05.2021
Peter Ulbrich
peter.ulbrich@tu-dortmund.de
Basierend auf Betriebssysteme von Olaf Spinczyk, Universität Osnabrück

Wiederholung
Prozesse in einem Rechner arbeiten nebenläufig
Zur Koordination von Prozessen werden Synchronisationsprimitiven eingesetzt
Grundidee ist das passive Warten
Der Semaphor erlaubt …
gegenseitigen Ausschluss
einseitige Synchronisation betriebsmittelorientierte Synchronisation
■ ■
■ ■
– – –
■
Wartemechanismen führen zu Verklemmungsproblemen
19.05.2021 Betriebssysteme: 06 – Verklemmungen 2

Inhalt
Ursachenforschung
Verklemmungen von Prozessen
Konsumierbare und nicht-konsumierbare Betriebsmittel Modellierung durch Betriebsmittelbelegungsgraphen
■ ■
– –
■
–
■
– – –
■
Zusammenfassung
Ein klassisches Verklemmungsproblem
„Die fünf Philosophen“
Gegenmaßnahmen, Verklemmungsbekämpfung
Vorbeugung
Vermeidung
Erkennung und Auflösung
Tanenbaum
6: Deadlocks
Silberschatz
5: Deadlocks
19.05.2021 Betriebssysteme: 06 – Verklemmungen 3

Verklemmung auf der Straße
Es gilt: „Rechts vor links!“ Es gilt: „Rechts vor links!“
Kein Auto darf fahren.
Kein Auto darf fahren.
Verklemmungssituationen
Verklemmungssituationen
wie diese kann es auch
wie diese kann es auch
bei Prozessen geben.
bei Prozessen geben.
19.05.2021 Betriebssysteme: 06 – Verklemmungen 4

Ursachenforschung … am Beispiel
1
Käfer 1 belegt L und benötigt R
Käfer 1 belegt L und benötigt R
Käfer 2 belegt R und benötigt L
Käfer 2 belegt R und benötigt L
1 L
L
R
R
2
Verklemmung möglich Verklemmung möglich
2
Verklemmung aufgetreten
Verklemmung aufgetreten
19.05.2021 Betriebssysteme: 06 – Verklemmungen 5

Ursachenforschung … abstrakt
Fortschritt Prozess K2
12
1-6:
mögliche Abläufe
1-6:
mögliche Abläufe
✘: ✘:
Verklemmung
Verklemmung
In diese Bereiche
In diese Bereiche
können die Prozesse
können die Prozesse
3
LR
L R
5 6
Fortschritt Prozess K1
4
nicht hinein!
nicht hinein!
✘
Verklemmung unvermeidbar
Betriebsmittel
19.05.2021
Betriebssysteme: 06 – Verklemmungen
6
Betriebsmittel

Ursachenforschung … abstrakt
19.05.2021
Betriebssysteme: 06 – Verklemmungen
7
Fortschritt Prozess K2
12 34
1-6: mögliche Abläufe
1-6: mögliche Abläufe
LR
L R
5 6
Fortschritt Prozess K1
Betriebsmittel
Eine Verklemmung kann
Eine Verklemmung kann
in diesem Szenario nicht
in diesem Szenario nicht
auftreten.
auftreten.
Betriebsmittel

Verklemmung von Prozessen
Der Begriff bezeichnet (in der Informatik)
■
„[ . . . ] einen Zustand, in dem die beteiligten Prozesse wechselseitig auf den Eintritt von Bedingungen warten, die nur durch andere Prozesse in dieser Gruppe selbst hergestellt werden können.“
Jürgen Nehmer und Peter Sturm. Systemsoftware: Grundlagen moderner Betriebssysteme. dpunkt.Verlag GmbH, zweite Ausgabe, 2001.
19.05.2021 Betriebssysteme: 06 – Verklemmungen 9

Verklemmung von Prozessen
1. Variante: Deadlock
Passives Warten Prozesszustand: BLOCKED
2. Variante: Livelock
Aktives Warten (busy waiting oder „lazy“ busy waiting) Prozesszustand beliebig (auch RUNNING), aber kein Fortschritt
■
– –
– –
– –
Deadlocks sind das vergleichsweise geringere Übel:
Zustand eindeutig erkennbar → Basis zur „Auflösung“ gegeben Extrem hohe Systembelastung durch aktives Warten
19.05.2021 Betriebssysteme: 06 – Verklemmungen 10

Bedingungen für eine Verklemmung
Damit es zu einer Verklemmung kommen kann, müssen alle folgenden
notwendigen Bedingungen erfüllt sein:
1. Exklusive Belegung von Betriebsmitteln (mutual exclusion)
die umstrittenen Betriebsmittel sind nur unteilbar nutzbar
2. Nachforderung von Betriebsmitteln (hold and wait)
die umstrittenen Betriebsmittel sind nur schrittweise belegbar
3. Kein Entzug von Betriebsmitteln (no preemption)
die umstrittenen Betriebsmittel sind nicht rückforderbar
Erst wenn zur Laufzeit die hinreichende Bedingung eintritt, liegt tatsächlich eine Verklemmung vor:
4. Zirkuläres Warten (circular wait)
Eine geschlossene Kette wechselseitig wartender Prozesse
–
–
–
–
19.05.2021 Betriebssysteme: 06 – Verklemmungen 11

Betriebsmittel …
werden vom Betriebssystem verwaltet und den Prozessen zugänglich gemacht. Man unterscheidet zwei Arten:
Wiederverwendbare Betriebsmittel
Werden von Prozessen für eine bestimmte Zeit belegt und anschließend wieder freigegeben.
Beispiele: CPU, Haupt- und Hintergrundspeicher, E/A-Geräte, Systemdatenstrukturen wie Dateien, Prozesstabelleneinträge, …
Typische Zugriffssynchronisation: Gegenseitiger Ausschluss
■
–
–
–
■
– –
–
Konsumierbare Betriebsmittel
Werden im laufenden System erzeugt (produziert) und zerstört (konsumiert)
Beispiele: Unterbrechungsanforderungen, Signale, Nachrichten, Daten von Eingabegeräten
Typische Zugriffssynchronisation: Einseitige Synchronisation
19.05.2021 Betriebssysteme: 06 – Verklemmungen 12

Wiederverwendbare Betriebsmittel
Es kommt zu einer Verklemmung, wenn zwei Prozesse ein wiederverwendbares Betriebsmittel belegt haben, das vom jeweils anderen nachgefordert wird.
Beispiel: Ein Rechnersystem hat 200 GByte Hauptspeicher. Zwei Prozesse belegen den Speicher schrittweise. Die Belegung erfolgt blockierend.
■
■
…
…
Prozess 1
Prozess 1
Belege 80 GByte; Belege 80 GByte;
…
…
Belege 60 GByte; Belege 60 GByte;
Wenn beide Prozesse ihre erste Anforderung ausführen, bevor
Wenn beide Prozesse ihre erste Anforderung ausführen, bevor
Speicher nachgefordert wird, ist eine Verklemmung unvermeidbar.
Speicher nachgefordert wird, ist eine Verklemmung unvermeidbar.
…
…
…
…
Prozess 2
Prozess 2
Belege 70 GByte; Belege 70 GByte;
Belege 80 GByte; Belege 80 GByte;
19.05.2021 Betriebssysteme: 06 – Verklemmungen 13

Konsumierbare Betriebsmittel
Es kommt zu einer Verklemmung, wenn zwei Prozesse auf ein konsumierbares Betriebsmittel warten, das vom jeweils anderen produziert wird.
Beispiel: Synchronisationssignale werden mit Hilfe der Semaphor- operation wait und signal zwischen zwei Prozessen „verschickt“.
■
■
Prozess 1
Prozess 1
semaphore s1 = {0, NULL};
semaphore s1 = {0, NULL};
wait (&s1); wait (&s1);
… // konsumiere
… // konsumiere
… // produziere
… // produziere
signal (&s2); signal (&s2);
Prozess 2
Prozess 2
semaphore s2 = {0, NULL};
semaphore s2 = {0, NULL};
wait (&s2); wait (&s2);
… // konsumiere
… // konsumiere
… // produziere
… // produziere
signal (&s1); signal (&s1);
Jeder Prozess wartet auf ein Synchronisationssignal des anderen,
Jeder Prozess wartet auf ein Synchronisationssignal des anderen,
das dieser aber nicht senden kann, da er selbst blockiert ist.
das dieser aber nicht senden kann, da er selbst blockiert ist.
19.05.2021 Betriebssysteme: 06 – Verklemmungen 14

Betriebsmittelbelegungsgraphen
(engl. resource allocation graphs)
… werden benutzt, um Verklemmungssituationen zu visualisieren und auch automatisch zu erkennen.
■
– – –
Beschreiben einen aktuellen Systemzustand Knoten: Prozesse und Betriebsmittel
Kanten: zeigen Anforderung oder Belegung an
B B1
PP P1 P2
12
Betriebsmittel B1 wird durch Prozess P1 angefordert
Prozess P2 belegt das Betriebsmittel B2
1
B B2
2
19.05.2021 Betriebssysteme: 06 – Verklemmungen 15

Betriebsmittelbelegungsgraphen
Frage: Liegt zirkuläres Warten vor? Wer ist beteiligt? (Prozesse A-B, Betriebsmittel R-W) AB
■
AB
CDE
CDE
T
T
A belegt R und verlangt S.
B belegt nichts, verlangt aber T. C belegt nichts, verlangt aber S. D belegt U und S und verlangt T. E belegt T und verlangt V.
F belegt W und verlangt S.
G belegt V und verlangt U.
F
F
19.05.2021
Betriebssysteme: 06 – Verklemmungen 16
R
R
S
S
W
W
U
U
G
G
V
V

Betriebsmittelbelegungsgraphen
Frage: Liegt zirkuläres Warten vor? Wer ist beteiligt? (Prozesse A-B, Betriebsmittel R-W) AB
CDE CDE
■
R
R
AB
S
S
F
F
W
W
U
G
G
T
T
U
Zwischen den Prozessen
Zwischen den Prozessen
D, E und G besteht eine
D, E und G besteht eine
zirkuläre Wartebeziehung!
zirkuläre Wartebeziehung!
V
V
19.05.2021
Betriebssysteme: 06 – Verklemmungen 17

Inhalt
Ursachenforschung
Verklemmungen von Prozessen
Konsumierbare und nicht-konsumierbare Betriebsmittel Modellierung durch Betriebsmittelbelegungsgraphen
■ ■
– –
■
–
■
– – –
■
Zusammenfassung
Ein klassisches Verklemmungsproblem
„Die fünf Philosophen“
Gegenmaßnahmen, Verklemmungsbekämpfung
Vorbeugung
Vermeidung
Erkennung und Auflösung
19.05.2021 Betriebssysteme: 06 – Verklemmungen 18

Die fünf speisenden Philosophen
Prozess → Philosoph Betriebsmittel → Gabel (unteilbar)
.
Fünf Philosophen, die
Fünf Philosophen, die
nichts anderes zu tun
nichts anderes zu tun
haben, als zu denken
Philosoph 4
Gabel 4
Philosoph 3 Gabel 3
Gabel 0
Philosoph 2
Philosoph 0 Gabel 1
Philosoph 1 Gabel 2
haben, als zu denken
und zu essen, sitzen an
und zu essen, sitzen an
einem runden Tisch.
einem runden Tisch.
Denken macht hungrig
Denken macht hungrig
— also wird jeder
— also wird jeder
Philosoph auch essen.
Philosoph auch essen.
Dazu benötigt ein
Dazu benötigt ein
Philosoph jedoch stets
Philosoph jedoch stets
beide neben seinem beide neben seinem
Teller liegenden Gabeln. Teller liegenden Gabeln
19.05.2021 Betriebssysteme: 06 – Verklemmungen 19

Verklemmte Philosophen?
Die drei ersten notwendigen Bedingungen sind erfüllt:
mutual exclusion
Aus hygienischen Gründen dürfen die Philosophen sich keine Gabeln teilen.
■
–
■
–
hold and wait
Die Philosophen hängen vor dem Essen noch so sehr ihren Gedanken nach, dass sie weder echt gleichzeitig die Gabeln greifen können, noch auf die Idee kommen, eine Gabel wieder wegzulegen.
no preemption
Einem anderen Philosophen die Gabel zu entreißen, kommt selbstverständlich nicht in Frage.
Aber kommt es wirklich zu einer Verklemmung?
■
–
19.05.2021 Betriebssysteme: 06 – Verklemmungen 20

Speisende Philosophen: Version 1
/* nebenläufig für
/* nebenläufig für
}
}
}
alle … */
alle … */
void phil (int who) {
void phil (int who) {
while (1) {
while (1) {
}
drop(who);
think();
think();
grab(who);
grab(who);
eat();
eat();
drop(who);
void think () { … }
void think () { … }
void eat () { … }
void eat () { … }
semaphore fork[NPHIL] = { semaphore fork[NPHIL] = {
{1, NULL}, …
{1, NULL}, …
};
};
void grab (int who) {
void grab (int who) {
wait(&fork[who]); wait(&fork[who]);
wait(&fork[(who+1)%NPHIL]); wait(&fork[(who+1)%NPHIL]);
}
}
void drop (int who) {
void drop (int who) {
signal(&fork[who]); signal(&fork[who]);
signal(&fork[(who+1)%NPHIL]); signal(&fork[(who+1)%NPHIL]);
}
}
Mit Hilfe eines Semaphors wird gegenseitiger Ausschluss beim Zugriff Mit Hilfe eines Semaphors wird gegenseitiger Ausschluss beim Zugriff
auf die Gabeln garantiert.
auf die Gabeln garantiert.
Jeder Philosoph nimmt erst sein rechte und dann seine linke Gabel.
Jeder Philosoph nimmt erst sein rechte und dann seine linke Gabel.
19.05.2021 Betriebssysteme: 06 – Verklemmungen 21

… leider verklemmungsgefährdet
Prozesswechsel
void grab(0) { void grab(0) {
wait(&fork[0]); wait(&fork[0]);
}
void grab(1) { void grab(1) {
wait(&fork[1]); wait(&fork[1]);
}
void grab(2) { void grab(2) {
wait(&fork[2]); wait(&fork[2]);
}
void grab(3) { void grab(3) {
wait(&fork[3]); wait(&fork[3]);
Verklemmung!
}
Jeder Philosoph greift sein Jeder Philosoph greift sein
rechte Gabel zuerst.
rechte Gabel zuerst.
void grab(4) { void grab(4) {
wait(&fork[4]); wait(&fork[4]);
wait(&fork[0]); wait(&fork[0]);
}
}
}
wait(&fork[4]); wait(&fork[4]);
}
wait(&fork[3]); wait(&fork[3]);
}
wait(&fork[2]); wait(&fork[2]);
Alle Philosophen blockieren
}
wait(&fork[1]); wait(&fork[1]);
Alle Philosophen blockieren
beim zweiten wait. beim zweiten wait.
19.05.2021 Betriebssysteme: 06 – Verklemmungen 22

… leider verklemmungsgefährdet
Betriebsmittelbelegungsgraph
Betriebsmittelbelegungsgraph
void grab(0) { void grab(0) {
wait(&fork[0]); wait(&fork[0]);
Prozesswechsel
void grab(1) { void grab(1) {
wait(&fork[1]); wait(&fork[1]);
philo philo0
Jeder Philosoph greift sein Jeder Philosoph greift sein
rechte Gabel zuerst.
0
rechte Gabel zuerst.
philo philo4
void grab(2) { void grab(2) {
wait(&fork[2]); wait(&fork[2]);
4
void grab(3) { void grab(3) {
4. circular wait }
wait(&fork[3]); wait(&fork[3]);
wait(&fork[3]); wait(&fork[3]);
void grab(4) { void grab(4) {
philo
philo1 wait(&fork[4]);
fork 4
fork 4
1 wait(&fork[4]); wait(&fork[0]);
wait(&fork[4]); wait(&fork[4]);
}
}
wait(&fork[0]); }
wait(&fork[2]); wpaiht(i&lfork[2]);
}
}
}
2
}
wait(&fork[1]); wait(&fork[1]);
}
philo2 Alle Philosophen blockieren philo Alle Philosophen blockieren
beim zweiten wait. beim zweiten wait.
Verklemmung!
}
philo3 3
fork
fork3 3
fork
fork2 2
19.05.2021
Betriebssysteme: 06 – Verklemmungen 23
fork fork 0
0
fork
fork1 1

Speisende Philosophen: Version 2
■
– –
■
–
semaphore mutex = {1, NULL}; semaphore mutex = {1, NULL};
void grab (int who) {
void grab (int who) {
wait(&mutex); wait(&mutex);
wait(&fork[who]); wait(&fork[who]);
wait(&fork[(who+1)%NPHIL]); wait(&fork[(who+1)%NPHIL]);
signal(&mutex); signal(&mutex);
}
}
Verklemmungsfreiheit? Ja,…
Max. 1 Prozess kann auf eine Gabel warten (Zyklus braucht 2!) Ein Prozess, der auf mutex wartet, hat keine Gabel
Eine„guteLösung“? Nein,…
Wenn philowho isst, blockiert philowho+1 im kritischen Abschnitt. Alle weiteren blockieren dann auch. Viele Spagetti werden kalt.
Geringe Nebenläufigkeit und schlechte Ressourcennutzung
19.05.2021 Betriebssysteme: 06 – Verklemmungen 24
–
Das Problem von Version 1 waren
Das Problem von Version 1 waren
Prozesswechsel zwischen dem 1.
Prozesswechsel zwischen dem 1.
und 2. wait – ein kritischer und 2. wait – ein kritischer
Abschnitt. Version 2 schützt diesen
Abschnitt. Version 2 schützt diesen
kritischen Abschnitt durch
kritischen Abschnitt durch
gegenseitigen Ausschluss.
gegenseitigen Ausschluss.

Speisende Philosophen: Version 3
const int N = 5;
const int N = 5;
semaphore mutex = {1, NULL}; semaphore mutex = {1, NULL};
semaphore s[N] = {{0, NULL},…}; /* ein Semaphor pro Philosoph */ semaphore s[N] = {{0, NULL},…}; /* ein Semaphor pro Philosoph */
enum { THINKING, EATING, HUNGRY } status[N]; /* Philo.-Zustand */
enum { THINKING, EATING, HUNGRY } status[N]; /* Philo.-Zustand */
int left(i) { return (i+N-1)%N; } /* Index linker Nachbar */
int left(i) { return (i+N-1)%N; } /* Index linker Nachbar */
int right(i) { return (i+1)%N; } /* Index rechter Nachbar */
int right(i) { return (i+1)%N; } /* Index rechter Nachbar */
}
}
}
/* Anzahl der Philosophen */
/* Anzahl der Philosophen */
/* Gegens. Ausschluss */
/* Gegens. Ausschluss */
void test (int i) { void test (int i) {
if (status[i] == HUNGRY && status[left(i)] != EATING && if (status[i] == HUNGRY && status[left(i)] != EATING &&
status[right(i)] != EATING) {
status[right(i)] != EATING) {
status[i] = EATING;
status[i] = EATING;
signal(&s[i]); signal(&s[i]);
}
void grab(int i) { void grab(int i) {
wait(&mutex); wait(&mutex);
status[i] = HUNGRY;
status[i] = HUNGRY;
}
signal(&mutex); signal(&mutex);
wait(&s[i]); wait(&s[i]);
}
test(i);
test(i);
void drop(int i) { void drop(int i) {
wait(&mutex); wait(&mutex);
status[i] = THINKING;
status[i] = THINKING;
}
signal(&mutex); signal(&mutex);
}
test(left(i));
test(left(i));
test(right(i));
test(right(i));
Diese Lösung ist
Diese Lösung ist
verklemmungsfrei
verklemmungsfrei
und hat den maximalen
und hat den maximalen
Grad an Nebenläufigkeit.
Grad an Nebenläufigkeit.
19.05.2021 Betriebssysteme: 06 – Verklemmungen 25

Diskussion: Speisende Philosophen
Im Speziellen: Es gibt meist viele Möglichkeiten für Verklemmungsfreiheit zu sorgen
Lösungen unterscheiden sich im Grad der möglichen Nebenläufigkeit
Bei einer zu restriktiven Lösung liegen Betriebsmittel zeitweilig unnötig brach.
■
– –
■
– –
Im Allgemeinen: Repräsentatives Beispiel für Verklemmungsprobleme bei der Verwaltung unteilbarer Betriebsmittel
Geht auf E. Dijkstra zurück (1965)
Etabliertes Standardszenario für die Bewertung und Illustration von Betriebssystem- und Sprachmechanismen zur nebenläufigen Programmierung
19.05.2021 Betriebssysteme: 06 – Verklemmungen 26

Inhalt
Ursachenforschung
Verklemmungen von Prozessen
Konsumierbare und nicht-konsumierbare Betriebsmittel Modellierung durch Betriebsmittelbelegungsgraphen
■ ■
– –
■
–
Ein klassisches Verklemmungsproblem
„Die fünf Philosophen“
■
– – –
■
Zusammenfassung
Gegenmaßnahmen, Verklemmungsbekämpfung
Vorbeugung
Vermeidung
Erkennung und Auflösung
19.05.2021 Betriebssysteme: 06 – Verklemmungen 27

Verklemmungsvorbeugung
(engl. deadlock prevention)
indirekte Methoden entkräften eine der Bedingungen 1–3 1. nicht-blockierendeVerfahrenverwenden
2. Betriebsmittelanforderungen unteilbar (atomar) auslegen
3. Betriebsmittelentzug durch Virtualisierung ermöglichen
virtueller Speicher, virtuelle Geräte, virtuelle Prozessoren
■
■
direkte Methoden entkräften Bedingung 4
4. lineare/totale Ordnung von Betriebsmittelklassen einführen:
Betriebsmittel Bi ist nur dann erfolgreich vor Bj belegbar, wenn i linear vor j angeordnet ist (d.h. i < j). ● ●  Regeln, die das Eintreten von Verklemmungen verhindern Methoden, die zur Entwurfs- bzw. Implementierungszeit greifen 19.05.2021 Betriebssysteme: 06 - Verklemmungen 28 – Verklemmungsvermeidung (engl. deadlock avoidance) Verhinderung von zirkulärem Warten (im laufenden System) durch strategische Maßnahmen: keine der ersten drei notwendigen Bedingungen wird entkräftet fortlaufende Bedarfsanalyse schließt zirkuläres Warten aus ■ – – ■ – – ● es existiert eine Prozessabfolge, bei der jeder Prozess seinen maximalen Betriebsmittelbedarf decken kann ■ Problem: À-priori-Wissen über den maximalen Betriebsmittelbedarf ist erforderlich. Betriebsmittelanforderungen der Prozesse sind zu steuern: sicherer Zustand muss immer beibehalten werden: unsichere Zustände werden umgangen: ● ● Zuteilungsablehnung im Falle nicht abgedeckten Betriebsmittelbedarfs anfordernde Prozesse nicht bedienen bzw. frühzeitig suspendieren 19.05.2021 Betriebssysteme: 06 - Verklemmungen 29 Sicherer/unsicherer Zustand (am Beispiel der speisenden Philosophen) Ausgangspunkt: fünf Gabeln sind insgesamt vorhanden jeder der fünf Philosophen braucht zwei Gabeln zum Essen ■ – ■ – – – – ● Situation: P0 , P1 und P2 haben je eine Gabel und zwei Gabeln sind frei P3 fordert eine Gabel an → eine Gabel wäre dann noch frei sicherer Zustand: einer von drei Philosophen könnte essen die Anforderung von P3 wird akzeptiert P4 fordert eine Gabel an → keine Gabel wäre dann mehr frei ● ● unsicherer Zustand: keiner der Philosophen könnte essen die Anforderung von P4 muss warten Haben vier Philosophen je eine Gabel, wird der fünfte gestoppt, bevor er die erste Gabel nimmt. 19.05.2021 Betriebssysteme: 06 - Verklemmungen 30 Sicherer/unsicherer Zustand Ausgangspunkt: fünf Gabeln sind insgesamt vorhanden Situation: P0 , P1 und P2 haben je eine Gabel und (am Beispiel der speisenden Philosophen) Erkennung: Betriebsmittelbelegungsgraph Erkennung: Betriebsmittelbelegungsgraph ■ ■ philo –0 jeder der fünf Philosophen braucht zwpeihGilaobeln zum Essen 0 zwei Gabeln sind frei – – – – P3 fordert eine Gabel an → eine Gabel wäre dann noch frei philo philo4 4 Die Umwandlung dieser ● sicherer Zustand: einer von drei Philosophen könnte essen Die Umwandlung dieser fork4 echte Belegung würde „Claim-Kante“ in eine „Claim-Kante“ in eine philo 1 die Anforderung von P3 wird akzeptiert philo 1 fork echte Belegung würde 4 zu einem Zyklus führen P4 fordert eine Gabel an → keine Gabel wäre dann mehr frei zu einem Zyklus führen unsicherer Zustand: keiner der Philosophen könnte essen ● ● Haben vier Philosophen je eine Gabel, wird der fünfte gestoppt, bevor er die erste die Anforderung von P4 wird abgelehnt, P4 muss warten 2 philo philo3 fork fork2 Gabel nimmt. philo philo2 3 fork fork3 3 2 19.05.2021 Betriebssysteme: 06 - Verklemmungen 31 fork fork 0 0 fork fork1 1 Sicherer/unsicherer Zustand (am Beispiel mehrfach vorhandener Betriebsmittel) Ausgangspunkt: ein primitives UNIX-System mit max. 12 Shared-Memory-Segmenten Prozess P0 benötigt max. 10 Segmente, P1 vier und P2 neun ■ – ■ – – – ● Situation: P0 belegt 6 Segmente, P1 und P2 je zwei; zwei Segmente sind frei P2 fordert ein Segment an, eins bliebe frei → unsicherer Zustand die Anforderung von P2 wird abgelehnt, P2 muss warten P0 fordert zwei Segmente an, keines bliebe frei → unsicherer Zustand die Anforderung von P0 wird abgelehnt, P0 muss warten sichere Prozessfolge: P1 → P0 → P2 ● 19.05.2021 Betriebssysteme: 06 - Verklemmungen 32 Sicherer/unsicherer Zustand (am Beispiel mehrfach vorhandener Betriebsmittel) ■ für aktuelle Belegung und maximale Belegung – Prozess P0 benötigt max. 10 Segmente, P1 vier und P2 neun – – – der die Betriebsmittel auch bei vollständiger ● die Anforderung von P2 wird abgelehnt, P2 muss warten ● die Anforderung von P0 wird abgelehnt, P0 muss warten • Verwaltung Prozess/Betriebsmittel-Matrizen Verwaltung Prozess/Betriebsmittel-Matrizen • • Erkennung: „Bankier-Algorithmus“ Erkennung: „Bankier-Algorithmus“ ■ Ausgangspunkt: ein primitives UNIX-System mit max. 12 Shared-Memory-Segmenten Situation: P0 belegt 6 Segmente, P1 und P2 je zwei; für aktuelle Belegung und maximale Belegung zwei Segmente sind frei • Funktion zum Finden einer Prozessabfolge, bei Funktion zum Finden einer Prozessabfolge, bei P2 fordert ein Segment an, eins bliebe frei → unsicherer Zustand der die Betriebsmittel auch bei vollständiger Ausschöpfung des „Kreditlimits“ nicht ausgehen Ausschöpfung des „Kreditlimits“ nicht ausgehen P0 fordert zwei Segm. an, keines bliebe frei → unsicherer Zustand Vorausschauende Anwendung dieser Funktion • VorausschauendeAnwendungdieserFunktion • im Falle von Betriebsmittelanforderungen im Falle von Betriebsmittelanforderungen sichere Prozessfolge: P1 → P0 → P2 (für mehr Details siehe Tanenbaum) (für mehr Details siehe Tanenbaum) 19.05.2021 Betriebssysteme: 06 - Verklemmungen 33 Verklemmungserkennung (engl. deadlock detection) Verklemmungen werden (stillschweigend) in Kauf genommen (ostrich algorithm) ... Nichts im System verhindert das Auftreten von Wartezyklen Keine der vier Bedingungen wird entkräftet ■ – – ■ – – ■ – – – Ansatz: Wartegraph erstellen und Zyklen suchen → O(n) Zu häufige Überprüfung verschwendet Betriebsmittel/Rechenleistung Zu seltene Überprüfung lässt Betriebsmittel brach liegen Zyklensuche geschieht zumeist in großen Zeitabständen, wenn ... Betriebsmittelanforderungen zu lange andauern die Auslastung der CPU trotz Prozesszunahme sinkt die CPU bereits über einen sehr langen Zeitraum untätig ist 19.05.2021 Betriebssysteme: 06 - Verklemmungen 34 Verklemmungsauflösung Erholungsphase nach der Erkennungsphase Prozesse abbrechen und so Betriebsmittel frei bekommen Verklemmte Prozesse schrittweise abbrechen (großer Aufwand) Mit dem „effektivsten Opfer“ (?) beginnen Alle verklemmten Prozesse terminieren (großer Schaden) ■ – – ● ■ – – – ● Transaktionen, checkpointing/recovery (großer Aufwand) ■ – Betriebsmittel entziehen und mit dem effektivsten Opfer (?) beginnen Betreffenden Prozess zurückfahren bzw. wieder aufsetzen Ein Aushungern der zurückgefahrenen Prozesse ist zu vermeiden Außerdem Vorsicht vor Livelocks! Gratwanderung zwischen Schaden und Aufwand: Schäden sind unvermeidbar, und die Frage ist, wie sie sich auswirken 19.05.2021 Betriebssysteme: 06 - Verklemmungen 35 Diskussion der Gegenmaßnahmen Verfahren zum Vermeiden/Erkennen sind im Betriebssystemkontext weniger praxisrelevant Sie sind kaum umzusetzen, zu aufwändig und damit nicht einsetzbar Zudem macht die Vorherrschaft sequentieller Programmierung diese Verfahren wenig notwendig ■ – – Verklemmungsgefahr ist lösbar durch Virtualisierung von Betriebsmitteln Prozesse beanspruchen/belegen ausschließlich logische Betriebsmittel Der Trick besteht darin, in kritischen Momenten den Prozessen (ohne ihr Wissen) physische Betriebsmittel entziehen zu können Dadurch wird die Bedingung der Nichtentziehbarkeit entkräftet ➔ Eher praxisrelevant/verbreitet sind die Vorbeugungsmaßnahmen. 19.05.2021 Betriebssysteme: 06 - Verklemmungen 36 ■ – – – Inhalt Ursachenforschung Verklemmungen von Prozessen Konsumierbare und nicht-konsumierbare Betriebsmittel Modellierung durch Betriebsmittelbelegungsgraphen ■ ■ – – ■ – ■ – – – ■ Zusammenfassung Ein klassisches Verklemmungsproblem „Die fünf Philosophen“ Gegenmaßnahmen, Verklemmungsbekämpfung Vorbeugung Vermeidung Erkennung und Auflösung 19.05.2021 Betriebssysteme: 06 - Verklemmungen 37 Zusammenfassung Verklemmung bedeutet Deadlock oder Livelock „[...] einen Zustand, in dem die beteiligten Prozesse wechselseitig auf den Eintritt von Bedingungen warten, die nur durch andere Prozesse in dieser Gruppe selbst hergestellt werden können“ Dabei ist der Livelock das größere Problem beider Verklemmungsarten. ■ – – ■ – – ■ – – Für Verklemmungen müssen vier Bedingungen gleichzeitig gelten: Exklusive Belegung, Nachforderung, kein Entzug von Betriebsmitteln Zirkuläres Warten der die Betriebsmittel beanspruchenden Prozesse Verklemmungsbekämpfung meint: Vorbeugen, Vermeiden, Erkennen/Auflösen die Verfahren können im Mix zum Einsatz kommen 19.05.2021 Betriebssysteme: 06 - Verklemmungen 38 Betriebssysteme (BS) 07. Interprozesskommunikation https://sys.cs.tu-dortmund.de/DE/Teaching/SS2021/BS/ 26.05.2021 Peter Ulbrich peter.ulbrich@tu-dortmund.de Basierend auf Betriebssysteme von Olaf Spinczyk, Universität Osnabrück Wiederholung Prozesse können miteinander interagieren Aufeinander warten (Synchronisation) Daten austauschen (Kommunikation) ■ – – ■ – – ■ – Wartemechanismen ... sind notwendig für kontrollierte Kommunikation können zu Verklemmungen führen Datenaustausch wurde bisher nur am Rande betrachtet Leicht- und federgewichtige Prozesse im selben Adressraum 26.05.2021 Betriebssysteme: 07 - Interprozesskommunikation 2 Inhalt Grundlagen der Interprozesskommunikation Lokale Interprozesskommunikation unter UNIX Signale Pipes Message Queues ■ ■ – – – ■ – – Rechnerübergreifende Interprozesskommunikation Sockets Entfernte Prozeduraufrufe (RPCs) ■ Zusammenfassung 26.05.2021 Betriebssysteme: 07 - Interprozesskommunikation 3 Tanenbaum 2.3: Interprozesskommunikation Silberschatz 3.4: Interprocess Communication Interprozesskommunikation Inter-Process Communication (IPC) Mehrere Prozesse bearbeiten eine Aufgabe: gleichzeitiges Nutzung von zur Verfügung stehender Information durch mehrere Prozesse Verkürzung der Bearbeitungszeit durch Parallelisierung Verbergen von Bearbeitungszeiten durch Ausführung „im Hintergrund“ ■ – – – ■ – – ■ – – Kommunikation durch gemeinsamen Speicher Datenaustausch nebenläufiges Schreiben in bzw. Lesen aus einem gemeinsamen Speicher Dabei muss auf Synchronisation geachtet werden. Heute: Kommunikation durch Nachrichten Nachrichten werden zwischen Prozessen ausgetauscht Gemeinsamer Speicher ist nicht erforderlich 26.05.2021 Betriebssysteme: 07 - Interprozesskommunikation 4 Nachrichtenbasierte Kommunikation ■ ... basiert auf zwei Primitiven: ■ – – – send (Ziel, Nachricht) send (Ziel, Nachricht) receive (Quelle, Nachricht) receive (Quelle, Nachricht) Unterschiede gibt es in ... Synchronisation Adressierung und diversen anderen Eigenschaften (oder ähnlich) 26.05.2021 Betriebssysteme: 07 - Interprozesskommunikation 5 Synchronisation ... bei nachrichtenbasierter Kommunikation Synchronisation bei Senden / Empfangen Synchroner Nachrichtenaustausch (auch Rendezvous) ■ – – ● ● Empfänger blockiert bis die Nachricht eingetroffen ist. Sender blockiert bis die Ankunft der Nachricht bestätigt ist. ■ – Asynchroner Nachrichtenaustausch ● ● ● Sender gibt die Nachricht dem Betriebssystem und arbeitet weiter Blockierung auf beiden Seiten optional Pufferung immer erforderlich Häufig anzutreffen: Asynchroner Nachrichtenaustausch mit potentiell blockierendem Senden und Empfangen 26.05.2021 Betriebssysteme: 07 - Interprozesskommunikation 6 Adressierung ... bei nachrichtenbasierter Kommunikation Direkte Adressierung Prozess-ID (Signale) Kommunikationsendpunkt eines Prozesses (Port, Socket) ■ – – ■ – – ■ – – – Unicast Multicast Broadcast – an genau einen – an eine Auswahl – an alle Indirekte Adressierung Kanäle (Pipes) Briefkästen (Mailboxes), Nachrichtenpuffer (Message Queues) Zusätzliche Dimension: Gruppenadressierung 26.05.2021 Betriebssysteme: 07 - Interprozesskommunikation 7 Diverse andere Eigenschaften ... bei nachrichtenbasierter Kommunikation Nachrichtenformat Stromorientiert / nachrichtenorientiert Feste Länge / variable Länge Getypt / ungetypt ■ – – – ■ – – – Übertragung Unidirektional / Bidirektional (halb-duplex, voll-duplex) zuverlässig / unzuverlässig Reihenfolge bleibt erhalten / nicht erhalten 26.05.2021 Betriebssysteme: 07 - Interprozesskommunikation 8 Inhalt Grundlagen der Interprozesskommunikation Lokale Interprozesskommunikation unter UNIX Signale Pipes Message Queues ■ ■ – – – ■ – – ■ Zusammenfassung Rechnerübergreifende Interprozesskommunikation Sockets Entfernte Prozeduraufrufe (RPCs) 26.05.2021 Betriebssysteme: 07 - Interprozesskommunikation 9 UNIX-Signale Signale sind in Software nachgebildete Unterbrechungen ähnlich denen eines Prozessors durch E/A-Geräte minimale Form der Interprozesskommunikation (Übertragung der Signalnummer) ■ – – ■ – – ■ – – – Sender Prozesse ... mit Hilfe des Systemaufrufs kill(2) Betriebssystem ... bei Auftreten bestimmter Ereignisse Empfänger-Prozess führt Signalbehandlung durch: Ignorieren, Terminierung des Prozesses oder Aufruf einer Behandlungsfunktion ● Nach der Behandlung läuft Prozess an unterbrochener Stelle weiter. 26.05.2021 Betriebssysteme: 07 - Interprozesskommunikation 10 Signale Mit Hilfe von Signalen können Prozesse über Ausnahmesituation informiert werden ähnlich wie Hardwareunterbrechungen ■ – ■ – – – – – – – Prozess abbrechen (z.B. bei Ctrl-C) Prozess anhalten (z.B. bei Ctrl-Z) Fenstergröße wurde geändert Kindprozess terminiert Speicherschutzverletzung des Prozesses Prozess wird getötet Beispiele: SIGINT SIGSTOP SIGWINCH SIGCHLD SIGSEGV SIGKILL ... Die Standardbehandlung (terminieren, anhalten, ...) kann für die meisten Signale überdefiniert werden. siehe signal(2) 26.05.2021 Betriebssysteme: 07 - Interprozesskommunikation 11 ■ – UNIX-Signale: Logische Sicht Hollywood-Prinzip: Don't call us, we'll call you. Empfänger- prozess normal Beh. 1 1 4 2 Beh. 2 3 Sender- prozess 1 kill Sender- prozess 2 2 kill 1 Betriebssysteme: 07 - Interprozesskommunikation 12 Signalisierung und Start Signalisierung und Start der Behandlungsroutine der Behandlungsroutine erfolgen in der logischen erfolgen in der logischen Sicht gleichzeitig. Sicht gleichzeitig. 26.05.2021 Behandlungsroutinen Behandlungsroutinen können auch unter- können auch unter- brochen werden. brochen werden. UNIX-Signale: Technische Sicht Die Signalbehandlung erfolgt immer beim Übergang vom Kernel in der User Mode. Was passiert also wirklich, wenn der Zielprozess gerade ... läuft, also im Zustand RUNNING ist (z.B. Segmentation Fault, Bus Error)? Unmittelbarer Start der Behandlungsroutine gerade nicht läuft, aber READY ist (z.B. Systemaufruf kill)? ■ ■ – – – ● ● Im Prozesskontrollblock wird das Signal vermerkt. Wenn der Prozess die CPU zugeteilt bekommt, erfolgt die Behandlung. auf E/A wartet, also BLOCKED ist? ● ● ● ● ● Der E/A-Systemaufruf (z.B. read) wird mit Fehlercode EINTR abgebrochen. Der Prozesszustand wird auf READY gesetzt. Danach wie bei 2. Ggf. wird der unterbrochene Systemaufruf neu ausgeführt (SA_RESTART). 26.05.2021 Betriebssysteme: 07 - Interprozesskommunikation 13 UNIX-Signale: Beispiel Auszug aus dem Handbuch des Apache HTTP-Servers TERM Signal: stop now Stopping and Restarting Apache Stopping and Restarting Apache To send a signal to the parent you should issue a command such as: To send a signal to the parent you should issue a command such as: TERM Signal: stop now kill -TERM `cat /usr/local/apache/logs/httpd.pid` kill -TERM `cat /usr/local/apache/logs/httpd.pid` Sending the TERM signal to the parent causes it to immediately attempt to kill off all of its children. Sending the TERM signal to the parent causes it to immediately attempt to kill off all of its children. It may take it several seconds to complete killing off its children. Then the parent itself exits. Any It may take it several seconds to complete killing off its children. Then the parent itself exits. Any requests in progress are terminated, and no further requests are served. requests in progress are terminated, and no further requests are served. HUP Signal: restart now HUP Signal: restart now Sending the HUP signal to the parent causes it to kill off its children like in TERM but the parent Sending the HUP signal to the parent causes it to kill off its children like in TERM but the parent doesn't exit. It re-reads its configuration files, and re-opens any log files. Then it spawns a new set doesn't exit. It re-reads its configuration files, and re-opens any log files. Then it spawns a new set of children and continues serving hits. of children and continues serving hits. USR1 Signal: graceful restart USR1 Signal: graceful restart The USR1 signal causes the parent process to advise the children to exit after their current request The USR1 signal causes the parent process to advise the children to exit after their current request (or to exit immediately if they're not serving anything). The parent re-reads its configuration files and (or to exit immediately if they're not serving anything). The parent re-reads its configuration files and re-opens its log files. As each child dies off the parent replaces it with a child from the new re-opens its log files. As each child dies off the parent replaces it with a child from the new generation of the configuration, which begins serving new requests immediately. generation of the configuration, which begins serving new requests immediately. 26.05.2021 Betriebssysteme: 07 - Interprozesskommunikation 14 UNIX Pipes Kanal zwischen zwei Kommunikationspartnern unidirektional gepuffert (feste Puffergröße) zuverlässig stromorientiert ■ – – – – ■ – – Operationen: Schreiben und Lesen Ordnung der Zeichen bleibt erhalten (Zeichenstrom) Blockierung bei voller Pipe (Schreiben) und leerer Pipe (Lesen) Pipe schreiben frei gefüllt lesen Sender- prozess Empfänger- prozess 26.05.2021 Betriebssysteme: 07 - Interprozesskommunikation 15 UNIX Pipes: Programmierung Unbenannte Pipes ErzeugeneinerPipe:int pipe (int fdes[2]) NacherfolgreichemAufruf(Rückgabewert== 0)kannman... ■ – – – ● über fdes[0] aus der Pipe lesen (Systemaufruf read) ■ – – über fdes[1] in die Pipe schreiben (Systemaufruf write) Nun muss man nur noch das eine Ende an einen anderen Prozess weitergeben. (siehe nächste Folie) ● Benannte Pipes Pipes können auch als Spezialdateien ins Dateisystem gelegt werden: int mkfifo (, mode_t mode)
Standardfunktionen zum Öffnen, Lesen, Schreiben und Schließen können dann verwendet werden.
●
Normale Dateizugriffsrechte regeln, wer die Pipe benutzen darf.
26.05.2021
Betriebssysteme: 07 – Interprozesskommunikation 16

UNIX Pipes: Programmierung
Unebneumna{nRnEtAeD=P0,ipWeRsITE=1 }; enum { READ=0, WRITE=1 };
– –
–
■
■
Benannte Pipes
–
–
Pipes können auch als Spezialdateien ins Dateisystem gelegt werden: close (fd[WRITE]); /* Schreibseite schließen */
Erzeugen einer Pipe: int pipe (int fdes[2]) int main (int argc, char *argv[]) {
int main (int argc, char *argv[]) {
}
…Fehler behandeln
}
NacherfolgreichemAufruf(Rückgabewert== 0)kannman… int res, fd[2];
int res, fd[2];
if (pipe (fd) == 0) { /* Pipe erzeugen */
if (pipe (fd) == 0) { /* Pipe erzeugen */
●
über fdes[0] aus der Pipe lesen (Systemaufruf read) res = fork ();
●
über fdes[1] in die Pipe schreiben (Systemaufruf write) if (res > 0) { /* Elternprozess */
●
Normale Dateizugriffsrechte regeln, wer die Pipe benutzen darf.
}
}
res = fork ();
if (res > 0) { /* Elternprozess */
close (fd[READ]); /* Leseseite schließen */
close (fd[READ]); /* Leseseite schließen */
Nun muss man nur noch das eine Ende an einen anderen Prozess weitergeben.
}
}
dup2 (fd[WRITE], 1); /* Std-Ausgabe in Pipe */ dup2 (fd[WRITE], 1); /* Std-Ausgabe in Pipe */
(siehe nächste Folie)
close (fd[WRITE]); /* Deskriptor freigeben */ close (fd[WRITE]); /* Deskriptor freigeben */
execlp (argv[1], argv[1], NULL); /* Schreiber ausführen */ execlp (argv[1], argv[1], NULL); /* Schreiber ausführen */
else if (res == 0) { /* Kindprozess */ else if (res == 0) { /* Kindprozess */
close (fd[WRITE]); /* Schreibseite schließen */ int mkfifo (, mode_t mode)
}
*/
}
dup2 (fd[READ], 0); /* Std-Eingabe aus Pipe */ dup2 (fd[READ], 0); /* Std-Eingabe aus Pipe */
Standcalrodsfeun(kftdio[nReEAnDz]u)m; Öffnen, Lesen, Sc/h*reDibeseknruinptdoSrchfrlieißgenben */ close (fd[READ]); /* Deskriptor freigeben */
könneenxdeaclnpn v(earwgve[n2d]e,t waregrdv[e2n]., NULL); /* Leser ausführen
execlp (argv[2], argv[2], NULL); /* Leser ausführen */
…Fehler behandeln
26.05.2021 Betriebssysteme: 07 – Interprozesskommunikation
17

UNIX Pipes: Programmierung
Unebneumna{nRnEtAeD=P0,ipWeRsITE=1 }; enum { READ=0, WRITE=1 };
– –
■
Erzeugen einer Pipe: int pipe (int fdes[2]) int main (int argc, char *argv[]) {
int main (int argc, char *argv[]) {
NacherfolgreichemAufruf(Rückgabewert== 0)kannman…
int res, fd[2]; int res, fd[2];
„./connect ls wc“entspricht „./connect ls wc“entspricht
if (pipe (fd) == 0) { /* Pipe erzeugen */ if (pipe (fd) == 0) { /* Pipe erzeugen */
●
dem Shell-Kommando „ls|wc“ dem Shell-Kommando „ls|wc“
●
über fdes[1] in die Pipe schreiben (Systemaufruf write) if (res > 0) { /* Elternprozess */
über fdes[0] aus der Pipe lesen (Systemaufruf read)
res = fork ();
res = fork ();
if (res > 0) { /* Elternprozess */
close (fd[READ]); /* Leseseite schließen */
close (fd[READ]); /* Leseseite schließen */ ulbrNiucnh@mkuoss:m~/anV_nBuSr /nvoochrldeasueninge/Ecnode>anlesinen anderen Prozess weitergeben.
ulbrich@kos:~/V_BS/vorlesung/code> ls
–
dup2 (fd[WRITE], 1); /* Std-Ausgabe in Pipe */ dup2 (fd[WRITE], 1); /* Std-Ausgabe in Pipe */
conn(esicethe ncäocnhnsetecFto.lcie) execl.c fork.c orphan.c wait.c connect connect.c execl.c fork.c orphan.c wait.c
close (fd[WRITE]); /* Deskriptor freigeben */ close (fd[WRITE]); /* Deskriptor freigeben */
ulbrich@kos:~/V_BS/vorlesung/code> ./connect ls wc
ulbrich@ekxoescl:p~/(Va_rgBvS[/1v]o,ralregsvu[1n]g,/cNoULdLe)>; ./*/cSocnhnreicbterlasuswfcühren */
■
–
–
Benannte Pipes
}
…Fehler behandeln
}
execlp (argv[1], argv[1], NULL); /* Schreiber ausführen */
6 6 49
}
}
6 6 49
else if (res == 0) { /* Kindprozess */ else if (res == 0) { /* Kindprozess */
Pipes können auch als Spezialdateien ins Dateisystem gelegt werden: close (fd[WRITE]); /* Schreibseite schließen */
close (fd[WRITE]); /* Schreibseite schließen */ int mkfifo (, mode_t mode)
dup2 (fd[READ], 0); /* Std-Eingabe aus Pipe */ dup2 (fd[READ], 0); /* Std-Eingabe aus Pipe */
Standcalrodsfeun(kftdio[nReEAnDz]u)m; Öffnen, Lesen, Sc/h*reDibeseknruinptdoSrchfrlieißgenben */ close (fd[READ]); /* Deskriptor freigeben */
könneenxdeaclnpn v(earwgve[n2d]e,t waregrdv[e2n]., NULL); /* Leser ausführen
●
Normale Dateizugriffsrechte regeln, wer die Pipe benutzen darf.
}
}
}
*/
}
execlp (argv[2], argv[2], NULL); /* Leser ausführen */
…Fehler behandeln
26.05.2021 Betriebssysteme: 07 – Interprozesskommunikation
18

UNIX Message Queues
Rechnerweit eindeutige Adresse (Key) dient zur Identifikation
Zugriffsrechte wie auf Dateien
Prozesslokale Nummer (MsqID) wird bei allen Operationen benötigt
Ungerichtete M:N-Kommunikation
Gepuffert
einstellbare Größe pro Queue
Nachrichten haben einen Typ (long-Wert)
Operationen zum Senden und Empfangen einer Nachricht
blockierend — nicht-blockierend (aber nicht asynchron) Empfang aller Nachrichten — nur ein bestimmter Typ
■
– –
■ ■
–
■ ■
– –
26.05.2021 Betriebssysteme: 07 – Interprozesskommunikation 19

UNIX Message Queues
Rechnerweit eindeutige Adresse (Key) dient zur Identifikation
■
Prozess 1
Zugriffsrechte wie auf Dateien
–
– Prozesslokale Nummer (MsqID) wird bei allen Operationen benötigt
Message Queue ID3 Key
einstellbare Größe pro Queue
Nachrichten haben einen Typ (long-Wert)
Prozess 3
■ ID1
Ungerichtete M:N-Kommunikation
■
–
■ ■
– –
ID2
Gepuffert
Operationen zum Senden und Empfangen einer Nachricht
Prozess 2
blockierend — nicht-blockierend (aber nicht asynchron) Empfang aller Nachrichten — nur ein bestimmter Typ
Message Queues werden heutzutage nur noch Message Queues werden heutzutage nur noch
Rechner selten eingesetzt, da sie anders als Sockets
selten eingesetzt, da sie anders als Sockets
(siehe nächster Abschnitt) auf lokale
(siehe nächster Abschnitt) auf lokale
Kommunikation beschränkt sind. Zudem ist
Kommunikation beschränkt sind. Zudem ist
der Anwendungscode weniger portabel.
der Anwendungscode weniger portabel.
26.05.2021
Betriebssysteme: 07 – Interprozesskommunikation 20

Inhalt
Grundlagen der Interprozesskommunikation
Lokale Interprozesskommunikation unter UNIX
Signale
Pipes
Message Queues
■ ■
– – –
■
– –
■
Zusammenfassung
Rechnerübergreifende Interprozesskommunikation
Sockets
Entfernte Prozeduraufrufe (RPCs)
26.05.2021 Betriebssysteme: 07 – Interprozesskommunikation 21

Sockets
Allgemeine Kommunikationsendpunkte im Rechnernetz
Bidirektional Gepuffert
■
– –
■
–
Abstrahiert von Details des Kommunikationssystems
Beschrieben durch Domäne (Protokollfamilie), Typ und Protokoll
Socket Socket
Socket
Rechnernetz
Prozess 1
Prozess 3
Prozess 2
26.05.2021 Betriebssysteme: 07 – Interprozesskommunikation 22

Sockets: Domänen
UNIX Domain
UNIX Domain Sockets verhalten sich wie bidirektionale Pipes. Anlage als Spezialdatei im Dateisystem möglich.
■
– –
■
–
Internet Domain
Dienen der rechnerübergreifenden Kommunikation mit Internet-Protokollen
Appletalk Domain, DECnet Domain, … Domänen bestimmen mögliche Protokolle
z.B. Internet Domain: TCP/IP oder UDP/IP Domänen bestimmen die Adressfamilie
z.B. Internet Domain: IP-Adresse und Port-Nummer
26.05.2021 Betriebssysteme: 07 – Interprozesskommunikation 23
■
■
–
■
–

Sockets: Typ und Protokoll
Die wichtigsten Sockettypen:
stromorientiert, verbindungsorientiert und gesichert nachrichtenorientiert und ungesichert nachrichtenorientiert und gesichert
■
– – –
■
–
–
●
strom- und verbindungsorientiert, gesichert
■
Protokollangabe ist oft redundant
Protokolle der Internet Domain:
TCP/IP Protokoll
UDP/IP Protokoll
●
●
●
●
nachrichtenorientiert, verbindungslos, ungesichert Nachrichten können verloren oder dupliziert werden Reihenfolge kann durcheinander geraten Paketgrenzen bleiben erhalten (Datagramm-Protokoll)
26.05.2021 Betriebssysteme: 07 – Interprozesskommunikation 24

Sockets: Programmierung
Anlegen von Sockets
Generieren eines Sockets mit (Rückgabewert ist ein Filedeskriptor)
int socket (int domain, int type, int proto); Adresszuteilung
Sockets werden ohne Adresse generiert Adressenzuteilung erfolgt durch:
int bind (int socket,
const struct sockaddr *address,
socklen_t address_len);
struct sockaddr_in(fürdieInternet-Adressfamilie)enthält:
sin_family: AF_INET
■
–
–
● ●
●
26.05.2021
Betriebssysteme: 07 – Interprozesskommunikation 25
sin_port: sin_addr:
16-Bit-Portnummer Struktur mit der IP-Adresse, z.B. 192.168.2.1
Hinweis: Für IPv6 gibt es Hinweis: Für IPv6 gibt es
sockaddr_in6 und AF_INET6 sockaddr_in6 und AF_INET6

Sockets: Programmierung
Datagram Sockets
Kein Verbindungsaufbau notwendig
Datagramm senden
ssize_t sendto (int socket, const void *message, size_t length, int flags,
const struct sockaddr *dest_addr,
socklen_t dest_len);
■
– –
–
Datagramm empfangen
ssize_t recvfrom (int socket, void *buffer, size_t length, int flags, struct sockaddr *address,
socklen_t *address_len);
26.05.2021 Betriebssysteme: 07 – Interprozesskommunikation 26

Sockets: Programmierung
Stream Sockets
Verbindungsaufbau notwendig
Client (Benutzer, Benutzerprogramm) will zu einem Server (Dienstanbieter) eine Kommunikationsverbindung aufbauen
■
– –
■
–
Client: Verbindungsaufbau bei stromorientierten Sockets
Verbinden des Sockets mit
int connect (int socket,
const struct sockaddr *address,
socklen_t address_len);
Senden und Empfangen mit write und read (oder send und recv)
Beenden der Verbindung mit close (schließt den Socket)
– –
26.05.2021 Betriebssysteme: 07 – Interprozesskommunikation 27

Sockets: Programmierung
Server: akzeptiert Anfragen/Aufträge
bindet Socket an eine Adresse (sonst nicht erreichbar) bereitet Socket auf Verbindungsanforderungen vor durch
int listen (int s, int queuelen); akzeptiert einzelne Verbindungsanforderungen durch
int accept (int s, struct sockaddr *addr, socklen_t *addrlen);
■
– –
–
– – –
●
gibt einen neuen Socket zurück, der mit dem Client verbunden ist
blockiert, falls kein Verbindungswunsch vorhanden
liest Daten mit read und führt den angebotenen Dienst aus
schickt das Ergebnis mit write zurück zum Sender schließt den neuen Socket mit close
●
26.05.2021 Betriebssysteme: 07 – Interprozesskommunikation 28

Sockets: Programmierung
■ Server: akzeptiert Anfragen/Aufträge #define PORT 6789
#define PORT 6789
#definbeindMAeXtRSEoQck(e4t0a96n*e1i0n2e4A)dresse (sonst nicht erreichbar)
#define MAXREQ (4096*1024)
–
bereitet Socket auf Verbindungsanforderungen vor durch char buffer[MAXREQ], body[MAXREQ+1000], msg[MAXREQ+2000];
–
char buffer[MAXREQ], body[MAXREQ+1000], msg[MAXREQ+2000]; void eirnrtor(lciosntstench(airn*tmssg,) {inpterrqoure(umesgl)e;n)e;xit(1); }
void error(const char *msg) { perror(msg); exit(1); } int main() {
int main() {
–
akzeptiert einzelne Verbindungsanforderungen durch
int sockfd, newsockfd; int sockfd, newsockfd;
socklen_t clilen;
socklen_t clilen;
struicnttsoackcaeddprt_i(nisnetrvs_,addsrt,ruclcit_asdodrc;kaddr *addr, struct sockaddr_in serv_addr, cli_addr;
int n; int n;
socklen_t *addrlen);
Hier wird der Socket
sockfd = socket(PF_INET, SOCK_STREAM, 0); sockfd = socket(PF_INET, SOCK_STREAM, 0);
if (sockfd < 0) error("ERROR opening socket"); if (sockfd < 0) error("ERROR opening socket"); ● Hier wird der Socket gibteinenneuenSocketzurück,dermitdemClientverbuAndreensiset gebunden. bzero((char *) &serv_addr, sizeof(serv_addr)); Adressegebunden. bzero((char *) &serv_addr, sizeof(serv_addr)); serv_addr.sin_family = AF_INET; serv_ blockiert, falls kein Verbindungswunsch vorhanden ● addr.sin_family = AF_INET; serv_addr.sin_addr.s_addr = INADDR_ANY; serv_addr.sin_addr.s_addr = INADDR_ANY; liest Daten mit read und führt den angebotenen Dienst aus serv_addr.sin_port = htons(PORT); – serv_addr.sin_port = htons(PORT); if (bind(sockfd, (struct sockaddr *) &serv_addr, sizeof(serv_addr)) < 0) if (bind(sockfd, (struct sockaddr *) &serv_addr, sizeof(serv_addr)) < 0) schickt das Ergebnis mit write zurück zum Sender –error("ERROR on binding"); error("ERROR on binding"); schließt den neuen Socket mit close listen(sockfd,5); – listen(sockfd,5); ... ... erstellt und an eine erstellt und an eine 26.05.2021 Betriebssysteme: 07 - Interprozesskommunikation 29 Sockets: Programmierung ■ Server: akzeptiert Anfragen/Aufträge ... wh–ile (1) { ... bindetSocketaneineAdresse(sonstnichterreichbar) while (1) { Eine neue Verbindung akzeptieren – } }– } – akzeptiert einzelne Verbindungsanforderungen durch – clilen = sizeof(cli_addr); clilen = sizeof(cli_addr); Eine neue Verbindung akzeptieren bereitet Socket auf Verbindungsanforderungen vor durch newsockfd = accept (sockfd, (struct sockaddr *) &cli_addr, &clilen); newsockfd = accept (sockfd, (struct sockaddr *) &cli_addr, &clilen); if (newsockfd < 0) error("ERROR on accept"); if (newsockfd < 0) error("ERROR on accept"); int listen (int s, int queuelen); bzero(buffer,sizeof(buffer)); bzero(buffer,sizeof(buffer)); n = read (newsockfd,buffer,sizeof(buffer)-1); n = read (newsockfd,buffer,sizeof(buffer)-1); if (n < 0) error("ERROR reading from socket"); if (n < 0) error("ERROR reading from socket"); snprintf (body, sizeof (body), snprintf (body, sizeof (body), "\n\n”
“\n\n”
int accept (int s, struct sockaddr *addr, “

Hallo Webbrowser

\nDeine Anfrage war …\n”
“

Hallo Webbrowser

\nDeine Anfrage war …\n”
“

%s

\n” “

%son\_n"t *addrlen);

"\n\n", buffer);

"\n\n", buffer);

snprintf (msg, sizeof (msg), snprintf (msg, sizeof (msg),

●

●

gibt einen neuen Socket zurück, der mit dem Client ve

"HTTP/1.0 200 OK\n"

"HTTP/1.0 200 OK\n"

"Content-Type: text/html\n" block"ieCrot,nftaellnstk-eTinypVe:rbtinedxutn/ghstwmuln\snc"h vorhanden

    "Content-Length: %zd\n\n%s", strlen (body), body);

    "Content-Length: %zd\n\n%s", strlen (body), body);

liest Daten mit read und führt den angebotenen Dienst aus n = write (newsockfd,msg,strlen(msg));

n = write (newsockfd,msg,strlen(msg));

if (n < 0) error("ERROR writing to socket"); –if (n < 0) error("ERROR writing to socket");
schickt das Ergebnis mit write zurück zum Sender close (newsockfd);
close (newsockfd);
schließt den neuen Socket mit close }
HTTP-Anfrage einlesen
HTTP-Anfrage einlesen
 Antwort generieren und
Antwort generieren und
rbunden ist
zurückschicken
zurückschicken
 Verbindung wieder
Verbindung wieder
schließen.
schließen.
 26.05.2021 Betriebssysteme: 07 - Interprozesskommunikation 30
 
   Sockets: Beispiel HTTP Echo
  26.05.2021 Betriebssysteme: 07 - Interprozesskommunikation 31
 
   Fernaufruf (RPC)
Funktionsaufruf über Prozessgrenzen hinweg (Remote Procedure Call)
hoher Abstraktionsgrad
selten wird Fernaufruf direkt vom System angeboten; benötigt Abbildung auf andere Kommunikationsformen (z.B. auf Nachrichten)
■
– –
–
Abbildung auf mehrere Nachrichten
●
●
Auftragsnachricht transportiert Aufrufabsicht und Parameter. Ergebnisnachricht transportiert Ergebnisse des Aufrufs.
Anwendungs- sicht
Realisierung
B Stub
Illusion eines Funktionsaufrufs
Nachrichten im Netzwerk
A Stub
gewöhnlicher Funktionsaufruf
  A
     –
Beispiele: NFS (ONC RPC), Linux D-BUS
 26.05.2021 Betriebssysteme: 07 - Interprozesskommunikation
32
B
 
   Inhalt
Grundlagen der Interprozesskommunikation
Lokale Interprozesskommunikation unter UNIX
Signale
Pipes
Message Queues
■ ■
– – –
■
– –
Rechnerübergreifende Interprozesskommunikation
Sockets
Entfernte Prozeduraufrufe (RPCs)
 ■
Zusammenfassung
 26.05.2021 Betriebssysteme: 07 - Interprozesskommunikation 33
 
   Zusammenfassung
Es gibt zwei Arten der Interprozesskommunikation
nachrichtenbasiert
■
–
–
●
die Daten werden kopiert
■
– –
geht auch über Rechnergrenzen über gemeinsamen Speicher
●
●
war heute nicht dran
UNIX-Systeme bieten verschiedene Abstraktionen
Signale, Pipes, Sockets, Message Queues Insbesondere die Sockets werden häufig verwendet.
●
●
Ihre Schnittstelle wurde standardisiert.
Praktisch alle Vielzweckbetriebssysteme implementieren heute Sockets.
 26.05.2021
Betriebssysteme: 07 - Interprozesskommunikation 34
 
   Betriebssysteme (BS)
08. Speicherverwaltung
https://sys.cs.tu-dortmund.de/DE/Teaching/SS2021/BS/
09.06.2021
Peter Ulbrich
peter.ulbrich@tu-dortmund.de
Basierend auf Betriebssysteme von Olaf Spinczyk, Universität Osnabrück
    
   Wiederholung: Betriebsmittel
Das Betriebssystem hat folgende Aufgaben:
Verwaltung der Betriebsmittel des Rechners
Schaffung von Abstraktionen, die Anwendungen einen einfachen und effizienten Umgang mit Betriebsmitteln erlauben
■
– –
■
–
 ■
–
Bisher: Prozesse
Konzept zur Abstraktion von der realen CPU
Nun: Speicher
Verwaltung von Haupt- und Hintergrundspeicher
     Hauptspeicher
(Memory)
 E/A-Schnittstellen
(Interfaces)
E/A-Geräte
(I/O Devices)
Hintergrundspeicher
(Secondary Storage)
 09.06.2021
2
Prozessor
(CPU, Central Processing Unit)
 
   Wiederholung: Mehrprogrammbetrieb
CPU-Auslastung unter Annahme einer bestimmten E/A-Wartewahrscheinlichkeit:
Quelle: Tanenbaum, Moderne Betriebssysteme
➔ Mehrprogrammbetrieb ist essentiell für eine hohe Auslastung
Beim Starten und Beenden der Prozesse muss dynamisch Speicher zugewiesen bzw. zurückgenommen werden!
■
  ■
 09.06.2021 3
A=1-pn A=1-pn
 
   Inhalt
Grundlegende Aufgaben der Speicherverwaltung
Anforderungen Strategien
 ■
– –
 ■
–
■
– –
■ ■ ■
Segmentbasierte Adressabbildung Seitenbasierte Adressabbildung Zusammenfassung
Speichervergabe
Platzierungsstrategien
Speicherverwaltung bei Mehrprogrammbetrieb
Ein-/Auslagerung Relokation
Tanenbaum
3: Speicherverwaltung
Silberschatz
8: Memory-Management Strategies
 09.06.2021 4
 
   Anforderungen
Mehrere Prozesse benötigen Hauptspeicher
Prozesse liegen an verschiedenen Stellen im Hauptspeicher.
Schutzbedürfnis des Betriebssystems und der Prozesse untereinander
Speicher reicht eventuell nicht für alle Prozesse.
➔ Freie Speicherbereiche kennen, verwalten und vergeben
➔ Ein- und Auslagern von Prozessen
➔ Relokation von Programmbefehlen
➔ Hardwareunterstützung ausnutzen
■
–
–
–
  Betriebssystem
 Prozess 1
 Prozess 2
 Das Betriebssystem
Das Betriebssystem
und zwei Anwendungs-
und zwei Anwendungs-
prozesse im Haupt-
prozesse im Haupt-
speicher
speicher
 09.06.2021 5
 
   Grundlegende Politiken/Strategien
... auf jeder Ebene der Speicherhierarchie:
Platzierungsstrategie (placement policy)
Woher soll benötigter Speicher genommen werden?
 ■
–
■
–
■
–
●
●
wo der Verschnitt am kleinsten/größten ist egal, weil Verschnitt zweitrangig ist
Ladestrategie (fetch policy)
Wann sind Speicherinhalte einzulagern?
●
auf Anforderung oder im Voraus
Ersetzungsstrategie (replacement policy)
Welche Speicherinhalte sind ggf. zu verdrängen, falls der Speicher knapp wird?
●
●
das älteste, am seltensten genutzte das am längsten ungenutzte
 09.06.2021
6
 
   Inhalt
Grundlegende Aufgaben der Speicherverwaltung
Anforderungen Strategien
■
– –
 ■
–
■
– –
■ ■ ■
Segmentbasierte Adressabbildung Seitenbasierte Adressabbildung Zusammenfassung
Speichervergabe
Platzierungsstrategien
Speicherverwaltung bei Mehrprogrammbetrieb
Ein-/Auslagerung Relokation
 09.06.2021 7
 
   Speichervergabe: Problemstellung
Verfügbarer (physischer) Speicher
■
0xFFFFFFFF
 ROM
 RAM
   RAM
   0
Speicherlandkarte (Memory Map) eines fiktiven 32-Bit-Systems
Hauptspeicherbereich 2 E/A-Geräte
Hauptspeicherbereich 1
Verfügbarer physischer Adressraum
(hier mit 32 Bit
breiten Adressen)
  09.06.2021
8
 
   Speichervergabe: Problemstellung
Belegung des verfügbaren Hauptspeichers durch ...
Benutzerprogramme
Programmbefehle (Text)
Programmdaten (Data)
Dynamische Speicheranforderungen (Stack, Heap)
■
– – –
Betriebssystem
Betriebssystemcode und -daten Prozesskontrollblöcke Datenpuffer für Ein-/Ausgabe ...
➔ Zuteilung des Speichers nötig
09.06.2021 9
■
– – – –
  
   Statische Speicherzuteilung
Feste Bereiche für Betriebssystem und Benutzerprogramme
Probleme:
Grad des Mehrprogrammbetriebs begrenzt
Begrenzung anderer Ressourcen (z.B. Bandbreite bei Ein-/Ausgabe wegen zu kleiner Puffer)
Ungenutzter Speicher des Betriebssystems kann von Anwendungsprogrammen
nicht genutzt werden und umgekehrt.
➔ Dynamische Speicherzuteilung einsetzen
■ ■
– –
–
 09.06.2021 10
 
   Dynamische Speicherzuteilung
Segmente
zusammenhängender Speicherbereich (Bereich mit aufeinanderfolgenden Adressen)
Allokation (Belegung) und Freigabe von Segmenten
Ein Anwendungsprogramm besitzt üblicherweise folgende Segmente:
Textsegment
Datensegment
Stapelsegment (lokale Variablen, Parameter, Rücksprungadressen, ...)
■
–
■ ■
– – –
Suche nach geeigneten Speicherbereichen zur Zuteilung
insbesondere beim Programmstart
➔ Platzierungsstrategien nötig
Besonders wichtig dabei: Freispeicherverwaltung
09.06.2021 11
■
–
–
  
   Freispeicherverwaltung
Freie (evtl. auch belegte) Segmente des Speichers müssen repräsentiert werden
Bitlisten
0 8 16
■
■
 A
 B
 C
 D
   Speicher
               11111000
 11111111
 11001111
 ...
Bitliste markiert belegte Speicherbereiche
Speichereinheiten gleicher Größe (z.B. 1 Byte, 64 Byte, 1024 Byte)
 ●
Bitliste kostet u. U. viel Speicher.
●
●
Bei der Freigabe muss man die Größe
●
Bei der Freigabe muss man die Größe
des freizugebenden Speichers kennen
des freizugebenden Speichers kennen
bzw. mit angeben.
bzw. mit angeben.
 09.06.2021 12
Probleme:
Probleme:
Bitliste kostet u. U. viel Speicher.
 
   Freispeicherverwaltung (2)
Verkettete Liste
0 8 16
■
 A
 B
 C
 D
   Speicher
         b
 0
 5
   f
 5
 3
    b
 8
 6
     b
 14
 4
    f
 18
 2
    b
 20
 4
     belegt/frei Länge Anfang
Repräsentation von belegten und freien Segmenten
 Problem: Für die Liste wird Problem: Für die Liste wird
(dynamisch) Speicher benötigt.
(dynamisch) Speicher benötigt.
 09.06.2021 13
 
   Freispeicherverwaltung (3)
Verkettete Liste im freien Speicher
0 8 16
Länge
Mindestlückengröße muss garantiert werden
■
          A
5
B
6
C
4
D
4
Speicher
  3
2
       ■ ■
zur Effizienzsteigerung eventuell Rückwärtsverkettung nötig Repräsentation letztlich auch von der Vergabestrategie abhängig
 09.06.2021 14
 
   Speicherfreigabe
Verschmelzung von Lücken
0 8 16
■
        A
5
B
6
C
4
D
4
  3
2
Speicher
      Nach Freigabe von B:
0 8 16
       A 5
C 4
D 4
  9
2
Speicher
       09.06.2021
15
 
   Platzierungsstrategien
... auf der Basis von unterschiedlich sortierten Löcherlisten:
First Fit (Sortierung nach Speicheradresse)
erste passende Lücke wird verwendet
■
–
■
– –
■
–
■
–
■
–
Rotating First Fit / Next Fit (Sortierung nach Speicheradresse)
wie First Fit, aber Start bei der zuletzt zugewiesenen Lücke vermeidet viele kleine Lücken am Anfang der Liste (wie bei First Fit)
Best Fit (Sortierung nach Lückengröße – kleinste zuerst)
kleinste passende Lücke wird gesucht
Worst Fit (Sortierung nach Lückengröße – größte zuerst)
größte passende Lücke wird gesucht
Probleme:
zu kleine Lücken, Speicherverschnitt
 09.06.2021 16
 
  Platzierungsstrategien (2)
Das Buddy-Verfahren
Einteilung in dynamische Bereiche der Größe 2n
■ ■
0 128
256 384
512 640 768
896 1024
         1024
 A
 128
 256
 512
 A
 B
 64
 256
 512
 A
 B
 64
 C
 128
 512
 128
 B
 64
 C
 128
 512
 128
 B
 D
 C
 128
 512
 128
 64
 D
 C
 128
 512
 256
 C
 128
 512
 1024
   Anfrage 70
Anfrage 35
Anfrage 80
  Freigabe A
Anfrage 60
Freigabe B
Freigabe D Freigabe C
  17
 09.06.2021
Effiziente Repräsentation der Lücken und effiziente Algorithmen
  
   Diskussion: Verschnitt
Externer Verschnitt
Außerhalb der zugeteilten Speicherbereiche entstehen Speicherfragmente, die nicht mehr genutzt werden können.
Passiert bei den listenbasierten Strategien wie First Fit, Best Fit, ... Interner Verschnitt
Innerhalb der zugeteilten Speicherbereiche gibt es ungenutzten Speicher.
Passiert z.B. bei Buddy, da die Anforderungen auf die nächstgrößere Zweierpotenz aufgerundet werden.
■
–
–
■
–
–
 09.06.2021 18
 
   Zwischenfazit: Einsatz der Verfahren
Einsatz im Betriebssystem r
Verwaltung des Systemspeichers
Zuteilung von Speicher an Prozesse und Betriebssystem
 ■
– –
■
– –
■
–
Einsatz innerhalb eines Prozesses
Verwaltung des Haldenspeichers (Heap)
erlaubt dynamische Allokation von Speicherbereichen durch den
Prozess (malloc und free)
Einsatz für Bereiche des Sekundärspeichers
Verwaltung bestimmter Abschnitte des Sekundärspeichers, z.B. Speicherbereich für Prozessauslagerungen (swap space)
 09.06.2021 19
z.B. Buddy-Allokator z.B. Buddy-Allokato
in Linux
in Linux
 typisch:
typisch:
listenbasiert
listenbasiert
 oft: Bitmaps
oft: Bitmaps
 
   Inhalt
Grundlegende Aufgaben der Speicherverwaltung
Anforderungen Strategien
■
– –
■
–
Speichervergabe
Platzierungsstrategien
 ■
– –
■ ■ ■
Segmentbasierte Adressabbildung Seitenbasierte Adressabbildung Zusammenfassung
Speicherverwaltung bei Mehrprogrammbetrieb
Ein-/Auslagerung Relokation
 09.06.2021 20
 
   Ein-/Auslagerung (swapping)
Segmente eines Prozesses werden auf Hintergrundspeicher ausgelagert und im Hauptspeicher freigegeben
z.B. zur Überbrückung von Wartezeiten bei E/A
■
–
■
Einlagern der Segmente in den Hauptspeicher am Ende der Wartezeit
Betriebssystem
  Prozess 1
Prozess 2
     Hauptspeicher
Ein-/Auslagerzeit ist hoch
Prozess 1 Prozess 2
Hintergrundspeicher
 ■
– –
Latenz der Festplatte (z.B. Positionierung des Schreib-/Lesekopfes) Übertragungszeit
 09.06.2021 21
 
   Ein-/Auslagerung (2)
Adressen im Prozess sind normalerweise statisch gebunden
kann nur an dieselbe Stelle im Hauptspeicher wieder eingelagert werden Kollisionen mit eventuell neu im Hauptspeicher befindlichen Segmenten
■
– –
Mögliche Lösung:
Partitionierung des Hauptspeichers
In jeder Partition läuft nur ein Prozess,
Einlagerung erfolgt wieder in dieselbe Partition.
Großer Nachteil: Speicher kann nicht optimal genutzt werden.
 Betriebssystem
 Partition 1
 Partition 2
 Partition 3
 Partition 4
 ■
–
–
–
Besser: Dynamische Belegung und Programmrelokation
09.06.2021 22
■
  
   Adressbindung und Relokation
Problem: Maschinenbefehle benutzen Adressen
z.B. ein Sprungbefehl in ein Unterprogramm oder ein Ladebefehl für eine Variable aus dem Datensegment
Es gibt verschiedene Möglichkeiten, die Adressbindung zwischen dem Befehl und seinem Operanden herzustellen ...
■
–
–
■
– –
■
– ➔
■
– – ➔
Absolutes Binden (Compile/Link Time)
Adressen stehen fest
Programm kann nur an bestimmter Speicherstelle korrekt ablaufen
Statisches Binden (Load Time)
Beim Laden des Programms werden die absoluten Adressen angepasst (reloziert) Compiler/Assembler muss Relokationsinformation liefern
Dynamisches Binden (Execution Time)
Der Code greift grundsätzlich nur indirekt auf Operanden zu. Das Programm kann jederzeit im Speicher verschoben werden. Programme werden etwas größer und langsamer
 09.06.2021 23
 
   Adressbindung und Relokation (2)
Übersetzungsvorgang
(Erzeugung der Relokationsinformationen)
test.c test.s
■
test.o
 Assembler
 main:
 pushl %ebp
 movl %esp,%ebp
 pushl $0
 call exit
 addl $4,%esp
 popl %ebp
 ret
 Bindemodul
 0000 55
0001 89E5
0003 6A00
0005 E800000000 000a 83C404 000d 89EC
000f 5D
0010 C3
main: 0
0006: exit ADDR32
 C-Programm
 int main () {
  exit(0);
}
Erzeugung beim Übersetzungsvorgang
Relokationsinformation: „ersetze Adresse von exit” 09.06.2021 24
  
   Adressbindung und Relokation (3)
Binde- und Ladevorgang
■
test.o
test
Prozess
  Bindemodul
 0000 55
0001 89E5
0003 6A00
0005 E800000000 000a 83C404 000d 89EC
000f 5D
0010 C3
main: 0
0006: exit ADDR32
 8
  ersetze Adresse von exit
ersetze Adresse relativ zum Befehlssegment
Adresse ist nun absolut Befehlssegment: 2100
Lademodul
    ...
0030 55
0031 89E5
0033 6A00
0035 E848010000 003a 83C404 003d 89EC
003f 5D
0040 C3
...
0036: ADDR32 TXT
=0x0148
=0x0148
...
2130 55
2131 89E5
2133 6A00
2135 E848220000 213a 83C404 213d 89EC
213f 5D
2140 C3
...
=0x2248
=0x224
 09.06.2021
25
Speicherabbild
 
   Adressbindung und Relokation (4)
Relokationsinformation im Bindemodul
erlaubt das Binden von Modulen in beliebige Programme
■
–
■
– –
■
–
■
–
Relokationsinformation im Lademodul
erlaubt das Laden des Programms an beliebige Speicherstellen absolute Adressen werden erst beim Laden generiert
Dynamisches Binden mit Compiler-Unterstützung
Programm benutzt keine absoluten Adressen und kann daher immer an beliebige Speicherstellen geladen werden
●
„Position Independent Code“
Dynamisches Binden mit MMU-Unterstützung:
Abbildungsschritt von „logischen“ auf „physische“ Adressen
●
Relokation beim Binden reicht (außer für „Shared Libraries“)
 09.06.2021
26
 
   Inhalt
Grundlegende Aufgaben der Speicherverwaltung
Anforderungen Strategien
■
– –
■
–
■
– –
■ ■ ■
Speichervergabe
Platzierungsstrategien
Speicherverwaltung bei Mehrprogrammbetrieb
Ein-/Auslagerung Relokation
Segmentbasierte Adressabbildung
Seitenbasierte Adressabbildung Zusammenfassung
  09.06.2021 27
 
   Segmentierung
Hardwareunterstützung:
Abbildung logischer auf physische Adressen
■
logischer Adressraum
physischer Adressraum
   ROM
  RAM
  0xfffff 0
+
0x100000
+
0x450000
0x54ffff
0x450000
0x1fffff
0x100000
   Das Segment des logischen Adressraums kann an jeder beliebigen Stelle
Das Segment des logischen Adressraums kann an jeder beliebigen Stelle
im physischen Adressraum liegen. Das Betriebssystem bestimmt, wo ein Segment
im physischen Adressraum liegen. Das Betriebssystem bestimmt, wo ein Segment
im physischen Adressraum tatsächlich liegen soll.
im physischen Adressraum tatsächlich liegen soll.
 09.06.2021
28
 
   Segmentierung (2)
Realisierung mit Übersetzungstabelle (pro Prozess) Segmenttabellen-
■
basisregister
Segmenttabelle
+
02 00 4a02
logische Adresse
        Startadr.
Länge
   00 01 02
      ffe0 f000
 ...
00 4fff
ja
Trap: Schutzverletzung
+
ffe1 3a02
physische Adresse
<
      09.06.2021
29
 
   Segmentierung (3)
Hardwareunterstützung: MMU (Memory Management Unit)
Schutz vor Segmentübertretung
MMU prüft Rechte zum Lesen, Schreiben und Ausführen von Befehlen Trap zeigt Speicherverletzung an
Programme und Betriebssystem voreinander geschützt
■ ■
– – –
■
–
■
–
■
– –
Prozessumschaltung durch Austausch der Segmentbasis
jeder Prozess hat eigene Übersetzungstabelle
Ein- und Auslagerung vereinfacht
nach Einlagerung an beliebige Stelle muss lediglich die Übersetzungstabelle angepasst werden
Gemeinsame Segmente möglich
Befehlssegmente Datensegmente (Shared Memory)
 09.06.2021 30
 
   Segmentierung (4)
Probleme ...
Fragmentierung des Speichers durch häufiges Ein- und Auslagern
Es entstehen kleine, nicht nutzbare Lücken: externer Verschnitt
■
–
 ■
– – –
■
–
Kompaktifizieren hilft
Segmente werden verschoben, um Lücken zu schließen Segmenttabelle wird jeweils angepasst
kostet aber Zeit
Lange E/A-Zeiten für Ein- und Auslagerung
Nicht alle Teile eines Segments werden gleich häufig genutzt.
 09.06.2021 31
 
   Kompaktifizieren
Verschieben von Segmenten
Erzeugen von weniger – aber größeren – Lücken
Verringern des Verschnitts aufwendigeOperation,abhängigvonderGrößederverschobenen Segmente
Ausgangslage 700 K verschoben 300 K verschoben 000
■
– – –
 P1
 300K
 P2
 400K
 P3
 300K
  P1
 P2
 P3
 1000K
 P1
 1000K
 P3
 P2
400K 400K 700K 700K
400K
1400K
1800K 2100K
1000K 1400K
1100K
 1800K
2100K 2100K
 09.06.2021
32
 
   Inhalt
Grundlegende Aufgaben der Speicherverwaltung
Anforderungen Strategien
■
– –
■
–
■
– –
■ ■ ■
Speichervergabe
Platzierungsstrategien
Speicherverwaltung bei Mehrprogrammbetrieb
Ein-/Auslagerung Relokation
Segmentbasierte Adressabbildung
Seitenbasierte Adressabbildung
Zusammenfassung
  09.06.2021 33
 
   Seitenadressierung (paging)
Einteilung des logischen Adressraums in gleichgroße Seiten, die an beliebigen Stellen im physischen Adressraum liegen können
Lösung des Fragmentierungsproblems
keine Kompaktifizierung mehr nötig
vereinfacht Speicherbelegung und Ein-/Auslagerungen
■
– – –
logischer Adressraum
physischer Adressraum
  ROM
      RAM
  Seiten
Kacheln
(frames)
34
  (pages) 09.06.2021
      
   MMU mit Seitentabelle
Tabelle setzt Seiten in Seitenrahmen (Kacheln) um ST-Basisregister
+ Seitentabelle
Startadr. 00000
00001 00002
00003 00004
■
   logische Adresse
 00002
 12a
        ffe0 fxxx
   ...
   ffe0f
 12a
 physische Adresse
 09.06.2021
35
 
   MMU mit Seitentabelle (2)
Seitenadressierung erzeugt internen Verschnitt
letzte Seite eventuell nicht vollständig genutzt
■
–
 ■
–
–
Seitengröße
kleine Seiten verringern internen Verschnitt, vergrößern aber die Seitentabelle (und umgekehrt)
übliche Größe: 4096 Bytes (4 KiB)
große Tabelle, die im Speicher gehalten werden muss
viele implizite Speicherzugriffe nötig
nur ein „Segment“ pro Kontext
sinngemäße Nutzung des Speichers schwerer zu kontrollieren (push/pop nur auf „Stack“, Ausführung nur von „Text“, ...)
➔ Kombination mit Segmentierung
09.06.2021 36
■
■
■
–
  
   Segmentierung und Seitenadressierung
Segmenttabellen- basisregister
+
logische Adresse
1
   0002
12a
       Segmenttabelle
ST-Zeiger Seitenzahl 00
Seitentabelle
Startadr. 00000
00001 00002
00003 00004
        ffe0 fxxx
   ...
   01
02     +
<
ja
Trap: Schutzverletzung
0005
     ...
  physische Adresse
 ffe0f
 12a
  09.06.2021
37
 
   Segmentierung u. Seitenadressierung (2)
Noch mehr implizite Speicherzugriffe
Große Tabellen im Speicher
Vermischung der Konzepte
Noch immer Ein-/Auslagerung kompletter Segmente
➔ Mehrstufige Seitenadressierung mit Ein- und Auslagerung
■ ■ ■ ■
 09.06.2021 38
 
   Ein-/Auslagerung von Seiten
Es ist nicht nötig, ein gesamtes Segment aus- bzw. einzulagern
Seiten können einzeln ein- und ausgelagert werden
■
–
■
–
–
–
Seitentabelle
Hardware-Unterstützung
Ist das Präsenzbit gesetzt, bleibt alles wie bisher.
Ist das Präsenzbit gelöscht,
wird ein Trap ausgelöst (page fault).
Die Trap-Behandlung kann nun für das Laden der Seite vom Hintergrundspeicher sorgen
und den Speicherzugriff danach wiederholen (benötigt HW-Support in der CPU).
Startadr.
Präsenzbit
     ffe0 fxxx
 X
 ...
  0000
0001
0002
  09.06.2021
39
 
   Mehrstufige Seitenadressierung
Beispiel: zweifach indirekte Seitenadressierung
logische Adresse
Basis- register
■
 3
 02
 03
 12a
         ...
         ...
    3
     ...
        ...
        02
      ...
  03
            ...
    ■
– –
■
Aber: Noch mehr implizite Speicherzugriffe
Präsenzbit auch für jeden Eintrag in den höheren Stufen
Tabellen werden aus- und einlagerbar
Tabellen können bei Zugriff (=Bedarf) erzeugt werden (spart Speicher!)
 09.06.2021
40
...
 
   Translation Look-Aside Buffer (TLB)
Schneller Registersatz wird konsultiert, bevor auf die Seitentabelle zugegriffen wird:
■
ST Basisregister
+
logische Adresse
    00002
 12a
      00000
00001
00002
00003 00004
Seitentabelle
Startadr.
Translation Look Aside Buffer (TLB)
     00004
a0123
   00028
bfff4
 ffe0 fxxx
   00002
ffe0f
      00032
12345
 ...
 ffe0f
 12a
 physische Adresse
 09.06.2021
41
 
   Translation Look-Aside Buffer (2)
Schneller Zugriff auf Seitenabbildung, falls Information im voll- assoziativen Speicher des TLB
keine impliziten Speicherzugriffe nötig
■
–
■
–
■
–
■
– – –
Bei Kontextwechseln muss TLB gelöscht werden (flush)
Process-Context ID (PCID): flush bei Intel-CPUs seit ~2010 (und AMD-CPUs ab Zen 3 / seit 2020) nicht mehr notwendig
Bei Zugriffen auf eine nicht im TLB enthaltene Seite wird die entsprechende Zugriffsinformation in den TLB eingetragen.
Ein alter Eintrag muss zur Ersetzung ausgesucht werden.
TLB-Größe:
Intel Core i7: 512 Einträge, Seitengröße 4K
UltraSPARC T2: Daten-TLB = 128, Code-TLB = 64, Seitengröße 8K Größere TLBs bei den üblichen Taktraten zur Zeit nicht möglich.
 09.06.2021 42
 
   Invertierte Seitentabelle
Bei großen logischen Adressräumen (z.B. 64 Bit):
klassische Seitentabellen sehr groß (oder ...) sehr viele Abbildungsstufen
Tabellen sehr dünn besetzt
■
– – –
■
Invertierte Seitentabelle (Inverted Page Table) PID logische Adresse
    05
... Suche
Kachel- Seitentabelle
physische Adresse
        ffe0f
 12a
    09.06.2021
43
00002
12a
 05
00002
   
   Invertierte Seitentabelle (2)
Vorteile
wenig Platz zur Speicherung der Abbildung notwendig Tabelle kann immer im Hauptspeicher gehalten werden
■
– –
■
–
–
–
■
– –
Nachteile
Sharing von Seitenrahmen schwer zu realisieren
prozesslokale Datenstrukturen zusätzlich nötig für Seiten, die ausgelagert sind
Suche in der Seitentabelle ist aufwendig
●
Einsatz von Assoziativspeichern und Hashfunktionen
Trotz der Nachteile setzen heute viele Prozessorhersteller bei 64- Bit-Architekturen auf diese Form der Adressumsetzung
PowerPC, UltraSparc, IA-64, (Alpha), ... Nicht: x86-64/amd64, Arm (AArch64)
 09.06.2021 44
 
   Inhalt
Grundlegende Aufgaben der Speicherverwaltung
Anforderungen Strategien
■
– –
■
–
■
– –
■ ■ ■
Segmentbasierte Adressabbildung Seitenbasierte Adressabbildung Zusammenfassung
Speichervergabe
Platzierungsstrategien
Speicherverwaltung bei Mehrprogrammbetrieb
Ein-/Auslagerung Relokation
  09.06.2021 45
 
   Zusammenfassung
Bei der Speicherverwaltung arbeitet das Betriebssystem sehr eng mit der Hardware zusammen.
Segmentierung und/oder Seitenadressierung
Durch die implizite Indirektion beim Speicherzugriff können Programme und Daten unter der Kontrolle des Betriebssystems im laufenden Betrieb beliebig verschoben werden.
■
– –
■
–
–
●
Unterscheiden sich bzgl. Verschnitt sowie Belegungs- und Freigabeaufwand.
Zusätzlich sind diverse strategische Entscheidungen zu treffen.
Platzierungsstrategie (First Fit, Best Fit, Buddy, ...)
Strategieauswahl hängt vom erwarteten Anwendungsprofil ab. Bei Ein-/Auslagerung von Segmenten oder Seiten:
●
 ●
●
Ladestrategie Ersetzungsstrategie
   09.06.2021
46
nächstes Mal mehr dazu
nächstes Mal mehr dazu
 
   Betriebssysteme (BS)
09. Virtueller Speicher
https://sys.cs.tu-dortmund.de/DE/Teaching/SS2021/BS/
16.06.2021
Peter Ulbrich
peter.ulbrich@tu-dortmund.de
Basierend auf Betriebssysteme von Olaf Spinczyk, Universität Osnabrück
    
   Wiederholung
Bei der Speicherverwaltung arbeitet das Betriebssystem sehr eng mit der Hardware zusammen.
Segmentierung und/oder Seitenadressierung
Durch die implizite Indirektion beim Speicherzugriff können Programme und Daten unter der Kontrolle des Betriebssystems im laufenden Betrieb beliebig verschoben werden.
■
– –
■
–
–
●
Unterscheiden sich bzgl. Verschnitt sowie Belegungs- und Freigabeaufwand.
Zusätzlich sind diverse strategische Entscheidungen zu treffen.
Platzierungsstrategie (First Fit, Best Fit, Buddy, ...)
Strategieauswahl hängt vom erwarteten Anwendungsprofil ab. Bei Ein-/Auslagerung von Segmenten oder Seiten:
●
 ●
●
●
Logische bzw. virtuelle Seiten und physische Seitenrahmen (Kacheln) Ladestrategie
Ersetzungsstrategie
   16.06.2021
Betriebssysteme: 09 - Virtueller Speicher 2
heute mehr dazu
heute mehr dazu
 
   Inhalt
Motivation
Demand Paging Seitenersetzung Seitenzuordnung Ladestrategie Zusammenfassung
 ■ ■ ■ ■ ■ ■
 16.06.2021
Betriebssysteme: 09 - Virtueller Speicher 3
 
   Lokalität der Speicherzugriffe
 ■
■
–
■
Die Lokalität kann ausgenutzt werden, wenn der Speicher nicht reicht.
z.B. „Overlay-Technik“
Einzelne Instruktionen benötigen nur wenige Speicherseiten.
Auch über längere Zeiträume zeigt sich starke Lokalität.
Instruktionen werden z.B. eine nach der anderen ausgeführt.
–
Quelle: Silberschatz, „Operating System Concepts“
 16.06.2021 Betriebssysteme: 09 - Virtueller Speicher 4
 
   Die Idee des „Virtuellen Speichers“
Entkoppelung des Speicherbedarfs vom verfügbaren Hauptspeicher
Prozesse benötigen nicht alle Speicherstellen gleich häufig:
■
–
–
●
bestimmte Befehle werden selten oder gar nicht benutzt (z.B. Fehlerbehandlungen)
■
–
–
–
–
bestimmte Datenstrukturen werden nicht voll belegt
Prozesse benötigen evtl. mehr Speicher als Hauptspeicher vorhanden
●
Idee:
Vortäuschen eines größeren Arbeitsspeichers
Einblenden aktuell benötigter Speicherbereiche
Auslagern nicht benötigter Bereiche
Abfangen von Zugriffen auf nicht eingeblendete Bereiche, einlagern der benötigen Bereiche auf Anforderung
 16.06.2021 Betriebssysteme: 09 - Virtueller Speicher 5
 
   Inhalt
Motivation
Demand Paging
Seitenersetzung Seitenzuordnung Ladestrategie Zusammenfassung
■ ■ ■ ■ ■ ■
   16.06.2021
Betriebssysteme: 09 - Virtueller Speicher 6
Tanenbaum
3: Speicherverwaltung
Silberschatz
9: Virtual Memory
 
   Demand Paging (Seitenumlagerung)
Bereitstellung von Seiten auf Anforderung
■
0 1 2 3
4 5 6 7
8
9
10
0 1
Hintergrundspeicher
        A
2
1
  C
 A
  G
   E
      B
14
    C
1
0
  1
    2 0:C
    D
5
0
3 4
5 6 7
4:
8: 12: 16:
DA GF
B
       0
   0
       0
       0
     E
7
1
       F
11
11
12 1       Präsenzbit
7
0
   0
  0
  G
4
16.06.2021 Betriebssysteme: 09 - Virtueller Speicher
E
   Virtueller Adressraum
Seitentabelle
Seitenrahmen im Hauptspeicher

   Demand Paging (Seitenfehler)
Reaktion auf Seitenfehler (page fault)
■
0 1 2 3
40 50 6
7
0
1     Hintergrundspeicher
2   0:C
      A
C
A
  G
   E
     B
14 0 lade v
      C
11
     in F 50
   D
3 4
5 6 7
Trap!
DA GF
      4:
8:
12:
E
B
  ST
       0
       0
     8
9 10 11
16:
E
7
1
        F
11
0
    0
 Betriebs- system
     12 1
8
G
4
0
  16.06.2021 Betriebssysteme: 09 - Virtueller Speicher Präsenzbit
 Virtueller Adressraum
Seitenrahmen im Hauptspeicher

   Demand Paging (Seitenfehler)
Reaktion auf Seitenfehler (page fault)
■
      0 1 2 3
40 50 6
7
Einlagern der Seite
0
1     Hintergrundspeicher
2   0:C
 F
C
A
  G
   E
        C
       8
9 10 11
E
A
B
D
14 0 lade v
   11
in F 50
 3 4
5 6 7
Trap!
DA 8:
      4:
  ST
    G
F
         12: 16:
B
   E
      F
11
0
  0
  7
1
  0
    0
 Betriebs- system
     12 1
Ermitteln der ausgelagerten Seite
G
4
0
  16.06.2021 Betriebssysteme: 09 - Virtueller Speicher 9 Präsenzbit
 Virtueller Adressraum
Seitenrahmen im Hauptspeicher

   Demand Paging (Seitenfehler)
Reaktion auf Seitenfehler (page fault)
■
0 1 2 3
40 50 6
7
8
9 10 11
12 1
0
1     Hintergrundspeicher
2   0:C
      A
 F
C
A
  G
   E
      B
14 0 lade v
     C
11
    in F 50
   D
3 4
5 6 7
4:
8: 12: 16:
DA GF
B
        ST
       0
          E
7
0
  1
    E
    F
0
1
   0
 Betriebs- system
   0
   G
4
 16.06.2021 Betriebssysteme: 09 - Virtueller Speicher Präsenzbit
10
 Virtueller Adressraum
Anpassen der ST
Seitenrahmen

   Demand Paging (Seitenfehler)
Reaktion auf Seitenfehler (page fault)
■
      A
Wiederholen
des Zugriffs 0
0
1 140
lade v 211
in F 350
40 50 6
7
1
Hintergrundspeicher
  F
 C
A
  G
   E
     B
     C
    2   0:C
      D
3 4
5 6 7
4:
8: 12: 16:
DA GF
B
        ST
       0
       0
     8
9 10 11
12 1
E
E
7
1
        F
0
1
   0
    G
4
Betriebs- system
  0
  16.06.2021 Betriebssysteme: 09 - Virtueller Speicher Präsenzbit
11
 Virtueller Adressraum
Seitenrahmen im Hauptspeicher

   Diskussion: Kosten der Seitenumlagerung
Performanz von Demand Paging
ohne Seitenfehler:
■
–
–
●
Effektive Zugriffszeit zwischen 10 und 200 Nanosekunden
■
–
mit Seitenfehler:
●
●
●
●
p sei Wahrscheinlichkeit für Seitenfehler
Annahme:
Zeit zum Einlagern einer Seite vom Hintergrundspeicher entspricht 25 Millisekunden (8 ms Latenz, 15 ms Positionierzeit, 1 ms Übertragungszeit)
Annahme: normale Zugriffszeit 100 ns
Effektive Zugriffszeit: (1–p)·100+p·25000000=100+24999900·p
Seitenfehlerrate muss extrem niedrig sein
p nahe Null
 16.06.2021 Betriebssysteme: 09 - Virtueller Speicher 12
 
   Diskussion: Weitere Eigenschaften
Prozesserzeugung
Copy-on-Write
■
–
–
●
auch bei Paging MMU leicht zu realisieren
■
–
feinere Granularität als bei Segmentierung Programmausführung und Laden erfolgen verschränkt:
●
●
Benötigte Seiten werden erst nach und nach geladen.
Sperren von Seiten
notwendig bei Ein-/Ausgabeoperationen
 16.06.2021 Betriebssysteme: 09 - Virtueller Speicher 13
 
   Diskussion: Segmentumlagerung Prinzipiell möglich, hat aber Nachteile ...
Grobe Granularität
z.B. Code-, Daten-, Stack-Segment
■
–
■
–
■
–
➔
In der Praxis hat sich Demand Paging durchgesetzt
Schwierigere Hauptspeicherverwaltung
Alle freien Seitenrahmen sind gleich gut für ausgelagerte Seiten.
Bei der Einlagerung von Segmenten ist die Speichersuche schwieriger.
Schwierigere Hintergrundspeicherverwaltung
Hintergrundspeicher ist wie Seitenrahmen in Blöcke strukturiert (2er-Potenzen)
 16.06.2021 Betriebssysteme: 09 - Virtueller Speicher 14
 
   Inhalt
Motivation Demand Paging Seitenersetzung Seitenzuordnung Ladestrategie Zusammenfassung
■ ■ ■ ■ ■ ■
  16.06.2021
Betriebssysteme: 09 - Virtueller Speicher 15
 
   Seitenersetzung
Was tun, wenn kein freier Seitenrahmen vorhanden?
Eine Seite muss verdrängt werden, um Platz für neue Seite zu schaffen! Auswahl von Seiten, die nicht geändert wurden (dirty bit in der ST) Verdrängung erfordert Auslagerung, falls Seite geändert wurde
■
– – –
■
– – – –
■
–
Vorgang:
Seitenfehler (page fault): Trap in das Betriebssystem Auslagern einer Seite, falls kein freier Seitenrahmen verfügbar Einlagern der benötigten Seite
Wiederholung des Zugriffs
Problem:
Welche Seite soll ausgewählt werden (das „Opfer“)?
 16.06.2021 Betriebssysteme: 09 - Virtueller Speicher 16
 
   Ersetzungsstrategien
Betrachtung von Ersetzungsstrategien und deren
Wirkung auf Referenzfolgen
Referenzfolge:
Speicherzugriffsverhalten eines Prozesses → Folge von Seitennummern
Ermittlung von Referenzfolgen z.B. durch Aufzeichnung der zugegriffenen Adressen
■
■
– –
–
●
Reduktion der aufgezeichneten Sequenz auf Seitennummern
Zusammenfassung von unmittelbar folgenden Zugriffen auf die gleiche Seite Beispiel für eine Referenzfolge: 1, 2, 3, 4, 1, 2, 5, 1, 2, 3, 4, 5
●
 16.06.2021 Betriebssysteme: 09 - Virtueller Speicher 17
 
   First-In, First-Out
Älteste Seite wird ersetzt
Notwendige Zustände:
Alter bzw. Einlagerungszeitpunkt für jeden Seitenrahmen
■ ■
–
■
Ablauf der Ersetzungen (9 Einlagerungen)
    Referenzfolge
1
2
3
4
1
2
5
1
2
3
4
5
Hauptspeicher
Rahmen 1
1
1
1
4
4
4
5
5
5
5
5
5
Rahmen 2
2
2
2
1
1
1
1
1
3
3
3
Rahmen 3
3
3
3
2
2
2
2
2
4
4
Kontrollzustände (Alter pro Rahmen)
Rahmen 1
0
1
2
0
1
2
0
1
2
3
4
5
Rahmen 2
>

0

1

2

0

1

2

3

4

0

1

2

Rahmen 3

>

>

0

1

2

0

1

2

3

4

0

1

                          16.06.2021 Betriebssysteme: 09 - Virtueller Speicher 19
   First-In, First-Out

Größerer Hauptspeicher mit 4 Seitenrahmen (10 Einlagerungen!) FIFO-Anomalie (Béládys Anomalie, 1969)

■ ■

   Referenzfolge

1

2

3

4

1

2

5

1

2

3

4

5

Hauptspeicher

Rahmen 1

1

1

1

1

1

1

5

5

5

5

4

4

Rahmen 2

2

2

2

2

2

2

1

1

1

1

5

Rahmen 3

3

3

3

3

3

3

2

2

2

2

Rahmen 4

4

4

4

4

4

4

3

3

3

Kontrollzustände (Alter pro Rahmen)

Rahmen 1

0

1

2

3

4

5

0

1

2

3

0

1

Rahmen 2

>

0

1

2

3

4

5

0

1

2

3

0

Rahmen 3

>

>

0

1

2

3

4

5

0

1

2

3

Rahmen 4

>

>

>

0

1

2

3

4

5

0

1

2

                            16.06.2021 Betriebssysteme: 09 - Virtueller Speicher 20
   Optimale Seitenersetzungsstrategie

Vorwärtsabstand

Ersetze die Seite die am längsten nicht referenziert wird

Strategie OPT (oder MIN) ist optimal (bei fester Seitenrahmenzahl):

Minimale Anzahl von Umlagerungen (hier 7)

Wähle die Seite mit dem größten Vorwärtsabstand

■

–

■ ➔

–

  Referenzfolge

1

2

3

4

1

2

5

1

2

3

4

5

Hauptspeicher

Rahmen 1

1

1

1

1

1

1

1

1

1

3

4

4

Rahmen 2

2

2

2

2

2

2

2

2

2

2

2

Rahmen 3

3

4

4

4

5

5

5

5

5

5

Kontrollzustände (Vorwärtsabstand)

Rahmen 1

4

3

2

1

3

2

1

>

>

>

>

>

Rahmen 2

>

4

3

2

1

3

2

1

>

>

>

>

Rahmen 3

>

>

7

7

6

5

5

4

3

2

1

>

                          16.06.2021 Betriebssysteme: 09 - Virtueller Speicher 21
   Optimale Seitenersetzungsstrategie

Vergrößerung des Hauptspeichers (4 Seitenrahmen)

6 Einlagerungen

keine Anomalie

■ ➔

–

  Referenzfolge

1

2

3

4

1

2

5

1

2

3

4

5

Hauptspeicher

Rahmen 1

1

1

1

1

1

1

1

1

1

1

4

4

Rahmen 2

2

2

2

2

2

2

2

2

2

2

2

Rahmen 3

3

3

3

3

3

3

3

3

3

3

Rahmen 4

4

4

4

5

5

5

5

5

5

Kontrollzustände (Vorwärtsabstand)

Rahmen 1

4

3

2

1

3

2

1

>

>

>

>

>

Rahmen 2

>

4

3

2

1

3

2

1

>

>

>

>

Rahmen 3

>

>

7

6

5

4

3

2

1

>

>

>

Rahmen 4

>

>

>

7

6

5

5

4

3

2

1

>

                            16.06.2021 Betriebssysteme: 09 - Virtueller Speicher 22
   Diskussion: Optimale Seitenersetzungsstrategie

Implementierung von OPT leider praktisch unmöglich

Referenzfolge müsste vorher bekannt sein

OPT ist nur zum Vergleich von Strategien brauchbar

■

– –

➔

–

Suche nach Strategien, die möglichst nahe an OPT kommen

z.B. Least Recently Used (LRU)

 16.06.2021 Betriebssysteme: 09 - Virtueller Speicher 23
   Least Recently Used (LRU)

Rückwärtsabstand

Zeitdauer, seit dem letzten Zugriff auf die Seite

■

–

■

–

LRU-Strategie (10 Einlagerungen)

Wähle den Seitenrahmen mit dem größten Rückwärtsabstand

  Referenzfolge

1

2

3

4

1

2

5

1

2

3

4

5

Hauptspeicher

Rahmen 1

1

1

1

4

4

4

5

5

5

3

3

3

Rahmen 2

2

2

2

1

1

1

1

1

1

4

4

Rahmen 3

3

3

3

2

2

2

2

2

2

5

Kontrollzustände (Rückwärts- abstand)

Rahmen 1

0

1

2

0

1

2

0

1

2

0

1

2

Rahmen 2

>

0

1

2

0

1

2

0

1

2

0

1

Rahmen 3

>

>

0

1

2

0

1

2

0

1

2

0

                          16.06.2021 Betriebssysteme: 09 - Virtueller Speicher 24
   Least Recently Used (LRU)

Vergrößerung des Hauptspeichers (4 Seitenrahmen):

8 Einlagerungen

■

Referenzfolge

1

2

3

4

1

2

5

1

2

3

4

5

Hauptspeicher

Rahmen 1

1

1

1

1

1

1

1

1

1

1

1

5

Rahmen 2

2

2

2

2

2

2

2

2

2

2

2

Rahmen 3

3

3

3

3

5

5

5

5

4

4

Rahmen 4

4

4

4

4

4

4

3

3

3

Kontrollzustände (Rückwärts- abstand)

Rahmen 1

0

1

2

3

0

1

2

0

1

2

3

0

Rahmen 2

>

0

1

2

3

0

1

2

0

1

2

3

Rahmen 3

>

>

0

1

2

3

0

1

2

3

0

1

Rahmen 4

>

>

>

0

1

2

3

4

5

0

1

2

                              16.06.2021 Betriebssysteme: 09 - Virtueller Speicher 25
   Diskussion: Least Recently Used (LRU)

Keine Anomalie

Allgemein gilt: Es gibt eine Klasse von Algorithmen (Stack-Algorithmen), bei denen keine Anomalie auftritt:

■

–

■

– –

●

●

●

Bei Stack-Algorithmen ist bei k Rahmen zu jedem Zeitpunkt eine Teilmenge der Seiten eingelagert, die bei k+1 Rahmen zum gleichen Zeitpunkt eingelagert wären!

LRU: Es sind immer die letzten k benutzten Seiten eingelagert. OPT:EssinddiekbereitsbenutztenSeiteneingelagert,diealsnächstes zugegriffen

werden.

Problem:

Implementierung von LRU nicht ohne Hardwareunterstützung möglich. Es muss jeder Speicherzugriff berücksichtigt werden.

 16.06.2021 Betriebssysteme: 09 - Virtueller Speicher 26
   Least Recently Used – Hardwareunterstützung

Naive Idee: Hardwareunterstützung durch Zähler

CPU besitzt einen Zähler, der bei jedem Speicherzugriff erhöht wird (inkrementiert wird)

bei jedem Zugriff wird der aktuelle Zählerwert in den jeweiligen Seitendeskriptor geschrieben

Auswahl der Seite mit dem kleinsten Zählerstand (Suche!)

■

–

–

–

■

– – –

Aufwändige Implementierung:

viele zusätzliche Speicherzugriffe

hoher Speicherplatzbedarf

Minimum-Suche in der Seitenfehler-Behandlung

 16.06.2021 Betriebssysteme: 09 - Virtueller Speicher 27
   Second Chance (Clock)

So wird’s gemacht: Einsatz von Referenzbits

Referenzbit im Seitendeskriptor wird automatisch durch Hardware gesetzt, wenn die Seite zugegriffen wird

■

–

■

–

–

●

●

●

einfacher zu implementieren weniger zusätzliche Speicherzugriffe

moderne Prozessoren bzw. MMUs unterstützen Referenzbits (z.B. x86: access bit)

Ziel: Annäherung von LRU

bei einer frisch eingelagerten Seite wird das Referenzbit zunächst auf 1 gesetzt

wird eine Opferseite gesucht, so werden die Seitenrahmen reihum inspiziert

●

●

ist das Referenzbit 1, so wird es auf 0 gesetzt (zweite Chance) ist das Referenzbit 0, so wird die Seite ersetzt

 16.06.2021

Betriebssysteme: 09 - Virtueller Speicher 28
   Second Chance (Clock)

Implementierung mit umlaufendem Zeiger (Clock) Referenzbit

■

 A

 1

   I

 1

 B

 0

 H

 0

 C

 10

  G

 1

 D

 10

 E

 0

 F

 1

Seite wird ersetzt

 –

an der Zeigerposition wird Referenzbit getestet

●

●

●

falls Referenzbit 1, wird Bit gelöscht

falls Referenzbit gleich 0, wurde ersetzbare Seite gefunden

Zeiger wird weitergestellt; falls keine Seite gefunden: Wiederholung

falls alle Referenzbits auf 1 stehen, wird Second Chance zu FIFO

16.06.2021 Betriebssysteme: 09 - Virtueller Speicher 29

–
   Second Chance (Clock)

Ablauf bei drei Seitenrahmen (9 Einlagerungen)

■

  Referenzfolge

1

2

3

4

1

2

5

1

2

3

4

5

Hauptspeicher

Rahmen 1

1

1

1

4

4

4

5

5

5

5

5

5

Rahmen 2

2

2

2

1

1

1

1

1

3

3

3

Rahmen 3

3

3

3

2

2

2

2

2

4

4

Kontrollzustände (Referenzbits)

Rahmen 1

1

1

1

1

1

1

1

1

1

0

0

1

Rahmen 2

0

1

1

0

1

1

0

1

1

1

1

1

Rahmen 3

0

0

1

0

0

1

0

0

1

0

1

1

Umlaufzeiger

2

3

1

2

3

1

2

2

2

3

1

1

                           16.06.2021 Betriebssysteme: 09 - Virtueller Speicher 30
   Second Chance (Clock)

Vergrößerung des Hauptspeichers (4 Seitenrahmen):

10 Einlagerungen

■

  Referenzfolge

1

2

3

4

1

2

5

1

2

3

4

5

Hauptspeicher

Rahmen 1

1

1

1

1

1

1

5

5

5

5

4

4

Rahmen 2

2

2

2

2

2

2

1

1

1

1

5

Rahmen 3

3

3

3

3

3

3

2

2

2

2

Rahmen 4

4

4

4

4

4

4

3

3

3

Kontrollzustände (Referenzbits)

Rahmen 1

1

1

1

1

1

1

1

1

1

1

1

1

Rahmen 2

0

1

1

1

1

1

0

1

1

1

0

1

Rahmen 3

0

0

1

1

1

1

0

0

1

1

0

0

Rahmen 4

0

0

0

1

1

1

0

0

0

1

0

0

Umlaufzeiger

2

3

4

1

1

1

2

3

4

1

2

3

                             16.06.2021 Betriebssysteme: 09 - Virtueller Speicher 31
   Second Chance (Clock)

Bei Second Chance kann es auch zur FIFO-Anomalie kommen:

Wenn alle Referenzbits gleich 1, wird nach FIFO entschieden.

■

–

➔

Im Normalfall kommt man aber LRU nahe.

Erweiterung:

Modifikationsbit kann zusätzlich berücksichtigt werden (Dirty Bit) Drei Klassen: (0,0), (1,0) und (1,1) mit (Referenzbit, Modifikationsbit) Suche nach der niedrigsten Klasse (Einsatz im MacOS)

■

– – –

 16.06.2021 Betriebssysteme: 09 - Virtueller Speicher 32
   Diskussion: Freiseitenpuffer

Freiseitenpuffer beschleunigt die Seitenfehlerbehandlung

Statt eine Seite zu ersetzen, wird permanent eine Menge freier Seiten gehalten

Auslagerung geschieht im Voraus

Effizienter: Ersetzungszeit besteht im Wesentlichen nur aus Einlagerungszeit

■

– –

■

–

–

Behalten der Seitenzuordnung auch nach der Auslagerung

Wird die Seite doch noch benutzt, bevor sie durch eine andere ersetzt wird, kann sie mit hoher Effizienz wiederverwendet werden.

Seite wird aus Freiseitenpuffer ausgetragen und wieder dem entsprechenden Prozess zugeordnet.

 16.06.2021 Betriebssysteme: 09 - Virtueller Speicher 33
   Inhalt

Motivation Demand Paging Seitenersetzung Seitenzuordnung Ladestrategie Zusammenfassung

■ ■ ■ ■ ■ ■

  16.06.2021

Betriebssysteme: 09 - Virtueller Speicher 34
   Zuordnung von Seitenrahmen zu Prozessen

Problem: Aufteilung der Seitenrahmen auf die Prozesse

Wie viele eingelagerte Seiten soll man einem Prozess zugestehen?

■

–

■

–

■

–

●

●

Maximum: begrenzt durch Anzahl der (physischen) Seitenrahmen Minimum: abhängig von der Prozessorarchitektur

Mindestens die Anzahl von Seiten nötig, die theoretisch bei einem Maschinenbefehl benötigt werden

(z.B. zwei Seiten für den Befehl, vier Seiten für die adressierten Daten)

–

Gleiche Zuordnung

Anzahl der Prozesse bestimmt die Menge, die ein Prozess bekommt

Größenabhängige Zuordnung

Größe des Programms fließt in die zugeteilte Menge der Seitenrahmen ein

 16.06.2021 Betriebssysteme: 09 - Virtueller Speicher 35
   Zuordnung von Seitenrahmen zu Prozessen

Globale und lokale Anforderung von Seiten

Lokal: Prozess ersetzt nur immer seine eigenen Seiten

Seitenfehler-Verhalten liegt nur in der Verantwortung des Prozesses Keine Interferenz zwischen Prozessen

Auslagerung unter Umständen unnötig (global ungenutzte Seiten)

■

■

– – –

■

– –

Global: Prozess ersetzt auch Seiten anderer Prozesse

Ungenutzt Seitenrahmen anderen Prozesse können verwendet werden Interferenz zwischen Prozessen (Seitenfehler-Verhalten)

 16.06.2021 Betriebssysteme: 09 - Virtueller Speicher 36
   Seitenflattern (Thrashing)

Ausgelagerte Seite wird gleich wieder angesprochen:

Prozess verbringt mehr Zeit mit dem Warten auf das Beheben von Seitenfehlern als mit der eigentlichen Ausführung.

■

–

     Grad des Mehrprogrammbetriebs (Anzahl der Prozesse)

thrashing

 16.06.2021 Betriebssysteme: 09 - Virtueller Speicher 37

 CPU-Auslastung
   Seitenflattern (Thrashing)

Ursachen:

Prozess ist nahe am Seitenminimum

Zu viele Prozesse gleichzeitig im System Schlechte Ersetzungsstrategie

Lokale Seitenanforderung behebt Thrashing zwischen Prozessen

Zuteilung einer genügend großen Zahl von Rahmen behebt Prozess-lokales Thrashing

Begrenzung der Prozessanzahl

■

– – –

➔ ➔

–

 16.06.2021 Betriebssysteme: 09 - Virtueller Speicher 38
   Lösung 1: Auslagerung von Prozessen

inaktiver Prozess benötigt keine Seitenrahmen

Seitenrahmen teilen sich auf weniger Prozesse auf Verbindung mit der Ablaufplanung (Scheduling) nötig

■

– –

●

●

Verhindern von Aushungerung Erzielen kurzer Reaktionszeiten

  16.06.2021

Betriebssysteme: 09 - Virtueller Speicher 39
   Lösung 2: Arbeitsmengenmodell

Seitenmenge, die ein Prozess wirklich braucht (Working Set)

Kann nur angenähert werden, da üblicherweise nicht vorhersehbar

■

–

■

–

Annäherung durch Betrachten der letzten ∆ Seiten, die angesprochen wurden

geeignete Wahl von ∆

●

●

zu groß: Überlappung von lokalen Zugriffsmustern

zu klein: Arbeitsmenge enthält nicht alle nötigen Seiten

 1

 2

 3

 4

 1

 2

 5

 1

 2

 3

 4

 5

      –

Hinweis: ∆ > Arbeitsmenge, da Seiten in der Regel mehrfach hintereinander angesprochen werden

∆

Referenzfolge

 16.06.2021 Betriebssysteme: 09 - Virtueller Speicher 40
   Arbeitsmengenmodell

Beispiel: Arbeitsmengen bei verschiedenen ∆

■

  Referenzfolge

1

2

3

4

1

2

5

1

2

3

4

5

∆=3

Seite 1

X

X

X

 X

X

X

X

X

X

Seite 2

 X

X

X

 X

X

X

X

X

X

 Seite 3

X

X

X

X

X

X

Seite 4

X

X

X

X

X

Seite 5

X

X

X

 X

∆=4

Seite 1

X

X

X

X

X

X

X

X

X

X

X

 Seite 2

 X

X

X

X

X

X

X

X

X

X

X

Seite 3

X

X

X

X

X

X

X

Seite 4

X

X

X

X

X

X

Seite 5

X

X

X

X

  X

                                                                               16.06.2021 Betriebssysteme: 09 - Virtueller Speicher 41
   Diskussion: Arbeitsmengenmodell

Annäherung der Zugriffe durch die Zeit

Bestimmtes Zeitintervall ist ungefähr proportional zu Anzahl von Speicherzugriffen

■

–

■

– –

Virtuelle Zeit des Prozesses muss gemessen werden

Nur die Zeit relevant, in der der Prozess im Zustand RUNNING ist Verwalten virtueller Uhren pro Prozess

 16.06.2021 Betriebssysteme: 09 - Virtueller Speicher 42
   Arbeitsmengenbestimmung mit Zeitgeber

Annäherung der Arbeitsmenge mit

Referenzbit

Altersangabe pro Seite (Zeitintervall ohne Benutzung) Timer-Interrupt (durch Zeitgeber)

■

– – –

■

–

Algorithmus:

durch regelmäßigen Interrupt wird mittels Referenzbit die Altersangabe fortgeschrieben:

–

Seiten mit Alter > ∆ sind nicht mehr in der Arbeitsmenge des jeweiligen Prozesses.

●

●

●

ist Referenzbit gesetzt (Seite wurde benutzt), wird das Alter auf Null gesetzt; ansonsten wird Altersangabe erhöht.

Es werden nur die Seiten des gerade laufenden Prozesses „gealtert“.

 16.06.2021 Betriebssysteme: 09 - Virtueller Speicher 43
   Arbeitsmengenbestimmung mit Zeitgeber

ungenau

System ist aber nicht empfindlich auf diese Ungenauigkeit Verringerung der Zeitintervalle: höherer Aufwand, genauere Messung

■

– –

■

–

ineffizient

große Menge von Seiten zu betrachten

 16.06.2021 Betriebssysteme: 09 - Virtueller Speicher 44
   Arbeitsmengenbestimmung mit WSClock

Algorithmus WSClock (working set clock)

Arbeitet wie Clock

Seite wird nur dann ersetzt, wenn sie nicht zur Arbeitsmenge ihres Prozesses

gehört oder der Prozess deaktiviert ist.

■

– –

■

Bei Zurücksetzen des Referenzbits wird die virtuelle Zeit des jeweiligen Prozesses eingetragen, die z.B. im PCB gehalten und fortgeschrieben wird.

Bestimmung der Arbeitsmenge erfolgt durch Differenzbildung von virtueller Zeit des Prozesses und Zeitstempel in dem Seitenrahmen.

■

 16.06.2021 Betriebssysteme: 09 - Virtueller Speicher 45
   Arbeitsmengenbestimmung mit WSClock

■

WSClock-Algorithmus

∆=3

Virtuelle Prozesszeit

     A

 10

 36

   G

 1

 4

  B

 10

 16

    F

 1

 1

  C

 0

 4

  E

 0

 0

  D

 0

 1

    16.06.2021

Betriebssysteme: 09 - Virtueller Speicher 46

PCB1

1

Referenzbit

Seite wird ersetzt

Zeitstempel des Rahmens

PCB2

6

PCB3

5
   Diskussion: Arbeitsmengenprobleme

Speicherplatzbedarf für Zeitstempel

Zuordnung zu einem Prozess nicht immer möglich

gemeinsam genutzte Seiten in modernen Betriebssystemen eher die Regel als die Ausnahme

■ ■

–

■

–

●

●

Shared Libraries

Gemeinsame Seiten im Datensegment (Shared Memory)

Lösung 3: Thrashing kann durch direkte Steuerung der Seitenfehlerrate leichter vermieden werden

Messung pro Prozess

●

●

Rate < Schwellwert: Menge der Seitenrahmen verkleinern Rate > Schwellwert: Menge der Seitenrahmen vergrößern

 16.06.2021

Betriebssysteme: 09 - Virtueller Speicher 47
   Inhalt

Motivation Demand Paging Seitenersetzung Seitenzuordnung Ladestrategie Zusammenfassung

■ ■ ■ ■ ■ ■

  16.06.2021

Betriebssysteme: 09 - Virtueller Speicher 48
   Ladestrategie

Auf Anforderung laden

Damit ist man auf der sicheren Seite

■

–

■

– –

– –

●

●

Durch Interpretation des Befehls beim ersten Seitenfehler können die benötigten anderen Seiten im Voraus eingelagert werden.

Weitere Seitenfehler werden verhindert.

Im Voraus laden

Schwierig: Ausgelagerte Seiten werden eigentlich nicht gebraucht. Oftmals löst eine Maschineninstruktion mehrere Seitenfehler aus.

Komplettes Working Set bei Prozesseinlagerung im Voraus laden Sequentielle Zugriffsmuster erkennen und Folgeseiten vorab laden

 16.06.2021 Betriebssysteme: 09 - Virtueller Speicher 49
   Inhalt

Motivation Demand Paging Seitenersetzung Seitenzuordnung Ladestrategie Zusammenfassung

■ ■ ■ ■ ■ ■

  16.06.2021

Betriebssysteme: 09 - Virtueller Speicher 50
   Zusammenfassung

Virtueller Speicher ermöglicht die Nutzung großer logischer Adressräume trotz Speicherbeschränkung.

Komfort hat aber seinen Preis:

Aufwand in der Hardware

Komplexe Algorithmen im Betriebssystem „Erstaunliche“ Effekte (wie „Thrashing“) Zeitverhalten nicht vorhersagbar

■

■

– – – –

■

Einfache (Spezialzweck-)Systeme, die diesen „Luxus“ nicht unbedingt benötigen, sollten besser darauf verzichten.

 16.06.2021 Betriebssysteme: 09 - Virtueller Speicher 51
   Betriebssysteme (BS)

10. Eingabe und Ausgabe

https://sys.cs.tu-dortmund.de/DE/Teaching/SS2021/BS/

23.06.2021

Peter Ulbrich

peter.ulbrich@tu-dortmund.de

Basierend auf Betriebssysteme von Olaf Spinczyk, Universität Osnabrück
   Wiederholung: Betriebsmittel

Das Betriebssystem hat folgende Aufgaben:

Verwaltung der Betriebsmittel des Rechners

Schaffung von Abstraktionen, die Anwendungen einen einfachen und effizienten Umgang mit Betriebsmitteln erlauben

■

– –

■

– –

 ■

–

Bisher:

Prozesse Arbeitsspeicher

Heute: E/A-Geräte

Verwaltung von Peripheriegeräten

     Hauptspeicher

(Memory)

 E/A-Schnittstellen

(Interfaces)

E/A-Geräte

(I/O Devices)

Hintergrundspeicher

(Secondary Storage)

 09.06.2021

2

Prozessor

(CPU, Central Processing Unit)
   Inhalt

Ein-/Ausgabe-Hardware Geräteprogrammierung Aufgaben des Betriebssystems Zusammenfassung

 ■ ■ ■ ■

  23.06.2021 Betriebssysteme: 10 - Eingabe und Ausgabe 3

Tanenbaum

5: Ein-Ausgabe

Silberschatz

13: I/O-Systems
   Anbindung von E/A-Geräten

           Tastatur-

Tastatur-

controller

controller

Video-

Video-

controller

controller

Platten-

Platten-

controller

controller

Ethernet-

Ethernet-

controller

controller

 Bus

 Ein-/Ausgabegeräte werden über

Ein-/Ausgabegeräte werden über

Controller an den Systembus Controller an den Systembus

  CPU

CPU

Haupt-

Haupt-

speicher

speicher

angebunden. Die Programmierung

angebunden. Die Programmierung

erfolgt über E/A-Register auf den erfolgt über E/A-Register auf den

Controllern.

Controllern.

 23.06.2021 Betriebssysteme: 10 - Eingabe und Ausgabe 4
   Beispiel: PC-Tastatur

serielle zeichenweise Kommunikation

Tastatur ist „intelligent“ (besitzt eigenen Prozessor)

■

–

    Make- und Break-Codes für gedrückte Tasten

Steuercodes z.B. LEDs an/aus

Sobald ein Zeichen abholbereit ist, löst der Controller eine Unterbrechung aus.

   Aufgaben der Software

Aufgaben der Software

●

Initialisierung des Controllers

●

●

Abholen der Zeichen von der Tastatur

Initialisierung des Controllers

Abholen der Zeichen von der Tastatur

controller

 ●

●

Abbildung der Make- und Break-

●

●

Senden von Kommandos

●

Abbildung der Make- und Break-

Codes auf ASCII

Codes auf ASCII

Senden von Kommandos

 23.06.2021

Betriebssysteme: 10 - Eingabe und Ausgabe 5

Tastatur-

Tastatur-

controller
   Beispiel: CGA-Videocontroller

Kommunikation über Videosignal

Umwandlung des Bildschirmspeicherinhalts in ein Bild (80x25 Z.)

■

–

Videosignal:

RGB, Intensity, VSync, HSync

 CGA-Videocontroller

CGA-Videocontroller

      AB

 ●

Initialisierung des Controllers

●

●

Bildschirmspeicher mit den gewünschten Zeichencodes füllen

●

●

Steuerung der Position des Cursors

●

●

Cursor an- und abschalten

●

Bildschirmspeicher mit den gewünschten Zeichencodes füllen

Steuerung der Position des Cursors

Cursor an- und abschalten

24

0 1 79 0

    Steuer- und Statusregister

A

B

...

Bildschirmspeicher

   Aufgaben der Software

Aufgaben der Software

Initialisierung des Controllers

 23.06.2021 Betriebssysteme: 10 - Eingabe und Ausgabe 6

 ... Zeichen Attribut

rot gelb

...
   Beispiel: IDE-Plattencontroller

Kommunikation über AT-Befehle

blockweiser wahlfreier Zugriff auf Datenblöcke

AT-Befehle

• Laufwerk kalibrieren

• Block lesen/schreiben/verifizieren • Spur formatieren

• Kopf positionieren

• Diagnose

• Laufwerksparameter einstellen

Datenblöcke

(à 512 Bytes)

■

–

       Steuer- und Statusreg.

     23.06.2021

Betriebssysteme: 10 - Eingabe und Ausgabe

7

Aufgaben der Software:

Aufgaben der Software:

●

AT-Befehle in Register schreiben

●

AT-Befehle in Register schreiben

Plattencontroller

Plattencontroller

 Sektor- puffer

Sobald der Sektorpuffer ausgelesen bzw. voll- geschrieben wurde, löst der Controller eine Unterbrechung aus.

 ●

Sektorpuffer füllen/leeren

●

●

Auf die Unterbrechungen reagieren

●

●

Fehlerbehandlung

●

Sektorpuffer füllen/leeren

Auf die Unterbrechungen reagieren

Fehlerbehandlung

  ...
   Beispiel: Ethernet-Controller

serielle paketbasierte Buskommunikation

Pakete haben eine variable Größe und enthalten Adressen

0 – 1500 Byte

gather

DMA

■

–

 Präambel+SFD

  Ziel

Quelle

  Typ

 Daten

  CRC

      Aufgaben der Software

Aufgaben der Software

Ethernet-

Ethernet-

controller

controller

Unterbrechung

nach Abschluss jeder Operation

   Bus

scatter

  ●

Bereitstellen der Daten bzw. Puffer

●

 ●

Initialisierung der Controllerregister

●

●

auf die Unterbrechungen reagieren

●

●

Fehlerbehandlung

●

Bereitstellen der Daten bzw. Puffer

Initialisierung der Controllerregister

auf die Unterbrechungen reagieren

Fehlerbehandlung

Haupt- speicher

Hauptspeicher-

Hauptspeicher-

zugriff erfolgt per

zugriff erfolgt per

Scatter/Gather

Scatter/Gather

Busmaster-DMA. Busmaster-DMA.

 23.06.2021

Betriebssysteme: 10 - Eingabe und Ausgabe

8
   Geräteklassen

zeichenorientierte Geräte

Tastatur, Drucker, Modem, Maus, ...

meist rein sequentieller Zugriff, selten wahlfreie Positionierung

■

– –

■

– –

■

– –

– –

blockorientierte Geräte

Festplatte, Diskette, CD-ROM, DVD, Bandlaufwerke, ... meist wahlfreier blockweiser Zugriff (random access)

Andere Geräte passen weniger gut in dieses Schema:

Grafikkarten (insbesondere 3D-Beschleunigung)

Netzwerkkarten (Protokolle, Adressierung, Broadcast/Multicast, Nachrichtenfilterung, ...)

Zeitgeberbaustein (einmalige oder periodische Unterbrechungen) ...

 23.06.2021 Betriebssysteme: 10 - Eingabe und Ausgabe 9
  Unterbrechungen ...

signalisieren, dass die Software aktiv werden muss

Ablauf einer Unterbrechungsbehandlung auf der Hardwareebene

■

1. Gerät hat Operation beendet → („interrupt request“, IRQ)

Bus

4. Controller teilt der CPU die Nummer der Unterbrechung mit

3. CPU bestätigt Beginn der Unterbrechungs- behandlung („acknowledge“)

 Interrupt-

          2. Controller signalisiert Unterbrechungs- anforderung

     23.06.2021

(„interrupt vector“) 10 Betriebssysteme: 10 - Eingabe und Ausgabe

Interrupt-

controller

controller

 eth

  CPU

  Software kann IRQ-

Software kann IRQ-

Behandlung unter-

Behandlung unter-

drücken. x86:

drücken. x86:

sti → erlauben sti → erlauben

cli → unterdrücken cli → unterdrücken

  ...
   Direct Memory Access (DMA) ...

... wird von komplexen Controllern benutzt, um Daten unabhängig von der CPU in den bzw. aus dem Hauptspeicher zu transferieren.

Durchführung eines DMA-Transfers

■

 1. CPU programmiert DMA-Controller

DMA-Controller

Disk-Controller

        CPU

CPU

address

 count

control

4. ACK

Daten- puffer

Haupt-

Haupt-

 speicher

speicher

      5. Unterbrechung wenn alles erledigt

2. DMA-Controller fordert Daten an

Bus

3. Datentransfer

  2., 3. und 4. wird in Abhängigkeit von

2., 3. und 4. wird in Abhängigkeit von

count wiederholt durchgeführt count wiederholt durchgeführt

 23.06.2021

Betriebssysteme: 10 - Eingabe und Ausgabe

11
   Inhalt

Ein-/Ausgabe-Hardware Geräteprogrammierung Aufgaben des Betriebssystems Zusammenfassung

■ ■ ■ ■

  23.06.2021 Betriebssysteme: 10 - Eingabe und Ausgabe 12
   Ein-/Ausgabeadressraum

Zugriff auf Controller-Register und Controller-Speicher erfolgt je nach Systemarchitektur ...

■

   zwei Adressräume

ein Adressraum

zwei Adressräume

Speicher

    0xffff

   0x0000

(a)

(b)

(c)

(a) separater E/A-Adressraum

I/O Ports

anzusprechen über spezielle Maschineninstruktionen

(b) gemeinsamer Adressraum (Memory-Mapped I/O) (c) hybride Architektur

●

 23.06.2021 Betriebssysteme: 10 - Eingabe und Ausgabe

13
   Arbeitsweise von Gerätetreibern

Je nach Fähigkeiten des Geräts erfolgt E/A mittels ...

Polling (oder „Programmierte E/A“), Unterbrechungen oder

DMA

■

– – –

■

Beispiel: Drucken einer Textzeile

  23.06.2021 Betriebssysteme: 10 - Eingabe und Ausgabe 14

 Quelle: Tanenbaum, „Modern Operating Systems“
   Polling (oder „Programmierte E/A“)

... bedeutet aktives Warten auf ein Ein-/Ausgabegerät.

  /* Zeichen in Kern-Puffer p kopieren */

copy_from_user (buffer, p, count);

/* Schleife über alle Zeichen */

for (i = 0; i < count; i++) {
  /* Warte “aktiv” bis Drucker bereit */
while (*printer_status_reg != READY) ;
  /* Ein Zeichen ausgeben */
  *printer_data_reg = p[i];
}
return_to_user ();
Betriebssystem-
Betriebssystem-
funktion zum Drucken
funktion zum Drucken
von Text im Polling- von Text im Polling-
Betrieb
Betrieb
 23.06.2021 Betriebssysteme: 10 - Eingabe und Ausgabe 15
Pseudo-Code einer
Pseudo-Code einer
 
   Unterbrechungsgetriebene E/A
... bedeutet, dass die CPU während der Wartezeit einem anderen Prozess zugeteilt werden kann.
Code, der die E/A-Operation initiiert Unterbrechungsbehandlungsroutine
  copy_from_user (buffer, p, count);
/* Druckerunterbrechungen erlauben */
enable_interrupts ();
/* Warte bis Drucker bereit */
while (*printer_status_reg != READY); /* Erstes Zeichen ausgeben */
*printer_data_reg = p[i++];
scheduler ();
return_to_user ();
 23.06.2021 Betriebssysteme: 10 - Eingabe und Ausgabe 16
if (count > 0) { *printer_data_reg = p[i]; count--;

i++;

}

else

  unblock_user ();

acknowledge_interrupt ();

return_from_interrupt ();
   DMA-getriebene E/A

... bedeutet, dass die Software nicht mehr für den Datentransfer zwischen Controller und Hauptspeicher zuständig ist.

Die CPU wird weiter entlastet.

–

 copy_from_user (buffer, p, count);

set_up_DMA_controller (p, count);

scheduler ();

return_to_user ();

 Code, der die E/A-Operation initiiert Unterbrechungsbehandlungsroutine

acknowledge_interrupt ();

unblock_user ();

return_from_interrupt ();

 23.06.2021 Betriebssysteme: 10 - Eingabe und Ausgabe 17
   Diskussion: Unterbrechungen

Kontextsicherung

Wird teilweise von der CPU selbst erledigt.

■

–

–

●

z.B. Statusregister und Rücksprungadresse, aber nur das Minimum.

■

–

–

●

Alle veränderten Register müssen gesichert und am Ende der Behandlung wiederhergestellt werden.

Behandlungsroutine möglichst kurz

Während der Unterbrechungsbehandlung werden i.d.R. weitere Unterbrechungen unterdrückt.

Es droht der Verlust von Unterbrechungen

Möglichst nur den Prozess wecken, der auf E/A-Beendigung wartet.

 23.06.2021 Betriebssysteme: 10 - Eingabe und Ausgabe 18
   Diskussion: Unterbrechungen (2)

Unterbrechungen sind die Quelle der Asynchronität

Ursache für Race Conditions im Betriebssystemkern

■

–

■

–

Unterbrechungssynchronisation:

einfachste Möglichkeit: Unterbrechungsbehandlung durch die CPU zeitweise hart verbieten, während kritische Abschnitte durchlaufen werden.

–

BS gängig: mehrstufige Behandlungen, durch die das harte Sperren von Unterbrechungen minimiert wird

●

●

x86: sti, cli

wieder Gefahr des Unterbrechungsverlusts

●

●

●

●

Abstrakt: Prolog (asynchron) und Epilog (synchron zum BS) UNIX: Top Half, Bottom Half

Linux: Tasklets

Windows: Deferred Procedures

 23.06.2021

Betriebssysteme: 10 - Eingabe und Ausgabe 19
   Diskussion: Direct Memory Access

Caches

Heutige Prozessoren arbeiten mit Daten-Caches; DMA läuft am Cache vorbei!

Vor dem Aufsetzen eines DMA-Vorgangs muss der Cache-Inhalt in den Hauptspeicher zurückgeschrieben und invalidiert werden bzw.

der Cache darf für die entsprechende Speicherregion nicht eingesetzt werden.

■

–

–

■

–

– –

Speicherschutz

Heutige Prozessoren verwenden eine MMU zur Isolation von Prozessen und zum Schutz des Betriebssystems;

DMA läuft am Speicherschutz vorbei!

Fehler beim Aufsetzen von DMA-Vorgängen sind extrem kritisch. Anwendungsprozesse dürfen DMA-Controller nie direkt programmieren!

 23.06.2021 Betriebssysteme: 10 - Eingabe und Ausgabe 20
   Inhalt

Ein-/Ausgabe-Hardware Geräteprogrammierung Aufgaben des Betriebssystems Zusammenfassung

■ ■ ■ ■

  23.06.2021 Betriebssysteme: 10 - Eingabe und Ausgabe 21
   Aufgaben des Betriebssystems

Geräteabstraktionen schaffen

einheitlich, einfach, aber vielseitig

■

–

■

–

■

–

■

–

■

– –

■

■

Stromsparzustände verwalten

Plug&Play unterstützen

...

■

Ein-/Ausgabenprimitiven bereitstellen

synchron und/oder asynchron

Pufferung

falls das Gerät bzw. der Empfängerprozess noch nicht bereit ist

Geräteansteuerung

möglichst effizient unter Beachtung mechanischer Eigenschaften

Ressourcenzuordnung verwalten

bei teilbaren Geräten: Welcher Prozess darf wo lesen/schreiben? bei unteilbaren Geräten: zeitweise Reservierungen

 23.06.2021 Betriebssysteme: 10 - Eingabe und Ausgabe 22
   Aufgaben des Betriebssystems

Geräteabstraktionen schaffen

einheitlich, einfach, aber vielseitig

■

–

■

–

■

–

■

–

■

– –

■

■

Stromsparzustände verwalten

Plug&Play unterstützen

...

■

Ein-/Ausgabenprimitiven bereitstellen

synchron und/oder asynchron

Pufferung

falls das Gerät bzw. der Empfängerprozess noch nicht bereit ist

Geräteansteuerung

möglichst effizient unter Beachtung mechanischer Eigenschaften

Ressourcenzuordnung verwalten

bei teilbaren Geräten: Welcher Prozess darf wo lesen/schreiben? bei unteilbaren Geräten: zeitweise Reservierungen

 23.06.2021 Betriebssysteme: 10 - Eingabe und Ausgabe 23
   Schichten des E/A-Subsystems

 Quelle: Tanenbaum, „Modern Operating Systems“

 23.06.2021 Betriebssysteme: 10 - Eingabe und Ausgabe 24
   UNIX: Geräteabstraktionen

Periphere Geräte werden als Spezialdateien repräsentiert:

Geräte können wie Dateien mit Lese- und Schreiboperationen angesprochen werden.

Öffnen der Spezialdateien schafft eine Verbindung zum Gerät, die durch einen Treiber hergestellt wird.

direkter Durchgriff vom Anwender auf den Treiber

■

–

–

–

■

–

■

–

blockorientierte Spezialdateien (block devices)

Plattenlaufwerke, Bandlaufwerke, Floppy Disks, CD-ROMs

zeichenorientierte Spezialdateien (character devices)

serielle Schnittstellen, Drucker, Audiokanäle etc.

 23.06.2021 Betriebssysteme: 10 - Eingabe und Ausgabe 25
   UNIX: Geräteabstraktionen (2)

Eindeutige Beschreibung der Geräte durch ein 3-Tupel: (Gerätetyp, Major Number, Minor Number)

Gerätetyp: Block Device, Character Device Major Number:

Auswahlnummer für einen Treiber

Minor Number:

Auswahl eines Gerätes innerhalb eines Treibers

■

■

■

■

 23.06.2021 Betriebssysteme: 10 - Eingabe und Ausgabe 26
   UNIX: Geräteabstraktionen (3)

Auszug aus dem Listing des /dev-Verzeichnisses

■

 brw-rw---- ulbr disk

3, 0 2008-06-15 14:14 /dev/hda

brw-rw---- ulbr disk

3, 0 2008-06-15 14:14 /dev/hda

brw-rw---- ulbr disk

3, 64 2008-06-15 14:14 /dev/hdb

brw-rw---- ulbr disk

3, 64 2008-06-15 14:14 /dev/hdb

brw-r----- root disk

8, 0 2008-06-15 14:13 /dev/sda

brw-r----- root disk

8, 0 2008-06-15 14:13 /dev/sda

brw-r----- root disk

8, 1 2008-06-15 14:13 /dev/sda1

brw-r----- root disk

8, 1 2008-06-15 14:13 /dev/sda1

crw-rw---- root uucp

4, 64 2006-05-02 08:45 /dev/ttyS0

crw-rw---- root uucp

4, 64 2006-05-02 08:45 /dev/ttyS0

crw-rw---- root lp

6, 0 2008-06-15 14:13 /dev/lp0

crw-rw---- root lp

6,

0 2008-06-15 14:13 /dev/lp0

crw-rw-rw- root root

1,

3 2006-05-02 08:45 /dev/null

crw-rw-rw- root root

1,

3 2006-05-02 08:45 /dev/null

lrwxrwxrwx root root

3 2008-06-15 14:14 /dev/cdrecorder -> hdb

lrwxrwxrwx root root

3 2008-06-15 14:14 /dev/cdrecorder -> hdb

lrwxrwxrwx root root

3 2008-06-15 14:14 /dev/cdrom -> hda

lrwxrwxrwx root root

3 2008-06-15 14:14 /dev/cdrom -> hda

 Zugriffs- Eigen- Major und rechte tümer Minor No.

c: character device b: block device

l: link

Erstellungs- zeitpunkt der Spezialdatei

Name der Spezialdatei

 23.06.2021 Betriebssysteme: 10 - Eingabe und Ausgabe 27
   UNIX: Zugriffsprimitiven

Das Wichtigste in Kürze ... (siehe man 2 ...)

int open(const char *devname, int flags)

Öffnen eines Geräts. Liefert Dateideskriptor als Rückgabewert.

■

–

■

– –

■

–

■

–

■

–

off_t lseek(int fd, off_t offset, int whence)

Positioniert den Schreib-/Lesezeiger nur bei Geräten mit wahlfreiem Zugriff

ssize_t read(int fd, void *buf, size_t count)

Einlesen von max. count Bytes in Puffer buf von Deskriptor fd

ssize_t write(int fd, const void *buf, size_t count)

Schreiben von count Bytes aus Puffer buf auf Deskriptor fd int close(int fd)

Schließen eines Geräts: Dateideskriptor fd kann danach nicht mehr benutzt werden.

 23.06.2021 Betriebssysteme: 10 - Eingabe und Ausgabe 28
   UNIX: Gerätespezifische Funktionen

Spezielle Geräteeigenschaften werden über ioctl angesprochen:

■

 ■

Schnittstelle generisch, Semantik gerätespezifisch:

IOCTL(2) Linux Programmer's Manual

IOCTL(2)

IOCTL(2) Linux Programmer's Manual

IOCTL(2)

NAME

NAME

ioctl - control device

SYNOPSIS

SYNOPSIS

CONFORMING TO

CONFORMING TO

ioctl - control device

#include 

#include 

int ioctl(int d, int request, ...);

int ioctl(int d, int request, ...);

 No single standard. Arguments, returns, and semantics of

No single standard. Arguments, returns, and semantics of

ioctl(2) vary according to the device driver in question

ioctl(2) vary according to the device driver in question

(the call is used as a catch-all for operations that

(the call is used as a catch-all for operations that

don't cleanly fit the Unix stream I/O model). The ioctl

don't cleanly fit the Unix stream I/O model). The ioctl

function call appeared in Version 7 AT&T Unix.

function call appeared in Version 7 AT&T Unix.

 23.06.2021 Betriebssysteme: 10 - Eingabe und Ausgabe 29
   UNIX: Warten auf mehrere Geräte

bisher: Lese- oder Schreibaufrufe blockieren

Was tun beim Lesen von mehreren Quellen?

■

–

■

– – –

Alternative 1: nichtblockierende Ein-/Ausgabe

O_NDELAY beim open()

Polling-Betrieb: Prozess muss immer wieder read() aufrufen unbefriedigend, da Verschwendung von CPU-Zeit bis etwas vorliegt

 23.06.2021 Betriebssysteme: 10 - Eingabe und Ausgabe 30
   UNIX: Warten auf mehrere Geräte (2)

Alternative 2: Blockieren an mehreren Dateideskriptoren

Systemaufruf:

int select (int nfds, fd_set *readfds, fd_set *writefds, fd_set *errorfds, struct timeval *timeout);

nfds legt fest, bis zu welchem Dateideskriptor select wirken soll. ...fds sind Dateideskriptoren, auf die gewartet werden soll:

■

–

– –

–

–

–

Timeout legt fest, wann der Aufruf spätestens deblockiert. Makros zum Erzeugen der Dateideskriptormengen

Ergebnis: In den Dateideskriptormengen sind nur noch die Dateideskriptoren vorhanden, die zur Deblockade führten.

●

●

●

readfds — bis etwas zum Lesen vorhanden ist writefds — bis man schreiben kann errorfds — bis ein Fehler aufgetreten ist

 23.06.2021 Betriebssysteme: 10 - Eingabe und Ausgabe 31
   Pufferung bei E/A-Operationen

Probleme ohne Datenpuffer im Betriebssystem:

Daten, die eintreffen, bevor read ausgeführt wurde (z.B. von der Tastatur), müssten verloren gehen.

Wenn ein Ausgabegerät beschäftigt ist, müsste write scheitern oder den Prozess blockieren, bis das Gerät wieder bereit ist.

Ein Prozess, der eine E/A-Operation durchführt, kann nicht ausgelagert werden.

■

–

–

–

 Betriebssystem

Einlesen

Benutzerprozess

   E/A-Gerät

E/A-Gerät

  (a) Leseoperation ohne Puffer

 23.06.2021 Betriebssysteme: 10 - Eingabe und Ausgabe 32
   E/A-Einzelpuffer

Einlesen:

Daten können vom System entgegengenommen werden, auch wenn der Leserprozess noch nicht read aufgerufen hat.

Bei Blockgeräten kann der nächste Block vorausschauend gelesen werden, während der vorherige verarbeitet wird.

Prozess kann problemlos ausgelagert werden. DMA erfolgt in Puffer.

■

–

–

–

■

–

Schreiben:

Daten werden kopiert. Aufrufer blockiert nicht. Datenpuffer im Benutzeradressraum kann sofort wiederverwendet werden.

Betriebssystem

Einlesen       Verschieben

(b) Leseoperation mit Einzelpuffer

Benutzerprozess

   E/A-Gerät

E/A-Gerät

  23.06.2021 Betriebssysteme: 10 - Eingabe und Ausgabe 33
   E/A-Einzelpuffer

■

 ■

Einlesen:

Eine einfache Rechnung zeigt den Leistungsgewinn beim wiederholten

–

–

Daten können vom System entgegengenommen werden, auch wenn der Leserprozess noch nicht read aufgerufen hat.

M:

Dauer des Kopiervorgang (Systempuffer→Benutzerprozess)

M:

Dauer des Kopiervorgang (Systempuffer→Benutzerprozess)

–

Daten werden kopiert. Aufrufer blockiert nicht. Datenpuffer im Benutzeradressraum kann sofort wiederverwendet werden.

G:

Gesamtdauer für Lesen und Verarbeiten eines Blocks

Betriebssystem

G:

Gesamtdauer für Lesen und Verarbeiten eines Blocks

Leistungsabschätzung

Leistungsabschätzung

Eine einfache Rechnung zeigt den Leistungsgewinn beim wiederholten

–

während der vorherige verarbeitet wird.

Prozess kann problemlos ausgelagert werden. DMA erfolgt in Puffer.

Bei Blockgeräten kann der nächste Block vorausschauend gelesen werden,

blockweisen Lesen mit anschließender Verarbeitung:

blockweisen Lesen mit anschließender Verarbeitung:

T: Dauer der Leseoperation

T: Dauer der Leseoperation

C: Rechenzeit für die Verarbeitung

C: Rechenzeit für die Verarbeitung

Schreiben:

Benutzerprozess Verschieben

MitT≈CundM≈0wäreG ≈2∙G .LeideristM>0. MitT≈CundM≈0wäreG0 ≈2∙GE.LeideristM>0.

ohne Puffer:

G = T + C G0 = T + C

ohne Puffer:

0

   E/A-Gerät

mit Puffer:

G = max (T, C) + M GE = max (T, C) + M

E/A-Gerät

mit Puffer:

Einlesen

  E

  (b) Leseoperation mit Einzelpuffer

0E

 23.06.2021 Betriebssysteme: 10 - Eingabe und Ausgabe 34
   E/A-Wechselpuffer

Einlesen:

Während Daten vom E/A-Gerät in den einen Puffer transferiert werden, kann der andere Pufferinhalt in den Empfängeradressraum kopiert werden.

■

–

■

–

Schreiben:

Während Daten aus einem Puffer zum E/A-Gerät transferiert werden, kann der andere Puffer bereits mit neuen Daten aus dem Senderadressraum gefüllt werden.

Betriebssystem

Einlesen       Verschieben

(c) Leseoperation mit Wechselpuffer

Benutzerprozess

   E/A-Gerät

E/A-Gerät

     23.06.2021

Betriebssysteme: 10 - Eingabe und Ausgabe 35
   E/A-Wechselpuffer

Einlesen:

Während Daten vom E/A-Gerät in den einen Puffer transferiert werden, kann der andere Pufferinhalt in den Empfängeradressraum kopiert werden.

■

–

■

–

Schreiben:

Während Daten aus einem Puffer zum E/A-Gerät transferiert werden, kann der andere Puffer bereits mit neuen Daten aus dem Senderadressraum gefüllt werden.

Betriebssystem

Einlesen       Verschieben

(c) Leseoperation mit Wechselpuffer

Benutzerprozess

   E/A-Gerät

E/A-Gerät

     23.06.2021

Betriebssysteme: 10 - Eingabe und Ausgabe 36
   E/A-Wechselpuffer

Einlesen:

Während Daten vom E/A-Gerät in den einen Puffer transferiert werden, kann der andere Pufferinhalt in den Empfängeradressraum kopiert werden.

■

–

 ■

Schreiben:

werden.

Leistungsabschätzung

Leistungsabschätzung

Während Daten aus einem Puffer zum E/A-Gerät transferiert werden, kann der

Mit einem Wechselpuffer kann ein Leseoperation parallel zur

Mit einem Wechselpuffer kann ein Leseoperation parallel zur

–

KopiearonpdereaPtiuofnfeur nbedrVeietsramrbitenietuenngDeartfeonlgaeuns.dem Senderadressraum gefüllt Kopieroperation und Verarbeitung erfolgen.

ohne Puffer: G = T + C ohne Puffer: G0 = T + C

0

mit Puffer: G mit Puffer: GE E

mit WecEh/As-eGlperuäftfer: G mit WecEh/As-eGlperuäftfer: GW W

MitC+M≤TkönntedasGerät MitC+M≤TkönntedasGerät

Betriebssystem

= max (T, C) + M

= max (T, C) + M

Benutzerprozess Verschieben

   = max (T, C + M)

  Einlesen

= max (T, C + M)

   zu 100% ausgelastet werden.

zu 100% ausgelastet werden.

(c) Leseoperation mit Wechselpuffer

 23.06.2021

Betriebssysteme: 10 - Eingabe und Ausgabe 37
   E/A-Ringpuffer

Einlesen:

Viele Daten können gepuffert werden, auch wenn der Leserprozess nicht schnell genug read-Aufrufe tätigt.

■

–

■

–

Schreiben:

Ein Schreiberprozess kann mehrfach write-Aufrufe tätigen, ohne blockiert werden zu müssen.

Betriebssystem

Einlesen Verschieben

(d) Leseoperation mit Ringpuffer

Benutzerprozess

    E/A-Gerät

E/A-Gerät

          23.06.2021 Betriebssysteme: 10 - Eingabe und Ausgabe 38
   Diskussion: E/A-Puffer

E/A-Puffer entkoppeln die E/A-Operationen der Nutzerprozesse vom Gerätetreiber

Kurzfristig lässt sich eine erhöhte Ankunftsrate an E/A-Aufträgen bewältigen. Langfristig bleibt auch bei noch so vielen Puffern ein Blockieren von Prozessen

(oder Verlust von Daten) nicht aus.

■

– –

■

– – –

■

– –

Puffer haben ihren Preis:

Verwaltung der Pufferstruktur Speicherplatz

Zeit für das Kopieren

In komplexen Systemen wird teilweise mehrfach gepuffert.

Beispiel: Schichten von Netzwerkprotokollen Nach Möglichkeit vermeiden!

  23.06.2021 Betriebssysteme: 10 - Eingabe und Ausgabe 39
   Geräteansteuerung: Beispiel Festplatte

Treiber muss mechanische Eigenschaften beachten!

Plattentreiber hat in der Regel mehrere Aufträge in Warteschlange

Eine bestimmte Ordnung der Ausführung kann Effizienz steigern. Zusammensetzung der Bearbeitungszeit eines Auftrags:

■ ■

– –

■

Ansatzpunkt:

Positionierungszeit

Sektor

Rotationsachse

...

●

●

●

Positionierungszeit: Rotationsverzögerung: Übertragungszeit:

abhängig von akt. Stellung des Plattenarms Zeit bis der Magnetkopf den Sektor bestreicht Zeit zur Übertragung der eigentlichen Daten

Spuren

Schreib-/Leseköpfe

    23.06.2021 Betriebssysteme: 10 - Eingabe und Ausgabe

40
   E/A-Scheduling: FIFO

Bearbeitung gemäß Ankunft des Auftrags (First In First Out)

Referenzfolge (Folge von Spurnummern): 98,183,37,122,14,124,65,67

Aktuelle Spur: 53

■

–

–

 – –

Gesamtzahl der Spurwechsel: 640 Weite Bewegungen des Schwenkarms:

mittlere Bearbeitungsdauer lang!

 23.06.2021 Betriebssysteme: 10 - Eingabe und Ausgabe 41
   E/A-Scheduling: SSTF

Es wird der Auftrag mit der kürzesten Positionierzeit vorgezogen (Shortest Seek Time First)

dieselbe Referenzfolge: 98, 183, 37, 122, 14, 124, 65, 67 (Annahme: Positionierungszeit proportional zum Spurabstand)

Gesamtzahl der Spurwechsel: 236

ähnlich wie SJF kann auch SSTF zur Aushungerung führen! noch nicht optimal

■

– –

 – – –

 23.06.2021 Betriebssysteme: 10 - Eingabe und Ausgabe 42
   E/A-Scheduling: Elevator

Bewegung des Plattenarms in eine Richtung bis keine Aufträge mehr vorhanden sind (Fahrstuhlstrategie)

Gleiche Referenzfolge (Annahme: bisherige Kopfbewegung Richtung 0)

Gesamtzahl der Spurwechsel: 208

Neue Aufträge werden miterledigt ohne zusätzliche Positionierungszeit Keine Aushungerung, lange Wartezeiten aber nicht ausgeschlossen

■

–

 – – –

 23.06.2021 Betriebssysteme: 10 - Eingabe und Ausgabe 43
   Diskussion: E/A-Scheduling heute

Platten sind intelligente Geräte

Physikalische Eigenschaften werden verborgen (Logische Blöcke) Platten weisen riesige Caches auf

Solid State Disks enthalten keine Mechanik mehr

■

– – –

➔

➔

■

– –

E/A-Scheduling verliert langsam an Bedeutung Erfolg einer Strategie ist schwerer vorherzusagen

Trotzdem ist E/A-Scheduling noch immer sehr wichtig:

CPUs werden immer schneller, Platten kaum

Linux implementiert zur Zeit zwei verschiedene Varianten

der Fahrstuhlstrategie (+ FIFO für „Platten“ ohne Positionierungszeit):

●

●

DEADLINE: Bevorzugung von Leseanforderungen (kürzere Deadlines) COMPLETELY FAIR: Prozesse erhalten gleichen Anteil an E/A-Bandbreite

 23.06.2021

Betriebssysteme: 10 - Eingabe und Ausgabe 44
   Inhalt

Ein-/Ausgabe-Hardware Geräteprogrammierung Aufgaben des Betriebssystems Zusammenfassung

■ ■ ■ ■

  23.06.2021 Betriebssysteme: 10 - Eingabe und Ausgabe 45
   Zusammenfassung

E/A-Hardware ist sehr unterschiedlich

teilweise auch „hässlich“ zu programmieren

■

–

■

– – –

■

–

Die Kunst des Betriebssystembaus besteht darin, ...

trotzdem einheitliche und einfache Schnittstellen zu definieren effizient mit der Hardware umzugehen

CPU und E/A-Geräteauslastung zu maximieren.

Gerätetreibervielfalt ist für den Erfolg eines Betriebssystems extrem wichtig.

Bei Systemen wie Linux und Windows sind die Gerätetreiber das weitaus größte Subsystem.

 23.06.2021 Betriebssysteme: 10 - Eingabe und Ausgabe 46
   Betriebssysteme (BS)

11. Dateisysteme

https://sys.cs.tu-dortmund.de/DE/Teaching/SS2021/BS/

30.06.2021

Peter Ulbrich

peter.ulbrich@tu-dortmund.de

Basierend auf Betriebssysteme von Olaf Spinczyk, Universität Osnabrück
   Wiederholung: Betriebsmittel

Das Betriebssystem hat folgende Aufgaben:

Verwaltung der Betriebsmittel des Rechners

Schaffung von Abstraktionen, die Anwendungen einen einfachen und effizienten Umgang mit Betriebsmitteln erlauben

■

– –

■

– – –

 ■

–

Bisher:

Prozesse

Arbeitsspeicher

E/A-Geräte (insb. blockorientiert)

Heute: Dateisysteme

Organisation des Hintergrundspeichers

     Hauptspeicher

(Memory)

 E/A-Schnittstellen

(Interfaces) Betriebssysteme: 11 - Dateisysteme

E/A-Geräte

(I/O Devices)

Hintergrundspeicher

(Secondary Storage)

 30.06.2021

2

Prozessor

(CPU, Central Processing Unit)
  local

home

Dateisysteme erlauben die Dateisysteme erlauben die

 dauerhafte Speicherung

dauerhafte Speicherung

großer Datenmengen.

großer Datenmengen.

  bs.pdf

 Festplatte mit

Festplatte mit

6 Oberflächen

6 Oberflächen

 Das Betriebssystem stellt

Das Betriebssystem stellt

den Anwendungen die

den Anwendungen die

logische Sicht zur

logische Sicht zur

Verfügung und muss

Verfügung und muss

diese effizient realisieren.

diese effizient realisieren.

   Hintergrundspeicher

Logische Sicht

Verzeichnis

pu foo bar al

Datei

Physikalische Sicht

Rotationsachse

...

 / usr

  bin

  Abbildung

Spuren

Schreib-/Leseköpfe

  Sektor

  30.06.2021

Betriebssysteme: 11 - Dateisysteme

3
   Inhalt

Dateien

Freispeicherverwaltung Verzeichnisse

Dateisysteme

Pufferspeicher

Dateisysteme mit Fehlererholung Zusammenfassung

 ■ ■ ■ ■ ■ ■ ■

  30.06.2021 Betriebssysteme: 11 - Dateisysteme 4

Tanenbaum

6: Dateisysteme

Silberschatz

10: File System

11: Implementing File Systems
   Speicherung von Dateien

Dateien benötigen oft mehr als einen Block auf der Festplatte

Welche Blöcke werden für die Speicherung einer Datei verwendet?

■

–

Variable Länge

Datei

?

    Block 0

 Block 1

 Block 02

 Block 03

 Block 4

 Block 5

 Block 06

 Block 07

 Platte

 Feste Länge

 30.06.2021

Betriebssysteme: 11 - Dateisysteme 5
   Kontinuierliche Speicherung

Datei wird in Blöcken mit aufsteigenden Blocknummern gespeichert

Nummer des ersten Blocks und Anzahl der Folgeblöcke muss gespeichert werden, z.B. Start: Block 4; Länge: 3.

■

–

 Block 0

 Block 1

 Block 02

 Block 03

 Block 4

 Block 5

 Block 0

Block 6

 Block 07

  ■

–

–

–

Vorteile:

Zugriff auf alle Blöcke mit minimaler Positionierzeit des Schwenkarms schneller direkter Zugriff auf bestimmte Dateiposition

Einsatz z.B. bei nicht modifizierbaren Dateisystemen wie auf CDs/DVDs

 30.06.2021 Betriebssysteme: 11 - Dateisysteme 6
   Kontinuierliche Speicherung: Probleme

Finden des freien Platzes auf der Festplatte

Menge aufeinanderfolgender und freier Plattenblöcke

■

–

■

–

■ ■ ■

Fragmentierungsproblem

Verschnitt: nicht nutzbare Plattenblöcke; analog zur Speicherverwaltung

Größe bei neuen Dateien oft nicht im Voraus bekannt

Erweitern ist problematisch

Umkopieren, falls kein freier angrenzender Block mehr verfügbar

 30.06.2021 Betriebssysteme: 11 - Dateisysteme 7
   Verkettete Speicherung

Blöcke einer Datei sind verkettet

■

        –

z.B. Commodore-Systeme (CBM 64 etc.)

●

●

●

●

Blockgröße 256 Bytes

Die ersten zwei Bytes bezeichnen Spur- und Sektornummer des nächsten Blocks; wenn Spurnummer gleich Null → letzter Block.

254 Bytes Nutzdaten

Block 3

Block 8

Datei kann vergrößert und verkleinert werden

30.06.2021 Betriebssysteme: 11 - Dateisysteme 8

➔

Block 1

Block 9
   Verkettete Speicherung: Probleme

Speicher für Verzeigerung geht von Nutzdaten im Block ab

Ungünstig im Zusammenhang mit Paging:

Seite würde immer aus Teilen von zwei Plattenblöcken bestehen

■

–

■

–

■ ■

Schlechter direkter Zugriff auf bestimmte Dateiposition Häufiges Positionieren des Schreib-, Lesekopfs bei verstreuten

Datenblöcken

Fehleranfälligkeit

Datei ist nicht restaurierbar, falls einmal Verzeigerung fehlerhaft

 30.06.2021 Betriebssysteme: 11 - Dateisysteme 9
   Verkettete Speicherung: FAT

Verkettung wird in separaten Plattenblöcken gespeichert

FAT-Ansatz (FAT: File Allocation Table)

■

–

●

z.B. MS-DOS, Windows 95

FAT-Block

0 5 10

Erster Dateiblock

Blöcke der Datei: 3, 8, 1, 9

        9

  8

     1

 -

    Block 3

Block 8

Block 1

Block 9

  ■

– –

kompletter Inhalt des Datenblocks ist nutzbar

mehrfache Speicherung der FAT möglich: Einschränkung der Fehleranfälligkeit

Vorteile:

 30.06.2021 Betriebssysteme: 11 - Dateisysteme 10
   Verkettete Speicherung: Probleme (2)

Zusätzliches Laden mindestens eines Blocks

Caching der FAT zur Effizienzsteigerung nötig

■

–

■

–

■

■

Aufwändige Suche nach dem zugehörigen Datenblock bei bekannter Position in der Datei

Häufiges Positionieren des Schreib-, Lesekopfs bei verstreuten Datenblöcken

Laden unbenötigter Informationen

FAT enthält Verkettungen für alle Dateien

 30.06.2021 Betriebssysteme: 11 - Dateisysteme 11
   Diskussion: Chunks/Extents/Clusters

Variation:

Unterteilen einer Datei in kontinuierlich gespeicherte Folgen von Blöcken (Chunk, Extent oder Cluster genannt)

Reduziert die Zahl der Positionierungsvorgänge

Blocksuche wird linear in Abhängigkeit von der Chunk-Größe beschleunigt

■

–

– –

■

– –

■

Wird eingesetzt, bringt aber keinen fundamentalen Fortschritt.

Probleme:

zusätzliche Verwaltungsinformationen Verschnitt

●

●

feste Größe: innerhalb einer Folge (interner Verschnitt) variable Größe: außerhalb der Folgen (externer Verschnitt)

 30.06.2021 Betriebssysteme: 11 - Dateisysteme 12
   Indiziertes Speichern

Spezieller Plattenblock (Indexblock) enthält Blocknummern der Datenblöcke einer Datei:

■

Indexblock

0 5 10

Erster Dateiblock

Blöcke der Datei: 3, 8, 1, 9

     3

 8

 1

 9

          ■

Problem: Feste Anzahl von Blöcken im Indexblock

30.06.2021

Betriebssysteme: 11 - Dateisysteme 13

●

●

Verschnitt bei kleinen Dateien Erweiterung nötig für große Dateien

Block 3

Block 8

Block 1

Block 9
   Indiziertes Speichern: UNIX-Inode

  direkt 0 direkt 1

direkt 9 einfach indirekt

zweifach indirekt

dreifach indirekt

Inode

Datenblöcke

           30.06.2021 Betriebssysteme: 11 - Dateisysteme

14

 ...
   Indiziertes Speichern: Diskussion

Einsatz von mehreren Stufen der Indizierung

Inode benötigt sowieso einen Block auf der Platte (Verschnitt unproblematisch bei kleinen Dateien)

durch mehrere Stufen der Indizierung auch große Dateien adressierbar

■

–

–

■

–

Nachteil:

mehrere Blöcke müssen geladen werden (nur bei langen Dateien)

 30.06.2021 Betriebssysteme: 11 - Dateisysteme 15
   Baumsequentielle Speicherung

Wird bei Datenbanken zum effizienten Auffinden eines Datensatzes mit Hilfe eines Schlüssels eingesetzt.

Schlüsselraum darf dünn besetzt sein.

■

–

■

–

z.B. NTFS, ReiserFS, Btrfs, IBMs JFS2-Dateisystem (B+-Baum)

9 21

9 < Block ≤ 21
17 20
Kann auch verwendet werden, um Datei-Chunks mit bestimmtem Datei-Offset aufzufinden
   Block ≤ 9
6 9
21 < Block
26 28
Indexblöcke
 25-26
 27-28
 -
 Bl. 25
 Bl. 27
  Bl. 26
 Bl. 28
     15-17
 18-20
 21
 Bl. 15
 Bl. 18
 Bl. 21
 Bl. 16
 Bl. 19
  Bl. 17
 Bl. 20
  5-6
 7-9
 -
 Bl. 5
 Bl. 7
  Bl. 6
 Bl. 8
   Bl. 9
        Chunks
mit Blöcken
   30.06.2021
Betriebssysteme: 11 - Dateisysteme
16
 
   Inhalt
Dateien
Freispeicherverwaltung Verzeichnisse
Dateisysteme
Pufferspeicher
Dateisysteme mit Fehlererholung Zusammenfassung
■ ■ ■ ■ ■ ■ ■
  30.06.2021 Betriebssysteme: 11 - Dateisysteme 17
 
   Freispeicherverwaltung
freie Blöcke mit Verweisen
freie Blöcke
Ähnlich wie Verwaltung von freiem Hauptspeicher
Bitvektoren zeigen für jeden Block Belegung an
oder verkettete Listen repräsentieren freie Blöcke
Verkettung kann in den freien Blöcken vorgenommen werden.
Optimierung: Aufeinanderfolgende Blöcke werden nicht einzeln am Stück verwaltet.
                                 ■ ■
– –
–
aufgenommen, sondern
■
– –
Optimierung: Ein freier Block enthält viele Blocknummern weiterer freier Blöcke, und evtl. die Blocknummer eines weiteren Blocks mit den Nummern freier Blöcke.
Baumsequentielle Speicherung freier Blockfolgen
Erlaubt schnelle Suche nach freier Blockfolge bestimmter Größe Anwendung z.B. im SGI XFS
 30.06.2021 Betriebssysteme: 11 - Dateisysteme 18
 
   Inhalt
Dateien
Freispeicherverwaltung Verzeichnisse
Dateisysteme
Pufferspeicher
Dateisysteme mit Fehlererholung Zusammenfassung
■ ■ ■ ■ ■ ■ ■
  30.06.2021 Betriebssysteme: 11 - Dateisysteme 19
 
   Verzeichnis als Liste
Einträge gleicher Länge hintereinander in einer Liste, z.B.
FAT File systems (VFAT nutzt mehrere Einträge für lange Dateinamen)
■
–
                    Name (8 Z.) Erweiterung (3 Z.)
Erstellungs- datum
letzter Zugriff
Länge Erster Datenblock
Letzte Änderung
Attribute
  ■
– –
Suche nach bestimmtem Eintrag muss linear erfolgen
Bei Sortierung der Liste: Schnelles Suchen, Aufwand beim Einfügen
–
UNIX System V.3
Probleme:
Inode- Nummer
Dateiname
(max. 14 Zeichen)
 30.06.2021 Betriebssysteme: 11 - Dateisysteme 20
 
   Einsatz von Hash-Funktionen
Funktion bildet Dateinamen auf einen Index in die Katalogliste ab
schnellerer Zugriff auf den Eintrag möglich (kein lineares Suchen)
■
–
■
Einfaches (aber schlechtes) Beispiel: ( ∑ Zeichen ) mod N
Verzeichnis- einträge
Dateiname
Index 0
           Hash-Funktion
(mehrere Dateinamen werden auf denselben Eintrag abgebildet)
  ■
Probleme:
– –
N-1
Kollisionen
Anpassung der Listengröße, wenn Liste voll
 30.06.2021 Betriebssysteme: 11 - Dateisysteme 21
 
   Variabel lange Listenelemente
Beispiel: 4.2 BSD, System V Rel. 4, u.a.
■
        Inode- Nummer
Länge des Name Namens
Offset zum nächsten gültigen Eintrag
...
 ■
– –
Verwaltung von freien Einträgen in der Liste Speicherverschnitt (Kompaktifizieren, etc.)
Probleme:
 30.06.2021 Betriebssysteme: 11 - Dateisysteme
22
 
   Inhalt
Dateien
Freispeicherverwaltung Verzeichnisse
Dateisysteme
Pufferspeicher
Dateisysteme mit Fehlererholung Zusammenfassung
■ ■ ■ ■ ■ ■ ■
  30.06.2021 Betriebssysteme: 11 - Dateisysteme 23
 
   UNIX System V File System
■
Blockorganisation
0 1 2
                     30.06.2021
Betriebssysteme: 11 - Dateisysteme
24
...
isize
Datenblöcke
(Dateien, Verzeichnisse, Indexblöcke)
...
  – –
Boot Block enthält Informationen zum Laden des Betriebssystems Super Block enthält Verwaltungsinformation für ein Dateisystem
●
●
●
Anzahl der Blöcke, Anzahl der Inodes
Anzahl und Liste freier Blöcke und freier Inodes Attribute (z.B. Modified flag)
Inodes Super Block
Boot Block
  
   BSD 4.2 (Berkeley Fast File System)
■
Blockorganisation
erste Zylindergruppe
Inodes Cylinder Group Block
Super Block Boot Block
zweite Zylindergruppe
Datenblöcke
                                 ■
– – –
Kopie des Super Blocks in jeder Zylindergruppe
Eine Datei wird möglichst innerhalb einer Zylindergruppe gespeichert. Verzeichnisse werden verteilt, Dateien eines V. bleiben zusammen
Vorteil: kürzere Positionierungszeiten
30.06.2021 Betriebssysteme: 11 - Dateisysteme 25
Zylindergruppe:
Zylindergruppe:
Menge aufeinanderfolgender
Menge aufeinanderfolgender
Zylinder (häufig 16)
Zylinder (häufig 16)
  
   Linux ext2/3/4 File System
Blockorganisation
erste Blockgruppe zweite Blockgruppe
Inodes Datenblöcke Bitmaps (freie Inodes u. Blöcke)
Group Descriptor
Super Block Boot Block
Ähnliches Layout wie BSD Fast File System Blockgruppen unabhängig von Zylindern
■
                                    – –
Blockgruppe: Blockgruppe:
Menge aufeinander
Menge aufeinander
folgender Blöcke
folgender Blöcke
 30.06.2021 Betriebssysteme: 11 - Dateisysteme 26
 
   Inhalt
Dateien
Freispeicherverwaltung Verzeichnisse
Dateisysteme
Pufferspeicher
Dateisysteme mit Fehlererholung Zusammenfassung
■ ■ ■ ■ ■ ■ ■
  30.06.2021 Betriebssysteme: 11 - Dateisysteme 27
 
   UNIX Block Buffer Cache
Pufferspeicher für Plattenblöcke im Hauptspeicher
Verwaltung mit Algorithmen ähnlich wie bei Seitenverwaltung (Speicher)
Read ahead: beim sequentiellen Lesen wird auch der Transfer von Folgeblöcken angestoßen
Lazy write: Block wird nicht sofort auf Platte geschrieben (erlaubt Optimierung der Schreibzugriffe und blockiert den Schreiber nicht)
Verwaltung freier Blöcke in einer Freiliste:
■
– –
–
–
●
●
Kandidaten für Freiliste werden nach LRU-Verfahren bestimmt
Bereits freie, aber noch nicht anderweitig benutzte Blöcke können reaktiviert werden (Reclaim)
 30.06.2021
Betriebssysteme: 11 - Dateisysteme 28
 
   UNIX Block Buffer Cache (2)
Schreiben erfolgt, wenn ...
keine freien Puffer mehr vorhanden sind,
regelmäßig vom System (fsflush-Prozess, update-Prozess),
beim Systemaufruf sync(),
und nach jedem Schreibaufruf im Modus O_SYNC (siehe open(2)).
■
– – – –
■
–
–
Adressierung:
Adressierung eines Blocks erfolgt über ein Tupel: (Gerätenummer, Blocknummer)
Über die Adresse wird ein Hash-Wert gebildet, der eine der möglichen Pufferlisten auswählt.
 30.06.2021 Betriebssysteme: 11 - Dateisysteme 29
 
   UNIX Block Buffer Cache: Aufbau
  30.06.2021 Betriebssysteme: 11 - Dateisysteme 30
 
   UNIX Block Buffer Cache: Aufbau (2)
  30.06.2021 Betriebssysteme: 11 - Dateisysteme 31
 
   Inhalt
Dateien
Freispeicherverwaltung Verzeichnisse
Dateisysteme
Pufferspeicher
Dateisysteme mit Fehlererholung Zusammenfassung
■ ■ ■ ■ ■ ■ ■
  30.06.2021 Betriebssysteme: 11 - Dateisysteme 32
 
   Dateisysteme mit Fehlererholung
Mögliche Fehler:
Stromausfall (ahnungsloser Benutzer schaltet einfach Rechner aus) Systemabsturz
■
– –
■
– –
■
–
■
– –
Auswirkungen auf das Dateisystem: inkonsistente Metadaten
z.B. Katalogeintrag fehlt zur Datei oder umgekehrt z.B. Block ist benutzt, aber nicht als belegt markiert
Reparaturprogramme
Programme wie chkdsk, scandisk oder fsck können inkonsistente Metadaten reparieren
Probleme:
Datenverluste bei Reparatur möglich
lange Laufzeiten der Reparaturprogramme bei großen Platten
 30.06.2021 Betriebssysteme: 11 - Dateisysteme 33
 
   Journaled File Systems
Zusätzlich zum Schreiben der Daten und Meta-Daten (z.B. Inodes) wird ein Protokoll der Änderungen geführt
Alle Änderungen treten als Teil von Transaktionen auf. Beispiele für Transaktionen:
Erzeugen, Löschen, Erweitern, Verkürzen von Dateien Verändern von Dateiattributen
Umbenennen einer Datei
Protokollieren aller Änderungen am Dateisystem zusätzlich in einer
■
– –
–
–
–
●
■
–
Protokolldatei (Log File) Bootvorgang
Abgleich der Protokolldatei mit den aktuellen Änderungen → Vermeidung von Inkonsistenzen
 30.06.2021 Betriebssysteme: 11 - Dateisysteme 34
 
   Journaled File Systems: Protokoll
Für jeden Einzelvorgang einer Transaktion wird zunächst ein Protokolleintrag erzeugt und ...
danach die Änderung am Dateisystem vorgenommen. Dabei gilt:
Der Protokolleintrag wird immer vor der eigentlichen Änderung auf Platte geschrieben.
Wurde etwas auf Platte geändert, steht auch der Protokolleintrag dazu auf der Platte.
■
■ ■
–
–
 30.06.2021 Betriebssysteme: 11 - Dateisysteme 35
 
   Journaled File Systems: Erholung
Beim Bootvorgang wird überprüft, ob die protokollierten Änderungen vorhanden sind:
Transaktion kann wiederholt bzw. abgeschlossen werden, falls alle Protokolleinträge vorhanden → Redo
Angefangene, aber nicht beendete Transaktionen werden rückgängig gemacht → Undo
■
–
–
 30.06.2021 Betriebssysteme: 11 - Dateisysteme 36
 
   Journaled File Systems: Ergebnis
Vorteile:
eine Transaktion ist entweder vollständig durchgeführt oder gar nicht
Benutzer kann ebenfalls Transaktionen über mehrere Dateizugriffe definieren, wenn diese ebenfalls im Log erfasst werden
keine inkonsistenten Metadaten möglich
Hochfahren eines abgestürzten Systems benötigt nur den relativ kurzen Durchgang durch das Log-File
■
– –
– –
■
–
■
●
Die Alternative chkdsk benötigt viel Zeit bei großen Platten.
Nachteile:
ineffizienter, da zusätzliches Log-File geschrieben wird
daher meist nur Metadata Journaling, kein Full Journaling Beispiele: NTFS, ext3/ext4, ReiserFS
●
 30.06.2021 Betriebssysteme: 11 - Dateisysteme 37
 
   Inhalt
Dateien
Freispeicherverwaltung Verzeichnisse
Dateisysteme
Pufferspeicher
Dateisysteme mit Fehlererholung Zusammenfassung
■ ■ ■ ■ ■ ■ ■
  30.06.2021 Betriebssysteme: 11 - Dateisysteme 38
 
   Zusammenfassung: Dateisysteme
... sind eine Betriebssystemabstraktion
Speicherung logisch zusammenhängender Informationen als Datei Meist hierarchische Verzeichnisstruktur, um Dateien zu ordnen
■
– –
■
– – –
■
–
–
●
zu klein → Verwaltungsstrukturen können zu Performance-Verlust führen
... werden durch die Hardware beeinflusst
Minimierung der Positionierungszeiten bei Platten Gleichmäßige „Abnutzung“ bei FLASH-Speicher Kein Buffer-Cache bei RAM-Disks
... werden durch das Anwendungsprofil beeinflusst
Blockgröße
zu groß → Verschnitt führt zu Plattenplatzverschwendung Aufbau von Verzeichnissen
●
●
●
keine Hash-Funktion → langwierige Suche
mit Hash-Funktion → mehr Aufwand bei der Verwaltung
 30.06.2021
Betriebssysteme: 11 - Dateisysteme 39
 
   Betriebssysteme (BS)
12. Systemsicherheit
https://sys.cs.tu-dortmund.de/DE/Teaching/SS2021/BS/
07.07.2021
Peter Ulbrich
peter.ulbrich@tu-dortmund.de
Basierend auf Betriebssysteme von Olaf Spinczyk, Universität Osnabrück
    
   Inhalt
Überblick über Sicherheitsprobleme Rechteverwaltung
Systemsoftware und Sicherheit Softwarefehler
Zusammenfassung
 ■ ■ ■ ■ ■
  07.07.2021 Betriebssysteme: 12 - Systemsicherheit 2
Tanenbaum
9: IT-Sicherheit
Silberschatz
14: Protection 15: Security
 
   Sicherheitsprobleme
Begriffsdefinition: Sicherheit
Safety
■
–
■
–
■
– –
–
Security
● ●
Schutz vor Risiken durch (Software-)Fehler, Störungen oder Ausfällen
Funktionale Sicherheit
● ●
Schutz von Menschen und Rechnern vor intendierten Fehlern (Angriffen)
Datensicherheit
Beide Themenbereiche sind für Systemsoftware relevant!
Im Folgenden: Fokus auf Security
 Ausnutzung von Sicherheitslücken
Schadsoftware („Malware“) Social Engineering
 07.07.2021 Betriebssysteme: 12 - Systemsicherheit 3
 
   Sicherheit in Betriebssystemen Jemanden ...
Unterscheidung von Personen und Gruppen von Personen
davon abhalten ...
durch technische und organisatorische Maßnahmen
einige ...
Begrenzung durch unser Vorstellungsvermögen
unerwünschte Dinge zu tun.
1) nichtautorisiertDatenlesen(Geheimhaltung,Vertraulichkeit),
2) nichtautorisiertDatenschreiben(Integrität),
3) unter„falscherFlagge“arbeiten(Authentizität),
4) nichtautorisiertRessourcenverbrauchen(Verfügbarkeit),
...
–
–
–
 07.07.2021 Betriebssysteme: 12 - Systemsicherheit 4
 
   Beispiel: Login-Attrappe
Angreifer startet Benutzerprogramm, das am Bildschirm einen Login-Screen simuliert
Der ahnungslose Benutzer tippt Benutzername und sein privates Passwort ein.
Angreiferprogramm speichert Benutzername und Passwort in Datei, terminiert aktuelles Shell-Programm
Login-Sitzung des Angreifers wird beendet und regulärer Login-Screen wird angezeigt
■
■
–
–
–
 ■
Abhilfe:
Login-Sequenz durch Tastensequenz starten, die von Benutzerprogramm nicht abgefangen werden kann
z.B. Strg-Alt-Entf bei Windows
–
NT und folgende.
 07.07.2021 Betriebssysteme: 12 - Systemsicherheit 5
 
   Beispiel: Virus
Programm, dessen Code an ein anderes Programm angefügt ist und sich auf diese Weise reproduziert
Virus schläft, bis infiziertes Programm ausgeführt wird Start des infizierten Programms führt zur Virusreproduktion Ausführung der Virusfunktion ist u.U. zeitgesteuert
■
– – –
■
–
–
–
■
Verbreitung durch Austausch von Datenträgern, E-Mails, Webseiten
Virus-Arten
Bootsektor-Viren: beim Systemstart
Linkviren: Ausführbares Programm als Virus
Makroviren: in skriptbaren Programmen wie Word, Excel
●
Durch Dokumente verbreitet!
 07.07.2021 Betriebssysteme: 12 - Systemsicherheit 6
 
   Beispiel: Social Engineering
Zugang zu Systemen durch Ausnutzung menschlicher Fehler
Kein Problem der Systemsoftware, aber immens wichtig
■
–
■
– –
■
– – –
Phishing
über gefälschte WWW-Adressen an Daten eines Internet-Benutzers gelangen z.B. durch gefälschte E-Mails von Banken
Pharming
Manipulation der DNS-Anfragen von Webbrowsern Umleitung von Zugriffen, z.B. auf gefälschte Bank-Webseiten Verdächtige Zertifikate werden von Nutzern meist ignoriert.
 07.07.2021 Betriebssysteme: 12 - Systemsicherheit 7
 
   Arten von „Schädlingen“ (1)
Viren
unabsichtliche Verbreitung „infizierter“ Programme/Dokumente Reproduktion: Einschleusen in andere Programme/Dokumente
■
– –
■
– – –
■
– –
Würmer
keine Anwender-„Unterstützung“ bei der Verbreitung in neue Systeme versuchen, aktiv in neue Systeme einzudringen
Ausnutzung von Sicherheitslücken auf Zielsystemen
Trojanische Pferde („Trojaner“)
Programm, das als nützliche Anwendung getarnt ist
ohne Wissen des Anwenders: Ausführen einer Schadfunktion,
z.B. Netzwerkzugang für den Angreifer
 07.07.2021 Betriebssysteme: 12 - Systemsicherheit 8
 
   Arten von „Schädlingen“ (2)
Rootkit
Sammlung von Softwarewerkzeugen, um ...
■
–
–
–
● ●
zukünftige Logins des Eindringlings verbergen Prozesse und Dateien zu verstecken
■
Oft treten Schädlinge als Kombination der vorgestellten Kategorien auf.
wird nach Einbruch in ein Computersystem auf dem kompromittierten System installiert
Versteckt sich selbst und seine Aktivitäten vor dem Benutzer
●
● ●
z.B. durch Manipulation der Werkzeuge zum Anzeigen von Prozessen (ps), Verzeichnisinhalten (ls), Netzwerkverbindungen (netstat) ...
... oder durch Manipulation von systemweiten shared libraries (libc) ... oder direkt durch Manipulation des Systemkerns
 07.07.2021 Betriebssysteme: 12 - Systemsicherheit 9
 
   Inhalt
Überblick über Sicherheitsprobleme Rechteverwaltung
Systemsoftware und Sicherheit Softwarefehler
Zusammenfassung
■ ■ ■ ■ ■
  07.07.2021 Betriebssysteme: 12 - Systemsicherheit 10
 
   Ziele der Rechteverwaltung
Schutz gespeicherter Information vor ...
Diebstahl (Verletzung der Vertraulichkeit) unerwünschter Manipulation (Verletzung der Integrität)
■
– –
■
–
... in allen Mehrbenutzersystemen
... und jedes am Internet angeschlossene System ist de facto ein Mehrbenutzersystem!
 07.07.2021 Betriebssysteme: 12 - Systemsicherheit 11
 
   Anforderungen
alle Objekte eines Systems müssen eindeutig und fälschungssicher identifiziert werden
(externer) Benutzer eines Systems muss eindeutig und fälschungssicher identifiziert werden
Authentifizierung
■
■
■
■
– –
➔
Zugriff auf Objekte sollte nur über zugehörige Objektverwaltung geschehen
Zugriff auf Objekte nur, wenn Zugreifer nötige Rechte hat
Rechte müssen fälschungssicher gespeichert werden Weitergabe von Rechten darf nur kontrolliert erfolgen
 07.07.2021 Betriebssysteme: 12 - Systemsicherheit 12
 
   Entwurfsprinzipien
Prinzip der geringst-möglichen Privilegisierung
(„principle of least privilege“)
Person oder Software-Komponenten nur die Rechte einräumen, die für die zu erbringende Funktionalität erforderlich sind
Verbot als Normalfall
Gegenbeispiel: Systemdienste mit „root-Rechten“ (Unix)
■
–
– –
■
–
■
–
Sichere Standardeinstellungen („secure defaults“)
Beispiel: neu installierte Server-Software
Separierung von Privilegien („separation of duties“)
mehrfache Bedingungen für die Zulassung einer Operation
 07.07.2021 Betriebssysteme: 12 - Systemsicherheit 13
 
   Zugriffsmatrix
Begriffe:
Subjekte (Personen, Prozesse)
Objekte (Daten, Geräte, Prozesse, Speicher ...) Operationen (Lesen, Schreiben, Löschen, Ausführen ...)
■
– – –
■
Frage: Ist Operation(Subjekt, Objekt) zulässig?
    Subjekt
Objekt
Rechte
 07.07.2021 Betriebssysteme: 12 - Systemsicherheit 14
 
   Basismodell: Datei-/Prozessattribute
Festlegungen in Bezug auf Benutzer:
Für welchen Benutzer arbeitet ein Prozess? Welchem Benutzer gehört eine Datei (owner)?
Welche Rechte räumt ein Benutzer anderen und sich selbst an „seiner“ Datei ein?
■
–
–
–
■
– –
Rechte eines Prozesses an einer Datei
Attribute von Prozessen: User ID Attribute von Dateien: Owner ID
User 1
User 3 User 4
 Datei 1
Datei 3
    07.07.2021 Betriebssysteme: 12 - Systemsicherheit
15
User 2
Datei 2
Read
 
   Varianten der Schutzmatrix
spaltenweise: ACL – Access Control List (Zugriffssteuerliste)
bei jedem Zugriff wird beim Objekt auf der Basis der Identität des Absenders dessen Berechtigung geprüft
■
–
■
–
■
–
zeilenweise: Capabilities (Zugriffsberechtigungen)
bei jedem Zugriff wird etwas geprüft, was Subjekte besitzen und bei Bedarf weitergeben können
regelbasiert: Mandatory access control
bei jedem Zugriff werden Regeln ausgewertet
 07.07.2021 Betriebssysteme: 12 - Systemsicherheit 16
 
   Access Control Lists (1)
Spaltenweise Darstellung: ACL – Access Control List
Festlegung für jedes Objekt, was welches Subjekt damit tun darf
■ ■
 Objekte
Rechte
  Subjekte
 07.07.2021
Betriebssysteme: 12 - Systemsicherheit 17
 
   Access Control Lists (2)
Setzen der ACLs darf:
Wer einen ACL-Eintrag für dieses Recht hat Erzeuger der Datei
■
– –
■
Beispiel Multics: Tripel (Nutzer, Gruppe, Rechte)
File 0 (Jan, *, RWX)
File 1 (Jan, system, RWX)
File 2 (Jan, *, RW-), (Els, staff, R--), (Maaike, *, RW-)
File 3 (*, student, R--)
File 4 (Jelle, *, ---), (*, student, R--)
Beispiel Windows (ab NT):
Pro Objekt eine Liste von Access Control Entries (ACEs)
Trustee (Nutzer oder Gruppe)
Rechte (jew. mit allow oder deny): full control, modify, read, execute, ...
■
– –
 07.07.2021 Betriebssysteme: 12 - Systemsicherheit 18
 
   Unix-Zugriffsrechte
Unix: rudimentäre Zugriffssteuerlisten
Prozess: User ID, Group ID
Datei: Owner, Group
Rechte in Bezug auf User (Owner), Group, Others
■
– – –
■
– –
Neuere Unix-Systeme implementieren auch ACLs
siehe get/setfacl (1)
Problem: Dateisystem-Integration, Kompatibilität mit Anwendungen
Dateiattribute:
rwx
 r--
   User: ulbrich
---
 Others
Group: staff
Ausführen (eXecute): Schreiben (Write): Lesen (Read):
ja/nein ja/nein ja/nein
  07.07.2021
Betriebssysteme: 12 - Systemsicherheit
19
vorlesung.tex
rw-
 
   Capabilities
Zeilenweise Darstellung der Schutzmatrix: Capability
Festlegung für jedes Subjekt, wie es auf welche Objekte zugreifen darf
Objekte
■ ■
  Subjekte
Rechte
  07.07.2021 Betriebssysteme: 12 - Systemsicherheit 20
 
   Capabilities: Beispiel
Rudimentäre Form: Unix-Dateideskriptoren Weitergabe durch fork-Systemaufruf
Ermöglicht Zugriff auf Dateien ohne erneute Prüfung der UNIX-Zugriffsrechte
■ ■
–
  07.07.2021 Betriebssysteme: 12 - Systemsicherheit 21
 
   Schutzmatrix regelbasiert
Mandatory Access Control (MAC): regelbas. Zugriffssteuerung
Konzept:
Subjekte und Objekte haben Attribute (labels) Entscheidung über Zugriff anhand von Regeln
■ ■
– –
■
Implementierung in sog. Sicherheitskernen, z.B. SELinux
   Subjekte
Objekte
Rechte
werden bei jedem Zugriff durch Regelwerk evaluiert
 07.07.2021
Betriebssysteme: 12 - Systemsicherheit 22
 
   Inhalt
Überblick über Sicherheitsprobleme Rechteverwaltung
Systemsoftware und Sicherheit Softwarefehler
Zusammenfassung
■ ■ ■ ■ ■
  07.07.2021 Betriebssysteme: 12 - Systemsicherheit 23
 
   Systemsoftware und Sicherheit
Schutz auf Hardware-Seite
MMU (Speicher) Schutzringe (CPU)
■
– –
■
–
... ergänzt durch Schutz auf Systemsoftware-Seite
Betriebssystem hat alleinige Kontrolle
–
Bereitstellung von
● ● ●
der Hardware
über alle Prozesse über alle Ressourcen
● ● ● ●
Identifikationsmechanismen Authentisierungsmechanismen Privilegseparation
Kryptographische Sicherung von Informationen
 07.07.2021
Betriebssysteme: 12 - Systemsicherheit 24
 
   Hardwarebasierter Schutz: MMU
Memory Management Unit
Hardwarekomponente der CPU, die Zugriff auf Speicherbereiche umsetzt und kontrolliert
Umsetzung von Prozess-Sicht (virtuelle Adressen) auf Hardware-Sicht (physische Adressen)
■
–
–
■ ■
–
– –
Einteilung des Hauptspeichers in Seiten (pages) Schutz durch ...
Einblendung nur der genau benötigten Menge an Speicherseiten des Hauptspeichers in den virtuellen Adressraum eines Prozesses
Isolation der physikalischen Adressräume unterschiedlicher Prozesse
Schutzbits für jede Seite, die bei jedem Zugriff kontrolliert werden
● ●
Lesen/Schreiben/Code ausführen Zugriff im User-Mode/Supervisor-Mode
 07.07.2021
Betriebssysteme: 12 - Systemsicherheit 25
 
   Schutzringe
Privilegienkonzept, hier in der x86-Variante
Ausführung von Code ist bestimmtem Schutzring zugeordnet Code in Ring 0 hat Zugriff auf alle Ressourcen des Systems User-Programme laufen in Ring 3
Ringe 1 u. 2 für BS-nahen Code
■
–
–
–
–
 ■
–
–
●
z.B. keine Interruptsperren in Ring>0

●

z.B. Gerätetreiber

Ringe schränken ein ...

den nutzbaren Befehlssatz des Prozessors

den zugreifbaren Adressbereich für den Prozess

●

Sperre von I/O-Zugriffen

 07.07.2021

Betriebssysteme: 12 - Systemsicherheit 26
   Softwarebasierter Schutz

Identifikationsmechanismen

Unix: Benutzeridentifikation, Gruppenidentifikation

Numerischer Wert

Übersetzung in Namen (Usernamen, Gruppennamen) durch Zuordnungstabellen

in /etc/passwd bzw. /etc/group

Ressourcen haben zugeordnete Besitzer

Superuser:uid = 0

Hat volle Rechte auf das System

■ ■

– –

■ ■

–

 07.07.2021 Betriebssysteme: 12 - Systemsicherheit 27
   Softwarebasierter Schutz

Authentifizierungsmechanismen

Beispiel: Unix login

Abfrage von Benutzernamen und Passwort

Verifikation des Passworts mit im System hinterlegtem Passwort

■

–

–

–

–

●

●

Entweder durch Verschlüsselung des eingegebenen Passworts und Vergleich mit dem hinterlegten verschlüsselten Wert

oder durch Verifikation eines Hash-Wertes

Der login-Prozess startet dann das erste Benutzerprogramm (z.B. eine Shell) mit der uid und gid, die zum eingegebenen Benutzernamen gehören.

   /sbin/getty

/usr/bin/login

login:

  uid=root uid=root uid=user 07.07.2021 Betriebssysteme: 12 - Systemsicherheit

28

/bin/bash

$_
   Softwarebasierter Schutz

Kryptographische Sicherung von Informationen

z.B. Passworte der Systembenutzer DES-verschlüsselt Ursprünglich in Unix: /etc/passwd

root:4t6f4rt3423:0:0:System Administrator:/var/root:/bin/sh daemon:ge53r3rfrg:1:1:System Services:/var/root:/usr/bin/false me:1x3Fe5$gRd:1000:1000:Michael Engel:/home/me:/bin/bash

Problem: verschlüsselte Passworte für alle Benutzer lesbar

■

– –

■

–

–

● ●

... und mit genügend Zeit auch durch „brute force“-Angriff zu knacken fertige Tools wie z.B. „John the Ripper“

Heute: Nur Benutzerinformationen in /etc/passwd

Passworte stehen separat in /etc/shadow!

-rw-r--r-- 1 root root 1353 May 28 22:43 /etc/passwd -rw-r----- 1 root shadow 901 May 28 22:43 /etc/shadow

 07.07.2021 Betriebssysteme: 12 - Systemsicherheit 29
   Inhalt

Überblick über Sicherheitsprobleme Rechteverwaltung

Systemsoftware und Sicherheit Softwarefehler

Zusammenfassung

■ ■ ■ ■ ■

  07.07.2021 Betriebssysteme: 12 - Systemsicherheit 30
   Softwarefehler

Trade-off: Performance ↔ Sicherheit

C, C++, Assembler: sogenannte „unmanaged“-Sprachen

u.a. Pointer, keine Prüfung von Arraygrenzen, Wertebereiche-Overflow

■ ■

–

■

– –

■

– –

■

Statistik: Durchschnittlich 1 Fehler pro 1000 Quellcodezeilen

C#, Java: „managed“-Sprachen

Für Systementwicklung leider i.d.R. ungeeignet.

In managed-Sprachen gibt es auch Probleme, z.B. mit Speicherlecks!

Häufige Probleme:

Pufferüberläufe Wertebereichsüberläufe

 07.07.2021 Betriebssysteme: 12 - Systemsicherheit 31
   Beispiel: Wertebereiche (1)

Problem: GanzzahlenwerdendurchBitstringsmit begrenzter Bitanzahl dargestellt

Beispiel: char in C

Wird als 8-Bit-Wert dargestellt

Wertebereich: -27 ... +27 – 1 ... oder -128 ... +127

■

■

– – –

 ■

– –

Die zugehörige binäre Berechnung sieht wie folgt aus (*):

Es sind nur die unteren 8 Bit signifikant

Ergebnis = -126!

 07.07.2021 Betriebssysteme: 12 - Systemsicherheit 32

char a = 127;

char b = 3;

char Ergebnis = a + b;

  01111111 (a)

+00000011 (b)

 10000010 (Ergebnis

           ist negativ!)

  (*) Überlauf bei Vorzeichen-behafteten Datentypen ist in C „undefined“, kann aber (*) Überlauf bei Vorzeichen-behafteten Datentypen ist in C „undefined“, kann aber

auf quasi allen gängigen Architekturen zu einem Wrap-Around (zum „negativen auf quasi allen gängigen Architekturen zu einem Wrap-Around (zum „negativen

Ende“ des Darstellungsbereichs) führen.

Ende“ des Darstellungsbereichs) führen.
   Beispiel: Wertebereiche (2)

Folgender Code führt zu Problemen:

■

 ■ ■

Bester Fall: Segmentation Fault

Schlimmer: Auslesen von „benachbarten“ Daten!

char string[127] = "Hallo Welt!\n"

char a = 127;

char b = 3;

...

char myfunc(char *string, char index) {

   return string[index];

}

...

printf("%x", myfunc(string, a+b));

 07.07.2021 Betriebssysteme: 12 - Systemsicherheit 33
   Inhalt

Überblick über Sicherheitsprobleme Rechteverwaltung

Systemsoftware und Sicherheit Softwarefehler

Zusammenfassung

■ ■ ■ ■ ■

  07.07.2021 Betriebssysteme: 12 - Systemsicherheit 34
   Fazit

Sicherheit in vernetzten Umgebungen immer relevanter

Extrem hoher Schaden durch Viren, Phishing, Botnets, Ransomware, ... Auch erfahrene Computerbenutzer sind nicht sicher!

■

– –

■

–

–

–

■

–

–

Sicherheitsüberprüfungen in Code unerlässlich

Automatisierte Tests finden nicht alle Fehler

Manuelle Audits sind weiterhin erforderlich

Dennoch sind Sicherheitsprobleme weiterhin häufig.

●

Systemsoftware muss also ständig aktualisiert werden.

„Hase-und-Igel“-Spiel

„Zero Day Exploits“, also neu entdeckte und nicht veröffentlichte Sicherheitslücken, sind extrem gefährlich.

Reaktionszeiten von Systemherstellern im Bereich von Stunden bis Monaten ...

 07.07.2021 Betriebssysteme: 12 - Systemsicherheit 35

Hallo Webbrowser

Hallo Webbrowser

Related Posts