Co jest warunkiem wyścigu?

Podczas pisania aplikacji wielowątkowych jednym z najczęstszych problemów są warunki wyścigowe.

Moje pytania do społeczności to:

Jaki jest stan wyścigu?
Jak je wykrywasz?
Jak sobie z nimi radzisz?
Wreszcie, w jaki sposób zapobiegasz ich występowaniu?

Wyścig występuje, gdy dwa lub więcej wątków może uzyskać dostęp do współużytkowanych danych i próbują je zmienić w tym samym czasie. Ponieważ algorytm planowania wątków może w dowolnym momencie przełączać się między wątkami, nie znasz kolejności, w której wątki będą próbowały uzyskać dostęp do udostępnionych danych. Dlatego wynik zmiany danych zależy od algorytmu szeregowania wątków, tzn. Oba wątki „ścigają się” w celu uzyskania dostępu / zmiany danych.

Często występują problemy, gdy jeden wątek wykonuje polecenie „sprawdź, a następnie działaj” (np. „Sprawdź”, jeśli wartość wynosi X, a następnie „działaj”, aby zrobić coś, co zależy od wartości będącej X), a inny wątek robi coś z wartością w między „czekiem” a „aktem”. Na przykład:

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

Chodzi o to, że y może wynosić 10, lub może być czymkolwiek, w zależności od tego, czy inny wątek zmienił x pomiędzy sprawdzeniem a działaniem. Nie masz prawdziwej wiedzy.

Aby zapobiec występowaniu warunków wyścigu, zwykle blokujesz udostępnione dane, aby zapewnić, że tylko jeden wątek może uzyskać dostęp do danych na raz. Oznaczałoby to coś takiego:

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

„Warunek wyścigu” istnieje, gdy wielowątkowy (lub w inny sposób równoległy) kod, który miałby dostęp do zasobu współdzielonego, mógłby to zrobić w taki sposób, aby spowodować nieoczekiwane wyniki.

Weź ten przykład:

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

Jeśli miałeś 5 wątków wykonujących ten kod jednocześnie, wartość x NIE NALEŻY skończyć na 50 000 000. W rzeczywistości zmieniałby się przy każdym uruchomieniu.

Wynika to z tego, że aby każdy wątek mógł zwiększyć wartość x, muszą wykonać następujące czynności: (oczywiście uproszczone)

Pobierz wartość x
Dodaj 1 do tej wartości
Zapisz tę wartość na x

Dowolny wątek może być na dowolnym etapie tego procesu w dowolnym momencie i może nadepnąć na siebie, gdy zaangażowany jest zasób współdzielony. Stan x może być zmieniony przez inny wątek podczas odczytywania x i gdy jest on ponownie zapisywany.

Powiedzmy, że wątek pobiera wartość x, ale jeszcze jej nie zapisał. Inny wątek może również pobrać tę samą wartość x (ponieważ żaden wątek go jeszcze nie zmienił), a następnie oba zapisywałyby tę samą wartość (x + 1) z powrotem w x!

Przykład:

Wątek 1: czyta x, wartość wynosi 7
Wątek 1: dodaj 1 do x, wartość wynosi teraz 8
Wątek 2: czyta x, wartość wynosi 7
Wątek 1: przechowuje 8 na x
Wątek 2: dodaje 1 do x, wartość wynosi teraz 8
Wątek 2: przechowuje 8 na x

Można uniknąć warunków wyścigu, stosując jakiś mechanizm blokujący przed kodem, który uzyskuje dostęp do udostępnionego zasobu:

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

Tutaj odpowiedź pojawia się za każdym razem w wysokości 50 000 000.

Aby uzyskać więcej informacji na temat blokowania, wyszukaj: mutex, semafor, sekcja krytyczna, zasób udostępniony.

Co to jest stan wyścigu?

Planujesz pójść do kina o 17:00. Zapytaj o dostępność biletów o 16.00. Przedstawiciel mówi, że są dostępne. Odprężasz się i docierasz do okna biletu na 5 minut przed koncertem. Jestem pewien, że możesz zgadnąć, co się stanie: to jest dom pełen. Problem polegał na czasie między sprawdzeniem a działaniem. Zapytałeś o 4 i działałeś o 5. W międzyczasie ktoś inny wziął bilety. To warunek wyścigu - w szczególności scenariusz warunków wyścigu „sprawdź, a następnie działaj”.

Jak je wykrywasz?

Przegląd kodu religijnego, wielowątkowe testy jednostkowe. Nie ma skrótu. Pojawia się niewiele wtyczek Eclipse, ale nic jeszcze nie jest stabilne.

Jak sobie z nimi radzić i jak im zapobiegać?

Najlepiej byłoby stworzyć funkcje wolne od skutków ubocznych i bezpaństwowe, w miarę możliwości używać niezmiennych. Ale nie zawsze jest to możliwe. Pomoże to w użyciu java.util.concurrent.atomic, współbieżnych struktur danych, właściwej synchronizacji i współbieżności opartej na aktorach.

Najlepszym źródłem współbieżności jest JCIP. Możesz również uzyskać więcej szczegółowych informacji na temat powyższego wyjaśnienia tutaj .

Istnieje istotna różnica techniczna między warunkami wyścigu a wyścigami danych. Większość odpowiedzi wydaje się przyjmować założenie, że te terminy są równoważne, ale nie są.

Wyścig danych ma miejsce, gdy 2 instrukcje uzyskują dostęp do tego samego miejsca w pamięci, co najmniej jeden z tych dostępów to zapis i przed złożeniem zamówienia między tymi dostępami nie ma miejsca. Teraz to, co dzieje się przed złożeniem zamówienia, jest przedmiotem wielu dyskusji, ale generalnie pary ulock-lock na tej samej zmiennej blokującej i pary sygnał oczekiwania na tej samej zmiennej warunkowej wywołują zdarzenie poprzedzające zamówienie.

Warunek wyścigu jest błędem semantycznym. Jest to usterka występująca w czasie lub porządku zdarzeń, która prowadzi do błędnego zachowania programu .

Wiele warunków wyścigu może być (i faktycznie jest) spowodowanych wyścigami danych, ale nie jest to konieczne. W rzeczywistości wyścigi danych i warunki wyścigu nie są ani koniecznym, ani wystarczającym warunkiem dla siebie nawzajem. Ten post na blogu również bardzo dobrze wyjaśnia różnicę na prostym przykładzie transakcji bankowej. Oto kolejny prosty przykład, który wyjaśnia różnicę.

Teraz, kiedy dopracowaliśmy terminologię, spróbujmy odpowiedzieć na pierwotne pytanie.

Biorąc pod uwagę, że warunki rasowe to błędy semantyczne, nie ma ogólnego sposobu ich wykrywania. Wynika to z faktu, że nie ma możliwości posiadania zautomatyzowanej wyroczni, która w ogólnym przypadku byłaby w stanie odróżnić prawidłowe i niepoprawne zachowanie programu. Wykrywanie rasy jest nierozstrzygalnym problemem.

Z drugiej strony rasy danych mają precyzyjną definicję, która niekoniecznie odnosi się do poprawności, a zatem można je wykryć. Istnieje wiele odmian detektorów wyścigów danych (wykrywanie wyścigów danych statycznych / dynamicznych, wykrywanie wyścigów danych na podstawie lockset, wykrywanie wyścigów na podstawie zdarzeń sprzed zdarzeń, wykrywanie wyścigów hybrydowych). Najnowocześniejszym detektorem dynamicznych wyścigów danych jest ThreadSanitizer, który działa bardzo dobrze w praktyce.

Ogólnie rzecz biorąc, obsługa wyścigów danych wymaga pewnej dyscypliny programistycznej, zanim dojdzie do krawędzi między dostępem do współdzielonych danych (podczas opracowywania lub po ich wykryciu za pomocą wyżej wymienionych narzędzi). można tego dokonać za pomocą blokad, zmiennych warunkowych, semaforów itp. Można jednak zastosować różne paradygmaty programowania, takie jak przekazywanie komunikatów (zamiast pamięci współużytkowanej), które pozwalają uniknąć wyścigów danych przez konstrukcję.

W pewnym sensie kanoniczną definicją jest „ gdy dwa wątki uzyskują dostęp do tego samego miejsca w pamięci w tym samym czasie, a przynajmniej jeden z dostępów to zapis ”. W tej sytuacji wątek „czytnik” może otrzymać starą lub nową wartość, w zależności od tego, który wątek „wygrywa wyścig”. Nie zawsze jest to błąd - w rzeczywistości niektóre naprawdę owłosione algorytmy niskiego poziomu robią to celowo - ale ogólnie należy tego unikać. @ Steve Gury daje dobry przykład, kiedy może to stanowić problem.

Wyścig jest rodzajem błędu, który zdarza się tylko w pewnych warunkach czasowych.

Przykład: wyobraź sobie, że masz dwa wątki, A i B.

W wątku A:

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

W wątku B:

object.a = 0

Jeśli wątek A zostanie zatrzymany tuż po sprawdzeniu tego obiektu. A nie jest zerowy, B zrobi to a = 0, a gdy wątek A zyska procesor, wykona „dzielenie przez zero”.

Ten błąd występuje tylko wtedy, gdy wątek A jest blokowany tuż po instrukcji if, jest to bardzo rzadkie, ale może się zdarzyć.

Wyścig jest związany nie tylko z oprogramowaniem, ale także ze sprzętem. Właściwie termin ten został ukuty przez przemysł sprzętowy.

Według wikipedii :

Termin wywodzi się z idei dwóch sygnałów, które ścigają się wzajemnie, aby najpierw wpłynąć na wynik .

Stan wyścigu w obwodzie logicznym:

Branża oprogramowania przyjęła ten termin bez modyfikacji, co utrudnia jego zrozumienie.

Musisz dokonać wymiany, aby zmapować go do świata oprogramowania:

• „dwa sygnały” => „dwa wątki” / „dwa procesy”
• „wpływ na wyjście” => „wpływ na stan wspólny”

Tak więc stan wyścigu w branży oprogramowania oznacza „dwa wątki” / „dwa procesy” ścigające się wzajemnie, aby „wpłynąć na jakiś wspólny stan”, a ostateczny wynik tego wspólnego stanu będzie zależał od pewnych subtelnych różnic czasowych, które mogą być spowodowane przez pewne określone kolejność uruchamiania wątków / procesów, planowanie wątków / procesów itp.

Warunkiem wyścigu jest sytuacja w programowaniu współbieżnym, w której dwa współbieżne wątki lub procesy konkurują o zasób, a wynikowy stan końcowy zależy od tego, kto pobierze zasób jako pierwszy.

Warunki wyścigu występują w aplikacjach wielowątkowych lub systemach wieloprocesowych. Warunek wyścigu, w swojej najbardziej podstawowej formie, jest wszystkim, co sprawia, że ​​zakłada się, że dwie rzeczy nie w tym samym wątku lub procesie wystąpią w określonej kolejności, bez podjęcia kroków w celu zapewnienia, że ​​tak się stanie. Dzieje się tak często, gdy dwa wątki przekazują wiadomości, ustawiając i sprawdzając zmienne składowe klasy, do której oba mają dostęp. Prawie zawsze występuje wyścig, gdy jeden wątek wywołuje tryb uśpienia, aby dać drugiemu czas na zakończenie zadania (chyba że sen jest w pętli z pewnym mechanizmem sprawdzającym).

Narzędzia do zapobiegania warunkom wyścigowym zależą od języka i systemu operacyjnego, ale niektóre z nich to muteksy, sekcje krytyczne i sygnały. Muteksy są dobre, gdy chcesz mieć pewność, że tylko Ty coś robisz. Sygnały są dobre, gdy chcesz mieć pewność, że ktoś już coś zrobił. Minimalizowanie udostępnionych zasobów może również pomóc w zapobieganiu nieoczekiwanym zachowaniom

Wykrywanie warunków wyścigu może być trudne, ale jest kilka znaków. Kod, który w dużej mierze opiera się na snach, jest podatny na warunki wyścigowe, więc najpierw sprawdź wezwania do spania w odpowiednim kodzie. Dodanie szczególnie długich snów może być również wykorzystane do debugowania w celu wymuszenia określonej kolejności zdarzeń. Może to być przydatne do odtworzenia zachowania, sprawdzenia, czy można go usunąć poprzez zmianę czasu rzeczy oraz do testowania wdrożonych rozwiązań. Uśpienia powinny zostać usunięte po debugowaniu.

Znakiem rozpoznawczym, że jeden ma warunek wyścigu, jest problem występujący sporadycznie tylko na niektórych maszynach. Typowymi błędami byłyby awarie i impasy. Po zalogowaniu powinieneś być w stanie znaleźć dotknięty obszar i wrócić do niego.

Microsoft opublikował naprawdę szczegółowy artykuł na temat warunków wyścigu i impasu. Najbardziej streszczonym streszczeniem byłby tytułowy akapit:

Warunek wyścigu występuje, gdy dwa wątki uzyskują dostęp do wspólnej zmiennej w tym samym czasie. Pierwszy wątek odczytuje zmienną, a drugi wątek odczytuje tę samą wartość ze zmiennej. Następnie pierwszy wątek i drugi wątek wykonują operacje na wartości i ścigają się, aby sprawdzić, który wątek może zapisać wartość jako ostatnią do zmiennej współdzielonej. Wartość wątku, który zapisuje ostatnią wartość, zostaje zachowana, ponieważ wątek zapisuje wartość zapisaną przez poprzedni wątek.

Co jest warunkiem wyścigu?

Sytuacja, w której proces jest krytycznie zależny od sekwencji lub czasu innych zdarzeń.

Na przykład procesor A i procesor B potrzebują identycznych zasobów do ich wykonania.

Jak je wykrywasz?

Istnieją narzędzia do automatycznego wykrywania warunków wyścigu:

• Kontroler wyścigów oparty na systemie Lockset
• Wydarza się przed wykryciem rasy
• Wykrywanie rasy hybrydowej

Jak sobie z nimi radzisz?

Warunkiem wyścigu może być Mutex lub Semaphores . Działają jak blokada, umożliwiając procesowi pozyskiwanie zasobów w oparciu o określone wymagania, aby zapobiec wyścigowi.

Jak zapobiegać ich występowaniu?

Istnieją różne sposoby zapobiegania stanom wyścigowym, takie jak unikanie sekcji krytycznych .

1. Nie ma dwóch procesów jednocześnie w ich krytycznych regionach. ( Wzajemne wykluczenie)
2. Nie poczyniono żadnych założeń dotyczących szybkości ani liczby procesorów.
3. Żaden proces nie działa poza obszarem krytycznym, który blokuje inne procesy.
4. Żaden proces nie musi czekać wiecznie, aby wejść do swojego krytycznego regionu. (A czeka na zasoby B, B czeka na zasoby C, C czeka na zasoby A)

Wyścig to niepożądana sytuacja, która występuje, gdy urządzenie lub system próbuje wykonać dwie lub więcej operacji jednocześnie, ale ze względu na naturę urządzenia lub systemu, operacje muszą być wykonane we właściwej kolejności, aby były wykonane poprawnie.

W pamięci komputera lub w pamięci może wystąpić wyścig, jeśli polecenia do odczytu i zapisu dużej ilości danych zostaną odebrane prawie w tym samym momencie, a maszyna podejmie próbę zastąpienia niektórych lub wszystkich starych danych, gdy te stare dane są nadal przetwarzane czytać. Rezultatem może być jedna lub więcej z następujących przyczyn: awaria komputera, „nielegalna operacja”, powiadomienie i zamknięcie programu, błędy odczytu starych danych lub błędy zapisu nowych danych.

Oto klasyczny przykład salda konta bankowego, który pomoże początkującym zrozumieć wątki w Javie w prosty sposób na warunki wyścigu:

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

}

Możesz zapobiec warunkom wyścigowym , jeśli użyjesz klas „Atomowych”. Powodem jest to, że wątek nie rozdziela operacji pobierania i ustawiania, przykład poniżej:

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

W rezultacie będziesz mieć 7 w linku „ai”. Chociaż wykonałeś dwie akcje, ale obie operacje potwierdzają ten sam wątek i żaden inny wątek nie będzie w to przeszkadzał, co oznacza brak warunków wyścigu!

Wypróbuj ten podstawowy przykład, aby lepiej zrozumieć warunki wyścigu:

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

Nie zawsze chcesz odrzucić warunek wyścigu. Jeśli masz flagę, która może być odczytywana i zapisywana przez wiele wątków, a ta flaga jest ustawiona na „zrobione” przez jeden wątek, tak aby inny wątek zatrzymał przetwarzanie, gdy flaga jest ustawiona na „zrobione”, nie chcesz, aby ten wyścig warunek ”do wyeliminowania. W rzeczywistości ten można nazwać łagodnym stanem rasy.

Jednak za pomocą narzędzia do wykrywania stanu wyścigu zostanie wykryte jako szkodliwy stan wyścigu.

Więcej informacji na temat warunków wyścigu tutaj, http://msdn.microsoft.com/en-us/magazine/cc546569.aspx .

Rozważ operację, która musi wyświetlać liczbę, gdy tylko liczba zostanie zwiększona. tzn. jak tylko CounterThread zwiększy wartość DisplayThread musi wyświetlić ostatnio zaktualizowaną wartość.

int i = 0;

Wynik

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

Tutaj CounterThread często otrzymuje blokadę i aktualizuje wartość, zanim DisplayThread ją wyświetli. Tutaj istnieje warunek wyścigu. Stan wyścigu można rozwiązać za pomocą synchronizacji

Warunek wyścigu jest niepożądaną sytuacją, która występuje, gdy dwa lub więcej procesów może uzyskać dostęp do wspólnych danych i zmienić je jednocześnie. Krytyczny problem z sekcją może powodować wyścig. Aby rozwiązać krytyczny warunek procesu, wyjęliśmy tylko jeden proces naraz, który wykonuje sekcję krytyczną.