Prüfung 2012, Fragen und Antworten - WS 2012/2013 PDF

Preview

Summary

Download Prüfung 2012, Fragen und Antworten - WS 2012/2013 PDF

Description

Wiederholungsklausur zur Vorlesung ”Grundlagen Betriebssysteme und Systemsoftware” (Prof. Dr. J. Schlichter, N. Kl¨ ugel, F. Schulze, WS 2012/13)

• Die Bearbeitungsdauer betr¨agt 90 Minuten. • Es sind keine Hilfsmittel zugelassen. • Die Klausur besteht aus 5 Aufgaben auf insgesamt 11 Seiten (dieses Deckblatt mitgerechnet). • Es sind insgesamt maximal 60 Punkte zu erreichen. • Es werden keine inhaltlichen Fragen beantwortet. • Schreiben Sie Ihre L¨osung auf dem Angabenblatt in den vorgesehenen Platz nach den Aufgabenstellungen. Sollten Sie mehr Platz ben¨otigen, k¨onnen Sie auch die R¨uckseiten der Bl¨atter verwenden. • Als Ergebnisse von Rechenaufgaben sind Br¨ uche und Potenzen zul¨ assig. • Beschriften Sie dieses Deckblatt mit Vorname, Nachname, Matrikelnummer und Studiengang.

1

Aufgabe 1: Modellierung paralleler Systeme (12 Punkte)

Wir betrachten eine Schleuse, die es Schiffen erm¨oglicht, von einem Fluss mit hohem Wasserspiegel in einen See mit niedrigem Wasserspiegel zu fahren (nur in diese Richtung). Die Schleuse hat zwei Tore. Der Wasserspiegel in der Schleuse kann entweder hoch oder niedrig sein. Im Fluss gibt es einen Warteplatz f¨ur ein Schiff, das u ¨berfahren will, und nat¨ urlich kann sich auch in der Schleuse selbst ein Schiff befinden. Es gelten folgende zus¨atzliche Bedingungen: • Tor 1 darf nur ge¨ offnet sein, wenn der Wasserspiegel in der Schleuse hoch ist und Tor 2 darf nur ge¨offnet werden, wenn der Wasserspiegel in der Schleuse niedrig ist. • Die Schleuse muss nach Durchfahrt eines Schiffes immer in der Lage sein, ein weiteres Schiff durchfahren zu lassen. • Zust¨ande sind dichotom: Die Tore sind entweder offen oder zu, der Wasserspiegel entweder hoch oder niedrig. Auf dem Warteplatz und in der Schleuse gibt es (unabh¨angig voneinander) ein Schiff oder nicht. Gegeben sei nun ein fehlerhafter Entwurf eines nat¨ urlichzahligen Petrinetzes zur Schaltung der Schleuse:

2

1. Beschreiben Sie potenziell auftretende Probleme in Worten. Es gibt f¨ unf m¨ogliche Probleme durch fehlende Elemente. Hinweis: Gehen Sie das Netz anhand eines naheliegenden Szenarios durch. Gibt es Schaltfolgen, nach denen eine der genannten Bedingungen nicht mehr erf¨ ullt ist? (5P)

2. Korrigieren Sie das obige Petrinetz. (7P)

3

Aufgabe 2: Prozess- und Threadsynchronisation (16 Punkte) 1. Ein System besitzt f¨ unf Prozesse P1 bis P5 sowie vier Ressourcen. Der aktuelle Zustand sei beschrieben durch den Vektor der existierenden Ressourcen e, die Matrix der bereits allozierten Ressourcen A und die Matrix der maximalen Allokationen M :  e = (4, 10, 7, 6)

  A=  

1 1 0 1 0

4 0 1 2 1

4 1 2 0 0

0 1 3 1 0





    

  M =  

2 4 0 1 4

6 0 2 2 1

4 1 5 1 0

0 2 4 5 6

     

Entscheiden Sie, ob der Systemzustand sicher ist. Wenn ja, in welcher Allokationsreihenfolge? Wenn nicht, bis wohin kann eine Allokation erfolgen? Dokumentieren Sie Ihr Vorgehen zur Entscheidungsfindung. (6P)

4

2. Das Erste Readers-Writers-Problem beschreibt ein Szenario, bei dem mehrere Prozesse – manche lesend, manche schreibend – um den Zugriff auf eine Ressource konkurrieren. Mehrere lesende Prozesse k¨onnen zeitgleich auf die Ressource zugreifen, solange kein schreibender Zugriff stattfindet. Will ein Prozess schreiben, wartet er, bis andere Zugriffe abgeschlossen sind. Greift ein Prozess schreibend auf die Ressource zu, ist anderen Prozessen der Zugriff solange verwehrt. Der untenstehende Pseudocode modelliert beide Prozesstypen und ist so zu vervollst¨andigen, dass Prozesse schreiben → doActualWriting() respektive lesen → doActualReading() k¨ onnen, ohne die genannten Voraussetzzungen zu verletzen. Verwenden Sie hierf¨ ur ausschließlich die bereits vorgegebenen Konstrukte. (6P) Semaphore write=1 Semaphore lock=1; int readcount=0; //z¨ ahle Lesezugriffe writer() {

//schreibe doActualWriting();

} reader() {

//lese doActualReading();

} 5

3. Welches Wartekonzept realisieren Monitore? (1P)

4. In der Architektur eines Monitors existieren mindestens zwei unterschiedliche Warteschlangen f¨ ur Prozesse (Stichwort Signaling). Erl¨ autern Sie diese in je einem Satz. (3P)

Aufgabe 3: Scheduling (8 Punkte) 1. Wir betrachten einen Round-Robin-Scheduler, der mit einer Liste von Pointern auf Prozesskontrollbl¨ocke arbeitet. Wie ließen sich mit dem beschriebenen System Priorit¨aten realisieren, ohne in die Algorithmik des Schedulers einzugreifen? Nennen Sie einen Nachteil Ihres Vorschlags. (3P)

6

2. Nennen Sie außer dem Prozessnamen vier Inhalte des Prozesskontrollblocks eines Prozesses. (2P)

3. Was ist eine Multilevel Feedback Queue? (1P)

4. Welche Abw¨ agung gilt es bei der Wahl des (fixen) Zeitquantums bei der Implementierung eines Round-Robin-Schedulers zu treffen? (2P)

7

Aufgabe 4: Speicherverwaltung (12 Punkte) Arbeitsspeicher 1. Worin besteht der Unterschied zwischen externer und interner Fragmentierung von Speicherbereichen? Erl¨autern Sie! (2P)

2. Gegeben seien eine Menge von Seiten (pages) N = {0, 1, 2, 3, 4, 5, 6, 7} und eine Menge von Seitenrahmen (frames) F = {f1 , f2 , f3 }. Nun wird in folgender Reihenfolge auf die Seiten zugegriffen: w=7 2 5 0 4 0 7 5 1 3 Vollziehen Sie schrittweise die Seitenersetzungs-Strategien LRU (Least Recently Used) und Second Chance schrittweise, indem Sie die entsprechenden leeren Tabellen bef¨ ullen! Strategie LRU: Anforderung

f1

f2

f3

Page-Fault j/n

7 2 5 0 4 0 7 5 1 3

(2 P)

8

Strategie Second Chance: FIFO Anforderung

f1

f2

f3

Page-Fault j/n

Pos 3

Pos 1

Pos 2

r

r

r

2

r

r

r

5

r

r

r

r

r

r

r

r

r

r

r

r

r

r

r

r

r

r

r

r

r

r

r

r

7

0 4 0 7 5 1 3

(3 P)

Dateisysteme 1. Wie unterscheiden sich Hard Links von Soft Links (Symbolic Links)? (2P)

2. Welcher Linktyp ist zu bevorzugen, wenn die Zieldatei h¨aufig in der Verzeichnishierarchie verschoben wird? Begr¨ unden Sie. (2P)

¨ eines Dateinamens vollzogen? (1P) 3. Wo wird in UNIX die Anderung

9

Aufgabe 5: Systemprogrammierung (12 Punkte) Nehmen Sie im Nachfolgenden ein 32-Bit-System an. Der Compiler verwendet 4 Bytes, um ein int zu speichern, 2 Bytes f¨ ur ein short und 1 Byte f¨ ur ein char. 1. Was ist ein heapbasierter Exploit? Geben Sie ein nat¨ urlichsprachliches Beispiel. (2P)

2. Ist Speicherallokation auf dem Heap oder auf dem Stack generell performanter? Wieso? (2P)

3. Betrachten Sie das folgende Codeschnippsel. Wie lautet die Ausgabe? (4P) int (*p)[4]; int i; p=0; p++; i = p; i--; printf("%d ", p); p = i; printf("%d", p);

10

4. Betrachten Sie den nachfolgenden Code: unsigned char bytes[12] = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12 }; char *i; struct int_and_char { int x; char c; } *p; i = (char *) (&(bytes[4])); p = (struct int_and_char *) (&(bytes[5]));

Welchen Wert haben die folgenden Ausdr¨ ucke? Geben Sie jeweils eine kurze Begr¨ undung an. (4P) (a) i[2]

(b) p->c

11

Wiederholungsklausur zur Vorlesung ”Grundlagen Betriebssysteme und Systemsoftware” (Prof. Dr. J. Schlichter, N. Kl¨ ugel, F. Schulze, WS 2012/13)

• Die Bearbeitungsdauer betr¨agt 90 Minuten. • Es sind keine Hilfsmittel zugelassen. • Die Klausur besteht aus 5 Aufgaben auf insgesamt 11 Seiten (dieses Deckblatt mitgerechnet). • Es sind insgesamt maximal 60 Punkte zu erreichen. • Es werden keine inhaltlichen Fragen beantwortet. • Schreiben Sie Ihre L¨ osung auf dem Angabenblatt in den vorgesehenen Platz nach den Aufgabenstellungen. Sollten Sie mehr Platz ben¨ otigen, k¨ onnen Sie auch die R¨ uckseiten der Bl¨ atter verwenden. • Als Ergebnisse von Rechenaufgaben sind Br¨ uche und Potenzen zul¨ assig. • Beschriften Sie dieses Deckblatt mit Vorname, Nachname, Matrikelnummer und Studiengang.

Aufgabe 1: Modellierung paralleler Systeme (12 Punkte)

Wir betrachten eine Schleuse, die es Schiffen erm¨oglicht, von einem Fluss mit hohem Wasserspiegel in einen See mit niedrigem Wasserspiegel zu fahren (nur in diese Richtung). Die Schleuse hat zwei Tore. Der Wasserspiegel in der Schleuse kann entweder hoch oder niedrig sein. Im Fluss gibt es einen Warteplatz f¨ ur ein Schiff, das u ¨berfahren will, und nat¨ urlich kann sich auch in der Schleuse selbst ein Schiff befinden. Es gelten folgende zus¨atzliche Bedingungen: • Tor 1 darf nur ge¨ offnet sein, wenn der Wasserspiegel in der Schleuse hoch ist und Tor 2 darf nur ge¨offnet werden, wenn der Wasserspiegel in der Schleuse niedrig ist. • Die Schleuse muss nach Durchfahrt eines Schiffes immer in der Lage sein, ein weiteres Schiff durchfahren zu lassen. • Zust¨ande sind dichotom: Die Tore sind entweder offen oder zu, der Wasserspiegel entweder hoch oder niedrig. Auf dem Warteplatz und in der Schleuse gibt es (unabh¨angig voneinander) ein Schiff oder nicht. Gegeben sei nun ein fehlerhafter Entwurf eines nat¨ urlichzahligen Petrinetzes zur Schaltung der Schleuse:

1. Beschreiben Sie potenziell auftretende Probleme in Worten. Es gibt f¨ unf m¨ogliche Probleme durch fehlende Elemente. Hinweis: Gehen Sie das Netz anhand eines naheliegenden Szenarios durch. Gibt es Schaltfolgen, nach denen eine der genannten Bedingungen nicht mehr erf¨ ullt ist? (5P) L¨ osung: • Wenn ein Schiff in die Schleuse f¨ahrt (t4 ), wird dem Zustand offen von Tor 1 ein Token entnommen. Tor 1 kann nun nicht mehr schalten. (1P) • t4 kann schalten, auch wenn bereits ein Schiff in der Schleuse ist. (1P) • Wenn ein Schiff die Schleuse verl¨ asst (t7 ), wird dem Zustand offen von Tor 2 ein Token entnommen. Tor 2 kann nun nicht mehr schalten. (1P) • t6 kann auch bei offenem Tor 1 schalten und den Wasserspiegel senken. (1P) • t5 kann auch bei offenem Tor 2 schalten und den Wasserspiegel heben. (1P) 2. Korrigieren Sie das obige Petrinetz. (7P)

L¨ osung:

Aufgabe 2: Prozess- und Threadsynchronisation (16 Punkte) 1. Ein System besitzt f¨ unf Prozesse P1 bis P5 sowie vier Ressourcen. Der aktuelle Zustand sei beschrieben durch den Vektor der existierenden Ressourcen e, die Matrix der bereits

allozierten Ressourcen A und die Matrix der maximalen Allokationen M :  e = (4, 10, 7, 6)

  A=  

1 1 0 1 0

4 0 1 2 1

4 1 2 0 0

0 1 3 1 0





    

  M =  

2 4 0 1 4

6 0 2 2 1

4 1 5 1 0

0 2 4 5 6

     

Entscheiden Sie, ob der Systemzustand sicher ist. Wenn ja, in welcher Allokationsreihenfolge? Wenn nicht, bis wohin kann eine Allokation erfolgen? Dokumentieren Sie Ihr Vorgehen zur Entscheidungsfindung. (6P) L¨ osung: Banker’s Algorithmus: Zun¨achst werden die noch zur Verf¨ ugung stehenden Ressourcen a bestimmt. Durch Addition der aktuell allozierten Ressourcen eines Typs und Subtraktion von e ergibt sich: a = (1, 2, 0, 1). P1 kann als einziger Prozess ausreichend Ressourcen (1, 2, 0, 0) anfordern und terminieren: a = (2, 6, 4, 1). Nur P3 ist mit einem Bedarf von (0, 1, 3, 1) gen¨ ugsam genug, um Ressourcen anzufordern und zu terminieren: a = (2, 7, 6, 4). Es kann daraufhin nur P4 mit (0, 0, 1, 4) folgen: a = (3, 9, 6, 5). Es folgt P2 zu a = (4, 9, 7, 6) und schließlich P5 . Der Zustand ist sicher. Die Allokationsreihenfolge ist: P1 , P3 , P4 , P2 , P5 .

• 1P Abzug je Fehler (Folgefehler bleiben abzugsfrei) • Antwort ohne Dokumentation: 0P

2. Das Erste Readers-Writers-Problem beschreibt ein Szenario, bei dem mehrere Prozesse – manche lesend, manche schreibend – um den Zugriff auf eine Ressource konkurrieren. Mehrere lesende Prozesse k¨onnen zeitgleich auf die Ressource zugreifen, solange kein schreibender Zugriff stattfindet. Will ein Prozess schreiben, wartet er, bis andere Zugriffe abgeschlossen sind. Greift ein Prozess schreibend auf die Ressource zu, ist anderen Prozessen der Zugriff solange verwehrt. Der untenstehende Pseudocode modelliert beide Prozesstypen und ist so zu vervollst¨andigen, dass Prozesse schreiben → doActualWriting() respektive lesen → doActualReading() k¨ onnen, ohne die genannten Voraussetzzungen zu verletzen. Verwenden Sie hierf¨ ur ausschließlich die bereits vorgegebenen Konstrukte. (6P) Semaphore write=1 Semaphore lock=1; int readcount=0; //z¨ ahle Lesezugriffe writer() {

//schreibe doActualWriting();

} reader() {

//lese doActualReading();

} L¨ osung:

Semaphore write = 1 //Mutex f¨ ur Schreibrechte Semaphore lock = 1; int readcount = 0; //z¨ ahle lesende Prozesse

writer() { write.P(); //schreibe doActualWriting(); write.V(); }

reader() {

lock.P(); readcount++; if (readcount == 1) write.P(); lock.V(); //lese doActualReading(); lock.P(); readcount--; if (readcount == 0) write.V(); lock.V(); } • Korrektes Inkrementieren/Dekrementieren von readcount: 1P • Korrekter Schutz von readcount mittels Mutex: je 0.5P (1P max) • Korrekter Schreibmutex in writer() 1P • Lock und Unlock des Schreibmutex beim Reader: je 1P • Fehlerfreiheit: 1P Die Aufgabe stellt eine Verallgemeinerung des Tunnelproblems der regul¨aren Klausur dar. Die L¨osung erfolgt absolut analog.

3. Welches Wartekonzept realisieren Monitore? (1P) L¨ osung: Blockierendes (passives) Warten (Umschreibung ebenfalls akzeptiert). Nicht busy waiting.

4. In der Architektur eines Monitors existieren mindestens zwei unterschiedliche Warteschlangen f¨ ur Prozesse (Stichwort Signaling). Erl¨autern Sie diese in je einem Satz. (3P) L¨ osung: Die externe Warteschlange bezieht sich auf das Lock des Monitors und damit darauf, welcher Prozess den Monitor betreten und auf den gesch¨ utzten Daten arbeiten darf. (1P) Die interne Warteschlange bezieht sich auf die Condition-Variablen und damit auf die Prozesse, die im Inneren des Monitors nach Aufruf von wait() passiv darauf warten, mittels notify() geweckt zu werden, um ihre Arbeit fortzusetzen.1 (2P) 1

In Java gibt es nur eine einzige, implizite Condition-Variable pro Monitor.

Aufgabe 3: Scheduling (8 Punkte) 1. Wir betrachten einen Round-Robin-Scheduler, der mit einer Liste von Pointern auf Prozesskontrollbl¨ocke arbeitet. Wie ließen sich mit dem beschriebenen System Priorit¨aten realisieren, ohne in die Algorithmik des Schedulers einzugreifen? Nennen Sie einen Nachteil Ihres Vorschlags. (3P) L¨ osung: Einf¨ ugen mehrerer Pointer auf den gleichen PCB (2P) M¨ogliche Nachteile (1P maximal) sind u.a.: • potentiell h¨ aufigere Kontextwechsel • Entfernen von Prozessen aus der Running-Queue aufwendiger • zus¨atzliche Instanz neben Scheduler f¨ urs Scheduling n¨otig (”Priorit¨atsverwalter”)

2. Nennen Sie außer dem Prozessnamen vier Inhalte des Prozesskontrollblocks eines Prozesses. (2P) L¨ osung: • Prozess-ID • Zustandsinformationen • Befehlsz¨ahler • CPU-Register • Stack-Pointer • Scheduling-Informationen • Zugewiesener Adressraum • I/O-Informationen (bspw. ge¨offnete Dateien) • Ggf. Pointer zum Elternprozess Je 0.5P

3. Was ist eine Multilevel Feedback Queue? (1P) L¨ osung: Gruppe mehrerer Queues zur Implementierung dynamischer Priorit¨aten (eine Queue pro Priorit¨at)

4. Welche Abw¨ agung gilt es bei der Wahl des (fixen) Zeitquantums bei der Implementierung eines Round-Robin-Schedulers zu treffen? (2P) L¨ osung: • Ein kleines Quantum erh¨ oht die Zahl der Kontextwechsel, ein Overhead entsteht. (1P) • Ein Round Robin mit zu großem Quantum approximiert FCFS. (1P)

Aufgabe 4: Speicherverwaltung (12 Punkte) Arbeitsspeicher 1. Worin besteht der Unterschied zwischen externer und interner Fragmentierung von Speicherbereichen? Erl¨autern Sie! (2P)

L¨ osung: • Externe Fragmentierung: Es wechseln sich benutzte und unbenutzte Speicherbereiche innerhalb des Adressraums ab. Speicheranforderungen werden jeweils genau erf¨ ullt. (1P) Anforderung

belegt

belegt

belegt

belegt

belegt

belegt

belegt

freie Speicherbereiche

• Interne Fragmentierung: Der Speicher ist in Bereiche fester Gr¨ oße untergliedert und Speicheranforderungen werden nur in Vielfachen dieser festen Grundgr¨oße befriedigt. Der Verschnitt findet innerhalb dieser Bereiche fester Gr¨ oße statt. (1P)

Anforderung

freier Speicherbereich

2. Gegeben seien eine Menge von Seiten (pages) N = {0, 1, 2, 3, 4, 5, 6, 7} und eine Menge von Seitenrahmen (frames) F = {f1 , f2 , f3 }. Nun wird in folgender Reihenfolge auf die Seiten zugegriffen: w=7 2 5 0 4 0 7 5 1 3 Vollziehen Sie schrittweise die Seitenersetzungs-Strategien LRU (Least Recently Used) und Second Chance schrittweise, indem Sie die entsprechenden leeren Tabellen bef¨ ullen! Strategie LRU: Anforderung

f2

f1

f3

Page-Fault j/n

7 2 5 0 4 0 7 5 1 3

(2 P) Strategie Second Chance: FIFO Anforderung

7 2 5 0 4 0 7 5 1 3

f1

f2

f3

Page-Fault j/n

Pos 3

Pos 1

Pos 2

r

r

r

r

r

r

r

r

r

r

r

r

r

r

r

r

r

r

r

r

r

r

r

r

r

r

r

r

r

r

(3 P)

L¨ osung: Strategie LRU: Anforderung

f1

7

7

2

7

2

5

7

2

5

j

0

0

2

5

j

4

0

4

5

j

0

0

4

5

n

7

0

4

7

j

5

0

5

7

j

1

1

5

7

j

3

1

5

3

j

f2

Page-Fault j/n

f3

j j

Strategie Second Chance: FIFO Anforderung

f1

7

7

f2

f3

Page-Fault j/n

j 2

5

7

2

5

j

5

0

0

2

5

j

0

4

0

4

5

j

2

4

0

0

4

5

n

4

7

0

4

7

j

7

Pos 2

r

7

7

2

j

Pos 1

Pos 3

r

r
...