Multi-threading without locks

[DeepT]

I have two threads, one of them needs to run as fast as possible(because timing is very important) while the second thread is an expensive thread to run.

The problem is that thread 1 and thread 2 have some objects in common. Traditionally I would just lock the object before using it. The issue with this is, that if thread 1 needs an object being used by thread 2, it could end up waiting a long time for thread 2 to finish, which pretty much defeats the purpose of it being on another thread.

An example of this in a video game. Thread2 is the render thread, and one thing it does is go through a list of sprites to draw.

If in thread 1, a space ship decides to fire a bullet, it will need to add a sprite to the list of sprites to draw. If thread2 is iterating through this list when thread1 tries to add it, you can see the problem.

Is there some way I can design two systems like this to work together without locking?

[googler]

I have two threads, one of them needs to run as fast as possible(because timing is very important) while the second thread is an expensive thread to run.Sorry to disappoint you but threads all run at the same speed and cost the same amount of money to run every time slice. The only choice you have is whether to run them or not.

If in thread 1, a space ship decides to fire a bullet, it will need to add a sprite to the list of sprites to draw. If thread2 is iterating through this list when thread1 tries to add it, you can see the problem. Use double buffering. Have your rasterizing thread lock and display one list of sprites, and the rest of the program add and remove sprites from another list of sprites. Then when it's time for another display cycle, switch lists.

[JVene]

I hope you don't mind me pointing out:


...threads all run at the same speed...


there is the option of setting priority, depending on the OS features for supporting it.


googler's idea of multiple lists is a good one. Using the same basic notion, what I've done on certain occasions is to have the 'second' thread place it's new items in a 'submission list' - a list of things to be added.

The primary thread will service that list between cycles - take the list of new submissions and append them to the container.

This does require a short lock on the 'submissions list' container, but it's usually (in my observations thus far) faster because it's one lock per cycle (from the display thread's view), rather than one per item (in the otherwise 'standard' approach). That is, there's only one possible 'moment' for lock contention, instead of one at every submission.


If your container is not sorted, and otherwise isn't violated by this second approach, you can perform a lock free container extension, though I'm not sure about STL other than vector without iterators. If your display list and main container were an array, for example, or a vector, you could append entries to the end of the container in such a way that it doesn't interfere with the display thread's 'view' of that container is never corrupt (out of date, occasionally, but never corrupt).

[googler]

there is the option of setting priority, depending on the OS features for supporting it.Right, and when a high-priority thread gets scheduled, it runs at exactly the same speed as when a low-priority thread runs at when it gets scheduled, which is the clock speed of the CPU. I suppose in theory you could have a computer with several CPUs all of which are identical except for their clock speed. But computers built based on the SMP (= symmetric multi-processing) model have identical CPUs, speed included. There are some other multi-processor architectures like connection machines, or computers that have special I/O processors, but the distinguishing features between CPUs there are not focused around their speed.

[Arjay]

In addition to the other suggestions:

1) Remember to keep you're locks to the absolute minimum - lock as late as possible and release as early as possible.
2) Consider having your containers store pointers to items. Depending on the size of the objects being stored, you may find shorter lock times if you store a pointer the object rather than having to make a copy constructor call every time you push an item onto the container. For small items there probably isn't much different (than storing the ptr), but it can make a difference for larger items.