Wednesday, September 12, 2012

AdaTutor - Generics and Tasking (2)

Tasking

Here are two versions of a program with two parallel tasks.  Since the main program is a task, these two versions are equivalent.

   with Ada.Text_IO; use Ada.Text_IO;     
   procedure Task_Demo is                 
      task A;                              
      task body A is                       
      begin                                
         Put_Line("b");                     
         Put_Line("b");                     
      end A;                               
   begin                                  
      Put_Line("a");                       
      Put_Line("a");                       
   end Task_Demo;                         
                                         
   with Ada.Text_IO; use Ada.Text_IO;
   procedure Task_Demo is
      task A;
      task body A is
      begin
         Put_Line("a");
         Put_Line("a");
      end A;
      task B;
      task body B is
      begin
         Put_Line("b");
         Put_Line("b");
      end B;
   begin
      null;
   end Task_Demo;

Our program could have specified as many tasks as we like.  Also, our tasks could have declarations between task body ... is and begin.  If the computer has several processors, and the Ada compiler makes use of that fact, the tasks could actually run simultaneously.  Otherwise, the compiler may (but doesn't have to) write code to time slice among the tasks, making them appear to run simultaneously.  One implementation of Ada we tried time slices, and the output of the program looked something like this:

ab

ab

This happened because Put_Line is equivalent to Put plus New_Line, and thus Put_Line can get interrupted before the CR-LF is output.  Here one task displayed "a", the other task displayed "b", and then both tasks sent CR-LF.

Another implementation of Ada we tried won't time-slice unless told to with a pragma, covered in the Advanced Topics section.  So the output of the same program with that implementation of Ada looked like this:

a
a
b
b

In this case one task ran to completion before the other task started.  The point is that both implementations of Ada ran our program correctly, but with different results.

When data are passed between tasks, we often don't want the process to be interrupted.  For example, suppose one task updates a record with several fields, such as a Date.  Another task reads the record.  We don't want the second task to interrupt the first in the middle of updating a record.  Otherwise, the second task might read an updated Day field, an updated Month field, and an old Year field, which would be meaningless.  Ada has an elegant solution to this problem, called the rendezvous.  (Another solution, Ada 95 protected objects and types, will be discusses shortly.)

In this example, we assume that the main program created both procedure Caller and task Server, and defined type Date:

   procedure Caller is       
      D : Date;               
   begin                     
      -----;                  
      -----;  -- Block 1      
      -----;                  
                             
      Server.Update(D);       
                             
      -----;                  
      -----;  -- Block 2      
      -----;                  
   end Caller;               


   task Server is
      entry Update(Item : in out Date);
   end Server;
   task body Server is
   begin
      -----;  -- Block 3
      -----;
      accept Update(Item : in out Date) do
         -----;  -- Block 4
         -----;
      end Update;
      -----;  -- Block 5
      -----;
   end Server;

Code blocks 1 and 3 run in parallel (perhaps simultaneously, as discussed).  Then Caller waits at the call to Server.Update while Server executes block 4.  Block 4 is called the critical section of code, where records might be updated, etc.  When this rendezvous is over, blocks 2 and 5 run in parallel.  If Caller reaches the call before Server reaches accept, Caller will wait patiently there for Server.  If Server reaches accept first, it will wait patiently there for a caller.

The call to Update looks like a procedure call.  We can't use a task, so the call requires dot notation.  The entry specification looks like a procedure specification, with entry replacing procedure.  The task specification may have any number of entry statements; if it has none, we write simply task Server;.  The accept block looks like a procedure without declarations, but accept replaces procedure, and do replaces is begin.  An accept with no parameters and no statements may be written simply as accept Update;.

In Ada 95 there's another way, simpler than the rendezvous, to assure that one task won't try to read an item while another task is writing it.  It's called a protected object.  For example:

   type Date is ...                  
   ...                               
   protected Prot_Date is            
      function Read return Date;      
      procedure Write(D : in Date);   
   private
       Item : Date;                    
   end Prot_Date;                    
                                       
   protected body Prot_Date is
      function Read return Date is
      begin
         return Item;
      end Read;

      procedure Write(D : in Date) is
      begin
         Item := D;
      end Write;
   end Prot_Date;

The syntax is similar to a package or a task, and the calls to Read and Write are similar to task calls: D : Date; ... D := Prot_Date.Read; ... Prot_Date.Write(D);.  Ada 95 guarantees that calls to the protected subprograms, in this case Read and Write, won't execute simultaneously.

This is a protected object. We'll learn about Ada 95 protected types shortly.

Question

   procedure Master is              task Slave is
                                       entry Sync;
                                    end Slave;
                                    task body Slave is
   begin                            begin
     -----;                           -----;
     -----;  -- Block 1               -----;  -- Block 3
     -----;                           -----;
     Slave.Sync;                      accept Sync;
     -----;                           -----;
     -----;  -- Block 2               -----;  -- Block 4
     -----;                           -----;
   end Master;                      end Slave;

True or False?  Statements in blocks 1 and 4 could execute simultaneously.

If several tasks call an entry before the server reaches accept, the calls are queued first-in, first-out.

We can write a select block to accept any of several different calls:

   select
      accept A;
   or
      accept B(I : in Integer) do
         -----;
      end B;
   or
      accept C;
   end select;

When select is reached, the task waits for a call to A or B or C.  If calls to more than one entry are pending, one will be chosen arbitrarily.

A delay statement, used in ordinary code, will delay a specified number of seconds (plus any system overhead).  For example,

   A;
   delay 5.0;
   B;
will call A, delay five seconds (plus system overhead), and then call B.  However, when used in a select block, the meaning is a bit different.  It's used to implement an impatient server.  For example,
   select
      accept A;
   or
      accept B;
   or
      delay 5.0;
      C;
   end select;
will wait up to five seconds for a call to A or B.  If no call is received, C will be called.

Guards can be used to switch alternatives of a select block on and off.  For example,

   J : Integer;
   ...
   select
      when J = 1 =>
      accept A;
   or
      when J = 2 =>
      accept B;
   end select;

Here A is an alternative only if the condition (J = 1) is true; B is an alternative only if J = 2.  If J /= 1, then no call to A will be accepted, even if one is pending.  If every branch of a select block has a guard and all guards are false, Program_Error is raised.

In Ada 95, we have protected types.  For example:

   protected type P is            
      entry One;                   
      entry Two(I : in Integer);   
   private                        
      X, Y : Integer;              
      ...
   end P;                         

   protected body P is
      entry One when X > Y is
      begin
         ...
      end One;

      entry Two(I : in Integer) when True is
      begin
         ...
      end Two;
   end P;

We can declare Q : P; J : Integer; and then call Q.One; and Q.Two(J);.  In the body, each entry has a barrier, similar to the guards just discussed.  Here a call to One can be accepted only if X > Y; otherwise, the call is queued.  A call to Two can always be accepted because the barrier is simply True.  At the end of each call, all the barriers are re-evaluated.

In Ada 95 an entry can requeue itself on another entry.  For example, the body of Two can execute requeue One; to requeue itself on entry One.

Ada 95 also lets us write

   select
      delay 10.0;
      C;
   then abort
      A;
      B;
   end select;

Here if the statements in the second block (the calls to A and B) take more than 10.0 seconds, they are abandoned and the first block (the call to C) is executed instead.

Tasks "die" in three ways.  The least elegant way is for a task to abort it, e.g., abort Server;.  This is drastic, because Server might be doing anything.  A better way is for a family of tasks each to include terminate; as one alternative in a select block.  (A "family" of tasks is the set of tasks created by one "parent," for example, the main program.)  When calls to the entries in the tasks all cease, all tasks in the family will reach the terminate alternative, and all will die together.

But the most orderly way for a task to die is for it simply to reach its last statement.  For example, task T below will continue to accept calls to T.A and T.B until a task calls T.Shutdown.  At that time, T will die.

   task T is                   
      entry A;                  
      entry B;                  
      entry Shutdown;           
   end T;                      
                               
   task body T is
      Done : Boolean := False;
   begin
      while not Done loop
         select
            accept A do
               -----;
            end A;
         or
            accept B do
               -----;
            end B;
         or
            accept Shutdown;
            Done := True;
         end select;
      end loop;
   end T;

Trying to call an entry of a task that has died will raise Tasking_Error.  Also, a task can't terminate until all the tasks it creates terminate.  In particular, the main program can't return to the operating system until all tasks in the program have died.  Programmers must be careful to avoid possible deadlocks.  Ada solves many problems that plague other languages, but unfortunately the deadlock problem remains unsolved.

A select block may have an else alternative.  Here's an example of a very impatient server.  If a call to A or B is pending it will be served, otherwise, C will be called:

   select
      accept A do
         -----;
      end A;
   or
      accept B do
         -----;
      end B;
   else
      C;
   end select;

Question

   type Date is ...                  
   task Data_Protector is           
      entry Read_Date(D : out Date); 
      entry Write_Date(D : in Date); 
      entry Shutdown;                
   end Data_Protector;              
                                   
                                   
   task body Data_Protector is
      Save_D : Date;
      Done   : Boolean := False;
   begin
      accept Write_Date(D : in Date) do
         Save_D := D:
      end Write_Date;
      while not Done loop
         select
            accept Read_Date(D : out Date) do
               D := Save_D;
            end Read_Date;
         or
            accept Write_Date(D : in Date) do
               Save_D := D;
            end Write_Date;
         or
            accept Shutdown;
            Done := True;
         end select;
      end loop;
   end Data_Protector;
True or False?  This task must serve at least one call to Write_Date before it will accept calls to Read_Date.

The select block can be used in a caller as well as a server.  The following block waits up to five seconds to call entry A in task T.  If T isn't ready to accept the call in five seconds, the block calls procedure B instead.  This is called an impatient customer:

   select
      T.A;
   or
      delay 5.0;
      B;
   end select;

A very impatient customer can be implemented with else.  This block calls T.A only if T is ready to accept the call immediately, otherwise, it calls B.

   select
      T.A;
   else
      B;
   end select;

Task types may be declared.  This permits us to create an array of tasks, and it lets us bring tasks into existence via access types.  Tasks begin executing as soon as they're brought into existence.  For example,

   task type X is
      entry E;
   end X;
   type P is access X;
   X1 : P;
   A : array(1 .. 10) of X;
   task body X is
      ...
   end X;

Entries to these tasks are called thus:

   A(5).E;
   X1 := new X;
   X1.all.E; -- or just X1.E;

Ada comes with a package Ada.Calendar.  In Ada 83, the name is simply Calendar, and Ada 95 accepts the shorter name for compatibility.  The specification of Ada.Calendar is in section 9.6 of the Ada 95 RM.  The part that concerns us here is shown below.  Type Duration is a fixed point type built into Ada; the delay statement discussed earlier takes an object of type Duration.

   package Ada.Calendar is
      type Time is private;
      function Clock return Time;
      function "+"(Left : Time; Right : Duration) return Time;
      function "-"(Left : Time; Right : Time)     return Duration;
      ...
   end Ada.Calendar;

Not shown are a few other operators, and subprograms to convert between type Time and the year, month, day, and number of seconds since midnight.

Let's write a program segment, using Calendar, that calls A every five seconds.  The following example is for Ada 83 as well as Ada 95:

   with Calendar; use Calendar;
   ...
   Next_Event : Time := Clock + 5.0;
   ...
   loop
      delay Next_Event - Clock;
      A;
      Next_Event := Next_Event + 5.0;
   end loop;

Note that this loop accounts for the time required to call A.  Instead of delaying 5.0, we calculate the time of the next call in Next_Event, and delay that time minus the current time, which we obtain by calling Clock.  Thus the program will go through the loop once every 5.0 seconds, even if it takes a little time to call A.  In Ada 95, we may write delay until Next_Event; which guarantees that no higher-priority task will interrupt the calculation of Next_Event - Clock, thereby causing the delay to be too long.

The - and + operators in this example all use infix functions from Calendar.

We're now ready for Outside Assignment 6! It will be much simpler than Outside Assignment 5.

< prev   next >

No comments: