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

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) - controlling task affinities - identifying interrupt affinities - Implementation advice and documentation requirements

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

The details of the proposal are contained in !wording.

The following points should be emphasized.

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

There is a default dispatching domain that initially contains all the processors and on which the environment task executes. All tasks will therefore execute on this domain unless they contain a CPU or Dispatching_Domain pragma. A task executing in the default domain can be assigned to another dispatching domain. A task will always activate in the dispatching domain of its activating task (as the activating task will be blocked).

For protected objects there is no need for affinities, it is the tasks that have domains 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.

Add a new clause:

D.16.1 Multiprocessor Dispatching Domains

This clause allows implementations on multiprocessor platforms to be partitioned into distinct dispatching domains.

Static Semantics

The following language-defined library package exists:

The type Dispatching_Domain represents a series of processors on which a task may execute. Each processor is contained within exactly one Dispatching_Domain. System_Dispatching_Domain contains the processor or processors on which the environmental task executes. At program start-up all processors are contained within System_Dispatching_Domain.

Syntax

The form of pragma Dispatching_Domain is as follows:

pragma Dispatching_Domain (expression);

Name Resolution Rules

The expected type for the expression is System.Multiprocessors.Dispatching_Domains.Dispatching_Domain.

Legality Rules

A Dispatching_Domain pragma is allowed only immediately within a task_definition. At most one such pragma shall appear within a given construct.

Dynamic Semantics

The Dispatching_Domain value, indicated by the use of pragma Dispatching_Domain, determines the dispatching domain on which the task will execute; the task is said to be assigned to that Dispatching_Domain. A task will activate on the dispatching domain of its activating task. A task without a Dispatching_Domain pragma will activate and execute on the same dispatching domain as its activating task.

If a task contains a CPU pragma and a Dispatching_Domain pragma, and the CPU value is not contained within the range of processors for the Dispatching_Domain value (and is not Not_A_Specific_CPU), the activation of the task is defined to have failed, and it becomes a completed task (see 9.2(1)).

The function Create creates and returns a Dispatching_Domain containing all the processors in the range First .. Last. These processors are removed from System_Dispatching_Domain. A call of Create will cause the exception Dispatching_Domain_Error to be propagated if any designated processor is not currently in System_Dispatching_Domain, or if the system cannot support a distinct domain over the processors identified, or if a processor has a task assigned to it, or if the allocation would leave System_Dispatching_Domain empty.

Calls to Create can only be made from the environment task prior to the call of the main subprogram.

The function Get_First_CPU returns the number of the first processor in DD.

The function Get_Last_CPU returns the number of the last processor in DD.

The function Get_Dispatching_Domain returns the Dispatching_Domain on which the task is assigned.

A call of the procedure Assign_Task assigns task T to processor P within Dispatching_Domain DD. Task T can now execute only on processor P unless P designates Not_A_Specific_CPU, in which case it can execute on any processor within DD. The exception Dispatching_Domain_Error is propagated if T is already assigned to a Dispatching_Domain other than System_Dispatching_Domain, or if P is not one of the processors of DD (and is not Not_A_Specific_CPU). A call of Assign_Task is a task dispatching point for task T. If T is the Current_Task the effect is immediate, otherwise the effect is as soon as practical. Assigning a task to System_Dispatching_Domain that is already assigned to that domain has no effect.

A call of procedure Set_CPU assigns task T to processor P. Task T can now execute only on processor P, unless P designates Not_A_Specific_CPU, in which case it can execute on any processor within its Dispatching_Domain. The exception Dispatching_Domain_Error is propagated if P is not one of the processors of the Dispatching_Domain on which T is assigned (and is not Not_A_Specific_CPU). A call of Set_CPU is a task dispatching point for task T. If T is the Current_Task the effect is immediate, otherwise the effect is as soon as practical.

The function Get_CPU returns the processor assigned to task T, or Not_A_Specific_CPU if the task is not assigned to a processor.

A call of Delay_Until_And_Set_CPU delays the calling task for the designated time and then assigns the task to the specified processor when the delay expires. The exception Dispatching_Domain_Error is propagated if P is not one of the processors of the calling task's Dispatching_Domain (and is not Not_A_Specific_CPU).

Implementation Requirement

The implementation shall perform the operations Assign_Task, Set_CPU, Get_CPU and Delay_Until_And_Set_CPU atomically with respect to any of these operations on the same dispatching_domain, processor or task.

Implementation Advice

Each dispatching domain should have separate and disjoint ready queues.

Documentation Requirement

The implementation shall document the processor(s) on which the clock interrupt is handled and hence where delay queue and ready queue manipulations occur. For any Interrupt_Id whose handler can execute on more than one processor the implementation shall also document this range of processors.

Implementation Permissions

An implementation may limit the number of dispatching domains that can be created and raise Dispatching_Domain_Error if an attempt is made to exceed this number.

--

Add to Ada.Interrupts (C.3.2):

The function Get_CPU returns the processor on which the handler for I is executed. If the handler can execute on more than one processor the value System.Multiprocessors.Not_A_Specific_CPU is returned.

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.

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.

One possible extension, not covered in this AI, is to allow each DD to have different dispatching policies. This was deemed to be too adventurous for the current set of changes. However, a possible package for this was discussed:

The following would allow dispatching (scheduling) policies to be defined.

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. Although a child package could be used to provide this extension.

If this package existed then when a DD was defined it would also define its disptching policy.

The following is an earlier version of the package that 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.

The required behaviour of each subprogram is as follows:

Create -- Creates a dispatching domain. 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, Not_A_Specific_CPU 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);

** TBD **

--!corrigendum D.16(1)

Add an ACATS C-Test of this package.

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