IT-Academy Logo
Sign Up Login Help
Home - Betriebssysteme - Allgemein - Prozess-Scheduling



Prozess-Scheduling

Das Umschalten zwischen Prozessen kann nach verschiedenen Verfahren geschehen. Dieser Artikel fasst die Verfahren aus Andrew Tannenbaums Buch "moderne Betriebssysteme" kurz und bündig zusammen.


Autor: Patrick Bucher (paedubucher)
Datum: 29-10-2006, 12:23:15
Referenzen: Andrew Tannenbaum; moderne Betriebssysteme
Schwierigkeit: Fortgeschrittene
Ansichten: 6803x
Rating: Bisher keine Bewertung.

Hinweis:

Für den hier dargestellte Inhalt ist nicht der Betreiber der Plattform, sondern der jeweilige Autor verantwortlich.
Falls Sie Missbrauch vermuten, bitten wir Sie, uns unter missbrauch@it-academy.cc zu kontaktieren.

[Druckansicht] [Als E-Mail senden] [Kommentar verfassen]



Scheduling-Verfahren

Ein Betriebssystem zeichnet sich dadurch aus, dass es verschiedene Prozesse ausführen kann. Welcher Prozess wann ausgeführt wird, ist Aufgabe des sog. Schedulers. Der Scheduler hat die Aufgabe, anhand einer festgelegten Strategie zu entscheiden, welcher Prozess wann ausgeführt wird. Früher, als Systeme noch im Stapelbetrieb liefen, war das Scheduling denkbar einfach; wenn ein Prozess zu Ende ist, dann führe den nächsten aus. Heute sind praktisch nur noch Multitasking-Systeme im Einsatz, also Systeme, die mehreren Aufgaben (scheinbar) gleichzeitig nachgehen können. Dies macht das Scheduling um einiges komplizierter.

Kriterien

Ein Scheduling-Verfahren kann unter Berücksichtigung der folgenden Kriterien bewertet werden:

  • Fairness: Prozesse sollen einen gerechten Teil der Prozessorzeit erhalten
  • Effizienz: Der Prozessor soll nach Möglichkeit immer vollständig ausgelastet sein
  • Antwortzeit: Interaktive Prozesse sollen eine möglichst kurze Antwortzeit haben
  • Verweilzeit: Die Wartezeit von Stapelaufträgen soll minimiert werden
  • Durchsatz: Die Anzahl bearbeiteter Aufträge in einem Zeitintervall soll maximiert werden

Einige dieser genannten Kriterien sind offensichtlich widersprüchlich. So soll z.B. die Antwortzeit von ineraktiven Prozessen und die Verweilzeit von Stapelaufträgen möglichst kurz gehalten werden. Hier hat der Scheduler die Aufgabe, einen optimalen Kompromiss zu finden. Wird eine Klasse von Prozessen bevorzugt, so wird automatisch eine andere benachteiligt. Dies liegt in der Natur der Sache, da immer gleich viel Ressourcen zur Verfügung stehen.

Prozess-Umschaltung

Computer besitzen eine elektronische Stoppuhr. Diese löst in regelmässigen Abständen ein Unterbrechungssignal aus. Das Intervall kann vom Betriebssystem bestimmt werden. Bei jedem Unterbrechungssignal erhält der Scheduler den Fokus und kann entscheiden, ob er den laufenden Prozess unterbrechen will oder ihn noch ein wenig laufen lassen soll. Kann ein Scheduler einen laufenden Prozess unterbrechen und ihn zu einem späteren Zeitpunkt wieder aufnehmen, so ist die Rede von preemptivem Scheduling.

Wenn ein Scheduler nicht über den genannten Mechanismus verfügt, so ist die Rede von nicht-preemptivem Scheduling. Jeder Prozess wird also komplett abgearbeitet, bis der nächste an die Reihe kommt. Dies ist bei älteren Stapelsystemen der Fall.

Round-Robin-Verfahren

Des Round-Robin-Verfahren ist das älteste Scheduling-Verfahren und gilt gleichzeitig als das einfachste und fairste. Jeder Prozess erhält ein gewisses Zeitintervall, das Quantum, für seine Ausführung. Ist dieses Quantum abgelaufen, wird auf den nächsten Prozess gewechselt. Der Prozesswechsel kann auch bereits vor dem Ablauf des Quantums stattfinden, so kann ein blockierender Prozess vorzeitig unterbrochen werden.

Alle Prozesse stellen sich in eine Warteschlange (Queue) ein (A-B-C-D). Nun wird Prozess A ausgeführt. Ist sein Quantum abgelaufen, kommt Prozess B an die Reihe. Prozess A stellt sich nun wieder hinten an (B-C-D-A).

Jeder Prozesswechsel erfordert etwas Prozessorzeit, so muss z.B. bei der Prozessumschaltung immer auf einen anderen Speicherbereich gewechselt werden. Angenommen, das Quantum beträgt 50 Millisekunden und die Umschaltung nimmt 10 Millisekunden in Anspruch, so wird die Prozessorzeit zu 20% für die Prozessumschaltung verbraucht. Um dieses Verhältnis zu verbessern, könnte man das Quantum auf eine Sekunde erhöhen. Der Prozessor verwendet nun 99% für die Prozessausführung und nur noch 1% für die Umschaltung. Dies mag im ersten Moment sehr gut klingen. Vergessen wir aber nicht, was dies für Auswirkungen auf Interaktive Systeme hätte. Wenn ein Benutzer z.B. auf dem Terminal drei mal die Return-Taste betätigen würde, so vergingen geschlagene drei Sekunden, bis das letzte Return angekommen wäre. Eine unzumutbare Wartezeit. Bei der Bestimmung der Länge des Quantums gilt es also, einen optimalen Kompromiss zu finden.

Prioritäts-Scheduling

Das Round-Robin-Verfahren betrachtet alle Prozesse als gleich wichtig. Oftmals empfindet ein Benutzer jedoch einen Prozess als wichtiger als den anderen. Um dem gerecht zu werden, wurde das Prioritäts-Scheduling entwickelt.

Jeder Prozess erhält dabei eine Priorität. Der ausführbare Prozess mit der höchsten Priorität wird als erster ausgeführt. Damit priorisierte Prozesse nicht einfach die gesamte Prozessorzeit in Beschlag nehmen können, wird die Priorität eines Prozesses nach jedem Durchlauf verringert. So werden bei der Ausführung trotzdem alle Prozesse berücksichtigt.

Diese Prioritäten können statisch oder dynamisch zugewiesen werden. Bei der statischen Zuweisung wird einfach ein fixer Wert vorgegeben. Die dynamische Priorisierung betrachtet, wie stark ein Prozess sein Quantum ausnützt. Ein Prozess, der sein Quantum jeweils vollständig ausnutzt, erhält eine tiefere Priorität. Prozesse, die z.B. viel I/O-Operationen ausführen, benötigen anteilsmässig weniger von ihrem Quantum. Dafür sollen sie aber auch schneller reagieren können (interaktive Verarbeitung). Letztere werden also eher ausgeführt, damit der Anwender "flüssig" arbeiten kann.

Prozesse können auch in Prioritätsgruppen eingeteilt werden. Innerhalb dieser Klassen kommt häufig das Round-Robin-Verfahren zum Einsatz. Auch hier müssen die Prioritäten angepasst werden. Ein Prozess wird so nach jeder Ausführung in eine tiefere Prioritätsklasse verschoben.

Mehrere Schlangen

Ein Prozesswechsel benötigt bekanntermassen einen nicht unwesentlich grossen Teil der Prozessorzeit. Wie wir auch gesehen haben, gibt es Prozesse die ihre Quanten nicht ausnützen, andere Prozesse lasten ihre Quanten um ein Mehrfaches aus. Um in diesem Falle ein unnötig häufiges Umschalten zwischen Prozessen zu verhindern, kann man den zeitlich anspruchsvolleren Prozessen mehrere Quanten auf einmal zuweisen.

Die Prozesse werden in verschiedene Prioritätsklassen gruppiert. Die Gruppe mit der höchsten Priorität erhält kleinere Quanten, dafür werden sie auch häufiger ausgeführt. Nach jeder Ausführung wandert der Prozess eine Stufe nach unten. Je weiter unten sich ein Prozess befindet, desto seltener wird er ausgeführt und desto mehr Quanten erhält er. Auf diese Weise kann die Anzahl der Kontextwechsel reduziert werden, es wird insgesamt Prozessorzeit gespart. So können interaktive Prozesse oft und kurz ausgeführt werden, länger dauernde Prozessen werden selten, dafür aber auch für eine längere Zeit ausgeführt.

Shortest-Job-First

Bisher stand der Fokus immer auf ineraktiven Systemen. Shortest-Job-First ist jedoch speziell für Stapelaufträge geeignet, deren Ausführungszeit bereits am Anfang bekannt ist.

Gehen wir von den Prozessen A, B, C und D aus. A wird 10 Minuten für die Ausführung beanspruchen. Die Prozesse B, C und D benötigen nur jeweils 2 Minuten. Würden die Prozesse in dieser Reihenfolge ausgeführt, betrüge die Verweildauer für Prozess A 10 Minuten, für B 12 Minuten, für C 14 Minuten und für D 16 Minuten. Dies gibt eine durchschnittliche Verweildauer von 13 Minuten. Führt man jedoch die kurzen Prozesse zuerst aus und stellt A ganz nach hinten, so würde die Verweildauer für B 2 Minuten, für C 4 Minuten, für D 6 Minuten und für A 16 Minuten betragen. Dies führt zu einer durchschnittlichen Verweildauer von 7 Minuten. So kann man in einer kurzen Zeit viele Prozesse abarbeiten, einzig ein langwieriger Prozess würde etwas länger auf sich warten lassen.

Zweistufiges Scheduling

Manchmal ist es nicht möglich, alle Prozesse im Arbeitsspeicher zu halten. So müssen Prozesse auf dem Hintergrundspeicher (Festplatte) abgelegt werden. Das holen eines Prozesses von der Festplatte dauert wesentlich länger als das wechseln zwischen zwei Prozessen innerhalb des Arbeitsspeichers. Hier werden also zwei Scheduler benötigt, welche sich die Arbeit teilen.

Der übergeordnete Scheduler entscheidet darüber, wann Prozesse vom Arbeitsspeicher auf die Festplatte und von der Festplatte in den Arbeitsspeicher kommen. Der untergeordnete Scheduler kann nach einem beliebigen, bereits vorgestellten, Verfahren arbeiten und wechselt nur die Prozesse innerhalb des Arbeitsspeichers aus.

Referenzen

  • Moderne Betriebssysteme
    • Autor: Andrew S. Tannenbaum
    • Verlag: Pearson Studium
    • ISBN-Nr: 3-8273-7019-1


[back to top]



Userdaten
User nicht eingeloggt

Gesamtranking
Werbung
Datenbankstand
Autoren:04508
Artikel:00815
Glossar:04116
News:13565
Userbeiträge:16552
Queueeinträge:06246
News Umfrage
Ihre Anforderungen an ein Online-Zeiterfassungs-Produkt?
Mobile Nutzung möglich (Ipone, Android)
Externe API Schnittstelle/Plugins dritter
Zeiterfassung meiner Mitarbeiter
Exportieren in CSV/XLS
Siehe Kommentar



[Results] | [Archiv] Votes: 1154
Comments: 0