Open Source im professionellen Einsatz
Linux-Magazin 04/2005

Kernel- und Treiberprogrammierung mit dem Kernel 2.6 - Folge 20

Kern-Technik

,

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.

567

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.

Linux-Magazin kaufen

Einzelne Ausgabe
 
Abonnements
 
TABLET & SMARTPHONE APPS
Bald erhältlich
Get it on Google Play

Deutschland

Ähnliche Artikel

  • Kern-Technik

    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.

  • Die Reihenfolge zählt

    Die Leistungsentfaltung von Betriebssystemen hängt entscheidend von der Performance und der Strategie des Schedulers ab, der die Prozessliste führt und lauffähigen Prozessen die CPU scheibchenweise zuteilt. Der Scheduler des Kernels 2.6 ist komplett umgeschrieben und erfüllt die Anforderungen in nachweisbar hohem Maße. Timo Hönig

  • Quellenschutz

    Linux hat sich als Betriebssystem für Embedded-Geräte längst etabliert - nicht zuletzt, weil die Hersteller von der Vorarbeit der Community profitieren und Entwicklungszeit sparen. Doch manche Firmen nehmen die GPL nicht allzu genau und erschweren den Zugang zu den Quellen.

  • Kern-Technik

    Der Blockdevice-Layer ist das Arbeitspferd bei Linux, was die Datenbeschaffung angeht - von der Festplatte bis zur Anwendung ist es ein langer Weg. Der I/O-Scheduler behält dabei den Überblick.

comments powered by Disqus

Stellenmarkt

Artikelserien und interessante Workshops aus dem Magazin können Sie hier als Bundle erwerben.