[ python-Bugs-788520 ] Queue class has logic error when non-blocking
SourceForge.net
noreply at sourceforge.net
Sun Jul 11 21:47:48 CEST 2004
Bugs item #788520, was opened at 2003-08-14 00:57
Message generated for change (Comment added) made by tim_one
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: Tim Peters (tim_one)
Date: 2004-07-11 15:47
Message:
Logged In: YES
user_id=31435
Well, there aren't "several posters" here: before you jumped
in, there were exactly three in this report's history: the
person who filed the original report (gazzadee), me, and
Raymond Hettinger (who asked once whether to close the
report as invalid). In the 11 months this has been open,
nobody else has cared enough to comment, let alone produce
a different implementation.
The reasons the current implementation is reasonable have
already been explained here at some length, so I'm not going
over them again. If you can't tolerate the Full or Empty
exceptions. don't use non-blocking calls. It's typical of non-
blocking calls (in and out of Python) that they may return for
no other reason than that they cannot succeed immediately,
so honor their contract not to block by returning at once but
without a useful response.
I still agree the docs could stand improvement.
----------------------------------------------------------------------
Comment By: Randall B. Smith (berryman77)
Date: 2004-07-11 15:13
Message:
Logged In: YES
user_id=880241
Rather than reiterating here, I agree with this post:
Date: 2003-08-17 21:55
Sender: gazzadee
I did read the docs for the put method, but not for the Full
Exception, as I assumed it means the queue is full.
Although the documentation of the Full exception makes the
code technically correct, I found (as several of the posters
here did) that it is unintuitive. So much so that it
appears to be a bug (hence this bug report). As I see it,
the documentation simply documents the bug.
"""
The name of the exception is simply briefly suggestive, as are
the names of most exceptions;
FULL_OR_NOT_FULL_BUT_LOCKED would be more accurate,
but too clumsy.
"""
The programmer is not aware of the internal blocking unless
s/he has looked at the source of Queue. S/he is most likely
expecting put_nowait() to not wait on the queue to free a
slot. This is to me the intuitive functionality of this
method. According to the comments here, there is
disagreement on this issue. So if put_nowait means there is
to be no blocking internally or by the queue, then there
should be 2 exceptions, Full and Locked, so that the user
can distinguish between the two.
----------------------------------------------------------------------
Comment By: Tim Peters (tim_one)
Date: 2004-07-11 02:32
Message:
Logged In: YES
user_id=31435
berryman77, as the first comment in this report suggested,
read the documentation:
"""
Full
Exception raised when non-blocking put() (or put_nowait()) is
called on a Queue object which is full or locked.
"""
Note the "OR LOCKED" part, a natural counterpoint to
your "NOT FULL" screaming <wink>.
When code functions as designed and as documented, you
can argue about the design, or about the quality of the docs,
but you can't call it "a bug" (well, not if you want to be taken
seriously).
The name of the exception is simply briefly suggestive, as are
the names of most exceptions;
FULL_OR_NOT_FULL_BUT_LOCKED would be more accurate,
but too clumsy.
----------------------------------------------------------------------
Comment By: Randall B. Smith (berryman77)
Date: 2004-07-11 02: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 23: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 01:41
Message:
Logged In: YES
user_id=31435
It depends on what you mean by "blocking" <wink>. If the
thread implementation schedules fairly, it's impossible for
self.mutex to be held for a "long" 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 "blocking" 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 "spurious" 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-18 00: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. "put(block=False)" will
call "mutex.acquire()", 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-18 00: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 23: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 "ensure we never under any
circumstances block". 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 ("or locked") in the Exception documentation.
More straightforward, etc.
----------------------------------------------------------------------
Comment By: Tim Peters (tim_one)
Date: 2003-08-17 23: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 "non-blocking" (in or out of
Python). After all, a "non-blocking" 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. "Full" 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 <wink>.
----------------------------------------------------------------------
Comment By: GaryD (gazzadee)
Date: 2003-08-17 22: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. "In the current implementation the
Full exception may sometimes be raised incorrectly.")
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 16: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 16:30
Message:
Logged In: YES
user_id=80475
Can this be closed as invalid?
----------------------------------------------------------------------
Comment By: Tim Peters (tim_one)
Date: 2003-08-14 10:59
Message:
Logged In: YES
user_id=31435
As the docs say (ALL CAPS emphasis added),
"""
exception Full
Exception raised when non-blocking put() (or put_nowait()) is
called on a Queue object which is full OR LOCKED.
"""
and similarly for Empty. The primary point of a non-blocking
call is never to block, and that's why "or locked" is in the
docs. A BoundedSemaphore (or any other "reliable"
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
More information about the Python-bugs-list
mailing list