代码之家 › 专栏 › 技术社区 › Andrey

是否可以创建没有锁的线程安全集合?

language-agnostic multithreading algorithm

Andrey · 技术社区 · 14 年前

那么,有没有可能在没有任何锁的情况下创建线程安全的集合呢?我所说的锁是指任何线程同步机制,包括互斥、信号量,甚至是互锁。是否可以在用户级,不调用系统函数?好吧,可能是执行不力,我感兴趣的是理论上的可能性。如果没有,最起码的方法是什么?

为什么不可变集合不起作用。

Stack Add 返回另一个堆栈。

下面是程序:

Stack stack = new ...;

ThreadedMethod()
{
   loop
   {
      //Do the loop
      stack = stack.Add(element);
   }
}

这个表达式 stack = stack.Add(element)

谢谢,

6 回复 | 直到 14 年前

Il-Bhima 14 年前

必须区分原子操作和锁。像compare和swap这样的原子操作将一个操作(否则需要两个或多个指令)作为单个不间断指令执行。锁是从原子操作构建的,但是它们会导致线程忙于等待或休眠,直到锁被解锁。

在实现各种无等待数据结构方面已经做了大量的研究。虽然代码往往很短,但由于出现了微妙的竞争条件,很难证明它们真的有效。调试也是一场噩梦。但是,已经做了很多工作,您可以找到无等待/无锁hashmaps、队列(michaelscott的无锁队列)、堆栈、列表、树等等。如果幸运的话,您还可以找到一些开源实现。

为了进一步阅读这个有趣的主题,从 The Art of Multiprocessor Programming 作者:莫里斯·赫利希。

Dimitris Andreou 14 年前

Craig Gidney Mihai 14 年前

Peterson's algorithm 或者更一般的 bakery algorithm

Cowan 14 年前

这真的取决于你如何定义这个术语(正如其他评论者所讨论的),但是是的,这是可能的 许多的 数据结构至少要以非阻塞的方式实现(不使用传统的互斥锁)。

如果你对这个话题感兴趣,我强烈建议你 the blog of Cliff Click --Cliff是Azul Systems的首席专家,他生产硬件+一个定制JVM来运行大规模并行的Java系统(想想大约1000个内核和数百GB的RAM区域),显然在这些类型的系统中,锁定可能是死亡(免责声明:不是Azul的员工或客户,只是他们工作的崇拜者)。

Click博士提出了一个著名的非阻塞哈希表,它基本上是一个使用原子CompareAndSwap操作的复杂(但相当出色)状态机。

有一篇由两部分组成的博客文章描述了这个算法( part one part two )以及在谷歌的演讲( slides , video )——特别是后者是一个精彩的开场白。我花了几次时间才弄明白——这很复杂,让我们面对现实吧!—但是如果你还活着(或者你比我聪明!)你会发现这很值得。

Uri 14 年前

我不这么认为。问题是,在某个时刻,您将需要一些互斥原语(可能在机器级别),例如原子测试和设置操作。否则,你总是可以设计一个竞赛条件。一旦有了测试和设置,就基本上有了锁。

这就是说,在指令集中没有任何支持的旧硬件中,可以禁用中断,从而防止另一个“进程”接管,但实际上是不断地将系统置于序列化模式,并在一段时间内强制某种程度的互斥。

sylvanaar 14 年前

推荐文章

SkyWalker · 在JavaScript中,合并日期-时间序列的有效算法是什么?

1 年前

root · 计数算法

1 年前

André Silveira · 使用循环将数组的每个槽递增1。数组的大小是传递给函数的参数

2 年前

danial · 如何在多个字符串的每个位置找到最频繁的字符

2 年前

Manny · 如何比较Perl中的字符串?

2 年前

Suhail Gupta · 在排序阵列中查找目标范围的时间复杂度-此解在最坏情况下是否为O(N)?

2 年前

Diret · 获取范围内每个数字的子倍数的算法

2 年前

Saif · 排序时python如何决定何时调用比较器?

2 年前

TryingToLearn · 我如何为通用遥控器构造一个类,该遥控器向连接到它的各种设备发送开/关命令?

2 年前

Sneha Sharma · 滑动窗口-在我的代码中找不到错误(非常基本的算法)

2 年前