| FUTEX(2) | Руководство программиста Linux | FUTEX(2) |
futex - быстрая блокировка в пользовательском пространстве
#include <linux/futex.h> #include <sys/time.h>
int futex(int *uaddr, int futex_op, int val,
const struct timespec *timeout, /* or: uint32_t val2 */
int *uaddr2, int val3);
Замечание: В glibc нет обёрточной функции для данного системного вызова; смотрите ЗАМЕЧАНИЯ.
Системный вызов futex() предоставляет программам метод для ожидания пока определённое условие не станет истинным. Обычно, этот системный вызов используется блокирующая конструкция в контексте синхронизации общей памяти. При использовании фьютексов основные операции синхронизации выполняются в пространстве пользователя. Программы пользовательского пространства выполняются системный вызов futex() только когда нужно, чтобы программа вошла в режим ожидания на долгий срок, пока условие не станет истинным. Также futex() можно использовать для пробуждения процессов или нитей, ожидающих определённого условия.
Фьютекс это 32-битное значение — называемое далее словом фьютекса — чей адрес передаётся в системный вызов futex() (фьютексы имеют размер в 32 бита на всех платформах, включая 64-битные системы). Все операции с фьютексами выполняются с этим значением. Чтобы сделать фьюетекс общим между процессами, фьютекс помещается в область общем памяти, создаваемой с помощью (например) mmap(2) или shmat(2) (то есть слово фьютекса может иметь различающиеся виртуальные адреса в разных процессах, но эти адреса всё равно указывают на одну область в физической памяти). В многонитевых программах достаточно поместить слово фьютекса в глобальную переменную, доступную из всех нитей.
Когда выполняется операция с фьютексом, запрашивается блокировка нити, которую выполняет ядро только, если слово фьютекса имеет значение, которое передаёт вызывающая нить (в одном из аргументов вызова 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);
int oldval = *(int *) uaddr2;
*(int *) 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-фьютексами, описанные далее, отличаются от других операций с фьютексами в том, что они следуют политике использования значения слова фьютекса:
С этой действующей политикой приложение пространства пользователя может получить свободную блокировку или освободить блокировку с помощью атомарных инструкций, выполняемых в пользовательском режиме (например, операцией сравнение-и-обмен cmpxchg на архитектуре x86). Получение блокировки состоит просто из использования сравнения-и-обмена для атомарного изменения значения слова фьютекса на TID вызывающего, если предыдущее значение было равно 0. Для освобождения блокировки требуется использовать сравнение-и-обмен для изменения значения слова фьютекса на 0, если предыдущее значение равно ожидаемому TID.
Если фьютекс уже получен (т. е. имеет ненулевое значение), то ожидающие должны применить операцию FUTEX_LOCK_PI для получения блокировки. Если другие нити ждут блокировку, то в значении фьютекса установлен бит FUTEX_WAITERS; в этом случае владелец блокировки должен применить операцию FUTEX_UNLOCK_PI для освобождения блокировки.
В случаях, когда вызывающие переходят в ядро (т. е., требуется выполнение вызова futex()), после этого они напрямую работают с так называемым RT-мьютексом, механизмом блокировок ядра, которым реализована требуемая семантика наследования приоритета. После получения RT-мьютекса, значение фьютекса обновляется соответствующим образом, перед возврата вызывающей нити в пространство пользователя.
Важно упомянуть, что ядро обновит значение слова фьютекса до возврата в пространство пользователя (это предотвращает возможность попадания значения слова фьютекса в некорректное состояние, такое, что имея владельца, значение равно 0, или имея ожидающих, не установлен бит FUTEX_WAITERS).
Если фьютекс связан с RT-мьютексом в ядре (т. е., есть заблокированные ожидающие) и владелец фьютекса/RT-мьютекса неожиданно завершился, то ядро очищает RT-мьютекс и передаёт его следующему ожидающему. Это, в свою очередь, требует, чтобы значение в пользовательском пространстве было изменено соответствующим образом. Для сообщения о необходимости этого ядро изменяет бит FUTEX_OWNER_DIED в слове фьютекса вместе со сменой ID нити нового владельца. Пользовательское пространство может определить такую ситуацию по установленному биту FUTEX_OWNER_DIED и затем, соответствующим образом, очистить устаревшее состояние, возникшее из-за закончившего работу владельца.
PI-фьютексы обрабатываются при указании в futex_op одного из значений, перечисленных далее. Заметим, что операции с PI-фьютексами должны использовать попарно и учитывать некоторые дополнительные требования:
Операции с PI-фьютексами:
В случае ошибки (предполагается, что futex() был вызван через syscall(2)), все операции возвращают -1 и присваивают errno номер ошибки.
При успешном выполнении возвращаемое значение зависит от операции:
Фьютексы появились в стабильном ядре Linux версии 2.6.0.
Начальная поддержка фьютексов была встроена в Linux 2.5.7, но с другой семантикой, отличающейся от описанной выше. Семантика системного вызова с четырьмя аргументами, описанная в этой странице, появилась в Linux 2.5.40. Пятый аргумент была добавлен в Linux 2.5.70, а шестой аргумент был добавлен в Linux 2.6.7.
Данный системный вызов есть только в Linux.
В glibc нет обёртки для данного системного вызова; запускайте его с помощью syscall(2).
На основе фьютексов было реализовано несколько высокоуровневых программных абстракций, например, семафоры 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)
Продемонстрировано использование фьютексов в программе, где родитель
и потомок используют пару фьютексов, расположенных в общем анонимном
отображении, для синхронизации доступа к общему ресурсу: терминалу.
Каждый из процессов записывает num-loops на терминал и использует
протокол синхронизации, который гарантирует, что они выполняют запись
поочерёдно.
*/
#define _GNU_SOURCE
#include <stdio.h>
#include <errno.h>
#include <stdatomic.h>
#include <stdlib.h>
#include <unistd.h>
#include <sys/wait.h>
#include <sys/mman.h>
#include <sys/syscall.h>
#include <linux/futex.h>
#include <sys/time.h>
#define errExit(msg) do { perror(msg); exit(EXIT_FAILURE); \
} while (0)
static int *futex1, *futex2, *iaddr;
static int
futex(int *uaddr, int futex_op, int val,
const struct timespec *timeout, int *uaddr2, int val3)
{
return syscall(SYS_futex, uaddr, futex_op, val,
timeout, uaddr, val3);
}
/* Получить фьютекс, указанный 'futexp': подождать пока его
значение не станет 1, и изменить значение на 0. */
static void
fwait(int *futexp)
{
int s;
/* atomic_compare_exchange_strong(ptr, oldval, newval)
атомарно выполняет эквивалент кода:
if (*ptr == *oldval)
*ptr = newval;
Она возвращает true, если тест вернул true и было обновлено *ptr.
while (1) {
/* фьютекс доступен? */
const int zero = 0;
if (atomic_compare_exchange_strong(futexp, &zero, 1))
break; /* да */
/* фьютекс недоступен, ждём */
s = futex(futexp, FUTEX_WAIT, 0, NULL, NULL, 0);
if (s == -1 && errno != EAGAIN)
errExit("futex-FUTEX_WAIT");
}
}
/* Освобождаем фьютекс, указанный в 'futexp': если значение фьютекса
сейчас равно 0, то присваиваем ему 1 и пробуждаем ожидающий фьютекса,
то есть, если вторая сторона заблокирована в fpost(), то она может
продолжить работу. */
static void
fpost(int *futexp)
{
int s;
/* atomic_compare_exchange_strong() описан в комментария выше */
const int one = 1;
if (atomic_compare_exchange_strong(futexp, &one, 0)) {
s = futex(futexp, FUTEX_WAKE, 1, NULL, NULL, 0);
if (s == -1)
errExit("futex-FUTEX_WAKE");
}
}
int
main(int argc, char *argv[])
{
pid_t childPid;
int j, nloops;
setbuf(stdout, NULL);
nloops = (argc > 1) ? atoi(argv[1]) : 5;
/* Создаём общее анонимное отображение, в котором будем хранить
фьютексы. Так как фьютексы совместно используются процессами,
воспользуемся операциями с «общими» фьютексами (т. е., без
суффикса «_PRIVATE»). */
iaddr = mmap(NULL, sizeof(int) * 2, PROT_READ | PROT_WRITE,
MAP_ANONYMOUS | MAP_SHARED, -1, 0);
if (iaddr == MAP_FAILED)
errExit("mmap");
futex1 = &iaddr[0];
futex2 = &iaddr[1];
*futex1 = 0; /* Состояние: недоступен */
*futex2 = 1; /* Состояние: доступен */
/* Создаём дочерний процесс, который наследует общее анонимное
отображение. */
childPid = fork();
if (childPid == -1)
errExit("fork");
if (childPid == 0) { /* Child */
for (j = 0; j < nloops; j++) {
fwait(futex1);
printf("Потомок (%ld) %d\n", (long) getpid(), j);
fpost(futex2);
}
exit(EXIT_SUCCESS);
}
/* предок попадает сюда */
for (j = 0; j < nloops; j++) {
fwait(futex2);
printf("Родитель (%ld) %d\n", (long) 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. и Guniguntala, D., 2009. Requeue-PI: Making Glibc Condvars PI-Aware (доклад на Real-Time Linux Workshop в 2009 году), 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, доступен на ftp://ftp.kernel.org/pub/linux/kernel/people/rusty/
| 2019-03-06 | Linux |