Fence instructions may not ensure sequential consistency

At CAV08 recently in Princeton, New Jersey, I heard folks say that compilers could always add fence instructions to generated code in order to ensure that the code produced only sequentially consistent results.

In some cases this is not true.

Most machines these days violate sequential consistency in two ways.

  1. A machine executes instructions out of order. Specifically, a machine executes load operations before logically preceding store operations.
  2. A machine performs store operations nonatomically.
If a machine executes instructions out of order (but is write atomic), then a compiler can indeed insert fence instructions into the generated code to prevent instructions from being executed out of order, and so, in this situation, ensure sequentially consistent results.

If a machine is not write atomic, then the following test case (from [DSB86]) involving threads T0, T1, and T2, can occur. 

  Initially, A = B = X = Y = 0.

          T0          T1          T2
        A = 1;      B = A;      X = B;
                                Y = A;

  Terminally, A = B = X = 1, Y = 0.
If the write into A is performed nonatomically, so that X receives the new value of A (via B) while Y receives the old value, then no number of fence instructions added to this code will necessarily create a sequentially consistent result.

Reference

Site Map

Last updated August 11, 2008.