Ensuring the Mutual Exclusion of Shared Variables

Ensuring the Mutual Exclusion of Shared Variables
in Pthreads

Prof. David Bernstein
James Madison University

Computer Science Department

bernstdh@jmu.edu

Review

Threads:
- A mechanism that permits a single process to perform multiple tasks concurrently
Shared Variables:
- Threads share the initialized data, uninitialized data, and heap segments

The Good and the Bad

The Good:
- Because threads share the "global" data segments it is easy for them to share information
The Bad:
- Multiple threads can modify the value of a variable concurrently
- Some threads can be modifying the value of a variable while others are retrieving the value

The Bad (cont.)

unixexamples/mutexes/threaded_counter_race.c

        #include <pthread.h>
#include <stdlib.h>
#include <stdio.h>

static volatile long global_counter = 0;


static void*
counter(void *arg)
{
  long   i, limit, local_counter;

  limit = *((long *) arg);
  for (i=0; i<limit; i++)
    {
      local_counter = global_counter;
      ++local_counter;
      global_counter = local_counter;

      // Try replacing the three statements above with the following
      //++global_counter;
    }
  
  return NULL;
}



int
main(int argc, char *argv[])
{
  long        limit;
  pthread_t  thread_a, thread_b;
  
  if (argc <= 1) limit = 100;
  else           limit = atol(argv[1]);

  // Start two threads counting
  pthread_create(&thread_a, NULL, counter, &limit);
  pthread_create(&thread_b, NULL, counter, &limit);

  // Wait for both threads to terminate
  pthread_join(thread_a, NULL);
  pthread_join(thread_b, NULL);

  // Display the result
  printf("Expected: %ld\n", limit*2);
  printf("Actual:   %ld\n", global_counter);
  exit(0);
}

The Bad (cont.)

Counting to 200:
- thread_a probably finishes before thread_b starts so the expected and actual are the same
Counting to 20,000,000:
- The two threads each get some time on the processor so the lack of coordination causes a failure

The Bad (cont.)

The Race Condition:
- Read-Modify-Write
The Implications:
- thread_a can read global_counter, assign its value to local_counter, modify local_counter, and then get swapped-off before it writes global_counter
- thread_b can then read global_counter (which contains an incorrect value)

The Bad (cont.)

Is This Example Contrived?
- A little, but just to make the race condition obvious
An Observation:
- On some architectures ++global_counter is not atomic meaning the same race condition exists

Coordination

An Important Property of Some Coordination Protocols:
- Mutual exclusion - it is possible to exclude multiple parties from using a resource at the same time
What's Needed:
- We must ensure that threads use shared variables in a mutually exclusive way

Ensuring Mutual Exclusion

The Mechanism:
- pthread_mutex_t variables
States:
- "Locked" and "Unlocked"
Ownership:
- A thread that "locks" (a.k.a. "acquires") a pthread_mutex_t variable becomes the "owner" of that variable
- Only the "owner" of a pthread_mutex_t variable can "unlock" (a.k.a. "release") it
- A thread that attempts to "lock" a "locked" pthread_mutex_t will block until it is "unlocked"

Using "Mutexes" (i.e., pthread_mutex_t Variables)

Pattern:
- Use one mutex for each resource that needs to be shared
Protocol:
- Lock the mutex for the shared resource
- Use the shared resource (in the critical section of the code) for as little time as possible
- Unlock the mutex

Using "Mutexes" (cont.)

Power/Authority:
- A mutex is not like a permission -- it doesn't prevent a resource from being used
Implication:
- Threads must cooperate (i.e., agree to follow the protocol)

Creating Mutexes

Step 1 - Allocation:
- Allocate memory for the mutex either statically in the initialized data segment, automatically (on the stack), or dynamically (on the heap)
Step 2 - Initialization:
- Assign attributes to the mutex

Creating Mutexes (cont.)

Static Allocation and Initialization:
- static pthread_mutex_t example = PTHREAD_MUTEX_INITIALIZER
Dynamic Initialization:
- Must be used for mutexes that are dynamically allocated (on the heap) or automatically allocated (on the stack)
- Can be used for mutexes that are statically allocated when non-default attributes are needed

State Transitions

Initial State:
- A mutex is initially unlocked/unowned
Transitions:
- A mutex can transition from being unlocked/unowned to locked/owned
- A mutex can transition from being locked/owned to unlocked/unowned

Locking: pthread_mutex_lock()

int pthread_mutex_lock(pthread_mutex_t *mutex)

Purpose:

Lock (i.e., acquire or become the owner of) a mutex

Details:

`mutex`	The mutex
Return	0 on success; positive error number on error

#include <pthread.h>

Attempting to Lock a Locked Mutex

By the thread that owns the mutex:
- The thread deadlocks (unless the thread's type is PTHREAD_MUTEX_ERROR_CHECK or PTHREAD_MUTEX_RECURSIVE, neither of which is the default)
By another thread:
- The thread blocks until the mutex is unlocked by the owning thread (at which point some indeterminate blocked thread will unblock and become the owner)

Unlocking: pthread_mutex_unlock()

int pthread_mutex_unlock(pthread_mutex_t *mutex)

Purpose:

Unlock (i.e., release) a mutex

Details:

`mutex`	The mutex
Return	0 on success; positive error number on error

#include <pthread.h>

Unlock Errors

Attempting to Unlock an Unlocked Mutex:
- EINVAL
Attempting to Unlock a Mutex Owned by Another Thread:
- EPERM

A Corrected Example

unixexamples/mutexes/threaded_counter_mutex.c

        #include <pthread.h>
#include <stdlib.h>
#include <stdio.h>

static volatile long     global_counter = 0;
static pthread_mutex_t  counter_lock = PTHREAD_MUTEX_INITIALIZER;

static void*
counter(void *arg)
{
  long   i, limit, local_counter;

  limit = *((long *) arg);
  for (i=0; i<limit; i++)
    {
      pthread_mutex_lock(&counter_lock);
      
      // Start of Critical Section
      local_counter = global_counter;
      ++local_counter;
      global_counter = local_counter;
      // End of Critical Section

      pthread_mutex_unlock(&counter_lock);
    }
  
  return NULL;
}



int
main(int argc, char *argv[])
{
  long       limit;
  pthread_t  thread_a, thread_b;
  
  if (argc <= 1) limit = 100;
  else           limit = atol(argv[1]);

  // Start two threads counting
  pthread_create(&thread_a, NULL, counter, &limit);
  pthread_create(&thread_b, NULL, counter, &limit);

  // Wait for both threads to terminate
  pthread_join(thread_a, NULL);
  pthread_join(thread_b, NULL);

  // Display the result
  printf("Expected: %ld\n", limit*2);
  printf("Actual:   %ld\n", global_counter);
  exit(0);
}

Performance

Costs:
- Locking and unlocking a mutex both take time
Coarse Measures of Performance:
- time can be used to obtain both the amount of time spent executing in user mode and the amount of time spend executing in kernel mode

Performance (cont.)

Two Threads with Race Condition (10,000,000 iterations each):
- User 0.328s; Kernel 0.000s
Two Threads with Mutexes (10,000,000 iterations each):
- User 3.088s; Kernel 4.176s
One Thread with Mutexes (20,000,000 iterations):
- User 0.464s; Kernel 0.000s
Main Thread (20,000,000 iterations):
- User 0.120s; Kernel 0.000s

Variants of pthread_mutex_lock()

pthread_mutex_trylock() :
- Does not block; returns EBUSY if the mutex is locked
- Can be used to check if a mutex is locked
pthread_mutex_timedlock() :
- Places a limit on the blocking time; returns ETIMEDOUT if the lock can't be acquired within the limit

Avoiding Deadlocks

Use a Hierarchy:
- Have all threads lock mutexes in the same order
Back Off:
- Lock the first mutex and then use pthread_mutex_trylock() on the others. If there are any errors release all of the locks, delay a random amount of time, and try again.

Dynamic Initialization: pthread_mutex_init()

int pthread_mutex_init(pthread_mutex_t *mutex, const pthread_mutexattr_t *attr)

Purpose:

Initialize a mutex

Details:

`mutex`	The mutex to be initialized
`attr`	The attributes to use (of NULL for the default attributes)
Return	0 on success; a positive error number on error

#include <pthread.h>

Mutex Attributes

Linux:
- Only supports one attribute (the "type"), which determines what happens when a thread attempts to lock a mutex it owns (and all of the kinds are non-portable)
SUSv3:
- Has three "types", PTHREAD_MUTEX_NORMAL does not detect self-deadlock, PTHREAD_MUTEX_ERRORCHECK provides error checking, and PTHREAD_MUTEX_RECURSIVE uses a lock count

Destruction

Which Mutexes?
- Those that are automatically or dynamically allocated
When?
- When the mutex is unlocked (and no longer needed)
- Before freeing the memory (for dynamically allocated) or before the "host function" returns (for automatically allocated)

Destruction (cont.): pthread_mutex_destroy()

int pthread_mutex_destroy(pthread_mutex_t *mutex)

Purpose:

Indicate that a mutex will no longer be used

Details:

`mutex`	The mutex to be destroyed
Return	0 on success; a positive error number on error

#include <pthread.h>