!standard D.14 (00) 05-03-16 AI95-00307/11 !standard D.14.1 (00) !class amendment 02-08-28 !status Amendment 200Y 04-06-24 !status ARG Approved 8-0-0 04-06-13 !status work item 03-09-21 !status ARG Approved 12-0-1 03-06-20 !status work item 02-08-28 !status received 02-08-28 !priority High !difficulty Hard !subject Execution-Time Clocks !summary Modern real-time scheduling policies require that applications have the ability to measure the execution time of tasks, and to detect execution time overruns. This functionality is provided by a new package that defines execution time clocks and a child of this package which provides timers. !problem Performance analysis techniques are usually based on the assumption that the application developer can accurately measure/estimate the execution time of each task. 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 the calculation of worst-case execution time (WCET) for some architectures, but they are generally very complex and not widely available for all architectures. A language defined means of measuring execution time is desirable. 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 is usually available in systems scheduled with cyclic executives, because the periodic nature of a cycle allows checking that all initiated work has 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 and timers. 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. 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. !proposal (See wording.) !wording Add new section D.14. D.14 Execution Time This clause describes a language-defined package to measure execution time. Static Semantics The following language-defined library package exists: with Ada.Task_Identification; with Ada.Real_Time; use Ada.Real_Time; package Ada.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; function Clock (T : Ada.Task_Identification.Task_Id := Ada.Task_Identification.Current_Task) return CPU_Time; 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; procedure Split (T : in CPU_Time; SC : out Seconds_Count; TS : out Time_Span); function Time_Of (SC : Seconds_Count; TS : Time_Span) return CPU_Time; private ... -- not specified by the language end Ada.Execution_Time; The *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 its behalf. 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 system. The type CPU_Time represents the execution time of a task. The set of values of this type 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 creation of the task and the start of the activation of the task. CPU_Time_First and CPU_Time_Last are the smallest and largest values of the CPU_Time type, respectively. Dynamic Semantics 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 CPU_Time and Time_Span are as for the operators defined for integer types. The function Clock returns the current execution time of the task identified by T; Tasking_Error is raised if that task has terminated; Program_Error is raised if the value of T is Task_Identification.Null_Task_Id. 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 T*CPU_Time_Unit = SC*1.0 + TS*CPU_Time_Unit, and 0.0 <= TS*CPU_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. Erroneous Execution For a call of Clock, if the task identified by T no longer exists, the execution of the program is erroneous. Implementation Requirements The range of CPU_Time values shall be sufficient to uniquely represent the range of execution times from the task creation to 50 years of execution time later. CPU_Tick shall be no greater than 1 millisecond. Documentation Requirements 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. Metrics 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> The following language-defined library package exists: @xcode<@b Ada.Task_Identification; @b Ada.Real_Time; @b Ada.Real_Time; @b Ada.Execution_Time @b @b CPU_Time @b; CPU_Time_First : @b CPU_Time; CPU_Time_Last : @b CPU_Time; CPU_Time_Unit : @b := @ft<@i>; CPU_Tick : @b Time_Span; @b Clock (T : Ada.Task_Identification.Task_Id := Ada.Task_Identification.Current_Task) @b CPU_Time; @b "+" (Left : CPU_Time; Right : Time_Span) @b CPU_Time; @b "+" (Left : Time_Span; Right : CPU_Time) @b CPU_Time; @b "-" (Left : CPU_Time; Right : Time_Span) @b CPU_Time; @b "-" (Left : CPU_Time; Right : CPU_Time) @b Time_Span; @b "<" (Left, Right : CPU_Time) @b Boolean; @b "<=" (Left, Right : CPU_Time) @b Boolean; @b "@>" (Left, Right : CPU_Time) @b Boolean; @b "@>=" (Left, Right : CPU_Time) @b Boolean; @b Split (T : @b CPU_Time; SC : @b Seconds_Count; TS : @b Time_Span); @b Time_Of (SC : Seconds_Count; TS : Time_Span) @b CPU_Time; @b ... -- not specified by the language @b Ada.Execution_Time;> The @i 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 its behalf. 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 system. The type CPU_Time represents the execution time of a task. The set of values of this type 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 creation of the task and the start of the activation of the task. CPU_Time_First and CPU_Time_Last are the smallest and largest values of the CPU_Time type, respectively. @i<@s8> CPU_Time_Unit is the smallest amount of execution time representable by the CPU_Time type; it is expressed in seconds. A @i 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 CPU_Time and Time_Span are as for the operators defined for integer types. The function Clock returns the current execution time of the task identified by T; Tasking_Error is raised if that task has terminated; Program_Error is raised if the value of T is Task_Identification.Null_Task_Id. 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 T*CPU_Time_Unit = SC*1.0 + TS*CPU_Time_Unit, and 0.0 <= TS*CPU_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. @i<@s8> For a call of Clock, if the task identified by T no longer exists, the execution of the program is erroneous. @i<@s8> 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. @i<@s8> 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. @i<@s8> The implementation shall document the following metrics: @xbullet @xbullet @xbullet @xbullet @i<@s8> Implementations targeted to machines with word size smaller than 32 bits need not support the full range and granularity of the CPU_Time type. @i<@s8> When appropriate, implementations should provide configuration mechanisms to change the value of CPU_Tick. !corrigendum D.14.1(01) @dinsc This clause describes a language-defined package that provides a facility for calling a handler when a task has used a defined amount of CPU time. @i<@s8> The following language-defined library package exists: @b System; @b Ada.Execution_Time.Timers @b @b Timer (T : @b Ada.Task_Identification.Task_Id) @b @b; @b Timer_Handler @b @b (TM : @b Timer); Min_Handler_Ceiling : @b System.Any_Priority := @ft<@i>; @b Set_Handler (TM : @b Timer; In_Time : @b Time_Span; Handler : @b Timer_Handler); @b Set_Handler (TM : @b Timer; At_Time : @b CPU_Time; Handler : @b Timer_Handler); @b Current_Handler (TM : Timer) @b Timer_Handler; @b Cancel_Handler (TM : @b Timer; Cancelled : @b Boolean); @b Time_Remaining (TM : Timer) @b Time_Span; Timer_Resource_Error : @b; @b ... -- not specified by the language @b Ada.Execution_Time.Timers;> The type Timer represents an execution-time event for a single task and is capable of detecting execution time overruns. The access discriminant T identifies the task concerned. The type Timer needs finalization (see 7.6). An object of type Timer is said to be @i if it is associated with a non-null value of type Timer_Handler and @i otherwise. All Timer objects are initially cleared. The type Timer_Handler identifies a protected procedure to be executed by the implementation when the timer expires. Such a protected procedure is called a @i. @i<@s8> When a Timer object is created, or upon the first call of a Set_Handler procedure with the timer as parameter, the resources required to operate a execution-time timer based on the associated execution-time clock are allocated and initialized. If this operation would exceed the available resources, Timer_Resource_Error is raised. The procedures Set_Handler associate the handler Handler with the timer TM; if Handler is @b, the timer is cleared, otherwise it is set. The first procedure Set_Handler loads the timer TM with an interval specified by the Time_Span parameter. In this mode, when the execution time of the task identified by TM.T has increased by In_Time, the timer TM is said to have expired. The second procedure Set_Handler loads the timer TM with the absolute value specified by At_Time. In this mode, when the the execution time of the task identified by TM.T reaches At_Time, the timer TM is said to have @i; if the value of At_Time has already been reached when Set_Handler is called, the timer TM is said to be expired. A call of a procedure Set_Handler for a timer that is already set replaces the handler and the (absolute or relative) execution time; if Handler is not @b, the timer remains set. When a timer expires, the associated handler is executed, passing the timer as parameter. The initial action of the execution of the handler is to clear the event. The function Current_Handler returns the handler associated with the timer TM if that timer is set; otherwise it returns @b. The procedure Cancel_Handler clears the timer if it is set. Cancelled is assigned True if the timer was set prior to it being cleared; otherwise it is assigned False. The function Time_Remaining returns the execution time interval that remains until the timer TM would expire, if that timer is set; otherwise it returns Time_Span_Zero. The constant Min_Handler_Ceiling is the priority value that ensures that no ceiling violation would occur, were a handler to be executed. For all the subprograms defined in this package, Tasking_Error is raised if the task identified by TM.T has terminated, and Program_Error is raised if the value of TM.T is Task_Identification.Null_Task_Id. An exception propagated from a handler invoked as part of the expiration of a timer has no effect. @i<@s8> For a call of any of the subprograms defined in this package, if the task identified by TM.T no longer exists, the execution of the program is erroneous. @i<@s8> For a given Timer object, the implementation shall perform the operations declared in this package atomically with respect to any of these operations on the same Timer object. The replacement of a handler by a call of Set_Handler shall be performed atomically with respect to the execution of the handler. When an object of type Timer is finalized, the system resources used by the timer shall be deallocated. @i<@s8> Implementations may limit the number of timers that can be defined for each task. If this limit is exceeded then Timer_Resource_Error is raised. @xindent<@s9> !ACATS test ACATS test(s) should be created for this package. !appendix 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: [1] A Proposal to Integrate the POSIX Execution-Time Clocks into Ada 95. Technical Report, June, 2002, By J. Miranda Gonzalez and M. Gonzalez Harbour. [2] 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. [3] 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. **************************************************************** From: Alan Burns Sent: Tuesday, August 10, 2004 10:50 PM I attach new version of 307 - execution time clocks [Editor's note: This is version /07.] Main change is the spliting of the package into 2. Also handler is now 'not null'. Text for meaning of operators was there al the time; other changes to words from minutes made. ****************************************************************