Version 1.7 of ais/ai-00327.txt
!standard D.03 (00) 03-11-24 AI95-00327/04
!class amendment 03-06-05
!status work item 03-06-05
!status received 03-06-05
!subject Dynamic ceiling priorities
An implementation of dynamic ceiling priorities is proposed. The ceiling
priority of a protected object (PO) would be dynamically changed by giving
access to a new attribute of a protected object.
The ceiling must be changed whilst mutual exclusion for the PO is in force,
according to the ceiling locking protocol. This is the only way to ensure a
consistent ceiling change without the need for a further lock to protect the
ceiling change. Examples are provided to show how to use this feature.
A prototype implementation by Javier Miranda, Edmond Schonberg and Jorge Real
concludes that the overheads of this feature is small and not distributed.
In Ada, the ceiling priority of a PO is static and thus it can only be set
once, by means of pragma Priority, at PO creation time. In contrast, task
priorities may be set dynamically. The ability to dynamically change protected
object ceiling priorities is especially required in situations where dynamic
task priority change occurs, or where a library containing POs with inadequate
ceilings is used by an application-specific set of tasks and interrupt handlers.
Examples of dynamic task priority changes include:
- multi-moded systems
- systems scheduled using dynamic priorities
For multi-moded systems, a common workaround is to use the so-called "ceiling
of ceilings", i.e. the highest ceiling that the PO can have across all operating
modes. Clearly this approach is error-prone, particularly during composition
of sub-systems, and may have a considerable impact on blocking times. The use of
ceiling of ceilings implies that a task running in a particular mode can be
blocked by another one unnecessarily, due to an inflated ceiling priority
resulting from the requirements of a different mode of operation. Consequently,
the ceiling of ceilings reduces the schedulability of the task set.
Add a new section:
D.5.1 Dynamic Priorities for Protected Objects
This clause specifies how the priority of a protected object can be
modified or queried at run time.
The following attribute of a protected object is defined:
Yields a variable component of the enclosing protected
object P (or current instance of the enclosing protected type P) of
type System.Any_Priority, which denotes the priority of P. Use of
this attribute is allowed only inside a protected body of P.
The attribute is part of the current instance of the protected object;
it is thus defined to be a constant within the body of a protected function,
but a variable within the body of a protected procedure and an entry_body.
When the locking policy in effect defines priorities for protected
objects, 'Priority denotes the priority of the designated protected
object. Otherwise, the meaning of 'Priority is implementation defined.
If Locking_Policy Ceiling_Locking is specified then the ceiling priority
of a protected object P is set to the value of P'Priority at the end
of each protected action of P.
If Locking_Policy Ceiling_Locking is specified then it is a bounded error to
lower the priority of a protected object below the active priority of any task
that is queued on an entry of the protected object. In this case one of the
- Program_Error exception is raised in the queued task;
- the entry body is executed, when the entry is open, at the ceiling
priority of the protected object;
- the entry body is executed, when the entry is open, at the ceiling
priority of the protected object and Program_Error exception is raised in
the queued task;
- the entry body is executed, when the entry is open, at the
ceiling priority of the protected object that was in effect when the
entry call was queued.
The implementation shall document the following metric:
The difference in execution time of calls to the following procedures
in protected object P,
protected P is
procedure Do_Not_Set_Ceiling (Pr : System.Any_Priority) is
procedure Set_Ceiling (Pr : System.Any_Priority) is
P'Priority := Pr;
The value of P'Priority following an assignment to the attribute immediately
reflects the new value even though its impact on the ceiling priority of P is
postponed until completion of the protected action in which it is executed.
Change the definition of Restriction identifier No_Dynamic_Priorities:
There are no semantic dependences on the package Dynamic_Priorities, and
occurrences of attribute 'Priority are not allowed.
Change D.5(11) to reflect the words used above.
A simple example on how to use the proposed features is given in this
protected type My_Protected is
procedure Set_My_Ceiling(Pr: in System.Any_Priority);
protected body My_Protected is
procedure Set_My_Ceiling(Pr : in System.Any_Priority) is
My_Protected'Priority := Pr;
In this example, the caller to Set_My_Ceiling must know the name of
the PO whose ceiling is to be changed - the call would have the form
PO.Set_My_Ceiling(Pr). A more flexible scheme can easily be obtained by
means of an access-to-protected-subprogram, that could be used in the
implementation of a general ceiling changer:
type General_Set_Ceiling is access protected procedure
(P: in System.Any_Priority);
Once the access object is properly initialised, the call would take the form:
The use of a protected interface could also achieve this functionality.
Both the old and new values of the ceiling must be retained by the
implementation, as an external call needs to have its priority checked
against the old value until the new
value takes effect, at the end of the protected action.
The interface to these features, e.g. the use of P'Priority
appears to be the easiest way of achieving the required functionality.
The need for dynamic ceilings and a detailed examination of the many
different ways it could be achieved has been the subject of much
discussion at four IRTAWs. The following is a summary.
Two primary approaches have been considered to make this proposal:
a) To implement the ceiling change as a special operation on the PO, not
necessarily as a protected operation under the ceiling locking protocol.
b) To implement the ceiling change as a protected operation.
We will discuss now the main problems with a) and later on, how b) solves them.
-- IMPLEMENTATION AS A SPECIAL OPERATION --
The motivation for a) was to be able to change a PO's ceiling from any
priority, lower or higher than the ceiling, thus allowing to promptly change
the ceilings from a high priority mode changer (in the mode change scenario).
This approach was inspired by the use of ceilings in POSIX mutexes. Let's
Three cases can be identified with respect to the relative priorities of tasks
executing a protected operation, the task assigning to 'Priority -referred to as
the "caller"- and the current and new ceiling priorities:
case 1: The caller has a lower or equal priority to the current ceiling
and is changing the ceiling to a higher priority. in this situation the
ceiling change can take place without problems. The priority change occurs
and tasks on entry queues are not affected. They may just inherit the new
ceiling when they execute the protected operation, which will be higher or
equal to their base priority.
case 2: The caller has a lower or equal priority to the current ceiling, as
in case 1, but now it is changing the ceiling to a lower priority. Here,
it is possible that tasks queued on entries might have active priorities
higher than the new ceiling. in this situation, the Ceiling_Locking policy could be
violated and it would be necessary to raise an appropriate exception to the
queued tasks. Currently in Ada, Program_Error is raised when a task tries to
call a protected operation in a protected object with a lower ceiling priority.
case 3: The caller has a higher priority than the current ceiling. Hence,
the ceiling change cannot adhere to the ceiling protocol to change the
ceiling priority. The POSIX 1003.1b standard says exactly the same about
the operation provided for changing the ceiling of a mutex. Cases 1 or 2
still apply with respect to the relationship between the old and new
The worst case is represented by the third situation, where data corruption may
occur. It could be the case that a task with a priority 10 wants to change the
ceiling priority of a protected object with a ceiling lower than 10, say 8. The
next figure shows graphically this scenario, where "ti" represents a task with
priority "i". A task with a lower priority, say 5, could be executing a
protected action (with an active priority 8) when it was preempted by the high
priority task t10. The main problem here is that a task with a medium priority,
say 8, that uses the same protected object, can be released whilst t5 is
preempted by t10. When t10 completes, the medium priority task t8 starts to run
when t5 is still in the middle of the protected operation. The risk of data
corruption in the protected object is clear. A well designed program can avoid
this situation, but it would be very difficult for the language to detect it.
t10 | |*|
Change ceiling from 8 to 6 --- Ready
__ __ _
t8 ---| |**| | |
|__|__| |_| Running
ACCESS TO HALF-UPDATED PO! |*|
__ _ |_| Executing
t5 | |*| protected
updated ------> time
Two possible solutions to this problem have been identified; unfortunately,
both present important drawbacks. The first one is to use a lock on the PO that
would prevent t8 in the example above to access the PO. The lock eliminates the
risk for data corruption but the use of locks can cause well-known priority
inversion problems. More importantly, the implementation of ceiling locking
on a mono-processor does not require a lock. Hence this solution should also
be rejected for efficiency reasons.
A second way to avoid the potential for data corruption is that the task
executing the protected action when a ceiling change happens to occur,
"immediately" inherits the new ceiling. In such case, no other task accessing
the protected object can preempt it, therefore the protected action will be
normally completed even in the presence of a ceiling change. A possible
implementation of an assignment to 'Priority conforming to such semantics
would be the following:
1. Change variable "ceiling" to New_Ceiling
2. if PO_In_Use and Prio(User_Task) < New_Ceiling then
3. User_Task inherits New_Ceiling
4. end if
A problem with this approach is that the runtime needs to know the identity of
the task running the protected action -the User_Task-, something that is not
needed in Ada but for this particular case. This approach therefore also
suffers from implementation impact on efficiency, and so we have rejected it.
-- IMPLEMENTATION AS A PROTECTED OPERATION --
The second approach (the one that is advocated in this AI) proposes to
implement the ceiling change as a protected operation, there by avoiding
the problems described above.
For a given protected object PO, we shall assume the existence of a predefined
procedure Set_Ceiling, implemented as an assignment to 'Priority, with an "in"
parameter of the type System.Any_Priority that expresses the new ceiling
priority for PO. This attribute can only be used immediately within the body of
a protected procedure or entry of the affected PO, thus its use is subject to
the ceiling locking policy. This means that a task calling it must have a
priority lower than or equal to the protected object's ceiling.
Accordingly, a task calling Set_Ceiling will be executed in mutual exclusion
with other potential users of the protected object, therefore ensuring that no other
task is executing a protected action when the ceiling is changed. This approach
avoids the situation described previously, where data consistency was at risk
due to the asynchronous nature of the ceiling change when it is implemented as
a special operation. It also makes it unnecessary to use a lock on the PO. If
Set_Ceiling is implemented as a protected operation, the standard implementation
of ceiling locking is sufficient to guarantee its execution in mutual exclusion
with other users of the protected object.
With respect to tasks queued on protected entries, it could be the case that
the ceiling of the protected object is lowered below the queued task's active
priority, which represents a bounded error in Ada. According to the Ada
Reference Manual, paragraph D.5(11):
"If a task is blocked on a protected entry call, and the call is queued,
it is a bounded error to raise its base priority above the ceiling
priority of the corresponding protected object."
In other words, if dynamic ceilings are considered, this rule would also apply
to the case where a protected object's ceiling is set below the active priority
of tasks queued on the protected object's entries. The situation is already
considered by the language, therefore no new problems are introduced in this
Note that we propose that the new ceiling should take effect at the end of the
protected action, instead of at the end of the protected operation that executes
the Set_Ceiling call. This is intended to reduce the risk of Program_Error for
queued tasks that have already successfully performed the initial entry call with
respect to the ceiling check. Those tasks for whom the barrier becomes open as
part of the same protected action as is changing the ceiling will be successfully
executed at the old ceiling priority. Thus the only tasks that will be affected
are those that remain blocked after the entire protected action has been completed.
Paper  contains further discussions on the motivation behind the proposal
and other examples (for an earlier version of the feature). Dynamic ceilings
have been implemented in an existing Ada compiler. The report on this
experience can be found in .
 J. Real, A. Crespo, A. Wellings, and A. Burns. Protected Ceiling
Changes. Proceedings of the 11th International Real-Time Ada Workshop.
Ada Letters XXII(4). December 2002.
 J. Miranda, E. Schonberg, M. Masmano, J. Real and A. Crespo.
Dynamic Ceiling Priorities in GNAT. Proceedings of the 12th International
Real-Time Ada Workshop. To appear in Ada Letters, December 2003.
From: Alan Burns
Sent: Thursday, June 5, 2003 5:02 AM
The Real-Time workshop has discussed at some length the
incorporation of dynamic ceiling for POs. A number of
solution have been proposed and discussed. In the attached
AI is the concensus proposal which I offer as a new AI.
[Editor's note: This is version /01 of the AI.]
From: Alan Burns
Sent: Monday, August 11, 2003 8:14 AM
Attached is new version of AI 327 (dynamic
priorities for POs).
I have followed the suggestions of Tucker (and the
minutes). If anyone has time to look at the details
of the ammended proposal and agree I could produce
the wording section before the next meeting.
Version 1 of this AI contains detailed discussions on the motivation
behind the proposal and further examples (for an earlier version of
From: Randy Brukardt
Sent: Wednesday, September 10, 2003 11:12 PM
I've looked at this AI. I think the general idea is what was discussed at the
meeting. A couple of specific comments:
1) Is it necessary to return the 'old' value of the priority? I recall Tucker
wanting to avoid that, as it increases the overhead of a protected object (you
have to have two priority values). Since no other task can read it anyway (to
do so would violate the PO locking rules), so all you're doing is hiding a
change the operation made from itself. That seems silly.
2) I think that some of the motivation for allowing this only during a
protected operation needs to be retained in the discussion. Older versions of
AIs are for historical reference only, and shouldn't be depended on to provide
important information. OTOH, I don't really want to see 5 pages of diagrams,
3) The bounded error text says Program_Error is raised (fine) or queued tasks
execute with the lower priority (fine) or both (??) or neither (??). "Neither"
is weird wording; I'd probably say what was actually meant (queued tasks
execute with the original priority - at least, I think that was what was
meant). And "both" is weirder: if Program_Error is raised, how can it be
executing in the PO at all? Any handler would be in the context of the caller,
and would use that priority, I hope.
From: Alan Burns
Sent: Thursday, September 11, 2003 11:47 AM
> I've looked at this AI. I think the general idea is what was discussed at
> the meeting. A couple of specific comments:
> 1) Is it necessary to return the 'old' value of the priority? I recall
> Tucker wanting to avoid that, as it increases the overhead of a protected
> object (you have to have two priority values). Since no other task can
> it anyway (to do so would violate the PO locking rules), so all you're
> is hiding a change the operation made from itself. That seems silly.
OK, will change to reflect this - after the Real-Time Workshop
> 2) I think that some of the motivation for allowing this only during a
> protected operation needs to be retained in the discussion. Older versions
> of AIs are for historical reference only, and shouldn't be depended on to
> provide important information. OTOH, I don't really want to see 5 pages of
> diagrams, either.
OK, will bring some of this text back
> 3) The bounded error text says Program_Error is raised (fine) or queued
> tasks execute with the lower priority (fine) or both (??) or neither (??).
> "Neither" is weird wording; I'd probably say what was actually meant
> tasks execute with the original priority - at least, I think that was what
> was meant). And "both" is weirder: if Program_Error is raised, how can it
> executing in the PO at all? Any handler would be in the context of the
> caller, and would use that priority, I hope.
This is the same case as dynamic priorities for tasks, and these
words are exactly those currently used in the LRM (D.5.11) - ie
'neither' is your word, weird or not.
From: Randy Brukardt
Sent: Thursday, September 11, 2003 4:27 PM
> This is the same case as dynamic priorities for tasks, and these
> words are exactly those currently used in the LRM (D.5.11) - ie
>'neither' is your word, weird or not.
Two wrongs don't make a right. (And it certainly isn't my word; I didn't have
anything to do with writing the Ada 95 standard, and certainly not Annex D.)
It certainly is fair to copy existing wording, but I still think we need to
look at it, because it is very confusing the way it is.
Questions? Ask the ACAA Technical Agent