マルチメディア通信と分散処理ワークショップ 平成10年 11月
グループ聞の競合解決とグループ内の規定数をみたすプロセス
への資源割当ての分散的解法
村 上 国 志 ↑ ， 和 田 裕
t
，程子学↑
↑:会津大学コンピュータソフトウェア学科t
:
会津大学大学院コンピュータ理工学研究科 分散システムを組定した，デッドロックや飢餓状態の回避等を目的とする資源割当て問題の重要性は既に広く知られており， これまでに犠々な研究が為されている.しかし，昨今のコンビュータネットワーク潔境の著しい普及とそれに伴う分散協調 型アプリケーションの湘加によって，協調作業を行なうプロセスのグループを単位とした資源の競合の解決やより効率の良 い資源の割当て方について考慮する必要性が見られる様になった.そこで，本研究ではグループ聞の資源の競合の状況をモ デノレ化を行ない，その上で，グループ内のある規定数をみたすプロセスに資源を獲得させる為の競合解決アルゴリズムを示 している.D
i
s
t
r
i
b
u
t
e
d
A
l
g
o
r
i
t
h
m
s
f
o
r
R
e
s
o
u
r
c
e
A
l
l
o
l
c
a
t
i
o
n
t
o
P
a
r
t
i
a
l
P
r
o
c
e
s
s
e
s
o
f
a
Group
M
a
s
a
s
h
i
Murakamit
，
Yutaka Wadat
，
Z
i
x
u
e
Cheng
↑
t
:
Department of Computer Software，
University of Aizut
:
Graduate School of Computer Science and Engineering，
University of AizuThe distributed resource allocation problem and its importance are well known and there are many works on resource allocationwhich deal with deadlock-free and starvation-free properties among processes. However
，
the progress of computer network environment causes the increment of distributed cooperation applications and the necessity of efficientway to allocate resources among process groups. In this paper，
we propose a model of resource allocation among process groups，
where a group can start their work onlywhen not less than a quorum ofits processes acquires required resources，
and propose several distributed solution to the problem.1
まえがき
ここ数年におけるコンピュータネットワーク環境の普及 には目を見張るべきものがある.企業や趣味集団等へのコン ヒ・ュータの広い普及に伴い，様々なグループウェア等の分散 協調型のアプリケーションの開発が盛んとなってきている. その様な状況を考慮すると，限りある資源(ハードウェア デバイスやメモリ，通信回線等)を効率的に利用するために， 協調作業をするプロセスのグループ(以下，単にグループと いう)のそれぞれにどの様に資源を割り当てるかを考えるこ とが必要となる. 個々のプロセス単位での資源割り当てに関しては，古く は「哲学者の食事問題/DiningPhilosopher ProblemJ [1] 等に始まり，様々な研究が為されている[
2
]
~[
4
]
.
しかし， それらの多くは，グループへの資源割り当てにそのまま適用 するには不十分だと言える. 例えば，ある2つのプロセス Pl，P2が1つのグループg" を形成し， 1J'Jの 2つのプロセスP3，仰が別のグループ gbを 形成するとする.PlとP3はある資源、Tlを，P2とP4は別 の資源 T2を要求するものとする それぞれのグループは， 協調作業を行なう為にはそのグループに属するすべてのプ ロセスが必要とする資源を獲得しなくてはならない様なア プリケーションを想定する.このような状況で，もしもTl をPlに，T2を仰にといった資源割り当てを行ってしまっ た場合，いずれのグループも作業を行うことができないとい う状態に陥ってしまう. こういった問題のために，我々はこれまでに幾つかの研究 開~[8]を行ってきた.それらにおいて我々は，各グループ はそれに属する全てのプロセスがそれぞれ必要とする資源 を獲得しなくては作業を行うことはできないものとして問 題を定めた.しかし，現実のアプリケーションでは，多数の プロセス(例えば，電子会議の参加者)のうちのある一定数 以上のプロセスが資源を確保すればグループとしての作業 を行うことができるというケースも多くあるだろう.この 様な場合，必要数以上の(獲得作業が遅い)プロセスが資源 の獲得作業を取りやめることで，そのプロセスが属するグ ループの作業の効率化が見込まれ，そのプロセスと何らかの 資源を競合する他のプロセスに資源を被ることで，他のグ ループの作業の効率化も望めるだろう. 本稿では，この様な点を考慮した分散的資源配分問題に ついて第2節で定め，3節ではその問題および拡張問題に関 するタイムスタンプを用いた解法を示している. 4節では， これらの問題や解法についてまとめている.2 モデルと問題の定義
2
.
1
資源割り当てのモデルと問題の定義
{定義1
]
資源割り当てモデル 資源割り当てモデルは， プ ロ セ ス の 集 合P
= {Pl，P2γ ..，Pi，・・.Pn}及 び 資 源 の 集 合R
=
{
r
l
，r
2
'
・..，rj，..・，rm }から構成される. Fは，Pの 部 分 集 合 か ら な る 族 で あ る.つまり F ={G
1，G
2，・・・，G
k
，...，Gd
で ，G
k
c
P
である，このP
の 部 分 集 合G
k
を グ ル ー プ と 呼 ぶ.また，本稿で はV
G
k
1
，Gk
2
ε
F
，G
k
l
nGk
2
=
ゆと仮定する .S
k
は，G
kの 作 業 の 際 に 最 低 限 必 要 な プ ロ セ ス 数 を 表 す も の で{
S
k1
1
< 九 三
1
Gk
1}である .t
k
は ，Gk
で 作 業 す 円 l nぺ Uる際のプロセス数の上限を表すもので
{
t
k
1
1
三九三
九三
1
GkI
}
とする. ある Piがりを要求できる場合，Piはrjに隣接す ると表現する.各プロセスは，それぞれが少なくとも1
個以上の資源に隣接されている.各プロセスは，そ れぞれ隣接している全ての資糠を要求する.各グルー プは，そのグループが作業を行うために必要なプロセ ス数が，要求する全ての資源を確保してからはじめて 作業を行なう. 各資源は，一度に複数のプロセスに割り当てられる 事はなく，最大でも一つのプロセスにしか割り当てら れない.あるプロセス Piに要求される資源の集合を Ric
R
とする.ある資源rjを要求するプロセスの 集合を 円。C P
とする. ある二つのプロセスPilとPi2に関して ，Ri1 nRi2=1= ゅのとき，つまりp
礼ε
乃
，Pi2ε
円 と な るη
が存 在するとき ，PilとPi2は競合を起こすと言う. ある2
つのグループG
1とG
2が，互いにある資源 rjに関して競合を起こしているプロセスPilεG
1と Pi2εG
2が存在するとき ，G
1とG
2は，競合を起こ すと言う. 各 fラ
，R
i，Gk
は，それぞれ静的である.つまり， プロセスおよび資源の集合，そしてその隣接関係とグ ループの構成は動的に変化しないという仮定をする. [定義2
]
デッドロック(
d
e
a
d
l
o
c
k
)
と飢餓状態(
s
t
訂 ・v
a
t
i
o
n
)
デッドロック: いずれのプロセスも必要とする全て の資源を確保する事ができない状態に陥ること. 飢餓状態: あるプロセスに関して決してその必要と する全ての資源を確保する事ができない状態に陥る こと. [定義3
]
グループのデッドロックとグループの飢餓状態 グループのデッドロック: いずれのグループも，その グループに属するプロセスの内の作業に必要とされる プロセス数が，必要とする全ての資源を確保した状態 になる事ができない状態に陥ること. グループの飢餓状態: あるグループが，決してそのグ ループに属するプロセスの内の作業に必要とされるプ ロセス数が，必要とする全ての資源を確保した状態に なる事ができない状態に陥ること. [定義4
]
資源割り当ての分散問題解決のための条件 グループのデッドロックおよびグループの飢餓状態が 起こらないようなプロセスク・ループへの資源割り当て のための分散アルゴリズムを構成するために，本論文 では以下のものを定義とする まず，入力情報として，各プロセスは基本情報(プ ロセス自身の識別子と接続されている辺)，所属する グループの識別子，隣接している資源の識別子，およ びその資源に関して競合を起こし得るプロセスの識別 子を知っているものとする. 次に，同一グループ内での競合を避けるために，同 一グループに属する2
つ以上のプロセスがある1
つ の資源に隣接することはないものとする.本論文では 同一グループ内での競合が起こった場合でも，そのグ ループが必要とするプロセス数が資源を確保できれば よいので，この仮定を取り除くことも可能である. また，ある1
つのプロセスが複数のグループに属し ていると割り当てが非常に繁雑になるため，いずれの プロセスも異なる複数のグループに属することはない ものとする.2
.
2
ネットワークモデル
各プロセスは，同ーのアルゴリズムに基づき，以下 の様なネットワーク環境上で動作するものとする. ここでは，各グループ内の全てのプロセスの間およ び各資源を共用する全てのプロセスの聞にはそれぞれ 無向完全グラフ状に通信路が存在するネットワークを 想定する. メッセージは通信路の双方向に独立して送ることが できる.送信されたメッセージの到達時間は不定であ るが，必ず有限時間以内に相手に届くものとする.ま た，同一通信路の同一方向に送信した複数のメッセー ジは，必ず送信順に届くものとする. 各プロセスは，作業の必要がない聞は待機しており， 本アルゴリズムを利用するアプリケーションプログラ ムやユーザーからの要求を受け取ったときに資源獲得 のための作業を開始する.3 グループタイムスタンプを用いた
分散アルゴリズム
3
.
1
基本的な考え方
各プロセスには Idle，Wait， Competition， ( Com-parison)， Workingの5
つの状態があり，基本的には Idle→ Wait → Competition→ ( Comparison)→ Working→ Idleという状態遷移を行なう.また各プ ロセス間でメッセージの交換が行なわれる事により， 競合の解決を行なう. 各グループ間での競合の解決の為の手法として，グ ループタイムスタンプという概念を導入する.グルー プタイムスタンプとは，グループ全体としてのある事 n x u n べ υ象の発生時刻を示すもので，グループ内で共通の値を 持つ.各グループのグループタイムスタンプを比較す ることにより競合を起こす資源の配分先を決める. ネットワークには，論理時計
[
5
)
が存在し，各プロ セスはこれに基づき様々な事象にタイムスタンプを設 定することができるものとする.また，ある二つの事 象のタイムスタンプが等しい場合，その事象を生じた プロセスの識別子の大小関係によってタイムスタンプ の大小を定めるものとする.それによって，全ての事 象に全順序を導入し，タイムスタンプをE
いに大小比 較することが可能になる. 各プロセスがユーザーやアプリケーションプログラ ムからの資源獲得の要求(以後，単に獲得要求という) を受けて資源の獲得作業を開始した時刻(以後，単に 開始または開始時刻という)を示すタイムスタンプを 記憶し，その値を所属するグループ Gk内の全プロセ ス聞で互いに比較し ，S
k
番目に小さい値 (S
k
番目に開 始したものの開始時刻)をグループ全体の開始時刻と 見倣し ，Gk
のグループタイムスタンプg
t
S
k
とする.3
.
2
メッセージ
処理を進めていく上で交わされるメッセージは，同 一グループ内のプロセス同士で交換されるものと，競 合相手(資源を共用する，他のグループに属するプロ セス)に送られるものとに大別される. 各メッセージの形式とその意味は以下の通りである. 但し，ここでP
i
はそのメッセージを発するプロセ ス自身の識別子 ，P
g
は，P
i
の同一グループ内のプロセ スの識別子 ，TjはP
i
が他のグループと競合している 資源の識別子 ，P
I
はP
i
とある資源を競合するプロセ スの識別子 ，t
S
i
はP
i
の開始時刻を示すタイムスタン プ ，p
t
S
i
はP
i
が資源を獲得した時刻を示すタイムス タンプ ，g
t
S
k
はP
i
の属するGk
のグループタイムス タンプである. 3.2.1 グループ内で交わされるメッセージNOTIFY(Pi
，p
g
，t
S
i
)
:
P
i
が開始したことを所属するG
k内の全てのP
g
に告知するために送信される.ま たg
t
S
k
を求めるために開始時刻であるt
S
i
もあわせ て送信する.QUERY(pi
，P
g
)
:
P
i
が，まだ開始を確認されていな い刊に対して，開始しているか否かを問い合わせる 為に送られる.CONFIRM(Pi
，P
g
)
:
P
i
が ，S
k
個のNOTIFY
を受け 取った時にまだNOTIFY
を受け取っていないプロセ スにANSWER
の送信またはNOTIFY
の確認を求 めるために送信する.ANSWER(pi
，P
g
)
:
QUERY
をうけとーったP
i
が，ま だ開始していない場合に返送する.REPLY(Pi
，P
g
)
:
CONFIRM
を受け取ったおが，ま だ開始していない場合に返送する.INFORM(Pi
，p
g
，p
t
s
i
)
:
P
i
が，必要とする全ての資源 を確保した際に，その事をグループ内の各プロセスに 報告する為に送信する.また ，P
i
のGk
内での資源獲 得順を求めるためにp
t
S
i
もあわせて送信する.ENQUIRY(Pi
，P
g
)
:
P
i
がまだINFORM
を受けとっ ていないG
kのプロセスに対して送信する.STOP(pi
，P
g
)
:
P
i
が，資源を獲得する必要のなくなっ た場合，または獲得後のp
t
S
i
の比較において ，Gk
内 でのP
i
自身の資源獲得時刻のタイムスタンプの小さ な順からS
k
番目以降の時に資源の解放をGk
内に知 らせる為に送信する. 3.2.2 資源を競合するプロセス聞で交わされるメツ セージREQUEST(Pi
，P
I
， Tj，g
t
S
k
)
:
P
i
が 資 源 rjを獲得す るため，それを競合する各P
I
に対し権利を要求する ために送信する.競合解決のためにg
t
S
k
もあわせて 送信する.NONEED(Pi
，P
I
，Tj):P
I
からのREQUEST
に対す る返答として ，P
i
が rjの権利をP
l
に譲ることを伝え るために送信する.RELEASE(Pi
，P
l
， T j ):P
i
が，資源、 Tjに関して競合 を起こしたP
l
に対し，その資源の使用が完了したの で使用の権利を放棄するという旨を伝えるために送信 する.また，資源獲得後の処理において ，P
i
が作業を 行う必要がなくなった場合に，資源の解放を行なう時 にも送信する.3
.
3
資源割り当てのためのアルゴリズム
ここでは 3通りの資源割り当てパターンについて のアルゴリズムについて考えることにする.ケース 1 としてS
k
個以上のプロセスが資源、を確保できればグ ループの作業が開始できる場合.ケース 2としてS
k
個以上九個以内，ケース3としてS
k
個のプロセスが 資源を確保し，グループの作業を開始する場合のアノレ ゴリズムである.初めにS
k
個以上の場合について説 n u d nべ υ明し，このアルゴリズムに対する変更点をそれぞれの 小節において順に書いていくことにする.
3
.
3
.
1
ケース1
のグループ作業開始条件の場合 各状態における処理は，以下の様になる. Idle 資源の要求を開始する前の待機状態である. この状態においては各プロセスが自発的に送出する メッセージ等は無く，グループ内のいずれかのプロセ スから QUERYが送られてきた場合，ANSWERを返 送する .CONFIRMが送られてきた時には ，REPLY を返信して Idle状態のまま待機する.そして，プロ セスはそのユーザーやアプリケーションプログラムか らの要求を受けると Waitに移行し資源の要求を開始 す る 他のグループから REQUESTが送信されてきた場 合，その REQUESTへの対応は ，Piが単独で決める 事はできない.これは，まだ所属する Gkのグループ タイムスタンプが決定できなし、からである. その時に次の2
つの可能性がある (1)GkのSk個以上のプロセスが NOTIFYを送信 していない，つまり Sk個以上のプロセスが Idle状態 である場合. (2)Gkの Sk個以上のプロセスが NOTIFYを送 信済だが，通信路の遅延によりまだSk個以上の NO-TIFYが届いていない. (1)の場合，REQUESTを送信してきたプロセスの グループの方がグループタイムスタンプが早いのは 明白なため，返事として NONEEDを送信するべきで ある. (2)の場合，Gkのグループタイムスタンプを 決定後，相手グループのグループタイムスタンプと比 較して REQUESTに対する返事を決めるべきである. 以上の2つの不確定性を確かめるために ，Piは Gkの未だ NOTIFYを送ってきていないプロセスに QUERYを送信する.その返事として PiはGkの各 プロセスから ANSWER(NOTIFYを送信済のプロ セスは QUERYを無視)を受け取った状態で Sk個 以上 NOTIFYを受け取っていない場合 ，REQUEST を送ってきたプロセスに対し NONEEDを送信し ，Pi は Idle状態のまま待機する .Sk個以上の NOTIFY が送られてきた場合は ，Gkの方がグループタイムス タンプが早い可能性があるため ，REQUESTに対する 返答は保留し，ユーザーなどからの獲得要求の指示を 待つ. Wait この状態に遷移した時刻を開始時刻として記憶 し，Gkに属するPiは NOTIFYを用いてそれをGk内 の全てのプロセスに送信する .Sk個以上の NOTIFY を受け取ったプロセスは Gk内のまだ NOTIFYを受 け取っていないプロセスへ向けて CONFIRMを送信 する.この CONFIRMを受け取ったプロセスがまだ Idle状態の場合は REPLYを返送してそのまま待機， 既に NOTIFYを送信したプロセスはこれを無視する. Gkに属するプロセスから Sk個以上の NOTIFYを 受けとり，かつそれ以外のプロセスから REPLYを受 け取ったら ，NOTIFYに含まれる tSiを並べて早い方 から Sk番目の tSiをグループタイムスタンプとしてC
o
m
p
e
t
i
t
i
o
n
へと移行する. また，この状態の聞に REQUESTを受け取った場 合は先に述べた Idle状態での REQUESTとほぼ同 様の処理を行う .Sk個以上の NOTIFYが送られてき た場合に変更があり，この場合はグループタイムスタ ンプを決定するための処理を行ってからC
o
m
p
e
t
i
t
i
o
n
へと移行するものとし ，REQUESTに対する返答は保 留しておく. は)p<はGkの プ ロ セ 3え か らAnswerを 受 け と っ た 状 簡 で Sk個 以 上NOTIFYを 受 け と っ て い な い 場 合 図 1:Wait状態のフローチャートC
o
m
p
e
t
i
t
i
o
n
Piはまず，全ての必要な資源に関し， その資源を競合し得る全てのプロセスに REQUEST を送信する. その返答として全ての競合相手から NONEEDあるいは RELEASEを受け取った時点で， 全ての資源、が確保できたものと見なし )Gkに属する 全てのプロセスに対して INFORMを送信し，資源の 確保が完了した事を告知する.その後 )Piが Gk内の n H U 4 4 aプロセスから Sk個以上の INFORMが送信されてく るのを待つ.PiにSk個以上の INFORMが送信され てきたら Workingへと移行する.また，資源獲得前に Sk個以上の INFORMを受け取った場合は全ての競 合相手に NONEEDを，Gkに属する全てのプロセス へ STOPを送信して Idle状態へ移行する. この間にPiが他のプロセスから REQUESTを受け 取った場合，または
Wait
状態の聞に受け取ったR
E
-QUESTに対してまだNONEEDを送り返していない 場合，以下のように競合の解決を行なう .REQUEST によって送られてきた相手側のグループタイムスタン プと所属するG
kのグループタイムスタンプを比較し， 相手側の方が小さい場合はNONEEDを返送して Gk 内のプロセスへ STOPを送信，自分の側が小さい場 合は相手からのREQUESTを無視する (REQUEST への返事は保留する)• 図2:C
o
m
p
e
t
i
t
i
o
n
状態のフローチャート Working Sk個以上のプロセスが確保した各資源を 用いて実際の仕事を開始する. 全ての仕事が完了後 ，REQUESTに対する返答を保 留していたプロセスがあれば ，REQUESTを送信して きたプロセスに対して RELEASEを送り，資源を解 放する旨を告知する. その後，Idle状態に戻り，次の要求に対して備える.3
.
3
.
2
ケース2
のグループ作業開始条件の場合 先程のケース1
に条件として tk個以内という条件 が追加されたものである .Idle，W
a
i
t
， Workingについ ては変更がないが ，Competitionに変更点がある.ま た，Comparisonという状態を新たに追加する . Com-petition， Comparisonについては以下の様になる. Competition グループ Gkに属するプロセスPiに ついて ，Sk個のINFORM(Pi，Pg， ptsi)が送信されて くるのを待ち ，PiにSk個の INFORM(Pi，pg，ptsi)が 送信されてきたら羽ゐ，rking へと移行したが，~ゐrking へと移行せずに Comparisonという新たな状態へと移 行 す る Comparison まず，送られてきた INFORMの全ての ptSiの比較を行い，タイムスタンプの小さな順から tk 番目以内に入っているならば ，INFORMまたはSTOP を受けとっていないプロセスに対して ENQUIRYを 送信する • Gkに属する全てのプロセスから INFORM あるb、は STOPが送信されてくるまで先ほどの処理 をINFORMを受け取る度に行う.ここでPiはtk番 目以降ならば Gkに属する全てのプロセスへ STOP， 競合相手へRELEASEを送信する.Gkに属する全て のプロセスから INFORMあるb、は STOPが送信さ れてきたならば Piは tk番目以内かどうかもう一度 同様の処理を行い，ここで九番目に入っていた場合 に Workingへと遷移する3
.
3
.
3
ケース3
のグループ作業開始条件の場合 先程のケース2
のアルゴリズムにさらに変更およ び追加をする.Idle， ¥ぬit，Workingについては変更 がないが ，Competition，Comparisonに変更点がある. Competition， Comparisonにおける処理の変更および 追加については，以下の様になる Competition ここではケース 2で述べたものに追加 をする.要求した資源を確保後で INFORMを送る直 前に ENQUIRYが送信されてきた場合は，既に Gk内 で Sk個以上のプロセスが資源を確保している為にこ のプロセスは Gkに属する全てのプロセスへ STOP を，競合相手へ NONEEDを送信して Idle状態へ移 行することにする. Comparison ここではケース 2で述べたものに変更 をする.メッセージの遅延の影響のために ，Sk個以上 のプロセスが Comparison状態に遷移する事がある ため ，tkという部分を Skに変えて Sk個のプロセス に絞ることにする.-41-3.
4
正当性の検討
はじめに，各グループは，それぞれ単一のグループ タイムスタンプを持つ.あるG
k内の全てのプロセス 間で，それぞれの開始時刻を NOTIFYを用いて相互 に送信，比較してグループタイムスタンプを決定する ため，各グループ毎に統ーされたグループタイムスタ ンプを持つ.また，これは論理時計[
5
]
に基づいてお り，論理時刻とプロセスの識別子を併用することから 各グループ毎のプロセスの持つタイムスタンプは単ー と言える. グループのデッドロックについて， [定義4
]
より，同 一グループ内でのプロセスの競合はないことになる. ある資源に関して競合が起こった場合，それぞれが属 するグループのグループタイムスタンプを比較し，そ の最小値を持つものが資源を確保できる.各グノレープ は異なるグループタイムスタンプを持つため，結果的 に最小のグループタイムスタンプを持つグループは， 必要とする全ての資源を獲得し使用できる.よって常 に少なくとも一つのグループは作業を行なう事がで きるので，グループのデッドロックは発生することは ない. グループの飢餓状態について.各グループは単ーな グループタイムスタンプを用いて資源を要求する.資 源の獲得が終了していないグループの集合の中で最小 のグループタイムスタンプを持つグループから資源を 確保し，作業に移る.作業を終了したグループは資源 を解放し，先程の集合のグループの中で最小のグルー プタイムスタンプを持つグループが資源を確保し作業 を開始する.このようにして全ての資源を要求するグ /レープ全てが作業を行うことができる.また，一度 作 業を終了したグループが再び資源の要求を開始した場 合，未だに作業を開始していないグループよりもグ /レープタイムスタンプは大きいために，先程の集合に は含まれない.よって，グループの飢餓状態が発生す ることはない.4
むすび
本稿では，分散協調型アプリケーションの構築の擦に起 こり得るグループ聞の資源競合という新たな分散問題を提 案し，その解法を示した. 今後，残された問題として，メッセージ複雑度や時間複雑 度等の解析が挙げられる.また，この問題の拡張として， ・グループ内の各プロセスが，ある一定数量以上の資源 を獲得すれば作業を行うことができるものとする. ・グループ全体で，ある一定数量以上の資源を獲得すれ ば作業を行うことができるものとする. ・あるプロセスが，複数のグノレープに同時に属すること が出来るものとする. といった，複雑な条件下での問題について研究する余地があ ると考えられる. また，本稿で定義した問題ではグループ内任意の一定 数(以上)Jという条件の性質上，プロセス単位での飢餓状態 の回避が保証されていない実際のアプリケーションでは， プロセスの飢餓状態が好ましくない場合も多くあるであろ うから，プロセスの飢餓状態の回避のための研究も行う必要 がある.参考文献
[1]K. M. Chandy and J. Misra，“The Drinking Philosophers Problem，"ACM 1'rans. Prog. Lang.
Syst. ， VoJ.6， 4， pp. 632・646，1984.
[2] Injong Rhee，“A fast Distributed Modular Algcト
rithm for Resource Allocation，" Proceedings of the 15th International Conference on Distributed Computing Systems， pp. 161-168， May， 1995.
[3] D. Ginat
，
A. U. Sha出.arand A. K. Agrawala，
“
An Efficient Solution to the Drinking Philoso -phers Problem and its Extensions，" Proceeding of the 3rd International Workshop on Distributed Al-gorithms
，
Lecture Notesin Computer Science，
VoJ. 392，
pp. 83-93. 1989.[4] H. Kakugawa and M. Yamashita，“Local Coter
-ies and a Distributed Resource Allocation Algo -rithm
，
"τransactions of Information Processing Scトciety of Japan， VoJ.37， 8， pp. 1487・1496，Aug. 1996
[5] L. Lamport，“Time， Clock ， and Ordering of Events in a distributed System，" Communications ofthe ACM， Vol. 21， No. 7， pp. 558・565，July 1978.
[6] Zixue Cheng， Ton広junHuang， and Norio Shiratori，
“
A Distributed Algorithm for Resource Allocation among Process Group，" Proceedings of The 9th International Conference on Information Network -ing，
pp. 443-448，
Dec. 1994.[7] Y. Wada， Z. Cheng， and T. Huang，“A distributed Algorithm for Allocation of Resources to Process Groups with Acyclic Graphs，" Proc. of the Interna -tional Conference on Parallel and Distributed Pro -cessing Techniques and Applications (PDPTA'97)
