473,545 Members | 1,884 Online
Bytes | Software Development & Data Engineering Community
+ Post

Home Posts Topics Members FAQ

Deadlock detection

Hi,

Does anyone know of a deadlock detector for Python? I don't think it
would be too hard to hook into the threading module and instrument
mutexes so they can be tested for deadlocks. I've googled around but I
haven't found anything.

Cheers,

Duncan.

--
-- Duncan Grisby --
-- du****@grisby.o rg --
-- http://www.grisby.org --
Jul 18 '05 #1
7 4558
>Does anyone know of a deadlock detector for Python? I don't think it
would be too hard to hook into the threading module and instrument
mutexes so they can be tested for deadlocks. I've googled around but I
haven't found anything.


Software Verification have Python Thread Validator. Its not publicly
advertised on the beta part of the website, but it is available.

http://www.softwareverify.com/publicBeta.html

Take a look at Thread Validator or Java Thread Validator to see what the
tool looks like (the Python tool is similar). If you are interested send
an email to support asking about the Python port.

Stephen
--
Stephen Kellett
Object Media Limited http://www.objmedia.demon.co.uk
RSI Information: http://www.objmedia.demon.co.uk/rsi.html
Jul 18 '05 #2

Duncan Grisby <du*********@gr isby.org> wrote:

Hi,

Does anyone know of a deadlock detector for Python? I don't think it
would be too hard to hook into the threading module and instrument
mutexes so they can be tested for deadlocks. I've googled around but I
haven't found anything.


I'm not aware of a deadlock dector for any language. I propose that a
completely working deadlock detector is NP-Complete, as it would, I
believe, necessitate solving the halting problem.
- Josiah

Jul 18 '05 #3
(warning: pedantic and off-topic response) NP-Complete does not mean
"equivalent to the halting problem." It means "poly-time equivalent to
any other NP-Complete problem".

NP-Complete problems are "only" exponential-time. The halting problem
is much harder! And of course, just the fact that a problem is
NP-complete doesn't mean that you can't construct algorithms that do a
pretty good job a pretty good fraction of the time.

Jul 18 '05 #4
In article <ma************ *************** ***********@pyt hon.org>,
Josiah Carlson <jc******@uci.e du> wrote:

Duncan Grisby <du*********@gr isby.org> wrote:

Does anyone know of a deadlock detector for Python? I don't think it
would be too hard to hook into the threading module and instrument
mutexes so they can be tested for deadlocks. I've googled around but I
haven't found anything.


I'm not aware of a deadlock dector for any language. I propose that a
completely working deadlock detector is NP-Complete, as it would, I
believe, necessitate solving the halting problem.


As Paul Du Bois has pointed out, NP complete is much easier than the
halting problem (i.e. the halting problem simply can't be done in
general, no matter how much time you have).

Aside from that, you're right that statically analysing code for
deadlocks is equivalent to the halting problem, and therefore
impossible. What I'm looking for, though, is a dynamic detector that
detects deadlocks at run-time when they happen. Doing that is well
understood, and there are plenty of systems that do it. I just haven't
been able to find one for Python.

Cheers,

Duncan.

--
-- Duncan Grisby --
-- du****@grisby.o rg --
-- http://www.grisby.org --
Jul 18 '05 #5
In message <5e************ **************@ nf1.news-service-com>, Duncan
Grisby <du*********@gr isby.org> writes
understood, and there are plenty of systems that do it. I just haven't
been able to find one for Python.


There is one at http://www.softwareverify.com as I mentioned in a
previous posting.

Stephen
--
Stephen Kellett
Object Media Limited http://www.objmedia.demon.co.uk
RSI Information: http://www.objmedia.demon.co.uk/rsi.html
Jul 18 '05 #6
On Mon, 2004-12-06 at 06:21, Duncan Grisby wrote:
Hi,

Does anyone know of a deadlock detector for Python? I don't think it
would be too hard to hook into the threading module and instrument
mutexes so they can be tested for deadlocks. I've googled around but I
haven't found anything.


In general, accurate deadlock detection is intractable. Like many
problems of this class you have two choices - either reduce the scope of
the problem to a non-general one or try a heuristic to guess.

As I recall, deadlock prevention is similar to the halting problem; the
only question you can answer is "which category am I in:"

A) I know for sure there are no deadlocks
B) I don't know, maybe there are, maybe there arn't.

In the halting problem, the answer to your question is B until you
actually halt, in which case the answer to your problem is obvious.

Here is a quick and dirty heuristics to filter some programs as being in
bin A or bin B.

First, for bin B. Instrument your mutex so that every time you lock, it
creates a directed edge in a global system wide graph from your current
mutex (mutex_N) to the next to most recently locked mutex you are
currently holding for the locking thread. If your graph becomes
cyclic, you might be in bin B (well, you were never in bin A to being
with.) Throw a "I've lost faith in my inability to deadlock" exception.

If you can *prove* that there is a strict topological order between
nested mutex invocations, then you are in bin A. The degree of rigor in
your proof is up to you, your level of comfort and how many people die
if your code deadlocks (your personal website and medical instruments
have different standards.)

Not everybody trusts themselves. There are a number of alternative
approaches, including having a single global critical section lock
(ancient linux smp code) or designing your mutex operation to imply the
release of all held locks. Of course, if you must hold more than one
lock at a time, your mutex function can take a list of locks that it
will atomically apply. The proper design of this is left as an exercise
for the reader.

Unless you thought of this from the beginning, retrofitting safe locks
into your existing large project will be expensive. The next
possibility won't work for python, but it is useful to keep in mind.

The halting problem has a small caveat, it is applicable to "general"
Turing machines. Place restrictions on your Turing machine that makes
it not a Turing machine and the problem goes away. In real time systems
(oh my, cat < aborted.phd.the sis.tex > mail python-list@... ) where you
have to compute the longest time any piece of code will take to execute
this sort of analysis is common place. Get rid of function pointers
(including weakly typed OOPLs like Python.) You don't have to worry
about limiting loop counts like in a RTL, because we arn't interested in
timing information. Oh, and ditch recursion. Maybe you don't have to,
but I'm not sure.

Now walk through your code taking each possible path. You can collapse
loops to each meaningful combination (depends on the nature of your
languages loop construct), collapse paths that don't have any mutex
operations. You get the idea.

Unless mutex calls are rare, or your code simple, you might spend a
while. Largely this problem is intractable, even with simplifications ,
but it is done which is why safety critical programs are (well, should
be) small and their languages not very expressive (as in finite state
machine, and not in the "but my computer is a FSM sense.")


Adam DePrince

Jul 18 '05 #7
Adam DePrince <ad**@cognitcor p.com> writes:
On Mon, 2004-12-06 at 06:21, Duncan Grisby wrote:
Hi,

Does anyone know of a deadlock detector for Python? I don't think it
would be too hard to hook into the threading module and instrument
mutexes so they can be tested for deadlocks. I've googled around but I
haven't found anything.


In general, accurate deadlock detection is intractable. Like many
problems of this class you have two choices - either reduce the scope of
the problem to a non-general one or try a heuristic to guess.


I've recently been involved in a thread on another list that dealt
with the problems of programming with threads. There are people
approaching the problems (including deadlocks) by providing constructs
for threading that mean you can't write such code. At least, that's
the idea.

http://www.jot.fm/issues/issue_2004_04/article6 was posted as one
such solution. I'm not convinced it works, but the paper only
discusses half the solution.

<mike
--
Mike Meyer <mw*@mired.or g> http://www.mired.org/home/mwm/
Independent WWW/Perforce/FreeBSD/Unix consultant, email for more information.
Jul 18 '05 #8

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

Similar topics

11
2500
by: hendershot | last post by:
Using SQL Server 2000 SP3a, I run the following in 2 query analizer windows on the Northwind database, the second one always gets the deadlock Msg 1205: Window 1: declare @cnt int select @cnt = 5 while @cnt > 0 begin
1
2349
by: debian mojo | last post by:
Hello faculties, i'm encountering a strange a deadlock problem on my remote server which is used to give application demo to the client. It has happened that on one of the databases a deadlock situation is taking place. What is the most detailed way to detect such the cause of such a deadlock to the innermost level of detail, like what...
2
3515
by: Alex | last post by:
I was hoping someone could confirm my understanding of how InnoDB handles deadlocks (error 1213) and timeouts (error 1206). The way I understand it, with AUTOCOMMIT=0, if I issue 3 SQL statements (updates), A, B, and C (in that order), and get one of the errors above while issuing statement C, InnoDB will have rolled back statements A and B....
3
7619
by: Nigel Robbins | last post by:
Hi There, I'm getting a deadlock when I have two clients running the following statement. DELETE FROM intermediate.file_os_details WHERE file_uid = ? AND obj_uid There is a compound index on file_uid / obj_uid. The isolation level is UR and I have set DB2_RR_TO_RS=YES. Any thoughts why I'm getting the deadlock ?
1
4225
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)...
3
4105
by: muscha | last post by:
Hello, Is there a function like CTRL-Backspace in .Net / C# like in Java? I suspect there is a deadlock in my code and I am trying to find it. thanks, /m
2
7646
by: Jürgen Devlieghere | last post by:
Hi, We are creating event-driven multi-threaded applications on a daily basis. To help us solving deadlocks, we implemented a CriticalSection class that does dead-lock detection: an attempt to Enter() the critical section that would cause a deadlock logs the complete deadlock loop (thread / Critical section) and raises an exception. It has...
4
26627
by: Ian Semmel | last post by:
I am doing a length operation reading access database and creating a sql database when I get this message. What am I supposed to do to get around it ? Thanks
0
1642
by: fuzzybr80 | last post by:
Hi, I am working with an application with a high rate of inserts/updates/deletes into a particular table, and recently am getting the following error code. My table uses InnoDB engine. ERROR 1213 (40001): Deadlock found when trying to get lock; try restarting transaction I read the section of MySQL documentation relating to this error...
0
7410
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
7668
Oralloy
by: Oralloy | last post by:
Hello folks, I am unable to find appropriate documentation on the type promotion of bit-fields when using the generalised comparison operator "<=>". The problem is that using the GNU compilers, it seems that the internal comparison operator "<=>" tries to promote arguments from unsigned to signed. This is as boiled down as I can make it. ...
0
7923
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...
1
7437
by: Hystou | last post by:
Overview: Windows 11 and 10 have less user interface control over operating system update behaviour than previous versions of Windows. In Windows 11 and 10, there is no way to turn off the Windows Update option using the Control Panel or Settings app; it automatically checks for updates and installs any it finds, whether you like it or not. For...
0
7773
tracyyun
by: tracyyun | last post by:
Dear forum friends, With the development of smart home technology, a variety of wireless communication protocols have appeared on the market, such as Zigbee, Z-Wave, Wi-Fi, Bluetooth, etc. Each protocol has its own unique characteristics and advantages, but as a user who is planning to build a smart home system, I am a bit confused by the...
0
5984
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
4960
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...
1
1025
muto222
by: muto222 | last post by:
How can i add a mobile payment intergratation into php mysql website.
0
722
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.