From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: X-Original-To: poffice@blade.nagaokaut.ac.jp Delivered-To: poffice@blade.nagaokaut.ac.jp Received: from kankan.nagaokaut.ac.jp (kankan.nagaokaut.ac.jp [133.44.2.24]) by blade.nagaokaut.ac.jp (Postfix) with ESMTP id 88CEF19E0025 for ; Wed, 16 Dec 2015 01:26:26 +0900 (JST) Received: from voscc.nagaokaut.ac.jp (voscc.nagaokaut.ac.jp [133.44.1.100]) by kankan.nagaokaut.ac.jp (Postfix) with ESMTP id 9B977B5D89C for ; Wed, 16 Dec 2015 01:58:27 +0900 (JST) Received: from neon.ruby-lang.org (neon.ruby-lang.org [221.186.184.75]) by voscc.nagaokaut.ac.jp (Postfix) with ESMTP id 8E79218CC7B5 for ; Wed, 16 Dec 2015 01:58:27 +0900 (JST) Received: from [221.186.184.76] (localhost [IPv6:::1]) by neon.ruby-lang.org (Postfix) with ESMTP id E2284120475; Wed, 16 Dec 2015 01:58:24 +0900 (JST) X-Original-To: ruby-core@ruby-lang.org Delivered-To: ruby-core@ruby-lang.org Received: from o10.shared.sendgrid.net (o10.shared.sendgrid.net [173.193.132.135]) by neon.ruby-lang.org (Postfix) with ESMTPS id 46838120459 for ; Wed, 16 Dec 2015 01:58:22 +0900 (JST) DKIM-Signature: v=1; a=rsa-sha1; c=relaxed; d=sendgrid.me; h=from:to:references:subject:mime-version:content-type:content-transfer-encoding:list-id; s=smtpapi; bh=UM4ESDwiCMqC9TM/nbP5YPm6AqA=; b=SmC9c+kCrP+/RJQ95i xn5YRteBfgc8dvRjHmx2qhJq73gp6atmBfD41r+tF1ijSXLJo6xg2AhBubW2pqeQ 4JUZVag05aZKt9IOln4zAQIvrgt2fbuzC8VrMIxiXbtVkr8xAXYqF9RP+nanP+Zs KnOG/QH6/PZqwSJ68soSvkJzg= Received: by filter0568p1mdw1.sendgrid.net with SMTP id filter0568p1mdw1.15241.567046A359 2015-12-15 16:58:11.688677786 +0000 UTC Received: from herokuapp.com (ec2-54-163-104-132.compute-1.amazonaws.com [54.163.104.132]) by ismtpd0006p1iad1.sendgrid.net (SG) with ESMTP id q3M5Qgh6SeaqXr7dRCWHZQ for ; Tue, 15 Dec 2015 16:58:11.877 +0000 (UTC) Date: Tue, 15 Dec 2015 16:58:11 +0000 From: headius@headius.com To: ruby-core@ruby-lang.org Message-ID: References: Mime-Version: 1.0 Content-Type: text/plain; charset=UTF-8 Content-Transfer-Encoding: 7bit X-Redmine-MailingListIntegration-Message-Ids: 46857 X-Redmine-Project: ruby-trunk X-Redmine-Issue-Id: 11822 X-Redmine-Issue-Author: headius X-Redmine-Sender: headius X-Mailer: Redmine X-Redmine-Host: bugs.ruby-lang.org X-Redmine-Site: Ruby Issue Tracking System X-Auto-Response-Suppress: All Auto-Submitted: auto-generated X-SG-EID: ync6xU2WACa70kv/Ymy4QrNMhiuLXJG8OTL2vJD1yS4MYtAvFsRzBea8TS7GfNfO1XeKh5TEW87wuZ L5jKXB6kBObp0UsAuk7DhmfL9EguPVhsQaw7yHA23Cx8QesDCWVxW1R5WEE56mQWctBV023+yJN8mk an8Ppr+hHBh5FibUFaMnimkmzXpvFOqMrEF5FdHAHddDgj7/nwis3qHZHg== X-ML-Name: ruby-core X-Mail-Count: 72150 Subject: [ruby-core:72150] [Ruby trunk - Bug #11822] Semantics of Queue#pop after close are wrong X-BeenThere: ruby-core@ruby-lang.org X-Mailman-Version: 2.1.15 Precedence: list Reply-To: Ruby developers List-Id: Ruby developers List-Unsubscribe: , List-Post: List-Help: List-Subscribe: , Errors-To: ruby-core-bounces@ruby-lang.org Sender: "ruby-core" 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/