I have heard it suggested that if every thread in a program takes 
whatever locks it needs to take in sorted order, it is guaranteed that 
deadlock can never occur.

Is this correct? And does anybody have a reference I can site?

Post a reply to this message

I'd think this is immediately obvious.

One issue is that a thread does not always know what locks it needs 
before the fact.  And if you hold a lock and want to get another with a 
lower key then you have to release the lock you hold then go back and 
get them in the right order.

As to references, Wikipedia 'Deadlock' article is a decent starting 
point.  Many more erudite references are given there.

Post a reply to this message

Paul Fuller wrote:
> I'd think this is immediately obvious.

Not to me. ;-)

> One issue is that a thread does not always know what locks it needs 
> before the fact.

Yes, this is the killer. Often it's not possible to know what locks you 
want until you read some data (which you have to lock first). And if you 
release the locks, somebody else could come and change the data...

> As to references, Wikipedia 'Deadlock' article is a decent starting 
> point.  Many more erudite references are given there.

OK, I'll take a look.

Post a reply to this message

Invisible wrote:

> Paul Fuller wrote:

>> One issue is that a thread does not always know what locks it needs
>> before the fact.
> 
> Yes, this is the killer. Often it's not possible to know what locks you
> want until you read some data (which you have to lock first). And if you
> release the locks, somebody else could come and change the data...

Isn't that the point? I've never worked with a low-level locking setup, but
I implemented a high-level one in the CMS I'm currently working on. If
somebody accesses a specific item, it is locked with a timeout. If he
doesn't commit changes within 15 minutes (or whatever is set), he "loses"
the lock, and somebody else can edit.

I.e. releasing a lock = it's ok for somebody else to change the data. You
have the lock = everybody else is blocked from changing the data?

-- 
Stefan Viljoen

Post a reply to this message

>>> One issue is that a thread does not always know what locks it needs
>>> before the fact.
>> Yes, this is the killer. Often it's not possible to know what locks you
>> want until you read some data (which you have to lock first). And if you
>> release the locks, somebody else could come and change the data...
> 
> Isn't that the point? I've never worked with a low-level locking setup, but
> I implemented a high-level one in the CMS I'm currently working on. If
> somebody accesses a specific item, it is locked with a timeout. If he
> doesn't commit changes within 15 minutes (or whatever is set), he "loses"
> the lock, and somebody else can edit.
> 
> I.e. releasing a lock = it's ok for somebody else to change the data. You
> have the lock = everybody else is blocked from changing the data?

My point is, you can't just go "I've got lock 7 and lock 13, and now I 
need lock 2, so I'll just release lock 7 and lock 13, then take lock 2 
and take back lock 7 and lock 13". In between releasing the locks and 
taking them back, something could change. You need a better plan than that.

Post a reply to this message

Invisible wrote:

> My point is, you can't just go "I've got lock 7 and lock 13, and now I
> need lock 2, so I'll just release lock 7 and lock 13, then take lock 2
> and take back lock 7 and lock 13". In between releasing the locks and
> taking them back, something could change. You need a better plan than
> that.

Isn't this what a mutex (like it is implemented in the Linux kernel) is for? 

Wik it a bit, I think it might be a partial answer to your original
question... :)
-- 
Stefan Viljoen

Post a reply to this message

> OK, I'll take a look.

Is this just theoretical interest or is there an actual problem that you 
are trying to solve ?

In non-trivial cases like databases and operating systems the 
possibility of deadlocks cannot be eliminated entirely.  The designers 
seek to reduce the chances by good design but they also have to 
implement 'deadlock detection' and 'deadlock resolution'.

Post a reply to this message

I just saw this:

http://en.wikipedia.org/wiki/Gridlock

I can't help thinking that this should be an XKCD strip. I can just 
imagine Black Hat Guy doing something to the timing of the traffic 
signals to induce a mathematically indefinite deadly embrace. (And throw 
in a pun or two in the process... Get it?... Process?)

Post a reply to this message

Paul Fuller wrote:
>> OK, I'll take a look.
> 
> Is this just theoretical interest or is there an actual problem that you 
> are trying to solve ?
> 
> In non-trivial cases like databases and operating systems the 
> possibility of deadlocks cannot be eliminated entirely.  The designers 
> seek to reduce the chances by good design but they also have to 
> implement 'deadlock detection' and 'deadlock resolution'.

I've just implemented a solution; I'm trying to write it up. ;-)

Post a reply to this message

http://en.wikipedia.org/wiki/Deadlock_provision

...so, it's like the deadlock resolution algorithm where you randomly 
terminate one process, except that you're terminating somebody's 
*employment* instead?

Wow, that's pretty harsh. :-D

Post a reply to this message