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

Stefan Viljoen schrieb:
> 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? 

With a mutex /being/ a lock, it doesn't get you out of the dilemma:

(1) Locks can create deadlocks.

(2) Deadlocks can be prevented by numbering the locks, and emposing the 
constraint that a program cannot acquire a "lower" lock than the 
"highest" one it currently owns, prevents deadlocks for sure.

(3) With this locking scheme, a program that has acquired lock X, done 
some computations on the data read while holding the lock, possibly even 
written other data, and is now coming to the conclusion that it needs to 
acquire lock X-N, can do nothing but rollback to the state before it 
acquired lock X, acquire lock X-N, and then acquire lock X again and 
re-do all the computations, because the data the previous run was based 
on might have been changed in the meantime.

So if performance is an issue, and it is not known beforehand what locks 
may be required to complete the operation, this locking concept is 
usually not an option.

Post a reply to this message

Invisible schrieb:
> 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?

Not really their *employment*, but rather their partial ownership of a 
business - at a monetary compensation.

And most variants don't seem too random to me.

Post a reply to this message

Stefan Viljoen wrote:
> Isn't this what a mutex (like it is implemented in the Linux kernel) is for? 

No. He's talking about taking and holding multiple mutexes.

There are officially five ways to prevent deadlocks. Let's see if I can 
remember them from memory:

1) Lock things in order, as you say.
2) Don't hold a lock while waiting for another lock.
    I.e., immediately roll back if you can't immediately aquire a lock.
3) Aquire all locks you'll need before you start processing.
    E.g., "run this job where there's a video tape reader, a CD burner,
    and a DSP available."
4) Only lock one thing, obviously.
5) Hmmmm... It's taking me too long to remember. :-)

But yeah, there's a formal mathematical proof that you can avoid deadlock in 
exactly five ways.

-- 
   Darren New, San Diego CA, USA (PST)
   I ordered stamps from Zazzle that read "Place Stamp Here".

Post a reply to this message

clipka wrote:
> So if performance is an issue, and it is not known beforehand what locks 
> may be required to complete the operation, this locking concept is 
> usually not an option.

I don't think you have a choice, if you want ACID-style guarantees that your 
changes are committed and valid. :-)  Everything else breaks down to doing 
locks and retrying for a deadlock.

-- 
   Darren New, San Diego CA, USA (PST)
   I ordered stamps from Zazzle that read "Place Stamp Here".

Post a reply to this message

Darren New schrieb:
> clipka wrote:
>> So if performance is an issue, and it is not known beforehand what 
>> locks may be required to complete the operation, this locking concept 
>> is usually not an option.
> 
> I don't think you have a choice, if you want ACID-style guarantees that 
> your changes are committed and valid. :-)  Everything else breaks down 
> to doing locks and retrying for a deadlock.

If noticing during an operation that you'll need an additional "lower" 
lock is a frequent situation you'll encounter, then risking deadlock may 
be the more performant option. Especially if all you really need are a 
few individual pages from a database, for instance, so that the risk of 
deadlock may actually be quite low. You'd be in for a retry anyway, 
whether you need to rollback to ackquire additional locks or to break up 
a deadlock.

Of course, if you absolutely positively know which locks you'll need, 
ordered locking seems to be the way to go.

If you're not sure, then of course you can acquire just any lock you 
/may/ possibly need, but that'll degrade performance as well.

Post a reply to this message

Darren New schrieb:
> 
> 1) Lock things in order, as you say.
> 2) Don't hold a lock while waiting for another lock.
>    I.e., immediately roll back if you can't immediately aquire a lock.
> 3) Aquire all locks you'll need before you start processing.
>    E.g., "run this job where there's a video tape reader, a CD burner,
>    and a DSP available."
> 4) Only lock one thing, obviously.
> 5) Hmmmm... It's taking me too long to remember. :-)
> 
> But yeah, there's a formal mathematical proof that you can avoid 
> deadlock in exactly five ways.

I guess timing out on acquiring a lock would constitute a variant of 2) 
in theory, right?

Also note that 3) only works to prevent deadlocks if acquiring multiple 
locks at once is an atomic operation.

Post a reply to this message

Invisible <voi### [at] devnull> wrote:
> 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?

  Perhaps if you explained what it means to "take whatever locks it needs
to take in sorted order", then I might be able to write some answer.
I just can't understand what that means.

-- 
                                                          - Warp

Post a reply to this message

Warp wrote:
> Invisible <voi### [at] devnull> wrote:
>> 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?
> 
>   Perhaps if you explained what it means to "take whatever locks it needs
> to take in sorted order", then I might be able to write some answer.
> I just can't understand what that means.

If you assign a unique ID to every lock in the system, and arrange for 
every thread to take whatever locks it needs to take in ascending order, 
deadlock is guaranteed not to occur.

Or so I believe, anyway...

-- 
http://blog.orphi.me.uk/
http://www.zazzle.com/MathematicalOrchid*

Post a reply to this message

Darren New wrote:

> There are officially five ways to prevent deadlocks. Let's see if I can 
> remember them from memory:
> 
> 1) Lock things in order, as you say.
> 2) Don't hold a lock while waiting for another lock.
>    I.e., immediately roll back if you can't immediately aquire a lock.
> 3) Aquire all locks you'll need before you start processing.
>    E.g., "run this job where there's a video tape reader, a CD burner,
>    and a DSP available."
> 4) Only lock one thing, obviously.
> 5) Hmmmm... It's taking me too long to remember. :-)
> 
> But yeah, there's a formal mathematical proof that you can avoid 
> deadlock in exactly five ways.

See, Darren knew.

(You see what I did there?)

Although... how is #4 different from #2?

Anyway, do you have a citable reference for this stuff? (I'm guessing 
Dijkstra, Knuth, or somebody must have written about this...)

-- 
http://blog.orphi.me.uk/
http://www.zazzle.com/MathematicalOrchid*

Post a reply to this message

Orchid XP v8 <voi### [at] devnull> wrote:
> If you assign a unique ID to every lock in the system, and arrange for 
> every thread to take whatever locks it needs to take in ascending order, 
> deadlock is guaranteed not to occur.

  I still don't understand how the "ascending order" has anything to do
with locks.

  Assume process 1 reserves resource 1, and then wants to also reserve
resource 2. However, resource 2 has already been reserved by process 2,
which means that process 1 has to wait for it to be freed. Meanwhile
process 2 tries to also reserve resource 1, but it's already reserved
by process 1, so process 2 has to wait. They are in a deadlock, waiting
for each other.

  What does any "ascending order" of locks have anything to do with this?

  (Btw, if you are curious, the above is the classical "dining philosophers
problem" with two processes and two resources. There could be more processes
and resources, forming a ring, with the same deadlock possibility.)

-- 
                                                          - Warp

Post a reply to this message

Warp wrote:

>   I still don't understand how the "ascending order" has anything to do
> with locks.
> 
>   Assume process 1 reserves resource 1, and then wants to also reserve
> resource 2. However, resource 2 has already been reserved by process 2,
> which means that process 1 has to wait for it to be freed. Meanwhile
> process 2 tries to also reserve resource 1, but it's already reserved
> by process 1, so process 2 has to wait. They are in a deadlock, waiting
> for each other.
> 
>   What does any "ascending order" of locks have anything to do with this?

Because, if every process always reversed resources in ascending order, 
then both processes above will attempt to reverse resource 1 and then 
resource 2, in that order. In the above example, deadlock occurs exactly 
because the first process tries to get resource 1 and then resource 2, 
but the other process tries to get resource 2 and then resource 1 
(descending order).

-- 
http://blog.orphi.me.uk/
http://www.zazzle.com/MathematicalOrchid*

Post a reply to this message

Paul Fuller wrote:

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

Ooo... Wikipedia claims you're supposed to also release resources in 
descending order. I didn't know that. o_O

-- 
http://blog.orphi.me.uk/
http://www.zazzle.com/MathematicalOrchid*

Post a reply to this message

clipka wrote:
> If noticing during an operation that you'll need an additional "lower" 
> lock is a frequent situation you'll encounter, then risking deadlock may 
> be the more performant option.

I misunderstood your reference to "this locking concept".

-- 
   Darren New, San Diego CA, USA (PST)
   I ordered stamps from Zazzle that read "Place Stamp Here".

Post a reply to this message

clipka wrote:
> I guess timing out on acquiring a lock would constitute a variant of 2) 
> in theory, right?

Yes. In that case, you're not "holding" the locks, as you'll release them to 
prevent a deadlock.

> Also note that 3) only works to prevent deadlocks if acquiring multiple 
> locks at once is an atomic operation.

Yes, that's the idea. It's pretty simple to set up an atomic-lock mechanism 
if you have a complete list of all possible locks up front.

-- 
   Darren New, San Diego CA, USA (PST)
   I ordered stamps from Zazzle that read "Place Stamp Here".

Post a reply to this message

Orchid XP v8 wrote:
> Although... how is #4 different from #2?

#4 is only having a lock on one item at a time. #2 means you can have 
multiple locks, you just can't *wait* on a lock if you already have another 
lock.

They all sound pretty similar, and boil down to "don't cause conflicts 
without resolving it."  You can avoid causing it (by only locking one thing, 
or locking in order) or you can resolve it (by freeing locks when you get a 
deadlock).

> Anyway, do you have a citable reference for this stuff? (I'm guessing 
> Dijkstra, Knuth, or somebody must have written about this...)

Uh, probably somewhere, but not off the top of my head, no.

-- 
   Darren New, San Diego CA, USA (PST)
   I ordered stamps from Zazzle that read "Place Stamp Here".

Post a reply to this message

Orchid XP v8 <voi### [at] devnull> wrote:
> Because, if every process always reversed resources in ascending order, 

  Reversed?

> then both processes above will attempt to reverse resource 1 and then 
> resource 2, in that order. In the above example, deadlock occurs exactly 
> because the first process tries to get resource 1 and then resource 2, 
> but the other process tries to get resource 2 and then resource 1 
> (descending order).

  You assume that the processes can reserve the resources in any order
they want. It may be so that process 1 *has to* reserve resource 1 before
it can reserve resource 2, and the other way around for process 2.

  Anyways, you were talking about ordering IDs of *locks*, not ordering
resources. I still can't understand what you are talking about.

-- 
                                                          - Warp

Post a reply to this message

Warp wrote:
>   You assume that the processes can reserve the resources in any order
> they want. It may be so that process 1 *has to* reserve resource 1 before
> it can reserve resource 2, and the other way around for process 2.

Right. In which case, this mechanism doesn't work. :-) Otherwise, everyone 
would always use this mechanism and not worry about deadlocks.

>   Anyways, you were talking about ordering IDs of *locks*, not ordering
> resources. I still can't understand what you are talking about.

He's trying to say this:

Establish a globally unique total ordering on all possible things you can 
lock. (Whether you're locking a mutex or a resource or whatever is 
irrelevant.) Let us call the thing you can lock a resource, and you prevent 
someone from using that resource while you hold the lock.

If you always request locks on resources in the same order as the globally 
unique total ordering described above, you will never deadlock. You can skip 
over resources, but you can't hold a lock on a higher-numbered resource 
while requesting a lock on a lower-numbered resource.

It's not always possible to create this global ordering, mind, but if you 
have something hierarchical (like B-Tree pages), it can be possible and 
efficient. So if you always lock everything you need from left-to-right at 
each level of a tree before locking something at the next level, you are 
guaranteed not to ever get a deadlock. If you want in an XML document to 
lock all the <div> elements with class="lockme", for example, you can do 
that without hitting a deadlock, as long as everyone follows the same rules.

I'm pretty sure you can release in any order, so IIRC you could even iterate 
thru the whole tree in pre-order traversal, locking each node, peeking, 
unlocking without modifying if you don't want to change it, then moving on 
to the next node.

-- 
   Darren New, San Diego CA, USA (PST)
   I ordered stamps from Zazzle that read "Place Stamp Here".

Post a reply to this message

Darren New <dne### [at] sanrrcom> wrote:
> Warp wrote:
> >   You assume that the processes can reserve the resources in any order
> > they want. It may be so that process 1 *has to* reserve resource 1 before
> > it can reserve resource 2, and the other way around for process 2.

> Right. In which case, this mechanism doesn't work. :-) Otherwise, everyone 
> would always use this mechanism and not worry about deadlocks.

  So the original claim was not about numbering locks (whatever that might
mean), but numbering shared resources so that one process can only reserve
more than one resource at a time in the order dictated by those numbers?

  I suppose that would work, at least assuming that a process never releasing
a resource is not included in the definition of "deadlock".

-- 
                                                          - Warp

Post a reply to this message

Warp schrieb:

>   I suppose that would work, at least assuming that a process never releasing
> a resource is not included in the definition of "deadlock".

If you have a process that never releases a resource, then you're 
somewhat screwed anyway...

Post a reply to this message

Warp wrote:
>   So the original claim was not about numbering locks (whatever that might
> mean), but numbering shared resources so that one process can only reserve
> more than one resource at a time in the order dictated by those numbers?

Right. I think probably the term "lock" there meant an individual mutex, or 
whatever structure you're using to keep track of who has which resource. 
I.e., "lock" meant a resource, not a reservation.

>   I suppose that would work, at least assuming that a process never releasing
> a resource is not included in the definition of "deadlock".

As long as the process holding the lock on the resource is not prevented 
from making progress, it's technically not a deadlock. That's why there are 
usually "fairness" criteria in such systems as well, where "fairness" means 
that no process that's ready to run gets delayed indefinitely.

-- 
   Darren New, San Diego CA, USA (PST)
   I ordered stamps from Zazzle that read "Place Stamp Here".

Post a reply to this message

clipka wrote:
> Warp schrieb:
> 
>>   I suppose that would work, at least assuming that a process never 
>> releasing
>> a resource is not included in the definition of "deadlock".
> 
> If you have a process that never releases a resource, then you're 
> somewhat screwed anyway...

Not really. It could be livelock, with all else outside of the resource 
locking/reservation/management subsystem being correct.

-- 
   Darren New, San Diego CA, USA (PST)
   I ordered stamps from Zazzle that read "Place Stamp Here".

Post a reply to this message

Darren New schrieb:

>>>   I suppose that would work, at least assuming that a process never 
>>> releasing
>>> a resource is not included in the definition of "deadlock".
>>
>> If you have a process that never releases a resource, then you're 
>> somewhat screwed anyway...
> 
> Not really. It could be livelock, with all else outside of the resource 
> locking/reservation/management subsystem being correct.

Yes. In this case it's the livelock that screws you. But screwed you are.

However you resolve such a situation, you want /some/ mechanism to make 
sure that processes don't run endless in the first place, not to mention 
doing so with resources locked (unless of course it's a daemon process 
and the only one to use the resource anyway). And if the only mechanism 
in place is a human brain & fingers typing "kill -9 <PID>", you'll still 
want it at any rate.

Post a reply to this message

clipka wrote:
> Darren New schrieb:
> 
>>>>   I suppose that would work, at least assuming that a process never 
>>>> releasing
>>>> a resource is not included in the definition of "deadlock".
>>>
>>> If you have a process that never releases a resource, then you're 
>>> somewhat screwed anyway...
>>
>> Not really. It could be livelock, with all else outside of the 
>> resource locking/reservation/management subsystem being correct.
> 
> Yes. In this case it's the livelock that screws you. But screwed you are.

Sure. I was just pointing out that "livelock" (or any other indefinite 
holding of a lock while not blocked) is not included in the definition of 
"deadlock". :-)

-- 
   Darren New, San Diego CA, USA (PST)
   I ordered stamps from Zazzle that read "Place Stamp Here".

Post a reply to this message