Тестирование и установка в Mutex Solution

Я пытаюсь проверить правильность этого решения для мьютекса, и мне нужно убедиться, что взаимное исключение, живость и справедливость удовлетворяются. L1 и L2 — это произвольные строки кода. Одновременно запущено 2 процесса. Ниже приведен код процесса i, а код процесса j симметричен.

bool waiting[i] = false;
bool waiting[j] = false;
bool busy = false;

cobegin(process i)

L1: Si(1)
L2: Si(2)
    waiting[i] = true;
L3: while (waiting[i] and TST(busy));
L4: [ Critical Section ]
L5: waiting[i] = false;
L6: busy = false;
L7: while(waiting[j];
L8: Go to L2

Я понял, что все три свойства удовлетворены, но мне просто нужно убедиться, что я ничего не пропустил. Можете ли вы найти свойство, которое не устраивает?


operating-system concurrency mutual-exclusion
person ratsimihah    schedule 11.04.2013    source источник
comment
Это похоже на алгоритм Петерсона. И вы действительно можете симулировать подобные вещи.   -  person Alexey Frunze    schedule 11.04.2013
comment
Это умно, спасибо!   -  person ratsimihah    schedule 11.04.2013
comment
На первый взгляд, даже я подумал, что это близко к алгоритму Петерсона, но потом заметил, что это просто аппаратное решение, основанное исключительно на test_and_set.   -  person unxnut    schedule 11.04.2013

Ответы (1)


arrow_upward
1
arrow_downward

В строке L3 waiting[i] всегда будет true, потому что вы только что изменили его на true в предыдущей строке. Я так понимаю, что TST является аппаратной реализацией неделимой инструкции test_and_set. В этом случае вы можете просто работать с while ( TST ( busy ) );, и решение будет правильным. Флаг waiting, похоже, не служит никакой цели.

person unxnut    schedule 11.04.2013
comment
Ваше предположение о TST верно. Кажется, что наши результаты совпадают, и взаимоблокировки, живые блокировки или нарушение мьютекса и справедливости невозможны. - person ratsimihah; 11.04.2013
comment
Вы правы в своем заключении. Единственное, что я изменю, это избавлюсь от ожидания, чтобы упростить код. - person unxnut; 11.04.2013
comment
На самом деле флаги ожидания, кажется, обеспечивают справедливость. Без них одна из ps могла бы просто зацикливаться, а другая ps проверяет блокировку в неподходящий момент, когда она верна. - person ratsimihah; 11.04.2013
comment
Я не вижу, как флаг ожидания обеспечит справедливость. Как видно из кода, ожидание i становится истинным, а проверка других ожидающих находится в разделе выхода. У вас должен быть своего рода механизм передачи обслуживания с использованием некоторого логического счетчика на случай, если вы хотите обеспечить выполнение условия ограниченного ожидания. - person unxnut; 11.04.2013