Version 1.3 of 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
--
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