Queue can result in nested monitor deadlock

[Jonathan Amsterdam]

I think there's a slight design flaw in the Queue class that makes it
hard to avoid nested monitor deadlock. The problem is that the mutex
used by the Queue is not easy to change. You can then easily get
yourself into the following situation (nested monitor deadlock):

Say we have a class that contains a Queue and some other things. The
class's internals are protected by a mutex M. Initially the Queue is
empty. The only access to the queue is through this class.

Thread 1 locks M, then calls Queue.get(). It blocks. At this point the
Queue's mutex is released, but M is still held.

Thread 2 tries to put something in the Queue by calling the enclosing
class's methods, but it blocks on M. Deadlock.

The solution would be to expose the Queue's mutex via a constructor
argument and/or method, so that, to take the above example, one could
create M and give it to the Queue as its mutex. Of course this is
doable now, as the code below demonstrates. But it should be documented
and exposed.

As I'm new to the Python community, I'm not sure that this is the right
forum for this suggestion. Is it the sort of thing one would put on the
SourceForge bug list? Advice appreciated.

"Fixed" Queue class:

class LQueue(Queue.Qu eue):
"""
Fixes a problem with the standard Queue implementation: you can't
use your own mutex,
so you are subject to nested monitor deadlock. This version lets
you pass in your
own lock.
"""

def __init__(self, maxsize=0, lock=None):
"Optionally takes a lock (threading.Lock or threading.RLock ) to
use for the queue's lock."
Queue.Queue.__i nit__(self, maxsize)
if lock:
self.mutex = lock
# Re-create the condition objects with the new mutex.
self.not_empty = threading.Condi tion(self.mutex )
self.not_full = threading.Condi tion(self.mutex )

[Paul McGuire]

"Jonathan Amsterdam" <jb*********@gm ail.com> wrote in message
news:11******** **************@ e56g2000cwe.goo glegroups.com.. .

This is a reply to Alan Morgan, Paul McGuire and Duncan Booth.

I need mutex M because I have other fields in my class that need to be
thread-safe.

The reason I want to use a Queue and not a list is that a Queue has
additional synchronization besides the mutex. For instance, Queue.get()
will block the caller until the queue is non-empty. Of course I could
build this behavior on top of a list, but then I'm reinventing the
wheel: Queue.Queue is the perfect thing, except for the problem I
describe.

I can't release my mutex M and then call Queue.get(). That could be a
race condition: between the time M is released and Queue's mutex is
acquired, another thread could get into my object and mess things up.
(We'd need a specific example to see this, and there may be many cases
where I could safely release M before calling Queue.get(), but in
general it won't work.)

What if you expose an unguarded method on your class, that allows external
put()'s to the Queue without first locking M?

-- Paul

[Piet van Oostrum]

>>>>> "Paul McGuire" <pt***@austin.r r._bogus_.com> (PM) wrote:

PM> "Jonathan Amsterdam" <jb*********@gm ail.com> wrote in message
PM> news:11******** **************@ e56g2000cwe.goo glegroups.com.. .

If you don't want to call it deadlock, fine, but the program execution
I describe will make no progress to the end of time. Thread 2 can never
put anything in the queue, because Thread 1 holds M, and Thread 1 will
never release M because that can only happen if someone puts something
on the queue.

PM> Ah, I get it now, and yes as you describe it, this is a deadlock. But why
PM> do you need both mutex M and a Queue, then? You should release M before
PM> calling Queue.get(). Then if you need to, you should reacquire it
PM> afterward.

What Jonathan says is that in his example M and the mutex for the Queue
should be the same to solve the problem. And that the Queue API should
allow you to do that. I think he is right.
--
Piet van Oostrum <pi**@cs.uu.n l>
URL: http://www.cs.uu.nl/~piet [PGP 8DAE142BE17999C 4]
Private email: pi**@vanoostrum .org

[Jonathan Amsterdam]

No redesign necessary. I simply make M be the Queue's mutex, via the
LQueue class I posted. I am making the modest suggestion that this
feature be documented and exposed in the Queue class.

[Ove Svensson]

"Jonathan Amsterdam" <jb*********@gm ail.com> writes:

No redesign necessary. I simply make M be the Queue's mutex, via the
LQueue class I posted. I am making the modest suggestion that this
feature be documented and exposed in the Queue class.

Even though LQueue is the correct sollution to the problem, why not fix
Queue.Queue? Fixing Queue.Queue would not break any existing code and we
don't have to pollute the namespace with yet another class.