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