Буфер без круговой блокировки

Question

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

Теперь два вопроса:

1. Является ли круговой буфер без блокировки ответом?

2. Если да, то, прежде чем я сделаю свою собственную, знаете ли вы какую-либо публичную реализацию, которая будет соответствовать моим потребностям?

Любые указатели в реализации циклического буфера без блокировки всегда приветствуются.

Кстати, делать это на C ++ в Linux.

Дополнительная информация:

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

Идея дизайна, к которой я склоняюсь, - это циклический буфер без полузакрытия, в котором поток производителя помещает данные в буфер настолько быстро, насколько это возможно, давайте назовем заголовок буфера A без блокировки, если буфер не full, когда A встречает конец буфера Z. Каждый из потоков-потребителей будет содержать два указателя на кольцевой буфер, P и P _n , где P - локальная головка буфера потока, а P _n - это n-ый элемент после P. Каждый потребительский поток будет продвигать свои P и P _n , как только он завершит обработку текущего P, а указатель конца буфера Z продвигается с самым медленным P _n . , Когда P догоняет A, что означает, что больше нет новых обновлений для обработки, потребитель вращается и действительно занят, ожидая, пока A снова продвинется. Если потребительский поток вращается слишком долго, его можно перевести в спящий режим и ждать переменную условия, но я согласен с тем, что потребитель принимает цикл ЦП в ожидании обновления, потому что это не увеличивает мою задержку (у меня будет больше ядер ЦП чем темы). Представьте, что у вас есть круговая дорожка, и производитель работает перед группой потребителей, ключ в том, чтобы настроить систему так, чтобы производитель, как правило, работал на несколько шагов впереди потребителей, и большинство из этих операций могут быть сделано с использованием техники без блокировки. Я понимаю, что правильно понять детали реализации нелегко ... хорошо, очень сложно, поэтому я хочу учиться на чужих ошибках, прежде чем делать несколько своих.

Answer 1

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

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

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

Я полагаю, однако, есть решение для вашего требования.

Вы должны связать очередь без блокировок со списком свободных без блокировок.

Свободный список даст вам предварительное распределение и, таким образом, устранит (финансово дорогое) требование для распределителя без блокировки; когда свободный список пуст, вы копируете поведение кольцевого буфера, мгновенно удаляя элемент из очереди и используя его вместо этого.

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

Майкл и Скотт разработали действительно хорошую очередь без блокировки еще в 1996 году. Ссылка ниже даст вам достаточно подробностей, чтобы отследить PDF их статьи; Майкл и Скотт, FIFO

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

Answer 2

Условием искусства для того, что вы хотите, является очередь без блокировки . Есть отличный набор заметок со ссылками на код и документы Росса Бенчина. Парень, работе которого я доверяю больше всего, Морис Херлихи (для американцев он произносит свое имя как «Моррис»).

Answer 3

Требование, чтобы производители или потребители блокировали, если буфер пуст или заполнен, предполагает, что вы должны использовать нормальную структуру данных блокировки с семафорами или переменными условия, чтобы производители и потребители блокировали, пока данные не станут доступны. Код без блокировки, как правило, не блокируется в таких условиях - он вращает или отменяет операции, которые невозможно выполнить вместо блокировки с использованием ОС. (Если вы можете позволить себе ждать, пока другой поток произведет или потребит данные, то почему ожидание блокировки другого потока для завершения обновления структуры данных хуже?)

В (x86 / x64) Linux, внутрипоточная синхронизация с использованием мьютексов достаточно дешевая, если нет конфликтов. Сконцентрируйтесь на минимизации времени, которое производители и потребители должны держать на своих замках. Учитывая, что вы сказали, что вам нужны только последние N записанных точек данных, я думаю, что циклический буфер будет делать это достаточно хорошо. Тем не менее, я не совсем понимаю, как это согласуется с требованием блокирования и с идеей потребителей, которые фактически потребляют (удаляют) данные, которые они читают. (Вы хотите, чтобы потребители смотрели только на последние N точек данных, а не удаляли их? Хотите, чтобы производители не заботились о том, что потребители не успевают, и просто перезаписывают старые данные?)

Кроме того, как прокомментировал Zan Lynx, вы можете агрегировать / буферизовать ваши данные в большие куски, когда вы получаете их много. Вы можете буферизовать фиксированное количество точек или все данные, полученные в пределах определенного количество времени. Это означает, что будет меньше операций синхронизации. Тем не менее, это приводит к задержке, но если вы не используете Linux в реальном времени, вам все равно придется с этим справляться.

Answer 4

Реализация в библиотеке Boost заслуживает рассмотрения. Это простой в использовании и довольно высокая производительность. Я написал тест и запустил его на четырехъядерном ноутбуке i7 (8 потоков) и получаю ~ 4M операций постановки / снятия в секунду. Еще одна реализация, не упомянутая до сих пор, - это очередь MPMC на http://moodycamel.com/blog/2014/detailed-design-of-a-lock-free-queue.. Я провел несколько простых испытаний с этой реализацией на одном ноутбуке с 32 производителями и 32 потребителями. Как рекламируется, это быстрее, чем увеличить очередь без блокировки.

Поскольку большинство других ответов гласят, что программирование без блокировки сложно. Большинству реализаций будет сложно обнаружить критические случаи, которые требуют много тестирования и отладки для исправления. Они обычно исправляются с помощью осторожного размещения барьеров памяти в коде. Вы также найдете доказательства правильности, опубликованные во многих академических статьях. Я предпочитаю тестировать эти реализации с помощью инструмента грубой силы. Любой алгоритм без блокировки, который вы планируете использовать в производстве, должен быть проверен на корректность с помощью инструмента, подобного http://research.microsoft.com/en-us/um/people/lamport/tla/tla.html.

Answer 5

Об этом есть довольно хорошая серия статей о DDJ . В качестве признака того, насколько сложным может быть этот материал, это исправление в более ранней статье , в котором это неправильно. Убедитесь, что вы понимаете ошибки, прежде чем делать свои собственные) -;

Answer 6

Я не эксперт по аппаратным моделям памяти и не блокирую свободные структуры данных, и я стараюсь избегать их использования в своих проектах, и я использую традиционные заблокированные структуры данных.

Однако недавно я заметил это видео: Очередь SPSC без блокировки на основе кольцевого буфера

Это основано на высокопроизводительной библиотеке Java с открытым исходным кодом, называемой LMAX distruptor, используемой торговой системой: LMAX Distruptor

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

Ниже вы можете увидеть очень простую реализацию C ++ 11 для него:

// USING SEQUENTIAL MEMORY
#include<thread>
#include<atomic>
#include <cinttypes>
using namespace std;

#define RING_BUFFER_SIZE 1024  // power of 2 for efficient %
class lockless_ring_buffer_spsc
{
    public :

        lockless_ring_buffer_spsc()
        {
            write.store(0);
            read.store(0);
        }

        bool try_push(int64_t val)
        {
            const auto current_tail = write.load();
            const auto next_tail = increment(current_tail);
            if (next_tail != read.load())
            {
                buffer[current_tail] = val;
                write.store(next_tail);
                return true;
            }

            return false;  
        }

        void push(int64_t val)
        {
            while( ! try_push(val) );
            // TODO: exponential backoff / sleep
        }

        bool try_pop(int64_t* pval)
        {
            auto currentHead = read.load();

            if (currentHead == write.load())
            {
                return false;
            }

            *pval = buffer[currentHead];
            read.store(increment(currentHead));

            return true;
        }

        int64_t pop()
        {
            int64_t ret;
            while( ! try_pop(&ret) );
            // TODO: exponential backoff / sleep
            return ret;
        }

    private :
        std::atomic<int64_t> write;
        std::atomic<int64_t> read;
        static const int64_t size = RING_BUFFER_SIZE;
        int64_t buffer[RING_BUFFER_SIZE];

        int64_t increment(int n)
        {
            return (n + 1) % size;
        }
};

int main (int argc, char** argv)
{
    lockless_ring_buffer_spsc queue;

    std::thread write_thread( [&] () {
             for(int i = 0; i<1000000; i++)
             {
                    queue.push(i);
             }
         }  // End of lambda expression
                                                );
    std::thread read_thread( [&] () {
             for(int i = 0; i<1000000; i++)
             {
                    queue.pop();
             }
         }  // End of lambda expression
                                                );
    write_thread.join();
    read_thread.join();

     return 0;
}

Answer 7

Очередь Саттера неоптимальна, и он это знает. Искусство многоядерного программирования - отличный пример, но не доверяйте Java-парням в моделях памяти. Ссылки Росса не дадут вам однозначного ответа, потому что у них были свои библиотеки в таких задачах и т. Д.

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

Answer 8

Я бы согласился с этой статьей и рекомендовал бы не использовать структуры данных без блокировки. Относительно недавняя статья об очередях fifo без блокировки - this , поиск других работ того же автора (ов); есть также кандидатская диссертация Чалмерса относительно структур данных без блокировки (я потерял связь). Однако вы не сказали, насколько велики ваши элементы - структуры данных без блокировок эффективно работают только с элементами размером в слово, поэтому вам придется динамически выделять элементы, если они больше машинного слова (32 или 64 биты). Если вы динамически распределяете элементы, вы перемещаете узкое место в памяти (предположительно, поскольку вы не профилировали свою программу и в основном выполняете преждевременную оптимизацию), поэтому вам нужен распределитель памяти без блокировки, например, Streamflow , и интегрируйте его с вашим приложением.

Answer 9

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

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

Answer 10

Хотя это старый вопрос, никто не упомянул безблокировочный кольцевой буфер DPDK . Это кольцевой буфер с высокой пропускной способностью, который поддерживает несколько производителей и нескольких потребителей. Он также предоставляет режимы с одним потребителем и одним производителем, а кольцевой буфер не требует ожидания в режиме SPSC. Он написан на C и поддерживает несколько архитектур.

Кроме того, он поддерживает режимы «Bulk» и «Burst», в которых элементы могут быть поставлены в очередь / сняты с очереди. Конструкция позволяет нескольким потребителям или нескольким производителям одновременно писать в очередь, просто зарезервировав пространство путем перемещения атомного указателя.