食事する哲学者

食事する哲学者の問題」の Chandy / Misra の解をアレンジしてみます。

この問題では 5 人の哲学者が円卓を囲み、 1 本ずつフォークが哲学者の間に置いてあるとします。 円卓上のフォークも 5 本です。 哲学者が食事をするときは 2 本のフォークが必要で、 並列処理でフォークを排他的に哲学者が手に取っていくときに、 デッドロックや飢餓が生じないようにするのがお題の目標です。 本来の Dikstra のお題では、 哲学者同士は会話しなかったはずですが、 食事中の隣の哲学者に「終わったらフォークを使わせてくれ」とお願いをしておくのが、 Chandy / Misra の解だと私は理解しています。 もう一つのこの解の特徴は、 フォークの所有者になる哲学者が常に存在していることです。 食事をしていないときもフォークを誰かが所有し続けます。 Chandy / Misra の解では、 フォークは汚れているときと綺麗なときの 2 つの状態があり、 フォークを隣に譲るときに汚れを落として綺麗にします。 今回は、 ここをアレンジして、 食事中のフォークはその哲学者にとって綺麗なものとして、 譲り受けたときと食事中にフォークを綺麗にするように変更しています。

哲学者は 5 人なので、 哲学者オブジェクトを 5 つ作り、 left メンバと right メンバでつないで双方向リンクのリングを作って円卓に座っていることを表します。 さらに、 フォーク・オブジェクトも 5 つ作り、 哲学者オブジェクトの left_fork メンバと right_hand メンバにつないでおきます。 ある哲学者オブジェクトの左手にあるフォークが left_fork、 右手にあるのが right_fork です。 隣あう哲学者の間にはフォーク・オブジェクトが一つだけあって、 左の哲学者の right_fork と右の哲学者の left_fork は同じフォーク・オブジェクトです。 哲学者の人数と同じだけスレッドを作り、 それぞれのスレッドでは思索にふけり、 pickup で両側のフォークをとり、 eat で食事をして、 putdown でフォークを円卓に置いてと動作を繰り返します。 フォーク・オブジェクトは dirty と clean の 2 つの状態をとり、 初期化時は dirty になります。 これを dirty メンバの真偽値で表し、 dirty メンバが真のとき状態 dirty、 偽のとき状態 clean になるとします。 状態 clean は食事にフォークが使用中であることに相当します。

require 'thread'

def eating_philosophier
  ph = Array.new(5) {|i|
    x = Philosophier.new(i, nil, nil, nil, nil)
    x.left_fork = Fork.new(true, x)
    x
  }
  ph.size.times do |i|
    ph[i].left  = ph[(i + ph.size - 1) % ph.size]
    ph[i].right = ph[(i + 1) % ph.size]
    ph[i].right_fork =ph[i].right.left_fork
  end
  Array.new(5) {|i|
    Thread.new do
      puts "No. #{i} thinks"
      3.times do
        sleep(0.1 * (rand(5) + 1))
        ph[i].pickup
        ph[i].eat
        ph[i].putdown
      end
    end
  }.each {|t| t.join }
end

哲学者クラスは、 MUTEX オブジェクトを一つ持ち、 排他制御に利用します。 哲学者オブジェクトには Queue オブジェクトをメンバに持ち、 フォーク待ちをしている両隣の哲学者オブジェクトへの通知に利用します。

class Philosophier
  MUTEX = Mutex.new
  attr_accessor :id, :left, :right, :left_fork, :right_fork, :queue

  def initialize(i, b, f, bf, ff)
    @id, @left, @right, @left_fork, @right_fork = i, b, f, bf, ff
    @queue = Queue.new
  end

  def pickup
    if MUTEX.synchronize { @left_fork.pickup(self) | @right_fork.pickup(self) }
      @queue.pop                                #  ^ ここを || にしないこと
    end
    self
  end

  def eat
    MUTEX.synchronize { puts "No. #{@id} eats" }
    sleep(0.1)
    MUTEX.synchronize { puts "No. #{@id} thinks" }
    self
  end

  def putdown
    MUTEX.synchronize {
      if @left_fork.putdown && @left.own?
        @left.queue.push(nil)
      end
      if @right_fork.putdown && @right.own?
        @right.queue.push(nil)
      end
    }
    self
  end

  def own?
    @left_fork.owner.equal?(self) && @right_fork.owner.equal?(self)
  end
end

フォーク・オブジェクトを哲学者 ph が手に取る pickup メソッドでは、 フォークが円卓に置いてある状態 dirty であるか、 または、 フォークの所有者が食事をしたがっている哲学者のとき、 空きを待つ必要がなく、 哲学者 ph が即座にそのフォークを使うことができます。 そうでないときは、 隣の哲学者が食事に使っているので、 request メンバにフォーク利用希望中の哲学者 ph を登録して、 フォークの空き通知を待ちます。

食事を終えた直後に哲学者が机に置く putdown メソッドでは、 そのフォークの空きを待っている哲学者がいないとき、 状態 dirty に戻します。 そうでないときは、 状態 clean で空きを待っている哲学者にフォークを譲ります。

class Fork
  attr_accessor :dirty, :owner, :request
  def initialize(a, b)
    @dirty, @owner, @request = a, b, nil
  end

  def pickup(ph)
    if not @dirty and not @owner.equal?(ph)
      @request = ph
      true  # needs to wait
    else
      @dirty = false
      @owner = ph
      @request = nil
      false
    end
  end

  def putdown
    if @request.nil?
      @dirty = true
      false
    else
      @dirty = false
      @owner = @request
      @request = nil
      true  # needs to signal
    end
  end
end