Блог

#c #linux #blocking #lock-free

#c #linux #блокировка #без блокировок

Вопрос:

Комментарии:

1. Привет, не могли бы вы поделиться со мной rps (количество запросов в секунду), которого вы достигли, используя этот подход? Я выполнял аналогичную работу (реализация простого HTTP-сервера), поэтому мне интересно узнать об этом. Я не знаю, как связаться, кроме как прокомментировать здесь. Извините, если я вас побеспокоил.

2. Производительность @Ayub была в порядке. RPS не является хорошей единицей измерения производительности из-за различных настроек оборудования и т.д. Я переработал приложение, чтобы позволить рабочим потокам работать в полной изоляции, и прирост производительности составил ~ 10 раз. Совместное использование меньшего количества данных действительно было ключевым.

3. Можете ли вы объяснить, почему вы выбрали подход с одной очередью на работника? Для меня звучит довольно неоптимально. Время выполнения заданий в очередях трудно предвидеть.

Ответ №1:

Комментарии:

1. Полезное разъяснение! На данный момент я поддержал оба ответа, связанные с Futex. Спасибо.

2. 1 за futex . Его производительность не так хороша, как без блокировок, но она достаточно хороша и является идеальным выбором, когда блокировка мьютекса слишком велика. API мьютекса pthread используется futex за кулисами.

3. Мьютексы в Linux реализованы с коротким cmpxchg вращением для случая низкой конкуренции и возвратом к futex вызову. Я действительно не понимаю, почему вы называете это неблокирующим, когда оно реализует блокировку (быстрый мьютекс пользовательского пространства — происхождение названия).

4. Я называю это неблокирующим из-за случая с низким уровнем конкуренции, который «обычно» возникает, если вы не находитесь под высокой нагрузкой…

Ответ №2:

Комментарии:

1. Это выглядит очень интересно. Я вскоре рассмотрю это и вернусь со своим вердиктом. Спасибо.

2. futex Вызов является реализацией блокировки . API mutex просто включается cmpxchg немного, а затем возвращается к futex (быстрый мьютекс пользовательского пространства).

Ответ №3:

 /* Interlocked SList queue using keyed event signaling */

struct queue {
    SLIST_HEADER slist;
    // Note: Multiple queues can (and should) share a keyed event handle
    HANDLE keyed_event;
    // Initial value: 0
    // Prior to blocking, the queue_pop function increments this to 1, then
    // rechecks the queue. If it finds an item, it attempts to compxchg back to
    // 0; if this fails, then it's racing with a push, and has to block
    LONG block_flag;
};

void init_queue(queue *qPtr) {
    NtCreateKeyedEvent(amp;qPtr->keyed_event, -1, NULL, 0);
    InitializeSListHead(amp;qPtr->slist);
    qPtr->blocking = 0;
}

void queue_push(queue *qPtr, SLIST_ENTRY *entry) {
    InterlockedPushEntrySList(amp;qPtr->slist, entry);

    // Transition block flag 1 -> 0. If this succeeds (block flag was 1), we
    // have committed to a keyed-event handshake
    LONG oldv = InterlockedCompareExchange(amp;qPtr->block_flag, 0, 1);
    if (oldv) {
        NtReleaseKeyedEvent(qPtr->keyed_event, (PVOID)qPtr, FALSE, NULL);
    }
}

SLIST_ENTRY *queue_pop(queue *qPtr) {
    SLIST_ENTRY *entry = InterlockedPopEntrySList(amp;qPtr->slist);
    if (entry)
        return entry; // fast path

    // Transition block flag 0 -> 1. We must recheck the queue after this point
    // in case we race with queue_push; however since ReleaseKeyedEvent
    // blocks until it is matched up with a wait, we must perform the wait if
    // queue_push sees us
    LONG oldv = InterlockedCompareExchange(amp;qPtr->block_flag, 1, 0);

    assert(oldv == 0);

    entry = InterlockedPopEntrySList(amp;qPtr->slist);
    if (entry) {
        // Try to abort
        oldv = InterlockedCompareExchange(amp;qPtr->block_flag, 0, 1);
        if (oldv == 1)
            return entry; // nobody saw us, we can just exit with the value
    }

    // Either we don't have an entry, or we are forced to wait because
    // queue_push saw our block flag. So do the wait
    NtWaitForKeyedEvent(qPtr->keyed_event, (PVOID)qPtr, FALSE, NULL);
    // block_flag has been reset by queue_push

    if (!entry)
        entry = InterlockedPopEntrySList(amp;qPtr->slist);
    assert(entry);

    return entry;
}
  

Комментарии:

1. Да, но ответы на futex уже были получены, и я подумал, что это может быть полезно для кого-то еще, кто будет искать по этому вопросу позже 🙂

2. Для полноты картины это интересно — я иногда разрабатываю для Windows. 🙂

3. 1, Также события с ключом отлично работают и на версии до Vista (изначально они были реализованы как единая глобальная блокировка для всех в случае неуправляемой ситуации взаимоблокировки с критическими разделами до 2k). Единственное различие между 2k / XP и Vista / 7 / 8 заключается в деталях реализации (связанный список против хэша), что делает Vista и более поздние версии KEs намного более эффективными, если вы просматриваете множество ячеек памяти с помощью одного дескриптора (никакой практической разницы для 99% всех приложений).

Ответ №4:

Комментарии:

1. Любые вызовы, выполняемые с использованием функций pthread, вызовут вызов в ядро, что будет значительно медленнее, чем атомарные операции. Прелесть futex в том, что вы используете комбинацию atomics и очереди ожидания на уровне ядра, но если нет конфликта блокировок, то вы никогда не касаетесь очереди ожидания на уровне ядра. С другой стороны, использование переменных условий автоматически помещает поток в очередь ожидания, поэтому с переменными условий вы проходите через ядро, несмотря ни на что, что будет намного медленнее, если 90% времени атомарная операция будет в порядке.

2. @Jason: мьютексы pthread в Linux не попадают в ядро в случае, когда не оспаривается; также не подается сигнал cvar без официантов. Конечно, ожидание cvar должно войти в ядро, но так же должна поступать и любая операция блокировки

3. @Jason, Futex — это базовый примитив, используемый для создания мьютексов NPTL pthread. Немного сложно безопасно использовать futex () самостоятельно, поэтому библиотека pthread оборачивает некоторые из наиболее распространенных протоколов futex и называет их мьютексами и условными переменными. Таким образом, он также более переносим — futex () является системным вызовом только для Linux.

4. @bdolan: Ценю разъяснение. Означает ли это, что фьютексы и мьютексы pthread имеют одинаковую скорость в Linux, и нет никакой пользы в использовании фьютексов, поскольку мьютексы являются фьютексами? Или все еще существует снижение производительности для мьютексов, и если да, то от чего?

5. Мьютекс реализуется с коротким вращением для обработки случая с низким уровнем конкуренции, а затем системного вызова через futex . Не имеет смысла использовать futex напрямую, если вы не знаете, что делаете.

Ответ №5:

Комментарии:

1. 1) Пожалуйста, предоставьте ссылку на ваше утверждение о том, что механизм, основанный на сигналах, будет «намного быстрее», чем переменная условия. В случае, когда поток должен проснуться, в обоих случаях аспекты планирования и кэширования играют огромную роль. 2) Пожалуйста, предоставьте схему того, как обрабатывать условия гонки и случай, когда поток не переходит в спящий режим, а скорее выбирает запись из непустой очереди. На практике этот быстрый путь является ключевым фактором масштабируемости / производительности под нагрузкой. И это становится немного сложнее, если у вас смешанная концепция.

Ответ №6:

 WAIT_TIME = 100; // Set this to whatever you're happy with
while(loop_condition) {
   thing = get_from_queue()
   if(thing == null) {
       sleep(WAIT_TIME);
   } else {
       handle(thing);
   }
}
  

Комментарии:

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

2. Это не решает проблему так элегантно, как другие ответы.

3. @rmcclellan «Не самое лучшее» обычно не является веской причиной для снижения голосов, но делайте, что хотите. Я понимаю, что это решение не самое лучшее для операционной системы (как они прокомментировали выше), но ответы Stack Overflow также появляются в результатах поиска, и это хорошее решение в некоторых случаях (массовый трафик, когда вам не нужны блокировки при обработке результатов, но вы не хотите тратить время процессора, когда ничего не происходит).

4. Было бы неплохо упомянуть в ответе места, где это решение является хорошим.