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 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

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.

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.

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.

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

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

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

and deadlines can similarly be set by the pragma Relative_Deadline thus

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

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

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

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

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

then this is not the same us

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

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 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.

Rationale for Ada 2005

5.5 Scheduling and dispatching