Notice: Undefined index: string in /var/www/stefan/howtux.de/htdocs/article.php on line 49

Notice: Undefined index: settings in /var/www/stefan/howtux.de/htdocs/article.php on line 61
Home / Prozesse und IPC / Scheduling

Scheduling

Kategorie: Prozesse und IPCErstellt: 02.10.2007 - 23:58 Geändert: 23.10.2007 - 22:52
Autor: Stefan Abu Salah
0Man spricht von einem Multitastking-System, wenn mehrere Prozesse quasi gleichzeitig auf einem System laufen können. In der Realität kann auf einem Single-CPU-System jedoch immer nur ein Prozess die CPU für sich beanspruchen. Andere Prozesse müssen solange auf die Zuteilung der CPU warten, bis sie an der Reihe sind. Genau diese Ziteilungsentscheidung übernimmt in UNIX- und Linux-Systemen der Scheduler. Die Grundlage, auf der der Scheduler entscheidet welcher Prozess als nächster die CPU nutzen darf und wielange dieser dies darf, bildet ein komplexer Zusammenhang zwischen Prozesszuständen, diverse Eigenschaften des Systems und eine Menge Statistik. Der Scheduler kennt unter anderem die in der folgenden Grafik veranschaulichten wichtigen Prozesszustände:
image

Zustände:
Bereit - Prozess wartet auf das Zuteilen der CPU
Blockiert - Prozess kann derzeit nicht ausgeführt werden, da er noch euf ein bestimmtes Ereignis wartet (z.B. Benutzereingabe)
Rechnend - Der Prozess wird derzeit von der CPU bearbeitet. In einem Single-CPU-System kann immer nur ein Prozess bearbeitet werden.
Zombie - Bereits beendeter Prozess, dessen Speicherbereich jedoch noch nicht freigegeben wurde. So kann zu einem späteren Zeitpunkt der Vaterprozess die Rückgaben auswerten.


Prozesse bevorzugen


Es ist möglich einen Prozess mit einer höheren Priorität zu versorgen. Dies soll dazu führen, dass dieser Prozess eher Zugriff auf die CPU bekommt als andere Prozesse. Der Scheduler muss diesen Prioritätswert mit berücksichtigen. Auch die bereits vom Prozess genutzte CPU-Zeit muss in die Entscheidung des Schedulers einfließen.
Im Scheduler des Linux Kernels werden diese Eigenschaften recht einfach umgesetzt. Der Kernel führt zwei Prozesslisten. Eine enthält alle Prozesse welche bereits bearbeitet wurden, die andere enthält die Prozesse welche noch nicht bearbeitet wurden. Hat ein Prozess seine Zeitscheibe (timeslice), welche maximal 1/1000 Sekunde dauert, hinter sich gebracht, oder ist er mit der Bearbeitung fertig, so wird er in die Liste der bearbeiteten Prozesse verschoben. Dies wird solange wiederholt, bis die Liste abgearbeitet ist. Jetzt werden die beiden Listen einfach getauscht und die Bearbeitung beginnt von vorne. Folgende Grafik veranschaulicht diesen Mechanismus:
image
Dieses Vorgehen würde zu einer absoluten Gleichverteilung der CPU-Zeiten auf alle Prozesse führen. Da in modernen Systemen jedoch unterschiedliche Anforderungen an Prozesse gestellt werden, muss es eine intelligentere Möglichkeit geben die Reihenfolge der Bearbeitung zu bestimmen. So werden beispielsweise interaktive gegenüber rechenintensiven Prozessen bevorzugt.
Linux kennt drei verschiedene Scheduling-Policies und untscheidet statische und dynamische Prioritäten. Beim Start jedes Programms wird diesem eine statische Priorität zugeordnet.

First Come First Serve (FCFS)


Alle Prozesse werden genau in der Reiehenfolge verarbeitet in der sie erzeugt wurden. Die Abarbeitung erfolgt streng Sequenziell. Ein Prozess wird immer vollständig ausgeführt, es sei denn er kommt in den Zustand "blockiert". Dieses Verfahren wird auch häufig "First In – First Out" (FIFO) genannt.
image

Round Robin Scheduling


Die Prozesse werden in einer Warteschlange verwaltet. Der vorderste Prozess erhält einen Zeitschlitz lang Zugang zu den Ressourcen, dann reiht er sich am Ende der Warteschlange ein und alle Prozesse rücken eine Position vor. Der nächste Prozess wird nach dem FIFO-Prinzip ausgewählt. Der Prozess kann die Ressourcen auch freiwillig früher zurückgeben. Auch wenn ein Prozess vor Ende seines Zeitschlitzes abgeschlossen wird, werden die Ressourcen sofort neu zugeteilt.
Round-Robin behandelt alle Prozesse gleich, so dass einerseits kein Prozess unfair behandelt wird oder gar verhungert, es aber andererseits auch nicht möglich ist, Prozesse mit höherer Dringlichkeit bevorzugt abzuarbeiten. Der Durchsatz dieses Scheduling-Verfahrens ist im Allgemeinen weder besonders niedrig noch besonders hoch; Die Verwendung von Zeitschlitzen fester Länge machen Round-Robin unflexibel und führen dazu, dass Ressourcen häufig ungenutzt bleiben.
image

Prioritätengesteuertes Scheduling


Jeder Prozess erhält eine Priorität. Der Prozess mit der höchsten Priorität erhält sofort Zugriff auf die CPU, solange er sich im Zustand "bereit" befindet. Es ist möglich das Prozesse "verhungern" (Prozesse mit niedriger Priorität erhalten nie Zugriff auf die CPU). Für Realzeitsysteme ist dieses Verfahren geeignet (evtl. in Verbindung mit anderen Verfahren).
image

POSIX 1003.1b


Es existieren mehrere Prioritätsebenen. Jede Prioritätsebene enthält eine Prozessliste. Jede Liste bedient die von ihr verwalteten Prozesse entweder mit dem FCFS oder mit dem Round Robin-Verfahren.
image

In Linux/UNIX-Systemen gilt: Je kleiner der Zahlenwert der Priorität (PRI), desto größer die Priorität des Prozesses im Scheduler.



Notice: Undefined variable: urli in /var/www/stefan/howtux.de/htdocs/classes.php on line 240
Bookmark auf del.icio.usBookmark auf Mister WongBookmark auf BlinklistBookmark auf GoogleBookmark auf LinkarenaBookmark auf YiggBookmark auf FolkdBookmark auf Yahoo
Home / Prozesse und IPC / Scheduling
simplum