CVS difference for ai05s/ai05-0167-1.txt

Differences between 1.2 and version 1.3
Log of other versions for file ai05s/ai05-0167-1.txt

--- ai05s/ai05-0167-1.txt	2009/11/04 06:26:38	1.2
+++ ai05s/ai05-0167-1.txt	2010/02/20 03:56:42	1.3
@@ -1,4 +1,4 @@
-!standard  D.16                                 09-10-22    AI05-0167-1/01
+!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
@@ -9,9 +9,9 @@
 !summary
 
 Facilities are provided to allow a multiprocessor platform to be
-partitioned into a number of non-overlapping allocation domains (ADs).
-Every task is scheduled within an AD. A task may also be assigned
-to execute on just one CPU from within its AD.
+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
 
@@ -32,204 +32,215 @@
 with supporting the execution of multi-tasking Ada programs on
 SMPs - identical multiprocessors. The following issues are addressed
 
-- representing CPUs
+- representing CPUs (now covered in AI05-171)
+- dispatching/scheduling policies for DDs
 - controlling task affinities
 - identifying interrupt affinities
-- supporting different scheduling schemes
 - Implementation advice and documentation requirements
 
 
-A simple integer type is used to represent the range of CPUs (CPUs).
-The range starts from one to more naturally cater for the single
-CPU case. There is a default that is necessary in other definitions
-(see group budgets' AI). The CPUs are potentially split
-into sets and hence an array of Boolean is defined (although
-perhaps a container should be used). These definitions are
-give here in a child package of System, although they could just
-be added to System:
+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;
 
-package Ada.System.MultiProcessors is
+pragma CPU(expression)
 
-   Number_of_CPUs : constant Positive := <implementation-defined>;
 
-   type CPU is range 1 .. Number_of_CPUs;
 
-   Default_CPU : constant CPU := <implementation-defined>;
+The following allows dispatching (scheduling) policies to be defined.
 
-   type CPU_Set is array (CPU) of Boolean;
+with System; use System;
+package Ada.Dispatching is
+   Dispatching_Policy_Error : exception;
 
-end Ada.System.MultiProcessors;
+   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);
 
-The following package (again defined here as an extension to System)
-allows the group of CPUs to be partitioned into a finite
-set of non-overlapping 'Allocation_Domains' (AD). One AD is
-defined to be the 'System' AD; the environmental task and any
-derived from that task are allocated to the 'System' AD.
+   subtype Priority_Specific is Policy range
+     FIFO_Within_Priorities .. EDF_ACross_Priorities;
 
-Tasks can be allocated to an AD and be globally scheduled within
-that AD. Alternatively they can be allocated to an AD and
-assigned to a specific CPU within that AD. Task cannot
-be allocated to more than one AD, or assigned to more than one
-CPU.
+   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
 
-with Ada.Task_Identification; use Ada.Task_Identification;
-with Ada.Real_Time; use Ada.Real_Time;
-with Ada.System.MultiProcessors; use Ada.System.MultiProcesors;
-package Ada.System.Allocation_Domains is
+private
+  -- not defined by language
+end Ada.Dispatching;
 
-   type Allocation_Domain is limited private;
+A series of calls of the final procedure allows the program to construct
+the required priority-specific allocations.
 
-   System_Allocation_Domain : constant Allocation_Domain;
+Note this is a non-extendible definition of dispatching policies.
 
-   NON_EMPTY_SYSTEM_Allocation_DOMAIN : exception;
-   CPU_NOT_IN_SYSTEM_DOMAIN : exception;
-   CPU_ASSIGNED_IN_SYSTEM_DOMAIN : exception;
-   CPU_NOT_IN_Allocation_DOMAIN: exception;
 
-   function Create(PS : CPU_Set) return Allocation_Domain;
-   -- raise CPU_NOT_IN_SYSTEM_DOMAIN if CPUs not in
-   --  System_Allocation_Domain
-   -- raise CPU_ASSIGNED_IN_SYSTEM_DOMAIN if in System_Allocation_Domain
-   --  but has a assigned task
-   -- raise NON_EMPTY_SYSTEM_Allocation_DOMAIN if the allocation would leave the
-   --  system_Scheduling domain empty
 
-   function Get_CPU_Set(AD : Allocation_Domain) return CPU_Set;
-   function Get_Allocation_Domain(Tid : Task_Id := Current_Task)
-      return Allocation_Domain;
+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.
 
-   procedure Allocate_Task(AD  : in out Allocation_Domain;
-                           Tid : Task_Id := Current_Task);
-   procedure Allocate_Task(AD  : in out Allocation_Domain; P : CPU;
-                           Tid : Task_Id := Current_Task);
-   -- raises CPU_NOT_IN_Allocation_DOMAIN if P not in AD
+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.
 
-   procedure Set_CPU(P : CPU; Tid : Task_Id := Current_Task);
-   -- raises CPU_NOT_IN_Allocation_DOMAIN if P not in current AD for Tid
+with Ada.Real_Time;
+package System.Multiprocessors.Dispatching.Domains is
 
+   Dispatching_Domain_Error : exception;
 
-   procedure Free_CPU(Tid : Task_Id := Current_Task);
+   type Dispatching_Domain is private;
 
-   function Get_CPU(Tid : Task_Id := Current_Task) return CPU;
+   System_Dispatching_Domain : Dispatching_Domain;
 
+   function Create(First,Last : CPU;
+            DP : in Dispatching_Policy) return Dispatching_Domain;
 
-   procedure Delay_Until_And_Set_CPU(T : Ada.Real_Time.Time;
-                                           P : CPU);
-   -- raises CPU_NOT_IN_Allocation_DOMAIN if P not in current AD for Tid
+   -- 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.
 
-private
-   type Allocation_Domain is new CPU_Set;
-   System_Allocation_Domain : constant Allocation_Domain := (others => True);
+   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
 
-end Ada.System.Scheduling.Domains;
+   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
 
-The required behaviour of each subprogram is as follows;
+   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
 
-Create: creates a new AD and moves CPUs from 'System' AD to this
-new AD. A CPU cannot be moved if it has a task assigned to it.
-The 'System' AD must not be emptied of CPUs as it always contains
-the environment task. Note, that there is still only one environment
-task.
+   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
 
-Get_CPU_Set and Get_Allocation_Domain are straightforward.
+   procedure Free_CPU(T : in Task_Id := Current_Task);
 
-There are two Allocate_Task procedures. One allocates the task just to
-an AD (for global scheduling) the other allocates it to an AD and assigns
-a specific CPU within that AD (for partitioned scheduling).
-The language could allow tasks to migrate between ADs, or raise an
-exception if the task is already allocated.
+   function Get_CPU(T : in Task_Id := Current_Task) return CPU_Range;
+   -- returns 0 if T is not set to a specific CPU
 
-Set_CPU assigns the task to the CPU. The task can now only
-execute on that 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
 
-Free_CPU removes the CPU specific assignment. The task can
-now execute on any CPU within its AD.
+private
+  -- not defined by the language
+end System.Multiprocessors.Dispatching.Domains;
 
-Get_CPU returns the CPU on which the designated task is
-executing. Note that if the task is not assigned to a specific
-CPU then the value returned may change asynchronously. An
-alternative behaviour would be to raise an exception if the task
-is not assigned.
 
-Delay_Until_And_Set_CPU delays a task and then assigns the task
-to the specified CPU when the delay expires. This is needed
-for some scheduling schemes.
+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.
 
-In addition to these two packages there are two new pragmas required
-to control the affinity of tasks during activation:
+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.
 
-pragma Allocation_Domain (AD : Allocation_Domain);
-pragma CPU (P : CPU);
+Get_Dispatching_Domain  -- as the names imply.
 
-If no affinities are declared then a task will inherit the AD
-and CPU (if assigned) of its parent task.
+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.
 
-For protected objects there is no need for affinities, it is the
-tasks that have ADs 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):
+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).
 
-function Get_CPUs(I: Interrupt_Id) return CPU_Set;
+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.
 
 
-For most platforms only one CPU will be identified in
-the returned set. But it is possible for more than one CPU
-to be capable of handling a particular interrupt (although an
-occurrence of the interrupt will only be delivered to one of these
-CPUs).
+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);
 
-Each AD is, in effect, scheduled independently; and hence could be
-subject to different dispatching policies. This is supported as
-follows.
 
-All ADs have the same range of priorities (System.Any_Priority).
+The following points should be emphasized.
 
-The 'System' AD, System_Allocation_Domain, is subject to the
-policies defined using the configuration pragmas: Task_Dispatching_
-Policy and Priority_Specific_Dispatching.
+All dispatching domains have the same range of priorities System.Any_Priority.
 
-All other ADs have as default those of System_Allocation_Domain
-but can re-define their policies by using the following
-library routines:
+The `System' dispatching domain, System_Dispatching_Domain, is subject to the
+policies defined using the configuration pragmas:
+Task_Dispatching_Policy and Priority_Specific_Dispatching.
 
-procedure Task_Dispatching_Policy(AD : Allocation_Domain; ...);
+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.
 
-procedure Priority_Specific_Dispatching(AD : Allocation_Domain; ...);
 
-Extra definitions will be needed to make these equivalent to the
-current pragmas. These procedure could be defined in the
-package above.
+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):
 
-Ideally a program should only be able to call Create and these
-dispatching policy routines at the library level.
 
+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
 
 
-There are a number of implementation characteristics 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 delay queue and
-ready queue manipulations (and user code - Timing Events)
-executed must be documented. As there is no scheduling
-between ADs an implementation is recommended to have distinct
-queues per AD.
+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 implementation must also document how it implements Ceiling_Locking
-for protected actions, in particular what happens to a task
-that calls an occupied PO. The implementation advice will be for
-the task to spin at its current active priority level - and then
-run at the (higher) ceiling level once it has gained access.
 
 
 !wording
@@ -269,7 +280,7 @@
 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 allocation domains, is not
+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.
 
@@ -278,7 +289,7 @@
 (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. 
+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
@@ -289,14 +300,14 @@
 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 an allocation domain has some similarities to the current
+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 allocation domains
+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 ADs is such that a simple system with just one
-AD will not need to consider these domains. Moreover, if global
+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.
 

Questions? Ask the ACAA Technical Agent