Welches Scheduling-Verfahren ist das beste?
Ein Scheduling-Verfahren legt fest, in welcher Reihenfolge Prozesse den Prozessor bekommen, und jedes Verfahren bevorzugt andere Prozesse. Mit der Wartezeit und der Durchlaufzeit vergleichen Sie die Verfahren fair.
Denken Sie an die Kasse in der Mensa. Wer nur einen Becher Wasser hat, ärgert sich über das volle Tablett vor sich. Die drei Verfahren dieser Lektion lösen genau dieses Problem auf verschiedene Weise.
Am Ende dieser Lektion
Notiz
Ich kann FCFS, SJF und Round Robin über die mittlere Wartezeit vergleichen.
Schlüsselwörter
| Begriff | Was er bedeutet | Beispiel |
|---|---|---|
| Laufzeit | die Zeit, die ein Prozess zum Rechnen braucht | 8 |
| Wartezeit | die Zeit, in der ein Prozess bereit ist und nicht rechnet | |
| Durchlaufzeit | die Zeit vom Eintreffen bis zum Ende des Prozesses | |
| FCFS | first come, first served: Wer zuerst kommt, rechnet zuerst | |
| SJF | shortest job first: Der kürzeste Auftrag rechnet zuerst | |
| Konvoi-Effekt | ein langer Prozess lässt alle kurzen dahinter warten |
Die Zellen, die Lernende ausfüllen, bleiben in dieser Vorschau leer.
Wartezeit und Durchlaufzeit messen den Preis
Die Laufzeit ist die Zeit, die ein Prozess zum Rechnen braucht. Die Wartezeit ist die Zeit, in der er bereit ist, aber nicht rechnet. Die Durchlaufzeit reicht vom Eintreffen bis zum Ende.
Die Durchlaufzeit ist Wartezeit plus Laufzeit. Treffen alle Prozesse zur Zeit 0 ein und läuft jeder ohne Unterbrechung, ist die Wartezeit einfach der Zeitpunkt, an dem er startet.
FCFS lässt jeden Prozess bis zum Ende rechnen
Beim FCFS (first come, first served) rechnen die Prozesse in der Reihenfolge, in der sie ankommen. Jeder rechnet bis zum Ende, niemand wird unterbrochen. Das ist einfach zu bauen.
Der Nachteil ist der Konvoi-Effekt. Kommt zuerst ein langer Prozess, müssen alle kurzen dahinter lange warten.
Beispiel: vier Aufträge nach FCFS
| Auftrag | Laufzeit | Start | Ende | Wartezeit |
|---|---|---|---|---|
| A | 8 | 0 | 8 | 0 |
| B | 2 | 8 | 10 | 8 |
| C | 4 | 10 | 14 | 10 |
| D | 2 | 14 | 16 | 14 |
| Mittelwert | 12 (Durchlaufzeit) | 8 |
Die Zellen, die Lernende ausfüllen, bleiben in dieser Vorschau leer.
SJF rechnet den kürzesten Auftrag zuerst
Beim SJF (shortest job first) wählt der Scheduler unter den bereiten Prozessen immer den mit der kleinsten Laufzeit. Kurze Aufträge ziehen an langen vorbei, und die mittlere Wartezeit wird klein. Bei bekannten Laufzeiten ist sie sogar die kleinste, die es gibt.
Der Haken: Das System kennt die Laufzeit vorher nicht und kann sie nur schätzen. Außerdem können lange Prozesse verhungern, wenn ständig kürzere eintreffen.
Beispiel: dieselben Aufträge nach SJF
| Auftrag | Laufzeit | Start | Ende | Wartezeit |
|---|---|---|---|---|
| B | 2 | 0 | 2 | 0 |
| D | 2 | 2 | 4 | 2 |
| C | 4 | 4 | 8 | 4 |
| A | 8 | 8 | 16 | 8 |
| Mittelwert | 7,5 (Durchlaufzeit) | 3,5 |
Die Zellen, die Lernende ausfüllen, bleiben in dieser Vorschau leer.
Ein häufiger Fehler
Warnung
Viele glauben, das Verfahren mit der kleinsten mittleren Wartezeit sei immer das beste. SJF braucht aber Laufzeiten, die niemand sicher kennt, und lässt lange Prozesse verhungern. Ein Programm mit Benutzeroberfläche braucht schnelle Antworten. Wählen Sie die Kennzahl passend zum Ziel.
Round Robin tauscht Wartezeit gegen Fairness
Round Robin unterbricht jeden Prozess nach einer Zeitscheibe. Dadurch muss kein kurzer Prozess auf einen langen warten. Die mittlere Wartezeit ist meist größer als bei SJF, aber niemand wartet ewig.
Die Zeitscheibe muss gut gewählt sein. Ist sie sehr groß, wird Round Robin zu FCFS. Ist sie sehr klein, gehen viele Kontextwechsel auf Kosten der Rechenzeit.
Beispiel: dieselben Aufträge nach Round Robin
| Auftrag | Laufzeit | Ende | Durchlaufzeit | Wartezeit |
|---|---|---|---|---|
| A | 8 | 16 | 16 | 8 |
| B | 2 | 4 | 4 | 2 |
| C | 4 | 12 | 12 | 8 |
| D | 2 | 8 | 8 | 6 |
| Mittelwert | 10 | 6 |
Die Zellen, die Lernende ausfüllen, bleiben in dieser Vorschau leer.
Linux gewichtet Prozesse mit dem Nice-Wert
Unter Linux stellen Sie mit nice ein, wie rücksichtsvoll ein Prozess gegenüber anderen ist. Ein höherer Wert heißt: Der Prozess lässt anderen den Vortritt. Der normale Wert ist 0. Nur root darf negative Werte setzen.
Mit -n 5 startet nice ein Programm mit dem Wert 5. Im Befehl unten ist dieses Programm wieder nice. Es gibt den Wert aus, den es geerbt hat.
Einen Prozess mit Nice-Wert 5 starten
nice -n 5 niceHier angezeigt, nicht ausgeführt. Erstellen Sie ein kostenloses Konto, um „Ausführen“ zu drücken und ihn im Terminal Ihres eigenen Labs einzugeben.
Die mittlere Wartezeit nach FCFS nachrechnen
python3 -c "b = [8, 2, 4, 2]; print(sum(sum(b[:i]) for i in range(len(b))) / len(b))"Hier angezeigt, nicht ausgeführt. Erstellen Sie ein kostenloses Konto, um „Ausführen“ zu drücken und ihn im Terminal Ihres eigenen Labs einzugeben.
Dieselbe Rechnung, kürzester Auftrag zuerst
python3 -c "b = sorted([8, 2, 4, 2]); print(sum(sum(b[:i]) for i in range(len(b))) / len(b))"Hier angezeigt, nicht ausgeführt. Erstellen Sie ein kostenloses Konto, um „Ausführen“ zu drücken und ihn im Terminal Ihres eigenen Labs einzugeben.