Verstehen Sie die vier wichtigsten IO-Planungsalgorithmen des Linux-Kernels in einem Artikel

Der Linux-Kernel enthält 4 Arten von IO-Schedulern, nämlich Noop IO-Scheduler, Anticipatory IO-Scheduler, Deadline IO-Scheduler und CFQ IO-Scheduler.

Normalerweise werden Lese- und Schreibverzögerungen auf der Festplatte dadurch verursacht, dass sich der Kopf zum Zylinder bewegt. Um diese Verzögerung zu beheben, wendet der Kernel hauptsächlich zwei Strategien an: Caching- und E/A-Planungsalgorithmen.

Konzept des Planungsalgorithmus

1. Wenn ein Datenblock auf das Gerät geschrieben oder davon gelesen wird, wird die Anforderung in eine Warteschlange gestellt, die auf den Abschluss wartet.
2. Jedes Blockgerät verfügt über eine eigene Warteschlange.
3. Der I/O-Planer ist dafür verantwortlich, die Reihenfolge dieser Warteschlangen aufrechtzuerhalten, um die Medien effizienter zu nutzen. Der I/O-Scheduler wandelt ungeordnete I/O-Vorgänge in geordnete I/O-Vorgänge um.
4. Vor der Planung muss der Kernel zunächst ermitteln, wie viele Anforderungen sich in der Warteschlange befinden.

IO-Planer

IO Scheduler (IO Scheduler) ist die Methode, mit der das Betriebssystem die Reihenfolge der Übermittlung von IO-Vorgängen auf Blockgeräten bestimmt. Es gibt zwei Existenzzwecke: Der eine besteht darin, den E/A-Durchsatz zu verbessern, und der andere darin, die E/A-Antwortzeit zu verkürzen.

Allerdings sind IO-Durchsatz und IO-Antwortzeit oft widersprüchlich. Um beides so gut wie möglich auszubalancieren, bietet der IO-Scheduler eine Vielzahl von Planungsalgorithmen zur Anpassung an verschiedene IO-Anfrageszenarien. Unter diesen ist DEANLINE der vorteilhafteste Algorithmus für zufällige Lese- und Schreibszenarien wie Datenbanken.

Der Speicherort des IO-Schedulers im Kernel-Stack ist wie folgt:

Das Tragischste an Blockgeräten ist die Festplattenrotation, die ein sehr zeitaufwändiger Prozess ist. Jedes Blockgerät oder jede Partition eines Blockgeräts entspricht seiner eigenen Anforderungswarteschlange (request_queue), und jede Anforderungswarteschlange kann einen E/A-Planer auswählen, um die übermittelten Anforderungen zu koordinieren.

Der Hauptzweck des I/O-Schedulers besteht darin, Anfragen entsprechend ihren entsprechenden Sektornummern auf dem Blockgerät anzuordnen, um Kopfbewegungen zu reduzieren und die Effizienz zu verbessern. Anfragen in der Anfragewarteschlange jedes Geräts werden der Reihe nach beantwortet.

Tatsächlich unterhält jeder Planer selbst zusätzlich zu dieser Warteschlange eine unterschiedliche Anzahl von Warteschlangen zur Verarbeitung übermittelter Anforderungen, und die Anforderung an der Spitze der Warteschlange wird zu gegebener Zeit in die Anforderungswarteschlange verschoben, um auf eine Antwort zu warten.

Die Hauptfunktion des IO-Planers besteht darin, den Bedarf an Festplattenrotation zu reduzieren. Wird hauptsächlich auf zwei Arten erreicht:

1. Zusammenführen
2. Sortieren

Jedes Gerät verfügt über eine eigene entsprechende Anforderungswarteschlange und alle Anforderungen befinden sich vor der Verarbeitung in der Anforderungswarteschlange. Wenn eine neue Anfrage eingeht und festgestellt wird, dass der Standort dieser Anfrage an eine vorherige Anfrage angrenzt, kann sie zu einer Anfrage zusammengeführt werden.

Wenn die zusammengeführte Datei nicht gefunden werden kann, wird sie nach der Drehrichtung der Festplatte sortiert. Normalerweise besteht die Aufgabe des E/A-Schedulers darin, zusammenzuführen und zu sortieren, ohne die Verarbeitungszeit einer einzelnen Anfrage zu sehr zu beeinträchtigen.

1、NOOP

FIFO

1. Was ist Noop? Noop ist ein Eingabe- und Ausgabeplanungsalgorithmus, No Operation. Diese Methode ist tatsächlich einfacher und effektiver. Das Problem besteht darin, dass zu viele Festplattensuchen durchgeführt werden, was für herkömmliche Festplatten nicht akzeptabel ist. Für SSD-Festplatten ist dies jedoch in Ordnung, da SSD-Festplatten nicht rotieren müssen.
2. Ein anderer Name für Noop ist auch der Aufzugsplanungsalgorithmus.
3. Was ist das Prinzip von Noop?

Stellen Sie die Eingabe- und Ausgabeanforderungen in eine FIFO-Warteschlange und führen Sie dann die Eingabe- und Ausgabeanforderungen in der Warteschlange in der folgenden Reihenfolge aus: Wenn eine neue Anforderung eingeht:

1. Wenn es zusammengeführt werden kann, führen Sie es zusammen

2. Wenn es nicht zusammengeführt werden kann, wird versucht, es zu sortieren. Wenn die Anfragen in der Warteschlange bereits sehr alt sind, kann diese neue Anfrage nicht in die Warteschlange springen und nur am Ende platziert werden. Andernfalls fügen Sie es an der entsprechenden Position ein

3. Wenn es nicht zusammengeführt werden kann und keine geeignete Position zum Einfügen vorhanden ist, wird es am Ende der Anforderungswarteschlange platziert.

4. Anwendbare Szenarien

   4.1 In Szenarien, in denen Sie die Reihenfolge der Eingabe- und Ausgabeanforderungen nicht ändern möchten;

   4.2 Geräte mit intelligenteren Planungsalgorithmen für Ein- und Ausgabe, wie z. B. NAS-Speichergeräte
   4.3 Die Eingabe- und Ausgabeanforderungen der Oberschichtanwendung wurden sorgfältig optimiert
   4.4 Festplattengeräte mit nicht rotierendem Kopf, wie z. B. SSD-Festplatten

2. CFQ (Completely Fair Queuing, völlig faires Anstehen) Der

CFQ-Algorithmus (Completely Fair Queuing) ist, wie der Name schon sagt, ein absolut fairer Algorithmus. Es wird versucht, allen Prozessen, die um das Recht zur Nutzung des Blockgeräts konkurrieren, eine Anforderungswarteschlange und eine Zeitscheibe zuzuweisen. Innerhalb der dem Prozess vom Scheduler zugewiesenen Zeitscheibe kann der Prozess seine Lese- und Schreibanforderungen an das zugrunde liegende Blockgerät senden . Wenn die Zeitscheibe des Prozesses verbraucht ist. Nach Abschluss wird die Anforderungswarteschlange des Prozesses angehalten und wartet auf die Planung.

Der Zeitabschnitt jedes Prozesses und die Warteschlangenlänge jedes Prozesses hängen von der E/A-Priorität des Prozesses ab. Jeder Prozess hat eine E/A-Priorität, und der CFQ-Scheduler verwendet diese als einen der zu berücksichtigenden Faktoren, um den Prozess zu bestimmen. Wenn die Anforderungswarteschlange das Recht erhält, das Blockgerät zu verwenden.

IO-Prioritäten können in drei Kategorien von hoch nach niedrig unterteilt werden:

RT (Echtzeit)

SEIN (am besten versuchen)
IDLE(Leerlauf)

RT und BE können weiter in 8 Unterprioritäten unterteilt werden. Sie können es über ionice anzeigen und ändern. Je höher die Priorität, desto früher erfolgt die Bearbeitung, desto mehr Zeitscheiben werden für diesen Vorgang benötigt und desto mehr Anfragen können gleichzeitig bearbeitet werden.

Tatsächlich wissen wir bereits, dass die Fairness des CFQ-Schedulers für den Prozess gilt und nur synchrone Anforderungen (Lesen oder Syn-Schreiben) für den Prozess vorhanden sind. Sie werden in die eigene Anforderungswarteschlange des Prozesses gestellt und alle asynchronen Anforderungen mit Unabhängig vom Prozess werden sie mit der gleichen Priorität in eine gemeinsame Warteschlange gestellt. Es gibt insgesamt 8 (RT) + 8 (BE) + 1 (IDLE) = 17 asynchrone Anforderungswarteschlangen.

Ab Linux 2.6.18 wird CFQ als Standard-IO-Planungsalgorithmus verwendet. Für Allzweckserver ist CFQ die bessere Wahl. Der zu verwendende spezifische Planungsalgorithmus muss auf der Grundlage ausreichender Benchmarks ausgewählt werden, die auf bestimmten Geschäftsszenarien basieren, und kann nicht allein durch die Worte anderer Personen entschieden werden.

3.FRIST

DEADLINE löst die extreme Situation des IO-Anfragehungers basierend auf CFQ.

Zusätzlich zur IO-Sortierwarteschlange, über die CFQ selbst verfügt, stellt DEADLINE zusätzlich FIFO-Warteschlangen für Lese-IO und Schreib-IO bereit.

Die maximale Wartezeit zum Lesen der FIFO-Warteschlange beträgt 500 ms und die maximale Wartezeit zum Schreiben der FIFO-Warteschlange beträgt 5 s (natürlich können diese Parameter manuell eingestellt werden).

Die Priorität der E/A-Anforderungen in der FIFO-Warteschlange ist höher als die in der CFQ-Warteschlange, und die Priorität der Lese-FIFO-Warteschlange ist höher als die Priorität der Schreib-FIFO-Warteschlange. Priorität kann wie folgt ausgedrückt werden:

“

FIFO (Lesen) > FIFO (Schreiben) > CFQ

“

Der Fristalgorithmus garantiert die minimale Verzögerungszeit für eine bestimmte E/A-Anfrage. Aus diesem Grund sollte er für DSS-Anwendungen sehr gut geeignet sein.

Deadline ist eigentlich eine Verbesserung gegenüber Elevator:

1. Vermeiden Sie einige Anfragen, die nicht zu lange bearbeitet werden können.

2. Unterscheiden Sie zwischen Lesevorgängen und Schreibvorgängen.

deadline IO unterhält 3 Warteschlangen. Die erste Warteschlange ist die gleiche wie bei Elevator und versucht, nach physischem Standort zu sortieren. Die zweite und die dritte Warteschlange sind beide nach Zeit sortiert. Der Unterschied besteht darin, dass es sich bei der einen um eine Leseoperation und bei der anderen um eine Schreiboperation handelt.

Deadline IO unterscheidet zwischen Lesen und Schreiben, da der Designer davon ausgeht, dass die Anwendung, wenn sie eine Leseanforderung sendet, im Allgemeinen dort blockiert und wartet, bis das Ergebnis zurückgegeben wird. Die Schreibanforderung ist normalerweise nicht die Anforderung der Anwendung, in den Speicher zu schreiben, und der Hintergrundprozess schreibt sie dann zurück auf die Festplatte. Bei Bewerbungen wird in der Regel nicht abgewartet, bis das Schreiben abgeschlossen ist, bevor mit dem Fortfahren fortgefahren wird. Daher sollten Leseanfragen eine höhere Priorität haben als Schreibanfragen.

Bei diesem Design wird jede neue Anfrage zuerst in die erste Warteschlange gestellt. Der Algorithmus ist der gleiche wie der von Elevator und wird auch am Ende der Lese- oder Schreibwarteschlange hinzugefügt. Auf diese Weise verarbeiten wir zunächst einige Anfragen aus der ersten Warteschlange und erkennen gleichzeitig, ob die ersten paar Anfragen in der zweiten/dritten Warteschlange zu lange gewartet haben. Wenn sie einen Schwellenwert überschritten haben, werden sie verarbeitet. Dieser Schwellenwert beträgt 5 ms für Leseanfragen und 5 s für Schreibanfragen.

Persönlich denke ich, dass es am besten ist, diese Art von Partition nicht zum Aufzeichnen von Datenbankänderungsprotokollen zu verwenden, wie z. B. das Online-Protokoll von Oracle, das Binlog von MySQL usw. Denn diese Art von Schreibanforderung ruft normalerweise fsync auf. Wenn das Schreiben nicht abgeschlossen werden kann, wirkt sich dies auch stark auf die Anwendungsleistung aus.

4. VORAUSSICHTEND

CFQ und DEADLINE konzentrieren sich auf die Erfüllung verstreuter IO-Anfragen. Für kontinuierliche IO-Anfragen, wie z. B. sequentielles Lesen, gibt es keine Optimierung.

Um dem Szenario gemischter zufälliger E/A und sequentieller E/A gerecht zu werden, unterstützt Linux auch den ANTICIPATORY-Planungsalgorithmus. Basierend auf DEADLINE legt ANTICIPATORY ein Wartezeitfenster von 6 ms für jeden Lese-IO fest. Wenn das Betriebssystem innerhalb dieser 6 ms eine Lese-E/A-Anfrage von einem benachbarten Standort erhält, kann diese sofort erfüllt werden.

Zusammenfassung

Die Wahl des IO-Scheduler-Algorithmus hängt sowohl von den Hardwareeigenschaften als auch von den Anwendungsszenarien ab.

Auf herkömmlichen SAS-Festplatten sind CFQ, DEADLINE und ANTICIPATORY eine gute Wahl; für dedizierte Datenbankserver bietet DEADLINE eine gute Leistung in Bezug auf Durchsatz und Antwortzeit.

Bei neuen Solid-State-Laufwerken wie SSD und Fusion IO ist jedoch möglicherweise der einfachste NOOP der beste Algorithmus, da die Optimierung der anderen drei Algorithmen auf der Verkürzung der Suchzeit basiert und Solid-State-Laufwerke keine so- Dies wird als Suchzeit bezeichnet. Und die E/A-Reaktionszeit ist sehr kurz.

Das obige ist der detaillierte Inhalt vonVerstehen Sie die vier wichtigsten IO-Planungsalgorithmen des Linux-Kernels in einem Artikel. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!