Email	Print Reprint
	add to:
	Del.icio.us Digg Google Furl	Slashdot Y! MyWeb Blink
	TABLE OF CONTENTS Data Race Different Ways to Spell "critical section" Code Must Never Move Out Automate Acquire/Release

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]

Previous Page | 1 Data Race | 2 Different Ways to Spell "critical section" | 3 Code Must Never Move Out | 4 Automate Acquire/Release Next Page

RELATED ARTICLES Logging In C++ : Part 2 recls 100% .NET QuickThread: A New C++ Multicore Library C Snippet #8 CUDA, Supercomputing for the Masses: Part 14		TOP 5 ARTICLES No Top Articles.