Есть ли у libc counting_semaphore проблема взаимоблокировки?

ProgramBox

Есть ли у libc counting_semaphore проблема взаимоблокировки?

Post author:admin
Запись опубликована:19 июля, 2022
Post category:Вопросы по программированию

#c #semaphore #c 20 #libc #stdatomic

#c #семафор #c 20 #libc #stdatomic

Вопрос:

libc counting_semaphore::release :

     void release(ptrdiff_t __update = 1)
    {
        if(0 < __a.fetch_add(__update, memory_order_release))
            ;
        else if(__update > 1)
            __a.notify_all();
        else
            __a.notify_one();
    }

Уведомляет, только если внутренний счетчик был равен нулю перед приращением, уведомляет более одного официанта, только если приращение больше единицы.

libc counting_semaphore::acquire :

     void acquire()
    {
        auto const __test_fn = [=]() -> bool {
            auto __old = __a.load(memory_order_relaxed);
            return (__old != 0) amp;amp; __a.compare_exchange_strong(__old, __old - 1, memory_order_acquire, memory_order_relaxed);
        };
        __cxx_atomic_wait(amp;__a.__a_, __test_fn);
    }

Ожидает, что count будет ненулевым, и пытается преобразовать его в CAS с уменьшенным значением.

Теперь, пожалуйста, ознакомьтесь со следующим 3-потоковым случаем:

 counting_semaphore<10> s;

T1: { s.acquire(); /*signal to T3*/ }
T2: { s.acquire(); /*signal to T3*/ }
T3: { /*wait until both signals*/ s.release(1); s.release(1); }

Изначально:

 __a == 0

( desired параметр передается как 0, любая попытка acquire блокируется)

Временная шкала

 T1: enters wait
T2: enters wait
T3: fetch add 1 amp; returns 0, now __a == 1
T3: (0 < 0) is false, so notify_one happens
T1: unblocks from wait
T3: fetch add 1 amp; returns 1, now __a == 2
T3: (0 < 1) is true, so no notification
T1: loads 2
T1: cas 2 to 1 successfully
T1: returns from acquire
T2: still waits despite __a == 1

Похоже ли это на допустимую взаимоблокировку?

почему я спрашиваю здесь, а не сообщаю о проблеме?

Я сообщил о проблеме довольно давно, ответа пока нет. Я хочу понять, действительно ли существует взаимоблокировка или я что-то упускаю.

1. Я бы сказал, предполагая соответствующие барьеры памяти, действительность этой реализации полностью зависит от того, что стоит за notify_one и __cxx_atomic_wait . Вполне возможно, что реализация notify_one останавливает выполнение до завершения любых обратных вызовов, о __cxx_atomic_wait которых были уведомлены. Но поскольку эти внутренние вещи являются … внутренними, только разработчик может знать так или иначе.

2. @NicolBolas, реализация, которая будет блокировать, notify_one нежизнеспособна как std::atomic::notify_one реализация, а также, поскольку мы desired установили значение 0, а параметр шаблона равен 10, мы можем выполнить до 10 release вызовов раньше, чем acquire , и ни один из них не должен блокироваться.

3. » реализация, которая будет блокировать в notify_one » Что вы подразумеваете под «блоком»? Реализация просто выполнит функтор (ы) обратного вызова atomic_wait . Это конечная операция, так почему она должна считаться «блокирующей»? Это также деталь реализации, поэтому выбор дилера.

4. Ах, вижу вашу точку зрения, я неправильно ее понял. Я проверил __cxx_atomic_wait , и, похоже, он не останавливается notify_one , так как возможно, что он выполнит ожидание ОС __libcpp_atomic_wait , которое является обычным futex syscall(SYS_futex, __ptr, FUTEX_WAIT_PRIVATE, __val, amp;__timeout, 0, 0); . Так что, по-видимому, нет, notify_one не синхронизирован с функтором в __cxx_atomic_wait

Ответ №1:

Условие if (0 < ...) — это проблема, но это не единственная проблема.

Заявлено, что последствия release :

Атомарно выполнить счетчик = обновить. Затем разблокирует все потоки, которые ожидают, что счетчик будет больше нуля.

Обратите внимание на слова «любые потоки». Множественное число. Это означает, что, даже если конкретное update значение оказалось равным 1, все потоки, заблокированные по этому условию, должны быть уведомлены. Таким образом, вызов notify_one является неправильным, если только реализация notify_one always не разблокирует все ожидающие потоки. Что было бы … интересной реализацией этой функции.

Даже если вы измените notify_one на notify_all , это не решит проблему. Логика условия в основном предполагает, что уведомление потока должно происходить только в том случае, если все потоки (логически), уведомленные предыдущим release , завершили свои acquire вызовы. Стандарт не требует ничего подобного.

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

Метки: Есть ли у libc counting_semaphore проблема с взаимоблокировкой?