cooperative multitasking scheme

On 23 Sep 2004 14:00:24 -0400, Grant Taylor
<gtaylor+carchemb_fcbgj092304@picante.com> wrote:

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

Waldemar <bleek004@hotmail.com> wrote:
> "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.

That's not saying anything.  You say "priority is determined", but
that's not what I asked about: it's not how you choose the priorities,
but what the scheduler is supposed to *do* with them that you have
design.  That's what the "meaning" of a priority is.  

And you can't generally control two independent aspects (order of
calling, and CPU usage) by a single number.  Actually in a cooperative
scheduler the priority cannot possibly control CPU usage --- that's
why it's called "cooperative".  If a task forgets to give up the CPU,
it'll have it forever.  Priorities have nothing to do with that, and
they can't.

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

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

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

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.


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

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
http://www.picante.com/

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

> That's not saying anything.  You say "priority is determined", but
> that's not what I asked about: it's not how you choose the priorities,
> but what the scheduler is supposed to *do* with them that you have
> design.  That's what the "meaning" of a priority is.
>
> And you can't generally control two independent aspects (order of
> calling, and CPU usage) by a single number.  Actually in a cooperative
> scheduler the priority cannot possibly control CPU usage --- that's
> why it's called "cooperative".  If a task forgets to give up the CPU,
> it'll have it forever.  Priorities have nothing to do with that, and
> they can't.

What's in a name?  ;-)   Perhaps my choice of the term "priority" wasn't
quite what it should be, for lack of a better word. However, the whole
purpose of this excercise was to try and mimic the behaviour of an RTOS
as close as possible, without having to use interrupts (which are inherently
system dependent. Remember that the kernel has to be system independent).
The thing I call "priority" does control the sequencing of tasks almost as 
an
RTOS does.
Of couse, and in that I fully agree, the kernel can only work properly if
tasks give up control of the cpu voluntarily. And that's what they will do,
either by waiting for a message from another task, excluding themselves
for a given number of times from competng for cpu control, or suspending
themselves until resumed by another task.

BCNU

Waldemar 

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 

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 

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 

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 

On Sat, 25 Sep 2004 12:52:08 +0200, "Waldemar" <bleek004@hotmail.com> wrote:

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

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

Jon

"Jonathan Kirwan" <jkirwan@easystreet.com> schreef in bericht
news:5bpal05uuiojc836b802viev5mson9a84e@4ax.com...
> On Sat, 25 Sep 2004 12:52:08 +0200, "Waldemar" <bleek004@hotmail.com>
> wrote:
>
>>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.
>
> I've only looked at the page, itself.  No download.  Where is 'AddTask()?'
>
> Jon

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