Como usar o testandset () para resolver o problema da seção crítica?

Question

Estou estudando para um exame e estou tendo dificuldades com um conceito. Este é o código pseudo -mero que recebeu:

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

Meu instrutor diz que apenas duas das três condições necessárias (exclusão mútua, progresso e espera limitada) são atendidas com esse código, mas não entendo qual não está sendo atendido ... ??

Como o código deve ser modificado para apoiar a condição que falta para resolver o problema da região crítica? Agradecemos antecipadamente por qualquer insight!

Answer 1

Se alguém vê isso procurando a resposta, o código acima não suporta a espera limitada (deve haver um limite na quantidade de tempo que um processo deve esperar). Este é o código correto para garantir que todas as três condições sejam atendidas para garantir a sincroniações usando o 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

Primeiro de tudo, um pequeno exemplo, mas o teste e o teste leva args booleanos e, por padrão, mutex está definido como FALSE. Então int mutex=0 é na verdade boolean mutex=FALSE.O código acima tem exclusão e progresso mútuos, mas não limitou a espera. Também sua definição de testandset está errado. Deveria ser target=TRUE e não target=TRUE.

Answer 3

É porque o mutex deve ser definido usando instruções de carga atômica e armazenamento para que o acesso à memória não seja reordenado? A execução atômica de um conjunto de instruções significa que as instruções são tratadas como uma única etapa que não pode ser interrompida.

// 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;
}

Apenas olhando para ele, parece que as funções fazem a mesma coisa que o código de amostra publicado anteriormente, mas acho que dessa maneira garante a exclusão mútua porque as funções que operam no *Target são atômicas ... ??

Desculpe qualquer erro de digitação ...

Answer 4

A espera limitada não é encontrada aqui. Você pode ver que lá deve estar vinculado ao número de vezes que um processo específico pode entrar em seção crítica, para evitar a fome de outros processos ... e deve haver um limite no tempo em que um processo deve esperar