〃〃　中山泰雄　　　〃〃　矢鳴虎夫九州大学工学部電子工学科吉　田　　　将

多端末入出力装置を用いた情報処理教育とシステム

      の待ち時間等について       （集団到着待ち行列の場合）

（昭和52年5月31日 原稿受付）

情報処理教育センター深川幸紀

   〃〃 中山泰雄    〃〃 矢鳴虎夫 九州大学工学部電子工学科吉 田   将

On the Waiting Time and the Waiting Line for Education System      of Information Processing with M已ny Terminals

         On Batch・Arrival Many−Server Queue

       by Yukinori FUKAGAWA        Yasuo NAKAYAMA        Torao YANARU

       ABSTRACT

  We are Planning，at our Educational Center for Information Processing， to get basic conside−

ration for processing speed and waiting time and reasonable size of a input−output devices・In this paper， we have considered the mean waiting number of students and waiting time and system

idle−probabihtylunder assumption that input−output devices（for example， character−display−termi−

nal）is many servers． System−model is same as Batch−Arrival， Many Server Queue with feed−back・

1．まえがき       コンソ＿ル        デイスプレイ

情報処理教育センターでは，集団情報処理に関する，      ・  334聯げイスク装置 計算機システムの処理方式（運用方式），処理速度等の基     膓膓3、プリンタ ＾

礎的検討を行ない，よりよいシステムを作成することを

めざしている。筆者らは前報1）2）3）のなかで，入力過程のな    穿竺ドリ＿ダ い待ち行列で，集団情報処理システムを近似して，主と    （マー久カード読雌勧｝

3115

中 央演算 処理．装置

f反魁｛1記 憶ノ∫工c 記 憶 装 置

チャンネル

一     一      ＿       0029

3348

ティスク ハ ノ ク

3348

ティスク ハ ノ ク

叢

3348

ティスク ハ ソ ク

3348

ティスク ハ ノ ク

東

して待ち人数について検討を行なった。このモデルでは    カート射L装置  1；1・冨竃聾      テ：竺ク

システム運用開始直後の様子はよくわかるが，オープン

^{ハ ノ ク}

処理システムでは入力過程をもち前回のモデルでは長時     一      構内回刷式，

3277モデル2    3277モァ レ1 ＿         一        ，  〔600111ま＼延土（可｝  『

間後の様子については無力である。情報処理教育セン     デ，，プ、イ猫  ・，…蹴  ，，，プ、イ纐一一一一 。、。プ、イ錯

3277モアル1      27〆モデル1

ターでは、昭和50年12月より図一1に示す構成で，キャ    ＿、ディスプレイ装γモデ，レ2、1fi  ．、バ，クァ．プ用

置として用いられ，オープン処理システムとして良好な

動作をして現在におよんでいる。教育センターのシステ   分布とするのは，プログラムの新規登録や操作がふなれ ムで，学生はインプット・マークカード・リーダーと，    な学生はディスプレイ装置使用の時間が長く，プログラ 複数台のディスプレイ装置を用いて，プログラム入力，   ムの一部訂正等はすぐ終了するなどと考えるとランダム ファイルへの登録プログラムの訂正や，バッチ区画の   処理（指数分布）が適当であるからである。

コンパイラーにプログラムを引き渡す方式で，プログラ    モデルを以下のように決める。

ム処理を行なっている。また学生が処理システムにくる     処理装置（ディスプレイ端末台数） 〃 様子は，個々がばらばらにくるよりは，ある程度の集団     到着過程  平均到着率λでそのサイズは〃2C沈 で，それも特定の時間帯にくる。       ここでCηは勿人到着する確率

 本文では，ディスプレイ装置を，装置操作時間や，学   処理過程 平均処理率μの指数処理分布

生が装置を専有したままで思考を行なう時間等も，シス     待ち室容量 無限大

テムの処理時間とみなす処理装置と考え，これを集団到      退去過程  確率4で退去（1一めで帰還 着待ち行列に帰着させて処理速度や待ち時間の解析を行    2．2 システムの平衡方程式

なった。       今，処理系内に時刻rで学生がη人いる確率をP。（ ）と 2．待ち行列にっいて

 2．1．待ち行列の定義

 本文でとりあつかうモデルを図一2に示す。処理装置 はキャラクターディスプレイ端末である。現実のシステ ツでは，ディスプレイ端末操作を終了した学生は，中央 のシステムプリンターから出力される結果をうけとるよ うになっていて、結果のいかんをとわず，ディスプレイ

する。

 平衡方程式は

0＝ 一（λ十〃μ）Pη十〃μ｛7Pη＋1十々μ4（1−（7）Pη

     カ

   ＋λΣC仇、Pη一沈 （κ≧ん）    （1）

    m＝0

0＝ 一（λ十ημ）Pη十（η十1）μ4Pη＋1十ημ（1−（7）Pη

     れ

   ＋λΣCmP。一栩 （0＜η＜〃）  （2）

     m＝1

0＝ 一λ1≧｝十μ7Pl      （3）

端末をはなれていく力儲果がすぐにディスプレイ鑓 

（1）（2）式に。・＋1をかけて各々。＝ 一。。と。；1−

に表示されるような会話型システムやCAIシステムで

初C仇の到着人数 λて到着

処理・装置（入出力端末）

    々台

4で退去

（1一ので帰還

一1の和をとれば

0＝｛〃μ4（1一克）一λエ（1−Aω）｝G1ω   十λ尤4（κ）G2（ガ十λ∬Po、4（エ）一〃μ4」P成々

  一λ∫×（C項）      （1）

・一一λ・G・（・）＋μ・（1−・罐（エ）＋吻P…

   一λ∬円。ヰλ∬×（C項）         ②

       ロロ

但しA（x）＝ΣC頑η， G1（∬）＝ΣP泌η

      η＝1       η＝々       カ  

   G2（∬）＝ΣP話η       η＝1

      C項＝P。（C1∬1＋C2x2十C3∬3十……十C々一♂｝1）

      図一2

      十Pl∂（Cl∬1十C2∬2十C3∬3十・…・・十G−2xゐ一2）

    ． 一      ＋P，∬2（Cl∬ ＋C、∬2＋C，エ3＋……＋C、．，∬克一3）

 図一2に示すモデルは通常，集団到着複数処理装置待

 、       十 ち行列（Batch−Arrival Many−Server Queue）と呼ばれ

る。計算機の処理をうける学生（以後これを呼とよぶこ      

      一一      ＋P、．3∬々−3（C1ピ＋C2エ2）

とがある）は，到着時間間隔がフンダムで勿人ひとまと

      一     ＋P ．、ピ2（C1エ1）

めでその確率がC仇で到着する。そして処理装置（ディ

スプレイ端末）が空いておれば，先着順に処理をうける。    ここで（1） ② をこのままで取り扱うのは複雑なので，

この処理時間の分布は指数分布とする。処理分布を指数    ここでは最も簡単なケースについて式を解析する。

（イ）到着人数サイズが勿＝〃≧〃なる時      々μ（μ向

   胸＝プC項一〇         ＋｛〃μ4（1−。）一λ。（1−。〃）P・

（1） （2yは各々（1） （2） となる。

O＝｛〃μ4（1−x）一λx（1−．ガ∬）｝αω一ぴ）ここで蕊1薫㌶る．これを保；1

     十λ∬M＋1几一〃μ4P々ピ      （1）        ．       るため〃μ4（1一エ）一祉（1一κ ）＝0の根について検討する。

②∵警）−1≒鋤ピ叶三②㌧二i㍑㌶認鵠）こ鴎み：腰

G（。）一，xp（一居砒）〔∫一織  よ（1大1；㌶∴（1−。・）

     ・xp（∫己此）此    一λ｛・M＋L（1＋膓）・＋膓｝

     ＋峰Pぽ輌〕 にお㌫漕1−（1＋罐

 ここでDは積分定数である。      とおく。

     ∫1書砒一ρ1・g（・−1）    ∫（・）の根｛・ついてρ・一〃』＜1の条件で

篭ぽて炉（1一醜を部分積分を繰∫ω＿（1＋況一。 ⑤

G（・）・−1 ﾍ‖・・一・（1−・）  ア（・・）一（〃＋1）・評一（1＋膓）＝・ ⑤

鵠 識（1一  ⑤に二ll増1代㌶＜1

   ＋ρ（ρ＋1）（ρ＋1；．．．（，＋々−2）・（1−・）〃−2  ∴∫（・）は・＜・＜1の間で重根をもたない．

＋，（ρ＋1）．告々−1）（1−・戸一1｝古  晒）について⇒＞1の時に限り・＜ 1

      で唯一つの根をもつことをのべる。

   一几＋（1−∬）一切        ②

 G2（1）が有限であることによりD＝0である。      ρ  ρ

      ル）一・・＋L（1＋旦）・＋互

ここでG・（・）のもともとの麟より几，Pl，…P・一・ @ ＋1）（・・＋〆1＋……⇒）

㌫具であらわすことが出来て それ1ま以下剛 ・（・）一・〃＋・…＋……峠とおけば

R一

ﾏ（ρ＋1）（ρ＋6……．．（ρ＋ −1）几 （3） 9（・）−9（1）一〃一膓〉°により゜q＜1に

R＝ o一ρ（ρ＋1）（耀・・（ρ＋〃−1）  ル）一。一一（1＋膓）。＋膓

      ＋，（，＋1）（ρ＋211…．．（，＋ −2）｝凡   ＋1）（・・＋・−1＋・・…・＋・一膓）

   ニ，（ρ＋1）（ρ＋2）三！…・（ρ＋〃−1）孔   ＝鴇二霊漂蜘）戸

以下（2） の・の徽をみることによ｝）計算出来る力鴻   …＋（1＋。。＋。』＋…＋ぴ一1）｝

雑なので略す・         ＝（。一。。）｛。・＋。。。・−1＋。8。・一・＋……

（1） について      …部一1。一（1＋。。＋．．．＋ぴ一1）｝

  G1㈲一一｛      λエ ＋1輪（1−∫）一λ∬（1−♂）｝G・ω     一〇

 今エ＝1〃。1＜1なる根があったとする。         几，丑，…，P ．（M十1）を未知数とする連立方程式が得られ，

 1＋∬。＋∬』＋…＋∬r1＝〆＋∬ぱM−1＋…＋工釦Llx     これと確率の正規化条件で几〜P々が求まるが，非常に複         ≦1エIM＋1エIM．1エ。＋＿＋lxlXr1     雑なので本文では以後〃≧々の場合をあつかう。

        ＝1 °IM＋1 °IM｝1∬°＋…＋1 °1ぴ一1      3．系の状態確率の計算

これは矛盾である．       系の状態をあらわす確率はいろいろあるが・ここでは

      最初に，系が空である確率R，処理装置が1台以上あい

 ∴ ∫（エ）は0＜エ＜1の間に1根しかもたない。

∴ρ。＜1の時ル）は。＜。＜11、根をもたない． ている確靱を・次に平均系人数Lと平均列待ち時間

       3．1 P〃，Po， Pldleの計算

には分子が（エー1）でわりきれる必要がある。ところが，

       几＋G1（1）＋G2（1）＝1        （i）

分子についてx→1の時

       G2（1）＝（〃／ρ）P々一、Pb      （ii）

 分子＝一λG2（1）＋々μ4P々一λP6

   ＝一務R＋λ島＋〃峨一λ几＝・    蓼円鋼＝悟一λ識妥鵠1芦≠〃＋1几

で蕊写ご慮る゜    ＝！興｛一λ織誓鑛鵠当

（イ）と全く同様にG・（∬）か計算できて

@  ∴Gl（1）＝当圭濡〒｝IR  （iii）

G・（・）十・−1＋i｛i識・一・（1−・）＋…  （iL（iiL（iii）より

＋，（，＋1）（，＋ ≡叉ρ＿）パ1一が（3）式よ∴ρ（ρ＋｝＝ （イ）

   ＋ρ（    々！（1一工）々−1ρ十1）（ρ十2）・・・… （ρ十〃−1）｝古  R＝，（，＋1）（鵠圭殺留1）（，＋ ）（・）

   ＋｛・ ＋ρ薯1・ 一 （1−・）＋……   み一Gメ1）＋ん（ρ＋詳1一ρ〃）一膓四

＋（，＋1）（，＋2巴．．（ρ＋ −1）・（1−・） 一  3・2平均系熾平均タ‖人数と平均列待ち時間、

      平均系人数，平均列人数と平均列待ち時間をそれぞれ

＋（ρ＋1）（鵠説＋ ）b  L・L・と卿とする・ここで仇は ・」待ち時間の確率

       である。

＋｛・栴1＋砦・M（1−・）……   （イ）Lの計算

1：：1灘罪∴；： 璽鷺鷺i鎌曇，

＋ピ＋（      （1一ρM舞1）・〃−2（1−・）＋……    一）〔（ 三㍑許（ −1）｝＋

＋（，＋1）（ρ監！1！（ρ＋々−2）・（1ザ  2（1‡P（ρ＋々）〕＋雫｛1）｛〃（・＋1）一（〃−1）｝几

＋（   （々−1）！（1一エ）々−1

ﾏ十1）（ρ十2）・…・・（ρ十々−1）｝几一几ここ禦＝4鵠1は1処灘＝バッ

この式とG2（カの定義より       チ到着行列の平均に等しい。

（ロ）LθとE（じrg）の計算

Lg＝ルfλE（呪）である。       3

    の       の      ロ       

L・＝

＝逍､・・＝星（∫＋〃）巳・仁星〃B・・       き      ＿

    oo       oo

   ＝雇∫巳一 恩巳       Pidl・

   ＝α（1）一〃G1（1）

   一α（1）一｛4㍑貢鵠）｝凪     1．・

∴醜）一α（1）一｛

国ﾋ鷲｝凪  ・8

      0．6  4．数値計算例

      0．4  パラメータが多いので）計算結果は主として処理装置

16台に限定して図示した。これからわかるように，平均     o．2 待ち人数や平均待ち時間はρμが0．6〜0．7の値以上を

とると急に大きくなってゆく、とがわかる 又処理装置 の処理速度と繰り返しパラメータ4が同等の効果をもっ

蓬  〃−16台

斥     ルf＝16人 120

100

＼．      ．

80

̲

    ロ

    ＼     L・

・・ ぺ＼   ・

       ＼

40     ＼

20

．，。一・一

Fププ

・1●〆●1

ピ 壷

10

5

・一

ていることに臆しておく必要がある・バッチ到着サイ  図一4（ρ・一警・☆・・謝

ズが大きくなった時，これに応じた端末台数を増加させ ると相応の効果があるが，平均待ち間に対して，これを

短縮させるきわだった働きはしない。

、      平均列待ち人数       ＿ L，      （〃＝16台）       〃＝16台      §

140       °     Pidl・140 〃−32人

       伸

120       ▲

100      8       1．0

80       ミξ゜      0．8

60       0．6

40       °       0．4

20       ／      0．2     xZ

メ＼

0．2 0．4 0．6 0．8 1．0ρM       O．2 0・4 0・6 0・8ρM

      図一3      図一5

   念

   →      一

   き 〃−16  ・垂        ：蕊㌶：；；

   式        」∬＝48       「宜       × 〃＝32， ノ∬＝64

Pidle 柿

      式      （     一

   陣。      世二    §  怜        L・

   120       12      蒲12012置        一一…W

1・0       10       斥100

0．8

0．6

0．4

0．2

・・

・・

、。 ^プグ＼＼

ン  ．／°        メ

8       80

6       60

4       40

2       20

0．2   0．4   0，6   0．8  ρM       O．2   0．4   0．6   0，8   1．0  ρM

図一6（…÷・☆−3・☆）     図一7（脳2㍍） 5．おわりに       参考文献

      2）深川，中山，矢鳴，吉田：九州Il菜大学研究報告（工学端）， NQ 帰還確率と処理時間との関係が明確になった。教育セン    32（昭和51年）． ターのように多人数を対象としたキャラクターディスプ   3）本聞：待ち行列の理品理1：学社． レイを用いた計算機システムにおいて，考慮しなければ    4）！剛H：待ち行列の理論と応胤朝倉書店

ならない点はr二つかめた・特に学生が端末装置を使    Polsson Queue， ORSA（1960）． 用する時に，操作が簡単であること又端末を専有したま   6）LTakacs：ASin91e−Server Queue wlth Feedback， BSTJ まプログラムのバグをみつけることをさせない等の対策    （1963）

泌要であろう．なお，実際のシステムで1ま，学生が到 711ぷ；uzuk1：BatcC㎞val《gP「°blem」°RS°fJapan

着する様子はランダムでなく，アーラン到着過程用いた   8）LAdlri：Cycllc Queues wlth Bulk Arrlvals， J．A．C M（1973）．

ほうがより現実にあてはまるので今後は到着過程をよ   9）D・P・Gaver：The In封uence of Sewicing Times ln Queulng