TechGI 3 Zwischentest am 09.01.2013 Gedaechtnisprotokoll ================================================================================================================ ================================================================================================================ ===========================================FRAGENDOKUMENT======================================================= ================================================================================================================ ================================================================================================================ 1. Aufgabe Multiple Choice (Wahr, Falsch) (6P) Falsche Angaben geben einen Punkt Abzug, keine Angabe weder plus noch minuspunkte. Die minimale Punktzahl dieser Aufgabe sind 0 Punkte. (keine Minuspunkte moeglich) 1. Threads, die im selben Prozess laufen haben einen gemeinsamen Speicherbereich. 2. Nebenlaeufigkeit (concurrency) bedeutet nicht, dass Prozesse tatsaechlich simultan ausgefuehrt werden (echte Parallelitaet). 3. Online Scheduling bedeutet, dass nur aktuelle Prozesse bekannt sind und die Entscheidungsfindung nur zur Laufzeit und auf Grund unvollstaendiger Informationen stattfindet. 4. Preemptive bedeutet, dass der Sollzeitpunkt (Deadline) eines Prozesses beachtet werden muss. 5. Bei Multilevel-Feedback wird ein Prozess, dem die CPU entzogen wird in die gleiche Warteschlange eingefuegt. 6. Semaphore sind fuer kurze kritische Abschnitte besser geeignet. 2. Aufgabe Prozesszustaende (3P) Tragen Sie die drei wichtigsten Prozesszustaende ein! 3. Aufgabe Prozessrelation Gegeben sei folgender Programmablauf: int main () { a = jobA(); b = jobB(a); c = jobC(a); d = jobD(a); e = jobE(b,c); f = jobF(d); g = jobG(e); h = jobH(g,f); i = jobI(h); return i; } a) Geben Sie den Prozessvorgaengergraphen an! b) Schreiben sie ein Porgramm in Pseudocode, das die Prozesse mit maximaler Parallelitaet ausfuehrt. Benutzen Sie dazu fork/join. 4. Aufgabe Scheduling Gegeben sind folgende Prozesse mit ihrer Bedienungs und Ankunftszeit: Prozess | Bedienzeit | Ankunftszeit ------------------------------------------ A | 15 | 0 B | 4 | 2 C | 3 | 7 D | 9 | 9 E | ? | 13 a) Geben Sie fuer folgende Schedulingverfahren an, welcher Prozess nach A als naechstes ausgefuehrt wird. FCFS: SJN: LCFS: HRRN: b) Die maximale Verspaetung fuer die folgenden Prozesse soll minimiert und bestimmt werden. Alle Prozesse starten bei t=4 | d | b --------------------------- P1 | 9 | 1 P2 | 16 | 4 P3 | 11 | 6 P4 | 12 | 2 P5 | 15 | 3 P6 | 19 | 2 5. Aufgabe Nebenlaeufigkeit Gegeben sind zwei Prozesse (P1, P2) die nebenlaeufig ausgefuehrt werden. Jede Zeile ist dabei als atomare Anweisung zu betrachten. Welche Werte koennen x und y nach der Ausfuehrung beider Prozesse annehmen? Startzustand: x = 7; y = 3; P1 { x = x + 1; y = x; } P2 { y = 3; x = x + 2; } 6. Aufgabe Semaphor Ein Parkhaus mit 10 Parkplaetzen soll in einem Programm nachgebildet werden. Jedes Auto wird dabei durch einen Prozess dargestellt. Stellen Sie mithilfe von Semaphoren in folgendem Pseudocode sicher, dass nicht zu viele Autos in das Parkhaus fahren koennen. (Die Semaphor-Funktionen brauchen nicht implementiert werden.) // Globale Variablen // Wird zur initialisierung einmalig aufgerufen init { } // Dies ist der Prozess fuer ein Auto Auto { // Auto parkt ein enterPH; //Auto verlaesst Parkplatz } ================================================================================================================ ================================================================================================================ ===========================================LOESUNGSDOKUMENT====================================================== ================================================================================================================ ================================================================================================================ HINWEIS: Alle hier beschiebenen Loesungen sind nicht zwangslaeufig richtig! Auch wir sind nur Studierende und machen leider hin und wieder Fehler :( Daher bitte alle Ergebnisse mit Vorsicht geniessen und doppelt ueberpruefen. An einigen Stellen findet ihr Anmerkungen, da wir uns nicht immer ganz einig waren, wie die Klausur nun aussah. 1. Aufgabe Multiple Choice (Wahr, Falsch) (6P) Falsche Angaben geben einen Punkt Abzug, keine Angabe weder plus noch minuspunkte. Die minimale Punktzahl dieser Aufgabe sind 0 Punkte. (keine Minuspunkte moeglich) 1. Threads, die im selben Prozess laufen haben einen gemeinsamen Speicherbereich. Loesung: Wahr 2. Nebenlaeufigkeit (concurrency) bedeutet nicht, dass Prozesse tatsaechlich simultan ausgefuehrt werden (echte Parallelitaet). Loesung: Wahr 3. Online Scheduling bedeutet, dass nur aktuelle Prozesse bekannt sind und die Entscheidungsfindung nur zur Laufzeit und auf Grund unvollstaendiger Informationen stattfindet. Loesung: Wahr 4. Preemptive bedeutet, dass der Sollzeitpunkt (Deadline) eines Prozesses beachtet werden muss. Loesung: Falsch 5. Bei Multilevel-Feedback wird ein Prozess, dem die CPU entzogen wird in die gleiche Warteschlange eingefuegt. Loesung: Falsch 6. Semaphore sind fuer kurze kritische Abschnitte besser geeignet. Loesung: Falsch 2. Aufgabe Prozesszustaende (3P) Tragen Sie die drei wichtigsten Prozesszustaende ein! Bereit, Blockiert, Laufend Der Rest war gegeben. 3. Aufgabe Prozessrelation a) Geben Sie den Prozessvorgaengergraphen an! int main () { a = jobA(); b = jobB(a); c = jobC(a); d = jobD(a); e = jobE(b,c); f = jobF(d); g = jobG(e); h = jobH(g,f); i = jobI(h); return i; } Loesung: b) Schreiben sie ein Porgramm in Pseudocode, das die Prozesse mit maximaler Parallelitaet ausfuehrt. Benutzen Sie dazu fork/join. Loesung: begin jobA(); fork(b); jobD(a); jobF(d); join(b); jobH(g,f); jobI(h); end b: begin fork(c); jobB(a); join(c); jobE(b,c); jobG(e); end c: begin jobC(a); end 4. Aufgabe Scheduling Gegeben sind folgende Prozesse mit ihrer Bedienungs und Ankunftszeit: Prozess | Bedienzeit | Ankunftszeit ------------------------------------------ A | 15 | 0 B | 4 | 2 C | 3 | 7 D | 9 | 9 E | ? | 13 a) Geben Sie fuer folgende Schedulingverfahren an, welcher Prozess nach A als naechstes ausgefuehrt wird. FCFS: Loesung: B SJN: Loesung: C LCFS: Loesung: E HRRN: Loesung: (unsicher) B oder C (wenn die Zahlen stimmen: B, weil ((15-2)+4)/4 = 17/4 und ((15-7)+3)/3=11/3. Allerdings mein ich, ich hatte da C raus...) b) Die maximale Verspaetung fuer die folgenden Prozesse soll minimiert und bestimmt werden. Alle Prozesse starten bei t=4 | d | b --------------------------- P1 | 9 | 1 P2 | 16 | 4 P3 | 11 | 6 P4 | 12 | 2 P5 | 15 | 3 P6 | 19 | 2 5. Aufgabe Nebenlaeufigkeit Gegeben sind zwei Prozesse (P1, P2) die nebenlaeufig ausgefuehrt werden. Jede Zeile ist dabei als atomare Anweisung zu betrachten. Welche Werte koennen x und y nach der Ausfuehrung beider Prozesse annehmen? Startzustand: x = 7; y = 3; P1 { x = x + 1; y = x; } P2 { y = 3; x = x + 2; } Loesung: x | y ------------ 10 | 10 10 | 3 10 | 8 <== Hatte hier nur 10 und 8 raus. Aber das kann auch falsch sein. Falsch, ist es leider auch. Richtig ist es wie es da steht: x=10; y element_aus {3;8;10}. y=3 passiert wenn zB: P1 vollstaendig vor P2 ablaeuft. 6. Aufgabe Semaphor Ein Parkhaus mit 10 Parkplaetzen soll in einem Programm nachgebildet werden. Jedes Auto wird dabei durch einen Prozess dargestellt. Stellen Sie mithilfe von Semaphoren in folgendem Pseudocode sicher, dass nicht zu viele Autos in das Parkhaus fahren koennen. (Die Semaphor-Funktionen brauchen nicht implementiert werden.) Loesung: // Globale Variablen Semaphore sem; // Wird zur initialisierung einmalig aufgerufen init { sem = 10; } // Dies ist der Prozess fuer ein Auto Auto { P(sem); // Auto parkt ein enterPH; //Auto verlaesst Parkplatz (evtl: exitPH;) V(sem); }