Reader Writer Problem: Process Synchronization

Reader-Writer Problem

The Reader-Writer Problem is a classic synchronization problem in the context of operating systems and multi-threaded applications. It addresses the issue of managing concurrent access to a shared resource (e.g., a file, database, or memory), where multiple threads (or processes) may need to read from or write to the resource simultaneously. The problem highlights the need to efficiently handle access to shared data while preventing data corruption and ensuring that the system works correctly when multiple threads are involved.

Problem Definition

In the Reader-Writer Problem:

• Readers: These processes only read the shared data and do not modify it.
• Writers: These processes modify the shared data and may alter its state.

The challenge is to allow:

1. Multiple Readers: Multiple readers can read the data at the same time, as long as no writer is writing.
2. Exclusive Writers: Only one writer can access the data at a time, and no reader can access it while a writer is writing.
3. Deadlock Prevention: We need to prevent scenarios where no process is able to proceed due to waiting indefinitely.

Key Concepts

• Critical Section: The part of the code where the shared resource (data) is accessed. Both readers and writers have critical sections.
• Mutual Exclusion: Only one writer can access the shared resource at a time, but multiple readers can read simultaneously.
• Race Condition: Occurs when two or more processes (readers or writers) attempt to access shared data concurrently without proper synchronization, potentially causing data corruption.
• Synchronization: The mechanism used to control the access of multiple processes to the shared resource to ensure the correctness of the system.
• Semaphores: A synchronization tool used to manage access to shared resources.

Solution Requirements

• Readers Preference: If there are no writers, multiple readers can access the resource concurrently.
• Writers Priority: If a writer is writing, no readers should be allowed to read.
• Fairness: No process should be starved; both readers and writers must eventually be able to access the shared resource.

Semaphores in the Reader-Writer Problem

To solve the Reader-Writer Problem, we use a combination of semaphores:

1. mutex: A binary semaphore to ensure mutual exclusion when accessing the shared resource.
2. readCount: A counter to track the number of readers accessing the shared resource.
3. write: A semaphore to manage access to the critical section for writers (writers have exclusive access).
4. readMutex: A binary semaphore to ensure mutual exclusion when updating the read count.

Solution Approach

1. When a Reader wants to read:

   • The reader must wait for readMutex to enter the critical section where the readCount is updated.
   • If the reader is the first to arrive, it waits for the writer to finish.
   • The reader increments the readCount to indicate that it is reading.
   • If there are other readers, it is allowed to read concurrently.
   • Once finished, the reader decrements the readCount. If the reader is the last one to leave, it signals that the writer can proceed.

2. When a Writer wants to write:

   • The writer must wait until there are no active readers or other writers.
   • The writer has exclusive access to the resource, meaning no readers or other writers can proceed while it is writing.
   • The writer performs its operation and signals that it has finished writing.

Pseudocode for Reader-Writer Problem

Reader Process:

Initialize:
    Semaphore mutex = 1;          // Mutex for mutual exclusion
    Semaphore readMutex = 1;      // Semaphore for synchronizing readCount
    Semaphore write = 1;          // Semaphore for writers (ensures exclusive access)
    int readCount = 0;            // Count of readers currently accessing the resource

Reader:
    while (true) {
        wait(readMutex);          // Enter critical section to update readCount
        readCount  ;              // Increment reader count
        if (readCount == 1) {
            wait(write);          // First reader blocks writer
        }
        signal(readMutex);        // Exit critical section

        // Critical section: Read the shared resource
        read_resource();

        wait(readMutex);          // Enter critical section to update readCount
        readCount--;              // Decrement reader count
        if (readCount == 0) {
            signal(write);        // Last reader allows writer to proceed
        }
        signal(readMutex);        // Exit critical section
    }

Writer Process:

Writer:
    while (true) {
        wait(write);              // Wait until no readers or writers are active

        // Critical section: Write to the shared resource
        write_resource();

        signal(write);            // Release the write lock, allowing others to proceed
    }

C Implementation Using Semaphores (POSIX)

Here's a C implementation of the Reader-Writer Problem using POSIX threads and semaphores.

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

#define BUFFER_SIZE 5  // Example buffer size

// Shared resource and state variables
int shared_resource = 0;
int readCount = 0;  // Number of readers currently reading

// Semaphores
sem_t mutex;        // Mutex for mutual exclusion (accessing readCount)
sem_t write;        // Semaphore for controlling access to the writer
sem_t readMutex;    // Semaphore for synchronizing the readCount

void *reader(void *param) {
    while (1) {
        sem_wait(&readMutex);      // Enter critical section to update readCount
        readCount  ;               // Increment readCount
        if (readCount == 1) {
            sem_wait(&write);      // Block writers if it's the first reader
        }
        sem_post(&readMutex);      // Exit critical section

        // Critical section: Read the shared resource
        printf("Reader is reading: %d\n", shared_resource);

        sem_wait(&readMutex);      // Enter critical section to update readCount
        readCount--;               // Decrement readCount
        if (readCount == 0) {
            sem_post(&write);     // Last reader allows writer to proceed
        }
        sem_post(&readMutex);      // Exit critical section
    }
}

void *writer(void *param) {
    while (1) {
        sem_wait(&write);          // Wait until no readers or writers are active

        // Critical section: Write to the shared resource
        shared_resource  ;
        printf("Writer is writing: %d\n", shared_resource);

        sem_post(&write);          // Release the write lock
    }
}

int main() {
    pthread_t readerThread, writerThread;

    // Initialize semaphores
    sem_init(&mutex, 0, 1);
    sem_init(&write, 0, 1);
    sem_init(&readMutex, 0, 1);

    // Create reader and writer threads
    pthread_create(&readerThread, NULL, reader, NULL);
    pthread_create(&writerThread, NULL, writer, NULL);

    // Join threads
    pthread_join(readerThread, NULL);
    pthread_join(writerThread, NULL);

    // Destroy semaphores
    sem_destroy(&mutex);
    sem_destroy(&write);
    sem_destroy(&readMutex);

    return 0;
}

Explanation of Code

1. Global Variables:

   • shared_resource: The shared resource (data) that readers and writers access.
   • readCount: Keeps track of the number of readers currently accessing the shared resource.

2. Semaphores:

   • mutex: Used for mutual exclusion to access the readCount variable.
   • write: Controls access for writers, ensuring that only one writer can access the resource at a time and blocking readers.
   • readMutex: Protects the readCount variable, ensuring that it is updated safely.

3. Reader Thread:

   • The reader increments the readCount and, if it’s the first reader, blocks writers.
   • After reading the shared resource, the reader decrements the readCount, allowing writers to proceed if it’s the last reader.

4. Writer Thread:

   • The writer waits for exclusive access (i.e., no readers or other writers) by acquiring the write semaphore.
   • It writes to the shared resource and releases the write semaphore when finished.

5. Main Function:

   • Initializes semaphores and creates reader and writer threads.
   • Joins the threads to ensure that they continue indefinitely.

Key Points:

• Readers Priority: Readers can read concurrently as long as no writers are writing, ensuring better throughput for read-heavy workloads.
• Writer Priority: Writers have exclusive access to the resource, and no readers can read while a writer is writing.
• Fairness: The semaphores ensure fairness, preventing starvation for both readers and writers.

Conclusion

The Reader-Writer Problem is an essential synchronization issue in operating systems and concurrent programming. It highlights the complexities of managing access to a shared resource when there are multiple processes that need to read and write concurrently. By using semaphores effectively, we can prevent race conditions, ensure mutual exclusion, and avoid issues like deadlock and starvation. This problem is widely applicable in database systems, file systems, and many multi-threaded applications.