Ensuring Compliance with the Real-Time Annex

The reader will be quick to notice that while mapping Ada tasks onto the underlying threads has significant advantages, it does create some complications when it comes to respecting the scheduling semantics specified in the real-time annex (Annex D).

For instance Annex D requires that for the FIFO_Within_Priorities scheduling policy we have:

     When the active priority of a ready task that is not running
     changes, or the setting of its base priority takes effect, the
     task is removed from the ready queue for its old active priority
     and is added at the tail of the ready queue for its new active
     priority, except in the case where the active priority is lowered
     due to the loss of inherited priority, in which case the task is
     added at the head of the ready queue for its new active priority.
     

While most kernels do put tasks at the end of the priority queue when a task changes its priority, (which respects the main FIFO_Within_Priorities requirement), almost none keep a thread at the beginning of its priority queue when its priority drops from the loss of inherited priority.

As a result most vendors have provided incomplete Annex D implementations.

The GNAT run-time, has a nice cooperative solution to this problem which ensures that accurate FIFO_Within_Priorities semantics are respected.

The principle is as follows. When an Ada task T is about to start running, it checks whether some other Ada task R with the same priority as T has been suspended due to the loss of priority inheritance. If this is the case, T yields and is placed at the end of its priority queue. When R arrives at the front of the queue it executes.

Note that this simple scheme preserves the relative order of the tasks that were ready to execute in the priority queue where R has been placed at the end.