Prozess-Scheduler

Prozess-Scheduler

Ein Prozess-Scheduler (Scheduler = Steuerprogramm) ist eine Arbitrationslogik, die die zeitliche Ausführung mehrerer Prozesse in Betriebssystemen regelt. Prozess-Scheduler kann man grob in unterbrechende (preemptive) und nicht unterbrechende (non preemptive, auch kooperativ genannt) aufteilen. Nicht unterbrechende Scheduler lassen einen Prozess, nachdem ihm die CPU einmal zugeteilt wurde, solange laufen, bis dieser diese von sich aus wieder freigibt oder bis er blockiert. Unterbrechende Scheduler teilen die CPU von vornherein nur für eine bestimmte Zeitspanne zu und entziehen dem Prozess diese daraufhin wieder. Weiter ist eine Unterscheidung in "work-conserving" und "non work-conserving" Strategien möglich. Eine Scheduler-Strategie arbeitet "work-conserving", wenn das Umschalten zwischen Prozessen nur eine vernachlässigbar geringe Zeit in Anspruch nimmt.[1] Man kann verschiedene Systeme unterscheiden, in welchen jeweils verschiedene Anforderungen an den Scheduler gestellt werden:

  1. Stapelverarbeitungssysteme
  2. interaktive Systeme
  3. Echtzeitsysteme

In Stapelverarbeitungssystemen sieht der Scheduler denkbar einfach aus: Ankommende Aufträge werden in eine Warteschlange eingereiht und jedes Mal, wenn ein Job abgearbeitet ist, kommt der nächste aus der Schlange dran (Queue-Manager).

Interaktive Systeme stellen andere Anforderungen: Der Benutzer legt Wert auf kurze Antwortzeit. Wenn er beispielsweise in einem Texteditor eine Tastatureingabe tätigt, sollte der Text sofort erscheinen.

In Echtzeitsystemen gibt es für jeden Job ein Zeitlimit, bis zu dem die Aufgabe erledigt sein muss. Siehe Real-Time Scheduling.

Typische Benutzer-PCs sind interaktive Systeme, auf denen gelegentlich auch Prozesse als so genannte Hintergrundprozesse mit niedrigerer Priorität ablaufen können.

Inhaltsverzeichnis

Ziele

Die Zuteilung der CPU an die Prozesse sollte bestmöglich erfolgen, wobei (abhängig vom ausführenden System) allerdings unterschiedliche Ziele verfolgt werden können:

Allgemein

  • Fairness: Kein Prozess sollte unverhältnismäßig lange warten müssen, während ein anderer bevorzugt wird.
  • Balance: Die Prozesse sollten der CPU auf eine Weise zugeteilt werden, dass auch andere Ressourcen wie Festplatte, Netzwerk-Schnittstelle u.a. ausgelastet sind.
  • Einhaltung der Systemregeln

Stapelverarbeitungssysteme

  • CPU-Auslastung: Die CPU sollte zu jeder Zeit ausgelastet sein. Es soll nicht vorkommen, dass die CPU sich im Leerlauf befindet, nur weil ein Prozess auf Daten von der Festplatte wartet.
  • Durchsatz: Die Anzahl beendeter Aufgaben pro Zeiteinheit sollte maximiert werden. Dies ergibt eine ähnliche Strategie wie die Auslastung, betrachtet aber mehr das tatsächliche Ergebnis.
  • kurze Turnaroundzeit (Durchlaufzeit): Die Zeit, die von der Ankunft eines Prozesses bis zu seiner vollständigen Beendigung vergeht, sollte minimiert werden.

Interaktive Systeme (Dialogsysteme)

  • Schnelle Antwortzeiten: Die Wartezeiten des Benutzers (oder anderer Systeme) sollten minimiert werden. Prozesse, die eine Interaktion mit dem Benutzer erfordern, sollten also bevorzugt werden vor solchen, die im Hintergrund stattfinden können.
  • Proportionalität: Die Antwortzeiten verschiedener Prozesse sollten den Erwartungen des Benutzers entsprechen. Werden Prozesse (wie z.B. das Schließen einer Anwendung) vom Benutzer als simpel betrachtet, sollten diese auch schnell ausgeführt werden.

Echtzeitsysteme

  • Deadlines einhalten
  • Vorhersagbarkeit: Wichtig für Multimedia-Anwendungen (da sonst z.B. Verschlechterung der Tonqualität droht)

Strategien

Das größte Problem des Schedulers ist die Tatsache, dass die benötigten Betriebsmittel für die einzelnen Prozesse nicht im Vorfeld bekannt sind. Es lässt sich also im Allgemeinen keine optimale Planung erstellen, sondern der Scheduler muss dynamisch auf geänderte Anforderungen reagieren. Dabei können (abhängig vom Scheduler) verschiedene Zuteilungsstrategien zum Einsatz kommen. Unter anderem:

  • First-Come First-Served (FCFS, FIFO): Hierbei werden alle Prozesse in der Reihenfolge ihres Eingangs bearbeitet. Eine Neuzuteilung der Prozesse findet erst statt, wenn der laufende Prozess zu warten beginnt oder seine Ausführung beendet ist.Diese Strategie erzielt eine gute Auslastung bezüglich der CPU, allerdings nicht bezüglich Ressourcen, die längere Zeit für eine Anforderung benötigen können, wie z. B. Ein-/Ausgabe oder Massenspeicher. Für Mehrbenutzersysteme ist die Strategie darüber hinaus wenig geeignet, da einzelne Benutzer so ggf. für längere Zeit (nämlich bei aufwendigen Prozessen anderer Benutzer) ausgeschlossen werden.
  • Shortest Job First (SJF, SPT) ist ein weiteres Verfahren, das nicht für Mehrbenutzersysteme geeignet ist. SJF lässt sich in Fällen einsetzen, in denen die benötigte Rechenzeit für einzelne Aufgaben aus Erfahrungswerten gut vorhergesagt werden kann. Ein Nachteil ist, dass große Prozesse u. U. niemals die CPU zugeteilt bekommen, wenn sich immer kürzere Jobs vordrängeln.
  • Shortest-Remaining-Time, Shortest-Remaining-Processing-Time entspricht dem SPT-Verfahren. Anders als beim SPT-Verfahren wird hier ein Prozesswechsel durchgeführt, wenn ein neu ankommender Prozess eine kürzere Ausführungszeit aufweist, als die verbleibende des aktuellen Prozesses.
  • Round Robin (Zeitscheibenverfahren): Einem Prozess wird die CPU für eine bestimmte (kurze) Zeitspanne zugeteilt. Danach wird der Prozess wieder hinten in die Warteschlange eingereiht.
  • Earliest Due Date: Bei dieser Strategie werden diejenigen Prozesse zuerst ausgeführt, welche die geringste Deadline haben. Voraussetzung dafür sind statische Deadlines und gleichzeitiges Eintreffen voneinander unabhängiger Tasks. Dieses nichtunterbrechende Verfahren ist ideal, um die maximale Verspätung zu minimieren.
  • Prioritätsscheduling: Bei dieser Strategie wird jedem Prozess eine Priorität zugeordnet. Die Abarbeitung erfolgt dann in der Reihenfolge der Prioritäten. Da es sich dann (innerhalb der gleichen Prioritäten) um eine Strategie der Eingangsreihenfolge handelt, wird diesem Verfahren meistens noch ein Zeitscheibenverfahren untergeordnet (diese nennt man dann u.a. auch Multilevel Feedback Queue Scheduling, Shortest-Elapsed-Time (SET) ), um trotzdem eine schnelle Antwortzeit zu ermöglichen. Zusätzlich wird in den verbreiteten Schedulern mit dynamischen Prioritäten gearbeitet, wobei sich die Priorität eines Prozesses mit der Zeit erhöht, damit auch niedrig priorisierte Prozesse irgendwann bearbeitet werden und nicht ständig von höher priorisierten Prozessen verdrängt werden.
  • Terminabhängige Ablaufplanung: Diese Strategie kommt hauptsächlich in Echtzeitsystemen vor. Dabei werden die Prozesse bevorzugt verarbeitet, die als erstes beendet sein müssen. Damit ist es möglich, eine definierte Antwortzeit für bestimmte Prozesse zu garantieren.

Scheduling-Verfahren

Literatur

Einzelnachweise

  1. Otto Spaniol: Systemprogrammierung : Skript zur Vorlesung an der RWTH Aachen, 1996, ISBN 3860734709

Wikimedia Foundation.

Игры ⚽ Нужна курсовая?

Schlagen Sie auch in anderen Wörterbüchern nach:

  • Scheduler — (englisch für: „Planer, Disponent“) steht für: Scheduler (Datenbank), verwaltet Schreib und Lesezugriffe Prozess Scheduler, regelt die zeitliche Ausführung mehrerer Prozesse in Betriebssystemen Festplatten Scheduler, regelt die Abfolge von Lese… …   Deutsch Wikipedia

  • Scheduler (Informatik) — Ein Prozess Scheduler (Scheduler = Steuerprogramm) ist eine Arbitrationslogik, der die zeitliche Ausführung mehrerer Prozesse in Betriebssystemen regelt. Prozess Scheduler kann man grob in unterbrechende (preemptive) und nicht unterbrechende (non …   Deutsch Wikipedia

  • Prozess (Computer) — Der Prozess in der Informatik ist ein ablaufendes Programm. Zum Ablauf ist das Speicherabbild des ausführbaren Programms (Code), Speicher für die Daten, weitere vom Betriebssystem bereitgestellte Betriebsmittel (Ressourcen) und ein Prozessor… …   Deutsch Wikipedia

  • O(1)-Scheduler — Linux (Kernel) Entwickler Linus Torvalds u. v. m. Sprache(n) …   Deutsch Wikipedia

  • Completely Fair Scheduler — Der Completely Fair Scheduler (kurz CFS) ist ein Prozess Scheduler in der Informatik. Solche Scheduler werden verwendet, um die Priorität von Programmabläufen auf Kernelebene von Betriebssystemen zu verwalten. CFS wurde von Ingo Molnár entwickelt …   Deutsch Wikipedia

  • Brain Fuck Scheduler — Entwickler Con Kolivas Aktuelle Version 363 (6. Januar 2011) Betriebssystem Linux Programmier­sprache C …   Deutsch Wikipedia

  • Computer Prozess — Der Prozess in der Informatik ist ein ablaufendes Programm. Zum Ablauf ist das Speicherabbild des ausführbaren Programms (Code), Speicher für die Daten, weitere vom Betriebssystem bereitgestellte Betriebsmittel (Ressourcen) und ein Prozessor… …   Deutsch Wikipedia

  • Real-Time-Scheduler — Ein Real Time Scheduler ist der Prozess Scheduler eines Realzeit Betriebssystem. Siehe Beispiele für Echtzeitbetriebssysteme für eine Liste der bekannten Realzeit Betriebssysteme. Real Time Scheduler, kurz RTS genannt, ist auch der Name einer… …   Deutsch Wikipedia

  • Open Source Job Scheduler — Dieser Artikel wurde aufgrund von inhaltlichen Mängeln auf der Qualitätssicherungsseite der Redaktion Informatik eingetragen. Dies geschieht, um die Qualität der Artikel aus dem Themengebiet Informatik auf ein akzeptables Niveau zu bringen. Hilf… …   Deutsch Wikipedia

  • Prozessverwaltung — Ein Prozess Scheduler (Scheduler = Steuerprogramm) ist eine Arbitrationslogik, der die zeitliche Ausführung mehrerer Prozesse in Betriebssystemen regelt. Prozess Scheduler kann man grob in unterbrechende (preemptive) und nicht unterbrechende (non …   Deutsch Wikipedia

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”