Prozessor Scheduling in Unix

Post Reply
Message
Author
Felix2000
Posts: 35
Joined: 06. Oct 2008 14:31

Prozessor Scheduling in Unix

#1 Post by Felix2000 »

Hallo zusammen !

Ich habe hier eine theoretische Frage, vielleicht kann mal jemand auf die Antworten schauen. Hoffe ich tappe nicht ganz im Dunkeln...

Das Prozessor Scheduling für das Betriebssystem Unix basiert auf einer Kombination aus dynamischen und festen Prioritäten ("Multi Level Feedback Queuing"). Angenommen die CPU Auslastung eines Unix Systems liegt nahezu bei 100% und ich starte eine Anwendung, die Eingaben von der Tastatur entgegennimmt, verarbeitet und ausgibt (z.b. das cat Kommando in der Bash Shell).

1. Begründen Sie, was man unter festen und dynamischen Prioritäten versteht.

2. Begründen Sie, weshalb die Antwortzeiten (d.h. Zeitdifferenz zwischen Abschluss der Eingabe bis zu der Ausgabe) sich gegenüber einem gering ausgelasteten System nicht wesentlich verlängert.

zu 1)

Unter dynamischen Prioritäten versteht man sich ständig verändernde Prioritäten, z.B. innerhalb von Prioritätenklassen. Durch das Prinzip der Fairness wird Prozessen, die gerade bearbeitet werden, durch den Timertick des Unixsystems, die Priorität nach und nach entzogen bzw. gesenkt, bis ein anderer Prozess mit einer dann höheren Priorität in die höhere Prozessklasse wechselt und bearbeitet wird. Der andere Prozess wechselt in den Zustand verdrängt.

Was man unter festen Prioritäten versteht weiß ich nicht...

zu 2)

Ich vermute, dass die Antwort bei 1) auch hier passen würde bzw. ein möglicher Grund sein könnte.

User avatar
Janka
Posts: 3585
Joined: 11. Feb 2006 19:10

Re: Prozessor Scheduling in Unix

#2 Post by Janka »

Felix2000 wrote:Hallo zusammen !
Unter dynamischen Prioritäten versteht man sich ständig verändernde Prioritäten, z.B. innerhalb von Prioritätenklassen. Durch das Prinzip der Fairness wird Prozessen, die gerade bearbeitet werden, durch den Timertick des Unixsystems, die Priorität nach und nach entzogen bzw. gesenkt, bis ein anderer Prozess mit einer dann höheren Priorität in die höhere Prozessklasse wechselt und bearbeitet wird. Der andere Prozess wechselt in den Zustand verdrängt.
Es gibt (eigentlich schon: gab, denn der aktuelle CFS funktioniert anders) bei Linux traditionell 140 Runqueues, entsprechend den 40 Nice-Leveln (+20 bis -20) und den 99 statischen Prioritäten. Die statische Priorität in den Nice-Leveln ist durchgehend Null, ist von POSIX so definiert.
Die RQs 41..140 entsprechen den statischen Prioritäten 1..99. Dies sind die Echtzeitprozesse des Systems. Normalerweise gibt es bei Linux so gut wie keine Prozesse mit statischer Priorität. Bei anderen Unix-Systemen, z.B. QNX gibt es hingegen keine Prozesse mit statischer Priorität 0.

Das Scheduling funktioniert(e) so: Es wird nachgeschaut, ob ein Prozess in Runqueue 140 lauffähig ist. Wenn ja, wird er aufgeweckt und läuft, bis er entweder freiwillig mittels sched_yield() das Zepter abgibt oder bis seine Zeitscheibe abgelaufen ist (nur, wenn SCHED_RR für diesen Prozess eingestellt wurde). Danach kommt der nächste Prozess in Runqueue 140 dran. Sind alle Prozesse in RQ 140 einmal durch, geht es wieder los.
Danach kommen die Prozesse in Runqueue 139, mit denen im Prinzip genauso verfahren wird. Hier gibt es aber schon die erste Besonderheit: Wird zwischendurch ein Prozess in RQ140 lauffähig, wird der in RQ139 sofort unterbrochen und der Prozess in RQ140 aufgeweckt.
Für die RQs 41 bis 138 gibt dasselbe, wobei dann die Prozesse in den jeweils höheren RQs eine Unterbrechung auslösen können.

Für die RQs 1..40 gilt im Prinzip genau dasselbe, hier kommt aber noch hinzu, dass die Prozesse zwischen den RQs wandern können. Dies wird anhand der Restzeit in ihrer Zeitscheibe entschieden. Braucht ein Prozess die ganze Zeitscheibe auf, wird er runtergestuft, bis er schließlich in RQ 1 angelangt ist. Ist ein Prozess lange Zeit nicht gelaufen, beginnt er wieder in der Runqueue, die seinem Nice-Level entspricht.

Aber der letzte Teil ist für Linux im Prinzip schon wieder Geschichte, denn der CFS benutzt für die Prozesse mit dynamischer Priorität keine Runqueues mehr, sondern organisiert sie in einer Baumstruktur. Dadurch kann auch die Information, wieviel von der Zeitscheibe noch übrig war, in die Berechnung einfließen, welcher Prozess als nächster gestartet werden sollte.

zu 2)

Ich vermute, dass die Antwort bei 1) auch hier passen würde bzw. ein möglicher Grund sein könnte.
Die Anwendung, die auf Tastatureingaben wartet, dann kurz etwas tut und dann wieder wartet, muss dies kooperativ tun. Das bedeutet, sie darf keine Busy-Loops der Form
"Wiederhole, wenn keine Taste gedrückt." enthalten. Stattdessen muss sie dem Kernel mittels blockierendem Lesen oder select()/poll() mitteilen, auf welches Ereignis sie warten möchte. Dann wird sie auch nicht in eine niedrigere Runqueue runtergestuft und wird vom Kernel daher bevorzugt wiederaufgeweckt, sobald das angeforderte Ereignis eintritt.

Janka
Ich vertonne Spam immer in /dev/dsp statt /dev/null.
Ich mag die Schreie.

Post Reply