Chapter 6: Concurrency - TOC - 6.1 CONCURRENCY OPTIONS

6.1.6 Priorities

guideline

Do not rely on pragma Priority unless your compiler supports the Real-Time Annex (Ada Reference Manual 1995, Annex D) and priority scheduling.

Minimize risk of priority inversion by use of protected objects and ceiling priority.

Do not rely upon task priorities to achieve a particular sequence of task execution.

example

For example, let the tasks have the following priorities:

task T1 is
   pragma Priority (High);
end T1;

task T2 is
   pragma Priority (Medium);
end T2;

task Server is
   entry Operation (...);
end Server;

----------------------------
task body T1 is
begin
   ...
   Server.Operation (...);
   ...
end T1;
task body T2 is
begin
   ...
   Server.Operation (...);
   ...
end T2;

task body Server is
begin
   ...
   accept Operation (...);
   ...
end Server;

At some point in its execution, T1 is blocked. Otherwise, T2 and Server might never execute. If T1 is blocked, it is possible for T2 to reach its call to Server's entry (Operation) before T1. Suppose this has happened and that T1 now makes its entry call before Server has a chance to accept T2's call.

This is the timeline of events so far:

T1 blocks
T2 calls Server.Operation
T1 unblocks
T1 calls Server.Operation
-- Does Server accept the call from T1 or from T2?

You might expect that, due to its higher priority, T1's call would be accepted by Server before that of T2. However, entry calls are queued in first-in-first-out (FIFO) order and not queued in order of priority (unless pragma Queueing_Policy is used). Therefore, the synchronization between T1 and Server is not affected by T1's priority. As a result, the call from T2 is accepted first. This is a form of priority inversion. (Annex D can change the default policy of FIFO queues.)

A solution might be to provide an entry for a High priority user and an entry for a Medium priority user.

---------------------------------------------------------------------
task Server is
   entry Operation_High_Priority;
   entry Operation_Medium_Priority;
   ...
end Server;
---------------------------------------------------------------------
task body Server is
begin
   loop
      select
         accept Operation_High_Priority do
            Operation;
         end Operation_High_Priority;
      else  -- accept any priority
         select
            accept Operation_High_Priority do
               Operation;
            end Operation_High_Priority;
         or
            accept Operation_Medium_Priority do
               Operation;
            end Operation_Medium_Priority;
         or
            terminate;
         end select;
      end select;
   end loop;
...
end Server;
---------------------------------------------------------------------

However, in this approach, T1 still waits for one execution of Operation when T2 has already gained control of the task Server. In addition, the approach increases the communication complexity (see Guideline 6.2.6).

rationale

The pragma Priority allows relative priorities to be placed on tasks to accomplish scheduling. Precision becomes a critical issue with hard-deadline scheduling. However, there are certain problems associated with using priorities that warrant caution.

Priority inversion occurs when lower priority tasks are given service while higher priority tasks remain blocked. In the first example, this occurred because entry queues are serviced in FIFO order, not by priority. There is another situation referred to as a race condition . A program like the one in the first example might often behave as expected as long as T1 calls Server.Operation only when T2 is not already using Server.Operation or waiting. You cannot rely on T1 always winning the race because that behavior would be due more to fate than to the programmed priorities. Race conditions change when either adding code to an unrelated task or porting this code to a new target.

You should not rely upon task priorities to achieve an exact sequence of execution or rely upon them to achieve mutual exclusion. Although the underlying dispatching model is common to all Ada 95 implementations, there might be differences in dispatching, queuing, and locking policies for tasks and protected objects. All of these factors might lead to different sequences of execution. If you need to ensure a sequence of execution, you should make use of Ada's synchronization mechanisms, i.e., protected objects or rendezvous.

notes

Work is being done to minimize these problems, including the introduction of a scheduling algorithm known as the priority ceiling protocol (Goodenough and Sha 1988). The priority ceiling protocol reduces the blocking time that causes priority inversion to only one critical region (defined by the entries in a task). The protocol also eliminates deadlock (unless a task recursively tries to access a critical region) by giving a ceiling priority to each task accessing a resource that is as high as the priority of any task that ever accesses that resource. This protocol is based on priority inheritance and, thus, deviates from the standard Ada tasking paradigm, which supports priority ceiling emulation instead of the priority ceiling blocking that occurs with priority inheritance.

Priorities are used to control when tasks run relative to one another. When both tasks are not blocked waiting at an entry, the highest priority task is given precedence. However, the most critical tasks in an application do not always have the highest priority. For example, support tasks or tasks with small periods might have higher priorities because they need to run frequently.

All production-quality validated Ada 95 compilers will probably support pragma Priority. However, you should use caution unless (Annex D is specifically supported.

There is currently no universal consensus on how to apply the basic principles of rate monotonic scheduling (RMS) to the Ada 95 concurrency model. One basic principle of RMS is to arrange all periodic tasks so that tasks with shorter periods have higher priorities than tasks with longer periods. However, with Ada 95, it might be faster to raise the priorities of tasks whose jobs suddenly become critical than to wait for an executive task to reschedule them. In this case, priority inversion can be minimized using a protected object with pragma Locking_Policy(Ceiling_Locking) as the server instead of a task.