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

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

!standard D.16.1          10-06-04 AI05-0167-1/03
!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. 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.
!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.
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_Domain.
A Dispatching_Domain pragma is allowed only immediately within a task_definition. At most one such pragma shall appear within a given construct.
Static Semantics
The following language-defined library package exists:
with Ada.Real_Time; package System.Multiprocessors.Dispatching_Domains is
Dispatching_Domain_Error : exception;
type Dispatching_Domain is private;
System_Dispatching_Domain : Dispatching_Domain;
[Should the type be limited and System_Dispatching_Domain a constant?]
function Create(First,Last : CPU) return Dispatching_Domain;
function Get_First_CPU(DD : Dispatching_Domain) return CPU;
function Get_Last_CPU(DD : Dispatching_Domain) return CPU;
function Get_Dispatching_Domain(T : Task_Id := Current_Task) return Dispatching_Domain;
procedure Assign_Task(DD : in out Dispatching_Domain; P : in CPU_Range; T : in Task_Id := Current_Task);
procedure Set_CPU(P : 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; P : in CPU_Range);
private -- not defined 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 environmental task executes. At program start-up all processors are contained within System_Dispatching_Domain.
Dynamic Semantics
The Dispatching_Domain value 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 the Dispatching_Domain value refers to a Dispatching_Domain that has not yet been created the task is defined to have failed, and it becomes a completed task (see 9.2(1)). 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 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 processor are removed from System_Dispatching_Domain. A call of Create will cause the exception Dispatching_Domain_Error to be raised if any designated processor is not initially 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.
[Can calls of Create be restricted to library level code only?]
The function Get_First_CPU returns the number of the first processor in DD. The exception Dispatching_Domain_Error is raised if DD is not created.
The function Get_Last_CPU returns the number of the last processor in DD. The exception Dispatching_Domain_Error is raised if DD is not created.
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 raised 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.
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 raised if P is not one of the processors of the Dispatching_Domain on which T is assigned (and is not Not_A_Specific_CPU).
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 raised if P is not one of the processors of the calling task's Dispatching_Domain (and is not Not_A_Specific_CPU).
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.
If the implementation has predefined dispatching domains, the details of these domains should be documented.
Implementation Permissions
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):
function Get_CPU(I: Interrupt_Id) return CPU_Range;
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 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 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.
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 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);
!example
** TBD **
--!corrigendum D.16(1)
!ACATS test
Add an ACATS C-Test of this package.
!appendix

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


Questions? Ask the ACAA Technical Agent