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

Thread Synchronization - Semaphore

Introduction to Semaphores

• Proposed by Edsger Dijkstra, technique to manage concurrent threads by using a simple integer value which is known as a semaphore.

• A sempahore allows at most $n$$n$ ($n\ge 0$$n\ge0$) threads to enter a critical section and execute concurrently. From the functionality's perspective, a mutex is a special case of semaphore where $n$$n$ is 1. This is why mutexes are also called as binary semaphores.

  Here, $n$$n$ is referred to as the permit number. Permit number is defined by the user.

• We have an assumption that the critical section protected by a semaphore is of a special property that it can be executed by $n$$n$ number of execution units (i.e., threads) concurrently without causing any problems.

• Semaphores can be used to synchronize multiple processes running on the same machine as well as to synchronize multiple threads within a process.

Semaphore APIs

• Semaphore APIs

  xxxxxxxxxx
  18
  1
  #include <semaphore.h>
  2
  
  3
  /* declare semaphore variable */
  4
  sem_t sem;
  5
  
  6
  /* initialize the semaphore */
  7
  sem_init(sem_t *sem,  /* pointer to the semaphore to be initialized */
  8
           int pshared, /* pshared = 0 to synchronize threads, non-zero value to synchronize processes */
  9
           int permit_counter); /* should be initialized to a non-negative integer */
  10
  
  11
  /* blocking the calling thread if semaphore is not available */
  12
  sem_wait(sem_t *sem);
  13
  
  14
  /* signal the blocked thread on semaphore */
  15
  sem_post(sem_t *sem);
  16
  
  17
  /* destroy the semaphore after use */
  18
  sem_destroy(sem_t *sem);
  

  sem_wait() and sem_post() forms the core functionality of a semaphore; Allow at most $n$$n$ threads to execute concurrently in a critical section.

  1. sem_wait(sem_t *sem);

     Unconditionally decrease the permit_counter of the semaphore.

     If permit_counter < 0 after decrement, block the calling thread.

  2. sem_post(sem_t *sem);

     Unconditionally increase the permit_counter of the semaphore.

     Send signal to threads blocked on sem_wait(), if any. If there is no thread blocked on the semaphore, signal will not be sent. (See the implementation)This signal will be delivered to any thread which is blocked on the semaphore by the OS and the recipient thread of the signal will then execute sem_wait() and enter the critical section.

  When permit_counter = 1, it is called a binary semaphore which is basically the same as mutex. The only difference is that a binary semaphore can be unblocked(= sem_post()) by a different thread whereas a mutex can only be unlocked by the thread that has locked it. In other words, the order in which the threads invoke sem_wait() does not necessarily match the order in which the threads invoke sem_post(). It is indeterministic!

  My understanding on the difference between a binary semaphore and a mutex is not clear! Revisit these concepts and clarify them! (Mutex - lock/unlock, Semaphore - wait/signal)

Semaphore Demonstration

• Write a program that creates 5 threads, allows at most 2 threads to execute in the critical section concurrently. You may face the critical section by just printing some messages by the executing threads.

  xxxxxxxxxx
  87
  1
  /*
  2
   * File Name    : semaphore_hello_world.c
  3
   * Description  : C program to demonstrate the usage of a semaphore to limite the number of threads
  4
   *                running inside the critical section.
  5
   * Author       : Modified by Kyungjae Lee 
  6
   *               (Original: Abhishek Sagar - Juniper Networks)
  7
   * Date Created : 01/13/2023
  8
   */
  9
  
  10
  /*
  11
   * compile using:
  12
   * gcc -g -c semaphore_hello_world.c -o semaphore_hello_world.o
  13
   * gcc -g semaphore_hello_world.o -o semaphore_hello_world -lpthread
  14
   * 
  15
   * run using: 
  16
   * ./semaphore_hello_world
  17
   */
  18
  
  19
  #include <stdio.h>
  20
  #include <stdlib.h>
  21
  #include <pthread.h>    /* POSIX threads*/
  22
  #include <unistd.h>     /* pause(), sleep() */
  23
  #include <errno.h>      /* global variable errno */
  24
  #include <semaphore.h>  /* semaphore */
  25
  
  26
  sem_t sem;
  27
  pthread_t threads[5];
  28
  
  29
  #define PERMIT_COUNT 2
  30
  
  31
  /* A thread callback fn must have following prototypes 
  32
   * void* (*thread_fn)(void *)
  33
   */
  34
  static void* thread_fn_callback(void *arg)
  35
  {
  36
      char *thread_name = (char *)arg;
  37
  
  38
      int i;
  39
      
  40
      printf("%s attempts to enter C.S\n", thread_name);
  41
  
  42
      sem_wait(&sem);
  43
      
  44
      /* CS Begins here */
  45
      printf("%s sucessfully entered C.S\n",  thread_name);
  46
      
  47
      for (i = 0 ; i < 5; i++)
  48
      {
  49
          printf("%s executing in C.S\n", thread_name);
  50
          sleep(1);
  51
      }
  52
  
  53
      printf("%s exiting from C.S\n", thread_name);
  54
      /* CS Ends here */
  55
      
  56
      sem_post(&sem); /* analogous to 'pthread_cond_singnal()' */
  57
  
  58
      printf("%s completely exited from C.S\n", thread_name);
  59
  }
  60
  
  61
  void thread_create(pthread_t *thread_handle, void *arg)
  62
  {
  63
      int rc = pthread_create(thread_handle, NULL, thread_fn_callback, arg);
  64
      if(rc != 0)
  65
      {
  66
          printf("Error occurred, thread could not be created, errno = %d\n", rc);
  67
          exit(0);
  68
      }
  69
  }
  70
  
  71
  int main(int argc, char **argv)
  72
  {
  73
      sem_init(&sem, 0, PERMIT_COUNT);
  74
      thread_create(&threads[0], "thread0");
  75
      thread_create(&threads[1], "thread1");
  76
      thread_create(&threads[2], "thread2");
  77
      thread_create(&threads[3], "thread3");
  78
      thread_create(&threads[4], "thread4");
  79
  
  80
      int i ;
  81
      for (i = 0; i < 5; i++) 
  82
      {
  83
          pthread_join(threads[i], NULL);
  84
      }
  85
      sem_destroy(&sem);
  86
      return 0;
  87
  }
  

  xxxxxxxxxx
  30
  1
  thread0 attempts to enter C.S
  2
  thread0 sucessfully entered C.S
  3
  thread0 executing in C.S
  4
  thread3 attempts to enter C.S
  5
  thread3 sucessfully entered C.S
  6
  thread2 attempts to enter C.S
  7
  thread3 executing in C.S
  8
  thread4 attempts to enter C.S
  9
  thread1 attempts to enter C.S
  10
  thread3 executing in C.S
  11
  thread0 executing in C.S
  12
  thread3 executing in C.S
  13
  thread0 executing in C.S
  14
  thread3 executing in C.S
  15
  thread0 executing in C.S
  16
  thread3 executing in C.S
  17
  thread0 executing in C.S
  18
  thread3 exiting from C.S
  19
  thread3 completely exited from C.S
  20
  thread0 exiting from C.S
  21
  thread2 sucessfully entered C.S
  22
  thread2 executing in C.S
  23
  thread4 sucessfully entered C.S
  24
  thread4 executing in C.S
  25
  thread0 completely exited from C.S
  26
  thread2 executing in C.S
  27
  thread4 executing in C.S
  28
  thread2 executing in C.S
  29
  thread4 executing in C.S
  30
  ...
  

  Notice that at most 2 threads are executing in the critical section concurrently.

Strict Alternation (Using Semaphore)

• Strict alternation is nothing but a pattern of execution of threads.

• It is of practical significance to make a pair of threads to execute in strict alternation manner. (It is about two threads!)

• Strict alternation can be implemented using zero semaphores whose permit_counter is 0.

  xxxxxxxxxx
  2
  1
  sem_wait(&sem);     /* calling thread is immediately blocked */
  2
  sem_post(&sem);     /* blocked thread, if any, wakes up */
  

  Any thread (T2) in the system can invoke sem_post() API on the same semaphore T1 was blocked on.

• Write a program which create two threads T1 and T2. T1 thread prints odd numbers between 1 to 15. T2 prints even numbers between 2 to 15. Output should be sequential.

  xxxxxxxxxx
  7
  1
  /* T1 */
  2
  for (i = 1; i < 15; i += 2)
  3
  {
  4
      print i;
  5
      sem_post(sem0_1);
  6
      sem_wait(sem0_2);
  7
  }
  

  xxxxxxxxxx
  7
  1
  /* T2 */
  2
  for (i = 2; i < 15; i += 2)
  3
  {
  4
      sem_post(sem0_1);
  5
      print i;
  6
      sem_wait(sem0_2);
  7
  }
  

Implementation of Semaphores

• Mutex and condition variable are building blocks of semaphores.

  In fact, mutex and condition variable are building blocks for all thread synchronization data structures such as thread barriers, wait queues, thread pools, monitors, thread schedulers, etc.

• Understanding the integer variable permit_counter:

  • When permit_counter $\ge$$\ge$ 0,

    The number of threads which are allowed to enter the critical section without waiting.

  • When permit_counter $<$$\lt$ 0,

    The number of threads which are blocked from entering the critical section because the maximum allowed limit has reached.

• Interface for Semaphore

  xxxxxxxxxx
  35
  1
  /*
  2
   * File Name    : semaphore.h
  3
   * Description  : Interface for semaphore
  4
   * Author       : Modified by Kyungjae Lee (Original: Abhishek Sagar - Juniper Networks)
  5
   * Date Created : 01/13/2023
  6
   */
  7
  
  8
  #ifndef SEMAPHORE_H
  9
  #define SEMAPHORE_H
  10
  
  11
  #include <pthread.h>
  12
  
  13
  typedef struct sema_
  14
  {
  15
      int permit_counter;
  16
      pthread_cond_t cv;
  17
      pthread_mutex_t mutex;
  18
  } sema_t;
  19
  
  20
  sema_t* sema_get_new_semaphore();
  21
  void sema_init(sema_t *sema, int count);
  22
  void sema_wait(sema_t *sema);
  23
  void sema_post(sema_t *sema);
  24
  void sema_destroy(sema_t *sema);
  25
  int sema_getvalue(sema_t *sema);
  26
  
  27
  /* several texts using P & V notation to represent wait and signals */
  28
  #define P(sema) sema_wait(sema)
  29
  #define V(sema) sema_post(sema)
  30
  
  31
  /* some texts also use up and down */
  32
  #define UP(sema)    sema_wait(sema)
  33
  #define DOWN(sema)  sema_post(sema)
  34
  
  35
  #endif /* SEMAPHORE_H */
  

  The member variable mutex is used to lock and unlock the section of code where permit_counter is getting updated.

  The member variable cv is used when a thread needs to wait or block on the semaphore.

• Implementation of Semaphore

  xxxxxxxxxx
  66
  1
  /*
  2
   * File Name    : semaphore.c
  3
   * Description  : Implementation of semaphore
  4
   * Author       : Modified by Kyungjae Lee (Original: Abhishek Sagar - Juniper Networks)
  5
   * Date Created : 01/13/2023
  6
   */
  7
  
  8
  #include <stdlib.h>
  9
  #include <pthread.h>
  10
  #include <assert.h>
  11
  #include <stdbool.h>
  12
  #include "semaphore.h"
  13
  
  14
  sema_t* sema_get_new_semaphore()
  15
  {
  16
      sema_t *sema = calloc(1, sizeof(sema_t));
  17
      return sema;
  18
  }
  19
  
  20
  void sema_init(sema_t *sema, int permit_counter)
  21
  {
  22
      sema->permit_counter = permit_counter;
  23
      pthread_cond_init(&sema->cv, NULL);
  24
      pthread_mutex_init(&sema->mutex, NULL);
  25
  }
  26
  
  27
  /* without using pending signals */
  28
  void sema_wait(sema_t *sema)
  29
  {
  30
     pthread_mutex_lock(&sema->mutex);
  31
     sema->permit_counter--;
  32
     if (sema->permit_counter < 0)
  33
     {
  34
         pthread_cond_wait(&sema->cv, &sema->mutex); /* mutex will be unlocked behind the scenes */
  35
     }
  36
     pthread_mutex_unlock(&sema->mutex);
  37
  }
  38
  
  39
  void sema_post(sema_t *sema)
  40
  {
  41
      bool any_thread_waiting;
  42
      pthread_mutex_lock(&sema->mutex);
  43
  
  44
      any_thread_waiting = sema->permit_counter < 0 ? true : false;
  45
      sema->permit_counter++;
  46
  
  47
      if (any_thread_waiting)
  48
      {
  49
          pthread_cond_signal(&sema->cv); /* one of the blocked threads chosen by thew OS
  50
                                             will get the signal */
  51
      }
  52
      pthread_mutex_unlock(&sema->mutex);
  53
  }
  54
  
  55
  void sema_destroy(sema_t *sema)
  56
  {
  57
      sema->permit_counter = 0;
  58
      pthread_mutex_unlock(&sema->mutex);
  59
      pthread_cond_destroy(&sema->cv);    
  60
      pthread_mutex_destroy(&sema->mutex);
  61
  }
  62
  
  63
  int sema_getvalue(sema_t *sema)
  64
  {
  65
      return sema->permit_counter;
  66
  }
  

• To check if your own implementation of a semaphore is robust, run it with the modified version of the previous demo program.

Types of Semaphores

• Types of Semaphores:

  • Unnamed Semaphores

    Used to synchronize threads or related processes (i.e., processes that are created by fork() system call)

    We've been discussing about unnamed semaphores till now.

  • Named Semaphores

    Mainly used for synchronizing unrelated processes, but can also be used for synchronizing threads or related processes.

    Have names using which the semaphore can be uniquely identified in the system.

Strong & Weak Semaphores

• Weak Semaphore

  Whenever theoretically you can show in your solution that some thread blocked on a mutex or semaphore may never get a chance to resume its execution (Starvation), then we say that solution is lacking the property of Bounded Waiting and such a semaphore is called Weak Semaphore.

  The root cause-of the weak semaphore is the randomness of scheduling which thread to allow to enter the critical section next.

• Strong Semaphore

  We can deploy a way such that blocked threads are unblocked in a FIFO way per signal (or in any other way that can prevent the starvation), then such a semaphore is called the Strong Semaphore. Bounded Waiting is guaranteed in strong semaphores.

• Weak/strong is the topic discussed in the realm of theory because in reality, it is very rare for a starvation of threads to occur.

• Bounded waiting means that any particular thread blocked on a semaphore would have a finite amount of waiting time. It is guaranteed that at some point in time, a particular thread blocked on a semaphore will be scheduled and enter the critical section. It is a desirable property that any synchronization solution must have.

• Weak semaphores can be converted into strong semaphores by changing the policy of blocked thread selection from random to FIFO (sequel course).

• The semaphores we have dealt with so far (i.e., custom semaphore, built-in semaphore) are all "weak semaphores". Even the mutexes are "weak" in this sense since the blocked threads are randomly selected by the operating system.

References

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