Good example problems to solve with threading

Question

I have used threads one or two times to try and boost the performance of my code, with varying degrees of success. It is obvious that I need some more experience working with multi thread code. Are there any good programming problems to solve which will help to get a grip on using multiple threads to improve performance?

It would be nice if it is a known/well explored problem so that after I have botched a couple of attempts I can read some literature on how it should be done.

-- edit

I am interested in using parallelism to speed up applications in general, as I have heard/read a lot recently about processors increasing power through parallelism rather than speed. I know vaguely of barbers/philosophers but was looking for something a little more practical, to gain hands on experience.

Answer 1

The standard multithreaded problem is the producer-consumer problem. It exists in various flavors that highlight different problems with multithreaded applications. The link I referenced also has several other threading problems listed at the bottom of the page.

Answer 2

Try the Dining philosophers problem It's an excellent metaphor for a classic multi-process synchronization problem.

There are on line examples that show it working, some of which are really quite cool. e.g. one java applet I found with almost no searching :)

Basically the problem goes thusly. You have five philosophers sitting at a table, each philosopher has a bowl of rice and one chopstick. There is a spare chopstick in the middle of the table, so only one philosopher can eat at any given time (in this universe philosophers only think OR eat). After eating for a short time the philosopher will put down the communial chopstick, and think for a while, before eating again.

This allows another philosopher to have the chopstick and allows him to eat for a while.

The problem works with any number of philosophers and chopsticks, once chopsticks are less than philosophers.

It applies to threading becase

• Each philosopher is a thread
• The communial chopstick is a resource needed by all threads.
• Eating is the thread in operation
• Thinking is the thread sleeping, or at rest.

I've done out the exercise my self, you can use buttons on a form to represent the philosophers/threads, and change the colour of the button to refelect which one is eating/working/has the communial chopstick/resource.

It's a good example because you can test different methods for allocating the chopstick (i.e. a) who ever grabs it first, b) hand around in rotation, c) keep exclusivly until you don't need it anymore). The thread won't finish until all the rice is gone out of the bowl so, if you don't have a fair method of sharing the chopstick, you'll have some bowls finish quickly while some philosophers literally starve.

Hope this helps,

BW

Answer 3

If you want parallell computing, try to do some distributed matrix calculations (adding and so forth) or parallelizing a large set of small problems like a bunch of vector operations.

Edit: There is some other problems listed under the dining philosophers' problem on wikipedia, like sleeping barber problem.

Answer 4

On a more practical level, I did find multi-threading very handy when I had to code an process which:

• has no global or shared resources (so no diner with the philosophers ;)
• is very long to run
• has to be repeated with different parameters

To repeat that process sequentially is a waste of time, especially if the first run crashes (all the other runs which may have succeeded with their parameters do not start)

If you launch multiple instances of this process, each in their own thread, you do not have a purely sequential run, but parallel runs which can go on, even of one of them fails.

You have to be careful to include the name of the thread in your log file, though, otherwise you would have a hard time to follow what is going on ;)

Answer 5

I tend to use two threads. One to handle user input, and make the front end as responsive as possible, and the other to do all the work behind the scenes.