Hlavní navigace

Názor ke článku SEH v Linuxu (C++) od petr - Ano máte pravdu, je to akademická diskuze a...

  • 6. 9. 2012 14:08

    petr (neregistrovaný)

    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.