有三种不同类型的"无锁";算法。操作中的并发性给出的定义是:
- 落下:如果所有其他线程都暂停，则任何给定的线程将在有限的步骤中完成其操作。
- 无锁:如果多个线程正在操作一个数据结构，那么经过一定数量的步骤后，其中一个将完成它的操作。
- 无等待:对数据结构进行操作的每个线程将在有限的步骤中完成其操作，即使其他线程也在操作数据结构。
Herb Sutter在他的演讲中说:
非正式地,"lock-free"≈不使用互斥体"==以上任意一个
我不明白为什么基于锁的算法不能落入上面给出的无锁定义。下面是一个简单的基于锁的程序:
#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();
}
如果这两个线程都在运行，那么在一定数量的步骤之后，其中一个必须完成。为什么我的程序不满足"无锁"的定义?
我在写" bounded">
规范的无锁原语- CAS循环没有给出任何界限，如果存在严重的争用，线程可能会反复不幸并永远等待，这是允许的。无锁算法的定义属性是总是存在系统范围的进度． 在任何时间点，一些线程将取得进展。
为每个线程在每个时间点提供更强的进度保证称为无等待。
换句话说，无锁保证了一个行为不端的线程不会致命地影响所有其他线程，无等待不会致命地影响任何线程。
如果这两个线程都在运行，那么在一定数量的步骤之后，其中一个必须完成。为什么我的程序不满足"无锁"的定义?
因为必须考虑(不公平)调度程序如果持有锁的线程处于睡眠状态，那么其他线程将无法取得任何进展->不是无锁的，当然也没有边界。这种情况不会发生在无锁编程中，资源总是可用的，一个线程的调度可能会使其他线程的操作完成得更快，而不是更慢。
*特别是在任何线程的暂停时间不受频率或持续时间限制的情况下。如果是的话，任何算法都是无等待的(有一些巨大的常数)。
你引用的Concurrency in Action是断义的。
事实上，书中真正说的是:
7.1定义和结果使用互斥锁、条件变量、和期货同步数据称为阻塞数据结构和算法。
不使用阻塞库的数据结构和算法函数被称为非阻塞． 不是所有的数据结构是锁定…
然后进一步分解非阻塞无障碍,锁定和无等待.So aLock-Free算法是
- 非阻塞算法(它不使用像互斥锁那样的锁)和
- 它能够在有限的步骤中至少在一个线程中取得进展。
所以Herb Sutter和Anthony Williams都是正确的。