CVS difference for ais/ai-00327.txt

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

--- ais/ai-00327.txt	2003/06/06 03:48:10	1.1
+++ ais/ai-00327.txt	2003/06/18 00:12:24	1.2
@@ -8,575 +8,51 @@
 
 !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.
-
--- IAL 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.
-
--- ECTED 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.
-
--- 
-
-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.
-
-
--- t_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?
 
 ****************************************************************

Questions? Ask the ACAA Technical Agent