TRMIにおけるマルチスレッド制御機能 - ソフトウェアシステム研究室

TRMI におけるマルチスレッド制御機能
Controlling Multiple Threads in TRMI
杉山安洋∗ 加藤剛彦†
Summary.
TRMI (Transparent Remote Method Invocation) is a mechanism that
allows stand-alone software systems to run in networked environments,
consisting of multiple computer systems, without modifying their source
code. However, stand-alone objects are not ready to be accessed simultaneously by multiple client objects. If two or more client objects on different machines access them at the same time, it will result in conflicts.
TRMI allows programmers to add their own thread control mechanism
to the objects without modifying their source code.
1
はじめに
インターネットの発達にともない，分散型のソフトウェアの重要性が広く認識さ
れ，その需要も爆発的に増大している．しかし，分散型のソフトウェアを開発する
ことは技術的に難しいことも多い．Java 言語には RMI [2], JavaIDL [11], JXTA [12],
Jini [13], Horb [4], Voyager [9] といったクライアント・サーバ型や P2P 型の分散シス
テムを開発するためのツールや開発システムが数多く用意されている．しかし，こ
れらを用いて分散システムを開発するためには，分散システムであることを意識し
たコードが必要となり，これが分散システム開発から手軽さを奪っている．
TRMI [14] [15] は，各々のオブジェクトには分散システムであることを意識させる
ことなく，オブジェクトを複数の Java 仮想マシン (JVM) 上に分散させ，他の JVM
上のオブジェクトのメソッドを呼び出すことのできる Java 言語用の分散オブジェク
ト開発システムである．TRMI を用いると，スタンドアロンの Java プログラム中
のオブジェクトを，それ自身は変更することなく分散化させる，即ち他の JVM 上
のオブジェクトからもアクセス可能とする，ことができる．
TRMI を用いると，もともとは単一マシン上のシングルスレッド環境で実行され
ることを想定して開発されたサーバオブジェクトが，複数のマシン上の他のクライ
アントオブジェクトから同時にアクセスされる状態が発生する．これは，ひとつの
サーバが複数のスレッドから同時にアクセスされることに他ならない．すると，ひ
とつのサーバへの複数のアクセスが何らかの競合状態を引き起こす可能性が出てく
る．サーバの中には，複数のスレッドからの同時アクセスを許すもの（以下スレッド
セーフなものと呼ぶ）もあれば，同時にアクセスされると，サーバ中のデータの整
合性が失われてしまうものもある．そのため，同時に発生することが避けられない
複数のアクセスを適切な順序で逐次的に処理するためのスケジューリングや，デッ
ドロックの回避のための同期処理などの問題を解決しなければならない．なお，本
論文では，あるオブジェクトが他のオブジェクトのメソッドを呼び出している場合，
∗
†
Yasuhiro Sugiyama, 日本大学工学部情報工学科
Takehiko Kato, 日本大学大学院工学研究科情報工学専攻
FOSE ’03
呼び出す側のオブジェクトをクライアント，呼び出される側のオブジェクトをサー
バと呼ぶ．
しかし，そのような同時アクセスを制御するための処理は，分散処理を意識して
いないサーバやクライアントの元々のコードには含まれていないため，TRMI を使
用する際に，新たに付け加える必要が発生する．TRMI では，オブジェクトを分散
化させる際に，そのような排他制御やスケジューリングなどの機能を，オブジェク
ト自身のコードを変更する必要なく，外付けで追加できる．本稿は，TRMI におけ
る，スケジューリング機能の追加の方式について述べるものである．
本論文の構成は以下の通りである．まず 2 章で TRMI の概要について述べ，3 章
で TRMI におけるスケジューリング機能について述べる．4 章では TRMI のスケ
ジューリング機能を利用した実例を検証することにより，TRMI のスケジューリン
グ機能の有効性を検証する．最後にまとめと今後の課題で論文を締めくくる．
2
TRMI の概要
分散型のソフトウェアを開発するためには，そのアプリケーション本来の機能で
あるアプリケーションロジックに加えて，その機能を複数の計算機に分散させて処
理するための分散ソフトウェア特有のネットワークに関連した処理を開発しなけれ
ばならない．このようなネットワーク処理をアプリケーションロジックと合わせて
開発することは，アプリケーションロジックとネットワーク処理の混同を招き，開
発作業を必要以上に複雑にしてしまう．また，アプリケーションロジックの開発者
が，いつもネットワーク処理に精通しているとは限らない．また，既に開発済みの
アプリケーションを分散化する必要が発生する場合もある．既存ソフトウェアの変
更は新規開発よりも工数がかかる場合も多い．
しかし，アプリケーションロジックとネットワーク処理とを独立して開発できれ
ば，回避できる問題も多い．アプリケーションロジックとネットワーク処理は，それ
ぞれの分野を得意とする別の開発者が担当し効率よく開発できるようになり，また，
既存のアプリケーションには外付けでネットワーク処理を追加できるようになる．
我々の基本手法は，アプリケーションロジックとネットワーク処理を分離し，し
かもアプリケーションロジックからネットワーク処理が透過的に使用できるように
することにある．そうすることより，分散型のソフトウェアの開発にあたっても，ま
ずスタンドアロンのソフトウェアを開発し，それを，できる限り等価な形で分散型
のソフトウェアに変換することができるようになる．
TRMI を用いると，クライアントであるオブジェクトは，別の JVM 上のサーバ
のメソッドを，あたかも同一の JVM 上にそのサーバが存在するかのように呼び出
すことが可能になる．しかも，クライアントやサーバには，他の分散オブジェクト
技術では必要であった，分散処理のための特別のコードを追加する必要がない．
TRMI でも RMI などの既存の分散オブジェクト技術と同様，スタブとスケルト
ン，およびレジストリは存在する．スタブとスケルトンは，クライアントがサーバの
メソッドをネットワーク経由で呼び出す際に，メソッド呼び出しを中継する機能を
有している．レジストリは，クライアントがサーバを検索する際のネームサービス
の機能を持つ．RMI などの既存の方式の問題点は，これらのスタブやスケルトンや
レジストリといったオブジェクトを，クライアントやサーバが直接アクセスしなけ
Controlling Multiple Threads in TRMI
ればならない点であった．一方 TRMI では，図 1 に示すようにスタブやスケルトン
は，クライアントやサーバの存在するアプリケーション層とは異なる TRMI 層 [14]
に存在し，クライアントやリモートサーバは，これらの存在を一切気にする必要は
ない．TRMI では，スタブやスケルトン，レジストリをクライアントやサーバから
隠すことにより，クライアントやサーバには分散システムであることを意識させる
ことなく，リモートメソッドの呼び出しが可能となった．この際，サーバの IP アド
レスなどの位置情報は TRMI のランタイムシステムに，システム管理者から与えら
れる．このようなメソッドの呼び出しを透過的リモートメソッド呼出しと呼ぶ．な
お，TRMI スタブやスケルトンは，trmic と呼ばれるツールにより自動生成される．
なお，TRMI は，TRMI スケル
トンとスタブが通信するための独
✒☞✓✟✔✖✕✟✗☞✘✚✙✜✛✖✢☞✣✟✤
✥✑✦✖✧
✧✡✩ ✍
✸✡✹☞✺ ✲ ✏✻✍
★
✥
✧☞✴✚✵
自の通信プロトコルを持っている
✲☞✳
☛
✏✷✶
わけではない．既存の分散オブジ
✂✁✂✄✆☎ ✶
✕✟✗☞✘✻✙✜✛☞✢☞✣✼✤
ェクトとの互換性を保つために，
✂✁✂✄✆☎
✂✁✂✄✆☎
✝✟✞✡✠
✝☞☛✡✌✎✍✑✏
✽☞✾☞✿☞❀
既存の複数のプロトコルを用いて
✰☞✱
✮☞✯
通信を行うことができる．現在，
✝ ✫ ✘✻✙
✪✁✂✄✆☎ ✥
❁☞❂☞❃✖❄
❅☞❆
✫✑✬ ✝✭✍
サポートしているプロトコルは，
❇ ✘ ✍❈✝☞❉ ✘ ✍
❇ ✘ ✍❈✝☞❉ ✘ ✍
RMI と CORBA である．なお，
TRMI スタブなどに関する詳しい
図 1 TRMI によるリモートメソッドの実行
記述は，文献 [14] にあるのでここ
では省略する.
TRMI の開発目的の一つに，アプリケーションロジックがネットワーク処理を透
過的に利用できることがあることは先程述べた通りである．しかし，ネットワーク
処理のすべてを透過的に行ったり，ネットワーク処理を 100%自動生成することを
狙っているわけではない．ネットワーク処理には，アプリケーションによらない共通
の処理と，アプリケーションごとに開発が必要な個別の処理がある．そこで，共通
な処理は，スタブやスケルトンといったフレームワークとしてまとめ，アプリケー
ションごとに開発しなくても済むようにし，開発者の負担を軽減させる．また，ア
プリケーション固有の処理は，フレームワークのホットスポットとして，開発者が
追加したり，フレームワークの機能を変更できるようにしている．
現在， TRMI において開発者が独自の処理を追加することが可能なホットスポッ
トは，クライアントにおける例外処理と，サーバにおけるスレッド制御である．リ
モートメソッドを呼び出す際に，単一の JVM 上のメソッド呼び出しでは発生しな
いような例外が発生する可能性がある．また，スタンドアロンのシステムを分散化
すると，自然と複数のクライアントがひとつのサーバを同時にアクセスすることが
可能となり，スタンドアロンシステムでは発生しなかった資源の競合が発生するた
め，メソッド呼び出しのスケジューリングや排他制御およびトランザクション管理
が必要となる．例外処理は，TRMI スタブのホットスポットに定義でき，スレッド
制御はスケルトン側のホットスポットに記述できる．
例外処理については文献 [14] で述べたので，本稿ではスレッド制御について述べ
る．なお，TRMI の提供するスレッド制御メカニズムは，スタンドアロンシステムを
分散化した際に追加が必要となるスレッド制御の機構を提供するものであり，もと
FOSE ’03
もとのスタンドアロンシステムにスレッド制御機構を組み込むための方式ではない．
3
TRMI のスレッド制御機能
TRMI スケルトンは，クライアントからのリクエストごとにマルチスレッドで動
作する．これらのスレッドの制御は，図 2 に示す通り TRMI スケルトンが生成する
スケジューラオブジェクトが行う．スケジューラには，trmic が自動生成する標準の
スケジューラと，開発者が自分自身のスレッド制御ポリシーを定義することができ
るユーザスケジューラがある．ユーザスケジューラを定義するためには，標準スケ
ジューラのサブクラスを作成し，そこで自分のスレッド制御ポリシーを記述すれば良
い．なお，ユーザのスケジューラと標準のスケジューラは，ともにサーバのクラスご
とに作成される．ユーザスケジューラのクラス名は，サーバのクラス名に Scheduler
という接尾語を付けたものとなり，そのスーパクラスである標準のスケジューラのク
ラス名は，サーバのクラス名に SuperScheduler という接尾語を付けたものとなる．
3.1 標準のスケジューラ
標準スケジューラのクラスは，サーバ
のリモートメソッドと同一 signature，即
✂✁☎✄☎✆✞✝✠✟
✡☞✍ ☛☎✌ ✟
✌✏✎ ✪✙✫☎✬✠✭
ちメソッド名が同一で引数と戻り値の型
✿✓❀✓❁✓❂✓❃✛❄✓❄❆❅
も同一，のメソッドを含んでいる．このメ
✪✙✫☎✬✮✭✰✯☎✱☎✲✞✳
✑✓✒✓✔✛✕
✑✓✒✓✔✖✕✓✗✙✘✂✚
✗☎✜✏✢ ✟☞✝
✴☎✵☎✶☎✷
✽☎✾ ✪✙✫✥✬✠✭
ソッドを代理メソッド（Proxy Method）
✿✓❀✓❁✓❂✓❃✛❄✓❄❆❅
✗✠✸ ✬✮✭
✗✠✸ ✬✠✭
と呼ぶ．TRMI スケルトンが TRMI ス
✹☎✺☎✻✥✼
✹☎✺☎✻☎✼
タブからサーバのリモートメソッドを呼
✣☎✤
び出す要求を受け取った場合には，スケ
✗✥✜☎✦✙✧ ✌ ✁
✗☎✜☎★ ✦✙✌✂✧ ✩ ✌ ✁
✍ ✚ ✏✁ ✗ ✽☎
✽✥✾ ✪✙✫☎✬✮✭
✾ ✪✞✫☎✬✠✭
ジューラの同名の代理メソッドが呼び出
✿✓❀❇❁✓❂✓❃✛❄✓❄❆❅
✿✓❀✓❁✓❂✓❃✛❄❇❄❆❅
され，それが中継処理を行う．従って，
それらの代理メソッドの動作スケジュー
図 2 TRMI におけるスレッド制御
ルを決定することにより，サーバ側のス
レッドを制御することができる．
開発者は，trmic によって標準のスケジューラを生成する際に，各代理メソッドの
呼び出しを逐次処理するか，マルチスレッドで動作させるかを指定できる．開発者が
何も指定しない場合には，標準スケジューラは TRMI スタブからの代理メソッド呼
び出しの中継要求をシングルスレッドで逐次処理することを基本としている．これ
は，複数のクライアントがマルチスレッド処理を前提としていないサーバのリモー
トメソッドを同時に実行することにより発生する資源の競合を防ぐためである．一
方，もともとスレッドセーフなスタンドアロンのサーバのメソッド対しては，分散
化後もマルチスレッドで動作させることが可能である．その場合，標準スケジュー
ラでは，排他制御やスケジューリングなどは行わないので，スレッドの制御はサー
バにもともと定義されている必要がある．
3.2 ユーザスケジューラ
ユーザスケジューラも，サーバのリモートメソッドと同一 signature の代理メソッ
ドを持つクラスである．ユーザスケジューラが定義されると，リモートメソッドの
Controlling Multiple Threads in TRMI
呼び出しが行われた時には，標準のスケジューラの代理メソッドではなく，ユーザ
スケジューラの代理メソッドが呼び出される．従って，ユーザスケジューラの代理
メソッドが，適切なスレッド管理を行ってサーバのメソッドを呼び出すことで，そ
のメソッドにおけるスレッド制御ポリシーを決定できる．
ユーザのスケジューラの内部では，スレッドの実行を制御する処理を記述する必
要があるが，それは，Java 言語が提供する機能やクラスを用いたり，TRMI が提供
するクラスを用いて行う．
Java 言語が提供するスレッド制御のための基本機能は，モニタ (monitor) [1] [5]
と Thread クラスである．モニタは，複数の処理の排他制御に用いられる．また，
Thread クラスは，各スレッドの実行を停止したり再開したりする機能を提供してい
る．これにより，スレッドの同期処理が記述できる．
また，一般的にスレッドを制御する際には，セマフォやスレッドの待ち行列 (Queue)
などの使用が有効であることが知られている．これらのオブジェクトは，Java 言語
には標準では用意されていない．Java の標準機能を用いて実装することも可能であ
るが，開発者がその度に開発していたのでは効率が悪い．そこで TRMI では，頻繁
に使用される制御用のオブジェクトに対しては，クラスとして提供している．なお，
TRMI が提供するクラス自身も Java 言語で実装されているので，これらのクラス
を用いても，Java 言語で記述できる範囲を超えてスレッドの制御ができるようにな
るわけではない．
TRMI のユーザスケジューラにおけるスレッド制御方式を考える上で強調してお
きたい点は，そのプログラミングのスタイルである．一般には，クライアントある
いはサーバに直接スレッドの制御機能を持たせる．この方式では，Java の基本機能
を用いてスレッドの制御が行えることは数多くの実例が示している．しかし，TRMI
の場合は，サーバでもクライアントでもなく，その中間に位置するスケジューラで
スレッドの制御を行うことになる．そのため，既存のスレッド制御法が適用できる
かは自明ではない．TRMI の有効性を検証するため，以下で，TRMI における代表
的なスレッド制御の方式について述べる．なお，以下のサンプルプログラムでは日
本語を含んだ疑似的な Java 言語を用いている．
3.3 スレッド自身の取り扱い
Java 言語の提供する Thread クラスは，分散環境で使用すると，開発者の期待通
りに動作しないことがある．例えば，RMI を用いてリモートメソッドを呼び出した
場合，リモートメソッド側で，クライアントのスレッドを区別したい場合がある．リ
モートメソッド内部でのスレッドは，基本的にクライアントの IP アドレスと TCP
コネクションのソケット番号で識別される．従って，クライアント側では別々のス
レッドでも，サーバ側では，同一のスレッドとして認識されてしまうことがある．こ
れは，RMI が TCP ソケットを再利用しようとするから [3] である．
この問題を回避するために，TRMI では，TRMIThread クラスを用意している．
このクラスを使用すると，サーバ側のスレッドと，それを発生させるクライアント
側のスレッドを１対１に対応付けることができ，サーバ側で対応するクライアント
のスレッドを正しく識別することができる．標準のスケジューラのクラスには，currentThread() メソッドが用意されており，その戻り値として，現在実行中のスレッ
FOSE ’03
class ユーザスケジューラ extends 標準スケジューラ {
Object lock;
……
synchronized public void A() { // 1st monitor
server.A();
}
public void B() {
synchronized(this) {
// 1st monitor
server.B();
}
}
図3
public void C() {
synchronized(lock) {
server.C();
}
}
public void D() {
synchronized(lock) {
server.D();
}
}
// 2nd monitor
// 2nd monitor
}
モニタによる排他制御
ドを表す TRMIThread クラスのインスタンスを取得することができる．
3.4
排他制御
複数のスレッドがひとつのオブジェクトのメソッドを同時に実行する際には，資
源の競合を防ぐために，排他制御が有効な場合が多い．Java 言語には，排他制御の
メカニズムとしてモニタが標準で用意されている．モニタとは，モニタに属する複
数のメソッドやコードブロックの内で，一時に実行されるものは一つのみに限定す
るメカニズムである．Java の各オブジェクトは，自分自身に対応するモニタをひと
つずつ持っている．同期 (synchronized) ブロックや同期メソッドで，モニタに属す
るメソッドやコードブロックを指定できる．各モニタに属する同期メソッドや同期
ブロックは，その処理を開始する前に，そのモニタのロックを獲得し，処理が完了
するとロックを解放する．これにより，同期メソッドや同期ブロックの排他的実行
が可能となる．なお，モニタに属するロックをプログラマが明示的に獲得したり解
放したりすることはできない．
TRMI における排他制御の実現においてもモニタが有効である．図 3 は，サーバ
のメソッド A，B，C，D を A と B，C と D という２つのグループに分けて，排他
制御する際のユーザスケジューラである．ここでは，２つのモニタが使用されてい
る．サーバの A メソッドを呼び出す同期メソッドと B メソッドを呼び出す同期ブ
ロックは，オブジェクト this（このクラスのインスタンス自身）が持つモニタに属
している．サーバの C メソッドと D メソッドを呼び出す同期ブロックは，オブジェ
クト lock が持つモニタに属している．これにより，A と B は排他的に実行されると
同時に，C と D も排他的に実行される．
上記の例中，server.A() という記述は，サーバのメソッド A を直接呼び出すこと
を意味している．server は，標準のスケジューラクラスのインスタンス変数である．
この記述を super.A() と書くこともできるが，その場合には，サーバのメソッドの
呼び出しは，標準のスケジューラを経由して行われるため，その規則に従う．
3.5 トランザクション
分散環境においては，複数のメソッドを原子的 (Atomic) に連続実行しなければ
ならない場合がよくある．例としてしばしば挙げられるのは，銀行の ATM の残高
照会と引き出し処理である．２人で口座を共有している場合など，一方の人が残高
照会をした後に預金を引き出そうとした場合，残高照会と引き出し処理の間に，他
Controlling Multiple Threads in TRMI
class ユーザスケジューラ extends 標準スケジューラ {
TRMILock lock, lock2;
……
void getBalance() {
// 残高照会
lock.lock();
// 排他制御のためのロックの獲得
server.getBalance ();
// サーバのメソッドの呼び出し
lock2.lock();
// 実行順序の制御のためのロックの獲得
}
void makeWithdrawal() {
// 引き出し
if(lock2.isLocked()) {
// ロックでガード（ロックの確認）
server.makeWithdrawal (); // サーバのメソッドの呼び出し
lock2.unlock();
// getBalance が獲得したロックの解放
lock.unlock();
// getBalance が獲得したロックの解放
} else { // エラー処理 }
}
}
図4
複数のメソッドを原子的に実行するスケジューラ
方の人の引き出し処理が行われてしまった場合などは，残高照会で確認した金額が
引き出せなくなってしまう．これを防ぐためには，残高照会と引き出し処理を原子
的に連続して実行する必要がある．これも同期処理の一種であるが，残高照会と引
き出し処理を同じモニタに属させるといった単純な方式では解決できない．
複数のメソッドを原子的に実行するために，TRMI では TRMILock クラスを用意
している．この TRMILock のオブジェクトは，一度に一つのスレッドがロックを獲
得できる．ロックを獲得したい他のスレッドは，始めのスレッドがロックを解放す
るまで待ち状態になる．あるスレッドが獲得しているロックを，他のスレッドが解
放することはできない．ロックの獲得と解放は lock() メソッドと unlock() メソッド
で行う．
２つのメソッドを原子的に実行するスケジューラの例を図 4 に示す．２つのメソッ
ド getBalance(), makeWithdrawal() をこの順に繰り返し実行するクライアントプ
ログラムがいくつかあり，それらを原子的に処理したいと仮定する．まず，最初の
getBalance() で lock オブジェクトのロックを獲得し，次の makeWithdrawal() で獲
得したロックを解放している．これにより，あるクライアントスレッドが２つのメ
ソッドの実行を開始すると，他のスレッドは２つのメソッドの実行を開始できない．
しかし，これだけでは，あくまでクライアント側が２つのメソッドを順序正しく
実行している場合のみに動作する．例えば，あるスレッドが突然 makeWithdrawal()
メソッドを実行した場合は，ロックを獲得する必要がないため，即座に実行されて
しまう．このような状況を防ぐためには，メソッドの実行順序を決める同期処理を
行う必要がある．図 4 では，makeWithdrawal() メソッドの内部で lock2 オブジェク
トのロックの確認を行い，makeWithdrawal() は getBalance() が実行後のみに実行
できるようになっている．ここで用いられている TRMILock クラスの isLocked() メ
ソッドは，それを実行するスレッドがロックを獲得済みかどうかを確認するための
メソッドである．
3.6 スケジューリング
スレッドセーフでないサーバのメソッドが同時に複数のクライアントから呼ばれ
た際には，それらを何らかの方式でスケジューリングして逐次処理する必要が出て
くる．TRMI では，ライブラリとしていくつかのスケジューリング用のクラスが用意
FOSE ’03
class ユーザスケジューラ extends 標準スケジューラ {
FifoQueue fifoQueue;
public UserScheduler() {
// constructor
fifoQueue = new FifoQueue ();
}
public void someMethod() {
fifoQueue.append();
// wait until preceding invocation terminates
server.someMethod ();
// invoke server’s remote method
fifoQueue.remove();
// activate a method in the queue
}
public void anotherMethod() {
fifoQueue.append();
// wait until preceding invocation terminates
server.anotherMethod (); // invoke server’s remote method
fifoQueue.remove();
// activate a method in the queue
}
}
図5
FIFO スケジューラの例
されている．その中の代表的なものに，FifoQueue，PriorityQueue，RoundRobinQueue がある．これらのクラスは，同時に呼び出されたメソッドを，それぞれ，到
着順 (FIFO の順)，何らかの優先度の順，Round Robin アルゴリズム [10] に基づい
て Time Sharing System のように時分割で実行するものである．
例えば，FifoQueue を用いたスケジューリングは，図 5 のように記述される．FifoQueue は，スレッドの待ち行列である．あるスレッドが append() メソッドを実行
すると，そのスレッドが FIFO の順に待ち行列に追加される．その際，待ち行列中の
スレッドで実行中のものがあれば，追加されたスレッドは実行待ち状態となる．実
行中のスレッドが，自分自身の処理の完了後，remove() メソッドを呼び出すと，そ
のスレッドは待ち行列から削除され，待ち行列の先頭のスレッドの実行が再開され
る．なお，FifoQueue の append() および remove() メソッドは，Java の同期メソッ
ドとして実装されており，スレッドの待ち行列への追加や削除は排他的に行われる．
なお，Java の同期メソッドを使うと，複数のメソッド呼び出しを逐次的に処理す
ることはできる．しかし，複数のスレッドが同時に待ち状態になった場合，それら
のうちどれが次に実行されるかは，言語仕様では規定されておらず，スレッドが開
始された順に処理を行わせることはできない．これを，FifoQueue を用いれば，待
ち行列に到着した順に実行することを保証できる．
なお，TRMI が提供するスレッドの待ち行列を使わなくとも，ユーザが自分で定
義すれば，ユーザ独自のスケジューリングを行うことは，もちろん可能である．
4
TRMI を用いたスケジューリングの実例
本節では，ユーザのスケジューラの例を示すことにより，TRMI のスケジュー
リング機能の有効性を検証する．その例として，古典的な並列処理の問題である，
Producer-Consumer Problem と Dining Philosopher Problem を取り上げる．なお，
これらの古典的な問題は数多くの教科書 [6] [8] [10] に解が出ている．今回は，それら
の解が TRMI のスケジューラの内部で実現できるかどうかという点について検討し
た．解のアルゴリズム自身の新規性を主張するものではない．
Controlling Multiple Threads in TRMI
class Producer {
public static void main(String args[]) {
Buffer buffer = new Buffer();
int i=0;
while(true) buffer.write(i++);
}
}
class Consumer {
public static void main(String args[]) {
Buffer buffer = new Buffer();
int data;
while(true) data = buffer.read();
}
}
図6
class Buffer {
int data[];
int count;
public Buffer() {
data = new int[5];
count = 0;
}
public void write( int value) {
data[count++]=value;
}
public int read() {
return(data[–count]);
}
}
分散化する前の Producer と Consumer プログラム
4.1 Producer-Consumer Problem
Producer-Consumer Problem では，有限の大きさを持ったバッファに対してデー
タを書き込む Producer プロセスと，データを読み出す Consumer プロセスが同時に
実行される．Producer は，バッファが一杯になった場合には，空きができるまで書
き込み処理を一時停止させる必要がある．一方，Consumer は，バッファにデータ
がある場合は，読み出し処理を行うことができるが，バッファが空の場合は，バッ
ファにデータが書き込まれるまで，処理を一時停止させる必要がある．
ここで，図 6 に示すスタンドアロンのプログラムを考える．Producer と Consumer
は全く別のプログラムであり，共通のバッファをアクセスできないため，このまま
ではスタンドアロンの Producer-Consumer Problem の解にはなっていない．しか
し，Buffer クラスを TRMI で分散化すると Producer と Consumer から同時アクセ
スできるようになり，解となる可能性がある．なお，Producer と Consumer 間での
同期処理は記述されていないだけでなく，Producer がバッファの大きさを無視して
書き込みを行ってしまうオーバフローの問題や，Consumer が空のバッファからも
読み出しを行うというアンダフローの問題も含んでいる．このプログラムを TRMI
で分散化させる際に，複数の Producer と Consumer が同時にひとつの Buffer オブ
ジェクトに対して正しくアクセスを行えるようにスケジューラを記述することがこ
こでの目的である．
Producer-Consumer Problem の解法は色々あるが，counting semaphore を使用
する方法が比較的に有名である．TRMI でも同様な手法でスケジューラが定義でき
る．図 7 は，Buffer クラスを TRMI によって分散化した際に必要となるユーザス
ケジューラを示す．Producer と Consumer の同期には，TRMI が提供する TRMICountingSemaphor クラスを用いる．TRMICountingSemaphore クラスは，セマフォ
の一種である counting semaphore を Java のクラスとして実装したもので，get メ
ソッドと release メソッドを含んでいる．セマフォは基本的には整数型の変数で，get
は数値を１減少させ，release は１増加させる．get は，数値が正の場合には実行で
きるが，それ以外の場合には，待ち状態となる．コンストラクタでは，セマフォの
初期値を指定する．なお，セマフォと TRMILock の動作は似ているが別のものであ
る．最も大きな違いは，セマフォがメソッドを実行するスレッドを区別しないのに
対し，TRMILock はスレッドを区別してロックを行う点にある．また TRMI では，
２進値を持つセマフォTRMIBinarySemaphore も提供している．
FOSE ’03
class Buffer Scheduler extends Buffer SuperScheduler {
TRMICountingSemaphore pro, con;
public Buffer Scheduler() {
pro = new TRMICountingSemaphore (5);
con = new TRMICountingSemaphore (0);
}
public void write(int value) {
pro.get(); synchronized(this) {
server.write(value);
}
con.release();
}
図7
public int read() {
int data;
con.get();
synchronized(this) {
data = server.read();
}
pro.release();
return data;
}
}
Producer-Consumer Problem のためのスケジューラ
バッファの空きの個数は，セマフォpro により管理されており，バッファのオーバ
フローが発生しないようになっている．一方，バッファ中のデータの個数は，セマ
フォcon により管理されており，バッファのアンダフローも防止されている
4.2 Dining Philosopher Problem
Dining Philosopher Problem では，何人かの哲学者（一般的には５人の哲学者）
が同時に丸い食卓についていると仮定する．食卓の中央には，スパゲッティが皿に
盛られており，各哲学者は，食事をする動作と思考する動作を交互に繰り返す．哲
学者の間には，フォークが１本ずつ置かれており，哲学者は，両側のフォークを手
にすることができた時のみに食事ができる．このような状態で，全ての哲学者が均
等にスパゲッティを食べられるようにするのが，この問題である．
その難しさのひとつに，デッドロックの回避がある．全ての哲学者が一斉に自分
の右手のフォークを取ってしまうと，全員が左のフォークを取れなくなってしまい，
誰も食事ができなくなってしまうというデッドロックが発生する．
これを回避するためのひとつの方法は，それぞれの哲学者が，両側のフォークを
取れる時にのみ，それらを同時に取る方式が考えられる．すなわち，右のフォーク
を取る動作と，左のフォークを取る作業を原子的に行う必要がある．
Dining Philosopher Problem には，このデッドロックの回避のほかに，一部の哲
学者のみが食事ができて，他の哲学者ができないといった不公平性を避けるといっ
た Starvation の問題も含まれるが，ここではデッドロックのみに着目する．この問
題の TRMI における解のもととなる，スタンドアロンの哲学者を表すクラスを図 8
に示す．食卓を表すクラス Table には，食卓に着くメソッド enter() や左右のフォー
クを操作するメソッドがある．哲学者が enter() メソッドを実行してテーブルに着
くと，席の番号が戻り値として返される．その後のフォークやスパゲッティへのア
クセスは，その番号を用いる．なお，ここでは同期処理は全く行われていない．
図 9 に，食卓をリモートサーバ，哲学者をクライアントとして Dining Philosopher
Problem を実現した場合のユーザスケジューラを示す．ここでは，それぞれのフォー
クに対応するロックが同期制御に使われている．新しい哲学者がテーブルに着くた
びにフォークが増えるので，enter() の代理メソッドで，そのフォーク用のロックを
生成する．getRightFork() で，右のフォークを取る時に，左のフォークも同時に取
れるかどうかを確認し，予約（ロック）する．空いていない場合は，空くまで待つ．
続いて，右のフォークが空いているかを確認する．空いていない場合には，待ち状態
Controlling Multiple Threads in TRMI
class Philosopher {
public static void main(String args[]) {
int id;
// 座席番号
Table table = new Table();
id = table.enter();
// 食卓につく
while(true) {
table.getRightFork(id);
// 右のフォークをとる
table.getLeftFork(id);
// 左のフォークをとる
table.eat(id);
// スパゲッティを食べる
table.putRightFork(id);
// 右のフォークを戻す
table.putLeftFork(id);
// 左のフォークを戻す
// 思考動作
}
}
}
図8
哲学者のクラス
class ユーザスケジューラ extends 標準スケジューラ {
TRMILock fork[];
int count;
……
synchronized public int enter() {
int id;
id = server.enter();
fork[count++]=new TRMILock();
return id;
}
public void getRightFork(int id) {
while(true) {
fork[id].lock();
// 左のフォーク予約
// 右のフォークが使えれば予約
if(!fork[(id+1)%count].testAndLock()) {
fork[id].unlock();
// 予約取消
} else
break;
}
server.getRightFork(id);
}
図9
public void getLeftFork(int id) {
server.getLeftFork(id);
}
public void putRightFork(int id) {
server.putRightFork(id);
fork[(id+1)%count].unlock();
}
public void putLeftFork(int id) {
server.putLeftFork(id);
fork[id].unlock();
}
public void eat(int id) {
server.eat(id);
}
}
Dining Philosopher Problem のためのスケジューラ
になると，デッドロックが起きる可能性があるので，ここでは待たない．左のフォー
クの予約も取り消して，再度，両方のフォークの予約を試みる．両方のフォークが
予約できて初めて，server.getRightFork() を呼び出して，実際にフォークを取る．
ここで用いられている TRMILock クラスの testAndLock() メソッドは，他のスレッ
ドがロックを獲得していない場合に限り，ロックを獲得するという処理を原子的に
行うメソッドである．lock() メソッドではロックが獲得できない場合は，そのスレッ
ドは待ち状態となるが，testAndLock() メソッドは，ロックが獲得できない場合でも
待ち状態にはならない．
なお，TRMI を用いた解で注意すべき点は，分散化により哲学者の数が動的に変
更できるようになる点である．ここでは，説明の単純化のために，ロックの配列を用
いたが，それでは哲学者の人数に制約が出てしまう．実際は，Vector などの可変長
のものを使用する必要がある．また，ひとつのフォークを取る動作と戻す動作の間
に哲学者の人数が増えてしまうと，取った時のフォーク番号と戻すフォーク番号が
一致しない等の問題も発生するため，enter() メソッドと getRightFork() メソッドで
も同期処理が必要となるが，ページ数の関係上，ここではその処理は省略してある．
FOSE ’03
5
まとめと今後の課題
本稿では，TRMI を用いてスタンドアロンシステムを分散化する際に必要となる
スレッドの制御方式について述べた．TRMI では，もとのプログラムには変更を加
えずに，外付けでスケジューラにスレッド制御の方式を記述するという形式で，ス
レッドの制御を行う．今回の検証では，TRMI のスケジューラの内部に，一般的な
スレッド制御のアルゴリズムを記述できることが確認できた．しかも，TRMI の提
供するスレッド制御用のオブジェクトを用いることにより，かなり簡便な方式でス
レッドの制御が行えることも確認できた．
今後の課題としては，より高度なスレッド制御機構の検討と実装があげられる．い
くつかの検討中の課題があるが，そのひとつは，スレッド制御の粒度の可変性の実
現である．現在の TRMI では，スレッド制御の粒度はサーバのメソッドである．そ
のため，メソッドを単位として，排他制御やスケジューリングを行うことができる．
しかし，メソッドの同時実行の際に，メソッドの一部のみが競合状態を発生させる場
合などは，メソッド全体を排他的に実行する必要がない．また，逆に，より大きな粒
度が望ましいこともある．Dining Philosopher Problem でも見たように，複数のメ
ソッドが複雑に絡み合って競合状態を発生させる場合もあり，それらを TRMILock
などで個別に制御していたのでは処理が複雑になってしまう．従って，メソッド単
位という粒度に限定しないスレッド制御方法の確立が必要となると考えている．
また，外付けのスケジューラでスレッド制御を記述するという TRMI のスレッド
制御方式の適用範囲の検討も挙げられる．TRMI では，これまで，スタンドアロン
のオブジェクトを TRMI によって分散化することによって発生するスレッドに対し
て制御の方法を提供することに主眼を置いてきた．しかし，もともとのプログラム
がスレッド制御機構を持っている場合などには，TRMI で分散化する際にスケジュー
ラとして付加するスレッド制御機構との整合性も問題になると考えられる．従って，
スレッド制御全体という観点に立った，アプローチが必要となると考えられる．
参考文献
[
[
[
[
[
1 ] Brinch-Hansen, P.:Operating System Principles, Prentice Hall, 1973.
2 ] Downing, T. B.:JavaRMI: Remote Method Invocation, IDG Books, 1998.
3 ] Grosso, W.:Java RMI, O’Reilly and Asssociates, 2002.
4 ] 平野聡: HORB ドキュメント， http://horb.etl.go.jp/horb-j/doc/
5 ] Hoare,C.A.R.:Monitors: An Operating System Structuring Concept, CACM, vol.17, No.10,
pp.549-557, October,1974.
[ 6 ] Horowitz, E.:Fundamentals of Programming Languages, Computer Science Press, 1984.
[ 7 ] Lea, D.: Concurrent Programming in Java, Addison Wesley, 1996.
[ 8 ] Oaks, S. and Wong, H.: Java Threads, O’Reilly and Associates,1997.
[ 9 ] ObjectSpace: Voyager 4.5 Documentation, http://www.recursionsw.com/products/voyager
[10] Silberschatz, A. et al: Operating System Concepts, Addison-Wesley, 1991.
[11] Sun Micro Systems: JavaIDL Documentation, http://java.sun.com/j2se/1.4.2/docs/guide/idl
[12] Sun Micro Systems: Project JXTA v2.0: Java Programmer’s Guide, 2003
[13] Sun Micro Systems: Jini Network Technology, http://java.sun.com/software/jini
[14] 杉山安洋: TRMI によるオブジェクトの分散化，コンピュータソフトウェア，vol.19, No.5,
pp.40-59, 2002.
[15] 千葉雄一郎，杉山安洋，TRMI を用いた分散システム構築の自動化，ソフトウェア工学の基礎
VIII，pp.245-248, 2001.

Download Report