---

Статья является любительским переводом статьи Futexes Are Tricky Ульриха Дреппера.
The given document is a translation of the article Futexes Are Tricky by Ulrich Drepper to the Russian language.

Первым описанием фьютексов была публикация Fuss, Futexes and Furwocks: Fast User Level Locking in Linux, написанная Franke, Russel и Kirkwood и представленная во время проведения Ottawa Linux Symposium в 2002 году. Данный документ описывает основу работы с фьютексами. С того времени функциональность ядра была существенно расширена и улучшена. Самым большим упущением является отсутствие хорошего руководства о правильном использовании фьютексов. Rusty Rassel распространяет пакет примеров (ftp://ftp.kernel.org/pub/linux/kernel/people/rusty), но к сожалению этот код недостаточно хорош и плохо документирован.

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

long sys_futex (void *addr1, int op, int val1, struct timespec *timeout, void *addr2, int val3);

Данный прототип не является полностью корректным, но на данный момент это не имеет большого значения.
Фьютекс представляет собой целочисленную переменную типа int, на которую указывает addr1. Переменная имеет размер 4 байта как 32-битных, так и 64-битных платформах. Значение переменной полностью контролируется приложением. Отсутствие значения (No value) является особым случаем 1).
Любой адрес памяти (исключая адреса DMA и прочие подобные вещи) может быть использован в качестве фьютекса. Единственным требованием является выравнивание адреса фьютекса на границу sizeof(int).
Ядро управляет текущим физическим адресом фьютекса. Т.е, если два процесса определяют фьютекс в общей области памяти, они определяют общий фьютекс. Это позволяет использовать фьютекс, как примитив синхронизации между процессами.
С фьютексом можно производить различные действия, указанные через передаваемый op параметр:

FUTEX_WAIT. Данный вызов переводит поток в режим ожидания до наступления события. В случае успешного пробуждения (FUTEX_WAKE) системный вызов возвращает нулевое значение.
Перед тем, как поток перейдет в состояние ожидания, происходит проверка значения фьютекса. Если его значение отличается от передаваемого параметра val1, вызов сразу завершается с результатом EWOULDBLOCK.
Если указан параметр timeout, то поток перейдет в состояние ожидания только на указанное время. Структура timespec задает количество секунд, в течении которых поток будет в этом состоянии. По истечении времени, если не пришло сообщения о пробуждении (FUTEX_WAKE), возвращается результат ETIMEDOUT.
Если поток во время ожидания получит сигнал, вызов завершится с результатом EINTR.
Другие параметры в данном вызове не используется.

FUTEX_WAKE. Данный вызов позволяет послать сигнал пробуждения одному или более потокам. Используются только параметры addr1, op и val1. Значение параметра val1 определяет количество потоков, которым необходимо послать сигнал. Поскольку тип передаваемого значения соответствует типу int, то для пробуждения всех потоков лучше всего использовать значение INT_MAX.
Обычно для передачи используются значения 1 и INT_MAX. Использование других значений не представляет большого интереса, поскольку пользователю не возможно узнать, какие именно потоки перешли в рабочее состояние. И даже, если сделать это возможным для конкретной ситуации, показанная особенность данного вызова может быть изменена в будущем. Передаваемые значения меньше или равные 0, являются некорректными.
На текущий момент ядро не учитывает приоритеты ожидающих потоков и фьютексы не могут использоваться для обеспечения реакций реального времени. Возможно это появится в будущих реализациях.
Будет ли передано управление разбуженному потоку сразу, или поток, пробуждающий остальных, будет продолжать выполнение - это особенность реализации. На многопроцессорных машинах особенно важно, чтобы проснувшийся поток вернулся на уровень пользователя до завершения потока, который вывел его из состояния ожидания. Это утверждение будет объяснено немного позже.
Данный вызов возвращает число разбуженных потоков.

FUTEX_WAKE_OP. Некоторые запросы требуют обработки нескольких фьютексов одновременно. Одним из таких примеров является условная переменная, которая для реализации требует использование внутренней блокировки и отдельную очередь ожидания. Внутренняя блокировка устанавливается перед каждым вызовом, но это может привести к большому числу переключений контекста. Представьте, что поток А пробудил поток В, ожидающий фьютекс. Каждый раз для обработки фьютекса необходимо использовать внутреннюю блокировку. Если выполнение потока В запланировано перед тем, как поток А освободит внутреннюю блокировку, он немедленно вернется в состояние ожидания и в данном случае это поведение невозможно изменить с помощью вызова FUTEX_CMP_REQUEUE, описанного ниже.
Для обхода данной, а также похожих проблем, была разработан вызов FUTEX_WAKE_OP. Он является аналогом FUTEX_WAKE, но результат пробуждения зависит от выполнения заданного условия после проведения операции над указанным адресом памяти. На языке C данная операция может быть описана так

int oldval = *(int *) addr2;
*(int *)addr2 = oldval OP OPARG;
futex_wake(addr1, val1);
if (oldval CMP CMPARG) futex_wake(addr2, val2);

где OP, OPARG, CMP и CMPARG закодированы внутри параметра val3 с использованием

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

Код выглядит странно, но он позволяет выполнять более эффективную обработку фьютекса, чем в других запросах (FUTEX_WAKE и FUTEX_CMP_REQUEUE).

Операция OP кодируется по следующим правилам				Сравнение CMP кодируется по следующим правилам
Name	Value	Operation		Name	Value	Operation
FUTEX_OP_SET	0	*addr2 = OPARG		FUTEX_OP_CMP_EQ	0	oldval = CMPARG
FUTEX_OP_ADD	1	*addr2 += OPARG		FUTEX_OP_CMP_NE	1	oldval ! = CMPARG
FUTEX_OP_OR	2	*addr2 |= OPARG		FUTEX_OP_CMP_LT	2	oldval < CMPARG
FUTEX_OP_ANDN	3	*addr2 &= OPARG		FUTEX_OP_CMP_LE	3	oldval < = CMPARG
FUTEX_OP_XOR	4	*addr2 ^= OPARG		FUTEX_OP_CMP_GT	4	oldval > CMPARG
				FUTEX_OP_CMP_GE	5	oldval > = CMPARG

FUTEX_CMP_REQUEUE. Данный вызов является надстройкой над вызовом FUTEX_WAKE. Он позволяет разбудить заданное количество ожидающих потоков. В дополнение, он обеспечивает следующую функциональность : если количество ожидающих потоков больше разбуженных, то они удаляются из очереди фьютекса, находящегося по адресу addr1 и добавляются к фьютексу, находящемуся по адресу addr2. В данном случае параметр timeout используется не так, как обычно. Числовое значение указателя преобразуется в целое число и используется как значение val2. Выполнение вызова начинается, если val3 является значением фьютекса, на который указывает адрес addr1. Если это условие не выполняется, вызов возвращает значение EAGAIN.
Потоки, перемещенные в очередь другого фьютекса, далее обрабатываются также, как любые другие потоки, ожидающие фьютекс. Они могут быть разбужены как по отдельности, так и все вместе. Этим потокам не передается никаких данных о том, что они были переставлены в другую очередь.
Для val1 обычно используются значения 0 или 1. Использование INT_MAX фактически означает вызов FUTEX_WAKE. Значение val2 обычно равно 1 или INT_MAX. Использование значения 0 не имеет смысла и приводит вызов к вызову FUTEX_WAIT.
Возвращаемое значение указывает сколько потоков проснулось или было переставлено в очередь второго фьютекса. Если возвращаемое значение больше val1, это означает что часть потоков была поставлена в другую очередь.

FUTEX_REQUEUE. Данный вызов является неиспользуемым более предшественником вызова FUTEX_CMP_REQUEUE. Он оставлен только для совместимости. Его основное отличие состоит в том, что он не использует val3 параметр, и поэтому изменения фьютеса при перемещении в очередь назначения не могут быть обнаружены, что может привести в блокировкам потоков.

FUTEX_FD. Семантика этого вызова отличается от остальных. Над фьютексом не производится никаких действий. Вместо этого, ядро создает файловый дескриптор, ассоциированный с указанным фьютексом. Также становится возможным запросить асинхронное уведомление.
Для вызова необходимо передать ядру только addr1 и val1. Если если значение val1 нулевое, вызов возвращает новый файловый дескриптор для фьютекса addr1. Этот дескриптор может быть использован в функциях select, call, или epoll. Как только поток будет разбужен, или им будет получен сигнал, вызов select/poll/epoll вернет управление. Значение поля revents для файлового дескриптора заполняется POLLIN|POLLRDNORM, если кто-либо разбудил ожидающие потоки. Событие пробуждения является edge-triggered.
Если значение val1 не является нулевым, оно должно содержать в себе значение сигнала. Ядро ассоциирует указанный сигнал с возвращаемым дескриптором, чтобы потом использовать его, когда поток, ожидающий фьютекс, проснется.

Из приведенного описания становится понятно, что фундаментальной частью фьютекса является очередь ожидания, которую ядро ассоциирует с ним. Запрос ожидания добавляет поток в очередь, а пробуждения - удаляет из нее. Данные операции выполняются атомарно, более того, проверка фьютекса при вызове FUTEX_WAIT тоже должна быть атомарной. Это означает, что операция ожидания состоит из блокировки фьютекса, проверки текущего значения, добавления, при необходимости, потока в очередь и освобождения блокировки. Пробуждение потоков устанавливает блокировку, пробуждает или переустанавливает очередь потоков перед освобождением блокировки. Очень важно, чтобы данная последовательность выполнения соблюдалась для гарантии, что потоки, которые переходят в состояние ожидания при неизменном значении фьютекса, проснулись, как только значение фьютекса изменится. Внутренние блокировки в устройстве фьютексов позволяют атомарно выполнять данные операции. Дальнейшее описание показывает, как все эти механизмы позволяют создать примитивы синхронизации.

В тексте мы используем созданные интерфейсы, описанные в Appendix A. Реализация этих интерфейсов является платформозависимой. Ни один из этих интерфейсов не является стандартом в настоящее время. Если есть желание их использовать, лучше попробуйте сделать собственную реализацию.

Хитрости с фьютексами. Часть 2
Хитрости с фьютексами. Часть 3
Комментировать


This work is licensed under a Creative Commons Attribution-Noncommercial-Share Alike 3.0 Unported License.