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

Question

这纯粹只是为了兴趣问题,欢迎任何类型的问题.

那么是否可以在没有任何锁的情况下创建线程安全的集合？通过锁我的意思是任何线程同步机制,包括Mutex,Semaphore,甚至Interlocked,所有这些机制.是否可以在用户级别,而无需调用系统功能？好的,可能实施效果不好,我对理论上的可能性很感兴趣.如果不是最低限度的手段是什么？

编辑:为什么不可变集合不起作用.

这个类Stack包含Add返回另一个Stack的方法.

现在这是程序:

Stack stack = new ...;

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

这个表达式stack = stack.Add(element)不是原子的,你可以从其他线程覆盖新的堆栈.

谢谢,安德烈

Answer 1

甚至大师软件开发人员似乎也对构成锁的内容存在误解.

人们必须区分原子操作和锁定.比较和交换等原子操作执行操作(否则需要两条或更多条指令)作为单个不间断指令.锁是从原子操作构建的,但是它们可能导致线程忙等待或睡眠,直到锁被解锁.

在大多数情况下,如果您设法使用原子操作实现并行算法而不诉诸锁定,您会发现它会快几个数量级.这就是为什么对无等待和无锁算法非常感兴趣的原因.

在实施各种无等待数据结构方面已经进行了大量研究.虽然代码往往很短,但由于出现了微妙的竞争条件,很难证明它们真的有用.调试也是一场噩梦.然而,已经做了很多工作,你可以找到无等待/无锁的哈希映射,队列(迈克尔斯科特的无锁队列),堆栈,列表,树,列表继续.如果你很幸运,你也会发现一些开源实现.

只需google'锁定我的数据结构',看看你得到了什么.

有关这一有趣主题的进一步阅读,请参阅Maurice Herlihy 的"多处理器编程艺术".

Answer 2

是的,不变的收藏品!:)