Cooperative Multitasking system

[Fonseca]

Hi there

I'm trying to get around the concept of cooperative multitasking system and exactly how it works in a single threaded application.

My understanding is that this is a "form of multitasking in which multiple tasks execute by voluntarily ceding control to other tasks at programmer-defined points within each task."

So if you have a list of tasks and one task is executing, how do you determine to pass execution to another task? And when you give execution back to a previous task, how do resume from where you were previously?

I find this a bit confusing because I don't understand how this can be achieve without a multithreaded application.


Any advice would be very helpeful :)

Thanks

[Disch]

Cooperative multithreading is useful when you have multiple entities whose actions have STRONG dependency on the other states.

There aren't many instances I can think of when it's useful. The only time I've found it particularly useful is in retro-system emulators. For example, the SNES.

The SNES has several systems:

1) CPU in charge of running actual game code
2) PPU (aka GPU) in charge or rendering pixels
3) APU, a separate processor which runs custom music/sound effect code.
4) DSP in charge of generating audio
5) Any additional hardware on the cartridge (such as the SuperFX chip on the StarFox cartridge, or the ?DSP-1? chip on Super Mario Kart)


The kicker is in real life these 5 areas are all running simulatenously, and all have constant, real-time communication with each other. So if you want to emulate them with multithreading, you're going to have to have some threads wait for other threads to sync up.

For example, every time the CPU writes to a PPU register (often hundreds of times per frame -- thousands of times per second), you have to make sure the PPU is in sync with the CPU, because the write will affect what is drawn. But you can't run the PPU ahead of the CPU because that will affect any register reads that the CPU does.

The end result is a LOT of switching between threads. Tens or hundreds of thousands of times per second. Preemptive (traditional) mulithreading performance sucks when you have this many context switches.

Cooperative multithreading, on the other hand, is ideal. When the CPU is running and it writes to a PPU register, just switch over to the PPU thread, run until you catch up to the CPU, then switch back to the CPU thread.

This is how the popular SNES emulator "bSNES" works. And in fact, I spoke with the author about this technique and employed it in my own NES emulator a while back. You can see the performance difference here:

http://forums.nesdev.com/viewtopic.php?p=96069#p96069




But like I say... that's about the only example I can give where I found it useful. I'm sure there are others, but it's kind of a niche thing.

[JLBorges]

> My understanding is that this is a "form of multitasking in which multiple tasks execute
> by voluntarily ceding control to other tasks at programmer-defined points within each task."

> So if you have a list of tasks and one task is executing,
> how do you determine to pass execution to another task?

A typical example is in the implementation of coroutines; the programmer knows when to cede control:
http://en.wikipedia.org/wiki/Coroutine#Comparison_with_subroutines

Another typical situation is when a blocking call is required; for instance for i/o as in std::cin >> str ; A implementation of a language library in a cooperative multitasking environment can yield while waiting for user input.


> And when you give execution back to a previous task,
> how do resume from where you were previously?

Conceptually, you need to first save the current 'context' - a snapshot of the current execution state which would include a snapshot of the cpu registers including the ip, and may include things like the stack frame. And then reload a previously saved context before resuming execution. Most operating systems provide support for this.

For example, makecontext(), getcontext(), setcontext() and swapcontext() on Unix:
http://www.freebsd.org/cgi/man.cgi?query=getcontext&apropos=0&sektion=0&manpath=FreeBSD+9.1-RELEASE&arch=default&format=html
Or fibers on Windows:
http://msdn.microsoft.com/en-us/library/windows/desktop/ms686350(v=vs.85).aspx

Libraries can wrap these platform/os specific operations.
Freecode: http://freecode.com/projects/libpcl
GNU Pth: http://www.gnu.org/software/pth/

A well-known example of very heavy use of cooperative multitasking for performance and scalability is Microsoft's SQL Server.
http://blogs.msdn.com/b/larryosterman/archive/2005/01/05/347314.aspx

Another well-known example is the 'Active Object', ubiquitous in the Symbian environment: http://www.developer.nokia.com/Community/Wiki/Fundamentals_of_Symbian_C%2B%2B/Active_Objects