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