29.1 并发计数器 237
第
第
2
2
9
9
章
章
基
基
于
于
锁
锁
的
的
并
并
发
发
数
数
据
据
结
结
构
构
在结束锁的讨论之前，我们先讨论如何在常见数据结构中使用锁。通过锁可以使数据
结构线程安全（thread safe）。当然，具体如何加锁决定了该数据结构的正确性和效率？因此，
我们的挑战是：
关键问题：如何给数据结构加锁？
对于特定数据结构，如何加锁才能让该结构功能正确？进一步，如何对该数据结构加锁，能够保证
高性能，让许多线程同时访问该结构，即并发访问（concurrently）？
当然，我们很难介绍所有的数据结构，或实现并发的所有方法，因为这是一个研究多
年的议题，已经发表了数以千计的相关论文。因此，我们希望能够提供这类思考方式的足
够介绍，同时提供一些好的资料，供你自己进一步研究。我们发现，Moir 和 Shavit 的调查
[MS04]就是很好的资料。
29.1 并发计数器
计数器是最简单的一种数据结构，使用广泛而且接口简单。图 29.1 中定义了一个非并
发的计数器。
1 typedef struct counter_t {
2 int value;
3 } counter_t;
4
5 void init(counter_t
*
c) {
6 c->value = 0;
7 }
8
9 void increment(counter_t
*
c) {
10 c->value++;
11 }
12
13 void decrement(counter_t
*
c) {
14 c->value--;
15 }
16
17 int get(counter_t
*
c) {
18 return c->value;
19 }
图 29.1 无锁的计数器
