O que é uma condição de corrida?

982

Ao escrever aplicativos multithread, um dos problemas mais comuns enfrentados são as condições de corrida.

Minhas perguntas à comunidade são:

Qual é a condição da corrida?
Como você os detecta?
Como você lida com eles?
Por fim, como você evita que elas ocorram?

bmurphy1976
fonte
3
Há um ótimo capítulo no HOWTO de Programação Segura para Linux que descreve o que são e como evitá-los.
287 Craig Craig H
4
Eu gostaria de mencionar que - sem especificar o idioma - a maioria das partes desta pergunta não pode ser respondida adequadamente, porque em diferentes idiomas, a definição, as consequências e as ferramentas para evitá-las podem diferir.
MikeMB
@MikeMB. Concordamos que, exceto ao analisar a execução do código de bytes, como é feita pelo Race Catcher (consulte este thread stackoverflow.com/a/29361427/1363844 ), podemos abordar todos os aproximadamente 62 idiomas que são compilados no código de bytes (consulte en.wikipedia.org / wiki / List_of_JVM_languages )
Ben

Respostas:

1238

Uma condição de corrida ocorre quando dois ou mais encadeamentos podem acessar dados compartilhados e eles tentam alterá-los ao mesmo tempo. Como o algoritmo de agendamento de encadeamentos pode alternar entre encadeamentos a qualquer momento, você não sabe a ordem em que os encadeamentos tentarão acessar os dados compartilhados. Portanto, o resultado da alteração nos dados depende do algoritmo de agendamento de threads, ou seja, os dois threads estão "correndo" para acessar / alterar os dados.

Os problemas geralmente ocorrem quando um thread faz um "check-then-act" (por exemplo, "check" se o valor é X, então "age" para fazer algo que depende do valor que é X) e outro thread faz algo com o valor em entre o "cheque" e o "ato". Por exemplo:

if (x == 5) // The "Check"
{
   y = x * 2; // The "Act"

   // If another thread changed x in between "if (x == 5)" and "y = x * 2" above,
   // y will not be equal to 10.
}

O ponto é que y pode ser 10 ou pode ser qualquer coisa, dependendo se outro segmento alterou x entre a verificação e a ação. Você não tem uma maneira real de saber.

Para impedir que as condições de corrida ocorram, você normalmente bloqueia os dados compartilhados para garantir que apenas um encadeamento possa acessar os dados por vez. Isso significaria algo como isto:

// Obtain lock for x
if (x == 5)
{
   y = x * 2; // Now, nothing can change x until the lock is released. 
              // Therefore y = 10
}
// release lock for x
Lehane
fonte
121
O que o outro encadeamento faz quando encontra o bloqueio? Isso espera? Erro?
187 Brian Ortiz
174
Sim, o outro encadeamento terá que esperar até que o bloqueio seja liberado antes de continuar. Isso torna muito importante que a trava seja liberada pela rosca de retenção quando terminar. Se ele nunca for lançado, o outro encadeamento aguardará indefinidamente.
Lehane
2
@Ian Em um sistema multithread, sempre haverá momentos em que os recursos precisam ser compartilhados. Dizer que uma abordagem é ruim sem dar uma alternativa simplesmente não é produtivo. Estou sempre procurando maneiras de melhorar e, se houver uma alternativa, terei prazer em pesquisar e pesar os prós e contras.
Despertar
2
@Despertar ... também, não é necessariamente o caso em que os recursos sempre precisam ser compartilhados em um sistema milti-threaded. Por exemplo, você pode ter uma matriz em que cada elemento precise ser processado. Você pode particionar a matriz e ter um encadeamento para cada partição e os encadeamentos podem fazer seu trabalho completamente independentemente um do outro.
Ian Warburton
12
Para que uma corrida ocorra, basta que um único encadeamento tente alterar os dados compartilhados enquanto o restante dos encadeamentos pode lê-los ou alterá-los.
SomeWittyUsername
213

Existe uma "condição de corrida" quando o código multithread (ou paralelo) que acessaria um recurso compartilhado poderia fazê-lo de maneira a causar resultados inesperados.

Veja este exemplo:

for ( int i = 0; i < 10000000; i++ )
{
   x = x + 1; 
}

Se você tivesse 5 threads executando esse código de uma vez, o valor de x NÃO acabaria sendo 50.000.000. De fato, variaria a cada execução.

Isso ocorre porque, para cada thread aumentar o valor de x, eles precisam fazer o seguinte: (simplificado, obviamente)

Recupere o valor de x
Adicione 1 a este valor
Armazene esse valor em x

Qualquer encadeamento pode estar em qualquer etapa deste processo a qualquer momento e pode se interpor quando um recurso compartilhado está envolvido. O estado de x pode ser alterado por outro encadeamento durante o tempo em que x está sendo lido e quando é gravado novamente.

Digamos que um thread recupere o valor de x, mas ainda não o armazenou. Outro encadeamento também pode recuperar o mesmo valor de x (porque nenhum encadeamento o alterou ainda) e, em seguida, ambos armazenariam o mesmo valor (x + 1) em x!

Exemplo:

Tópico 1: lê x, o valor é 7
Tópico 1: adicione 1 a x, o valor é agora 8
Tópico 2: lê x, o valor é 7
Tópico 1: armazena 8 em x
Tópico 2: adiciona 1 a x, o valor agora é 8
Tópico 2: armazena 8 em x

As condições de corrida podem ser evitadas empregando algum tipo de mecanismo de bloqueio antes do código que acessa o recurso compartilhado:

for ( int i = 0; i < 10000000; i++ )
{
   //lock x
   x = x + 1; 
   //unlock x
}

Aqui, a resposta sai sempre como 50.000.000.

Para obter mais informações sobre bloqueio, procure por: mutex, semáforo, seção crítica, recurso compartilhado.

privatehuff
fonte
Veja jakob.engbloms.se/archives/65 para obter um exemplo de programa para testar como essas coisas ficam ruins ... realmente depende do modelo de memória da máquina em que você está executando.
jakobengblom2
1
Como pode chegar a 50 milhões se precisar parar em 10 milhões?
9
@nocomprende: por 5 segmentos executando o mesmo código de cada vez, como descrito imediatamente abaixo o trecho ...
Jon Skeet
4
@ JonSkeet Você está certo, eu confundi o ie o x. Obrigado.
O bloqueio de verificação dupla na implementação do padrão Singleton é um exemplo de prevenção da condição de corrida.
Bharat Dodeja
150

O que é uma condição de corrida?

Você planeja ir ao cinema às 17h. Você pergunta sobre a disponibilidade dos ingressos às 16:00. O representante diz que eles estão disponíveis. Você relaxa e chega à bilheteria 5 minutos antes do show. Tenho certeza que você pode adivinhar o que acontece: é uma casa cheia. O problema aqui estava na duração entre a verificação e a ação. Você perguntou às 4 e agiu às 5. Enquanto isso, outra pessoa pegou os ingressos. Essa é uma condição de corrida - especificamente um cenário de "verificar e agir" das condições de corrida.

Como você os detecta?

Revisão de código religioso, testes de unidade multithread. Não há atalho. Existem poucos plug-ins do Eclipse emergentes nisso, mas nada estável ainda.

Como você lida e os impede?

O melhor seria criar funções livres e sem estado de efeitos colaterais, usar imutáveis ​​o máximo possível. Mas isso nem sempre é possível. Portanto, o uso de java.util.concurrent.atomic, estruturas de dados simultâneas, sincronização adequada e simultaneidade baseada em ator ajudará.

O melhor recurso para simultaneidade é o JCIP. Você também pode obter mais detalhes sobre a explicação acima aqui .

Vishal Shukla
fonte
Revisões de código e testes de unidade são secundários à modelagem do fluxo entre os ouvidos e ao uso menos da memória compartilhada.
Acumenus
2
Apreciei o exemplo do mundo real de uma condição de corrida
Tom O.
11
Como a resposta, gostei . A solução é: você bloqueia os tickets entre 4-5 com mutex (exceção mútua, c ++). No mundo real é chamado de reserva de bilhetes :)
Volt
1
seria uma resposta decente se você deixar cair os bits só de Java (a questão não é sobre Java, mas sim as condições de corrida em geral)
Corey Goldberg
Não. Esta não é uma condição de corrida. Do ponto de vista de "negócios", você apenas esperou demais. Obviamente, o pedido em atraso não é uma solução. Tente um cambista de outra forma apenas comprar o bilhete como um seguro
csherriff
65

Há uma diferença técnica importante entre as condições da corrida e as corridas de dados. A maioria das respostas parece assumir que esses termos são equivalentes, mas não são.

Uma corrida de dados ocorre quando 2 instruções acessam o mesmo local de memória, pelo menos um desses acessos é uma gravação e não há ocorre antes da solicitação entre esses acessos. Agora, o que constitui um acontecimento antes do pedido está sujeito a muito debate, mas, em geral, os pares ulock-lock na mesma variável de bloqueio e os pares de sinal de espera na mesma variável de condição induzem uma ordem de antes do acontecimento.

Uma condição de corrida é um erro semântico. É uma falha que ocorre no tempo ou na ordem dos eventos que leva ao programa incorreto comportamento .

Muitas condições de corrida podem ser (e de fato são) causadas por corridas de dados, mas isso não é necessário. De fato, as corridas de dados e as condições de corrida não são necessárias nem suficientes para uma a outra. Esta postagem no blog também explica muito bem a diferença, com um exemplo simples de transação bancária. Aqui está outro exemplo simples que explica a diferença.

Agora que definimos a terminologia, vamos tentar responder à pergunta original.

Dado que as condições de corrida são erros semânticos, não existe uma maneira geral de detectá-las. Isso ocorre porque não há como ter um oráculo automatizado que possa distinguir o comportamento correto e incorreto do programa no caso geral. A detecção de corrida é um problema indecidível.

Por outro lado, as corridas de dados têm uma definição precisa que não se relaciona necessariamente à correção e, portanto, é possível detectá-las. Existem muitos tipos de detectores de corrida de dados (detecção de corrida de dados estática / dinâmica, detecção de corrida de dados com base em conjunto, detecção de corrida de dados baseada em fatos anteriores, detecção de corrida de dados híbrida). Um detector de corrida de dados dinâmicos de última geração é o ThreadSanitizer que funciona muito bem na prática.

O tratamento das corridas de dados em geral requer alguma disciplina de programação para induzir as ocorrências antes das arestas entre os acessos aos dados compartilhados (durante o desenvolvimento ou depois que eles são detectados usando as ferramentas mencionadas acima). isso pode ser feito por meio de bloqueios, variáveis ​​de condição, semáforos, etc. No entanto, também é possível empregar diferentes paradigmas de programação, como passagem de mensagens (em vez de memória compartilhada), que evitam corridas de dados por construção.

Baris Kasikci
fonte
A diferença é crítica para entender as condições da corrida. Obrigado!
ProgramCpp
37

Uma definição do tipo canônica é " quando dois threads acessam o mesmo local na memória ao mesmo tempo e pelo menos um dos acessos é uma gravação ". Na situação, o segmento "reader" pode obter o valor antigo ou o novo valor, dependendo de qual segmento "vence a corrida". Isso nem sempre é um bug - na verdade, alguns algoritmos de baixo nível realmente peludos fazem isso de propósito - mas geralmente deve ser evitado. @ Steve Gury dá um bom exemplo de quando isso pode ser um problema.

Chris Conway
fonte
3
Você poderia dar um exemplo de como as condições da corrida podem ser úteis? O Google não ajudou.
Alex V.
3
@ Alex V. Neste momento, não tenho ideia do que estava falando. Acho que isso pode ter sido uma referência à programação sem bloqueio, mas não é realmente preciso dizer que depende das condições da corrida, por si só.
Chris Conway
33

Uma condição de corrida é um tipo de bug, que acontece apenas com certas condições temporais.

Exemplo: Imagine que você tem dois threads, A e B.

No segmento A:

if( object.a != 0 )
    object.avg = total / object.a

No segmento B:

object.a = 0

Se o encadeamento A for antecipado logo após ter verificado que o objeto.a não é nulo, B funcionará a = 0e, quando o encadeamento A ganhar o processador, ele fará uma "divisão por zero".

Esse bug só acontece quando o encadeamento A é antecipado logo após a instrução if, é muito raro, mas pode acontecer.

Steve Gury
fonte
21

A condição de corrida não está relacionada apenas ao software, mas também ao hardware. Na verdade, o termo foi cunhado inicialmente pela indústria de hardware.

De acordo com a wikipedia :

O termo se origina com a idéia de dois sinais correndo um contra o outro para influenciar a saída primeiro .

Condição de corrida em um circuito lógico:

insira a descrição da imagem aqui

A indústria de software adotou esse termo sem modificações, o que o torna um pouco difícil de entender.

Você precisa fazer alguma substituição para mapeá-lo para o mundo do software:

  • "dois sinais" => "dois threads" / "dois processos"
  • "influenciar a saída" => "influenciar algum estado compartilhado"

Portanto, a condição de corrida na indústria de software significa "dois threads" / "dois processos" correndo um contra o outro para "influenciar algum estado compartilhado", e o resultado final do estado compartilhado dependerá de alguma diferença sutil de tempo, que pode ser causada por algum problema específico. ordem de lançamento de encadeamento / processo, agendamento de encadeamento / processo etc.

nybon
fonte
20

Uma condição de corrida é uma situação na programação simultânea em que dois processos ou threads simultâneos competem por um recurso e o estado final resultante depende de quem obtém o recurso primeiro.

Jorge Córdoba
fonte
simplesmente brilhante explicação
gokareless
Estado final de quê?
Roman Alexandrovich
1
@RomanAlexandrovich O estado final do programa. O estado que se refere a coisas como valores de variáveis ​​etc. Veja a excelente resposta de Lehane. O "estado" em seu exemplo se referiria aos valores finais de 'x' e 'y'.
AMTerp
19

As condições de corrida ocorrem em aplicativos multithread ou sistemas multiprocessos. Uma condição de corrida, na sua forma mais básica, é qualquer coisa que pressupõe que duas coisas que não estão no mesmo segmento ou processo acontecerão em uma ordem específica, sem tomar medidas para garantir que elas aconteçam. Isso acontece normalmente quando dois threads passam mensagens configurando e verificando variáveis ​​de membros de uma classe que ambos podem acessar. Quase sempre há uma condição de corrida quando um segmento chama suspensão para dar tempo a outro segmento para concluir uma tarefa (a menos que o sono esteja em loop, com algum mecanismo de verificação).

As ferramentas para prevenir condições de corrida dependem do idioma e do sistema operacional, mas algumas comuns são mutexes, seções críticas e sinais. Os mutexes são bons quando você quer ter certeza de que é o único a fazer alguma coisa. Os sinais são bons quando você quer ter certeza de que alguém terminou de fazer alguma coisa. Minimizar recursos compartilhados também pode ajudar a evitar comportamentos inesperados

Detectar as condições da corrida pode ser difícil, mas há alguns sinais. O código que depende muito da suspensão é propenso a condições de corrida, portanto, verifique primeiro se há chamadas para suspensão no código afetado. Adicionar adições particularmente longas também pode ser usado para depuração para tentar forçar uma ordem específica de eventos. Isso pode ser útil para reproduzir o comportamento, ver se é possível fazê-lo desaparecer alterando o tempo das coisas e para testar as soluções implementadas. Os dormentes devem ser removidos após a depuração.

O sinal de assinatura de que alguém tem uma condição de corrida é se houver um problema que ocorre apenas de forma intermitente em algumas máquinas. Erros comuns seriam falhas e impasses. Com o registro, você poderá encontrar a área afetada e voltar a trabalhar a partir daí.

tsellon
fonte
10

A Microsoft publicou um artigo realmente detalhado sobre esse assunto de condições de corrida e impasses. O resumo mais resumido seria o parágrafo do título:

Uma condição de corrida ocorre quando dois threads acessam uma variável compartilhada ao mesmo tempo. O primeiro thread lê a variável e o segundo thread lê o mesmo valor da variável. Em seguida, o primeiro segmento e o segundo segmento executam suas operações no valor e correm para ver qual segmento pode gravar o último valor na variável compartilhada. O valor do segmento que escreve seu último valor é preservado, porque o segmento está escrevendo sobre o valor que o segmento anterior gravou.

Konstantin Dinev
fonte
5

O que é uma condição de corrida?

A situação em que o processo depende criticamente da sequência ou do tempo de outros eventos.

Por exemplo, o processador A e o processador B precisam de recursos idênticos para sua execução.

Como você os detecta?

Existem ferramentas para detectar automaticamente a condição de corrida:

Como você lida com eles?

As condições da corrida podem ser tratadas por Mutex ou Semáforos . Eles agem como um bloqueio, permitindo que um processo adquira um recurso com base em certos requisitos para impedir a condição de corrida.

Como você evita que elas ocorram?

Existem várias maneiras de evitar a condição de corrida, como Evitar Seção Crítica .

  1. Não há dois processos simultaneamente dentro de suas regiões críticas. ( Exclusão mútua)
  2. Nenhuma suposição é feita sobre velocidade ou número de CPUs.
  3. Nenhum processo em execução fora de sua região crítica que bloqueia outros processos.
  4. Nenhum processo precisa esperar uma eternidade para entrar em sua região crítica. (A aguarda recursos B, B aguarda recursos C, C aguarda recursos A)
Adnan Qureshi
fonte
2

Uma condição de corrida é uma situação indesejável que ocorre quando um dispositivo ou sistema tenta executar duas ou mais operações ao mesmo tempo, mas devido à natureza do dispositivo ou sistema, as operações devem ser executadas na seqüência adequada para serem feito corretamente.

Na memória ou armazenamento do computador, pode ocorrer uma condição de corrida se os comandos para ler e gravar uma grande quantidade de dados forem recebidos quase no mesmo instante, e a máquina tentar sobrescrever alguns ou todos os dados antigos enquanto esses dados antigos ainda estão sendo usados. ler. O resultado pode ser um ou mais dos seguintes procedimentos: falha no computador, "operação ilegal", notificação e desligamento do programa, erros na leitura dos dados antigos ou erros na gravação dos novos dados.

dilbag koundal
fonte
2

Aqui está o exemplo clássico de Saldo de conta bancária, que ajudará os novatos a entender os Threads em Java com facilidade nas condições de corrida:

public class BankAccount {

/**
 * @param args
 */
int accountNumber;
double accountBalance;

public synchronized boolean Deposit(double amount){
    double newAccountBalance=0;
    if(amount<=0){
        return false;
    }
    else {
        newAccountBalance = accountBalance+amount;
        accountBalance=newAccountBalance;
        return true;
    }

}
public synchronized boolean Withdraw(double amount){
    double newAccountBalance=0;
    if(amount>accountBalance){
        return false;
    }
    else{
        newAccountBalance = accountBalance-amount;
        accountBalance=newAccountBalance;
        return true;
    }
}

public static void main(String[] args) {
    // TODO Auto-generated method stub
    BankAccount b = new BankAccount();
    b.accountBalance=2000;
    System.out.println(b.Withdraw(3000));

}
realPK
fonte
1

Você pode impedir a condição de corrida , se usar classes "Atomic". O motivo é que o thread não separa a operação get and set, o exemplo está abaixo:

AtomicInteger ai = new AtomicInteger(2);
ai.getAndAdd(5);

Como resultado, você terá 7 no link "ai". Embora você tenha feito duas ações, mas as duas operações confirmam o mesmo encadeamento e nenhum outro encadeamento interfere nisso, isso significa que não há condições de corrida!

Aleksei Moshkov
fonte
0

Tente este exemplo básico para entender melhor as condições da corrida:

    public class ThreadRaceCondition {

    /**
     * @param args
     * @throws InterruptedException
     */
    public static void main(String[] args) throws InterruptedException {
        Account myAccount = new Account(22222222);

        // Expected deposit: 250
        for (int i = 0; i < 50; i++) {
            Transaction t = new Transaction(myAccount,
                    Transaction.TransactionType.DEPOSIT, 5.00);
            t.start();
        }

        // Expected withdrawal: 50
        for (int i = 0; i < 50; i++) {
            Transaction t = new Transaction(myAccount,
                    Transaction.TransactionType.WITHDRAW, 1.00);
            t.start();

        }

        // Temporary sleep to ensure all threads are completed. Don't use in
        // realworld :-)
        Thread.sleep(1000);
        // Expected account balance is 200
        System.out.println("Final Account Balance: "
                + myAccount.getAccountBalance());

    }

}

class Transaction extends Thread {

    public static enum TransactionType {
        DEPOSIT(1), WITHDRAW(2);

        private int value;

        private TransactionType(int value) {
            this.value = value;
        }

        public int getValue() {
            return value;
        }
    };

    private TransactionType transactionType;
    private Account account;
    private double amount;

    /*
     * If transactionType == 1, deposit else if transactionType == 2 withdraw
     */
    public Transaction(Account account, TransactionType transactionType,
            double amount) {
        this.transactionType = transactionType;
        this.account = account;
        this.amount = amount;
    }

    public void run() {
        switch (this.transactionType) {
        case DEPOSIT:
            deposit();
            printBalance();
            break;
        case WITHDRAW:
            withdraw();
            printBalance();
            break;
        default:
            System.out.println("NOT A VALID TRANSACTION");
        }
        ;
    }

    public void deposit() {
        this.account.deposit(this.amount);
    }

    public void withdraw() {
        this.account.withdraw(amount);
    }

    public void printBalance() {
        System.out.println(Thread.currentThread().getName()
                + " : TransactionType: " + this.transactionType + ", Amount: "
                + this.amount);
        System.out.println("Account Balance: "
                + this.account.getAccountBalance());
    }
}

class Account {
    private int accountNumber;
    private double accountBalance;

    public int getAccountNumber() {
        return accountNumber;
    }

    public double getAccountBalance() {
        return accountBalance;
    }

    public Account(int accountNumber) {
        this.accountNumber = accountNumber;
    }

    // If this method is not synchronized, you will see race condition on
    // Remove syncronized keyword to see race condition
    public synchronized boolean deposit(double amount) {
        if (amount < 0) {
            return false;
        } else {
            accountBalance = accountBalance + amount;
            return true;
        }
    }

    // If this method is not synchronized, you will see race condition on
    // Remove syncronized keyword to see race condition
    public synchronized boolean withdraw(double amount) {
        if (amount > accountBalance) {
            return false;
        } else {
            accountBalance = accountBalance - amount;
            return true;
        }
    }
}
Morsu
fonte
0

Você nem sempre quer descartar uma condição de corrida. Se você possui um sinalizador que pode ser lido e gravado por vários threads, e esse sinalizador é definido como 'concluído' por um thread, para que outro thread pare de processar quando o sinalizador está definido como 'concluído', você não deseja que " condição "a ser eliminada. De fato, este pode ser referido como uma condição de raça benigna.

No entanto, usando uma ferramenta para detecção de condição de corrida, ela será identificada como uma condição de corrida prejudicial.

Mais detalhes sobre as condições da corrida aqui, http://msdn.microsoft.com/en-us/magazine/cc546569.aspx .

Kiriloff
fonte
Em que idioma sua resposta se baseia?
precisa saber é o seguinte
Francamente, parece-me que, se você tem condições de corrida em si , não está arquitetando seu código de maneira rigidamente controlada. O que, embora possa não ser um problema no seu caso teórico, é evidência de problemas maiores na maneira como você cria e desenvolve software. Espere enfrentar erros dolorosos nas condições da corrida, mais cedo ou mais tarde.
Engenheiro
0

Considere uma operação que precise exibir a contagem assim que a contagem for incrementada. ou seja, assim que CounterThread incrementa o valor DisplayThread precisa exibir o valor atualizado recentemente.

int i = 0;

Resultado

CounterThread -> i = 1  
DisplayThread -> i = 1  
CounterThread -> i = 2  
CounterThread -> i = 3  
CounterThread -> i = 4  
DisplayThread -> i = 4

Aqui, CounterThread obtém o bloqueio com freqüência e atualiza o valor antes que DisplayThread o exiba. Aqui existe uma condição de corrida. A Condição de corrida pode ser resolvida usando o Synchronzation

bharanitharan
fonte
0

Uma condição de corrida é uma situação indesejável que ocorre quando dois ou mais processos podem acessar e alterar os dados compartilhados ao mesmo tempo. Isso ocorreu porque havia acessos conflitantes a um recurso. O problema crítico da seção pode causar condições de corrida. Para resolver uma condição crítica do processo, realizamos apenas um processo por vez que executa a seção crítica.

rashedcs
fonte