Screen Version

School of Computer Science & Engineering
University of New South Wales
 Advanced Operating Systems 
 COMP9242 2002/S2 

Total Store Ordering

• Stores to write buffer hide memory latency.
• Loads read from write buffer if possible.
• Stores are guaranteed to occur in FIFO order.

CPU 0
store	r1, adr1
load	r2, adr2

CPU 1
store	r1, adr2
load	r2, adr1

• Both CPUs may read old values!

Total store ordering breaks Decker:

void lock (volatile lock_t *l) {

   l->status[MYSELF] = LOCKED;

   while (l->status[OTHER] == LOCKED) {

      if (l->turn != MYSELF) {

         l->status[MYSELF] = !LOCKED;

         while (l->turn == OTHER) ;

         l->status[MYSELF] = LOCKED;

} } }

• Need hardware support for synchronisation, e.g.:
  • atomic swap,
  • test&set,
  • load-linked & store-conditional (LL&SC),
  • memory barriers.
• Stall pipeline and drain (& bypass) write buffer.