Состояние гонки - Race condition

эта статья нужны дополнительные цитаты для проверка. Пожалуйста помоги улучшить эту статью к добавление цитат в надежные источники. Материал, не полученный от источника, может быть оспорен и удален. Найдите источники: «Состояние гонки»  – Новости  · газеты  · книги  · ученый  · JSTOR (Июль 2010 г.) (Узнайте, как и когда удалить этот шаблон сообщения)

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

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

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

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

Электроника

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

Рассмотрим, например, двухвходовой И ворота на один вход подается логический сигнал А, а на другой - его отрицание НЕ А. Теоретически результат (А И НЕ А) никогда не должен быть правдой. Если, однако, изменения в значении A распространяются на второй вход дольше, чем на первый, когда A изменяется с false на true, то наступает короткий период, в течение которого оба входа являются истинными, и поэтому выход вентиля также будет истинным. .^[2]

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

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

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

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

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

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

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

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

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

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

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

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

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

пример

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

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

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

Гонка данных

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

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

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

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

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

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

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

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

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

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

Бумага Обнаружение гонки данных в слабых системах памяти^[7] дает другое определение:

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

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

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

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

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

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

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

SC для DRF

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

Например, в Java эта гарантия прямо указывается^[8]:

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

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

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

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

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

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

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

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

Модель памяти DRF1^[10] предоставляет SC для DRF и позволяет оптимизировать WO (слабое упорядочение), RCsc (Согласованность выпуска с последовательно согласованными специальными операциями), модель памяти VAX и модели памяти без гонки данных. Модель памяти PLpc^[11] предоставляет SC для DRF и позволяет оптимизировать TSO (Общий заказ магазина ), ПСО, ПК (Согласованность процессора ) и RCpc (Согласованность выпуска со специальными операциями согласованности процессора). DRFrlx^[12] дает набросок SC для теоремы DRF в присутствии релаксированной атомики.

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

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

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

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

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

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

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

Сети

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

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

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

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

Программные недостатки в жизненно важные системы может иметь катастрофические последствия. Условия гонки были одними из недостатков Терак-25 радиационная терапия машина, которая привела к гибели как минимум трех пациентов и травм еще нескольких.^[17]

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

Примеры за пределами вычислений

Биология

Эта секция нуждается в расширении. Вы можете помочь добавляя к этому. (Октябрь 2016)

Неврология демонстрирует, что расовые состояния могут возникать и в мозге млекопитающих (крыс).^[19][20]

инструменты

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

Анализ безопасности потоков - это инструмент статического анализа для внутрипроцедурного статического анализа на основе аннотаций, первоначально реализованный как ветвь gcc, а теперь переопределенный в Лязг, поддерживающие PThreads.^{[21][неосновной источник необходим ]}

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

• Инспектор Intel, средство проверки и отладки памяти и потоков для повышения надежности, безопасности и точности приложений C / C ++ и Fortran; Советник Intel, основанный на выборке, инструмент оптимизации векторизации SIMD и поддержки потоков с общей памятью для разработчиков и архитекторов программного обеспечения C, C ++, C # и Fortran;
• ThreadSanitizer, использующий двоичный (Валгринд на основе) или источника, LLVM -на базе КИПиА и поддерживает резьбу PThreads);^{[22][неосновной источник необходим ]} и Хелгринд, Валгринд инструмент для обнаружения ошибок синхронизации в программах C, C ++ и Fortran, использующих примитивы потоковой передачи POSIX pthreads.^{[23][неосновной источник необходим ]}
• Детектор гонки данных^[24] предназначен для поиска гонок данных на языке программирования Go.

Контрольные точки

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

• DataRaceBench^[25] это набор тестов, разработанный для систематической и количественной оценки инструментов обнаружения гонки данных, которые анализируют многопоточные приложения, написанные на OpenMP.

Смотрите также

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

Рекомендации

внешняя ссылка

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