• Dining Philosphers: Not So Hungery After All
  • Background
  • Scenario
• Visual Trace Exercise: Deadlock When Full
  • Background: Circular Wait with Semaphores
  • Scenario
  • Visual Timeline Example
• Missed Notify with Separate Lock and Premature Signal
  • Background
  • Recap: Java Monitors and Intrinsic Synchronization
    • Mutex
    • Condition Synchronization
  • Scenario
• Can This Bounded Buffer Deadlock?
  • Background
  • Scenario
• Circular Wait in Print Spooler and Scanner
  • Background
  • Scenario
• Banker’s Algorithm: Approve or Deny?
  • Background
  • Scenario
    • Allocation Matrix
    • Max Matrix
• The Banker’s Mistake
  • Background
  • Scenario
  • Answer the following questions
• The Unsafe Shortcut
  • Background
  • Scenario
• Hidden Cycles in Resource Allocation Graph
  • Background
  • Scenario
• Dining Savages with Broken Pot Semaphore
  • Background
  • Scenario
  • Epilogue
• Preemption and Priority Inversion in Lock Acquisition
  • Background
  • Scenario
• The Ostrich Algorithm
  • Background
  • Scenario

50.005 Computer System Engineering
Information Systems Technology and Design
Singapore University of Technology and Design
Natalie Agus (Summer 2025)

Deadlock

Dining Philosphers: Not So Hungery After All

Background

The Dining Philosophers Problem is a classic illustration of deadlock and resource contention. Five philosophers sit around a table. Between each pair of philosophers is a single fork. To eat, a philosopher needs to pick up both the left and right fork. Philosophers alternate between thinking and eating.

In the naïve solution, each philosopher:

1. Picks up the left fork.
2. Picks up the right fork.
3. Eats.
4. Puts down both forks.

If all philosophers pick up their left fork at the same time, no one can pick up their right fork, and deadlock occurs.

Deadlock arises when four conditions are met. These are called the four Coffman conditions:

• Mutual exclusion (forks cannot be shared)
• Hold and wait (each philosopher holds one fork while waiting for the other)
• No preemption (forks are only released voluntarily)
• Circular wait (each philosopher waits on the next in a cycle)

Scenario

You are given a C-like pseudocode implementation of the philosophers’ behavior. Each philosopher runs the following:

while (true) {
    think();
    pick_up(left_fork);
    pick_up(right_fork);
    eat();
    put_down(left_fork);
    put_down(right_fork);
}

Forks are represented as mutexes. All philosophers start simultaneously. Deadlock sometimes occurs during execution.

Several alternate designs are proposed:

• Design A: Allow at most four philosophers to sit at the table at once.
• Design B: Impose a resource hierarchy by requiring philosophers to always pick up the lower-numbered fork first.
• Design C: Use a waiter (monitor) who grants permission to pick up forks only if both are available.
• Design D: Replace blocking pick_up() with try-lock which check first if the second fork is unavailable, release the first and retry after thinking.

Answer the following questions:

1. Identify which of the four Coffman deadlock conditions are satisfied in the original code.
2. For each of the proposed designs (A–D), explain how they address the deadlock problem.
3. Which designs also improve fairness or avoid starvation? Why?
4. What are the trade-offs between centralized (Design C) and decentralized (Design D) control?

Hints:

• Think about how each design breaks one or more deadlock conditions.
• Consider whether philosophers may starve even if deadlock is avoided.
• For resource hierarchy, assume fork numbers range from 0 to 4 clockwise.

Visual Trace Exercise: Deadlock When Full

Background: Circular Wait with Semaphores

In producer-consumer systems using semaphores, the order in which semaphores are acquired is critical. If a thread holds one semaphore while waiting on another, and other threads are waiting to acquire the first one, the system can enter a deadlock: a circular wait where no thread can proceed.

Let’s demonstrate how a subtle change in ordering can cause the system to freeze when the buffer becomes full.

Scenario

You attempt to optimize a bounded buffer implementation by locking access early. You reason: “Since the thread will use both mutex and empty, let’s acquire mutex first to avoid holding mutex too long after.”

Here’s the newly modified producer code:

sem_wait(&mutex);
sem_wait(&empty);
// insert into buffer
sem_post(&full);
sem_post(&mutex);

And here’s the existing consumer code:

sem_wait(&full);
sem_wait(&mutex);
// insert into buffer
sem_post(&mutex);
sem_post(&empty);

Problem

At runtime, the system works for a while. But occasionally, when the buffer becomes full, all producers and consumers block indefinitely although there are items in the buffer to be consumed.

Answer the following questions:

1. What is the mistake in the order of semaphore operations?
2. Show how deadlock can occur if one producer holds mutex and is blocked on empty, while other threads are waiting for mutex.
3. Why does this problem only show up under full buffer conditions?
4. How should the semaphore order be fixed to prevent deadlock?
5. Why is it safe to call sem_wait(&empty) before locking the mutex?

Hints:

• Think about the scenario where the buffer has no more empty slots.
• A thread holding mutex must never block on another semaphore.
• Blocking must happen before acquiring exclusive access.

Visual Timeline Example

Initial state: buffer is full (empty = 0)

T1 (Producer):
    sem_wait(mutex) → succeeds (mutex = 1 → 0)
    sem_wait(empty) → blocks (empty = 0)

T2 (Producer):
    sem_wait(mutex) → blocks (mutex = 0)

T3 (Consumer):
    sem_wait(full) → succeeds
    tries to acquire mutex → blocks

→ All threads waiting on each other → deadlock

sem_wait(&empty);
sem_wait(&mutex);
// insert into buffer
sem_post(&mutex);
sem_post(&full);

Missed Notify with Separate Lock and Premature Signal

Background

In Java, wait() and notify() are used within synchronized(lock) blocks to allow threads to coordinate using an object’s monitor. However, unlike semaphores, notify() does not persist. If no thread is currently waiting on the monitor when notify() is called, the signal is lost.

This means if a thread calls wait() after a notify() has already occurred, it will block forever, akin to how a patient waiting to see a doctor in a hospital missed hearing their name (e.g: was in the restroom) being called by a nurse and ended up waiting indefinitely.

Recap: Java Monitors and Intrinsic Synchronization

In Java, a monitor is a high-level concurrency construct that provides both mutual exclusion and condition synchronization. Java monitors are implemented as an intrinsic part of every object in the Java Virtual Machine (JVM), meaning that every object implicitly supports monitor-based coordination.

Mutex

From the lecture notes, recall that Java achieves mutual exclusion through the use of the synchronized keyword. When a thread enters a synchronized block or method, it must acquire the monitor associated with the target object or class.

• For instance methods, the monitor is associated with the instance (this).
• For static methods, the monitor is associated with the class object (ClassName.class).
• For synchronized(obj) blocks, the monitor is associated with the specific object obj.

Only one thread may hold a given monitor at a time. All other threads attempting to enter a synchronized region guarded by that monitor are blocked until the monitor is released.

Condition Synchronization

Java monitors also support condition synchronization through the methods wait(), notify(), and notifyAll(): all of which must be called while holding the monitor (i.e., within a synchronized block or method).

• wait() causes the current thread to release the monitor and suspend execution until another thread invokes notify() or notifyAll() on the same object.
• notify() wakes up one thread waiting on that monitor.
• notifyAll() wakes up all threads waiting on that monitor.

The typical pattern for condition synchronization involves a shared predicate variable and a while loop guarding a wait() call:

synchronized (lock) {
    while (!condition) {
        lock.wait();
    }
    // Proceed when condition is true
}

This usage ensures correctness in the presence of spurious wakeups, where a thread may return from wait() even if it was not explicitly notified.

It has the following key properties:

• A thread must hold the monitor before calling wait(), notify(), or notifyAll(). Otherwise, a java.lang.IllegalMonitorStateException is thrown.
• The monitor’s condition queue is shared for all waiting threads. notify() does not distinguish which thread to wake; it may wake a thread that cannot proceed, leading to inefficiencies or stalling unless notifyAll() is used appropriately.
• Unlike semaphores, notify() does not persist. If no thread is waiting when notify() is called, the signal is lost.

While Java monitors provide a simple and safe mechanism for concurrency control, they are limited to a single condition queue per object. For more advanced control (e.g., multiple condition queues, fine-grained control), Java provides the java.util.concurrent.locks.Condition interface in conjunction with ReentrantLock. With ReentrantLock, you can create multiple conditions and call await() on each condition accordingly.

Scenario

The following class models a one-shot event between a producer and a consumer. The producer sets a flag and calls notify() to wake the consumer.

class OneShotEvent {
    private boolean ready = false;
    private final Object lock = new Object();

    public void produce() {
        System.out.println("Producer's running")
        synchronized (lock) {
            ready = true;
            lock.notify(); // signal consumer
        }
    }

    public void consume()  {
    
        System.out.println("Consumer's running")
        while (!ready){
            synchronized(lock){
              lock.wait(); // wait for signal
            }
        }
        System.out.println("Consumed");

    }
}

This test is run:

OneShotEvent event = new OneShotEvent();
new Thread(() -> {
    try {
        event.consume();
    } catch (InterruptedException e) {}
}).start();


System.out.println("Producer Begins")
event.produce();

Observation: Sometimes the program hangs and the message "Consumed" is never printed.

Answer the following questions:

1. Why does the consume() method sometimes block forever?
2. What happens if produce() calls notify() before consume() reaches wait()?
3. How does this differ from a semaphore-based approach?
4. Modify the code minimally so that no missed signal occurs, using only Java synchronization.

Hints:

• notify() only works if a thread is already waiting.
• Always use while, not if, with wait().
• Semaphores store permits, condition variables do not.

  public synchronized void consume() {
        System.out.println("Consumer's running")
        while (!ready) 
            lock.wait();
        System.out.println("Consumed");

  }

Can This Bounded Buffer Deadlock?

Background

A classic bounded buffer allows multiple producers and consumers to share access to a fixed-size queue. In this Java implementation, threads use wait() and notify() to coordinate access.

Important properties:

• wait() suspends the current thread until it is notified.
• notify() wakes one thread waiting on the same monitor.
• All threads synchronize on a single shared lock object.
• There is no explicit condition variable: all threads wait on the same monitor.

Scenario

The following implementation runs with multiple producer and consumer threads:

class BoundedBuffer {
    private final Queue<Integer> buffer = new LinkedList<>();
    private final int CAPACITY = 5;
    private final Object lock = new Object();

    public void produce(int item) throws InterruptedException {
        synchronized (lock) {
            while (buffer.size() == CAPACITY)
                lock.wait();

            buffer.add(item);
            lock.notify(); // wake up one thread
        }
    }

    public int consume() throws InterruptedException {
        synchronized (lock) {
            while (buffer.isEmpty())
                lock.wait();

            int item = buffer.remove();
            lock.notify(); // wake up one thread
            return item;
        }
    }
}

At first glance, using notify() (not notifyAll()) seems risky: it wakes an arbitrary thread, even if that thread can’t make progress. What if producer mistakenly wake up another producer thread instead of a consumer thread?

Answer the following question: Is it possible for this program to enter a deadlock where no thread makes progress, despite threads being alive and correctly synchronized?

To make a clear answer, either:

• Provide a concrete example of a buffer state and thread state that causes deadlock, or
• Give a convincing proof that no such deadlock is possible, explaining why progress is always guaranteed.

Hint:

• What condition causes a thread to block?
• Who can unblock it?
• Can notify() ever wake the “wrong” thread?
• Does that matter if only one kind of thread is waiting at a time?

Circular Wait in Print Spooler and Scanner

Background

Deadlock is a state where a group of processes is unable to proceed because each is waiting for a resource held by another. Four conditions we learned in class (mutex, circular wait, no-preemption, hold-and-wait) must hold simultaneously for a deadlock to occur. If all four conditions are present, the system can reach a deadlocked state.

As stated previously, these are formally known as the Coffman conditions.

Scenario

A user launches two applications at the same time:

• App A locks the scanner first, then tries to lock the printer.
• App B locks the printer first, then tries to lock the scanner.

Each device is protected by a mutex. Sometimes, both applications stop responding and remain blocked forever.

The system has only one printer and one scanner. The simplified pseudocode for both apps is shown below.

// App A
lock(scanner);
sleep(1);  // simulate time gap
lock(printer);
... // scan and print
unlock(printer);
unlock(scanner);

// App B
lock(printer);
sleep(1);  // simulate time gap
lock(scanner);
... // print and scan
unlock(scanner);
unlock(printer);

Answer the following questions:

1. Identify how each of the Coffman conditions is satisfied in this system.
2. Provide a step-by-step explanation of how the two applications could enter a deadlock.
3. Suggest two alternative designs that could prevent this deadlock and explain why they work.
4. Suppose the printer driver is updated to include a log message before allowing access, which adds a short delay. How could this change affect the likelihood of deadlock?

Hints:

• Consider how timing affects the acquisition order.
• Draw a resource allocation graph if needed.
• Use the Coffman conditions to reason through both cause and prevention.

Banker’s Algorithm: Approve or Deny?

Background

In operating systems, Banker’s Algorithm is used to avoid deadlocks by checking whether a resource request will leave the system in a safe state. A safe state is one in which all processes can finish in some order, even if they do not finish immediately.

The algorithm works with four matrices or vectors:

• Available — the number of free instances of each resource.
• Max — the maximum demand each process may eventually request.
• Allocation — the number of resources currently held by each process.
• Need — the remaining resources needed, calculated as Max - Allocation.

Before granting a request, the system simulates the allocation and checks whether a safe sequence of completion exists for all processes. If so, the request is granted. If not, it is denied to avoid the risk of entering an unsafe state that could lead to deadlock.

Scenario

A system has three resource types: A, B, and C. The total number of instances for each resource is:

• A: 10
• B: 5
• C: 7

There are five processes (P0 to P4). The current state of the system is as follows:

Allocation Matrix

Max Matrix

The Available vector is:

• A: 3
• B: 3
• C: 2

Now, process P1 makes a request for resources: (1, 0, 2).

Answer the following questions:

1. Compute the Need matrix for each process.
2. Should the system grant P1’s request? Show your reasoning using the Banker’s safety check.
3. If the request is granted and P1 finishes and releases all its resources, what will the new Available vector be?
4. Explain why entering an unsafe state does not immediately cause deadlock but is still dangerous.

Hints:

• A safe state guarantees at least one execution order where all processes can finish.
• An unsafe state does not guarantee deadlock but makes it possible.
• Holding resources without a guaranteed finish path creates future risk.
• The number of requested units doesn’t determine safety — the global state does.

The Banker’s Mistake

Background

As you’ve done in the lab, the Banker’s Algorithm is used to avoid deadlock by simulating allocations and only approving those that leave the system in a safe state: a state where all processes can eventually finish. A mistake in the algorithm’s logic can admit requests that appear harmless but eventually trap the system in a deadlock.

Scenario

A system is managing three types of resources (A, B, C) and four running processes. To optimize speed, a developer modifies the safety check to only verify if at least one process can finish after each allocation. The system continues to run, but under a specific sequence of requests, all processes become blocked and hold some resources. The Banker’s Algorithm did not catch this unsafe path because it didn’t simulate all possible finishing orders.

Answer the following questions

1. What is the purpose of simulating the safety check in the Banker’s Algorithm?
2. Why is it incorrect to only check if one process can finish when evaluating safety?
3. Give a small example (2–3 processes, 2–3 resources) where granting a request appears safe at first glance but results in an unsafe state.
4. How can the Banker’s Algorithm be modified to correctly detect unsafe allocations?

Hints:

• A safe state guarantees all processes can eventually finish.
• Just one process finishing doesn’t ensure overall safety.
• The algorithm simulates a possible sequence where every process can finish in some order.
• You must evaluate the system state after the hypothetical allocation before committing it.

The Unsafe Shortcut

Background

Deadlock avoidance techniques completely disallow the system from entering states where deadlock could happen. The Banker’s Algorithm we learned in class repeatedly checks whether a resource request leaves the system in a “safe state”. If it doesn’t, it will reject that request. The process whose request is rejected couldn’t progress and has to wait and try to request again some time in the future: it might be granted in the future after other processes have released their resources.

Safe state: a state where all processes can eventually finish.

Scenario

A system uses the Banker’s Algorithm to approve resource requests. To optimize performance under load, a developer modifies the algorithm to skip the safe-state check for requests that appear “small” (e.g., requesting only one unit). At first, the system continues to run fine. But under heavy load, it freezes entirely. Post-mortem analysis shows multiple unfinished processes holding resources and waiting indefinitely.

Example Suppose the system has 2 identical units of a resource and 3 processes:

• P1 may request up to 2
• P2 may request up to 2
• P3 may request up to 1

The current allocation is:

• P1 has 0
• P2 has 1
• P3 has 0

Suppose P1 now requests 1 of the resources. Granting it would leave 0 free units. This leads to an unsafe state: P1 still needs 1, P2 still needs 1, and P3 still needs 1, but not yet deadlocked (as each process may request up to n resources, not fully maxed out at a time).

Let’s push the scenario further: if P3 asked for the resource, it will have to wait because no more resource is available, but the system is also not yet deadlocked. There’s still a possibility where P2 might eventually release the resource, allowing P3 to proceed.

However, if all processes: P1, P2, and P3 request for 1 more instance of the resource to proceed. Then, the system will be deadlocked.

Answer the following questions

1. What is the difference between an unsafe state and a deadlocked state?
2. Explain how entering an unsafe state can eventually lead to deadlock.
3. In the scenario above, why is skipping the safety check dangerous even if the request seems small?
4. Suppose the system grants a request and enters an unsafe state. Describe one possible sequence of events that leads to deadlock.
5. Suggest one modification to improve performance without removing the safety check.

Hints:

• A safe state guarantees at least one execution order where all processes can finish.
• An unsafe state does not guarantee deadlock but makes it possible.
• Holding resources without a guaranteed finish path creates future risk.
• The number of requested units doesn’t determine safety — the global state does.

Hidden Cycles in Resource Allocation Graph

Background

A Resource Allocation Graph (RAG) is a directed graph used to visualize how processes and resources interact in a system. It consists of:

• Processes (circles)
• Resources (squares)
• Request edges from a process to a resource
• Assignment edges from a resource to a process

In a system where each resource has exactly one instance, a cycle in the graph implies a deadlock. However, if a resource has multiple instances, a cycle does not necessarily mean deadlock.

The graph must be analyzed more carefully to distinguish between true deadlocks and safe but cyclic states.

Scenario

You are given the following snapshot of a system. It includes three processes (P1, P2, P3) and two resource types:

• R1 has 2 instances
• R2 has 1 instance

Current graph state:

• P1 holds 1 instance of R1 and is requesting R2
• P2 holds R2 and is requesting 1 instance of R1
• P3 holds 1 instance of R1 and is not requesting anything

Graphically, this forms a cycle:

• P1 → R2 → P2 → R1 → P1

Note that R1 has 2 instances, and one is held by P3.

Answer the following questions:

1. Draw the resource allocation graph based on the description. Label request and assignment edges clearly.
2. Does this graph represent a deadlock? Justify your answer using resource instance counts.
3. What is the key difference in reasoning when resources have multiple instances compared to when each has only one?
4. How would adding another instance of R2 affect the potential for deadlock in this graph?

Hints:

• A cycle in a resource allocation graph is only sufficient to prove deadlock when all resources have one instance.
• If a resource has multiple instances, you must check whether the processes can eventually proceed.
• Track how many units are held and whether a process’s request can be fulfilled with the remaining instances.
• Just because a cycle exists does not mean the system is stuck.

Dining Savages with Broken Pot Semaphore

Background

The Dining Savages Problem is a classic concurrency scenario involving a group of threads (savages) sharing a common pot of food. A cook thread refills the pot when it is empty. To coordinate correctly, synchronization primitives such as mutexes and semaphores are used.

Each savage must:

1. Acquire a lock to check the pot.
2. If food is available, take one serving.
3. If the pot is empty, signal the cook to refill it.
4. Wait until food becomes available again.

If the synchronization is incorrect; for example, if a semaphore is missing or misused then the system can enter a deadlock where savages wait indefinitely and the cook is never notified.

Scenario

Consider the following buggy implementation:

semaphore serving_available = 0; 
semaphore empty = 1; // used to wake up cook 
mutex mtx = 1; // used by savages to protect servings_eaten 
int servings_eaten = 0; // shared resource among savages

// savage code
while (true) {
    wait(serving_available);
    eat();

    wait(mtx);
    servings_eaten++;
    if (servings_eaten == N) {
        servings_eaten = 0;
        signal(empty);
    }
    signal(mtx);
}

// cook code
while (true) {
    wait(empty);
    cook();
    signal(serving_available);
}

However, after some time, the program deadlocks. All savage threads are blocked, and the cook is idle.

Answer the following questions:

1. Explain the purpose of each semaphore and how they coordinate between the savages and the cook.
2. Describe the condition (scenario) that leads the system into a deadlock.
3. Why is it incorrect to simply call signal(serving_available) once?
4. Modify the synchronization so that deadlock is mitigated. The modification should be as minimal as possible.

Hints:

• Only one savage should signal the cook when the pot is empty.
• Semaphores do not queue extra signals if no one is waiting.
• The cook only wakes one savage after refilling and the others remain blocked with the current implementation.
• Think about whether serving_available should count the number of available servings.

Epilogue

The above solution to the dining savages problem works, but it requires you to signal many times as the semaphore servings_available represents the number of servings available for each savage. Below is an alternative solution that uses int servings variable instead of using the semaphore to count the servings. Either solution works.

// Shared variables
int servings = 0;
mutex pot_mutex;
semaphore empty = 0;     // used to wake up cook
semaphore full = 0;      // used to wake up savages

// Savage thread
while (true) {
    wait(pot_mutex);
    if (servings == 0) {
        signal(empty);   // notify cook
        wait(full);      // wait for refill
    }
    servings--;
    signal(pot_mutex);
    eat();
}

// Cook thread
while (true) {
    wait(empty);         // wait until pot is empty
    cook();
    servings = N;        // refill pot
    signal(full);        // notify savage
}

Preemption and Priority Inversion in Lock Acquisition

Background

In preemptive operating systems with priority scheduling, a high-priority process can interrupt a low-priority one to ensure timely execution. However, if a low-priority thread holds a lock needed by a high-priority thread, and medium-priority threads keep preempting the low-priority one, the high-priority thread gets blocked. This scenario is called priority inversion.

Priority inversion violates scheduling expectations. It may not cause a classical deadlock, but it leads to indefinite blocking of higher-priority threads. In real-time systems, this can cause serious issues. Some systems implement priority inheritance to solve the problem.

Scenario

Three threads are running with the following priorities:

• Low-priority T1 holds a lock L and is in its critical section.
• High-priority T2 tries to acquire L and is blocked.
• Medium-priority T3 does not need L but frequently runs and preempts T1.

Because T1 never gets CPU time, it cannot release the lock. T2 remains blocked even though it has higher priority. This behavior is observed in some real-time systems like Mars Pathfinder.

Answer the following questions:

1. Why does T2 not proceed, even though it has higher priority than T1 and T3?
2. Does this situation meet the four Coffman conditions for deadlock? Why or why not?
3. How does priority inheritance help resolve this issue?
4. Suppose priority inheritance is not available. Suggest an alternate way to prevent such inversion scenarios.

Hints:

• Deadlock requires circular wait. Is that happening here?
• T1 is not waiting for a resource, but still blocks T2 indirectly.
• Inheritance temporarily boosts T1’s priority to match T2’s.
• Consider how resource access policies can be redesigned to avoid this.

The Ostrich Algorithm

Background

A deadlock prevention strategy often taught in operating systems is the Ostrich Algorithm, which simply ignores the problem (what a wonderful strategy!). The idea is that if deadlocks are rare, it may not be worth the overhead of avoiding or detecting them. This approach is named after the ostrich’s supposed habit of “burying its head in the sand” when facing danger.

In practice, many general-purpose operating systems adopt this strategy for certain types of locks or resources. The assumption is that users or programs will avoid mistakes, or that occasional restarts are acceptable.

However, ignoring deadlocks is only safe when the cost of failure is low and the system can recover gracefully. In long-running systems or mission-critical applications, even a rare deadlock can be catastrophic.

Scenario

A file server uses a multi-threaded model where threads acquire read and write locks on files. Occasionally, two threads acquire locks in different orders:

• Thread A locks File X and then requests File Y.
• Thread B locks File Y and then requests File X.

The system does not enforce lock ordering and does not use any deadlock detection. After a long uptime, the server becomes unresponsive. Investigation reveals that Thread A and Thread B are both blocked, each waiting on the other’s lock.

The server does not crash but stops processing requests. This problem only happens once every few weeks.

Answer the following questions:

1. Why is the Ostrich Algorithm sometimes chosen as a design strategy in operating systems?
2. What are the risks of using the Ostrich Algorithm in the file server scenario described?
3. Suggest one runtime strategy and one design-time strategy that could help reduce the likelihood of such deadlocks.
4. In what types of systems is the Ostrich Algorithm a reasonable tradeoff, and when is it irresponsible?

Hints:

• Think about the cost of prevention versus the cost of failure.
• Is the system interactive, recoverable, or mission-critical?
• Not all deadlocks are equally harmful — some are tolerable, others are fatal.
• Runtime fixes involve detection or recovery, while design-time fixes involve resource usage rules.

class BoundedBuffer {
    private final Queue buffer = new LinkedList<>();
    private final int CAPACITY = 5;

    private final Object producerLock = new Object();
    private final Object consumerLock = new Object();

    public void produce(int item) throws InterruptedException {
        // Always acquire consumerLock before producerLock
        while (true) {
            synchronized (consumerLock) {
                synchronized (producerLock) {
                    if (buffer.size() < CAPACITY) {
                        buffer.add(item);
                        consumerLock.notify(); // signal a waiting consumer
                        return;
                    }
                }
                // Only wait while holding consumerLock
                consumerLock.wait(); // wait until consumer removes an item
            }
        }
    }

    public int consume() throws InterruptedException {
        while (true) {
            synchronized (consumerLock) {
                synchronized (producerLock) {
                    if (!buffer.isEmpty()) {
                        int item = buffer.remove();
                        producerLock.notify(); // signal a waiting producer
                        return item;
                    }
                }
                // Only wait while holding consumerLock
                consumerLock.wait(); // wait until producer adds an item
            }
        }
    }
}
</code></pre>

This version:

  
Always locks consumerLock before producerLock.
  
Avoids holding both locks during wait().
  
Eliminates circular wait: hence prevents deadlock.


Note that using two locks like this is inefficient, but the question is just made for exercise purposes.
</div>