From: headius@headius.com
To: ruby-core@ruby-lang.org
Subject: [ruby-core:72150] [Ruby trunk - Bug #11822] Semantics of Queue#pop after close are wrong
Date: Tue, 15 Dec 2015 16:58:11 +0000 [thread overview]
Message-ID: <redmine.journal-55561.20151215165810.11f4aafccfe723d1@ruby-lang.org> (raw)
In-Reply-To: redmine.issue-11822.20151215160530@ruby-lang.org
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/
next prev parent reply other threads:[~2015-12-15 16:26 UTC|newest]
Thread overview: 17+ messages / expand[flat|nested] mbox.gz Atom feed top
[not found] <redmine.issue-11822.20151215160530@ruby-lang.org>
2015-12-15 16:05 ` [ruby-core:72149] [Ruby trunk - Bug #11822] [Open] Semantics of Queue#pop after close are wrong headius
2015-12-15 16:58 ` headius [this message]
2015-12-15 17:48 ` [ruby-core:72152] [Ruby trunk - Bug #11822] " headius
2015-12-15 17:52 ` [ruby-core:72155] " headius
2015-12-15 23:47 ` [ruby-core:72164] " ko1
2015-12-16 7:39 ` [ruby-core:72178] " funny.falcon
2015-12-18 5:32 ` [ruby-core:72357] " ko1
2015-12-18 18:41 ` [ruby-core:72369] " email
2015-12-19 1:39 ` [ruby-core:72372] " ko1
2015-12-19 13:37 ` [ruby-core:72380] " email
2015-12-19 14:37 ` [ruby-core:72382] " headius
2015-12-19 15:01 ` [ruby-core:72383] " email
2015-12-19 15:27 ` [ruby-core:72386] " headius
2015-12-19 15:29 ` [ruby-core:72387] " headius
2015-12-20 8:54 ` [ruby-core:72408] " funny.falcon
2016-01-25 18:21 ` [ruby-core:73429] " Andrew Vit
2017-01-31 7:12 ` [ruby-core:79334] [Ruby trunk Bug#11822][Closed] " ko1
Reply instructions:
You may reply publicly to this message via plain-text email
using any one of the following methods:
* Save the following mbox file, import it into your mail client,
and reply-to-list from there: mbox
Avoid top-posting and favor interleaved quoting:
https://en.wikipedia.org/wiki/Posting_style#Interleaved_style
List information: https://www.ruby-lang.org/en/community/mailing-lists/
* Reply using the --to, --cc, and --in-reply-to
switches of git-send-email(1):
git send-email \
--in-reply-to=redmine.journal-55561.20151215165810.11f4aafccfe723d1@ruby-lang.org \
--to=ruby-core@ruby-lang.org \
/path/to/YOUR_REPLY
https://kernel.org/pub/software/scm/git/docs/git-send-email.html
* If your mail client supports setting the In-Reply-To header
via mailto: links, try the mailto: link
Be sure your reply has a Subject: header at the top and a blank line
before the message body.
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for read-only IMAP folder(s) and NNTP newsgroup(s).