CVS difference for ais/ai-00357.txt

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

--- ais/ai-00357.txt	2003/12/07 05:00:33	1.4
+++ ais/ai-00357.txt	2004/02/21 03:05:36	1.5
@@ -1,4 +1,4 @@
-!standard D.03 (00)                                  03-11-24  AI95-00357/02
+!standard D.03 (00)                                  04-02-19  AI95-00357/03
 !class amendment 03-09-27
 !status work item 03-09-27
 !status received 03-09-27
@@ -9,7 +9,7 @@
 !summary
 
 Direct support for deadlines is defined and a new dispatching policy
-for EDF is provided.
+for EDF is supported.
 
 !problem
 
@@ -23,9 +23,6 @@
 fixed priority scheduling for real-time system. It has the advantage that
 higher levels of resource utilization are possible.
 
-It is important that EDF works with priorities and hence a combined
-scheme via Priority_Specific scheduling is defined.
-
 For many scheduling schemes, including for example EDF, the most effective
 locking policy for protected objects is one known as the Stack Resource
 Policy (or preemption level locking). This was defined
@@ -47,7 +44,7 @@
 current running task S if:
 
 1) Deadline of T is before that of S
-2) Premeption level of T is higher than preemption level of any
+2) Preemption level of T is higher than preemption level of any
 locked PO
 
 If preemption levels are assigned (by the programmer) using
@@ -57,7 +54,7 @@
 
 In this proposal
 
-a) deadlines are represented by a new task attribute
+a) deadlines are represented by a new task 'attribute'
 b) preemption levels for tasks are represented by base priority
 c) preemption levels for POs are represented by ceiling priorities
 
@@ -65,64 +62,34 @@
 are followed. But the active priority of a task when executing outside
 a PO may be lower than its base priority (see details below).
 
-First support for (absolute) deadlines. The following package is provided:
-
-with Ada.Real_Time;
-with Ada.Task_Identification; use Ada.Task_Identification;
-package Ada.Deadline_Support is
-  subtype Deadline is Ada.Real_Time.Time;
-  Default_Deadline : constant Deadline := Ada.Real_Time.Time_Last;
-  Set_Deadline(D : in Deadline; T : in Task_ID := Current_Task);
-  Get_Deadline(D : out Deadline; T : in Task_ID := Current_Task);
-end Ada.Deadline_Support;
-
-with Implementation Advice to hold the deadline value
-as a task attribute.
-
 To enable a task to be assigned a (non-default) deadline to control
 its activation, a new pragma is provided:
-
-pragma Deadline(expression);
-where the expected type of expression is Ada.Real_Time.Time.
 
-This pragma is the only real impact this AI has on the compiler;
-if this pragma is rejected then the Default_Deadline should be
-Ada.Real_Time.Time_First, hence all new tasks would be given a
-very early deadline.
+pragma Relative_Deadline(expression);
+where the expected type of expression is Ada.Real_Time.Time_Span.
 
 The pragma can only occur in the specification part of a task.
 
-A task can change its current deadline by use of Set_Deadline
-and read the current deadline using Get_Deadline.
-
 To support EDF scheduling a new Priority_Policy identifier is
-defined: EDF_Within_Priority. If this policy is in effect then
-the Task_Dispatching_Policy must be Priority_Specific and the
-Locking_Policy must be Ceiling_Locking:
-
-pragma Task_Dispatching_Policy (Priority_Specific);
-pragma Priority_Policy (EDF_Within_Priorities,Lower_Pri,Upper_Pri);
-
-This defines (see AI-355) a band of priorities, Lower_Pri..
-Upper_Pri, that will be used for EDF scheduling.
+defined: EDF_Across_Priorities.
 
-When the Priority policy EDF_Within_Priority is in effect the
+When the Priority policy EDF_Across_Priorities is in effect the
 following rules apply. Let T'Base be the base priority of task T
 and T'Deadline its absolute deadline.
 
 
 Rule 1
-All ready queues in the specified range Lower_Pri..Upper_Pri
+All ready queues in the specified range System.Any_Priority
 are ordered by deadline. For two tasks on the same ready queue,
 S and T: S'Deadline < T'Deadline implies S is closer to the
 head of the queue than T.
 
 Rule 2
 When a task T becomes unblocked it is placed on the highest
-non-empty ready queue R (in range Lower_Pri+1..Upper_Pri) such that
+non-empty ready queue R such that
   T'Deadline < Deadline of task at tail of R, and
   T'Base > Priority level of R.
-if no such R exists then add T to Lower_Pri.
+if no such R exists then add T to Any_Priority'first.
 
 Rule 3
 When a task is chosen for execution it runs with the active priority
@@ -130,37 +97,165 @@
 preempted it returns to the ready queue for its active priority.
 If it inherits a higher active priority it will return to its
 original active priority when it no longer inherits the higher
-level. (NOT SURE IF THIS RULE IS ALREADY IMPLIED)
+level.
 
 Rule 4
 When a task executes a delay_statement that does not result in
 blocking it is added to the ready queue for its active priority.
 
 Rule 5
-When a task has its base priority changed to a value in the range
-Lower_Pri..Upper_Pri it is placed on the ready queue for priority
-Lower_Pri when the change to its base priority takes effect.
+priority ceiling level Priority'first is not allowed.
 
-Rule 6
-Implementation rounds all ceilings at level Lower_Pri to Lower_Pri+1.
+!wording
 
-Words such as the following are needed:
-For multiprocessor implementations other rules may apply.
+D.2.6 Earliest Deadline First Dispatching
 
-!wording
+This clause defines the policy_identifier, EDF_Across_Priorities,
+the pragma Relative_Deadline, and package EDF_Dispatching.
+
+Post-Compilation Rules
 
+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.
 
-!example
+Syntax
 
+The form of a pragma Relative_Deadline is as follows:
 
+pragma Relative_Deadline (relative_deadline_expression);
+
+Name Resolution Rules
+
+The expected type for relative_deadline_expression is
+Ada.Real_Time.Time_Span.
+
+Legality Rules
+
+A Relative_Deadline pragma is allowed only immediately within a
+task_definition. At most one such pragma shall appear within a given
+task_definition.
+
+When EDF_Across_Priorities is in effect no protected object shall have
+ceiling priority System.Any_Priority'first.
+
+Static Semantics
+
+The following language-defined library package exist:
+
+with Ada.Real_Time;
+with Ada.Task_Identification;
+package Ada.Dispatching.EDF_Dispatching is
+  subtype Deadline is Ada.Real_Time.Time;
+  procedure 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 Set_Relative_Deadline(TS : in Ada.Real_Time.Time_Span;
+              T : in Ada.Task_Identification.Task_ID :=
+              Ada.Task_Identification.Current_Task);
+  procedure Delay_and_Set_Relative_Deadline(
+              Delay_Time : in Ada.Real_Time.Time;
+              TS : in Ada.Real_Time.Time_Span);
+  function Get_Deadline(T : in Ada.Task_Identification.Task_ID :=
+              Ada.Task_Identification.Current_Task) return Deadline;
+end Ada.Dispatching.EDF_Dispatching;
+
+
+Dynamic Semantics
+
+The absolute deadline of a task is an indication of the urgency of the task.
+Unless otherwise specified, whenever tasks compete for processors or other
+implementation-defined resources, the resources are allocated to the task with
+the earliest absolute deadline. The initial absolute deadline of a task
+containing pragma Relative_Deadline is the value of Ada.Real_Time.Clock +
+relative_deadline_expression. The call of Ada.Real_Time.Clock being made
+between task creation and the start of its activation. If there is no
+Relative_Deadline pragma then the initial absolute deadline is the value of
+Default_Deadline.
+
+A call of Set_Deadline changes the absolute deadline of the
+task to D. A call of Set_Relative_Deadline changes the absolute
+deadline of the task to Ada.Real_Time.Clock+TS. A call of Get_Deadline
+returns the absolute deadline of the task.
+
+A call of Delay_and_Set_Relative_Deadline delays the calling task until time
+Delay_Time (equivalent to executing delay until Delay_Time). When the
+task becomes runnable again it will have deadline Delay_Time+TS.
+
+When EDF_Across_Priorities is in effect, modifications to the
+ready queues occur only as follows:
+
+o All ready queues are ordered by deadline. The task at the
+  head of a queue is the one with the earliest absolute deadline.
+
+o When a task becomes unblocked it is placed on the highest
+  non-empty ready queue such that the deadline of the task is
+  earlier than that of the task on the tail of the queue, and
+  the base priority of the task is greater than the priority
+  level of the ready queue. If no such ready queue exists the
+  task is added to the ready queue for Any_Priority'first.
+
+o When the setting of the base priority of a running task takes effect,
+  the task is added to the ready queue determined by the above rule.
+
+o When a task is chosen for execution it runs with the active priority
+  determined by the ready queue from which the task was taken. If
+  preempted it returns to the ready queue for its active priority.
+  If it inherits a higher active priority it will return to its
+  original active priority when it no longer inherits the higher
+  level.
+
+o A task dispatching point occurs whenever a task has its deadline
+  changed.
+
+When task dispatching policy EDF_Across_Priorities is in effect a
+task dispatching point occurs for the currently running task of a
+processor whenever there is a non-empty ready queue for that processor
+with a higher priority than the priority of the running task.
+
+For all the operations and types defined in this package, 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.
+
+
+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.
+
+Notes
+
+The above rules implement the preemption-level protocol for resource
+sharing under EDF dispatching (see Baker[1]). 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.
+
+An implementation may support addition dispatching policies by replacing
+absolute deadline with an alternative measure of urgency.
+
+Do we put references in? [Editor's note: No.]
+Reference
+[1] Baker, T.P., Stack-Based Scheduling of Real-Time Processes,
+Journal of Real-Time, Vol 3, No 1, pp67-99, March 1991.
+
 !discussion
 
+The addition of procedure Delay_and_Set_Relative_Deadline reflects
+a common need to change deadline and then delay. For example a periodic
+task would do this. As the change of deadline (extending it) is likely
+to cause a context switch (with a later switch to put the task on
+the delay queue) it is more efficient for the run-time to do the
+delay and deadline change as a single operation.
+
 Here we show that the above rules do give the required behaviour for EDF
 scheduling and preemption level locking (without the need for a new
 locking policy, i.e. just use of ceiling locking).
 
 First if no POs are used or locked then all tasks are always placed on the
-ready queue for level Lower_Pri (which is of course ordered by deadline).
+ready queue for level Prioirity'first (which is of course ordered by deadline).
 
 The preemption level rule is that a newly executing task (T) should
 preempt the current running task (S) if it has a higher preemption
@@ -175,7 +270,7 @@
 same q and will preempt.
 
 If there are a number of locked POs then T needs to be placed on the
-correct ready q. On all ready queues, apart from that at Lower_Pri,
+correct ready q. On all ready queues, apart from that at Priority'first,
 the tail of the q is the task that has the lock on the PO whose
 ceiling pri is that of the ready q. Rule 2 then gets the right q:
 the q is appropriate as T has the correct attributes (shorter
@@ -191,7 +286,7 @@
 --
 
 During discussions an alternative way of expressing this model
-was considered. This did not need the 'no POs at level Lower_Pri'
+was considered. This did not need the 'no POs at level Priority'first'
 rule. But it did required that tasks be placed at one above
 the level in the above model, and required the rule that a
 task preempted while executing in a PO must always stay

Questions? Ask the ACAA Technical Agent