ScalaのActorのお勉強がてら、「居眠り床屋問題」というものに挑戦してみました。
居眠り床屋問題 どう書く？org
若干手抜きでログ出力などが設問通りではありませんけど。
居眠り床屋問題 どう書く？org
並行処理のお題です。ある床屋の亭主は、客がいないときまって居眠りを始めます。床屋店内には三台の散髪兼順番待ち用の椅子があり、客は来店時に椅子に空きがあれば、いずれかに勝手に座って自分の番が来るのを待ち、散髪を終えてから店を出ます。空席が無ければそのまま何もせずに立ち去ります。居眠り中の亭主は、客の入店時に起こされると待ち客すべてをひとりずつ順に散髪しますが、誰もいなくなればまた居眠りを始めます。
この床屋店に16人の客が訪れた日のシミュレーションを行なうコードと、その結果（下に例として示したログ形式。「[スレッドのIDなど] イベント描写」の一覧と終了後の総括）を出力して示してください。なお、散髪には一人当たり100～400ミリ秒の時間（この範囲でランダムに変化）を要し、客は通常 0～200ミリ秒（同）の間隔で訪れます。ただし例外として9番目の客だけは前の客から1200ミリ秒程度の間隔（すなわち、最大三名の待ち客全員を散髪し終えるのに十分な時間）をあけて訪れるものとします。
実装に際し、実行時のデッドロックの回避はもちろんですが、そのほかにも、競合状態（席の空きを確認して座ろうとしたら、もう別の客が座っていた...というような事態）などの不整合も生じないよう配慮し、必要であればそのための対策を講じてください。たとえば来客の間隔が仮に０ミリ秒で固定の場合（つまり、客が一斉に来店した場合）でも、コードが正常に動作するかどうか試してみるのもよいかもしれません。
若干手抜きでログ出力などが設問通りではありませんけど。
Actorを使っての実装
ScalaのActorというものを使ったことがなかったのでいろいろ勉強になりました。慣れてくると、うわさ通り並列処理がとても書きやすいことがわかります。
import _root_.scala.actors._
import _root_.scala.actors.Actor._
case class VISIT(x: Int)
case class CLOSE()
case class RESULT(visited: Int, cut: Int)
class Barber(s: Int) extends Actor {
barber =>
private val rnd = new java.util.Random
private case class CUT(x: Int)
private case class DONE(x: Int)
private case class REPLY()
def act = {
Owner.start
var visited = 0
var cut = 0
var seat = s
loop {
react {
case VISIT(x) => {
println("visit " + x)
visited += 1
if(seat > 0) {
seat -= 1
Owner ! CUT(x)
}
else {
println("return " + x)
}
}
case DONE(x) => {
cut += 1
seat += 1
}
case CLOSE => {
Owner !? CLOSE
println("closed")
forward(REPLY)
}
case REPLY => {
reply(RESULT(visited, cut))
exit
}
}
}
}
private object Owner extends Actor {
def act = {
loop {
reactWithin(0) {
case TIMEOUT => sleep
case CUT(x) => cut(x)
}
}
}
private def sleep = {
println("sleep...")
react {
case CUT(x) => {
println("wake up")
cut(x)
}
case CLOSE => {
reply()
exit
}
}
}
private def cut(x: Int) = {
println("cut " + x)
Thread.sleep(rnd.nextInt(300) + 100)
println("done " + x)
barber ! DONE(x)
}
}
}
object Barber {
def main(args : Array[String]) {
val rnd = new java.util.Random
val barber = new Barber(3)
barber.start
for(i <- 1 to 8) { Thread.sleep(rnd.nextInt(200)); barber ! VISIT(i) }
Thread.sleep(1200)
for(i <- 9 to 16) { Thread.sleep(rnd.nextInt(200)); barber ! VISIT(i) }
val result = (barber !? CLOSE).asInstanceOf[RESULT]
println("result " + "%2d / %2d".format(result.cut, result.visited))
}
}
