streamalism.org

1. Uvod

U ovom uputstvu naučit ćemo što su neblokirajuće strukture podataka i zašto su važna alternativa istodobnim podatkovnim strukturama temeljenim na zaključavanju.

Prvo ćemo razmotriti neke pojmove poput bez prepreka, bez zaključavanja, i bez čekanja.

Drugo, pogledat ćemo osnovne građevne blokove neblokirajućih algoritama poput CAS (usporedi i zamijeni).

Treće, razmotrit ćemo implementaciju reda bez zaključavanja u Javi i na kraju ćemo iznijeti pristup kako to postići čekanje-sloboda.

2. Zaključaj protiv gladi

Prvo, pogledajmo razlika između začepljene i izgladnjele niti.

Na gornjoj slici, nit 2 dobiva blokadu na strukturi podataka. Kad Thread 1 pokuša dobiti i bravu, treba pričekati da Thread 2 otpusti bravu; neće se nastaviti prije nego što uspije zaključati. Ako suspendiramo Thread 2 dok drži zaključan, Thread 1 morat će zauvijek čekati.

Sljedeća slika ilustrira izgladnjivanje niti:

Ovdje Thread 2 pristupa strukturi podataka, ali ne dobiva zaključavanje. Nit 1 pokušava istodobno pristupiti strukturi podataka, otkriva istodobni pristup i odmah se vraća, obavještavajući nit da ne može dovršiti (crvenu) operaciju. Nit 1 zatim će pokušati ponovo dok ne uspije dovršiti operaciju (zeleno).

Prednost ovog pristupa je što nam ne treba brava. Međutim, ono što se može dogoditi je da ako nit 2 (ili druge niti) pristupi strukturi podataka s visokom frekvencijom, tada nit 1 treba velik broj pokušaja dok konačno ne uspije. To nazivamo izgladnjivanjem.

Kasnije ćemo vidjeti kako usporediti i zamijeniti operacijom se postiže neblokirajući pristup.

3. Vrste neblokirajućih struktura podataka

Možemo razlikovati tri razine neblokirajućih struktura podataka.

3.1. Bez prepreka

Sloboda prepreka najslabiji je oblik neblokirajuće strukture podataka. Ovdje zahtijevamo da se zajamči nastavak niti samo ako su sve ostale niti suspendirane.

Točnije, nit neće i dalje gladovati ako su sve ostale niti suspendirane. To se razlikuje od upotrebe brava u tom smislu, da ako nit čeka bravu, a nit koja drži bravu suspendirana, nit koja čeka čeka zauvijek.

3.2. Bez zaključavanja

Struktura podataka pruža slobodu zaključavanja ako u bilo kojem trenutku može nastaviti barem jedna nit. Sve ostale niti mogu gladovati. Razlika u slobodi ometanja je u tome što postoji barem jedna nit koja ne gladuje, čak iako niti jedna niti nije ovješena.

3.3. Bez čekanja

Struktura podataka je bez čekanja ako je bez zaključavanja i zajamčeno je da će se svaka nit nastaviti nakon konačnog broja koraka, odnosno niti neće gladovati zbog "nerazumno velikog" broja koraka.

3.4. Sažetak

Sažmimo ove definicije u grafičkom prikazu:

Prvi dio slike prikazuje slobodu prepreka jer nit 1 (gornja nit) može nastaviti (zelena strelica) čim suspendiramo ostale niti (pri dnu žuto).

Srednji dio prikazuje slobodu zaključavanja. Barem nit 1 može napredovati dok drugi mogu gladovati (crvena strelica).

Posljednji dio prikazuje slobodu čekanja. Ovdje jamčimo da se nit 1 može nastaviti (zelena strelica) nakon određenog razdoblja gladovanja (crvene strelice).

4. Primici koji ne blokiraju

U ovom ćemo odjeljku pogledati tri osnovne operacije koje nam pomažu u izgradnji operacija bez zaključavanja na podatkovnim strukturama.

4.1. Usporedite i zamijenite

Jedna od osnovnih operacija koja se koristi za izbjegavanje zaključavanja je usporediti i zamijeniti (CAS) operacija.

Ideja usporedi i zamijeni je da se varijabla ažurira samo ako i dalje ima istu vrijednost kao u vrijeme kada smo vrijednost varijable dohvaćali iz glavne memorije. CAS je atomska operacija, što znači da su zajedničko preuzimanje i ažuriranje jedna operacija:

Ovdje obje niti dohvaćaju vrijednost 3 iz glavne memorije. Nit 2 uspijeva (zeleno) i ažurira varijablu na 8. Kako prvi CAS pomoću niti 1 očekuje da vrijednost bude i dalje 3, CAS ne uspijeva (crveno). Stoga Thread 1 ponovno dohvaća vrijednost i drugi CAS uspijeva.

Ovdje je najvažnije da CAS ne dobije blokadu strukture podataka već se vraća pravi ako je ažuriranje bilo uspješno, u suprotnom se vraća lažno.

Sljedeći isječak koda opisuje kako CAS funkcionira:

volatile int vrijednost; logička vrijednost cas (int očekivana vrijednost, int nova vrijednost) {if (vrijednost == očekivana vrijednost) {vrijednost = nova vrijednost; povratak istinit; } return false; }

Vrijednost ažuriramo novom vrijednošću samo ako još uvijek ima očekivanu vrijednost, u suprotnom se vraća lažno. Sljedeći isječak koda pokazuje kako se CAS može nazvati:

void testCas () {int v = vrijednost; int x = v + 1; while (! cas (v, x)) {v = vrijednost; x = v + 1; }}

Pokušavamo ažurirati našu vrijednost dok CAS operacija ne uspije, odnosno ne vrati se pravi.

Međutim, moguće je da nit zaglavi u gladovanju. To se može dogoditi ako druge niti istodobno izvrše CAS na istoj varijabli, tako da operacija nikada neće uspjeti za određenu nit (ili će joj trebati nerazumno puno vremena). Ipak, ako usporediti i zamijeniti ne uspije, znamo da je uspjela još jedna nit, stoga osiguravamo i globalni napredak, potreban za slobodu zaključavanja.

Važno je napomenuti da bi hardver trebao podržavati usporediti i zamijeniti, kako bi to bila istinski atomska operacija bez upotrebe zaključavanja.

Java omogućuje implementaciju usporediti i zamijeniti u razredu sunce.misc.Nesigurno. Međutim, u većini slučajeva ne bismo trebali koristiti ovu klasu izravno, već atomske varijable.

Nadalje, usporediti i zamijeniti ne sprečava problem A-B-A. To ćemo pogledati u sljedećem odjeljku.

4.2. Load-Link / Store-Conditional

Alternativa za usporediti i zamijeniti je load-link / store-conditional. Ponovno posjetimo usporediti i zamijeniti. Kao što smo već vidjeli, CAS ažurira vrijednost samo ako je vrijednost u glavnoj memoriji i dalje vrijednost za koju očekujemo da će biti.

Međutim, CAS također uspije da se vrijednost promijenila, a u međuvremenu se vratila na svoju prethodnu vrijednost.

Sljedeća slika ilustrira ovu situaciju:

Obje, nit 1 i nit 2 očitavaju vrijednost varijable, koja je 3. Tada nit 2 izvodi CAS, koji uspijeva postaviti varijablu na 8. Zatim opet, nit 2 izvodi CAS da vrati varijablu na 3, što i uspijeva. Konačno, Thread 1 izvodi CAS, očekujući vrijednost 3, i također uspijeva, iako je vrijednost naše varijable između dvaput modificirana.

To se naziva A-B-A problem. Ovo ponašanje možda neće predstavljati problem, ovisno o slučaju upotrebe, naravno. Međutim, to možda ne bi bilo poželjno za druge. Java omogućuje implementaciju load-link / store-conditional s AtomicStampedReference razred.

4.3. Dohvati i dodaj

Druga alternativa je dohvati i dodaj. Ova operacija povećava varijablu u glavnoj memoriji za zadanu vrijednost. Opet, važna je stvar da se operacija odvija atomski, što znači da niti jedna druga nit ne može ometati.

Java pruža implementaciju dohvati i dodaj u svojim atomskim klasama. Primjeri su AtomicInteger.incrementAndGet (), koji povećava vrijednost i vraća novu vrijednost; i AtomicInteger.getAndIncrement (), koji vraća staru vrijednost, a zatim povećava vrijednost.

5. Pristup povezanom redu iz više niti

Da bismo bolje razumjeli problem dviju (ili više) niti koje istovremeno pristupaju redu, pogledajmo povezani red i dvije niti koje istodobno pokušavaju dodati element.

Red čekanja koji ćemo pogledati dvostruko je povezan FIFO red u koji dodajemo nove elemente nakon posljednjeg elementa (L) i varijable rep upućuje na taj posljednji element:

Da bi dodali novi element, niti trebaju izvršiti tri koraka: 1) stvoriti nove elemente (N i M), s pokazivačem na sljedeći element postavljen na null; 2) imaju referencu na prethodni element ukazuju na L, a referencu na sljedeći element u L ukazuju na N (M, odnosno). 3) Imati rep pokažite na N (M):

Što može poći po krivu ako dvije niti istovremeno izvršavaju ove korake? Ako se koraci na gornjoj slici izvrše redom ABCD ili ACBD, L, kao i rep, pokazat će na M. N će i dalje biti isključen iz reda.

Ako se koraci izvršavaju po nalogu ACDB, rep ukazat će na N, dok će L ukazivati ​​na M, što će uzrokovati nedosljednost u redu:

Naravno, jedan od načina za rješavanje ovog problema je da jedna nit stekne bravu u redu. Rješenje koje ćemo razmotriti u sljedećem poglavlju riješit će problem uz pomoć operacije bez zaključavanja pomoću CAS operacije koju smo ranije vidjeli.

6. Neblokirajući red u Javi

Pogledajmo osnovni red bez zaključavanja u Javi. Prvo, pogledajmo članove razreda i konstruktor:

javna klasa NonBlockingQueue {privatni konačni AtomicReference glava, rep; privatna konačna veličina AtomicInteger; javna NonBlockingQueue () {head = nova AtomicReference (null); rep = novo AtomicReference (null); veličina = novo AtomicInteger (); size.set (0); }}

Važan dio je izjava o referencama glave i repa kao AtomicReferences, što osigurava da je svako ažuriranje ovih referenci atomska operacija. Ovaj tip podataka u Javi provodi potrebno usporediti i zamijeniti operacija.

Dalje, pogledajmo implementaciju klase Node:

private class Node {privatna volatilna T vrijednost; privatni hlapljivi čvor sljedeći; privatni volatilni čvor prethodni; javni čvor (vrijednost T) {this.value = vrijednost; this.next = null; } // geteri i postavljači}

Ovdje je važan dio deklariranje referenci na prethodni i sljedeći čvor kao hlapljiv. To osigurava da ove reference ažuriramo uvijek u glavnoj memoriji (stoga su izravno vidljive svim nitima). Isto za stvarnu vrijednost čvora.

6.1. Bez zaključavanja dodati

Naše bez zaključavanja dodati operacija će osigurati da novi element dodamo u rep i da neće biti odvojena od reda, čak i ako više niti istovremeno želi dodati novi element:

javna void dodaj (T element) {if (element == null) {baciti novi NullPointerException (); } Čvor čvor = novi čvor (element); Node currentTail; do {currentTail = tail.get (); node.setPrevious (currentTail); } while (! tail.compareAndSet (currentTail, čvor)); if (node.previous! = null) {node.previous.next = node; } head.compareAndSet (null, node); // za umetanje veličine prvog elementa.incrementAndGet (); }

Bitan dio na koji treba obratiti pažnju je istaknuta crta. Pokušavamo dodati novi čvor u red sve dok CAS operacija ne uspije ažurirati rep, koji i dalje mora biti isti rep kojem smo dodali novi čvor.

6.2. Bez zaključavanja dobiti

Slično operaciji dodavanja, i operacija dobivanja bez zaključavanja pobrinut će se da vratimo zadnji element i pomaknemo rep u trenutni položaj:

javno T get () {if (head.get () == null) {throw new NoSuchElementException (); } Čvor currentHead; Čvor nextNode; do {currentHead = head.get (); nextNode = currentHead.getNext (); } while (! head.compareAndSet (currentHead, nextNode)); size.decrementAndGet (); vratiti currentHead.getValue (); }

Opet, bitan dio na koji treba obratiti pažnju je istaknuta crta. CAS operacija osigurava pomicanje trenutne glave samo ako u međuvremenu nije uklonjen nijedan drugi čvor.

Java već nudi implementaciju neblokirajućeg reda, ConcurrentLinkedQueue. To je implementacija reda bez zaključavanja M. Michaela i L. Scotta opisana u ovom radu. Zanimljiva je napomena ovdje da Java dokumentacija navodi da je to bez čekanja red, gdje je zapravo bez zaključavanja. Java 8 dokumentacija ispravno poziva implementaciju bez zaključavanja.

7. Redovi bez čekanja

Kao što smo vidjeli, gornja implementacija je bez zaključavanjameđutim, nije bez čekanja. The dok petlje u obje dodati i dobiti metoda može se petljati dulje vrijeme (ili, iako je malo vjerojatno, zauvijek) ako postoji mnogo niti koje pristupaju našem redu.

Kako možemo postići slobodu čekanja? Implementacija algoritama bez čekanja, općenito, prilično je lukav. Zainteresiranog čitatelja upućujemo na ovaj rad koji detaljno opisuje red bez čekanja. U ovom ćemo članku pogledati osnovnu ideju o tome kako možemo pristupiti implementaciji reda bez čekanja.

Red bez čekanja zahtijeva da svaka nit postigne zajamčeni napredak (nakon konačnog broja koraka). Drugim riječima, dok petlje u našim metodama dodavanja i dobivanja moraju uspjeti nakon određenog broja koraka.

Da bismo to postigli, svakoj niti dodijelimo pomoćnu nit. Ako ta pomoćna nit uspije dodati element u red, to će pomoći drugoj niti da umetne svoj element prije umetanja drugog elementa.

Kako pomoćna nit ima pomoćnika sama, a na cijelom popisu niti svaka nit ima pomoćnika, možemo jamčiti da nit uspije umetanje najkasnije nakon što svaka nit izvrši jedno umetanje. Sljedeća slika ilustrira ideju:

Naravno, stvari se zakompliciraju kada možemo dinamički dodavati ili uklanjati niti.

8. Zaključak

U ovom smo članku vidjeli osnove neblokirajućih struktura podataka. Objasnili smo različite razine i osnovne operacije poput usporediti i zamijeniti.

Zatim smo pogledali osnovnu implementaciju a bez zaključavanja red u Javi. Na kraju smo iznijeli ideju kako to postići čekanje-sloboda.

Potpuni izvorni kod za sve primjere u ovom članku dostupan je na GitHubu.