无锁的定义

Question

存在三种不同类型的“无锁”算法。并发实践中给出的定义是：

\n

\n
1. 无阻碍：如果所有其他线程都暂停，则任何给定的\n线程都将在有限的步骤中完成其操作。
\n
2. 无锁：如果多个线程正在对一个数据结构进行操作，那么在有限数量的步骤之后，其中一个线程将完成其操作。
\n
3. 无等待：每个操作数据结构的线程都将在有限的步骤中完成其操作，即使其他线程也在操作该数据结构。
\n

\n

Herb Sutter 在他的演讲《无锁编程》中说道：

\n

\n

非正式地，“无锁”\xe2\x89\x88“不使用互斥体”==其中任何一个。

\n

\n

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

\n

#include <iostream>\n#include <mutex>\n#include <thread>\n\nstd::mutex x_mut;\n\nvoid print(int& x) {\n    std::lock_guard<std::mutex> lk(x_mut);\n    std::cout << x;\n}\n\nvoid add(int& x, int y) {\n    std::lock_guard<std::mutex> lk(x_mut);\n    x += y;\n}\n\nint main() {\n\n    int i = 3;\n\n    std::thread thread1{print, std::ref(i)};\n\n    std::thread thread2(add, std::ref(i), 4);\n\n    thread1.join();\n\n    thread2.join();\n\n}\n

\n

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

\n

Answer 1

您对《行动中的并发》的引用是断章取义的。

\n

事实上，这本书实际上说的是：

\n

\n

7.1 定义和后果

\n

使用互斥体、条件变量和 future 来同步数据的算法和数据结构称为阻塞数据结构和算法。

\n

不\xe2\x80\x99 不使用阻塞库\n函数的数据结构和算法被称为非阻塞。并非所有这些数据结构都是无锁的......

\n

\n

然后它进一步将非阻塞算法分解为无阻塞、无锁和无等待。

\n

所以无锁算法是

\n

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

\n

所以赫伯·萨特和安东尼·威廉姆斯都是正确的。

\n