Both Java and Ada provide built-in concurrency features.

The Java example below is taken from TutorialRide.com

Java Example

The Java example uses a single element buffer shared between the producer and the consumer. The shared buffer is implemented in the Shop class. The Shop class contains two private variables. The int variable materials will contain the data shared by the producer and the consumer. The boolean variable available is used to control the access to the variable materials so that the consumer can only read data when available is TRUE and the producer can only produce data when available is FALSE.

In the class Shop put method a while loop polls the available variable while the value of available is TRUE. Similarly the get method uses a while loop to poll the available variable while the value of available is FALSE. In both cases the wait() method causes the thread calling the synchronized method to suspend until the notifyAll() method awakens the suspended thread.

The Java notifyAll() method awakens all waiting threads, both producers and consumers. The awakened thread checks the value of available. If the value of the variable available matches the loop’s terminating condition the method is completed, otherwise the method again suspends upon executing wait().

Java does not provide any policy concerning which thread awakened by the call to notifyAll() will run, thus the use of multiple producers and multiple consumers will produce non-deterministic execution of the multiple threads.

The output of the Java example above is:

Ada Example

The following Ada code closely resembles the Java code in its external behavior with the exception that the Ada code implements two producers and two consumers.

Ada allows subprograms, equivalent to Java methods, to be defined within the scope of other subprograms. Similarly, Ada protected objects and tasks may be defined within a subprogram. Ada provides two kinds of subprograms; functions which always return a value and procedures which never return a value, however parameter values can be passed out of a procedure to the scope in which the procedure is called.

The entry point to an Ada program is always a procedure with no parameters. The procedure may be named whatever the programmer wants to name it. It need not be called “main”. In this case I did name it “main” for ease of understanding by Java programmers.

Ada provides protected objects and protected types as passive units of concurrency. In this case the protected object is named “buffer”.

Unlike Java, Ada clearly separates the interface specification of a protected object from its implementation. In this case the lines highlighted in blue are the protected object interface. Protected objects are allowed to have three kinds of methods used to interface with the object. The three kinds of methods are entries, procedure and functions. Entries provide read/write access to the protected object with an associated boundary condition. Procedures provide unconditional read/write access to the protected object. Function provide read-only access to the protected object. Entries and procedures implicitly implement an exclusive read/write lock on the protected object. Tasks waiting for the entry boundary condition to open are placed in a suspension queue and are allowed access to the protected object in accordance with the specified queuing policy. The default queuing policy is First-In-First-Out. Functions implicitly enforce a shared read lock on the protected object allowing multiple tasks to simultaneously call functions without encountering any race conditions.

The private part of the protected object interface specification contains the data items within the protected object. Those data items are only accessible through the entries, procedures or functions defined for the protected object. In this case the variable Num is an Integer. It will hold the value assigned by the producer and read by the consumer. The variable Empty is a Boolean initialized to True. The Empty variable is used to control whether a producer or a consumer is allowed to execute the put or get entries.

The implementation of the protected object entries is found in the protected body, highlighted above in red.

The Put entry takes an IN parameter of type Integer and executes only when Empty is True. The Put entry assigns the value in the parameter Item to the protected object’s Num variable. It then assigns false to the protected object’s Empty variable.

The Get entry takes an OUT parameter of type Integer and executes only when Empty is False. The Get entry assigns the value in Num to the parameter Item, which is passed out to the calling task. The Empty variable is then assigned True.

All the locking and queuing activities of the entries are written by the compiler and are not left as an exercise for the programmer.

The implementation of the two task types also separates the interface specification from the implementation.

Again, the task type interface specifications are highlighted in blue and the implementations are highlighted in red.

In this example each task type has a discriminant value named Id, of the subtype Positive. Ada does not have constructors like Java does. In this case the discriminant serves the purpose of a constructor, allowing a parameter within the task to be set when an instance of the task type is created.

The task body for the producer task type simply executes a “for” loop iterating through the range of values specified as 0 .. 4. Each iteration the producer calls buffer.Put(I), writing its current value of “I” to the protected object named buffer. The producer task then outputs a statement saying The producer with the Id value assigned to it through the discriminant, produced whatever value I is at this iteration. The task then delays (similar to sleep in Java) for 0.0001 seconds. Similarly, the task body for the consumer task type declares a local variable named Value of type Integer and then iterates through a “for” loop five times. Each time through the “for” loop the task calls buffer.Get(Value). Value is assigned the value read from the buffer. The task then outputs its consumer Id and the value it read, followed by delaying for 0.0001 seconds.

The rest of procedure “main” declares two producer objects and two consumer objects. The four tasks start running as soon as the program reaches the “begin” in the “main” procedure. The executable part of the “main” procedure does nothing except wait for the four tasks to complete. The “null;” statement notifies the compiler that the main procedure does nothing intentionally. In fact the main procedure simply creates and starts the tasks and then does nothing.

The output of the Ada example is:

Conclusion

While the Java example produces similar output to the Ada example, when one accounts for only one producer and one consumer, the outputs would look more chaotic in the Java example if two or more producers and two or more consumers were used. The difference is cause by the fact that tasks suspended on an Ada entry are queued in FIFO order while thread suspended due to the Java wait() method then activated through the Java notifyAll() method are activated in no particular order.

The Ada example is far less complex to write than is the Java example. A simple source line count shows the Java example to use 95 lines without using any blank lines while the Ada example uses 54 lines including many blank lines. The Java example adds extra lines as part of the class definitions for multiple classes, including the definition of constructors which Ada does not have. Furthermore the while loops needed to poll the wait() and notifyAll() activities in both the Put and Get methods of class Shop have no corresponding source lines in the Ada example because all the suspension, queuing and activation activities of the Ada program are written by the compiler and not by the programmer.

While the outputs of the two examples are superficially similar, they are not the same. The ordered output of the Ada program cannot be reliably reproduced using Java.

 A recent question on Stack Overflow concerned creation of a C program to create and print a reverse copy of a string. Thus, for example, the string “hello” would be copied to another string and would contain “olleh”.

C versions

While this is clearly a beginner level problem, the difficulties encountered by the person submitting the question illustrate how learning C can be a struggle.

The source code posted by the author of the question is:

#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <string.h>
#define ARR_SIZE 50

int main()
{
 char string[ARR_SIZE];
 printf("Enter char array!\n");
 fgets(string, ARR_SIZE, stdin);

 string[strlen(string) - 1] = '\0';
 int length = (strlen(string) - 1);
 int length2 = (strlen(string) - 1);

 printf("%s\t%d\n", string, length);

 for (int i = 0; i <= length; i++)
 {
 printf("INDEX = %d CHAR = %c\n", i, string[i]);
 }
 
 printf("%d", length2);
 char copy[ARR_SIZE];
 
 for (int i = 0; i <= length2; i++)
 {
 copy[i] = string[length];
 length--;
 }

 


 printf("\n%s", copy);
}

There are a number of beginner mistakes in this code example. One answer attempted to correct the most obvious errors with the following result:

#include <stdio.h>
#include <string.h>
// remove unneeded headers

#define ARR_SIZE 50

int main(void)
{
  char string[ARR_SIZE];
  printf("Enter char array!\n");
  fgets(string, ARR_SIZE, stdin);

  string[strlen(string) - 1] = '\0';
  // remove the -1 on the string length calculation, the NUL terminator is not
  // included in strlen's return value
  int length = strlen(string);
  // no sense in calling strlen twice
  int length2 = length;

  // fixed `length` now prints the correct length
  printf("%s\t%d\n", string, length);

  // change from <= to <. The array indices where the characters live are
  // [0, length-1].
  for (int i = 0; i < length; i++)
  {
    printf("INDEX = %d CHAR = %c\n", i, string[i]);
  }
 
  // fixed `length2` now prints the correct length
  printf("%d", length2);
  char copy[ARR_SIZE];
 
  for (int i = 0; i < length2; i++)
  {
    // last character in `string` lives at the `length`-1 index
    copy[i] = string[length-1];
    length--;
  }

  // `length2` is the index after the last char in `copy`, this needs
  // to be NUL terminated.
  copy[length2] = '\0';

  // prints the reversed string
  printf("\n%s", copy);
}

These suggestions do produce a working program, but it has some weaknesses inherent in the C language handling of strings. The biggest weakness is the effort needed to deal with determining how long the string is. C strings are terminated with a null character. The example above uses the strlen function to find the position of the null character.

A second answer tried to offer a more compact solution, although it does omit the necessary header files. The author of this example suggested that a proper solution should define and use a function. Note that this function is highly compact, uncommented, and extremely terse. In other words it contains all the elements commonly associated with C programming.

char *copyreverse(char *dest, const char *src)
{
  size_t len = strlen(src);
  const char *end = src + len - !!len;
  char *wrk = dest;
  while(len--)
    *wrk++ = *end--;
  *wrk = 0;
  return dest;
}
int main()
{
  char dest[10];
  char *src = "hello";
  printf("`%s` reversed `%s`\n", src, copyreverse(dest, src));
}

In this case we see a function named copyreverse and a function named main in the same file. In C this places the two functions in the same file scope, allowing copyreverse to be visible to the implementation of main. C does not allow a function to be implemented within the scope of another function.

This terse solution has typical C problems. The copyreverse function takes two parameters, a pointer to character named dest and a pointer to character named src. Only the programmer know that these pointers should point to the start of an array of characters and not a simple character. There is no check in the program to ensure that the dest parameter points to an array large enough to hold all the characters contained in the array pointed to by the parameter src. This failure to check sizes opens the opportunity for a buffer overflow.

Another part of the simplification of this program is its lack of ability to read the string from standard input, thus making the program unnecessarily compact.

Ada versions

Next I offer a couple of solutions created in the Ada programming language.

The first Ada example creates a function using the Ada.Strings.Unbounded package which provides an append procedure for unbounded strings. Use of unbounded strings prevents any buffer overflow problems.

with Ada.Text_IO; use Ada.Text_IO;
with Ada.Strings.Unbounded; use Ada.Strings.Unbounded;

procedure Main is
  Result : Unbounded_String := Null_Unbounded_String;
  Input : String (1 .. 80);
  Length : Natural;
begin
  Put ("Enter a string: ");
  Get_Line (Item => Input, Last => Length);
  Put_Line (Input (1 .. Length));
  for C of reverse Input (1 .. Length) loop
    Append (Result, C);
  end loop;
  Put_Line (To_String (Result));
end Main;

The Get_Line procedure reads the string from standard input and places it into a string named Input. The Get_Line function passes out the modified string as well as a parameter indicating the index of the last character of the useful information in the string. The Put_Line procedure simply writes the input data to standard output. The data to be output is in the slice of the Input variable which was filled by Put_Line.  The for loop scans through the slice of Input in reverse order, appending each value to the Unbounded_String named Result. When the loop finishes Result will contain the data in Input (1 .. Length), but in reverse order.

The final Put_Line procedure call simply converts the Unbounded_String Result to a corresponding String value and outputs that String value.

A second Ada example avoids the use of the package Ada.Strings.Unbounded and does the string copy directly to another Ada string.

with Ada.Text_IO; use Ada.Text_IO;

procedure main_2 is
   function reverse_str (src : in String) return String is
     Result : String (src'Range);
     r_idx : Positive := Result'First;
   begin
     for value of reverse src loop
       Result (r_idx) := value;
       r_idx := r_idx + 1;
     end loop;
   return Result;
  end reverse_str;

  Input : String (1 .. 80);
  Length : Natural;
begin
  Put ("enter a string: ");
  Get_Line (Input, Length);
  Put_Line (Input (1 .. Length));
  Put_Line (reverse_str (Input (1 .. Length)));
end main_2;

The function named reverse_str is defined within the procedure main_2. Reverse_str takes one String parameter named src and returns a String. Reverse_str creates a String variable named Result. Result is created to have the same index range as src, and therefore has exactly the same size as src, eliminating any possibility of overflow. The variable r_idx is an instance of the subtype Positive and is initialized to the first index value of Result. The for loop iterates through src in reverse assigning each value of src to the element in Result indexed by the variable r_idx. The variable r_idx is then incremented and the loop continues until all elements of src have been processed. Result is then returned by the function reverse_str.

The body of main_2 prompts for a string to be input from standard input, reads up to 80 characters from standard input and places the data in the variable Input. The value of the string Input (1 .. Length) is output and on the next output line the value of the reverse of Input (1 .. Length) is output.

While not as terse as the second C solution the second Ada version is highly readable and does not require the programmer to provide a destination string parameter of possibly dubious size as is required in the C program. The Ada version also does not require the src string to be scanned to determine its size followed by an obscure expression seen in the C example to deal with a possible empty string. Instead the Ada range syntax defines a range where the first index is greater than the last index to be an empty range. For instance, if the users passes an empty string to the Ada program the notation Input (1 .. Length) resolves to Input ( 1 .. 0), which is an empty string. The for loop then does not iterate through the values because the first index exceeds the last index and Result, which is created with the expression Result : String := (src’Range) is defined as an empty string. Result is returned without being modified in the for loop and no buffer overflow occurs.

The Ada versions are both simpler because of the differences between Ada strings and C strings and also because Ada arrays, of which strings are an example, can easily be sliced.

The Ada versions both avoid the possibility of array overflows while the second C version does not.

The Ada versions avoid any pointer manipulation syntax while the second C example performs all array element processing using explicit pointer manipulations.

Tasking and the Ada Rendezvous

Multiprocessing has been a part of the Ada programming language since the language was first standardized in 1983. The original version of Ada provided active concurrency objects called tasks. Today tasks are commonly implement by Ada compilers as operating system threads, but the Ada language does not depend on operating system threading to implement tasks.

The execution of an Ada program consists of the execution of one or more tasks. Each task represents a separate thread of control that proceeds independently and concurrently between the points where it interacts with other tasks. The various forms of task interaction are described in this clause, and include:

·         the activation and termination of a task;

·         a call on a protected subprogram of a protected object, providing exclusive read-write access, or concurrent read-only access to shared data;

·         a call on an entry, either of another task, allowing for synchronous communication with that task, or of a protected object, allowing for asynchronous communication with one or more other tasks using that same protected object;

·         a timed operation, including a simple delay statement, a timed entry call or accept, or a timed asynchronous select statement (see next item);

·         an asynchronous transfer of control as part of an asynchronous select statement, where a task stops what it is doing and begins execution at a different point in response to the completion of an entry call or the expiration of a delay;

·         an abort statement, allowing one task to cause the termination of another task.

Tasks can be implemented as a task type, allowing multiple identical instances of a task to be created, or as single task entities defined as members of an anonymous task type.

Definition of a task type includes declaration of all interfaces to the task type. Task interfaces, or calling points, are called task entries. Each task entry allow another task to call an instance of the task type, possibly passing data to or from the task type instance.

Rendezvous

When one task calls an entry of another task the two task synchronize to allow data to be passed from one task to the other. If task A calls an entry named set_id declared in task B with the purpose of passing an id value from task A to task B the two tasks synchronize to allow direct communication between the tasks. Task A calls the Task B entry. Task B accepts the entry call. Synchronization happens when both task are ready to process the entry. If task A calls the entry before task B accepts the entry call then task A suspends until task B is ready. Similarly, if task B accepts the entry before any task calls the entry then task B suspends until the entry is called. An entry is allowed to transfer data to or from the task calling the entry.

Table 1 Task Type Example

The task type in the example above is named Counter. Task type Counter has one entry. A task type may have multiple entries or it may have no entries.

The single entry in this example is named Set_Num. Set_Num requires a single parameter of type Integer. The “in” mode designation causes the value to be passed from the calling task to the called instance of Counter.

Each task or task type declaration must be completed with a task body. The task or task type declaration contains the declaration of the name of the task or task type as well as the declaration of all entries associated with the task or task type. The task body contains the logic implemented by the task. The task body must have the same name as its corresponding task or task type declaration.

Table 2 Task Body Example

The structure of a task body is very similar to the structure of an Ada procedure. Local variables are declared between the “is” reserved word and the “begin” reserved word. The “accept” statement performs the task’s interaction with the entry call. In this case the parameter “Val” contains the value passed from the task calling the entry. That value is copied into the local variable “Num”. The accept operation ends when the code reaches “end Set_Num”. Upon completion of the accept operation the synchronization of this task with its calling task completes and both tasks resume asynchronous execution.

Calling a Task Entry

The following example demonstrates how one task calls the entry of another task.

Table 3 Calling a Task Entry

The purpose of this simple program is to use tasks to print the digits 0 through 9 in random order. The task type counter is designed to receive a single integer value through its Set_Num entry, delay execution for a random time (in this case the time is a random fraction of milliseconds between 9 milliseconds and 1 millisecond) and then output the value of its local variable named Num. Upon completing the output operation the instance of Counter completes.

An array of Counter objects is created. The name of that array is Counters. The array is indexed by the values 0 through 9, which causes the array to have 10 instances of task type Counter. Those tasks start automatically when program execution reaches the “begin” statement of the Main procedure.

Looking back at the task body for Counter we see that the first action of the task is to call the Reset procedure for random generator, setting the random number seed to a unique value based upon the current computer clock. After resetting the random number seed the task calls the accept operator for the Set_Num entry. The task then suspends until its Set_Num entry is called.

The “for” loop in the Main procedure iterates through the array of Counter tasks, calling each one in order and passing its array index value as the number it will output. Keep in mind that the Main procedure executes in a task separate from the ten Counter tasks.

Another example of the Ada Rendezvous is shown below. This example defines an Ada package implementing parallel addition of an array of integer values. The example is implemented in three files.

Table 4 Parallel_Addition.ads

This package specification declares an unconstrained array type named Data_Array. Data_Array arrays are indexed by some set of values within the valid set of Integer values. Each element contains an Integer. An unconstrained array allows the user to pass an array of any size permitted by the computer hardware.

The type Data_Access is a reference to Data_Array.

The function Sum takes a parameter of type Data_Access so that very large arrays created on the heap may be passed to the function. The function returns a single Integer which is the sum of all the elements in the array passed to the function.

Table 5 Parallel_Addition.adb

The package body for Parallel_Addition contains the implementation of the Sum function declared in the Parallel_Addition package specification.

Within the Sum function we find the declaration of a task type name Adder. Instances of Adder will perform the parallel addition. The task type declaration for Adder includes two entries named Set and Report. The Set entry sets the minimum and maximum index values to be used by the task. The Report entry passes the total calculate by the task back to the entry’s calling task.

Two instances of Adder are created. One is named A1 and the other is named A2. Similarly two integer variables intended to hold the results of the additions are created. Those variables are named R1 and R2.

The Sum function calculated a middle value for the index values in the array passed to it as Item.

The Adder tasks begin execution when program execution reaches the “begin” of the Sum function.

The Sum function calls the Set entry for Adder A1 passing it the index values for the first index of Item and the Mid value. Similarly, the set entry for Adder A2 is passed the index value of Mid + 1 and the last index value of Item.

The Sum function immediately calls the Adder A1 Report entry to receive the value for R1, followed by calling the Adder A2 report entry to receive the value for R2. The Sum function will suspend until A1 accepts its Report entry. It will then suspend again if necessary until A2 accepts its Repot entry.

Sum returns the sum of R1 and R2.

Table 6 Parallel_Addition_Test.adb

The program Parallel Addition Test creates an array containing 2,147,483,647 elements. The object of this test is to calculate an average time for each addition operation using the Parallel_Addition package. A large array provides a statistically solid number for the average time.

In this case all the elements of the array are initialized to 1 so that the addition will not result in an integer overflow. This also gives a good check of the addition, since the correct result is 2,147,483,647.

The program captures the clock time in the variable Start, calls the Sum function, then captures the time in the variable Stop. The difference between the two times is the approximate time used to sum the array.

The addition result along with the elapsed time and the average time per addition operation are reported.

The result of an example run is:

Table 7 Example Parallel_Addition_Test Output

People who prefer programming language syntax derived from the C language have often argued that the Ada language is verbose because it uses entire words rather than punctuation.

Of course, not everything in Ada takes more lines of code or more typing than the equivalent program in C or C++. For instance, the following C++ program is taken from the CodesCracker website. Its purpose is to convert a user input of a hexadecimal value into the corresponding decimal value.

An Ada program handling the same input and results in the same output is:

Ada has the built-in capability to handle literal numbers represented by base 2 through base 16. The base 16 value FF is represented as 16#FF#. Ada accepts either upper or lower case representation of the hexadecimal values A through F. The program simply appends the 16# to the entered hexadecimal digits and then appends # to the end of the string. The integer’value built in attribute converts a string representation of an integer to its corresponding integer value.

The message created in response to the exception Constraint_Error is raised if the user enters a value more than 2^32 or if one of the digits is not in the range of 0 through 9 or A through F.

In this case the Ada program appears to be far less verbose than the C++ program.

package Barber_Shop is
   task Barber is
      entry Close_Shop;
   end Barber;

   task Customers;
end Barber_Shop;

with Ada.Text_IO;               use Ada.Text_IO;
with Ada.Numerics.Float_Random; use Ada.Numerics.Float_Random;

package body Barber_Shop is
   Seed : Generator;

   type Num_Seats is range 0 .. 3;
   protected Shop is
      function Is_Open return Boolean;
      function Shop_Empty return Boolean;
      entry Take_Seat;
      entry Serve_Customer;
      procedure Close_Shop;
   private
      Shop_Open      : Boolean   := True;
      Occupied_Seats : Num_Seats := 0;
   end Shop;

   protected body Shop is
      function Is_Open return Boolean is
      begin
         return Shop_Open;
      end Is_Open;

      function Shop_Empty return Boolean is
      begin
         return Occupied_Seats = 0;
      end Shop_Empty;

      entry Take_Seat when Shop_Open and then Occupied_Seats < Num_Seats'Last
      is
      begin
         Occupied_Seats := Occupied_Seats + 1;
      end Take_Seat;

      entry Serve_Customer when Occupied_Seats > 0 is
      begin
         Occupied_Seats := Occupied_Seats - 1;
      end Serve_Customer;

      procedure Close_Shop is
      begin
         Shop_Open := False;
      end Close_Shop;

   end Shop;

   ------------
   -- Barber --
   ------------

   task body Barber is
      procedure Cut_Hair is
      begin
         Put_Line ("Luigi is serving a customer.");
         delay Duration (Random (Seed) * 3.0);
      end Cut_Hair;

   begin
      loop
         select
            accept Close_Shop;
            Put_Line ("Luigi is closing the shop");
            Shop.Close_Shop;
         else
            if Shop.Is_Open then
               if Shop.Shop_Empty then
                  Put_Line ("Luigi is sleeping.");
               end if;
               Shop.Serve_Customer;
               Cut_Hair;
            else
               while not Shop.Shop_Empty loop
                  Shop.Serve_Customer;
                  Cut_Hair;
               end loop;
               exit;
            end if;
         end select;
      end loop;
   end Barber;

   ---------------
   -- Customers --
   ---------------

   task body Customers is
   begin
      loop
         delay Duration (Random (Seed) * 6.0);
         select
            Shop.Take_Seat;
            Put_Line ("A customer took a seat");
         else
            if Shop.Is_Open then
               Put_Line ("A customer left because all the seats were taken.");
            else
               Put_Line ("A customer left because the shop is closed.");
               exit;
            end if;
         end select;
      end loop;
   end Customers;
begin
   Reset (Seed);
end Barber_Shop;

with Barber_Shop; use Barber_Shop;
procedure Main is
begin
   delay 60.0;
   Barber.Close_Shop;
end Main;

Classic Producer-Consumer Pattern

• Single Producer with Multiple Consumers
• Multiple Producers with Single Consumer
• Multiple Producers with Multiple Consumers

Single Producer Multiple Consumer Pattern

Multiple Consumer Single Producer Pattern

Multiple Producer Multiple Consumer Pattern

Producer-Consumer Implemented Using Ada

Ada Tasks

Task Entries

Select statements

Protected Methods

• Procedures
  
• Entries
  
• Functions
  

Protected Procedures

Protected Entries

Protected Functions

Ada Producer-Consumer Example

Determinism

Non-Deterministic Example

Deterministic Examples

Race conditions

Avoiding race conditions

Interleaving task access to a shared object

• ·         Is_Empty – This function returns true if the stack is empty and false if it is not empty
• ·         Size – A function returning number of elements currently contained by the stack
• ·         Top – A function returning the top element of a stack that is not empty
• ·         Push – Push a data element onto the stack
• ·         Pop – A procedure that pops the top element off the stack, passing the popped element out as a parameter
• ·         Clear – A procedure that empties the stack
• ·         Display – A procedure that displays the current contents of the stack

Unbounded Stack

Bounded Stack

Using the unbounded stack package

Using the bounded stack package

CWE-129: Improper Validation of Array Index

Description

Demonstrative Examples

Example 1 : Java language

Example 2: Java language

Example 3: C language

Example 4: C language

Potential Mitigations using the Ada language

Mitigation 1: