原子操作
保证多个线程不在同一个时间内访问共享资源
类似互斥量对共享资源访问的保护，但是原子操作更接近底层，效率更高
数值操作比如自增（++）、自减（--）、赋值（=）都不是原子操作， 如果使用锁或者互斥量保证操作的安全性，对于较高并发的程序会造成一定的性能瓶颈
-
GCC从4.1.2开始提供了
__sync_系列的built-in函数，用于提供加减和逻辑运算的原子操作// 第一组返回更新前的值，第二组返回更新后的值 type __sync_fetch_and_add (type *ptr, type value) type __sync_fetch_and_sub (type *ptr, type value) type __sync_fetch_and_or (type *ptr, type value) type __sync_fetch_and_and (type *ptr, type value) type __sync_fetch_and_xor (type *ptr, type value) type __sync_fetch_and_nand (type *ptr, type value) type __sync_add_and_fetch (type *ptr, type value) type __sync_sub_and_fetch (type *ptr, type value) type __sync_or_and_fetch (type *ptr, type value) type __sync_and_and_fetch (type *ptr, type value) type __sync_xor_and_fetch (type *ptr, type value) type __sync_nand_and_fetch (type *ptr, type value) // 原子比较和交换操作 // 如果*ptr == oldval，就将newval写入*ptr，第一个函数返回操作之前的值，第二个函数在相等并写入的情况下返回true type __sync_val_compare_and_swap (type *ptr, type oldval, type newval) bool __sync_bool_compare_and_swap (type *ptr, type oldval, type newval) // 原子赋值操作，第一个函数将*ptr设为value并返回*ptr操作之前的值，第二个函数将*ptr置零 type __sync_lock_test_and_set (type *ptr, type value) void __sync_lock_release (type *ptr)
无锁队列实现
CAS（Compare And Swap）
-
GCC的CAS
bool __sync_bool_compare_and_swap (type *ptr, type oldval, type newval, ...) type __sync_val_compare_and_swap (type *ptr, type oldval, type newval, ...) -
C++11的CAS
template< class T > bool atomic_compare_exchange_weak( std::atomic* obj, T* expected, T desired ); template< class T > bool atomic_compare_exchange_weak( volatile std::atomic* obj, T* expected, T desired );
无锁队列的链表实现
enQueue(val) {
node = new Node(val);
do {
p = tail;
} while(CAS(p->next, NULL, node) != TRUE);
CAS(tail, p, node);
}
deQueue() {
do {
p = head;
} while(CAS(head, p, p->next) != TRUE);
return p->next->val;
}
操作系统中锁的原理
锁的本质
内存中的一个整型数，不同的数值代表不同的状态（空闲状态和加锁状态）
加锁的过程
- 读内存表示锁的变量
- 判断锁的状态
- 如果已经加锁，返回失败
- 把锁设置为上锁状态
- 返回成功
锁的实现
-
中断
中断可能会导致两个线程同时获取到锁
关中断：加锁操作完成后再开中断，代价高，无法处理多核场景
-
test and set指令
test and set指令将读取内存，判断和设置值作为一个原子操作，在单核场景下加锁的过程就是原子性的了
多核场景下会出现两个线程同时执行test and set情况
-
锁内存总线
硬件提供了锁内存总线的机制，在锁内存总线的状态下执行test and set操作就能保证不会存在多线程获取到锁的情况
内核锁相关
- 临界区
- 原子操作
- 自旋锁
- 信号量
- 互斥量
- RCU机制
- 读写锁
自旋锁
-
用于执行很快的锁操作，等待锁的时间不会很长，自旋锁是不可重入的
当一个线程在获取锁时，如果锁已经被其它线程获取，那么该线程将循环等待，不断地判断该锁是否能够被成功获取，直到获取到锁时才会退出循环，尝试获取锁的线程一直处于活跃状态，但是并没有执行任何有效的任务，使用这种锁会造成busy-waiting
-
自旋锁的优点
自旋锁不会使线程状态发生切换，一直处于用户态，即线程一直都是活跃的不会使线程进入阻塞状态，减少了不必要的上下文切换，执行速度快
非自旋锁在获取不到锁的时候会进入阻塞状态，从而进入内核态，当获取到锁的时候需要从内核态恢复，需要线程上下文切换（线程被阻塞后便进入内核调度状态，这个会导致系统在用户态与内核态之间来回切换，严重影响锁的性能）
RCU机制（Read-Copy Update）
-
空间换时间
读取是访问实际存储，修改则是通过创建一个副本，在副本中修改相关内容，在所有读取结束后将指针替换为新的副本指针
读写锁
- 读写自旋锁
- 读写信号量
用户空间锁相关
- 原子操作
- 自旋锁
- 信号量
- 互斥量
- 读写锁
内核可以很好地通过schedule调度来进行相关task等待以及唤醒，但是用户空间并不能直接去处理调度相关内容，所以用户空间锁等待锁时是如何挂起线程的呢？
pthread定义了一大堆与thread相关的接口函数，包括线程，锁，优先级，信号等等各种资源。用户空间相关的锁就是通过这一套标准与内核交互的
pthread_spin_lock 自旋锁
pthread_mutex_lock/unlock 互斥锁
pthread_rwlock_rdlock 读锁
pthread_rwlock_timedrdlock 读锁超时
pthread_rwlock_wrlock 写锁
pthread_rwlock_timedwrlock 写锁超时
pthread_rwlock_unlock 释放读写锁
pthread_cond_wait 条件变量等待
pthread_cond_signal 条件变量通知
pthread_cond_broadcast 条件变量通知所有等待thread
-
pthread_spin_lock就是通过while循环执行CAS操作 -
pthread_mutex_lock及pthread_rwlock实际是通过futex系统调用来执行的，其基本思想就是想尝试在user space通过CAS获取锁，如果成功就直接返回，如果失败则进入内核调用mutex_lock相关逻辑，而读写锁相关逻辑是自己实现的，其思想与内核相关实现差不多 -
pthread_cond_wait/notify会结合信号机制及锁机制一起合作实现，通过维护pthread_cond_t中的thread队列来进行相关通信及等待
