Tickles scheduler

Tickles scheduler

[Dragoslav Zaric]

Did anybody test and compare work of ticking and tickles scheduler ?

Currently I think it is implemented as ticking scheduler with
hard-coded frequency (usually 100 Hz).

Personally I think that tickles scheduler is much better solution, but
maybe I am over-view something and
maybe there are side effects when implementation starts ? Instead of
tick, we can wait for events to happen
(for example IRQ, add or remove process from list), and when periodic
actions are needed, we can time
schedule them dynamically based on system load.

Can somebody give me some insight in this issue if he has any
experience with this ?

Is it at all possible to implement kernel without ticking, spin system
by events and periods ?
Maybe ticking is still best solution to have fast responding system ?

Kind regards

-- 
Dragoslav Zaric

Professional Programmer
MSc Astrophysics

Re: Tickles scheduler

[Martin Nybo Andersen]

On Tue, 26 Oct 2010, Dragoslav Zaric wrote:

> [...]
>
> Is it at all possible to implement kernel without ticking, spin system
> by events and periods ?

You can compile with CONFIG_NO_HZ=n if you want a ticking kernel.

> Maybe ticking is still best solution to have fast responding system ?

My guesses are that it has already been benchmarked for speed, but you can 
still test it yourself.
At least power usage/battery times is much better with a tickless kernel.

> Kind regards
>
> -- 
> Dragoslav Zaric

-- 
Regards,
Martin

Re: Tickles scheduler

[Christoph Lameter]

On Tue, 26 Oct 2010, Martin Nybo Andersen wrote:

> On Tue, 26 Oct 2010, Dragoslav Zaric wrote:
>
> > [...]
> >
> > Is it at all possible to implement kernel without ticking, spin system
> > by events and periods ?
>
> You can compile with CONFIG_NO_HZ=n if you want a ticking kernel.

The kernel always ticks when a process is running CONFIG_NO_HZ does
nothing for that.

> > Maybe ticking is still best solution to have fast responding system ?

I think we need a tickless kernel.... Yes....

> My guesses are that it has already been benchmarked for speed, but you can
> still test it yourself.
> At least power usage/battery times is much better with a tickless kernel.

Well yes CONFIG_NO_HZ really should say CONFIG_NO_HZ_IDLE. You have
no ticks when a cpu is idle. Otherwise we are ticking...

Re: Tickles scheduler

[Dragoslav Zaric]

1.Currently processes in the system are in some kind of list I think
(double circular).
So what if we assign each process structure (task_struct) property for
priority (maybe already there)
and another property which is time how long should run. So instead
having ticker in system,
each process runs itself predetermined period of time based on
priority and probably few more
parameters that should be in algorithm.

2. Second, when adding process into list, we can have separate side
lists, created in advance (something
like slab), where each lists hold tasks of same priority. So when we
add new process to list, at same
time we add it to his priority list. Than scheduler goes trough these
lists, based on priority and each
tasks hold it's running time. So we have two points to ease algorithm,
lists with single priority and time inside
each process task_struct related to priority.

3. In this way time-granularity of the system is high and allows for
real-time behavior, because we do
not have outside time that we "cut" in the middle when interrupt
happens, we just interrupt current process and when
finished, scheduler continue to walk trough lists of processes that
run its own time.

regards

On Thu, Oct 28, 2010 at 2:26 AM, Christoph Lameter <cl@linux.com> wrote:
> On Tue, 26 Oct 2010, Martin Nybo Andersen wrote:
>
>> On Tue, 26 Oct 2010, Dragoslav Zaric wrote:
>>
>> > [...]
>> >
>> > Is it at all possible to implement kernel without ticking, spin system
>> > by events and periods ?
>>
>> You can compile with CONFIG_NO_HZ=n if you want a ticking kernel.
>
> The kernel always ticks when a process is running CONFIG_NO_HZ does
> nothing for that.
>
>> > Maybe ticking is still best solution to have fast responding system ?
>
> I think we need a tickless kernel.... Yes....
>
>> My guesses are that it has already been benchmarked for speed, but you can
>> still test it yourself.
>> At least power usage/battery times is much better with a tickless kernel.
>
> Well yes CONFIG_NO_HZ really should say CONFIG_NO_HZ_IDLE. You have
> no ticks when a cpu is idle. Otherwise we are ticking...
>
>



-- 
Dragoslav Zaric

Professional Programmer
MSc Astrophysics

Re: Tickles scheduler

[Christoph Lameter]

The current plan is to switch off the tick when a process is running that
cannot be preempted ("realtime" (very bad choice of terms) tasks).

Re: Tickles scheduler

[Mark Hounschell]

On 10/28/2010 09:47 AM, Christoph Lameter wrote:
> The current plan is to switch off the tick when a process is running that
> cannot be preempted ("realtime" (very bad choice of terms) tasks).
> 

In what kind of time frame is this plan? And in the plan what will be the criteria for
"cannot be preempted"?

Thanks
Mark

Re: Tickles scheduler

[Christoph Lameter]

On Thu, 28 Oct 2010, Mark Hounschell wrote:

> On 10/28/2010 09:47 AM, Christoph Lameter wrote:
> > The current plan is to switch off the tick when a process is running that
> > cannot be preempted ("realtime" (very bad choice of terms) tasks).
> >
>
> In what kind of time frame is this plan? And in the plan what will be the criteria for
> "cannot be preempted"?

Time frame is dependent on my available time unless someone else steps
forward to help out. The criteria for "cannot be preempted" could be
initially a process running with SCHED_FIFO.