CC-311›Synchronization Problems

Operating SystemsTopic 14 of 34

Synchronization Problems

8 minread

1,320words

Intermediatelevel

Synchronization Problems in Operating Systems

In multi-threaded and multi-process environments, synchronization is critical to ensure that concurrent processes or threads do not interfere with each other when accessing shared resources. Without proper synchronization, issues like race conditions, deadlocks, and resource contention can arise, leading to unexpected behavior and errors. These issues are known as synchronization problems, and they are essential for understanding how to manage concurrency and ensure the correct execution of programs.

Common Synchronization Problems

Critical Section Problem
Producer-Consumer Problem
Readers-Writers Problem
Dining Philosophers Problem
Sleeping Barber Problem
Mutual Exclusion Problem

1. Critical Section Problem

Problem Overview:

The Critical Section Problem arises when multiple processes or threads need access to shared resources (like variables, files, or devices). The critical section refers to the part of the program where these shared resources are accessed and potentially modified.

To ensure the consistency and correctness of the data, only one process or thread should be allowed to execute in the critical section at a time. The challenge is to implement a synchronization mechanism that enforces this mutual exclusion without introducing other problems like starvation or deadlock.

Key Requirements:

Mutual Exclusion: Only one thread can be in the critical section at any given time.
Progress: If no thread is in the critical section and one or more threads want to enter, one of them must eventually be allowed to do so.
Bounded Waiting: A thread that requests entry to the critical section must not be delayed indefinitely by other threads.

Solution Approaches:

Locks: Using mutual exclusion locks (mutexes) to ensure that only one thread can enter the critical section at a time.
Semaphores: Semaphores can be used to signal when a thread can enter or leave the critical section.
Monitors: Higher-level constructs that encapsulate shared resources and ensure that only one thread accesses the critical section at a time.

2. Producer-Consumer Problem

Problem Overview:

The Producer-Consumer Problem involves two types of processes: producers and consumers. The producers generate data and store it in a shared buffer, while consumers retrieve and process the data. The challenge is to ensure that producers do not produce data when the buffer is full and that consumers do not consume data when the buffer is empty. Additionally, mutual exclusion must be enforced on access to the buffer to prevent race conditions.

Key Requirements:

Mutual Exclusion: Access to the buffer must be synchronized to prevent concurrent access by producers and consumers.
Synchronization: Producers must wait if the buffer is full, and consumers must wait if the buffer is empty.
Buffer Management: The buffer must be large enough to store data, but also need to manage space when items are added or removed.

Solution Approaches:

Semaphores: Use a full semaphore to keep track of the number of filled slots and an empty semaphore to track the number of empty slots in the buffer.
Mutex: A mutex lock is used to protect the critical section that involves modifying the shared buffer.

Example of semaphores used to solve this problem:

semaphore mutex = 1;    // Protects the shared buffer
semaphore full = 0;     // Keeps track of filled slots
semaphore empty = N;    // Keeps track of empty slots

// Producer:
wait(empty);
wait(mutex);
produce_item();
signal(mutex);
signal(full);

// Consumer:
wait(full);
wait(mutex);
consume_item();
signal(mutex);
signal(empty);

3. Readers-Writers Problem

Problem Overview:

The Readers-Writers Problem involves a shared resource that can be read by multiple readers simultaneously but must be written to by only one writer at a time. The problem is to synchronize the readers and writers to ensure:

Multiple readers can read the shared resource concurrently.
If a writer is writing, no readers or other writers should access the resource.

There are two versions of the readers-writers problem:

First-Come, First-Served (FCFS) Solution: This allows writers to acquire the resource when there are no active readers. However, this can lead to starvation, where readers can be locked out indefinitely if there are always writers trying to write.
Priority to Writers: In this solution, writers are given priority over readers. Writers will always be allowed to proceed if they are waiting, preventing starvation of writers but may cause readers to starve.

Solution Approaches:

Semaphores: Use semaphores to manage the readers and writers.
Mutexes and Condition Variables: A mutex can be used to manage the access to the shared resource, while condition variables can be used to signal when readers or writers can proceed.

Example with priority to writers:

semaphore mutex = 1;    // Protects read_count
semaphore write_lock = 1; // Ensures mutual exclusion for writing
int read_count = 0;     // Keeps track of number of readers

// Reader:
wait(mutex);
read_count++;
if (read_count == 1) 
    wait(write_lock);   // Block writers when the first reader arrives
signal(mutex);
// Read the shared resource
wait(mutex);
read_count--;
if (read_count == 0) 
    signal(write_lock); // Allow writers when the last reader leaves
signal(mutex);

// Writer:
wait(write_lock);
// Write the shared resource
signal(write_lock);

4. Dining Philosophers Problem

Problem Overview:

The Dining Philosophers Problem is a classic synchronization problem that illustrates the difficulties of allocating resources in a way that avoids deadlock, starvation, and ensures mutual exclusion. In this problem, five philosophers are sitting at a round table, thinking and occasionally eating. To eat, a philosopher needs two forks, one on the left and one on the right. The challenge is to ensure that:

Philosophers do not starve.
Deadlock (where no philosopher can eat because each is holding one fork) is avoided.
Only one philosopher can use each fork at a time.

Solution Approaches:

Semaphores and Mutexes: Philosophers can use semaphores or mutexes to ensure mutual exclusion when accessing the shared forks and avoid deadlocks by introducing conditions like asymmetric picking of forks (e.g., one philosopher picks up the left fork first, while others pick up the right fork first).
Resource Hierarchy: Philosophers pick up the forks in a particular order, which prevents cyclic dependencies and, thus, deadlock.

5. Sleeping Barber Problem

Problem Overview:

In the Sleeping Barber Problem, there is a barber who cuts hair and a waiting room with several chairs. The barber sleeps when there are no customers, and when a customer arrives, they either sit in the waiting room or leave if it is full. The challenge is to manage the barber and customer interactions to avoid race conditions and ensure smooth operation.

Solution Approaches:

Semaphores: Use semaphores to manage the customer queue and the barber’s sleep/wake status.
Mutexes: A mutex can be used to protect the critical section where customers are added or removed from the waiting room.

6. Mutual Exclusion Problem

Problem Overview:

The Mutual Exclusion Problem is a more general version of the critical section problem. It ensures that no two processes can be in the critical section simultaneously, which is a fundamental aspect of synchronization. It is a problem of guaranteeing that only one process/thread can access a shared resource at a time.

Solution Approaches:

Locks (Mutexes): Locks are the most commonly used approach to enforce mutual exclusion, where only one thread can acquire the lock and enter the critical section.
Semaphores: A binary semaphore (value of 1 or 0) can also be used to control mutual exclusion in critical sections.

Conclusion

Synchronization problems are essential to understanding how operating systems and concurrent systems function correctly. These problems arise when multiple processes or threads share resources and need to be coordinated to avoid conflicts, such as race conditions or deadlocks. Various classic problems, such as the Critical Section Problem, Producer-Consumer Problem, Readers-Writers Problem, Dining Philosophers Problem, and Sleeping Barber Problem, offer frameworks to understand and design synchronization mechanisms.

The key to solving these problems is the use of synchronization techniques like semaphores, mutexes, monitors, and condition variables, which help ensure mutual exclusion, progress, and fairness in concurrent systems.

Previous topic 13

Synchronization Hardware

Next topic 15

Deadlocks

Past Papers

Open this section to load past papers

Click on Show Past Papers to see past papers.

semaphore mutex = 1; // Protects the shared buffer semaphore full = 0; // Keeps track of filled slots semaphore empty = N; // Keeps track of empty slots // Producer: wait(empty); wait(mutex); produce_item(); signal(mutex); signal(full); // Consumer: wait(full); wait(mutex); consume_item(); signal(mutex); signal(empty);

semaphore mutex = 1; // Protects read_count semaphore write_lock = 1; // Ensures mutual exclusion for writing int read_count = 0; // Keeps track of number of readers // Reader: wait(mutex); read_count++; if (read_count == 1) wait(write_lock); // Block writers when the first reader arrives signal(mutex); // Read the shared resource wait(mutex); read_count--; if (read_count == 0) signal(write_lock); // Allow writers when the last reader leaves signal(mutex); // Writer: wait(write_lock); // Write the shared resource signal(write_lock);