スケジューリング

出典: Wikipedio

スケジューリングは、マルチタスクOS、マルチプロセッシングOS、RTOSなどの設計における重要な概念である。スケジューリングは、優先度つきキューで優先度を割り当てられたプロセス(またはタスク)を制御する手法を指す。この優先度割り当てを行うソフトウェアをスケジューラと呼ぶ。実行プロセスの切り替えを行う操作はディスパッチと呼ばれ、スケジューラはディスパッチ先のプロセスを決定するソフトウェアと言うことができる。

汎用OSでは、スケジューラの設計目標はプロセッサの負荷を公平に分散し、かつ全プロセスについてプロセッサを独占したり、逆に全く資源を割り当てられなかったりすることなく平等に実行されるよう制御することである。ミッションクリティカルな用途を指向している汎用OS(例えばSolaris、AIX、z/OSなど)では、スケジューラは「防御的」機能を備えている。プロセスが積極的にプロセッサリソースを可能な限り使用しようとする場合、システムはそのプロセスを減速させてプロセッサをなるべく割り当てないようにする。

RTOSは機器の自動制御などにも使われるが、そのような場合は処理の遅延が致命的となるので、スケジューラは保証した時間以内にタスクが実行されるようにしなければならない。

スケジューリングの望ましい属性として、システム全体のスループットが高くなること、 リアルタイム性を守ることなどがあげられる。 近年では消費電力を考慮した ローパワースケジューリングの研究が盛んに行われている。

目次

スケジューラの分類

スケジューラは3種類に分類される。「長期スケジューラ」、「中期スケジューラ」、「短期スケジューラ」(ディスパッチャとも呼ぶ)である。

長期スケジューラ

長期スケジューラはジョブやプロセスを実行可能キューに載せるかどうかを決定する。つまり、あるプログラムを実行しようとしたとき、それを実行可能なプロセス群にすぐに追加するか、それとも遅延させるかを長期スケジューラが決定するのである。この種のスケジューラはシステム上で実行すべきプロセス群を決定し、ある時点の並列性の度合いをも決定すると言える。つまり、同時並行的に実行すべきプロセス群を決め、I/Oバウンドなプロセス群とCPUバウンドなプロセス群の比率を決める(I/Oバウンドなプロセスとは入出力待ちとなることが多いプロセスを意味し、CPUバウンドなプロセスとは計算処理主体のプロセスを意味する)。一般的なパーソナルコンピュータなどでは長期スケジューラは存在せず、プロセスは生成されると自動的に実行可能状態となる。しかし、RTOSなどのリアルタイムシステムでは長期スケジューラが重要であり、応答時間の保証のために同時並行的に実行するプロセス数を制限するなどの機能によって、より確実な制御がなされる。[Stallings, 399]

なお、「長期スケジューラ」という用語で別の機能を表す場合もある。プロセスの優先度を自動的に変化させて平等性を確保する場合、CPUバウンドなプロセスは徐々に優先度が下げられ、最終的には最低優先度となる。そのようなプロセスは他に高優先度のプロセスが存在する限り、ディスパッチされないことになってしまう。そのため、実行可能状態でありながら長期間実行されていないプロセスの優先度を上げる処理が定期的に実行される。これを長期スケジューラと呼ぶ場合がある。

中期スケジューラ

中期スケジューラは仮想記憶方式のシステムに必ず存在し、プロセスを主記憶から二次記憶(ディスクなど)に一時的に退避したり、その逆に二次記憶から主記憶にプロセスを戻したりする。このような処理を「スワップアウト」および「スワップイン」と呼ぶ。中期スケジューラは、長期間ブロックされているプロセスや優先度の低いプロセス、頻繁にページフォールトの発生するプロセスや大量のメモリを確保しているプロセスなどをスワップアウトして主記憶を他のプロセスのために空ける。また、主記憶に余裕が生じたときやブロックされていたプロセスが起床した場合などに、スワップアウトされていたプロセスをスワップインする。[Stallings, 396] [Stallings, 370]

多くのシステムではスワップアウトが発生する前にページ置換アルゴリズムが働いて主記憶の空き容量を増やそうとする。そのため、中期スケジューラはある意味で長期スケジューラとも呼べるような位置づけとなっている。ページ置換は一般に特定のプロセスの使用している全メモリを一度に解放するような動作はせず、システム全体で使用頻度の低いページをターゲットとする。そのように置換されて対応する物理メモリのなくなった仮想ページへのアクセスはページフォールトを発生し、例外処理の延長でページインが行われる。実際、スワップアウトが発生するほどメモリ容量が逼迫する状況では、システムは設計段階で予定されていた性能を発揮できない可能性が高く、なるべくページ置換で済むようにメモリ負荷の事前予測を立てるのが通例である。

短期スケジューラ

短期スケジューラ(またはディスパッチャ)は、実行可能状態でメモリ上にあるプロセス群の中で次に実行すべき(CPUを割り当てるべき)プロセスを決定する。そのタイミングとしては、クロック割り込み、I/O割り込み、システムコール、その他の何らかの契機がある。従って、短期スケジューラは長期/中期スケジューラよりも頻繁にスケジューリングを行っている。少なくともタイムスライス毎にスケジューリング処理が行われる可能性があり、その間隔は非常に短い。プリエンプティブなスケジューラでは、プロセスを切り替える必要があると判断したときには強制的にディスパッチを行う。一方、非プリエンプティブなスケジューラでは強制的にディスパッチすることはなく、実行中のプロセスが何らかの資源を待つためにブロックするかプログラム上明示的にプロセッサを明け渡したときだけディスパッチを行う。[Stallings, 396]

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

スケジューリングアルゴリズムは、ポリシーに従って同時かつ非同期に要求されるリソースを分配するアルゴリズムである。スレッドやプロセスにCPU時間を分配するスケジューリングアルゴリズムだけでなく、パケットのトラフィックを制御するルーターのスケジューリングアルゴリズム、ハードディスクへのリード/ライト要求に関するスケジューリングアルゴリズムなどがある。

スケジューリングアルゴリズムの主要な目的は、リソーススタベーションを無くし、リソースの使用者間で公平さを保証することである。

主なスケジューリング方式

よく知られているスケジューリングアルゴリズムには以下のようなものがある。

  • FIFO(First In, First Out) - スケジューリング方式としては、First Come First Served (FCFS) とも呼ばれる。最も単純なスケジューリング方式であり、バッチ処理は本来このスケジューリング方式である。
  • LIFO(Last In, First Out) - 公平性に問題があるため、ほとんど使われない。
  • ラウンドロビンスケジューリング (RR) - 最も基本的なスケジューリングアルゴリズム
  • 多段フィードバックキュー - UNIXの基本的なスケジューリングアルゴリズム

リアルタイムオペレーティングシステムのスケジューリングアルゴリズムには以下のようなものがある。

以下は、大規模システムで基本的なスケジューリングアルゴリズムに加えて実装されることがある手法である。

  • フェアシェアスケジューリング - 例えばユーザー毎にCPU時間の占有率を予め設定しておき、それに従ってスケジューリングする方式。同じユーザーを所有者とするプロセスが複数存在する場合、それらプロセス群にユーザーのCPU時間を平等に分配するのが一般的。
  • ギャングスケジューリング - 関連するスレッドやプロセスをなるべく同時並行的に複数のプロセッサで実行されるようにスケジュールする方式。スレッド間やプロセス間の通信が迅速に行えるため、通信の応答を待ってブロックすることが少なくなり、結果として性能が向上する。ただし、使い方を誤るとリソーススタベーションを生じる危険がある。

稀に優先度以外の属性を選択基準とするスケジューリング方式が使われることがある。これらをポリシーとして優先度決定の際に考慮することもある。ただし、SRTは事前にプロセスの完了までにかかる時間を予測しなければならないので、ほとんど使われない。

  • Shortest Job Next (SJN) - 累積実行時間が短いプロセスを優先してスケジュールする。I/OバウンドのプロセスがCPUバウンドのプロセスに比較して優先されることになる。
  • Shortest Remaining Time (SRT) - 完了までにかかる(と予想される)時間の短いプロセスを優先してスケジュールする。

また、仮想記憶に対応したスケジューリングアルゴリズムとして Two-level scheduling がある。例えば、実装メモリ容量が少なく、50個のプロセスのうち40個がスワップアウトされたシステムがあるとする。いずれもブロックされていないなら単純なスケジューラがディスパッチ先として選択するプロセスは80%の確率でスワップアウトされており、そのままでは頻繁にスワップアウトとスワップインが繰り返される。Two-Level scheduling では、スワップアウトされていないプロセスを優先的にスケジュールすることでシステムの稼動効率を向上させる。

主なディスクI/Oのスケジューリング方式

  • FIFO(First In, First Out) - 単純にI/O要求を受け付けた順に処理する。
  • Shortest Seek First - シーク時間が最も短くなるようにスケジュールする方式。
  • Elevator Algorithm - ヘッドをシリンダ番号の昇順か降順に動作させるものとし、その順番にあうようにスケジュールする方式。
  • Anticipatory Scheduling - LinuxのI/Oスケジューラの方式

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

スケジューリングにおいて、リアルタイム制約を満たすということは以下のどちらかを指す。

  • 優先度逆転問題を防ぐ。
  • タスクのリアルタイム制約を守れることを保証する。

後者についての研究はさかんに行われているが、 スケジューリングが複雑になるために実際のシステムで利用されることは極めて少ない。

マルチプロセッシングでのスケジューリング

マルチプロセッシングでは、各プロセッサをなるべく平等に使用するようスケジューリングするのが一般的である。スケジューリングをプロセッサ単位に行う方式とシステム全体で行う方式があり、前者ではプロセッサ毎の実行可能プロセスのキューが存在し、後者ではシステムに唯一の実行可能プロセスキューが存在する。システム全体の方が優先順位の逆転が発生しにくく、プロセッサ間の負荷バランスをとりやすいという利点がある。しかし、実行効率を考えた場合、各プロセッサのキャッシュメモリの内容などを生かすにはプロセスはなるべく同じプロセッサ上で実行された方がよい。この性質をアフィニティ(Affinity)と呼ぶ。そのため、プロセッサ単位のスケジューラを使用し、負荷バランスが大きく崩れたときだけ調整を行う方式を採用するシステムもある(Linuxなど)。また、システム全体をひとつのスケジューラで制御しようとすると、実行可能プロセスキューへのアクセスで衝突が発生し性能が低下するという問題もある。

NUMAでは、SMPシステムが相互接続されている。このSMPシステム間でのプロセスの移動はSMP内よりもさらに性能に悪影響を与える。そのため各SMPシステムでスケジューラを動作させ、SMPノード間の負荷バランスは別途調整するのが一般的である。Linuxではexec()によるオーバーレイの際にバランス調整を行う。exec()ではプロセスのアドレス空間の内容が置き換えられるので、ノード間の移動をさせるのにちょうどよいタイミングと言える。

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

当然のことながら、OSの数だけスケジューリング方式がある。

初期のMS-DOSやWindowsシステムはマルチタスクではないので、スケジューラも存在しなかった。

Windows 3.1系のOSは単純な非プリエンプティブ・スケジューラを使用しており、プログラマはプロセスが明示的にCPUを明け渡す(yield)ように設計してCPU時間を他のプロセスに使わせる必要があった。これにより基本的なマルチタスクをサポートしていたが、高度なスケジューリング機能とは言えない。

Windows NT 4.0系のOSは単純な優先度付きラウンドロビン方式のプリエンプティブ・スケジューラを使用している。優先度は 1 から 31 であり、1 から 15 がノーマル優先度、16 から 31 がリアルタイム優先度と呼ばれている。リアルタイム優先度はアドミニストレータ特権がないと設定できない。なお、Windows のスケジューラはRTOSのようなスケジューリング方式を採用しているわけではないので、「リアルタイム」という言葉は若干語弊がある。ユーザーは "ALT+CTRL+DEL" で起動されるタスクマネージャで各プロセスの優先度を5段階に設定できる。次に実行すべきプロセスとしては、ラウンドロビン方式で最も優先度が高くキューの先頭に近いプロセスを選択する。従って、プロセスA、B、C が同じ優先度でこの順番で待っている場合、A→B→C の順にディスパッチする。また、それらより低い優先度で実行可能状態のプロセスがある場合、A、B、C全てが何らかのリソース待ちになるなどして実行可能状態でなくなったときだけディスパッチされる。低優先度のプロセスがCPU時間を全く得られない状況を回避するため、NTのスケジューラは3秒以上実行されていないプロセスの優先度を一時的に上げて、実行可能キューの先頭に移動させ、通常よりも長いタイムスライスを割り当てる。

初期のUNIXの実装では、多段フィードバックキュー方式のスケジューラを使用しており、各フィードバックキューはラウンドロビン方式になっていた。このシステムでは、プロセスが生成されると最高優先度のキューに置かれる(新しいプロセスの応答性能を良くして、マウスやキー入力への反応を良くするため)。プロセスがCPU時間を消費していくと、プリエンプションが発生して徐々に優先度が下がっていき、最終的に最低優先度のキューに置かれることになる。この方式では長期間生存しているプロセスは必ず最低優先度に落ち着くことになり、新たなプロセスが生成され続けるとリソーススタベーションが発生し易い。UNIXでは40段階の優先度を明示的に設定できる。これをNICE値と呼ぶ。NICE値は変動する優先度に下駄を履かせるように作用する。最近のUNIX系OSでは内部的にもっと多段階の優先度を使用している(Solarisでは160)。前述のNTスケジューラのスタベーション回避方法とは異なり、UNIXではもっと巧妙なエージング方式を使用する。優先度が低く長時間実行されていないプロセスは徐々に優先度を上げられ、再度実行されるようになる。

参考文献

関連項目

外部リンク

いずれも英文

Template:オペレーティングシステムca:Planificador cs:Plánování procesů de:Prozess-Scheduler el:Χρονοπρογραμματισμός en:Scheduling (computing) es:Planificador et:Ressursijaotus fr:Ordonnancement dans les systèmes d'exploitation it:Scheduler ko:CPU 스케줄링 nl:Scheduling pl:Algorytm szeregowania pt:Escalonamento de processos ru:Диспетчер операционной системы sl:Urnik uk:Планувальник операційної системи zh:排程

"http://ictmax.org/mediawiki/index.php/%E3%82%B9%E3%82%B1%E3%82%B8%E3%83%A5%E3%83%BC%E3%83%AA%E3%83%B3%E3%82%B0" より作成
個人用ツール