Pytanie Przykład użycia AtomicStampedReference & AtomicMarkableReference


Szukam przykładu AtomicStampedReference & / lub AtomicMarkableReference, który może pomóc mi zrozumieć te klasy i ich funkcje. Nie mogę uzyskać żadnych przykładów jakościowych w Internecie.

Mogę myśleć o używaniu ich w procesie zbierania śmieci, ale dobry przykład pomoże mi je lepiej zrozumieć.


11
2017-12-17 06:31


pochodzenie




Odpowiedzi:


Praktyczne przykłady (skomplikowane)

Dla AtomicMarkableReference:

https://github.com/arunmoezhi/ConcurrentKaryST

Dla AtomicStampedReference

https://github.com/arunmoezhi/LockFreeBST

Prosty przykład:

W drzewie binarnym, jeśli chcesz zmienić element potomny węzła nadrzędnego atomically, następnie compareAndSwap na AtomicMarkableReference może być użyte.

W drzewie binarnym powiedzmy, że chcesz flagować węzeł atomowo. Następnie AtomicStampedReference może być użyte.

Powyższe skomplikowane implementacje rzeczywistych zastosowań używają tych dwóch typów klas.


10
2018-02-26 04:03



Nie mogę uwierzyć, że to pytanie i odpowiedź dostały tak mało głosów ... - Alex Salauyou
@arunmoezhi Dlaczego zwykle AtomicReference nie jest wystarczający w przykładzie z binaru? - gstackoverflow


S Kr Oto wyjaśnienie. Weź stos, który wygląda tak: góra -> A -> B -> C.
Weź dwa wątki, Th1 i Th2. Korzystają z porównania i zestawu bez blokowania (CAS) do operacji pop.
Th1: set return = A, next = B .., ale zostaje przeniesiony poza stan pracy
Th2:
 - pop A: return = A, next = B, CAS (A, B) .. więc teraz top = B
 - pop B: return = B, next = C, CAS (B, C) .. więc teraz top = C
 - wciśnij A (to samo, co wcześniej, gdy satysfakcjonowałeś ==, ponieważ powiedzmy, że było gdzieś zbuforowane): ... więc teraz góra jest A, a stos wygląda tak ... góra -> A -> C
Th1: z powrotem w akcji ... i wznawia .. CAS (A, B) ... to się uda !! Stack wygląda teraz tak ... góra -> B -> C .. ale .. ale B został już usunięty ze stosu przez wątek 2 i magicznie wraca! Zły.
Morał z historii: użyj AtomicStampedReference. AtomicMarkableReference jest szczególnym przypadkiem AtomicStampedReference.

Bonus: pomyśl o posortowanej połączonej liście i wielu wątkach nad nią pracujących. Spróbuj wstawić C w A -> B -> D -> E i wymyślić podobny problem ABA.


-1
2017-09-09 17:03