Как реализовать список пропуска без блокировки
Мне нужно реализовать список пропусков без блокировки. Я пытался искать документы. К сожалению, все, что я нашел, было свободными от единственных ссылок списками (во многих вариантах). Однако как реализовать список пропуска без блокировки?
2 ответа
Списки пропусков без блокировки описаны в книге Искусство многопроцессорного программирования , а также в технических отчет Практическая свобода от блокировок , основанный на докторской диссертации по данной теме. Обсуждение списков пропуска начинается на странице 53. Пример реализации, основанный на этих источниках, включен в этот проект кода Google .
В вопросах SO Список пропуска и двоичное дерево и Списки пропуска - когда-нибудь их использовали? есть связанные обсуждения, ссылки на литературу и реализации (не обязательно без блокировки) ].
В этой статье представлен список пропусков без блокировки и без ожидания. Это несложно реализовать - я реализовал это несколько недель назад как часть Intel Threading Challenge 2010 (см. Вкладку SkipList на полпути вниз).
Java включает реализацию списка одновременных пропусков, java.util.concurrent.ConcurrentSkipListMap .