Scheduling

Several scheduling models exist, most of which are overkill. For all but truly exceptional programs, the normal vendor scheduler does a fine job and that, along with proper synchronization, means that we don’t have to worry about scheduling at all. Realtime folks are on their own. – “Multithreaded Programming with Java Technology”

Don’t have to worry. Uf. Zapamiętajmy na tę chwilę, że ze względu na to, że istnieją różne implementacje modeli schedulowania, nie powinniśmy uzależniać naszego wielowątkowego kodu od żadnego z nich. Nie zakładaj więc, że jeśli na Twoim komputerze wątki wykonują się X czasu i uruchamiane są z częstotliwością Y, to tak samo będzie się dziać na komputerze sąsiadki.

Spójrz na poniższy krótki kod. Tworzymy obiekt wątku, którego zadaniem (taskiem) jest wyświetlenie trzech zdań.

class MTApp {
    public static void main(String[] args) {
            Thread thread = new Thread(new MySimpleTask());
            thread.start();
            System.out.println("I'm main thread");
            System.out.println("I'm still the main thread");
    }

}

class MySimpleTask implements Runnable {

    @Override
    public void run() {
        print1();
    }

    void print1() {
        System.out.println("I'm mySimpleTask (print1)!");
        print2();
    }

    void print2() {
        System.out.println("I'm mySimpleTask (print2)!");
        print3();
    }

    void print3() {
        System.out.println("I'm mySimpleTask (print3)!");
    }
}

Wynik po pierwszym uruchomieniu:

 I'm main thread
 I'm still the main thread
 I'm mySimpleTask (print1)!
 I'm mySimpleTask (print2)!
 I'm mySimpleTask (print3)!

Wynik po drugim uruchomieniu:

I'm main thread
I'm mySimpleTask (print1)!
I'm mySimpleTask (print2)!
I'm mySimpleTask (print3)!
I'm still the main thread

Raptem dwa uruchomienia, a wyniki różnią się od siebie. W pierwszym przypadku wątek główny wykonał swoje zadanie, następnie czas procesora otrzymał drugi wątek wykonujący zadanie MySimpleTask. W drugim przypadku zaś wątek główny otrzymał czas na wykonanie, ale jednak tego czasu nie było na tyle dużo, aby zrealizował swoje zadanie. Więc po wyświetleniu I’m main thread czas na wykonanie otrzymał nasz wątek wykonujący zadanie MySimpleTask

W trzecim wypadku natomiast wynik naszego programu może być też taki:

I'm main thread
I'm mySimpleTask (print1)!
I'm still the main thread
I'm mySimpleTask (print2)!
I'm mySimpleTask (print3)!

Nie jesteśmy w stanie tego przewidzieć.

Jeśli jednak chcesz dowiedzieć się czegoś o scheduling models, context switching i innych pokrewnych tematach to są one opisane między innymi właśnie w książce “Multithreaded Programming with Java Technology”, rozdział nr 5 lub w Operating System Concepts, rozdział również (heh!!!1) nr 5

Synchronizacja

O co chodzi z tymi wątkami. Na czym nam zależy. Zależy nam na tym, aby wątki wykonywały swoją robotę szybko i w skoordynowany sposób. Co oznacza skoordynowany? Jeśli zadania wykonywane przez wątki zależą od siebie, bo realizują jeden cel, a wiemy że wątki współdzielą dane na których operują (oprócz sytuacji gdy nie dzielą i mają własną kopię danych :-)), to chcemy, aby te taski wątków były realizowane według jakiegoś mundrego planu. Takiego planu, który zagwarantuje naszym danym bezpieczeństwo. Chcemy zabezpieczyć się od sytuacji, gdy jeden wątek realizuje swoje zadanie, a w tym momencie drugi wątek zaczyna robić swoje na tych samych danych. Dane prawdopodobnie pozostaną w strzępach. Musimy pozwolić wątkowi dokończyć pracę, którą zaczął.

Poniższy przykład pokazuje co oznacza brak koordynacji tasków.

Rys. 1 “Multithreaded Programming with Java Technology”

Po lewej stronie mamy wątek nr 1, który bierze Twoje pieniążki (1000 zł), które masz na koncie, oblicza Twój zysk bo jesteś piękny (1000 * 0.01 = 10 zł) i aktualizuje to co masz na koncie, czyli zyskałeś z bycia pięknym gościem 10 zł, tj.: masz 1010 zł na koncie.

Drugi wątek zaś potrafi zrobić coś innego. Wpłacasz 2000 zł w bankomacie i wątek wykonuje zadanie pobrania tych pieniędzy i dopisania ich do tego co masz na koncie. No normalna rzecz.

JEDNAK!!!!1111~~ JEDNAK CO SIĘ STANIE GDY TE DWA MILUSIE WĄTKI ZACZNĄ DZIAŁAĆ W TYM SAMYM MOMENCIE. CO ZA PRZYPADEK, CO ZA NIESZCZĘŚCIE, ijo ijo ijo ijo.

Jeśli działanie tych wątków nałożyłoby się na siebie, to mimo, że wpłaciłeś właśnie pachnące 2000 zł z wizerunkami panów w koronach i dopisane zostały one do tysiaczka, który dostałeś od babuni na święta, to wątek nr 1 nic o tym nie wie. Smutna minka. On pobrał stan Twojego konta (1000 zł) zanim wątek nr 2 wykonał pierwszą operację albo zrobił to w tym samym momencie co wątek 2!!!!!!1111 Na koniec wątek nr 1 nadpisuje stan Twojego konta marnymi 1010 zł, za które, umówmy się, nie zaimponujesz Marysi.

Praca tych dwóch wątków zdecydowanie nie jest ze sobą skoordynowana i zsynchronizowana. Działają sobie beztrosko i nic ich nie intereserere.

Atomowość

Czyli wiemy, że jeśli jeden wątek wykonuje dwie operacje, np.: pobranie stanu konta, a następnie jego modyfikację, to między tymi dwiema czynnościami, drugi wątek może coś namieszać. Tzn., zaktualizować po swojemu stan konta w taki sposób, że pierwszy wątek nie będzie o tym wiedział. Chcemy takiej sytuacji uniknąć. Chcemy aby takie dwie instrukcje pobrania i modyfikacji danych zostały zrealizowane jako jedna instrukcja. Dzięki temu nie będzie między nimi odstępu czasowego (choćby to było 5 nanosekund) co zagwarantuje nam, że żaden inny wątek nie wtryni nam się ze swoim zadaniem.

Taki mechanizm jest możliwy dzięki atomowym instrukcjom. Atomowe zdarzenie wykona się lub nie. Nie ma stanów pośrednich. Taka instrukcja potrafi za jednym zamachem pobrać dane z pamięci i ustawić nową wartość. Dzięki czemu jesteśmy zabezpieczeni na wypadek opisanej wyżej sytuacji. Nie jest ważne ile wątków jednocześnie będzie chciało dokonać odczytu i modyfikacji danych – tylko jeden wątek będzie mógł to zrobić i żaden inny wątek tego nie zepsuje, tzn., żaden wątek nie pokrzyżuje planów dokończenia taska swojemu koledze. Kod, który musi wykonać się w taki atomowy sposób jest zwany sekcją krytyczną.

Jak żyć w takim razie

W powyższym przykładzie, z kontem, dwa wątki dzielą pewne dane. Dane konta. Dzielą pewien obiekt, do którego dostęp w danym momencie powinien mieć tylko jeden wątek. Ten wątek powinien móc rozpocząć operacje na tych danych i spokojnie je zakończyć bez obawy, że inny wątek również zacznie na nich operować.

Istotne jest dla nas zatem chronienie spójności, zniekształcenia danych. Tworząc kod kierujemy się pewnymi niezmiennikami, regułami, realizujemy jakiś kontrakt. Im lepiej on będzie zdefiniowany, im lepiej zadbamy o nasz kod stosując między innymi enkapsulację, tym łatwiej będzie nam zapanować nad zagrożeniem wiszącym nad naszymi danymi. Stosując odpowiednie techniki jesteśmy w stanie zadbać o to, że stan naszych danych nie ulegnie naruszeniu. Najfajniej by było, gdyby nasze obiekty miały jeden inicjalny stan i nie dałoby się w ogóle wprowadzić tego obiektu w jakikolwiek inny. Wtedy wątki mogą bawić się obiektem do woli i jesteśmy pewni, że nic złego się nie stanie. Mowa o klasach niemutowalnych. Możesz o nich przeczytać tu. Ale skoro piszemy już aplikację, za którą ktoś płaci grubą pengę, to prawdopodobnie znajdą się w Twojej aplikacji obiekty, które będą miały więcej niż jeden stan, np.: dla uproszczenia niech to będzie Account z właściwością State state, gdzie State to enum z wartościami Active oraz Inactive. Innym sposobem na poradzenie sobie z taką sytuacją jest wspomniana synchronizacja, a trzecim niewspółdzielenie stanu pomiędzy wątkami. O tym za jakiś czas.

Wróćmy do synchronizacji.

Synchronizacja na obiekcie

Synchronizacja pozwala nam zablokować kod w taki sposób, że tylko jeden wątek będzie mógł go wykonać w danym momencie. Synchronizacja gwarantuje, że żaden wątek nie będzie miał do czynienia z obiektem będącym w niespójnym stanie oraz to, że każdy wątek będzie świadomy zmian jakie wprowadził każdy inny wątek. Po realizacji swojego zadania, zalockowana wcześniej sekcja kodu zostaje odblokowana. Dopiero wówczas inny wątek może próbować nałożyć blokadę na rzecz swojej potrzeby wykonania zadania. Jeśli wątek założy lock na sekcję kodu, to próba założenia locka przez wątek B zakończy się niepowodzeniem i wątek B przejdzie w stan uśpienia. Gdy lock zostanie zwolniony, wątek B zostanie wybudzony. Jeśli mamy jeszcze oprócz tego wątek C, który również ma chętkę na założenie locka i wykonanie swojego zadania, to o tym, który wątek (B czy C) będzie miał pierwszeństwo zadecyduje pewien atrybut wątku – priorytet. Priorytet określa miejsce w kolejce śpiochów, na które trafi wątek w opisanym przypadku. Jeśli wątek C ma wyższy priorytet niż wątek B, to mimo że uśpiony wątek B wcześniej złożył rezerwację na locka, to pierwszeństwo otrzyma wątek C.

Wzajemne wykluczanie (MutEx) & Widoczność

class Account() {
   private int balance = 0;
   
   void synchronized withdrawal() {
      int tempBalance = balance.
      int balanceAfterWithdrawal = tempBalance - 50;
      balance = balanceAfterWithdrawal;
   }

   void synchronized deposit() {
      int tempBalance = balance.
      int balanceAfterDeposit = tempBalance + 100;
      balance = balanceAfterDeposit; 
   }
}

Po wykonaniu wpłaty 100 zł i wypłacie 50 zł lub na odwrót oczekuję, że na koncie będę miał tak czy siak 50 zł, zakładając że początkowy stan konta do 0 zł.

W powyższym fragmencie kodu operacje są rozbite na kilka przypisań, żebyśmy zobaczyli, że gdyby dwa wątki operowały na tym samym obiekcie Account, to jeden wątek mógłby rozpocząć operację withdrawal, nie zdążyć jej skończyć, gdy nagle i całkowicie niespodziewanie drugi wątek by zaczął swoją robotę (task deposit). Mogłoby to doprowadzić do (zakładamy póki co, że słówko synchronized nie istnieje w naszym fragmencie kodu):

  1. funkcja withdrawal zapamiętuje stan konta 0 zł w zmiennej tempBalance – zadanie wątku A
  2. funkcja deposit zostaje wówczas wykonana w całości przez wątek B. W tym momencie stan konta jest 0 + 100 = 100 zł.
  3. Wątek kończy swoją robotę przy wykorzystaniu zapamiętanego przez siebie wcześniej stanu konta. Czyli robi 0 – 50 = -50 i nadpisuje tą wartością zmienną balance, która przed sekundką została przecież zmodyfikowana przez wątek B. :-<

To ingerowanie jednego wątku w działania drugiego wątku, nakładanie się działań wątków, nazywane jest thread interference. A to z kolei może prowadzić do memory consistency errors.

Aby nie spotkały nas powyżej opisane problemy, użyliśmy konstruktów synchronized, które tworzą blokadę na poziomie obiektu.

Lock na poziomie obiektu, tzn.:

synchronized void deposit() { (...) }

jest równoważny z zapisem:

void deposit() { synchronized(this) { (...) } 

Jeśli mamy jeden obiekt i kilka wątków, które wykonują jakąś akcję (np.: synchronizowaną metodę deposit lub withdrawal) to w jednym momencie, tylko jeden wątek może wykonywać synchronizowaną metodę na obiekcie Account (tylko jeden wątek może uzyskać object lock). Każdy inny wątek, który będzie chciał wykonać jakąkolwiek synchronizowaną metodę obiektu Account będzie musiał poczekać aż pierwszy wątek zakończy działanie.

Słówko synchronized gwarantuje nam, że wątki nie wejdą sobie w drogę ze swoimi działaniami na współdzielonych zasobach (mutual exclusion). Możemy uzyskać w ten sposób atomowość, o której wspominałem na początku. Jednocześnie mamy gwarancję, że modyfikacje wprowadzone przez jeden wątek będą widoczne dla wszystkich innych (w końcu wątek uzyskał locka).

Krótki cytat odnośnie synchronizacji, z Concurrent programming in Java. Design Principles and Patterns:

The latter sense of synchronized may be viewed as a mechanism by which a method running in one thread indicates that it is willing to send and/or receive changes to variables to and from methods running in other threads.

Gwarancja widoczności, o której wspomniałem powyżej nosi nazwę happens-before relationship i konstrukt synchronized zdecydowanie nam to zagwarantuje. Mała uwaga: aby zapewnić widoczność nie trzeba zawsze używać słówka kluczowego synchronized. Jest też inny, nieraz lepszy sposób, o czym niebawem.

Cytat nr 1 odnośnie happens-before relationship (źródło tu)

The results of a write by one thread are guaranteed to be visible to a read by another thread only if the write operation happens-before the read operation.

I jeszcze krótki cytat nr 2 z dokumentacji Javy:

Every object has an intrinsic lock associated with it. By convention, a thread that needs exclusive and consistent access to an object’s fields has to acquire the object’s intrinsic lock before accessing them, and then release the intrinsic lock when it’s done with them. A thread is said to own the intrinsic lock between the time it has acquired the lock and released the lock. As long as a thread owns an intrinsic lock, no other thread can acquire the same lock. The other thread will block when it attempts to acquire the lock. When a thread releases an intrinsic lock, a happens-before relationship is established between that action and any subsequent acquisition of the same lock.

Wcale nie był to krótki cytat.

Volatile, widoczność

Locking can guarantee both visibility and atomicity; volatile variables can only guarantee visibility.Java Concurrency in practice.

Możemy chcieć, aby tylko jeden wątek mógł wykonać kod synchronizowanej metody, czyli naszej sekcji krytycznej. No i okej. Jeśli jest taka potrzeba to tak robimy i mamy zagwarantowane jednocześnie, że modyfikacja na współdzielonych danych, na których operujemy w ramach synchronizowanej metody będą widoczne dla wszystkich wątków. Istnieją jednak sytuacje, kiedy nie ma potrzeby synchronizowania metod, a widoczność będziemy mieli mimo to zagwarantowaną. Nie interesuje nas po prostu blokowanie wykonania metod przez więcej niż jeden wątek jednocześnie. Można sobie wyobrazić taką sytuację w przypadku, gdy mamy jeden wątek, który pisze do jakiejś zmiennej, a kilka wątków następnie czyta z tej zmiennej. Czyli mamy do czynienia z przypadkiem write/modify – read. Nie chcielibyśmy przecież, aby w takim przypadku zmodyfikowana wartość była ukryta dla któregoś z wątków. Jeśli chcesz przeczytać, dlaczego wartość modyfikowana przez wątek A może nie być widoczna dla wątku B zajrzyj tu. Skupmy się póki co na tym, że tak może się stać i chcemy tego uniknąć.

Widoczność zmian na zmiennej wykonywanych przez wątek A zostanie zagwarantowana przez słówko kluczowe volatile.

A write to a volatile field happens-before every subsequent read of that same field. Writes and reads of volatile fields have similar memory consistency effects as entering and exiting monitors, but do not entail mutual exclusion locking. (źródło)

Słówko kluczowe volatile zapewnia również widoczność zmiennym, które nie są oznaczone jako volatile, o ile są widoczne dla wątku zapisującego do zmiennej volatile. Uh. Dziwnie to brzmi. Na przykładzie.

Zacznijmy od przykładu bez użycia volatile. Konfigurujemy obiekt typu MyDataSource i po skonfigurowaniu ustawiamy flagę isDataSourceConfigured na true. Wówczas metoda start uruchamia nasz serwer. Whatever. 🙂

class MyVolatileApp {
    public static void main(String[] args) {
        ConfigureSomething ex = new ConfigureSomething();
        new Thread(() -> { ex.setUp(); }).start();
        new Thread(() -> { ex.start(); }).start();
    }
}
class ConfigureSomething {
    MyDataSource myDataSource = new MyDataSource();
    boolean isDataSourceConfigured = false;

    void setUp() {
        // below variables may be reordered by compiler
        myDataSource.hostname = "wprostychslowach.pl";
        isDataSourceConfigured = true;
    }

    void start() {
        while(!isDataSourceConfigured) {
            // do nothing
        }
        // Here I'm _not_ sure if myDataSource has been fully set up
        System.out.println("It's possible that we'll connect with dummy data source");
    }
}

class MyDataSource {
    public String hostname;
}

Nie użyliśmy ani synchronizacji, ani volatile. Mamy dwa wątki, których wykonanie może się nakładać. Wątek wykonujący task start może zacząć wykonywać swoje zadanie, gdy wątek setUp zdążył wykonać tylko jedno przypisanie (bo nie mamy zapewnionej atomowości). Nie jesteśmy w stanie stwierdzić jaki będzie rezultat programu. Nie wiemy więc czy modyfikacje znajdujące się w metodzie setUp będą widoczne dla wątku wykonującego task start. Może będą, może nie, a może tylko część. Zmienna isDataSourceConfigured może zostać ustawiona na true i drugi wątek odnotuje to, wyjdzie z pętli i spróbuje wystartować serwer z nieskonfigurowanym źródłem danych. Ale jak to? Dlaczego tak miałoby się stać? Kompilator może w celu optymalizacji kodu zmienić kolejność deklaracji zmiennych, które nie są oznaczone jako volatile. Zakładając, że kompilator zamienił kolejnością linie to teraz początek metody setUp wygląda tak:

isDataSourceConfigured = true;   
myDataSource.hostname = "wprostychslowach.pl";

I teraz wyobraź sobie, że wątek wykonujący start przejmuje czas procesora gdy wątek setUp wykonał jedynie:

isDataSourceConfigured = true;    

Wątek start dostaje sygnał, że może uruchamiać serwer, a przecież nie mamy jeszcze skonfigurowanego źródła danych. Koniec świata.

Nie dbamy w tym przypadku ani o atomowość ani o widoczność. Może być zatem różnie (o reorder i innych przyczynach możesz przeczytać tu lub tu.

Cytat, który może być streszczeniem powyższych dwóch linków i opisanego problemu:

“Actions in different threads are not necessarily ordered with respect to each other at all — if you start two threads and they each execute without synchronizing on any common monitors or touching any common volatile variables, you can predict exactly nothing about the relative order in which actions in one thread will execute (or become visible to a third thread) with respect to actions in the other thread.

Zatem jeśli nie zadbamy o synchronizację i widoczność, a dodatkowo kompilator zamieni nam kolejność linijek w celach optymalizacji to nie jesteśmy w stanie nic powiedzieć o rezultacie działania takiej aplikacji.

Wróćmy do naszego przykładu. Teraz podobny przykład, tylko dodajmy volatile.

 class MyVolatileApp {
    public static void main(String[] args) {
        ConfigureSomething ex = new ConfigureSomething();
        new Thread(() -> { ex.setUp(); }).start();
        new Thread(() -> { ex.start(); }).start();
    }
}
class ConfigureSomething {
    MyDataSource myDataSource = new MyDataSource();
    volatile boolean isDataSourceConfigured = false;

    void setUp() {
        // below variables will not be reordered by compiler
        myDataSource.hostname = "wprostychslowach.pl";
        isDataSourceConfigured = true;
    }

    void start() {
        while(!isDataSourceConfigured) {
            // do nothing
        }
        // Here i'm sure that isDataSourceConfigured is true, so myDataSource is configured!
        System.out.println("Yeah. Let's connect");
    }
}

class MyDataSource {
    public String hostname;
}

Zgodnie z definicją konstruktu volatile, mamy w tym momencie pewność, że jeśli task setUp zmodyfikuje zmienną isDataSourceConfigured, to drugi wątek, ten startujący, otrzyma aktualną, najświeższą jej wartość.

Co z obiektem źródła danych, który nie jest oznaczony jako volatile? Ponieważ jest on również widoczny dla wątku wykonującego setUp (jest w obrębie zmiennej oznaczonej jako volatile), to mimo że zmienna myDataSource nie jest oznaczona jako volatile, to ona również trafi do głównej pamięci i wątek startujący będzie widział najświeższą wartość myDataSource.

A dzieje się tak dlatego, że kompilator nie zrobi reorderingu naszych linijek w takim przypadku. Tzn., takim, gdzie działamy w obrębie zmiennej volatile. I to jest dla nas najważniejsza informacja – nie ma możliwości, abyśmy wystartowali serwer bez wykonania kodu konfigurującego źródło danych.

Podobny przykład znajdziesz tu, w akapicie Problem #2: Reordering volatile and nonvolatile stores.

Liznęliśmy temat sekcji krytycznych. Niedługo część nr 3.

Leave a Reply

Your email address will not be published. Required fields are marked *