計算機科学 においてスケジューリング （英 : scheduling ）は、スレッド やプロセス やデータの流れについて、システム資源（例えば、プロセッサ時間、通信帯域など）へのアクセスを与える方法の一つ。
システムを効果的に負荷分散 するため、あるいはターゲットの Quality of Service を保証するためになされる。スケジューリングアルゴリズムは、マルチタスク （同時に複数のプロセスを実行）や多重化 （複数のデータの流れを同時に転送）の発展とともに進化してきた。
スケジューラの主な関心事は以下の通りである。
スループット - 単位時間ごとに実行完了するプロセスの総数レイテンシ
ターンアラウンド - プロセスの発行から完了までの総時間
応答時間 - 要求を送ってから最初の応答が生成されるまでにかかる時間公平さ/待ち時間 - 各プロセスに平等にCPU時間を割り当てること（またより一般的には、各プロセスの優先度に応じた適切な時間） スループットを最大化し、レイテンシを最小化するのがスケジューリングの目標である。しかし実際にはこれらの目標は同時に満たすのが難しく、スケジューラは適当なところで妥協した実装とすることが多い。ユーザーのニーズと目的によって上記のいずれかに力点を置く。
ファクトリーオートメーション のための組み込みシステム （例えば産業用ロボット ）などのリアルタイム 環境では、スケジューラがプロセスの時間制限（デッドライン）を満たすことを保証する必要がある。これは、システムの安定性を保つ上で重要である。
近年 [いつ? では消費電力を考慮したローパワースケジューリングの研究が盛んに行われている。
スケジューラは3種類に分類される。「長期スケジューラ」、「中期スケジューラ」、「短期スケジューラ」である。名称が示唆するとおり、その機能が実行される頻度が異なる。スケジューラは、システムに次に入れるべきジョブを決定し、次の実行すべきプロセスを決定する。
長期スケジューラはジョブやプロセスを実行可能キューに載せるかどうかを決定する。つまり、あるプログラムを実行しようとしたとき、それを実行可能なプロセス群にすぐに追加するか、それとも遅延させるかを長期スケジューラが決定するのである。この種のスケジューラはシステム上で実行すべきプロセス群を決定し、ある時点の並列性の度合いをも決定すると言える。つまり、同時並行的に実行すべきプロセス群を決め、I/Oバウンドなプロセス群とCPUバウンドなプロセス群の比率を決める（I/Oバウンドなプロセスとは記憶媒体すなわちディスクやメモリの入出力待ちとなることが多いプロセスを意味し、CPUバウンドなプロセスとは計算処理主体のプロセスを意味する）。一般的なパーソナルコンピュータ などでは長期スケジューラは存在せず、プロセスは生成されると自動的に実行可能状態となる。しかし、RTOSなどのリアルタイムシステムでは長期スケジューラが重要であり、応答時間の保証のために同時並行的に実行するプロセス数を制限するなどの機能によって、より確実な制御がなされる[ 1]
長期スケジューラはバッチ処理 システム、コンピュータ・クラスター 、スーパーコンピュータ 、レンダーファーム などの大規模システムでも重要である。その場合、専用のジョブ管理システム が長期スケジューラの役目を果たす。
なお、「長期スケジューラ」という用語で別の機能を表す場合もある。プロセスの優先度を自動的に変化させて平等性を確保する場合、CPUバウンドなプロセスは徐々に優先度が下げられ、最終的には最低優先度となる。そのようなプロセスは他に高優先度のプロセスが存在する限り、ディスパッチされないことになってしまう。そのため、実行可能状態でありながら長期間実行されていないプロセスの優先度を上げる処理が定期的に実行される。これを長期スケジューラと呼ぶ場合がある。
中期スケジューラは仮想記憶 方式のシステムに必ず存在し、プロセスを主記憶から二次記憶（ディスクなど）に一時的に退避したり、その逆に二次記憶から主記憶にプロセスを戻したりする。このような処理を「スワップアウト」および「スワップイン」と呼ぶ。中期スケジューラは、長期間ブロックされているプロセスや優先度の低いプロセス、頻繁にページフォールト の発生するプロセスや大量のメモリを確保しているプロセスなどをスワップアウトして主記憶を他のプロセスのために空ける。また、主記憶に余裕が生じたときやブロックされていたプロセスが起動した場合などに、スワップアウトされていたプロセスをスワップインする[ 2]
多くのシステムではスワップアウトが発生する前にページ置換アルゴリズム が働いて主記憶の空き容量を増やそうとする。そのため、中期スケジューラはある意味で長期スケジューラとも呼べるような位置づけとなっている。ページ置換は一般に特定のプロセスの使用している全メモリを一度に解放するような動作はせず、システム全体で使用頻度の低いページをターゲットとする。そのように置換されて対応する物理メモリのなくなった仮想ページへのアクセスはページフォールト を発生し、例外処理 の延長でページインが行われる。実際、スワップアウトが発生するほどメモリ容量が逼迫する状況では、システムは設計段階で予定されていた性能を発揮できない可能性が高く、なるべくページ置換で済むようにメモリ負荷の事前予測を立てるのが通例である。
短期スケジューラ（またはCPUスケジューラ）は、実行可能状態でメモリ上にあるプロセス群の中で次に実行すべき（CPUを割り当てるべき）プロセスを決定する。そのタイミングとしては、クロック割り込み 、I/O割り込み、システムコール 、その他の何らかの契機がある。従って、短期スケジューラは長期/中期スケジューラよりも頻繁にスケジューリングを行っている。少なくともタイムスライス毎にスケジューリング処理が行われる可能性があり、その間隔は非常に短い。プリエンプティブ なスケジューラでは、プロセスを切り替える必要があると判断したときには強制的にディスパッチを行う。一方、非プリエンプティブなスケジューラでは強制的にディスパッチすることはなく、実行中のプロセスが何らかの資源を待つためにブロックするかプログラム上明示的にプロセッサを明け渡したときだけディスパッチを行う[ 3]
CPUのスケジューリング機能に関わるもう1つのコンポーネントとしてディスパッチャがある。ディスパッチャは短期スケジューラが選択したプロセスにCPUの制御を与えるモジュールである。次のようなことを行う。
プロセスを切り換える際に必ず実行されるので、ディスパッチャは性能が重視される。ディスパッチャがあるプロセスを一時停止させ、別のプロセスを実行再開させるのにかかる時間を「ディスパッチ・レイテンシ」と呼ぶ。
スケジューリングアルゴリズムは、ポリシーに従って同時かつ非同期に要求されるリソースを分配するアルゴリズムである。スレッド やプロセス にCPU時間を分配するスケジューリングアルゴリズムだけでなく、パケットのトラフィックを制御するルーター のスケジューリングアルゴリズム、ハードディスクへのリード/ライト要求に関するスケジューリングアルゴリズム、プリンターのスプーリング のスケジューリングアルゴリズムなどがある。
スケジューリングアルゴリズムの主要な目的は、リソーススタベーション を無くし、リソースの使用者間で公平さを保証することである。スケジューリングは、未処理の要求のどれに資源を割り当てるかを決定する。様々なスケジューリングアルゴリズムがあり、以下ではその一部を紹介する。
FIFO
FIFO は最も単純なスケジューリングアルゴリズムで、実行可能キュー にプロセスが到着した順番にプロセスをキューイングし、先頭から順に実行する。FCFS (First-Come, First-Served) とも。
コンテキストスイッチはプロセス終了時にしか発生せず、キューの再編成も必要とされないので、スケジューリングのオーバーヘッドは最小である。
長くかかるプロセスがCPUを占有することがあるので、スループットは低くなりうる。
同じ理由で、ターンアラウンド時間、待ち時間、応答時間は長くなる可能性がある。
優先順位付けは行わないので、プロセスのデッドラインを満たすのは難しい。
優先順位付けを行わないということは、全てのプロセスが結局は完了するという意味で、スタベーション は発生しないと言える。一部プロセスが完了しない環境では、スタベーションがありうる。
キューイングをベースとしている。
最小残余時間優先 （英語版 ） 最短ジョブ優先 （英語版 ）
あるプロセスを実行中に別のもっと短いプロセスが到着すると、動作中のプロセスは中断され（プリエンプション ）、そのプロセスを2つの別々の計算ブロックに分けることになる。これはコンテキストスイッチを追加することになり、オーバーヘッドが増えることを意味する。スケジューラはキュー上の適当な位置に新たなプロセスを置かなければならず、これもオーバヘッドを生じる。
多くの場合でスループットを最大化するよう設計されている。
プロセスが要求する計算資源が大きいほど、待ち時間と応答時間が増大する。ターンアラウンド時間は待ち時間と処理時間の総和なので、長くかかるプロセスは特に大きく影響を受ける。全体としての待ち時間の総和はFIFOと同程度だが、長くかかるプロセスの完了まで他のプロセスを待たせる必要はない。
デッドラインに対する配慮は全くない。プログラマはプロセスがなるべく短時間で終了するよう気をつけるぐらいしかできない。
スタベーションは発生しうる。特に小さなプロセスが多数動作するシステムで発生しやすい。
固定優先度プリエンプティブ・スケジューリング （英語版 ）
オーバーヘッドは最小でもないし、極端に大きくもない。
スループットの面ではFIFOスケジューリングと大差ない。
待ち時間と応答時間はプロセスの優先度に左右される。高優先度のプロセスほど待ち時間と応答時間が小さくなる。
デッドラインは優先度をうまく設定することで満たすことができる。
低優先度プロセスではスタベーションが発生しうる。
スケジューラは各プロセスにある一定時間単位を割り当て、次々にその割り当てを実行させる。
オーバーヘッドは比較的大きく、特に割り当てる時間単位を短くするほど大きくなる。
スループットはFCFSとSJFの中間で、短いジョブはFCFSより早く完了し、長いプロセスはSJFより早く完了する。
平均応答時間はよくない。待ち時間はプロセス数に依存し、平均プロセス長（時間）には依存しない。
待ち時間は比較的長いので、純粋なラウンドロビンでデッドラインを守るのは難しい。
優先度を設定していないので、スタベーションは決して発生しない。時間単位を割り当てる順序は、FCFSと同様プロセスの到着順である。
これは、プロセスを容易に複数のグループに分類できる場合に使われる、例えば典型的な分類はフォアグラウンド（対話型）プロセスとバックグラウンド（バッチ）プロセスである。このように分けると、それぞれ応答時間の要求がグループによって異なるので、スケジューリングに求められることがグループによって異なる。
パケット交換 コンピュータネットワーク や他の統計多重化 では、データパケットのFIFO キューがスケジューリングアルゴリズムとほぼ同義である。
最も単純なベストエフォート なスケジューリングアルゴリズムとしてラウンドロビン・スケジューリング 、均等化キューイング （英語版 ） 最大最小公平 （英語版 ） 比例公平 （英語版 ） 最大スループットスケジューリング （英語版 ） QoS の保証を行う場合、重み付け均等化キューイング （英語版 ）
3.5G携帯システムの High-Speed Downlink Packet Access (HSDPA) などの無線パケットネットワークは、チャネル状態情報 （英語版 ） channel-dependent scheduling を採用している。チャネル状態が良好なら、スループット とスペクトル効率 も向上する。LTE などのさらに進んだシステムでは、スケジューリングはパケット単位の動的チャネル割り当てと組み合わされたり、OFDMA マルチキャリアや周波数領域等化 （英語版 ）
ディスクのアームやヘッダを移動させる時間を減少させるようにスケジュールすることで、高速化が期待できる。
FIFO (First In, First Out) - 単純にI/O要求を受け付けた順に処理する方式。Shortest Seek First - シーク時間が最も短くなるようにスケジュールする方式。Elevator Algorithm - ヘッドをシリンダ番号の昇順か降順に動作させるものとし、その順番にあうようにスケジュールする方式。Shortest Seek Firstと比べ、断続的にI/O要求を受け付けた場合でも待ち時間のばらつきが小さく収まる特徴がある。Anticipatory Scheduling - 将来のI/O要求を予測してスケジュールする方式。Completely Fair Queuing (CFQ) - プロセス毎のI/Oキューを持ち、できるだけ公平にスケジュールする方式。Linux 2.6.18以降のデフォルトのI/Oスケジューラとして採用されていたが、Linux5.0で削除された。[ 4] Budget Fair Queueing (BFQ) - CFQをマルチキュー機構向けに改良したLinuxのI/Oスケジューラ。スループットよりもレイテンシーを少なくするように制御する。[ 5] Deadline - 時間制限を設けリクエストの処理開始時間を保証する方式。[ 6]
OS設計の際、そのシステムを使用するにあたって最善のスケジューリングアルゴリズムは何かを検討する必要がある。あらゆる用途に最善といえる単一のスケジューリングアルゴリズムは存在せず、上述の各種スケジューリングアルゴリズムを組み合わせたり拡張したりして使っているOSが多い。例えば、Windows NT /XP/Vista は固定優先度プリエンプティブ・スケジューリングとラウンドロビンとFIFOを組み合わせた多段フィードバックキュー を採用している。このシステムでは、プロセスがそれまでに動作してきた状況や待ち続けた状況に従い、優先度を動的に調整する。優先度ごとにキューがあり、高優先度のキューではラウンドロビン・スケジューリング 、低優先度のキューではFIFO を採用している。応答時間はほとんどのプロセスで短くなり、短いが重要なプロセスは特に素早く完了する。高優先度のキューはラウンドロビン なのでプロセスが一定時間単位しか動作しないため、スタベーションは起こりにくい。
スケジューリングにおいて、リアルタイム制約を満たすということは以下のどちらかを指す。
優先度逆転問題 を防ぐ。タスクのリアルタイム制約を守れることを保証する。 後者についての研究はさかんに行われているが、
スケジューリングが複雑になるために実際のシステムで利用されることは極めて少ない。
当然のことながら、OSの数だけスケジューリング方式がある。
ラウンドロビン のような単純なアルゴリズムを採用すると、各プロセスに同じ時間（一般に1ミリ秒から100ミリ秒）が割り当てられ、それが巡回するように実際に実行されていく。従って、プロセスとして A、B、C の3つがあるとき、Aを1ミリ秒実行し、次にB、次にCと実行していき、再びAを実行するというようになる。
より進んだアルゴリズムではプロセスに優先度を設定したり、プロセスの重要度を判断したりする。それによって特定のプロセスが他のプロセスよりも優先してCPU時間を割り当てられることになる。カーネル はシステムを正しく機能させるのに必要な資源を必要なだけ使用するので、ある意味では無限の優先度があるとも言える。対称型マルチプロセッシング (SMP) システムでは、プロセッサ親和性 を考慮することでシステム全体性能を向上させようとするが、個々のプロセスはそれによって動作がゆっくりになることもありうる。これは一般にキャッシュスラッシング を低減させることで性能を向上させる。
マルチプロセッシング では、各プロセッサをなるべく平等に使用するようスケジューリングするのが一般的である。スケジューリングをプロセッサ単位に行う方式とシステム全体で行う方式があり、前者ではプロセッサ毎の実行可能プロセスのキューが存在し、後者ではシステムに唯一の実行可能プロセスキューが存在する。システム全体の方が優先順位の逆転 が発生しにくく、プロセッサ間の負荷バランスをとりやすいという利点がある。しかし、実行効率を考えた場合、各プロセッサのキャッシュメモリ の内容などを生かすにはプロセスはなるべく同じプロセッサ上で実行された方がよい。この性質をアフィニティ (affinity) と呼ぶ。そのため、プロセッサ単位のスケジューラを使用し、負荷バランスが大きく崩れたときだけ調整を行う方式を採用するシステムもある。また、システム全体をひとつのスケジューラで制御しようとすると、実行可能プロセスキューへのアクセスで衝突が発生し性能が低下するという問題もある。
NUMA では、SMP システムが相互接続されている。このSMPシステム間でのプロセスの移動はSMP内よりもさらに性能に悪影響を与える。そのため各SMPシステムでスケジューラを動作させ、SMPシステム間の負荷バランスは別途調整するのが一般的である。Linuxではexec()によるオーバーレイ の際にバランス調整を行う。exec()ではプロセスのアドレス空間 の内容が置き換えられるので、ノード間の移動をさせるのにちょうどよいタイミングと言える。
Windows
初期のMS-DOS やWindowsシステムはマルチタスクではないので、スケジューラも存在しなかった。Windows 3.1 系のOSは単純な非プリエンプティブ・スケジューラを使用しており、プログラマはプロセスが明示的にCPUを明け渡す (yield) ように設計してCPU時間を他のプロセスに使わせる必要があった。これにより協調的マルチタスクをサポートしていた。Windows 95 で初歩的なプリエンプティブ・スケジューラを導入したが、互換性を維持するため16ビットアプリケーションはプリエンプションなしで動作した[ 7]
Windows NT 系のOSは多段フィードバックキュー を使っている。優先度は32段階で0から31まであり、0から15がノーマル優先度、16から31がリアルタイム優先度と呼ばれている。リアルタイム優先度はアドミニストレータ特権がないと設定できない。0はOSが予約している。ユーザーはタスクマネージャまたはスレッド管理APIから動作中アプリケーションの優先度を5段階に設定できる。カーネルはスレッドのI/OおよびCPU使用具合を見て優先度を更新しており、対話的（ユーザーとのやりとりを行っている）なI/O中心のプロセスの優先度は高くし、CPU中心のプロセスの優先度は低くする。それによってアプリケーションの応答性を向上させる[ 8] Windows Vista ではスケジューラが修正され、タイムスタンプカウンタ （英語版 ） [ 9] デフラグメンテーション などのプログラムが通常の処理を邪魔しないようになった。
Mac OS
Mac OS 9 はスレッドの協調的スケジューリングであり、1つのプロセスが複数の協調動作するスレッド群を制御する。また、MPタスクのプリエンプティブなスケジューリングも提供している。カーネルはプリエンプティブなスケジューリングアルゴリズムを使ってMPタスクをスケジュールする。プロセスマネージャの全プロセスは1つの特殊なMPタスク "blue task" 内で動作する。それらのプロセスはラウンドロビン・スケジューリング を使って協調的にスケジュールされ、WaitNextEvent などの関数を使って明示的にプロセッサの制御を他のプロセスに譲る。各プロセスにはスレッドマネージャがあり、こちらもスレッド群を協調的にスケジュールする。スレッドは YieldToAnyThread や YieldToThread といった関数を使って他のスレッドにプロセッサの制御を譲る。
macOS は多段フィードバックキュー を使っており、スレッドにはノーマル/システム高優先度/カーネルモードオンリー/リアルタイムという4つの優先度バンドを提供する[ 10] プリエンプション を伴ってスケジュールを行う。Carbon 内では協調的スケジューラ （英語版 ）
AIX
AIX Version 4 には、スレッドスケジューリングポリシーとして以下の3種類の設定が可能である。
FIFO
このポリシーでスケジュールされたスレッドは、ブロックされるまで、あるいはCPUの制御を明示的に明け渡すまで、あるいはより高優先度のスレッドが動作可能になるまで、動作し続ける。FIFOスケジューリングポリシーは固定優先度のスレッドのみ設定可能である。
RR
AIX Version 3 のスケジューラと同様のラウンドロビン方式で、タイムスライスは10ミリ秒である。RRスレッドがタイムスライスを使い切ると、その優先度の実行可能スレッドのキューの最後尾につなげられる。RRスケジューリングポリシーは固定優先度のスレッドのみ設定可能である。
OTHER
POSIX1003.4a で定義されたポリシーの実装。AIX Version 4 では RR と等価だが、固定優先度でないスレッドにも適用される。クロック割り込みの際に動作中スレッドの優先度を再計算するので、他の動作可能なスレッドの方が優先度が高くなれば、そこでディスパッチが発生する。これは AIX Version 3 と同じである。 AIX 5 では、FIFO、ラウンドロビン、フェア・ラウンドロビンという3つのスケジューリングポリシーを実装している。FIFOポリシーには3つの実装（FIFO、FIFO2、FIFO3）がある。ラウンドロビンポリシーはAIXではSCHED_RRと呼ばれ、フェア・ラウンドロビンは SCHED_OTHER と呼ばれる[ 11]
Linux
Linux 2.4
Linux 2.4 では、多段フィードバックキュー 方式のO(n)スケジューラ （英語版 ） nice タスク用のレベルとされていた。リアルタイムのタスクでは、プロセス切り替え間隔であるタイムクォンタムは約200ミリ秒、niceタスクでは約10ミリ秒となっていた[要出典 。スケジューラは全実行可能プロセスが入っているactiveキューを調べ、最も優先度の高いプロセスを選択してディスパッチし、タイムクォンタムを使い切ったら、それをexpiredキューにつなぐ。activeキューが空になると、expiredキューがactiveキューとなり、activeキューだったものがexpiredキューとなる。
一部の企業向けLinuxディストリビューション （SUSE Linux Enterprise Server など）は、O(1)スケジューラ （英語版 ） アラン・コックス が Linux 2.4-ac Kernel series として保守していた）。
バージョン 2.6 から 2.6.22 までのカーネルは、Linux 2.5 の開発でインゴ・モルナー （英語版 ） O(1)スケジューラ （英語版 ） コン・コリバス （英語版 ）
コン・コリバス （英語版 ） フェア・シェア・スケジューリング （英語版 ） O(1)スケジューラ （英語版 ） Completely Fair Scheduler を開発した[ 12] パケット通信 用に発明された均等化キューイング （英語版 ） stride scheduling の名でCPUスケジューリング方式として使われたことがある。
CFSスケジューラのスケジューリング複雑性は On(log N) で、この N はランキュー上のタスク数である。タスクの選択は一定時間で行われるが、タスク実行後に再びランキューに挿入する際に O(log N) 回の操作を必要とする。これはランキュー （英語版 ） 赤黒木 で実装されているためである。
汎用OSで均等化キューイングをスケジューラとして実装したのはCFSが最初である[ 13]
FreeBSD
FreeBSD は、優先度が0から255までの多段フィードバックキュー を使用している。0から63までは割り込み用、64から127まではカーネル用、128から159まではリアルタイムのユーザースレッド用、160から223まではタイムシェアリングのユーザースレッド用、224から255まではアイドルスレッド用である。Linuxと同様、activeキューを使ってスケジューリングするが、FreeBSDにはidleキューもある[ 14]
NetBSD
NetBSD は、優先度が0から233までの多段フィードバックキュー を使用している。0から63まではタイムシェアリング・スレッド用（SCHED_OTHERポリシー）、64から95まではカーネル空間 に入った状態（システムコール 実行中など）のユーザースレッド用、96から128まではカーネル・スレッド用、128から191まではユーザーのリアルタイム・スレッド用（SCHED_FIFOまたはSCHED_RRポリシー）、192から233まではソフトウェア割り込み 用である。
Solaris
Solaris は、優先度が0から169までの多段フィードバックキュー を使用している。0から59まではタイムシェアリング・スレッド用[ 15] [ 15]
Błażewicz, Jacek; Ecker, K.H.; Pesch, E.; Schmidt, G.; Weglarz, J. (2001). Scheduling computer and manufacturing processes (2 ed.). Berlin [u.a.]: Springer. ISBN 3-540-41931-4 Stallings, William (2004). Operating Systems Internals and Design Principles (fifth international edition) . Prentice Hall. ISBN 0-13-147954-7 Stallings, William (2004). Operating Systems Internals and Design Principles (fourth edition) . Prentice Hall. ISBN 0-13-031999-6 Information on the Linux 2.6 O(1)-scheduler
