Синхронизация вставки односвязных списков

Question

Предположим, у меня есть отсортированный односвязный список из N целых чисел, не содержащих дубликатов, и k потоков (где k << <em>N ), каждый пытается вставить какое-то целое число (больше, чем головной узел) в список.

Можно ли синхронизировать вставки в такой список, что:

• Поток может блокировать доступ только к своему (непосредственно) предыдущему узлу
  (Не блокировать «весь список»)
• Может использоваться не более O (k) мьютексов и условных переменных
• Нет прерываний / прерываний не может быть

Answer 1

Во-первых, если вставка в коллекцию - не очень редкая задача, то связанные списки не являются хорошим решением для этого - поскольку поиск точки вставки является операцией O(N), даже для отсортированного списка, и, следовательно, в конечном итоге плохо масштабируется.

Если вам все еще нужно это сделать, можно выполнить вставку (в отличие от удаления) в отсортированный список как операцию без блокировки, с некоторой осторожностью:

1. Найти точку вставки, cur
2. Создать новый узел (назначить предыдущую / следующую связь для cur / cur->next)
3. Атомный оператор: compare_and_swap(cur->next, new, new->next);
   Если не удалось: if (new->value == next->value) return; // someone beat us to it
   Остальное: cur = cur->next и повторите танец (список отсортирован, кто-то вставил перед нами)

т.е. Результатом попытки связать новый узел является либо то, что мы преуспели, либо что кто-то побил нас, чтобы вставить тот же самый узел (в этом случае мы в порядке - он уже там), или кто-то вставил в пробел (т.е. существующий было N, N+3, мы пытались N+1, кто-то другой преуспел N+2), и в этом случае мы повторяем попытку до тех пор, пока не добьемся успеха или не найдем наш узел, сделанный кем-то другим.

Гораздо сложнее синхронизировать удаление; ищите RCU (Read-Copy-Update) для этого.