Everyone knows the basics of how to use locks:
mut.lock(); // acquire lock on x ... read/write x ... mut.unlock(); // release lock on x
But why do locks, lock-free styles, and other synchronization techniques work at all, never mind interoperate well with each other and with aggressive optimizers that transform and reorder your program to make it run faster? Because every synchronization technique you've ever heard of must express, and every optimization that may ever be performed must respect and uphold, the common fundamental concept of a critical section.
Data Race
A data race (or just "race") occurs whenever the same memory location can be accessed simultaneously by more than one thread, and at least one of the accesses is a write. Consider the following code, where x is a shared object:
Thread 1 Thread 2 x = 1; obj.f( x );
Thread 1 writes x and Thread 2 reads it, and so this is a classic race if there is no synchronization that prevents the two threads from executing at the same time.
How potentially bad it can be to have a race? Very, depending on your language's and/or platform's memory model, which sets forth limits on compiler and processor reordering and on what, if any, guarantees you can expect. For example, in Java, "very strange, confusing, and counterintuitive behaviors are possible," including seeing partly constructed objects. [1] In POSIX threads (pthreads), there is no such thing as a benign race: Nearly any race could in principle cause random code execution.
Clearly, we want to eliminate races. The right way to do that is to use critical sections to prevent two pieces of code that read or write the same shared object from executing at the same time. But note:
- Not every object is shared for its entire lifetime: You only need to protect it with critical sections while it is shared, or while it is in transition from unshared to shared and vice versa (for instance, when a previously private object is first "published" to other threads by being made reachable outside its original thread).
- A shared object need not be protected in the same way for its entire lifetime: It is perfectly legitimate to protect the same object using locks at some times and lock-free techniques at others. Next month, I'll consider some examples in detail.