Фьютекс (futex — сокращение от «Fast userspace mutex») — это механизм, предложенный разработчиками Linux из IBM в 2002 году и вошедший в ядро в конце 2003 года. Основной идеей было предоставить более эффективный способ синхронизации пользовательских потоков с минимальным количеством обращений к ядру ОС.
В этой статье мы сделаем обзор фьютексов, попытаемся понять принципы их работы, а также используем их в качестве кирпичиков для построения более высокоуровневых (и знакомых нам) объектов синхронизации.
Важный момент: фьютексы — это достаточно низкоуровневый инструмент, напрямую его использовать стоит лишь при разработке фундаментальных библиотек, вроде стандартной библиотеки C/C++. Очень маловероятно, что вам понадобится использовать фьютексы в обычном прикладном приложении.
Мотивация
До появления фьютексов для управления доступом к общим ресурсам из нескольких потоков приходилось каждый раз делать системные вызовы (с использованием, например, semop), что, как известно, достаточно ресурсозатратно, поскольку каждый вызов требует переключения контекста из пользовательского режима в режим ядра. С ростом количества ядер в современных процессорах и повышением количества потоков в прикладном ПО это стало существенной проблемой. Она тем более «обидна», учитывая, что все эти вызовы не несут никакой прикладной функции, не реализуют никакой бизнес-логики, а лишь гарантируют корректную работу остального кода.
Предложение добавить в ОС новую концепцию «фьютекс» базировалась на простом наблюдении: в большинстве случаев попытка захвата объекта синхронизации удаётся с первого раза. Программисты пишут ПО таким образом, чтобы от захвата блокировки до её освобождения проходило как можно меньше времени, а значит есть очень высокие шансы на то, что попытка захвата другим потоком не встретит препятствий. Когда поток доходит до такого «свободного» объекта синхронизации — мы можем захватить его без выполнения системного вызова, с использованием относительно дешевых атомарных операций. И есть очень большой шанс того, что атомарная операция сработает успешно.
В том редком случае, когда мы всё-таки пытаемся получить доступ к ресурсу, заблокированному другим потоком, атомарная операция вернёт ошибку. В этом случае у нас есть два варианта. Мы либо можем покрутиться в каком-нибудь спин-локе пользовательского режима, ожидая освобождения ресурса (что съест ресурсы CPU), либо попросить ядро перевести нас в спящий режим, ожидая освобождения ресурса. Именно здесь на сцену выходят фьютексы.
Простое использование фьютексов — ожидание и пробуждение
Системный вызов futex объединяет в себе достаточно разнообразную функциональность. Мы не будем рассматривать здесь сложные варианты (некоторые из них настолько вычурны, что даже не описаны в официальной документации), а сфокусируемся на операциях FUTEX_WAIT и FUTEX_WAKE. Описание в официальной документации послужит хорошей базой:
Системный вызов futex() предоставляет программам метод для ожидания пока определённое условие не станет истинным. Обычно, этот системный вызов используется блокирующая конструкция в контексте синхронизации общей памяти. При использовании фьютексов основные операции синхронизации выполняются в пространстве пользователя. Программы пользовательского пространства выполняются системный вызов futex() только когда нужно, чтобы программа вошла в режим ожидания на долгий срок, пока условие не станет истинным. Также futex() можно использовать для пробуждения процессов или нитей, ожидающих определённого условия.
Проще говоря, фьютекс — это конструкция в ядре, которая помогает пользовательскому коду синхронизировать потоки при наступлении каких-то событий. Одни процессы (или потоки) могут ожидать события в вызове FUTEX_WAIT, в то время как другие — вызывать эти события с помощью FUTEX_WAKE. Ожидание работает эффективно — ожидающие потоки приостанавливаются ядром и не используют процессорных ресурсов, пока не будут пробуждены при наступлении ожидаемого события.
Не поленитесь прочитать документацию полностью. Ну или хотя бы прочитайте разделы о FUTEX_WAIT и FUTEX_WAKE.
Давайте рассмотрим простой пример, демонстрирующий базовое использование фьютексов для координации работы двух процессов.
Дочерний процесс:
- Ждёт появления в общем слоте памяти значения 0xA
- Записывает в этот слот значение 0xB
Родительский процесс в это время:
- Записывает значение 0xA в общий слот памяти
- Ждёт появления в нём значения 0xB
Такое себе «рукопожатие» между двумя процессами. Вот код:
int main(int argc, char** argv) {
int shm_id = shmget(IPC_PRIVATE, 4096, IPC_CREAT | 0666);
if (shm_id < 0) {
perror("shmget");
exit(1);
}
int* shared_data = shmat(shm_id, NULL, 0);
*shared_data = 0;
int forkstatus = fork();
if (forkstatus < 0) {
perror("fork");
exit(1);
}
if (forkstatus == 0) {
// дочерний процесс
printf("child waiting for An");
wait_on_futex_value(shared_data, 0xA);
printf("child writing Bn");
// записываем 0xB в разделяемый слот памяти и ждём ответа родителя
*shared_data = 0xB;
wake_futex_blocking(shared_data);
} else {
// родительский процесс
printf("parent writing An");
// Записываем 0xA в разделяемый слот памяти и ждём ответа ребёнка
*shared_data = 0xA;
wake_futex_blocking(shared_data);
printf("parent waiting for Bn");
wait_on_futex_value(shared_data, 0xB);
// Wait for the child to terminate.
wait(NULL);
shmdt(shared_data);
}
return 0;
}Обратите внимание на POSIX-вызовы для выделения разделяемой между процессами памяти. Мы не могли использовать здесь обычное выделение памяти, поскольку даже одинаковые адреса указателей в разных процессах на самом деле указывали бы на разные блоки памяти (уникальные для каждого процесса).
Нужно отметить, что данный пример несколько отходит от канонов, ведь фьютекс изначально создавался чтобы ждать изменения некоторого значения «с чего-то конкретного на что-угодно», а не «с чего-угодно на что-то конкретное». Я привёл этот пример для того, чтобы продемонстрировать и такую возможность, а ниже мы рассмотрим и базовый вариант (на нём мы реализуем мьютекс).
А вот и код функции wait_on_futex_value:
void wait_on_futex_value(int* futex_addr, int val) {
while (1) {
int futex_rc = futex(futex_addr, FUTEX_WAIT, val, NULL, NULL, 0);
if (futex_rc == -1) {
if (errno != EAGAIN) {
perror("futex");
exit(1);
}
} else if (futex_rc == 0) {
if (*futex_addr == val) {
// здесь мы просыпаемся
return;
}
} else {
abort();
}
}
}Главной задачей данной функции (помимо, собственно, системного вызова futex) является цикл, в котором мы бегаем при ложном (не интересующем нас) пробуждении. Это может случиться при установке в разделяемый слот памяти нового, но не ожидаемого нами значения. Ну или в случае, когда другой процесс был пробуждён раньше нашего (этого не может случиться в нашем конкретном случае, но в более общем — возможно).
Семантика фьютекса — достаточно хитрая штука! Вызов FUTEX_WAIT немедленно вернётся, если значение по адресу фьютекса не равно переданному аргументу val. В нашем случае это может случиться, если дочерний процесс перешел в ожидание до того, как родительский записал в слот значение 0xA. Фьютекс в этом случае вернёт значение EAGAIN.
А вот код функции wake_futex_blocking:
void wake_futex_blocking(int* futex_addr) {
while (1) {
int futex_rc = futex(futex_addr, FUTEX_WAKE, 1, NULL, NULL, 0);
if (futex_rc == -1) {
perror("futex wake");
exit(1);
} else if (futex_rc > 0) {
return;
}
}
}Это блокирующая обёртка над FUTEX_WAKE, которая быстро отработает и вернёт значение, независимо от того, как много слушателей его ожидают. В нашем примере это используется как часть «рукопожатия», но возможны и другие применения.
Фьютексы — это очереди ядра для пользовательского кода
Попросту говоря, фьютекс — это очередь, управляемая ядром для решения задач пользовательского кода. Она позволяет пользовательскому коду запросить ядро приостановить выполнение своего потока до наступления некоторого события, а другому потоку в то же время — просигнализировать это событие и разбудить все ожидающие его потоки. Ранее мы упоминали возможность организовать спин-лок в пользовательском режиме, ожидая выполнение некоторого условия. Однако, очередь в ядре является значительно лучшей альтернативой, ведь она спасает нас от миллиардов впустую сожженных процессорных инструкций, выполняемых в цикле ожидания.
Вот диаграма из статьи «A futex overview and update» на LWN:
В коде ядра Linux фьютексы реализованы в файле kernel/futex.c. Ядро хранит хеш-таблицу, где ключами являются адреса — для быстрого поиска нужной очереди и добавления вызывающего процесса в неё. Всё, конечно, не так просто — ведь ядру и самому нужно синхронизировать доступ к данным внутри, плюс поддерживать всякие дополнительные опции фьютексов.
Ограниченное по времени ожидание с FUTEX_WAIT
Системный вызов futex имеет параметр timeout, позволяющий пользователю указать, как долго он готов ожидать. Вот полный пример, где это реализовано, а вот его ключевая часть:
printf("child waiting for An");
struct timespec timeout = {.tv_sec = 0, .tv_nsec = 500000000};
while (1) {
unsigned long long t1 = time_ns();
int futex_rc = futex(shared_data, FUTEX_WAIT, 0xA, &timeout, NULL, 0);
printf("child woken up rc=%d errno=%s, elapsed=%llun", futex_rc,
futex_rc ? strerror(errno) : "", time_ns() - t1);
if (futex_rc == 0 && *shared_data == 0xA) {
break;
}
}Если ожидание затянется на 500 мс, то функция futex завершится, и мы в очередной итерации цикла можем как-то на это отреагировать (вывести что-то на экран, записать в лог, продолжить ожидание или остановиться).
Используем фьютекс для реализации мьютекса
Мы начали эту статью с того, что фьютексы имеют практическую пользу при реализации более высокоуровневых объектов синхронизации. Давайте же попробуем, используя их (а также атомики) реализовать классический мьютекс. Реализация ниже построена на базе кода из статьи «Futexes are Tricky», написанной Ulrich Drepper.
Для этого примера я использую С++, в основном для возможности использовать атомики из стандарта С++11. Полный код вы можете найти здесь, а вот наиболее важная его часть:
class Mutex {
public:
Mutex() : atom_(0) {}
void lock() {
int c = cmpxchg(&atom_, 0, 1);
// If the lock was previously unlocked, there's nothing else for us to do.
// Otherwise, we'll probably have to wait.
if (c != 0) {
do {
// If the mutex is locked, we signal that we're waiting by setting the
// atom to 2. A shortcut checks is it's 2 already and avoids the atomic
// operation in this case.
if (c == 2 || cmpxchg(&atom_, 1, 2) != 0) {
// Here we have to actually sleep, because the mutex is actually
// locked. Note that it's not necessary to loop around this syscall;
// a spurious wakeup will do no harm since we only exit the do...while
// loop when atom_ is indeed 0.
syscall(SYS_futex, (int*)&atom_, FUTEX_WAIT, 2, 0, 0, 0);
}
// We're here when either:
// (a) the mutex was in fact unlocked (by an intervening thread).
// (b) we slept waiting for the atom and were awoken.
//
// So we try to lock the atom again. We set teh state to 2 because we
// can't be certain there's no other thread at this exact point. So we
// prefer to err on the safe side.
} while ((c = cmpxchg(&atom_, 0, 2)) != 0);
}
}
void unlock() {
if (atom_.fetch_sub(1) != 1) {
atom_.store(0);
syscall(SYS_futex, (int*)&atom_, FUTEX_WAKE, 1, 0, 0, 0);
}
}
private:
// 0 means unlocked
// 1 means locked, no waiters
// 2 means locked, there are waiters in lock()
std::atomic<int> atom_;
};
В этом коде функция cmpxhg — это простая обёртка для более удобного использования атомиков:
// An atomic_compare_exchange wrapper with semantics expected by the paper's
// mutex - return the old value stored in the atom.
int cmpxchg(std::atomic<int>* atom, int expected, int desired) {
int* ep = &expected;
std::atomic_compare_exchange_strong(atom, ep, desired);
return *ep;
}Данный пример кода содержит много комментариев с объяснением логики его работы. Это не помешает, поскольку есть существенный риск того, что вам захочется написать чуть более простую, но совершенно неправильную его версию. Что касается данного кода — он тоже не во всём идеален. Например, он пытается сделать предположение о внутреннем устройстве типа std::atomic, приводя его содержимое к int* для передачи в вызов futex. Это, в общем, случае, не верно. Код компилируется и работает на Linux x64, но у нас нет гарантии совместимости с другими платформами. Чтобы её получить — нам нужно добавить слой платформенной зависимости для атомиков. Поскольку это не тема данной статьи (а также потому что очень вряд ли вы будете смешивать в одном модуле С++ и фьютексы) мы опустим эту реализацию. Это просто демонстрация!
Мьютексы в glibc и низкоуровневые блокировки
И вот мы подобрались к тому, как glibc реализует POSIX-потоки, частью которых является тип pthread_mutex_t. Как я уже говорил в начале данной статьи, фьютексы — не совсем та вещь, которая понадобится рядовому разработчику. Они используются рантайм-библиотеками или чем-то очень узкоспециализированным для реализации примитивов синхронизации более высокого уровня. В этом контексте интересно посмотреть на реализацию мьютекса для NPTL. В коде glibc это файл nptl/pthread_mutex_lock.c.
Код достаточно усложнён из-за необходимости поддерживать различные типы мьютексов, но мы при желании можем найти достаточно знакомые блоки. Также можно взглянуть на файлы sysdeps/unix/sysv/linux/x86_64/lowlevellock.h и nptl/lowlevellock.c. Код несколько запутанный, но всё же комбинация операций сравнение-и-обмен и вызова futex находится легко.
Начальный комментарий файла systeds/nptl/lowlevellock.h должен вам уже быть хорошо понятен:
/* Low-level locks use a combination of atomic operations (to acquire and
release lock ownership) and futex operations (to block until the state
of a lock changes). A lock can be in one of three states:
0: not acquired,
1: acquired with no waiters; no other threads are blocked or about to block
for changes to the lock state,
>1: acquired, possibly with waiters; there may be other threads blocked or
about to block for changes to the lock state.
We expect that the common case is an uncontended lock, so we just need
to transition the lock between states 0 and 1; releasing the lock does
not need to wake any other blocked threads. If the lock is contended
and a thread decides to block using a futex operation, then this thread
needs to first change the state to >1; if this state is observed during
lock release, the releasing thread will wake one of the potentially
blocked threads.
..
*/Фьютексы в рантайме Go
Рантайм Go не использует libc (в большинстве случаев). Таким образом, он не может полагаться на реализацию POSIX-потоков. Вместо этого он напрямую вызывает лежащие уровнем ниже системные вызовы. Это делает его хорошим примером использования фьютексов. Поскольку нет возможности вызвать pthread_mutex_t — приходится писать свою замену. Давайте посмотрим как это сделано, начнём с видимого пользователю типа sync.Mutex (в src/sync/mutex.go).
Метод Lock этого типа пытается использовать атомарную операцию обмена (swap) для быстрого захвата блокировки. Если оказывается, что нужно ждать, он вызывает runtime_SemacquireMutex, который вызывает runtime.lock. Эта функция определена в src/runtime/lock_futex.go и в ней объявлено несколько констант, которые вам уже могут показаться знакомыми:
const (
mutex_unlocked = 0
mutex_locked = 1
mutex_sleeping = 2
...
)
// Possible lock states are mutex_unlocked, mutex_locked and mutex_sleeping.
// mutex_sleeping means that there is presumably at least one sleeping thread.
runtime.lock также пытается захватить блокировку с помощью атомик-функции. Это имеет смысл, поскольку runtime.lock вызывается во многих местах рантайма Go, но мне кажется можно было бы как-то оптимизировать код, убрав два последовательных вызова атомик-функции при вызове runtime.lock из Mutex.lock.
Если оказывается, что нужно ждать — вызывается платформозависимая функция futexsleep, которая определена для Linux в файле src/runtime/os_linux.go. Эта функция делает системный вызов futex с кодом FUTEX_WAIT_PRIVATE (в данном случае это подходит, поскольку рантайм Go живёт в одном процессе).
Автор: tangro
