Multimedia-Systeme: Übungsblatt 11 (Musterlösung)

Übung: 17.01.2003

Aufgabe 1: Disk-Scheduling-Algorithmen

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

siehe Vorlesung.

(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: 1-100-2-99-3-98-4-97 Shortest-Seek-Time-First (SSTF): 2-1-3-98-99-100-97-4 Scan Disk (SD): 100-99-3-2-1-4-97-98 C-Scan Disk (CSD): 100-1-2-3-4-97-98-99

(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?

Für N=1 entspricht N-Step-Scan dem FCFS-Verfahren. Bei großem N nähert sich das Verfahren dem SCAN-Algorithmus an.

(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.

siehe Vorlesung.

Aufgabe 2: Scheduling

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

Ein Scheduler entscheidet, welcher inaktive Prozess als nächster in den Zustand ready übergeht.

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

Im Gegensatz zu herömmlichen Prozessen haben Prozesse die kontinuierliche Datenströme verarbeiten i.A. Deadlines, die eingehalten werden müssen. Ein Scheduler sollte versuchen, diese Deadlines wenn irgend möglich einzuhalten.

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

EDF-Scheduling: Der Prozess mit der frühsten Deadline erhält die höchste Priorität. Ratenmonotones Scheduling: Der Prozess mit der höchsten Paketrate erhält die höchste Priorität.

(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 arbeitet pre-emptive hat 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

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

  Antwortzeitverletzung in Periode 3 (4 - 6ms)

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?

CPU-Output: o= 100kByte/10ms ==> o= 10 kByte/ms= 10.000 kByte/s benötigt werden 2MBit/s pro Strom 250kByte/s ==> Quantum q= 250kByte/10.000kByte/s= 0,025s Das Umschalten dauert s= 5ms n*(q+s)= 1sec ==> n= 1/(q+s)= 33 Es können also 33 Ströme gleichzeitig von einem Server bedient werden.

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.

sei: - Ni die Spur, die in Anforderung i gelesen werden soll - A die aktuelle Spur, auf der sich der Lesekopf gerade befindet - Nmax die höchste Spur. - Di die Deadline (ganzzahlig) von Anforderung i Funktion: -- | wenn down und Ni < A: A - Ni | | wenn down und Ni > A: Ni f(Ni)= 1/Nmax * | | wenn up und Ni > A: Ni - A | | wenn up und Ni < A: Nmax - Ni -- Die modifizierte Deadline DDi berechnet sich nun folgendermaßen: DDi= Di + f(Ni) Überlegungen zu der Funktion: Die hier angegegebene Funktion gibt exakt die Anforderungen von Scan-EDF wieder: Anforderungen mit kleinerer Deadline werden zuerst abgearbeitet, da Deadlines ganzzahlig sind, und f lediglich die Nachkommastellen beeinflußt Die Deadlines werden so modifiziert, daß Anforderungen mit gleicher Deadline in Scan-Reihenfolge abgearbeitet werden d.h.: wenn sich der Lesekopf in "down" Richtung befindet, so hat die Funktion f für eine Anforderungen i, deren angeforderte Spur Ni kleiner als die aktuelle Position A ist, einen KLEINEREN Wert als Anforderungen nach höheren Spuren als A. analoges gilt für die "up" Richtung.

Aufgabe 5: Threads und Prozesse

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

   Vorteile von Threads: leichtgewichtiger, Context-Switching schneller (nur ein eigener Stack sowie Stackpointer benötigt) teilen Speicher mit anderen Threads des gleichen Prozesses, was weniger Overhead erzeugt und Threadkommunikation vereinfacht (keine Kopieren von Nachrichten) Prozessorcache bleibt gültig, keine Seiten-/Segmenttabellenmanipulationen nötig Nachteile von Threads: kein Schutz des Speichers, daher Synchronisation von Threads wichtig (non-reentrant code, etc.) kein eigener Eintrag in Tabelle auszuführender Prozesse, daher ist ein eigener Scheduler auf User-Level notwendig. (Kernel-Threads mit eigenem Eintrag können zwar unabhängig vom Elternprozess (wichtig für I/O) geschedult werden, verursachen aber auch mehr Overhead.)

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

   Thread: Oberflächenprogrammierung (Model-View-Controller-Prinzip) mit user-level Threads, Client-Server Anwendungen mit Kernel-Threads, ... Prozess: komplexe Anwendungen bei denen der Speicherschutz zusätzliche Sicherheit bietet; z.B. Netscape, denn beim Browserabsturz würde dann endlich die Emailanwendung nicht mit abstürzen ;-)