<< 5.2 Thread-Konzept | Index | 5.4 Kontext-Wechsel >>


5.3 Scheduling

  • CPU-Scheduling
    • Treffen der Entscheidung: Welcher Prozess darf wann und wie lange die CPU nutzen?
    • Prozesswechsel durchführen
  • Ziele des Schedulings bei allen Verfahren
    • Fairness: Jeder Prozess bekommt CPU-Zeit
    • Policy Enforcement: Die gewählte Strategie wird auch tatsächlich umgesetzt
    • Balance: Alle Teile des Systems sind ausgelastet
  • Wird beeinflusst von:
    • Designparamtern
      • Ein-/Mehrprozessor, un-/unterbrechbare Prozesse, mit/ohne Deadlines, etc.
    • Leistungskriterien
      • Anforderungen an Wartezeit, CPU-Auslastung, Durchsatz, etc.

Mehrschichtiges Scheduling

  • Long-term Scheduling (LTS)
    • Verwaltung der Hintergrundprozesse
    • Entscheidend für den Multiprogramming-Grad
    • Nicht in jedem Betriebssystem enthalten
  • Medium-term Scheduling
    • Auslagern von Prozessen bei Überlastung
    • Einlagern wenn wieder Luft
    • Guter Prozessmix: I/O-Intensive und CPU-Intensive Prozesse gleichzeitig (beim Warten auf I/O kann gerechnet werden)
  • Short-term Scheduling
    • Auswahl eines Prozesses aus der Rechenwilligen-Liste, nicht notwendigerweise FIFO
    • Meist ausgelöst durch:
      • System-Call
      • I/O-Interrupt
      • Timer-Interrupt, Signale

Strategie-Klassen

  • Nicht unterbrechend (non-preemptive)
    • Keine automatische (zeitlich gesteuerte) Unterbrechung, nur durch System-Call oder I/O-Interrupt
    • Z. B. FCFS-Strategie
    • Vorteile:
      • Einfach zu implementieren
    • Nachteile:
      • Gefahr der Monopolisierung
  • Unterbrechend (preemptive)
    • Z. B. Zeitscheiben-Strategie, Round-Robin
    • Vorteile:
      • Keine Monopolisierung möglich
      • Gut für interaktive Systeme
    • Nachteile:
      • Problematisch für Ausführung von System-Calls (diese bleiben meistens ununterbrechbar)

Verweilzeit-optimale Strategien (VOP)

  • Nicht-unterbrechende Strategien
  • Shortest Job First (JFS)
    • Optimal, falls alle Prozesse gleiche Ankunftszeit haben
  • Shortest Remaining Time Next
    • Neues Scheduling wann immer ein neuer Prozess hinzu kommt, sonst ähnlich wie JFS
    • Geeignet für Long-term Scheduling
  • Probleme:
    • Ausführungsdauer der Prozesse muss bekannt sein, oder aus der Vergangenheit erahnt werden.
    • "Unfair" für langwierige Prozesse

Zeitscheiben-Strategie (Round Robin)

  • Unterbrechende Strategien
  • Merkmale:
    • Prozesse erhalten jeweils festes Zeitquantum q ("Zeitscheibe")
    • Spätestens nach dem Ablauf von q wird Prozess unterbrochen
    • Zyklisches Bedienen aller Prozesse
  • Probleme:
    • Wahl von q, typisch zwischen 10 und 100ms

Prioritäten-Strategie

  • Nicht alle Prozesse sind gleich wichtig, daher Prioritäten festlegen
    • Statische Prioritätenvergabe
      • Gilt für die Lebenszeit eines Prozesses
    • Dynamische Prioritätenvergabe
      • Prioritäten werden periodisch neu berechnet
        • Prozesse mit langer Wartezeit und niedriger Priorität hochstufen
        • Prozesse mit hoher Priorität und langer Rechenzeit runterstufen
  • Häufig Kombination aus Zeitscheiben und Prioritäten
    => mehrschichtige Warteschlangen

Strategien mit mehrschichtigen Warteschlangen (multilevel queues)

  • Prozesse werden je nach Typ in Gruppen unterteilt
    • Z. B. Hintergrundprozesse, System-Prozesse, interaktive Prozesse, ...
  • Verschiedene Gruppen werden unterschiedlich geschedulet
    • Unterschiedliche Scheduling-Parameter (z. B. Größe des Zeitquantums)
    • Unterschiedliche Scheduling-Strategien
  • Zuordnung in Gruppen kann sein:
    • Statisch (für die Lebensdauer des Prozesses)
    • Dynamisch (nach Laufzeitverhalten, z. B. CPU-Burst-Verhalten)
      => Multilevel-Feedback-Warteschlangen

Nach oben

Zuletzt geändert am 14 März 2005 19:04 Uhr von chrschn