close

Anmelden

Neues Passwort anfordern?

Anmeldung mit OpenID

Download - Lehrstuhl für Mobile und Verteilte Systeme

Einbetten
Ludwig-Maximilians-Universität München
Institut für Informatik
Lehrstuhl für Mobile und Verteilte Systeme
Prof. Dr. Claudia Linnhoff-Popien
Betriebssysteme im Wintersemester 2014/2015
Übungsblatt 13
Abgabetermin:
Freiwillige Abgabe von Fragen zum Stoff bis 22.01.2015 16.00 Uhr
Besprechung:
Besprechung der Aufgaben in den Tutorien vom 19. – 23. Januar 2015
Ankündigungen:
Am Montag, den 26. Januar 2015 findet von 16.00-18.00 Uhr ein Sondertutorium
für alle Studenten statt, an dem gezielt nochmals Fragen zum Stoff gestellt werden
können! Der Raum hierzu wird rechtzeitig auf der Vorlesungswebseite bekannt gegeben.
In der Woche vom 26.-30. Januar 2015 findet keine Vorlesung und auch keine anderen
Tutorien mehr statt!
Die Klausur findet am 30. Januar 2015 von 18.30 - 20.30 Uhr statt. Bitte melden Sie
sich bis spätestens 27. Januar 2015 zur Klausur über Uniworx an.
Aufgabe 55: (T) Buddy-Systeme
(– Pkt.)
Ein mobiles Gerät verfüge über einen 1 MB großen Speicher, der nach dem Buddy-Verfahren verwaltet wird. Um diesen Speicher byteweise zu adressieren, benötigt man 20 Bits (220 = 1.048.576
Bytes = 1 MB).
a.
Nacheinander sollen die folgenden vier Programme in den Speicher geladen werden:
–
P1 : 100 KB
–
P2 : 220 KB
–
P3 : 250 KB
–
P4 : 60 KB
Zeichnen Sie den Buddy-Baum nach jeder Neubelegung. Tragen Sie auch die Zeiger auf die
Freibereiche ein, und geben Sie für P1 bis P4 die Speicheradressen an.
Hinweis: Es wird immer das am weitesten links stehende Segment gesplittet und der am
weitesten links stehende Buddy belegt.
b.
Die Programme aus Teilaufgabe a benötigen insgesamt 630 KB Speicherplatz. Damit müssten
noch 1024 − 630=394 KB nutzbar sein. Warum ist das im Beispiel nicht der Fall? Welcher
Effekt kommt hier zum Tragen? Wie viel nutzbarer Speicherplatz steht dem Benutzer noch
zur Verfügung?
c.
Gegeben ist eine weitere Anfrage:
–
P5 : 280 KB
Kann P5 noch zusätzlich in den Speicher geladen werden? Falls ja, zeichnen Sie den BuddyBaum nach der Belege-Operation. Falls nein, begründen Sie Ihre Antwort.
Betriebssysteme – WS 1415, Übungsblatt 13
d.
2
Beurteilen Sie aufgrund der Ergebnisse aus den vorigen Teilaufgaben die Anwendung des
Buddy-Verfahrens im Hinblick auf die Speicherausnutzung. Worin liegt der wesentliche Vorteil im Vergleich zu einem System mit fester Speicherpartitionierung?
Aufgabe 56: (T) Wiederholung
(– Pkt.)
Beantworten Sie die folgenden Fragen bitte in kurzen Stichpunkten.
a.
b.
c.
Prozesskoordination:
(i)
Welches sind die gültigen Operationen auf Binärsemaphoren?
(ii)
Worin liegt der Unterschied zwischen Binär- und Zählsemaphoren?
(iii)
Welches Ziel wird durch den Einsatz programmiersprachlicher Monitore verfolgt?
(iv)
Unterstützen Java-Monitore die Verwendung von Bedingungsvariablen? Falls nicht:
Wie kann trotzdem verhindert werden, dass der Rumpf einer als synchronized deklarierten Methode zur Ausführung kommt, wenn bestimmte Voraussetzungen (noch)
nicht erfüllt sind?
Deadlocks:
(i)
Erklären Sie den Zusammenhang zwischen Deadlocks und Multiprogramming.
(ii)
Lässt sich das Modell des Prozessfortschrittsdiagramms auch auf Multiprozessorsysteme anwenden? Was ändert sich?
(iii)
Nennen Sie ein Verfahren zur Deadlock-Vermeidung und ein Verfahren zur DeadlockBehebung.
Prozesse, Threads und Scheduling:
(i)
In welchem Fall ist ein Kontextwechsel zwischen Threads ohne vorherigen Moduswechsel möglich?
(ii)
Eine preemptive Variante der Scheduling-Strategie SJF (auch manchmal SJN genannt)
ist SRPT. In welchem Fall ist SRPT eine sinnvolle Alternative zu SJF?
(iii)
Welche Informationen werden im PCB gespeichert?
Aufgabe 57: (T) Koordination von Threads
(– Pkt.)
In dieser Aufgabe soll das bekannte Philosophenproblem (Dining Philosophers) mit Hilfe der Programmiersprache Java implementiert werden.
Beim Philosophenproblem sitzen fünf Philosophen an einem runden Tisch beim Essen (siehe Abbildung). Vor jedem Philosophen befindet sich ein Teller voller Reis und zwischen je zwei Tellern
befindet sich ein Stäbchen. Ein Philosoph, der hungrig ist, benötigt sowohl das linke als auch das
rechte Stäbchen, um essen zu können. Hat ein Philosoph zwei Stäbchen, so isst dieser, bis er satt
ist, erst dann legt er die Stäbchen an die ursprünglichen Plätze zurück, so dass seine Nachbarn
davon Gebrauch machen können.
a.
Beschreiben Sie, ab wann man sich beim Philosophenproblem im kritischen Bereiche befindet
und ab wann man diesen wieder verlässt.
b.
Wenn man beim Philosophenproblem keine Einschränkung beim Zugriff auf die Stäbchen
formuliert, kann es zu einem Deadlock kommen.
Betriebssysteme – WS 1415, Übungsblatt 13
c.
3
(i)
Beschreiben Sie informell einen Ablauf für das Philosophenproblem, der zu einem
Deadlock führt.
(ii)
Geben Sie zwei der effizientesten (!) Möglichkeit an, wie sich die Deadlocksituation im
speziellen Fall des Fünf-Philosophenproblems vermeiden lässt.
(iii)
Das Auftreten welcher der für einen Deadlock notwendigen Bedingungen wird durch
ihre Lösungen ausgeschlossen?
Im Folgenden sollen Sie das Philosophenproblem in Form der drei Java Klassen Philosoph,
Staebchen und Dinner implementieren. Der Quelltext der Klasse Dinner ist bereits vorgegeben und sieht folgendermaßen aus:
1
2
3
4
public class Dinner {
public static void main(String[] args) {
Thread[] philosoph = new Thread[5];
Staebchen staebchen[] = new Staebchen[5];
5
for (int i = 0; i < 5; ++i) {
staebchen[i] = new Staebchen();
}
for (int i = 0; i < 5; ++i) {
philosoph[i] =
new Philosoph(i, staebchen[(i+4)%5], staebchen[i]);
philosoph[i].start();
}
6
7
8
9
10
11
12
13
}
14
15
(i)
}
Implementieren Sie zunächst die Klasse Staebchen (nächste Seite). Diese soll die
beiden Methoden get() (Stäbchen vom Tisch nehmen) und put() (Stäbchen an
den ursprünglichen Platz zurücklegen) zur Verfügung stellen. Verwenden Sie dazu den
nachfolgenden Code-Rahmen. Achten Sie darauf, dass der Zugriff auf ein Stäbchen im
wechselseitigen Ausschluss erfolgt und keine Race Conditions auftreten können! Verwenden Sie für Ihre Implementierung das vorgegebene Attribut wirdBenutzt.
Kommentieren Sie Ihre Lösung ausführlich!
Code-Rahmen der Klasse Staebchen
1
public class Staebchen {
2
// Attribut
private boolean wirdBenutzt = false;
3
4
5
//
//
//
//
6
7
8
9
10
(ii)
get()-Methode
...
put()-Methode
...
}
Implementieren Sie nun die Klasse Philosoph Achten Sie darauf, dass Ihre Implementierung frei von Deadlocks ist. Verwenden Sie dazu den nachfolgenden Code-Rahmen
(Fortsetzung auf der nächsten Seite!). Fügen Sie Ihrer Implementierung alle Attribute hinzu, die notwendig sind, damit Ihre Implementierung sich mit der vorgegebenen
Klasse Dinner fehlerfrei übersetzen lässt.
Kommentieren Sie Ihre Lösung ausführlich!
Betriebssysteme – WS 1415, Übungsblatt 13
4
Hinweis: Die Klasse Random dient dazu, Zufallszahlen zu erzeugen. Die Methode
nextInt(int positiveZahl) liefert eine Zahl zwischen 0 (inklusive) und
positiveZahl (exklusive). Mit Hilfe dieser Methode wird die Zeit, die ein Philosoph
isst bzw. denkt simuliert.
Code-Rahmen der Klasse Philosoph
1
import java.util.Random;
2
3
4
public class Philosoph extends Thread {
private static Random rand = new Random();
5
// Attribute
// ...
// Konstruktor
// ...
// run()-Methode
public void run() {
try {
while(true) {
// denken
System.out.println("Philosoph "+ id + " denkt");
Thread.sleep(rand.nextInt(500) + 500);
// hungrig (versuche Staebchen zu erhalten)
// ...
// essen
System.out.println("Philosoph "+ id + " isst");
Thread.sleep(rand.nextInt(500) + 500);
// satt (lege Staebchen zurück)
// ...
}
}
catch(InterruptedException ie) {
}
}
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
}
Aufgabe 58: (H) Nachgefragt
(– Pkt.)
Diese Aufgabe dient dazu, sich nochmals gezielt Fragen über den Stoff zu überlegen!
Bitte formulieren Sie auf freiwilliger Basis Fragen, die Ihnen beim Durcharbeiten Ihrer Vorlesungsmitschriften (bzw. des Skripts) oder bei der Bearbeitung der Übungsblätter bisher unbeantwortet geblieben sind.
Laden Sie Ihre Fragen bitte bis spätestens 22.01.2015 16.00 Uhr als Lösung zu diesem Blatt bei
Uniworx hoch. Strukturieren Sie Ihre Fragen bitte folgendermaßen:
<frage>Text der ersten Frage. . . </frage>
<frage>Text der zweiten Frage. . . </frage>
...
Ihre eingereichten Fragen werden dann in einem zusätzlich Sondertutorium beantwortet. Dieses
findet satt am: 26. Januar 2015 von 16.00-18.00 Uhr.
Wir wünschen Ihnen viel Erfolg bei den Vorbereitungen auf die Klausur!
Autor
Document
Kategorie
Uncategorized
Seitenansichten
4
Dateigröße
146 KB
Tags
1/--Seiten
melden