 |
 |
 |
 |
 |
 |
 |
 |
 |
|
|
|
|
|
queuing model「待ち行列モデル」の直感的な理解のために
上智大学 伊藤 潔
2006年3月19日
queuing
model 「待ち行列モデル」は，下図のとおり，トランザクションがサーバ（窓口）にやって来て，自分の番になったら，サービスを受けるもので，自分の番になるまでは，queue
「待ち行列」に並びます．
本稿では，分布については述べません．直感的な部分を，用語と共に理解します．
待ち行列のパラメータには，以下のものがあります．
λ
：
arrival rate 「到着率」
１／λ
： inter-arrival
time 「平均到着時間間隔」
μ
：
service rate 「サービス率」
１／μ
： average
service time 「平均サービス時間」
τ
： throughput
「スループット」
１／τ
：
inter-departure time 「平均完了時間間隔」
ρ ： utilization rate 「稼働率」
λ 「到着率」は，単位時間あたりのトランザクションの到着個数です．その逆数 １／λは，平均到着時間間隔になります．例えば，5秒に1個のトランザクションが到着する場合，1/5
= 0.2が到着率λで，5
= 1/0.2 が平均到着時間間隔
１／λになります．
μ
「サービス率」は，サーバが単位時間あたり，トランザクションを何個処理できるかを表します．その逆数
１／μは，平均サービス時間になります．例えば，1個のトランザクションの処理に4秒かかる場合，1/4
= 0.25がサービス率μで，4
= 1/0.25 が平均サービス時間１／μになります．
ここで，稼働率ρを直感的に理解します．上の例で，5秒に1個のトランザクションが到着し，そのトランザクションの処理に4秒かかるのですから，5秒のうち4秒がビジーで，1秒はアイドル（お暇）です．稼働率は，ρ = 4/5 = 0.8になります．
公式的に書くと
① ρ
＝ 平均サービス時間／平均到着時間間隔＝ （1/μ
）/
（1/λ
）
＝ λ/μ
よく出てくる ρ
＝ λ/μ は，上の式の通りです．
稼働率の項で
② 稼働率 ＝ サーバの稼働時間の総和／システム運転時間
と説明しました．システム運転時間にn個到着して，サービスを受けているとすれば，①から
ρ
＝ （1/μ
）/
（1/λ
） ＝ (n*（1/μ
）)/
(n*（1/λ
）)
＝ サーバの稼働時間の総和／システム運転時間
で問題がありません．
以上の稼働率は，（1/μ
）＜（1/λ
），すなわち μ
＞λ
の時だけで成り立っています．トランザクションが来る時間間隔よりサービス時間が短ければ，サーバはトランザクションを待たさずに処理できます． ρ
＝ （1/μ
）/
（1/λ
）です．
一方，（1/μ
）＞（1/λ
），すなわち μ
＜λ
の時は，トランザクションが来る時間間隔よりサービス時間が大きいので，サーバは次に来るトランザクションを待たしてしまいます．このときはサーバは休まず稼働し続けるの，ρ＝１となります．ρは１を超えません．待ち行列のたくさん並びます．
τは，throughput 「スループット」で単位時間あたり何個トランザクションを処理できるかを表します．逆数 １／τ は， inter-departure time 「平均完了時間間隔」 です．
(A)
ρ
＜１，すなわち，（1/μ
）＜（1/λ
），すなわち μ
＞λ
の時，到着時間よりサービス時間が小さいので，平均完了時間間隔は到着時間に等しくなります．よって
τ＝λ となります．
(B)
ρ
＝１，すなわち，（1/μ
）＞（1/λ
），すなわち μ
＜λ
の時，到着時間よりサービス時間が大きいので，平均完了時間間隔はサービス時間に等しくなります．よって
τ＝μ となります．
5秒に1個のトランザクションが到着し，そのトランザクションの処理に4秒かかる場合は，
１／τ = 5になります．また，3秒に1個のトランザクションが到着し，そのトランザクションの処理に4秒かかる場合は，サーバは働きづめで，１／τ = 4になります．