Bei Linux 2.6.10 kann der Anwender über die Auswahl von IO-Schedulern bestimmen, wie der Kernel auf Festplatten zugreift. Wer weiß, wie sie intern funktionieren, passt das System optimal an die eigene Anwendung an. Zur Laufzeit lassen sich die IO-Scheduler über das SysFS austauschen und einstellen.

Das Blockgeräte-Subsystem – im Kernel 2.6 grunderneuert – ist für den effizienten Transport von Daten zwischen Applikationen und Festplatten verantwortlich[1]. Damit hat es wesentlichen Anteil an der Performance und an der so genannten Interaktivität des Systems. Eine ganze Reihe von Techniken gestaltet den Zugriff möglichst optimal (siehe Abbildung 1).

Getrennt lesen und schreiben

So trennt der VFS (Virtual Filesystem Switch) die Aufträge für zeichenorientierte Geräte von denen für blockorientierte. Außerdem löst er Dateinamen in Sektornummern auf. Die zu einer Sektornummer gehörigen Daten sucht der Kernel im Page-Cache, der die Applikation von dem eigentlichen Gerät entkoppelt. Für diese Aufgabe hält der Page- Cache jeweils eine Kopie genau jenes Blocks (Sektors) vorrätig, auf den die Applikation zugreifen möchte. Der Page-Cache legt die Kopie dabei asynchron zum Ablauf der Applikation an.

Die im Page-Cache generierten Aufträge (Requests) werden dem so genannten Elevator übergeben, der das Zusammenfassen und Sortieren von Aufträgen im IO-Scheduler veranlasst. Darüber hinaus sorgt der Elevator (Fahrstuhl) dafür, dass sich der Gerätetreiber zu gegebener Zeit seine Aufträge abholt. Allerdings tut er dies erst dann, wenn eine ausreichende Anzahl von Aufträgen vorhanden ist – sonst gibt es schließlich nichts zu sortieren (siehe Kasten “IO-Scheduler im Blockgeräte-Subsystem”).

Verstopfen und füllen

Bildlich gesprochen verschließt (Plugging) der Elevator den Pool (Queue), in dem sich die Aufträge befinden und zum Sortieren ansammeln. Dann entfernt der Scheduler den Stopfen (Unplugging) und reicht die Aufträge an den Treiber weiter. Natürlich darf der Pool nicht zu lange zugepfropft bleiben. Deshalb startet man beim ersten Auftrag einen Timer mit einem Wert von beispielsweise drei Millisekunden.

Das Sortieren und Zusammenfassen der Aufträge beschleunigt den Festplattenzugriff insgesamt, denn diese Strategie minimiert Bewegungen des Schreib-Lese- Kopfes. Das deutet bereits der Name Elevator an: Die Aufträge werden nach Möglichkeit so an die Platte weitergereicht, dass der Schreib-Lese-Kopf der Platte keine Zickzack-Bewegungen ausführen muss, sondern sich fahrstuhlähnlich von den niedrigen Sektornummern zu den hohen bewegt und genauso wieder wieder zurück.

So einfach das Prinzip klingt, so kompliziert ist es zu implementieren. Ein einfaches Einsortieren neuer Aufträge führt nämlich unter ungünstigen Umständen zum Verhungern (Starvation) einzelner Requests. Erteilt eine Applikation beispielsweise den Auftrag, die Sektoren mit den Nummern 20 und 30000 zu lesen, wird der Block 30000 eventuell erst zu einem viel späteren Zeitpunkt gelesen. Das wäre der Fall, wenn andere Applikationen nur Sektoren kleiner 30000 anfordern.

Das Einsortieren der Aufträge steigert zwar die IO-Performance, verschlechtert aber die Interaktivität. Hier gilt es also, einen möglichst guten Kompromiss zu finden. Dass dieser möglichst wenig Rechenleistung verbrauchen soll, versteht sich von selbst. Da es keinen für jede Anwendung optimalen IO-Scheduler gibt, stellt Kernel 2.6 vier verschiedene Algorithmen zur Wahl: No-Op-, Deadline-, Anticipatory- und CFQ-IO-Scheduler (siehe Abbildung 2).

Der No-Op-Scheduler ist in jedem Fall im Kernel einkompiliert, schon um beim Booten auf das Root-Filesystem zugreifen zu können. Der User darf beim Kernel-Compile auch mehrere IO-Scheduler konfigurieren und beim Booten einen davon auswählen. Noch besser ist allerdings: Ab Kernel 2.6.10 lässt sich der IO-Scheduler für jedes Blockgerät jederzeit separat auswählen. Entsprechende Einträge im Sys-Filesystem passen den Algorithmus optimal an die eigene Anwendung an (siehe Kasten: “IO-Scheduler im Kernel 2.6.10”).

Abbildung 1: Verschiedene Mechanismen beschleunigen den Zugriff auf langsame Festplatten. Die Funktionen »elv_add_request_fn()« und »elevator_next_req()« sind die Hauptschnittstellen zum IO-Scheduler.

Abbildung 2: Auswahl der IO-Scheduler bei der Kernelkonfiguration. Sind alternative IO-Scheduler Teil des Kernels, kann der Benutzer sie zur Laufzeit über das Sys-Filesystem austauschen.

Ein- und Ausgabe in Zahlen

Dass der IO-Scheduler großen Einfluss auf die Interaktivität des Systems besitzt, hat Andrew Morton mit einem einfachen Benchmark demonstriert[3]. Um IO-Last zu erzeugen, startet der User im Hintergrund einen großen Datentransfer. Er wartet so lange, bis der Page-Cache mit den Blöcken gefüllt ist, und misst dann die Zeit, bis das Auslesen mehrerer Dateien abgeschlossen ist. Listing 1 implementiert diesen Ablauf. Wie die meisten anderen Benchmarks ist auch dieser nicht völlig zuverlässig: Die 15-Sekunden-Pause entfernt nicht immer alle eingelesenen Dateien aus dem Page-Cache. Das führt bei darauf folgenden Messungen zu – jedoch nur vermeintlich – besseren Werten.

Im Übrigen setzt Listing 1 voraus, dass das Verzeichnis »/tmp/« und die Kernelquellen auf der ersten IDE-Platte »hda« liegen. Allerdings dürfen sich die Kernelquellen und das Tmp-Verzeichnis durchaus auf unterschiedlichen Partitionen dieser Platte befinden. Außerdem muss im Tmp-Verzeichnis etwa 7 GByte freier Platz zur Verfügung stehen.

Abbildung 4 zeigt das Ergebnis: Mit Abstand am schlechtesten schneidet der No-Op-IO-Scheduler ab. Er benötigt zum Auslesen der Dateien ungefähr zehnmal so viel Zeit wie die Konkurrenten. Am besten schneiden der Anticipatory- und der CFQ-IO-Scheduler ab. Die nahe liegende Schlussfolgerung, der Anticipatory-Scheduler sei in jedem Fall der beste, ist allerdings nicht gerechtfertigt. Denn sowohl der Durchsatz als auch die Interaktivität hängen von der Charakteristik der laufenden Applikationen und von der Hardware ab. <@99 L_Dreieck (E)>E

IO-Scheduler im Blockgeräte-Subsystem

Aus Sicht des Kernels ist ein IO-Scheduler ein Objekt vom Typ »struct elevator_type«, das mindestens vier Methoden zur Verfügung stellt. Die Funktion »elv_register()« registriert den IO-Scheduler beim Kernel. Der IO-Scheduler arbeitet dabei wie ein Pool, in dem der Page-Cache seine Aufträge ablegt und von dem der Gerätetreiber Requests zur Bearbeitung entnimmt. Welcher Pool (IO-Scheduler) verwendet wird, steht in der Request-Queue, dem Objekt, das der Treiber bei seiner Initialisierung dem Blockgeräte-Subsystem übergibt (über die Funktion »blk_init_queue()«, siehe[5]). Der Aufruf der IO-Scheduler-Methoden vom Page-Cache aus ist in der Funktion »__make_request()« in »drivers/block/blk_ll_rw.c« kodiert (siehe Abbildung 2). Zuerst versucht der Page-Cache einen Auftrag mit anderen zu vereinen (Aufruf der Methode »elevator_merge _fn()«). Falls dies nicht gelingt, fügt er den Auftrag über »elevator_add_req_fn()« dem Pool hinzu. Die Funktion »__generic_unplug_ device()« übernimmt das Unplugging und damit die Entnahme von Aufträgen durch den Gerätetreiber. Diese Funktion ruft der Kernel auf, wenn der Timer abläuft. Falls sich im Pool des IO-Schedulers Aufträge befinden, ruft »__generic_unplug_device()« die Request-Funktion des Gerätetreibers auf. Diese Funktion wiederum entnimmt per »elevator_next_ req()« die Aufträge und bearbeitet sie anschließend. Abbildung 3: Einbettung des IO-Schedulers in das Blockgeräte-Subsystem.

Moderne SCSI-Festplatten bringen ein so genanntes TCQ (Tagged Command Queuing) mit, womit sie Aufträge selber noch umsortieren. Das wiederum hebelt aber das Umsortieren durch die Kernelalgorithmen aus. Ähnliches gilt für Raid-Systeme, denn bei diesen verteilt sich eine Datei auf mehrere Festplatten. Dass hier mehrere Schreib-Lese-Köpfe bewegt werden, berücksichtigen die Algorithmen aber nicht.

Abbildung 4: Das Diagramm zeigt die Dauer für die Ausgabe einiger C-Dateien bei unterschiedlichen IO-Schedulern an, wenn das System unter IO-Last steht (Pentium M, 1,4 GHz, 512 MByte Hauptspeicher).

Der einfachste der vier Algorithmen ist der No-Op-IO-Scheduler. No-Op steht für No-Operation, was bedeutet, dass die Requests nicht sortiert werden. Immerhin versucht der Scheduler aber Aufträge zusammenzufassen. Wenn sich ein Auftrag der Art “Lese ab Sektor 1234 vier Sektoren” in der Request-Queue befindet und danach ein Auftrag “Lese ab Sektor 1238 drei Sektoren” folgt, fasst der No-Op-Scheduler beide zum Auftrag “Lese ab Sektor 1234 sieben Sektoren” zusammen (siehe Abbildung 5).

01 #!/bin/bash
02 # Simples Skript zur Messung der Interaktivität der IO-Scheduler.
03 # GPL, (c) 2004, Juergen Quade.
04 
05 SCHEDULERFILE=/sys/block/hda/queue/scheduler
06 
07 function do_benchmark()
08 {
09    dd if=/dev/zero of=/tmp/foo bs=1M count=7000 &
10    echo $1 >$SCHEDULERFILE
11    sleep 15
12    echo -n "---> $1: "
13    time cat /usr/src/linux/kernel/*.c > /dev/null
14    # clean up
15    echo anticipatory >$SCHEDULERFILE
16    kill -9 $! # kill last background process (dd)
17    rm /tmp/foo
18 }
19 
20 do_benchmark noop
21 do_benchmark anticipatory
22 do_benchmark deadline
23 do_benchmark cfq

Abbildung 5: Das Zusammenfügen zweier Requests zu einem heißt Merging. Backmerging hängt den zweiten Auftrag an den ersten an, Frontmerging setzt den zweiten vor den ersten.

Aufträge zusammenfassen

Hängt der Scheduler einen Auftrag an einen anderen an, so heißt das Backmerging. Entsprechend spricht man von Frontmerging, wenn der Scheduler einen zweiten Auftrag vor einen bereits existierenden stellt. Wenn also nach “Lese ab Sektor 1234 vier Sektoren” der Auftrag “Lese ab Sektor 1231 drei Sektoren” folgt, erzeugt der IO-Scheduler durch Frontmerging den Auftrag “Lese ab Sektor 1231 sieben Sektoren”.

Der No-Op-Scheduler hängt einen neuen Auftrag – wenn er ihn nicht mit einem bestehenden zusammenfügen kann – ans Ende einer Liste an. Der Treiber nimmt sich immer das erste Element aus dieser Liste, die damit ein Fifo implementiert, Verhungern der Aufträge kommt nicht vor. Dieser IO-Scheduler ist wirklich simpel, er verbraucht kaum Rechenzeit und besitzt keine für den Anwender einstellbaren Parameter.

Wie das Beispiel in Abbildung 6 zeigt, arbeitet er nicht unbedingt optimal: Drei Rechenprozesse benötigen Daten aus den Festplattensektoren 100, 50 und 70. Wenn Rechenprozess B aus Sektor 50 gelesen hat, braucht er zusätzlich noch Daten aus Sektor 51. Kommen die Aufträge in dieser Reihenfolge beim No-Op-Scheduler an, übergibt er sie beim Unplugging in derselben Reihenfolge dem Gerätetreiber. Der Schreib-Lese-Kopf der Festplatte hat damit aber einen vergleichsweise weiten Weg (Seek-Distanz) zurückzulegen: Erst 100 Sektoren vorwärts, dann 50 Sektoren zurück (was zeitlich betrachtet besonders teuer ist), dann wieder 20 Sektoren nach vorne und schließlich noch einmal 19 Sektoren rückwärts.

Der zweite IO-Algorithmus, der zur Auswahl steht, ist der Deadline-Scheduler. Bei ihm handelt es sich um eine Weiterentwicklung des Linus-Elevators, des Standard-IO-Scheduler in Kernel 2.4.

Im Zeitplan mit dem Deadline-Scheduler

Als Erweiterung zum No-Op-Scheduler gibt der Deadline-Scheduler die einzelnen Lese- und Schreibaufträge in aufsteigender Reihenfolge der Sektornummern an die Festplatte weiter. Weil es ungünstig ist, Schreib- und Leseaufträgen zu mischen, verwaltet der Scheduler die beiden Sorten getrennt.

Seinen Namen erhielt dieser IO-Scheduler, weil er die Aufträge (um das Verhungern zu verhindern) mit einer oberen Zeitschranke (der Deadline) versieht. Damit kann der Deadline-IO-Scheduler die Aufträge nicht nur gemäß der jeweiligen Sektornummer (in der Datenstruktur »sort_list«), sondern zugleich (in einer eigenen Datenstruktur »fifo_list«) auch entsprechend ihres zeitlichen Auftretens sortieren.

Auch die zeitliche Sortierung erfolgt für Lese- und für Schreibaufträge getrennt (Abbildung 7). Der Gerätetreiber entnimmt den nächsten Auftrag der Dispatch-Queue. Ist sie leer, prüft er zunächst, ob in der »fifo_list« ein Auftrag steht, dessen Deadline abgelaufen ist. Wenn ja, entnimmt er diesen Auftrag zusammen mit einer Anzahl benachbarter Requests aus der »sort_list« und der »fifo_list« und verschiebt ihn in die Dispatch-Queue (in Abbildung 6 sind dies drei zusätzliche Requests).

Abbildung 6: Der No-Op-IO-Scheduler reicht die Aufträge in der Reihenfolge ihres Eintreffens an den Gerätetreiber weiter. Das führt zu aufwändigen Rückwärtsbewegungen des Schreib-Lese-Kopfes der Festplatte, die Seek-Distanz ist also relativ groß (Darstellung qualitativ).

Kernelhacker nennen eine solche Gruppe von IO-Aufträgen Batch. Zu ihr gehören auch Aufträge, deren Deadline nicht abgelaufen ist. Falls noch gar keine Deadline überschritten ist, entnimmt der Scheduler seiner »sort_list« den zum vorherigen Request benachbarten Auftrag (in Richtung aufsteigender Sektornummern) und verschiebt ihn in die Dispatch-Queue. Sie führt die bisher getrennt behandelten Lese- und Schreibaufträge wieder zusammen. Dabei bevorzugt sie allerdings normalerweise die Leseaufträge, da diese für die Interaktivität des Systems von größerer Bedeutung sind. Standardmäßig kommt auf zwei Gruppen Leseaufträge eine Gruppe Schreibaufträge (siehe »deadline_dispatch_requests()« in »drivers/block/deadline_iosched.c«).

Abbildung 8 überträgt das Beispiel aus Abbildung 5 auf den Deadline-Scheduler. Bei dieser Variante ist die Seek-Distanz kürzer. Außerdem vermeidet der Algorithmus Rückwärtsbewegungen des Schreib-Lese-Kopfes, was sich positiv auf die Seek-Time auswirkt. Die entsprechende Theorie geht davon aus, dass Rückwärtsbewegungen doppelt so aufwändig sind wie gleich weite Vorwärtsbewegungen des Kopfes.

# cat /sys/block/hda/queue/scheduler
[noop] anticipatory deadline cfq

# echo deadline > /sys/block/hda/queue/
  scheduler
# cat /sys/block/hda/queue/scheduler
noop anticipatory [deadline] cfq

# cd /sys/block/hda/queue/iosched/
# ls
fifo_batch  front_merges  read_expire
  write_expire  writes_starved
# cat fifo_batch
16
# echo 8 >fifo_batch
# cat fifo_batch
8

Abbildung 7: Neue Aufträge verwaltet der Scheduler in der »sort_list« nach ihrer Sektornummer, in »fifo_list« nach der Reihenfolge. Beim Unplugging verschiebt er die Aufträge in die Dispatch-Queue und übergibt sie so dem Gerätetreiber. In der Queue sind zuvor getrennte Lese- und Schreibaufträge wieder vereint.

Nicht nur der Algorithmus als solcher, auch die Implementierung ist für Programmierer interessant: Neben doppelt verketteten Listen kommen Red-Black-Trees[4] und Hashfunktionen zum Einsatz. Die doppelt verketteten Listen (»fifo_list«) dienen der Einsortierung nach der Auftragszeit – jeweils eine Liste für Leseaufträge und eine für Schreibaufträge. Red-Black-Trees (»sort_list«) sind optimal für die Sortierung nach der Sektornummer. Dabei verwaltet ebenfalls jeweils ein Tree die Leseaufträge, ein anderer die Schreibaufträge. Die Hashfunktion fasst schließlich die Aufträge zusammen.

Feineinstellung über SysFS

Die Wahl der Algorithmen sorgt für eine weitgehend konstante Laufzeit des Algorithmus – abgesehen vom Einsortieren der Aufträge. Die Red-Black-Trees garantieren allerdings auch hier einen überschaubaren Aufwand mit der Komplexität O(Log N).

Abbildung 8: Der Deadline-IO-Scheduler sortiert die Anfragen der Rechenprozesse. Später eingehende Aufträge werden nicht mehr einsortiert (Darstellung qualitativ).

Der Kasten “IO-Scheduler in Kernel 2.6.10” beschreibt, wie man den Deadline-IO-Scheduler einstellt (siehe auch[2]). Er besitzt folgende Parameter:

• »fifo_batch«: Dieser Parameter legt fest, wie viele
  benachbarte Aufträge der Scheduler in die Dispatch-Queue zur
  Übergabe an den Gerätetreiber übernimmt, wenn die
  Deadline eines Auftrags abgelaufen ist. Standardmäßig
  bilden 16 Aufträge eine Auftragsgruppe (Batch).
• »read_expire«: Der Wert bestimmt die Länge der
  Deadline für Leseaufträge in Millisekunden.
  Standardmäßig beträgt sie 500 Millisekunden.
• »write_expire«: Das Attribut legt die Länge
  der Deadline für Schreibaufträge in Millisekunden fest.
  Standardmäßig sind es fünf Sekunden.
• »writes_starved«: Das Attribut legt fest, wie viele
  Gruppen der Scheduler für Leseaufträge bearbeitet, bevor
  er eine Gruppe Schreibaufträge angeht. Gibt es keine Lese-,
  sondern nur Schreibaufträge, übernimmt er diese nach
  Ablauf der Deadline direkt. Normalerweise verarbeitet er vor einem
  Schreib-Batch zwei Lese-Batches.
• »front_merges«: Dieser Parameter legt fest, ob der
  Deadline-IO-Scheduler überhaupt Frontmerges durchführt.
  Üblicherweise erlaubt man Frontmerges, sodass der Parameter
  von Haus aus den Wert »1« besitzt.

Vorschau

Für jede IO-Scheduling-Strategie wäre es am besten, in die Zukunft schauen zu können. Denn wer die folgenden Lese- und Schreibaufträge kennt, kann am besten entscheiden, wie er mit den aktuellen verfährt. Einen Schritt in diese Richtung macht der Anticipatory-Scheduler, der zu erraten versucht, welche Ordnung der Aufträge am günstigsten ist. Wer erfahren möchte, wie der Anticipatory-Scheduler arbeitet und was ihn vom CFQ-Scheduler unterscheidet, findet alle Details in der kommenden Folge der Kern-Technik. (ofr)