• Introduction
• Semaphore API’s
• Semaphore operations
  • Initialize a semaphore (sem_init() API)
  • wait operation (sem_wait() API)
  • Signal operation (sem_post() API)
  • Destroy a semaphore (sem_destroy() API)
  • Get the semaphore value (sem_getvalue() API)
• Types of semaphore
  • Binary semaphore
  • Counting semaphore
• Producer and consumer problem
• Binary semaphore vs counting semaphore
• Use case of semaphore
• Relevant posts

Introduction

• A semaphore is a synchronization mechanism where the execution of one thread is controlled by another thread.
• Since it need not be acquired and released by the same thread, hence can be used as signaling mechanism that is for event notification.
• A thread that is waiting on a semaphore variable is signaled by other thread and is woken up.
• This object is manipulated by two operations: wait and signal by using two routines sem_wait() and sem_post() respectively.
• Wait decrements the value of semaphore and blocks if the value goes negative.
• signal increments the value of semaphore and wakes one waiting thread out of many(if).
• There are two types of semaphore: Binary and Counting Semaphore.

Generic syntax:

/* Declare a semaphore variable */
sem_t sem_var;

/* wait operation on semaphore */
sem_wait (&sem_var);
    Critical Section(CS) code
/* signal operation on semaphore */
sem_post (&sem_var);

/* Destroy the semaphore */
sem_destroy (&sem_var);

Semaphore API:

/* Declare a semaphore variable */
sem_t sem_var;

/* Initialize a semaphore variable */
sem_init (sem_t *sem_var, int pshared, unsigned int val);

/* Decrement or wait operation */
sem_wait (sem_t *sem_var);

/* Increment or signal operation */
sem_post (sem_t *sem_var);

/* Destroy the semaphore */
sem_destroy (sem_t *sem_var);

/* Get the value of a semaphore */
sem_getvalue (sem_t *sem_var, int *var);

Declaring a Semaphore variable:

sem_t sem_var;

Initialize a semaphore:

int sem_init (sem_t *sem_var, int pshared, unsigned int val);

• Theint sem_init (sem_t *sem_var, int pshared, unsigned int val); first parameter is the pointer the semaphore variable which need to be initialized.
• The second parameter determines whether the semaphore is local to the current process or can be shared among current process. Its values is 0 and 1 respectively.
• The third parameter is the value of the semaphore variable.
• The return value is 0 on success and non zero for errors.

#include <semaphore.h>
#include <errno.h>

sem_t sem_var;
/* Initialize a semaphore local to the current process */
int ret = sem_init (&sem_var, 0, 1);
if (ret) {
  printf("\n Semaphore initialization failed %s\n, strerror(errno));
  exit (EXIT_FAILURE);
}

Wait operation:

int sem_wait (sem_t *sem_var);

• This operation decrements the value of semaphore pointed by sem_var by 1.
• If the value of semaphore is greater than zero, then the decrements proceeds, and the function return immediately.
• If the semaphore currently has the value zero, then the call blocks until signal operation is performed and value rises above zero or a signal handler interrupts the call.
• It return 0 on success and non zero in case of failure.

Signal Operation:

int sem_post (sem_t *sem_var);

• This operation increments the value of semaphore by 1 and if there are one or more threads waiting, wake one.
• It return 0 on success and non zero in case of failure.

Destroy Operation:

int sem_destroy (sem_t *sem_var);

• This function destroys the semaphore at the address pointed to by sem_var;
• This releases any resources held by the semaphore.
• Only a semaphore that has been initialized by sem_init(3) should be destroyed using sem_destroy().
• If attempt is made to destroy a semaphore for which some thread is waiting,will result an error.
• It return 0 on success and non zero in case of failure.

Fetch Operation:

int sem_getvalue (sem_t *sem_val, int *variable_to_store);

• This operation is used the fetch the value of the semaphore variable.
• It places the current value of the semaphore pointed to sem_var into the integer pointed to by variable_to_store.

sem_t sem_var;
int status;
sem_init (&sem_var, 0 , 1);
sem_getvalue (&sem_var, &status);
printf("\n Semaphore initial value:  %d\n", status);

sem_wait (&sem_var);
sem_getvalue (&sem_var, &status);
printf("\n Semaphore value after wait operation: %d\n", status);

sem_post (&sem_var);
sem_getvalue (&sem_var, &status);
printf("\n Semaphore value after signal operation: %d\n", status);

sem_destroy (&sem_var);

Diag-1: Semaphore Operations

Binary Semaphore

• A Binary semaphore can only have 0 or 1 as its values.
• It has a waiting queue where only one thread can be placed, so it can either be full or empty.
• Binary semaphore cannot ensure mutual exclusion, thus this is not the same as mutex.

Working of a Binary Semaphore:
This can be understood by analyzing a problem of parent and child process

• Parent thread waits till the child terminates that is once the child finishes, a signal is sent to the parent to continue.
• This signal can be given with the help of semaphore operations.
• POSIX API pthread_join() makes the parent wait until the child process terminates.
• pthread_join() is a spinning call and wastes CPU cycle in doing so.

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

sem_t sem_var;

void thr_join()
{
        /* Parent calling wait */
        sem_wait(&sem_var);
}

void *child (void *arg)
{
        printf("\n Child execution done\n");
        sem_post(&sem_var);
}

int main()
{
        pthread_t th_id;
        sem_init (&sem_var, 0 , 0);
        int res = pthread_create(&th_id, NULL, child, NULL);
        if(res)
        {
                printf ("\n Thread creation failed: %s\n", strerror(res));
                exit(0);
        } 
        thr_join();
        printf("\n Parents execution is done\n");
        return 0; 
}

Output:

[aprakash]$ gcc binary_semaphore.c -lpthread
[aprakash@wtl-lview-6 thread]$ ./a.out 

 Child execution done
 Parents execution is done

Binary Semaphore cannot ensures Mutual exclusion:

• In the case of semaphore, the thread does not take ownership, that is semaphore variable locked by one thread can be signaled by another thread and is unlocked.
• This is not the case in the mutex, the thread that has locked the mutex becomes its current owner and remains until the same thread has unlocked it.
• Because of this, a semaphore cannot ensure mutual exclusion.

sem_t sem_var =1;
sem_wait(&sem_var);
Critical Section(CS);
sem_post(&sem_var);

• Thread T1 calls wait() and decrement the semaphore variable to 0 and enter the CS.
• Just imagine a case where thread T2 calls signal on the same variable and increment the semaphore variable to 1.
• Thread T1 is still in CS, the other thread(T3) can call wait() and decrements the value to 0 and can enter the CS.
• Hence there can be two threads in a critical section(CS) at a time.
• Thus semaphore cannot be used to ensure mutual excursion.
• This is referred to as Premature release and is one of the drawbacks of using semaphore.

Diag-2: Binary Semaphore

Counting Semaphore

• The counting semaphore variable can take any integer value, unlike the binary semaphore which can only have 0 and 1 as its values.
• It maintains a state which represents the maximum number of concurrent access that are allowed on multiple identical resources(file handles, buffer, etc).
• For example, Only three processes or threads to be printing because there are only three printers.
• The requests are blocked once the count goes beyond the initialization value(max number of concurrent access).
• The variable is manipulated by two operations that are wait and signal by wait() and post() primitives.
• When the semaphore count becomes 0, indicating that no more resources are present, threads trying to acquire the resources(decrement the semaphore value) get blocks until the count becomes greater than zero.
• This can be useful to implement producer-consumer design patterns or implement resources like thread pool, DB connection pool.

Algorithm: Producer and Consumer problem by counting semaphore

• Similar to the two condition variables, there will be two semaphore variables: empty and full.
• This will be used by threads to indicate when the buffer is empty and full respectively.

#define MAX  10
sem_t empty, full;
sem_init(&empty, 0, MAX);
sem_init(&full, 0 , 0);
int buffer[MAX];
int fill = 0
int use = 0;

void put_data( int value)         void get_data()
{                                 {
 buffer[fill] = value;             int temp = buffer[use];
 put_data(i);                      use= (use + 1 ) % MAX;
}                                  return temp;
                                  }
                                        
                                        
void producer()                  void consumer()                       
{                                {                                  
   for ( i =0 ;i <loop; i++)      for ( i =0 ;i <loop; i++)                         
    {                              {                                                             
        sem_wait (&empty);            sem_wait (&full);                       
        put_data (i);			      int val = get_data (i);			   
        sem_post (&full);             sem_post (&empty);                           
     }                              }                                      
}

Explanation:There can be two scenario:

• If the producer runs first
• If the consumer runs first

Producer running first:

• Since the value of empty is 1, thus it decrements the value to 0 and continues execution down.
• Once the producer finished its job and calls sem_post() on variable “full”, just the value is incremented to 1, since there is no sleeping thread.
• Now the consumer runs, and calls wait() on the variable “fill”, decrements the value to 0, and consumes the data.
• At the end consumer calls sem_post() on semaphore variable “empty”, it value is incremented to 1.
• And in the same fashion producer and consumer works in a cycle.

Consumer running first:

• Since the consumer waits on the semaphore variable “fill”, whose value is 0, hence it is blocked and the value is decremented to 0.
• Now the producer runs and calls wait on variable “empty”, decrements the value to 0, produces the data and, calls sem_post() on semaphore variable “fill” to increment the value to 1 and unblocks the consumer.
• Now the consumer consumes the data and again calls post on variable “empty” to increment the value to 1.

Hence, in either case, the desired behavior is achieved.

The above problem works very well with the single producer and single consumer but faces a problem of Race condition, in the case of multiple producer and multiple consumers.

Consider a scenario of two producers:

• If the first producer(P1) produces the data and calls the put_data() function to puts the data at the 0th location of buffer but before the index is incremented to 1, it is preempted by another producer(P2).
• The second producer will produce the data and uses the same old index and put data at buffer[0].
• Thus the value of producer(P1) is lost.
• Filling the buffer and incrementing the index is a part of the critical section and hence must be safeguarded against race conditions.
• Thus both producer and consumer must be locked that it should be mutually exclusive.
• A new semaphore variable can be taken which acts like a Binary semaphore

Solution:

#define MAX  10
sem_t empty, full;
sem_init(&empty, 0, MAX);
sem_init(&full, 0 , 0);
int buffer[MAX];
int fill = 0;
int use = 0;
sem_t mutex;
sem_init(&mutex, 0 , 1)

void put_data( int value)          void get_data()
{                                  {
 buffer[fill] = value;               int temp = buffer[use];
 put_data(i);                        use= (use + 1 ) % MAX;
}                                    return temp;
                                   }
                                        
                                        
void producer()                  void consumer()                       
{                                 {                                  
   for ( i =0 ;i <loop; i ++)      for ( i =0 ;i <loop; i ++)                         
    {                               {                                                             
        sem_wait(&mutex)               sem_wait(&mutex)                              
        sem_wait(&empty);              sem_wait(&full);                       
        put_data(i);			       int val = get_data(i);			   
        sem_post(&full);               sem_post(&empty); 
        sem_post(&mutex);              sem_post(&mutex);                  
     }                               }                                      
}                                   } 

Above Solution works well but has a problem of deadlock:

• Consider consumer running first and acquires the mutex lock.
• Now it tries to consume data but since there is no data, it is blocked and thus yields the CPU.
• Now the producer tries to acquire the mutex which is already locked, hence even the producer is blocked, causing deadlock.
• To overcome this deadlock problem, the scope of the lock should be reduced, that is it should be around the CS.
• Put the mutex lock after the sem_wait() for each semaphore variable(Swap).

#define MAX  10
sem_t empty, full;
sem_init(&empty, 0, MAX);
sem_init(&full, 0 , 0);
int buffer[MAX];
int fill = 0;
int use = 0;
sem_t mutex;
sem_init(&mutex, 0 , 1)

void put_data( int value)        void get_data()
{                                {
 buffer[fill] = value;             int temp = buffer[use];
 put_data(i);                      use= (use + 1 ) % MAX;
}                                  return temp;
                                 }
                                        
                                        
void producer()                   void consumer()                       
{                                 {                                  
   for ( i =0 ;i <loop; i ++)       for ( i =0 ;i <loop; i ++)                         
    {                               {                                                             
        sem_wait(&empty)              sem_wait(&full)                              
        sem_wait(&mutex);             sem_wait(&mutex);                       
        put_data(i);			      int val = get_data(i);			   
        sem_post(&mutex);             sem_post(&mutex); 
        sem_post(&full);              sem_post(&empty);                  
     }                               }                                      
}                                  }    

Diag-3: Counting Semaphore

Binary semaphore vs counting semaphore

Major difference between Binary and Counting semaphore are as follows:

• Binary semaphore can have only 0 and 1 as its values whereas counting semaphore can attain any integer values.
• Binary semaphore is preferred when only one resource has to be shared among multiple threads but only one at a time, whereas counting semaphore is preferred when more than one(N) similar resources has to be shared among multiple threads.

Semaphore use case:

• Semaphore is a signaling mechanism and should be preferred when one thread sleep until some other thread signals it to wake up.
• It is a kind of event-driven mechanism. once the event occurs, the signal is generated.
• The thread which locked the semaphore variable does not take ownership, it can be signaled by another thread to unblock. Hence should not be used for mutual exclusion.
• This can be useful in producer and consumer problems where both can signal each other once the buffer is full and empty respectively.
• Also useful in DB thread pool, DB connection pool.

Relevant Posts:

• Thread Synchronization
• Critical Section
• Race Condition
• Mutual Exclusion(Mutex)
• Mutex Vs Semaphore
• Spinlock
• Spinlock Vs Mutex
• Condition Variables

Categories: Operating system (OS)