cooperative multitasking scheme

Hi y'all

Quick but not so easy question (it may spawn a considerable thread...)
We need to develop a cooperative multitasking kernel for various
embedded platforms (See the implications and the complications?).
One requirement is that c-functions should serve as "tasks". (Notably,
these tasks perform very simple functions, e.g. polling push buttons,
occasionally updating a display, polling an adc, and a whole slew of
other things that are definitely not time critical.)
The question is, how should cpu time be distributed, given the following:
   Task 1: Priority 1
   Task 2: Priority 1
   Task 3: Priority 1
   Task 4: Priority 1
   Task 5: Priority 4
   Task 6: Priority 8
Should it be:
   T6 T6 T6 T6 T6 T6 T6 T6 T5 T5 T5 T5 T1 T2 T3 T4... ad infinitum
or:
   T6 T5 T6 T5 T6 T5 T6 T5 T6 T1 T6 T2 T6 T3 T6 T4... ad infinitum
or perhaps another scheme that does the assigned priorities right?
A pointer would be very nice too, apart from an interesting discussion.
None of us has a formal education in these matters... We are at a
moderate loss...

Thanks in advance

Waldemar

In article <414d5239$0$76505$b83b6cc0@news.wanadoo.nl>, "Marco Bleekrode" <bleek004@hotmail.com> wrote:
>Hi y'all
>
>Quick but not so easy question (it may spawn a considerable thread...)
>We need to develop a cooperative multitasking kernel for various
>embedded platforms (See the implications and the complications?).
>One requirement is that c-functions should serve as "tasks". (Notably,
>these tasks perform very simple functions, e.g. polling push buttons,
>occasionally updating a display, polling an adc, and a whole slew of
>other things that are definitely not time critical.)
>The question is, how should cpu time be distributed, given the following:
>   Task 1: Priority 1
>   Task 2: Priority 1
>   Task 3: Priority 1
>   Task 4: Priority 1
>   Task 5: Priority 4
>   Task 6: Priority 8
>Should it be:
>   T6 T6 T6 T6 T6 T6 T6 T6 T5 T5 T5 T5 T1 T2 T3 T4... ad infinitum
>or:
>   T6 T5 T6 T5 T6 T5 T6 T5 T6 T1 T6 T2 T6 T3 T6 T4... ad infinitum
>or perhaps another scheme that does the assigned priorities right?
>A pointer would be very nice too, apart from an interesting discussion.
>None of us has a formal education in these matters... We are at a
>moderate loss...

There are so many RTOSes out there that are already written, to me it makes no 
sense to write one from scratch.

So true, nothing is more fun then re-inventing the wheel, however... the 
requirement is
that it has to be absolutely system independent, and furthermore, real time 
is not an issue!
But it has to have a small footprint, no resource management, no i/o 
scheduling, whatsoever...
just the bare "switch"...

"Paul J. Bosselaers" <pjb658@NOSPAMcomcast.net> schreef in bericht 
news:T4e3d.463636$%_6.381885@attbi_s01...
> In article <414d5239$0$76505$b83b6cc0@news.wanadoo.nl>, "Marco Bleekrode" 
> <bleek004@hotmail.com> wrote:
>>Hi y'all
>>
>>Quick but not so easy question (it may spawn a considerable thread...)
>>We need to develop a cooperative multitasking kernel for various
>>embedded platforms (See the implications and the complications?).
>>One requirement is that c-functions should serve as "tasks". (Notably,
>>these tasks perform very simple functions, e.g. polling push buttons,
>>occasionally updating a display, polling an adc, and a whole slew of
>>other things that are definitely not time critical.)
>>The question is, how should cpu time be distributed, given the following:
>>   Task 1: Priority 1
>>   Task 2: Priority 1
>>   Task 3: Priority 1
>>   Task 4: Priority 1
>>   Task 5: Priority 4
>>   Task 6: Priority 8
>>Should it be:
>>   T6 T6 T6 T6 T6 T6 T6 T6 T5 T5 T5 T5 T1 T2 T3 T4... ad infinitum
>>or:
>>   T6 T5 T6 T5 T6 T5 T6 T5 T6 T1 T6 T2 T6 T3 T6 T4... ad infinitum
>>or perhaps another scheme that does the assigned priorities right?
>>A pointer would be very nice too, apart from an interesting discussion.
>>None of us has a formal education in these matters... We are at a
>>moderate loss...
>
> There are so many RTOSes out there that are already written, to me it 
> makes no
> sense to write one from scratch. 

Marco Bleekrode <bleek004@hotmail.com> wrote in message
news:414d5239$0$76505$b83b6cc0@news.wanadoo.nl...
> Hi y'all
>
> Quick but not so easy question (it may spawn a considerable thread...)
> We need to develop a cooperative multitasking kernel for various
> embedded platforms (See the implications and the complications?).
> One requirement is that c-functions should serve as "tasks". (Notably,
> these tasks perform very simple functions, e.g. polling push buttons,
> occasionally updating a display, polling an adc, and a whole slew of
> other things that are definitely not time critical.)
> The question is, how should cpu time be distributed, given the following:
>    Task 1: Priority 1
>    Task 2: Priority 1
>    Task 3: Priority 1
>    Task 4: Priority 1
>    Task 5: Priority 4
>    Task 6: Priority 8
> Should it be:
>    T6 T6 T6 T6 T6 T6 T6 T6 T5 T5 T5 T5 T1 T2 T3 T4... ad infinitum
> or:
>    T6 T5 T6 T5 T6 T5 T6 T5 T6 T1 T6 T2 T6 T3 T6 T4... ad infinitum
> or perhaps another scheme that does the assigned priorities right?
> A pointer would be very nice too, apart from an interesting discussion.
> None of us has a formal education in these matters... We are at a
> moderate loss...
>
> Thanks in advance
>
> Waldemar

You must first define what you want priority to mean.

Should all priority 1 task run in preference to any priority 2 tasks, should
all priority 2 tasks run in preference to any priority 3 tasks etc.

Are you just trying to give a bias toward higher priority tasks such that
each level has certain percentage of the CPU time. Maybe all priority 1
tasks form a group that has 50% of the CPU time, all priority 2 tasks have
25% of the CPU time, all priority 3 tasks have 10% etc

Are you trying to improve the way tasks use CPU time based on how long they
sleep (maybe increasing the priority of tasks if they are not ready to run
so that they receive quicker attention when they are ready to run).

You really need to know what you want the priority system to achive before
you look at ways of implementing your schedular. In some systems I have
found it adiquate to use simple round robin with no prority, others have
required just 2 levels and others 16. Sometimes trying to be too clever is
really counter productive and you end up with a lot of wasted CPU time as
the schedular does a lot of work just to return to the same task that last
active.

Try writing a simulation to get a better feel for how the tasks interact
withing the priority system.

If in doubt keep it simple!

Regards
Sergio Masci

http://www.xcprod.com

Marco Bleekrode <bleek004@hotmail.com> wrote:

[...]
> The question is, how should cpu time be distributed, given the following:
>    Task 1: Priority 1
>    Task 2: Priority 1
>    Task 3: Priority 1
>    Task 4: Priority 1
>    Task 5: Priority 4
>    Task 6: Priority 8
> Should it be:
>    T6 T6 T6 T6 T6 T6 T6 T6 T5 T5 T5 T5 T1 T2 T3 T4... ad infinitum
> or:
>    T6 T5 T6 T5 T6 T5 T6 T5 T6 T1 T6 T2 T6 T3 T6 T4... ad infinitum
> or perhaps another scheme that does the assigned priorities right?

Quite impossible to say, from your problem description.  I would actually
suggest, for this particular case:

	T6 T5 T6 T4 T6 T5 T6 T3 T6 T5 T6 T2 T6 T5 T6 T1

I.e.: distribute not just the 8 calls of Task 6, but also the 4 calls
of T5 evenly.

As another reply already stated, what should be done strongly depends
on what you want "priority" to mean, and what the requirements of your
tasks are, in terms of minimum, average, and maximum time allowed
between executions, and what their behaviour is in terms of time
consumption per (cooperative) call of each task's function.

> None of us has a formal education in these matters... We are at a
> moderate loss...

Then you should definitely get yourself some textbooks before you
proceed.  I've found Pont's "Patterns for Time-Triggered Embedded
Systems" quite helpful, although it spans a rather large arc, and
scheduling algorithms are only one aspect it covers.

-- 
Hans-Bernhard Broeker (broeker@physik.rwth-aachen.de)
Even if all the snow were burnt, ashes would remain.

Marco Bleekrode wrote:
> Hi y'all
> 
> Quick but not so easy question (it may spawn a considerable thread...)
> We need to develop a cooperative multitasking kernel for various
> embedded platforms (See the implications and the complications?).
> One requirement is that c-functions should serve as "tasks". (Notably,
> these tasks perform very simple functions, e.g. polling push buttons,
> occasionally updating a display, polling an adc, and a whole slew of
> other things that are definitely not time critical.)
> The question is, how should cpu time be distributed, given the following:
>    Task 1: Priority 1
>    Task 2: Priority 1
>    Task 3: Priority 1
>    Task 4: Priority 1
>    Task 5: Priority 4
>    Task 6: Priority 8
> Should it be:
>    T6 T6 T6 T6 T6 T6 T6 T6 T5 T5 T5 T5 T1 T2 T3 T4... ad infinitum
> or:
>    T6 T5 T6 T5 T6 T5 T6 T5 T6 T1 T6 T2 T6 T3 T6 T4... ad infinitum
> or perhaps another scheme that does the assigned priorities right?
> A pointer would be very nice too, apart from an interesting discussion.
> None of us has a formal education in these matters... We are at a
> moderate loss...
> 

and since you said in a reply to another poster:

 >So true, nothing is more fun then re-inventing the wheel, however... 
 >the requirement is that it has to be absolutely system independent, 
 >and furthermore, real time is not an issue!But it has to have a 
small >footprint, no resource management, no i/o scheduling, whatsoever...
 >just the bare "switch"...

the problem becomes much simpler.  First, to be system independent we 
cannot use any timers so the key becomes what you define as priority. 
Assuming this means 'each time round the loop, do,if the highest 
priority task is ready to run then run it, else try the next highest 
prioity task, while there are tasks untried' then this is fairly easy 
to code.

Ian
-- 
Ian Bell

On Sun, 19 Sep 2004 14:22:37 +0200, "Marco Bleekrode"
<bleek004@hotmail.com> wrote:

>however... the requirement is
>that it has to be absolutely system independent,

How independent?  Without any code changes at all?  That is hard to
imagine.

A very simple completely self-contained cooperative multi-tasking
manager can be written in about 100 lines of assembler code.  I know
because I have done it.  This is hardly the size package that
established RTOS vendors are interested in selling.  You might have a
hard time buying such a small package of functionality without
bringing alone a lot of what you don't need.  The only thing my
cooperative multi-tasker does is manage separate stack pointers for
each task.  When any task calls suspend(), the next task is executed
from its saved PC and saved stack pointer.  A few registers are saved
as well.  I can't imagine doing this without some concession to the
differences between processors.  In particular, if the processer
doesn't have the ability to save the call stack (like low-end PICs),
it would be impossible, unless you restricted the tasks so that they
could only call suspend from the top level of their call stack - the
same level at which they received control.  If you are interested in a
x86 multi-tasker, I can send you the source code.  (Is does not
implement priority, though.  You would have to implement that some
other way.)



-Robert Scott
 Ypsilanti, Michigan
(Reply through this forum, not by direct e-mail to me, as automatic reply address is fake.)

On Sun, 19 Sep 2004 11:32:19 +0200, "Marco Bleekrode"
<bleek004@hotmail.com> wrote:

>Hi y'all
>
>Quick but not so easy question (it may spawn a considerable thread...)
>We need to develop a cooperative multitasking kernel for various
>embedded platforms (See the implications and the complications?).
>One requirement is that c-functions should serve as "tasks". (Notably,
>these tasks perform very simple functions, e.g. polling push buttons,
>occasionally updating a display, polling an adc, and a whole slew of
>other things that are definitely not time critical.)
>The question is, how should cpu time be distributed, given the following:
>   Task 1: Priority 1
>   Task 2: Priority 1
>   Task 3: Priority 1
>   Task 4: Priority 1
>   Task 5: Priority 4
>   Task 6: Priority 8
>Should it be:
>   T6 T6 T6 T6 T6 T6 T6 T6 T5 T5 T5 T5 T1 T2 T3 T4... ad infinitum
>or:
>   T6 T5 T6 T5 T6 T5 T6 T5 T6 T1 T6 T2 T6 T3 T6 T4... ad infinitum
>or perhaps another scheme that does the assigned priorities right?
>A pointer would be very nice too, apart from an interesting discussion.
>None of us has a formal education in these matters... We are at a
>moderate loss...

Your requirement is not clear to me. Why complicate a homebrew
cooperative multitasker with priorities? If the "tasks" are performing
"polling" of I/O, then  basically the tasks are doing nothing but
"waiting" (on an event) & so priority ranking of tasks may be
unnecessary. Unless you're designing a control system, in typical
systems the tasks are just sitting there waiting for an event, such as
an operator pushing a key or a door to operate a reed switch. Even in
motor controllers, the majority of software execution is initiated at
the sample rate.

Also by keeping the "RTOS" simple, it makes it much easier to test and
validate it for its intended use. By introducing priorities you
increase the use cases that you need to test by several orders of
magnitude -- bear in mind that it'll also make the (software) system
more susceptible to deadlock.

Ken.

>
>Thanks in advance
>
>Waldemar
>
>


+====================================+
I hate junk email. Please direct any 
genuine email to: kenlee at hotpop.com

On Sun, 19 Sep 2004 11:32:19 +0200, "Marco Bleekrode" <bleek004@hotmail.com>
wrote:

>We need to develop a cooperative multitasking kernel for various
>embedded platforms (See the implications and the complications?).

Various?

In any case, it's the features you need to describe well, I suppose.

>One requirement is that c-functions should serve as "tasks".

That's fine and I've done that many times.  This probably means (unless you
limit the time of C function) that you need to accept a variable number of
parameters.  What I've done before is to make the return address point to the
kill() function, so that the process self-kills when it finally returns.  That
may not be what you want, but it's one way of handling things.  And I also
placed (copied) the parameters sent to the create() function into the process
stack.  That way, when the function starts, it has access to the parameters in
the usual way (assuming that the parameters are passed via the stack, which is
not always the case -- sometimes registers are used for a few parameters.)

Keep in mind that various C compilers will not always use the same conventions,
even on the same processor technologies, so your cooperative switch() may need
to handle things differently on your 'various' platforms.  But it's really
trivial code, so having several incarnations isn't hard to do.

>(Notably,
>these tasks perform very simple functions, e.g. polling push buttons,
>occasionally updating a display, polling an adc, and a whole slew of
>other things that are definitely not time critical.)

Since you said this is "cooperative" I want to clarify that I take this to mean
"as opposed to pre-emptive."  This means that your 'push button polling' or
'display updating' will only take place when some other process gives up the CPU
to allow those processes to run -- the processor will not grab the CPU away
without first cooperating, if you keep this 'cooperative' in nature.  That can
be just fine for your application or it can be a real problem.  You will need to
decide that.

>The question is, how should cpu time be distributed, given the following:
>   Task 1: Priority 1
>   Task 2: Priority 1
>   Task 3: Priority 1
>   Task 4: Priority 1
>   Task 5: Priority 4
>   Task 6: Priority 8
>Should it be:
>   T6 T6 T6 T6 T6 T6 T6 T6 T5 T5 T5 T5 T1 T2 T3 T4... ad infinitum
>or:
>   T6 T5 T6 T5 T6 T5 T6 T5 T6 T1 T6 T2 T6 T3 T6 T4... ad infinitum
>or perhaps another scheme that does the assigned priorities right?

Priorities are usually not so relevant in cooperative systems.  When I use
cooperative methods, it's usually just a matter of switching to the next process
to give up a little time and that process, when it decides to, gives it up yet
again for the next, and so on.  By 'salting' each process with switch() calls at
appropriate places, things work well without any priorities involved.

If you honestly want priorities in cooperative switching, keep in mind that the
current process still doesn't yield up the CPU until it cooperates to do so,
regardless of priorities, since there is no pre-emption going on to allow the
O/S to yank away the CPU from the lower priority process.  Probably not much of
a problem, since the only way a higher priority process would take place would
be if the current process raises the priority of another process or creates a
new process of higher priority and, either way, the O/S can take control at that
'cooperative' point, I suppose.

I've not used priorities without also supporting pre-emption, so I cannot say I
fully appreciate why you need them.  Probably, the scheme you use should be
based on what you decide is important to you, not on my opinion, since you are
writing this for your own use.

>A pointer would be very nice too, apart from an interesting discussion.
>None of us has a formal education in these matters... We are at a
>moderate loss...

Read Douglas Comer's Operating System Design: The XINU Approach.  Very clear and
easy for neophyte O/S designers to use as a leg-up.

I should add that, at its core, a simple cooperative O/S does not require queues
or semaphores or priorities, etc.  Heck, you don't even have to support a
variable number of processes -- just a fixed set.  If so, just some modest
initialization code to set up the few stacks (if even that) and a single
switch() function that runs only a very few lines in assembly to save the
current register context, switch stacks, and then restore the saved context.
I've done this in as little as perhaps 20 assembly lines and almost no C code at
all, in a few cases.  It's really not very hard.  Of course, you are suggesting
that you want to use any c function to start a process so you will need a
create() call and there will be more code involved.  But as long as it stays
cooperative it won't be very difficult.

Best of luck,
Jon

On Sun, 19 Sep 2004 22:34:19 GMT, postmaster@noname.com (Ken Lee)
wrote:

>Your requirement is not clear to me. Why complicate a homebrew
>cooperative multitasker with priorities? If the "tasks" are performing
>"polling" of I/O, then  basically the tasks are doing nothing but
>"waiting" (on an event) & so priority ranking of tasks may be
>unnecessary.

I agree.

I've been writing and using cooperative schedulers for a
very long time in applications ranging from 4-axis bomb
disposal machines to embedded web servers. I have never
has to implement priority, although there have been
a few occasions in which it would have been useful.

The tools we use instead of priority are a timebase
mechanism (multiple slaved timers), and occasionally
an event triggering mechanism within the scheduler.
Our interrupt mechanics are completely separate from
the tasker. The design has been implemented on CPUs
ranging from 2 MHz Z80 to 200 MHz ARM.

Our design objectives have always been to get the
highest *useful* CPU work under heavy load. Under
these conditions the scheduler/OS is *all* wasted
cycles, so you should keep it as simple/fast as
possible. Under light load, the scheduler overhead
matters much less.

You certainly have to learn to use a lightweight
cooperative scheduler, but the benefits in resource
constrained systems can be impressive.

Steohen
--
Stephen Pelc, stephenXXX@INVALID.mpeltd.demon.co.uk
MicroProcessor Engineering Ltd - More Real, Less Time
133 Hill Lane, Southampton SO15 5AF, England
tel: +44 (0)23 8063 1441, fax: +44 (0)23 8033 9691
web: http://www.mpeltd.demon.co.uk - free VFX Forth downloads