Session 3.3: High-Level Synchronization Tools

Exploring semaphores, mutex locks, monitors, and classic synchronization problems

Module 3 2.5 Hours Theory

Learning Objectives

By the end of this session, you will be able to:
  • Understand semaphores and their operations
  • Distinguish between counting and binary semaphores
  • Implement mutex locks for mutual exclusion
  • Explain monitors and condition variables
  • Solve classic synchronization problems
  • Analyze Producer-Consumer, Readers-Writers, and Dining Philosophers problems
Key Concept

High-level synchronization tools provide abstractions that make it easier to write correct concurrent programs while hiding the complexity of low-level synchronization mechanisms.

Semaphores

A semaphore is a synchronization primitive that maintains a counter and provides two atomic operations: wait() and signal().

Semaphore Operations

// Semaphore structure
typedef struct {
    int value;
    struct process *list;  // waiting queue
} semaphore;

// Wait operation (P operation, acquire)
wait(semaphore *S) {
    S->value--;
    if (S->value < 0) {
        // Add this process to S->list
        block();  // Block the process
    }
}

// Signal operation (V operation, release)  
signal(semaphore *S) {
    S->value++;
    if (S->value <= 0) {
        // Remove a process P from S->list
        wakeup(P);  // Wake up the process
    }
}
Counting Semaphores
  • Value can be any non-negative integer
  • Used to control access to multiple resources
  • Initial value = number of available resources
Binary Semaphores (Mutex)
  • Value can only be 0 or 1
  • Used for mutual exclusion
  • Similar to a lock mechanism

Mutex Locks

Mutex (mutual exclusion) locks provide a simple mechanism for protecting critical sections by ensuring only one thread can hold the lock at a time.

Mutex Implementation

// Mutex structure
typedef struct {
    boolean available;
    struct process *owner;
} mutex_lock;

// Acquire the lock
acquire(mutex_lock *lock) {
    while (!lock->available);  // Busy wait
    lock->available = false;
    lock->owner = current_process;
}

// Release the lock  
release(mutex_lock *lock) {
    if (lock->owner == current_process) {
        lock->available = true;
        lock->owner = NULL;
    }
}

// Usage example
mutex_lock mutex;

do {
    acquire(&mutex);
    
    // Critical Section
    
    release(&mutex);
    
    // Remainder Section
} while (true);
Mutex vs Binary Semaphore
  • Ownership: Mutex has ownership concept, semaphore doesn't
  • Release: Only lock owner can release mutex
  • Priority: Mutex can support priority inheritance
  • Recursion: Recursive mutexes allow same thread to acquire multiple times

Monitors

A monitor is a high-level synchronization construct that encapsulates shared data and the procedures that operate on it, ensuring mutual exclusion automatically.

Monitor Structure

monitor BoundedBuffer {
    int buffer[N];
    int count = 0;
    int in = 0, out = 0;
    
    condition full, empty;
    
    procedure insert(item) {
        if (count == N)
            wait(full);
        
        buffer[in] = item;
        in = (in + 1) % N;
        count++;
        
        signal(empty);
    }
    
    procedure remove() {
        if (count == 0)
            wait(empty);
        
        item = buffer[out];
        out = (out + 1) % N;
        count--;
        
        signal(full);
        return item;
    }
}
Monitor Properties
  • Automatic mutual exclusion
  • Condition variables for synchronization
  • Structured programming approach
  • Compiler-enforced safety
Condition Variables
  • wait(): Block until condition is true
  • signal(): Wake up one waiting process
  • broadcast(): Wake up all waiting processes

Producer-Consumer Problem

Problem Description

Producer processes generate data and place items in a shared buffer. Consumer processes remove items from the buffer. The buffer has finite capacity.

Semaphore Solution

// Shared data
int buffer[BUFFER_SIZE];
int in = 0, out = 0;

// Semaphores
semaphore mutex = 1;      // Mutual exclusion
semaphore empty = BUFFER_SIZE;  // Count of empty slots
semaphore full = 0;       // Count of full slots

// Producer Process
do {
    // Produce item
    
    wait(empty);    // Wait for empty slot
    wait(mutex);    // Enter critical section
    
    buffer[in] = item;
    in = (in + 1) % BUFFER_SIZE;
    
    signal(mutex);  // Exit critical section
    signal(full);   // Signal item available
} while (true);

// Consumer Process
do {
    wait(full);     // Wait for item
    wait(mutex);    // Enter critical section
    
    item = buffer[out];
    out = (out + 1) % BUFFER_SIZE;
    
    signal(mutex);  // Exit critical section
    signal(empty);  // Signal slot available
    
    // Consume item
} while (true);

Readers-Writers Problem

Problem Description

Multiple processes want to access a shared database. Readers only read data, writers modify data. Allow concurrent reads, exclusive writes.

First Readers-Writers Solution

// Shared data
int readcount = 0;

// Semaphores  
semaphore mutex = 1;     // Protect readcount
semaphore wrt = 1;       // Writer exclusion

// Reader Process
do {
    wait(mutex);
    readcount++;
    if (readcount == 1)  // First reader blocks writers
        wait(wrt);
    signal(mutex);
    
    // Reading is performed
    
    wait(mutex);
    readcount--;
    if (readcount == 0)  // Last reader allows writers
        signal(wrt);
    signal(mutex);
} while (true);

// Writer Process  
do {
    wait(wrt);
    
    // Writing is performed
    
    signal(wrt);
} while (true);
Starvation Problem

In the first solution, writers may starve if readers keep arriving. The second solution gives priority to writers, but then readers may starve.

Dining Philosophers Problem

Problem Description

Five philosophers sit around a circular table. Each philosopher alternates between thinking and eating. To eat, a philosopher needs both adjacent forks (chopsticks).

Incorrect Solution (Causes Deadlock)

// Semaphores for forks
semaphore fork[5] = {1, 1, 1, 1, 1};

// Philosopher i
do {
    wait(fork[i]);         // Pick up left fork
    wait(fork[(i+1) % 5]); // Pick up right fork
    
    // Eat
    
    signal(fork[(i+1) % 5]); // Put down right fork
    signal(fork[i]);         // Put down left fork
    
    // Think
} while (true);

// DEADLOCK: All philosophers pick up left fork simultaneously!

Correct Solutions

Solution 1: Asymmetric Approach
// Even philosophers pick left fork first
// Odd philosophers pick right fork first
if (i % 2 == 0) {
    wait(fork[i]);         // Left first
    wait(fork[(i+1) % 5]); // Then right
} else {
    wait(fork[(i+1) % 5]); // Right first
    wait(fork[i]);         // Then left
}
Solution 2: Limit Concurrent Dining
// Allow only 4 philosophers to try eating simultaneously
semaphore dining_room = 4;

do {
    wait(dining_room);  // Enter dining room
    wait(fork[i]);
    wait(fork[(i+1) % 5]);
    
    // Eat
    
    signal(fork[(i+1) % 5]);
    signal(fork[i]);
    signal(dining_room);  // Leave dining room
    
    // Think
} while (true);

Session Summary

Key Takeaways:
  • Semaphores: Provide a flexible synchronization mechanism with wait() and signal() operations
  • Mutex Locks: Offer simpler mutual exclusion with ownership semantics
  • Monitors: Encapsulate shared data and provide automatic synchronization
  • Condition Variables: Allow processes to wait for specific conditions in monitors
  • Classic Problems: Demonstrate common synchronization patterns and solutions
  • Trade-offs: Compare different synchronization tools and strategies
Study Tips:
  • Practice implementing semaphore solutions for different scenarios
  • Understand the difference between counting and binary semaphores
  • Work through the classic problems step by step
  • Identify potential deadlock situations and prevention strategies
Next Session:

Session 3.4: Deadlock Fundamentals
System model, deadlock characterization, and resource allocation graphs

Previous Session Next Session