|
From: Dirk S. <val...@ds...> - 2008-03-27 07:22:26
|
Hello, first: Thanks a lot for valgrind and the included checking tools. Now what I want: I wrote a pthreaded server tool with heavy usage of pthread_rwlock and the PTHREAD_RWLOCK_PREFER_WRITER_NONRECURSIVE_NP attribute. The idea behind is, that read looks can happen parallel multiple times and only when the data is written, an exclusive lock is taken (multi-read, single-write). Now helgrind complains about possible deadlocks due to locking e.g. foo and bar in the order 1) foo, 2) bar in one place and 1) bar, 2) foo in another. This is ok for normal exclusive looks, but disturbing for this concept. What I would like to have is, that this message (for the rwlocks) can be reduced to the cases, where at least one of the locks is a lock-write and leave lock-read only chains unnotified. If I do not have a large error in my thinking, there should be no possible situation, where read-locks result in deadlocks, when no write-lock is in the lock chain. P.S. Is there a tool telling me stack usage for threads (I use Linux). Ciao -- http://www.dstoecker.eu/ (PGP key available) |
|
From: Bart V. A. <bar...@gm...> - 2008-03-27 12:50:08
|
On Thu, Mar 27, 2008 at 8:22 AM, Dirk Stoecker <val...@ds...> wrote: > I wrote a pthreaded server tool with heavy usage of pthread_rwlock and the > PTHREAD_RWLOCK_PREFER_WRITER_NONRECURSIVE_NP attribute. The idea behind is, > that read looks can happen parallel multiple times and only when the data is > written, an exclusive lock is taken (multi-read, single-write). > > Now helgrind complains about possible deadlocks due to locking e.g. foo and bar > in the order 1) foo, 2) bar in one place and 1) bar, 2) foo in another. This is > ok for normal exclusive looks, but disturbing for this concept. > > What I would like to have is, that this message (for the rwlocks) can be > reduced to the cases, where at least one of the locks is a lock-write and > leave lock-read only chains unnotified. > > If I do not have a large error in my thinking, there should be no possible > situation, where read-locks result in deadlocks, when no write-lock is in the > lock chain. Hello Dirk, Regarding the complaint about a possible deadlock: if a first thread locks (1) foo (2) bar, and a second thread locks (3) bar and (4) foo, then at (4) it is impossible to predict which other synchronization objects will be locked by the second thread in the future. And whether or not a deadlock can be triggered depends on these future actions. So I'm not sure it is possible to invent an algorithm that detects all possible deadlocks and does not complain on your example. Bart. |
|
From: Igmar P. <mai...@jd...> - 2008-03-28 09:13:24
|
> Regarding the complaint about a possible deadlock: if a first thread > locks (1) foo (2) bar, and a second thread locks (3) bar and (4) foo, > then at (4) it is impossible to predict which other synchronization > objects will be locked by the second thread in the future. And whether > or not a deadlock can be triggered depends on these future actions. So > I'm not sure it is possible to invent an algorithm that detects all > possible deadlocks and does not complain on your example. Can't we 'borrow' the deadlock detector from the linux kernel ? It has a pretty solid and extended detecting infrastructure. Igmar |
|
From: Julian S. <js...@ac...> - 2008-03-27 15:25:28
|
Bart, On Thursday 27 March 2008 13:44, Bart Van Assche wrote: > I'm not sure it is possible to invent an algorithm that detects all > possible deadlocks and does not complain on your example. That's unfortunate. Do you know of any papers etc which explain this stuff in any detail? J |
|
From: Bart V. A. <bar...@gm...> - 2008-03-27 17:33:39
|
On Thu, Mar 27, 2008 at 4:20 PM, Julian Seward <js...@ac...> wrote: > > On Thursday 27 March 2008 13:44, Bart Van Assche wrote: > > I'm not sure it is possible to invent an algorithm that detects all > > possible deadlocks and does not complain on your example. > > That's unfortunate. Do you know of any papers etc which explain this > stuff in any detail? I'm not aware of any research carried out on this topic. Deadlock prevention appears to be a popular subject in Dr. Dobbs Journal however: an archive search learned me that about once a year an article is published in Dr. Dobbs about this subject. But all articles I verified are about mutexes, none of these articles discusses reader/writer locks. Bart. |
|
From: Dirk S. <val...@ds...> - 2008-03-27 15:46:45
|
Hello,
>> I wrote a pthreaded server tool with heavy usage of pthread_rwlock and the
>> PTHREAD_RWLOCK_PREFER_WRITER_NONRECURSIVE_NP attribute. The idea behind is,
>> that read looks can happen parallel multiple times and only when the data is
>> written, an exclusive lock is taken (multi-read, single-write).
>>
>> Now helgrind complains about possible deadlocks due to locking e.g. foo and bar
>> in the order 1) foo, 2) bar in one place and 1) bar, 2) foo in another. This is
>> ok for normal exclusive looks, but disturbing for this concept.
>>
>> What I would like to have is, that this message (for the rwlocks) can be
>> reduced to the cases, where at least one of the locks is a lock-write and
>> leave lock-read only chains unnotified.
>>
>> If I do not have a large error in my thinking, there should be no possible
>> situation, where read-locks result in deadlocks, when no write-lock is in the
>> lock chain.
>
> Regarding the complaint about a possible deadlock: if a first thread
> locks (1) foo (2) bar, and a second thread locks (3) bar and (4) foo,
> then at (4) it is impossible to predict which other synchronization
> objects will be locked by the second thread in the future. And whether
Well, why predict the future? The deadlock check comes back, when I lock a
new object, doesn't it?
> or not a deadlock can be triggered depends on these future actions. So
> I'm not sure it is possible to invent an algorithm that detects all
> possible deadlocks and does not complain on your example.
>From this I think you do not store the complete look chain, but only
"foo after bar" or "foo before bar"? Right?
Well I thought the looks are store in a tree like
foo bar2
bar bar2
bar2 foo bar
--> means 7 possible looks have been detected till now:
foo
foo -> bar
foo -> bar -> bar2
foo -> bar2
foo -> bar2 -> foo (requires rw-read-mode for foo)
foo -> bar2 -> bar
bar2
Each tree element must contain a note, where it first was detected.
And each thread has a pointer to the element, where it currently is.
Now when a new unknown lock comes, a new node is created and can be
checked against all the other trees for possible deadlocks.
Checking becomes more time consuming, the longer and deeper the tree is,
but I hope real world programs don't use extremely deep trees, as these
are very hard to get done correctly (and free of deadlocks).
Something wrong with this? How is it done in helgrind?
Ciao
--
http://www.dstoecker.eu/ (PGP key available)
|
|
From: Julian S. <js...@ac...> - 2008-03-27 16:05:32
|
> >From this I think you do not store the complete look chain, but only > "foo after bar" or "foo before bar"? Right? Yes, correct. > Well I thought the looks are store in a tree like > foo bar2 > bar bar2 > bar2 foo bar > > --> means 7 possible looks have been detected till now: > > foo > foo -> bar > foo -> bar -> bar2 > foo -> bar2 > foo -> bar2 -> foo (requires rw-read-mode for foo) > foo -> bar2 -> bar > bar2 > > Each tree element must contain a note, where it first was detected. > And each thread has a pointer to the element, where it currently is. > > Now when a new unknown lock comes, a new node is created and can be > checked against all the other trees for possible deadlocks. > > Checking becomes more time consuming, the longer and deeper the tree is, > but I hope real world programs don't use extremely deep trees, as these > are very hard to get done correctly (and free of deadlocks). > > Something wrong with this? How is it done in helgrind? H just makes a graph of simple "X before Y" relationships, as you said. Then, if the thread holds some set of locks LL and acquires M, then it reports an error if any L exists in LL for which the graph says "M before L". If that makes sense. The tree is interesting (never saw that before, though). One problem is that even maintaining the graph is an expensive operation for very lock intensive programs. Eg firefox does approximately 1 million lock/unlock events just for a simple startup/exit cycle. J |
|
From: Dirk S. <val...@ds...> - 2008-03-27 16:23:02
|
On Thu, 27 Mar 2008, Julian Seward wrote:
> The tree is interesting (never saw that before, though). One problem
> is that even maintaining the graph is an expensive operation for very
> lock intensive programs. Eg firefox does approximately 1 million
> lock/unlock events just for a simple startup/exit cycle.
That would be ok. The question would be how many different routes they
have? The tree is only expensive, when a new node is added. For already
known nodes it is mainly
for(i = 0; i < numtreeentries && tree[i] != newtree; ++i)
;
if(i < numtreeentries) switchtonode(tree[i]);
Ok. That also depends on the number of different nodes.
I do not know how this is for real-world programs, never tested it. But I
know it would work for my tool :-)
Ciao
--
http://www.dstoecker.eu/ (PGP key available)
|
|
From: Bart V. A. <bar...@gm...> - 2008-03-27 17:06:39
|
On Thu, Mar 27, 2008 at 4:46 PM, Dirk Stoecker <val...@ds...> wrote: > Well, why predict the future? The deadlock check comes back, when I lock a > new object, doesn't it? That's a good idea, but please keep in mind that deadlock checking is really time consuming. Implementing a more complex deadlock checking algorithm might slow down deadlock checking even more. Are you aware that there exist several techniques to suppress the warning about a possible deadlock ? The simplest technique is to interchange the order in which nested locking happens. Unfortunately this is not always possible. Another solution is to add extra locking, e.g. as follows: -------------------------------------------------------------------------------------- Original (triggers warning about possible deadlock): Thread 1: lock foo for reading lock bar for reading Thread 2: lock bar for reading lock foo for reading -------------------------------------------------------------------------------------- New (should not trigger a warning about a possible deadlock): Thread 1: lock foo for reading lock bar for reading Thread 2: lock foo for reading /* <- added statement */ lock bar for reading lock foo for reading -------------------------------------------------------------------------------------- Bart. |
|
From: Dirk S. <val...@ds...> - 2008-03-27 17:41:22
|
On Thu, 27 Mar 2008, Bart Van Assche wrote: > That's a good idea, but please keep in mind that deadlock checking is > really time consuming. Implementing a more complex deadlock checking > algorithm might slow down deadlock checking even more. I really would like to know, how the tree-based approach would work in this respect. I don't think for normal operations it would be so time consuming. But I really do not have enough time to start programing helgrind and try it out. > Are you aware that there exist several techniques to suppress the > warning about a possible deadlock ? The simplest technique is to > interchange the order in which nested locking happens. Unfortunately I generally do use same locking order even for read-locks (I program for a long time now and learned to be careful). The cases, where I get warnings are very hard to turn around. > this is not always possible. Another solution is to add extra locking, > e.g. as follows: > Thread 1: > lock foo for reading > lock bar for reading > > Thread 2: > lock foo for reading /* <- added statement */ > lock bar for reading > lock foo for reading I can't do that in my sources. The cases, where I have reversed looks are clearly defined and cannot be handled like that without making runtime-configuration impossible. Is there a possibility to suppress warnings without affecting other occurrencies (i.e. if there is an a/b b/a pair at places 1 and 2 it is suppressed, but all others are reported)? I suspect that there are some possible deadlocks under very special conditions, but these are hard to find in the current data output. Ciao -- http://www.dstoecker.eu/ (PGP key available) |
|
From: Ivan S. J. <isj...@i1...> - 2008-03-28 00:44:27
|
On Thursday 27 March 2008 08:22:24 Dirk Stoecker wrote: > If I do not have a large error in my thinking, there should be no possible > situation, where read-locks result in deadlocks, when no write-lock is in > the lock chain. Correct. If only read-locks are used (and no other synchronization) then deadlocks are not possible because read-locks do not block each other. On Thursday 27 March 2008 13:44:38 Bart Van Assche wrote: > Regarding the complaint about a possible deadlock: if a first thread > locks (1) foo (2) bar, and a second thread locks (3) bar and (4) foo, > then at (4) it is impossible to predict which other synchronization > objects will be locked by the second thread in the future. And whether > or not a deadlock can be triggered depends on these future actions. So > I'm not sure it is possible to invent an algorithm that detects all > possible deadlocks and does not complain on your example. Yes, it is possible. But in order to avoid false positives they cannot be online algorithms - they have to be run "after the future is known", ie. based on a trace file. /isj |
|
From: Julian S. <js...@ac...> - 2008-03-28 01:05:36
|
> Yes, it is possible. But in order to avoid false positives they cannot be > online algorithms - they have to be run "after the future is known", ie. > based on a trace file. Or at the end of execution, analysing data collected during the run. Do you have pointers to paper(s) describing this? J |
|
From: Dirk S. <val...@ds...> - 2008-03-28 07:59:20
|
On Fri, 28 Mar 2008, Ivan Skytte Jørgensen wrote: >> I'm not sure it is possible to invent an algorithm that detects all >> possible deadlocks and does not complain on your example. > > Yes, it is possible. But in order to avoid false positives they cannot be > online algorithms - they have to be run "after the future is known", ie. > based on a trace file. Sorry, I do not understand the reason for your statement. When you have stored all possible lock-chains which have occured before, then with each new entry you can check your chains and see if there could be a situation, where a deadlock would be a result. To be clear: A lock-chain for me is the order in which locks have been acquired including (lock,type,accessmode) for each node. When two chains would conflict, you get the warning at the second chain and thus always before the (possible) deadlock. If you keep the chains for individual threads, you can reduce false positives more (i.e. when only one thread does a/b and later b/a there is no need to report this), but I would not do this, as it needs memory and changing the programs a bit will then showup the problems. Your offline algorithm would allow deeper analysis in case not only chains are stored, but also the time/situation when such a chain has been used. Then one can distinguish between different version of the same conflicts (my tree model would only allow to say a/b/c and c/b conflict, but not c/b conflict in situation x and situation z). Thought you would need large logfiles for this. I get about half a GB per minute for my tool when I enable full lock logging (in low use situations). Probably I will send these logs by TCP instead and write an online analyser using perl as a demonstrator. This is probably the same work as thinning out helgrinds output. That there is no way "to invent an algorithm that detects all possible deadlocks" should be pretty clear. There can only be ways to detect problem situations, which have occured during runtime, as the "halting problem" will not go away for helgrind. Ciao -- http://www.dstoecker.eu/ (PGP key available) |
|
From: Ivan S. J. <isj...@i1...> - 2008-03-28 18:38:05
|
On Friday 28 March 2008 08:59:24 Dirk Stoecker wrote: > On Fri, 28 Mar 2008, Ivan Skytte Jørgensen wrote: > >> I'm not sure it is possible to invent an algorithm that detects all > >> possible deadlocks and does not complain on your example. > > > > Yes, it is possible. But in order to avoid false positives they cannot be > > online algorithms - they have to be run "after the future is known", ie. > > based on a trace file. > > Sorry, I do not understand the reason for your statement. When you have > stored all possible lock-chains which have occured before, then with each > new entry you can check your chains and see if there could be a situation, > where a deadlock would be a result. > To be clear: A lock-chain for me is the order in which locks have been > acquired including (lock,type,accessmode) for each node. You build lock-chains based on actual behaviour. Deducing actual deadlocks is quite simple based on that. Deducing potential deadlocks is doable, but eliminating false positives from the potential deadlocks is quite difficult (and as you mention, equivalent to the halting problem). Assuming these two partial lock traces: Thread 1: lock A lock B unlock B unlock A Thread 2: lock B lock A unlock A unlock B then it is easy to see that there is a potential deadlock. But it is not so easy to see if the potential deadlock is something that actually could occur, because you have to consider all synchronization between the threads. Example 1: Both thread 1 and 2 is wrapped in a lock on C: Thread 1: lock C lock A lock B unlock B unlock A unlock C Thread 2: lock C lock B lock A unlock A unlock B unlock C With this slight change the potential deadlock A-B is prevent C. Example 2: The involved threads synchronize in other ways: Thread 1: lock A lock B unlock B unlock A spawn thread 2 ... join thread 2 Thread 2: lock B lock A unlock A unlock B the "other" synchronization could also be a semaphore, a socket, a condition, and pthread_mutex_timedlock, a signal, etc. > If you keep the chains for individual threads, you can reduce false > positives more (i.e. when only one thread does a/b and later b/a there is > no need to report this), but I would not do this, as it needs memory and > changing the programs a bit will then showup the problems. Yes, this is a tradeoff between speed and accuracy. > Your offline algorithm would allow deeper analysis in case not only chains > are stored, but also the time/situation when such a chain has been used. > Then one can distinguish between different version of the same conflicts > (my tree model would only allow to say a/b/c and c/b conflict, but not c/b > conflict in situation x and situation z). Thought you would need large > logfiles for this. I get about half a GB per minute for my tool when I > enable full lock logging (in low use situations). Interesting. I made a tool for analyzing pthread programs based on interposing and lock traces a few years ago. I newer got around to implement rwlock analysis ( wasn't widespread back then). http://i1.dk/mta/ Feel free to get inspired or borrow code from it. And as you also observe, tracing a real world program generates massive amounts of trace. > That there is no way "to invent an algorithm that detects all possible > deadlocks" should be pretty clear. There can only be ways to detect > problem situations, which have occured during runtime, as the "halting > problem" will not go away for helgrind. I completely agree. Back to my original statement: because and online algorithm cannot eleminate parts of traces except the most trivial ones (such as reducing "lock A, unlock A, lock A, unlock A" to "lock A, unlock A") it needs to keep most of the collected traces; and on each lock operation it has to build a wait-for graph for all earlier operations in all threads and check for potential deadlocks. Therefore my statement that it is possible but it should only be done offline. But detecting the simple potential A-B deadlock, even if it is a false positive, is is very useful because it is a problem waiting to happen when someone changes program (such as eliminating lock C in example 1 above) Regards, Ivan |
|
From: <bar...@gm...> - 2008-03-28 18:47:39
|
On 3/27/08, Dirk Stoecker <val...@ds...> wrote: > > P.S. Is there a tool telling me stack usage for threads (I use Linux). Is it sufficient if stack usage is reported for all threads at the time a process terminates ? I can add such functionality easily to exp-drd if you want. Bart. |
|
From: Dirk S. <val...@ds...> - 2008-03-28 19:34:56
|
On Fri, 28 Mar 2008, bar...@gm... wrote: >> P.S. Is there a tool telling me stack usage for threads (I use Linux). > > Is it sufficient if stack usage is reported for all threads at the > time a process terminates ? I can add such functionality easily to > exp-drd if you want. Actually I want to know the maximum stack size a thread used. Because I need to set the maximum stack size to a defined value and currently this is based on guessing+some security margin. And this is never a good way. Measurement+security margin would be much better. Ciao -- http://www.dstoecker.eu/ (PGP key available) |
|
From: Bart V. A. <bar...@gm...> - 2008-03-30 10:25:40
|
On Thu, Mar 27, 2008 at 9:22 AM, Dirk Stoecker <val...@ds...> wrote: > Now helgrind complains about possible deadlocks due to locking e.g. foo and bar > in the order 1) foo, 2) bar in one place and 1) bar, 2) foo in another. This is > ok for normal exclusive looks, but disturbing for this concept. > > What I would like to have is, that this message (for the rwlocks) can be > reduced to the cases, where at least one of the locks is a lock-write and > leave lock-read only chains unnotified. > > If I do not have a large error in my thinking, there should be no possible > situation, where read-locks result in deadlocks, when no write-lock is in the > lock chain. It took some time before I realized that the algorithm I invented about seven years ago handles the above scenario correctly. The algorithm is as follows: * For regular mutexes, complain if nested locking occurs in a different order than the order in which nested locking happened before (as usual). * Handle reader-writer locking objects as if their implementation was based on a single mutex M and as if the operations on these locking objects were implemented as follows: - Obtaining a reader lock is equivalent to locking + unlocking mutex M. - Unlocking a reader lock is equivalent to locking + unlocking mutex M. - Obtaining a writer lock is equivalent to locking mutex M. - Unlocking a writer lock is equivalent to unlocking mutex M. It's not clear to me how the lockdep algorithm in the Linux kernel treats reader-writer locks. Bart. |
|
From: <bar...@gm...> - 2008-03-30 16:35:26
|
On 3/30/08, Bart Van Assche <bar...@gm...> wrote:
> It took some time before I realized that the algorithm I invented
> about seven years ago handles the above scenario correctly. The
> algorithm is as follows:
> * For regular mutexes, complain if nested locking occurs in a
> different order than the order in which nested locking happened before
> (as usual).
> * Handle reader-writer locking objects as if their implementation was
> based on a single mutex M and as if the operations on these locking
> objects were implemented as follows:
> - Obtaining a reader lock is equivalent to locking + unlocking mutex M.
> - Unlocking a reader lock is equivalent to locking + unlocking mutex M.
> - Obtaining a writer lock is equivalent to locking mutex M.
> - Unlocking a writer lock is equivalent to unlocking mutex M.
The algorithm I was referring to also flags upgrading a reader lock to
a writer lock as an error, since this can easily lead to a deadlock.
E.g. the following code will sooner or later deadlock:
Thread 1
while (true)
{
read lock A
write lock A
unlock A
unlock A
}
Thread 2
while (true)
{
read lock A
write lock A
unlock A
unlock A
}
Bart.
|
|
From: Ivan S. J. <isj...@i1...> - 2008-03-30 14:21:16
|
On Sunday 30 March 2008 12:25:46 Bart Van Assche wrote: [snip] > * Handle reader-writer locking objects as if their implementation was > based on a single mutex M and as if the operations on these locking > objects were implemented as follows: > - Obtaining a reader lock is equivalent to locking + unlocking mutex M. > - Unlocking a reader lock is equivalent to locking + unlocking mutex M. > - Obtaining a writer lock is equivalent to locking mutex M. > - Unlocking a writer lock is equivalent to unlocking mutex M. It does not catch this scenario: thread 1: readlock A writelock B unlock B unlock A thread 2: readlock B writelock A unlock A unlock B /isj |
|
From: Bart V. A. <bar...@gm...> - 2008-04-05 15:33:49
|
On Sun, Mar 30, 2008 at 4:20 PM, Ivan Skytte Jørgensen <isj...@i1...> wrote: > On Sunday 30 March 2008 12:25:46 Bart Van Assche wrote: > [snip] > > > * Handle reader-writer locking objects as if their implementation was > > based on a single mutex M and as if the operations on these locking > > objects were implemented as follows: > > - Obtaining a reader lock is equivalent to locking + unlocking mutex M. > > - Unlocking a reader lock is equivalent to locking + unlocking mutex M. > > - Obtaining a writer lock is equivalent to locking mutex M. > > - Unlocking a writer lock is equivalent to unlocking mutex M. > > It does not catch this scenario: > > thread 1: > readlock A > writelock B > unlock B > unlock A > thread 2: > readlock B > writelock A > unlock A > unlock B Would you consider it acceptable for a tool that verifies the locking order to complain whenever it is attempted to obtain a writer lock nested inside a reader lock ? Bart. |
|
From: Ivan S. J. <isj...@i1...> - 2008-03-30 14:35:48
|
On Friday 28 March 2008 02:01:31 Julian Seward wrote: > > Yes, it is possible. But in order to avoid false positives they cannot be > > online algorithms - they have to be run "after the future is known", ie. > > based on a trace file. > > Or at the end of execution, analysing data collected during the run. > > Do you have pointers to paper(s) describing this? Strange, I thought this was a well-researched subject, but I can only find three relevant papers at citeseer: http://citeseer.ist.psu.edu/feitelson91deadlock.html http://citeseer.ist.psu.edu/masticola93static.html http://www.havelund.com/Publications/padtad06.pdf All of them mostly concerned with the theory and not the practicality. There is a brief/introductory presentation at http://www.cs.jhu.edu/~yairamir/cs418/os4/sld028.htm I am not sure if any of the helps. /isj |
|
From: Julian S. <js...@ac...> - 2008-03-30 16:54:35
|
On Sunday 30 March 2008 16:35, Ivan Skytte Jørgensen wrote: > On Friday 28 March 2008 02:01:31 Julian Seward wrote: > > > Yes, it is possible. But in order to avoid false positives they cannot > > > be online algorithms - they have to be run "after the future is known", > > > ie. based on a trace file. > > > > Or at the end of execution, analysing data collected during the run. > > > > Do you have pointers to paper(s) describing this? > > Strange, I thought this was a well-researched subject, but I can only find > three relevant papers at citeseer: [...] On the basis that many ideas in CS have been reinvented several times by different generations of researchers, I would not be surprised to find that the database people had this all figured out by about 1970 :-) After all, concurrency and locking is a big deal in database-world. J |
|
From: Bart V. A. <bar...@gm...> - 2008-03-30 18:27:22
|
On Sun, Mar 30, 2008 at 6:50 PM, Julian Seward <js...@ac...> wrote: > > On the basis that many ideas in CS have been reinvented several > times by different generations of researchers, I would not be > surprised to find that the database people had this all figured > out by about 1970 :-) After all, concurrency and locking is a > big deal in database-world. I'm not a database expert, but as far as I know database software detects deadlocks after these happened. This is not the same as locking order checking: locking order checking guarantees the absence of deadlocks by verifying the order in which locks are nested in a single thread at a time. By this time I found the following papers that discuss a.o. lock ordering: * Chandrasekhar Boyapati. SafeJava: A Unified Type System for Safe Programming. PhD thesis, Massachusetts Institute of Technology, 2004. http://pmg.csail.mit.edu/~chandra/publications/phd.pdf Discusses Java language extensions to specify a locking order in the source code. * B. McCloskey, F. Zhou, D. Gay, and E. Brewer. Autolocker: synchronization inference for atomic sections. In J. G. Morrisett and S. L. P. Jones, editors, POPL, pages 346–358. ACM, Jan. 2006. http://cag.csail.mit.edu/crg/papers/mccloskey06autolocker.pdf Autolocker is a tool that converts so called pessimistic sections into lock-based code in such a way that the generated code honors a lock order. * Pratibha Permandla, Michael Roberson, Chandrasekhar Boyapati, A type system for preventing data races and deadlocks in the java virtual machine language, Proceedings of the 2007 ACM SIGPLAN/SIGBED conference on Languages, compilers, and tools Extends on the SafeJava work. Bart. |