!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.] ****************************************************************