futex

ИМЯ

futex - быстрая блокировка в пользовательском пространстве

LIBRARY

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

This option bit can be employed only with the FUTEX_WAIT_BITSET, FUTEX_WAIT_REQUEUE_PI, (since Linux 4.5) FUTEX_WAIT, and (since Linux 5.14) FUTEX_LOCK_PI2 operations.

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

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

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

FUTEX_WAIT (начиная с Linux 2.6.0)

Эта операция проверяет, что значение слова фьютекса, на которое указывает адрес uaddr по прежнему содержит ожидаемое значение val и если это так, то засыпает, ожидая операции FUTEX_WAKE для этого слова фьютекса. Загрузка значения слова фьютекса является атомарным доступом к памяти (т. е., используются атомарные машинные инструкции соответствующей архитектуры). Эта загрузка, сравнение с ожидаемым значением и запуск сна выполняются атомарно и целиком упорядочены относительно других фьютекс-операций с этим словом фьютекса. Если нить начала засыпать, то считается что она — ожидающий этого слова фьютекса. Если значение фьютекса не совпадает с val, то вызов немедленно завершается с ошибкой 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. Если нет, то операция завершается с ошибкой EAGAIN. В противном случае, операция пробуждает не более val ожидающих, которые ждут фьютекс по адресу uaddr. Если существует более val ожидающих, то оставшиеся ожидающие удаляются из очереди ожидания фьютекса-источника по адресу uaddr и добавляются в очередь ожидания фьютекса-назначения по адресу uaddr2. В аргументе val2 задаётся верхний предел количества ожидающих, которые перемещаются в очередь фьютекса по адресу uaddr2.

Загрузка из 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 эквивалентна выполнению следующего кода, при чём, атомарно и полностью упорядочено в соответствии с другими фьютекс-операциями, выполняемыми над двумя указанными словами фьютекса:

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

Иначе говоря, FUTEX_WAKE_OP делает следующее:

Операция и сравнение, которое будет выполнено, кодируется в битах аргумента 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)

Эта операция подобна FUTEX_WAIT, за исключением того, что val3 используется для передачи 32-битной маски в ядро. Данная битовая маска, в которой должен быть установлен хотя бы один бит, хранится в ядре во внутреннем состоянии ожидающего. Подробности смотрите в описании FUTEX_WAKE_BITSET.

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

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

•

Если блокировка не получена, то значение слова фьютекса должно быть равно 0.

•

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

•

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

FUTEX_WAITERS | TID
    

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

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

•

Парой к операциям FUTEX_LOCK_PI, FUTEX_LOCK_PI2 и FUTEX_TRYLOCK_PI является FUTEX_UNLOCK_PI. Операция FUTEX_UNLOCK_PI должна применяться только к фьютексам, принадлежащим вызывающей нити, определённой значением политики, или же возникнет ошибка EPERM.

•

Парой к операции FUTEX_WAIT_REQUEUE_PI является FUTEX_CMP_REQUEUE_PI. Она должна применяться для перехода с не PI-фьютекса к PI-фьютексу (или возникает ошибка EINVAL). Также, val (количество разбуживаемых ожидающих) должно равняться 1 (или возникает ошибка EINVAL).

Операции с PI-фьютексами:

FUTEX_LOCK_PI (начиная с Linux 2.6.18)

This operation is used after an attempt to acquire the lock via an atomic user-mode instruction failed because the futex word has a nonzero value—specifically, because it contained the (PID-namespace-specific) TID of the lock owner.

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

Если есть более одного ожидающего, то перестановка ожидающего в очередь выполняется в порядке убывания приоритета (упорядочивание по приоритету описано в разделе об алгоритмах планирования 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_LOCK_PI2 (начиная с Linux 5.14)

This operation is the same as FUTEX_LOCK_PI, except that the clock against which timeout is measured is selectable. By default, the (absolute) timeout specified in timeout is measured against the CLOCK_MONOTONIC clock, but if the FUTEX_CLOCK_REALTIME flag is specified in futex_op, then the timeout is measured against the CLOCK_REALTIME clock.

FUTEX_TRYLOCK_PI (начиная с Linux 2.6.18)

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

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

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

FUTEX_UNLOCK_PI (начиная с Linux 2.6.18)

This operation wakes the top priority waiter that is waiting in FUTEX_LOCK_PI or FUTEX_LOCK_PI2 on the futex address provided by the uaddr argument.

Операция вызывается, когда значение по адресу uaddr пользовательского пространства невозможно изменить атомарно с TID (владельца) на 0.

Аргументы 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.

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

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. При успешном выполнении возвращаемое значение зависит от операции:

FUTEX_WAIT

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

FUTEX_WAKE

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

FUTEX_FD

Возвращается новый файловый дескриптор, связанный с фьютексом.

FUTEX_REQUEUE

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

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_LOCK_PI2

Возвращается 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_LOCK_PI2, FUTEX_TRYLOCK_PI, FUTEX_CMP_REQUEUE_PI) ID нити владельца фьютекса по адресу uaddr (для FUTEX_CMP_REQUEUE_PI — uaddr2) вскоре закончит работу, но не выполнил очистку внутреннего состояния. Попробуйте ещё раз.

EDEADLK

(FUTEX_LOCK_PI, FUTEX_LOCK_PI2, FUTEX_TRYLOCK_PI, FUTEX_CMP_REQUEUE_PI) Слово фьютекса по адресу uaddr уже заблокировано вызывающим.

EDEADLK

(FUTEX_CMP_REQUEUE_PI) Во время перемещения в другую очередь ожидающего PI-фьютекса со словом фьютекса по адресу uaddr2 ядро обнаружило тупиковую блокировку (deadlock).

EFAULT

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

EINTR

A FUTEX_WAIT or FUTEX_WAIT_BITSET operation was interrupted by a signal (see signal(7)). Before Linux 2.6.22, this error could also be returned for a spurious wakeup; since Linux 2.6.22, this no longer happens.

EINVAL

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

EINVAL

The operation specified in futex_op employs one or both of the pointers uaddr and uaddr2, but one of these does not point to a valid object—that is, the address is not four-byte-aligned.

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) The kernel detected an inconsistency between the user-space state at uaddr and the kernel state—that is, it detected a waiter which waits in FUTEX_LOCK_PI or FUTEX_LOCK_PI2 on uaddr.

EINVAL

(FUTEX_LOCK_PI, FUTEX_LOCK_PI2, 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_BITSET на адресе uaddr.

EINVAL

(FUTEX_CMP_REQUEUE_PI) The kernel detected an inconsistency between the user-space state at uaddr and the kernel state; that is, the kernel detected a waiter which waits on uaddr via FUTEX_LOCK_PI or FUTEX_LOCK_PI2 (instead of FUTEX_WAIT_REQUEUE_PI).

EINVAL

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

EINVAL

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

EINVAL

Неверный аргумент.

ENFILE

(FUTEX_FD) Достигнуто ограничение на общее количество открытых файлов в системе.

ENOMEM

(FUTEX_LOCK_PI, FUTEX_LOCK_PI2, FUTEX_TRYLOCK_PI, FUTEX_CMP_REQUEUE_PI) Ядро не может выделить память для хранения информации о состоянии.

ENOSYS

В futex_op задана неверная операция.

ENOSYS

The FUTEX_CLOCK_REALTIME option was specified in futex_op, but the accompanying operation was neither FUTEX_WAIT, FUTEX_WAIT_BITSET, FUTEX_WAIT_REQUEUE_PI, nor FUTEX_LOCK_PI2.

ENOSYS

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

EPERM

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

EPERM

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

ESRCH

(FUTEX_LOCK_PI, FUTEX_LOCK_PI2, 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.

ЗАМЕЧАНИЯ

На основе фьютексов было реализовано несколько высокоуровневых программных абстракций, например, семафоры 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) Файлы из дерева исходного кода ядра:

•

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. 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 <[email protected]>, Dmitry Bolkhovskikh <[email protected]>, Yuri Kozlov <[email protected]> и Иван Павлов <[email protected]> Этот перевод является бесплатной документацией; прочитайте Стандартную общественную лицензию GNU версии 3 или более позднюю, чтобы узнать об условиях авторского права. Мы не несем НИКАКОЙ ОТВЕТСТВЕННОСТИ. Если вы обнаружите ошибки в переводе этой страницы руководства, пожалуйста, отправьте электронное письмо на [email protected]