論文 / 著書情報
Article / Book Information
論題(和文)Web サービスベースのワークフロー管理における障害を考慮したアク
ティビティスケジューリング手法

Title(English)

A Failure-aware Activity Scheduling Method for Web-Service BasedWork ow Management

著者(和文)

加藤英之, 小林隆志, 横田治夫

Authors(English)

Hideyuki Katoh, Takashi KOBAYASHI, Haruo YOKOTA

掲載誌(和文)DEWS2006 論文集

Citation(English)

Proc. of DEWS2006

Vol, no, pages

Vol. , No. , pp. 7C-o1

発行日 / Pub. date

2006, 3

URL

http://search.ieice.org/

権利情報 / Copyright

本著作物の著作権は電子情報通信学会に帰属します。
Copyright (c) 2006 Institute of Electronics, Information andCommunication Engineers.

Powered by T2R2 (Science Tokyo Research Repository)

DEWS2006 7C-o1

Web サービスベースのワークフロー管理における障害を考慮したアクティビティスケジューリング手法
加藤 英之†

小林

隆志††

横田

治夫††,†† 東京工業大学 大学院 情報理工学研究科 計算工学専攻 〒 1528552 東京都目黒区大岡山 2121†† 東京工業大学 学術国際情報センター 〒 1528550 東京都目黒区大岡山 2121
E-mail: †katoh@de.cs.titech.ac.jp, ††tkobaya@gsic.titech.ac.jp, ††, †yokota@cs.titech.ac.jp
あらましワークフロー管理システムでは , アクティビティを適切に割り当てることが処理効率の改善につながる．

我々はこれまでに，近年注目されている Web サービスを用いたワークフローに着目し，その特徴を考慮したアクティ
ビティの割り当て方法 OXTHAS を提案し ，その有効性を示した．Web サービ スを前提とすると，1 つの Web サー
ビスが特定のワークフローエンジンのみから利用されるとは限らないため負荷状況を正確に把握できない．OXTHAS
では，Web サービスの過去の処理履歴を利用して負荷状況を推定し，処理負荷サイズを考慮してアクティビティを効率良く割り当てる．本稿では，より実際の環境に対応させるべく，ネットワークやハード ウェア等の障害を考慮に入れ，タイムアウトを設定し ，効率の良い処理を可能にする再割り当て手法を提案する．さらに本稿では，シミュレー
ションにより，提案手法の評価を行う．
キーワード

Web サービス，ワークフロー，Web とインターネット

A Failure-aware Activity Scheduling Method for Web-Service BasedWorkow Management
†
††
††,†
Hideyuki KATOH , Takashi KOBAYASHI , and Haruo YOKOTA† Department of Computer Science, Graduate School of Information Science and Engineering,Tokyo Institute of Technology

2121 Ookayama, Meguro-ku, Tokyo, 1528552 Japan†† Global Scientic Information and Computing Center, Tokyo Institute of Technology
2121 Ookayama, Meguro-ku, Tokyo, 1528550 Japan
E-mail: †katoh@de.cs.titech.ac.jp, ††tkobaya@gsic.titech.ac.jp, ††, †yokota@cs.titech.ac.jp

Abstract In a workflow management system, appropriate allocation of its activities greatly contributes to improvement of its efficiency. We have proposed OXTHAS, a load-balancing method of scheduling the activities inworkflow management systems using Web services. The OXTHAS makes the activities be allocated to appropriate
executors based on the estimation of their processing capacity using execution histories in workflow engines. In thispaper, we propose a failure-aware re-scheduling method for the OXTHAS using process timeouts under the networkand system failures. To allocate activities appropriately, the estimated processing capacity and timeout duration
are re-calculated with considering the penalty for a failure when a process timeout occurs. We then evaluate theeffectiveness of the proposed methods through simulations.
Key words Web Service，Workflow，Web and Internet

1.

はじめに

ス，アクティビティ・インスタンスと呼び，その自動化された
プ ロセスを管理するシステムとしてワークフロー管理システ

プロセス（ 作業）の一部もしくは全てを自動化するものとしムが提案されている [1], [2]．ワークフロー管理システムの導入てワークフローが提案されている．ワークフローではプロセス

により，人的コストの削減など 様々な メリットが期待できる．

をアクティビティ（ 工程）の集合とし ，実際に流れる具体的な

現在，商用・研究用を問わず多数のワークフロー管理システム

プロセスやアクティビティをそれぞれ，プロセス・インスタンが存在する．近年その普及に伴って，処理する仕事量は膨大になってきており，負荷分散の重要性が増している．

3 0)45#768#94;:

"!$#&%'(!)!+*-,/.-01'(!2!

< = > ?

一方，ネットワークを介して HTTP と SOAP を用い，ソフト
ウェアシステム間で通信を行うオープンな技術である Web サー

  
 

ビスが注目されている [3]．Web サービスは，実行環境に依存しないアプリケーションの連携が可能なため，CORBA や DCOM

  
 

 
 






などの分散オブジェクト技術よりも利用が容易である．Web サー





ビ スが登場した当初は，SOAP，WSDL，UDDI など の基盤となる技術についての検証が行われ，その後 WS-Security，XML
Signature などのセキュリティ・相互接続性の確保について研究

図 1 ワークフローのプロセスモデルされてきた．現在，BPEL4WS（ 注 ）, WS-BusinessActivity や WS1（ 注 2）

AtomicTransaction（ 注 3）, WS-Choreography（ 注 4）, WS-CAFなど

DEDEDE
GFHDE
L
GF HGF HIKGFMF HIK 5J IKJ IK1J J ONを用いた Web サービ スの実用化に向けた仕様の策定が行われ
QSR

ている．
BPEL4WS は XML ベースのワークフロー定義言語であり，

ikR

ikR

WS-BusinessActivity や WS-AtomicTransaction はアプリケーショ

ンの動作やトランザクションの信頼できる結果を調整する方法

QSR

QSR

* -+ ,/.1032"+54
687:9<;=7?>A@* 6ABC

を提供する．WS-Choreography は複数の Web サービ スの協調動作を実現する．また，WS-CAF 仕様は，複数の Web サービ
ikRス間でトランザクションに関する重要な情報を共有できるようにシステムの設定を行う．これらの仕様の登場により，ワーク  x
  1 1
 "!#$%&!(') 
ikR

 
  1 1
 "!#$%&!(') P  H   "!#$%&!(') 

ikR

ikR

ikR

TVUPWXZYZ[\^]=_

uvljwm#yx npz{orx }|:qts  "!#$(~uPuljm orqts
11

`baPcedgfAhjikR

フローを Web サービ スを用いて実現することが盛んに研究さ
TKUPWXZY1[\5]

れている．

11

TKUPWtXZYZ[\^]しかし，これらの仕様では，障害対策や負荷分散などに関しては十分に言及されていない．ワークフロー管理の一般的な実現

図 2 ワークフロー管理システムのアーキテクチャ

方法としては，1) 集中管理手法，2) 分散管理手法，3) エージェントによる手法，などがあり，障害対策，負荷分散共にそれぞ定処理能力を再計算，もしくはタイムアウトの値を調整し，再れで考慮すべき点が異なる．我々はこれまでに，Web サービス

スケジューリングを行う．

を用いたワークフローにおける障害対策手法として集中管理に

以下では，まず，本稿の対象となるワークフロー管理システ

適した手法 [4]，分散管理，エージェントによる実現に適した手ムのモデルについて説明した後，前述の OXTHAS について簡法 [5] を提案してきた．また，我々は集中管理に適した負荷分散

単に述べる．次に，このワークフロー管理モデルにおけるタ手法としてスケジューリング戦略 OXTHAS(Observed Execution

イムアウトの概念について言及し ，タイムアウトを利用し たTime History and Activity Size based scheduling) [6], [7] を提案し

OXTHAS 再スケジューリング戦略について説明する．そして，てきた．しかし ，[6], [7] では，障害時におけるスケジューリン

シミュレータを用いて，タイムアウトを用いた OXTHAS の性

グについては言及していなかった．

能評価を行い，その効果を示す．最後に本稿をまとめ，今後の

本稿では，我々が提案したスケジューリング戦略 OXTHAS に関して，サービスの故障やネットワークの障害等を考慮し，そ

課題について言及する．
2.

対象となるワークフロー管理モデル

ケジューリング戦略を提案する．OXTHAS では，エグゼキュー

2. 1

プロセスモデル

タ毎のワークフロー・エンジンから観測した各アクティビティ・

ビジネスプロセスはグラフに例えられる (図 1)．ビジネスプ

インスタンスの過去の実行時間の履歴と，そのアクティビティ・

ロセスはノード と矢印から成り立っており，ノード はアクティ

れらに対応するために，タイムアウトを用いた OXTHAS 再ス

インスタンスの処理負荷サイズから推定処理能力を算出し，アビティを意味し ，矢印は依存関係を意味する．複数のアクティ

クティビティ・インスタンスを適切なエグゼキュータに割り当

ビ ティが 矢印でつながり，それらがビジネスプ ロセスを構成てることで負荷分散を実現する．このとき，ネットワークやエする．

グゼキュータの障害に対応するために OXTHAS にタイムアウ

2. 2

トの概念を導入し，タイムアウトが起こった場合には，そのエ

本稿では，図 2 のような集中管理型のワークフロー管理シス

グゼキュータで発生したタイムアウトの回数も考慮に入れて推テムのアーキテクチャを対象とする．図 2 のワークフロー管理

ワークフロー管理アーキテクチャ

システムは，主にワークフロー・エンジンとエグゼキュータか（ 注 1）：http://www-128.ibm.com/developerworks/library/specication/ws-bpel/（ 注 2）：http://www-128.ibm.com/developerworks/library/specication/ws-tx/

ら構成されている．ワークフロー・エンジンとは，前述したビ（ 注 3）：http://www.w3.org/TR/ws-chor-reqs/

ジネスプロセスを自動化するための制御や管理を行う部分であ（ 注 4）：http://www.oasis-open.org/committees/tc home.php?wg abbrev=ws-caf

る．このシステムの動作の概要は次の通りである．

2. 2. 1

動作

フロー・エンジンは任意のエグゼキュータを共用することがで（ 1 ） ワークフロー・エンジン内のスケジューラは，クライきることを前提とする．また，ワークフロー・エンジンは自分アントからのキューに入ってきたプロセス・インスタンスをが処理しているプロセス・インスタンスやアクティビティ・イ

1 つずつ取り出し ，その中で最初に実行すべきアクティビ

ンスタンスに関して，どこのエグゼキュータに処理のリクエス

ティ・インスタンスを決める．それと同時にスケジューラは

トを渡しているかについては把握しているが ，他のワークフ

そのプロセス・インスタンスの情報をプロセス・インスタン

ロー・エンジンが処理しているプロセス・インスタンスやアクステーブルに格納する．あるいは，エグゼキュータから返っティビティ・インスタンスに関しては知らないものとする．
Web サービスベースのワークフロー管理てきたアクティビティ・インスタンスが入っているキューか

2. 3

ら 1 つずつ取り出して，そのアクティビティ・インスタンス

まず，ネットワーク経由での Web サービス利用を前提としたが属するプロセス・インスタンスに関してプロセス・インス
タンステーブルから情報を取り出し ，次に実行すべきアクティビティ・インスタンスを決める．
（ 2 ） スケジューラは，実行すべきアクティビティ・インスタンスの情報と，各エグゼキュータが実行可能なアクティビ
ティの情報から，そのアクティビティ・インスタンスをどの
エグゼキュータに割り当てるかのスケジューリングを行い，対応するエグゼキュータの処理キューに入れる．

ワークフロー管理システムを考える．その場合，（ 1 ） 1 つのエグゼキュータの行うアクティビティ・インスタンス処理が 1 つの Web サービスである．
（ 2 ） エグゼキュータの行うアクティビティ・インスタンス処
理を提供する Web サービスを複数のワークフロー・エンジ
ンで共有する場合がある．
といったことが考えられる．

（ 3 ） 各エグゼキュータもキューを持ち，キューの先頭にある

まず (1) については，エグゼキュータは 1 種類以上のアクティ

アクティビティ・インスタンスから 1 つずつ処理していき，

ビティ・インスタンスの処理を Web サービスとして提供するこ処理が終了したとき，ワークフロー・エンジンのキューにそとが考えられる．そのため，各エグゼキュータの処理能力を考の処理結果を返す．

える際には，処理内容毎に考慮する必要がある．なお，ここで（ 4 ） ワークフロー・エンジンはエグゼキュータからの処理結はエグゼキュータ内で同時に処理できるアクティビティ・イン

果について，ACK(処理結果の受理) もしくは NACK(処理結スタンスは 1 つに限ることとして議論する．複数のアクティビ

果の拒否) を同一のエグゼキュータのキューに入れる．

ティ・インスタンスを実行する環境は，物理的なプロバイダに（ 5 ） エグゼキュータは ACK/NACK を受けたことをワーク
フロー・エンジンに知らせるために，ACK/NACK の受理をワークフロー・エンジンのキューに入れる．

複数の論理的なエグゼキュータをマップすることでモデル化できる．
また，個々のアクティビティ・インスタンスの入力データの（ 6 ） ワークフロー・エンジンはエグゼキュータから ACK を

ファイルサイズが一定でないことが処理時間に影響を与える場受けた時，次のアクティビティ・インスタンスについての割合を想定する必要がある．本稿では，処理時間はファイルサイ

り当てを行う．

ズに比例すると考える．さらに，各エグゼキュータの能力や環（ 7 ） 以上を全てのプロセス・インスタンスの処理が終わるまで繰り返す．
2. 2. 2概要

2. 2. 1 節の手順において，各アクティビティ・インスタンス

をどのエグゼキュータに割り当てるかを考慮することによって，システム全体の負荷分散を行うことが可能となる．手順 (2) のところで，一定時間を経過しても (3) が行われなかった場合，
タイムアウトが発生し ワークフロー・エンジンは別のエグゼ
キュータにアクティビティ・インスタンスを割り当てる (リトライ)．このとき，同じアクティビティ・インスタンスのリクエ
ストが複数回発生することになるが，(4) により，そのうちの 1
つだけを採用するようにしている．そして，リトライが起こった場合，最初に割り当てたエグゼキュータから処理結果が返ってきてもそのエグゼキュータには NACK を送信し，必ず，最後に割り当てたエグゼキュータからの処理のみを採用する．このリトライの際に，タイムアウトをどのように設定するか，どのように再割り当てを行うかの戦略によってエグゼキュータ障害時のシステム全体の負荷分散を行うことが可能となる．
ここでは，ワークフロー・エンジンは複数存在し，各ワーク境が一定でないことが考えられる．これは，単純にあるアクティビティ・インスタンスの処理能力が Web サービスを提供するプロバイダの環境等によって異なる場合や，ネットワークの良否による処理の遅延やタイムアウトの発生などの場合が考えられる．
(2) については，この場合，エグゼキュータに溜っているキューの中のアクティビティ・インスタンスのリクエストは複数のワー
クフロー・エンジンから出されたリクエストの集合である．また，1 つのエグゼキュータを複数のワークフロー・エンジンが利用するだけでなく，そのエグゼキュータが提供している機能を
Web サービス以外の形態で利用する可能性もある．あるワーク

フロー・エンジンが知ることができる情報は自身が管理するア
クティビティ・インスタンスに関してだけであり，エグゼキュー
タの処理性能を知るためにキューの全長を把握することは困難である．そのため，ワークフロー・エンジンが知ることのできる情報は，ワークフロー・エンジンがエグゼキュータに処理を要求してから，その処理が完了してそのワークフロー・エンジ
ンに戻ってくるまでの時間の観測値である．それは，キューでの待ち時間とエグゼキュータ内の処理時間，およびネットワー
ク遅延等の合計の値である．

以上の前提を踏まえて，我々はワークフロー管理システムで






 



 

負荷分散を行うためのスケジューリング戦略 OXTHAS を提案した．OXTHAS では各ワークフロー・エンジンが利用できる"!$# 

情報は，処理が完了したアクティビティ・インスタンスの入力
データのファイルサイズと観測される実行時間の履歴であるた"!$#     "!$# "!$#%"!$#'& め，それらの情報からアクティビティ・インスタンスの割り当てを決定する．それらは，ネットワークの状況やエグゼキュー
タ上での他の処理といった環境も考慮したものとなる．なお，
  

 

る．また，障害時の対応に関しては後に説明をする．
3.

  


これらの情報は，ワークフロー・エンジン毎に異なるものとな

OXTHAS スケジューリング戦略

図3

ここでは，我々が提案した OXTHAS スケジューリング戦略

OXTHAS-N の例 (N=3)

について簡潔に説明する．詳細は [6], [7] を参照されたい．
3. 1があまり使用されていないために，待ち時間がほとんどない場

推定処理能力合，他のエグゼキュータよりも ce ,a の値が大きくなることが

まず以下のように変数を定義する．

k• プロセス・インスタンス番号: P = { p1 , . . . pi , . . . pl }• アクティビティ番号: A = {a1 , . . . a j , . . . am }kpi における a j の処理負荷サイズ : s pi ,a j•pi における a j が ek で処理可能であるかど うかを示すマッjj場合もある．

k

3. 2

OXTHAS-N

アクティビティ・インスタンスの処理負荷サイズが大きい場

エグゼキュータで処理可能な場合は 1，そうでない場合は 0

合は，当然 ce ,a の値が最も大きいところに割り当てるべきだ
k

となる.

•

ティ・インスタンスはそのエグゼキュータの得意なアクティビ
ティ・インスタンスの ce ,a の値も相乗して大きくなってしまう•iある．また，そのエグゼキュータで処理をしていたアクティビ
ティ・インスタンスを多く処理していたため，他のアクティビ• エグゼキュータ番号: E = {e1 , . . . ek , . . . en }ピング :m p ,a ,ejjが，逆に処理負荷サイズが小さい場合は，必ずしも ce ,a の値kpi における a j の観測実行時間: t pi ,a jjが最も大きいところに割り当てなくても，次に ce ,a の値が良kjいところに割り当てる方が偏りが減って効率的である．そこ
処理負荷サイズ s p ,a は，アクティビティ・インスタンスija j の入力データのファイルサイズを表し，観測実行時間 t pi ,a jはワークフロー・エンジンがエグゼキュータにリクエストを出してから，エグゼキュータで処理が終わってワークフ
ロー・エンジンに返ってくるまでの時間を表す．つまり，処理時間の他にエグゼキュータのキュー内での待ち時間，ネッ
トワークの遅延の時間などを含む．また，リトライが起こった場合，タイムアウトの値を処理がそのエグゼキュータから返ってくるまでの暫定的な観測実行時間として推定処理能力を計算する．

で，OXTHAS-N では候補となる ce ,a の値の高い N 台のエグゼk

イズを分割するための閾値を設け，処理負荷サイズに応じた割り当てを行う．閾値の決定方法は等分割，整数比分割，ce ,a のk割が最適であった [8] ため，以下ではこれを用いる．
整数比分割では，アクティビティ・インスタンスの処理負荷サ
イズを分割するための閾値は , wi = (処理負荷サイズのボーダー
ライン )，n = (分割数)，S max = (過去の履歴の中でのアクティビ
ティ・インスタンスの最大サイズ) とし，次のように定める．

ビティa j の推定処理能力 ce ,a を以下の式で算出する．
k

j

wi =

i
n

X
.X

l
X
s p ,api =1ijt pi ,a j· m p ,a ,e )ijでは，割り当てを決定する区切りの処理負荷サイズの決定方法

Xに関しては，過去の履歴から最も大きい処理負荷サイズをとm pi ,a j ,ek

りだして，OXTHAS-2 はその処理負荷サイズを 1 番目と 2 番

pi =1目に処理能力の高いエグゼキュータに処理を担当する処理負この推定処理能力 ce ,a は単位時間当たりの仕事量の平均値
j

荷サイズの幅が 2:1 の割り当てになるように処理負荷サイズの閾値を決定する．3 つのエグゼキュータ間の負荷分散を行う

を過去の処理時間から求めている．
推定処理能力 ce ,a は，値が大きいほど ，そのエグゼキューk· S maxk=1

例えば，2 つのエグゼキュータに負荷を分散する OXTHAS-2

k

l

k

k

j
j=1

cek ,a j =j

値に応じた分割等いくつか考えられる．実験結果から整数比分以上の変数を用いて，エグゼキュータ ek における各アクティ(

j

キュータに対し ，アクティビティ・インスタンスの処理負荷サ

j

タの処理能力が大きいことを示す．しかし，ce ,a の値が大きいkj

ことには他の要因も考えられる．例えば，そのエグゼキュータ

OXTHAS-3 では同様に，3:2:1 の比率になるように処理負荷サ

イズの閾値を決定する (図 3 を参照)．

4.

OXTHAS 再スケジューリング戦略

OXTHAS-N は，エグゼキュータの負荷分散のみを考慮しているため，ネットワークやサーバの障害などによりエグゼキュー

る．ネットワークの混雑による速度低下の場合は，OXTHAS では推定処理能力に反映されているため，ここでは故障した場合について考慮する．故障検知のみを目的とする場合，ある程度長くタイムアウトを取ることで，故障検知を行うことができる．

タが故障した際，処理自体が途中で止まってし まう．そこで，故障を検知する時刻は故障する前に割り当てられたアクティビ

エグゼキュータが故障しても処理が止まらず，さらに処理効率

ティ・インスタンスがタイムアウトした時であるため，タイムの低下を最小限に防ぐ 必要がある．この問題点を解決するたアウトの値が短い方がより早く故障を検知することができる．

めに，本稿では OXTHAS 再スケジューリング戦略を提案する．

しかし，あまりに短いタイムアウトを設定する場合，処理時間

以下では，OXTHAS 再スケジューリング戦略としてタイムア

が遅いアクティビティ・インスタンスに対してもタイムアウト

ウトの利用方法について説明し ，OXTHAS に適用するタイムを行ってしまい，検知ミスを起こすことを考慮に入れなくてはアウトの利用方法を示し ，OXTHAS における再割り当て手法

ならない．

について説明する．
4. 1

タイムアウト の利用方法

タイムアウトを用いることには大きく分けて次の 2 通りの目
的がある．以下では，その 2 つについて詳しく議論する．

• 処理効率の向上• 障害検知4. 3

再スケジューリング戦略

以上のことを踏まえて，故障検知の対応のみを目的とするため，「 タイムアウトの発生=エグゼキュータもし くはネットワー
クの故障」と考える．そして，タイムアウトが起こった場合，そのエグゼキュータにアクティビティ・インスタンスが割り当てられないようにするために，推定処理能力 ce ,a の値を下げる．
kjもしくは，割り当てられても，すぐにタイムアウトが発生する

一つ目の処理効率の向上に関しては，処理性能の悪いエグゼ

ようにタイムアウトの値を下げる．前者を推定処理能力調整法，キュータにアクティビティ・インスタンスが集中してしまった

後者をタイムアウト値調整法とし，以下のように定義する．

場合，処理効率を改善させる場合がある．これは，あるアク
ティビティ・インスタンスでタイムアウトが発生し ，別のエグ
ゼキュータにリクエストをし 直した場合，その処理時間は (タイムアウトの値 + 処理時間) となるため，タイムアウトの値だ
け処理時間が増加するため，タイムアウトによる時間のロスを補うことが可能となる．
一方，障害検知に関しては，処理が途中で停止することなく終了させることが目的である．まず障害にはエグゼキュータの推定処理能力調整法
先ほど 定義した推定処理能力にタイムアウトの発生時を考慮に入れて，c0e ,a を以下のように再定義する (Rexe はそのエkj

グゼキュータでタイムアウトが発生した回数．α は定数)．
0

ce ,a
k

j

=

cek ,a j
1 + α · Rexe

タイムアウトの発生時，その推定処理能力は α = 1 とす

故障やネットワークの故障，混雑による速度低下等が考えられると 2 分の 1，3 分の 1・・・となり，そのエグゼキュータにる．また，故障にも一時的なものとすぐには復旧しないものがアクティビティ・インスタンスを割り当てないようになる．

ある．ネットワークが混雑することによる速度低下の場合，通タイムアウト 値調整法

常より時間はかかるが処理は行われる．しかし，エグゼキュー

タイムアウトが発生した場合はそれ以降に割り当てるアクタやネットワークの故障の場合，アクティビティ・インスタンス

ティビティ・インスタンスに関して，タイムアウトの値 T exeの処理自体が行われず，プロセス・インスタンスの処理がいつを次のように定める．(β，T init は定数)までも終了しないことになる．そのため，どのような割り当て方法を用いた場合であっても，タイムアウトを利用して別のエグゼキュータに再割り当てをすることが必要である．また，故障から復旧した場合，そのエグゼキュータにもアクティビティ・
インスタンスを割り当てることが望ましい．
4. 2

OXTHAS におけるタイムアウト の利用

T exe = T init − β · Rexe

タイムアウトの値は T init = 1000，β = 100 とすると 900，
800・・・と減っていき，故障したエグゼキュータに割り当てられてもすぐにタイムアウトが発生し，再割り当てが起こる．

OXTHAS では，その時その時で不確定要素を踏まえて推定もし，タイムアウトが発生した後にそのエグゼキュータから処理能力を計算することでキュー長の偏りまでを把握してアク処理が返ってきた場合，故障検知ミスか故障からの復旧を意味

ティビティ・インスタンスを割り当てている．キュー長が長くするため，c0e ,a や T exe の値を最初に定義した値に戻す．この方なる場合は推定処理能力が低下し，そのエグゼキュータにアク法を取ることで，一時的な故障に対応することが可能となり，

ティビティ・インスタンスが割り当たらないようになる．そのさらに故障傾向が高い場合は，タイムアウトのペナルティを大結果，同じエグゼキュータのキュー長が常に長くなってしまう

きくするという効果がある．

kj

ことを防ぎ ，処理効率の向上を実現している．そのため，前述再割り当てを行う時は，再割り当てを行うアクティビティ・

のタイムアウトの利用方法として 2 つ挙げたが，処理効率の向インスタンスをすでに割り当てたエグゼキュータには基本的に上のためのタイムアウトの利用は OXTHAS では必要ない．

は割り当てないようにする．そのため，もしエグゼキュータがそこで，OXTHAS では障害検知としてタイムアウトを利用す

10 台の場合，同じアクティビティ・インスタンスで再割り当て

が発生する度に割り当て対象となるエグゼキュータの数も 9 台，  

8 台・・・と減っていく．そして，再割り当て対象エグゼキュータ')(+*-,+.0/  

台数 Nexe と OXTHAS-N の N の関係が，132547698;:=<?>

 
%&Nexe < Nとなってしまった場合，OXTHAS-Nexe で再割り当てを行う．

"$#



!





5.

評

5. 1

シミュレーション内容

 

価 



前述した OXTHAS におけるタイムアウトの利用方法の検証

































































と再スケジューリング戦略の有効性を示すために [6] のシミュ
レータを用いて，シミュレーションを行った．最初に，アクティ

図 4 タイムアウトの値を変化させた時の総処理ステップ数

ビティ・インスタンスに設けるタイムアウトの値を変えていったときの OXTHAS-N(N=3) とランダ ムにおけるタイムアウト の効果を調べ，OXTHAS では処理効率改善のためのタイムア

 

&('*)

ウトの利用は必要がないことを検証する．次に，1 台のエグゼ調整法を用いた OXTHAS-N を比較する．

&('.-

 
%
$

キュータを途中で故意に故障させたときのタイムアウトの効果
を，OXTHAS-N(N=3) において通常の OXTHAS-N と提案した

&(',+

&('0/
&('*1



&('.2

!#"







推定処理能力は過去の履歴から求められるものであるため，



初めの 1000 ステップまでは，ランダム割り当てを用いる．そ

れぞれ 10 回測定を行い，その平均を取る．実験結果の各グラ











 

フの誤差棒は 95 パーセント信頼区間を表す．
エグゼキュータは 6 台，ワークフロー・エンジンは 2 台とし，

図5

 

      







      OXTHAS-3 におけるタイムアウトなしのときの各エグゼキュー

各ワークフロー・エンジンでは同じ数のプロセス・インスタン

タのキュー長の変化

ス (プロセス・インスタンス数は 200 個) を処理し，プロセス・
インスタンスは 10 ステップに 1 つ到着し ，それぞれのプロセ

 
&('*)

ス・インスタンスをどこで処理するかなどはそのワークフロー・
エンジンしか管理していない．ビジネスプロセスは分岐などの &('. %$ない単純なものとした．エグゼキュータの処理性能や，プロセ
ス・インスタンス，アクティビティ・インスタンスのサイズなすべて同じにしてある．そして，各エグゼキュータではすべて

&('0/
&('*1



&('.2

!#"


どはランダムで決定される．また，すべてのプロセス・インス
タンスが持つアクティビティ・インスタンスの数は 5 として，

&(',+









のアクティビティ・インスタンスに関して処理可能であるとする．また今回は，エグゼキュータの部分的な故障は考えず，故


































































障の時は，そのすべてのアクティビティ・インスタンスの処理が不可能であるとする．
5. 2

結果と考察

図 6 ランダムにおけるタイムアウトなしのときの各エグゼキュータのキュー長の変化

図 4 は，タイムアウトの値の変化に伴う総処理ステップ数を測定した結果である．OXTHAS は再割り当て手法を含まないはないということが分かる．さらに，ランダムにおける最小値

通常の OXTHAS-N である．なお，タイムアウトの値が 200 ス

より，OXTHAS-N の方が早く処理されているため，処理効率

テップ以下の場合，タイムアウトを永遠に繰り返し処理が終了の向上のためのタイムアウトの値の設定は必要ない．

しなかった．この図から，ランダムではタイムアウトの効果がまた，図 4 における OXTHAS とランダムそれぞれについてタあることがわかるが，適切なタイムアウトの値は 300 から 400

イムアウトを設定しない場合の各エグゼキュータのキュー長のステップという非常に狭い範囲であることがわかる．パラメー

遷移を比較するために，10 回の試行のうちのある 1 回のそれぞ

タが異なった場合には処理が終了しない場合も考えられるため，れのキュー長の遷移を図 5，6 に示す．このシミュレーションで常に適切なタイムアウトの値を設定することは難しいことがわ

は，処理性能が高い順に (エグゼキュータ 2，3)，(エグゼキュー

かる．一方，OXTHAS-N では，そのグラフに極小値が存在し

タ 1，4)，(エグゼキュータ 0，5) となっている．図 6 から分かる

ないため，タイムアウトの値によって処理効率が向上すること

ように，ランダムでは，ほぼ等分に処理が割り当てられるため，

bBiajFkml
an

g/
9h



 -/.10243 

;-9.10<>=@?BADCFEHG


+,-/.0132

5/67989:

-9.10

'(

(*)

$





























































































"!




# 





































































図 7 故障時における再割り当て手法の違いによる総処理ステップ数の
比較


































図 9 タイムアウト値調整法の有無による OXTHAS の e2 の累計リト
ライ数の変化

.0/=
21;
430
45>
76984
;:0
2<CBF
ED

 

OQPSRUTWV'XY

β = T init /100 とした．
「 5 台，タイムアウトなし 」の線は故障さ

!#"%$


!#"'&

せた 1 台を最初から抜かしてエグゼキュータを 5 台でタイム

!#")(

 

!#"+*



アウトなしで測定し たときの結果である．調整法を用いない

!#"%,



OXTHAS よりも調整法を用いた場合の方が，タイムアウトの

!#")-


 

値が長くなっていった時の総処理ステップ数の低下を抑えてい

ることがわかる．さらに，タイムアウトの値が 500 ステップか

ら 1400 ステップの間では，「 5 台，タイムアウトなし 」よりも









 


































.0/=
21;
430
45>
76984
;:0
2<@?=A

!#"%$


!#")(

勝る場合もあるということを示している．また，2 つの調整法

!#"+*



!#"%,


提案した調整法の方が効率よく処理が行われている．このことは，低信頼なエグゼキュータを含んだ 6 台のエグゼキュータの処理が高信頼な 5 台のエグゼキュータの処理に匹敵，もしくは

!#"'&

 

の間では差が見られず，推定処理能力調整法とタイムアウト値

!#")-



G0H2I2J=K+L2M2N

 






 



 
!#"

$%



MNOQPQRTSQUQV% &

RTSVU1WYX[Z]\N/^a1_B`bac9deFf

&'

-/.0
ACBEDGFGHJILK

 

)*

OHPNQ <>=@?FADCBE 243

46587:9<;>=@?

+

01LNM

IKJ




,

調整法の両手法を併用した場合にも差は見られないため，2 つの調整法の間に相乗効果は見られない．



図 8 は各エグゼキュータのキュー長の変化を表し，図 9 は故障したエグゼキュータ 2 の累計リトライ数の変化を表す．これ

























 



















らの図はタイムアウトの値が 1000 ステップのときの 10 回の試行のうちのある 1 回の試行についてのグラフである．まず，推図 8 推定処理能力調整法の有無による OXTHAS の各エグゼキュータのキュー長の変化

定処理能力調整法の効果について説明する．推定処理能力調整法を用いない OXTHAS の場合の図 8 では，故障に対して早期に反応できていないため，故障後も長いステップ数の間，エグ処理性能の低いエグゼキュータのキュー長が長くなってしまい，

ゼキュータ 2 のキュー長が増加している．一方，推定処理能力

処理性能の高いエグゼキュータは逆に Idle 状態になってしまっ

調整法を用いた場合では，故障に対して早く反応し，そのエグている．一方，図 5 から分かるように，OXTHAS-N では処理

ゼキュータにアクティビティ・インスタンスが割り当たらず，別性能の高いエグゼキュータにアクティビティ・インスタンスがのエグゼキュータに割り当てられ (この図の場合はエグゼキュー

より多く割り当てられ，すべてのエグゼキュータを効率よく使

タ 1，3，4)，全体の処理が早く終わる．また，タイムアウト値

用している．また，あるエグゼキュータのキュー長が長くなっ調整法を用いない場合の図 9 では，累計リトライ数が全処理がた場合，別のエグゼキュータに割り当てられるように推定処理

終わるステップ数まで増加している．一方，タイムアウト値調能力が柔軟に働いていることも分かる．そのため，OXTHAS に整法を用いる場合では，故障したエグゼキュータ 2 累計リトラ

おいては処理効率改善のためのタイムアウトは必要ないことがイ数の増加は 4000 ステップほどで止まっている．これは，タ分かる．

イムアウト値調整法により，タイムアウトの値が短くなりエグ

図 7 は，故障が発生する場合にタイムアウトを変化させていったときの調整法を用いない OXTHAS と 2 つの調整法を比ゼキュータ 2 から他のエグゼキュータに早期に再割り当てが行
われ，その結果全体の処理も早く終わる．

較したものである．エグゼキュータ 6 台中の 1 台 (エグゼキュー

以上のことから推定処理能力調整法とタイムアウト値調整法

タ 2) を，2000 ステップ 目に故意に故障させて測定を行った．

がエグゼキュータの故障時に有効であるということがわかる．

推定処理能力調整法は α = 1 とし ，タイムアウト 値調整法は

6.

関連研究

Lie-jie Jin らは，プロセス・インスタンスを一定時間毎にワー

クフロー・エンジンに投入する際にワークフロー・エンジンで割する際の分割方法について，より良い方法を検討すること，様々なプロセス・インスタンスの到着率やプロセス・インスタ
ンス毎にアクティビティ・インスタンスの数や種類が異なる時，
アクティビティ・インスタンスの処理負荷サイズに偏りがあるの処理前の待ち時間を減らすようにどのワークフロー・エンジ

場合等に対応することや，エグゼキュータが複数のアクティビ

ンに入れるかについての負荷分散手法を提案している [9]．そティ・インスタンスを同時に処理できる場合，エグゼキュータのの中で分散ワークフロー管理システムにおけるワークフロー・故障が多発する場合やエグゼキュータが一部の種類のアクティ

エンジン間の負荷分散を行うために負荷指標を定義している．

ビティ・インスタンスの処理ができないような部分故障が発生

しかし，今回のように複数のワークフロー・エンジンがエグゼする場合などの様々な状況に対応するようにすることなどが挙

キュータを共用する場合には，それぞれのエグゼキュータの負げられる．また，実際にこのワークフロー管理システムを実現

荷を計算し，その負荷に応じて処理を振り分ける負荷分散が重し，実際のシステムでも同様の有効性が言えるかを検証するこ要となってくるが，この研究ではエグゼキュータ間の負荷分散とが重要である．

に関しては対応していない．
また，Koji Nonobe らは，資源制約付きスケジューリング問謝辞題に関するアルゴ リズムを提案している [10]．これは，ワーク

本研究の一部は，文部科学省科学研究費補助金特定領域研究

フロー・エンジンが 1 つであるような閉じたワークフロー管理(16016232)，独立行政法人科学技術振興機構 CREST，および東システムにおける仕事の割り当てに関しては最短で処理が完

京工業大学 21 世紀 COE プログラム「大規模知識資源の体系化

了する割り当て方を提供してくれる．しかし，複数のワークフと活用基盤構築」の助成により行なわれた．
文

ロー・エンジンがあり，それぞれのワークフロー・エンジンが自身の仕事にのみ割り当てや監視を行っているような場合や，
ネットワークの環境が動的に変化するような場合，このアルゴ
リズムをそのまま利用することはできない．

Workow Management Coalition. http://www.wfmc.org/.

[2]

戸田保一, 飯島淳一, 速水治夫, 堀内正博. ワークフロー -ビジネスプロセスの変革に向けて-. 株式会社日科技連出版社, 1998.
株 式 会 社 日 本ユ ニ テック DigitalXpress 編 集 部. SOAP UDDI
WSDL Web サービ ス技術基礎と 実践 徹底解説. 技術評論社,[3]

さらに，ワークフローにおいてプロセス・インスタンスの処理の順番を動的に変更することにより期日に遅れるプロセス・

2002.
[4]

加藤英之, 小林隆志, 横田治夫. ワークフローの自動実行における障害対策. In DEWS2004. 電子情報通信学会, Mar. 2004. I-12-02.

[5]

Neila Ben Lakhal, Takashi Kobayashi, and Haruo Yokota. Throws:

インスタンスの数を減らすスケジューリング手法を提案している [11]．これは処理時間とルートを推測しプロセス・インスタ

An architecture for highly available distributed execution of web ser-

ンスの処理の順番を適切に決定している．しかし，本稿で目的

vices compositions. In Proc. of RIDE WS-ECEG'2004, pp. 103110.

としている負荷分散や障害対策については述べていない．
その他に，分野は異なるが ，Web サーバにおいて，小さなIEEE, Mar 2004.
[6]

ファイルを求めるリクエストから優先的に処理することによりキューでの待ち時間を減らし，パフォーマンスを改善する研[7]

究 [12] や，分散システムにおいて，遅延予測方法と遅延時間のマージンの決定方法を提案し，それらを組み合わせ障害を検知加藤英之, 小林隆志, 横田治夫. Web サービ スを用いたワークフ
ローにおける負荷分散手法. 信学技報 DE2005-46(2005-7), 電子
情報通信学会, Jul. 2005.
加藤英之, 小林隆志, 横田治夫. Web サービ スを用いたワークフ
ロー管理における負荷分散手法のシミュレーションによる評価.
DBSJ Letters, Vol. 4, No. 2, pp. 2528, Sep. 2005.

[8]

加藤英之. Web サービスベースのワークフロー管理におけるアクティビティスケジューリングに関する研究. 修士論文, 東京工業
大学, Jan. 2006.

[9]

Li jie Jin, Fabio Casati, Mehmet Sayal, and Ming-Chien Shan. Load

する研究などがある [13]．しかし，Web サービスベースのワー
クフロー管理システムにこれらの手法をそのまま適用すること献[1]はできない．

balancing in distributed workow management system. In Proc. of
SAC2001, Aug. 2001.

7.

おわりに

[10]

Koji Nonobe and Toshihide Ibaraki. Formulation and tabu search algorithm for the resource constrained project scheduling problem. In
C.C. Ribeiro and P. Hansen, editors, Essays and Surveys in Meta-

本稿では，Web サービスベースの集中管理型ワークフロー管理における障害を考慮した負荷分散手法を提案した．具体的には，

heuristics, pp. 557588. Kluwer Academic Publishers, 2002.
[11]

ワークフロー管理モデルを説明し，ワークフローと Web サービ

ow systems. In Proc. of SAC2004, Mar. 2004.
[12]の 2 つの調整法を提案した．そして，シミュレーションを行う
ことにより，提案手法は障害の発生時にもその処理効率をあまり低下することなく処理可能なことを示した．
今後の課題とし ては，より効率的な再スケジューリング 戦
略にするための提案手法の改良や，OXTHAS-N における N 分

Mor Harchol-Balter, Bianca Schroeder, Nikhil Bansal, and Mukesh
Agrawal.

の障害を考慮に入れて，タイムアウトを考慮して再スケジューリング戦略として推定処理能力調整法とタイムアウト値調整法

Applyingscheduling techniques to minimize the number of late jobs in work-

スの特徴を考慮に入れたスケジューリング戦略 OXTHAS について説明した．さらに，OXTHAS に基づいて，エグゼキュータ

Gregorio Baggio, Jacques Wainer, and Clarence Ellis.

Size-based scheduling to improve web performance.

In

Proc. of TOCS2003, May 2003.
[13]

Raul Ceretta Nunes and Ingrid Jansch-Porto. Qos timeout-based selftuned failure detectors: the effects of the communication delay predictor and the safety margin. In Proc. of DSN2004, Jun. 2004.