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