转载自《四火的唠叨》
Peterson 算法（Dekker算法的演化），这个算法设计得很巧妙，理解的核心就是搞清楚三个标志位是怎样控制两个方法对临界区的访问的：
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
2 int
3 flag1 =
4 0
5 ;
6 //主观因素：flag1表示方法1自身是否要求进入临界区
7
8
9
10
11
12 volatile
13 int
14 flag2 =
15 0
16 ;
17 //主观因素：flag2表示方法2自身是否要求进入临界区
18
19
20
21
22
23 volatile
24 int
25 turn =
26 1
27 ;
28 //客观因素：turn取1和2分别表示当前临界区针对方法1还是方法2开放
29
30
31
32
33
34
35
36
37
38
39
40 void
41 fun1(){
42
43
44
45
46
47
48 flag1 =
49 1
50 ;
51
52
53
54
55
56
57 turn =
58 2
59 ;
60
61
62
63
64
65
66 while
67 ( flag2==
68 1
69 && turn==
70 2
71 ){}
72 //只有在方法2自身要求进入临界区且临界区针对方法2开放时，方法1才会阻塞
73
74
75
76
77
78
79 //Critical Section
80
81
82
83
84
85
86 ...
87 //临界区内
88
89
90
91
92
93
94 flag1 =
95 0
96 ;
97
98
99
100
101
102 }
103
104
105
106
107
108
109
110
111
112
113
114 void
115 fun2(){
116
117
118
119
120
121
122 flag2 =
123 1
124 ;
125
126
127
128
129
130
131 turn =
132 1
133 ;
134
135
136
137
138
139
140 while
141 ( flag1==
142 1
143 && turn==
144 1
145 ){}
146 //只有在方法1自身要求进入临界区且临界区针对方法1开放时，方法1才会阻塞
147
148
149
150
151
152
153 //Critical Section
154
155
156
157
158
159
160 ...
161 //临界区内
162
163
164
165
166
167
168 flag2 =
169 0
170 ;
171
172
173
174
175
176 }
177
ConcurrentHashMap，设计巧妙，用桶粒度的锁，避免了put和get中对整个map的锁定，尤其在get中，只对一个HashEntry做锁定操作，性能提升是显而易见的。
HashMap不是线程安全的，错误的使用并发状况下可能出现CPU100%的状况：
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
2
3
4
5
6
7 * Transfers all entries from current table to newTable.
8
9
10
11
12
13 */
14
15
16
17
18
19 void
20 transfer(Entry[] newTable) {
21
22
23
24
25
26
27 Entry[] src = table;
28
29
30
31
32
33
34 int
35 newCapacity = newTable.length;
36
37
38
39
40
41
42 for
43 (
44 int
45 j =
46 0
47 ; j < src.length; j++) {
48
49
50
51
52
53
54 Entry e = src[j];
55
56
57
58
59
60
61 if
62 (e !=
63 null
64 ) {
65
66
67
68
69
70
71 src[j] =
72 null
73 ;
74
75
76
77
78
79
80 do
81 {
82
83
84
85
86
87
88 Entry next = e.next;
89
90
91
92
93
94
95 int
96 i = indexFor(e.hash, newCapacity);
97
98
99
100
101
102
103 e.next = newTable[i];
104
105
106
107
108
109
110 newTable[i] = e;
111
112
113
114
115
116
117 e = next;
118
119
120
121
122
123
124 }
125 while
126 (e !=
127 null
128 );
129
130
131
132
133
134
135 }
136
137
138
139
140
141
142 }
143
144
145
146
147
148 }
149
问题最终就出现在HashMap中transfer方法的这个while循环上，这个方法在HashMap扩容时调用，详细分析见：
http://blog.sina.com.cn/s/blog_56146a210100owft.html
在Lock-Free世界里，最简单也最普遍的一个通用原语是CAS(Compare and Swap)操作。支持并发的现代的处理器都提供了这个原语的硬件实现。CAS原语负责比较某个内存地址处的内容与一个期望值，如果比较成功则将该内存地址处的内容替换为一个新值。这整个操作是原子的。
这里有对无锁并发编程的介绍：http://www.cnblogs.com/lucifer1982/archive/2008/04/16/1154727.html
如果站在语言层面之上，仅从设计的层面看，可以免锁的思路至少包括：
1、单线程来主导行为，多线程池化操作避开状态变量。
比如在一个WEB应用中，每一个Action都可以给相应的用户线程分配一个实例，线程之间互不干扰；但是到了业务逻辑Service内，避开Service状态变量的使用，减少了开发人员对并发编程的关注。
2、函数式编码。
函数式编码是最天然的和最高效的免锁方式，如果你对函数式编码还不了解，请参看这篇文章。
3、资源局部复制、异步处理。
总所周知对资源的争夺是造成锁的一个重要原因，在很多情况下，资源只能有一份，但是对使用资源的每个线程来说，都可以看到属于它自己的一份（这一份并非是真正的资源，很可能只是一个缓冲区，每个线程使用它自己的一个缓冲区，到一定程度时将缓冲区的数据处理到唯一资源中，这就减少了需要加锁对线程的影响），无需考虑并发地去使用。
4、不变对象。
不妨参考ConcurrentHashMap的实现，其中的节点是不变的。对象不变性是保证线程安全的重要方式之一。
Java的锁操作和锁优化：
锁自旋
线程要进入阻塞状态，肯定需要调用操作系统的函数来完成从用户态进入内核态的过程，这一步通常是性能低下的。
那么在遇到锁的争用时，或许等待线程可以不那么着急进入阻塞状态，而是等一等，看看锁是不是马上就释放了，这就是锁自旋。锁自旋在多处理器上有重要价值。
当然锁自旋也带来了一些问题，比如如何判断自旋周期，如何确定自旋锁的个数，如何处理线程优先级差异等。
锁偏向
锁偏向是JDK1.6引入的，主要为了解决在没有竞争情况下锁的性能问题。
锁都是可重入的，在已经获得锁的情况下，该线程可以多次锁住该对象，但是每次执行这样的操作会因为CAS（CPU的Compare-And-Swap指令）操作而造成一些开销，为了减少这种开销，这个锁会偏向于第一个获得它的线程，如果在接下来的执行过程中，该锁没有被其他的线程获取，则持有偏向锁的线程将永远不需要再进行同步。
锁消除
（JDK1.6）锁削除是指虚拟机即时编译器在运行时，对一些代码上要求同步，但是被检测到不可能存在共享数据竞争的锁进行削除。
锁膨胀
（JDK1.6）和数据库中的锁升级有些相似，多个或多次调用粒度太小的锁，进行加锁解锁的消耗，反而还不如一次大粒度的锁调用来得高效，因此JVM可将锁的范围优化到更大的区域。
轻量级锁
（JDK1.6）轻量级锁能提升程序同步性能的依据是“对于绝大部分的锁，在整个同步周期内都是不存在竞争的”，这是一个经验数据。轻量级锁在当前线程的栈帧中建立一个名为锁记录的空间，用于存储锁对象目前的指向和状态。如果没有竞争，轻量级锁使用CAS操作避免了使用互斥量的开销，但如果存在锁竞争，除了互斥量的开销外，还额外发生了CAS操作，因此在有竞争的情况下，轻量级锁会比传统的重量级锁更慢。
———————————————————————————————————-
2012年11月16日：
今天看到一个C#实现的读共享写互斥的代码：
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
2 ReaderAndWriter
3
4
5
6
7
8 {
9
10
11
12
13
14
15 private
16 static
17 Mutex mut =
18 new
19 Mutex();
20 //用于保护读者数量的互斥信号量
21
22
23
24
25
26
27 private
28 static
29 Mutex rw =
30 new
31 Mutex();
32 //保证读者写者互斥的信号量
33
34
35
36
37
38
39
40
41
42
43
44
45 static
46 int
47 count = 0;
48 //读者数量
49
50
51
52
53
54
55
56
57
58
59
60
61 private
62 static
63 void
64 Reader()
65
66
67
68
69
70
71 {
72
73
74
75
76
77
78 mut.WaitOne();
79
80
81
82
83
84
85 if
86 (count == 0)
87
88
89
90
91
92
93 {
94
95
96
97
98
99
100 rw.WaitOne();
101
102
103
104
105
106
107 }
108
109
110
111
112
113
114 count++;
115
116
117
118
119
120
121 mut.ReleaseMutex();
122
123
124
125
126
127
128
129
130
131
132
133
134 Thread.Sleep(
135 new
136 Random().Next(2000));
137 //读取耗时1S
138
139
140
141
142
143
144 Console.WriteLine(
145 "读取完毕"
146 );
147
148
149
150
151
152
153
154
155
156
157
158
159 mut.WaitOne();
160
161
162
163
164
165
166 count--;
167
168
169
170
171
172
173 mut.ReleaseMutex();
174
175
176
177
178
179
180 if
181 (count == 0)
182
183
184
185
186
187
188 {
189
190
191
192
193
194
195 rw.ReleaseMutex();
196
197
198
199
200
201
202 }
203
204
205
206
207
208
209
210
211
212
213
214
215 }
216
217
218
219
220
221
222 private
223 static
224 void
225 writer()
226
227
228
229
230
231
232 {
233
234
235
236
237
238
239 rw.WaitOne();
240
241
242
243
244
245
246 Console.WriteLine(
247 "写入数据"
248 );
249
250
251
252
253
254
255 rw.ReleaseMutex();
256
257
258
259
260
261
262
263
264
265
266
267
268 }
269
270
271
272
273
274 }
275
这种方式是写线程的逻辑比较简单的一种实现，只管获取到rw锁（用于表示互斥锁），而读线程在每次进行读区域前，通过mut锁的机制保证至少有一个互斥锁被读线程所占据（这样写线程就没法并行操作了），然后再真正开始读的时候放开mut锁，让其它读线程可以并发地进行读操作。其中的count用于表示当前读者的个数，当count降为0的时候，进入的读线程必须去获取一个写锁，以保证有读者的时候，写锁一定被某个读者占有。
