1 Prozesse und Scheduling (13 Punkte)
a) Round Robin (6 Punkte) Ein Betriebssystem verwaltet die drei Prozesse P1, P2 und P3. Die Prozesse treen in dieser Reihenfolge im System ein und sind alle zum Zeitpunkt t=0 rechenbereit. Die Be- dienzeiten der Prozesse und die Zeitpunkte und Dauer von E/A-Operationen sind in der folgenden Tabelle angegeben:
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
Bei der Bedienzeit handelt es sich um die reine Rechenzeit. Für die Gesamtzeit kommt noch die Dauer der E/A-Operationen hinzu. Der E/A-Zeitpunkt ist relativ zur Bedienzeit angegeben. Prozess P1 beginnt also nach 20 ms Rechenzeit mit seinen E/A-Operationen, Prozess P2 wird nach seinen ersten 30 ms blockiert, etc.
Zeichnen Sie in das folgende Gantt-Diagramm ein, wie die drei Prozesse P1, P2 und P3 bei Scheduling nach der Round Robin-Strategie mit einer Zeitscheibendauer von 40 ms abgearbeitet werden. Jeder Prozess führt genau einen E/A-Vorgang durch. Zeitpunkt und Dauer sind in der Tabelle angegeben. Die Prozessumschaltzeit kann vernachlässigt werden. Markieren Sie in dem folgenden Diagramm die Prozesszustände entsprechend der Legende.
Hinweis: Die ersten 20 ms sind bereits fertig ausgefüllt.
P1 P2 P3
Legende:
Running Ready Blocked Terminated
t[ms] 0 100 200 300
Probeklausur Betriebssysteme, 25./26.07.2017 Seite 1 von 5
b) Prozesserzeugung (7 Punkte) Was geben die folgenden C-Programme aus? Wieso ist die Ausgabe unterschiedlich? Fehlerabfragen und die #include-Zeilen zur Einbindung der Systemheader wurden der Einfachheit halber weggelassen. Gehen Sie davon aus, dass alle Systemaufrufe fehlerfrei abgearbeitet werden und keine Race Condition auftritt.
1 int pferd; 1 int pferd ; 22
3 void∗ erzeugePferd(void∗ param) { 3
4 pferd++; 4
5 printf(“%d\n”,pferd); 5 66
7 return NULL; 7 8} 8} 99
10
11
12
13
14
15
16 17}
int main(void) { pferd = 42;
18
19 }
Ausgabe:
return
erzeugePferd (NULL); 0;
10 int main(void) {
11 pferd = 42; 12 pthread_t id ;
if (fork() == 0) { 13
}else{
erzeugePferd (NULL);
14 pthread_create(&id , 15 NULL ,
16 erzeugePferd , 17NULL);
18 erzeugePferd (NULL); 19 return 0;
20 }
Ausgabe:
void∗ erzeugePferd(void∗ param) { pferd++;
p r i n t f ( “%d \ n ” , p f e r d ) ; pthread_exit (NULL);
Probeklausur Betriebssysteme, 25./26.07.2017
Seite 2 von 5
2 Synchronisation und Verklemmungen (14,5 Punkte)
a) Gegeben ist ein Programm, das mittels zwei Semaphoren einen Schreiber gegen mehrere Leser absi- chern soll. Zu Beginn ist der gemeinsame Speicher leer. Initialisieren Sie die Variable readcount und die Semaphoren mutex und wrt geeignet. Verwenden Sie die Semaphor-Operationen signal und wait, um die Prozesse gegeneinander abzusichern. Es soll möglich sein, dass mehrere Leser gleichzeitig arbeiten, der Schreiber währenddessen aber blockiert ist. Ebenso dürfen Leseprozesse nur arbeiten, wenn kein Schreiber aktiv ist. (10 Punkte)
/* Gemeinsamer Speicher */
Semaphore mutex = 0 Semaphore wrt = 1 int readcount = 1
; ;
;
void schreiber() {
schreibe_Daten();
}
void leser() {
readcount =
if ( readcount ==
}
lese_Daten();
readcount =
if ( readcount ==
}
}
) {
) {
b) Verklemmungen (4,5 Punkte) Wenn eine geschlossene Kette wechselseitig wartender Prozesse exis- tiert (circular wait, also ein Zyklus im Betriebsmittelbelegungsgraphen), liegt eine Verklemmung vor. 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.
Probeklausur Betriebssysteme, 25./26.07.2017 Seite 3 von 5
3 Speicherverwaltung und Virtueller Speicher (8 Punkte)
a) Adressabbildung (4 Punkte) In einem System mit Seitenadressierung (paging) bendet sich die Sei- tenkacheltabelle im unten angegebenen Zustand. Die Adresslänge beträgt 16Bit, wovon 12Bit für den Oset innerhalb der Seite verwendet werden (Seitengröÿe: 4096 Bytes). Bilden Sie die logischen Adressen 6AB116 und F1B716 auf ihre physikalischen Adressen ab. (Hinweis: Eine Hexadezimalzier stellt immer genau vier Bit der Adresse dar.)
Seitennummer Startadresse
0 F00016 1 300016 2 800016 3 100016 4 C00016 5 200016 6 400016 7 B00016
… … 15 500016
logische Adresse: 6AB116 → physikalische Adresse:
logische Adresse: F1B716 → physikalische Adresse:
b) Buddy-Verfahren (4 Punkte) Die jeweils zweite Zeile der folgenden Szenarien zeigt die momentane Speicherbelegung eines Arbeitsspeichers der Gröÿe 32MiB. Ergänzen Sie die folgenden Tabellen um Markierungen für die vorgegebenen Anfragen. Nutzen Sie das Buddyverfahren zur dynamischen Spei- cherverwaltung.
Hinweis: Falls eine Belegung/Freigabe nicht erfüllt werden kann, kennzeichnen Sie die betreende Zeile geeignet.
Szenario 1: Prozess C belegt 3 MiB
0 2 4 6 8 10 12 14 16 18 20 22 24 26 28 30
AAAA BB Szenario 2: Prozess D belegt 12 MiB
0 2 4 6 8 10 12 14 16 18 20 22 24 26 28 30
AA
Szenario 3: Prozess E belegt 14 MiB
0 2 4 6 8 10 12 14 16 18 20 22 24 26 28 30
BB AA Szenario 4: Prozess F belegt 7 MiB
0 2 4 6 8 10 12 14 16 18 20 22 24 26 28 30 AAAABB
Probeklausur Betriebssysteme, 25./26.07.2017 Seite 4 von 5
4 Ein-/Ausgabe und Dateisysteme (9,5 Punkte)
a) Block-Buer-Cache (3 Punkte) Nennen und erläutern Sie drei Ereignisse, die das Rückschreiben des Block-Buer-Caches auslösen.
b) Kontinuierliche Speicherung (2 Punkte) Nennen Sie je einen Vor- und einen Nachteil der kontinu- ierlichen Speicherung von Dateien.
c) I/O-Scheduling (4,5 Punkte) Gegeben sei ein Plattenspeicher mit 8 Spuren. Der dazugehörige 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 drei bearbeiteten Aufträgen erhält er die Aufträge in L2. Nach weiteren drei (d.h. nach insgesamt sechs) bearbeiteten Aufträgen erhält er die Aufträge in L3. Zu Beginn bendet sich der Schreib-/Lesekopf über Spur 0.
L1 = {1,4,7,2},L2 = {3,6,0},L3 = {5,2}
Der I/O-Scheduler arbeitet nach der Fahrstuhlstrategie (Elevator). Tragen Sie die Reihenfolge der gelesenen Spuren ein.
.. .. .. .. .. .. .. .. ..
Probeklausur Betriebssysteme, 25./26.07.2017 Seite 5 von 5