Very basic multitasking article

[Sik]

Kinda unorthodox but thought it may be interesting, I wrote an article explaining how to make an extremely basic (just two tasks) kinda preemptive multitasking system where the foreground task is resumed every video frame and the remaining CPU time is given to the background task (until the next frame). This wasn't made for an OS but rather for a very specific application (shameless plug).

Here's the article:
https://plutiedev.com/multitasking

Mind that this is in 68000 asm, not x86 or ARM, also no MMU or stuff like that. However it does save and restore all the registers for the background task as well as give separate stacks to each task, and it's simple enough that it may give beginners enough push to start working on their task switching code. Mind, the article looks kinda long because it explains what's going on, but the actual code used in that tech demo is around 100 lines (comments included) lol

In the last section it also touches a bit on how one could expand the concept to handle more tasks, although it doesn't go into details.

[bloodline]

The 68K is where I learned programming, I had an Amiga so understanding multitasking on the 68000 is second nature to me

[Sik]

Bumping this thread because I noticed a pretty serious race condition (the kind that halts the CPU in an infinite loop) so I changed how it works. The kind of bug that needs 100% cycle-perfect timing (and interrupt needs to happen exactly between two specific instructions). And I managed to trigger it consistently. Somehow.

On the flipside, no more self-modifying code. Should have done it this way from the beginning honestly, but I guess I was worried about the RTE instruction messing up when not inside an interrupt (since this isn't a traditional scheduler but manually yielding). Turns out that 68000 doesn't work that way, instead when it acknowledges the interrupt it simply modifies the IRQ mask in SR — there isn't any special "interrupt" flag, and RTE will pop whatever mask is left in the stack as-is regardless of what was in SR before. This means that executing RTE from a non-interrupt routine is safe as long as you build the stack frame properly (and you're in supervisor mode, of course).

—————

I guess the steps can be summarized in a more generic way as follows, assuming I'm not forgetting something while writing this:

When entering the scheduler interrupt:

1. Save all registers
2. Save stack frame

When re-entering the task:

1. Restore stack frame
2. Restore all registers
3. Return like an "interrupt"

Whether the register and stack frame steps can be swapped or not (in both cases) depends on whether the instruction set lets you copy values as-is from memory to memory without clobbering registers (68000 lets you do it, but many architectures don't).

On a system with MMU you'd also need to save/restore the MMU state (in whatever way is appropriate for the CPU in question). Also remember that it's not just general purpose registers that you need to save but also FPU, SIMD, etc. (if you aren't saving any of those you need to consider said feature "unsupported" by your kernel)

[nullplan]

On the flipside, no more self-modifying code. Should have done it this way from the beginning honestly, but I guess I was worried about the RTE instruction messing up when not inside an interrupt (since this isn't a traditional scheduler but manually yielding). Turns out that 68000 doesn't work that way, instead when it acknowledges the interrupt it simply modifies the IRQ mask in SR — there isn't any special "interrupt" flag, and RTE will pop whatever mask is left in the stack as-is regardless of what was in SR before. This means that executing RTE from a non-interrupt routine is safe as long as you build the stack frame properly (and you're in supervisor mode, of course).

Most CPUs work this way. They don't actually know whether you are inside of an interrupt or not, they just execute code. And the "return from exception" opcode does some things that might be helpful in interrupt mode, but it always does the same things.

When entering the scheduler interrupt:

Save all registers
Save stack frame


When re-entering the task:

Restore stack frame
Restore all registers
Return like an "interrupt"

Not entirely sure what you mean here. My system works like this: When entering an interrupt - any interrupt - just save all registers. Just do it. It is easier. When returning from kernel mode to userspace, test the task flags to see if the task has a pending signal or needs scheduling. If so, handle these events. There is no scheduler "interrupt". There is a timer interrupt which sets the "needs scheduling" task flag.

The scheduler contains two task switch functions, a high level one and a low level one. The high level one is written in C and saves FPU context and debug registers (by calling the requisite assembler functions). The low level one is written in assembler and simply saves the non-volatile registers, switches stack frames, and restores the other task's registers (and sets the "current task" variable)

All tasks sleep in kernel mode. This is necessary to even just save their registers. But that means that waking up just means switching stacks. The other task knows what it has to restore.

[nexos]

This was my ah-ha moment in multitasking. I realized that the scheduler was separate from the timer when reading a Unix book. It all made sense then. A preemptive scheduler is based around a cooperative scheduler (i.e., the swtch() function). The timer checks if the current thread's quantum is up, and if it is, preempts it.

[Sik]

Most CPUs work this way. They don't actually know whether you are inside of an interrupt or not, they just execute code. And the "return from exception" opcode does some things that might be helpful in interrupt mode, but it always does the same things.

There are a few CPUs that do keep track of whether they're inside an interrupt handler *stares at Z80 and its IFF1/IFF2 flip-flops* but yeah I guess most don't bother to do that.

Not entirely sure what you mean here. My system works like this: When entering an interrupt - any interrupt - just save all registers. Just do it. It is easier. When returning from kernel mode to userspace, test the task flags to see if the task has a pending signal or needs scheduling. If so, handle these events. There is no scheduler "interrupt". There is a timer interrupt which sets the "needs scheduling" task flag.

[...]

Trying to be generic since it depends on each kernel, I assumed that the most common way to do it is to let that timer interrupt to handle the scheduler calls directly. Sounds like you're attaching it to any interrupt no matter what piece of hardware generated it?

Bear into mind, in that list "save registers" is not pushing them to stack (which is what you normally expect from any interrupt handler) but saving there wherever the process context is stored, unless you have separate kernel-space stacks for every process as well (in which case then yeah, you can just save to stack lol).

[nullplan]

There are a few CPUs that do keep track of whether they're inside an interrupt handler *stares at Z80 and its IFF1/IFF2 flip-flops* but yeah I guess most don't bother to do that.

Oh god. Well, the Z80 was a long time ago. Perhaps I should rephrase: I have never come across a CPU that does that, and I have looked a quite an extensive list of CPUs (x86, PowerPC, ARM, Microblaze).

Sounds like you're attaching it to any interrupt no matter what piece of hardware generated it?

Yes. If a network packet comes in, I want to unblock the network driver immediately, and once it has run, there is a chance some other process becomes runnable now. And a big chance these processes are higher priority than the process currently running, which is likely a batch process or even more likely the idle task. Ditto for most other interrupts.

unless you have separate kernel-space stacks for every process as well (in which case then yeah, you can just save to stack lol).

Guilty as charged. Not having separate kernel stacks would require enumerating all reasons why a process might be blocked. Which I don't know right now and might change in future.

[Sik]

Not going to lie, I didn't even think about the possibility for separate kernel stacks until I was writing that post and suddenly realized what may have been going on ¯\_(ツ)_/¯ Probably simplifies some stuff, also I wonder how it impacts security (since presumably it adds a bit more of isolation, but not sure if it really adds much in practice).

Thinking on the Z80 may seem silly, but I was writing that code for something which has a Z80 as a coprocessor (and for which I'm writing a driver at the same time) so you can see how I was left wondering about that (´・ω・`)