Tag: deadlocks

Don’t Tie Your Threads in Knots

Chip n’ Dale: Out on a Limb (1950)

One thing to remember about threads: they’re never polite. Ever.

While animated chipmunks may graciously insist that the other go first, threads never move themselves out of the way for other threads. When threads contend for a single resource this is not a great concern, but occasionally a situation arises where multiple threads contend for simultaneous access to multiple resources.

For example, let’s suppose we have a thread that is dedicated to a simple task. It checks the speed of a motor every ten seconds and records it in a log file. Another thread manages its own simple task of taking a temperature reading every six seconds and slowing the motor down if the temperature is too high. When the temperature is too high, the second thread also records the temperature in the log file. Assuming we have two resources to share between the threads (access to the log file and the motor), we might implement a logMotorSpeed() function as follows:

void logMotorSpeed()
{
    // Lock log file.
    logFile.lock();

    // Lock motor access.
    motor.lock();

    // Read motor speed and write to log file.
    const int speed = motor.getSpeed();
    logFile.writeSpeed(speed);

    // Unlock motor access.
    motor.unlock();

    // Unlock log file.
    logFile.unlock();
}

The second thread might perform the following actions:

void throttleMotorSpeed(int maxTemp)
{
    // Lock motor access.
    motor.lock();

    // Read motor temperature and write to log file.
    const int temp = motor.getTemp();
    if (temp > maxTemp)
    {
        // Lock log file.
        logFile.lock();
        
        logFile.writeTemp(temp);

        // Unlock log file.
        logFile.unlock();

        // Reduce to half current speed.
        motor.setSpeed(motor.getSpeed() / 2);
    }

    // Unlock motor access.
    motor.unlock();
}

At first glance, it might appear that we’ve successfully shared our resources between the two threads, locking and unlocking logFile and motor in each function to prevent the two threads from interfering with one another. However, we will eventually tie them into a knot that stops execution of both threads. At some point the two threads will execute with the following results:

logMotorSpeed() throttleMotorSpeed()
Lock logFile access
Lock motor access
Wait for motor access
Check temp.
Temp. is too high
Wait for logFile access

And now we’re deadlocked. Each thread is holding a resource that’s needed by the other and they are both forced to wait until the other thread releases its resource (which can’t happen while it’s waiting). And threads don’t have sufficient manners to back out of the way and let the other go first.

There are a couple of solutions to the problem in this example. If a thread can avoid simultaneously locking multiple resources, it should do so. Neither thread actually needs to lock both resources simultaneously. They could have been implemented as:

void logMotorSpeed()
{
    // Read the motor speed.
    motor.lock();
    const int speed = motor.getSpeed();
    motor.unlock();

    // Write the speed to the log file.
    logFile.lock();
    logFile.writeSpeed(speed);
    logFile.unlock();
}

void throttleMotorSpeed(int maxTemp)
{
    // Read motor temperature.
    motor.lock();
    const int temp = motor.getTemp();
    motor.unlock();

    // Write to log file and slow down motor.
    if (temp > maxTemp)
    {
        logFile.lock();
        logFile.writeTemp(temp);
        logFile.unlock();

        motor.lock();
        motor.setSpeed(motor.getSpeed() / 2);
        motor.unlock();
    }
}

In addition to avoiding a deadlock, we’ve also reduced the duration of each resource lock, which potentially improves each thread’s performance. But there are occasionally situations where both resources must be locked simultaneously. For this reason, it’s important to maintain a consistent locking order on our resources. The following change will also avoid tying our threads in knots:

void logMotorSpeed()
{
    motor.lock();

    // Read the motor speed.
    const int speed = motor.getSpeed();

    // Write the speed to the log file.
    logFile.lock();
    logFile.writeSpeed(speed);
    logFile.unlock();

    motor.unlock();
}

Even though we’re locking access to logFile and motor simultaneously, since both functions lock logFile within the lock on motor, we won’t deadlock. It’s no longer possible for a thread to lock logFile unless it has already obtained the lock on motor. We just need to be sure that we maintain a consistent locking order whenever any threads require simultaneous locks on multiple resources. While this is rather trivial in our example, the ordering of resource locks can become obscured as applications grow in complexity. A simple function call may hide resource locks that tie our threads in knots when we least expect it.

A few simple principles to keep threads running smoothly:

  • Maintain resource locks only as long as they are absolutely necessary.
  • Avoid nested resource locks whenever possible.
  • Maintain a consistent locking order when resource locks must be nested.
  • Consider what resource locks might be hidden inside function calls.