Каково общее число семафоров?

Ответ 1

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

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

Ответ 2

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

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

Ответ 3

Бесконечно, неужели? Но они не ждут свободного времени.

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

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

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

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

Ответ 4

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

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

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

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

КЭД