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