如果此类型的hashtable cound被定义为无锁？

Question

据我理解

block is there are =1 task could progress if there are N tasks concurrent running 
and one enter the critical area(enter the critical area one).

lock-free is there are >=1 tasks could progress if there are N tasks concurrent 
running and one enter the critical area.

wait-free is there are N tasks could progress if there are N tasks concurrent 
running and one enter the critical area(maybe it shouldn't be called `critical area`).

我的问题是：

如果一个哈希表有N个桶，并且每个桶都有一个锁，那么在任何时候，都应该有>=1任务正在进行。这种类型的哈希表可以定义为无锁的吗？

bucket
+-------------+      +-------+      +-------+
| head | lock | ---> | entry | ---> | entry | ---> ...
+-------------+      +-------+      +-------+

Answer 1

如果一个哈希表有N个桶，并且每个桶都有一个锁，那么在任何时候，都应该有>=1任务正在进行。这种类型的哈希表可以定义为无锁的吗？

不是的。“每个人都有一个锁”意味着潜在的阻塞。作为对“无锁”的测试，请考虑挂起的线程是否会阻止另一个线程在挂起的整个时间内取得进展。如果是的话，那就不是没有锁的情况了。

在无锁编程中，您使用类似于原子操作的东西--通常是在更新失败的情况下--这样，试图取得进展的线程可能不得不重新尝试，但每次都有一个新的竞赛条件来查看它们是否进展；它们有一个真正的机会。

自旋锁

(我在评论中提到了一些细节，但这有点笨拙。)

“自旋锁”对不同的人意味着不同的东西。

历史上，有些人称互斥锁或读写锁为自旋锁，如果它至少跨越几次(十万/千次)，试图在加入该锁的OS队列之前原子地获取该锁(因此，如果持有锁的线程运行很长时间，它就不会继续消耗CPU )。

微软在http://msdn.microsoft.com/en-us/library/ms894034.aspx以不同的方式使用它：

只有持有自旋锁的线程才能使用该资源，直到锁被释放为止。自旋锁阻止其他线程访问资源。在等待自旋锁释放时，另一个线程可以启动一个试图获取自旋锁并继续循环的循环，直到持有该锁的线程释放自旋锁为止。

因此，在这种情况下，他们认为一个自旋锁类似于我上面描述的用法，但没有考虑回到事件驱动的队列上，以避免消耗CPU时间。

无锁原子操作往往也在旋转--区别在于它们已经在旋转停止时完成了它们的工作，而不是关闭竞争线程以允许它们开始工作(即使锁定线程以某种方式被挂起或延迟，这些竞争线程也无法继续工作)。

Answer 2

我对无锁的理解是：

有多个任务正在运行并发性，每个任务都可以访问共享数据，而不会阻碍其他任务的进行。因此，如果挂起单个线程，它将永远不会阻止其他线程取得进展。

所以(我想)如果你使用任何锁，你的代码就不是免费的。您实际上使用锁的确切原因是多个线程可能尝试并发访问共享数据，因此这个单一的锁可能会被争用并序列化访问；显然，这意味着您的代码不是没有锁的。您在存储桶中使用的锁可能是一个mutex (操作系统管理队列并在获得锁时提供事件通知)或一个繁忙的循环(其中CPU在试图单独获取锁的应用程序空间中旋转)，但两者都不是没有锁的。

对back-off使用一些技术是没有锁的，如果满足以下条件：Also if you suspend a single thread, it will never prevent other threads from making progress.。

在您的哈希表中，多个线程可以取得进展，但尽管如此，在对同一桶中的元素进行操作时，线程还是会彼此阻塞。在存储桶的链接列表中，您可以使用细粒度的锁--允许更多的线程处理列表中的元素--但即使这样也不是真正的免费锁定。

编辑

无锁和无等待之间的区别( C++ Concurrency in action书中的定义)：

无锁:要使数据结构限定为无锁，必须有多个线程能够同时访问数据结构。它们不必执行相同的操作；无锁队列可能允许一个线程推送，另一个线程弹出，但如果两个线程试图同时推送新项，则会中断。不仅如此，如果一个访问数据结构的线程在运行中途被调度程序挂起，其他线程仍必须能够完成它们的操作，而无需等待挂起的线程。

在数据结构上使用比较/交换操作的算法通常都有循环，具有这种循环的无锁算法可能导致一个线程受到饥饿。如果另一个线程以“错误”的时间执行操作，则另一个线程可能会取得进展，而第一个线程必须不断地重试其操作。避免此问题的数据结构是无等待的，也是无锁的。

无等待:无等待数据结构是一种无锁的数据结构，每个访问该数据结构的线程都可以在一定数量的步骤内完成其操作。因此，由于与其他线程的冲突而涉及无限重试次数的算法并不是没有等待的。

有了这些定义，我认为我的描述就像锁定自由;)。但是对于你的哈希图，我的投票是基于锁的代码。在这本书中，作者还实现了这样的哈希表，并将其插入到他的书的lock-based data structures section中。