!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 WG9 Approved 22-06-22 !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) @drepl For a task type (including the anonymous type of a @fa) or subprogram, the following language-defined representation aspect may be specified: @dby For a task type (including the anonymous type of a @fa), protected type (including the anonymous type of a @fa), or subprogram, the following language-defined representation aspect may be specified: !corrigendum D.16(10/3) @drepl The CPU aspect shall not be specified on a task interface type. @dby The CPU aspect shall not be specified on a task or protected interface type. !corrigendum D.16(11/4) @drepl The @fa 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. @dby The @fa 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) @drepl 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). @dby 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. @s8<@i> Starting a protected action on a protected object assigned to a processor should be implemented without busy-waiting. !corrigendum J.15.9(4/3) @drepl A CPU pragma is allowed only immediately within a @fa, or the @fa of a @fa. @dby A CPU pragma is allowed only immediately within a @fa, @fa, or the @fa of a @fa. !corrigendum J.15.9(6/3) @drepl For an implementation that supports Annex D, a @fa CPU specifies the value of the CPU aspect (see D.16). If the @fa appears in a @fa, the @fa is associated with the aspect for the task type or @fa that contains the @fa; otherwise, the @fa is associated with the aspect for the subprogram that contains the @fa. @dby For an implementation that supports Annex D, a @fa CPU specifies the value of the CPU aspect (see D.16). If the @fa appears in a @fa, the @fa is associated with the aspect for the task type or @fa that contains the @fa. If the pragma appears in a @fa, the @fa is associated with the aspect for the protected type or @fa that contains the @fa. Otherwise, the @fa is associated with the aspect for the subprogram that contains the @fa. !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.” ****************************************************************