九州工業大学電気工学科村上周太Mean　Cycle　Times　of　the　Multiqueue　with　aGating　and　with　a　Exhaustive　Service

九州工業大学研究報告（工学）No．57 1988年9月      57

ゲート式及び全処理式非割り込み優先処理   巡回型多重待ち行列の平均巡回時間

（昭和63年5月27日 原稿受付）

西日本工業大学電気工学科大木正彦 西日本工業大学電気工学科深川幸紀

九州工業大学大学院電気工学専攻中山  ^悌

九州工業大学電気工学科村上周太

Mean Cycle Times of the Multiqueue with  aGating and with a Exhaustive Service

      by Masahiko OOKI

      Yukinori FUKAGAWA       Yasushi NAKAYAMA       Shuta MURAKAMI

Abstract

  Amultiqueue with gating service discipline and a multiqueue with exhaustive service discipline under non−preemptive priority are studied for the performance evaluation on the token ring or token passing protocol of the local area networks．

  As for the multiqueue with limiting service， gating service or exhaustive service， a strict analy．

sis has been studied and important results are obtained．

  On the other hand， a multiqueue with priority discipline has not been investigated so much．

The authors show a balance equation for the multiqueue with a gating and with an exhaustive ser．

vice under non．preemptive priority and then， we derive a mean cycle time in the strict form． It is shown that the mean cycle time for both service discipline is same and coincident with a mean cycle time of the multiqueue with one limiting service under non−preemptive priority．

      なっていて，平均列待ち時間に関しては，全処理式がす

Lまえがき        ぐれていることが指摘されている。

 巡回型多重待ち行列は，トークンパッシングプロトコ    ー方，到着メッセージ（ジョブ）に外部優先権が付与

のポーリング方式のデータ伝達システムの性能評価のた   され，有用な知見が得られている。

めの数学モデルとして重要であり，制限式処理とゲート    本文では，平均列待ち時間特性が制限式処理方式に比

式処理及び全処理方式の巡回型多重待ち行列が厳密に考   較してすぐれているゲート処理方式と全処理方式におい

時間は 制限式〉ゲート式〉全処理式 の順に小さく   ている非割り込み処理の巡回型多重待ち行列を考察し，

最初に，着目処理施設に関する扱い者到着時メッセージ    2．2 記号の定義

数確立に関する平衡方程式を示す。次に，この方程式を    （1）κ   ：処理施設台数

母函数表現形式方程式に変換し，この方程式から得られ    （2）LST ：ラプラススチェルチェス変換 るP個の関係式を導出すると共に，扱い者の平均巡回時    （3）⑧  ：たたみ込み演算記号

間を導き出す。       （4）ρ  ：外部優先レベル数でρ＝1が最高レベル

       （5）λ、  ：優先レベルゴのメッセージ到着率

       （6）Hz（り ：優先レベルτのメッセージ処理時間

 本文での待ち行列システムは，K台の対称な処理施設    （7）H、＊（8）：H、（ののLsT

（窓口，待ち行列）を一人の扱い者（トークンあるいは   （8）穗  ：H湿）の平均 制御権）が歩行過程を伴って巡回処理をする。扱い者が    （9）H。（τ）：扱い者の歩行時間分布 ある一台の処理施設に到着したとき，待ち室バッファ内    ㈹ 酷（り：H，（引のLST の待ちメッセージのうち最も高い優先レベルのメッセー    （11）万。 ：H。（τ）の平均

ジをゲート式かつ非割り込みで処理して次の施設へ巡回    （12）H。。（Z）：扱い者の巡回時間分布。巡回時間は，扱

の施設へ巡回してゆく。待ち室バッファ容量は無限大と         次の回に同じ施設に到着するまでの時間

し，メッセージ到着過程はボアソン分布に従うものとす         と定義する。

る。また，メッセージ処理時間と扱い者の歩行時間は一    （13）H㌔（8）：H。。（DのLSτ

メッセージ到着と処理の時間分布は優先レベル毎に互い    （1θ τ。  ：扱い者の平均一巡巡回時間

に異なっているものとする。      ⑯ P。、．。，，。、，＿，。．：扱い者が着目処理施設に到着し

       た時点で，この施設のバッファに各優先

Hc（t

と

↓引   （1カ＿，㌘∵る灘

       （1θL。FΣΣ…Ση、P。，。，。，＿，。，，。川．＿。ρ        ゆてロれいハニ   れタ  

       L。、は扱い者が着目施設に到着したとき，待ち

       メッセージのうち最も高い優先レベルのメッセー

λZr・  12（t）   … （19。一入（1一勘）＋為（1一鋤）＋．．．礼（1一脇）

λ1＿   1（t）   ＿   ジの平均待ち数

1    4       ・

λトーL  Hp（t）  一←   ・滅（h） ←

↑日

図一1 非割り込み優先処理巡回型多重待ち行列

       （20  ρ、，戊＝λ￡H、 （1 ≦ τ ≦ρ，  1 ≦元≦ρ）

       （21） ρ、，cy＝λ、 Hcシ （1 ≦↓ ≦ρ）

       （22） ρi，c＝λ。 Hc

       2．3 平衡方程式と平均巡回時間

       扱い者が第ノ回目に着目処理施設に到着した時点と，

      第ノ＋1回目に同じ着目施設に到着した時点のバッファ

ー     内待ちメッセージ数同時確率に関する平衡方程式は以下

      のようになる。

ゲート式及び全処理式非割り込み優先処理巡回型多重待ち行列の平均巡回時間        5g

 君、・，π2 ，η♂

一∫°°点α1（・1 ）急色（・ジー・・）嘉偽（・♂一・・臨・・

       dHρη1（τ）⑭H，。ω

＋∫°°嘉α1（・1 ）・・（・礁色（・∴一・・）P；・−

       d醗・・（τ）⑧H。。（z）

川       一｛G1僻（z3），1，エ，，1，…，1）＋G、（Hr（z、），コc・，1，…，1）＋…

＋∫°°嘉1α1（・・ ）・・（・・ ）・・（・のP；・…d蜘・）⑧疏（・）

＋∫°°・・（・1り・・（・ノ）・・（・・りP；・…繊（・）

    ここで・、（・、）は・鋤一e芸τ呉ある．

       ＋G。（H㌧（z，））＋P。｝H㌔（z、）

    G1（1，…，1，コcρ）十G2（1，…，1，⑳ρ）十…十Gρ（コcρ）十P。

（1） 一｛G1僻（・。），1，…，1，・・。）＋G・（Hナ（・・）・1・・…1・…）

       十…十Gρ（Hち（zρ））十Po｝H㌔（zρ）

 式（3）において第 式をエ、で微分後にコc、→1とする手 川頁をτ＝1〜ρまで行なえば式（4）が導出される。

このα （ηz）は期間君の間にη 個のメッセージが到着す

 ここで，定常状態において式（1）をpレベルまで含めて      i

母函数表現形式に変換すれば式（2）となる。      L。ρ＝ρ。，、L。、＋ρ．，，L，，＋＿＋ρ．，。L。ρ＋ρ。，。。

 母函数は次のように定義されている。

      式（3）をL。、（1≦τ≦ρ）を未知数と考えて整理すれば

  輪㍗…噌   。仰  式（，）の連立方程式が得られる．

   ＝ΣΣ…ΣP。，。，＿，。，。、，．．．，。。エ、…エ。

    ゆニ ゆぐ ニ   カアニむ      （  ＝ 1〜ρ）       −1個

G1（コc1，コc2，…，コcρ）＋G，（エ，，＿，コC。）＋…＋G。（コC。）＋P・

＝Gl（H言（z），コσ、，＿，コc。）H三。（z）

 ＋G、（H夢（2），コc、，…，エ。）H㌔（z）＋…

 ＋G。（Hち（z））酷。（z）＋P。H㌻。（z）    （2）

L。1＝ρ1，、L。1＋ρ1，，L，，＋…＋ρb。L。。＋ρ1，。。

L。，＝ρ2，1Lq1＋ρ，，、L。，＋…＋ρ，，ρL。ρ＋ρ2，。y L。，＝禽，1L。1＋ρ，，、L，，＋…＋ρ，，ρLqρ＋ρ・，。。

1一ρ1，1 一ρ1，2 一ρL3 ・…  一ρ1，ρ 一ρ、，11一ρ・，・一ρ・，3・…一ρ・，ρ

一ρ。，1 一ρρ、＿．＿＿ 1一ρρ・

Lql

Lq3

．Lqρ

ρ1，cy

ρ2、cy

ρ3，cy

ρρ，cy

（5）

 式（2）がゲート式非割り込み優先処理方式の母函数表現    式（5）においてρ／，。y＝λ H。。が未知数で残されているが，

形式の平衡方程式である。この方程式を解けば，本シス   このH。。は式（6）のように（直観的に）得られる。

テムの扱い者到着時の離が得られるカ㍉式（2）を解くこ また，臨（・）を独立性仮定7）のもとで近似をすれば

とは容易ではない。            （7）となり・これから平均巡回時間が求められるが・これ

L。、を含んだ形の扱い者の平均巡回時間を，やや直感的   H。。＝KH。＋（κ一1）｛L。1H、＋L。、H、＋…＋L。ρH。｝（6）

に与え・これらの式からL・を含まない形の平均巡回時 @甑（。）≒Hご・（。）｛G、㈱。），1，…，1）

間を導く。

       十G2（H芽（8），1，…，1）十…十Gρ（Hち（8））十Po｝κ一1 （7）

 式（2）において，コcεを除いた全てのコC」を1とおくこと

をτ＝1〜Pまで行えば，式（3）が得られる。         式（6）を（5）に代入整理すればL・・を未知数とする連立方        程式が式（8）の形で与えられる。

G1（コc、，1，＿，1）＋G，（1，…，1）＋…＋G。（1）＋P・

 ＝｛G1（H㌣（z、），1，＿，1）＋G2（H芽（z1），1，…，1）十…

         ＋G。（Hち（z1））＋P。旧㌔（ZI）

Gl（1，コc2，1，…1）＋G，（∬，，1，…，1）＋…＋G。（1）＋P・

一｛G1ぽ（Z2），コc、，1，・∵，1）＋G、（Hr（z・），1，…，1）＋一          ＋G。（Hち（z、））＋P。｝麟。（z，）

1一κρ1」一κρい2 ．＿＿．．＿一κρ11。

一κρ，、11−Kρ2、、    −Kρ2、。

−Kρ、，1一κ角，，1一κρ，，， 一κρ、，。

−KρA1  −Kρ兄2   ・・・・・・・…   1一κρρρ Lql

L叩

κρ11cy

κρ2，cy κρ3、cy

Kρρcy

・  ノ

（8）

G・（1，1，コc3，1，…1）＋G・（1・コc・・1・…・1）＋…＋G・（1）＋P・ （3）   式（8）をL。、について解けばL。、は式（9）のようになる。

      κρ、，。      長分布

  Lq ＝ρ    

    1＿κΣρゴ、」       （2）、酷（8）：B」（τ）のL8T。．酵（8）は既知の結果例え        ノ＝1

      ば文献（2）から

式（9）を（6）に代入して整理すれば       、Bナ（8）＝」雪｛8＋λ、（1＿疎（8））｝

       カ

     1＿Σρ」、」      として与えられている。

       ゴコ        

  』1一κ烏、κH・   （1° （・）瓦・平均副稼醐間 一瓦／（1一厄）

       」＝1      （4）  γ輪，」＝λz万」 （1 ≦ τ ≦ρ， 1≦」≦ρ）

（10が本章での主要な結果であり，この式は単一制限式非       e一λ・￡（λzτ戸 割り込み優先処理巡回型多重待ち行列の結果・）とも＿ （5）αF・、・

致し，また，λ」＝0（2≦」≦ρ）の優先権のない巡回型    3．3 平衡方程式と平均巡回時間

多重待ち行列の平均巡回時間にも一致している。       優先レベルρまでの場合について平衡方程式を記述す

施設での平均処理時間（扱い者の平均滞在時間），すな   述し，母函数表現形式平衡方程式はρレベルの式を示す わちL。1H1＋Lq2H，＋…＋L。。H。を加算して計算され，   ことにする。

式（10となる。

      K瓦      瓦・，顕一｛∬向（・1怠色（・ニー励無（・∴一⇒・

τ＝

P一κ喜    （11）［雇蹴（m、一砺）瀞（＿砿，。，衡

こ口ま文献、）、）7）の結果に一致する．       dB1⑧π1（・』（・）

3．全処理式の平均巡回時間    廿偽（   πゴη， ）Σ］α、（π1ノーm1  ητ1−0）息（・ゴー⇒

エ1待ち行列システムの定義    ［鳥゜°α1（・1）蕊（…嚇一d蜘）］d馴

本章の待ち行列は・前章の待ち行列とほ1ま同様である ＋｛∫°°⑭怠（  アどピη、 −m，）Σ（η1 −m1  η↓10）｝・

ごう㌶遼欝籔㌻竺二⊆㌫ ぽ⑭砺（m、）P。，。，。、dB、⑧・・（τ）］⑭

理し・そのレベルのメ・セージがなくなるまで処理した ＋∫°°α1（・1・）・，（・，・）・、（・，・）d基。（・）  （11）

後に次の施設に巡回してゆく。本処理方式のもとでは，

扱い者が一つの処理施設に到着したとき，何個のメッ   式（切の母函数表現形式は式（吻となる。

セージを処理するかは直接的には表わされない。しかし，

既知の副稼鯛間長分布（のL∬）・）を用いることに Gl（品▲恥・・鋤＋G・（』・… …）＋

；二麟㌶ζ㌫＝：▲灘i−｛ご（㌶∴…，輌（B♪（め＿，鋤

て導出できる．       ＋G麟ぬ石・…鋤＋…＋鋼勧＋酬㌔（・）

ここで，副獺鯛長分布は，一個のメ。セージで起 ただし乏・は次の表現式である．   （1力

動される稼動期間の分布で・次のような分布である・  乏L加一、，1）＋、、（1一工2）＋…＋、、．1（1−、，、−1）

 扱い者は，まず一個のメッセージを処理するが，この

       十λ￡＋1（1一コτ￡ト1）十・・・… 十λρ（1一コcρ）

処理時間中に新たなメ・セージが到着すると・これも続  すなわち告。一、、（1−、，」

いて処理を行う。以下全ての新たな到着メッセージを処

理し，メッセージがなくなるまで処理が継続される期間   式⑫は前章の式（2）において右辺の理（z）が疎（乏 ）にお が副稼動期間長分布である。      きかわっているのみである。

 3・2記号の定義（本章で新たに使用される記号）｝）    式（均においてコc、（1≦τ≦ρ）を除いた全てのコc、

 （1）B、（τ）：優先レベルτのジョブによる副稼動期間   （1≦ノ≦ρ，」キのを1とすれば式（13が得られる。

ゲート式及び全処理式非割り込み優先処理巡回型多重待ち行列の平均巡回時間        61

 Gl（コc1，1，1，＿，1）十G2（1，1，＿，1）十…十Gρ（1）十Po

−｛G1（1，1，＿，1）＋G、（Bタ（z1），1，＿，1）＋…

 ＋G。（Bご（z、））＋P。｝H㌔（z1）

 Gl（1，コじ2，1，舎w．，1）＋G，（エ，，1，1，＿，1）

 十G3（1，1，．．．，1）十…十Gρ（1）十Po

＝｛G1（B言（z2），エ、，1，…，1）＋G，（1，1，＿，1）

1−（κ一1）乃、1 −K乃12  ………−Kz、ρ  一κ万1 1−（K−1）乃、2 ………・・…一一κ万ρ

一肱1 一κ恒 1−（κ一1）乃．、……一κ乃、，

 一κ万、｜    一κ万12     −K）㌦3  ㌧㌧    i

 一κγρ1       一κγρ2      ・・・・・・・・・…  1−（1（−1）γ」，、ρ

Lql

Lワ2

Lqρ κρlc

κρ2c

Kρρc

＋G、（Bき（z2），1，…，1）＋…＋G。（B♪（z、））＋P。｝H㌔（z、）      （1の       式（1カをたとえばクラメールの方法で解けば

 G1（1，1，コσ3、1，．◆．，1）＋G、（1，コσ、，1，＿，1）

  ヰG、（、，、，1，…，、）＋…＋G。（1）惜      ｛加＋司κ・・」（1＋川 一｛α（Br鳳1，砥，1，…，1）      輪＝｛亘（1＋副1一κ（喜（馴＋万川

 ＋G，（B芽（23），コc、，1，＿，1）＋…      ＿

      一方，芳、 ＝λβ は定義式（3）から

＋G・（B掴）＋P・踏・（z・）      ㌍，、、／（1−，、、）となり，これを上式に代入整

 i       理すれば結果Lq、は式（18となる。

G・（1・ ・1・…）＋G・（1・・…1・・σ・）＋ ＋G・（エ・）＋P・   （卜。，、）κ，、c

−｛G1（B蹴1・……脇）＋G（B㌻（石）……・脇）＋… @ 輪＝、−K』       （18

        ＋G。（B葦（Z、））＋P。｝H㌔（Z。） （13      」；1

       さらに式（18を式個に代入整理すれば，扱い者の平均巡 式（13をコc、で微分後にコc、→1G＝1〜ρ）とすれば，   回時間H。，は式⑳で与えられる。

式（凶が得られ，この式をL。、を未知数として行列形式で        1＿￡ρ」、

表現すれば式（19を得る。      万。。＝  」弓 κ万。       （20        1−KΣρ刀

      」＝l

 I・・＝0 ・L・1＋λ1B2L・2＋λハB3L・3＋…＋λLB・Lqρ＋ρ1 c〃    万。シはゲート式の場合と一致している。

 Z・・＝λ・B・L・1＋0 Lq2＋λ・B・L・・＋…＋λ2B・Lqρ＋ρ2cy     扱い者の平均一巡巡回時間丁，は式￠Oに，扱い者が一  i   i   i        i   i （1φ   つの処理施設に滞在する時間の平均値すなわち

Z。ρ一λ諺1L，1＋λ諺，L，、＋λ。万、L。、＋…＋・・L。。＋，。。、  L・・Bl＋L・・B・＋ ＋L・ρB・を加算して計算され・式

      （21）となる。

 1 一万2一γ1，3＿＿一％、Lq1

一γ，パ 1 一γ，，3＿＿一γ、， L。，

一γ｝，1一万、2 1 ＿＿一万、 Lq3＝

一万，1一万，2一万3＿＿  1 Lgρ

ρ1cy

ρ2c9 合。。 （15）

ρρcy

   κHc

T・＝   ρ       ⑳

  1一κΣρ」」

    ゴ＝1

このT。はまた，文献（7）の結果や前章の結果に一致する。

4．まとめ

 式（19においてρ、。。；λ、H。、のH。、が未知であるが前章    非割り込み優先処理のゲート式及び全処理式対称型巡 と同様に次の式で与えられる。       回型多重待ち行列の平衡方程式を示し，これから，扱い

  ＿  ＿       ＿   ＿     ＿     者の平均巡回時間を導出した。この二つの値は互いに等   H。。−KH。＋（κ一1）（Lσ1B1＋L，、B，＋…＋L。ρB。）         、

      しい結果となっていて興味深い。平均巡回時間は，処理       （1θ

      方策に依らないことが指摘されているが，本文では，

 式（1θを（1θに代入整理すれば，L。、を未知数とする連立   ゲート式と全処理式の場合にそのことを実際に示した。

方程式（1カが導出される。       なおまた，平衡方程式はK；1では厳密な式となる。

      さらに，H悔（5）が厳密に決定されれば， K＞1でも

      厳密式となる。しかし，H㌧ッ（5）を式（7）で表現すれば，

この式は独立性仮定のもとでの近似式となり，平衡方程 式も近似式となる。しかし，これらの平衡方程式から，

非割り込みゲート処理式巡回型多重待ち行列のメッセー ジ平均待ち時間の近似値が導出できる可能性もあり，今 後の課題である。

       参 考 文 献

1）H．Takagi； Analysis of Polling Systems ， The MIT

Press， Massachusetts（1986）

2）藤木，雁部㍉通信トラピック理論，丸善（昭和55）

3）W．Chang； Preemptive priorty queues ， Opers。 Res．，13

（1965）

4）野村，塚本；ミポーリングシステムのトラピック解析フ，信

学論（B），J61−B，7（1978）

5）橋田 温；ミゲート式多重待ち行列フ，信学論，53−A，1

（1973）

6）M．Eisenberg； Queues with periodic service and

changeover time ， Opers． Res，，20（1972）

7）深川，村上，吉田；ミ優先処理式巡回型多重待ち行列の近

似解タ，信学論（A），J76−A，9（1987）