Любая реализация очереди без блокировки с одним производителем для одного производителя в C?

Question

Я пишу программу с потоком потребителя и потоком производителя, теперь кажется, что синхронизация очереди - это большие накладные расходы в программе, и я искал некоторые реализации очереди без блокировки, но нашел только версию Lamport и улучшенную версию на PPoPP '08:

enqueue_nonblock(data) {
    if (NULL != buffer[head]) {
        return EWOULDBLOCK;
    }
    buffer[head] = data;
    head = NEXT(head);
    return 0;
}

dequeue_nonblock(data) {
    data = buffer[tail];
    if (NULL == data) {
        return EWOULDBLOCK;
    }
    buffer[tail] = NULL;
    tail = NEXT(tail);
    return 0;
}

Обе версии требуют предварительно выделенного массива для данных, мой вопрос в том, есть ли какая-либо реализация очереди без блокировки для одного производителя с одним производителем, которая использует malloc () для динамического распределения пространства?

И еще один связанный с этим вопрос: как измерить точные издержки при синхронизации очереди? Например, сколько времени занимает pthread_mutex_lock () и т. Д.

Answer 1

Если вы беспокоитесь о производительности, добавление malloc () в микс не поможет. И если вы не беспокоитесь о производительности, почему бы просто не контролировать доступ к очереди через мьютекс. Вы действительно измерили производительность такой реализации? Мне кажется, что вы идете по семейному пути преждевременной оптимизации.

Answer 2

Алгоритм, который вы показываете, работает, потому что, хотя два потока совместно используют ресурс (то есть очередь), они разделяют его очень особым образом. Поскольку только один поток когда-либо изменяет главный индекс очереди (производитель), и только один поток каждый изменяет хвостовой индекс (потребитель, конечно), вы не можете получить противоречивое состояние общего объекта. Также важно, чтобы производитель поместил фактические данные в перед обновлением индекса головки, и чтобы потребитель считал данные, которые ему нужны до обновления хвостового индекса.

Работает так же хорошо, как б / с, массив довольно статичен; оба потока могут рассчитывать на хранилище для находящихся там элементов. Вы, вероятно, не можете полностью заменить массив, но то, что вы можете сделать, это изменить назначение этого массива.

Т.е. вместо того, чтобы хранить данные в массиве, используйте его для хранения указателей на данные. Затем вы можете выполнять malloc () и free () для элементов данных, передавая ссылки (указатели) на них между вашими потоками через массив.

Кроме того, posix поддерживает чтение наносекундных часов, хотя фактическая точность зависит от системы. Вы можете прочитать эти часы с высоким разрешением до и после и просто вычесть.

Answer 3

Вам стоит взглянуть на библиотеку FastFlow

Answer 4

Да.

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

Я реализовал одну из них, написанную Майклом и Скоттом, из их статьи 1996 года.

Я (после еще одного тестирования) выпустлю небольшую библиотеку структур данных без блокировки (в C), которая будет включать эту очередь.

Answer 5

Добавление malloc убило бы любой прирост производительности, который вы можете получить, и такая же эффективная структура на основе блокировки. Это так, потому что malloc требует какой-то блокировки CAS для кучи, и, следовательно, некоторые формы malloc имеют свою собственную блокировку, поэтому вы можете блокировать ее в диспетчере памяти.

Чтобы использовать malloc, вам нужно предварительно выделить все узлы и управлять ими с помощью другой очереди ...

Обратите внимание, что вы можете создать некоторую форму расширяемого массива, который необходимо будет заблокировать, если он был расширен.

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

Answer 6

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

Чтобы избежать слишком большой синхронизации, вы можете попробовать записать / прочитать несколько значений в / из очереди при каждом доступе.

Если вы все еще хотите использовать алгоритмы без блокировок, то вы должны использовать предварительно распределенные данные или использовать распределитель без блокировок. Есть статья о распределителе без блокировки «Масштабируемое динамическое выделение памяти без блокировки» и реализация Streamflow

Перед тем, как начать работу с материалами без блокировки, посмотрите: Круговой буфер без блокировки

Answer 7

Я работал с довольно простой реализацией очереди, отвечающей большинству ваших критериев. Он использовал статический пул максимального размера байтов, а затем мы внедрили в него сообщения. Был указатель заголовка, который должен переместить один процесс, и хвостовой указатель, который переместил бы другой процесс.

Блокировки все еще требовались, но мы использовали 2-процессорный алгоритм Петерсона , который является довольно легковесным, поскольку он не включает системные вызовы. Блокировка требуется только для очень маленькой, хорошо ограниченной области: максимум несколько циклов ЦП, поэтому вы никогда не будете блокировать долго.

Answer 8

Я помню, что видел один, который выглядел интересным несколько лет назад, хотя я не могу найти его сейчас. :( Предложенная реализация без блокировки требует использования примитива CAS , хотя даже реализация блокировки (если вы не хотите использовать примитив CAS) имела довольно хорошие характеристики производительности --- блокировки не позволили нескольким читателям или нескольким производителям одновременно встать в очередь, производитель по-прежнему никогда не состязался с потребителем.

Я помню, что фундаментальная концепция очереди заключалась в создании связанного списка, в котором всегда был один дополнительный «пустой» узел. Этот дополнительный узел означал, что указатели заголовка и хвоста в списке будут когда-либо ссылаться на одни и те же данные только тогда, когда список пуст. Хотел бы я найти статью, я не оправдываю алгоритм своим объяснением ...

AH-ха!

Я нашел кого-то, кто расшифровал алгоритм без остатка статьи . Это может быть полезной отправной точкой.

Answer 9

В этой реализации используются новые и удаляемые C ++, которые можно легко перенести в стандартную библиотеку C с помощью malloc и free:

http://www.drdobbs.com/parallel/writing-lock-free-code-a-corrected-queue/210604448?pgno=2