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