Бинарные семафоры на futex через parking_lot_core

Привет, Харб!

Сегодня рассмотрим, как реализовать собственный бинарный семафор на основе futex и библиотеки parking_lot_core.

Зачем семафор, если есть Mutex?

Ошибка, которую часто совершают начинающие разработчики: отождествляют семафор с мьютексом. Это принципиально разные сущности. Мьютекс ассоциирован с конкретным владельцем: поток, захвативший замок, обязан его освободить. У бинарного семафора понятие владельца отсутствует: это просто счётчик в состоянии 0 или 1, который обнуляется первым, кто успеет. Его дефолтный сценарий — дозирование доступа к внешним или дорогим ресурсам, буферам фиксированного размера, синхронизация продюсер/консюмер при buffer size = 1.

Так же сам по себе семафор не требует связки Mutex + Condvar, что экономит как на коде, так и на рантайм-переключениях.

Futex — мостик между user space и ядром

Ключ к высокой эффективности семафоров в Linux — системный вызов futex. В простейшем случае он вообще не заходит в ядро: атомарные операции и спиннинг происходят целиком в user space. Лишь при контеншенах задействуется переход в kernel mode.

Под семафор нам достаточно двух операций:

• FUTEX_WAIT — поток засыпает, если условие не выполнено.

• FUTEX_WAKE — пробуждение ровно одного ожидающего.

Эти две примитивные операции — эквивалент POSIX-терминов down и up.

Прямой вызов sys_futex в Rust возможен, но крайне неудобен: потребуется работать через libc::syscall, следить за таймаутами, ручками кодировать параметры и быть готовым к undefined behavior на каждом углу. И тут включается наш parking_lot_core.

Parking_lot_core

parking_lot_core — низкоуровневая библиотека, извлекающая логику парковки из более высокоуровневых примитивов parking_lot. Автор библиотеки вдохновился архитектурой WebKit, где управление потоками организовано через абстрактные очереди спящих по адресу.

Основные идеи:

• каждое «состояние» — это ключ в очереди потоков;

• park, unpark_one, unpark_all — API, которое инкапсулирует системные вызовы и MCS-замки.

Так можно строить собственные синхронизационные структуры без необходимости напрямую взаимодействовать с ядром.

Реализация бинарного семафора

Память

Бинарный семафор — это всего один AtomicU32.

use core::sync::atomic::{AtomicU32, Ordering}; use parking_lot_core::{park, unpark_one, SpinWait, DEFAULT_PARK_TOKEN, DEFAULT_UNPARK_TOKEN};  const AVAILABLE: u32 = 1; const TAKEN: u32 = 0;  pub struct BinarySemaphore {     state: AtomicU32, }

Захват

Захват жетона идёт по принципу «быстрый путь / медленный путь»:

pub fn acquire(&self) {     let mut spin = SpinWait::new();     loop {         if self.state             .compare_exchange(AVAILABLE, TAKEN, Ordering::Acquire, Ordering::Relaxed)             .is_ok()         {             return;         }          if spin.spin() {             continue;         }          unsafe {             park(                 &self.state as *const _ as usize,                 || self.state.load(Ordering::Relaxed) == TAKEN,                 || {},                 |_, _| {},                 DEFAULT_PARK_TOKEN,                 None,             );         }         spin.reset();     } }

Сначала идёт спинлок, чтобы не загружать ядро понапрасну. Если не удаётся — поток паркуется.

Освобождение

pub fn release(&self) {     if self.state.swap(AVAILABLE, Ordering::Release) == TAKEN {         unsafe {             unpark_one(                 &self.state as *const _ as usize,                 |_| DEFAULT_UNPARK_TOKEN,             );         }     } }

unpark_one будит ровно одного спящего потока.

RAII guard

Чтобы избежать ошибок управления ресурсом, можно обернуть захват в RAII:

pub struct SemaphoreGuard<'a>(&'a BinarySemaphore);  impl<'a> Drop for SemaphoreGuard<'a> {     fn drop(&mut self) {         self.0.release();     } }  impl BinarySemaphore {     pub fn lock(&self) -> SemaphoreGuard<'_> {         self.acquire();         SemaphoreGuard(self)     } }

Нюансы

Память и порядок операций.
Acquire на compare_exchange гарантирует, что изменения до release видны захватившему. Release на swap экспонирует все данные до отдачи жетона.

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

Приоритеты.
futex не учитывает приоритеты. Для realtime-сценариев лучше использовать FUTEX_PI или RT-mutex.

Спуровые пробуждения.
futex может разбудить поток без WAKE. Именно поэтому после park всегда пересчитывается условие.

Переносимость.
Для Windows и macOS есть аналог — крейт atomic-wait. Но он не даёт коллбэков под замком, что затрудняет составные конструкции.

Заключение

Бинарный семафор на базе futex и parking_lot_core — компактный и эффективный примитив: 4 байта памяти, ни одной динамической аллокации и максимум один системный вызов в случае контеншена. Лёгок в реализации и понятен.

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

Если вам интересна разработка на Rust, приглашаем на серию открытых уроков курса Rust Developer. Professional:

«Техническое собеседование на Middle Rust разработчика» — 24 июля в 20:00 
Разберём типовые вопросы, подходы к решению задач и критерии оценки.

«Rust в деле: пишем многопользовательский чат с сервером, клиентом и CLI» — 14 августа в 20:00 
Покажем, как собрать рабочий прототип с нуля.

«Макросы в Rust: от macro_rules! до процедурных макросов» — 19 августа в 20:00 
Поговорим о макросах, механизмах их работы и применении в реальных задачах.

Кроме того, можно пройти тестирование по курсу Rust Developer. Professional и оценить, насколько хорошо вы ориентируетесь в основных темах.