0! = 1
0! = 1
4! = 4 ∗ 3 ∗ 2 ∗ 1
4! = 4 ∗ 3 ∗ 2 ∗ 1
⃝
⃝
BSRvS1 Last Chance Test A0 – Erste Schritte in C Name: Max Mustermann Matrikelnummer: 10000
A0 – Erste Schritte in C
Maximal mögliche Gesamtpunktzahl für dieses Blatt: 20 Punkte. Zum Bestehen werden 50% der maximal möglichen Punkte benötigt. Bei allen Multiple-Choice-Fragen im Test zu A0 ist jeweils nur eine Antwort richtig.
1. Vervollständigen Sie Zeile 3 des folgenden Listings, das die Adresse einer Variable im Speicher ausgeben soll. (2 Punkte)
1 int main(void) { 2 intx;
3 printf (“x liegt an Adresse %p im Speicher\n” , (void ∗) &x );
4 return 0; /∗ Es i s t auch okay , den Cast wegzulassen . ∗/
5}
2. Auf einem x86-System werden innerhalb einer Funktion f() eines C-Programmes nacheinander zwei Variablen (a und b) vom Typ int angelegt und mit printf(3) ihre Adressen im Speicher ausgegeben:
a liegt an Adresse 0xffb89608 im Speicher b liegt an Adresse 0xffb89604 im Speicher
Wieso ist der Abstand der beiden Adressen gleich 4, und warum ist die zweite Adresse kleiner als die erste? Warum kann es passieren, dass bei einem zweiten Aufruf der Funktion f() andere Adressen ausgegeben werden? (5 Punkte)
Beides sind lokale Variablen, sie werden daher nacheinander auf dem Stack angelegt. Auf 32-Bit- Maschinen hat ein int die Größe 4 Bytes, was den Abstand erklärt.
Bei einem zweiten Aufruf der Funktion kann der Stack völlig anders aussehen – der Aufruf kann auch aus einem völlig anderen Programmteil erfolgen, somit auch der Stack-Pointer beim Betreten der Funktion einen ganz anderen Wert haben. Die Adressen der lokalen Variablen hängen natürlich von diesem Initialwert ab.
3. Was gibt folgendes C-Programm aus, wenn man es übersetzt und ausführt? (3 Punkte)
#include
int square(int x) { return x∗x; } int main(void) {
inti;
for (i=0; i<4; i++){
printf("%d ", square(square(i ))); printf ("\n");
}
Ausgabe: 0 1 16 81
}
return 0;
⃝c 2009 TU Dortmund, Informatik 12, Arbeitsgruppe ESS, Blatt 1 von 2
BSRvS1 Last Chance Test A0 – Erste Schritte in C
4. Aus der man-Page zu welchem Standard-UNIX-Kommando ist folgende Beschreibung entnommen? „Gib Zeilen-, Wort- und Byteanzahl für jede DATEI aus und eine Gesamtzeile, wenn mehr als eine DATEI angegeben wurde.“ (DATEI ist ein Parameter für das Kommando.) (1 Punkt)
ls x wc
cat grep
5. Mit welchem Befehl werden die Zugriffsrechte für das Verzeichnis „foo“ sowie dessen Unterverzeichnisse geändert? (1 Punkt)
rmdir foo/
mv -i foo/ bar/
x chmod -R o+r foo/
id foo/
6. In welchen Speichersegmenten befinden sich die Funktion f() und die Variablen a, b, c und d im
Speicherlayout des folgenden Programms? (5 Punkte)
int a;
char b[] = "Hello , World!";
int f(void) { intc=1;
return 0;
}
7. Der Aufruf des Unix-Kommandos "ps" erzeuge folgende Ausgabe:
PID TTY 3522 pts/1 8780 pts/1 14348 pts/1
TIME CMD 00:00:00 bash
00:00:13 gedit 00:00:00 ps
Der Prozess des Editors gedit reagiert auf keine Eingabe mehr. Was würden Sie in einer UNIX- Shell eingeben, um den Prozess zu beenden? (3 Punkte)
kill 8780
a: float d; b:
Text- oder Codesegment BSS
Datensegment Stacksegment Stacksegment
Bezeichnung des jeweiligen Speichersegments:
f:
c:
d:
⃝c 2009 TU Dortmund, Informatik 12, Arbeitsgruppe ESS, Blatt 2 von 2
BS Last Chance Test A0 Erste Schritte in C
Name: Max Mustermann Matrikelnummer: 10000
A0 Erste Schritte in C
Maximal mögliche Gesamtpunktzahl für dieses Blatt: 22 Punkte. Zum Bestehen werden 50% der maximal möglichen Punkte benötigt. Bei allen Multiple-Choice-Fragen im Test zu A0 ist jeweils nur eine Antwort richtig.
1. Vervollständigen Sie folgendes Listing in Zeile 4 und 5 so, dass in einer weiteren Adress-Variable p die Adresse von x abgelegt und anschlieÿend ausgegeben wird. (2 Punkte)
1 int main(void) {
2 int x = 43;
3# int∗p=&x;
4 # printf("Die Adresse von x ist: %p\n", (void ∗)p); 5 return 0;
6}
2. Gegeben sei die folgende Funktion ffoo(n).
unsigned ffoo(unsigned n) { unsigned i, j, ergebnis = 0; for (i = 0; i < n; i++)
for (j = 0; j < i; j++) ergebnis += j * i;
return ergebnis; }
Schreiben Sie die Funktion so um, dass sie nur while- und keine for-Schleifen verwendet. Dabei soll natürlich gelten ∀n : ffoo(n) = wfoo(n), die umgeschriebene Funktion wfoo(n) soll also das Gleiche berechnen. (6 Punkte)
unsigned wfoo(unsigned n) { unsigned i, j, ergebnis = 0; i = 0;
while (i < n) {
j = 0;
while (j < i) {
ergebnis += j * i;
j++; }
i++; }
return ergebnis; }
3. Was gibt folgendes C-Programm aus, wenn man es übersetzt und ausführt? (5 Punkte)
⃝c 2010 TU Dortmund, Informatik 12, Arbeitsgruppe ESS, Blatt 1 von 2
BS
Last Chance Test
A0 Erste Schritte in C
4.
5.
6.
#include
int div(int x) { return x/2; } int main(void) {
inti;
for (i = −2; i < 3; i++)
printf("%d ", div(i)); return 0;
}
Ausgabe: -1 0 0 0 1 Anm.: ganzzahlige Division!
Mit welchem der folgenden UNIX-Programme lässt sich eine Liste aller derzeit laufenden Prozesse anzeigen? Kreuzen Sie bei J (ja, zutreend) oder N (nein, nicht zutreend) an! (1 Punkt)
JN
X kill
X ln X ps X lp
Womit wird der aktuell angemeldete Benutzer ausgegeben? Kreuzen Sie wieder bei J (ja, zutreend) oder N (nein, nicht zutreend) an! (1 Punkt)
JN
X me
X you X who
X foo
In welchen Speichersegmenten benden sich die Funktion h() und die Variablen g, k, i und p im
Speicherlayout des folgenden Programms? (5 Punkte)
7.
Sie sollen bei der Bearbeitung einer C-Programmieraufgabe zur Ausgabe die Funktion printf(3) verwenden, wissen jedoch nicht, wie Sie diese aufrufen sollen, da Sie die Semantik der Argumente nicht kennen. Was würden Sie in einer UNIX-Shell eingeben, um sich Klarheit zu verschaen? (2 Punkte)
man 3 printf
static const int g = 10; char k[100];
int h(unsigned i) {
int ∗p = malloc(i+g); free(p);
return 0;
}
Bezeichnung des jeweiligen Speichersegments: g: Datensegment
k: BSS
i: Stack
h: Text
p: p selbst: Stack; Speicher, auf den p zeigt: Heap
⃝c 2010 TU Dortmund, Informatik 12, Arbeitsgruppe ESS, Blatt 2 von 2
BS Last Chance Test A0 Erste Schritte in C
Name: Matrikelnummer:
A0 Erste Schritte in C
Maximal mögliche Gesamtpunktzahl für dieses Blatt: 23 Punkte. Zum Bestehen werden 50% der maximal möglichen Punkte benötigt.
1. Vervollständigen Sie folgendes Listing in Zeile 3 und 4 so, dass in einer Adress-Variable p die Adresse von x abgelegt und anschlieÿend ausgegeben wird. (2 Punkte)
1 int main(void) {
2 int x = 42;
3# int∗p=&x;
4 # printf("Die Adresse von x ist: %p\n", (void ∗)p); 5 return 0;
6}
2. Auf einem x86-System werden innerhalb einer Funktion f() eines C-Programmes nacheinander zwei Variablen (x und y) vom Typ char angelegt und mit printf(3) ihre Adressen im Speicher ausgegeben:
x liegt an Adresse 0xbfe28313 im Speicher y liegt an Adresse 0xbfe28312 im Speicher
Wieso ist der Abstand der beiden Adressen gleich 1, und warum ist die zweite Adresse kleiner als die erste? Warum kann es passieren, dass bei einem zweiten Aufruf der Funktion f() andere Adressen ausgegeben werden? (5 Punkte)
Beides sind lokale Variablen, sie werden daher nacheinander auf dem Stack angelegt. Auf 32-Bit- Maschinen hat ein char die Gröÿe von einem 1 Byte, was den Abstand erklärt. Die zweite Adresse ist kleiner, weil (zumindest auf x86) der Stack nach unten wächst.
Bei einem zweiten Aufruf der Funktion kann der Stack völlig anders aussehen der Aufruf kann auch aus einem völlig anderen Programmteil erfolgen, somit auch der Stack-Pointer beim Betreten der Funktion einen ganz anderen Wert haben. Die Adressen der lokalen Variablen hängen natürlich von diesem Initialwert ab.
3. Was gibt folgendes C-Programm aus, wenn man es übersetzt und ausführt? (3 Punkte)
#include
if (a == 0) { return b; } while (b != 0) {
if (a > b) { a = a-b; }
else { b = b-a; } }
return a; }
int main(void) {
printf(“%d\n”, t(6,18));
return (0); }
⃝c 2011 TU Dortmund, Informatik 12, Arbeitsgruppe ESS, Blatt 1 von 3
BS
Last Chance Test A0 Erste Schritte in C
4.
Schreiben Sie die Funktion t() in der Aufgabe 3 so um, dass die Berechnungen rekursiv durchgeführt werden. Die umgeschriebene Funktion soll das Gleiche berechnen. (3 Punkte)
int t(int a, int b) { if (a == 0) {
5.
Mit welchem der folgenden UNIX-Programme lässt sich eine Liste aller derzeit laufenden Prozesse anzeigen? Kreuzen Sie bei J (ja, zutreend) oder N (nein, nicht zutreend) an! Jeweils nur eine Antwort ist richtig. (2 Punkt)
JN
X kill
X ln X ps X lp
Mit welchem UNIX-Kommando (evtl. mit Optionen) wird ein Verzeichnis “test” inklusive der enthalte- nen Dateien und Unterverzeichnisse rekursiv gelöscht? Jeweils nur eine Antwort ist richtig. (1 Punkt)
ls -R test X rm -r test rmdir test del ./test
In welchen Speichersegmenten benden sich die Funktion r() und die Variablen a, b, i und p im Speicherlayout des folgenden Programms? (5 Punkte)
Ausgabe: 6
return b;
} else if (b return a; } else if (a > return t((a
} else { return t(a,
} }
== 0) {
b) {
– b), b);
(b – a));
6.
7.
8.
Sie sollen bei der Bearbeitung einer C-Programmieraufgabe zur Texteingabe die Funktion scanf(3) verwenden, wissen jedoch nicht, wie Sie diese aufrufen sollen, da Sie die Semantik der Argumen-
static const int a = 0xD431; char b; a: int r(unsigned i) {
Bezeichnung des jeweiligen Speichersegments:
Datensegment BSS
Stack
Text
Stack
int ∗p;
p = &i ; ∗p = 47; return 0;
}
b: i: r: p:
⃝c 2011 TU Dortmund, Informatik 12, Arbeitsgruppe ESS, Blatt 2 von 3
BS Last Chance Test A0 Erste Schritte in C
te nicht kennen. Was würden Sie in einer UNIX-Shell eingeben, um sich Klarheit zu verschaen? (2 Punkte)
man 3 scanf
⃝c 2011 TU Dortmund, Informatik 12, Arbeitsgruppe ESS, Blatt 3 von 3
⃝
⃝
→
→
BSRvS1 Last Chance Test A1 Prozesse
Name: Max Mustermann Matrikelnummer: 10000
A1 Prozesse
Maximal mögliche Gesamtpunktzahl für dieses Blatt: 20 Punkte. Zum Bestehen werden 50% der maximal möglichen Punkte benötigt.
1. Tragen Sie die Namen der entsprechenden UNIX-Systemaufrufe ein. (4 Punkte) fork erzeugt einen Kindprozess
exit dient einem Prozess dazu, sich selbst zu beenden
getpid liefert die Prozess-ID des laufenden Prozesses
execlp lädt und startet ein Programm im Kontext des laufenden Prozesses
2. Was gibt folgendes C-Programm aus, wenn man es übersetzt und ausführt? Die Include-Direktiven und Fehlerabfragen wurden der Einfachheit halber weggelassen, gehen Sie von einer fehlerfreien Abar- beitung aller Systemaufrufe aus. Hinweis: 2x nachdenken. (4 Punkte)
int main(void) { int x = 10;
if (fork() == 0) { /∗ Kind ∗/ x=x∗2;
} else { /∗ Vater ∗/ x −−;
wait(NULL); /∗ auf die Terminierung des Kindes warten ∗/ printf(“%d\n”, x);
}
return 0;
}
Ausgabe: 20 9 (eigentlich mit Zeilenumbruch dazwischen und danach)
3. Erklären Sie, weshalb es auf UNIX-Systemen sogenannte Zombies geben kann. (1,5 Punkte)
Ein Zombie ist ein terminierter Prozess, für den sein Vaterprozess noch nicht wait/waitpid aufgerufen und damit seinen Exit-Status abgerufen hat. Solange dies nicht geschieht, belegt der Zombie weiter u.a. seine Prozess-ID und Speicher im Systemkern.
4. Welche Rolle spielt der Init-Prozess im Zusammenhang mit Zombies? (1,5 Punkte)
Sobald der Vaterprozess eines Prozesses terminiert, wird letzterer automatisch Kind von ‘Init’ (PID 1), welcher in jedem UNIX-System ständig läuft und u.a. nötigenfalls wait/waitpid aufruft.
5. Erklären Sie knapp in eigenen Worten, was präemptives von nicht-präemptivem Scheduling unter- scheidet. Nennen Sie für beide Varianten beispielhaft jeweils eine Scheduling-Strategie. (3 Punkte)
präemptiv: Prozesse werden dazu gedrängt, die CPU abzugeben (z.B. Timer-Unterbrechung) (RR, VRR, SRTF, HRRN, FB)
nicht-präemptiv: Prozesse geben freiwillig die CPU ab, Kooperation (FCFS, SPN, SJF)
⃝c 2009 TU Dortmund, Informatik 12, Arbeitsgruppe ESS, Blatt 1 von 2
BSRvS1 Last Chance Test A1 Prozesse
6. Welches Problem tritt bei Round-Robin-Scheduling evtl. auf, und wie wird dies durch Virtual Round Robin vermieden? (4 Punkte)
Problem bei RR:
ungleiche Verteilung der CPU-Zeit zugunsten CPU-lastiger Prozesse (E/A-lastige geben die CPU immer schon vor Ende ihrer Zeitscheibe ab!) → E/A-lastige Prozesse werden schlecht bedient, Geräte schlecht ausgelastet
Vermeidung in VRR:
Vorzugsliste, in die Prozesse nach Beendigung ihrer E/A-Stöÿe kommen; wird vor der normalen Ready- Liste abgearbeitet→ Zeitscheiben unterschiedlicher Längen, da die Prozesse in der Vorzugsliste nur ihre Restlaufzeit bekommen!
7. Zeichnen Sie das Prozess-Zustandsdiagramm mit den drei grundlegenden Zuständen READY, RUN- NING und BLOCKED und den gültigen Zustandsübergängen. (2 Punkte)
⃝c 2009 TU Dortmund, Informatik 12, Arbeitsgruppe ESS, Blatt 2 von 2
BS Last Chance Test A1 Prozesse
Name: Max Mustermann Matrikelnummer: 10000
A1 Prozesse
Maximal mögliche Gesamtpunktzahl für dieses Blatt: 23 Punkte. Zum Bestehen werden 50% der maximal möglichen Punkte benötigt.
1. Tragen Sie jeweils den Namen eines entsprechenden UNIX-Systemaufrufes ein. (4 Punkte)
execlp lädt und startet ein Programm im Kontext des laufenden Prozesses getppid liefert die Prozess-ID des Vaterprozesses
sleep legt den Prozess für eine bestimmte Zeit schlafen
wait gibt die Ressourcen eines Zombies wieder frei
2. Ordnen Sie die Ihnen bekannten Standard-E/A-Kanäle den folgenden C-Bibliotheksfunktionen zu. (1,5 Punkte)
perror() stderr printf() stdout scanf() stdin
3. Was gibt folgendes C-Programm aus, wenn man es übersetzt und ausführt? Die Include-Direktiven und Fehlerabfragen wurden der Einfachheit halber weggelassen, gehen Sie von einer fehlerfreien Ab- arbeitung aller Systemaufrufe aus. Hinweis: 2x nachdenken. (4 Punkte)
int main(void) { intx=2;
if (fork() == 0) { /∗ Kind ∗/ x=x+2;
} else { /∗ Vater ∗/ x −−;
wait(NULL); /∗ auf die Terminierung des Kindes warten ∗/ printf(“%d\n”, x);
Ausgabe: 4 1 (Anm.: mit Newline dazwischen)
4. Ordnen Sie die folgenden Schedulingverfahren durch Ankreuzen den Kategorien zu. (2,5 Punkte)
}
}
return 0;
präemptiv
Verhungern möglich
vorhersagebasiert
X X
RR (Round Robin) X
HRRN (Highest Response Ratio Next)
VRR (Virtual Round Robin) X
SRTF (Shortest Remaining Time First) X X FCFS (First-Come First-Served)
⃝c 2010 TU Dortmund, Informatik 12, Arbeitsgruppe ESS, Blatt 1 von 2
BS
Last Chance Test A1 Prozesse
5.
Schnelle Prozesserzeugung: Da das Kopieren des Adressraums etwa bei einem Aufruf von fork() ver- gleichsweise viel Zeit kostet, verwendet man heutzutage ein Verfahren, bei dem sich Eltern- und Kindprozess das Code- und Datensegment mit Hilfe der MMU teilen. Erst, wenn das Kind Daten verändert, wird das Segment kopiert. Wie heiÿt dieses Verfahren? (2 Punkte)
Copy-on-write
6. Welche Rolle spielt der Init-Prozess im Zusammenhang mit Zombies? (2 Punkte)
Ein Prozess, dessen Vaterprozess terminiert, wird automatisch zum Kindprozess von Init (Prozess- ID 1). Sobald dieser Prozess ebenfalls terminiert, räumt Init ihn weg, so dass kein Zombie zurückbleibt.
7. Scheduling: Kreuzen Sie bei J (ja, zutreend) oder N (nein, nicht zutreend) für die folgenden Fragen an. (2,5 Punkte)
JN
X X
X X
X
Ein Prozess kann beim präemptiven Scheduling so lange rechnen, bis er die Kontrolle über den Prozessor freiwillig abgibt.
Bei RR (Round Robin) bekommt der Prozess als nächstes die CPU, welcher ganz vorne in der Bereit-Warteschlange steht.
HRRN (Highest Response Ratio Next) bevorzugt Prozesse mit kurzen E/A-Stöÿen. VRR (Virtual Round Robin) is präemptiv.
Für FB (Feedback) müssen die Ausführungszeiten der Prozesse vorher bekannt sein.
8. Ergänzen
gänge und beschreiben Sie jeweils kurz, durch welches Ereignis der jeweilige Zustandsübergang aus- gelöst wird. Als Beispiel ist der Übergang vom Zustand aktiv zu blockiert bereits vorgegeben. (4,5 Punkte)
Zustandsübergang 1 aktiv → blockiert: Der aktive Prozess startet einen E/A-Vorgang. Zustandsübergang 2 blockiert → bereit: Der E/A-Vorgang ist beendet, wodurch der Prozess wieder
laufbereit wird.
Zustandsübergang 3 aktiv → bereit: Der gerade aktive Prozess wird verdrängt (oder gibt freiwillig die CPU ab), ein anderer Prozess aus der Ready-Liste wird vom Scheduler ausgewählt.
Zustandsübergang 4 bereit → aktiv: Ein bereiter, aber gerade nicht laufender Prozess wird vom Scheduler ausgewählt.
Sie im untenstehenden Prozesszustandsdiagramm mit drei Zuständen die fehlenden Über-
⃝c 2010 TU Dortmund, Informatik 12, Arbeitsgruppe ESS, Blatt 2 von 2
BS Last Chance Test A1 Prozesse
Name: Matrikelnummer:
A1 – Prozesse
Maximal mögliche Gesamtpunktzahl für dieses Blatt: 20 Punkte. Zum Bestehen werden 50% der maximal möglichen Punkte benötigt.
1. Beschreiben sie kurz mit eigenen Worten wie Prozesse bei präemptivem Scheduling bzw. beim Round- Robin-Verfahren verwaltet werden. (3 Punkte)
• Präemptives Scheduling
Ein Prozess kann dazu gedrängt werden, die CPU abzugeben.
• Round Robin Verfahren
Prozesse bekommen eine Zeitscheibe zugeteilt. Mit Ablauf der Zeitscheibe erfolgt ggf. ein Prozess-
wechsel.
2. Tragen Sie jeweils den Namen eines entsprechenden UNIX-Systemaufrufes ein. (4 Punkte)
fork erzeugt einen Kindprozes
getpid liefert die Prozess-ID des laufenden Prozesses
sleep legt den Prozess für eine bestimmte Zeit schlafen waitpid/wait gibt die Ressourcen eines Zombies wieder frei
3. Welche Aussagen treen zu?
(Mehrfachnennungen sind möglich, falsche Antworten geben Punktabzug) (3 Punkte)
X
X
X
exec() startet ein Programm.
fork() beendet das laufende Programm.
fork() erzeugt einen neuen Prozess.
fork() erzeugt für das Kind eine ID. Diese ist identisch zur ID des Vaters.
waitpid() erlöst Zombies.
4. Wie viele Prozesse werden beim Starten dieses Programms erzeugt? (Der erste Prozess zählt mit! Eine Skizze ist hier hilfreich.) (3 Punkte)
int main () { i n t i ;
Antwort:
}
for (i = 0; i < 4; i++) fork ();
return 0;
16 Prozesse (Hinweis: Die Antwort ist zweistellig!)
⃝c 2011 TU Dortmund, Informatik 12, Arbeitsgruppe ESS, Blatt 1 von 2
BS
Last Chance Test A1 Prozesse
5. Bei welchem der folgenden Schedulingverfahren ist ein Verhungern einzelner Prozesse möglich? (nur eine Antwort richtig!) (2 Punkte)
FCFS (First Come First Served)
X SRTF (Shortest Remaining Time First)
HRRN (Highest Response Ratio Next) RR (Round Robin)
Zeichnen Sie das Prozess-Zustandsdiagramm mit den drei grundlegenden Zuständen READY, RUNNING und BLOCKED und den gültigen Zustandsübergängen. (2 Punkte)
1. Was gibt folgendes C-Programm aus, wenn man es übersetzt und ausführt? Die Include-Direktiven und Fehlerabfragen wurden der Einfachheit halber weggelassen, gehen Sie von einer fehlerfreien Ab- arbeitung aller Systemaufrufe aus. Hinweis: 2x nachdenken. (3 Punkte)
int main(void) { int x = 21;
if (fork() == 0) { /∗ Kind ∗/ x=x∗2;
} else { /∗ Vater ∗/ x −−;
wait(NULL); /∗ auf die Terminierung des Kindes warten ∗/ printf("%d\n", x);
}
Ausgabe: 42 20
}
return 0;
⃝c 2011 TU Dortmund, Informatik 12, Arbeitsgruppe ESS, Blatt 2 von 2
BSRvS1 Last Chance Test A2 – Synchronisation
Name: Max Mustermann Matrikelnummer: 10000
Maximal mögliche Gesamtpunktzahl für dieses Blatt: 20
Zum Bestehen werden 50% der maximal möglichen Punkte benötigt.
Bei den Multiple-Choice-Aufgaben können grundsätzlich mehrere Antworten richtig und anzukreuzen sein.
1. In einem Verzeichnis liegen ein Makefile und verschiedene C-Quelltexte (senf.c, ketchup.c, broetchen.c und bratwurst.c). Der Inhalt des Makefiles ist unten angegeben. Welche Dateien werden durch den Aufruf von „make bratwurstbroetchen“ erzeugt? (Bitte erzeugte Dateien ankreuzen) (2,5 Punkte)
Makefile erzeugte Dateien
bratwurstbroetchen: bratwurst broetchen
senf.o: senf.c
gcc -c -o senf.o senf.c
broetchen: broetchen.c
gcc -o broetchen broetchen.c
ketchup.o: ketchup.c
gcc -c -o ketchup.o ketchup.c
bratwurst: bratwurst.c senf.o
gcc -o bratwurst bratwurst.c senf.o
x bratwurst x broetchen
bratwurstbroetchen x senf.o
ketchup.o
• das Target bratwurstbroetchen erzeugt selbst keine Datei
• bratwurstbroetchen benötigt bratwurst und broetchen (werden erzeugt) • bratwurst benötigt senf.o (wird erzeugt)
2. Gegeben sei eine 5-elementige System-V-Semaphormenge mit der ID 4711, deren letzter Semaphor mit 3 initialisiert ist.
a) Füllen Sie die Lücken in der unten angegebenen Funktion so, dass diese eine V-Operation auf dem letzten Semaphor der genannten Semaphormenge ausführt. (Signatur der Funktion semop(2): int semop(int semid, struct sembuf *sops, unsigned nsops)) (2 Punkte)
void my_v() {
struct sembuf sop;
sop.sem_num = 4;
sop.sem_flg = 0;
sop.sem_op = 1;
if ( semop(4711, &sop, 1) ) {
perror("my_v()");
exit(1); }
}
b) Es existiere nun eine entsprechende Funktion my_p() für die P-Operation. Welchen Wert hat der (mit 3 initalisierte!) Semaphor nach Beendigung des Prozesses? (Es wird angenommen, das kein anderer Prozess zwischenzeitlich auf die Semaphore zugreift) (2 Punkte)
int main(void) {
...
my_p(); my_p(); my_v(); my_p(); my_p(); my_v();
return 0; }
Antwort: 1
⃝c 2009 TU Dortmund, Informatik 12, Arbeitsgruppe ESS, Blatt 1 von 2
BSRvS1 Last Chance Test A2 – Synchronisation
3. Was versteht man unter passivem Warten? Erläutern Sie diesen Begriff kurz. Beschreiben Sie kurz,
was dabei passiert. (3 Punkte)
• passives Warten: Prozess wird von der CPU-Zuteilung ausgeschlossen
– Prozess blockiert: kommt auf eine separate Warteliste
– erwartetes Ereignis tritt ein: Prozess kommt wieder auf Bereitliste des Schedulers
4. Worin besteht der Nachteil von aktivem gegenüber passivem Warten? (2 Punkte)
• Prozesse, die sinnvoll arbeiten könnten, werden behindert
• Wartender schadet sich selbst, da er andere davon abhält, die Bedingung zu erfüllen, auf die er
wartet
5. Welche der folgenden Aussagen über Semaphore sind falsch? (2 Punkte)
x Wenn zwei Prozesse gleichzeitig P() auf einem Semaphor mit Wert 1 aufrufen, blockieren beide. x Die P()-Operation kann nur mittels aktivem Warten realisiert werden.
Mit Semaphoren kann gegenseitiger Ausschluss realisiert werden.
x Es darf niemals mehr als ein Semaphor innerhalb des selben Fadens benutzt werden.
6. Der rechte und linke Programmausschnitt wird jeweils von verschiedenen Fäden ausgeführt. Ihnen ste- hen zwei Semaphore (x und y) zur Verfügung. Sorgen Sie in jeder Teilaufgabe durch die entsprechen- de Initalisierung der Semaphore und durch Einfügen von Semaphor-Operationen (p(&x), p(&y), v(&x), v(&y)) innerhalb oder außerhalb der Schleifen dafür, dass die beiden Fäden zusammen die gewünschte Ausgabe machen. (Hinweis: es müssen nicht zwingend beide Semaphore benutzt werden.)
a) gewünschte Ausgabe: aaaaaabbbbbb (2,5 Punkte)
int i;
for (i=0; i<6; i++)
{
printf("a");
} v(&x)
int i;
p(&x)
for (i=0; i<6; i++)
{
printf("b");
}
Hier bitte die Initialwerte der Semaphore eintragen:
x=0 y=-
Die Semaphoroperationen bitte direkt links in den Quelltext einfügen.
b) gewünschte Ausgabe: babababababa (4 Punkte)
int i;
for (i=0; i<6; i++)
{
p(&x);
printf("a");
v(&y);
}
int i;
for (i=0; i<6; i++)
{
p(&y)
printf("b");
v(&x)
}
Hier bitte die Initialwerte der Semaphore eintragen:
x=0 y=1
Die Semaphoroperationen bitte direkt links in den Quelltext einfügen.
⃝c 2009 TU Dortmund, Informatik 12, Arbeitsgruppe ESS, Blatt 2 von 2
BS Last Chance Test A2 Synchronisation
Name: Max Mustermann Matrikelnummer: 10000
A2 Synchronisation
Maximal mögliche Gesamtpunktzahl für dieses Blatt: 21,5 Punkte. Zum Bestehen werden 50% der maximal möglichen Punkte benötigt.
1. In folgendem Pseudocode-Abschnitt benutzen die beiden nebenläugen Prozesse erzeuger() und ver- braucher() einen gemeinsamen Ringpuer, der bis zu 42 Elemente aufnehmen kann. Gehen Sie davon aus, dass das Einfügen und Entnehmen von Elementen in diesen bzw. aus diesem Puer atomar erfolgt.
Buffer gemeinsamerPuffer (42);
sem_frei = 42; sem_belegt = 0;
erzeuger () { while (1) {
Element e = produziereElement ();
P(sem_frei ); gemeinsamerPuffer.enqueue(e);
V( sem_belegt ) ;
} }
verbraucher () { while (1) {
Element e ;
/∗ schreibe in gemeinsamen Puffer ∗/
P( sem_belegt ) ;
e = gemeinsamerPuffer.dequeue(); /∗ lies aus gemeinsamem Puffer ∗/
V(sem_frei );
verbraucheElement (e ); }
}
a) Welche zwei Probleme treten auf, wenn die beiden Prozesse ohne weitere Synchronisationsmaÿ- nahmen ablaufen? (3 Punkte)
i. Der Verbraucher verbraucht schneller Elemente, als der Erzeuger sie erzeugen kann (und versucht dabei, aus einer leeren Queue zu lesen).
ii. Der Erzeuger erzeugt schneller Elemente, als der Verbraucher sie verbrauchen kann (und versucht dabei, neue Elemente in eine bereits volle Queue zu schieben).
b) Verwenden Sie geeignet initialisierte Semaphore und die Semaphor-Operationen P und V, um die beiden Prozesse zu synchronisieren. (Bitte direkt oben im Code einfügen. Die Notation ist irrelevant, Pseudocode genügt.) (4 Punkte)
⃝c 2010 TU Dortmund, Informatik 12, Arbeitsgruppe ESS, Blatt 1 von 2
BS
Last Chance Test A2 Synchronisation
2.
Welche der folgenden Aussagen über Semaphore treen zu? (Mehrfachauswahl möglich) (3,5 Punkte) JN
X X
X X
X
X X1
Wenn zwei Prozesse gleichzeitig P() auf einem Semaphor mit Wert 1 aufrufen, blockieren beide.
Gegenseitiger Ausschluss kann mit Semaphoren realisiert werden.
Die zwei möglichen Semaphor-Operationen sind atomar.
Es darf niemals mehr als ein Semaphor innerhalb des selben Fadens benutzt werden. Semaphore basieren auf dem Prinzip des passiven Wartens.
Die Semaphor-Operation V bzw. signal erhöht eine Semaphor-Variable immer um 1. Der Bäckerei-Algorithmus ist ein Verfahren zum aktiven Warten.
3.
4.
5.
Nennen Sie jeweils einen Prozesszustand, in dem sich ein Prozess benden kann, der gerade aktiv bzw. passiv auf eine Ressource wartet. (2 Punkte)
wartet aktiv:
aktiv (running) (oder bereit (ready))
wartet passiv:
blockiert (waiting)
Erklären Sie den Begri Race Condition stichpunktartig mit eigenen Worten. (3 Punkte)
mehrere Prozesse greifen konkurrierend auf dieselben Daten zu und ändern diese
bei einer Race Condition hängt der resultierende Wert der Daten davon ab, welcher Prozess zuletzt zugegrien hat
→ Ergebnis nicht vorhersagbar, möglicherweise inkorrekt
Wie oft gibt folgendes, kurzes C-Programm den Buchstaben X aus? Die Semaphore sem ist mit dem
Wert 4 initialisiert. (3 Punkte)
int main(void) { for ( ; ; ) {
}
p r i n t f ( "X\ n " ) ; P(&sem);
}
p r i n t f ( "X\ n " ) ; return 0;
Anzahl der Xe:
5
6.
Auf x86-CPUs können mit Hilfe der Instruktionen cli und sti Unterbrechungen gesperrt werden, wo- durch der gegenseitige Ausschluss zweier Prozesse realisiert werden könnte. Weshalb ist das von groÿem Nachteil (und daher unter gängigen Betriebssystemen für Benutzerprozesse nicht möglich)? (3 Punkte)
Dadurch werden alle Prozesse (nicht nur die, die sich synchronisieren möchten) und das Betriebssystem selbst beeinträchtigt.
1
Hierüber lässt sich streiten: Das ist wohl implementierungsabhängig. Wenn ein anderer Prozess auf eine Semaphore mit dem Wert 0 (mittels P) wartet, könnte diese bei V dennoch kurz den Wert 1 einnehmen.
⃝c 2010 TU Dortmund, Informatik 12, Arbeitsgruppe ESS, Blatt 2 von 2
BS Last Chance Test A2 – Synchronisation Name: Matrikelnummer:
A2 – Synchronisation
Maximal mögliche Gesamtpunktzahl für dieses Blatt: 17,5 Punkte. Zum Bestehen werden 50% der maximal möglichen Punkte benötigt.
1. Gegeben sei eine System-V-Semaphormenge.
a) Füllen Sie die Lücken in der unten angegebenen Funktion so, dass diese eine P-Operation auf dem 3. Semaphor der genannten Semaphormenge mit der ID 4242 ausführt. (Signatur der Funktion semop(2): int semop(int semid, struct sembuf *sops, unsigned nsops)) (3 Punkte)
void my_p() {
struct sembuf sop;
sop.sem_num = 2;
sop.sem_op = -1;
sop.sem_flg = 0;
if (semop(4242,&sop,1) < 0) {
perror("my_p()");
exit(1); }
}
b) Es existiere nun eine entsprechende Funktion my_p() für die P-Operation. Welchen Wert hat der mit 4 initialisierte Semaphor nach Beendigung des Prozesses? (Es wird angenommen, das kein anderer Prozess zwischenzeitlich auf die Semaphore zugreift) (1 Punkte)
int main(void) {
...
my_v(); my_p(); my_p(); my_v(); my_p(); my_p(); my_v();
return 0; }
Antwort: 3
2. Welche der folgenden Aussagen treffen zu? Kreuzen Sie J (ja, zutreffend) oder N (nein, nicht zutref-
fend) an! (3,5 Punkte) JN
X X
X
X
X
X
X
Eine Race Condition sorgt für eine Synchronisation der konkurrierenden Prozesse. Schlossalgorithmen behindern unnütz andere Prozesse, die sinnvolle Arbeit leisten könnten.
Beim passiven Warten geben die Prozesse die Kontrolle über die CPU ab, während sie auf Ereignisse warten.
Wird auf einem Semaphor mit dem Wert 0 die P-Operation ausgeführt, wird ggf. ein blockierter Prozess deblockiert.
Eine Synchronisation bringt die Aktivitäten verschiedener nebenläufiger Prozesse in eine Reihenfolge.
Synchronisation mit Monitor-Variablen basiert auf dem Prinzip des aktiven Wartens. Der Bäckerei-Algorithmus verteilt Wartenummern und der Prozess mit der niedrigsten Wartenummer darf als nächstes den kritischen Abschnitt betreten.
⃝c 2011 TU Dortmund, Informatik 12, Arbeitsgruppe ESS, Blatt 1 von 2
BS 3.
4.
Last Chance Test A2 – Synchronisation
Welche zwei Probleme können auftreten, wenn Semaphoren beim Beenden eines Programms nicht
gelöscht werden(im UNIX System-V Kontext)? (2 Punkte)
Die Semaphoren verbleiben im Speicher und beim erneuten Start des Programms werden die alten
Semaphoren weiter verwendet oder lassen sich nicht anlegen, da sie schon vorhanden sind.
Zwei Prozesse P1 und P2 interagieren über einen gemeinsamen Speicher, der Platz für ein Einzelbild aus einem Video hat. P1 erzeugt in unregelmäßigen Abständen solche Bilder und schreibt sie in den gemeinsamen Speicher. P2 liest sie von dort aus. Es muss nun für Synchronisation gesorgt werden, da P1 keinen Bild überschreiben darf, das noch nicht von P2 gelesen wurde. Außerdem muss P2 jeweils mit dem Lesen warten bis ein neues Bild im gemeinsamen Speicher eingetroffen ist.
a) Wie nennt man dieses Synchronisationsproblem? (1 Punkt) Erzeuger-Verbraucher-Problem
a) Wieviele klassische (nicht System V!) Semaphore würde man für die Synchronisation benötigen und welche Initialwerte müssten sie bekommen? (2 Punkte)
2 Semaphore (initialisiert mit 0 "nicht_leer" bzw. 1 "nicht_voll"), oder 1 binäre Semaphor (initialisiert mit 1)
a) Beschreiben Sie kurz wann (bevor/nach dem Speicherzugriff) Prozess 1 bzw. Prozess 2 welche Semaphoroperation aufruft. (2 Punkte)
P1: p(&nicht_voll); schreiben(); v(&nicht_leer); P2: p(&nicht_leer); lesen(); v(&nicht voll);
Betrachtet das folgende Szenario. Es wurde bereits make all für den folgenden Makefile ausgeführt. Welche Dateien werden bei einem erneuten Aufruf von make all neu erstellt, wenn zuvor kuehlschrank.h verändert wurde? (2 Punkte)
CC=gcc GCC_OPTS=-Wall -ansi -pedantic -D_XOPEN_SOURCE -D_POSIX_SOURCE
all: greifarm student
greifarm: greifarm.c kuehlschrank.h kuehlschrank.c
$(CC) $(GCC_OPTS) -o greifarm greifarm.c kuehlschrank.c
student: student.c kuehlschrank.h kuehlschrank.c
$(CC) $(GCC_OPTS) -o student student.c kuehlschrank.c
greifarm und student.
5.
6. Erkläre den Begriff Race Condition (oder auch Wettkampfbedingung). (3 Punkte)
Bei einer Race Condition greifen mehrere Prozesse konkurrierend auf gemeinsame Daten zu. Das
Ergebnis hängt davon ab, in welcher Reihenfolge die Prozesse darauf zugreifen.
⃝c 2011 TU Dortmund, Informatik 12, Arbeitsgruppe ESS, Blatt 2 von 2
a1 b1 a2 c1 c2 b2 a3 c3
}
void a1() {
p(Sa)
v(Sa)
p(…)
a1 a2 a3 b1 b2 c1 c2 c3
v(…)
4711
int semop(int semid, struct sembuf sops, unsigned nsops) *
void sem4_p() {
struct sembuf sop;
sop.sem_num = 3;
sop.sem_flg = 0;
sop.sem_op = -1; /* P — dekrementieren */
if (semop(4711, &sop, 1) == -1) { /* Fehlerabfrage */
perror(“sem4_p()”);
exit(1); }
}
⃝
/* 4-elementig, Zaehlung ab 0, das letzte ist 3 */ /* keine besonderen Flags verlangt */
int main(void) { …
SEM_UNDO
p(); v(); v(); p(); v(); p();
return 0;
}
→
→
→
→
→
→
→
→
→
→
→
→
→
→
→
→
→
→
→
→
→
→
⃝
BSRvS1 Last Chance Test A3 – Verklemmungen Name: Max Mustermann Matrikelnummer: 10000
A3 – Verklemmungen
Maximal mögliche Gesamtpunktzahl für dieses Blatt: 20 Punkte. Zum Bestehen werden 50% der maximal möglichen Punkte benötigt.
1. In der Übungsaufgabe A3 („Kreuzung“) war vorgesehen, dass vier Autos auf eine Kreuzung zufahren und diese überqueren können. Ein Auto, das an die Kreuzung herangefahren ist, belegt zunächst (durch eine Semaphor-Operation) den Kreuzungs-Quadranten direkt vor seiner Motorhaube, danach den Quadranten des rechten Nachbarn, und fährt dann über die Kreuzung (siehe Graphik). Danach werden beide Quadranten wieder freigegeben, und das Spiel beginnt von vorne.
a) Zeichnen Sie den Betriebsmittel-Belegungsgraphen für die Situation, in der tatsächlich eine Ver- klemmung eingetreten ist. Benennen Sie die Prozesse (die Autos) mit A1-A4, die Betriebsmittel (Kreuzungs-Quadranten) mit Q1-Q4, wobei der Quadrant Qx derjenige vor der Motorhaube von Auto Ax ist. (4 Punkte)
⃝c 2009 TU Dortmund, Informatik 12, Arbeitsgruppe ESS, Blatt 1 von 2
BSRvS1 b)
c)
Last Chance Test A3 – Verklemmungen
Das Aufstellen des Betriebsmittel-Belegungsgraphen zum Feststellen einer Verklemmung ist in der Praxis meist zu aufwändig. In der Aufgabenstellung durchlaufen die vier Autos jeweils nachein- ander die Zustände „Heranfahren“, „Warten“ und „Fahren“. Wie kann man statt der Untersuchung des Belegungsgraphen anhand der Zustände der Autos erkennen, dass eine Verklemmungssitua- tion vorliegt? (1 Punkt)
alle Autos im Zustand „Warten“: jedes Auto hat „seinen“ Quadranten belegt und wartet auf die Freigabe des Quadranten des rechten Nachbarn
Methoden zur Verklemmungsvorbeugung (deadlock prevention) entkräften jeweils eine der Vor- bedingungen für Deadlocks. Beschreiben Sie anhand der Kreuzungs-Situation eine mögliche Me- thode stichpunktartig und geben Sie an, welche der Bedingungen sie entkräftet. (3 Punkte) eine aus:
indirekte Methoden:
i. „mutual exclusion“ ließe sich nur durch Änderung der Aufgabenstellung entkräften – die
Kreuzungs-Quadranten sind per Definition unteilbar
ii. „hold and wait“ entkräften: mehrere aufeinanderfolgende Betriebsmittelanforderungen un-
teilbar auslegen, also das Belegen der zwei Quadranten in einem Schritt durchführen (z.B.
durch atomare Operation auf Semaphor-Array)
iii. „no preemption“ – man könnte die Autos auf „Zuruf“ (z.B. Signal) dazu bringen, kurzfristig
den von ihnen belegten Quadranten wieder herzugeben, damit ein anderes Auto fahren kann
(geht in die Richtung Verklemmungsauflösung)
oder die direkte Methode, lineare Ordnung auf den Betriebsmitteln einführen: ein Auto, das die
Quadranten i und j belegen will, tut dies immer in aufsteigender Reihenfolge (falls i < j: erst i, dann j; sonst: erst j, dann i)
2. Welche der folgenden Aussagen zu Semaphore sind richtig? (Mehrfachauswahl möglich) (2 Punkte) x Die zwei möglichen Semaphor-Operationen sind atomar.
Semaphore verhindern Verklemmungen.
Semaphore basieren auf dem Prinzip des „aktiven Wartens“.
x Die Semaphor-Operation V bzw. signal erhöht eine Semaphor-Variable um 1.
3. Erklären Sie stichpunktartig den Unterschied zwischen einem Deadlock und einem Livelock. Weshalb sind Deadlocks das „geringere Übel“? (4 Punkte)
passives vs. aktives Warten
Prozesszustand BLOCKED vs. READY oder RUNNING
Deadlocks sind das „geringere Übel“, da sie eindeutig erkennbar sind, und damit eine Basis zu deren Auflösung gegeben ist.
4. Welche der folgenden Möglichkeiten gehören zu den wiederverwendbaren Betriebsmitteln? (Mehrfach- auswahl möglich) (3 Punkte)
Signale, x Hauptspeicher, Unterbrechungsanforderungen, Daten von Eingabegeräten, x Prozesstabelleneinträge, x Dateien
5. Was ist der Ostrich-Algorithmus? Spielt er eine Rolle bei der Vorbeugung, Vermeidung oder Erkennung von Verklemmungen? (3 Punkte)
• unter Verklemmungserkennungeinzuordnendes Verfahren
• Verklemmungen werden nicht verhindert, keine der vier Bedingungen entkräftet • Ansatz: Wartegraph wird in regelmäßigen Abständen nach Zyklen durchsucht
– wenn BM-Anforderungen zu lange andauern, die Auslastung der CPU trotz Prozesszunahme sinkt, oder die CPU bereits über einen sehr langen Zeitraum untätig ist
⃝c 2009 TU Dortmund, Informatik 12, Arbeitsgruppe ESS, Blatt 2 von 2
BS Last Chance Test A3 – Verklemmungen Name: Max Mustermann Matrikelnummer: 10000
A3 – Verklemmungen
Maximal mögliche Gesamtpunktzahl für dieses Blatt: 20 Punkte. Zum Bestehen werden 50% der maximal möglichen Punkte benötigt.
1. In der Übungsaufgabe A3 („Die Bibliothek“) wurde folgendes Verklemmungsproblem behandelt: Zwei Priester gehen unabhängig voneinander in eine Bibliothek. Dort angekommen liest jeder der Priester zunächst in seiner Schriftrolle. In dieser findet er nun einen Verweis auf die jeweils andere Schriftrolle. Aus diesem Grund möchte der Priester nun gleichzeitig auch in dieser lesen und wartet so lange, bis diese für ihn zugänglich ist. Sobald er beide Schriftrollen gelesen hat, legt er sie wieder zurück.
a) Zeichnen Sie den Betriebsmittel-Belegungsgraphen für die Situation, in der tatsächlich eine Ver- klemmung eingetreten ist. Benennen Sie die Prozesse (die Priester) mit P1 und P2, die Betriebs- mittel (Schriftrollen) mit R1 und R2. (4 Punkte)
b) Woran erkennen Sie an diesem Graphen, dass eine Verklemmung eingetreten ist? (1 Punkt) Zyklus vorhanden
c) Erklären Sie stichpunktartig den Unterschied zwischen einem Deadlock und einem Livelock. Welche der beiden ist in der Bibliothek eingetreten? (3 Punkte)
Deadlock: Prozesszustand BLOCKED (passives Warten); eindeutig erkennbar an Zyklus im BM- Belegungsgraphen
Livelock: Prozesszustand RUNNING bzw. READY (aktives Warten), aber kein Fortschritt
In der Bibliothek tritt ein Deadlock ein.
d) In der Vorlesung wurden vier Bedingungen für Verklemmungen genannt, die zwingend erfüllt sein müssen. Nennen und erklären Sie diese kurz am Beispiel der Bibliothek. (4 Punkte)
exklusive Belegung (mutual exclusion): Gleichzeitiges Lesen einer Schriftrolle von mehreren Pries- tern ist nicht möglich.
Nachfordern von Betriebsmitteln (hold and wait): Nachdem ein Priester eine Schriftrolle hat, holt er sich noch die zweite.
kein Entzug von Betriebsmitteln (no preemption): Wenn ein Priester eine Schriftrolle hat, gibt er sie auch erst mal nicht wieder her.
zirkuläres Warten (circular wait): Da die Priester die Schriftrollen in umgekehrter Reihenfolge aufnehmen, kann es tatsächlich zu einem Zyklus kommen.
2. Betriebsmittel werden vom Betriebssystem verwaltet und Prozessen zugänglich gemacht. Man unter- scheidet dabei zwischen wiederverwendbaren und konsumierbaren Betriebsmitteln. Welche der Folgen- den fallen in die Gruppe der konsumierbaren Betriebsmittel? (Mehrfachauswahl möglich) (2 Punkte)
⃝c 2010 TU Dortmund, Informatik 12, Arbeitsgruppe ESS, Blatt 1 von 2
BS
Last Chance Test
A3 – Verklemmungen
JN
X Daten von Eingabegeräten
X Prozesstabelleneinträge
X E/A-Geräte X Signale
3. Semaphoren sind ein Betriebsmittel zur Synchronisation von Prozessen. Sowohl der Systemaufruf semctl als auch semget ermöglichen das Abfragen von Semaphorwerten. Was ist der entscheidende Unterschied zwischen diesen beiden beim Auslesen mehrerer Semaphoren einer Semaphor-Menge? (2 Punkte)
(Diese Frage ist so unsinnig – semget(2) erlaubt nicht das Abfragen von Semaphorwerten. Eigentlich wollten wir hier nach dem für die Aufgabe relevanten Unterschied zwischen den möglichen semctl- Kommandos GETVAL und GETALL fragen, nämlich dass mit GETALL alle Semaphorwerte in dem Array atomar ausgelesen werden können, was mit GETVAL nicht gelingt. Unabhängig davon, ob keine Antwort gegeben, oder irgendwie versucht wurde, auf die Fragestellung einzugehen, haben wir hier allen zwei Punkte gegeben.)
4. Zur Vorbeugung von Verklemmungen wurde u.a. indirekte Methoden vorgestellt. Betriebsmittelent- zug durch Virtualisierung ist ein solche. Erklären Sie diese Methode kurz. Welche der notwendigen Bedingungen für eine Verklemmung wird dadurch entkräftet? (4 Punkte)
Betriebsmittel werden virtualisiert, bspw. die CPU: Durch Zeitscheiben-Scheduling laufen mehrere Prozesse reihum auf einem Prozessor. Dadurch wird es möglich, einem Prozess ein BM zu entziehen, und es einem anderen zur Verfügung zu stellen. Die Bedingung „kein Entzug von BM (no preemption)“ wird entkräftet.
⃝c 2010 TU Dortmund, Informatik 12, Arbeitsgruppe ESS, Blatt 2 von 2
BS Last Chance Test A3 Verklemmungen
Name: Matrikelnummer:
A3 Verklemmungen
Maximal mögliche Gesamtpunktzahl für dieses Blatt: 21 Punkte. Zum Bestehen werden 50% der maximal möglichen Punkte benötigt.
1. In der Übungsaufgabe A3 (Die Internationale Weltraumstation) wurde folgendes Verklemmungspro- blem behandelt: Zwei Space-Shuttles erreichen unabhängig voneinander die Internationale Weltraum- station. Dort angekommen beginnt jedes Space-Shuttle mit Wartungsarbeiten und leiht zunächst das dafür benötigte Gerät. Die Crew von SpaceA transportiert den Teilchendetektor an Bord von SpaceA und bemerkt, dass auch der Stromgenerator benötigt wird. Für die Crew von SpaceB gilt: der Strom- generator wird an Bord von SpaceB transportiert und anschlieÿend wird der Teilchendetektor benötigt. Solange das zweite Gerät nicht an Bord des Space-Shuttles transportiert werden kann, wartet die Crew. Sobald mit beiden Geräten gearbeitet wurde, werden sie wieder zur Weltraumstation zurückgebracht.
a) Zeichnen Sie den Betriebsmittel-Belegungsgraphen für die Situation, in der tatsächlich eine Ver- klemmung eingetreten ist. Benennen Sie die Prozesse (die Space-Shuttles) mit P1 und P2, die Betriebsmittel (Teilchendetektor und Stromgenerator) mit R1 und R2. (4 Punkte) Betriebs-
mittelgraph: R1 -> P1 -> R2 -> P2 -> R1. Teilchendetektor (R1) wurde dem SpaceA (P1) zugewiesen und SpaceA benötigt den Stromgenerator (R2). Gleichzeitig wird der Stromgene- rator (R2) von dem SpaceB (P2) allokiert und es wird der Teilchendetektor benötigt und die Ausführung fortsetzen zu können.
b) Woran erkennen Sie an diesem Graphen, dass eine Verklemmung eingetreten ist? (1 Punkt) Es ist mindestens ein Zyklus vorhanden, d.h. der Betriebsmittelgraph ist nicht kreisfrei.
c) Erklären Sie stichpunktartig den Unterschied zwischen einem Deadlock und einem Livelock. Wes- halb sind Deadlocks das geringere Übel? (3 Punkte) Deadlock: Prozesszustand BLOCKED
(passives Warten); eindeutig erkennbar am Zyklus im Betriebsmittelgraphen. Livelock: Prozess- zustand RUNNING bzw. READY (aktives Warten), aber es kommt nicht zu dem Fortschritt während der Prozessausführung.
d) In der Vorlesung wurden vier Bedingungen für Verklemmungen genannt, die erfüllt sein müssen. Nennen und erklären Sie diese kurz am Beispiel der Internationalen Weltraumstation. (4 Punkte)
Exklusive Belegung (mutual exclusion): Gleichzeitiges Arbeiten mit den Geräten von mehreren Space-Shuttles ist nicht möglich. Nachfordern von Betriebsmitteln (hold and wait): Nachdem ein Space-Shuttle ein Gerät ausgeliehen hat, fordert es noch das zweite Gerät an. Dabei wird das zuerst ausgeliehene Gerät an Bord behalten. Falls das zweite benötigte Gerät nicht zur Verfügung steht wird solange gewartet, bis es ausgeliehen werden kann und das erste ausgeliehene Gerät wird nicht freigegeben. Kein Entzug von Betriebsmitteln (no preemption): Wenn ein Space- Shuttle ein Gerät ausgeliehen hat, gibt es es auch erst mal nicht wieder her. Zirkuläres Warten (circular wait): Da die Space-Shuttles die Geräte in umgekehrter Reihenfolge ausleihen, kann es tatsächlich zu einem Zyklus kommen.
2. Betriebsmittel werden vom Betriebssystem verwaltet und Prozessen zugänglich gemacht. Man unter- scheidet dabei zwischen wiederverwendbaren und konsumierbaren Betriebsmitteln. Welche der Folgen- den fallen in die Gruppe der konsumierbaren Betriebsmittel? Kreuzen Sie bei J (ja, zutreend) oder N (nein, nicht zutreend) an! (2 Punkte)
⃝c 2011 TU Dortmund, Informatik 12, Arbeitsgruppe ESS, Blatt 1 von 3
BS
Last Chance Test
A3 Verklemmungen
3.
JN
X Daten von Eingabegeräten
X Prozesstabelleneinträge
X E/A-Geräte X Signale
Semaphoren sind ein Betriebsmittel zur Synchronisation von Prozessen. Sei sem der Semaphor eines bestimmten kritischen Abschnitts, so wird p(sem) vor Beginn und v(sem) nach Abschluss des kriti- schen Abschnitts ausgeführt. Die Operationen p und v sollen die kritischen Abschnitte schützen. Was ist der Vorteil von Semaphoren gegenüber von expliziten Synchronisationsvariablen? (2 Punkte) Die
Verwendung von Synchronisationsvariablen zum Schutz eines kritischen Abschnitts kann oft folgen- den Nachteil mit sich bringen: Während sich ein Prozess im kritischen Abschnitt bendet, fragt der konkurrierende Prozess ständig nach Erlaubnis, diesen betreten zu können. Daher verschluckt aktives Warten kostbare Prozessorzeit und ist somit unproduktiv. Ezienter ist eine Implementierung bei der es möglich ist, ein Prozess, der den kritischen Abschnitt betreten möchte, zu deaktivieren und wieder zu aktivieren, wenn der derzeit aktive Prozess den kritischen Abschnitt verlässt (passives Warten). Ein weiteres Nachteil von Synchronisationsvariablen ist es, dass eine gegebene Folge von Anweisungen, die unter anderem die Synchronisationsvariablen modizieren, nicht ungestört nacheinander ablaufen muss (nicht atomare Operationen, Unterbrechungen durch den Kontextwechsel möglich). Mit Semaphoren werden exklusiven Ressourcen überwacht und Operationen, die Semaphorvariablen modizieren, er- folgen atomar (Auslesen und Setzen des Wertes erfolgt atomar). Signal und wait sind also atomare Elementaroperationen, d.h. sie können vor ihrem Abschluss nicht unterbrochen werden.
Was kann man tun, wenn ein Deadlock erkannt wurde? Erklären Sie, wie man diese Ansätze auf die Weltraumstation übertragen könnte. Welche der notwendigen Bedingungen für eine Verklemmung werden dadurch entkräftet? (3 Punkte) Beseitigung/Auösung von Deadlocks: Zunächst versucht
man, die an einem Deadlock beteiligten Prozesse und Ressourcen herauszunden, dann werden die Prozesse (Space-Shuttles) und die zur Beseitigung von Deadlocks erforderlichen Ressourcen (Teil- chendetektor, Stromgenerator) freigegeben -> (1) vorzeitiger Prozessabbruch bzw. -terminierung und anschlieÿender Neustart von Space-Shuttles, die einzelnen Space-Shuttles können nicht wieder an der abgebrochen Stelle im Programm fortgesetzt werden. (2) Schrittweiser Abbruch einzelner Space- Shuttles, bis kein Deadlock mehr vorliegt -> Auswahl des eektivsten Opfers ist schwer zu treen. (3) Speicherung des gesamten Systemzustandes in regelmäÿigen Abständen. So kann im Falle eines Dead- locks der Systemzustand zurückgespielt werden -> Minimierung des eingetretenen Schadens, aufgrund von Systemkomplexität kan man nicht alle Informationen abspeichern. (4) Ressourcenentzug bis kein Deadlock mehr vorliegt, z.B. Enzug des Stromgenerators dem SpaceB, anschlieÿend soll SpaceB in den Zustand versetzt werden, in dem keine Ressourcen mehr allokiert sind und die Ressourcenanforderung initial passieren wird -> Anfang der Lebens-while-Schleife.
Was ist der Bankier-Algorithmus? Spielt er eine Rolle bei der Vorbeugung, Vermeidung oder Erkennung von Deadlocks? (2 Punkte)
Der Bankier-Algorithmus wird zur Deadlockvermeidung eingesetzt. Im Algorithmus wird das Konzept der sicheren/unsicheren Zustände zur Ressourcenallokation realisiert. Der Systemzustand wird durch vorhandene Ressourcen (rem-Vektor) und bereits allokierten Ressourcen (claim-Vektor) dargestellt. Für jeden Prozess sind maximalen Ressourcenanforderungen im voraus bekannt (max-Vektor). Bei jeder Ressourcenanforderung wird der Systemzustand, im Falle der Allokation von angeforderten Res- sourcen, auf die Sicherheit geprüft. Ein Systemzustand gilt dann als sicher, wenn es mindestens eine deadlockfreie Ausführungsreihenfolge aller Prozesse existiert, unter der Voraussetzung, dass alle Pro- zesse ihre maximale Anzahl an Ressourcen anfordern (b.h. bis sie erfolgreich terminiert haben). Falls
4.
5.
⃝c 2011 TU Dortmund, Informatik 12, Arbeitsgruppe ESS, Blatt 2 von 3
BS
Last Chance Test A3 Verklemmungen
es keine sichere Ausführungsreihenfolge der Prozess gibt, ist der Zustand unsicher und die angefor- derten Ressourcen werden nicht zugeteilt. Dies resultiert in einer hohen Restriktivität des Verfahrens, denn es existiert eine Teilmenge von unsicheren, aber dennoch deadlockfreien Zuständen. In der Praxis wird das Verfahren nur dann eingesetzt, wenn maximale Ressourcenanforderungen für alle Prozesse bekannt sind.
⃝c 2011 TU Dortmund, Informatik 12, Arbeitsgruppe ESS, Blatt 3 von 3
℄ ℄
⃝
⃝
BSRvS1 Last Chance Test A4 – Speicherverwaltung Name: Max Mustermann Matrikelnummer: 10000
A4 – Speicherverwaltung
Maximal mögliche Gesamtpunktzahl für dieses Blatt: 20 Punkte. Zum Bestehen werden 50% der maximal möglichen Punkte benötigt.
1. Dynamische Speicherverwaltung nach dem Worst-Fit-Verfahren: Zum Zeitpunkt t = 1 sei der voll- ständige Speicher der Größe 16 MiB nicht belegt. Zum Zeitpunkt t = 2 werden 5 MiB (Spalte S) angefordert, die mit dem Buchstaben A (Spalte ID) in die Tabelle eingetragen werden sollen (hier schon beispielhaft ausgefüllt). Markieren Sie die weiteren Belegungen/Freigaben (Spalte B/F) zu den Zeitpunkten 3 bis 7. (4 Punkte)
Hinweise: Die Belegung erfolgt immer am Anfang des durch Worst Fit ausgewählten Speicherbe- reichs. Falls eine Belegung/Freigabe nicht erfüllt werden kann, kennzeichnen Sie die betreffende Zeile geeignet.
t B/F ID S 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 1
2BA5AAAAAAAAAAAAAAAA 3BB2AAAAABB
4BC6AAAAABBCCCCCC 5FB AAAAA CCCCCC
6BD4AAAAA!!CCCCCC!!! 7BE1AAAAA CCCCCCE
2. Bei den listenbasierten Speicher-Platzierungsverfahren (wie First/Next/Best/… Fit) kann externer Verschnitt auftreten. Erklären Sie den Begriff knapp in eigenen Worten und erklären Sie den Unter- schied zu internem Verschnitt. Welche Maßnahme kann ergriffen werden, wenn der externe Verschnitt überhandnimmt? (4 Punkte)
außerhalb der zugeteilten Speicherbereiche entstehen Speicherfragmente, die nicht mehr genutzt wer- den können (da zu klein); bei internem Verschnitt ist dagegen Speicher innerhalb der Speicherbereiche nicht mehr nutzbar (wenn aufgrund der Strategie mehr Speicher reserviert wird als angefordert wurde, z.B. bei Buddy)
→ Kompaktifizieren
⃝c 2009 TU Dortmund, Informatik 12, Arbeitsgruppe ESS, Blatt 1 von 2
BSRvS1 Last Chance Test A4 – Speicherverwaltung
3. Schreiben Sie eine C-Funktion, die zwei Integer-Arrays vergleicht. Die Funktion bekommt zwei Zeiger auf den Anfang der beiden Arrays und die Anzahl der zu vergleichenden Elemente übergeben. Die Funktion soll die Zahl 0 zurückliefern, wenn die Arrays identisch sind, sonst 1. (4 Punkte)
int array_cmp(int ∗a1, int ∗a2, unsigned int n) {
inti;
for (i = 0; i < n; ++i) {
if (a1[i] != a2[i]) { return 1;
} }
return 0;
}
4. Welche Schritte führt das Betriebssystem als Reaktion auf einen Seitenfehler beim Demand Paging
bis zur Rückkehr der Behandlungsroutine in das Anwendungsprogramm aus? (3 Punkte)
a) Ermitteln der ausgelagerten Seite im Hintergrundspeicher
b) Einlagern der Seite in eine geeignet gewählte Kachel
c) Anpassen der Seiten-Kachel-Tabelle (Eintragung der Kachel, Setzen des Präsenz-Bits)
5. Ein C-Programm, das die Adresse einer global angelegten Variable globale_variable ausgibt, wird auf einem UNIX-System gleichzeitig zwei Mal gestartet. Die Ausgabe der beiden Prozesse ist zwei Mal dieselbe Hexadezimalzahl. Wie erklären Sie sich das Verhalten? (3 Punkte)
printf ("Adresse der Variable : %p\n", &globale_variable );
Die ausgegebenen Adressen sind logische Adressen. Dieselbe logische Adresse in zwei verschiedenen Prozessen kann (und wird, insbesondere bei Stack-/Datensegment bzw. BSS) auf verschiedene phy- sikalische Adressen abgebildet werden, weshalb es durchaus möglich ist, dass eine Variable in zwei Prozessen dieselbe logische Adresse hat.
6. Welche dieser Aussagen zum Buddy-Verfahren sind richtig? (Mehrfachauswahl möglich) (2 Punkte) Der verwaltete Speicher wird in Bereiche der Größe 2*n aufgeteilt.
Es tritt externer Verschnitt auf.1
Buddy gehört zu den listenbasierten Verfahren.
x Bei Freigeben eines Bereiches muss dieser manchmal mit seinem Nachbarn verschmolzen werden.
1Grundsätzlich könnte man argumentieren, dass bei Buddy interner und externer Verschnitt auftritt. Daher haben wir hier beide Möglichkeiten gelten lassen.
⃝c 2009 TU Dortmund, Informatik 12, Arbeitsgruppe ESS, Blatt 2 von 2
BS Last Chance Test A4 Speicherverwaltung
Name: Max Mustermann Matrikelnummer: 10000
A4 Speicherverwaltung
Maximal mögliche Gesamtpunktzahl für dieses Blatt: 22 Punkte. Zum Bestehen werden 50% der maximal möglichen Punkte benötigt.
1. Im Folgenden verwalten wir Speicher nach dem Buddy-Verfahren: Die erste Spalte kennzeichnet den Zeitverlauf t. A für steht für die Aktion (Belegung oder Freigabe), die mit Datenblock D (Klein- buchstaben) durchgeführt werden soll. Die Gröÿe des dabei angeforderten Speichers ndet sich in der 4. Spalte G, der zur Verfügung stehende Speicher hat eine Gesamtgröÿe von 512 KiB. Für den Zeitpunkt t = 1 ist in jedem Szenario bereits eine Speicherbelegungssituation vorgegeben. In den 8 rechten Spalten (64 KiB) stehen die Buchstaben jeweils für bereits belegte Speicherblöcke der entsprechenden Gröÿe. Tragen Sie das Speicherprol für den Zeitpunkt t = 2 in die jeweils 2. Zeile der voneinander unabhängigen Szenario-Tabellen ein! (4 Punkte)
• Hinweise: 64-KiB-Speicherblöcke werden nicht weiter in kleinere Blöcke zerlegt. Falls eine Be- legung/Freigabe nicht erfüllt werden kann, kennzeichnen Sie das betreende Szenario geeignet.
• Szenario 1: tAD G
64KiB 64KiB 64KiB 64KiB 64KiB 64KiB 64KiB 64KiB 128 KiB a b 256 KiB
128 KiB a 64 KiB 256 KiB
64KiB 64KiB 64KiB 64KiB 64KiB 64KiB 64KiB 64KiB 512 KiB
Anfangsbelegung→ Fb
1 2
•
1 Anfangsbelegung→ 2 B x 121KiB
• Szenario 3: tAD G
1 Anfangsbelegung→ 2Fy
• Szenario 4: tAD G
1 Anfangsbelegung→ 2 B z 180 KiB
(Anm.: geht nicht!)
Szenario 2: tAD G
x 128 KiB
256 KiB
64KiB 64KiB 64KiB 64KiB 64KiB 64KiB 64KiB 64KiB 128 KiB 64 KiB y a
256 KiB
a
64KiB 64KiB 64KiB 64KiB 64KiB 64KiB 64KiB 64KiB 128 KiB 64 KiB a b 64 KiB 128 KiB
128 KiB 64 KiB a b 64 KiB 128 KiB
2. Erklären Sie kurz stichpunktartig: Wie funktioniert die Ersetzungsstrategie OPT, wozu dient sie, und unter welchen Voraussetzungen kann sie eingesetzt werden? (4 Punkte)
Die (für xe Kachelmenge) optimale Seitenersetzungsstrategie OPT ersetzt immer die Seite, die in gröÿtmöglichem Abstand in der Zukunft wieder referenziert wird. Die (im Normalfall nicht gegebene) Voraussetzung für den Einsatz ist, dass die Referenzfolge vorab bekannt ist.
⃝c 2010 TU Dortmund, Informatik 12, Arbeitsgruppe ESS, Blatt 1 von 2
BS
Last Chance Test A4 Speicherverwaltung
3.
Schreiben Sie eine C-Funktion, die ein Array umdreht, d. h. das Element, welches an der 1. Stelle steht, soll nach dem Aufruf am Ende stehen, das Element an der 2. Stelle, an der vorletzten Stelle, usw. Die Funktion bekommt einen Zeiger auf das Eingabe-Array und die Anzahl der enthaltenen Elemente (n). Das Ergebnis soll in einem neuen, mit malloc() allokierten Array abgelegt und ein Zeiger darauf zurückgeben werden. Fangen Sie auch mögliche Fehler ab. (Zur Erinnerung: void *malloc(size_t size) ) (5 Punkte)
short ∗array_reverse(const short ∗src , unsigned int n) {
short ∗dest = malloc(sizeof(short) ∗ n); unsigned i ;
if (!dest) return NULL;
for (i = 0; i < n; i++) dest[i] = src[n − i − 1];
return dest ; }
Ein C-Programm, das die Adresse einer globalen, initialisierten Variable glv ausgibt, wird auf einem UNIX-System gleichzeitig zwei Mal gestartet. Die Ausgabe der beiden Prozesse ist zwei Mal dieselbe Hexadezimalzahl. Wie erklären Sie sich das Verhalten? (3 Punkte)
printf ("Adresse der Variable : %p\n", &glv );
Die ausgegebenen Adressen sind logische Adressen. Dieselbe logische Adresse in zwei verschiedenen Prozessen kann (und wird, insbesondere bei Stack-/Datensegment bzw. BSS) auf verschiedene phy- sikalische Adressen abgebildet werden, weshalb es durchaus möglich ist, dass eine Variable in zwei Prozessen dieselbe logische Adresse hat.
Betrachten Sie den folgenden Code-Ausschnitt in C:
4.
5.
1 inta=1,b=2,c=7; 2 c &= ~(a | b);
Welchen Wert enthält die Variable c nach der Zuweisung in Zeile 2? (2 Punkte) Wert von c: 4
6. Kreuzen Sie an, bei welchen der folgenden Speicherverwaltungsverfahren interner bzw. externer Ver- schnitt auftreten kann! (4 Punkte)
int. Verschnitt ext. Verschnitt
X
Buddy-Verfahren
X Rotating-First-Fit / Next-Fit
X Best-Fit X Worst-Fit
⃝c 2010 TU Dortmund, Informatik 12, Arbeitsgruppe ESS, Blatt 2 von 2
BS Last Chance Test A4 – Speicherverwaltung Name: Matrikelnummer:
A4 – Speicherverwaltung
Maximal mögliche Gesamtpunktzahl für dieses Blatt: 16 Punkte. Zum Bestehen werden 50% der maximal möglichen Punkte benötigt.
1. Dynamische Speicherverwaltung nach dem Next-Fit-Verfahren: Die Größe des vollständigen Speichers beträgt 17 MiByte. Zum Zeitpunkt 2 fordert der Prozess D 2 Speichereinheiten (S in MiByte) an (hier schon beispielhaft ausgefüllt). Markieren Sie die weiteren Belegungen (B) der Prozesse (P), bzw. die Freigaben (F) zu den Zeitpunkten 3 bis 9. Falls eine Belegung/Freigabe nicht erfüllt werden kann, kennzeichnen Sie die betreffende Zeile geeignet. (4 Punkte)
t R/F P S 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
1AABBCCC 2BD2DDAA BB CCC 3BE2DDAAEE BB CCC
t R/F P S 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
1AABBCC 2BD2AA BBDDCC 3BE3AA BBDDCCEEE
t R/F P S 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
1 AABBCCC
2BD6 AABBCCCDDDDDD 3FB AA CCCDDDDDD
16 17
16 17
16 17
t R/F P S 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17
1 AA BB CCCCC 2BD2AADD BB CCCCC 3BE5AADD BB CCCCC
2. Bei welcher Platzierungsstrategie entsteht interner Verschnitt? (1 Punkt)
First Fit Next Fit Best Fit Worst Fit
X Buddy Verfahren
3. Seitenersetzung. Vervollständigen Sie die Tabelle nach dem First-In First-Out Verfahren. Das Alter
der Kachel ist als Hilfestellung gedacht und muss nicht ausgefüllt werden. (3 Punkte)
© 2010 TU Dortmund, Informatik 12, Arbeitsgruppe ESS, Blatt 1 von 2
BS
Last Chance Test A4 – Speicherverwaltung
Anfragefolge→ 1234561232 Hauptspeicherkachel1 1111555533
Hauptspeicherkachel2 Hauptspeicherkachel 3 Hauptspeicherkachel 4
2
2
3
2 2 33 44 3 0 2 3 1 2 0 1
6 6 6 6 6 31111 44222 1 2 3 0 1 0 1 2 3 4 3 0 1 2 3 2 3 0 1 0
AlterderKachel1(optional) 0 1 AlterderKachel2(optional) > 0 AlterderKachel3(optional) > > AlterderKachel4(optional) > > >
2 1 0
4.
Betrachten Sie den folgenden Code-Ausschnitt in C:
1 inta=1,b=2,c=4; 2 c |= (a & b);
Welchen Wert enthält die Variable c nach der Zuweisung in Zeile 2? (2 Punkte) Wert von c: 4
5. Welche der folgenden Aussagen treffen zu? Kreuzen Sie J (ja, zutreffend) oder N (nein, nicht zutref- fend) an! (3 Punkte)
JN
X
X X
X X
X
Paging vermeidet das Fragmentierungsproblem.
Die MMU lädt bei Bedarf automatisch Seiten aus dem Hintergrundspeicher nach. Seitenflattern (Thrashing) kann durch die optimale Ersetzungsstrategie komplett verhindert werden.
Der Vorwärtsabstand entspricht der Zeitdauer bis zum nächsten Zugriff auf die entsprechende Seite.
Least Recently Used (LRU) kann ohne Hardwareunterstützung implementiert werden. Die Rückwärtsverkettung eigenet sich zur Effizienzsteigerung bei verketteten Listen.
6. Mit welchem Begriff bezeichnet man einen Vorgang, der externen Verschnitt verringert oder beseitigt? Was wird dabei gemacht? Welches Problem ergibt sich daraus? (3 Punkte)
Defragmentierung bzw. Kompaktifizieren. Das Verfahren verschiebt die Speichersegmente, so dass nur noch eine große Lücke vorhanden ist. Der Nachteil ist die erhöhte Laufzeit.
© 2010 TU Dortmund, Informatik 12, Arbeitsgruppe ESS, Blatt 2 von 2
℄
℄
→
⃝
℄
⃝
BSRvS1 Last Chance Test A5 – Dateioperationen & E/A Name: Max Mustermann Matrikelnummer: 10000
Maximal mögliche Gesamtpunktzahl für dieses Blatt: 20 Punkte.
Zum Bestehen werden 50% der maximal möglichen Punkte benötigt.
Bei den Multiple-Choice-Aufgaben können grundsätzlich mehrere Antworten richtig und anzukreuzen sein.
1. Welche der folgenden Aussagen treffen auf die verkettete Speicherung von Dateien zu? (jeder Plat- tenblock besitzt einen Zeiger auf seinen logischen Nachfolger) (2,5 Punkte)
Aufeinanderfolgende Datenblöcke einer Datei liegen auch auf der Platte immer hintereinander. x Der Zugriff auf eine bestimmte Dateiposition ist langsamer als bei kontinuierlicher Speicherung. x Es entsteht kein Verschnitt (abgesehen vom jeweils letzten Block einer Datei).
Dateien können restauriert werden, wenn eine Verzeigerung fehlerhaft ist. Auf einer 64-Bit-Architektur ist dieses Verfahren nicht realisierbar.
2. Was versteht man unter den Begriffen read ahead und lazy write? Antworten Sie knapp in Stichpunk- ten. (3 Punkte)
• read ahead: beim sequentiellen Lesen wird auch der Transfer des/der Folgeblocks angestoßen
• lazywrite:BlockwirdnichtsofortaufPlattegeschrieben(erlaubtOptimierungderSchreibzugriffe
und blockiert den Schreiber nicht)
3. Welche der folgenden Geräte gelten unter UNIX-artigen Betriebssystemen als blockorientierte Geräte? (2,5 Punkte)
x Festplatten Tastaturen Grafikkarten x DVD-Laufwerke serielleSchnittstellen
4. In der Vorlesung wurden verschiedene Möglichkeiten der Arbeitsweise von Gerätetreibern behandelt: Programmierte und unterbrechungsgetriebene Ein-/Ausgabe (mit und ohne DMA). Geben Sie für diese jeweils an, ob die in der ersten Spalte aufgeführten Eigenschaften zutreffen, indem sie das entsprechende Feld mit einem ’J’ (ja) oder einem ’N’ (nein) ausfüllen. (3 Punkte)
programmiert (ohne DMA)
unterbrechungs- getrieben ohne DMA
unterbrechungs- getrieben mit DMA
J
N
N
Da CPU und Hauptspeicher schneller
Daten liefern, als Geräte sie verarbei-
ten können, muss beim Datentrans-
fer an ein Gerät zwischendurch immer
wieder gewartet werden. Dies wird ge-
tan, indem die Software ständig über-
prüft, ob das Gerät wieder bereit ist.
Der Datentransfer zwischen Gerät und NNJ Hauptspeicher läuft am Datencache
des Prozessors vorbei.
⃝c 2009 TU Dortmund, Informatik 12, Arbeitsgruppe ESS, Blatt 1 von 2
BSRvS1 Last Chance Test 5. Betrachten Sie die Funktion geheim:
A5 – Dateioperationen & E/A
(a) Markieren Sie alle Zeilen, die eine Fehlerbehandlunga erfordern wür- den (z.B. durch Umkreisen der Zei- lennummer; falsche Markierungen geben Punktabzug!) (2,5 Punk- te)
(b) In den Zeilen 13-16 wird zum Schleifenkopf gesprungen, wenn entry auf den Spezialeintrag „.“ zeigt. Verändern Sie die Bedin- gung so, dass dies auch geschieht, wenn entry auf den Spezialeintrag für das übergeordnete Verzeichnis zeigt. (1 Punkt)
(c) Verändern Sie den Parameter von malloc in den Zeilen 17-20 so, dass die in den Zeilen 21-24 konstruier- te Zeichenkette incl. Terminierung genau in den reservierten Speicher- bereich passt. (1 Punkt)
ad.h. Ausgabe des Fehlers und Abbruch bzw. Überspringen aller Operationen, die von die- ser Zeile abhängig sind
1
2 struct dirent ∗entry = NULL;
3 DIR ∗dir = NULL;
4 char ∗nextpath = NULL;
5 struct stat info = {0};
6 !! stat(path,&info);
7 if (!S_ISDIR(info.st_mode)) return; 8 p r i n t f ( “%s \ n ” , p a t h ) ;
9 !! dir = opendir(path);
void geheim(const char ∗path) {
10 while (1) {
11 !! entry = readdir(dir );
12 if (!entry) break;
13 if (!strcmp(“.”, entry−>d_name)) 14
15
16 continue ;
17 !! nextpath = malloc(
18 strlen (entry−>d_name) 19
20
21 );
22 strcpy(nextpath ,path);
23 strcat(nextpath ,”/”);
24 strcat (nextpath , entry−>d_name); 25 geheim(nextpath );
26 free(nextpath);
27 }
28 !! closedir(dir);
29 }
(d) Welche Bedingung muss der Parameter path erfüllen, damit die Funktion überhaupt etwas auf stdout ausgibt? (unter der Annahme, dass bei keinem der Bibliotheksaufrufe ein Fehler auftritt) (1 Punkt)
Der Parameter path muss auf einen gültigen Pfad zu einem Verzeichnis zeigen (welcher natürlich auch relativ zum aktuellen Verzeichnis sein kann).
(e) Was würde bei dem Aufruf geheim(“.”) passieren? (nach Erledigung von (b) und (c) und unter der Annahme, dass bei keinem der Bibliotheksaufrufe ein Fehler auftritt) (2 Punkte)
gibt „.“ und rekursiv sämtliche Unterverzeichnisse des aktuellen Verzeichnisses („.“) aus
6. Welche der folgenden Aussagen treffen auf C-Streams zu? (1,5 Punkte)
x Neben den Standardstreams stdin und stdout gibt es noch stderr. x C-Streams erlauben „Zurückschreiben“ von gelesenen Zeichen.
Auf C-Streams greift man mit Syscall-Wrappern (z.B. open, read, write) zu.
⃝c 2009 TU Dortmund, Informatik 12, Arbeitsgruppe ESS, Blatt 2 von 2
BS Last Chance Test A5 – Dateioperationen & E/A Name: Max Mustermann Matrikelnummer: 10000
Maximal mögliche Gesamtpunktzahl für dieses Blatt: 21 Punkte.
Zum Bestehen werden 50% der maximal möglichen Punkte benötigt.
Bei den Multiple-Choice-Aufgaben können grundsätzlich mehrere Antworten richtig und anzukreuzen sein.
1. Erklären Sie mit eigenen Worten die beiden Begriffe read ahead und lazy write. (3 Punkte) read ahead
beim sequentiellen Lesen wird auch der Transfer des/der Folgeblocks angestoßen
lazy write
Block wird nicht sofort auf Platte geschrieben (erlaubt Optimierung der Schreibzugriffe und blockiert den Schreiber nicht)
2. Welche der folgenden Geräte gelten unter UNIX-artigen Betriebssystemen als zeichenorientierte Gerä- te? (2,5 Punkte)
Festplatten X Tastaturen Grafikkarten DVD-Laufwerke X Modems 3. Welche Ausgabe liefert das folgende C-Programm (3 Punkte)
#include
char s[] = “Veni,␣vidi,␣vici!”; s[16] = ’\0’;
printf(“v%s\n”, s + 13);
return 0;
}
4. Gegeben sei ein magnetischer Plattenspeicher mit 8 Spuren. Der E/A-Scheduler erhält nach jedem zweiten Lesezugriff ausgehend von L1, weitere blockweise-gruppierte Leseaufträge (L2 und anschlie- ßend L3) für bestimmte Spuren. Zu Beginn befindet sich der Schreib-/Lesekopf über der Spur 0. Führen Sie ein E/A-Scheduling nach dem SSTF-Verfahren (Shortest Seek Time First) durch. (4 Punkte)
L1 = {2,4,3,1}, L2 = {5,6}, L3 = {0,7} 12345670
⃝c 2010 TU Dortmund, Informatik 12, Arbeitsgruppe ESS, Blatt 1 von 2
BS 5.
6.
Last Chance Test A5 – Dateioperationen & E/A NennenSiezweiweitere,inVerbindungmitmagnetischenPlattenspeichernbenannte,E/A-Scheduling-
Strategien. (1 Punkt)
FIFO (First-in-First-out), Elevator
Nennen Sie jeweils einen Vorteil bzw. Nachteil der verketteten Speicherung von Daten im Vergleich zur kontinuierlichen Speicherung. (2 Punkte)
(+) Es wird kein zusammenhängender freier Speicherbereich vorausgesetzt (fragmentierter freier Spei- cherplatz kann genutzt werden).
(+) Eine Datei kann ohne die Notwendigkeit des Umkopierens vergrößert bzw. verkleinert werden.
(-) Die Verkettung beansprucht zusätzlichen Speicherplatz im Vergleich zur kontinuierlichen Speiche- rung.
(-) Ein Zugriff auf eine bestimmte Dateiposition ist im Allgemeinen nicht direkt möglich.
(-) Eine Datei ist im Falle einer fehlerhaften oder korrumpierten Verzeigerung nicht restaurierbar.
Was versteht man unter dem Begriff Endianness? Nennen Sie ferner zwei Ihnen bekannte Endian- Formate. (2,5 Punkte)
Endianness bezeichnet die Byte-Reihenfolge, in der Basisdatentypen im Speicher abgelegt werden (erst wichtig bei Datentypen, die mehr als ein Byte benötigen). Am stärksten verbreitet sind Big- (signifikantestes Byte zuerst) und Little-Endian (signifikantestes Byte zuletzt).
Welchen Vorteil bieten so genannte Journaled-Dateisysteme (JFS) gegenüber einer Journal-freien Al- ternative (z. B. bei einem plötzlichen Stromausfall)? Nennen Sie ferner ein JFS Ihrer Wahl. (3 Punkte)
Alle Änderungen des Dateisystem werden bei einem JFS vor ihrer Durchführung in einem Journal protokolliert. Nach einer unvorhergesehenen Unterbrechung (z.B. Stromausfall) kann mit Hilfe des Journals ein konsistenter Status des Dateisystems wiederhergestellt werden. (bekannte JFSs: ext3, ext4, NTFS, HFS+, ZFS, ReiserFS)
7.
8.
⃝c 2010 TU Dortmund, Informatik 12, Arbeitsgruppe ESS, Blatt 2 von 2
BS Last Chance Test A5 Dateioperationen & E/A
Name: Matrikelnummer:
A5 – Dateioperationen & Ein-Ausgabe
Maximal mögliche Gesamtpunktzahl für dieses Blatt: 22 Punkte. Zum Bestehen werden 50% der maximal möglichen Punkte benötigt. Bei den Multiple-Choice-Aufgaben können grundsätzlich mehrere Antworten richtig und anzukreuzen sein.
1. Welche der folgenden Aussagen über Geräte und Geräteprogrammierung treen zu? (3 Punkte) (Mehrere Antworten möglich, falsche Antworten geben Punktabzug)
X
X
Beim Polling-Betrieb wird passiv gewartet
Zeichenorientierte Geräte sind gepuert, blockorientierte Geräte nicht
Für den E/A-Adressraum besitzen hybride Architekturen spezielle Maschineninstruktionen DMA entlastet den Cache der CPU
DMA-getriebene E/A erzeugt Unterbrechungen
Eine laufende Unterbrechungsbehandlung kann nicht unterbrochen werden
2. Mit welchem Tupel wird ein Gerät unter Unix eindeutig beschrieben? (1 Punkt)
( Gerätetyp (block/char) , Major Number , Minor Number )
3. Welche der folgenden Begrie sind mögliche E/A-Scheduling-Strategien für magnetische Plattenspe-
icher? (3 Punkte)
X Elevator Lazy Write X First In First Out X SSTF HRRN Random Access
4. Beschreiben Sie eine der E/A-Scheduling-Strategien für magnetische Plattenspeicher. (2 Punkte)
Elevator: der Schwenkarm geht immer in dieselbe Richtung bis in dieser Richtung keine weiteren zu schreibenden Blöcke mehr vorhanden sind.
First In First Out: die Blöcke werden in derselben Reihenfolge geschrieben in der sie übergeben wurden.
SSTF: es wird immer der Block geschrieben, der der aktuellen Schwenkarm-Position am nächsten ist (Minimierung der Positionierzeit).
5. Nennen Sie zwei Nachteile der verketteten Speicherung von Dateien im Dateisystem (jeder Block enthält den Zeiger auf den nächsten Block), und beschreiben Sie die beiden Nachteile stichpunktartig. (2 Punkte)
Weniger Nutzdaten in einem Block, da hier auch die Verzeigerung gespeichert wird.
Es sind viele Kopfpositionierungen notwendig, da man sich von Block zu Block hangeln muss – schlechter direkter Zugri.
Ist einmal ein Block beschädigt, dann ist die ganze Datei zerstört (bzw. ab diesem Block wird nichts oder falsche Blöcke gelesen).
© 2011 TU Dortmund, Informatik 12, Arbeitsgruppe ESS, Blatt 1 von 2
BS
Last Chance Test A5 Dateioperationen & E/A
6.
7.
Durch welche Eigenschaft kann sich ein Dateisystem schnell und mit geringem Datenverlust von einem Systemabsturz oder Stromausfall erholen (ohne dabei ein Reparaturprogramm zu benötigen)? Beschreiben Sie kurz das hierzu nötige Vorgehen des Dateisystems im Normalbetrieb und nach einem Ausfall. (3 Punkte)
Journaling: das Dateisystem loggt alle Zugrie (Log File) und kann nach einem Absturz die nicht abgeschlossenen Zugrie wahlweise fertigstellen (Redo) oder rückgängig machen (Undo), durch Lesen des Logs (Transaktionen).
Beschreiben Sie zwei mögliche Auslöser, die den Block Buer Cache veranlassen, Blöcke auf ein Speichermedium (z.B. einen Plattenspeicher) zu schreiben. (2 Punkte)
Der Puer ist voll
regelmäÿiges Schreiben (Daten sollen nicht zu lange im Puer bleiben) Systemaufruf sync(2)
8. Welche Ausgabe liefert das folgende C-Programm? (6 Punkte)
int main(void) { Die Datei satz.txt hat folgenden Inhalt:
char buf [15] = {0};
int r_fd, r_bytes, retval;
r_fd = open(“satz.txt”, O_RDONLY );
r_bytes = read(r_fd, buf+5, 9); printf(“%s\n”, buf+5);
retval = lseek(r_fd, 12, SEEK_SET );
r_bytes = read(r_fd, buf+4, 4); printf(“%s\n”, buf+4);
retval = lseek(r_fd, 3, SEEK_CUR );
r_bytes = read(r_fd, buf, 4); buf [3] = buf [8] = buf [13]; printf(“%s\n”, buf);
return 0; }
very vicious video venture
Geben Sie die drei vom Programm ausgegebe- nen Strings (Textzeilen) an. Machen Sie dabei Leerzeichen kenntlich, indem Sie für jedes
Leerzeichen das
very vici
vidy vici
veni vidi vici
-Symbol verwenden.
© 2011 TU Dortmund, Informatik 12, Arbeitsgruppe ESS, Blatt 2 von 2