How to use TestAndSet() for solving the critical section problem?

Question

I'm studying for an exam and I'm having difficulty with a concept. This is the pseudo code I am given:

int mutex = 0;
do {
  while (TestAndSet(&mutex));
  // critical section
  mutiex = 0;
  // remainder section
} while (TRUE);

My instructor says that only two of the three necessary conditions (mutual exclusion, progress, and bounded waiting) are met with this code, but I don't understand which one isn't being met...??

How should the code be modified to support the missing condition to solve the critical region problem? Thanks in advance for any insight!

Answer 1

If anybody sees this looking for the answer, the above code does not support bounded waiting (there must be a bound on the amount of time a process has to wait). This is the correct code to ensure all three conditions are met to ensure synchronyzation using SetAndTest:

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);

Answer 2

First of all nice little example but testandset takes boolean args and by default mutex is set to FALSE. So int mutex=0 is actually boolean mutex=FALSE.The above code does have mutual exclusion and progress but not bounded waiting. Also your definition of testandset is wrong. It should be target=TRUE and not target=TRUE.

Answer 3

Is it because the mutex should be set using atomic LOAD and STORE instructions so that memory access is not reordered? Atomic execution of a set of instructions means that the instructions are treated as a single step that cannot be interrupted.

// example process using mutual exclusion
void process() {
  int mutex;
  init_lock (&mutex);
  do {
    lock (&mutex);
    // critical section
    unlock (&mutex);
    //remainder section
  } while(TRUE);
}

// mutual exclusion functions
void init_lock (int *mutex) {
  *mutex = 0;
}

void lock (int *mutex) {
  while(TestAndSet(mutex))
}

void unlock (int *mutex) {
  *mutex = 0;
}

int TestAndSet(*target) {
  int rv = *target;
  *target = 1;
  return rv;
}

Just looking at it, it appears that the functions do the same thing as the sample code posted earlier, but I guess this way ensures mutual exclusion because the functions operating on *target are atomic...??

Excuse any typos...

Answer 4

Bounded waiting is not met here. you can see there must be bound on the number of times a particular process can go into Critical Section , inorder to avoid starvation of other processes ...and there must be a bound on the time a process should wait