Is a preemptive multitasking OS possible on the interruptless DCPU-16?

Question

I am looking into various OS designs in the hopes of writing a simple multitasking OS for the DCPU-16. However, everything I read about implementation of preemptive multitasking is centered around interrupts. It sounds like in the era of 16-bit hardware and software, cooperative multitasking was more common, but that requires every program to be written with multitasking in mind.

Is there any way to implement preemptive multitasking on an interruptless architecture? All I can think of is an interpreter which would dynamically switch tasks, but that would have a huge performance hit (possibly on the order of 10-20x+ if it had to parse every operation and didn't let anything run natively, I'm imagining).

Bale

Note that DCPU-16 has interrupts now. – Autogiro

Does it? As of May 4 2014 the version of the documentation available on the website (0x10c.com/doc/dcpu-16.txt) is still 1.1 and has no interrupts. Is there any documentation on the new features? – Bale

I assume you don't reddit or use the forum. Check this bad boy (spec 1.7) out! We chat about this on freenode IRC #0x10c-dev if you want to drop by. – Autogiro

Answer 1

Preemptive multitasking is normally implemented by having interrupt routines post status changes/interesting events to a scheduler, which decides which tasks to suspend, and which new tasks to start/continue based on priority. However, other interesting events can occur when a running task makes a call to an OS routine, which may have the same effect.

But all that matters is that some event is noted somewhere, and the scheduler decides who to run. So you can make all such event signalling/scheduling occur only only on OS calls.

You can add egregious calls to the scheduler at "convenient" points in various task application code to make your system switch more often. Whether it just switches, or uses some background information such as elapsed time since the last call is a scheduler detail.

Your system won't be as responsive as one driven by interrupts, but you've already given that up by choosing the CPU you did.

Bloodshed

So this has the disadvantage of cooperative multitasking in that there is no strict upper bound on how long the CPU can run without hitting the scheduler (for instance, if a process goes into a loop that does not involve any OS calls) but since it hijacks OS calls for scheduling purposes, it will work on any program that makes OS calls? – Bale

@AndrewG. exactly. And this is how the Classic Mac OS added multitasking, initially as an extension in System 5. Appropriate calls into the OS were treated as cooperative multitasking opportunities. As you say, there's no strict upper bound — e.g. a process that, presumably by an error in design, enters an infinite loop without OS calls will hang the entire system. – Radiance

@Radiance that's what a hardware watchdog timer that asserts CPU reset and in-RAM reset routine that unwinds the stack back to the program entry point is for. See my explanation for why that's not incredibly crazy. – Stewartstewed

@AndrewG.: this is in essence cooperative multitasking, especially if you use the egregious calls. – Bloodshed

Answer 2

Actually, yes. The most effective method is to simply patch run-times in the loader. Kernel/daemon stuff can have custom patches for better responsiveness. Even better, if you have access to all the source, you can patch in the compiler.

The patch can consist of a distributed scheduler of sorts. Each program can be patched to have a very low-latency timer; on load, it will set the timer, and on each return from the scheduler, it will reset it. A simplistic method would allow code to simply do an

if (timer - start_timer) yield to scheduler;

which doesn't yield too big a performance hit. The main trouble is finding good points to pop them in. In between every function call is a start, and detecting loops and inserting them is primitive but effective if you really need to preempt responsively.

It's not perfect, but it'll work.

The main issue is making sure that the timer return is low latency; that way it is just a comparison and branch. Also, handling exceptions - errors in the code that cause, say, infinite loops - in some way. You can technically use a fairly simple hardware watchdog timer and assert a reset on the CPU without clearing any of the RAM; an in-RAM routine would be where RESET vector points, which would inspect and unwind the stack back to the program call (thus crashing the program but preserving everything else). It's sort of like a brute-force if-all-else-fails crash-the-program. Or you could POTENTIALLY change it to multi-task this way, RESET as an interrupt, but that is much more difficult.

So...yes. It's possible but complicated; using techniques from JIT compilers and dynamic translators (emulators use them).

This is a bit of a muddled explanation, I know, but I am very tired. If it's not clear enough I can come back and clear it up tomorrow.

By the way, asserting reset on a CPU mid-program sounds crazy, but it is a time-honored and proven technique. Early versions of Windows even did it to run compatibility mode on, I think 386's, properly, because there was no way to switch back to 32-bit from 16-bit mode. Other processors and OSes have done it too.

EDIT: So I did some research on what the DCPU is, haha. It's not a real CPU. I have no idea if you can assert reset in Notch's emulator, I would ask him. Handy technique, that is.

Culbertson

Would it be accurate to summarise your suggestion as automatic cooperative multitasking? – Radiance

Answer 3

I think your assessment is correct. Preemptive multitasking occurs if the scheduler can interrupt (in the non-inflected, dictionary sense) a running task and switch to another autonomously. So there has to be some sort of actor that prompts the scheduler to action. If there are no interrupting devices (in the inflected, technical sense) then there's little you can do in general.

However, rather than switching to a full interpreter, one idea that occurs is just dynamically reprogramming supplied program code. So before entry into a process, the scheduler knows full process state, including what program counter value it's going to enter at. It can then scan forward from there, substituting, say, either the twentieth instruction code or the next jump instruction code that isn't immediately at the program counter with a jump back into the scheduler. When the process returns, the scheduler puts the original instruction back in. If it's a jump (conditional or otherwise) then it also effects the jump appropriately.

Of course, this scheme works only if the program code doesn't dynamically modify itself. And in that case you can preprocess it so that you know in advance where jumps are without a linear search. You could technically allow well-written self-modifying code if it were willing to nominate all addresses that may be modified, allowing you definitely to avoid those in your scheduler's dynamic modifications.

You'd end up sort of running an interpreter, but only for jumps.

Radiance

Answer 4

another way is to keep to small tasks based on an event queue (like current GUI apps)

this is also cooperative but has the effect of not needing OS calls you just return from the task and then it will go on to the next task

if you then need to continue a task you need to pass the next "function" and a pointer to the data you need to the task queue

Panegyrize

Doesn't this require all programs on the system to break their processing down into small tasks ending with an OS call (essentially cooperative multitasking)? Or would you dynamically inspect and rewrite tasks? – Bale

@AndrewG. didn't I say that in my second sentence? but yes, yes it would, though more a return to the queue when you are done – Panegyrize