Classical IPC Problems

Now that we have learnt about semaphores and mutexes, let us write programs using these for the classical IPC problems. I give solution to one version(either using semaphores or using mutexes) per problem. The other versions for each problem is left as an exercise for the reader;).

I will be giving solutions to 4 different problems.

Producer Consumer Problem
Dining Philosophers problem
Sleeping Barber problem
Readers-Writers problem

---

Note: I will be using the functions which I have provided in my previous post, for semaphores, which is in the file "mysem.c".

Producer-Consumer Problem:Semaphore Version

#include<stdio.h>
#include<stdlib.h>
#include<sys/types.h>
#include<pthread.h>
#include "mysem.c"

#define MAX_BUF 10


int    *buffer;
int    head=0,tail=0,item_id=1;
int    count=0;
int    sem_ID; // 3 semaphores... { Mutex, Empty, Full}
int    fflag=0,eflag=0;

void producer()
{


printf("Producer started\n");

 while(1)
 {
  int v=0;
  sem_change(sem_ID, 0, -1);
  if(count==MAX_BUF)
  {
   printf("Producer waiting\n");
   fflag=1;
   sem_change(sem_ID, 0, 1);
   sem_change(sem_ID, 2, -1);
   sem_change(sem_ID, 0, -1);    //Waits until a free slot is available
  } 
   
  count++;
  buffer[head]=item_id++;
  
  if(count==1 && eflag==1)
  {
  eflag=0; 
  sem_change(sem_ID, 1, 1);    //To signal consumer thread that buffer is not empty
  }
  printf("produced item:%d \n", buffer[head]);
  head=(head+1)%MAX_BUF;
  sem_change(sem_ID, 0, 1);
  
  sleep(rand()%3);
  
 }
}

void consumer()
{
printf("consumer started\n");
 while(1)
 {
  int v=0;
  sem_change(sem_ID, 0, -1);
  if(count==0)
  {
   printf("Consumer Waiting\n");
   eflag=1;
   sem_change(sem_ID, 0, 1);
   sem_change(sem_ID, 1, -1);
   sem_change(sem_ID, 0, -1);
      //Waits until an item is produced
  }
  count--;
  
  printf("consumed item:%d \n", buffer[tail]);
  tail=(tail+1)%MAX_BUF;
  if(count==MAX_BUF-1 && fflag==1)
  {
   fflag=0;
   sem_change(sem_ID, 2, 1);                //To signal the producer thread that       
   }
buffer is not full
   sem_change(sem_ID, 0, 1);
  sleep(rand()%4);
 }
}
int main()
{
 buffer=(int*)calloc(MAX_BUF,sizeof(int));
 pthread_t pro,con;
 int values[]={1,0,0};
 sem_ID=sem_init_diff_val(3, values); //initialize with 1, 0, 0

 pthread_create(&pro, NULL, (void*)&producer, NULL);
 pthread_create(&con, NULL, (void*)&consumer, NULL);
 
 pthread_join(pro,NULL);

 return 0;
}

---

Dining Philosophers Problem:Mutex Version

#include<stdio.h>
#include<stdlib.h>
#include<pthread.h>
#define PHILOSOPHERS 5

pthread_mutex_t   spoon[PHILOSOPHERS];

//Intializes the philosopher threads
void phil_init(int a, int* b, int* c)
{
 *b=(a>0) ? a-1 : PHILOSOPHERS;
 *c=a;
 printf("Philosopher %d started\n", a+1);
 return;
}


int  check_If_Spoons_Are_Available(int a, int b, int c)
{
 int  sum=0;
 if(a&1)
 {
  sum =  pthread_mutex_trylock(&spoon[c])==0 ? 0 : 10;
  sum += pthread_mutex_trylock(&spoon[b])==0 ? 0 :  1;
 }
 else
 {
  sum = pthread_mutex_trylock(&spoon[b])==0 ? 0 : 1;
  sum += pthread_mutex_trylock(&spoon[c])==0 ? 0 : 10;
 }
 return sum;
}

void Release_Spoons(int a, int b, int c)
{
 if(a&1)
 {
  pthread_mutex_unlock(&spoon[b]);
  pthread_mutex_unlock(&spoon[c]);
 }
 else
 {
  pthread_mutex_unlock(&spoon[c]);
  pthread_mutex_unlock(&spoon[b]);
 }
}

void wait_for_others_to_finish(int a, int b ,int c, int d)
{
 switch(a)
 {
  case 1:
   printf("Philosopher %d waiting since right spoon is unavailable\n",b+1);
   pthread_mutex_lock(&spoon[c]);
   break;
   case 10:
    printf("Philosopher %d waiting since left spoon is unavailable\n", b+1);
    pthread_mutex_lock(&spoon[d]);
    break;
    case 11:
     printf("Philosopher %d waiting since both spoons are unavailable\n", b+1);
     if(a&1)
     {
      pthread_mutex_lock(&spoon[d]);
      pthread_mutex_lock(&spoon[c]);
     }
     else
     {
      pthread_mutex_lock(&spoon[d]);
      pthread_mutex_lock(&spoon[c]);
     }
     break;
 }
 return;
}

void Eat(int a)
{
  printf("philosopher %d eating\n", a+1);
  sleep(rand()%5);
  printf("philosopher %d finished eating\n", a+1);
}
void philo(void * arg)
{
 
 int  back;
 int  front;
 int  tmp;
 int  id=*((int*)arg);
 phil_init(id, &back, &front);


 while(1)
 {
  printf("philosopher %d thinking\n", id+1);
  sleep(rand()%6);

  if((tmp=check_If_Spoons_Are_Available(id, back, front))!=0)
   wait_for_others_to_finish(tmp, id, back, front);
  
   Eat(id);
  
  Release_Spoons(*((int*)arg), back, front);
 }
}


int main(int argc, char* argv[])
{
 pthread_t  S[PHILOSOPHERS];
 int   *g;

 for(int i=0; i<PHILOSOPHERS; i++)
 pthread_mutex_init(&spoon[i], NULL);

  g=(int*)malloc(PHILOSOPHERS*sizeof(int));
 for(int i=0; i<PHILOSOPHERS; i++)
 {
   g[i]=i;
  pthread_create(&S[i], NULL, (void*)&philo,(void*)&g[i]);
 }
 pthread_join(S[0], NULL);
exit(0);
}

---

Sleeping Barber Problem:Semaphore Version

#include<stdlib.h>
#include<stdio.h>
#include<pthread.h>
#include "mysem.c"
#define MAX_C 5
int sem_ID;         //----> creates a set of 5 semaphores. { mutex, cond_empty, counting semaphore, waiting semaphore, barber semaphore}
int customers_count=0;
int eflag=fflag=0;
void barber()
{
 printf("barber started\n");
 while(1)
 {
  
  sem_change(sem_ID, 0, -1);

  if(customers_count==0)
  {  
   printf("barber sleeping\n");
   eflag=1;
   sem_change(sem_ID, 0, 1);
   sem_change(sem_ID, 1, -1);
   sem_change(sem_ID, 0, -1);
  }

  customers_count--;

  sem_change(sem_ID, 0, 1);
  sem_change(sem_ID, 3, 1);
 // printf("tail:%d\n", tail);
 // pthread_mutex_lock(&B);
  
  sem_change(sem_ID, 4, -1);
 // pthread_mutex_unlock(&B);
  
  }
}
void customer(void *arg)
{  
  
  //printf("C\n");
 sem_change(sem_ID, 0, -1);
 if(customers_count==MAX_C)       // If all seats are occupied exit the thread
  {
   int *ptr=(int*)arg;
   *ptr=0;
   printf("No place for customer %d so leaving\n", pthread_self());
   sem_change(sem_ID, 0, 1);
   return;
  } 
  
  customers_count++;

  if(customers_count==1 && eflag==1)
  {
  sem_change(sem_ID, 1, 1);
  eflag=0;
  }
  sem_change(sem_ID, 0, 1);
  printf("Customer %d got a place\n", pthread_self());
  sem_change(sem_ID, 3, -1);
  printf("Cutting for %d customer\n", pthread_self());
  sleep(rand()%5+4);
  sem_change(sem_ID, 4, 1);
 // printf("head:%d\n", head);
 // pthread_mutex_lock(&B);
  
 // pthread_mutex_unlock(&B);

  
  int *ptr=(int*)arg;
  *ptr=0;
}
int main(int argc, char* argv[])
{
pthread_t  barber_thread;
int   live_threads[MAX_C+2];     // 0 = no thread is created with this index, 

          // 1=there is a live thread with this index

pthread_t  customer_thread[MAX_C +2];
          

for(int i=0; i<MAX_C+2; i++)
 live_threads[i]=0;     // initially all are dead state


int array[]={1, 0, MAX_C, 0, 0};     // Initial values of different semaphores
sem_ID=sem_init_diff_val(5,array);

pthread_create(&barber_thread, NULL, (void*)&barber, NULL);

sleep(2);
//Continuous thread generator....
while(1)
{
 for(int i=0; i<MAX_C+2; i++)
 {
  if(live_threads[i]==0)
  {
   live_threads[i]=1;
   pthread_create(&customer_thread[i], NULL, (void*)&customer, (void*)&live_threads[i]);
   sleep(rand()%4);
  }
  
 }
}


 
exit(0);
}

---

Readers Writers Problem:Mutex Version

Note: The execution depends on the selection algorithm of the mutex.

#include<stdio.h>
#include<pthread.h>
pthread_mutex_t no_wait, no_acc, counter;
int no_of_readers=0;



void reader(void *arg)
{

 int id=*((int*)arg);
 printf("reader %d started\n", id);
 while(1)
 {
  sleep(rand()%4);
 check_and_wait(id);
 read(id);
}
}


void writer(void* arg)
{ 
 int id=*((int*)arg);
 printf("writer %d started\n", id);
 while(1)
{  
 sleep(rand()%5);
 check_and_wait_if_busy(id);
 write(id);
}
}


/*sub functions for reader and writer threads*/
void check_and_wait_if_busy(int id)
{
  if(pthread_mutex_trylock(&no_wait)!=0){
  printf("Writer %d Waiting\n", id);
  pthread_mutex_lock(&no_wait);
 }
}
void check_and_wait(int id)
{
 if(pthread_mutex_trylock(&no_wait)!=0){
  printf("Reader %d Waiting\n", id);
  pthread_mutex_lock(&no_wait);
 }
}
void read(int id)
{
 pthread_mutex_lock(&counter);
 no_of_readers++;
 pthread_mutex_unlock(&counter);
 if(no_of_readers==1) 
  pthread_mutex_lock(&no_acc);
 pthread_mutex_unlock(&no_wait);
 printf("reader %d reading...\n", id);
 sleep(rand()%5);
 printf("reader %d finished reading\n", id);
 
 pthread_mutex_lock(&counter);
 no_of_readers--;
 pthread_mutex_unlock(&counter);
 if(no_of_readers==0) 
  pthread_mutex_unlock(&no_acc);
 
}

void write(int id)
{
 pthread_mutex_lock(&no_acc);
 pthread_mutex_unlock(&no_wait);
 printf("Writer %d writing...\n", id);
 sleep(rand()%4+2);
 printf("Writer %d finished writing\n", id);
 pthread_mutex_unlock(&no_acc);
}

/**************************************************/
//MAIN
int main(int argc, char* argv[])
{
 pthread_t R[5],W[5];
 int ids[5];
 for(int i=0; i<5; i++)
 {
  ids[i]=i+1;
  pthread_create(&R[i], NULL, (void*)&reader, (void*)&ids[i]);
  pthread_create(&W[i], NULL, (void*)&writer, (void*)&ids[i]);
 }
 pthread_join(R[0], NULL);
 exit(0);
}

<<Prev Next>>