Version 1.1 of ais/ai-00327.txt

Unformatted version of ais/ai-00327.txt version 1.1
Other versions for file 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
!priority Medium
!difficulty Medium
!subject Dynamic Ceiling Priorities
!summary
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.
!problem
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).
!proposal
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 ceiling priority.
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 Priorities D.5(11)).
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.
!wording
!example
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 pragma Adjustable_Ceiling; procedure Set_My_Ceiling(P: in Any_Priority); -- other protected procedures, functions and/or entries end My_Protected;
protected body My_Protected is procedure Set_My_Ceiling(P : in Any_Priority) is begin -- Code before setting the ceiling My_Protected'Set_Ceiling(P); -- <<<<< Use of 'Set_Ceiling -- Code after setting the ceiling -- The new ceiling does not take effect until the end of this procedure end Set_My_Ceiling;
-- Rest of bodies
end My_Protected;
PO: My_Protected; -- Instantiation of the PO
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 pragma Adjustable_Ceiling; procedure Set_My_Ceiling(P: in Any_Priority); -- other protected operations end PO;
protected body PO is procedure Set_My_Ceiling (P: in Any_Priority) is begin -- Code before setting the ceiling PO'Set_Ceiling(P); -- <<<<< Use of 'Set_Ceiling -- Code after setting the ceiling -- The new ceiling does not take effect until the end of this procedure end Set_My_Ceiling;
-- Rest of bodies
end PO;
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); Ceiling_Changing_Procedure: General_Set_Ceiling;
Once the access object is properly initialised, the call would take the form:
Ceiling_Changing_Procedure(P)
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 begin ... end Wait_Proper_Ceiling;
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.
!discussion
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 explore it.
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 protected object.
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 ceilings.
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
|__|_| action
^ PO half 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 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. 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 sense.
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 old ceiling.
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 Set_My_Ceiling, respectively:
procedure Set_My_Ceiling (P: in System.Any_Priority) is begin ... PO'Set_Ceiling(P); -- Just assigns New_Ceiling ... -- Added by the compiler: Current_Ceiling := New_Ceiling; Set_Priority(Current_Task,Current_Ceiling); end Set_My_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 new ceiling.
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 the following:
| 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 change
Request
^ |_ _ _
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 ceilings.
2.- Now, PO2 is empty. The actions to perform are:
PO2'Set_Ceiling(12) 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:
PO1'Set_Ceiling(6) 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 | ------------------------------------ PO | old | new | 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 -- some code Set_Priority(10); PO.Wait_Proper_Ceiling(Current_Mode); -- some more code end t18;
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 begin -- some code, e.g., setting the caller's -- priority to the new-mode value end Wait_Proper_Ceiling;
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 new-mode value.
This example is interesting in two senses:
- it provides the desired functionality and - it avoids delaying T2 for the worst case.
!ACATS test
!appendix

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