Non-Blocking Mutex Acquisition for Deadlock Avoidance

The Power of Not Waiting: pthread_mutex_trylock

The fundamental difference between pthread_mutex_lock and pthread_mutex_trylock is that lock will block (put the thread to sleep) until the mutex is available, whereas trylock will never block. It returns immediately, telling you whether you successfully acquired the lock or not.

As the documentation states:

• int pthread_mutex_trylock(pthread_mutex_t *mutex);
• If the mutex is unlocked, this function locks it and returns 0.
• If the mutex is already locked by any thread (including the current one), it returns immediately with the error code EBUSY.

This non-blocking "try" behavior allows a thread to test for a lock's availability and, if it's unavailable, do something else instead of just waiting—like releasing other locks to let another thread make progress. This is the key to deadlock avoidance.

The "Try-and-Backoff" Pattern

Let's return to our classic deadlock scenario: two threads need to lock two mutexes, m1 and m2, but they attempt to do so in opposite orders.

• Thread 1: lock(m1); lock(m2);
• Thread 2: lock(m2); lock(m1);

A lock-ordering policy would force Thread 2 to lock m1 first. The trylock approach offers a different solution: a thread attempts to acquire the locks it needs, but if it fails to get one, it "backs off" by releasing any locks it has already acquired, allowing other threads to proceed. It then waits a moment and tries again.

The logic shown in the article is the core pattern for deadlock avoidance with trylock:

// Conceptual code for the "try-and-backoff" pattern
while (1) {
    // Acquire the first lock
    pthread_mutex_lock(&m1);

    // Try to acquire the second lock
    if (pthread_mutex_trylock(&m2) == 0) {
        // Success! We have both locks.
        break; // Exit the loop and proceed.
    }

    // Failure. We couldn't get the second lock.
    // To prevent deadlock, we must release the first lock.
    pthread_mutex_unlock(&m1);

    // Wait a bit before retrying to avoid "livelock",
    // where threads waste CPU time by constantly failing and retrying.
    sched_yield(); // or usleep(), etc.
}

// ... critical section ...

pthread_mutex_unlock(&m2);
pthread_mutex_unlock(&m1);

With this pattern, if Thread 1 has m1 and Thread 2 has m2, when Thread 1 tries for m2, it will fail. It will then release m1. Now, Thread 2, which was waiting for m1, can acquire it. The deadlock is broken.

A Note on Livelock

The article mentions sched_yield(). Without a small delay or yield in the failure path, two threads could enter a "livelock": they repeatedly acquire their first lock, fail the trylock on the second, release the first, and immediately retry, accomplishing no useful work but burning CPU cycles. Adding a short usleep() or sched_yield() gives other threads a chance to run and clear the contention.

Alternative Use Case: A Pool of Identical Resources

The "try-and-backoff" pattern is for when you need a specific set of locks. But what if you have a pool of identical resources (e.g., worker connections, processing units) and your thread just needs to acquire any one of them? trylock is perfect for this.

The strategy is simple:

1. Iterate through the mutexes protecting each resource.
2. Use trylock on each one.
3. The first one you successfully lock is yours. Break the loop and use the resource.
4. If you iterate through all of them and fail to get a lock, it means all resources are currently busy. Wait for a moment and retry the entire loop.

This pattern is highly useful for managing pools of fungible resources where a thread doesn't care which specific resource it gets, only that it gets one.

#include <unistd.h> // for usleep

typedef struct {
    int balance;
    pthread_mutex_t lock;
} Account;

void transfer(Account *from, Account *to, int amount) {
    // Your implementation here using the try-and-backoff pattern.
}

void transfer(Account *from, Account *to, int amount) {
    // Special case: transferring to the same account doesn't need locks.
    if (from == to) {
        return;
    }

    while (1) {
        pthread_mutex_lock(&from->lock);

        if (pthread_mutex_trylock(&to->lock) == 0) {
            // Got both locks
            break;
        }

        // Couldn't get the second lock, so back off
        pthread_mutex_unlock(&from->lock);

        // Wait for a very short time to prevent livelock
        // and give the other thread a chance to complete.
        usleep(100); // sleep for 100 microseconds
    }

    // Critical Section
    if (from->balance >= amount) {
        from->balance -= amount;
        to->balance += amount;
    }

    // Release locks in reverse order of acquisition
    pthread_mutex_unlock(&to->lock);
    pthread_mutex_unlock(&from->lock);
}

Conclusion: Choosing Your Strategy

You now have two powerful techniques to prevent deadlock: lock ordering and try-and-backoff.

• Lock Ordering: This should be your default choice. It is more efficient because it never involves wasted work from failed lock attempts and retries. Its main cost is the intellectual effort of designing and enforcing the ordering policy across your entire codebase.
• Try-and-Backoff with trylock: This is a more flexible and dynamic strategy. It's invaluable when a rigid lock hierarchy is difficult to implement, for example in complex, irregular data structures. Its main drawback is lower performance under high contention due to repeated lock/unlock cycles and the risk of livelock if not implemented with a delay/yield.

Key Takeaways:

• pthread_mutex_trylock is a non-blocking function that attempts to acquire a mutex and returns immediately, indicating success (0) or failure (EBUSY).
• This function enables the "try-and-backoff" pattern: lock the first mutex, try to lock the second, and if you fail, release the first and retry. This breaks the "hold and wait" condition that can lead to a circular wait.
• It's crucial to add a small delay (usleep) or yield (sched_yield) in the backoff path to prevent livelock.
• trylock is also effective for managing pools of identical resources, where a thread can loop through and attempt to grab any available resource.

Preview of the Next Lesson:
We've spent two lessons discussing the Dining Philosophers problem and strategies to solve it. In the next lesson, we will put this knowledge into practice by writing a full C program to simulate the Dining Philosophers problem. This will give you a chance to see a deadlock happen "live" and to apply the prevention techniques you've learned to fix it.