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 Übungen sind relevant
Umfang
kürzer als das „Original“: 45 (statt 60) Minuten
Durchführung
keine Hilfsmittel erlaubt (keine Spickzettel, Bücher, …) bitte still arbeiten
jeder fü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 verdrängt
● Der nächste Prozess wird gemäß 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
Änderungen sind unabhängig voneinander
● pthread_create erzeugt leichtgewichtige POSIX-Threads
Variable “pferd” liegt im gemeinsam genutzten Datensegment Beide Threads verä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 erfüllt sein müssen, damit es überhaupt zu einer Verklemmung kommen kann, und erklä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 rückforderbar
Probeklausur
9
3a) Adressabbildung (4 Punkte)
In einem System mit Seitenadressierung (paging) befindet sich die Seitenkacheltabelle im unten angegebenen Zustand. Die Adresslänge beträgt 16 Bit, wovon 12 Bit für den Offset innerhalb der Seite verwendet werden (Seitengröß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
Lö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
Lö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
Lösung:
Belegung ist nicht mö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
Lö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 erläutern Sie drei Ereignisse, die das Rückschreiben des Block-Buffer-Caches auslösen.
Wenn kein freier Puffer mehr vorhanden ist Bei Aufruf des Systemaufrufes sync() Regelmäßig vom System
Nach jedem Schreibaufruf im Modus O_SYNC
●
– – – –
Probeklausur
17
4b) Kontinuierliche Speicherung (2 Punkte)
Datei wird in Blöcken mit aufeinander folgenden Blocknummern gespeichert
Vorteile:
Zugriff auf alle Blöcke mit minimaler Positionierungszeit
Schneller direkter Zugriff auf bestimmte Dateipositionen
Gut geeignet für nicht-modifizierbare Datenträger (z.B. optische Medien)
●
●
– – –
●
– – – – –
Nachteile:
Aufwändiges Finden von freiem, aufeinanderfolgendem Speicherplatz Fragmentierungsproblem
Dateigröß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 fü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 zusammenzä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?
Übungsaufgaben verstehen, C und UNIX „können“
–
●
– –
AsSESS-System bleibt mindestens bis zur Klausur offen bei Fragen zur Korrektur melden
Am besten die Aufgaben noch einmal lö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