Multitasking on Mega Drive

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.

Overview

Iwis says

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:

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 that repurpose a7 for non-stack use.

Some downsides:

Are you ready? Let's move on.

Required variables

Before we begin, here are the variables we're going to need in RAM: 

BgTaskSr:       rs.w 1  ; Background task's SR register
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)

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:
    ; 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

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:

  1. Push the current flags to stack. This is used so when the interrupt handler returns using rte it sees the foreground task's sr and pc (actually our return address) and resumes foreground task execution from there.
  2. Restore all of the background task's d0-d7/a0-a6 registers (they'll be garbage on first run but will contain valid values later, see interrupt handler).
  3. Push the background's pc and sr onto the stack and execute a rte instruction, simulating a return from an interrupt (we need to do it this way since we don't want sr to change before we jump back to the background task).

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 back to the background task by
    ; simulating a return from an interrupt
    move.l  (BgTaskPc), -(sp)
    move.w  (BgTaskSr), -(sp)
    rte

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.

  1. Check the flags pushed to the stack to see if the 68000 was running in supervisor or user mode (important to do this without clobbering registers, btst is your friend here). If it was in supervisor mode then it means the foreground task was still running and you should skip all this.
  2. Save all d0-d7/a0-a6 registers to RAM, so YieldToBgTask can restore them later. We don't bother with a7 since it already resides safely in usp.
  3. Also save sr and pc into their respective variables in RAM, and pop them off the stack so rte sees what was left behind by YieldToBgTask and 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

Almost done

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:

  1. Point the vertical blank interrupt 68000 vector to TaskSwitchIrq (or otherwise find a way for a suitable interrupt handler to invoke it)
  2. 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 YieldToBgTask)

Step #2 can be easily done this way: 

    bra     StopBgTask

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 begins).

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: