[ python-Bugs-788520 ] Queue class has logic error when non-blocking

Sun Jul 11 08:00:19 CEST 2004

Bugs item #788520, was opened at 2003-08-13 23:57
Message generated for change (Comment added) made by berryman77
You can respond by visiting: 
https://sourceforge.net/tracker/?func=detail&atid=105470&aid=788520&group_id=5470

Category: Threads
Group: Python 2.2.2
Status: Open
Resolution: None
Priority: 5
Submitted By: GaryD (gazzadee)
Assigned to: Nobody/Anonymous (nobody)
Summary: Queue class has logic error when non-blocking

Initial Comment:
Looking at the Queue class, I noticed that it might
incorrectly raise a Full/Empty Exception when called
with block=False.

This leads to the following undesirable behaviour:
 * Full exception raised when Queue not full
 * Full exception raised when Queue has no maxsize

Here's my logic (for put(), but get() is similar):

First part of code for put, in Queue.py:
    def put(self, item, block=1):
        if block:
            self.fsema.acquire()
        elif not self.fsema.acquire(0):
            raise Full

Now, for the purposes of raising a Full exception, we
are assuming that fsema is locked if and only if the
Queue is full.

BUT, it seems that fsema is locked every time an item
is added to the Queue, even if that item would not make
the Queue full.

Hence, it might be possible for a Full exception to be
raised, when fsema is locked due to adding an item that
would not  actually make the Queue full. 

An example...

 * Queue with maxsize 10, currently 5 objects in it.
 * Threads T1 and T2, both trying to add an item with
Queue.put(item, block=True).
 * This should obviously be fine, resulting in a Queue
with 7 items.
 [1] Call T1.put(item1, block=True)
 [2] Call T2.put(item2, block=True)
 [3] T1 grabs fsema and mutex, but then the current
thread changes before they are released...
 [4] T2 cannot acquire fsema (since T1 currently has
it), and so raises the Full exception (incorrectly)

Of course, I may have misunderstood something, since I
haven't been able to consistently reproduce the problem
(threading errors are so vexing).

I have no easy solution to this issue (redo the class
using a threading.BoundedSemaphore to count the Queue
length?).

My python version:
Python 2.2.2 (#1, Feb 24 2003, 17:36:09)
[GCC 3.0.4 (Mandrake Linux 8.2 3.0.4-2mdk)] on linux2

----------------------------------------------------------------------

Comment By: Randall B. Smith (berryman77)
Date: 2004-07-11 01:00

Message:
Logged In: YES 
user_id=880241

A Full exception is returned when the queue is NOT FULL. 
This is a bug!  The lack of an immediate solution is not an
excuse to accept incorrect code.

----------------------------------------------------------------------

Comment By: GaryD (gazzadee)
Date: 2003-08-21 22:40

Message:
Logged In: YES 
user_id=693152

Okay, that makes more sense. So, loosely expressed,
non-blocking means there's no way the user can put the Queue
in a blocked state (and especially not deadlocked) - as with
your example of waiting forever on a get call. But,
obviously, internal locks can always be used (in a careful
manner).

I think that's closer to my implicit understand of blocking
that I was trying to express. In the case of put/get, I had
a slightly different expectation about what we were blocking
for (as we have already dicscussed at length :-). Anyway,
I've knocked up some modifications to the documentation,
which you're welcome to use, abuse, or reject out of hand.

I've done this in the form of modifications to the source
code. I assume that's the correct approach, but the 2.3
source code and 2.3 HTML documentation seem to be a bit
different (so I ended up incorporating the relevant HTML
doco into the python source doco, then modifying that).

The patch is the output from:
% diff Queue_v2_3.py Queue_doc_change.py

----------------------------------------------------------------------

Comment By: Tim Peters (tim_one)
Date: 2003-08-18 00:41

Message:
Logged In: YES 
user_id=31435

It depends on what you mean by &quot;blocking&quot; &lt;wink&gt;.  If the 
thread implementation schedules fairly, it's impossible for 
self.mutex to be held for a &quot;long&quot; time by any thread -- unlike 
esema and fsema, self.mutex is used only for mutual exclusion 
over brief sections of code that don't wait for anything, and 
nothing Queue clients do can cause self.mutex to be held for 
an arbitrarily long time (a spectacularly bad OS 
implementation of thread scheduling could, but that's out of 
the user's-- and out of Python's --hands).

The usual meaning of &quot;blocking&quot; is that clients *can* do 
something to get the system into a state where a call can 
take arbitrarily long to complete (while assuming fair thread 
scheduling).  The obvious example here is that Queue.get() 
can take forever if the Queue is empty and the app stops 
adding anything to the Queue.  There's nothing (sane) the 
app can do that can make Queue.get_nowait() take forever.

BTW, I hope you're looking at the 2.3 code here!  Queue is 
more complicated in 2.3 because these methods have also 
grown optional timeout arguments.  If you're really worried 
about &quot;spurious&quot; Full exceptions, doing a blocking 2.3 
Queue.put() call with a short timeout will try to grab fsema 
several times before giving up.

----------------------------------------------------------------------

Comment By: GaryD (gazzadee)
Date: 2003-08-17 23:52

Message:
Logged In: YES 
user_id=693152

Whoops - let's try that question in a clearer way:

When you do a non-blocking call to put(), why does it
acquire mutex in a blocking way (ie. &quot;put(block=False)&quot; will
call &quot;mutex.acquire()&quot;, which could block whilst acquiring
mutex). I thought the theory was that you *never* block
anywhere.

----------------------------------------------------------------------

Comment By: Tim Peters (tim_one)
Date: 2003-08-17 23:32

Message:
Logged In: YES 
user_id=31435

We acquire a mutex with a blocking call because the use of a 
blocking call announces that the client is *willing* to block, 
and nothing about the state of a Queue can be changed 
without acquiring a lock first.  So it wouldn't make sense not 
to acquire a lock in that case.

I have no objection at all to improving the docs.  They appear 
to be what they are now because the original version of the 
Queue module didn't have a non-blocking put() method, or a 
Full exception.  I added those 7(!) years later, in 1999.  
Development was done by emailing changes to Guido at that 
time, though, and doc changes were often dropped on the 
floor.

If you can work up a doc patch to supply words that would 
make better sense to you, that would be great.

----------------------------------------------------------------------

Comment By: GaryD (gazzadee)
Date: 2003-08-17 22:53

Message:
Logged In: YES 
user_id=693152

First up, you're right that non-blocking calls are unusual.
This isn't exactly a critical matter for me :-)

Okay, I have misunderstood the meaning of non-blocking calls
- so it actually means &quot;ensure we never under any
circumstances block&quot;. Why then do we acquire mutex with a
blocking call?

I am not suggesting there's anything wrong with the naming
of Full (amusing as your suggestion is :-). Of course you
can't completely describe how an exception will be used in
it's name.

It just seems more intuitive for put's documentation to
fully and unambiguously describe when an exception is
raised, rather than to have part of the function
documentation (&quot;or locked&quot;) in the Exception documentation.
More straightforward, etc.

----------------------------------------------------------------------

Comment By: Tim Peters (tim_one)
Date: 2003-08-17 22:22

Message:
Logged In: YES 
user_id=31435

The primary point of a non-blocking call is never to block.  
That's the common meaning of &quot;non-blocking&quot; (in or out of 
Python).  After all, a &quot;non-blocking&quot; call that *could* block is 
useless for apps that need not to block.  If you're willing to 
block, use the blocking methods (which most apps do use, 
BTW -- using the non-blocking methods is unusual).

The Full exception isn't raised incorrectly.  &quot;Full&quot; is just 4 
letters strung together, and is only meant to be suggestive 
and convenient -- its full meaning is explained in the docs, 
albeit somewhat cryptically.  I don't think it would be a real 
improvement to, e.g., rename this exception to 
FullOrMaybeNotFullButCheckingForThatCouldPotentiallyBlockSo
WeSkippedThat &lt;wink&gt;.

----------------------------------------------------------------------

Comment By: GaryD (gazzadee)
Date: 2003-08-17 21:55

Message:
Logged In: YES 
user_id=693152

Sorry - my fault. I didn't read that part of the doco well
enough.

However, is it an issue that important behaviour of a
function is described separately to the function (ie. in the
exception)? Could we put a general note in the put/get
documentation also (Eg. &quot;In the current implementation the
Full exception may sometimes be raised incorrectly.&quot;)

Also, I may have the wrong expectations for how this class
should behave. My assumption was that put(block=False) means
 don't block waiting for a slot in the queue, but it's
implicitly okay to block for other reasons (eg. internal
data sharing, as actually happens with mutex). Was this
incorrect?

I'll see if I can think up an alternative implementation
over the next few days.

----------------------------------------------------------------------

Comment By: Tim Peters (tim_one)
Date: 2003-08-17 15:50

Message:
Logged In: YES 
user_id=31435

Yes, but unless it's a screamingly obvious non-bug I like to 
wait at least a week to see whether somebody else has a 
clever approach that works as well but without the surprising 
parts.  The docs in this case aren't terribly clear, because 
they really can't explain the whole truth without explaining 
the implementation.

----------------------------------------------------------------------

Comment By: Raymond Hettinger (rhettinger)
Date: 2003-08-17 15:30

Message:
Logged In: YES 
user_id=80475

Can this be closed as invalid?

----------------------------------------------------------------------

Comment By: Tim Peters (tim_one)
Date: 2003-08-14 09:59

Message:
Logged In: YES 
user_id=31435

As the docs say (ALL CAPS emphasis added),

&quot;&quot;&quot;
exception Full 

Exception raised when non-blocking put() (or put_nowait()) is 
called on a Queue object which is full OR LOCKED. 
&quot;&quot;&quot;

and similarly for Empty.  The primary point of a non-blocking 
call is never to block, and that's why &quot;or locked&quot; is in the 
docs.  A BoundedSemaphore (or any other &quot;reliable&quot; 
synchronization gimmick) could block, so cannot be used.

In practice, it doesn't matter:  a Queue user who wants to 
use non-blocking calls has to be prepared for Full or Empty 
exceptions, and that's the end of it.

----------------------------------------------------------------------

You can respond by visiting: 
https://sourceforge.net/tracker/?func=detail&atid=105470&aid=788520&group_id=5470