Open Source im professionellen Einsatz
Linux-Magazin 04/2013
© psdesign1, Fotolia

© psdesign1, Fotolia

Kernel- und Treiberprogrammierung mit dem Linux-Kernel – Folge 67

Kern-Technik

,

Scheduling ist eine zentrale Aufgabe des Linux-Kernels, der sich dabei um größte Fairness bemüht. Wer aber glaubt, dass damit alle das Gleiche bekommen, der irrt.

650

Das Task-Scheduling beeinflusst, wie sich ein Computer unter Last verhält. Nicht zufällig war diese CPU-Zuteilung häufig nicht nur Diskussions-, sondern sogar Streitthema unter den Linux-Entwicklern. Mit Kernel 2.6.23 vom Oktober 2007 hat der ungarische Entwickler Ingo Molnar den bis dahin in Linux verwendeten Scheduler O(1) durch den Completely Fair Scheduler (CFS) ersetzt, der seitdem – mit einigen Veränderungen versehen – seine Arbeit tut.

Fair Play

Anstelle der im O(1)-Scheduler implementierten Heuristik setzt CFS zur Erreichung von Interaktivität auf Fairness. Da er damit harte zeitliche Anforderungen nicht erfüllen kann, gibt es vorgeschaltet noch einen Echtzeit-Scheduler. Das Grundprinzip des CFS besteht darin, die zur Verfügung stehende Rechenzeit fair auf die lauffähigen Tasks aufzuteilen [1].

Dazu bekommt jede Task innerhalb einer definierten Scheduler-Periode je einmal Rechenzeit zugeteilt. Die Länge dieser Rechenzeit berechnet sich im ersten Ansatz durch Division der Scheduling-Periode durch die Anzahl der lauffähigen Tasks. Ist beispielsweise eine Scheduler-Periode 20 Millisekunden lang und es gibt vier lauffähige Tasks, darf jede Task 5 Millisekunden lang rechnen, bevor die nächste Task die CPU übernimmt.

Diese gleichförmige Aufteilung der Rechenzeit ist aber noch nicht fair. Daher berücksichtigt der Scheduler außerdem den Nice-Wert, die "Nettigkeit" von Tasks: Ist eine Task besonders nett, gibt sie sich mit weniger Rechenzeit zufrieden und besitzt einen positiven Nice-Wert. Bei einem negativen Nice-Wert dagegen erwartet sie mehr Rechenzeit.

Der alte O(1)-Scheduler realisierte den Nice-Wert über Prioritäten, die der Scheduler – um Interaktivität zu gewährleisten – während der Laufzeit modifizierte. So setzte er die Priorität eines Jobs, der ständig rechnete, herunter und die Priorität eines I/O-intensiven Jobs hoch.

CFS dagegen zieht die Nice-Werte heran, um die Laufzeit der Tasks anzupassen. Nette Tasks laufen kürzer, die übrigen entsprechend länger. Dazu rechnet der Scheduler den Nice-Wert in eine Weight genannte Gewichtung um. Das Gewicht für eine Task mit einem Nice-Wert von 0 beträgt per definitionem 1024 [2]. Die Gewichte für andere Nice-Werte berechnen sich nach der Formel:

w(nice)=1024/1.24^nice

Ein Nice-Wert von 1 resultiert somit in einem Gewicht von 820, ein Nice-Wert von -1 ergibt den Wert 1277. Durch die Art der Berechnung ergibt sich eine gewollte exponentielle Gewichtung der Nice-Werte in Abgrenzung zur früher üblichen linearen Zuteilung. Wird der Nice-Wert um 1 erhöht, reduziert sich die zugehörige Rechenzeit um etwa 10 Prozent: Die eigene Rechenzeit wird um 5 Prozent reduziert, die der übrigen Tasks um 5 Prozent erhöht.

Nette Tasks

Die Laufzeit einer Task innerhalb der Scheduler-Periode berechnet der Kernel anteilig zu ihrem Gewicht. Sie ergibt sich durch Multiplikation der Scheduling-Periode mit dem Quotienten aus dem Gewicht der Task und der Summe aller lauffähigen Gewichte (Tabelle 1). Ist beispielsweise eine Task mit einem Nice-Wert von 2 versehen, hat sie ein Gewicht von 655. Bei insgesamt vier Tasks, von denen eine einen Nice-Wert von -2, eine von 2 und die übrigen beiden 0 haben und die Scheduling-Periode 20 Millisekunden beträgt, ergibt sich für die erste Task eine Zeitscheibe von etwa 3 Millisekunden, für die beiden Tasks mit einem Nice-Wert von 0 je 5 Millisekunden und für die Task mit -2 eine Zeitscheibe von etwa 7 Millisekunden.

Tabelle 1

Berechnung der Zeitscheiben

Datenbank

»nice« -Wert

Gewicht »w« 1

Timeslice2  

T1

2

655

3 ms

T2

 

1024

5 ms

T3

 

1024

5 ms

T4

-2

1586

7 ms

Die Länge der Scheduler-Periode lässt sich über die virtuelle Datei »/proc/sys/kernel/sched_latency_ns« konfigurieren. Im selben Verzeichnis kann man in »sched_min_granularity_ns« die minimale Zeitscheibenlänge für eine Task festlegen. Die zugehörige Variable verhindert, dass die Zeitscheiben zu kurz werden, wenn beispielsweise viele Tasks im System lauffähig sind.

In diesem Fall erhöht der CFS selbstständig die Scheduling-Periode: Ist »sched_min_granularity_ns« zum Beispiel auf 2 Millisekunden eingestellt – wobei die ursprüngliche Scheduling-Periode wieder 20 Millisekunden beträgt – und sind 20 Tasks lauffähig, ergibt sich eine reale Scheduling-Periode von 20 mal 2, also von 40 Millisekunden.

Linux-Magazin kaufen

Einzelne Ausgabe
 
Abonnements
 
TABLET & SMARTPHONE APPS
Bald erhältlich
Get it on Google Play

Deutschland

Ähnliche Artikel

  • Kern-Technik

    Scheduling ist eine zentrale Aufgabe des Linux-Kernels, der sich dabei um größte Fairness bemüht. Wer aber glaubt, dass damit alle das Gleiche bekommen, der irrt.

  • Kern-Technik

    Nur ausgewiesene Echtzeitbetriebssysteme konnten bislang mit einem "Earliest Deadline First Task"-Scheduler protzen. Seit Kernel 3.14 steht das überlegene CPU-Zuteilungsverfahren auch Linux-Nutzern zur Verfügung. Gegenüber dem prioritätengesteuerten Verfahren hat es einige Vorteile.

  • Die Reihenfolge zählt

    Die Leistungsentfaltung von Betriebssystemen hängt entscheidend von der Performance und der Strategie des Schedulers ab, der die Prozessliste führt und lauffähigen Prozessen die CPU scheibchenweise zuteilt. Der Scheduler des Kernels 2.6 ist komplett umgeschrieben und erfüllt die Anforderungen in nachweisbar hohem Maße. Timo Hönig

  • Kernel 3.0

    Was steckt im Linux-Kernel 3.0? Ein Rundgang durch Taskverwaltung, Memory-Management und weitere wichtige Architekturmerkmale eines modernen Betriebssystemkerns.

comments powered by Disqus

Stellenmarkt

Artikelserien und interessante Workshops aus dem Magazin können Sie hier als Bundle erwerben.