!standard D.14 (01) 04-03-25 AI95-00307/08 !class amendment 02-08-28 !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 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. This revision of the AI was produced by IRTAW 12 in response to the requirement to be able to wait for one or more Timers to expire. This has required a restructuring of the proposed solution. The consequence is that the Timer is no longer a protected object. Timer expirations are notified by the system by calling a protected procedure that is passed to it by an access parameter in the Timer operations. !problem 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 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 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. !proposal (See wording.) !wording Add new section D.14. D.14 Execution Time This clause specifies an execution-time clock package. 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 : 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; 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 system. 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 task's activation. CPU_Time_First and CPU_Time_Last are the smallest and largest values of the 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 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 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. 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 or used to define an object declared by a type provided by this package (or any language-defined child package of this package) and the corresponding task object 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 start-up 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; procedure Arm (TM: in out Timer; Interval : Time_Span; H : Handler); procedure Arm (TM: in out Timer; Abs_Time : CPU_Time; H : Handler); procedure Disarm(TM : in out Timer); function Timer_Has_Expired(TM : Timer) return Boolean; function Time_Remaining(TM : Timer) return Time_Span; Timer_Error : exception; Timer_Resource_Error : exception; private ... -- not specified by the language end Ada.Execution_Time.Timers; The type Timer needs finalization (see 7.6). Dynamic Semantics Type Timer 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 type has 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, when arming the timer, an access to a protected procedure (type Handler) is passed. This procedure will be called by the implementation when the timer expires. The constant Min_Handler_Ceiling is the priority value that will insure that no ceiling violation will occur when a handler is executed. 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. The timer is initialized in the disarmed state. If this operation would exceed the limit of the maximum number of timers in the system, the Timer_Resource_Error exception is raised. The Arm 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 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. When a Timer expires, the protected procedure Handler is invoked by the system with a parameter equal to the Timer. The Disarm procedure sets the timer to the disarmed state. In this state the timer will not expire. The Time_Has_Expired 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 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_Has_Expired, or Time_Remaining if an attempt is made to use a timer that is in the disarmed state. 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. Implementation Requirements 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. When an object of type Timer is finalized, the system resources used by the timer shall be deallocated. Implementation Permissions Implementations may limit the number of timers that can be defined for each task. If this limit is exceeded the Timer_Resource_Error exception is raised. !discussion 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 runtime system. Implementations on bare machines or systems without POSIX execution-time clocks and timers would be a bit more complex because the underlying execution-time monitoring functionality would have to be implemented in the scheduler. Document [2] 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 scheduler. 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 task's activation. 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 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.Execution_Time.Timers, Ada.Task_Identification; use Ada; use type Ada.Real_Time.Time; ... task Periodic_Stopped; protected Control is entry Wait_Budget_Expiry; procedure Budget_Expired(T : in out Ada.Execution_Time.Timers.Timer); pragma Priority(Ada.Execution_Time.Timers.Min_Handler_Ceiling); private Expired : Boolean := False; end Control; protected body Control is entry Wait_Budget_Expiry when Expired is begin Expired := False; end Wait_Budget_Expiry; procedure Budget_Expired(T : in out Ada.Execution_Time.Timers.Timer) is begin Expired := True; end Budget_Expired; end Control; task body Periodic_Stopped is My_Id : aliased Task_Identification.Task_Id:= Periodic_Stopped'Identity; The_Timer : Ada.Execution_Time.Timers.Timer(My_Id'Access); Next_Start : Real_Time.Time:=Real_Time.Clock; WCET : constant Duration:=1.0E-3; Period : constant Duration:=1.0E-2; begin loop Ada.Execution_Time.Timers.Arm (The_Timer, Real_Time.To_Time_Span(WCET), Control.Budget_Expired'Access); select Control.Wait_Budget_Expiry; -- Execution-time overrun detection -- Handle_the_error; then abort null; -- Do_useful_work; end select; Ada.Execution_Time.Timers.Disarm(The_Timer); Next_Start := Next_Start + Real_Time.To_Time_Span(Period); delay until Next_Start; end loop; end Periodic_Stopped; ... 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. with Ada.Real_Time,Ada.Execution_Time.Timers, Ada.Dynamic_Priorities, System, Ada.Task_Identification; use Ada; ... protected Control is entry Wait_Budget_Expiry; procedure Budget_Expired(T : in out Ada.Execution_Time.Timers.Timer); pragma Priority(Ada.Execution_Time.Timers.Min_Announce_Ceiling); private Expired : Boolean := False; end Control; protected body Control is entry Wait_Budget_Expiry when Expired is begin Expired := False; end Wait_Budget_Expiry; procedure Budget_Expired(T : in out Ada.Execution_Time.Timers.Timer) is begin Expired := True; end Budget_Expired; end Control; task Worker; task body Worker is task Supervisor is pragma Priority(System.Priority'Last); end Supervisor; task body Supervisor is WCET : constant Duration:=1.0E-3; My_Id : aliased Task_Identification.Task_Id:=Supervisor'Identity; The_Timer : Ada.Execution_Time.Timers.Timer(My_Id'Access); Low_Prio : System.Priority:=System.Priority'First; begin Ada.Execution_Time.Timers.Arm (The_Timer, Real_Time.To_Time_Span(WCET), Control.Budget_Expired'Access); Control.Wait_Budget_Expiry; -- wait for timer overrun Dynamic_Priorities.Set_Priority(Low_Prio,Worker'Identity); end Supervisor; begin -- Do_useful_work; abort Supervisor; end Worker; ... --!corrigendum D.13(01) !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. ****************************************************************