CVS difference for ai12s/ai12-0230-1.txt

Differences between 1.2 and version 1.3
Log of other versions for file ai12s/ai12-0230-1.txt

--- ai12s/ai12-0230-1.txt	2017/06/10 04:24:23	1.2
+++ ai12s/ai12-0230-1.txt	2018/05/11 05:33:05	1.3
@@ -1,4 +1,4 @@
-!standard D.2.6(9/2)                                  17-06-05  AI12-0230-1/01
+!standard D.2.6(9/2)                                  18-05-01  AI12-0230-1/02
 !standard D.2.6(9.1/3)
 !standard D.2.6(29/2)
 !standard D.3(4)
@@ -20,6 +20,9 @@
 [Editor's note: Numbers in square brackets here represent references, which can
 be found at the end of the !discussion section.]
 
+This new version of the AI reflects extensive discussion on the previous AI at
+the 19th IRTAW which took place in April 2018.
+
 Ada currently supports EDF scheduling and Protected Object (PO) sharing via an
 implementation of the Stack Resource Protocol (SRP). At the 2013 and 2015 IRTAW
 Workshops [4,5] it was accepted that the Deadline Floor Protocol (DFP) [1,2,3]
@@ -28,8 +31,9 @@
 deprecated.
 
 For Ravenscar-like tasks with no self-suspension there is a static relationship
-between a task's relative and absolute deadlines. For general tasks the notion
-of a minimum relative deadline is needed to enforce the rules for DFP.
+between a task's relative and absolute deadlines. For such task it would be
+advantageous if the run-time automatically updates the absolute deadline of
+the task when it becomes ready for execution (i.e. runnable).
 
 !proposal
 
@@ -41,7 +45,7 @@
 
 Under the DFP, every protected object has a relative deadline equal to the
 shortest relative deadline of any task that uses it. The relative deadline of a
-protected object is called its deadline floor. All tasks also have a minimum
+protected object is called its deadline floor. All tasks also have a
 relative deadline (which will usually be static, just as a task has a base
 priority that is usually fixed).
 
@@ -66,18 +70,38 @@
 are well behaved (e.g. do not self-suspend while executing within a PO, and have
 the correct relationship between relative deadline and absolute deadline).
 However, due to the common use of multiprocessors, and the requirements for
-resilience, a lightweight mutex lock is proposed for DFP (this was the
-recommendation from the discussion at the last IRTAW [5]).
-
-With restricted tasks that conform to the Ravenscar Profile, and which do not
-self-suspend, the Minimum_Relative_Deadline would be identical to the usual
-Relative_Deadline parameter. But for tasks that do self-suspend a distinct
-aspect would be beneficial.
+resilience, a lightweight mutex lock was proposed for DFP (this was the
+recommendation from the discussion at the 2016 IRTAW [5]; during discussion
+at the last (2018) IRTAW an alternative check was proposed, this is included
+in the discussion below).
+
+There two styles of programming that can be applied to EDF-based 
+scheduled systems. In one (which fits with hard real-time systems and
+hence Ravenscar) each task has a relative deadline and every time it is made
+runnable the run-time system can assign a new absolute deadline.
+The relative deadline aspect will usually be constant, but to
+program mode changes an application should be allowed to change it.
+With the second programming style (which fits more with soft real-time)
+tasks directly update their own absolute deadlines; there is less use
+of the notion of relative deadline although the minimum relative deadline
+will be needed to fix each protected object's floor value.
+Both styles of programming are supported by the proposals in this AI,
+hence both absolute and relative deadline need to be represented.
+
+With the first style the run-time check (on entry to a protected object, PO)
+could be simply that the task's relative deadline should not be less than
+the PO's floor. However to accommodate the more flexible programming style
+it is necessary to check that the relative deadline currently in effect is
+not less than the PO's floor. This leads to the run-time check being:
+the task's current absolute deadline minus its last release time (i.e. the time
+it last became runnable) must not be less that the PO's floor. This therefore
+requires that the run-time keeps track of the last time each task becomes
+runnable. No lock is required (on a single processor).
 
 To embed the rules for the DFP within Ada, the following issues must be
 addressed:
 
-1) All tasks must have a minimum relative deadline assigned via an aspect or a
+1) All tasks have a minimum relative deadline assigned via an aspect or a
    routine defined in a library package.
 
 2) Protected objects must have also a relative deadline (floor) assigned via an
@@ -86,59 +110,69 @@
 3) Default relative deadline values must be defined for tasks and protected
    objects (and their types).
 
-4) Rules for EDF scheduling must be extended to include a new locking policy:
-   Deadline_Floor_Locking (“Floor_Locking” by itself could be confusing).
+4) Rules for EDF scheduling must be changed to include a new locking policy:
+   Deadline_Floor_Locking (or just Floor_Locking); however as Floor_Locking
+   will always be used in conjunction with Ceiling_Locking it may be better
+   to define the rules for Floor_Locking as part of Ceiling_Locking.
 
-5) Rules for EDF scheduling need simplifying to remove the ‘across priorities’
+5) Rules for EDF scheduling need simplifying to remove the 'across priorities'
    feature of the current definition.
+
+6) A configuration pragma (Generate_Deadlines?) is defined that requires each
+   task's absolute deadline to be computed by the run-time each time the task
+   becomes runnable.
 
-6) For completeness (and parity with priority ceilings) means of modifying the
+7) For completeness (and parity with priority ceilings) means of modifying the
    relative deadline attribute of tasks and protected objects should be defined.
 
+8) Rules for rendezvous and activation need to be set.
+
 Each of these topics will now be covered.
 
 1)
-The easiest way to introduce minimum relative deadlines to tasks is via the
-addition of new items to Ada.Dispatching.EDF:
+The easiest way to introduce relative deadlines to tasks is via the
+addition of new items to Ada.Dispatching.EDF which would now become:
 
 with Ada.Real_Time;
 with Ada.Task_Identification;
 package Ada.Dispatching.EDF is
-  .....
+  subtype Deadline is Ada.Real_Time.Time;
   subtype Relative_Deadline is Real_Time.Time_Span;
-  Default_Minimum_Relative_Deadline : constant
+  Default_Relative_Deadline : constant
       Relative_Deadline :=
       Real_Time.Time_Span_Last;
-  procedure Set_Minimum_Relative_Deadline
-     (D : in Relative_Deadline;
+  procedure Set_Deadline (D : in Deadline;
+      T : in Ada.Task_Identification.Task_Id :=
+      Ada.Task_Identification.Current_Task);
+  function Get_Deadline (T : Ada.Task_Identification.Task_Id :=
+      Ada.Task_Identification.Current_Task) return Deadline;
+  procedure Set_Relative_Deadline
+      (D : in Relative_Deadline;
       T : in Ada.Task_Identification.Task_Id :=
       Ada.Task_Identification.Current_Task);
-  function Get_Minimum_Relative_Deadline (T :
+  function Get_Relative_Deadline (T :
       Ada.Task_Identification.Task_Id :=
       Ada.Task_Identification.Current_Task)
       return Relative_Deadline;
+  procedure Delay_Until_And_Set_Deadline (
+      Delay_Until_Time : in Ada.Real_Time.Time;
+      Deadline_Offset : in Ada.Real_Time.Time_Span :=
+      Get_Relative_Deadline);
+  function Get_Last_Release_Time(T :
+      Ada.Task_Identification.Task_Id :=
+      Ada.Task_Identification.Current_Task)
+      return Ada.Real_Time;
 end Ada.Dispatching.EDF;
 
-In would make sense for the existing subprogram, Delay_Until_And_Set_Deadline,
-to be modified to take the task's Minimum_Relative_Deadline aspect as the
-default value of Deadline_Offset.
-
-A simple means of delaying a sporadic task on an entry and have its absolute
-deadline assigned when the task is next released will be necessary.
-
 2)
 Each PO needs a Deadline_Floor attribute that can be set on the creation of a PO
 by an aspect. The Relative_Deadline aspect already exists, so can be reused to
 set the deadline floors. This is identical to the way that the priority aspect
 is used both for task priority and PO ceiling priority.
+
+3) For each PO:
 
-3)
-Default_Deadline : constant Deadline :=
-  Real_Time.Time_Last; -- already defined
-Default_Minimum_Relative_Deadline : constant
-  Relative_Deadline :=
-  Real_Time.Time_Span_Last;
-Default_Deadline_Floor : constant Relative_Deadline :=
+Default_Floor : constant Relative_Deadline :=
   Real_Time.Time_Span_Zero;
 
 4) and 5)
@@ -154,11 +188,6 @@
 policy. And to accommodate hierarchical dispatching the new policy is defined as
 EDF_Within_Priorities.
 
-Wording is not yet attempted as agreement in principle is needed and a number of
-other issues need to be considered such as whether deadline inheritance should
-occur during a rendezvous and task activation, and whether entry queues can be
-deadline ordered.
-
 With EDF_Within_Priorities, all tasks with the same priority compete for the
 processor using the rules for EDF dispatching. The ready queue is ordered by
 active deadline. A collection of EDF dispatched tasks and the set of protected
@@ -166,29 +195,27 @@
 But they will have different relative deadlines (and deadline floors).
 
 A task that has not been given an explicit deadline or relative deadline will
-get the default values of Default_Deadline and
-Default_Minimum_Relative_Deadline. The default value for the deadline floor of
-any protected object is 0 (actually Time_Span_Zero). This will have the effect
-of making all protected actions non-preemptive, as does the default priority
-ceiling (unless tasks are released with deadlines in the past).
+get the default values of Default_Deadline and Default_Relative_Deadline. 
+The default value for the deadline floor of any protected object is 0 
+(actually Time_Span_Zero). This will have the effect of making all protected 
+actions non-preemptive, as does the default priority ceiling (unless tasks are
+released with deadlines in the past).
 
 Locking policies are applied to a whole partition using the Locking_Policy
 pragma. The ARM defines the single policy Ceiling_Locking. As deadline floor
-locking is orthogonal to ceiling locking, the two could be used together (in
-hierarchical scheduling where there is both fixed priority and EDF dispatching).
-Indeed the definition of Ceiling_Locking could be expanded to include the rules
-for the deadline floor protocol. However, to make the definition of the new
-protocol clearer a new locking policy is defined: Deadline_Floor_Locking. But
-note that Ceiling_Locking and Deadline_Floor_Locking can be used together (and
-may need a new locking policy that is both ceiling and floor locking — see
-!discussion).
+locking is orthogonal to ceiling locking, the two could and indeed will be used
+together (in hierarchical scheduling where there is both fixed priority (or
+interrupt handling) and EDF dispatching). Indeed the definition of
+Ceiling_Locking could be expanded to include the rules for the deadline floor
+protocol - this is the approach taken in !wording. Alternatively the two
+policies (and a third which is them combined) could be defined.
 
 Just as a task has a base and active priority, with EDF_Within_Priorities and
-Deadline_Floor_Locking a task has an active (absolute) deadline and a base
-(absolute) deadline. The dispatcher uses active deadline to determine execution
-order.
+Floor_Locking a task has an active (absolute) deadline and a base (absolute)
+deadline. The dispatcher uses active deadline to determine execution order.
 
-The rules for EDF_Within_Priorities with Deadline_Floor_Locking are as follows:
+In the context of the use of protected objects the rules for
+EDF_Within_Priorities with Floor_Locking are as follows:
 
 o Whenever a task is executing outside a protected action, its active deadline
   is equal to its base deadline.
@@ -198,30 +225,235 @@
   corresponding protected object; 'now' is obtained via use of the real-time
   clock (i.e. the clock that supports the Ada.Real_Time library package).
 
-o When calling a protected entry or procedure a lock is obtained on the
-  associated protected object.
-
 o When a task completes a protected action its active deadline returns to the
-  value it had on entry, and the lock is released.
+  value it had on entry.
 
 o When a task calls a protected operation, a check is made that (absolute
   deadline - release time) of the task is not less than the deadline floor of
-  the object. On a uniprocessor the lock should also be available. Program_Error
-  is raised if this check fails.
-
-With this definition of a new locking policy, the definition of Ceiling_Locking
-can return to its pre-2005 wording.
+  the object.
 
 6)
+Requires a configuration pragma, Generate_Deadlines, that will cause the
+deadline of a task, whenever it is made runnable, to be set to 'now'
+(as defined above) plus the task's current Relative_Deadline. A task is
+still allowed to directly change its absolute deadline. When Generate_Deadlines
+is applied, a periodic task will not need to use Delay_Until_And_Set_Deadline.
+A sporadic task released from an entry or suspension object will also have its
+deadline automatically set on release. A Ravenscar-EDF profile might wish to
+mandate Generate_Deadlines and prevent the use of Set_Deadline and
+Delay_Until_And_Set_Deadline.
+
+7)
 In the same way that a protected object can contain code to change its ceiling
 priority - to take effect when the calling task exits the protected object, it
 can have its deadline floor updated by an assignment to the Relative_Deadline
-attribute. A task can also change its minimum relative deadline.
+attribute.
 
+8)
+A rendezvous between two tasks should take place at the higher priority of
+the two tasks and the shorter deadline. A task's activation should take
+place at the deadline of the task responsible for creating the new task.
 
+
 !wording
 
+The existing D.2.6 should be replaced by the following.
+
+D.2.6 Earliest Deadline First Dispatching
+
+The deadline of a task is an indication of the urgency of the task;
+it represents a point on an ideal physical time line. The deadline might
+affect how resources are allocated to the task. This subclause defines
+a package for representing the deadline of a task and a dispatching
+policy that defines Earliest Deadline First (EDF) dispatching.
+An aspect is defined to assign an initial deadline to a task.
+A configuration pragma is defined that requires the run-time to
+compute each task's deadline whenever it is made runnable.
 
+Static Semantics
+The policy_identifier EDF_Within_Priorities is a task dispatching policy.
+
+The following language-defined library package exists:
+
+with Ada.Real_Time;
+with Ada.Task_Identification;
+package Ada.Dispatching.EDF is
+  subtype Deadline is Ada.Real_Time.Time;
+  subtype Relative_Deadline is Real_Time.Time_Span;
+  Default_Deadline : constant Deadline :=
+      Ada.Real_Time.Time_Last;
+  Default_Relative_Deadline : constant
+      Relative_Deadline :=
+      Real_Time.Time_Span_Last;
+  procedure Set_Deadline (D : in Deadline;
+      T : in Ada.Task_Identification.Task_Id :=
+      Ada.Task_Identification.Current_Task);
+  function Get_Deadline (T : Ada.Task_Identification.Task_Id :=
+      Ada.Task_Identification.Current_Task) return Deadline;
+  procedure Set_Relative_Deadline
+      (D : in Relative_Deadline;
+      T : in Ada.Task_Identification.Task_Id :=
+      Ada.Task_Identification.Current_Task);
+  function Get_Relative_Deadline (T :
+      Ada.Task_Identification.Task_Id :=
+      Ada.Task_Identification.Current_Task)
+      return Relative_Deadline;
+  procedure Delay_Until_And_Set_Deadline (
+      Delay_Until_Time : in Ada.Real_Time.Time;
+      Deadline_Offset : in Ada.Real_Time.Time_Span :=
+      Get_Relative_Deadline);
+  function Get_Last_Release_Time (T :
+      Ada.Task_Identification.Task_Id :=
+      Ada.Task_Identification.Current_Task)
+      return Ada.Real_Time;
+end Ada.Dispatching.EDF;
+
+For a task type (including the anonymous type of a single_task_declaration)
+or subprogram, the following language-defined representation aspect may
+be specified:
+
+Relative_Deadline
+The aspect Relative_Deadline is an expression, which shall be of type
+Real_Time.Time_Span.
+
+The form of pragma Generate_Deadlines is as follows:
+pragma Generate_Deadlines
+
+Legality Rules
+The Relative_Deadline aspect shall not be specified on a task interface type.
+
+Post-Compilation Rules
+If the EDF_Within_Priorities policy is specified for a partition, then the
+Ceiling_Locking policy (see D.3) shall also be specified for the partition.
+
+If the EDF_Within_Priorities policy appears in a Priority_Specific_Dispatching
+pragma (see D.2.2) in a partition, then the Ceiling_Locking policy (see D.3)
+shall also be specified for the partition.
+
+The Generate_Deadlines pragma is a configuration pragma.
+
+
+Dynamic Semantics
+The Relative_Deadline aspect has no effect if it is specified for a subprogram
+other than the main subprogram.
+
+If pragma Generate_Deadlines is in effect an implementation is required to 
+update a task's deadline every time it becomes runnable.
+The new deadline is the value of Real_Time.Clock at the time the task is
+added to a ready queue plus the value of Get_Relative_Deadline.
+
+The initial absolute deadline of a task for which aspect Relative_Deadline is
+specified is the value of Real_Time.Clock + the expression that is the value
+of the aspect, where this entire expression, including the call of
+Real_Time.Clock, is evaluated between task creation and the start of its
+activation. If the aspect Relative_Deadline is not specified, then the initial
+absolute deadline of a task is the value of Default_Deadline. The environment
+task is also given an initial deadline by this rule, using the value of
+the Relative_Deadline aspect of the main subprogram (if any).
+
+The procedure Set_Deadline changes the base deadline of the task to D.
+The function Get_Deadline returns the base deadline of the task.
+
+The procedure Set_Relative_Deadline changes the relative deadline of the
+task to D. The function Get_Deadline returns the relative deadline of the task.
+
+The function Get_Last_Release_Time returns the time, as provided by
+Real_Time.Clock, when the task was last made runnable (i.e. added to a
+ready queue).
+
+The procedure Delay_Until_And_Set_Deadline delays the calling task until
+time Delay_Until_Time. When the task becomes runnable again it will have
+deadline Delay_Until_Time + Deadline_Offset.
+
+On a system with a single processor, the setting of the deadline of a task
+to the new value occurs immediately at the first point that is outside the
+execution of a protected action. If the task is currently on a ready queue it
+is removed and re-entered on to the ready queue determined by the rules
+defined below.
+
+When EDF_Within_Priorities is specified for a priority, the ready queue is
+ordered by deadline. The task at the head of a queue is the one with the
+earliest deadline.
+
+A task dispatching point occurs for the currently running task T to which
+policy EDF_Within_Priorities applies:
+o  when a change to the base deadline of T occurs;
+o  there is a nonempty ready queue for that processor with a higher priority
+than the active priority of the running task.
+o  there is a runnable task with the same priority as T but with an earlier
+deadline.
+
+In these cases, the currently running task is said to be preempted and is
+returned to the ready queue for its active priority, at a position determined
+by its active deadline.
+
+When the setting of the base priority of a ready task takes effect and the new
+priority is specified as EDF_Within_Priorities, the task is added to the ready
+queue, at a position determined by its active deadline.
+
+For all the operations defined in Dispatching.EDF, Tasking_Error is raised if
+the task identified by T has terminated. Program_Error is raised if the value
+of T is Null_Task_Id.
+
+If two tasks with priority designated as EDF_Within_Priorities rendezvous then
+the deadline for the execution of the accept statement shall be the earlier of
+the two tasks' deadlines.
+
+During activation a task being activated inherits the deadline that its
+activator (see 9.2) had at the time the activation was initiated.
+
+Bounded (Run-Time) Errors
+
+Erroneous Execution
+If a value of Task_Id is passed as a parameter to any of the subprograms of this
+package and the corresponding task object no longer exists, the execution of the
+program is erroneous.
+
+Documentation Requirements
+On a multiprocessor, the implementation shall document any conditions that cause
+the completion of the setting of the deadline of a task to be delayed later than
+what is specified for a single processor.
+
+NOTES
+18 If two distinct priorities are specified to have policy
+EDF_Within_Priorities, then task from the higher priority always run before
+tasks of the lower priority, regardless of deadlines.
+
+------------
+
+The following addition is required to D.3 Priority Ceiling Locking.
+
+Under Dynamic Semantics:
+
+If the ceiling priority of a protected object designates one with
+EDF_Within_Priorities, the following additional rules apply.
+
+Every protected object has a relative deadline, which is determined by a
+Relative_Deadline aspect as defined in D.2.6, or by assignment to the
+Relative_Deadline attribute as described in D.5.2. The relative deadline of a
+protected object is a lower bound on the relative deadline a task can have when
+it calls protected operations of that protected object.
+
+If aspect Relative_Deadline is not specified for a protected type then the
+initial Relative_Deadline of the corresponding protected object is
+Ada.Real_Time.Time_Span_Zero.
+
+While a task executes a protected action, it inherits the Relative_Deadline
+of the corresponding protected object so that its active deadline is reduced
+to (if it is currently greater then) 'now' plus the deadline floor of
+the corresponding protected object; 'now' is obtained via use of
+Real_Time.Clock.
+
+When a task calls a protected operation, a check is made that its active
+deadline minus its last release time is not less than Relative_Deadline
+of the corresponding protected object; Program_Error is raised if this check fails.
+
+---------
+
+D.5.2 needs to be changed to allow assignments to a PO's Relative_Deadline
+aspect (perhaps via a Relative-Deadline attribute).
+
+
 !discussion
 
 Much discussion concerning the Deadline Floor protocol can be found in the
@@ -408,5 +640,17 @@
 part. If IRTAW doesn't know what should happen, how the heck are načve ARG
 members such as myself supposed to figure it out? Sounds like the blind leading
 the deaf or something like that. :-)
+
+****************************************************************
+
+From: Alan Burns
+Sent: Tuesday, May 1, 2018  7:25 AM
+
+Following the latest IRTAW workshop (last month) we have produced a new 
+version of the AI which is attached. [This is version /02 of the AI - Editor.]
+An initial attempt at !wording has been made. There are some differences to
+the details of what was in the previous version of this AI.
+
+I understand that this AI is still 'in scope' for inclusion in Ada 2002X.
 
 ****************************************************************

Questions? Ask the ACAA Technical Agent