Why is a relocatable stack good for preemptive multitasking?

[Arlet]

I think there's a useful distinction between embedded systems, running a coordinated set of tasks as a coherent unit, and a (typically multi-user) system running unknown and potentially hostile code. In the first case, a memory protection scheme is an optional luxury. It can help to find some problems early, but in a correct system, it shouldn't really ever trigger a protection fault.

In the second case, like a full blown Linux system, memory protection is obviously much more useful.

[GARTHWILSON]

Quote:

For a rugged multitasking system preemptive scheduling is only a part of the story. IMHO memory virtualization and protection schemes are the more important part. If you can't do this on your processor you might as well stick to cooperative scheduling, which is far more simple to implement.

and

Quote:

I think there's a useful distinction between embedded systems, running a coordinated set of tasks as a coherent unit, and a (typically multi-user) system running unknown and potentially hostile code. In the first case, a memory protection scheme is an optional luxury. It can help to find some problems early, but in a correct system, it shouldn't really ever trigger a protection fault.

In the second case, like a full blown Linux system, memory protection is obviously much more useful.

So true. In a perfect world, cooperative works far better, with almost no overhead involved in task-switching, and never needing to disable interrupts for it. Also, in a perfect world, memory protection is not needed. (That's not to say virtualization and MMUs aren't valuable. They are.) I have a 6502-oriented article on simple methods for multitasking without a multitasking OS, for systems that lack the resources to implement a multitasking OS, or where hard realtime requirements would rule one out anyway, here.

Yes, in a perfect world. With 6502 and '816 software, we're unlikely to ever again find ourselves in the situation where we're buying commercial software packages and running them simultaneously, wondering when a bug in one will take the whole system down. We write our own software, or if we start with someone else's, at least we have full access to, and control of, the source code. When there's a bug, we fix it. We're not at the mercy of a company that rushed a half-baked product to market and then won't support it, or that fixes one bug while introducing two more (possibly because they're rushing to add more features).

In a perfect world, a task in a cooperative system won't monopolize the processor time either, whether from getting stuck in a loop or simply deciding to do too much without giving other tasks a chance to run. It does the minimum it needs to do to reach a good stopping point and pass control back to the control center, whether that's an OS of some kind or just a cyclic executive (which may or may not start with a task that loads and unloads other tasks and adjusts the list). There isn't really any task scheduler. "Coming to a good stopping point" means it gets to where it's quick to pick back up and resume execution the next time it is given its turn, not needing to remember much while it's taking a break. My last big software project was on a PIC16 microcontroller (actually two PIC16's) whose tiny stack and miserable stack-access capabilities meant each task had to be done using the stack every time the task gave control back. It worked well though. (Yes, it was an embedded system.)

It's within our power to make this perfect world—or at least our tiny corner of our software world. I find preemptive multitasking to be somewhat interesting; but for our realm, I would encourage cooperative multitasking. And, if you do have to split the stack area up into a portion for each task, well, you can.

[Arlet]

GARTHWILSON wrote:

In a perfect world, a task in a cooperative system won't monopolize the processor time either, whether from getting stuck in a loop or simply deciding to do too much without giving other tasks a chance to run. It does the minimum it needs to do to reach a good stopping point and pass control back to the control center, whether that's an OS of some kind or just a cyclic executive (which may or may not start with a task that loads and unloads other tasks and adjusts the list).

I don't think I would go quite that far. There are certainly good applications for preemptive schedulers. There are systems where you'd need to respond in a timely fashion to various priorities of interrupts, but with a structure that's not suited to state machines. In those cases, a preemptive scheduler can be the best solution.

I do see an overuse of preemptive schedulers, where a non-preemptive solution would have worked at least as well, but with much greater simplicity. For example, most (if not all) of the commercial real time operating systems are preemptive.

[GARTHWILSON]

Arlet wrote:

I don't think I would go quite that far. There are certainly good applications for preemptive schedulers. There are systems where you'd need to respond in a timely fashion to various priorities of interrupts, but with a structure that's not suited to state machines. In those cases, a preemptive scheduler can be the best solution.

I'm not sure I understand what you're saying here. Interrupts cut in on the tasks, without the ISR working like the normal tasks. I suppose an interrupt could ask the task scheduler to change its plans and make its next jump to a particular task rather than the next one it was planning to run, and without waiting for the planned expiration time of the current task. But for the interrupt itself to be serviced by a task? That doesn't entirely sound like an interrupt. The PIC16 system I mentioned above switched tasks about 10,000 to 16,000 times per second (cooperatively, and asynchronously to the interrupts), but interrupts from a timer cut in 39,000 times per second and took more than half the processor time (up to 79% in the extreme case, for the ISR having to do the maximum work before returning). The interrupt sequence started never more than two instruction cycles after the interrupt hit, regardless of what task was running at the moment or even if it was in the middle of a task switch. There was communication between the ISR and a couple of tasks, but more like a mailbox, and the tasks did not do the actual interrupt servicing, nor did the ISR know or dictate or care what the task-switching speed was.

Quote:

I do see an overuse of preemptive schedulers, where a non-preemptive solution would have worked at least as well, but with much greater simplicity. For example, most (if not all) of the commercial real time operating systems are preemptive.

I suspect one of the main reasons for that is so one task can crash without taking the others down, right? (working along with memory protection as well). The other reason I'm sure is so the tasks don't have to be written to handle their own cooperation with others. Such cooperation is easy to write for when the tasks are simple like for the embedded system I did last, but may not be so simple for a lot of complex desktop applications.

[Arlet]

Quote:

I suppose an interrupt could ask the task scheduler to change its plans and make its next jump to a particular task rather than the next one it was planning to run, and without waiting for the planned expiration time of the current task

Yes, that's what I meant. I was using "interrupt" more in the generic sense as an indication that the CPU needs to work on something else, but that something else is too big to perform in an ISR, but it's urgent enough that you can't wait for the current task to finish.

Imagine for instance an embedded controller for a complex robot. You get a bunch of data from cameras, sensors, networking interfaces. Some of it urgent, and some less so, but handling the data is too complex to perform in an ISR. All you do in the ISR is store immediate sensor data, and then instruct the scheduler to switch to the appropriate task to handle it.

[KC9UDX]

It always seemed to me, with my lack of actual experience with this, that the ISR would be the best place for the task scheduler to be.

[porcupine]

This is where the Parallax Propeller really shines as a microcontroller. It doesn't provide interrupts (though the next version will) but it gives you 8 "cogs" (processor cores) which are capable of running completely in parallel each on their own 80mhz clock. You can do some amazing hard realtime responsive systems without having to have OS support for pre-emptive multitasking. It's only when you need to use the shared ("HUB") RAM that things slow down. If you can do what you need to do in 2k, you can motor along quite quickly.

[Arlet]

I would think that having 8 separate cores is great if you have 8 independent jobs. But when you need efficient communication between them, interrupts would be very useful too.

Consider for instance that you implement the aforementioned robot inside such a controller. One cog could be dedicated to watching proximity sensors, and another cog could be responsible for motor control. When one of the proximity sensors goes off, you'd want to let the motor controller know as soon as possible, something perfectly suited to interrupts.

[porcupine]

The Propeller has semaphor type mechanisms to wait on signals from other cogs.

But the Propeller II (in final stages of development, available on FPGA right now) has interrupts as well. And 16 cores instead of 8, a higher clock rate, way more I/Os, and each I/O can be a ADC or DAC as well.

[BigDumbDinosaur]

GARTHWILSON wrote:

...In a perfect world, cooperative works far better, with almost no overhead involved in task-switching, and never needing to disable interrupts for it. Also, in a perfect world, memory protection is not needed.

Alas, a perfect computing world is as elusive as unicorns, rainbows and honest politicians.

Cooperative multitasking is a form of controlled resource hogging. Computers that are human-interactive via a local keyboard and display spend much of their wall-clock time waiting on the user. Even now as I am typing, I am using a tiny fraction of the available processing time as I peck away at the keyboard, despite being a pretty fast typist. If I were running on a cooperative multitasking system a lot of MPU time would be wasted in waiting for me to type something.

On a preemptive system, my job would be sleeping in between keystrokes and a different job could be awakened and run. That job could be run until its allotted time-slice has expired, it has completed its work and terminated, or I have typed a character, at which time the operating system would put that other job to sleep and turn its focus on me again.

The primary limitation of preemptive multitasking is that no one process is guaranteed to be run within any kind of deadline. So preemptive multitasking would not be a first choice for real-time work, although with the speed of today's microprocessors, preemption can be carried out with great alacrity.

[BigDumbDinosaur]

Dr Jefyll wrote:

Re memory protection, I recently stumbled across a short piece that discusses the use of the 6829 (an old Motorola MMU chip) in this context.

I vaguely recall the 6829 from decades ago. It has an interesting register called the FUSE register, which has nothing to do with handling short circuits.

When properly interfaced to a 6809, the 6829 is able to determine when the former has responded to an interrupt—the 6809 has two outputs that when viewed together are analogous to VPB on the 65C02 and 65C816. The 6829 can then remap the system to bring the operating system kernel into focus so the interrupt may be processed. The problem is how to put the interrupted task back into focus when the ISR has finished. That is done by loading a count into the 6829's FUSE register, the count being the number of instruction cycles that will occur before the interrupted task would have to be in focus. If a count of $01 is loaded into the FUSE register and then RTI is immediately executed the interrupted task will be brought into focus by the 6829 after the clock cycle in which the RTI opcode is fetched has elapsed. In other words, FUSE is a down-counter slaved to the system clock.

A similar arrangement should be possible with the 65C816 by using a CPLD as the analog to the 6829. VPB would tell the CPLD that the '816 is processing an interrupt, and the CPLD would respond by switching context from user to supervisor mode. When the interrupt processing has been completed a "FUSE" register in the CPLD would be primed to count Ø2 cycles and when the count hit zero, the context would be switched from supervisor mode to user mode. RTI on the 65C816 takes seven clock cycles to complete, with the second and third cycles being internal operations. So the "FUSE" count could be set to $02 or $03 if RTI immediately follows the write to the "FUSE" register, causing the context change to occur during the "dead" cycles of the RTI instruction.

[GARTHWILSON]

In the context of things like robots, mechanical things hardly need 6502 interrupt-level response speed. The 65c02's maximum interrupt latency, including finishing up a just-started maximum-length instruction plus the interrupt sequence plus stacking A, X, and Y (although it may not be necessary to push all of them) is 23 cycles which takes 1.15µs @ 20MHz. That's the amount of time it takes an airliner flying at cruise speed to travel approximately one-sixth the thickness of standard PC board, 0.01 inch. The diesel engine in our son's Ford E350 work van has a redline of something like 4000rpm (I don't remember exactly), and the fuel injection timing for each spurt is electronically controlled. 1.15µs interrupt latency translates then to about .028° of crankshaft rotation. Doing the rest of the job (beyond the latency) with more-than adequate precision is still well within the capability of a 65c02.

Sampling and processing electronic signals via timer interrupts is a different matter, possibly requiring lots more speed.

A ISR can be very complex if needed though, and don't have to be in assembly language, and ISRs can be nested, so a higher-priority interrupt that doesn't take long to service can cut in on the servicing of a lower-priority interrupt that may take longer. I do this regularly.

BigDumbDinosaur wrote:

GARTHWILSON wrote:

...In a perfect world, cooperative works far better, with almost no overhead involved in task-switching, and never needing to disable interrupts for it. Also, in a perfect world, memory protection is not needed.

Alas, a perfect computing world is as elusive as unicorns, rainbows and honest politicians.

But then I go on to say at the end that we can create this perfect world, at least our tiny corner of our software world, where we're not at the mercy of suppliers that rush half-baked software products to market and then don't support them well.

Quote:

Cooperative multitasking is a form of controlled resource hogging. Computers that are human-interactive via a local keyboard and display spend much of their wall-clock time waiting on the user. Even now as I am typing, I am using a tiny fraction of the available processing time as I peck away at the keyboard, despite being a pretty fast typist. If I were running on a cooperative multitasking system a lot of MPU time would be wasted in waiting for me to type something.

In the PIC16 application I mentioned above, one of the tasks is watching for keyboard input every time it runs. Usually there is none, so it consumes only a few instructions' time, and gives control back. So even though we're watching for keyboard input, we're still switching tasks a minimum of about 10,000 times per second. If you're holding a key down, the task looks to see if it's still down, or if it's time to react to it (ie, it has completed the debounce time) or see if it's time to repeat (for automatic key repeat). In most cases the answer is no, it's not time yet, so again it gives control back very quickly. If it was time, it puts the keystroke in the key buffer for whatever other task is using it, and gives control back. Interrupt response is never delayed for any reason (which is good, since I was using it to produce two sound channels at 39,062 samples per second each, where minimizing jitter is essential), and the amount of time needed for a cooperative task to see if it needs to do anything is far less than the amount of time spent just switching tasks in a preemptive system.

[KC9UDX]

The guy caught standing between the fence and the robot will argue about the lack of need for instant interrupt response.

In fact, new regulations are going into effect about this to further shorten robot emergency stop travel distances.

[GARTHWILSON]

Ok, but again, even 1% of a second, or even 100 microseconds, which is extremely fast for something mechanical, isn't enough to even get a yawn out of a 65c02 for interrupt response. That's an eternity. If you're switching tasks many thousands of times per second, you don't need an interrupt at all.

[Arlet]

Quote:

If you're switching tasks many thousands of times per second, you don't need an interrupt at all.

Imagine that part of the robot involves a 30 fps camera. You have a task to search the image for obstacles and decide an appropriate course of action. Imagine this task takes 20 milliseconds from the moment a frame is captured to completion of all the complicated motion planning. If you want to switch 5000 times per second, you're going to have to break up this task in 100 equally sized little pieces. That's a huge pain. You don't want to stop halfway a matrix inversion routine to go check on some buttons.