Tasks, schedules and priorities (2)

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.

interrupt-3

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:

  1. A is pushed onto the stack
  2. X is pushed onto the stack
  3. 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)!

2 thoughts on “Tasks, schedules and priorities (2)

  1. Thanks for the explanation! One question to check if I got it right – the task subroutines end ALWAYS with the (misused) RTI?

    1. That is correct. The tasks are switched to in the IRQ, so you could interpret them as an interrupt routine themselves that needs to end with an RTI at some point in time. The whole mechanism is kind of a multi-level IRQ.

Leave a Reply

Your email address will not be published. Required fields are marked *