|
スケジューリング
計算機科学においてスケジューリング（英: scheduling）は、スレッドやプロセスやデータの流れについて、システム資源（例えば、プロセッサ時間、通信帯域など）へのアクセスを与える方法の一つ。 概要システムを効果的に負荷分散するため、あるいはターゲットの Quality of Service を保証するためになされる。スケジューリングアルゴリズムは、マルチタスク（同時に複数のプロセスを実行）や多重化（複数のデータの流れを同時に転送）の発展とともに進化してきた。 スケジューラの主な関心事は以下の通りである。
スループットを最大化し、レイテンシを最小化するのがスケジューリングの目標である。しかし実際にはこれらの目標は同時に満たすのが難しく、スケジューラは適当なところで妥協した実装とすることが多い。ユーザーのニーズと目的によって上記のいずれかに力点を置く。 ファクトリーオートメーションのための組み込みシステム（例えば産業用ロボット）などのリアルタイム環境では、スケジューラがプロセスの時間制限（デッドライン）を満たすことを保証する必要がある。これは、システムの安定性を保つ上で重要である。 近年[いつ?]では消費電力を考慮したローパワースケジューリングの研究が盛んに行われている。 スケジューラの分類スケジューラは3種類に分類される。「長期スケジューラ」、「中期スケジューラ」、「短期スケジューラ」である。名称が示唆するとおり、その機能が実行される頻度が異なる。スケジューラは、システムに次に入れるべきジョブを決定し、次の実行すべきプロセスを決定する。 長期スケジューラ長期スケジューラはジョブやプロセスを実行可能キューに載せるかどうかを決定する。つまり、あるプログラムを実行しようとしたとき、それを実行可能なプロセス群にすぐに追加するか、それとも遅延させるかを長期スケジューラが決定するのである。この種のスケジューラはシステム上で実行すべきプロセス群を決定し、ある時点の並列性の度合いをも決定すると言える。つまり、同時並行的に実行すべきプロセス群を決め、I/Oバウンドなプロセス群とCPUバウンドなプロセス群の比率を決める（I/Oバウンドなプロセスとは記憶媒体すなわちディスクやメモリの入出力待ちとなることが多いプロセスを意味し、CPUバウンドなプロセスとは計算処理主体のプロセスを意味する）。一般的なパーソナルコンピュータなどでは長期スケジューラは存在せず、プロセスは生成されると自動的に実行可能状態となる。しかし、RTOSなどのリアルタイムシステムでは長期スケジューラが重要であり、応答時間の保証のために同時並行的に実行するプロセス数を制限するなどの機能によって、より確実な制御がなされる[1]。 長期スケジューラはバッチ処理システム、コンピュータ・クラスター、スーパーコンピュータ、レンダーファームなどの大規模システムでも重要である。その場合、専用のジョブ管理システムが長期スケジューラの役目を果たす。 なお、「長期スケジューラ」という用語で別の機能を表す場合もある。プロセスの優先度を自動的に変化させて平等性を確保する場合、CPUバウンドなプロセスは徐々に優先度が下げられ、最終的には最低優先度となる。そのようなプロセスは他に高優先度のプロセスが存在する限り、ディスパッチされないことになってしまう。そのため、実行可能状態でありながら長期間実行されていないプロセスの優先度を上げる処理が定期的に実行される。これを長期スケジューラと呼ぶ場合がある。 中期スケジューラ中期スケジューラは仮想記憶方式のシステムに必ず存在し、プロセスを主記憶から二次記憶（ディスクなど）に一時的に退避したり、その逆に二次記憶から主記憶にプロセスを戻したりする。このような処理を「スワップアウト」および「スワップイン」と呼ぶ。中期スケジューラは、長期間ブロックされているプロセスや優先度の低いプロセス、頻繁にページフォールトの発生するプロセスや大量のメモリを確保しているプロセスなどをスワップアウトして主記憶を他のプロセスのために空ける。また、主記憶に余裕が生じたときやブロックされていたプロセスが起動した場合などに、スワップアウトされていたプロセスをスワップインする[2]。 多くのシステムではスワップアウトが発生する前にページ置換アルゴリズムが働いて主記憶の空き容量を増やそうとする。そのため、中期スケジューラはある意味で長期スケジューラとも呼べるような位置づけとなっている。ページ置換は一般に特定のプロセスの使用している全メモリを一度に解放するような動作はせず、システム全体で使用頻度の低いページをターゲットとする。そのように置換されて対応する物理メモリのなくなった仮想ページへのアクセスはページフォールトを発生し、例外処理の延長でページインが行われる。実際、スワップアウトが発生するほどメモリ容量が逼迫する状況では、システムは設計段階で予定されていた性能を発揮できない可能性が高く、なるべくページ置換で済むようにメモリ負荷の事前予測を立てるのが通例である。 短期スケジューラ短期スケジューラ（またはCPUスケジューラ）は、実行可能状態でメモリ上にあるプロセス群の中で次に実行すべき（CPUを割り当てるべき）プロセスを決定する。そのタイミングとしては、クロック割り込み、I/O割り込み、システムコール、その他の何らかの契機がある。従って、短期スケジューラは長期/中期スケジューラよりも頻繁にスケジューリングを行っている。少なくともタイムスライス毎にスケジューリング処理が行われる可能性があり、その間隔は非常に短い。プリエンプティブなスケジューラでは、プロセスを切り替える必要があると判断したときには強制的にディスパッチを行う。一方、非プリエンプティブなスケジューラでは強制的にディスパッチすることはなく、実行中のプロセスが何らかの資源を待つためにブロックするかプログラム上明示的にプロセッサを明け渡したときだけディスパッチを行う[3]。 ディスパッチャCPUのスケジューリング機能に関わるもう1つのコンポーネントとしてディスパッチャがある。ディスパッチャは短期スケジューラが選択したプロセスにCPUの制御を与えるモジュールである。次のようなことを行う。
プロセスを切り換える際に必ず実行されるので、ディスパッチャは性能が重視される。ディスパッチャがあるプロセスを一時停止させ、別のプロセスを実行再開させるのにかかる時間を「ディスパッチ・レイテンシ」と呼ぶ。 スケジューリングアルゴリズムスケジューリングアルゴリズムは、ポリシーに従って同時かつ非同期に要求されるリソースを分配するアルゴリズムである。スレッドやプロセスにCPU時間を分配するスケジューリングアルゴリズムだけでなく、パケットのトラフィックを制御するルーターのスケジューリングアルゴリズム、ハードディスクへのリード/ライト要求に関するスケジューリングアルゴリズム、プリンターのスプーリングのスケジューリングアルゴリズムなどがある。 スケジューリングアルゴリズムの主要な目的は、リソーススタベーションを無くし、リソースの使用者間で公平さを保証することである。スケジューリングは、未処理の要求のどれに資源を割り当てるかを決定する。様々なスケジューリングアルゴリズムがあり、以下ではその一部を紹介する。 FIFO→詳細は「FIFO」を参照
FIFOは最も単純なスケジューリングアルゴリズムで、実行可能キューにプロセスが到着した順番にプロセスをキューイングし、先頭から順に実行する。FCFS (First-Come, First-Served) とも。
最小残余時間優先最小残余時間優先 (SRT) 方式は、最短ジョブ優先 (SJF) 方式とも似ている。この戦略では、キュー内で残り処理時間の推定値が最も短いプロセスをスケジューラが選択する。これはプロセスの完了までにかかる時間についての高度な知識または評価を必要とする。
固定優先度プリエンプティブ・スケジューリング固定優先度プリエンプティブ・スケジューリング (FPPS) は、全てのプロセスに固定の優先度を付与し、その優先度順にプロセスをキューイングする。新たに高優先度のプロセスが到着すると、現に実行中だった低優先度のプロセスは中断される。
ラウンドロビン・スケジューリング→詳細は「ラウンドロビン・スケジューリング」を参照
スケジューラは各プロセスにある一定時間単位を割り当て、次々にその割り当てを実行させる。
多段キュースケジューリング→詳細は「多段フィードバックキュー」を参照
これは、プロセスを容易に複数のグループに分類できる場合に使われる、例えば典型的な分類はフォアグラウンド（対話型）プロセスとバックグラウンド（バッチ）プロセスである。このように分けると、それぞれ応答時間の要求がグループによって異なるので、スケジューリングに求められることがグループによって異なる。 まとめ
通信ネットワークのスケジューリングアルゴリズムパケット交換コンピュータネットワークや他の統計多重化では、データパケットのFIFOキューがスケジューリングアルゴリズムとほぼ同義である。 最も単純なベストエフォートなスケジューリングアルゴリズムとしてラウンドロビン・スケジューリング、均等化キューイング（最大最小公平なスケジューリングアルゴリズム）、比例公平スケジューリング、最大スループットスケジューリングなどがある。ベストエフォートではなくQoSの保証を行う場合、重み付け均等化キューイングなどが使われる。 3.5G携帯システムの High-Speed Downlink Packet Access (HSDPA) などの無線パケットネットワークは、チャネル状態情報を利用した channel-dependent scheduling を採用している。チャネル状態が良好なら、スループットとスペクトル効率も向上する。LTEなどのさらに進んだシステムでは、スケジューリングはパケット単位の動的チャネル割り当てと組み合わされたり、OFDMAマルチキャリアや周波数領域等化コンポーネントを最も有効利用できるユーザーに割り当てることでなされる。 I/Oのスケジューリング方式ディスクのアームやヘッダを移動させる時間を減少させるようにスケジュールすることで、高速化が期待できる。
OSにおけるスケジューリングアルゴリズムの選択法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では 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ではスケジューラが修正され、タイムスタンプカウンタを使って各スレッドが実際に動作したCPUサイクル数をカウントするようになった[9]。また、I/Oキューも優先度付きとなり、ディスクのデフラグメンテーションなどのプログラムが通常の処理を邪魔しないようになった。 Mac OSMac OS 9はスレッドの協調的スケジューリングであり、1つのプロセスが複数の協調動作するスレッド群を制御する。また、MPタスクのプリエンプティブなスケジューリングも提供している。カーネルはプリエンプティブなスケジューリングアルゴリズムを使ってMPタスクをスケジュールする。プロセスマネージャの全プロセスは1つの特殊なMPタスク "blue task" 内で動作する。それらのプロセスはラウンドロビン・スケジューリングを使って協調的にスケジュールされ、 macOSは多段フィードバックキューを使っており、スレッドにはノーマル/システム高優先度/カーネルモードオンリー/リアルタイムという4つの優先度バンドを提供する[10]。プリエンプションを伴ってスケジュールを行う。Carbon内では協調的スケジューラ (cooperative scheduler) も実装している。 AIXAIX Version 4 には、スレッドスケジューリングポリシーとして以下の3種類の設定が可能である。
AIX 5 では、FIFO、ラウンドロビン、フェア・ラウンドロビンという3つのスケジューリングポリシーを実装している。FIFOポリシーには3つの実装（FIFO、FIFO2、FIFO3）がある。ラウンドロビンポリシーはAIXではSCHED_RRと呼ばれ、フェア・ラウンドロビンは SCHED_OTHER と呼ばれる[11]。 LinuxLinux 2.4Linux 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 として保守していた）。 Linux 2.6.0 から Linux 2.6.22 までバージョン 2.6 から 2.6.22 までのカーネルは、Linux 2.5 の開発でインゴ・モルナーらが開発したO(1)スケジューラを採用している。しかし、多くのディストリビューションはコン・コリバスが開発した対話性を向上させるパッチを適用するか、あるいはコン・コリバスのスケジューラに完全に置き換えていた。 Linux 2.6.23 以降コン・コリバスが実装したフェア・シェア・スケジューリング方式の "Rotating Staircase Deadline" に触発され、インゴ・モルナーがO(1)スケジューラの代替として Completely Fair Scheduler を開発した[12]。Completely Fair Scheduler (CFS) はパケット通信用に発明された均等化キューイングという古典的なスケジューリングアルゴリズムをベースにしている。均等化キューイングはかつて stride scheduling の名でCPUスケジューリング方式として使われたことがある。 CFSスケジューラのスケジューリング複雑性は On(log N) で、この N はランキュー上のタスク数である。タスクの選択は一定時間で行われるが、タスク実行後に再びランキューに挿入する際に O(log N) 回の操作を必要とする。これはランキューが赤黒木で実装されているためである。 汎用OSで均等化キューイングをスケジューラとして実装したのはCFSが最初である[13]。 FreeBSDFreeBSDは、優先度が0から255までの多段フィードバックキューを使用している。0から63までは割り込み用、64から127まではカーネル用、128から159まではリアルタイムのユーザースレッド用、160から223まではタイムシェアリングのユーザースレッド用、224から255まではアイドルスレッド用である。Linuxと同様、activeキューを使ってスケジューリングするが、FreeBSDにはidleキューもある[14]。 NetBSDNetBSDは、優先度が0から233までの多段フィードバックキューを使用している。0から63まではタイムシェアリング・スレッド用（SCHED_OTHERポリシー）、64から95まではカーネル空間に入った状態（システムコール実行中など）のユーザースレッド用、96から128まではカーネル・スレッド用、128から191まではユーザーのリアルタイム・スレッド用（SCHED_FIFOまたはSCHED_RRポリシー）、192から233まではソフトウェア割り込み用である。 SolarisSolarisは、優先度が0から169までの多段フィードバックキューを使用している。0から59まではタイムシェアリング・スレッド用[15]、60から99まではシステムスレッド用、100から159はリアルタイム・スレッド用[15]、160から169までは低優先度の割り込み用である。Linuxとは異なり、タイムクォンタムを使い切ったプロセスは新たな優先度を設定され、キューに戻される。 まとめ
脚注
参考文献
関連項目
外部リンク
|
Portal di Ensiklopedia Dunia
