cooperative multitasking scheme

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.)
[Stuff Snipped]

Hi,

Have a look at "Multi-C" from MiX software. The book that 
accompanies the software discusses the basics of multi-threading
and I think they basically implement what you want.
http://www.mixsoftware.com

Regards
   Anton Erasmus

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

Very, very, very independent...

> 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.)

Thanks for the offer, but alas... Assembler is not what I would call
system independent. Nope, it has to be C and that's hard... Right
now I have a prototype compiling flawlessly in Metrowerks
Codewarrior HC08, Imagecraft AVR, and HiTech for the PICC.
The �nterface seems clean enough and the code is fairly predictable
in its behaviour...

Waldemar

"Robert Scott" <no-one@dont-mail-me.com> schreef in bericht 
news:414db129.1213455@news.provide.net...
> 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.) 

> You must first define what you want priority to mean.

Priority in this particular case determines the order in which a task
receives control over the cpu as well as the number of times within
the period it takes to execute all tasks that are actively competing
for cpu control.

> 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.

Nope, just the other way around, but that is IMHO not relevant.

> 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

Well, an excact percentage cannot easily be determined, since we deal
with a cooperative multitasker. In fact, a low priority task could simply
block the whole kaboodle by going into an infinite loop (Remember e.g.
Windows 3.x?) It's up to the programmer to design tasks in such a way
that they give up cpu control after they've done their thing. Furthermore,
it's the programmer's responsibilty to assign priorities such that more
important functions are executed more often...

> 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).

Indeed, a waiting task does not actively compete for cpu time, but it gets
a priority boost. The same goes for a suspended or delaying task. In fact
the schedulder is an attempt to mimich the behaviour of it's pre-emptive
brethren...

Thanks for your input

Waldemar

> The question is, how should cpu time be distributed

If you were given the order to implement the scheme you outlined,
implement it as is.

If you are supposed to serve the keyboard and LCD in a multitasking
system, dont try to make them fit your multitasking scheduler. Rather
make the scheduler fit the keyboard and LCD requirements!  

A human operator wont type more than 5-10 keys per second.  Therefore
keyboards usually are polled at 50 Hz rate, or similar.  Install a
timer interrupt or task at this rate, and give the rest of the CPU
to whatever other task wants it.  It makes no sense to poll the keyboard
more often, just because your scheduling algorithm decides that its
time for priority level X.

The LCD, unless its a controller-less type, isnt a multitasking item
either.  Usually, when a task produces LCD output, it can be visualized
immediately.  Delaying it only makes sense when the task cannot take
a break from what its doing.  In simple devices, such tasks are
implemented as interrupt functions that modify status variables, which
then are visualized in the main loop.  Such loops dont need to run at
high rate either, a) because LCDs dont visualize at more than 5-10 Hz
anyways, and b) because human operators can not percieve the data when
its updated faster.  Numeric data for example should be stable for at
least 1/2 sec, preferably more.

You see, depending on your application, the LCD is best served within
the very task that produces the output (using its CPU time instead of
a separate LCD task), or in a task with fixed timing (eg 1 Hz).  No
priority scheduling needed either.

I could go on, but Im not designing your product.  You should analyse
exactly what the tasks are supposed to do, and when and why.  The
implementation then becomes obvious, and Im almost sure that it wont
involve priority-scheduling at all.  You probably can do completely
without multitasking, using just interrupts and the main loop.  Or
you do just two tasks, one for the hard work and one for the MMI,
and assign absolute priority either to the MMI if you can, or to the
hard work task when there is no way around it (no priority scheduling
either).

Marc

On Thu, 23 Sep 2004 11:51:22 +0200, "Waldemar" <bleek004@hotmail.com>
wrote:

>> How independent?  Without any code changes at all?  That is hard to
>> imagine.
>
>Very, very, very independent...
>
>> 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.)
>
>Thanks for the offer, but alas... Assembler is not what I would call
>system independent. Nope, it has to be C and that's hard... Right
>now I have a prototype compiling flawlessly in Metrowerks
>Codewarrior HC08, Imagecraft AVR, and HiTech for the PICC.
>The &#4294967295;nterface seems clean enough and the code is fairly predictable
>in its behaviour...

Does it allow tasks to give up control at various levels in the call
stack?  If so, then the multi-tasker must be able to manage separate
stacks for each task.  There is no C primitive that deals directly
with switching stacks, unless it is something akin to longjump().
Does your C-only multi-tasker use longjump() to implement stack
switching?

On the other hand, if you impose the rule that a task may give up
control only if it is at the top of its call stack, then perhaps a
multi-tasker can be written in C only.  You would only need a list of
function pointers, which are supported in C.  But all the tasks would
share a single call stack.  In most of the applications that I have
worked on, that would be a serious restriction.

My offer of the x86 assembler code was not meant as something you
would use directly, but merely as an aide to seeing what minimum
functionality is required in a cooperative multi-tasker.


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

"Robert Scott" <no-one@dont-mail-me.com> schreef in bericht 
news:4152afa5.961351@news.provide.net...
> On Thu, 23 Sep 2004 11:51:22 +0200, "Waldemar" <bleek004@hotmail.com>
> wrote:

> Does it allow tasks to give up control at various levels in the call
> stack?  If so, then the multi-tasker must be able to manage separate
> stacks for each task.  There is no C primitive that deals directly
> with switching stacks, unless it is something akin to longjump().
> Does your C-only multi-tasker use longjump() to implement stack
> switching?

To answer your first question, yup, it does allow that through the use
of setjmp()/longjmp(). Calls like Wait(), Stop(), etc. utilize the
longjmp() to pass control back to the scheduler. However,
there's no way to get back to the point right after the call to e.g.
Wait(). It's up to the task to remember what it did just before it
invoked the Wait().
As to your second remark/question... Well, actually one doesn't
have to manage separate stacks in this case, because when a task
gives up control of the cpu, either through a normal return or
through the use of a longjmp(), the stack is cleaned up to the point
where this task was invoked by the scheduler. But you can
manipulate the stack pointer through the use of setjmp(). After
its initial call (when it returns 0), the jmp_buf structure is filled
with the program counter and the stack pointer. At that stage
you may assign a different value to the stack pointer, i.e. the
address of some byte array to serve as the task's private stack.
Nope, no stack switching. I could have done that, but I decided
against it, given the fact that most 8 bit microcontrollers have
only limited amounts of RAM. I  left other ramifications for what
they were...

> On the other hand, if you impose the rule that a task may give up
> control only if it is at the top of its call stack, then perhaps a
> multi-tasker can be written in C only.  You would only need a list of
> function pointers, which are supported in C.  But all the tasks would
> share a single call stack.  In most of the applications that I have
> worked on, that would be a serious restriction.

That is indeed what I did... pointer to functions...
Actually, this isn't much of a limitation, not for the kind of applications
I have in mind... Think of educational purposes (push a button, flash a
 light), thermometer, nothing fancy...

> My offer of the x86 assembler code was not meant as something you
> would use directly, but merely as an aide to seeing what minimum
> functionality is required in a cooperative multi-tasker.

I understand that, thanks again.

BCNU

Waldemar

"Hans-Bernhard Broeker" <broeker@physik.rwth-aachen.de> schreef in bericht 
news:2r5jpuF15hmi7U1@uni-berlin.de...

> Quite impossible to say, from your problem description.  I would actually
> suggest, for this particular case:
>
> T6 T5 T6 T5 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.


That's the scheme I've implemented.

> 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.

Priority is determined as the order of task execution as well as the
amount of cpu time a task gets within the period of all tasks getting
at least once control of the cpu.

> 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.

I managed to google up a copy.

Thanks

Waldemar 

"Ian Bell" <ruffrecords@yahoo.com> schreef in bericht 
news:cika5r$h3c$1@slavica.ukpost.com...

> 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.

Right, no interrups, no timers, everything polled (for now). And the
loop, that's what I started with... but choosing the right scheme.
The picture is quite complete now.

Thanks

Waldemar 

On Thu, 23 Sep 2004 12:10:22 +0200, "Waldemar" <bleek004@hotmail.com> wrote:

>Priority in this particular case determines the order in which a task
>receives control over the cpu as well as the number of times within
>the period it takes to execute all tasks that are actively competing
>for cpu control.

Tried to parse this several times and I' still not sure I understand.
So, combining it now with an earlier comment:

>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?

If I gather what you are saying, it's a new use of the term 'priority' to which
I haven't been exposed.  But I can see the utility in the idea, if I gather
where you are going.

Do you mean that, given the above list of 6 tasks, there are 8+4+4*1 = 16 total
switch events before it repeats?  So that you want to execute T6 8 times out of
16, T5 4 times out of 16, and t1 through T4 each 1 time out of 16?

If so, and if I'm generally understanding you, then I think you'll need to come
up with your own algorithm on this.  I don't believe there is a standard here.

One suggestion that comes to mind would be to use a delta queue arrangement with
integer deltas.  When a process is inserted into the queue, it is inserted based
on an assigned delta value for that process, as in:

void insert( pid_t proc, int delta ) {
   for each process (p) currently in the queue, (may be zero)
      if p.delta <= delta then
         delta -= p.delta;
      else {
         p.delta -= delta;
         insert proc with current delta value before (p) in the queue;
         return;
      }
   add proc to end of the queue with current delta value
   return;
}

For example, if the queue holds only one current process with a delta value of 7
and you try and insert a process with a specified delta of 3, that new process
will be at the top of the queue with a delta of 3 and the previously sole entry
will be moved to the end with a new delta value of 4.  This last process (of the
two) still has a total (net) delta of 7, because it is the sum of all the prior
deltas in the queue.  Do you see how that works?

When you perform a switch and execute a process for a time, you always take the
top entry from the queue and re-insert it back using the above algorithm with a
fixed delta value that is assigned to that process.  When that process calls the
switch algorithm, the switch simply takes again the top entry in the queue to
run and again re-inserts that one back using, again, a fixed delta assigned to
it.

That leaves computing the delta assignments for each process to be figured out.
That is done by first multiplying all of your existing priorities together and
then dividing that by each priority assignment and finding the GCD of all those
resulting values.  Then, you divide the product of the existing priorities by
this GCD value and making that a numerator and using the priority assignment of
each process as the denominator.  The resulting computation is the delta.

For example, with your priorities mentioned earlier, the product of all of them
is 32 (1*1*1*1*4*8).  32 is then divided by each priority, giving
(32,32,32,32,8,4).  You now find the GCD of these values, which is 4.  So divide
32 by 4 to get 8.  Now, taking each priority and divide it into 8, giving
(8,8,8,8,2,1).  Those are your delta values:

  T1 8
  T2 8
  T3 8
  T4 8
  T5 2
  T6 1

If you already know the number of processes and the desired priorities, you can
code those numbers at compile time and be done with it.  If you have no idea
what the priorities are or how many processes there will be in the queue at any
given time and want to assign the process priorities at run time, you'll need
some code to go through the list of active processes and generate run-time delta
value assignments for re-insertion.

Depending on how your processes are initially inserted, your example might
produce a sequence like:

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

The above sequence was generated by using some actual simulation code I just
wrote in BASIC.  Another possible sequence (different initialization, same delta
values) it generated was:

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

I think that meets what you are suggesting, if I got it right.

Jon

no-one@dont-mail-me.com (Robert Scott) writes:

> Does it allow tasks to give up control at various levels in the call
> stack?  If so, then the multi-tasker must be able to manage separate
> stacks for each task.  There is no C primitive that deals directly
> with switching stacks, unless it is something akin to longjump().
> Does your C-only multi-tasker use longjump() to implement stack
> switching?

> On the other hand, if you impose the rule that a task may give up
> control only if it is at the top of its call stack, then perhaps a
> multi-tasker can be written in C only.  You would only need a list
> of function pointers, which are supported in C.  But all the tasks
> would share a single call stack.  In most of the applications that I
> have worked on, that would be a serious restriction.

One man's restriction is another man's salvation...

I've built this sort of runtime before, one which operates many tasks
on one stack, with a recursively invokable scheduler (ie a call like
"yield").  It was an incredibly delightful way to debug what was, on
the target, a fully concurrent distributed system.  Debugger support
for multitasking schemes with multiple switchable stack or register
contexts, where it even exists, is just nowhere near as easy to deal
with.

The necessary restriction is an ordinary strict priority scheme -
assign each task a priority number and allow tasks to wait only on
tasks of higher priority.  (This is easy with message-passing,
probably so with other schemes).

The nice thing about this arrangement is that the restrictions which
eliminate stack contention in the monolithic cooperative environment
also happen to eliminate deadlock in the distributed concurrent
environment.  It's always nice to kill two birds with one stone.
Particularly when you can determine that the birds are indeed dead
with nothing more than static analysis ;)


The other portable choice is to insist that all task functions run for
only a short time, and not provide preemption or a yield() type of
call.  This is, of course, the usual "while(1)" scheduler.  Calling
*this* a restriction is in the eye of the beholder; the world is full
of systems that run this way.

-- 
Grant Taylor
Embedded Linux Consultant
http://www.picante.com/