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

Thread Synchronization - Recursive Mutex/Lock

Introduction to Recursive Mutex

• A regular mutex, which has already been locked cannot be locked again by the same thread. Any attempt for a thread to lock a mutex that has already been locked by itself leads to deadlock.

• A recursive mutex works just like a regular mutex except that it can be locked by the same thread multiple times. A thread has to unlock the mutex as many times as it has locked it.

• Defining a recursive mutex using POSIX Standard APIs:

  xxxxxxxxxx
  6
  1
  pthread_mutex_t mutex;
  2
  pthread_mutexattr attr;
  3
  
  4
  pthread_mutexattr_init(&attr);
  5
  pthread_mutexattr_settype(&attr, PTHREAD_MUTEX_RECURSIVE);
  6
  pthread_mutex_init(&mutex, &attr);
  

  Everything is the same as when you are defining a regular mutex, except that for a recursive mutex, you need to specify its property as a recursive mutex by passing PTHREAD_MUTEX_RECURSIVE to the function pthread_mutexattr_settype() as a second argument.

Use Case of Recursive Mutex

• Recursive mutexes simply things in the scenario where there is a possibility that a function could be invoked from another function which locks the mutex that will be locked again by the invoked function.

  For example, let's say a developer wrote the following function:

  xxxxxxxxxx
  6
  1
  void delete_student_record(student_db, stud_rec)
  2
  {
  3
      pthread_mutex_lock(&student_db.mutex);
  4
      student_db.delete(student_db, stud_rec);
  5
      pthred_mutex_unlock(&student_db.mutex);
  6
  }
  

  And, after a few months, a new developer writes the following function without knowing the implementation of delete_student_record():

  xxxxxxxxxx
  13
  1
  void remove_failed_student(student_db, int agg_limit)
  2
  {
  3
      stud_rec_t *stud_rec;
  4
      pthread_mutex_lock(&student_db.mutex);  /* locking the mutex */
  5
      for_each_rec(student_db, stud_rec)
  6
      {
  7
          if (stud_rec->agg_limit < agg_limit)
  8
          {
  9
              delete_student_record(student_db, stud_rec); /* includes mutex locking mechanism */
  10
          }
  11
      }
  12
      pthread_mutex_unlock(&student_db.mutex);
  13
  }
  

  In this case, invoking remove_failed_student() function is likely to cause a deadlock! However, had this mutex been defined as a recursive mutex, no issue would have risen.

Implementation of Recursive Mutex

• Being able to implement our own recursive mutexes will be helpful when writing a multi-threaded program using a language that does not support recursive mutexes. Try to make the interface and the functionalities of your own recursive mutex as similar to the POSIX pthread library as possible.

• Requirements:

  • If thread T1 has locked a recursive mutex (RM), any other thread T2 must block upon an attempt to lock the RM.

  • T2 must resume execution only when T1 (holding a lock), releases all locks on RM.

  • RM, like a regular Mutex, must guarantee the mutual exclusion.

  • Owning thread must invoke as many unlock calls as lock calls to release the RM.

  • Assert if any thread tries to unlock an unlocked RM.

• Interface for Recursive Mutex

  xxxxxxxxxx
  30
  1
  /*
  2
   * File Name    : recursive_mutex.h
  3
   * Description  : Interface for recursive mutex
  4
   * Author       : Modified by Kyungjae Lee (Original: Abhishek Sagar - Juniper Networks)
  5
   * Date Created : 01/14/2023
  6
   */
  7
  
  8
  #ifndef RECURSIVE_MUTEX
  9
  #define RECURSIVE_MUTEX
  10
  
  11
  #include <pthread.h>
  12
  #include <stdint.h>
  13
  #include <stdbool.h>
  14
  
  15
  typedef struct rec_mutex_
  16
  { 
  17
      uint16_t n;                 /* mumber of times self-lock is allowed */
  18
      pthread_t locking_thread;   /* pthread id of the thread which owns this mutex */
  19
      pthread_cond_t cv;          /* a CV to make threads block */
  20
      pthread_mutex_t state_mutex;/* a Mutex to manupulate the state of this structure 
  21
                                     in a mutually exclusive way */
  22
      uint16_t n_waiting;         /* number of threads waiting for the grant of this mutex lock */
  23
  } rec_mutex_t;
  24
  
  25
  void rec_mutex_init(rec_mutex_t *rec_mutex) ;
  26
  void rec_mutex_lock(rec_mutex_t *rec_mutex);
  27
  void rec_mutex_unlock(rec_mutex_t *rec_mutex);
  28
  void rec_mutex_destroy(rec_mutex_t *rec_mutex);
  29
  
  30
  #endif /* RECURSIVE_MUTEX */
  

• Implementation of Recursive Mutex

  xxxxxxxxxx
  121
  1
  /*
  2
   * File Name    : recursive_mutex.c
  3
   * Description  : Implementation of recursive mutex
  4
   * Author       : Modified by Kyungjae Lee (Original: Abhishek Sagar - Juniper Networks)
  5
   * Date Created : 01/14/2023
  6
   */
  7
  
  8
  #include <stdio.h>
  9
  #include <assert.h>
  10
  #include "recursive_mutex.h"
  11
  
  12
  void rec_mutex_init(rec_mutex_t *rec_mutex)
  13
  {
  14
      rec_mutex->n = 0;
  15
      rec_mutex->locking_thread = 0;
  16
      pthread_cond_init(&rec_mutex->cv, NULL);
  17
      pthread_mutex_init(&rec_mutex->state_mutex, NULL);
  18
      rec_mutex->n_waiting = 0;
  19
  }
  20
  
  21
  void rec_mutex_lock(rec_mutex_t *rec_mutex)
  22
  {
  23
      /* to make modifying rec_mutex operation an atomic operation */
  24
      pthread_mutex_lock(&rec_mutex->state_mutex);
  25
      
  26
      /* case 1 : when rec_mutex has NOT yet been locked */
  27
      if (rec_mutex->n == 0)
  28
      {
  29
          assert(rec_mutex->locking_thread == 0); /* double-check if locking_thread == 0 */
  30
          rec_mutex->n = 1;
  31
          rec_mutex->locking_thread = pthread_self();
  32
          pthread_mutex_unlock(&rec_mutex->state_mutex);
  33
          return;
  34
      }
  35
  
  36
      /* case 2 : when rec_mutex has already been locked by itself */
  37
      if (rec_mutex->locking_thread == pthread_self())
  38
      {
  39
          assert(rec_mutex->n);   /* double-check if rec_mutex > 0 */
  40
          rec_mutex->n++;
  41
          pthread_mutex_unlock(&rec_mutex->state_mutex);
  42
          return;
  43
      }
  44
  
  45
      /* case 3 : when rec_mutex has been locked by some other thread */
  46
      while (rec_mutex->locking_thread && rec_mutex->locking_thread != pthread_self())
  47
      {
  48
          /* simply make the current thread block on this rec_mutex */
  49
          rec_mutex->n_waiting++;
  50
          pthread_cond_wait(&rec_mutex->cv, &rec_mutex->state_mutex); /* this thread will 
  51
              wakeup once its condition variable receives the signal */
  52
          rec_mutex->n_waiting--;
  53
      }
  54
  
  55
      /* case 3 cont'd - now locking rec_mutex is available for the current thread */
  56
      assert(rec_mutex->n == 0);
  57
      assert(rec_mutex->locking_thread == 0);
  58
  
  59
      rec_mutex->n = 1;
  60
      rec_mutex->locking_thread = pthread_self();
  61
      pthread_mutex_unlock(&rec_mutex->state_mutex);
  62
  }
  63
  
  64
  void rec_mutex_unlock(rec_mutex_t *rec_mutex)
  65
  {
  66
      pthread_mutex_lock(&rec_mutex->state_mutex);
  67
      
  68
      /* case 1 : when rec_mutex has NOT yet been locked 
  69
         (unlocking an already unlocked rec_mutex) */
  70
      if (rec_mutex->n == 0)  
  71
      {
  72
          assert(rec_mutex->locking_thread == 0);
  73
          assert(0);
  74
      }
  75
  
  76
      /* case 2 : when rec_mutex has already been locked by itself */
  77
      if (rec_mutex->locking_thread == pthread_self())
  78
      {
  79
          assert(rec_mutex->n);   /* double-check if rec_mutex > 0 */
  80
          rec_mutex->n--;
  81
  
  82
          if (rec_mutex->n > 0)
  83
          {
  84
              pthread_mutex_unlock(&rec_mutex->state_mutex);
  85
              return;
  86
          }
  87
  
  88
          /* is there any blocked threads waiting to obtain rec_mutex? */
  89
          if (rec_mutex->n_waiting)
  90
          {
  91
              /* if so, send a signal for one among those blocked (waiting) threads */
  92
              pthread_cond_signal(&rec_mutex->cv);
  93
          }
  94
  
  95
          rec_mutex->locking_thread = 0;
  96
          pthread_mutex_unlock(&rec_mutex->state_mutex);
  97
          return;
  98
      }
  99
  
  100
      /* case 3 : when rec_mutex has been locked by some other thread */
  101
      while (rec_mutex->locking_thread && rec_mutex->locking_thread != pthread_self())
  102
      {
  103
          /* why would a thread want to unlock the rec_mutex that belongs to someone else? */
  104
          assert(0);  /* terminate the program! */
  105
      }
  106
  }
  107
  
  108
  void rec_mutex_destroy(rec_mutex_t *rec_mutex)
  109
  {
  110
      /* the following asserts are important because destroying a rec_mutex when there is any
  111
         thread holding it or waiting to obtain it will results in an undefined behavior
  112
         (imagine a thread waiting for a signal on the condition variable that does not even
  113
         exist) */
  114
      assert(!rec_mutex->n); /* there must be no threads still holding rec_mutex */
  115
      assert(!rec_mutex->locking_thread); /* there must be no threads still holding rec_mutex */
  116
      assert(!rec_mutex->n_waiting); /* there must be no threads waiting to obtain rec_mutex */
  117
      
  118
      /* only if above conditions have successfully been met, destory rec_mutex */ 
  119
      pthread_mutex_destroy(&rec_mutex->state_mutex);
  120
      pthread_cond_destroy(&rec_mutex->cv);
  121
  }
  

  Notice that assert()s have been placed so that the program terminates as soon as it encounters a bug. Feel free to insert any many assert()s as possible so that bugs can be found as soon as possible!

  L46: while() instead of if() to prevent spurious wakeups.

  It is the developer's responsibility to only invoke rec_mutex_destroy() in a situation that everything is safe to be destroyed.

References

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