By Timon Bestebreur (Software Team)

The satellite needs to perform many tasks, but how does it decide what task to perform? We do this using a multi-level non-preemptive queue, with a separate queue for high priority tasks that need to be done once (onetime tasks). How this all works is explained in more detail below!

The task scheduler consists of a multi-level profile (six stacked lists) that contains tasks with an executable (a function and its arguments, if any), an interval (how often the task needs to be executed) and a watchdog limit (the total time the task is allowed to run before it is killed). Tasks are assigned a priority based on the level in the list that they’re placed in. This is visualized in the figure below.

 

Next to recurring tasks, the scheduler supports onetime tasks. These are high-priority tasks that need to be executed only once, and not multiple times on recurring intervals. The onetime tasks can be scheduled with or without a delay and are contained in a onetime task list.

To keep track of which tasks need to be executed, the scheduler contains an execute list. This is a FIFO queue that contains tasks that are due to be executed. Tasks are due to be executed when the time between now and the last time they have been executed is longer than their interval. Thus, the task interval is not a deadline but a minimum wait time between two executions of the task.

Scheduling a task happens by copying the task from the multi-level profile to the execute list. The profile is scanned for tasks that are due for execution
in the order of descending priority level. Concretely: if two tasks are due for execution and one is in level 1 and one in level 3, the level 1 task is added to the execute list before the task in level 3. Once the tasks are in the execute list, the priorities are ignored since the execute list is a FIFO queue.

Each time the recurring tasks are scanned for tasks that are due for execution, the onetime tasks are scanned as well. If due for execution, the onetime tasks are added to the execute list and removed from the list of onetime tasks to prevent multiple executions.

The scheduler is ‘passive’ in that it does not actively periodically move tasks from the profile to the execute list. Instead, the scheduler contains a method that returns true or false based on whether there are tasks available for execution. Each time this method is called, the scheduler scans its internal profile for recurring and onetime tasks that are due for execution and, if there are any, appends them to the execute list. Then the method returns whether the execute list contains any tasks or not. This way the user of the scheduler can decide when it wants to execute tasks or do something else based on whether tasks are available, and it allows the scheduler to function without a background routine.

The great thing about this design is that it makes selecting and executing tasks very simple. This can be done using a few lines of code:

That’s it! Quite neat, right?

Thus, this is task scheduling theory applied to our real-world context. We hope you learned something along the way.
Have a nice day!

-The Software Team