Skript Betriebssysteme
Skript Betriebssysteme
Systemsoftware (GBS)
Johann Schlichter
Institut für Informatik
TU München, Munich, Germany
September 2015
Vorlesungsunterlagen
(Teacher Script1 )
1 Übersicht 2
1.1 Ziele der Vorlesung . . . . . . . . . . . . . . . . . . . . . . . . . 2
1.2 Motivation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3
1.2.1 Anforderungen an Rechensysteme . . . . . . . . . . . . . 4
1.2.2 Struktur eines Rechensystems . . . . . . . . . . . . . . . 7
1.3 Themen der Vorlesung . . . . . . . . . . . . . . . . . . . . . . . 9
1.3.1 Laufzeitmodell . . . . . . . . . . . . . . . . . . . . . . . 9
1.3.2 Inhaltsübersicht . . . . . . . . . . . . . . . . . . . . . . . 10
1.4 Literaturübersicht . . . . . . . . . . . . . . . . . . . . . . . . . . 11
1.4.1 Begleitend zur Vorlesung . . . . . . . . . . . . . . . . . . 12
1.4.2 Weiterführende Literatur . . . . . . . . . . . . . . . . . . 12
2 Einführung 14
2.1 Betriebssystem - Überblick . . . . . . . . . . . . . . . . . . . . . 14
2.1.1 BS-Hauptaufgaben . . . . . . . . . . . . . . . . . . . . . 15
2.1.2 Systemprogrammierung . . . . . . . . . . . . . . . . . . 19
2.1.3 Hardwarekomponenten . . . . . . . . . . . . . . . . . . . 20
2.1.4 Betriebsarten . . . . . . . . . . . . . . . . . . . . . . . . 21
2.1.5 Historie . . . . . . . . . . . . . . . . . . . . . . . . . . . 22
2.2 Betriebssystem-Architektur . . . . . . . . . . . . . . . . . . . . . 23
2.2.1 Monolithischer Ansatz . . . . . . . . . . . . . . . . . . . 23
2.2.2 Mikrokern-Ansatz . . . . . . . . . . . . . . . . . . . . . 26
2.2.3 Beispiel: BS-Architekturen . . . . . . . . . . . . . . . . . 27
2.2.4 Systemaufrufe . . . . . . . . . . . . . . . . . . . . . . . 30
i
Schlichter, TU München INHALTSVERZEICHNIS
ii
Schlichter, TU München INHALTSVERZEICHNIS
5 Speicherverwaltung 141
5.1 Fragestellungen . . . . . . . . . . . . . . . . . . . . . . . . . . . 141
5.2 Einführung . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 141
5.2.1 Adressräume . . . . . . . . . . . . . . . . . . . . . . . . 142
5.2.2 Organisation von Adressräumen . . . . . . . . . . . . . . 143
5.2.3 Fragmentierung . . . . . . . . . . . . . . . . . . . . . . . 150
5.2.4 Forderungen an Adressraumrealisierung . . . . . . . . . . 151
5.3 Speicherabbildungen . . . . . . . . . . . . . . . . . . . . . . . . 152
5.3.1 Direkte Adressierung . . . . . . . . . . . . . . . . . . . . 152
iii
Schlichter, TU München INHALTSVERZEICHNIS
6 Prozesskommunikation 184
6.1 Fragestellungen . . . . . . . . . . . . . . . . . . . . . . . . . . . 184
6.2 Einführung . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 185
6.2.1 Kommunikationsarten . . . . . . . . . . . . . . . . . . . 185
6.2.2 Verteilte Systeme . . . . . . . . . . . . . . . . . . . . . . 189
6.3 Nachrichtenbasierte Kommunikation . . . . . . . . . . . . . . . . 190
6.3.1 Elementare Kommunikationsmodelle . . . . . . . . . . . 190
6.3.2 Erzeuger-Verbraucher Problem . . . . . . . . . . . . . . . 196
6.3.3 Modellierung durch ein Petrinetz . . . . . . . . . . . . . . 196
6.3.4 Ports . . . . . . . . . . . . . . . . . . . . . . . . . . . . 197
6.3.5 Kanäle . . . . . . . . . . . . . . . . . . . . . . . . . . . 199
6.3.6 Ströme . . . . . . . . . . . . . . . . . . . . . . . . . . . 200
6.3.7 Pipes . . . . . . . . . . . . . . . . . . . . . . . . . . . . 200
6.4 Client-Server-Modell . . . . . . . . . . . . . . . . . . . . . . . . 204
6.5 Netzwerkprogrammierung . . . . . . . . . . . . . . . . . . . . . 207
6.5.1 Einführung . . . . . . . . . . . . . . . . . . . . . . . . . 207
6.5.2 Server Protokoll . . . . . . . . . . . . . . . . . . . . . . 208
iv
Schlichter, TU München INHALTSVERZEICHNIS
7 Dateisysteme 218
7.1 Fragestellungen . . . . . . . . . . . . . . . . . . . . . . . . . . . 218
7.2 Charakteristika von Dateisystemen . . . . . . . . . . . . . . . . . 219
7.3 Dateien . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 220
7.4 Memory-Mapped Dateien . . . . . . . . . . . . . . . . . . . . . . 223
7.5 Verzeichnisse . . . . . . . . . . . . . . . . . . . . . . . . . . . . 224
7.6 Schichtenmodell . . . . . . . . . . . . . . . . . . . . . . . . . . 225
7.6.1 Datenträgerorganisation . . . . . . . . . . . . . . . . . . 225
7.6.2 Blockorientiertes Dateisystem . . . . . . . . . . . . . . . 226
7.6.3 Dateiverwaltung . . . . . . . . . . . . . . . . . . . . . . 227
7.6.4 Virtuelles Dateisystem . . . . . . . . . . . . . . . . . . . 228
8 Ein-/Ausgabe 229
8.1 Klassifikation von E/A-Geräten . . . . . . . . . . . . . . . . . . . 229
8.2 Schichten eines E/A-Systems . . . . . . . . . . . . . . . . . . . . 230
8.3 Geräteverwaltung . . . . . . . . . . . . . . . . . . . . . . . . . . 232
8.3.1 Gerätetreiber . . . . . . . . . . . . . . . . . . . . . . . . 232
8.3.2 Geräteunabhängige E/A . . . . . . . . . . . . . . . . . . 234
8.4 RAID . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 238
8.5 Disk Scheduling . . . . . . . . . . . . . . . . . . . . . . . . . . . 240
8.6 Multimedia Systems . . . . . . . . . . . . . . . . . . . . . . . . 243
8.6.1 Zustellung von Mediendaten . . . . . . . . . . . . . . . . 243
8.6.2 Eigenschaften von Multimedia Systemen . . . . . . . . . 244
v
Schlichter, TU München INHALTSVERZEICHNIS
11 Zusammenfassung 276
vi
Schlichter, TU München INHALTSVERZEICHNIS
• Prof. J. Schlichter
1
Kapitel 1
Übersicht
Grundlagen der
Programmierung
Systemnahe Programmierung;
Betriebsysteme, verteilte Systeme
2
Schlichter, TU München 1.2. MOTIVATION
• Mit der rasanten Verbreitung des Internet und dessen Nutzung für private und
geschäftliche Transaktionen (E-Commerce und E-Business) steigt der Bedarf
an sicheren IT-Systemen. Der Abschnitt behandelt nach einigen verbreiteten Si-
cherheitslücken verschiedene Schutzmechanismen, wie Schutzmatrizen, Kryp-
tosysteme und Authentifizierungsmechanismen. Eine vertiefte Behandlung die-
ser Thematik erfolgt in verschiedenen Spezialvorlesungen zur IT-Sicherheit.
1.2 Motivation
Aufgabe der Informatik ist es, Rechensysteme zu entwickeln und diese Anwen-
dern als leistungsfähige Hilfsmittel für Lösungen ihrer Informationsverarbei-
tungsprobleme zur Verfügung zu stellen. Diese Aufgabe ist vielgestaltig, weit-
reichend, kompliziert und komplex; sie führt im Zuge der Weiterentwicklung von
Rechensystemen und im Zuge der wachsenden Nachfrage der Gesellschaft nach
Information fortwährend auf neue Fragestellungen, für die nach Antworten ge-
sucht werden muss. Sie hat zudem dazu geführt, dass sich große Bereiche der
Industrie und der Wirtschaft mit dieser Aufgabe befassen. Im folgenden werden
3
Schlichter, TU München 1.2. MOTIVATION
zunächst die wichtigsten Anforderungen, die mit der Entwicklung von Rechensy-
stemen erfüllt werden sollen, in Kürze genauer erklärt.
Offenes System
• R hat eine (offene) Schnittstelle, mit der Einwirkungen von U(R) auf R und
Einwirkungen von R auf U(R) möglich sind.
4
Schlichter, TU München 1.2. MOTIVATION
Umgebung
U(R)
Schnittstelle R - U(R)
Rechensystem R
– Außensicht vs. Innensicht. Die Außensicht, die von außen die Eigenschaften
der R-U(R) Schnittstelle zeigt, und die Innensicht, welche die inneren
Eigenschaften von R präsentiert.
– Black-box Sicht vs. White-box Sicht. 1
Das System ist ein schwarzer Kasten (black box): Das System wird als
einzelner Gegenstand aufgefasst. Das System ist ein weißer Kasten (white
box oder auch glass box): Für das Verständnis des Systems ist dessen
Zusammensetzung aus Komponenten wichtig.
– Sichten sind methodische Hilfsmittel für Systemanalysen:
∗ Komponenten haben Eigenschaften, die denen von Systemen entsprechen.
Dies bedeutet, Komponenten können für sich als Systeme betrachtet
werden.
∗ Verbindungen zwischen Komponenten beschreiben Abhängigkeiten zwi-
schen Komponenten.
∗ Rekursive Aufteilungen in Komponenten bzw. Sub-Komponenten liefern
verfeinerte White-box Sichten.
1
(siehe Informatik I, Brügge)
5
Schlichter, TU München 1.2. MOTIVATION
Dynamisches System
Technisches System
6
Schlichter, TU München 1.2. MOTIVATION
Wissen
Information Information
Repräsentation Interpretation
Daten Daten
Nachricht
Daten sind elementare Fakten, Aussagen und Sachverhalte. Sie sind leicht
zu strukturieren, leicht maschinell zu erfassen und leicht zu übertragen. Im
Zusammenhang mit der Übertragung spricht man auch gerne von Nachrichten.
Information sind Daten mit einer Bedeutung und einem Zweck; sie erfordert
Analyse, Konsens bzgl. Semantik und Interpretation. Die Semantic Web
(URL: [Link] Initiative versucht, die syntaktische Web-
Information um semantische Information zu ergänzen. Wissen ist Information
in einem bestimmten, für den Menschen relevanten Kontext; es ist schwierig,
Wissen zu strukturieren, schwierig maschinell zu erfassen und zu verarbeiten.
Weiterhin ist es schwierig Wissen zu übertragen, da es oft nur implizit existiert
(siehe auch das neue Forschungsgebiet Wissensmanagement bzw. "Knowledge
Management").
2
2
Unterscheidung zwischen implizites und explizites Wissen.
7
Schlichter, TU München 1.2. MOTIVATION
Anwendungs-
Datenbank World Wide Web Email programme
Betriebssystem
Maschinensprache
In dieser Vorlesung werden wir uns besonders mit Aspekten der technischen
Informatik beschäftigen, und zwar mit den Systemprogrammen (Betriebssysteme,
Assembler, Kommunikation in verteilten Systemen) sowie der Schnittstelle zu
der darunter liegenden Hardware. Die Vorlesung ist als eine Einführung in
diesen Bereich zu interpretieren; eine detailliertere Behandlung von Hardware,
Systemprogramme und verteilte Systeme erfolgt in weiterführenden Vorlesungen.
Mikroprogramme dienen zur Realisierung der Maschinensprache; bei RISC-
Rechnern (z.B. Sun Workstation) sind die Mikroprogramme oft festverdrahtet.
8
Schlichter, TU München 1.3. THEMEN DER VORLESUNG
Dabei werden vor allem Strukturen, Abläufe und Dienste von Betriebssyste-
men betrachtet. Der Fokus liegt auf nicht verteilte Systeme. Im Zusammen-
hang mit der Prozesskommunikation wird auch ein Ausblick auf verteilte Sy-
steme gegeben. Dienste sind Softwareeinheiten, die bestimmte Funktionali-
täten bereitstellen. Ablauf ist eine Abfolge von Aktivitäten/Operationen. Als
Teil eines Ablaufs können die Operationen eines Dienstes aufgerufen werden.
Ablauf hat einen Zeitbezug.
1.3.1 Laufzeitmodell
Bereitstellung eines indirekten Zugangs zur Rechnerhardware über eine Dienst-
schicht. 3 Ziel dieser Schicht ist die Realisierung einer virtuellen Maschine.
Virtualisierung kann sowohl zur Fehlervermeidung als auch zur Reduktion der
Komplexität eingesetzt werden.
9
Schlichter, TU München 1.3. THEMEN DER VORLESUNG
1.3.2 Inhaltsübersicht
Im einzelnen werden in der Vorlesung die folgenden Themen behandelt:
10
Schlichter, TU München 1.4. LITERATURÜBERSICHT
Programmiersprachen
– entwickelt zwischen 1969 und 1973 von Dennis Ritchie bei Bell Labs
– C und Unix sind eng miteinander verbunden
– C ist eine einfache, kleine Sprache
– C war und ist noch eine wichtige Sprache für systemnahe Programmierung
– C bedingt jedoch einige Fehleranfälligkeiten, z.B.
dynamische Speicherbelegung und -freigabe. (malloc, free)
Pointerarithmetik. (Addieren einer ganzen Zahl zu einem Pointer)
1.4 Literaturübersicht
Literatur, die als Basis für die Vorlesung verwendet wird.
11
Schlichter, TU München 1.4. LITERATURÜBERSICHT
• Elliote Rusty Harold, "Java Network Programming", O’Reilly, 2013 (seit 2009
auch als eBook Kindle erhältlich)
4
2010 ist eine Variante erschienen als " Operating System Concepts with Java Operating
System Concepts with Java" (8. Edition).
12
Schlichter, TU München 1.4. LITERATURÜBERSICHT
13
Kapitel 2
Einführung
14
Schlichter, TU München 2.1. BETRIEBSSYSTEM - ÜBERBLICK
2.1.1 BS-Hauptaufgaben
Ein Betriebssystem (engl. operating system) erfüllt folgende Hauptaufgaben:
– Ressourcenklassen
Ein Rechensystem kann als strukturierte Sammlung von Ressourcenklassen
betrachtet werden, wobei jede Klasse durch Dienste des Betriebsystems
kontrolliert wird. 2
15
Schlichter, TU München 2.1. BETRIEBSSYSTEM - ÜBERBLICK
16
Schlichter, TU München 2.1. BETRIEBSSYSTEM - ÜBERBLICK
Benutzerprozess
Ausführung System Rückkehr von
Benutzermodus
Benutzerprozess Aufruf System Aufruf
Betriebssystemkern
Ausführung
Systemmodus
Systemdienst
• Struktureller Aufbau
17
Schlichter, TU München 2.1. BETRIEBSSYSTEM - ÜBERBLICK
System- Benutzer-
Prozesse Z
Prozesse
u
g
Betriebssystem-Schnittstelle a
n
g
Prozess
s
verwaltung
k
o
Speicher Datei
n
verwaltung system
t
r
o
Scheduler & EA- l
Dispatcher System l
e
Unterbrechungs-
System
Hardware
Konfiguration
Aus dem strukturellen Aufbau sind auch die wichtigsten Aufgaben und Funk-
tionen eines Betriebssystems ersichtlich. Dabei ist auch festzulegen, welche
Dienste im Betriebssystemkern und welche Dienste über Systemprozesse reali-
siert werden.
18
Schlichter, TU München 2.1. BETRIEBSSYSTEM - ÜBERBLICK
3
volunteers.
2.1.2 Systemprogrammierung
Die Programmierung eines Betriebssystems gehört zu dem Bereich der System-
programmierung.
• Definition
Die Systemprogrammierung befasst sich mit der Darstellung, der Realisierung,
den Eigenschaften und der Konstruktion derjenigen Algorithmen für ein
Rechensystem, die die Bearbeitung und Ausführung von Benutzerprogrammen
unter vorgegebenen Qualitätsgesichtspunkten organisieren, d.h. steuern und
kontrollieren, und zum Teil selbst durchführen.
direkte Nutzung der generischen Systemprogrammierschnittstelle des BS.
meist in Programmiersprache C.
generischen Systemprogrammierschnittstelle bedeutet eine allgemeine Schnitt-
stelle, d.h. alle Applikationen haben die gleiche Schnittstelle; im Gegensatz zu
anwendungsspezifischen Schnittstellen.
19
Schlichter, TU München 2.1. BETRIEBSSYSTEM - ÜBERBLICK
2.1.3 Hardwarekomponenten
Das Betriebssystem ist sehr eng mit der Hardware des Rechensystems verknüpft,
auf dem es ausgeführt wird. Es erweitert den Befehlssatz des Rechners und
verwaltet seine Ressourcen.
Deshalb an dieser Stelle einen kurzen Überblick über den Aufbau eines
Rechensystems. (Detaillierte Erklärungen zum Aufbau von Rechensystemen
wurden in der Vorlesung Einführung in die Technischen Grundlagen behandelt.)
Als Beispiel wird hier kurz der Aufbau eines Intel PC’s präsentiert. Daraus erkennt
man, dass ein Rechner unterschiedlicher Bussysteme mit unterschiedlichen
Geschwindigkeiten integriert. Daneben gibt es noch weitere Busse wie SCSI für
den Anschluss Festplatten und anderen Geräten, sowie IEEE 1394 - Firewire für
den Anschluss von Multimedia Geräten z.B. digitale Kamera.
Systembus Speicherbus
USB (Maus,
Tastatur)
AGP
EA-Karte
Grafik
PCI Bus
EA-Karte
Sound
IDE
Festplatte
Southbridge
ISA Bus
EA-Karte
LAN Drucker
20
Schlichter, TU München 2.1. BETRIEBSSYSTEM - ÜBERBLICK
2.1.4 Betriebsarten
Beim Betrieb von Rechenanlagen können bzgl. des Zusammenwirkens von Be-
nutzer und Rechensystem die Betriebsweisen Stapelverarbeitung, Dialogbetrieb,
Transaktionsbetrieb und Echtzeitbetrieb unterschieden werden.
• Stapelbetrieb
Das Rechensystem verarbeitet Ströme von Auftragspaketen (engl. batch pro-
cessing). Ein Benutzer deklariert vollständig alle Teile eines Auftragspaketes,
bevor es in das System eingegeben wird. Anschließend wird das Auftragspa-
ket durch das Rechensystem abgearbeitet, ohne dass der Benutzer noch Ein-
flussmöglichkeiten hat. Bei Auftreten eines Fehlers muss i.a. nach der Korrektur
das gesamte Auftragspaket nochmals gestartet werden. Auftragspakete können
in Unterabschnitte zerfallen, z.B. Teilprogrammabläufe. Diese Betriebsart war
in den Anfängen von Rechenanlage sehr verbreitet (Nutzung von Lochkarten
und Lochstreifen).
• Dialogbetrieb
Im Dialogbetrieb (engl. Timesharing) erteilt der Benutzer dem Betriebssystem
einen Auftrag nach dem anderen im Dialog. Innerhalb eines Benutzerauftrags
findet eine Interaktion zwischen dem Benutzer und der Systemumgebung
statt (z.B. Eingabe weiterer Daten, Ausgabe von Zwischenergebnissen). Der
Dialogbetrieb erfordert eine besondere Gestaltung der Benutzerschnittstelle.
Oft wird Betriebssystem und Benutzerschnittstelle (engl. user interface) in
einem Atemzug genannt und auch oft gleichgesetzt. Beide sind jedoch getrennt
voneinander zusehen. Beispielsweise existierten mit dem X11-Windowsystem
und Sun Windowsystem (auf der Basis von Postscript) zwei unterschiedliche
Benutzerschnittstellen auf demselben Betriebssystem.
21
Schlichter, TU München 2.1. BETRIEBSSYSTEM - ÜBERBLICK
• Transaktionsbetrieb
Bewältigung einer Vielzahl von kleinen Aufgaben in kürzester Zeit, z.B.
Banküberweisungen oder Buchungen. Dabei muss die Bearbeitung folgende
Kriterien, wie sie auch von Datenbanken bekannt sind, erfüllen: Atomarität,
Konsistenz, Isolation, Dauerhaftigkeit (engl. ACID), d.h. die Bearbeitung muss
entweder vollständig ablaufen oder keinerlei Änderung verursachen (Alles-
oder-nichts Prinzip).
• Echtzeitbetrieb
In der Prozesssteuerung (automatische Fertigungssysteme, Roboter) und im
Multimediabereich sind die Reaktionszeiten des Betriebssystems von großer
Bedeutung. Dies erfordert spezielle Mechanismen bei der Behandlung von
Ereignissen und Unterbrechungen sowie der CPU-Zuteilung an rechenbereite
Prozesse / Threads. Beispielsweise ein Videoserver (bei Nutzung des Streaming
Ansatzes) benötigt ein Betriebssystem, das gewisse Echtzeitfähigkeiten hat.
Videos müssen mit einer bestimmten Geschwindigkeit abgespielt werden. Die
Bilder dürfen an das Abspielprogramm nicht zu langsam (ansonsten ruckelt
das Videobild) und nicht zu schnell ausgeliefert werden (sonst gehen bei
Pufferüberlauf Videobilder verloren). Unterscheidung zwischen
harte Echtzeitsysteme: Reaktionszeit darf nicht überschritten werden. Eine
zu späte Reaktion kann zu ernsthaften Problemen führen, z.B. bei der
Steuerung eines Atomreaktors.
weiche Echtzeitsysteme: gewisse Toleranzen bzgl. der Abweichung
sind erlaubt. Bei Audio und Multimedia-Systemen werden gewisse
Abweichungen von der Reaktionszeit toleriert.
2.1.5 Historie
Betriebssysteme haben sich über die Jahre hinweg ständig weiterentwickelt.
Faktoren für die Entwicklung von Betriebssystemen:
Fortschritte der Hardwaretechnologie.
Preis - Leistungs - Verhältnis.
Übergang von numerischer Berechnung zur allgemeinen
Informationsverarbeitung.
neue Anwendungsbereiche und Öffnung für Nichspezialisten. Ein Beispiel
ist die Nutzung von Rechnern als eingebettete Systeme im Auto sowie ihre
Nutzung in Mobiltelefonen oder Smartphones.
22
Schlichter, TU München 2.2. BETRIEBSSYSTEM-ARCHITEKTUR
(nur Steuerung der Ein-/Ausgabe, es wird deshalb auch nicht als Betriebssystem
bezeichnet). Ein Benutzer hatte den Rechner für sich. Die Programmierung
erfolgte in Maschinensprache. Lochkarten und Lochstreifen brachten eine
gewisse Verbesserung. Beispielrechner sind die Zuse Z3, ENIAC, oder die
PERM an der TUM.
2.2 Betriebssystem-Architektur
In der Praxis findet man einige verschiedene BS-Architekturkonzepte, wobei der
monolithische Ansatz und zunehmend auch der Mikrokern-Ansatz am weitesten
verbreitet sind.
23
Schlichter, TU München 2.2. BETRIEBSSYSTEM-ARCHITEKTUR
Anwendung Anwendung
Benutzerprozess Benutzerprozess
Benutzer-Modus
(User Mode)
System-Modus
Systemdienste (Kernel Mode)
(Hauptprozedur)
Hilfs
funktionen
Hardware
• Geschichtete Systeme
24
Schlichter, TU München 2.2. BETRIEBSSYSTEM-ARCHITEKTUR
Anwendungen
Funktionsschnittstelle
Schicht N
abstrakte Maschine N
Funktionsschnittstelle
Schicht N-1
abstrakte Maschine N - 1
Funktionsschnittstelle
Schicht 0
abstrakte Maschine 0
Rechnerhardware
25
Schlichter, TU München 2.2. BETRIEBSSYSTEM-ARCHITEKTUR
2.2.2 Mikrokern-Ansatz
Der Trend moderner Betriebssystem geht hin zu einem Mikrokern-Ansatz.
Im Mikrokern sind nur mehr Basismechanismen, z.B. Prozesskommunikation
(Austausch von Nachrichten), CPU-Zuteilung. Möglichst viele Subsysteme
sind als Systemprozesse außerhalb des Mikrokerns realisiert. Sie laufen im
Benutzermodus ab, z.B. Dateisystem, Speicherverwaltung. Verwaltungsdienste,
z.B. Strategien zur Speicherverwaltung oder Prozessverwaltung (z.B. Zuteilung
von Prioritäten) laufen im Benutzermodus. Man spricht im Zusammenhang
mit diesem Ansatz auch von einer Client/Server-Struktur. Systemfunktionen
werden als Serverprozesse im Benutzermodus ausgeführt. Benötigt ein Prozess
(Client) eine Dienstleistung schickt er eine Anforderung an einen anderen
Prozess (Server), der die Dienstleistung erfüllt und die Antwort an den Client
zurückgibt. Die Kommunikation zwischen den beteiligten Prozessen erfolgt über
den Mikrokern. Durch die Ausgliederung in Serverprozesse ist eine Trennung von
Mechanismus und Strategie möglich. Die Strategien werden in Serverprozessen
im Benutzermodus realisiert, während der Mikrokern wenige Basismechanismen
umfasst. Ziel ist, das der BS-Kern nur für kurze Zeit blockiert sein soll.
Einfaches Austauschen von Subsysteme ⇒ ermöglicht die einfache Anpas-
sung von Systemanforderungen.
Anforderung System-Modus
(Kernel Mode)
Mikrokern
Antwort
Hardware
26
Schlichter, TU München 2.2. BETRIEBSSYSTEM-ARCHITEKTUR
Bibliotheken Benutzungs-
Programme Shells
(z.B. lib.a) schnittstelle
Systemschnittstelle Programmier-
u.a. open,close, read, write; fork, exec, kill, ... schnittstelle
Hardware
Windows NT Betriebssystem
27
Schlichter, TU München 2.2. BETRIEBSSYSTEM-ARCHITEKTUR
Logon
OS/2 Client Win32 Client Posix Client Applications
Process
Protected
OS/2 Posix Subsysteme
Subsystem Subsystem (Servers)
Security Win32
Subsystem Subsystem
Systemaufrufe
Kernel Mode
System Services
I/O Manager
Local Virtual
Object Security Process NT Executive
Procedure Memory File
Manager Manager Manager
Call Facility Manager Systems
Cache Mgr
Device
Kernel Drivers
Network
Drivers
Hardware Abstraction Layer (HAL)
Hardware Manipulation
Hardware
28
Schlichter, TU München 2.2. BETRIEBSSYSTEM-ARCHITEKTUR
Linux Betriebssystem
Linux begann Anfang der 1990er Jahre als eine Unix Variante für den IBM PC;
erste Version durch Linus Torvalds (1991).
Linux ist frei und Quellcode ist verfügbar.
kollaborative Weiterentwicklung durch Open Source Community.
29
Schlichter, TU München 2.2. BETRIEBSSYSTEM-ARCHITEKTUR
Traps Physical
Interrupt
faults memory
Network interface
CPU Main memory terminal disk
controller
Signals: Aufruf eines Prozesses durch den Kernel (z.B. um Prozess von einem
Fehler zu unterrichten (Division durch 0).
2.2.4 Systemaufrufe
Die Schnittstelle zwischen dem Betriebssystem und den Benutzerprogrammen
wird durch eine Menge von Systemaufrufen (engl. system calls) gebildet. Sie
stellen für Benutzerprogramme die einzige Schicht zum Zugriff auf Dienste des
Betriebssystems and damit zur Nutzung der Hardware dar.
30
Schlichter, TU München 2.2. BETRIEBSSYSTEM-ARCHITEKTUR
(z.B. glibc bei Linux) gelinkt, bevor es ausgeführt wird. Die Aufgabe dieser
Bibliothek ist es, Standard-C-Aufrufe in Systemaufrufe umzusetzen.
main ( ) {
--------------
printf ("hello“); Anwendung
--------------
}
Benutzermodus
-------------
printf erledigt Formatierung
-------------- Bibliotheksfunktion
Systemaufruf
-------------
write (1, "hello“, 5); Betriebssystemkern
Systemmodus
--------------
Hardware
Z.B. Zugriff auf Festplatte
31
Schlichter, TU München 2.2. BETRIEBSSYSTEM-ARCHITEKTUR
Gast-Betriebssystem Gast-Betriebssystem
(free BSD) (Windows XP)
Virtualisierungsschicht
Host Betriebssystem
(Linux)
Hardware
CPU Arbeitsspeicher E/A-Geräte
In diesem Fall ist Linux ist das native Host-Betriebssystem. Die Virtualisierungs-
schicht abstrahiert die physikalische Hardware zu isolierten virtuellen Maschinen,
auf denen jeweils Gast-Betriebssysteme laufen.
Die Java Virtual Machine (JVM) spezifiziert einen abstrakten Computer, auf dem
Java Programme ausgeführt werden. JVM ist ein Softwaresystem, das auf dem
Host-Betriebssystem ausgeführt wird.
32
Schlichter, TU München 2.3. HARDWARENAHE PROGRAMME
2.3.1 Definitionen
Maschinenschnittstelle
• Folge von Maschinenbefehlen ist auf dieser Ebene eine Folge von Binärzeichen.
Auf dieser Ebene müsste man insbesondere die Befehle der Maschine als reine
Folge von Binärzeichen (Befehlswörter) schreiben; diese Schnittstelle ist sehr
programmier-unfreundlich.
Assemblerschnittstelle
Assembler
33
Schlichter, TU München 2.3. HARDWARENAHE PROGRAMME
2.3.2 Programmaufbereitung
Wir wollen eine grobe Vorstellung der Funktion eines Assemblers, Binders und
Laders vermitteln. Binder/Lader sind i.d.R. Bestandteil des Betriebssystems. Hier
steht nicht die Konstruktion solcher Komponenten (Systemprogrammierung),
sondern deren Aufgaben und Funktionen im Vordergrund.
Programm
Assembler
Programm
Assembler
Bindemodul Bindemodul
Maschinenbefehle mit
relativen Adressen Lader
Maschinenprogramm im
Arbeitsspeicher
Aufruf:
unix> gcc -o hello hello.c
34
Schlichter, TU München 2.3. HARDWARENAHE PROGRAMME
relocatable object
program (Binary)
printf.o
hello linker
(ld)
executable
object program
(Binary)
Transformation in 4 Phasen
35
Schlichter, TU München 2.3. HARDWARENAHE PROGRAMME
Binder
Der Binder (engl. linker) hat die Aufgabe, aus einer Menge von einzelnen
Bindemoduln ein ausführfähiges Ladeprogramm zu erzeugen, indem die noch
offenen externen Referenzen aufgelöst werden.
• Binde-Module
Der Assembler erzeugt Code, der jeweils relativ zum Modul-Anfang adressiert.
assemblieren
– Externe Referenzen
In einem Modul Mi können Referenzen auf Daten/Symbole auftreten, wobei
die Daten/Symbole in einem anderen Modul Mj definiert werden. Beispiel:
Symbol start wird in Segment 1 verwendet, und erst in Segment n definiert.
36
Schlichter, TU München 2.3. HARDWARENAHE PROGRAMME
37
Schlichter, TU München 2.3. HARDWARENAHE PROGRAMME
Lader
Ein Lader (engl. loader) ist ein Systemprogramm, das die Aufgabe hat,
Objektprogramme in den Speicher zu laden und deren Ausführung anzustoßen.
• Eigenschaften
In einem System ist i.d.R. nur ein Lader vorhanden, so dass Programme
unterschiedlicher Quellsprachen in ein einheitliches Objektprogramm-Format
transformiert werden müssen.
38
Schlichter, TU München 2.3. HARDWARENAHE PROGRAMME
Der Binder benötigt eine Tabelle ESTAB ("external symbol table") für die
aufzulösenden externen Referenzen, wenn im Programm externe Referenzen
auftreten. Der Tabelleneintrag besteht aus [Symbol, Adresse]. ESTAB hat analoge
Aufgaben wie die Symboltabelle des Assemblers. Der Tabelleneintrag beinhaltet
u.U. auch den Modul, in dem das Symbol definiert ist.
• Hilfsvariable
39
Schlichter, TU München 2.3. HARDWARENAHE PROGRAMME
Dynamisches Binden
Binden von Unterprogrammen erst zur Laufzeit, d.h. erst wenn sie das erste Mal
aufgerufen werden. Als Vorteile ergeben sich folgende:
40
Schlichter, TU München 2.3. HARDWARENAHE PROGRAMME
41
Kapitel 3
3.1 Fragestellungen
• Sequentielle Aspekte von systemnaher Programmierung:
42
Schlichter, TU München 3.1. FRAGESTELLUNGEN
43
Schlichter, TU München 3.2. GRUNDLAGEN
3.2 Grundlagen
In diesem Teilabschnitt werden kurz die wichtigsten Begriffe definiert sowie
Konzepte zur Formulierung paralleler Aktivitäten aufgelistet. Einige dieser
Konzepte werden in nachfolgenden Teilabschnitten ausführlicher diskutiert.
3.2.1 Begriffsdefinitionen
Nebenläufigkeit
• z.B. zeitlich verzahnt: Benutzerauftrag muss CPU abgeben und wartet; ein
anderer Auftrag wird (teilweise) ausgeführt und gibt CPU wieder zurück, bevor
das Ende erreicht ist. Hier spricht man auch von Pseudoparallalität. Für einen
Benutzer sieht es so aus, als ob Dinge gleichzeitig passieren.
Parallelität
Verteiltheit
Verteilheit (engl. distribution) ist die räumliche oder auch nur konzeptionelle
Aufteilung der Komponenten eines Systems, z.B. vernetzte PCs. Die Verteilung
kann sich sowohl auf der Ebene der HW-Komponenten als auch auf der Daten-
und Anwendungsebene abspielen.
44
Schlichter, TU München 3.2. GRUNDLAGEN
Interaktion
Nichtdeterminismus
45
Schlichter, TU München 3.2. GRUNDLAGEN
3.2.2 Beschreibungskonzepte
Es gibt eine Vielzahl von Konzepten zur Formulierung paralleler Aktivitäten.
In der Vorlesung werden wir uns vor allem mit den beiden modell-basierten
Ansätzen, Ereignisse und Petrinetze befassen. Es gibt auch noch andere
Modellansätze (z.B. bei Rechnernetzen), z.B. formale Beschreibungssprachen
(Estelle, LOTOS), die z.T. auf Prozessalgebren basieren. Eine andere Möglichkeit
sind parallele Programmiersprachen.
modell-basierte Konzepte
Sprachkonstrukte in Programmiersprachen
Konzepte in Betriebssystemen
46
Schlichter, TU München 3.3. MODELLIERUNG PARALLELER SYSTEME
3.3.1 Modellierungsziele
Ziel ist die einfache Analyse und Beschreibung von parallelen Systemen.
47
Schlichter, TU München 3.3. MODELLIERUNG PARALLELER SYSTEME
3.3.2 Verhaltensbeschreibung
Verhaltensbeschreibungen eines dynamischen Systems sind Beschreibungen der
Eigenschaften des Systems und deren Veränderungen über der Zeit. Das Verhalten
eines Systems kann mit Spuren in einem 2-dimensionalen Raum beschrieben
werden:
Die 1. Dimension ist die Zeit, mit der das Fortschreiten der Ausführung der
Berechnungen erfasst wird, d.h. hier geht es um die Folge von Ausführungen
von elementaren Aktionen, die jeweils Ereignisse auslösen.
Die 2. Dimension ist der Raum der Eigenschaften des Systems, mit dem die
Systemzustände in Zeitpunkten erfasst werden. Zu Zeitpunkten wird jeweils
ein Schnappschuss des Systemzustands genommen. Über die Zeitachse wird
eine Folge von Zuständen angegeben, die sich mit der Ausführung der
Aktionen (Berechnungen) ergibt.
48
Schlichter, TU München 3.3. MODELLIERUNG PARALLELER SYSTEME
– Die Sicht auf die Tätigkeiten, die auszuführen sind; in dieser Sicht
sind die Basiseinheiten die atomaren Aktionen. Eine Aktion kann ein
Maschinenbefehl oder eine Java Anweisung sein.
– Die Sicht auf die Veränderungen, die erfolgen und beobachtet werden
können; in dieser Sicht sind die Basiseinheiten die atomaren Ereignisse,
die eintreten. Die Ausführung einer Aktion führt zu einem Ereignis im
Rechensystem. Aktionen und Ereignisse sind dual zueinander und können
nach Bedarf genutzt werden; hier wird überwiegend die Ereignissicht
benutzt. Aktionen können mehrfach ausgeführt werden; sie resultieren in
mehrfachen Ereignissen.
Beispiel: Aktion - Knopf drücken; Ereignis - die Ampel ist rot.
• Zustände des Systems anhand der Werte der Datenobjekte. Folge von
Zuständen gemäß der Zeitachse. Jedem Zeitpunkt wird der Zustand der
Datenobjekte, der mit dem Zeitpunkt erreicht ist, zugeordnet. Für jeden
Zeitpunkt wird damit ein Schnappschuss vom System angegeben; über der
Zeitachse wird die Folge der Zustände angegeben, die sich mit der Ausführung
der Berechnungen ergibt.
• Spuren
Es sind zwei Varianten von Verhaltensbeschreibungen zweckmässig.
49
Schlichter, TU München 3.3. MODELLIERUNG PARALLELER SYSTEME
Prozess
Gegeben seien eine Menge (das "Universum") E* von Ereignissen (engl. events)
und eine Menge A von Aktionen (engl. actions).
• Definition
Ein Triple p = (E, ≤, α) nennen wir einen Prozess oder auch eine
Aktionsstruktur, falls folgende Aussagen gelten:
• Beispiel: Fußgängerübergang
Wir betrachten einen Prozess mit 14 Ereignissen. Jedem Ereignis werden
Aktionen zugeordnet.
50
Schlichter, TU München 3.3. MODELLIERUNG PARALLELER SYSTEME
Ereignis Aktion
e1 Knopf wird gedrückt
e2 Ampel für Autofahrer schaltet auf Gelb
e3 Ampel für Autofahrer schaltet auf Rot
e4 Auto hält auf Spur 1
e5 Ampel für Fußgänger schaltet auf Grün
e6 Auto hält auf Spur 2
e7 Fußgänger benutzt Fußgängerübergang
e8 Auto hält auf Spur 3
e9 Ampel für Fußgänger schaltet auf Rot
e10 Ampel für Autofahrer schaltet auf Rot und Gelb
e11 Ampel für Autofahrer schaltet auf Grün
e12 Auto fährt an auf Spur 1
e13 Auto fährt an auf Spur 2
e14 Auto fährt an auf Spur 3
e15 Knopf wird gedrückt
Die Ausführung einer Aktion löst ein Ereignis aus. Wird dieselbe Aktion
mehrmals ausgeführt, so wird jeweils ein neues Ereignis ausgelöst (siehe e1
und e15).
51
Schlichter, TU München 3.3. MODELLIERUNG PARALLELER SYSTEME
e6 e13
e1 e2 e3 e4 e12
e8 e14
e9 e10 e11
e5 e7 e15
– Parallel, nebenläufig
Für einen Prozess p = (E, ≤, α) nennen wir zwei Ereignisse e1, e2 ∈ E
parallel oder nebenläufig (engl. concurrent), falls sie im Prozess p nicht in
einer kausalen Relation stehen, d.h. wenn gilt:
¬(e1 ≤ e2 oder e2 ≤ e1)
∗ Parallele Ereignisse sind kausal unabhängig, sie können zeitlich nebenein-
ander oder in beliebiger Reihenfolge stattfinden.
– Sequentiell
Ein Prozess p = (E, ≤, α) heißt sequentiell, wenn in ihm kein Paar von
parallelen Ereignissen auftritt, d.h. die Kausalitätsrelation ≤ eine lineare
Ordnung ist. Damit gilt für zwei beliebige Ereignisse e1 und e2 stets
entweder e1 ≤ e2 oder e2 ≤ e1.
– Der Ablauf eines Programmes kann auch als Prozess im Sinne der
Aktionsstrukturen gedeutet werden. Sequentielle Programme erzeugen
sequentielle Prozesse.
– Endlich
Ein Prozess p = (E, ≤, α) heißt endlich, falls seine Ereignismenge
eine endliche Menge ist. Beispielsweise ist das Abspielen einer CD ein
endlicher Prozess, während ein Betriebssystem einen unendlichen Prozess
52
Schlichter, TU München 3.3. MODELLIERUNG PARALLELER SYSTEME
Kausale Abhängigkeiten
– Beispiel
e = Geldeinwurf, d = Kartenausgabe; e ≤ d, d.h. der Fahrkartenautomat gibt
erst dann eine Fahrkarte aus, wenn der passende Geldbetrag eingeworfen
wurde.
• zeitliche Beziehungen
das Ereignis e endet, bevor das Ereignis d beginnt.
– Beispiel: Nachricht muss gesendet sein, bevor sie empfangen werden kann.
Zeitliche Beziehungen können, aber müssen nicht echt kausal sein. Auto 1
fährt auf Spur 1, Auto 2 fährt eine Minute später auf Spur 2; es gibt eine
zeitliche Beziehung, jedoch keine kausale Beziehung.
– Happend-before
Die kausale Beziehung impliziert also eine zeitliche Relation; das ist die
bekannte happened before-Beziehung von L. Lamport. Die Umkehrung
gilt nicht. Die zeitliche Relation zwischen Ereignissen sagt nichts über die
Kausalität aus.
∗ Wichtig: Ereignisse wurden als atomare Ereignisse modelliert. D.h.
Beginn und Ende fallen auf einen Zeitpunkt zusammen. Ein alternativer
Ansatz wäre die Spezifikation eines Zeitintervalls für ein Ereignis mit
Anfangs- und Endzeitpunkt. Damit könnten auch Überlappungen von
Ereignissen modelliert werden.
∗ Die Happend-before Relation spielt im Kontext von Verteilten Anwendun-
gen eine wichtige Rolle (siehe Vorlesung Verteilte Anwendungen (URL:
[Link] Insbesondere in der
53
Schlichter, TU München 3.3. MODELLIERUNG PARALLELER SYSTEME
• Systembeschränkungen
Systembeschränkungen, z.B. wechselseitiger Ausschluss. Das Ereignis e darf
nicht parallel zum Ereignis d auftreten.
– Beispiel
e = Fußgänger überquert die Fahrbahn beim Übergang, und
d = Auto überfährt den Übergang.
e und d dürfen nicht parallel ausgeführt werden, aber es besteht keine ech-
te kausale Abhängigkeit zwischen e und d. Ereignisse, welche mit Aktionen
markiert sind, die aufgrund von Systembeschränkungen nicht parallel statt-
finden können, sind nicht unbedingt in einem "echt" kausalen Zusammen-
hang. Trotzdem sollten sie nicht als parallele Ereignisse auftreten. Um diese
Systembeschränkungen mit den eingeführten Modellierungskonzepten (un-
interpretierte Aktionen) zu erfassen, müssten sie in eine (künstliche) kausale
Abhängigkeit gebracht werden; das ist aber meist nicht sehr sinnvoll. Wir
werden später sinnvollere Möglichkeiten kennen lernen.
Sequentialisierung
Idee: vereinfachte Darstellung paralleler Abläufe, aus der Sicht eines Beobachters.
Ein sequentieller Prozess hat genau eine vollständige Sequentialisierung, nämlich
die vorgegebene Reihenfolge der Ereignisse. Durch α ergibt sich aus der
Ereignisreihenfolge eine Folge von Aktionen. Vollständige Sequentialisierung:
partielle Kausalitätsordnung zu linearer Ordnung ergänzen.
• Definition
Ein Prozess p1 = (E1, ≤1, α1) heißt eine Sequentialisierung eines Prozesses p2
= (E2, ≤2, α2), falls gilt:
E1 = E2
∀ e, d ∈ E1: e ≤2 d ⇒ e ≤1 d
α1 = α2
54
Schlichter, TU München 3.3. MODELLIERUNG PARALLELER SYSTEME
• Ein sequentieller Beobachter eines Prozesses ist ein Beobachter, der die
Ereignisse eines Prozesses und die entsprechenden Aktionen in einem
sequentiellen Ablaufprotokoll festhält. Parallele Aktionen werden dabei in
eine zufällige Reihenfolge gebracht. Das Ergebnis der Beobachtung ist
ein sequentieller Prozess, der einer zufällig gewählten Sequentialisierung
entspricht. Gehen wir von sequentiellen Beobachtern aus, so erhalten wir
sequentielle Prozesse als Beobachtungen.
• Beispiel
Für das Beispiel des Fußgängerübergangs ist folgendes eine vollständige
Sequentialisierung.
e1 e2 e3 e4 e6 e5 e7 e8 e9
• Spuren
Darstellung sequentieller Prozesse mittels Spuren. Sequentielle Prozesse sind
Spezialfälle paralleler Prozesse. Für die Darstellung sequentieller Prozesse
bietet sich eine wesentlich einfachere Darstellungsform als Aktionsstrukturen.
Wir können ganz auf die explizite Angabe von Ereignismengen verzichten und
stattdessen endliche oder unendliche Sequenzen von Aktionen verwenden.
– Sei A eine Menge von Aktionen, dann bezeichnen wir mit A+ die Menge
der endlichen Folgen von Aktionen aus A und mit A∞ die Menge der
unendlichen Folgen von Aktionen.
55
Schlichter, TU München 3.3. MODELLIERUNG PARALLELER SYSTEME
– Jedem sequentiellen Prozess können wir eindeutig eine Folge von Aktionen
zuordnen, wie sprechen von der Spur (engl. trace). Sei p = (E, ≤, α) ein
sequentieller Prozess. Wir definieren:
∗ spur : {p | p ist sequentieller Prozess } → A+ ∪ A∞
∗ spur(p) = empty, falls E = Ø
∗ spur(p) = <a> · spur(p | E \ {e}), falls E 6= Ø, wobei e das gemäß der
Kausalitätsordnung kleinste Ereignis in p ist und α(e) = a gilt.
p | E \ {e} bezeichnet den Teilprozess, der durch die Einschränkung
auf die Ereignismenge E \ {e} entsteht.
"·" ist hier die Konkatenation von Aktionen, die sich durch die Ereignisse
ergeben. spur ist eine Abbildung auf die Menge der Aktionen. Als Ergebnis
liefert spur einen Strom (engl. stream) von Aktionen.
– Für einen nichtsequentiellen Prozess p gilt:
Spuren(p) = {spur(q) : Prozess q ist eine vollständige Sequentialisierung
von p}
Spuren sind ein einfacheres Modell für sequentielle Abläufe eines Systems
als Aktionsstrukturen. Da bei nichtsequentiellen Systemen in vielen Anwen-
dungen die Frage, welche Aktionen parallel zueinander auftreten können,
von untergeordneter Bedeutung ist, ist es naheliegend für solche Systeme
vereinfachend statt ihrer nebenläufigen Prozesse deren Sequentialisierungen
als Abläufe zu betrachten. In vielen Ansätzen zur Modellierung verteilter Sy-
steme werden nicht Prozesse mit ihrer expliziten Darstellung von Parallelität,
sondern die technisch etwas einfacher zu handhabenden Mengen von Akti-
onsströmen verwendet.
Interpretierte Aktionen
56
Schlichter, TU München 3.3. MODELLIERUNG PARALLELER SYSTEME
Modell
• Zustandsautomat
Ein nichtdeterministischer Zustandsautomat ist gegeben durch:
• Beispiel Fahrkartenautomat
Akzeptiert werden 1- und 2 DMark Münzen. Mittels zweier Knöpfe kann man
zwischen einer Kurzstrecke für 1 DM oder einer normalen Fahrt für 2 DM
wählen. Der Automat gibt Wechselgeld zurück.
57
Schlichter, TU München 3.3. MODELLIERUNG PARALLELER SYSTEME
Wn Wk
(normal, 2) (Wahl, 0)
E2
An Ak
E1
E1 E1
(normal, 1) (normal, 0) (kurz, 0) (kurz, 1)
E2 R1 R1 R1
E2
An Ak
(normal, -1) (Wahl, -1) (kurz, -1)
• Aktionsspur
Jedem Zustandsautomaten lassen sich ausgehend von der gegebenen Menge
von Anfangszuständen Spuren zuordnen.
– Definition
Gegeben sei ein Zustandsautomat Z = (S, A, R, S0). Eine Folge ai, wobei 1
≤ i ≤ k mit k ∈ IN ∪ {∞}, ist eine endliche oder unendliche Aktionsspur
des Zustandsautomaten, falls eine Folge von Zuständen si existiert, mit si ∈
S, s1 ∈ S0 und
58
Schlichter, TU München 3.3. MODELLIERUNG PARALLELER SYSTEME
Konflikte
59
Schlichter, TU München 3.3. MODELLIERUNG PARALLELER SYSTEME
nicht ohne Konflikte nebeneinander ausgeführt werden. Wir sagen, dass diese
Aktionen im Konflikt miteinander sind. Sollen beispielsweise zwei Anweisungen
an die gleiche Programmvariable x parallel ausgeführt werden, so lässt sich dem
entsprechenden Prozess keine Zustandsänderungsabbildung eindeutig zuordnen.
In beiden Aktionen soll die Programmvariable x geändert werden. Die Aktionen
sind im Konflikt.
• Beispiel
Mögliche Konflikte bei parallel durchzuführenden Zuweisungen. Wir betrach-
ten die Aktionen, die den folgenden beiden Zuweisungen entsprechen:
(1) x = x + 1
(2) x = 2 * x
Die Zuweisungen stehen im Konflikt zueinander.
• Störungsfreiheit
Frage: Gibt es Kriterien, um auf einfache Weise solche Konflikte zu erkennen,
so dass sie durch eine Reihenfolgeregelung gelöst werden können? Die Frage
kann mit ja beantwortet werden; es gibt Kriterien, und zwar die Bernstein-
Bedingungen.
– Vorbereitung
Für eine Transitionsaktion a gelte:
V(a) ⊆ S ist Vorbereich, d.h. die Menge der gelesenen Zustandsvariablen.
60
Schlichter, TU München 3.3. MODELLIERUNG PARALLELER SYSTEME
3.3.5 Petri-Netze
Ein Prozess beschreibt einen möglichen Ablauf eines verteilten Systems. Ver-
teilte Systeme besitzen viele Abläufe, d.h. ein System wird durch die Men-
ge von Abläufen beschrieben. Gesucht wird deshalb ein Modell zur Beschrei-
bung von Systemen und deren möglichen Abläufen. Drei Vertreter solcher For-
malismen sind Petri-Netze (graphische Beschreibungsmethode), Agenten (for-
male Beschreibungssprache, siehe Broy Band II) und prädikatenlogische For-
meln zur Beschreibung von Abläufen. Im folgenden werden Petri-Netze (URL:
[Link] vorgestellt, die eine graphen-orientierte
Beschreibung verteilter Systeme und deren Abläufen ermöglicht.
Allgemeines
Formalismus von C.A. Petri 1962 entwickelt. Ansatz führte zu einer Theorie zur
Analyse und Entwicklung nebenläufiger Systeme.
61
Schlichter, TU München 3.3. MODELLIERUNG PARALLELER SYSTEME
• informelle Charakterisierung
Ein Petri-Netz ist gerichteter Graph mit Kanten und zweierlei Knoten.
62
Schlichter, TU München 3.3. MODELLIERUNG PARALLELER SYSTEME
Bestell- Auslieferung
aufnahme
Bestellung Lieferauftrag Waren
Produktions-
Produktion Lager
auftrag
Definition: Petri-Netz
• Mit obiger Definition ist die statische Struktur eines Netzes formal erfasst. Die
graphische Darstellung wurde bereits anhand des obigen Beispiel gezeigt.
• Für das Beispiel Materialverwaltung gilt beispielsweise:
·Bestellaufnahme = {Bestellung}
Bestellaufnahme· = {Produktionsauftrag, Lieferauftrag}
63
Schlichter, TU München 3.3. MODELLIERUNG PARALLELER SYSTEME
• Verfeinerung
Netzstrukturen können schrittweise verfeinert, konkretisiert werden. Wichtig:
Globale Struktur muss bei Verfeinerung erhalten bleiben, d.h. alle Kanten in
eine verfeinerte Transition und alle Kanten aus dieser verfeinerten Transition
bleiben erhalten. Die innere Struktur der Transition kann wiederum in
Stellen, Transitionen und Kanten aufgeschlüsselt werden. Die zu verfeinernde
Transition kann nach außen hin als Blackbox gesehen werden.
– Beispiel
Verfeinerung der Materialverwaltung: z.B. der Komponente Auslieferung.
Anhand des Lieferauftrages wird der Lieferschein geschrieben, der zusam-
men mit dem Produkt verpackt und versandt wird.
Lieferschein-
erstellung Versenden
Lieferauftrag
Lieferschein Waren
Lager verpackte
Verpacken Produkte
Auslieferung
Auslieferung ist nach außen hin eine Transition. Dies bedeutet, dass die
Eingangskanten von Auslieferung jeweils zu einer Transition führen müssen.
Zur Erfassung des dynamischen Verhaltens erweitern wir die Definition eines
Petri-Netzes zunächst um Markierungen und geben dann die Schaltregeln an.
• Markierung
Gegeben sei ein Petri-Netz (S, T, F).
64
Schlichter, TU München 3.3. MODELLIERUNG PARALLELER SYSTEME
– Eine Abbildung c: S → IN ∪ {∞} gibt die Kapazität einer Stelle an. Wenn
in den von uns verwendeten Netzen die Stellen nicht explizit markiert sind,
dann bedeutet dies eine unbeschränkte Kapazität.
– Eine Abbildung w: F → IN ∪ {0} gibt die Gewichtung einer Kante an. Wenn
in den von uns verwendeten Netzen die Kanten nicht explizit markiert sind,
dann bedeutet dies eine implizite Gewichtung mit dem Gewicht 1.
– Eine Abbildung M: S → IN heißt natürlichzahlige Markierung der Stellen.
Die Markierung beschreibt einen Zustand des Netzes.
Es muss gelten: ∀ s ∈ S: M(s) ≤ c(s)
Ein solches Netz heißt Stellen-Transitionsnetz
– Falls gilt M: S→ IB, mit IB = {0, 1}, dann heißt das Netz: Bedin-
gungs/Ereignisnetz oder Boolesches Netz. Demnach entsprechen Boolsche
Petri-Netze natürlichzahligen Petri-Netzen, bei denen jede Stelle die Kapazi-
tät 1 hat (oder einen boolschen Wert mit true (=1) bzw. false (=0) hat). Eine
Transition t kann nur dann schalten, wenn alle Stellen, zu denen Kanten von
t aus führen, mit false markiert sind.
• Schaltregeln
Das Verhalten eines Netzes wird durch Schaltvorgänge beschrieben. Gegeben
sei ein Petri-Netz (S, T, F), die Funktionen c, w und eine Anfangsmarkierung
M0.
65
Schlichter, TU München 3.3. MODELLIERUNG PARALLELER SYSTEME
besagt, dass eine Transition nur schalten kann, wenn in ihren Eingangsstellen
mindestens soviele Marken liegen, wie die Gewichtung der jeweiligen
Kanten angibt und wenn außerdem gewährleistet ist, dass durch das Schalten
die Kapazität ihrer Ausgangstellen nicht überschritten wird. Durch das
Schalten werden entsprechend der Kantengewichtung Marken von allen
Eingangstellen abgezogen und ebenfalls entsprechend der Gewichtung
Marken den Ausgangstellen hinzugefügt.
– Beispiel: Schalten einer Transition
Gegeben sei eine Kantengewichtungsfunktion w, die jede Kante mit 1
gewichtet, also
w: F → 1
3 3
2 2
66
Schlichter, TU München 3.3. MODELLIERUNG PARALLELER SYSTEME
ein Markenüberfluss vor. Die Transition t1 kann nicht schalten, da auf der
Stelle s4 bereits ein Token liegt und damit die Kapazität der Stelle (1)
bereits erschöpft ist. Durch ein Schalten würde ein weiteres Token der Stelle
hinzugefügt werden und die Kapazität überschreiten.
s1 t1 s3 s1 t1 s3
s4 Kapazität 1
s2 s2 s4
2 2
Animation Petrinetz
siehe online Version
Nebenläufigkeit
Mit Petri-Netzen lassen sich nebenläufige Systeme auf einfache Weise modellie-
ren. Betrachten wir zum Beispiel vier Aktivitäten t1, ... , t4, wobei jede Aktivität
durch eine Transition modelliert wird. Nach Beendigung von t1 (z.B. Einlesen von
Eingabewerten) können t2 (z.B. Berechne ggt) und t3 (z.B. Berechne Fibonacci)
nebenläufig aktiv sein, aber sie müssen beide beendet sein, bevor t4 ausgeführt
wird.
t2
t1 t4
t3
• Nichtdeterminismus
67
Schlichter, TU München 3.3. MODELLIERUNG PARALLELER SYSTEME
– Beispiel
Erzeuger/Verbraucher mit Konfliktbelegung. Nach dem nebenläufigen
Schalten der Transitionen a und b des Netzes (siehe Situation oben) ergibt
sich eine Konfliktbelegung (siehe Situation unten), in der nur entweder die
Transition c oder die Transition d schalten kann.
nebenläufiges
a c e d b
Schalten
Erzeuger Verbraucher
Konflikt
a c e d b belegung
bzgl c und d
Für ein gegebenes Petri-Netz, das das Verhalten eines verteilten Systems
modelliert, sind wir daran interessiert, zu klären, ob das System bei gegebener
Anfangsmarkierung bestimmte Eigenschaften besitzt. Eigenschaften sind die
Erreichbarkeit und die Lebendigkeit.
• Erreichbarkeit
Häufig ist man an der Frage interessiert, ob das Netz ausgehend von einer
Markierung M irgendwann eine Folgemarkierung M’ erreicht. Das ist die Frage
der Erreichbarkeit von Zuständen.
68
Schlichter, TU München 3.3. MODELLIERUNG PARALLELER SYSTEME
– Erreichbare Markierung
Gegeben sei ein Petri-Netz (S, T, F) mit der Markierung M. Eine endliche
Sequenz ρ = t1, t2, ..., tn mit ti ∈ T heißt von M aktivierte endliche
Schaltfolge, wenn Markierungen M1, M2, ..., Mn existieren mit
t1 t2 tn
M M1 M2 Mn d.h. M Mn
Aufgabe: Das System ist so zu konstruieren, dass sich niemals beide Züge
auf derselben Strecke befinden.
Lösung: Die Strecken werden mit Stellen s1, ... , s4 modelliert. Eine
Marke auf der Stelle si bedeutet, dass ein Zug auf der i-ten Strecke fährt.
Durch die zusätzlichen Kontrollstellen k1, .. , k4 soll garantiert werden,
dass in keiner erreichbaren Markierung mehr als eine Marke auf einer der
Stellen si liegt. ki kontrolliert den Zugang zur Strecke si (Stelle).
s1
t4 t1
k1
s4 k4 k2 s2 Bahnnetz
k3
t3 t2
s3
Der Graph zeigt jeweils einen Zug auf Strecke s2 und s4.
69
Schlichter, TU München 3.3. MODELLIERUNG PARALLELER SYSTEME
t4 t2 Erreichbarkeitsgraph
t3 t1
s1, k2, s3, k4
t1 t3
Die Zustände werden durch die Menge der markierten Stellen in einer
erreichbaren Markierung beschrieben. Der Erreichbarkeitsgraph zeigt, dass
kein Zustand ereichbar ist, in dem mehr als eine Marke, also mehr als ein
Zug, auf einer Stelle si liegt. Damit ist die gewünschte Eigenschaft korrekt
modelliert.
Die Frage, ob es einen Algorithmus gibt, der entscheidet, ob eine Markierung
aus einer gegebenen Anfangsmarkierung aus erreichbar ist oder nicht,
(Entscheidbarkeit des Erreichbarkeitsproblems), war ca. 10 Jahre lang offen.
Prof. E.W. Mayr hat die Entscheidbarkeit 1980 in seiner Dissertation (an der
TUM) bewiesen. Aber: der Algorithmus besitzt sehr hohe Komplexität, er ist
nicht effizient durchführbar.
• Lebendigkeitseigenschaften
Wie zu Beginn des Kapitels bereits erwähnt, verwendet man System-
modelle häufig, um Lebendigkeitseigenschaften zu analysieren. Stellen-
Transitionsnetze werden oft in Bereichen verwendet, in denen es auf die An-
zahl und die Verteilung veränderlicher Objekte ankommt. (z.B. Daten in einem
Rechner, Waren in einem Lager, Werkstücke). Man ist daran interessiert zu er-
kennen, ob es in einem System zu Blockierungen kommen kann, so dass Teile
des Systems blockiert sind oder der gesamte Ablauf zum Stillstand kommt.
Ursachen für solche Situationen sind Mangel oder Stau, der durch die verän-
derlichen Objekte ausgelöst wird.
– Netzdarstellung
aktive Systemelemente als Transitionen (Prozessor, Maschine, etc.)
passive Systemteile als Stellen (Speicher, Lager, etc.)
veränderliche Objekte als Marken
Für Lebendigkeitsuntersuchungen sind Netzteile interessant, die niemals
markiert werden oder die niemals ihre Marken verlieren.
70
Schlichter, TU München 3.3. MODELLIERUNG PARALLELER SYSTEME
– Definition
Gegeben sei ein Petri-Netz (S, T, F) mit der Anfangsmarkierung M0.
∗ Das Netz heißt lebendig, wenn für jede erreichbare Markierung M und für
jede Transition t ∈ T eine Markierung M’ existiert, die aus M erreichbar ist
und in der t transitionsbereit ist. Informell: jede Transition t kann immer
wieder irgendwann einmal schalten.
∗ Die von M0 aus erreichbare Markierung M beschreibt eine vollständige
Verklemmung (eng. deadlock), wenn es keine Transition t ∈ T gibt, die
unter M schalten kann.
∗ Die von M0 aus erreichbare Markierung M beschreibt eine lokale
Verklemmung, wenn es eine Transition t ∈ T gibt, so dass ausgehend von
M keine Folgemarkierung M’ erreichbar ist, in der t transitionsbereit ist.
∗ Ist (S, T, F) mit Anfangsmarkierung M0 lebendig, dann ist es auch
verklemmungsfrei. Lebendige Netze stellen sicher, dass es weder zu einem
Markenmangel noch zu einem Überfluss kommt. Die Eigenschaft der
Lebendigkeit eines Netzes ist insbesondere für Systeme, die für einen
Endlosbetrieb ausgelegt sind (z.B. Betriebssysteme) wichtig.
– Beispiel: Lebendiges Netz
Lösung: Das System besteht aus 3 Zellen, die jeweils eine Nachricht
aufnehmen können (die Stellen repräsentieren die Speicherzellen). Die
Transition t1 modelliert das Eingeben einer neuen Nachricht und die
Transition t4 modelliert die Ausgabe der Nachricht. Mit den Transitionen
ti werden die Nachrichten von Zelle si-1 zur Zelle si weitergereicht.
Voraussetzung ist, dass die entsprechende Zelle leer ist. Der Zustand "Zelle
si ist leer", wird durch die markierte Stelle ki modelliert.
Das modellierte Netz ist verklemmungsfrei und lebendig. Falls der FIFO
Puffer in ein größeres System eingebunden ist, müssen die Transition t1 (für
die Eingabe von Nachrichten) und t4 (für die Ausgabe von Nachrichten) in
das Gesamtsystem integriert werden.
71
Schlichter, TU München 3.3. MODELLIERUNG PARALLELER SYSTEME
k1 k2 k3
t1 t2 t3 t4
s1 s2 s3
Eingabe einer Ausgabe einer
Nachricht Nachricht
– Beispiel: Verklemmung
2 Studenten benötigen ein 2-bändiges Lehrbuch. Student 1 leiht sich zunächst
nur Band 1 aus und Student 2 leiht sich vorsorglich den noch vorhandenen
Band 2 aus. Bevor Student 1 seinen ersten Band zurückgibt, möchte er noch
den zweiten ausleihen. Auch Student 2 gibt seinen ausgeliehenen Band nicht
zurück, sondern versucht, den ersten Band auszuleihen.
∗ Vor der Ausleihe
Anfangszustand des Netzes vor der Ausleihe. Die nachfolgende Abbildung
zeigt zunächst das Netz, bevor einer der Studenten ein Buch ausleiht
und die zweite Abbildung zeigt das Netz, nachdem die Studenten die
jeweiligen Bände ausgeliehen haben.
72
Schlichter, TU München 3.3. MODELLIERUNG PARALLELER SYSTEME
Band 1 Band 2
ausleihen ausleihen
Band 2 Band 1
ausleihen ausleihen
73
Schlichter, TU München 3.4. THREAD-KONZEPT
Band 1 Band 2
ausleihen ausleihen
Band 2 Band 1
ausleihen ausleihen
• Weitere Eigenschaften
Weitere interessante Eigenschaften - nur ganz informell - sind
– Fairness
Gegeben sei ein Netz N mit Anfangsmarkierung M. Das Netz ist unfair für
eine Transition t, wenn es eine unendliche Sequenz gibt, in der t nur endlich
oft auftritt, obwohl t unendlich oft transitionsbereit ist.
– Verhungern
t verhungert (engl. Starvation): Es gibt eine unendliche Sequenz, in der die
Transition t niemals auftritt. Falls unfaire Sequenz: trotz Transitionsbereit-
schaft von t.
3.4 Thread-Konzept
Threads sind ein BS-Konzept für die Modellierung und Realisierung von
nebenläufigen Aktionen in einem Rechensystem. Threads (Kontrollflüsse) 2
beschreiben die Aktivitäten in einem Rechensystem. Sie können als virtuelle
2
[nehmer2001 S97]
74
Schlichter, TU München 3.4. THREAD-KONZEPT
Prozessoren aufgefasst werden, die jeweils für die Ausführung eines zugeordneten
Programms in einem Adressraum verantwortlich sind. Threads konkurrieren um
die physische CPU, um ablaufen zu können. In traditionellen Umgebungen hat
jeder Prozess genau einen Thread, der den Kontrollfluss des Prozess repräsentiert,
während in Multithreaded-Umgebungen ein Prozess mehrere Threads besitzen
kann.
Prozess
Benutzer
Adressraum
Thread Thread
Betriebssystem
Motivation
Ein Thread ist die Abstraktion eines physischen Prozessors; er ist ein Träger einer
sequentiellen Aktivität. Gründe für die Einführung von Threads:
75
Schlichter, TU München 3.4. THREAD-KONZEPT
• Threadspezifische Information
Jeder Thread umfasst eine Reihe von Informationen, die seinen aktuellen
Zustand charakterisieren:
Befehlszähler, aktuelle Registerwerte, Keller, Ablaufzustand des Thread.
Ebenso wie ein Prozess befindet sich ein Thread in einem der nachfolgenden
Zustände: rechenwillig, rechnend, wartend, terminiert. Entsprechend den
ausgeführten Aktionen (z.B. Ein-/Ausgabe) und der Zuteilung bzw. des Entzugs
der CPU finden Zustandsübergänge statt. Jeder Thread hat seinen eigenen
Keller, in dem die Unterprogrammaufrufe verwaltet werden. Jeder Thread hat
seinen eigenen Satz an Registern (darunter auch den Befehlszähler), die gerettet
76
Schlichter, TU München 3.4. THREAD-KONZEPT
werden müssen, falls einem Thread die CPU entzogen wird. Bei einer CPU-
Zuteilung werden die geretteten Registerwerte des Threads in die jeweiligen
Register geladen.
• Prozessspezifische Information
Verschiedene Threads eines Prozesses sind nicht so ganz unabhängig wie
verschiedene Prozesse. Die nachfolgende Information/Ressourcen wird von
allen Threads eines Prozesses geteilt. Jeder Thread des Prozesses kann sie
verwenden bzw. darauf zugreifen.
Adressraum, globale Variable, offene Dateien, Kindprozesse (z.B. erzeugt
mit fork), eingetroffene Alarme bzw. Interrupts, Verwaltungsinformation
Dies sind Eigenschaften des Prozesses und nicht eines einzelnen Threads.
Beispielsweise, wenn ein Thread eine Datei öffnet, dann ist diese Datei auch
für die anderen Threads sichtbar, und sie können in sie schreiben bzw. aus ihr
lesen. Diese Information ist i.a. zwischen Prozessen nicht sichtbar, außer dass
vom Vaterprozess an den Kindprozess Dateideskriptoren vererbt werden.
Beispiel: Web-Server
Ein Prozess kann mehrere Threads umfassen, die unterschiedliche Aufgaben über-
nehmen. Beispielsweise kann ein Web-Server einen Verteiler-Thread ("dispat-
cher") und mehrere Server-Threads ("worker-thread") umfassen.
Web-Serverprozess
Verteiler- Server-
Thread Thread Benutzer
Adressraum
Anforderung
Betriebssystem
Netzwerk-Verbindung
Auf diese Weise ist es möglich den Server als eine Menge von sequentiellen
Threads zu realisieren. Der Verteiler-Thread ist eine unendliche Schleife, die die
77
Schlichter, TU München 3.4. THREAD-KONZEPT
Definition
78
Schlichter, TU München 3.4. THREAD-KONZEPT
Ergebnisrückgabe
Der Ablauf der Threads ist asynchron, d.h. die Ausführungsreihenfolge einer
Menge von Threads ist nicht fest vordefiniert. Dies ist insbesondere bei
kooperierenden Threads von Bedeutung, z.B. bei der Ergebnisrückgabe eines
Thread an einen anderen Thread. Die Ausführungsreihenfolge ergibt sich
durch die CPU-Zuteilung (Scheduling) durch das Betriebssystem oder das
Laufzeitsystem. Dies bedeutet, dass bei der Kommunikation zwischen Threads
nicht von einem bestimmten Zeitverhalten der Threads ausgegangen werden kann,
d.h. wann welche Threads ausgeführt werden.
• Direkter Ansatz
Angenommen jeder Thread liest eine Datei und erzeugt daraus die zugehörige
Hash-Information (z.B. verwendet für verschlüsselte Datenübertragung).
public class ReturnDigest implements Runnable {
private File input;
private byte[] digest;
public ReturnDigest(File input) { [Link] = input; }
public void run() {
......
digest = .......
}
public byte[] getDigest() { return digest; }
79
Schlichter, TU München 3.4. THREAD-KONZEPT
}
public class ReturnDigestUserInterface {
......
public static void main(String[] args) {
......
for (int i = 0; i < [Link]; i++) {
File f = new File(args[i]);
ReturnDigest dr = new ReturnDigest(f);
Thread t = new Thread(dr); [Link](); Berechnung
Hash
.....
byte[] digest = [Link](); Abruf von Hash
....
}
}
}
Jeder Thread speichert das Ergebnis der Dateibearbeitung in der Variablen
digest, auf die über die Methode getDigest zugegriffen werden kann.
[Link]() ruft die run-Methode auf und berechnet die Hash-Information, die
in der lokalen Variablen digest gespeichert wird.
80
Schlichter, TU München 3.5. SYNCHRONISATION
• Callback Ansatz
Nicht das main-Programm holt die Ergebnisse ab, sondern die aufgerufenen
Threads rufen jeweils eine Methode des main-Programms auf, um die
Ergebnisse zu übergeben ⇒ Callback .
public class CallbackDigest implements Runnable {
private File input;
public CallbackDigest(File input) { [Link] = input; }
public void run() {
......
byte[] digest = ........;
[Link](digest);
}
public byte[] getDigest() { return digest; }
}
public class CallbackDigestUserInterface {
......
public static void receiveDigest(byte[] digest) {
.....
}
public static void main(String[] args) {
......
for (int i = 0; i < [Link]; i++) {
File f = new File(args[i]);
CallbackDigest dr = new CallbackDigest(f);
Thread t = new Thread(dr); [Link]();
}
}
}
Im Gegensatz zum main-Programm des direkten Ansatzes dient das main-
Programm dieses Ansatzes nur zum Starten der verschiedenen Threads. Es
versucht nicht die Berechnungen der getriggerten Threads direkt zu lesen
und zu verarbeiten. Dies wird durch separate Methode receiveDigest
erledigt. Aufruf des interaktiven Beispiels: "java CallbackDigestUserInterface
[Link] [Link] [Link]".
3.5 Synchronisation
Eine wichtige Systemeigenschaft betrifft die Synchronisation paralleler Ereignis-
se. In einem Rechensystem konkurrieren parallele Aktivitäten um wiederholt ex-
81
Schlichter, TU München 3.5. SYNCHRONISATION
klusiv (d.h. zu einem Zeitpunkt darf höchstens eine Aktivität die Ressource nut-
zen) benutzbare Ressourcen, wie beispielsweise die CPU, den Drucker etc. Zu-
sätzlich dazu können aber parallele Aktivitäten auch kooperieren, indem sie Daten
über gemeinsam benutzte exklusive Objekte austauschen oder sich Nachrichten
zusenden. In all diesen Fällen haben wir das Problem, den wechselseitigen Aus-
schluss (engl. mutual exclusion) zu gewährleisten, d.h. sicherzustellen, dass nur
höchstens ein Prozess zu einem gegebenen Zeitpunkt eine exklusiv benutzbare
Ressource belegt.
3.5.1 Beispiele
Die beiden Beispiele basieren auf der speicherbasierten Prozessinteraktion,
d.h. Prozesse (oder auch Threads) interagieren über gemeinsam zugreifbare
Speicherzellen.
82
Schlichter, TU München 3.5. SYNCHRONISATION
int x; x = 0
Prozess P1 Prozess P2
A: x = x + 1
B: x = x + 2
Zeitpunkt Z
• Das Ergebnis ist vom zeitlichen Ablauf abhängig. Es sind folgende Fälle
möglich:
– Fall 1
P1 liest x = 0, erhöht, speichert x = 1;
P2 liest x = 1, erhöht, speichert x = 3; => Wert von x = 3
– Fall 2
P2 liest x = 0, erhöht, speichert x = 2;
P1 liest x = 2, erhöht, speichert x = 3; => Wert von x = 3
– Fall 3
P1 und P2 lesen x = 0;
P1 erhöht, speichert x = 1;
P2 erhöht, speichert x = 2; => Wert von x = 2
– Fall 4
P1 und P2 lesen x = 0;
P2 erhöht, speichert x = 2;
P1 erhöht, speichert x = 1; => Wert von x = 1
• Verhinderung des Nichtdeterminismus nur dadurch möglich, dass man garan-
tiert, dass die Veränderung von x in den beiden Prozessen unter wechselseiti-
gem Ausschluss (engl. mutual exclusion) erfolgt. Die Asynchronität der Pro-
zesse muss also genau an dieser Stelle eingeschränkt werden. Vernderung be-
steht in diesem Zusammenhang aus 3 Schritten: Lesen des Wertes, Erhöhen und
Speichern des neuen Wertes.
83
Schlichter, TU München 3.5. SYNCHRONISATION
Erzeuger-Verbraucher-Problem
Ein Beispiel für einen synchronisierten Zugriff auf eine gemeinsame Ressource,
nämlich einen Puffer 4 , haben wir bereits kennengelernt. Interpretiert man das
bereits angesprochene → Petri-Netz (siehe Seite 68) als eine Komposition aus drei
Teilen:
einem Erzeuger von Nachrichten (links),
einem Puffer für Nachrichten (Mitte) und
einem Verbraucher von Nachrichten (rechts).
So kann man sehen, dass durch diese Modellierung gewährleistet wird, dass
Erzeuger und Verbraucher nicht gleichzeitig etwas in den Puffer eintragen und
aus ihm entnehmen können; sie greifen wechselseitig ausgeschlossen zu.
84
Schlichter, TU München 3.5. SYNCHRONISATION
3.5.3 Modellierung
Modelliert man parallele Einheiten, die kritische Abschnitte besitzen, durch Petri-
Netze, so sind vier Phasen dieser parallelen Aktivitäten von Interesse:
1. Ausführen unkritischer Abschnitte/Transaktionen
2. Betreten eines kritischen Abschnitts
3. Ausführen der Transaktion(en) des kritischen Abschnitts
4. Verlassen des kritischen Abschnitts.
Modellierung jeder Phase durch eine Transition; Koordinierung des wechselseiti-
gen Ausschluss durch Kontrollstelle s.
Prozess 1 Prozess 2
t2 Eintritt Eintritt
t1: Phase 1; unkritische Transition
t2: Phase 2; Eintritt in kritischen Abschnitt
t3: Phase 3; Ausführung des kritischen
Abschnitts
t4: Phase 4; Verlassen des kritischen
Abschnitts
s: Kontrollstelle
k.A.
t1 t3 s
t4 Austritt Austritt
• Beispiel: Leser-Schreiber-Problem
85
Schlichter, TU München 3.5. SYNCHRONISATION
Leser Schreiber
Eintritt Eintritt
k.A. k.A.
s
Austritt Austritt
86
Schlichter, TU München 3.5. SYNCHRONISATION
3.5.4 Synchronisierungskonzepte
Ziel: Einführung wichtiger Realisierungskonzepte zur Synchronisierung paralleler
Abläufe. Dazu Konkretisierung des Prozessbegriffs. Um die modellierten Eigen-
schaften eines System zu realisieren, benötigt man Konzepte zur Formulierung
paralleler Abläufe. Auf der programmiersprachlichen Ebene sind dies Sprachkon-
strukte, wie die Java-Threads oder die Ada-Tasks. Für das Folgende benötigen
wir einen Prozessbegriff, der den abstrakten → Prozessbegriff (siehe Seite 52)
zunächst nur so konkretisiert, dass wir damit erste wichtige Konzepte zur Rea-
lisierung von Abhängigkeiten zwischen parallelen Aktivitäten einführen können.
Dies ist ein erster Schritt in die Richtung auf einen Prozess, wie er auf der Be-
triebssystemebene benötigt wird. Auf die weitere Konkretisierung eines Prozesses
als Betriebssystem-Verwaltungseinheit zusammen mit den Maßnahmen zur seiner
Verwaltung gehen wir in den folgenden Abschnitten ein.
Prozess - Konkretisierung
E/A-Auftrag wartend
fork start
erzeugt rechnend
CPU-Entzug E/A-
Auftrag
end beendet
CPU
Zuteilung
Zur Verwaltung eines Prozesses wird eine Datenstruktur benötigt, die die Infor-
mation, die einen Prozess charakterisiert, beinhaltet. Dies ist der Prozess-Kontext
(Prozess-Deskriptor), der auf dieser Konkretisierungsebene den eindeutigen Pro-
zessnamen und die Prozesszustände umfasst und später noch erweitert wird (z.B.
87
Schlichter, TU München 3.5. SYNCHRONISATION
Priorität, Registerinhalte).
Die Netz-Modellierung hat bereits gezeigt, dass man zur Synchronisation von
Prozessen spezifische Kontrollkomponenten benötigt (z.B. zusätzliche Stellen
im Petri-Netz, oder Kapazitätsbeschränkungen, die implizit durch die abstrakte
Kontrollkomponente, die die Transitionsbereitschaft von Transitionen prüft,
kontrolliert werden).
Weiterhin hat die Modellierung gezeigt, dass durch die Synchronisationsmaßnah-
men, die ja im wesentlichen durch absichtlich herbeigeführte Konflikte modelliert
wurden, ggf. unfaire Abläufe auftreten, die in einem realisierten System natürlich
unerwünscht sind. Das heißt, wir benötigen geeignete Konzepte, durch die diese
Kontrollaufgaben wahrgenommen werden und ein unfaires Verhalten vermieden
wird.
• Anforderungen
Folgende Anforderungen sind an eine Realisierung des wechselseitigen
Ausschlusses (w.A.) zu stellen:
• Jede Realisierung des w.A. benötigt eine Basis, mit festgelegten atomaren, d.h.
nicht teilbaren Operationen. Diese unteilbaren Basisoperationen sind von Hard-
und/oder Software zur Verfügung zu stellen. Informell: mit einer atomaren
Operation kann überprüft werden, ob der kritische Abschnitt frei ist; falls
ja kann er sofort betreten werden (und der kritische Abschnitt damit belegt
werden). Falls die Abfrage und das Betreten nicht atomar sind, können mehrere
zeitlich-verzahnte Abfrage stattfinden, und gegebenenfalls mehrere Prozesse
den kritischen Abschnitt betreten.
88
Schlichter, TU München 3.5. SYNCHRONISATION
• Unterbrechungssperre
Der Ablauf des Prozesses darf nicht unterbrochen werden.
• Test-and-Set Operationen
Test-and-Set Operationen (Test-And-Set-Lock, TSL) erlauben auf Hardware-
Ebene (Maschinenbefehl) das Lesen und Schreiben einer Speicherzelle als
atomare Operation.
89
Schlichter, TU München 3.5. SYNCHRONISATION
• Semaphor-Konzept
Das Semaphor-Konzept ermöglicht die Realisierung des w.A. auf einem hö-
heren Abstraktionslevel als die bereits angesprochenen Hardwareoperationen.
Zur Realisierung wird aber auf diese wieder zurückgegriffen. Realisierung von
Semaphoren mit aktivem und passivem Warten möglich.
• Monitor-Konzept
90
Schlichter, TU München 3.5. SYNCHRONISATION
Das Monitor-Konzept basiert auf der Idee, die in einem kritischen Bereich
bearbeiteten Daten zusammen mit den darauf definierten Zugriffsoperationen
in einer sprachlichen Einheit - dem Monitor - zusammenzufassen.
soll Probleme, wie sie bei der Programmierung von Semaphoren auftreten,
vermeiden. Beispiele sind die Vertauschung der P-Operationen bei
Semaphoren, oder das Vergessen der zugehörigen V-Operation. Bei
Monitoren wird die richtige Reihenfolge der Synchronisierungsoperationen
durch den Compiler generiert.
zu einem Zeitpunkt höchstens ein Prozess innerhalb des Monitors aktiv.
Prozesse können zwar jederzeit die Methoden (Prozeduren) eines Monitors
aufrufen, jedoch können sie nicht direkt auf die internen Daten eines
Monitors zugreifen. Zu jedem Augenblick kann nur ein Prozess innerhalb
des Monitors aktiv sein. Der erfolgreiche Aufruf einer Monitorprozedur
ist gleichbedeutend mit der Sperre des Monitors, die bis zum Verlassen
der Monitorprozedur bestehen bleibt. Die Vorteile des Monitor-Konzepts
gegenüber den Semaphoren ist a) die gemeinsamen Daten werden in der
Programmstruktur der beteiligten Prozesse explizit sichtbar gemacht, und
b) Monitore kapseln alle relevanten Daten und Algorithmen des kritischen
Bereichs.
Gemeinsame Daten
Warte
schlange
Operationen
Initialisierungscode
91
Schlichter, TU München 3.5. SYNCHRONISATION
3.5.5 Semaphore
Semaphore wurden 1968 von Dijkstra eingeführt. Ein Semaphor (Signalmast) ist
eine ganzzahlige Koordinierungsvariable s, auf der nur die drei vordefinierten
Operationen (Methoden) zulässig sind:
Initialisierung,
Prolog P (kommt von protekt),
Epilog V (kommt von vrej).
In der Einführungsvorlesung von Prof. Seidl wurden die Bezeichnung down für P
und up für V verwendet.
Operationen
Die Operationen P und V sind atomar; sie sind unteilbar und sie werden
wechselseitig ausgeschlossen ausgeführt.
Sei s die Koordinierungsvariable, dann sind die P und V Operationen wie
nachfolgend definiert.
Die Operation müssen mit Hilfe von Systemdiensten so realisiert werden, dass
sie wechselseitig ausgeschlossen ausgeführt werden. Vorsicht: hier gibt es keine
ganz einheitliche Definition in der Literatur für die beiden Operationen. Mögliche
Realisierung auf Hardware-Ebene mittels des Test-and-Set Maschinenbefehls. Die
P und V Operationen werden mit Hilfe von TSL im BS-Kern auf Maschinenebene
realisiert.
92
Schlichter, TU München 3.5. SYNCHRONISATION
• Informelle Charakterisierung
public void P (int s) {
s = s - 1;
if ( s < 0 ) { Prozess in die Menge der bzgl. s wartenden
Prozesse einreihen }
}
public void V (int s) {
s = s + 1;
if ( s ≤ 0 ) { führe genau einen der bzgl. s wartenden
Prozesse in den Zustand rechenwillig über }
}
s ist mit einem ganzzahligen Wert vorbesetzt, z.B. s = 1. Falls s mit einem Wert
größer 1 vorbesetzt ist, bedeutet dies die Anzahl der Prozesse, die gleichzeitig
im kritischen Bereich erlaubt sind. Die beiden Funktionen müssen jeweils
atomar ausgeführt werden, d.h. nicht als Java Programm.
– Mutex in Posix
Ein Posix Mutex ist als binäres Semaphor eine einfache Sperre, die die
Nutzung gemeinsamer Ressourcen absichert.
pthread_mutex_init(mutex) ⇒ initialisiert und konfiguriert ein Mutex.
pthread_mutex_lock(mutex) ⇒ entspricht der P-Operation; sperrt ein
Mutex.
pthread_mutex_unlock(mutex) ⇒ entspricht der V-Operation; gibt ein
Mutex frei.
Mutex Objekte und Semaphore mit Integer Werten stehen auch in Windows
zur Verfügung.
93
Schlichter, TU München 3.5. SYNCHRONISATION
Beispiel Erzeuger-Verbraucher
94
Schlichter, TU München 3.5. SYNCHRONISATION
• Variante 1
Zugriff auf Puffer W erfolgt durch Semaphor wa: semaphor(1); sowohl der
Erzeuger-Prozess E als auch der Verbraucher-Prozess V rufen vor jedem Zugriff
auf den Puffer W die entsprechenden Operationen des Semaphors wa auf.
Erzeuger E: Verbraucher V:
while (true) { while (true) {
produziere wa.P
wa.P entnimm aus W, falls Element da; sonst warte
schreibe nach W wa.V
wa.V verarbeite
} }
• Variante 2
Einführen eines zusätzlichen Semaphors voll: semaphor(0), das die Datenele-
mente im Puffer zählt:
Erzeuger E: Verbraucher V:
while (true) { while (true) {
produziere voll.P
wa.P wa.P
schreibe nach W entnimm aus W
wa.V wa.V
voll.V verarbeite
} }
Für den Erzeuger ergibt sich natürlich ein analoges Problem, falls der Puffer W
nur eine beschränkte Kapazität besitzt. Eine Abhilfe kann analog wieder durch
die Einführung eines weiteren Semaphors "leer" erreicht werden. Dieses stellt
sicher, dass der Erzeuger den Puffer nicht betritt, wenn der Puffer bereits voll
ist.
• Variante 3
95
Schlichter, TU München 3.5. SYNCHRONISATION
Einführen eines zusätzlichen Semaphors leer: semaphor(n), das die Anzahl der
freien Elemente im Puffer zählt:
Erzeuger E: Verbraucher V:
Darf die Reihenfolge der P-Operationen für die Semaphore leer, voll, wa
beim Erzeuger bzw. beim Verbraucher vertauscht werden, ohne dass sich
Ablaufprobleme ergeben?
Beispiel Philosophenproblem
96
Schlichter, TU München 3.5. SYNCHRONISATION
3
2 2
3
4 1
4
0 1
0
– Variante 1
Für eine Lösung des Philosophenproblems seien die folgenden 5 Semaphore
definiert: stab_0, stab_1, ...., stab_4, wobei jedes der 5 Semaphore mit 1
initialisiert ist. Jeder Philosoph j, mit j ∈ {0,...,4}, führe den folgenden
Algorithmus aus:
philosoph_j:
while (true) {
Denken;
stab_i.P; mit i = j
stab_i.P; mit i = j + 1 mod 5
Essen
stab_i.V; mit i = j
stab_i.V; mit i = j + 1 mod 5
}
Der angegebene Algorithmus liefert keine korrekte Lösung des wechselsei-
tigen Ausschlusses! Wenn alle fünf Philosophen gleichzeitig die erste P-
Operation (stab_i.P mit i = j) ausführen, d.h. alle gleichzeitig ihr linkes Stäb-
chen nehmen, folgt daraus eine Verklemmungs-Situation, da kein Philosoph
das zweite Stäbchen nehmen kann. Bei Ausführung der zweiten P-Operation
stab_i.P; mit i=j+1 mod 5 werden alle Philosophen blockiert. Die Philoso-
phen verhungern somit.
– Variante 2
Nur vier Philosophen dürfen gleichzeitig zu ihrem linken Stäbchen
greifen. Dies wird durch Einführung eines weiteren Semaphors tisch:
semaphor(4), das mit 4 initialisiert wird, erreicht. Der "Anweisungsteil"
jedes Philosophen wird zusätzlich mit tisch.P und tisch.V geklammert.
97
Schlichter, TU München 3.5. SYNCHRONISATION
98
Schlichter, TU München 3.5. SYNCHRONISATION
Wenn ein Thread die synchronized Methode betritt und ausführt, kann kein
anderer Thread diese Methode solange nicht ausführen, bis nicht der erste Thread
die Methode wieder verlässt.
public class Customer extends Thread {
private static int number = 1000; //initial customer ID
private int id;
private TakeANumber takeANumber;
public Customer(TakeANumber gadget) {
id = ++number;
takeANumber = gadget;
} //Customer constructor
public void run() {
try {
sleep( (int)([Link]() * 1000) );
[Link]("Customer "+id+" takes ticket " +
[Link]());
} catch ......
} //run
} //Customer
public class Bakery {
public static void main(String args[]) {
[Link]("Starting Customer threads");
TakeANumber numberGadget = new TakeANumber();
.........
for (int k = 0; k < 5; k++) {
Customer customer = new Customer(numberGadget);
[Link]();
}
} // main
} //Bakery
Die Kunden kommen hierbei nicht alle gleichzeitig, sondern die Ankunftszeit
wird zufällig gewählt; sleep heißt, der jeweilige Kunde wird nach seiner
Erzeugung für eine zufällige Zeit "Schlafen" gelegt, bevor er als Kunde eine
Nummer zieht. Durch "geeignete" Wahl der Zufallszahl können Kunden auch
"fast" gleichzeitig eine Nummer ziehen. Was hier nun noch fehlt, ist eine
Verkäuferklasse, die jeweils die Kunden entsprechend ihrer gezogenen Nummer
bedient (siehe Morelli Kap 15, S 728).
Java Monitor
• Ein Monitor stellt sicher, dass nur ein Thread zur Zeit in einer der
99
Schlichter, TU München 3.6. VERKLEMMUNGEN
3.6 Verklemmungen
Mit Verklemmung (engl. deadlock) bezeichnet man 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 können.
Verklemmungen können durch die gemeinsame Verwendung von Ressourcen
(synonym verwenden wir auch den Begriff Betriebsmittel), wie z.B. CPU,
Arbeitsspeicher, E/A-Geräte, Dateien auftreten. Ein Beispiel aus der allgemeinen
Praxis ist eine Verkehrskreuzung, wobei alle 4 Fahrzeuge geradeaus über die
Kreuzung fahren wollen; falls jedes Fahrzeug in die Kreuzung einfährt, können
sie sich gegenseitig blockieren. 7
Der Austausch von Information über gemeinsame Speicherbereiche ist eine
häufige Situation (speicherbasierte Prozessinteraktion), die bei unkorrekter
Verwendung von Synchronisationsoperationen (z.B. P und V bei Semaphoren)
leicht zu Verklemmungen führen kann; siehe die → Variante 1 (siehe Seite 95)
des Erzeuger-Verbraucher Lösungsansatzes. Dieser Abschnitt skizziert nur die
Ansätze zur Erkennung, Vermeidung und Verhinderung von Verklemmungen.
3.6.1 Allgemeines
Es lässt sich zeigen, dass die folgenden Bedingungen notwendig und hinreichend
dafür sind, dass eine Verklemmung auftreten kann.
7
Stallings S263.
100
Schlichter, TU München 3.6. VERKLEMMUNGEN
3.6.2 Belegungs-Anforderungsgraph
Die Zuteilung/Belegung und Anforderung von Ressourcen kann man sich
an einem Graphen, dem Belegungs-Anforderungsgraph, veranschaulichen. Die
Knoten sind die Prozesse und Ressourcen, die Kanten spiegeln Belegungen und
Anforderungen wider.
• Beispiel
Seien P = {P1, ... , Pn} Prozesse und R= {R1, ... , Rm} Ressourcen, z.B. n = 3
und m = 4. Beispiel eines Belegungs/Anforderungsgraphen.
fordert belegt
P1 R1 P3 R4
fordert
R2 P2 R3
fordert
P1 und P2 warten gegenseitig aufeinander. P1 wartet auf R1, die durch P2 belegt
ist, und P2 wartet auf R2, die durch P1 belegt ist.
3.6.3 Verklemmungs-Ignorierung
In vielen Systemen wird eine ’Vogel-Strauß’-Politik in bezug auf die Deadlock-
problematik verfolgt, d.h. es werden keine Maßnahmen eingesetzt, sondern es
101
Schlichter, TU München 3.6. VERKLEMMUNGEN
wird gehofft, dass alles gut geht. In Unix wird diese Philosophie z.B. bei der
Verwaltung der Prozesstabelle verfolgt. Es ist der manuelle Eingriff des Syste-
madministrators erforderlich. Prozesstabelle ist eher einfach. Sie kann jedoch bei
der Erzeugung neuer Prozesse durch "fork" überlaufen, d.h. es können keine neu-
en Prozesse mehr eingetragen und damit erzeugt werden. Prozesse warten bis sie
einen neuen Prozess erfolgreich erzeugen können. Die Tabelle ist jedoch groß ge-
nug, so dass dieser Fall sehr selten eintritt. Meist tritt er nur bei einem fehlerhaft
programmierten Programm, z.B. unendliche while Schleife, die bei jedem Durch-
lauf ein fork absetzt.
3.6.4 Verklemmungs-Erkennung
In der Praxis häufig angewendete Strategie: Verklemmungen in Kauf nehmen,
sie erkennen und beseitigen. Man versucht eine Verklemmung festzustellen
und sie, sollte sie eingetreten sein, zu beseitigen. Indiz für Verklemmungen,
z.B. angeforderte Ressource ist nach einer gewissen Zeit immer noch nicht
zugewiesen.
• Erkennungs-Algorithmus
Ansatz 1: Suche nach Zyklen im Belegungs/Anforderungsgraph.
Ansatz 2: Prüfen, ob es eine Reihenfolge für die Ausführung der Prozesse gibt,
so dass alle Prozesse terminieren können.
• Vorgehen für Ansatz 2
102
Schlichter, TU München 3.6. VERKLEMMUNGEN
3.6.5 Verklemmungs-Verhinderung
Die Verhinderungssverfahren beruhen darauf, dass man durch die Festlegung von
Regeln dafür sorgt, dass mindestens eine der für das Auftreten von Deadlocks
notwendigen Bedingungen nicht erfüllt ist. Aber: solche Regeln lassen sich nicht
für jedes Verklemmungsproblem finden. Deshalb wird meist ein allgemeinerer
Algorithmus gesucht: Vermeidungs-Algorithmus.
d.h. ein Prozess, der Ressource Ri belegt, darf nur Ressourcen Rj anfordern,
für die gilt: Rj > Ri.
Problem: wie Ordnung festlegen? Daumenregel: wichtige Ressourcen, die
gut ausgelastet genutzt werden sollten, dürfen nicht zulange einem Prozess
zugeordnet werden. Deshalb sollte für eine solche Ressource Rj gelten: Rj >
Ri, für unwichtigere Ri. Ein Problem sind jedoch interaktive Prozesse, da die
Ressourcen nicht von vorneherein feststehen, sondern sie sich erst im Laufe der
Interaktion mit dem Nutzer ergeben.
103
Schlichter, TU München 3.6. VERKLEMMUNGEN
c) Spooling: nur der Spooler Prozess hat als einziger die Ressource
zugeteilt; Zugriffe anderer Prozesse gehen über diesen Prozess. Beispiel ist
das Spooling von Druckaufträgen. Die Ressource ist exklusiv dem Spooler
Prozess zugeordnet., d.h. die Ressource wird nicht mehr gemeinsam
benutzt. Der Spooler Prozess verwaltet eine Auftragswarteschlange für
Aufträge von Prozessen.
3.6.6 Verklemmungs-Vermeidung
Die Vermeidungsverfahren basieren auf der Idee,
die zukünftigen Betriebsmittelanforderungen von Prozessen zu analysieren
(bzw. diese geeignet abzuschätzen) und
solche Zustände zu verbieten (sie also zu verhindern), die zu Verklemmungen
führen könnten.
Die Verklemmungs-Vermeidung unterscheidet sich von der Verklemmungs-
Verhinderung dadurch, dass sie erst während des Betriebs und nicht schon bei
der Softwareentwicklung greift.
Ein Beispiel ist der Bankiers-Algorithmus, der 1965 von Dijkstra entwickelt
wurde.
• Ausgangspunkt
Idee: Verwaltung von nur einer Ressourcen-Klasse, nämlich den Bankkrediten.
104
Schlichter, TU München 3.6. VERKLEMMUNGEN
Verleihen des Geldes so, dass jeder Kunde seine Geschäfte in endlicher
Zeit durchführen kann und Kunden möglichst parallel bedient werden. Die
sequentielle Abfolge ist natürlich eine triviale Lösung.
Idee: Reihenfolge für Kreditvergabe finden, so dass selbst bei denkbar un-
günstigsten Kreditforderungen die Durchführung aller Geschäfte sicherge-
stellt ist.
ungünstigster Fall: alle Kunden fordern Geld bis zu ihrem jeweiligen max.
Kreditrahmen, ohne Kredite zurückzuzahlen.
• Grobes Vorgehen
1. falls ein Kunde (Prozess) eine Anforderung hat, die aktuell erfüllbar ist,
so teilt man das Geld (die Ressource) probeweise zu und
2. untersucht für den sich damit ergebenden Zustand, ob jetzt eine
Verklemmung vorliegt, indem
3. für alle anderen Kunden von deren ungünstigsten Anforderungen
ausgegangen wird und
4. ein Erkennungs-Algorithmus ausgeführt wird.
Falls keine Verklemmung auftritt, kann die Zuteilung tatsächlich erfolgen,
anderenfalls könnte bei einer Zuteilung ein Deadlock auftreten (muss aber
nicht), weshalb die Anforderung nicht erfüllt wird.
• Beispiel
Ausgangspunkt ist die folgende Situation der vier Kunden A, B, C, D (Einheiten
jeweils in Tausend Euro):
Kunde aktueller Kredit max. Kreditrahmen
A 1 6
B 1 5
C 1 4
D 4 7
Es seien noch 3 Einheiten (Tausend Euro) in der Bank als Kredit verfügbar.
– Annahme: Kunde C fordere eine weitere Einheit als Kredit an. Diese
Anforderung wird probeweise zugeteilt und mündet nicht in einem Deadlock,
da zuerst C (max noch 2 Einheiten bis Kreditrahmen) bedient werden kann.
Wenn C seine Einheiten wieder zurückgezahlt hat, können B oder D und
schließlich A bedient werden.
Probleme bei Vermeidungsverfahren: zukünftige maximale Anforderungen
müssen bekannt sein; anderenfalls nur worst-case Abschätzungen möglich.
105
Schlichter, TU München 3.6. VERKLEMMUNGEN
106
Kapitel 4
Ein Prozess ist der Ablauf eines Programms in einem Rechensystem. Dieser
Ablauf ist eine Verwaltungseinheit im jeweiligen Betriebssystem. Der Prozess
ist ein Grundbaustein einer Parallelverarbeitung unter einem Betriebssystem, d.h.
sie laufen im Prinzip parallel ab. Falls nur eine CPU vorhanden ist, erfolgt die
Bearbeitung quasiparallel, d.h. in einem zeitlichen Wechsel.
4.1 Fragestellungen
Dieser Abschnitt gibt eine kurze Einführung in eine der wichtigen Verwaltungs-
aufgaben eines Betriebssystems:
4.2 Prozessverwaltung
Dieser Abschnitt behandelt das Prozesskonzept, Datenstrukturen zur Beschrei-
bung des aktuellen Prozesszustandes sowie Dienste zum Aufruf von Systemfunk-
tionen.
107
Schlichter, TU München 4.2. PROZESSVERWALTUNG
4.2.1 Prozesskonzept
Wir unterscheiden Benutzerprozesse, die Anwendungsprogrammen in Ausfüh-
rung entsprechen, und Systemprozesse, die Programme/Dienste des Betriebssy-
stems durchführen.
a) Jeder Prozess besitzt einen eigenen Prozessadressraum.
b) Spezielle Systemprozesse sind die Dämonen (engl. daemon); das sind
Hilfsprozesse, die ständig existieren, die meiste Zeit aber passiv sind. Sie
erfüllen i. d. R. Service-Funktionen und werden dazu durch das Eintreten
von Ereignissen aufgeweckt (z.B. Datei zum Drucken eingetroffen) oder
werden von Zeit zu Zeit aktiv, um selber zu prüfen, ob Dienste zu
erbringen sind.
108
Schlichter, TU München 4.2. PROZESSVERWALTUNG
Prozesskontrollblock
Jeder Prozess muss als eine Verwaltungseinheit beschrieben sein. Ein Prozess
wird durch seinen Prozess-Kontext und dieser durch den Prozesskontrollblock
(PCB) beschrieben. Ein PCB wird meist programmiersprachlich als Verbund
(struct) spezifiziert. Ein PCB (process control block) enthält i.d.R. folgende
Informationen:
• falls der Prozess wartend ist, eine Spezifikation des Ereignisses, auf das der
Prozess wartet (z.B. Adresse eines Semaphors).
• die Inhalte der programmierbaren Register (die Anzahl ist abhängig von der
jeweiligen CPU-Architektur), z.B. Kellerpointer.
• die Inhalte der Register, in denen die Anfangsadresse und Länge der pro-
zessspezifischen Speicherabbildungstabellen enthalten sind (virtuelle Adressie-
rung).
109
Schlichter, TU München 4.2. PROZESSVERWALTUNG
• das Programmstatuswort (PSW).Beispiele für dem Inhalt des PWS’s sind der
Ablaufmodus (Benutzer- oder Systemmodus), die momentane Ablaufpriorität,
die Adressierungsart im Benutzermodus (virtuelle oder direkte Adressierung)
und die Ergebnisse der letzten Vergleichsoperation auf Maschinenebene
(sogenannte Condition-Code Register, z.B. das N-Register (Ergebnis der letzten
Operation negativ).
• PCB unter Linux ist durch die Struktur task_struct spezifiert; definiert unter
include/linux/sched.h
1
. Dies ist eine umfangreiche Struktur, die Information zum Scheduling (z.B.
Zustand und Priorität), Prozess-ID, Vaterprozess, Kinder enthält. Daneben wer-
den Informationen Benutzer-/Gruppeninformationen und Ressourceninforma-
tionen (Locks, threads, etc) gespeichert.
Daneben kann ein PCB noch weitere Statistiken über die Historie des Prozesses
speichern, die beim Scheduling ausgewertet werden.
Prozesslisten
Die Prozesse werden in Zustandslisten verwaltet, die als verkettete Liste der PCBs
realisiert sind.
für E/A-Geräte (z.B. Platte, Terminal) existiert i.d.R. jeweils eine eigene
Warteschlange, die die PCBs der wartenden Prozesse enthält.
Falls mehrere CPUs vorhanden sind, verweist "rechnend" auf mehrere Elemente.
Prozessidentifikation
Rechnend
Registerzustand
Prozesskontrollblock PCB
Da der PCB eine Datenstruktur des Betriebssystems ist, kann die Ablage nicht im
Benutzeradressraum erfolgen. Da weiterhin die Prozesse nicht kellerartig aktiviert
1
Achilles S 21
110
Schlichter, TU München 4.2. PROZESSVERWALTUNG
und deaktiviert werden, sondern in beliebiger Folge, kann er auch nicht im Keller
des Betriebssystems abgelegt werden, sondern es wird dafür die Halde verwendet.
Zustandsmodell
resign
add retire
rechenwillig assign rechnend
block
ready
wartend
swap out
swap in
ausgelagert
Zustandsübergänge sind:
add: ein neu erzeugter Prozess wird zu der Menge der rechenwilligen Prozesse
hinzugefügt;
assign: als Folge eines Kontextwechsels wird dem Prozess die CPU zugeordnet;
block: aufgrund eines EA-Aufrufs oder einer Synchronisationsoperation wird der
Prozess wartend gesetzt;
ready: nach Beendigung der angestoßenen Operation wechselt der Prozess in den
Zustand rechenwillig; er bewirbt sich erneut um die CPU;
resign: dem rechnenden Prozess wird die CPU entzogen; er bewirbt sich
anschließend erneut um die CPU;
retire: der aktuell rechnende Prozess terminiert;
swap out: der Prozess wird auf die Festplatte ausgelagert;
111
Schlichter, TU München 4.2. PROZESSVERWALTUNG
swap in: der Prozess wird von der Festplatte in den Arbeitsspeicher geladen.
Prozesserzeugung
Ein Prozess kann andere Prozesse erschaffen. Diese sind die Kindprozesse (child
process) und der Erschaffer ist der Vater (parent process). Vater
kann auf Beendigung von Kind warten, oder
parallel weiterlaufen.
• Prozesserzeugung: 2 Vorgehensweisen
Windows NT: Vaterprozess veranlasst eine Reihe von Systemaufrufen, die
das Kind entstehen lassen.
Unix: Vater klont sich mit Systemaufruf fork(); Kind ändert selbst sein
Aufgabe.
• Unix Prozesserzeugung
Aufruf von fork() führt zu einem fast exakten Duplikat des Vaterprozesses.
Unterschiede sind
unterschiedlicher process identifier (PID)
der Ergebniswert von fork()
Vater: PID des Kindprozesses
Kind: 0
Mit Hilfe der PID kann der Vaterprozess den Kindprozess adressieren, z.B. um
ihn zu beenden.
– Beispielprogramm
#include <stdio.h>
int main(int argc, char *argv[]) {
char *myname = argv[1];
int cpid = fork();
if cpid == 0 {
printf("The child of %s is %d\n", myname, getpid());
.......
return (0);
} else {
printf("My child is %d\n", cpid);
/* wird vom Vaterprozess durchlaufen */
.....
return(0);
}
}
112
Schlichter, TU München 4.2. PROZESSVERWALTUNG
113
Schlichter, TU München 4.2. PROZESSVERWALTUNG
Falls der Kindprozess vor dem wait des Vaters beendet wird, entsteht ein
"Zombieprozess".
Ein Zombieprozess führt keinen Code mehr aus. Er belegt nur noch
Tabelleneinträge im BS, da der Rückgabewert und der Beendigungsstatus
für den Elternprozess bereitgehalten werden müssen.
Kind
exit
Vater
Vater Vater
fork
wait
Kind exit
Zombieprozess
Vater
Vater Vater
fork wait
Der Aufruf von wait des Vaterprozesses ist norwendig, da sonst dauerhafte
Zombieprozesse entstehen können. Terminiert der Vaterprozess vor dem
Kindprozess, verwaist er und wird als Kind dem init-Systemprozess
zugeordnet; dieser führt zu gegebener Zeit ein wait für alle Kinderprozesse
aus.
Bei der Verwaltung von Vater-/Kindprozess sind eine Reihe von Entscheidungen
zu treffen:
• Ausführung
Vaterprozess und Kind werden gleichzeitig ausgeführt, oder
der Vaterprozess wartet darauf, dass das Kind beendet wird
114
Schlichter, TU München 4.2. PROZESSVERWALTUNG
• Ressourcen
Vater und Kind teilen sich alle Ressourcen.
Vater und Kind teilen sich einen Teil der Ressourcen.
Vater und Kind haben keine Ressourcen gemeinsam.
• Adressraum
Das Kind ist ein Duplikat des Vaters.
Das Kind führt durch automatisches Laden ein neues Programm aus (exec-
Systemaufruf).
• Threads
Das Kind dupliziert alle Threads des Vaters.
Das Kind dupliziert nur den Thread des Vaters, der die fork-Operation
ausgelöst hat. Falls nach der fork-Operation der exec-Systemaufruf
ausgeführt wird, wird sowieso der komplette Prozess ersetzt.
4.2.2 Dispatcher
Aufgabe des Dispatchers: Realisieren der Zustandsübergänge zwischen rechnend
und rechenwillig: Prozessor binden und entbinden. Dazu ist ein Kontextwechsel
erforderlich. Dabei ist zu berücksichtigen, dass die Prozesslisten entsprechend
aktualisiert werden, d.h. der PCB des ausgewählten Prozess muss aus der
rechenwillig-Liste entfernt werden und in die rechnend-Liste eingetragen werden.
Kontextwechsel
CPU wird entzogen und einer anderen Aktivität zugeteilt; ein Kontextwechsel ist
erforderlich, falls der rechnende Prozess P1 in den Zustand wartend oder z.B.
durch Prozessorentzug in den Zustand rechenwillig übergeführt wird.
• Problem
aktueller Ausführungskontext des Prozesses muss gesichert werden und
Kontext des nächsten rechenbereiten Prozesses muss geladen werden. Falls für
den Zugriff auf eine Datei X nur ein Dateizeiger zur Verfügung steht, dann
muss die Position des Dateizeigers gerettet werden. Wenn Prozess P1 wieder
rechnend wird, dann soll er an der Position weiterlesen, an der er unterbrochen
wurde; falls zwischenzeitlich ein anderer Prozess P2 ebenfalls die Datei gelesen
115
Schlichter, TU München 4.2. PROZESSVERWALTUNG
und den Dateizeiger verändert hat, darf dies bei der Fortsetzung von P1 keine
Auswirkung haben. In Unix erhält jeder Prozess einen eigenen Dateizeiger.
Threads
Kontextwechsel z.B. durch den Aufruf der Systemoperation sleep durch einen
Prozess. Beim Aufruf der Operation sleep ist ein Warteraum, in den der
Prozess eingefügt werden soll, anzugeben (z.B. E/A-Warteraum, oder warten
auf Terminieren eines Kind-Prozesses). Bei der Ausführung von sleep werden
vergröbert folgende Schritte durchgeführt.
1. Maskieren von Interrupts; Ausblenden von Unterbrechungen, da der
Kontextwechsel nicht gestört werden soll.
2. Lokalisieren der benötigten Warteschlange;
3. Neuberechnung der Priorität des Prozesses;
4. Einfügen des Prozesses in die Warteschlange;
5. Aufruf der Operation zum Kontextwechsel.
Bei der Ausführung der Operation zum Kontextwechsel wird vom Scheduler der
nächste Prozess ausgesucht, dem der Prozessor zugeteilt werden soll, und mit
dieser Information wird die Operation resume aufgerufen.
Zunächst wird der Zustand des noch aktuellen Prozesses aus den Registern in
den Prozesskontrollblock des Prozesses gespeichert.
Dann wird die Adresse des Prozesskontrollblocks des neu zu bindenden
Prozesses sowie der Zustand des neuen Prozesskontrollblocks in die Register
geladen und der Kontextwechsel ist durchgeführt.
116
Schlichter, TU München 4.2. PROZESSVERWALTUNG
Durch das Maskieren von Interrupts kann das Warten auf die relevanten
Ereignisse eingestellt werden, d.h. die anderen Interrupts werden ausgeblendet;
der Kontextwechsel soll nicht gestört werden.
4.2.3 Arbeitsmodi
Ziel für den Betrieb von Rechensystemen: kontrollierter Zugriff auf Hardware-
komponenten nur durch BS. Dadurch soll verhindert werden, dass Benutzer oder
Softwaresysteme Hardwarekomponenten unsachgemäß nutzen, und implizit an-
dere nebenläufige Aktivitäten schädigen.
Lösung: alle Zugriffe auf Hardware nur über privilegierte Befehle zulässig;
Frage: wer darf privilegierte Befehle ausführen ⇒ Antwort: Prozesse in einem
privilegierten Modus.
Herkömmlich unterscheidet man zwischen dem Benutzer- (engl. user mode) und
dem Systemmodus (engl. kernel mode).
• Benutzermodus
Es sind nur die nicht privilegierten Befehle verfügbar. Damit ist der Zugriff auf
Prozessadressraum und unkritische Register, wie Befehlszähler, Indexregister
möglich. Benutzerprozesse werden im Benutzermodus ausgeführt. Kritische
Register, über die der Kontext eines Prozesses beeinflusst werden kann
(z.B. Ablaufpriorität, Arbeitsmodus) können nur im Systemmodus verändert
werden. Wird versucht, einen privilegierten Befehl auszuführen, gibt es einen
Befehlsalarm.
• Systemmodus
Es sind auch die privilegierten Befehle verfügbar (z.B. Anhalten der Maschine,
Verändern der Ablaufpriorität). Die Dienste des Betriebssystemkerns werden
im Systemmodus ausgeführt.
• Nutzung der Hardware-Komponenten nur über Dienste des BS: Aufruf eines
BS-Dienstes über spezielle Befehle: den Systemaufruf. Dies führt zu einer →
Unterbrechung (siehe Seite 134) und damit zu einem kontrollierten Eingang in
das BS (z.B. Zugriffsrechte des aufrufenden Prozesses prüfen).
4.2.4 Systemaufrufe
Ein Systemaufruf ist eine Funktion, die von einem Benutzerprozess aufgerufen
wird, um einen BS-Kerndienst aufzuführen.
117
Schlichter, TU München 4.2. PROZESSVERWALTUNG
• Beispiel
Lesen von Daten aus einer Datei und Kopieren in eine andere Datei. Dabei
treten die folgenden Systemaufrufe auf:
(1)
Schreiben des Prompts auf Bildschirm: Angabe der Dateinamen
(2)
Lesen der Tastatureingabe (bzw. Analoges bei Mouse-Eingabe)
(3)
Öffnen der zu lesenden Datei (open)
(4)
Erzeugen der neuen Datei
(5)
ggf. Fehlerbehandlung: Nachricht auf Bildschirm
(6)
Schleife: Lesen von Eingabedatei (ein Systemaufruf) und schreiben in
zweite Datei (auch Systemaufruf)
(7) Schließen beider Dateien
(8) Ausgabe auf Bildschirm
Jeder Schritt ist jeweils ein Systemaufruf. Durch die Verwendung von
Laufzeitroutinen ergibt sich eine höhere Abstraktionsebene ⇒ Aufruf einer
Routine, die die notwendigen Systemaufrufe durchführt.
• im Benutzer-Adressraum
Der BS-Kern verwaltet nur single-threaded Prozesse. Damit ist es auch möglich
ein Thread-Package für ein Betriebssystem zu realisieren, das auf BS-Ebene
keine Threads unterstützt.
118
Schlichter, TU München 4.2. PROZESSVERWALTUNG
Prozess Thread
Benutzer
Adressraum
(Benutzermodus)
System
BS-Kern Adressraum
(Systemmodus)
• im System-Adressraum
Neben den Prozessen werden im BS-Kern auch alle Threads verwaltet. Damit
können auch alle Funktionen zur Verwaltung von Prozessen, z.B. CPU-
119
Schlichter, TU München 4.2. PROZESSVERWALTUNG
Zuteilung, für Threads verwendet werden. Dies bedeutet jedoch auch, dass bei
Erzeugung bzw. Terminierung von Threads jeweils Systemaufrufe durchgeführt
werden müssen. Systemaufrufe sind jedoch i.a. aufwendig.
Prozess Thread
Benutzer
Adressraum
(Benutzermodus)
System
BS-Kern Adressraum
(Systemmodus)
Thread Prozess-
tabelle tabelle
120
Schlichter, TU München 4.3. PROZESSORVERWALTUNG
Prozess User-Thread
BS-Kern
Kernel
Thread
4.3 Prozessorverwaltung
Eine wesentliche Aufgabe der Prozessorverwaltung besteht darin zu entscheiden,
welcher der um den bzw. die Prozessor(en) konkurrierenden Prozesse (bzw.
Threads) zu einem Zeitpunkt an den bzw. die Prozessor(en) gebunden wird.
Dazu steht die BS-Komponente Scheduler zur Verfügung. Die Durchführung der
→ Zustandsübergangs (siehe Seite 111) eines Prozesses von rechenwillig nach
rechnend ist Aufgabe des Dispatchers, während der Scheduler aus der Liste
der möglichen Prozesse einen geeigneten auswählt. Der Scheduler wählt den
Prozess aus, der durch einen assign-Zustandsübergang nach rechnend übergeht.
In folgenden Situationen 2
muss ein Scheduler auf jeden Fall aktiviert werden:
ein neuer Prozess wird erzeugt;
ein Prozess terminiert;
ein Prozess blockiert aufgrund eines EA-Auftrags;
eine EA-Unterbrechung tritt auf.
Daneben kann das Betriebssystem einem Prozess die CPU entziehen, falls er
bereits zulange rechnend ist (Ablauf der Zeitscheibe).
• Prozessablauf besteht aus einer Sequenz von alternierenden CPU- und E/A-
Perioden. Während der E/A-Perioden wartet der Prozess auf die Beendigung
2
[Tanenbaum2001, S134]
121
Schlichter, TU München 4.3. PROZESSORVERWALTUNG
Zeit
Zuweisung
A hat CPU CPU an A A hat CPU
Prozess A
Unterbrechung
BS-Kern
hat CPU
BS-Kern
BS-Kern
Unterbrechung
hat CPU
B hat CPU
Prozess B
Zuweisung
CPU an B
4.3.1 Kriterien
Der Scheduler wählt aus der Menge der rechenwilligen Prozesse den nächsten
auszuführenden Prozess aus. Es existieren unterschiedliche Verfahren die von der
jeweiligen Prozessorverwaltungsstrategie abhängen. Mögliche Leistungskriterien
für ein Schedulingverfahren:
• Fairness. Jeder Prozess soll einen fairen Anteil der CPU zum Rechnen erhalten.
• Effizienz, Prozessorauslastung. Dies ist ein Maß für die Auslastung eines
Prozessors. Ziel sollte es sein, dass möglichst alle Teile der Rechenanlage
effizient genutzt werden, z.B. CPU und EA-Geräte sollten möglichst gut
ausgelastet sein.
122
Schlichter, TU München 4.3. PROZESSORVERWALTUNG
Die Ziele der Schedulingverfahren hängen von der Umgebung und den
Betriebsarten des Rechensystems ab.
• Alle Systeme
Fairness - jeder Prozess bekommt Rechenzeit der CPU.
Balance - alle Teile des Systems sind ausgelastet.
Policy Enforcement - Scheduling Policy wird nach außen sichtbar
durchgeführt.
• Stapelbetrieb
Durchsatz - maximiere nach Aufträge pro Zeiteinheit.
Ausführungszeit - minimiere die Zeit von Start bis zur Beendigung.
CPU-Belegung - belege CPU konstant mit Aufträgen.
• Dialogbetrieb - interaktive Systeme
Antwortzeit - antworte schnellstmöglich auf Anfragen.
Proportionalität - Erwartungshaltung der Nutzer berücksichtigen. Der
Benutzer erwartet, dass der Aufbau einer Internetverbindung länger dauert
als deren Abbruch. Ein weiteres Beispiel ist die Dateiauswahlbox im
Windows Explorer: die Erstellung der Liste zu den hierarchisch oberen
Verzeichnissen sollte schnell erfolgen (ist jedoch nicht immer so).
123
Schlichter, TU München 4.3. PROZESSORVERWALTUNG
• Echtzeitsysteme
Abschlusszeit - kein Verlust von Daten.
Vorhersagbarkeit - Qualitätsverlust bei Multimedia vermeiden. Schwan-
kungen können durch Pufferung von Informationen (Frames) ausgeglichen
werden, solange die Schwankungen in einem gewissen Rahmen bleiben.
4.3.2 Scheduling-Strategien
Es werden zwischen zwei Klassen unterschieden: nicht-unterbrechende (nonpre-
emptive) und unterbrechende Strategien (preemptive).
Zeitscheibenstrategie
124
Schlichter, TU München 4.3. PROZESSORVERWALTUNG
der Prozess entweder bis zum Ablauf des Zeitquantums oder bis zum Auftreten
einer blockierenden Systemfunktion im Besitz der CPU (je nachdem was zuerst
eintritt). Alle rechenwilligen Prozesse werden in einer FIFO-Warteschlange
verwaltet. Nach Ablauf der Zeitscheibe wird der Prozess am Ende der FIFO-
Warteschlange eingereiht.
Prioritäten
Diese Strategie ist i.a. unterbrechend. Sie basiert darauf, an die Prozesse Prioritä-
ten zu vergeben. Die Prioritätenvergabe kann dabei statisch oder dynamisch sein.
Die Prioritätenstrategie kann unterbrechend und nicht-unterbrechend sein. Im er-
sten Fall wird der Ablauf eines Prozesses unterbrochen, wenn ein anderer Prozess
mit höherer Priorität rechenwillig wird. Im zweiten Fall behält der Prozess die
125
Schlichter, TU München 4.3. PROZESSORVERWALTUNG
CPU solange bis er entweder eine blockierende Systemfunktion aufruft oder die
CPU freiwillig abgibt.
• Statische Prioritätenvergabe
jeder Prozess besitzt für die Dauer seiner Existenz eine feste Priorität.
Problem: Gefahr des Verhungerns von Prozessen mit niedriger Priorität
Lösung: Erhöhung der Priorität von lange wartenden Prozessen, d.h.
dynamische Prioritäten.
• Dynamische Prioritätenvergabe
die Prioritäten der Prozesse können sich dynamisch verändern, d.h. sie werden
in gewissen Zeitabständen neu berechnet.
Idee: lange Wartezeiten berücksichtigen (Erhöhen die Priorität).
Prozesse mit großem CPU-Verbrauch sinken in Priorität.
E/A-intensive Prozesse steigen in Priorität (damit E/A-Geräte und CPU
parallel genutzt werden).
• Zeitscheibenstrategien und Prioritätenvergabe können zu effizienten Verwal-
tungsstrategien kombiniert werden. Beispielsweise können Prozesse in Priori-
tätsklassen gruppiert werden. Innerhalb einer Gruppe wird die Zeitscheibenstra-
tegie verwendet. Beispielweise können 4 Prioritätsklassen eingerichtet werden,
wobei die Klasse 4 die höchste Priorität hat. Solange Prozesse in der Klasse
4 sind, werden diese jeweils im Zeitscheibenverfahren ausgewählt. Falls die
Klasse 4 leer, werden Prozesse der Klasse 3 ausgewählt usw. Prozesse müssen
dynamisch den Klassen zugeordnet werden, damit nicht Prozesse der untersten
Klasse verhungern.
• Windows XP Scheduling
Windows XP nutzt eine Prioritäten-basierte, unterbrechende Strategie. Thread
mit höchster Priorität wird ausgeführt, bis
er terminiert, oder
er seine Zeitscheibe ausgeschöpft hat, oder
eine Blockierung (Systemaufruf, E/A) auftritt.
Es werden Prioritäten von 0 - 31 unterschieden, die in verschiedene Klassen
eingeteilt werden
126
Schlichter, TU München 4.3. PROZESSORVERWALTUNG
First-Come First-Served
• Ein Kontextwechsel findet nur statt, wenn der Prozess eine blockierende
Systemfunktion aufruft oder der Prozess die CPU freiwillig abgibt. Im letzten
Fall wird der Prozess sofort wieder am Ende der Ready-Queue eingereiht. Im
ersten Fall wird der Prozess nach Ende der Blockierungsursache wieder am
Ende der Ready-Queue eingereiht.
127
Schlichter, TU München 4.3. PROZESSORVERWALTUNG
Shortest-Jobs-First
• anwendbar, falls die Dauer der nächsten Rechenphase bis E/A-Befehl, Interrupt
etc. bekannt ist.
• Beispiel: P1: 6ms, P2: 8ms, P3: 7ms, P4: 3ms
Schedule bei SFJ : P4, P1, P3, P2; Wartezeit: (3+16 +9 +0) /4 = 7 ms
bei FCFS: 10.25 ms (P1 vor P2 vor P3 vor P4)
• Problem: Kenntnis über die Bedienzeiten erforderlich. Für Stapelbetrieb
geeignet, da dort Information über Rechenzeiten zur Verfügung stehen
(Benutzer geben bei Batch-Jobs Rechenzeit an). Für SJF gibt es wieder
nicht-unterbrechende und unterbrechende Varianten. Im letzteren Fall wird
ein Prozess unterbrochen, falls ein Prozess rechenwillig, dessen nächste
Rechenphase kürzer ist als die noch verbleibende Rechenzeit des momentan
rechnenden Prozesses.
• Für interaktive Prozesse wird die Länge der nächsten Rechenphase ("Burst")
geschätzt:
X n
Sn+1 = 1/n Ti
i=1
128
Schlichter, TU München 4.3. PROZESSORVERWALTUNG
129
Schlichter, TU München 4.3. PROZESSORVERWALTUNG
User-Threads
130
Schlichter, TU München 4.3. PROZESSORVERWALTUNG
Kernel-Threads
• Long-Term-Scheduler
Auswahl rechenwilliger neuer Aufträge (meist Jobs aus dem Hintergrundbe-
trieb (batch)) und Einlagerung in den Arbeitsspeicher; Einfügen der Prozesse
in die Ready-Queue. Scheduler kontrolliert den Multiprogramming-Grad, d.h.
wieviele Prozesse im Arbeitsspeicher liegen. Long-Term-Scheduler wird relativ
selten aufgerufen. Wenn ein Prozess das System verläßt, wird dieser Scheduler
u.U. erst nach mehreren Minuten aufgerufen.
Kriterium: guten Prozessmix erzielen, d.h. Mischung aus E/A-intensiven
und rechenintensiven Prozessen (nur E/A-intensiv: Ready-Queue häufig
leer, CPU nicht ausgelastet, andersherum: E/A-Geräte schlecht ausgelastet).
Long-term Scheduling ist nicht immer vorhanden: z.B. in Unix nicht, jeder
neue Prozess wird in Arbeitsspeicher geladen. Eine andere Zwischenstufe ist
131
Schlichter, TU München 4.3. PROZESSORVERWALTUNG
• Graphische Darstellung
neue
Aufträge
Long-term
Scheduler ausgeswappte
Prozesse
swap-out
swap-in
CPU Scheduler
E/A-Befehl
E/A-Warteschlange
Zeitscheibe
abgelaufen
sleep-Befehl
Zeit-Interrupt-
Warteschlange
Ausführung im Systemaufruf
BS-Kern
132
Schlichter, TU München 4.3. PROZESSORVERWALTUNG
– nicht-unterbrechend
Eine Prozessorzuordnung bleibt bis der Prozess eine blockierende System-
funktion aufruft oder freiwillig die CPU abgibt. Neue eintreffende Prozesse
mit kürzeren Fristen werden erst beim nächsten Scheduling berücksichtigt.
– unterbrechend
Diese Variante führt einen Kontextwechsel durch, wenn ein Prozess
mit einer kürzeren Frist rechenwillig wird. Man kann zeigen, dass die
preemptive Variante immer eine Abarbeitungsreihenfolge mit Einhaltung
aller Zeitvorgaben findet, solange mindestens eine solche Reihenfolge
existiert.
5
[Steinmetz1999, S303][Nehmer2001, S123]; Videobilder nicht zu früh, sonst Pufferüberlauf;
Videobilder nicht zu spät, sonst Ablaufgeschwindigkeit nicht korrekt.
133
Schlichter, TU München 4.4. UNTERBRECHUNGSKONZEPT
• Rate-Monotonic Scheduling
Rate-Monotonic Scheduling (RMS) ist für periodische Prozesse; RMS ordnet
Prioritäten in Abhängigkeit von der Periode zu.
1) Prozesse mit der höchsten Frequenz (kleinste Periode) erhalten die
höchste Priorität.
2) Prozesse mit der geringsten Frequenz (längste Periode) erhalten die
niedrigste Priorität.
Die Priorität ist statisch; sie ändert sich nicht für den Rest der Prozesslaufzeit.
Prioritäten geben die relative Wichtigkeit eines Prozesses gegenüber der
Wichtigkeit anderer Prozesse im Rechensystem wider. RMS ist relativ einfach
zu handhaben und sie erlaubt eine Abschätzung, ob eine Echtzeitanwendung
auf einer bestimmten Rechenanlage ohne Fristverletzung ausgeführt werden
kann oder nicht.
– Auswahl der Prozesse anhand ihrer Priorität. Jedoch auch unter Berücksich-
tigung der anderen Kenngrößen, wie z.B. Bereitzeit.
– hochfrequente Prozesse werden minimal verzögert.
– Zerstückelung niederfrequenter Prozesse, da sie häufig wegen hochfrequen-
ter Prozesse unterbrochen werden.
4.4 Unterbrechungskonzept
Die optimale Ausnutzung und Auslastung aller Geräte eines Rechensystems legt
Mehrprogrammbetrieb nahe. Zerlegung der Ausführungsphasen eines Programms
in viele Einzelteile;
- Aufbrechen der Ausführung eines Prozesses in mehrere Phasen: u.a.
Rechnen, E/A, Synchronisieren mit Partner.
- Die Ausführung der Programme wird in der Regel mehrfach unterbrochen.
4.4.1 Motivation
Ursachen für Unterbrechungen
zugeteilte Prozessorzeit ist aufgebraucht;
benötigte Ressourcen stehen aktuell nicht zur Verfügung;
ein E/A-Gerät meldet sich zurück;
ein Fehler tritt auf, z.B. Division durch 0;
Systemaufruf (wurde bereits als spezielle Unterbrechung eingeführt);
134
Schlichter, TU München 4.4. UNTERBRECHUNGSKONZEPT
Die ersten 3 Ursachen sind extern veranlasst, während die letzten beiden
Unterbrechungen intern ausgelöst werden.
• Es ist erforderlich, bei der Unterbrechung den CPU Status des gerade aktiven
Prozesses für die spätere Fortsetzung zu speichern. Als Minimum ist dabei
der Befehlszähler und das Programmstatuswort zu retten, da diese bei der
Einstellung des neuen Zustandes bei der Unterbrechungsausführung in der
CPU verändert werden. Weitere Zustandsinformationen wird dann in der
Unterbrechungsbehandlung des Betriebssystems gerettet.
4.4.2 Unterbrechungsarten
Die normale Programmausführung eines Prozessors kann auch durch mehrere
Arten von Unterbrechungen verändert werden. Man unterscheidet zwischen
synchronen und asynchronen Unterbrechungen.
Unterbrechung
synchron asynchron
Alarme
Trap Interrupt
(Exception)
135
Schlichter, TU München 4.4. UNTERBRECHUNGSKONZEPT
Ende E/A
Auftrag
Unterbrechungs-
behandlung (UBH)
136
Schlichter, TU München 4.4. UNTERBRECHUNGSKONZEPT
Unterbrechung
arithmetischer Alarm
Unterbrechungs-
behandlung (UBH)
137
Schlichter, TU München 4.4. UNTERBRECHUNGSKONZEPT
Ablauf
4.4.4 Konflikte
Konflikte bei Unterbrechungen treten z.B. in folgenden Situationen auf:
(1) während einer Unterbrechungsbehandlung treten weitere Unterbrechun-
gen auf;
(2) es treffen gleichzeitig mehrere Unterbrechungswünsche ein.
• Beispiel
E/A-Kanal 1 und E/A-Kanal 2 erledigen beide Aufträge für Prozess A.
138
Schlichter, TU München 4.4. UNTERBRECHUNGSKONZEPT
externe
Unterbrechung
externe
Konflikt
Unterbrechung
Ende E/A
Auftrag
• Mögliche Konfliktlösungen
139
Schlichter, TU München 4.4. UNTERBRECHUNGSKONZEPT
140
Kapitel 5
Speicherverwaltung
Der Adressraum ist eine zentrale Abstraktion, die von der Systemsoftware eines
Rechensystems zur Verfügung gestellt werden muss. Über den Adressraum sind
alle für die Ausführung eines Anwendungsprogramms notwendigen Operationen
und Datenstrukturen zugreifbar. Allgemein wird ein Adressraum durch eine
zusammenhängende Menge von Adressen und deren Inhalte definiert. Die
maximale Größe eines Adressraums kann aus dem Adressbusaufbau der
verwendeten Prozessorarchitektur abgeleitet werden. Modernde Rechensysteme
unterscheiden zwischen den Adressräumen der Programme und dem physischen
Adressraum (Arbeitsspeicher).
5.1 Fragestellungen
Dieser Abschnitt beschäftigt sich mit den Adressräumen für Programme und
deren Abbildung auf den physischen Arbeitsspeicher einer Rechenanlage:
5.2 Einführung
Die unmittelbare Nutzung des physischen Adressraums (Arbeitsspeichers) bei der
Anwendungsentwicklung ist nicht empfehlenswert. Probleme sind folgende:
141
Schlichter, TU München 5.2. EINFÜHRUNG
5.2.1 Adressräume
• Maschinenadressraum
142
Schlichter, TU München 5.2. EINFÜHRUNG
Die CPU muss vor jedem Zugriff auf Befehle und Operanden die jeweiligen
Programmadressen in Maschinenadressen umsetzen. Diese Umsetzung wird
durch Speicherabbildungen geleistet. Die wichtigsten dieser Abbildungen
werden in den folgenden Abschnitten kurz vorgestellt.
direkte Adressierung,
Basisadressierung,
Seitenadressierung und
Segment-Seitenadressierung.
Single-Threaded Adressraum
niedrige hohe
Adresse Adresse
143
Schlichter, TU München 5.2. EINFÜHRUNG
Multi-Threaded Adressraum
hohe
niedrige Adresse
Adresse
Beispiel - Adressräume
144
Schlichter, TU München 5.2. EINFÜHRUNG
zwischen ca. 2 GByte und 4 GByte. Bei allen BS wird ein unterschiedlich
großer Adressbereich am Anfang (Adressen 0 und aufwärts) für jeglichen Zugriff
gesperrt: bei Windows 95 sind es 4 KByte, bei Windows NT 64 KByte, bei BSD
Unix ist es abhängig vom Rechnertyp (4 - 8 KByte). Durch diese Sperrung wird
jeder Zugriff auf diesen Bereich und damit insbesondere das Dereferenzieren
eines Nullzeigers vom System abgefangen und die Programmausführung mit
einer Fehlermeldung abgebrochen. Gleiches gilt für den Bereich zwischen dem
Adressbereich der Anwendung und des Betriebssystems; auch hier ist ein kleiner
Bereich, z.B. 64 KB bei Windows, nicht zugreifbar, um fehlerhafte Pointer zu
erkennen.
In Windows 95 wird zusätzlich der Adressbereich von 4 KByte - 4 MByte von der
Nutzung durch 32 Bit Anwendungen ausgeklammert (Adressbereich für MS-DOS
bzw 16 Bit Anwendungen).
Im oberen Bereich des virtuellen Adressraums wird meist der Betriebssystemcode
eingeblendet (z.B. bei Windows 95 im Bereich 1 GByte - 2 GByte; dadurch
können BS-Funktionen auch ohne Adressraumwechsel genutzt werden. Bei
BSD Unix und Windows NT/2000 ist dieser Bereich vor jeglichem Zugriff
durch die Anwendung geschützt (oft wird sogar lesender Zugriff unterbunden).
Bei Windows 95 besteht dieser Schutz nicht, d.h. Anwendungen können das
Betriebssystem zum Absturz bringen.
Windows 7 bzw. Windows 10 unterstützt 64 Bit Adressierung mit einem virtuellen
Adressraum von 8 TB. Für die Größe des physikalischen Arbeitsspeichers gelten
jedoch folgende Einschränkungen:
Windows 7 Professional bis 192 GB
Windows 7 Home Premium bis 16 GB
Windows 7 Home Basic bis 8 GB
Windows 10 Professional bis 512 GB
Windows 10 Home Basic bis 128 GB
Mac OS X bis 128 GB
Haldenverwaltung
Dynamisch erzeugte Daten, z.B. Listen und Objekte werden auf der Halde (heap)
gespeichert. 1 Die Halde wird nicht nach dem Kellerprinzip verwaltet. Zellen des
Kellerspeichers werden mit Hilfe der Operation pop freigegeben. Kellerbereiche
werden nach dem LIFO-Prinzip verwaltet. Datenobjekte der Halde werden bei
Bedarf erzeugt und gelöscht. Nicht mehr benötigte Datenobjekte werden entweder
1
siehe Informatik II von Prof. Brügge.
145
Schlichter, TU München 5.2. EINFÜHRUNG
• Belegung Beispiel C:
• Buchführung des Speicherbereichs einer Halde mit Hilfe von Belegungs- und
Freigabeoperationen.
146
Schlichter, TU München 5.2. EINFÜHRUNG
5 4 6 2
5 4 6 2
Das Verfahren etwas aufwendiger als implizite Listen, da ein extra Pointer
notwendig ist. Bei impliziten Listen ist kein extra Pointer notwendig, da
aufgrund der Blockgröße der Beginn des jeweils nächsten Blocks leicht zu
bestimmen ist. Eine weitere Verfeinerung ist die Führung von getrennten
Freiliste für jede unterschiedliche Größenklasse. Damit wird die Suche bei
der Allozierung erleichtert.
• Freiliste
Die Freibereiche der Halde werden mit Hilfe einer Liste (z.B. einfach verkettet)
verwaltet.
public class freibereich {
int size;
freibereich next;
<methodendefinitionen>
}
Für jeden verfügbaren Freibereich wird jeweils die Größe in Bytes gespeichert.
Man könnte auch eine doppelt verkettete Liste anlegen.
147
Schlichter, TU München 5.2. EINFÜHRUNG
• Garbage Collection
Java sammelt belegten Speicher, der nicht mehr benötigt wird, auf. In C muss
der Speicher explizit durch free freigegeben werden; deshalb oft sogenannte
148
Schlichter, TU München 5.2. EINFÜHRUNG
Memory-Leaks. Garbage Collection geht zurück auf die Lisp Systeme, die in
den 1960’er Jahren von McCarthy am MIT entwickelt wurden.
automatische Rückgewinnung von nicht mehr benötigtem Speicher
üblich in Spachen wie Java, Lisp, Perl, ....
Wurzelknoten
erreichbar
nicht
Haldenknoten
erreichbar
149
Schlichter, TU München 5.2. EINFÜHRUNG
Animation Haldenverwaltung
siehe online Version
5.2.3 Fragmentierung
Unter dem Begriff Fragmentierung versteht man verschiedene Formen der
Zerstückelung des noch freien und nutzbaren Teils des Adressraums in kleine
Bereiche. Fragmentierung kann jedesmal dann entstehen, wenn eine neue
Speicherplatzanforderung aus der Menge noch freier Speicherbereiche mit einem
einzigen zusammenhängenden Bereich befriedigt werden muss. Unterscheidung
zwischen externer und interner Fragmentierung.
• Externe Fragmentierung
Es wechseln sich benutzte und unbenutzte Speicherbereiche innerhalb des
Adressraums ab. Speicheranforderungen werden jeweils genau erfüllt.
Anforderung
freie Speicherbereiche
150
Schlichter, TU München 5.2. EINFÜHRUNG
• Interne Fragmentierung
Der Speicher ist in Bereiche fester Größe untergliedert und Speicheranforde-
rungen werden nur in Vielfachen dieser festen Grundgröße befriedigt.
Anforderung
freier Speicherbereich
Der Verschnitt findet innerhalb dieser Bereiche fester Größe statt. Beispiels-
weise kann Plattenspeicher nur blockweise belegt werden; die Blockgröße
schwankt zwischen 512 Byte und 4-8 Kbyte. Selbst für die Speicherung eines
einzigen Bytes muss ein ganzer Block belegt werden.
151
Schlichter, TU München 5.3. SPEICHERABBILDUNGEN
5.3 Speicherabbildungen
Dieser Abschnitt behandelt einige Mechanismen zur Abbildung von Programm-
adressen auf Maschinenadressen des Arbeitsspeichers.
152
Schlichter, TU München 5.3. SPEICHERABBILDUNGEN
Verschiebbarkeit,
Programmgröße,
Speicherausnutzung.
Verschiebbarkeit
P1 P2 P3
Programmgröße
153
Schlichter, TU München 5.3. SPEICHERABBILDUNGEN
zerlegen und diese nach Bedarf selbst nachladen. Man spricht von der
sogenannten Overlay-Technik (veraltet). Die Overlay-Technik ist aufwendig,
schwierig und damit auch fehleranfällig. Da die Zerlegung statisch ist, kann
die Zerlegung des Programms nicht dynamisch an den konkret vorhandenen
Arbeitsspeicher angepasst werden und damit die jeweilige Maschine gut
ausnutzen.
• Forderung
Es muss daher gefordert werden, dass die Programmgröße unabhängig von der
realen Arbeitsspeichergröße ist.
Speicherausnutzung
• Forderung
Arbeitsspeicher beinhaltet nur die momentan bzw. in naher Zukunft notwen-
digen Ausschnitte des Programms. Nutzen der Lokalitätseigenschaft von Pro-
grammen:
durch Datenstrukturen z.B. Arrays, oder
Programmstrukturen: Prozeduren, Schleifen.
5.3.2 Basisadressierung
Die Basisadressierung hat eine einfache Abbildungsvorschrift:
Maschinenadresse = Basisadresse + Programmadresse
154
Schlichter, TU München 5.3. SPEICHERABBILDUNGEN
• Speicherverwaltungsstrategien
Aufgabe: Finden eines zusammenhängenden Arbeitsspeicherbereichs, der groß
genug ist, um das Programm zu speichern ⇒ siehe Verfahren zur → Verwaltung
der Halde (siehe Seite 147). Hier kommen die Strategien zum Einsatz, die
bereits bei der Haldenverwaltung diskutiert wurden, insbesondere deren Vor-
und Nachteile. Beispielsweise erfordert best-fit immer den Durchlauf durch die
gesamte Freibereichsliste. Zusätzlich liefert diese Strategie mit der Zeit immer
kleinere Fragmente ⇒ externe Fragmentierung.
– first-fit
Durchsuche die Liste der Freibereiche vom Anfang an und nimm den ersten
passenden Frei-Bereich: Spalte nicht benötigten Speicher ab und füge ihn als
freien Bereich in die Freibereichsliste ein. Problem: am Anfang häufen sich
kleine Reststücke, die bei jeder Suche neu durchsucht werden müssen.
– next-fit
Durchsuche die Liste der Freibereiche nach first-fit, jedoch beginne die Suche
dort, wo man bei der letzten Suche aufgehört hat. Problem von first-fit mit
den kleinen Reststücken am Anfang wird vermieden.
– best-fit
Durchsuche die Liste der Freibereiche vom Anfang an und nimm den
passenden Frei-Bereich, der die Speicheranforderungen des Programms am
besten erfüllt: Spalte nicht benötigten Speicher ab und füge ihn als freien
Bereich in die Freibereichsliste ein.
– worst-fit
Durchsuche die Liste der Freibereiche vom Anfang an und nimm den Frei-
Bereich, der die Speicheranforderungen des Programms am schlechtesten
erfüllt: Spalte nicht benötigten Speicher ab und füge ihn als freien Bereich in
die Freibereichsliste ein.
– Buddy-Systeme
Speicheranforderungen werden in Größen von Zweierpotenzen vergeben,
d.h. eine Anforderung wird auf die nächste Zweierpotenz aufgerundet
Anforderung 280 Bytes ⇒ Belegung von 512 Bytes = 29
In Linux wird dieses Verfahren in Kombination mit der Seitenadressierung
verwendet. Zusammenhängende Kacheln des Arbeitsspeichers werden
mittels des Buddy-Verfahrens zugeordnet.
∗ am Anfang besteht der Arbeitsspeicher aus einem großen Stück. Abhängig
von der Größe des Arbeitsspeichers.
155
Schlichter, TU München 5.4. SEITENADRESSIERUNG
5.4 Seitenadressierung
Die virtuelle Adressierung wurde Ende der 50er Jahre 2 eingeführt. Viele
weiterführende Arbeiten erfolgten dann später im Rahmen des Projektes MAC
und des Systems MULTICS (Vorgänger von UNIX) in den USA in den 60er
Jahren. Ziel ist
Virtualisierung des Speichers,
Verstecken von realen Beschränkungen, wie Speichergröße,
Speicher als sehr großes Feld gleichartiger Speicherzellen zu betrachten.
Die Seitenadressierung ("paging") ist die Grundform der virtuellen Adressierung.
5.4.1 Ansatz
Der Programmadressraum, der sogenannte virtuelle Adressraum eines Prozesses
wird in aufeinanderfolgende Seiten (engl. page) gleicher Größe unterteilt.
Man spricht deshalb von virtuellen Adressen des Prozesses, anstatt von
seinen Programmadressen. Gängige Größen für virtuelle Adressräume heutiger
Architekturen:
232 , also 32-Bit Adressen zum Ansprechen der Speicherzellen.
Fortgeschrittene Architekturen: 264, also 64-Bit Adressen (z.B. Sun ULTRA-
Sparc).
Die Seiten sind keine logische Aufteilung des Speichers. Denkaufgabe: was hat
das für Vor- und Nachteile?
156
Schlichter, TU München 5.4. SEITENADRESSIERUNG
gleich groß. Es ist auch möglich, dass die Seitengröße ist ein Vielfaches der Ka-
chelgröße ist. Im Folgenden wird von gleichen Größen ausgegangen. Typische
Seitengrößen sind 4 - 8 KByte.
– Die Zuordnung, welche Seite in welcher Kachel gespeichert ist, und wo sich
die Seite auf dem Hintergrundspeicher befindet, erfolgt mittels der Seiten-
Kacheltabelle, die die Seitendeskriptoren enthält. Die Zuordnung von Seite
zu Kachel kann sich im Laufe eines Programmablaufes ändern.
– Befindet sich bei einer Befehlsausführung die erforderliche Seite nicht im
Arbeitsspeicher, so löst ein solcher Zugriff eine Unterbrechung aus ⇒
Seitenfehler ⇒ Einlagerung der Seite bei Bedarf ("Demand Paging").
Der Seitenfehler ist eine synchrone Unterbrechung, die vom Betriebssystem
zu behandeln ist, d.h. die geforderte Seite ist in den Arbeitsspeicher zu laden.
Man spricht deshalb auch vom Demand Paging. Nach dem erfolgreichen
Laden der Seite wird der Befehl, der zum Alarm führte, erneut ausgeführt.
Der gesamte Vorgang heißt Seiteneinlagerung (engl. paging).
– Falls eine Seite eingelagert werden muss, aber gleichzeitig bereits alle
Kacheln des Arbeitsspeichers besetzt sind, so muss eine der eingelagerten
Seiten aus dem Arbeitsspeicher verdrängt werden. Man spricht von
157
Schlichter, TU München 5.4. SEITENADRESSIERUNG
Seite 1 von
Kachel 1
P1
Seiten-Kachel
Tabelle
Seite 2 von
... Kachel 2 Auslagern
P1
...
...
..... ... Kachel 3
...
...
... Kachel 4
Seite 1 von ...
P2
Deskriptor
Kachel 5 Einlagern
Seite 2 von Hintergrundspeicher
P2 mit Blöcken
...
.....
Arbeitsspeicher
mit Kacheln
virt. Adressraum von P2
• Vorteile
Bei der Seitenadressierung werden durch eine flexible Speicherabbildung alle
Probleme der → direkten Adressierung (siehe Seite 152) gelöst. D.h. die
Programme können:
verschoben werden,
größer als der Arbeitsspeicher sein,
auch ausschnittsweise im Arbeitsspeicher sein.
– Zusätzliche positive Eigenschaften
158
Schlichter, TU München 5.4. SEITENADRESSIERUNG
5.4.2 Adressabbildung
Bei der Seitenadressierung erfolgt die Umsetzung der Programmadressen, also die
Umsetzung der virtuellen Adressen in Maschinenadressen durch eine Abbildung
von Seiten auf Kacheln. Eine virtuelle Adresse v ist gegeben durch v = (s, w),
wobei s die Seitennummer und w das Offset in der Seite angibt. Die Adresse v
wird abgebildet auf die reale Adresse p = (k, w), wobei k die Kachelnummer
angibt, die die Seite enthält.
s w
Seiten-Kacheltabelle
L
k
k w
D.h. die virtuelle Adresse wird von der CPU nicht direkt auf den Speicherbus
159
Schlichter, TU München 5.4. SEITENADRESSIERUNG
gelegt, sondern an die MMU (Chip oder mehrere Chips) weitergeleitet. Die MMU
berechnet die reale Adresse und legt sie auf den Bus. Falls s > L ist, kann mit Hilfe
des Längenregisters sofort ein Adressierungsfehler entdeckt werden.
Gegeben sei ein 16-Bit virtueller Adressraum und eine Seitengröße von 4K. D.h.
der Adressraum zerfällt in 16 Seiten; man benötigt 4 Bit, um die Seitennummern
zu identifizieren und 12-Bit, um die 4096 Byte innerhalb einer Seite zu
adressieren.
v= 0 0 1 0 0 0 0 0 0 0 0 0 0 1 0 0
present/
s=2 absent Bit
0 010 1
1 001 1
2 110 1
12 bit offset w
3 000 1
wird kopiert
4 100 1
5 011 1
6 000 0
7 000 0
Seiten-
8 000 0 Kacheltabelle
9 101 1
10 000 0
11 111 1
12 000 0
13 000 0
14 000 0
15 000 0
p= 1 1 0 0 0 0 0 0 0 0 0 0 1 0 0
k=6
Die Anzahl der Bits von s (Seitennummer) und k (Kachelnummer) können sich
unterscheiden. Die Zahl der Bits von s hängt von der Größe des virtuellen
Adressraums ab, während sich die Anzahl der Bits von k aus der Größe des
Maschinenadressraums ergibt. Damit können s und k unterschiedliche lang sein.
160
Schlichter, TU München 5.4. SEITENADRESSIERUNG
Die Adressrechnung wird von der Hardware, der MMU (Memory Management
Unit), durchgeführt.
Speicherbus
Arbeits
CPU MMU
speicher
virtuelle physische
Adressen Adressen
161
Schlichter, TU München 5.4. SEITENADRESSIERUNG
virtuelle Adresse
s w
Seitennr Kachelnr
TLB hit
k w
TLB Adresse im
Arbeitsspeicher
Seiten-Kacheltabelle
s
TLB miss
k
162
Schlichter, TU München 5.4. SEITENADRESSIERUNG
5.4.3 Seiten-Kacheltabelle
Die Adressabbildung erfolgt mittels der Seiten-Kacheltabelle (SKT). Wir benöti-
gen Informationen über die zu verwaltenden Seiten. Dazu wird jede Seite eines
Prozesses durch einen Seitendeskriptor beschrieben. Die Seiten-Kacheltabelle ist
i.a. prozessspezifisch. Neben der Zuordnung Seite-Kachel enthält ein Seitende-
skriptor noch weitere Informationen, wie z.B. die Zugriffsrechte und den Zustand
der Seite.
• Zugriffsrechte (A)
Angabe, ob der Prozess
- ausführend (x ∈ A),
- lesend (r ∈ A),
- schreibend (s ∈ A).
auf die Seite zugreifen darf. Diese Information wird vom Betriebssystem
eingetragen und in der CPU vor dem Zugriff ausgewertet.
163
Schlichter, TU München 5.4. SEITENADRESSIERUNG
• Zugriffsbit (r)
Das Zugriffsbit (engl. reference bit) dient zur Unterstützung der Seitenerset-
zungsalgorithmen. Es wird von der CPU nach dem Laden der Seite gelöscht
und bei einem Zugriff auf eine Seite von der CPU gesetzt. Nach einem gewis-
sen Zeitintervall wird es wieder zurückgesetzt.
• Veränderungsbit (m)
Die Seite wurde verändert (modifiziert). Dieses Bit dient ebenfalls zur
Unterstützung der Seitenersetzungsalgorithmen. Es wird nach dem Laden
der Seite von der CPU gelöscht und nach einem schreibenden Zugriff auf
die Seite gesetzt. Beispielsweise könnte eine Verdrängungsstrategie bevorzugt
Seiten auslagern, die nicht modifiziert wurden, d.h. ein Übertragen der Seite
auf den Hintergrundspeicher ist nicht notwendig, da die Seite auf dem
Hintergrundspeicher noch aktuell ist ⇒ man spart sich den Datentransfer.
Probleme
Es gibt einige Probleme mit der Seitenadressierung, die sich auf die Speichereffi-
zienz und die Performanz beziehen.
164
Schlichter, TU München 5.4. SEITENADRESSIERUNG
virtuelle Adresse
s1 s2 w
Deskriptor
Deskriptor k w
Beispielsweise kann ein 32-Bit Adressraum auf der ersten Stufe in 128 Seiten
(27) mit je 32 MByte unterteilt werden. Ein Seitentabellen-Deskriptor verweist
auf eine Seitentabelle, die die 32 MByte große Seite in weitere Seiten unterteilt,
z.B. 256 KByte. Es muss nicht die gesamte Tabelle im Arbeitsspeicher gehalten
werden. Das schrittweise Durchlaufen u. U. mehrstufiger Seiten-Kacheltabellen
nennt man Page-Table Lookup.
3
– Linux verwendet ein 3-stufiges Paging Verfahren
jede virtuelle Adresse ist in 4 Teile aufgeteilt.
• Performanz
Schnelle Umrechnung der virtuellen auf realen Adressen erforderlich, da
Berechnung bei jedem Zugriff notwendig ist! Häufig verwendete Adressen
werden in einem Schnellzugriffspeicher (cache) der MMU gehalten, dem
Translation Lookaside Buffer (TLB).
165
Schlichter, TU München 5.4. SEITENADRESSIERUNG
5.4.4 Seitenfehlerbehandlung
Der Zugriff auf eine Seite, die nicht im Arbeitsspeicher ist, führt zu einem
Seitenfehler.
Arbeitsspeicher
Seiten- Kachel 1
Kacheltabelle
Kachel 2
(4)
(5) Aktuali- Einlagern
(1) Zugriff sieren
Kachel 3
load M
(6) Befehl
erneuert
..... Hintergrundspeicher
mit Blöcken
(2) page fault
166
Schlichter, TU München 5.4. SEITENADRESSIERUNG
1. Beim Zugriff auf eine virtuelle Adresse (z.B. LOAD-Befehl) tritt ein
Seitenfehler auf.
2. Die Adressrechnungshardware löst einen Alarm aus, so dass die Unterbre-
chungsbehandlung des BS aktiviert wird. Dieser wird beispielsweise in der
MMU bei der Adressrechnung ausgelöst. Der Prozesszustand muss gerettet
werden, u.a. der Befehlszähler und die Registerbelegungen. Weiterhin muss der
Unterbrechungsbehandlung die Adresse übergeben werden, die den Seitenfeh-
ler auslöste.
3. Das BS stellt eine freie Kachel zur Verfügung, lokalisiert die Seite auf der
Platte und initiiert die Einlagerung der Seite (Lesen von Platte). Falls aktuell
keine Kachel frei ist, muss eine Seite auf den Hintergrundspeicher verdrängt
werden. Falls die Daten nicht auf der Festplatte vorhanden sind, wird ein
Speicherschutzalarm ausgelöst.
4. Die Seite wird eingelagert.
5. Der Seitendeskriptor wird aktualisiert und verweist jetzt auf die belegte Kachel
(im Beispiel k = 3).
6. Der unterbrochene Befehl wird erneut gestartet. Die Daten sind jetzt
zugreifbar. Dazu muss zunächst wieder der Prozesszustand geladen werden,
d.h. Befehlszähler, Register etc. Anschließend wird der Befehl fortgeführt, als
ob keine Unterbrechung stattgefunden hätte.
5.4.5 Seitenverwaltungsstrategien
Aufgabe der Arbeitsspeicherverwaltung: Laden der für die Ausführung der
Prozesse benötigten Seiten in die Kacheln. Es ergeben sich drei strategische
Aufgaben:
Ladestrategie
• Lösungsansätze
167
Schlichter, TU München 5.4. SEITENADRESSIERUNG
Platzierungsstrategie
• Lösung
Seitenverdrängungsstrategie
Frage: welche Seite ist aus dem Arbeitsspeicher zu entfernen, wenn für eine zu
ladende Seite keine freie Kachel mehr zur Verfügung steht? Im Idealfall baut
ein Verdrängungsverfahren auf der Referenzlokalität vieler Programme (Verbot
von Goto-Befehlen) und der sich ergebenden Lokalitätsmenge auf. Solange
sich die Lokalitätsmenge jedes Prozesses im Arbeitsspeicher befindet, ist die
Seitenfehlerrate sehr gering. Auf der Grundlage der Working-Set-Theorie ergibt
sich damit für ein Seitenverdrängungsverfahren die Aufgabe, bevorzugt solche
Seiten auszulagern, die nicht in der Lokalitätsmenge enthalten sind.
• FIFO Strategie
FIFO (first-in first-out): Verdrängen der ältesten Seite, einfach zu implementie-
ren. Das Verfahren berücksichtigt die Lokalitätsmenge nicht. So werden über
längere Zeit hinweg häufig referenzierte Seiten verdrängt (z.B. Seiten mit Kon-
stanten und globalen Variablen, die am Anfang geladen und häufig referenziert
werden). Umgekehrt bleiben auch wenig referenzierte Seiten im Mittel genau-
so lange im Arbeitsspeicher wie häufig referenzierte Seite. Vorsicht bzgl der
FIFO-Anomalie, d.h. trotz Vergrössern des zur Verfügung stehenden Arbeits-
speichers können u.U. mehr Seitenfehler (d.h. Seiteneinlagerungsoperationen)
auftreten, als bei kleinerem Speicher. (Warum, woran könnte so etwas liegen?
Antwort: FIFO beachtet nicht, wann die Seite zuletzt benutzt wurde. D.h. ei-
ne häufig benutzte globale Variable, die zu einem frühen Zeitpunkt eingelagert
168
Schlichter, TU München 5.4. SEITENADRESSIERUNG
wurde, könnte z.B. dazu führen, dass diese Seite nach dem Entfernen gleich
wieder eingelagert werden muss.)
– Belady’s Anomalie
Zuordnung von zusätzlichen Kacheln an einen Prozess reduziert nicht
notwendigerweise die Anzahl der Seitenfehler. Das Gegenteil ist möglich.
Beispiel:
∗ Aufrufsequenz von benötigten Seitennummern: 1, 2, 3, 4, 1, 2, 5, 1, 2, 3,
4, 5
∗ jeweils 3 Seiten im Arbeitsspeicher:
(1, 2, 3), (2, 3, 4), (3, 4, 1), (4, 1, 2), (1, 2, 5), (2, 5, 3), (5, 3, 4) ⇒ 9
Seitenfehler
∗ jeweils 4 Seiten im Arbeitsspeicher:
(1, 2, 3, 4), (2, 3, 4, 5), (3, 4, 5, 1), (4, 5, 1, 2), (5, 1, 2, 3), (1, 2, 3, 4),
(2, 3, 4, 5) ⇒ 10 Seitenfehler
• Second-Chance
Variante von FIFO, die vermeidet, dass ältere Seiten, obwohl sie häufig benutzt
werden, ausgelagert werden. Neben dem Status "älteste Seite" wird auch
Zugriffsbit r betrachtet:
r = 1: Seite wird an das Ende der FIFO Liste gestellt; r wird auf 0 gesetzt.
Die Seite wird so behandelt, als ob sie neu angekommen wäre.
r = 0: Seite wird ausgelagert; bei Modifikation (m-Bit gesetzt) wird Seite
zurückgeschrieben.
– Clock-Algorithmus
Eine Implementierungsart von Second-Chance ist der Clock-Algorithmus.
4
Die Seiten werden in einem Ring angeordnet. Ein Pointer zeigt auf den
nächsten Kandidat für eine Auslagerung. Falls r=1 ist, wird das Zugriffsbit
zurückgesetzt und der Pointer auf die nächste Seite im Ring gesetzt.
Oft in Kombination mit dem m-Bit (Modifikation).
4
Tanenbaum01 S 238, Stallings S370
169
Schlichter, TU München 5.4. SEITENADRESSIERUNG
Seite 7 Seite 9
r=0 r=0
m=1 m=1
Seite 94
r=0
m=0
Seite 47 Seite 95
r=1 r=1
m=1 m=0
Seite 46 Seite 45
r=1 r=1
m=0 m=0
Verfahren
1. beginnend von der aktuellen Pointerposition suche die erste Seite mit
(r=0, m=0); diese Seite wird ausgelagert. Die Zugriffsbits werden nicht
verändert, d.h. zurückgesetzt.
2. Falls 1. Schritt fehlschlägt, suche nach der ersten Seite mit (r=0; m=1);
diese Seite wird ausgelagert. Von untersuchten Seite wird das r-Bit
zurückgesetzt. Die Zugriffsbits aller untersuchten Seiten werden auf 0
zurückgesetzt.
3. Falls 2. Schritt fehlschlägt, starte von der ursprünglichen Pointerposition;
wiederhole den 1., und falls notwendig, den 2. Schritt. Bei Beginn des 3.
Schritts sind alle R-Bits der im Ring gespeicherten Seiten auf 0 gesetzt.
Dieses Mal wird auf jeden Fall (im 1. Schritt oder spätestens im 2.
Schritt) eine Seite für die Auslagerung identifiziert. Im Prinzip geht der
Algorithmus zyklisch durch die Menge der Seiten, um eine Seite, die nicht
modifiziert und in letzter Zeit nicht referenziert wurde.
• Weitere Strategien
170
Schlichter, TU München 5.4. SEITENADRESSIERUNG
Hardware möglich, die jeder Seite ein Zeitfeld assoziiert und dieses bei
jedem Zugriff aktualisiert.
Frage: wie LRU-Verhalten approximieren
Antwort: Nutzen eines Referenz-Bits (siehe r-Bit der Seitendeskriptor-
Informationen) pro Seite, das durch Hardware bei einem Seitenzugriff
gesetzt wird. Jeder Seite wird ein Zähler zugeordnet. Das BS inspiziert
in regelmäßigen Abständen die Seiten, und inkrementiert den Zähler
der Seiten mit nicht gesetztem Bit. Für jede referenzierte Seite werden
dagegen Zähler und r-Bit gelöscht. Verdrängt wird immer die Seite mit
dem höchsten Zählerstand, da diese am längsten nicht referenziert wurde.
– Working-Set Modell
Working-Set ist die Menge der Seiten, die ein Prozess zu einem bestimmten
Zeitpunkt benutzt.
w(k,t) = Menge der Seiten, die zum Zeitpunkt t in den letzten k
Speicherzugriffen benutzt wurden. t ist hierbei als Position in der
Seitenreferenzfolge zu interpretieren.
die Zahl k kann dynamisch angepasst werden.
t kann hier als Position in der Seitenreferenzfolge interpretiert werden, und
nicht als physikalische Zeit. Bei Windows XP wird für das Working Set ein
Minimum und Maximum spezifiziert; in der Regel ist das Minimum 35 und
das Maximum 345 Seiten.
∗ Verdrängungsstrategie: ersetze eine der Seiten, die nicht zum aktuellen
Working-Set gehören.
∗ Verdrängung einer Seite notwendig, obwohl alle Seiten zu w(k,t) gehören:
verkleinere den Parameter k
Reduziere die Anzahl der Prozesse im Arbeitsspeicher ⇒ Auslagern
eines Prozesses auf die Festplatte (Swapping).
∗ Working-Set kann nur näherungsweise über Zugriffsbits (r) und Verände-
rungsbit (m) bestimmt werden.
– Optimale Strategie: Seite, auf die in Zukunft am längsten nicht zugegriffen
wird. Die optimale Strategie ist unrealistisch, da das zukünftige Verhalten
i.d.R. nicht bekannt ist. Leistungsdaten dieser Strategie, d.h. wieviele
Seitenfehler treten bei gegebener Arbeitsspeichergröße und gegebenen
Zugriffscharakteristika von Prozessen auf, gibt Obergrenze für Erreichbares
an. Die Strategie ist gut für Vergleiche von Algorithmen, d.h. zur
Bestimmung der Güte eines Verfahrens.
171
Schlichter, TU München 5.4. SEITENADRESSIERUNG
• Seitenflattern
Seitenflattern (engl. thrashing) tritt auf, wenn im System zuviele Prozesse
sind, die nebenläufig voranschreiten wollen und Kacheln beanspruchen. Gerade
verdrängte Seiten müssen zu schnell wieder eingelagert werden, das System ist
im schlimmsten Fall nur noch mit Ein- und Auslagern beschäftigt.
172
Schlichter, TU München 5.4. SEITENADRESSIERUNG
Register
+
Seitentabelle
+ Seite
Seiten-Directory
+
mittleres Seiten- +
Directory
• Seitenallokation
aufeinanderfolgende Seiten werden auf zusammenhängende Kacheln abgebil-
det. Auf diese Weise wird die Performanz beim Lesen und Schreiben von Seiten
in bzw. aus dem Arbeitsspeicher erhöht.
Behandlung von Gruppen mit 1, 2, 4, 8, 16, oder 32 Seiten. Auf der x86-
Architektur ist die Seitengröße 4 KBytes. Gruppen von Kacheln werden
gemäß dem Buddy-System vergeben.
• Seitenverdrängung
Anwendung eines modifizierten Clock-Algorithmus. Zugriffsbit r wird durch
einen 8-bit Zähler ersetzt.
bei jedem Zugriff wird der Zähler inkrementiert.
Linux dekrementiert periodisch die Zähler aller Seiten im Arbeitsspeicher.
Linux scannt dazu periodisch durch alle Seiten, die im Arbeitsspeicher sind,
und dekrementiert jeweils den Zähler. Auf eine Seite deren Zählerwert 0 ist,
wurde seit einiger Zeit nicht mehr zugegriffen und sie wird als Kandidat für
die Auslagerung betrachtet. Eine Seite, auf die in letzter Zeit öfters zugegriffen
wurde, ist eher weniger eine Kandidat für die Auslagerung. Linux realisiert eine
Form der LFU.
173
Schlichter, TU München 5.5. SEGMENT-SEITENADRESSIERUNG
5.5 Segment-Seitenadressierung
Unterteilung des Programmadressraums in logische Einheiten unterschiedlicher
Länge, sogenannte Segmente. Ein Segment umfasst inhaltlich bzw. organisato-
risch zusammengehörige Speicherbereiche, z.B. Daten, Code und Laufzeitkeller-
Segment. Im Gegensatz dazu ist die Seiteneinteilung systembedingt und vom
jeweiligen Programm unabhängig. Die Segmentunterteilung ist programmspezi-
fisch.
• Jedes Segment besitzt eine maximale Größe. Die Länge der einzelnen Segmente
kann unterschiedlich sein und sich dynamisch verändern.
• Jedes Segment besteht aus Seiten, die jeweils beginnend mit Null fortlaufend
numeriert sind.
• Ein Zugriff auf ein nicht existentes Segment führt zum Speicherschutzalarm.
Segmenttabellenregister Seiten-Kacheltabelle
0
Segmenttabelle
0
+ s k
+ sg
Adresse im
Arbeitsspeicher
sg s w
virtuelle Adresse k w
174
Schlichter, TU München 5.6. SPEICHERHIERARCHIE / CACHES
Bei der Adressierung der Tabellen muss natürlich jeder Index mit der Länge eines
Seiten- bzw Segmentdeskriptors multipliziert werden. Falls ein Eintrag 4 Byte
lang ist, ergibt sich damit z.B.
Adresse des Segmentdeskriptors =
Wert Segmenttabellenregister + sg * 4.
Entsprechendes gilt auch für die Seiten-Kacheltabelle.
175
Schlichter, TU München 5.6. SPEICHERHIERARCHIE / CACHES
L5 entfernter Hintergrundspeicher
(entferntes Filesystem)
deshalb okay, wenn Speicher auf Schicht k+1 langsamer und preiswerter
ist.
176
Schlichter, TU München 5.6. SPEICHERHIERARCHIE / CACHES
Daten werden
blockweise kopiert
0 1 2 3
12 13 14 15
• Cache-Fehler (miss): b ist nicht auf Schicht k; Cache muss b von Schicht k+1
holen (z.B. Block 8).
wenn Schicht k Cache voll, muss ein Block entfernt werden, z.B. nach LRU.
Dies ist vergleichbar mit der Verdrängung von Seiten.
177
Schlichter, TU München 5.6. SPEICHERHIERARCHIE / CACHES
178
Schlichter, TU München 5.6. SPEICHERHIERARCHIE / CACHES
179
Schlichter, TU München 5.6. SPEICHERHIERARCHIE / CACHES
Angenommen, wir haben ein System mit CPU, Registern, L1 Cache und
Arbeitsspeicher. Die CPU führt einen Befehle aus, der auf das Speicherwort
w zugreift. w wird vom L1 Cache angefordert. Falls w im L1 Cache vorhanden
ist (Cache Hit), wird w unmittelbar an CPU ausgeliefert. Ansonsten haben wir
einen Cache Miss und die CPU wartet, bis der L1 Cache den Block, der das
Speicherwort w beinhaltet, vom Arbeitsspeicher angefordert und ausgeliefert
bekommen hat. Der Block mit w wird im L1 Cache gespeichert und w wird an
die CPU ausgeliefert. Damit ergibt sich die Folge CPU ⇒ L1 Cache ⇒ ASP.
• Direct-Mapped Cache
Einfachste Art des Caches mit genau einer Reihe pro Menge; Zugriff erfolgt in
der Reihenfolge
Mengenselektion: Benutzung der "set Index" bits zum Bestimmen der
relevanten Menge.
Reihenabgleich: Finden der gültigen Reihe in der selektierten Menge mit
dem richtigen Tag. Da pro Menge nur eine Reihe vorhanden ist, müssen
nur die Tagbits der vorhandenen Reihe mit den Tagbits der Adresse
auf Übereinstimmung verglichen werden. Es ist keine Durchsuchung der
ausgewählte Menge notwendig. Weiterhin muss das "Valid" Bit gesetzt
sein, um anzuzeigen, dass die Reihe gültig ist.
180
Schlichter, TU München 5.6. SPEICHERHIERARCHIE / CACHES
set 0
3
0 1 2 3 5 6 7
set 1 1 0110 w0 w1 w2 w3
1
set 0
0 1 2 3 5 6 7
set 1 1 1001
1
1 0110 w0 w1 w2 w3
3
2
0110 00001 100
=?
tag set Index block offset
set s-1
181
Schlichter, TU München 5.6. SPEICHERHIERARCHIE / CACHES
Daneben gibt es noch einen voll assoziativen Cache (fully assoziative), der
nur aus einer Menge besteht, die alle Cache Reihen aufnimmt. In diesem
Fall entfällt die Mengenselektion und es werden nur gültige Reihen auf ihre
Übereinstimmung mit den Tagbits überprüft. Voll assoziative Caches sind nur
für sehr kleine Caches geeignet, z.B. Translation Lookaside Buffer (TLB) im
virtuellen Speicher, der Einträge in der Seitenkacheltabelle cached.
Betrachten wir 4-Byte Worte. Weiterhin umfasse der Cache nur eine Menge mit
genau einer Reihe.
Ein Cacheblock der Reihe umfasse vier 4-Byte Worte.
pro Matrixelement (vom Typ int) ist ein Wort (d.h. 4 Bytes) notwendig.
die Matrix a[M, N] sei zeilenweise im Speicher abgelegt und passt nicht
vollständig in den Cache. D.h. zunächst alle Elemente der ersten Zeile,
dann die der zweiten Zeile usw. Neben der Summenbildung könnte auch
die Multiplikation zweier Matrizen und die Speicherung der Ergebnisse in
einer dritten Matrix eindrucksvoll die unterschiedlichen Fehlerraten je nach
der Anordnung der Laufschleifen demonstrieren.
• Zeilenweises Aufsummieren
int i, j, sum = 0;
for (i = 0; i < M; i++)
for (j = 0; j < N; j++) sum += a[i][j]
return sum
Fehlerrate der inneren Schleife = 1/4 = 25%. Ausgangspunkt ist ein leerer
Cache. Der Zugriff a[0, 0] führt zum Laden eine Blocks mit den ersten 4
182
Schlichter, TU München 5.6. SPEICHERHIERARCHIE / CACHES
Matrixelementen der 0-ten Zeile in den Cache. Die nachfolgenden Zugriffe auf
a[0, 1], a[0, 2] und a[0, 3] können durch den Cache befriedigt werden. Erst der
Zugriff auf a[0, 4] führt einem Laden eines neuen Blocks in den Cache.
• Spaltenweises Aufsummieren
int i, j, sum = 0;
for (j = 0; j < N; j++)
for (i = 0; i < M; i++) sum += a[i][j]
return sum
Fehlerrate der inneren Schleife = 100%. Beim Zugriff von a[0, 0] werden die
ersten 4 Elemente der ersten Zeile in den Cache geholt. Als nächstes Element in
der inneren Schleife wird a[1, 0] benötigt, was jedoch nicht im Cache ist. Jeder
Zugriff auf eine Matrixelement in der inneren Schleife führt zu einem Cache
Miss.
183
Kapitel 6
Prozesskommunikation
Disjunkte Prozesse, d.h. Prozesse, die völlig isoliert voneinander ablaufen, stellen
eher die Ausnahme dar. Häufig finden Wechselwirkungen zwischen den Prozessen
statt ⇒ Prozesse interagieren. Die Unterstützung der Prozessinteraktion stellt
einen unverzichtbaren Dienst dar. Betrachtet man diese Prozesswechselwirkungen
1
genauer, dann lassen sich 2 grundlegende Interaktionsmuster unterscheiden:
Konkurrenz und Kooperation. Eine Konkurrenzsituation liegt vor, wenn sich
Prozesse gleichzeitig um ein exklusiv benutzbares Betriebsmittel bewerben
⇒ Prozesssynchronisation. Bei Prozesskooperation geht es darum, dass die
beteiligten Prozesse gezielt Informationen untereinander austauschen.
6.1 Fragestellungen
Dieser Abschnitt beschäftigt sich mit den Mechanismen von Rechensystemen
zum Austausch von Informationen zwischen Prozessen.
• Kommunikationsarten.
184
Schlichter, TU München 6.2. EINFÜHRUNG
6.2 Einführung
Prozessinteraktion kann Rechner-lokal und Rechner-übergreifend stattfinden.
Prozesse können auf vielfältige Weise Informationen austauschen.
6.2.1 Kommunikationsarten
Prozesskommunikation
breitbandig schmalbandig
1:m n:m
n:m Ströme
185
Schlichter, TU München 6.2. EINFÜHRUNG
Schmalbandige Kanäle
• Beim Ablauf von Prozessen können Alarme entstehen (z.B. arithmetische Alar-
me). Da das BS keine genauen Kenntnisse über den internen Berechnungszu-
stand eines Prozesses besitzt, kann man mit den allgemeinen Standardalarmbe-
handlungen des BS einen Prozess höchstens abbrechen. Es ist somit sinnvoll,
die Alarmbehandlung dem Prozess selber zu überlassen.
• Die Alarme werden über Namen identifiziert, die im BS vereinbart sind. Das
BS stellt Dienste zur Zustellung von Alarmen zur Verfügung. Bemerkung:
schmalbandige Informationskanäle sind für den Bereich der Datensicherheit
problematisch, da sie schwierig zu beherrschen sind. Über diese Kanäle können
sich Angreifer Informationen über das System beschaffen und ausnutzen.
Beispiel: Einloggen unter Solaris 7.0 liefert bereits nach Eingabe der Kennung
Informationen, dass diese Kennung korrekt ist. Lässt sich für einen Passwort-
Cracking-Angriff ausnutzen.
Im folgenden werden wir uns vertiefend mit breitbandigen Kommunikations-
formen beschäftigen, und zwar nicht nur im lokalen Bereich, sondern auch im
verteilten Bereich.
Implizite Kommunikation
• Die Kommunikation findet ohne direkte Unterstützung und ohne Kenntnis des
BS statt.
186
Schlichter, TU München 6.2. EINFÜHRUNG
• Nachteil:
a) gemeinsame Bereiche sind nicht immer vorhanden: z.B. in physisch
verteilten, vernetzten Systemen gibt es i.d.R. keinen gemeinsamen
Speicher. Eine Ausnahme bilden sogenannte DSM (Distributed Shared
Memory) Realisierungen.
b) gegebenenfalls aufwendiges busy waiting ⇒ Mischform: Ereigniszustel-
lung, d.h. schmalbandige Kommunikation, die das Vorhandensein von Da-
ten signalisiert.
• Implizite Kommunikationsformen
Verschiedene Formen der impliziten Kommunikation
1:1 ein Puffer pro Sender/Empfänger-Paar
n:1 n Sender senden Nachrichten an einen Empfänger, z.B.
Sender: Prozesse senden Druckaufträge
Empfänger: Drucker-Server
187
Schlichter, TU München 6.2. EINFÜHRUNG
S1 S1 Sn S1 Sn
prozess- prozess-
spezifischer spezifischer
Briefkasten
oder oder
(mail box)
zentraler zentraler
Puffer Puffer
E1 E1 E1 Em
Si i-ter Senderprozess
Ei i-ter Empfängerprozess
Explizite Kommunikation
• prinzipieller Ablauf
Der Nachrichtendienst ND ist meist Teil des Betriebssystemkerns.
188
Schlichter, TU München 6.2. EINFÜHRUNG
Nachricht m Nachricht m
Sende Nachrichten Empfänger
prozess S dienst ND prozess E
send receive
Falls die Prozesse auf unterschiedlichen Rechnern sind, sind die Nachrichten-
dienste der beteiligten Betriebssysteme involviert. In diesem Fall findet eine
Kommunikation zwischen den beiden Nachrichtendiensten statt.
Vielfach CPU-
Systeme
189
Schlichter, TU München 6.3. NACHRICHTENBASIERTE KOMMUNIKATION
190
Schlichter, TU München 6.3. NACHRICHTENBASIERTE KOMMUNIKATION
Klassifikationsschema
191
Schlichter, TU München 6.3. NACHRICHTENBASIERTE KOMMUNIKATION
Es ist auch möglich das Merkmal Synchronität nicht auf die Nachrichtentrans-
aktion, sondern getrennt auf Sender und Empfänger anzuwenden. Damit las-
sen sich asynchrone und synchrone Formen des Nachrichtenversands und -
empfangs beliebig kombinieren.
Meldung
• Asynchrone Meldung
Sender wird lediglich bis zur Ablieferung der Meldung an das Nachrichtensy-
stem (Kommunikationssystem) blockiert.
send
Meldung
receive
Zeit
• Synchrone Meldung
Sender und Empfänger von Meldungen sind zeitlich gekoppelt.
192
Schlichter, TU München 6.3. NACHRICHTENBASIERTE KOMMUNIKATION
send Meldung
receive
Quittung
Zeit
Über die Ablieferung der Nachricht wird der Sender durch eine Quittungsnach-
richt informiert, die zur Aufhebung der Blockade des Senders führt.
Auftrag
• Synchroner Auftrag
Bearbeitung der Nachricht durch Empfänger und Senden der Resultatnachricht
sind Teil der Nachrichtentransaktion.
193
Schlichter, TU München 6.3. NACHRICHTENBASIERTE KOMMUNIKATION
Auftrags
bearbeitung
Resultat reply
Zeit
• Asynchroner Auftrag
Auftrag und Resultat werden als Paar unabhängiger Meldungen verschickt.
194
Schlichter, TU München 6.3. NACHRICHTENBASIERTE KOMMUNIKATION
Auftrags
bearbeitung
receive Resultat reply
result
Zeit
Zwischen send und receive result kann der Sender u.U. noch weitere
Aufträge versenden (an den gleichen oder andere Empfänger).
195
Schlichter, TU München 6.3. NACHRICHTENBASIERTE KOMMUNIKATION
– Entwurf und Nachweis der Korrektheit des Systems ist schwierig. Auftreten
von Fehlern abhängig von Pufferinhalten und dem Zeitverhalten des
verteilten Systems (Last des Kommunikationssystems).
196
Schlichter, TU München 6.3. NACHRICHTENBASIERTE KOMMUNIKATION
Sendebereit
send receive
message message
buffer full
Prozess 1 wait Prozess 2
for message
ack. received
receive
send
ack.
ack.
buffer full
Dies trifft auf, wenn das Acknowledgement nicht gesendet wird oder verloren
geht. Pragmatische Lösung mit Hilfe von Timeouts
• Sender bzw. Empfänger warten nur eine festgelegte Zeit, Sender: falls kein
Acknowledgement (Quittung) eintrifft, z.B. erneutes Senden.
6.3.4 Ports
Bisher wurde davon ausgegangen, dass ein Prozess eine Nachricht mittels
receive in seinen Adressraum entgegennehmen kann. Dazu wurde jedem
Prozess ein eigener Nachrichtenpuffer für neu eingetroffene, jedoch noch nicht
abgelieferte Nachrichten zugeordnet. Bisher bestand zwischen Sender und
Empfänger eine feste Beziehung, die über Prozessidentifikatoren (z.B. Namen
oder Nummer) hergestellt wurde. Nachteile
197
Schlichter, TU München 6.3. NACHRICHTENBASIERTE KOMMUNIKATION
• ein Port ist mit dem Adressraum des zugehörigen Prozesses verbunden.
• ein Rechner mit einer IP-Adresse unterstützt mehrere tausend Ports. Für das
TCP-Protokoll sind es 65 535 unterstützte Ports.
• der Name des Ports ist für einen Rechner eindeutig. Ein Betriebssystem
verwaltet eine bestimmte Anzahl von Ports, die es entweder fest oder
dynamisch verschiedenen Protokollen bzw. deren zugehörigen Applikationen
zuordnen kann.
• die Portnummern 1 - 1023 sind fest reserviert für bestimmte Protokolle (bzw.
deren Applikationen).
198
Schlichter, TU München 6.3. NACHRICHTENBASIERTE KOMMUNIKATION
6.3.5 Kanäle
Bisher wurde von einer verbindungslosen Kommunikation ausgegangen, d.h. eine
Nachricht kann an einen Port geschickt werden. Bei einer verbindungsorientierten
Kommunikation muss zuerst eine logische Verbindung zwischen den Kommuni-
kationspartner eingerichtet werden ⇒ Kanal ("socket").
• bidirektionale Übertragung über Kanäle. Ports sind nicht mehr nur Empfangs-
stellen für Nachrichten, sondern sie dienen auch als Quellen. Damit sind kom-
plexere Auftragsbeziehungen zwischen den Kommunikationspartnern möglich.
Beispielsweise müssen nicht alle benötigten Daten in der Auftragsnachricht
mitgeschickt werden, sondern sie können bei Bedarf vom beauftragten Prozess
angefordert werden.
• Die Sende- bzw. Empfangsoperation bezieht sich auf die lokale PortID;
199
Schlichter, TU München 6.3. NACHRICHTENBASIERTE KOMMUNIKATION
6.3.6 Ströme
Ströme (engl. streams) sind eine Abstraktion von Kanälen. Sie verdecken die
tatsächlichen Nachrichtengrenzen. Ein Sender schickt mittels send-Operationen
Nachrichten an den Empfänger. Die Nachrichten werden jedoch logisch zu
einem Bytestrom vereinigt, dem man auf Empfangsseite die Nachrichtengrenzen
nicht mehr entnehmen kann. Der Empfänger kann den Bytestrom in Portionen
verarbeiten, ohne sich an den ursprünglichen Nachrichtengrenzen zu orientieren.
Empfänger
1 Byte
• Dienste für Dateizugriffe oder Zugriffe auf Geräte: spezielle Ausprägung der
stromorientierten Kommunikation.
6.3.7 Pipes
Realisierung von Strömen über Pipe-Konzept (z.B. in Unix, Windows); Strom
zwischen 2 Kommunikationspartnern
unidirektional
200
Schlichter, TU München 6.3. NACHRICHTENBASIERTE KOMMUNIKATION
Prozess 1 Prozess 2
Schreiben Lesen
201
Schlichter, TU München 6.3. NACHRICHTENBASIERTE KOMMUNIKATION
– Kinderprozesse
Kind 1 liest aus der Pipe, während Kind 2 in die Pipe schreibt.
202
Schlichter, TU München 6.3. NACHRICHTENBASIERTE KOMMUNIKATION
/* Kind 1 */
main (int argc, char *argv[]) {
char buffer[100];
read(0, buffer, 28); /* Prozess liest von Pipe */
write(1, buffer, 28); /* schreibt auf Standard Aus */
exit(0);
}
/* Kind 2 */
main (int argc, char *argv[]) {
write(1, "Dies erscheint in der Queue\n", 28);
exit(0);
}
Das Lesen der pipe erfolgt durch read(fhandle[0], block, anzahl). Ist
die Pipe beim read-Aufruf leer, so wird der Prozess blockiert.
• Named Pipes
Problem: nur Prozesse, die über fork() eng miteinander verwandt sind, können
im Beispielprogramm kommunizieren.
Einführung von Named Pipes, die mittels mknod erzeugt werden.
ermöglicht die Kommunikation zwischen Prozessen, die nicht miteinander
verwandt sind.
main (int argc, char *argv[]) {
int rc;
mknod("myfifo", 0600, S_IFIFO);/* 0600 spezifiziert die
Zugriffsrechte.*/
if (rc == 0) {
int fd;
fd = open("myfifo", O_WRONLY);
write(fd, "Satz 1\n", 7);
close(fd);
exit(0)
} else {
int fd;
char block[20];
fd = open("myfifo", O_RDONLY);
rc = read(fd, block, 7);
write(1, ":", 1);
if (rc > 0) { write(1, block, rc); }
else printf("Fehler: %d\n", rc);
close(fd);
exit(0)
}
}
203
Schlichter, TU München 6.4. CLIENT-SERVER-MODELL
6.4 Client-Server-Modell
Client-Server Modell basiert i.a. auf der Kommunikationsklasse der synchronen
Aufträge. Server stellen Dienste zur Verfügung, die von vorher unbekannten
Clients in Anspruch genommen werden können. Der Client ruft die Operation
eines Servers auf; nach Ausführung der Operation wird das Ergebnis an Client
übergeben. Während der Ausführung der Operation wird Ablauf des Client meist
unterbrochen. Eine leere Antwort ist möglich, falls die Operation kein Ergebnis
liefert (z.B. Eintrag einer Informationseinheit in eine Datenbank).
• Client-Server Architektur
Client C Server S
Auftrag
blockiert
Ausführung
Resultat
Zeit
• Definitionen
– Definition: Client
Ein Client ist eine Anwendung, die auf einer Clientmaschine läuft und i.a.
einen Auftrag initiiert, und die den geforderten Dienst von einem Server
erhält.
Clients sind meist a-priori nicht bekannt. Clients sind oft Benutzerprozesse,
die dynamisch erzeugt und gelöscht werden.
– Definition: Server
Ein Server ist ein Subsystem, das auf einer Servermaschine läuft und einen
bestimmten Dienst für a-priori unbekannte Clients zur Verfügung stellt. Es
existiert eine einfache n:1 Auftragsbeziehung zwischen den Clients und
einem Server.
204
Schlichter, TU München 6.4. CLIENT-SERVER-MODELL
• Multi-Tier
ein System kann sowohl Client als auch Server sein.
Server
Client Server
Client
– Beispiel
205
Schlichter, TU München 6.4. CLIENT-SERVER-MODELL
SQL
Daten
bank
• Peer-to-Peer Computing
Es findet keine Unterscheidung zwischen Client und Server statt
⇒ Systeme übernehmen beide Rollen, d.h. sie sind sowohl Client als auch
Server (Peers).
Damit soll der Server-Flaschenhals eliminiert werden.
206
Schlichter, TU München 6.5. NETZWERKPROGRAMMIERUNG
6.5 Netzwerkprogrammierung
Bedingt durch rasche Verbreitung des Internet hat auch das Interesse an Netz-
Anwendungen sehr zugenommen. Netz-Anwendungen sind verteilte Anwendun-
gen, die jeweils aus mehreren Teilkomponenten bestehen und die im Netz verteilt
auf verschiedenen Rechensystemen ausgeführt werden. Teilkomponenten sind
hier nicht einzelne Objekte, sondern komplexe Verarbeitungseinheiten (z.B. ein
Modul bestehend aus einer Menge von Objekten). Eine verteilte Anwendung ist
eine Anwendung A, dessen Funktionalität in eine Menge von kooperierenden Teil-
komponenten A1, .., An, n ∈ IN, n > 1 zerlegt ist;
Jede Teilkomponente umfasst Daten (interner Zustand) und Operationen, die
auf den internen Zustand angewendet werden.
6.5.1 Einführung
In Berkeley Unix wurde das Konzept von Sockets eingeführt, um die
Netzwerkprogrammierung zu erleichtern. Sie erlauben jede Netzverbindung
als einen Strom von Bytes zu betrachten, die gelesen bzw. geschrieben
werden können. Ein Socket definiert einen einfachen, bidirektionalen →
Kommunikationskanal (siehe Seite 199) zwischen 2 Rechensystemen, mit Hilfe
dessen 2 Prozesse über ein Netz miteinander kommunizieren können.
207
Schlichter, TU München 6.5. NETZWERKPROGRAMMIERUNG
Input Strom
Client Server
Output Strom
Socket Verbindung
Socket Grundlagen
Sockets abstrahieren von den technischen Details eines Netzes, z.B. Übertra-
gungsmedium, 2 Paketgröße, Paketwiederholung bei Fehlern, Netzadressen. An-
fänglich standen Sockets nur in Unix Umgebungen zur Verfügung. In der Zwi-
schenzeit werden sie auch von Windows, dem MacOs und von Java unterstützt.
208
Schlichter, TU München 6.5. NETZWERKPROGRAMMIERUNG
1. Erzeugen eines SocketServer und Binden an einen bestimmten Port. Ein Port
entspricht einer FIFO Warteschlange. Sie sammelt die Verbindungswünsche
der Clients. Die maximale Länge ist abhängig vom Betriebssystem, z.B. 50.
Falls die Warteschlange voll ist, werden keine weiteren Verbindungswünsche
akzeptiert.
2. Warten auf Verbindungswünsche von Clients. Falls der Client bzgl. einer
Socketverbindung autorisiert ist, akzeptiert der Server den Verbindungs-
wunsch. Der Server wird blockiert, bis die accept-Methode des Servers die
Verbindung zwischen Client und Server eingerichtet hat. Die beiden Ströme
der Socketverbindung werden eingerichtet.
3. Austausch von Daten zwischen Client und Server entsprechend einem
wohldefinierten Protokoll (z.B. HTTP).
4. Schließen einer Verbindung (durch Server, durch Client oder durch beide);
weiter bei Schritt 2.
• Programmstück
Socket socket; //reference to socket
ServerSocket port; //the port the server listens to
try {
port = new ServerSocket(10001, ...);
socket = [Link](); //wait for client call
// communicate with client
[Link]();
}
catch (IOException e) {[Link]();}
• Für das Abhören des Ports kann ein eigener Verteiler-Thread spezifiziert
werden; die Bearbeitung übernehmen sogenannte Worker-Threads. Der Unix
FTP Server hat früher für jede Verbindung einen eigenen Prozess erzeugt, was
einen großen Overhead verursacht ⇒ FTP Server konnte deshalb oft nicht mehr
als 400 offene Verbindungen unterstützen, falls noch vernünftige Antwortzeiten
erwartet werden.
209
Schlichter, TU München 6.5. NETZWERKPROGRAMMIERUNG
1. Erzeugen einer Socket Verbindung. Dazu muss die Adresse des Servers (z.B.
Internet-Adresse) und der Port, auf dem der Server wartet, angegeben werden.
2. Austausch von Daten zwischen Client und Server über die Duplex-Verbindung
entsprechend einem wohldefinierten Protokoll (z.B. HTTP).
3. Schließen einer Verbindung (durch Server, durch Client oder durch beide).
Programmstück
210
Schlichter, TU München 6.5. NETZWERKPROGRAMMIERUNG
• Constructor
public Socket(String host, int port)
throws UnknownHostException, IOException
Der Parameter host ist ein Rechnername, z.B. [Link]. Falls der
Domain Name Server den Parameter host nicht auflösen kann, wird die
Exception UnknownHostException ausgelöst. Falls die Socket aus einem
anderen Grund nicht geöffnet werden kann, wird IOException ausgelöst, z.B.
der entfernte Host akzeptiert keine Verbindungen. Es gibt noch eine Reihe
anderer Konstruktoren, z.B.
public Socket(InetAddress host, int port) throws IOException
Das Objekt der Klasse InetAddress umfasst den Rechnernamen und seine IP-
Adresse, d.h. eine Auflösung durch den Domain Name Server ist nicht mehr
notwendig.
211
Schlichter, TU München 6.5. NETZWERKPROGRAMMIERUNG
• Constructor
public ServerSocket(int port)
throws IOException, BindException
erzeugt eine Socket auf Server-Seite und assoziiert sie mit dem Port. Falls
die Socket nicht an den angegebenen Port gebunden werden kann, wird
BindException ausgelöst. Es existieren noch weitere Konstruktoren, z.B.
public ServerSocket(int port, int queueLength)
throws IOException, BindException
212
Schlichter, TU München 6.5. NETZWERKPROGRAMMIERUNG
Die Länge der mit dem Port verbundenen Warteschlange wird durch den
Parameter queueLength angegeben.
• ClientServer Klasse
import [Link].*;
import [Link].*;
213
Schlichter, TU München 6.5. NETZWERKPROGRAMMIERUNG
214
Schlichter, TU München 6.5. NETZWERKPROGRAMMIERUNG
215
Schlichter, TU München 6.5. NETZWERKPROGRAMMIERUNG
import [Link].*;
import [Link].*;
216
Schlichter, TU München 6.5. NETZWERKPROGRAMMIERUNG
Dateisysteme
7.1 Fragestellungen
Dieser Abschnitt beschäftigt sich mit den Mechanismen eines Rechensystems zur
dauerhaften (persistenten) Speicherung von Programmen und Daten:
1
[nehmer2001, S 253]
218
Schlichter, TU München 7.2. CHARAKTERISTIKA VON DATEISYSTEMEN
219
Schlichter, TU München 7.3. DATEIEN
7.3 Dateien
Dateien bilden in einem Dateisystem die Behälter für die dauerhafte Speicherung
beliebiger Information. Dabei nutzen nicht nur Benutzerprogramme, sondern auch
die Systemsoftware greift in vielen Fällen auf Dateien zurück. Beispielsweise
wird auch die Auslagerung von Seiten des virtuellen Adressraums über das Datei-
system auf einer sogenannten Auslagerungsdatei (swap Datei) vorgenommen.
• in den meisten Systemen wird eine Datei als eine Folge von Bytes aufgefasst.
Eine Datei beginnt mit dem Byte 0 und endet in Abhängigkeit von ihrer Länge
n mit dem Byte n-1.
• Dateinamen
in manchen Dateisystemen haben Dateinamen die Form "[Link]".
Beispiele für extension: .c, .java, .html, .gif, .pdf, .tex,
.doc, .zip, ....
In einigen Betriebssystemen werden die Datei-Extension sematisch interpretiert
und veranlassen ein bestimmtes Verhalten, z.B. ein Doppel-Click auf eine
".doc"-Datei startet unter Windows die Anwendung Microsoft Word. In
Unix sind Datei-Extensions nur Konventionen. Das Mac Betriebssystem nutzt
keine Extensions, um Applikationen zu triggern; dort wird eine zusätzliche
Ressource-Datei genutzt.
• Dateiaufbau
Die interne Struktur einer Datei hängt von der jeweiligen Nutzung und
Zielsetzung ab, z.B. ASCII Datei besteht aus Zeilen, die mit CR, LF
abgeschlossen sind. MS-DOS verwendet eine Kombination von CR und LF.
Beispiel einer Archivdatei
220
Schlichter, TU München 7.3. DATEIEN
Modulname
Header Datum
Owner
Objekt Modul
Zugriffsrechte
Header
Länge
Objekt Modul
Header
Objekt Modul
• Operationen
Dateisysteme unterstützen die folgenden grundlegenden Systemaufrufe:
open
Öffnen einer Datei; Ergebnis ist ein Dateideskriptor, über den in
nachfolgenden Systemaufrufen auf die Datei zugegriffen werden kann.
Aufruf nach Posix-Standard
int open (
const char *filename,
int flags,
mode_t mode)
flags spezifiziert die Zugriffsart, z.B. lesend, schreibend, erzeugend,
anhängend (append); mode spezifiziert die Zugriffsrechte für neu erzeugte
Dateien. In Windows NT/2000 wird der Systembefehl CreateFile zum Öffnen
einer Datei bzw. zum Erzeugen einer neuen Datei verwendet. Analog zu open
wird als Ergebnis ein Dateideskriptor zurückgegeben (Datentyp Handle). Die
Anzahl der Dateideskriptoren ist beschränkt.
close
Schließen einer Datei; Aufrufparameter ist ein Dateideskriptor. Bei
Terminierung des Prozesses werden alle offenen Dateien automatisch
geschlossen.
221
Schlichter, TU München 7.3. DATEIEN
– Dateipuffer
Zugriffe auf Dateien erfolgen über einen Dateideskriptor und einen
Dateipuffer.
Dateipuffer
Datei
Deskriptor Dateizeiger
Puffer
Pufferposition
Ortsinformation
222
Schlichter, TU München 7.4. MEMORY-MAPPED DATEIEN
1
1
2 1 2 3
3 4
4
4
3
Festplatte
• Beispiel
223
Schlichter, TU München 7.5. VERZEICHNISSE
7.5 Verzeichnisse
Verzeichnisse (engl. directories) erlauben eine hierarchische Strukturierung des
externen Speichers.
224
Schlichter, TU München 7.6. SCHICHTENMODELL
7.6 Schichtenmodell
Ein Dateisystem kann logisch in 3 Schichten unterteilt werden, die zunehmend
höhere Abstraktionen für die Speicherung persistenter Daten anbieten.
Dateiverwaltung
Blockorientiertes Dateisystem
Datenträgerorganisation
7.6.1 Datenträgerorganisation
Unterteilung des gesamten Datenträgers in Blöcke, die von 0 an aufsteigend
durchnummeriert sind. Das auf MS-DOS aufbauende Dateisystem FAT (Windows
95) verwendet lediglich maximal 16 Bit für eine Blocknummer. Bei einer ur-
sprünglichen Blockgröße von 512 Byte können damit externe Speicher mit bis
zu 32 MByte Speicherkapazität angesprochen werden. Zusammenfassung von
Blöcken zu Clustern (32 KByte), um bis zu 2 GByte große Datenträger zu ad-
dressieren; Cluster sind die kleinste Zuteilungseinheit ⇒ interne Fragmentierung.
Defekte
0 0 0 1 0 0 0 0
Blöcke
Freie
0 1 1 0 0 1 0 0
Blöcke
225
Schlichter, TU München 7.6. SCHICHTENMODELL
Eine gängige Realisierung der Listen für freie und defekte Blöcke besteht in
zusammenhängenden Bitvektoren, die auf dem Datenträger selbst gespeichert
werden. Diese Realisierung erlaubt den gleichzeitigen Test von 16, 32 oder 64
Bitpositionen mit Hilfe von Logikoperatoren des Prozessors.
• Blockstruktur
Super- Defekte
Freie Blöcke Block 0 Block 1 Block n
block Blöcke
• jede Datei besteht aus einer Menge von Blöcken, die relativ zum Dateianfang
nummeriert sind. Die Blöcke können entweder zusammenhängend oder verteilt
über den Datenträger zugeteilt werden. Im ersten Fall kann dies zu externer
Fragmentierung führen. Die interne Fragmentierung hängt von der Blockgröße
ab. Dateien werden immer in Vielfachen von Blöcken belegt.
• wesentliche Operationen:
Erzeugen und Löschen von Dateien
Öffnen und Schließen von Dateien
Lesen und Schreiben von Blöcken
226
Schlichter, TU München 7.6. SCHICHTENMODELL
7.6.3 Dateiverwaltung
Bereitstellung von Dateien und Verzeichnissen; Dateien werden über Namen
identifiziert. Unix verwendet Dateideskriptoren (sogenannte i-nodes), die alle
relevanten Dateiattribute einschließlich einer Indexstruktur für die Lokalisierung
der einzelnen Dateiblöcke enthalten. Die Position der ersten 10 Blöcke (bei
einigen Implementierungen auch 12 Blöcke) einer Datei werden direkt im
Deskriptor gespeichert.
I-Node Schutzbits
Link Count
uid
gid
Größe
Adressen der
ersten 10 Blöcke
(manchmal auch 12 Blöcke)
einfach indirekt
zweifach indirekt
dreifach indirekt
Jeder Datei, auch jedem Verzeichnis ist genau ein i-node zugeordnet. i-node
Nummern werden sequentiell vergeben. Sie sind in einem speziellen Block, dem
Superblock, auf der Festplatte zusammengefasst. i-node Nummer werden nach
der Löschung der zugehörigen Datei wiederverwendet.
• Windows NTFS
Grundeinheit ist ein volume, das nur aus einer Sorte Daten besteht:
Dateien, die durchnummeriert sind.
jede Datei hat eine 64-Bit Nummer, bestehend aus 48 Bit Dateinummer und
16 Bit Sequenznummer. Die Sequenznummer wird nach jedem Löschen
der zur Dateinummer gehörenden Datei inkrementiert, so dass man
zwischen der Referenz zu einer gelöschten Datei und einer aktuellen Datei
unterscheiden kann.
Jedes volume hat eine zentrale Tabelle, die Master File Table (MFT), in der alle
Dateien verzeichnet sind.
227
Schlichter, TU München 7.6. SCHICHTENMODELL
Dateisystem
Schnittstelle
Schnittstelle virtuelles
Dateisystem
Lokales entferntes
Dateisystem Dateisystem
• die oberste Schicht stellt die allgemeinen Zugriffsoperationen wie open, read,
write und close bereit.
• die VFS Schicht ermöglicht die eindeutige Repräsentation einer Datei
über Netzwerkgrenzen hinweg. Die VFS Schicht trennt die generischen
Zugriffsoperationen von den aktuellen Implementierungen. Dateien werden mit
Hilfe eines Deskriptors, dem vnode, netzwerkweit eindeutig charakterisiert.
Für das lokale Dateisystem werden vnodes auf den entsprechenden inode
abgebildet. Falls der vnode auf eine entfernte Datei verweist, wird eine
Zugriffsoperation auf entsprechende Kommunikationsnachrichten (z.B. durch
den NFS-Client auf der Basis des NFS Protokolls) abgebildet.
228
Kapitel 8
Ein-/Ausgabe
229
Schlichter, TU München 8.2. SCHICHTEN EINES E/A-SYSTEMS
einheitliches Benennungsschema für die Geräte. Der Name sollte aus einer
Zeichenkette oder Nummer bestehen, und nicht von der Art des Gerätes
abhängen.
Gerätetreiber
Betriebssystem
Unterbrechungsroutinen
Controller
Hardware
Gerät
230
Schlichter, TU München 8.2. SCHICHTEN EINES E/A-SYSTEMS
Systemaufruf
Übertrage Daten in Prozess-
Kann ja BS-Kern Adressraum, melde
Request erledigt
Geräteunabhängige Ergebniscode (Erfolg oder
werden
BS Software Fehlercode)
nein
Send Request zu
BS-Kern
Gerätetreiber
Geräteunabhängige
Blockiere Prozess, falls
BS Software
notwendig
Unterbrechung
231
Schlichter, TU München 8.3. GERÄTEVERWALTUNG
6. Der Gerätetreiber entweder pollt den Controller bzgl. des Zustandes der
Requestdurchführung. Falls der E/A-Request über einen DMA-Controller
erfolgt, wird gewartet bis bei E/A-Ende durch den DMA-Controller eine
Unterbrechung generiert wird.
7. Die Unterbrechungsbehandlung speichert die Unterbrechungsdaten und
signalisiert, die Blockierung des Gerätetreibers aufzuheben.
8. Der Gerätetreiber identifiziert den E/A-Request, der beendet wurde,
bestimmt den Request Status und meldet die Beendigung an den BS-Kern.
9. Der BS-Kern transferriert die Daten und den Returncode in den Adressraum
des Benutzerprozesses, hebt die Blockierung des Prozesses auf und reiht ihn
in die Liste der rechenwilligen Prozesse ein.
10. Wenn der Scheduler dem Prozess die CPU zuordnet, wird der Prozess mit
der Beendigung des Systemaufrufs fortgesetzt.
8.3 Geräteverwaltung
Eine Hauptaufgabe des BS ist die einheitliche Darstellung der unterschiedlichen
E/A-Geräte und Treiber.
Zuordnung von logischen Kanälen zu physischen Geräten.
E/A-System xxTreiber
create() xxcreate()
open() xxopen()
Anwendung Controller
close() xxclose()
Gerät
read() xxread()
Logischer write() xxwrite()
Kanal ioctl() xxioctl()
logische
Kanalnummer Treibertabelle
8.3.1 Gerätetreiber
Treiber sind gerätetyp-spezifisch und sie schaffen die Verbindung zwischen
Anwenderprozessen und den Geräten bzw. deren Controller. Gelegentlich können
232
Schlichter, TU München 8.3. GERÄTEVERWALTUNG
Kommunikation über
Bussystem Kontroller
Prozessor mit System
Signale, Daten
Programmausführung
Befehle, Daten Gerät
(BS mit Treiber,
Anwendung) Register
Zustände, Signale, Daten
233
Schlichter, TU München 8.3. GERÄTEVERWALTUNG
– in vielen Unix Systemen werden alle Geräte unter dem Teilbaum /dev
verwaltet.
– der Dateiname charakterisiert den jeweiligen Typ des E/A-Geräts.
234
Schlichter, TU München 8.3. GERÄTEVERWALTUNG
Standardisierte E/A-Funktionen
• open(): eröffnet einen logischen Kanal zu einem Gerät und liefert einen
Identifikationswert (Deskriptor, Handle) für die anschließende Nutzung. Beim
Dateisystem wird anstelle des Geräts eine einzelne Datei angesprochen.
• read(): liest eine Anzahl von Byte (als Bytestrom) vom Gerät ein.
• ioctl(): dient dazu, die Betriebsart des Geräts zu ändern. Bei einer seriellen
Schnittstelle kann dies z.B. die Übertragungsrate sein.
Wie bereits erwähnt, werden diese generischen Funktionen durch das Betriebssy-
stem auf Funktionen des relevanten Treibers abgebildet.
Pufferung
235
Schlichter, TU München 8.3. GERÄTEVERWALTUNG
BS
Falls keine Pufferung erfolgt, muss sichergestellt werden, dass der von der E/A
betroffene Teil des virtuellen Adressraums des Prozesses nicht ausgelagert wird,
ansonsten kann es passieren, dass das Gerät die E/A nicht ausführen kann, da der
benutzerseitige Puffer gerade auf die Festplatte ausgelagert wurde.
• einfach: auf Puffer wird wechselseitig über BS von Benutzerprozess und Gerät
zugegriffen. Bei der Eingabe füllt das Gerät zunächst den Puffer, anschließend
liest der Prozess die Daten. Während der Bearbeitung des Datenblocks durch
den Benutzerprozess kann das Gerät bereits den nächsten Datenblock in den
Puffer transferieren. Beim Schreiben können die Daten schnell in den Puffer
transferiert werden, womit der Benutzerprozess nach kurzer Zeit weiterarbeiten
kann.
• Wiederholte Pufferung
Pufferung ist ein weitverbreitete Technik; jedoch bei häufiger Pufferung ist
mehrfaches Kopieren der Daten notwendig, darunter leidet die Geschwindigkeit
des Gesamtsystems. Falls das Schichtenreferenzmodell der Rechnernetze
236
Schlichter, TU München 8.3. GERÄTEVERWALTUNG
Benutzer Prozess
Adressraum
BS-Kern
Adressraum
Netzwerk
Controller
Spooling
Benutzerprozesse
P1 Systemprozess
Funktionsaufrufe E/A-System
für Gerät Treiber
Spooler
Pn
Dämon
Spooling Controller
Verzeichnis Gerät
237
Schlichter, TU München 8.4. RAID
8.4 RAID
Erhöhung der Plattenkapazität durch Zusammenschluss von mehreren kleinen
Festplatten zu einer großen virtuellen Platte. Dadurch ergeben sich eine höhere
Geschwindigkeit und eine bessere Zuverlässigkeit.
⇒ RAID = redundant array of inexpensive disks. Früher waren RAIDS
vor allem aus billigen Festplatten zusammengesetzt, um auf diese Weise
kostengünstige Platten zu erhalten. Heute stehen die höhere Zuverlässigkeit
und die hohen Transferraten im Vordergrund; deshalb wird für das "I" statt
"inexpensive" oft "independet" verwendet.
Für das BS sieht RAID wie eine einzelne Festplatte aus.
keine Änderung an Anwendungssoftware notwendig, um ein RAID-System
nutzen zu können.
• Daten werden über die Platten verteilt, was eine parallele Verarbeitung
ermöglicht.
• RAID Level 0
Der gesamte Speicherbereich der virtuellen Festplatte wird in gleich große
Abschnitte ("strips"), z.B. 1 Block oder 1 Sektor. Die Strips werden nach dem
Round-Robin Strategie auf die physischen Platten verteilt;
Datenpuffer umfasst mehr als einen Strip ⇒ Verteilung auf mehrere Platten.
In diesem Fall zerlegt der RAID Controller den Schreibbefehl in einzelne
Kommandos, einen für jede betroffene Platte. Die Befehle für jeden Platte
werden dann parallel ausgeführt. Damit haben wir parallele Ein-/Ausgabe,
ohne dass die Anwendungssoftware etwas davon mitbekommt.
238
Schlichter, TU München 8.4. RAID
• RAID Level 1
Es werden alle Platten verdoppelt. Im Beispiel existieren 2 Hauptplatten und 2
Backup-Platten.
Bei einem Schreibvorgang wird jeder Strip doppelt geschrieben.
Bei einem Lesevorgang können beide Platten genutzt werden.
Sehr gute Ausfallsicherheit.
Während die Schreibgeschwindigkeit nicht besser gegenüber einer einzelnen
Platte ist, erhöht sich die Lesegeschwindigkeit durch die parallele Nutzung von
Haupt- und Backup-Platten.
Spiegelplatten
• RAID Level 2
Striping erfolgt auf Bitebene mit zusätzlichen Parity-Platten. Beispielsweise
wird jedes Byte in 4-Bit Stücke unterteilt, zusätzlich wird ein 3-Bit Hamming
Code generiert. Dadurch lassen sich Bitfehler nicht nur erkennen, sondern auch
korrigieren.
Alle Platten arbeiten synchron.
239
Schlichter, TU München 8.5. DISK SCHEDULING
Sehr gute Ausfallsicherheit, mit weniger Platten als bei RAID Level 1.
Paritybits
240
Schlichter, TU München 8.5. DISK SCHEDULING
für jeden Zylinder in einer verketteten Liste abgespeichert sind. Falls die Liste
der offenen E/A-Requests jeweils nur einen Auftrag enthält, verhalten sich alle
Algorithmen wie FCFS.
• FCFS Scheduling
Die E/A-Requests werden in der Reihenfolge ihres Eintreffens abgearbeitet
(First Come-First Served). Angenommen die E/A-Requests betreffen Blöcke
der Zylinder
98, 183, 37, 122, 14, 124, 65, 67. "Der Arm stehe zu Beginn beim Zylinder
53."
Problem dieses Verfahrens ist, dass der Arm je nach E/A-Request sehr viel
bewegt werden muss, so dass viel Suchzeit notwendig ist. Für dieses Beispiel
sind insgesamt 640 Zylinderbewegungen notwendig.
• SSTF Scheduling
Beim SSTF-Verfahren (Shortest Seek Time First) wird als nächstes der
E/A-Request bearbeitet, der am nächsten zur aktuellen Position ist. Die
Ausgangsliste
98, 183, 37, 122, 14, 124, 65, 67 wird umsortiert zur Bearbeitungsreihen-
folge
65, 67, 37, 14, 98, 122, 124, 183. Der Arm stehe zu Beginn beim Zylinder
53.
241
Schlichter, TU München 8.5. DISK SCHEDULING
Dieses Verfahren ist vergleichbar mit der Strategie Shortest-Job-First bei der
Rechnerkernvergabe. In dem Beispiel sind nur mehr 236 Zylinderbewegungen
notwendig.
Es kann jedoch zum Verhungern von E/A-Requestes kommen, wenn neue E/A-
Aufträge eintreffen, deren Zylinderpositionen näher an den gerade aktuellen
Positionen liegt. Angenommen die Abarbeitungsfolge enthält die Reihenfolge
14 und anschließend 183. Während der Bearbeitung von 14 trifft ein neuer
Auftrag, der näher bei 14 liegt, dann wird dieser zunächst behandelt.
Währenddessen trifft wieder ein Auftrag, der näher bei 14 liegt, dann wird
dieser wieder der 183 vorgezogen. Der Algorithmus bewegt sich also von 14
weg und wieder zurück, ohne jedoch bis zu 183 zu gelangen ⇒ vergleichbares
Problem bei Aufzügen in Hochhäusern.
• SCAN Scheduling
Der SCAN-Algorithmus bearbeitet die E/A Requests zunächst in eine Richtung
bis zum Plattenende, und anschließend zurück zum anderen Plattenende. Die
Ausgangsliste
98, 183, 37, 122, 14, 124, 65, 67 wird umsortiert zur Bearbeitungsreihen-
folge
37, 14, 65, 67, 98, 122, 124, 183. Der Arm stehe zu Beginn beim Zylinder
53 und es wird angenommen, dass er sich in Richtung Zylinder 0 bewegt.
242
Schlichter, TU München 8.6. MULTIMEDIA SYSTEMS
• lokales Playback. Die Mediendaten werden vom Server herunter geladen und
im lokalen Dateisystem gespeichert. Von dort werden sie dann abgespielt, z.B.
Laden und Abspielen eines Films oder MP3-Datei auf dem Laptop.
• Streaming
Zustellung der Mediendaten von einem Server über ein Netzwerk zum Client.
Der Client beinhaltet die Abspielsoftware. Er kann ein PC oder ein mobiles
Endgerät sein. Unterscheidung zwischen
243
Schlichter, TU München 8.6. MULTIMEDIA SYSTEMS
Disk Scheduling
244
Schlichter, TU München 8.6. MULTIMEDIA SYSTEMS
Zeit
0
Auftrag Deadline Zylinder A
A 150 25 D
B 201 112
C 399 95
D 94 31 I
J
E 295 185 F C
100 H
F 78 85 B
G 165 150
H 125 101
I 300 85 G
J 210 90
E
199
Zur ersten Gruppe (0-100ms) gehören die Aufträge D und F, zur zweiten
Gruppe (101-200ms) die Aufträge A, G und H, zur 3. Gruppe (201-300ms)
die Aufträge B, E und J sowie zur letzten Gruppe (301-400ms) die Aufträge C
und I.
245
Kapitel 9
Sicherheit in Rechensystemen
9.1 Fragestellungen
Dieser Abschnitt behandelt die Sicherheitsproblematik in zentralen Rechensyste-
men. Dazu werden verschiedene Schutzmechanismen auf Betriebssystemebene
vorgestellt.
• Zugriffsschutz in Rechensystemen.
• Mobiler Code.
9.2 Motivation
Was versteht man unter Sicherheit im Bezug auf Rechensysteme?
246
Schlichter, TU München 9.2. MOTIVATION
zu tun.
innen. "Der Angreifer ist in das Rechensystem bereits eingeloggt und ver-
schafft sich illegalen Zugriff auf Ressourcen oder Berechtigungen, z.B.
Systemadministrator-Rechte. Mögliche Angriffstechniken sind Trojanische
Pferde, Login-Attrappen, die Nutzung von Hintertüren in einem Software-
system ("trap door"), Phishing zum Abgreifen von Passwörtern oder die
Ausnutzung eines künstlich herbeigeführten Pufferüberlaufs."
außen. "Durch die Vernetzung von Rechnern finden verstärkt auch Angriffe
von entfernten Rechnern über ein Rechnernetz (z.B. das Internet) statt.
Beispiele für mögliche Angriffstechniken sind sogenannte "war-dialer"
(Ausprobieren von Telefonnummern und Passwörtern) oder die Verbreitung
von Viren."
• Beispiel: Login-Attrappe
Nutzung von Login-Attrappen in Rechnerumgebungen, wo Rechner von
mehreren Benutzern verwendet werden, um geschützte Benutzerpasswörter zu
erfassen (z.B. in Informatikhalle der Informatik-Fakultät).
247
Schlichter, TU München 9.2. MOTIVATION
• Beispiel: Virus
Ein Virus ist ein Programm, dessen Code an ein anderes Programm anfügt ist
und sich auf diese Weise reproduziert. 1 Zusätzlich kann ein Virus noch andere
Funktionen aufrufen, z.B. Löschen von Dateien, Senden von Nachrichten etc.
Oft ist die Reproduktion des Virus und die Ausführung der Virusfunktion zeitlich
getrennt, d.h. die Virusfunktion wird erst nach Eintreten eines bestimmten
Datums getriggert. Dadurch wird erreicht, dass sich ein Virus relativ unbemerkt
ausbreiten kann (z.B. über das Internet), ohne dass die Benutzer bereits
frühzeitig merken, dass ihr Rechner mit dem Virus infiziert ist.
Virus schläft bis infiziertes Programm ausgeführt wird.
Start des infizierten Programms führt zur Virusreproduktion.
Ausführung der Virusfunktion ist u.U. mit einem zeitlichen Datum
versehen.
mögliche Virustypen sind
1
[Tanenbaum2001, S 617]
248
Schlichter, TU München 9.2. MOTIVATION
– Boot Sector Virus. BIOS liest beim Start des Rechners den Master Boot
Record (MBR) und führt ihn aus. Ein Boot Sector Virus trägt sich im MBR
ein und wird damit bei Rechnerstart jeweils ausgeführt. Der ursprüngliche
MBR Inhalt wird oft auf einen anderen Platz der Festplatte kopiert und
von Virus automatisch aufgerufen, um den Rechnerstart zu ermöglichen.
Nach dem Start speichert sich der Virus oft im Speicherbereich des
Unterbrechungsvektors, um nach jedem Systemaufruf wieder die Kontrolle
zu erhalten.
– Macro Virus. Programme wie Word oder Excel erlauben dem Benutzer
das Schreiben von Macroprogrammen (Visual Basic). Beispielsweise kann
ein Angreifer für ein Word-Dokument ein Macro schreiben, das mit der
Open File Funktion verbunden ist. Integriert in das Macro ist der Virus
des Angreifers. Da Macros i.a. alle Systemfunktionen des Betriebssystems
aufrufen dürfen, hat der Virus Zugriff auf die volle Funktionalität. Die
Verbreitung erfolgt durch Versenden des Dokuments, z.B. als Email
Attachment. Öffnen des Dokuments führt zur Ausführung des Macros und
damit des Virus.
– Ausführbares Programm als Virus. Das Virusprogramm sucht nach seinem
Aufruf nach geeigneten ausführbaren Programmen (z.B. "exe Dateien") im
gesamten Dateiverzeichnis und infiziert diese mit dem Virus; beispielsweise
durch Überschreiben des Binärprogramms mit dem Virusprogramm. Die
Länge der Datei wird dadurch verändert (kann genutzt werden durch
Antivirenprogramme, um den Virus zu erkennen).
– Verbreitung von Viren
Früher diente der Austausch von Datenträgern (z.B. Floppy Disk), jetzt das
Internet
als Attachment zu Emails
Lesen des Adressbuchs und automatische Generierung von Emails
mit Virus Attachment an alle Adressbucheinträge (z.B. von Microsoft
Outlook). Dabei wird oft das Subject-Feld so besetzt, dass der Empfänger
das Gefühl hat, er empfange eine persönliche Email von einem
Bekannten.
• Beispiel: Pufferüberlauf
Durch einen künstlich herbeigeführten Pufferüberlauf kann ein Angreifer die
Ausführung seines eigenen Programms veranlassen und oft auch noch die
Systemadministrator-Berechtigung (root) erlangen. 2
2
[Tanenbaum2001, S 610]
249
Schlichter, TU München 9.2. MOTIVATION
– Hintergrund
Die meisten C-Compiler und Laufzeitsysteme überprüfen nicht die Einhal-
tung der Feldgrenzen. Da viele aktuelle Betriebssysteme auf der Basis von C
realisiert wurden, ist diese Problematik von großer Bedeutung.
int i;
char c[256];
i = 12000;
c[i] = 0;
Die Codesequenz ist zwar falsch. Das Laufzeitsystem führt jedoch keine
Überprüfung durch; der Fehler bleibt unentdeckt. In den meisten Fällen
führt dieser Fehler über kurz oder lang jedoch zu einem Programmabsturz
(oft ein Nullpointer). Ein Angreifer kann diese Eigenschaft nutzen, um
Teile des Laufzeitkellers zu überschreiben. Ein Beispiel wäre, das Feld
c für die Speicherung des Pfadnamen einer Datei vorzusehen. Da das
Betriebssystem nur maximal 256 Zeichen pro Pfadenamen unterstützt, ist
für den Programmierer die Länge von c ausreichend. Ein Angreifer kann nun
einen Datei-Pfadnamen angeben, der erheblich länger als 256 ist.
∗ String Library in C
Implementierung der Unix Funktion gets (get string from stdin)
keine Möglichkeit zur Spezifikation der Anzahl der zu lesenden
Zeichen
char *gets(char *dest) {
int c = getc();
char *p = dest;
while (c != EOF && c != ’\n’) {
*p++ = c; c = getc();
}
*p = ’\0’;
return dest;
}
◦ ähnliche Probleme auch bei anderen Unix Funktionen
strcpy: kopiert einen String beliebiger Länge
scanf, fscanf, sscanf: mit %s Konvertierungsspezifikation.
wobei scanf("...", liste der Variablen) gilt.
◦ Angreifbarer Buffer Code
void echo() {
char buf[4]; /* sehr klein */
gets(buf);
puts(buf);
}
250
Schlichter, TU München 9.2. MOTIVATION
int main() {
printf("Type a string:");
echo();
return 0;
}
unix> bufdemo
Type a string: 123
123
unix> bufdemo
Type a string: 12345
Segmentation Fault
Rückkehradresse Information
für UP Aufruf
[3] [2] [1] [0] buf
Keller von echo
251
Schlichter, TU München 9.3. SCHUTZMECHANISMEN
– Gegenmaßnahmen
Unterscheidung
sichere Programmierung. Durch sorgfältige Programmierung, bei der ins-
besondere alle Eingabewerte geprüft und Bereichsgrenzen kontrolliert,
kann man verhindern, Ziel von Buffer Overflow Angriffen zu werden.
Maßnahmen zur Übersetzungszeit. Ein StackGuard Tool fügt ein
spezielles Kontrollzeichen direkt hinter die Rücksprungadresse auf dem
Stack ein. Zusätzlich wird automatisch Code hinzugefügt, der vor dem
Rücksprung überprüft, ob das Kontrollzeichen verändert wurde.
Maßnahmen zur Laufzeit. Das Java Laufzeitsystem überprüft zur
Laufzeit die Einhaltung der Bereichsgrenzen automatisch.
9.3 Schutzmechanismen
Schutz von gespeicherter Information vor Diebstahl, unerwünschter Manipulation
und Verletzung der Vertraulichkeit ist ein zentrales Anliegen in allen Mehrbenut-
zersystemen. 3 Der Schutz sollte jedoch so organisiert werden, dass dadurch der
gewollte Austausch sowie die gemeinsame Nutzung von Programmen und Daten
zwischen den beteiligten Nutzern nicht unnötig eingeschränkt werden. Die Forde-
rung ist ein flexibles Schutzkonzept, das an die Anwendungsumgebung angepasst
werden kann.
3
[Nehmer2001, S 293]
252
Schlichter, TU München 9.3. SCHUTZMECHANISMEN
9.3.1 Anforderungen
Für einen Schutzmechanismus gelten die folgenden Anforderungen
• alle Objekte eines Systems müssen eindeutig und fälschungssicher identifiziert
werden. Insbesondere muss auch der Aufrufer eines Dienstes eindeutig
und fälschungssicher identifiziert werden. Dies ist gerade für Client-Server
Beziehungen von großer Bedeutung, z.B. die eindeutige Identifizierung des
Client bei Ecommerce Anwendungen.
• externer Benutzer eines Systems muss eindeutig und fälschungssicher identifi-
ziert werden ⇒ Authentifizierung. Die Zuordnung zu einem Benutzerprozess
muss fälschungssicher sein.
• Zugriff auf Objekte sollte nur über zugehörige Objektverwaltung geschehen.
• Zugriff auf Objekte nur, wenn Zugreifer die nötige Rechte hat.
• Rechte müssen fälschungssicher gespeichert werden; Weitergabe von Rechten
darf nur kontrolliert erfolgen.
• Prinzip der minimalen Rechte. Jedem Programm oder Benutzer sollen für die
Objekte nur die Rechte eingeräumt werden, die für die momentane Arbeit
zwingend erforderlich sind. Beispielsweise werden unnötige Ports geschlossen.
• grundlegenden Schutzmechanismen sollen ohne großen Aufwand überprüft
werden können. Dies bedeutet, dass am besten ein einheitliches Schutzkonzept
für alle zu schützenden Objekte verwendet wird, und dass die Implementierung
zentral in einem möglichst kleinen Baustein, einem Schutzkern im Betriebssy-
stem, erfolgt.
253
Schlichter, TU München 9.3. SCHUTZMECHANISMEN
9.3.3 Schutzmatrix
Das Konzept der Schutzmatrix wurde von B. Lampson eingeführt. Es verknüpft
Schutzdomänen mit den zu schützenden Objekten.
• Schutzdomänen
Definition: Eine Schutzdomäne ist eine Menge von (Objekt, Rechte) Paaren.
"Jedes Paar spezifiziert ein Objekt und eine Menge von Operationen, die auf
diesem Objekt ausgeführt werden dürfen. Meist entspricht eine Schutzdomäne
einem Benutzer, d.h. sie gibt an, was dieser Benutzer tun darf. Negative Rechte,
d.h. das was er nicht tun darf, werden nicht explizit angegeben."
Domäne 1 Domäne 2
Datei1[RWX]
Datei1[R]
Printer1[W]
Datei4[R]
Datei2[RW] Datei3[RW]
Floppy1[R]
254
Schlichter, TU München 9.3. SCHUTZMECHANISMEN
Das Beispiel zeigt mehrere Objekte mit Ihren Rechten und ihre Zuordnung
zu den Domänen. Gleiche Objekte (im Beispiel Datei1) können mit
unterschiedlichen Rechten unterschiedlichen Domänen zugeordnet werden.
Objekt
read write
2 read write read write read
execute
255
Schlichter, TU München 9.3. SCHUTZMECHANISMEN
der Domäne 1 in der Spalte für Objekt Domäne 2 die Zugriffsart "enter"
eingetragen.
• Schutzmonitor
Jeder Zugriff (D, o, a) eines Subjektes S wird mit Hilfe eines Schutzmonitors
überprüft. Der Schutzmonitor prüft anhand seiner intern gespeicherten Schutz-
matrix, ob in der Zeile von D ein Zugriffsrecht a für das Objekt o existiert. Bei
positivem Ausgang wird der Zugriff zugelassen, andernfalls wird ein Schutz-
alarm ausgelöst und der Zugriff unterdrückt. Der Schutzmonitor läuft meist in
einem geschützten Teil des Betriebssystems ab (z.B. Betriebssystemkern).
Objekte
Schutz-
Prozess o1
domäne
(D,o1,a) Schutzmonitor
D P Schutz o2
matrix
o3
Subjekt Betriebssystem - Systemmodus
Benutzermodus
256
Schlichter, TU München 9.3. SCHUTZMECHANISMEN
Neben den allgemeinen Rechten wie read, write und execute können auch
objekt-spezifische Zugriffsarten in die Zugriffskontrollliste des Objektes einge-
tragen werden. Für einen Prozess (Subjekt) sind nur diejenigen Zugriffsarten
auf das Objekt erlaubt, die in der zugehörigen ACL eingetragen sind. Manche
Schutzsysteme unterstützen auch Wildcards für die Prozessspezifikation, d.h.
ein ACL-Element (*, R) bedeutet, dass beliebige Prozesse das Leserecht auf
das Objekt besitzen.
• Capability-Liste
Capability-Listen ("Zugriffsausweislisten") realisieren die zeilenweise Speiche-
rung der Schutzmatrix.
jeder Prozess besitzt eine Menge von Capabilities, die die erlaubten
Zugriffe auf Objekte repräsentieren.
Element einer Capability-Liste besteht aus Paar (Objekt, Zugriffsarten). Ein
Capability gibt dessen Besitzer gewisse Zugriffsrechte für das Objekt.
257
Schlichter, TU München 9.3. SCHUTZMECHANISMEN
D1: R
D1: RW D2: R
D2: RW System
D2: R D3: RX
D3: RWX Modus
Capability-
Liste
258
Schlichter, TU München 9.3. SCHUTZMECHANISMEN
9.3.4 Authentifizierung
Authentifizierung eines Nutzers erfolgt meist über Login-Name und dem
zugehörigen Passwort. Ein häufig benutzter Ansatz besteht darin, dass das
ursprüngliche Passwort mit einem Streuwert ("salt value") kombiniert wird, und
daraus ein Hash Code generiert wird.
Generierung eines Hash Code aus dem Passwort und einem Streuwert fester
Länge. Der Streuwert ist eine Zufallszahl oder der Zeitpunkt, an dem das
Passwort erzeugt wurde. Aus Passwort und Streuwert wird ein Hash Code
fester Länge generiert. Die Hash Code Generierung wird gezielt verlangsamt,
um Attacken durch automatisch gesteuerte Versuche entgegenzutreten. Unix
Systeme nutzen oft eine MD5 basierte Hash Funktion mit einem Streuwert
von bis zu 48 Bits; Ergebnis ist ein 128-bit Hashwert.
Ein sehr sicheres Verfahren wurde für OpenBSD entswickelt. Die Hash Funktion
basiert auf dem Blowfish symmetrischen Verschlüsselungs Verfahren. Passwörter
können eine Länge bis zu 55 Zeichen haben, der Streuwert umfasst 128 Bit; es
entsteht ein Hash Code von 192 Bit.
Eintragen Passwort
User ID Streuwert Hash Code
Passwort
Langsame Hash
Funktion
Streuwert
Passwort Datei
Überprüfen Passwort
Passwort
User ID Streuwert Hash Code
Streuwert
User ID
Langsame Hash
Funktion
Vergleich
• Duplikate von Passwörter sollen in der Passwort Datei nicht erkennbar sein.
Auch wenn zwei Benutzer das gleiche Passwort wählen, entsteht aufgrund des
unterschiedlichen Streuwerts ein unterschiedlicher Hash Code.
259
Schlichter, TU München 9.4. MOBILER CODE
• Erhöht den Aufwand für offline Attacken auf die Passwort Datei. Hier wird der
Fall berücksichtigt, dass ein Angreifer eine Kopie der Passwort Datei erhält.
Durch einen Streuwert mit b-bits erhöht sich der Aufwand um den Faktor
2b. Neben dem Ausprobieren möglicher Passwörter muss der Angreifer auch
jeweils die möglichen Streuwerte durchspielen.
• nicht erkennbar, ob eine Person dasselbe Passwort auf 2 oder mehreren
Systemen nutzt.
9.4.1 Sandboxing
Ausführung des Applets wird auf einen bestimmten virtuellen Adressbereich
beschränkt.
Für eine Sandbox sind die high-order Bits aller Adressen gleich, d.h.
angenommen für einen 32 Bit Adressraum werden 256 Sandboxes auf 16
MByte Grenzen eingerichtet
⇒ für alle Adressen innerhalb einer Sandbox sind die oberen 8 Bits
identisch.
260
Schlichter, TU München 9.4. MOBILER CODE
9.4.2 Interpretation
Applet wird als Byte-Code geladen. Jeder Befehl wird vor seiner Ausführung von
der Java Virtual Machine (JVM) analysiert.
Falls die beiden Hashzahlen nicht übereinstimmen, wird die Ausführung des
Applets abgelehnt.
261
Kapitel 10
10.1 Einführung
Die Ziele von Betriebssystemen können sich zwischen verschiedenen Systemen
unterscheiden, für Server-Systeme, für Laptops, für Smartphones oder für
eingebettete Systeme.
10.1.1 Hauptaspekte
Man kann die folgenden 4 Hauptaspekte unterscheiden
262
Schlichter, TU München 10.1. EINFÜHRUNG
10.1.2 Probleme
Hardware hat sich gemäß des Moore‘schen Gesetzes kontinuierlich verbessert;
Betriebssysteme haben zwar mehr Funktionalität, jedoch bzgl. Verfügbarkeit sind
sie teilweise schlechter als die alten Systeme. Unix wurde in den 70er Jahren,
Windows in den 80er Jahren entwickelt.
• Betriebssysteme existieren eine lange Zeit. Unix wurde bereits in den 70er
Jahren, Windows in den 80er Jahren entwickelt. Entwickler müssen deshalb
263
Schlichter, TU München 10.2. SCHNITTSTELLENENTWURF
• Entwickler wissen oft nicht vorab, wie ihre Systeme genutzt werden. Unix
wurde zunächst für Minicomputer entwickelt; später wurde es auch als Server-
BS und als Desktop-BS genutzt.
10.2 Schnittstellenentwurf
Ein BS bietet eine Reihe von Diensten, die von Benutzerprozessen in Anspruch
genommen werden können.
Bereitstellen der Dienste über Schnittstellen.
264
Schlichter, TU München 10.2. SCHNITTSTELLENENTWURF
Nutzergruppen von BS
• Endbenutzer
Nutzung von Anwendungen ⇒ grafische Oberfläche des BS
• Programmierer
Nutzung der Systemaufrufschnittstelle des BS
• Systemadmin
Aufruf von Systemdiensten
Algorithmischer Ansatz
basiert auf der Idee, dass ein Programm eine bestimmte Funktion erfüllen soll, die
es im Voraus oder durch Parameter kennt.
Beispiel
main () {
int ...;
init();
do_something();
read(...); /* Systemaufruf */
do_something_else();
write(...); /* Systemaufruf */
continue();
exit(0);
}
265
Schlichter, TU München 10.2. SCHNITTSTELLENENTWURF
Ereignis-basierter Ansatz
nach einer Initialisierung warten Programme dieses Ansatzes auf Ereignisse des
Betriebssystems
Beispiel
main () {
mess_t msg;
init();
while (get_message(&msg)) {
case 1: ...;
case 2: ...;
case 3: ...;
......
}
}
Datenparadigma
Beispiel Unix
266
Schlichter, TU München 10.2. SCHNITTSTELLENENTWURF
• "Alles" ist ein Objekt. Das Datenparadigma "Alles" ist ein Objekt ist
allgemeiner als jenes von Unix. Wenn ein Prozess ein gültiges Handle für
eine Datei, einen Prozess, ein Semaphor, eine Mailbox erhalten hat, kann er
Operationen darauf ausführen.
Systemaufrufschnittstelle
267
Schlichter, TU München 10.3. WEITERE IMPLEMENTIERUNGSASPEKTE
10.3.1 Architektur
Ein etablierter und erprobter Architekturansatz sind geschichtete Systeme. Eng
verbunden mit dem Thread Management ist das Prozess Management und die
Interprozesskommunikation.
Systemaufrufbehandlung
Ein anderer Ansatz sind Client-Server Systeme mit einem Mikrokern und
ausgelagerten Serverprozessen. Dies erlaubt einen modularen, flexiblen Entwurf.
268
Schlichter, TU München 10.3. WEITERE IMPLEMENTIERUNGSASPEKTE
10.3.3 Namensräume
Die meisten langlebigen Datenstrukturen eines BS haben einen Namen oder einen
Bezeichner zugeordnet, z.B. Login-Namen, Dateinamen, Gerätenamen, Prozess-
ID etc. Namen werden auf 2 Ebenen vergeben
extern: Namen, welche Menschen verwenden (z.B. Dateiname)
intern: Namen, welche das System verwendet (z.B. inode Nummer)
In einem guten Entwurf wird darüber nachgedacht,
wie viele Namensräume benötigt werden,
Welche Syntax sie haben,
Ob absolute und relative Namen existieren.
Directories bilden externe Namen auf interne Namen ab.
Externer Name: /usr/ast/books/mos2/Chap-12
Interner Name: 2
269
Schlichter, TU München 10.3. WEITERE IMPLEMENTIERUNGSASPEKTE
• Beispiel Prozesstabelle:
Statisch: feste Prozesstabelle mit 256 Einträgen.
Dynamisch: Prozesstabelle als verkettete Liste.
Schnelle Suche in statischer Prozesstabelle. Falls ein 257. Prozess erzeugt
wird, ist der Aufruf nicht erfolgreich, da zu einem Zeitpunkt nur 256 Prozesse
existieren können.
270
Schlichter, TU München 10.3. WEITERE IMPLEMENTIERUNGSASPEKTE
• Hardware-Architekturen unterstützen
unterschiedliche WortlängenCPU-abhängige bedingte Übersetzung. Generiert
BS-Code abhängig von der unterstützten Wortlänge.
#include "config.h"
{
#if (WORD_LENGTH == 32) typedef int Register; #endif
#if (WORD_LENGTH == 64) typedef long Register; #endif
Register R0, R1, ...;
In der Datei config.h werden die entsprechenden Variablen CPU und
Word_LENGTH abhängig von der jeweiligen Rechnerarchitektur geeignet
besetzt. Bei der Übersetzung des BS-Codes muss nur die geeignete config.h
Datei verwendet werden.
271
Schlichter, TU München 10.4. TRENDS BEIM ENTWURF VON BETRIEBSSYSTEMEN
272
Schlichter, TU München 10.4. TRENDS BEIM ENTWURF VON BETRIEBSSYSTEMEN
– Eingebettete Systeme sind eng gekoppelt mit dem Produkt, wobei die
Anforderungen sehr variieren können
Größe des Produkts, in das es eingebettet ist. Dies hat oft Konsequenzen
bzgl der Kosten des Systems oder erfordert oft unterschiedliche
Optimierungsansätze.
Lebensdauer. Manche Produkte haben eine sehr lange Lebensdauer, so
dass bzgl Aktualisierung bzgl. des BS nachgedacht werden muss. Andere
Produkte haben eine so kurze Lebensdauer, so dass ein Update zu
aufwändig ist.
Nutzungsumgebung. Welchen Umwelteinflüssen ist das eingebettete
System ausgesetzt, z.B. Strahlung, Vibration, Hitze, Luftfeuchtigkeit.
Realzeitverhalten.
– Es wurden eine Vielzahl von speziellen Betriebssystemen für eingebettete
Systeme realisiert
∗ für mobile Endgeräte: Symbian OS, Windows CE oder Android (URL:
[Link] von Google.
Android Systemarchitektur basiert auf Linux Kernel (Treiber,
Speicher-/Prozessmanagement); darauf existieren Bibliotheken (z.B.
für Graphik), eine Laufzeitumgebung und ein Anwendungsframework.
Das ganze Anwendungsframework ist geschrieben in Java. Alle An-
wendungen benutzen dieses Framework, egal ob sie von Google inte-
griert sind, oder von einem externen Entwickler geschrieben wurden.
Komponenten des Frameworks sind der Window Manager, Activity
Manager, der den Lebenszyklus der Anwendung kontrolliert.
∗ TinyOS
für drahtlose Sensornetze: TinyOS (URL: [Link] ent-
wickelt von der UC Berkeley
273
Schlichter, TU München 10.4. TRENDS BEIM ENTWURF VON BETRIEBSSYSTEMEN
zentraler Teil des BS ist sehr klein, ca. 400 Bytes Code und
Datenspeicher
Internet
Sensor Sensor
Relay Relay
Sensor
Relay
Sensor
Relay Sensor
274
Schlichter, TU München 10.4. TRENDS BEIM ENTWURF VON BETRIEBSSYSTEMEN
275
Kapitel 11
Zusammenfassung
Diese Vorlesung beschäftigte sich mit den technischen Aspekten von Rechensy-
stemen. Es gab eine Einführung in Betriebssysteme und systemnahe Programmie-
rung. Insbesondere wurden folgende Aspekte behandelt:
• Sicherheit in Rechensystemen.
Der Entwurf und die Implementierung von Betriebssystemen ist komplex und
aufwändig. Wichtige Aspekte sind
definierte Abstraktionen, z.B. Prozesse, Threads, Adressraum
Definition von Schnittstellen zur Bereitstellung von Operationen, z.B.
Operation zur Synchronisation, persistente Speicherung von Information
Schnittstelle sollte einfach, vollständig und effizient sein.
Sicherstellen der Abgrenzung, z.B. Isolieren von Fehlern. Falls ein Benutzer-
prozess abstürzt, sollte es möglich den Rest des Systems fortzusetzen.
276
Schlichter, TU München
277