助言を求む（expmlさんの質問）

待ち行列ネットワークへの助走

私のブログにexpmlさんという方がコメントで質問されました。

しかし、私はexpmlさんの質問に答えることが出来ませんでした。最後にexpmlさんは

私が　このページを見つけたように、また誰か他の方に見つけられて、何か情報が得られるかもしれません。どうぞ　末永く、このページを残されますよう、お願いします。

と書いておられます。この一連のコメントを残すのはやぶさかではありませんが、コメントでは他の人にとって読みづらいので、ここで形を整えていたほうがよいと思い、このエントリーをアップすることにしました。
（09/9/23追記）「Webアプリケーション・サーバの応答時間近似式を求む（by expmlさん）」も参照して下さい。



expmlexpml 2009/09/14 00:26

なかなか大量の参考文献を閲覧できるようで、うらやましいです。
ところで、もし、私の抱えている問題領域の資料もお持ちでしたら、紹介いただけませんでしょうか？

対象領域

  • 処理窓口がm個のWeb　アプリケーション　サーバの負荷量（内部保留リクエスト件数/システム）がL個の毎の、平均応答時間を算定できる近似式。
    • t=F(m,L)


モデル化の難点 1

  • なお、L>mの場合、リトルの公式によって、
    • F(m,L){\approx}F(m,m)\frac{L}{m}
  • という近似がなりたつ場合が多いかとは思いますが、反例もあります。
  • 処理窓口の内の１個に応答時間が無限大（つまり、ソフトウェア不良によって、処理窓口が閉塞した場合）でも、残りの(m-1)個の処理窓口でシステム動作は継続可能で、F(m,L)の値が無限大にならないような近似式が導出できると良いです。


モデル化の難点 2


小生の経験則

  • ＯＳのタスクスケジューラのように、非常に多段の待ち行列ネットワークから構成されている場合、「Lに対してtが1次遅延系である」という仮定で、近似式を導くことができます。⊿ｔ∝⊿Ｌという、「少し遅れた時刻との応答時間の変動幅（差分）は、その微小時間内の内部保留リクエスト件数の変動幅（差分）に比例する」という微分方程式を解いて、
    • t=F(m,L)=a{\times}\exp\left(\frac{L-1}{b}\right){ただし、L{\le}m}
  • ここで、定数a、bは、Ｗｅｂサーバの実測データから得ることができます。
    • aは、L=1の場合（１人で操作した場合）の応答時間
    • bは、各Lの値に対応する応答時間から、指数関数の係数を逆算した値。

※F(m,L)の、L>mの場合の近似式が求まっていなくて　困っています。


派生して得られる性質

  • もし、とあるときの稼動データから得られた係数bの値に、Ｗｅｂシステムの環境に設定している処理窓口数（m）の値が差異があるならば、b=mとなるように環境設定を変更することで、効果的なＷｅｂシステムチューニングができる。


F(m，Ｌ）の分布に関する経験データ

  • システムの応答時間は、ポアソン分布かアーラン分布とされる場合が多いようですが、上述の\{F(m,L)\}の値は、\{L\}の集合がポアソン分布的な偏りがあって、さらにLに対する指数関数となっているF(m,L)は、対数をとった\{F(m,L)\}の分布を見ても、正規分布よりかなり歪んだ分布となった経験データが多かったのです。

id:CUSCUS 2009/09/14 21:41

コメントありがとうございます。

＞なかなか大量の参考文献を閲覧できるようで、うらやましいです。


実 は私はそんな環境にはありません。参考にしているのは「Factory Physics」という本を別にすれば、すべてウェブから無料で得ることの出来るものだけです。それに私は待ち行列理論の専門家でもありません。半導体工場の自動化の一部を仕事にしておりまして、その関係で工場内の物流について興味があり、このような勉強をしているところです。もっとも最近はコンピュータ の性能評価に待ち行列ネットワークを用いることを説明した文献を翻訳していますが、これも、そこから工場運用に応用出来るものがないか、という興味からです。

そんなわけで、expmlさんのお抱えの問題領域の資料と言っても正直、思いつかない状況です。また、ご質問の内容が理解出来ていない部分も数箇所あります。たとえば「1次遅延系」という言葉も分かっておりません。
そんな私ですが、あるいは何かご助言出来るかもしれません。２，３日考えていてもよろしいですか？


id:CUSCUS 2009/09/15 20:10

だいたい、ご質問の内容を理解したように思います。しかし、残念ながら私の手に負える問題ではなさそうです。おそらくマルチタスク環境で、複数のタスクがＣＰＵを共有する状況だと思うのですが、マルチタスクがどう実現されているのか、ということ自体、私の知識にありません。それでどんなモデルを想定すれば よいのかも分かりません。また、それがタイムシェアリングのモデルであった場合は私はその知識を持っていません。これは私の興味がもっぱら工場での生産状況にあるためです。
ということで、すみませんがご質問に対して何もご助言出来ない状況です。


expml expml 2009/09/16 22:12

レスポンスありがとう御座います。
私が　このページを見つけたように、また誰か他の方に見つけられて、何か情報が得られるかもしれません。どうぞ　末永く、このページを残されますよう、お願いします。


expml expml 2009/09/16 23:03

このページに掲載されている数学的な解析手法は、Webシステムの応答時間短縮に関する解析に応用できそうな気配があります。

★極めて段数の多い待ち行列システムの例；

  • WEBシステムは、このページをホストしているシステムであったり、生産工場の受注・生産管理等、広く応用されています。そのシステム内には、単純に数え上げただけでも、数段の待ち行列システムがつながっています。
  • 1段目：Webアプリケーションプロセス
    • tomcat等のWebアプリケーションシステムには、最大同時実行件数（maxThreads）という処理窓口数を指定するパラメタがあり、最大同時実行件数を超えた大量の処理リクエストは、キューイングされて実行されます。
  • 2段目：DBサーバ・プロセス
    • Webアプリケーションプロセスが、大量のデータにアクセスする場合、DBサーバにSQL文等のリクエストを発行しますが、そのDBサーバ内でも、最大処理プロセス数等の処理窓口と、実行待ちキューの構造が、内蔵されています。
  • 3段目：OS内のプロセス処理・CPUスケジューラ
    • 1段目にも2段目にも共通した下部構造として、OSのスケジューラがあります。
    • OSのスケジューラが、数個程度のプロセッサ（CPUコア）を、時分割で各プロセスに割り付けますが、WEBサーバ・プロセスやDBサーバ・プロセスを構成するスレッドの数が、OSが管理するプロセッサ数（処理窓口）を超えていた場合、ここでもキューイングされます。しかも、このOS内のプロセス・スケジューラは、入り口と出口が繋がって、ループしたネットワーク構造の待ち行列システムになっています。
  • 3段目その２：OS内のプロセス処理・CPUスケジューラ
    • ＯＳのスケジューラとしては、ＣＰＵだけではなくて、ディスクデバイスやＬＡＮ通信デバイスに関しても,CPUスケジューラに類似した、待ち行列構造があります。


★1次遅延系；

  • 下記のように、自己相関があるシステムの１種です。
    • Ｗｅｂサーバ・プロセス内の”処理窓口”の稼働率が増えると、ＯＳスケジューラ・レベルでの”実行待ちキューイング件数”が増え、応答時間が長くなり、さらに、その次の時刻でのキューイング件数が更に増えます。
    • Ｗｅｂシステム内で、ある時まで”処理窓口”で処理されていた処理が、”一斉に同時期”に応答した場合、レスポンスがブラウザに帰り、さらに　その後続画面操作によって、再びＷｅｂシステムに”一斉に同時期”にリクエストが到着します。この繰り返しが、延々と続く場合、「Ｗｅｂシステムへのリクエスト到着間隔」は、｛「Ｗｅｂシステム内の”処理窓口”での処理時間」、「Ｗｅｂサーバとブラウザ間の通信時間を加えた時間」、「ブラウザの操作時間」｝の合計に比例します。つまり、「待ち行列システム内の”処理窓口”での処理時間」と「リクエスト　到着間隔」とが比例、あるいは、強い正の相関関係がある、という状況になります。
    • これは、よく知られた待ち行列システムのモデルでの｛「処理時間は指数分布」「到着間隔はポアソン分布」｝という条件が成り立たず、｛「処理時間は指数分布より偏った分布」「到着間隔は”処理時間”と相関が強い、指数分布より偏った分布」｝となります。
    • これらが、Webシステムでの”１次遅延系”の特徴の表れです。　


未解決の問題＝Ｗｅｂシステムの応答時間の近似式

  • 応答時間:t=F(m,L)の近似式を知りたい。　ここで、各記号の意味は以下。
    • Ｗｅｂシステムの系内滞留件数（＝処理中＋処理待ちリクエスト件数）:L
    • Ｗｅｂシステムの処理窓口数：m
    • t=F(m,L)=a{\times}\exp\left(\frac{L-1}{b}\right) {ただし、L{\le}mの場合。
    • t=F(m,L)=a{\times}\exp\left(\frac{m-1}{b}\right)+G(m,L) {ただし、L>mの場合。
  • ここで、G(m,L)は、F(m,L)の値の統計的分散が大きくて、無視できない頻度で平均値より圧倒的に長い処理時間となる場合、待ち行列理論ではポピュラーなリトルの公式から導出される予想結果より、可也少ない値となるような実データを何度か経験しています。つまり「G(m,L){\ll}(F(m,m)の平均値）{\time}\frac{L}{m}」となりうるような近似精度の高い数式が欲しいのです。
  • あるいは、下記のような状態遷移時間を算定できる数式が欲しいのです。
    • G(m,L)≡（m個の処理窓口の系で、内部保留件数がL個からm個まで減るまでの時間）≡（(L-m)個の処理待ち件数が無くなるまでの時間）

では、また　何時か、誰かから、続きのコメントが来る事を期待しています。