Уже много лет твой компьютер умеет выполнять код любимого ПО параллельно, на всех своих ядрах и процессорах. Да что там компьютер — скоро холодильники смогут обсчитывать гастрономические предпочтения хозяина в несколько потоков, недаром IoT движется по планете семимильными шагами. И казалось бы, уже весь софт давным-давно должен уметь максимально эффективно нагревать атмосферу вокруг тебя, нагружая транзисторы твоего ПК многопоточностью, но все не так замечательно, как хотелось бы.

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

Из этого следует простой вывод — если есть возможность избежать разделения данных между ядрами, то надо этой возможностью непременно воспользоваться. Но что делать, если такой возможности решительно нет?

 

Сферическая задача в вакууме

Допустим, нам нужно написать серверное приложение, которое принимает одно-единственное подключение по UDP-протоколу и как-то нехитро обрабатывает входящие датаграммы, например считает статистику по пришедшим данным. Основная проблема в том, что данные идут на очень больших скоростях, например 10 Гбит/c. Чтобы справиться с такой нагрузкой, нам надо проявить определенную сообразительность и не ударить в грязь лицом.

Какая хакерская задача немыслима без эффективной многопоточности кода?

Загрузка ... Загрузка ...

Хорошая новость состоит в том, что устройство, на котором наше ПО будет запущенно, принадлежит полностью нам, можно грузить процессор на 100%, и никто нас за это не поругает, главное — обсчитать как можно больше пакетов и максимально не допустить потерь. Размер данных в UDP-датаграмме не может превышать 512 байт (к примеру).

 

Архитектура приложения

Из описания задачи сразу становится понятно, что без всех ядер ПК нам тут не обойтись. Первое, что придет в голову более-менее опытному разработчику, — это выделить один поток на прием входящих датаграмм и создать пул потоков для их обработки. Размер пула обычно делают равным количеству доступных ядер у машины.

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

Для потоков из пула, которые обрабатывают UDP-пакеты, мы реализуем очередь из этих самых пакетов. Как только главный поток получает датаграмму, он сразу кладет ее в очередь и пытается прочитать следующую порцию данных из сокета. Потоки пула при этом придерживаются той же модели работы, что и main thread. В частности, они будут крутить цикл вычитки пакетов из очереди, не засыпая на ожидании, если очередь пуста.

Теперь надо немного напрячь мозг и подумать, что мы забыли учесть. Поскольку очередь — разделяемая структура данных, то работа с ней связана с дополнительными расходами времени на синхронизацию. Как мы выяснили немного выше, нам надо максимально избегать разделяемых данных, поскольку это чревато потенциальными ошибками и возникновением «узких мест». К сожалению, полностью отказаться от очереди у нас не выйдет, но вот снизить затраты на синхронизацию вполне можно.

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

Конечно, мы могли бы использовать readers-write lock, чтобы обеспечить одновременно чтение из очереди потокам пула, когда не ведется запись. Но проблема в том, что датаграммы будут сыпаться с большой частотой и основная конкуренция за разделяемый ресурс у обработчиков данных окажется не друг с другом, а с главным потоком.

Сколько логических ядер максимально бывает у современного процессора?

Загрузка ... Загрузка ...
 

Очередь

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

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

Таким образом, вырисовывается примерный интерфейс класса, который будет имплементировать нашу структуру данных. Назовем его RingQueue. Класс будет иметь как минимум два метода: push и pop. Причем метод push() будет возвращать булев результат, где true обозначает успешное добавление в очередь, а false — очередь полна.

Теперь, когда мы определились с общими принципами, по которым будет работать наш класс, давай подумаем о реализации.

Продолжение доступно только подписчикам

Вариант 1. Оформи подписку на «Хакер», чтобы читать все материалы на сайте

Подписка позволит тебе в течение указанного срока читать ВСЕ платные материалы сайта. Мы принимаем оплату банковскими картами, электронными деньгами и переводами со счетов мобильных операторов. Подробнее о подписке

Вариант 2. Купи один материал

Заинтересовала информация, но нет возможности оплатить подписку? Тогда этот вариант для тебя! Обрати внимание: этот способ покупки доступен только для материалов, опубликованных более двух месяцев назад.


5 комментариев

  1. baragoz

    24.04.2018 at 13:14

    Это же тот парень, который антивирус Касперского поломал)

  2. artstorm

    25.04.2018 at 22:24

    Если уж речь идёт о производительности, то неплохо бы заметить, что простым чтением из сокета 10 Гб/с не захватить. Нужно использовать PF_RING.

  3. Андрей Васильков

    Андрей Васильков

    26.04.2018 at 10:34

    Подсказка сомневающимся в ответе на второй вопрос: https://ark.intel.com/products/120496/Intel-Xeon-Platinum-8180-Processor-38_5M-Cache-2_50-GHz

  4. devbutch

    26.04.2018 at 22:55

    Спасибо за статью!
    Несколько вопросов:
    0. Не совсем понятная прозрачность для пользователя size+1. Что меняет вариант без size+1? Код становится чище и понятнее.
    explicit RingQueue(size_t size)
    : m_container(size)
    {
    assert(size);
    }

    size_t incrementPosition(size_t pos) { return pos == m_container.size() ? 0 : pos + 1; }
    1. «В нашей реализации единственное требование к T — это поддержка move-семантики.» (c)
    Но в пуше мы используем: auto& item = m_container.at(m_pushPos); auto tmp = T(args …); item = std::move(tmp);
    Можете прокомментировать эти строчки?

    • deeonis

      27.04.2018 at 17:34

      По поводу size+1.

      Реализация класса RingQueue подразумевает что один элемент в очереди всегда будет пустым. Нужно это для того чтобы корректно понимать когда очередь пуста и когда заполнена на 100%. Т.о. образом если смотреть на класс с точки зрения пользователя этого класса, то зарезервировав в очереди 100, он должен получить capacity в 100 элементов и если не делать size+1, то интерфейс класса становится непрозрачным для пользователя.

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

      По поводу move семантики. Если я правильно понял вопрос, то ответ следующий.

      Она тут используется. Строка item = std::move(tmp) обращается к оператору присваивания поддерживающего move семантику. Создание объекта tmp можно было выкинуть и записать две последние строки следующим образом:
      item = T(args …);
      Но сути это не поменяло бы, просто вместо move версии operator= вызвалась бы move версия конструктора.

Оставить мнение

Check Also

Разбудить мертвеца. Изучаем возможности и безопасность режимов восстановления смартфонов

Восстанавливал ли ты когда-нибудь телефон из состояния «кирпича»? В зависимости от платфор…