Most mutual exclusion and synchronization mechanisms use hardware atomic operations. However, it is possible to implement mutual exclusion entirely in software.
Some language-level mutex implementations rely on machine-level support such as Test-and-set.
Atomic operations -- Test-and-set
In computer science, the test-and-set instruction is an instruction used to write 1 (set) to a memory location and return its old value as a single atomic (i.e., non-interruptible) operation. If multiple processes may access the same memory location, and if a process is currently performing a test-and-set, no other process may begin another test-and-set until the first process's test-and-set is finished. A CPU may use a test-and-set instruction offered by another electronic component, such as dual-port RAM; a CPU itself may also offer a test-and-set instruction.
int test_and_set(int x) // let x be strictly either 0 or 1.
{
if (x) { return 1; } else { x=1; return 0; }
}
All this needs to be implemented atomically, in hardware.
A lock can be built using an atomic test-and-set instruction as follows:
function Lock(boolean *lock) {
while (test_and_set(lock) == 1);
}
The calling process obtains the lock if the old value was 0 otherwise while-loop spins waiting to acquire the lock. This is called a spinlock.
//implement thread lock(l) simply as
while test_and_set(l) { do nothing; } // spinlock version of thread_lock()
volatile int lock = 0;
void Critical() {
while (TestAndSet(&lock) == 1);
critical section // only one process can be in this section at a time
lock = 0 // release lock when finished with the critical section
}
The assembly instruction test and set can be made to be atomic across multiple processors. An equivalent option would be an atomic compare and swap assembly instruction.
These low-level hardware solutions are then built up into high-level functions, either built into the languages, or in libraries. In general, do not implement your own locking functions, but rather use functions from a tested library. Getting things right can be tricky, and your own solution is also likely to be non-portable.
more ref:
https://stackoverflow.com/questions/1485924/how-are-mutexes-implemented
https://stackoverflow.com/questions/1726702/how-are-mutex-and-lock-structures-implemented
