Java Concurrency

Streszczenie

Ogólnie

Zakładam że czytelnik wie co to jest wielowątkowść ogólnie. Jak nie wie niech przeczyta rozdział 13 'Thinking in Java' tu (patrzlinki).

Model wielowątkowości

Model wielowątkowości

Co możemy z tym zrobić:

Synchronizacja

JVM daje gwarancje że tylko jeden z bloków synchronizowanych na kluczu A będzie wykonywany na raz.
Ponadto wątki muszą synchronizować swoją pamięć z pamięcią główną kiedy zdowbywają klucz.
Kompilator może przestawiać kolejność wykonywania poleceń. Ale nie może przenieść poleceń z bloków synchronizowanych poza nie.
Nie gwarantuje to:
Kolejności wykonywania metod.

volatile

Jeśli zmienna jest volatile to wątki nie mogą wykonywać kopii jej z pamięci głównej do swojego kasza.

immutable

Jeśli zmienna jest immutable to (czyli jej stan się nie zmienia) to dowolna ilość wątków może z niej czytać.

Atomowość

Jeśli jakaś operacja jest atomowa oznacza to że jej wykonanie jest de facto jedną instrukcją procesora, czyli nie ma ona stanu pośredniego który może się spsuć.
Jednak
W Javie nie ma operacji atomoych poza java.util.concurrent.atomic. Nawet:

    i++;

nie jest atomowe. Szczególnie jeśli i to long, ale dla intów też nie daje rady.

Synchroniacja:

Jak się synchronizuje to każdy wie (zresztą nie wgryzłem się jeszcze w nowy framework do wielowątkowości z JDK6…, a staroci nie będę publikował!) Polecam zaznajomić się z java.util.concurrent, atomic, lock.

Ważne jest to czego synchronizacja nie gwarantuje:

Wady synchronizacji

Nie gwarantuje kolejności wykonywania funkcji.

Przykład niezsynchronizowany

Przykładowo:

class Sample {
 
    int a = 1, b = 2;
    void hither() {
        a = b;
    }
    void yon() {
        b = a;
    }
}

W klasie wątek A woła jedną metodę Sample wątek B drugą.

Wynikiem może być:

  • Zamiana wartości a i b.
  • a = b = 2 lub a = b = 1

Oraz może być tak że wątki A i B mają w swoich keszach niezgodne wartości np: A uważa że a = 1 a B uważa że a = 2.

Przykład zsynchronizowany

Jeśli metody zsynchrnonizumejy to możliwe będą tylko dwa wyniki:

  • a = b = 2 lub a = b = 1

Oraz wątki będą się zgadzały do do tego która możliwość zaszła.

Dokładniejsze analizy w [3].

Kolekcje

Problem:
Mamy w programie kolekcję z której niektóre wątki sobie czytają a inne do niej piszą1. Problem polega na tym że co jakiś czas leci ConcurrentModificationException.

Nie rozwiązanie
Rozwiązaniem nie jest synchronizacja kolekcji (z użyciem Collections.synchronizedXXX()).

** O co chodzi**
Ogólnie kolekcje mają mechanizm który powoduje że nie da się ich modyfikować strukturalnie i czytać w tej samej chwili. Mechnizm ten nie jest mechanizmem pewnym, raczej jest to best effort. I dotyczy on nie tyle operacji na samej kolekcji ale na jej widokach (i iteratorach) i powoduje rzucenie wyjątku jeśli z jakiegoś widoku czyta się dane które zostały zmodyfikowane za pomocą innego widoku (nawet w jednym wątku).

Czyli jeśli wątek A woła:

    map.get("foo");

Natomiast wątek B:

    map.remove("foo");

Wszystko jest cacy. Od kolejności wywołania wątków (i całej reszty…) zależy to czy A zobaczy "foo" w mapie czy nie.

Natomiast wyjątek poleci jeśli A będzie robić coś takiego:

     for(String a : list){
        /* cośtam */
    }

Natomiast w tym czasie (jakikolwiek wątek) zrobi:

    list.remove(1);

Wyjątek poleci nawet jeśli w w jednym wątku zostanie wykonane:

    for(Map.Entry<String, String> me : map.entrySet()){
        if(/*warunek*/){
            map.remove(me.getKey());
        }
    }

Tutaj synchronizacja nic nie pomoże.

Co gwarantuje synchronizacja
Że z kodu pobierającego własności z mapy nie będą leciały inne dziwne wyjątki.

Rozwiązanie tego problemu

Użyć odpowiendiem kolekcji z java.util.concurrent. Na przykład: ConcurrentSkipListMap działa w ten sposób że iteratory i widoki pokazują stan kolekcji z jakiegoś konkretnego punktu w czasie (i zmiany które nastąpiły po tym punkcie nie są odzwierciedlane).

StringBuffer

Nie używaj

Koszty synchronizacji

Synchronizacja jest bardzo drogą operacją. Wątki mają obowiązek synchronizować swój kesz z pamięcią główną podczas zdobywania klucza lub oddawania go (czyli podczas wchodzenia i wychodzenia z bloku synchronizowanego). A takie kopiowanie pamięci może być drogie i długotrwałe.

Deadlocki

Patrz thinking in java…

volatile

Jeśli zmienna jest volatile znaczy to tyle że wątek nie ma prawa skopiować jej do swojego kesza. Oraz że wszystkie dostępy (odczyty i zapisy) do zmiennych volatile będą się odbywać w tej kolejności co było w kodzie napisane.

Do czego służy volatile:

Jeśli jakaś zmienna ma być dostępna dla wielu wątków trzeba ją oznaczyć jako volatile.

Na przykład:

    class MyThread extends Thread{    
        private boolean kill = false;
        void kill(){
            kill = true; 
        }
        void doStuff(){
            /*Doing stuff*/
        }
        void run(){
            while(!kill){
                doStuff();
            }
        }
    }
    public static void main(String[] args){
        MyThread t = new MyThread();
        t.start();
        t.kill();
 
    }

MyThread ma działać tak że jeśli ktoś wywoła na obiekcie kill() zostanie ustawiona zmienna kill i wątek się po jakimś czasie wyłączy. Jest to bardzo często używany wzorzec - bo powoduje w miarę czyste zabicie wątka w sposób kontrolowany.

Ale to w ten sposób nie zadziała. Sekwencja zdarzeń będzie raczej taka:

  1. Utworzymy wątek
  2. Wywołamy funkcję start. W tym momencie zmienna kill jest kopiowana do pamięci wątku.
  3. Ustawiamy kill na true w pamięci głównej (ale wątek tego nie widzi), bo ma się synchronizować tylko w odpowiednich momentach

Żeby to zadziałało trzeba ustawić kill jako volatile.

private volatile boolean kill = false;

[1]

volatile a long i double

No to zgrubsza chodzi o to że JVM ma prawo zapisywać longa w dwóch rzutach - w piewszym pierwsze 32 bity - w drugim drugie. To może powodować odczyty bezsensownych danych. Jeśli zmienne są volatile nie będzie to możliwe.

Ale:
Żadna nowoczesna JVM tego nie robi

Do czego nie służy TODO

TODO

Niezmienność

Jeśli jakiś obiekt nie zmienia swojego stanu to jest bezpieczny.

Co to znaczy niezmienny.

Niezmienny nie znaczy nie zmienił swojego stanu od momentu utworzenia. Znaczy [2]:

  1. Można do niego dojść po ścieżce referencji z których pierwsza jest final.
  2. Zmienna final nie opuściła konstruktora przed jego wykonaniem.
  3. Obiekt sie nie zmienił się od czasu wykonania.

Dokładniej:

  1. W tym przykładzie foo.bar.baz spełnia pierwszy warunek
    class Bar{
        int baz;
    }
    class Foo{
        final Bar bar; 
    }
  1. 'Zmienna final nie opuściła konstruktora przed jego wykonaniem'

Z grubsza chodzi o to że wyrażenia mogą zostać poprzestawiane i jeśli mamy coś takiego:

    class Bar{
        public static Bar lastConstructedBar; 
        int baz;
    }
    class Foo{
        final Bar bar; 
        Foo(){
            bar =  new Bar(); 
            bar.baz = 1; 
            Bar.lastConstructedBar = bar;  
        }
    }

To w konstruktorze polecenia mogą zostać poprzestawiane do:

    Foo(){
            bar =  new Bar(); 
            Bar.lastConstructedBar = bar;  
            bar.baz = 1;         
        }

I jakiś wątek zobaczy bar ze zmienną baz ustawioną na 0. Zapisze sobie w keszu i już nigdy nie odczyta…

Atomowość

Operacja atomowe są bezpieczne dla wielu wątków.

Operacja atomowa to operacja w której nie ma stanu pośredniego, więc żaden wątek nie może odczytać złych danych (czyli właśnie tego stanu pośredniego) bo ich nie ma!

Nie to złoto co się świeci

Następujące operacje nie muszą być atomowe:

    i ++;
    i = 2L;

i tak dalej…

java.util.concurrent.atomic

CAS

Główną operacją atomową jest CAS - Compare And Set. Rozważmy takie coś - mamy sobie generator liczb losowych, który ma sobie zmienną seed żeby generator działał w wielu wątkach, ale nie chcemy go explicite synchronizować. Nie może też być tak że zwróci (nawet w dwóch wątkach) tą samą liczbę losową.

Czyli musimy zrobić takie operacje (pseudokod)

    long seed = this.seed; 
    /*inicjalizacja nowej wartości ziarna*/ //1
    this.seed = seed; //Zapisanie nowej wartości ziarna.
    /*wygenerowanie z ziarna liczby losowej (czyli inta)*/ 
    return random;

Jedyną operacją która nas martwi jest 1. Może być tak że:

Wątek A odczyta this.seed.
Wątek B odczyta this.seed.
Wątek A zapisze nową wartość seed

No i oba zwrócą tą samą liczbę losową.

Robimy więc coś takiego:

  1. Odczytujemy do zmiennej oldSeed wartość ziarna.
  2. Generujemy do zmiennej newSeed nową wartość ziarna.
  3. Ustawiamy ziarno w obiekcie tylko jeśli się nie zmieniło. To znaczy że jeśli this.seed == oldSeed ustawiamy wartość. Jeśli nie wracamy do punktu 1.

java.util.Random

Na marginiesie: java.util.Random właśnie tak działa.

        long oldseed, nextseed; 
        AtomicLong seed = this.seed; 
        do {
        oldseed = seed.get(); //Pobranie aktualnej wartości zmiennej
        nextseed = (oldseed * multiplier + addend) & mask; //Wygenerowanie nowej
        } while (!seed.compareAndSet(oldseed, nextseed)); //Jeśli aktualna wartość 
        //się nie zmieniła to zapisujemy ją - jeśli nie to jeszcze raz. 
        return (int)(nextseed >>> (48 - bits));

Atomowe operacje arytmetyczne

Operacje arytmetyczne nie są atomowe:

    stanKonta+=20;

Składa się z:

  1. Odczytu wartości
  2. Dodania wartości
  3. Zapisu wartości

Może więc być tak:

  1. Wątek A czyta wartość stanKonta
  2. Wątek B czyta wartość stanKonta
  3. Wątek A dodaje 20 i zapisuje
  4. Wątek B dodaje 20 i zapisuje

I stan kąta wzrośnie o 20 (a nie 40!)

Stąd mamy w java.util.concurrent.atomic operacje takie jak incrementAndGet czy addAndGet które atomowo wykonują te operacje.

Duże implementacje korzytające tylko z atomowości:

Lock-Free HashTable

Inne podejścia

Można też do problemów wielowątkowości podejść od innej strony. To znaczy da się napisać program w którym wszyscy mają dostęp do wszystkiego a mimo to daje radę (z użyciem minimalnej synchronizacji).

Wzorzec Master - Worker

Mamy jeden wątek który jest wątkiem Master i odpowiada za COŚ, na przykład za interakcję z użytkownikiem, który wszystkie działania wymagające czasu (lub mogące się zablokować) deleguje do innych wątków robotników (które to zadanie wykonują asynchronicznie) i po jakimś czasie zwracają odpowiedź.

Swing używa właśnie tej architektury - wszystkie operacje na komponentach swingowych2 powinny być wołane ze specjalnego wątku zwanego EDT (Event Dispatching Thread).

Jeśli EDT się zablokuje (albo nagle zacznie coś obliczać) to cały interfejs przestanie odpowiadać. Dlatego wszystkie długotrwałe operacje powinno się wykonywać z innych wątków a w EDT zwracać ich wyniki.

Żeby to ułatwić JDK6 dostarcza klasę SwingWorker. Która jest zasadniczo itemem roboty do wykonania poza EDT i która potrafi po wykonaniu roboty odświerzyć UI.

Najporstsze użycie jest mniej więcej takie:

    SwingWorker foo = new SwingWorker(){
 
        //Wykonywane poza EDT.
        Object doInBackground(){
            /*Jakaś strasznie ciężka operacja, na 
            przykład czytanie pliku */
            return result; 
        }
 
        //Wykonywane w EDT
        void done(){
            Object result = get();
            /* Wyświetlenie wyniku */
        }
 
    }

O ile nie zaznaczono inaczej, treść tej strony objęta jest licencją Creative Commons Attribution-NonCommercial-NoDerivs 3.0 License