Producer Consumer Problem: Process Synchronisation

The Producer-Consumer Problem is a classic synchronization problem in Operating Systems that illustrates the need for process synchronization in the context of shared resources. In this problem, there are two types of processes: Producers and Consumers.

Problem Definition

• Producers generate data and place it in a buffer.
• Consumers take the data from the buffer and process it.
• The buffer is finite, meaning it can only hold a certain number of items at a time.

The challenge lies in ensuring that:

1. Producers don’t add data to a full buffer.
2. Consumers don’t remove data from an empty buffer.
3. No two processes (producers or consumers) access the buffer at the same time in a way that corrupts the shared data.

Key Concepts

• Critical Section: A part of the code where shared resources are accessed. In the Producer-Consumer problem, both producers and consumers have critical sections when they access the shared buffer.
• Race Condition: This occurs when two or more processes or threads try to modify shared data concurrently, leading to unpredictable results.
• Synchronization: The mechanism to control the access of multiple processes to the shared buffer, ensuring only one process accesses the critical section at a time.
• Semaphores: A synchronization tool used to handle the critical sections. Typically, you use two types of semaphores:
  • Full: Indicates how many items are filled in the buffer.
  • Empty: Indicates how many slots are empty in the buffer.
  • Mutex: A binary semaphore (0 or 1) used to ensure mutual exclusion (only one process can access the critical section at a time).

Producer-Consumer Problem Using Semaphores

1. Semaphores:

• empty: Keeps track of the number of empty slots in the buffer. Initialized to the buffer size.
• full: Keeps track of the number of filled slots in the buffer. Initialized to 0.
• mutex: A binary semaphore to ensure mutual exclusion during buffer access.

2. Producer:

• Before adding an item to the buffer, the producer must:
  1. Wait until there is at least one empty slot (empty semaphore).
  2. Wait for mutual exclusion to enter the critical section (mutex semaphore).
  3. Add the item to the buffer.
  4. Signal to release mutual exclusion.
  5. Signal that a new item is added to the buffer (full semaphore).

3. Consumer:

• Before removing an item from the buffer, the consumer must:
  1. Wait until there is at least one filled slot (full semaphore).
  2. Wait for mutual exclusion to enter the critical section (mutex semaphore).
  3. Remove the item from the buffer.
  4. Signal to release mutual exclusion.
  5. Signal that an empty slot is available (empty semaphore).

Pseudocode for Producer and Consumer

Initialize:
   Semaphore empty = n   // n is the size of the buffer
   Semaphore full = 0
   Semaphore mutex = 1

Producer:
   while (true) {
      // Produce an item
      wait(empty);       // Check if there are empty slots
      wait(mutex);       // Enter the critical section
      // Add item to the buffer
      signal(mutex);     // Exit the critical section
      signal(full);      // Indicate that a new item is available
   }

Consumer:
   while (true) {
      wait(full);        // Check if there are filled slots
      wait(mutex);       // Enter the critical section
      // Remove item from the buffer
      signal(mutex);     // Exit the critical section
      signal(empty);     // Indicate that an empty slot is available
      // Consume the item
   }

C Implementation Using Semaphores (POSIX)

In this implementation, we use POSIX threads and semaphores for the producer-consumer problem.

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

#define BUFFER_SIZE 5  // Buffer size

int buffer[BUFFER_SIZE];
int in = 0, out = 0;

// Semaphores
sem_t empty;
sem_t full;
pthread_mutex_t mutex;

void *producer(void *param) {
    int item;
    while (1) {
        // Produce an item
        item = rand() % 100;  
        sem_wait(&empty);         // Decrement empty semaphore
        pthread_mutex_lock(&mutex);  // Lock the buffer (critical section)

        // Add item to the buffer
        buffer[in] = item;
        printf("Producer produced: %d\n", item);
        in = (in + 1) % BUFFER_SIZE;

        pthread_mutex_unlock(&mutex);  // Unlock the buffer
        sem_post(&full);           // Increment full semaphore
    }
}

void *consumer(void *param) {
    int item;
    while (1) {
        sem_wait(&full);          // Decrement full semaphore
        pthread_mutex_lock(&mutex);   // Lock the buffer (critical section)

        // Remove item from the buffer
        item = buffer[out];
        printf("Consumer consumed: %d\n", item);
        out = (out + 1) % BUFFER_SIZE;

        pthread_mutex_unlock(&mutex); // Unlock the buffer
        sem_post(&empty);          // Increment empty semaphore
    }
}

int main() {
    pthread_t tid1, tid2;  // Thread IDs
    pthread_attr_t attr;   // Thread attributes

    // Initialize semaphores and mutex
    sem_init(&empty, 0, BUFFER_SIZE);
    sem_init(&full, 0, 0);
    pthread_mutex_init(&mutex, NULL);

    // Create threads
    pthread_attr_init(&attr);
    pthread_create(&tid1, &attr, producer, NULL);
    pthread_create(&tid2, &attr, consumer, NULL);

    // Join threads (wait for them to finish)
    pthread_join(tid1, NULL);
    pthread_join(tid2, NULL);

    // Clean up
    sem_destroy(&empty);
    sem_destroy(&full);
    pthread_mutex_destroy(&mutex);

    return 0;
}

Explanation of Code:

1. Global Variables:

   • buffer[BUFFER_SIZE]: This is the buffer where the producer will place items, and the consumer will take them out.
   • in: Points to the next position where the producer will insert the item.
   • out: Points to the next position where the consumer will retrieve the item.

2. Semaphores:

   • empty: Keeps track of empty slots in the buffer. Initialized to BUFFER_SIZE.
   • full: Keeps track of filled slots. Initialized to 0.
   • mutex: Ensures mutual exclusion when accessing the shared buffer.

3. Producer Thread:

   • Generates an item (random value in this case).
   • Waits until there’s an empty slot (sem_wait(&empty)).
   • Locks the buffer (pthread_mutex_lock(&mutex)).
   • Places the item in the buffer.
   • Unlocks the buffer (pthread_mutex_unlock(&mutex)).
   • Signals that an item has been placed in the buffer (sem_post(&full)).

4. Consumer Thread:

   • Waits until there is at least one item in the buffer (sem_wait(&full)).
   • Locks the buffer (pthread_mutex_lock(&mutex)).
   • Retrieves an item from the buffer.
   • Unlocks the buffer (pthread_mutex_unlock(&mutex)).
   • Signals that a slot is now empty (sem_post(&empty)).

5. Main Function:

   • Initializes the semaphores and mutex.
   • Creates the producer and consumer threads.
   • Joins the threads to ensure they run indefinitely.

Key Points:

• The buffer is shared between producers and consumers, and thus needs to be accessed in a synchronized manner.
• Semaphores empty and full ensure that the producer doesn’t produce when the buffer is full and the consumer doesn’t consume when it’s empty.
• Mutex ensures that only one producer or consumer can access the buffer at a time, avoiding race conditions.

Conclusion:

The Producer-Consumer problem is a fundamental example in Operating Systems to understand synchronization, mutual exclusion, and deadlock prevention. Semaphores and mutexes are widely used in solving such problems, ensuring that processes coordinate their access to shared resources effectively.