How locks are implemented on multiple cores

Question

For a uni-processor, the lock algorithm is pretty simple.

Lock(threadID) {
  Disable Interrupts
  If lock is already owned by same thread{
    Restore Interrupts
    return
  }
  if lock is free {
    make lock busy
    set current thread as the owner of the lock
  }
  else {
     add threadID to the lock queue.
  }
  Restore Interrupts
  return
}

But how do we implement this code in multiprocessor/multicore systems. What if 2 cores/procs try to give the same lock to different processes.

Discomfort

Answer 1

Mutexes are generally implemented with atomic operations on a single memory value. For instance, a lock can be a single word that is free when 0 and locked when 1. To acquire the lock, the processor will lock the memory bus (so no other processors can read or write to memory), read the most-current value of the word, set it to 1 if it is 0, and unlock the memory bus. To unlock, the word can be set to 0.

That's a simple example that doesn't address what happens when the lock is contended. Different OSs handle that using different mechanisms. Linux uses something called futexes. I'm not sure what Windows or Macs do.

Although the algorithm you posted is correct, non-kernel code can't disable CPU interrupts, so user-space code will tend to use atomic operations even on a single core.

Pinson

Can it be done only with atomic operations, or does it need also system calls(Disable Interrupts)? – Derbent

Answer 2

I say the simplest way to think about the lock is an atomic exchange instruction. The following acquires a lock X.

LOCK:
  set RegisterA = 1
  Atomic_Exchange(X, RegisterA)  //runs such that no other thread can work with X
  if RegisterA == 1:
    Means X was 1 when I esecuted the exchange thus someone else has the lock
    Since I do not have the lock, goto LOCK
  else:
    If A is zero, it means I was the first one to set X to 1, which means I own the lock

UNLOCK:
    X = 0

The atomic exchange exists in most computers. Intel's x86 has an EXCHG instruction for this. Just FYI, Intel's x86 also has a compare-and-exchange instruction which takes care of the acquire as well as the compare for you. Basically, instead of first doing the exchange and then doing the test in software, it uses hardware and does the exchange only if X==0 to begin with. This saves an extra write to the variable X which reduces cache misses for X, leading to higher performance.

Ferricyanide