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

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.

Answer 2

I think Test-and-set shall be (or implemented with) atomic compare-and-exchange, e.g. InterlockedCompareExchange() on Windows (http://msdn.microsoft.com/en-us/library/ms683560(VS.85).aspx)

Using atomic operations, mutual exclusions can be implemented without locking.

Answer 3

When P0 is executing It has set the lock=true via TestAndSet() and if P1 comes to execute while P0 is executing, it will stay in the while loop until and unless the lock is false again due to

while(TestAndSetLock(&lock));

Notice the ; at the of while Loop.

and when the lock has been released (e.g. lock = false again) it will come out of the while loop and execute other instructions.

But what I don't understand is another problem (of the same Book Galvin p233):

do { 
waiting[ i ] = TRUE; 
key = TRUE; 
while (waiting[ i ] && key) 
  key = TestAndSet(&lock); 
  waiting[ i ] = FALSE; 

  //critical section 

  j = (i + 1) % n; 
  while (( j != i) && !waiting[ j ]) 
  j = ( j + 1) % n; 
  if ( j == i) 
    lock = FALSE; 
  else 
    waiting[ j ] = FALSE; 

  //remainder section 

}while(TRUE);

Here My problem is: P0 will execute first and I assume that p1 also wants to enter the Critical section. so it will make waiting[1] = false (Remember than p[0] has come Out of the Critical section) but then what will happen after that ?? ther is no statement like i = j and the value of i is still same and unchanged. then why on the earth it will come to let p[j] a chance to enter Critical section. if p1 starts executing it makes waiting[1] = true and key = true But lock is still true Cause p[0] will release the lock only when the circular queue comes to itself (e.g. j == i) . it will only come to make lock= false if and only if all other processes are unwilling to enter the Critical section. and if lock is false P1 will wait in the while loop infinitely. I cant understand how this can be a Solution.

I think this One (Figure 6.8) is Incomplete in Galvin's book. However I'vent found teh Complete One anywhere in the net. everybody uses this example without further clarification.

Answer 4

to Neel Basu: suppose p0 will execute first and p1 also wants to enter the critical section.then waiting[0]=true and so is waiting[1];and we assume loce=false . thus in p0,key=TestAndSet(&lock) key will be false ,after that p0 will go out of the "while" but p1 will still stay in it; after this ,p0 enters its critical section and go out of it.then,j=i+1 (here j=1) since j==i==1,lock will be assigned false thus breaking the while in p1 .and p1 will also go into its own cs.

Answer 5

To use the testAndset method, we begin with a variable called Lock, which is set to alse: HdwareData lock = new HdwareData(false);

Answer 6

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.