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