Prozessplanung: Ziele, Kriterien und Scheduling-Algorithmen

Prozessplanungs-Prozess

Ziele

• Justiz: Prozesse sollten, wenn möglich, zugunsten einiger Prozesse gegenüber anderen vermieden werden.
• Maximale Anzahl interaktiver Benutzer: Fokus der Time-Sharing-Systeme.
• Vorhersagbarkeit: Die Strategie muss wissen, wie die Ausführung von Prozessen zu ermöglichen ist.
• Minimierung des Overheads: Es sollte versucht werden, Kontextwechsel zu minimieren.
• Gleichgewicht bei der Nutzung der Ressourcen: Die Ressourcen müssen fair und so lange wie möglich genutzt werden.
• Prioritäten für die Sicherheit: Bei der Festlegung von Prioritäten sollten diese eingehalten werden.
• Maximale Kapazität der Ausführung: Es sollte versucht werden, Änderungen zu minimieren, die verarbeitet werden müssen.

Kriterien

• Reaktionszeit: Geschwindigkeit, mit der das System auf eine Anfrage reagiert.
• Service-Zeit: Antwortzeit - Zeit für E/A.
• Laufzeit: Service-Zeit - Zeit außerhalb (vermutlich: Gesamtzeit minus Wartezeit).
• Prozessor-Zeit: Prozessorzeit-Nutzung.
• Timeout: Die Wartezeiten in den Warteschlangen.
• Wirkungsgrad: Prozessor-Auslastung.
• Ausbeute (Throughput): Anzahl der Aufträge pro Zeiteinheit.

Metriken

• $t_i$ = Startzeitpunkt der Ausführung (Time Executive Order).
• $t$ = Zeitpunkt der Ausführung.
• $t_f$ = Endzeitpunkt der Implementierung.
• $T$ = Servicezeit = $t_f - t_i$.
• $E$ = Wartezeit = $T - t$.
• $I$ = Service-Index = $t / T$.

Strategien (Scheduling-Politiken)

Geeignete Politiken

• Produzieren einen Prozesswechsel mit jeder Veränderung des Rahmens (Time-Sharing, Echtzeit usw.).

Nicht-unterbrechende Politiken (Non-Preemptive)

• Die Prozesse werden bis zu ihrem Ende ausgeführt (Batch-Verarbeitung).
• FIFO (First Come, First Out).
• SJN (Kürzester Job zuerst).
• LIFO (Last In, First Out).
• LJN (Nächster längster Job).

Unterbrechende Politiken (Preemptive)

• RR (Round Robin).
• SRT (Kürzeste Verbleibende Zeit).
• PRIORITY (Priorität).
• Mehrere Warteschlangen.

Details zu spezifischen Politiken

First In, First Out (FIFO)

• Auch bekannt als FCFS (First Come, First Served).
• Es ist eine non-preemptive Politik.
• Es ist sehr vorhersagbar.
• Der Service-Index verbessert sich für Prozesse, die länger warten mussten.
• Es hat keine sehr gute Leistung (im Sinne von geringer Wartezeit für alle).

Kürzester Job zuerst (SJN)

• Bekannt als Kürzester Job als Nächstes (Shortest Job Next).
• Es ist eine non-preemptive Politik.
• Es ist sehr vorhersagbar.
• Der Service-Index ist gut für kurze Prozesse.
• Es erfordert mehr Informationen als andere Politiken, um den nächsten auszuführenden Prozess zu bestimmen (heuristische Entscheidung).

Last In, First Out (LIFO)

• Auch bekannt als LCF (Last Come, First Served).
• Es ist eine non-preemptive Politik.
• Es ist sehr vorhersagbar.
• Der Service-Index verbessert sich für kürzere Prozesse (die zuletzt kamen).
• Es hat keine sehr gute Leistung.

Längster Job zuerst (LJN)

• Bekannt als Größter Job als Nächstes (Longest Job Next).
• Es ist eine non-preemptive Politik.
• Es ist sehr vorhersagbar.
• Der Service-Index ist gut für lange Prozesse.
• Es erfordert mehr Informationen als andere Politiken, um den nächsten auszuführenden Prozess zu bestimmen (heuristische Entscheidung).

Round-Robin (RR)

• Auch bekannt als zyklische Verteilung.
• Es ist eine geeignete Politik (für Time-Sharing).
• Es ist unvorhersehbar (hinsichtlich der Fertigstellungszeit eines einzelnen Prozesses).
• Der Service-Index ist abhängig vom Zeitquantum ($q$), das in der Regel einen Wert zwischen 5 und 90 Millisekunden hat.
• RR versucht ständig, den Service-Index für kurze Prozesse zu optimieren.

Prioritäten

• Statisch: Der Wert ändert sich nicht während der Laufzeit des Prozesses.
• Dynamisch: Der Wert kann sich während der Laufzeit des Prozesses ändern.
• Intern: Der Wert hängt von einigen charakteristischen Merkmalen des Prozesses ab.
• Extern: Der Wert hängt von einem externen Faktor des Prozesses ab.

Unterbrechungen (Interrupts)

Ist ein Ereignis, das die Ausführungsreihenfolge auf dem Prozessor verändert.

Arten von Unterbrechungen

• Anleitung (Software-Interrupt): Erzeugt durch die System-Hardware oder durch den laufenden Code (Computing).

Ablauf einer Unterbrechung

1. Hardware übergibt die Steuerung an das Betriebssystem (BS).
2. Das BS speichert den Zustand des unterbrochenen Prozesses.
3. Das BS analysiert die Unterbrechung und übergibt die Steuerung an die entsprechende Routine.
4. Die Interrupt-Routine verarbeitet den Vorgang.
5. Es wird der Zustand des unterbrochenen Verfahrens wiederhergestellt oder der nächste Prozess ausgeführt.

Typen von Interrupt-Quellen

• Supervisor Calls (SVC): Benutzeranfragen für E/A.
• E/A: Gestartet durch Hard- und E/A-Geräte (z. B. Zustandsänderung (Bereitschaft)).
• Extern: Ablauf von Fristen, Unterbrechung durch einen anderen Prozessor.
• Neustart (Reset).
• Programmprüfung: Division durch Null, Überlauf bei Zahlen, Formatfehler, ungültiger Code.
• Machine Check.