How to properly do threading in C++?

Question

I have a rather large, dynamic sparse matrix object class to write, and I want to make the following happen: one thread to handle placing elements into the matrix, and one to handle reading from the matrix.

The only time when these two would conflict would be when they would both want to access the same row/column at the same time. As such, I've decided that a simple mutex lock for each row/column is sufficient.

Now this is the first time I've actually done threading in C/C++, and I'd like to do it by the books, so to speak. I have two concerns.

1. How do I spawn these threads? This is a language question more than anything.
2. How do I implement the locking itself as efficiently as possible? I figure if there is a conflict, then the requesting thread would place itself in line and wait until the resource is freed. However, how do I implement that waking? I can have a loop poll the memory location, but that's not elegant. Ideally, I figure an interrupt based approach would be best.

Answer 1

C++ itself does not offer any threading. On Windows, you can use CreateThread. On UNIX, you can use POSIX threads (pthreads).

There should be no need to implement your own concurrency primitives. On Windows, for example, you can create a mutex object using CreateMutex, and use WaitForSingleObject to wait until it is released.

Answer 2

I can answer part one fairly simply - it depends on your platform. If you're using Win32 API, take a look at http://msdn.microsoft.com/en-us/library/ms682453%28VS.85%29.aspx "CreateThread" function and read up on examples. The book I read on multi-threading on Windows was this one: http://www.amazon.co.uk/Windows-PRO-Developer-Jeffrey-Wintellect-Christophe/dp/0735624240 which covers not just threading with CreateThread and the other option BeginThread but also locks and semaphones etc.

If you're using Linux, you'll want POSIX Threads via the pthread function, see http://www.yolinux.com/TUTORIALS/LinuxTutorialPosixThreads.html as an example.

A code example for pthreads looks like this - be careful, I've left in functionality for creating several threads from the same function i.e. callocing an array of pthread_t variables. You might not need this.

#include <pthread.h>
#include <stdio.h>
#include <unistd.h>
#include <malloc.h>

void *thread_function(void *arg) 
{
        /* DO SOME STUFF */

        /* Exit Thread */
    pthread_exit();
}

int main(int argc, char** argv)
{
        /* variables */
        int retval = 0;
        /* array of thread handles */
    pthread_t* thread_handle = (pthread_t*) calloc(1, sizeof(pthread_t));;

        /* create function - fork() for threads */
    retval = pthread_create(&thread_handle[0], NULL, thread_function, NULL);

        /* DO SOME STUFF */

        /* join - wait for thread to finish */ 
        pthread_join(thread_handle[0], NULL); 

    return EXIT_SUCCESS;
}

Compile with gcc filename -o fileexe -lpthread

Answer 3

are you sure you want a matrix, what you describe sounds like a queue. The locking for a queue is fairly simple to do: when anybody reads or writes they take an exclusive lock (via a pthread_mutex). (Dont get into readwrite locks etc unless you really know you are in perf trouble)

certainly no Interrupts are needed

Answer 4

If this is your first time to do multi-threading, use the Boost.Threads library. Its semantics (including synchronization mechanisms) are very straightforward and your implementation will be portable.

http://www.boost.org/doc/libs/1_42_0/doc/html/thread.html

Answer 5

Start with boost threads.

And as for your design, it sounds like you've decided to allow random access to the whole matrix from any thread.

If at all possible, it would be better to figure out how to partition responsibility for parts of the matrix to specific threads. Taking out a lock for every cell access is going to be quite a bottleneck.

Answer 6

First of all, you don't need a mutex per column and one per row. If you acquired a mutex for a row, you locked all cells in that row, so it doesn't matter which column you access. Or if you acquire a lock per column, you locked all cells in that columns, doesn't matter which row. So you can have a mutex per table, one per cell, one per row or one per column. But one per row and one per column makes no sense.

Most synchronization primitives will block your threads and the thread will simply resume when the resource becomes free, you do not need to worry about signaling and waking up. That part is exactly what a synchronization object like a mutex or a critical section does for you.

The specifics of how to construct and use the synchronization primitives are platform specific. As others have posted, there are cross platform libraries you can use, but you must specify what platform you target at least so we know what libraries are available.

Answer 7

Thomas covered the threading library. The only reason you'd want to mess with interrupt handlers is if you don't have an OS. Otherwise, use what the OS gives you for thread control.

The thing I'd warn you about with the locking is to be careful not to deadlock. You want to lock by rows and columns, so each row and each column needs its own mutex. (Actually, a reader/writer lock would be far better for performance, but you have to be even more careful about deadlocks and race conditions.)

Make sure you always acquire and release the locks in a consistent order; you don't want a thread to lock row N and then block locking column K, and then the thread which has locked column K decides to lock row N and blocks, giving you two blocked threads and nothing happening (cue John Woo pistol standoff).

Answer 8

If you have a mutex for each row/column, you'll have a race condition when a row-writing thread and a column-reading thread accesses the element at the row/column intersection. If you have a large matrix, you'll need many mutexes. I'm not sure every operating system can provide thousands of mutexes.

It sounds like a thread-safe producer-consumer queue would be a better solution to your problem. Check out Intel's Thread Building Blocks (TBB) library. I find that multi-threading becomes much easier when you model your program using the data flow paradigm.

I you want to reduce the memory footprint of large, sparce matrices, check out Boost.uBlas. It has a sparce_matrix template class that uses a map to store elements associatively by indices.

For efficiency reasons, you will not want to pass entire matrices by copy to your producer-consumer queue. Instead, you'll want to pass around proxies of your sparce matrices. If TBB doesn't already have some kind of proxy facility, you can simply use boost::shared_ptr. You may also want to have a pre-allocated pool of matrices that are recycled in a data-flow "circuit".

Answer 9

Quick idea, choose one of available implementations of std::threads and then consider std::async and std::future and related tools.

Answer 10

As for your second question, on how to do the locking: putting the thread to sleep and waking it up will be done by the OS, that's not your worry. But there is a problem with your scheme.

You want to block access to a cell only if its row AND its column are locked. Which is to say, allow access if the row OR the column are UNlocked. That is not typically the way locks work. Furthermore, if the row was locked but you allowed access anyway (because the column was unlocked), you still want to lock it "more." This means you'll need more than a mutex.

The best implementation I can think of uses one atomic counter for the rows and a condition variable counter for the columns. Upon access:

• Increment the row's atomic counter.
• If the previous value of the atomic counter was zero, the row was unlocked. Access is OK.
  • Increment the column's condition variable. Ideally this should not block.
• If the row's counter was nonzero, it was locked. Maybe block on the column.
  • Wait until the column's condition variable is zero. Set it to one before releasing the mutex.
• When you're done with the access:
• Decrement the condition variable (don't forget to lock it), and signal it to wake other accesses if it became zero.
• Atomically decrement the row counter.

This involves a little fancy footwork, but the total number of locking resources is overall pretty low. Can anyone else do better (or find a counterexample to my scheme)?

Also note, the partitioning of the matrix into rows and columns is somewhat arbitrary. If too much contention occurs under this scheme, you should probably subdivide the rows into halves (for example).

Answer 11

Rather than having separate thread for read and write ( which will required locking always) you can restrict thread to access only particular elements of matrix , say lone thread for half of rows and other thread for last half (or one thread for even row and one for odd row ) this way you can ensure no thread is ever blocked