Безблокировочный скиплист с операцией ранга

Question

Кто-нибудь знает о каких-либо имплиментациях и / или исследовательских работах без пропусков без блокировки (т. Е. Найти элемент kth)? Или кто-нибудь знает фундаментальную причину, почему такая операция никогда не может работать?

Бонусные очки:

Имплиментация, которая не предполагает сборку мусора. По моему опыту, довольно много исследовательских работ игнорируют управление памятью.

Служба поддержки:

Для описания того, как операция ранга может быть сделана в обычном скиплисте: "Поваренная книга списка пропусков" Уильяма Пью

Для одного из лучших описаний скиплистов без блокировки: "Практическая свобода блокировки" Кейра Фрейзера

Один из лучших вариантов пропуска списка без блокировок: http://www.1024cores.net/home/parallel-computing/concurrent-skip-list

Answer 1

В отличие от ключа, значения и уровня, которые являются локальными свойствами элемента в списке пропусков и на которые не влияют операции с другими элементами, ранг элемента, то есть его положение в списке, является свойством, которое изменяется при вставке и удалении элементов. с более низким рангом. Следовательно, для параллельного списка пропусков ранг элемента является очень эфемерным, потому что он может быть изменен в любой момент одновременно выполняющейся операцией, которая вставляет или удаляет элемент более низкого ранга.

Например, предположим, что вы выполняете линейный поиск k-го элемента в списке уровня 1. В тот момент, когда вы выполнили k шагов, одновременные модификации могут добавить или удалить любое количество предыдущих элементов, поэтому текущий ранг найденного элемента фактически неизвестен. Более того, пока поток выполняет k прямых итераций, одновременные изменения могут быть сделаны между его текущей позицией и элементом, который был k- тым, когда он начал поиск. Таким образом, поиск заканчивается тем, что не является ни элементом с текущим рангом k, ни тем, который имеет ранг k, когда поиск начался. Это просто какой-то случайный элемент!

Короче говоря, для параллельного списка ранг элемента - это плохо определенная концепция, а поиск по рангу - плохо определенная операция. Это основная причина, по которой он никогда не может работать, и почему разработчики никогда не должны беспокоиться о предоставлении такой операции.