The perilous of multithreading

Do not switch to berserk coding mode

Yes, some programmers are very good at quickly writing dozen and dozen lines of code. The problem is that it does not cope very well with multithreaded programming. You need to be very cautious about synchronizations. Handle locks, mutexes, critical sections with care or else: you might end up with invalid data or in a dead lock.

The code would work with single threaded code; but with multithreaded code, it becomes much harder to get a good (correct) idea of the temporal execution of your program. So, pay attention to what is synchronized: make it small and make it readable and for the rest; I leave it to you.

If you store the result in a list, map, database, then you might face a big problem:

most structures are thought to be read by many at the same time OR (exclusive OR) to be written by one AND read by no-one else at the same time
This is basically how boost/stl/generic implementation work

To pin-point the problem: in most of the case, reading and writing onto structures simultaneously might make them incoherent

I have concurrent reads and writes onto my structures, what can I do ?

The most easy solution would be using mutexes ( mutual exclusions). Mutex FTW !

One thread will request the mutex, will eventually acquire it and when its job is done, will release the mutex.
If other threads request the mutex while it is acquired, they will wait.

Mutex are handy but they come at a cost. They are OS objects, and they need a bunch of handles/synchronization/cpu cycles.

Alternatively, OS offers semaphores. They might fit better to your solution.

"Mutexes" are too heavy! I want performances, I want something lighter! You can try Critical Section. Critical Section FTW !

Critical Section are slightly better…
Critical Section are part of execution handled by one thread at a time, other threads will be prevented from executing from the same Critical Section.

But Critical Section does not stop you from delays, indeed your thread can still wait and then be "context" switched.

If you are really targeting performances, you can try Critical Section with Spin Count. It exists on Microsoft system and there's surely an equivalent unix based system

Critical Section is bad! OS is slow! I want to do synchronization by hand: use Interlocked Functions. Interlocked Functions FTW

Those function ensure you that memory access to a variable is "interlocked", meaning that no other threads/cores/processors is reading/writing on this variable. It has a cost (in term of CPU cycles)

It has two drawbacks:

  • sometime the compiler tries to optimize your code, instruction are re-ordered and things go baaaad…
  • It could be worst: the CPU also tries to optimize your code and instruction are re-ordered (x86 does not but PPC does)

You can try to use the c++ "volatile" keyword, or even better, use MemoryBarrier. But that's not all, you might even consider a "memory model".

Quoting Herb Sutter in: Machine Architecture: Things Your Programming Language Never Told You

Memory model:Describes how memory reads and writes may appear to be executed relative to their program order. It ensures you that the CPU optimization will not screw up the precious instruction ordering.

From this point, I would recommend that you do not try to implement again Critical Section and Mutexes that are beyond simplicity ( not 3000 lines of code )

You can think: Microsoft sucks, they do bad programming… I, as a good programmer, can do even better… Okay, but…

  1. you are going to lose time and effort on it, was that the intent ?
  2. you might ignore a lot of details for a good implementation ( your mutex implementation will offer fairness and avoid starving ? )
  3. someone may have the same idea as you (and some years of research in the field) while other offers their implementation

So I recall, if you can, try to rely on your OS function, or if possible, abstract interfaces

Matthew Wilson offers a very nice study of synchronization procedures and their time costs in his book Imperfect C++[1]

Bibliography
1. Imperfect C++: Practical Solutions for Real-Life Programming, Matthew Wilson, Addison Weslew, ISBN-10: 0321228774
Unless otherwise stated, the content of this page is licensed under Creative Commons Attribution-ShareAlike 3.0 License