Monitors, Condition Variables, and Readers-Writers

Motivation for Monitors

Overview

Monitors address the limitations of semaphores and provide a more structured mechanism for handling synchronization in concurrent programming. This approach helps to distinctly differentiate between the concerns of mutual exclusion and scheduling of threads.

Key Concepts

Semaphores vs. Monitors

Semaphores have been widely used for synchronization in computer science but can be complex, as they serve dual purposes: managing mutual exclusion (making sure only one thread accesses a resource at a time) and scheduling (determining which thread resumes after blocking). Monitors simplify this by isolating these two functions.

Definition of a Monitor

A monitor consists of:

• A lock that provides mutual exclusion to shared data.

• Condition variables that allow waiting threads to be managed within critical sections of code.

Lock Mechanism

A lock provides mechanisms to synchronize access to shared resources. It has two fundamental operations:

1. Lock::Acquire(): Blocks the thread until the lock is available. Once available, it locks access.

2. Lock::Release(): Unlocks the lock and wakes up a thread that may be waiting to acquire the lock.

• The lock is initially in a free state, allowing the first calling thread to access the resource it protects.

Best Practices for Locks

• Always acquire a lock before accessing any shared data structures to prevent race conditions.

• Release the lock immediately after the operation is complete to ensure that other threads can proceed unhindered.

Example Usage of Locks

AddToBuffer() {
    Lock.Acquire();   // Request access to the buffer
    // Critical section to add an item to the buffer
    Lock.Release();   // Release the lock after modifying the buffer
}

RemoveFromBuffer() {
    Lock.Acquire();   // Request access to the buffer
    // Critical section to remove an item from the buffer only if it exists
    Lock.Release();   // Release the lock after modifying the buffer
    return item;
}

Condition Variables

Condition variables enhance synchronization by allowing threads to wait for certain conditions within a locked context, minimizing the waiting time without holding on to the lock unnecessarily.

• Using condition variables, a thread can atomically release the acquired lock and sleep while waiting for a condition to be signaled. The lock is reacquired automatically upon waking up.

Operations Associated with Condition Variables

1. Wait(): Atomically releases the lock and puts the thread to sleep until another thread signals it.

2. Signal(): Wakes up one thread from the waiting queue if any are present.

3. Broadcast(): Wakes up all threads waiting on that condition variable.

• These operations must only be performed while holding the associated lock to maintain thread safety.

Example Usage of Condition Variables

AddToBuffer() {
    lock.Acquire();   // Lock the buffer
    // Add one item to the buffer
    condition.Broadcast(&lock); // Notify waiting threads that an item has been added
    lock.Release();   // Release the lock
}

RemoveFromBuffer() {
    lock.Acquire();
    while (nothing in the buffer) {  // Wait for the buffer to have an item
        condition.Wait(&lock);  // Wait here; lock is released during wait
    }
    lock.Release();   // Release the lock once done
    return item;  // Return the item removed from the buffer
}

Understanding Hoare vs. Mesa Monitors

Hoare Monitors

• Common in academic contexts, these monitors transfer control from the signaling thread directly to the waiting thread upon signaling, which can be efficient but can lead to busy-wait scenarios.

Mesa Monitors

• More common in real-world operating systems, they only place the waiting thread into the ready queue. When the signaling thread releases the lock, the waiting thread must retest the condition it was waiting for, as the circumstances may have changed by then.

Solving the Readers-Writers Problem

The readers-writers problem is a classic issue in database management where we have:

• Readers: Threads that read data without modifying it.

• Writers: Threads that read and modify data.

In this problem, we allow multiple readers to access the database simultaneously, but we restrict access to one writer at a time to prevent data inconsistencies.

Conditions for Access:

• A reader must wait if a writer is currently accessing or is in the process of accessing the database.

• A writer must wait if there is any current reader or writer accessing the database.

• Global state modifications must also be synchronized to maintain integrity.

Basic Structure of the Solution

• Reader:

• Waits for no active writers.

• Accesses the database to read its contents.

• Notifies waiting writers once finished.

• Writer:

• Waits for no active readers or writers.

• Accesses the database to modify its contents.

• Notifies waiting threads upon completion.

Semaphores vs. Monitors

While monitors can be implemented using semaphores, it is important to note key differences. Condition variables are designed for use inside a lock, whereas semaphores can cause deadlocks if misused.

• Condition variables do not maintain history; signaling an empty condition queue has no effect on subsequent waits.

• When using semaphores, a Wait() may block indefinitely depending on if the semaphore's value reflects the required state.

Conclusion

Monitors provide a more intuitive and structured approach to synchronization in concurrent programming compared to semaphores. By focusing on locking mechanisms alongside condition variables, monitors simplify the reasoning about how threads interact and access shared data, ultimately enhancing the robustness of multi-threaded applications.