Реализация мьютекса с атомарной операцией test-and-set: будет ли она работать более чем для 2 потоков?

Question

Я читаю статью в Википедии об атомной операции test-and-set . В нем говорится, что одним из способов реализации взаимного исключения является использование блокировки на основе теста и набора.

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

Так работает ли мьютекс, основанный на операции test-and-set, только для двух потоков? Если да, то как реализованы «настоящие» мьютексы?

Answer 1

Следует отметить, что взаимное исключение по сути является эквивалентом консенсуса для двух потоков.Другими словами, для реализации взаимного исключения необязательно иметь n-поточный консенсус.- @ Комментарий Эрика

Я настоятельно рекомендую прочитать Искусство многопроцессорного программирования , от Мориса Херлихи и Нира Шавита.На самом деле, на странице test-and-set Wikipedia цитируется статья Херлихи о том, что "test-and-set имеет конечное число консенсуса и может решить проблему консенсуса без ожидания"для не более чем двух одновременных процессов ".

В главе 5 книги обсуждается консенсус с использованием примитивных операций синхронизации, но я верю, что глава 7 заинтересовала вас: они обсуждают, как TAS (тест и установка)Инструкция может быть использована для реализации блокировки в Java.Спойлер со стр. 145:

public class TASLock implements Lock {
  AtomicBoolean state = new AtomicBoolean(false);
  public void lock() {
    while (state.getAndSet(true)) {}
  }
  public void unlock() {
    state.set(false);
  }
}

Так работает ли мьютекс, основанный на операции проверки и установки, только для двух потоков?

Простой ответ:нет, они работают для более чем двух потоков.

Если да, то как реализованы "настоящие" мьютексы?

На той же странице Википедии цитируется CAS ( сравните-и-поменяйте ) какболее мощная альтернатива ТАС, но в книге представлено обширное обсуждение по этому вопросу.Более того, это уже было задано здесь в SO, поэтому я рекомендую прочитать ответы Как реализованы мьютексы?

Answer 2

«Правильным» решением является наличие флага «бесперебойного режима», который имеет следующие свойства:

1. атомарное чтение и запись (у вас это есть с оператором test-and-set);
2. Ваше приложение не может быть прервано ни при каких условиях (перепланирование потока и т. Д.), Пока это установлено.

У вас есть один удерживающий поток под мьютексом и n ожидающих потоков, которые помещаются в очередь (любой вид списка, но я предпочитаю очередь.) При блокировке мьютекса вы переходите в непрерывный режим путем атомного тестирования / установки вашего флаг (вращаться или спать, пока флаг установлен), и либо получить мьютекс, либо войти в очередь для этого (в последнем случае текущий поток не может повторно войти в очередь готовности планировщика.) При разблокировке вы переходите в режим бесперебойного и освободить мьютекс к следующему потоку в очереди, если таковой имеется.

Я думаю, что libpthread и такие реализовали мьютексы таким образом. Само по себе это не сложно, но решения либо окончательно верны, либо неверны.

Надеюсь, это имеет смысл!