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?

Altman

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.

Besnard

Could you also please explain why it doesn't satisfy bounded buffer condition?? – Sweatshop

@nj-ath, There is no definitive gurantee that a process that is waiting for lock gets the lock with certain fixed amount of time. – Circumgyration

@nj-ath, >If there are multiple processes trying to get into their critical sections, there is no guarantee of what order they will enter, and any one process could have the bad luck to wait forever until they got their turn in the critical section. (Since there is no guarantee as to the relative rates of the processes, a very fast process could theoretically release the lock, whip through their remainder section, and re-lock the lock before a slower process got a chance.) – Circumgyration

Answer 2

The implementation shown can be written more clearly like this:

while(TestAndSet(&lock))
{
   // spin in this loop until TestAndSet returns false
}
do_critical_section_stuff();
lock = FALSE;
// We've now left the critical section

I think the OP was misinterpreting it as:

while(TestAndSet(&lock))
{
   lock = FALSE;
}
do_critical_section_stuff();

which wouldn't work properly for obvious reasons.

Maxilliped

Answer 3

Ah I had that question also. Let me share my understanding.

Initially *target will be FALSE.(that's a given). It is true that P need to pass while(TestAndSetLock(&lock)) ; // do nothing to obtain the lock and enter the critical section. (obtaining the lock is just an hypothetical thing, if it can pass the while loop then it has the lock)

someone has the lock means target is TRUE, lock is free to be taken is target is FALSE. so in the beginning it's like this,

P1 (the very first to call the function will get lucky), he sees the target is FALSE and set it to true and RETURN FALSE, which leads it to avoid the while loop wait.

Now the target is TRUE.Other fact is TestAndSet(boolean_ref lock) will return the called value, And TestAndSet(boolean_ref lock) will ALWAYS set the target to TRUE so someone has to set target to FALSE in somewhere else (so the one with the lock can set it to FALSE)

Other P's will come and see that target is TRUE and when calling TestAndSet(boolean_ref lock) it will return TRUE always until P1 set target to false.

And I found this nice graphical explanation from This site, you can download it from here

Anibalanica

Answer 4

The TestAndSet function you initially quote is executed only when target is false. I.e. the thread is blocking until target is false. I don't have that text book, but I'm sure it's mentioned somewhere in the text.

Please note the TestAndSet is an "atomic" function that must be implemented in the lowest levels of the OS (or even by the instruction set of the CPU). If it's implemented in a user application, a context switch may occur between the test and the set, causing corruption.

Clarification: I'm only sure of the fact the function is executed when target is false because somewhere these must be a comparison operation that is blocking. There are two types of TestAndSet - one that returns only when the target is set to True (blocking), and one that may return False, i.e. return immediately (that one will enable polling by another thread). I assume the one you quote is blocking because it seems to return immediately after starting execution, which would mean the "IF" statement is executed by a lower level mechanism, e.g. the CPU or OS kernel.

Jene

I haven't come across the fact that TestAndSet() is executed only when target is false. I've checked both the textbook ad Wikipedia. However, it does make sense, i'll look into it. – Altman

There's no blocking in the example shown, the while(TestAndSet()) loop just spins until the condition changes. While it's wasteful of CPU, threads don't actually have to block when waiting for something to happen. Look up "spinlock" on Wikipedia for more context. – Maxilliped

Answer 5

To use the testAndset method, we begin with a variable called Lock, which is set to false:

HdwareData lock = new HdwareData(false);

Reorganize

Answer 6

By looking at the implementation of the mutual exclusion of TestAndSet(&lock), one can safely say that as long as TestAndSet returns true, the process(P) will not enter its critical section. The process will continue executing in its loop condition until it(the condition) fails.

The condition will succeed(TestAndSet will return true) as long as another process has a lock on the resource. When another process has a lock on the resource, the value of lock is true. As soon as the other process releases its hold over the resource, by setting lock = false, TestAndSet will return false.

When TestAndSet returns false, the condition for the while loop fails and hence process P enters its critical section.

TestAndSet is an atomic operation, ie it is executed without interruptions. This is done to prevent race conditions with the lock.

Biz

Answer 7

Think non-linearly. You pointed out three issues in the definition Silberchatz provided to implement the testAndSet() function:

(1) you correctly stated that target is set to TRUE unconditionally, and realized (mistakenly) that is a problem.

(2) In order to address the problem in (1) (which is non-existent), you proposed that target be tested before setting it to TRUE.

(3) Finally, you showed your concerns regarding the fact that result is set to FALSE also unconditionally by the block that implements the Mutual Exclusion (this does not actually happen).

I will try to clarify these issues. Initially, note that the first thing the function TestAndSet() does is to copy the value of target to rv and only afterwards target is set unconditionally to TRUE. Now, the catch: if target was originally FALSE, TestAndSet() sets target to TRUE and returns FALSE, so the process can enter the critical section. In case the original target value was TRUE, it is set to TRUE anyway (which causes no harm) and TestAndSet() returns TRUE, so the process can NOT enter the critical region. So, setting target unconditionally to TRUE is not a problem and issue (1) proves non-existent.

Regarding issue (2), once it is demonstrated above that it is harmless to set target to TRUE unconditionally, there is no need to test its value beforehand.

Issue (3) is also non-existent because result is not really set unconditionally to FALSE. I mean, it is, but only AFTERWARDS the critical region has been processed by the process; i.e., when the mutual exclusion is no longer necessary. The process HAS TO set target to FALSE as soon as it leaves the critical section (it is not supposed to block any other processes after exiting the critical section). It is mandatory to release the lock after processing the critical section!

To

Answer 8

Consider the following highlighted part in your question:

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.

The P1(or any process), irrespective of lock being True or False, doesn't set the value of lock to False.

• If the lock is value is False, it enters critical section and sets its value to True, thereby grabbing the lock.

• If the lock value is True, it does nothing(sets its value to True, thereby not changing it) and waits for the lock value to turn to False(which happens when process that has the lock completes the execution of its critical section).

Circumgyration