| futex(2) | System Calls Manual | futex(2) |
futex - быстрая блокировка в пользовательском пространстве
Standard C library (libc, -lc)
#include <linux/futex.h> /* определения констант FUTEX_* */ #include <sys/syscall.h> /* определения констант SYS_* */ #include <unistd.h>
long syscall(SYS_futex, uint32_t *uaddr, int futex_op, uint32_t val,
const struct timespec *timeout, /* or: uint32_t val2 */
uint32_t *uaddr2, uint32_t val3);
Note: glibc provides no wrapper for futex(), necessitating the use of syscall(2).
Системный вызов futex() предоставляет программам метод для ожидания пока определённое условие не станет истинным. Обычно, этот системный вызов используется блокирующая конструкция в контексте синхронизации общей памяти. При использовании фьютексов основные операции синхронизации выполняются в пространстве пользователя. Программы пользовательского пространства выполняются системный вызов futex() только когда нужно, чтобы программа вошла в режим ожидания на долгий срок, пока условие не станет истинным. Также futex() можно использовать для пробуждения процессов или нитей, ожидающих определённого условия.
A futex is a 32-bit value—referred to below as a futex word—whose address is supplied to the futex() system call. (Futexes are 32 bits in size on all platforms, including 64-bit systems.) All futex operations are governed by this value. In order to share a futex between processes, the futex is placed in a region of shared memory, created using (for example) mmap(2) or shmat(2). (Thus, the futex word may have different virtual addresses in different processes, but these addresses all refer to the same location in physical memory.) In a multithreaded program, it is sufficient to place the futex word in a global variable shared by all threads.
Когда выполняется операция с фьютексом, запрашивается блокировка нити, которую выполняет ядро только, если слово фьютекса имеет значение, которое передаёт вызывающая нить (в одном из аргументов вызова futex()) равное ожидаемому значению слова фьютекса. Загрузка значения слова фьютекса, сравнение этого значения с ожидаемым и реальная блокировка выполняется автоматически и будет полностью упорядочена в соответствии с одновременными операциями, выполняемыми другими нитями на тем же словом фьютекса. Таким образом, слово фьютекса используется для обеспечения синхронизации в пользовательском пространстве реализованной через блокировку ядром. По аналогии с атомарной операцией сравнения-и-обмена, которая, потенциально, изменяет общую память, блокировка через фьютекс является атомарной операцией сравнения-и-блокировки.
Одним из применений фьютексов является реализация блокировок. Состояние блокировки (т. е., получена или не получена) может быть представлено в виде атомарно доступного флага в общей памяти. При отсутствии конкурентов, нить может получить доступ или изменить состояние блокировки атомарными инструкциями, например атомарно изменяя её значение с не полученной на полученную с помощью атомарной инструкции сравнения-и-обмена (эти инструкции целиком выполняются в пользовательском режим, и ядро с состоянием блокировки ничего не делает). С другой стороны, нить может не получить блокировку, так как она уже получена другой нитью. После этого она может передать флаг блокировки в виде слова фьютекса, значением которого будет ожидаемое значение состояния получения в операции ожидания futex(). Операция futex() блокируется, только когда блокировка всё ещё имеется (т. е., значение слова фьютекса совпадает с «состояния получения»). При освобождении блокировки нить сначала сбрасывает состояние блокировки в не полученное, а затем вызывает операцию фьютекса, которая пробуждает нить, заблокированную флагом блокировки, используя его как слово фьютекса (в дальнейшем это может быть оптимизировано для устранения ненужных пробуждений). О том, как использовать фьютексы, смотрите futex(7).
Кроме основных операций ожидания и пробуждения у фьютексов есть и другие операции, для более сложных случаев применения.
Заметим, что для использования фьютексов не требуется явных действий по инициализации и удалению; ядро поддерживает фьютексы (т. е., внутренняя часть реализации ядра) только в операции FUTEX_WAIT, описанной далее, обрабатывая определённое слово фьютекса.
В аргументе uaddr указывает слово фьютекса. На всех платформах фьютексы это целые числа размером в четыре байта, которые должны быть выровнены по четырёх байтовой границе. Операция, выполняемая с фьютексом, задаётся в аргументе futex_op; какое значение будет задаваться в val, зависит от futex_op.
Остальные аргументы (timeout, uaddr2 и val3) требуются только для определённых операций с фьютексами и описаны далее. Там, где эти аргументы не нужны, они игнорируются.
Для некоторых операций блокировки аргументом timeout является указатель на структуру timespec, в которой задаётся время ожидания операции. Однако, несмотря на прототип, показанный выше, для некоторых операций используются только младшие четыре байта этого аргумента вместо целого числа, назначение которого определяется операцией. Для этих операций ядро преобразует значение timeout сначала к unsigned long, затем к uint32_t. Отсюда и до конца страницы этот аргумент будет называться val2, когда он интерпретируется в такой манере.
Там, где требуется, аргумент uaddr2 представляет собой указатель на второе слово фьютекса, которое используется операцией.
Интерпретация последнего целочисленного аргумента, val3, зависит от операции.
Аргумент futex_op состоит из двух частей: команды, задающей выполняемую операцию, и объединённые биты нуля или более параметров, которые изменяют поведение операции. Параметры, которые можно включать в futex_op:
Операцией в futex_op может быть одно из:
lock(A)
while (!check_value(V)) {
unlock(A);
block_on(B);
lock(A);
};
unlock(A);
uint32_t oldval = *(uint32_t *) uaddr2;
*(uint32_t *) uaddr2 = oldval op oparg;
futex(uaddr, FUTEX_WAKE, val, 0, 0, 0);
if (oldval cmp cmparg)
futex(uaddr2, FUTEX_WAKE, val2, 0, 0, 0);
+---+---+-----------+-----------+
|оп |сра| аргоп | аргсра |
+---+---+-----------+-----------+
4 4 12 12 <== кол-во бит
#define FUTEX_OP(op, oparg, cmp, cmparg) \
(((op & 0xf) << 28) | \
((cmp & 0xf) << 24) | \
((oparg & 0xfff) << 12) | \
(cmparg & 0xfff))
FUTEX_OP_SET 0 /* uaddr2 = oparg; */
FUTEX_OP_ADD 1 /* uaddr2 += oparg; */
FUTEX_OP_OR 2 /* uaddr2 |= oparg; */
FUTEX_OP_ANDN 3 /* uaddr2 &= ~oparg; */
FUTEX_OP_XOR 4 /* uaddr2 ^= oparg; */
FUTEX_OP_ARG_SHIFT 8 /* исп. (1 << oparg) как операнд */
FUTEX_OP_CMP_EQ 0 /* если (oldval == cmparg) — пробудить */
FUTEX_OP_CMP_NE 1 /* если (oldval != cmparg) — пробудить */
FUTEX_OP_CMP_LT 2 /* если (oldval < cmparg) — пробудить */
FUTEX_OP_CMP_LE 3 /* если (oldval <= cmparg) — пробудить */
FUTEX_OP_CMP_GT 4 /* если (oldval > cmparg) — пробудить */
FUTEX_OP_CMP_GE 5 /* если (oldval >= cmparg) — пробудить */
В Linux поддерживается наследование приоритета из-за фьютексов priority-inheritance (PI), так как требуется решать проблему обратного приоритета, которая встречается у обычных блокировок фьютексов. Проблема обратного приоритета возникает, когда задача с высоким приоритетом блокируется в ожидании получения блокировки, которую удерживает задача с низким приоритетом, в то время как задачи со средним приоритетом постоянно вытесняют задачу с низким приоритетом с ЦП. В следствии этого, выполнение задачи с низким приоритетом никак не продвигается к освобождению блокировки, и задача с высоким приоритетом остаётся заблокированной.
Наследование приоритета — это механизм, который решает проблему обратного приоритета. С его помощью, когда задача с высоким приоритетом блокируется из-за удержания блокировки задачей с низким приоритетом, приоритет задачи с низким приоритетом временно повышается до приоритета, имеющегося у заблокированной задачи, и поэтому не происходит вытеснения задачами с средним приоритетом, что способствует ускорению освобождения блокировки. Чтобы это работало, наследование приоритета должно быть транзитивным, то есть если задача с высоким приоритетом заблокирована, из-за удержания блокировки задачей с низким приоритетом, которая сама заблокирована из-за удержания блокировки другой задачей со средним приоритетом (и так далее, по цепочке произвольной длины), то для обеих этих задач (или, шире, всех задач в заблокированной цепочке) повышается приоритет, который равен приоритету задачи с высоким приоритетом.
Со стороны пользовательского пространства фьютекс является PI из-за следования соглашениям (описанных далее) между пользовательским пространством и ядром о значении слова фьютекса и применяемым операциям над PI-фьютексами, описанным далее (в отличие от других операций с фьютексами, описанных выше, операции с PI-фьютексами разработаны для реализации очень специфичных механизмов IPC).
Операции с PI-фьютексами, описанные далее, отличаются от других операций с фьютексами в том, что они следуют политике использования значения слова фьютекса:
FUTEX_WAITERS | TID
С этой действующей политикой приложение пространства пользователя может получить свободную блокировку или освободить блокировку с помощью атомарных инструкций, выполняемых в пользовательском режиме (например, операцией сравнение-и-обмен cmpxchg на архитектуре x86). Получение блокировки состоит просто из использования сравнения-и-обмена для атомарного изменения значения слова фьютекса на TID вызывающего, если предыдущее значение было равно 0. Для освобождения блокировки требуется использовать сравнение-и-обмен для изменения значения слова фьютекса на 0, если предыдущее значение равно ожидаемому TID.
If a futex is already acquired (i.e., has a nonzero value), waiters must employ the FUTEX_LOCK_PI or FUTEX_LOCK_PI2 operations to acquire the lock. If other threads are waiting for the lock, then the FUTEX_WAITERS bit is set in the futex value; in this case, the lock owner must employ the FUTEX_UNLOCK_PI operation to release the lock.
В случаях, когда вызывающие переходят в ядро (т. е., требуется выполнение вызова futex()), после этого они напрямую работают с так называемым RT-мьютексом, механизмом блокировок ядра, которым реализована требуемая семантика наследования приоритета. После получения RT-мьютекса, значение фьютекса обновляется соответствующим образом, перед возврата вызывающей нити в пространство пользователя.
Важно упомянуть, что ядро обновит значение слова фьютекса до возврата в пространство пользователя (это предотвращает возможность попадания значения слова фьютекса в некорректное состояние, такое, что имея владельца, значение равно 0, или имея ожидающих, не установлен бит FUTEX_WAITERS).
Если фьютекс связан с RT-мьютексом в ядре (т. е., есть заблокированные ожидающие) и владелец фьютекса/RT-мьютекса неожиданно завершился, то ядро очищает RT-мьютекс и передаёт его следующему ожидающему. Это, в свою очередь, требует, чтобы значение в пользовательском пространстве было изменено соответствующим образом. Для сообщения о необходимости этого ядро изменяет бит FUTEX_OWNER_DIED в слове фьютекса вместе со сменой ID нити нового владельца. Пользовательское пространство может определить такую ситуацию по установленному биту FUTEX_OWNER_DIED и затем, соответствующим образом, очистить устаревшее состояние, возникшее из-за закончившего работу владельца.
PI-фьютексы обрабатываются при указании в futex_op одного из значений, перечисленных далее. Заметим, что операции с PI-фьютексами должны использовать попарно и учитывать некоторые дополнительные требования:
Операции с PI-фьютексами:
In the event of an error (and assuming that futex() was invoked via syscall(2)), all operations return -1 and set errno to indicate the error.
При успешном выполнении возвращаемое значение зависит от операции:
Фьютексы появились в стабильном ядре Linux версии 2.6.0.
Начальная поддержка фьютексов была встроена в Linux 2.5.7, но с другой семантикой, отличающейся от описанной выше. Семантика системного вызова с четырьмя аргументами, описанная в этой странице, появилась в Linux 2.5.40. Пятый аргумент была добавлен в Linux 2.5.70, а шестой аргумент был добавлен в Linux 2.6.7.
Данный вызов есть только в Linux.
На основе фьютексов было реализовано несколько высокоуровневых программных абстракций, например, семафоры POSIX и различные механизмы синхронизации нитей POSIX (мьютексы, переменные условий, блокировки чтения-записи и барьеры).
В программе, показанной далее, показано использование фьютексов: родительский и дочерний процессы используют пару фьютексов, расположенных в общем анонимном отображении, для синхронизации доступа к общему ресурсу: терминалу. Каждый из процессов записывает nloops (аргумент командной строки, если отсутствует, то 5) сообщений на терминал и использует протокол синхронизации, который гарантирует, что они записываются поочерёдно. Результат работы программы:
$ ./futex_demo Родитель (18534) 0 Потомок (18535) 0 Родитель (18534) 1 Потомок (18535) 1 Родитель (18534) 2 Потомок (18535) 2 Родитель (18534) 3 Потомок (18535) 3 Родитель (18534) 4 Потомок (18535) 4
/* futex_demo.c
Использование: futex_demo [nloops]
(по умолчанию: 5)
Demonstrate the use of futexes in a program where parent and child
use a pair of futexes located inside a shared anonymous mapping to
synchronize access to a shared resource: the terminal. The two
processes each write 'num-loops' messages to the terminal and employ
a synchronization protocol that ensures that they alternate in
writing messages.
*/
#define _GNU_SOURCE
#include <err.h>
#include <errno.h>
#include <linux/futex.h>
#include <stdatomic.h>
#include <stdint.h>
#include <stdio.h>
#include <stdlib.h>
#include <sys/mman.h>
#include <sys/syscall.h>
#include <sys/time.h>
#include <sys/wait.h>
#include <unistd.h>
static uint32_t *futex1, *futex2, *iaddr;
static int
futex(uint32_t *uaddr, int futex_op, uint32_t val,
const struct timespec *timeout, uint32_t *uaddr2, uint32_t val3)
{
return syscall(SYS_futex, uaddr, futex_op, val,
timeout, uaddr2, val3);
}
/* Acquire the futex pointed to by 'futexp': wait for its value to
become 1, and then set the value to 0. */
static void
fwait(uint32_t *futexp)
{
long s;
const uint32_t one = 1;
/* atomic_compare_exchange_strong(ptr, oldval, newval)
атомарно выполняет эквивалент кода:
if (*ptr == *oldval)
*ptr = newval;
Она возвращает true, если тест вернул true и было обновлено *ptr.
while (1) {
/* фьютекс доступен? */
if (atomic_compare_exchange_strong(futexp, &one, 0))
break; /* да */
/* фьютекс недоступен, ждём. */
s = futex(futexp, FUTEX_WAIT, 0, NULL, NULL, 0);
if (s == -1 && errno != EAGAIN)
err(EXIT_FAILURE, "futex-FUTEX_WAIT");
}
}
/* Release the futex pointed to by 'futexp': if the futex currently
has the value 0, set its value to 1 and then wake any futex waiters,
so that if the peer is blocked in fwait(), it can proceed. */
static void
fpost(uint32_t *futexp)
{
long s;
const uint32_t zero = 0;
/* atomic_compare_exchange_strong() описан
в комментария выше */
if (atomic_compare_exchange_strong(futexp, &zero, 1)) {
s = futex(futexp, FUTEX_WAKE, 1, NULL, NULL, 0);
if (s == -1)
err(EXIT_FAILURE, "futex-FUTEX_WAKE");
}
}
int
main(int argc, char *argv[])
{
pid_t childPid;
unsigned int nloops;
setbuf(stdout, NULL);
nloops = (argc > 1) ? atoi(argv[1]) : 5;
/* Создаём общее анонимное отображение, в котором будем хранить
фьютексы. Так как фьютексы совместно используются процессами,
воспользуемся операциями с «общими» фьютексами (т. е., без
суффикса «_PRIVATE»). */
iaddr = mmap(NULL, sizeof(*iaddr) * 2, PROT_READ | PROT_WRITE,
MAP_ANONYMOUS | MAP_SHARED, -1, 0);
if (iaddr == MAP_FAILED)
err(EXIT_FAILURE, "mmap");
futex1 = &iaddr[0];
futex2 = &iaddr[1];
*futex1 = 0; /* Состояние: недоступен */
*futex2 = 1; /* Состояние: доступен */
/* Создаём дочерний процесс, который наследует общее анонимное
отображение. */
childPid = fork();
if (childPid == -1)
err(EXIT_FAILURE, "fork");
if (childPid == 0) { /* Child */
for (unsigned int j = 0; j < nloops; j++) {
fwait(futex1);
printf("Child (%jd) %u\n", (intmax_t) getpid(), j);
fpost(futex2);
}
exit(EXIT_SUCCESS);
}
/* предок попадает сюда. */
for (unsigned int j = 0; j < nloops; j++) {
fwait(futex2);
printf("Parent (%jd) %u\n", (intmax_t) getpid(), j);
fpost(futex1);
}
wait(NULL);
exit(EXIT_SUCCESS);
}
get_robust_list(2), restart_syscall(2), pthread_mutexattr_getprotocol(3), futex(7), sched(7)
Файлы из дерева исходного кода ядра:
Franke, H., Russell, R., and Kirwood, M., 2002. Fuss, Futexes
and Furwocks: Fast Userlevel Locking in Linux
(доклад на
симпозиуме
по Linux в 2002 году),
http://kernel.org/doc/ols/2002/ols2002-pages-479-495.pdf
Hart, D., 2009. A futex overview and update, http://lwn.net/Articles/360699/
Hart, D. and Guniguntala, D., 2009. Requeue-PI: Making glibc Condvars PI-Aware (from proceedings of the 2009 Real-Time Linux Workshop), http://lwn.net/images/conf/rtlws11/papers/proc/p10.pdf
Drepper, U., 2011. Futexes Are Tricky, http://www.akkadia.org/drepper/futex.pdf
Пример
библиотеки
futex, futex-*.tar.bz2,
доступен
на
https://mirrors.kernel.org/pub/linux/kernel/people/rusty/
Русский перевод этой страницы руководства был сделан Azamat Hackimov <azamat.hackimov@gmail.com>, Dmitry Bolkhovskikh <d20052005@yandex.ru>, Yuri Kozlov <yuray@komyakino.ru> и Иван Павлов <pavia00@gmail.com>
Этот перевод является бесплатной документацией; прочитайте Стандартную общественную лицензию GNU версии 3 или более позднюю, чтобы узнать об условиях авторского права. Мы не несем НИКАКОЙ ОТВЕТСТВЕННОСТИ.
Если вы обнаружите ошибки в переводе этой страницы руководства, пожалуйста, отправьте электронное письмо на man-pages-ru-talks@lists.sourceforge.net.
| 5 февраля 2023 г. | Linux man-pages 6.03 |