スケジューリング
計算機科学においてスケジューリング(scheduling)は、スレッドやプロセスやデータの流れについて、システム資源(例えば、プロセッサ時間、通信帯域など)へのアクセスを与える方法である。システムを効果的に負荷分散するため、あるいはターゲットの Quality of Service を保証するためになされる。スケジューリングアルゴリズムは、マルチタスク(同時に複数のプロセスを実行)や多重化(複数のデータの流れを同時に転送)の発展とともに進化してきた。
スケジューラの主な関心事は以下の通りである。
スループット - 単位時間ごとに実行完了するプロセスの総数
ターンアラウンド - プロセスの発行から完了までの総時間
応答時間 - 要求を送ってから最初の応答が生成されるまでにかかる時間
公平さ/待ち時間 - 各プロセスに平等にCPU時間を割り当てること(またより一般的には、各プロセスの優先度に応じた適切な時間)
スループットを最大化し、レイテンシを最小化するのがスケジューリングの目標である。しかし実際にはこれらの目標は同時に満たすのが難しく、スケジューラは適当なところで妥協した実装とすることが多い。ユーザーのニーズと目的によって上記のいずれかに力点を置く。
ファクトリーオートメーションのための組み込みシステム(例えば産業用ロボット)などのリアルタイム環境では、スケジューラがプロセスの時間制限(デッドライン)を満たすことを保証する必要がある。これは、システムの安定性を保つ上で重要である。
2021-02では消費電力を考慮したローパワースケジューリングの研究が盛んに行われている。
スケジューリングアルゴリズムは、ポリシーに従って同時かつ非同期に要求されるリソースを分配するアルゴリズムである。スレッドやプロセスにCPU時間を分配するスケジューリングアルゴリズムだけでなく、パケットのトラフィックを制御するルーターのスケジューリングアルゴリズム、ハードディスクへのリード/ライト要求に関するスケジューリングアルゴリズム、プリンターのスプーリングのスケジューリングアルゴリズムなどがある。
スケジューリングアルゴリズムの主要な目的は、リソーススタベーションを無くし、リソースの使用者間で公平さを保証することである。スケジューリングは、未処理の要求のどれに資源を割り当てるかを決定する。様々なスケジューリングアルゴリズムがあり、以下ではその一部を紹介する。
FIFOは最も単純なスケジューリングアルゴリズムで、実行可能キューにプロセスが到着した順番にプロセスをキューイングし、先頭から順に実行する。FCFS (First-Come, First-Served) とも。
コンテキストスイッチはプロセス終了時にしか発生せず、キューの再編成も必要とされないので、スケジューリングのオーバーヘッドは最小である。
長くかかるプロセスがCPUを占有することがあるので、スループットは低くなりうる。
同じ理由で、ターンアラウント時間、待ち時間、応答時間は長くなる可能性がある。
優先順位付けは行わないので、プロセスのデッドラインを満たすのは難しい。
優先順位付けを行わないということは、全てのプロセスが結局は完了するという意味で、スタベーションは発生しないと言える。一部プロセスが完了しない環境では、スタベーションがありうる。
キューイングをベースとしている。
最小残余時間優先 (SRT) 方式は、最短ジョブ優先 (SJF) 方式とも似ている。この戦略では、キュー内で残り処理時間の推定値が最も短いプロセスをスケジューラが選択する。これはプロセスの完了までにかかる時間についての高度な知識または評価を必要とする。
あるプロセスを実行中に別のもっと短いプロセスが到着すると、動作中のプロセスは中断され(プリエンプション)、そのプロセスを2つの別々の計算ブロックに分けることになる。これはコンテキストスイッチを追加することになり、オーバーヘッドが増えることを意味する。スケジューラはキュー上の適当な位置に新たなプロセスを置かなければならず、これもオーバヘッドを生じる。
多くの場合でスループットを最大化するよう設計されている。
プロセスが要求する計算資源が大きいほど、待ち時間と応答時間が増大する。ターンアラウンド時間は待ち時間と処理時間の総和なので、長くかかるプロセスは特に大きく影響を受ける。全体としての待ち時間の総和はFIFOと同程度だが、長くかかるプロセスの完了まで他のプロセスを待たせる必要はない。
デッドラインに対する配慮は全くない。プログラマはプロセスがなるべく短時間で終了するよう気をつけるぐらいしかできない。
スタベーションは発生しうる。特に小さなプロセスが多数動作するシステムで発生しやすい。
固定優先度プリエンプティブ・スケジューリング (FCFS) は、全てのプロセスに固定の優先度を付与し、その優先度順にプロセスをキューイングする。新たに高優先度のプロセスが到着すると、現に実行中だった低優先度のプロセスは中断される。
オーバーヘッドは最小でもないし、極端に大きくもない。
スループットの面では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スケジューラとして採用されている。
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()ではプロセスのアドレス空間の内容が置き換えられるので、ノード間の移動をさせるのにちょうどよいタイミングと言える。
初期のMS-DOSやWindowsシステムはマルチタスクではないので、スケジューラも存在しなかった。Windows 3.1系のOSは単純な非プリエンプティブ・スケジューラを使用しており、プログラマはプロセスが明示的にCPUを明け渡す (yield) ように設計してCPU時間を他のプロセスに使わせる必要があった。これにより協調的マルチタスクをサポートしていた。Windows 95 で初歩的なプリエンプティブ・スケジューラを導入したが、互換性を維持するため16ビットアプリケーションはプリエンプションなしで動作した。
Windows NT系のOSは多段フィードバックキューを使っている。優先度は32段階で0から31まであり、0から15がノーマル優先度、16から31がリアルタイム優先度と呼ばれている。リアルタイム優先度はアドミニストレータ特権がないと設定できない。0はOSが予約している。ユーザーはタスクマネージャまたはスレッド管理APIから動作中アプリケーションの優先度を5段階に設定できる。カーネルはスレッドのI/OおよびCPU使用具合を見て優先度を更新しており、対話的(ユーザーとのやりとりを行っている)なI/O中心のプロセスの優先度は高くし、CPU中心のプロセスの優先度は低くする。それによってアプリケーションの応答性を向上させる。Windows Vista ではスケジューラが修正され、タイムスタンプカウンタを使って各スレッドが実際に動作したCPUサイクル数をカウントするようになった。また、I/Oキューも優先度付きとなり、ディスクのデフラグメンテーションなどのプログラムが通常の処理を邪魔しないようになった。
Mac OS 9はスレッドの協調的スケジューリングであり、1つのプロセスが複数の協調動作するスレッド群を制御する。また、MPタスクのプリエンプティブなスケジューリングも提供している。カーネルはプリエンプティブなスケジューリングアルゴリズムを使ってMPタスクをスケジュールする。プロセスマネージャの全プロセスは1つの特殊なMPタスク "blue task" 内で動作する。それらのプロセスはラウンドロビン・スケジューリングを使って協調的にスケジュールされ、WaitNextEvent などの関数を使って明示的にプロセッサの制御を他のプロセスに譲る。各プロセスにはスレッドマネージャがあり、こちらもスレッド群を協調的にスケジュールする。スレッドは YieldToAnyThread や YieldToThread といった関数を使って他のスレッドにプロセッサの制御を譲る。
macOSは多段フィードバックキューを使っており、スレッドにはノーマル/システム高優先度/カーネルモードオンリー/リアルタイムという4つの優先度バンドを提供する。プリエンプションを伴ってスケジュールを行う。Carbon内では協調的スケジューラ (cooperative scheduler) も実装している。
AIX Version 4 には、スレッドスケジューリングポリシーとして以下の3種類の設定が可能である。
このポリシーでスケジュールされたスレッドは、ブロックされるまで、あるいはCPUの制御を明示的に明け渡すまで、あるいはより高優先度のスレッドが動作可能になるまで、動作し続ける。FIFOスケジューリングポリシーは固定優先度のスレッドのみ設定可能である。
AIX Version 3 のスケジューラと同様のラウンドロビン方式で、タイムスライスは10ミリ秒である。RRスレッドがタイムスライスを使い切ると、その優先度の実行可能スレッドのキューの最後尾につなげられる。RRスケジューリングポリシーは固定優先度のスレッドのみ設定可能である。
POSIX1003.4a で定義されたポリシーの実装。AIX Version 4 では RR と等価だが、固定優先度でないスレッドにも適用される。クロック割り込みの際に動作中スレッドの優先度を再計算するので、他の動作可能なスレッドの方が優先度が高くなれば、そこでディスパッチが発生する。これは AIX Version 3 と同じである。
AIX 5 では、FIFO、ラウンドロビン、フェア・ラウンドロビンという3つのスケジューリングポリシーを実装している。FIFOポリシーには3つの実装(FIFO、FIFO2、FIFO3)がある。ラウンドロビンポリシーはAIXではSCHED_RRと呼ばれ、フェア・ラウンドロビンは SCHED_OTHER と呼ばれる。
Linux 2.4 では、多段フィードバックキュー方式のO(n)スケジューラを採用していた。優先度は0から140まであり、0から99まではリアルタイムタスク用、100から140まではniceタスク用のレベルとされていた。リアルタイムのタスクでは、プロセス切り替え間隔であるタイムクォンタムは約200ミリ秒、niceタスクでは約10ミリ秒となっていた。スケジューラは全実行可能プロセスが入っているactiveキューを調べ、最も優先度の高いプロセスを選択してディスパッチし、タイムクォンタムを使い切ったら、それをexpiredキューにつなぐ。activeキューが空になると、expiredキューがactiveキューとなり、activeキューだったものがexpiredキューとなる。
一部の企業向けLinuxディストリビューション(SUSE Linux Enterprise Server など)は、O(1)スケジューラを2.4カーネルに先取りする形で移植したものを使っていた(アラン・コックスが Linux 2.4-ac Kernel series として保守していた)。
バージョン 2.6 から 2.6.22 までのカーネルは、Linux 2.5 の開発でインゴ・モルナーらが開発したO(1)スケジューラを採用している。しかし、多くのディストリビューションはコン・コリバスが開発した対話性を向上させるパッチを適用するか、あるいはコン・コリバスのスケジューラに完全に置き換えていた。
コン・コリバスが実装したフェア・シェア・スケジューリング方式の "Rotating Staircase Deadline" に触発され、インゴ・モルナーがO(1)スケジューラの代替として Completely Fair Scheduler を開発した。Completely Fair Scheduler (CFS) はパケット通信用に発明された均等化キューイングという古典的なスケジューリングアルゴリズムをベースにしている。均等化キューイングはかつて stride scheduling の名でCPUスケジューリング方式として使われたことがある。
CFSスケジューラのスケジューリング複雑性は O(log N) で、この N はランキュー上のタスク数である。タスクの選択は一定時間で行われるが、タスク実行後に再びランキューに挿入する際に O(log N) 回の操作を必要とする。これはランキューが赤黒木で実装されているためである。
汎用OSで均等化キューイングをスケジューラとして実装したのはCFSが最初である。
FreeBSDは、優先度が0から255までの多段フィードバックキューを使用している。0から63までは割り込み用、64から127まではカーネル用、128から159まではリアルタイムのユーザースレッド用、160から223まではタイムシェアリングのユーザースレッド用、224から255まではアイドルスレッド用である。Linuxと同様、activeキューを使ってスケジューリングするが、FreeBSDにはidleキューもある。
NetBSDは、優先度が0から233までの多段フィードバックキューを使用している。0から63まではタイムシェアリング・スレッド用(SCHED_OTHERポリシー)、64から95まではカーネル空間に入った状態(システムコール実行中など)のユーザースレッド用、96から128まではカーネル・スレッド用、128から191まではユーザーのリアルタイム・スレッド用(SCHED_FIFOまたはSCHED_RRポリシー)、192から233まではソフトウェア割り込み用である。
Solarisは、優先度が0から169までの多段フィードバックキューを使用している。0から59まではタイムシェアリング・スレッド用、60から99まではシステムスレッド用、100から159はリアルタイム・スレッド用、160から169までは低優先度の割り込み用である。Linuxとは異なり、タイムクォンタムを使い切ったプロセスは新たな優先度を設定され、キューに戻される。