Re: Real Time Runqueue

Re: Real Time Runqueue

[Jesse Pollard]

Mike Kravetz <kravetz@us.ibm.com>:
> 
> As you may know, a few of us are experimenting with multi-runqueue
> scheduler implementations.  One area of concern is where to place
> realtime tasks.  It has been my assumption, that POSIX RT semantics
> require a specific ordering of tasks such as SCHED_FIFO and SCHED_RR.
> To accommodate this ordering, I further believe that the simplest
> solution is to ensure that all realtime tasks reside on the same
> runqueue.  In our MQ scheduler we have a separate runqueue for all
> realtime tasks.  The problem is that maintaining a separate realtime
> runqueue is a pain and results in some fairly complex/ugly code.
> 
> Since I'm not a realtime expert, I would like to ask if my assumption
> about strict ordering of RT tasks is accurate.  Also, is anyone aware
> of other ways to approach this problem?

I used to do real-time (seismic survey navigation - sea, land and aircraft
based systems). I've always admired some of the approaches used by the old
VAX system (we did an adaptation for PDP-11/73 systems).

The operation provided a mixed environment of RR and fixed priority operation.
The core scheduler is based on a bit vector of no larger than 64 fixed priority
queues. Each queue could then be handled in a FIFO or RR manner. Selection
of the queue was done by a "first bit set" selection. This identified the
queue that the process was to be selected. Each queue had a selection fuction
that could implement any choses scheduling algorithm, but we only used FIFO
and RR. Several properties were required:

1. Only runnable processes are permitted to exist in the queues.
2. An empty queue had the corresponding bit value of zero.
3. Any queue with pending processes had the corresponding bit set to 1.

Our adaption took the bit vector, converted it to floating point, and
subtracted the exponent bias from the exponent. This gave us the "first bit
set" in the vector. This index can then be used to select the queue and
the selection algorithim. The return value is always the process to run.
If the current process matches the original value, then return to the
already loaded context; otherwise a context swich was called for. Also note
that the current context contained the queue identifier. This makes it
simple to save the current context. Of course, if the vector were zero then
the idle task was invoked.

We found that most of the time the queues only held one or two processes,
making for a fast selection (we only had one processor so we didn't have
to deal with SMP issues).

When only one process/queue exists you have fixed priority queueing.

If a queue has more than one process, then the possibility for FIFO or RR is
available, with FIFO becoming a "complete current process" before it ever
looks at the other processes at the same priority.

I think the VMS useage was to have the first 16 bits in the vector for
realtime kernel processes, the second 16 for realtime user mode processes, the
next 32 were timesharing user processes, with various priorities.

Now as to strict realtime ordering, yes and no. This is because some things
MUST be done - in our case range computations had to be completed before the
next range came in. This put it at the highest fixed priority, NO
interference from other tasks.

Distance/bearing/location came next (if a new range was not available, then
dead reckon the location) and was strictly scheduled on time.

These two tasks were fixed priority and were the only processes in their
corresponding priority queue.

A lower level task called for data recording when a certain distance had
been covered. This would be FIFO with a display update process. (we ended
up with a ship representation display with known local obsticals.. oil rigs,
entered base line markers, wrecks, sandbars...)

Lower level tasks handled command input and was scheduled RR with a
data calculator functions (geodesic distance/time computation), navigation
parameter initialization ...

The idle task ended up handling a location plotter (spin on flag interface,
no interrupt available... stupid thing was too fast for an interrupt, but
required about 100 iterations per output byte).

Inter-process communication was done with SHORT messages. The largest was
the data recording snapshot -between 128 and 150 bytes long); the shortest
was about 32 bytes - latitude/longitude/bering/distance. The kernel
suspended scheduling during the message copy.

Along with this was the usual device drivers (tape/printer/keyboard/serial)
for communicating with external customer devices. There were also special
drivers for controlling the range input device, early GPS recievers,
LORAN-C recievers,...

This is in part a description in favor of your multi queue scheduler.

Complexity is relative - usually the hard part is deciding whether all
processes must exist in the queue at all times -idle/ready/sleeping/...
or if the queues only contain runnable processes.

If (and this may depend on hardware) it is easy to insert/remove from
queues, then having the process out of the queues when idle will speed up
the selection process. Having only active processes also makes it feasable
to use the bit vector.

I believe we opted to leave all process in the queues to speed up the
state change procedures. The selection process was always at the end of
a processing cyle (either clock interrupt, or the process did an I/O)
so the overhead was always measured relative to the previous running
process.

I always liked the trick of converting the bit vector to a floating point to
use the exponent to determine the active queue - it took far fewer instructions
than a loop to check each queue in an array. The added overhead when doing
the queue insertion became one instruction. It does require that only active
processes be in the queue, though. Otherwise you have to have a queue scan
since the queue MAY have all processes idle, even though the bit is set (have
to clear it and start the queue selection over - bummer. (a "find first set
bit" instruction is really usefull here).

-------------------------------------------------------------------------
Jesse I Pollard, II
Email: pollard@navo.hpc.mil

Any opinions expressed are solely my own.

Re: Real Time Runqueue

[Davide Libenzi]

On Fri, 16 Nov 2001, Jesse Pollard wrote:

> I believe we opted to leave all process in the queues to speed up the
> state change procedures. The selection process was always at the end of

I believe in that too, expecially if a good RT tasks distribution is
achieved.



> I always liked the trick of converting the bit vector to a floating point to
> use the exponent to determine the active queue - it took far fewer instructions
> than a loop to check each queue in an array. The added overhead when doing

Smart trick but by doing it in Linux needs you to get the fpu status
before doing the fp op otherwise you're going to do the fpu status
save/restore each time.




- Davide

Re: [Lse-tech] Re: Real Time Runqueue

[george anzinger]

Jesse Pollard wrote:
> 
> Mike Kravetz <kravetz@us.ibm.com>:
> >
> > As you may know, a few of us are experimenting with multi-runqueue
> > scheduler implementations.  One area of concern is where to place
> > realtime tasks.  It has been my assumption, that POSIX RT semantics
> > require a specific ordering of tasks such as SCHED_FIFO and SCHED_RR.
> > To accommodate this ordering, I further believe that the simplest
> > solution is to ensure that all realtime tasks reside on the same
> > runqueue.  In our MQ scheduler we have a separate runqueue for all
> > realtime tasks.  The problem is that maintaining a separate realtime
> > runqueue is a pain and results in some fairly complex/ugly code.
> >
> > Since I'm not a realtime expert, I would like to ask if my assumption
> > about strict ordering of RT tasks is accurate.  Also, is anyone aware
> > of other ways to approach this problem?
> 
> I used to do real-time (seismic survey navigation - sea, land and aircraft
> based systems). I've always admired some of the approaches used by the old
> VAX system (we did an adaptation for PDP-11/73 systems).
> 
> The operation provided a mixed environment of RR and fixed priority operation.
> The core scheduler is based on a bit vector of no larger than 64 fixed priority
> queues. Each queue could then be handled in a FIFO or RR manner. Selection
> of the queue was done by a "first bit set" selection. This identified the
> queue that the process was to be selected. Each queue had a selection fuction
> that could implement any choses scheduling algorithm, but we only used FIFO
> and RR. Several properties were required:
> 
> 1. Only runnable processes are permitted to exist in the queues.
> 2. An empty queue had the corresponding bit value of zero.
> 3. Any queue with pending processes had the corresponding bit set to 1.
> 
> Our adaption took the bit vector, converted it to floating point, and
> subtracted the exponent bias from the exponent. This gave us the "first bit
> set" in the vector. This index can then be used to select the queue and
> the selection algorithim. The return value is always the process to run.
> If the current process matches the original value, then return to the
> already loaded context; otherwise a context swich was called for. Also note
> that the current context contained the queue identifier. This makes it
> simple to save the current context. Of course, if the vector were zero then
> the idle task was invoked.

Take a look at http://sourceforge.net/projects/rtsched/ to see a linux
scheduler that uses very much this same thing.  No floating point, but
there are find first bit instructions on most machines.


> 
~snip
-- 
George           george@mvista.com
High-res-timers: http://sourceforge.net/projects/high-res-timers/
Real time sched: http://sourceforge.net/projects/rtsched/

Re: Real Time Runqueue

[Victor Yodaiken]

On Fri, Nov 16, 2001 at 04:32:24PM -0800, Mike Kravetz wrote:
> The reason I ask is that we went through the pains of a separate
> realtime RQ in our MQ scheduler.  And yes, it does hurt the common
> case, not to mention the extra/complex code paths.  I was hoping
> that someone in the know could enlighten us as to how RT semantics
> apply to SMP systems.  If the semantics I suggest above are required,
> then it implies support must be added to any possible future
> scheduler implementations.

POSIX RT specs, at least last year, did not mention any SMP
requirements for scheduling at all.
What we do in RTLinux is require that RT threads be associated with a
processor identifier on the theory that the user may have some idea what
processors should run which RT threads, but the OS has no way of
guessing.




> 
> -- 
> Mike
> -
> To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
> the body of a message to majordomo@vger.kernel.org
> More majordomo info at  http://vger.kernel.org/majordomo-info.html
> Please read the FAQ at  http://www.tux.org/lkml/

Re: Real Time Runqueue

[Mike Kravetz]

On Fri, Nov 16, 2001 at 04:28:33PM -0800, Davide Libenzi wrote:
> On Fri, 16 Nov 2001, Mike Kravetz wrote:
> 
> > Suppose you have a 2 CPU system with 4 runnable tasks.  3 of these
> > tasks are realtime with the same realtime priority and the other is
> > an ordinary SCHED_OTHER task.  The task distribution on the runqueues
> > looks something like this.
> >
> > CPU 0             CPU 1
> > ---------         ---------
> > RT Task A         RT Task B
> > Other Task C      RT Task D
> >
> > Task A and Task B are currently running on the 2 CPUs.  Now, Task A
> > voluntarily gives up CPU 0 and Task B is still running on CPU 1.
> > At this point, Task D should be chosen to run on CPU 0.  Correct?
> > Isn't this a required RT semantic?  I'm curious how you plan on
> > accomplishing this.
> 
> Well I don't know how RT sematics apply to SMP systems.

Me either (not exactly).

> The easy solution ( == big common lock ) would be to have a single RT
> queue that is checked before the private one.
> Anyway, sometime it happens that the cure is worst than the disease and to
> solve a corner case you're going to punish common case performances (
> Linux is not an RT OS even with that fix ).

The reason I ask is that we went through the pains of a separate
realtime RQ in our MQ scheduler.  And yes, it does hurt the common
case, not to mention the extra/complex code paths.  I was hoping
that someone in the know could enlighten us as to how RT semantics
apply to SMP systems.  If the semantics I suggest above are required,
then it implies support must be added to any possible future
scheduler implementations.

-- 
Mike

Re: Real Time Runqueue

[Davide Libenzi]

On Fri, 16 Nov 2001, Mike Kravetz wrote:

> Suppose you have a 2 CPU system with 4 runnable tasks.  3 of these
> tasks are realtime with the same realtime priority and the other is
> an ordinary SCHED_OTHER task.  The task distribution on the runqueues
> looks something like this.
>
> CPU 0             CPU 1
> ---------         ---------
> RT Task A         RT Task B
> Other Task C      RT Task D
>
> Task A and Task B are currently running on the 2 CPUs.  Now, Task A
> voluntarily gives up CPU 0 and Task B is still running on CPU 1.
> At this point, Task D should be chosen to run on CPU 0.  Correct?
> Isn't this a required RT semantic?  I'm curious how you plan on
> accomplishing this.

Well I don't know how RT sematics apply to SMP systems.
The easy solution ( == big common lock ) would be to have a single RT
queue that is checked before the private one.
Anyway, sometime it happens that the cure is worst than the disease and to
solve a corner case you're going to punish common case performances (
Linux is not an RT OS even with that fix ).




- Davide

Re: Real Time Runqueue

[Mike Kravetz]

On Fri, Nov 16, 2001 at 02:44:30PM -0800, Davide Libenzi wrote:
> 
> I do not use a separate queue coz, if it's single, it becomes a common
> lock for all CPUs.
> RT tasks are scheduled as usual and the only problem arises in
> reschedule_idle() when an RT task is pushed onto the run queue when
> 1) on its CPU it is _not_ running the idle
> 2) on its CPU is running another RT task with higher priority
> 
> In that case a "good CPU" discovery loop is triggered, the task is moved
> on that CPU runqueue, need_resched is set, an IPI is sent and on return
> from the remote CPU IPI  path the RT task is run.
> A good solution would be ( i'm not doing it now ), in setscheduler() to
> move the task in a way to have an even distribution of RT tasks among
> CPUs.
> 
> - Davide

Davide,

Suppose you have a 2 CPU system with 4 runnable tasks.  3 of these
tasks are realtime with the same realtime priority and the other is
an ordinary SCHED_OTHER task.  The task distribution on the runqueues
looks something like this.

CPU 0             CPU 1
---------         ---------
RT Task A         RT Task B
Other Task C      RT Task D

Task A and Task B are currently running on the 2 CPUs.  Now, Task A
voluntarily gives up CPU 0 and Task B is still running on CPU 1.
At this point, Task D should be chosen to run on CPU 0.  Correct?
Isn't this a required RT semantic?  I'm curious how you plan on
accomplishing this.

Regards,
-- 
Mike

Re: Real Time Runqueue

[Davide Libenzi]

On Fri, 16 Nov 2001, Mike Kravetz wrote:

> As you may know, a few of us are experimenting with multi-runqueue
> scheduler implementations.  One area of concern is where to place
> realtime tasks.  It has been my assumption, that POSIX RT semantics
> require a specific ordering of tasks such as SCHED_FIFO and SCHED_RR.
> To accommodate this ordering, I further believe that the simplest
> solution is to ensure that all realtime tasks reside on the same
> runqueue.  In our MQ scheduler we have a separate runqueue for all
> realtime tasks.  The problem is that maintaining a separate realtime
> runqueue is a pain and results in some fairly complex/ugly code.
>
> Since I'm not a realtime expert, I would like to ask if my assumption
> about strict ordering of RT tasks is accurate.  Also, is anyone aware
> of other ways to approach this problem?

I do not use a separate queue coz, if it's single, it becomes a common
lock for all CPUs.
RT tasks are scheduled as usual and the only problem arises in
reschedule_idle() when an RT task is pushed onto the run queue when
1) on its CPU it is _not_ running the idle
2) on its CPU is running another RT task with higher priority

In that case a "good CPU" discovery loop is triggered, the task is moved
on that CPU runqueue, need_resched is set, an IPI is sent and on return
from the remote CPU IPI  path the RT task is run.
A good solution would be ( i'm not doing it now ), in setscheduler() to
move the task in a way to have an even distribution of RT tasks among
CPUs.




- Davide

Re: Real Time Runqueue

[Richard Gooch]

Mike Kravetz writes:
> As you may know, a few of us are experimenting with multi-runqueue
> scheduler implementations.  One area of concern is where to place
> realtime tasks.  It has been my assumption, that POSIX RT semantics
> require a specific ordering of tasks such as SCHED_FIFO and SCHED_RR.
> To accommodate this ordering, I further believe that the simplest
> solution is to ensure that all realtime tasks reside on the same
> runqueue.  In our MQ scheduler we have a separate runqueue for all
> realtime tasks.  The problem is that maintaining a separate realtime
> runqueue is a pain and results in some fairly complex/ugly code.
> 
> Since I'm not a realtime expert, I would like to ask if my assumption
> about strict ordering of RT tasks is accurate.  Also, is anyone aware
> of other ways to approach this problem?

Yes, strict ordering is required. Years ago I championed a separate
runqueue for RT tasks. Linus even said he liked the approach. I got
busy and never nursed it to inclusion. The patch is here:
ftp://ftp.atnf.csiro.au/pub/people/rgooch/linux/kernel-patches/v2.1/rtqueue-patch

				Regards,

					Richard....
Permanent: rgooch@atnf.csiro.au
Current:   rgooch@ras.ucalgary.ca

Real Time Runqueue

[Mike Kravetz]

As you may know, a few of us are experimenting with multi-runqueue
scheduler implementations.  One area of concern is where to place
realtime tasks.  It has been my assumption, that POSIX RT semantics
require a specific ordering of tasks such as SCHED_FIFO and SCHED_RR.
To accommodate this ordering, I further believe that the simplest
solution is to ensure that all realtime tasks reside on the same
runqueue.  In our MQ scheduler we have a separate runqueue for all
realtime tasks.  The problem is that maintaining a separate realtime
runqueue is a pain and results in some fairly complex/ugly code.

Since I'm not a realtime expert, I would like to ask if my assumption
about strict ordering of RT tasks is accurate.  Also, is anyone aware
of other ways to approach this problem?

Thanks,
-- 
Mike