CPU-Scheduling
Wie das Betriebssystem entscheidet, wer als Nächstes läuft, und warum diese Wahl sowohl Wartezeit als auch Fairness verändert.
Es gibt immer mehr Arbeit als CPU. Der Scheduler wählt jeweils einen bereiten Prozess, und diese Wahl bestimmt, wer wartet. Unterschiedliche Ziele — Durchsatz, Latenz, Fairness — führen zu unterschiedlichen Verfahren.
Ein langer Auftrag kommt zuerst. Beobachte, wie alles dahinter wartet.
| Prozess | Ankunft | Laufzeit | Zustand | Genutzt |
|---|---|---|---|---|
| P1 | 0 | 6 | wartend | — |
| P2 | 1 | 4 | wartend | — |
| P3 | 2 | 2 | wartend | — |
| P4 | 3 | 1 | wartend | — |
- P1
P1 kommt mit einer Laufzeit von 6ms an
- Mittlere Wartezeit
- 0
- Mittlere Bearbeitungszeit
- 0
- Gesamtzeit
- 0
| Verfahren | Mittlere Wartezeit | Mittlere Bearbeitungszeit | Gesamtzeit |
|---|---|---|---|
| First-Come, First-Served | 5.5 | 8.75 | 13 |
| Shortest Job First | 4 | 7.25 | 13 |
| Round-Robin | 5.75 | 9 | 13 |
Wartezeit ist, wie lange ein Prozess bereit war, ohne zu laufen. Bearbeitungszeit ist die Spanne von Ankunft bis Abschluss. Genau an diesen zwei Zahlen werden Scheduling-Verfahren gemessen.
Round-Robin gibt jedem Prozess ein festes Zeitfenster (Quantum) und rotiert. Kein Prozess wartet ewig, deshalb fühlt sich das System reaktionsschnell an — aber kurze Quanten bedeuten mehr Kontextwechsel, und die kosten echte Zeit.
# Правило, которое стоит запомнить:
#
# waiting time = (момент завершения - приход) - burst
# turnaround time = момент завершения - приход
#
# Пример из набора «convoy» (P1=6, P2=4, P3=2, P4=1):
#
# FCFS: P1[0..6] P2[6..10] P3[10..12] P4[12..13]
# среднее ожидание = (0 + 5 + 8 + 9) / 4 = 5.5
#
# SJF : P1[0..6] P4[6..7] P3[7..9] P2[9..13]
# среднее ожидание = (0 + 3 + 5 + 8) / 4 = 4.0
#
# SJF выигрывает, потому что короткие работы успевают
# пройти раньше, а не стоят за длинной. Это и есть convoy effect.Praxis
Welches Verfahren kann einen langen Auftrag unbegrenzt aushungern, wenn ständig kurze Aufträge eintreffen?
Hinweise
- Überlege, welcher Auftrag immer wieder von kürzeren überholt wird.
- Eines dieser Verfahren lässt einen neuen kurzen Auftrag nie vorrücken.
12 XP
Vergleiche unten im Simulator FCFS und SJF mit derselben Prozessmenge. Wo ist die mittlere Wartezeit geringer, und warum?
Hinweise
- Führe beide aus und vergleiche die mittlere Wartezeit, die der Simulator anzeigt.
- Frage dich, ob ein langer Auftrag die kurzen dahinter aufhält.
18 XP
Bringe die Scheduling-Entscheidungen von Round-Robin für P1(4ms), P2(2ms) bei einem Quantum von 2ms in die richtige Reihenfolge.
Hinweise
- Jeder Prozess erhält das Quantum, bevor er verdrängt wird.
- Ein Prozess, der früher fertig wird, verlässt die Warteschlange.
15 XP