Skip to main content

多线程

互斥​

竞争条件（race condition），当多线程相互竞争操作共享变量时，由于运气不好，即在执行过程中发生了上下文切换，我们得到了错误的结果，事实上，每次运行都可能得到不同的结果，因此输出的结果存在不确定性（indeterminate）。

由于多线程执行操作共享变量的这段代码可能会导致竞争状态，因此我们将此段代码称为临界区（critical section），它是访问共享资源的代码片段，一定不能给多线程同时执行。

我们希望这段代码是互斥（mutual exclusion）的，也就说保证一个线程在临界区执行时，其他线程应该被阻止进入临界区，说白了，就是这段代码执行过程中，最多只能出现一个线程。

同步​

所谓同步，就是并发进程/线程在一些关键点上可能需要互相等待与互通消息，这种相互制约的等待与互通消息称为进程/线程同步。

实现​

在实现进程/线程的互斥和同步中，我们可以使用锁或者信号量的方式。

其中锁用于实现互斥，而信号量可以用于实现互斥和同步。

锁​

根据锁的实现不同，可以分为忙等待锁和无忙等待锁。

忙等待锁​

依赖于 CPU 中提供的 Test-and-Set 指令。

#include <thread>
#include <vector>
#include <iostream>
#include <atomic>
 
std::atomic_flag lock = ATOMIC_FLAG_INIT;
 
void f(int n)
{
    for (int cnt = 0; cnt < 40; ++cnt) {
        while (lock.test_and_set(std::memory_order_acquire)) {  
        // acquire lock
        // Since C++20, it is possible to update atomic_flag's
        // value only when there is a chance to acquire the lock.
        // See also: https://stackoverflow.com/questions/62318642
        #if defined(__cpp_lib_atomic_flag_test)
            while (lock.test(std::memory_order_relaxed))        // test lock
        #endif
                ; // spin
        }
        static int out{};
        std::cout << n << ((++out % 40) == 0 ? '\n' : ' ');
        lock.clear(std::memory_order_release);                  // release lock
    }
}
 
int main()
{
    std::vector<std::thread> v;
    for (int n = 0; n < 10; ++n) {
        v.emplace_back(f, n);
    }
    for (auto& t : v) {
        t.join();
    }
}
  1. 若没有其他线程持有锁，调用 lock 时，TestAndSet(flag, 1) 会返回 0，跳出 while 循环，flag 被设置为 1，调用 unlock 后，将 flag 清理为 0
  2. 若某线程已经持有锁，调用 lock 时，TestAndSet(flag, 1) 会返回 1，本线程即会一直忙等待，其他线程 unlock 后，TestAndSet(flag, 1) 才会返回 0，跳出 while 循环。

忙等待锁又被称为自旋锁。

这是最简单的一种锁，一直自旋，利用 CPU 周期，直到锁可用。在单处理器上，需要抢占式的调度器（即不断通过时钟中断一个线程，运行其他线程）。否则，自旋锁在单 CPU 上无法使用，因为一个自旋的线程永远不会放弃 CPU。

无等待锁​

获取不到锁的时候，不用自旋，而是把当前线程放入到锁的等待队列，然后执行调度程序，把 CPU 让给其他线程执行。

信号量​

信号量表示资源的数量，对应的变量是一个整型(sem)变量。

  • P 操作：将 sem 减 1，相减后，如果 sem < 0，那么进程/线程进入阻塞等待，否则继续
  • V 操作，将 sem 加 1，相加后，如果 sem <= 0，那么唤醒一个等待中的进程/线程

As my understanding, mutex is a kind of lock-mechanism, which is implemented based on the OS/kernel. For example, Linux offers a mechanism, which is futex. With the help of futex, we could implement mutex and semaphore. Furthermore, I've known that futex is implemented by the low-level atomic operation, such as CompareAndSet, CompareAndSwap.