Cooperative multitasking OS-??

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

Reply to
ssubbarayan
Loading thread data ...

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.

Reply to
Arlet Ottens

It means that a task runs until it explicitly and voluntarily yeilds.

No. The scheduling algorithm can be anything.

Yes.

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.

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.

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
 Click to see the full signature
Reply to
Grant Edwards

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.

Reply to
Eric Smith

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.
 Click to see the full signature
Reply to
FreeRTOS.org

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
Reply to
Robert Adsett

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.

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 , Seattle, WA, USA. PGP keyID 27F772C1
Reply to
Wim Lewis

On Fri, 30 Nov 2007 01:16:27 -0800 (PST), ssubbarayan 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.

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.

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.

That may be true in desktop operating systems, it is most certainly not true in many embedded systems.

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.

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.

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
 Click to see the full signature
Reply to
Jack Klein

I wrote a multitasking multi window program for the Sinclair Spectrum in the early 1980's.

This was before Bill Gates got into it. Its a shame I didnt patent it !

Reply to
Marra

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:

Your patent would have been invalid for prior use. So would mine.

--
 Chuck F (cbfalconer at maineline dot net)
   
 Click to see the full signature
Reply to
CBFalconer

a

to

r

ld

In a cooperative system a task can volunteer to yield at any point the

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

Reply to
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

Reply to
ssubbarayan

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.

Reply to
Arlet Ottens

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.

???? Sorry, that point doesn't parse.

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.

Yes, at least in the case of interrupts thats often true.

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

Reply to
Robert Adsett

There are various methods. One is to switch stacks. Here's another interesting method (I particularly like the pointer-to-label version):

formatting link

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.

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
 Click to see the full signature
Reply to
Grant Edwards

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

Reply to
Jonathan Kirwan

ElectronDepot website is not affiliated with any of the manufacturers or service providers discussed here. All logos and trade names are the property of their respective owners.