Alle Tabs der Lerneinheit (Erklärung · Interaktiv verstehen · Praxis-Übung · Klausur-Quiz) als durchgehender Text. Ideal zum Wiederholen vor der Klausur, und für Suchmaschinen wie Google, Bing und KI-Suche (ChatGPT, Perplexity).
Erklärung
Scheduling: FCFS, SJF, Round-Robin
Mehrere Prozesse, eine CPU: wer kommt wann dran? Das ist die Aufgabe des Schedulers. Klausurpflicht in praktisch jedem Betriebssysteme-Modul, fast immer mit Gantt-Chart-Rechenaufgabe.
Die Idee in einem Satz
Der CPU-Scheduler entscheidet, welcher bereite Prozess als nächstes die CPU bekommt. Verschiedene Algorithmen (FCFS, SJF, Round-Robin, Priority) optimieren unterschiedliche Ziele: Durchsatz, Wartezeit oder Fairness.
Wichtige Kennzahlen
| Kennzahl | Definition | Formel |
|---|---|---|
| Ankunftszeit | Wann der Prozess bereit wird | gegeben |
| Bedienzeit (Burst) | Wie lange er die CPU braucht | gegeben |
| Fertigstellung (Completion) | Wann er fertig ist | berechnet |
| Durchlaufzeit (Turnaround) | Fertigstellung − Ankunft | T = C − A |
| Wartezeit | Durchlaufzeit − Bedienzeit | W = T − B |
| Antwortzeit (Response) | Erste CPU-Zuteilung − Ankunft | wichtig bei interaktiv |
Ziel meist: durchschnittliche Wartezeit minimieren.
Preemptive vs. Non-Preemptive
- Non-preemptive: ein laufender Prozess behält die CPU, bis er fertig ist oder selbst blockiert (FCFS, SJF-basic).
- Preemptive: der Scheduler kann einen laufenden Prozess unterbrechen (Round-Robin via Timer, SRTF, Preemptive Priority).
FCFS (First Come First Served)
Prinzip: wer zuerst kommt, mahlt zuerst. Non-preemptive. Wie eine Warteschlange an der Kasse.
P1 (Burst 7) | P2 (Burst 4) | P3 (1) | P4 (4)
0 7 11 12 16
Vorteil: einfach, fair im Ankunfts-Sinn. Nachteil: Convoy-Effekt (ein langer Prozess blockiert kurze, die dahinter warten). Schlechte durchschnittliche Wartezeit.
SJF (Shortest Job First)
Prinzip: der Prozess mit der kürzesten Bedienzeit kommt zuerst. Non-preemptive.
Optimal: SJF minimiert die durchschnittliche Wartezeit (beweisbar, bei gleichzeitiger Ankunft).
Nachteil:
- Starvation (Aushungern): lange Prozesse kommen nie dran, wenn ständig kurze nachkommen.
- Bedienzeit unbekannt: man muss die Burst-Zeit vorher kennen (in Praxis: schätzen via exponentielles Mittel).
Preemptive Variante: SRTF (Shortest Remaining Time First): wenn ein kürzerer Prozess ankommt, wird der laufende unterbrochen.
Round-Robin (RR)
Prinzip: jeder Prozess bekommt ein festes Zeit-Quantum (z.B. 2 ms). Danach wird er hinten in die Warteschlange gestellt. Preemptive.
Quantum = 2:
P1 | P2 | P1 | P3 | P4 | P1 | P2 | P4 | ...
Vorteil: fair, gute Antwortzeit, ideal für interaktive Systeme (Time-Sharing). Nachteil: Quantum-Wahl kritisch:
- Zu klein → viele Kontextwechsel (Overhead).
- Zu groß → degeneriert zu FCFS.
- Faustregel: Quantum etwas größer als typische Interaktion (10-100 ms).
Priority Scheduling
Prinzip: jeder Prozess hat eine Priorität, höchste Priorität kommt zuerst. Kann preemptive oder non-preemptive sein.
Nachteil: Starvation niedrig-priorer Prozesse. Lösung: Aging (Priorität steigt mit Wartezeit).
Multilevel-Feedback-Queue (MLFQ)
Moderne Scheduler (Linux CFS, Windows): mehrere Warteschlangen mit unterschiedlichen Prioritäten + Quanten. Prozesse wandern zwischen Queues je nach Verhalten (CPU-bound sinkt, I/O-bound steigt). Kombiniert Fairness + Reaktionsfähigkeit.
Vergleich der Algorithmen
| Algorithmus | Preemptive? | Optimiert | Problem |
|---|---|---|---|
| FCFS | nein | Einfachheit | Convoy-Effekt |
| SJF | nein | Ø Wartezeit (optimal) | Starvation, Burst unbekannt |
| SRTF | ja | Ø Wartezeit (preemptive) | Starvation |
| Round-Robin | ja | Fairness, Antwortzeit | Quantum-Wahl |
| Priority | beides | wichtige Tasks zuerst | Starvation (→ Aging) |
Beispiel-Rechnung (FCFS)
Prozesse: P1(A=0, B=7), P2(A=2, B=4), P3(A=4, B=1), P4(A=5, B=4).
| Prozess | Ankunft | Burst | Start | Fertig | Turnaround | Wartezeit |
|---|---|---|---|---|---|---|
| P1 | 0 | 7 | 0 | 7 | 7 | 0 |
| P2 | 2 | 4 | 7 | 11 | 9 | 5 |
| P3 | 4 | 1 | 11 | 12 | 8 | 7 |
| P4 | 5 | 4 | 12 | 16 | 11 | 7 |
Ø Wartezeit = (0+5+7+7)/4 = 4,75. Mit SJF wäre sie deutlich kleiner.
Klausur-Faustregeln
1. Wartezeit = Turnaround − Burst, Turnaround = Fertig − Ankunft. Auswendig.
2. SJF minimiert die durchschnittliche Wartezeit (optimal).
3. FCFS leidet unter Convoy-Effekt. Langer Prozess blockiert kurze.
4. Round-Robin braucht ein Quantum, ist fair und preemptive.
5. Priority + Starvation → Aging als Lösung.
6. Gantt-Chart zeichnen, dann Kennzahlen ablesen. Immer der Lösungsweg.
Häufige Stolpersteine
1. SJF minimiert Wartezeit, NICHT Durchlaufzeit als Primärziel (zwar auch, aber die klassische Optimalitäts-Aussage ist die Wartezeit).
2. Wartezeit-Formel verwechseln. Wartezeit = Turnaround − Burst, NICHT Start − Ankunft (das ist nur bei non-preemptive identisch).
3. Round-Robin-Quantum-Effekt. Quantum → ∞ wird zu FCFS, Quantum → 0 zu reinem Overhead.
4. Priorität-Richtung. Konvention oft: niedrige Zahl = hohe Priorität (1 vor 3). In Klausur immer prüfen, was definiert ist.
5. Bei gleicher Ankunftszeit: SJF sortiert nach Burst, Reihenfolge bei Gleichstand meist nach Prozess-Nummer.
6. Idle-Zeit der CPU. Wenn kein Prozess bereit ist, ist die CPU idle: das muss im Gantt-Chart als Lücke berücksichtigt werden.
Interaktiv verstehen
Scheduling, interaktiv
Vier Prozesse mit Ankunfts-/Bedienzeit + Priorität. Wähle den Algorithmus (FCFS / SJF / Round-Robin / Priority) und sieh das Gantt-Chart + die berechnete durchschnittliche Wartezeit und Durchlaufzeit. Bei Round-Robin kannst du das Quantum verändern.
Vergleiche: welcher Algorithmus erzeugt die geringste Wartezeit?
Interaktive Visualisierung
Interaktive Komponente: probiere sie im Topic-Player oben aus.
Klausur-Tipp: Immer zuerst das Gantt-Chart zeichnen, dann Fertigstellungs-Zeiten ablesen, dann Turnaround (Fertig − Ankunft) und Wartezeit (Turnaround − Burst) pro Prozess berechnen, dann mitteln. SJF sollte die kleinste Ø Wartezeit liefern.
Praxis-Übung
Scheduling, Praxis-Übung
6 Aufgaben zu FCFS, SJF, Round-Robin und Kennzahlen.
Klausurfragen mit Lösungen (6)
- F1.Welcher Scheduling-Algorithmus minimiert die durchschnittliche Wartezeit (bei gleichzeitiger Ankunft)?
Antwort: SJF (Shortest Job First)
Erklärung: SJF (Shortest Job First) minimiert beweisbar die durchschnittliche Wartezeit, wenn alle Prozesse gleichzeitig ankommen. Kurze Jobs zuerst = die wartende Gesamt-Zeit aller Jobs wird minimal. Nachteil: lange Jobs können aushungern (Starvation) und die Bedienzeit muss bekannt/geschätzt sein. Klausur-Kernaussage.
- F2.Wie berechnet man die Wartezeit eines Prozesses?
Antwort: Wartezeit = Durchlaufzeit − Bedienzeit
Erklärung: Wartezeit = Durchlaufzeit (Turnaround) − Bedienzeit (Burst). Die Durchlaufzeit = Fertigstellung − Ankunft. Die Wartezeit ist die Zeit, die der Prozess insgesamt wartet, ohne die CPU zu nutzen. Klausur-Pflicht-Formel.
- F3.Ordne Scheduling-Algorithmus seinem Hauptmerkmal zu.
Zuordnungen:
- FCFS → Convoy-Effekt, non-preemptive
- SJF → minimale Ø Wartezeit, Starvation-Gefahr
- Round-Robin → Zeit-Quantum, fair, preemptive
- Priority → wichtige Tasks zuerst, Aging gegen Starvation
Erklärung: FCFS: einfach, aber Convoy-Effekt (langer Job blockiert kurze). SJF: optimale Ø Wartezeit, aber Starvation. Round-Robin: Quantum-basiert, fair, ideal interaktiv. Priority: wichtige Tasks zuerst, Aging (Prio steigt mit Wartezeit) verhindert Starvation. Klausur-Pflicht-Zuordnung.
Typ: Zuordnung
- F4.Was passiert bei Round-Robin, wenn das Zeit-Quantum sehr groß gewählt wird (größer als alle Bedienzeiten)?
Antwort: Es wird zu FCFS
Erklärung: Wenn das Quantum größer ist als jede Bedienzeit, läuft jeder Prozess komplett durch, bevor der nächste drankommt = identisch zu FCFS (First Come First Served). Umgekehrt: sehr kleines Quantum → viele Kontextwechsel → hoher Overhead. Die Quantum-Wahl ist der zentrale RR-Tuning-Parameter. Klausur-Verständnisfrage.
- F5.Round-Robin ist ein preemptive Scheduling-Verfahren: ein laufender Prozess wird nach Ablauf seines Quantums unterbrochen.
Antwort: Wahr
Erklärung: RICHTIG. Round-Robin ist preemptive: nach Ablauf des Zeit-Quantums wird der laufende Prozess durch einen Timer-Interrupt unterbrochen und hinten in die Bereit-Queue gestellt. FCFS und basic-SJF sind dagegen non-preemptive (laufender Prozess behält die CPU bis Ende). Klausur-Klassifikation.
Typ: Wahr/Falsch
- F6.Was ist der Convoy-Effekt bei FCFS?
Antwort: Ein langer Prozess vorn blockiert viele kurze Prozesse, die dahinter warten müssen, was die Ø Wartezeit stark erhöht
Erklärung: Der Convoy-Effekt: bei FCFS muss ein kurzer Prozess, der nach einem langen ankommt, die gesamte Bedienzeit des langen abwarten (wie LKWs hinter einem langsamen Fahrzeug). Folge: hohe durchschnittliche Wartezeit. SJF löst das, indem kurze Prozesse vorgezogen werden. Klausur-Schlüsselbegriff.
Klausur-Quiz
Scheduling, Klausur-Quiz
6 Klausur-Fragen mit Algorithmen, Kennzahlen und Gantt-Berechnung.
Klausurfragen mit Lösungen (6)
- F1.Was ist die Aufgabe des CPU-Schedulers?
Antwort: Entscheiden, welcher bereite Prozess als nächstes die CPU bekommt
Erklärung: Der CPU-Scheduler (Kurzzeit-Scheduler) entscheidet, welcher der BEREITEN Prozesse als nächstes die CPU zugeteilt bekommt. Er läuft sehr häufig (bei jedem Kontextwechsel) und muss daher schnell sein. Ziel: CPU-Auslastung, Durchsatz, Wartezeit, Antwortzeit oder Fairness optimieren (je nach Algorithmus). Klausur-Definition.
- F2.Was bedeutet 'preemptive' Scheduling?
Antwort: Der Scheduler kann einen laufenden Prozess unterbrechen und die CPU einem anderen geben
Erklärung: Preemptive Scheduling: der laufende Prozess kann unterbrochen werden (z.B. durch Timer-Interrupt bei Round-Robin, oder wenn ein höher-priorer Prozess ankommt). Non-preemptive: ein laufender Prozess behält die CPU, bis er fertig ist oder selbst blockiert (I/O). FCFS und basic-SJF sind non-preemptive, RR und SRTF preemptive. Klausur-Schlüsselkonzept.
- F3.Ordne Kennzahl ihrer Formel zu.
Zuordnungen:
- Durchlaufzeit (Turnaround) → Fertigstellung − Ankunft
- Wartezeit → Durchlaufzeit − Bedienzeit
- Antwortzeit (Response) → Erste CPU-Zuteilung − Ankunft
- Bedienzeit (Burst) → gegeben (CPU-Bedarf)
Erklärung: Turnaround = C − A (gesamte Verweildauer im System). Wartezeit = Turnaround − Burst (Zeit ohne CPU-Nutzung). Antwortzeit = erste Zuteilung − Ankunft (wichtig bei interaktiv: wie schnell reagiert das System?). Burst = gegebener CPU-Bedarf. Klausur-Pflicht-Formeln.
Typ: Zuordnung
- F4.Wie löst man das Starvation-Problem beim Priority-Scheduling?
Antwort: Durch Aging: die Priorität eines wartenden Prozesses steigt mit der Wartezeit
Erklärung: Aging: je länger ein Prozess wartet, desto höher wird seine Priorität. So kommt auch ein ursprünglich niedrig-priorer Prozess irgendwann dran und hungert nicht aus (Starvation). Aging ist die Standard-Lösung für Starvation bei Priority- und SJF-Scheduling. Klausur-Standard-Lösung.
- F5.FCFS (First Come First Served) ist ein preemptive Scheduling-Verfahren.
Antwort: Falsch
Erklärung: FALSCH. FCFS ist NON-PREEMPTIVE: ein Prozess, der die CPU bekommt, behält sie bis zum Ende seiner Bedienzeit (oder bis er selbst blockiert). Es gibt keine Unterbrechung durch den Scheduler. Das führt zum Convoy-Effekt. Preemptive Verfahren sind z.B. Round-Robin und SRTF. Klausur-Klassifikations-Stolperstein.
Typ: Wahr/Falsch
- F6.Drei Prozesse kommen gleichzeitig (t=0) an: P1(Burst 6), P2(Burst 2), P3(Burst 4). Wie hoch ist die durchschnittliche Wartezeit bei SJF?
Antwort: 2,67
Erklärung: SJF-Reihenfolge nach Burst: P2(2) → P3(4) → P1(6). Gantt: P2[0-2], P3[2-6], P1[6-12]. Wartezeiten: P2=0, P3=2, P1=6. Ø = (0+2+6)/3 = 8/3 ≈ 2,67. Zum Vergleich FCFS-Reihenfolge P1→P2→P3 hätte Ø = (0+6+8)/3 = 4,67. SJF ist deutlich besser. Klausur-Rechenaufgabe.
