There are three different types of "lock-free" algorithms. The definitions given in Concurrency in Action are:
- Obstruction-Free: If all other threads are paused, then any given thread will complete its operation in a bounded number of steps.
- Lock-Free: If multiple threads are operating on a data structure, then after a bounded number of steps one of them will complete its operation.
- Wait-Free: Every thread operating on a data structure will complete its operation in a bounded number of steps, even if other threads are also operating on the data structure.
Herb Sutter says in his talk Lock-Free Programming:
Informally, "lock-free" ≈ "doesn't use mutexes" == any of these.
I do not see why lock-based algorithms can't fall into the lock-free definition given above. Here is a simple lock-based program:
#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();
}
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"?
Your quote from Concurrency in Action is taken out of context.
In fact, what the book actually says is:
Then it proceeds to further break down nonblocking algorithms into Obstruction-Free, Lock-Free and Wait-Free.
So a Lock-Free algorithm is
So both Herb Sutter and Anthony Williams are correct.