Ever wanted to do stuff in the background that can take a while, but don't want to slow down the entire game and trying to split it into smaller chunks is a pain? Do you want it to adapt to whatever free CPU time is left on the fly, no matter how much or little it is?
In this page we'll see how to make a primitive preemptive (kinda) multitasking scheduler with two tasks, one of which is always run at full framerate while the other will take up whatever free CPU time remains available.
- Required variables
- Starting up background task
- Stopping the background task
- Giving up free time to background task
- Resuming foreground task
- Almost done
- More than two tasks
Before getting started, it's recommended that you first get acquainted with the 68000's supervisor and user modes (and their respective stacks) since this makes heavy use of them.
What we're doing here is a system that splits the game's execution into two separate "tasks" which run independently from each other:
- A foreground task, which resumes execution at the beginning of every frame. It runs with the 68000 in supervisor mode. You'd use it to process game logic at full speed even when some other part of the game takes a lot of time to execute.
- A background task, which uses up the remaining CPU time in the frame. It runs with the 68000 in user mode. Use it for stuff that can take a lot of time to run and is expected to take multiple frames, e.g. a software renderer for a 3D game, or simulation math for a real-time simulation game, or decompressing data.
The foreground task is resumed every vertical blank (or whatever else you pick as the "beginning of a frame"), ensuring it will always run at full framerate regardless of how long the background task takes. The foreground task does its job for the frame, then passes execution to the background task until the next frame begins. If the foreground task takes too long, then the background task never executes.
Since the background task executes in user mode, this also means it's
using its own stack pointer (
usp), and this stack pointer is
not used by interrupts. This makes it ideal for complex routines
a7 for non-stack use.
- You can't use
uspas a temporary variable, since now it's being used as an actual stack pointer for the background task. This is rarely done but worth mentioning.
- All the usual hazards from interrupts also apply here. Be careful when accessing hardware! (ideally keep hardware accesses to only one of the tasks)
- Background task runs in user mode so there are a few things that it
can't do (in particular, it can't mess with interrupt masking, though
you can still use the
trapinstruction or the
$A000-$AFFFopcodes to by-pass these limitations). Foreground task isn't limited by this.
Are you ready? Let's move on.
Before we begin, here are the variables we're going to need in RAM. The order of these variables is important since some of them are used as executable code (we modify on the fly to switch to the background task).
BgTaskMoveSr: rs.w 1 ; Opcode for MOVE to SR BgTaskSr: rs.w 1 ; Background task's SR register BgTaskJmp: rs.w 1 ; Opcode for long JMP BgTaskPc: rs.l 1 ; Background task's PC register BgTaskRegs: rs.l 15 ; Background task's d0-d7 and a0-a6 BgTaskRegsEnd: rs.l 0 ; (for use with MOVEM)
If for whatever reason you can't guarantee that the variables won't get reordered, you can try allocating it all as a single block and then point to offsets within it:
BgTaskVars: rs.b 70 BgTaskMoveSr: equ BgTaskVars+0 BgTaskSr: equ BgTaskVars+2 BgTaskJmp: equ BgTaskVars+4 BgTaskPc: equ BgTaskVars+6 BgTaskRegs: equ BgTaskVars+10 BgTaskRegsEnd: equ BgTaskVars+70
Starting up background task
First let's see how to initialize a background task. The subroutine pretty much sets up the variables such that the next time the background task "resumes" it will start executing the subroutine we gave it.
Note that the background task has its own stack and hence you will need to allocate memory for it separately (up to you). Alternatively, if the routine will never touch the stack you can simply never set it up.
; Starts a new background task ; in a5 = BG task's initial stack pointer ; in a6 = BG task's entry point SetUpBgTask: ; Write the opcodes for the instructions ; used to jump to the background task move.w #$46FC, (BgTaskMoveSr) move.w #$4EF9, (BgTaskJmp) ; Store the background task's stack ; pointer and initial program address move.l a5, usp move.l a6, (BgTaskPc) ; Reset the background task flags (the ; important part is that it'll make the ; background task go into user mode) clr.w (BgTaskSr) ; We're done rts
If you're curious, the code written in RAM looks as follows (where
nnnn are the
for the background task):
move.w #nnnn, sr jmp (nnnn).l
Stopping the background task
You probably don't have something to run in the background all the time,
so sometimes you want to "stop" the background task. While you could
achieve this by never calling
YieldToBgTask, another thing
you can do is set up a routine that does nothing as the background task:
; "Stops" the background task ; modifies a6 StopBgTask: ; Set up the idle routine below as the ; background task (no stack needed) lea @Stub(pc), a6 bra SetUpBgTask ; Idle routine used as placeholder ; background task (loops forever ; without doing anything useful) @Stub: bra.s @Stub
Giving up free time to background task
Now that we have a way to initialize the background task, let's move on. The way it works is that the foreground task resumes execution on every frame, then gives up any free CPU time to the background task. This means we need a way to indicate when the foreground task is done for the frame.
We'll need a subroutine that does the following:
- Push the current flags to stack. This is used so when the interrupt
handler returns using
rteit sees the foreground task's
pc(actually our return address) and resumes foreground task execution from there.
- Restore all of the background task's
d0-d7/a0-a6registers (they'll be garbage on first run but will contain valid values later, see interrupt handler).
- Jump to the executable code made up by the variables in RAM, these will restore the background task's flags (in turn switching to user mode and stack) and then jump to the next instruction it's supposed to execute. We do it this way so we don't stomp on any of the restored registers.
This will clobber all
d0-d7/a0-a6 registers on
return for the foreground task. This is fine because it'll only
happen when you explicitly ask for it, but remember to save any register
you want to keep intact.
; moves execution from FG task to BG task ; modifies all d0-d7/a0-a6 on return YieldToBgTask: ; Push the foreground task's flags onto ; the supervisor stack so when the ; interrupt returns with RTE it ends up ; returning back to our caller move.w sr, d7 move.w #$2700, sr move.w d7, -(sp) ; Restore all of the background task's ; d0-d7/a0-a6 registers (not a7 since it ; already resides in usp) lea (BgTaskRegs+4), a0 movem.l (a0)+, d0-d7/a1-a6 move.l (BgTaskRegs), a0 ; Jump to the code in RAM to resume the ; background task where it left jmp BgTaskMoveSr
Resuming foreground task
Now we need a way to return to the foreground task. Normally, you'd do this from the vertical blank interrupt handler.
- Check the flags pushed to the stack to see if the 68000 was running
in supervisor or user mode (important to do this without
btstis your friend here). If it was in supervisor mode then it means the foreground task was still running and you should skip all this.
- Save all
d0-d7/a0-a6registers to RAM, so
YieldToBgTaskcan restore them later. We don't bother with
a7since it already resides safely in
- Also save
pcinto their respective variables in RAM (note how this modifies the executed code), and pop them off the stack so
rtesees what was left behind by
YieldToBgTaskand returns back to the foreground task instead.
This is how the interrupt handler ends up looking like:
TaskSwitchIrq: ; Check if 68000 was already in supervisor ; mode (i.e. foreground task), in which case ; just skip all of this btst #5, (sp) bne.s @NoBgTask ; Save all d0-d7/a0-a6 registers for the ; background task (but not a7 since that ; already resides safely in usp) move.l a0, (BgTaskRegs) lea (BgTaskRegsEnd), a0 movem.l d0-d7/a1-a6, -(a0) ; Save the background task's flags and PC, ; and remove them so what was left behind by ; YieldTaskToBg is used to return instead move.w (sp)+, (BgTaskSr) move.l (sp)+, (BgTaskPc) ; Resume foreground task @NoBgTask: rte
We're almost done! Now we need to glue all this together to get it running. Assuming all the code is there already, you need to do these two things:
- Point the vertical blank interrupt 68000 vector to
TaskSwitchIrq(or otherwise find a way for a suitable interrupt handler to invoke it)
- In your initialization code make sure to set up any
background task to get it ready (interrupts can be enabled, but
must be done before calling
Step #2 can be easily done this way:
Now all you need to do is call
SetUpBgTask whenever you want
to start a new background task and make sure to call
YieldToBgTask from the foreground task every frame (which
conveniently also doubles as a way to know when the next vertical blank
More than two tasks
In theory, you can build up further on this technique to allow any arbitrary amount of tasks executed in a row every frame, with later tasks in the queue being given less priority in case of running low on CPU time. There are some things to bear in mind:
- Obviously you can't rely on supervisor and user mode anymore to
separate the tasks, so the stack pointer (
a7) now also needs to be saved alongside other registers.
- Building on the above: you could use either supervisor or user mode, but if you want to be able to trash the stack pointer at will in any task, you should run them in user mode (supervisor stack needs to remain valid for interrupts to execute properly).
- If you have spare CPU time you'll run out of tasks to execute for the frame. Trying to check when you're done may be more trouble than it's worth, instead always assign an "idle" task that does nothing but wait forever without yielding as the last task.
- Following the design as-is means that if the CPU is way too loaded then the last tasks in the queue may never get to execute for the frame, possibly many frames. If this becomes a problem you may want to consider a way to rotate the order of the tasks (there are many approaches you can take for this).