Фьютекс

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

Фьютекс состоит из в пространстве ядра очереди ожидания , которая прикреплена к атомарному целому числу в пространстве пользователя . Несколько процессов или потоков работают с целым числом полностью в пользовательском пространстве (используя атомарные операции , чтобы не мешать друг другу), и прибегают только к относительно дорогостоящим методам. ^{[ нужна ссылка ]} системные вызовы для запроса операций в очереди ожидания (например, для пробуждения ожидающих процессов или для помещения текущего процесса в очередь ожидания). Правильно запрограммированная блокировка на основе фьютекса не будет использовать системные вызовы, за исключением случаев, когда за блокировку возникает конфликт; поскольку большинство операций не требуют арбитража между процессами, в большинстве случаев этого не произойдет.

История

Хубертус Франке ( Исследовательский центр IBM Томаса Дж. Уотсона ), Мэтью Кирквуд, Инго Молнар ( Red Hat ) и Расти Рассел ( Технологический центр IBM Linux ) разработали механизм фьютекса в Linux в 2002 году. ^[1] В том же году состоялось обсуждение предложения сделать фьютексы доступными через файловую систему путем создания специального узла в /dev или /proc. Однако Линус Торвальдс категорически выступил против этой идеи и отверг любые связанные с ней патчи. ^[2]

Затем фьютексы впервые появились в версии 2.5.7 серии статей по разработке ядра Linux; семантика стабилизировалась с версии 2.5.40, а фьютексы стали частью основной ветки ядра Linux с момента выпуска в декабре 2003 года серии стабильных ядер 2.6.x.

Функциональность Futex была реализована в Microsoft Windows начиная с Windows 8 или Windows Server 2012 под названием WaitOnAddress . ^[3]

В 2013 году Microsoft запатентовала технологию фьютекса. ^[4] WaitOnAddress , патент был выдан в 2014 году. ^[5]

В мае 2014 года система CVE объявила об уязвимости, обнаруженной в подсистеме фьютекса ядра Linux, которая позволяла осуществлять атаки типа «отказ в обслуживании» или локальное повышение привилегий. ^[6]^[7]

В мае 2015 года в ядре Linux появилась ошибка взаимоблокировки через Commit b0c29f79ecea , которая приводила к зависанию пользовательских приложений. Ошибка затронула многие корпоративные дистрибутивы Linux, включая ядра 3.x и 4.x, а также Red Hat Enterprise Linux версий 5, 6 и 7, SUSE Linux 12 и Amazon Linux. ^[8]

Фьютексы реализованы в OpenBSD с 2016 года. ^[9]

Механизм фьютекса — одна из основных концепций ядра Zircon. ^[10] в Google Fuchsia операционной системе как минимум с апреля 2018 года. ^[11]

Apple реализовала фьютекс в iOS/iPadOS/tvOS 17.4, macOS 14.4, watchOS 10.4 и VisionOS 1.1. ^[12]

Операции

Фьютексы имеют две основные операции: WAIT и WAKE.

WAIT(addr, val)

Если значение, хранящееся по адресу addr является val, переводит текущий поток в спящий режим.

WAKE(addr, num)

Просыпается num количество потоков, ожидающих по адресу addr.

Для более продвинутого использования существует ряд других операций, наиболее часто используемыми являются CMP_REQUEUE и WAKE_OP, которые оба функционируют как более общие WAKE операции. ^[13]

CMP_REQUEUE(old_addr, new_addr, num_wake, num_move, val)

Если значение, хранящееся по адресу old_addr является val, просыпается num_wake потоки, ожидающие адреса old_addrи ставит в очередь num_move потоки, ожидающие адреса old_addr теперь ждать по адресу new_addr. Это можно использовать, чтобы избежать проблемы с грохотом стада при следовании. ^[14]^[15]

WAKE_OP(addr1, addr2, num1, num2, op, op_arg, cmp, cmp_arg)

буду читать addr2, выполнять op с op_arg на нем и сохраните результат обратно в addr2. Тогда он проснется num1 потоки ждут addr1, и, если ранее прочитанное значение из addr2 спички cmp_arg используя сравнение cmp, проснется num2 потоки ждут addr2. Этот очень гибкий и универсальный механизм пробуждения полезен для реализации многих примитивов синхронизации.

См. также

Ссылки

^ «Суета, фьютексы и фурвоки: быстрая блокировка на уровне пользователя в Linux», Франке, Рассел, Кирквуд. Опубликовано в 2002 году для симпозиума Linux в Оттаве.
^ Торвальдс, Линус. «Асинхронный интерфейс Futex» .
^ «Функция WaitOnAddress» . Проверено 1 ноября 2019 г.
^ «Сравнение WaitOnAddress с фьютексами» . Проверено 9 мая 2024 г.
^ «US8782674B2 Ожидание интерфейса синхронизации адресов» . Проверено 1 ноября 2019 г.
^ CVE-2014-3153
^ «[БЕЗОПАСНОСТЬ] [DSA 2949-1] обновление безопасности Linux» . Lists.debian.org. 05.06.2014 . Проверено 8 июня 2014 г.
^ «Ошибка Linux futex_wait()...» 13 мая 2015 г. Проверено 24 марта 2018 г.
^ Мазурек, Михал. « 'Фьютексы для OpenBSD' — MARC» . marc.info . Проверено 30 апреля 2017 г. .
^ «Концепции ядра циркона» . fuchsia.dev . Проверено 20 октября 2019 г.
^ "zx_futex_wait" . fuchsia.dev . Проверено 20 октября 2019 г.
^ «os_sync_wait_on_address» . Документация разработчика Apple . Проверено 14 марта 2024 г.
^ Futexes Are Tricky Ульрих Дреппер (Red Hat, v1.6, 2011)
^ Справочная страница Linux futex(2), раздел FUTEX_CMP_REQUEUE
^ Документация по Циркону zx_futex_requeue

Внешние ссылки

futex(2) - системный вызов futex()
futex(7) - семантика и использование фьютексов
Хубертус Франке, Расти Рассел, Мэттью Кирквуд. Суета, фьютексы и фурвоки: быстрая блокировка на уровне пользователя в Linux , Симпозиум Linux в Оттаве , 2002 г.
Дреппер, Ульрих (2011). «Фьютексы сложны» (PDF) . 1.6. Красная шляпа.
Берт Хьюберт (2004). Неофициальные справочные страницы Futex
Инго Молнар. « Надежные фьютексы », Документация ядра Linux
« Фьютексы приоритетного наследования », Документация ядра Linux

[1] «Суета, фьютексы и фурвоки: быстрая блокировка на уровне пользователя в Linux», Франке, Рассел, Кирквуд. Опубликовано в 2002 году для симпозиума Linux в Оттаве.

[2] Торвальдс, Линус. «Асинхронный интерфейс Futex» .

[3] «Функция WaitOnAddress» . Проверено 1 ноября 2019 г.

[4] «Сравнение WaitOnAddress с фьютексами» . Проверено 9 мая 2024 г.

[5] «US8782674B2 Ожидание интерфейса синхронизации адресов» . Проверено 1 ноября 2019 г.

[6] CVE-2014-3153

[7] «[БЕЗОПАСНОСТЬ] [DSA 2949-1] обновление безопасности Linux» . Lists.debian.org. 05.06.2014 . Проверено 8 июня 2014 г.

[8] «Ошибка Linux futex_wait()...» 13 мая 2015 г. Проверено 24 марта 2018 г.

[9] Мазурек, Михал. « 'Фьютексы для OpenBSD' — MARC» . marc.info . Проверено 30 апреля 2017 г. .

[10] «Концепции ядра циркона» . fuchsia.dev . Проверено 20 октября 2019 г.

[11] "zx_futex_wait" . fuchsia.dev . Проверено 20 октября 2019 г.

[12] «os_sync_wait_on_address» . Документация разработчика Apple . Проверено 14 марта 2024 г.

[Ulrich_Drepper-13] Futexes Are Tricky Ульрих Дреппер (Red Hat, v1.6, 2011)

[14] Справочная страница Linux futex(2), раздел FUTEX_CMP_REQUEUE

[15] Документация по Циркону zx_futex_requeue

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

[14]

[15]