GANGスケジューリング

GANGスケジューリング（ギャングスケジューリング, GANG scheduling）とは、複数のノードにまたがったタスクを同時にスケジューリングする仕組みのことである。co-schedulingとも呼ばれる。

主にスパコンや並列サーバー環境でバッチジョブを同時実行するために使われる。

必要性

通常CPU上で動くタスクをスケジューリングする際は、それぞれのタスクを個別に止めたり再開させたりしてコンテキストスイッチする。しかし、複数ノード（複数のマシン）で同時に動作するような並列アプリケーションは、通信や同期を行っているため、それぞれのノードで当該タスクをバラバラに長時間停止すると正常に動作しなくなる。よって、ノードのスケジューラー同士が協調して複数のタスク（ギャング=徒党）を一斉に止めたり再開させたりする必要がある。

そのほかにも、同時実効性の必要は無いがデッドロックを抑えたい時にも使われる。

Ousterhout matrix

GANGスケジューリングの様子を洗わず方法としてOusterhout matrixという行列がある。

table:ousterhout

P1 P2 P3 P4 P5

Time Slice 0 J1 J1 J1 J1 J1

Time Slice 1 J2 J2 J2 J2 J2

Time Slice 2 J3 J3 J4 J4 J4

... ... ... ... ... ...

各行はTime Slice（単位時間）を表し、下に行くほど時間が経っていくことになる。一番最後のTime Sliceが完了するとTime Slice 0に戻る。

各列はプロセッサ（CPU、ノード、コア）であり、今回は全部で5つコアがある。一つ一つのマスはセルを呼ぶ。

J1~J4はジョブである。J1は5つのタスク（プロセス）が並列して動き、J3は2つが並列して動くようなジョブである。

この表を見ると、まずTime Slice 0の瞬間には5つのプロセッサ全てをJ1のタスクが全て占有し、次の瞬間にはJ2が占有する。その次にはJ3とJ4がそれぞれ2つと3つずつ占有してコアを使うことになる。

GANGスケジューリングではこの表を効率的に作成し、各ノードが遂行するのが目的となる。

種類

GANGスケジューリングの実際の実装方法として、複数のアルゴリズムがある。

各アルゴリズムはまず最初に空のOusterhout matrixを作成してから、各行に対して待ちジョブをどうやって埋めていくかを考える。

Bag of Gangs (BoG)

Adapted first come first served (AFCFS)

いわゆるFIFO（First-In-First-Out）と同じで、待ちジョブの一番先頭にあるジョブを使って空き行を埋める。ただし、空いているセルの合計がジョブの要求プロセッサ数より少ない場合はそのジョブをスキップして次のジョブを検討する。このアルゴリズムは大きなジョブより小さなジョブを先に採用するためシステムが断片化してしまう（=開いてしまう無駄なセルが多くなる）

Largest gang first served (LGFS)

待ちジョブのうち最も大きいジョブから優先的に埋めていく。小さいジョブがなかなか実行されないというデメリットがあるためプロセッサ数が少ないシステムには適さない。

Paired gang scheduling

CPU boundなジョブとI/O boundなジョブを同時に1つのプロセッサに割り当てることで、HyperThreadingのような環境下でCPUの利用効率を向上させる。

参考文献: