Monitor Pattern in Operating Systems

Synchronization is a core concept in operating system theory and multi-threaded programming. Using mutex or semaphore directly to handle complex systems is challenging and error-prone because you must carefully design the order of acquiring locks to avoid deadlock problems. To address this, computer science textbooks introduce a design pattern called monitor, which provides a higher-level abstraction for thread synchronization.

What is a Monitor?

A monitor is a synchronization construct that combines:

• A container (typically implemented as a class in high-level programming languages)
• Encapsulated data and operations on that data
• Mutual exclusion - only one thread can execute inside the monitor at a time
• Condition variables for thread coordination

Key characteristics of monitors:

• Mutual Exclusion: Only one thread can be active inside the monitor at any given time
• Encapsulation: Internal data is protected and can only be accessed through monitor procedures
• Condition Synchronization: Threads can wait for specific conditions and be notified when those conditions become true

Note that while the basic monitor ensures only one thread executes at a time, you can design more complex monitors with fine-grained locking:

class MultiMonitor {
    private final Object lock1 = new Object();
    private final Object lock2 = new Object();

    public void operation1() {
        // Some operations...
        synchronized(lock1) {
            // Critical section 1
        }
    }

    public void operation2() {
        // Some operations...
        synchronized(lock2) {
            // Critical section 2
        }
    }
}

In this example, two different threads can call operation1() and operation2() simultaneously since these methods use different lock objects.

Note: Monitors are suitable for most thread-safe situations. For performance-critical real-time systems, you may need to implement synchronization using low-level atomic operations for performance optimization.

Example 1: The Bounded-Buffer Problem

The bounded-buffer problem is a classic Producer-Consumer synchronization problem. Producers add items to a buffer, and consumers remove items from it. The challenge is managing the buffer when it becomes full (producers must wait) or empty (consumers must wait).

Here’s a monitor solution using C++-like pseudocode:

monitor BoundedBuffer {
private:
    int capacity;
    int size = 0;
    condition notEmpty;
    condition notFull;
    array<int> buffer;
    int front = 0, rear = 0;

public:
    void produce(int item) {
        if (size == capacity) {
            wait(notFull); // Buffer is full, block here
        }
        
        buffer[rear] = item;
        rear = (rear + 1) % capacity;
        ++size;
        
        signal(notEmpty); // Wake up one waiting consumer
    }

    int consume() {
        if (size == 0) {
            wait(notEmpty); // Buffer is empty, block here
        }
        
        int item = buffer[front];
        front = (front + 1) % capacity;
        --size;
        
        signal(notFull); // Wake up one waiting producer
        return item;
    }
}

This monitor provides two public functions: produce() and consume(). Clients can only access the buffer through these methods. Every public operation in a monitor is automatically protected by mutual exclusion - when a thread enters any monitor procedure, it acquires the monitor’s lock and releases it when the procedure exits.

The notEmpty and notFull are condition variables that manage waiting queues. The size counter tracks how many items are currently in the buffer.

Example 2: The Readers-Writers Problem

The readers-writers problem has several variations. The first variation has these requirements:

1. Multiple readers can read simultaneously
2. Only one writer can write at a time
3. Readers and writers cannot access the resource simultaneously

First Readers-Writers Solution

monitor ReadersWriters_1 {
private:
    int read_count = 0;
    bool writing = false;
    condition canRead;
    condition canWrite;

public:
    void startRead() {
        if (writing) {
            wait(canRead);
        }
        ++read_count;
        signal(canRead); // Allow other readers to proceed
    }

    void endRead() {
        --read_count;
        if (read_count == 0) {
            signal(canWrite); // Last reader signals waiting writers
        }
    }

    void startWrite() {
        if (writing || read_count > 0) {
            wait(canWrite);
        }
        writing = true;
    }

    void endWrite() {
        writing = false;
        signal(canRead);  // Wake up waiting readers
        signal(canWrite); // Wake up waiting writers
    }
}

This solution uses two member variables (read_count and writing) to track the current state and two condition variables (canRead and canWrite) for waiting threads.

Note: This variation can cause writer starvation if readers continuously arrive.

Second Readers-Writers Solution (Writer Priority)

monitor ReadersWriters_2 {
private:
    int read_count = 0;      // Active readers
    int waiting_writers = 0; // Waiting writers
    bool writing = false;
    condition canRead;
    condition canWrite;

public:
    void startRead() {
        if (writing || waiting_writers > 0) {
            wait(canRead); // Block if writer is active or waiting
        }
        ++read_count;
        signal(canRead); // Allow other readers to join
    }

    void endRead() {
        --read_count;
        if (read_count == 0) {
            signal(canWrite); // No active readers, allow writer to proceed
        }
    }

    void startWrite() {
        ++waiting_writers;
        if (writing || read_count > 0) {
            wait(canWrite); // Block if there are active readers or writers
        }
        --waiting_writers;
        writing = true;
    }

    void endWrite() {
        writing = false;
        if (waiting_writers > 0) {
            signal(canWrite); // Priority to waiting writers
        } else {
            signal(canRead);  // No waiting writers, allow readers
        }
    }
}

This implementation adds a waiting_writers counter to give priority to writers. However, this can cause reader starvation if writers keep arriving.

Example 3: The Dining-Philosophers Problem

The classic dining-philosophers problem involves five philosophers sitting around a table with five chopsticks. Each philosopher needs two chopsticks (left and right) to eat. The challenge is to prevent deadlock while allowing maximum concurrency.

Basic Solution

monitor DiningPhilosopher {
private:
    enum State {THINKING, EATING, HUNGRY};
    State state[5] = {THINKING}; // Track each philosopher's state
    condition self[5];           // One condition per philosopher

public:
    void pickup(int i) {
        state[i] = HUNGRY;
        test(i);
        if (state[i] != EATING) {
            wait(self[i]);
        }
    }

    void putdown(int i) {
        state[i] = THINKING;
        test((i + 4) % 5); // Test left neighbor
        test((i + 1) % 5); // Test right neighbor
    }

private:
    void test(int i) {
        if (state[i] == HUNGRY &&
            state[(i + 4) % 5] != EATING &&
            state[(i + 1) % 5] != EATING) {
            state[i] = EATING;
            signal(self[i]);
        }
    }
}

This solution prevents deadlock by only allowing a philosopher to pick up chopsticks when both neighbors are not eating. Each philosopher has a dedicated condition variable for synchronization.

Starvation-Free Solution

The basic solution can still cause starvation. Here’s an improved version that prevents starvation:

monitor DiningPhilosopher {
private:
    enum State {THINKING, EATING, HUNGRY};
    State state[5] = {THINKING};
    condition self[5];
    queue<int> hungry_queue; // FIFO queue for fairness

public:
    void pickup(int i) {
        state[i] = HUNGRY;
        hungry_queue.push(i); // Join the fairness queue
        test(i);
        if (state[i] != EATING) {
            wait(self[i]);
        }
    }

    void putdown(int i) {
        state[i] = THINKING;
        // Check all hungry philosophers in order
        for (int j : hungry_queue) {
            test(j);
        }
    }


private:
    void test(int i) {
        int left = (i + 4) % 5;
        int right = (i + 1) % 5;

        bool leftInFront  = hungry_queue.contains(left)  && hungry_queue.indexOf(left)  < hungry_queue.indexOf(i);
        bool rightInFront = hungry_queue.contains(right) && hungry_queue.indexOf(right) < hungry_queue.indexOf(i);
        
        if (state[i] == HUNGRY &&
            state[left] != EATING &&
            state[right] != EATING &&
            !leftInFront && !rightInFront) {
            state[i] = EATING;
            signal(self[i]);
            hungry_queue.remove(i); // Remove from queue after eating
        }
    }
}

This solution adds a FIFO queue to ensure fairness. Philosophers are served in the order they become hungry, preventing starvation.

Conclusion

Monitors provide a clean, high-level abstraction for thread synchronization. They encapsulate both data and the operations on that data, ensuring thread safety through mutual exclusion and providing condition variables for complex coordination. While the examples shown use pseudocode, most modern programming languages provide monitor-like constructs (such as synchronized methods in Java or lock-based classes in C++).

The key advantages of monitors are:

• Simplicity: Easier to use than low-level primitives like mutexes and semaphores
• Safety: Automatic mutual exclusion reduces the risk of race conditions
• Structure: Clear separation between data and synchronization logic

When designing concurrent systems, consider using monitor patterns for clean, maintainable synchronization solutions.