Сегодня программисты 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].