Queue can result in nested monitor deadlock

Discussion in 'Python' started by Jonathan Amsterdam, Apr 17, 2006.

  1. 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.Queue):
    """
    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.__init__(self, maxsize)
    if lock:
    self.mutex = lock
    # Re-create the condition objects with the new mutex.
    self.not_empty = threading.Condition(self.mutex)
    self.not_full = threading.Condition(self.mutex)
     
    Jonathan Amsterdam, Apr 17, 2006
    #1
    1. Advertising

  2. Jonathan Amsterdam <> wrote:
    ...
    > 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.


    Posting a patch and/or bug to Sourceforge is probably the best approach.


    Alex
     
    Alex Martelli, Apr 17, 2006
    #2
    1. Advertising

  3. Jonathan Amsterdam

    Paul McGuire Guest

    "Jonathan Amsterdam" <> wrote in message
    news:...
    > 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.
    >

    This isn't really a deadlock, it is just a blocking condition, until Thread
    1 releases M.

    There are 3 requirements for deadlock:
    1. Multiple resources/locks
    2. Multiple threads
    3. Out-of-order access

    You have definitely created the first two conditions, but the deadlock only
    occurs if Thread 2 first acquires the Queue lock, then needs to get M before
    continuing. By forcing all access to the Queue through the class's methods,
    which presumably lock and unlock M as part of their implementation, then you
    have successfully prevented 3. No deadlocks, just proper
    blocking/synchronization.

    -- Paul
     
    Paul McGuire, Apr 17, 2006
    #3
  4. 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.
     
    Jonathan Amsterdam, Apr 17, 2006
    #4
  5. On Mon, Apr 17, 2006 at 09:41:37AM -0700, Jonathan Amsterdam wrote:
    > 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.
    >

    Right, the problem isn't with Queue it is with your global lock M.
    Here is the pseudo code for your program:

    acquire_lock("No_one_else_can_do_anything")
    wait_for_someone_else_to_do_something() # waits forever

    -Jack
     
    Jack Diederich, Apr 17, 2006
    #5
  6. Jonathan Amsterdam

    Duncan Booth Guest

    Jonathan Amsterdam wrote:

    > 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.
    >

    If your class is using a queue to handle the inter-thread communication why
    is it also using a semaphore?

    If your methods are already locked so only one thread runs at a time why
    are you then using a queue to provide another layer of locking: a simple
    list should suffice?
     
    Duncan Booth, Apr 17, 2006
    #6
  7. Jonathan Amsterdam

    Paul McGuire Guest

    "Jonathan Amsterdam" <> wrote in message
    news:...
    > 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.
    >


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

    -- Paul
     
    Paul McGuire, Apr 17, 2006
    #7
  8. Jonathan Amsterdam

    Terry Reedy Guest

    "Jonathan Amsterdam" <> wrote in message
    news:...
    > 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.


    As a sometimes bug reviewer who has noticed that a substantial fraction of
    'bug' reports do not actually report CPython bugs, I wish more people would
    do as you did and post here first and get opinions from the wider variety
    of readers here.

    A CPython bug is a discrepancy between a reasonable interpretation of the
    doc and the behavior of the CPython implementation. Your post did not even
    claim such a discrepancy that I could see.

    A request for a design change can be put on the RFE (request for
    enhancement) list. Patches, whether to fix bugs or implement enhancements,
    usually go on the patch list. Note that you do not necessarily need to
    convince people that the current design is 'flawed' to demonstrate that a
    change would be good.

    Perhaps your recipe should be added to the oreilly online python cookbook.

    Terry Jan Reedy
     
    Terry Reedy, Apr 17, 2006
    #8
  9. Jonathan Amsterdam

    Alan Morgan Guest

    In article <>,
    Jonathan Amsterdam <> wrote:
    >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.


    That's not a problem in the design of the queue class, it is a problem
    in how you are using it. Two possible solutions are:

    1. Don't have the global lock on the object (or, at the very least,
    don't have that global lock taken when you read from the queue).
    2. Don't use a syncronized queue. If the only access to the queue is
    through the object and the object is protected then you don't need
    a synchronized queue.

    Alan
    --
    Defendit numerus
     
    Alan Morgan, Apr 17, 2006
    #9
  10. 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.)
     
    Jonathan Amsterdam, Apr 17, 2006
    #10
  11. Jonathan Amsterdam

    Paul McGuire Guest

    "Jonathan Amsterdam" <> wrote in message
    news:...
    > 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
     
    Paul McGuire, Apr 17, 2006
    #11
  12. On 17 Apr 2006 13:37:24 -0700, "Jonathan Amsterdam"
    <> declaimed the following in comp.lang.python:

    > 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.
    >

    Unfortunately, since you haven't shown us /your/ code (or a minimal
    subset that represents your problem) it is not all that easy to propose
    valid solutions...

    I would suggest, for the above "other fields", that you release M
    prior to doing the Q.get(), and reacquire M whenever Q.get() returns.

    > 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.)


    Well -- since you say that won't work... You appear to have a major
    redesign effort ahead -- since you need to decouple blocking on Q.get()
    from inside your other lock (or move Q.put() outside of the other
    potentially blocking lock calls)


    http://greenteapress.com/semaphores/
    might have something of applicability
    --
    > ============================================================== <
    > | Wulfraed Dennis Lee Bieber KD6MOG <
    > | Bestiaria Support Staff <
    > ============================================================== <
    > Home Page: <http://www.dm.net/~wulfraed/> <
    > Overflow Page: <http://wlfraed.home.netcom.com/> <
     
    Dennis Lee Bieber, Apr 18, 2006
    #12
  13. >>>>> "Paul McGuire" <._bogus_.com> (PM) wrote:

    >PM> "Jonathan Amsterdam" <> wrote in message
    >PM> news:...
    >>> 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 <>
    URL: http://www.cs.uu.nl/~piet [PGP 8DAE142BE17999C4]
    Private email:
     
    Piet van Oostrum, Apr 18, 2006
    #13
  14. 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.
     
    Jonathan Amsterdam, Apr 18, 2006
    #14
  15. Jonathan Amsterdam

    Ove Svensson Guest

    "Jonathan Amsterdam" <> 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.
     
    Ove Svensson, Apr 19, 2006
    #15
    1. Advertising

Want to reply to this thread or ask your own question?

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. Russell Warren

    Is Queue.Queue.queue.clear() thread-safe?

    Russell Warren, Jun 22, 2006, in forum: Python
    Replies:
    4
    Views:
    725
    Russell Warren
    Jun 27, 2006
  2. Michael Bayer

    queue deadlock possibility

    Michael Bayer, Jun 26, 2006, in forum: Python
    Replies:
    0
    Views:
    327
    Michael Bayer
    Jun 26, 2006
  3. Gal Aviel
    Replies:
    8
    Views:
    953
    Dennis Lee Bieber
    Feb 29, 2008
  4. Kris
    Replies:
    0
    Views:
    536
  5. Michael Tan
    Replies:
    32
    Views:
    1,079
    Ara.T.Howard
    Jul 21, 2005
Loading...

Share This Page