Version 1.6 of ais/ai-00327.txt

Unformatted version of ais/ai-00327.txt version 1.6
Other versions for file ais/ai-00327.txt

!standard D.03 (00)          03-09-21 AI95-00327/03
!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) can be dynamically changed by execution of a predefined procedure attribute. The execution of this procedure is only allowed immediately within a protected procedure or protected entry.
A similar mechanism, in the form of a read-only attribute, is proposed to read the current ceiling of a PO. The execution of this attribute is only allowed immediately within any protected operation of the PO.
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.
!problem
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.
!proposal
Two new attributes of a protected type or protected object P are defined. In the case of a protected type, the attributes apply to the current instance of the type.
P'Priority: Yields the ceiling priority of the protected object P, or the current instance of the protected type P. The returned value is of type System.Any_Priority. The attribute may only be used immediately within a protected operation of P, excluding within any entry barrier expression.
P'Set_Priority(X): This attribute is a procedure. It may only be called immediately within the body of a protected procedure or entry. The type of the parameter X is System.Any_Priority. The effect of the call to P'Set_Priority is to amend the ceiling priority of the enclosing protected object (or current instance of the enclosing protected type) to X, at completion of the protected action in which it is executed.
If a task is blocked on a protected entry call, and the call is queued, it is a bounded error to lower the ceiling priority of the corresponding protected object below the active priority of the blocked task. In this case Program_Error is raised in the queued caller, or its priority is temporarily lowered, or both, or neither (this is similar wording to that in D.5(11) for Dynamic Priorities).
According to these rules, a read of P'Priority after a call to P'Set_Priority within the same protected action will return the old ceiling priority. In addition, queued tasks that are serviced as part of the same protected action as the one that changes the priority, will execute with the old ceiling priority.
The new attributes are only permitted if Ceiling_Locking locking policy is in effect for the active partition.
A new identifier for pragma Restrictions, No_Dynamic_Ceilings, is introduced to provide user control over the legality of these attributes, i.e. the use of these attributes is not allowed if No_Dynamic_Ceilings applies to the active partition. This restriction is to be added to the definition of pragma Profile (Ravenscar).
A new metric needs to be defined to document the cost of a call to P'Set_Priority, ie, the difference in time between calls to:
procedure Set_My_Ceiling (Pr : System.Any_Priority) is begin null; end;
and
procedure Set_My_Ceiling (Pr : System.Any_Priority) is begin PO’Set_Priority(Pr); end;
as protected procedures in a protected object PO with no entries.
!wording
!example
A simple example on how to use the proposed features is given in this section.
protected type My_Protected is pragma Priority(Some_Initial_Value); procedure Set_My_Ceiling(Pr: in System.Any_Priority); -- other protected procedures, functions and/or entries end My_Protected;
protected body My_Protected is procedure Set_My_Ceiling(Pr : in System.Any_Priority) is begin -- Code before setting the ceiling My_Protected'Set_Priority(Pr); -- Code after setting the ceiling. -- The new ceiling does not take effect -- until the end of the protected action end Set_My_Ceiling;
-- Rest of bodies
end My_Protected;
PO: My_Protected; -- Declaration of the PO
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); Ceiling_Changing_Procedure: General_Set_Ceiling;
Once the access object is properly initialised, the call would take the form:
Ceiling_Changing_Procedure(P);
!discussion
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 and P'Set_Priority appears to be the easiest way of achieving the required functionality. Allowing assignment to an implicit component called P'Priority (e.g. P'Priority := Pr;) would be an anomalous use of Ada attributes. One other possibility would be to define a pre-defined procedure called Set_Priority, as in the case of dynamic task priorities, but this would need PO IDs.
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. At the end of this section, the reasons for not allowing 'Priority in entry barriers are explained.
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 explore it.
Three cases can be identified with respect to the relative priorities of tasks executing a protected operation, the task calling 'Set_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 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 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 Set_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 document- 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_Priority, implemented as an attribute PO'Set_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. Note that we suggest that both attributes can be used only immediately within the protected bodies for consistency with other attributes such as E'Caller.
Accordingly, a task calling Set_Priority 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_Priority 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 sense.
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_Priority 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.
-- ABOUT THE USE OF 'Priority IN BARRIERS --
In principle, the proposal considered the possibility to use the attribute 'Priority in barrier expressions, to be able to wait until the ceiling priority of a PO was equal to a certain value. For instance, in the mode change scenario, a new-mode task could wait until the ceiling priority of a PO has been adjusted to the new-mode ceiling by providing an entry with a barrier to check this. It could be done by means of a PO entry as in the following example:
entry Wait_Proper_Ceiling when PO'Priority = PO_Ceiling(Mode) is begin -- some code end Wait_Proper_Ceiling;
Looking at this example in detail, it shows a poor programming style that may lead to having Program_Error raised very easily: just asking what the current ceiling is may be erroneous, since this call must follow Ceiling_Locking. With this mechanism, a task with a relatively high priority cannot wait for the ceiling to be raised without causing a ceiling violation.
Note also that the use of 'Priority in a barrier in conjunction with the eggshell model and the proxy model (which causes the ceiling change to be deferred until the end of the protected action in which 'Set_Priority is invoked) causes any tasks that remain on closed barriers, not to be released as part of the same protected action. If this was permitted, it could give rise to surprising results, in that the task will be released potentially much later than expected. The following example illustrates this issue:
-- initial priority is 12 entry X (...) when My_PO'Priority = 10 ...
procedure P (...) is begin
... My_PO'Set_Priority (10); --> this will take effect in the order:
-- Service_Entries(...); -- Service pending entry calls -- Adjust_Ceiling(...); -- Perform the actual ceiling change
...
end P;
hence the task queued on X will NOT be released just after the execution of P, but at the next occasion the barrier will be evaluated.
Therefore we propose that the use of 'Priority in a barrier expression should be rejected and the user should use a more precise form of expression to control the release of such a task.
Paper [1] 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 [2].
References: -----------
[1] 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.
[2] 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.
!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.

[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
the feature).

****************************************************************

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

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:

Thanks

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

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

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