Как использовать TestAndSet () для решения проблемы критической секции? - PullRequest
Новая
       28

Как использовать TestAndSet () для решения проблемы критической секции?

0 голосов
/ 07 апреля 2010

Я готовлюсь к экзамену, и у меня возникают трудности с концепцией. Это псевдокод, который мне дают: 

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

Мой инструктор говорит, что с этим кодом встречаются только два из трех необходимых условий (взаимное исключение, прогресс и ограниченное ожидание), но я не понимаю, какое из них не выполняется ... ??

Как изменить код для поддержки отсутствующего условия для решения проблемы критической области? Заранее спасибо за любую информацию!

Ответы [ 4 ]

3 голосов
/ 07 апреля 2010

Если кто-то видит это в поисках ответа, приведенный выше код не поддерживает ограниченное ожидание (должно быть ограничение на количество времени, которое процесс должен ждать). Это правильный код, обеспечивающий выполнение всех трех условий для обеспечения синхронизации с использованием 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);
1 голос
/ 12 сентября 2012

Прежде всего, хороший маленький пример, но testandset принимает логические аргументы, и по умолчанию мьютекс установлен на FALSE. Таким образом, int mutex=0 на самом деле boolean mutex=FALSE. Приведенный выше код имеет взаимное исключение и прогресс, но не ограниченное ожидание. Также ваше определение testandset неверно. Это должно быть target=TRUE, а не target=TRUE.

0 голосов
/ 12 января 2013

Ограниченное ожидание здесь не встречается. Вы можете видеть, что должно быть определено количество раз, которое конкретный процесс может перейти в критическую секцию, чтобы избежать голодания других процессов ... и должно быть ограничение на время, в течение которого процесс должен ждать

0 голосов
/ 07 апреля 2010

Это потому, что мьютекс должен быть установлен с использованием атомарных команд LOAD и STORE, чтобы доступ к памяти не переупорядочивался? Атомное выполнение набора инструкций означает, что инструкции обрабатываются как один шаг, который нельзя прервать. 

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

Просто глядя на это, кажется, что функции делают то же самое, что и пример кода, опубликованный ранее, но я предполагаю, что этот способ обеспечивает взаимное исключение, потому что функции, работающие с * target, являются атомарными ...

Извините за любые опечатки ...

...