Mutual-exclusion using TestAndSet() instruction

Question

The book Operating System Principles by Silberschatz, Galvin and Gagne contains the following definition for the TestAndSet() instruction in the chapter on synchronization:

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

An implementation of mutual-exclusion using the above instruction is also provided as follows:

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

Now, how is mutual exclusion achieved if there is no condition for setting target to TRUE?

Consider the following situation, process P0 sets the shared variable lock to TRUE and enters its critical section. Another process P1 calls TestAndSet() in the while loop above, it returns TRUE (since P0 has the lock) while unconditionally setting lock to FALSE. The second time TestAndSet() is called in the while loop it will return FALSE and P1 enters its critical section even though P0 is in its critical section. Mutual-exclusion is then violated.

I did some searching and stumbled upon a paper by Mithun Acharya and Robert Funderlic (of the North Carolina State University CS department) which contains the following alternative definition of TestAndSet():

   boolean Test-and-Set(boolean target)
    begin
        if(target == false):
            target = true;
        return target;
    end

This makes much more sense to me, I included it for comparison and also because the paper lists the book by Silberschatz as one of its references.

I just don't understand how the definition I found in my text book (the one I provided first) can be used to acheieve mutual exclusion, can anyone help?

Answer 1

Here is a way to think about atomic TestAndSet intuitively.

A thread uses it before entering a critical region. Only two cases:

1. Lock is being held (*target is TRUE): return TRUE and *target remains TRUE
2. Lock is NOT being held: return FALSE, and *target is set to TRUE

So either another thread is in the critical region so *target (TRUE) reflects what the value should be; or "I" am entering this critical region now, so set *target to TRUE.