From: headius@...
Date: 2015-12-15T16:58:11+00:00
Subject: [ruby-core:72150] [Ruby trunk - Bug #11822] Semantics of Queue#pop after close are wrong

Issue #11822 has been updated by Charles Nutter.


=begin
Additional thoughts on this...

I'm not sure the semantics of these queues are compatible with actual parallel execution as in JRuby for a few reasons.

NON-ATOMICITY OF STATE

Setting a closed bit *and* waking all waiting consumers cannot be done atomically. This allows the closed bit to be set *after* another thread has checked it but *before* that thread has inserted an item into the queue. This in turn could cause all waiting threads to wake, receive a nil result, and not see the subsequently-pushed value.

Pseudo-code that represents current MRI impl:

=end
class Queue
  def close
    @closed = true
    notify_waiting_threads
  end

  def push(value)
    raise ClosedQueueError if closed?
    @queue << value
  end
end
=begin

An implementation that can run these pieces of code in parallel can not guarantee the atomicity of closing and notifying waiting threads. The result would be that all waiters might return nil but there's still elements in the queue.

NOTIFICATION OF WAITING THREADS ON CLOSE

It is also not possible to atomically notify all threads on close. More pseudo-code in addition to the above:

=end
class Queue
  def pop
    return nil if closed?
    return @queue.pop if @queue.size != 0
    wait_for_push
  end
end
=begin

Since it is not possible in a parallel implementation to set the closed bit *and* notify all threads atomically, it's possible for a thread to get stuck waiting forever if the following order happens:

1. Thread A checks if the queue is closed? in Queue#pop. It is not, so it proceeds.
2. Thread A checks if the queue is empty. It is empty, so it proceeds.
3. Thread B closes the queue and sets the closed bit and notifies waiting threads. At this point, no threads are waiting.
4. Thread A proceeds to wait on the queue.

Under parallel execution, it is not possible to guarantee no threads will be blocking on the queue after Queue#close has been called given the current semantics of Queue.

I will think on both of these for a while, but I'd also appreciate some input if I've missed a possible solution.

----------------------------------------
Bug #11822: Semantics of Queue#pop after close are wrong
https://bugs.ruby-lang.org/issues/11822#change-55561

* Author: Charles Nutter
* Status: Open
* Priority: Normal
* Assignee: 
* ruby -v: 
* Backport: 2.0.0: UNKNOWN, 2.1: UNKNOWN, 2.2: UNKNOWN
----------------------------------------
Current test/ruby/thread/test_queue.rb test_close has the following assertion that seems wrong to me:

  def test_close
    [->{Queue.new}, ->{SizedQueue.new 3}].each do |qcreate|
      q = qcreate.call
      assert_equal false, q.closed?
      q << :something
      assert_equal q, q.close
      assert q.closed?
      assert_raise_with_message(ClosedQueueError, /closed/){q << :nothing}
      assert_equal q.pop, :something  # <<< THIS ONE
      assert_nil q.pop
      assert_nil q.pop
      # non-blocking
      assert_raise_with_message(ThreadError, /queue empty/){q.pop(non_block=true)}
    end
  end

Once a queue is closed, I don't think it should ever return a result anymore. The queue should be cleared and pop should always return nil.

In r52691, ko1 states that "deq'ing on closed queue returns nil, always." This test does not match that behavior.



-- 
https://bugs.ruby-lang.org/