Friday, July 21, 2023

Threads of Confusion

Many programming languages support concurrent behavior through the creation of threads and the explicit manipulation of semaphores, locks or mutexes. The C language seems to have initiated this approach to handling concurrency.

C example

The following example of using a mutex with thread comes from C Program to Show Thread Interface and Memory Consistency Errors – GeeksforGeeks

1       // C program to use a mutex to avoid memory consistency

2       // errors

3       #include <pthread.h>

4       #include <stdio.h>

5       #include <stdlib.h>

6

7       // Global variable that will be shared among threads

8       int shared_counter = 0;

9

10       // Mutex to protect the shared counter

11       pthread_mutex_t shared_counter_mutex

12       = PTHREAD_MUTEX_INITIALIZER;

13

14       // Function that will be executed by each thread

15       void* thread_function(void* thread_id)

16       {

17               // Get the thread ID

18               long tid = (long)thread_id;

19

20               // Lock the mutex to protect the shared counter

21               pthread_mutex_lock(&shared_counter_mutex);

22

23               // Increment the shared counter

24               shared_counter++;

25

26               // Print the thread ID and the updated value of the

27               // shared counter

28               printf("Thread %ld: shared_counter = %d\n", tid,

29                             shared_counter);

30

31               // Unlock the mutex

32               pthread_mutex_unlock(&shared_counter_mutex);

33

34               // Return NULL to indicate successful execution of the

35               // thread

36               return NULL;

37   }

38

39       int main(int argc, char* argv[])

40       {

41               // Check if the number of arguments is correct

42               if (argc != 2) {

43                       printf("Usage: %s <number_of_threads>\n", argv[0]);

44                       exit(EXIT_FAILURE);

45       }

46

47               // Get the number of threads to create from the command

48               // line arguments

49               int num_threads = atoi(argv[1]);

50

51               // Create an array of pthread_t structures to store the

52               // thread IDs

53               pthread_t* threads = (pthread_t*)malloc(

54                       num_threads * sizeof(pthread_t));

55

56               // Create the specified number of threads

57               for (int i = 0; i < num_threads; i++) {

58                       int status = pthread_create(

59                               &threads[i], NULL, thread_function, (void*)i);

60                       if (status != 0) {

61                               printf("Error: pthread_create() returned error "

62                                             "code %d\n",

63                                             status);

64                               exit(EXIT_FAILURE);

65           }

66       }

67

68               // Wait for all threads to finish execution

69               for (int i = 0; i < num_threads; i++) {

70                       int status = pthread_join(threads[i], NULL);

71                       if (status != 0) {

72                               printf("Error: pthread_join() returned error "

73                                             "code %d\n",

74                                             status);

75                               exit(EXIT_FAILURE);

76           }

77       }

78

79               // Free the memory allocated for the thread IDs

80               free(threads);

81

82               // Print the final value of the shared counter

83               printf("Final value of shared_counter: %d\n",

84                             shared_counter);

85

86               // Return success

87               return 0;

88   }

The C threading model uses the pthread library to create threads. The behavior of each created thread is controlled by the function passed to the thread as part of the pthread_create function parameter list. First an array of pthread_t structures is created:

53               pthread_t* threads = (pthread_t*)malloc(

54                       num_threads * sizeof(pthread_t));

Next, the Id number of each thread is created as the function named thread_function is passed to each element of the thread as a parameter to the pthread_create function:

57               for (int i = 0; i < num_threads; i++) {

58                       int status = pthread_create(

59                               &threads[i], NULL, thread_function, (void*)i);

60                       if (status != 0) {

61                               printf("Error: pthread_create() returned error "

62                                             "code %d\n",

63                                             status);

64                               exit(EXIT_FAILURE);

65           }

66       }

The third parameter to the pthread_create command is the function passed to the newly created thread. The fourth argument is the parameter passed to the function passed to the thread. Not only is the thread function parameter passed as the fourth argument to the pthread_create function, it is also cast to a pointer to void. This bit of syntax can be confusing because the value being passed is not a pointer, but rather an int.

Let's now look inside the function named thread_function, but before that, let's look at the creation of the pthread_mutex used to control access to the shared counter.

10       // Mutex to protect the shared counter

11       pthread_mutex_t shared_counter_mutex

12       = PTHREAD_MUTEX_INITIALIZER;

Yes, the pthread_mutex_t instance used to control access to the shared counter is itself a shared instance of a type. You might also see that the shared_counter_mutex is only loosely connected to the shared_counter integer variable. That loose connection is a voluntary connection not enforced by any syntax in the C pthreads library.

The thread_function is defined as:

14       // Function that will be executed by each thread

15       void* thread_function(void* thread_id)

16       {

17               // Get the thread ID

18               long tid = (long)thread_id;

19

20               // Lock the mutex to protect the shared counter

21               pthread_mutex_lock(&shared_counter_mutex);

22

23               // Increment the shared counter

24               shared_counter++;

25

26               // Print the thread ID and the updated value of the

27               // shared counter

28               printf("Thread %ld: shared_counter = %d\n", tid,

29                             shared_counter);

30

31               // Unlock the mutex

32               pthread_mutex_unlock(&shared_counter_mutex);

33

34               // Return NULL to indicate successful execution of the

35               // thread

36               return NULL;

37   }

The thread function must explicitly lock the shared_counter mutex, then increment the shared_counter, then output the current value of the shared_counter and finally unlock the shared_counter_mutex.

A major source of confusion

The order of the locking modifying and unlocking the mutex is critical. The shared_counter knows nothing of these locks. The pthread_mutex_t has no syntactical connection to the shared_counter. On the other hand, failing to lock, perform operations and then unlock the mutex will result in semantic failures which prevent the mutex from properly locking the shared_counter and then unlocking the shared counter after the operations are completed. Even worse, there is no syntax in the C pthread library prohibiting a thread from simply accessing the shared_counter while completely ignoring the mutex lock and unlock behaviors.

Further program issues

The remainder of the program calls pthread_join, forcing the main thread to wait until all the pthreads have completed before continuing to execute its sequence of instructions.

68               // Wait for all threads to finish execution

69               for (int i = 0; i < num_threads; i++) {

70                       int status = pthread_join(threads[i], NULL);

71                       if (status != 0) {

72                               printf("Error: pthread_join() returned error "

73                                             "code %d\n",

74                                             status);

75                               exit(EXIT_FAILURE);

76           }

77       }

It is important to understand that the pthread_join function called for each thread can fail and return failure status.

Once the pthreads have completed the program frees all the pointers in the array of pointers to pthread_t that were created to create the array of threads. This is done because it is always correct to free dynamically allocated memory when that memory is no longer needed in the program.

While this action is not particularly confusing, it is yet another detail that should be explicitly implemented.

Ada Example

The Ada programming language has tasking, which is roughly equivalent to threads, built into the core language since the first Ada language standard in 1983. In the 1995 standard protected types were added to the core language, which allow asynchronous communication between tasks. There are no special Ada libraries to implement tasking or protected types.

A protected type or protected object is protected against inappropriate simultaneous access to a shared data structure. A protected type or object is built very much in the philosophy of Object Oriented Programming inasmuch as the protected object has programmer-defined behaviors, however the locking and unlocking of the protected object is performed implicitly by the object itself and not through explicit lock and unlock methods called by the task accessing the protected object.

There are three kinds of protected methods.

  • Protected procedures – Protected procedures control an unconditional exclusive read-write lock on the protected object. The task calling the protected procedure can access the protected object whenever the object is unlocked.

  • Protected entries – Protected entries control a conditional exclusive read-write lock on the protected object. The calling task can only execute the entry when its boundary condition evaluates to True and only then can the task implicitly acquire the exclusive read-write lock.

  • Protected functions – Protected functions control an unconditional shared read lock on the protected object. This allows multiple tasks to simultaneously read from the protected object at the same time, but prevents any task to execute any procedure or entry while tasks are calling protected functions.

The following Ada example creates a protected object implementing the shared counter. The protected object in this example implements one procedure and one function. The source code for this program is:

1       with Ada.Text_IO;         use Ada.Text_IO;

2       with Ada.Integer_Text_IO; use Ada.Integer_Text_IO;

3

4       procedure Main is

5             Num_Tasks : Positive;

6

7             -- protected object shared by all the tasks

8             protected counter is

9                   procedure update (The_Count : out Natural);

10                   function get_value return Natural;

11             private

12                   count : Natural := 0;

13             end counter;

14

15             protected body counter is

16                   procedure update (The_Count : out Natural) is

17                   begin

18                         count     := count + 1;

19                         The_Count := count;

20                   end update;

21                   function get_value return Natural is

22                   begin

23                         return count;

24                   end get_value;

25             end counter;

26

27             -- Define the task type

28             task type thread is

29                   entry set_id (Id : in Positive);

30             end thread;

31

32             task body thread is

33                   Me       : Positive;

34                   My_Count : Natural;

35             begin

36                   -- accept the set_id entry call from the main task

37                   accept set_id (Id : in Positive) do

38                         Me := Id;

39                   end set_id;

40

41                   counter.update (My_Count);

42                   Put_Line ("Task" & Me'Image & ": counter =" & My_Count'Image);

43             end thread;

44

45       begin

46             Put ("Enter the number of tasks to create: ");

47             Get (Num_Tasks);

48

49             -- declare an inner block in which all the tasks will execute

50             -- the inner block will only complete after all tasks have completed

51             declare

52                   -- create an array of thread objects

53                   pool : array (1 .. Num_Tasks) of thread;

54             begin

55                   for I in pool'Range loop

56                         -- set the id number of each thread object

57                         pool (I).set_id (I);

58                   end loop;

59             end;

60

61      -- output the total after all threads have completed

62      Put_Line

63        ("The final value of the shared counter:" &

64         Natural'Image (counter.get_value));

65

66   end Main;

Ada allows functions, procedures, protected objects and task types to be declared within any function, procedure or task type. This means all items declared in this program are completely local to this program and not “static” as are multiple functions created in the same file in C.

Ada variables are declared by stating the name of the variable, followed by a colon, followed by the type of the variable. This is opposite the order of declaring variables in C where the type is listed first followed by the variable name.

5             Num_Tasks : Positive;

The variable name is Num_Tasks. The type is Positive, which is a pre-defined subtype of the Ada Integer type. Integer is equivalent to the C int type. Positive is an Integer with a minimum possible value of 1 and a maximum possible value of Integer'Last, which is the same as MAX_INT in C. This variable is used to contain the number of tasks the user specifies during the execution of the program.

The protected object named counter is declared in two parts. Protected objects are always declared in two parts. The protected specification defines the public view of the protected methods along with a private view of the data elements in the protected object. The protected body contains the definition of the protected methods, and is not visible to any task calling the protected object.

The protected specification for the counter protected object is:

8             protected counter is

9                   procedure update (The_Count : out Natural);

10                   function get_value return Natural;

11             private

12                   count : Natural := 0;

13             end counter;

There are two methods for this protected object. The procedure named update has one parameter which passes a value of type Natural out to the calling task. Natural is a predefined subtype of Integer with a minimum value of 0. The function named get_value returns a value of the subtype Natural.

In the private section of the protected specification one data element is declared. It is a variable named count. The type of the variable is Natural and it is initialized to 0.

The protected body for the counter protected object is:

15             protected body counter is

16                   procedure update (The_Count : out Natural) is

17                   begin

18                         count     := count + 1;

19                         The_Count := count;

20                   end update;

21                   function get_value return Natural is

22                   begin

23                         return count;

24                   end get_value;

25             end counter;

The update procedure increments count and passes its current value out through the parameter named The_Count.

The function get_value simply returns the value of count. The Ada compiler will issue an error message if the programmer attempts to modify the count data member of the protected object within the execution of the get_value function. Functions are read-only methods in a protected object.

The procedure update implicitly implements a read-write lock and the function get_value implicitly implements a read lock.

The task type named thread is defined in two parts. The first part, the task specification, defines that name of the task type and the direct interfaces to the task type. In this case one task entry is defined. That entry is used to set the task ID.

28             task type thread is

29                   entry set_id (Id : in Positive);

30             end thread;

The task entry implements a direct synchronous communication channel to each instance of the thread type. The entry synchronization scheme is called a Rendezvous. The word "rendezvous" is a French word meaning "a meeting at an agreed time and place". A task calling another task's entry is will suspend until the task declaring the entry accepts the entry call. Similarly, a task accepting an entry will suspend until another task calls that entry. Once both the task calling the entry and the task accepting the entry are in this state for an overlapping time period any data specified in the entry specification is passed between the calling task and the called task. Once the entry has completed both tasks continue to execute concurrently.

The behavior of the task type is defined in the task body.

32             task body thread is

33                   Me       : Positive;

34                   My_Count : Natural;

35             begin

36                   -- accept the set_id entry call from the main task

37                   accept set_id (Id : in Positive) do

38                         Me := Id;

39                   end set_id;

40

41                   counter.update (My_Count);

42                   Put_Line ("Task" & Me'Image & ": counter =" & My_Count'Image);

43             end thread;

The task body declared two local variables. Each instance of the task type has unique instances of these two variables.

The first action taken by the thread task is to accept the set_id entry, passing the Id value from a calling task to this task. The accept statement assigns the value of Id to the task's local variable named Me. Task entries implement a Rendezvous behavior. The thread task will wait at the accept statement until its entry is called by another task. Once the value is passed to the thread task both tasks will the resume concurrent behavior.

The thread task calls the protected object's update procedure, using its local variable My_Count to receive the current value of the counter protected object. Finally, the thread task simply outputs the value it received from the counter.update procedure.

The next “begin” begins the execution of the Main task.

45       begin

46             Put ("Enter the number of tasks to create: ");

47             Get (Num_Tasks);

48

49             -- declare an inner block in which all the tasks will execute

50             -- the inner block will only complete after all tasks have completed

51             declare

52                   -- create an array of thread objects

53                   pool : array (1 .. Num_Tasks) of thread;

54             begin

55                   for I in pool'Range loop

56                         -- set the id number of each thread object

57                         pool (I).set_id (I);

58                   end loop;

59             end;

60

61      -- output the total after all threads have completed

62      Put_Line

63        ("The final value of the shared counter:" &

64         Natural'Image (counter.get_value));

65

66   end Main;

The Main task prompts the user for the number of tasks to create and reads the number entered by the user.

An inner block is created starting at the “declare” reserved word. That inner block has a declarative section in which an array of thread tasks, equal in number to the value entered by the user, is created. The tasks in the array named pool begin executing immediately. Their first responsibility is to accept the set_id entry, so each task waits until its set_id entry is called.

The “for” loop iterates through each element in the pool array assigning the element's index value as the ID for the task.

Immediately after accepting its ID number each task executes counter.update and then outputs the value of the counter passed back through the counter.update procedure.

The inner block will only complete when all the tasks created within the block complete. This produces the same effect as the “join” command in the C example.

After the inner block completes the Main task calls the counter.get_value function and displays the final value of the shared counter. Completion of the inner block automatically frees the array of task objects which were created on the stack at the start of the inner block. No explicit loop to free the task elements is needed or even possible.

Conclusion

While the two programs above achieve the same behavior dealing with allowing multiple threads or tasks to update a shared counter, the C solution contains more opportunities for programmer confusion and error. It also requires a lot more coding by the programmer than the Ada solution.

No comments:

Post a Comment

Comparison of three algorithms for summing an array of integers

This article shares a comparison of the time taken to sum an array of integers. This article tests three algorithms for summing the array. •...