Has this wheel already been invented?

There are all sorts of preemptive kernels, RTOS's, frameworks, out
there, open source and commercial.  There are priority-driven
preemptive systems, time-sliced preemptive systems, and others.

But preemptive systems have their costs, namely context switching
time, and context storing RAM.  Even cooperative coroutines have
context switch and space overhead.

On the other end of the scale is pure cooperative multitasking, as
exemplified by the classic "super loop":

while (1)
{
   task1();
   task2();
   /* ... */
   task99();
   task100();
}

In most cases, each of these task calls some lower level routine
(timer, communication interface, whatever) to see if there's actually
any work for it to do.  If not, is just returns.  The advantage, of
course, is that there is no context overhead, either space or time.

This can be detrimental to response time if an event comes in for a
task just after it has had its turn in the super loop.  It won't see
its event until after every other task has been called, whether the
other tasks really have any useful work to do or not.

What I need, and I am planning to develop, is a cooperative task
scheduler to replace the super loop.  Inter task communication, and
ISR to task communication, will go through a kernel to set event
flags, timer flags, put messages in queues, etc., and the kernel will
track which tasks are actually ready because they have pending events.

After any task returns, the scheduler will execute the highest
priority ready task.

My question is, does anyone know of any kernel, RTOS, whatever, that's
implemented this way?  I'd look at the documentation and API details
for any that exist, not their source code.

Knowing whether or not this wheel has already been invented will be
handy when I reinvent it.

-- 
Jack Klein
Home: http://JK-Technology.Com
FAQs for
comp.lang.c http://c-faq.com/
comp.lang.c++ http://www.parashift.com/c++-faq-lite/
alt.comp.lang.learn.c-c++
http://www.club.cc.cmu.edu/~ajo/docs/FAQ-acllc.html

On Fri, 16 Nov 2007 22:31:06 -0600, Jack Klein <jackklein@spamcop.net>
wrote:

=== SNIP ===

>What I need, and I am planning to develop, is a cooperative task
>scheduler to replace the super loop.  Inter task communication, and
>ISR to task communication, will go through a kernel to set event
>flags, timer flags, put messages in queues, etc., and the kernel will
>track which tasks are actually ready because they have pending events.
>
>After any task returns, the scheduler will execute the highest
>priority ready task.
>
>My question is, does anyone know of any kernel, RTOS, whatever, that's
>implemented this way?  I'd look at the documentation and API details
>for any that exist, not their source code.
>
>Knowing whether or not this wheel has already been invented will be
>handy when I reinvent it.

Salvo?  www.pumpkininc.com

-- 
Dan Henry

On Nov 17, 5:31 am, Jack Klein <jackkl...@spamcop.net> wrote:

> There are all sorts of preemptive kernels, RTOS's, frameworks, out
> there, open source and commercial.  There are priority-driven
> preemptive systems, time-sliced preemptive systems, and others.
>
> But preemptive systems have their costs, namely context switching
> time, and context storing RAM.  Even cooperative coroutines have
> context switch and space overhead.
>
> On the other end of the scale is pure cooperative multitasking, as
> exemplified by the classic "super loop":
>
> while (1)
> {
>    task1();
>    task2();
>    /* ... */
>    task99();
>    task100();
>
> }
>
> In most cases, each of these task calls some lower level routine
> (timer, communication interface, whatever) to see if there's actually
> any work for it to do.  If not, is just returns.  The advantage, of
> course, is that there is no context overhead, either space or time.
>
> This can be detrimental to response time if an event comes in for a
> task just after it has had its turn in the super loop.  It won't see
> its event until after every other task has been called, whether the
> other tasks really have any useful work to do or not.
>
> What I need, and I am planning to develop, is a cooperative task
> scheduler to replace the super loop.  Inter task communication, and
> ISR to task communication, will go through a kernel to set event
> flags, timer flags, put messages in queues, etc., and the kernel will
> track which tasks are actually ready because they have pending events.
>
> After any task returns, the scheduler will execute the highest
> priority ready task.
>
> My question is, does anyone know of any kernel, RTOS, whatever, that's
> implemented this way?  I'd look at the documentation and API details
> for any that exist, not their source code.
>
> Knowing whether or not this wheel has already been invented will be
> handy when I reinvent it.

This sounds like the 'task queue' mechanism that Linux has. Check this
link for an explanation:

http://www.xml.com/ldd/chapter/book/ch06.html#t4

This is basically a non-preemptive scheduler.  Any RTOS can give you the 
exact behavior you desire with no hassel.  Look at uC/OS-II for an example, 
it has its source available and a book.


---Matthew Hicks


> There are all sorts of preemptive kernels, RTOS's, frameworks, out
> there, open source and commercial.  There are priority-driven
> preemptive systems, time-sliced preemptive systems, and others.
> 
> But preemptive systems have their costs, namely context switching
> time, and context storing RAM.  Even cooperative coroutines have
> context switch and space overhead.
> 
> On the other end of the scale is pure cooperative multitasking, as
> exemplified by the classic "super loop":
> 
> while (1)
> {
> task1();
> task2();
> /* ... */
> task99();
> task100();
> }
> In most cases, each of these task calls some lower level routine
> (timer, communication interface, whatever) to see if there's actually
> any work for it to do.  If not, is just returns.  The advantage, of
> course, is that there is no context overhead, either space or time.
> 
> This can be detrimental to response time if an event comes in for a
> task just after it has had its turn in the super loop.  It won't see
> its event until after every other task has been called, whether the
> other tasks really have any useful work to do or not.
> 
> What I need, and I am planning to develop, is a cooperative task
> scheduler to replace the super loop.  Inter task communication, and
> ISR to task communication, will go through a kernel to set event
> flags, timer flags, put messages in queues, etc., and the kernel will
> track which tasks are actually ready because they have pending events.
> 
> After any task returns, the scheduler will execute the highest
> priority ready task.
> 
> My question is, does anyone know of any kernel, RTOS, whatever, that's
> implemented this way?  I'd look at the documentation and API details
> for any that exist, not their source code.
> 
> Knowing whether or not this wheel has already been invented will be
> handy when I reinvent it.
> 

> What I need, and I am planning to develop, is a cooperative task
> scheduler to replace the super loop.  Inter task communication, and
> ISR to task communication, will go through a kernel to set event
> flags, timer flags, put messages in queues, etc., and the kernel will
> track which tasks are actually ready because they have pending events.


Have you looked at the co-routine functionality in FreeRTOS.org? 
FreeRTOS.org has the following concepts:

Co-routines - These are prioritised light weight tasks that share a stack, 
and there is no context switch as such.  The overhead is no more than a 
function call.

Cooperative tasks - basically tasks but with the kernel set to cooperative 
mode.  Each task maintains its own stack and a full context switch is 
performed to switch from task to task.

Pre-emptive tasks - as cooperative tasks but with the kernel set to 
pre-emptive mode.

If you are looking for something really light weight then take a look at 
http://www.sics.se/~adam/pt/

-- 
Regards,
Richard.

+ http://www.FreeRTOS.org
14 official architecture ports, 1000 downloads per week.

+ http://www.SafeRTOS.com
Certified by T�V as meeting the requirements for safety related systems. 

Jack Klein wrote:
> 
> There are all sorts of preemptive kernels, RTOS's, frameworks, out
> there, open source and commercial.  There are priority-driven
> preemptive systems, time-sliced preemptive systems, and others.
> 
> But preemptive systems have their costs, namely context switching
> time, and context storing RAM.  Even cooperative coroutines have
> context switch and space overhead.
> 
> On the other end of the scale is pure cooperative multitasking, as
> exemplified by the classic "super loop":
> 
> while (1)
> {
>    task1();
>    task2();
>    /* ... */
>    task99();
>    task100();
> }
> 
> In most cases, each of these task calls some lower level routine
> (timer, communication interface, whatever) to see if there's actually
> any work for it to do.  If not, is just returns.  The advantage, of
> course, is that there is no context overhead, either space or time.
> 
> This can be detrimental to response time if an event comes in for a
> task just after it has had its turn in the super loop.  It won't see
> its event until after every other task has been called, whether the
> other tasks really have any useful work to do or not.
> 
> What I need, and I am planning to develop, is a cooperative task
> scheduler to replace the super loop.  Inter task communication, and
> ISR to task communication, will go through a kernel to set event
> flags, timer flags, put messages in queues, etc., and the kernel will
> track which tasks are actually ready because they have pending events.
> 
> After any task returns, the scheduler will execute the highest
> priority ready task.
> 
> My question is, does anyone know of any kernel, RTOS, whatever, that's
> implemented this way?  I'd look at the documentation and API details
> for any that exist, not their source code.
> 
> Knowing whether or not this wheel has already been invented will be
> handy when I reinvent it.

I did something along these lines about 10 years ago on a PIC.  The
system was simplified by requiring that every called subroutine
exited within a fixed period, I think 100 uSec. or so.  This was
forced by the slowest peripheral, which was the display, and could
have to wait about 50 uSec. to become non-busy and accept the next
character.  Thus the char. output mechanism squirted one char and
returned.  There was no minimum time requirement.

When some routine required service more often, I simply called it
more often.  For example, I could have a routine needing service
every 300 uSec (svc0) and four others with no particular speed
requirement (svc1 thru svc4).  Then I called:

  do {
     svc0();
     svc1();
     svc2();
     svc0();  /* again */
     svc3();
     svc4();
  } while (running);

This also had the advantage, for PICs, that interrupts were
normally disabled, and only enabled once in the complete loop. 
That controlled the stack usage etc.

This handled concurrent systems quite nicely.

-- 
 Chuck F (cbfalconer at maineline dot net)
   <http://cbfalconer.home.att.net>
   Try the download section.



-- 
Posted via a free Usenet account from http://www.teranews.com

Jack Klein wrote:
> There are all sorts of preemptive kernels, RTOS's, frameworks, out
> there, open source and commercial.  There are priority-driven
> preemptive systems, time-sliced preemptive systems, and others.
> 
> But preemptive systems have their costs, namely context switching
> time, and context storing RAM.  Even cooperative coroutines have
> context switch and space overhead.
> 
> On the other end of the scale is pure cooperative multitasking, as
> exemplified by the classic "super loop":
> 
> while (1)
> {
>    task1();
>    task2();
>    /* ... */
>    task99();
>    task100();
> }
> 
> In most cases, each of these task calls some lower level routine
> (timer, communication interface, whatever) to see if there's actually
> any work for it to do.  If not, is just returns.  The advantage, of
> course, is that there is no context overhead, either space or time.
> 
> This can be detrimental to response time if an event comes in for a
> task just after it has had its turn in the super loop.  It won't see
> its event until after every other task has been called, whether the
> other tasks really have any useful work to do or not.
> 
> What I need, and I am planning to develop, is a cooperative task
> scheduler to replace the super loop.  Inter task communication, and
> ISR to task communication, will go through a kernel to set event
> flags, timer flags, put messages in queues, etc., and the kernel will
> track which tasks are actually ready because they have pending events.
> 
> After any task returns, the scheduler will execute the highest
> priority ready task.
> 
> My question is, does anyone know of any kernel, RTOS, whatever, that's
> implemented this way?  I'd look at the documentation and API details
> for any that exist, not their source code.
> 
> Knowing whether or not this wheel has already been invented will be
> handy when I reinvent it.
> 
In most embedded systems, the number of possible tasks is fixed (as in
your example above). Often, their priorities do not change: they too are
fixed by the system design. When this is so, an efficient scheduler is
just a list of machine instructions, which are altered as needed.
Using Z80 instructions as an example, you can have something like this:

            .section ROM
            Scheduler:
21 tasktab       ld   hl,tasktab       ; Table of JP instructions
11 03 00         ld   de,3             ; Length of a JP instruction
C3 TaskList      call TaskList         ; Return (here) is stacked
                 ...

            tasktab:          ; These do not change
C3 Task_0        jp   Task_0
C3 Task_1        jp   Task_1
                 ...

Task_0:                       ; Typical of each task
                 ...
C9               ret

	    .section RAM
            TaskList:         ; These are altered to de/activate tasks
19               add  hl,de            ; Task 0 cannot run
E9               jp   (hl)             ; Task 1 can run
                 ...
C9               ret                   ; Nothing can run (end marker)

Each TaskList element is 1 byte, being a 1-byte Z80 instruction. You set
a task active or inactive by changing that byte to either "add hl,de" or
"jp (hl)". When the table is executed, the first (highest) available
task will run, as its jump will be taken.

Obviously, alter to taste for other CPUs.
[I first saw this trick used in 1972, on the GEC 2050 mini.]

Jack Klein wrote:

> There are all sorts of preemptive kernels, RTOS's, frameworks, out
> there, open source and commercial.  There are priority-driven
> preemptive systems, time-sliced preemptive systems, and others.
> 
> But preemptive systems have their costs, namely context switching
> time, and context storing RAM.  Even cooperative coroutines have
> context switch and space overhead.
> 
> On the other end of the scale is pure cooperative multitasking, as
> exemplified by the classic "super loop":
> 
> while (1)
> {
>    task1();
>    task2();
>    /* ... */
>    task99();
>    task100();
> }
> 
> In most cases, each of these task calls some lower level routine
> (timer, communication interface, whatever) to see if there's actually
> any work for it to do.  If not, is just returns.  The advantage, of
> course, is that there is no context overhead, either space or time.
> 
> This can be detrimental to response time if an event comes in for a
> task just after it has had its turn in the super loop.  It won't see
> its event until after every other task has been called, whether the
> other tasks really have any useful work to do or not.
> 
> What I need, and I am planning to develop, is a cooperative task
> scheduler to replace the super loop.  Inter task communication, and
> ISR to task communication, will go through a kernel to set event
> flags, timer flags, put messages in queues, etc., and the kernel will
> track which tasks are actually ready because they have pending events.
> 
> After any task returns, the scheduler will execute the highest
> priority ready task.
> 
> My question is, does anyone know of any kernel, RTOS, whatever, that's
> implemented this way?  I'd look at the documentation and API details
> for any that exist, not their source code.
> 
> Knowing whether or not this wheel has already been invented will be
> handy when I reinvent it.

Some years back Klaus Schleisik-Kern presented a paper at a EuroForth
Conference with a mechanism that seemed to have similar aims to your idea.
I'll try and locate the paper and give you a reference to it. If you are
lucky it may be available on the Bournemouth web-site. If not I'll see
about sending a copy to you.

-- 
********************************************************************
Paul E. Bennett...............<email://Paul_E.Bennett@topmail.co.uk>
Forth based HIDECS Consultancy
Mob: +44 (0)7811-639972
Tel: +44 (0)1235-811095
Going Forth Safely ..... EBA. www.electric-boat-association.org.uk..
********************************************************************

Jack Klein wrote:

>There are all sorts of preemptive kernels, RTOS's, frameworks, out
>there, open source and commercial.  There are priority-driven
>preemptive systems, time-sliced preemptive systems, and others.
>
>But preemptive systems have their costs, namely context switching
>time, and context storing RAM.  Even cooperative coroutines have
>context switch and space overhead.
>
>On the other end of the scale is pure cooperative multitasking, as
>exemplified by the classic "super loop":
>
>while (1)
>{
>   task1();
>   task2();
>   /* ... */
>   task99();
>   task100();
>}
>
>In most cases, each of these task calls some lower level routine
>(timer, communication interface, whatever) to see if there's actually
>any work for it to do.  If not, is just returns.  The advantage, of
>course, is that there is no context overhead, either space or time.
>
>This can be detrimental to response time if an event comes in for a
>task just after it has had its turn in the super loop.  It won't see
>its event until after every other task has been called, whether the
>other tasks really have any useful work to do or not.
>
>What I need, and I am planning to develop, is a cooperative task
>scheduler to replace the super loop.  Inter task communication, and
>ISR to task communication, will go through a kernel to set event
>flags, timer flags, put messages in queues, etc., and the kernel will
>track which tasks are actually ready because they have pending events.
>
>After any task returns, the scheduler will execute the highest
>priority ready task.
>
>My question is, does anyone know of any kernel, RTOS, whatever, that's
>implemented this way?  I'd look at the documentation and API details
>for any that exist, not their source code.
>
>Knowing whether or not this wheel has already been invented will be
>handy when I reinvent it.

I woke up one morning a couple of years ago with an idea for improving
the "classic super loop".  I coded it up and call it "prioritized
jobbing".

Each job to be executed is described in an array of data structures that
include job ready booleans and pointers to jobs' initialization and
executive functions.  The initialization functions are called once from
early in main().  Both functions are passed their jobs' indeces.

Event service functions associated with jobs indicate that their jobs
have become ready by passing their jobs' indeces to a job scheduling
function that sets the indicated job's ready flag.

main() scans the job data and jobs' executive functions are called only
when their associated jobs are ready.  When the executive functions
return, job data scanning is restarted from the beginning of the job
data array.  In this way, higher priority is given to jobs with lower
index values.

Not being preemptive, it's not deterministic, but it is simple, small,
and is an improvement over simple looping.

I expect to be told that I have reinvented something that my lack of
formal software engineering education has left me unaware.  ;-)

-- 
========================================================================
          Michael Kesti            |  "And like, one and one don't make
                                   |   two, one and one make one."
    mrkesti at hotmail dot com     |          - The Who, Bargain

On 2007-11-17, Jack Klein <jackklein@spamcop.net> wrote:

> What I need, and I am planning to develop, is a cooperative task
> scheduler to replace the super loop.  Inter task communication, and
> ISR to task communication, will go through a kernel to set event
> flags, timer flags, put messages in queues, etc., and the kernel will
> track which tasks are actually ready because they have pending events.
>
> After any task returns, the scheduler will execute the highest
> priority ready task.
>
> My question is, does anyone know of any kernel, RTOS, whatever, that's
> implemented this way?  I'd look at the documentation and API details
> for any that exist, not their source code.
>
> Knowing whether or not this wheel has already been invented will be
> handy when I reinvent it.

It's been invented many times.

Here are a couple approaches I thought were interesting:

  http://www.sics.se/~adam/pt/

This is a threading model, but doesn't deal with scheduling.
I think you could run it on top of something like this to deal
with scheduling:
  
  http://www.embedded.com/columns/technicalinsights/190302110?_requestid=327672

There are also many implementations of coroutines and
cooperative multi-tasking available.

-- 
Grant