Ano máte pravdu, je to akademická diskuze a taky je už mimo původní téma. Ale lock-free algoritmy jsou hodně zajimavé, tak snad není tato debata úplně zbytečná. Napsat lock-free algoritmus je opravdu težké, snadno se udělá neodhalitelná chyba v úplně elementární věci - proto jsem s tím přestal a používám výhradně hotové věci.
A také máte pravdu v tom přístupu na next v kroku 2, to řeší SEHem i InterlockedXxxSList (i když každá verze OS trochu jinak).
Ale stejně mi něco nesedí. Konkrétně krok 5 v odebrání ze seznamu. Pokud to dobře chápu, tak má řešit ABA problém při přidání nových záznamů do seznamu. Ale co když jen nahrazeny nebo smazány?
Simulujme ABA problém - tzn. znovupoužití stejné hodnoty pointeru.
Průběh 1 - nečekané přidání položek z jiného threadu
1. Výchozí stav: a b c d e f
2. dokončení kroku 2: cur_top=a, cur_next=b
3. pak je thread přerušen jiným, který změní seznam (pop a, push z, push y, push x, push a)
4. Aktuální stav: a x y z b c d e f
5. thread pokračuje ve vykonávání kroku 3, top==cur_top, CAS se provede
6. Aktuální stav: b c d e f
7. vykoná se krok 5: cur_next==b a cur_top->next==x (celá řada je x y z b c d e f), tedy jsou různé a já musím přidat prvky navíc.
8. vím, že mám přidat x, y, z, protože se zastavím na b.
Tohle je podle mě ok.
Průběh 2 - nečekané smazání položek z jiného threadu
1. Výchozí stav: a b c d e f
2. dokončení kroku 2: cur_top=a, cur_next=b
3. pak je thread přerušen jiným, který změní seznam (pop a, pop b, pop c, push a)
4. Aktuální stav: a e f
5. thread pokračuje ve vykonávání kroku 3, top==cur_top, CAS se provede
6. Aktuální stav: e f
7. vykoná se krok 5: cur_next==b a cur_top->next==e (celá řada je e f)
8. A co teď? Ty hodnoty jsou různé, ale v seznamu žádné b není. Správně bych neměl přidat žádnou.
Tohle podle mě není ok.
Průběh 3 - nečekaná změna položek z jiného threadu
1. Výchozí stav: a b c d e f
2. dokončení kroku 2: cur_top=a, cur_next=b
3. pak je thread přerušen jiným, který změní seznam (pop a, pop b, push x, push a)
4. Aktuální stav: a x c d e f
5. thread pokračuje ve vykonávání kroku 3, top==cur_top, CAS se provede
6. Aktuální stav: x c d e f
7. vykoná se krok 5: cur_next!=b a cur_top->next==x (celá řada je x c d e f)
8. A co teď? Ty hodnoty jsou různé, ale v seznamu žádné b není. Správně bych neměl přidat žádnou.
Tohle podle mě taky není ok.
Intenzivně se zabývám programováním zejména v jazyce C++. Vyvíjím vlastní knihovny, vzory, techniky, používám šablony, to vše proto, aby se mi usnadnil život při návrhu aplikací. Pracoval jsem jako programátor ve společnosti Seznam.cz. Nyní jsem se usadil v jednom startupu, kde vyvíjím serverové komponenty a informační systémy v C++
Přečteno 48 580×
Přečteno 22 616×
Přečteno 21 789×
Přečteno 18 079×
Přečteno 16 654×