Version 1.9 of ai12s/ai12-0230-1.txt

Unformatted version of ai12s/ai12-0230-1.txt version 1.9
Other versions for file ai12s/ai12-0230-1.txt

!standard D.2.6(2/2)          19-04-02 AI12-0230-1/06
!standard D.2.6(7/2)
!standard D.2.6(9/2)
!standard D.2.6(9.1/3)
!standard D.2.6(9.2/3)
!standard D.2.6(9.3/3)
!standard D.2.6(10/2)
!standard D.2.6(11/2)
!standard D.2.6(12/3)
!standard D.2.6(13/3)
!standard D.2.6(14/2)
!standard D.2.6(15/2)
!standard D.2.6(16/2)
!standard D.2.6(17/2)
!standard D.2.6(18/2)
!standard D.2.6(19/2)
!standard D.2.6(20/2)
!standard D.2.6(21/2)
!standard D.2.6(22/2)
!standard D.2.6(23/2)
!standard D.2.6(24/2)
!standard D.2.6(25/2)
!standard D.2.6(26/2)
!standard D.2.6(27/2)
!standard D.2.6(28/2)
!standard D.2.6(29/2)
!standard D.2.6(30/2)
!standard D.2.6(33/3)
!standard D.2.6(34/2)
!standard D.3(13)
!standard D.5.2(2/2)
!standard D.5.2(3/2)
!standard D.5.2(4/2)
!class Amendment 17-06-05
!status Amendment 1-2012 18-11-27
!status ARG Approved 7-0-3 18-10-22
!status work item 17-06-05
!status received 17-05-02
!priority Low
!difficulty Medium
!subject Deadline Floor Protocol
!summary
A mechanism is proposed to allow tasks, dispatched according to the rules of EDF (Earliest Deadline First), to control their access to shared protected objects via the use of the Deadline Floor protocol.
!problem
[Author'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] has many advantages over the SRP and that it should be incorporated into a future version of the language, and that ideally the support for SRP should be deprecated.
For Ravenscar-like tasks with no self-suspension there is a static relationship between a task's relative and absolute deadlines. For such a task it would be advantageous if the run-time automatically updates the absolute deadline of the task when it becomes ready for execution (that is, runnable).
!proposal
The DFP has all the key properties of SRP; specifically, causing at most a single blocking effect from any task with a longer relative deadline, which leads to the same worst-case blocking in both protocols. However, DFP is conceptually more straightforward, is easier to implement, and has less run-time overheads [2,3,6].
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 relative deadline (which will usually be static, just as a task has a base priority that is usually fixed).
The key idea of the DFP is that the absolute deadline (as used for EDF scheduling) of a task can be temporarily shortened while accessing a protected object. Given a task with absolute deadline d that accesses a resource with deadline floor DF at time t, the absolute deadline of the task is (potentially) reduced according to d := min(d, t+DF) while holding the resource.
The action of the protocol on a single processor with tasks that do not self-suspend results in a single block per task, deadlock free execution and the protocol works for nested calls on protected objects (PO). While a task accesses a PO, its deadline is reduced so that no newly released tasks can preempt it and then access the PO. See [1,2,3] for details and proof of the key properties. This is equivalent to the use of a priority ceiling; again, the only tasks that can preempt a task executing within a protected object are tasks that are guaranteed not to use that object (unless there is a program error, which can be caught at run-time).
As with the priority ceiling protocol, an actual lock is not strictly required to provide mutual exclusion for POs when a single processor is used and tasks 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 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 are 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 ready 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 (that is, the time it last became ready) 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 ready. 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 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
aspect.
3) Default relative deadline values must be defined for tasks and protected
objects (and their types).
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'
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 ready.
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 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_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;
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:
Default_Floor : constant Relative_Deadline := Real_Time.Time_Span_Zero;
4) and 5) Currently, EDF dispatching is supported via the policy EDF_Across_Priorities. A range of priorities is needed to account for the different priority ceilings needed for the protected objects. The tasks themselves only execute at the base priority of this range when they are not executing within a protected action. All ready queues are ordered by the (absolute) deadline of the ready tasks.
To prevent confusion, and to emphasize the fact that with the new protocol only a single priority is needed for all EDF dispatched tasks (regardless of the number of protected objects they use), it is proposed to have a new dispatching policy. And to accommodate hierarchical dispatching the new policy is defined as EDF_Within_Priorities.
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 objects they use/share will all have the same priority (and ceiling priority). 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_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 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 Floor_Locking a task has an active (absolute) deadline and a base (absolute) deadline. The dispatcher uses active deadline to determine execution order.
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.
o When a task executes a protected action, its active deadline will be reduced
to (if it is currently greater than) 'now' plus the deadline floor of the 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 a task completes a protected action, its active deadline returns to the
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.
6) Requires a configuration pragma, Generate_Deadlines, that will cause the deadline of a task, whenever it is made ready, 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.
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.
[Redundant: This subclause presents Ada.Dispatching.EDF, a package for representing the deadline of a task and a dispatching policy that defines Earliest Deadline First (EDF) dispatching. The Relative_Deadline aspect is provided to assign an initial deadline to a task. A configuration pragma Generate_Deadlines is provided to specify that a task's deadline is recomputed whenever it is made ready.]
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.Time; end Ada.Dispatching.EDF;
For a subprogram, a task type (including the anonymous type of a single_task_declaration), or a protected type (including the anonymous type of a single_protected_declaration), 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;
The Generate_Deadlines pragma is a configuration pragma.
Legality Rules
The Relative_Deadline aspect shall not be specified on a task or protected interface type. If the Relative_Deadline aspect is specified for a subprogram, the aspect_definition shall be a static expression.
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.
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, the deadline of a task is recomputed each time it becomes ready. The new deadline is the value of Real_Time.Clock at the time the task is added to a ready queue plus the value returned by Get_Relative_Deadline.
The initial absolute deadline for a task with a specified Relative_Deadline is the result of adding the value returned by a call of Real_Time.Clock to the value of the expression specified as the Relative_Deadline aspect, where this entire computation, including the call of Real_Time.Clock, is performed 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 (Ada.Real_Time.Time_Last). 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 effect of specifying a Relative_Deadline aspect for a protected type or single_protected_declaration is discussed in D.3.
A task has both an /active/ and a /base/ absolute deadline. These are the same except when the task is inheriting a relative deadline during activation or a rendezvous (see below) or within a protected action (see D.3). The procedure Set_Deadline changes the (base) absolute deadline of the task to D. The function Get_Deadline returns the (base) absolute deadline of the task.
The procedure Set_Relative_Deadline changes the relative deadline of the task to D. The function Get_Relative_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 ready (that is, was 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 ready again it will have deadline [code font: 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 onto the ready queue determined by the rules defined below.
When EDF_Within_Priorities is specified for a priority, the ready queue for that priority 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:
* when a change to the base (absolute) deadline of T occurs;
* there is a nonempty ready queue for that processor with a higher priority than the active priority of the running task;
* there is a ready task with the same priority as T but with an earlier absolute 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 (absolute) 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 is the earlier of the deadlines of the two tasks.
During activation, a task being activated inherits the deadline that its activator (see 9.2) had at the time the activation was initiated.
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 tasks from the higher priority always run before tasks of the lower priority, regardless of deadlines.
------------
Additional text is needed in D.3 Priority Ceiling Locking.
Add after D.3(13) (in 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 represents a lower bound on the relative deadline a task may have when it calls a protected operation 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 than) 'now' plus the deadline floor of the corresponding protected object; 'now' is obtained via a call on Ada.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 the relative deadline of the corresponding protected object; Program_Error is raised if this check fails.
---------
D.5.2 is changed to allow assignments to a PO's Relative_Deadline aspect, as follows:
Modify D.5.2(2/2): The following attribute{s are} [is] defined for a prefix P that denotes a protected object:
Add after D.5.2(3/2):
P'Relative_Deadline
Denotes a non-aliased component of the protected object P. This component is of type Ada.Real_Time.Time_Span and its value is the relative deadline of P. P'Relative_Deadline denotes a variable if and only if P denotes a variable. A reference to this attribute shall appear only within the body of P.
Modify D.5.2(4/2) The initial value of [this] {the} attribute {Priority} is {determined by} the initial value of the priority of the protected object{ (see D.3)}, and can be changed by an assignment. {The initial value of the attribute Relative_Deadline is determined by the initial value of the relative deadline of the protected object (see D.3).}
!discussion
Much discussion concerning the Deadline Floor protocol can be found in the references [1,2,3].
One of the advantages of the new EDF_Within_Priorities policy is that it unifies Ada's use of priority as the primary dispatching policy. It is no longer necessary to reserve a range of priorities for a single EDF domain. If we ignore the non-preemptive policy, we now have a clear means of supporting mixed scheduling in a hierarchical manner:
o At all times, the task at the head of the highest priority non-empty ready
queue is the one chosen to be executed.
o Each ready queue has its own discipline to determine which task is at its
head.
The disciplines supported are: FIFO, Round Robin (RR) and now EDF; i.e. FIFO_Within_Priorities, Round_Robin_Within_Priorities, and EDF_Within_Priorities.
Tasks with different priorities and different dispatching policies can share access to protected objects by a combination of Ceiling_Locking and Deadline_Floor_Locking. When a task enters such a PO its active priority is raised to the ceiling value and its active deadline is reduced to the floor value.
References
[1] A. Burns, A Deadline-Floor Inheritance Protocol for EDF Scheduled Real-Time Systems with Resource Sharing, Department of Computer Science, University of York, YCS-2012-476, 2012.
[2] A. Burns, M. Gutierrez, M. Aldea and M. Gonzalez Harbour, A Deadline-Floor Inheritance Protocol for EDF Scheduled Embedded Real-Time Systems with Resource Sharing, IEEE Transactions on Computers, 64(5), 1241-1253, 2015.
[3] M. Aldea, A. Burns, M. Gutierrez and M. Gonzalez Harbour, Incorporating the Deadline Floor Protocol in Ada, ACM SIGAda Ada Letters, Proc. of IRTAW 16, XXXIII(2),49-58, 2013.
[4] A.J. Wellings, Session Summary: Locking protocols, ACM SIGAda Ada Letters, Proc IRTAW 16, XXXIII(2): pp 123-125, 2013.
[5] A.J. Wellings, Session Summary: Deadline floor protocol, Ada User Journal, IRTAW 18, 37(3), 169-170, 2016.
[6] H. Almatary, N.C. Audsley and A. Burns, Reducing the Implementation Overheads of IPCP and DFP, Proceeding of IEEE Real-Time Systems Symposium, 2015.
!corrigendum D.2.6(2/2)
Replace the paragraph:
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.
by:
This subclause presents Dispatching.EDF, a package for representing the deadline of a task and a dispatching policy that defines Earliest Deadline First (EDF) dispatching. The Relative_Deadline aspect is provided to assign an initial deadline to a task. A configuration pragma Generate_Deadlines is provided to specify that a task's deadline is recomputed whenever it is made ready.
!corrigendum D.2.6(7/2)
Replace the paragraph:
The policy_identifier EDF_Across_Priorities is a task dispatching policy.
by:
The policy_identifier EDF_Within_Priorities is a task dispatching policy.
!corrigendum D.2.6(9/2)
Replace the paragraph:
with Ada.Real_Time; with Ada.Task_Identification; package Ada.Dispatching.EDF is subtype Deadline is Ada.Real_Time.Time; Default_Deadline : constant Deadline := Ada.Real_Time.Time_Last; procedure Set_Deadline (D : in Deadline; T : in Ada.Task_Identification.Task_Id := Ada.Task_Identification.Current_Task); procedure Delay_Until_And_Set_Deadline ( Delay_Until_Time : in Ada.Real_Time.Time; Deadline_Offset : in Ada.Real_Time.Time_Span); function Get_Deadline (T : Ada.Task_Identification.Task_Id := Ada.Task_Identification.Current_Task) return Deadline; end Ada.Dispatching.EDF;
by:
with Ada.Real_Time; with Ada.Task_Identification; package Ada.Dispatching.EDF with Nonblocking is subtype Deadline is Ada.Real_Time.Time; subtype Relative_Deadline is Ada.Real_Time.Time_Span; Default_Deadline : constant Deadline := Ada.Real_Time.Time_Last; Default_Relative_Deadline : constant Relative_Deadline := Ada.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) with Nonblocking => False; function Get_Last_Release_Time (T : Ada.Task_Identification.Task_Id := Ada.Task_Identification.Current_Task) return Ada.Real_Time.Time; end Ada.Dispatching.EDF;
!corrigendum D.2.6(9.1/3)
Replace the paragraph:
For a task type (including the anonymous type of a single_task_declaration) or subprogram), the following language-defined representation aspect may be specified:
by:
For a subprogram, a task type (including the anonymous type of a single_task_declaration), or a protected type (including the anonymous type of a single_protected_declaration), the following language-defined representation aspect may be specified:
!corrigendum D.2.6(9.2/3)
Insert after the paragraph:
Relative_Deadline
The aspect Relative_Deadline is an expression, which shall be of type Real_Time.Time_Span.
the new paragraphs:
The form of pragma Generate_Deadlines is as follows:
pragma Generate_Deadlines;
The Generate_Deadlines pragma is a configuration pragma.
!corrigendum D.2.6(9.3/3)
Replace the paragraph:
The Relative_Deadline aspect shall not be specified on a task interface type.
by:
The Relative_Deadline aspect shall not be specified on a task or protected interface type. If the Relative_Deadline aspect is specified for a subprogram, the aspect_definition shall be a static expression.
!corrigendum D.2.6(10/2)
Replace the paragraph:
If the EDF_Across_Priorities policy is specified for a partition, then the Ceiling_Locking policy (see D.3) shall also be specified for the partition.
by:
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.
!corrigendum D.2.6(11/2)
Replace the paragraph:
If the EDF_Across_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.
by:
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.
!corrigendum D.2.6(12/3)
Insert after the paragraph:
The Relative_Deadline aspect has no effect if it is specified for a subprogram other than the main subprogram.
the new paragraph:
If pragma Generate_Deadlines is in effect, the deadline of a task is recomputed each time it becomes ready. The new deadline is the value of Real_Time.Clock at the time the task is added to a ready queue plus the value returned by Get_Relative_Deadline.
!corrigendum D.2.6(13/3)
Replace the paragraph:
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).
by:
The initial absolute deadline for a task with a specified Relative_Deadline is the result of adding the value returned by a call of Real_Time.Clock to the value of the expression specified as the Relative_Deadline aspect, where this entire computation, including the call of Real_Time.Clock, is performed 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 (Ada.Real_Time.Time_Last). 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 effect of specifying a Relative_Deadline aspect for a protected type or single_protected_declaration is discussed in D.3.
!corrigendum D.2.6(14/2)
Replace the paragraph:
The procedure Set_Deadline changes the absolute deadline of the task to D. The function Get_Deadline returns the absolute deadline of the task.
by:
A task has both an active and a base absolute deadline. These are the same except when the task is inheriting a relative deadline during activation or a rendezvous (see below) or within a protected action (see D.3). The procedure Set_Deadline changes the (base) absolute deadline of the task to D. The function Get_Deadline returns the (base) absolute deadline of the task.
The procedure Set_Relative_Deadline changes the relative deadline of the task to D. The function Get_Relative_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 ready (that is, was added to a ready queue).
!corrigendum D.2.6(15/2)
Replace the paragraph:
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.
by:
The procedure Delay_Until_And_Set_Deadline delays the calling task until time Delay_Until_Time. When the task becomes ready again it will have deadline Delay_Until_Time + Deadline_Offset.
!corrigendum D.2.6(16/2)
Replace the paragraph:
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.
by:
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 onto the ready queue determined by the rules defined below.
!corrigendum D.2.6(17/2)
Replace the paragraph:
When EDF_Across_Priorities is specified for priority range Low..High all ready queues in this range are ordered by deadline. The task at the head of a queue is the one with the earliest deadline.
by:
When EDF_Within_Priorities is specified for a priority, the ready queue for that priority is ordered by deadline. The task at the head of a queue is the one with the earliest deadline.
!corrigendum D.2.6(18/2)
Replace the paragraph:
A task dispatching point occurs for the currently running task T to which policy EDF_Across_Priorities applies:
by:
A task dispatching point occurs for the currently running task T to which policy EDF_Within_Priorities applies:
!corrigendum D.2.6(19/2)
Replace the paragraph:
by:
!corrigendum D.2.6(20/2)
Delete the paragraph:
!corrigendum D.2.6(21/2)
Replace the paragraph:
by:
!corrigendum D.2.6(22/2)
Replace the paragraph:
In these cases, the currently running task is said to be preempted and is returned to the ready queue for its active priority.
by:
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 (absolute) deadline.
!corrigendum D.2.6(23/2)
Delete the paragraph:
For a task T to which policy EDF_Across_Priorities applies, the base priority is not a source of priority inheritance; the active priority when first activated or while it is blocked is defined as the maximum of the following:
!corrigendum D.2.6(24/2)
Delete the paragraph:
!corrigendum D.2.6(25/2)
Delete the paragraph:
!corrigendum D.2.6(26/2)
Delete the paragraph:
!corrigendum D.2.6(27/2)
Delete the paragraph:
When a task T is first activated or becomes unblocked, it is added to the ready queue corresponding to this active priority. Until it becomes blocked again, the active priority of T remains no less than this value; it will exceed this value only while it is inheriting a higher priority.
!corrigendum D.2.6(28/2)
Replace the paragraph:
When the setting of the base priority of a ready task takes effect and the new priority is in a range specified as EDF_Across_Priorities, the task is added to the ready queue corresponding to its new active priority, as determined above.
by:
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.
!corrigendum D.2.6(29/2)
Insert after the paragraph:
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.
the new paragraphs:
If two tasks with priority designated as EDF_Within_Priorities rendezvous then the deadline for the execution of the accept statement is the earlier of the deadlines of the two tasks.
During activation, a task being activated inherits the deadline that its activator (see 9.2) had at the time the activation was initiated.
!corrigendum D.2.6(30/2)
Delete the paragraph:
If EDF_Across_Priorities is specified for priority range Low..High, it is a bounded error to declare a protected object with ceiling priority Low or to assign the value Low to attribute 'Priority. In either case either Program_Error is raised or the ceiling of the protected object is assigned the value Low+1.
!corrigendum D.2.6(33/3)
Replace the paragraph:
18 If two adjacent priority ranges, A..B and B+1..C are specified to have policy EDF_Across_Priorities then this is not equivalent to this policy being specified for the single range, A..C.
by:
18 If two distinct priorities are specified to have policy EDF_Within_Priorities, then tasks from the higher priority always run before tasks of the lower priority, regardless of deadlines.
!corrigendum D.2.6(34/2)
Delete the paragraph:
19 The above rules implement the preemption-level protocol (also called Stack Resource Policy protocol) for resource sharing under EDF dispatching. The preemption-level for a task is denoted by its base priority. The definition of a ceiling preemption-level for a protected object follows the existing rules for ceiling locking.
!corrigendum D.3(13)
Insert after the paragraph:
the new paragraphs:
If the ceiling priority of a protected object designates one with EDF_Within_Priorities, the following additional rules apply:
!corrigendum D.5.2(2/2)
Replace the paragraph:
The following attribute is defined for a prefix P that denotes a protected object:
by:
The following attributes are defined for a prefix P that denotes a protected object:
!corrigendum D.5.2(3/2)
Insert after the paragraph:
P'Priority
Denotes a non-aliased component of the protected object P. This component is of type System.Any_Priority and its value is the priority of P. P'Priority denotes a variable if and only if P denotes a variable. A reference to this attribute shall appear only within the body of P.
the new paragraph:
P'Relative_Deadline
Denotes a non-aliased component of the protected object P. This component is of type Ada.Real_Time.Time_Span and its value is the relative deadline of P. P'Relative_Deadline denotes a variable if and only if P denotes a variable. A reference to this attribute shall appear only within the body of P.
!corrigendum D.5.2(4/2)
Replace the paragraph:
The initial value of this attribute is the initial value of the priority of the protected object, and can be changed by an assignment.
by:
The initial value of the attribute Priority is determined by the initial value of the priority of the protected object (see D.3), and can be changed by an assignment. The initial value of the attribute Relative_Deadline is determined by the initial value of the relative deadline of the protected object (see D.3), and can be changed by an assignment.
!example
** TBD.
!ASIS
[Not sure. It seems like some new capabilities might be needed to support the new aspects and attributes, but I didn't check - Editor.]
!ACATS test
ACATS C-Tests are needed to check that the new capabilities are supported.
!appendix

From: Alan Burns
Sent: Tuesday, May 2, 2017  4:59 AM

The attached AI [this is version /01 of the AI - Editor] comes from prolonged
consideration by the real-time folk on support for EDF scheduling; in particular
the issue of sharing protected object effectively. A new protocol, the
Deadline-Floor Protocol (DFP), has been developed that is consider to be better
than the Stack Resource Protocol (SRP) on which Ada is based.

The attached AI starts the process of moving DFP into Ada (and removing SRP).

I am sure there will be comments!

I assume Randy will give this a number etc.
Looking forward to dicussions

****************************************************************

From: Erhard Ploedereder
Sent: Thursday, June 1, 2017  10:25 AM

> But for tasks that do self-suspend a distinct aspect would be
> beneficial.

The AI says/claims this, but does not explain what this benefit for tasks that
self-suspend actually is. And yet, this seems to be crucial for the merits of
the proposal, since my cursory reading so far created the impression that rather
than talking (higher) ceiling priority, we are now reading (lower) deadline
floor, and as one is the inverse of the other, nothing really has changed except
words of explanation.

So what is this benefit that warrants the change?

****************************************************************

From: Alan Burns
Sent: Friday, June 2, 2017  2:30 AM

Get back to next week

****************************************************************

From: Alan Burns
Sent: Monday, June 5, 2017  3:02 AM

There are really no benefits of tasks that self-suspend. All real-time
abstractions for tasks assume that they do not self suspend. Hence the abstract
definition of the deadline-floor protocol assumes that they do not.

However, as you know, programmers can do what they wish, so for programs that
have tasks that do self-suspend the protocol has to be resilient.

So the point of the Deadline-floor protocol is to give a much easier to
understand and efficient means for real-time tasks dispatched via EDF to share
access to protected objects. Self-suspension is not really an issue (just needs
to be covered in the definition).

****************************************************************

From: Randy Brukardt
Sent: Monday, June 5, 2017  8:17 PM

> The attached AI comes from prolonged consideration ...

A few thoughts on the AI noted upon skimming it while filing it:

(1) The AI states "... and that ideally the support for SRP should be
deprecated."

But the rest of the AI is written as if the support for SRP will be completely
removed. "Deprecation" in Ada means "moving to Annex J"; we almost never remove
anything.

We might be able to make an exception in this case (since I don't know of any
implementations that actually support EDF, so there is no possibility of
breaking existing code by removing the previous version -- but that has to be
verified, not just asserted by someone).

In any case, the AI seems to go beyond the IRTAW recommendation (which certainly
does not suggest removal). Has the IRTAW position changed (in which case the AI
should say that)? Or is this just the author going beyond the recommendation??
Surely it matters whether obsolescence or removal is proposed, and the AI needs
to be crystal-clear on which is proposed and needs a very strong justification
for removal if that is the recommendation.

(2) There's no such thing as a !reference section. These !thingys are intended
(and used) by various automated tools; one does not get to create new ones
without involving the editor and ARG (because the number of tools that would
need updates). I put the references at the end of the !discussion section and
added a note to point out that they're there.

I'll also note that AIs are not papers! Since there are no URLs associated with
the references, there's no useful way to refer to them. So if I, for instance,
wanted to read about the justification for these changes, it would be impossible
(in my case, I do have the Ada Letters issue somewhere, but one can hardly
assume that). In such a case, one would hope that more of the justification
would make it into the AI proper. (Nothing wrong with referencing something
outside for details, but it seems wrong to give no idea at all.)

(3) The proposal seems to be adding another locking policy. In such a case,
you'll have to explain how that policy works with all of the other existing
protocols (since one specifies locking policy and dispatching policy
separately). Moreover, that's critical if one wants to support mixed EDF and
FIFO policies via Priority_Specific_Dispatching -- since locking policies are
partition-wide. (Unless you want to define Priority_Specific_Locking!!)

(4) "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."

The first part is fine at this stage, but I don't understand the "other issues"
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.

****************************************************************

From: Tucker Taft
Sent: Wednesday, October 17, 2018  1:04 PM

Here is an update to the Deadline Floor Protocol AI initially produced by Alan
Burns.  Mostly I just made a number of editorial corrections, plus  I finished
up the edits to D.5.2 to include protected types into the proposal.

[This is version /03 of the AI - Editor.]

****************************************************************

From: Randy Brukardt
Sent: Wednesday, October 17, 2018  6:22 PM

A few typos here: some extra spaces after periods (when is that not true in a
Tucker AI?), "rendesvous", a few paragraphs that ran very long needed to be
broken up.

---

>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.

Isn't "shall" usually used for Legality Rules? This is a Dynamic Semantics rule.
This probably should just say "is" rather than "shall be". (Isn't that usually
your comment? :-)

---

>The following addition is required to D.3 Priority Ceiling Locking.
>
>Under Dynamic Semantics:

We need an exact place, of course. So I replaced the above with:

Add after D.3(13) (in Dynamic Semantics):

****************************************************************

From: Tucker Taft
Sent: Wednesday, October 17, 2018  7:38 PM

Thanks again for the corrections.  I agree with all of them.

****************************************************************

From: Randy Brukardt
Sent: Monday, April 1, 2019  10:30 PM

Jean-Pierre Rosen asked in his RM review:

> D.2.6 This clause uses the term "runnable" (which is undefined) 
> instead of "ready". Or did I miss something?

I verified that "runnable" only occurs in D.2.6 in the entire AARM. This text 
should not use "runnable".

Is J-P right that it should be replaced by "ready" consistently, or is it more 
subtle than that??

Aside: J-P also asks about D.2.6(16):

  ... it is removed and re-entered on [to ]the ready queue ...

I agree with J-P that "on to" is weird, it should either be "onto" or just 
"on". Which is it??
End Aside.

****************************************************************

From: Tucker Taft
Sent: Monday, April 1, 2019  11:16 PM

...
> Is J-P right that it should be replaced by "ready" consistently, or is 
> it more subtle than that??

"Ready" is probably correct.

...
> Aside: J-P also asks about D.2.6(16):
> 
>  ... it is removed and re-entered on [to ]the ready queue ...
> 
> I agree with J-P that "on to" is weird, it should either be "onto" or 
> just "on". Which is it??

"It is removed from and then re-entered onto the ready queue ..." would make
the most sense to me.

****************************************************************

From: Tullio Vardanega
Sent: Tuesday, April 2, 2019  2:36 AM

Yes, "runnable" should be replaced by "ready".

****************************************************************

From: Alan Burns
Sent: Tuesday, April 2, 2019  2:51 AM

I agree - ready

****************************************************************

From: Randy Brukardt
Sent: Tuesday, April 2, 2019  8:30 PM

...
> > Is J-P right that it should be replaced by "ready" consistently, or is 
> > it more subtle than that??
> 
> "Ready" is probably correct.

Since everyone agrees on this, and to save a *lot* of time (there are a bunch 
of uses of "runable"), I'm processing this as an editorial correction to the 
AI.

So we won't see this one on a meeting agenda; if someone wants to object, 
they need to speak up.

****************************************************************

From: Jeff Cousins
Sent: Wednesday, April 3, 2019  6:32 AM

“there are a bunch of uses of "runnable"”

Previously Randy said “I verified that "runnable" only occurs in D.2.6 in the 
entire AARM”

So do I take it that the bunch are all within D.2.6?

****************************************************************

From: Randy Brukardt
Sent: Wednesday, April 3, 2019  2:57 PM

Yes, they're all in D.2.6; I found 4 occurrences ultimately (one in old text, 
the rest in the new text).

****************************************************************

From: Brad Moore
Sent: Wednesday, April 3, 2019  10:16 PM

>> Aside: J-P also asks about D.2.6(16):
>> 
>>  ... it is removed and re-entered on [to ]the ready queue ...
>> 
>> I agree with J-P that "on to" is weird, it should either be "onto" or 
>> just "on". Which is it??
>> End Aside:
> 
> "It is removed from and then re-entered onto the ready queue ..." 
> would make the most sense to me.

Shouldn't that be "into" rather than "onto"?

When I go to the bank, I enter into the queue, not onto it.

At least that's the usage I'm familiar with.

****************************************************************

From: Richard Wai
Sent: Wednesday, April 3, 2019  10:49 PM

Maybe this is one of the animate/inanimate cases - You're in the queue, but
that's on the queue... 

For me anyways, "Entered into the queue" feels less right than "Entered onto
the queue". 

****************************************************************

From: Tucker Taft
Sent: Wednesday, April 3, 2019  11:52 PM

Either is fine with me. "Onto" seems a bit more appropriate when talking about 
inanimate objects.

****************************************************************

From: Brad Moore
Sent: Thursday, April 4, 2019  10:00 AM

> Either is fine with me. "Onto" seems a bit more appropriate when 
> talking about inanimate objects.

I think it has more to do with one's mental model of a queue. If its a 
horizontal queue, like a pipe, then items get placed into the queue, and
flow to the other end.

If its a vertical queue, like a stack of papers on the printer, or perhaps 
a consumable queue like a conveyor belt, where one physically places items 
onto (on top) of the queue, then onto works better.

e.g. I am sending my tax return into the queue to be processed. (An inanimate 
     object example)
     The rescuers queued everyone onto ladder (An animate object onto example) 

     I find it difficult to come up with vertical queue examples, I think they 
     may be much less prevalent, which may be why when I search for "onto the 
     queue" in Google, Google tries to correct me by asking, "Did you mean 
     into the queue?"

Anyway, this is a minor nit. I'm happy to let Randy apply whichever he feels 
is more appropriate.

****************************************************************

From: Randy Brukardt
Sent: Thursday, April 4, 2019  8:39 PM

> Anyway, this is a minor nit. I'm happy to let Randy apply whichever he 
> feels is more appropriate.

Considering that I applied these changes two days ago, and that I rather gave 
my opinion in the original question, not to mention that everyone else seemed 
to think "onto" sounds better, it should be obvious what I'm going to do.

****************************************************************

Questions? Ask the ACAA Technical Agent