如何在不加锁的情况下解决多线程问题？

前几天微信群里有同学聊一个面试题，怎样在不加锁的情况下解决线程安全问题，你需要了解lock free和wait free这两个概念，在此之前我们先从最简单的有锁编程开始。

我们知道，多线程同时修改共享变量时会出现数据不一致的问题，比如多个线程同时对一个变量加1，假设count的初始值为0：

int count;


void add() {
    ++count;
}

如果只有一个线程调用add函数，那么什么问题都没有，但如果多个线程同时调用上述函数，比如10个线程都调用一遍，那么count值最后不一定等于0，原因在于对count加1的操作不是原子的。

所谓某个操作是原子的是指CPU要么执行该操作，要么不执行该操作，不存在中间状态，但上述对count加1的操作经过编译器处理后会生成几条对应的机器指令，所以该操作不是原子的。

那么怎样才能让其变成原子的呢？很简单，加一把锁。

int count;
mutex mtx; // 锁


void add() {
    mtx.lock();
    ++count;
    mtx.unlock();
};

现在我们用一把锁将对count的操作保护了起来，此时你可以将mtx.lock()以及mtx.unlock()中间的代码看成原子的，CPU要完全执行完对count的加1要么根本不会操作count，这样上述程序的运行结果就是我们想要的了。

这是怎样做到呢？这就要说到操作系统了，千万不要小瞧了上面的mutex这把锁，这把锁的背后相当复杂，因为这涉及到了操作系统。

假设现在有三个线程，各自运行在不同的CPU核心上，每个方框代表一个时间片：

T1时间片这三个线程都在调用add函数，线程A拿到锁，A可以继续向前推进，但B和C就没这么幸运了，此时操作系统将剥夺线程B和C继续持有CPU的权利，将其分配给其它具备执行条件的线程，这就是操作系统中所谓的挂起，注意，这个过程相当复杂，因为这涉及到用户态与内核态的切换以及线程的切换等等。

此时来到T2时间片，线程A继续向前推进，线程B和C则被按下暂停键。

T3时间片，然而就在线程A拿到锁运行时因为某些原因像高优先级线程枪占之类导致操作系统也剥夺了线程A继续持有CPU的权利，糟糕的是，因为线程A此时持有锁，而线程A又无法继续向前推进，这就进一步使得线程B和C也无法继续向前推进。

你会发现在T3时刻，这几个线程都没有任何进展，根本原因在于我们为解决多线程问题加互斥锁惊动了操作系统，而这类互斥锁是操作系统给我们实现的，那么解决线程安全问题一定要经过操作系统吗？

不是的，在硬件层面也可以解决线程安全问题，硬件层面当然是指CPU，或者说机器指令。

CPU中有特定的原子指令，实际上操作系统也是基于这些指令实现的互斥锁，既然操作系统能用这些指令，我们(用户态)也可以使用这些指令，基于此我们可以将上述代码进行简单改造：

int count = 0;
               
void add() {
    int old_value;


    do {
      old_value = count;
    } while (!atomic_compare_exchange(&count, &old_value, old_value + 1));
}

此时add函数是线程安全的，我们也没有对其进行加锁，不管多少线程同时调用add函数得到count都是正确的，而该函数的执行完全不涉及操作系统，不需要操作系统来维护秩序，利用的就是CPU中的原子指令，CPU在硬件层面一样可以替我们维护秩序。

上述代码就是所谓lock-free的，不管操作系统怎样调度这三个线程，我们都能确保这三个线程中总有一个能继续向前推进。

lock-free的系统看起来像这样：

对于这类系统不存在某个时间片下线程都无法推进的情况，换句话说就是lock-free程序保证至少有一个线程能继续向前推进。

可以看到，lock-free给出了比普通锁更优的保障。

但不能简单从代码是不是加锁或不加锁去判断代码是否lock-free，回旋锁也是没有上述互斥锁的，也不经过操作系统，但回旋锁并不是lock-free的，如果你这样利用CPU中的原子操作修改add函数：

int count = 0;
int lock = 0;  // 回旋锁


void add () {
    int expected = 0;
    while(!atomic_compare_exchange_weak(&lock, &expected, 1))
        expected = 0;
    count++;
    lock = 0;
}

这就是典型的回旋锁，然而如果某个线程持有回旋锁后被操作系统挂起那么其它线程开始无效的执行死循环，除了白白消耗CPU之外它们都无法继续向前推进，显而易见，如果此时系统负载较高那么此类程序的性能会变差。

既然现在你已经知道了lock-free我们再继续优化这段代码：

std::atomic<int> count;


void add() {
    ++count;
}

这段代码没有锁，也不需要用循环不断检测是否有其它线程修改count，不管操作系统如何调度这三个线程，它们都能在有限的操作数内执行完成，此时我们说该程序是wati-free的，wait-free系统运行起来像这样：

可以看到在任意时间片内，不管操作系统怎样调度，所有线程都能向前推进。

wait-free比lock-free的要求更高更加严格，由于wait-free的程序总是能在有限的步骤内执行完成，因此实时性是最好的，适用于那些对实时性要求较高的场景，当然实现难度也要比lock-free更高。

值得注意的是，wait-free以及lock-free程序的实现通常不是那么简单。

好啦，今天就到这里，希望这篇对大家理解多线程有所帮助。​