 |
|
|
|
|
|
| |
| |
|
|
|
|
| |
| |
|
|
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] dev null> 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
|
|
| |
| |
|
|
|
|
| |
| |
|
|
clipka wrote:
> 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...
Not really. It could be livelock, with all else outside of the resource
locking/reservation/management subsystem being correct.
--
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 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...
>
> Not really. It could be livelock, with all else outside of the resource
> locking/reservation/management subsystem being correct.
Yes. In this case it's the livelock that screws you. But screwed you are.
However you resolve such a situation, you want /some/ mechanism to make
sure that processes don't run endless in the first place, not to mention
doing so with resources locked (unless of course it's a daemon process
and the only one to use the resource anyway). And if the only mechanism
in place is a human brain & fingers typing "kill -9 <PID>", you'll still
want it at any rate.
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
clipka wrote:
> Darren New 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...
>>
>> Not really. It could be livelock, with all else outside of the
>> resource locking/reservation/management subsystem being correct.
>
> Yes. In this case it's the livelock that screws you. But screwed you are.
Sure. I was just pointing out that "livelock" (or any other indefinite
holding of a lock while not blocked) is not included in the definition of
"deadlock". :-)
--
Darren New, San Diego CA, USA (PST)
I ordered stamps from Zazzle that read "Place Stamp Here".
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
|
|
