[Tinyos-devel] SimpleArbiterP bug

[Kevin Klues]

Nevermind, I see how your code works.  I'll look into pushing it into
the tree this way in the next couple of days if no one responds saying
they require the existing semantics.

Kevin

On Wed, Oct 15, 2008 at 10:58 AM, Kevin Klues <klueska at gmail.com> wrote:
> 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
>



-- 
~Kevin