SimPyで離散事象シミュレーション(3) リソースを理解しよう：StoreとResource編

# はじめに

SimPyというPythonの離散事象シミュレーション用のパッケージを見つけて試してみたら気に入ったので自分用の備忘録も兼ねて使い方をまとめていく．

* [SimPyのドキュメント](https://simpy.readthedocs.io/en/latest/)
* [SimPyのソース](https://bitbucket.org/simpy/simpy/src/default/)
* [第1回の記事](https://qiita.com/j54854/items/687f8842be1d3e212384)（はじめの一歩）
* [第2回の記事](https://qiita.com/j54854/items/816d7b974562fc4e93bb)（リソースを理解しよう：Container編）

第3回目の今回は，「resources関連のモジュール群」の中で前回詳しく触れられなかったstore.pyとresource.pyの2つのモジュールをとりあげる．

# Store系のリソース

store.pyモジュールの中にはStore系のリソース（Store，PriorityStore，FilterStoreの3つ）が定義されている．基本となるのがStoreクラスで，これはBaseResourceクラスを継承したサブクラスになっている．残る2つはStoreクラスを継承して少しカスタマイズしたものになっている．ここでは，基本となるStoreクラスを中心にみていこう．

## Storeの概要

前回紹介したContainerクラスは，液体などの連続的なオブジェクト，もしくは均一で互いに区別できない離散的なオブジェクトを蓄える容器のようなリソースであった．そのため，容器の中身を単に数量（`level`）で把握しておけばよかった．

これに対して，Storeクラスは，離散的でかつ個別に区別できるアイテムを保持しておく容器のようなリソースである．したがって，容器の中身をアイテムのリスト（`items`）で把握している．それにあわせて，Putクラスを継承したStorePutクラスには，容器に格納したいアイテム（`item`）の情報が追加されている．

そして，`_do_put()`メソッドでは，Storeの容量に余裕があれば（`items`リストの長さが`capacity`未満であれば），StorePut事象の`item`を`items`リストの末尾に追加してから，`ok=True`で対応するStorePut事象をトリガーしている．

また，`_do_get()`メソッドでは，Store内にアイテムが存在すれば（`items`リストの長さが1以上であれば），`items`リストの先頭の要素を取り出し，それを`value`に代入し，`ok=True`で対応するStoreGet事象をトリガーしている．

これらの実装の結果，Storeクラスは，アイテムの先入れ先出し（FIFO）バッファ，あるいはQueueになっていることがわかる．仮に，これを後入れ先出し（LIFO）バッファ，あるいはStackに変更したいとすると，`_do_get()`メソッドをオーバライドして，リストの取り出し順を末尾からに変更すればいいだろう（ただし，有限の`capacity`を設定してしまうと全体としては必ずしもStackにはならない）．

Storeクラスのインスタンスは，

```python
simpy.resources.store.Store(env, capacity=float('inf'))
simpy.Store(env, capacity=float('inf'))
```

のいずれかで生成できる（2つ目はショートカット）．生成時に特に指定しないと，`capacity`は無限になる．

## Storeの使用例

簡単な例として，makerプロセスが100個のproductを1つずつ生産して順にStoreに格納していき，buyerプロセスはそれらをStoreから1つずつ購入していく，という状況をモデル化してみた．

```python
import random
import simpy

def maker(env):
    for i in range(100):
        time_to = random.expovariate(1)
        yield env.timeout(time_to)
        yield env.store.put('product_' +str(i))  # put string "product_i" into Store

def buyer(env):
    for j in range(100):
        time_to = random.expovariate(1)
        yield env.timeout(time_to)
        item = yield env.store.get()  # get string "product_i" from Store and assign it to item
        print('buyer_{} bought {}.'.format(j, item))

def main():
    env = simpy.Environment()
    env.store = simpy.Store(env)
    env.process(maker(env))
    env.process(buyer(env))
    env.run()

if __name__ == "__main__":
    main()
```
これを動かしてみると，StoreがFIFOになっていることが確認できる．次に，Storeを少しカスタマイズしてみよう．

```python
import random
import simpy

class CustomStore(simpy.Store):
    def __init__(self, env, capacity=float('inf')):
        super(CustomStore, self).__init__(env, capacity)

    def _do_get(self, event):
        if self.items:
            event.succeed(self.items.pop(len(self.items) -1))

def maker(env):
    for i in range(100):
        time_to = random.expovariate(1)
        yield env.timeout(time_to)
        yield env.store.put('product_' +str(i))  # put string "product_i" into Store

def buyer(env):
    for j in range(100):
        time_to = random.expovariate(1)
        yield env.timeout(time_to)
        item = yield env.store.get()  # get string "product_i" from Store and assign it to item
        print('buyer_{} bought {}.'.format(j, item))

def main():
    env = simpy.Environment()
    env.store = CustomStore(env)
    env.process(maker(env))
    env.process(buyer(env))
    env.run()

if __name__ == "__main__":
    main()
```

最初に，Storeクラスを継承したCustomStoreというサブクラスを作成している．これは，`items`リストの末尾から順に要素を取得するように`_do_get()`メソッドをオーバーライドしたものである（FIFOをLIFOに変更）．

`main()`関数では，Storeの代わりにCustomStoreを利用して上とまったく同じ処理を行っている．これを実際に動かしてみると，先ほどとは購買されていく製品の順序が異なることが確認できる．

## PriorityStoreとFilterStore

PriorityStoreは，`items`をリストではなくヒープにすることで，アイテムをなんらかの優先順位の順に取り出せるように，Storeクラスを拡張したものである．したがって，PriorityStoreに格納するアイテムはorderableでないといけない（`__lt__()`メソッドをもつこと）．そのために，PriorityItemクラスが用意されているので，必要に応じて利用しよう．

FilterStoreは，StoreGetクラスをさらに継承してFilterStoreGetクラスを定義し，それをGet事象として利用している．このFilterStoreGetクラスには，`item`をフィルタリングするメソッド（`filter()`）が追加されていて，`_do_get()`で`items`リストから要素を抽出する際に，`filter()`が`True`を返すという条件を加えている．

# Resource系のリソース

resource.pyモジュールの中にはResource系のリソース（Resource，PriorityResource，PreemptiveResourceの3つ）が定義されている．基本となるのがResourceクラスで，これはBaseResourceクラスを継承したサブクラスになっている．PriorityResourceはResourceを，PreemptiveResourceはPriorityResourceをそれぞれ継承して少しカスタマイズしたものになっている．ここでは，基本となるResourceクラスを中心にみていこう．

Resourceは，プロセスが使用する道具，機械などを表していて，同時に利用可能な個数に上限（`capacity`）があるため，取り合いが起こる．これに対するPutとGetの事象としては，Put/Getクラスを継承したサブクラスのRequest/Releaseクラスを用いるようになっている．

Resourceクラスの`put_queue`は`queue`に改名されており，そのリストにRequest事象が追加されていく．リソースの中身は`users`という名称のリスト（Storeクラスの`items`リストに対応）で表され，その中にもRequest事象が格納される．この`users`リストの長さを返す属性`count`も追加されている．

解釈としては，`users`リストに含まれるRequest事象（を送出したプロセス）が現在そのリソースを使用中であり，`queue`リストに含まれるRequest事象（を送出したプロセス）はリソースが入手可能になるのを待機中ということになる．

Releaseクラスは対応するRequest事象への参照をもち，インスタンス（Release事象）が生成されるとすぐにリソースの`_do_get()`メソッドが呼ばれる．そして，`_do_get()`メソッドは，それに対応するRequest事象を`users`リストから削除して，このRelease事象を`ok=True`でトリガーする．

Requestクラスは，`yield`する際に`with`でコンテキスト化しておくと自動的に`release()`を呼ぶ（対応するRelease事象を生成する）仕組みが追加されている（ので，通常はそのスタイルでコーディングすること）．これでリソースの使用中に依頼元のプロセスから取り消しが入った場合などにも自動的に`release()`が走るようになる（前回紹介した`cancel()`と`release()`の違いに注意する）．

Requestクラスの`_do_put()`メソッドは，`users`リストの長さが`capacity`未満であれば，Request事象を`users`リストの末尾に追加し，その事象の（リソース使用開始時刻を表す）属性`usage_since`に`env.now`の値を代入する．

Resourceクラスのインスタンスは，

```python
simpy.resources.resource.Resource(env, capacity=1)
simpy.Resource(env, capacity=1)
```

のいずれかで生成できる（2つ目はショートカット）．生成時に特に指定しないと，`capacity`は1になる．

## Resourceの使用例

ここではよくあるジョブショップスケジューリングの例を挙げておこう．

```python
import random
import simpy

MACHINE = 3  # number of machines
JOB = 5  # number of jobs
OPR_MIN = 2  # minimum number of operations
OPR_MAX = 5  # maximum number of operations

def job(env, j):
    n_o = random.randint(OPR_MIN, OPR_MAX)  # number of operations of job j
    p_r = random.choices(range(MACHINE), k=n_o)  # processing route
    p_t = [random.randint(2,7) for o in range(n_o)]  # processing times
    for o in range(n_o):
        m = env.machines[p_r[o]]  # which machine to use
        with m.request() as req:
            yield req
            s_t = round(env.now)  # start time
            yield env.timeout(p_t[o])
            c_t = round(env.now)  # completion time
            print('o_{}_{} on m_{}: {}-{}'.format(j, o, p_r[o], s_t, c_t))

def main():
    env = simpy.Environment()
    env.machines = [simpy.Resource(env) for m in range(MACHINE)]
    for j in range(JOB):
        env.process(job(env, j))
    env.run()

if __name__ == "__main__":
    main()
```
プロセス`job()`の中で，まずそのジョブのオペレーション数と加工経路，各オペレーションの処理時間をランダムに設定している．そして，加工経路の順に機械をリクエストし，確保できたら専有し，加工時間が経過したらリリースするというサイクルを繰り返している．`

`maim()`関数の中を見ればわかるように，各機械はResourceでモデル化されている．したがって，上記のコードでは，すべての機械がディスパッチングルールとしてFIFOを使用していることになる．なお，下で紹介するPriorityResourceを使えば，これをSPTなどの他のディスパッチングルールに簡単に変更してみることもできる（ので，ぜひ試してみてほしい）．

## PriorityResourceとPreemptiveResource

PriorityResourceは，`queue`を，なんらかのkeyでソート可能なSortedQueueに変更している．また，PriorityRequestというRequestのサブクラスを定義して，それをPut事象として用いている．これらによって，リソースを利用するプロセスの優先順位付け（優先度の高いプロセスから順にリソースが割り当てられていく）を可能にしている点が標準のResourceとの違いである．

PreemptiveResourceは，リソースを割り当てる際の優先順位付けに加えて，さらに現在リソースを使用中のプロセスを中断させて，優先度の高いプロセスが優先度の低いプロセスから使用中のリソースを奪い取る行為（Preempt）を考慮できるようにしている．このとき，PreemptされたPriorityRequest事象は`users`リストから削除され，それに対応するプロセスには`Interrupt`例外が投げ込まれる（ので，プロセス側で必要に応じてこの例外を処理する）．

# まとめ

今回はSimPyの「resources関連のモジュール群」のうち，store.pyとresource.pyの内容についてまとめた．StoreクラスとResourceクラスの標準的な使い方も紹介したので，機会があればぜひ試してみてほしい．次回はシミュレーションの途中経過のアニメーション化についてまとめたいと思う．

* [第4回へのリンク](https://qiita.com/j54854/items/0f842df7a42c5688dc2a)
* [この記事のプログラムのソース（GitHub）](https://github.com/j54854/mySimPy)