Version 1.5 of ais/ai-00354.txt

Unformatted version of ais/ai-00354.txt version 1.5
Other versions for file ais/ai-00354.txt

!standard D.03 (00)          04-02-19 AI95-00354/03
!class amendment 03-09-27
!status work item 03-09-27
!status received 03-09-27
!priority Low
!difficulty Medium
!subject Group Execution-Time Budgets
This AI proposes a child package of Ada.Execution_Time (the revised AI 00307) to allow more than one task to share an execution-time budget.
Currently Ada 95 has no mechanisms to allow the implementation of aperiodic servers such as sporadic servers and deferrable servers. This severely limits the language's ability to handle aperiodic activities at anything other than a background priority. The fundamental problem that prohibits the implementation of aperiodic server algorithms is that tasks cannot share CPU budgets.
(See wording.)
Add new section:
D.14.2 Group Execution Time Budgets
This clause specifies a group execution time control package.
Static Semantics
The following language-defined library package exists:
with System; with Ada.Task_Identification; package Ada.Execution_Time.Group_Budgets is type Group_Budget is limited private;
type Handler is not null access protected procedure(GB : in out Group_Budget);
type Task_Array is array(Natural range <>) of Ada.Task_Identification.Task_ID;
Min_Handler_Ceiling : constant System.Any_Priority := <Implementation Defined>;
procedure Add_Task(GB: in out Group_Budget; T : Ada.Task_Identification.Task_ID); procedure Remove_Task(GB: in out Group_Budget; T : Ada.Task_Identification.Task_ID); function Is_Member(GB: Group_Budget; T : Ada.Task_Identification.Task_ID) return Boolean; function Is_A_Group_Member( T : Ada.Task_Identification.Task_ID) return Boolean; function Members(GB: Group_Budget) return Task_Array;
procedure Replenish (GB: in out Group_Budget; To : Time_Span); procedure Add(GB: in out Group_Budget; Interval : Time_Span); function Budget_Has_Expired(GB: Group_Budget) return Boolean; function Budget_Remaining(GB: Group_Budget) return Time_Span;
procedure Set_Handler(GB: in out Group_Budget; H : Handler); function Current_Handler(GB: Group_Budget) return Handler; procedure Cancel_Handler(GB: in out Group_Budget; Cancelled : out Boolean);
Group_Budget_Error : exception; private -- not specified by the language end Ada.Execution_Time.Group_Budgets;
The type Group_Budget represents a CPU budget to be used by a group of tasks. Objects of this type require finalization.
An object of type Group_Budget is said to be set if it has a registered Handler. An object is said to be cleared if it has no Handler. All Group_Budget objects are initially cleared.
Dynamic Semantics
Tasks of any priority are added to a group by calling Add_Task. Tasks are members of at most one group. Group_Budget_Error is raised by a call to Add_Task if the task is already a member of any group.
Tasks are removed from a group by calling Remove_Task. An attempt to remove a task that has not been added to the group will cause Group_Budget_Error to be raised.
The Is_Member function will return True if the task parameter is a member of the specified group. The Is_A_Group_Member function returns True if the task is a member of any group. Both return False otherwise.
The Members function returns the task IDs of the members of the group.
When a call to Replenish is made, the Group_Budget is loaded with the Time_Span value passed as a parameter. Any execution of the group of tasks results in the Group_Budget counting down. When the budget is exhausted (goes to Time_Span_Zero) the handler, if set, is called; the tasks continue to execute. A Group_Budget is initially loaded with zero budget.
A call to Budget_Remaining returns the remaining budget. If the budget is exhausted it will return Time_Span_Zero. This is the minimum value for the budget. A call to Budget_Has_Expired will return True if the budget is exhausted (equal to Time_Span_Zero), otherwise it returns False.
A Group_Budget can have its budget increased by calling Add. A negative value for the parameter will reduce the budget, but never below Time_Span_Zero.
A call of Replenish with a non positive value of To will causes exception Group_Budget_Error to be raised. A call to Add that results in the value of the budget going to Time_Span_Zero will cause the handler, if set, to be executed.
A call to Set_Handler registers the Handler and returns when GB is set. A call to Set_Handler for a Group_Budget that is already set, initially clears the Group_Budget then registers the new Handler.
A call to Current_Handler returns with the current Handler. If the Group_Budget denoted by GB is not set, exception Group_Budget_Error is raised.
A call to Cancel_Handler returns after the Group_Budget denoted by GB is cleared. Cancelled is assigned True if GB was set prior to it being cleared; otherwise the parameter is assigned False.
The constant Min_Handler_Ceiling is the priority value that will insure that no ceiling violation will occur when a handler is executed.
The precision of the accounting of task execution time to a Group_Budget is the same as that defined for execution-time clocks from the parent package.
As part of the finalization of an object of type Group_Budget all member tasks are removed from the group identified by the object.
If a task is a member of a Group_Budget when it terminates then as part of the finalization of the task it is removed from the group.
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 Group_Budget object, the implementation shall perform the operations declared in this package atomically with respect to any of these operations on the same Group_Budget object.
One common bandwidth preserving technique is the deferrable server. The code for a simple deferrable server is given below:
with Ada.Timing_Events; use Ada.Timing_Events; with Ada.Execution_Time.Group_Budgets; use Ada.Execution_Time.Group_Budgets; with Ada.Task_Identification; use Ada.Task_Identification; with Ada.Real_Time; use Ada.Real_Time; with System; use System; package Deferrable_Servers is type Deferrable_Server is limited private;
procedure Create(DS : in out Deferrable_Server; First : Time; Budget : Time_Span; Period : Time_Span); procedure Add(DS : in out Deferrable_Server; T : Task_Id);
private protected type Controller(DS : access Deferrable_Server) is procedure Budget_Expired(GB: in out Group_Budget); procedure Replenish_Due(TE : in out Timing_Event); pragma Priority(Priority'Last); end Controller;
type Deferrable_Server is record Budget : Time_Span; Period : Time_Span; Next_Replenishment_Time : Time; Replenish_Control : Timing_Event; Budget_Control : Group_Budget; Server_Control : Controller(Deferrable_Server'access); end record; end Deferrable_Servers;
A deferrable server can be represented by a type which encapsulated the Budget, the replenishment period, the next replenishment time, a Timing_Event to signal the next replenishment time, a Group_Budget to monitor the execution time consumed by the controlled tasks, and a controller to perform the required suspension and resumption of the tasks.
The body of the package is given below.
with Ada.Asynchronous_Task_Control; use Ada.Asynchronous_Task_Control; package body Deferrable_Servers is
procedure Create(DS : in out Deferrable_Server; First : Time; Budget : Time_Span; Period : Time_Span) is begin DS.Budget := Budget; DS.Period := Period; DS.Next_Replenishment_Time := First; Group_Budgets.Set_Handler(DS.Budget_Control, DS.Server_Control.Budget_Expired'access); Timing_Events.Set_Handler(DS.Replenish_Control, DS.Next_Replenishment_Time, DS.Server_Control.Replenish_Due'access); end Create;
procedure Add(DS : in out Deferrable_Server; T : Task_Id) is begin Add_Task(DS.Budget_Control,T); end Add;
protected body Controller is procedure Budget_Expired(GB : in out Group_Budget) is TA : Task_Array := Members(GB); begin for ID in TA'range loop Ada.Asynchronous_Control.Hold(TA(ID)); end loop; end Budget_Expired;
procedure Replenish_Due(TE : in out Timing_Event) is TA : Task_Array; begin Replenish(DS.Budget_Control, DS.Budget); DS.Next_Replenishment_Time := DS.Next_Replenishment_Time + DS.Period; Timing_Events.Set_Handler(DS.Replenish_Control, DS.Next_Replenishment_Time, DS.Server_Control.Replenish_Due'access); TA := Members(DS.Budget_Control); for ID in TA'range loop Ada.Asynchronous_Control.Continue(TA(ID)); end loop; end Replenish_Due;
end Controller;
end Deferrable_Servers;
Should the Add_Task, Remove_Task have a default task_ID of the current task?
Various alternative models were considered including:
a) Passing the Notify protected procedure as an access discriminant to the Group_Budget type.
This was rejected in favour of explicit get and set methods mainly for ease of use when combining an object of the Group_Budget type and the required protected object into a single record type.
b) Passing an unconstrained array of task identifiers as a parameter to the Handler protected procedure.
The argument for such a facility is that the user of the package is probably going to want to know the group of tasks whose Timer has expired. This can now be done with the Members function.
c) Having the Group_Budget type as a tagged type.
This was rejected as the Workshop as unclear on whether the benefit was worth the added complexity and overhead.
d) Having the package automatically suspend the group of tasks when the associated Group_Budget expired.
This was rejected because not all Aperiodic Server approaches suspend the tasks, some set the tasks' priorities to a background priority.
!ACATS test
Tests should be created to check on the implementation of this feature.

From: Robert Dewar
Sent: Thursday, February 19, 2004  12:14 PM

For a proposal like this, I would like to see an analysis of
implemntability under various operating systems and real time
executives, e.g. AE653. These days almost all Ada real-time programs are
deployed in such environments and it is important to understand whether
this feature fits smoothly into existing environments. If not, I would
consider this a serious problem with the proposal.

In other words, it is hard to convince me that Ada needs to be able to
do something that cannot be done under Lynx, VxWorks, Integrity,
Solaris, NT, and other systems typically being used today
to implement real time systems.


From: Alan Burns
Sent: Monday, February 23, 2004  6:44 PM

It is true that no current RTOS provides exactly this capability,
but I think a number of activities do warrant the (optional)
support of budgeting in Ada:

1) Real-Time Java has it (as an optional capability)
2) POSIX defines sporadic servers; which are a weaker provision
3) Servers in general are much discussed in the literature and
can be programmed with this provision
4) Applications are looking for various forms of isolation;
budgets (on a group of tasks) does provide one useful aaproach.
5) It is only an optional provision, but does give an API
that defines a standard way of supporting budgets.
6) In general RTOSs are weak in their support for execution
time budgeting (per thread and for groups of threads); this
will change I believe. Should Ada wait for OSs or help to
define what RTOSs should/will support in the future?


Questions? Ask the ACAA Technical Agent