boost::threads execution ordering

Question

i have a problem with the order of execution of the threads created consecutively. here is the code.

#include <iostream>
#include <Windows.h>
#include <boost/thread.hpp>

using namespace std;

boost::mutex mutexA;
boost::mutex mutexB;
boost::mutex mutexC;
boost::mutex mutexD;


void SomeWork(char letter, int index)
{
    boost::mutex::scoped_lock lock;
    switch(letter)
    {
    case 'A' : lock = boost::mutex::scoped_lock(mutexA); break;
    case 'B' : lock = boost::mutex::scoped_lock(mutexB); break;
    case 'C' : lock = boost::mutex::scoped_lock(mutexC); break;
    case 'D' : lock = boost::mutex::scoped_lock(mutexD); break;
    }

    cout << letter <<index << " started" << endl;
    Sleep(800);
    cout << letter<<index << " finished" << endl; 
}

int main(int argc , char * argv[])
{
    for(int i = 0; i < 16; i++)
    {
        char x = rand() % 4 + 65;
        boost::thread tha = boost::thread(SomeWork,x,i);
        Sleep(10);
    }
Sleep(6000);
    system("PAUSE");
  return 0;
}

each time a letter (from A to D) and a genereaion id (i) is passed to the method SomeWork as a thread. i do not care about the execution order between letters but for a prticular letter ,say A, Ax has to start before Ay, if x < y. a random part of a random output of the code is :

B0 started  
D1 started  
C2 started  
A3 started  
B0 finished  
B12 started  
D1 finished  
D15 started  
C2 finished  
C6 started  
A3 finished  
A9 started
B12 finished
B11 started --> B11 started after B12 finished.
D15 finished
D13 started
C6 finished
C7 started
A9 finished

how can avoid such conditions?
thanks.

---

i solved the problem using condition variables. but i changed the problem a bit. the solution is to keep track of the index of the for loop. so each thread knows when it does not work. but as far as this code is concerned, there are two other things that i would like to ask about.
first, on my computer, when i set the for-loop index to 350 i had an access violation. 310 was the number of loops, which was ok. so i realized that there is a maximum number of threads to be generated. how can i determine this number? second, in visual studio 2008, the release version of the code showed a really strange behaviour. without using condition variables (lines 1 to 3 were commented out), the threads were ordered. how could that happen?

here is the code:

#include <iostream>
#include <Windows.h>
#include <boost/thread.hpp>

using namespace std;

boost::mutex mutexA;
boost::mutex mutexB;
boost::mutex mutexC;
boost::mutex mutexD;


class cl
{
public:
    boost::condition_variable con;
    boost::mutex mutex_cl;
    char Letter;
    int num;
    cl(char letter) : Letter(letter) , num(0)
    {

    }
    void doWork( int index, int tracknum)
    {
        boost::unique_lock<boost::mutex> lock(mutex_cl);
        while(num != tracknum)     // line 1
            con.wait(lock);   // line 2 
        Sleep(10);
        num = index;
        cout << Letter<<index << endl; 
        con.notify_all();  // line 3
    }
};

int main(int argc , char * argv[])
{
    cl A('A');
    cl B('B');
    cl C('C');
    cl D('D');

    for(int i = 0; i < 100; i++)
    {   
        boost::thread(&cl::doWork,&A,i+1,i);
        boost::thread(&cl::doWork,&B,i+1,i);
        boost::thread(&cl::doWork,&C,i+1,i);
        boost::thread(&cl::doWork,&D,i+1,i);
    }
    cout << "************************************************************************" << endl;

    Sleep(6000);
    system("PAUSE");
  return 0;
}

Answer 1

If you have two different threads waiting for the lock, it's entirely non-deterministic which one will acquire it once the lock is released by the previous holder. I believe this is what you are experiencing. Assume B10 is holding the lock, and in the mean time threads are spawned for B11 and B12. B10 releases the lock - it's down to a coin toss as to whether B11 or B12 acquires it next, irrespective of which thread was created first, or even which thread started waiting first.

Perhaps you should implement work queues for each letter, such that you spawn exactly 4 threads, each of which consume work units? This is the only way to easily guarantee ordering in this way. A simple mutex is not going to guarantee ordering if multiple threads are waiting for the lock.

Answer 2

Even though B11 is started before B12 it is not guaranteed to be given a CPU time slice to execute SomeWork() prior to B12. This decision is up to the OS and its scheduler.

Mutex's are typically used to synchronize access to data between threads and a concern has been raised with the sequence of thread execution (i.e. data access).

If the threads for group 'A' are executing the same code on the same data then just use one thread. This will eliminate context switching between threads in the group and yield the same result. If the data is changing consider a producer/consumer pattern. Paul Bridger give's an easy to understand producer/consumer example here.

Answer 3

Your threads have dependencies that must be satisfied before they start execution. In your example, B12 depends on B0 and B11. Somehow you have to track that dependency knowledge. Threads with unfinished dependencies must be made to wait.

I would look into condition variables. Each time a thread finishes SomeWork() it would use the condition variable's notify_all() method. Then all of the waiting threads must check if they still have dependencies. If so, go back and wait. Otherwise, go ahead and call SomeWork().

You need some way for each thread to determine if it has unfinished dependencies. This will probably be some globally available entity. You should only modify it when you have the mutex (in SomeWork()). Reading by multiple threads should be safe for simple data structures.