Version 1.1 of ais/ai-00327.txt
!standard D.03 (00) 03-06-05 AI95-00327/01
!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 a protected
procedure attribute of the PO, which could only be invoked from within a
procedure or entry of the PO.
A similar mechanism, in the form of a protected function attribute, is proposed
to read the current ceiling of a PO. The protected function attribute could be
invoked from within any protected operation of the PO. In addition, it could
also be used in barrier expressions associated to entries of the PO.
A new pragma is proposed which explicitly states that these attributes
will be used.
With these mechanisms, the ceiling must be changed from a valid priority,
according to the ceiling locking protocol. This is the only way to ensure a
consistent ceiling change without the need for a lock to protect the ceiling
change. Examples are provided to show how to use this feature. The proposal
is the result of considerable discussion at IRTAW and represents the most
effect solution (of the very many that are possible).
A prototype implementation by 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 assigned
once, by means of pragma Priority, at PO creation time. In contrast with that,
tasks' priorities are dynamic. The ability to dynamically changing ceiling
priorities is specially useful in:
- multi-moded systems,
- systems scheduled with dynamic priorities and
- dynamically adapting library units containing POs.
For multi-moded systems, a common workaround is to use the so called "ceiling
of ceilings", i.e. the highest ceiling that PO will have across all operating
modes. Unfortunately, this approach is not elegant and may have a considerable
impact on blocking times: by using the ceiling of ceilings, a task running in a
particular mode can be blocked by another one due to the ceiling priority of a
PO being higher in another operating mode. It can be the case that the priority
assignment for that particular mode would produce a lower ceiling for the PO,
thus resulting in a null blocking time for some tasks.
Overall, the ceiling of ceilings reduces the feasibility of the task set.
Similar considerations hold for the other two situations (dynamic priority
systems and adapting libraries).
Two new protected subprogram attributes are proposed to assign or read the
current PO's ceiling priority: 'Set_Ceiling and 'Get_Ceiling, respectively.
These attributes can only be used from within the PO. More precisely:
- 'Set_Ceiling can only be called from within a protected procedure or
entry of the affected PO.
- 'Get_Ceiling can be called from within any protected operation of the
affected PO and it can also be used in barrier expressions at entries
of the affected PO.
The prefix for both attributes can denote a protected type or a protected
object. The programmer would choose whatever is appropriate depending on
whether the PO is instantiated from a protected type or directly created with a
single protected declaration.
The caller to the protected operation enclosing 'Set_Ceiling or 'Get_Ceiling
must be executing, at most, at the current ceiling priority of the PO.
Otherwise, Program_Error should be raised to the caller, as is the rule in Ada
95 for accessing a PO (ARM D.5-11). In other words, the ceiling change must
follow the ceiling locking protocol. This approach eliminates the need for an
additional lock on the PO.
The change of the ceiling by means of 'Set_Ceiling does not take place until
the end of the enclosing protected operation.
According to this semantics, a call to 'Get_Ceiling after a call to
'Set_Ceiling within the same protected operation will still return the old
It is a bounded error to lower the ceiling priority while there are tasks
queued on an entry with higher priorities. In this case Program_Error
is raised in the queued tasks, or the queued tasks execute with the lower
ceiling priority when they become unblocked, or both, or neither (c.f. Dynamic
Finally, the new attributes should be optional and explicitly required by means
of a pragma: Adjustable_Ceiling.
In summary, the proposal includes:
- A protected procedure attribute 'Set_Ceiling.
- A protected function attribute 'Get_Ceiling.
- A pragma Adjustable_Ceiling to require support for the two new attributes.
Some simple examples on how to use the proposed features are given in this
section. The section "discussion" provides more elaborated examples in the
context of mode changes, along with the discussion of the rationale for the
proposal and implementation issues.
The new attribute 'Set_Ceiling can be used as follows:
protected type My_Protected is
procedure Set_My_Ceiling(P: in Any_Priority);
protected body My_Protected is
procedure Set_My_Ceiling(P : in Any_Priority) is
PO: My_Protected; --
As can be seen, the name of the type qualifies the call to Set_Ceiling. For POs
of an anonymous type (single protected declarations), the actual name of the PO
would be used as the next example shows:
protected PO is
procedure Set_My_Ceiling(P: in Any_Priority);
protected body PO is
procedure Set_My_Ceiling (P: in Any_Priority) is
In the two examples above, the caller to Set_My_Ceiling must know the name of
the PO: the call would have the form PO.Set_My_Ceiling(P). 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 generic ceiling changer:
type General_Set_Ceiling is access protected procedure (P: in Any_Priority);
Once the access object is properly initialised, the call would take the form:
The examples of use of 'Get_Ceiling would be very similar to those given for
'Set_Ceiling. Nevertheless, 'Get_Ceiling can also be used in a barrier
expression as follows:
entry Wait_Proper_Ceiling when PO'Get_Ceiling < Some_Threshold is
A task queued in Wait_Proper_Ceiling would not gain access to the body of the
entry until the ceiling is adequate, according to the barrier expression.
The need for this functionality and a detailed examination of the many
different ways it could be achieved has been the subject of much
discussion at three 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 adherent to 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 changing
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 calling 'Set_Ceiling -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 will 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 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 access a lower 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 it may produce a large priority inversion: t8 and
other intermediate-priority tasks would be allowed to execute completely before
t5 gains access to the PO again. Moreover, the implementation of ceiling
locking does not require a lock. This solution should be rejected also for the
sake of efficiency.
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 Set_Ceiling conforming to such semantics would be the
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. The approach is therefore rejected.
-- IMPLEMENTATION AS A PROTECTED OPERATION --
The second approach -the one that is advocated in this document- proposes to
implement the ceiling change as a protected operation.
For a given protected object PO, we shall assume the existence of a procedure
Set_Ceiling, implemented as an attribute PO'Set_Ceiling to avoid name clash,
where an "in" parameter of the type System.Any_Priority expresses the new
ceiling priority for PO. This attribute can only be used inside a protected
procedure 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
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
an special operation. It also makes it unnecessary to use a lock on the PO. If
Set_Ceiling is implemented as a protected operation, the priority assignment is
sufficient to guarantee its execution in mutual exclusion with other users of
the protected object.
With respect to tasks queued in protected entries, it could be the case that
the ceiling of the protected object is lowered below the queued tasks' base
priority, which represents a bounded error in Ada. According to the Ada
Reference Manual, section 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 base 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
We are also proposing an attribute Get_Ceiling to read the current PO's
ceiling. Get_Ceiling can be used in any protected operation and it can also be
used in a barrier expression. The interactions between Set_ and Get_Ceiling are
described in the following points:
1.- When using Set_Ceiling, the ceiling change does not take place until
the end of the enclosing protected operation. This means that Get_Ceiling
after Set_Ceiling, in the same protected operation, will still return the
2.- An implementation of protected objects using the proxy model should take
the ceiling change into account. More specifically, it should avoid to execute
protected entries, on behalf of the queued tasks, with the wrong (old)
priority. This can be achieved with the following scheme, where
Current_Ceiling and New_Ceiling represent the ceiling before and after calling
procedure Set_My_Ceiling (P: in System.Any_Priority) is
Current_Ceiling := New_Ceiling;
The setting of the task's priority to the new ceiling will make it to
execute the pending calls with the appropriate active priority, equal to the
3.- An implementation following the self-service model should also take care
to execute the evaluation of barriers at the proper priority. A similar
scheme to the one in point 2 may be used when it is the task leaving
Set_My_Ceiling who evaluates the barriers.
-- A MODE CHANGE EXAMPLE --
The implementation of Set_Ceiling as a protected operation avoids the problems
of inconsistency and large priority inversion introduced by the approach of
implementing dynamic ceilings as a special operation, separated from the
ceiling locking protocol. The main motivation to investigate the case of
changing the ceiling from any priority, even higher than the protected object's
ceiling, was to be able to implement prompt mode changes: a high-priority task
acts as the mode changer, changing periods, deadlines and priorities of tasks
and protected objects before releasing new-mode tasks. A sensible question to
study is the impact of limiting the priority of the task changing the ceiling
on the mode change protocol.
If a single task is to perform all the ceiling changes, then it needs to
proceed in steps, orderly changing the ceilings of the POs that are not in use.
This apparently implies a time delay, since the mode changer must wait for the
PO to be empty before changing the ceiling; but this delay is unavoidable to
consistently change the ceilings in any case.
Two different protocols have been studied to orderly change the ceilings in a
mode change scenario:
- DOC: Decreasing Old-mode Ceilings. The order in which ceilings are
adjusted is determined by the ceiling values in the old mode. The protocol
proceeds from higher to lower ceilings.
- DNC: Decreasing New-mode Ceilings. The protocol proceeds from higher to
lower new-mode ceilings.
DNC allows higher priority new-mode tasks to start executing earlier, as their
PO's are updated sooner. We present now an example system and investigate how
the proposed ceiling change can be executed.
The example system has two operating modes, referred to as "old" "new". We
analyse the transition from "old" to "new". The description of the system is
| active_in_mode | |
task | old | new | uses_PO |
t12 | - | Yes | PO2 | | ceiling |
t10 | Yes | - | PO1 | PO | old | new |
t8 | Yes | Yes | PO2 | --
t6 | Yes | Yes | PO1 & PO2 | PO1 | 10 | 6 |
t5 | - | Yes | PO1 | PO2 | 8 | 12 |
t4 | Yes | - | PO2 |
t3 | Yes | - | PO1 |
The table on the left lists the tasks, their participation in the two modes and
the POs they use. Assume task ti has a priority "i" in the modes it is active.
On the right hand side, we see the ceilings of the two POs in each mode.
According to DNC, the ceiling of PO2 will be changed first and then PO1, since
their ceilings in the new mode are 12 and 6, respectively.
Regarding the mode change protocol, we assume that old-mode tasks are allowed
to complete their execution if they were running when a mode change request
arrives in the system, but they are not released again as old-mode tasks after
the mode change request. The worst case scenario, according to promptness in
the mode change transition, occurs when the mode change request arrives
coinciding with the simultaneous release of all the old-mode tasks. We also
assume tasks do not suspend themselves in any delay or entry queue -with the
exception of a delay until the next activation of periodic tasks.
We add a notional task, the mode_changer, that performs the ceiling changes. To
ensure that there are no tasks executing inside the POs when the ceiling change
takes place, the mode_changer proceeds in steps, lowering its priority to that
of the lowest priority old-mode task that may use a PO. We call this priority
level the "floor priority" of the PO. The following diagram shows the steps of
the DNC algorithm:
|_ _ _
mode_changer |1| |2| |3|
|_| |_| |_|
| | __ |
t12 | | |
| | |__| |
t10 |-| | | |
| __ | __ |
t8 |----| | ---| |
| |__| | |__| |
| __ __
t6 |-------| | | | | |
| |__| |__|
| | | __
t5 | ---| |
| | | |__|
t4 |----------| | |
t3 |---------------------| |
The actions performed by the mode_changer are marked as 1, 2 and 3:
1.- Initially, the mode_changer runs at the highest priority. The mode change
request immediately activates it. The actions to perform are:
Stop releasing old-mode tasks
Release new-mode independent tasks, if any (none in the example)
Set_Priority(Current_Task,4) -- Sets its own priority to the floor of PO2
After these actions, all old-mode tasks with a priority higher or equal
to 4 continue to execute normally, accessing the POs with their old-mode
2.- Now, PO2 is empty. The actions to perform are:
Release t12 and t8
Set_Priority(Current_Task,3) -- Sets its priority to the floor of PO1
After this, t12 and t8 execute and may use PO2 with the correct ceiling
3.- Now t3 has completed and the ceiling of PO1 can be safely set. The mode
changer executes the following actions:
Release t6 and t5
Set_Priority(Current_Task,Highest) -- The mode_changer is ready for the
-- next mode change request
This example sows how to implement a relatively elaborated mode change
protocol. Other protocols can also be implemented, such as the idle-time
protocol. Under the idle-time protocol, upon a mode change request, the mode
changer waits for an idle time to stop releasing the old-mode workload, then it
changes all the ceilings for the new mode, and finally releases
synchronously all the new mode tasks.
-- AN EXAMPLE OF USE OF 'Get_Ceiling IN BARRIERS --
In this section we present an example of use of the protected function
attribute 'Get_Ceiling in a protected entry's barrier. The context of the
example is a simple multi-moded system with the following description:
| active_in_mode | |
task | old | new | uses_PO | | ceiling |
t18 | - | Yes | PO | --
t16 | Yes | - | PO | PO1 | 16 | 18 |
t10 | Yes | Yes | PO |
There exists a single protected object PO.
There is a potential ceiling violation when changing from mode old to new if
t18 started to use PO before the ceiling was adjusted to 18. Besides the
ceiling of ceilings, there exists an offset-based solution to avoid the
potential error. It consists in delaying t18's activation in the new mode until
a point in time when PO's ceiling has been adjusted. The delay must conform the
worst case situation, i.e., the latest point in time when the ceiling can be
changed, considering the worst case phasing of the mode change request arrival.
With the new attributes, a mechanism can be programmed to avoid ceiling
violation without suffering the worst-case delay:
task body t18 is begin
Upon realising the mode change (e.g., by means of ATC), t18 sets its own
priority to 10, i.e., the FLOOR priority of PO in the old mode. (Remember the
floor priority of a protected object is defined as the lowest priority among
the tasks using the PO in a particular mode). This priority assignment makes it
ceiling-safe to call Wait_Proper_Ceiling. Task t18 will be queued until another
task adjusts the ceiling to the new mode's value. The notification of the mode
change in progress includes updating Current_Mode, thus this variable really
refers to the new mode.
Now assume PO offers a family of entries, one per mode. In the protected object
PO, the entry family would be implemented as follows:
entry Wait_Proper_Ceiling(for Mode in Operating_Mode)
when PO'Get_Ceiling = PO_Ceiling(Mode) is
PO_Ceiling is an array, indexed by mode names, that contains the ceiling
priorities of PO in the different operating modes. With this approach, t18 can
immediately be released after the mode change request, since it won't be
removed from the entry queue until the ceiling has been properly set to its
This example is interesting in two senses:
- it provides the desired functionality and
- it avoids delaying T2 for the worst case.
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.
Questions? Ask the ACAA Technical Agent