Apparently I was creating more questions than answering them in my last post. I will try to provide a bit more detail about the implementation of the task scheduler.

The interrupt routine decides, if it wants to schedule a new task. If the new task has a higher priority than the one that is currently running, we want to switch to the new task. So what we need to make sure is, that when we return from the interrupt we do not return to the old task, but to the new one. In order to achieve this, we need to manipulate the stack accordingly, as the return address (and some more information) is stored there. Let’s look at what happens when an interrupt is triggered:

1. the currently executed instruction is finished
2. the current program counter is pushed onto the stack, high byte first
3. the status register is pushed onto the stack
4. the interrupt flag is set (because you usually would not want your interrupt routine to be interrupted itself)

All these steps are performed by the hardware itself. An interrupt service routine normally saves the registers in software in addition:

5. A is pushed onto the stack
6. X is pushed onto the stack
7. Y is pushed onto the stack

How can we manipulate the stack now to return to a different task? We simply push respective data onto the stack!

    lda #>task
    pha          ; push >task
    lda #<task
    pha          ; push <task
    lda #0
    pha          ; push arbitrary states, IRQ flag must be clear
    pha          ; push arbitrary A
    pha          ; push arbitrary X
    pha          ; push arbitrary Y

When the end of the interrupt service routine is reached, it will restore Y, X and A and the final rti will pop the state register and jump to the new address we just pushed onto the stack! We do not have reasonable values for the registers (as the task was never executed before), so we simply chose 0. There is one caveat regarding the state register: we need to make sure that the interrupt flag is clear, or the interrupt will never be called again. It took me a while to realize this, as I was happily using php to push the current state register instead and as can be seen from step 4 above, that had the interrupt flag set.

Now let’s have a look at the task_done routine that is jumped to by a task when it is finished. In theory, all we need to do is to jump to the task with the next highest priority. Let’s for now assume, that the old task has the next highest priority. Things get slightly messy now: we still have the remains of the interrupt on the stack, but tasks are always executed in the main loop! So instead of jumping to the new task with jmp, we will misuse rti and simply do the same as we would do at the end of an interrupt routine:

    pla
    tay
    pla
    tax
    pla
    rti

Et voilá: we restore all registers and are back in the old task!

There is one additional thing that needs to be organized: when a task is added with a lower priority than the currently executed one, it needs to be stored for later. To do this, a list with upcoming tasks needs to be kept. Every time a task is done, the list needs to be searched for the next highest priority and the task needs to be pushed onto the stack as described above. But I am going to leave this little detail to be worked out by the reader (ha, I always wanted to say this cruel sentence at some point in my life)!

Here we are with another rather technical update! Last time I was posting some information about how I want to get more diversity into the game graphics by switching parts of the character set on the fly while the player moves through the world. That actually raised an interesting new problem: how to handle tasks with different priorities!

Up to now there were only two possible priorities: tasks that need to be done during the currently displayed frame (like color RAM scrolling or inserting new characters at the border of the screen) and tasks that only need to be finished eventually during the next frames (like scrolling the currently invisible double buffer or checking for trigger areas for events). The character set swapping adds another priority: in theory it can take quite long and there is no need to have it finished in the next 2-3 frames, it is ok even if it takes e.g. 10 frames or so. Instead of patching this into the existing engine I decided to do it right from the start and be prepared for any upcoming additional tasks.  Which means: implement a task scheduler!

What does a task scheduler do? It makes sure, that most of the processor time is spent on the tasks with the highest priority. I simplified the concept a bit, so that higher priority tasks are always finished before lower priority tasks are continued. The implementation is actually simple, although there is some mean stack fiddling involved and it needed a bit of head scratching until I got it right. The interface of the scheduler module has only two routines: task_add, which adds a new task with a given priority and might switch to it immediately (if it is the highest priority), and task_done, which is called by a task when it is done and selects the next highest priority task to be executed.  All that is needed is to modify the stack such, that the RTI instruction at the end of the interrupt routine jumps to the right task. Apologies for the clumsy block diagram trying to depict this with an example. Did I mention that I am not a graphician?

In any case: implementation is done and unit tests are passing (yay!), so I am looking forward to put this new module into good use!