Linux Grundlagen – Kurze Geschichte der ersten Linux Scheduler

Die Linux Scheduler sind ein interessantes Studienobjekt. Auf der einen Seite mit Blick auf die Anwendungsmodelle, in denen man Linux heute findet, denn obschon Linux als Desktop Betriebssystem entwickelt wurde, trifft man es heute ebenfalls auf Servern, kleinen embedded Devices, Mainframes, und Supercomputern an. Kein Wunder also, dass die Scheduling Last, je nach Plattform, stark zueinander variieren. Auf der anderen Seite stehen dem die Fortschritte der Plattformen gegenüber, zu welchen die Architektur (Multiprocessing, symmetrisches Multiprocessing, Non-uniform Memory Access [NUMA]) und die Virtualisierung zählen. Ebenfalls integriert ist hier die Balance zwischen Interaktivität (Nutzerreaktion) und einer gesamtheitlichen Fairness. Alleine dies lässt erahnen wie komplex und schwierig das Scheduling-Problem innerhalb des Linux-Systems – zu denen auch Android zählt – sein kann.

Frühe Linux Scheduler haben ein minimales Design genutzt, nicht ausgelagt auf massive Architekturen mit vielen Processoren, oder gar Hyperthreading. Erst Linux Version 2.2 hat die Idee von Scheduling Klassen eingeführt, und damit Scheduling Policies für real-time Tasks, non-real-time Tasks und non-preemtible Tasks zugelassen. Er enthielt außerdem Unterstützung für das Symmetrische Multiprocessing – kurz SMP.

Der O(N)-Scheduler

Der 2.4er Kernel wiederum besaß einen relativ simplen Scheduler, der auf Basis des mathematischen O(N) Laufzeitalgorythmus operaierte (da er über jeden Task während eines Scheduling Events iterierte). Er spaltete Zeit in Perioden auf, und innerhalb jeder Periode, war die Ausführung eines jeden Task bis zum Erreichen seiner vorgesehenen Zeitscheibe erlaubt. Für den Fall, dass ein Task nicht all seine Zeitscheiben benötigte, wurde der Rest einer neuen Zeitscheibe hinzuaddiert, um dem dort ausgeführten Task zu erlauben, dass er – wenn nötig – in der darauffolgenden Periode länger laufen konnte. Der Scheduler iterierte einfach über Tasks, unter Anwendung einer Gütefunktion (Metrik genannt), um zu bestimmen welcher Task als nächstes ausgeführt werden soll. Auch wenn dieses Herangehen vom Prinzip her relativ simpel ist, war es dennoch auch sehr ineffizient, mangelte an Skalierbarkeit, und war schwach bei real-time Systemen. Es mangelte zudem an Features, um die Vorteiler neuer Hardware Architekturen, wie etwa Multi-Core Prozessoren, zu nutzen.

Der O(1)-Scheduler

Der frühe 2.6 Scheduler, genannt O(1)-Scheduler, war dazu designed viele Probleme seines – oben erläuterten – Vorgänger zu lösen. So war dieser neue Scheduler nicht darauf angewiesen die gesamte taskliste zu iterieren, um den nächsten, zu planenden Task zu identifizieren. Alleine diese Tasache machte ihn bereits wesentlich effeizienter und skalierbarer. Der O(1)-Scheduler hält die lauffähigen Tasks in einer Run-Warteschlange (eigentlich zwei Run-Warteschlangen für jede Prioritätsebene – eine für aktive und eine für abgelaufene Tasks) nach, was de Facto bedeutet, dass der Scheduler – um den als nächstes auszuführenden Task zu identifizieren – lediglich den nächsten Task aus der, gemäß Priorität aktiven, Run-Queue heraus aufnehmen musste. Der O(1)-Schdeuler war nicht nur skalierbarer, sondern integrierte außerdem Interaktivitäts-Metriken mit zahlreichen Heuristiken, um festzustellen, ob Aufgaben I/O-gebunden, oder prozessorgebunden waren. Dies führte dazu, dass der Scheduler im Linux Kernel unhändelbar wurde, da die Masse an Code, die benötigt wurde um Heuristiken zu berechnen, grundlegend schwer zu bewältigen war, und es den Puristen an algorithmischer Substanz fehlte.

Prozesse vs. Threads

Linux integriert Process und Thread Scheduling, indem es den Einen, wie auch den Anderen vollkommen gleich behandelt. Ein Prozess kann daher als ein einzelner Thread betrachtet werden, und dennoch kann dieser Prozess eine Vielzahl an Threads enthalten, die sich somit eine gewisse Anteil der Ressourcen teilen (Code und/oder Daten).

Angesichts der Probleme, denen sich der O(1)-Scheduler stellen musste, und anderer externer Drücke, musste dringend etwas geändert werden. Diese Veränderung kam auf dem Weg eines Kernel-Patch von Con Kolivas, mit seinem Rotating Staircase Deadline Scheduler (RSDL), die seine früheren Arbeiten an dem Staircase Scheduler enthielten. Das Ergebnis dieser Arbeit war ein relativ einfach designeter Scheduler, der Fairness mit begrenzter Latenz inkorporierte. Kolivas‘ Scheduler beeindruckte viele – inklusive Aufforderungen diesen in den aktuellen 2.6.21 Mainline-Kernel zu integrieren. So wurde noch viel offensichtlicher, dass eine Veränderung des Scheduler auf den Weg gebracht war. Ingo Molnar, der Schöpfer des O(1)-Schedulers, entwickelte so schließlich den Completely Fair Scheduler (CFS), der um viele Ideen aus Kolivas‘ Arbeit herum konstruiert war.

Der CFS ist es allerdings auch wert ihm einen eigenen Artikel zu widmen, it dessen Erstellung ich mich die kommenden Tage befassen werde.

Advertisements

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 )

w

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: