Version 1.3 of ais/ai-00298.txt

Unformatted version of ais/ai-00298.txt version 1.3
Other versions for file ais/ai-00298.txt

!standard D.8 (00)          02-08-01 AI95-00298/02
!class amendment 02-06-01
!status work item 02-06-01
!status received 02-06-01
!priority Medium
!difficulty Medium
!subject Non-Preemptive Dispatching
!summary
A new dispatching policy is defined for the non-preemptive execution of Ada tasks.
!problem
The Real-Time Annex requires that a preemptive dispatching policy is always provided by an implementation. It also allows implementation-defined policies to be supplied. For many system builders, particularly in the safety-critical area, the policy of choice is non-preemption.
The standard way of implementing many high-integrity applications is with a cyclic executive. Here a sequence of procedures is called within a defined time interval. Each procedure runs to completion, there is no concept of preemption. Data is passed from one procedure to another via shared variables; no synchronization constraints are needed since the procedures never run concurrently.
There is a need for a standard way of obtaining non-preemptive execution for Ada programs whilst still using tasks as a convenient means of encapsulating concurrent entities.
!proposal
A new task dispatching policy is defined, namely Non_Preemptive_FIFO_ Within_Priorities. It uses the existing pragmas thus:
pragma Task_Dispatching_Policy (
Non_Preemptive_FIFO_Within_Priorities);
This policy is optional.
Post-Compilation Rules
If the Non_Preemptive_FIFO_Within_Priorities is specified for a partition then Ceiling_Locking (see D.3) shall also be specified for that partition.
Dynamic Semantics
In accordance with implementation permission D.2.1(9) an additional execution resource, the execution token, is defined.
Each processor has one such execution token.
A ready task must acquire the execution token before it can become the running task. When the Non_Preemptive_FIFO_Within_Priorities policy is in effect the modifications to the ready queues are identical to the existing preemptive policy FIFO_Within_Priorities.
The running task releases the execution token whenever it becomes suspended (or completed). It also releases the execution token whenever it executes a delay statement (whether this results in suspension or not). A new running task is selected and is assigned the execution token whenever the previously running task on that processor becomes suspended or otherwise releases the execution token. The rule for selecting the new running task follows the policy of Fifo_Within_Priorities. On a multiprocessor system there may be further restrictions on where tasks may execute (as covered in D.2.1(15)).
To cover asynchronous task interactions the following rules apply:
o If a task holding an execution token is aborted it releases the
execution token when it completes.
o If a task holding an execution token executes a select-then-abort
construct, and the trigger occurs, then the aborted construct is completed following the rules of D.6 but the token is retained.
o If a task holding an execution token is subject to a priority
change (as a consequence of a call to Set_Priority, D.5) or asynchronous control (as a consequence of a call to Hold, D.11) then it retain the execution token. Note this can only occur in a multiprocessor implementation.
NOTE:
* The running task may release the execution token by issuing a relative
delay with a nonpositive duration or an absolute delay using a time in the past, but be reassigned the token immediately if it is at the head of the highest priority ready queue.
* Implementation Permission 9.5.3 (22) still applies.
* It remains a bounded error to call a potentially blocking operation
from within a protected object.
* A task executing an accept statement on which there is an
outstanding call, proceeds without releasing the execution token (either before or after the execution of the accept statement). Select statements are treated similarly.
* A task calling an entry of a task releases the execution token even
if the entry is open.
* It remains implementation defined, on a multiprocessor, whether a
task waiting for access to a protected agent keeps the processor busy (i.e. retains the execution token), see D.2.1(3).
!wording
New subclause:
D.2.3 A Non-Preemptive Task Dispatching Policy
would include the text above and
Implementation Permission
Since implementations are allowed to round all ceiling priorities in subrange System_Priority to System_Priority'last (see D.3 (14)), an implementation may allow a task to execute within a protected object without raising its active priority provided the protected object does not contain pragma Interrupt_Priority, Interrupt_Handler or Attach_Handler.
!discussion
(a) The above definitions have centered on the notion of a processor and non-preemptive execution on that processor. In Ada terms, however, this is not the complete story. Dispatching policies are set on a per-partition basis and it is possible for an implementation to put more than one partition on a processor. The standard is silent about multi-partition scheduling, and there is clearly more than one way to schedule such a system, for example:
o use `priority' across all partitions on the same processor;
o assign overriding priorities to each partition;
o use priority dispatching within a partition and time-slicing
between partitions.
The notion of `non-preemption' is different in all three cases. But as Ada only allows the dispatching policy within a partition to be defined, no further refinement of the language model can be given. It would be possible for an implementation to have an execution token per processor or per partition.
(b) The implementation permission is valid as Tasking_Error cannot be raised if all ceiling are rounded to the 'last value. However this is only a permission, not a requirement and hence is weaker than the earlier proposal.
(c) The use of an execution token, rather than a new policy, is required as Annex D assumes preemptive execution. D.2.2, the dispatching policy builds on the priority scheduling model D.2.1. This model clearly states that "processor are preemptible resources" (D.2.1 (7)), and "the task dispatching model specifies preemptive scheduling" (D.2.1 (1)).
To make all of D.2.1 'A model' (rather than 'The model') would undermine Annex D. Preemption is implicit in a number of places, e.g. D.6 (5), D.5 (14), D.9 (12), D.9 (13) and D.1 (15). The introduction of an execution token leaves the processor as a preemptive resource and does seem to be the appropriate method as allowed by D.2.1 (9).
Although not covered in this AI, it would be possible to define a policy that allowed the coexistence of preemptive and non-preemptive tasks by a relatively simple change to the rules defined above for the execution token; a completely new scheduling model would not be necessary.
As a final point, the approach taken in this AI could easily be used to define a non-interruptible policy (based on a different token).
!examples
!ACATS Test
ACATS test(s) need to be created.
!appendix

!standard D.8
!class amendment
!status
!priority -- IRTAW11 consider this to be medium
!difficulty
!subject Non-Preemptive Dispatching
!from A. Burns on behalf of IRTAW11


! summary

A new dispatching policy and locking policy are defined for the
non-preemptive execution of Ada tasks.


! problem

The Real-Time Annex requires that a preemptive dispatching policy is
always provided by an implementation. It also allows implementation-defined
policies to be supplied. For many system builders, particularly in
the safety-critical area, the policy of choice is non-preemption.

The standard way of implementing many high-integrity applications is
with a cyclic executive.  Here a sequence of procedures is called
within a defined time interval.  Each procedure runs to completion,
there is no concept of preemption.  Data is passed from one procedure
to another via shared variables; no synchronization constraints are
needed since the procedures never run concurrently.

There is a need for a standard way of obtaining non-preemptive execution
for Ada programs whilst still using tasks as a convenient means of
encapsulating concurrent entities.


! proposal

Two new policy identifiers are defined, namely Non_Preemptive_FIFO_
Within_Priorities and Non_Preemptive_Locking. These are task dispatching
policies and locking policies respectively and are used with the existing
pragmas thus:

pragma Task_Dispatching_Policy (
	Non_Preemptive_FIFO_Within_Priorities);

pragma Locking_Policy (Non_Preemptive_Locking);

These policies are optional.

Post-Compilation Rules

If the Non_Preemptive_Locking policy is specified for a partition then
Non_Preemptive_FIFO_Within_Priorities shall also be specified for that
partition.

Dynamic Semantics

In accordance with implementation permission D.2.1(9) an additional
execution resource, the execution token, is defined.

Each processor has one such execution token.

A ready task must acquire the execution token before it can become the
running task.  When the Non_Preemptive_FIFO_Within_Priorities policy is
in effect the modifications to the ready queues are identical to the
existing preemptive policy FIFO_Within_Priorities.

The running task releases the execution token whenever it becomes suspended
(or completed). It also releases the execution token whenever it
executes a delay statement (whether this results in suspension or not).
A new running task is selected and is assigned the execution token whenever
the previously running task on that processor becomes suspended or otherwise
releases the execution token. The rule for selecting the new
running task follows the policy of Fifo_Within_Priorities.
On a multiprocessor system there may be further restrictions on
where tasks may execute (as covered in D.2.1(15)).

To cover asynchronous task interactions the following rules apply:

o If a task holding an execution token is aborted it releases the
  execution token when it completes.

o If a task holding an execution token executes a select-then-abort
  construct, and the trigger occurs, then the aborted construct is
  completed following the rules of D.6 but the token is retained.

o If a task holding an execution token is subject to a priority
  change (as a consequence of a call to Set_Priority, D.5) or asynchronous
  control (as a consequence of a call to Hold, D.11) then it retain
  the execution token. Note this can only occur in a multiprocessor
  implementation.

The locking policy, Non_Preemptive_Locking is defined as follows:

- if the protected object contains any of the following three pragmas:
  Interrupt_Priority, Interrupt_Handler or Attach_Handler then the rules
  defined for locking policy Ceiling_Locking apply;

- if none of the above pragmas are present then, on a single processor,
  no run-time code need be generated to protect the object, in particular
  the priority of the calling task need not be changed;

- pragma Priority must not be present in any protected object (an
  alternative would be to say that pragma Priority has no effect).

NOTE:

* The running task may release the execution token by issuing a relative
  delay with a nonpositive duration or an absolute delay using a time in
  the past, but be reassigned the token immediately if it is at the head
  of the highest priority ready queue.

* Implementation Permission 9.5.3 (22) still applies.

* It remains a bounded error to call a potentially blocking operation
  from within a protected object.

* A task executing an accept statement on which there is an
  outstanding call, proceeds without releasing the execution
  token (either before or after the execution of the accept statement).
  Select statements are treated similarly.

* A task calling an entry of a task releases the execution token even
  if the entry is open.

* It remains implementation defined, on a multiprocessor, whether a
  task waiting for access to a protected agent keeps the processor
  busy (i.e. retains the execution token), see D.2.1(3).



! discussion

The above definitions have centered on the notion of a processor and
non-preemptive execution on that processor. In Ada terms, however, this is
not the complete story. Dispatching policies are set on a per-partition
basis and it is possible for an implementation to put more than one
partition on a processor. The standard is silent about multi-partition
scheduling, and there is clearly more than one way to schedule such a
system, for example:

o use `priority' across all partitions on the same processor;

o assign overriding priorities to each partition;

o use priority dispatching within a partition and time-slicing
  between partitions.

The notion of `non-preemption' is different in all three cases. But as
Ada only allows the dispatching policy within a partition to be defined,
no further refinement of the language model can be given. It would
be possible for an implementation to have an execution token per processor
or per partition.


! examples

! appendix

Full motivation and justification for the details of this proposal
are contained in: A. Burns, Defining New Non-Preemptive Dispatching
and Locking Policies for Ada, Proceedings of Reliable Software
Technologies - Ada Europe 2001, LNCS, pp328-336, 2001.

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


Questions? Ask the ACAA Technical Agent