![](/i/fill.gif) |
![](/i/fill.gif) |
|
![](/i/fill.gif) |
|
![](/i/fill.gif) |
| ![](/i/fill.gif) |
| ![](/i/fill.gif) |
|
![](/i/fill.gif) |
|
![](/i/fill.gif) |
| ![](/i/fill.gif) |
| ![](/i/fill.gif) |
|
![](/i/fill.gif) |
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/fill.gif) |
| ![](/i/fill.gif) |
| ![](/i/fill.gif) |
|
![](/i/fill.gif) |
|
![](/i/fill.gif) |
| ![](/i/fill.gif) |
| ![](/i/fill.gif) |
|
![](/i/fill.gif) |
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
|
![](/i/fill.gif) |
| ![](/i/fill.gif) |
| ![](/i/fill.gif) |
|
![](/i/fill.gif) |
|
![](/i/fill.gif) |
| ![](/i/fill.gif) |
| ![](/i/fill.gif) |
|
![](/i/fill.gif) |
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
|
![](/i/fill.gif) |
| ![](/i/fill.gif) |
| ![](/i/fill.gif) |
|
![](/i/fill.gif) |
|
![](/i/fill.gif) |
| ![](/i/fill.gif) |
| ![](/i/fill.gif) |
|
![](/i/fill.gif) |
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
|
![](/i/fill.gif) |
| ![](/i/fill.gif) |
| ![](/i/fill.gif) |
|
![](/i/fill.gif) |
|
![](/i/fill.gif) |
| ![](/i/fill.gif) |
| ![](/i/fill.gif) |
|
![](/i/fill.gif) |
>>> 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
|
![](/i/fill.gif) |
| ![](/i/fill.gif) |
| ![](/i/fill.gif) |
|
![](/i/fill.gif) |
|
![](/i/fill.gif) |
| ![](/i/fill.gif) |
| ![](/i/fill.gif) |
|
![](/i/fill.gif) |
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
|
![](/i/fill.gif) |
| ![](/i/fill.gif) |
| ![](/i/fill.gif) |
|
![](/i/fill.gif) |
|
![](/i/fill.gif) |
| ![](/i/fill.gif) |
| ![](/i/fill.gif) |
|
![](/i/fill.gif) |
> 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/fill.gif) |
| ![](/i/fill.gif) |
| ![](/i/fill.gif) |
|
![](/i/fill.gif) |
|
![](/i/fill.gif) |
| ![](/i/fill.gif) |
| ![](/i/fill.gif) |
|
![](/i/fill.gif) |
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
|
![](/i/fill.gif) |
| ![](/i/fill.gif) |
| ![](/i/fill.gif) |
|
![](/i/fill.gif) |
|
![](/i/fill.gif) |
| ![](/i/fill.gif) |
| ![](/i/fill.gif) |
|
![](/i/fill.gif) |
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
|
![](/i/fill.gif) |
| ![](/i/fill.gif) |
| ![](/i/fill.gif) |
|
![](/i/fill.gif) |
|
![](/i/fill.gif) |
| ![](/i/fill.gif) |
| ![](/i/fill.gif) |
|
![](/i/fill.gif) |
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
|
![](/i/fill.gif) |
| ![](/i/fill.gif) |
| ![](/i/fill.gif) |
|
![](/i/fill.gif) |
|
![](/i/fill.gif) |
| ![](/i/fill.gif) |