无锁的定义

Question

存在三种不同类型的“无锁”算法。 Concurrency in Action中给出的定义是：

无障碍：如果所有其他线程都暂停，则任何给定的线程将在有限的步骤中完成其操作。
Lock-Free:如果多个线程在操作一个数据结构，那么经过一定数量的步骤后，其中一个将完成其操作。
Wait-Free:每个线程都在一个数据结构上运行将在有限的步骤中完成其操作，即使其他线程也在数据结构上操作。

Herb Sutter 在他的演讲中说 Lock-Free Programming:

Informally, "lock-free" ≈ "doesn't use mutexes" == any of these.

我不明白为什么基于锁的算法不能落入上面给出的无锁定义。这是一个简单的基于锁的程序：

#include <iostream>
#include <mutex>
#include <thread>

std::mutex x_mut;

void print(int& x) {
    std::lock_guard<std::mutex> lk(x_mut);
    std::cout << x;
}

void add(int& x, int y) {
    std::lock_guard<std::mutex> lk(x_mut);
    x += y;
}

int main() {

    int i = 3;

    std::thread thread1{print, std::ref(i)};

    std::thread thread2(add, std::ref(i), 4);

    thread1.join();

    thread2.join();

}

如果这两个线程都在运行，那么在有限数量的步骤之后，其中一个必须完成。为什么我的程序不满足“无锁”的定义？

Answer 1

我会小心说“有界”而不定义什么。

规范的 lock-free 原语 - CAS 循环没有任何界限，如果竞争激烈，线程可能会反复倒霉并永远等待，这是允许的。 lock-free 算法的 定义属性总是有 system-wide 进展 。在任何时候，某些线程都会取得进展。

在每个时间点对每个线程的某些进度的更强保证称为 wait-free。

换句话说，lock-free保证行为不当的线程不会对所有其他线程造成致命影响，wait-free不会对任何线程造成致命影响 个线程。

If both of these threads are operating, then after a bounded number of steps, one of them must complete. Why does my program not satisfy the definition of "Lock-free"?

因为必须考虑（不公平）调度程序。*如果持有锁的线程进入睡眠状态，其他线程将无法取得任何进展 - > not-lock-free 并且当然没有界限。 lock-free 编程不会发生这种情况，资源始终可用，不幸的是，一个线程的调度只会使其他线程的操作完成得更快，而不是更慢。

* 特别是，任何线程的暂停时间不受频率或持续时间限制。如果是的话，根据定义，任何算法都将是 wait-free（具有一些巨大的常数）。

Answer 2

您在 Concurrency in Action 中的引述被断章取义了。

其实书上实际说的是：

7.1 Definitions and consequences

Algorithms and data structures that use mutexes, condition variables, and futures to synchronize the data are called blocking data structures and algorithms.

Data structures and algorithms that don’t use blocking library functions are said to be nonblocking. Not all these data structures are lock-free ...

然后进一步分解非阻塞算法为Obstruction-Free,Lock-Free和Wait-Free.

所以Lock-Free算法是

一个非阻塞算法（它不像互斥锁那样使用锁）和
它能够在有限的步数中至少在一个线程中取得进展。

所以 Herb Sutter 和 Anthony Williams 都是正确的。

无锁的定义

The definition of lock-free

c++

multithreading

computer-science

lock-free

lockless