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

Сегодня рассмотрим, как реализовать собственный бинарный семафор на основе 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 и оценить, насколько хорошо вы ориентируетесь в основных темах.

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