Instances of lazy scheduling and timeslice donation in L4 implementations

Espen Skoglund esk at
Tue Jan 24 21:45:29 CET 2006

[Udo A Steinberg]
> On Tue, 24 Jan 2006 20:59:21 +0100 Espen Skoglund (ES) wrote:
ES> This can be argued about.  If high-priority thread B is in no way
ES> penalized by running on a dontated lower priority timeslice for a
ES> while, then it is not necessarily a bad thing.

> I consider B to be penalized if it can be preempted by a thread with
> a lower priority than that of B.

Right.  But if the timeslice donated by A is preemted by a priority
between A and B, then thread B will start its timeslice because it has
the higher priority.

ES> Once the timeslice expires or is preempted, and if thread B is now
ES> eligible to be scheduled then it will continue to run on its own
ES> timeslice with its own priority.

> That way B is not penalized (according to the definition above), but
> there is no clean accounting. Clearly B is handling a request on
> behalf of A - and initially the consumed time is accounted to
> A. After a preemption B continues to run with its own priority and
> consumes its own time. Thus, some or all of the time required to
> handle the request will be accounted to the client, some or none to
> the server. Also you can incur an unnecessary preemption of B (while
> it's running on A's priority) if a thread between A's and B's
> priority is released (admittedly, this is not a common case).

> Imho you want to either account the consumed time completely to the
> client or completely to the server.

You're assuming that B is only performing work on behalf of A.  This
is not necessarily true.  You're also moving into an area where you're
not simply talking about simple timeslice donation anymore.  This is
all fine, but does require a complete redesign of how we do scheduling
in L4.

ES> Now for how things are implemented in Pistachio:
ES> o If send phase finished and there is *no receive phase* the
ES> kernel will donate the timeslice to the destination thread *if*
ES> the destination runs on a higher priority.  If destination does
ES> not run on a higher priority the current thread will contine
ES> executing its own timeslice.

> What is the motivation for donating to the destination thread of a
> send-only IPC if the destination has a higher priority? A pure send
> operation does not establish a dependency between both parties,
> i.e. the caller does not wait for the callee to reply.

Because both source thread and destination thread are now runnable,
and destination thread should run because it has higher priority.
Sure, you may have wanted to skip the timeslice donation here, but we
don't do that for reasons of efficiency.  Also, if destination does
perform work on behalf of sender then timeslice donation is probably
what you want anyway.

ES> o If receive partner is not ready and there was a send phase
ES> (remember send and receive partner may be different) we block and
ES> donate the timeslice to the send partner.

> The receive partner is the party to which you send or from which you
> receive? This is a bit confusing because during request and reply
> the sender and receiver roles of both parties switch.

The receive partner is the thread which you receive from.


More information about the l4-hackers mailing list