Thursday, November 15, 2007

Using multiple threads to process a list of items.

Another multithreading issue I've come across frequently is where I have a fixed size list of items that need to be processed in some way.  Maybe it's a list of IP addresses to check or a list of files to parse.  Either way, the list size is fixed and each item can be processed independently.

 

One way to deal with these situations is to create a small number of worker threads and have them execute the same loop on the list.  Each thread should be numbered (e.g., from 0 to n-1 where n is the number of threads).  Each thread needs to know its number and the total number of workers.  The loop for each thread then becomes:

 

for (int i=myNumber; i < size of the list; i += numberOfThreads)

   process list[i]

 

As far as I can tell this is an example of the isolation approach to concurrency.  The data is carved up into independently processable segments and each segment is handled by a separate thread.  It reminds of the approach that an MPI based program might take.

 

Since the list is fixed and the elements are independent there's no need for locking.

 

Of course, the master thread usually needs some way to figure out when everyone is done.  I tend to have the worker threads signal an event then have the master thread wait on all of the thread's events.  An alternative approach might be to use an InterlockedIncrement/Decrement then have the master thread use an InterlockedCompareAndExchange to continually poll until a counter falls back to zero.

 

 

No comments :

Post a Comment