lkml.org 
[lkml]   [1999]   [Jan]   [12]   [last100]   RSS Feed
Views: [wrap][no wrap]   [headers]  [forward] 
 
Messages in this thread
/
From
SubjectRe: MM deadlock [was: Re: arca-vm-8...]
Date
"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/

\
 
 \ /
  Last update: 2005-03-22 13:49    [W:0.060 / U:0.432 seconds]
©2003-2020 Jasper Spaans|hosted at Digital Ocean and TransIP|Read the blog|Advertise on this site