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

Unformatted version of ai05s/ai05-0167-1.txt version 1.6
Other versions for file ai05s/ai05-0167-1.txt

!standard D.16.1          11-01-23 AI05-0167-1/05
!standard C.3.2
!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 multiprocessors
!summary
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.
!problem
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.
!proposal
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:
package System.Multiprocessors is pragma Preelaborate(Multiprocessors);
type CPU_Range is range 0 .. <implementation-defined>; Not_A_Specific_CPU : constant CPU_Range := 0; subtype CPU is CPU_Range range 1 .. CPU_Range'Last;
function Number_Of_CPUs return CPU; end System.Multiprocessors;
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. If no tasks are explicitly assigned to other domains, then all tasks will execute on this default domain. 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.
!wording
Add a new clause:
D.16.1 Multiprocessor Dispatching Domains
This clause allows implementations on multiprocessor platforms to be partitioned into distinct dispatching domains during program startup.
Static Semantics
The following language-defined library package exists:
with Ada.Real_Time; package System.Multiprocessors.Dispatching_Domains is pragma Preelaborate(Dispatching_Domains);
Dispatching_Domain_Error : exception;
type Dispatching_Domain (<>) is limited private;
System_Dispatching_Domain : constant Dispatching_Domain;
function Create(First, Last : CPU) return Dispatching_Domain;
function Get_First_CPU(Domain : Dispatching_Domain) return CPU;
function Get_Last_CPU(Domain : Dispatching_Domain) return CPU;
function Get_Dispatching_Domain(T : Task_Id := Current_Task) return Dispatching_Domain;
procedure Assign_Task(Domain : in out Dispatching_Domain; CPU : in CPU_Range := Not_A_Specific_CPU; T : in Task_Id := Current_Task);
procedure Set_CPU(CPU : in CPU_Range; T : in Task_Id := Current_Task);
function Get_CPU(T : in Task_Id := Current_Task) return CPU_Range;
procedure Delay_Until_And_Set_CPU( Delay_Until_Time : in Ada.Real_Time.Time; CPU : in CPU_Range);
private ... -- not specified by the language end System.Multiprocessors.Dispatching_Domains;
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 environment 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 task_definition.
Dynamic Semantics
A pragma Dispatching_Domain assigns the task to the specified domain. During activation, a task executes in the domain of the activating task; afterward, it executes in the domain to which it is assigned. If the task is not assigned to any domain, it executes in that of the activating task.
[Author's question:
The above matches my understanding of the minutes, but I'm still having trouble with it. Activation is over when a task reaches its "begin" -- do we really want to insist that it move to a different domain, and therefore a different CPU, at that time? Suppose we say:
Assign_Task(DD_3, CPU_7, My_Task);
And suppose My_Task is then activated by the environment task, which is running in System_Dispatching_Domain, on CPU_2. So during activation, My_Task runs in System_Dispatching_Domain, but it certainly can't run on CPU_7, because that's part of DD_3. But that contradicts the semantics of Assign_Task below.
To me it seems much simpler if a task is assigned to a domain once and for all (doesn't switch domains at the "begin"), and always runs on its assigned CPU (before and after "begin"), and that CPU is always part of that domain. (Except the Not_A_Specific_CPU case, of course). We can change CPU affinity, but not the domain, of a task, right?
End Author's Question]
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 raise Dispatching_Domain_Error 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. A call of Create will raise Dispatching_Domain_Error if the calling task is not the environment task, or after the call to the main subprogram.
[Author's Question: Is that last sentence what we want? The minutes say "Program_Error", but everything else here raises Dispatching_Domain_Error, so I used that. But more importantly: It's OK to create domains after tasks start running? And it's bad to create domains in the main procedure?]
The function Get_First_CPU returns the first CPU in Domain; Get_Last_CPU returns the last one.
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 the CPU within Dispatching_Domain Domain. Task T can now execute only on CPU unless CPU designates Not_A_Specific_CPU, in which case it can execute on any processor within Domain. The exception Dispatching_Domain_Error is propagated if T is already assigned to a Dispatching_Domain other than System_Dispatching_Domain, or if CPU is not one of the processors of Domain (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 the CPU. Task T can now execute only on CPU, unless CPU 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 CPU 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 Requirements
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 set 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):
with System.Multiprocessors;
function Get_CPU(Interrupt: Interrupt_Id) return System.Multiprocessors.CPU_Range;
The function Get_CPU returns the processor on which the handler for Interrupt is executed. If the handler can execute on more than one processor the value System.Multiprocessors.Not_A_Specific_CPU is returned.
!discussion
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.
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.
with System; use System; package Ada.Dispatching is Dispatching_Policy_Error : exception;
type Dispatching_Policy is private;
type Policy is (Priority_Specific_Dispatching, Non_Preemptive_FIFO_Within_Priorities, FIFO_Within_Priorities, Round_Robin_Within_Priorities, EDF_ACross_Priorities, Implementation_Specific);
subtype Priority_Specific is Policy range FIFO_Within_Priorities .. EDF_ACross_Priorities;
procedure Set_Policy(DP : in out Dispatching_Policy; P : Policy);
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
private -- not defined by language end Ada.Dispatching;
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 environment 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.
with Ada.Real_Time; package System.Multiprocessors.Dispatching_Domains is
Dispatching_Domain_Error : exception;
type Dispatching_Domain is private;
System_Dispatching_Domain : Dispatching_Domain;
function Create(First,Last : CPU) return Dispatching_Domain;
-- 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
function Get_Dispatching_Domain(T : Task_Id := Current_Task) return Dispatching_Domain;
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 Free_CPU(T : in Task_Id := Current_Task);
function Get_CPU(T : in Task_Id := Current_Task) return CPU_Range; -- returns 0 if T is not set to a specific CPU
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
private -- not defined by the language end System.Multiprocessors.Dispatching_Domains;
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 environment 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);
!example
** TBD **
--!corrigendum D.16(1)
!ACATS test
Add an ACATS C-Test of this package.
!appendix

From: Bob Duff
Sent: Sunday, January 23, 2011 5:30 PM

New version of AI05-0167-1, Managing affinities for programs executing on
multiprocessors. [Editor's note: This is version /05 of this AI.]

I basically did what the minutes say, but:

(Alan, and everybody, see "???" below.)

Where does the name "system DD" come from?

   System_Dispatching_Domain : constant Dispatching_Domain;

Seems like "default" would be a better name for it, and seems like "dispatching"
is unnecessary noise.  So how about:

   Default_Domain : constant Dispatching_Domain;

?

> Tucker suggests rewording:
>
> ?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); assigning a task to the System_Dispatching_Domain
> has no effect.? And drop the last sentence.

I don't see how that makes sense.  If a task is already assigned to some
non-system domain, then attempting to assign it back to the system domain should
be an error, shouldn't it?

Dynamic Semantics

A pragma Dispatching_Domain assigns the task to the specified domain.
During activation, a task executes in the domain of the activating task; afterward, it executes in the domain to which it is assigned.
If the task is not assigned to any domain, it executes in that of the activating task.

----------------

???The above matches my understanding of the minutes, but I'm still having
trouble with it. Activation is over when a task reaches its "begin" -- do we
really want to insist that it move to a different domain, and therefore a
different CPU, at that time? Suppose we say:

    Assign_Task(DD_3, CPU_7, My_Task);

And suppose My_Task is then activated by the environment task, which is running
in System_Dispatching_Domain, on CPU_2. So during activation, My_Task runs in
System_Dispatching_Domain, but it certainly can't run on CPU_7, because that's
part of DD_3.  But that contradicts the semantics of Assign_Task below.

To me it seems much simpler if a task is assigned to a domain once and for all
(doesn't switch domains at the "begin"), and always runs on its assigned CPU
(before and after "begin"), and that CPU is always part of that domain.  (Except
the Not_A_Specific_CPU case, of course).  We can change CPU affinity, but not
the domain, of a task, right?

----------------

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 raise Dispatching_Domain_Error
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. A call of Create will raise
Dispatching_Domain_Error if the calling task is not the environment task, or
after the call to the main subprogram.

???Is that last sentence what we want?  The minutes say "Program_Error", but
everything else here raises Dispatching_Domain_Error, so I used that.  But more
importantly: It's OK to create domains after tasks start running?  And it's bad
to create domains in the main procedure?



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


Questions? Ask the ACAA Technical Agent