linux同步相关内容

互斥锁、信号量、自旋锁

http://www.cnblogs.com/biyeymyhjob/archive/2012/07/21/2602015.html

linux用户空间机制：

1. 互斥量

　　pthread互斥接口，确保同一时间只有一个线程访问数据

　　本质是锁

　　pthread_mutex_t

　　pthread_mutex_lock、pthread_mutex_trylock、pthread_mutex_unlock

　　要么是锁住状态，要么不加锁；一次只有一个线程对其加锁

2. 读写锁（共享-独占锁）

　　与互斥量类似，具有更高的并行特性

　　三种状态：读模式加锁、写模式加锁、不加锁

　　一次只能有一个线程能占有写模式锁、但可有多个线程同时占有读模式锁

　　当写加锁状态时，在这个锁被解锁之前，所有试图对这个锁加锁的线程均阻塞

　　当读加锁状态时，所有读模式均可得到访问权；写模式必须等到所有线程释放资源

　　适合读的次数远大于写的情况

　　pthread_rwlock_t

3. 条件变量

　　条件变量是利用线程间共享的全局变量进行同步的一种机制，主要包括两个动作：一个线程等待"条件变量的条件成立"而挂起；另一个线程使"条件成立"（给出条件成立信号）。为了防止竞争，条件变量的使用总是和一个互斥锁结合在一起。

　　条件变量和互斥量一起使用时，允许线程以无竞争的方式等待特定的条件发送

　　条件本身由互斥量保护，线程在改变条件状态前必须锁住互斥量

　　pthread_cond_t

　　pthread_cond_wait、pthread_cond_timedwait

　　pthread_cond_signal、pthread_cond_broadcast

PS：避免死锁

　　把结构简单化：假设需要对两个互斥量A和B同时加锁，如果所有线程总是在对B加锁之前锁住A，或者在对A加锁之前锁住B，那么就不会发生死锁。

linux内核空间同步机制：

1. 信号量

　　struct semaphore

　　down、up

　　不可递归

2. 读/写信号量

　　struct rw_semaphore

　　down_read、down_write、up_read、up_write

　　写的优先级比读高、适用于很少需要写访问且写只会占很短时间的情况

3. 完成量

　　一种轻量级机制，允许一个线程告诉另一个线程某个工作已经完成

　　struct completion

　　wait_for_completion、complete、complete_all

4. 自旋锁

　　任何拥有自旋锁的代码都必须是原子的，且不能休眠

　　拥有自旋锁时在本地CPU上禁止中断

　　自旋锁必须在最短时间内拥有，不能长时间占有

　　spinlock_t

　　spin_lock、spin_unlock、spin_trylock

　　不可递归

5. 读/写自旋锁

　　rwlock_t

　　read_lock、read_unlock、write_lock、write_unlock

6. 免锁算法

　　循环缓冲区

7. 原子变量

　　共享的资源是一个简单整数

　　atomic_t

　　atomic_read、atomic_add、atomic_sub、atomic_inc、atomic_dec

8. 位操作

　　asm/bitops.h

　　set_bit、clear_bit、change_bit

9. 顺序锁 seqlock

　　写优先级大于读

　　适用于读操作远大于写操作的情况

　　seqlock_t、write_seqlock、write_sequnlock

　　实现思路：

　　用一个递增的整数表示sequence。写操作进入临界区时，sequence++；退出时再++。写操作还需要获得一个锁（用spinlock实现），这个锁仅用于写互斥，以保证同一时间最多只有一个正在进行的写操作。

　　当sequence为奇数时，表示有写操作正在进行，这是读操作要进入临界区需要等待，直到sequence变成偶数。读操作进入临界区时，需记下当前sequence的值，等它退出临界区时用记录的sequence和当前sequence做比较，不等则表示在读操作进入临界区时发生了写操作，这时读到的东西是无效的，需要返回重试。

10. 读取-复制-更新（RCU机制）

　　用在读多写少的情况，如网络路由表的查询更新、设备状态表的维护、数据结构的延迟释放以及多径I/O设备的维护等。

　　对于被RCU保护的共享数据结构，读者不需要获得任何锁就可以访问它，但写者在访问它是首先拷贝一个副本，然后对副本进行修改，最后使用一个callback机制在适当的时机把指向原来数据的指针指向新的被修改的数据。这个时机就是所有应用该数据的CPU都退出共享数据的操作。

　　读者必须提供一个信号告诉写者一边写者能够确定数据可以被安全地释放或修改的时机。有一个专门的垃圾收集器来探测读者的信号，一旦所有的读者都已经发送信号告知他们都不再使用被RCU保护的数据时，垃圾收集器救调用callback完成最后的数据释放或修改操作。

　　RCU不能替代rwlock，因为如果写比较多时，对读者的性能提高不能弥补写者导致的损失。

　　等待适当时机的时期grace period，CPU发生上下文切换称为经历了一个quiescent state，grace period就是所有CPU都经历了一次quiescent state所需要的等待的时间。

　　rcu_read_lock() 

　　rcu_read_unlock() //简单理解成所有读者都调过了unlock，就可以到了合适的时机

　　call_rcu()

PS：以上所有同步机制变量都需要进行初始化