Betriebssysteme (BS)
Probeklausur
Olaf Spinczyk und Alexander Lochmann Arbeitsgruppe Eingebettete Systemsoftware
Lehrstuhl für Informatik 12 TU Dortmund
http://ess.cs.uni-dortmund.de/
http://ess.cs.tu-dortmund.de/DE/Teaching/SS2015/BS/
1
Ankündigung
Rechnerü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 Übungen sind relevant
Umfang
● kürzer als das „Original“: ca. 40–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. 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) Entitä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 zunächst auf denselbem BSS-, Daten-, und Heap-Segment – bis einer der beiden etwas verändert
●
●
●
Klausurvorbereitungsveranstaltung 06.07.2015 8
1 – Prozesse und Scheduling
c) Scheduling
X X
SRTF → Übungsaufgabe A1, Theorieaufgabe 1 E/A-lastige Prozesse geben die CPU sofort ab und
kommen ans Ende der ready-Liste
Prä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 ausgefü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 ausgeführt werden dü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() können als gegeben angesehen werden und mü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) Erlä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 erlä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 rückforderbar 4) Zirkuläres Warten („circular wait“)
– Eine geschlossene Kette wechselseitig wartender Prozesse
●
Klausurvorbereitungsveranstaltung 06.07.2015 13
2 – Synchronisation und Verklemmung
d) Nennen Sie eine Möglichkeit zur Verklemmungsvorbeugung (deadlock prevention) ● indirekte Methoden entkräften eine der Bedingungen 1–3
– nicht-blockierende Verfahren verwenden
– Betriebsmittelanforderungen unteilbar (atomar) auslegen
– Betriebsmittelentzug durch Virtualisierung ermöglichen – virtueller Speicher, virtuelle Geräte, virtuelle Prozessoren
● direkte Methoden entkräften Bedingung 4
– lineare/totale Ordnung von Betriebsmittelklassen einfü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 können
● Lösung des Fragmentierungsproblems
● keine Kompaktifizierung mehr nö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
Kontrollzustä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 Leseaufträge für eine bestimmte Spur. Die Leseaufträge in L1 sind dem I/O-Scheduler bereits bekannt. Nach einem
bearbeiteten Auftrag erhält er die Aufträge in L2. Nach
weiteren drei (d.h. nach insgesamt vier) bearbeiteten Aufträgen erhält er die Aufträge in L3. Zu Beginn befindet
sich der Schreib-/Lesekopf ü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 fü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 Blö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 Plattenblöcke)
- Fragmentierungsproblem (Verschnitt: nicht nutzbare Plattenblöcke; siehe auch Speicherverwaltung)
- Größe bei neuen Dateien oft nicht im Voraus bekannt
- Erweitern ist problematisch
- Umkopieren, falls kein freier angrenzender Block mehr verfü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
Datenblö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 lässt sich die maximale Dateigröße für dieses Dateisystem berechnen, wenn die Blockgröße 1024 Bytes beträgt und für die Speicherung eines Blockverweises 4 Bytes benötigt werden.
Hinweis: Es ist nicht erforderlich die Zahl auszurechnen. Beschreiben Sie den Rechenweg Schritt für Schritt oder geben Sie eine Formel an.
●
Klausurvorbereitungsveranstaltung 06.07.2015 36
4 - Ein-/Ausgabe und Dateisysteme
B: Maximale Anzahl der Blöcke
BG: Blockgröße
D: Maximale Dateigröße (gesucht)
I: Anzahl der Verweise in indirekten Blö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 müssen mehrere Blöcke gelesen werden
Klausurvorbereitungsveranstaltung 06.07.2015 38
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
● ●
Klausurvorbereitungsveranstaltung 06.07.2015 39
Weitere Hinweise zur Vorbereitung
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
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