Rechner- und
Betriebssysteme INF 5T Wintersemester 2003/2004

Inhaltsverzeichnis

1 Einleitung	3

1.1 Begriffsbestimmung	3

1.1.1 Informatik und Systeme	3

1.1.2 Rechnersysteme	7

1.1.3 Rechnersystemstrukturen	7

1.1.3.1 Strukturierung mittels Parallelitätsebenen	7

1.1.3.1.1 Bitebenenparallelität	7

1.1.3.1.2 Befehlsebenenparallelität	7

1.1.3.1.3 Ebene der Anweisungsfolge (Parallelitätserkennung)	8

1.1.3.1.4 Ebene der kooperierenden Prozesse (coarse-grain parallelism)	8

1.1.3.2 Strukturierung mittels Operationsprinzip	8

1.1.3.2.1 SISD (eng. Single Instruction Single Data)	8

1.1.3.2.2 MISD (eng. Multiple Instruction Single Data)	9

1.1.3.2.3 SIMD (eng. Single Instruction Multiple Data)	9

1.1.3.2.4 MIMD (eng. Multiple Instruction Multiple Data)	10

1.1.3.3 Speichergekoppelte Multiprozessorsysteme	10

1.1.3.3.1 UMA	12

1.1.3.3.2 NUMA	15

1.1.3.4 Nachrichtengekoppelte Multiprozessorsysteme	15

1.1.3.4.1 NORMA	15

1.1.3.4.2 Programmierung von UMA/NUMA	16

1.2 Betriebssysteme	21

1.2.1 Grundlegende Konzepte der Betriebssysteme	21

1.2.1.1 Prozesse	21

1.2.1.2 Systemdienste	22

1.2.2 Komponenten eines Betriebssystems	25

1.2.3 Strukturen von Betriebssystemen	27

1.2.3.1 Monolithische Struktur	27

1.2.3.2 geschichtetes System	27

1.2.3.3 Mikrokernbasierte Systeme	27

1.2.3.4 Unterbrechungen	28

2 Prozessornahe Systemsoftware	31

2.1 Unterbrechungen und ihre Behandlung	31

2.2 Prozesse und ihre Verwaltung	34

2.2.1 Schwergewichtige Prozesse (Task)	34

2.2.2 Konzepte der Prozessverwaltung	37

2.2.3 (2.2.3) Leichtgewichtige Prozesse (Threads)	39

3 Prozesse, ihre Verwaltung und Prozesskooperation	42

3.1 Prozess-Synchronisation	42

3.1.1 Kritischer Abschnitt	43

3.1.1.1 Mechanismen	44

3.1.1.1.1 Hardware-Lösung	44

3.1.1.1.2 Algorithmische Lösung	45

3.1.1.1.3 Betriebssystem-Lösung	45

4 Speicher und ihre Verwaltung	48

Einleitung

Begriffsbestimmung

Informatik und Systeme

System1: verteiltes, fehlertolerantes System
System2: Laufzeitsystem (zur Ausführung von Programmen)

Interesse ausgerichtet auf maschinelle Verarbeitung von Information

These: Algorithmus kein ausreichendes Konzept für die Entwicklung heutiger Informatiksysteme
Beleg: komponentenbasierte SW-Entwicklung; Vernetzung, Web-Services (Dienstanbieter, z.B. Kreditkartenbelastung)

Was ist ein System?

Anordnung von Komponenten, die

ein einheitliches, geordnetes Ganzes ergibt

nach außen durch eine Systemgrenze abgegrenzt sind

aufeinander wirken gemäß Beziehungen

Beziehungen: Beschreibung/Charakterisierung mittels Ein-/Ausgabegrößen

Funktionsbeschreibung: Werte der Ein-/Ausgabegrößen und ihre zeitliche Veränderung

dynamisches System: Ausgabe des Systems hängt von der aktuellen wie von der vergangenen Eingabe ab.

Kausales System: Ausgabe hängt nur von vergangenen Eingaben ab

Aufgabe: nicht-kausale Systeme, z.B.: idealer Tiefpass (i.d. Elektrotechnik), Quantenrechner?

Was ist ein Rechensystem?

RS = dynamisches, kausales, technisches System
RS-Komponenten: Hard- und Software-Komponenten
Kern eines RS (Hardware): Rechenanlage

Betrachtungsformen:

Funktionsschnittstelle

Verteilung im Raum

Zustände

Schnittstellen bzw. dienstorientierte Sicht

Erwartung:

korrekte Resultate eines genutzten Dienstes

Benutzerfreundlichkeit/Dienstverfügbarkeit

Beispiel:

Geg.: n funktional gleichartige, sonst verschiedene RS

zusätzliche Erwartung: Leistung

Maße zur Leistungsbewertung:

Effektivitätsmaße: extern beobachtbare Wirksamkeit eines RS, z.B. Antwortzeit, Durchsatz (“Aufträge pro Zeiteinheit”)

Beispiel:

AK 1: 5 sec Bearbeitungszeit
AK 2: 2 sec -//-
AK 3: 8 sec -//-

RS umfasse:
6 Aufträge AK 1
9 Aufträge AK 2
5 Aufträge AK 3

⇒ Durchsatz des RS: 0.227273 Aufträge pro Sekunde

Effizienzmaße: intern beobachtbare produktive Ausnutzung, z.B. Auslastung in %.

Wahl der Schnittstelle:

Granularität der Dienste;
grob: “starte Auftrag x”
fein: “transferiere Datum von A nach B; dann verknüpfe Daten A und B multiplikativ”

Lage: HW-nah / HW-fern

Systematische Anwendung:

Hierarchie von Schichten -> Verallgemeinerung: virtuelle Maschine. Der Vorteil: Verbergen von Details

Gewünscht:

read (buffer)

read (sector, buffer)

d.h. Lese Sektor sector im Speicherbereich buffer

Hierzu:

Übertragung des Kommandos und der Parameter mittels MOVE-Befehle

Warten auf Ausführungsende

Abruf des Status

Rückmeldung an Aufrufer

Systemsoftware = Menge von SW-Komponenten (i.d.R. strukturiert in Form von Schichten/VMs)

Vorteile:

Entwicklungsaufwand wird verringert (keine Mehrfachimplementierung)

Benutzerkomfort durch Verbergen der Details

höhere Effizienz

Vermeidung fehlerhafter HW-Benutzung

Aufgaben der Systemsoftware:

effektive und komfortable Nutzung eines Rechensystems; „Veredelung“ der Rechenanlage

effiziente Nutzung -> Problem der Auftragsreihenfolge

1950: Ein-Benutzer-Programmierer
-> Single-User/Single-Programming-Betrieb

2000: mehrere Programme
-> Multi-User/Multi-Programm-Betrieb

Charakterisierung der Entwicklung:

Beispiel: steigender Hauptspeicher-Bedarf

virtueller Speicher

MMU (memory management unit) / TLB (translation look-ahead buffer)

Beispiel:

geringe Auslastung

Ausweg: Mehrprogrammbetrieb

Meilensteine der Entwicklung:

Mehrprogrammbetrieb

mehrere Programme gemeinsam, in verschiedenen Zeitabschnitten verzahnt ausführen (Zeitscheiben)

der Prozessor bedient jedes Programm abwechselnd; sind Programme IDLE, dann kümmert sich der Prozessor vornehmlich um die anderen Programme.

Steigerung der Auslastung

Erhöhung des Datendurchsatzes

Beispiel: Rechensystem aus CPU, I/O-Geräte.

Aufträge:
A1	Beginn Zeitpunkt 1
2,5 ZE	E
2,0 ZE	CPU
0,5 ZE	A
A2	Beginn Zeitpunkt 4
1,0 ZE	E
2,0 ZE	CPU
1,0 ZE	A
A3	Beginn Zeitpunkt 6
0,5 ZE	E
3,0 ZE	CPU
0,5 ZE	A

Datendurchsatz im Einprogrammbetrieb:

Datendurchsatz im Mehrprogrammbetrieb:

Koordinierung der Aktionen erforderlich

Verallgemeinerung: Ressourcen sind:

CPU

Speicherbereiche

Geräte

Dateien

SW-Objekte

Dann: Aufgabe der Systemsoftware ist die Organisation der gemeinsamen Ressourcennutzung

Rechnersysteme

Rechenanlagen stellen die Hardware-Grundlage für Rechensysteme. Sie beinhalten die klassischen Komponenten wie CPU, Arbeitsspeicher, E/A-Geräte usw. Sie ist räumlich (halbwegs) begrenzt.

Ein Rechnersystem unterscheidet sich zur Rechenanlage dadurch, dass die Komponenten räumlich weiter entfernt liegen können; es ist nicht unbedingt ein einziger PC.

Rechnersystemstrukturen

Strukturierung mittels Parallelitätsebenen

Als Kriterium für Parallelitätsebenen gilt die Art und der Umfang der Parallelisierung mittels Funktionswerke oder Verarbeitungseinheiten. Als Beispiele wären zu nennen:

spezialisierte Funktionseinheiten wie Gleitpunktwerke, Pipelinewerke

Prozessoren mit gleichartigen Werkten wie Feldrechner

ganze Prozessoren

komplette Rechenanlagen

Bitebenenparallelität

z.B. 32/64-Bit Prozessoren

Befehlsebenenparallelität

	in-order	out-order
issue	gem. seq. Notierung	gem. Verfügbarkeit von Funktionswerken
execution/completition	gem. seq. Notierung	Fertigstellung von Komplexität der Instruktionsausführung
	⇒ unproblematisch	⇒ problematisch

Superskalartechnik

mehrfach vorhandene, unabhängige Funktionseinheiten werden gleichzeitig mit Ausführung von Befehlen beauftragt; in-order-issue, out-of-order-exec

Pipeline-Technik

Sie ist eine Technik zur Zerlegung der Befehlsausführung in verschiedene Phasen. Grafik und Funktionsweise von Pipelines siehe Vorlesung „Rechnerarchitektur“.

Beispiel:

Pentium I-III:	Superskalar
Pentium IV:	tiefe Pipeline

Ebene der Anweisungsfolge (Parallelitätserkennung)

Darunter versteht man die intelligente Übersetzung von Programmen, in denen Teile parallelisiert werden können. Es ist die Ebene der Hochsprachenanweisungen.

Parallele Verarbeitung von Anwendungssequenzen, z.B. in Schleifen:

for( int i = 1; i <= 100; i++ ) x[i] = y[i] + a[i];

=> parallelisierbar

for( int i = 1; i <= 100; i++ ) {
a[i] = a[i] + b[i];
b[i+1] = c[i] * d[i];
}

=> Parallelisierung „nicht offensichtlich“, da Abhängigkeiten zwischen Iterationen. Lösung:

a[1] = a[1] + b[1];

for( int i = 1; i <= 99; i++ ) {

b[i+1] = c[i] + d[i];

a[i+1] = a[i+1] + b[i+1];

}

b[101 = c[100] + d[100]

Folgerung: unter Umständen existiert doch ein hoher Parallelisierungsgrad; er ist aber oft nur schwer aufzudecken. Um diese Parallelisierung nutzen zu können, benötigt man auch „Multi-Threading“-Architekturen (Intel: Hyperthreading) oder gar Multiprozessorsysteme mit gemeinsamen Speicher.

Ein Thread (Kontrollflussfaden) ist ein Kontrollfluss im Programmfluss der auszuführenden Anweisungen in einer Menge von Anweisungen. Ein ursprünglicher Programm-Thread kann sich in mehrere Threads aufteilen.

Ebene der kooperierenden Prozesse (coarse-grain parallelism)

Parallele Ausführung „weitgehend“ unabhängiger Programme bzw. Programmteile oberhalb der Ebene der Prozeduren. Das führt zum Begriff des Prozesses und zur Kooperation zwischen Prozessen. Ausführende, ausnutzende HW – das sind Mehrprozessorsysteme mit verteiltem Speicher.

Strukturierung mittels Operationsprinzip

Klassifikation von Flynn (1966)

	Daten einzeln mehrfach
Instruktionen	einzeln SISD SIMD mehrfach MISD MIMD

SISD (eng. Single Instruction Single Data)

Von-Neumann-Organisation mit

CPU

Rechenwerk: arithmetisch/logische Operationen

Leitwerk: Steuerung der Komponenten zur Implementierung des Befehlsabarbeitungszyklus

Registersatz: Speicherung der Zwischenergebnisse, Adresse (z.B. für Realisierung von Adressirungsmodi), Instruktionen, Stapelzeiger, Programmzeiger, Statusinformationen („Nullanzeige“ = Zero-Flag, Overflow-Flags, ...)

Aktionsfolge „Befehlsabarbeitung“

Befehl lesen

Befehl Decodieren/inspizieren

Bereitstellung der Operanden

Befehl ausführen

Ergebnisse speichern

Prüfung auf Unterbrechungen

Varianten der von-Neumann-Organisation:

Princeton-Architektur/Organisation

Harvard-Architektur

Kriterium: Ablageart von Instruktionen und Daten. Die unterschiedlichen Parteien:

Princeton:

Instruktionen und Daten in einem Speicher

Harvard:

Instruktionen und Daten in verschiedenen Speichern

MISD (eng. Multiple Instruction Single Data)

mehrere Instruktionen werden auf einem Satz von Daten ausgeführt => z.Z. kein geläufiges Rechnersystem

SIMD (eng. Single Instruction Multiple Data)

Ausführung einer Instruktion auf verschiedenen Sätzen von Daten

Beispiel: Matrix-Addition

Verarbeitungselemente addieren Matrixelemente:

Feldrechner

Feldrechner sind ein Feld von Ves (Verarbeitungselementen, also Prozessoren)

Vektorrechner

Anwendung des Pipeliningkonzepts auf Daten

MIMD (eng. Multiple Instruction Multiple Data)

parallele Ausführung verschiedener Instruktionen auf verschiedenen Datensätzen

speichergekoppelte Mehrprozessorsysteme

nachrichtengekoppelte Mehrprozessorsysteme

Speichergekoppelte Multiprozessorsysteme

Struktur:

Gemeinsamer Adressraum: jeder Prozessor kann jedes Wort im Speicher adressieren
=> einfaches Programmiermodell

Thread 1 auf P1	gem. Adressraum	Thread 2 auf P2
|	a	
|	b	x = a*b
Z = x/5	x	a = x * b

Kommunikation basiert auf gemeinsamen Variablen. Die Prozessoren müssen Absprache über Datenzugriff halten (Synchronisation). Dies geschieht ebenfalls über gemeinsame Variablen.

Beispiel: Erzeuger/Verbraucher

Erzeuger:	fertig := false
| Anweisungen der Erzeugung
fertig := true

Verbraucher:	while( nicht fertig); // ! Busy waiting!
| Anweisungen für Verbrauch

CPU1 CPU2 MEM I/O Merkmal: Threads agieren in gemeinsamem Adressraum
SMP-System: symmetrical multiprocessing

Unterscheidungen:

UMA - uniform memory access
Zugriffszeit auf ein Datum unabhängig vom Speicherort
Verbindungsstrukturen

Bus
Vorteil: einfach, gängig, performant
Nachteil: skaliert schlecht bis 8/16/20 Prozessoren
Abhilfe: schnelle, prozessorlokale Zwischenspeicher (Cache)
Thread 1 Cache 1 Mem Cache2 Thread 2
LOAD adr_x ->
read miss! <- LOAD adr_x
Cache-Fehl-OP. ->read read miss!
adr_x <- <-read
LOAD adr_x ->
<-read
Wenn Thread2 ein Datum verändert, liegt dies zuerst in seinem Cache. Dieses Datum kann aber unterschiedlich von dem im Cache1 und von dem im Hauptspeicher sein!! -> Kohärenzproblem!
Cache-Fill-Operation
Kennzeichen:

I: Daten einer Zelle ungültig (invalid)

V: Daten gültig (valid)

D Daten wurden modifiziert (dirty)

Füllen einer ganzen Zeile:
Methode »Wrap-around« (s. rechts)
Es wird nicht nur Adr. 1, sondern auch die drum herum
geholt
Aktualisierungsstrategien:

write-through
sofortige Aktualisierung des Wortes im Hauptspeicher

write-back / copy-back
Aktualisierung des Hauptspeichers erfolgt erst, wenn die Zeile im Cache ersetzt werden soll (dann wird die zuerst nur im Cache vorliegende, geänderte, Information in den Hauptspeicher geschrieben)

Problem: Datenkonsistenz und ihr Erhalt

Datenkonsistenz: Kopien unterscheiden sich nicht von Hauptspeicher-Daten
Auswege:

Cache-Kohärenz-Protokoll

gemeinsam genutzte Daten ≙ »nicht cache-bar«

Grundlage eines Kohärenzprotokolls:

Bus-Snooping: Abhören des Busses
Überwachung der Adressen

Lesender Zugriff (durch fremden Cache) -> do nothing

Schreibender Zugriff von anderem Cache:

Daten zu Adresse nicht im eigenen Cache -> do nothing

Datum im eigenen Cache: Snoop-Hit on a Write
eigener Cache: schreibt Datum zurück bzw. markieren des Datums als geändert.
MESI-Kohärenzprotokoll
Zustädne für Cache-Zeilen ( Daten !!):
M: Exclusive modified (liegen nur in einem Cache vor; verändert)
E: Exclusive unmodified (nur in einem Cache; unverändert)
S: Shared unmodified (in mehreren Caches; unverändert)
I: Invalid (Cache-Zeileninhalt ungültig)

Einschub: Strukturierung (?!?)

Rechnersysteme

SISD

MIMD

UMA

Bus / Bus+Cache

...

NUMA

NORMA

UMA

BUS-Snooping

Situation:

Thread 1	Thread 2
lx = 0; for( int i = 0; i < n; i++ ) { lx += a[i]; } gr = lx/n;	ly = 1; for( int j = 1; j < m; j++ ) { ly *= b[j]; } gr = ly/m;

Das Problem ist der konkurrierende schreibende Zugriff auf die globale Variable gr. Die Lösung dieses Problems übernimmt nicht irgend eine Hardware-Struktur oder Cache-Kohärenz-Protokolle sondern muss von uns als Programmierer gelöst werden: ein Synchronisations-Mechanismus auf Thread-Ebene ist erforderlich.

MESI-Protokoll

M: exclusive modified; Datum in genau einem Cache liegend und verändert
E: exclusive unmodified = M ohne Modifikation
S: shared; Datum, unmodifiziert, in mehreren Caches
I: invalid; Cache-Zeileninhalt ist ungültig

Übergänge lokale Zugriffe

Übergänge für externe Zugriffe

Beispiel:

	Cache 1	Cache 2
Start:	I	II
	shared = 0 1. Read Miss	Snoop Hit on Read
	Laden aus HS	
	I -> E	
	Snoop Hit on a Read	2. Red Miss
	E -> S	Laden aus HS
		I -> S
	3. Write Hit	
	shared = 1 Modifizieren im Cache	Snoop Hit on a Write
	S -> M	S -> I
	Snoop Hit on a Read	4. Read Miss
		Laden aus HS
		Laden abbrechen
	invalidate = 1 retry = 1 Rückschreiben in HS	Laden aus HS
	retry = 0 shared = 1 Snoop Hit on a Read	
	M -> S	

Verbindungsstrukturen

Bus

Kreuzschienenverteiler (cross bar net)
Problem: Aufwand quadratischer Anstieg

Netz aus 2x2-Router

NUMA

NUMA = non-uniform memory access; Zugriffszeit abhängig von der Speicherart

Variante: Kopplung von SMP-Systemen

+ geringer HW-Aufwand

- Kohärenzproblem  aufwendiges, verzeichnisbasiertes Protokoll

Verknüpfungsbausteine:

hohe Übertragungsgeschwindigkeit; SCI (eng. scalable coherent interface)

Nachrichtengekoppelte Multiprozessorsysteme

NORMA

NORMA = no remote memory access. Kein gemeinsamer Adressraum. Kommunikation mittels Nachrichtenaustausch

Sender

send( <adress>, <message> )

I Übertragung der Nachricht

Empfänger

receive( <adress>, <buffer> )

Programmierung von UMA/NUMA

OpenMP (open specification for multi processing)

Wie geht das, was ist das?

API zur Spezifikation von Parallelität zwischen Threads

Bestandteile:

Übersetzerdirektiven (#ifndef ...)

Laufzeitbibliotheken

Umgebungsvariablen

Programmiermodell:

Parallelität, also thread-basiert und explizit

fork/join-Konstrukt:

Fork: Aufsplitten des Master-Threads in mehrere Threads

Join: zusammen laufen aller Threads zum Master-Thread

Beispiel:

int main( void )

{

int nthreads, tid,

#pragma omp parallel

private( nthreads, tid )

{

tid = omp.getThreadID();

}

}

Anzahl Threads:

mittels Funktion, z.B. omp.setNumThreads( int n );

Umgebungsvariable OMP_NUM_THREADS

Voreinstellung

Muster für Teams

Do/For

Fork in multiple threads

each threads processes a unique for-loop to manipulate „his“ data

Join

⇒ Ausnutzung der Datenparallelität

Muster für Section

Fork in multiple threads

each thread does a quite different job, i.e. one decodes MP3, the other one compiles the kernel

Join

=> Ausnutzung der Funktionsparallelität

Beispiel: Teams

int main( void )

int i, chunk;

float a[N], b[N], c[N];

#pragma omp parallel

shared( a, b, c, chunk )

private( i )

{

#pragma omp for

{

for( i = 0;i < N; i++ ) c[i] = a[i] + b[i];

}

}

}

Beispiel: Teams

int main( void )

int i, chunk;

float a[N], b[N], c[N];

#pragma omp parallel

shared( a, b, c, chunk )

private( i )

{

#pragma omp for

{

for( i = 0;i < N; i++ ) c[i] = a[i] + b[i];

}

#pragma omp <keyword> { ... }

}

}

Einschub Präprozessoranweisungen

Man unterscheidet drei Arten von Präprozessoranweisungen:

Texteinfügung

Textexpansion/-ersetzung

bedingte Übersetzung

Nun zu (1) Texteinfügung

#include <datei> // Var. 1: #include <iostream>

// Var. 2: #include „mydata.h“

(2) Textexpansion/-ersetzung

// Konstanten definieren

#define <bezeichner> <ersetzungstext>

// z.B.: #define SIZE 37

// Makros definieren

#define SQR(c) c*c

// Typen definieren

#define UINT unsigned int

(3) bedingte Übersetzung

#if defined <bezeichner>

Anweisungsblock 1

#else

Anweisungsblock 2

#endif

// z.B.:

#if defined GNU

GNU-spezifischer Code

#else

Borland-Müll

#endif

Übersetzerdirektive

#pragma

Anweisung an Compiler zur Ausführung spezieller Aktionen, z.B.:

#pragma char unsigned // Anweisung, alle Charakter aus Bereich

// [0,255] auszuwählen

oder:

#pragma omp parallel

Zurück zum Stoff: Ausprogrammieren von Parallelität – also wie sage ich, dass ich parallel programmieren möchte?

Explizites, vollständiges Ausprogrammieren -> ich muss mich selbst um alle Details kümmern

Hinweisend  z.B. mit OpenMP

Automatisch

Beispiel: OpenMP – Multiplikation einer Matrix mit einem Vektor

int i = 0;

int j = 0;

float matrix[ N ][ N ], vector[ N ], result[ N ];

#pragma omp parallel

shared( matrix, vector, result )

Erzeugung der Threads (fork) private( i )

{

#pragma omp for private( j )

for( i = 0; i < N; i++ ) {

for( j = 0; j < N; j++ ) {

result[ i ] = matrix[ i ][ j ] * vector[ j ]

}

}

}

MPI

Illustration 1 - Grundmodell MPI MPI (eng. Message Passing Interface) ist eine Spezifikation einer Bibliothek für nach­richten­gekoppelte Prozes­sor­systeme. Hinweis: wir reden hier von Multiprocessing, also von Prozessen, die keinen gemeinsamen Speicherraum besitzen und nur über Nachrichten miteinander kommunizieren können! MPI erlaubt ebenso wie OpenMP hinweisendes Programmieren, da die Nachrichtenkommunikation dem Programmierer transparent erscheint durch die darunter liegende Bibliothek.

Beispiel: MPI-Anwendung

int rank, size;

{

MPI_Init( &arc, &argv );

// Abfrage num. Identifikation im Kommunikator MPI_COMM_WORLD

MPI_Comm_Rank( MPI_COMM_WORLD, &rank );

MPI_Comm_Size( MPI_COMM_WORLD, &size );

// Abschließen der Aktionen

MPI_Finalize();

}

Eine Nachricht entspricht einem Feld von Elementen eines MPI-Datentyps (z.B. MPI_Char, MPI_Int)

Kommunkationsende := sicherer, konsistenter Zugriff auf Speicher für Nachrichten. Dabei gilt für

Sender: kann Nachrichtenvariablen wieder verändern

Empfänger: Nachrichtenvariable steht für Weiterverarbeitung zur Verfügung

Es existieren verschiedene Modi:

blockierend

nicht-blockierend

Beispiel: synchrone Kommunikation

MPI_SSend(

// Was

data, // Nachrichtenpuffer

500, // Anzahl Elemente

MPI_REAL,

// An wen?

6, // Prozessidentifikation

33, // Sequenznummer der Nachricht

MPI_COMM_WORLD ) // Kommunikator

MPI_Receive( ... )

Betriebssysteme

Aufgaben/Erwartungen der Systemsoftware

effektive/komfortable Nutzung der Ressourcen eines Rechnersystems

effiziente Nutzung der Ressourcen einer Rechnersystems

Dabei gilt: Programme greifen auf das Betriebssyste zu, welche eine Systemsoftware ist und Aufgaben der Organisation, Steuerung und Kontrolle übernimmt. Das Betriebssystem selbst greift auf Ressourcen zu wie Speicher, CPU, Geräte, Verbindungen.

Probleme treten auf, wenn mehrere Programme (konkurriered, parallel) auf Systemressourcen zugreifen wollen

Grundlegende Konzepte der Betriebssysteme

Programm Statische Merkmale: Code-Größe Stack-/Heap-Größen Dateireferenzen -> alle gleichzeitig offen? -> auf welchen Geräten?	Programm in Ausführung = dynamischer Vorgang problematischer Schluss

Beispiel: Ackermann-Funktion

int a( int n, int m )

{

if( n == 0 ) return m + 1;

else if( m == 0 ) return a( n-1, 1 );

else return a( n-1, a(n, m-1) );

}

Prozesse

Ziel: Erfassung „dynamischer Vorgänge“

Ein Prozess ist ein individueller, zeitlicher Ablauf eines Programms:

Zeitintervalle -> Berechnungen

Zeitpunkte -> Operationen

Merkmale einer Prozesses:

Adressraum:

Codesegment

Datensegment (Heap)

Stacksegment

Prozessidentifikation

Programmzählerinhalt und andere Register

weitere Ressourcen

Dateien/Geräte

Verbindungen

Kontrollfluss: symbolisiert Verlauf ausgeführter Operationen, d.h. den Prozessfortschritt

Programm		Prozess
Anweisungen Ausführung Kontrollstrukturen Prozeduren Statische Elemente Variablen Dateizeiger		Code Stack/Heap Zustand (insb. Programmzähler) geöffnete Dateien

Prozess = dynamischer Ablauf, der verwaltet wird.

Systemdienste

Angebot der Systemsoftware zur Nutzung der Ressourcen.

Beispiel: Öffnen einer Datei

FILE* fp_in = fopen( „Dateiname“, Modus“ );

-> Zeiger auf Datenstruktur, die Datei beschreibt

Situation: oben im Adressraum liegt der Code der Bibliothek (für den Dateizugriff). Wie kann verhindert werden, dass ein gewöhnlicher Programmierer mit einem Jump im Code der Systemdienste landet?
⇒ Problem: Schutz der Systemsoftware

Lösung: Betriebsmodi zur Überprüfung von Zugriffen auf Speicherbereiche

Betriebsmodus: Rechte bei Programmausführung

privilegierter Modus: alle Maschinenbefehle, alle Register, alle Speicherbereiche

nicht-privilegierter Modus: eingeschränkte Befehlssatz, eingeschränkte Zugriffsmöglichkeiten

Wechsel in privilegierten Modus: Absetzen eines SVC-Befehls (Supervisor-call)
-> Unterbrechung (Interrupt), also Softwareinterrupt

Wechsel in nicht-privilegierten Modus: Systemsoftware setzt RTI-Befehl (Return from Interrupt)

Ausführung Programm:

Anweisungen

Kontrollstrukturen

Prozeduren

Statische Elemente (Variablen, Dateizeiger ...)

Prozess:Programm in Ausführung

Code

Stack/Heap

Zustand (insbes. Programmzähler)

geöffnete Dateien

Prozess ≙ dynamischer Ablauf, der verwaltet wird

Entstehung eines Programms:Hochsprache  Maschinenprogramm (Assembler)

Beispiel: SVC-Befehl unter Win2k:

Anwendung:	fprintf()	 = Prozeduraufrufe
C-Bibliothek (Win32-API)	 call WriteFile()
Kernel32	 call NtWriteFile()
NTDLL	 SVC

Kernel	 ≠ CALL

Beispiel: SVC-Befehl unter UNIX:

Anwendung:	fprintf()
C-Bibliothek:	 SVC

Notwendig: „Abschottungsmaßnahmen“

Zugang zu Prozeduren nur via SVC-Befehl

Zugriff aus Systemadressen, HW-Prüfung der Adresse

Verfeinerung des Betriebsmodus

Privilegstufen:

hoch privilegiert	Stufe 0	Systemkernfunktionen	Systemanwendungen

niedrig privilegiert	Stufe n	Anwendungen

Wechsel der Privilegstufe mittels Referenzierung so genannter Gates

Prozessadressraum:

Kontrollfluss: Verlauf der ausgeführten Befehle

je Prozess: mindestens ein Kontrollfluss

Möglich: Aufteilung ⇒ Threads (unterstützt durch eigenen Stacks)

Komponenten eines Betriebssystems

Prozessorverwaltung:

Zuteilung des Betriebsmittels Prozessor an Prozesse auf unterster Ebene (sog. Dispatcher).

Unterbrechungsbehandlung

Ziel: hohe Reaktivität

E/A-System:

Verwaltung der Geräte

Realisierung abstrakter Geräte (z.B. durch Treiber)

Dateisystem:

Realisierung einer einheitlichen logischen Sicht auf Dateien und Dateiverzeichnissen

Speicherverwaltung:

Verwaltung von Prozessadressräumen

Unabhängigkeit von physikalischem Speicher

Verbergen einer Speicherhierarchie

Prozessverwaltung:

Organisation des Ablaufs paralleler Prozesse, z.B. strategische Überlegung. Zuordnung von Prozessen zu Prozessor (sog. Scheduler)

Generierung/Terminierung von Prozessen

Kooperation zwischen Prozessen, z.B. für

Kommunikation

Synchronisation

Beispiel: Erzeuger/Verbraucher

Strukturen von Betriebssystemen

Monolithische Struktur

Strukturmerkmal: Sammlung von Modulen und Prozeduren

jede Funktion kann jede andere Funktion aufrufen/nutzen.

Vorteile:

„einfach“ umsetzbar

„beliebig“ erweiterbar

effiziente Kommunikation zwischen Modulen

direkte Zugriffe auf Datenstrukturen

Nachteile:

änderungs-unfreundlich

kein Schutz zwischen Kernkomponenten

Weiterentwicklung: modularisierte, monolithische Systeme (siehe Linux)

geschichtetes System

Hierarchie von Schichten mit steigendem Abstraktionsgrad. Problem: Festlegung der Schichten.

Mikrokernbasierte Systeme

Kern = SW-Schicht, mit der HW-Details verborgen werden
Nutzung: durch Aufruf (aufrufbasiert)
Mikrokern = Kern mit minimaler Funktionalität
Systemprozesse: realisieren übrige Funktionalität

Nutzung bei Mikrokernen ist auftragsbasiert.

Vorteile:

geringere Komplexität des Mikrokerns

Flexibilität

Zuverlässigkeit durch Abschottung

Nachteile:

Leistungsverlust

Weiterentwicklung:

Verbesserung der Implementierung

Integration von Diensten aus den Modulen zurück in den Mikrokern

Unterbrechungen

CPU: Während ein Befehl ausgeführt wird, tritt ein Ereignis ein, welches eine Unterbrechung auslöst.

a) synchron zur Befehlsausführung

b) asynchron zur Befehlsausführung

Unterscheidung:

externe Unterbrechungen (b): Eingriffe der Peripherie; Interrupt request

E/A-Peripherie-Eingriffe
maskierbar, d.h. Annahme kann unterdrückt werden

Hardware-Diagnostik-Eingriffe
(z.B. Paritätsfehler beim Lesen aus dem Speicher)
nicht maskierbar

interne Unterbrechungen (a): Ausnahmen, Exceptions

prozessorentdeckte Unterbrechungen

Fehler, Alarme
z.B. Division durch 0, Seitenfehleralarm,
oft: Befehlsausführung nach Behandlung wiederholen

Traps
Auslösung der Unterbrechung nach Befehlsausführung
z.B. für Debug-Zwecke

Abbrüche
Anzeige von Hardware-/Software-Fehlern
Ausführung aktueller Anwendungssequenz nicht mehr möglich

programmiert mittels Befehl
Systemdienstaufruf, Test auf Feldgrenzüberschreitung, ...

Problem: Pipelining

Behandlung:

Eingriff
Befehle in Pipeline werden zu Ende ausgeführt
Befehl der Behandlung wird als nächste in Pipeline fließen

Ausnahme

Alarm
Befehl und die nachfolgenden Befehle erneut nach Behandlung in Pipeline fließen lassen

Trap
analog zum Alarm

Abbruch
Pipeline leeren

⇒ aufwändige, fallabhängige Unterbrechungsbehandlung

Unterbrechungsvektor

numerischer Identifikator
i.d.R. fest für Ausnahmen und nicht-maskierbare Eingriffe
programmierbar für maskierbare Eingriffe

Bereitstellung des Vektors durch

Hardware bei internen Unterbrechungen

Zusatzinformation bei externen Unterbrechungen

Anbindung der Peripherie

PIC:

Tabelle mit Unterbrechungsvektoren
Gerät => Indentifikation der Unterbrechung

Aktionen:

Abhören der Geräte

Falls ja:

Ermittlung der Indentifikation

Signalisierung via INTR

Warten auf INTA

Bereitstellung des Vektors in Register (CPU liest Register via Datenbus)

Probleme:

Vielfalt externer Geräte

CPU in einem Mehrprozessorsystem ist auch ein Erzeuger von Unterbrechungen

Lösung:

PIC ⇒ CPU-lokaler APIC
I/O-APIC

APIC = advanced PIC

Aufgaben:

lokaler APIC
Annahme und Weiterleitung von Eingriffen an Prozessorkern
Aussenden von Interprozessor-Unterbrechungen

I/O-APIC
Annahme und Verteilung der Eingriffe an die CPUs

statisch via Tabelle

dynamisch gemäß Prozesspriorität

Prozess Unterbrechungs- behandlung Unterbrechung:Zustands-sicherung Zustands- restaurierung

Zustandsinformationen:

Programmzähler

Registerinhalte

Prozessorstatuswort (Anzeigen: Zero-Flag, Carry-Flag)

Prozessornahe Systemsoftware

Mechanismen der Zuteilung des Prozessors an:

Prozesse

Periphere Prozesse (Geräte)

Unterbrechungen und ihre Behandlung

Ein permanent ausgeführter Maschinenbefehlszyklus besteht aus zwei Aktionen

Lesebefehl. Er bekommt die Adresse des auszuführenden Befehls aus dem Program-Counter (PC)

Befehlsausführung

Beispiel „was macht mein schnuckeliger Pentium“?

while( 1 ) {

LeseBefehl( PC );

BefehlAusführen();

}

Was ist bei

Fehler während der Befehlsausführung. Es ist immer ein Bezug zum Programm / zur Sequenz ausgeführter Befehle da. Mögliche Fehler:

Speicherzugriffsverletzung

Division durch 0

Maschinenbefehlsalarm

Peripherie will etwas sagen: „habe fertig“; ohne Bezug zu aktuell ausgeführten Befehlen
⇒ Ereignisse treten (unerwartet) ein und werden mittels elektrischer Signale dem Prozessor als Unterbrechung angezeigt.

Behandlung von SVC

SVC bedeutet programmierte Unterbrechung

SVC_par: Identifikation des angeforderten Systemdienstes

Kern einer UBH-Routine für einen SVC: Sprungtabelle

Aktionen innerhalb des UBH-Rahmens:

Sicherung des SVC_par auf Stack

Prüfung des SVC_par

Aufruf gemäß Sprungtabelle (indiziert mittels SVC_par)

Ablage des Rückgabewertes an definierte Stelle (oftmals eine Ersetzung des SVC_par auf dem Stack)

Problem:

Übergabe weiterer Parameter an Behandlungsroutine (z.B. Dateireferenz, Datenreferenz bei write)

Anwendung: Bereitstellung auf Anwender-Stack

Kern: Nutzung des Kern-Stacks

⇒ komplizierter Zugriff. Man hat also folgende Vereinbarungen getroffen:

Übergabe der Parameter eines Systemdienstes via Register (Ablage durch Bibliotheksfunktion)

Vor Aufruf der SVC-Behandlungsroutine: Kopieren der Register auf Kern-Stack

Behandlung eines Eingriffs

Aufgaben:

Identifikation des Gerätes und der Eingriffsursache

Behandlung

Aufteilung der Behandlung:

kritische Aktionen z.B. Rückmeldung an Gerät
⇒ sofortige Durchführung unter Unterbrechungssperre

unkritische Aktionen z.B. Tastaturumstellung (d.h. Aktualisierung von Ländercode-Tabellen)
⇒ sofortige Durchführung, aber unterbrechbar

verschiebbare Aktionen, z.B. Kopieren des Tastaturpuffers
⇒ Vormerken der Ausführung

Eingriffsbehandlung: siehe allgemeine Rahmen
für eingriffsspezifische Behandlung: Datenstruktur mit verschiedenen Informationsdeskriptoren

Datenstruktur:

Nutzung:

Zugriff auf Datenstruktur via Eingriffsnummer

Quittung am PIC via IC-Handler

Iteration über Liste der Aktionsdeskriptoren: Aufruf gerätespezifischer Behandlungsroutinen

⇒ der Vorteil liegt auf der Hand: man gewinnt Flexibilität. Das System ist erweiterbar hinsichtlich PIC und Geräte!

Rückkehr aus UBH

Stack-Operationen Push: Datum auf Stack legen Pop: Datum gemäß LIFO vom Stack nehmen SVC ≙ INTR 3 , SVC_par
⇒ Referenzierung der IDT (engl. Interrupt Descriptor/Dispatch Table) zwecks Ermittlung der Adresse UBH (5430)

Prozesse und ihre Verwaltung

Prozesse:

zentrales Konzept zur Erfassung sequentieller Aktivität

Verwaltungselement im Rahmen der Realisierung des Mehrprogrammbetriebs

Anforderungen:

keine Monopolisierung von Ressourcen

keine unerwünschten wechselseitigen Beeinflussungen

Schwergewichtige Prozesse (Task)

Zur Wiederholung: Prozess ≙ Programm in Ausführung

Beschreibende Elemente:

Adressraum (getrennt von den Adressräumen anderer Prozesse)

Programmcode

Strukturen zur Ausführungsunterstützung (Heap, Stack, Dateipuffer)

Ausführungselemente (Prozesskontext)

HW-Kontext (Register, Bedingungsanzeige, Programmzähler)

Ressourcen( Dateien, Signale, Verbindungen, ...)

Implementierung von Prozessen

Prozesskontrollblock/Prozessdeskriptor: Datenstruktur für Verwaltung und Zustandshaltung [PCB (engl. Process Control Block)].

Zusammenfassung prozessbeschreibender Attribute:

Identifizierung (nummerische ID als PID, Benutzerinformation, weitere Identifikationen (z.B. bzgl. Prozesshierarchie))

Prozesszustand: Aufnahme des HW-Kontextes

Prozesskontrollinformationen:

symbolischer Prozesszustand

scheduling-bezogene Informationen (Priorität)

Ressourcen:

Dateien und Verzeichnisse

Arbeitsspeicherbereiche

Signale und Nachrichten

Organisation von Prozessen

Tabelle (wahlfreier Zugriff mittels PID)

Listen (zur Bildung von Teilmengen)

Datenstruktur für PCBs :

Prozesserzeugung

Man unterscheidet folgende Arten der Prozesserzeugung:

Statisches Prozess-System: alle Prozesse werden zum Systemstart eingerichtet

Dynamisches Prozess-System: Erzeugung mittels Systemdienst; aufgerufen durch existierenden Prozess

unstrukturiert: kein Zusammenhang zwischen erzeugendem und erzeugtem Prozess_
Prozess A: Erzeuge_Prozess -> Ablauf von Prozess B
Prozess B weiß nichts über Prozess A, insbesondere

strukturiert: es wird eine Hierarchie aufgebaut
d.h. ein erzeugender Prozess entspricht der Wurzel (Vater) der erzeugten Prozesse (Kinder)

Charakteristisch für strukturierte Prozesse ist, dass Kind-Prozesse die Ressourcen des Vater-Prozesses erben. Durch diese Weiterreichung der Ressourcen gewinnt man Kontrollmöglichkeiten. So ein Kindprozess kann synchron oder asynchron ablaufen.

Auswahlformen für Kind-Programm

Erneuerung: auszuführendes Programm = Parameter der Erzeugung

Duplizierung: Kind führt gleiches Programm aus

Beispiel: Windows 2000

Windows praktiziert eine unstrukturierte Prozess-Erzeugung. Im Rahmen dieser Erzeugung wird eine Erneuerung durchgeführt und spezifiziert, welches Programm der Kind-Prozess ausführen soll

Beispiel: UNIX/Linux

Die restliche Computer-Welt praktiziert die elegantere strukturierte Prozess-Erzeugung. Es ist eine asynchrone Erzeugung mit Duplizierung

fork: Systemdienst für Prozesserzeugung

Beispiel-Quellcode:

int pid;

pid = fork();

if( pid == 0 ) ... // Kind-Aktionen

else ... // Vater-Aktionen

Systemdienste:

wait: Warten auf Terminierung irgendeines Kind-Prozesses
Aufrufergebnis: PID des terminierenden Kindes (alternativ: wait pid)

exit: Terminierung und Übergabe eines Statements.

Prozess-Zustände

Bisher:

Verfeinerung:

Anforderungen an das Betriebssystem zwecks Organisation des Prozesswechsels:

Sicherung / Restaurierung des Kontextes eines Prozesses

Verwaltungsstrukturen (Warteschlangen, ...)

organisatorischer Akteur: Dispatcher

strategischer Akteur: Scheduler

Suspendierungsformen:

erzwungen: Prozess wird am Fortschreiten gehindert
Ursachen: Unterbrechung

freiwillig: Anforderung eines Dienstes
(E/A-Dienste, Warten auf Ereignisse)

Verfeinerung:

Besonderheit in hierarchischen Prozess-Systemen:

Vater terminiert vor Kind: Kind ⇒ „Weise“. Es erfolgt eine Zuordnung zum Urvater

Kind terminiert vor Vater und Vater hat Rückgabewert noch nicht abgerufen: Wechsel des Kindes in Zustand „vor Terminierung“ ⇒ „Zombie-Prozess“

Konzepte der Prozessverwaltung

Organisation zeitparalleler Abläufe der verschiedenen Prozesse durch Scheduler/Dispatcher.

Aktivierung

nach freiwilliger Abgabe der Ressource „Prozessor“

nach jeder Unterbrechungsbehandlung

Scheduling:

Scheduling bedeutet Bestimmung des rechenwilligen Prozesses, der als nächstes in Zustand „rechnend“ wechselt

Ziele:

Auslastung maximieren

Antwortzeit minimieren

Fairness

Strategieraum:

ohne/mit Verdrängung (preemptive/non-preemptive)

ohne/mit Prioritäten

unabhängig/abhängig vom Rechenzeitbedarf

Strategien:

FCFS (First Come First Serve): Strategie ohne Verdrängung, ohne Prioritäten, unabhängig vom Rechenzeitbedarf.
Belegen der Ressource „Prozessor“ bis zur freiwilligen Abgabe ⇒ hohe Prozessorauslastung

LCFS (Last Come First Serve): Strategie ohne Verdrängung, ohne Prioritäten, unabhängig vom Rechenzeitbedarf

RR (Round Robin): Strategie mit Verdrängung, ohne Prioritäten, unabhängig vom Rechenzeitbedarf; Belegen bis zur freiwilligen Abgabe oder bis Ablauf einer Zeitspanne (sog. Zeitscheibe)

PRIO-NP/P: Strategie ohne/mit Verdrängung, mit Prioritäten, unabhängig vom Rechenzeitbedarf

SJF (Shortest Job First): Strategie ohne Verdrängung, ohne Prioritäten, abhängig vom Rechenzeitbedarf; Auswahl des Prozesses mit dem kleinsten Rechenzeitbedarf

SRTN (Shortest Remaining Time Next): Auswahl des Prozesses mit der kürzesten Zeit bis zur Abgabe des Prozessors

Scheduling-Strategie RR

ohne Priorität

unabhängig von Rechenzeit-Bedarf

Prozessor besitzt ≙ Dauer einer Zeitscheibe

Beispiel: Zeitscheibe mit 5 ZE

Schedule:

Varianten:

bei Eingriff: Neubewertung (ggf. Verdrängung)

Organisation der rechenwilligen Prozesse nicht nach FCFS

Zeitscheibenrest bleibt erhalten.

Multilevel-Feedback-Scheduling

dynamische Anpassung der Scheduling-Strategie

Unterteilung der Menge rechenwilliger Prozesse in Teilmengen

Beispiel: RR als Basis

Echtzeit-Scheduling

Einhaltung von Zeitforderungen:

spätest möglicher Zeitpunkt des Beginns der Ausführung

spätest möglicher Zeitpunkt des Endes der Ausführung

strikte/schwache Forderungen:

1. EDF

EDF (Earliest Deadline First): man wählt den Prozess aus, dessen Ende-Zeitpunkt am nähesten (direktesten) in der Zukunft liegt) man gibt dem Prozess die höchste Priorität, der am ehesten fertig werden muss (vgl. Prioritäten-basiertes Scheduling)

Beispiel: EDF

Reihenfolge der Prozessausführung: P1, P2, P3

Aber Vorsicht! Es kommt bei P3 drei zu einer Fristverletztung, weil er nach Zeitpunkt 9 fertig wird!

2. RMS

RMS (Rate Monotone Scheduling (RMS): Prozessverhalten gekennzeichnet durch periodische Aktivität ⇒ Aktivitätsfrequenz ≙ Anzahl der Aktivierungen pro ZE

Beispiel: Wiederholung alle 30 ms

⇒ Frequenz 33 mal/s

(2.2.3) Leichtgewichtige Prozesse (Threads)

Prozesskonzept ≙ Konzept zur Bildung von Einheiten

Einheit zur Bündelung von Ressourcen: Adressraum, Dateien und Verbindung werden abgebildet auf einen Prozess.

Einheitenbildung gemäß Aktivitätsträger ⇒ Threads

Unter einem Thread versteht man eine eigenständig ablaufende Instruktionsfolge im Adressraum des Prozesses.

Beispiel: Webserver

Es gibt nur einen HTTPD-Prozess. Trifft eine Anfrage auf den Webserver ein, wird ein neuer Thread gestartet und die Anfrage von dem Thread behandelt. Ist die Aufgabe Erfüllt, also die HTML-Seite dem Client zugestellt, wird der Thread wieder beendet.

Thread-Implementierung:

kein PCB!

separater Programmzähler

Zustand

Einsatzvorteile:

einfachere Programmierung

Datenaustausch via gemeinsamen Speicher

effiziente Ausführung

Realisierungsvarianten für Threads

User-Level-Threads

Realisierung im Benutzer-Adressraum
⇒ Bereitstellung eine Laufzeitumgebung inklusive Thread-Tabellen, Thread-Zustände und Thread-Scheduler

Vor/Nachteile:

effizient wg. kurzer Umschaltung zwischen Threads

Erweiterung des Betriebssystems

Problematisch: Behandlung blockierender Systemdienste ⇒ alle Threads werden blockiert.

Beispiel: User-Level-Threads

Implementierung in ältere UNIX-Varianten; POSIX (portable operating standard)

Kernel-Level-Threads

Realisierung im Betriebssystem-Kern
⇒ keine spezielle Laufzeitumgebung. Der Kern verwaltet Prozesse und Threads

Vor/Nachteile:

besser bei blockierendem Systemdienst. Auswahl eines rechenwilligen Threads.

Das Verfahren ist zeitaufwendiger, da Thread-Operationen Kernoperationen sind

Beispiel: Kernel-Level-Threads

Implementierung in Solaris, Windows 2000, Linux

Prozesse, ihre Verwaltung und Prozesskooperation

Vermeidung unbeabsichtigter Zustände von Ressourcen bei gemeinsamer Nutzung durch parallele Prozesse/Threads

Oberbegriff: Prozessinteraktion:

Kooperation: gezielter Informationsaustausch

Synchronisation: Bewerbung um Ressource, die zu einem Zeitpunkt nur exklusiv genutzt werden darf.

Prozess-Synchronisation

Threads:

0 = Observer: beobachtet und zählt Ereignisse,
L = Logger: protokolliert periodisch den Ereignis-Zähler

Ein Programm mit den beiden Threads O und L könnte so ablaufen, dass O kontinuierlich Ereignisse abfängt und L periodisch nach Ablauf einer Wartezeit (Bearbeitungsintervall) aktiv wird und den Zustand von O protokolliert.

Der Programmcode für Thread O könnte auszugsweise so aussehen:

while( 1 ) {

...

cnt = cnt + 1;

...

}

Der Programmcode für Thread L könnte auszugsweise so aussehen:

while( 1 ) {

sleep( 500 );

printf( "count status of O: %d\n", cnt );

cnt = 0;

}

Dabei können folgende Probleme auftreten:

Ereignisse gehen verloren:

Ereignisse werden doppelt gezählt:

Ursache für Inkonsistenzen:

Unterbrechungen mit Prozesswechsel

keine Unteilbarkeit von Anweisungsfolgen/Anweisungen formulierbar

Die eben gezeigten Probleme können aber umgangen werden, wenn eine Abstimmung zwischen den Prozessen bzgl. gemeinsam (global) genutzten Variablen vornimmt. Dafür maskiert man Code-Abschnitte als kritischen Abschnitt.

Kritischer Abschnitt

Ein kritischer Abschnitt ist eine Folge von Anweisungen mit modifizierendem Zugriff auf gemeinsam genutztes Betriebsmittel. Man verfolgt dabei das Ziel, zu jedem Zeitpunkt höchstens einen Prozess in seinem kritischen Abschnitt auszuführen. Folgende Fälle können mit drei Prozessen auftreten:

Alle drei Prozesse wollen zu verschiedenen Zeitpunkten kritische Abschnitte ausführen:
⇒ es gibt keine Konflikte; die Prozesse werden normal nach dem Prinzip des Scheduling ausgeführt

Prozess A führt einen Kritischen Abschnitt aus, dann möchte Prozess B auch einen Kritischen Abschnitt ausführen:
⇒ Prozess B muss warten, bis Prozess A von der Ausführung des Kritischen Abschnitts zurückkehrt um anschließend selbst so einen Abschnitt auszuführen.

Prozess A führt einen Kritischen Abschnitt aus, dann möchte sowohl Prozess B als auch Prozess C einen kritischen Abschnitt ausführen:
⇒ Prozess B und C müssen warten, bis Prozess A von der Ausführung des Kritischen Abschnitts zurückkehrt. Welcher der beiden wartenden Prozesse dann in den Kritischen Abschnitt wechseln darf, hängt von der Auswahl-Strategie ab. Dies kann FVFS (First Come First Serve) sein oder auch eine zufällige Auswahl.

Modell für Formulierung von Abstimmungsmechanismen:

Anforderungen:

Sicherheit: wechselseitiger Ausschluss

keine Annahmen über Ausführungsgeschwindigkeiten

keine gegenseitige Behinderung

Verlassen des Kritischen Abschnitts in endlicher Zeit

Fairness

Mechanismen

Mechanismen:

spezielle Hardware-Lösungen (Maschinenbefehle)

algorithmische Lösungen

Hardware-Lösung

Die Maschine kümmert sich um die Behandlung. Merkmale:

Unterbrechungssperre: ein Scheduler des Betriebssystems hat darauf keinen Einfluss. Nachteile:

beeinträchtigt Reaktivität

unsicher, denn was passiert, wenn ein Prozess nie mehr aus dem Kritischen Abschnitt zurückkehrt?

keine allgemeine Lösung, denn dann haben auch normale User die Möglichkeit, das System zu blockieren ⇒ Einschränkung auf Systemkern

spezielle Maschinenbefehle: z.B. test_a_set-Befehl, notiert in C-ähnlicher Form
BOOL test_a_set( bool* lock ) {
BOOL tmp = *lock; // test
*lock = true
return tmp;
}
Hinweis: diese Funktion ist ein einziger Maschinenbefehl und somit atomar und unteilbar. Der Ausführende Prozess muss also mit der Funktion testen, ob sie in den kritischen Abschnitt darf; anschließend muss sie zwingend lock = false aufrufen, damit die Sperre wieder aufgehoben wird.

Beispiel: Einsatz eines speziellen Maschinenbefehls

Algorithmische Lösung

Zugriff auf Variable unteilbare Aktion

Wechselseitiger Ausschluss :

Prozess 1	Prozess 2

Schwierigkeiten, die hierbei auftreten werden:

„umfassendere“ Absprache erforderlich

statisch und unflexibel

nur alternierendes Betreten

Betriebssystem-Lösung

Nachteil bisheriger Lösungen: Busy Waiting

Maschinenbefehl SWAP

Austauschen von Inhalten von Variablen:
a = true, b = false;
SWAP( a, b );
a = false, b = true;

Verwendung für wechselseitigen Ausschluss

Beim wechselseitigen Ausschluss existiert eine Schutzvariable lock, global je Prozess: lokale Variable

void enter_KA()

{

bool want = true;

do { swap( lock, want );

} while (want == true );

}

void exit_KA() { lock == false; }

Mechanismen zum wechselseitigen Ausschluss:

HW-Lösung

algorithmische Lösungen

Betriebssystem-Angebot

kein Busy Waiting mehr

freie Wahl der Reihenfolge

Angebot des Betriebssystems:

Semaphore

Mutex

Semaphore

Eine Semaphore ist eine Datenstruktur/ein Objekt, das im Minimalfall aus einer Integer-Variablen s besteht (Initialisierung ≥ 0). Außerdem sind Operationen atomar.

<< alles andere siehe Buch >>

Monitor als Lösung einer Programmiersprache. Nachteile der Semaphore:

keine Prüfung (ob P- und V-Operationen ausgeführt werden)

kein Test

keine Wartezeit-Beschränkung

Was ist ein Monitor? Natürlich eine Weiterentwicklung der Semaphore, aber was ist das nun?

kritisch/exklusiv zu nutzende Ressourcen und Operationen, die kritischen Abschnitten entsprechen

Vorstellung: <konfuses Bild>

P1 möchte auf kritisches Betriebsmittel der konfusen Grafik zugreifen ⇒ Aufruf einer Zugangsprozedur

Raum frei: Prozess betritt Monitor (hu, was läuft denn da? ⇒ Sendung mit der Maus!)

Raum belegt: Prozess wartet vor Monitor (und die Sanduhr dreht sich und dreht sich ...)

Prozess hat Zugriff auf kritisches BM (Betriebsmittel) abgeschlossen

Monitor wird verlassen. Ein anderer, wartender Prozess wird aktiviert (shake, baby, shake!)

Hey Erkan, kennst du korrekt Krassen Vorteil von der Monitor? Hier, schaust du:

Synchronisationsaufrufe implementiert durch Übersetzer, z.B. durch Umhüllung jedes Aufrufs einer Zugangsprozedur mittels P-/V-Paares
Dabei musst du fett korrekt checken: Monitor ≙ Sprachmittel. Guckst du!

Stefan: hey Erkan, das war aber nur ein Vorteil, warum machst du dann Punkt?
Erkan: ja mei, Stefan, nicht alle sind so Checker wie du! Ich geb mir mal korrektes Beispiel für das Sache hier:

Beispiel: Java

Schlüsselwort synchronised

class ...

{

public synchronized int op_A() { ... }

public synchronized int op_B() { ... }

}

Erweiterungen:

Möglichkeit zur Selbstblockade, falls eine bestimmte Bedingung nicht erfüllt ist. Die Möglichkeit, das zu formulieren, erfolgt über Bedingungsvariablen – das sind auch so eine Art Anzeigen, und es werden weitere Wartelisten eingerichtet. <scho widda korrekte Grafik>

Hey Stefan, das war schon wieder nur ein Punkt! Das ist genau so schwul wie wenn ich bei Planet Döner einen Döner mit allem bestell und dann nur ein Fladenbrot krieg!

Operationen:

cwait( <Bedingungsvariablen> ): Prozess wartet auf Eintreten einer bestimmten Situation, welche durch Bedingunbgsvariable benannt ist

csignal( <Bedingungsvariable> ): Bedingung erfüllt/Situation erreicht, blockierter Prozess wird in Zustand wartend gesetzt (erneute Bewerbung um Zutritt) (Hey Leila, darf isch zu dir?)

Beispiel:

monitor P_C {

void insert( int item ) {

while( count == N ) cwait( nonfull );

insert_item( item );

count++;

if( count == 1 ) csignal( nonempty );

}

int remove() {

while( count == 0 cwait( nonempty );

item = remove_item();

count--;

if( count == N-1 ) csignal( nonfull );

return item;

}

Speicher und ihre Verwaltung

Es gibt keinen Speicher. Nein, den gibt es nicht.

Wozu auch?

Lernziele für dieses Kapitel:

- keine -

Befehle können parallelisiert werden, wenn Anweisungen wie ADD und MUL verschiedene Register benutzen und sich somit nicht in die Quere kommen. Die Befehle werden dann in einen Befehls-Warteraum geladen. Dort wird überprüft, ob für eine Anweisung ein entsprechendes Funktionswerk vorhanden ist. Wenn ja, wird er dort hinein geladen. Gibt es also mehrere Funktionswerke, die Anweisungen aus dem Befehlswarteraum aufnehmen können, können die Befehle parallel abgearbeitet werden.

if-then-else, etc

Unterbrechungsvektor

PCB = Process Control Block

arbiter-Variable heißt so viel wie “Schiedsrichter-Variable”. Natürlich könnte man auch “foobar” hinschreiben oder “Blümchen”, nur ist das nicht sehr aussagekräftig

Mitschrift	Rechner- und Betriebssysteme (INF 5T)

© Arthur Müller	info@artoo4u.de	page 48 of 48

Rechner- und Betriebssysteme (INF 5T)

FH Ingolstadt; Mitschrift

FH Ingolstadt 2003

2003-10-08T23:41:12

Arthur Müller