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

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

Ответ 1

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

Ответ 2

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

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

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

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

Ответ 3

Да.

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

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

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

Ответ 4

Вы должны посмотреть библиотеку FastFlow

Ответ 5

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

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

AH-ха!

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

Ответ 6

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

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

Ответ 7

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

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

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

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

Ответ 8

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

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

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

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