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

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

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

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

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

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. マージ＃＃＃＃＃＃ 選別＃＃＃＃＃＃
2. 各デバイスには対応する独自のリクエスト キューがあり、すべてのリクエストは処理される前にリクエスト キューに置かれます。新しいリクエストが来たとき、このリクエストの位置が前のリクエストに隣接していることが判明した場合、そのリクエストを 1 つのリクエストにマージできます。
マージが見つからない場合は、ディスクの回転方向に従ってソートされます。通常、IO スケジューラの役割は、単一リクエストの処理時間にあまり影響を与えずにマージとソートを実行することです。

1、いいえ

FIFO

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

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

1. マージできる場合はマージしてください

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

3. マージできず、挿入に適した位置がない場合は、リクエスト キューの最後に配置されます。

4. 該当シーン

   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 サイトの他の関連記事を参照してください。