互斥锁、读写锁 、 自旋锁和RCU锁

基础知识思考整理
http://blog.csdn.net/aganlengzi/article/details/50996227

互斥锁 mutex：

在访问共享资源之前对进行加锁操作，在访问完成之后进行解锁操作。
加锁后，任何其他试图再次加锁的线程会被阻塞，直到当前进程解锁。
如果解锁时有一个以上的线程阻塞，那么所有该锁上的线程都被编程就绪状态，
第一个变为就绪状态的线程又执行加锁操作，那么其他的线程又会进入等待。
在这种方式下，只有一个线程能够访问被互斥锁保护的资源。

读写锁 rwlock（也叫作共享互斥锁：读模式共享，写模式互斥）：

读写锁有三种状态：读加锁状态、写加锁状态和不加锁状态
一次只有一个线程可以占有写模式的读写锁，但是多个线程可以同时占有读模式的读写锁。（这也是它能够实现高并发的一种手段）
当读写锁在写加锁模式下，任何试图对这个锁进行加锁的线程都会被阻塞，直到写进程对其解锁。
当读写锁在读加锁模式先，任何线程都可以对其进行读加锁操作，但是所有试图进行写加锁操作的线程都会被阻塞，直到所有的读线程都解锁。
所以读写锁非常适合对数据结构读的次数远远大于写的情况。

如果严格按照上述读写锁的操作进行的话，那么当读者源源不断到来的时候，写者总是得不到读写锁，就会造成不公平的状态。
一种避免这种不公平状态的方法是：
当处于读模式的读写锁接收到一个试图对其进行写模式加锁操作时，便会阻塞后面对其进行读模式加锁操作的线程。
这样等到已经加读模式的锁解锁后，写进程能够访问此锁保护的资源。

自旋锁spinlock：

自旋锁的使用模式和互斥锁很类似。
只是在加锁后，有线程试图再次执行加锁操作的时候，该线程不会阻塞，而处于循环等待的忙等状态（CPU不能够做其他事情）。
所以自旋锁适用的情况是：锁被持有的时间较短，而且进程并不希望在重新调度上花费太多的成本。

RCU锁（Read-Copy Update）：读-复制 更新

实际上是对读写锁的一种改进，同样是对读者线程和写者线程进行区别对待，只不过对待的方式是不同的。
读写锁中只允许多个读者同时访问被保护的数据，但是在RCU中允许多个读者和多个写者同时访问被保护的资源。写者的同步开销则取决于使用的写者间同步机制，RCU并不对此进行支持。
RCU中，读者不需要使用锁，要访问资源尽管访问就好了。
RCU中，写者的同步开销比较大，要等到所有的读者都访问完成了才能够对被保护的资源进行更新。
写者修改数据前首先拷贝一个被修改元素的副本，然后在副本上进行修改，修改完毕后它向垃圾回收器注册一个回调函数以便在适当的时机执行真正的修改操作。
读者必须提供一个信号给写者以便写者能够确定数据可以被安全地释放或修改的时机。有一个专门的垃圾收集器来探测读者的信号，一旦所有的读者都已经发送信号告知它们都不在使用被RCU保护的数据结构，垃圾收集器就调用回调函数完成最后的数据释放或修改操作。
写者要从链表中删除元素 B，它首先遍历该链表得到指向元素 B 的指针，然后修改元素 B 的前一个元素的 next 指针指向元素 B 的 next 指针指向的元素C，修改元素 B 的 next 指针指向的元素 C 的 prep 指针指向元素 B 的 prep指针指向的元素 A,在这期间可能有读者访问该链表，修改指针指向的操作是原子的，所以不需要同步，而元素 B 的指针并没有去修改，因为读者可能正在使用 B 元素来得到下一个或前一个元素。写者完成这些操作后注册一个回调函数以便在 grace period 之后删除元素 B，然后就认为已经完成删除操作。垃圾收集器在检测到所有的CPU不在引用该链表后，即所有的 CPU 已经经历了 quiescent state（上下文切换）,grace period（所有的CPU都经历了一次上下文切换） 已经过去后，就调用刚才写者注册的回调函数删除了元素 B。

适用于网络路由表的查询更新、设备状态表的维护、数据结构的延迟释放以及多径I/O设备的维护

[0] UNIX环境高级编程
[1] https://www.ibm.com/developerworks/cn/linux/l-rcu/