adaptive scheduling

Can we expect adaptive scheduling soon?

  • Mario

Previously, Armin Steinhoff wrote in qdn.public.qnxrtp.os:

An ‘adaptive’ scheduler or a scheduler which does ‘adaptive
scheduling’ ??

Can you explain the difference?

Would be nice to see at first the ‘simple’ things like adjustable
time slices and more than 64 priorities

I’ve heard a few people say they’d like to see that. I’m curious -
why do we need more than 64 priorities? I don’t even run 64 threads
total on a typical installation.

We use the adjustable time slice in QNX4 solely for timer resolution.
Does NTO have a different mechanism so that timer resolution is not
tied to time slice? If time slice and timer resolution are tied
together, adjustable time slice sounds like an absolute necessity.

Cheers,
Andrew

Mario Charest <mcharest@antispam_zinformatic.com> wrote:

Can we expect adaptive scheduling soon?

The next item on my personal todo list involves
implementing a more adaptive scheduler.

Your comments on this topic can be directed to
me for now.

Thomas

Thomas Fletcher wrote:

Mario Charest <mcharest@antispam_zinformatic.com> wrote:

Can we expect adaptive scheduling soon?

The next item on my personal todo list involves
implementing a more adaptive scheduler.

Your comments on this topic can be directed to
me for now.

May I ? :slight_smile:
I think timeslice should be adjustable. Or at least make the
‘multiplication factor’ for which is currently ‘4’ adjustable (I mean
timeslice = ClockPeriod * 4).

  • igor

Thomas Fletcher wrote:

Mario Charest <mcharest@antispam_zinformatic.com> wrote:

Can we expect adaptive scheduling soon?

The next item on my personal todo list involves
implementing a more adaptive scheduler.

An ‘adaptive’ scheduler or a scheduler which does ‘adaptive
scheduling’ ??

Would be nice to see at first the ‘simple’ things like adjustable
time slices and more than
64 priorities

Armin

Your comments on this topic can be directed to
me for now.

Thomas

May I suggest that it simply be the same algorithm as in QNX4.
The adaptive scheduling in QNX4 worked great.

-----Original Message-----
From: Thomas Fletcher [mailto:thomasf@qnx.com]
Posted At: Monday, February 19, 2001 12:25 PM
Posted To: os
Conversation: adaptive scheduling
Subject: Re: adaptive scheduling


Mario Charest <mcharest@antispam_zinformatic.com> wrote:

Can we expect adaptive scheduling soon?

The next item on my personal todo list involves
implementing a more adaptive scheduler.

Your comments on this topic can be directed to
me for now.

Thomas

Andrew Thomas wrote:

Previously, Armin Steinhoff wrote in qdn.public.qnxrtp.os:
An ‘adaptive’ scheduler or a scheduler which does ‘adaptive
scheduling’ ??

Can you explain the difference?

I’ll leave that pleasure to Armin.

Would be nice to see at first the ‘simple’ things like adjustable
time slices and more than 64 priorities

I’ve heard a few people say they’d like to see that. I’m curious -
why do we need more than 64 priorities? I don’t even run 64 threads
total on a typical installation.

If you try to apply some science to assigning priorities to your
threads, you may end up needing more than 64. Theoretically you might
need a unique priority for each thread.

By the way, we have over 100 threads in just one of our processes.

We use the adjustable time slice in QNX4 solely for timer resolution.
Does NTO have a different mechanism so that timer resolution is not
tied to time slice? If time slice and timer resolution are tied
together, adjustable time slice sounds like an absolute necessity.

As I said already, TimeSlice = 4 * ClockPeriod.

  • igor

Igor Kovalenko wrote:

Andrew Thomas wrote:

Previously, Armin Steinhoff wrote in qdn.public.qnxrtp.os:
An ‘adaptive’ scheduler or a scheduler which does ‘adaptive
scheduling’ ??

Can you explain the difference?


I’ll leave that pleasure to Armin.

Thank you :slight_smile:

IMHO … an adaptive scheduler is a scheduler which allows the
modification of its static scheduling parameters … e.g. the
duration of the timeslice (SCHED_RR).

Adaptive scheduling is a scheduling discipline which deals e.g with
dynamic system states like overload situation, timeliness, deadlines
specific algorithmn and many other aspects … so it is a little bit
more than SCHED_OTHER :slight_smile:

Would be nice to see at first the ‘simple’ things like adjustable
time slices and more than 64 priorities

I’ve heard a few people say they’d like to see that. I’m curious -
why do we need more than 64 priorities? I don’t even run 64 threads
total on a typical installation.

If you use threads and not the old QNX4 driver concepts with
continuations … then you simply needs a lot of threads.

If you try to apply some science to assigning priorities to your
threads, you may end up needing more than 64. Theoretically you might
need a unique priority for each thread.

By the way, we have over 100 threads in just one of our processes.

We use the adjustable time slice in QNX4 solely for timer resolution.

AFAIK … QNX4 has a fixed time slice of 50ms for its RR scheduling.

Armin

“Armin Steinhoff” <A-Steinhoff@web_.de> wrote in message
news:3A928420.974756A9@web_.de…

IMHO … an adaptive scheduler is a scheduler which allows the
modification of its static scheduling parameters … e.g. the
duration of the timeslice (SCHED_RR).

What you are describing here, I would call an adjustable scheduler,
not an adaptive scheduler.

Adaptive scheduling is a scheduling discipline which deals e.g with
dynamic system states like overload situation, timeliness, deadlines
specific algorithmn and many other aspects … so it is a little bit
more than SCHED_OTHER > :slight_smile:

In QNX4 the adaptive scheduler dealt with the case where a thread
continuously consumed all of its timeslice without blocking (a form of
overload). What it did in this situation is decay the priority of the
thread.

I hate the way compiles don’t automatically drop to below shell priority
in RtP, the way they do in QNX 4.

Rennie

I hate the way compiles don’t automatically drop to below shell priority
in RtP, the way they do in QNX 4.

Oh, but they do. If you use qcc (but why would anyone want to do that? ;v)


cburgess@qnx.com

On 20 Feb 2001 16:31:55 GMT, Colin Burgess <cburgess@qnx.com> wrote:

I hate the way compiles don’t automatically drop to below shell priority
in RtP, the way they do in QNX 4.

Oh, but they do. If you use qcc (but why would anyone want to do that? ;v)

Touche’ – LOL


cburgess@qnx.com

Thank you for your comments on what you would like to see
with respect to scheduler and scheduling adjustments. I’ll
take them and put them in my back pocket. The additional
scheduling algorithm will indeed be similar to the QNX4
priority decay scheduling algorithm.

Thomas

<!doctype html public “-//w3c//dtd html 4.0 transitional//en”>

Thomas Fletcher a écrit :
Thank you for your comments on what you would like to see
with respect to scheduler and scheduling adjustments.  I'll
take them and put them in my back pocket.
Please take care when you'll put your jean in the wash machine :wink:
Thomas


 

 

In article <3A91ACC0.CC7F3366@motorola.com>,
Igor Kovalenko <Igor.Kovalenko@motorola.com> wrote:

Andrew Thomas wrote:

Previously, Armin Steinhoff wrote in qdn.public.qnxrtp.os:
An ‘adaptive’ scheduler or a scheduler which does ‘adaptive
scheduling’ ??

Can you explain the difference?


I’ll leave that pleasure to Armin.

Would be nice to see at first the ‘simple’ things like adjustable
time slices and more than 64 priorities

I’ve heard a few people say they’d like to see that. I’m curious -
why do we need more than 64 priorities? I don’t even run 64 threads
total on a typical installation.


If you try to apply some science to assigning priorities to your
threads, you may end up needing more than 64. Theoretically you might
need a unique priority for each thread.

Of course, this is only theoretical. The worst case is EDF scheduling,
where you need a different priority to represent each deadline. To do
EDF on a priority system, you are probably better off using a secondary
scheduler that adjusts priorities anyway.

In the case of most static priority analysis schemes, particularly
RMS, you only need a unique priority for each rate/cost pair. If you
have more than 64 rates, you can map multiple rates into a single bucket.
So, for example, with a couple of hundred threads with a large number
running at the same rate and with similar costs per period, you can lump
the costs together and run those threads at the same priority.

If you perform a mapping, it is possible that the hard realtime guarantees
won’t be met 100% of the time. However, if you consider the CPU utilization
possible while still meeting all deadlines – assuming completely accurate
cost measurements (another issue) – empirical studies have demonstrated
that there is a curve relating the number of priorities available (the
buckets) relative to the percentage of CPU utilization possible. The
knee of the curve sits at around 32 priorities with 95% utilization.

In the real world, there are always non-realtime activities, including
non-schedulable OS activities, even with the best OS (context-switch
overhead, primarily if not doing run-to-block (i.e. FIFO), interrupts etc.),
so the CPU utilization target is usually much lower (defence contractors,
for example, typically use a 50% target).

Under such circumstances, I fail to see how 64 priorities would be deemed
insufficient.

If your analysis isn’t at least that rigorous, arguing about the number
of priorities would seem to be pointless in any case.

By the way, we have over 100 threads in just one of our processes.

We use the adjustable time slice in QNX4 solely for timer resolution.
Does NTO have a different mechanism so that timer resolution is not
tied to time slice? If time slice and timer resolution are tied
together, adjustable time slice sounds like an absolute necessity.


As I said already, TimeSlice = 4 * ClockPeriod.

  • igor

Steve Furr email: furr@qnx.com
QNX Software Systems, Ltd.

Steve Furr wrote:

In article <> 3A91ACC0.CC7F3366@motorola.com> >,
Igor Kovalenko <> Igor.Kovalenko@motorola.com> > wrote:
Andrew Thomas wrote:

Previously, Armin Steinhoff wrote in qdn.public.qnxrtp.os:
An ‘adaptive’ scheduler or a scheduler which does ‘adaptive
scheduling’ ??

Can you explain the difference?


I’ll leave that pleasure to Armin.

Would be nice to see at first the ‘simple’ things like adjustable
time slices and more than 64 priorities

I’ve heard a few people say they’d like to see that. I’m curious -
why do we need more than 64 priorities? I don’t even run 64 threads
total on a typical installation.



[ clip …]

If your analysis isn’t at least that rigorous, arguing about the number
of priorities would seem to be pointless in any case.

I’m not sure. Solaris is using the following scheme:

Time Share (TS) –
Provides traditional UNIX process scheduling, assuring fairness
and maximizing throughput (priorities 0-59)

Interactive (IA) –
Provides responsiveness for user interaction by favoring processes
with keyboard focus (for a system running a windowing system)

System (SYS) –
Provides fixed-priority scheduling for kernel threads such as the
pageout thread and RPC service threads (priorities 60-99)

Real Time (RT) –
Provides fixed-priority preemptive scheduling for user processes
(priorities 100-159)


I don’t believe that this design is pointless …

Armin


By the way, we have over 100 threads in just one of our processes.

We use the adjustable time slice in QNX4 solely for timer resolution.
Does NTO have a different mechanism so that timer resolution is not
tied to time slice? If time slice and timer resolution are tied
together, adjustable time slice sounds like an absolute necessity.


As I said already, TimeSlice = 4 * ClockPeriod.

  • igor

Steve Furr email: > furr@qnx.com
QNX Software Systems, Ltd.

In article <3A94E4FA.77E69311@web_.de>,
Armin Steinhoff <A-Steinhoff@web_.de> wrote:

Steve Furr wrote:

In article <> 3A91ACC0.CC7F3366@motorola.com> >,
Igor Kovalenko <> Igor.Kovalenko@motorola.com> > wrote:
Andrew Thomas wrote:

Previously, Armin Steinhoff wrote in qdn.public.qnxrtp.os:
An ‘adaptive’ scheduler or a scheduler which does ‘adaptive
scheduling’ ??

Can you explain the difference?


I’ll leave that pleasure to Armin.

Would be nice to see at first the ‘simple’ things like adjustable
time slices and more than 64 priorities

I’ve heard a few people say they’d like to see that. I’m curious -
why do we need more than 64 priorities? I don’t even run 64 threads
total on a typical installation.



[ clip …]

If your analysis isn’t at least that rigorous, arguing about the number
of priorities would seem to be pointless in any case.

I’m not sure. Solaris is using the following scheme:

Time Share (TS) –
Provides traditional UNIX process scheduling, assuring fairness
and maximizing throughput (priorities 0-59)

Interactive (IA) –
Provides responsiveness for user interaction by favoring processes
with keyboard focus (for a system running a windowing system)

System (SYS) –
Provides fixed-priority scheduling for kernel threads such as the
pageout thread and RPC service threads (priorities 60-99)

Real Time (RT) –
Provides fixed-priority preemptive scheduling for user processes
(priorities 100-159)


I don’t believe that this design is pointless …

Okay, so it’s not pointless, but the important point I take from it is
that 60 priorities are available for realtime. That’s on the
same order as 54 for QNX if you were to put 10 aside for “traditional”
QNX priorities, for non-realtime applications. This tends to support
the contention that 64 is sufficient for realtime demands, and thus
makes a good tradeoff between kernel memory requirements and
flexibility.

Note that changing the scheduling algorithm (SCHED_OTHER) would allow
QNX4 “adaptive” scheduling – multi-level feedback – to dynamically
adjust priorities within the first ten to adjust “responsiveness”. Other
scheduling algorithms can also keep scheduler-specific information,
so there is no reason SCHED_OTHER can’t have nice-ness levels, scheduling
classes, or even cause a different selection policy (though that would
complicate it).

Armin




By the way, we have over 100 threads in just one of our processes.

We use the adjustable time slice in QNX4 solely for timer resolution.
Does NTO have a different mechanism so that timer resolution is not
tied to time slice? If time slice and timer resolution are tied
together, adjustable time slice sounds like an absolute necessity.


As I said already, TimeSlice = 4 * ClockPeriod.

  • igor

Steve Furr email: > furr@qnx.com
QNX Software Systems, Ltd.

Steve Furr email: furr@qnx.com
QNX Software Systems, Ltd.

Solaris simply splits priorities range into classes. You can have same
scheme with different total number of priorities, although it might be
less flexible.

  • igor

Armin Steinhoff wrote:

Steve Furr wrote:

In article <> 3A91ACC0.CC7F3366@motorola.com> >,
Igor Kovalenko <> Igor.Kovalenko@motorola.com> > wrote:
Andrew Thomas wrote:

Previously, Armin Steinhoff wrote in qdn.public.qnxrtp.os:
An ‘adaptive’ scheduler or a scheduler which does ‘adaptive
scheduling’ ??

Can you explain the difference?


I’ll leave that pleasure to Armin.

Would be nice to see at first the ‘simple’ things like adjustable
time slices and more than 64 priorities

I’ve heard a few people say they’d like to see that. I’m curious -
why do we need more than 64 priorities? I don’t even run 64 threads
total on a typical installation.



[ clip …]

If your analysis isn’t at least that rigorous, arguing about the number
of priorities would seem to be pointless in any case.

I’m not sure. Solaris is using the following scheme:

Time Share (TS) –
Provides traditional UNIX process scheduling, assuring fairness
and maximizing throughput (priorities 0-59)

Interactive (IA) –
Provides responsiveness for user interaction by favoring processes
with keyboard focus (for a system running a windowing system)

System (SYS) –
Provides fixed-priority scheduling for kernel threads such as the
pageout thread and RPC service threads (priorities 60-99)

Real Time (RT) –
Provides fixed-priority preemptive scheduling for user processes
(priorities 100-159)

I don’t believe that this design is pointless …

Armin



By the way, we have over 100 threads in just one of our processes.

We use the adjustable time slice in QNX4 solely for timer resolution.
Does NTO have a different mechanism so that timer resolution is not
tied to time slice? If time slice and timer resolution are tied
together, adjustable time slice sounds like an absolute necessity.


As I said already, TimeSlice = 4 * ClockPeriod.

  • igor

Steve Furr email: > furr@qnx.com
QNX Software Systems, Ltd.