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

«Критическая гонка» перенаправляется сюда. Об академическом движении см. Критическая расовая теория .

Состояние гонки в логической схеме. Здесь ∆ t ₁ и ∆ t ₂ представляют собой задержки распространения логических элементов. Когда входное значение A меняется с низкого на высокое, схема выдает короткий всплеск продолжительностью (∆ t ₁ + ∆ t ₂ ) − ∆ t ₂ = ∆ t ₁ .

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

Термин « состояние гонки» уже использовался к 1954 году, например, в докторской диссертации Дэвида А. Хаффмана «Синтез схем последовательного переключения».

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

В электронике

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

Рассмотрим, например, вентиль И с двумя входами, питаемый следующей логикой: $${\text{output}}=A\wedge {\overline {A}}$$Логический сигнал $A$ на одном входе и его отрицании, $\neg A$ (¬ — логическое отрицание ), на другом входе теоретически никогда не выводится истинное значение: $A\wedge {\overline {A}}\neq 1$. Однако если изменится стоимость $A$ распространение на второй вход занимает больше времени, чем на первый, когда $A$ изменится с ложного на истинное, то наступит короткий период, в течение которого оба входных сигнала будут истинными, и поэтому выходной сигнал вентиля также будет истинным.

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

Критические и некритические формы

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

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

Статические, динамические и существенные формы

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

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

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

Обходные пути

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

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

В программном обеспечении

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

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

Гонка данных — это тип состояния гонки. Гонки данных являются важной частью различных формальных моделей памяти . Модель памяти, определенная в стандартах C11 и C++11, указывает, что программа C или C++, содержащая гонку данных, имеет неопределенное поведение .

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

Пример

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

Тема 1	Тема 2		Целое значение
			0
прочитать значение		←	0
увеличить стоимость			0
напиши ответ		→	1
	прочитать значение	←	1
	увеличить стоимость		1
	напиши ответ	→	2

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

Тема 1	Тема 2		Целое значение
			0
прочитать значение		←	0
	прочитать значение	←	0
увеличить стоимость			0
	увеличить стоимость		0
напиши ответ		→	1
	напиши ответ	→	1

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

Гонка данных

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

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

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

Примеры определений гонок данных в конкретных моделях параллелизма

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

Стандарт C++ в проекте N4296 (19 ноября 2014 г.) определяет гонку данных следующим образом в разделе 1.10.23 (стр. 14).

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

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

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

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

Статья «Обнаружение гонок за данными в слабых системах памяти» дает другое определение:

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

Здесь у нас есть две операции с памятью, обращающиеся к одному и тому же месту, одна из которых — запись.

Отношение hb1 определено в другом месте статьи и является примером типичного отношения « происходит до »; интуитивно, если мы можем доказать, что находимся в ситуации, когда одна операция с памятью X гарантированно будет выполнена до завершения до того, как начнется другая операция с памятью Y, тогда мы говорим, что «X происходит - до Y». Если ни «X не происходит до Y», ни «Y не происходит до X», то мы говорим, что X и Y «не упорядочены отношением hb1». Таким образом, предложение «...и они не упорядочены отношением выполнения hb1» можно интуитивно перевести как «...и X и Y потенциально параллельны».

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

Спецификация языка Java дает другое определение:

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

Критическое различие между подходом C++ и подходом Java заключается в том, что в C++ гонка данных представляет собой неопределенное поведение, тогда как в Java гонка данных просто влияет на «действия между потоками». Это означает, что в C++ попытка выполнить программу, содержащую гонку данных, может (при соблюдении спецификации) привести к сбою или может привести к небезопасному или странному поведению, тогда как в Java попытка выполнить программу, содержащую гонку данных, может привести к нежелательное поведение параллелизма, но в остальном (при условии, что реализация соответствует спецификации) безопасно.

Последовательная согласованность для свободы гонок за данными

Важным аспектом гонок данных является то, что в некоторых контекстах программа, свободная от гонок данных, гарантированно будет выполняться последовательно -согласованным образом, что значительно упрощает рассуждения о параллельном поведении программы. Говорят, что формальные модели памяти, обеспечивающие такую ​​гарантию, обладают свойством «SC for DRF» (последовательная согласованность для свободы гонок данных). Говорят, что этот подход недавно достиг консенсуса (предположительно по сравнению с подходами, которые гарантируют последовательную согласованность во всех случаях, или подходами, которые не гарантируют ее вообще).

Например, в Java эта гарантия указана напрямую:

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

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

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

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

Напротив, проект спецификации C++ не требует напрямую свойства SC для DRF, а просто отмечает, что существует теорема, обеспечивающая это:

[Примечание: можно показать, что программы, которые правильно используют мьютексы и операции Memory_order_seq_cst для предотвращения всех гонок данных и не используют никаких других операций синхронизации, ведут себя так, как будто операции, выполняемые их составляющими потоками, просто чередуются, при этом каждое вычисление значения объекта выполняется от последнего побочного эффекта на этот объект в этом чередовании. Обычно это называется «последовательной согласованностью». Однако это применимо только к программам без гонок за данными, а программы без гонок за данными не могут наблюдать большинство преобразований программы, которые не меняют семантику однопоточной программы. Фактически, большинство однопоточных преобразований программ по-прежнему разрешены, поскольку любая программа, которая в результате ведет себя по-другому, должна выполнить неопределенную операцию. — последнее примечание

Обратите внимание, что проект спецификации C++ допускает возможность использования программ, которые являются допустимыми, но используют операции синхронизации с Memory_order, отличным от Memory_order_seq_cst, и в этом случае результатом может быть программа, которая является правильной, но для которой не предоставляется гарантия последовательной согласованности. Другими словами, в C++ некоторые правильные программы не являются последовательно согласованными. Считается, что этот подход дает программистам C++ свободу выбора более быстрого выполнения программы за счет отказа от простоты рассуждений о своей программе.

Существуют различные теоремы, часто представленные в форме моделей памяти, которые обеспечивают гарантии SC для DRF в различных контекстах. Посылки этих теорем обычно налагают ограничения как на модель памяти (и, следовательно, на реализацию), так и на программиста; иными словами, обычно бывает так, что существуют программы, которые не соответствуют предпосылкам теоремы и которые не могут быть гарантированно выполнены последовательно-согласованным образом.

Модель памяти DRF1 обеспечивает SC для DRF и позволяет оптимизировать WO (слабый порядок), RCsc ( согласованность выпуска с последовательно согласованными специальными операциями), модель памяти VAX и модели памяти без гонок данных 0. Модель памяти PLpc обеспечивает SC для DRF и позволяет оптимизировать модели TSO ( общий заказ хранилища ), PSO, PC ( согласованность процессора ) и RCpc ( согласованность выпуска со специальными операциями согласованности процессора). DRFrlx представляет собой схему SC для теоремы DRF в присутствии релаксированных атомов.

Компьютерная безопасность

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

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

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

Файловые системы

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

Другая форма состояния гонки существует в файловых системах, где несвязанные программы могут влиять друг на друга, внезапно используя доступные ресурсы, такие как дисковое пространство, пространство памяти или циклы процессора. Программное обеспечение, не разработанное должным образом для предвидения и управления этой гоночной ситуацией, может стать непредсказуемым. Такой риск может долгое время игнорироваться в системе, которая кажется очень надежной. Но в конечном итоге может накопиться достаточно данных или может быть добавлено достаточно другого программного обеспечения, чтобы критически дестабилизировать многие части системы. Примером этого стала гибель марсохода «Спирит» вскоре после приземления. Решение состоит в том, чтобы программное обеспечение запрашивало и резервировало все необходимые ему ресурсы перед началом задачи; если этот запрос завершается неудачей, задача откладывается, что позволяет избежать многих моментов, когда мог произойти сбой. Альтернативно, каждая из этих точек может быть оснащена обработкой ошибок, или успех всей задачи может быть проверен впоследствии, прежде чем продолжить. Более распространенный подход — просто проверить наличие достаточного количества системных ресурсов перед запуском задачи; однако этого может быть недостаточно, поскольку в сложных системах действия других работающих программ могут быть непредсказуемыми.

сеть

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

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

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

Жизненно важные системы

Ошибки программного обеспечения в жизненно важных системах могут иметь катастрофические последствия. Условия гонки были среди недостатков Therac-25 аппарата лучевой терапии , что привело к гибели как минимум трех пациентов и ранениям еще нескольких.

Другим примером является система управления энергопотреблением, предоставленная GE Energy и используемая Огайо базирующейся в компанией FirstEnergy Corp (среди других энергетических предприятий). В подсистеме сигнализации существовало состояние гонки; Когда одновременно были отключены три провисающие линии электропередачи, из-за этого условия специалисты по мониторингу не были предупреждены, что задержало их осведомленность о проблеме. Этот программный недостаток в конечном итоге привел к отключению электроэнергии в Северной Америке в 2003 году . Позже GE Energy разработала исправление программного обеспечения для исправления ранее не обнаруженной ошибки.

Инструменты

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

Анализ безопасности потоков — это инструмент статического анализа для внутрипроцедурного статического анализа на основе аннотаций, первоначально реализованный как ветвь gcc, а теперь перереализованный в Clang с поддержкой PThreads.

Инструменты динамического анализа включают в себя:

• Intel Inspector — инструмент проверки и отладки памяти и потоков для повышения надежности, безопасности и точности приложений C/C++ и Fortran; Intel Advisor — основанный на выборке инструмент для оптимизации векторизации SIMD и поддержки потоков в общей памяти для разработчиков и архитекторов программного обеспечения C, C++, C# и Fortran;
• ThreadSanitizer, который использует двоичный ( на основе Valgrind ) или исходный инструментарий на основе LLVM и поддерживает PThreads; и Helgrind, инструмент Valgrind для обнаружения ошибок синхронизации в программах C, C++ и Fortran, использующих примитивы потоков POSIX pthreads.
• Детектор гонки данных предназначен для поиска гонок данных на языке программирования Go.

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

• ДанныеГонкаСкамейка — это пакет тестов, предназначенный для систематической и количественной оценки инструментов обнаружения гонок за данными, которые анализируют многопоточные приложения, написанные на OpenMP .

В других областях

Нейронауки показывают, что расовые состояния могут возникать и в мозге млекопитающих.

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

См. также

• Коллизия вызовов
• Управление параллелизмом
• Тупик
• Опасность (логика)
• Линеаризуемость
• Проблема с гоночной трассой
• Гонка по символическим ссылкам
• Синхронизация (информатика)
• Время проверки до времени использования
• Тест и настройка

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

• Карам, генеральный менеджер; Бур, RJA (август 1990 г.). «Анализаторы голода и критической расы для Ады». Транзакции IEEE по разработке программного обеспечения . 16 (8): 829–843. дои : 10.1109/32.57622 .
• Фюрер, Р.М.; Лин, Б.; Новик, С.М. (март 1995 г.). «Алгоритмы оптимального назначения состояний асинхронных конечных автоматов». Перспективные исследования в области СБИС, 1995. Материалы 16-й конференции по . стр. 59–75. дои : 10.1109/ARVLSI.1995.515611 . ISBN  978-0-8186-7047-3 . S2CID   4435912 . в формате PDF. Архивировано 10 июня 2021 г. на Wayback Machine.
• Статья « Новая основа для решения проблемы назначения состояний для спецификаций на основе событий » Лучано Лаваньо, Чо В. Муна, Роберта К. Брайтона и Альберто Санджованни-Винсентелли
• Уиллер, Дэвид А. (7 октября 2004 г.). «Безопасный программист: предотвращайте условия гонки — борьба за ресурсы может быть использована против вас» . IBM DeveloperWorks . Архивировано из оригинала (PDF) 1 февраля 2009 г. Альтернативный URL.
• Глава « Избегайте состояний гонки », заархивировано 9 марта 2014 г. на Wayback Machine (HOWTO по безопасному программированию для Linux и Unix)
• Условия гонки, безопасность и неизменяемость в Java , с примером исходного кода и сравнением с кодом C, автор Chiral Software.
• Карпов, Андрей (6 апреля 2009 г.). «Интервью с Дмитрием Вьюковым — автором Relacy Race Detector (RRD)» .
• Описание службы поддержки Майкрософт
• Состояние гонки против гонки данных