I/Oスケジューリング

入出力（I/O）スケジューリングとは、コンピュータのオペレーティングシステムが、ストレージボリュームへの入出力操作をどの順序で実行するかを決定するために使用する方法です。I/Oスケジューリングは、ディスクスケジューリングと呼ばれることもあります。

I/Oスケジューリングは通常、ハードディスクドライブを扱う必要があり、ディスクヘッドの現在位置から遠く離れた場所にあるリクエストへのアクセスには長い時間がかかります（この操作はシークと呼ばれます）。システムパフォーマンスへの影響を最小限に抑えるため、ほとんどのI/Oスケジューラは、 ランダムに順序付けられた受信リクエストを並べ替えるエレベーターアルゴリズムの変種を実装し、ヘッドの移動を最小限に抑えて関連データにアクセスできるようにします。

I/Oスケジューラは、目的に応じてさまざまな用途に使用できます。一般的な用途には、以下のようなものがあります。

• ハードディスクのシークによる時間の浪費を最小限に抑えるため
• 特定のプロセスのI/O要求を優先する
• ディスク帯域幅を各実行プロセスに分配する
• 特定の期限前に特定のリクエストが確実に発行されるようにするため

一般的なスケジューリング手法には、以下のようなものがあります。

• ランダムスケジューリング（RSS）
• 先入れ先出し（FIFO）、別名先着順（FCFS）
• 後入先出法（LIFO）
• 最短シーク優先（最短シーク/サービス時間優先（SSTF）とも呼ばれる）
• エレベーターアルゴリズム（SCANとも呼ばれる。C-SCAN、LOOK、C-LOOKなどの派生形を含む）
• Nステップスキャン：一度にN個のレコードをスキャンします。
• FSCAN、NステップSCAN（NはSCANサイクルの開始時のキューサイズに等しい）
• mClockスケジューラ^{[ 2 ]}
• Linuxカーネルでは：
  • 予測的（2032年6月2日まで）
  • noop（4.20まで）🠊 none（4.11以降）
  • 締め切り（4月20日まで）🠊 mq-deadline（4月11日以降）
  • cfq (完全公平キューイング) (4.20まで) 🠊 bfq (予算公平キューイング) (4.12以降) ^{[ 3 ] [ 4 ]}
  • kyber (4.12以降) ^{[ 5 ] [ 6 ]}

• タグ付きコマンドキューイング（TCQ）
• ネイティブコマンドキューイング（NCQ）

• Linuxカーネルドキュメント：ブロックサブシステム
• LinuxのI/Oスケジューラ（Ubuntu Wikiより）
• オペレーティングシステム：3つの簡単なステップ（Remzi H. Arpaci-Dusseau、Andrea C. Arpaci-Dusseau著、Arpaci-Dusseau Books、2014年）。関連章：ハードディスクドライブ
• Love, R. ( 2005). Linuxカーネル開発、Novell Press。ISBN 0-672-32720-1
• オペレーティングシステム：内部構造と設計原理、第7版、ウィリアム・スタリングス著。

• ウィキメディア・コモンズにあるI/Oスケジューリング関連のメディア