CS计算机代考程序代写 file system ER cache assembler algorithm Betriebssysteme, Rechnernetze und verteilte Systeme 1 (BSRvS1)

Betriebssysteme, Rechnernetze und verteilte Systeme 1 (BSRvS1)
Klausurvorbereitung
Olaf Spinczyk,
Jochen Streicher, Horst Schirmeier
Arbeitsgruppe Eingebettete Systemsoftware
Lehrstuhl für Informatik 12 TU Dortmund
olaf.spinczyk@tu-dortmund.de
http://ess.cs.uni-dortmund.de/DE/Teaching/SS2008/BSRvS1/
1

Ablauf
Probeklausur (45 Minuten) Besprechung der Aufgaben Auswertung
Weitere Hinweise zur Vorbereitung
● ● ● ●
BSRvS1: Klausurvorbereitung, 21.01.2009 2
© Olaf Spinczyk

Ablauf
Probeklausur (45 Minuten)
Besprechung der Aufgaben Auswertung
Weitere Hinweise zur Vorbereitung
● ● ● ●
BSRvS1: Klausurvorbereitung, 21.01.2009 3
© Olaf Spinczyk

Probeklausur
… in (fast) allen Belangen realistisch:
Art der Aufgaben
● Auswahl aus dem gesamten Inhalt der Veranstaltung
Betriebssystemgrundlagen und UNIX-Systemprogrammierung in C alle Vorlesung und Übungen sind relevant
Umfang
● geplant für ca. 45 Minuten
Durchführung
● keine Hilfsmittel erlaubt (keine Spickzettel, Bücher, …!) ● bitte still arbeiten
● jeder für sich
Die Klausur wird nicht eingesammelt
●
● ●
●
BSRvS1: Klausurvorbereitung, 21.01.2009 4
© Olaf Spinczyk

Ablauf
Probeklausur (45 Minuten)
Besprechung der Aufgaben
Auswertung
Weitere Hinweise zur Vorbereitung
● ● ● ●
BSRvS1: Klausurvorbereitung, 21.01.2009 5
© Olaf Spinczyk

Besprechung der Aufgaben
Vorstellung der Musterlösung
Klärung von Fragen
Wiederholung anhand der passenden Vorlesungsfolien Bewertung der eigenen Lösungen!
● ● ● ●
BSRvS1: Klausurvorbereitung, 21.01.2009 6
© Olaf Spinczyk

1 Synchronisation, a) Race Conditions
Erklären Sie knapp in eigenen Worten den Begriff Race Condition.
Welche Maßnahme muss ergriffen werden, um diese zu vermeiden?
● ●
BSRvS1: Klausurvorbereitung, 21.01.2009 7
© Olaf Spinczyk

Begriff: Race Condition (oder auch „Wettkampfbedingung“)
Eine Race Condition ist eine Situation, in der mehrere Prozesse konkurrierend auf gemeinsame Daten zugreifen und diese manipulieren. Der letztendliche Wert der gemeinsamen Daten hängt bei einer Race Condition davon ab, welcher Prozess zuletzt zugegriffen hat. Das Ergebnis ist also nicht vorhersagbar.
Um Race Conditions zu vermeiden, müssen konkurrierende Prozesse synchronisiert werden.
●
●
BSRvS1: Klausurvorbereitung, 21.01.2009 8
© Olaf Spinczyk

Beispiel Race Condition
mehrere worker-Threads laufen parallel
Zugriff auf gemeinsame Daten: global_work_counter Zähler-Erhöhung kann verlorengehen
kritischer Abschnitt, der synchronisiert werden muss!
● ● ● ●
void worker() { while (1) {
int work; do_some_important_work(); work = global_work_counter; work++;
/* Unterbrechung! */
global_work_counter = work;
} }
void worker() { while (1) {
int work; do_some_important_work(); work = global_work_counter; work++; global_work_counter = work;
} }
BSRvS1: Klausurvorbereitung, 21.01.2009 9
© Olaf Spinczyk

1 Synchronisation, b) Semaphore
Welche d. folgenden Aussagen zu Semaphore treffen zu?
● Die Operation P erniedrigt den Semaphor in jedem Fall um 1.
● Semaphore sind BS-Abstraktionen zum Austausch von Synchronisationssignalen.
● Durch den Einsatz von Semaphore werden Verklemmungen verhindert.
● Semaphore sind geeignet für die Synchronisation von Erzeuger- Verbraucher-Prozessen.
●
BSRvS1: Klausurvorbereitung, 21.01.2009 10
© Olaf Spinczyk

Semaphor (semaphore) Eine ”nicht-negative ganze Zahl“,
für die zwei unteilbare Operationen definiert sind:
P (hol. prolaag, „erniedrige“; auch down, wait)
● hat der Semaphor den Wert 0, wird der laufende Prozess blockiert ● ansonsten wird der Semaphor um 1 dekrementiert
V (hol. verhoog, „erhöhe“; auch up, signal)
● auf den Semaphor ggf. blockierter Prozess wird deblockiert ● ansonsten wird der Semaphor um 1 inkrementiert
Eine Betriebssystemabstraktion zum Austausch von Synchronisationssignalen zwischen nebenläufig arbeitenden Prozessen.
●
●
BSRvS1: Klausurvorbereitung, 21.01.2009 11
© Olaf Spinczyk

Aufgabe 2 „Mensa“: Ablauf
wiederhole {
erniedrige(frei);
exklusiv {
kochen }
erhöhe(belegt);
}
frei = 3
erniedrige(belegt);
exklusiv {
Tablett nehmen
}
erhöhe(frei);
belegt = 4
= Semaphore
BSRvS1: Klausurvorbereitung, 21.01.2009 12
© Olaf Spinczyk

1 Synchronisation, b) Semaphore
x x
BSRvS1: Klausurvorbereitung, 21.01.2009 13
© Olaf Spinczyk

Dateisysteme, Aufgabe 2a
Zu einer bestimmten Dateiposition kann der zugehörige Block leicht berechnet werden ( Position / Blockgröße ):
● [x] Der Zugriff auf eine bestimmte Dateiposition ist i.A. schneller als
bei verketteter Speicherung.
Eine Datei lässt sich nur erweitern, wenn dahinter genug Platz ist. ● Problem: Wieviel Platz lässt man?
zu wenig: evtl. Umkopieren nötig
zu viel: Fragmentierung
● [ ] Es kann keine Fragmentierung auftreten.
● [ ] Das Verfahren eignet sich nicht für nur-lesbare Dateisysteme.
● [x] Vergrößern von Dateien erfordert evtl. ein Umkopieren der Daten.
Aufeinanderfolgende Blöcke liegen i.A. in einer Spur. Diese können gelesen/geschrieben werden, ohne dass ein Schwenkarm o.ä. bewegt werden muss.
● [x] Das Verfahren minimiert die Positionierzeit des Schreib-/Lesekopfes.
●
●
●
Block 0
Block 1
Block 02
Block 03
Block 4
Block 5
Block 06
Block 07
BSRvS1: Klausurvorbereitung, 21.01.2009 14
© Olaf Spinczyk

Dateisysteme, Aufgabe 2b
Antwort: Es wird eine C-Stream-Operation (fread) auf einen Dateideskriptor angewandt.
Erklärung: Zwei Möglichkeiten für Dateizugriff:
● low-level, plattformabhängig (POSIX)
Dateideskriptoren (int)
libc-Funktionen, die direkt Linux-Systemcalls aufrufen
● high-level, plattformunabhängig
Zeiger auf sog. Streams (FILE)
interne Pufferung
Standardstreams: stdin, stdout, stderr printf arbeitet auf stdout
●
●
BSRvS1: Klausurvorbereitung, 21.01.2009 15
© Olaf Spinczyk

„Low-Level“ Dateioperationen
Öffnen von Dateien mit open(2)
int open(const char *path, int flags)
● gibt einen Dateideskriptor zurück, der für die anderen Funktionen verwendet wird
Lesen aus Dateien mit read(2)
ssize_t read(int fd, void *buf, size_t count)
Schreiben in Dateien mit write(2)
ssize_t write(int fd, void *buf, size_t count)
Schließen von offenen Dateien mit close(2) int close(int fd)
Standardisiert u.a. in POSIX.1 2001
●
●
●
●
●
BSRvS1: Klausurvorbereitung, 21.01.2009 16
© Olaf Spinczyk

„High-Level“ Dateioperationen
Öffnen von Dateien mit fopen(3)
FILE *fopen(const char *path, const char *mode)
● Modi: r/r+ (lesen/+schreiben), w/w+ (schreiben/+lesen), a/a+ (anhängen/+lesen) (siehe Manpage)
Lesen aus Dateien mit fread(3)
Schreiben in Dateien mit fwrite(3)
Schließen von offenen Dateien mit fclose(3) int fclose(FILE *stream)
Im C-Standard enthalten, plattformunabhängig!
●
●
●
●
●
size_t fread(void *buf, size_t size, size_t count,
FILE *stream)
size_t fwrite(void *buf, size_t size, size_t count,
FILE *stream)
BSRvS1: Klausurvorbereitung, 21.01.2009 17
© Olaf Spinczyk

3 Prozesse, a) Prozesszustände
Füllen Sie das Prozesszustandsdiagramm mit den drei grundlegenden Zuständen RUNNING, READY und BLOCKED aus …
1
324
●
BSRvS1: Klausurvorbereitung, 21.01.2009 18
© Olaf Spinczyk

Prozessverhalten und -zustände (1)
●
●
●
Prozesszustände
RUNNING
● Prozess wird gerade
ausgeführt
READY
● Prozess ist rechenbereit,
wartet auf die CPU BLOCKED
● Prozess wartet auf die
Beendigung einer E/A- Aktivität
RUNNING A
BLOCKED
READY BC
A B C
CPU
jetzt
Zeit
BSRvS1: Klausurvorbereitung, 21.01.2009
19
© Olaf Spinczyk

Prozessverhalten und -zustände (2)
Prozess A hat einen E/A- Vorgang gestartet und ist in den Zustand BLOCKED übergegangen. Da A die CPU nun nicht benötigt, hat das Betriebssystem den Prozess C ausgewählt und von READY in RUNNING überführt. Es fand ein Kontextwechsel von A zu C statt.
RUNNING C
BLOCKED AB
READY
CPU
E/A
A B C
CPU
jetzt
Zeit
BSRvS1: Klausurvorbereitung, 21.01.2009
20
© Olaf Spinczyk

Prozessverhalten und -zustände (3)
C hat die CPU zu lange „besessen“, wurde „verdrängt“ und ist daher nun wieder im Zustand READY. Damit kann jetzt endlich auch B bearbeitet werden und wird RUNNING.
RUNNING B
BLOCKED AC
Zeitscheibe abgelaufen
READY
CPU
E/A
A B C
CPU
CPU
© Olaf Spinczyk
jetzt
Zeit
BSRvS1: Klausurvorbereitung, 21.01.2009
21

Prozessverhalten und -zustände (3)
Die E/A-Operation von A ist nun abgeschlossen. Daraufhin wird A nun READY und wartet auf die Zuteilung der CPU.
CPU
E/A
A B C
Zeitscheibe E/A-Operation abgelaufen fertig
CPU
CPU
BLOCKED
READY AC
RUNNING B
© Olaf Spinczyk
jetzt
Zeit
BSRvS1: Klausurvorbereitung, 21.01.2009
22

3 Prozesse, a) Prozesszustände
Füllen Sie das Prozesszustandsdiagramm mit den drei grundlegenden Zuständen RUNNING, READY und BLOCKED aus …
1
●
RUNNING
READY
324
BLOCKED
BSRvS1: Klausurvorbereitung, 21.01.2009 23
© Olaf Spinczyk

3 Prozesse, a) Prozesszustände
… und erklären Sie die Zustandsübergänge stichpunktartig.
●
1
RUNNING
READY
324
BLOCKED
BSRvS1: Klausurvorbereitung, 21.01.2009 24
© Olaf Spinczyk

3 Prozesse, a) Prozesszustände
… und erklären Sie die Zustandsübergänge stichpunktartig.
1. Zeitscheibe eines Prozesses abgelaufen, wird verdrängt 2. wartender Prozess bekommt die CPU zugeteilt
3. laufender Prozess hat E/A-Vorgang gestartet
4. E/A-Operation eines Prozesses ist beendet
1
●
RUNNING
READY
324
BLOCKED
BSRvS1: Klausurvorbereitung, 21.01.2009 25
© Olaf Spinczyk

3 Prozesse, b) Kindprozesse mit fork(2)
Sekundenabstand (vorgegeben) Vater: PID des Kindes ausgeben Kind: „Papa!“, terminieren Fehlerabfrage
● ● ● ●
int main(void) { pid_t pid;
while (1) {
pid = fork();
/* 1P fork */
/* 1P Fehlerabfrage */
/* 1P Fall Kind korrekt */
/* 1P Kind terminiert */
/* 1P Fall Vater korrekt */
/* 1P PID wird ausgegeben */
} }
BSRvS1: Klausurvorbereitung, 21.01.2009 26
if (pid < 0) { perror("fork"); } else if (pid == 0) { printf("Mama!\n"); return 0; } else { printf("%u\n", (unsigned)pid); } if (wait(NULL) == 1) perror("wait"); sleep(1); © Olaf Spinczyk 3 Prozesse, b) Kindprozesse mit fork(2) Sekundenabstand (vorgegeben) Vater: PID des Kindes ausgeben Kind: „Papa!“, terminieren Fehlerabfrage ● ● ● ● int main(void) { pid_t pid; while (1) { pid = fork(); /* 1P fork */ /* 1P Fehlerabfrage */ /* 1P Fall Kind korrekt */ /* 1P Kind terminiert */ /* 1P Fall Vater korrekt */ /* 1P PID wird ausgegeben */ } } BSRvS1: Klausurvorbereitung, 21.01.2009 27 if (pid < 0) { perror("fork"); } else if (pid == 0) { printf("Mama!\n"); return 0; } else { printf("%u\n", (unsigned)pid); } if (wait(NULL) == 1) perror("wait"); sleep(1); © Olaf Spinczyk 3 Prozesse, b) Kindprozesse mit fork(2) Sekundenabstand (vorgegeben) Vater: PID des Kindes ausgeben Kind: „Papa!“, terminieren Fehlerabfrage ● ● ● ● int main(void) { pid_t pid; while (1) { pid = fork(); /* 1P fork */ /* 1P Fehlerabfrage */ /* 1P Fall Kind korrekt */ /* 1P Kind terminiert */ /* 1P Fall Vater korrekt */ /* 1P PID wird ausgegeben */ } } BSRvS1: Klausurvorbereitung, 21.01.2009 28 if (pid < 0) { perror("fork"); } else if (pid == 0) { printf("Mama!\n"); return 0; } else { printf("%u\n", (unsigned)pid); } if (wait(NULL) == 1) perror("wait"); sleep(1); © Olaf Spinczyk 3 Prozesse, b) Kindprozesse mit fork(2) Sekundenabstand (vorgegeben) Vater: PID des Kindes ausgeben Kind: „Papa!“, terminieren Fehlerabfrage ● ● ● ● int main(void) { pid_t pid; while (1) { pid = fork(); /* 1P fork */ /* 1P Fehlerabfrage */ /* 1P Fall Kind korrekt */ /* 1P Kind terminiert */ /* 1P Fall Vater korrekt */ /* 1P PID wird ausgegeben */ } } BSRvS1: Klausurvorbereitung, 21.01.2009 29 if (pid < 0) { perror("fork"); } else if (pid == 0) { printf("Mama!\n"); return 0; } else { printf("%u\n", (unsigned)pid); } if (wait(NULL) == 1) perror("wait"); sleep(1); © Olaf Spinczyk 3 Prozesse, b) Kindprozesse mit fork(2) Sekundenabstand (vorgegeben) Vater: PID des Kindes ausgeben Kind: „Papa!“, terminieren Fehlerabfrage ● ● ● ● int main(void) { pid_t pid; while (1) { pid = fork(); /* 1P fork */ /* 1P Fehlerabfrage */ /* 1P Fall Kind korrekt */ /* 1P Kind terminiert */ /* 1P Fall Vater korrekt */ /* 1P PID wird ausgegeben */ } } BSRvS1: Klausurvorbereitung, 21.01.2009 30 if (pid < 0) { perror("fork"); } else if (pid == 0) { printf("Mama!\n"); return 0; } else { printf("%u\n", (unsigned)pid); } if (wait(NULL) == 1) perror("wait"); sleep(1); © Olaf Spinczyk 3 Prozesse, c) wait() Weshalb ist der (vorgegebene) Aufruf von wait() wichtig? ● int main(void) { pid_t pid; while (1) { pid = fork(); /* 1P fork */ /* 1P Fehlerabfrage */ /* 1P Fall Kind korrekt */ /* 1P Kind terminiert */ /* 1P Fall Vater korrekt */ /* 1P PID wird ausgegeben */ if (pid < 0) { perror("fork"); } else if (pid == 0) { printf("Mama!\n"); return 0; } else { printf("%u\n", (unsigned)pid); } if (wait(NULL) == 1) perror("wait"); sleep(1); } } BSRvS1: Klausurvorbereitung, 21.01.2009 31 © Olaf Spinczyk 3 Prozesse, c) wait() Weshalb ist der (vorgegebene) Aufruf von wait() wichtig? ● wait() räumt den entstandenen Zombie weg ● diese sammeln sich sonst über die Zeit an! ● int main(void) { pid_t pid; while (1) { pid = fork(); /* 1P fork */ /* 1P Fehlerabfrage */ /* 1P Fall Kind korrekt */ /* 1P Kind terminiert */ /* 1P Fall Vater korrekt */ /* 1P PID wird ausgegeben */ if (pid < 0) { perror("fork"); } else if (pid == 0) { printf("Mama!\n"); return 0; } else { printf("%u\n", (unsigned)pid); } if (wait(NULL) == 1) perror("wait"); sleep(1); } } BSRvS1: Klausurvorbereitung, 21.01.2009 32 © Olaf Spinczyk Scheduling, Aufgabe 4a t (ms) laufend normale WS Vorzugs-WS blockiert 0 F1 F2,F3,F4 5 F2 F3,F4 F1(15) 10 F2 F3,F4 F1(15) 15 F3 F4 F1(15), F2(10) 20 F3 F4 F2(10) F1(15) 25 F3 F4 F2(10) F1(15) 30 F3 F4 F2(10), F1(15) 35 F2 F4, F3 F1(15) 40 F1 F4, F3 F2(5) 45 F1 F4,F3 F2(5) 50 F1 F4,F3 F2(5) 55 F2 F4,F3,F1 © Olaf Spinczyk BSRvS1: Klausurvorbereitung, 21.01.2009 33 Scheduling, Aufgabe 4b Prozessverdrängung ● Obwohl der gerade laufende Prozess noch weiterlaufen könnte, wird auf einen anderen Prozess umgeschaltet. ● Keine Verdrängung: Prozessumschaltung nur, wenn der laufende Prozess auf etwas warten muss (Semaphore, Ein-Ausgabe...). Verfahren ● [x] SRTF: Verdrängung, sobald ein Prozess laufbereit ist, dessen erwartete CPU-Stoßdauer geringer ist, als die erwartete Rest-CPU- Stoßdauer des laufenden. ● [ ] SPN ● [x] RR: Verdrängung durch Zeitgeber ● []FCFS ● ● BSRvS1: Klausurvorbereitung, 21.01.2009 34 © Olaf Spinczyk 5 Speicherverw., a) Seitenadressierung Welche Aussagen zur Seitenadressierung sind richtig? ● Seitenadressierung erzeugt internen Verschnitt ● Durch S. werden Indirektionen beim Speicherzugriff eingespart. ● Seitenadressierung und Segmentierung können kombiniert werden. ● Durch ein Präsenzbit in der Seiten-Kacheltabelle werden logische von physikalischen Adressen unterschieden. ● Der Translation Look-Aside Buffer (TLB) beschleunigt die Seitenabbildung. ● BSRvS1: Klausurvorbereitung, 21.01.2009 35 © Olaf Spinczyk MMU mit Seiten-Kacheltabelle (2) Seitenadressierung erzeugt internen Verschnitt ● letzte Seite eventuell nicht vollständig genutzt Seitengröße ● kleine Seiten verringern internen Verschnitt, vergrößern aber die Seiten-Kacheltabelle (und umgekehrt) ● übliche Größen: 512 Bytes — 8192 Bytes große Tabelle, die im Speicher gehalten werden muss viele implizite Speicherzugriffe nötig nur ein „Segment“ pro Kontext Kombination mit Segmentierung ● ● ● ● ● ➔ BSRvS1: Klausurvorbereitung, 21.01.2009 36 © Olaf Spinczyk MMU mit Seiten-Kacheltabelle Tabelle setzt Seiten in Kacheln um SKT Basisregister + Seiten-Kacheltabelle Startadr. 00000 00001 00002 00003 00004 logische Adresse ● 00002 12a ffe0 fxxx ... physikalische Adresse ffe0f 12a © Olaf Spinczyk BSRvS1: Klausurvorbereitung, 21.01.2009 37 Mehrstufige Seitenadressierung Beispiel: zweifach indirekte Seitenadressierung logische Adresse ● ● ● 3 02 03 12a ... ... 3 ... ... ... 02 ... 03 ... © Olaf Spinczyk Präsenzbit auch für jeden Eintrag in den höheren Stufen ● Tabellen werden aus- und einlagerbar Aber: Noch mehr implizite Speicherzugriffe BSRvS1: Klausurvorbereitung, 21.01.2009 38 Ein-/Auslagerung von Seiten Es ist nicht nötig ein gesamtes Segment aus- bzw. einzulagern ● Seiten können einzeln ein- und ausgelagert werden ● ● Hardware-Unterstützung ● Ist das Präsenzbit gesetzt, bleibt alles wie bisher. Seiten-Kacheltabelle Startadr. Präsenzbit 0000 ● Ist das Präsenzbit gelöscht, wird eine Unterbrechung ausgelöst (page fault). 0001 ffe0 fxxx X ... ● Die Unterbrechungsbehandlung 0002 kann nun für das Laden der Seite vom Hintergrundspeicher sorgen und den Speicherzugriff danach wiederholen (benötigt HW-Support in der CPU). BSRvS1: Klausurvorbereitung, 21.01.2009 39 © Olaf Spinczyk 5 Speicherverw., a) Seitenadressierung x x x BSRvS1: Klausurvorbereitung, 21.01.2009 40 © Olaf Spinczyk 5 Speicherverw., b) LRU Least Recently Used Referenzfolge: 3, 1, 2, 4, 2, 1, 5, 3, 2, 5, 1 ● ● BSRvS1: Klausurvorbereitung, 21.01.2009 41 © Olaf Spinczyk 5 Speicherverw., c) OPT Die bei fester Kachelmenge optimale Ersetzungsstrategie OPT würde für die minimale Anzahl von Einlagerungen/Ersetzungen sorgen. Warum nicht praktikabel? ● ● BSRvS1: Klausurvorbereitung, 21.01.2009 42 © Olaf Spinczyk Optimale Ersetzungsstrategie Vorwärtsabstand ● Zeitdauer bis zum nächsten Zugriff auf die entsprechende Seite Strategie OPT (oder MIN) ist optimal (bei fester Kachelmenge): minimale Anzahl von Einlagerungen/Ersetzungen (hier 7) ● „Ersetze immer die Seite mit dem größten Vorwärtsabstand!“ Implementierung von OPT nahezu unmöglich ● Referenzfolge müsste vorher bekannt sein ● OPT meist nur zum Vergleich von Strategien brauchbar ● ● ● BSRvS1: Klausurvorbereitung, 21.01.2009 43 © Olaf Spinczyk 5 Speicherverw., c) OPT Die bei fester Kachelmenge optimale Ersetzungsstrategie OPT würde für die minimale Anzahl von Einlagerungen/Ersetzungen sorgen. Warum nicht praktikabel? ● Die Referenzfolge müsste vorher bekannt sein! ● Das ist in der Praxis natürlich so gut wie nie der Fall. ● ● BSRvS1: Klausurvorbereitung, 21.01.2009 44 © Olaf Spinczyk Ablauf Probeklausur (45 Minuten) Besprechung der Aufgaben Auswertung Weitere Hinweise zur Vorbereitung ● ● ● ● BSRvS1: Klausurvorbereitung, 21.01.2009 45 © Olaf Spinczyk Auswertung Bitte schnell einmal die Punkte zählen ... Notenspiegel Punkte Note 36 – 40 1 30 – 35,5 2 24 – 29,5 3 20 – 23,5 4 < 20 5 ● ● BSRvS1: Klausurvorbereitung, 21.01.2009 46 © Olaf Spinczyk Ablauf Probeklausur (45 Minuten) Besprechung der Aufgaben Auswertung Weitere Hinweise zur Vorbereitung ● ● ● ● BSRvS1: Klausurvorbereitung, 21.01.2009 47 © Olaf Spinczyk Weitere Hinweise zur Vorbereitung Inhalt der Folien lernen ● Klassifizieren: Was muss ich lernen? Was muss ich begreifen? Übungsaufgaben verstehen, C und UNIX „können“ ● ASSESS-System bleibt mindestens bis zur Klausur offen Bei Fragen zur Korrektur melden ● Am besten die Aufgaben noch einmal lösen ● Optionale Zusatzaufgaben bearbeiten Beispielaufgaben lösen ● „Last Chance Test“ und Musterlösung sind auf der BSRvS1- Webseite verfügbar Literatur zur Lehrveranstaltung durchlesen BSRvS1-Forum nutzen Sprechstunde: 2.2.-6.2., jeweils 13-15 Uhr, OH16 R. E03 BSRvS1: Klausurvorbereitung, 21.01.2009 48 ● ● ● ● ● ● © Olaf Spinczyk Literatur: Standardwerke © Olaf Spinczyk Operating System Concepts. von Abraham Silberschatz, Peter Galvin, und Greg Gagne Modern Operating Systems 2/e. von Andrew S. Tanenbaum BSRvS1: Klausurvorbereitung, 21.01.2009 49 Operating Systems.: Internals and Design Principles. von William Stallings Betriebssysteme, Rechnernetze und verteilte Systeme 1 (BSRvS 1) Klausurvorbereitung Olaf Spinczyk, Jochen Streicher, Horst Schirmeier Arbeitsgruppe Eingebettete Systemsoftware Lehrstuhl für Informatik 12 TU Dortmund Vorname.Nachname@tu-dortmund.de http://ess.cs.uni-dortmund.de/ http://ess.cs.tu-dortmund.de/DE/Teaching/SS2009/BSRvS1/ 1 Ablauf Probeklausur (45 Minuten) Besprechung der Aufgaben Auswertung Weitere Hinweise zur Vorbereitung ● ● ● ● Klausurvorbereitungsveranstaltung 20.01.2010 2 Probeklausur ... in (fast) allen Belangen realistisch: Art der Aufgaben ● Auswahl aus dem gesamten Inhalt der Veranstaltung - Betriebssystemgrundlagen und UNIX-Systemprogrammierung in C - alle Vorlesungen und Übungen sind relevant Umfang ● geplant für ca. 45 Minuten Durchführung ● keine Hilfsmittel erlaubt (keine Spickzettel, Bücher, ...!) ● bitte still arbeiten ● jeder für sich Die Klausur wird nicht eingesammelt Klausurvorbereitungsveranstaltung 20.01.2010 3 ● ● ● ● Besprechung der Aufgaben Vorstellung der Musterlösung Klärung von Fragen Wiederholung anhand der passenden Vorlesungsfolien Bewertung der eigenen Lösungen! ● ● ● ● Klausurvorbereitungsveranstaltung 20.01.2010 4 Prozesse und Scheduling a) Zustände und Ebenen des Prozess-Schedulings EXIT ● BLOCKED SUSPEND Klausurvorbereitungsveranstaltung 20.01.2010 5 Wdh.: Kurzfristige Einplanung bereit (READY) zur Ausführung durch den Prozessor (die CPU) ● Der Prozess ist auf der Warteliste für die CPU-Zuteilung (ready list) ● Seine Listenposition bestimmt sich durch das Einplanungsverfahren laufend (RUNNING) Zuteilung des Betriebsmittels ”CPU“ ist erfolgt ● Der Prozess führt Berechnungen durch, er vollzieht seinen CPU-Stoß ● Für jeden Prozessor gibt es zu einem Zeitpunkt nur einen laufenden Prozess blockiert (BLOCKED) auf ein bestimmtes Ereignis ● Der Prozess führt ”Ein-/Ausgabe“ durch, er vollzieht seinen E/A-Stoß ● Er erwartet die Erfüllung mindestens einer Bedingung ● ● ● Klausurvorbereitungsveranstaltung 20.01.2010 6 Wdh.: Mittelfristige Einplanung Ein Prozess ist komplett ausgelagert, d. h. der Inhalt seines gesamten Adressraums wurde in den Hintergrundspeicher verschoben (swap-out) und der von dem Prozess belegte Vordergrundspeicher wurde freigegeben. Die Einlagerung (swap-in) des Adressraums ist abzuwarten: ausgelagert bereit (READY SUSPEND) ● Die CPU-Zuteilung (”bereit“) ist außer Kraft gesetzt ● Der Prozess ist auf der Warteliste für die Speicherzuteilung ausgelagert blockiert (BLOCKED SUSPEND) ● Der Prozess erwartet weiterhin ein Ereignis (”blockiert“) ● Tritt das Ereignis ein, wird der Prozess ”ausgelagert bereit“ ● ● Klausurvorbereitungsveranstaltung 20.01.2010 7 Wdh.: Langfristige Einplanung erzeugt (NEW) und fertig zur Programmverarbeitung fork(2) ● Der Prozess ist instanziiert, ihm wurde ein Programm zugeordnet ● Ggf. steht die Zuteilung des Betriebsmittels ”Speicher“ jedoch noch aus beendet (EXIT) und erwartet die Entsorgung exit(2)/wait(2) ● Der Prozess ist terminiert, seine Betriebsmittel werden freigegeben ● Ggf. muss ein anderer Prozess den ”Kehraus“ vollenden (z. B. UNIX) ● ● Klausurvorbereitungsveranstaltung 20.01.2010 8 Prozesse und Scheduling a) Zustände und Ebenen des Prozess-Schedulings ● EXIT NEW READY SUSPEND BLOCKED SUSPEND RUNNING READY BLOCKED Klausurvorbereitungsveranstaltung 20.01.2010 9 Prozesse und Scheduling a) Zustände und Ebenen des Prozess-Schedulings ● RUNNING READY BLOCKED Short Term Short Term READY SUSPEND BLOCKED SUSPEND Medium Term Medium Term EXIT NEW Long Term Long Term Klausurvorbereitungsveranstaltung 20.01.2010 10 Prozesse und Scheduling b) Welche der folgenden Aussagen zu UNIX-Prozessen sind richtig? ● Neue Prozesse können mit Hilfe des Systemaufrufs fork(2) erzeugt werden. ● Um einen Zombie-Prozess zu entfernen, muss der Vater-Prozess kill(2) aufrufen. Nein, wait oder waitpid. ● Der Vater-Prozess wird mit dem Signal SIGTERM über die Terminierung eines Kindes informiert. Nein, SIGCHLD. SIGTERM → Töten ● Jeder Prozess wird nach seiner Terminierung zumindest kurzzeitig zum Zombie. ● Der init-Prozess übernimmt das Entfernen eines Zombies, wenn sein Vater- Prozess terminiert ist. ●    Klausurvorbereitungsveranstaltung 20.01.2010 11 Prozesse und Scheduling c) First-come, first-served ● Vorgehensweise? ● Auftretendes Problem? ● ... unter welchen Bedingungen? ● Klausurvorbereitungsveranstaltung 20.01.2010 12 Prozesse und Scheduling c) First-come, first-served ● Vorgehensweise? - Einreihungskriterium: Ankunftszeit („wer zuerst kommt, mahlt zuerst“) - nicht-präemptiv ● Auftretendes Problem? ● ... unter welchen Bedingungen? ● T1 T2 T1 T2 T1 T2 t Klausurvorbereitungsveranstaltung 20.01.2010 13 Prozesse und Scheduling c) First-come, first-served ● Vorgehensweise? - Einreihungskriterium: Ankunftszeit („wer zuerst kommt, mahlt zuerst“) - nicht-präemptiv ● Auftretendes Problem? - „Konvoi-Effekt“ ● ... unter welchen Bedingungen? ● T1 T2 T1 T2 T1 T2 t Klausurvorbereitungsveranstaltung 20.01.2010 14 Prozesse und Scheduling c) First-come, first-served ● Vorgehensweise? - Einreihungskriterium: Ankunftszeit („wer zuerst kommt, mahlt zuerst“) - nicht-präemptiv ● Auftretendes Problem? - „Konvoi-Effekt“ ● ... unter welchen Bedingungen? - Mix aus kurz laufenden, E/A-lastigen Prozessen und Prozessen mit langen CPU-Bursts ● T1 T2 T1 T2 T1 T2 t Klausurvorbereitungsveranstaltung 20.01.2010 15 Prozesse und Scheduling d) Abschätzung von CPU-Stoß-Längen ● Shortest Process Next – der Prozess, dessen CPU-Stoß erwartungsgemäß der kürzeste ist, wird gescheduled → Abschätzung notwendig ● Das geschieht unter Verwendung der Historie des Prozesses (also der Länge seiner bisherigen CPU-Stöße): ● Formel (kann man auch erraten und anhand der Tabelle verifizieren): Sn1=α⋅Tn1−α⋅Sn ● α = 0,5 (leicht durch Einsetzen von Tabellenwerten ausrechenbar) ● Das Verfahren nennt sich Das Verfahren nennt sich „exponentielle Glättung“: „exponentielle Glättung“: Weiter zurückliegende CPU- Weiter zurückliegende CPU- Stöße werden weniger gewichtet. Stöße werden weniger gewichtet. Klausurvorbereitungsveranstaltung 20.01.2010 16 Synchronisation / Verklemmungen a) Semaphor-Implementierung ● Auftrag: Implementierung der Operationen p() und v(), wie sie innerhalb des Betriebssystems aussehen ● Hintergrundwissen – Was ist ein Semaphor? Was ist P / V? ● Klausurvorbereitungsveranstaltung 20.01.2010 17 ● E. Dijkstra: Semaphor (semaphore) Eine ”nicht-negative ganze Zahl“, für die zwei unteilbare Operationen definiert sind: P (hol. prolaag, „erniedrige“; auch down, wait) -1 hat der Semaphor den Wert 0, wird der laufende Prozess blockiert ● ansonsten wird der Semaphor um 1 dekrementiert ● Eine Betriebssystemabstraktion zum Austausch von Synchronisationssignalen zwischen nebenläufig arbeitenden Prozessen. ● V (hol. verhoog, „erhöhe“; auch up, signal) ● +1auf den Semaphor ggf. blockierter Prozess wird deblockiert ● ansonsten wird der Semaphor um 1 inkrementiert Klausurvorbereitungsveranstaltung 20.01.2010 18 Synchronisation / Verklemmungen a) Semaphor-Implementierung ● Auftrag: Implementierung der Operationen p() und v(), wie sie innerhalb des Betriebssystems aussehen ● vorhanden: - Semaphor-Zähler: Variable counter - Datentyp zum Verwalten einer Prozesswarteschlange: Waitingroom - Operationen darauf: enqueue, dequeue - Scheduler-Funktionen: active, block, wakeup ● p: p: if (counter > 0) if (counter > 0)
else
else
counter = counter – 1;
counter = counter – 1;
sem_wr.enqueue(sched.active())
sem_wr.enqueue(sched.active())
block()
block()
Klausurvorbereitungsveranstaltung 20.01.2010 19

●
E. Dijkstra: Semaphor (semaphore) Eine ”nicht-negative ganze Zahl“,
für die zwei unteilbare Operationen definiert sind: P (hol. prolaag, „erniedrige“; auch down, wait)
-1 hat der Semaphor den Wert 0, wird der laufende Prozess blockiert ● ansonsten wird der Semaphor um 1 dekrementiert
●
Eine Betriebssystemabstraktion zum Austausch von Synchronisationssignalen zwischen nebenläufig arbeitenden Prozessen.
●
V (hol. verhoog, „erhöhe“; auch up, signal) ●
+1auf den Semaphor ggf. blockierter Prozess wird deblockiert ● ansonsten wird der Semaphor um 1 inkrementiert
Klausurvorbereitungsveranstaltung 20.01.2010 20

Synchronisation / Verklemmungen
a) Semaphor-Implementierung
● Auftrag: Implementierung der Operationen p() und v(), wie sie innerhalb des Betriebssystems aussehen
● vorhanden:
– Semaphor-Zähler: Variable counter
– Datentyp zum Verwalten einer Prozesswarteschlange: Waitingroom – Operationen darauf: enqueue, dequeue
– Scheduler-Funktionen: active, block, wakeup
●
p:
p:
if (counter > 0) if (counter > 0)
else
else
counter = counter – 1;
counter = counter – 1;
sem_wr.enqueue(sched.active())
sem_wr.enqueue(sched.active())
block()
block()
v:
v:
process = sem_wr.dequeue()
process = sem_wr.dequeue()
if (process) if (process)
else
else
sched.wakeup(process)
sched.wakeup(process)
counter = counter + 1
counter = counter + 1
Klausurvorbereitungsveranstaltung 20.01.2010 21

Synchronisation / Verklemmungen
b) Deadlock
● Prozesse K1 und K2, die im Laufe ihrer Ausführung die …
● … unteilbaren Ressourcen L und R belegen und wieder freigeben
●
Fortschritt Prozess K2
Bereich, nach dessen Betreten eine Verklemmung unvermeidbar wird?

Wo tritt sie tatsächlich auf?
LR
L R
Fortschritt Prozess K1
Betriebsmittel
22
Klausurvorbereitungsveranstaltung 20.01.2010
Betriebsmittel

Synchronisation / Verklemmungen
b) Deadlock
● Prozesse K1 und K2, die im Laufe ihrer Ausführung die …
● … unteilbaren Ressourcen L und R belegen und wieder freigeben
●
Fortschritt Prozess K2
nicht betretbarer Bereich? → Ressourcen unteilbar!
 Verklemmung unvermeidbar
LR
L R
Fortschritt Prozess K1
Betriebsmittel
23
Klausurvorbereitungsveranstaltung 20.01.2010
Betriebsmittel

Synchronisation / Verklemmungen
b) Deadlock
● Prozesse K1 und K2, die im Laufe ihrer Ausführung die …
● … unteilbaren Ressourcen L und R belegen und wieder freigeben
●
Fortschritt Prozess K2
möglicher Ablauf ohne Verklemmung?
 Verklemmung unvermeidbar
LR
L R
Fortschritt Prozess K1
Betriebsmittel
24
Klausurvorbereitungsveranstaltung 20.01.2010
Betriebsmittel

3) Skalierbarkeit
Skalierbarkeit
● Eine parallele Rechnerarchitektur gilt als skalierbar, wenn die effektiv verfügbare Rechenleistung sich proportional zur Anzahl der eingebauten CPUs verhält.
oder
● Verhalten der tatsächlichen Rechenleistung im Vergleich zur Anzahl der eingebauten CPUs
Gründe für mangelnde Skalierbarkeit
● Hardware: gemeinsamer Speicherbus/-controller(besser: lokale Speicher mit lokalen Bussen)
● Betriebsystem:
– grobgranulares Locking
– viele gemeinsame Datenstrukturen zwischen CPUs
– Häufiges Wechseln von Prozessen zwischen CPUs (kalter Cache) – lokale Bereitliste läuft häufig leer
●
●
Klausurvorbereitungsveranstaltung 20.01.2010 25

4a) Segmente und Variablen
Klausurvorbereitungsveranstaltung 20.01.2010 26

4a) Segmente und Variablen
hohe Adressen
Stack
Heap
BSS
(Block Started by Symbol, Block Storage Segment) (uninitialisierte Daten)
Daten
(vorinitialisierte Daten)
Text
(Programmcode)
#include
#include
char a[] = “ABCDEFG”;
char a[] = “ABCDEFG”;
int b;
int b;
int main(void) {
int main(void) {
}
return 0;
}
int c;
int c;
char *d = malloc(128);
char *d = malloc(128);
return 0;
niedrige Adressen
Daten
Code
Klausurvorbereitungsveranstaltung 20.01.2010 27
zeigt auf

4b) Paging
Seitenadressierung erzeugt internen Verschnitt.
Invertierte Seiten-Kacheltabellen sind grundsätzlich nur auf 64-Bit-Systemen möglich.
→ überall möglich, aber bei großen Adressräumen eher nötig
Seitenadressierung und Segmentierung schließen sich gegenseitig aus.
● ●
●
Klausurvorbereitungsveranstaltung 20.01.2010 28

Segmentierung und Seitenadressierung
Segmenttabellen- basisregister
Segmenttabelle +
SKT Zeiger Seitenzahl
logische Adresse
Seiten-Kacheltabelle
1
0002
12a
Startadr.
00 01 02
+
00000 00001 00002
00003 00004
…
0005
ffe0 fxxx
< ja Trap: Schutzverletzung ... physikalische Adresse ffe0f 12a Klausurvorbereitungsveranstaltung 20.01.2010 29 4b) Paging Seitenadressierung erzeugt internen Verschnitt. Invertierte Seiten-Kacheltabellen sind grundsätzlich nur auf 64-Bit-Systemen möglich. → überall möglich, aber bei großen Adressräumen eher nötig Seitenadressierung und Segmentierung schließen sich gegenseitig aus. Durch mehrstufige Seitenadressierung kann der für Seitentabellen benötigte Platz im Hauptspeicher reduziert werden. ● ● ● ● Klausurvorbereitungsveranstaltung 20.01.2010 30 Mehrstufige Seitenadressierung Beispiel: zweifach indirekte Seitenadressierung logische Adresse ● ● ● 3 02 03 12a ... ... 3 ... ... ... 02 ... 03 ... Präsenzbit auch für jeden Eintrag in den höheren Stufen ● Tabellen werden aus- und einlagerbar Aber: Noch mehr implizite Speicherzugriffe Klausurvorbereitungsveranstaltung 20.01.2010 31 4b) Paging Seitenadressierung erzeugt internen Verschnitt. Invertierte Seiten-Kacheltabellen sind grundsätzlich nur auf 64-Bit-Systemen möglich. → überall möglich, aber bei großen Adressräumen eher nötig Seitenadressierung und Segmentierung schließen sich gegenseitig aus. Durch mehrstufige Seitenadressierung kann der für Seitentabellen benötigte Platz im Hauptspeicher reduziert werden. Der logische Adressraum wird in Seiten, der physikalische in Kacheln unterteilt. ● ● ● ● ● Klausurvorbereitungsveranstaltung 20.01.2010 32 4b) Seitenadressierung Klausurvorbereitungsveranstaltung 20.01.2010 33 5a) Kontinuierliche Speicherung Vorteile ● minimale Schwenkarmbewegungen beim Lesen einer Datei oder ● bestimmte Position einer Datei schnell auffindbar Nachteile ● Vergrößern von Dateien schwierig - Größe nicht im voraus bekannt - evtl. Umkopieren nötig oder ● Verschnitt beim Verkleinern/Löschen von Dateien → vgl. Speicherverwaltung → Besonders geeignet für read-only-Dateisysteme ● ● Block 0 Block 1 Block 02 Block 03 Block 4 Block 5 Block 06 Block 07 Klausurvorbereitungsveranstaltung 20.01.2010 34 E/A-Scheduling: Elevator Bewegung des Plattenarm in eine Richtung bis keine Aufträge mehr vorhanden sind (Fahrstuhlstrategie) ● Gleiche Referenzfolge (Annahme: bisherige Kopfbewegung Richtung 0) ● Gesamtzahl der Spurwechsel: 208 ● Neue Aufträge werden miterledigt ohne zusätzliche Positionierungszeit und ohne mögliche Aushungerung ● Klausurvorbereitungsveranstaltung 20.01.2010 35 5b) I/O-Scheduler (Fahrstuhl) Anstehende Aufträge gelesene Spur 1, 4, 7, 2 1 4, 7, 2 2 4, 7 4 7, 3, 6, 0 6 7, 3, 0 7 3, 0 3 0, 5, 2 2 0, 5 0 5 5 3, 6, 0 5, 2 innen Spur 7 Spur 6 Spur 5 Spur 4 Spur 3 Spur 2 Spur 1 Spur 0 Klausurvorbereitungsveranstaltung 20.01.2010 36 Auswertung Bitte schnell einmal die Punkte zusammenzählen ... Notenspiegel: Punkte Note 39,5–45 1 34–39 2 28,5–33,5 3 23–28 4 0–22,5 5 ● ● Klausurvorbereitungsveranstaltung 20.01.2010 37 Weitere Hinweise zur Vorbereitung Inhalt der Folien lernen ● Klassifizieren: Was muss ich lernen? Was muss ich begreifen? Übungsaufgaben verstehen, C und UNIX „können“ ● ASSESS-System bleibt mindestens bis zur Klausur offen - Bei Fragen zur Korrektur melden ● Am besten die Aufgaben noch einmal lösen ● Optionale Zusatzaufgaben bearbeiten Beispielaufgaben lösen ● „Last Chance Test“ und Musterlösung sind auf der BSRvS1- Webseite verfügbar Literatur zur Lehrveranstaltung durchlesen BSRvS1-Forum nutzen Sprechstunde: 28.01. und 01.-03.02., jeweils 10-12 Uhr, OH-16/E03 (am besten vorher per Mail ankündigen!) ● ● ● ● ● ● Klausurvorbereitungsveranstaltung 20.01.2010 38 Empfohlene Literatur [1] A. Silberschatz et al. Operating System Concepts. Wiley, 2004. ISBN 978-0471694663 [2] A. Tanenbaum: Modern Operating Systems (2nd ed.). Prentice Hall, 2001. ISBN 0-13-031358-0 [3] B. W. Kernighan, D. M. Ritchie. The C Programming Language. Prentice-Hall, 1988. ISBN 0-13-110362-8 (paperback) 0-13-110370-9 (hardback) [4] R. Stevens, Advanced Programming in the UNIX Environment, Addison-Wesley, 2005. ISBN 978-0201433074 Klausurvorbereitungsveranstaltung 20.01.2010 39 Betriebssysteme (BS) Probeklausur Olaf Spinczyk, Horst Schirmeier Arbeitsgruppe Eingebettete Systemsoftware Lehrstuhl für Informatik 12 TU Dortmund Vorname.Nachname@tu-dortmund.de http://ess.cs.uni-dortmund.de/ http://ess.cs.tu-dortmund.de/DE/Teaching/SS2010/BS/ 1 Ablauf Probeklausur (45 Minuten) Besprechung der Aufgaben Auswertung Weitere Hinweise zur Vorbereitung ● ● ● ● Klausurvorbereitungsveranstaltung 12.07.2010 2 Probeklausur ... in (fast) allen Belangen realistisch: Art der Aufgaben ● Auswahl aus dem gesamten Inhalt der Veranstaltung - Betriebssystemgrundlagen und UNIX-Systemprogrammierung in C - alle Vorlesungen und Übungen sind relevant Umfang ● kürzer als das „Original“: ca. 40–45 (statt 60) Minuten Durchführung ● keine Hilfsmittel erlaubt (keine Spickzettel, Bücher, ...) ● bitte still arbeiten ● jeder für sich Die Klausur wird nicht eingesammelt. Klausurvorbereitungsveranstaltung 12.07.2010 3 ● ● ● ● Besprechung der Aufgaben Vorstellung der Musterlösung Klärung von Fragen Wiederholung anhand der passenden Vorlesungsfolien Bewertung der eigenen Lösungen! ● ● ● ● Klausurvorbereitungsveranstaltung 12.07.2010 4 1 – Prozesse und Scheduling a) Prozessmodelle (J / N?) N JN ? ● Klausurvorbereitungsveranstaltung 12.07.2010 5 Vorlesungsfolien: 3-Prozesse Leichtgewichtige Prozesse (Threads) Die 1:1-Beziehung zwischen Kontrollfluss und Adressraum wird aufgebrochen. ● Eng kooperierende Threads können sich einen Adressraum teilen (code + data + bss, nicht stack!). Vorteile: ● Aufwändige Operationen können in einen leichtgewichtigen Hilfsprozess ausgelagert werden, während der Elternprozess erneut auf Eingabe reagieren kann. - Typisches Beispiel: Webserver ● Programme, die aus mehreren unabhängigen Kontrollflüssen bestehen, profitieren unmittelbar von Multiprozessor-Hardware. ● Schneller Kontextwechsel, wenn man im selben Adressraum bleibt. ● Je nach Scheduler eventuell mehr Rechenzeit. Nachteil: ● Programmierung ist schwierig: Zugriff auf gemeinsame Daten muss koordiniert werden. ● ● ● Klausurvorbereitungsveranstaltung 12.07.2010 6 Vorlesungsfolien: 3-Prozesse Federgewichtige Prozesse (engl. User-Level Threads) Werden komplett auf der Anwendungsebene implementiert. Das Betriebssystem weiß nichts davon. ● Realisiert durch Bibliothek: User-Level Thread Package Vorteile: ● Extrem schneller Kontextwechsel: Nur wenige Prozessorregister sind auszutauschen. Ein Trap in den Kern entfällt. ● Jede Anwendung kann sich das passende Thread-Package wählen. Nachteile: ● Blockierung eines federgewichtigen Prozesses führt zur Blockierung des ganzen Programms. ● Kein Geschwindigkeitsvorteil durch Multi-Prozessoren. ● Kein zusätzlicher Rechenzeitanteil. ● ● ● Klausurvorbereitungsveranstaltung 12.07.2010 7 1 – Prozesse und Scheduling ● a) Prozessmodelle (J / N?) NJJ JJN NNJ Klausurvorbereitungsveranstaltung 12.07.2010 8 1 – Prozesse und Scheduling b) Scheduling-Verfahren ● Werden Prozesse mit langen CPU-Stößen begünstigt? ● X X X X X Klausurvorbereitungsveranstaltung 12.07.2010 9 1 – Prozesse und Scheduling c) Prozesserzeugung ● Wie viele Ws werden ausgegeben? ● int main(void) { int i; for (i = 0; i < 4; ++i) fork(); printf("W"); return 0; } Klausurvorbereitungsveranstaltung 12.07.2010 10 1 – Prozesse und Scheduling c) Prozesserzeugung ● Wie viele Ws werden ausgegeben? ● int main(void) { int i; fork(); fork(); fork(); fork(); printf("W"); return 0; } → 16! Klausurvorbereitungsveranstaltung 12.07.2010 11 1 – Prozesse und Scheduling d) Zombies ● Wie kann es zu diesem Zustand kommen? - Kindprozess terminiert (ruft exit() auf, oder wird gekillt) - Vaterprozess hat noch kein wait/waitpid aufgerufen, um den Prozesszustand abzufragen ● Ansammeln von Zombies Nachteil? Wie entfernen? - belegen weiterhin Systemressourcen (PID; Speicherplatz u.a. für Exitstatus) - Vater muss wait/waitpid aufrufen ● Prozesse, die zeitlich nach ihrem Vaterprozess terminieren? ● Klausurvorbereitungsveranstaltung 12.07.2010 12 Vorlesungsfolien: 3-Prozesse Diskussion: Verwaiste Prozesse (engl. „orphan processes“) Ein UNIX-Prozess wird zum Waisenkind, wenn sein Elternprozess terminiert. Was passiert mit der Prozesshierarchie? ● ● init (PID 1) init (PID 1) getty tty0 login bash exit! firefox firefox init (PID 1) adoptiert alle verwaisten Prozesse. init (PID 1) adoptiert alle verwaisten Prozesse. So bleibt die Prozesshierarchie intakt. So bleibt die Prozesshierarchie intakt. Klausurvorbereitungsveranstaltung 12.07.2010 13 2 – Synchronisation und Verklemmungen a) Verklemmungs-Arten ● Deadlock ↔ Livelock? ● Was ist das „geringere Übel“? ● Klausurvorbereitungsveranstaltung 12.07.2010 14 Vorlesungsfolien: 6-Verklemmungen Verklemmung von Prozessen 1. Variante: Deadlock ● Passives Warten ● Prozesszustand BLOCKED 2. Variante: Livelock ● Aktives Warten (busy waiting oder lazy waiting) ● Prozesszustand READY oder RUNNING, aber kein Fortschritt Deadlocks sind das vergleichsweise geringere Übel, da dieser Zustand eindeutig erkennbar ist und so die Basis zur „Auflösung“ gegeben ist. ● ● ● Klausurvorbereitungsveranstaltung 12.07.2010 15 2 – Synchronisation und Verklemmungen b) Vorbedingungen für Verklemmungen ● Nur, wenn die drei Vorbedingungen gelten, kann die vierte Bedingung (zirkuläres Warten) überhaupt eintreten! ● Wie lauten die Bedingungen? ● Klausurvorbereitungsveranstaltung 12.07.2010 16 Vorlesungsfolien: 6-Verklemmungen Bedingungen für eine Verklemmung Damit es zu einer Verklemmung kommen kann, müssen alle folgenden Bedingungen erfüllt sein: („notwendige Bedingungen“) 1. Exklusive Belegung von Betriebsmitteln („mutual exclusion“) ● die umstrittenen Betriebsmittel sind nur unteilbar nutzbar 2. Nachforderung von Betriebsmitteln („hold and wait“) ● die umstrittenen Betriebsmittel sind nur schrittweise belegbar 3. Kein Entzug von Betriebsmitteln („no preemption“) ● die umstrittenen Betriebsmittel sind nicht rückforderbar Erst wenn zur Laufzeit eine weitere Bedingung eintritt, liegt tatsächlich eine Verklemmung vor: 4. Zirkuläres Warten („circular wait“) ● Eine geschlossene Kette wechselseitig wartender Prozesse Klausurvorbereitungsveranstaltung 12.07.2010 17 2 – Synchronisation und Verklemmungen c) Provozierte Verklemmung ● zwei Systemressourcen, repräsentiert durch Semaphore x und y ● zwei Threads, die jeweils beide belegen und hinterher wieder freigeben sollen ● Zutaten: Semaphor-Operationen P und V; sleep() ● /* Ausschnitt aus Programm 1 */ /* Ausschnitt aus Programm 1 */ work_with_xy(); work_with_xy(); /* Ausschnitt aus Programm 2 */ /* Ausschnitt aus Programm 2 */ work_with_xy(); work_with_xy(); Klausurvorbereitungsveranstaltung 12.07.2010 18 Vorlesungsfolien: 5-Synchronisation E. Dijkstra: Semaphor (semaphore) Eine ”nicht-negative ganze Zahl“, ● für die zwei unteilbare Operationen definiert sind: P (hol. prolaag, „erniedrige“; auch down, wait) -1 hat der Semaphor den Wert 0, wird der laufende Prozess blockiert ● ansonsten wird der Semaphor um 1 dekrementiert ● Eine Betriebssystemabstraktion zum Austausch von Synchronisationssignalen zwischen nebenläufig arbeitenden Prozessen. ● V (hol. verhoog, „erhöhe“; auch up, signal) ● +1auf den Semaphor ggf. blockierter Prozess wird deblockiert ● ansonsten wird der Semaphor um 1 inkrementiert Klausurvorbereitungsveranstaltung 12.07.2010 19 2 – Synchronisation und Verklemmungen c) Provozierte Verklemmung ● zwei Systemressourcen, repräsentiert durch Semaphore x und y ● zwei Threads, die jeweils beide belegen und hinterher wieder freigeben sollen ● Zutaten: Semaphor-Operationen P und V; sleep() ● /* Ausschnitt aus Programm 1 */ /* Ausschnitt aus Programm 1 */ P(&x); P(&x); sleep(1); sleep(1); P(&y); P(&y); work_with_xy(); work_with_xy(); V(&x); V(&x); V(&y); V(&y); /* Ausschnitt aus Programm 2 */ /* Ausschnitt aus Programm 2 */ P(&y); P(&y); sleep(1); sleep(1); P(&x); P(&x); work_with_xy(); work_with_xy(); V(&x); V(&x); V(&y); V(&y); Klausurvorbereitungsveranstaltung 12.07.2010 20 3 – Speicherverwaltung ● a) Best Fit aaaaaa bbdd c Best Fit! aaddddbb keine sukzessive Halbierung (16 → 8 → 4 ...) wie beim Buddy-Verfahren! Klausurvorbereitungsveranstaltung 12.07.2010 21 3 – Speicherverwaltung aa bb kann nicht erfüllt werden – keine 7M am Stück verfügbar aaaa cc Klausurvorbereitungsveranstaltung 12.07.2010 22 3 – Speicherverwaltung b) Verschnitt ● externer / interner Verschnitt? ● jew. eine Beispiel-Speicherplatzierungsstrategie ● Klausurvorbereitungsveranstaltung 12.07.2010 23 Vorlesungsfolien: 8-Speicherverwaltung Diskussion: Verschnitt Externer Verschnitt ● Außerhalb der zugeteilten Speicherbereich entstehen Speicherfragmente, die nicht mehr genutzt werden können. ● Passiert bei den listenbasierten Strategien wie First Fit, Best Fit, ... 0 8 16 ● A B C D Speicher 3 2 Länge Klausurvorbereitungsveranstaltung 12.07.2010 24 Vorlesungsfolien: 8-Speicherverwaltung Diskussion: Verschnitt Interner Verschnitt ● Innerhalb der zugeteilten Speicherbereiche gibt es ungenutzten Speicher. ● Passiert z.B. bei Buddy, da die Anforderungen auf die nächstgrößere Zweierpotenz aufgerundet werden. ● 0 128 256 384 512 640 768 896 1024 1024 A 128 256 512 A B 64 256 512 A B 64 C 128 512 Anfrage 70 Anfrage 35 Anfrage 80 70 35 80 Klausurvorbereitungsveranstaltung 12.07.2010 25 4 – Systemsicherheit a) „Sicherheit“ ● Safety vs. Security? Safety ● Schutz von Menschen vor Fehlern, Störungen, Ausfällen, bei Katastrophen Security ● Schutz von Menschen und Rechnern vor intendierten Fehlern (Angriffen) ● ● ● Klausurvorbereitungsveranstaltung 12.07.2010 26 4 – Systemsicherheit b) Zugriffsrechte ● Zusatzinformation: Benutzer hsc ist in der Gruppe admins ● rwxrxr 1 root admins 11448 20100712 12:30 testdatei42 rwxrxr 1 root admins 11448 20100712 12:30 testdatei42 JNJ JJJ JNN Klausurvorbereitungsveranstaltung 12.07.2010 27 4 – Systemsicherheit c) Sicherheitsproblem ● Fachbegriff? ● Was genau passiert? ● int ask_passwd() { char buf[8]; printf("Passwort: "); if (strcmp("geheim", buf) == 0) return 1; printf("Falsches Passwort!\n"); return 0; } int main() { if (ask_passwd()) start_shell(); return 0; } gets(buf); Klausurvorbereitungsveranstaltung 12.07.2010 28 Übungsfolien: U6-Sicherheit Was ist passiert? ● ● ● ● int ask_passwd(void) { int ask_passwd(void) { char buf[8]; char buf[8]; ... gets(buf); ... printf("Passwort:"); printf("Passwort:"); gets(buf); ... Rücksprung- adresse alter Framepointer die Eingabe hat den b Framepointer und die a %ebp (Framepointer) f e d c Rücksprungadresse überschrieben ● Stack-LayoutkannaufeurerMaschineevtl. 9 8 7 buf[7] anders aussehen, Disassembler verwenden! Fachbegriff: „Pufferüberlauf“ (buffer overflow) Fachbegriff: „Pufferüberlauf“ (buffer overflow) → Sprung auf eine nicht ausführbare Adresse → Segmentation Fault Das ist noch der harmloseste Fall! 5 4 3 2 1 0 buf[5] %esp (Stackpointer) 6 buf[6] buf[4] buf[3] buf[2] buf[1] buf[0] Klausurvorbereitungsveranstaltung 12.07.2010 29 Auswertung Bitte schnell einmal die Punkte zusammenzählen ... Notenspiegel: Punkte Note 39,5–45 1 34–39 2 28,5–33,5 3 23–28 4 0–22,5 5 ● ● Klausurvorbereitungsveranstaltung 12.07.2010 30 Weitere Hinweise zur Vorbereitung Inhalt der Folien lernen ● Klassifizieren: Was muss ich lernen? Was muss ich begreifen? Übungsaufgaben verstehen, C und UNIX „können“ ● ASSESS-System bleibt mindestens bis zur Klausur offen - bei Fragen zur Korrektur melden ● Am besten die Aufgaben noch einmal lösen ● Optionale Zusatzaufgaben bearbeiten Beispielaufgaben lösen ● ältere (und diesjährige) Last Chance Tests, Probeklausuren Literatur zur Lehrveranstaltung durchlesen BS-Forum nutzen ● ● ● ● ● Klausurvorbereitungsveranstaltung 12.07.2010 31 Empfohlene Literatur [1] A. Silberschatz et al. Operating System Concepts. Wiley, 2004. ISBN 978-0471694663 [2] A. Tanenbaum: Modern Operating Systems (2nd ed.). Prentice Hall, 2001. ISBN 0-13-031358-0 [3] B. W. Kernighan, D. M. Ritchie. The C Programming Language. Prentice-Hall, 1988. ISBN 0-13-110362-8 (paperback) 0-13-110370-9 (hardback) [4] R. Stevens, Advanced Programming in the UNIX Environment, Addison-Wesley, 2005. ISBN 978-0201433074 Viel Erfolg bei der Klausur! Klausurvorbereitungsveranstaltung 12.07.2010 32 Betriebssysteme (BS) Probeklausur Olaf Spinczyk, Horst Schirmeier Arbeitsgruppe Eingebettete Systemsoftware Lehrstuhl für Informatik 12 TU Dortmund Vorname.Nachname@tu-dortmund.de http://ess.cs.uni-dortmund.de/ http://ess.cs.tu-dortmund.de/DE/Teaching/SS2011/BS/ 1 Ablauf Probeklausur (45 Minuten) Besprechung der Aufgaben Auswertung Weitere Hinweise zur Vorbereitung ● ● ● ● Klausurvorbereitungsveranstaltung 04.07.2011 2 Probeklausur ... in (fast) allen Belangen realistisch: Art der Aufgaben ● Auswahl aus dem gesamten Inhalt der Veranstaltung - Betriebssystemgrundlagen und UNIX-Systemprogrammierung in C - alle Vorlesungen und Übungen sind relevant Umfang ● kürzer als das „Original“: ca. 40–45 (statt 60) Minuten Durchführung ● keine Hilfsmittel erlaubt (keine Spickzettel, Bücher, ...) ● bitte still arbeiten ● jeder für sich Die Klausur wird nicht eingesammelt. Klausurvorbereitungsveranstaltung 04.07.2011 3 ● ● ● ● Besprechung der Aufgaben Vorstellung der Musterlösung Klärung von Fragen Wiederholung anhand der passenden Vorlesungsfolien Bewertung der eigenen Lösungen! ● ● ● ● Klausurvorbereitungsveranstaltung 04.07.2011 4 1 – Prozesse und Scheduling a) Definition von Prozess ● „Programm in Ausführung“ ● Oder: „Ein Prozess wird durch ein Programm kontrolliert und benötigt zur Ausführung dieses Programms einen Prozessor.“ ● Klausurvorbereitungsveranstaltung 04.07.2011 5 1 – Prozesse und Scheduling b) Unix-Prozesse X X ● X X ● ● ● „Ausgelagert“ gehört zum medium-term scheduling Swapper hat die Prozess-ID 0 und steht an der Wurzel Beim präemptieven Scheduling wird der Prozess dazu gedrängt, die CPU abzugeben Klausurvorbereitungsveranstaltung 04.07.2011 6 1 – Prozesse und Scheduling c) Prozesserzeugung ● Wie viele Gs werden ausgegeben? ● int main(void) { int p; fork(); fork(); printf("G\n"); fork(); printf("G\n"); return 0; } Klausurvorbereitungsveranstaltung 04.07.2011 7 1 – Prozesse und Scheduling c) Prozesserzeugung ● Wie viele Gs werden ausgegeben? ● int main(void) { int p; fork(); fork(); printf("G\n"); fork(); printf("G\n"); return 0; } G GGG GGGGGGGG → 4+8=12 Klausurvorbereitungsveranstaltung 04.07.2011 8 1 – Prozesse und Scheduling d) Scheduling ● Funktionsweise des Scheduling-Verfahrens „Shortest Process Next“ ● Wie kann das Betriebssystem den „Shortest Process“ ermitteln? ● Klausurvorbereitungsveranstaltung 04.07.2011 9 Vorlesungsfolien: 4 - Scheduling Shortest Process Next – SPN ● Grundlage dafür ist die Kenntnis über die Prozesslaufzeiten das Hauptproblem besteht in der Vorhersage der Laufzeiten ● Stapelbetrieb: Programmierer geben das erforderliche time limit* vor ● Dialogbetrieb: Mittelwert der früheren Stoßlängen des Prozesses Antwortzeiten werden wesentlich verkürzt und die Gesamtleistung steigt ● Dafür: Gefahr der Aushungerung CPU-lastiger Prozesse Die Zeitdauer, innerhalb der der Job (wahrscheinlich/hoffentlich) beendet wird, bevor er abgebrochen wird. ● ● ● * Verringert die bei FCFS auftretende Benachteiligung kurzer CPU-Stöße: „Die Kleinen nach vorne“ ● Verdrängung findet nicht statt Klausurvorbereitungsveranstaltung 04.07.2011 10 Vorlesungsfolien: 4 - Scheduling Diskussion: SPN - CPU-Stoßdauer 1n 1n−1 Sn1=n⋅∑Ti=n⋅Tn n ⋅Sn i=1 Problem dieser Berechnung ist die gleiche Gewichtung aller CPU-Stöße ● Jüngere CPU-Stöße sind jedoch von größerer Bedeutung als ältere und sollten daher auch mit größerer Gewichtung berücksichtigt werden Ursache ist das Lokalitätsprinzip ● ● ● Basis für die Schätzung ist die Mittelwertbildung über alle bisherigen CPU-Stoßlängen eines Prozesses: Klausurvorbereitungsveranstaltung 04.07.2011 11 2 – Synchronisation und Verklemmungen a) Synchronisation X X X ● X X X ● ● ● Semaphoren, basieren auf dem Prinzip des passivem Wartens Der Bäckerei-Algorithmus kann nicht garantieren, dass eine Wartenummer nur an einen Prozess vergeben wird Unterbrechungsanforderungen gehören zu den konsumierbaren Betriebsmitteln Klausurvorbereitungsveranstaltung 04.07.2011 12 2 – Synchronisation und Verklemmungen b) Das Erzeuger-Verbraucher-Problem: sem count = 0 und sem access = 1. Wenn die beiden p-Operationen im Verbraucher-Prozess vertauscht werden? ● /* Erzeuger-Prozess */ /* Erzeuger-Prozess */ repeat repeat Erzeuge Element; Erzeuge Element; p(access); p(access); Schreibe das Element in den Puffer; Schreibe das Element in den Puffer; v(access); v(access); v(count); v(count); until false until false /* Verbraucher-Prozess */ /* Verbraucher-Prozess */ repeat repeat p(count); p(count); p(access); p(access); Lese das Element aus dem Puffer; Lese das Element aus dem Puffer; v(access); v(access); Verbrauche Element; Verbrauche Element; until false; until false; Klausurvorbereitungsveranstaltung 04.07.2011 13 2 – Synchronisation und Verklemmungen b) Wenn die beiden p-Operationen im Verbraucher- Prozess vertauscht werden? Es kann ein Deadlock entstehen: Wenn keine Elemente im Puffer vorhanden sind (count = 0) und der Verbraucher- Prozess führt p(access) und p(count) aus, stellt er sich in die Warteschlange vor dem Semaphor count ein. Somit kann access nie wieder freigegeben werden. Erzeuger- Prozess kann ein Element nicht in den Puffer schreiben und wartet unendlich lange auf access → Deadlock ● ● /* Erzeuger-Prozess */ /* Erzeuger-Prozess */ /* Verbraucher-Prozess */ /* Verbraucher-Prozess */ repeat repeat repeat repeat Erzeuge Element; p(access); p(access); Erzeuge Element; p(access); p(access); p(count); p(count); Schreibe das Element in den Puffer; Schreibe das Element in den Puffer; Lese das Element aus dem Puffer; v(access); v(access); v(count); v(count); Lese das Element aus dem Puffer; until false Verbrauche Element; until false until false; v(access); v(access); Verbrauche Element; until false; Klausurvorbereitungsveranstaltung 04.07.2011 14 2 – Synchronisation und Verklemmungen b) Das Erzeuger-Verbraucher-Problem: sem count = 0 und sem access = 1. Wenn die beiden v-Operationen im Erzeuger-Prozess vertauscht werden? ● /* Erzeuger-Prozess */ /* Erzeuger-Prozess */ repeat repeat Erzeuge Element; Erzeuge Element; p(access); p(access); Schreibe das Element in den Puffer; Schreibe das Element in den Puffer; v(access); v(access); v(count); v(count); until false until false /* Verbraucher-Prozess */ /* Verbraucher-Prozess */ repeat repeat p(count); p(count); p(access); p(access); Lese das Element aus dem Puffer; Lese das Element aus dem Puffer; v(access); v(access); Verbrauche Element; Verbrauche Element; until false; until false; Klausurvorbereitungsveranstaltung 04.07.2011 15 2 – Synchronisation und Verklemmungen b) Das Erzeuger-Verbraucher-Problem: sem count = 0 und sem access = 1. Wenn die beiden v-Operationen im Erzeuger-Prozess vertauscht werden? Beeinflusst nicht die Korrektheit des Programms, denn der Verbraucher-Prozess kann auf den Puffer nur zugreifen, wenn Elemente im Puffer vorhanden sind und der Erzeuger Prozess schon den access freigegeben hat. ● ● /* Erzeuger-Prozess */ /* Erzeuger-Prozess */ repeat repeat Erzeuge Element; Erzeuge Element; p(access); p(access); Schreibe das Element in den Puffer; Schreibe das Element in den Puffer; v(count); v(count); v(access); v(access); until false until false Klausurvorbereitungsver /* Verbraucher-Prozess */ /* Verbraucher-Prozess */ repeat repeat p(count); p(count); p(access); p(access); Lese das Element aus dem Puffer; Lese das Element aus dem Puffer; v(access); v(access); Verbrauche Element; Verbrauche Element; until false; until false; anstaltung 04.07.2011 16 2 – Synchronisation und Verklemmungen c) Das Erzeuger-Verbraucher-Problem: Kapazität des Puffers n, Semaphoren full = 0, empty = n, access = 1. ● /*Erzeuger-Prozess */ /*Erzeuger-Prozess */ repeat repeat Erzeuge Element; Erzeuge Element; p(empty); p(empty); p(access); p(access); Schreibe das Element in den Puffer; Schreibe das Element in den Puffer; v(access); v(access); v(full); v(full); until false until false /* Verbraucher-Prozess */ /* Verbraucher-Prozess */ repeat repeat p(full); p(full); p(access); p(access); Lese das Element aus dem Puffer; Lese das Element aus dem Puffer; v(access); v(access); v(empty); v(empty); Verbrauche Element; Verbrauche Element; until false until false Klausurvorbereitungsveranstaltung 04.07.2011 17 2 – Synchronisation und Verklemmungen d) Ein Verfahren zur Verklemmungsauflösung Prozesse abbrechen und dadurch Betriebsmittel frei bekommen ● Verklemmte Prozesse schrittweise abbrechen (großer Aufwand) - Mit dem „effektivsten Opfer“ (?) beginnen ● Alle verklemmten Prozesse terminieren (großer Schaden) Betriebsmittel entziehen und mit dem „effektivsten Opfer“ (?) beginnen ● Der betreffende Prozess ist zurückzufahren bzw. wieder aufzusetzen - Transaktionen, checkpointing/recovery (großer Aufwand) ● Ein Aushungern der zurückgefahrenen Prozesse ist zu vermeiden ● ● ● Klausurvorbereitungsveranstaltung 04.07.2011 18 3 – Speicherverwaltung ● a) Worst Fit a a a a a a d d b b c c Worst Fit! cccc aa b keine sukzessive Halbierung (16 → 8 → 4 ...) wie beim Buddy-Verfahren! Klausurvorbereitungsveranstaltung 04.07.2011 19 3 – Speicherverwaltung aa bb kann nicht erfüllt werden – keine 7M am Stück verfügbar aaaa cc Klausurvorbereitungsveranstaltung 04.07.2011 20 3 – Speicherverwaltung b) Adressbildung ● Klausurvorbereitungsveranstaltung 04.07.2011 21 Vorlesungsfolien: 8-Speicherverwaltung Seitenadressierung (paging) Einteilung des logischen Adressraums in gleichgroße Seiten, die an beliebigen Stellen im physikalischen Adressraum liegen können ● Lösung des Fragmentierungsproblems ● keine Kompaktifizierung mehr nötig ● Vereinfacht Speicherbelegung und Ein-/Auslagerungen ● logischer Adressraum physikalischer Adressraum ROM RAM Seiten (pages) Kacheln (frames) 22 Klausurvorbereitungsveranstaltung 04.07.2011 Vorlesungsfolien: 8-Speicherverwaltung MMU mit Seiten-Kacheltabelle Tabelle setzt Seiten in Kacheln um SKT Basisregister ● + logische Adresse 00002 12a Seiten-Kacheltabelle Startadr. 00000 00001 00002 00003 00004 ffe0 fxxx ... physikalische Adresse ffe0f 12a Klausurvorbereitungsveranstaltung 04.07.2011 23 3 – Speicherverwaltung b) Adressbildung ● 1000 XOR AB1 1AB1 0000 XOR 1B0 01B0 Klausurvorbereitungsveranstaltung 04.07.2011 24 4 – Systemsicherheit a) „Sicherheit“ ● Safety vs. Security? Safety ● Schutz von Menschen vor Fehlern, Störungen, Ausfällen, bei Katastrophen Security ● Schutz von Menschen und Rechnern vor intendierten Fehlern (Angriffen) ● ● ● Klausurvorbereitungsveranstaltung 04.07.2011 25 4 – Systemsicherheit b) Pufferspeicher X X X X ● ● ● ● Kandidaten für Freiliste werden nach LRU Verfahren bestimmt Beim lazy write wird der Block nicht sofort auf die Platte geschrieben Read ahead stößt beim squentiellen Lesen auch den Transfer des Folgeblocks an Klausurvorbereitungsveranstaltung 04.07.2011 26 4 – Systemsicherheit c) Geräteklassen Zeichenorientiert ● Meist rein sequentieller Zugriff, selten wahlfrei; z.B. Tastatur, Drucker Blockorientiert ● Meist wahlfreier Zugriff; z.B. Festplatte, CD-ROM ● ● ● Klausurvorbereitungsveranstaltung 04.07.2011 27 Auswertung Bitte schnell einmal die Punkte zusammenzählen ... Notenspiegel: Punkte Note 38,5–44 1 33,5–38 2 28–33 3 22,5–27,5 4 0–22 5 ● ● Klausurvorbereitungsveranstaltung 04.07.2011 28 Weitere Hinweise zur Vorbereitung Inhalt der Folien lernen ● Klassifizieren: Was muss ich lernen? Was muss ich begreifen? Übungsaufgaben verstehen, C und UNIX „können“ ● ASSESS-System bleibt mindestens bis zur Klausur offen - bei Fragen zur Korrektur melden ● Am besten die Aufgaben noch einmal lösen ● Optionale Zusatzaufgaben bearbeiten Beispielaufgaben lösen ● ältere (und diesjährige) Last Chance Tests, Probeklausuren Literatur zur Lehrveranstaltung durchlesen BS-Forum nutzen ● ● ● ● ● Klausurvorbereitungsveranstaltung 04.07.2011 29 Empfohlene Literatur [1] A. Silberschatz et al. Operating System Concepts. Wiley, 2004. ISBN 978-0471694663 [2] A. Tanenbaum: Modern Operating Systems (2nd ed.). Prentice Hall, 2001. ISBN 0-13-031358-0 [3] B. W. Kernighan, D. M. Ritchie. The C Programming Language. Prentice-Hall, 1988. ISBN 0-13-110362-8 (paperback) 0-13-110370-9 (hardback) [4] R. Stevens, Advanced Programming in the UNIX Environment, Addison-Wesley, 2005. ISBN 978-0201433074 Viel Erfolg bei der Klausur! Klausurvorbereitungsveranstaltung 04.07.2011 30 Betriebssysteme (BS) Probeklausur Olaf Spinczyk, Daniel Cordes und Matthias Meier Arbeitsgruppe Eingebettete Systemsoftware Lehrstuhl für Informatik 12 TU Dortmund http://ess.cs.uni-dortmund.de/ http://ess.cs.tu-dortmund.de/DE/Teaching/SS2012/BS/ 1 Ablauf Probeklausur (45 Minuten) Besprechung der Aufgaben Auswertung Weitere Hinweise zur Vorbereitung ● ● ● ● Klausurvorbereitungsveranstaltung 02.07.2012 2 Probeklausur ... in (fast) allen Belangen realistisch: Art der Aufgaben ● Auswahl aus dem gesamten Inhalt der Veranstaltung - Betriebssystemgrundlagen und UNIX-Systemprogrammierung in C - alle Vorlesungen und Übungen sind relevant Umfang ● kürzer als das „Original“: ca. 40–45 (statt 60) Minuten Durchführung ● keine Hilfsmittel erlaubt (keine Spickzettel, Bücher, ...) ● bitte still arbeiten ● jeder für sich Die Klausur wird nicht eingesammelt. Klausurvorbereitungsveranstaltung 02.07.2012 3 ● ● ● ● 1 – Prozesse und Scheduling a) Definition von Prozess ● „Programm in Ausführung“ ● Oder: „Ein Prozess wird durch ein Programm kontrolliert und benötigt zur Ausführung dieses Programms einen Prozessor.“ ● Klausurvorbereitungsveranstaltung 02.07.2012 4 1 – Prozesse und Scheduling b) Prozesserzeugung ● Wie viele Gs werden ausgegeben? ● int main (void) { char c; printf("G\n"); fork(); printf("G\n"); fork(); fork(); printf("G\n"); return 0; } Klausurvorbereitungsveranstaltung 02.07.2012 5 1 – Prozesse und Scheduling b) Prozesserzeugung ● Wie viele Gs werden ausgegeben? ● int main (void) { char c; printf("G\n"); fork(); printf("G\n"); fork(); fork(); printf("G\n"); return 0; } G G G G GGGGGGGG → 1+2+8=11 Klausurvorbereitungsveranstaltung 02.07.2012 6 1 – Prozesse und Scheduling c) Scheduling X X X X X jeder Prozess bekommt eine Zeitscheibe von X Zeiteinh. beim präemptiven Scheduling wird der Prozess dazu gedrängt, die CPU abzugeben Prozesse mit langen CPU-Stößen werden begünstigt ● Konvoi-Effekt Klausurvorbereitungsveranstaltung 02.07.2012 7 ● ● ● ● 1 – Prozesse und Scheduling d) Scheduling ● Unterschied zwischen „Round Robin“ und „Virtual Round Robin“ ● Welche Vor- und Nachteile ergeben sich durch den Einsatz von VRR? ● Klausurvorbereitungsveranstaltung 02.07.2012 8 1 – Prozesse und Scheduling ● Round Robin ● Prozesse, die die CPU vor Ende ihrer Zeitscheibe freiwillig abgeben, werden benachteiligt ● Virtual Round Robin ● Prozesse, die die CPU vor Ende ihrer Zeitscheibe freiwillig abgeben, kommen, auf eine Vorzugsliste ● Das nächste Zeitquantum wird auf die nicht ausgeschöpfte Zeit gesetzt Klausurvorbereitungsveranstaltung 02.07.2012 9 1 – Prozesse und Scheduling ● Round Robin ● Prozesse, die die CPU vor Ende ihrer Zeitscheibe freiwillig abgeben, werden benachteiligt ● Virtual Round Robin ● Prozesse, die die CPU vor Ende ihrer Zeitscheibe freiwillig abgeben, kommen, auf eine Vorzugsliste ● Das nächste Zeitquantum wird auf die nicht ausgeschöpfte Zeit gesetzt E/A-lastige Prozesse werden nicht benachteiligt → Fairness Durch die im Durchschnitt kürzeren Zeitscheiben erhöht sich sie Zahl der Kontextwechsel Jeder einzelne Kontextwechsel ist etwas teurer, da immer zwei Queues inspiziert werden müssen Klausurvorbereitungsveranstaltung 02.07.2012 10 2 – Synchronisation und Verklemmungen a) Synchronisation und Verklemmung X X X X X X bei der Verwendung von Semaphoren können Verklemmungen entstehen Unterbrechungsanforderungen gehören zu den konsumierbaren Betriebsmitteln Prozesse befinden sich im Zustand blocked (pass. Warten) hat der Semaphor den Wert 0, wird der laufende Prozess blockiert (sonst wird der Semaphor um 1 dekrementiert) ● ● ● ● ● Klausurvorbereitungsveranstaltung 02.07.2012 11 2 – Synchronisation und Verklemmungen b) Implementierung einer Schlossvariable ● Warum ist dieses naive Verfahren zur Synchronisierung von Prozessen (bei präemptivem Scheduling) nicht geeignet? ● Welche gängige Betriebssystem-Abtraktion sollte man stattdessen verwenden? abstrakter Datentyp Lock Verzögert einen Prozess bis das „Schloss“ offen ist öffnet das Schloss, ohne den auf- rufenden Prozess zu verzögern ● /* Schlossvariable (Initialwert 0) */ typedef unsigned char Lock; /* Kritischen Abschnitt betreten */ void acquire (Lock *lock) { while (*lock); *lock = 1; } /* Kritischen Abschnitt wieder verlassen */ void release (Lock *lock) { *lock = 0; } Klausurvorbereitungsveranstaltung 02.07.2012 12 2 – Synchronisation und Verklemmungen b) Implementierung einer Schlossvariable ● Warum ist dieses naive Verfahren zur Synchronisierung von Prozessen (bei präemptivem Scheduling) nicht geeignet? - acquire() soll einen kritischen Abschnitt schützen, ist dabei aber selbst kritisch! - Zusätzlich wird CPU-Zeit verschwendet (aktives Warten) ● Welche gängige Betriebssystem-Abtraktion sollte man stattdessen verwenden? - Semaphore Gefahr bei Kontextwechsel! ● ... /* Kritischen Abschnitt betreten */ void acquire (Lock *lock) { while (*lock); *lock = 1; } ... Klausurvorbereitungsveranstaltung 02.07.2012 13 2 – Synchronisation und Verklemmungen c) Verklemmungs-Arten ● Deadlock ↔ Livelock? ● Was ist das „geringere Übel“? ● Klausurvorbereitungsveranstaltung 02.07.2012 14 Vorlesungsfolien: 06-Verklemmungen Verklemmung von Prozessen 1. Variante: Deadlock ● Passives Warten ● Prozesszustand BLOCKED 2. Variante: Livelock ● Aktives Warten (busy waiting oder „lazy“ busy waiting) ● Prozesszustand beliebig (auch RUNNING), aber kein Fortschritt Deadlocks sind das vergleichsweise geringere Übel, da dieser Zustand eindeutig erkennbar ist und so die Basis zur „Auflösung“ gegeben ist. ● ● ● Klausurvorbereitungsveranstaltung 02.07.2012 15 2 – Synchronisation und Verklemmungen d) Verfahren zur Auflösung von Verklemmungen Prozesse abbrechen und dadurch Betriebsmittel frei bekommen ● Verklemmte Prozesse schrittweise abbrechen (großer Aufwand) - Mit dem „effektivsten Opfer“ (?) beginnen ● Alle verklemmten Prozesse terminieren (großer Schaden) Betriebsmittel entziehen und mit dem „effektivsten Opfer“ (?) beginnen ● Der betreffende Prozess ist zurückzufahren bzw. wieder aufzusetzen - Transaktionen, checkpointing/recovery (großer Aufwand) ● Ein Aushungern der zurückgefahrenen Prozesse ist zu vermeiden ● ● ● Klausurvorbereitungsveranstaltung 02.07.2012 16 3 – Speicherverwaltung a) Buddy-Verfahren ● Buddy-Verfahren: auf nächste 2er-Potenz aufrunden! kann nicht erfüllt werden – keine 8 MiB am Stück verfügbar Klausurvorbereitungsveranstaltung 02.07.2012 17 3 – Speicherverwaltung a) Buddy-Verfahren ● Gebe den Speicherbereich frei und betrachte den angrenzenden Buddy - ist dieser ebenfalls nicht belegt, so fasse diese beiden zusammen - wiederhole die Zusammenfassung von Buddies, bis ein Speicherbereich belegt oder der ganze Speicher freigeben ist ● Klausurvorbereitungsveranstaltung 02.07.2012 18 3 – Speicherverwaltung b) Adressabbildung ● Klausurvorbereitungsveranstaltung 02.07.2012 19 Vorlesungsfolien: 08-Speicherverwaltung Seitenadressierung (paging) Einteilung des logischen Adressraums in gleichgroße Seiten, die an beliebigen Stellen im physikalischen Adressraum liegen können ● Lösung des Fragmentierungsproblems ● keine Kompaktifizierung mehr nötig ● Vereinfacht Speicherbelegung und Ein-/Auslagerungen ● logischer Adressraum physikalischer Adressraum ROM RAM Seiten (pages) Kacheln (frames) 20 Klausurvorbereitungsveranstaltung 02.07.2012 Vorlesungsfolien: 08-Speicherverwaltung MMU mit Seiten-Kacheltabelle Tabelle setzt Seiten in Kacheln um SKT Basisregister + Seiten-Kacheltabelle Startadr. 00000 00001 00002 00003 00004 logische Adresse ● 00002 12a ffe0 fxxx ... physikalische Adresse ffe0f 12a Klausurvorbereitungsveranstaltung 02.07.2012 21 3 – Speicherverwaltung b) Adressabbildung ● 2000 OR AF4 2AF4 5000 OR 8C8 58C8 Klausurvorbereitungsveranstaltung 02.07.2012 22 4 – Systemsicherheit a) Sicherheit ● Safety vs. Security? ● Safety - Schutz vor Risiken durch (Software-)Fehler, Störungen oder Ausfälle ● Security - Schutz von Menschen und Rechnern vor intendierten Fehlern (Angriffen) ● Klausurvorbereitungsveranstaltung 02.07.2012 23 4 – Systemsicherheit b) Hardware-Mechanismen X X X X X alle User-Programme (auch vom Superuser 'root') laufen in Ring 3 es sind viele implizite Speicherzugriffe auf Tabelle nötig → verschlechtert Performance (deshalb TLB) im Gegenteil, Prozesse können über gemeinsame Datensegmente kommunizieren ● ● ● ● Klausurvorbereitungsveranstaltung 02.07.2012 24 4 – Systemsicherheit c) Welches Sicherheitsproblem hat der folgende Ausschnitt eines C-Programms? ● int ask_passwd() { char buf[8]; printf("Passwort: "); if (strcmp("geheim", buf) == 0) return 1; printf("Falsches Passwort!\n"); return 0; } int main() { if (ask_passwd()) start_shell(); return 0; } gets(buf); Klausurvorbereitungsveranstaltung 02.07.2012 25 4 – Systemsicherheit c) Welches Sicherheitsproblem hat der folgende Ausschnitt eines C-Programms? ● Fachbegriff: - Buffer Overflow ● Was passiert dabei? - gets() prüft nicht, die Größe des Zielpuffers → Daten an höheren Speicheradressen können überschrieben werden ● Wie könnte dieses Sicherheitsproblem von Angreifern ausgenutzt werden? - Rücksprungadresse könnte überschrieben werden - Angreifer könnte Shellcode einschleusen und ausführen ● Klausurvorbereitungsveranstaltung 02.07.2012 26 Auswertung Bitte schnell einmal die Punkte zusammenzählen ... Notenspiegel: Punkte Note 38,5–45 1 33,5–38 2 28–33 3 22,5–27,5 4 0–22 5 ● ● Klausurvorbereitungsveranstaltung 02.07.2012 27 Weitere Hinweise zur Vorbereitung Inhalt der Folien lernen ● Klassifizieren: Was muss ich lernen? Was muss ich begreifen? Übungsaufgaben verstehen, C und UNIX „können“ ● ASSESS-System bleibt mindestens bis zur Klausur offen - bei Fragen zur Korrektur melden ● Am besten die Aufgaben noch einmal lösen ● Optionale Zusatzaufgaben bearbeiten Beispielaufgaben lösen ● ältere (und diesjährige) Last Chance Tests, Probeklausuren Literatur zur Lehrveranstaltung durchlesen BS-Forum nutzen ● ● ● ● ● Klausurvorbereitungsveranstaltung 02.07.2012 28 Empfohlene Literatur [1] A. Silberschatz et al. Operating System Concepts. Wiley, 2004. ISBN 978-0471694663 [2] A. Tanenbaum: Modern Operating Systems (2nd ed.). Prentice Hall, 2001. ISBN 0-13-031358-0 [3] B. W. Kernighan, D. M. Ritchie. The C Programming Language. Prentice-Hall, 1988. ISBN 0-13-110362-8 (paperback) 0-13-110370-9 (hardback) [4] R. Stevens, Advanced Programming in the UNIX Environment, Addison-Wesley, 2005. ISBN 978-0201433074 Viel Erfolg bei der Klausur! Klausurvorbereitungsveranstaltung 02.07.2012 29 Betriebssysteme (BS) Probeklausur Olaf Spinczyk und Matthias Meier Arbeitsgruppe Eingebettete Systemsoftware Lehrstuhl für Informatik 12 TU Dortmund http://ess.cs.uni-dortmund.de/ http://ess.cs.tu-dortmund.de/DE/Teaching/SS2013/BS/ 1 Ablauf Probeklausur (45 Minuten) Besprechung der Aufgaben Auswertung Weitere Hinweise zur Vorbereitung ● ● ● ● Klausurvorbereitungsveranstaltung 08.07.2013 2 Probeklausur ... in (fast) allen Belangen realistisch: Art der Aufgaben ● Auswahl aus dem gesamten Inhalt der Veranstaltung - Betriebssystemgrundlagen und UNIX-Systemprogrammierung in C - alle Vorlesungen und Übungen sind relevant Umfang ● kürzer als das „Original“: ca. 40–45 (statt 60) Minuten Durchführung ● keine Hilfsmittel erlaubt (keine Spickzettel, Bücher, ...) ● bitte still arbeiten ● jeder für sich Die Klausur wird nicht eingesammelt. Klausurvorbereitungsveranstaltung 08.07.2013 3 ● ● ● ● 1 – Prozesse und Scheduling a) Prozesserzeugung ● Wie viele Gs werden ausgegeben? ● int main (void) { int i; printf("G\n"); fork(); for (i = 0; i < 2; i++) { if ((i % 2) == 0) printf("G\n"); fork(); } printf("G\n"); return 0; } Klausurvorbereitungsveranstaltung 08.07.2013 4 1 – Prozesse und Scheduling a) Prozesserzeugung ● Wie viele Gs werden ausgegeben? G GG ● int main (void) { int i; printf("G\n"); fork(); for (i = 0; i < 2; i++) { if ((i % 2) == 0) printf("G\n"); fork(); } printf("G\n"); return 0; } GG GGGGGG → 1+2+8=11 Klausurvorbereitungsveranstaltung 08.07.2013 5 1 – Prozesse und Scheduling b) Medium-term Scheduling ● Der Prozess ist komplett ausgelagert, d. h. der Inhalt seines gesamten Adressraums wurde in den Hintergrundspeicher verschoben (swap-out). ● Der von dem Prozess belegte Vordergrund- speicher wurde freigegeben. ● Klausurvorbereitungsveranstaltung 08.07.2013 6 1 – Prozesse und Scheduling c) Scheduling X X VRR ist präemptiv → der Prozess wird dazu gedrängt, die CPU abzugeben Im Gegenteil, bei SRTF können Prozesse mit einer langen CPU-Stoß Dauer verhungern Prozesse mit langen CPU-Stößen werden begünstigt ● Konvoi-Effekt ● ● ● ● X X Klausurvorbereitungsveranstaltung 08.07.2013 7 1 – Prozesse und Scheduling d) Scheduling ● Unterschied zwischen „Round Robin“ und „Virtual Round Robin“ ● Welche Vor- und Nachteile ergeben sich durch den Einsatz von VRR? ● Klausurvorbereitungsveranstaltung 08.07.2013 8 1 – Prozesse und Scheduling ● Round Robin ● Prozesse, die die CPU vor Ende ihrer Zeitscheibe freiwillig abgeben, werden benachteiligt ● Virtual Round Robin ● Prozesse, die die CPU vor Ende ihrer Zeitscheibe freiwillig abgeben, kommen, auf eine Vorzugsliste ● Das nächste Zeitquantum wird auf die nicht ausgeschöpfte Zeit gesetzt Klausurvorbereitungsveranstaltung 08.07.2013 9 1 – Prozesse und Scheduling ● Round Robin ● Prozesse, die die CPU vor Ende ihrer Zeitscheibe freiwillig abgeben, werden benachteiligt ● Virtual Round Robin ● Prozesse, die die CPU vor Ende ihrer Zeitscheibe freiwillig abgeben, kommen, auf eine Vorzugsliste ● Das nächste Zeitquantum wird auf die nicht ausgeschöpfte Zeit gesetzt E/A-lastige Prozesse werden nicht benachteiligt → Fairness Durch die im Durchschnitt kürzeren Zeitscheiben erhöht sich sie Zahl der Kontextwechsel Jeder einzelne Kontextwechsel ist etwas teurer, da immer zwei Queues inspiziert werden müssen Klausurvorbereitungsveranstaltung 08.07.2013 10 2 – Synchronisation und Verklemmungen a) Synchronisation und Verklemmung X X X X X Signale gehören zu den konsumierbaren Betriebsmitteln Semaphore realisieren passives Warten (Zstd.: BLOCKED) Operation V → freigeben, hier wird nicht blockiert Prozesszustand ist beliebig (auch RUNNING), aber kein Fortschritt ● ● ● ● ● Klausurvorbereitungsveranstaltung 08.07.2013 11 2 – Synchronisation und Verklemmungen b) Provozierte Verklemmung ● Durch das Einfügen von Semaphor-Operationen soll dafür gesorgt werden, dass beim Belegen der Ressourcen eine Verklemmung möglich ist. ● p(&x); p(&y); v(&x); v(&y); p(&y); p(&x); v(&x); v(&y); Klausurvorbereitungsveranstaltung 08.07.2013 12 2 – Synchronisation und Verklemmungen b) Provozierte Verklemmung ● Durch das Einfügen von Semaphor-Operationen soll dafür gesorgt werden, dass beim Belegen der Ressourcen eine Verklemmung möglich ist. ● Wahrscheinlichkeit für Verklemmung mit sleep(1); erhöhen ● p(&x); sleep(1); p(&y); v(&x); v(&y); p(&y); sleep(1); p(&x); v(&x); v(&y); Klausurvorbereitungsveranstaltung 08.07.2013 13 2 – Synchronisation und Verklemmungen c) Verklemmungs-Arten ● Deadlock ↔ Livelock? ● Was ist das „geringere Übel“? ● Klausurvorbereitungsveranstaltung 08.07.2013 14 Vorlesungsfolien: 06-Verklemmungen Verklemmung von Prozessen 1. Variante: Deadlock ● Passives Warten ● Prozesszustand BLOCKED 2. Variante: Livelock ● Aktives Warten (busy waiting oder „lazy“ busy waiting) ● Prozesszustand beliebig (auch RUNNING), aber kein Fortschritt Deadlocks sind das vergleichsweise geringere Übel, da dieser Zustand eindeutig erkennbar ist und so die Basis zur „Auflösung“ gegeben ist. ● ● ● Klausurvorbereitungsveranstaltung 08.07.2013 15 3 – Speicherverwaltung a) Buddy-Verfahren ● CC Buddy-Verfahren: auf nächste 2er-Potenz aufrunden! DDDDDDDD Klausurvorbereitungsveranstaltung 08.07.2013 16 3 – Speicherverwaltung a) Buddy-Verfahren ● kann nicht erfüllt werden – keine 16 MiB am Stück verfügbar FFFF Klausurvorbereitungsveranstaltung 08.07.2013 17 3 – Speicherverwaltung b) Segmentierung X X X X X im Gegenteil, Segmente werden verschoben, um Lücken zu schließen → weniger aber größere Lücken entstehen im Gegenteil, Prozesse können über gemeinsame Datensegmente kommunizieren ● ● ● Klausurvorbereitungsveranstaltung 08.07.2013 18 3 – Speicherverwaltung c) Ersetzungsstrategien ● System mit Seitenadressierung und der Ersetzungsstrategie FIFO ● Referenzfolge: 2, 1, 5, 1, 3, 2, 4, 1, 5, 4, 3 ● drei Hauptspeicherkacheln für diesen Prozess 222 11 5 ● Klausurvorbereitungsveranstaltung 08.07.2013 19 3 – Speicherverwaltung c) Ersetzungsstrategien ● System mit Seitenadressierung und der Ersetzungsstrategie FIFO ● Referenzfolge: 2, 1, 5, 1, 3, 2, 4, 1, 5, 4, 3 ● drei Hauptspeicherkacheln für diesen Prozess bereits eingelagert! 2222 111 55 ● Klausurvorbereitungsveranstaltung 08.07.2013 20 3 – Speicherverwaltung c) Ersetzungsstrategien ● System mit Seitenadressierung und der Ersetzungsstrategie FIFO ● Referenzfolge: 2, 1, 5, 1, 3, 2, 4, 1, 5, 4, 3 ● drei Hauptspeicherkacheln für diesen Prozess ● 22223 1111 555 FIFO → Seite 2 wird ersetzt Klausurvorbereitungsveranstaltung 08.07.2013 21 3 – Speicherverwaltung c) Ersetzungsstrategien ● System mit Seitenadressierung und der Ersetzungsstrategie FIFO ● Referenzfolge: 2, 1, 5, 1, 3, 2, 4, 1, 5, 4, 3 ● drei Hauptspeicherkacheln für diesen Prozess 2222333 111122 55554 ● Klausurvorbereitungsveranstaltung 08.07.2013 22 3 – Speicherverwaltung c) Ersetzungsstrategien ● System mit Seitenadressierung und der Ersetzungsstrategie FIFO ● Referenzfolge: 2, 1, 5, 1, 3, 2, 4, 1, 5, 4, 3 ● drei Hauptspeicherkacheln für diesen Prozess ● 2222333111 111122255 55554444 bereits eingelagert! Klausurvorbereitungsveranstaltung 08.07.2013 23 3 – Speicherverwaltung c) Ersetzungsstrategien ● System mit Seitenadressierung und der Ersetzungsstrategie FIFO ● Referenzfolge: 2, 1, 5, 1, 3, 2, 4, 1, 5, 4, 3 ● drei Hauptspeicherkacheln für diesen Prozess 22223331111 1111222555 555544443 ● Klausurvorbereitungsveranstaltung 08.07.2013 24 3 – Speicherverwaltung d) Translation Look-Aside Buffer (TLB) ● schneller Registersatz, der vor dem Zugriff auf die SKT konsultiert wird ● Klausurvorbereitungsveranstaltung 08.07.2013 25 4 – Ein-/Ausgabe und Dateisysteme ● a) E/A-Scheduling ● Shortest Seek Time First: - Auftrag mit der kürzesten Positionierzeit wird vorgezogen ● Elevator: - Plattenarm bewegt sich in eine Richtung bis keine Aufträge mehr vorhanden sind ● Problem bei SSTF im Gegensatz zu Elevator? - eine Anfrage könnte „nie“ beantwortet werden, falls immer eine Anfrage eintrifft, bei der die Positionierzeit kürzer ist → Aushungerung Klausurvorbereitungsveranstaltung 08.07.2013 26 4 – Ein-/Ausgabe und Dateisysteme a) E/A-Scheduling ● Beispiel für SSTF – Referenzfolge: 2 3 4 10 1 2 3 4 5 6 7 8 9 10 ● Klausurvorbereitungsveranstaltung 08.07.2013 27 4 – Ein-/Ausgabe und Dateisysteme a) E/A-Scheduling ● Beispiel für SSTF – Referenzfolge: 10 123456789 ● neue Anfragen: 10 123 Klausurvorbereitungsveranstaltung 08.07.2013 28 4 – Ein-/Ausgabe und Dateisysteme a) E/A-Scheduling ● Beispiel für SSTF – Referenzfolge: 3 2 1 10 1 2 3 4 5 6 7 8 9 10 ● Klausurvorbereitungsveranstaltung 08.07.2013 29 4 – Ein-/Ausgabe und Dateisysteme a) E/A-Scheduling ● Beispiel für SSTF – Referenzfolge: 10 123456789 ● neue Anfragen: 10 234 Klausurvorbereitungsveranstaltung 08.07.2013 30 4 – Ein-/Ausgabe und Dateisysteme a) E/A-Scheduling ● Beispiel für SSTF – Referenzfolge: 10 123456789 ● neue Anfragen: 10 123 hier würde das Aushungern auftreten! Klausurvorbereitungsveranstaltung 08.07.2013 31 4 – Ein-/Ausgabe und Dateisysteme b) Journaled File Systems ● Funktionsweise - zusätzlich zum Schreiben der Daten und Meta-Daten wird ein Protokoll (Log File) der Änderungen geführt - Änderungen treten als Teil von Transaktionen auf - beim Bootvorgang wird auf Inkonsistenzen geprüft ● Klausurvorbereitungsveranstaltung 08.07.2013 32 4 – Ein-/Ausgabe und Dateisysteme b) Journaled File Systems ● Funktionsweise - zusätzlich zum Schreiben der Daten und Meta-Daten wird ein Protokoll (Log File) der Änderungen geführt - Änderungen treten als Teil von Transaktionen auf - beim Bootvorgang wird auf Inkonsistenzen geprüft keine Inkonsistenten Meta-Daten möglich Hochfahren eines abgestürzten Systems benötigt nur den relativ kurzen Durchgang durch das Log-File (effizienter als chkdsk) ineffizienter, da zusätzliches Log-File geschrieben wird ● Klausurvorbereitungsveranstaltung 08.07.2013 33 Auswertung Bitte schnell einmal die Punkte zusammenzählen ... Notenspiegel: Punkte Note 38,5–45 1 33,5–38 2 28–33 3 22,5–27,5 4 0–22 5 ● ● Klausurvorbereitungsveranstaltung 08.07.2013 34 Weitere Hinweise zur Vorbereitung Inhalt der Folien lernen ● Klassifizieren: Was muss ich lernen? Was muss ich begreifen? Übungsaufgaben verstehen, C und UNIX „können“ ● ASSESS-System bleibt mindestens bis zur Klausur offen - bei Fragen zur Korrektur melden ● Am besten die Aufgaben noch einmal lösen ● Optionale Zusatzaufgaben bearbeiten Beispielaufgaben lösen ● ältere Last Chance Tests, Probeklausuren Literatur zur Lehrveranstaltung durchlesen BS-Forum nutzen ● ● ● ● ● Klausurvorbereitungsveranstaltung 08.07.2013 35 Empfohlene Literatur [1] A. Silberschatz et al. Operating System Concepts. Wiley, 2004. ISBN 978-0471694663 [2] A. Tanenbaum: Modern Operating Systems (2nd ed.). Prentice Hall, 2001. ISBN 0-13-031358-0 [3] B. W. Kernighan, D. M. Ritchie. The C Programming Language. Prentice-Hall, 1988. ISBN 0-13-110362-8 (paperback) 0-13-110370-9 (hardback) [4] R. Stevens, Advanced Programming in the UNIX Environment, Addison-Wesley, 2005. ISBN 978-0201433074 Viel Erfolg bei der Klausur! Klausurvorbereitungsveranstaltung 08.07.2013 36 Betriebssysteme (BS) Probeklausur Olaf Spinczyk Arbeitsgruppe Eingebettete Systemsoftware Lehrstuhl für Informatik 12 TU Dortmund http://ess.cs.uni-dortmund.de/ http://ess.cs.tu-dortmund.de/DE/Teaching/SS2014/BS/ 1 Ablauf Probeklausur (45 Minuten) Besprechung der Aufgaben Auswertung Weitere Hinweise zur Vorbereitung ● ● ● ● Klausurvorbereitungsveranstaltung 07.07.2014 2 Probeklausur ... in (fast) allen Belangen realistisch: Art der Aufgaben ● Auswahl aus dem gesamten Inhalt der Veranstaltung - Betriebssystemgrundlagen und UNIX-Systemprogrammierung in C - alle Vorlesungen und Übungen sind relevant Umfang ● kürzer als das „Original“: ca. 40–45 (statt 60) Minuten Durchführung ● keine Hilfsmittel erlaubt (keine Spickzettel, Bücher, ...) ● bitte still arbeiten ● jeder für sich Die Klausur wird nicht eingesammelt. Klausurvorbereitungsveranstaltung 07.07.2014 3 ● ● ● ● 1 – Prozesse und Scheduling Der Pipe „|“ Operator verbindet die Standardausgabe eines Prozesses mit der Standardeingabe eines weiteren Prozesses nach dem FIFO-Prinzip. ls -R | grep jpg | wc Klausurvorbereitungsveranstaltung 07.07.2014 4 1 – Prozesse und Scheduling Es handelt sich um die Umlenkung der Eingabe für einen Prozess. So ist es z. B. möglich eine Eingabe aus einer Datei statt von der Tastatur zu lesen. Klausurvorbereitungsveranstaltung 07.07.2014 5 1 – Prozesse und Scheduling Ein Programm ist eine, nach bestimmten Regeln formulierte, Anweisungsvorschrift. Ein Prozess ist ein Programm in Ausführung dynamisch Folge von Rechnen und Ein-/Ausgabe benötigt Betriebsmittel des Rechners wird vom BS kontrolliert ● ● ● ● Klausurvorbereitungsveranstaltung 07.07.2014 6 1 – Prozesse und Scheduling Klausurvorbereitungsveranstaltung 07.07.2014 7 2 – Synchronisation & Verklemmung mutual exclusion die umstrittenen Betriebsmittel sind nur unteilbar nutzbar hold and wait die Prozesse fordern Betriebsmittel an, behalten aber zugleich den Zugriff auf andere no preemption umstrittene Betriebsmittel sind nicht rückforderbar, können nur durch den Prozess freigegeben werden ● ● ● Klausurvorbereitungsveranstaltung 07.07.2014 8 2 – Synchronisation & Verklemmung X X X X X X ● ● ● ● Semaphoren, basieren auf dem Prinzip des passivem Wartens Der Bäckerei-Algorithmus kann nicht garantieren, dass eine Wartenummer nur an einen Prozess vergeben wird Unterbrechungsanforderungen gehören zu den konsumierbaren Betriebsmitteln Klausurvorbereitungsveranstaltung 07.07.2014 9 2 – Synchronisation & Verklemmung ● ● ● acquire() ist nicht atomar und damit selbst kritisch aktives Warten verschwendet CPU-Zeit Gängiger Mechanismus: Semaphoren Klausurvorbereitungsveranstaltung 07.07.2014 10 2 – Synchronisation & Verklemmung ● Deadlock ● passives Warten (gut) ● Prozesszustand blocked Livelock ● aktives Warten (schlecht) ● alle Prozesszustände möglich (auch RUNNING) ● kein Fortschritt Deadlocks sind erkennbar, es existiert eine Basis zur Auflösung ● ● Klausurvorbereitungsveranstaltung 07.07.2014 11 3 – Speicherverwaltung & virt. Speicher CC Buddy-Verfahren: auf nächste 2er-Potenz aufrunden! Klausurvorbereitungsveranstaltung 07.07.2014 12 3 – Speicherverwaltung & virt. Speicher DDDDDDDD Klausurvorbereitungsveranstaltung 07.07.2014 13 3 – Speicherverwaltung & virt. Speicher kann nicht erfüllt werden – keine 16 MiB am Stück verfügbar Klausurvorbereitungsveranstaltung 07.07.2014 14 3 – Speicherverwaltung & virt. Speicher FFFF Klausurvorbereitungsveranstaltung 07.07.2014 15 3 – Speicherverwaltung & virt. Speicher Externer Verschnitt ● Außerhalb der zugeteilten Speicherbereich entstehen Speicherfragmente, die nicht mehr genutzt werden können. ● Passiert bei den listenbasierten Strategien wie First Fit, Best Fit, ... ● 0 8 16 A B C D Speicher 3 2 Länge Klausurvorbereitungsveranstaltung 07.07.2014 16 3 – Speicherverwaltung & virt. Speicher Interner Verschnitt ● Innerhalb der zugeteilten Speicherbereiche gibt es ungenutzten Speicher. ● Passiert z.B. bei Buddy, da die Anforderungen auf die nächstgrößere Zweierpotenz aufgerundet werden. 0 128 256 384 512 640 768 896 1024 ● 1024 A 128 256 512 A B 64 256 512 A B 64 C 128 512 Anfrage 70 Anfrage 35 Anfrage 80 70 35 80 Klausurvorbereitungsveranstaltung 07.07.2014 17 4 – Ein-/Ausgabe und Dateisysteme Hier wird überprüft, ob es sich bei „datei.txt“ um eine reguläre Datei handelt. Falls „datei.txt“ keine reguläre Datei ist, bricht das Programm ab. Klausurvorbereitungsveranstaltung 07.07.2014 18 4 – Ein-/Ausgabe und Dateisysteme Dieser Aufruf setzt die Schreib-/Leseposition, in dem angegebenen Stream vom Ende der aus Datei, um 5 Bytes zurück. Klausurvorbereitungsveranstaltung 07.07.2014 19 4 – Ein-/Ausgabe und Dateisysteme **ve for t##ay! Klausurvorbereitungsveranstaltung 07.07.2014 20 4 – Ein-/Ausgabe und Dateisysteme ● a) E/A-Scheduling ● Shortest Seek Time First: - Auftrag mit der kürzesten Positionierzeit wird vorgezogen ● Elevator: - Plattenarm bewegt sich in eine Richtung bis keine Aufträge mehr vorhanden sind ● Problem bei SSTF im Gegensatz zu Elevator? - eine Anfrage könnte „nie“ beantwortet werden, falls immer eine Anfrage eintrifft, bei der die Positionierzeit kürzer ist → Aushungerung Klausurvorbereitungsveranstaltung 07.07.2014 21 4 – Ein-/Ausgabe und Dateisysteme a) E/A-Scheduling ● Beispiel für SSTF – Referenzfolge: 2 3 4 10 1 2 3 4 5 6 7 8 9 10 ● Klausurvorbereitungsveranstaltung 07.07.2014 22 4 – Ein-/Ausgabe und Dateisysteme a) E/A-Scheduling ● Beispiel für SSTF – Referenzfolge: 10 123456789 ● neue Anfragen: 10 123 Klausurvorbereitungsveranstaltung 07.07.2014 23 4 – Ein-/Ausgabe und Dateisysteme a) E/A-Scheduling ● Beispiel für SSTF – Referenzfolge: 3 2 1 10 1 2 3 4 5 6 7 8 9 10 ● Klausurvorbereitungsveranstaltung 07.07.2014 24 4 – Ein-/Ausgabe und Dateisysteme a) E/A-Scheduling ● Beispiel für SSTF – Referenzfolge: 10 123456789 ● neue Anfragen: 10 234 Klausurvorbereitungsveranstaltung 07.07.2014 25 4 – Ein-/Ausgabe und Dateisysteme a) E/A-Scheduling ● Beispiel für SSTF – Referenzfolge: 10 123456789 ● neue Anfragen: 10 123 hier würde das Aushungern auftreten! Klausurvorbereitungsveranstaltung 07.07.2014 26 Auswertung Bitte schnell einmal die Punkte zusammenzählen ... Notenspiegel: Punkte Note 38,5–45 1 33,5–38 2 28–33 3 22,5–27,5 4 0–22 5 ● ● Klausurvorbereitungsveranstaltung 07.07.2014 27 Weitere Hinweise zur Vorbereitung Inhalt der Folien lernen ● Klassifizieren: Was muss ich lernen? Was muss ich begreifen? Übungsaufgaben verstehen, C und UNIX „können“ ● ASSESS-System bleibt mindestens bis zur Klausur offen - bei Fragen zur Korrektur melden ● Am besten die Aufgaben noch einmal lösen ● Optionale Zusatzaufgaben bearbeiten Literatur zur Lehrveranstaltung durchlesen BS-Forum nutzen ● ● ● ● Klausurvorbereitungsveranstaltung 07.07.2014 28 Empfohlene Literatur [1] A. Silberschatz et al. Operating System Concepts. Wiley, 2004. ISBN 978-0471694663 [2] A. Tanenbaum: Modern Operating Systems (2nd ed.). Prentice Hall, 2001. ISBN 0-13-031358-0 [3] B. W. Kernighan, D. M. Ritchie. The C Programming Language. Prentice-Hall, 1988. ISBN 0-13-110362-8 (paperback) 0-13-110370-9 (hardback) [4] R. Stevens, Advanced Programming in the UNIX Environment, Addison-Wesley, 2005. ISBN 978-0201433074 Viel Erfolg bei der Klausur! Klausurvorbereitungsveranstaltung 07.07.2014 29 Betriebssysteme (BS) Probeklausur Olaf Spinczyk und Alexander Lochmann Arbeitsgruppe Eingebettete Systemsoftware Lehrstuhl für Informatik 12 TU Dortmund http://ess.cs.uni-dortmund.de/ http://ess.cs.tu-dortmund.de/DE/Teaching/SS2015/BS/ 1 Ankündigung Rechnerübung findet nochmal zur LCT-Vorbereitung statt: ● Mittwoch, 08. Juli ● Montag, 13. Juli ● Klausurvorbereitungsveranstaltung 06.07.2015 2 Ablauf Probeklausur (45 Minuten) Besprechung der Aufgaben Auswertung Weitere Hinweise zur Vorbereitung ● ● ● ● Klausurvorbereitungsveranstaltung 06.07.2015 3 Probeklausur ... in (fast) allen Belangen realistisch: Art der Aufgaben ● Auswahl aus dem gesamten Inhalt der Veranstaltung - Betriebssystemgrundlagen und UNIX-Systemprogrammierung in C - alle Vorlesungen und Übungen sind relevant Umfang ● kürzer als das „Original“: ca. 40–45 (statt 60) Minuten Durchführung ● keine Hilfsmittel erlaubt (keine Spickzettel, Bücher, ...) ● bitte still arbeiten ● jeder für sich Die Klausur wird nicht eingesammelt. Klausurvorbereitungsveranstaltung 06.07.2015 4 ● ● ● ● 1 – Prozesse und Scheduling a) Prozesserzeugung ● Was wird ausgegeben? int pferd; void* erzeugePferd(void* param) { pferd++; } printf("%d\n",pferd); pthread_exit(NULL); return NULL; int main(void) { pferd = 42; } pthread_t id; pthread_create(...); erzeugePferd(NULL); pthread_exit(NULL); return 0; 43 44 43 44 } ● int pferd; void* erzeugePferd(void* param) { pferd++; printf("%d\n",pferd); return NULL; } int main(void) { pferd = 42; pid_t ret; if (fork() == 0) { erzeugePferd(NULL); } else { erzeugePferd(NULL); } return 0; 43 43 43 43 Klausurvorbereitungsveranstaltung 06.07.2015 5 1 – Prozesse und Scheduling a) Prozesserzeugung ● Wieso ist die Ausgabe unterschiedlich? ● ● fork() ● Erzeugt neuen Prozess ● Kopiert Adressraum → eigene Version von Data, BSS, Heap und Stack ● pthread_create() ● Erzeugt neuen Thread ● Legt eigenen Stack an ● Teilt sich Data, BSS und Heap Jeder hat Jeder hat sein eigenes „pferd“ sein eigenes „pferd“ Beide teilen sich Beide teilen sich ein „pferd“ ein „pferd“ Klausurvorbereitungsveranstaltung 06.07.2015 6 1 – Prozesse und Scheduling b) Prozesse ● 1) Was geschieht mit den Kindprozessen, wenn der Elternprozess terminiert? ● (engl. „orphan processes“) Ein UNIX-Prozess wird zum Waisenkind, wenn sein Elternprozess terminiert. Was passiert mit der Prozesshierarchie? ● ● init (PID 1) init (PID 1) getty tty0 login bash exit! firefox firefox init (PID 1) adoptiert alle verwaisten Prozesse. init (PID 1) adoptiert alle verwaisten Prozesse. So bleibt die Prozesshierarchie intakt. So bleibt die Prozesshierarchie intakt. Klausurvorbereitungsveranstaltung 06.07.2015 7 1 – Prozesse und Scheduling b) Prozesse ● 2) Was ist der copy-on-write Mechanismus? Wo kommt er im Kontext von Prozessen zum Einsatz? Copy-on-write ● Zwei (oder mehr) Entitäten arbeiten auf demselbem Datum ● Erst bei einem schreibendem Zugriff werden Kopien erstellt Einsatz im Kontext von Prozessen ● Verwendung bei fork() ● Erlaubt schnelles Erzeugen von Prozessen ● Beide (Vater und Kind) arbeiten zunächst auf denselbem BSS-, Daten-, und Heap-Segment – bis einer der beiden etwas verändert ● ● ● Klausurvorbereitungsveranstaltung 06.07.2015 8 1 – Prozesse und Scheduling c) Scheduling X X SRTF → Übungsaufgabe A1, Theorieaufgabe 1 E/A-lastige Prozesse geben die CPU sofort ab und kommen ans Ende der ready-Liste Präemptives Scheduling soll eine Monopolisierung der CPU verhindern E/A-lastige Prozesse werden benachteiligt ● X X ● ● ● ● Klausurvorbereitungsveranstaltung 06.07.2015 9 2 – Synchronisation und Verklemmung Die Funktionen producer() und consumer() in folgendem Pseudocode- Abschnitt werden potentiell gleichzeitig ausgeführt, wobei producer() Elemente erzeugt und consumer() diese verbraucht. Synchronisieren Sie die beiden Funktionen mittels einseitiger Synchronisation und beachten Sie dabei, dass die Warteschlange zwar beliebig viele Elemente aufnehmen kann, die Operationen enqueue() und dequeue() aber selbst kritisch sind und nicht gleichzeitig ausgeführt werden dürfen. Der consumer() soll nur Elemente aus der Warteschlange entfernen, wenn diese nicht leer ist! Legen Sie dazu geeignet benannte Semaphore an, initialisieren Sie diese, und setzen Sie an den freien Stellen Semaphor-Operationen (P, V bzw. wait, signal) ein (z.B. P(MeinSemaphor)). (P(), V(), produce_element(), consume_element(), enqueue() und dequeue() können als gegeben angesehen werden und müssen nicht implementiert werden!) ● Klausurvorbereitungsveranstaltung 06.07.2015 10 2 – Synchronisation und Verklemmung a) Namen und Initialwerte der Semaphore: ● mutex – Wert=1 ● elements - Wert=0 ● producer () { while (1) { Element e = produce_element (); P(mutex); enqueue ( e ); V(mutex); V(elements); } } consumer() { while (1) { P(elements); P(mutex); Element e = dequeue(); V(mutex); consume_element(e); } } Klausurvorbereitungsveranstaltung 06.07.2015 11 2 – Synchronisation und Verklemmung b) Erläutern Sie, was man unter sogenannten Race Conditions versteht und wie man diese verhindern kann. ● Race Conditions entstehen, wenn mehrere Prozesse auf die selben Daten zugreifen und mindestens ein Prozess diese manipuliert. ● Klausurvorbereitungsveranstaltung 06.07.2015 12 2 – Synchronisation und Verklemmung c) Nennen und erläutern Sie zwei Bedingungen, die notwendig sind, damit eine Verklemmung auftreten kann. 1) Exklusive Belegung von Betriebsmitteln („mutual exclusion“) - die umstrittenen Betriebsmittel sind nur unteilbar nutzbar 2) Nachforderung von Betriebsmitteln („hold and wait“) - die umstrittenen Betriebsmittel sind nur schrittweise belegbar 3) Kein Entzug von Betriebsmitteln („no preemption“) - Die umstrittenen Betriebsmittel sind nicht rückforderbar 4) Zirkuläres Warten („circular wait“) - Eine geschlossene Kette wechselseitig wartender Prozesse ● Klausurvorbereitungsveranstaltung 06.07.2015 13 2 – Synchronisation und Verklemmung d) Nennen Sie eine Möglichkeit zur Verklemmungsvorbeugung (deadlock prevention) ● indirekte Methoden entkräften eine der Bedingungen 1–3 - nicht-blockierende Verfahren verwenden - Betriebsmittelanforderungen unteilbar (atomar) auslegen - Betriebsmittelentzug durch Virtualisierung ermöglichen - virtueller Speicher, virtuelle Geräte, virtuelle Prozessoren ● direkte Methoden entkräften Bedingung 4 - lineare/totale Ordnung von Betriebsmittelklassen einführen: - Betriebsmittel Bi ist nur dann erfolgreich vor Bj belegbar, wenn i linear vor j angeordnet ist (d.h. i < j). ● Klausurvorbereitungsveranstaltung 06.07.2015 14 3 – Speicherverwaltung + virt. Speicher a) Adressabbildung ● Klausurvorbereitungsveranstaltung 06.07.2015 15 Vorlesungsfolien: 08 - Speicherverwaltung Seitenadressierung (paging) Einteilung des logischen Adressraums in gleichgroße Seiten, die an beliebigen Stellen im physikalischen Adressraum liegen können ● Lösung des Fragmentierungsproblems ● keine Kompaktifizierung mehr nötig ● Vereinfacht Speicherbelegung und Ein-/Auslagerungen ● logischer Adressraum physikalischer Adressraum ROM RAM Seiten (pages) Kacheln (frames) 16 Klausurvorbereitungsveranstaltung 06.07.2015 Vorlesungsfolien: 08 - Speicherverwaltung MMU mit Seiten-Kacheltabelle Tabelle setzt Seiten in Kacheln um SKT Basisregister Seiten-Kacheltabelle+ Startadr. 00000 00001 00002 00003 00004 logische Adresse ● 00002 12a ffe0 fxxx ... physikalische Adresse ffe0f 12a Klausurvorbereitungsveranstaltung 06.07.2015 17 3 – Speicherverwaltung + virt. Speicher ● a) Adressabbildung 4000 OR AB1 4AB1 5000 OR 1B7 51B7 Klausurvorbereitungsveranstaltung 06.07.2015 18 3 – Speicherverwaltung + virt. Speicher b) LRU (Seitenersetzung) ● Referenzfolge 3 1 2 4 2 1 5 3 2 Kachel 1 3 3 3 4 4 4 5 5 5 Kachel 2 1 1 1 1 1 1 1 2 Kachel 3 2 2 2 2 2 3 3 Kontrollzustände Kachel 1 0 1 2 0 1 2 0 1 2 Kachel 2 0 1 2 3 0 1 2 0 Kachel 3 0 1 0 1 2 0 1 Klausurvorbereitungsveranstaltung 06.07.2015 19 4 - Ein-/Ausgabe und Dateisysteme Gegeben sei ein Plattenspeicher mit 16 Spuren. Der jeweilige I/O-Scheduler bekommt immer wieder Leseaufträge für eine bestimmte Spur. Die Leseaufträge in L1 sind dem I/O-Scheduler bereits bekannt. Nach einem bearbeiteten Auftrag erhält er die Aufträge in L2. Nach weiteren drei (d.h. nach insgesamt vier) bearbeiteten Aufträgen erhält er die Aufträge in L3. Zu Beginn befindet sich der Schreib-/Lesekopf über Spur 0. L1={4,7,11,3} L2={2,13,1} L3={15,5,6} ● Klausurvorbereitungsveranstaltung 06.07.2015 20 4 - Ein-/Ausgabe und Dateisysteme L1={4,7,11,3} L2={2,13,1} L3={15,5,6} Sofort bekannt Nach 1 Ops Nach 4 Ops bekannt bekannt Bitte tragen Sie hier die Reihenfolge der gelesenen Spuren für einen I/O-Scheduler, der nach der First In First Out (FIFO) Strategie arbeitet, ein: ● Klausurvorbereitungsveranstaltung 06.07.2015 21 4 - Ein-/Ausgabe und Dateisysteme I/O-Anfragen: 4, 7, 11, 3 Position des Kopfes 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 T=0 Klausurvorbereitungsveranstaltung 06.07.2015 22 4 - Ein-/Ausgabe und Dateisysteme I/O-Anfragen: 7, 11, 3, 2, 13, 1 Position des Kopfes 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 T=1 4 Klausurvorbereitungsveranstaltung 06.07.2015 23 4 - Ein-/Ausgabe und Dateisysteme I/O-Anfragen: 11, 3, 2, 13, 1 Position des Kopfes 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 T=2 4 7 Klausurvorbereitungsveranstaltung 06.07.2015 24 4 - Ein-/Ausgabe und Dateisysteme I/O-Anfragen: 3, 2, 13, 1 Position des Kopfes 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 T=3 4 7 11 Klausurvorbereitungsveranstaltung 06.07.2015 25 4 - Ein-/Ausgabe und Dateisysteme I/O-Anfragen: 2, 13, 1, 15, 5, 6 Position des Kopfes 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 T=4 4 7 11 3 Klausurvorbereitungsveranstaltung 06.07.2015 26 4 - Ein-/Ausgabe und Dateisysteme I/O-Anfragen: 13, 1, 15, 5, 6 Position des Kopfes 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 T=5 4 7 11 3 2 Klausurvorbereitungsveranstaltung 06.07.2015 27 4 - Ein-/Ausgabe und Dateisysteme I/O-Anfragen: 1, 15, 5, 6 Position des Kopfes 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 T=6 4 7 11 3 2 13 Klausurvorbereitungsveranstaltung 06.07.2015 28 4 - Ein-/Ausgabe und Dateisysteme I/O-Anfragen: 15, 5, 6 Position des Kopfes 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 T=7 4 7 11 3 2 13 1 Klausurvorbereitungsveranstaltung 06.07.2015 29 4 - Ein-/Ausgabe und Dateisysteme I/O-Anfragen: 5, 6 Position des Kopfes 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 T=8 4 7 11 3 2 13 1 15 Klausurvorbereitungsveranstaltung 06.07.2015 30 4 - Ein-/Ausgabe und Dateisysteme I/O-Anfragen: 6 Position des Kopfes 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 T=9 4 7 11 3 2 13 1 15 5 Klausurvorbereitungsveranstaltung 06.07.2015 31 4 - Ein-/Ausgabe und Dateisysteme I/O-Anfragen: 6 Position des Kopfes 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 T= 10 4 7 11 3 2 13 1 15 5 6 Klausurvorbereitungsveranstaltung 06.07.2015 32 4 - Ein-/Ausgabe und Dateisysteme b) Nennen Sie je einen Vorteil und einen Nachteil der kontinuierlichen Datenspeicherung ● Vorteile: - Zugriff auf alle Blöcke mit minimaler Positionierzeit des Schwenkarms - Schneller direkter Zugriff auf bestimmter Dateiposition - Einfacher Einsatz bei nicht-beschreibbaren Medien (CD, etc) ● Nachteile: - Finden des freien Platzes auf der Festplatte (Menge aufeinanderfolgender und freier Plattenblöcke) - Fragmentierungsproblem (Verschnitt: nicht nutzbare Plattenblöcke; siehe auch Speicherverwaltung) - Größe bei neuen Dateien oft nicht im Voraus bekannt - Erweitern ist problematisch - Umkopieren, falls kein freier angrenzender Block mehr verfügbar ● Klausurvorbereitungsveranstaltung 06.07.2015 33 4 - Ein-/Ausgabe und Dateisysteme ● c) Indizierte Speicherung direkt 0 direkt 1 direkt 9 einfach indirekt zweifach indirekt dreifach indirekt Inode Datenblöcke Klausurvorbereitungsveranstaltung 06.07.2015 34 ... 4 - Ein-/Ausgabe und Dateisysteme c) Indizierte Speicherung ● 1. Nennen Sie beispielhaft ein Dateisystem, bei dem Dateien in der dargestellten Weise abgelegt werden.UNIX-, Linux-Dateisysteme, EXT2,3,4 Filesystem UNIX-, Linux-Dateisysteme, wie z.B. EXT2,3,4 Filesystem ● ● Klausurvorbereitungsveranstaltung 06.07.2015 35 4 - Ein-/Ausgabe und Dateisysteme c) Indizierte Speicherung ● 2. Ein hypothetisches Dateisystem verwendet Inodes wie oben dargestellt, nur ohne Dreifach-Indirektion. Wie lässt sich die maximale Dateigröße für dieses Dateisystem berechnen, wenn die Blockgröße 1024 Bytes beträgt und für die Speicherung eines Blockverweises 4 Bytes benötigt werden. Hinweis: Es ist nicht erforderlich die Zahl auszurechnen. Beschreiben Sie den Rechenweg Schritt für Schritt oder geben Sie eine Formel an. ● Klausurvorbereitungsveranstaltung 06.07.2015 36 4 - Ein-/Ausgabe und Dateisysteme B: Maximale Anzahl der Blöcke BG: Blockgröße D: Maximale Dateigröße (gesucht) I: Anzahl der Verweise in indirekten Blöcken Jeder Blockverweis ist 4 Byte groß ● ● ● ● I=BG/4=1024/4 Jeder Blockverweis ist 4 Byte groß Direkte Einfache Direkte Indirektion Verweise Indirektion Verweise Einfache Zweifache Indirektion Indirektion D=BG∗B=BG∗(10+I+I∗I) =1024 Bytes∗(10+256+256∗256) =67381248Bytes =65802KiBytes Zweifache Klausurvorbereitungsveranstaltung 06.07.2015 37 4 - Ein-/Ausgabe und Dateisysteme c) Indizierte Speicherung ● 3) Nennen Sie einen Vorteil und einen Nachteil der indizierten Speicherung im Vergleich zur kontinuierlichen Speicherung. ● ● ● Vorteil: ● Auch große Dateien lassen sich so addressieren Nachteil: ● Bei großen Dateien müssen mehrere Blöcke gelesen werden Klausurvorbereitungsveranstaltung 06.07.2015 38 Auswertung Bitte schnell einmal die Punkte zusammenzählen ... Notenspiegel: Punkte Note 38,5–45 1 33,5–38 2 28–33 3 22,5–27,5 4 0–22 5 ● ● Klausurvorbereitungsveranstaltung 06.07.2015 39 Weitere Hinweise zur Vorbereitung Inhalt der Folien lernen ● Klassifizieren: Was muss ich lernen? Was muss ich begreifen? Übungsaufgaben verstehen, C und UNIX „können“ ● ASSESS-System bleibt mindestens bis zur Klausur offen - bei Fragen zur Korrektur melden ● Am besten die Aufgaben noch einmal lösen ● Optionale Zusatzaufgaben bearbeiten Literatur zur Lehrveranstaltung durchlesen BS-Forum nutzen ● ● ● ● Klausurvorbereitungsveranstaltung 06.07.2015 40 Empfohlene Literatur [1] A. Silberschatz et al. Operating System Concepts. Wiley, 2004. ISBN 978-0471694663 [2] A. Tanenbaum: Modern Operating Systems (2nd ed.). Prentice Hall, 2001. ISBN 0-13-031358-0 [3] B. W. Kernighan, D. M. Ritchie. The C Programming Language. Prentice-Hall, 1988. ISBN 0-13-110362-8 (paperback) 0-13-110370-9 (hardback) [4] R. Stevens, Advanced Programming in the UNIX Environment, Addison-Wesley, 2005. ISBN 978-0201433074 Viel Erfolg bei der Klausur! Klausurvorbereitungsveranstaltung 06.07.2015 41 Betriebssysteme Probeklausur http://ess.cs.tu-dortmund.de/DE/Teaching/SS2016/BS/ Olaf Spinczyk und Pascal Libuschewski olaf.spinczyk@tu-dortmund.de https://ess.cs.tu-dortmund.de/~os AG Eingebettete Systemsoftware Informatik 12, TU Dortmund Ablauf Probeklausur (45 Minuten) Besprechung der Aufgaben Auswertung Weitere Hinweise zur Vorbereitung ● ● ● ● Probeklausur ... in (fast) allen Belangen realistisch: Art der Aufgaben ● ● ● – ● – ● Auswahl aus dem gesamten Inhalt der Veranstaltung Betriebssystemgrundlagen und UNIX-Systemprogrammierung in C alle Vorlesungen und Übungen sind relevant Umfang – kürzer als das „Original“: 45 (statt 60) Minuten Durchführung – keine Hilfsmittel erlaubt (keine Spickzettel, Bücher, ...) – bitte still arbeiten jeder für sich Die Klausur wird nicht eingesammelt. ● 1a) Round Robin (6 Punkte) Prozess Bedienzeit E/A-Zeitpunkt E/A-Dauer P1 70 ms 20 ms 80 ms P2 110 ms 30 ms 30 ms P3 90 ms 60 ms 50 ms P1 ••••••••––––– –––– P2 –– P3 ––––– 0 •••– –––––– –––– •••••–––– 100 200 Hinweise: ● Die Prozessorzeit wird in Zeitscheiben von 40 ms aufgeteilt ● Mit Ablauf der Zeitscheibe erfolgt ggfs. ein Prozesswechsel ● Unterbrochene Prozesse werden ans Ende der Bereitliste verdrängt ● Der nächste Prozess wird gemäß FCFS der Bereitliste entnommen 300 t[ms] 1b) Allgemeine Fragen 1. “>” Shell-Operator (1.5 Punkte) Angenommen der Befehl “echo Parameter” gibt in die Standardausgabe den Text aus dem Parameter:
Was bewirkt der Befehl “echo “” > Datei”, falls Datei schon Inhalt enthält?
– Der Inhalt der Datei wird gelöscht und die Datei enthält danach den String “”, also keine Zeichen.

1b) Allgemeine Fragen
2. Prozesse vs. Funktionen (1.5 Punkte) Erklären Sie kurz den Unterschied einer Prozesserzeugung und einem Funktionsaufruf.
– Prozesserzeugungen erzeugen eine Kopie des bereits laufenden Prozesses. Nach der Erzeugung laufen zwei Prozesse parallel weiter. Es wird der Adressraum nicht geteilt.
– Ein Funktionsaufruf springt innerhalb einer Prozessausführung an eine Funktion, führt diese aus und springt anschließend an die aufrufende Funktion zurück. Es findet keine parallele Ausführung statt.

1b) Allgemeine Fragen
3. Zombie-Prozesse (1.5 Punkte) Warum muss das Betriebssystem auf das Abfragen von Zombie-Prozessen warten anstatt diese direkt aus der Prozesstabelle zu entfernen?
– Evtl. wird der Rückgabewert der Prozesse noch benötigt und abgefragt.

2a) Erzeuger/Verbraucher (7 Punkte)
Semaphore mutex = 1
Semaphore available = 0
producer () {
while (1) {
Element e = produce_element ();
P ( mutex );
enqueue ( e );
V ( mutex );
V ( available );
consumer () {
while (1) {
P ( available );
P ( mutex );
Element e = dequeue ( );
V ( mutex );
consume_element ( e );
} }
//wait(mutex)
//signal(mutex)
//signal(available)
//wait(available)
//wait(mutex)
//signal(mutex)
} }

2b) Verklemmungen (6 Punkte)
Nennen Sie stichpunktartig die drei Vorbedingungen, die erfüllt sein müssen, damit es überhaupt zu einer Verklemmung kommen kann, und erklären Sie diese jeweils kurz mit eigenen Worten.
– Exklusive Belegung von Betriebsmitteln (mutual exclusion)
die umstrittenen Betriebsmittel sind nur schrittweise belegbar
– Kein Entzug von Betriebsmitteln (no preemption)
die umstrittenen Betriebsmittel sind nicht rückforderbar
●
die umstrittenen Betriebsmittel sind nur unteilbar nutzbar
●
– Nachforderung von Betriebsmitteln (hold and wait)
●
●

3a) Platzierung/Ersetzung (4 Punkte)
Erläutern Sie den Unterschied zwischen der Platzierungsstrategie (placement policy) und der Ersetzungsstrategie (replacement policy)
– Die Platzierungsstrategie bestimmt woher benötigter Speicher genommen wird. (z.B. zur Minimierung des Verschnitts )
First/Last Fit Best Fit
Worst Fit Buddy-Verfahren
●
–
Die Ersetzungsstrategie bestimmt welche Speicherinhalte verdrängt werden sollen, falls kein freier Speicher mehr zu Verfügung steht.
LRU – Least recently used FIFO – First in First out Second Chance
● ● ● ●
● ● ●

3b) Speichersegmentierung (4 Punkte)
Geben Sie für die Speicheranfragen 0x1000 A100 und
0x030B 5000 die physikalische Adresse unter Anwendung des Speichersegmentierungsverfahrens an.
Die höchstwertigen 8 Bit der logischen Adresse geben die Position innerhalb der Segementtabelle an. Löst eine Speicheranfrage eine Zugriffsverletzung aus, so machen Sie dies bitte kenntlich.
●
Startadresse Länge
0116
B542 000016
01 000016
0216
C471 000016
00 F00016
0316
B080 000016
00 FFFF16
…
1016
4310 100016
FF FFF16

3b) Speichersegmentierung (4 Punkte)
●
Anfrage:0x1000 A100 Segmenttabellen-
basisregister
Segmenttabelle
Länge
01 000016
00 F00016
00 FFFF16
FF FFF16
+
10
00 A100
logische Adresse
Startadresse
0116 B542 000016
0216 C471 000016
0316 B080 000016
…
1016 4310 100016
< ja Trap: Schutzverletzung + 4310 B100 physikalische Adresse 3b) Speichersegmentierung (4 Punkte) ● Anfrage:0x030B 5000 Segmenttabellen- basisregister Segmenttabelle Länge 01 000016 00 F00016 00 FFFF16 FF FFF16 + 03 0B 5000 logische Adresse Startadresse 0116 B542 000016 0216 C471 000016 0316 B080 000016 ... 1016 4310 100016 < ja Trap: Schutzverletzung + physikalische Adresse 3c) Buddy-Verfahren (4 Punkte) Szenario 1: Prozess C belegt 3 MiB (aufgerundet 4 MiB) AAAA BB ● 0 2 4 6 8 10 12 14 16 18 20 22 24 26 28 30 Lösung: AAAA 0 246 8 10 12 14 16 18 20 22 24 26 28 30 CC BB 3c) Buddy-Verfahren (4 Punkte) Szenario 2: Prozess D belegt 12 MiB (aufgerundet 16 MiB) AA ● 0 2 4 6 8 10 12 14 16 18 20 22 24 26 28 30 Lösung: AA DDDDDDDD 0 2 4 6 8 10 12 14 16 18 20 22 24 26 28 30 3c) Buddy-Verfahren (4 Punkte) Szenario 3: Prozess E belegt 14 MiB (aufgerundet 16 MiB) BB AA ● 0 2 4 6 8 10 12 14 16 18 20 22 24 26 28 30 Lösung: Belegung ist nicht möglich 0 2 4 6 8 10 12 14 16 18 20 22 24 26 28 30 BB AA 4 MiB 8 MiB 8 MiB 4 MiB 3c) Buddy-Verfahren (4 Punkte) Szenario 4: Prozess F belegt 7 MiB (aufgerundet 8 MiB) AAAABB ● 0 2 4 6 8 10 12 14 16 18 20 22 24 26 28 30 Lösung: AAAA 0 246 8 10 12 14 16 18 20 22 24 26 28 30 BB FFFF 4a) Block-Buffer-Cache (3 Punkte) Nennen und erläutern Sie drei Ereignisse, die das Rückschreiben des Block-Buffer-Caches auslösen. – Wenn kein freier Puffer mehr vorhanden ist – Bei Aufruf des Systemaufrufes sync() – Regelmäßig vom System – Nach jedem Schreibaufruf im Modus O_SYNC ● 4b) Kontinuierliche Speicherung (2 Punkte) Datei wird in Blöcken mit aufsteigenenden Blocknummern gespeichert Vorteile: – Zugriff auf alle Blöcke mit minimaler Positionierungszeit – Schneller direkter Zugriff auf bestimmte Dateipositionen – Gut geeignet für nicht-modifizierbare Datenträger (z.B. optische Medien) Nachteile: – Aufwändiges Finden von freiem, aufeinanderfolgendem Speicherplatz – Fragmentierungsproblem – Dateigröße von neuen Dateien oft nicht im Voraus bekannt – Erweitern bestehender Daten komplex – Umkopieren notwendig, wenn hinter Daten kein freier Platz ist ● ● ● 4c) IO-Scheduling (4,5 Punkte) L1={1,4,7,2} L2={3,6,0} L3={5,2} Sofort bekannt Nach 3 Ops Nach 6 Ops bekannt bekannt ● Bitte tragen Sie hier die Reihenfolge der gelesenen Spuren für einen I/O-Scheduler, der nach der Fahrstuhl (Elevator) Strategie arbeitet, ein: Übung 5 - Sicherheit 20 4c) IO-Scheduling (4,5 Punkte) I/O-Anfragen: 1, 4, 7, 2 Position des Kopfes 0 1 2 3 4 5 6 7 8 T=0 Übung 5 - Sicherheit 21 4c) IO-Scheduling (4,5 Punkte) I/O-Anfragen: 4, 7, 2 Position des Kopfes 0 1 2 3 4 5 6 7 8 T=1 1 Übung 5 - Sicherheit 22 4c) IO-Scheduling (4,5 Punkte) I/O-Anfragen: 4, 7 Position des Kopfes 0 1 2 3 4 5 6 7 8 T=2 1 2 Übung 5 - Sicherheit 23 4c) IO-Scheduling (4,5 Punkte) I/O-Anfragen: 7 Position des Kopfes 0 1 2 3 4 5 6 7 8 T=3 1 2 4 Übung 5 - Sicherheit 24 4c) IO-Scheduling (4,5 Punkte) I/O-Anfragen: 7, 3, 6, 0 Position des Kopfes 0 1 2 3 4 5 6 7 8 T=3 1 2 4 Übung 5 - Sicherheit 25 4c) IO-Scheduling (4,5 Punkte) I/O-Anfragen: 7, 3, 0 Position des Kopfes 0 1 2 3 4 5 6 7 8 T=4 1 2 4 6 Übung 5 - Sicherheit 26 4c) IO-Scheduling (4,5 Punkte) I/O-Anfragen: 3, 0 Position des Kopfes 0 1 2 3 4 5 6 7 8 T=5 1 2 4 6 7 Übung 5 - Sicherheit 27 4c) IO-Scheduling (4,5 Punkte) I/O-Anfragen: 0 Position des Kopfes 0 1 2 3 4 5 6 7 8 T=6 1 2 4 6 7 3 Übung 5 - Sicherheit 28 4c) IO-Scheduling (4,5 Punkte) I/O-Anfragen: 5, 2 Position des Kopfes 0 1 2 3 4 5 6 7 8 T=7 1 2 4 6 7 3 2 Übung 5 - Sicherheit 29 4c) IO-Scheduling (4,5 Punkte) I/O-Anfragen: 0, 5, 2 Position des Kopfes 0 1 2 3 4 5 6 7 8 T=6 1 2 4 6 7 3 Übung 5 - Sicherheit 30 4c) IO-Scheduling (4,5 Punkte) I/O-Anfragen: 0, 5 Position des Kopfes 0 1 2 3 4 5 6 7 8 T=7 1 2 4 6 7 3 2 Übung 5 - Sicherheit 31 4c) IO-Scheduling (4,5 Punkte) I/O-Anfragen: 5, Position des Kopfes 0 1 2 3 4 5 6 7 8 T=8 1 2 4 6 7 3 2 0 Übung 5 - Sicherheit 32 4c) IO-Scheduling (4,5 Punkte) I/O-Anfragen: Position des Kopfes 0 1 2 3 4 5 6 7 8 T=9 1 2 4 6 7 3 2 0 5 Übung 5 - Sicherheit 33 Auswertung Bitte schnell einmal die Punkte zusammenzählen ... Notenspiegel: Punkte Note 38,5–45 1 33,5–38 2 28–33 3 22,5–27,5 4 0–22 5 ● ● Weitere Hinweise zur Vorbereitung Inhalt der Folien lernen Übungsaufgaben verstehen, C und UNIX „können“ ● – Klassifizieren: Was muss ich lernen? Was muss ich begreifen? ● – AsSESS-System bleibt mindestens bis zur Klausur offen ● ● – Optionale Zusatzaufgaben bearbeiten Literatur zur Lehrveranstaltung durchlesen BS-Forum nutzen bei Fragen zur Korrektur melden ● – Am besten die Aufgaben noch einmal lösen Empfohlene Literatur [1] A. Silberschatz et al. Operating System Concepts. Wiley, 2004. ISBN 978-0471694663 [2] A. Tanenbaum: Modern Operating Systems (2nd ed.). Prentice Hall, 2001. ISBN 0-13-031358-0 [3] B. W. Kernighan, D. M. Ritchie. The C Programming Language. Prentice-Hall, 1988. ISBN 0-13-110362-8 (paperback) 0-13-110370-9 (hardback) [4] R. Stevens, Advanced Programming in the UNIX Environment, Addison-Wesley, 2005. ISBN 978-0201433074 Viel Erfolg bei der Klausur! Betriebssysteme Probeklausur https://ess.cs.tu-dortmund.de/DE/Teaching/SS2017/BS/ Olaf Spinczyk olaf.spinczyk@tu-dortmund.de https://ess.cs.tu-dortmund.de/~os AG Eingebettete Systemsoftware Informatik 12, TU Dortmund Ablauf Probeklausur (45 Minuten) Besprechung der Aufgaben Auswertung Weitere Hinweise zur Vorbereitung ● ● ● ● Probeklausur 2 Probeklausur ... in (fast) allen Belangen realistisch: Art der Aufgaben Auswahl aus dem gesamten Inhalt der Veranstaltung Betriebssystemgrundlagen und UNIX-Systemprogrammierung in C alle Vorlesungen und Übungen sind relevant Umfang kürzer als das „Original“: 45 (statt 60) Minuten Durchführung keine Hilfsmittel erlaubt (keine Spickzettel, Bücher, ...) bitte still arbeiten jeder für sich ● – ● – ● – – – ● Die Klausur wird nicht eingesammelt. Probeklausur ● ● 3 1a) Round Robin (6 Punkte) Prozess Bedienzeit E/A-Zeitpunkt E/A-Dauer P1 70 ms 20 ms 80 ms P2 110 ms 30 ms 30 ms P3 90 ms 60 ms 50 ms P1 ••••••••––––– –––– P2 –– P3 ––––– 0 •••– –––––– –––– •••••–––– 100 200 Hinweise: ● Die Prozessorzeit wird in Zeitscheiben von 40 ms aufgeteilt ● Mit Ablauf der Zeitscheibe erfolgt ggfs. ein Prozesswechsel ● Unterbrochene Prozesse werden ans Ende der Bereitliste verdrängt ● Der nächste Prozess wird gemäß FCFS der Bereitliste entnommen 300 t[ms] Probeklausur 4 1b) Prozesserzeugung (7 Punkte) ● WasgebendiefolgendenProgrammeaus? int pferd; int pferd; void* erzeugePferd(void* param) void* erzeugePferd(void* param) {{ pferd++; printf(“%d\n”, pferd); return NULL; }} pferd++; printf(“%d\n”, pferd); pthread_exit(NULL); int main(void) { pferd = 42; int main(void) { pferd = 42; pthread_t id; pthread_create(&id, NULL, erzeugePferd, NULL); erzeugePferd(NULL); return 0; } } if (fork() == 0) { erzeugePferd(NULL); } else { erzeugePferd(NULL); } return 0; 43 43 43 43 43 44 43 44 Probeklausur 5 1b) Prozesserzeugung (7 Punkte) ● WiesoistdieAusgabeunterschiedlich? ● fork() erzeugt schwergewichtige Prozesse Variable “pferd” liegt danach in unterschiedlichen Speicherbereichen Änderungen sind unabhängig voneinander ● pthread_create erzeugt leichtgewichtige POSIX-Threads Variable “pferd” liegt im gemeinsam genutzten Datensegment Beide Threads verändern die gleiche Variable ● ● ● ● Probeklausur 6 2a) Synchronisation (10 Punkte) Gemeinsamer Speicher, mehrere Leser, ein Schreiber ● /* gem. Speicher */ /* gem. Speicher */ Semaphore mutex = ?; Semaphore mutex = ?; Semaphore wrt = ?; Semaphore wrt = ?; int readcount = ?; int readcount = ?; void leser() { void leser() { void schreiber() { void schreiber() { } ? } ? ? schreibe_Daten(); schreibe_Daten(); ? } ? } ? readcount = ?; readcount = ?; if (readcount == ?) { if (readcount == ?) { } ? } ? ? Probeklausur 7 ? ? readcount = ?; readcount = ?; if (readcount == ?) { if (readcount == ?) { } ? } ? ? ? lese_Daten(); lese_Daten(); ? 2a) Synchronisation (10 Punkte) Gemeinsamer Speicher, mehrere Leser, ein Schreiber ● /* gem. Speicher */ /* gem. Speicher */ Semaphore mutex = 1; Semaphore mutex = 1; Semaphore wrt = 1; Semaphore wrt = 1; int readcount = 0; int readcount = 0; void leser() { void leser() { void schreiber() { void schreiber() { } signal(&wrt); } wait(&wrt); wait(&wrt); schreibe_Daten(); schreibe_Daten(); signal(&wrt); } signal(&mutex); } wait(&mutex); readcount = readcount – 1; readcount = readcount – 1; if (readcount == 0) { if (readcount == 0) { } signal(&wrt); } signal(&wrt); signal(&mutex); Probeklausur 8 wait(&mutex); wait(&mutex); readcount = readcount + 1; readcount = readcount + 1; if (readcount == 1) { if (readcount == 1) { } wait(&wrt); } wait(&wrt); signal(&mutex); signal(&mutex); lese_Daten(); lese_Daten(); wait(&mutex); 2b) Verklemmungen (4,5 Punkte) Nennen Sie stichpunktartig die drei Vorbedingungen, die erfüllt sein müssen, damit es überhaupt zu einer Verklemmung kommen kann, und erklären Sie diese jeweils kurz mit eigenen Worten. Exklusive Belegung von Betriebsmitteln (mutual exclusion) die umstrittenen Betriebsmittel sind nur unteilbar nutzbar ● – ● – ● – ● Nachforderung von Betriebsmitteln (hold and wait) die umstrittenen Betriebsmittel sind nur schrittweise belegbar Kein Entzug von Betriebsmitteln (no preemption) die umstrittenen Betriebsmittel sind nicht rückforderbar Probeklausur 9 3a) Adressabbildung (4 Punkte) In einem System mit Seitenadressierung (paging) befindet sich die Seitenkacheltabelle im unten angegebenen Zustand. Die Adresslänge beträgt 16 Bit, wovon 12 Bit für den Offset innerhalb der Seite verwendet werden (Seitengröße: 4096 Bytes). Bilden Sie die logischen Adressen 6AB1 und F1B7 auf ihre physikalischen Adressen ab. (Hinweis: Eine Hexadezimalziffer stellt immer genau vier Bit der Adresse dar.) ...... ...... ● Seitennummer Startadresse 6 400016 15 500016 Probeklausur 10 3a) Adressabbildung (4 Punkte) ● Logische Adresse: 6AB116 SKT Basisregister + 6 AB1 logische Adresse Seiten-Kacheltabelle Startadresse 5 6 7 ... 400016 ... 4 AB1 physikalische Adresse Probeklausur 11 3a) Adressabbildung (4 Punkte) ● Logische Adresse: F1B716 SKT Basisregister + F 1B7 logische Adresse Seiten-Kacheltabelle Startadresse 14 15 16 ... 500016 ... 5 1B7 physikalische Adresse Probeklausur 12 3b) Buddy-Verfahren (4 Punkte) Szenario 1: Prozess C belegt 3 MiB (aufgerundet 4 MiB) AAAA BB ● 0 2 4 6 8 10 12 14 16 18 20 22 24 26 28 30 Lösung: AAAA 0 246 8 10 12 14 16 18 20 22 24 26 28 30 CC BB Probeklausur 13 3b) Buddy-Verfahren (4 Punkte) Szenario 2: Prozess D belegt 12 MiB (aufgerundet 16 MiB) AA ● 0 2 4 6 8 10 12 14 16 18 20 22 24 26 28 30 Lösung: AA DDDDDDDD 0 2 4 6 8 10 12 14 16 18 20 22 24 26 28 30 Probeklausur 14 3b) Buddy-Verfahren (4 Punkte) Szenario 3: Prozess E belegt 14 MiB (aufgerundet 16 MiB) BB AA ● 0 2 4 6 8 10 12 14 16 18 20 22 24 26 28 30 Lösung: Belegung ist nicht möglich 0 2 4 6 8 10 12 14 16 18 20 22 24 26 28 30 BB AA 4 MiB 8 MiB 8 MiB 4 MiB Probeklausur 15 3b) Buddy-Verfahren (4 Punkte) Szenario 4: Prozess F belegt 7 MiB (aufgerundet 8 MiB) AAAABB ● 0 2 4 6 8 10 12 14 16 18 20 22 24 26 28 30 Lösung: AAAA 0 246 8 10 12 14 16 18 20 22 24 26 28 30 BB FFFF Probeklausur 16 4a) Block-Buffer-Cache (3 Punkte) Nennen und erläutern Sie drei Ereignisse, die das Rückschreiben des Block-Buffer-Caches auslösen. Wenn kein freier Puffer mehr vorhanden ist Bei Aufruf des Systemaufrufes sync() Regelmäßig vom System Nach jedem Schreibaufruf im Modus O_SYNC ● – – – – Probeklausur 17 4b) Kontinuierliche Speicherung (2 Punkte) Datei wird in Blöcken mit aufeinander folgenden Blocknummern gespeichert Vorteile: Zugriff auf alle Blöcke mit minimaler Positionierungszeit Schneller direkter Zugriff auf bestimmte Dateipositionen Gut geeignet für nicht-modifizierbare Datenträger (z.B. optische Medien) ● ● – – – ● – – – – – Nachteile: Aufwändiges Finden von freiem, aufeinanderfolgendem Speicherplatz Fragmentierungsproblem Dateigröße von neuen Dateien oft nicht im Voraus bekannt Erweitern bestehender Daten komplex Umkopieren notwendig, wenn hinter Daten kein freier Platz ist Probeklausur 18 4c) IO-Scheduling (4,5 Punkte) L1={1,4,7,2} L2={3,6,0} L3={5,2} Sofort bekannt Nach 3 Ops Nach 6 Ops bekannt bekannt ● Bitte tragen Sie hier die Reihenfolge der gelesenen Spuren für einen I/O-Scheduler, der nach der Fahrstuhl (Elevator) Strategie arbeitet, ein: Probeklausur 19 4c) IO-Scheduling (4,5 Punkte) I/O-Anfragen: 1, 4, 7, 2 Position des Kopfes T=0 0 1 2 3 4 5 6 7 8 Probeklausur 20 4c) IO-Scheduling (4,5 Punkte) I/O-Anfragen: 4, 7, 2 Position des Kopfes T=1 0 1 2 3 4 5 6 7 8 1 Probeklausur 21 4c) IO-Scheduling (4,5 Punkte) I/O-Anfragen: 4, 7 Position des Kopfes T=2 0 1 2 3 4 5 6 7 8 1 2 Probeklausur 22 4c) IO-Scheduling (4,5 Punkte) I/O-Anfragen: 7 Position des Kopfes T=3 0 1 2 3 4 5 6 7 8 1 2 4 Probeklausur 23 4c) IO-Scheduling (4,5 Punkte) I/O-Anfragen: 7, 3, 6, 0 Position des Kopfes T=3 0 1 2 3 4 5 6 7 8 1 2 4 Probeklausur 24 4c) IO-Scheduling (4,5 Punkte) I/O-Anfragen: 7, 3, 0 Position des Kopfes T=4 0 1 2 3 4 5 6 7 8 1 2 4 6 Probeklausur 25 4c) IO-Scheduling (4,5 Punkte) I/O-Anfragen: 3, 0 Position des Kopfes T=5 0 1 2 3 4 5 6 7 8 1 2 4 6 7 Probeklausur 26 4c) IO-Scheduling (4,5 Punkte) I/O-Anfragen: 0 Position des Kopfes T=6 0 1 2 3 4 5 6 7 8 1 2 4 6 7 3 Probeklausur 27 4c) IO-Scheduling (4,5 Punkte) I/O-Anfragen: 0, 5, 2 Position des Kopfes T=6 0 1 2 3 4 5 6 7 8 1 2 4 6 7 3 Probeklausur 28 4c) IO-Scheduling (4,5 Punkte) I/O-Anfragen: 0, 5 Position des Kopfes T=7 0 1 2 3 4 5 6 7 8 1 2 4 6 7 3 2 Probeklausur 29 4c) IO-Scheduling (4,5 Punkte) I/O-Anfragen: 5 Position des Kopfes T=8 0 1 2 3 4 5 6 7 8 1 2 4 6 7 3 2 0 Probeklausur 30 4c) IO-Scheduling (4,5 Punkte) I/O-Anfragen: Position des Kopfes T=9 0 1 2 3 4 5 6 7 8 1 2 4 6 7 3 2 0 5 Probeklausur 31 Auswertung Bitte schnell einmal die Punkte zusammenzählen ... Notenspiegel: Punkte Note 38,5–45 1 33,5–38 2 28–33 3 22,5–27,5 4 0–22 5 ● ● Probeklausur 32 Weitere Hinweise zur Vorbereitung ● – ● ● ● Literatur zur Lehrveranstaltung durchlesen BS-Forum nutzen Inhalt der Folien lernen Klassifizieren: Was muss ich lernen? Was muss ich begreifen? Übungsaufgaben verstehen, C und UNIX „können“ – ● – – AsSESS-System bleibt mindestens bis zur Klausur offen bei Fragen zur Korrektur melden Am besten die Aufgaben noch einmal lösen Optionale Zusatzaufgaben bearbeiten Probeklausur 33 Empfohlene Literatur [1] A. Silberschatz et al. Operating System Concepts. Wiley, 2004. ISBN 978-0471694663 [2] A. Tanenbaum: Modern Operating Systems (2nd ed.). Prentice Hall, 2001. ISBN 0-13-031358-0 [3] B. W. Kernighan, D. M. Ritchie. The C Programming Language. Prentice-Hall, 1988. ISBN 0-13-110362-8 (paperback) 0-13-110370-9 (hardback) [4] R. Stevens, Advanced Programming in the UNIX Environment, Addison-Wesley, 2005. ISBN 978-0201433074 Viel Erfolg bei der Klausur! Probeklausur 34 Betriebssysteme Probeklausur https://ess.cs.tu-dortmund.de/DE/Teaching/SS2018/BS/ Olaf Spinczyk olaf.spinczyk@tu-dortmund.de https://ess.cs.tu-dortmund.de/~os AG Eingebettete Systemsoftware Informatik 12, TU Dortmund Ablauf Probeklausur (45 Minuten) Besprechung der Aufgaben Auswertung Weitere Hinweise zur Vorbereitung ● ● ● ● Probeklausur 2 Probeklausur ... in (fast) allen Belangen realistisch: Art der Aufgaben ● ● – ● – – – ● Die Klausur wird nicht eingesammelt. Probeklausur Auswahl aus dem gesamten Inhalt der Veranstaltung Betriebssystemgrundlagen und UNIX-Systemprogrammierung in C alle Vorlesungen und Übungen sind relevant Umfang kürzer als das „Original“: 45 (statt 60) Minuten Durchführung keine Hilfsmittel erlaubt (keine Spickzettel, Bücher, ...) bitte still arbeiten jeder für sich – ● ● 3 UNIX Shell 1) “$ ls > Dateien.txt” Was bewirkt die Ausführung dieses Kommandos in einer UNIX-Shell?
Probeklausur
4

UNIX Shell
1) “$ ls > Dateien.txt” Was bewirkt die Ausführung dieses Kommandos in einer UNIX-Shell?
Leitet die Ausgabe von „ls“ (alle Dateien im aktuellen Arbeitsverzeichnis) in die Datei Dateien.txt um.
2) „$ cat Dateien.txt | grep txt“ (3 Punkte) Was bewirkt die Ausführung dieses Kommandos in einer UNIX-Shell?
Probeklausur
6

1a) Prozess-Scheduling (FCFS)
Prozess
P1
P2
P3
Ankunftszeit
20 ms
30 ms
CPU-Zeit E/A-Zeit
40 ms 20 ms 30 ms
20 ms 10 ms 40 ms
0ms
Probeklausur
8

1b) Prozesserzeugung (7 Punkte)
● WasgibtdasfolgendeProgrammaus?
1 2 3 4 5 6 7 8 9
10
11
12
13
14
15
16
17
#define GALAXIES_BOUND 10 int worlds, galaxies; pthread_t demiurge;
void* populateGalaxies(void* param) { inti;
for(i=0;i Verklemmung
Probeklausur Betriebssysteme 2020
20

2 – Synchronisation und Verklemmung
c) Prozessverläufe
●
– – – – –
Kann in diesem Prozessverlaufsdiagramm eine Verklemmung auftreten?
Betriebsmittel werden schrittweise belegt
P1 belegt L und R
P2 blockiert an L und R
Sobald P1 die Betriebsmittel freigibt, läuft P2 weiter Circular Wait wird nicht erfüllt => Keine Verklemmung
Probeklausur Betriebssysteme 2020
21
Fortschritt Betriebsmittel Prozess P1
Fortschritt
Prozess P2
L R
L R
Betriebsmittel

3 – Speicherverwaltung + virt. Speicher
a) Speichersegmentierung
Anfrage: 0x0000BEEF
Segmenttabelle
●
00 00BEEF
logische Adresse
Startadresse
Länge
0010
0000 00E016
21 20FF16
0110
B542 000016
01 000016
0210
0515 000016
20 000016
0310
0006 000016
00 FFFF16
…
2810
0001 000016
FF FFFF16
Probeklausur Betriebssysteme 2020
22
physikalische Adresse

3 – Speicherverwaltung + virt. Speicher
a) Speichersegmentierung
Anfrage: 0x0000BEEF
●
Segmenttabellen- basisregister
Segmenttabelle
+
00 00BEEF
logische Adresse
Startadresse
Länge
0010
0000 00E016
21 20FF16
0110
B542 000016
01 000016
0210
0515 000016
20 000016
0310
0006 000016
00 FFFF16
…
2810
0001 000016
FF FFFF16
< ja Trap: Schutzverletzung + Probeklausur Betriebssysteme 2020 23 physikalische Adresse 3 – Speicherverwaltung + virt. Speicher a) Speichersegmentierung Anfrage: 0x0000BEEF ● Segmenttabellen- basisregister Segmenttabelle + 00 00BEEF logische Adresse Startadresse Länge 0010 0000 00E016 21 20FF16 0110 B542 000016 01 000016 0210 0515 000016 20 000016 0310 0006 000016 00 FFFF16 ... 2810 0001 000016 FF FFFF16 < ja Trap: Schutzverletzung + 0000BFCF physikalische Adresse Probeklausur Betriebssysteme 2020 24 3 – Speicherverwaltung + virt. Speicher a) Speichersegmentierung – forts. Anfrage: 0x1CEB00DA Segmenttabellen- ● basisregister Segmenttabelle + 1C EB00DA logische Adresse Startadresse Länge 0010 0000 00E016 21 20FF16 0110 B542 000016 01 000016 0210 0515 000016 20 000016 0310 0006 000016 00 FFFF16 ... 2810 0001 000016 FF FFFF16 < ja Trap: Schutzverletzung + 00EC00DA physikalische Adresse Probeklausur Betriebssysteme 2020 25 3 – Speicherverwaltung + virt. Speicher a) Speichersegmentierung – forts. Anfrage: 0x1CEB00DA Segmenttabellen- ● basisregister Segmenttabelle + 1C EB00DA logische Adresse Startadresse Länge 0010 0000 00E016 21 20FF16 0110 B542 000016 01 000016 0210 0515 000016 20 000016 0310 0006 000016 00 FFFF16 ... 2810 0001 000016 FF FFFF16 < ja Trap: Schutzverletzung + 00EC00DA physikalische Adresse Probeklausur Betriebssysteme 2020 26 0 2 4 6 8 10 12 14 16 18 20 22 24 26 28 30 A A A A 3 – Speicherverwaltung + virt. Speicher b) Buddy-Verfahren Prozess B: Prozess B belegt 9 MiB ● Probeklausur Betriebssysteme 2020 27 0 2 4 6 8 10 12 14 16 18 20 22 24 26 28 30 A A A A 0 2 4 6 8 10 12 14 16 18 20 22 24 26 28 30 A A A A B B B B B B B B 3 – Speicherverwaltung + virt. Speicher b) Buddy-Verfahren Prozess B: Prozess B belegt 9 MiB ● Lösung: Probeklausur Betriebssysteme 2020 28 0 2 4 6 8 10 12 14 16 18 20 22 24 26 28 30 A A A A B B B B B B B B 3 – Speicherverwaltung + virt. Speicher b) Buddy-Verfahren Prozess C: Prozess C belegt 1 MiB ● Probeklausur Betriebssysteme 2020 29 0 2 4 6 8 10 12 14 16 18 20 22 24 26 28 30 A A A A B B B B B B B B 0 2 4 6 8 10 12 14 16 18 20 22 24 26 28 30 A A A A C B B B B B B B B 3 – Speicherverwaltung + virt. Speicher b) Buddy-Verfahren Prozess C: Prozess C belegt 1 MiB ● Lösung: Probeklausur Betriebssysteme 2020 30 0 2 4 6 8 10 12 14 16 18 20 22 24 26 28 30 A A A A C B B B B B B B B 3 – Speicherverwaltung + virt. Speicher b) Buddy-Verfahren Prozess D: Prozess D belegt 6 MiB ● Probeklausur Betriebssysteme 2020 31 0 2 4 6 8 10 12 14 16 18 20 22 24 26 28 30 A A A A C B B B B B B B B Belegung ist nicht möglich 0 2 4 6 8 10 12 14 16 18 20 22 24 26 28 30 A A A A C B B B B B B B B 3 – Speicherverwaltung + virt. Speicher b) Buddy-Verfahren Prozess D: Prozess D belegt 6 MiB ● Lösung: Probeklausur Betriebssysteme 2020 32 3 – Speicherverwaltung + virt. Speicher c) LRU (Least Recently Used) Referenzfolge 5 3 5 1 2 5 4 6 1 Hauptspeicher Kachel 1 5 Kachel 2 Kachel 3 Kontrollzustände Kachel 1 0 Kachel 2 Kachel 3 Probeklausur Betriebssysteme 2020 33 3 – Speicherverwaltung + virt. Speicher c) LRU (Least Recently Used) Referenzfolge 5 3 5 1 2 5 4 6 1 Hauptspeicher Kachel 1 5 5 Kachel 2 3 Kachel 3 Kontrollzustände Kachel 1 0 1 Kachel 2 0 Kachel 3 Probeklausur Betriebssysteme 2020 34 3 – Speicherverwaltung + virt. Speicher c) LRU (Least Recently Used) Referenzfolge 5 3 5 1 2 5 4 6 1 Hauptspeicher Kachel 1 5 5 5 Kachel 2 3 3 Kachel 3 Kontrollzustände Kachel 1 0 1 0 Kachel 2 0 1 Kachel 3 Probeklausur Betriebssysteme 2020 35 3 – Speicherverwaltung + virt. Speicher c) LRU (Least Recently Used) Referenzfolge 5 3 5 1 2 5 4 6 1 Hauptspeicher Kachel 1 5 5 5 5 Kachel 2 3 3 3 Kachel 3 1 Kontrollzustände Kachel 1 0 1 0 1 Kachel 2 0 1 2 Kachel 3 0 Probeklausur Betriebssysteme 2020 36 3 – Speicherverwaltung + virt. Speicher c) LRU (Least Recently Used) Referenzfolge 5 3 5 1 2 5 4 6 1 Hauptspeicher Kachel 1 5 5 5 5 5 Kachel 2 3 3 3 2 Kachel 3 1 1 Kontrollzustände Kachel 1 0 1 0 1 2 Kachel 2 0 1 2 0 Kachel 3 0 1 Probeklausur Betriebssysteme 2020 37 3 – Speicherverwaltung + virt. Speicher c) LRU (Least Recently Used) Referenzfolge 5 3 5 1 2 5 4 6 1 Hauptspeicher Kachel 1 5 5 5 5 5 5 Kachel 2 3 3 3 2 2 Kachel 3 1 1 1 Kontrollzustände Kachel 1 0 1 0 1 2 0 Kachel 2 0 1 2 0 1 Kachel 3 0 1 2 Probeklausur Betriebssysteme 2020 38 3 – Speicherverwaltung + virt. Speicher c) LRU (Least Recently Used) Referenzfolge 5 3 5 1 2 5 4 6 1 Hauptspeicher Kachel 1 5 5 5 5 5 5 5 Kachel 2 3 3 3 2 2 2 Kachel 3 1 1 1 4 Kontrollzustände Kachel 1 0 1 0 1 2 0 1 Kachel 2 0 1 2 0 1 2 Kachel 3 0 1 2 0 Probeklausur Betriebssysteme 2020 39 3 – Speicherverwaltung + virt. Speicher c) LRU (Least Recently Used) Referenzfolge 5 3 5 1 2 5 4 6 1 Hauptspeicher Kachel 1 5 5 5 5 5 5 5 5 Kachel 2 3 3 3 2 2 2 6 Kachel 3 1 1 1 4 4 Kontrollzustände Kachel 1 0 1 0 1 2 0 1 2 Kachel 2 0 1 2 0 1 2 0 Kachel 3 0 1 2 0 1 Probeklausur Betriebssysteme 2020 40 3 – Speicherverwaltung + virt. Speicher c) LRU (Least Recently Used) Referenzfolge 5 3 5 1 2 5 4 6 1 Hauptspeicher Kachel 1 5 5 5 5 5 5 5 5 1 Kachel 2 3 3 3 2 2 2 6 6 Kachel 3 1 1 1 4 4 4 Kontrollzustände Kachel 1 0 1 0 1 2 0 1 2 0 Kachel 2 0 1 2 0 1 2 0 1 Kachel 3 0 1 2 0 1 2 Probeklausur Betriebssysteme 2020 41 4 - Ein-/Ausgabe und Dateisysteme a) Block-Buffer-Cache Nennen und erläutern Sie drei Ereignisse, die das Rückschreiben des Block-Buffer-Caches auslösen. ● Probeklausur Betriebssysteme 2020 42 4 - Ein-/Ausgabe und Dateisysteme a) Block-Buffer-Cache Nennen und erläutern Sie drei Ereignisse, die das Rückschreiben des Block-Buffer-Caches auslösen. Wenn kein freier Puffer mehr vorhanden ist Bei Aufruf des Systemaufrufes sync() Regelmäßig vom System Nach jedem Schreibaufruf im Modus O_SYNC ● – – – – Probeklausur Betriebssysteme 2020 43 4 - Ein-/Ausgabe und Dateisysteme b) Kontinuierliche Speicherung Nennen Sie je einen Vor- und einen Nachteil der kontinuierlichen Speicherung von Dateien: Probeklausur Betriebssysteme 2020 44 4 - Ein-/Ausgabe und Dateisysteme b) Kontinuierliche Speicherung Nennen Sie je einen Vor- und einen Nachteil der kontinuierlichen Speicherung von Dateien: Datei wird in Blöcken mit aufsteigenden Blocknummern gespeichert Vorteile: Zugriff auf alle Blöcke mit minimaler Positionierungszeit Schneller direkter Zugriff auf bestimmte Dateipositionen Gut geeignet für nicht-modifizierbare Datenträger (z.B. optische Medien) ● ● – – – ● – – – – – Nachteile: Aufwändiges Finden von freiem, aufeinander folgendem Speicherplatz Fragmentierungsproblem Dateigröße von neuen Dateien oft nicht im Voraus bekannt Erweitern bestehender Daten komplex Umkopieren notwendig, wenn hinter Daten kein freier Platz ist Probeklausur Betriebssysteme 2020 45 4 - Ein-/Ausgabe und Dateisysteme c) I/O-Scheduling L1={1,4,7,2} L2={3,6,0} L3={5,2} ● Bitte tragen Sie hier die Reihenfolge der gelesenen Spuren für einen I/O-Scheduler, der nach der Fahrstuhl (Elevator) Strategie arbeitet, ein: Sofort bekannt Nach 3 Operationen bekannt Nach 6 Operationen bekannt Probeklausur Betriebssysteme 2020 46 4 - Ein-/Ausgabe und Dateisysteme c) I/O-Scheduling I/O-Anfragen: 1, 4, 7, 2 Position des Kopfes 0 1 2 3 4 5 6 7 8 T=0 Probeklausur Betriebssysteme 2020 47 4 - Ein-/Ausgabe und Dateisysteme c) I/O-Scheduling I/O-Anfragen: 4, 7, 2 Position des Kopfes 0 1 2 3 4 5 6 7 8 T=1 1 Probeklausur Betriebssysteme 2020 48 4 - Ein-/Ausgabe und Dateisysteme c) I/O-Scheduling I/O-Anfragen: 4, 7 Position des Kopfes 0 1 2 3 4 5 6 7 8 T=2 1 2 Probeklausur Betriebssysteme 2020 49 4 - Ein-/Ausgabe und Dateisysteme c) I/O-Scheduling I/O-Anfragen: 7 Position des Kopfes 0 1 2 3 4 5 6 7 8 T=3 1 2 4 Probeklausur Betriebssysteme 2020 50 4 - Ein-/Ausgabe und Dateisysteme c) I/O-Scheduling I/O-Anfragen: 7, 3, 6, 0 Neue Anfragen bekannt Position des Kopfes 0 1 2 3 4 5 6 7 8 T=3 1 2 4 Probeklausur Betriebssysteme 2020 51 4 - Ein-/Ausgabe und Dateisysteme c) I/O-Scheduling I/O-Anfragen: 7, 3, 0 T=4 0 1 2 3 4 5 6 7 8 Position des Kopfes 1 2 4 6 Probeklausur Betriebssysteme 2020 52 4 - Ein-/Ausgabe und Dateisysteme c) I/O-Scheduling I/O-Anfragen: 3, 0 T=5 0 1 2 3 4 5 6 7 8 Position des Kopfes 1 2 4 6 7 Probeklausur Betriebssysteme 2020 53 4 - Ein-/Ausgabe und Dateisysteme c) I/O-Scheduling I/O-Anfragen: 0 Position des Kopfes 0 1 2 3 4 5 6 7 8 T=6 1 2 4 6 7 3 Probeklausur Betriebssysteme 2020 54 4 - Ein-/Ausgabe und Dateisysteme c) I/O-Scheduling I/O-Anfragen: 0, 5, 2 Position des Kopfes 0 1 2 3 4 5 6 7 8 T=6 Neue Anfragen bekannt 1 2 4 6 7 3 Probeklausur Betriebssysteme 2020 55 4 - Ein-/Ausgabe und Dateisysteme c) I/O-Scheduling I/O-Anfragen: 0, 5 Position des Kopfes 0 1 2 3 4 5 6 7 8 T=7 1 2 4 6 7 3 2 Probeklausur Betriebssysteme 2020 56 4 - Ein-/Ausgabe und Dateisysteme c) I/O-Scheduling I/O-Anfragen: 5, Position des Kopfes 0 1 2 3 4 5 6 7 8 T=8 1 2 4 6 7 3 2 0 Probeklausur Betriebssysteme 2020 57 4 - Ein-/Ausgabe und Dateisysteme c) I/O-Scheduling I/O-Anfragen: T=9 Position des Kopfes 0 1 2 3 4 5 6 7 8 1 2 4 6 7 3 2 0 5 Probeklausur Betriebssysteme 2020 58 Auswertung Punkte zusammenzählen (soweit nach eigener Bewertung von Teilpunkten möglich) Notenspiegel: Punkte Note 38,5–45 1 33,5–38 2 28–33 3 22,5–27,5 4 0–22 5 ● ● Probeklausur Betriebssysteme 2020 59 Weitere Hinweise zur Vorbereitung Inhalt der Folien lernen Klassifizieren: Was muss ich lernen? Was muss ich begreifen? Übungsaufgaben verstehen, C und UNIX „können“ ● – ● ● ● ergänzend Literatur zur Lehrveranstaltung heranziehen HelpDesk nutzen (Uhrzeiten und Links siehe BS-Webseite) – ● – – Am besten die Aufgaben noch einmal lösen Optionale Zusatzaufgaben bearbeiten ASSESS-System bleibt mindestens bis zur zweiten Klausur offen bei Fragen zur Korrektur melden Probeklausur Betriebssysteme 2020 60 Empfohlene Literatur [1] A. Silberschatz et al. Operating System Concepts. Wiley, 2004. ISBN 978-0471694663 [2] A. Tanenbaum: Modern Operating Systems (2nd ed.). Prentice Hall, 2001. ISBN 0-13-031358-0 [3] B. W. Kernighan, D. M. Ritchie. The C Programming Language. Prentice-Hall, 1988. ISBN 0-13-110362-8 (paperback) 0-13-110370-9 (hardback) [4] R. Stevens, Advanced Programming in the UNIX Environment, Addison-Wesley, 2005. ISBN 978-0201433074 Viel Erfolg bei der Klausur! Probeklausur Betriebssysteme 2020 61

Related Posts