Readers Writers problem in OS

Introduction to the Readers-Writers Problem

The Readers-Writers Problem is a classic synchronization challenge in concurrent programming. It involves coordinating access to a shared resource (e.g., a database or file) between two types of processes:

• Readers: Processes that only read the shared resource (no modifications).
• Writers: Processes that modify the shared resource (require exclusive access).

Key Requirements:

1. Multiple readers can access the resource simultaneously.
2. Writers must have exclusive access (no other readers/writers during a write).
3. Avoid race conditions and ensure data consistency.

Solution Using Semaphores

Semaphores are used to enforce mutual exclusion and synchronization. The solution prioritizes readers (First Readers-Writers Problem), which may lead to writer starvation.

Semaphores Used:

1. rw_mutex (Binary Semaphore): Ensures mutual exclusion for writers. Acquired by the first reader and released by the last reader.
2. mutex (Binary Semaphore): Protects the read_count variable from race conditions.
3. read_count (Integer): Tracks the number of active readers.

Pseudocode:

// Initialization
semaphore rw_mutex = 1
semaphore mutex = 1
int read_count = 0

// Reader Process
procedure reader():
    wait(mutex)           // Lock read_count
    read_count += 1
    if read_count == 1:
        wait(rw_mutex)    // First reader blocks writers
    signal(mutex)         // Unlock read_count

    // Read the shared resource

    wait(mutex)           // Lock read_count
    read_count -= 1
    if read_count == 0:
        signal(rw_mutex) // Last reader unblocks writers
    signal(mutex)         // Unlock read_count

// Writer Process
procedure writer():
    wait(rw_mutex)        // Block readers and writers
    // Write to the shared resource
    signal(rw_mutex)

Example Code in C (POSIX Semaphores)

This implementation uses POSIX semaphores and threads to simulate readers and writers.

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

sem_t rw_mutex, mutex;
int read_count = 0;
int shared_data = 0; // Simulated shared resource

void *reader(void *arg) {
    int id = *(int *)arg;
    sem_wait(&mutex);
    read_count++;
    if (read_count == 1) {
        sem_wait(&rw_mutex);
    }
    sem_post(&mutex);

    // Reading
    printf("Reader %d read data: %d\n", id, shared_data);

    sem_wait(&mutex);
    read_count--;
    if (read_count == 0) {
        sem_post(&rw_mutex);
    }
    sem_post(&mutex);
    return NULL;
}

void *writer(void *arg) {
    int id = *(int *)arg;
    sem_wait(&rw_mutex);

    // Writing
    shared_data++;
    printf("Writer %d wrote data: %d\n", id, shared_data);

    sem_post(&rw_mutex);
    return NULL;
}

int main() {
    pthread_t readers[3], writers[2];
    sem_init(&rw_mutex, 0, 1);
    sem_init(&mutex, 0, 1);

    int ids[] = {1, 2, 3};

    // Create threads
    pthread_create(&writers[0], NULL, writer, &ids[0]);
    pthread_create(&readers[0], NULL, reader, &ids[0]);
    pthread_create(&readers[1], NULL, reader, &ids[1]);
    pthread_create(&writers[1], NULL, writer, &ids[1]);
    pthread_create(&readers[2], NULL, reader, &ids[2]);

    // Join threads
    for (int i = 0; i < 3; i++) pthread_join(readers[i], NULL);
    for (int i = 0; i < 2; i++) pthread_join(writers[i], NULL);

    sem_destroy(&rw_mutex);
    sem_destroy(&mutex);
    return 0;
}

Discussion

Key Points:

1. Mutual Exclusion:
   • rw_mutex ensures only one writer or multiple readers access the resource.
   • mutex protects the read_count variable from concurrent updates.
2. Starvation of Writers:
   • In this solution, continuous reader arrivals can block writers indefinitely (First Readers-Writers Problem).
3. Variations:
   • Second Readers-Writers Problem: Prioritizes writers to prevent starvation (requires additional semaphores).

Output Example:

Writer 1 wrote data: 1
Reader 1 read data: 1
Reader 2 read data: 1
Writer 2 wrote data: 2
Reader 3 read data: 2

Conclusion

Semaphores provide an effective way to solve the Readers-Writers Problem by:

• Allowing concurrent reads.
• Ensuring exclusive writes.
• Using rw_mutex and mutex to coordinate access.

However, this approach may starve writers in high-reader scenarios. For systems requiring fairness, the Second Readers-Writers solution (using additional synchronization) is recommended.