Mutual Exclusion for Shared Variables

• Using pthread_create and pthread_join calls, we can create concurrent tasks. These tasks work together to manipulate data and accomplish a given task. When multiple threads attempt to manipulate the same data item, the results can often be incoherent if proper care is not taken to synchronize them.
• Consider the following code fragment being executed by multiple threads. The variable my_cost is thread-local and best_cost is a global variable shared by all threads.

  1   /* each thread tries to update variable best_cost as follows */ 
  2   if (my_cost < best_cost) 
  3       best_cost = my_cost;
  

• To understand the problem with shared data access, let us examine one execution instance of the above code fragment.
  • Assume that there are two threads, the initial value of best_cost is 100, and the values of my_cost are 50 and 75 at threads t1 and t2, respectively.
  • If both threads execute the condition inside the if statement concurrently, then both threads enter the then part of the statement. Depending on which thread executes first, the value of best_cost at the end could be either 50 or 75.
  • There are two problems here: the first is the non-deterministic nature of the result; second, and more importantly, the value 75 of best_cost is inconsistent in the sense that no serialization of the two threads can possibly yield this result.
  • This is an undesirable situation, sometimes also referred to as a race condition (so called because the result of the computation depends on the race between competing threads).
• The aforementioned situation occurred because the test-and-update operation illustrated above is an atomic operation; i.e., the operation should not be broken into sub-operations.
• Furthermore, the code corresponds to a critical segment; i.e., a segment that must be executed by only one thread at any time. Many statements that seem atomic in higher level languages such as C may in fact be non-atomic; for example, a statement of the form $global_count += 5$ may comprise several assembler instructions and therefore must be handled carefully.
• Threaded APIs provide support for implementing critical sections and atomic operations using mutex-locks (mutual exclusion locks).
  • Mutex-locks have two states: locked and unlocked. At any point of time, only one thread can lock a mutex lock.
  • A lock is an atomic operation generally associated with a piece of code that manipulates shared data. To access the shared data, a thread must first try to acquire a mutex-lock.
  • If the mutex-lock is already locked, the process trying to acquire the lock is blocked. This is because a locked mutex-lock implies that there is another thread currently in the critical section and that no other thread must be allowed in.
  • When a thread leaves a critical section, it must unlock the mutex-lock so that other threads can enter the critical section.
  • All mutex-locks must be initialized to the unlocked state at the beginning of the program.
• The function pthread_mutex_lock can be used to attempt a lock on a mutex-lock.

  1   int 
  2   pthread_mutex_lock ( 
  3       pthread_mutex_t *mutex_lock);
  

• A call to this function attempts a lock on the mutex-lock mutex_lock. (The data type of a mutex_lock is predefined to be pthread_mutex_t.)
• If the mutex-lock is already locked, the calling thread blocks; otherwise the mutex-lock is locked and the calling thread returns. A successful return from the function returns a value 0. Other values indicate error conditions such as deadlocks.
• On leaving a critical section, a thread must unlock the mutex-lock associated with the section. If it does not do so, no other thread will be able to enter this section, typically resulting in a deadlock. The Pthreads function pthread_mutex_unlock is used to unlock a mutex-lock.

  1   int 
  2   pthread_mutex_unlock ( 
  3       pthread_mutex_t *mutex_lock);
  

• On calling this function, in the case of a normal mutex-lock, the lock is relinquished and one of the blocked threads is scheduled to enter the critical section.
• The specific thread is determined by the scheduling policy. There are other types of locks (other than normal locks).
• If a programmer attempts a pthread_mutex_unlock on a previously unlocked mutex or one that is locked by another thread, the effect is undefined.
• We need one more function before we can start using mutex-locks, namely, a function to initialize a mutex-lock to its unlocked state. The Pthreads function for this is pthread_mutex_init.

  1   int 
  2   pthread_mutex_init ( 
  3       pthread_mutex_t *mutex_lock, 
  4       const pthread_mutexattr_t *lock_attr);
  

  This function initializes the mutex-lock mutex_lock to an unlocked state. The attributes of the mutex-lock are specified by lock_attr. If this argument is set to NULL, the default mutex-lock attributes are used (normal mutex-lock).
• Computing the minimum entry in a list of integers
  • A threaded program to compute the minimum of a list of integers. The list is partitioned equally among the threads.
    • The size of each thread's partition is stored in the variable partial_list_size.
    • The pointer to the start of each thread's partial list is passed to it as the pointer list_ptr.

    1   #include <pthread.h> 
    2   void *find_min(void *list_ptr); 
    3   pthread_mutex_t minimum_value_lock; 
    4   int minimum_value, partial_list_size; 
    5 
    6   main() { 
    7       /* declare and initialize data structures and list */ 
    8       minimum_value = MIN_INT; 
    9       pthread_init(); 
    10      pthread_mutex_init(&minimum_value_lock, NULL); 
    11 
    12      /* initialize lists, list_ptr, and partial_list_size */ 
    13      /* create and join threads here */ 
    14  } 
    15 
    16  void *find_min(void *list_ptr) { 
    17      int *partial_list_pointer, my_min, i; 
    18      my_min = MIN_INT; 
    19      partial_list_pointer = (int *) list_ptr; 
    20      for (i = 0; i < partial_list_size; i++) 
    21          if (partial_list_pointer[i] < my_min) 
    22              my_min = partial_list_pointer[i]; 
    23      /* lock the mutex associated with minimum_value and 
    24      update the variable as required */ 
    25      pthread_mutex_lock(&minimum_value_lock); 
    26      if (my_min < minimum_value) 
    27          minimum_value = my_min; 
    28      /* and unlock the mutex */ 
    29      pthread_mutex_unlock(&minimum_value_lock); 
    30      pthread_exit(0); 
    31  }
    

  • In this example, the test-update operation for minimum_value is protected by the mutex-lock minimum_value_lock.
  • Threads execute pthread_mutex_lock to gain exclusive access to the variable minimum_value. Once this access is gained, the value is updated as required, and the lock subsequently released. Since at any point of time, only one thread can hold a lock, only one thread can test-update the variable.
• Producer-consumer work queues
  • A common use of mutex-locks is in establishing a producer-consumer relationship between threads.
  • The producer creates tasks and inserts them into a work-queue. The consumer threads pick up tasks from the task queue and execute them.
  • Let us consider a simple instance of this paradigm in which the task queue can hold only one task (in a general case, the task queue may be longer but is typically of bounded size).
  • A simple (and incorrect) threaded program would associate a producer thread with creating a task and placing it in a shared data structure and the consumer threads with picking up tasks from this shared data structure and executing them. However, this simple version does not account for the following possibilities:
    • The producer thread must not overwrite the shared buffer when the previous task has not been picked up by a consumer thread.
    • The consumer threads must not pick up tasks until there is something present in the shared data structure.
    • Individual consumer threads should pick up tasks one at a time.
  • To implement this, we can use a variable called task_available. If this variable is 0, consumer threads must wait, but the producer thread can insert tasks into the shared data structure task_queue.
  • If task_available is equal to 1, the producer thread must wait to insert the task into the shared data structure but one of the consumer threads can pick up the task available.
  • All of these operations on the variable task_available should be protected by mutex-locks to ensure that only one thread is executing test-update on it.

    1   pthread_mutex_t task_queue_lock; 
    2   int task_available; 
    3 
    4   /* other shared data structures here */ 
    5 
    6   main() { 
    7       /* declarations and initializations */ 
    8       task_available = 0; 
    9       pthread_init(); 
    10      pthread_mutex_init(&task_queue_lock, NULL); 
    11     /* create and join producer and consumer threads */ 
    12  } 
    13 
    14  void *producer(void *producer_thread_data) { 
    15      int inserted; 
    16      struct task my_task; 
    17      while (!done()) { 
    18          inserted = 0; 
    19          create_task(&my_task); 
    20          while (inserted == 0) { 
    21              pthread_mutex_lock(&task_queue_lock); 
    22              if (task_available == 0) { 
    23                  insert_into_queue(my_task); 
    24                  task_available = 1; 
    25                  inserted = 1; 
    26              } 
    27              pthread_mutex_unlock(&task_queue_lock); 
    28          } 
    29      } 
    30  } 
    31 
    32  void *consumer(void *consumer_thread_data) { 
    33      int extracted; 
    34      struct task my_task; 
    35      /* local data structure declarations */ 
    36      while (!done()) { 
    37          extracted = 0; 
    38          while (extracted == 0) { 
    39              pthread_mutex_lock(&task_queue_lock); 
    40              if (task_available == 1) { 
    41                  extract_from_queue(&my_task); 
    42                  task_available = 0; 
    43                  extracted = 1; 
    44              } 
    45              pthread_mutex_unlock(&task_queue_lock); 
    46          } 
    47          process_task(my_task); 
    48      } 
    49  }
    

  • In this example, the producer thread creates a task and waits for space on the queue. This is indicated by the variable task_available being 0.
  • The test and update of this variable as well as insertion and extraction from the shared queue are protected by a mutex called task_queue_lock.
  • Once space is available on the task queue, the recently created task is inserted into the task queue and the availability of the task is signaled by setting task_available to 1.
  • Within the producer thread, the fact that the recently created task has been inserted into the queue is signaled by the variable inserted being set to 1, which allows the producer to produce the next task.
  • Irrespective of whether a recently created task is successfully inserted into the queue or not, the lock is relinquished. This allows consumer threads to pick up work from the queue in case there is work on the queue to begin with.
  • If the lock is not relinquished, threads would deadlock since a consumer would not be able to get the lock to pick up the task and the producer would not be able to insert its task into the task queue.
  • The consumer thread waits for a task to become available and executes it when available. As was the case with the producer thread, the consumer relinquishes the lock in each iteration of the while loop to allow the producer to insert work into the queue if there was none.
  • Overheads of Locking;
    • Locks represent serialization points since critical sections must be executed by threads one after the other.
    • Encapsulating large segments of the program within locks can, therefore, lead to significant performance degradation. It is important to minimize the size of critical sections.
    • For instance, in the above example, the create_task and process_task functions are left outside the critical region, but insert_into_queue and extract_from_queue functions are left inside the critical region.
    • The former is left out in the interest of making the critical section as small as possible.
    • The insert_into_queue and extract_from_queue functions are left inside because if the lock is relinquished after updating task_available but not inserting or extracting the task, other threads may gain access to the shared data structure while the insertion or extraction is in progress, resulting in errors.
    • It is therefore important to handle critical sections and shared data structures with extreme care.
  • Facilitating Locking Overheads
    • It is often possible to reduce the idling overhead associated with locks using an alternate function, pthread_mutex_trylock.
    • This function attempts a lock on mutex_lock. If the lock is successful, the function returns a zero. If it is already locked by another thread, instead of blocking the thread execution, it returns a value EBUSY. This allows the thread to do other work and to poll the mutex for a lock.
    • Furthermore, pthread_mutex_trylock is typically much faster than pthread_mutex_lock on typical systems since it does not have to deal with queues associated with locks for multiple threads waiting on the lock.

      1   int 
      2   pthread_mutex_trylock ( 
      3       pthread_mutex_t *mutex_lock);
      

• Finding k matches in a list
  • We consider the example of finding k matches to a query item in a given list. The list is partitioned equally among the threads. Assuming that the list has $n$ entries, each of the $p$ threads is responsible for searching $n/p$ entries of the list.

    1   void *find_entries(void *start_pointer) { 
    2 
    3       /* This is the thread function */ 
    4 
    5       struct database_record *next_record; 
    6       int count; 
    7       current_pointer = start_pointer; 
    8       do { 
    9           next_record = find_next_entry(current_pointer); 
    10          count = output_record(next_record); 
    11      } while (count < requested_number_of_records); 
    12  } 
    13 
    14  int output_record(struct database_record *record_ptr) { 
    15      int count; 
    16      pthread_mutex_lock(&output_count_lock); 
    17      output_count ++; 
    18      count = output_count; 
    19      pthread_mutex_unlock(&output_count_lock); 
    20 
    21      if (count <= requested_number_of_records) 
    22          print_record(record_ptr); 
    23      return (count); 
    24  }
    

  • This program segment finds an entry in its part of the database, updates the global count and then finds the next entry.
  • If the time for a lock-update count-unlock cycle is t1 and the time to find an entry is t2, then the total time for satisfying the query is $(t1 + t2)*n_{max}$, where $n_{max}$ is the maximum number of entries found by any thread.
  • If t1 and t2 are comparable, then locking leads to considerable overhead. This locking overhead can be handled by using the function pthread_mutex_trylock.
  • Each thread now finds the next entry and tries to acquire the lock and update count. If another thread already has the lock, the record is inserted into a local list and the thread proceeds to find other matches.
  • When it finally gets the lock, it inserts all entries found locally thus far into the list (provided the number does not exceed the desired number of entries).

    1   int output_record(struct database_record *record_ptr) { 
    2       int count; 
    3       int lock_status; 
    4       lock_status = pthread_mutex_trylock(&output_count_lock); 
    5       if (lock_status == EBUSY) { 
    6           insert_into_local_list(record_ptr); 
    7           return(0); 
    8       } 
    9       else { 
    10          count = output_count; 
    11          output_count += number_on_local_list + 1; 
    12          pthread_mutex_unlock(&output_count_lock); 
    13          print_records(record_ptr, local_list, 
    14                requested_number_of_records - count); 
    15          return(count + number_on_local_list + 1); 
    16      } 
    17  }
    

  • Notice that if the lock for updating the global count is not available, the function inserts the current record into a local list and returns.
  • If the lock is available, it increments the global count by the number of records on the local list, and then by one (for the current record). It then unlocks the associated lock and proceeds to print as many records as are required using the function print_records.
  • The time for execution of this version is less than the time for the first one on two counts: First, as mentioned, the time for executing a pthread_mutex_trylock is typically much smaller than that for a pthread_mutex_lock. Second, since multiple records may be inserted on each lock, the number of locking operations is also reduced.