thread starvation with boost::lock_guard

Question

i am trying to learn the boost library and was going through examples of boost::thread.

The example below illustrates the usage of the boost::lock_guard for thread synchronization, ensuring that the access to std::cout is not concurrent:

#include <boost/thread.hpp>
#include <boost/format.hpp>
#include <iostream>

void wait(const int secs) {
    boost::this_thread::sleep(boost::posix_time::seconds(secs));
}

boost::mutex mutex;

void thread1() {
    for (int i = 0; i < 10; ++i) {
        wait(1); // <-- all works fine if wait is placed here
        boost::lock_guard<boost::mutex> lock(mutex);
        std::cout << boost::format("thread A here %d\n") % i ;
    }
}

void thread2() {
    for (int i = 0; i < 10; ++i) {
        wait(1); //  <-- all works fine if wait is placed here
        boost::lock_guard<boost::mutex> lock(mutex);
        std::cout << boost::format("thread B here %d\n") % i;
    }

}

int main() {
    boost::thread t1(thread1);
    boost::thread t2(thread2);
    t1.join();
    t2.join();
}

The results where pretty much what one would expect, i.e. alternating messages by the two threads printed:

thread A here 0
thread B here 0
thread A here 1
thread B here 1
thread A here 2
thread B here 2
thread A here 3
thread B here 3
thread A here 4
thread B here 4
...

However, a small modification -- moving the wait call inside the scope of the lock guard -- led to a surprise:

void thread1() {
    for (int i = 0; i < 10; ++i) {
        boost::lock_guard<boost::mutex> lock(mutex);
        wait(1); // <== !
        std::cout << boost::format("thread A here %d\n") % i ;
    }
}

void thread2() {
    for (int i = 0; i < 10; ++i) {
        boost::lock_guard<boost::mutex> lock(mutex);
        wait(1);  // <== !
        std::cout << boost::format("thread B here %d\n") % i;
    }

Now either thead1 or thread2 wins the initial "race" for the mutex and then wins again and again on each loop iteration, thereby starving the other thread!

Example output:

thread B here 0
thread B here 1
thread B here 2
thread B here 3
thread B here 4
thread B here 5
thread B here 6
thread B here 7
thread B here 8
thread B here 9
thread A here 0
thread A here 1
thread A here 2
thread A here 3
thread A here 4
thread A here 5
thread A here 6
thread A here 7
thread A here 8
thread A here 9

Can anybody please explain why this is the case?

This is normal. There's no guarantee of fitness, especially visible when you have a thread not own a lock for less than a nanosecond. There's just no chance for the other thread to acquire the lock. Your first result is a random outcome as well. — Hans Passant
The typical mutex implementations do not guarantee against starvation, so your results are as valid as anything. In your first code, you have a very high probability of running the threads in a lockstep fashion, in your latter approach the thread will try to re-aquire the mutex immediately after it unlocks it. — nos
@nos: I couldn't imagine how to prevent threads from running lockstep given this example. Your wording "typical implementations do not guard against" suggests that this is actually possible. Do you have a paper (or even an implementation) at hand? — Damon
@Daemon Which of the two approaches are you referring to ? in the first piece of code there's really not any contention at all, the wait call makes the threads alternate. In the 2. example the threads would alternate too if the mutex implementation uses a fifo queue for the tasks blocked on the mutex, which they are not on the platform of the OP (which is quite typical on unix implementations) — nos
@nos: I am referring to the second snippet. I could hardly imagine how one could have a "non-typical" mutex that avoids threads running lockstep, since it's being held while threads go to sleep. It would have to be something like how Windows completion ports work, which wake another blocked thread if one of the active ones blocks on I/O. But this kind of thing wouldn't be valid behavior for a mutex. Even when a thread is not executing, it is still inside the "mutually exclusive" program section while holding the mutex. Otherwise, being re-scheduled would also mean releasing a mutex. — Damon

Captain Obvlious Captain Obvlious · Accepted Answer · 2013-12-25T21:39:23

This is because after the lock is acquired the wait call causes the second thread to begin executing. Since the second thread cannot acquire the lock it goes into a wait-state until the lock is available. In your case the lock does not become available until the first thread completes it's loop.

thread starvation with boost::lock_guard

1 Answers