締め切りスケジューラ

Deadline は、Linux カーネル用のI/O スケジューラ、またはディスク スケジューラです。2002 年にJens Axboeによって作成されました。

デッドラインスケジューラの主な目的は、要求の開始サービス時間を保証することです。^{[1]スケジューラは、}要求の枯渇を防ぐためにすべてのI/O操作に期限を課します。2つのデッドラインキューとソートされたキュー（読み取りと書き込みの両方）を維持します。デッドラインキューは有効期限でソートされ、ソートされたキューはセクター番号でソートされます。

Deadline は、次のリクエストを処理する前に、どのキューを使用するかを決定します。プロセスは通常、読み取り操作をブロックするため、読み取りキューには高い優先順位が与えられます。次に、Deadline は、期限キューの最初のリクエストが期限切れになっているかどうかを確認します。期限が切れていない場合、スケジューラは、ソートされたキューからリクエストのバッチを処理します。どちらの場合も、スケジューラは、ソートされたキューで選択されたリクエストに続くリクエストのバッチも処理します。

デフォルトでは、読み取り要求の有効期限は 500 ミリ秒、書き込み要求の有効期限は 5 秒です。

スケジューラのラフバージョンは、2002年1月にAxboeによってLinuxカーネルメーリングリストに公開されました。 ^[2]

測定によれば、デッドラインI/Oスケジューラは、特定のマルチスレッドワークロードに対してCFQ I/Oスケジューラよりも優れたパフォーマンスを発揮することが示されています。^[3]

Deadline は、セクター番号の増加順に並べられた操作のセットである「バッチ」の概念を通じて I/O 操作 (IOP) を実行します。この調整可能値は、要求がディスクにキューイングされる前にバッチがどのくらいの大きさになる必要があるかを決定します (現在構築されているバッチの有効期限が切れている場合を除く)。バッチが小さいほど、新しい要求が早く実行されるため (より多くの要求が来るのを待つ可能性よりも)、待ち時間を減らすことができます。それでも、ドライブ ヘッドの全体的な動きが増えるため、全体的なスループットが低下する可能性があります (シーケンスはバッチ間で行われるのではなく、バッチ内で行われるため)。さらに、IOP の数が十分に大きい場合、バッチはいずれにしてもタイムリーに実行されます。

「read_expire」時間は、読み取り要求が「期限切れ」とみなされるまでの最大時間（ミリ秒単位）です。読み取り要求は有効期限前に使用するのが最適です。Deadline は、すべての I/O が有効期限前に発行されるようにはしません。ただし、I/O が有効期限を過ぎている場合は、優先されます。

読み取り期限切れキューは、Deadline が読み取りキューを再評価するときにのみチェックされます。読み取り要求の場合、これはソートされた読み取り要求がディスパッチされることを意味します (ストリーミング I/O の場合を除く)。スケジューラが読み取りキューから I/O をストリーミングしている間、期限切れの読み取りは評価されません。期限切れの読み取りがある場合、最初の読み取りが FIFO から取得されます。この期限切れの読み取りが、読み取りソート順序の新しい中心となることに注意してください。キャッシュされた次のポインターは、この期限切れの I/O の後のソート キューからの次の I/O を指すように設定されます...。注意すべき点は、アルゴリズムが有効期限を過ぎたすべての期限切れの I/O を単に実行するわけではないことです。これにより、期限切れの読み取りキューを再度チェックする前に、「write_starved」ソート読み取りをまとめてバッチ処理することで、ある程度の妥当なパフォーマンスを維持できます。

読み取り期限切れ I/O 間で実行できる I/O の最大数は、2 * 'fifo_batch' * 'writes_starved' です。最初の期限切れ読み取り I/O の後に 1 セットの 'fifo_batch' ストリーミング読み取りが行われ、このストリームが書き込み不足状態を引き起こした場合は、別の 'fifo_batch' ストリーミング書き込みが行われる可能性があります。これは最悪のケースであり、その後、読み取り期限切れキューが再評価されます。最良の場合、期限切れ読み取りキューは、書き込みキューが使用されるためスキップされる前に、連続して 'write_starved' 回評価されます。

「write_expire」は read_expire と同じ機能を持ちますが、書き込み操作に使用されます (読み取り要求とは別のバッチにグループ化されます)。

Deadline は読み取り要求を書き込み要求よりも優先するため、実行される操作がほぼすべて読み取り要求になる状況につながる可能性があります。write_expire が長くなったり、全体の帯域幅が飽和状態に近づいたりすると、これはより重要な調整可能項目になります。この値を下げると、読み取り操作を犠牲にして書き込みの帯域幅が (相対的に) 増加します。ただし、アプリケーションのワークロードが読み取り中心で (ほとんどの HTTP サーバーやディレクトリ サーバーなど)、書き込みはたまにしか行われない場合は、この値を上げることで平均 IOP のレイテンシを短縮できます (書き込みバッチがディスクにキューイングされる前に、より多くの読み取りを実行する必要があります)。

「フロント マージ」とは、I/O スケジューラが、より小さなリクエストをより少ない (より大きな) 操作に凝縮 (または「マージ」) しようとする操作です。新しい操作を取得してからアクティブ バッチを調べ、開始セクターが別の操作の開始セクターと同じか、その直後である操作を見つけようとします。「バック マージ」はその逆で、アクティブ バッチの終了セクターを検索して、現在の操作の開始セクターと同じか、その直後であるセクターを探します。マージにより、現在のバッチからアクティブ バッチに操作が転送され、「公平性」が低下してスループットが向上します。

ファイルの一般的なレイアウト方法により、バックマージはフロントマージよりもはるかに一般的です。一部のワークロードでは、フロントマージ要求を試行する際に時間が無駄になる場合があります。 'front_merges' を 0 に設定すると、この機能は無効になります。キャッシュされた 'last_merge' ヒントによりフロントマージが引き続き発生する可能性がありますが、基本的にコストがかからないため、引き続き実行されます。このブール値は、I/O スケジューラのマージ関数が呼び出されたときにフロントセクターのルックアップを無効にするだけです。ディスクマージの合計は、ブロックデバイスごとに '/proc/diskstats' に記録されます。^[1]

• CFQスケジューラ
• 予測スケジューラ
• Noop スケジューラ