锁的实现

互斥锁

锁的开销

机制

摘录自：https://www.cnblogs.com/MrLiuZF/p/15143976.html

现在锁的机制一般使用futex(fast userspace mutexes)，即内核态和用户态的混合机制。

在futex之前，内核维护一个对象，这个对象对所有进程可见，这个对象用来管理互斥锁并且通知阻塞的进程。如果进程A要进入临界区，先去内核查看这个对象，有没有别的进程在占用这个临界区，出临界区的时候，也去内核查看这个对象，有没有别的进程在等待进入临界区，然后根据一定的策略唤醒等待的进程。这些不必要的系统调用造成了大量的性能开销。

futex是一种用户态和内核态混合的同步机制。首先，同步的进程间通过mmap共享一段内存，futex变量就位于这段共享的内存中且操作是原子的。当进程尝试进入或者退出互斥区的时候，先去查看共享内存中的futex变量，如果没有竞争发生，则只修改futex，而不用再执行系统调用了。当通过访问futex变量告诉进程有竞争发生，则还是得执行系统调用去完成相应的处理（wait或者wake up）。简单的说，futex就是通过在用户态的检查，如果没有竞争就不需要陷入内核，大大提高了low-contention时的效率。

mutex是在futex的基础上用内存共享变量实现的。如果共享变量建立在进程内，它就是一个线程锁，如果建立在进程间共享内存上，它就是一个进程锁。pthread_mutex_t中的_lock字段用户标记占用情况，先使用CAS判断_lock是否占用，若未占用，则直接返回。否则通过__lll_lock_wait_private调用SYS_futex系统调用迫使线程进入沉睡。CAS是用户态的CPU指令，若无竞争，简单修改锁状态即返回，非常高效。只有发现竞争，才通过系统调用陷入内核态。

所以如果锁不存在冲突，每次获得锁和释放锁的开销仅仅是CAS指令的开销。

竞争条件和非竞争条件下的锁开销试验

#include <chrono>
#include <stdio.h>
#include <mutex>
#include <thread>
#include <vector>
#include <memory>

int counter = 0;
std::mutex g_mutex;

/* Get current time in nano-seconds. */
auto lambda_now = []()
{
    using namespace std::chrono;
    auto now_count = duration_cast<nanoseconds>(system_clock::now().time_since_epoch()).count();
    return now_count;
};

/* Add 1 to @counter for certain times, calculate
 how much time spent, store the time to @a. */
void trd_work(int &a)
{   
    const int times = 1 * 1000 * 10;
    auto t1 = lambda_now();
    for (int i = 0; i < times; ++i)
    {
        g_mutex.lock();
        counter += 1;
        g_mutex.unlock();
    }
    auto t2 = lambda_now();

    a = (int)(t2-t1);
}

int main(int argc, char **argv)
{
    if (argc != 2)
    {
        printf("Usage: %s <thread num>\n", argv[0]);
        return EXIT_FAILURE;
    }

    std::size_t num_threads = atoi(argv[1]);

    std::vector<int> vec_sum;
    std::vector<std::shared_ptr<std::thread>> vec_threads;
    vec_sum.resize(num_threads);
    vec_threads.resize(num_threads);

    for (std::size_t i = 0; i < num_threads; ++i)
    {
        vec_threads[i] = std::make_shared<std::thread>(trd_work, std::ref(vec_sum[i]));
    }

    for (auto i : vec_threads)
    {
        i->join();
    }

    int total_time = 0;
    for (auto i : vec_sum)
    {
        total_time += i;
    }

    printf("%d ns/lock, counter=%d\n", total_time / counter, counter);

    return 0;
}

test@test:~/tmp$ g++ test.cpp -O3
test@test:~/tmp$ ./a.out 1
31 ns/lock, counter=10000
test@test:~/tmp$ ./a.out 2
155 ns/lock, counter=20000
test@test:~/tmp$ ./a.out 4
343 ns/lock, counter=40000
test@test:~/tmp$ ./a.out 8
748 ns/lock, counter=80000

上述测试代码中，各个线程通过加锁的方式，对全局变量进行特定次数的+1操作。先不考虑互斥锁的耗时，此时线程越多，需要等待的时间越长（因为同一时间只能有一个线程操作），并且等待的时间和线程数成正比。

但是，从试验结果看，仅在线程数大于2之后，这个比例关系才成立。因此，有理由相信，有竞争关系时相比没有竞争关系时，锁操作会消耗更多的时间。由试验数据估算，单个线程的耗时应为75ns左右，实际为30ns左右，因此耗时近一倍。

libc --> NPTL(pthread)