技術部門: スレッド移送とその負荷分散への応用
代表: 首藤 一幸
早稲田大学 村岡研究室 分散コンピューティング班
compiler@muraoka.info.waseda.ac.jp


1.応募の技術的主張の概要

Java仮想マシン (JVM) をまたいだスレッド移送を実現した。 移動エージェントの記述、スレッド外部化を利用しての耐故障 性向上、負荷分散などへの応用が考えられる。このスレッド移 送システム MOBA [1] [2] の上で、スレッド群の可視化、操作 ツール MOBAio、負荷分散システムを開発した。また、 これら 3者間の通信には、新たに開発した Object Request Broker(ORB) RyORB を利用している。


2. 応募の背景

2.1 移動エージェントシステム

Aglets[3]、 Voyager[4]、 Kafka[5]など Java で実現された既存の移動エージェントシステムでは、エー ジェントを移動させる際に実行コンテクストを伴えない。移動 先ではシステムやプログラムが指定するメソッドが新たに呼び 出される。プログラマは実行のその不連続を意識して、ローカ ルに動作するプログラムとは異なる作法で移動エージェントを プログラミングする必要があった。

2.2 ソフトウェアコンポーネント

Java のソフトウェア部品を扱う枠組として JavaBeans がある。 JavaBeans はオブジェクト群をバイト列化する Object Serializer を必要としている。ところが Java 実行系が持つ シリアライザはスレッドオブジェクトをバイト列化できない。

JavaBeans が MOBA のスレッド外部化を利用できれば、スレッ ドオブジェクトを利用したソフトウェア部品が実現できる。

2.3 耐故障性向上

数週間といった長時間に渡って実行されるプログラムには、不 慮の事故で計算結果を失うことのないように、実行中の状態を 保存、保存した状態から復帰する仕掛けを用意することが一般 的である。この仕掛けはプログラムの目的、本質ではないにも 関わらず、通常そのプログラムに特化したものが必要なのでプ ログラムごとに作る必要があり、手間はとても大きい。

スレッド外部化を利用すると、プログラム実行中の状態をファ イルやデータベースに保存することが可能である。プログラマ を非本質的な作業から解放する。定期的にプログラムのスナッ プショットを保存するデーモンスレッドを用意することで、プ ログラム側は保存について考える必要をなくせる。

2.4 負荷分散

Java で記述されたプログラム、仕事をネットワーク上のマシ ン群に dispatch するシステムは数多く存在するが、一旦実行 を開始した Java プログラムをマシン間で移すことはできない。 すべての仕事を事前に静的にスケジュールしてしまえない場合、 つまり、動的に新たな仕事が発生したり、実行時間の見積りを 精度良く行えない場合、実行中のプログラムをマシン間で移せ ることが役に立つ。


3. 応募の構成・新規性・有用性

スレッド移送システム MOBA およびその上で動作する を開発した。これらコンポーネント間の通信には RyORB を利用している。


図1: MOBA および負荷分散システム

3.1 スレッド移送システム MOBA

スレッド移送システム MOBA を利用することで、JVM 上のスレッドを

移動させることができる。また、移送の際に利用されるスレッ ド外部化を直接行うことで、実行中のスレッドをディスクなど に保存、復帰して実行を再開させることができる。

次の応用が考えられる。

MOBA はすでに公開されている[2]。ソースコードも 入手可能となっている。インストール法、利用法など各種文書 は Web ページを参照のこと。

3.1.1 構成

スレッド移送は次の要素技術で実現されている。 外部化でバイト列化したスレッドをネットワーク越しに転送する。


図2: スレッド移送の要素技術


図3: スレッドの外部化手順

スレッド群が動作する場を MOBA place と呼ぶ。Place はひと つの JVM を占有する。同一マシン上の place 群は TCP のポー ト番号で識別される。


図4: MOBA Place

3.1.2 移動エージェントへの応用

既存の移動エージェントシステムでは移動の際に実行コンテク ストは伴えず、移動先ではシステムやプログラムが指定するメ ソッドが新たに呼び出される。Voyager[4] 1.0 を例にとる。

import COM.objectspace.voyager.*;

public class MobileAgent extends Agent {
  public void callback(Object arg) {
    System.out.println((String)arg);
  }

  public void go(String address /* is  */) {
    moveTo(address, "callback", "Hello.");
    System.out.println(
      "This statement is never executed.");
  }
}
自身が移動するメソッド moveTo() の引数として、 移動先で呼び出すメソッド callback() を指定して いる。moveTo() 呼び出しまでの実行コンテクスト、 すなわち連鎖するスタックフレームが保持するプログラムカウ ンタ、局所変数、スタック上の要素などは破棄される。

MOBA では移動可能なスレッドを移動エージェントとみなす。 通常、スレッドの記述には java.lang.Thread クラ スを使用するところ、代わりに MobaThread クラス を使用する。次のようにスレッド、つまり移動エージェントを生成し

MobaThread t = new MobaThread(...);
t.start();
自身で移動する際は次のようにする。
MobaThread.goTo(移動先計算機);

3.2 可視化, 操作ツール MOBAio

MOBAio は MOBA place 群のユーザインタフェースである。ス レッドの生成、停止、および Drag & Drop による移動が可能 である。


図5: MOBAio の画面

3.3 負荷分散システム

MOBA place ひとつに対して同じマシン上でひとつのデーモン を動作させる。以下、これをノードと呼ぶ。各ノードは、場合 に応じて自らに対応する place 上のスレッドを他 place 上へ 移動させる。

文献[6]のアルゴリ ズムに対して、実際の負荷分散への応用のために足りない点を 補ったものを用いている。集中管理が不要であること、タスク、 すなわちスレッドの起動、移送先を決定する際のメッセージ数 が少ない事が特徴である。ただし、各マシンの負荷だけは 1箇 所で集中管理している。


図6: 負荷分散のアルゴリズム

文献[6]では、アル ゴリズムの応用例として負荷分散が挙げられているが、そこで は、各ノードの負荷を light, medium, heavy とクラス分けで きるという現実的ではない前提が置かれている。このままでは 実際のシステムに応用できない。そこで、負荷情報の扱いにつ いてアルゴリズムを拡張した。

負荷分散は heavy ノードが light ノードを探してタスクを渡 すことでなされる。この処理は次の通り遂行される。

各ノードは一定時間おきにベンチマークプログラムを実行し、 その時点の負荷を表す浮動小数点数を得る。得られた値は、ノー ド集合につきひとつ存在する負荷サーバに送られる。負荷サー バは、ノード群の負荷を集計、各ノードの偏差値を求めてその ノードの点数とする。ノードは、自らがプロセッサ構造の環 (図6 参照)から外れていてなおかつ偏差値が閾値を超えていた 場合に、自ノードで動いているスレッドの他ノードへの移送を 決定する。移送を決定したノードは、より負荷の軽いノードを 探す際に、自らの偏差値に応じて決めた要求偏差値を提示する。 要求より偏差値が良い(低い)ノードを light ノードとみなし て移動先とする。

light ノードの探索過程でノード群の構造を変化させる。環に はなるべく light ノードのみが含まれるように保つことで、 以後の他ノードによる探索コストを低く保てるので、light と みなされなかったノードは環の外のブランチへはじき出す。

この拡張アルゴリズム、負荷分散システムは未評価である。 現在、評価方法から検討している。

3.4 RyORB を用いた各コンポーネント間の通信

MOBA place とユーザインタフェース MOBAio や負荷分散シス テムの通信には、RyORB を利用している。開発中の Java 用 ORB である。

クラスファイルのネットワーク経由ロード、スタブの自動生成、 デーモンが不要など、 RMI[4] や HORB[5] にない特徴を持つ。


4. 応募システムの実行例

MOBA place を制御するために、MOBAio ( 図5) を利用する以外にも telnet を使って place が持つ コマンドインタプリタを使う方法がある。

MOBA place を起動し
% mobaplace -d -c
MOBA place started on cafe.muraoka.info.waseda.ac.jp(133.9.68.49):10000.
Command interpreter is waiting at 10000/tcp.
MobaPlaceController is waiting at 10010/tcp with the name "MobaPlace" via RyORB.
Enjoy!
別の端末から telnet で接続する。
% telnet cafe.muraoka.info.waseda.ac.jp 10000
Welcome to MOBA place on cafe.muraoka.info.waseda.ac.jp(133.9.68.49):10000.
Ready.
help コマンドでコマンド一覧を取得。
help
This shell accepts the following commands.
Shortened form is also acceptable.
The latter in this list is adoptedif the input is vague.
  list
  write threadID key
  read key [key ...]
  stopall
  suspend threadID [ID ...]
  resume threadID [ID ...]
  stop threadID [ID ...]
  start class_name[@host[:port]] [...]
  move threadID destination[:port]
  fork threadID destination[:port]
  name threadID new_name
  property property_name
  run {gc,finalization}
  halt
  quit
  help [command ...]
Ready.
start コマンドで、クラス名を指定してスレッドを 2つ起動。
start Counter
Now start the thread instance of "Counter".
Ready.
start Counter
Now start the thread instance of "Counter".
Ready.
list コマンドで、動作しているスレッドを確認。
list
  512 "Thread of Counter" Mobile
  2400 "Thread of Counter" Mobile
Ready.
stop コマンドでスレッドを停止。
stop 2400
Ready.
write コマンドでスレッドを外部化、ディスクに保存。
write 512 foo
Ready.
read コマンドで外部化されたスレッドを復帰。
read foo
Ready.

5. まとめ

スレッド移送システム MOBA を開発した。移動エージェントの 記述、プログラムの耐故障性向上、負荷分散などへの応用可能 性を述べ、MOBA のユーザインタフェース、MOBA 上の負荷分散 システムのアルゴリズムを説明した。


参考文献

[1]
首藤, 村岡. "Java 言語環境におけるスレッド移送手法と移動エージェントへの応用", 電子情報通信学会技術研究報告, CPSY98-32, pp. 39-46, May 1998.
[2]
MOBA: Mobile Agent Facilities on Java Lang. Env.,
http://www.shudo.net/moba/
[3]
IBM Aglets Software Development Kit,
http://www.trl.ibm.co.jp/aglets/.
[4]
ObjectSpace Voyager,
http://www.objectspace.com/products/Voyager/.
[5]
Kafka: Java用マルチ・エージェント記述ライブラリ,
http://www.fujitsu.co.jp/hypertext/free/kafka/jp/.
[6]
S. Fujita and M. Yamashita. "Maintaining a Dynamic Set of Processors in a Distributed System", 10th International Workshop, WDAG'96, Lecture Notes in Computer Science, Vol. 1151, pp.220-233, 1996.
[4]
Sun Microsystems. JavaTM Remote Method Invocation Specification, 1997.
[6]
平野. "HORB: Distributed Execution of Java Programs", Proceedings of World Wide Computing and Its Applications, March 1997.