Home | Projects | Notes > Multi-Threading (POSIX Threads) > Thread Synchronization - Mutex

Thread Synchronization - Mutex

Introduction to Mutex

• Mutex is a thread synchronization construct/tool which provides mutual exclusion while a critical section is being access by multiple threads concurrently.

• Analogy:

  Mutex is like a key to a locker and whomever wants to access the locker needs to have the key. Whoever that does not have the key cannot access the locker and has to wait till it obtains the key. Whoever that is accessing the locker needs to handover the key when done accessing the locker.

  Here,

  • Locker = Critical section

  • Whoever = Threads

  • Key = Mutex

• Basic POSIX APIs for Mutex:

  xxxxxxxxxx
  5
  1
  pthread_mutex_t mutex;          /* create mutex */
  2
  
  3
  pthread_mutex_lock(&mutex);     /* enter critical section */
  4
  /* critical section */
  5
  pthread_mutex_unlock(&mutex);   /* leave critical section */
  

See "POSIX APIs for Mutex" section below for all the relevant APIs.

Mutex Rules

• Whichever thread unlocks the Mutex shall be able to enter the critical section.

• If a thread tries to lock an already locked Mutex, the thread turns into blocking state waiting for the Mutex to unlock. Multiple threads may be blocked by the same Mutex. In this case, the OS will decide which thread will gain access to the critical section next depending on several factors such as thread priority, OS scheduling policy, etc.

• When a thread exits the critical section, it MUST unlock the Mutex.

• A thread must not intentionally die while holding the Mutex lock. If so, that Mutex becomes unusable forever.

• If a thread attempts to double lock the same Mutex, it will be self-deadlocked.

  xxxxxxxxxx
  2
  1
  pthread_mutex_lock(&mutex); /* lock */
  2
  pthread_mutex_lock(&mutex); /* attempt to lock the same lock again  */
  

• Mutexes must be unlocked in a LIFO order (Recommended).

  xxxxxxxxxx
  5
  1
  pthread_mutex_lock(&mutex1);
  2
  pthread_mutex_lock(&mutex2);
  3
  /* critical section */
  4
  pthread_mutex_unlock(&mutex2);
  5
  pthread_mutex_unlock(&mutex1);
  

• Use of Mutex causes threads to block and unblock. The more the blocking and unblocking of threads, the more the scheduling work overhead on the OS, the poorer the application performance will become.

  The bigger the size of a critical section, the longer the threads would have to wait in blocking state, the poorer the application performance will become.

Two Types of Mutex Locking

• Code locking

• Object locking

Code Locking (Static Locking)

• Code locking is used to protect a section of code against the concurrent thread unsafe access. In this case, Mutex is defined at source file level.

  Code locking structure:

  xxxxxxxxxx
  10
  1
  static pthread_mutex_t mutex;
  2
  
  3
  foo()
  4
  {
  5
      ...
  6
      pthread_mutex_lock(&mutex);
  7
      /* critical section */
  8
      pthread_mutex_unlock(&mutex);
  9
      ...
  10
  }
  

  Code locking example:

  xxxxxxxxxx
  11
  1
  char global_buffer[256];    /* shared resource */
  2
  static pthread_mutex_mutex_t mutex;
  3
  
  4
  void pkt_receive(char *pkt, int pkt_size)
  5
  {
  6
      pthread_mutex_lock(&mutex);
  7
      memset(global_buffer, 0, sizeof(global_buffer));
  8
      memcpy(global_buffer_pkt, pkt_size);
  9
      forward_pkt(global_buffer, pkt_size);
  10
      pthread_mutex_unlock(&mutex);
  11
  }
  

Object Locking (Run-time Locking)

• Object locking is used to protect an object (e.g., data structure) rather than a section of code against the concurrent thread unsafe access. In this case, Mutex is owned by the object (i.e., one of the members of the object).

  Object locking structure:

  xxxxxxxxxx
  8
  1
  foo()
  2
  {
  3
      ...
  4
      pthread_mutex_lock(&object->mutex);
  5
      /* critical section */
  6
      pthread_mutex_unlock(&object->mutex);
  7
      ...
  8
  }
  

  Object locking example:

  xxxxxxxxxx
  8
  1
  void delete_node_from_list(list l, int n)
  2
  {
  3
      pthread_mutex_lock(&l->mutex);      /* locking an object only */
  4
      node_t *node = search_node(l, n);
  5
      remove_node(node);
  6
      free(node);
  7
      pthread_mutex_unlock(&l->mutex);    /* unlocking an object only */
  8
  }
  

• A thread will block other threads ONLY when they are trying to access to an object that it is currently accessing. Otherwise, the same section of code does not have to be protected.

  For example, if a thread T1 is accessing a linked linked list to delete an element, why should it stop another thread from deleting a node from a binary tree that is completely independent from the linked list T1 is accessing?

  In such a situation, using the code locking will only degrade the application performance.

• When object locking technique is used, a section of code itself can be executed concurrently (single-core) or simultaneously (multi-core) by the threads if the threads are accessing the different objects.

POXIS APIs for Mutex

• Mutex APIs and generic structure:

  xxxxxxxxxx
  13
  1
  /* declaration */
  2
  pthread_mutex_t mutex;
  3
  
  4
  /* initialization */
  5
  pthread_mutex_init(&mutex, NULL);
  6
  
  7
  /* locking & unlocking */
  8
  pthread_mutex_lock(&mutex);
  9
      /* critical section */
  10
  pthread_mutex_unlock(&mutex);
  11
  
  12
  /* destruction */
  13
  pthread_mutex_destroy(&mutex);
  

• Note carefully that Mutex must NEVER be memcpy()ed. It will lead to an undefined behavior!

  You should NEVER try to use memcpy() to move a data structure from on memory location to another if it has a Mutex as its member.

Challenge

• Problem statement:

  Witness the undefined behavior without mutual exclusion. Fix it using Mutex!

  The thread T1 is continuously calculating the sum of the elements of a global array arr whose elements are {1, 2, 3, 4, 5}, and the T2 is continuously swapping the first and the last element of the array. When you run this program, you'll see the sum displaying 11, 15 or 19 in a seemingly random fashion. This is happening because T1 and T2 are not synchronized, and therefore T1 happens to be calculating the sum on a four different snapshots caused by T2's swapping operation; {1, 2, 3, 4, 1}, {1, 2, 3, 4, 5}, {5, 2, 3, 4, 5}, {5, 2, 3, 4, 1}.

  xxxxxxxxxx
  117
  1
  /*
  2
   * File Name    : critical_section_problem.c
  3
   * Description  : C program to demonstrate the critical section problem
  4
   * Author       : Modified by Kyungjae Lee 
  5
   *               (Original: Abhishek Sagar - Juniper Networks)
  6
   * Date Created : 01/09/2023
  7
   */
  8
  
  9
  /*
  10
   * compile using:
  11
   * gcc -g -c critical_section_problem.c -o critical_section_problem.o
  12
   * gcc -g critical_section_problem.o -o critical_section_problem -lpthread
  13
   * 
  14
   * run using: 
  15
   * ./critical_section_problem
  16
   */
  17
  
  18
  #include <stdio.h>
  19
  #include <stdlib.h>
  20
  #include <pthread.h> /* POSIX threads*/
  21
  #include <unistd.h>  /* pause(), sleep() */
  22
  #include <errno.h>   /* errno */
  23
  #include <assert.h>
  24
  
  25
  int arr[] = { 1, 2, 3, 4, 5};
  26
  
  27
  void print_array()
  28
  {
  29
      int i = 0;
  30
      int arr_size = sizeof(arr)/sizeof(arr[0]);
  31
  
  32
      for ( ; i < arr_size -1; i++)       
  33
          printf("%d ", arr[i]);
  34
      
  35
      printf("%d\n", arr[i]);
  36
  }
  37
  
  38
  /* A thread callback fn must have the following prototype 
  39
     void* (*thread_fn)(void*) */
  40
  static void* thread_fn_callback_sum(void *arg) 
  41
  {
  42
      int i;
  43
      int sum;
  44
      
  45
      int arr_size = sizeof(arr)/sizeof(arr[0]);
  46
  
  47
      while (1)
  48
      {
  49
          sum = 0;
  50
          i = 0;
  51
          
  52
          while (i < arr_size) 
  53
          {
  54
              sum += arr[i];
  55
              i++;
  56
          }
  57
          
  58
          printf("sum = %d\n", sum);
  59
          //print_array();
  60
      }
  61
  }
  62
  
  63
  static void* thread_fn_callback_swap(void *arg) 
  64
  {
  65
      int temp;
  66
      int arr_size = sizeof(arr)/sizeof(arr[0]);
  67
  
  68
      while (1)
  69
      {
  70
          temp = arr[0];  
  71
          arr[0] = arr[arr_size -1];
  72
          arr[arr_size-1] = temp; 
  73
          //printf("swap :\n");
  74
          //print_array();
  75
      }
  76
  }
  77
  
  78
  void sum_thread_create() 
  79
  {
  80
      /* opaque object, dont bother about its internal members */
  81
      pthread_t pthread1;
  82
  
  83
      int rc = pthread_create(&pthread1, NULL, thread_fn_callback_sum, NULL);
  84
      
  85
      if (rc != 0) 
  86
      {
  87
          printf("Error occurred, thread could not be created, errno = %d\n", rc);
  88
          exit(0);
  89
      }
  90
  }
  91
  
  92
  void swap_thread_create() 
  93
  {
  94
      /* opaque object, dont bother about its internal members */
  95
      pthread_t pthread2;
  96
  
  97
      int rc = pthread_create(&pthread2, 
  98
                     NULL, 
  99
                     thread_fn_callback_swap,
  100
                     NULL);
  101
      if (rc != 0)
  102
      {
  103
          printf("Error occurred, thread could not be created, errno = %d\n", rc);
  104
          exit(0);
  105
      }
  106
  }
  107
  
  108
  int main(int argc, char *argv[])
  109
  {
  110
      sum_thread_create();
  111
      swap_thread_create();
  112
  
  113
      /*  Allow main thread to exit, while other threads are still running */
  114
      pthread_exit(0);
  115
      
  116
      return 0;
  117
  }
  

• Solution:

  xxxxxxxxxx
  1
  1
  /* write your code here */
  

   

References

Sagar, A. (2022). Part A - Multithreading & Thread Synchronization - Pthreads [Video file]. Retrieved from https://www.udemy.com/course/multithreading_parta/