Version 1.3 of ai05s/ai05-0167-1.txt

!standard D.16 10-02-18 AI05-0167-1/02
!class Amendment 09-10-22
!status work item 09-10-22
!status received 09-10-22
!priority Medium
!difficulty Medium
!subject Managing affinities for programs executing on multiprocessor platforms

Facilities are provided to allow a multiprocessor platform to be partitioned into a number of non-overlapping dispatching domains (DDs). Every task is scheduled within a DD. A task may also be assigned to execute on just one CPU from within its DD.

An increasing number of embedded applications are now executed on multiprocessor and multicore platforms. For non-real-time programs it is usually acceptable for the mapping of tasks to CPUs to be implementation defined and hidden from the program. For real-time programs it may not be acceptable for the mapping of tasks to CPUs to be hidden from the program.

This mapping is often known as the "affinity" of the task. The control of affinities is as important as the control of priorities. The ability to control the affinity of a task is needed in Ada.

The following collection of additions to the language are concerned with supporting the execution of multi-tasking Ada programs on SMPs - identical multiprocessors. The following issues are addressed

- representing CPUs (now covered in AI05-171) - dispatching/scheduling policies for DDs - controlling task affinities - identifying interrupt affinities - Implementation advice and documentation requirements

The following package (and pragma CPU) is defined in AI05-171:

package System.Multiprocessors is type CPU_Range is range 0 .. <implementation-defined> subtype CPU is CPU_Range range 1 .. CPU_Range'last; function Number_Of_CPUs return CPU; end System.Multiprocessors;

pragma CPU(expression)

The following allows dispatching (scheduling) policies to be defined.

type Policy is (Priority_Specific_Dispatching, Non_Preemptive_FIFO_Within_Priorities, FIFO_Within_Priorities, Round_Robin_Within_Priorities, EDF_ACross_Priorities, Implementation_Specific);

procedure Set_Priority_Specific_Policy( DP : in out Dispatching_Policy; P : Priority_Specific; Low : Priority; High : Priority); -- raises Dispatching_Policy_Error if -- DP has not been set to Priority_Specific_Dispatching, or -- High is not greater than Low, or -- any priority from Low to High has already been set

A series of calls of the final procedure allows the program to construct the required priority-specific allocations.

Note this is a non-extendible definition of dispatching policies.

The following package supports the creation of dispatching domains (DDs). One DD is defined to be the 'System' DD; the environmental task and any derived from that task are allocated to the 'System' DD.

The collection of CPUs, represented by an integer ordering 1 .. Number_Of_CPUs, is partitioned into a finite set of non-overlapping DDs. When a DD is defined it is given a dispatching (scheduling).

Tasks can be allocated to a DD and be globally scheduled within that DD. Alternatively they can be allocated to a DD and assigned to a specific CPU within that DD. Tasks cannot be allocated to more than one DD, or assigned to more than one CPU. Task cannot move between DD, but can move between CPUs within the same DD.

-- checks to see if the processors First, First+1, ..., Last -- are in the system dispatching domain. -- if so, remove them from system scheduling domain and add to the new domain, -- set the scheduling policy for the domain -- raise Dispatching_Domain_Error -- if the system cannot support global scheduling -- over the processors identified, or -- if processors are not in system dispatching domain, or -- if a processor has a task fixed to it, or -- if the allocation would leave the system dispatching domain -- empty, or -- if Dispatching_Domain_Policy has not been set.

function Get_First_CPU(DD : Dispatching_Domain) return CPU; function Get_Last_CPU(DD : Dispatching_Domain) return CPU; -- both raise Dispatching_Domain_Error if domain not created

procedure Assign_Task(DD : in out Dispatching_Domain; T : in Task_Id := Current_Task); -- raises Dispatching_Domain_Error if T is already assigned -- to a dispatching domain

procedure Assign_Task(DD : in out Dispatching_Domain; P : in CPU; T : in Task_Id := Current_Task); -- raises Dispatching_Domain_Error if P not in DD or if -- T is already assigned

procedure Set_CPU(P : in CPU_Range; T : in Task_Id := Current_Task); -- raises Dispatching_Domain_Error if P not in current DD for T

procedure Delay_Until_And_Set_CPU( Delay_Until_Time : in Ada.Real_Time.Time; P : in CPU); -- raises Dispatching_Domain_Error if P not in -- current DD for calling task

The required behaviour of each subprogram is as follows:

Create -- Creates a dispatching domain with a dispatching policy. The identified CPUs are moved from the `System' dispatching domain to this new domain. A CPU cannot be moved if it has a task assigned to it. The `System' dispatching domain must not be emptied of CPUs as it always contains the environmental task.

Get_First_CPU -- returns the number of the first CPU in the domain. Get_Last_CPU -- returns the number of the last CPU in the domain.

Get_Dispatching_Domain -- as the names imply.

Assign_Task -- There are two Assign_Task procedures. One allocates the task just to a dispatching domain (for global scheduling within that domain) the other allocates it to a dispatching domain and assigns a specific CPU within that dispatching domain (for partitioned scheduling).

Set_CPU -- sets the task to a specified CPU. The task will now only execute on that CPU.

Free_CPU -- removes the CPU specific assignment. The task can now execute on any CPU within its dispatching domain.

Get_CPU -- returns the CPU on which the designated task is runnable. (if assigned, 0 otherwise).

Delay_Until_And_Set_CPU -- delays a task and then sets the task to the specified CPU when the delay expires. This is needed for some scheduling schemes.

In addition to these two packages there is a further new pragma required to control the affinity of tasks during activation:

pragma Dispatching_Domain (DD : Dispatching_Domain);

The following points should be emphasized.

All dispatching domains have the same range of priorities System.Any_Priority.

The `System' dispatching domain, System_Dispatching_Domain, is subject to the policies defined using the configuration pragmas: Task_Dispatching_Policy and Priority_Specific_Dispatching.

A task has, by default, the dispatching domain of its activating task. If the activating task is assigned to a specific processor, then so is the child task.

For protected objects there is no need for affinities, it is the tasks that have DDs and possibly an assigned CPU. PO code will run on the task's CPU. There is however a need to know on what CPU interrupt code will execute, this will allow an associated task to be assigned the same CPU. Hence the following (which could be added to Ada.Interrupts):

function Get_CPU(I: Interrupt_Id) return CPU_Range; -- returns 0 if interrupt is handled by more than one CPU -- in this case the mapping algorithm must be documented

Finally, there are a number of implementation characteristic that must be documented, and there will be certain implementation advice useful to include in the ARM. For example the CPU(s) on which the clock interrupt is handled and hence where delay queue and ready queue manipulations (and user code - Timing Events) executed must be documented. If the Ada environment is being implemented on a system that has predefined dispatching domains, the details of these domains should also be documented.

An increasing number of embedded applications are now executed on multiprocessor and multicore platforms. For non-real-time programs it is usually acceptable for the mapping of tasks to CPUs to be implementation defined and hidden from the program. For real-time programs this is not the case. The control of affinities is as important as the control of priorities.

In the literature on multiprocessor scheduling there are two main approaches to affinity: global scheduling where the tasks can run on any CPU (and potentially migrate at runtime); and partitioned scheduling where tasks are anchored to a single CPU. From these schemes, two further variants are commonly discussed: for global scheduling tasks are restricted to a subset of the available CPUs, and for partitioned scheduling the program can explicitly change a task's affinity and hence cause it to be moved at run-time.

Restricting the set of CPUs on which a task can be globally scheduled supports scalability - as platforms move to contain hundreds of CPUs, the overheads of allowing full task migration become excessive and outweighs any advantage that might accrue from global scheduling. Controlled changing of a task's affinity has been shown to lead to improved schedulability for certain types of application.

These four schemes can be used with any form of dispatching, for example fixed priority or EDF. For multiprocessors, EDF is no longer optimal and is not always better than fixed priority. Also global scheduling is usually better than partitioning, but not always. New dispatching algorithms will be defined in the future (it is an active research area), the provisions defined above will allow many of these algorithms to be programmed using the controls provided. However, a fully flexible model with, for example, overlapping dispatching domains, is not supported by the workshop (IRTAW). It was felt better to remove a constraint later rather than attempt to add one.

protected objects require a real lock on a multiprocessor platform unless all user tasks are assigned the same CPU. Spin locking (where tasks spin at their current active priority) is an adequate scheme. Programmer control over ceilings allows protocols such as non-preemptive execution of 'shared' POs to be programmed. No further language provision is required.

The provisions outlined in this AI formed the main focus of the 14th IRTAW. They are the result of considerable discussion and evaluation. The starting point were a number of papers at the workshop, including: Supporting Execution on Multiprocessor Platforms, by Burns and Wellings; Providing Additional Real-Time Capability and Flexibility for Ada 2005, by Rod White; Towards a Ravenscar Extension for Multiprocessor Systems, by Ruiz; and Realtime Paradigms Needed Post Ada 2005, by Michell et al. There were also relevant papers and discussions at the previous workshop.

The notion of a dispatching domain has some similarities to the current Ada notion of a partition. However the workshop felt that the two notions were not identical and to use partitions for dispatching domains would not be effective. Partitions are more likely to have a role with non SMP (i.e. CC-NUMA) architectures.

The definition of DDs is such that a simple system with just one DD will not need to consider these domains. Moreover, if global dispatching using fixed priorities is adequate then the program can be silent on all affinity issues.