psim言語講座（第2回）離散イベントシミュレーション（待ち行列 M/M/1モデル）を読んでみる

本記事は当社が発行しているシミュレーションメールマガジンVol.2の記事です。
シミュレーションメールマガジンの詳細・購読申込はこちら のサポートページから

M/M/1 モデル

前回、M/M/1モデルを psim で構築し、実行してみました。（プログラムはこちらからダウンロード）

M/M/1モデルとは、同時に1つのみ行えるサービスに対し、ランダムに利用者が到着し、ランダムな時間サービスを利用するようなモデルの事でした。

今回は、そのコードの中身を詳しく読んで行こうと思います。

psim とは

psim言語とは S-Quattro Simulation System に搭載される、離散イベントシミュレーションを記述するための言語です。Python言語上のライブラリとして提供されます。

離散イベントシミュレーションとは、イベントを起因として状態が変化するようなシステムのシミュレーションの事です。

M/M/1モデルにおけるイベントとは、「お客様が到着する」や、「サービスの利用が終了する」などが該当します。これらのイベントが発生したタイミングのみ、システムの状態が変化するので、イベントが発生するタイミングだけシミュレートするのが効率が良いという事に気付くかと思います。

ですが、そのようなシミュレーターを1から書くのはそれほど容易ではありません。一方で、psim は、イベントが複雑に組み合わさるようなモデルを、如何に分かりやすく記述できるかという点を主眼に設計されおり、psim を使えば、かなり直感的なプログラミングができるようになってい ます。

では、具体的に psim を使った M/M/1 のコードを見て行きたいと思います。

資源の定義

離散イベントシミュレーションの基本は有限の資源を利用する時に発生する待ち行列です。その「資源」のひとつとして、psim には、Facility という概念があります。M/M/1モデルにおいては「サービス」を示します。 例えば、銀行の「窓口」などがそれに該当します。

M/M/1モデルのコードの中では、以下のように資源を作成しています。

    # 窓口を示すファシリティ資源
    f = Facility(1, monitor = True)

「1」は、容量が1である事を示しています。monitorオプションが指定されていますが、これは Facility の利用ログを記録しておくように指示しているだけです。

Facility を利用する際に発生する待ち行列が本シミュレーションの基本になります。

到着プロセス

psim では、一連の処理の流れをプロセスとして定義する事で、離散イベントシミュレーションを定義していきます。

M/M/1モデルではランダムにお客様が到着します。このプロセスを到着プロセスと名付けます。

到着プロセスは、ランダムな時間間隔でお客様が到着し、窓口に並ぶ事を繰り返します。これを文字通りに、psim の言葉を使って表現すると以下のようになります。

    # 到着プロセス
    def arrive():
        while True:
            # 次の到着まで待つ
            yield pause(next(g1))
            # サービスプロセスを開始する
            # - この処理自体は非同期なので、一瞬で完了する
            yield subactivate(service)()

def を使って到着プロセスを定義しています。これは python の関数定義構文そのものです。

while True による永久ループも python の構文そのものです。

yield pause(...) は、psim の組込みAPIです。ここは少々特殊なのですが、そのまま構文として捉えて頂いて構いません。単純に指定時間待つという事を表現しています。この例では、「到着間隔を生成する乱数発生器」から得られる時間だけ待ちます。

psim には様々な API がありますが、「何かが成立するまで待つ」ような処理は待ち受け式と呼ばれ、「yield 〰」という形式を用いて表現します。

yield subactivate(...)() は、psim の組込みAPIです。指定された別のプロセスを(非同期に)起動させるものです。ここで指定している service は、後述のサービスプロセスです。

以上のコードで、「ランダムな時間間隔でお客様が到着し、窓口に並ぶ事を繰り返す」ような到着プロセスを表現できました。

サービスプロセス

サービスプロセスは、窓口を実際に利用するプロセスです。お客様が到着する度に、起動されます。最初に定義した窓口Facilityを占有し、ランダムな時間利用します。

ここで大事なのは、窓口は高々1つしかないので、複数人到着した場合は、待ち行列が構成される点です。

具体的に、サービスプロセスを psim の言葉を使って表現すると以下のようになります。

    # サービスプロセス
    def service():
        t0 = now()
        # 窓口の待ち行列に並ぶ
        # - 窓口を示すファシリティ資源の利用を予約する
        # - 既に利用者がいる場合は、利用可能になるまで待ち受ける
        lock = (yield f.request(name = "lock"))["lock"]
        # 窓口サービスを開始する
        # - 窓口を示すファシリティ資源の利用権を取得した
        # - 利用権を開放するまで他の利用者は利用できない
        t1 = now()
        # 待ち時間を記録
        monitor.observe(t1 - t0)
        # 窓口を利用する
        yield pause(next(g2))
        # 窓口を示すファシリティ資源の利用権を開放する
        lock.release()

少々複雑なのですが、

        lock = (yield f.request(name = "lock"))["lock"]

の部分は、そのまま psim の 組込みAPIだと捉えて下さい。窓口を占有し、その証しとしてロックオブジェクトを取得しています。serviceプロセスはお客様が到着する度に起動するため、場合によっては、窓口が既に占有されている場合があります。その場合、窓口が利用可能になるまで、この式は成立しません。つまり待ち行列が発生します。

monitor.observe(...) は、あとで待ち時間を集計できるように結果を記録しています。t0 が並んだ時間、t1 が窓口を占有できた時間なので、t1 - t0 は待ち時間になります。

yield pause(...) は、ランダムな時間窓口を利用する事を表現しています。

lock.release() は、窓口の占有を開放しています。もし、他のお客様が、窓口に並んでいた場合、このタイミングで、先頭に並んでいるお客様に占有権が移ります。

コード上にコメントがあると、逆に本質が見えにくくなっているかもしれません。本質的な所のみを抽出すると以下になります。

    def service():
        lock = (yield f.request(name = "lock"))["lock"]
        yield pause(next(g2))
        lock.release()

　これだけで、「窓口に並び、ランダムな時間利用し、窓口を開放する」というサービスプロセスを表現できました。

まとめ

以上で、M/M/1モデルが出来上がりました。

psim を使って離散イベントシミュレーションを書くのは、非常に簡単である事がお分かりになったでしょうか。

psim言語の構文を組み合わせる事で、もっと複雑な離散イベントシミュレーションも容易に書けそうな事が見えてきたのではないでしょうか。