Linux カーネルの 4 つの主要な IO スケジューリングアルゴリズムを 1 つの記事で理解する-Linux-php.cn

Linux カーネルには、Noop IO スケジューラ、Anticipatory IO スケジューラ、Deadline IO スケジューラ、CFQ IO スケジューラという 4 種類の IO スケジューラが含まれています。

通常、ディスクの読み取りおよび書き込みの遅延は、ディスクヘッドのシリンダへの移動によって発生します。この遅延を解決するために、カーネルは主に、キャッシュアルゴリズムと IO スケジューリングアルゴリズムという 2 つの戦略を採用します。

スケジューリングアルゴリズムの概念

データのブロックがデバイスに書き込まれるか、デバイスから読み取られると、リクエストは完了を待つキューに入れられます。
各ブロックデバイスには独自のキューがあります。
I/O スケジューラは、メディアをより効率的に利用するためにこれらのキューの順序を維持する責任があります。 I/O スケジューラは、順序付けされていない I/O 操作を順序付けされた I/O 操作に変換します。
スケジュールを設定する前に、カーネルはまずキュー内にリクエストがいくつあるかを判断する必要があります。

IO スケジューラ

IO スケジューラ (IO スケジューラ) は、ブロックデバイス上で IO 操作が送信される順序を決定するためにオペレーティングシステムによって使用される方法です。存在目的は 2 つあり、1 つは IO スループットの向上、もう 1 つは IO 応答時間の短縮です。

ただし、IO スループットと IO 応答時間は矛盾することがよくあります。この 2 つのバランスを可能な限り高めるために、IO スケジューラは、さまざまな IO 要求シナリオに適応するさまざまなスケジューリングアルゴリズムを提供します。その中で、データベースなどのランダムな読み取りおよび書き込みシナリオに最も有益なアルゴリズムは DEANLINE です。

カーネルスタック内の IO スケジューラの場所は次のとおりです:

ブロックデバイスに関して最も悲劇的なのは、非常に時間のかかるプロセスであるディスクのローテーションです。各ブロックデバイスまたはブロックデバイスのパーティションは、独自のリクエストキュー (request_queue) に対応し、各リクエストキューは、送信されたリクエストを調整する I/O スケジューラを選択できます。

I/O スケジューラの基本的な目的は、ブロックデバイス上の対応するセクタ番号に従ってリクエストを配置し、ヘッドの移動を減らし、効率を向上させることです。各デバイスのリクエストキュー内のリクエストは順番に応答されます。

実際には、このキューに加えて、各スケジューラ自体も、送信されたリクエストを処理するために異なる数のキューを維持しており、キューの先頭にあるリクエストは、やがてリクエストキューに移動されます。

IO スケジューラの機能は主に、ディスク回転の必要性を減らすことです。主に 2 つの方法で実現します:

マージ＃＃＃＃＃＃選別＃＃＃＃＃＃
各デバイスには対応する独自のリクエストキューがあり、すべてのリクエストは処理される前にリクエストキューに置かれます。新しいリクエストが来たとき、このリクエストの位置が前のリクエストに隣接していることが判明した場合、そのリクエストを 1 つのリクエストにマージできます。

1、いいえ

FIFO

noop とは何ですか? noop は入出力のスケジューリングアルゴリズムです。NOOP、No Operation. 何もせず、リクエストを 1 つずつ処理します。この方法は実際にはより簡単で効果的です。問題は、ディスクのシークが多すぎることであり、これは従来のディスクでは許容できないことです。ただし、SSD ディスクは回転する必要がないため、SSD ディスクの場合は問題ありません。

noop の別名は、エレベータースケジュールアルゴリズムとも呼ばれます。

noop の原理とは何ですか?

入力リクエストと出力リクエストを FIFO キューに入れ、キュー内の入力リクエストと出力リクエストを順番に実行します。新しいリクエストが来たとき:

マージできる場合はマージしてください
マージできない場合は、並べ替えを試みます。キュー上のリクエストがすでに非常に古い場合、この新しいリクエストはキューに入ることができず、最後に配置することしかできません。それ以外の場合は、適切な位置に挿入します
マージできず、挿入に適した位置がない場合は、リクエストキューの最後に配置されます。
該当シーン

4.1 入力リクエストと出力リクエストの順序を変更したくないシナリオの場合;

4.2 NAS ストレージデバイスなど、入出力においてよりインテリジェントなスケジューリングアルゴリズムを備えたデバイス;

4.3 上位層アプリケーションの入力および出力リクエストは慎重に最適化されています;

4.4 SSDディスクなどの非回転ヘッドディスクデバイス

2. CFQ (完全に公平なキューイング、完全に公平なキューイング)

CFQ (Completely Fair Queuing) アルゴリズムは、その名前が示すように、完全に公平なアルゴリズムです。ブロックデバイスを使用する権利を競合するすべてのプロセスにリクエストキューとタイムスライスを割り当てようとします。スケジューラによってプロセスに割り当てられたタイムスライス内で、プロセスはその読み取りおよび書き込みリクエストを基礎となるブロックデバイスに送信できます。 . プロセスのタイムスライスが消費されたとき完了後、プロセスのリクエストキューは一時停止され、スケジューリングを待ちます。

各プロセスのタイムスライスと各プロセスのキューの長さは、プロセスの IO 優先度によって異なります。各プロセスには IO 優先度があり、CFQ スケジューラはそれを、いつ実行するかを決定するために考慮する要素の 1 つとして使用します。プロセスのリクエストキューはブロックデバイスの使用権を取得できます。

IO の優先順位は、高から低まで 3 つのカテゴリに分類できます。

RT(リアルタイム)
BE(ベストトライ)
IDLE(アイドル)

RT と BE はさらに 8 つのサブ優先度に分類できます。 ionice を通じて表示および変更できます。優先順位が高くなるほど、処理が早くなり、このプロセスに使用されるタイムスライスが増え、一度に処理できるリクエストの数が増えます。

実際、CFQ スケジューラの公平性はプロセスに対するものであり、プロセスには同期リクエスト (読み取りまたは同期書き込み) のみが存在し、それらはプロセス独自のリクエストキューに入れられることはすでにわかっています。同じ優先度のリクエストは、どのプロセスからのものであっても、共通のキューに入れられ、合計 8 (RT) 8 (BE) 1 (IDLE) = 17 の非同期リクエストキューがあります。

Linux 2.6.18 以降、CFQ がデフォルトの IO スケジューリングアルゴリズムとして使用されます。汎用サーバーの場合は、CFQ の方が適しています。使用する具体的なスケジューリングアルゴリズムは、特定のビジネスシナリオに基づく十分なベンチマークに基づいて選択される必要があり、他人の言葉だけで決定することはできません。

3、締切

DEADLINE は CFQ に基づいており、IO リクエストの枯渇という極端な状況を解決します。

CFQ 自体が持つ IO ソートキューに加えて、DEADLINE は読み取り IO と書き込み IO 用の FIFO キューをさらに提供します。

FIFO キューの読み取りの最大待ち時間は 500 ミリ秒、FIFO キューの書き込みの最大待ち時間は 5 秒です (もちろん、これらのパラメーターは手動で設定できます)。

FIFO キュー内の IO リクエストの優先度は CFQ キュー内の IO リクエストよりも高く、読み取り FIFO キューの優先度は書き込み FIFO キューの優先度よりも高くなります。優先度は次のように表現できます:

#「」
FIFO(読み取り) > FIFO(書き込み) > CFQ

」

#デッドラインアルゴリズムは、特定の IO リクエストの最小遅延時間を保証します。この点を理解すると、DSS アプリケーションに非常に適していることがわかります。

deadline は実際にはエレベーターの改善です:

\1. 長時間処理できないリクエストは避けてください。

\2. 読み取り操作と書き込み操作を別の方法で扱います。

deadline IO は 3 つのキューを維持します。最初のキューはエレベーターと同じで、物理的な位置に従って並べ替えようとします。 2 番目のキューと 3 番目のキューはどちらも時間によってソートされていますが、違いは、一方が読み取り操作であり、もう一方が書き込み操作であることです。

Deadline IO では、読み取りと書き込みが区別されます。これは、アプリケーションが読み取りリクエストを送信すると、通常はそこでブロックされ、結果が返されるまで待機すると設計者が考えているためです。通常、書き込みリクエストはメモリに書き込むアプリケーションのリクエストではなく、バックグラウンドプロセスによってディスクに書き戻されます。通常、アプリケーションは書き込みが完了するまで待機せずに続行します。したがって、読み取りリクエストは書き込みリクエストよりも優先される必要があります。

この設計では、各新しいリクエストは最初に最初のキューに配置されます。アルゴリズムはエレベーターのアルゴリズムと同じで、読み取りまたは書き込みキューの最後にも追加されます。このようにして、最初のキューのいくつかのリクエストを処理すると同時に、2 番目/3 番目のキューの最初のいくつかのリクエストが長時間待機していないかどうかを検出し、しきい値を超えている場合は処理されます。このしきい値は、読み取りリクエストの場合は 5 ミリ秒、書き込みリクエストの場合は 5 秒です。

個人的には、Oracle のオンラインログ、mysql の binlog などのデータベース変更ログの記録には、この種のパーティションを使用しない方がよいと思います。このタイプの書き込みリクエストは通常 fsync を呼び出すためです。書き込みが完了できない場合、アプリケーションのパフォーマンスにも大きな影響を与えます。

4、予想的

CFQ と DEADLINE の焦点は、分散した IO リクエストを満たすことです。連続読み取りなどの連続 IO リクエストの場合、最適化は行われません。

ランダム IO とシーケンシャル IO が混在するシナリオに対応するために、Linux は ANTICIPATORY スケジューリングアルゴリズムもサポートしています。 DEADLINE に基づいて、ANTICIPATORY は各読み取り IO に 6 ミリ秒の待機時間ウィンドウを設定します。 OS がこの 6ms 以内に隣接する場所から読み取り IO 要求を受信した場合、即座に応答できます。

＃＃＃＃＃＃まとめ＃＃＃＃＃＃

IO スケジューラアルゴリズムの選択は、ハードウェアの特性とアプリケーションシナリオの両方に依存します。

従来の SAS ディスクでは、CFQ、DEADLINE、および ANTICIPATORY はすべて適切な選択肢ですが、専用データベースサーバーの場合、DEADLINE のスループットと応答時間は良好に機能します。

ただし、SSD や Fusion IO などの新興ソリッドステートドライブでは、最も単純な NOOP が最適なアルゴリズムである可能性があります。他の 3 つのアルゴリズムの最適化はシーク時間の短縮に基づいており、ソリッドステートドライブにはいわゆるシーク時間、チャネル時間と IO 応答時間は非常に短いです。

以上がLinux カーネルの 4 つの主要な IO スケジューリングアルゴリズムを 1 つの記事で理解するの詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。