Um mehrere Prozesse auf demselben System auszuführen, kommen verschiedene Zuteilungsstrategien zum Einsatz. In dieser Aufgabe simulieren Sie die Verfahren Round Robin (RR), First-Come First-Served (FCFS) und Shortest Process Next (SPN) anhand eines Beispiels. Gegeben sind die folgenden Ankunfts- und Bearbeitungszeiten, vereinfachend bemessen in der fiktiven Einheit ZE (Zeiteinheit):
| Prozess | Ankunftszeit | Benötigte Ausführungszeit $T_s$ [ZE] |
|---|---|---|
| A | 0 | 5 |
| B | 0 | 3 |
| C | 4 | 3 |
| D | 5 | 1 |
| E | 6 | 5 |
| F | 7 | 4 |
Level 1: Wissen
Simulieren Sie die Zuteilung mit allen drei Verfahren. Gehen Sie bei Round Robin von 3 Zeiteinheiten je Zeitscheibe aus.
Round Robin
| Zeitpunkt | 00 | 01 | 02 | 03 | 04 | 05 | 06 | 07 | 08 | 09 | 10 |
|---|---|---|---|---|---|---|---|---|---|---|---|
| Prozess | A | A | A | B | B | B | A | A | C | C | C |
| Zeitpunkt | 11 | 12 | 13 | 14 | 15 | 16 | 17 | 18 | 19 | 20 | 21 |
|---|---|---|---|---|---|---|---|---|---|---|---|
| Prozess | D | E | E | E | F | F | F | E | E | F | – |
First-Come First-Served
| Zeitpunkt | 00 | 01 | 02 | 03 | 04 | 05 | 06 | 07 | 08 | 09 | 10 |
|---|---|---|---|---|---|---|---|---|---|---|---|
| Prozess | A | A | A | A | A | B | B | B | C | C | C |
| Zeitpunkt | 11 | 12 | 13 | 14 | 15 | 16 | 17 | 18 | 19 | 20 | 21 |
|---|---|---|---|---|---|---|---|---|---|---|---|
| Prozess | D | E | E | E | E | E | F | F | F | F | – |
Shortest Process Next
| Zeitpunkt | 00 | 01 | 02 | 03 | 04 | 05 | 06 | 07 | 08 | 09 | 10 |
|---|---|---|---|---|---|---|---|---|---|---|---|
| Prozess | B | B | B | A | A | A | A | A | D | C | C |
| Zeitpunkt | 11 | 12 | 13 | 14 | 15 | 16 | 17 | 18 | 19 | 20 | 21 |
|---|---|---|---|---|---|---|---|---|---|---|---|
| Prozess | C | F | F | F | F | E | E | E | E | E | – |
Level 3: Anwenden
Vergleichen Sie die normalisierte Laufzeit $\hat{T}$ des Prozesses E bei allen drei Verfahren. Die normalisierte Laufzeit $\hat{T}$ ist dabei das Verhältnis aus benötigter Ausführungszeit $T_s$ und beobachteter Laufzeit $T_r$:
$$ \hat{T} = \frac{T_r}{T_s} $$ Bei der beobachteten Laufzeit $T_r$ handelt es sich um die Zeitdauer von der erstmaligen Lauffähigkeit des Prozesses bis zur Beendigung des Prozesses.
Zum Verständnis stellen Sie sich als Analogie eine Autofahrt von Bamberg nach München vor. Die reine Fahrtdauer beträgt 2:40 h ($\sim$ benötigte Ausführungszeit). Zudem machen Sie eine Pause von 30 Minuten. Insgesamt benötigen Sie also 3:10 h ($\sim$ beobachtete Laufzeit).
Normalisierte Laufzeit: $\hat{T} = T_r ÷ T_s$ mit benötigter Ausführungszeit $T_s$ (en. service time) und tatsächlicher Laufzeit $T_r$ (en. response time, auch „Antwortzeit“ insbesondere in Echtzeitsystemen)
Level 1: Wissen
Kontextwechsel sind allerdings nicht kostenlos und benötigen ebenfalls Prozessorzeit. Wiederholen Sie Teilaufgabe (a) unter der Annahme, dass eine Kontextwechsel-Dauer von 1 ZE zu berücksichtigen ist. In dieser Zeit wird der aktuelle Prozess ausgelagert und der nächste Prozess eingelagert. Für das Einlagern des ersten Prozesses ist in dieser Aufgabe ebenfalls ein Kontextwechsel (en. Context Switch, kurz CS) zu berücksichtigen.
Hinweis: Werden zum gleichen Zeitpunkt mehrere Prozesse der Ready List hinzugefügt, nehmen wir vereinfachend an, dass dies in alphabetischer Reihenfolge geschieht.
Round Robin (CS)
| Zeitpunkt | 00 | 01 | 02 | 03 | 04 | 05 | 06 | 07 | 08 | 09 | 10 |
|---|---|---|---|---|---|---|---|---|---|---|---|
| Prozess | CS | A | A | A | CS | B | B | B | CS | A | A |
| Zeitpunkt | 11 | 12 | 13 | 14 | 15 | 16 | 17 | 18 | 19 | 20 | 21 |
|---|---|---|---|---|---|---|---|---|---|---|---|
| Prozess | CS | C | C | C | CS | D | CS | E | E | E | CS |
| Zeitpunkt | 22 | 23 | 24 | 25 | 26 | 27 | 28 | 29 | 30 | 31 | 32 |
|---|---|---|---|---|---|---|---|---|---|---|---|
| Prozess | F | F | F | CS | E | E | CS | F | – | – | – |
First-Come First-Served (CS)
| Zeitpunkt | 00 | 01 | 02 | 03 | 04 | 05 | 06 | 07 | 08 | 09 | 10 |
|---|---|---|---|---|---|---|---|---|---|---|---|
| Prozess | CS | A | A | A | A | A | CS | B | B | B | CS |
| Zeitpunkt | 11 | 12 | 13 | 14 | 15 | 16 | 17 | 18 | 19 | 20 | 21 |
|---|---|---|---|---|---|---|---|---|---|---|---|
| Prozess | C | C | C | CS | D | CS | E | E | E | E | E |
| Zeitpunkt | 22 | 23 | 24 | 25 | 26 | 27 | 28 | 29 | 30 | 31 | 32 |
|---|---|---|---|---|---|---|---|---|---|---|---|
| Prozess | CS | F | F | F | F | – | – | – | – | – | – |
Shortest Process Next (CS)
| Zeitpunkt | 00 | 01 | 02 | 03 | 04 | 05 | 06 | 07 | 08 | 09 | 10 |
|---|---|---|---|---|---|---|---|---|---|---|---|
| Prozess | CS | B | B | B | CS | C | C | C | CS | D | CS |
| Zeitpunkt | 11 | 12 | 13 | 14 | 15 | 16 | 17 | 18 | 19 | 20 | 21 |
|---|---|---|---|---|---|---|---|---|---|---|---|
| Prozess | F | F | F | F | CS | A | A | A | A | A | CS |
| Zeitpunkt | 22 | 23 | 24 | 25 | 26 | 27 | 28 | 29 | 30 | 31 | 32 |
|---|---|---|---|---|---|---|---|---|---|---|---|
| Prozess | E | E | E | E | E | – | – | – | – | – | – |
Level 1: Wissen
Berechnen Sie erneut die normalisierten Laufzeiten des Prozesses E. Rechnen Sie die Dauer eines Kontextwechsels der Laufzeit des nach dem Kontextwechsel eingelagerten Prozesses an.
Level 2: Verstehen
Welche Bedeutung hat eine normalisierte Laufzeit größer 1? Unter welchen Umständen könnte die normalisierte Laufzeit kleiner 1 sein?
In dieser Aufgabe …