Ein Prozess-Scheduler ist ein „Steuerprogramm“, das die zeitliche Ausführung aller Prozesse im Betriebssystem regelt. Anhand verschiedener Scheduling-Strategien versucht dieser die Prozesse bestmöglich der CPU zuzuweisen, um diese schnellstmöglich abzuarbeiten.
Scheduling-Strategien
1. First-Come-First-Served (FCFS)
Prozesse werden in der Reihenfolge des Eingangs vollständig abgearbeitet
Vorteil: Es gibt eine feste Reihenfolge, in welcher jeder Prozess in absehbarer Zeit bearbeitet wird
Nachteil: Kurze Prozesse haben die selbe Wartezeit
| First-Come-First-Served | |||||||||||||||
| A | |||||||||||||||
| B | |||||||||||||||
| C | |||||||||||||||
| Einheit: 1 Kasten = 5ms | |||||||||||||||
| Benötigte Rechenzeit: A → 25ms, B → 10ms, C → 15ms | |||||||||||||||
| Prozesse kommen nacheinander (A: 0ms, B: 35ms, C:40ms) | |||||||||||||||
2. Shortest-Job-First (SJF)
Die Prozesse mit der kürzesten Rechenzeit werden zuerst abgearbeitet.
Voraussetzung: Die benötigte Rechenzeit muss sich vorhersagen lassen.
Vorteil: Es werden viele Prozesse in kurzer Zeit abgearbeitet.
Nachteil: Lange Prozesse haben eine hohe Wartezeit.
| Shortest-Job-First | |||||||||||||||
| A | |||||||||||||||
| B | |||||||||||||||
| C | |||||||||||||||
| Einheit: 1 Kasten = 5ms | |||||||||||||||
| Benötigte Rechenzeit: A → 25ms, B → 10ms, C → 15ms | |||||||||||||||
3. Round Robin (Rundlauf)
Für jeden Prozess existiert eine feste Zeitspanne (Zeitscheibe), in der er bearbeitet wird. Ist diese Zeitspanne überschritten, wird der Prozess pausiert und in die Warteschlange eingereiht, damit die CPU den nächsten Prozess bearbeiten kann.
Vorteil: Alle Prozesse werden gleich behandelt.
Nachteil: Round Robin ist unflexibel, somit bleiben Ressourcen meistens ungenutzt.
| Round Robin | |||||||||||||||
| A | |||||||||||||||
| B | |||||||||||||||
| C | |||||||||||||||
| Einheit: 1 Kasten = 5ms | |||||||||||||||
| Benötigte Rechenzeit: A → 25ms, B → 10ms, C → 15ms | |||||||||||||||
| Zeitscheibe: 10ms (Zeitscheibe nicht verkürzen) | |||||||||||||||
4. Priority Scheduling (Prioritätssteuerung)
Beim Priority Scheduling erhält jeder Prozess eine Priorität. Es wird der Prozess dem Prozessor zugewiesen, der die höchste Priorität besitzt. Wenn alle Prozesse die gleiche Priorität besitzen, erfolgt die Abarbeitung nach der Eingangsreihenfolge oder nach anderen, in der Aufgabe definierten Verfahren.
Vorteil: Wichtige Prozesse werden bevorzugt
Nachteil: Unwichtige Prozesse haben lange Wartezeiten bis zur Vergabe an die CPU
| Priority Scheduling | |||||||||||||||
| A (4) | 3 | 2 | 1 | 0 | 0 | ||||||||||
| B (1) | 0 | 0 | |||||||||||||
| C (2) | 1 | 0 | 0 | ||||||||||||
| Einheit: 1 Kasten = 5ms | |||||||||||||||
| Benötigte Rechenzeit: A → 25ms, B → 10ms, C → 15ms | |||||||||||||||
| Priorität: Priorität pro ZE um 1 verringern | |||||||||||||||
| Keine Eingangsreihenfolge, Abarbeitung nach Round Robin | |||||||||||||||
Deadlock
Definition: Ein Deadlock (Verklemmung) ist ein Zustand, bei dem sich eine Menge von Prozessen gegenseitig permanent blockiert. Dies ist der Fall, wenn jeder Prozess aus der Menge auf ein Ereignis wartet, das nur ein anderer Prozess aus der Menge auslösen kann.
Vorgehensweise:
1. Prozesse/Ressourcen identifizieren
2. Abhängigkeiten einzeichnen
3. „Kreise“ (Deadlocks) suchen
Deadlocks verhindern:
Da sich Deadlocks nicht einfach beseitigen lassen, ist es sinnvoll diese zu verhindern und vorbeugende Maßnahmen zu treffen:
- wechselseitiger Ausschluss: Betriebsmittel werden für alle Prozesse zugänglich gemacht. Auf diese Weise lässt sich ein möglicher wechselseitiger Ausschluss beseitigen.
- Bevorrechtigung: „Wichtigere“ Prozesse erhalten eine Bevorrechtigung, was bedeutet, dass einem anderen Prozess Ressourcen entzogen werden, um sie umzuverteilen.
- Halten und Warten: Jeder Prozess gibt zu Beginn an, welche Ressourcen er benötigt. Sind die erforderlichen Ressourcen nicht verfügbar, muss er warten.
- zyklische Abhängigkeit: Die Betriebsmittel werden zuerst linear geordnet und anschließend in aufsteigender Reihenfolge vergeben. Somit ist man in der Lage eine zyklische Abhängigkeit auszuschließen.
Deadlocks beseitigen:
- Prozesse zurücksetzen (Rollback): Ein Weg einen Deadlock zu beseitigen ist das zurücksetzen eines Prozesses. Dazu werden von jedem Prozess in bestimmten Abständen Sicherungen angelegt. Sollte es zu einer Verklemmung kommen, wird zu einer der Sicherungen zurückgesprungen. Ein Nachteil dieses Verfahrens ist, dass nicht alle Prozesse zurückgesetzt werden sollten.
- Prozess abbrechen: Die einfachste Möglichkeit ist das gezielte Abbrechen eines Prozesses. Jedoch muss darauf geachtet werden, einen Prozess zu wählen, der die Verklemmung sicher löst. Ansonsten müssen weitere Prozesse beendet werden.
- Beseitigung durch Preemption: Deadlocks können unter Anderem auch durch Pausieren eines Prozesses beseitigt werden, der eine bestimmte Ressource belegt. In der Zwischenzeit können andere Prozesse die Ressource in Anspruch nehmen. Dadurch wird der Deadlock beseitigt und der pausierte Prozess wird zu einem späteren Zeitpunkt fortgesetzt.
Ressource-Allocation-Graph
Prozess besitzt eine Ressource:
Prozess wartet auf eine Ressource:
Begriffe
- Startzeit: Zeitpunkt, in dem der Prozess dem Prozessor das erste Mal zugewiesen wurde
- Wartezeit: Zeit, in welcher der Prozess auf den Prozessor wartet
- Endzeit: Zeitpunkt, in dem der Prozess vom Prozessor fertig abgearbeitet wurde
- Ankunftszeit: Zeitpunkt, ab welcher der Prozess dem Prozessor zugewiesen werden kann
- Verweilzeit: Zeit, ab der Ankunftszeit bis zur Endzeit