Сегодня программисты Velan выпускают две наши структуры данных без блокировок; свободная от блокировки очередь и свободный от блокировки целочисленный пул. Мы используем оба как основную часть нашей технологии Viper. Обе структуры данных написаны на C99 и являются довольно автономными.

Очередь без блокировки: vqueue

Наша незаблокированная очередь — это реализация неблокирующей очереди из статьи Майкла и Скотта «Простые, быстрые и практичные неблокирующие и блокирующие параллельные алгоритмы очереди». Несмотря на то, что этой прекрасной статье уже более 20 лет, мы не видели, чтобы она была четко реализована на выбранном нами языке без вызовов malloc() в операции push.

Очередь поддерживает три основные операции:

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

Очередь не блокируется и является потокобезопасной. При нажатии выполняется как минимум 3 атомарных 64-битных операции сравнения и замены (CAS) и 1 атомарное 32-битное приращение. Выталкивание из непустой очереди выполняет как минимум 2 атомарные 64-битные операции CAS и 1 атомарное 32-битное декрементирование.

Мы заранее выделяем место под вместимость очереди. На каждый элемент, который может содержать очередь, приходится 8 байт служебных данных.

Целочисленный пул без блокировки: vintpool

После написания распределителя узлов очереди для vqueue мы решили немного обобщить код, и так родился vintpool. Один из распространенных шаблонов в Viper — это управление блоком предварительно выделенного хранилища потокобезопасным способом.

thing_t things[k_max_things];
    int alloc_thing() { /* Get an index to a free thing. */ }
    void free_thing(int thing_index) { /* Marked an indexed thing as free. */ }

Это миссия vintpool — управлять пулами индексированных ресурсов. Пул поддерживает две операции:

  • Выделите индекс.
  • Освободить индекс.

Обе операции являются безблокировочными и потокобезопасными. Каждая операция влечет за собой накладные расходы как минимум на 1 атомарный 64-битный CAS. Хранилище для пула предварительно выделяется по цене 8 байт на индекс.

Где взять код

Код для vqueue и vintpool уже доступен на GitHub. Если вы используете этот код, сообщите нам об этом. Мы хотели бы услышать от вас.

Вы можете связаться с технической командой Velan по электронной почте [email protected].