以下算法是无锁的吗？

Is the following algorithm lock-free?

以我的理解，如果某个线程总是取得进展，则算法是无锁的。

下面的例子（使用锁）不满足这个条件吗：

线程 1：对临界区使用 lock1
线程 2：对临界区使用 lock1
线程3：一些调用独立于lock1和其他两个线程一般

你所描述的肯定不是 "lock-free" 任何有意义的。线程 1 和 2 依赖于相同的共享资源（一个临界区，由 "lock1" 强制执行），因此如果其中一个获取该锁然后被挂起，那么另一个线程将死锁等待它。

当然，线程 3 将继续有增无减，但线程 A、B 和 C（即，与您的程序无关的线程也会如此）。从整个算法来看，这似乎是无关紧要的，它可能由所有三个线程组成。

本质上，您对 "lock-free" 的定义存在的问题是它不够精确。你说一个算法是lock-free"if some thread always makes progress"，但是你没有从整体上看算法

线程 3 是微不足道的 lock-free（因为它自己取得进展，没有任何其他线程的帮助），但您的整体算法不是。

评估算法是否 lock-free 的更好方法是问自己：如果一个线程被挂起，这是否会阻止其他线程作为一个整体 取得进展？在这种情况下，是的。如果线程 1 或线程 2 获取锁然后被挂起，这将阻止其他线程执行，并且可能这些其他线程正在执行对您的算法很重要的工作。