Mit dem Anticipatory-IO-Scheduler greift der Linux-Kernel vorausschauend und damit recht effektiv auf Festplatten zu. Der brandneue CFQ-IO-Scheduler tritt als ambitionierter Konkurrent auf. Der Artikel erklärt die Arbeitsweise beider Zugriffsstrategien und zeigt, worin sie sich unterscheiden.

Die vorige Folge der Kern-Technik-Reihe stellte die Arbeitsweise der No-Op- und Deadline-IO-Scheduler vor[1]. Beide sind Beispiele für die neue IO-Architektur in Kernel 2.6, die es erlaubt, IO-Scheduler zur Laufzeit auszutauschen. Dabei demonstriert der untätige No-Op-Scheduler auf einfache Weise, wie sich eine solche Komponente ins Gesamtsystem integriert. In echten Arbeitsumgebungen liefern der Deadline- und die im Folgenden beschriebenen Anticipatory- und CFQ-IO-Scheduler weitaus bessere Ergebnisse, denn sie arbeiten mit ausgefeilten Algorithmen.

In die Zukunft sehen

Der Anticipatory-IO-Scheduler (vorausschauend, anticipatory) kann seine Verwandtschaft zum Deadline-IO-Scheduler nicht leugnen[2]. Wie dieser sortiert er die Aufträge nach aufsteigenden Sektornummern in einem Red-Black-Tree und verhindert über eine mit Fifos implementierte Zeitüberwachung das Verhungern einzelner Aufträge. Auch er kennt die Dispatch-Queue, in die er – zum Beispiel nach dem Unplugging – Aufträge verschiebt und aus der der Plattentreiber sich die Aufträge nach dem Fifo-Prinzip herausholt.

Zusätzlich berücksichtigt der Anticipatory-IO-Scheduler jedoch auch den Rechenprozess, in dessen Auftrag er lesen und schreiben soll. Das ist durchaus sinnvoll, denn üblicherweise verteilen sich die Daten einer Applikation nicht kreuz und quer über die gesamte Festplatte. Vielmehr legen moderne Filesysteme die Daten in möglichst sequenziell hintereinander liegenden Sektoren auf der Festplatte ab, man spricht von einer Lokalität der Daten.

Die Sache hat nur einen Haken: In Unix-Systemen greifen Applikationen synchron zu. Sie starten einen neuen Leseauftrag erst, wenn der letzte Auftrag abgeschlossen ist (siehe Abbildung 1). Bei Verwendung des Deadline-Schedulers[1] bedeutet dies, dass der Schreib-Lese-Kopf der Festplatte sich bereits von der gewünschten Plattenposition entfernt hat. Der nachfolgende Auftrag müsste also wohl knapp 500 Millisekunden warten – das ist viel zu lange für ein interaktives System.

Abbildung 1: Synchrones Lesen: Typischerweise erteilen Applikationen erst dann den nächsten IO-Auftrag, wenn der vorhergehende abgeschlossen ist.

Anders als der Deadline- verschiebt der Anticipatory-Scheduler normalerweise nicht gleich einen ganzen Batch in die Dispatch-Queue, sondern nur einen einzelnen Auftrag. Holt der Gerätetreiber einen Auftrag beim IO-Scheduler ab, überprüft dieser den nächsten Kandidaten. Stammt der Auftrag vom gleichen Rechenprozess, reicht der Scheduler ihn an den Gerätetreiber weiter. Das tut er auch, wenn es sich um einen benachbarten Auftrag handelt, also einen, dessen Speicherort auf der Festplatte sich in der Nähe befindet.

Aufträge bearbeiten

In allen anderen Fällen zieht der IO-Scheduler eine Zugriffsstatistik zu Rate, die er für jeden Prozess getrennt führt. Ist zu erwarten, dass ein Prozess bald einen neuen Auftrag erteilen wird, bleibt seine Dispatch-Queue zunächst leer – der Treiber und damit das Gerät bekommen keinen neuen Auftrag und warten. Trifft ein neuer Auftrag ein, reicht der Scheduler ihn an den Gerätetreiber durch. Bleibt er aus, startet der IO-Scheduler einen Timer. Er holt sich entweder aus der Fifo-Liste (abgelaufene Deadline) oder aus dem Red-Black-Tree den nächsten Auftrag.

Abbildung 2 zeigt, wie der Anticipatory-Scheduler auf Requests wartet. Trifft während der Wartezeit kein neuer Auftrag vom selben Prozess (in der Abbildung nach Sektor 70) ein, übergibt der Scheduler den nächsten, bereits vorhandenen Auftrag (hier Sektor 100) an den Gerätetreiber.

Abbildung 2: Der Anticipatory-IO-Scheduler sortiert die Anfragen und wartet zusätzlich auf später ankommende Aufträge. Rückwärtsbewegungen des Schreib-Lese-Kopfes werden damit weitgehend vermieden.

Dass sich das Warten lohnt, zeigt ein Blick auf die für das Beispiel optimale Seek-Distanz. Für den Deadline-IO-Scheduler betrug sie im analogen Fall 189 (siehe[1]). Auch die Seek-Time, also die Zugriffszeit als solche, verkürzt sich trotz Wartens erheblich.

Der Scheduler führt Buch

Woran erkennt der Anticipatory-Scheduler, dass es besser ist, noch zu warten und den Auftrag eines anderen Prozesses nicht sofort dem Gerätetreiber zu übergeben? Dazu berechnet er für jeden Rechenprozess die bereits erwähnte Statistik, bei der er den durchschnittlichen zeitlichen Abstand zwischen zwei Leseaufträgen misst. In der Sprache des Anticipatory-Schedulers ist dies die Denkzeit (Thinktime). Zudem führt er eine Statistik darüber, wie nahe die jeweiligen Aufträge beieinander liegen (Seek-Distanz). Wegen dieses Faktors findet ein Rechenprozess kaum Berücksichtigung, der zwar häufig Requests erteilt, die aber weit auseinander liegen.

Wie seine einfacher gestrickten Kollegen unterscheidet auch der Anticipatory-IO-Scheduler zwischen Lesen und Schreiben. Allerdings richtet er sich nicht nach der Anzahl der übergebenen Batches, sondern beachtet eine einstellbare Zeitdauer. Dieser Wert ist für Lesen und Schreiben getrennt einzustellen (Parameter »read_batch_expire« und »write_batch_expire«). Die Schreibaufträge übergibt man wie beim Deadline-IO-Scheduler als Batch.

Und noch ein Unterschied zu den IO-Schedulern aus der vorigen Folge: Der Anticipatory-Scheduler gibt unter Umständen auch Aufträge mit niedrigeren Sektornummern als der aktuellen an den Gerätetreiber weiter. Er erlaubt also eine Rückwärtsbewegung des Schreib-Lese-Kopfes. Das macht er, wenn der nächsthöhere Sektor mehr als doppelt so weit entfernt ist wie der niedrigere.

Der Anticipatory-IO-Scheduler ist der Standard-IO-Scheduler im aktuellen Linux-Kernel. Die Tabelle “Anticipatory-IO-Scheduler einstellen” beschreibt die damit verfügbaren Tuning-Parameter im Einzelnen.

Completely Fair Queueing

Einen etwas anderen Ansatz als der Anticipatory-IO-Scheduler verfolgt der CFQ-IO-Scheduler (CFQ, Completely Fair Queueing). Sein Grundprinzip besteht darin, die vorhandene Bandbreite für den Plattenzugriff möglichst gerecht zwischen den einzelnen Rechenprozessen aufzuteilen.

Aufträge legt er prinzipiell nach Threadgruppen (TGID) getrennt ab. Abbildung 3 zeigt, dass dazu für jede Threadgruppe (»struct cfq_queue«) ein eigener Red-Black-Tree (»sort_list«) und eine eigene Fifo-Liste (»fifo«) zur Verfügung stehen. Innerhalb der »sort_list« gibt es übrigens keine Unterscheidung zwischen Lese- und Schreibaufträgen, wohl aber in der Fifo-Liste.

Abbildung 3: Der CFQ-IO-Scheduler besitzt für jede Threadgruppe einen eigenen Satz an Datenstrukturen. Um Fairness zu garantieren, übernimmt er von jeder Threadgruppe jeweils einen Auftrag in die Dispatch-Queue. Die so geordneten Aufträge wandern über eine Warteschlange zum Gerätetreiber.

Dass der CFQ-Scheduler nicht selbst zwischen Lese- und Schreibaufträgen unterscheidet, spielt keine Rolle, denn Schreibaufträge erfolgen ohnehin selten im Kontext des Prozesses, zu dem die Daten gehören. Vielmehr initiiert der Systemprozess »pdflush« das Sichern der Daten aus dem Pagecache, sodass die Trennung aufgrund der Threadgruppe gleichzeitig auch Schreib- und Leseaufträge unterscheidet.

Das Dispatching, also das Verteilen und Übergeben der Aufträge an den Gerätetreiber, geschieht in einer Funktion namens »cfq_dispatch_requests()«. Für jede Threadgruppe verschiebt der IO-Scheduler jeweils einen Auftrag in die Dispatch-Queue. Aufträge einer Threadgruppe bleiben von ihm unberücksichtigt, wenn sich einer ihrer Aufträge in Bearbeitung (»in_flight«) befindet. Der Dispatch-Queue (»queuelist«) entnimmt der Gerätetreiber nach dem Fifo-Prinzip die Aufträge zur Bearbeitung.

Insgesamt versucht der Dispatcher eine Anzahl »quantum«-Requests in die »queuelist« zu übernehmen. Gibt es wenige Threadgruppen mit IO-Aufträgen, verschiebt der IO-Scheduler auch schon mal mehrere Aufträge aus einer einzigen Threadgruppe.

Timer sorgen für Gerechtigkeit

Normalerweise verschiebt der Scheduler den in der »sort_list« folgenden Auftrag einer jeden Threadgruppe – abhängig also vom zuletzt erteilten Auftrag – nach dem Elevator-Prinzip. Um dabei das Verhungern (Starvation) einzelner Aufträge zu verhindern, überwacht auch der CFQ-IO-Scheduler über die Fifo-Liste die abgelaufene Zeit. Die Werte »fifo_sync_expire« (fürs Lesen; die entsprechende interne Variable heißt »cfq_fifo_expire_r«) sowie »fifo_async_expire()« (fürs Schreiben; die interne Variable heißt »cfq_fifo_expire_w«) parametrisieren die zugehörigen Deadlines.

Steht an erster Stelle in der Fifo-Liste ein Auftrag, dessen Deadline abgelaufen ist, bevorzugt der Scheduler ihn beim Verschieben in die Dispatch-Queue. Gibt es einen solchen Auftrag sowohl in der Lese- als auch in der Schreib-Fifo-Liste, besitzt die Lese-Fifo Priorität. Allerdings überwacht der IO-Scheduler die Fifo-Listen nicht ständig. Hat er sich einmal aus der Fifo-Liste bedient, wartet er mindestens die Zeit »fifo_batch_expire« ab, bevor er erneut die Fifo-Listen der entsprechenden Queue überprüft. Die Tabelle “CFQ-IO-Scheduler einstellen” beschreibt die Parameter und ihre Verwendung im Detail.

Blick in die Glaskugel

Im Vergleich zum Anticipatory-IO-Scheduler kann der CFQ bei Durchsatz und maximaler Latenzzeit nicht überzeugen. Wegen seiner Vorzüge in puncto Interaktivität aktivieren einige bekannte Distributionen CFQ jedoch bereits beim Booten. Entscheidender für die Kernelentwickler ist hingegen das Potenzial, das sie in den verwendeten Grundprinzipien sehen. Anders als der Anticipatory-IO-Scheduler ist der CFQ-IO-Scheduler nämlich noch nicht ausgereizt.

In der Tat arbeitet Jens Axboe, der verantwortlich für das Blockgeräte-Subsystem im Linux-Kernel ist, kräftig am CFQ. Auf der Kernel-Mailingliste kursierten bereits Patches für einen Time-sliced CFQ-IO-Scheduler mit Prioritäten[3]: Statt von jedem Rechenprozess genau einen IO-Auftrag in die Dispatch-Queue zu übernehmen, stellt diese Scheduler-Variante jedem Rechenprozess eine Zeitscheibe (Time Slice) zur Verfügung. Währenddessen übernimmt er Aufträge in die Dispatch-Queue und bearbeitet sie auch gleich. Wie beim Anticipatory-IO-Scheduler eröffnet das die Möglichkeit, eine kurze Zeit (maximal die einstellbare Zeit »slice_idle«) auf weitere Aufträge des gleichen Prozesses zu warten. Diese Aufträge sind wegen des Lokalität-Prinzips mit großer Wahrscheinlichkeit benachbart zum vorherigen.

So gut wie möglich

Damit nicht genug: Der neue Time- sliced CFQ-IO-Scheduler berücksichtigt zusätzlich noch IO-Prioritäten. Jens Axboe definierte zunächst drei Prioritätenklassen: »Idle«, »Best Effort« (BE) und »Realtime«. Die normalerweise verwendete Klasse »Best Effort« bietet insgesamt acht Prioritäten, wobei die mit »0« bezeichnete Priorität die höchste dieser Klasse ist (siehe Abbildung 4). Ohne weiteres Zutun teilt der IO-Scheduler einem Prozess eine Best-Effort-Priorität gemäß seinem Nice-Wert zu. Um diesen Wert zu beeinflussen oder um einem Prozess gar eine Echtzeitpriorität zu geben, führte Axboe die neuen, aber nur vorläufigen Systemcalls »ioprio_set« und »ioprio_get« ein. Sollte der Code Eingang in den offiziellen Kernel finden – so die Warnung – sind Änderungen zu erwarten. Ein Beispiel dafür, wie man diese Systemcalls nutzt, findet sich in[4].

Abbildung 4: Die IO-Priorität wird mit 16 Bit kodiert. Die obersten 3 Bits wählen eine von drei definierten Klassen aus. Die unteren 13 Bits spezifizieren im Fall von Best Effort die Priorität (von 0 bis 7).

Zeitscheiben

Abbildung 5 zeigt die wesentlichen Datenstrukturen des Time-sliced CFQ-IO-Schedulers mit Prioritäten. Das Objekt »cfq_data« repräsentiert das Gerät respektive den IO-Scheduler. Die Zeitscheibenvariante des CFQ-IO-Schedulers sortiert die Aufträge nicht auf Basis der Threadgruppen (TGID), sondern nach Threads (PID). Jeder Prozess findet eine Entsprechung in einem Objekt des Typs »cfq_queue« – allerdings nicht nur in einer Liste, sondern gleich in mehreren gemäß der IO-Priorität.

Abbildung 5: Die Requests eines Thread sind nach Prioritäten sortiert. Fordert der Gerätetreiber einen Request an, übergibt der IO-Scheduler einen Auftrag aus der »cfq_queue« an die Real-Time-Queue »cur_rr«. Ist diese leer, fügt er stattdessen einen Best-Effort-Prozess hinzu.

Die ersten acht Listen »rr_list« entsprechen den acht Prioritäten für Best-Effort-Aufträge. Aufträge, die über die Dispatch-Queue an den Gerätetreiber gehen, werden allerdings nur den Request-Queues entnommen, die in der Liste »cur_rr« stehen. Immer wenn »cur_rr« leer ist, entnimmt der Scheduler ein »cfq_queue«-Objekt gemäß IO-Priorität den Best-Effort-Listen. Prozessobjekte, deren IO-Aufträge der Real-Time-Klasse angehören, hängt der Scheduler direkt in die Liste »cur_rr« ein und bedient sie somit zuerst.

Die Funktion »cfq_dispatch_requests()« verschiebt nach bekanntem Schema maximal »quantum« Aufträge aus der Request-Queue in die Dispatch-Queue. Falls der zur Request-Queue gehörige Prozess seine IO-Zeitscheibe verbraucht hat, berücksichtigt der Scheduler die Request-Queue des nächsten Prozesses aus der Schlange »cur_rr«. Das »struct cfq_queue«-Objekt verwaltet die eigentlichen IO-Aufträge (»cfq_request«) in Red-Black-Trees und in Fifo-Listen getrennt fürs Lesen und Schreiben.

Tests mit der Zeitscheiben-Variante des CFQ zeigen, dass dieser bezüglich Durchsatz und Latenzzeiten zum Anticipatory-IO-Scheduler aufschließt[5]. Übertrumpft hat er ihn allerdings bislang noch nicht.

Abbildung 6: Jedem Thread steht eine Zeitscheibe zur Verfügung, während der er exklusiv Aufträge an den Gerätetreiber übergeben kann. Die Länge der Zeitscheibe hängt von der IO-Priorität ab. Wartet er nach einem Auftrag länger als »slice_idle«, wird die Zeitscheibe abgebrochen.

IO-Scheduling-Alternativen

Jens Axboe ist nicht konkurrenzlos, wenn es um die Optimierung der Festplattenzugriffe geht. Philips in Eindhoven beispielsweise entwickelt zusammen mit Werner Almesberger das Active Block IO Scheduling System (ABISS), das den Applikationen garantierte Lese- und Schreibraten bereitstellt (Realtime Streams). Eine erste Implementierung gibt es bereits [6]. Ob und wann allerdings Code in den Standardkernel übernommen wird, steht in den Sternen. (ofr)