Version 1.2 of ai12s/ai12-0281-1.txt
!standard D.16(7/3) 18-06-05 AI12-0281-1/01
!standard D.16(10/3)
!standard D.16(11/3)
!standard D.16(14/3)
!standard J.5.9(4/3)
!standard J.5.9(6/3)
!class Amendment 18-06-05
!status work item 18-06-05
!status received 18-05-19
!priority Low
!difficulty Easy
!subject CPU Affinity for Protected Objects
!summary
CPU aspect may be specified on protected type declarations to allow simpler
lock-free and deadlock-free implementations.
!problem
A very desirable property of an Ada program on a single core computer is that
it can be guaranteed to be deadlock free, with no unbounded priority inversions
when the priority ceiling protocol is applied. Unfortunately, this property
can not be easily proven for multi-tasking Ada programs executing on a multicore
processor. This is because a lock must be obtained prior to executing a protected
action. For instance, consider two protected objects that have protected
procedures that in turn call a protected procedure of the other object. If task
A calls protected object P1, which calls a protected procedure of P2, while
task B calls protected object P2, which calls a protected procedure of P1,
deadlock is a possibility, since both tasks will have acquired locks to one of
the protected objects, while waiting endlessly for the lock of the other
protected object. If the protected objects were implemented with lock free
algorithms, or if it could be guaranteed that all tasks that interact with a
protected object execute on the same processor, then this deadlocking could be
avoided. Should Ada provide better mechanisms to guarantee that deadlocking will not
occur when a program is executing on a multicore processor, if communicating tasks
have the same CPU affinity?
!proposal
The goal of this proposal is to allow the CPU aspect to be specified on a
declaration of a protected type or a stand alone protected object. This ensures
that all tasks that invoke protected actions of such a protected object are executing
on the same CPU, which implies that the runtime can be simpler without needing
locks to be acquired, thus avoiding deadlock.
Program_Error would be raised if a task executing on a CPU other than the one
specified for the protected object attempts to execute a protected action of that
protected object.
!wording
Modify D.16 (7/3) -- to allow aspect CPU to be applied to a protected type
For a task type (including the anonymous type of a single_task_declaration)
{, protected type (including the anonymous type of a single_protected_declaration),}
or subprogram, the following language-defined representation aspect may be specified:
Modify D.16 (8.a/3)
Aspect Description for CPU: Processor on which a given task{, or calling task
for a protected type} should run.
Modify D.16 (10/3)
The CPU aspect shall not be specified on [a] task { or protected }interface type{s}.
Modify D.16 (11/4)
The expression specified for the CPU aspect of [a] task { or protected }type{s} is
evaluated each time an object of the [task]{corresponding} type is created
(see 9.1 {and 9.4}). The CPU value is then associated with the [task] object.
Modify D.16 (14/3)
{For a task, the}[The] CPU value determines the processor on which the task will
activate and execute; the task is said to be assigned to that processor. If
the CPU value is Not_A_Specific_CPU, then the task is not assigned to a processor.
A task without a CPU aspect specified will activate and execute on the same
processor as its activating task if the activating task is assigned a processor.
If the CPU value is not in the range of System.Multiprocessors.CPU_Range or is
greater than Number_Of_CPUs the task is defined to have failed, and it becomes a
completed task (see 9.2).
{For a protected type, the CPU value determines the processor on which calling tasks
will execute; the protected object is said to be assigned to that processor. If
the CPU value is Not_A_Specific_CPU, then the protected object is not assigned to
a processor. A call to a protected object that is assigned to a processor from a
task that is not assigned a processor or is assigned a different processor
raises Program_Error.}
D.16 Implementation Advice
Starting a protected action on a protected object assigned to a processor should
be implemented without busy-waiting.
AARM Reason: Busy-waiting is a form of lock and can be a source of deadlock.
Busy-waiting is typically needed for starting protected actions on multiprocessors,
but if all tasks calling a protected object execute on the same CPU, this locking
isn't needed and the source of deadlock and associated overhead can be eliminated.
Modify J.15.9 (4/3)
A CPU pragma is allowed only immediately within a task_definition, {protected_definition, }
or the declarative_part of a subprogram_body.
Modify J.15.9 (6/3)
For an implementation that supports Annex D, a pragma CPU specifies the value of
the CPU aspect (see D.16). If the pragma appears in a task_definition, the
expression is associated with the aspect for the task type or single_task_declaration
that contains the pragma{. If the pragma appears in a protected_definition, the
expression is associated with the aspect for the protected type or
single_protected_declaration that contains the pragma. Otherwise}[; otherwise],
the expression is associated with the aspect for the subprogram that contains the pragma.
Modify K.1 (15/3)
CPU Processor on which a given task {, or calling task
for a protected type} should run. See D.16.
!discussion
From a real-time perspective, very efficient lock free data structures can in
theory be obtained in a straight forward manner when the Ravenscar Profile is
being applied, and when it is known that all use of a protected object is by
tasks that execute on the same processor. This is because each task is locked
to execute on a specific CPU, and because the ceiling priority protocol is in
place. If all use of a protected object is by tasks executing on the same CPU,
then any task that is executing a protected action cannot be preempted by another
task wishing to call into the same protected object and therefore no locking is
needed. But locking is needed to implement a protected object if a protected
object can be accessed from tasks executing on multiple cores. Ada allows aspect
CPU to be applied to a task desclaration to indicate which CPU a task of that
type will execute on. The CPU aspect may also be applied to a subprogram
declaration, which could be applied to protected procedures, or protected
functions, but not protected entries.
It would be helpful if the CPU aspect could be applied to a protected type
declaration, or single protected object, which would imply that all calls to the
protected object are via tasks that are executing on the same CPU.
With such a specification in place, this would provide an indication to the
implementation that locking is not needed, and that any overhead associated with
locking, including space for the lock in memory and initialisation and
finalisation of the locks can be eliminated.
!ASIS
TBD.
!ACATS test
ACATS B-Tests and C-Tests.
!appendix
From: Brad Moore
Sent: Friday, May 18, 2018 11:55 PM
Here is the AI split off from AI12-0234-1 (Compare an Swap Atomic Operations)
that allows the CPU aspect to be specified on protected object declarations.
[This is version /01 of this AI - Editor.]
****************************************************************
From: Jeff Cousins
Sent: Monday, June 11, 2018 8:30 AM
A few comments:
!summary
{The} CPU aspect
!wording
“Modify D.16 (10/3)
The CPU aspect shall not be specified on [a] task { or protected }interface type{s}.”
“Modify K.1 (15/3)
CPU Processor on which a given task {, or calling task for a protected type}
should run. See D.16.”
Should these say “for actions of a protected object”?
I was wondering whether this AI should allow for Partition_Id rather than just
CPU, so as to alow for (entry-less) protected objects in a shared passive
partition??
****************************************************************
From: Tucker Taft
Sent: Monday, June 11, 2018 9:43 AM
> I was wondering whether this AI should allow for Partition_Id rather than
> just CPU, so as to alow for (entry-less) protected objects in a shared
> passive partition??
I am not sure what this would accomplish. If it is a shared passive
partition, presumably you already have plenty of control about which active
partitions can see which passive partitions. Adding protected object
restrictions into the mix would just seem to add undue complexity, without
commensurate benefits (IMHO).
****************************************************************
From: Randy Brukardt
Sent: Monday, June 11, 2018 9:43 PM
> Modify D.16 (10/3)
>
> The CPU aspect shall not be specified on [a] task { or protected }interface
> type{s}.”
>
> “Modify K.1 (15/3)
>
> CPU Processor on which a given task {, or calling task for a protected type}
> should run. See D.16.”
>
> Should these say “for actions of a protected object”?
Huh? The first paragraph is a Legality Rule, it has to apply to something
static like a type, not an action. Did you mean to reference some other text?
I sort of understand the second, if your point was that one doesn't call a
protected type, but rather a protected operation. Maybe it would be better
to say:
CPU Processor on which a given task {or calling task for a protected
operation of a protected type }should run. See D.16.
****************************************************************
Questions? Ask the ACAA Technical Agent