Linux I/O Scheduler

Hinweis: Bitte beachten Sie, dass dieser Artikel / diese Kategorie sich entweder auf ältere Software/Hardware Komponenten bezieht oder aus sonstigen Gründen nicht mehr gewartet wird. Diese Seite wird nicht mehr aktualisiert und ist rein zu Referenzzwecken noch hier im Archiv abrufbar.

Hinweis: Mit Linux Kernel 5.0 wurden die bisherigen unten angeführten Legacy I/O Scheduler aus dem Kernel entfernt. Ab Linux Kernel 5.0 kommt ausschließlich der Linux Multi-Queue Block IO Queueing Mechanism (blk-mq) zum Einsatz.

Im Linux Kernel sind drei verschiedene I/O Scheduler vorhanden: NOOP, Deadline und CFQ. Jeder Scheduler besitzt seinen eigenen Algorithmus, um Requests zu verarbeiten und an den Device Driver für die Abarbeitung zu übergeben. Bis zu Kernel 2.6.33 waren noch vier Scheduler vorhanden, der AS Scheduler ist ab dieser Version jedoch nicht mehr Teil des Kernels. Dieser Artikel gibt einen Überblick über die zur Zeit "aktiven" Scheduler, deren Algorithmen im Linux Kernel als auch Grafiken, die deren Arbeitsweisen visualisieren. Teil des Artikels ist auch, wie ein Scheduler zur Laufzeit ausgewählt werden kann.

Aufgaben eines I/O Schedulers

Das Lesen und Schreiben von Daten von/auf Block Devices ist aus Performance-Sicht eine teure Angelegenheit. Der Zugriff auf Festplatten benötigt aufgrund der Positionierung der Schreib-/Leseköpfe auf den Magnetscheiben mehrere Millisekunden (Seek Time). Es werden daher intelligente Verfahren benötigt, um diese Zeiten möglichst gering zu halten und I/O Requests in bestmöglicher Reihenfolge abzusetzen. Diese Aufgaben des Sortierens und Zusammenführen mehrerer Requests im Linux Kernel übernimmt der I/O Scheduler. Bei High-Performance Solid-State Drives (SSDs) können diese Verfahren allerdings Performance-Nachteile bringen. Daher wurde mit Linux Kernel 3.13 der neue Linux Multi-Queue Block IO Queueing Mechanism (blk-mq) eingeführt, der parallel zum herkömmlichen Linux Block I/O Layer arbeitet.

Grundsätzlich sind im Zusammenhang mit I/O Scheduling beim herkömmlichen Linux Block I/O Layer zwei Queues (Warteschlangen) von Relevanz:

1. Request Queue: In dieser Queue werden die von Prozessen abgesetzten Requests gesammelt, u.U. gemerged und vom Scheduler je nach Scheduling Algorithmus sortiert. Die Scheduler verwenden unterschiedliche Ansätze um die einzelnen Requests zu behandeln und an den Device Driver zu übergeben.
2. Dispatch Queue: Diese Queue beinhaltet die geordneten Requests die bereite für die Abarbeitung am Device sind. Sie wird vom Device Driver verwaltet.

Vorhandene I/O Scheduler

Die I/O Scheduler von Linux finden sich hin und wieder auch unter dem Begriff "Elevator" wieder. Unter der Bezeichnung Elevator wird auch die Dispatch Queue miteinbezogen, der Name "I/O Scheduler" referenziert zumeist immer den schedule-spezifischen Teil. Die beiden Komponenten finden sich auch im Linux Storage Stack Diagramm wieder.

Grafische Darstellung

• 

  Arbeitsweise NOOP Scheduler

• 

  Arbeitsweise Deadline Scheduler

• 

  Arbeitsweise CFQ Scheduler

NOOP

Der NOOP-Scheduler ist ein simpler Scheduler der alle I/O Requests in einer FIFO-Queue sammelt. Request Merging wird durchgeführt, um ein optimales Absetzen der Request zu ermöglichen und unnötige Seek-Times zu vermeiden. Eine Sortierung der Requests findet jedoch nicht statt, der Device Driver arbeitet die Dispatch Queue wiederum nach dem FIFO-Prinzip ab. Der NOOP-Scheduler besitzt keine Einstellungs-Möglichkeiten zur Optimierung ("Tunables").

Deadline

Der Deadline-Scheduler versucht das sogenannte "Verhungern" (Starvation) von Requests zu verhindern. Dazu wird jeder Request mit einer Ablaufzeit (Expiration Time) versehen und in zwei verschiedene Queues gegeben (s. u.). Im schlechtesten Falle sollen Requests nach einer definierten Expiration Time abgearbeitet werden, es wird also versucht eine vorhersagbare Service-Start-Zeit zu garantieren. Read-Requests werden höherwertig behandelt als Write-Requests, sie besitzen daher auch eine kürzere Deadline. Diese Maßnahme ist insofern von Vorteil, da Read-Requests zumeist synchron (blockierend) und Write-Requests asynchron (nicht-blockierend) abgesetzt werden. Die Default-Zeiten für Read-Requests betragen 0.5 Sekunden, für Write 5 Sekunden. Dieser Parameter kann über die Option "read_expire" angepasst werden. Für die Verwaltung der Requests werden zwei Queue-Paare verwendet - jeweils eine Queue für die I/O Vorgänge Read und Write. Jede Direction besitzt eine der folgenden Queue-Arten:

1. Eine nach Sektoren sortierte (seek ordered) Queue - Sorted Queues
2. Eine FIFO Queue (Reihenfolge aufgrund der Deadline) - Deadline Queues.

Auswahl von Requests: Die einzelnen Requests in den Queues werden immer in sogenannten "Batches" abgearbeitet - mehrere Requests werden zusammen an die Dispatch Queue des Device Drivers abgesetzt (Standardmäßig: 16, einstellbar über die Option "fifo_batch"). Während eines Batches wird weder Direction noch Queue gewechselt. Nach jedem Batch wird eine neue Direction gewählt - standardmäßig "Read", auf "Write" wird dann gewechselt, wenn "Write" bereits "writes_starved"-Mal warten musste (default: 2x). Der neue Batch startet mit den Requests mit der frühesten Ablaufzeit aus der FIFO Deadline Queue wenn:

1. Eine Deadline bereits abgelaufen ist.
2. Die Data Direction gewechselt wurde.
3. Der letzte Request bereits der letzte in der Sorted Queue war.

Ansonsten wird der nächste Request der Sorted Queue abgearbeitet (z.B. wenn keine Deadline abgelaufen ist und die Direction nicht gewechselt wurde). Durch diesen Mechanismus wird verhindert, dass einzelne Requests verhungern und für lange Zeit nicht beachtet werden.

CFQ

Der "Completely fair queuing" (CFQ) Scheduler ist der Default-Scheduler des Linux Kernels und setzt sich folgende Ziele:

• Faire Aufteilung der vorhandenen I/O Bandbreite auf Prozesse gleicher Prioritäts-Klassen via Time-Slices. Diese "Fairness" bezieht sich auf die Länge der Time-Slots und nicht auf die Bandbreite, d.h. ein Prozess mit sequentiellen-Writes wird im gleichen Slot eine höhere Bandbreite erzielen als ein Prozess mit random-Writes.
• Die Möglichkeit Prozesse in Prioritäts- bzw. Scheduling-Klassen einzuteilen (z.B. via ionice).
• Periodische Abarbeitung der Prozess-Queues verteilen die Latenz. Die Time-Slots ermöglichen für Prozesse, die viele Requests in ihrem Slot absetzen können eine hohe Bandbreite.

Prioritäts-Klassen (priority classes): CFQ ist bis jetzt der einzige Scheduler, der eine Einteilung der Prozesse in Klassen ermöglicht. Die folgenden Klassen sind verfügbar (in absteigender Priorität):

1. Real-time (RT): RT-Prozesse erhalten immer als Erstes Zugriff auf das Device. RT besitzt 8 Priority Levels (7 bedeutet niedrigste Priorität), die die Priorität innerhalb der RT-Prozesse bestimmen. Da RT-Prozesse andere zum Verhungern bringen könnte, kann nur root diese Klasse für einen Prozess setzen.
2. Best-effort (BE): RT-Prozesse werden immer dann behandelt, wenn keine RTs vorhanden sind. Genau wie RT sind 8 Priority Levels vorhanden.
3. Idle: Wenn RT und BE Queues geleert sind werden Requests aus der Idel Queue abgearbeitet. Unter hoher Last kann es dazu kommen, das Requests verhungern, dennoch ist seit Kernel 2.6.25 diese Klasse für normale User erlaubt (vgl. man ionice (linux.die.net)).

Werden für einen Prozess Klasse und Level nicht explizit gesetzt wird die Klasse "Best-Effort" und der Level über den CPU-nice-Wert ermittelt: io_nice = (cpu_nice + 20) / 5.

Auswahl von Requests: Der Scheduler verwaltet die ankommenden Requests eines Prozesses in mehreren Datenstrukturen. Zum einen gibt es einen RBTree zum anderen wird eine FIFO (Sortierung nach Expiration Time) verwaltet. Im RBTree wird nicht zwischen Read und Write Requests unterschieden, in der FIFO Queue sehr wohl. Hier besitzen Read, Write - respektive synchrone, asynchrone - Requests unterschiedliche Expire Zeiten: "fifo_expire_async" und "fifo_expire_sync" bestimmen die Ablaufzeit. Vom Scheduler wird den Queues eines Prozesses immer ein gewisser Time Slot für die Bearbeitung von Requests zur Verfügung gestellt. In dieser Zeit kann eine maximale Anzahl an Requests vom Prozess gedispatched werden (basierend auf "cfq_quantum"). Besondere Aufmerksamkeit wird auch dem Umstand gewidmet, wenn ein Prozess keine Pending Requests mehr aufzuweisen hat. Unter diesen Umständen wird trotzdem noch eine gewisse Zeit abgewartet (vgl. Tunables).

Tunables:

• slice_idle: Besitzt eine Queue eines Prozesses keinen weiteren Requests mehr, der im aktuellen Slot abgearbeitet werden könnte, wird trotzdem eine bestimmte Zeit im Slot verweilt (idle time). Dies hat den Vorteil, dass bei herkömmlichen Festplatten unnötige Seek-Zeiten vermieden werden, wenn in der Queue noch neue Requests kommen, die aus räumlicher Sicht der Festplatte angrenzend sind. Idling findet jedoch nicht statt wenn die Queue:

1. Expired ist,
2. die Priorität "Idle" besitzt,
3. es sich um eine async Queue handelt,
4. es "close cooperator" (arbeiten nahe am selben Bereich eines Devices) gibt.

Auswahl eines I/O Schedulers

Scheduler ausgewählter Distributionen

Linux Distribution	Default I/O Scheduler
Ubuntu	Deadline (Seit Ubuntu 12.10)
Red Hat Enterprise Linux (RHEL)	Deadline, außer bei SATA Disks

Scheduler wechseln

Seit Linux Kernel 2.6.10 ist es möglich den aktuellen I/O Scheduler zur Laufzeit zu wechseln. Dadurch kann z.B. der default Scheduler nicht verändert werden, für ein bestimmtes Device aber ein anderer ausgewählt werden. Welcher Scheduler zur Zeit aktiv ist, zeigt folgendes Kommando:

:~$ cat /sys/block/sda/queue/scheduler 
noop deadline [cfq]

Der aktive Scheduler ist der in Klammern gesetzte. Um den Scheduler zu wechseln, braucht für ein Device (in diesem Fall sda) nur folgendes durchgeführt werden (root-Rechte werden benötigt):

:~# echo deadline > /sys/block/sda/queue/scheduler
:~# cat /sys/block/sda/queue/scheduler
noop [deadline] cfq

Diese Einstellung ist jedoch nicht persistent und wird bei einem Reboot wieder auf die default Einstellung zurückgesetzt. Um die Einstellungen bezüglich I/O Scheduler permanent zu ändern muss dies bereits zur Boot-Zeit über einen Kernel-Parameter durchgeführt werden. Es muss dazu der Eintrag

elevator=<scheduler>

angehängt werden, wobei <scheduler> entweder noop, cf, deadline oder as (bis Kernel 2.6.33, siehe Git Commit Log) sein kann.

Scheduler für SSDs

Der Deadline Scheduler eignet sich gut für das Zusammenspiel mit SSDs, da er nicht auf das exzessive Mergen von Requests setzt. Vielerorts wird NOOP als bester Scheduler für SSDs angepriesen, da er die Requests einfach an das Device weiter gibt. Aus Performance-Gründen ist das durchaus schlüssig, die Fairness der Scheduler-Zeiten unter Applikationen kann darunter aber leiden.

Auch der CFQ-Scheduler hat mittlerweile Verbesserungen für SSDs erhalten:

• CFQ has some optimizations for SSDs and if it detects a non-rotational media which can support higher queue depth (multiple requests at in flight at a time), then it cuts down on idling of individual queues and all the queues move to sync-noidle tree and only tree idle remains.
• IOPS Modus bei SSDs standardmäßig aktiv (ab Kernel 4.2)

Einzelnachweise

Autor: Georg Schönberger Georg Schönberger, Abteilung DevOps bei der XORTEX eBusiness GmbH, absolvierte an der FH OÖ am Campus Hagenberg sein Studium zum Bachelor Computer- und Mediensicherheit, Studium Master Sichere Informationssysteme. Seit 2015 ist Georg bei XORTEX beschäftigt und arbeitet sehr lösungsorientiert und hat keine Angst vor schwierigen Aufgaben. Zu seinen Hobbys zählt neben Linux auch Tennis, Klettern und Reisen.