From: "NAKAMURA, Hiroshi" <nakahiro@...>
Date: 2010-07-28T20:03:51+09:00
Subject: [ruby-dev:41885] [1.9] Queueのfairness

Queueのfairnessは必要でしょうか。

ここで"fairness"で意図しているのは、Queue#popで複数のスレッドが待ってい
る場合に、一番長く待っているスレッドから順に制御を渡されること、です。

この意味では、1.8のQueueはfairで、例えば以下のスクリプトを走らせると、
常に[:go, :first]と表示されます。

# http://gist.github.com/493930#file_gistfile1.rb
create_waiter = lambda { |name, command|
  t = Thread.new {
    p [command.pop, name]
  }
  Thread.pass until t.status == 'sleep'
  t
}

50.times do
  command = Queue.new
  # create 3 waiters, and...
  create_waiter.call(:first, command)
  create_waiter.call(:second, command)
  create_waiter.call(:third, command)
  # and pushes a command.
  command.push(:go)
  # then try to consume the command by a subsequent thread
  Thread.new {
    p [command.pop, :LATER]
  }
end

これに対し1.9では、Queueがfairではなくなったため、時々[:go, :LATER]など
と表示されます。

正直なところ、RubyではprimitiveのMutex#lockがfairではない（間違っていた
ら指摘をお願いします）ことから、Queueだけがんばってもね、という気はしま
す。しかし1.9のQueueも、結構惜しいところまでfairなので、うまい解決法があ
れば。。。誰か思いつきませんか。

とりあえず1.8のQueueをスレッドスケジューラもどきに使っている人は、もし
ハマったらfairnessを疑ってみるとよいかもしれません。私の典型的な使い方
は、以下でした。

# http://gist.github.com/430066
require 'thread'

q = Queue.new
t1 = Thread.new {
  p [:t1, q.pop]
  q.push(:t1)
}

q.push(:main)
p [:main, q.pop]

ちなみにJRubyもunfair（1.8も）なんですが、1.9とは異なり、「main threadだ
けは割り込みできる」という状態になっています。最初のサンプルは問題なく
動きますが、最後のヤツはダメ。ちなみに実装はfastthread作者の@mentalguy。