Úvod do bezzámkových dátových štruktúr s príkladmi Java

1. Úvod

V tomto výučbe sa dozvieme, čo sú neblokujúce dátové štruktúry a prečo sú dôležitou alternatívou k súbežným dátovým štruktúram založeným na uzamknutí.

Najskôr si prejdeme niektoré pojmy ako bez prekážok, bez zámkova bez čakania.

Po druhé, pozrieme sa na základné stavebné bloky neblokujúcich algoritmov, ako napríklad CAS (porovnaj a zamieňaj).

Po tretie, pozrieme sa na implementáciu bezbariérového frontu v Jave a nakoniec načrtneme prístup, ako dosiahnuť sloboda čakania.

2. Zamknite verzus hladovanie

Najprv sa pozrime na rozdiel medzi blokovanou a hladujúcou niťou.

Na obrázku vyššie vlákno 2 získava zámok v dátovej štruktúre. Keď sa vlákno 1 pokúsi získať tiež zámok, musí počkať, kým vlákno 2 zámok neuvoľní; nebude pokračovať skôr, ako získa zámok. Ak pozastavíme vlákno 2, kým drží zámok, vlákno 1 bude musieť čakať večne.

Nasledujúci obrázok ilustruje hladovanie vlákien:

Tu vlákno 2 pristupuje k dátovej štruktúre, ale nezíska zámok. Vlákno 1 sa pokúša súčasne získať prístup k dátovej štruktúre, zistí súbežný prístup a okamžite sa vráti a informuje vlákno, že operáciu nemohlo dokončiť (červene). Vlákno 1 sa potom pokúsi znova, kým sa nepodarí dokončiť operáciu (zelené).

Výhodou tohto prístupu je, že nepotrebujeme zámok. Čo sa však môže stať, je to, že ak vlákno 2 (alebo iné vlákna) pristupuje k dátovej štruktúre s vysokou frekvenciou, potom vlákno 1 potrebuje veľký počet pokusov, kým bude nakoniec úspešný. Hovoríme tomu hladovka.

Neskôr uvidíme, ako porovnať a vymeniť prevádzka dosahuje neblokujúci prístup.

3. Typy neblokujúcich dátových štruktúr

Môžeme rozlišovať medzi tromi úrovňami neblokujúcich dátových štruktúr.

3.1. Bez prekážok

Sloboda prekážok je najslabšou formou neblokujúcej dátovej štruktúry. Tu vyžadujeme, aby zaručené pokračovanie vlákna bolo iba v prípade, že sú pozastavené všetky ostatné vlákna.

Presnejšie, vlákno nebude pokračovať v hladovaní, ak budú všetky ostatné vlákna pozastavené. To sa líši od používania zámkov v tom zmysle, že ak vlákno čakalo na zámok a vlákno, ktoré drží zámok, je pozastavené, čakajúce vlákno by čakalo navždy.

3.2. Bez zámkov

Dátová štruktúra poskytuje voľnosť uzamknutia, ak môže kedykoľvek pokračovať aspoň jedno vlákno. Všetky ostatné vlákna môžu hladovať. Rozdiel v slobode prekážok je v tom, že existuje najmenej jedno vlákno, ktoré nehladuje, aj keď nie sú pozastavené.

3.3. Bez čakania

Dátová štruktúra je bez čakania, ak je uzamknutá a každé vlákno bude zaručene pokračovať po konečnom počte krokov, to znamená, že vlákna nebudú hladovať po „neprimerane veľkom“ počte krokov.

3.4. Zhrnutie

Zhrňme tieto definície v grafickom znázornení:

Prvá časť obrázka zobrazuje voľnosť prekážok, pretože vlákno 1 (horné vlákno) môže pokračovať (zelená šípka), akonáhle pozastavíme ďalšie vlákna (dole žltou farbou).

Stredná časť ukazuje voľnosť zámku. Aspoň vlákno 1 môže postupovať, zatiaľ čo ostatní môžu hladovať (červená šípka).

Posledná časť ukazuje voľnosť čakania. Tu zaručujeme, že vlákno 1 môže pokračovať (zelená šípka) po určitej dobe hladovania (červené šípky).

4. Neblokujúce primitívne látky

V tejto časti sa pozrieme na tri základné operácie, ktoré nám pomáhajú budovať operácie bez zámkov na dátových štruktúrach.

4.1. Porovnajte a vymeňte

Jednou zo základných operácií používaných na zabránenie zablokovaniu je porovnať a vymeniť (CAS).

Myšlienka porovnania a výmeny je, že premenná sa aktualizuje, iba ak má stále rovnakú hodnotu ako v čase, keď sme načítali hodnotu premennej z hlavnej pamäte. CAS je atómová operácia, čo znamená, že načítanie a aktualizácia sú jednou operáciou:

Tu obidve vlákna načítajú hodnotu 3 z hlavnej pamäte. Vlákno 2 uspeje (zelená) a aktualizuje premennú na 8. Pretože prvý CAS podľa vlákna 1 očakáva, že hodnota bude stále 3, CAS zlyhá (červená). Preto vlákno 1 znova načíta hodnotu a druhý CAS je úspešný.

Dôležité tu je, že CAS nezíska zámok v dátovej štruktúre, ale vráti sa pravda ak bola aktualizácia úspešná, inak sa vráti nepravdivé.

Nasledujúci úryvok kódu načrtáva, ako funguje CAS:

hodnota volatile int; boolean cas (int expectValue, int newValue) {if (value == expectValue) {value = newValue; návrat pravdivý; } return false; }

Hodnotu s novou hodnotou aktualizujeme, iba ak má stále očakávanú hodnotu, inak sa vráti nepravdivé. Nasledujúci úryvok kódu ukazuje, ako možno nazvať CAS:

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

Snažíme sa aktualizovať našu hodnotu, kým operácia CAS nebude úspešná, to znamená, že sa vráti pravda.

Je však možné, že sa nitka zasekne hladom. To sa môže stať, ak iné vlákna vykonávajú CAS na rovnakej premennej v rovnakom čase, takže operácia nebude nikdy úspešná pre konkrétne vlákno (alebo bude trvať neúmerne dlho, kým bude úspešná). Napriek tomu, ak porovnať a vymeniť zlyhá, vieme, že sa podarilo uspieť inému vláknu, a tým zabezpečujeme aj globálny pokrok, ktorý sa vyžaduje pre slobodu zámku.

Je dôležité si uvedomiť, že hardvér by mal podporovať porovnať a vymeniť, aby sa stala skutočne atómovou operáciou bez použitia blokovania.

Java poskytuje implementáciu porovnať a vymeniť v triede slnko.misc.nebezpečný. Vo väčšine prípadov by sme však nemali používať túto triedu priamo, ale skôr atómové premenné.

Ďalej porovnať a vymeniť nezabráni problémom A-B-A. Na to sa pozrieme v nasledujúcej časti.

4.2. Load-Link / Store-Conditional

Alternatíva k porovnať a vymeniť je load-link / store-conditional. Najprv sa vráťme porovnať a vymeniť. Ako sme už videli predtým, CAS aktualizuje hodnotu, iba ak je hodnota v hlavnej pamäti stále taká, akú očakávame.

CAS však uspeje aj vtedy, ak sa hodnota zmenila, a medzitým sa zmenila späť na svoju predchádzajúcu hodnotu.

Túto situáciu ilustruje nasledujúci obrázok:

Vlákno 1 aj vlákno 2 čítajú hodnotu premennej, ktorá je 3. Potom vlákno 2 vykoná CAS, ktoré úspešne nastaví premennú na 8. Potom znovu vlákno 2 vykoná CAS, aby premennú nastavilo späť na 3, ktorý uspeje tiež. Nakoniec Thread 1 vykoná CAS, očakávajúc hodnotu 3, a uspeje tiež, aj keď hodnota našej premennej bola medzi nimi dvakrát upravená.

Toto sa nazýva problém A-B-A. Toto správanie nemusí byť problémom, samozrejme, v závislosti od prípadu použitia. Pre ostatných to však nemusí byť žiaduce. Java poskytuje implementáciu load-link / store-conditional s AtomicStampedReference trieda.

4.3. Načítať a pridať

Ďalšou alternatívou je načítať a pridať. Táto operácia zvýši premennú v hlavnej pamäti o danú hodnotu. Opäť je dôležité, že operácia sa deje atómovo, čo znamená, že žiadne iné vlákno nemôže rušiť.

Java poskytuje implementáciu načítať a pridať v jeho atómových triedach. Príklady sú AtomicInteger.incrementAndGet (), ktorá zvyšuje hodnotu a vracia novú hodnotu; a AtomicInteger.getAndIncrement (), ktorá vráti starú hodnotu a potom ju zvýši.

5. Prístup k prepojenému frontu z viacerých vlákien

Aby sme lepšie pochopili problém dvoch (alebo viacerých) vlákien, ktoré pristupujú do fronty súčasne, pozrime sa na prepojenú frontu a dve vlákna, ktoré sa snažia súčasne pridať prvok.

Poradie, na ktoré sa pozrieme, je dvojito prepojený rad FIFO, do ktorého pridávame nové prvky za posledný prvok (L) a premennú chvost poukazuje na tento posledný prvok:

Ak chcete pridať nový prvok, musia vlákna vykonať tri kroky: 1) vytvoriť nové prvky (N a M), pričom ukazovateľ na nasledujúci prvok je nastavený na nulový; 2) majú odkaz na predchádzajúci prvok bod L a odkaz na ďalší prvok L bod N (M). 3) Maj chvost ukážte na N (M):

Čo sa môže pokaziť, ak tieto kroky vykonajú obe vlákna súčasne? Ak sa kroky na vyššie uvedenom obrázku vykonávajú v poradí ABCD alebo ACBD, L, rovnako ako chvost, ukáže na M. N. zostane odpojený od poradia.

Ak sa kroky vykonajú v poradí ACDB, chvost bude ukazovať na N, zatiaľ čo L bude ukazovať na M, čo spôsobí nekonzistenciu vo fronte:

Jedným zo spôsobov riešenia tohto problému je samozrejme to, aby jedno vlákno získalo zámok vo fronte. Riešenie, na ktoré sa pozrieme v nasledujúcej kapitole, vyrieši problém pomocou operácie bez uzamknutia pomocou operácie CAS, ktorú sme videli už skôr.

6. Neblokujúci front v prostredí Java

Pozrime sa na základný rad bez uzamknutia v Jave. Najprv sa pozrime na členov triedy a konštruktor:

verejná trieda NonBlockingQueue {private final AtomicReference hlava, chvost; súkromná konečná veľkosť AtomicInteger; public NonBlockingQueue () {head = new AtomicReference (null); tail = new AtomicReference (null); size = new AtomicInteger (); size.set (0); }}

Dôležitou súčasťou je deklarácia odkazov na hlavu a chvost ako Atómová referencias, ktorá zaisťuje, že každá aktualizácia týchto odkazov je atómová operácia. Tento dátový typ v Jave implementuje potrebné porovnať a vymeniť prevádzka.

Ďalej sa pozrime na implementáciu triedy Node:

privátna trieda Uzol {súkromná volatilná hodnota T; privátny volatilný uzol ďalej; private volatile Uzol predchádzajúci; public Node (hodnota T) {this.value = hodnota; this.next = null; } // zakladatelia a zakladatelia}

Tu je dôležitou časťou deklarovať odkazy na predchádzajúci a nasledujúci uzol ako prchavý. To zaisťuje, že tieto odkazy aktualizujeme vždy v hlavnej pamäti (teda sú priamo viditeľné pre všetky vlákna). To isté pre skutočnú hodnotu uzla.

6.1. Bez zámkov pridať

Naše bez zámkov pridať operácia zabezpečí, že pridáme nový prvok na koniec a nebude odpojený od frontu, aj keď chce viac vlákien súčasne pridať nový prvok:

public void add (T element) {if (element == null) {throw new NullPointerException (); } Uzol uzla = nový Uzol (prvok); Uzol currentTail; do {currentTail = tail.get (); node.setPrevious (currentTail); } while (! tail.compareAndSet (currentTail, node)); if (node.previous! = null) {node.previous.next = uzol; } head.compareAndSet (null, node); // na vloženie prvého prvku size.incrementAndGet (); }

Podstatnou časťou, ktorej je potrebné venovať pozornosť, je zvýraznená čiara. Pokúšame sa pridať nový uzol do frontu, kým sa operácii CAS nepodarí aktualizovať chvost, ktorý musí byť stále ten istý chvost, ku ktorému sme pripojili nový uzol.

6.2. Bez zámkov dostať

Podobne ako pri operácii pridania, aj pri operácii bez uzamknutia sa zaistí, že vrátime posledný prvok a posunieme chvost do aktuálnej polohy:

public T get () {if (head.get () == null) {throw new NoSuchElementException (); } Uzol currentHead; Uzol nextNode; do {currentHead = head.get (); nextNode = currentHead.getNext (); } while (! head.compareAndSet (currentHead, nextNode)); size.decrementAndGet (); return currentHead.getValue (); }

Podstatnou časťou, ktorej je potrebné venovať pozornosť, je opäť zvýraznená čiara. Operácia CAS zaisťuje, že aktuálnu hlavicu presunieme, iba ak medzitým nebol odstránený žiadny iný uzol.

Java už poskytuje implementáciu neblokujúceho frontu, ConcurrentLinkedQueue. Je to implementácia frontu bez uzamknutia od M. Michaela a L. Scotta opísaného v tomto dokumente. Zaujímavá vedľajšia poznámka je, že v dokumentácii Java sa uvádza, že je to bez čakania frontu, kde to vlastne je bez zámkov. Dokumentácia k Java 8 správne volá implementáciu bez zámkov.

7. Fronty bez čakania

Ako sme videli, vyššie uvedená implementácia je bez zámkovvšak nie bez čakania. The zatiaľ čo slučky v oboch pridať a dostať Metóda môže potenciálne dlho (alebo hoci nepravdepodobne navždy) cyklovať, ak existuje veľa vlákien prístupných do nášho frontu.

Ako môžeme dosiahnuť slobodu čakania? Implementácia algoritmov bez čakania je vo všeobecnosti dosť ošemetná. Zainteresovaného čitateľa odkazujeme na tento dokument, ktorý podrobne popisuje frontu bez čakania. V tomto článku sa pozrime na základnú myšlienku, ako môžeme pristupovať k čakacej implementácii frontu.

Fronta bez čakania vyžaduje, aby každé vlákno zaručene napredovalo (po konečnom počte krokov). Inými slovami, zatiaľ čo slučky v našich metódach pridania a získania musia byť po určitom počte krokov úspešné.

Aby sme to dosiahli, každému vláknu priradíme pomocné vlákno. Ak sa pomocnému vláknu podarí pridať prvok do poradia, pomôže druhému vláknu vložiť jeho prvok pred vložením iného prvku.

Pretože pomocné vlákno má samotného pomocníka a v celom zozname vlákien má každé vlákno pomocníka, môžeme zaručiť, že sa vlákno podarí vložiť najneskôr po každom vložení. Nasledujúci obrázok ilustruje myšlienku:

Veci sa samozrejme komplikujú, keď môžeme vlákna pridávať alebo odstraňovať dynamicky.

8. Záver

V tomto článku sme videli základy neblokujúcich dátových štruktúr. Vysvetlili sme rôzne úrovne a základné operácie ako porovnať a vymeniť.

Potom sme sa pozreli na základnú implementáciu a bez zámkov rad v Jave. Na záver sme načrtli myšlienku, ako to dosiahnuť sloboda čakania.

Celý zdrojový kód pre všetky príklady v tomto článku je k dispozícii na GitHub.


$config[zx-auto] not found$config[zx-overlay] not found