CVS difference for ais/ai-00327.txt

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

--- ais/ai-00327.txt	2003/06/18 00:12:24	1.2
+++ ais/ai-00327.txt	2003/06/28 02:53:57	1.3
@@ -8,51 +8,577 @@
 
 !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: John Barnes
-Sent: Thursday, June 5, 2003  1:16 AM
-
-At the last meeting I mentioned that one of the generic
-packages did not have preinstantiated equivalents. I
-promised to tell you which one.
-
-It is Text_IO.Complex_IO.
-
-The name is unhelpful. It ought to be
-Text_IO.Generic_Complex_IO so that Text_IO.Complex_IO would
-be the preinstantiated version with type Float (or strictly
-with Complex_Types which itself is based on type Float).
-
-
-
-Pascal suggests the following solution:
 
-"The name is consistent with the packages nested in Text_IO, e.g.,
-Ada.Text_IO.Integer_IO.  Maybe those names were poorly chosen, and we
-should blame Jean, but it's water under the bridge at this point.
+From: Alan Burns
+Sent: Thursday, June 5, 2003  5:02 AM
 
-I think we should do the same thing as was done for Integer_IO.  In this
-case the non-generic equivalents are named Ada.Integer_Text_IO,
-Ada.Long_Integer_Text_IO, etc.  So I am proposing to add a
-Ada.Complex_Text_IO, Ada.Long_Complex_Text_IO, etc."
+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.
 
-Any comments?
+[Editor's note: This is version /01 of the AI.]
 
 ****************************************************************

Questions? Ask the ACAA Technical Agent