Condição de corrida - Race condition

Condição de corrida em um circuito lógico. Aqui, ∆ t 1 e ∆ t 2 representam os atrasos de propagação dos elementos lógicos. Quando o valor de entrada A muda de baixo para alto, o circuito emite um curto pico de duração (∆ t 1 + ∆ t 2 ) - ∆ t 2 = ∆ t 1 .

Uma condição de corrida ou risco de corrida é a condição de um sistema eletrônico , software ou outro sistema em que o comportamento substantivo do sistema depende da sequência ou do tempo de outros eventos incontroláveis. Torna-se um bug quando um ou mais dos comportamentos possíveis são indesejáveis.

O termo condição de corrida já estava em uso em 1954, por exemplo na tese de doutorado de David A. Huffman "A síntese de circuitos de comutação sequencial".

As condições de corrida podem ocorrer especialmente em circuitos lógicos , multithreaded ou programas de software distribuídos .

Em eletronica

Um exemplo típico de condição de corrida pode ocorrer quando uma porta lógica combina sinais que viajaram por caminhos diferentes da mesma fonte. As entradas para o gate podem mudar em momentos ligeiramente diferentes em resposta a uma mudança no sinal de origem. A saída pode, por um breve período, mudar para um estado indesejado antes de voltar ao estado projetado. Certos sistemas podem tolerar tais falhas, mas se essa saída funcionar como um sinal de clock para outros sistemas que contenham memória, por exemplo, o sistema pode rapidamente se desviar de seu comportamento projetado (na verdade, a falha temporária se torna uma falha permanente).

Considere, por exemplo, uma porta AND de duas entradas alimentada com a seguinte lógica:

Um sinal lógico em uma entrada e sua negação (o ¬ é uma negação booleana ), em outra entrada, em teoria, nunca produz um valor verdadeiro: Se, no entanto, as mudanças no valor de demoram mais para se propagar para a segunda entrada do que a primeira quando muda de falso para verdadeiro, então um breve período ocorrerá durante o qual ambas as entradas são verdadeiras e, portanto, a saída do gate também será verdadeira.

Formas críticas e não críticas

Uma condição de corrida crítica ocorre quando a ordem em que as variáveis ​​internas são alteradas determina o estado eventual em que a máquina de estado ficará.

Uma condição de corrida não crítica ocorre quando a ordem em que as variáveis ​​internas são alteradas não determina o estado eventual em que a máquina de estado ficará.

Formas estáticas, dinâmicas e essenciais

Uma condição de corrida estática ocorre quando um sinal e seu complemento são combinados.

Uma condição de corrida dinâmica ocorre quando resulta em várias transições quando apenas uma é pretendida. Eles são devidos à interação entre os portões. Ele pode ser eliminado usando não mais do que dois níveis de portas.

Uma condição de corrida essencial ocorre quando uma entrada tem duas transições em menos do que o tempo total de propagação do feedback. Às vezes, eles são curados usando elementos de linha de retardo indutivo para aumentar efetivamente o tempo de duração de um sinal de entrada.

Soluções Alternativas

Técnicas de design, como mapas de Karnaugh, incentivam os designers a reconhecer e eliminar as condições de corrida antes que causem problemas. Freqüentemente , a redundância lógica pode ser adicionada para eliminar alguns tipos de corridas.

Além desses problemas, alguns elementos lógicos podem entrar em estados metaestáveis , o que cria mais problemas para projetistas de circuitos.

Em software

Uma condição de corrida surge no software quando um programa de computador, para operar corretamente, depende da sequência ou do tempo dos processos ou threads do programa . Condições críticas de corrida causam execução inválida e bugs de software . Freqüentemente, as condições críticas de corrida acontecem quando os processos ou threads dependem de algum estado compartilhado. As operações em estados compartilhados são feitas em seções críticas que devem ser mutuamente exclusivas . O não cumprimento desta regra pode corromper o estado compartilhado.

Uma corrida de dados é um tipo de condição de corrida. Corridas de dados são partes importantes de vários modelos de memória formal . O modelo de memória definido nos padrões C11 e C ++ 11 especifica que um programa C ou C ++ contendo uma disputa de dados tem comportamento indefinido .

Uma condição de corrida pode ser difícil de reproduzir e depurar porque o resultado final não é determinístico e depende do tempo relativo entre threads interferentes. Problemas dessa natureza podem, portanto, desaparecer durante a execução no modo de depuração, adicionando log extra ou anexando um depurador. Um bug que desaparece assim durante as tentativas de depuração costuma ser chamado de " Heisenbug ". Portanto, é melhor evitar condições de corrida por meio de um projeto de software cuidadoso.

Exemplo

Suponha que cada um de dois threads incrementa o valor de uma variável inteira global em 1. Idealmente, a seguinte sequência de operações ocorreria:

Tópico 1 Tópico 2 Valor inteiro
0
ler valor 0
aumentar o valor 0
Escreva de volta 1
ler valor 1
aumentar o valor 1
Escreva de volta 2

No caso mostrado acima, o valor final é 2, conforme o esperado. No entanto, se os dois threads forem executados simultaneamente sem bloqueio ou sincronização, o resultado da operação pode estar errado. A sequência alternativa de operações abaixo demonstra este cenário:

Tópico 1 Tópico 2 Valor inteiro
0
ler valor 0
ler valor 0
aumentar o valor 0
aumentar o valor 0
Escreva de volta 1
Escreva de volta 1

Nesse caso, o valor final é 1 em vez do resultado esperado de 2. Isso ocorre porque aqui as operações de incremento não são mutuamente exclusivas. Operações mutuamente exclusivas são aquelas que não podem ser interrompidas durante o acesso a algum recurso, como um local de memória.

Corrida de dados

Nem todos consideram as corridas de dados como um subconjunto das condições da corrida. A definição precisa de corrida de dados é específica para o modelo de simultaneidade formal que está sendo usado, mas normalmente se refere a uma situação onde uma operação de memória em um encadeamento pode potencialmente tentar acessar um local de memória ao mesmo tempo que uma operação de memória em outro encadeamento está escrever para esse local da memória, em um contexto onde isso é perigoso. Isso implica que uma corrida de dados é diferente de uma condição de corrida, pois é possível haver não-determinismo devido ao tempo, mesmo em um programa sem corrida de dados, por exemplo, em um programa em que todos os acessos à memória usam apenas operações atômicas .

Isso pode ser perigoso porque em muitas plataformas, se dois threads gravam em um local da memória ao mesmo tempo, pode ser possível que o local da memória termine mantendo um valor que é uma combinação arbitrária e sem sentido dos bits que representam os valores que cada thread estava tentando escrever; isso pode resultar em corrupção de memória se o valor resultante for um que nenhum thread tentou gravar (às vezes isso é chamado de ' gravação interrompida '). Da mesma forma, se um thread lê de um local enquanto outro thread está gravando nele, pode ser possível para a leitura retornar um valor que é uma combinação arbitrária e sem sentido dos bits que representam o valor que o local da memória mantinha antes da gravação, e dos bits que representam o valor que está sendo escrito.

Em muitas plataformas, operações de memória especiais são fornecidas para acesso simultâneo; nesses casos, normalmente o acesso simultâneo usando essas operações especiais é seguro, mas o acesso simultâneo usando outras operações de memória é perigoso. Às vezes, essas operações especiais (que são seguras para acesso simultâneo) são chamadas de operações atômicas ou de sincronização , enquanto as operações comuns (que não são seguras para acesso simultâneo) são chamadas de operações de dados . É provavelmente por isso que o termo é corrida de dados ; em muitas plataformas, onde há uma condição de corrida envolvendo apenas operações de sincronização , tal corrida pode ser não determinística, mas de outra forma segura; mas uma corrida de dados pode levar à corrupção da memória ou comportamento indefinido.

Definições de exemplo de corridas de dados em modelos de simultaneidade específicos

A definição precisa de corrida de dados difere entre os modelos de simultaneidade formais. Isso é importante porque o comportamento simultâneo geralmente não é intuitivo e, por isso, o raciocínio formal às vezes é aplicado.

O padrão C ++ , no rascunho N4296 (19/11/2014), define a disputa de dados como segue na seção 1.10.23 (página 14)

Duas ações são potencialmente simultâneas se

  • eles são executados por diferentes threads, ou
  • eles não são sequenciados e pelo menos um é executado por um manipulador de sinais.

A execução de um programa contém uma corrida de dados se contiver duas ações conflitantes potencialmente concorrentes, pelo menos uma das quais não é atômica, e nenhuma acontece antes da outra, exceto para o caso especial para manipuladores de sinal descritos abaixo [omitido]. Qualquer corrida de dados resulta em comportamento indefinido.

As partes desta definição relacionadas a manipuladores de sinal são idiossincráticas para C ++ e não são típicas de definições de corrida de dados .

O artigo Detectando Corridas de Dados em Sistemas de Memória Fraca fornece uma definição diferente:

"duas operações de memória entram em conflito se acessam o mesmo local e pelo menos uma delas é uma operação de gravação ..." Duas operações de memória, x e y, em uma execução sequencialmente consistente, formam uma corrida 〈x, y〉, iff x e conflito y, e eles não são ordenados pela relação hb1 da execução. A corrida 〈x, y〉, é uma corrida de dados se pelo menos um de x ou y for uma operação de dados.

Aqui temos duas operações de memória acessando o mesmo local, uma das quais é uma gravação.

A relação hb1 é definida em outro lugar no artigo e é um exemplo de uma relação típica " acontece antes "; intuitivamente, se pudermos provar que estamos em uma situação em que uma operação de memória X tem a garantia de ser concluída antes que outra operação de memória Y comece, então dizemos que "X acontece antes de Y". Se nem "X acontece antes de Y" nem "Y acontece antes de X", dizemos que X e Y "não são ordenados pela relação hb1". Assim, a cláusula "... e eles não são ordenados pela relação hb1 da execução" pode ser traduzida intuitivamente como "... e X e Y são potencialmente concorrentes".

O artigo considera perigosas apenas aquelas situações em que pelo menos uma das operações de memória é uma "operação de dados"; em outras partes deste artigo, o artigo também define uma classe de " operações de sincronização " que são seguras para uso potencialmente simultâneo, em contraste com as "operações de dados".

A especificação da linguagem Java fornece uma definição diferente:

Dois acessos a (leituras ou gravações) na mesma variável são considerados conflitantes se pelo menos um dos acessos for uma gravação ... Quando um programa contém dois acessos conflitantes (§17.4.1) que não são ordenados por um relação acontece antes, diz-se que contém uma disputa de dados ... uma disputa de dados não pode causar um comportamento incorreto, como retornar o comprimento errado para uma matriz.

Uma diferença crítica entre a abordagem C ++ e a abordagem Java é que em C ++, uma corrida de dados é um comportamento indefinido, enquanto em Java, uma corrida de dados apenas afeta as "ações entre threads". Isso significa que em C ++, uma tentativa de executar um programa contendo uma corrida de dados pode (enquanto ainda segue as especificações) travar ou pode exibir um comportamento inseguro ou bizarro, enquanto em Java, uma tentativa de executar um programa contendo uma corrida de dados pode produzir comportamento de simultaneidade indesejado, mas de outra forma (assumindo que a implementação está de acordo com a especificação) é seguro.

SC para DRF

Uma faceta importante das corridas de dados é que, em alguns contextos, um programa que está livre de corridas de dados tem garantia de execução de maneira sequencialmente consistente , facilitando muito o raciocínio sobre o comportamento simultâneo do programa. Os modelos de memória formal que fornecem essa garantia exibem uma propriedade "SC para DRF" (consistência sequencial para liberdade de corrida de dados). Foi dito que essa abordagem alcançou um consenso recente (presumivelmente em comparação com as abordagens que garantem consistência sequencial em todos os casos, ou abordagens que não a garantem de forma alguma).

Por exemplo, em Java, esta garantia é especificada diretamente:

Um programa é sincronizado corretamente se e somente se todas as execuções sequencialmente consistentes estiverem livres de corridas de dados.

Se um programa estiver sincronizado corretamente, todas as execuções do programa parecerão sequencialmente consistentes (§17.4.3).

Esta é uma garantia extremamente forte para programadores. Os programadores não precisam raciocinar sobre reordenamentos para determinar se seu código contém corridas de dados. Portanto, eles não precisam raciocinar sobre reordenamentos ao determinar se seu código está sincronizado corretamente. Uma vez feita a determinação de que o código está corretamente sincronizado, o programador não precisa se preocupar se os reordenamentos afetarão seu código.

Um programa deve ser sincronizado corretamente para evitar os tipos de comportamentos contra-intuitivos que podem ser observados quando o código é reordenado. O uso da sincronização correta não garante que o comportamento geral de um programa seja correto. No entanto, seu uso permite que um programador raciocine sobre os possíveis comportamentos de um programa de uma maneira simples; o comportamento de um programa sincronizado corretamente é muito menos dependente de possíveis reordenamentos. Sem a sincronização correta, comportamentos muito estranhos, confusos e contra-intuitivos são possíveis.

Por outro lado, um projeto de especificação C ++ não exige diretamente um SC para a propriedade DRF, mas apenas observa que existe um teorema que o fornece:

[Nota: pode ser mostrado que os programas que usam mutexes e operações memory_order_seq_cst corretamente para evitar todas as corridas de dados e não usam outras operações de sincronização se comportam como se as operações executadas por seus threads constituintes fossem simplesmente intercaladas, com cada cálculo de valor de um objeto sendo feito do último efeito colateral naquele objeto nessa intercalação. Isso normalmente é conhecido como “consistência sequencial”. No entanto, isso se aplica apenas a programas sem disputa de dados, e os programas sem disputa de dados não podem observar a maioria das transformações de programa que não alteram a semântica do programa de thread único. Na verdade, a maioria das transformações de programa de thread único continua a ser permitida, uma vez que qualquer programa que se comporte de maneira diferente como resultado deve executar uma operação indefinida. - nota final

Observe que a especificação preliminar C ++ admite a possibilidade de programas que são válidos, mas usam operações de sincronização com uma memory_order diferente de memory_order_seq_cst, caso em que o resultado pode ser um programa correto, mas para o qual nenhuma garantia de consistência sequencial é fornecida. Em outras palavras, em C ++, alguns programas corretos não são sequencialmente consistentes. Essa abordagem é pensada para dar aos programadores C ++ a liberdade de escolher uma execução mais rápida do programa ao custo de desistir da facilidade de raciocínio sobre seu programa.

Existem vários teoremas, frequentemente fornecidos na forma de modelos de memória, que fornecem SC para garantias de DRF em vários contextos. As premissas desses teoremas normalmente colocam restrições tanto no modelo de memória (e, portanto, na implementação), e também no programador; ou seja, normalmente é o caso de programas que não atendem às premissas do teorema e que não pode ser garantida a execução de uma maneira sequencialmente consistente.

O modelo de memória DRF1 fornece SC para DRF e permite as otimizações de WO (ordenação fraca), RCsc ( Release Consistency com operações especiais sequencialmente consistentes), modelo de memória VAX e modelos de memória data-race-free-0. O modelo de memória PLpc fornece SC para DRF e permite as otimizações dos modelos TSO ( Total Store Order ), PSO, PC ( Processor Consistency ) e RCpc ( Release Consistency com operações especiais de consistência do processador). DRFrlx fornece um esboço de um SC para o teorema DRF na presença de átomos relaxados.

Segurança informática

Muitas condições de corrida de software têm implicações associadas à segurança do computador . Uma condição de corrida permite que um invasor com acesso a um recurso compartilhado faça com que outros atores que utilizam esse recurso funcionem incorretamente, resultando em efeitos que incluem negação de serviço e aumento de privilégios .

Um tipo específico de condição de corrida envolve a verificação de um predicado (por exemplo, para autenticação ) e, em seguida, a ação sobre o predicado, enquanto o estado pode mudar entre o momento da verificação e o tempo de uso . Quando esse tipo de bug existe em um código sensível à segurança, uma vulnerabilidade de segurança chamada bug do tempo de verificação até o tempo de uso ( TOCTTOU ) é criada.

As condições de corrida também são usadas intencionalmente para criar geradores de números aleatórios de hardware e funções fisicamente impossíveis de clonar . Os PUFs podem ser criados projetando topologias de circuito com caminhos idênticos para um nó e contando com variações de fabricação para determinar aleatoriamente quais caminhos serão concluídos primeiro. Ao medir o conjunto específico de resultados de condição de corrida de cada circuito fabricado, um perfil pode ser coletado para cada circuito e mantido em segredo para posteriormente verificar a identidade de um circuito.

Sistemas de arquivos

Dois ou mais programas podem colidir em suas tentativas de modificar ou acessar um sistema de arquivos, o que pode resultar em corrupção de dados ou aumento de privilégios. O bloqueio de arquivo fornece uma solução comumente usada. Uma solução mais complicada envolve organizar o sistema de tal forma que um único processo (executando um daemon ou semelhante) tenha acesso exclusivo ao arquivo, e todos os outros processos que precisam acessar os dados nesse arquivo o fazem apenas por meio de comunicação entre processos com aquele processo. Isso requer sincronização no nível do processo.

Uma forma diferente de condição de corrida existe em sistemas de arquivos onde programas não relacionados podem afetar uns aos outros usando repentinamente os recursos disponíveis, como espaço em disco, espaço de memória ou ciclos de processador. O software não projetado cuidadosamente para antecipar e lidar com essa situação de corrida pode se tornar imprevisível. Esse risco pode passar despercebido por muito tempo em um sistema que parece muito confiável. Mas, eventualmente, dados suficientes podem se acumular ou outro software suficiente pode ser adicionado para desestabilizar criticamente muitas partes de um sistema. Um exemplo disso ocorreu com a quase perda do "Spirit" do Mars Rover, pouco depois de pousar. Uma solução é o software solicitar e reservar todos os recursos de que precisará antes de iniciar uma tarefa; se esta solicitação falhar, a tarefa é adiada, evitando os muitos pontos onde a falha poderia ter ocorrido. Alternativamente, cada um desses pontos pode ser equipado com tratamento de erros, ou o sucesso de toda a tarefa pode ser verificado posteriormente, antes de continuar. Uma abordagem mais comum é simplesmente verificar se há recursos de sistema suficientes disponíveis antes de iniciar uma tarefa; no entanto, isso pode não ser adequado porque, em sistemas complexos, as ações de outros programas em execução podem ser imprevisíveis.

Networking

Na rede, considere uma rede de bate-papo distribuída como o IRC , onde um usuário que inicia um canal adquire automaticamente privilégios de operador de canal. Se dois usuários em servidores diferentes, em extremidades diferentes da mesma rede, tentarem iniciar o canal com o mesmo nome ao mesmo tempo, o respectivo servidor de cada usuário concederá privilégios de operador de canal a cada usuário, uma vez que nenhum servidor ainda terá recebido o sinal de outro servidor de que ele alocou aquele canal. (Este problema foi amplamente resolvido por várias implementações de servidor IRC.)

Neste caso de condição de corrida, o conceito de " recurso compartilhado " abrange o estado da rede (quais canais existem, bem como quais usuários os iniciaram e, portanto, têm quais privilégios), que cada servidor pode alterar livremente, desde que ele sinaliza os outros servidores da rede sobre as mudanças para que eles possam atualizar sua concepção do estado da rede. No entanto, a latência na rede torna possível o tipo de condição de corrida descrita. Neste caso, evitar as condições de corrida impondo uma forma de controle sobre o acesso ao recurso compartilhado - digamos, nomear um servidor para controlar quem detém quais privilégios - significaria transformar a rede distribuída em uma centralizada (pelo menos para aquela parte da operação da rede).

Também podem existir condições de corrida quando um programa de computador é escrito com soquetes não bloqueadores , caso em que o desempenho do programa pode depender da velocidade do link de rede.

Sistemas vitais

Falhas de software em sistemas vitais podem ser desastrosas. As condições de corrida estavam entre as falhas na máquina de terapia de radiação Therac-25 , o que levou à morte de pelo menos três pacientes e ferimentos a vários outros.

Outro exemplo é o sistema de gerenciamento de energia fornecido pela GE Energy e usado pela FirstEnergy Corp, sediada em Ohio (entre outras instalações de energia). Existia uma condição de corrida no subsistema de alarme; quando três cabos de força flácidos foram acionados simultaneamente, a condição impediu que fossem emitidos alertas aos técnicos de monitoramento, retardando sua conscientização sobre o problema. Essa falha de software acabou levando ao Blackout na América do Norte em 2003 . Mais tarde, a GE Energy desenvolveu um patch de software para corrigir o erro não descoberto anteriormente.

Ferramentas

Existem muitas ferramentas de software para ajudar a detectar condições de corrida no software. Eles podem ser amplamente categorizados em dois grupos: ferramentas de análise estática e ferramentas de análise dinâmica .

Thread Safety Analysis é uma ferramenta de análise estática para análise estática intraprocedimento baseada em anotação, originalmente implementada como um branch do gcc, e agora reimplementada no Clang , com suporte a PThreads.

As ferramentas de análise dinâmica incluem:

  • Intel Inspector , uma ferramenta de verificação e depuração de memória e thread para aumentar a confiabilidade, segurança e precisão dos aplicativos C / C ++ e Fortran; Intel Advisor , uma ferramenta baseada em amostragem, otimização de vetorização SIMD e assistência de threading de memória compartilhada para desenvolvedores e arquitetos de software C, C ++, C # e Fortran;
  • ThreadSanitizer, que usa binário ( baseado em Valgrind ) ou fonte, instrumentação baseada em LLVM e suporta PThreads); e Helgrind, uma ferramenta Valgrind para detectar erros de sincronização em programas C, C ++ e Fortran que usam as primitivas de thread pthreads POSIX.
  • O Data Race Detector foi projetado para localizar corridas de dados na linguagem de programação Go.

Existem vários benchmarks projetados para avaliar a eficácia das ferramentas de detecção de corrida de dados

  • DataRaceBench é um conjunto de benchmark projetado para avaliar de forma sistemática e quantitativa as ferramentas de detecção de corrida de dados que analisam aplicativos multi-threaded escritos em OpenMP .

Em outras áreas

A neurociência está demonstrando que as condições de corrida também podem ocorrer nos cérebros de mamíferos (ratos).

Na sinalização ferroviária do Reino Unido , uma condição de corrida surgiria no cumprimento da Regra 55 . De acordo com essa regra, se um trem fosse parado em uma linha em movimento por um sinal, o bombeiro da locomotiva caminharia até a caixa de sinalização para lembrar ao sinaleiro que o trem estava presente. Em pelo menos um caso, em Winwick em 1934, ocorreu um acidente porque o sinaleiro aceitou outro trem antes da chegada do bombeiro. A prática moderna de sinalização remove a condição de corrida, tornando possível para o motorista entrar em contato instantaneamente com a caixa de sinalização por rádio.

Veja também

Referências

links externos