Bug #11822: Semantics of Queue#pop after close are wrong

• Status: Closed
• Assignee: ko1 (Koichi Sasada)
• Target version: -
• Backport: 2.0.0: UNKNOWN, 2.1: UNKNOWN, 2.2: UNKNOWN

[headius (Charles Nutter)]

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.

[headius (Charles Nutter)]

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:

class Queue
  def close
    @closed = true
    notify_waiting_threads
  end

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

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:

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

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.

[headius (Charles Nutter)]

FWIW, JRuby has always supported a Queue#shutdown! method that only set a shutdown bit because of the problems of setting a bit and safely waking all consumers.

[headius (Charles Nutter)]

Also worth noting that java.util.concurrent's BlockingQueue implementations do not support any of the following for the same reasons as above:

• Closing or shutting down a queue
• Notifying all threads waiting on a queue that it is no longer available

The justification is that shutdown semantics for threads waiting on a queue varies too greatly to have a single consistent semantic. Some code will want a "closed" queue to cause all waiters to raise an error, others may want them to all receive a null value, still others will want them to receive a poison pill indicating the queue is done. Basically, the expectation is that if user code sets up threads to wait on a queue, user code should also handle notifying them that the queue is no longer available for use.

I agree.

[ko1 (Koichi Sasada)]

• Description updated (diff)

[funny_falcon (Yura Sokolov)]

Charles, closing queue only prevents adding new elements to. It should not delete already added items.

Look at Golang's channels, they behaves same way. It is really most useful behaviour.

Deleting already added items would be very unfriendly behaviour.

Perhaps, you complain about documentation? It should be clearer about actual way.

[ko1 (Koichi Sasada)]

• Assignee set to ko1 (Koichi Sasada)

Semantics

I'm not sure all I can understand, but Queue#close does not remove remaining items as Yura said.

(on 2.3) Queue#close is only for simple way for the following code:

# without Queue#close

q = Queue.new
3.times{
  Thread.new{ # workers
    while e = q.pop
      work_with(e)
    end
  }
}

q.push work1
q.push work2
q.push work3
q.push work4
3.times{
  q.push nil
}

# with Queue#close

q = Queue.new
3.times{
  Thread.new{ # workers
    while e = q.pop
      work_with(e)
    end
  }
}

q.push work1
q.push work2
q.push work3
q.push work4
q.close # simplified

Suggestions about documentation are welcome.

Atomicity

I think it is possible to implement in atomic with appropriate locks. For example, we can make this implementation on pthread libraries.
However, such locks can be affect performance, especially on well-optimized lock-free queue implementations such as Java has.

I can't decide the problem is critical or not.
We have no time for Ruby 2.3 to prove it.

So I can remove Queue#close and continue discussion for ruby 2.4 if someone (Charles) says it should be removed.

Charles, what do you think?

[pitr.ch (Petr Chalupa)]

Could you clarify for me following cases: What does pop do when called on empty closed queue? What does close do about already blocked threads when it's empty?
The documentation does not specifies this.

[ko1 (Koichi Sasada)]

Petr Chalupa wrote:

Could you clarify for me following cases: What does pop do when called on empty closed queue? What does close do about already blocked threads when it's empty?
The documentation does not specifies this.

What does pop do when called on empty closed queue?

returns nil.

What does close do about already blocked threads when it's empty?

I assume 'already blocked threads' are consumer threads.
They are resumed, and get nil.

You can verify with code.

q = Queue.new
q.close
p q.pop

q = Queue.new
Thread.new{
  sleep 1
  q.close
}
p q.pop

[pitr.ch (Petr Chalupa)]

Thank you for explanation. So nil can mean a normal nil pushed to the queue or closed queue, that might be error prone. As Charles mentioned there are many possible behaviors users might want when queue is closed. I would suggest to make this configurable on queue initialization.

Queue.new on_close: nil # pops nil
Queue.new on_close: :poison_pill # pops symbol :poison_pill
CLOSED = Object.new
Queue.new on_close: CLOSED # pops CLOSED
Queue.new on_close: ClosedQueueError # raises exception of supplied class

Raising exception seems unnecessary to me, since close is normal feature of the queue not an exceptional state (this is subjective though so including in the example too).

[headius (Charles Nutter)]

tldr: Atomicity can be achieved with full locking, but it prevents Queue from being lock-free in the future. #pop should have a way to indicate the queue is closed other than just returning nil. I don't see anything that prevents the current impl of #close from going into 2.3.

Atomicity

It is possible to implement these operations with a hard lock, but my concern is that it prevents us from using more efficient lock-free Queue implementations in the future.

I have reimplemented JRuby's Queue to mimic a GVL by locking around all operations, and it is passing tests. Performance seems fine, but there were other changes that muddle measurement a bit.

Queue#pop behavior on a closed queue

I do have concerns about #pop returning nil on a closed queue, but it is not an implementation challenge...just an API challenge. The concern is this: there's no indication from #pop that the queue is closed, since nil is a valid value to push into a queue. Or put another way: it will no longer be safe to have nil be a regular value in a queue, since it could now mean the queue is closed. You will have to check #closed? every time.

Perhaps there should be a way to query if the queue is closed and pop at the same time? Go provides a multiple assignment form of receive:

x, ok = <-ch

where "ok" receives a boolean indicating that the queue is closed.

We don't want to make pop always return multiple values, so here's a couple ideas for how we might do this in Ruby:

(Queue#pop already takes a boolean value to indicate if it should be nonblocking, so overloading Queue#pop is not an option)

q.pop!([nonblock]) # raises exception on a closed queue
q.pop?(value [, nonblock]) # returns value if queue is closed (or would block?), rather than nil

[pitr.ch (Petr Chalupa)]

I like this better to make it configurable per pop operation.

[headius (Charles Nutter)]

Summarizing some discussion with Koichi on #ruby-core:

• Current JRuby Queue uses Java's LinkedBlockingQueue and ArrayBlockingQueue, which both are locking implementations. There are lock-free queue implementations on JVM but they do not support blocking.
• Performance of the fully-locked impl of Queue from MRI 2.3 appears to be as good or better than JRuby's existing impls based on Java LBQ and ABQ for single and multi-threaded benchmarks. This is likely because the existing impls were also fully locked and JRuby had to implement num_waiters separately.
• The API proposed for #close, #push, and #pop for 2.3 is accepted by JRuby since there appears to be no performance implication right now.

So we should bump this to to Ruby 2.4 to address the inability to check for closed? and pop at the same time, as in Go. I believe that is the only remaining issue.

This can go forward in 2.3.

For reference, here's what OpenJDK lock-free queues are based upon: http://www.cs.rochester.edu/u/scott/papers/1996_PODC_queues.pdf

We may want to add a lock-free queue implementation to either Ruby or concurrent-ruby in the future.

[headius (Charles Nutter)]

Clarifying my statements above:

"So we should bump this to to Ruby 2.4 to address the inability to check for closed? and pop at the same time, as in Go."

I mean we should discuss further API improvements like Queue#pop! or pop? for Ruby 2.4.

"This can go forward in 2.3."

I mean current #close, #closed?, #push, and #pop changes can go forward as they are implemented on trunk today.

[funny_falcon (Yura Sokolov)]

I like optional arg to pop:
Either pop? or pop(on_close: value)

[avit (Andrew Vit)]

On 2015-12-20 12:54 AM, [e-mail] wrote:

I like optional arg to pop:
Either pop? or pop(on_close: value)

Another possibility is a default proc similar to how Hash#fetch
interface works.

[ko1 (Koichi Sasada)]

• Status changed from Open to Closed

Now close this issue and please file another ticket if someone need to change it.