Scheduling behaviour issue

Scheduling behaviour issue

[Simon Wright]

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'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

Re: Scheduling behaviour issue

[fabien.chouteau]

On Wednesday, April 22, 2020 at 1:34:53 PM UTC+2, Simon Wright wrote:
> 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 couldn't find the paragraph that says that.

That seems very strange to not resume the task that was just preempted.

Re: Scheduling behaviour issue

[Simon Wright]

fabien.chouteau@gmail.com writes:

> On Wednesday, April 22, 2020 at 1:34:53 PM UTC+2, Simon Wright wrote:
>> 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 couldn't find the paragraph that says that.

It's the dicussion after Figure 29.

There are 2 "continuous" tasks (no interaction with the scheduler) of
the same priority, say A & B (this is so unlike any real-time system
I've encountered! You might have just one, doing some sort of
housekeeping or monitoring).

Both A and B are ready. One of the tasks, A, runs until a
higher-priority task C preempts it; when the higher-priority task
finishes, *the other task* B runs!

> That seems very strange to not resume the task that was just
> preempted.

I so agree. I think it's because the mechanism used is derived from
FreeRTOS's round-robin scheduler.

Re: Scheduling behaviour issue

[Niklas Holsti]

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've been having some trouble thinking of a way to demonstrate the
> (mis)behaviour!

I'm not sure about the definition of a "correct [Ada] application" in 
this context, but it seems to me that the Ada RM rule means that if 
several tasks have the same priority, they can assume mutual 
non-pre-emption, in essence that the running task will not yield to 
another task within this same-priority set until the running task 
explicitly blocks or yields.

Under that rule, therefore, tasks at the same priority, on the same 
processor core, can act on shared data without mutual-exclusion 
protections -- more or less as in a co-operative, non-pre-emptive system 
-- even if they are pre-empted by higher-priority tasks (which do not 
share these same data). The tasks in the same-priority set just have to 
take care not to block or yield while engaged in such actions on shared 
data.

Under RTEMS, if there are higher-priority tasks on that processor core, 
such actions on shared data would not have this mutual-exclusion 
property, and the shared data could be messed up. However, I'm not sure 
if such use of shared data is "correct" per the Ada RM, and if the 
resulting mess can be called "misbehaviour".

> [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
       .      @       .

Re: Scheduling behaviour issue

[Anh Vo]

On Wednesday, April 22, 2020 at 10:20:27 AM UTC-7, Simon Wright wrote:
> fabien.chouteau@gmail.com writes:
> 
> > On Wednesday, April 22, 2020 at 1:34:53 PM UTC+2, Simon Wright wrote:
> >> 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 couldn't find the paragraph that says that.
> 
> It's the dicussion after Figure 29.
> 
> There are 2 "continuous" tasks (no interaction with the scheduler) of
> the same priority, say A & B (this is so unlike any real-time system
> I've encountered! You might have just one, doing some sort of
> housekeeping or monitoring).
> 
> Both A and B are ready. One of the tasks, A, runs until a
> higher-priority task C preempts it; when the higher-priority task
> finishes, *the other task* B runs!
> 
> > That seems very strange to not resume the task that was just
> > preempted.
> 
> I so agree. I think it's because the mechanism used is derived from
> FreeRTOS's round-robin scheduler.

If the preempted task was resumed again, then task B will have no chance to run. Is it a undesired situation.

Re: Scheduling behaviour issue

[Niklas Holsti]

On 2020-04-22 21:05, Anh Vo wrote:
> On Wednesday, April 22, 2020 at 10:20:27 AM UTC-7, Simon Wright wrote:
>> fabien.chouteau@gmail.com writes:
>>
>>> On Wednesday, April 22, 2020 at 1:34:53 PM UTC+2, Simon Wright wrote:
>>>> 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 couldn't find the paragraph that says that.
>>
>> It's the dicussion after Figure 29.
>>
>> There are 2 "continuous" tasks (no interaction with the scheduler) of
>> the same priority, say A & B (this is so unlike any real-time system
>> I've encountered! You might have just one, doing some sort of
>> housekeeping or monitoring).
>>
>> Both A and B are ready. One of the tasks, A, runs until a
>> higher-priority task C preempts it; when the higher-priority task
>> finishes, *the other task* B runs!
>>
>>> That seems very strange to not resume the task that was just
>>> preempted.
>>
>> I so agree. I think it's because the mechanism used is derived from
>> FreeRTOS's round-robin scheduler.
> 
> If the preempted task was resumed again, then task B will have no
> chance to run.

Sure it will run, after other tasks at this priority terminate or block.

> Is it a undesired situation.

Only if you desire round-robin execution of tasks with the same priority.

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

Re: Scheduling behaviour issue

[AdaMagica]

Am Mittwoch, 22. April 2020 20:03:56 UTC+2 schrieb Niklas Holsti:
> Under RTEMS, if there are higher-priority tasks on that processor core, 
> such actions on shared data would not have this mutual-exclusion 
> property, and the shared data could be messed up. However, I'm not sure 
> if such use of shared data is "correct" per the Ada RM, and if the 
> resulting mess can be called "misbehaviour".

This is the reasoning of Ada 83 (RM 9.11 Shared Variables):

<quote>
For the actions performed by a program that uses shared variables, the following assumptions can always be made:

* If between two synchronization points of a task, this task reads a shared variable whose type is a scalar or access type, then the variable is not updated by any other task at any time between these two points.

* If between two synchronization points of a task, this task updates a shared variable whose type is a scalar or access type, then the variable is neither read nor updated by any other task at any time between these two points. 

The execution of the program is erroneous if any of these assumptions is violated.
</quote>

I'm too lazy to search for the relevant text in current Ada, but as far as I can tell, this principle is still valid. This is one of the reasons I guess that protected objects were introduced.

Re: Scheduling behaviour issue

[Niklas Holsti]

On 2020-04-22 23:41, AdaMagica wrote:
> Am Mittwoch, 22. April 2020 20:03:56 UTC+2 schrieb Niklas Holsti:
>> Under RTEMS, if there are higher-priority tasks on that processor core,
>> such actions on shared data would not have this mutual-exclusion
>> property, and the shared data could be messed up. However, I'm not sure
>> if such use of shared data is "correct" per the Ada RM, and if the
>> resulting mess can be called "misbehaviour".
> 
> This is the reasoning of Ada 83 (RM 9.11 Shared Variables):

    [snipped]

> I'm too lazy to search for the relevant text in current Ada, but as
> far as I can tell, this principle is still valid.

The wording in Ada 2012 is very different (RM 9.10 Shared Variables, and 
C.6 Shared Variable Control).

As I understand it, two tasks can read and/or write shared atomic 
variables without that being erroneous, and all tasks see the same order 
of operations on each variable separately, but the interleaving order of 
these reads and writes from the two tasks is not specified (if the 
reads/writes are not in a protected operation or similar).

Mutual exclusion for actions on shared data is usually necessary to 
ensure that a _sequence_ of reads/writes done by one task is not 
_interleaved_ with reads/writes from another task. As far as I can see, 
RM 9.10 and C.6 (and Ada 83 RM 9.11) do not address that question.

The usual example is a simple increment of an atomic counter variable 
(read - add one - write):

    Counter := Counter + 1;

which can lose one count if executed interleaved by two tasks. However, 
if the two tasks have the same priority, and compete for the same 
processor, and the Ada rule quoted by Simon (D.2.3(9)) applies, then 
both tasks can execute the increment without risking interleaving, or so 
it seems to me. But if the RTEMS rule is followed, then pre-emptions 
from higher-priority tasks can force interleaving of instructions from 
the two incrementing tasks, and thus break the counter.

> This is one of the reasons I guess that protected objects were
> introduced.
Certainly (and why rendez-vous parameters were introduced in Ada 83) and 
I would definitely recommend using protected objects for shared 
counters. That would make the counters work properly even under RTEMS.

Simon's challenge was to find a correct program that misbehaves under 
the RTEMS scheduling rule. I think my example will misbehave (not work 
as the programmer expected) but I'm not fully sure if the Ada RM defines 
its behaviour even under the Ada rules. I'm looking for an RM rule that 
says that if two tasks have the same priority and are scheduled on the 
same processor then only one task is running at a time, and executes all 
its reads/writes without any interleaved reads/writes from the other 
task, until the running task somehow yields to the other task. This may 
be implicit in the notions of "scheduling" and "running", but I would 
prefer an explicit connection between those notions and RM 9.10 and C.6.

In this connection I want to ask if the "Discussion" in RM 2012 
9.10(15.b) uses a valid example. The Discussion says that two 
"sequential" assignments to the same variable, where neither "signals" 
the other, are not erroneous, because there may be cases where the order 
in which the assignments are executed makes no difference. The 
Discussion gives, as an example, assignments that just "accumulate 
aggregate counts". It seems to me that the order of two such assignments 
to the same counter does matter, because the values written may be 
different, as in the counter-increment example above. Am I right? If so, 
this example seems wrong for this Discussion (also in Ada 202X ARM).

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

Re: Scheduling behaviour issue

[Jere]

On Wednesday, April 22, 2020 at 5:58:52 PM UTC-4, Niklas Holsti wrote:
> On 2020-04-22 23:41, AdaMagica wrote:
> > Am Mittwoch, 22. April 2020 20:03:56 UTC+2 schrieb Niklas Holsti:
> >> Under RTEMS, if there are higher-priority tasks on that processor core,
> >> such actions on shared data would not have this mutual-exclusion
> >> property, and the shared data could be messed up. However, I'm not sure
> >> if such use of shared data is "correct" per the Ada RM, and if the
> >> resulting mess can be called "misbehaviour".
> > 
> > This is the reasoning of Ada 83 (RM 9.11 Shared Variables):
> 
>     [snipped]
> 
> > I'm too lazy to search for the relevant text in current Ada, but as
> > far as I can tell, this principle is still valid.
> 
> <SNIPPED>
>
> In this connection I want to ask if the "Discussion" in RM 2012 
> 9.10(15.b) uses a valid example. The Discussion says that two 
> "sequential" assignments to the same variable, where neither "signals" 
> the other, are not erroneous, because there may be cases where the order 
> in which the assignments are executed makes no difference. The 
> Discussion gives, as an example, assignments that just "accumulate 
> aggregate counts". It seems to me that the order of two such assignments 
> to the same counter does matter, because the values written may be 
> different, as in the counter-increment example above. Am I right? If so, 
> this example seems wrong for this Discussion (also in Ada 202X ARM).

It's definitely worded awkwardly.  The text is correct that 
it isn't a data race and therefor erroneous, but I think you
are correct that there is a potential race condition there
where the counter could get incremented to the same value
twice, losing a count (assuming I am reading it correctly).

Re: Scheduling behaviour issue

[Simon Wright]

Niklas Holsti <niklas.holsti@tidorum.invalid> writes:

> I'm not sure about the definition of a "correct [Ada] application" in
> this context, but it seems to me that the Ada RM rule means that if
> several tasks have the same priority, they can assume mutual
> non-pre-emption, in essence that the running task will not yield to
> another task within this same-priority set until the running task
> explicitly blocks or yields.
>
> Under that rule, therefore, tasks at the same priority, on the same
> processor core, can act on shared data without mutual-exclusion
> protections -- more or less as in a co-operative, non-pre-emptive
> system -- even if they are pre-empted by higher-priority tasks (which
> do not share these same data). The tasks in the same-priority set just
> have to take care not to block or yield while engaged in such actions
> on shared data.

I see what you mean. Seems like a fragile design under possible priority
reassignment. Not obvious why the work couldn't be done in a single task
- no problem!

> Under RTEMS, if there are higher-priority tasks on that processor
> core, such actions on shared data would not have this mutual-exclusion
> property, and the shared data could be messed up. However, I'm not
> sure if such use of shared data is "correct" per the Ada RM, and if
> the resulting mess can be called "misbehaviour".

So FreeRTOS behaves in the same way as RTEMS? the RTEMS documentation
[1] says part-way through section 5.6 "All tasks with the same priority
will execute in FIFO order" (until they themselves do something to alter
this, I think; it's complicated). On the other hand, there seems to be a
variety of choices, a lot to get ones head round.

[1] https://docs.rtems.org/branches/master/c-user/scheduling_concepts.html

Re: Scheduling behaviour issue

[Simon Wright]

I've done some tests on this with GNAT CE 2019.

Test program at the end; the commented-out lines are for checks on host
machines, irrelevant for single-cpu STM32F4 boards.  The test execution
is to be under GDB, but a breakpoint on the null; in task C (line 48),
and set up this script for that breakpoint:

   command
   silent
   print As
   print Bs
   continue
   end

On macOS with 4 CPUs, both As and Bs are updated, and the user load is
~199% (i.e. two CPUs in use).

On debian stretch under VMware (1 CPU), both As and Bs are updated.

Conclusion: the macOS host RTS doesn't respect the CPU
restriction. Can't tell about macOS, but the Linux RTS behaves in the
same way as FreeRTOS.

On STM32F4, with cortex-gnat-rts, the behaviour is as I expected (both
As and Bs updated).

On STM32F4, with ravenscar-{sfp,full}-stm32f4, the behaviour is as
D.2.3(9)[3] (only As updated).

==========================================

with Ada.Real_Time;
with System;
--  with System.Multiprocessors;

package body Priority_Issue is

   type Count is mod 2 ** 64;
   As : Count := 0;
   Bs : Count := 0;

   task A
   with
     --  CPU => 1,
     Priority => System.Default_Priority;

   task B
   with
     --  CPU => 1,
     Priority => System.Default_Priority;

   task C
   with
     --  CPU => 1,
     Priority => System.Default_Priority + 1;

   use type Ada.Real_Time.Time;

   task body A is
   begin
      delay until Ada.Real_Time.Clock + Ada.Real_Time.Milliseconds (300);
      loop
         As := As + 1;
      end loop;
   end A;

   task body B is
   begin
      delay until Ada.Real_Time.Clock + Ada.Real_Time.Milliseconds (600);
      loop
         Bs := Bs + 1;
      end loop;
   end B;

   task body C is
   begin
      loop
         delay until Ada.Real_Time.Clock + Ada.Real_Time.Seconds (1);
         null;  --  break here, print As, Bs
      end loop;
   end C;

end Priority_Issue;

Re: Scheduling behaviour issue

[Niklas Holsti]

On 2020-04-23 13:56, Simon Wright wrote:
> Niklas Holsti <niklas.holsti@tidorum.invalid> writes:
    [snip]

>> Under RTEMS ...

> So FreeRTOS behaves in the same way as RTEMS?

Sorry, brain fart, I meant FreeRTOS, which you spoke of. (I had other 
correspondence at the same time involving RTEMS, and was confused.) I 
don't know, of my own knowledge, how either FreeRTOS or RTEMS behaves on 
this issue.

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

Re: Scheduling behaviour issue

[Niklas Holsti]

On 2020-04-23 13:56, Simon Wright wrote:
> Niklas Holsti <niklas.holsti@tidorum.invalid> writes:
> 
>> I'm not sure about the definition of a "correct [Ada] application" in
>> this context, but it seems to me that the Ada RM rule means that if
>> several tasks have the same priority, they can assume mutual
>> non-pre-emption, in essence that the running task will not yield to
>> another task within this same-priority set until the running task
>> explicitly blocks or yields.
>>
>> Under that rule, therefore, tasks at the same priority, on the same
>> processor core, can act on shared data without mutual-exclusion
>> protections -- more or less as in a co-operative, non-pre-emptive
>> system -- even if they are pre-empted by higher-priority tasks (which
>> do not share these same data). The tasks in the same-priority set just
>> have to take care not to block or yield while engaged in such actions
>> on shared data.
> 
> I see what you mean. Seems like a fragile design under possible priority
> reassignment. Not obvious why the work couldn't be done in a single task
> - no problem!

There are various logical reasons why one may want to divide different 
SW functions into different tasks -- say, the tasks are triggered 
sporadically by different input signals but contain several internal 
suspension points embedded within their respective algorithms. A 
possible reason to give two different tasks the same priority is that 
the system supports only a handful of priorities, and luckily there is 
no reason (from real-time requirements) to assign different priorities 
to these two tasks, so that distinct priority levels can be saved for 
other tasks.

As I said in a later post, I agree that using static priority 
assignments to ensure synchronization or mutual exclusion between tasks 
is fragile, and more robust methods (protected objects) are preferable.

On the other hand, I often see posts on e.g. comp.arch.embedded from 
people who prefer co-operative multi-tasking (or even single-thread 
programming). They could find it attractive to use such designs based on 
this Ada feature.

Several coding standards (rulebooks) or design standards that I've seen 
have rules forbidding tasks of equal priority, I assume in order to 
avoid uncertainties about execution order, including the case under 
discussion.

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

Re: Scheduling behaviour issue

[Niklas Holsti]

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
       .      @       .