Producer Consumer Problem in C++

Today I'm going to solve a most common problem which is known as the consumer producer problem. In this context we have a shared buffer which the producers produce and the consumers consume. The consumers and producers are threads which will simultaneously produce and consume. There are some conditions to be met where consumers have to wait until producers produce, and another thing is that when the buffer is full producers must halt until the consumers consume.

In the following example was implemented using pthreads. The producer produce a random number to the buffer and consumers consume that number. Mutex locks are used to protect the shared buffer. 

ProducerConsumer.cpp     DOWNLOAD SOURCE

#include <iostream>
#include <pthread.h>
#include <vector>
#include <cstdlib>
#include <stdlib.h>
#include <stdio.h>
#include <pthread.h>
#include <semaphore.h>
#include <string.h>



#define BUFFER_SIZE 10

void InitializeData();
void *Produce(void *);
void *Consume(void *);
int InsertItem(int);
int RemoveItem(int *);

int iCounter;
pthread_mutex_t mutex;
sem_t full, empty;

int buffer[BUFFER_SIZE];



int main(int argc , char * argv[])
{
 InitializeData(); 
 pthread_t ProducerThread , ConsumerThread;
 int *aa = new int [10];
 for(int i = 0 ; i < 10 ; i++)
 {
  aa[i] = i;
  pthread_t t;
  pthread_create(&t , NULL, Produce , &aa[i]);
  printf("Creating Producer %d \n", i);
 }
 int *bb = new int[10];
 for(int i = 0 ; i < 10 ; i++)
 {
  bb[i] = i;
  pthread_t t;
  pthread_create(&t , NULL, Consume , &bb[i]);
  printf("Creating Consumer %d \n", i);
 }
 
 sleep(5);
 delete [] aa;
 delete [] bb;
 

 return 0;
}

//****************************************************************************************************
void InitializeData()
{
 pthread_mutex_init(&mutex , NULL);
 sem_init(&full , 0 ,0);
 sem_init(&empty , 0 , BUFFER_SIZE);
 
 iCounter = 0;
 

}

//****************************************************************************************************
void * Produce(void * Param)
{
 int item;
 
 while(1)
 {
  //sleep(1);
  item = rand() % 100;
  sem_wait(&empty);
  pthread_mutex_lock(&mutex);
  int iMsg = InsertItem(item);
  
  if(iMsg == -1){
   printf("Error Inserting Item \n");
  }else
  {
   printf("Produced Item :: %d  Thread No :: %d\n", item , *((int *)Param));
  }
  pthread_mutex_unlock(&mutex);
  sem_post(&full);
  
 }
}

//****************************************************************************************************
void * Consume(void * Param)
{
 int item;
 
 while(1)
 {
  //sleep(1);
  sem_wait(&full);
  pthread_mutex_lock(&mutex);
  int iMsg = RemoveItem(&item);
  
  if(iMsg == -1){
   printf("Error Removing Item \n");
  }else
  {
   printf("Consumed Item :: %d  Thread No :: %d \n", item ,*((int *)Param));
  }
  pthread_mutex_unlock(&mutex);
  sem_post(&empty);
  
 }
}

//****************************************************************************************************
int InsertItem(int item)
{
 if(iCounter < BUFFER_SIZE)
 {
  buffer[iCounter] =  item;
  iCounter++;
  return 1;
 }
 else{
  return -1;
 }

}

//****************************************************************************************************
int RemoveItem(int *item)
{
 if(iCounter > 0)
 {
  *item = buffer[iCounter - 1];
  iCounter--;
  return 1;
 }
 else{
  return -1;
 }
}

That's it folks. Hope to see you soon in another exciting tutorial.

Longest Path Algorithm (Java Code)

The longest path algorithm is used to find the maximum length of a given graph. The maximum length may be measured by the maximum number of edges or the sum of the weights in a weighted graph. Following is a sample java code to find the Longest Path. It has two classes. CreateMatrix.java class to create the matrix and LongestPath.java to find the Longest Path to the created matrix. 

Download Source From Here.. DOWNLOAD

/********************* LongestPathAlgo.java ********************/ 
class LongestPathAlgo {

    public static void main(String[] args) {

        int length = 13;//length of the 2-D array
        int adjMatrix[][] = new int[length][length];
        CreateMatrix cm = new CreateMatrix();
        cm.createMatrix(length);
        adjMatrix = cm.readMatrix(adjMatrix);

        long starttime = System.nanoTime();
        LongestPathAlgo lpa = new LongestPathAlgo();
        boolean visited[] = new boolean[adjMatrix.length];
        lpa.initialize(adjMatrix, visited);
        int max = lpa.longestPath(0, visited, adjMatrix);
        long runtime = System.nanoTime()-starttime;
        System.out.println("Runtime =" + runtime +" nano seconds");
        System.out.println("Longest Path Length = "+max);
    }

    public void initialize(int adjMatrix[][], boolean visited[]) {
        for (int u = 0; u < adjMatrix.length; u++) {
            visited[u] = false;
        }
    }

    int longestPath(int vertex, boolean visited[], int adjMatrix[][]) {
        int dist, max = 0;
        visited[vertex] = true;

        for (int u = 0; u < adjMatrix[vertex].length; u++) {
            if (adjMatrix[vertex][u] != -1) {
                if (!visited[u]) {
                    dist = adjMatrix[vertex][u] + longestPath(u, visited, adjMatrix);
                    if (dist > max) {
                        max = dist;
                    }
                }
            }
        }
        visited[vertex] = false;
        return max;
    }
}

/********************* CreateMatrix.java ********************/
import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.File;
import java.io.FileReader;
import java.io.FileWriter;
import java.io.IOException;


public class CreateMatrix {

    public void createMatrix(int length) {
        Random ran = new Random();
        FileWriter fw;
        try {
            File file = new File("matrix.txt");
            fw = new FileWriter(file);
            BufferedWriter bw = new BufferedWriter(fw);
            for (int i = 0; i < length; i++) {
                for (int j = 0; j < length; j++) {
                    if (i == j) {
                        bw.write("" + -1);
                    } else {
                        bw.write("" + (i+j));
                    }
                    bw.write("@");
                }
                bw.newLine();
            }
            for (int i = 0; i < length; i++) {
            }
            bw.close();
            fw.close();
        } catch (IOException ex) {
            System.out.println("File Not Found");
          }

    }

    public int[][] readMatrix(int adjMatrix[][]) {

        try {
            File file = new File("matrix.txt");
            FileReader fr = new FileReader(file);
            BufferedReader br = new BufferedReader(fr);
            int i = 0;
            while (br.ready()) {
                String line = br.readLine();
                String array[] = line.split("@");
                for (int j = 0; j < adjMatrix.length; j++) {
                    adjMatrix[i][j] = Integer.parseInt(array[j]);
                }
                i++;
            }
        } catch (Exception e) {
            System.out.println("Error " + e);
        }
        return adjMatrix;
    }
}

Dijkstra Algorithm (Shortest Path Algorithm ) Java Code

Dijkstra Algorithm is used find the shortest path in a directed graphs. Following is a java implementation of the Dijkstra Algorithm.

class Dijkstra {

    public static void main(String[] args) {
        int length = 300;//length of the 2-D array
        int adjMatrix[][] = new int[length][length];
        CreateMatrix cm = new CreateMatrix();
        cm.createMatrix(length);
        adjMatrix = cm.readMatrix(adjMatrix);
        Dijkstra dk = new Dijkstra();
        dk.dijkstra(adjMatrix);

    }

    public void dijkstra(int adjMatrix[][]) {

        long startTime = System.nanoTime();
        int distance[] = new int[adjMatrix.length];
        int resolved[] = new int[adjMatrix.length];
        int prev[] = new int[adjMatrix.length];

        for (int i = 0; i < adjMatrix.length; i++) {
            distance[i] = Integer.MAX_VALUE;
            resolved[i] = Integer.MAX_VALUE;
            prev[i] = -1;
        }
        distance[ 0] = 0;
        resolved[ 0] = 0;

        int minNode = Integer.MAX_VALUE, position = 0;
        for (int i = 0; i < adjMatrix.length; i++) {
            for (int j = 0; j < resolved.length; j++) {
                if (minNode > distance[j] && resolved[j] != -1) {
                    minNode = distance[j];
                    position = j;
                }
            }
            resolved[position] = -1;

            for (int j = 0; j < adjMatrix.length; j++) {
                if (distance[j] > adjMatrix[position][j] + distance[position]) {
                    distance[j] = adjMatrix[position][j] + distance[position];
                    prev[j] = position;
                }
            }
            minNode = Integer.MAX_VALUE;
		}
        long runTime = System.nanoTime() - startTime;
        System.out.println("Runtime =" + runTime + " nano seconds");
        System.out.println("Distance Array");
        for (int j = 0; j < distance.length; j++) {
            System.out.print(" " + distance[j]);
        }
        System.out.println("");
        System.out.println("Predecessor Array");
        for (int i = 0; i < prev.length; i++) {
            System.out.print(" " + prev[i]);
        }
        System.out.println("");
    }
}