Android Grundlagen – Completely Fair Scheduling (CFS) erklärt

Nachdem ich bereits in der vergangenen Nacht eine Reihe zu Linux Schedulern begonnen habe, und Euch zunächst einen kurzen Abriss zur Geschichte der Linux Scheduler präsentiert habe, will ich mich in diesem Artikel – wie versprochen – dem nächsten wesentlichen Scheduler in deren Entwicklung widmen, dem Completely Fair Scheduler (CFS). Es ist durchaus möglich, dass ich diese Reihe mit einem, noch einmal wesentlich längeren, Artikel über den – noch sehr jungen – Energy Aware Scheduler (EAS) abschließen werde, der aktuell bereits in den Pixel Smartphones aus dem Jahr 2016 zum Einsatz kommt, und in diesem Jahr noch einmal eine deutliche Weiterentwicklung erfahren hat. Aber beginnen wir mit dem CFS, und sehen wohin uns diese Reise führt.

Ein Überblick über den CFS

Die Hauptidee hinter dem CFS ist es die Balance (Fairness) bei der Zuteilung der Prozessoerzeit zu Tasks sicherzustellen. Wenn die Zeit für Tasks außer Balace gerät, so dass einem oder mehreren Tasks relativ zueinander nicht ausreichend Zeit zugewiesen wird, sollte dies erkannt werden können, um ihnen Zeit zuzuweisen, die ihre Ausführung ermöglicht.

Um die Balance zu bestimmen, verwaltet der CFS den Umfang der Zeit, welcher dem jeweiligen Task zugewiesen wurde, genannt die Virtual Runtime. Je geringer die Virtual Runtime eines Task – also der ihm zugewiesene Umfang an Zeit, in der er Zugriff auf den Prozessor erhält – ist, um so höher ist dessen Anspruch auf den Prozessor. Der CFS enthält zudem ein Konzept der Sleeper Fairness, um sicherzustellen, dass Tasks die aktuell nicht ausführbar sind (wie etwa, das Warten auf den I/O) ebenfalls einen vergleichbaren Anteil an dem Prozesor erhalten sobald sie diesen benötigen.

Aber anstatt die Tasks in einer Run-Queue zu verwalten, wie es bei vorangegangenen Linux Schedulern war, verwaltet der CFS einen zeitlich geordneten Red-Black-Tree. Ein Red-Black Tree ist ein Baum mit einigen interesanten, wie nützlichen, Eigenschaften. Zunächst ist er selbstausgleichend, was bedeutet, dass kein Pfad in dem Baum jemals doppelt so lang sein kann, als irgendein anderer. Dann treten Operationen auf dem Baum mit einer Zeit O(log n) auf, bei dem n die Zahl der Knoten auf dem jeweiligen Pfad entspricht. Letzteres bedeutet insbesondere, dass man Tasks extrem schnell und effizient einfügen, oder löschen kann.

cfsTREE

Die Tasks werden zeitlich sortiert in ein Red-Black-Tree angeordnet, wobei Tasks mit dem höchsten Bedarf am Prozessor (niedrigste Virtual Runtime) auf der linken Seite angeordnet sind, und Tasks mit dem geringsten Bedarf am Prozessor (höchste Virtual Runtime) auf der rechten Seite des Baumes angeordnet sind. Representiert werden sie durch sched_entity Objekte. Der Scheduler wählt und plant dann, um fair zu sein, den äußerst rechts angeordneten Knoten des Baumes, um Fairness zu gewährleisten. Der Task  berücksichtigt seine benötigte Zeit mit der CPU, indem er seine Ausführungszeit der Virtual Runtime hin-, und dann wieder in den Baum eingefügt wird. Auf diese Weise werden Tasks auf der linken Seite des Baumes Zeit zur Ausführung gegeben, und der Inhalt des Baumes wandert von rechts nach links, um die Fairness zu wahren. Daher jagt jeder lauffähige Task den Anderen, um eine Balance der Ausführung über die Menge der ausführbaren Tasks zu erhalten.

CFS Internals

Alle Aufgaben innerhalb des Linux-Systems werden durch eine Task-Struktur, task_struct, dargestellt. Diese Struktur beschreibt den Task vollständig und enthält seinen aktuellen Status, den Stapel, die Prozessflags, die Priorität (sowohl statisch als auch dynamisch) und vieles mehr. Man findet diese und viele der verwandten Strukturen in ./linux/include/linux/sched.h. Aber da nicht alle Tasks ausführbar sind, finden sich keine CFS-verwandten Felder in task_struct, weshalb eine neue Struktur namens sched_entity erstellt, um Scheduling-Informationen zu verfolgen.

Data structures (5)

Die Beziehungen der verschiedenen Strukturen sind in der obigen Abbildung dargestellt. Die Wurzel des Baumes wird über das rb_root-Element aus der cfs_rq-Struktur (in ./kernel/sched.c) referenziert. Blätter in einem Red-Black-Tree enthalten keine Information, so dass interne Knoten eine oder mehrere Tasks repräsentieren, die ausführbar sind. Jeder Knoten innerhalb des Baumes wird durch einen rb_node dargestellt, der nichts weiter enthält als die untergeordneten Referenzen und die Farbe des Elternteils. Die rb_node ist in der sched_entity-Struktur enthalten, die die rb_node-Referenz, das Lastgewicht und eine Vielzahl von Statistischen Daten enthält. Am wichtigsten ist, dass die sched_entity das vruntime (64-Bit-Feld) enthält, welches die Zeitspanne angibt, die der Task ausgeführt hat und als Index für den Baum dient. Schließlich sitzt die task_struct an der Spitze, die die Aufgabe vollständig beschreibt und auch die sched_entity-Struktur enthält.

Die Scheduling-Funktion ist relativ einfach, wenn es um den CFS-Anteil geht. In ./kernel/sched.c findet sich die generische Zeitplan ()-Funktion, die den aktuell laufenden Task vorgibt. Es gilt zu beachten, dass der CFS keine wirkliche Vorstellung von Zeitscheiben für Preemtion hat, da die Preemption-Zeit variabel ist. Der aktuell laufende Task wird durch einen Aufruf an put_prev_task (über die Scheduling-Klasse) an den Baum zurückgegeben. Wenn die Zeitplan-Funktion zur Identifizierung des nächsten Task zum Planen kommt, ruft sie die Funktion pick_next_task auf. Diese Funktion ist auch generisch (innerhalb ./kernel/sched.c), aber sie ruft den CF-Scheduler über die Scheduler-Klasse auf. Die Funktion pick_next_task in CFS befindet sich in ./kernel/sched_fair.c – genannt pick_next_task_fair (). Sie wählt die linke Aufgabe aus dem Baum und gibt die zugehörige sched_entity zurück. Mit dieser Referenz identifiziert ein einfacher Aufruf von task_of () die zurückgegebene task_struct-Referenz. Der generische Scheduler stellt dem Prozessor schließlich dieses Task zur Verfügung.

Advertisements

Seiten: 1 2

Ein Kommentar zu „Android Grundlagen – Completely Fair Scheduling (CFS) erklärt

Gib deinen ab

Kommentar verfassen

Trage deine Daten unten ein oder klicke ein Icon um dich einzuloggen:

WordPress.com-Logo

Du kommentierst mit Deinem WordPress.com-Konto. Abmelden /  Ändern )

Google+ Foto

Du kommentierst mit Deinem Google+-Konto. Abmelden /  Ändern )

Twitter-Bild

Du kommentierst mit Deinem Twitter-Konto. Abmelden /  Ändern )

Facebook-Foto

Du kommentierst mit Deinem Facebook-Konto. Abmelden /  Ändern )

Verbinde mit %s

This site uses Akismet to reduce spam. Learn how your comment data is processed.

Create a website or blog at WordPress.com

Nach oben ↑

%d Bloggern gefällt das: