Tag: multithreading

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.

More Than Resource Contention

One of the first things we learn about multithreaded programming is the need to guard against simultaneous read-write access to shared resources, but this isn’t always a simple matter.

Let’s consider a scenario where we have an existing C++ class that was written without concern for thread-safety:

class Book;

class Library
{
private:
    std::list<Book*> mBooks;

public:
    void addBook(Book* inBook)
    {
        mBooks.insert(mBooks.begin(), inBook);
    }

    Book* getBook(int inIndex)
    {
        return mBooks[inIndex];
    }

    int getBookCount()
    {
        return mBooks.size();
    }

    void removeBook(Book* inBook)
    {
        std::vector<Book*>::iterator iter = std::find(mBooks.begin(), mBooks.end(), inBook);
        if (iter != mBooks.end())
        {
            mBooks.erase(iter);
        }
    }
};

Running through all the books in the library might look like this:

void processBooks(Library* inLibrary)
{
    int count = inLibrary->getBookCount();
    for (int index = 0; index < count; ++index)
    {
        Book* book = inLibrary->getBook(index);
        // do something with the book
    }
}

Now, suppose we want to make the Library class thread-safe. Since the std::vector template isn’t thread-safe, we’ll need to implement a locking mechanism to serialize access to mBooks. Otherwise, two threads might try to manipulate the vector at the same time with unexpected results. A quick implementation might be:

class Library
{
private:
    std::list<Book*> mBooks;
    Mutex mBooksLock;

public:
    void addBook(Book* inBook)
    {
        mBooksLock.lock();
        mBooks.insert(mBooks.begin(), inBook);
        mBooksLock.unlock();
    }

    Book* getBook(int inIndex)
    {
        mBooksLock.lock();
        Book* book = mBooks[inIndex];
        mBooksLock.unlock();
        return book;
    }

    int getBookCount()
    {
        mBooksLock.lock();
        int count = mBooks.size();
        mBooksLock.unlock();
        return count;
    }

    void removeBook(Book* inBook)
    {
        mBooksLock.lock();
        std::vector<Book*>::iterator iter = std::find(mBooks.begin(), mBooks.end(), inBook);
        if (iter != mBooks.end())
        {
            mBooks.erase(iter);
        }
        mBooksLock.unlock();
    }
};

Now it’s thread-safe, right?

Well, no.

This implementation will prevent concurrent access to mBooks, but consider this real-life parallel. While driving down the highway with a camera, we point the camera out the window and take a picture of the traffic to our right. A few minutes later, we need to switch into the right-hand lane, so we check the picture to make sure no cars are in the lane. This kind of driving suffers from the same problem as our class implementation – relying on state information that’s possibly out of date – and it’s likely our car and our software will face the same outcome.

Just like cars moving into or out of adjacent lanes, if a second thread decides to add or remove a book from the library while the first thread is looping through the books, we have a potential change in two pieces of state information used in our loop. Can you spot both of them?

First, the book count may change. It may increase or decrease as we run through the processing loop. We might modify the code a bit to better handle changes to the book count:

Book* Library::getBook(int inIndex)
{
    Book* book = NULL;
    mBooksLock.lock();
    // Make sure we have a valid index.
    if ((inIndex >= 0) && (inIndex < mBooks.size()))
    {
        book = mBooks[inIndex];
    }
    mBooksLock.unlock();
    return book;
}

void processBooks(Library* inLibrary)
{
    int index = 0;
    int count = inLibrary->getBookCount();
    do
    {
        Book* book = inLibrary->getBook(index);
        if (book != NULL)
        {
            // do something with the book
        }
        index++;
        count = inLibrary->getBookCount();
    } while (index < count);
}

However, we still have a second bit of changing state information: the current index value. Let’s assume our mBooks vector contains the books “A”, “B”, “C”, “D”, and “E”. If we process book “C” when the index is 2, then add a new book at the front of mBooks, when we process index 3 we’ll be processing book “C” again. Or if we remove the book at the front of the vector, we’ll skip processing on book “D” and go straight to book “E”.

You may think these problems should be obvious, but these kinds of mistakes can be all too common. Sometimes a developer manages to get away with a “safe enough” solution, but at some point the bugs will surface – most likely when another developer begins using the Library class in a slightly different manner or from yet another thread.

The primary purpose of this post is to point out that thread-safety is sometimes not as straight forward as we might think. Just scattering a few locks around class member variables isn’t sufficient. We need to be mindful of 1) how various threads may access shared resources, and 2) the lifetime of any state information we may be using (e.g. the book count and index value in our sample). In a later post, we’ll consider how we might implement the Library class to avoid threading problems.