Состояние гонки

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

Например, двухвходовый логический элемент И с такой логикой:

$${\displaystyle {\text{output}}=A\wedge {\overline {A}}}$$

${\displaystyle A}$

${\displaystyle \neg A}$

${\displaystyle A\wedge {\overline {A}}\neq 1}$

${\displaystyle A}$

${\displaystyle A}$

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

Критическое состояние гонки возникает, когда порядок изменения внутренних переменных определяет конечное состояние автомата.

Некритическое состояние гонки — ситуация, когда порядок изменения внутренних переменных не влияет на конечное состояние автомата.

Статическое состояние гонки — возникает при объединении сигнала и его комплемента.

Динамическое состояние гонки — возникает, когда в результате работы схемы происходит несколько переключений вместо одного из-за взаимодействия элементов; устраняется использованием не более двух уровней схемной логики.

Существенное состояние гонки — наблюдается при двойном изменении входного сигнала менее чем за полный период обратной связи; для устранения иногда применяют индуктивные элементы задержки для увеличения длительности входного сигнала.

Методы проектирования, такие как использование карт Карно, помогают конструктору выявлять и устранять состояния гонки на этапе разработки. Для устранения некоторых видов состояний гонки может быть введена логическая избыточность.

Помимо этих проблем, отдельные компоненты логических схем могут входить в метастабильные состояния, создавая дополнительные трудности для разработчиков.

Состояние гонки возникает в программном обеспечении, когда программа имеет несколько параллельно исполняющихся блоков кода, и ожидается, что они завершатся в определённом порядке. Если блоки кода завершаются в ином, неожиданном порядке, возможны ошибки из-за необработанного поведения. Состояние гонки может также проявиться при одновременной работе двух программ, приводя к проблемам с безопасностью.

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

Гонка данных (англ. data race) — особый тип состояния гонки. Она имеет важное значение для формальных моделей памяти. Например, модели памяти стандартов C11 и C++11 определяют, что программы C или C++, содержащие гонку данных, имеют неопределённое поведение^[3][4].

Состояния гонки может быть сложно воспроизвести и отлаживать, так как их проявление нелинейно и зависит от относительных задержек между потоками. Проблемы могут исчезать при запуске в режиме отладки, при добавлении ведения журнала или при подключении отладчика. Ошибка, исчезающая подобным образом, известна как "гейзенбаг". Поэтому предпочтительнее предотвращать состояния гонки на этапе проектирования ПО.

Пусть два потока по очереди увеличивают глобальную целочисленную переменную на 1. Идеальный порядок операций:

В этом случае итоговое значение — 2, что ожидаемо. Однако если оба потока работают одновременно без синхронизации (через семафоры), возможна другая последовательность:

В результате итоговое значение — 1 вместо ожидаемых 2, так как операции увеличения не были выполнены взаимно исключающе. Взаимно исключающие операции — такие, которые нельзя прервать при обращении к ресурсу, например, к ячейке памяти.

Не все специалисты относят гонку данных к частным случаям состояния гонки^[5]. Точное определение гонки данных зависит от используемой модели параллелизма, но обычно это ситуация, когда одна операция памяти в потоке потенциально пересекается по времени с записью в ту же область памяти в другом потоке в опасном контексте. Это означает, что гонка данных отличается от состояния гонки: возможно появление недетерминированности из-за времени даже в программе без гонки данных, если всё взаимодействие между потоками происходит с использованием только атомарных операций.

Гонка данных опасна, поскольку на многих платформах одновременная запись может привести к появлению в памяти непредсказуемой комбинации бит, отличной от записываемых каждым потоком (так называемая «torn write»). Аналогично, одновременное чтение и запись может привести к возврату комбинации старого и нового значения.

Для одновременного обращения на многих платформах существуют специальные операции, безопасные для параллельного доступа (чаще называемые «атомарными» или «синхронизационными»), в отличие от обычных операций, которые небезопасны («data» operations). Скорее всего, отсюда и термин «гонка данных»: при гонке только между синхронизационными операциями результат может быть просто недетерминированным, но корректным; а гонка данных может привести к повреждению памяти или неопределённому поведению.

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

Стандарт C++ (черновик N4296, 2014-11-19, раздел 1.10.23, стр. 14)^[6] формулирует:

Два действия потенциально параллельны, если

• они выполняются разными потоками, либо
• они не упорядочены, и хотя бы одно выполнено обработчиком сигнала.

Выполнение программы содержит гонку данных, если в нём присутствуют две конфликтующие потенциально параллельные операции, хотя бы одна из которых не является атомарной, и между ними отсутствует отношение happens-before — за исключением отдельных случаев для обработчиков сигналов [опущено]. Любая подобная гонка данных приводит к неопределённому поведению.

Часть определения, относящегося к обработчикам сигналов, характерна только для C++.

В работе Detecting Data Races on Weak Memory Systems^[7] приведено другое определение:

две операции памяти конфликтуют, если они обращаются к одной и той же области и хотя бы одна выполняет запись… Две операции, x и y, в последовательном выполнении составляют гонку 〈x, y〉, если x и y конфликтуют и не упорядочены через отношение hb1. Гонка 〈x, y〉 — это гонка данных, если хотя бы одна из x или y — операция данных.

Здесь hb1 — частный случай отношения «произошло до».

Стандарт Java Language Specification^[8] даёт другое определение:

Два обращения (чтения или записи) к одной и той же переменной конфликтуют, если хотя бы одно из обращений является записью… Если в программе есть два конфликтующих обращения (§17.4.1), не связанных зависимостью happens-before, то в ней есть гонка данных… Гонка данных не должна приводить к неправильному поведению, например, к возврату некорректной длины массива.

Ключевое различие: в C++ гонка данных — это неопределённое поведение, а в Java она затрагивает только «межпоточные действия»^[8]. Программа с гонкой данных в Java может иметь нежелательное параллельное поведение, но будет безопасной (если реализация следует стандарту).

Важный аспект гонок данных — в некоторых случаях отсутствие гонок данных гарантирует [последовательную согласованность], что упрощает рассуждения о поведении параллельной программы. Такая гарантия называется SC for DRF. Современные языки программирования (например, Java^[8]) прямо содержат такое требование. Вот пример:

Программа синхронизирована корректно, если и только если все её последовательные выполнения свободны от гонок данных.

Если программа синхронизирована корректно, то все её выполнения будут казаться последовательными (§17.4.3).

Это весьма сильная гарантия для программистов… Достаточно доказать корректную синхронизацию, чтобы исключить влияние перестановок инструкций.

В отличие от Java, стандарт C++ не требует напрямую SC for DRF, но отмечает наличие такой теоремы:

[Примечание: Установлено, что программы, корректно использующие мьютексы и операции memory_order_seq_cst для предотвращения гонок данных, ведут себя как если бы инструкции выполнялись просто в некой последовательности. Это называется «последовательной согласованностью». Однако это верно только для программ без гонок данных…]

Также существуют модели памяти (DRF1^[9], PLpc^[10], DRFrlx^[11]), описывающие SC for DRF для разных архитектур и подходов.

Многие программные состояния гонки связаны с угрозами безопасности. Злоумышленник, получивший доступ к совместно используемому ресурсу, способен спровоцировать сбой и, как следствие, отказ в обслуживании^[12] или повышение привилегий^[13][14].

Особый вид проблемы возникает, если проверка некоего предиката (например, аутентификации) и использование результата разделены во времени, а состояние может измениться между проверкой и использованием (ошибка вида time-of-check to time-of-use).

Состояния гонки также намеренно применяются при создании аппаратных генераторов случайных чисел и физически неклонируемых функций^[15]. PUF реализуются схемами с идентичными путями, где вариации производства определяют, какой путь завершится первым. Измеряя состояние гонки конкретной микросхемы, можно собрать уникальный профиль и использовать его при идентификации.

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

Другая разновидность возникает тогда, когда отдельные программы могут резко исчерпать ресурсы (место на диске, память, процессорное время), что приводит к нестабильности системы. Такое поведение может долгое время не обнаруживаться, а затем быстро привести к отказу многих компонентов. Пример — инцидент с марсоходом Spirit, едва не приведший к его потере из-за некорректного освобождения памяти файловой системой^[16]. Решение — резервировать необходимые ресурсы заранее, либо, более типично, проверять наличие достаточных ресурсов перед запуском (этого может быть недостаточно в сложных системах).

В компьютерных сетях, например в распределённом чате IRC, пользователь, впервые создавший канал, получает права оператора. Если два пользователя на разных серверах запускают канал с одним именем одновременно, оба получают права, поскольку серверы ещё не обменялись состояниями. Проблема устранена в современных реализациях IRC-серверов.

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

Состояние гонки наблюдается также при использовании программой неблокирующих сокетов, когда производительность зависит от скорости сети.

Серьёзные последствия могут быть в системах с риском для жизни. Гонки были среди причин аварий с лучевым аппаратом Therac-25, приведших к гибели как минимум трёх пациентов и ранениям других^[17].

Другой пример — система управления энергоснабжением GE Energy на электростанции FirstEnergy Corp в штате Огайо. Из-за гонки в модуле сигнализации три аварии на линиях электропередачи не были вовремя замечены, что стало причиной блэкаута 2003 года^[18]. Позже был выпущен патч.

Для обнаружения состояний гонки существуют различные инструменты статического и динамического анализа кода.

Статический анализатор Thread Safety Analysis был реализован в gcc, затем в Clang, поддерживает PThreads^[19].

Средства динамического анализа включают:

• Intel Inspector (обнаружение ошибок памяти и потоков для C/C++ и Fortran);
• Intel Advisor (инструмент оптимизации и поддержки потоков);
• ThreadSanitizer (бинарная или LLVM-инструментация, поддержка PThreads)^[20];
• Helgrind (модуль Valgrind для поиска ошибок синхронизации в C, C++, Fortran, использующих POSIX threads)^[21];
• Data Race Detector^[22] для поиска гонки данных в Go.

Для сравнения эффективности средств поиска гонки данных используются бенчмарки:

• DataRaceBench^[23] — набор тестов для инструментов анализа многопоточных приложений на OpenMP.

Состояния гонки часто встречаются в проектировании взаимодействия и удобстве программ: система должна выдавать пользователю понятный отклик на действия, в противном случае неожиданные системные события (например, входящий звонок на смартфоне во время выполнения другой задачи) могут прервать работу пользователя.

В британской железнодорожной сигнализации ситуация гонки возникала при исполнении Правила 55: если машинист сообщал о присутствии поезда, но сигналист принимал другой поезд до его прихода, могла произойти авария (напр., авария в Винвике в 1934 г.). Современные методы устраняют этот риск по радио.

Состояния гонки бывают не только в цифровых системах. Нейронаука обнаруживает гонки и в мозге млекопитающих — например, между путями, управляющими началом движения и его остановкой^[24][25].