Why is a relocatable stack good for preemptive multitasking?

[GARTHWILSON]

A possible way I can imagine doing it is to have it pause at the end of each row or diagonal or whatever, in an orderly fashion, so it doesn't have to remember too much in order to get going again when it comes back to it.

[Tor]

I'm very comfortable with interrupts, I've been writing interrupt handlers and using real-time systems since the early eighties. But I have learned to appreciate the Propeller way - no interrupts. It really works. I don't run out of cogs (cores) either. Just let one cog wait on a pin. And the counters etc. It has been mentioned that the P2 will have interrupts, however they're not interrupts in the traditional sense. They're fine-tuned to match the Propeller philosophy.

[Arlet]

Quote:

A possible way I can imagine doing it is to have it pause at the end of each row or diagonal or whatever, in an orderly fashion, so it doesn't have to remember too much in order to get going again when it comes back to it.

In some cases, you could, but not all tasks are easy to translate to state machines. Often, it's much easier and cleaner to be able to write a task as a separate unit, only worrying about the total time spent, and let the rest of the system take care of itself. It also makes maintenance a lot easier. If you discover that some part of the system needs higher service frequency, you can just adjust that part, and it will automatically interrupt the other tasks more often, without having to rewrite them.

Also, the ability for a task to stop and wait for certain events in the middle of processing allows for much cleaner implementation. Calling a 'read_headers' function in a web server, which then calls 'read_line', which then calls a 'read_data' from the network stack is a lot easier than writing the whole thing as a state machine, having to keep track of exactly where you are in the whole parsing process, and in the meantime switch to completely unrelated tasks every so many microseconds.

The system will also become much more efficient if you only switch tasks when there's actually something useful to do, rather than just switching back and forth.

[Klaus2m5]

There is a misconception about cooperative multitasking hogging resources. True for a badly programmed task but not different for preemtive multitasking. You just don't do wait loops for anything in a multitasking system (except the scheduler, if all tasks are waiting for something). Only in preemptive multitasking hogging processor time is "invisible" until you hit the saturation of the processor.

[Arlet]

If an image recognition task is designed to take 20 ms out of every 33 ms, and it does exactly that, doing nothing but optimized calculations, I wouldn't say it was badly programmed. Yet, you could still consider it hogging resources, if other tasks need to be serviced every 1 or 2 ms.

[Klaus2m5]

The image recognition tasks saturates the CPU with 60% during 33ms. With 33+1 (1ms/20ms) task context switches in a preemptive system there is little or no headroom. A preemptive system may still work for these real-time tasks but you will have to scratch your head to make it work.

And yes, a cooperative multitasking system will not be able to handle the load without scatching your head either. However with 60% main task I would consider to use a single task only and simply share the load between the main task (image recognition) and an ISR (1ms service / 0.3ms max.).

[Arlet]

Many things can't be done well inside an ISR. Suppose you want to add a webserver so that the operator can adjust some settings from his computer or smartphone. In a preemptive multitasking system, I could add another (low priority) task without having to modify anything else. The time critical stuff will proceed at the same speed, and the webserver will grab whatever time is left.

A huge advantage is also that I can just grab my standard webserver code and integrate it without having to worry about breaking it up into little pieces, and switching tasks, depending on which project it is part of.

[Klaus2m5]

If you need to run near 100% CPU uitilization preemptive is better, even if it takes up more resources itself. But you are walking on a thin line and users will start to complain about response time...

And of course if you need to run existing tasks relying on preemptive scheduling, then preemptive is the right choice for you.

[Arlet]

The numbers are just an example. Use a faster CPU or better code if you want less CPU utilization. It's not really about the performance, it's about the ease of development and the quality of the code. Some code just can't be cleanly rewritten as a state machine, and will become an unreadable mess.

And even if the code is specifically written for this application, it makes sense to keep things separate. That makes it a lot easier to change things, or have code developed by two different persons without having to worry too much about what the other is doing.

[whartung]

BigDumbDinosaur wrote:

If I were running on a cooperative multitasking system a lot of MPU time would be wasted in waiting for me to type something.

Not hardly. You would have two options.

1) your cooperative tasks yield often enough that the keyboard handler can poll the keyboard adequately enough to keep up with the typing speed. If it doesn't see anything, it yields, if it does, it dispatches the character appropriately. What it won't do, is just sit and spin waiting for a keystroke.

2) You have an ISR, or some other mechanism to buffer keyboard input, and your cooperative task needs to simply check the key queue for characters. Again, if there's nothing there, it yields, otherwise it processes the keys on the the key queue.

Quote:

On a preemptive system, my job would be sleeping in between keystrokes and a different job could be awakened and run.

In a cooperative system, tasks sleep by simply having nothing to do. They rapidly determine they have nothing to do, and then yield to the next process.

If you have lots of tasks, you end up spending a perhaps inordinate amount of time "checking for nothing".

But there's no reason you can't meet in the middle, by alerting the scheduler that you're waiting for something (typically I/O) so that when you yield, the scheduler takes your task off the active list, and lets the infrastructure that it's waiting for something. Then the can have ISRs (or however the system is monitoring "things that tasks wait upon") inject a task back in to the active list when whatever it's been waiting for has arrived. Otherwise, the scheduler just yields from one active task to another.

You have to appreciate, also, that today, many high speed servers have forgone preemptive scheduling for cooperative systems. These are driven almost entirely off of I/O events, with tasks stacking up asynchronous requests for processing. It is not uncommon today for a Linux machine to have 1 process per core, each one a single thread runtime handling asynchronous event processing. These are not micro-controller applications, but sophisticated online server systems. Paypal, for example, is in the process (as of 2013, I don't know if they're done) of migrating their entire stack to this model.

[Arlet]

Quote:

But there's no reason you can't meet in the middle, by alerting the scheduler that you're waiting for something (typically I/O) so that when you yield, the scheduler takes your task off the active list, and lets the infrastructure that it's waiting for something. Then the can have ISRs (or however the system is monitoring "things that tasks wait upon") inject a task back in to the active list when whatever it's been waiting for has arrived. Otherwise, the scheduler just yields from one active task to another

That's what I do in most of my projects: non-preemptive multitasking. Every task has its own stack that it uses for local state. It can wait for things, such as I/O activity or timers, or other tasks, but it's not being run all the time just to check for nothing, which saves a lot of CPU and power. In addition, I use interrupts to handle the really time critical stuff. As long as the time critical things are relatively simple, that approach works pretty well.

A big advantage of non-preemptive multitasking is that it's a lot easier to write for, because you rarely need any locking. This also saves CPU time and code size.

[White Flame]

I can't think of any examples of "real" cooperatively multitasking OSes where a foreground task hogs the CPU busy-polling for input. That's simply not good design, and is an incorrect expectation of cooperative systems.

The closest I can think is where you have something like a BASIC environment, where there are multiple environments that the user can manually swap between, to separate between dev and execution, or to have multiple utilities available on-demand. That's not computer multi-tasking, though, that's human multi-tasking.

[GARTHWILSON]

Arlet wrote:

Some code just can't be cleanly rewritten as a state machine, and will become an unreadable mess.

To avoid the state explosion, I wonder how well it would work to just have the task record an address to pick up at, rather than keeping a lot of levels of state. When it leaves off, it would just record the address of the first instruction of the following part, and the jump-in point would do an indirect jump to that desired resumption point. The short routine could be put in a one-line macro, called maybe something like PAUSE , which would end with RTS. You would PAUSE only when you can do it with a minimum of overhead, like when the task itself has nothing on the stack(s). I think I'd like to try it. The indirect jump variable address would have to be initialized before you call the task the first time; but I think I can envision a way to do that, both for RAM-resident and ROM-resident code.

[Arlet]

Also known as protothreads (link goes to C version, but can also be done using asm macro)

[BitWise]

White Flame wrote:

I can't think of any examples of "real" cooperatively multitasking OSes where a foreground task hogs the CPU busy-polling for input. That's simply not good design, and is an incorrect expectation of cooperative systems.

I seem to remember that in Windows 95/98 all the applications where cooperatively multi-tasked. Only DOS boxes were preemptively scheduled against the GUI tasks.