CS计算机代考程序代写 cache Betriebssysteme

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 Ü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.

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]

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 enthält?
– Der Inhalt der Datei wird gelöscht und die Datei enthält danach den String “”, also keine Zeichen.

1b) Allgemeine Fragen
2. Prozesse vs. Funktionen (1.5 Punkte) Erklä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 Prozessausführung an eine Funktion, führt diese aus und springt anschließend an die aufrufende Funktion zurück. Es findet keine parallele Ausfü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 Rückgabewert der Prozesse noch benö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 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 schrittweise belegbar
– Kein Entzug von Betriebsmitteln (no preemption)
die umstrittenen Betriebsmittel sind nicht rückforderbar

die umstrittenen Betriebsmittel sind nur unteilbar nutzbar

– Nachforderung von Betriebsmitteln (hold and wait)

3a) Platzierung/Ersetzung (4 Punkte)
Erläutern Sie den Unterschied zwischen der Platzierungsstrategie (placement policy) und der Ersetzungsstrategie (replacement policy)
– Die Platzierungsstrategie bestimmt woher benötigter Speicher genommen wird. (z.B. zur Minimierung des Verschnitts )
First/Last Fit Best Fit
Worst Fit Buddy-Verfahren


Die Ersetzungsstrategie bestimmt welche Speicherinhalte verdrängt werden sollen, falls kein freier Speicher mehr zu Verfügung steht.
LRU – Least recently used FIFO – First in First out Second Chance
● ● ● ●
● ● ●

3b) Speichersegmentierung (4 Punkte)
Geben Sie für die Speicheranfragen 0x1000 A100 und
0x030B 5000 die physikalische Adresse unter Anwendung des Speichersegmentierungsverfahrens an.
Die höchstwertigen 8 Bit der logischen Adresse geben die Position innerhalb der Segementtabelle an. Löst eine Speicheranfrage eine Zugriffsverletzung aus, so machen Sie dies bitte kenntlich.

Startadresse Lä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
Lä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 Lä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 Lö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 Lö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 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 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 Lö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 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 ● 4b) Kontinuierliche Speicherung (2 Punkte) Datei wird in Blöcken mit aufsteigenenden 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 ● ● ● 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: Ü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 Ü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 Ü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 Ü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 Ü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 Ü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 Ü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 Ü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 Ü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 Ü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 Ü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 Ü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 Ü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 Übung 5 - Sicherheit 33 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 ● ● Weitere Hinweise zur Vorbereitung Inhalt der Folien lernen Übungsaufgaben verstehen, C und UNIX „kö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 lö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!