[OS Concepts] 07. Synchronization Problems: Producer-Consumer, Dining Philosophers

Classic Synchronization Problems

To understand the correct use of synchronization tools, let us examine three classic problems traditionally studied in the operating systems field.

1. Bounded-Buffer Problem

The producer creates data and places it in the buffer, while the consumer takes data from the buffer and uses it. Since the buffer size is finite, the producer must wait when the buffer is full, and the consumer must wait when it is empty.

[Bounded Buffer Structure]

Producer -->  [  |  |  |  |  ]  --> Consumer
              0  1  2  3  4
              ^           ^
             out          in

Semaphores:
  mutex = 1      (mutual exclusion for buffer access)
  empty = N      (number of empty slots, initial = buffer size)
  full  = 0      (number of filled slots, initial = 0)

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

#define BUFFER_SIZE 5

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

sem_t empty;    // Number of empty slots
sem_t full;     // Number of filled slots
pthread_mutex_t mutex;

void *producer(void *arg) {
    int id = *(int *)arg;
    for (int i = 0; i < 10; i++) {
        int item = rand() % 100;

        sem_wait(&empty);           // Wait until empty slot available
        pthread_mutex_lock(&mutex); // Lock buffer access

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

        pthread_mutex_unlock(&mutex);
        sem_post(&full);            // Increase filled slot count

        usleep(rand() % 500000);
    }
    return NULL;
}

void *consumer(void *arg) {
    int id = *(int *)arg;
    for (int i = 0; i < 10; i++) {
        sem_wait(&full);            // Wait until filled slot available
        pthread_mutex_lock(&mutex); // Lock buffer access

        // Critical section: remove item from buffer
        int item = buffer[out];
        printf("Consumer %d: buffer[%d] = %d consumed\n", id, out, item);
        out = (out + 1) % BUFFER_SIZE;

        pthread_mutex_unlock(&mutex);
        sem_post(&empty);           // Increase empty slot count

        usleep(rand() % 800000);
    }
    return NULL;
}

int main() {
    pthread_mutex_init(&mutex, NULL);
    sem_init(&empty, 0, BUFFER_SIZE);
    sem_init(&full, 0, 0);

    pthread_t prod[2], cons[2];
    int ids[] = {0, 1};

    for (int i = 0; i < 2; i++) {
        pthread_create(&prod[i], NULL, producer, &ids[i]);
        pthread_create(&cons[i], NULL, consumer, &ids[i]);
    }

    for (int i = 0; i < 2; i++) {
        pthread_join(prod[i], NULL);
        pthread_join(cons[i], NULL);
    }

    pthread_mutex_destroy(&mutex);
    sem_destroy(&empty);
    sem_destroy(&full);
    return 0;
}

2. Readers-Writers Problem

When multiple processes share a database, processes that only read (readers) can access concurrently without issues, but writing processes (writers) need exclusive access.

[Readers-Writers Rules]

Reader + Reader = Allowed (concurrent reads OK)
Reader + Writer = Not Allowed (conflict)
Writer + Writer = Not Allowed (conflict)

First Variation: Reader Priority

Writers wait while readers are present. If readers keep arriving, writers may starve.

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

pthread_mutex_t mutex = PTHREAD_MUTEX_INITIALIZER;
pthread_mutex_t rw_mutex = PTHREAD_MUTEX_INITIALIZER;
int read_count = 0;
int shared_data = 0;

void *reader(void *arg) {
    int id = *(int *)arg;

    pthread_mutex_lock(&mutex);
    read_count++;
    if (read_count == 1) {
        // First reader blocks writers
        pthread_mutex_lock(&rw_mutex);
    }
    pthread_mutex_unlock(&mutex);

    // Critical section: read
    printf("Reader %d: data read = %d (current readers: %d)\n",
           id, shared_data, read_count);

    pthread_mutex_lock(&mutex);
    read_count--;
    if (read_count == 0) {
        // Last reader unblocks writers
        pthread_mutex_unlock(&rw_mutex);
    }
    pthread_mutex_unlock(&mutex);

    return NULL;
}

void *writer(void *arg) {
    int id = *(int *)arg;

    pthread_mutex_lock(&rw_mutex);  // Exclusive access

    // Critical section: write
    shared_data++;
    printf("Writer %d: data updated = %d\n", id, shared_data);

    pthread_mutex_unlock(&rw_mutex);

    return NULL;
}

Second Variation: Writer Priority

When a writer is ready, new readers cannot enter. After all existing readers leave, the writer executes.

3. Dining Philosophers Problem

Five philosophers sit at a round table. There is one chopstick between each pair of philosophers, and eating requires two chopsticks.

[Dining Philosophers]

        P0
    C4      C0
  P4          P1
    C3      C1
        P3
      C2
        P2

P: Philosopher
C: Chopstick

Philosopher i uses chopstick i and chopstick (i+1)%5

Simple Solution Using Semaphores (Deadlock Risk)

// Warning: This solution can cause deadlock!
sem_t chopstick[5];

void *philosopher(void *arg) {
    int id = *(int *)arg;

    while (1) {
        printf("Philosopher %d: thinking\n", id);
        usleep(rand() % 1000000);

        // Pick up both chopsticks
        sem_wait(&chopstick[id]);           // Left
        sem_wait(&chopstick[(id + 1) % 5]); // Right

        printf("Philosopher %d: eating\n", id);
        usleep(rand() % 1000000);

        // Put down chopsticks
        sem_post(&chopstick[id]);
        sem_post(&chopstick[(id + 1) % 5]);
    }
}

// Deadlock: If all 5 pick up their left chopstick simultaneously
// no one can get their right chopstick!

Deadlock Prevention Solutions

// Solution 1: Asymmetric - Even philosophers pick left first, odd pick right first
void *philosopher_asymmetric(void *arg) {
    int id = *(int *)arg;

    while (1) {
        printf("Philosopher %d: thinking\n", id);

        if (id % 2 == 0) {
            sem_wait(&chopstick[id]);
            sem_wait(&chopstick[(id + 1) % 5]);
        } else {
            sem_wait(&chopstick[(id + 1) % 5]);
            sem_wait(&chopstick[id]);
        }

        printf("Philosopher %d: eating\n", id);
        usleep(rand() % 1000000);

        sem_post(&chopstick[id]);
        sem_post(&chopstick[(id + 1) % 5]);
    }
}

Monitor-Based Solution

// Monitor-based solution (using Pthreads condition variables)
#include <pthread.h>
#include <stdio.h>
#include <unistd.h>
#include <stdlib.h>

#define N 5
#define THINKING 0
#define HUNGRY   1
#define EATING   2

int state[N];
pthread_mutex_t monitor_mutex = PTHREAD_MUTEX_INITIALIZER;
pthread_cond_t self[N];

// Left and right neighbor indices
#define LEFT(i)  ((i + N - 1) % N)
#define RIGHT(i) ((i + 1) % N)

void test(int i) {
    // If I'm hungry and neither neighbor is eating, I can eat
    if (state[i] == HUNGRY &&
        state[LEFT(i)] != EATING &&
        state[RIGHT(i)] != EATING) {
        state[i] = EATING;
        pthread_cond_signal(&self[i]);
    }
}

void pickup(int i) {
    pthread_mutex_lock(&monitor_mutex);

    state[i] = HUNGRY;
    printf("Philosopher %d: hungry\n", i);
    test(i);  // Check if can eat immediately

    while (state[i] != EATING) {
        pthread_cond_wait(&self[i], &monitor_mutex);
    }

    printf("Philosopher %d: starts eating\n", i);
    pthread_mutex_unlock(&monitor_mutex);
}

void putdown(int i) {
    pthread_mutex_lock(&monitor_mutex);

    state[i] = THINKING;
    printf("Philosopher %d: done eating, starts thinking\n", i);

    // Check if neighbors can eat
    test(LEFT(i));
    test(RIGHT(i));

    pthread_mutex_unlock(&monitor_mutex);
}

void *philosopher(void *arg) {
    int id = *(int *)arg;
    while (1) {
        usleep(rand() % 1000000);  // Think
        pickup(id);                 // Pick up chopsticks
        usleep(rand() % 1000000);  // Eat
        putdown(id);                // Put down chopsticks
    }
}

POSIX Synchronization

POSIX Mutex

#include <pthread.h>

pthread_mutex_t lock;

// Static initialization
pthread_mutex_t lock = PTHREAD_MUTEX_INITIALIZER;

// Dynamic initialization
pthread_mutex_init(&lock, NULL);

// Usage
pthread_mutex_lock(&lock);
// Critical section
pthread_mutex_unlock(&lock);

// Non-blocking attempt
if (pthread_mutex_trylock(&lock) == 0) {
    // Lock acquired successfully
    pthread_mutex_unlock(&lock);
} else {
    // Another thread holds the lock
}

// Cleanup
pthread_mutex_destroy(&lock);

POSIX Semaphores

POSIX provides named and unnamed semaphores.

#include <semaphore.h>

// Unnamed semaphore (between threads)
sem_t sem;
sem_init(&sem, 0, 1);  // 0: between threads, initial value 1
sem_wait(&sem);
sem_post(&sem);
sem_destroy(&sem);

// Named semaphore (between processes)
sem_t *sem = sem_open("/my_sem", O_CREAT, 0644, 1);
sem_wait(sem);
sem_post(sem);
sem_close(sem);
sem_unlink("/my_sem");

POSIX Condition Variables

#include <pthread.h>

pthread_mutex_t mutex = PTHREAD_MUTEX_INITIALIZER;
pthread_cond_t cond = PTHREAD_COND_INITIALIZER;
int data_ready = 0;

// Producer
void *producer(void *arg) {
    pthread_mutex_lock(&mutex);

    // Generate data
    data_ready = 1;
    printf("Producer: data ready\n");

    pthread_cond_signal(&cond);    // Wake up waiting consumer
    pthread_mutex_unlock(&mutex);
    return NULL;
}

// Consumer
void *consumer(void *arg) {
    pthread_mutex_lock(&mutex);

    while (!data_ready) {
        // Wait until condition is met
        // Mutex is automatically released during wait
        pthread_cond_wait(&cond, &mutex);
    }

    printf("Consumer: data consumed\n");
    data_ready = 0;

    pthread_mutex_unlock(&mutex);
    return NULL;
}

Java Synchronization

synchronized Keyword

public class Counter {
    private int count = 0;

    // Method-level synchronization
    public synchronized void increment() {
        count++;
    }

    public synchronized int getCount() {
        return count;
    }

    // Block-level synchronization
    public void incrementBlock() {
        synchronized (this) {
            count++;
        }
    }
}

ReentrantLock

A more flexible locking mechanism than synchronized.

import java.util.concurrent.locks.ReentrantLock;
import java.util.concurrent.locks.Condition;

public class BoundedBufferLock {
    private final Object[] buffer;
    private int count = 0, in = 0, out = 0;

    private final ReentrantLock lock = new ReentrantLock();
    private final Condition notFull = lock.newCondition();
    private final Condition notEmpty = lock.newCondition();

    public BoundedBufferLock(int size) {
        buffer = new Object[size];
    }

    public void produce(Object item) throws InterruptedException {
        lock.lock();
        try {
            while (count == buffer.length) {
                notFull.await();    // Wait until buffer has space
            }
            buffer[in] = item;
            in = (in + 1) % buffer.length;
            count++;
            notEmpty.signal();      // Wake up consumer
        } finally {
            lock.unlock();
        }
    }

    public Object consume() throws InterruptedException {
        lock.lock();
        try {
            while (count == 0) {
                notEmpty.await();   // Wait until data available
            }
            Object item = buffer[out];
            out = (out + 1) % buffer.length;
            count--;
            notFull.signal();       // Wake up producer
            return item;
        } finally {
            lock.unlock();
        }
    }
}

Alternative Approaches

Transactional Memory

Applies the database transaction concept to memory access.

// Conceptual code (actual syntax varies by implementation)
atomic {
    // All memory operations in this block execute atomically
    // Automatically retries on conflict
    account1.balance -= amount;
    account2.balance += amount;
}

Functional Programming

Using immutable data structures means shared state is never modified, making synchronization unnecessary. Functional languages like Erlang, Scala, and Haskell utilize this approach.

Summary

The bounded buffer, readers-writers, and dining philosophers problems are classic examples that illustrate the core challenges of synchronization. POSIX and Java provide various synchronization tools including mutexes, semaphores, and condition variables. Alternative approaches like transactional memory and functional programming are also gaining attention as methods for solving concurrency problems.