Adding a new scheduling algorithm to Fiasco.OC

Adam Lackorzynski adam at
Mon Aug 11 23:35:40 CEST 2014


On Thu Aug 07, 2014 at 15:43:20 +0200, Valentin Hauner wrote:
> On 08/05/2014 10:59 PM, Adam Lackorzynski wrote:
> > Anyway, left() tells the generic code how long a
> > thread still has time to run. I think you'll also have a value to put
> > in there, at least it should be known at which point in time a
> > reevaluation of the situation should be done.
> OK, that makes sense. But there's still a problem: The scheduling
> mechanisms in Fiasco.OC (even those that are independent of any concrete
> scheduling algorithm) are timeslice-based, e.g. the method expired() in
> timeslice_timeout.cpp calls the requeue method of the ready queue:
> In the original fixed priority algorithm, the current context is
> requeued and rotated to the end (!) of the queue by the following line
> of code (in ready_queue_fp.cpp):
> > prio_next[i->prio()].rotate_to(*++List::iter(i));
> That makes sense in a timeslice based round robin scheduler, where the
> threads are executed by turns. But it does not make sense for EDF where
> the ready queue has to be sorted by deadlines in ascending order.
> Removing the line mentioned above from my EDF implementation stops the
> execution of the whole system: The last message I see on screen is
> > SIGMA0: Hello!
> Obviously, sigma0 is a regular, periodic task and is scheduled together
> with my example tasks. So no other task than sigma0 comes to execution,
> as no round robin mechanism takes place.
> What's your suggestion to fix this?

I'd assume that the ready queue also has moe because moe should be
ready. Wouldn't, with a requeue, sigma0 moved behind moe now (next
deadline of sigma0 is further away)? On the other side, sigma0 is not
done with that single message, so it also should be continuing
execution. Who's running when the output stops?

> My second question is a short one: How can I pass individual arguments
> for my example tasks to the L4 system, e.g. individual deadlines? Each
> Sched_context object has a deadline attribute that is initialized to a
> default value at the moment.
> The following LUA script starts the two tasks hello1 and hello2:
> >-- Include L4 functionality
> >require("L4");
> >
> >-- Some shortcut for less typing
> >local l = L4.default_loader;
> >
> >l:start({ caps = { },
> >           log = { "hello1", "blue" } },
> >         "rom/hello1");
> >
> >l:start({ caps = { },
> >           log = { "hello2", "green" } },
> >         "rom/hello2");
> Where can I pass my deadlines here?

You add
 l:start({ ..., 
           scheduler = L4.Env.user_factory:create(L4.Proto.Scheduler, ...),
         }, ...)
For the fixed-prio type, we add two numbers, giving upper limit and base
 (e.g. L4.Env.user_factory:create(L4.Proto.Scheduler, 10, 5). However,
for using this in the lua scripting, you also need to adapt libkproxy.
So for the start, I'd suggest you use the C/C++ interface and reconfig
the main thread from the defaults just in your program.

In your case, the numbers used have a different meaning of course.
Passing them down to the kernel goes via Scheduler::run_thread. There's
some support for different scheduling parameters in the kernel, you've
probably seen 'union Sp'. You can probably squeeze it in there.

Adam                 adam at

More information about the l4-hackers mailing list