无锁式滑雪者 [英] lock-free skiplist with rank operation

问题描述

有人知道任何无锁的滑雪者运动和/或研究论文支持排名操作（即找到第k个元素）？或者，任何人都知道为什么这样的操作永远不能工作？

Is anyone aware of any lock-free skiplist implimentations and/or research papers that support the rank operation (i.e. find kth element)? Alternatively, is anyone aware of a fundamental reason why such an operation could never work?

奖励积分：

不假定垃圾收集的一个实现。这是我的经验相当一些研究论文忽略内存管理。

An implimentation that does not assume garbage collection. It has been my experience quite a few research papers ignore memory management.

支持：

有关如何在常规skiplist中执行排名操作的说明：William Pugh的A Skip List Cookbook

For a description of how the rank operation may be done in a regular skiplist: "A Skip List Cookbook" by William Pugh

免费滑雪者描述：Keir Fraser提供的实用锁定自由

For one of the better lock-free skiplist descriptions: "Practical lock-freedom" by Keir Fraser

更好的无锁滑雪装置之一： http://www.1024cores.net/home/parallel-computing/concurrent-skip-list

One of the better lock-free skiplist implimentations: http://www.1024cores.net/home/parallel-computing/concurrent-skip-list

推荐答案

与键，值和是在滑雪者中的元素的局部属性，并且不受具有其他元素的操作的影响，元素的 rank （即其在列表中的位置）是随着元素的插入和移除而改变的属性低等级。因此，对于并发的滑雪者，元素的等级是非常短暂的，因为它可以在任何时刻通过插入或降低较低等级元素的同时运行操作来改变。

Unlike key, value and level, which are local properties of an element in a skiplist and are not affected by operations with other elements, rank of an element, i.e. its position in the list, is a property that changes with insertion and removal of elements with lower rank. Therefore, for a concurrent skiplist, rank of an element is very ephemeral because it may be changed in any moment by a concurrently running operation that inserts or delets a lower rank element.

例如，假设您通过级别1列表对 k -th元素进行线性搜索。目前您已执行 k 步骤，并发修改可能会添加或删除任何数量的先前元素，因此您刚才找到的元素的当前排名事实上是未知的。此外，当线程正在执行 k 正向迭代时，可以在其当前位置和 k 的元素之间进行并发更改。因此，当搜索开始时，搜索结果不是具有当前排名 k 的元素，也不是具有排序 k 的元素。它只是一些随机元素！

For example, suppose you do linear search of k-th element through the level 1 list. At the moment you did k steps, concurrent modifications might add or remove any number of prior elements, so the current rank of the element you just find is in fact unknown. Moreover, while the thread is performing the k forward iterations, concurrent changes can be done between its current position and the element that was k-th when it started the search. So what the search ends up with is neither the element with the current rank of k nor the one that has the rank of k when the search started. It's just some random element!

简单来说，对于并发列表，元素的rank是一个定义不明确的概念，按rank搜索是一个不明确的操作。这是它永远不能工作的根本原因，以及为什么实施者不应该烦恼提供这样的操作。

To say it short, for concurrent list, rank of an element is an ill-defined concept and searching by rank is an ill-defined operation. This is the fundamental reason why it could never work, and why implementers should never bother with providing such operation.

这篇关于无锁式滑雪者的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！