Hybrid Partition Scheduling in GeMRTOS, Multiprocessor RTOS for Altera FPGA

Most real-time operating systems ask you to choose, once and for all, between partitioned scheduling (every task pinned to a processor) and global scheduling (any task may run on any processor). GeMRTOS does not ask. Its scheduler is built on a single mechanism — the scheduling list — and partitioned, global and everything between them are simply different ways of wiring that one mechanism. This is what hybrid partition scheduling means, and it is available per group of tasks, in the same application, at the same time.

GeMRTOS is a natively multiprocessor RTOS: it was designed for multiple processors from the start, rather than being a uniprocessor kernel later adapted to them. Hybrid partition scheduling is the clearest place that shows.

The usual fork in the road #

Partitioned scheduling is predictable and easy to analyse, but it wastes capacity: a processor sits idle while another has a queue. Global scheduling uses capacity well, but it makes worst-case reasoning harder and lets any task migrate anywhere, which is not always what you want for a task bound to a device or a cache-sensitive workload.

Real systems are rarely one or the other. A control loop wants affinity. A pool of workers wants to spread out. A group of tasks touching one shared peripheral wants to never run concurrently with each other, but is otherwise free. Under a conventional RTOS those three demands are met with three different mechanisms — affinity masks, a global queue, and a mutex — each with its own failure modes.

One mechanism: the scheduling list #

In GeMRTOS, a scheduling list holds ready tasks and defines the discipline used among them. Two independent associations give the model its flexibility:

• Tasks associate to a list with gu_SchedulingListAssociateTask. That list is where the task queues when it becomes ready.
• Processors associate to a list with gu_SchedulingListAssociateProcessor, each association carrying a priority. That priority is the order in which the processor searches lists when it looks for work.

The mapping of tasks onto processors is not declared anywhere. It emerges from those two sets of associations. A list also carries an exclusion quota: the maximum number of its tasks that may be running anywhere in the system at the same instant. By default a new list has no effective limit; gu_SchedulingListExclusionSet lowers it.

Each list also has its own discipline, chosen at creation with gu_SchedulingListCreate: GS_LCBTypeFP for fixed priority, or GS_LCBTypeEDF for earliest deadline first. Different groups of tasks in one application can therefore be scheduled under different disciplines.

The three classic models, from the same parts #

Note what the first row does not use: there is no affinity mask and no per-task processor field. Affinity is the consequence of a list simply being absent from the other processors’ search chains. One concept, applied differently.

How a processor picks its next task #

When a processor needs work, it walks its own chain of list associations in priority order and takes the first eligible task it finds. Two cases decide eligibility:

• If the candidate belongs to a different list from the task currently running, the processor takes it only if that list’s exclusion quota still has room.
• If the candidate belongs to the same list, ordinary priority preemption applies: the ready task wins only if it is more urgent than the running one.

If nothing is eligible, the processor runs its idle task. The decision is bounded and always returns.

Mutual exclusion without a semaphore #

The exclusion quota is worth dwelling on, because it does something a priority scheme alone cannot. Set a list’s quota to 1 and associate it with every processor: its tasks are free to run on any processor, but never two at the same time. That is mutual exclusion enforced by the scheduler itself.

No semaphore is taken, so there is no lock to forget, no ordering to get wrong, and no priority inversion to inherit around. The constraint is a property of the task group, declared once at setup, rather than a discipline every task must remember to follow. For a group of tasks sharing one peripheral or one non-reentrant library, this replaces a whole class of bug with a single line of configuration.

Preemption across processors #

A task becoming ready on one processor may need to displace a lower-priority task running on another. After each scheduling pass, GeMRTOS evaluates what every other running processor should be executing, and signals the one that is out of date. That processor then performs its own scheduling pass and switches. Priority is therefore respected across the whole system, not merely within each processor.

The hardware does the routing #

This is where GeMRTOS differs most from a software-only RTOS. GeMRTOS runs alongside an event-driven hardware controller synthesised into the FPGA next to the processors. On every dispatch, the kernel writes into that controller which processor is currently executing the least urgent work.

The controller uses that register to target incoming external interrupts and expiring timed events at the processor that is cheapest to preempt. Event routing is decided in hardware, informed by software, without any processor polling for work and without a periodic timer tick driving the scheduler. GeMRTOS is timer-tickless: the kernel runs when an event occurs, not on a fixed interval.

This is the mechanism behind GeMRTOS’s timing behaviour. Determinism here is not an adjective applied to the software; it is a consequence of the controller’s event-driven architecture.

What it looks like in code #

The following is the topology setup from the 07_multiprocessor_scheduling example that ships with GeMRTOS. It builds one partitioned list and one exclusion-limited list:

/* Partitioned list: associated with ONE processor only.
   A task assigned here cannot be selected by any other processor,
   because this list is absent from their search chains. */
g_lcb_affinity = gu_SchedulingListCreate(GS_LCBTypeFP);
gu_SchedulingListAssociateProcessor(g_lcb_affinity,
                                    AFFINITY_PROCESSOR,   /* 1-based */
                                    AFFINITY_PRIORITY);

/* Shared list: associated with EVERY processor, but capped.
   With the limit at 1, two of its tasks eligible on two different
   processors still never run concurrently -- and no semaphore
   is involved. */
g_lcb_exclusive = gu_SchedulingListCreate(GS_LCBTypeFP);
for (cpu_id = 1U; cpu_id <= G_NUMBER_OF_PCB; cpu_id++) {
    gu_SchedulingListAssociateProcessor(g_lcb_exclusive, cpu_id,
                                        EXCLUSIVE_PRIORITY);
}
gu_SchedulingListExclusionSet(g_lcb_exclusive, EXCLUSION_LIMIT);

Tasks are then attached to whichever list expresses their requirement:

ptcb = gu_TaskCreate((void *) task_affinity_worker, (void *) 0,
                     "affinity_worker");
gu_SchedulingListAssociateTask(ptcb, g_lcb_affinity);

Processor identifiers are 1-based. Every one of these calls returns a status you should check; the shipped example does, and it is omitted above only for brevity.

Try it #

Example 07_multiprocessor_scheduling demonstrates all three configurations side by side on a dual-processor system, reporting which processor each task runs on. It is delivered as part of the GeMRTOS example catalogue, which runs both on development boards and in the Windows simulation layer, so you can watch the scheduling behaviour before you have hardware on your desk.

GeMRTOS integrates into Altera FPGA devices using the standard Quartus® Prime and Platform Designer flow, targeting Nios V soft processors. Nios II remains supported as a legacy route.

In short #

Hybrid partition scheduling means you are not forced to pick one scheduling model for a whole system. You express each group of tasks as a list, say which processors may serve it and how many of its tasks may run at once, and let the mapping follow. Affinity, global sharing, and mutual exclusion stop being three separate mechanisms and become three settings of one.