Use Critical Sections (Preferably Locks) to Eliminate Races

Code Must Never Move Out

Let's see what "code can't move out" means in the context of the following code, which acquires a mutex mut that protects two integers x and y:

mut.lock();   // enter ("acquire")      
              // critical section
x = 42;      // where can this line
             // appear to move to?
y = 43;          
mut.unlock(); // exit ("release")
              //critical section

What are the legal reorderings of the assignment to x? It is perfectly legal for the system to transform the above code to:

mut.lock();
y = 43;
x = 42;   // ok: can move down
          // past y's assignment
mut.unlock();

because both assignments still happen inside the protected critical section (and do not otherwise depend on each other, assuming x and y are independent and not aliased). A system may not, however, transform the code to either

x = 42;    // invalid: race bait
mut.lock();
y = 43;
mut.unlock();

or

mut.lock();
y = 43;
mut.unlock();
x = 42;    // invalid: race bait

because either of these would move the assignment outside the critical section and therefore create a potential race on x.

So what about moving code into a critical section?

It's Okay For Code to Move In

Consider an adapted example:

x = "life";   // where can this line
              // appear to move to?
mut.lock();   // enter ("acquire")
              // critical section
y = "universe";
mut.unlock(); // exit ("release") 
              // critical section
z = "everything"; // where can this 
                 // line appear to
                 // move to?

What are the legal reorderings of the assignments to x and z? Again assuming that x, y, and z are independent and not aliased, it is perfectly legal for the system to transform the above code to:

mut.lock();
z = "everything"; // ok: can move as
                  // far up as this
y = "universe";
x = "life";      // ok: can move as
                 // far down as this
mut.unlock();

Even though the moved lines now run while holding the lock, it doesn't alter the meaning or correctness of the code. It is always safe to add extra guarantees; in this case, to hold a lock a little longer.

But it is not safe to arbitrarily remove guarantees, such as to fail to hold a needed lock. Therefore, a system cannot arbitrarily reorder the code to cross either fence the wrong way:

z = "everything"; // invalid: race bait
mut.lock();
y = "universe";
mut.unlock();
x = "life";     // invalid: race bait

Note that this is true even though the assignments to x and z were not initially inside the critical section. For example, what if setting y = "universe" is treated as a flag that tells another thread that x is now ready to be shared, so that y publishes x? That is why no code must pass the release fence in the downward direction. [3]