Version 1.5 of ais/ai-00307.txt
!standard D.14 (01) 03-07-02 AI95-00307/04
!class amendment 02-08-28
!status Amendment 200Y 03-07-02
!status ARG Approved 12-0-1 03-06-20
!status work item 02-08-28
!status received 02-08-28
!subject Execution-Time Clocks
Modern real-time scheduling policies require that applications have
the ability to measure execution time of tasks, and to detect
execution time overruns. Two mechanisms were proposed to achieve these
requirements. One was based on a library-level package, and the other
one was integrated into the Ada 95 language by creating a new Time
type that could be used in the languages time constructs such as the
delay until statement or various forms of the select
statement. Prototype implementations exist for both.
After discussion by the ARG it was decided that the package
mechanism was preferable, and a few changes were suggested. This
document describes the package mechanism only, and includes the
changes requested by the ARG. A discussion of these changes can be
found at the end of the "Discussion" section.
Real-time analysis techniques are always based on the assumption that
the application developer can accurately measure the worst-case
execution time (WCET) of each task. This measurement is always very
difficult, because, with effects like cache misses, pipelined and
superscalar processor architectures, etc., the execution time is
highly unpredictable. There are models that allow calculation of
WCET's for some architectures, but they are generally very complex
and not widely available for all architectures.
In hard real-time systems it is essential to monitor the execution
times of all tasks and detect situations in which the estimated WCET
is exceeded. This detection was usually available in systems scheduled
with cyclic executives, because the periodic nature of its cycle
allowed checking that all initiated work had been completed at each
cycle. In event-driven concurrent systems the same capability should
be available, and this can be accomplished with execution time clocks
Moreover, many flexible real-time scheduling algorithms require the
capability to measure execution time and be able to perform scheduling
actions when a certain amount of execution time has been consumed (for
example, sporadic servers in fixed priority systems, or the constant
bandwidth server in EDF-scheduled systems). Support for execution time
clocks and timers would ease implementation of such flexible
scheduling algorithms in Ada 95.
The Real-Time extensions to POSIX have recently incorporated support for
execution time monitoring. Real-Time POSIX supports execution time clocks and
timers that allow an application to monitor the consumption of execution time
by its tasks, and to set limits for this consumption.
It could be argued that given that the POSIX standard already defines
execution time clocks and timers it would not be necessary to have the
same functionality in the Ada language standard, because the POSIX
services can be accessed through the appropriate bindings. This is
true for Ada platforms built on top of POSIX OS implementations, but
not for bare-machine implementations, like the ones used in embedded
systems, avionics, etc. For portability purposes it is necessary to
have this functionality supported in a homogeneous way for all the
implementations that choose to support it.
Add new section D.14.
D.14 Execution Time
This clause specifies an execution-time clock package.
The following language-defined library package exists:
package Ada.Real_Time.Execution_Time is
type CPU_Time is private;
CPU_Time_First : constant CPU_Time;
CPU_Time_Last : constant CPU_Time;
CPU_Time_Unit : constant := implementation-defined-real-number;
CPU_Tick : constant Time_Span;
(T : Ada.Task_Identification.Task_ID
function "+" (Left : CPU_Time; Right : Time_Span) return CPU_Time;
function "+" (Left : Time_Span; Right : CPU_Time) return CPU_Time;
function "-" (Left : CPU_Time; Right : Time_Span) return CPU_Time;
function "-" (Left : CPU_Time; Right : CPU_Time) return Time_Span;
function "<" (Left, Right : CPU_Time) return Boolean;
function "<=" (Left, Right : CPU_Time) return Boolean;
function ">" (Left, Right : CPU_Time) return Boolean;
function ">=" (Left, Right : CPU_Time) return Boolean;
(T : CPU_Time; SC : out Seconds_Count; TS : out Time_Span);
function Time_Of (SC : Seconds_Count; TS : Time_Span) return CPU_Time;
protected type Timer
(T : access Ada.Task_Identification.Task_ID)
procedure Arm (Interval : Time_Span);
procedure Arm (Abs_Time : CPU_Time);
function Timer_Has_Expired return Boolean;
function Time_Remaining return Time_Span;
Timer_Error : exception;
Timer_Resource_Error : exception;
Execution time or cpu time of a given task is defined as the time spent
by the system executing that task, including the time spent executing
run-time or system services on behalf of it. The mechanism used to
measure execution time is implementation defined. It is implementation
defined which task, if any, is charged the execution time that is
consumed by interrupt handlers and run-time services on behalf of the
The type CPU_Time represents the execution time of a task. The set of
values of the type CPU_Time corresponds one-to-one with an
implementation-defined range of mathematical integers.
The CPU_Time value I represents the half-open execution-time interval
that starts with I*CPU_Time_Unit and is limited by
(I+1)*CPU_Time_Unit, where CPU_Time_Unit is an implementation-defined
real number. For each task, the execution time value is set to zero at
some unspecified point between the task creation and the start of the
CPU_Time_First and CPU_Time_Last are the smallest and largest values
of the Time type, respectively.
CPU_Time_Unit is the smallest amount of execution time representable
by the CPU_Time type; it is expressed in seconds. A CPU clock tick is an
execution time interval during which the clock value (as observed by
calling the Clock function) remains constant. CPU_Tick is the average
length of such intervals.
The effects of the operators on Time and Time_Span are as for the
operators defined for integer values.
The function Clock returns the amount of execution time of the task
associated with the execution-time clock of the task represented by T.
The effects of the Split and Time_Of operations are defined as
follows, treating values of type CPU_Time, Time_Span, and
Seconds_Count as mathematical integers. The effect of Split (T, SC,
TS) is to set SC and TS to values such that TCPU_Time_Unit = SC1.0 +
TSCPU_Time_Unit, and 0.0 <= TSCPU_Time_Unit < 1.0. The value
returned by Time_Of(SC,TS) is the execution-time value T such that
T*CPU_Time_Unit=SC*1.0 + TS*CPU_Time_Unit.
Package Execution_Time contains a protected object type called Timer,
which represents a software object that is capable of detecting
execution time overruns. Each timer is attached to a specific execution
time clock, which is the clock of the task specified by the access
discriminant T. This protected object type has visible operations for
the application tasks to arm or disarm a timer, and to determine
whether a timer has expired or not (Timer_Has_Expired). In addition,
Timer has an entry (Timer_Expired) that can be used by application
tasks to block until an execution time budget is exhausted, or as an
event that triggers the abortion of the instructions of a select
statement with an abortable part.
When a Timer object is created, or upon the first call to one of its Arm
procedures, the resources required to operate a CPU-time timer based on
the associated execution-time clock will be allocated and initialized.
If this operation would exceed the limit of the maximum number of timers
in the system, the Timer_Resource_Error exception is raised. The timer
is initialized in the disarmed state.
The Arm protected procedure that takes a Time_Span parameter
loads the associated timer with the relative value specified by
Interval and sets it to the armed state. In this state the timer
counts execution time and, when the CPU clock associated with the
timer measures the passage of Interval, it is said to have expired. If
the timer was already armed, it is rearmed.
The Arm protected procedure that takes a CPU_Time parameter
loads the associated timer with the absolute value specified by
Abs_Time and sets it to the armed state. In this state the timer
monitors execution time and, when the CPU clock associated with the
timer reaches the value Abs_Time, it is said to have expired. If the
value of Abs_Time had already been reached by the clock at the time of
the call, the timer is set to the armed state and is said to have
expired. If the timer was already armed, it is rearmed.
The Disarm protected procedure sets the timer to the disarmed
state. In this state no timer expirations occur.
The Timer_Expired protected entry suspends the calling task until
the timer expires if the timer is in the armed state; if the timer has
already expired, then the calling task proceeds. If the timer is in the
disarmed state, the Timer_Error exception is raised.
The Time_Has_Expired protected function returns True if the
timer is in the armed state and has expired, and returns False if the
timer is in the armed state but has not yet expired. If the timer is
in the disarmed state, the Timer_Error exception is raised.
The Time_Remaining protected function returns, when the timer is
in the armed state, the CPU time interval that remains until the timer
will expire, or a value representing zero if the timer has expired. If
the timer is in the disarmed state, the Timer_Error exception is raised.
The Timer_Error exception is raised by Timer_Expired,
Timer_Has_Expired, or Time_Remaining if an attempt is made
to use a timer that is in the disarmed state.
When an object of type Timer is finalized, the system resources used by
the timer shall be deallocated.
The range of CPU_Time values shall be sufficient to uniquely represent
the range of execution times from the task start-up to 50 years of
execution time later. CPU_Tick shall be no greater than 1 millisecond.
The implementation shall document the values of CPU_Time_First,
CPU_Time_Last, CPU_Time_Unit, and CPU_Tick.
The implementation shall document the properties of the underlying
mechanism used to measure execution times, such as the range of
values supported and any relevant aspects of the underlying hardware
or operating system facilities used.
The implementation shall document the following metrics:
- An upper bound on the execution-time duration of a clock
tick. This is a value D such that if t1 and t2 are any execution
times of a given task such that t1<t2 and Clock[t1]=Clock[t2]
then t2-t1 <= D.
- An upper bound on the size of a clock jump. A clock jump is the
difference between two successive distinct values of an execution
-time clock (as observed by calling the Clock function with the
- An upper bound on the execution time of a call to the Clock
function, in processor clock cycles.
- Upper bounds on the execution times of the operators of the type
CPU_Time, in processor clock cycles.
Implementations targeted to machines with word size smaller than 32
bits need not support the full range and granularity of the CPU_Time
When appropriate, implementations should provide configuration
mechanisms to change the value of CPU_Tick.
A prototype implementations was developed for the initial
proposal, using the MaRTE operating system that provides a POSIX.13
interface and includes execution-time clocks and timers.
The implementation of the proposal is very simple,
because it does not require modifications to the compiler nor to the
Implementations on bare machines or systems without POSIX
execution-time clocks and timers would be a bit more complex because
the underlaying execution-time monitoring functionality would have to
be implemented in the scheduler. Document  describes one such
implementation and it can be seen that it is relatively simple, and
that it does not introduce any significant overhead into the
The overhead of the implementation is small.
The original proposal included Time_Of taking a Task_Id
parameter. This was included so that an implementation could
choose to have the Task_Id as part of an Execution_Time value, in case
we wished to disallow operations between CPU_Time values of different
tasks. Since we allow operations between CPU_Time values from different tasks,
the Task_Id is not needed.
The initial proposal left the initial value of the execution time
clock of each task unspecified. However, it is valuable to be
able to determine a task's absolute execution time, and thus the value
should be forced to start at zero. In some implementations this requirement may
require saving an initial value of the CPU-Time clock, but this isn't
an expensive requirement.
Because the execution time value may be set to zero during the task's
activation, the requirement is that the value is set to zero at
some unspecified point between the task creation and the end of the
The initial proposal had two protected operations inside the Timer:
Initialize and Finalize. Initialize took a parameter that identified
the execution time clock to be used. These operations appeared unnecessary
to reviewers; the parameter could be moved to an access discriminant
of the protected type or a parameter of the Arm operation. The
reviewers preferred the later solution.
Without these operations, a library implementation of the package on top
of the POSIX execution-time services will have to include a component
derived from Ada.Finalization.Controlled in the protected type to ensure
that appropriate initialization and finalization are made. This should not
cause a hardship; restricted runtime implementations may have to resort to
some "magic", but most implementations will not need extra support. In
either case, the overhead is small and bounded.
Given that it is forecasted that most implementations of package
Ada.Real_Time.Execution_Time will be made on top of the POSIX
execution-time services, the
parameter that identifies the clock should be an access discriminant,
and not a parameter to Arm. The reason is that in the POSIX API
Execution-Time timers are system objects that require allocation and
deallocation of resources, and therefore it is not reasonable to
allocate these resources each time a Timer is being used. The common
use is to allocate the resources once, and then use the timer many
times. It is also necessary to take into account that an application
may want to establish more than one timer per task, and therefore the
resources cannot be preallocated: for example, a system may be
implementing a sporadic server for a given task using a CPU-Time
Timer, but that task itself may use another timer to finish some
particular any-time algorithm that it may be executing.
Example 1: Stopped task
The following is an example of a periodic task that limits its own execution
time to some predefined amount called WCET (worst-case execution
time). If an execution time overrun is detected, the task aborts the
remainder of its execution, until the next period.
with Ada.Real_Time, Ada.Real_Time.Execution_Time, Ada.Task_Identification;
use type Ada.Real_Time.Time;
task body Periodic_Stopped is
My_Id : aliased Task_Identification.Task_Id:=
The_Timer : Ada.Real_Time.Execution_Time.Timer(My_Id'access);
Next_Start : Real_Time.Time:=Real_Time.Clock;
WCET : constant Duration:=1.0E-3;
Period : constant Duration:=1.0E-2;
Next_Start := Next_Start + Real_Time.To_Time_Span(Period);
delay until Next_Start;
Example 2: Lowered task
In this example, when an execution time overrun is detected the priority
of the task is lowered to allow other lower priority tasks to
continue meeting their timing requirements.
A simple implementation of this scheme uses two nested tasks: the
Worker task and the Supervisor task. The Supervisor task sleeps until
the execution time of the Worker task reaches the instant of the
priority change. When this happens the supervisor lowers (or
increases) the priority of the worker task. If the Worker task
completes the work before the instant of the priority change then it
aborts the Supervisor task.
Ada.Dynamic_Priorities, System, Ada.Task_Identification;
task body Worker is
task Supervisor is
task body Supervisor is
WCET : constant Duration:=1.0E-3;
My_Id : aliased Task_Identification.Task_Id:=Supervisor'Identity;
The_Timer : Ada.Real_Time.Execution_Time.Timer(My_Id'access);
Low_Prio : System.Priority:=System.Priority'First;
From: Alan Burns
Sent: Monday, August 5, 2002 8:28 AM
I attach the AI from Michael Harbour on CPU clocks.
I'm not sure if this issue actually had an AI number.
For the real-time folks this is the second most important
issue (after Ravenscar).
You can see that the AI contains two possible approches, a
new timer type or a new library package. It would be useful
at the next ARG to have a general discusion about the approach
to be take.
[Editor's note: The attachment is draft 1 of this AI. The draft credited
authors of Michael Gonzalez Harbour, Javier Miranda, and Mario Aldea
on behalf of IRTAW11].
Additional references for the original proposal:
 A Proposal to Integrate the POSIX Execution-Time Clocks into Ada
95. Technical Report, June, 2002, By J. Miranda Gonzalez and
M. Gonzalez Harbour.
 Implementing and using Execution Time Clocks in Ada Hard
Real-Time Applications. By Gonzalez Harbour M., Aldea Rivas M.,
Gutierrez Garcia J.J., Palencia Gutierrez J.C. International
Conference on Reliable Software Technologies, Ada-Europe'98,
Uppsala, Sweden, in Lecture Notes on Computer Science No. 1411,
Junio, 1998, ISBN:3-540-64563-5, pp. 91,101.
 Extending Ada's Real-Time Systems Annex with the POSIX Scheduling
Services. By: Mario Aldea Rivas and Michael Gonzalez
Harbour. IRTAW-2000, Las Navas, Avila, Spain.
Questions? Ask the ACAA Technical Agent