Re: Tasking in Ada

[rational.com!bonnie!rlk@uunet.uu.net (Robert Kitzberger)]

kgatlin@galaxy.csc.calpoly.edu (Kang Su Gatlin) writes:

>I have hit a snag with Ada.  I need to create dynamic tasks that know which
>task they are.

If your compiler implements CIFO (the Catalog of Interface Features and
Options for the Ada Runtime Environment) or ExTRA then you can call these
libraries to obtain the task control block for the current task.  Even
if CIFO/ExTRA isn't supported, then your compiler vendor may provide some
implementation-dependent way of getting the current task's TCB. 

>I can't seem to find a way to pass information to tasks efficiently.  I want
>all the tasks to run simultaneously so that the creation and execution of
>the tasks can be done in t(1) time.  

Creation of the tasks will take time linear to n on SISD machines.  On
MISD or MIMD machines, the runtime can activate the tasks in parallel
on multiple processors, achieving activation of n tasks in o(c).  But
on a uniprocessor, even in the case of creating an array of tasks (see
below) the underlying runtime system will activate the tasks
sequentially.  Execution-time complexity of the tasks is another
matter entirely, and outside of the realm of the Ada run-time
environment.  So you see, even if your Ada code appears to
have O(c) complexity, you are a slave to the underlying Ada runtime's
time and space complexity.

Regardless... the classic, portable way to assign task ids and
maintain task counts is to have a 'task manager' assigning ids (pardon
any syntax errors -- I'm just typing this in as I go...)

  type task_id is new natural;

  task id_manager is
     entry new_id( id : out task_id);
     entry number_of_tasks( count : out natural );
     -- to make this an accurate count, you'll want to add 'recycle_id'
     -- or some other such entry to notify the manager of task death
  end id_manager;

  task body id_manager is
     current : task_id := task_id'first;
  begin
     loop
         select
            accept new_id( id : out task_id ) do
                current := current + 1;
                id := current;
            end new_id;
         or
            accept number_of_tasks( count : out natural ) do
                count := natural(current);
            end number_of_tasks;
         or
            terminate;
         end select;
     end loop;
  end id_manager;

Each new task would need to call id_manager.new_id upon startup in
order to determine its identity.  For example:

  task type t is
  end t;

  task body t is
    my_id : task_id;
  begin
    id_manager.new_id( my_id );
    ...
  end t;

  Task_Array : array(1..n) of t;

Note that this will still take time linear to n on uniprocessor
architectures, even if the compiler is smart enough to perform some of
the task initialization at compile-time (e.g. the runtime will loop
through the n task control blocks, allocating stack space, heap space,
register save areas, etc. -- a certain amount can be done in O(c),
but the rest is O(n)).

On a multiprocessor (MISD) architecture, the compiler/runtime could
allocate the tasks to multiple processors and activate in O(c) (minus
some noise for contention on shared memory).

Too bad that tasks can't be generic units -- otherwise you could
parameterize a task with a unique id (as well as address clauses
for interrupt entries, etc...)

Good luck,

	.Bob.

--
Bob Kitzberger                          Internet:   rlk@rational.com
Rational, Grass Valley, CA              CompuServe: 70743,1550