Messages in this thread | | | From | "Peter T. Breuer" <> | Subject | Re: MM deadlock [was: Re: arca-vm-8...] | Date | Tue, 12 Jan 1999 16:29:03 +0100 (MET) |
| |
"A month of sundays ago Tom Eastep wrote:" > Linus Torvalds wrote: > > "owner" is P#1, count=1 > > > > down() down() > > lock ; decl succeeds > > > > lock ; decl fails > > goto slow part > > slow part sees stale owner > > returns success > > > > "owner" is P#2 > > > > BOOM! - both CPU's are now inside the critical region.
I need to know what semantics "owner" is supposed to have ... you can release (up?) your own semaphore twice but nobody else can release yours a second time even when it's free? You can take (down) your own semaphore even when it is not available? Or the opposite.
No. The only sense that the word recursive makes to me as applied to semaphores is that you want to not block when trying to take your own semaphore a second time. I.e. it should block everybody else but you. That allows you to reenter your own semaphore, once you've got it. I suppose also that an available semaphore belongs to nobody (it's been released). But I still don't see how signalling the semaphore several times by different people can be squared with any theoretical concept. Oh well .. that's the spec. I asked for. What does one want here?
Here's doing it in complete safety using pure semaphores. That seems to require two semaphores. That's a
assert: sem.owner != nobody -> sem.count < 0 sem_owner.count == 0 -> sem.owner == nobody
new_P(sem) = P(owner_sem) if sem.owner== me // implies sem.count < 0 then sem.count--; // safe - we have it, take it again V(owner_sem);// release lock on owner field else V(owner_sem); P(sem); // wait our turn /* Needs more control? See below */ P(owner_sem);// lock owner field sem.owner = me; V(owner_sem);// release owner field
After getting the semaphore, we have to wait also to get control of the owner field. Then we change it and let other people look at it again. What worries me is that while we're waiting for the owner field, somebody else might grab it. If they were the previous owner then they might think they had the semaphore still and decrement the count. The best way to make sure that the previous owner doesn't ever think it's still his is to religiously clear the owner field whenever the semaphore is released.
new_V(sem) = P(owner_sem); if sem.owner== me then V(sem); if sem.count == 0 then sem.owner = nobody; else // I don't know what you want spec'ed here, say .. // can I signal the resource is free while someone else // has it? Or only if nobody has it? V(sem); // for example V(owner_sem);
> > up(sem) { > > if (!sem.count) > > sem.owner = 0;
Well. You're trying to set the owner to nobody as you go up through zero on the semaphore count, as I did. It's not protected at this point, however. So two people can get as far as this. But, they both do the same thing if they do it at the same time, so that's OK.
> > old_up();
That must be atomic. It is.
> > } > > > > but I can't convince myself that that always works either.
I don't know what the spec is that you want. It's safe against contrary writes, if that's what you mean. But what should happen when two different people signal to the same (available) semaphore?
> The way I've implemented this in the past is to make the recursive > semaphore a 3-tuple: > > ( old_semaphore , owner, owner_count ) where owner and owner_count > are initially zero. > > down() { > if ( owner == current ) {
Well, this test is not protected, but it doesn't change itself, so OK.
> owner_count++;
This supposed that owner_count = 0 was impossible if owner = current? What's it counting, anyway?
> return;
You don't decrement the signal count? This is a very binary semaphore!
> } > old_down();
i.e. wait to decrement count only if it was not our semaphore. You now got it ..
> owner = current; > owner_count = 1;
OK. You got the semaphore so you can do what you like with it. Why is owner_count set to 1? What is this variable? It looks to be the number of times we've waited on the same semaphore.
> } > > up() { > if ( ! --owner_count ) {
Hoooo. That's a set and test :-). If we're due to release ...
> owner = 0; > old_up();
... we release. I like it.
> } > > -Tom > -- > Tom Eastep > Compaq Computer Corporation > Enterprise Computing Group > Tandem Division > tom.eastep@compaq.com
I can run simulations are trace these abstractions, if anyone likes. I'm a little wary of tom's solution, although it looks good to the eye.
Peter
- To unsubscribe from this list: send the line "unsubscribe linux-kernel" in the body of a message to majordomo@vger.rutgers.edu Please read the FAQ at http://www.tux.org/lkml/
| |