Synchronized vs Semaphore vs Lock

W dzisiejszym poście chciałbym porównać trzy mechanizmy synchronizacji wątków w Java 6 - monitory, locki oraz semafory. Mechanizmy te umożliwiają tworzenie sekcji krytycznych, czyli modeli przepływu sterowania, które w danym momencie mogą być wykonywane tylko przez jeden wątek. Innymi sposobami na ochronę spójności danych jest oczywiście stosowanie obiektów niemutowalnych lub typów atomowych jednak na potrzeby tego artykuły chciałbym się skupić na porównaniu mechanizmów lockingu. Więcej o współbieżności można poczytać w innym wpisie, zapraszam ;)

Aby móc porównywać mechanizmy musimy dysponować pewnym zbiorem kryteriów wg których będziemy to robić. Jako kryteria przyjąłem wydajność oraz zapewnianie poniższych funkcjonalności:

  • reentrant locking - umożliwia wątkom nakładanie blokady, której są właścicielami bez oczekiwania na jej zwolnienie

  • timed locking - umożliwia określenie maksymalnego czasu oczekiwania na zwolnienie blokady

  • lock polling - umożliwia odczytanie stanu blokady

  • condition locking - dostarcza metody wstrzymujące / wznawiające wątki (m.in. do sprawnego rozwiązywania problemu producentów i konsumentów)

  • shared / exclusive locking - umożliwia stosowanie blokad współdzielonych i wykluczających (m.in. do sprawnego rozwiązywania problemu czytelników i pisarzy)

  • lock ownership - przechowuje informacje o wątku, który pobrał blokadę i umożliwia jej zwolnienie tylko właścicielowi

Monitory

Monitor jest specjalnym znacznikiem, którego właścicielem w danej chwili dla pojedynczego obiektu może być tylko jeden wątek. Wejście w posiadanie znacznika odbywa się poprzez uruchomienie metody synchronizowanej (lub bloku synchronizowanego). Wątek, który zostanie wywłaszczony przez scheduler nie oddaje znacznika. Z kolei wątek, który potrzebuje monitora do obiektu, po wykonaniu metody synchronizowanej przechodzi do stanu Oczekiwania na monitor. W momencie gdy monitor stanie się dostępny, scheduler wybierze jeden wątek z puli wątków oczekujących na monitor, przekaże mu monitor i przeniesie do stanu runnable, gdzie zostanie obsłużony tak samo jak reszta wątków.

Poniżej fragment kodu wykorzystujący mechanizm monitorów

1
2
3
4
5
6
7
8
9
10
11
12
private static final Object guard = new Object();

    public void timeSynchronized(final int reps) {
        testAlgo(reps, new Runnable() {
            @Override
            public void run() {
                synchronized (guard) {
                    r.nextInt();
                }
            }
        });
    }

Cechy:

  • reentrant locking - zapewniają

  • timed locking - nie zapewniają

  • lock polling - nie zapewniają

  • condition locking - zapewniają za pomocą metod wait() / notify() / notifyAll()

  • shared / exclusive locking - nie zapewniają

  • lock ownership - zapewniają - tylko wątek, który pobrał monitor może go zwrócić

  • Ważnym ograniczeniem jest także konieczność zwolnienia monitora w tej samej ramce stosu, w której monitor został pobrany co ogranicza zasięg bloku synchronizowanego tylko do jednej metody

Semafory

Najprościej mówiąc semafory są to obiekty, które posiadają pewną pulę pozwoleń. Semafory posiadają dwie metody P (opuszczenie semafora) oraz V (podniesienie semafora). Tak samo jak monitory umożliwiają budowanie sekcji krytycznych - wątek który uruchomi na semaforze operację P w momencie, gdy semafor nie posiada żadnego pozwolenia zostanie wstrzymany do czasu aż pozwolenie zostanie zwrócone do puli. W Javie semafory reprezentowane są przez obiekty klasy java.util.concurrent.Semaphore, a odpowiednikami operacji P i V są odpowiednio metody acquire() oraz release(). W ogólności semafory mogą posiadać dowolną liczbę pozwoleń (stąd określenie semafor ogólny) jednak najczęstszym typem semaforów są semafory posiadające tylko jedno pozwolenie - są to tzw semafory binarne inaczej zwane mutexami. My skupimy się na porównaniu semaforów binarnych.

Poniżej fragment kodu wykorzystującego semafor. Użyłem metody acquireUninterruptibly(), która jest blokującym odpowiednikiem metody acquire().

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
private static final Semaphore sem = new Semaphore(1);

    public void timeSemaphore(final int reps) {
        testAlgo(reps, new Runnable() {
            @Override
            public void run() {
                sem.acquireUninterruptibly();
                try {
                    r.nextInt();
                } finally {
                    sem.release();
                }
            }
        });
    }

Semafory w porównaniu do monitorów dają bardziej elastyczny kod jednak implementacja jest nieco trudniejsza. Sami musimy dbać o odpowiednie nakładanie blokad i ich zwracanie. Nie jesteśmy jednak ograniczeni do jednej ramki stosu.

Cechy:

  • reentrant locking - nie zapewniają

  • timed locking - zapewniają - za pomocą metody tryAcquire(long timeout, TimeUnit unit) blokującą wątek do momentu uzyskania blokady, maksymalnie przez pewien okres czasu

  • lock polling - zapewniają - za pomocą metody availablePermits() zwracającej liczbę pozwoleń oraz metody tryAcquire()

  • condition locking - nie zapewniają

  • shared / exclusive locking - nie zapewniają

  • lock ownership - nie zapewniają - semafory mogą być podnoszone i opuszczane przez różne wątki

Locki

Locki to mechanizm Java łączący w sobie zalety mechanizmu monitorów i semaforów, stworzony z myślą o zapewnianiu dużej wydajności i skalowalności algorytmów dla wysokiego poziomu współbieżności. Monitory są prostym mechanizmem, często wystarczającym do wielu zastosowań jednak są ograniczone funkcjonalnie. Semafory cechują się większą elastycznością, jednak nie posiadają pewnych cech, które mają monitory. Locki są więc dobrą alternatywą.

Poniżej przykład kodu wykorzystującego locki

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
private static final Lock lock = new ReentrantLock();

    public void timeLock(final int reps) {
        testAlgo(reps, new Runnable() {
            @Override
            public void run() {
                lock.lock();
                try {
                    r.nextInt();
                } finally {
                    lock.unlock();
                }
            }
        });
    }

Cechy:

  • reentrant locking - zapewniają - implementacja ReentrantLock

  • timed locking - zapewniają - za pomocą metody tryLock(long time, TimeUnit unit) blokującą wątek do momentu uzyskania blokady, maksymalnie przez pewien okres czasu

  • lock polling - zapewniają - za pomocą metody tryLock()

  • condition locking - zapewniają - umożliwiają stworzenie dowolnej ilości obiektów klasy java.util.concurrent.locks.Condition implementującej metody await() / signal() / signalAll()

  • shared / exclusive locking - zapewniają - implementacja ReentrantReadWriteLock

  • lock ownership - zapewniają - lock może być zwolniony tylko przez wątek, który go nałożył

Porównanie wydajności

Poniżej wyniki testu wydajnościowego. Test został wykonany za pomocą microbenchmarka Caliper i obejmował uruchomienie w pętli przy coraz większym współczynniku współbieżności (1, 2, 4, 8, 16 oraz 32, 64, 128, 256 wątków) prostego obliczenia matematycznego w sekcji krytycznej chronionej przez kolejne mechanizmy synchronizacji. Obliczenie było wykonywane przez każdy wątek w pętli po 1000 * 1000 * reps iteracji (przy każdorazowym wejściu do sekcji krytycznej). Parametr reps jest parametrem przekazywanym przez benchmark i wahał się od 1 do 5000 w zależności od liczby wątków. Wyniki testów przedstawiają średni czas wykonywania podanej liczby iteracji jednak należy wziąć pod uwagę, że dla każdej ilości wątków parametr reps był inny, toteż nie należy porównywać wartości bezwzględnych pomiędzy różnymi poziomami współbieżności.

Specyfikacja maszyny testowej - Intel® Core™ i7-3610QM CPU @ 2.30GHz, 16GB RAM, Performance Governor, JDK - Java™ SE Runtime Environment (build 1.6.0_35-b10), Java HotSpot™ 64-Bit Server VM (build 20.10-b01, mixed mode)

Wynik testu dla liczby wątków od 1 do 16:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
numThreads    benchmark    ms linear runtime
         1 Synchronized  1,22 =
         1         Lock  2,45 =
         1    Semaphore  2,51 =
         2 Synchronized 12,74 ====
         2         Lock 26,83 ========
         2    Semaphore 26,52 ========
         4 Synchronized 23,51 =======
         4         Lock 18,86 =====
         4    Semaphore 16,40 =====
         8 Synchronized 46,27 ==============
         8         Lock 37,06 ===========
         8    Semaphore 31,21 =========
        16 Synchronized 94,42 ==============================
        16         Lock 78,22 ========================
        16    Semaphore 61,55 ===================

Wynik testu dla liczby wątków od 16 do 256:

1
2
3
4
5
6
7
8
9
10
11
12
13
numThreads    benchmark     ms linear runtime
        32 Synchronized  192,1 ===
        32         Lock  147,3 ==
        32    Semaphore  121,0 ==
        64 Synchronized  382,4 =======
        64         Lock  278,2 =====
        64    Semaphore  240,1 ====
       128 Synchronized  787,0 ===============
       128         Lock  631,2 ============
       128    Semaphore  475,9 =========
       256 Synchronized 1516,4 ==============================
       256         Lock 1050,4 ====================
       256    Semaphore  908,9 =================

Przy niskim poziomie współbieżności największą wydajność posiadają metody synchronizowane, są one dużo wydajniejsze niż semafory oraz locki. Wraz ze wzrostem współbieżności sytuacja się zmienia. Przy poziomie współbieżności >= 4 metody synchronizowane są już mniej wydajne niż semafory i locki. Różnica najwyraźniej objawia się dla 256 wątków kiedy metody synchronizowane są około 50% mniej wydajne niż pozostałe mechanizmy.

Wnioski

Wnioski z powyższego wpisu są następujące - metody synchronizowane posiadają przyzwoitą wydajność dla niskiego poziomu współbieżności, co w połączeniu z dość bogatym zbiorem funkcjonalności stanowi dobry wybór dla większości zastosowań, dla których jesteśmy w stanie poświęcić trochę wydajności kosztem prostoty i niskiej złożoności kodu. Gdy z kolei potrzebujemy wyższej wydajności (oraz skalowalności) powinniśmy skupić się na wyborze pomiędzy semaforami oraz lockami. Pozostaje tylko kwestia określenia funkcjonalności, które potrzebujemy.

Comments