Classical IPC Problems

1. Introduction to Classical IPC Problems

These are well-known synchronization challenges used to test and demonstrate synchronization primitives like semaphores, mutexes, and monitors. They highlight potential issues in concurrent programming such as deadlock, starvation, and data inconsistency.

2. Producer-Consumer Problem (Bounded-Buffer Problem)

This problem involves processes that produce data (producers) and processes that consume data (consumers) using a shared, fixed-size buffer.

2.1 Problem Description

  • Producers: Generate items and add them to the buffer.

  • Consumers: Remove items from the buffer and process them.

  • Buffer: A shared memory area with a limited capacity (bounded).

2.2 Challenges

  • Buffer Full: Producers must wait if the buffer is full.

  • Buffer Empty: Consumers must wait if the buffer is empty.

  • Race Condition: Multiple producers/consumers accessing the buffer simultaneously can lead to inconsistent data.

2.3 Synchronization using Semaphores

  • mutex: A binary semaphore initialized to 11, used for mutual exclusion to protect the buffer itself (ensures only one process accesses the buffer at a time).

  • empty: A counting semaphore initialized to the size of the buffer, representing the number of empty slots.

  • full: A counting semaphore initialized to 00, representing the number of filled slots.

2.4 Producer Process Logic

  1. wait(empty): Decrements empty. If 00, waits until a slot is available.

  2. wait(mutex): Acquires lock for buffer access.

  3. Produce Item: Adds item to buffer.

  4. signal(mutex): Releases lock.

  5. signal(full): Increments full, signaling that a slot is filled.

2.5 Consumer Process Logic

  1. wait(full): Decrements full. If 00, waits until an item is available.

  2. wait(mutex): Acquires lock for buffer access.

  3. Consume Item: Removes item from buffer.

  4. signal(mutex): Releases lock.

  5. signal(empty): Increments empty, signaling that a slot is now empty.

3. Dining Philosophers Problem

This problem illustrates a classic synchronization challenge involving resource allocation and deadlock.

3.1 Problem Description

  • Philosophers: 55 philosophers sit around a circular table.

  • Chopsticks: 55 chopsticks are placed between each pair of philosophers.

  • Actions: Each philosopher alternately thinks (does not need chopsticks) and eats (needs two chopsticks: one from their left and one from their right).

3.2 Challenges

  • Deadlock: If all philosophers pick up their left chopstick simultaneously, they will all wait for their right chopstick indefinitely, leading to a system-wide halt.

  • Starvation: Even if deadlock is avoided, some philosopher might repeatedly miss out on eating due to unfavorable scheduling.

3.3 Solutions to Prevent Deadlock

  1. Resource Ordering (Asymmetric Solution): Assign an order to the chopsticks. Philosophers try to pick up the lower-numbered chopstick first, then the higher-numbered one. This breaks the circular wait condition.

  2. Arbitrator/Waiter: Introduce a central coordinator (arbitrator) that ensures only N-1 philosophers can attempt to pick up chopsticks at any given time. This guarantees at least one philosopher can always pick up both chopsticks.

  3. Allow Eating Only if Both Available: A philosopher only picks up chopsticks if both are immediately available. This avoids a philosopher holding one chopstick while waiting for another.

4. Readers-Writers Problem

This problem deals with multiple processes attempting to read from or write to a shared data resource concurrently.

4.1 Problem Description

  • Readers: Multiple readers can access the shared data concurrently without causing inconsistency issues.

  • Writers: Only one writer can modify the shared data at a time to maintain data integrity. No readers can access the data while a writer is writing, and no writer can access while another writer or any reader is accessing.

4.2 Challenges

  • Reader Starvation: If writers are given preference, a continuous stream of writers might prevent readers from ever accessing the data.

  • Writer Starvation: If readers are given preference, a continuous stream of readers might prevent writers from ever modifying the data.

4.3 Variants and Synchronization

  1. First Readers-Writers Problem (Readers Preference):

    • New readers are granted access immediately if other readers are present.

    • Writers can starve if there's a constant influx of readers.

    • Synchronization: Uses a mutex for read_count (number of active readers) and rw_mutex for writers and the first/last reader.

      • rw_mutex: Initialized to 11, controls access to the shared resource itself, ensuring only one writer or at least one reader can access.

      • mutex: Initialized to 11, protects updates to read_count.

      • read_count: Integer variable initialized to 00.

  2. Second Readers-Writers Problem (Writers Preference):

    • If a writer is waiting, new readers are blocked to allow the writer to access the resource as soon as possible.

    • Readers can starve if there's a continuous stream of writers.

    • Synchronization: More complex, involving additional semaphores to prioritize writers, ensuring a waiting writer gets access before new readers.