Scheduling

Definition

Scheduling

Abarbeitungsreihenfolge bestimmen - Zuteilung der CPU-Zeit an Prozesse

Optimierungsziele / Scheduling Kriterien:

User-Oriented

Response Time

Turnaround Time

Meeting Deadlines

Predictability

System-Oriented

Throughput

Procesor Utilization

Fairness

Resource Balance

Priorities

Alles über der Linie bezieht sich auf Performance.

Die Ziele können einander widersprechen: zB Fairness und Einhaltung von Deadlines

Begriffe

Response Time Zeit zwischen Eintritt in ready und erster Instruktion auf CPU

Turnaround Time Zeit zwischen Eintritt in ready und Abschluss

Normalized Turn.Time Turn around time dividiert durch service time (= % Wartezeit)

Throughput Duschsatz: Anzahl der abgeschlossenen Prozesse per Zeiteinheit

Processor Utilization Prozessorauslastung

Fairness Verhältnis von Warte-Zeit zu CPU-Zeit

Scheduling Arten

Long-term-scheduling

new $-~?\rarr$ ready

Kreierung von Prozessen (hinzufügen zu new )

Grad der Parallelität, CPU-IO-Anteil bestimmen

Medium-term-scheduling

new/ready/running $-~?\rarr$ ready-suspend/blocked-suspend

Zuständig für Swapping

Welche Prozesse sollen suspendiert / ausgelagert werden wenn die Resourcen knapp werden?

Short-term-scheduling= Dispatching

ready $-~?\rarr$ runningauf der CPU

Wird mit Priorisierung genutzt.

Dispatcher wird bei einem process switch aktiviert:

System Calls

Traps

Interrupt: IO Interrupt, Clock Interrupt (spezieller interrupt)

Signale

____________

Scheduling Strategien

In der Praxis werden mehrere Strategien kombiniert und an verschiedenen Zeiten verwendet.

Wir behandeln hier short-term-scheduling.

Selection function

Funktion zB basierend auf:

Arrival Time / Ankunftszeit

Elapsed time / bisherige Ausführungszeit - wie lang ist Prozess schon im System

Service Time / Burst time / CPU Time / Gesamte Abarbeitungszeit / Gesamte Ausführungszeit

Deadline der Fertigstellung

$\dots$

Decision mode

Non-preemptive Wie bei traditionellen batch-OS, keine externe Unterbrechung durch OS

Preemptive OS kann Prozess unterbrechen

Priorisierung von Prozessen

(Allgemeine Implementierung)

$\downarrow$ Ready-Queue-Index = $\uparrow$ Priorität.

2 Wege aus CPU: Prozesse preempten oder vollständig ausführen.

Starvation möglich.

Lösung: Verweildauer in Queue beschränken.

1) First Come First Served FCFC

Selection Function First Arrival Time / Ankunftszeit

Decision Mode Non-Preemptive

Problem: Schlechte Auslastung

Begünstigt lange Prozesse

Durchschnittliche haben kurze und lange Prozesse gleich lange Wartezeiten (normalized turnaround time) in der Queue, aber lange Prozesse erhalten mehr CPU Zeit, da sie nicht unterbrochen werden.

Begünstigt CPU-intensive Prozesse

Monopolisierung wenn ohne IO

IO-System wird nicht parallel zur CPU benutzt

Schlechte Interaktivität

2) Round Robin RR / Time Slicing

Selection function First Arrival Time / Ankunftszeit

Decision mode Preemptive

Implementierung

Clock interrupt: Gleich lange Zeitscheiben zyklisch an Prozesse vergeben.

Zyklisch: nach interrupt wieder in die ready-queue gestellt.

Clock interrupt darf nicht ins gewicht fallen sonst zu viel Overhead

Zeitscheibenlänge $>$ Clock Interruption time $+$ scheduling switch time

und bisschen länger als eine typische Interaktion sein.

Problem

Keine gute Response Time bei Interaktiven Prozessen

IO-Intensive Prozesse benachteiligt, da diese die Zeitscheiben nicht voll ausnutzen

Lösung

Virtual Round Robin - mit Auxiliary Queue

IO Operationen in Hilfs-Queue werden priorisiert

3) Shortest Process Next SPN

Selection Function Shortest estimated Service-Time first / Gesamte Abarbeitungszeit

Decision Mode Non-Preemptive

Vorteil

Mehr fairness als FCFS.

Probleme

Reine Abschätzung der Abarbeitungszeiten (Bevor Prozess überhaupt gestartet ist)

Wenn estimated service time zu lange, kann es zu starvation führen

Response Time kann ganz unterschiedlich sein

Langer Prozess, der früh ankommt wenn es keine kürzeren gibt und keine IO-Interrupts hat kann CPU monopolisieren

Nicht für interaktive Prozesse geeignet

4) Shortest Remaining Time SRT

Selection Function Shortest Remaining Time (= Service Time - Elapsed time)

Decision Mode Preemptive

Implementierung

Sobald ein neuer Prozess in queue gestellt wird, wird aktueller Prozess interrupted.

Dann wird Prozess mit shortest remaining time until completion gewählt.

Vorteil

Mehr fairness als FCFS.

Weniger Interrupts als RR

Nachteil

Overhead: Protokollieren elapsed time notwendig

Benachteiligt lange Prozesse - Starvation möglich

5) Highest Response Ratio Next HRRN

Selection Function

Versucht kurze Prozesse zu priorisieren aber nicht zu starvation bei langen Prozessen zu führen.

$\argmax(\frac{\textsf{w+s}}{\textsf{s}}) = \argmax(\frac{\textsf{w}}{\textsf{s}}+1)$

$\textsf w$ gesamte bisherige Wartezeit des Prozesses im System

$\textsf s$ abgeschätzte Abarbeitungszeit (service time)

$\frac{\textsf w+ \textsf s}{\textsf s}$ response ratio (RR)

Das bedeutet:

Kurze Prozesse erzeugen eine große Zahl durch kleine Werte im Nenner

Prozesse die lange genug gewartet haben kommen irgendwann auch dran
Es wird jener Prozess ausgewählt, die in Relation zur eingeschätzten Abarbeitungszeit am längsten bisher gewartet hat.

Decision Mode

Non-Preemptive

Vorteil keine Starvation von langen Prozessen und kürzere Prozesse fair behandelt

Nachteil Reine Abschätzung der Abarbeitungszeit

6) Feedback Scheduling FS

Selection Function

Versucht ohne im Voraus abgeschätze Abarbeitungszeit auszukommen und kurze Prozesse zu bevorzugen.

$\uparrow$ Elapsed Time = $\downarrow$ Priorität, $\uparrow$ Zeitscheiben

Wobei Priorität mit queues implementiert

Am Anfang starten alle Prozesse mit hoher Priorität und erhalten kurze Zeitscheiben.

Je mehr von ihnen ausgeführt wird (insgesamt mehr bei längeren Prozessen):

desto unwichtiger werden sie

desto länger werden sie auf einmal ausgeführt

Dadurch haben kurze Prozesse höhere Priorität.

Decision Mode

Preemptive

Vorteil keine Abschätzung der Abarbeitungszeit im Voraus notwendig

Problem Starvation von langen Prozessen möglich

Lösung Anheben der Priorität nach bestimmter Zeit

Echtzeitscheduling / Real-Time Scheduling

Applikation / Anwendung hat Menge an Deadlines (soft vs. hard / critical) .

Es geht nicht um Performance / dass alles möglichst schnell abgearbeitet wird sondern Einhalten von critical Deadlines.

Prozesse oft periodisch

Die meisten scheduler sind preemptive

statische vs. dynamische Prioritäten

7) Earliest Deadline First EDF

Selection Function Earliest Completion Deadline first

Decision Mode Preemptive

Eigenschaften

Optimaler Scheduler: Beweisbar optimal darin # der deadline misses zu minimieren.

Setzt statische Deadlines und gleichzeitiges Eintreffen von einander unabhängiger Tasks voraus.

Deadlines müssen sortiert werden.

Schedulability Test

Statisch vor Nutzung testen ob Tasks rechtzeitig beendet werden können

$T_i$ Periodendauer alle unsere Tasks sind periodisch.

$C_i$ Ausführungszeit (müssen wir im Voraus wissen)

$i$ Index für Prozess

Es muss gelten: $\sum_i \frac{C_i}{T_i} \leq 1$

$\frac{C_i}{T_i}$ CPU-Auslastung durch einen Task (in einer Periode)

Das bedeutet Gesamt-CPU-Auslastung $\leq 100\%$ für alle Tasks

Beispiel mit fixen Prioritäten

Wichtig: hier vernachlässigen wir scheduling overhead

$A$ und $B$ sind tasks die periodisch auftreten $(A_1, A_2, \dots A_n),~(B_1, B_2, \dots B_n)$ und immer dieselbe execution time und arrival time haben.

Statische Prioritätsvergabe priorisierung von $A$ oder $B$ - Deadlines nicht eingehalten

Dynamische Prioritätsvergabe (EDF) alle Deadlines eingehalten.