This repository contains implementations of three classic synchronization problems in concurrent programming. Each problem demonstrates different challenges in coordinating multiple threads and showcases various synchronization mechanisms.
The three synchronization problems covered in this project are:
- Dining Philosophers Problem
- Producer-Consumer Problem
- Reader-Writer Problem
Each problem is implemented using different synchronization primitives to demonstrate various approaches to thread coordination.
The Dining Philosophers Problem is a classic synchronization problem that illustrates challenges in resource allocation and deadlock prevention. The scenario involves:
- N philosophers sitting around a circular table
- N forks placed between each pair of adjacent philosophers
- Each philosopher alternates between thinking and eating
- To eat, a philosopher needs two forks (the one on their left and the one on their right)
- Deadlock: If all philosophers pick up their left fork simultaneously, they will wait indefinitely for the right fork
- Starvation: Some philosophers might never get a chance to eat if the scheduling is unfair
- Resource contention: Multiple philosophers competing for the same forks
Located in: Dining-Philosopher/semaphores/
This implementation uses semaphores to control access to forks and prevent deadlock.
The Producer-Consumer Problem (also known as the Bounded-Buffer Problem) involves:
- Producers: Threads that generate data items and place them in a shared buffer
- Consumers: Threads that remove and process data items from the shared buffer
- Shared buffer: A fixed-size buffer that stores items between production and consumption
- Buffer overflow: Producers must wait when the buffer is full
- Buffer underflow: Consumers must wait when the buffer is empty
- Race conditions: Concurrent access to the buffer must be synchronized
- Mutual exclusion: Only one thread should modify the buffer at a time
Located in: Producer-Consumer/
This problem is implemented using three different synchronization mechanisms:
- Semaphores (
semaphores/): Uses counting semaphores to track empty and full buffer slots - Locks (
locks/): Uses mutex locks to ensure mutual exclusion - Conditionals (
conditionals/): Uses condition variables to signal when the buffer state changes
The Reader-Writer Problem models a scenario where:
- Readers: Threads that only read shared data (multiple readers can read simultaneously)
- Writers: Threads that modify shared data (writers need exclusive access)
- Shared resource: Data that can be read by multiple threads or written by one thread
- Concurrent reads: Multiple readers should be able to access the resource simultaneously
- Exclusive writes: Writers need exclusive access (no readers or other writers)
- Priority: Deciding whether readers or writers get priority when both are waiting
- Starvation: Ensuring fairness so that neither readers nor writers are starved
Located in: Reader-Writer/
This problem is implemented using two different synchronization mechanisms:
- Semaphores (
semaphores/): Uses semaphores to control access patterns - Locks and Conditionals (
locks-and-conditionals/): Uses mutex locks and condition variables for more fine-grained control
- Counting semaphores: Track the number of available resources
- Binary semaphores: Act as mutex locks (0 or 1)
- Useful for signaling and resource counting
- Provide mutual exclusion
- Ensure only one thread can execute a critical section at a time
- Simple and efficient for basic synchronization
- Allow threads to wait for specific conditions to become true
- Used with locks to implement more complex synchronization patterns
- Enable efficient waiting and signaling between threads
Synchronizing-Threads/
├── Dining-Philosopher/
│ └── semaphores/
├── Producer-Consumer/
│ ├── conditionals/
│ ├── locks/
│ └── semaphores/
├── Reader-Writer/
│ ├── locks-and-conditionals/
│ └── semaphores/
└── README.md
By studying these implementations, you will learn:
- How to identify and prevent deadlocks
- Techniques for avoiding race conditions
- Different synchronization primitives and when to use them
- Trade-offs between different synchronization approaches
- How to design thread-safe concurrent programs
A situation where two or more threads are blocked forever, waiting for each other to release resources.
A situation where the behavior of a program depends on the relative timing of events, leading to unpredictable results.
A situation where a thread is perpetually denied access to resources it needs, even though other threads are making progress.
A situation where threads are actively trying to resolve a conflict but end up repeating the same actions without making progress.
These are fundamental problems in concurrent programming and are covered in:
- Operating Systems textbooks
- Concurrent Programming courses
- System Design interviews
Each problem serves as a building block for understanding more complex synchronization scenarios in real-world applications.