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