[SOLVED]Understanding Spinlock Principles in Multi-CPU Environment

[shizi]

"I'm diving into low-level synchronization for my OS project and have hit a conceptual wall regarding spinlocks on multi-CPU systems. I understand that they rely on atomic operations, but the hardware interaction eludes me.

My core confusion lies in this apparent contradiction:

1. If the lock is just a variable in globally-visible memory, and one CPU acquires it by writing lock=1, why does this simple write prevent other CPUs from entering the critical section? What physically stops them?
2. Conversely, after a CPU successfully acquires the lock (and has written lock=1), why doesn't that same CPU get stuck in the spinloop when it checks the lock value again? It would see lock=1 and should, in theory, wait for itself—which is absurd.

Thanks for any insights that can clear this up!"

[iansjack]

1. I don't think anything physically prevents other threads from entering the critical system. But the OS is written so that any access requires acquisition of the lock first. It's software protection, not hardware.

2. The thread that has the lock doesn't need to acquire it again, so it doesn't need to check it. Rather it frees the lock when it exits the critical section.

[nullplan]

1. If the lock is just a variable in globally-visible memory, and one CPU acquires it by writing lock=1, why does this simple write prevent other CPUs from entering the critical section? What physically stops them?

Nothing. All CPUs have to voluntarily participate in the locking system for it to work.

2. Conversely, after a CPU successfully acquires the lock (and has written lock=1), why doesn't that same CPU get stuck in the spinloop when it checks the lock value again? It would see lock=1 and should, in theory, wait for itself—which is absurd.

I get the feeling we may need to look at your code. The CPU should be using an atomic primitive to both set the lock to 1 and verify that it was 0 before that. The simplest way to do that is with the XCHG instruction on X86:

Code: Select all

static inline int a_swap(volatile int *p, int v) {
  __asm__ ("lock; xchg %0, %1" : "+m"(*p), "+r"(v));
  return v;
}

struct spinlock {
  int lock;
};

void acquire_lock(struct spinlock *l) {
  while (a_swap(&l->lock, 1)) __asm__("pause");
}

void release_lock(struct spinlock *l) {
  a_swap(&l->lock, 0);
}

This way, only a single CPU can ever set the lock to 1 when it was zero before. If the lock is 1, the CPU will both write and read 1, which does nothing. Only when the lock is actually zero can a CPU break out of the loop. And because the operation is atomic, an unlocker cannot come between the read and the write.

If the same CPU called acquire_lock() on the same lock again, then yes, it would deadlock. There is nothing preventing this because this simple lock does not track ownership. If you want recursive lock semantics, that is what you need to do.

Also note that this lock is horrible on long-contended locks, because the CPUs stuck in the acquire loop never go to sleep. And note that, to be interrupt-safe, the acquire function would have to save the interrupt flag and then block interrupts, and the release function would have to restore the interrupt flag to its prior state. Look at Linux for an example (functions spinlock_irqsave() and spinunlock_irqrestore()).

[shizi]

The CPU should be using an atomic primitive to both set the lock to 1 and verify that it was 0 before that. The simplest way to do that is with the XCHG instruction on X86

Thanks for your reply! I used to think that the CPU would see the new value, but now I understand that it actually reads the old value (via the atomic exchange instruction). I've now successfully implemented it following your approach.