Jak zaimplementować listę pominięć bez blokady

Muszę zaimplementować listę pominięć bez blokady. Szukałem Papierów. Niestety wszystko, co znalazłem, to wolne od blokad pojedyncze listy połączone (w wielu smakach). Jak jednak zaimplementować listę pominięć bez blokady?

Author: Gabe, 2010-08-13
Source

2 answers

Lista przeskoków bez blokady jest opisana w książce The Art of Multiprocessor Programmingoraz w raporcie technicznym Practical lock-freedom, która jest oparta na pracy doktorskiej na ten temat. Dyskusja na temat listy przeskoków rozpoczyna się na stronie 53. Przykładowa implementacja, oparta na tych źródłach, znajduje się w tym projekcie google code .

W tzw. pytaniach Skip znajdują się powiązane dyskusje, linki do literatury i implementacji (niekoniecznie bez blokady) Lista kontra drzewo binarne i Pomiń listy - używałeś ich kiedyś?.

 15
Author: ire_and_curses,
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/doraprojects.net/template/agent.layouts/content.php on line 54
2017-05-23 12:17:47

Ten artykuł prezentuje listę pominięć bez blokady i bez oczekiwania. Jest to proste do wdrożenia-zaimplementowałem to kilka tygodni temu w ramach Intel Threading Challenge 2010 (patrz Zakładka SkipList w połowie strony.)

Java zawiera implementację równoległej listy przeskoków, java.util./ align = "left" / ConcurrentSkipListMap .

 4
Author: mdma,
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/doraprojects.net/template/agent.layouts/content.php on line 54
2010-08-13 17:07:38