473,583 Members | 2,817 Online
Bytes | Software Development & Data Engineering Community
+ Post

Home Posts Topics Members FAQ

Queue can result in nested monitor deadlock

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 )

Apr 17 '06 #1
13 2536
Jonathan Amsterdam <jb*********@gm ail.com> 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
Apr 17 '06 #2
"Jonathan Amsterdam" <jb*********@gm ail.com> wrote in message
news:11******** **************@ v46g2000cwv.goo glegroups.com.. .
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

Apr 17 '06 #3
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.

Apr 17 '06 #4
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("N o_one_else_can_ do_anything")
wait_for_someon e_else_to_do_so mething() # waits forever

-Jack
Apr 17 '06 #5
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?
Apr 17 '06 #6
"Jonathan Amsterdam" <jb*********@gm ail.com> wrote in message
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.


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
Apr 17 '06 #7

"Jonathan Amsterdam" <jb*********@gm ail.com> wrote in message
news:11******** **************@ v46g2000cwv.goo glegroups.com.. .
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

Apr 17 '06 #8
In article <11************ **********@e56g 2000cwe.googleg roups.com>,
Jonathan Amsterdam <jb*********@gm ail.com> 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
Apr 17 '06 #9
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.)

Apr 17 '06 #10

This thread has been closed and replies have been disabled. Please start a new discussion.

Similar topics

9
2772
by: phil | last post by:
And sorry I got ticked, frustrating week >And I could help more, being fairly experienced with >threading issues and race conditions and such, but >as I tried to indicate in the first place, you've >provided next to no useful (IMHO) information to >let anyone help you more than this This is about 5% of the code. Uses no locks.
1
4228
by: Rohit Raghuwanshi | last post by:
Hello all, we are running a delphi application with DB2 V8.01 which is causing deadlocks when rows are being inserted into a table. Attaching the Event Monitor Log (DEADLOCKS WITH DETAILS) here. From the log it looks like the problem happens when 2 threads insert 1 record each in the same table and then try to aquire a NS (Next Key Share)...
12
1877
by: Brett Robichaud | last post by:
I need to make access to a reference object threadsafe. My natural instinct was to simply use Monitor.Enter() and Exit(). The problem is that the object behind the reference changes frequently, so my understanding of Monitor indicates this would not protect my object. Example: Bitmap bmp = new Bitmap("x.jpg"); Monitor.Enter(bmp); bmp =...
6
3720
by: rmunson8 | last post by:
I have a derived class from the Queue base class. I need it to be thread-safe, so I am using the Synchronized method (among other things out of scope of this issue). The code below compiles, but at runtime, the cast of "Queue.Synchronized(new EventQueue())" to an EventQueue object is failing stating invalid cast. Why? public class...
1
3288
by: Dominic | last post by:
Hi all, We've just migrated to IIS 6.0 / Windows Server 2003. We are now experiencing some stability problem what we did not experience in IIS 5.0 / Windows 2000 Server. Our ASP.NET application is running in a web-farm environment of multiple web servers. We have been using "Performance Monitor" to monitor the "Requests in Application...
4
10270
by: Russell Warren | last post by:
I'm guessing no, since it skips down through any Lock semantics, but I'm wondering what the best way to clear a Queue is then. Esentially I want to do a "get all" and ignore what pops out, but I don't want to loop through a .get until empty because that could potentially end up racing another thread that is more-or-less blindly filling it...
0
1439
by: Michael Bayer | last post by:
Hi - i was just going through this thread: http://mail.python.org/ pipermail/python-list/2006-April/336948.html , where it is suggested that the Lock instance used by Queue.Queue should be publically configurable. I have identified another situation where a Queue can be deadlocked, one which is also alleviated by configuring the type of...
7
1652
by: RobKinney1 | last post by:
Here is another question we have been meaning to post for a long time. My colleague is literally pulling chunks of hair out of his head right now. We have a logging class. This class is mutlithreaded (as required by our boss). So when we tell the class to log something, it puts the data into a queue, and logs it to the disk when it has...
12
1399
by: Paul Rubin | last post by:
I'd like to suggest adding a new operation Queue.finish() This puts a special sentinel object on the queue. The sentinel travels through the queue like any other object, however, when q.get() encounters the sentinel, it raises StopIteration instead of returning the sentinel. It does not remove the sentinel from the queue, so further...
0
7896
marktang
by: marktang | last post by:
ONU (Optical Network Unit) is one of the key components for providing high-speed Internet services. Its primary function is to act as an endpoint device located at the user's premises. However, people are often confused as to whether an ONU can Work As a Router. In this blog post, we’ll explore What is ONU, What Is Router, ONU & Router’s main...
0
7828
by: Hystou | last post by:
Most computers default to English, but sometimes we require a different language, especially when relocating. Forgot to request a specific language before your computer shipped? No problem! You can effortlessly switch the default language on Windows 10 without reinstalling. I'll walk you through it. First, let's disable language...
0
8329
jinu1996
by: jinu1996 | last post by:
In today's digital age, having a compelling online presence is paramount for businesses aiming to thrive in a competitive landscape. At the heart of this digital strategy lies an intricately woven tapestry of website design and digital marketing. It's not merely about having a website; it's about crafting an immersive digital experience that...
0
6583
agi2029
by: agi2029 | last post by:
Let's talk about the concept of autonomous AI software engineers and no-code agents. These AIs are designed to manage the entire lifecycle of a software development project—planning, coding, testing, and deployment—without human intervention. Imagine an AI that can take a project description, break it down, write the code, debug it, and then...
0
5377
by: conductexam | last post by:
I have .net C# application in which I am extracting data from word file and save it in database particularly. To store word all data as it is I am converting the whole word file firstly in HTML and then checking html paragraph one by one. At the time of converting from word file to html my equations which are in the word document file was convert...
0
3821
by: TSSRALBI | last post by:
Hello I'm a network technician in training and I need your help. I am currently learning how to create and manage the different types of VPNs and I have a question about LAN-to-LAN VPNs. The last exercise I practiced was to create a LAN-to-LAN VPN between two Pfsense firewalls, by using IPSEC protocols. I succeeded, with both firewalls in...
0
3847
by: adsilva | last post by:
A Windows Forms form does not have the event Unload, like VB6. What one acts like?
1
1436
muto222
by: muto222 | last post by:
How can i add a mobile payment intergratation into php mysql website.
0
1160
bsmnconsultancy
by: bsmnconsultancy | last post by:
In today's digital era, a well-designed website is crucial for businesses looking to succeed. Whether you're a small business owner or a large corporation in Toronto, having a strong online presence can significantly impact your brand's success. BSMN Consultancy, a leader in Website Development in Toronto offers valuable insights into creating...

By using Bytes.com and it's services, you agree to our Privacy Policy and Terms of Use.

To disable or enable advertisements and analytics tracking please visit the manage ads & tracking page.