Version 1.7 of ais/ai-00327.txt

Unformatted version of ais/ai-00327.txt version 1.7
Other versions for file 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
!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 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.
!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
(See wording.)
!wording
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.
Dynamic Semantics
The following attribute of a protected object is defined:
P'Priority: 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 following applies:
- 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.
Metrics
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 begin null; end; procedure Set_Ceiling (Pr : System.Any_Priority) is begin P'Priority := Pr; end;
end P;
Notes 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:
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.
!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'Priority := Pr; -- Code after setting the ceiling -- The new ceiling does not take effect -- until the end of this procedure, but the -- new value is return by any read of 'Priority end Set_My_Ceiling;
-- Rest of bodies
end My_Protected;
PO: My_Protected;
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);
The use of a protected interface could also achieve this functionality.
!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 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 explore it.
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 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 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 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_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 [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