Linux 内核同步原语

每 CPU 变量

每 CPU 变量是一种内核用来避免竞争（而不是解决竞争）的手段，意思就是每个 CPU 访问各自的每 CPU变量而不要越界，这样就直接不需要同步了

原子操作

原子操作需要硬件支持，这类芯片级的原子操作对操作系统来说是不可或缺的，他们不仅用来应对一些简单的原子性需求，比如atomic_inc, atomic_dec；并且用来实现锁，锁的意义是将临界区缩小到 lock和 unlock 甚至更小的范围之内以避免同步问题，那么加锁操作本身的竞争问题必须要由原子操作来解决，硬件级CAS指令如 test_and_set, cmpxchg指令都是由硬件来保证原子性的，多处理器环境下通过锁总线来保证多个CPU 对内存的串行访问

优化屏障与内存屏障

自旋锁

自旋锁用于多处理器系统中的同步，它的特定就是“忙等”；

自旋锁保护的临界区都是禁止内核抢占的，即获得锁之后会立即禁用内核抢占，但spinning的过程中仍然有可能会被高优先级的进程替代。

自旋锁在单处理器环境下是无效的，对于 Linux，单核处理器系统中，自旋锁原语仅仅是关闭内核抢占或重新开启内核抢占

读写自旋锁

顺序锁

信号量

信号量由3个部分组成：一个整数变量、一个等待的进程的链表、两个原子方法：down() up()。

down() 对信号量值减一，如果新值小于0，则将调用进程添加到等待链表，然后调用调度程序，将该进程投入睡眠（挂起 / 阻塞）。up()对信号量加1，新值大于等于0则激活阻塞在 down 上一个或多个的进程。

信号量与自旋锁的区别在于等待锁的时候，获取锁的时候会将进程投入睡眠；资源释放后进程才再次变为可运行的。只有可以睡眠的函数才能获取内核信号量；中断处理程序和可延迟函数都不能使用内核信号量，为此 Linux 提供了 down_trylock() 作为补充函数（实际上就和自旋锁差不多了）。

读写信号量

互斥量

pthread 线程同步

自旋锁

信号量

互斥量

互斥量本质就是在自旋锁上加了个 waiting，当线程获得锁的时候，其他试图获得锁的线程会被系统投入睡眠状态（挂起），当线程释放锁的时候会唤醒阻塞在这个互斥量上的其他线程

mutex

int pthread_mutex_lock(pthread_mutex_t *mutex);
int pthread_mutex_trylock(pthread_mutex_t *mutex); // 类似自旋锁，函数会立即返回，不会被系统投入睡眠
int pthread_mutex_unlock(pthread_mutex_t *mutex);

互斥量的本质是二值信号量

读写锁

读写锁与互斥量类似。但是它有三种状态和两个加锁的动作，三个状态分别为：读锁占用，写锁占用，无锁状态；两个动作是获取读锁，获取写锁。

如果当前状态是写锁占用，那么所有其他获取锁的动作都会阻塞，直到写锁释放。

如果当前状态是读锁占用，那么其他获取读锁动作的线程会立即得到访问权，而其他获取写锁的线程会阻塞直到读锁释放（被所有线程释放）；并且获取写锁的请求到来后，后续的读锁请求也会被阻塞，以防止长期的读锁占用无法满足获取写锁的请求。

rwlock

pthread_rwlock_rdlock(pthread_rwlock_t *rwlock);
pthread_rwlock_wrlock(pthread_rwlock_t *rwlock);
pthread_rwlock_unlock(pthread_rwlock_t *rwlock);

条件变量

互斥锁能解决多个线程同时访问一个资源的问题，却无法优雅的解决线程协作问题。比如当某个线程完成了一项工作，需要另一个线程基于这个结果去完后后续动作的情况，仅仅基于互斥锁，需要等待的线程通过竞争的方式轮询检查互斥锁保护的对象，这种轮询很难取得实时性和性能的平衡

条件变量必须与互斥量结合使用（受互斥量保护），以实现更高级的并发控制模型，比如blocking queue，wait – notify，future 等

一个简单的blocking queue实现 – 摘自APUE P.310

#include <pthread.h>

typedef struct msg
{
struct msg *next;
// more stuff here
} MSG;

MSG *q;
pthread_cond_t qready = PTHREAD_COND_INITIALIZER;
pthread_mutex_t qlock = PTHREAD_MUTEX_INITIALIZER;

// producer thread
void enqueue_msg(MSG *m)
{
pthread_mutex_lock(&qlock);
m->next = q;
q = m;
pthread_mutex_unlock(&qlock);
pthread_cond_signal(&qready);
}

// consumer thread
void process_msg()
{
MSG *m;
while(1)
{
pthread_mutex_lock(&qlock);
while(q == NULL)
pthread_cond_wait(&qready, &qlock);
m = q;
q = m->next;
pthread_mutex_unlock(&qlock);
// then process the message m
}
}

consumer thread 的代码是可以用于多线程竞争消费的（而不会在第31行产生死锁），因为 pthread_cont_wait 函数一个很重要的特性是：当线程投入等待队列的时候，会同时完成互斥量的解锁，两个操作的原子性由系统内核保证；同样当函数返回，即线程唤醒的时候，互斥量再次锁上。如果没有这个特性，当一个消费线程释放锁的时候，另一个消费线程在生产线程将消息投入 queue 之前就锁住了互斥量，而如果这时候 queue 是空的，cond_wait就会一直阻塞，那生产线程由于无法获取互斥量将永远无法运行。这也是为什么条件变量需要和互斥量配合使用。

另一个值得注意的地方是，这段代码的19行和20行是可以交换的。到底先释放互斥量还是先发送条件信号，这需要结合具体的业务场景去考虑，我这篇博客中的案例就是先调用 cond_signal 会更优，个人觉得书上的例子也是先调用 cond_signal会更优。先 unlock 再 signal 的顺序其实会更容易导致虚假唤醒，不过由于各种原因虚假唤醒也是不可避免的，而第30行使用 while 而不是 if 正是为了解决虚假唤醒的问题。

多维度看并发与同步