成蹊大学理工学研究報告
J. Fac. Sci. Tech., Seikei Univ.
Vol.45 No.１ (2008) pp.5-12

タスクスケジューリングのための GUI ツールの開発
色川恵理*1，石岡秀基*2，甲斐 宗徳*3

Development of a GUI tool supporting Task Scheduling
Eri IROKAWA＊1, Hideki ISHIOKA＊2, Munenori KAI＊3,
ABSTRACT：In this paper, we propose a very useful GUI tool to construct some algorithms to solve anytask scheduling problems. In the past works in order to construct algorithms to solve task schedulingproblems, we had to draw task graphs to know their parallelism structure, and draw Gantt-charts toanalyze and adjust the scheduling results. The GUI tool for task scheduling which we designed andimplemented can visualize both task graphs and Gantt-charts automatically, and make them cooperate toevaluate and reconstruct task scheduling algorithms.
Keywords：task scheduling, GUI tool, task graph, Gantt chart（Received March 25, 2008）

１．はじめにるが，実際には，実用的な時間で最適解を得ることはほとんど不可能である。そこで，プログラムを解析し，並近年のプロセッサは，大量の計算処理を高速に行うた列実行可能なタスク集合を見つけて，そのタスク集合のめに改良されているが，単一プロセッサの処理能力の向プロセッサへの割り当て方を考察する，すなわち，探索上には限度があるといわれている。しかし，コンピューにヒューリスティックを組み合わせたスケジューリング

タを使用するアプリケーションは，より大規模化・複雑手法というものが１つのキーポイントとなる。

化し，計算量が増えつつある。そこで，処理を高速化す

このようにスケジューリングの良し悪しが並列処理のるために，プロセッサを複数台使用して一つの巨大な計効率を左右する一因となるが，そのアルゴリズムを構築算機のように動くマルチプロセッサシステムの研究がハするためにはタスクグラフの形状や暫定解の見直しによードウエア，ソフトウェアの両面で進められている。こるヒューリスティックの考察が必要である。従来はタスのような，マルチプロセッサシステムで適切な負荷分散クグラフやガントチャートを人手により作成して考察しを行い，処理の高速化を実現するためには，プログラムていたが，多数のタスク集合を材料にしてスケジューリを解析し並列実行可能なタスク集合を見つけ，個々のタングアルゴリズムを練り上げるために，大いに手間と時スクを適切なプロセッサに割り当てるためのスケジュー間がかかる状況にあった。そこで本研究では，スケジュリング手法が，重要なキーポイントになる。しかし，こーリングアルゴリズムや必要なヒューリスティックを考のスケジューリング問題は，強 NP 困難なクラスに属す察する手助けとするためにタスクグラフとガントチャー組み合わせ最適化問題であり，大規模タスクグラフにおトを自動で表示し，さらにスケジューリングアルゴリズいて，最適解を求めることは事実上困難である。そのたムの改善に役に立つ GUI ツールの開発を行った。

め，実用的な時間内で，最適または近似解を求めるスケ２．タスクグラフとガントチャート

ジューリング手法が提案されているが，これは，人間の経験に基づく，ヒューリスティックアルゴリズムである

2. 1 タスクグラフ

ため，得られた解が最適解であるという保証はない。ま

１つのプログラムはタスクの集合である。タスク集合

た，全探索アルゴリズムでは，理論的には最適解が求まは，タスクをノード，先行制約を有向エッジで表した無*1：工学研究科情報処理専攻修士学生：工学部経営・情報工学科学生*3：工学研究科情報処理専攻教授 (kai@is.seikei.ac.jp)

サイクル有向グラフで表現できる。このグラフをタスク*2グラフと呼ぶ。図 2.1 がタスクグラフの図で，ノードの－5－

中の数字がタスク番号，ノード脇の数字がタスクの実行余地をスケジューリング結果から見出したりすることが時間を示している。

難しいということである。
スケジューリング結果はどのタスクが，どのプロセッ

タスクスケジューリング問題とは，このようなタスクグラフの各タスクを与えられた個数のプロセッサに並列サにどの時刻で割り当てられているかという情報であり，処理時間を最小にすることを目的にして割り当てを決定

例えば図 3.1 のような数字の羅列で表現されている。こすることである。

れを見ているだけでは図 2.1 や図 2.2 のような図のイメージをつかむことは難しい。以前は図 3.1 のようなスケジューリング結果を元に人手でタスクグラフやガントチ

2. 2 ガントチャート
ガントチャートとは，タスクスケジューリング結果，ャートを作成し，得られた並列処理スケジュールの良しすなわちタスクのプロセッサへの割り当て結果を図示し悪しを考察していたので作業効率が低かった。そこで，たものであり，どのタスクをどのタイミングでどのプロタスクグラフやガントチャートを表示するツールで図セッサに割り当てるかを可視化したものである。図 2.2

3.1 のような結果情報を読み込み，自動的に視覚化するのガントチャートは，図 2.1 のタスクグラフのスケジュことで手間をかけずに正確なグラフを確認することが出ーリング結果の例を図示したものである。

来るようになる。

016662５５5400４４77344766タスクグラフ

ガントチャート

7020
16102310
3 10 1 14 10 1 15 12 2 1 26 10 3 3 4 52010

0001356
240 2 8 19 314 14
2 5 7 124 6 24 6

図 3.1 ツール用データフォーマット(一部)

図 2.1 タスクグラフ

また，タスクに関する情報を表示する機能を追加することで，通信や先行タスクの確認などが可能になる。さらにタスクを移動する機能や部分的スケジューリング機

１CPU1４能を利用し，手動でタスクを操作してスケジューリング６を調整することでさらに良い解が見つかる可能性がある。
既存のアルゴリズムのみでは発見できなかったが，人に２CPU2３よる操作や考察を加えてさらに良い解を発見しその手法５をアルゴリズムに反映させる，などの新たなヒューリス
ティック解法の発見の助けにもなる。
0５10152520時間→

3. 1 ツール概観

図 2.2 ガントチャート

図 3.2 に示すように，タスクグラフとガントチャートを同時に参照するために複数ウィンドウを起動させ，そ３．タスクスケジューリング用 GUI ツール[2][3]

れぞれにタスクグラフとガントチャートを表示させるマルチウィンドウ方式で作成している。これにより，ガン

これまで，スケジューリングを行う上で問題になってトチャートとタスクグラフが一括して表示できるだけでいたことが二つある。一つは探索により最適解を見つけなく，それぞれを連携させた機能を持たせることも可能るまでに時間がかかってしまう事である。もう一つは実になる。

用的な時間内でスケジューリング結果を求めた際にその解が最適解にどれだけ近いのかを評価したり解の改善の－6－

図3.4 タスク5 選択(グラフ一部)
図 3.2 補助ツール概観

ィレベルを求めるにはスケジューリングと同様に探索問題を解かねばならないため，ここでは通信時間を無3. 2 タスクグラフツールの基本機能視している。このようなプライオリティレベルを，ノ①

拡大，縮小機能ードを表示する位置に反映することで大体同じ時期にタスクグラフ上部にある入力フォームに数字を入力並列して処理を行うべきタスクを確認することが出来すると，その値の倍率でタスクグラフを再描画する。

る。

また，メニューバーにも倍率変更メニューが存在し，タスク数が増加すると，タスク間のエッジが重なっそちらからでも倍率変更が可能となっている(図 3.3てしまうなどして，見難くなってしまうことがある。

参照)。この機能で倍率を調整し，タスクグラフの必要

この時，グラフを見やすくするためにタスクをドラッな部分を拡大したり全体表示するために縮小したりなグ＆ドロップして任意の場所に移動することができる。

どの調整ができる。

そのときタスクの先行エッジが赤い色に，後続エッジが青い色に変化する（図 3.4 参照）。ただし手動による移動では，プライオリティレベルを反映した位置に必ずしも配置できない場合が起こり得る。例えば図 3.4のようにタスク５のプライオリティレベルが 22 だが，手動でタスクを動かした為にプライオリティレベル20 のタスク３や４よりも低い位置になってしまったとする。
このようなときに図 3.5 の PL 反映ボタンは，プライオリティレベルに応じてタスクの縦軸位置を変更させる。また矢印のボタンはタスク間をその方向に

図 3.3 タスクグラフ倍率変更広げたり縮めたりすることが出来る。
②

タスクの適切な配置機能

このようにして，タスクグラフを通じて処理内容の図 3.1 のようなタスクグラフデータに基づく初期描構造的な特徴を容易に捉えることが出来る。

画では，タスクを表すノードの位置は，先行関係を考また元に戻したい場合には，メニューを選択すると慮しながら縦軸方向は上からプライオリティレベルのタスクの配置のみを戻す機能と，配置・倍率を戻す機高い順に，横軸方向はほぼ等しいプライオリティレベルを持つタスクを一定間隔で配置する。プライオリテ
ィレベルとは，あるタスクから出口ノードが終了するまでの処理時間の下限値である。入口ノードのプライオリティレベルは並列実行時間の下限値になっているが，通信時間は考慮されていない。通信を考慮するとクリティカルパス長に事実上通信時間が影響を及ぼす場合があり，その分だけ本当のプライオリティレベル
図 3.5は大きくなる。しかし，通信を考慮したプライオリテ－7－

タスクグラフ配置変図3.6ではタスク4をクリックしており，タスク4の先行能を実行できるようにした(図 3.5 参照)。
③マクロタスクグラフの描画[4]

タスク1が青く変化し，タスク１の先行タスクである０タスクの中でも階層的にタスクを含むようなタスクが緑色に変化している。また，タスク１から４への通をマクロタスクと呼ぶ。すなわちマクロタスクは１つ信が赤いラインで，タスク４から６への通信が灰色ののプログラムを構成するタスク X の中に X を構成するラインで描かれており，通信が発生する先行タスクや複数のタスクが存在することを示す。そして上位層と後続タスクもわかるようになっている(図3.8参照)。

同様に，このタスク X を構成するタスク間には先行制先行タスクが解る事で，もし通信を必要としない位約があり，その先行関係を表したものがマクロタスクグラフである。
マクロタスクは通常タスクとは違い青い色で表示されており，それをダブルクリックすることでそのマクロタスク用のタスクグラフを読み込み，新たなウィン
図 3.8 選択タスクドウで表示する。

置にタスクを移動することが可能なら，それにより通信の削除などが出来る。また，後続タスクに関しても

3. 3 ガントチャートツールの基本機能[5]図 3.6 はガントチャートの概観である。スケジューリ同じことが言える。指定したタスクから発生している

ング結果ファイルを読み込むと，このようなガントチャ通信を削除できるような位置にタスクを配置できれば，ートが表示される。

通信による後続タスクの実行開始の遅れを除去できる。
先行制約の流れ上にある全てのタスクはなるべく同じ CPU に割り当てることで，通信を発生させずに実行が出来る。その為先行タスクや通信の情報はタスクを手動で再割り当てをする場合にこの機能が重要になってくる。
③

通信時間表示通信時間表示チェックボックスにチェックをいれると，全ての通信時間を赤いラインで表示する(図 3.9参照)。チェックボックスにチェックが入っている間は必ず通信時間が表示され続ける。

図 3.6 ガントチャート概観①

拡大，縮小機能
ガントチャート上部にある入力フォームに数字を入力すると，その値の倍率でガントチャートを表示する(図 3.7 参照)。

図 3.7 倍率変更と全体通信時間表示
図 3.6 では全体像がウィンドウ内に収まっているが，図 3.9 通信時間表示

CPU 数が多い場合やタスク数が多くて全体が見られここでは，CPU がデータの送受信とタスクの計算はない場合にこの縮小機能を使えば全体が一見できる。
②

先行タスクの表示

同時に実行ができるが，送信同士または受信同士は同あるタスクをクリックすると，そのタスクの先行タ時には行うことが出来ないことを前提としている。しスク，先行タスクのさらに先行タスクを色を分けて表たがって，あるタスクが複数の先行タスクを持ち，そ示する。同時に，そのタスクに関係した通信情報も表れらが別の CPU に割り当てられている場合はそれら示する。受信情報は赤，送信情報は灰色で表示する。の通信は逐次的に処理されることになる。スケジュー－8－

リング結果では，全ての先行タスクからの受信完了以クにより影響を受ける後続タスクを始めとする全ての降にそのタスクの開始時刻が定められており，それをタスクの配置も再計算され，描画し直される。
⑤

ガントチャートで確認することが出来る。
④

変更データの保存再割り当てなどで変更されたスケジューリング結果

タスク移動による再割り当て機能を新たにファイル名をつけて保存する。

タスクをドラッグ＆ドロップして，移動したい場所⑥にタスクを置く事により，指定した CPU および時刻にタスク初期配置タスクの割り当てを変更する機能である。先行制約とタスクを最初の状態に戻す機能である。この場合の通信の配置を考慮して割り当て位置の再計算が行われ最初とは，ガントチャートウィンドウが表示されたとる。

きの最初のスケジューリング内容を示す。

また，ドラッグ＆ドロップではなくクリックしたタ
3. 4 ガントチャートとタスクグラフの連携

スクを次のように指定する方法で再計算する手段も準ガントチャート，タスクグラフをそれぞれで表示する備した。ガントチャートの下部にある移動先 CPU 欄に移動先 CPU，移動先座標欄に時刻を入力し，移動ボタだけであれば，一つにまとめる必要は無い。このツール

ンを押すと選択済みのタスクをその場所に移動するこの最大の特徴の一つに，ガントチャートとタスクグラフとが出来る（図 3.10 参照）。の表示を連携させる機能がある。
①

クリティカルパス表示
タスクグラフでクリティカルパスを表示すると，ガ

図 3.10 タスク移動指定バー

ントチャートでクリティカルパスのタスクの色を変化させる(図 3.12 参照)。

タスクを移動するとそれに伴い後続タスクが，通信や処理の開始時刻が再計算されて正しく配置される。
図 3.11 は図 3.6 の状態からタスク３を CPU1 からCPU2 に移動させている。

図 3.12 クリティカルパス
クリティカルパスの情報はタスクグラフが持っている。
したがって，クリティカルパスの表示をする度にクリティカルパスのタスク情報をガントチャート側に送信
図 3.11 タスク 3 の移動する。ガントチャートではその情報を元にクリティカ

この機能により，今表示されているスケジューリン

ルパスのタスクの色を変化させる。これにより，クリグ結果から特定のタスクを別の CPU や時間に移動しティカルパスのタスクがどの CPU に割り当てられてた場合の情報を作成して確認，考察することができる。

いるのかが一見してわかる。クリティカルパス長は並割り当ての際，もし指定したタスクの処理開始時刻列実行時間の下限値であるから，そのパス上のタスクが先行制約の関係上その時間に配置することが出来なが同じ CPU に割り当てられていないと，通信の発生にい場合がある。このときは移動先の CPU で一番早い配より明らかに実行時間がクリティカルパス長より長く置可能な時間に実行開始時刻を自動設定する。すでになる，といったことが確認できる。
②

別のタスクが割り当てられている場所に割り当てよう

CPU・時間軸での表示とした場合は，タスク情報の再計算の際にその割り当

ガントチャート上で CPU，時間軸をクリックした場て済みのタスクの終了後に実行を開始するように移動合にはタスクグラフ上でもそのタスクの色が変化する。

するタスクの実行開始時刻を変更する。移動したタス－9－

（Critical Path/Most Immediate Successors First 法[1]）を使っている。これは通信を考慮していないヒューリス
ティックアルゴリズムで，リストスケジューリングの中で割り当てタスクを選択する際に，タスクに優先順位を決めて利用するものである。すなわち，レディタスク数がアイドル CPU 数より多いとき，どのレディタスクから優先的に割り当てるかを選ぶために次のようなヒューリスティックを用いる。
１）各タスクから出口ノードまでの最長パス長を計算する。
２）最長パス長の大きい順にプライオリティリストを図 3.13 CPU1 選択時作る。
図 3.13 では，ガントチャート上で CPU１をクリック

３）もし最長パス長が等しければ，その中で直接後続している。すると，ガントチャートでは CPU1 に割りタスクの多い順に，プライオリティリストを作成する。

当てられた全てのタスクの色が変化して，同時にタス

４）先行タスクの実行が終わり，実行可能（レディ）クグラフにそれらのタスク番号を送信して，タスクグとなったタスクのうちで，プライオリティリストにラフ上でも同一 CPU に割り当てられているタスクをおける順位が高いものから，空いているプロセッサ一覧できる。この色の変化は CPU をクリックしている（アイドルプロセッサ）に割当てる。このとき，レ間続き，マウスのボタンを離すと元の表示に戻る。

ディタスクが存在するかぎり，プロセッサをアイドル状態のままにしておくようなことはしない。

タスクの少ない状態ではこの機能はあまり必要性を③

感じられないかもしれないが，タスク数や CPU 数が増

全体スケジューリングにヒューリスティックを用いえるとどのタスクがどこで実行されていて，タスク実て探索解法を行わないのは，単純に処理時間を短く抑え行がどの様な流れになっているのかが分かり易くなる。

るためである。また部分スケジューリングの方はタスクリストスケジューリングを手動で移動する作業を行った後，残りのタスクについ通信を考慮せず，探索を行わないでヒューリスティて簡単なスケジューリングを適応したい場合に役立つ。

ックのみに基づいたスケジューリングを行う。ツール
3. 5 タスクスケジューリングのリアルタイム表示のリストスケジューリングには二種類あり，全体をスタスクスケジューリングの解は，分枝限定法のようなケジューリングするものと選択したタスク以降を再スケジューリングするものがある。

全探索により求められるが，膨大な処理時間がかかるた

タスクグラフ側にあるスケジューリングボタンを押

め探索の初期段階でできるだけ良い解にたどり着けるよ

すと，左側の入力フォームの CPU 数で全体をスケジュうにヒューリスティックを入れることが多い。そのヒューリングし，その結果を新しいウィンドウでガントチーリスティックが実際にどのくらい効いているかを調べャートに表示する。(図 3.14 参照)

るためには，タスクスケジューリングの解を探索する上で，どのような順番で探索がされ，枝切りを行ったかなどの情報はとても重要である。
そのような情報をスケジューリングプログラムから貰い，リアルタイムで表示する機能を加えた。この機能に

図 3.14 全体スケジューリング(タスクグラフ)

より，スケジューリングプログラムがどの様に暫定解をガントチャート側にあるスケジューリングボタンで出しているのか，その流れが判るようになり，探索アルは，ガントチャートでクリックして選択したタスクよゴリズムを改善する上での補助になる。

りも後の時刻に始まるタスク全てを再スケジューリン

3. 5. 1 スケジューリングプログラム側処理グするようになっている。もし選択したタスクと同時スケジューリングプログラム側は DF/IHS 法[1]を使い，刻に始まるタスクが存在した場合にはそのタスクも再解の探索を行う。DF/IHS 法は CP/MISF 法のヒューリススケジューリングの対象となる。

ティック効果を，分枝限定法（Branch & Bound）に取り入れた，ヒューリスティックな探索アルゴリズムである。

スケジューリングアルゴリズムには CP/MISF 法－10－ューリング法と CP/MISF 法を使ってスケジューリングを行った。
リストスケジューリングを行った場合，図 4.2 のようなスケジューリング結果となり，CP/MISF 法を使うと図4.3 のスケジューリング結果となる。

図 3.15 探索プログラムとの連係機能
スケジューリング側は探索中に暫定解が得られる度にその結果を図 3.1 の右側のようなフォーマットで本研究のツールに送信してもらう。
3. 5. 2 ツール側処理
図 3.15 は本ツールがスケジューリングプログラムと通信中の一例である。スケジューリングプログラム側か
ら暫定解のデータを受信するのを待ち，受信したらそれをガントチャートで表示する。表示が終わったらまた受図 4.1 使用タスクグラフ

信待ちになる。以上をスケジューリング側から探索終了の合図が送られてくるまで続ける。スケジューリング側から受信したファイルはユーザの指定する場所に自動で名前をつけてテキスト形式で保存する。ツールはユーザが指定した数(1～10 枚)だけウィンドウを複数表示し，暫定解で何処が改善されたのかを確認することが出来る。
暫定解は自動で割り振られたウィンドウの番号の順番で書き換えられてゆくが，ウィンドウ上部の『表示固定』チェックボックスにチェックをいれることでそのウィンドウの情報の書き換えをしないようにすることが出来る。
また，暫定解の情報の書き換えが速く，チェックをする
余裕がない場合はメインウィンドウの上部にある入力フ

図 4.2 リストスケジューリングによる結果ォームにあらかじめ整数値を入力する。すると，その番号の暫定解は固定され，情報が上書きされないようになる。これにより基準のデータを決めて，そこから次の暫定解がどこを改善したのか，という情報を得ることが出来る。

４．評価

ツールの評価のために，既存のヒューリスティックを二つ取り上げ，それらのスケジューリング結果を比較する。
一つはリストスケジューリング，もう一つは CP/MISF法である。後者は前者を改善したアルゴリズムであり，その改善点を本ツールで明らかに出来ることを示す。こ図 4.3

こでは，図 4.1 のタスクグラフを利用し，リストスケジ－11－

CP/MISF 法による結果ルゴリズムを改善する手助けになる。今後はスケジュー

図 4.2 と図 4.3 ではタスク３とタスク５の割り当てがリングプログラムとの連携を重視した開発が必要となっ全く異なる。
リストスケジューリングではタスク番順に割り当てててくるだろう。スケジューリング側からデータをもらっいるので，タスク５の割り当ては後回しなるが，CP/MISFてきて表示するだけではなく，途中結果を確認してユー法では出口ノードまでの最長パス長の長い順にタスクをザ側で手動のタスク移動などで変更した順番をスケジュ割り当てているので，タスク５のプライオリティレベルーリング側に送信，その情報を元にスケジューリングをの高さにより割り当てが早くなっているからである。リ進めるなどの連携が考えられる。

ストスケジューリングから CP/MISF 法へと近づけるた

参考文献

めに，まず全体の実行時間が延びている原因を調べる。
タスクの通信情報や先行タスク関係を確認すると，タス
ク５の先行タスクがタスク１とタスク２であることが分[1] 笠原博徳：“並列処理技術”， コロナ社，1991

かる。つまり，タスク１とタスク５の間にタスク４が入[2] 牧野勝好，宝達真吾：“タスクスケジューリング用ってしまっているためにタスク５の実行開始が遅れていGUI 環境の製作”,2005 年度成蹊大学工学部卒業論文

ることが分かる。そこで，タスク４をタスク５の後ろに[3] 野本利信：“タスクスケジューリング補助ツールの開移動する。また，通信時間を確認すると，タスク５から発・拡張―タスクグラフのマルチウィンドウ表示とタスク６への通信時間は他の通信に比べて長い。この通GUI 機能の拡張―”，2006 年度成蹊大学工学部卒業論

信はなるべく避けたいので，タスク５は CPU1 に移動さ文せる。そして，この場合にはタスク５の処理をタスク３[4] 大藪俊通：“タスクスケジューリング補助ツールの開よりも先行させる必要があることが分かり，ガントチャ発・拡張 ―タスクグラフのマルチウィンドウ表示とートおよびタスクグラフに表示されている情報から，プGUI 機能の拡張―”，2006 年度成蹊大学工学部卒業論

ライオリティレベルの高いタスクを先に割り当てるべき

文[5] 高山翔：“タスクスケジューリング補助ツールの開であることが分かることになる。
このようにして通信時間や先行タスクを確認し，タス発・拡張 ―タスクグラフ情報ファイル出力とガントクを移動させてゆくことによってより良い解を探し出す

チャート追加機能の実装－”，2006 年度成蹊大学工学

ことが出来る。

部卒業論文

以上より，ツールがスケジューリングの考察の手助けけが出来ることが確認できた。

５．おわりに従来，独立していたタスクグラフ描画ツールとガントチャートツールを統合し，それぞれのツールの連携をとることができた。このツールの開発により，タスク情報やスケジューリング結果を確認しながら手動でのスケジューリングの考察が簡単になった。また，リストスケジ
ューリング機能とガントチャートのタスク再割り当て機能により，手動による再スケジューリングも可能になった。たとえば，プライオリティレベルの近いタスクが並列に処理されているかどうかをタスクグラフやガントチ
ャートで確認し，もし並列ではないのであればそこを改善すればより良い解が求まる可能性が高くなる。
また，スケジューリングプログラムと通信し，その暫定解の流れをガントチャートで確認することで視覚的に現在のアルゴリズムの解法を確認することが出来る。そうすることで新たにヒューリスティックな考察をしてア－12－