On Fri, 20 Jan 2006 23:18:28 +1100 (EST) Gernot Heiser (GH) wrote:

GH> Note that the Inside L4 document refers to the old MIPS kernel, which GH> is one implementation of (and extended) V2 API. GH> GH> It also, like many other implementations, does time-slice donation GH> incorrectly (i.e. blindly). Time-slice donation should respect GH> priorities. I believe that this is fixed in NICTA::Pistachio-embedded, GH> but the code is the ultimate reference ;-)

Also note that time-slice donation on L4 typically does not extend across preemptions. A client that performs an RPC to a server donates its time quantum and priority to the server - this is achieved by switching only the execution context during the IPC and leaving the scheduling parameters of the client "in place". However, if the RPC is preempted by a higher- priority thread and is later resumed, the server will continue executing using its own time and priority instead of using the client's time and priority.

To my knowledge no existing L4 implementation correctly resumes the original donation after a preemption. A solution has been described in [1], but we at TUD have not implemented it yet.

- Udo

[1] http://doi.ieeecomputersociety.org/10.1109/ECRTS.2005.16

Gernot Heiser wrote:

...

...

...

...

...

On Fri, 20 Jan 2006 14:04:03 +0100, "Udo A. Steinberg" us15@os.inf.tu-dresden.de said:

You imply that donation across preemptions is the "correct" behaviour. This is at least debated. In fact, the original motivation is not at all to donate a time slice, but to do lazy scheduling,

A different slant on 'proper' timeslice donation.

Situation:

Thread A has a 'very long' timeslice (set by L4_Schedule()), and is currently running on the CPU.

Thread B has a standard timeslice, is active (ready), but not running, not because is blocked on IPC, but just because it has a priority lower than A.

Thread A ... L4_ThreadSwitch ( Thread B ); ...

According to these L4 specifications:

http://l4hq.org/docs/manuals/l4-x2-20051021.pdf http://www.ertos.nicta.com.au/software/kenge/pistachio/latest/refman.pdf

-------------------------------------------------------- THREADSWITCH [Systemcall] The invoking thread releases the processor (non-preemptively) so that another ready thread can be processed.

Input Parameter

1) dest == nilthread Processing switches to an undefined ready thread which is selected by the scheduler. (It might be the invoking thread.) Since this is “ordinary” scheduling, the thread gets a new timeslice.

2) dest != nilthread If dest is ready, processing switches to this thread. In this “extraordinary” scheduling, the invoking thread donates its remaining timeslice to the destination thread. (This one gets the donation in addition to its ordinarily scheduled timeslices, if any.) ... --------------------------------------------------------

Since the correctness of some software I am writing may end relying on the behaviour _specified_ at point 2) above, I have the following Q:

Do L4 implementations _really_ honour case 2) ? In other words, will Thread B run as long as prescribed by Thread A timeslice ?

Local experts believe that current L4 implementation(s) do not conform to specification, and Thread B will run only until the next timertick.

Comments ?

Sergio

Udo A. Steinberg wrote:

On Tue, 24 Jan 2006 16:00:24 +1100 Sergio Ruocco (SR) wrote: SR> Local experts believe that current L4 implementation(s) do not conform SR> to specification, and Thread B will run only until the next timertick.

Your local experts are correct. In the L4 implementations that I know of B will only run on A's time slice until a higher-priority thread preempts B. I think this is what you meant by "next timer tick" (but note that the next timer tick may wake up a lower-priority thread which does not preempt B - therefore, preemption is what ultimately breaks the donation, not the timer tick per se).

Local experts said 'timertick', but they were busy with other things, so we may want to take a close look at the source and/or ask what they meant exactly. I also found the answer 'timertick' a bit strange, as I would expect donation to be terminated only by:

1) natural end of augmented timeslice 2) preemption by higher-priority thread

Btw., this is the exact same issue as the IPC donation we discussed a few days ago - the kernel does not maintain enough information to restore the donation to B when A's time slice is selected by the scheduler again. - Udo

On the one hand, remember that according to the specification the part of timeslice that A donated to B via L4_ThreadSwitch() *adds* to B's natural timeslice, so the kernel should have provision for this donation-preserving behaviour. Again, a close look to the source seems necessary.

On the other hand, as Gernot pointed out, A's timeslice donation to B when A IPCs to B is simply a *side* *effect* of lazy scheduling, a speed optimisation that avoids to run the scheduler in the IPC path. Being the timeslice donation a mere side-effect, actively carrying it over across preemptions may probably not be the required behaviour.

Sergio

[Udo A Steinberg]

The "side effect" of L4 IPC only implements desired donation behavior in the case when a high-priority thread A calls a low-priority thread B. In that case B will be boosted to A's priority and priority inversion is avoided. However, if A has the lower priority and calls a high-priority thread B, then A effectively drags B down to its priority level, which is imho not desired. In that case the IPC implementation should switch to B's scheduling parameters or boost the priority of A's time quantum to the priority of B for the duration of the IPC.

This can be argued about. If high-priority thread B is in no way penalized by running on a dontated lower priority timeslice for a while, then it is not necessarily a bad thing. Once the timeslice expires or is preempted, and if thread B is now eligible to be scheduled then it will continue to run on its own timeslice with its own priority.

Now for how things are implemented in Pistachio:

o If send phase finished and there is *no receive phase* the kernel will donate the timeslice to the destination thread *if* the destination runs on a higher priority. If destination does not run on a higher priority the current thread will contine executing its own timeslice.

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

o When the receive IPC copy operation occurs we switch to the receive partner (the IPC copy operation always happens in the context of the sender) if it has a higher priority than the send partner. Otherwise we switch to the send partner. Again, timeslice donation occurs.

o After the receive phase has finished the scheduling is decided upon by the party doing the last send operation (see the two first bullets above).

Hope this clears up a few things regarding the Pistachio implementation. Note that this is pretty much just from the top of my head, though. There might be some slight differences in the actual implementation. Also note that other things such as delayed preemtion also complicate these scheduling decisions.

eSk

[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> 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.

eSk

On Wed, 25 Jan 2006 12:01:22 +1100 Sergio Ruocco (SR) wrote:

SR> Beware that Quantum and Timeslice are not the same thing. Quantum is the SR> amount of execution time after which the thread scheduler receives an SR> RPC. After the RPC the Quantum is re-initialised to the value of SR> thread's TimeSlice, but the thread scheduler is free to set it to any SR> value, including oo, independently from timeslice. SR> SR> So, to avoid confusion, let's keep Quantum outside of this discussion.

We are using conflicting terminology here. What I refer to as a time slice or scheduling context is a time quantum Q coupled with a priority P. A thread with such a time slice can run with priority P for Q units of time.

SR> No. I think that with IPC Lazy Scheduling B does not get a priority SR> boost, but only to run for the remaining part of A timeslice. This is SR> not the same as B running with A priority.

I guess it is implementation-dependent. In our Fiasco kernel there is a strict distinction between time slices and execution contexts. During an IPC with lazy scheduling the kernel switches execution contexts but not time slices. This means that both A's priority and time quantum remain in effect - and thus B runs with A's priority and consumes A's time quantum until the time quantum is depleted and a new time slice is selected by the scheduler.

SR> In fact, as soon as a thread C of intermediate priority between A and B SR> is ready to run, it immediately preempts B, because B was running on A's SR> timeslice, not on A's priority.

Not in our kernel. An intermediate thread C can be woken up but it cannot preempt B as long as A's time slice hasn't run out.

SR> What do mean with the "priority of A's time quantum" ??

In our model every time quantum is coupled with a priority. If it doesn't become clear from the description above I can elaborate some more.

- Udo

[Sergio Ruocco]

2. dest != nilthread

If dest is ready, processing switches to this thread. In this “extraordinary” scheduling, the invoking thread donates its remaining timeslice to the destination thread. (This one gets the donation in addition to its ordinarily scheduled timeslices, if any.) ...

---

Since the correctness of some software I am writing may end relying on the behaviour _specified_ at point 2) above, I have the following Q:

Do L4 implementations _really_ honour case 2) ? In other words, will Thread B run as long as prescribed by Thread A timeslice ?

Local experts believe that current L4 implementation(s) do not conform to specification, and Thread B will run only until the next timertick.

Comments ?

Speaking for the Pistachio implementation: The time is accounted to the thread who currently "owns" the timeslice (thread A in this case). Each time a timer tick occurs, and there are no preemptions by higher priority threads, thread B will run on the time donated by thread A. This is according to the spec. Once the timeslice expires a new scheduling decision is made. This may or may not cause thread B to continue running (depending on priorities, scheduling queues, etc.). The "in addition to its ordinarily scheduled timeslices" in the spec does not imply that it will also be the next thread scheduled. It merely means that the time it was donated is not accounted to its own timeslices.

eSk

[Udo A Steinberg]

On Tue, 24 Jan 2006 19:54:29 +0100 Espen Skoglund (ES) wrote:

ES> Speaking for the Pistachio implementation: The time is accounted to ES> the thread who currently "owns" the timeslice (thread A in this case). ES> Each time a timer tick occurs, and there are no preemptions by higher ES> priority threads, thread B will run on the time donated by thread A. ES> This is according to the spec.

So far all is clear.

ES> Once the timeslice expires a new ES> scheduling decision is made. This may or may not cause thread B to ES> continue running (depending on priorities, scheduling queues, etc.).

This is also clear.

The tricky case is as follows:

1. A performs a thread_switch syscall, donating its time slice to B
2. B executes and consumes part of A's time (but not all)
3. B is preempted by a higher-priority thread H
4. H blocks

How does B get to consume the remainder of A's time slice, i.e. the part that it did not use up in 2) ?

Sorry for not being precise enough here. True, if preemted while running on the donated timeslice the remainder of the timeslice will no longer be donated. One could think of a scheme that maintained the timeslice donation state across such preemptions. One might even come up with a solution that does not require any modifications on the fast IPC path. It would complicate the scheduling code a little, though. How this would affect the scheduler performance I can not tell.

eSk

On Wed, 25 Jan 2006 11:09:09 +1100 Kevin Elphinstone (KE) wrote:

KE> * System-level priority ceiling protocol (static assignment of KE> priorities) with priority preserving lazy scheduling, i.e. lazy switch KE> only happens if destination is (equal) highest priority thread. KE> KE> - I beleive we have something that approximates this at NICTA, maybe KE> dresden has this also.

I don't believe we have something like this in Dresden or I'm not understanding why lazy switching should be done only if destination is equal highest-priority thread in this case.

KE> * system-level priority inheritance (or call it persistent time-slice KE> donation if you wish), this is what I believe dresden is talking about, KE> has proposed, and I gather have not implemented. It requires tracking of KE> dependencies of IPC in some manner.

The proposed mechanism can do priority inheritance and stack-based priority ceiling on top of L4 with some tracking added to the IPC path.

KE> My point, everybody is "correct" depending on what you are KE> doing/expecting at the system level.

Sure.

KE> So rather than argue over details of how lazy-scheduling "should" or KE> does behave, one should have a clear idea of what is required at the KE> system level, and what model of the three above is required (or maybe an KE> alternative), or maybe an existing model with restrictions on what one KE> can do.

There has been no argument but rather a discussion of issues that exist in the current L4 implementations. Whether these issues matter in a particular system design is entirely dependent on what your real-time requirements are or rather, whether you have any.

I know these issues have been debated to death in the past and to some of us the implications are pretty clear - but I didn't start this thread ;)

- Udo