Какое число консенсуса для семафоров?

Question

(я так думаю) консенсусное число для мьютекса равно 2.

Каково число консенсуса для семафоров (как в pthread_sem _ *)?

Каково число консенсуса для условных переменных (как в pthread_cond _ *)?

Answer 1

Консенсус-число для мьютекса будет равно 1. Тривиально ясно, что мьютекс будет без ожидания для одного потока. Из его определения также ясно, что мьютекс больше не ждет ожидания для двух потоков. Следовательно, число консенсуса> = 1 и <2, поэтому оно должно быть 1. </p>

Аналогично, другие механизмы синхронизации, которые работают, останавливая один поток в пользу другого, также имеют консенсус № 1 и поэтому не могут использоваться для создания объекта без ожидания, совместно используемого двумя потоками.

Answer 2

Ответ зависит от поддерживаемых операций с мьютексом или семафором. Если поддерживаются только блокирующие блокировки, консенсусное число равно 1. Если поток может попытаться заблокировать мьютекс без ожидания, консенсусное число равно 2. Это связано с тем, что если есть два потока, оба могут попытаться заблокировать мьютекс, оба могут согласитесь, какой из них получил, так что есть консенсус. Если мьютекс может дополнительно определить для любого числа потоков, какой поток заблокировал его, то число консенсуса бесконечно. Я думаю, что ситуация с семафорами похожа. Мьютексы эквивалентны семафорам со счетчиком 1. Я не думаю, что консенсус может быть достигнут только с помощью больших счетчиков, он все равно сводится к тем же операциям. Pthreads поддерживает неблокирующие блокировки, но не запросы, поэтому ответ будет 2.

Сигнализация условной переменной ничего не делает, если какие-либо потоки ее не ожидают, поэтому они имеют общее число 1.

Answer 3

Бесконечно, конечно? Но они не ждут бесплатно.

Возможно, я неправильно понимаю. Вы говорите, что мьютекс имеет согласованное число 2 - каков ваш источник для этого? Он разработан для того, чтобы разрешить любому количеству потоков совместно использовать ресурс с компромиссом блокировки.

Atomic test-and-set имеет согласованное число 2, но не блокирует.

---

Для пояснения: семафоры, мьютексы и т. Д. Являются примитивами, которые можно просто обернуть вокруг общего ресурса, чтобы сделать его безопасным (если вы делаете это правильно). Они могут блокировать, но они гарантируют, что ваши данные в безопасности.

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

Answer 4

Только из этой статьи вы можете сделать вывод, что семафор должен иметь согласованное число, меньшее или равное 2. Вот почему:

На третьей странице статьи говорится: «Операция извлечения и добавления довольно гибкая: ее можно использовать для семафоров ...». Поскольку мы знаем, что fetch & add имеет согласованное число, равное 2, теорема 1 этой статьи может затем использоваться, чтобы показать, что семафор должен иметь согласованное число, меньшее или равное 2. Доказательство выглядит следующим образом:

Доказательство

Предположим, что реализация fetch & add существует без ожидания. Далее предположим, что у семафора консенсус-число больше 2. Мы знаем, что fetch & add имеет консенсус-число 2. Из теоремы 1 мы можем заключить, что в системе, состоящей из более чем 2 процессов, не существует реализации семафора без ожидания с помощью fetch & add. , Это противоречит предположению о том, что реализация fetch & add существует. Следовательно, семафор должен иметь согласованное число, меньшее или равное 2.

QED