开发者

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

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!


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


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.


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...


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

0

上一篇:

下一篇:

精彩评论

暂无评论...
验证码 换一张
取 消

最新问答

问答排行榜