Can Test and Set be implemented in software without hardware support?

Question

Here's the Test and Set written in software:

boolean TestAndSet(boolean *target) {
    boolean rv = *target;
    *target = TRUE;
    return rv;
}

and

do {
    while(TestAndSetLock(&lock))
        ; // do nothing
        // critical section
    lock = FALSE;
        // remainder section
} while(TRUE);

Can we use the mechanism in CPUs that do not support test-and-set at the hardware level? If so, how is atomicity assured?

Answer 1

You can use Lamport's 'bakery' mutual exclusion algorithm on machines w/o TAS/CAS to gate access to the 'atomic' (protected) value.

http://www.disi.unige.it/person/DelzannoG/SO1/AA0607/bakery.htm

It only gets complicated if you don't have a reasonably limited 'N' processes.