Preskoči na glavni sadržaj

Jedan članak da potpuno razjasnite princip Java implementacije CAS-a

Chenmo Wang ErJava jezgroJava konkurentno programiranje2666 reči9 minuta

CAS (Compare-and-Swap) je način implementacije optimističke brave, skraćenica je za „uporedi i zameni" i atomska je operacija bez brave.

U konkurentnom programiranju svi znamo da operacija i++ nije bezbedna za niti, jer i++ nije atomska operacija. O tome smo govorili kada smo pričali o kojim problemima donose više niti, sigurno se još sećate?

Kako garantovati atomičnost?

Uobičajeni pristup je zaključavanje.

U Javi možemo koristiti ključnu reč synchronized i CAS da postignemo efekat zaključavanja.

synchronized je pesimistička brava. Iako se sa nadogradnjom JDK verzija synchronized znatno „olakšao" (detaljno je opisano ranije, kliknite na link za podsetnik), i dalje je pesimistička brava. Nit, čim počne da izvršava prvi korak, mora da pribavi bravu; jednom kada pribavi bravu, druge niti koje uđu će biti blokirane i čekati bravu.

Ako vam je teško da to zamislite, uzećemo primer iz svakodnevnog života: osoba uđe u toalet i prvo zaključa vrata (pribavlja bravu), zatim počne da koristi toalet. U tom trenutku, ako dođu drugi ljudi, mogu samo da čekaju napolju (blokada), čak i ako im je veoma hitno, ne pomaže. Kada završi, otključa vrata (otključavanje) i drugi mogu da uđu.

CAS je optimistička brava. Nit pri izvršenju ne zaključava; pretpostavlja da u tom trenutku nema sukoba, a zatim obavlja određenu operaciju; ako ne uspe zbog sukoba, pokušava ponovo, sve dok ne uspe.

Optimistička i pesimistička brava

Brave se mogu klasifikovati iz različitih uglova. Na primer, kada smo ranije pričali o četiri stanja brave synchronized, pomenuli smo biasovanu bravu, laku bravu i tešku bravu, zar ne? Optimistička i pesimistička brava su takođe jedan način klasifikacije.

Pesimistička brava

Za pesimističku bravu, uvek se smatra da će pri svakom pristupu deljenom resursu doći do sukoba, pa se mora zaključati svaka operacija nad podacima, kako bi se osiguralo da program u kritičnoj sekciji u jednom trenutku izvršava samo jedna nit.

Optimistička brava

Optimistička brava je, kao što joj ime kaže, optimistična. Optimistička brava uvek pretpostavlja da pristup deljenom resursu nema sukoba, pa nit može neprekidno da se izvršava, bez zaključavanja i bez čekanja. Čim dođe do sukoba između više niti, optimistička brava obično koristi tehniku koja se zove CAS da bi garantovala bezbednost izvršenja niti.

Pošto optimistička brava pretpostavlja da u operaciji nema brave, malo je verovatno da će se pojaviti mrtva blokada. Drugim rečima, optimistička brava je prirodno imuna na mrtvu blokadu.

  • Optimistička brava se više koristi u okruženjima sa „mnogo čitanja, malo pisanja", kako bi se izbeglo da često zaključavanje utiče na performanse.
  • Pesimistička brava se više koristi u okruženjima sa „mnogo pisanja, malo čitanja", kako bi se izbeglo da česti neuspesi i ponovni pokušaji utiču na performanse.

Šta je CAS

U CAS-u postoje tri vrednosti:

  • V: promenljiva koju treba ažurirati (var)
  • E: očekivana vrednost (expected)
  • N: nova vrednost (new)

Proces upoređivanja i zamene je sledeći:

Proverava se da li je V jednako E; ako jeste, vrednost V se postavlja na N; ako nije, to znači da je V već ažurirala neka druga nit, pa trenutna nit odustaje od ažuriranja i ne radi ništa.

Ovde očekivana vrednost E suštinski označava „staru vrednost".

Objasnićemo ovaj proces jednostavnim primerom:

  1. Ako je promenljiva i koju deli više niti prvobitno bila 5, a ja sam u niti A i želim da je postavim na novu vrednost 6.
  2. Koristimo CAS za taj posao.
  3. Prvo poredimo i sa 5 i otkrivamo da je jednako 5, što znači da je nijedna druga nit nije promenila, pa ću je postaviti na novu vrednost 6. Ovaj CAS je uspeo; vrednost i je postavljena na 6.
  4. Ako nije jednako 5, to znači da je i promenila neka druga nit (na primer, vrednost i je sada 2), pa ja ne radim ništa. Ovaj CAS nije uspeo; vrednost i i dalje ostaje 2.

U ovom primeru, i je V, 5 je E, a 6 je N.

Da li je moguće da, nakon što utvrdim da je i jednako 5, baš kad se spremam da ažuriram njenu novu vrednost, neka druga nit promeni vrednost i?

Nije. Jer CAS je atomska operacija; to je sistemska primitiva, atomska instrukcija CPU-a, i na nivou CPU-a je već garantovana njena atomičnost.

Kada više niti istovremeno koristi CAS nad jednom promenljivom, samo će jedna pobediti i uspešno ažurirati; sve ostale će ne uspeti, ali niti koje ne uspešu neće biti obustavljene — samo će biti obaveštene o neuspehu i dozvoljeno im je da pokušaju ponovo. Naravno, nitima koje ne uspeju je dozvoljeno i da odustanu od operacije.

Princip CAS-a

Pomenuli smo da je CAS atomska operacija. Kako Java koristi CAS? Znamo da u Javi, ako je metoda native, onda Java ne odgovara za njenu konkretnu implementaciju, već to prepušta donjoj JVM sloju koji je implementira u C-u ili C++-u.

U Javi postoji klasa Unsafe (detaljno će biti obrađena kasnije, kliknite na link za direktan pristup), koja se nalazi u paketu sun.misc. U njoj su neke native metode, od kojih se nekoliko odnosi na CAS:

boolean compareAndSwapObject(Object o, long offset,Object expected, Object x);
boolean compareAndSwapInt(Object o, long offset,int expected,int x);
boolean compareAndSwapLong(Object o, long offset,long expected,long x);

Unsafe implementira CAS preko C++-a, a konkretna implementacija zavisi od operativnog sistema i CPU-a.

Na Linuxu sa X86, CAS operacija se na CPU-u uglavnom obavlja preko instrukcije cmpxchgl, ali u slučaju više procesora mora se koristiti lock instrukcija za zaključavanje. Naravno, različiti operativni sistemi i procesori sigurno se razlikuju u načinu implementacije.

CMPXCHG je skraćenica od „Compare and Exchange". To je atomska instrukcija koja služi za bezbednu izmenu deljenih podataka u višejzgarnom/višenitnom okruženju. CMPXCHG postoji u mnogim modernim mikroprocesorskim arhitekturama, na primer Intel x86/x64. Za 32-bitne operande ova instrukcija se obično naziva CMPXCHG, dok se za 64-bitne operande naziva CMPXCHG8B ili CMPXCHG16B.

Pored gore pomenutih metoda, u klasi Unsafe postoje i druge metode. Na primer, metode park i unpark koje podržavaju obustavu i nastavak niti — klasa LockSupport (o kojoj će biti reči kasnije) na dnu poziva ove dve metode. Tu je i metoda allocateInstance() koja podržava refleksiju.

Kako CAS implementira atomsku operaciju?

Gore smo predstavili nekoliko metoda klase Unsafe koje podržavaju CAS. Kako konkretno Java pomoću ovih metoda implementira atomsku operaciju?

JDK pruža neke klase za atomske operacije, u paketu java.util.concurrent.atomic. U JDK 8 postoje sledeće klase:

Iz imena se može naslutiti opšta namena ovih klasa (atomske klase će biti detaljno obrađene kasnije, kliknite na link za direktan pristup):

  • Atomsko ažuriranje osnovnih tipova
  • Atomsko ažuriranje nizova
  • Atomsko ažuriranje referenci
  • Atomsko ažuriranje polja (svojstava)

Ovde ćemo na primeru metode getAndAdd(int delta) klase AtomicInteger pokazati kako Java implementuje atomsku operaciju.

Hajde prvo da pogledamo izvorni kod metode getAndAdd:

public final int getAndAdd(int delta) {
    return unsafe.getAndAddInt(this, valueOffset, delta);
}

Ovde je unsafe zapravo jedan Unsafe objekat:

// setup to use Unsafe.compareAndSwapInt for updates
private static final Unsafe unsafe = Unsafe.getUnsafe();

Dakle, metoda getAndAdd() klase AtomicInteger je implementirana pozivom metode klase Unsafe:

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;
}

Hajde detaljno da analiziramo ovaj kod, prvo parametre:

  • Object var1, ovaj parametar predstavlja objekat nad kojim želite da izvršite operaciju.
  • long var2, ovaj parametar je pomeraj (offset) nekog polja u objektu var1 nad kojim želite da operišete. Ovaj pomeraj se može dobiti metodom objectFieldOffset klase Unsafe.
  • int var4, ovaj parametar je vrednost za koju želite da uvećate.

Sada da pogledamo proces izvršenja metode:

  • Prvo, na početku do while petlje, preko this.getIntVolatile(var1, var2) dobija se vrednost zadatog polja trenutnog objekta i smešta u privremenu promenljivu var5. Metoda getIntVolatile ovde može da garantuje vidljivost operacije čitanja, odnosno da je pročitani rezultat najnoviji rezultat upisa, i da zbog strategija optimizacije JVM-a (kao što je preraspodela instrukcija) ili keša CPU-a neće biti pročitani zastareli podaci.
  • Zatim se izvršava compareAndSwapInt(var1, var2, var5, var5 + var4) za CAS operaciju. Ako je vrednost objekta var1 na memorijskoj adresi var2 jednaka očekivanoj vrednosti var5, vrednost na toj poziciji se ažurira na var5 + var4 i vraća true; inače se ne radi ništa i vraća false.
  • Ako je CAS operacija uspela, to znači da smo uspešno ažurirali vrednost polja na pomeraju var2 objekta var1 na var5 + var4, i da je to ažuriranje atomično, pa izlazimo iz petlje i vraćamo staru vrednost var5.
  • Ako CAS operacija ne uspe, to znači da su u trenutku dok smo pokušavali da ažuriramo vrednost, druge niti izmenile vrednost tog polja, pa nastavljamo petlju, ponovo dobijamo vrednost polja i pokušavamo CAS operaciju.

Ovde se koristi do-while petlja. Ovakva petlja nije česta; njen cilj je da garantuje da će se naredbe u telu petlje izvršiti barem jednom. Tako se garantuje da je vraćena vrednost ona koju očekujemo.

U JDK 9 i kasnijim verzijama, metoda getAndAddInt se razlikuje od implementacije u JDK 8. Hajde da uzmemo izvorni kod JDK 11 za poređenje:

@HotSpotIntrinsicCandidate
public final int getAndAddInt(Object o, long offset, int delta) {
    int v;
    do {
        v = getIntVolatile(o, offset);
    } while (!weakCompareAndSetInt(o, offset, v, v + delta));
    return v;
}

Iznad ove metode je dodata anotacija @HotSpotIntrinsicCandidate. Ova anotacija dozvoljava HotSpot VM-u sam da napiše asembler ili IR kompajler za implementaciju ove metode kako bi pružio bolje performanse.

IR (Intermediate Representation) je metoda predstavljanja intermedijernog koda koja služi za pomoć u optimizaciji kompajlera. Kompajler obično prvo pretvara izvorni kod u IR, zatim vrši razne optimizacije nad IR-om, i konačno pretvara optimizovani IR u ciljni kod. U JVM-u (Java Virtual Machine), JIT (Just-In-Time) kompajler pretvara Java bajtkod (odnosno sadržaj .class datoteke) u IR, zatim vrši optimizacije nad IR-om, i konačno kompajlira IR u mašinski kod. Ovaj proces se obavlja tokom izvršenja Java programa, pa se naziva „just-in-time kompajliranje". C1 i C2 kompajleri u JVM-u su IR kompajleri. C1 kompajler pri kompajliranju vrši neke jednostavne optimizacije, a zatim brzo kompajlira IR u mašinski kod. C2 kompajler pri kompajliranju vrši dublje optimizacije kako bi dobio veću efikasnost izvršenja, ali mu je i vreme kompajliranja relativno duže.

Odnosno, iako površinski vidimo weakCompareAndSet i compareAndSet, ne isključuje se mogućnost da HotSpot VM ručno implementira pravu funkcionalnost weakCompareAndSet.

Jednostavno rečeno, operacija weakCompareAndSet zadržava samo osobine same volatile promenljive, a isključuje memorijsku semantiku koju donose happens-before pravila. Drugim rečima, weakCompareAndSet ne može da garantuje redosled izvršenja drugih promenljivih osim volatile promenljive koja je cilj operacije (kompajler i procesor mogu prerasporediti sekvencu instrukcija radi optimizacije performansi programa), niti može da garantuje vidljivost tih promenljivih. Ali to do određene mere može poboljšati performanse.

Da se vratimo na uslov petlje — vidi se da se neprekidno pokušava sa CAS ažuriranjem. Ako ažuriranje ne uspe, pokušava se ponovo.

Zašto se operacija dobijanja „stare vrednosti" v stavlja u telo petlje?

I to je lako razumljivo. ranije smo rekli: ako CAS-ova stara vrednost V nije jednaka očekivanoj vrednosti E, ažuriranje će neuspeti. To znači da se stara vrednost promenila. Naravno da onda moramo da vratimo staru vrednost nakon što ju je promenila druga nit, pa se zato nalazi u telu do petlje.

Tri velika problema CAS-a

Iako CAS pruža efikasno sredstvo sinhronizacije, postoji i nekoliko problema, uglavnom sledeća tri: ABA problem, dugotrajni spinning, atomska operacija nad više deljenih promenljivih.

ABA problem

ABA problem je sledeći: vrednost je prvobitno bila A, promenjena u B, pa vraćena u A. U tom slučaju CAS ne može da otkrije promenu, iako je zapravo ažurirana dva puta.

Rešenje ABA problema je dodavanje broja verzije ili vremenske oznake ispred promenljive. Počevši od JDK 1.5, JDK-ov atomic paket pruža klasu AtomicStampedReference za rešavanje ABA problema.

Metoda compareAndSet ove klase prvo proverava da li je trenutna referenca jednaka očekivanoj referenci i da li je trenutna oznaka jednaka očekivanoj oznaci; tek ako su oba jednaka, koristi CAS za postavljanje nove vrednosti i oznake.

public boolean compareAndSet(V   expectedReference,
                              V   newReference,
                              int expectedStamp,
                              int newStamp) {
    Pair<V> current = pair;
    return
        expectedReference == current.reference &&
        expectedStamp == current.stamp &&
        ((newReference == current.reference &&
          newStamp == current.stamp) ||
          casPair(current, Pair.of(newReference, newStamp)));
}

Hajde prvo da pogledamo parametre:

  • expectedReference: očekivana referenca, odnosno referenca za koju mislite da bi trebalo da se nalazi na toj poziciji.
  • newReference: nova referenca; ako je očekivana referenca tačna, nova referenca će biti postavljena na tu poziciju.
  • expectedStamp: očekivana oznaka, to je oznaka za koju mislite da bi trebalo da se nalazi na toj poziciji.
  • newStamp: nova oznaka; ako je očekivana oznaka tačna, nova oznaka će biti postavljena na tu poziciju.

Tok izvršenja:

①. Pair<V> current = pair; — ovaj red koda dobija trenutni pair objekat, koji sadrži referencu i oznaku.

②. Sledeća return naredba vrši nekoliko provera:

  • expectedReference == current.reference && expectedStamp == current.stamp: prvo se proverava da li su trenutna referenca i oznaka jednaki očekivanoj referenci i oznaci. Ako bilo šta od toga nije jednako, metoda će vratiti false.
  • Ako gore navedena provera prođe, odnosno ako su trenutna referenca i oznaka jednaki očekivanim, zatim se proverava da li su i nova referenca i oznaka jednaki trenutnim. Ako jesu, zapravo nema potrebe za bilo kakvom promenom i metoda vraća true.
  • Ako se nova referenca ili oznaka razlikuju od trenutnih, poziva se metoda casPair koja pokušava da ažurira pair objekat. Metoda casPair pokušava da zameni trenutni pair objekat novim Pair objektom kreiranim od newReference i newStamp. Ako zamena uspe, casPair vraća true; ako ne uspe (odnosno ako je u toku pokušaja zamene pair objekat već promenila druga nit), casPair vraća false.

Dugotrajni spinning

CAS se često kombinuje sa spinningom. Ako spinning CAS dugo ne uspe, zauzeće velike količine CPU resursa.

Rešenje je da JVM podrži pause instrukciju koju pruža procesor.

Pause instrukcija omogućava da CPU pri neuspehu spinninga na kraće vreme pređe u stanje mirovanja pre nego što nastavi sa spinningom, čime se znatno smanjuje učestalost operacija čitanja, a i troškovi preraspodele protoka CPU-a radi rešavanja sukoba u redosledu memorije biće mnogo manji.

Atomska operacija nad više deljenih promenljivih

Kada se operacija obavlja nad jednom deljenom promenljivom, CAS može da garantuje atomičnost te promenljive. Ali za više deljenih promenljivih, CAS ne može da garantuje atomičnost operacije. Tada obično postoje dva pristupa:

  1. Koristiti klasu AtomicReference da se garantuje atomičnost između objekata, tako što se više promenljivih stavlja u jedan objekat nad kojim se vrši CAS operacija.
  2. Koristiti bravu. Kôd u kritičnoj sekciji unutar brave može da garantuje da samo trenutna nit može da operiše.

Rezime

CAS (Compare-and-Swap) je algoritam koji se široko koristi u kontroli konkurentnosti. To je način implementacije optimističke brave. CAS je skraćenica za „uporedi i zameni" i atomska je operacija bez brave.

Puno ime CAS-a je: uporedi i zameni (Compare And Swap). U CAS-u postoje tri vrednosti:

  • V: promenljiva koju treba ažurirati (var)
  • E: očekivana vrednost (expected)
  • N: nova vrednost (new)

Proces upoređivanja i zamene je sledeći:

Proverava se da li je V jednako E; ako jeste, vrednost V se postavlja na N; ako nije, to znači da je V već ažurirala neka druga nit, pa trenutna nit odustaje od ažuriranja i ne radi ništa.

Ovde očekivana vrednost E suštinski označava „staru vrednost".

CAS je dobar, ali ima i problema, kao što su ABA problem, veliki troškovi zbog dugog vremena petlje, i to što može da garantuje atomsku operaciju samo nad jednom deljenom promenljivom. U razvoju treba na osnovu stvarne situacije da biramo da li ćemo koristiti CAS ili bravu.

Urednik: Chenmo Wang Er. Sadržaj pre uređivanja potiče iz ovog otvorenog repozitorijuma mog prijatelja: Java višenitnost jednostavno objašnjena, toplo preporučujem.