Multimedia-Systeme: Übungsblatt 10

Aufgabe 1: Scheduling

(a) Definieren Sie den Begriff Scheduling.

(b) Entwerfen Sie einen Algorithmus, der das EDF-Scheduling (Earliest Deadline First) simuliert. Dieser Algorithmus soll Video und Audio nicht-präemptiv und alle anderen Aufträge präemptiv behandeln. Was sollte beachtet werden bei der Festlegung des Zeitintervalls, für das jeder gerade laufende Prozeß ohne unterbrochen zu werden die CPU bekommt (=Quantum)?

(c) Betrachten Sie folgende Prozesse (beides sind MPEG-Videos):

• Prozeß 1: Ankunft 0.0, Dauer 0.15, Deadline 0.2
• Prozeß 2: Ankunft 0.0, Dauer 0.1, Deadline 0.2

Können diese Prozesse mit EDF fristgerecht ausgeführt werden? Falls nein, überlegen Sie, durch welchen Parameter Sie die Verlustrate so niedrig wie möglich halten können.

(d) In der folgenden Tabelle sind die Ankunftszeiten und die Deadlines zweier Prozesse angegeben. Jeder dieser Prozesse hat ein Quantum von 1 ms. 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 (beide präemptiv behandeln).

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	6 ms	10 ms
3	4 ms	5 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
Antwortzeitverletzung in Periode 2
Antwortzeitverletzung in Periode 3
Antwortzeitverletzung in Periode 4
Antwortzeitverletzung in Periode 5

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

Keine Probleme
Antwortzeitverletzung in Periode 1
Antwortzeitverletzung in Periode 2
Antwortzeitverletzung in Periode 3
Antwortzeitverletzung in Periode 4
Antwortzeitverletzung in Periode 5

Aufgabe 2: Scheduling

Betrachten Sie eine Multimedia-Workstation, auf der zwei Module lokal laufen: Das erste dient als Empfänger für vom Netz kommende Filme, das zweite als Player für die Filme.

(a) Welche Möglichkeiten gibt es, den empfangenen Film von Modul 1 zu Modul 2 zu übergeben?

(b) Untersuchen Sie die Eignung der Verfahren zur Verarbeitung isochroner Datenströme. Welches ist am besten geeignet?

(c) Wie läßt es sich vermeiden, daß sich die beiden Prozesse bei der Benutzung von Shared Memory gegenseitig blockieren? Nennen Sie die Konzepte, die solche Deadlocks verhindern sollen.

Aufgabe 3: Videoserver

Ein Video on Demand Server nutzt das Non-preemtive 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?

4 22 33 46 54

Aufgabe 4: Multimedia-Datenspeicher

(a) Betrachten Sie eine Festplatte mit Interleavefaktor 3, die aus 10 Zylindern mit 8 Sektorn von jeweils 4096 Byte Größe besteht. Geben Sie die Reihenfolge an, in der die Sektoren auf einem Zylinder plaziert werden.

1, 3, 5, 7, 2, 4, 6, 8
1, 2, 3, 4, 5, 6, 7, 8
1, 4, 7, 2, 5, 8, 3, 6

(b) Nehmen Sie weiterhin an, daß sich die Platte mit 100 Umdrehungen pro Minute dreht. Der Festplattenarm benötigt 0,5 sec, um von einem Zylinder zum nächsten zu wechseln. Wie lange dauert es durchschnittlich, bis eine Datei von 13.000 Bytes Länge eingelesen worden ist? Gehen Sie davon aus, daß sich die Daten der Datei geordnet in Sektoren mit aufeinanderfolgender Nummerierung auf demselben Zylinder befinden.

3,55 sec 2,025 sec 2,70 sec 2,5975 sec

(c) Es liege die folgende Anforderungsreihenfolge für Blöcke einer Platte vor: 12-45-42-50-16-30-24. 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 1 war 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):

Abgabedaten:

Matrikelnummer: Password: