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

Question

(Я думаю) Консенсус номер Для мутекс 2.

Каков консенсус для семафоров (например, в pthread_sem_*)?

Что такое консенсусное число для переменных условий (например, в pthread_cond_*)?

Answer 1

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

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

Answer 2

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

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

Answer 3

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

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

Атомный тест и сет имеет консенсусное число 2, но не блокирует.

---

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

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

Answer 4

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

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

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

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

QED