待ち行列のコンピュータへの応用
【まちぎょうれつのこんぴゅーたへのおうよう (applications of queueing theory to computer systems)】
概要
複雑で大規模なコンピュータシステムでは, 性質の異なる様々な処理要求が非同期に発生するため, システムの内部は資源競合が発生し混雑している. この混雑現象のモデル化と解析を行うことによりコンピュータシステムの性能を評価し, 過不足のない最適なシステム設計, 性能トラブルを起こさないシステム開発など的確に推進するために, 待ち行列理論や待ち行列ネットワークモデルが活用されている.
詳説
セントラルサーバモデル 大規模なコンピュータシステムでは, 多数の利用者から性質の異なる様々な処理が非同期に要求されるため, その内部では CPU を始めとする種々のシステム資源の競合が発生する. すなわち, コンピュータの内部は混雑しているのである. この混雑現象を解析し, その結果をシステムの設計開発の利用するため, 待ち行列理論, とりわけ待ち行列ネットワークモデルがよく利用される. 閉鎖型ジャクソンネットワークを利用したセントラルサーバモデルとその計算アルゴリズム [7]が最も簡単な待ち行列ネットワークモデルとして知られている. 待ち行列のコンピュータへの応用
BCMPネットワーク BCMPネットワークは, 複数の異なる網内移動経路 (経路選択確率行列) をもつ客が混在することが許されるため, それぞれの網内移動経路を性格の異なるサブシステムに対応付けることにより, 複雑で大規模なコンピュータシステムの性能評価モデルを柔軟に構成することができる. 待ち行列ネットワークを実用化するに際しては, 正規化定数の効率的な計算方法の開発, 積形式解をもたないようなモデルに関する近似解法の開発, 利用者に分かりやすく使いやすいインターフェィスをもつソフトウエアパッケージの開発等が欠かせないが, 1975年は BCMP ネットワークに関する積形式解 [1] が発表されるとともに, その正規化定数の計算法の提案 [9], ならびにそのアルゴリズムを実装したソフトウエアパッケージの開発が行われた. それを契機に, BCMP ネットワークに関する研究と応用は大きな進展をみせた. とりわけ, 開放型ネットワークと閉鎖型ネットワークが混在する混合型待ち行列ネットワークは現在広く実用に供されている.
待ち行列ネットワークの計算法 積形式解をもつ待ち行列ネットワークを利用する際には, ネットワーク状態分布の正規化定数といわれる定数を計算することが必要になる. この正規化定数は, 確率条件から定められるものであるが, ネットワークを構成するノード数, 網内移動経路数 (部分連鎖数) , 閉鎖型連鎖にしたがう客数等が大きくなるにしたがい, その計算量は組み合わせ的な速さで増大する. そのため, 待ち行列ネットワークに関する効率的な計算法の開発は実用化のためには欠かせない. この計算法は, 大きく分けると, たたみ込み法の系統に属するものと, MVA (Mean Value Analysis) 法 [10]の系統に属するものに分けることができる. たたみ込み法では, 正規化定数をたたみ込み演算を利用して直接求める. MVA 法では, ネットワークの積形式解から連鎖と客数をパラメータとする漸化式をつくり, これを手がかりにして計算を行う. たたみ込み法では, 指数部のあふれ, MVA 法では仮数部の桁落ち, という数値計算上の不安定要因をもっているため, それを避ける計算法についての研究も多数なされている. 実際に待ち行列ネットワークを利用する際には, これらの計算アルゴリズムを実装したソフトウエアパッケージが必要になる. コンピュータシステムへの応用を目的とした開発も QM-X [7] をはじめ多数行われている.
性能測定技術 待ち行列ネットワークを利用してコンピュータシステムの性能評価を行う際には, 評価の基礎となるデータをどのようにして得るのか, という問題が重要となる. 質の良いデータを効率的に測定するための技術も色々と開発されている. また, 待ち行列ネットワークを効果的に利用するための方法論と測定法の提案もなされている. これらについては, 解説 [5, 6] に示される. また, 待ち行列ネットワークとそのコンピュータシステムの性能評価への応用については, [3, 4, 7, 9] に詳しい.
参考文献
[1] F. Baskett, K. M. Chandy, R. R. Muntz and F. G. Palacios, "Open, Closed, and Mixed Networks of Queues with Different Classes of Customers," Journal of Association of Computing Machinery, 22 (1975), 248-260.
[2] J. P. Buzen, "Computatonal Algorithm for Closed Queueing Networks with Exponential Servers," Communication of Association for Computing Machinery, 16 (1973), 527-531.
[3] 亀田壽夫, 紀 一誠, 李 頡, 『性能評価の基礎と応用』, 共立出版, 1998.
[4] K. Kant, Introduction to Computer Performance Evaluation, McGraw-Hill, Inc., 1992.
[5] 紀 一誠, 「情報処理システムの性能評価(1)(2)(3)」, 『オペレーションズ・リサーチ』, 40 (1995), 315-320, 370--375, 431-436.
[6] 紀 一誠, 「コンピュータシステム」, 『オペレーションズ・リサーチ』, 43 (1998), 562-567.
[7] 紀 一誠, 『待ち行列ネットワーク』,朝倉書店 , 2002.
[8] 紀 一誠, 納富研造, 「待ち行列網モデルによる計算機システムの性能評価用ソフトウエアパッケージ QM-X」, 『情報処理学会論文誌』, 25 (1984), 570-578.
[9] S. S. Lavenvarg (Ed. ), Computer Performance Handbook, Academic Press, 1983.
[10] M. Reiser and H. Kobasyashi, "Queueing Networks with Multiple Closed Chains: Theory and Computational Algorithms," IBM Research and Development, 19 (1975), 283-249.
[11] M. Reiser and S. S. Lavenverg, "Mean Value Analysis of Closed Multichain Queueing Networks," Journal of Association for Computing Machinery, 22 (1980), 313-333.