Version 1.3 of ais/ai-00354.txt

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

!standard D.03 (00)          03-11-24 AI95-00354/02
!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
!summary
This AI proposes a child package of Ada.Real_Time.Execution_Time (the revised AI 00307) to allow more than one task to share an execution-time budget.
!problem
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.
!proposal
(See wording.)
!wording
Add new section:
D.14.1 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.Real_Time.Execution_Time.Group_Budgets is type Group_Budget is limited private;
type Handler is access protected procedure(GB : in out Group_Budget);
type Task_Group is array(Natural range <>) of Ada.Task_Identification.Task_ID;
Min_Handler_Ceiling : constant System.Any_Priority := <Implementation Defined>;
procedure Set_Handler(GB: in out Group_Budget; H : Handler); function Current_Handler(GB: Group_Budget) return Handler;
procedure Replenish (GB: in out Group_Budget; To : Time_Span); procedure Add(GB: in out Group_Budget; Interval : Time_Span);
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_Member( T : Ada.Task_Identification.Task_ID) return Boolean;
function Budget_Has_Expired(GB: Group_Budget) return Boolean; function Budget_Remaining(GB: Group_Budget) return Time_Span;
function Members(GB: Group_Budget) return Task_Group;
Group_Budget_Error : exception; private -- not specified by the language end Ada.Real_Time.Execution_Time.Group_Budgets;
The type Group_Budget represents a CPU budget to be used by a group of tasks.
Dynamic Semantics
Tasks of any priority can be added to a group by calling Add_Task. Tasks can be the member 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 can be 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 first Is_Member function will return True if the task parameter is a member of the specified group. The other Is_Member function returns True if the task is a member of any group. Both return False otherwise.
When the Group_Budget is exhausted a call is made to a protected procedure. This procedure can be set by the Set_Handler subprogram. The subprogram Current_Handler allows the current procedure to be obtained. A call to Set_Handler for a Group_Budget that is already set, resets the handler.
The constant Min_Handler_Ceiling indicates the minimum ceiling priority that must be assigned to any protected object associated with the Handler protected procedure.
A Group_Budget is initially without budget. The Handler protected procedure is initially null.
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 is called; the tasks continue to execute.
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 to be executed.
The Members function returns the task IDs of the members of the group.
The precision of the accounting of task execution time to a Group_Budget is the same as that of Timers from the parent package.
As part of the finalization of an object of type Group_Budget all tasks are removed from the group identified by the object.
If restriction No_Nested_Finalization is in effect Group_Budget objects can only be defined at the library level.
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.
!example
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.Real_Time.Execution_Time.Group_Budgets; use Ada.Real_Rime.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 begin for T in Members(GB)'range loop Ada.Asynchronous_Control.Hold(T); end loop; end Budget_Expired;
procedure Replenish_Due(TE : in out Timing_Event) is 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); for T in Members(GB)'range loop Ada.Asynchronous_Control.Continue(T); end loop; end Replenish_Due;
end Controller;
end Deferrable_Servers;
!discussion
Should the Add_Task, Remove_Task and the two Is_Member functions 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.
!appendix

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

Questions? Ask the ACAA Technical Agent