CVS difference for ais/ai-00327.txt

Differences between 1.5 and version 1.6
Log of other versions for file ais/ai-00327.txt

--- ais/ai-00327.txt	2003/09/19 01:42:28	1.5
+++ ais/ai-00327.txt	2003/09/30 02:01:13	1.6
@@ -1,4 +1,4 @@
-!standard D.03 (00)                                    03-08-11  AI95-00327/02
+!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
@@ -9,80 +9,99 @@
 !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.
+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.
 
-With this mechanisms, the ceiling may be changed from a valid priority,
+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 lock to protect the ceiling
-change. An example is 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).
+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 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).
+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
 
-A new attribute of a protected object is defined:
+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;
 
-P'Priority: Yields a variable component of protected object P of
-type System.Any_Priority, which denotes the priority of P. Use of
-this attribute is allowed only inside a protected body.
-
-Note if Locking_Policy Ceiling_Locking is specified then P'Priority
-denotes the ceiling priority of P.
-
-The caller to the protected operation enclosing use of the attribute
-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
-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 priority by means of an assignment to the attribute
-takes place at the end of the enclosing protected action.
-
-According to this semantics, a read of 'Priority after an
-assignment to 'Priority will return the old value.
-
-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)).
+as protected procedures in a protected object PO with no entries.
 
-If Ceiling_Locking is not in effect and no priority has been set
-then the attribute returns an implementation defined value.
-
-A new restriction, No_Dynamic_Ceilings, is introduced and added to the
-Ravenscar Profile.
-
 !wording
 
 
@@ -92,31 +111,275 @@
 section.
 
   protected type My_Protected is
-    pragma Priority(Some_Initial_Value : Any_Priority);
-    procedure Set_My_Ceiling(Pr: in Any_Priority);
+    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 Any_Priority) 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
+      My_Protected'Set_Priority(Pr);
+      -- Code after setting the ceiling.
       -- The new ceiling does not take effect
-      -- until the end of this procedure
+      -- until the end of the protected action
     end Set_My_Ceiling;
 
     -- Rest of bodies
 
   end My_Protected;
+
+  PO: My_Protected; -- Declaration of the PO
 
-  PO: My_Protected; -- Instantiation 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.
 
-Is it necessary for a read of 'Priority (after a write) to
-return the old value?
 
 !ACATS test
 

Questions? Ask the ACAA Technical Agent