|
|
|
|
|
|
| |
| |
|
|
|
|
| |
| |
|
|
Warp wrote:
> 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?
Because, if every process always reversed resources in ascending order,
then both processes above will attempt to reverse resource 1 and then
resource 2, in that order. In the above example, deadlock occurs exactly
because the first process tries to get resource 1 and then resource 2,
but the other process tries to get resource 2 and then resource 1
(descending order).
--
http://blog.orphi.me.uk/
http://www.zazzle.com/MathematicalOrchid*
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
Paul Fuller wrote:
> As to references, Wikipedia 'Deadlock' article is a decent starting
> point. Many more erudite references are given there.
Ooo... Wikipedia claims you're supposed to also release resources in
descending order. I didn't know that. o_O
--
http://blog.orphi.me.uk/
http://www.zazzle.com/MathematicalOrchid*
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
clipka wrote:
> 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.
I misunderstood your reference to "this locking concept".
--
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:
> I guess timing out on acquiring a lock would constitute a variant of 2)
> in theory, right?
Yes. In that case, you're not "holding" the locks, as you'll release them to
prevent a deadlock.
> Also note that 3) only works to prevent deadlocks if acquiring multiple
> locks at once is an atomic operation.
Yes, that's the idea. It's pretty simple to set up an atomic-lock mechanism
if you have a complete list of all possible locks up front.
--
Darren New, San Diego CA, USA (PST)
I ordered stamps from Zazzle that read "Place Stamp Here".
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
Orchid XP v8 wrote:
> Although... how is #4 different from #2?
#4 is only having a lock on one item at a time. #2 means you can have
multiple locks, you just can't *wait* on a lock if you already have another
lock.
They all sound pretty similar, and boil down to "don't cause conflicts
without resolving it." You can avoid causing it (by only locking one thing,
or locking in order) or you can resolve it (by freeing locks when you get a
deadlock).
> Anyway, do you have a citable reference for this stuff? (I'm guessing
> Dijkstra, Knuth, or somebody must have written about this...)
Uh, probably somewhere, but not off the top of my head, no.
--
Darren New, San Diego CA, USA (PST)
I ordered stamps from Zazzle that read "Place Stamp Here".
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
Orchid XP v8 <voi### [at] devnull> wrote:
> Because, if every process always reversed resources in ascending order,
Reversed?
> then both processes above will attempt to reverse resource 1 and then
> resource 2, in that order. In the above example, deadlock occurs exactly
> because the first process tries to get resource 1 and then resource 2,
> but the other process tries to get resource 2 and then resource 1
> (descending order).
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.
Anyways, you were talking about ordering IDs of *locks*, not ordering
resources. I still can't understand what you are talking about.
--
- Warp
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
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
|
|
| |
| |
|
|
|
|
| |
| |
|
|
Darren New <dne### [at] sanrrcom> wrote:
> 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.
So the original claim was not about numbering locks (whatever that might
mean), but numbering shared resources so that one process can only reserve
more than one resource at a time in the order dictated by those numbers?
I suppose that would work, at least assuming that a process never releasing
a resource is not included in the definition of "deadlock".
--
- Warp
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
Warp schrieb:
> I suppose that would work, at least assuming that a process never releasing
> a resource is not included in the definition of "deadlock".
If you have a process that never releases a resource, then you're
somewhat screwed anyway...
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
Warp wrote:
> So the original claim was not about numbering locks (whatever that might
> mean), but numbering shared resources so that one process can only reserve
> more than one resource at a time in the order dictated by those numbers?
Right. I think probably the term "lock" there meant an individual mutex, or
whatever structure you're using to keep track of who has which resource.
I.e., "lock" meant a resource, not a reservation.
> I suppose that would work, at least assuming that a process never releasing
> a resource is not included in the definition of "deadlock".
As long as the process holding the lock on the resource is not prevented
from making progress, it's technically not a deadlock. That's why there are
usually "fairness" criteria in such systems as well, where "fairness" means
that no process that's ready to run gets delayed indefinitely.
--
Darren New, San Diego CA, USA (PST)
I ordered stamps from Zazzle that read "Place Stamp Here".
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
|
|