Rationale for Ada 2005

John Barnes
Contents   Index   References   Search   Previous   Next 

5.5 Scheduling and dispatching

Another area of increased flexibility in Ada 2005 is that of task dispatching policies. In Ada 95, the only predefined policy is FIFO_Within_Priorities although other policies are permitted. Ada 2005 provides further pragmas, policies and packages which facilitate many different mechanisms such as non-preemption within priorities, the familiar Round Robin using timeslicing, and the more recently acclaimed Earliest Deadline First (EDF) policy. Moreover it is possible to mix different policies according to priority level within a partition.
In order to accommodate these many changes, Section D.2 (Priority Scheduling) of the Reference Manual has been reorganized as follows 
D.2.1  The Task Dispatching Model
D.2.2  Task Dispatching Pragmas
D.2.3  Preemptive Dispatching
D.2.4  Non-Preemptive Dispatching
D.2.5  Round Robin Dispatching
D.2.6  Earliest Deadline First Dispatching
Overall control is provided by two pragmas. They are 
pragma Task_Dispatching_Policy(policy_identifier);
pragma Priority_Specific_Dispatching(
                          policy_identifer,
                          first_priority_expression,
                          last_priority_expression);
The pragma Task_Dispatching_Policy, which already exists in Ada 95, applies the same policy throughout a whole partition. The pragma Priority_Specific_Dispatching, which is new in Ada 2005, can be used to set different policies for different ranges of priority levels.
The full set of predefined policies in Ada 2005 is
FIFO_Within_Priorities

This already exists in Ada 95. Within each priority level to which it applies tasks are dealt with on a first-in-first-out basis. Moreover, a task may preempt a task of a lower priority.
Non_Preemptive_FIFO_Within_Priorities

This is new in Ada 2005. Within each priority level to which it applies tasks run to completion or until they are blocked or execute a delay statement. A task cannot be preempted by one of higher priority. This sort of policy is widely used in high integrity applications.
Round_Robin_Within_Priorities

This is new in Ada 2005. Within each priority level to which it applies tasks are timesliced with an interval that can be specified. This is a very traditional policy widely used since the earliest days of concurrent programming.
EDF_Across_Priorities

This is new in Ada 2005. This provides Earliest Deadline First dispatching. The general idea is that within a range of priority levels, each task has a deadline and that with the earliest deadline is processed. This is a fashionable new policy and has mathematically provable advantages with respect to efficiency. 
For further details of these policies consult Concurrent and Real-Time Programming in Ada 2005 by Alan Burns and Andy Wellings [8].
These various policies are controlled by the package Ada.Dispatching plus two child packages. The root package has specification
package Ada.Dispatching is
   pragma Pure(Dispatching);
   Dispatching_Policy_Error: exception;
end Ada.Dispatching;
As can be seen this root package simply declares the exception Dispatching_Policy_Error which is used by the child packages.
The child package Round_Robin enables the setting of the time quanta for time slicing within one or more priority levels. Its specification is
with System;  use System;
with Ada.Real_Time;  use Ada.Real_Time;
package Ada.Dispatching.Round_Robin is
   Default_Quantum: constant Time_Span := implementation-defined;
   procedure Set_Quantum(Pri: in Priority, Quantum: in Time_Span);
   procedure Set_Quantum(Low, High: in Priority; Quantum: in Time_Span);
   function Actual_Quantum(Pri: Priority) return Time_Span;
   function Is_Round_Robin(Pri: Priority) return Boolean;
end Ada.Dispatching.Round_Robin;
The procedures Set_Quantum enable the time quantum to be used for time slicing to be set for one or a range of priority levels. The default value is of course the constant Default_Quantum. The function Actual_Quantum enables us to find out the current value of the quantum being used for a particular priority level. Its identifier reflects the fact that the implementation may not be able to apply the exact actual value given in a call of Set_Quantum. The function Is_Round_Robin enables us to check whether the round robin policy has been applied to the given priority level. If we attempt to do something stupid such as set the quantum for a priority level to which the round robin policy does not apply then the exception Dispatching_Policy_Error is raised.
The other new policy concerns deadlines and is controlled by a new pragma Relative_Deadline and the child package Dispatching.EDF. The syntax of the pragma is
pragma Relative_Deadline(relative_deadline_expression);
The deadline of a task is a property similar to priority and both are used for scheduling. Every task has a priority of type Integer and every task has a deadline of type Ada.Real_Time.Time. Priorities can be set when a task is created by pragma Priority
task T is
   pragma Priority(P);
and deadlines can similarly be set by the pragma Relative_Deadline thus
task T is
   pragma Relative_Deadline(RD);
The expression RD has type Ada.Real_Time.Time_Span. Note carefully that the pragma sets the relative and not the absolute deadline. The initial absolute deadline of the task is 
Ada.Real_Time.Clock + RD
where the call of Clock is made between task creation and the start of its activation.
Both pragmas Priority and Relative_Deadline can appear in the main subprogram and they then apply to the environment task. If they appear in any other subprogram then they are ignored. Both properties can also be set via a discriminant. In the case of priorities we can write 
task type TT(P: Priority) is
   pragma Priority(P);
   ...
end;
High_Task: TT(13);
Low_Task: TT(7);
We cannot do the direct equivalent for deadlines because Time_Span is private and so not discrete. We have to use an access discriminant thus 
task type TT(RD: access Timespan) is
   pragma Relative_Deadline(RD.all);
   ...
end;
One_Sec: aliased constant Time_Span := Seconds(1);
Ten_Mins: aliased constant Time_Span := Minutes(10);
Hot_Task: TT(One_Sec'Access);
Cool_Task: TT(Ten_Mins'Access);
Note incidentally that functions Seconds and Minutes have been added to the package Ada.Real_Time. Existing functions Nanoseconds, Microseconds and Milliseconds in Ada 95 enable the convenient specification of short real time intervals (values of type Time_Span). However, the specification of longer intervals such as four minutes meant writing something like Milliseconds(240_000) or perhaps 4*60*Milliseconds(1000). In view of the fact that EDF scheduling and timers (see 5.6) would be likely to require longer times the functions Seconds and Minutes are added in Ada 2005. There is no function Hours because the range of time spans is only guaranteed to be 3600 seconds anyway. (The numerate will recall that 3600 seconds is one hour.)
If a task is created and it does not have a pragma Priority then its initial priority is that of the task that created it. If a task does not have a pragma Relative_Deadline then its initial absolute deadline is the constant Default_Deadline in the package Ada.Dispatching.EDF; this constant has the value Ada.Real_Time.Time_Last (effectively the end of the universe).
Priorities can be dynamically manipulated by the subprograms in the package Ada.Dynamic_Priorities and deadlines can similarly be manipulated by the subprograms in the package Ada.Dispatching.EDF whose specification is 
with Ada.Real_Time;  use Ada.Real_Time;
with Ada.Task_Identification; use Ada.Task_Identification;
package Ada.Dispatching.EDF is
   subtype Deadline is Ada.Real_Time.Time;
   Default_Deadline: constant Deadline := Time_Last;
   procedure Set_Deadline(D: in Deadline; T: in Task_Id := Current_Task);
   procedure Delay_Until_And_Set_Deadline (
                                                    Delay_Until_Time: in Time;
                                                    Deadline_Offset: in Time_Span);
   function Get_Deadline(T: Task_Id := Current_Task) return
Deadline;
end Ada.Dispatching.EDF;
The subtype Deadline is just declared as a handy abbreviation. The constant Default_Deadline is set to the end of the universe as already mentioned. The procedure Set_Deadline sets the deadline of the task concerned to the value of the parameter D. The long-winded Delay_Until_And_Set_Deadline delays the task concerned until the value of Delay_Until_Time and sets its deadline to be the interval Deadline_Offset from that time – this is useful for periodic tasks. The function Get_Deadline enables us to find the current deadline of a task.
It is important to note that this package can be used to set and retrieve deadlines for tasks whether or not they are subject to EDF dispatching. We could for example use an ATC on a deadline overrun (ATC = Asynchronous Transfer of Control using a select statement). Hence there is no function Is_EDF corresponding to Is_Round_Robin and calls of the subprograms in this package can never raise the exception Dispatching_Policy_Error.
If we attempt to apply one of the subprograms in this package to a task that has already terminated then Tasking_Error is raised. If the task parameter is Null_Task_Id then Program_Error is raised.
As mentioned earlier, a policy can be selected for a whole partition by for example 
pragma Task_Dispatching_Policy(Round_Robin_Within_Priorities);
whereas in order to mix different policies across different priority levels we can write
pragma Priority_Specific_Dispatching(Round_Robin_Within_Priority, 1, 1);
pragma Priority_Specific_Dispatching(EDF_Across_Priorities, 2, 10);
pragma Priority_Specific_Dispatching(FIFO_Within_Priority, 11, 24);
This sets Round Robin at priority level 1, EDF at levels 2 to 10, and FIFO at levels 11 to 24. This means for example that none of the EDF tasks can run if any of the FIFO ones can. In other words if any tasks in the highest group can run then they will do so and none in the other groups can run. The scheduling within a range takes over only if tasks in that range can go and none in the higher ranges can.
Note that if we write
pragma Priority_Specific_Dispatching(EDF_Across_Priorities, 2, 5);
pragma Priority_Specific_Dispatching(EDF_Across_Priorities, 6, 10);
then this is not the same us
pragma Priority_Specific_Dispatching(EDF_Across_Priorities, 2, 10);
despite the fact that the two ranges in the first case are contiguous. This is because in the first case any task in the 6 to 10 range will take precedence over any task in the 2 to 5 range whatever the deadlines. If there is just one range then only the deadlines count in deciding which tasks are scheduled. This is emphasized by the fact that the policy name uses Across rather than Within. For other policies such as Round_Robin_Within_Priority two contiguous ranges would be the same as a single range.
We conclude this section with a few words about ceiling priorities.
In Ada 95, the priority of a task can be changed during execution but the ceiling priority of a protected object cannot be so changed. It is permanently set when the object is created using the pragma Priority. This is often done using a discriminant so that at least different objects of a given protected type can have different priorities. Thus we might have 
protected type PT(P: Priority) is
   pragma Priority(P);
   ...
end PT;
PO: PT(7);    -- ceiling priority is 7
The fact that the ceiling priority of a protected object is static can be a nuisance in many applications especially when the priority of tasks can be dynamic. A common workaround is to give a protected object a higher ceiling than needed in all circumstances (often called "the ceiling of ceilings"). This results in tasks having a higher active priority than necessary when accessing the protected object and this can interfere with the processing of other tasks in the system and thus upset overall schedulability. Moreover, it means that a task of high priority can access an object when it should not (if a task with a priority higher than the ceiling priority of a protected object attempts to access the object then Program_Error is raised – if the object has an inflated priority then this check will pass when it should not).
This difficulty is overcome in Ada 2005 by allowing protected objects to change their priority. This is done through the introduction of an attribute Priority which applies just to protected objects. It can only be accessed within the body of the protected object concerned.
As an example a protected object might have a procedure to change its ceiling priority by a given amount. This could be written as follows 
protected type PT is
   procedure Change_Priority(Change: in Integer);
   ...
end;
protected body PT is
   procedure Change_Priority(Change: in Integer) is
   begin
      ...       -- PT'Priority has old value here
      PT'Priority := PT'Priority + Change;
      ...       -- PT'Priority has new value here
      ...
   end Change_Priority;
   ...
end PT;
Changing the ceiling priority is thus done while mutual exclusion is in force. Although the value of the attribute itself is changed immediately when the assignment is made, the actual ceiling priority of the protected object is only changed when the protected operation (in this case the call of Change_Priority) is finished. Note that if any of the procedures of the protected object is an interrupt handler (through pragma Attach_Handler or Interrupt_Handler) then a check is made that the value is in the range of System.Interrupt_Priority; Program_Error is raised if the check fails.
Note the unusual syntax. Here we permit an attribute as the destination of an assignment statement. This happens nowhere else in the language. Other forms of syntax were considered but this seemed the most expressive.

Contents   Index   References   Search   Previous   Next 
© 2005, 2006, 2007 John Barnes Informatics.
Sponsored in part by:
The Ada Resource Association and its member companies: ARA Members AdaCore Polyspace Technologies Praxis Critical Systems IBM Rational Sofcheck and   Ada-Europe:
Ada-Europe