Predpokladajme, že mám triedený, jednotlivo prepojený zoznam N celé čísla neobsahujúce žiadne duplikáty a k vlákna (kde k << N), pričom každý sa pokúša vložiť do zoznamu celé číslo (väčšie ako hlavný uzol).
Je možné synchronizovať vloženia do takéhoto zoznamu tak, aby:
- Niť môže zablokovať prístup iba k jeho (okamžite) predchádzajúcemu uzlu
(Žiadne uzamknutie "celého zoznamu") - Môžu sa používať najviac O (k) mutexy a premenné stavu
- Nie je možné predvídať / prerušiť
?
odpovede:
3 pre odpoveď č. 1Po prvé, ak vkladanie do kolekcie nie je nič iné ako veľmi zriedkavá úloha, potom prepojené zoznamy nie sú pre toto skvelé riešenie - pretože nájdenie bodu vkladania je O(N) dokonca aj pre triedený zoznam, a preto skončí škálovanie.
Ak to ešte musíte urobiť, je možné vykonať vloženie (na rozdiel od vymazania) do triedeného zoznamu ako operácia bez zámku, s určitou starostlivosťou:
- Nájsť bod vkladania,
cur - Vytvoriť nový uzol (priradiť predchádzajúce / nasledujúce prepojenie na
cur/cur->next) - Atómová op:
compare_and_swap(cur->next, new, new->next);
Ak zlyhá:if (new->value == next->value) return; // someone beat us to it
else:cur = cur->nexta opakovanie tanca (zoznam je zoradený, niekto vložený pred nami)
Tj. Výsledok pokusu prepojiť nový uzol je buď to, že sa nám podarí, alebo že nás niekto porazil vložením toho istého uzla (v tom prípade sme v poriadku - už je tam), alebo niekto vložil do medzery ( tj existujúci bol N, N+3, pokúsili sme sa N+1, niekto iný uspel N+2), vtedy opäť skúsme, kým sa nám nepodarí nájsť "náš" uzol vykonaný niekým iným.
Je to oveľa ťažšie synchronizovať odstránenie, vyhľadávanie RCU (Read-Copy-Update) pre to.