Cooperative multitasking OS-??
ssubbarayan
Sorry if this sounds novice.I would like to really understand whats
meant by Cooperative multitasking OS?I read another thread in this
group which was explaining about the advantages and disadvantages it
has over a preemptive system.
From what I understood going through the discussion,Cooperative to me
looks like FIFO scheduling mechanism.
Can any of you throw some light on this or provide some links to
understand about this concept?I hit google and wikipedia but did not
get a satisfactory explaination.
Wikipedia IIRC says,Cooperative multitasking systems existed during
pre win9xOS days and non existant almost in current scenerio.Is this
true?
How different is this Cooperative system from roundrobin or FIFO?How
does the OS kernel decide which task/process to promote at any point
of time?
What sort of applications need cooperative functionality?
Looking farward for all your replies,
Advanced thanks to all,
Regards,
s.subbarayan
Arlet Ottens
I don't know if everybody uses the same definition, but I've recently
implemented what I call a cooperative scheduler. Just like a preemptive
scheduler, there's a list of tasks with priorities. When the scheduler
is called, it picks the runnable task with the highest priority to run.
The only real difference with a preemptive kernel is that the selected
task will run until it blocks itself and calls the scheduler again. If
an interrupt unblocks a higher priority task, it will have to wait. This
requires some discipline from the programmer to make sure none of the
tasks run for excessive amounts of time between two calls to the scheduler.
The advantage is that you don't to worry about shared data between
tasks. The only time you need to use semaphores is when you actually
want to sleep in a critical section. Priority inversion is also less of
a problem. For me, an additional advantage is that it requires less
memory to save the context (i.e. the stack), because tasks are only
switched at well defined points.
The disadvantage is of course that high priority tasks don't always get
to run right away. In some cases, this can be mitigated by doing more in
the interrupt handler itself, such as putting incoming data in a FIFO.
Grant Edwards
> Sorry if this sounds novice.I would like to really understand
> whats meant by Cooperative multitasking OS?
It means that a task runs until it explicitly and voluntarily
yeilds.
> From what I understood going through the
> discussion,Cooperative to me looks like FIFO scheduling
> mechanism.
No. The scheduling algorithm can be anything.
> Wikipedia IIRC says,Cooperative multitasking systems existed during
> pre win9xOS days and non existant almost in current scenerio.Is this
> true?
Yes.
> How different is this Cooperative system from roundrobin or FIFO?
You're confusing the scheduling method that decides
who to run next with the method that decides when to switch to
the next task. The two are more-or-less independant.
> How does the OS kernel decide which task/process to promote at
> any point of time?
Irrelevent to the question of cooperative vs. pre-emptive
multitasking. "Cooperative" refers to the decision on _when_
to switch to the next task. It has nothing to do with deciding
_who_ the next task is going to be.
> What sort of applications need cooperative functionality?
Cooperative multi-tasking can have less overhead than
pre-emptive multt-tasking, so it's ofen used in more resource
limited situations.
--
Grant Edwards grante Yow! I need to discuss
at BUY-BACK PROVISIONS
visi.com with at least six studio
SLEAZEBALLS!!
Eric Smith
> Wikipedia IIRC says,Cooperative multitasking systems existed during
> pre win9xOS days and non existant almost in current scenerio.Is this
> true?
No. Many embedded systems use cooperative multitasking (also known
as the "run to completion" model).
Cooperative multitasking is less practical for systems that are intended
to run workloads that haven't been well-characterized in advance, e.g.,
general purpose desktop computers. But where the problem is well-known,
cooperative multitasking can work quite well, and tends to be easier to
debug.
FreeRTOS.org
> as the "run to completion" model).
Terminology again. To me "run to completion" is something quite different
to cooperative multitasking. Old Windoze systems did not use run to
completion.
Run to completion systems are very simple/basic (which is not necessarily a
bad thing) whereby once a task function starts it continues to the end of
its function with no possibility of it stopping to allow a different task to
run. When it starts again it starts from the beginning of its function
again - although it may then branch to any point in the function.
In a cooperative system a task can volunteer to yield at any point the
programmer sees fit. By yielding it is allowing a different task to run.
The big difference then is that when the task starts executing again it
commences from exactly the point from where it yielded.
Pre-emptive on the other hand does not require the task to yield (volunteer
to give up execution), the task can be stopped at any time the scheduler
sees fit and without the knowledge of the task being pre-empted. This could
be in response to a temporal event, external event, or internal event.
As already mentioned by Grant, 'Round Robin' is another issue altogether.
I think there are many texts that describe all these concepts.
--
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.
Robert Adsett
> ssubbarayan <ssu...@gmail.com> writes:
> > Wikipedia IIRC says,Cooperative multitasking systems existed during
> > pre win9xOS days and non existant almost in current scenerio.Is this
> > true?
>
> No. Many embedded systems use cooperative multitasking (also known
> as the "run to completion" model).
Run to completion can be either co-operative or pre-emptive. Run to
completion usually runs in a single stack (although multiple stacks
could be used)
Three properties of RTOS that are pretty well independent
Pre-emptive vs cooperative
Run to completion vs continuously running
round-robin vs prioritized (1)
memory protection or lack of (many systems don't have the HW to
support this)
There are other characteristics as well, not all of them completely
independant or as easily categorized.
centrality of clock to the implementation
single or multiple stacks
use of privledged modes
....
Robert
1 - I can imagine other possibilities such as random scheduling, but
I've not heard of any system that doesn't fit one of these two patterns.
It would be interesting to know if there were any and why if they do
exist.
--
Posted via a free Usenet account from http://www.teranews.com
Wim Lewis
ssubbarayan <ssu...@gmail.com> wrote:
>Sorry if this sounds novice.I would like to really understand whats
>meant by Cooperative multitasking OS?I read another thread in this
>group which was explaining about the advantages and disadvantages it
>has over a preemptive system.
>From what I understood going through the discussion,Cooperative to me
>looks like FIFO scheduling mechanism.
The scheduling mechanism is a separate thing from the cooperative/preemptive
distinction. You can use various kinds of schedulers with either kind
of task switching.
In a cooperative system, each task is responsible for periodically
calling a routine in the operating system which will suspend the
calling task and tell the scheduler to run another task. (On some
OSs, *any* operating system call can have this effect. On other
OSs, it's a specific routine, frequently named "yield".) If a task
enters a loop and doesn't call the yield routine, it will monopolize
the processor indefinitely. With a preemptive OS, there is a hardware
timer which will eventually interrupt the running task and transfer
control to the scheduler, which will decide which task to run next.
In other words, in a cooperative system, the tasks have to explicitly
cooperate in order to share the use of the processor.
>Wikipedia IIRC says, Cooperative multitasking systems existed during
>pre win9xOS days and non existant almost in current scenerio.Is this
>true?
Sort of. All modern desktop operating systems use preemptive
multitasking among applications. But within a single program, it's
very common to use an event-loop style of programming, which is a
form of cooperative multitasking. In embedded systems, especially
small ones, cooperative multitasking is still common.
--
Wim Lewis <wi...@hhhh.org>, Seattle, WA, USA. PGP keyID 27F772C1
Jack Klein
<ssu...@gmail.com> wrote in comp.arch.embedded:
I am cross-posting this to comp.realtime, since I cross-posted the
original thread there, and certainly some replies came from there.
> Dear experts,
>
> Sorry if this sounds novice.I would like to really understand whats
> meant by Cooperative multitasking OS?I read another thread in this
> group which was explaining about the advantages and disadvantages it
> has over a preemptive system.
If you go back and read the original post in that thread, you will see
that it describes what is almost certainly the simplest of all
cooperative systems, the "super loop". I know that, because I wrote
that original post, two weeks ago.
> From what I understood going through the discussion,Cooperative to me
> looks like FIFO scheduling mechanism.
The super loop is not FIFO, but purely round-robin. It looks like
this:
void super_loop(void)
{
for ( ; ; )
{
task_1();
task_2();
/*...*/
task_N();
}
}
Each task is called in order, every time. Typically, the task
maintains an internal state machine, and if it is in an idle state, it
looks for new events that it must do something about. Once a task has
finished its current business (if any), it returns and the loop calls
the next task.
Technically, this is "cooperative" "run to completion" "round-robin".
It is "cooperative" because a task is never preempted, except by
interrupts. It runs until it is ready to voluntarily stop running,
and only then does another task get to run.
It is "run to completion" because the only way the task gives up
execution is by executing a return, completely exiting its main
function. There is no "yield" call that a task can make somewhere in
the middle of its code to give up execution, to be resumed at that
point later.
The big advantage of the combination of "cooperative" and "run to
completion" is that there only needs to be one stack, at least for
foreground tasks. When a task returns to the super_loop(), it
releases all of the stack space used for its return address, its local
variables, and the return addresses and local variables of any nested
internal functions that it has.
Even tasks that are cooperative but are not run to completion, that is
like tasks in older versions of Windows that were supposed to call
PeekMessage() or some such named function if they performed long
operations, have a stack foot print that must be preserved.
In a fully preemptive system, where a task can be suspended at any
arbitrary time, there is usually even more to be preserved so that the
task can later resume in exactly the same state.
For many simple situations, the super loop is more than good enough.
It does have one disadvantage though. It violates some of the primary
rules of "high performance" "efficient" real time systems, namely:
1. A task that has nothing to do should do nothing.
2. A task that does nothing should take no time doing nothing.
The simple super loop violates these rules because each task's entry
point is called on each pass of the loop. Typically, the entry point
checks the state of its state machine. If it is idle, then it calls
some lower level driver (perhaps the serial port driver to see if data
has been received, or a timer driver to see if a certain amount of
time has passed). If it is idle and has no new events from drivers or
other tasks, it has nothing to do so it exits.
But it broke the two rules because even though it had nothing to do,
it had to execute code to find out that it had nothing to do, breaking
rule 1. And because it had to execute code, it certainly took time
doing it, breaking rule 2.
> Can any of you throw some light on this or provide some links to
> understand about this concept?I hit google and wikipedia but did not
> get a satisfactory explaination.
> Wikipedia IIRC says,Cooperative multitasking systems existed during
> pre win9xOS days and non existant almost in current scenerio.Is this
> true?
That may be true in desktop operating systems, it is most certainly
not true in many embedded systems.
> How different is this Cooperative system from roundrobin or FIFO?How
> does the OS kernel decide which task/process to promote at any point
> of time?
As others have pointed out, the issue here is not the "cooperative"
part, or the "run to completion" part, but the super_loop() function
that is "round-robin". That is because it goes around and around,
calling all the same functions in the same order every time.
If the super loop had a way of knowing whether or not each task had a
need to do something, and only called the ones that did, it could be
more efficient.
void super_loop(void)
{
for ( ; ; )
{
if (work_for_task_1) task_1();
if (work_for_task_2) task_2();
/*...*/
if (work_for_task_N) task_N();
}
}
...and finally, the super could be priority based instead of
round-robin. The simplest way to do this is if each task has a fixed
priority, and they are arranged in order of the priority.
void super_loop(void)
{
for ( ; ; )
{
if (work_for_task_1) task_1();
else if (work_for_task_2) task_2();
/*...*/
else if (work_for_task_N) task_N();
}
}
...so it will execute the first task that actually has a need for
execution time, then start back at the top of the list. That means
that if task_2 and task_3 are both ready, task_2 is run. If task_2
does something that makes task_1 ready to run, the super loop, which
has now become worthy of being called a scheduler, starts at the top
of the loop and runs task_1 on the next pass, before running task_3.
> What sort of applications need cooperative functionality?
Applications that run in very tight constraints in terms of resources,
including RAM in general, or just RAM that can be used for stacks. Or
systems that can't afford the overhead of context switches.
> Looking farward for all your replies,
>
> Advanced thanks to all,
There are other possibilities for cooperative multitasking systems
that I haven't even begun to describe here. But it should give you
something to think about for now.
--
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
Marra
in the early 1980's.
This was before Bill Gates got into it.
Its a shame I didnt patent it !
CBFalconer
I had the Data Acquisition 512 multitasking in native code in
1965. You can see the machine and its programming language (more
or less) at:
<http://cbfalconer.home.att.net/firstpc/>
Your patent would have been invalid for prior use. So would mine.
--
Chuck F (cbfalconer at maineline dot net)
<http://cbfalconer.home.att.net>
Try the download section.
ssubbarayan
> > No. Many embedded systems use cooperative multitasking (also known
> > as the "run to completion" model).
>
> Terminology again. To me "run to completion" is something quite different
> to cooperative multitasking. Old Windoze systems did not use run to
> completion.
>
> Run to completion systems are very simple/basic (which is not necessarily a
> bad thing) whereby once a task function starts it continues to the end of
> its function with no possibility of it stopping to allow a different task to
> run. When it starts again it starts from the beginning of its function
> again - although it may then branch to any point in the function.
>
> In a cooperative system a task can volunteer to yield at any point the
> programmer sees fit. By yielding it is allowing a different task to run.
> The big difference then is that when the task starts executing again it
> commences from exactly the point from where it yielded.
>
> Pre-emptive on the other hand does not require the task to yield (volunteer
> to give up execution), the task can be stopped at any time the scheduler
> sees fit and without the knowledge of the task being pre-empted. This could
> be in response to a temporal event, external event, or internal event.
>
> As already mentioned by Grant, 'Round Robin' is another issue altogether.
>
> I think there are many texts that describe all these concepts.
>
> --
> Regards,
> Richard.
>
> 14 official architecture ports, 1000 downloads per week.
>
> Certified by TÜV as meeting the requirements for safety related systems.
In a cooperative system a task can volunteer to yield at any point
the
> programmer sees fit. By yielding it is allowing a different task to run.
> The big difference then is that when the task starts executing again it
> commences from exactly the point from where it yielded.
Hi,
Can you please explain in the above situation where would the context
information be stored so that it could be restored back?In another
thread related to this topic,it was discussed that context information
would not be stored as in pre emptive statements.When its possible to
restore the execution from the point left,I believe definitely storing
context information is must for cooperative systems.
I would appreciate your/any of your comments on this,
Regards,
s.subbarayan
ssubbarayan
Jack,
Thanks for your clear explaination.I am summarising what I understood
on cooperative system from this and how this could be implemented:
1)Create tasks with priority assigned.Based on the priority they would
execute, the main difference wrt pre emptive system being,while
preemptive systems allow the executing task to be preempted in
between,our cooperative system does not do it.
2)Once the executing task finishes execution,it releases the cpu for
the next priority task to execute.
3)Incase of interrupts,the current task would be interrupted and
resumed back.
4)The current task can leave the CPU only by itself.
5)Once the current task releases the CPU,the task with next lower
level of priority with respect to current completed task would be
promoted to execution.
6)Only missing link for me is about context switching.Where exactly
would be the context information stored in such systems?Even if not
with in tasks,between interrupts and tasks atleast,there should be way
to restore context information so that the interrupted task can
execute from the point it was interrupted.
It would be of great help to me if you could correct me incase I am
wrong and help to understand the 6th point.
Looking farward for your replies,
Regards,
s.subbarayan
Arlet Ottens
> Jack,
> Thanks for your clear explaination.I am summarising what I understood
> on cooperative system from this and how this could be implemented:
>
> 1)Create tasks with priority assigned.Based on the priority they would
> execute, the main difference wrt pre emptive system being,while
> preemptive systems allow the executing task to be preempted in
> between,our cooperative system does not do it.
> 2)Once the executing task finishes execution,it releases the cpu for
> the next priority task to execute.
> 3)Incase of interrupts,the current task would be interrupted and
> resumed back.
> 4)The current task can leave the CPU only by itself.
> 5)Once the current task releases the CPU,the task with next lower
> level of priority with respect to current completed task would be
> promoted to execution.
> 6)Only missing link for me is about context switching.Where exactly
> would be the context information stored in such systems?Even if not
> with in tasks,between interrupts and tasks atleast,there should be way
> to restore context information so that the interrupted task can
> execute from the point it was interrupted.
>
> It would be of great help to me if you could correct me incase I am
> wrong and help to understand the 6th point.
The easiest way to store the context is to push it all on the stack,
save the stack pointer, load the stack pointer for the next task, and
pop its context from the stack.
This requires a separate stack for each task of course.
Robert Adsett
> ssubbarayan wrote:
> > Jack,
> > Thanks for your clear explaination.I am summarising what I understood
> > on cooperative system from this and how this could be implemented:
>
> > 1)Create tasks with priority assigned.Based on the priority they would
> > execute, the main difference wrt pre emptive system being,while
> > preemptive systems allow the executing task to be preempted in
> > between,our cooperative system does not do it.
For this particular example that's true. Some co-operative systems
allow context switching at any OS call (actually many OS facilities
require it) such as blocking blocking on a sempahore or setting a
semaphore flag. Even in run to completion systems that can be true
although in that case blocking is usually not allowed.
> > 2)Once the executing task finishes execution,it releases the cpu for
> > the next priority task to execute.
> > 3)Incase of interrupts,the current task would be interrupted and
> > resumed back.
> > 4)The current task can leave the CPU only by itself.
???? Sorry, that point doesn't parse.
> > 5)Once the current task releases the CPU,the task with next lower
> > level of priority with respect to current completed task would be
> > promoted to execution.
Possibly, in a run to completion system that doesn't allow tasks to
give up control during execution the next task may actually be a
higher priority than the current task. The key is the ready task with
the highest remaining priority runs next.
> > 6)Only missing link for me is about context switching.Where exactly
> > would be the context information stored in such systems?Even if not
> > with in tasks,between interrupts and tasks atleast,there should be way
> > to restore context information so that the interrupted task can
> > execute from the point it was interrupted.
>
> > It would be of great help to me if you could correct me incase I am
> > wrong and help to understand the 6th point.
>
> The easiest way to store the context is to push it all on the stack,
Yes, at least in the case of interrupts thats often true.
> save the stack pointer, load the stack pointer for the next task, and
> pop its context from the stack.
>
> This requires a separate stack for each task of course.
No. Not for all co-operative systems. In particular run to completion
systems only need a single stack. Some co-operative systems do of
course need multiple stacks.
Robert
Grant Edwards
>> programmer sees fit. By yielding it is allowing a different
>> task to run. The big difference then is that when the task
>> starts executing again it commences from exactly the point
>> from where it yielded.
>
> Can you please explain in the above situation where would the
> context information be stored so that it could be restored
> back?
There are various methods. One is to switch stacks. Here's
another interesting method (I particularly like the
pointer-to-label version):
> In another thread related to this topic,it was discussed that
> context information would not be stored as in pre emptive
> statements.
That may or may not be true. While context information needs
to bestored, it doesn't have to be done the same way a
pre-emptive system does it. There's nothing (other than the
memory required) to prevent a cooperative tasking system from
pushing CPU context and then switching stacks the same what
that pre-emptive systems often do. However, only part of the
CPU context generally needs to be saved, since the context
switch in a cooperative system is usually intitated by a
subroutine call. The ABI for a given platoform usually only
requires a portion of the CPU context to be preserved during a
subroutine call.
> When its possible to restore the execution from the point
> left, I believe definitely storing context information is must
> for cooperative systems.
Yes it is. However, in general less context info has to be
saved, and it can be done in different ways.
--
Grant Edwards grante Yow! Kids, don't gross me
at off ... "Adventures with
visi.com MENTAL HYGIENE" can be
carried too FAR!
Ed Prochak
The context for each task is local static data. There will also be
some global data shared between tasks (possibly event queues and
similar structures available both to tasks and to the interrupt
handlers).
There is essentially only ONE context, that of the superloop. And so,
the superloop's need for only one stack becomes clear.
Ed
Ed Prochak
Very nice post Jack.
Another rule not mentioned is that one task should not prevent another
task from meeting its deadline.
It is unfortunately very easy to violate this rule in simple
cooperative, run-to-completion systems. This rule typically gets
violated during maintenance or enhancements. One of the tasks is
changed such that it violates an assumed time limit per task. Because
this is a loop, the offending tasks may not be the one immediately
preceeding the one that fails. This makes the superloop system brittle
IMO.
Ed
Jonathan Kirwan
wrote:
><snip>
> The ABI for a given platoform usually only
>requires a portion of the CPU context to be preserved during a
>subroutine call.
><snip>
To add even more to this, it's not just the simple fact of not having
to save a few registers that the compiler may otherwise assumed are
scratched across a function call in a cooperative release of control.
In pre-emptive systems, there may be hardware contexts (for example,
the multiplier unit in one of several incarnations found for the
MSP430) that may need re-starting (meaning code examination at the
point of interruption) if the compiler doesn't automatically wrap such
code with interrupt disable/restore prologue/epiloges, or there may be
static contexts within libraries (such as some floating point ones I
know of, for example) that need to be saved/restored in preemptive
systems where there is almost never such a need to worry when you are
making a cooperative call to release control. Etc.
Pre-emption is often far more complex a matter than saving a few more
registers.
Jon