Version 1.5 of ai12s/ai12-0281-1.txt

Unformatted version of ai12s/ai12-0281-1.txt version 1.5
Other versions for file ai12s/ai12-0281-1.txt

!standard D.16(7/3)          19-03-05 AI12-0281-1/03
!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 Amendment 1-2012 19-02-26
!status ARG Approved 9-0-2 19-02-26
!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 cannot be easily proven for multitasking 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.
!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 assigned to 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 operation} should run.
Modify D.16 (10/3) The CPU aspect shall not be specified on a task { or protected }interface type.
Modify D.16 (11/4) The expression specified for the CPU aspect of a task { or protected }type 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.
!discussion
From a real-time perspective, very efficient lock-free data structures can in theory be obtained in a straightforward 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.
When the CPU aspect is applied to a protected type declaration, or single protected object, it is implied that all calls to the protected object are via tasks that are assigned to (and thus executing on) the same CPU.
With such a specification in place, this provides 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 initialization and finalization of the locks can be eliminated.
!corrigendum D.16(7/3)
Replace the paragraph:
For a task type (including the anonymous type of a single_task_declaration) or subprogram, the following language-defined representation aspect may be specified:
by:
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:
!corrigendum D.16(10/3)
Replace the paragraph:
The CPU aspect shall not be specified on a task interface type.
by:
The CPU aspect shall not be specified on a task or protected interface type.
!corrigendum D.16(11/4)
Replace the paragraph:
The expression specified for the CPU aspect of a task type is evaluated each time an object of the task type is created (see 9.1). The CPU value is then associated with the task object.
by:
The expression specified for the CPU aspect of a task or protected type is evaluated each time an object of the corresponding type is created (see 9.1 and 9.4). The CPU value is then associated with the object.
!corrigendum D.16(14/3)
Replace the paragraph:
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).
by:
For a task, 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.
Implementation Advice
Starting a protected action on a protected object assigned to a processor should be implemented without busy-waiting.
!corrigendum J.15.9(4/3)
Replace the paragraph:
A CPU pragma is allowed only immediately within a task_definition, or the declarative_part of a subprogram_body.
by:
A CPU pragma is allowed only immediately within a task_definition, protected_definition, or the declarative_part of a subprogram_body.
!corrigendum J.15.9(6/3)
Replace the paragraph:
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; otherwise, the expression is associated with the aspect for the subprogram that contains the pragma.
by:
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, the expression is associated with the aspect for the subprogram that contains the pragma.
!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.

****************************************************************

From: Jeff Cousins
Sent: Tuesday, June 12, 2018  4:49 AM

>>  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?
 
Sorry, I meant the preceding paragraph:

“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.”

****************************************************************

From: Randy Brukardt
Sent: Tuesday, February 26, 2018  11:46 PM

When we discussed this AI today, we mentioned that (in general) aspect CPU is 
not static, so the compiler cannot always know whether or not busy-waiting is 
needed. We didn't think this is a problem, since aspect CPU is usually static,
and is always static for profiles Ravenscar/Yorvik.

The Implementation Advice in this AI reads:

   Starting a protected action on a protected object assigned to a processor 
   should be implemented without busy-waiting.

This is not possible in general, as noted above. Should we fix this wording so 
it applies only to cases where the implementation could reasonably do the 
right thing? A strategic insertion of "statically" should do the trick:

   Starting a protected action on a protected object statically assigned to 
   a processor should be implemented without busy-waiting.

Generally, we try to avoid asking the impossible in implementation advice, and 
while I suppose it could be accomplished with heroic efforts (generating all 
of the operations both ways, and picking one at runtime), that would seem to 
defeat the goal of analysis (especially at the generated code level) and 
surely efficiency.

That seems especially true in this case, where the advice is as much a 
statement to users of what they ought to expect as it is to implementers.

Thoughts?

****************************************************************


Questions? Ask the ACAA Technical Agent