Mutex/Locks Implementation

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