Kernel- und Treiberprogrammierung mit dem Kernel 2.6 - Folge 20

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.