[Tinyos-devel] SimpleArbiterP bug

[Kevin Klues]

I agree this is a bug and should be changed if no one is relying on
the existing semantics.  That said, your proposed solution only seems
to cover the case where we are signaling Resource.requested() to the
resource default owner.  In general it can be singaled to any user
that currently owns the resource and will probably require a more
general solution.  I'll take a look into this soon.

Kevin

On Wed, Oct 15, 2008 at 10:29 AM, Philip Levis <pal at cs.stanford.edu> wrote:
> I think this is a bug in SimpleArbiterP, but wanted to check with
> everyone to make sure. In particular, whether there are existing
> systems which depend on the current behavior, such that fixing it
> would break them.
>
> A bit of background: arbiters (power locks) are built around
> SimpleArbiterP. SimpleArbiterP uses a queue interface, and the
> implementation of that queue interface controls its locking policy
> (e.g., First-come, first-served vs. round-robin).
>
> The test case is as follows. I'm using indentation to show the call
> graph. E.g., 2a is called on 2's stack frame.
>
> 1. Client A requests and acquires power lock P
> 2. Client B requests power lock P
> 2a.  P signals to Client A that the lock has been requested
> 2aa.   Client A releases P
> 2ab.   Client A re-requests P
>
> In this case, I think that P should grant to B; 2aa and 2ab are a
> yield from A. When B releases the lock, A will re-acquire it. However,
> the request code looks like this (immediateRequest is similar):
>
>   async command error_t Resource.request[uint8_t id]() {
>     signal ResourceRequested.requested[resId]();
>     atomic {
>       if(state == RES_CONTROLLED) {
>         state = RES_GRANTING;
>         reqResId = id;
>       }
>       else return call Queue.enqueue(id);
>     }
>     signal ResourceDefaultOwner.requested();
>     return SUCCESS;
>   }
>
> Because requested() is signaled before the caller's request is put on
> the queue, then in the case above, this is what happens:
>
> 1. Client A requests and acquires power lock P
> 2. Client B requests power lock P
> 2a.  P signals to Client A that the lock has been requested
> 2aa.   Client A releases P
> 2ab.   Client A re-requests P
> 2aba.    P puts A at head of queue
> 2abb.    P posts a task to grant A the lock
> 2b.  P puts B on queue
> ....
> 3. A re-acquires lock, while B is waiting on queue
>
> I think the code should be this:
>
>   async command error_t Resource.request[uint8_t id]() {
>     bool getsNow = TRUE;
>     atomic {
>       if(state == RES_CONTROLLED) {
>         state = RES_GRANTING;
>         reqResId = id;
>         getsNow = FALSE;
>       }
>     }
>     if (getsNow == FALSE) {
>       error_t rval = call Queue.enqueue(id);
>       signal ResourceRequested.requested[resId]();
>       return rval;
>     }
>     else {
>       signal ResourceDefaultOwner.requested();
>       return SUCCESS;
>     }
>   }
>
> Thoughts?
>
> Phil
>
>
> _______________________________________________
> Tinyos-devel mailing list
> Tinyos-devel at millennium.berkeley.edu
> https://www.millennium.berkeley.edu/cgi-bin/mailman/listinfo/tinyos-devel
>



-- 
~Kevin