Need help understanding implementation of mutex with test_and_set

Question

The book Operating System Principles by Silberschatz, Galvin, and Gagne has the following implementation for atomic operations of test_and_set

boolean test_and_set(boolean *target) {
    boolean rv = *target;
    *target = true;
    return rv;
}

They declared a global variable lock initialized to 0 and used the following implementation of the mutex for each process

do {
    while(test_and_set(&lock))
        ; // do nothing
        // critical section
    lock = false;
        // remainder section
} while(true);

Now, let's consider the situation when process P0 is implementing the critical section and process P1 is stuck at the while loop. Consider the following order of execution then

//lock = true initially because P0 is in critical section
P1 boolean rv = *target; //rv = true, lock = true
//P0 now completed its critical section and is ready to leave the lock
P0 lock = false //rv = true, lock = false
P1 *target = true; //rv = true, lock = true
P1 return rv; // returns true

So, the process P0 or any other as a matter of fact cannot enter the critical section forever. How does this handle this case then?

Alain Merigot · Accepted Answer · 2019-03-08T18:34:44.653

You are right in your description and such a situation would lead to a deadlock.
But what you are missing is that test_and_set must be an atomic operation. This is not a test followed by a set but a unique unbreakable operation that performs both.

It is generally implemented by processors with an instruction that 1/ forbids out of order execution, 2/ waits until the pipeline and the memory queue of the processor are empty, 3/ reads the memory in a register and 4/ sets the memory word. The read/write memory cannot be interrupted, no thread swap can happen and memory access is forbidden to other processors.

On risc processors, there is a similar mechanism. You first perform a special load that watches accesses to memory (frequently called load locked) and it is followed by a special store that will fail is any access has been done on the memory location (store conditional).

This way, one can be certain that only one thread has access to the memory during the the test_and_set and the situation that you describe cannot happen.

//lock = true initially because P0 is in critical section
P1 boolean rv = *target; //rv = true, lock = true
//P0 now completed its critical section and is ready to leave the lock
// BUT P0 MUST WAIT THE COMPLETION OF THE TAS.
// NO THREAD SWAP CAN HAPPEN AND ACCESS TO *target IS LOCKED
// DELAYED UNTIL END OF TAS P0 lock = false //rv = true, lock = false
P1 *target = true; //rv = true, lock = true
P1 return rv; // returns true
//NOW WE CAN DO
P0 lock = false //rv = true, lock = false
// AND LOCK IS PROPERLY UNSET
// ON NEXT ITERATION OF THE SPINLOCK WHILE, P1 WILL GET IT.

I misunderstood the meaning of 'atomically'. I misunderstood the sentence "Thus, if two test_and_set() instructions are executed simultaneously (each on a different CPU), they will be executed sequentially in some arbitrary order." to mean that the restriction is only on multiple test_and_set and not on other instructions. Thanks for such a wonderful explanation — Satyam Yadav, Mar 09 '19 at 09:28

Need help understanding implementation of mutex with test_and_set

1 Answers1