スケジューリング

計算機科学におけるスケジューリング

計算機科学におけるスケジューリングは、システム資源（プロセッサ時間、通信帯域など）へのアクセスを管理し、スレッド、プロセス、およびデータフローの実行順序を決定する重要なプロセスです。このプロセスは、システムを効率的に運用し、ユーザーのニーズに応じたサービス品質を保証するために不可欠です。

スケジューリングの概要

スケジューリングの主な目的は、システムのリソースを最大限に活用し、ユーザーが求めるサービス品質（QoS）を維持することです。具体的には、以下の点が考慮されます。

スループット: 単位時間あたりに完了するプロセスの総数。スループットを最大化することは、システム全体の効率を高める上で重要です。
レイテンシ: 要求が送信されてから最初の応答が生成されるまでの時間。レイテンシを最小化することで、システムはより迅速にユーザーの操作に反応できます。
ターンアラウンド: プロセスの開始から完了までの総時間。ターンアラウンド時間を短縮することで、ユーザーはタスクをより早く完了できます。
応答時間: 要求から最初の応答までの時間。応答時間を短縮することで、ユーザーの待ち時間が減り、快適な操作感を得られます。
公平性: すべてのプロセスにCPU時間を平等に割り当てること。これにより、特定のプロセスが他のプロセスよりも著しく不利になる状況を回避できます。

これらの目標はしばしば相反するため、スケジューリングアルゴリズムはこれらの間でバランスを取る必要があります。また、リアルタイムシステムでは、プロセスの時間制限（デッドライン）を守ることが非常に重要であり、スケジューリングはシステムの安定性を保つ上で不可欠な役割を果たします。

スケジューラの分類

スケジューラは、その機能が実行される頻度に基づいて、長期スケジューラ、中期スケジューラ、および短期スケジューラの3つのタイプに分類されます。

長期スケジューラ

長期スケジューラは、どのジョブやプロセスを実行可能キューに入れるかを決定します。これは、システム内でどのプロセスを同時に実行するかを制御し、システム全体の並列度を決定する上で重要な役割を果たします。リアルタイムオペレーティングシステム（RTOS）では、長期スケジューラはシステムの応答時間を保証するために、実行するプロセス数を制限することがあります。また、大規模なバッチ処理システムやスーパーコンピュータでは、長期スケジューラはジョブ管理システムとして機能し、システムのリソースを最適に割り当てます。

中期スケジューラ

中期スケジューラは、仮想記憶システムにおいて、プロセスを主記憶から二次記憶（ディスク）へ一時的に退避（スワップアウト）、またはその逆（スワップイン）を行う役割を担います。これは、メモリ不足を解消し、システム全体のパフォーマンスを維持するために不可欠です。中期スケジューラは、長期間ブロックされているプロセスや優先度の低いプロセスをスワップアウトし、他のプロセスが使用できるようにメモリを確保します。

短期スケジューラ

短期スケジューラ（CPUスケジューラ）は、実行可能な状態にあるプロセスの中から、次にCPUを割り当てるプロセスを決定します。この決定は、クロック割り込み、I/O割り込み、システムコールなど、様々なイベントによってトリガーされます。短期スケジューラは、最も頻繁に実行されるスケジューラであり、システムの応答時間に直接的な影響を与えます。プリエンプティブなスケジューラでは、プロセスが実行中に中断され、別のプロセスにCPUが割り当てられることがありますが、非プリエンプティブなスケジューラでは、実行中のプロセスが自発的にCPUを解放するまで、別のプロセスにCPUが割り当てられることはありません。

ディスパッチャ

ディスパッチャは、短期スケジューラによって選択されたプロセスにCPUの制御を渡す役割を担います。ディスパッチャは、コンテキストスイッチを行い、ユーザーモードに切り替え、プログラムの実行を再開するために必要な操作を行います。ディスパッチの効率はシステムのパフォーマンスに直接影響するため、ディスパッチャは性能が重視されます。ディスパッチャがプロセスを切り替えるのにかかる時間は、ディスパッチレイテンシと呼ばれます。

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

スケジューリングアルゴリズムは、リソースをどのように分配するかを決定する一連の規則です。以下にいくつかの一般的なアルゴリズムを紹介します。

FIFO (First-In, First-Out): 到着順にプロセスを処理する最も単純なアルゴリズムです。実装が容易ですが、長いプロセスがCPUを独占する可能性があり、ターンアラウンド時間が長くなることがあります。
最小残余時間優先 (SRT): 残り処理時間が最も短いプロセスを優先するアルゴリズムです。スループットを最大化しますが、プロセスの処理時間を正確に見積もる必要があります。また、より短いプロセスが到着すると、実行中のプロセスが中断されるため、コンテキストスイッチのオーバーヘッドが増加します。
固定優先度プリエンプティブ・スケジューリング (FPPS): 各プロセスに固定の優先度を与え、高優先度のプロセスを優先するアルゴリズムです。デッドラインを考慮できますが、低優先度のプロセスがスタベーションに陥る可能性があります。
ラウンドロビン・スケジューリング: 各プロセスに一定のCPU時間を割り当て、順に実行するアルゴリズムです。公平性を保つことができますが、コンテキストスイッチのオーバーヘッドが大きくなることがあります。
多段キュースケジューリング: 複数のキューを用意し、プロセスをフォアグラウンド（対話型）とバックグラウンド（バッチ）などのグループに分けて、グループごとに異なるスケジューリングポリシーを適用するアルゴリズムです。

その他のスケジューリング

通信ネットワーク: パケット交換ネットワークでは、FIFOキューがスケジューリングアルゴリズムの基本となります。他にも、ラウンドロビン、均等化キューイング、比例公平スケジューリングなどがあります。
I/Oスケジューリング: ディスクのアームやヘッドの移動時間を最小化するスケジューリング方式には、FIFO、Shortest Seek First、Elevator Algorithmなどがあります。

OSにおけるスケジューリングアルゴリズムの選択

オペレーティングシステム（OS）の設計では、用途に最適なスケジューリングアルゴリズムを選択することが重要です。単一の最適なアルゴリズムは存在せず、多くのOSでは複数のアルゴリズムを組み合わせたり、拡張したりして使用しています。例えば、Windows NT/XP/Vistaは、固定優先度プリエンプティブ・スケジューリングとラウンドロビンとFIFOを組み合わせた多段フィードバックキューを採用しており、プロセスの状況に応じて動的に優先度を調整します。

リアルタイム性を保証するスケジューリング

リアルタイムシステムでは、優先度逆転問題を防ぎ、タスクのデッドラインを保証することが不可欠です。これらの制約を満たすための研究は盛んに行われていますが、スケジューリングが複雑になるため、実際には利用されることが少ないのが現状です。

オペレーティングシステムのスケジューラ実装

各OSは、独自のスケジューリング方式を採用しています。例えば、ラウンドロビンのような単純なアルゴリズムや、プロセスの優先度を考慮したより高度なアルゴリズムなどがあります。マルチプロセッサシステムでは、プロセッサの親和性を考慮することで、システム全体の性能を向上させることができます。また、負荷分散を行うために、プロセッサごとのキューを使用する方法や、システム全体で単一のキューを使用する方法があります。

各OSのスケジューリング

Windows: Windows NT系のOSでは、多段フィードバックキューを使用しており、スレッドの優先度を動的に調整して、応答性を向上させています。
Mac OS: macOSは多段フィードバックキューを使用し、スレッドに複数の優先度バンドを提供しています。
AIX: AIXでは、FIFO、ラウンドロビン、フェア・ラウンドロビンの3つのスケジューリングポリシーを使用できます。
Linux: Linux 2.6以降では、Completely Fair Scheduler (CFS)という均等化キューイングに基づいたスケジューラを使用しています。
FreeBSD: FreeBSDは、多段フィードバックキューを使用しており、複数の優先度レベルを提供しています。
NetBSD: NetBSDも多段フィードバックキューを使用しており、複数の優先度レベルを提供しています。
* Solaris: Solarisは、多段フィードバックキューを使用しており、複数の優先度レベルを提供しています。

まとめ

スケジューリングは、オペレーティングシステムの中核を成す重要な機能です。効率的なスケジューリングは、システムのリソースを最適に利用し、ユーザーエクスペリエンスを向上させる上で不可欠です。今後も、より効率的で公平なスケジューリングアルゴリズムの開発が進むと予想されます。

もう一度検索