www.wikidata.de-de.nina.az

Prozess Scheduler Ein Scheduler Steuerprogramm vom englischen schedule für Zeitplan ist eine Arbitrationslogik die die z

Prozess-Scheduler

Ein Prozess-Scheduler (Scheduler = Steuerprogramm; vom englischen schedule für „Zeitplan“) ist eine Arbitrationslogik, die die zeitliche Ausführung mehrerer Prozesse in Betriebssystemen und in der Anwendungsvirtualisierung regelt. Prozess-Scheduler kann man grob in unterbrechende (präemptiv) 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. 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.

Ein Echtzeitsystem muss garantieren, dass ein Prozess eine Aufgabe innerhalb einer vorgegebenen Zeitspanne abgearbeitet haben muss. Bei harten Echtzeitanforderungen wird das in 100 % aller Fälle garantiert, während bei weichen Anforderungen das Zeitlimit in einem kleinen Prozentsatz der Fälle überschritten werden darf.

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

Ziele Bearbeiten

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

Allgemein Bearbeiten

  • 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 Massenspeicher, Netzwerk-Schnittstelle u. a. ausgelastet sind.
  • Einhaltung der Systemregeln

Stapelverarbeitungssysteme Bearbeiten

  • 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 Zeitspanne 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) Bearbeiten

  • 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 Bearbeiten

  • Deadlines einhalten
  • Vorhersagbarkeit: Wichtig für Multimedia-Anwendungen (da sonst z. B. Verschlechterung der Tonqualität droht) oder sicherheitskritische Anwendungen wie zum Beispiel Steuergeräte für Airbags, Tempomat bei Kraftfahrzeugen, oder Autopiloten bei Flugzeugen.

Strategien Bearbeiten

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 In – First Out (FIFO), First-Come First-Served (FCFS): 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-Next (SJN), Shortest Job First (SJF), Shortest Processing Time (SPT): ein weiteres Verfahren, das nicht für Mehrbenutzersysteme geeignet ist. Es 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. Können Prozesse unterbrochen werden, so dass ein Prozesswechsel durchgeführt wird, wenn ein neu ankommender Prozess eine kürzere Ausführungszeit aufweist als der aktuell laufende Prozess, so spricht man von Shortest-Remaining-Time (SRT) oder Shortest-Remaining-Processing-Time (SRPT):
  • Random Job Next (RJN): Hierbei wird einem Prozess eine bestimmte Anzahl an Lotterie-Tickets zugewiesen. Der Scheduler lost ein Ticket, wonach der Prozess, welcher die Auslosung gewonnen hat, die vorgesehene Bearbeitungszeit übergeben bekommt. Der Overhead hiervon liegt bei O(2n) von der Implementation, welche nach David Petrou als Pseudocode repräsentiert wird.
  • Earliest Due Date (EDD): 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. Wenn Prozesse unterbrochen werden können spricht man von einer Terminabhängigen Ablaufplanung, Planen nach Fristen oder Earliest Deadline First (EDF). Diese Strategie kommt hauptsächlich in Echtzeitsystemen vor, da es damit möglich ist, eine definierte Antwortzeit für bestimmte Prozesse zu garantieren.
  • Prioritätsscheduling: Bei dieser Strategie wird jedem Prozess eine Priorität zugeordnet. Die Abarbeitung erfolgt dann in der Reihenfolge der Prioritäten.
    • Rate Monotonic Scheduling (RMS): Die Priorität wird aus der Periodenlänge berechnet (Prozesse mit kürzeren Perioden haben höhere Priorität).
    • Deadline Monotonic Scheduling (DMS): Die Priorität wird aus der relativen Deadline berechnet (Prozesse mit kürzeren relativen Deadlines haben höhere Priorität).
    • Man kann auch mehreren Prozessen die gleiche Priorität geben, sie werden dann in Eingangsreihenfolge ausgeführt, oder mit einem untergeordneten Zeitscheibenverfahren innerhalb der gleichen Priorität abgewechselt (zum Beispiel Multilevel Feedback Queue Scheduling oder Shortest-Elapsed-Time (SET) )
    • Die Prioritäten können auch dynamisch sein, 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.
  • 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. Sind die einzelnen Zeitspannen unterschiedlich groß, so spricht man von Weighted Round Robin (WRR)

Scheduling-Verfahren Bearbeiten

Literatur Bearbeiten

  • Tanenbaum, Andrew S.: Moderne Betriebssysteme ISBN 3-8273-7019-1
  • A. Silberschatz, P. B. Galvin, G. Gagne: Operating System Concepts, 7th edition, John Wiley & Sons Inc. 2000, ISBN 0-471-69466-5

Einzelnachweise Bearbeiten

  1. Otto Spaniol: Systemprogrammierung : Skript zur Vorlesung an der RWTH Aachen. 1996, ISBN 3-86073-470-9
  2. David Petrou, John W. Milford, Garth A. Gibson: Implementing Lottery Scheduling: Matching the Specializations in Traditional Schedulers. (PDF) In: USENIX. USENIX Annual Technical Conference, 6. Juni 1999, abgerufen am 8. November 2021 (englisch).
  3. Credit Scheduler im Xen-Wiki
  4. Credit2 Scheduler im Xen-Wiki
wikipedia, wiki, deutsches, deutschland, buch, bücher, bibliothek artikel lesen, herunterladen kostenlos kostenloser herunterladen, MP3, Video, MP4, 3GP, JPG, JPEG, GIF, PNG, Bild, Musik, Lied, Film, Buch, Spiel, Spiele
Veröffentlichungsdatum:
Ein Prozess Scheduler Scheduler Steuerprogramm vom englischen schedule fur Zeitplan ist eine Arbitrationslogik die die zeitliche Ausfuhrung mehrerer Prozesse in Betriebssystemen und in der Anwendungsvirtualisierung regelt Prozess Scheduler kann man grob in unterbrechende praemptiv 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 fur eine bestimmte Zeitspanne zu und entziehen dem Prozess diese daraufhin wieder Weiter ist eine Unterscheidung in work conserving und non work conserving Strategien moglich Eine Scheduler Strategie arbeitet work conserving wenn das Umschalten zwischen Prozessen nur eine vernachlassigbar geringe Zeit in Anspruch nimmt 1 Man kann verschiedene Systeme unterscheiden in welchen jeweils verschiedene Anforderungen an den Scheduler gestellt werden Stapelverarbeitungssysteme interaktive Systeme EchtzeitsystemeIn Stapelverarbeitungssystemen sieht der Scheduler denkbar einfach aus Ankommende Auftrage werden in eine Warteschlange eingereiht und jedes Mal wenn ein Job abgearbeitet ist kommt der nachste 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 tatigt sollte der Text sofort erscheinen Ein Echtzeitsystem muss garantieren dass ein Prozess eine Aufgabe innerhalb einer vorgegebenen Zeitspanne abgearbeitet haben muss Bei harten Echtzeitanforderungen wird das in 100 aller Falle garantiert wahrend bei weichen Anforderungen das Zeitlimit in einem kleinen Prozentsatz der Falle uberschritten werden darf Typische Desktop PCs sind interaktive Systeme auf denen gelegentlich auch Prozesse als so genannte Hintergrundprozesse mit niedrigerer Prioritat ablaufen konnen Inhaltsverzeichnis 1 Ziele 1 1 Allgemein 1 2 Stapelverarbeitungssysteme 1 3 Interaktive Systeme Dialogsysteme 1 4 Echtzeitsysteme 2 Strategien 3 Scheduling Verfahren 4 Literatur 5 EinzelnachweiseZiele BearbeitenDie Zuteilung der CPU an die Prozesse sollte bestmoglich erfolgen wobei abhangig vom ausfuhrenden System unterschiedliche Ziele verfolgt werden konnen Allgemein Bearbeiten Fairness Kein Prozess sollte unverhaltnismassig lange warten mussen wahrend ein anderer bevorzugt wird Balance Die Prozesse sollten der CPU auf eine Weise zugeteilt werden dass auch andere Ressourcen wie Massenspeicher Netzwerk Schnittstelle u a ausgelastet sind Einhaltung der SystemregelnStapelverarbeitungssysteme Bearbeiten 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 Zeitspanne sollte maximiert werden Dies ergibt eine ahnliche Strategie wie die Auslastung betrachtet aber mehr das tatsachliche Ergebnis kurze Turnaroundzeit Durchlaufzeit Die Zeit die von der Ankunft eines Prozesses bis zu seiner vollstandigen Beendigung vergeht sollte minimiert werden Interaktive Systeme Dialogsysteme Bearbeiten 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 konnen Proportionalitat Die Antwortzeiten verschiedener Prozesse sollten den Erwartungen des Benutzers entsprechen Werden Prozesse wie z B das Schliessen einer Anwendung vom Benutzer als simpel betrachtet sollten diese auch schnell ausgefuhrt werden Echtzeitsysteme Bearbeiten Deadlines einhalten Vorhersagbarkeit Wichtig fur Multimedia Anwendungen da sonst z B Verschlechterung der Tonqualitat droht oder sicherheitskritische Anwendungen wie zum Beispiel Steuergerate fur Airbags Tempomat bei Kraftfahrzeugen oder Autopiloten bei Flugzeugen Strategien BearbeitenDas grosste Problem des Schedulers ist die Tatsache dass die benotigten Betriebsmittel fur die einzelnen Prozesse nicht im Vorfeld bekannt sind Es lasst sich also im Allgemeinen keine optimale Planung erstellen sondern der Scheduler muss dynamisch auf geanderte Anforderungen reagieren Dabei konnen abhangig vom Scheduler verschiedene Zuteilungsstrategien zum Einsatz kommen Unter anderem First In First Out FIFO First Come First Served FCFS 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 Ausfuhrung beendet ist Diese Strategie erzielt eine gute Auslastung bezuglich der CPU allerdings nicht bezuglich Ressourcen die langere Zeit fur eine Anforderung benotigen konnen wie z B Ein Ausgabe oder Massenspeicher Fur Mehrbenutzersysteme ist die Strategie daruber hinaus wenig geeignet da einzelne Benutzer so ggf fur langere Zeit namlich bei aufwendigen Prozessen anderer Benutzer ausgeschlossen werden Shortest Job Next SJN Shortest Job First SJF Shortest Processing Time SPT ein weiteres Verfahren das nicht fur Mehrbenutzersysteme geeignet ist Es lasst sich in Fallen einsetzen in denen die benotigte Rechenzeit fur einzelne Aufgaben aus Erfahrungswerten gut vorhergesagt werden kann Ein Nachteil ist dass grosse Prozesse u U niemals die CPU zugeteilt bekommen wenn sich immer kurzere Jobs vordrangeln Konnen Prozesse unterbrochen werden so dass ein Prozesswechsel durchgefuhrt wird wenn ein neu ankommender Prozess eine kurzere Ausfuhrungszeit aufweist als der aktuell laufende Prozess so spricht man von Shortest Remaining Time SRT oder Shortest Remaining Processing Time SRPT Random Job Next RJN Hierbei wird einem Prozess eine bestimmte Anzahl an Lotterie Tickets zugewiesen Der Scheduler lost ein Ticket wonach der Prozess welcher die Auslosung gewonnen hat die vorgesehene Bearbeitungszeit ubergeben bekommt Der Overhead hiervon liegt bei O 2n von der Implementation welche nach David Petrou als Pseudocode reprasentiert wird 2 Earliest Due Date EDD Bei dieser Strategie werden diejenigen Prozesse zuerst ausgefuhrt welche die geringste Deadline haben Voraussetzung dafur sind statische Deadlines und gleichzeitiges Eintreffen voneinander unabhangiger Tasks Dieses nichtunterbrechende Verfahren ist ideal um die maximale Verspatung zu minimieren Wenn Prozesse unterbrochen werden konnen spricht man von einer Terminabhangigen Ablaufplanung Planen nach Fristen oder Earliest Deadline First EDF Diese Strategie kommt hauptsachlich in Echtzeitsystemen vor da es damit moglich ist eine definierte Antwortzeit fur bestimmte Prozesse zu garantieren Prioritatsscheduling Bei dieser Strategie wird jedem Prozess eine Prioritat zugeordnet Die Abarbeitung erfolgt dann in der Reihenfolge der Prioritaten Rate Monotonic Scheduling RMS Die Prioritat wird aus der Periodenlange berechnet Prozesse mit kurzeren Perioden haben hohere Prioritat Deadline Monotonic Scheduling DMS Die Prioritat wird aus der relativen Deadline berechnet Prozesse mit kurzeren relativen Deadlines haben hohere Prioritat Man kann auch mehreren Prozessen die gleiche Prioritat geben sie werden dann in Eingangsreihenfolge ausgefuhrt oder mit einem untergeordneten Zeitscheibenverfahren innerhalb der gleichen Prioritat abgewechselt zum Beispiel Multilevel Feedback Queue Scheduling oder Shortest Elapsed Time SET Die Prioritaten konnen auch dynamisch sein wobei sich die Prioritat eines Prozesses mit der Zeit erhoht damit auch niedrig priorisierte Prozesse irgendwann bearbeitet werden und nicht standig von hoher priorisierten Prozessen verdrangt werden Round Robin Zeitscheibenverfahren Einem Prozess wird die CPU fur eine bestimmte kurze Zeitspanne zugeteilt Danach wird der Prozess wieder hinten in die Warteschlange eingereiht Sind die einzelnen Zeitspannen unterschiedlich gross so spricht man von Weighted Round Robin WRR Scheduling Verfahren BearbeitenCompletely Fair Scheduler CFS neuester Scheduler von Linux seit 2 6 23 Fair Share Scheduling Brain Fuck Scheduler Highest Response Ratio Next HRRN Least Laxity First Planen nach Spielraum Lotterie Scheduling Three Level Scheduling Credit Scheduler 3 Credit2 Scheduler 4 von XenLiteratur BearbeitenTanenbaum Andrew S Moderne Betriebssysteme ISBN 3 8273 7019 1 A Silberschatz P B Galvin G Gagne Operating System Concepts 7th edition John Wiley amp Sons Inc 2000 ISBN 0 471 69466 5Einzelnachweise Bearbeiten Otto Spaniol Systemprogrammierung Skript zur Vorlesung an der RWTH Aachen 1996 ISBN 3 86073 470 9 David Petrou John W Milford Garth A Gibson Implementing Lottery Scheduling Matching the Specializations in Traditional Schedulers PDF In USENIX USENIX Annual Technical Conference 6 Juni 1999 abgerufen am 8 November 2021 englisch Credit Scheduler im Xen Wiki Credit2 Scheduler im Xen Wiki Abgerufen von https de wikipedia org w index php title Prozess Scheduler amp oldid 231446587