Multimedia-Systeme: Übungsblatt 11

Aufgabe 1: Disk-Scheduling-Algorithmen

(a) Grenzen Sie die in der Vorlesung beschriebenen klassischen Disk-Scheduling-Algorithmen voneinander ab

(b) Es liege die folgende Anforderungsreihenfolge für Blöcke einer Platte vor: 1-100-2-99-3-98-4-97. In welcher Reihenfolge werden die Blöcke bei den folgenden Algorithmen gelesen? (Geben Sie KEINE Blanks ein und trennen Sie die Zahlen mit einem Bindestrich, wie im Beispiel). Gehen Sie dabei davon aus, daß die letzte angefahrene Position 50 war, der Kopf sich in der Aufwärtsbewegung befindet und der Sektorauftragspuffer die Größe 3 hat.

First-Come-First-Serve (FCFS):
Shortest-Seek-Time-First (SSTF):
Scan Disk (SD):
C-Scan Disk (CSD):

(c) Betrachten Sie den Disk-Scheduling-Algorithmus N-Step-Scan. Was bedeutet der Parameter N? Wie würde sich das Verfahren verhalten, wenn N=1 gesetzt würde? Wie verhält sich das Verfahren bei großem N?

(d)Erläutern Sie die Disk-Scheduling-Algorithmen für kontinuierliche Datenströme EDF und Scan-EDF an folgender Anforderungsreihenfolge (Format: deadline/blocknumber): 1/1 - 1/100 - 2/2 - 99/1 - 3/2 - 98/3 - 4/2 - 97/4.

Aufgabe 2: Scheduling

(a) Welche Aufgabe hat ein Scheduler innerhalb eines Betriebssystems.

(b) Erläutern Sie die speziellen Anforderungen an den Scheduler bezüglich der Verarbeitung kontinuierlicher Datenströme.

(c) Erläutern Sie EDF-Scheduling und ratenmonotones Scheduling.

(d) In der folgenden Tabelle sind die Ankunftszeiten und die Deadlines zweier Prozesse angegeben, die jeweils einen Datenstrom verarbeiten. Ein Paket von Prozeß 1 kann in 1 ms, dasjenige von Prozeß 2 in 2.5 ms abgearbeitet werden. Tragen Sie in die nachfolgende Grafik die Abarbeitungsreihenfolge gemäß RM-Scheduling (Rate Monotonic) bzw. EDF-Scheduling ein. Der Scheduler für die Prozesse ein Quantum von 0.5 ms (d.h. alle 0.5 ms kann bei der Bearbeitung zwischen den verschiedenen Prozessen umgeschaltet werden).

Paket	Ankunftszeit Prozeß 1	Deadline P1	Ankunftszeit Prozeß 2	Deadline P2
1	0 ms	2 ms	0 ms	5 ms
2	2 ms	4 ms	5 ms	10 ms
3	4 ms	6 ms	-	-
4	6 ms	8 ms	-	-
5	8 ms	10 ms	-	-

Zu welchem der folgenden Probleme kommt es bei der Abarbeitung mit EDF?

Keine Probleme
Antwortzeitverletzung in Periode 1 (0 - 2ms)
Antwortzeitverletzung in Periode 2 (2 - 4ms)
Antwortzeitverletzung in Periode 3 (4 - 6ms)
Antwortzeitverletzung in Periode 4 (6 - 8ms)
Antwortzeitverletzung in Periode 5 (8 - 10ms)

Zu welchem der folgenden Probleme kommt es bei der Abarbeitung mit RM?

Keine Probleme
Antwortzeitverletzung in Periode 1 (0 - 2ms)
Antwortzeitverletzung in Periode 2 (2 - 4ms)
Antwortzeitverletzung in Periode 3 (4 - 6ms)
Antwortzeitverletzung in Periode 4 (6 - 8ms)
Antwortzeitverletzung in Periode 5 (8 - 10ms)

Aufgabe 3: Videoserver

Ein Video on Demand Server nutzt non-preemptive Scheduling. Seine Aufgabe ist es, gleichmäßig Videodaten an seine Empfänger zu senden. Innerhalb von 10 ms kann der Server im Durchschnitt 100 kByte Daten versenden. Ein Videostrom besteht aus durchschnittlich 2 MBit/s wobei das Senden eines Videostromes in jeweils einem Prozeß geschieht. Zum Umschalten zwischen zwei Prozessen werden jeweils 5 ms benötigt. Wieviele Ströme kann der Server maximal parallel versenden?
Hinweis: Rechnen Sie aus Vereinfachungsgründen mit 1 KByte = 1000 bytes und 1 MBit = 1000000 bits. Ein Strom muß mindestens einmal pro Sekunde mit Daten versorgt werden.

4 22 33 46 54

Aufgabe 4: Multimedia-Datenspeicher

• Betrachten Sie die Anforderungsreihenfolge für Blöcke einer Festplatte auf der nächsten Seite. Bearbeiten Sie diese Anforderungsreihenfolge unter Verwendung des Scan-EDF-Verfahrens mit modifizierten deadlines. Verwenden Sie zur Darstellung nebenstehendes Diagramm. Zur Berechnung der modifizierten deadlines wählen Sie eine geeignete Funktion aus und geben Sie diese an.

Geben Sie in der nachfolgenden Auswahlbox den Zustand des Schreib-/Lesekopfes nach Abarbeitung der zuletzt ausgeführten Anfrage an:

- 20 up 10 up 10 down

Aufgabe 5: Threads und Prozesse

1. Diskutieren Sie Vor- und Nachteile von Threads gegenüber Prozessen.

2. Nennen Sie jeweils ein Beispiel für eine Anwendung, die sich besser mit Threads bzw. Prozessen realisieren läßt.

Abgabedaten:

Matrikelnummer: Password: