ИМЯ

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_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_PRIVATE_FLAG (начиная с Linux 2.6.22)
Этот параметр может быть использован для всех операций с фьютексами. Он
указывает ядру, что фьютекс доступен только для одного процесса и
недоступен другим процессам (т. е., используется для синхронизации только
между нитями одного процесса). Это позволяет ядру выполнять некоторые
дополнительные оптимизации для производительности.

Для удобства, в <linux/futex.h> определён набор констант с суффиксом
_PRIVATE, которые эквивалентны всем операциям, перечисленным ниже, но с
добавленным константным значением флага FUTEX_PRIVATE_FLAG. То есть,
существуют FUTEX_WAIT_PRIVATE, FUTEX_WAKE_PRIVATE и т. д.

FUTEX_CLOCK_REALTIME (начиная с Linux 2.6.28)
Этот бит параметра может применяться только с операциями FUTEX_WAIT_BITSET,
FUTEX_WAIT_REQUEUE_PI и FUTEX_WAIT (начиная с Linux 4.5).

Если он указан, то ядро измеряет timeout по часам CLOCK_REALTIME.

Если он не указан, то ядро измеряет timeout по часам CLOCK_MONOTONIC.

Операцией в futex_op может быть одно из:

FUTEX_WAIT (начиная с Linux 2.6.0)
то вызов немедленно завершается с ошибкой EAGAIN.

Целью сравнения с ожидаемым значением является предотвращение потери
пробуждения. Если другая нить изменит значение слова фьютекса после того,
как вызывающая нить решила заблокироваться из-за предыдущего значения и
если другая нить выполнила операцию FUTEX_WAKE (или подобное пробуждение)
после изменения значения и до этой операции FUTEX_WAIT, то вызывающая нить
увидит эту смену значения и не станет впадать в сон.

Если значение timeout не равно NULL, то структура, на которую он указывает,
определяет время ожидания (этот интервал будет округлён до точности
системных часов, и гарантируется, что он не наступит раньше положенного).
По умолчанию время ожидания измеряется по часам CLOCK_MONOTONIC, но начиная
с Linux 4.5 можно выбрать часы CLOCK_REALTIME, указав FUTEX_CLOCK_REALTIME
в futex_op. Если timeout равно NULL, то вызов блокируется бессрочно.

Замечание: при FUTEX_WAIT значение timeout интерпретируется как
относительное. В этом отличие от других операций над фьютексами, в которых
timeout интерпретируется как абсолютное значение. Чтобы получить эквивалент
FUTEX_WAIT с абсолютным временем ожидания укажите FUTEX_WAIT_BITSET в val3
вместе с FUTEX_BITSET_MATCH_ANY.

Аргументы uaddr2 и val3 игнорируются.

FUTEX_WAKE (начиная с Linux 2.6.0)
Эта операция пробуждает не больше val процессов, ожидающих (например,
внутри FUTEX_WAIT) слово фьютекса по адресу uaddr. Чаще всего, val
присваивают или 1 (пробудить одного ожидающего), или INT_MAX (пробудить
всех ожидающих). Не гарантируется, что разбудят каких-то определённых
ожидающих (например, что ожидающий с большим приоритетом планировщика будет
разбужен раньше ожидающего, имеющего меньший приоритет).

Аргументы timeout, uaddr2 и val3 игнорируются.

FUTEX_FD (начиная с Linux 2.6.0 и по Linux 2.6.25 включительно)
Эта операция создаёт файловый дескриптор, который связан с фьютексом по
адресу uaddr. Вызывающий должен закрыть возвращённый файловый дескриптор
после использования. Если другой процесс или нить выполняет операцию
FUTEX_WAKE со словом фьютекса, то файловый дескриптор будет отмечен как
доступный для чтения в select(2), poll(2) и epoll(7).

Файловый дескриптор можно использовать для получения асинхронных
уведомлений: если val не равно нулю, то когда другой процесс или нить
выполняют FUTEX_WAKE, то вызывающий примет сигнал с номером, который был
указан в val.

Аргументы timeout, uaddr2 и val3 игнорируются.

Так как по своей природе операция FUTEX_FD приводит к состязательности, она
была удалена из Linux, начиная с версии 2.6.26.

FUTEX_REQUEUE (начиная с Linux 2.6.0)
Эта операция выполняет ту же задачу, что и FUTEX_CMP_REQUEUE (смотрите
далее), за исключением того, что она не проверяет используемое значение в
val3 (аргумент val3 игнорируется).

FUTEX_CMP_REQUEUE (начиная с Linux 2.6.7)
Загрузка из uaddr является атомарным доступом к памяти (т. е., используются
атомарные машинные инструкции соответствующей архитектуры). Эта загрузка,
сравнение с val3 и перестановка в очередь ожидающих выполняются атомарно и
целиком упорядочены относительно других фьютекс-операций с этим словом
фьютекса.

Типичными значениями val являются 0 или 1 (указание INT_MAX бесполезно, так
как это сделало бы операцию FUTEX_CMP_REQUEUE эквивалентной FUTEX_WAKE).
Значение ограничения, указанное в val2, обычно, или 1 или INT_MAX (указание
0 бесполезно, так как это сделало бы операцию FUTEX_CMP_REQUEUE
эквивалентной FUTEX_WAIT).

Операция FUTEX_CMP_REQUEUE была добавлена в качестве замены имевшейся
FUTEX_REQUEUE. Различие в том, что проверку значения по адресу uaddr можно
использовать для гарантии того, что перестановка в очередь произойдёт
только при определённых условиях, что в определённых случаях позволит
избежать состязательности.

И FUTEX_REQUEUE и FUTEX_CMP_REQUEUE можно использовать для недопущения
«нашествия орды» из пробудившихся, которое может произойти при
использовании FUTEX_WAKE в случаях, когда всем разбуженным ожидающим
требуется заблокировать другой фьютекс. Рассмотрим следующий сценарий, где
несколько ожидающих нитей ждут B, очередь ожидания реализована с помощью
фьютекса:

lock(A)
while (!check_value(V)) {
unlock(A);
block_on(B);
lock(A);
};
unlock(A);

Если пробуждающая нить использует FUTEX_WAKE, то все ожидающие,ждущие B,
проснулись бы, и попытались получить блокировку A. Однако пробуждение всех
нитей таким образом было бы нецелесообразно, так как все кроме одной нити
снова немедленно бы заблокировались в ожидании A. В отличие от этого,
операция перестановки в очередь разбудит только одного ожидающего и
переместит остальных ожидающих в ожидание блокировки A, и когда разбуженный
ожидающий разблокирует A, то следующий ожидающий сможет продолжить работу.

FUTEX_WAKE_OP (начиная с Linux 2.6.14)
Эта операция была добавлена для работы в некоторых случаях из
пользовательского пространства, в которых нужно одновременно учитывать
несколько фьютексов. Самый известный пример — реализация
pthread_cond_signal(3), которая требует операций для работы с двумя
фьютексами: один для реализации мьютекса, а другой для реализации очереди
ожидания, связанной с переменной условия. Операция FUTEX_WAKE_OP позволяет
это реализовать без увеличения состязательности и контекстного
переключения.

Операция FUTEX_WAKE_OP эквивалентна выполнению следующего кода, при чём,
атомарно и полностью упорядочено в соответствии с другими
фьютекс-операциями, выполняемыми над двумя указанными словами фьютекса:

int oldval = *(int *) uaddr2;
*(int *) uaddr2 = oldval op oparg;

используются атомарные машинные инструкции на соответствующей
архитектуре);

* пробуждает не более val ожидающих у фьютекса слова фьютекса по адресу
uaddr; и

* в зависимости от результата проверки первоначального значения слова
фьютекса по адресу uaddr2, пробуждает не более val2 ожидающих у фьютекса
слова фьютекса по адресу uaddr2.

Операция и сравнение, которое будет выполнено, кодируется в битах аргумента
val3. Графически, кодирование выглядит так:

+---+---+-----------+-----------+
|оп |сра| аргоп | аргсра |
+---+---+-----------+-----------+
4 4 12 12 <== кол-во бит

В виде кода это выглядит так:

#define FUTEX_OP(op, oparg, cmp, cmparg) \
(((op & 0xf) << 28) | \
((cmp & 0xf) << 24) | \
((oparg & 0xfff) << 12) | \
(cmparg & 0xfff))

Указанные выше op и cmp могут содержат один из кодов, перечисленных далее.
Компоненты oparg и cmparg являются числовыми литералами, с учётом замечаний
далее.

Компонент op может иметь одно из следующих значений:

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; */

Также, битовое сложение следующего значения с op приводит к использованию
(1 << oparg) в качестве операнда:

FUTEX_OP_ARG_SHIFT 8 /* исп. (1 << oparg) как операнд */

В поле cmp может быть одно из:

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) — пробудить */

Возвращаемое значение операции FUTEX_WAKE_OP — сумма количества разбуженных
ожидающих фьютекса uaddr и количества разбуженных ожидающих фьютекса
uaddr2.

FUTEX_WAIT_BITSET (начиная с Linux 2.6.25)
Аргумент uaddr2 игнорируется.

FUTEX_WAKE_BITSET (начиная с Linux 2.6.25)
Данная операция подобна FUTEX_WAKE, за исключением того, что val3
используется для передачи 32-битной маски в ядро. Данная битовая маска, в
которой должен быть установлен хотя бы один бит, используется для выбора
ожидающих, которые должны быть разбужены. Выбор выполняется путём
побитового И битовой маски «wake» (т. е., значения val3) и битовой маски,
которая хранится в ядре во внутреннем состоянии ожидающего (битовая маска
«wait», устанавливающаяся с помощью FUTEX_WAIT_BITSET). Все ожидающие, для
которых результат побитового И не равен нулю, пробуждаются; оставшиеся
ожидающие продолжают спать.

Влияние FUTEX_WAIT_BITSET и FUTEX_WAKE_BITSET позволяет выбирать
пробуждающихся из многих ожидающих, которые заблокированы на один фьютекс.
Однако заметим, что в зависимости от варианта применения, использование
данного свойства комбинирования битовой маски с фьютексом может быть менее
эффективно, чем простое использование нескольких фьютексов, так как
использование комбинирования битовой маски требует от ядра проверки всех
ожидающих фьютекса, включая тех, которые и не нужно было бы будить (т. е.,
у них неподходящий набор бит в их битовой маске «wait»).

Константу FUTEX_BITSET_MATCH_ANY, которая соответствует всем установленным
битам в 32-битной маске, можно использовать в аргументе val3 для
FUTEX_WAIT_BITSET и FUTEX_WAKE_BITSET. Кроме различий в обработке аргумента
timeout, операция FUTEX_WAIT эквивалентна FUTEX_WAIT_BITSET с val3, равным
FUTEX_BITSET_MATCH_ANY, то есть разрешается будить любого пробуждающего.
Операция FUTEX_WAKE эквивалентна FUTEX_WAKE_BITSET с val3, равным
FUTEX_BITSET_MATCH_ANY, то есть пробуждается любой(ые) пробуждающий.

Аргументы uaddr2 и timeout игнорируются.

Наследование приоритета из-за фьютексов
В Linux поддерживается наследование приоритета из-за фьютексов
priority-inheritance (PI), так как требуется решать проблему обратного приоритета,
которая встречается у обычных блокировок фьютексов. Проблема обратного приоритета
возникает, когда задача с высоким приоритетом блокируется в ожидании получения
блокировки, которую удерживает задача с низким приоритетом, в то время как задачи
со средним приоритетом постоянно вытесняют задачу с низким приоритетом с ЦП. В
следствии этого, выполнение задачи с низким приоритетом никак не продвигается к
освобождению блокировки, и задача с высоким приоритетом остаётся заблокированной.

Наследование приоритета — это механизм, который решает проблему обратного
приоритета. С его помощью, когда задача с высоким приоритетом блокируется из-за
удержания блокировки задачей с низким приоритетом, приоритет задачи с низким
приоритетом временно повышается до приоритета, имеющегося у заблокированной
задачи, и поэтому не происходит вытеснения задачами с средним приоритетом, что
способствует ускорению освобождения блокировки. Чтобы это работало, наследование
приоритета должно быть транзитивным, то есть если задача с высоким приоритетом
заблокирована, из-за удержания блокировки задачей с низким приоритетом, которая
сама заблокирована из-за удержания блокировки другой задачей со средним
приоритетом (и так далее, по цепочке произвольной длины), то для обеих этих задач
(или, шире, всех задач в заблокированной цепочке) повышается приоритет, который
равен приоритету задачи с высоким приоритетом.

Со стороны пользовательского пространства фьютекс является PI из-за следования
соглашениям (описанных далее) между пользовательским пространством и ядром о
* Если блокировка получена, то значение слова фьютекса должно быть равно ID нити
(TID; смотрите gettid(2)), которой оно принадлежит.

* Если блокировка получена и есть претендующие на неё нити, то в значении слова
фьютекса должен быть установлен бит FUTEX_WAITERS; иначе говоря, это значение
равно:

FUTEX_WAITERS | TID

(заметим, что некорректное слово PI-фьютекса не имеет владельца и
FUTEX_WAITERS)

С этой действующей политикой приложение пространства пользователя может получить
свободную блокировку или освободить блокировку с помощью атомарных инструкций,
выполняемых в пользовательском режиме (например, операцией сравнение-и-обмен
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-фьютексами должны использовать
попарно и учитывать некоторые дополнительные требования:

* Парой к операциям FUTEX_LOCK_PI и FUTEX_TRYLOCK_PI является FUTEX_UNLOCK_PI.
Операция FUTEX_UNLOCK_PI должна применяться только к фьютексам, принадлежащим
вызывающей нити, определённой значением политики, или же возникнет ошибка
EPERM.
Данная операция используется после попытки получить блокировку через
атомарную инструкцию в пространстве пользователя, которая завершилась с
ошибкой из-за того, что слово фьютекса не равно нулю — содержит value—
specifically, because it contained the TID (PID в этом пространстве имён)
владельца блокировки.

Операция проверяет значение слова фьютекса по адресу uaddr. Если значение
равно 0, то ядро пытается атомарно изменить слово фьютекса на TID
вызывающего. Если слово фьютекса не равно нулю, то ядро атомарно
устанавливает бит FUTEX_WAITERS, который указывает владельцу фьютекса, что
он не может разблокировать фьютекс в пространстве пользователя атомарным
способом посредством установки значения фьюетекса в 0. После этого ядро:

1. Пытается найти нить-владельца по TID.

2. Создаёт или повторно использует состояние ядра от имени владельца (если
это первый ожидающий, то для этого фьютекса не состояния ядра, поэтому
состояние ядра создаётся блокировкой RT-мьютекса и владелец фьютекса
становится владельцем RT-мьютекса. Если ожидающие уже есть, то
используется имеющееся состояние).

3. Присоединяет ожидающего к фьютексу (т. е., ожидающий ставится в очередь
списка ожидающих на основе RT-мьютекса).

Если есть более одного ожидающего, то перестановка ожидающего в очередь
выполняется в порядке убывания приоритета (упорядочивание по приоритету
описано в разделе об алгоритмах планирования SCHED_DEADLINE, SCHED_FIFO и
SCHED_RR в sched(7)). Владелец наследует от ожидающего пропускную
способность ЦП (если ожидающий работает по алгоритму планирования
SCHED_DEADLINE) или приоритет (если ожидающий работает по алгоритму
планирования SCHED_RR или SCHED_FIFO). При обнаружении вложенности
блокировки и клинча такое наследование распространяется по всей цепочке
блокировки.

В аргументе timeout задаётся время ожидания захвата блокировки. Если
timeout равно NULL, то структура, на которую он указывает, определяет
абсолютное время ожидания, отсчитываемое по часам CLOCK_REALTIME. Если
timeout равно NULL, то операция может быть в блокировке неопределённо
долго.

Аргументы uaddr2, val и val3 игнорируются.

FUTEX_TRYLOCK_PI (начиная с Linux 2.6.18)
Эта операция пытается получить блокировку по адресу uaddr. Она вызывается,
когда не удалось выполнить атомарное получение из пользовательского
пространства, так как слово фьютекса не равно 0.

Так как ядро имеет больший доступ к информации о состоянии, чем
пользовательское пространство, получение блокировки из ядра может
осуществиться, в случаях когда слово фьютекса (т. е., информация о
состоянии доступна из пользовательского пространства) устарело
(FUTEX_WAITERS и/или FUTEX_OWNER_DIED). Это может случиться, если владелец
фьютекса неожиданно завершился. Пользовательское пространство не может
учесть это событие не получив состязательности, но ядро может решить данную
проблему и получить блокировку.

Аргументы uaddr2, val, timeout и val3 игнорируются.

FUTEX_CMP_REQUEUE_PI (начиная с Linux 2.6.31)
Данная операция является PI-аналогом операции FUTEX_CMP_REQUEUE. Она
перестанавливает ожидающих, заблокированных с помощью FUTEX_WAIT_REQUEUE_PI
для uaddr, из очереди не PI-фьютекса источника (uaddr) в очередь
PI-фьютекса назначения (uaddr2).

Как и FUTEX_CMP_REQUEUE, эта операция пробуждает не более val ожидающих,
которые ждут фьютекса по адресу uaddr. Однако у FUTEX_CMP_REQUEUE_PI
значение val должно быть равно 1 (чтобы избежать «нашествия орды»).
Оставшиеся ожидающие удаляются из очереди ожидания фьютекса-источника по
адресу uaddr и добавляются в очередь ожидания фьютекса-назначения по адресу
uaddr2.

Аргументы val2 и val3 служат тем же целям, что и в FUTEX_CMP_REQUEUE.

FUTEX_WAIT_REQUEUE_PI (начиная с Linux 2.6.31)
Ждать не PI-фьютекса по адресу uaddr и, потенциально быть перемещённым в
очередь (при операции FUTEX_CMP_REQUEUE_PI из другой задачи) PI-фьютекса по
адресу uaddr2. Операция ожидания на адресе uaddr такая же как для
FUTEX_WAIT.

Ожидающий может быть удалён из ожидающих на адресе uaddr перемещения в
очередь у uaddr2 при операции FUTEX_WAKE из другой задачи. В этом случае
операция FUTEX_WAIT_REQUEUE_PI завершается с ошибкой EAGAIN.

Если значение timeout не равно NULL, то структура, на которую он указывает,
определяет абсолютное время ожидания. Если timeout равно NULL, то операция
блокируется бессрочно.

Аргумент val3 игнорируется.

Операции FUTEX_WAIT_REQUEUE_PI и FUTEX_CMP_REQUEUE_PI добавлены для
довольно узкого варианта применения — поддержки переменных условия нитей
POSIX с наследованием приоритета. Идея в том, что эти операции всегда
должны использоваться попарно, для поддержания синхронизации между
пользовательским пространством и ядром. То есть в операции
FUTEX_WAIT_REQUEUE_PI приложение пользовательского пространства заранее
задаёт назначение для перемещения в очередь, которое проводится операцией
FUTEX_CMP_REQUEUE_PI.

ВОЗВРАЩАЕМОЕ ЗНАЧЕНИЕ

В случае ошибки (предполагается, что futex() был вызван через syscall(2)), все
операции возвращают -1 и присваивают errno номер ошибки.

При успешном выполнении возвращаемое значение зависит от операции:

FUTEX_WAIT
Значение 0 возвращается, если вызывающий был разбужен. Заметим, что
пробуждение также может быть вызвано часто используемыми вариантами
использования фьютексов в не связанном коде, которое случается, если память
под слово фьютекса использовалась ранее (например, при типичной реализации
фьютексов на основе мьютексов Pthreads это может возникать при определённых
условиях). Поэтому вызывающий всегда должен консервативно предполагать, что
возвращаемое значение 0 может означать побочное пробуждение (spurious
wake-up), и учитывать значение слово фьютекса (т. е. схема с синхронизацией
пользовательского пространства) при принятии решения нужна дальнейшее
Возвращается количество разбуженных ожидающих.

FUTEX_CMP_REQUEUE
Возвращается общее количество ожидающих, которые будятся или перемещаются в
очередь фьютекса, у которого слово фьютекса задано по адресу uaddr2. Если
это значение больше чем val, то разница это количество ожидающих,
перемещённых в очередь фьютекса, у которого слово фьютекса задано по адресу
uaddr2.

FUTEX_WAKE_OP
Возвращается общее количество разбуженных ожидающих. Это сумма разбуженных
ожидающих у двух фьютексов для слов фьютексов по адресам uaddr и uaddr2.

FUTEX_WAIT_BITSET
Возвращается 0, если вызывающий был разбужен. Смотрите в описании
FUTEX_WAIT, как это правильно учитывать на практике.

FUTEX_WAKE_BITSET
Возвращается количество разбуженных ожидающих.

FUTEX_LOCK_PI
Возвращается 0, если фьютекс был успешно заблокирован.

FUTEX_TRYLOCK_PI
Возвращается 0, если фьютекс был успешно заблокирован.

FUTEX_UNLOCK_PI
Возвращается 0, если фьютекс был успешно разблокирован.

FUTEX_CMP_REQUEUE_PI
Возвращается общее количество ожидающих, которые будятся или перемещаются в
очередь фьютекса, у которого слово фьютекса задано по адресу uaddr2. Если
это значение больше чем val, то разница это количество ожидающих,
перемещённых в очередь фьютекса, у которого слово фьютекса задано по адресу
uaddr2.

FUTEX_WAIT_REQUEUE_PI
Возвращается 0, если вызывающий был успешно перемещён в очередь фьютекса со
словом фьютекса по адресу uaddr2.

ОШИБКИ

EACCES Нет доступа на чтение памяти слова фьютекса.

EAGAIN (FUTEX_WAIT, FUTEX_WAIT_BITSET, FUTEX_WAIT_REQUEUE_PI) Значение, на которое
указывает uaddr, не было равно ожидаемому значению val на момент вызова.

Замечание: в Linux символические имена EAGAIN и EWOULDBLOCK (оба есть в
разных частях кода фьютекса ядра) имеют одинаковое значение.

EAGAIN (FUTEX_CMP_REQUEUE, FUTEX_CMP_REQUEUE_PI) Значение, на которое указывает
uaddr, не равно ожидаемому значению val3.

EAGAIN (FUTEX_LOCK_PI, FUTEX_TRYLOCK_PI, FUTEX_CMP_REQUEUE_PI) ID нити владельца
фьютекса по адресу uaddr (для FUTEX_CMP_REQUEUE_PI — uaddr2) вскоре
закончит работу, но не выполнил очистку внутреннего состояния. Попробуйте
ещё раз.

EFAULT Требуемый аргумент указателя (т. е., uaddr, uaddr2 или timeout) не
указывает на допустимый адрес пользовательского пространства.

EINTR Операция FUTEX_WAIT или FUTEX_WAIT_BITSET была прервана сигналом (смотрите
signal(7)). В ядрах до версии Linux 2.6.22 эта ошибка также возвращалась
при побочном пробуждении; начиная с Linux 2.6.22 этого больше не
происходит.

EINVAL Операция в futex_op является одной из тех, что используют ожидание
(timeout), но значение аргумента timeout некорректно (tv_sec меньше нуля
или tv_nsec больше 1000000000).

EINVAL Операция, указанная в futex_op, использует один или оба указателя uaddr и
uaddr2, но один из них не указывает на корректный объект, то есть адрес не
выровнен по четырёх байтовой границе.

EINVAL (FUTEX_WAIT_BITSET, FUTEX_WAKE_BITSET) Битовая маска, указанная в val3,
равна нулю.

EINVAL (FUTEX_CMP_REQUEUE_PI) Значение uaddr равно uaddr2 (т. е., предпринята
попытка выполнить перемещение в одну и ту же очередь).

EINVAL (FUTEX_FD) В val указан некорректный номер сигнала.

EINVAL (FUTEX_WAKE, FUTEX_WAKE_OP, FUTEX_WAKE_BITSET, FUTEX_REQUEUE,
FUTEX_CMP_REQUEUE) Ядро обнаружило противоречие между состояние в
пользовательском пространстве по адресу uaddr и состоянием в ядре, то есть
обнаружило, что ожидающий ждёт посредством операции FUTEX_LOCK_PI на адресе
uaddr.

EINVAL (FUTEX_LOCK_PI, FUTEX_TRYLOCK_PI, FUTEX_UNLOCK_PI) Ядро обнаружило
противоречие между состояние в пользовательском пространстве по адресу
uaddr и состоянием в ядре. Это указывает на поврежденное значение состояния
или что ядро обнаружило ожидающего на адресе uaddr, который делает это
посредством операции FUTEX_WAIT или FUTEX_WAIT_BITSET.

EINVAL (FUTEX_CMP_REQUEUE_PI) Ядро обнаружило противоречие между состояние в
пользовательском пространстве по адресу uaddr2 и состоянием в ядре, то есть
обнаружило, что ожидающий ждёт посредством операции FUTEX_WAIT или
FUTEX_WAIT_BITSET на адресе uaddr2.

EINVAL (FUTEX_CMP_REQUEUE_PI) Ядро обнаружило противоречие между состояние в
пользовательском пространстве по адресу uaddr и состоянием в ядре, то есть
обнаружило, что ожидающий ждёт посредством операции FUTEX_WAIT или
FUTEX_WAIT_BITESET на адресе uaddr.

EINVAL (FUTEX_CMP_REQUEUE_PI) Ядро обнаружило противоречие между состояние в
пользовательском пространстве по адресу uaddr и состоянием в ядре, то есть
обнаружило, что ожидающий ждёт посредством операции FUTEX_LOCK_PI на адресе
uaddr (вместо FUTEX_WAIT_REQUEUE_PI).

EINVAL (FUTEX_CMP_REQUEUE_PI) Предпринята попытка выполнить перемещение ожидающего
на фьютекс, отличный от указанного в соответствующем вызове
FUTEX_WAIT_REQUEUE_PI для этого вызывающего.

EINVAL (FUTEX_CMP_REQUEUE_PI) Значение аргумента val не равно 1.


ENOSYS В futex_op был указан параметр FUTEX_CLOCK_REALTIME, но сопутствующая
операция не равна FUTEX_WAIT, FUTEX_WAIT_BITSET или FUTEX_WAIT_REQUEUE_PI.

ENOSYS (FUTEX_LOCK_PI, FUTEX_TRYLOCK_PI, FUTEX_UNLOCK_PI, FUTEX_CMP_REQUEUE_PI,
FUTEX_WAIT_REQUEUE_PI) Проверка во время выполнения обнаружила, что
операция недоступна. Операции с PI-фьютексами реализованы не на всех
архитектурах и не поддерживаются на некоторых моделях ЦП.

EPERM (FUTEX_LOCK_PI, FUTEX_TRYLOCK_PI, FUTEX_CMP_REQUEUE_PI) Вызывающему
запрещено самостоятельно присоединяться к фьютексу по адресу uaddr (для
FUTEX_CMP_REQUEUE_PI: фьютексу по адресу uaddr2) (это может быть вызвано
повреждением состояния в пользовательском пространстве).

EPERM (FUTEX_UNLOCK_PI) Вызывающему не принадлежит блокировка, представленная в
слове фьютекса.

ESRCH (FUTEX_LOCK_PI, FUTEX_TRYLOCK_PI, FUTEX_CMP_REQUEUE_PI) Идентификатор нити
из слова фьютекса по адресу uaddr не существует.

ESRCH (FUTEX_CMP_REQUEUE_PI) Идентификатор нити из слова фьютекса по адресу
uaddr2 не существует.

ETIMEDOUT
Операция в futex_op использует время ожидания, указанное в timeout, и время
истекло до завершения операции.

ВЕРСИИ

Фьютексы появились в стабильном ядре 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

Исходный код программы

/* futex_demo.c

Использование: futex_demo [nloops]
(по умолчанию: 5)

Продемонстрировано использование фьютексов в программе, где родитель
и потомок используют пару фьютексов, расположенных в общем анонимном
отображении, для синхронизации доступа к общему ресурсу: терминалу.
Каждый из процессов записывает num-loops на терминал и использует
протокол синхронизации, который гарантирует, что они выполняют запись
поочерёдно.
*/
#define _GNU_SOURCE
#include <stdio.h>
#include <errno.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;

/* __sync_bool_compare_and_swap(ptr, oldval, newval) — встроенная
функция gcc. Она атомарно выполняет эквивалент кода:

if (*ptr == oldval)
*ptr = newval;

Она возвращает true, если тест вернул true и было обновлено *ptr.
Вместо неё здесь можно было бы использовать эквивалентные
атомарные инструкции процессора. Подробней смотрите в
руководстве по GCC. */

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;

/* __sync_bool_compare_and_swap() описана в комментариях выше */

if (__sync_bool_compare_and_swap(futexp, 0, 1)) {

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)
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)

Файлы из дерева исходного кода ядра:

* Documentation/pi-futex.txt

* Documentation/futex-requeue-pi.txt

* Documentation/locking/rt-mutex.txt

* Documentation/locking/rt-mutex-design.txt

* Documentation/robust-futex-ABI.txt

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/⟩