并发控制简介

并发控制，控制的是对共享资源的并发访问。

1 并发控制思路

分为两大类。下面只是举一些例子，大部分针对内存数据，有些思路是可以直接模仿的。

1.1 避免竞争

）多进程
进程空间是进程独享的。

）Thread local storage
线程隶属于进程，共享进程空间，容易出现竞争。Thread local storage是线程独享的。

）明确分工，独享某些资源
大部分GUI框架都是单线程模型，让一部分数据只允许UI线程访问（需要程序配合）。

）MVCC
多版本并发控制，最早是在PostgreSQL接触到的，没有完全避免竞争，是部分避免，能做到读写分离。
从实现来看，是CopyOnWrite，java.util.concurrent.CopyOnWriteArrayList属于此类。

）不可变数据（immutable）
纯函数式编程语言没有变量，这很自然就避免了共享变量竞争。

）允许重复消耗一些资源，避免竞争
例子，同时生成同一个小文件，偶尔出现这种情况，可以让不同的线程获得唯一的文件名，把数据写入相应文件。
如果是代价很小的操作，那可以每次都重复消耗。

）拆分数据结构
把数据分离，这样可以并发修改各个不同的部分。
对于RDBMS，把多个列的记录拆分为key-value型的更多记录，可以有revision列。有些行可能需要保持数据的一致性，更新之前应该统一加锁。

）无锁CopyOnWrite
对某些数据的并发修改是没有冲突的（最新的修改可以直接取代次新的修改），这种情况可以不用锁。
方法：以RDBMS为例，修改记录会自动加锁，所以，每次都插入新的记录，旧的记录由后台任务负责删除（不能直接删除，需要先标记）。对于拆分过的数据结构，做到这一点还是比较方便的。

1.2 协调竞争

1.2.1 锁

）排他锁
比如，mutex,semaphore

）小范围锁
例子：
* 读写锁
* Double-checked Locking
* Java5里边的ConcurrentHashMap使用了segment。

1.2.2 无锁

）Lock-free
确保执行它的所有线程中至少有一个能够继续往下执行。

说是没阻塞的，确实可以一直运行，只不过可能运行不到关键代码，相当于阻塞了，只是可能比显式锁开销小一些，特别是当被原子保护的代码很快能执行完的时候，否则，可能还不如显式锁。

一般使用CAS原子操作来实现。

例子：
* Spin lock（自旋锁）
* Seqlock

）Wait-free
任何操作都可以在有限步之内完成。

java.util.concurrent.ConcurrentLinkedQueue使用Simple, Fast, and Practical Non-Blocking and Blocking Concurrent Queue Algorithms - Author: Maged M. Michael & Michael L. Scott - www.cs.rochester.edu介绍的算法实现了一个，这个算法1996年就有了。
伪代码在Fast Concurrent Queue Algorithms - Author: Maged M. Michael & Michael L. Scott - www.cs.rochester.edu，注释比较多。

1.2.3 参考资料

* https://en.wikipedia.org/wiki/Memory_barrier
* https://en.wikipedia.org/wiki/Non-blocking_synchronization
* 透过Linux内核看无锁编程 - Author: 杨小华 - www.ibm.com
* https://en.wikipedia.org/wiki/Seqlock
* Linux seqlock - Author: droplet - www.kernelchina.org
* https://en.wikipedia.org/wiki/Spinlock

=文章版本=

20130331
20130523
20130602 删除费解的部分