ZHAW BSY Kap4

Batch Systeme:

• Verbeitung von Jobs erfolgt am Stück
• Non-preemtive  scheduling. (d.H. keine Unterbrechung durch scheduler sondern nur wenn Prozess blockiert)
• Ziel: Durchsatz, CPU-Nutzung und Turnaroundzeit zu minimieren.(Zeit zwischen Aufgabe und Terminierung)

Interaktive Systeme

• Umschaltung zwischen Anwendern resp. deren Prozessen notwendig
• Preemtive Scheduling (d.H: Prozesse erhalten CPU während ihres time-slices, Scheduler unterbricht Prozess wenn time-slice abgelaufen und Umschaltung wenn Prozess blockiert
• Ziel: Antwortzeit und Erfüllen der Anwendererwartung

Real-time System

• Systemantwort: Deadlines müssen eingehalten werden
• Oft repetitive Aufgabe (z.B: alle 1/25s ein Bild rendern)
• Ziel: Keine Datenverluste und Vorhersagbarkeit

Ziel: Parallelisierung

Multicore Scheduling berücksichtigt

    • Load Balancing

    • Affinity (Tasks sollten auf eine CPU gebunden werden.)

    • Synchronisation / Kommunikation zwischen verschiedenen CPU's

Probleme:

• Task läuft lange auf CPU viele Daten ins Cache geladen - CPU-Wechsel Daten müssen neu geladen werden

• Task hält Spin-Lock, q läuft ab Task wird unterbrochen - Tasks die am Lock warten warten bis Task wieder läuft

• Lösungsansätze: Affinity Scheduling und Smart Scheduling 

Affinity Scheduling: Scheduler versucht Task immer auf gleicher CPU zu halten. Nachteil evtl schlechtere CPU Nutzung.

Smart Scheduling: Tasks, die Lock halten setzen flag. Falls flag gesetzt können sie nicht unterbrochen werden

First Come First Served:

- Antwortzeit lang, wenn Ausführungszeiten sehr unterschiedlich sind

- Durchsatz kein Thema

- Fairness lange und CPU-bound Prozesse werden bevorzugt schlechte Ausnutzung von I/O Geräten

- Verhungern (Starvation) nicht möglich

- Implementation einfach, minimaler Overhead 

Shortest Process Next:

- Antwortzeit gut für kurze Prozesse, lange Prozesse müssen warten verbessert mittlere Wartezeit

- Durchsatz hoch: viele kurze Prozesse

- Fairness bestraft lange Prozesse

- Verhungern möglich für lange Prozesse

- Overhead relativ hoch: Bestimmung resp. Schätzung der Rechenzeit 

Priority Scheduling:

-neue und aufgeweckte Prozesse werden anhand ihrer Priorität in die Ready Queue einsortiert

- Prozesse mit tiefen Prioritäten können verhungern mögliche Abhilfe: dynamische Prioritäten Prioritäten in Funktion der Zeit anpassen 

Round Robin:

Zum Einsatz kommt es beispielsweise als Prozess-Scheduler, wo es mehreren konkurrierenden Prozessen begrenzte Ausführungs-Ressourcen zuordnet. Das Round-Robin-Verfahren gewährt allen Prozessen nacheinander für jeweils einen kurzen Zeitraum während eines Zeitschlitzes Zuteilung zu einer ausführenden CPU;

- Time Slicing und Einsatz von ver. Queues

- Response Time gut für kurze Prozesse (P5 wird für q=1 stark bevorzugt) lange Prozesse müssen auf nächsten Time Slice warten: Tw = n⋅q (n Anzahl Prozesse)

- Throughput abhängig vom Time-Slice q (Zeit-Quantum q resp. Quantum q) tief, wenn q zu klein → zuviele Prozesse und zuviele Context Switches FCFS Verhalten wenn q (zu) gross

- Fairness Benachteiligung von I/O-bound Prozessen (nutzen ev. nicht ganzes q)

- Verhungern nicht möglich

- Overhead klein

Multilevel /Multilevel Feedback

 Prozesse werden in Abhängigkeit von ihrem bisherigen Ressourcenverbrauch dynamisch in eine dieser Warteschlangen eingeordnet.[1]

- Verschiedene Queues mit verschiedenen prioritäten.

- Dispatcher sucht immer Prozesse aus der Queue mit der höchsten Priorität.

- Threads können verhundern (weil prozesse aus der Q1 nicht laufen können solange in Q2 Prozesse vorhanden sind)

Unix

- Multilevel Feedback, Round Robin innerhalb jeder Queue und dynamische Prioritäten

- Einteilung der Prozesse in Benutzer- und Systemprozesse

- Unterstützt effektive Nutzung von IO Geräten

- Unterstützt Real-Time Threads

Windows

- Nur Thread Scheduling (keine Prozesse)

- Multilevel feedback mit Round Robin Queue.

- Unterstützt sym. Multiprocessing und Real-Time Threads

Rate Monotonic Scheduling:

• Preemtives Verfahren für periodische Tasks
• Tasks werden anhand ihrer Priorität periodisch schedult. 
• Tasks müssen periodisch sein
• Tasks müssen unterbrechbar sein
• Tasks dürfen nicht voneinander abhängig sein
• bis 90% CPU Auslastung möglich

Deadline Scheduling

• Tasks zum richtigen Zeitpunkt starten und beenden.
• 100% CPU Auslastung möglich
• Mögliche Deadlines: Start deadline oder Completion deadline (Zeitpunkt an dem der Task beendet sein muss

Cyclic Executives

• Statisches Scheduling für zyklische Abläufe
• Non-preemtive

Long-Term: welche Prozesse werden f¨ur die Ausführung zugelessen bzw gestartet, (Prozesse in ready queue verschieben)

MediumTerm: welche Prozesse werden im Speicher gehalten, welche ausgelagert,

Short-Term: Dispatcher → welcher Prozess wird ausgeführt.

• CPU-bound: Prozess ”rechnet” haupst¨achlich, sehr wenig I/O
• I/O-bound: Prozess f¨uhrt vor allem I/O Operatione aus und wartet demzufolge oft.

• preemtive: Prozesse werden vom BS unterbrochen oder gebem CPU freiwillig ab
• nonpreemptive: Prozesse werden vom BS nicht unterbrochen, Unterbruch bei blockierendem System-Call und wenn CPU freiwillig abgegeben.

First come first Serve

Resultat der Berechunung muss richtig sein aber zu¨astzlich zum ”richtigen” Zeitpunkt. Meist spezielles Scheduling-Verfahren, keine interaktive Tasks.

Software Real-Time Scheduling, höhere Priorität, kann ev. nicht mehr abgebrochen werden (Progrmmierfehler) → neu booten.