How to implement a lock in software when no hardware atomic operations are provided?
In Boost.Lockfree documentation, they say that:
Some architectures do not provide the necessary atomic operations in natively in hardware. If this is not the case, they are emulated in software using spinlocks.
One way I can think of is the Dekker's algorithm which only requires non-tearing stores to work. But it only works for 2 processes. Then there is the Peterson's algorithm, which can handle N processes, but N has to be statically known. But I don't know anything that works for locking among dynamic-N processes.
Other ways that come to my mind is to disable all interrupts and context switches and power off all other cores. But these are extreme and I don't think that is done in practice.
What you do is make a call to the kernel, for example as described in pthread_spin_lock. The kernel is responsible for tracking the information across all processes.
Internally the kernel has a copy of itself running on each CPU. You noted that Peterson's algorithm works between N processes, if N is statically known. However inside the kernel the number of things that need to cooperate is the number of CPUs. This the kernel DOES statically know, and so that's where the actual lock logic can be defined.