Programowanie współbieżne

Stos i sterta

W Javie wszystkie obiekty i tablice mieszczą się w obszarze pamięci nazywanym stertą (ang. heap) – jest jedna na proces, wspólna dla wszystkich jego wątków. Nie ma specjalnej struktury, jest nieuporządkowana (z punktu widzenia programu), stąd nazwa. Każdy wątek ponadto ma w pamięci swój stos (stack), gdzie mieszczą się informacje o obecnie trwających wywołaniach funkcji, w tym argumenty funkcji i zmienne lokalne.

Wykonanie programu polega na wywołaniu (w wątku głównym) funkcji main; podczas tego wywołania możemy przejść do wywołania funkcji wewnątrz main, a w niej do kolejnej funkcji, i tak dalej. W danym momencie stos musi więc pamiętać sekwencję obecnie trwających, zagnieżdżonych wywołań funkcji – czyli wszystkie wywołania które zaczęliśmy, a z których jeszcze nie wyszliśmy. Stos składa się z sekwencji ramek stosu (stack frame) odpowiadających kolejnym wywołaniom: od main, aż po obecnie wykonywaną funkcję. Każdy inny wątek będzie miał własny stos, tylko zaczynający się od innej funkcji niż main.

Na ramkę stosu składa się odnośnik do wykonywanej funkcji, oraz argumenty wywołania i zmienne lokalne. Ale, co ważne, prymitywne zmienne (int/float/boolean/char/short/long/double/byte) są zapisane w ramce stosu bezpośrednio, przez wartość, natomiast dla obiektów i tablic zapisujemy w ramce stosu tylko referencję (wskaźnik 32 lub 64-bitowy) do pozycji obiektu/tablicy na wspólnej stercie.

Wywołanie metody obiektu foo działa tak jak wywołanie funkcji, której niejawnie przekazujemy dodatkowo argument this – referencję na obiekt foo.

Przykład

Spójrzmy na TwoWritersSynchronized. Dodałem opcjonalne this. przed first, last i id dla czytelności.

public class TwoWritersSynchronized {

    private static volatile boolean lettersDone = false;
    private static volatile boolean digitsDone = false;

    private static volatile int currentId;

    private static class Writer implements Runnable {

        private static final int LINES_COUNT = 100;
        private static final int LINE_LENGTH = 50;

        private final char first;
        private final char last;
        private final int id;

        public Writer(char first, char last, int id) {
            this.first = first;
            this.last = last;
            this.id = id;
        }

        @Override
        public void run() {
            char c = this.first;
            for (int i = 0; i < LINES_COUNT; ++i) {
                while (currentId != this.id) {}

                for (int j = 0; j < LINE_LENGTH; ++j) {
                    System.out.print(c);
                    ++c;
                    if (c > this.last) {
                        c = this.first;
                    }
                }
                System.out.println();

                currentId = 1 - currentId;
            }
            if (id == 0) {
                lettersDone = true;
            } else {
                digitsDone = true;
            }
        }

    }

    public static void main(String[] args) {
        Thread letters = new Thread(new Writer('a', 'z', 0));
        Thread digits = new Thread(new Writer('0', '9', 1));
        currentId = 0;
        System.out.println("Początek");
        letters.start();
        digits.start();
        while (!lettersDone) {}
        while (!digitsDone) {}
        System.out.println("Koniec");
    }

}

W połowie wykonania programu mamy na stercie (w przypadkowej, nieistotnej kolejności):

0. obiekt Writer('a', 'z', 0) (w nim zmienne first, last, id) i obiekt Thread wskazujący na niego.
1. obiekt Writer('0', '9', 1) (w nim zmienne first, last, id) i obiekt Thread wskazujący na niego.
2. zmienne lettersDone, digitsDone, currentId (bo są oznaczone static)

Do tego mamy trzy stosy:

0. stos głównego wątku, z ramką main, a w niej zmienne letters i digits będące referencjami do powyższych obiektów Thread (i nic więcej, wywołanie start() było króciutkie i już z niego wyszliśmy).
1. stos wątku letters, z ramką run, a w niej zmienna this wskazująca na obiekt 0. Writer na stercie, oraz zmienne lokalne i,j,c.
2. stos wątku digits, z ramką run, a w niej zmienna this wskazująca na obiekt 1. Writer na stercie, oraz zmienne lokalne i,j,c.

Opis tych stosów, tzw. stacktrace/backtrace, można zobaczyć wstrzymując wątek wyjątkiem lub w debuggerze. Jeśli trafimy odpowiedni moment, na stosach wątków możemy zobaczyć jeszcze ramki print/println (i kolejne ramki wykonywanych wewnątrz print/println funkcji).

Współbieżność

Zmiennych na stosie nie da się sięgnąć z innego wątku, więc ich zachowanie jest proste i bezpieczne.

Na zmienne na stercie już musimy uważać, natomiast dla wielu nadal możemy łatwo zobaczyć, że sięga do nich tylko jeden wątek. Przykładem są zmienne w obiekcie Writer danego wątku – w odwołaniach do this.first, this.last, this.id nie musimy na nic uważać. No chyba że jakoś przekażemy innym wątkom this z naszego wątku lub sięgniemy do letters/digits z głównego wątku (moglibyśmy np. zapisać sobie w main referencję do Writer przed przekazaniem go do konstruktora Thread).

Zmienna lettersDone (i podobnie digitsDone) może być zapisana tylko przez jeden wątek, co mocno ułatwia analizę; natomiast jest czytana przez inny wątek w celu synchronizacji, więc volatile jest konieczne.

Wreszcie zmienna currentId jest zapisywana i czytana przez dwa wątki, więc volatile jest konieczne i analiza tego co się z nią dzieje już wymaga pomyślenia o jakichś niezmiennikach.

W językach C, C++, Rust

Krótko mówiąc jest tak samo, ale rozróżniamy w kodzie obiekt od wskaźnika na obiekt; zmienne lokalne zawsze są na stosie – sami decydujemy czy trzymamy obiekt bezpośrednio na stosie, czy trzymamy na stosie tylko wskaźnik do obiektu utworzonego na stercie.

(Uwaga: volatile z C/C++ daje zupełnie inne gwarancje niż volatile z Javy. Bliższy jest typ std:atomic<int> z C/C++, który dodatkowo gwarantuje atomowość (niepodzielność) między innymi inkrementacji ++. Przypomnijmy: volatile z Javy atomowość gwarantuje tylko dla pojedynczego odczytu lub dla pojedynczego zapisu.)