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

[SourceForge.net]

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: Gary Donovan (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: 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