Skip to content

README.md

Latest commit

 

History

History
228 lines (178 loc) · 16.6 KB

README.md

File metadata and controls

228 lines (178 loc) · 16.6 KB

Reader-Writer Problem (C Implementation with Pthreads)

A comprehensive simulation of the classic Reader-Writer Synchronization Problem using POSIX threads, mutexes, and semaphores for coordinated resource access.

What is the Reader-Writer Problem?

The Reader-Writer Problem is a fundamental synchronization challenge in operating systems that demonstrates how to manage concurrent access to a shared resource.

Imagine a shared library with multiple visitors:

  • Readers can enter and read books simultaneously (multiple readers don't interfere with each other).
  • Writers must have exclusive access (no other reader or writer can be present).
  • The Goal: Allow maximum concurrency while ensuring data consistency and preventing race conditions.

Key Concepts:

  • Read-Write Lock: A synchronization mechanism that permits multiple concurrent readers but only one writer.
  • Mutual Exclusion: Ensures that only one writer (or no readers when a writer is active) can access the resource.
  • Starvation Prevention: Both readers and writers should eventually get their turn.
  • Fairness: The system should balance between reader and writer priorities based on the chosen variant.

Architecture and Data Structures

This implementation uses POSIX threading libraries to demonstrate synchronization primitives in action.

1. Thread Model (pthread)

The program creates multiple threads:

  • Reader threads: Simulate processes reading from a shared resource.
  • Writer threads: Simulate processes writing to a shared resource.
  • Each thread has a unique ID, execution time, and synchronized access pattern.

2. Synchronization Primitives

a. Mutex (pthread_mutex_t)

pthread_mutex_t counter_mutex;
  • Protects the read_count variable from race conditions.
  • Ensures atomic operations when incrementing/decrementing reader count.
  • Prevents simultaneous modification of shared state.

b. Semaphore (sem_t)

sem_t writer_sem;
  • A binary semaphore initialized to 1 (unlocked state).
  • Controls exclusive access for writers.
  • The first reader acquires the semaphore; the last reader releases it.
  • Writers must acquire it before writing.

3. Shared State Variables

  • read_count: Tracks the number of active readers.
  • counter_mutex: Protects read_count from race conditions.
  • writer_sem: Guards write access and blocks writers when readers are active.

How the Algorithm Works (Step by Step)

Reader Process Flow:

  1. Acquire mutex to safely check and increment read_count.
  2. If first reader (read_count was 0), acquire the writer semaphore to block all writers.
  3. Release mutex to allow other readers to enter.
  4. Read the resource (simulated by sleep()).
  5. Re-acquire mutex to safely decrement read_count.
  6. If last reader (read_count becomes 0), release the writer semaphore to unblock waiting writers.
  7. Release mutex and terminate.

Writer Process Flow:

  1. Acquire writer semaphore (blocks if any reader or another writer is active).
  2. Write the resource (simulated by sleep()).
  3. Release writer semaphore to unblock waiting readers or writers.
  4. Terminate.

Synchronization Guarantee:

  • Multiple readers can execute concurrently.
  • Only one writer can execute at a time.
  • No reader and writer execute simultaneously.

Getting Started

Prerequisites

  • A C compiler (gcc, clang, or MSVC)
  • POSIX thread library (pthread.h)
  • Standard C libraries (stdio.h, stdlib.h, unistd.h)

On Windows:

  • MinGW or WSL2 for POSIX thread support
  • Or use MSVC with platform-specific adjustments

On Linux/macOS:

  • POSIX threads are built-in

Compilation

Linux/macOS:

gcc main.c -o reader_writer -pthread

Windows (MinGW):

gcc main.c -o reader_writer.exe -pthread

Windows (WSL2):

gcc main.c -o reader_writer -pthread
./reader_writer

Run

Linux/macOS:

./reader_writer

Windows (PowerShell):

.\reader_writer.exe

Example Output

When executed, the program displays interleaved reader and writer actions:

WE provided four process:
 three of which are readers and one is a writer 
 and arrived at the same time at 0s
Reader 0 is reading for 5s...
Reader 1 is reading for 8s...
Blocking any Writing processes, Because ....
Reader 2 is reading for 3s...
Reader 2 has finished.
Reader 0 has finished.
Reader 1 has finished.
Notifying Writers to commit, Because .....
Writer 3 is Writing for 6s...
Writer 3 has finished.

Output Interpretation:

  • "Blocking any Writing processes...": The first reader acquired the writer semaphore.
  • Multiple readers execute concurrently: Notice readers 0, 1, and 2 all start without blocking each other.
  • "Notifying Writers to commit...": The last reader released the writer semaphore.
  • Writer executes exclusively: Only after all readers finish, the writer begins.

Key Features

1. Reader Priority (First Variant)

  • The current implementation uses the "readers-preference" variant.
  • Once a reader arrives, incoming readers can proceed without waiting for the writer.
  • Potential Issue: Writers may starve if readers keep arriving.

2. Mutex-Protected Reader Count

  • read_count is protected by counter_mutex to prevent race conditions.
  • Ensures accurate tracking of active readers.

3. Semaphore-Based Writer Exclusion

  • writer_sem acts as a turnstile for writers.
  • The first reader blocks writers; the last reader unblocks them.

4. Deterministic Thread Ordering

  • Thread IDs (0, 1, 2, 3) provide predictable process identification.
  • Execution times are statically defined for reproducibility.

5. Proper Resource Cleanup

  • All threads are joined before destroying synchronization primitives.
  • Prevents resource leaks and undefined behavior.

Customization

Changing Thread Count

Modify the loop in main():

#define NUM_PROCESSES 4

Then adjust array sizes and reader/writer distribution.

Adjusting Execution Times

Update the execution_time array in main.c:

int execution_time[4] = {5, 8, 3, 6};  // execution times in seconds

Changing Reader-to-Writer Ratio

Modify the condition in the thread creation loop:

if (i == 3) {  // Change 3 to 2 for two writers, etc.
    pthread_create(&process_threads[i], NULL, writer, id);
} else {
    pthread_create(&process_threads[i], NULL, reader, id);
}

Writer-Preference Variant

To implement the "writer-preference" solution (preventing writer starvation):

  1. Add a second semaphore read_sem to block arriving readers when a writer is waiting.
  2. Track write_count (number of waiting writers).
  3. Modify reader entry/exit logic to check for waiting writers.

Advanced Concepts

Race Condition Prevention

  • Without mutex: Two readers could both see read_count == 0, both acquire writer_sem, causing inconsistency.
  • With mutex: Only one reader checks and modifies read_count at a time.

Semaphore Semantics

  • sem_wait(): Decrements the semaphore; blocks if it reaches 0.
  • sem_post(): Increments the semaphore; wakes a waiting thread if any exist.

Real-World Applications

  • Database systems: Multiple readers, exclusive writers (journaling).
  • Cache management: Reader threads query; writer threads invalidate.
  • Configuration servers: Many clients read; few services write updates.

Final Thoughts

This project demonstrates the core synchronization challenges in concurrent programming:

  • How mutexes protect critical sections.
  • How semaphores enforce mutual exclusion and ordering.
  • The importance of careful synchronization to prevent deadlock and race conditions.

It is a strong foundation for extending into:

  • Writer-preference or reader-preference analysis: Compare starvation behavior.
  • Multiple shared resources: Extend to a read-write lock library.
  • Performance analysis: Measure throughput under different workloads.
  • Deadlock detection: Add timeout mechanisms and circular wait detection.
  • Monitor pattern: Implement using condition variables instead of semaphores.