Scheduling

• Allgemein: Vorgehensweise bei der Zuteilung von Betriebsmitteln

• Konkret: Zuteilung des Prozessors auf Prozesse

Dispatcher

• Durchführung des Prozesswechsel

• Sicherung des Zustandes des laufenden Prozesses

• Aktivierung des nächsten Prozesses

• Auslastung der CPU

  • Ziel ist die 100%ige Auslastung der CPU

  • normal 40% - 90%

• Durchsatz (throughput)

  • Anzahl der Jobs pro Zeiteinheit sollte maximal sein

• Faire Behandlung (fairness)

  • Jeder Benutzer sollte im Mittel den gleichen CPU-Zeitanteil erhalten

  • Es wird zwischen weak fair und strong fair unterschieden

• Wartezeit (waiting time)

  • Wartezeit in der Bereit-Liste minimieren (einziger Scheduling-parameter)

• Ausführungszeit (turnaround time)

  • Die Zeitspanne vom Jobbeginn bis zum Jobende sollte minimal sein. Sie enthält alle Zeiten in Warteschlangen, der Ausführung (Bedienzeit) und der Ein- und Ausgabe

• Antwortzeit (response time)

  • Die Zeit zwischen einer Eingabe und der Übergabe der Antwortdaten an die Ausgabegeräte sollte minimal werden (interaktive Systeme!)

• Vorhersehbarkeit

  • Wann erhält ein Prozess die CPU

• Je nach Anwendungstyp gibt es verschiedene Scheduling Ziele:

  • Batch

  • Dialog

  • Realtime

• Für Realtime System sind beispielsweise Vorhersehbarkeit besonders wichtig

• non-preemptive, auch „run-to-completion“-Verfahren:

  • Ein Prozess darf nicht unterbrochen werden, bis er seine Aufgaben vollständig erledigt hat.

  • MS-DOS und auch die ersten Windows-Systeme und noch Mac OS 9!

• preemptive Scheduling Verfahren

  • Rechenbereite Prozesse können suspendiert werden

  • Basis der Zeitscheibenverfahrens

  • Die meisten heutigen Betriebssysteme (Windows, Linux)

• Im Fall des preemptive Schedulings gibt es mehrere Strategien

• Die eingesetzten Strategien sind dabei abhängig von der Art der Systeme. Man unterscheidet:

  • Batch-Systeme

  • Dialog-Systeme

  • Realtime-Systeme

• In den aktuellen Betriebssystemen wird aber meistens eine Kombination von Strategien unterstützt

• Zeitscheibenverfahren (Timesharing)

  • CPU-Zuteilung durch Betriebssystem, wenn

    • laufender Prozess auf ein Ereignis wartet

    • laufender Prozess eine bestimmte Zeit den Prozessor nutzte

• Zeitscheibe = Quantum: 10 ms, 100 ms, ....

  • abhängig von CPU und Betriebssystem

  • Zeitscheibe je CPU

• Beispiel: Ein Quantum von 10 ms bedeutet 100 Kontextwechsel pro Sekunde (Overhead vernachlässigt)

• First Come First Serve (FCFS)

• Shortest Job First (SJF)

• Round Robin (RR)

• Priority Scheduling (PS)

• Batch-System

• bearbeitet die im System ankommenden Aufträge in der Reihenfolge ihres Eintreffens

• Batch System

• sucht sich dagegen immer den Job bzw. Prozess aus, von dem es die kürzeste Bedienzeit erwartet

• Verhungern (engl. Starvation)

  • von Prozessen ist möglich. Es kann also Prozesse geben, die nie eine CPU zugeteilt bekommen und daher nicht ausgeführt werden.

  • Beispiel SJF: Es kommen laufend kurze laufende Prozesse in die Queue. Damit wird der langlaufende Prozess nie fertig. Widerspricht der Fairness Forderung.

• Bestimmung der Zeit, die ein Prozess braucht, ist eigentlich nicht möglich. Daher ist das Verfahren SJF in der Praxis kaum umsetzbar

• RR

• FCFS in Verbindung mit einer Zeitscheibe.

• Alle Prozesse sind gleich wichtig.

• Jeder Prozess erhält ein bestimmtes Quantum der Zeitscheibe. Wenn das Quantum abgearbeitet ist, wird er hinten in die Warteschlange eingereiht und wartet bis er wieder drankommt.

• Länge der Zeitscheibe ist von großer Bedeutung für die Leistung des Systems

• wählt immer den Prozess mit der höchsten Priorität aus

  • Verwalten der Prioritäten

  • Jedem Prozess wird eine Priorität zugeordnet

  • Prozesse der gleichen Priorität kommen in eine gemeinsame Warteschlange. Hier gilt oft RR

  • Prozesse mit einer höheren Priorität kommen vor Prozesse mit einer niederen Priorität dran

Garantiertes Scheduling

• bezeichnet ein Verfahren, bei dem jeder Prozess der gleiche Anteil der CPU zugeteilt wird

• Bei n Prozesse bekommt jeder 1/n der CPU-Leistung zur Verfügung

• Die aktuelle Laufzeit in Relation zur tatsächlichen CPU-Zeit wird festgehalten. Der Prozess mit dem schlechtesten Verhältnis wird als nächstes ausgewählt und darf so lange aktiv bleiben, bis er die anderen Prozesse überrundet hat

Lottery Scheduling

• Jede Scheduling-Entscheidung erfolgt zufällig und wählt beispielsweise einen Prozess, der lauffähig wäre, zufällig alle n Sekunden aus und gibt diesen eine Zeitscheibe

• Round-Robin mit Prioritäten

• Prioritätenwahl:

  • statisch zu Beginn der Laufzeit und dann keine Änderung mehr

  • Dynamische adaptive Prioritätenwahl

  • Kombination der beiden Möglichkeiten, d.h. statische Festlegung zu Beginn und dann dynamisch adaptiv anpassen. (Heute bevorzugtes Verfahren)

  • Probleme:

    Gerechte Ressourcenzuteilung

• Aufbau einer eigenen Warteschlange für jede Priorität oder Prozesstyp

• Wenn die Prozesse die Warteschlange wechseln können, nennt man das Multi-Level-Feedback-Scheduling

• Round Robin Verfahren mit Prioritätensteuerung

• Folgende Aspekte sind zu beachten:

  • Wie wird die Priorität einzelner Prozesse bestimmt?

  • Wie lange soll die Zeitscheibe für einzelne Prozesse (das Quantum) sein?

    • Kurzes Quantum → hoher Overhead

    • Beispiel: Quantum 10 ms, Kontextwechsel: 1 ms → 10 % Overhead

    • Statische und/oder dynamische Festlegung möglich

    • 10 bis 200 ms heute üblich

• Wie wird die Priorität für einzelne Prozesse eingestellt bzw. ermittelt?

  • Statische Festlegung zum Start des Prozesses

  • Zusätzlich adaptive (dynamisch) Festlegung möglich

    → Man spricht dann auch von relativer Priorität

• In der Praxis stellt folgendes Verfahren einen recht guten Ansatz dar:

  • Das Quantum wird initial eingestellt

  • Anpassung dynamisch, so dass auch Prozesse mit niedriger Priorität die CPU ausreichend lange erhalten.

  • Ein-/Ausgabe-intensive Prozesse erhalten ein höheres Quantum, rechenintensive ein kürzeres. Damit können vernünftige Antwortzeiten von Dialogprozessen erreicht werden, und die rechenintensiven Prozesse können gut damit leben.

  • Die Prozess-Prioritäten werden statisch voreingestellt und unterliegen einer dynamischen Veränderung. Die aktuelle Priorität wird auch als relative Priorität bezeichnet.

  • Quantumgröße von 10ms bis 200ms

• Ursprüngliche Unix Systeme nehmen RR mit Prioritäten-Steuerung

  • Jede Priorität hat eine eigene Queue (Run-Queue)

  • Verfahren ist verdrängend

  • Prozesse sind die Einheiten für den Scheduler

  • Prioritäten von 0 bis 255 (0 höchste Priorität)

  • Initiale Priorität ändert sich mit der Zeit dynamisch

• Das Scheduling-Verfahren hat sich aus Unix heraus stark weiter entwickelt

  • Nutzt Threads als Scheduling-Einheit

  • drei Verfahren werden unterstützt

    • Timesharing (verdrängend)

    • Realtime mit FIFO (nicht verdrängend)

    • Realtime mit RR (verdrängend)

  • Seit Version 2.6.23 wird der Linux Completely Fair Scheduler (CFS) eingesetzt

    • Timesharing mit Prioritätensteuerung

    • Run-Queue-Verwaltung

• Andoid nutzt im Wesentlichen auch den CFS

• Betriebsmittelverwalter

  • führt eine Freiliste für die freien Betriebsmittel-Einheiten

  • teilt anfordernden Prozessen die Betriebsmittel zu

  • nimmt von einem Prozess nicht mehr benötigte Betriebsmittel entgegen

  • fordert die restlichen bei Prozessbeendigung oder -abbruch zurück

  • versetzt er sie wieder in einen definierten Ausgangszustand

• Bedingungen, bei denen Deadlocks auftreten können:

  • Exklusivität: Beteiligte Betriebsmittel müssen exklusiv belegt werden

  • Sequentialisierbarkeit: Zeitliche Reihenfolge des Zugriffs ist unerheblich

  • Unteilbarbarkeit: Die Belegung ist unteilbar

  • Beschränktheit: Sie sind nur in beschränkter Anzahl vorhanden.

• Äquivalente Betriebsmittel können auch zu Klassen zusammengefasst werden

Voraussetzung für Deadlock:

• Ausschlussbedingung, mutual exclusion condition:

  • Die Ressourcen müssen von den Prozessen exklusiv genutzt werden

• Bedingung der Zusatzanforderung, wait for condition:

  • Jeder Prozess hat bereits (mind.) ein Ressourcen belegt und fordert (mind.) ein weiteres an

• Nichtentziehbarkeit, no preemption condition:

  • Die Ressourcen können nicht entzogen werden

• Zirkuläre Wartebedingung, circular wait condition:

  • Es besteht ein geschlossener Kreis, in dem jeder Prozess ein Ressource anfordert, das vom jeweils nächsten Prozess belegt ist

• Notwendig für ein Deadlock ist das gleichzeitige Zutreffen von dieser 4 Bedingungen.

  => wenn eine der Bedingungen nicht erfüllt ist, kann es zu keinem Deadlock kommen

• Statische Verklemmungsverhinderung (deadlock prevention)

• Dynamische Verklemmungsvermeidung (deadlock avoidance)

• Verklemmungserkennung (deadlock detection)

• Verklemmungsbehebung (deadlock recovery)

• Deadlock-Verhinderung (deadlock prevention)

• Zu Ausschlussbedingung

  • Mit Datenpufferung/Spooling Exklusivität unterlaufen

• Zu Bedingung der Zusatzanforderung

  • Ein Prozess darf alle benötigten Betriebsmittel nur gleichzeitig anfordern bzw. muss warten, bis alle frei sind (one shot allocation); spez. Systemaufruf erforderlich

  • Probleme: dynamischer Ressourcen-Bedarf, Aushungern, Ressourcen-Verschwendung (z.B. Drucker)

• Zu Nichtentziehbarkeit

  • Bei Nichterfüllung der Ressourcen-Anforderung, muss der Prozess sämtliche belegten Ressourcen freigeben und dann die bisher gehaltenen und das zusätzlich gewünschte Ressourcen neu anfordern.

  • Problem: Konsistenz von Dateien, Rechenzeitverschwendung durch Neuberechnung, Aushungerung; in transaktionsgesicherten Prozessen jedoch praktikabel

• Zu zirkuläre Wartebedingung

  • Betriebsmittel nur in einer festgelegten aufsteigenden Reihenfolge anfordern, sonst müssen alle höher angeordneten Ressourcen freigegeben werden

  • Problem: richtige Festlegung der Reihenfolge (von selten zu häufig), Stabilität der Nummerierung, Notwendigkeit des Anerkennens der Regel durch alle Prozesse

• Versorgung der Prozesse mit dem Betriebsmittel „Arbeitsspeicher“ (Hauptspeicher)

• Verantwortliche Softwarekomponente ist der Memory Manager (Speicherverwalter)

• Der Memory Manager verwaltet die freien und belegten Speicherbereiche

• Dazu wird der Speicher entsprechend organisiert und adressiert.

• Heute geht man von dem Lokalitätsprinzip aus.

• Man unterscheidet zeitlich und örtliche Lokalität.

• Einfachste Form der Speicherverwaltung

• Nur ein Programm läuft zu einer Zeit

• Aufteilung des Speichers in feste Teile (Partitionen)

• Multiprogramming und Verbesserung der CPU-Auslastung möglich

• Job wird in eine Queue eingetragen

  • Für jede Partition eine Queue oder eine globale Queue

• Programme sind zu groß für den verfügbaren Arbeitsspeicher

• Aufspaltung der Programme in Overlays, die auf der Festplatte gespeichert werden und dynamisch ein- und ausgelagert werden.

• Ausführung:

  • Zunächst wird Overlay 0 ausgeführt

  • Wenn Overlay 0 beendet ist, wird Overlay 1 ausgeführt, etc.

  • Problem: Programmierer müssen Programme in kleine, modulare Teile aufspalten

• Eine Overlay-Struktur besteht aus:

  • einem speicherresidenten Programmteil (root program),

  • aus mehreren Unterprogrammen, die sich gegenseitig überlagern, und

  • aus gemeinsamen Daten (Common), die von Aufruf zu Aufruf erhalten bleiben sollen

Grundgedanke: Timesharing!

• Es passen nicht immer alle Prozesse in den Hauptspeicher

• Prozess wird im Gesamten geladen

• Prozess wird nach einer gewissen Zeit wieder auf einen Sekundärspeicher (Platte) ausgelagert

• Entstehende Löcher können durch Kombination benachbarter Speicherbereiche eliminiert werden, aber aufwändig!

Hauptunterschied zu festen Partitionen:

• Anzahl, Speicherplatz und Größe des für einen Prozess verwendeten Speicherbereichs variieren dynamisch

• Prozess wird immer dahin geladen, wo gerade ausreichend Platz ist

• Freispeicherverwaltung

  • Speicheranfrage (ob noch freier Speicher vorhanden ist)

  • Zuteilung eines Blocks gegebener Größe (Allokation)

  • Verlängerung eines bereits allozierten Blocks (ggf. mit Adresswechsel)

  • Rücknahme (mit Verschmelzung aneinandergrenzender Blöcke),

  • Kompaktifizierung (Lücken- oder Freispeichersammlung, garbage collection)

• Verschnittproblem:

  • interner Verschnitt: Speicherblöcke werden alloziert, die größer sind als gewünscht.

  • externer Verschnitt: (Stückelung, Fragmentierung)

• Abhilfe gegen den externen Verschnitt Kachelung: Aufteilung des angeforderten Blocks in physikalisch nicht aneinandergrenzende Bereiche einheitlicher Größe (Pages, Kacheln von z.B. 512 byte oder 4 Kbyte). Dazu ist eine spezielle Form der virtuellen Adressierung nötig

• Lückensammlung: (garbage collection).

  Belegte Blöcke werden zusammengeschoben, so dass die Lücken größer werden bzw. eine einzige Lücke entsteht.

  • bei Bedarf (Erschöpfung des Vorrats)

    => Zeitaufwand?!

  • bei CPU-Leerlauf durch den Leerlaufprozess / nebenläufiger Kompaktifizierungsprozess

• Vergabestrategien:

  • Sequentielle Suche, erster geeigneter Bereich wird vergeben (First-Fit oder rotating First-Fit)

    • Freiliste der Blöcke nach aufsteigenden Anfangsadressen geordnet

    • Falls der geforderte Block x ≠ L dem Block der Freiliste ist, wird das Reststück auf der Freiliste belassen

    • First fit: Suche beginnt jeweils beim vordersten Block, Rotating-first-fit arbeitet zirkulär

  • Optimale Suche nach dem passendsten Bereich, um Fragmentierung möglichst zu vermeiden (Best-Fit ,Worst-Fit)

    • Best-Fit:

      • Freiliste nach steigenden Blocklängen geordnet, also L1 ≤ L2 ≤ ... ≤ LM Suche Index i, so daß Li-1 < x <= Li

      • Falls ein Restblock übrigbleibt, muss er neu in die Freiliste eingeordnet werden

      • Problem: best-fit erzeugt besonders viele nutzlos kleine Blöcke erzeugt

    • Worst-Fit:

      • Suche unter den "passenden" Speicherbereichen, den größten

      • Vorteil: Verbleibende Reststücke können gut wieder genutzt werden

  • Zufällige Suche (random-Fit)

  • Buddy-Technik: Schrittweise Halbierung des Speichers bei einer Hauptspeicheranforderung

    • Speichervergabe:

      • Suche nach kleinstem geeigneten Bereich

      • Halbierung des gefundenen Bereichs solange bis gewünschter Bereich gerade noch in einen Teilbereich passt

    • Bei Hauptspeicherfreigabe werden Rahmen wieder zusammengefasst:

      • Zurückgegebenen Bereich mit allen freien Nachbarbereichen (und deren Partnern) verbinden und zu einem Bereich machen