Firma je dobila senior inženjera iz Meituana koji je potpuno razjasnio brave u Javi

Predgovor

Java pruža bogatstvo različitih brava, a svaka zbog svojih specifičnih osobina u odgovarajućim scenarijima postiže vrlo visoku efikasnost. Cilj ovog članka je da kroz primere izvornog koda (izvorni kod u tekstu potiče iz JDK 8 i Netty 3.10.6) i scenarija korišćenja čitaocu predstavi ključne koncepte o bravama i njihove primene.

U Javi se brave najčešće definišu prema tome da li poseduju određenu osobinu. Brave grupišemo prema osobinama, a zatim ih predstavljamo poređenjem, kako bi svima olakšali razumevanje. Ispod je dat opšti pregled sadržaja članka:

1. Optimistička VS pesimistička brava

Optimistička i pesimistička brava su široki pojmovi koji odražavaju dva različita ugla gledanja na sinhronizaciju niti. I u Javi i u bazama podataka postoje praktične primene ovih pojmova.

Prvo, pojam. Pri konkurentnom pristupu istim podacima, pesimistička brava smatra da će, dok ona koristi podatke, neka druga nit sigurno pokušati da ih izmeni. Zato prilikom uzimanja podataka prvo stavlja bravu, kako bi osigurala da drugi niti ne izmene podatke. U Javi, ključna reč synchronized i implementacije interfejsa Lock su pesimističke brave.

Optimistička brava pak smatra da, dok ona koristi podatke, druge niti neće menjati podatke, pa ne stavlja bravu; tek prilikom ažuriranja podataka proverava da li ih je neka druga nit u međuvremenu izmenila. Ako podaci nisu izmenjeni, trenutna nit uspešno upisuje svoje izmene. Ako su podatke već izmenile druge niti, postupa se različito u zavisnosti od implementacije (npr. izbacivanje greške ili automatsko ponavljanje).

Optimistička brava se u Javi implementira programiranjem bez brava, najčešće kroz CAS algoritam. Operacija uvećanja u Java atomnim klasama ostvarena je CAS-spinom.

Iz gornjeg opisa pojmova možemo zaključiti:

• Pesimistička brava odgovara scenarijima sa mnogo operacija pisanja — prethodno zaključavanje osigurava ispravnost podataka pri upisu.
• Optimistička brava odgovara scenarijima sa mnogo operacija čitanja — izostanak zaključavanja znatno poboljšava performanse čitanja.

Pojam je pomalo apstraktan, pa hajde da pogledamo primere poziva optimističke i pesimističke brave:

// ------------------------- Način poziva pesimističke brave -------------------------
// synchronized
public synchronized void testMethod() {
	// rad sa sinhronizovanim resursom
}
// ReentrantLock
private ReentrantLock lock = new ReentrantLock(); // mora se osigurati da više niti koristi istu bravu
public void modifyPublicResources() {
	lock.lock();
	// rad sa sinhronizovanim resursom
	lock.unlock();
}

// ------------------------- Način poziva optimističke brave -------------------------
private AtomicInteger atomicInteger = new AtomicInteger(); // mora se osigurati da više niti koristi isti AtomicInteger
atomicInteger.incrementAndGet(); // izvršava uvećanje za 1

Iz primera poziva vidimo da se pesimistička brava skoro uvek koristi tek nakon eksplicitnog zaključavanja, dok optimistička brava direktno pristupa sinhronizovanim resursima. Zašto onda optimistička brava može ispravno da ostvari sinhronizaciju niti bez zaključavanja resursa? To ćemo objasniti kroz tehničke principe CAS-a, glavnog načina realizacije optimističke brave.

CAS je skraćenica od Compare And Swap (uporedite i zameni), i predstavlja algoritam bez brava. Omogućava sinhronizaciju promenljivih između niti bez korišćenja brava (nijedna nit se ne blokira). Atomne klase u paketu java.util.concurrent upravo kroz CAS ostvaruju optimističku bravu.

CAS algoritam obuhvata tri operanda:

• V — vrednost u memoriji koja se čita/upisuje.
• A — vrednost sa kojom se poredi.
• B — nova vrednost koja se upisuje.

Samo ako je V jednako A, CAS atomički menja V novom vrednošću B („uporedi + ažuriraj“ je celina atomska operacija), inače ne radi ništa. U opštem slučaju, „ažuriranje“ je operacija koja se neprekidno ponavlja.

Malopre smo spomenuli atomne klase iz paketa java.util.concurrent koje preko CAS-a ostvaruju optimističku bravu. Zato ćemo ući u izvorni kod atomne klase AtomicInteger i pogledati njenu definiciju:

Iz definicije možemo videti ulogu pojedinih polja:

• unsafe: dobavlja i opslužuje podatke u memoriji.
• valueOffset: čuva ofset vrednosti value unutar AtomicInteger-a.
• value: čuva int vrednost AtomicInteger-a; ovo polje mora biti vidljivo među nitima, što se postiže ključnom reči volatile.

Zatim, kada pogledamo izvorni kod metode uvećanja incrementAndGet() klase AtomicInteger, vidimo da ona na nižem nivou poziva unsafe.getAndAddInt(). Pošto sam JDK sadrži samo Unsafe.class, samo iz imena parametara u class datoteci ne možemo dobro razumeti ulogu metode, pa ćemo za pregled izvornog koda Unsafe koristiti OpenJDK 8:

// ------------------------- JDK 8 -------------------------
// AtomicInteger metod uvećanja
public final int incrementAndGet() {
  return unsafe.getAndAddInt(this, valueOffset, 1) + 1;
}

// Unsafe.class
public final int getAndAddInt(Object var1, long var2, int var4) {
  int var5;
  do {
      var5 = this.getIntVolatile(var1, var2);
  } while(!this.compareAndSwapInt(var1, var2, var5, var5 + var4));
  return var5;
}

// ------------------------- OpenJDK 8 -------------------------
// Unsafe.java
public final int getAndAddInt(Object o, long offset, int delta) {
   int v;
   do {
       v = getIntVolatile(o, offset);
   } while (!compareAndSwapInt(o, offset, v, v + delta));
   return v;
}

Iz izvornog koda OpenJDK 8 vidimo da getAndAddInt() u petlji dobavlja vrednost v na zadatom ofsetu objekta o, a zatim proverava da li je vrednost u memoriji jednaka v. Ako jeste, postavlja vrednost u memoriji na v + delta; inače vraća false i nastavlja petlju sa ponavljanjem dok postavljanje ne uspe, kada izlazi iz petlje i vraća staru vrednost. Celokupna operacija „uporedi + ažuriraj“ obuhvaćena je u compareAndSwapInt(), koji se u JNI-ju ostvaruje jednom instrukcijom CPU-a — atomskom operacijom koja garantuje da više niti može videti istu izmenu vrednosti iste promenljive.

Kasnije verzije JDK-a putem CPU instrukcije cmpxchg upoređuju A iz registra i vrednost V u memoriji. Ako su jednaki, nova vrednost B se upisuje u memoriju. Ako nisu jednaki, vrednost iz memorije V se dodeljuje registru A. Zatim while petlja u Java kodu ponovo poziva cmpxchg instrukciju radi ponavljanja, sve dok postavljanje ne uspe.

CAS je iako vrlo efikasan, ima tri glavna problema, koje ćemo ukratko navesti:

1. Problem ABA. CAS pri promeni vrednosti proverava da li se vrednost u memoriji promenila; ažurira je samo ako nije. Ali ako je vrednost u memoriji prvobitno bila A, zatim postala B, pa opet A, CAS pri proveri zaključuje da se ništa nije promenilo, iako je zapravo bilo promena. Rešenje problema ABA je dodavanje verzije promenljivoj: pri svakoj izmeni verzija se uveća za jedan, tako da tok promene postaje „1A-2B-3A“ umesto „A-B-A“.

• Od JDK-a 1.5 dostupna je klasa AtomicStampedReference za rešavanje problema ABA; konkretna operacija je obuhvaćena u compareAndSet(). compareAndSet() najpre proverava da li trenutna referenca i trenutna oznaka odgovaraju očekivanoj referenci i očekivanoj oznaci; ako oba uslova vrede, atomski postavlja vrednost reference i oznake na date nove vrednosti.

2. Dugo vrtetenje znatno povećava opterećenje. Ako CAS operacija dugo ne uspe, nit će se stalno vrteti, što dovodi do velikog opterećenja CPU-a.
3. Garantuje atomsku operaciju samo nad jednom deljenom promenljivom. Pri operaciji nad jednom deljenom promenljivom CAS garantuje atomičnost, ali pri operacijama nad više deljenih promenljivih CAS ne može garantovati atomičnost.

• Od JDK-a 1.5 dostupna je klasa AtomicReference kojom se obezbeđuje atomičnost između referentnih objekata; više promenljivih se može smestiti u jedan objekat i nad njim izvesti CAS.

2. Spin-brava VS adaptivna spin-brava

Pre nego što predstavimo spin-bravu, moramo navesti neke osnove koje pomažu u razumevanju njenog pojma.

Blokiranje ili buđenje Java niti zahteva od operativnog sistema da promeni stanje CPU-a, a to prebacivanje stanja troši procesorsko vreme. Ako je sadržaj sinhronizovanog bloka previše jednostavan, vreme potrebno za promenu stanja može biti duže od vremena izvršavanja korisničkog koda.

U mnogim scenarijima vreme držanja brave nad sinhronizovanim resursom je vrlo kratko, i zbog tog kratkog vremena prebacivati nit — troškovi suspendovanja i obnove konteksta mogu sistem učiniti da izgubi više nego što dobije. Ako fizička mašina ima više procesora, pa dve ili više niti mogu istovremeno paralelno da se izvršavaju, možemo dozvoliti onoj niti koja kasnije traži bravu da ne odustane od svog procesorskog vremena, već da proveri da li nit koja drži bravu uskoro neće osloboditi bravu.

Da bismo trenutnoj niti „dali da malo sačeka“, puštamo je da se vrti (spin). Ako se nakon završetka spin čeka nit koja je držala bravu nad resursom već oslobodila, trenutna nit ne mora da se blokira već direktno uzima resurs, čime se izbegava trošak prebacivanja niti. To je spin-brava.

Spin-brava ima i nedostataka: ne može zameniti blokiranje. Spin-čekanje iako izbegava trošak prebacivanja niti, ipak zauzima procesorsko vreme. Ako je brava držana kratko, spin-čekanje daje odlične rezultate. Obrnuto, ako je brava držana dugo, nit u spinu samo uzalud troši procesorske resurse. Zato vreme spin-čekanja mora imati neku granicu: ako spin pređe zadati broj pokušaja (podrazumevano 10, menjano opcijom -XX:PreBlockSpin) a brava ne bude pribavljena, nit treba suspendovati.

Princip realizacije spin-brave takođe je CAS — do-while petlja u izvornom kodu AtomicInteger-a gde se poziva unsafe za uvećanje jeste spin operacija: ako promena vrednosti ne uspe, ponavlja se kroz petlju sve dok ne uspe.

Spin-brava je uvedena u JDK 1.4.2 i uključivala se opcijom -XX:+UseSpinning. U JDK-u 6 postala je podrazumevano uključena, a uvedena je i adaptivna spin-brava.

Adaptivnost znači da vreme (broj pokušaja) spin-a više nije fiksno, već zavisi od prethodnog ishoda spin-a na istoj bravi i stanja vlasnika brave. Ako je na istom objektu brave spin-čekanje nedavno uspelo da pribavi bravu, a nit koja drži bravu trenutno radi, virtuelna mašina smatra da će i ovaj spin verovatno uspeti, pa će dozvoliti da spin-čekanje potraje nešto duže. Ako za neku bravu spin retko uspeva, pri narednim pokušajima pribavljanja te brave spin će se možda preskočiti i nit će se direktno blokirati, čime se izbegava rasipanje procesorskih resursa.

Postoje još tri uobičajena oblika spin-brava: TicketLock, CLHLock i MCSLock. Ovde ih samo pominjemo i nećemo ih detaljno razmatrati — zainteresovani čitaoci mogu samostalno potražiti dodatne materijale.

3. Brava bez zaključavanja VS bias-brava VS lako-brzinska brava VS teška brava

Ove četiri brave se odnose na stanja brave, i to isključivo u kontekstu synchronized. Pre nego što ih predstavimo, moramo navesti još neke dodatne pojmove.

Najpre, zašto synchronized uopšte može da ostvari sinhronizaciju niti?

Pre nego što odgovorimo na to pitanje, moramo upoznati dva važna pojma: „Java zaglavlje objekta“ i „Monitor“.

Java zaglavlje objekta

synchronized je pesimistička brava — pre rada sa sinhronizovanim resursom taj resurs se prvo zaključa. Ta brava se čuva u zaglavlju Java objekta. Šta je zapravo zaglavlje Java objekta?

Uzećemo za primer virtuelnu mašinu Hotspot: njeno zaglavlje objekta sadrži uglavnom dva dela podataka — Mark Word (polje oznaka) i Klass Pointer (pokazivač na tip).

Mark Word: podrazumevano čuva HashCode objekta, uzrast generacije i oznaku stanja brave. To su podaci nezavisni od same definicije objekta, pa je Mark Word zamišljen kao nepokretna struktura podataka koja na malom prostoru memorije čuva što više podataka. Prema stanju objekta ponovo koristi svoj prostor za skladištenje, što znači da se podaci u Mark Word-u tokom izvršavanja menjaju zajedno sa oznakom stanja brave.

Klass Pointer: pokazivač objekta na metapodatke njegove klase; virtuelna mašina pomoću njega određuje kom klasi taj objekat pripada.

Monitor

Monitor se može shvatiti kao sinhronizacioni alat, odnosno sinhronizacioni mehanizam, koji se obično opisuje kao objekat. Svaki Java objekat ima nevidljivu bravu, koja se naziva unutrašnja brava ili Monitor-brava.

Monitor je privatna struktura podataka niti: svaka nit ima sopstveni spisak dostupnih zapisa monitora, a postoji i globalni spisak dostupnih. Svaki zaključan objekat povezan je sa jednim monitorom, a u monitoru postoji polje Owner u kojem se čuva jedinstveni identifikator niti koja drži bravu, čime se označava da je brava zauzeta tom niti.

Vratimo se sada na synchronized — synchronized sinhronizaciju niti ostvaruje preko Monitora, a Monitor zavisi od Mutex Lock-a (brave uzajamnog isključivanja) operativnog sistema.

Kao što smo već naveli kod spin-brave, „blokiranje ili buđenje Java niti zahteva od operativnog sistema da promeni stanje CPU-a, što troši procesorsko vreme; ako je sadržaj sinhronizovanog bloka previše jednostavan, vreme promene stanja može biti duže od vremena izvršavanja korisničkog koda“. takav način je bio prvobitni pristup synchronized-a sinhronizaciji, i to je razlog što je synchronized pre JDK-a 6 bio neefikasan. Brave koje se oslanjaju na Mutex Lock operativnog sistema nazivamo „teškim bravama“; u JDK-u 6 su, da bi se smanjio trošak pribavljanja i oslobađanja brave, uvedene „bias-brava“ i „lako-brzinska brava“.

Tako sada ukupno postoje 4 stanja brave, po težini od najnižeg ka najvišem: bez brave, bias-brava, lako-brzinska brava i teška brava. Stanje brave može samo da se unapređuje, nikako da se snižava.

Gornjim uvodom stekli smo predstavu o mehanizmu zaključavanja synchronized-a. U nastavku dajemo sadržaj Mark Word-a za svako od četiri stanja brave, a zatim objašnjavamo principe i osobine pojedinih stanja:

Stanje brave	Sadržaj skladištenja	Oznaka
Bez brave	HashCode objekta, uzrast generacije objekta, da li je bias-brava (0)	01
Bias-brava	ID bias-niti, vremenska oznaka bias-a, uzrast generacije objekta, da li je bias-brava (1)	01
Lako-brzinska brava	Pokazivač na zapis brave u steku	00
Teška brava	Pokazivač na Mutex (tešku bravu)	10

Bez brave

U stanju bez brave resurs nije zaključan — sve niti mogu pristupati i menjati isti resurs, ali u svakom trenutku samo jedna nit uspešno izmeni.

Karakteristika stanja bez brave je da se izmena vrši u petlji: nit neprekidno pokušava da izmeni deljeni resurs. Ako nema sukoba, izmena uspeva i izlazi; inače nastavlja da pokušava. Ako više niti menja istu vrednost, jedna će sigurno uspeti, a one koje ne uspeju pokušavaju iznova dok ne uspeju. CAS princip i primena koje smo gore opisali upravo su realizacija stanja bez brave. Stanje bez brave ne može potpuno zameniti stanje sa bravom, ali u određenim situacijama postiže vrlo visoke performanse.

Bias-brava

Bias-brava znači da je deo sinhronizovanog koda uvek pristupao jedna ista nit — ta nit onda automatski pribavlja bravu, čime se smanjuje cena pribavljanja.

U većini slučajeva bravu uvek dobija ista nit, pa nema konkurencije među nitima — otuda bias-brava. Njen cilj je da poboljša performanse kada sinhronizovani blok izvršava samo jedna nit.

Kada jedna nit pristupi sinhronizovanom bloku i pribavi bravu, u Mark Word se upisuje ID niti kojoj je brava naklonjena. Pri ulasku i izlasku niti iz sinhronizovanog bloka ne koristi se CAS za zaključavanje i otključavanje, već se proverava da li Mark Word čuva pokazivač bias-brave ka trenutnoj niti. Bias-brava je uvedena da bi se u situacijama bez konkurencije izbegla nepotrebna putanja lako-brzinske brave, jer pribavljanje i oslobađanje lako-brzinske brave zavisi od više atomskih CAS instrukcija, dok bias-brava zahteva samo jednu atomsku CAS instrukciju pri zameni ThreadID-a.

Bias-brava se oslobađa tek kada druga nit pokuša da je preotme — nit ne oslobađa bias-bravu sama. Opozivanje bias-brave zahteva čekanje globalne bezbedne tačke (trenutak u kojem se ne izvršava nijedan bajtkod): tada se prvo pauzira nit koja drži bias-bravu i proverava da li je objekat brave u zaključanom stanju. Nakon opoziva bias-brave vraća se u stanje bez brave (oznaka „01“) ili u lako-brzinsku bravu (oznaka „00“).

Bias-brava je u JDK-u 6 i kasnijim JVM-ovima podrazumevano uključena. Može se isključiti JVM parametrom -XX:-UseBiasedLocking=false, nakon čega program podrazumevano prelazi u lako-brzinsku bravu.

Lako-brzinska brava

Kada je brava u stanju bias-brave, a njoj pristupi druga nit, bias-brava se unapređuje u lako-brzinsku bravu; druge niti pokušavaju da pribave bravu spinovanjem, bez blokiranja, čime se poboljšavaju performanse.

Pri ulasku u sinhronizovani blok, ako je stanje brave objekta „bez brave“ (oznaka „01“, bias-flag „0“), virtuelna mašina prvo u okviru stek frejma trenutne niti formira prostor pod imenom Lock Record, u koji smešta kopiju trenutnog Mark Word-a objekta, a zatim u taj zapis kopira Mark Word iz zaglavlja objekta.

Nakon uspešnog kopiranja, virtuelna mašina pokušava CAS-om da ažurira Mark Word objekta tako da pokazuje na Lock Record, i da owner pokazivač u Lock Record-u usmeri na Mark Word objekta.

Ako ovo ažuriranje uspe, ta nit stiče bravu nad objektom, a oznaka stanja brave u Mark Word-u postavlja se na „00“, što označava da je objekat u lako-brzinskom zaključanju.

Ako ažuriranje lako-brzinske brave ne uspe, virtuelna mašina prvo proverava da li Mark Word objekta pokazuje na stek frejm trenutne niti — ako da, trenutna nit već drži bravu nad tim objektom, pa može neposredno ući u sinhronizovani blok; inače to znači da više niti konkuriše za bravu.

Ako čeka samo jedna nit, ona čeka spinovanjem. Ali kada spin pređe određeni broj pokušaja, ili dok jedna nit drži bravu, druga se vrti, a stigne i treća — lako-brzinska brava unapređuje se u tešku bravu.

Teška brava

Prilikom unapređenja u tešku bravu, oznaka stanja postaje „10“, a u Mark Word-u se tada čuva pokazivač na tešku bravu; niti koje čekaju bravu ulaze u blokirano stanje.

Ceo tok unapređenja stanja brave prikazan je ispod:

Zaključno: bias-brava rešava problem zaključavanja poređenjem Mark Word-a, izbegavajući CAS; lako-brzinska brava rešava ga CAS-om i spinom, izbegavajući uticaj blokiranja i buđenja niti na performanse; teška brava blokira sve niti osim one koja drži bravu.

4. Pravedna VS nepravedna brava

Pravedna brava znači da više niti pribavlja bravu redom po prijavi: niti ulaze direktno u red čekanja, a prvu nit u redu dobija bravu. Prednost pravedne brave je da niti koje čekaju neće „umreti od gladi“. Mana je da je ukupna propusnost nešto niža nego kod nepravedne brave, jer sve niti u redu osim prve blokiraju, a trošak buđenja blokiranih niti od strane CPU-a veći je nego kod nepravedne brave.

Nepravedna brava znači da više niti pri zaključavanju direktno pokušava da pribavi bravu, a tek ako ne uspe odlazi na kraj reda čekanja. Ali ako u tom trenutku brava bude dostupna, nit je može dobiti bez blokiranja, pa se kod nepravedne brave može desiti da nit koja je kasnije prijavila bravu dobije pre niti koja je ranije prijavila. Prednost nepravedne brave je smanjenje troška buđenja niti i veća ukupna propusnost jer nit često dobija bravu bez blokiranja, pa CPU ne mora da budi sve niti. Mana je da niti u redu čekanja mogu „umreti od gladi“ ili čekati vrlo dugo.

Opis rečima je pomalo apstraktan, pa ćemo pozajmiti jedan primer koji objašnjava pravednu i nepravednu bravu.

Kao na slici, pretpostavimo da postoji jedan bunar sa vodom i čuvar koji ima bravu: samo ko dobije bravu sme da crpi vodu, a po završetku vraća bravu čuvaru. Svako ko dođe po vodu mora dobiti dozvolu čuvara i preuzeti bravu; ako neko ispred njega već crpe vodu, mora se postaviti u red. Čuvar proverava da li je sledeći na redu za crpljenje zaista prvi u redu — ako jeste, daje mu bravu; ako nije, mora na kraj reda. To je pravedna brava.

Kod nepravedne brave čuvar ne postavlja nikakve uslove. Čak i ako u redu čekanja ima ljudi, ako prethodnik upravo završi i vrati bravu, a čuvar još nije dozvolio sledećem iz reda da crpi, a taman tada stigne neko ko preseca red — ta osoba može direktno od čuvara dobiti bravu i crpiti vodu, bez čekanja u redu, dok oni koji su strpljivo čekali moraju nastaviti da čekaju. Kao na sledećoj slici:

Naredno, pomoću izvornog koda ReentrantLock-a objasnićemo pravednu i nepravednu bravu.

public class ReentrantLock implements Lock, java.io.Serializable {
    private final Sync sync;  // FairSync ili NonfairSync
    ...
}

Iz koda se vidi da ReentrantLock ima unutrašnju klasu Sync koja nasleđuje AQS (AbstractQueuedSynchronizer); veći deo operacija dodavanja i oslobađanja brave zapravo je realizovan u Sync-u. On ima dve potklase: pravednu FairSync i nepravednu NonfairSync. ReentrantLock podrazumevano koristi nepravednu bravu, a konstruktorom se može izričito tražiti pravedna brava.

Hajde da pogledamo izvorni kod metoda zaključavanja pravedne i nepravedne brave:

Fer brava — kod:

protected final boolean tryAcquire(int acquires) {
    final Thread current = Thread.currentThread();
    int c = getState();
    if (c == 0) {
        if (!hasQueuedPredecessors()      // poštuje red
                && compareAndSetState(0, acquires)) {
            setExclusiveOwnerThread(current);
            return true;
        }
    }
    ...
}

Poređenjem izvornog koda sa slike jasno se vidi da se lock() metodi pravedne i nepravedne brave razlikuju samo u jednom dodatnom uslovu prilikom pribavljanja sinhronizacionog stanja: hasQueuedPredecessors().

Ulaskom u hasQueuedPredecessors() vidimo da metoda uglavnom radi jedno: proverava da li je trenutna nit prva u sinhronizacionom redu. Ako jeste, vraća true; inače false.

Zaključno, pravedna brava preko sinhronizacionog reda omogućava da više niti pribavlja bravu po redu prijave, čime se postiže pravednost. Nepravedna brava pri zaključavanju ne razmišlja o redu čekanja već direktno pokušava da pribavi bravu, pa postoji mogućnost da ko zakači kasnije — dobije prvi.

5. Reentrantna VS nereentrantna brava

Reentrantna brava (još poznata kao rekurzivna brava) znači da kada jedna ista nit u spoljašnjoj metodi pribavi bravu, njen ulazak u unutrašnju metodu iste niti automatski pribavlja bravu (pod uslovom da je u pitanju isti objekat ili class), bez blokiranja zbog toga što je prethodnu bravu već drži a nije je oslobodila. U Javi su i ReentrantLock i synchronized reentrantne brave; jedna prednost reentrantne brave je da do izvesne mere izbegava mrtvu petlju (deadlock). Analizirajmo na primeru:

public class Widget {
    public synchronized void doSomething() {
        System.out.println("Izvršava se metod 1...");
        doOthers();
    }

    public synchronized void doOthers() {
        System.out.println("Izvršava se metod 2...");
    }
}

U gornjem kodu su obe metode klase obeležene ugrađenom bravom synchronized, a doSomething() poziva doOthers(). Pošto je ugrađena brava reentrantna, ista nit pri pozivu doOthers() može neposredno da pribavi bravu trenutnog objekta i uđe u doOthers() radi rada.

Da je u pitanju nereentrantna brava, pre poziva doOthers() trenutna nit bi morala da oslobodi bravu nad trenutnim objektom stečenu u doSomething() — a tu bravu zapravo već drži i ne može da je oslobodi. Tada bi nastupila mrtva petlja.

Zašto reentrantna brava može automatski da pribavi bravu pri ugnježdenom pozivu? Razložićemo to crtežom i izvornim kodom.

Vratimo se primeru s crpljenjem vode: više ljudi čeka u redu, a čuvar dozvoljava da se brava veže za više kofa iste osobe. Kada ta osoba crpi vodu u više kofa, prva kofa se veže za bravu i po završetku crpljenja, druga kofa može neposredno da se veže za bravu i počne crpljenje; tek kada sve kofe završe, osoba vraća bravu čuvaru. Ceo tok crpljenja te osobe se uspešno odvija, a i oni koji čekaju posle nje uspešno će crpiti. To je reentrantna brava.

A kod nereentrantne brave čuvar dozvoljava da se brava veže samo za jednu kofu te osobe. Nakon što prva kofa počne i završi crpljenje, brava se ne oslobađa, pa druga kofa ne može da se veže za bravu niti da crpi. Trenutna nit zapada u mrtvu petlju, a sve niti u redu čekanja ne mogu da se probude.

Rekli smo da su i ReentrantLock i synchronized reentrantne brave. Uporedićemo preko izvornog koda reentrantnog ReentrantLock-a i nereentrantnog NonReentrantLock-a zašto nereentrantna brava pri ponovljenom pozivu sinhronizovanog resursa zapada u mrtvu petlju.

I ReentrantLock i NonReentrantLock nasleđuju roditeljsku klasu AQS, čije sinhrono stanje status broji broj reentriranja; status je na početku 0.

Kada nit pokuša da pribavi bravu, reentrantna brava prvo pokušava da pribavi i ažurira status: ako je status == 0, nijedna druga nit ne izvršava sinhronizovani kod, pa se status postavlja na 1 i trenutna nit počinje izvršavanje. Ako je status != 0, proverava se da li je trenutna nit baš ona koja drži bravu; ako jeste, status se uvećava za 1 i nit ponovo pribavlja bravu. Nereentrantna brava pak direktno pokušava da pribavi i ažurira trenutni status: ako je status != 0, pribavljanje brave ne uspeva i trenutna nit se blokira.

Pri oslobađanju brave, reentrantna brava takođe prvo čita trenutni status i, ako je trenutna nit zaista ona koja drži bravu: ako status-1 == 0, to znači da su svi ponovljeni pribavci brave izvršeni, pa tek tada nit zaista oslobađa bravu. Nereentrantna brava, pošto utvrdi da je trenutna nit nosilac brave, direktno postavlja status na 0 i oslobađa bravu.

Razlika u kodu — nefer nonfairTryAcquire:

final boolean nonfairTryAcquire(int acquires) {
    final Thread current = Thread.currentThread();
    int c = getState();
    if (c == 0) {
        if (compareAndSetState(0, acquires)) { // odmah uzima, bez reda
            setExclusiveOwnerThread(current);
            return true;
        }
    }
    ...
}

Fer varijanta (tryAcquire u FairSync) dodatno proverava hasQueuedPredecessors() — ima li neko u redu, pa tek onda pokušava CAS.

6. Ekskluzivna VS deljena brava

Ekskluzivna i deljena brava su takođe pojmovi. Najpre ćemo predstaviti konkretne pojmove, a zatim kroz izvorni kod ReentrantLock-a i ReentrantReadWriteLock-a objasniti ekskluzivnu i deljenu bravu.

Ekskluzivna brava (još poznata kao brava uzajamnog isključivanja) znači da jednu bravu u jednom trenutku može držati samo jedna nit. Ako nit T stavi ekskluzivnu bravu na podatak A, druge niti ne mogu na A staviti bilo koju vrstu brave. Nit koja drži ekskluzivnu bravu može i da čita i da menja podatak. synchronized iz JDK-a i implementacije Lock-a iz JUC-a su brave uzajamnog isključivanja.

Deljena brava znači da jednu bravu može držati više niti. Ako nit T stavi deljenu bravu na podatak A, druge niti mogu na A dodati samo deljenu bravu, ali ne i ekskluzivnu. Nit koja drži deljenu bravu može samo čitati podatak, ne i menjati ga.

Ekskluzivna i deljena brava ostvareni su takođe preko AQS-a, ali implementacijom različitih metoda postiže se ekskluzivnost, odnosno deljenost.

Ispod je deo izvornog koda ReentrantReadWriteLock-a:

Vidimo da ReentrantReadWriteLock ima dve brave: ReadLock i WriteLock — jedna čitalačka, jedna pisačka, zajednički „brava za čitanje/pisanje“. Dalje se vidi da su ReadLock i WriteLock ostvareni preko unutrašnje klase Sync. Sync je potklasa AQS-a, a takva struktura postoji i u CountDownLatch, ReentrantLock i Semaphore-u.

U ReentrantReadWriteLock-u je telo brave i za čitanje i za pisanje Sync, ali se način zaključavanja razlikuje. Brava za čitanje je deljena, a brava za pisanje ekskluzivna. Deljenost brave za čitanje omogućava vrlo efikasno paralelno čitanje, dok su čitanje-pisanje, pisanje-čitanje i pisanje-pisanje međusobno isključivi, jer su brava za čitanje i brava za pisanje razdvojene. Tako je konkurentnost ReentrantReadWriteLock-a znatno poboljšana u odnosu na običnu bravu uzajamnog isključivanja.

Koja je razlika u načinu zaključavanja brave za čitanje i brave za pisanje? Pre nego što pređemo na izvorni kod, podsetimo se još nečega. Na samom početku, pri pominjanju AQS-a, spomenuli smo i polje state (int, 32 bita) koje opisuje koliko niti drži bravu.

Kod ekskluzivne brave ta vrednost je obično 0 ili 1 (ako je reentrantna, state je broj reentriranja), dok je kod deljene brave state broj niti koje drže bravu. Ali u ReentrantReadWriteLock-u postoje dve brave — za čitanje i za pisanje — pa u jednom celobrojnom polju state treba opisati i brojčano stanje i brave za čitanje i brave za pisanje. Zato se state „seče po bitovima“ na dva dela: gornjih 16 bita opisuje stanje brave za čitanje (broj čitalaca), a donjih 16 bita stanje brave za pisanje (broj pisaca). Kao na slici:

ReadWriteLock state (int, 32 bita):
|----------------|----------------|
| gornjih 16 bita | donjih 16 bita |
| stanje čitanja | stanje pisanja |
|----------------|----------------|

Upoznavši pojmove, pređimo na kod — prvo na izvorni kod zaključavanja brave za pisanje:

protected final boolean tryAcquire(int acquires) {
	Thread current = Thread.currentThread();
	int c = getState(); // čita trenutni broj brava
	int w = exclusiveCount(c); // čita broj pisačkih brava w
	if (c != 0) { // ako neka nit već drži bravu (c!=0)
    // (Note: if c != 0 and w == 0 then shared count != 0)
		if (w == 0 || current != getExclusiveOwnerThread()) // ako je broj pisačkih niti (w) 0 (dakle postoji čitalačka brava) ili nit koja drži bravu nije trenutna nit, vrati neuspeh
			return false;
		if (w + exclusiveCount(acquires) > MAX_COUNT)    // ako broj pisačkih brava prekorači maksimum (65535, 2^16-1), baci Error
      throw new Error("Maximum lock count exceeded");
		// Reentrant acquire
    setState(c + acquires);
    return true;
  }
  if (writerShouldBlock() || !compareAndSetState(c, c + acquires)) // ako je trenutni broj pisačkih niti 0, a trenutna nit treba da se blokira — vrati neuspeh; ili ako CAS-om povećanje broja pisačkih niti ne uspe — takođe neuspeh
		return false;
	setExclusiveOwnerThread(current); // ako je c=0, w=0 ili c>0, w>0 (reentriranje), postavi trenutnu nit kao vlasnika brave
	return true;
}

• Ovaj kod najpre čita ukupan broj brava c, a zatim iz c dobavlja broj pisačkih brava w. Pošto je pisačka brava u donjih 16 bitova, uzima se maksimum donjih 16 bitova i radi se AND sa trenutnim c (int w = exclusiveCount©;); gornjih 16 bita AND sa 0 daje 0, pa preostaje vrednost donje operacije — ujedno i broj niti koje drže pisačku bravu.
• Nakon dobavljanja broja pisačkih niti, prvo se proverava da li je neka nit već zauzela bravu. Ako neka drži bravu (c!=0), gleda se broj pisačkih niti: ako je broj pisačkih niti 0 (dakle postoji čitalačka brava) ili nit koja drži bravu nije trenutna nit — vraća se neuspeh (ovde se radi o implementaciji pravedne i nepravedne brave).
• Ako broj pisačkih brava prelazi maksimum (65535, 2^16-1), baca se Error.
• Ako je broj pisačkih niti 0 (tada bi i broj čitalačkih trebao biti 0, jer je slučaj c!=0 već obrađen iznad), a trenutna nit treba da se blokira — vraća se neuspeh; ako CAS-om povećanje broja pisačkih niti ne uspe — takođe neuspeh.
• Ako je c=0, w=0 ili c>0, w>0 (reentriranje), postavlja se trenutna nit kao vlasnik brave — uspeh!

tryAcquire() pored uslova reentriranja (trenutna nit je ona koja drži pisačku bravu) uvodi i proveru postojanja čitalačke brave. Ako postoji čitalačka brava, pisačka brava se ne može pribaviti, jer mora biti obezbeđeno da operacije pisačke brave budu vidljive čitačkoj bravi; da je dozvoljeno pribavljanje pisačke brave dok je čitalačka već pribavljena, druge čitačke niti koje se izvršavaju ne bi mogle da opaze rad trenutne pisačke niti.

Zato se pisačka brava može pribaviti tek kada sve druge čitačke niti oslobode čitalačku bravu; a jednom pribavljena pisačka brava blokira sve naredne čitačke i pisačke niti. Oslobađanje pisačke brave je u suštini slično oslobađanju ReentrantLock-a: pri svakom oslobađanju smanjuje se pisačko stanje; kada ono postane 0, pisačka brava je oslobođena i niti koje čekaju na čitanje ili pisanje mogu nastaviti, pri čemu su izmene prethodne pisačke niti vidljive narednim čitačkim i pisačkim nitima.

Zatim sledi kod čitalačke brave:

protected final int tryAcquireShared(int unused) {
    Thread current = Thread.currentThread();
    int c = getState();
    if (exclusiveCount(c) != 0 &&
        getExclusiveOwnerThread() != current)
        return -1;                                  // ako je druga nit već pribavila pisačku bravu, trenutna nit ne uspeva da pribavi čitalačku i ulazi u čekanje
    int r = sharedCount(c);
    if (!readerShouldBlock() &&
        r < MAX_COUNT &&
        compareAndSetState(c, c + SHARED_UNIT)) {
        if (r == 0) {
            firstReader = current;
            firstReaderHoldCount = 1;
        } else if (firstReader == current) {
            firstReaderHoldCount++;
        } else {
            HoldCounter rh = cachedHoldCounter;
            if (rh == null || rh.tid != getThreadId(current))
                cachedHoldCounter = rh = readHolds.get();
            else if (rh.count == 0)
                readHolds.set(rh);
            rh.count++;
        }
        return 1;
    }
    return fullTryAcquireShared(current);
}

Vidimo da u tryAcquireShared(int unused), ako je druga nit već pribavila pisačku bravu, trenutna nit ne uspeva da pribavi čitalačku i ulazi u čekanje. Ako je trenutna nit pribavila pisačku bravu ili pisačka brava nije pribavljena, trenutna nit (na nitno-bezbedan način, CAS-om) povećava čitalačko stanje i uspešno pribavlja čitalačku bravu. Pri svakom oslobađanju čitalačke brave (nitno-bezbedno, jer više čitalačkih niti može istovremeno oslobađati) smanjuje se čitalačko stanje za „1<<16“. Zato brava za čitanje/pisanje omogućava deljenost čitanje-čitanje, a čitanje-pisanje, pisanje-čitanje i pisanje-pisanje su međusobno isključivi.

Sada se vratimo na izvorni kod zaključavanja pravedne i nepravedne brave u ReentrantLock-u:

U fer varijanti, tryAcquire pre CAS-a poziva hasQueuedPredecessors() — ako u redu čekanja već postoji nit, nova nit se stavlja na kraj reda. U nefer varijanti (nonfairTryAcquire) nema te provere: nit odmah pokušava CAS i može da "presretne" one koji čekaju.

Primećujemo da u ReentrantLock, iako postoje pravedna i nepravedna brava, u oba slučaja se dodaje ekskluzivna brava. Prema izvornom kodu, kada neka nit pozove lock da pribavi bravu, a sinhronizovani resurs nije zaključan drugom niti, trenutna nit nakon uspešnog CAS ažuriranja state-a preuzima taj resurs. Ako je resurs zauzet i to ne od strane trenutne niti, zaključavanje ne uspeva. Dakle, u ReentrantLock-u se i za čitanje i za pisanje dodaje ekskluzivna brava.

Zaključak

Ovaj članak daje osnovni prikaz uobičajenih brava u Javi i pojmova o bravama, sa uporednom analizom iz ugla izvornog koda i praktične primene. Zbog obima i nivoa znanja nismo sve sadržaje mogli detaljno da razradimo.

Java je same brave već dobro zapakovala, čime je u svakodnevnom radu programerima olakšano korišćenje. Ipak, programeri moraju poznavati principe rada brava na nižem nivou, kako bi u različitim scenarijima odabrali najpogodniju bravu. Ideje u izvornom kodu vredne su učenja i preuzimanja.

Reference

1. „Umetnost konkurentnog programiranja u Javi“
2. Brave u Javi
3. Analiza principa Java CAS
4. Java konkurentno — analiza ključne reči synchronized
5. Pregled principa Java synchronized
6. Razgovor o konkurentnosti (2) — synchronized u Java SE 1.6
7. Duboko razumevanje brave za čitanje/pisanje — analiza izvornog koda ReadWriteLock
8. JUC — analiza izvornog koda ReentrantReadWriteLock u JDK 1.8
9. Java višenitnost (10) — detaljna analiza ReentrantReadWriteLock
10. Java — princip realizacije brave za čitanje/pisanje

O autoru

• Jiaqi, inženjer pozadinskog sistema u Meituan-Dianpingu. Pristupio Meituan-Dianpingu 2017. godine, zadužen za razvoj poslovnog domena za domaće odmore.

Referentni link: https://tech.meituan.com/2018/11/15/java-lock.html, priredio: Erge

---

Na GitHub-u je konačno stiglo prvo izdanje PDF-aopen-source baze znanja sa preko 17000 zvezdica „Put ka boljoj Javi“! Obuhvata osnove sintakse Java-e, nizove i stringove, OOP, okvir kolekcija, Java IO, obradu izuzetaka, nove osobine Java-e, mrežno programiranje, NIO, konkurentno programiranje, JVM itd. — ukupno preko 320 000 reči i preko 500 ručno nacrtanih ilustracija, što se može opisati kao pristupačno i sa humorom... Više detalja: Odlično, Java tutorial sa preko 17000 zvezdica na GitHub-u