Re: Scheduling behaviour issue

[Niklas Holsti <niklas.holsti@tidorum.invalid>]

On 2020-04-22 14:34, Simon Wright wrote:
> As some will recall, I've based my Cortex GNAT RTS[1] (for ARM Cortex-M
> devices, so far) on FreeRTOS[2].
> 
> I've now discovered an unfortunate difference between what the ARM
> requires at D.2.3(9)[3] and the way FreeRTOS behaves. What we need is
> 
>      A task dispatching point occurs for the currently running task of a
>      processor whenever there is a nonempty ready queue for that
>      processor with a higher priority than the priority of the running
>      task. The currently running task is said to be preempted and it is
>      added at the head of the ready queue for its active priority.
> 
> but FreeRTOS adds the preempted task at the *tail* of its ready queue
> ([4], section Prioritized Pre-emptive Scheduling (without Time Slicing),
> on page 95 or thereabouts).
> 
> I can see that this will make an application less predictable, but I
> don't think it'll make a correct application misbehave.

I suggested in another response that the FreeRTOS rule would prevent 
equal-priority tasks from acting on shared data with implicit mutual 
exclusion protection, making such an application misbehave. Thinking 
more about this, I have begun to feel that the FreeRTOS rule may break 
the Priority Ceiling Locking protocol itself (RM D.3), and that the Ada 
RM rule is necessary for that protocol to work when priorities are equal.

Assume an Ada program has two tasks A and B with the same priority, a 
protected object P with the same priority value as its ceiling priority, 
and some tasks C, D of higher priority.

Suppose task A calls an operation of P, but this operation is pre-empted 
by C, which then sends a signal that makes B ready. After C blocks, we 
have A running in P, and B in the ready queue. Suppose that D pre-empts 
A for a short time, still in P. Under the FreeRTOS rule, task B will 
then get to execute before task A, which means that B can call P, 
although A is still executing in P, and so the mutual exclusion of P is 
broken.

The work-around is to make the ceiling priority of a protected object 
truly higher (say, one more) than the priority of any task that uses 
that object.

> I've been having some trouble thinking of a way to demonstrate the
> (mis)behaviour!
> 
> [1] https://github.com/simonjwright/cortex-gnat-rts
> [2] https://www.freertos.org
> [3] http://www.ada-auth.org/standards/rm12_w_tc1/html/RM-D-2-3.html#p9
> [4] https://bit.ly/2VK7slM

-- 
Niklas Holsti
Tidorum Ltd
niklas holsti tidorum fi
       .      @       .