cooperative multitasking scheme

Do you have a question? Post it now! No Registration Necessary

Translate This Thread From English to

Threaded View
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



Re: cooperative multitasking scheme
Quoted text here. Click to load it

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

Re: cooperative multitasking scheme
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"...

Quoted text here. Click to load it



Re: cooperative multitasking scheme
On Sun, 19 Sep 2004 14:22:37 +0200, "Marco Bleekrode"

Quoted text here. Click to load it

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

Re: cooperative multitasking scheme
Quoted text here. Click to load it

Very, very, very independent...

Quoted text here. Click to load it

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

Quoted text here. Click to load it



Re: cooperative multitasking scheme

Quoted text here. Click to load it

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

Re: cooperative multitasking scheme

Quoted text here. Click to load it


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

Quoted text here. Click to load it

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

Quoted text here. Click to load it

I understand that, thanks again.

BCNU

Waldemar



Re: cooperative multitasking scheme
no-one@dont-mail-me.com (Robert Scott) writes:

Quoted text here. Click to load it


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
We've slightly trimmed the long signature. Click to see the full one.
Re: cooperative multitasking scheme
On 23 Sep 2004 14:00:24 -0400, Grant Taylor

Quoted text here. Click to load it

The rules out implementing several tasks of equal priority, or else it
imposes an unnatural allocation of CPU time just to stay within the
rules of the game.  Another programmer I knew worked for months on a
cooperative multitasking scheme that used a single stack.  No matter
how he tried to order things, there were always cases of the stack
getting messed up.  He eventually gave up and implemented several
stacks.  Then everything worked beautifully.


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

Re: cooperative multitasking scheme
no-one@dont-mail-me.com (Robert Scott) writes:

Quoted text here. Click to load it


Goodness, no.  Task priority in this case is used only to select a set
of runnable tasks that will not introduce stack contention.  Task
priority is not used to decide how long or often to run anything.
There is no preemption or any other attempt at cpu resource
management.  It is obviously not a realtime system...

It is true that tasks of the same priority cannot wait for each other.
This is just as well, as they could then deadlock.  However, nothing
precludes the use of many tasks at the same priority level, and indeed
the application run over this schedule often has hundreds of tasks at
the same priority.

Tasks can only wait for a message response.  Since messages are
addressed with a (priority, number) tuple, it is easy to implement
runtime checks for illegal waits; it is also straightforward to
inspect the task source code for correctness.

The secondary restriction, implicit in the first, is that no task
being waited on may require input from a task with a priority number
<= to than the priority of the highest numbered task currently waiting
for the response.  This includes tasks being indirectly waited upon.
The runtime check for this is slightly trickier, but by no means hard;
code inspection to find such errors is admittedly more interesting.
In practice it is easier to work from a more restrictive but less
complex rule: all code which responds to a request being waited on
should only require interaction with tasks of priority >= to self.
This artificial restriction makes static checking less difficult.


Quoted text here. Click to load it

Well, he must have missed something.  The executive I wrote to do this
most certainly works, and it really is possible to develop nontrivial
applications atop it.  Furthermore it is easy to understand the
application in a debugger, which was the whole point :)

--
Grant Taylor
Embedded Linux Consultant
We've slightly trimmed the long signature. Click to see the full one.
Re: cooperative multitasking scheme
You can download the sources of a prototype from
http://home.wanadoo.nl/bleek004 /
as to get an idea of what I'm aiming at.

Waldemar



Re: cooperative multitasking scheme

Quoted text here. Click to load it

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



Re: cooperative multitasking scheme
Quoted text here. Click to load it

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.

Quoted text here. Click to load it

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

Quoted text here. Click to load it

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

Quoted text here. Click to load it

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



Re: cooperative multitasking scheme

Quoted text here. Click to load it

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

Quoted text here. Click to load it

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

Re: cooperative multitasking scheme
Jon, thanks for your extensive treatise of the matter.

You can download the sources of a prototype from
http://home.wanadoo.nl/bleek004 /
as to get an idea of what I'm aiming at.

Waldemar



Re: cooperative multitasking scheme

Quoted text here. Click to load it

I've only looked at the page, itself.  No download.  Where is 'AddTask()?'

Jon

Re: cooperative multitasking scheme

Quoted text here. Click to load it

Hi

My fault... I forgot to repace the '<' by '&lt'. Should be OK now...
No download? You mean you can't download the zip or you
didn't download?

Waldemar




Re: cooperative multitasking scheme

Quoted text here. Click to load it

I didn't try to download anything -- I decided to simply look at what was
present on the web page.

So, you use setjmp/longjmp as a mechanism to get back to the call frame of
schedule() and, when running a process again, simply call it.  I don't consider
this very useful as a process loses it's local context anytime it exits (whether
by a longjmp or simply returning) and is always restarted at the top.  This
isn't my idea of a cooperative switcher.

But perhaps I missed some detail.

Jon

Re: cooperative multitasking scheme

Quoted text here. Click to load it

There's no other "clean" way to get back to the scheduler, unless you want
to
call it recursively and that's exactly *not* what I want to do (especially
not on
a microcontroller with very limited stack space, apart from the fact that
the
scheduler needs to know that it was called recursively and instead of keep
on looping needs to return, i.e. more overhead.) The idea behind it is that
a task should keep track of what state it was in (which is common practice)
and once a task gives up control of the cpu from whatever level of function
nesting, a complete steck roll up is in order. I agree that loosing the
local
context may pose a problem, but then again, the size and complexity of
the tasks will be limited.

Waldemar



Re: cooperative multitasking scheme

Quoted text here. Click to load it

I don't think that is common terminology to call that a "task".  In
most implementations of a "multi-tasking executive", even the
cooperative variety, a task is a fairly general thread of execution
whose place in the code is preseved through interruptions for
CPU-sharing.  I'll grant you that most small microcontrollers don't
have the facilities to implement separate stacks, but that is no
reason to call something a "multi-tasker" when it isn't.  I would say
that the kind of tasks that you are describing are really state
machines.  That is the kind of task that always starts at the top of a
loop, and whose state is kept in ways other than by the program
counter.  That certainly doesn't describe most "tasks".  So what you
have implemented you should call an "executive for the cooperative
management of parallel state machines".


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

Site Timeline