Präemptives Scheduling

a)

Level 2: Verstehen

Wie könnte eine präemptive Version des Verfahrens Shortest Process Next aussehen?

Lösung

Shortest Process Next (ohne Unterbrechung, en. run to completion):
- Prozesse mit der kürzesten Abarbeitungszeit werden bevorzugt
- setzt kooperierende Prozesse voraus
- Entscheidung über einen Prozesswechsel nur, wenn ein Prozess beendet wurde
Shortest Time-to-Completion First (mit Unterbrechung, en. preemptive):
- nach jeder Zeiteinheit wird entschieden, welcher Prozess aktuell die geringste verbleibende Laufzeit hat
- zwei Optionen: aktuellen Prozess fortsetzen oder einen anderen laden
- benötigt nach verbleibender Laufzeit sortierte Liste der lauffähigen Prozesse

b)

Level 3: Anwenden

Die folgende Tabelle gibt die Ankunfts- und Rechenzeit von fünf Prozessen an.

Prozess	Ankunftszeit	Rechenzeit
A	0	60
B	15	10
C	30	35
D	45	10
E	60	10

Geben Sie an, in welcher Reihenfolge die Prozesse bei der Zuteilung berücksichtigt werden, wenn Ihre präemptive Variante von Shortest Process Next zum Einsatz kommt. Das Zeitquantum beträgt fünf Zeiteinheiten. Nehmen Sie vereinfachend an, dass der Kontextwechsel keine Latenz verursacht.

Lösung

Jeder einmal eingelagerte Prozess wird für ein Zeitquantum von 5 Zeiteinheiten ausgeführt, bevor entschieden wird, ob er erneut die Zuteilung erhält oder gegen einen anderen Prozess ausgetauscht wird. Wir notieren darum einen Prozess je Zeitquantum, identifiziert über den zugehörigen Buchstaben:

Periode	00	01	02	03	04	05	06	07	08	09	10
Beginn	00	05	10	15	20	25	30	35	40	45	50
Prozess	A	A	A	B	B	A	C	C	C	D	D

Periode	11	12	13	14	15	16	17	18	19	20	21
Beginn	55	60	65	70	75	80	85	90	95	100	105
Prozess	C	E	E	C	C	C	A	A	A	A	A

Periode	22	23	24	25	26	27	28	29	30
Beginn	110	115	120	125	130	135	140	145	150
Prozess	A	A	A	–	–	–	–	–	–

Wird nur die Reihenfolge verlangt, genügt die Angabe aller Prozesse in der Form AAABBACCCDD….

c)

Level 3: Anwenden

Listen Sie die Prozesse aus der Tabelle in Scheduling-Reihenfolge unter Verwendung von präemptiven Round-Robin-Scheduling auf. Das Zeitquantum beträgt fünf Zeiteinheiten. Nehmen Sie vereinfachend an, dass der Kontextwechsel keine Latenz verursacht.

Diese Aufgabe war Teil der Klausur im Sommersemester 2025 (Ersttermin).

Lösung

Periode	00	01	02	03	04	05	06	07	08	09	10
Beginn	00	05	10	15	20	25	30	35	40	45	50
Prozess	A	A	A	B	A	B	C	A	C	D	A

Periode	11	12	13	14	15	16	17	18	19	20	21
Beginn	55	60	65	70	75	80	85	90	95	100	105
Prozess	C	D	E	A	C	E	A	C	A	C	A

Periode	22	23	24	25	26	27	28	29	30
Beginn	110	115	120	125	130	135	140	145	150
Prozess	C	A	A	–	–	–	–	–	–

Lernziele

In dieser Aufgabe …

entwickeln und simulieren die Studierenden ein eigenes, präemptives Scheduling-Verfahren.
erweitern die Studierenden ihr Verständnis der Zuteilung auf Zeitquanten, die mehrere Zeiteinheiten umfassen.
üben die Studierenden die Anwendung des Round-Robin-Verfahrens.