Prüfung 2012, Fragen und Antworten - (WS 2011/12), winter PDF

Preview

Summary

Klausur zur Vorlesung Betriebssysteme und (Prof. Dr. J. Schlichter, Dr. W. WS Die Bearbeitungsdauer agt 90 Minuten. Es sind keine Hilfsmittel zugelassen. Die Klausur besteht aus 5 Aufgaben auf insgesamt 9 Seiten (dieses Deckblatt mitgerechnet). Es sind insgesamt maximal 40 Punkte zu erreichen. Es we...

Description

Klausur zur Vorlesung ”Grundlagen Betriebssysteme und Systemsoftware” (Prof. Dr. J. Schlichter, Dr. W. W¨orndl, WS 2011/12)

• Die Bearbeitungsdauer betr¨agt 90 Minuten. • Es sind keine Hilfsmittel zugelassen. • Die Klausur besteht aus 5 Aufgaben auf insgesamt 9 Seiten (dieses Deckblatt mitgerechnet). • Es sind insgesamt maximal 40 Punkte zu erreichen. • Es werden keine 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. • Klausureinsicht ist am Dienstag, 06.03.2012, 10:00-11:30 in Raum 01.07.023 m¨ oglich. ¨ (Diese Information steht auch auf den Web-Seiten zur Vorlesung und Ubung.) • Beschriften Sie dieses Deckblatt mit Vorname, Nachname, Matrikelnummer und Studiengang.

Aufgabe 1: Synchronisation mit Semaphoren (7 Punkte) Ein M¨obelh¨andler hat eine Lagerhalle f¨ ur Tische und St¨ uhle. Beliefert wird er von einem Fabrikanten F, der bei jeder Lieferung einen Tisch und zwei St¨ uhle bringt. Ein Ausfahrer T bringt je Fahrt einen Tisch zum Kunden, ein Ausfahrer S je Fahrt einen Stuhl. Zum Be- und Entladen muss eine Laderampe benutzt werden. F¨ ur sich alleine betrachtet laufen die beteiligten Prozesse folgendermaßen ab: Process T { while (TRUE) { ; ; ; } }

Process S { while (TRUE) { ; ; ; } }

Process F { while (TRUE) { ; ; ; ; } }

Synchronisieren Sie diese drei Prozesse, indem Sie in Pseudocode-Notation in geeigneter Weise Semaphore deklarieren und Semaphor-Operationen einf¨ ugen. Die Pseudocode-Operation zum Deklarieren eines Semaphors mit Namen name mit Startwert n laute: name(n); Die Pseudocode-Operationen zum Aufrufen von P und V auf der Semaphore mit Namen name lauten: P(name) V(name) Sperrphasen sind m¨oglichst kurz zu halten und folgende Bedingungen m¨ ussen erf¨ ullt sein: • Zur Laderampe kann jeweils nur ein Prozess fahren. • Der Ausfahrer T darf nur zur Rampe fahren, wenn noch ein Tisch im Lager ist. • Der Ausfahrer S darf nur zur Rampe fahren, wenn noch ein Stuhl im Lager ist. • Die Lagerhalle hat beschr¨ ankte Kapazit¨ at, sie kann h¨ ochstens 12 M¨ obelst¨ ucke (Tische oder St¨ uhle) aufnehmen. • Der Fabrikant darf nur zur Rampe fahren, wenn er seine Lieferung vollst¨ andig abladen kann. • Zu Beginn sei das Lager leer und die Rampe frei.

1. Deklarieren Sie alle ben¨otigten Semaphoren und erkl¨ aren Sie kurz ihren Zweck bzw. ihre Pragmatik. (3 P.)

2. F¨ ugen Sie im nachfolgend aufgelisteten Pseudocode des Ablaufs der beteiligten Prozesse an geeigneter Stelle entsprechende Aufrufe von P und V ein. (4 P.) Process T { while (TRUE) {

Process S { while (TRUE) {

Process F { while (TRUE) {

;

;

;

;

;

;

;

;

;

;

} }

} }

} }

Aufgabe 2: Scheduling (11 Punkte) 1. Gegeben seien f¨ unf Prozesse mit ihren jeweiligen Ankunftszeiten, Bedienzeiten und Priorit¨ aten: Prozess

Ankunfszeit

Bedienzeit

Priorit¨ at

P1 P2 P3 P4 P5

1 4 2 6 6

8 4 6 5 3

1 3 2 2 1

Dabei stellt 1 die niedrigste und 3 die h¨ ochste Priorit¨ at dar. Tragen Sie in den nachfolgenden Gantt-Diagrammen f¨ ur die angegebenen SchedulingVerfahren ein, welcher Prozess zu welcher Zeit die CPU erh¨alt. Markieren Sie rechenwillige Prozesse mit ”-” und rechnende Prozesse mit ”X” in der jeweiligen Spalte. (a) Shortest Remaining Processing Time (SRPT): Prozess mit der k¨ urzesten Restbedienzeit wird ausgef¨ uhrt, unterbrechend nur beim Eintreffen neuer Prozesse. Haben zwei Prozesse gleiche Restbedienzeiten, soll dem Prozess Vorrang gegeben werden, der die h¨ ohere Priorit¨ at besitzt. (3 P.) 0

5

10

15

20

25

Zeit

P1 P2 P3 P4 P5 (b) Statische Priorit¨ aten mit Round Robin: Prozess mit h¨ ochster Priorit¨ at wird ausgew¨ ahlt, unterbrechend nur beim Eintreffen neuer Prozesse. Prozesse mit gleicher Priorit¨at sollen mit Round Robin und einem Zeitquantum von 2 Zeiteinheiten abgearbeitet werden. (3 P.) 0

5

10

15

P1 P2 P3 P4 P5 2. Berechnen Sie die Verweilzeit f¨ ur P3 in beiden Strategien. (1 P.)

3. Berechnen Sie die Wartezeit f¨ ur P4 in beiden Strategien. (1 P.)

20

25

Zeit

4. Nennen Sie allgemein die Vor- und Nachteile kurzer bzw. langer Zeitquanten in Bezug auf Effizienz, Fairness und Reaktionszeiten bei Zeitscheibenstrategien (Round Robin). (3 P.)

Aufgabe 3: Speicherverwaltung und Dateisysteme (9 Punkte) 1. Speicherverwaltungsstrategien dienen der Belegung und Freigabe von zusammenh¨ angenden Speicherbereichen. Gegeben sei eine Liste freier Speicherbereiche: 150 KB - 100 KB - 250 KB - 300 KB - 200 KB Wie verhalten sich jeweils die Strategien first fit, next fit, best fit und worst fit bei einer eingehenden Speicheranforderung von 160 KB? Geben Sie jeweils nur an, welcher der freien Speicherbereiche verwendet wird. (2 P.) (a) first fit:

(b) next fit:

(c) best fit:

(d) worst fit:

2. Gegeben sei ein Rechnersystem mit 5 Kacheln, die Seitentabelle sei entsprechend folgender Tabelle belegt: Seite 0 1 2 5 7

Kachel 0 1 2 3 4

Ladezeit 100 160 140 180 200

Letzter Zugriff (Zeit) 240 200 220 230 210

R-Bit 1 0 0 1 0

M-Bit 1 0 1 0 1

Geben Sie an, welche Seite jeweils unter Verwendung der Seitenersetzungsstrategien FIFO, LRU und Second Chance bei Einlagerung einer neuen Seite ersetzt und ausgelagert wird. Begr¨ unden Sie Ihre Antwort kurz. (3 P.) (a) FIFO:

(b) LRU:

(c) Second Chance:

3. Was versteht man unter Belady’s Anomalie? (2 P.)

4. Auf einer 16 GB Festplatte werden Dateien unter Unix mittels I-Nodes gespeichert. Ein I-Node verf¨ uge u ¨ ber 10 direkte Referenzen auf Datenbl¨ ocke, einen single-indirect Verweis und einen double-indirect Verweis. Die Blockl¨ ange betr¨ agt 1024 Bytes und die Adressl¨ange 32 Bit. Wie viele Bl¨ocke Verwaltungsaufwand ben¨otigt eine 300 KB Datei? (2 P.)

Aufgabe 4: C-Programmierung (5 Punkte) 1. Die Datei ARTIKEL.H enthalte die folgende Struktur-Definition. struct artikel { int nummer; // Nummer char bezeich[32]; // Bezeichnung int anzahl; // Anzahl float preis; // Verkaufspreis };

Die Vereinbarung der beteiligten Variablen: #include "ARTIKEL.H" struct artikel art = { 0, "NN", 1, 0.0F }; struct artikel *artptr = &art;

Beschreiben Sie kurz den Effekt der folgenden Anweisungen, wenn sie zul¨assig sind. Geben sie andernfalls eine Erl¨auterung, warum die Anweisungen unzul¨assig sind. (5 P.) (a) --art.anzahl;

(b) printf("Preis: %f\n", artptr->preis);

(c) if( artptr.nummer == 4321 ) printf("\n Gefunden!");

(d) strcpy( artptr->bezeich, "TV");

(e) artptr++;

Aufgabe 5: Petri-Netze (8 Punkte) Gegeben sei folgendes boolsche Petri-Netz:

1. Geben Sie den Erreichbarkeitsgraphen des gegebenen Petri-Netzes an. (3 P.)

2. Existiert in dem gegebenen Petri-Netz ein nicht-sequentieller Ablauf? Falls ja, geben Sie ein Beispiel an. Falls nein, begr¨ unden Sie Ihre Antwort kurz. (1 P.)

3. Ist in dem gegebenen Petri-Netz eine Verklemmung m¨ oglich? Begr¨ unden Sie Ihre Antwort kurz. (1 P.)

4. Die Stellen s4 und s5 sollen nun einen kritischen Bereich darstellen, d.h. es darf nur entweder s4 oder s5 belegt sein. Realisieren Sie diesen wechselseitigen Ausschluss zwischen den beiden Stellen s4 und s5, indem sie das gegebene Petri-Netz erweitern und dabei maximal eine weitere Stelle einf¨ ugen. Abl¨aufe, die den kritischen Bereich nicht betreffen, sollen m¨ oglichst unver¨ andert bleiben. Zeichnen Sie Ihre Erweiterung in die folgende Grafik. (3 P.)

Klausur zur Vorlesung ”Grundlagen Betriebssysteme und Systemsoftware” L¨osungsvorschlag (Prof. Dr. J. Schlichter, Dr. W. W¨orndl, WS 2011/12)

Punkteschema:

Note Punkte 1.0 38-40 1.3 36-37 1.7 34-35 2.0 32-33 2.3 29-31 2.7 27-28 3.0 25-26 3.3 23-24 3.7 20-22 4.0 17-19 4.3 10-16 4.7 5-9 5.0 0-4

Aufgabe 1: Synchronisation mit Semaphoren (7 Punkte) Ein M¨ obelh¨ andler hat eine Lagerhalle f¨ ur Tische und St¨ uhle. Beliefert wird er von einem Fabrikanten F, der bei jeder Lieferung einen Tisch und zwei St¨ uhle bringt. Ein Ausfahrer T bringt je Fahrt einen Tisch zum Kunden, ein Ausfahrer S je Fahrt einen Stuhl. Zum Be- und Entladen muss eine Laderampe benutzt werden. F¨ ur sich alleine betrachtet laufen die beteiligten Prozesse folgendermaßen ab: Process T { while (TRUE) { ; ; ; } }

Process S { while (TRUE) { ; ; ; } }

Process F { while (TRUE) { ; ; ; ; } }

Synchronisieren Sie diese drei Prozesse, indem Sie in Pseudocode-Notation in geeigneter Weise Semaphore deklarieren und Semaphor-Operationen einf¨ ugen. Die Pseudocode-Operation zum Deklarieren eines Semaphors mit Namen name mit Startwert n laute: name(n); Die Pseudocode-Operationen zum Aufrufen von P und V auf der Semaphore mit Namen name lauten: P(name) V(name) Sperrphasen sind m¨oglichst kurz zu halten und folgende Bedingungen m¨ ussen erf¨ ullt sein: • Zur Laderampe kann jeweils nur ein Prozess fahren. • Der Ausfahrer T darf nur zur Rampe fahren, wenn noch ein Tisch im Lager ist. • Der Ausfahrer S darf nur zur Rampe fahren, wenn noch ein Stuhl im Lager ist. • Die Lagerhalle hat beschr¨ ankte Kapazit¨ at, sie kann h¨ ochstens 12 M¨ obelst¨ ucke (Tische oder St¨ uhle) aufnehmen. • Der Fabrikant darf nur zur Rampe fahren, wenn er seine Lieferung vollst¨ andig abladen kann. • Zu Beginn sei das Lager leer und die Rampe frei.

1. Deklarieren Sie alle ben¨otigten Semaphoren und erkl¨ aren Sie kurz ihren Zweck bzw. ihre Pragmatik. (3 P.) L¨ osung: lager(12); - z¨ ahlt die freien Pl¨ atze im Lager stuehle(0); - z¨ ahlt die St¨ uhle im Lager tische(0); - z¨ ahlt die Tische im Lager rampe(1); - boolscher Semaphor zum wechselseitigen Ausschluss der Rampe, zu Beginn ist Rampe frei. (Je fehlendem Semaphor -1 P., fehlende oder falsche Initialisierung -0,5 P., je falscher Erkl¨ arung -0.5 P.) 2. F¨ ugen Sie im nachfolgend aufgelisteten Pseudocode des Ablaufs der beteiligten Prozesse an geeigneter Stelle entsprechende Aufrufe von P und V ein. (4 P.) L¨ osung: Process T { while (TRUE) {

Process S { while (TRUE) {

Process F { while (TRUE) {

P(tische); P(rampe);

P(stuehle); P(rampe);

P(lager); P(lager); P(lager); P(rampe);

;

;

;

;

;

;

V(lager);

V(lager);

V(tische);

;

;

;

V(rampe);

V(rampe);

V(stuehle); V(stuehle);

; V(rampe);

} }

(Je Fehler -1 P.)

} }

} }

Aufgabe 2: Scheduling (11 Punkte) 1. Gegeben seien f¨ unf Prozesse mit ihren jeweiligen Ankunftszeiten, Bedienzeiten und Priorit¨ aten: Prozess P1 P2 P3 P4 P5

Ankunfszeit 1 4 2 6 6

Bedienzeit 8 4 6 5 3

Priorit¨ at 1 3 2 2 1

Dabei stellt 1 die niedrigste und 3 die h¨ ochste Priorit¨ at dar. Tragen Sie in den nachfolgenden Gantt-Diagrammen f¨ ur die angegebenen SchedulingVerfahren ein, welcher Prozess zu welcher Zeit die CPU erh¨alt. Markieren Sie rechenwillige Prozesse mit ”-” und rechnende Prozesse mit ”X” in der jeweiligen Spalte. (a) Shortest Remaining Processing Time (SRPT): Prozess mit der k¨ urzesten Restbedienzeit wird ausgef¨ uhrt, unterbrechend nur beim Eintreffen neuer Prozesse. Haben zwei Prozesse gleiche Restbedienzeiten, soll dem Prozess Vorrang gegeben werden, der die h¨ ohere Priorit¨ at besitzt. (3 P.) L¨ osung: 0

P1 P2 P3 P4 P5

5

X - - - - - X X X X X X - - - - - -

10

15

20

25

Zeit

- - - - - - - - - - - - X X X X X X X - - - X X X X - - - - - - - X X X X X X X X

(Je Fehler -1 P.) (b) Statische Priorit¨ aten mit Round Robin: Prozess mit h¨ ochster Priorit¨ at wird ausgew¨ ahlt, unterbrechend nur beim Eintreffen neuer Prozesse. Prozesse mit gleicher Priorit¨at sollen mit Round Robin und einem Zeitquantum von 2 Zeiteinheiten abgearbeitet werden. (3 P.) L¨ osung: 0

P1 P2 P3 P4 P5

5

X - - - - - X X X X X X - - - - - -

10

15

20

25

Zeit

- - - - - - - - - - - X X - X X X X X X X - - X X - - X X - - X X X - - - - - - - - - X X - - X

(Je Fehler -1 P.) Hinweis: Das Round Robin von P3 und P4 ab Zeiteinheit 8, sowie von P5 und P1 ab Zeiteinheit 17, kann auch vertauscht ablaufen, da keine weitere Priorisierung festgelegt wurde.

2. Berechnen Sie die Verweilzeit f¨ ur P3 in beiden Strategien. (1 P.) L¨ osung: a) VP 3 = 13 b) VP 3 = 12 Hinweis: Wenn bei Teilaufgabe 1. das Round Robin von P3 und P4 ab Zeiteinheit 8 vertauscht angegeben wurde, ergibt sich VP 3 = 14 bei b). (Je 0,5 P.) 3. Berechnen Sie die Wartezeit f¨ ur P4 in beiden Strategien. (1 P.) L¨ osung: a) WP 4 = 9 b) WP 4 = 6 (Je 0,5 P.) 4. Nennen Sie allgemein die Vor- und Nachteile kurzer bzw. langer Zeitquanten in Bezug auf Effizienz, Fairness und Reaktionszeiten bei Zeitscheibenstrategien (Round Robin). (3 P.) L¨ osung: Kurze Zeitquanten f¨ uhren zu h¨ aufigerem Kontextwechsel und damit schlechterer Effizienz (0,5 P.), besserer Fairness (0,5 P.) und besserer Reaktionszeit (0,5 P.). Lange Zeitquanten f¨ uhren zu seltenerem Kontextwechsel und damit besserer Effizienz (0,5 P.), schlechterer Fairness (0,5 P.) und schlechterer Reaktionszeit (0,5 P.).

Aufgabe 3: Speicherverwaltung und Dateisysteme (9 Punkte) 1. Speicherverwaltungsstrategien dienen der Belegung und Freigabe von zusammenh¨ angenden Speicherbereichen. Gegeben sei eine Liste freier Speicherbereiche: 150 KB - 100 KB - 250 KB - 300 KB - 200 KB Wie verhalten sich jeweils die Strategien first fit, next fit, best fit und worst fit bei einer eingehenden Speicheranforderung von 160 KB? Geben Sie jeweils nur an, welcher der freien Speicherbereiche verwendet wird. (2 P.) L¨ osung: (a) first fit: 250 KB (b) next fit: 250 KB (c) best fit: 200 KB (d) worst fit: 300 KB (Je 0,5 P.)

2. Gegeben sei ein Rechnersystem mit 5 Kacheln, die Seitentabelle sei entsprechend folgender Tabelle belegt: Seite 0 1 2 5 7

Kachel 0 1 2 3 4

Ladezeit 100 160 140 180 200

Letzter Zugriff (Zeit) 240 200 220 230 210

R-Bit 1 0 0 1 0

M-Bit 1 0 1 0 1

Geben Sie an, welche Seite jeweils unter Verwendung der Seitenersetzungsstrategien FIFO, LRU und Second Chance bei Einlagerung einer neuen Seite ersetzt und ausgelagert wird. Begr¨ unden Sie Ihre Antwort kurz. (3 P.) L¨ osung: (a) FIFO: Seite 0, weil a¨lteste Ladezeit (b) LRU: Seite 1, weil a¨lteste Zugriffszeit (c) Second Chance: Seite 2, wegen R-Bit = 1 bei Seite 0 wird Seite mit zweit¨altester Ladezeit und R-Bit = 0 gew¨ ahlt (Je richtiger Auswahl 0,5 P., je richtiger Begr¨ undung 0,5 P.)

3. Was versteht man unter Belady’s Anomalie? (2 P.) L¨ osung: Belady’s Anomalie bedeutet, dass mehr Kacheln nicht unbedingt zu weniger Seitenfehlern f¨ uhren.

4. Auf einer 16 GB Festplatte werden Dateien unter Unix mittels I-Nodes gespeichert. Ein I-Node verf¨ uge u ¨ ber 10 direkte Referenzen auf Datenbl¨ ocke, einen single-indirect Verweis und einen double-indirect Verweis. Die Blockl¨ ange betr¨ agt 1024 Bytes und die Adressl¨ange 32 Bit. Wie viele Bl¨ocke Verwaltungsaufwand ben¨otigt eine 300 KB Datei? (2 P.) L¨ osung: 300 KB bedeutet 300 Bl¨ocke. 10 Bl¨ ocke direkt im I-Node = 1 Verwaltungsblock. 256 Bl¨ ocke im single-indirect Verweis = 1 Verwaltungsblock. 34 Bl¨ ocke im double-indirect Verweis = 2 Verwaltungsbl¨ ocke. Insgesamt werden also 4 Verwaltungsbl¨ ocke ben¨ otigt.

Aufgabe 4: C-Programmierung (5 Punkte) 1. Die Datei ARTIKEL.H enthalte die folgende Struktur-Definition. struct artikel { int nummer; // Nummer char bezeich[32]; // Bezeichnung int anzahl; // Anzahl float preis; // Verkaufspreis };

Die Vereinbarung der beteiligten Variablen: #include "ARTIKEL.H" struct artikel art = { 0, "NN", 1, 0.0F }; struct artikel *artptr = &art;

Beschreiben Sie kurz den Effekt der folgenden Anweisungen, wenn sie zul¨assig sind. Geben sie andernfalls eine Erl¨auterung, warum die Anweisungen unzul¨assig sind. (5 P.) (a) --art.anzahl; L¨ osung: Zul¨ assig. In art wird das Element anzahl dekrementiert.

(b) printf("Preis: %f\n", artptr->preis); L¨ osung: Zul¨ assig. Gibt das Element preis von art aus.

(c) if( artptr.nummer == 4321 ) printf("\n Gefunden!");

L¨ osung: Nicht zul¨ assig. Richtig ist: artptr->nummer.

(d) strcpy( artptr->bezeich, "TV"); L¨ osung: Zul¨ assig. Der String "TV" wird in das Element bezeich kopiert.

(e) artptr++; L¨ osung: Syntaktisch zul¨ assig: Der Zeiger wird auf die erste Speicherstelle hinter art gesetzt. Aber nicht sinnvoll, da dort kein Objekt vom Typ struct artikel liegen muss.

(Je Teilaufgabe 1 P.)

Aufgabe 5: Petri-Netze (8 Punkte) Gegeben sei folgendes boolsche Petri-Netz:

1. Geben Sie den Erreichbarkeitsgraphen des gegebenen Petri-Netzes an. (3 P.) L¨ osung:

Hinweis: Die Transition t3 kann nicht schalten, da die Nachbedingung der freien Kapazit¨at ¨ in der Zielstelle s2 nicht erf¨ ullt ist, vgl. Tutoraufgabe 2 auf Ubungsblatt 4. (Je Fehler -1 P.)

2. Existiert in dem gegebenen Petri-Netz ein nicht-sequentieller Ablauf? Falls ja, geben Sie ein Beispiel an. Falls nein, begr¨ unden Sie Ihre Antwort kurz. (1 P.) L¨ osung: Ja, t2 und t4 k¨onnen im Ausgangszustand nicht-sequentiell bzw. nebenl¨aufig ausgef¨ uhrt werden. 3. Ist in dem gegebenen Petri-Netz eine Verklemmung m¨ oglich? Begr¨ unden Sie Ihre Antwort kurz. (1 P.) L¨ osung: Ja, der Zustand (000111) nach Schalten von t2, t4, t1 und t2 stellt eine Verklemmung dar. 4. Die Stellen s4 und s5 sollen nun einen kritischen Bereich darstellen, d.h. es darf nur entweder s4 oder s5 belegt sein. Realisieren Sie diesen wechselseitigen Ausschluss zwischen den beiden Stellen s4 und s5, indem sie das gegebene Petri-Netz erweitern und dabei maximal eine weitere Stelle einf¨ ugen. Abl¨aufe, die den kritischen Bereich nicht betreffen, sollen m¨ oglichst unver¨ andert bleiben. Zeichnen Sie Ihre Erweiterung in die folgende Grafik. (3 P.) L¨ osung: Neue Stelle s7 mit Kante von t4 und zu t2:...