Cos'è una condizione di gara?

Question

Quando si scrivono applicazioni multi-thread, uno dei problemi più comuni riscontrati sono le condizioni di competizione.

Le mie domande alla comunità sono:

Cos'è una condizione di gara?Come rilevarli?Come li gestisci?Infine, come evitare che si verifichino?

Answer 1

Una race condition si verifica quando due o più thread possono accedere ai dati condivisi e tentano di modificarli contemporaneamente.Poiché l'algoritmo di pianificazione dei thread può passare da un thread all'altro in qualsiasi momento, non si conosce l'ordine in cui i thread tenteranno di accedere ai dati condivisi.Pertanto, il risultato della modifica dei dati dipende dall'algoritmo di pianificazione dei thread, ad es.entrambi i thread stanno "correndo" per accedere/modificare i dati.

Spesso si verificano problemi quando un thread esegue un "check-then-act" (ad es."check" se il valore è X, quindi "act" per fare qualcosa che dipende dal fatto che il valore sia X) e un altro thread fa qualcosa al valore tra "check" e "act".Per esempio:

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.
}

Il punto è che y potrebbe essere 10, o potrebbe essere qualsiasi cosa, a seconda che un altro thread abbia modificato x tra il controllo e l'azione.Non hai alcun modo reale di saperlo.

Per evitare che si verifichino condizioni di competizione, in genere si mette un blocco attorno ai dati condivisi per garantire che solo un thread alla volta possa accedere ai dati.Ciò significherebbe qualcosa del genere:

// 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

Answer 2

Esiste una "race condition" quando il codice multithread (o altrimenti parallelo) che accede a una risorsa condivisa potrebbe farlo in modo tale da causare risultati imprevisti.

Prendi questo esempio:

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

Se avessi 5 thread che eseguono questo codice contemporaneamente, il valore di x NON finirebbe per essere 50.000.000.In effetti varierebbe ad ogni corsa.

Questo perché, affinché ciascun thread possa incrementare il valore di x, deve fare quanto segue:(semplificato, ovviamente)

Retrieve the value of x
Add 1 to this value
Store this value to x

Qualsiasi thread può trovarsi in qualsiasi fase di questo processo in qualsiasi momento e può sovrapporsi a vicenda quando è coinvolta una risorsa condivisa.Lo stato di x può essere modificato da un altro thread durante il tempo che intercorre tra la lettura di x e il momento in cui viene riscritto.

Diciamo che un thread recupera il valore di x, ma non lo ha ancora memorizzato.Un altro thread può anche recuperare il file Stesso valore di x (perché nessun thread lo ha ancora modificato) e quindi entrambi memorizzerebbero il file Stesso valore (x+1) di nuovo in x!

Esempio:

Thread 1: reads x, value is 7
Thread 1: add 1 to x, value is now 8
Thread 2: reads x, il valore è 7
Thread 1: stores 8 in x
Thread 2: adds 1 to x, value is now 8
Thread 2: memorizza 8 in x

Le condizioni di gara possono essere evitate impiegando una sorta di bloccaggio meccanismo prima del codice che accede alla risorsa condivisa:

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

Qui la risposta è sempre 50.000.000.

Per ulteriori informazioni sul blocco, cercare:mutex, semaforo, sezione critica, risorsa condivisa.

Answer 3

Che cos'è una condizione di competizione?

Hai intenzione di andare al cinema alle 17:00.Si informa sulla disponibilità dei biglietti alle 16:00.Il rappresentante dice che sono disponibili.Ti rilassi e raggiungi la biglietteria 5 minuti prima dello spettacolo.Sono sicuro che puoi indovinare cosa succede:è una casa piena.Il problema qui era nella durata tra il controllo e l'azione.Hai chiesto informazioni alle 4 e hai agito alle 5.Nel frattempo qualcun altro ha preso i biglietti.Questa è una condizione di gara, in particolare uno scenario "controlla e poi agisci" delle condizioni di gara.

Come rilevarli?

Revisione del codice religioso, unit test multi-thread.Non esiste una scorciatoia.Ci sono pochi plugin Eclipse emergenti su questo, ma ancora niente di stabile.

Come gestirli e prevenirli?

La cosa migliore sarebbe creare funzioni senza effetti collaterali e senza stato, utilizzare il più possibile gli immutabili.Ma ciò non è sempre possibile.Pertanto, sarà utile utilizzare java.util.concurrent.atomic, strutture di dati simultanee, una corretta sincronizzazione e una concorrenza basata sugli attori.

La migliore risorsa per la concorrenza è JCIP.Puoi anche ottenerne altri dettagli sulla spiegazione sopra qui.

Answer 4

Esiste un'importante differenza tecnica tra le condizioni di gara e le gare con dati.La maggior parte delle risposte sembra presupporre che questi termini siano equivalenti, ma non lo sono.

Una gara di dati avviene quando 2 istruzioni accedono alla stessa locazione di memoria, almeno uno di questi accessi è di scrittura e non c'è avviene prima dell'ordine tra questi accessi.Ora, ciò che costituisce un ordine accade prima è soggetto a molti dibattiti, ma in generale le coppie ulock-lock sulla stessa variabile di blocco e le coppie segnale di attesa sulla stessa variabile di condizione inducono un ordine accade prima.

Una condizione di competizione è un errore semantico.È un difetto che si verifica nella tempistica o nell'ordine degli eventi che porta a un programma errato comportamento.

Molte condizioni di gara possono essere (e in effetti lo sono) causate da gare di dati, ma ciò non è necessario.È un dato di fatto, la corsa ai dati e le condizioni di gara non sono né la condizione necessaria né sufficiente l’una per l’altra. Questo Anche il post sul blog spiega molto bene la differenza, con un semplice esempio di transazione bancaria.Ecco un altro semplice esempio questo spiega la differenza.

Ora che abbiamo chiarito la terminologia, proviamo a rispondere alla domanda iniziale.

Dato che le condizioni di competizione sono bug semantici, non esiste un modo generale per rilevarli.Questo perché non esiste modo di avere un oracolo automatizzato in grado di distinguere quello corretto da quello corretto.comportamento errato del programma nel caso generale.Il rilevamento della razza è un problema indecidibile.

D'altra parte, la corsa ai dati ha una definizione precisa che non necessariamente si riferisce alla correttezza, e quindi è possibile rilevarla.Esistono molte versioni di rilevatori di competizione di dati (rilevamento di competizione di dati statico/dinamico, rilevamento di competizione di dati basato su lockset, rilevamento di competizione di dati basato su "accade prima", rilevamento di competizione di dati ibrido).È un rilevatore di dati dinamici all'avanguardia ThreadSanitizer che funziona molto bene nella pratica.

La gestione delle gare di dati in generale richiede una certa disciplina di programmazione per indurre i limiti che si verificano prima tra gli accessi ai dati condivisi (durante lo sviluppo o una volta rilevati utilizzando gli strumenti sopra menzionati).questo può essere fatto attraverso lock, variabili di condizione, semafori, ecc.Tuttavia, si possono anche impiegare diversi paradigmi di programmazione come lo scambio di messaggi (invece della memoria condivisa) che evitano la corsa dei dati per costruzione.

Answer 5

Una sorta di definizione canonica è "quando due thread accedono contemporaneamente alla stessa posizione in memoria e almeno uno degli accessi è in scrittura." Nella situazione in cui il thread "lettore" potrebbe ottenere il vecchio valore o il nuovo valore, a seconda di quale thread "vince la gara." Questo non è sempre un bug: in effetti, alcuni algoritmi di basso livello davvero pelosi lo fanno su scopo, ma generalmente dovrebbe essere evitato.@Steve Gury fornisce un buon esempio di quando potrebbe essere un problema.

Answer 6

Una race condition è una sorta di bug, che si verifica solo con determinate condizioni temporali.

Esempio:Immagina di avere due thread, A e B.

Nel thread A:

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

Nel thread B:

object.a = 0

Se il thread A viene interrotto subito dopo aver verificato che object.a non sia nullo, lo farà B a = 0, e quando il thread A acquisirà il processore, eseguirà una "divisione per zero".

Questo bug si verifica solo quando il thread A viene interrotto subito dopo l'istruzione if, è molto raro, ma può succedere.

Answer 7

Le condizioni di competizione si verificano in applicazioni multi-thread o sistemi multi-processo.Una condizione di competizione, nella sua forma più elementare, è tutto ciò che presuppone che due cose che non rientrano nello stesso thread o processo accadranno in un ordine particolare, senza adottare misure per garantire che ciò accada.Ciò accade comunemente quando due thread passano messaggi impostando e controllando le variabili membro di una classe a cui entrambi possono accedere.C'è quasi sempre una condizione di competizione quando un thread chiama sleep per dare a un altro thread il tempo di completare un'attività (a meno che sleep non sia in un ciclo, con qualche meccanismo di controllo).

Gli strumenti per prevenire le condizioni di competizione dipendono dalla lingua e dal sistema operativo, ma alcuni comuni sono mutex, sezioni critiche e segnali.I mutex sono utili quando vuoi assicurarti di essere l'unico a fare qualcosa.I segnali sono utili quando vuoi assicurarti che qualcun altro abbia finito di fare qualcosa.Ridurre al minimo le risorse condivise può anche aiutare a prevenire comportamenti imprevisti

Rilevare le condizioni di gara può essere difficile, ma ci sono un paio di segnali.Il codice che fa molto affidamento sulle modalità di sospensione è soggetto a condizioni di competizione, quindi controlla prima le chiamate alla modalità di sospensione nel codice interessato.L'aggiunta di sleep particolarmente lunghi può essere utilizzata anche per il debug per provare a forzare un particolare ordine di eventi.Questo può essere utile per riprodurre il comportamento, vedere se è possibile farlo scomparire modificando i tempi delle cose e per testare le soluzioni messe in atto.I posti letto dovrebbero essere rimossi dopo il debug.

Tuttavia, il segno distintivo che si ha una condizione di competizione è se c'è un problema che si verifica solo in modo intermittente su alcune macchine.I bug più comuni sarebbero arresti anomali e deadlock.Con la registrazione, dovresti essere in grado di trovare l'area interessata e tornare da lì.

Answer 8

Le condizioni di gara non sono legate solo al software ma anche all'hardware.In realtà il termine è stato inizialmente coniato dall'industria dell'hardware.

Secondo Wikipedia:

Il termine ha origine dall'idea di due segnali che si sfregano tra loro A influenzare prima l'output.

Condizione di competizione in un circuito logico:

L'industria del software ha adottato questo termine senza modifiche, il che lo rende un po' difficile da comprendere.

È necessario fare qualche sostituzione per mapparlo nel mondo del software:

• "due segnali" => "due thread"/"due processi"
• "influenza l'output" => "influenza alcuni stati condivisi"

Quindi la condizione di competizione nell'industria del software significa "due thread"/"due processi" che gareggiano tra loro per "influenzare uno stato condiviso", e il risultato finale dello stato condiviso dipenderà da alcune sottili differenze temporali, che potrebbero essere causate da alcuni specifici ordine di avvio di thread/processi, pianificazione di thread/processi, ecc.

Answer 9

Una race condition è una situazione di programmazione simultanea in cui due thread o processi concorrenti competono per una risorsa e lo stato finale risultante dipende da chi ottiene per primo la risorsa.

Answer 10

Microsoft in realtà ha pubblicato un documento davvero dettagliato articolo su questa questione di condizioni di gara e situazioni di stallo.L’abstract più riassuntivo sarebbe il paragrafo del titolo:

Una condizione di gara si verifica quando due thread accedono ad una variabile condivisa a Alla stessa ora.Il primo thread legge la variabile, e il secondo thread legge lo stesso valore dalla variabile.Poi il primo thread e secondo thread eseguono le loro operazioni sul valore, e corrono per vedere quale thread può scrivere l'ultimo valore alla variabile condivisa.Il valore del thread che scrive il suo valore ultimo è conservato, perché il thread sta sovrascrivendo il valore che il thread precedente ha scritto.

Answer 11

Cos'è una condizione di gara?

La situazione in cui il processo dipende in modo critico dalla sequenza o dalla tempistica di altri eventi.

Ad esempio: Trasformatore A e trasformatore B entrambe le esigenze risorsa identica per la loro esecuzione.

Come rilevarli?

Esistono strumenti per rilevare automaticamente la condizione di competizione:

• Controllo di gara basato su Lockset
• Succede prima del rilevamento della gara
• Rilevamento di razze ibride

Come li gestisci?

La condizione di competizione può essere gestita da Mutex O Semafori.Fungono da blocco e consentono a un processo di acquisire una risorsa in base a determinati requisiti per prevenire condizioni di competizione.

Come evitare che si verifichino?

Esistono vari modi per prevenire le condizioni di gara, ad esempio Evitamento della sezione critica.

1. Non esistono due processi contemporaneamente all'interno delle loro regioni critiche.(Esclusione reciproca)
2. Non vengono fatte ipotesi sulla velocità o sul numero di CPU.
3. Nessun processo in esecuzione al di fuori della sua regione critica che blocca altri processi.
4. Nessun processo deve aspettare per sempre per entrare nella sua regione critica.(A attende le risorse B, B attende le risorse C, C attende le risorse A)

Answer 12

Una race condition è una situazione indesiderata che si verifica quando un dispositivo o un sistema tenta di eseguire due o più operazioni contemporaneamente ma, a causa della natura del dispositivo o del sistema, le operazioni devono essere eseguite nella sequenza corretta per poter essere eseguite. fatto correttamente.

Nella memoria o nell'archiviazione del computer, può verificarsi una condizione di competizione se i comandi per leggere e scrivere una grande quantità di dati vengono ricevuti quasi nello stesso istante e la macchina tenta di sovrascrivere alcuni o tutti i vecchi dati mentre tali vecchi dati sono ancora in fase di elaborazione. Leggere.Il risultato può essere uno o più dei seguenti:un arresto anomalo del computer, una "operazione illegale", notifica e chiusura del programma, errori nella lettura dei vecchi dati o errori nella scrittura dei nuovi dati.

Answer 13

Ecco il classico esempio del saldo del conto bancario che aiuterà i principianti a comprendere facilmente i thread in Java rispetto acondizioni di gara:

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));

}

Answer 14

Prova questo esempio di base per una migliore comprensione delle condizioni di gara:

    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;
        }
    }
}

Answer 15

Non è sempre consigliabile scartare una condizione di gara.Se hai un flag che può essere letto e scritto da più thread e questo flag è impostato su 'done' da un thread in modo che l'altro thread interrompa l'elaborazione quando il flag è impostato su 'done', non vuoi che "gara condizione" da eliminare.In effetti, questa può essere definita una condizione di razza benigna.

Tuttavia, utilizzando uno strumento per il rilevamento della race condition, questa verrà individuata come dannosa.

Maggiori dettagli sulle condizioni di gara qui, http://msdn.microsoft.com/en-us/magazine/cc546569.aspx.

Answer 16

Considera un'operazione che deve visualizzare il conteggio non appena il conteggio viene incrementato.cioè, non appena Controfilo incrementa il valore DisplayThread deve visualizzare il valore aggiornato di recente.

int i = 0;

Produzione

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

Qui Controfilo ottiene il blocco frequentemente e aggiorna il valore prima DisplayThread lo visualizza.Qui esiste una condizione di gara.La Race Condition può essere risolta utilizzando la sincronizzazione

Answer 17

Puoi prevenire le condizioni di gara, se usi le classi "Atomiche".Il motivo è semplicemente che il thread non separa l'operazione get e set, l'esempio è seguente:

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

Di conseguenza, ne avrai 7 nel collegamento "ai".Sebbene tu abbia eseguito due azioni, ma entrambe le operazioni confermano lo stesso thread e nessun altro thread interferirà con questo, ciò significa che non ci sono condizioni di competizione!

Answer 18

Una race condition è una situazione indesiderata che si verifica quando due o più processi possono accedere e modificare i dati condivisi contemporaneamente. Si è verificata perché si erano verificati accessi contrastanti a una risorsa.Il problema della sezione critica può causare una condizione di competizione.Per risolvere le condizioni critiche nel processo, abbiamo eliminato un solo processo alla volta che esegue la sezione critica.

Answer 19

public class Synchronized_RACECONDITION {
    private static final int NUM_INCREMENTS = 10000;

    private static int count = 0;

    public static void main(String[] args) {
        testSyncIncrement();
        testNonSyncIncrement();
    }

    private static void testSyncIncrement() {
        count = 0;

        ExecutorService executor = Executors.newFixedThreadPool(2);

        IntStream.range(0, NUM_INCREMENTS)
                .forEach(i -> executor.submit(Synchronized_RACECONDITION::incrementSync));

        ConcurrentUtils.stop(executor);

        System.out.println("   Sync: " + count);
    }

    private static void testNonSyncIncrement() {
        count = 0;

        ExecutorService executor = Executors.newFixedThreadPool(2);

        IntStream.range(0, NUM_INCREMENTS)
                .forEach(i -> executor.submit(Synchronized_RACECONDITION::increment));

        ConcurrentUtils.stop(executor);

        System.out.println("NonSync: " + count);
    }

    private static synchronized void incrementSync() {
        count = count + 1;
    }

    private static void increment() {
        count = count + 1;
    }
static  class ConcurrentUtils {

    public static void stop(ExecutorService executor) {
        try {
            executor.shutdown();
            executor.awaitTermination(60, TimeUnit.SECONDS);
        }
        catch (InterruptedException e) {
            System.err.println("termination interrupted");
        }
        finally {
            if (!executor.isTerminated()) {
                System.err.println("killing non-finished tasks");
            }
            executor.shutdownNow();
        }
    }
}
}