Multiprocessor (aka Multicore) Synchronization

The general idea

Programming applications for multiple processors is increasingly and issue because of the growing trend towards multicore designs. A multicore design is no different in the programming challenges, even if it is cheaper than a traditional multi-chip design. Specifically, there is a big bottleneck in implementing simple approaches to locking to safeguard critical sections.

A simple spin lock may be implemented as follows

init_lock (lock) {
  lock = unset;
}

set_lock (lock) {
  mylock = set;
  while (mylock == set);
    atomic_swap (mylock, lock);
  // on exit from loop lock == set, my_lock == unset
}


free_lock (lock) {
  lock = unset;
}

Assuming atomic_swap results in the memory system ensuring that any modification to a lock variable results in flushing it from other caches before another processor can modify it, this will work, but will result in a lot of memory traffic when several processors are spinning on a lock, as they are modifying it every few instructions.

The challenge

Locks implemented through atomic memory operations presents the following challenges

several processors spinning on a lock generate a lot of contention
simple improvements e.g. when spinning only read the value, and only try to swap the value when it changes, still result in a lot of memory traffic when the lock is released

There are various approach to more efficient locks, such as ticket locks. You are required to find one such approach, and analyze the reduction in memory traffic the approach will result in, as well as implementing a test bed to measure performance differences of the approaches you are comparing (simple versus at least one signficant improvement).