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

StackOverflow https://stackoverflow.com/questions/990627

Вопрос

Я пишу программу с потоком потребителя и потоком производителя, теперь кажется, что синхронизация очереди - это большие накладные расходы в программе, и я искал некоторые реализации очереди без блокировки, но нашел только версию Лампорта и улучшенную версию на 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() и т. д.

Это было полезно?

Решение

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

Другие советы

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

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

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

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

Да.

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

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

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

Вам следует посмотреть библиотеку FastFlow.

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

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

А-ха!

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

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

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

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

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

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

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

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

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

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

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

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

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

Лицензировано под: CC-BY-SA с атрибуция
Не связан с StackOverflow
scroll top