居眠り床屋問題解いたけれども

multiprocessing モジュールのマニュアル読みつつ、「居眠り床屋問題」をとりあえず解いた。けれども id:sumim さんからおそわった Axon.STM とかをつかってないので、もうしばらくこの問題とは付き合うことになりそう。要勉強。

# coding: utf-8

u"""居眠り床屋問題

http://ja.doukaku.org/285/
"""

from multiprocessing import \
        Process, Queue, Lock, Event, Array, current_process
from Queue import Empty
import time
import random

def barber(seats, output_data, barber_waking):
    pid = current_process().pid

    while True:
        try:
            seat_num, customer = seats.check()
        except SeatsEmpty:
            seat_num, customer = None, None
        if customer is not None:
            output_data.put(u"[barber %d] 散発開始 %d" % (pid, customer))
            time.sleep(random.randint(100, 400) / 1000.0)
            output_data.put(u"[barber %d] 散発終了 %d" % (pid, customer))
            seats.stand(seat_num)
        else:
            # 客がいないので寝る
            barber_waking.clear()
            output_data.put(u"[barber %d] 床屋、眠る" % pid)
            barber_waking.wait() # 寝た
            # 起こされた
            output_data.put(u"[barber %d] 床屋、目覚める" % pid)

def shop(seats, output_data, barber_waking):
    pid = current_process().pid

    for customer in  xrange(0, 16):
        try:
            output_data.put(u"[shop %d] 来店 %d" % (pid, customer))
            seats.sit(customer)
        except SeatsFull:
            output_data.put(u"[shop %d] 満席で立ち去る %d" % (
                pid, customer))
        else:
            if not barber_waking.is_set():
                output_data.put(u"[shop %d] 床屋を起こす %d" % (
                    pid, customer))
            barber_waking.set()
        if customer != 7:
            time.sleep(random.randint(0, 200) / 1000.0)
        else:
            time.sleep(random.randint(1200, 1400) / 1000.0)

class SeatsEmpty(Exception):
    pass

class SeatsFull(Exception):
    pass

class Seats(object):
    def __init__(self, num):
        # seats には客の id  (>= 0) が入る。負の値は空席を意味する
        self.seats = Array('b', num, lock=False)
        self.lock = Lock()
        with self.lock:
            for i in xrange(num):
                self.seats[i] = -1

    def check(self):
        u"""客がいるかどうか見る
        
        客がいなければ SeatsEmpty 例外を送出する。"""
        with self.lock:
            for seat_num, customer in enumerate(self.seats):
                if customer >= 0:
                    return seat_num, customer
            else:
                raise SeatsEmpty()

    def sit(self, customer):
        u"""客を空席に座らせる
        
        空席がない場合 SeatsFull 例外を送出する。"""
        with self.lock:
            for seat_num, seat in enumerate(self.seats):
                if seat < 0:
                    self.seats[seat_num] = customer
                    break
            else:
                raise SeatsFull()

    def stand(self, seat_num):
        u"""seat_num 番目の席に座っている客に席を立たせる"""
        with self.lock:
            assert self.seats[seat_num] >= 0
            self.seats[seat_num] = -1

def main():
    seats = Seats(3) # 席
    output_data = Queue() # 出力バッファ
    barber_waking = Event() # 床屋が起きているか
    barber_waking.set()

    process_shop = Process(
            target=shop,
            args=(seats, output_data, barber_waking))
    process_barber = Process(
            target=barber,
            args=(seats, output_data, barber_waking))

    process_barber.start()
    process_shop.start()

    while (process_shop.is_alive() or
           barber_waking.is_set() or
           not output_data.empty()):
        try:
            print output_data.get(timeout=1)
        except Empty:
            pass

    process_barber.terminate()
    process_barber.join()

if __name__ == '__main__':
    main()