-
Notifications
You must be signed in to change notification settings - Fork 1
Expand file tree
/
Copy path1a8406e8.html
More file actions
494 lines (385 loc) · 77.8 KB
/
1a8406e8.html
File metadata and controls
494 lines (385 loc) · 77.8 KB
1
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
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
<!DOCTYPE html>
<html lang="zh-CN">
<head>
<meta charset="UTF-8">
<meta name="viewport" content="width=device-width">
<meta name="theme-color" content="#222"><meta name="generator" content="Hexo 6.3.0">
<link rel="apple-touch-icon" sizes="180x180" href="/images/apple-touch-icon-next.png">
<link rel="icon" type="image/png" sizes="32x32" href="/images/favicon.png">
<link rel="icon" type="image/png" sizes="16x16" href="/images/favicon.png">
<link rel="mask-icon" href="/images/logo.svg" color="#222">
<link rel="stylesheet" href="/css/main.css">
<link rel="stylesheet" href="https://cdnjs.cloudflare.com/ajax/libs/font-awesome/6.4.0/css/all.min.css" integrity="sha256-HtsXJanqjKTc8vVQjO4YMhiqFoXkfBsjBWcX91T1jr8=" crossorigin="anonymous">
<link rel="stylesheet" href="https://cdnjs.cloudflare.com/ajax/libs/animate.css/3.1.1/animate.min.css" integrity="sha256-PR7ttpcvz8qrF57fur/yAx1qXMFJeJFiA6pSzWi0OIE=" crossorigin="anonymous">
<script class="next-config" data-name="main" type="application/json">{"hostname":"tallate.github.io","root":"/","images":"/images","scheme":"Gemini","darkmode":false,"version":"8.18.0","exturl":false,"sidebar":{"position":"left","display":"post","padding":18,"offset":12},"copycode":{"enable":false,"style":null},"fold":{"enable":false,"height":500},"bookmark":{"enable":false,"color":"#222","save":"auto"},"mediumzoom":false,"lazyload":false,"pangu":false,"comments":{"style":"tabs","active":null,"storage":true,"lazyload":false,"nav":null},"stickytabs":false,"motion":{"enable":true,"async":false,"transition":{"menu_item":"fadeInDown","post_block":"fadeIn","post_header":"fadeInDown","post_body":"fadeInDown","coll_header":"fadeInLeft","sidebar":"fadeInUp"}},"prism":false,"i18n":{"placeholder":"搜索...","empty":"没有找到任何搜索结果：${query}","hits_time":"找到 ${hits} 个搜索结果（用时 ${time} 毫秒）","hits":"找到 ${hits} 个搜索结果"}}</script><script src="/js/config.js"></script>
<meta name="description" content="无锁栈Treiber Stack无锁列表CopyOnWriteArrayListCopyOnWriteArrayList 是一个线程安全的 ArrayList，对其进行的修改操作和元素迭代操作都是在底层创建一个拷贝的数组（快照）上进行的，也就是写时拷贝策略。CopyOnWriteArrayList 适合读多写少的场景，但如果应用在写操作频繁的场景下反而会降低性能。 lock：保证写操作时的">
<meta property="og:type" content="article">
<meta property="og:title" content="并发和并发安全容器">
<meta property="og:url" content="https://tallate.github.io/1a8406e8.html">
<meta property="og:site_name" content="Tallate">
<meta property="og:description" content="无锁栈Treiber Stack无锁列表CopyOnWriteArrayListCopyOnWriteArrayList 是一个线程安全的 ArrayList，对其进行的修改操作和元素迭代操作都是在底层创建一个拷贝的数组（快照）上进行的，也就是写时拷贝策略。CopyOnWriteArrayList 适合读多写少的场景，但如果应用在写操作频繁的场景下反而会降低性能。 lock：保证写操作时的">
<meta property="og:locale" content="zh_CN">
<meta property="og:image" content="https://tallate.github.io/imgs/%E5%B9%B6%E5%8F%91/CopyOnWriteArrayList%E7%B1%BB%E5%9B%BE.png">
<meta property="og:image" content="https://tallate.github.io/imgs/%E5%B9%B6%E5%8F%91/ConcurrentLinkedQueue%E7%B1%BB%E5%9B%BE.png">
<meta property="og:image" content="https://tallate.github.io/imgs/%E5%B9%B6%E5%8F%91/ConcurrentLinkedQueue%E7%9A%84%E9%98%9F%E5%88%97%E7%BB%93%E6%9E%84.png">
<meta property="og:image" content="https://tallate.github.io/imgs/%E5%B9%B6%E5%8F%91/ConcurrentLinkedQueue%E6%8F%92%E5%85%A51.png">
<meta property="og:image" content="https://tallate.github.io/imgs/%E5%B9%B6%E5%8F%91/ConcurrentLinkedQueue%E6%8F%92%E5%85%A52.png">
<meta property="og:image" content="https://tallate.github.io/imgs/%E5%B9%B6%E5%8F%91/ConcurrentLinkedQueue%E6%8F%92%E5%85%A53.png">
<meta property="og:image" content="https://tallate.github.io/imgs/%E5%B9%B6%E5%8F%91/ConcurrentLinkedQueue%E5%87%BA%E9%98%9F1.png">
<meta property="og:image" content="https://tallate.github.io/imgs/%E5%B9%B6%E5%8F%91/ConcurrentLinkedQueue%E6%8F%92%E5%85%A53.png">
<meta property="og:image" content="https://tallate.github.io/imgs/%E5%B9%B6%E5%8F%91/ConcurrentLinkedQueue%E5%87%BA%E9%98%9F2.png">
<meta property="og:image" content="https://tallate.github.io/imgs/%E5%B9%B6%E5%8F%91/ConcurrentLinkedQueue%E5%87%BA%E9%98%9F3.png">
<meta property="og:image" content="https://tallate.github.io/imgs/%E5%B9%B6%E5%8F%91/ConcurrentLinkedQueue%E5%87%BA%E9%98%9F4.png">
<meta property="og:image" content="https://tallate.github.io/imgs/%E5%B9%B6%E5%8F%91/ConcurrentHashMap%E7%BB%93%E6%9E%84.png">
<meta property="og:image" content="https://tallate.github.io/imgs/%E5%B9%B6%E5%8F%91/ConcurrentHashMap%E7%9A%84put%E6%93%8D%E4%BD%9C.png">
<meta property="article:published_time" content="2019-09-12T14:12:49.000Z">
<meta property="article:modified_time" content="2025-07-06T17:56:20.870Z">
<meta property="article:author" content="tallate">
<meta property="article:tag" content="并发">
<meta name="twitter:card" content="summary">
<meta name="twitter:image" content="https://tallate.github.io/imgs/%E5%B9%B6%E5%8F%91/CopyOnWriteArrayList%E7%B1%BB%E5%9B%BE.png">
<link rel="canonical" href="https://tallate.github.io/1a8406e8.html">
<script class="next-config" data-name="page" type="application/json">{"sidebar":"","isHome":false,"isPost":true,"lang":"zh-CN","comments":true,"permalink":"https://tallate.github.io/1a8406e8.html","path":"/1a8406e8.html","title":"并发和并发安全容器"}</script>
<script class="next-config" data-name="calendar" type="application/json">""</script>
<title>并发和并发安全容器 | Tallate</title>
<noscript>
<link rel="stylesheet" href="/css/noscript.css">
</noscript>
</head>
<body itemscope itemtype="http://schema.org/WebPage" class="use-motion">
<div class="headband"></div>
<main class="main">
<div class="column">
<header class="header" itemscope itemtype="http://schema.org/WPHeader"><div class="site-brand-container">
<div class="site-nav-toggle">
<div class="toggle" aria-label="切换导航栏" role="button">
<span class="toggle-line"></span>
<span class="toggle-line"></span>
<span class="toggle-line"></span>
</div>
</div>
<div class="site-meta">
<a href="/" class="brand" rel="start">
<i class="logo-line"></i>
<p class="site-title">Tallate</p>
<i class="logo-line"></i>
</a>
<p class="site-subtitle" itemprop="description">该吃吃该喝喝 啥事别往心里搁</p>
</div>
<div class="site-nav-right">
<div class="toggle popup-trigger" aria-label="搜索" role="button">
<i class="fa fa-search fa-fw fa-lg"></i>
</div>
</div>
</div>
<nav class="site-nav">
<ul class="main-menu menu"><li class="menu-item menu-item-home"><a href="/" rel="section"><i class="home fa-fw"></i>首页</a></li><li class="menu-item menu-item-about"><a href="/about/" rel="section"><i class="user fa-fw"></i>关于</a></li><li class="menu-item menu-item-tags"><a href="/tags/" rel="section"><i class="tags fa-fw"></i>标签<span class="badge">84</span></a></li><li class="menu-item menu-item-categories"><a href="/categories/" rel="section"><i class="th fa-fw"></i>分类<span class="badge">25</span></a></li><li class="menu-item menu-item-archives"><a href="/archives/" rel="section"><i class="archive fa-fw"></i>归档<span class="badge">192</span></a></li>
<li class="menu-item menu-item-search">
<a role="button" class="popup-trigger"><i class="fa fa-search fa-fw"></i>搜索
</a>
</li>
</ul>
</nav>
<div class="search-pop-overlay">
<div class="popup search-popup"><div class="search-header">
<span class="search-icon">
<i class="fa fa-search"></i>
</span>
<div class="search-input-container">
<input autocomplete="off" autocapitalize="off" maxlength="80"
placeholder="搜索..." spellcheck="false"
type="search" class="search-input">
</div>
<span class="popup-btn-close" role="button">
<i class="fa fa-times-circle"></i>
</span>
</div>
<div class="search-result-container no-result">
<div class="search-result-icon">
<i class="fa fa-spinner fa-pulse fa-5x"></i>
</div>
</div>
</div>
</div>
</header>
<aside class="sidebar">
<div class="sidebar-inner sidebar-nav-active sidebar-toc-active">
<ul class="sidebar-nav">
<li class="sidebar-nav-toc">
文章目录
</li>
<li class="sidebar-nav-overview">
站点概览
</li>
</ul>
<div class="sidebar-panel-container">
<!--noindex-->
<div class="post-toc-wrap sidebar-panel">
<div class="post-toc animated"><ol class="nav"><li class="nav-item nav-level-1"><a class="nav-link" href="#%E6%97%A0%E9%94%81%E6%A0%88"><span class="nav-number">1.</span> <span class="nav-text">无锁栈</span></a><ol class="nav-child"><li class="nav-item nav-level-2"><a class="nav-link" href="#Treiber-Stack"><span class="nav-number">1.1.</span> <span class="nav-text">Treiber Stack</span></a></li></ol></li><li class="nav-item nav-level-1"><a class="nav-link" href="#%E6%97%A0%E9%94%81%E5%88%97%E8%A1%A8"><span class="nav-number">2.</span> <span class="nav-text">无锁列表</span></a><ol class="nav-child"><li class="nav-item nav-level-2"><a class="nav-link" href="#CopyOnWriteArrayList"><span class="nav-number">2.1.</span> <span class="nav-text">CopyOnWriteArrayList</span></a><ol class="nav-child"><li class="nav-item nav-level-3"><a class="nav-link" href="#add-E-e"><span class="nav-number">2.1.1.</span> <span class="nav-text">add(E e)</span></a></li><li class="nav-item nav-level-3"><a class="nav-link" href="#get-int-index"><span class="nav-number">2.1.2.</span> <span class="nav-text">get(int index)</span></a></li><li class="nav-item nav-level-3"><a class="nav-link" href="#set-int-index-E-element"><span class="nav-number">2.1.3.</span> <span class="nav-text">set(int index, E element)</span></a></li><li class="nav-item nav-level-3"><a class="nav-link" href="#remove-int-index"><span class="nav-number">2.1.4.</span> <span class="nav-text">remove(int index)</span></a></li><li class="nav-item nav-level-3"><a class="nav-link" href="#remove-Object-o"><span class="nav-number">2.1.5.</span> <span class="nav-text">remove(Object o)</span></a></li><li class="nav-item nav-level-3"><a class="nav-link" href="#remove-Object-o-Object-snapshot-int-index"><span class="nav-number">2.1.6.</span> <span class="nav-text">remove(Object o, Object[] snapshot, int index)</span></a></li><li class="nav-item nav-level-3"><a class="nav-link" href="#iterator"><span class="nav-number">2.1.7.</span> <span class="nav-text">iterator</span></a></li></ol></li></ol></li><li class="nav-item nav-level-1"><a class="nav-link" href="#%E6%97%A0%E9%94%81%E9%98%9F%E5%88%97"><span class="nav-number">3.</span> <span class="nav-text">无锁队列</span></a><ol class="nav-child"><li class="nav-item nav-level-2"><a class="nav-link" href="#ConcurrentLinkedQueue"><span class="nav-number">3.1.</span> <span class="nav-text">ConcurrentLinkedQueue</span></a><ol class="nav-child"><li class="nav-item nav-level-3"><a class="nav-link" href="#%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84"><span class="nav-number">3.1.1.</span> <span class="nav-text">数据结构</span></a></li><li class="nav-item nav-level-3"><a class="nav-link" href="#%E5%85%A5%E9%98%9F-offer"><span class="nav-number">3.1.2.</span> <span class="nav-text">入队 - offer</span></a></li><li class="nav-item nav-level-3"><a class="nav-link" href="#%E5%87%BA%E9%98%9F-poll"><span class="nav-number">3.1.3.</span> <span class="nav-text">出队 - poll</span></a></li></ol></li><li class="nav-item nav-level-2"><a class="nav-link" href="#ArrayBlockingQueue"><span class="nav-number">3.2.</span> <span class="nav-text">ArrayBlockingQueue</span></a></li><li class="nav-item nav-level-2"><a class="nav-link" href="#LinkedBlockingQueue"><span class="nav-number">3.3.</span> <span class="nav-text">LinkedBlockingQueue</span></a></li><li class="nav-item nav-level-2"><a class="nav-link" href="#PriorityBlockingQueue"><span class="nav-number">3.4.</span> <span class="nav-text">PriorityBlockingQueue</span></a></li><li class="nav-item nav-level-2"><a class="nav-link" href="#SynchronousQueue"><span class="nav-number">3.5.</span> <span class="nav-text">SynchronousQueue</span></a></li><li class="nav-item nav-level-2"><a class="nav-link" href="#LinkedTransferQueue"><span class="nav-number">3.6.</span> <span class="nav-text">LinkedTransferQueue</span></a></li><li class="nav-item nav-level-2"><a class="nav-link" href="#%E9%98%9F%E5%88%97%E6%AF%94%E8%BE%83"><span class="nav-number">3.7.</span> <span class="nav-text">队列比较</span></a></li><li class="nav-item nav-level-2"><a class="nav-link" href="#Disruptor"><span class="nav-number">3.8.</span> <span class="nav-text">Disruptor</span></a></li><li class="nav-item nav-level-2"><a class="nav-link" href="#Logback-%E6%A1%86%E6%9E%B6%E4%B8%AD%E5%BC%82%E6%AD%A5%E6%97%A5%E5%BF%97%E6%89%93%E5%8D%B0%E4%B8%AD-ArrayBlockingQueue-%E7%9A%84%E4%BD%BF%E7%94%A8"><span class="nav-number">3.9.</span> <span class="nav-text">Logback 框架中异步日志打印中 ArrayBlockingQueue 的使用</span></a></li></ol></li><li class="nav-item nav-level-1"><a class="nav-link" href="#%E5%B9%B6%E5%8F%91%E5%AE%89%E5%85%A8-Map"><span class="nav-number">4.</span> <span class="nav-text">并发安全 Map</span></a><ol class="nav-child"><li class="nav-item nav-level-2"><a class="nav-link" href="#ConcurrentHashMap"><span class="nav-number">4.1.</span> <span class="nav-text">ConcurrentHashMap</span></a><ol class="nav-child"><li class="nav-item nav-level-3"><a class="nav-link" href="#get"><span class="nav-number">4.1.1.</span> <span class="nav-text">get</span></a></li><li class="nav-item nav-level-3"><a class="nav-link" href="#put"><span class="nav-number">4.1.2.</span> <span class="nav-text">put</span></a></li><li class="nav-item nav-level-3"><a class="nav-link" href="#rehash"><span class="nav-number">4.1.3.</span> <span class="nav-text">rehash</span></a></li><li class="nav-item nav-level-3"><a class="nav-link" href="#size"><span class="nav-number">4.1.4.</span> <span class="nav-text">size</span></a></li></ol></li></ol></li><li class="nav-item nav-level-1"><a class="nav-link" href="#QA"><span class="nav-number">5.</span> <span class="nav-text">QA</span></a></li><li class="nav-item nav-level-1"><a class="nav-link" href="#%E5%8F%82%E8%80%83"><span class="nav-number">6.</span> <span class="nav-text">参考</span></a></li></ol></div>
</div>
<!--/noindex-->
<div class="site-overview-wrap sidebar-panel">
<div class="site-author animated" itemprop="author" itemscope itemtype="http://schema.org/Person">
<p class="site-author-name" itemprop="name">tallate</p>
<div class="site-description" itemprop="description"></div>
</div>
<div class="site-state-wrap animated">
<nav class="site-state">
<div class="site-state-item site-state-posts">
<a href="/archives/">
<span class="site-state-item-count">192</span>
<span class="site-state-item-name">日志</span>
</a>
</div>
<div class="site-state-item site-state-categories">
<a href="/categories/">
<span class="site-state-item-count">25</span>
<span class="site-state-item-name">分类</span></a>
</div>
<div class="site-state-item site-state-tags">
<a href="/tags/">
<span class="site-state-item-count">84</span>
<span class="site-state-item-name">标签</span></a>
</div>
</nav>
</div>
</div>
</div>
</div>
</aside>
</div>
<div class="main-inner post posts-expand">
<div class="post-block">
<article itemscope itemtype="http://schema.org/Article" class="post-content" lang="zh-CN">
<link itemprop="mainEntityOfPage" href="https://tallate.github.io/1a8406e8.html">
<span hidden itemprop="author" itemscope itemtype="http://schema.org/Person">
<meta itemprop="image" content="/images/avatar.gif">
<meta itemprop="name" content="tallate">
</span>
<span hidden itemprop="publisher" itemscope itemtype="http://schema.org/Organization">
<meta itemprop="name" content="Tallate">
<meta itemprop="description" content="">
</span>
<span hidden itemprop="post" itemscope itemtype="http://schema.org/CreativeWork">
<meta itemprop="name" content="并发和并发安全容器 | Tallate">
<meta itemprop="description" content="">
</span>
<header class="post-header">
<h1 class="post-title" itemprop="name headline">
并发和并发安全容器
</h1>
<div class="post-meta-container">
<div class="post-meta">
<span class="post-meta-item">
<span class="post-meta-item-icon">
<i class="far fa-calendar"></i>
</span>
<span class="post-meta-item-text">发表于</span>
<time title="创建时间：2019-09-12 22:12:49" itemprop="dateCreated datePublished" datetime="2019-09-12T22:12:49+08:00">2019-09-12</time>
</span>
<span class="post-meta-item">
<span class="post-meta-item-icon">
<i class="far fa-calendar-check"></i>
</span>
<span class="post-meta-item-text">更新于</span>
<time title="修改时间：2025-07-07 01:56:20" itemprop="dateModified" datetime="2025-07-07T01:56:20+08:00">2025-07-07</time>
</span>
<span class="post-meta-item">
<span class="post-meta-item-icon">
<i class="far fa-folder"></i>
</span>
<span class="post-meta-item-text">分类于</span>
<span itemprop="about" itemscope itemtype="http://schema.org/Thing">
<a href="/categories/Java/" itemprop="url" rel="index"><span itemprop="name">Java</span></a>
</span>
</span>
</div>
</div>
</header>
<div class="post-body" itemprop="articleBody"><span id="more"></span>
<h1 id="无锁栈"><a href="#无锁栈" class="headerlink" title="无锁栈"></a>无锁栈</h1><h2 id="Treiber-Stack"><a href="#Treiber-Stack" class="headerlink" title="Treiber Stack"></a>Treiber Stack</h2><h1 id="无锁列表"><a href="#无锁列表" class="headerlink" title="无锁列表"></a>无锁列表</h1><h2 id="CopyOnWriteArrayList"><a href="#CopyOnWriteArrayList" class="headerlink" title="CopyOnWriteArrayList"></a>CopyOnWriteArrayList</h2><p>CopyOnWriteArrayList 是一个线程安全的 ArrayList，对其进行的修改操作和元素迭代操作都是在底层创建一个拷贝的数组（快照）上进行的，也就是写时拷贝策略。CopyOnWriteArrayList 适合读多写少的场景，但如果应用在写操作频繁的场景下反而会降低性能。<br><img src="/imgs/%E5%B9%B6%E5%8F%91/CopyOnWriteArrayList%E7%B1%BB%E5%9B%BE.png" alt="CopyOnWriteArrayList类图" title="CopyOnWriteArrayList类图"></p>
<ul>
<li>lock：保证写操作时的并发安全；</li>
</ul>
<h3 id="add-E-e"><a href="#add-E-e" class="headerlink" title="add(E e)"></a>add(E e)</h3><p>添加操作拷贝了份快照，在快照上添加元素，最后替代原数组</p>
<figure class="highlight plaintext"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br></pre></td><td class="code"><pre><span class="line">public boolean add(E e) {</span><br><span class="line"></span><br><span class="line"> // 加独占锁</span><br><span class="line"> final ReentrantLock lock = this.lock;</span><br><span class="line"> lock.lock();</span><br><span class="line"> try {</span><br><span class="line"> // 获取array</span><br><span class="line"> Object[] elements = getArray();</span><br><span class="line"></span><br><span class="line"> // 拷贝array到新数组，添加元素到新数组</span><br><span class="line"> // 新数组长度是原数组长度+1，可见CopyOnWriteArrayList是无界的</span><br><span class="line"> int len = elements.length;</span><br><span class="line"> Object[] newElements = Arrays.copyOf(elements, len + 1);</span><br><span class="line"> newElements[len] = e;</span><br><span class="line"></span><br><span class="line"> // 使用新数组替换添加前的数组</span><br><span class="line"> setArray(newElements);</span><br><span class="line"> return true;</span><br><span class="line"> } finally {</span><br><span class="line"> // 释放独占锁</span><br><span class="line"> lock.unlock();</span><br><span class="line"> }</span><br><span class="line">}</span><br></pre></td></tr></table></figure>
<h3 id="get-int-index"><a href="#get-int-index" class="headerlink" title="get(int index)"></a>get(int index)</h3><p>get 操作获取下标处的元素，实际上 get 可以被分解为以下两个步骤：</p>
<ol>
<li>获取 array 的引用；</li>
<li>通过下标访问 array 指定位置的元素。</li>
</ol>
<p>整个过程并没有加锁，如果在访问期间有另一个线程删除了某个元素，实际上因为修改操作是发生在原数组的一个快照上的，get 操作仍然获取的是原数组上的元素，因此不会发生类似数组越界的问题。但同时也不可避免这个过程带来的<strong>弱一致性</strong>，因为元素事实上已经被删除了却仍然可以被访问到。</p>
<h3 id="set-int-index-E-element"><a href="#set-int-index-E-element" class="headerlink" title="set(int index, E element)"></a>set(int index, E element)</h3><p>修改 list 中指定元素的值。</p>
<ul>
<li>如果指定位置的元素不存在则抛出 IndexOutOfBoundsException 异常；</li>
<li>如果指定位置元素与新值不一致，则创建新数组、在新数组上修改，最后设置新数组到 array（COW）。</li>
<li>即使没有变化，也还是需要重新设置一次 array，这主要是因为 array 本身是 volatile 的，set 方法应当提供 volatile 的语义。</li>
</ul>
<h3 id="remove-int-index"><a href="#remove-int-index" class="headerlink" title="remove(int index)"></a>remove(int index)</h3><figure class="highlight plaintext"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br><span class="line">31</span><br><span class="line">32</span><br><span class="line">33</span><br></pre></td><td class="code"><pre><span class="line">public E remove(int index) {</span><br><span class="line"></span><br><span class="line"> //获取独占锁</span><br><span class="line"> final ReentrantLock lock = this.lock;</span><br><span class="line"> lock.lock();</span><br><span class="line"> try {</span><br><span class="line"></span><br><span class="line"> //获取数组</span><br><span class="line"> Object[] elements = getArray();</span><br><span class="line"> int len = elements.length;</span><br><span class="line"></span><br><span class="line"> //获取指定元素</span><br><span class="line"> E oldValue = get(elements, index);</span><br><span class="line"> int numMoved = len - index - 1;</span><br><span class="line"></span><br><span class="line"> //如果要删除的是最后一个元素</span><br><span class="line"> if (numMoved == 0)</span><br><span class="line"> setArray(Arrays.copyOf(elements, len - 1));</span><br><span class="line"> else {</span><br><span class="line"> //分两次拷贝除删除后的元素到新数组</span><br><span class="line"> Object[] newElements = new Object[len - 1];</span><br><span class="line"> System.arraycopy(elements, 0, newElements, 0, index);</span><br><span class="line"> System.arraycopy(elements, index + 1, newElements, index,</span><br><span class="line"> numMoved);</span><br><span class="line"> //使用新数组代替老的 </span><br><span class="line"> setArray(newElements);</span><br><span class="line"> }</span><br><span class="line"> return oldValue;</span><br><span class="line"> } finally {</span><br><span class="line"> //释放锁</span><br><span class="line"> lock.unlock();</span><br><span class="line"> }</span><br><span class="line">}</span><br></pre></td></tr></table></figure>
<h3 id="remove-Object-o"><a href="#remove-Object-o" class="headerlink" title="remove(Object o)"></a>remove(Object o)</h3><h3 id="remove-Object-o-Object-snapshot-int-index"><a href="#remove-Object-o-Object-snapshot-int-index" class="headerlink" title="remove(Object o, Object[] snapshot, int index)"></a>remove(Object o, Object[] snapshot, int index)</h3><h3 id="iterator"><a href="#iterator" class="headerlink" title="iterator"></a>iterator</h3><p>CopyOnWriteArrayList 中的 iterator 是弱一致性的，其他线程的修改操作对 iterator 不可见的。</p>
<figure class="highlight plaintext"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br></pre></td><td class="code"><pre><span class="line">public Iterator<E> iterator() {</span><br><span class="line"> return new COWIterator<E>(getArray(), 0);</span><br><span class="line">}</span><br><span class="line"></span><br><span class="line">static final class COWIterator<E> implements ListIterator<E> {</span><br><span class="line"> //array的快照版本</span><br><span class="line"> private final Object[] snapshot;</span><br><span class="line"></span><br><span class="line"> //数组下标</span><br><span class="line"> private int cursor;</span><br><span class="line"></span><br><span class="line"> //构造函数</span><br><span class="line"> private COWIterator(Object[] elements, int initialCursor) {</span><br><span class="line"> cursor = initialCursor;</span><br><span class="line"> snapshot = elements;</span><br><span class="line"> }</span><br><span class="line"></span><br><span class="line"> //是否遍历结束</span><br><span class="line"> public boolean hasNext() {</span><br><span class="line"> return cursor < snapshot.length;</span><br><span class="line"> }</span><br><span class="line"></span><br><span class="line"> //获取元素</span><br><span class="line"> public E next() {</span><br><span class="line"> if (! hasNext())</span><br><span class="line"> throw new NoSuchElementException();</span><br><span class="line"> return (E) snapshot[cursor++];</span><br><span class="line"> }</span><br></pre></td></tr></table></figure>
<ul>
<li>如果在该线程使用返回的迭代器遍历元素的过程中，其它线程没有对 list 进行增删改，那么 snapshot 本身就是 list 的 array，因为它们是引用关系。</li>
<li>如果在遍历期间存在其他线程对 list 的增删改操作，那么 snapshot 会成为原 array 的快照，此时其他线程对 list 进行的增删改是不可见的，因为它们操作的是两个不同的数组。</li>
</ul>
<h1 id="无锁队列"><a href="#无锁队列" class="headerlink" title="无锁队列"></a>无锁队列</h1><h2 id="ConcurrentLinkedQueue"><a href="#ConcurrentLinkedQueue" class="headerlink" title="ConcurrentLinkedQueue"></a>ConcurrentLinkedQueue</h2><ul>
<li>线程安全</li>
<li>无界</li>
<li>非阻塞</li>
</ul>
<h3 id="数据结构"><a href="#数据结构" class="headerlink" title="数据结构"></a>数据结构</h3><p><img src="/imgs/%E5%B9%B6%E5%8F%91/ConcurrentLinkedQueue%E7%B1%BB%E5%9B%BE.png" alt="ConcurrentLinkedQueue类图" title="ConcurrentLinkedQueue类图"></p>
<ul>
<li>底层队列使用单向链表实现。</li>
<li>两个volatile的Node节点（head和tail）分别存放队列的首尾节点，从下面无参构造函数可知默认头尾节点都是指向 item 为 null 的哨兵节点。 <figure class="highlight plaintext"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br></pre></td><td class="code"><pre><span class="line">public ConcurrentLinkedQueue() {</span><br><span class="line"> head = tail = new Node(null);</span><br><span class="line">}</span><br></pre></td></tr></table></figure></li>
<li>Node节点内部为一个volatile修饰的变量item用来存放节点的值，next用来存放链表的下一个节点，从而链接成一个单向无界链表，如下图所示：<br><img src="/imgs/%E5%B9%B6%E5%8F%91/ConcurrentLinkedQueue%E7%9A%84%E9%98%9F%E5%88%97%E7%BB%93%E6%9E%84.png" alt="ConcurrentLinkedQueue的队列结构" title="ConcurrentLinkedQueue的队列结构"></li>
<li>入队和出队操作使用CAS来实现线程安全。</li>
</ul>
<h3 id="入队-offer"><a href="#入队-offer" class="headerlink" title="入队 - offer"></a>入队 - offer</h3><p>offer操作在队列末尾添加一个元素：</p>
<ul>
<li>如果传入的是null，抛出NPE，表明ConcurrentLinkedQueue是不允许插入null值的；</li>
<li>其他情况下插入任何元素都会返回true，因为该队列是无界队列；</li>
<li>使用CAS操作实现线程安全<figure class="highlight plaintext"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br></pre></td><td class="code"><pre><span class="line">public boolean offer(E e) {</span><br><span class="line"> checkNotNull(e);</span><br><span class="line"> final Node<E> newNode = new Node<E>(e);</span><br><span class="line"> // 从尾节点进行插入</span><br><span class="line"> for (Node<E> t = tail, p = t;;) {</span><br><span class="line"> Node<E> q = p.next;</span><br><span class="line"> </span><br><span class="line"> // 如果q==null说明p是尾节点，则执行插入</span><br><span class="line"> // （1）</span><br><span class="line"> if (q == null) {</span><br><span class="line"> // 使用CAS设置p节点的next节点</span><br><span class="line"> if (p.casNext(null, newNode)) {</span><br><span class="line"> // cas成功，则说明新增节点已经被放入链表，然后设置当前尾节点</span><br><span class="line"> if (p != t)</span><br><span class="line"> casTail(t, newNode); // Failure is OK.</span><br><span class="line"> return true;</span><br><span class="line"> }</span><br><span class="line"> }</span><br><span class="line"> // （2）</span><br><span class="line"> else if (p == q)</span><br><span class="line"> // 多线程操作时候，由于poll操作移除元素后有可能会把head变为自引用，然后head的next变为新head，所以这里需要</span><br><span class="line"> // 重新找新的head，因为新的head后面的节点才是正常的节点。</span><br><span class="line"> p = (t != (t = tail)) ? t : head;</span><br><span class="line"> // （3）</span><br><span class="line"> else</span><br><span class="line"> // 寻找尾节点</span><br><span class="line"> p = (p != t && t != (t = tail)) ? t : q;</span><br><span class="line"> }</span><br><span class="line">}</span><br></pre></td></tr></table></figure>
注意这里的循环体从队列尾部添加元素：</li>
</ul>
<ol>
<li>刚开始队列为空，代码（1）通过CAS替换p的下一个节点；<br>注意有一个哨兵节点null，刚开始队列的head和tail节点都是指向该哨兵节点，因此队列中至少都会有一个节点；</li>
<li>如果多个线程同时执行插入，总会有一个线程CAS时插入失败，这时会进入下一次循环<br><img src="/imgs/%E5%B9%B6%E5%8F%91/ConcurrentLinkedQueue%E6%8F%92%E5%85%A51.png" alt="ConcurrentLinkedQueue插入1" title="ConcurrentLinkedQueue插入1"><br>这时不满足（1）和（2）的条件，在代码（3）处会将q赋值给p<br><img src="/imgs/%E5%B9%B6%E5%8F%91/ConcurrentLinkedQueue%E6%8F%92%E5%85%A52.png" alt="ConcurrentLinkedQueue插入2" title="ConcurrentLinkedQueue插入2"><br>再到下一次循环时q就会移动到null，这时要么正常插入，要么又被别人通过CAS抢了。</li>
<li>代码（2）是在执行poll时可能出现的情况：<br><img src="/imgs/%E5%B9%B6%E5%8F%91/ConcurrentLinkedQueue%E6%8F%92%E5%85%A53.png" alt="ConcurrentLinkedQueue插入3" title="ConcurrentLinkedQueue插入3"><br>此时由于t==tail，所以p被赋值为head，然后继续循环插入元素。</li>
</ol>
<h3 id="出队-poll"><a href="#出队-poll" class="headerlink" title="出队 - poll"></a>出队 - poll</h3><p>poll 操作是在队列头部获取并且移除一个元素，如果队列为空则返回 null。</p>
<figure class="highlight plaintext"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br><span class="line">31</span><br><span class="line">32</span><br><span class="line">33</span><br><span class="line">34</span><br><span class="line">35</span><br></pre></td><td class="code"><pre><span class="line">public E poll() {</span><br><span class="line"> // goto标记</span><br><span class="line"> restartFromHead:</span><br><span class="line"></span><br><span class="line"> // （1）无限循环</span><br><span class="line"> for (;;) {</span><br><span class="line"> for (Node<E> h = head, p = h, q;;) {</span><br><span class="line"> // 获取当前队头节点</span><br><span class="line"> E item = p.item;</span><br><span class="line"></span><br><span class="line"> // （2）当前节点有值则cas变为null</span><br><span class="line"> if (item != null && p.casItem(item, null)) {</span><br><span class="line"> //（6）cas成功标志当前节点以及从链表中移除</span><br><span class="line"> if (p != h) </span><br><span class="line"> updateHead(h, ((q = p.next) != null) ? q : p);</span><br><span class="line"> return item;</span><br><span class="line"> }</span><br><span class="line"> // （3）当前队列为空则返回null</span><br><span class="line"> else if ((q = p.next) == null) {</span><br><span class="line"> updateHead(h, p);</span><br><span class="line"> return null;</span><br><span class="line"> }</span><br><span class="line"> // （4）自引用了，则重新找新的队列头节点</span><br><span class="line"> else if (p == q)</span><br><span class="line"> continue restartFromHead;</span><br><span class="line"> // （5）</span><br><span class="line"> else</span><br><span class="line"> p = q;</span><br><span class="line"> }</span><br><span class="line"> }</span><br><span class="line">}</span><br><span class="line">final void updateHead(Node<E> h, Node<E> p) {</span><br><span class="line"> if (h != p && casHead(h, p))</span><br><span class="line"> h.lazySetNext(h);</span><br><span class="line">}</span><br></pre></td></tr></table></figure>
<ol>
<li>刚开始队列是空的，内层循环代码（3）判断队列为空就直接返回null了；<br>这时updateHead执行时由于h等于p所以没有设置头节点，poll直接返回null。</li>
<li>如果执行到（3）时已经有其他线程调用了offer方法成功添加一个元素到队列末尾，这时q会指向新增元素的节点<br><img src="/imgs/%E5%B9%B6%E5%8F%91/ConcurrentLinkedQueue%E5%87%BA%E9%98%9F1.png" alt="ConcurrentLinkedQueue出队1" title="ConcurrentLinkedQueue出队1"><br>这时会进入（5），令p也指向新q。<br>然后在下一次循环时，进入代码（2），执行<code>p.casItem(item, null)</code>时会通过CAS操作设置头节点的值为null。<br>代码（6）处，此时h指向哨兵节点，而p指向队列头节点，这时将p设置为新的头节点（这时p里的值已经被清掉了是一个空节点）。<br>此时队列的状态为：<br><img src="/imgs/%E5%B9%B6%E5%8F%91/ConcurrentLinkedQueue%E6%8F%92%E5%85%A53.png" alt="ConcurrentLinkedQueue插入3" title="ConcurrentLinkedQueue插入3"><br>这就是之前讲队列offer时的一种特殊情况。</li>
<li>自引用的情况<br>假设线程A已经执行到（2）将第一个节点值置为null，这时又有一个线程B开始执行poll操作，如下图所示：<br><img src="/imgs/%E5%B9%B6%E5%8F%91/ConcurrentLinkedQueue%E5%87%BA%E9%98%9F2.png" alt="ConcurrentLinkedQueue出队2" title="ConcurrentLinkedQueue出队2"><br>然后线程 A 执行 updateHead 操作，执行完毕后线程 A 退出，这时候队列状态为：<br><img src="/imgs/%E5%B9%B6%E5%8F%91/ConcurrentLinkedQueue%E5%87%BA%E9%98%9F3.png" alt="ConcurrentLinkedQueue出队3" title="ConcurrentLinkedQueue出队3"><br>然后线程 B 继续执行代码（3）q=p.next由于该节点是自引用节点所以p==q所以会执行代码（4）跳到外层循环 restartFromHead，重新获取当前队列队头 head, 现在状态为：<br><img src="/imgs/%E5%B9%B6%E5%8F%91/ConcurrentLinkedQueue%E5%87%BA%E9%98%9F4.png" alt="ConcurrentLinkedQueue出队4" title="ConcurrentLinkedQueue出队4"></li>
</ol>
<h2 id="ArrayBlockingQueue"><a href="#ArrayBlockingQueue" class="headerlink" title="ArrayBlockingQueue"></a>ArrayBlockingQueue</h2><p>offer是不会阻塞的，如果满了直接返回：</p>
<figure class="highlight plaintext"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br></pre></td><td class="code"><pre><span class="line">public boolean offer(E e) {</span><br><span class="line"> checkNotNull(e);</span><br><span class="line"> final ReentrantLock lock = this.lock;</span><br><span class="line"> lock.lock();</span><br><span class="line"> try {</span><br><span class="line"> // 如果已经超过容量阈值，则直接返回false</span><br><span class="line"> if (count == items.length)</span><br><span class="line"> return false;</span><br><span class="line"> else {</span><br><span class="line"> enqueue(e);</span><br><span class="line"> return true;</span><br><span class="line"> }</span><br><span class="line"> } finally {</span><br><span class="line"> lock.unlock();</span><br><span class="line"> }</span><br><span class="line">}</span><br><span class="line"></span><br><span class="line">private void enqueue(E x) {</span><br><span class="line"> // assert lock.getHoldCount() == 1;</span><br><span class="line"> // assert items[putIndex] == null;</span><br><span class="line"> final Object[] items = this.items;</span><br><span class="line"> items[putIndex] = x;</span><br><span class="line"> // 把它看成一个循环数组，如果超出范围就卷回</span><br><span class="line"> if (++putIndex == items.length)</span><br><span class="line"> putIndex = 0;</span><br><span class="line"> count++;</span><br><span class="line"> // 唤醒这个Condition，必须是在加了锁的前提下才能使用</span><br><span class="line"> notEmpty.signal();</span><br><span class="line">}</span><br></pre></td></tr></table></figure>
<p>poll同样也不会阻塞，如果空了直接返回null：</p>
<figure class="highlight plaintext"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br></pre></td><td class="code"><pre><span class="line">public E poll() {</span><br><span class="line"> final ReentrantLock lock = this.lock;</span><br><span class="line"> lock.lock();</span><br><span class="line"> try {</span><br><span class="line"> return (count == 0) ? null : dequeue();</span><br><span class="line"> } finally {</span><br><span class="line"> lock.unlock();</span><br><span class="line"> }</span><br><span class="line">}</span><br><span class="line"></span><br><span class="line">private E dequeue() {</span><br><span class="line"> // assert lock.getHoldCount() == 1;</span><br><span class="line"> // assert items[takeIndex] != null;</span><br><span class="line"> final Object[] items = this.items;</span><br><span class="line"> @SuppressWarnings("unchecked")</span><br><span class="line"> E x = (E) items[takeIndex];</span><br><span class="line"> items[takeIndex] = null;</span><br><span class="line"> // 回卷</span><br><span class="line"> if (++takeIndex == items.length)</span><br><span class="line"> takeIndex = 0;</span><br><span class="line"> count--;</span><br><span class="line"> if (itrs != null)</span><br><span class="line"> itrs.elementDequeued();</span><br><span class="line"> // 唤醒</span><br><span class="line"> notFull.signal();</span><br><span class="line"> return x;</span><br><span class="line">}</span><br></pre></td></tr></table></figure>
<p>put操作会等待notFull这个条件：</p>
<figure class="highlight plaintext"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br></pre></td><td class="code"><pre><span class="line">public void put(E e) throws InterruptedException {</span><br><span class="line"> checkNotNull(e);</span><br><span class="line"> final ReentrantLock lock = this.lock;</span><br><span class="line"> lock.lockInterruptibly();</span><br><span class="line"> try {</span><br><span class="line"> while (count == items.length)</span><br><span class="line"> notFull.await();</span><br><span class="line"> enqueue(e);</span><br><span class="line"> } finally {</span><br><span class="line"> lock.unlock();</span><br><span class="line"> }</span><br><span class="line">}</span><br></pre></td></tr></table></figure>
<p>take操作同理，会等待notEmpty这个条件：</p>
<figure class="highlight plaintext"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br></pre></td><td class="code"><pre><span class="line">public E take() throws InterruptedException {</span><br><span class="line"> final ReentrantLock lock = this.lock;</span><br><span class="line"> lock.lockInterruptibly();</span><br><span class="line"> try {</span><br><span class="line"> while (count == 0)</span><br><span class="line"> notEmpty.await();</span><br><span class="line"> return dequeue();</span><br><span class="line"> } finally {</span><br><span class="line"> lock.unlock();</span><br><span class="line"> }</span><br><span class="line">}</span><br></pre></td></tr></table></figure>
<h2 id="LinkedBlockingQueue"><a href="#LinkedBlockingQueue" class="headerlink" title="LinkedBlockingQueue"></a>LinkedBlockingQueue</h2><p>LinkedBlockingQueue 内部是通过单向链表实现，使用头尾节点来进行入队和出队操作，也就是入队操作都是对尾节点进行操作，出队操作都是对头节点进行操作，而头尾节点的操作分别使用了单独的<strong>独占锁</strong>保证了原子性，所以出队和入队操作是可以同时进行的。另外头尾节点的独占锁都配备了一个条件队列，用来存放被阻塞的线程，并结合入队出队操作实现了一个生产消费模型。</p>
<h2 id="PriorityBlockingQueue"><a href="#PriorityBlockingQueue" class="headerlink" title="PriorityBlockingQueue"></a>PriorityBlockingQueue</h2><h2 id="SynchronousQueue"><a href="#SynchronousQueue" class="headerlink" title="SynchronousQueue"></a>SynchronousQueue</h2><h2 id="LinkedTransferQueue"><a href="#LinkedTransferQueue" class="headerlink" title="LinkedTransferQueue"></a>LinkedTransferQueue</h2><h2 id="队列比较"><a href="#队列比较" class="headerlink" title="队列比较"></a>队列比较</h2><h2 id="Disruptor"><a href="#Disruptor" class="headerlink" title="Disruptor"></a>Disruptor</h2><ul>
<li><p>无锁内存队列</p>
</li>
<li><p>优化 CPU 伪共享</p>
</li>
<li><p>RingBuffer<br>环形队列，使用定长数组存储，长度是 2^N，可以使用位运算提升性能。<br>无锁：无锁设计减少了竞争。<br>预热：预先填充好任务/事件，不需要像链表那样每次添加/删除节点时去创建/回收节点，从而可以避免一定的垃圾回收。<br>缓存行填充解决了 CPU 伪共享问题。</p>
</li>
<li><p>WorkPool<br>存储 WorkProcessor 的池子，Disruptor 可以通过 Executor 并发启动每一个 WorkProcessor</p>
</li>
<li><p>WorkProcessor<br>从 RindBuffer 消费事件/任务，并交由 WorkHandler 处理。</p>
</li>
<li><p>WorkHandler<br>处理任务的工作者，根据任务类型委托给不同的 EventHandler。</p>
</li>
</ul>
<h2 id="Logback-框架中异步日志打印中-ArrayBlockingQueue-的使用"><a href="#Logback-框架中异步日志打印中-ArrayBlockingQueue-的使用" class="headerlink" title="Logback 框架中异步日志打印中 ArrayBlockingQueue 的使用"></a>Logback 框架中异步日志打印中 ArrayBlockingQueue 的使用</h2><p>异步模型是业务线程把要打印的日志任务写入一个队列后直接返回，然后使用一个线程专门负责从队列中获取日志任务写入磁盘，对用户线程来说，耗时只有将数据写入队列中。</p>
<h1 id="并发安全-Map"><a href="#并发安全-Map" class="headerlink" title="并发安全 Map"></a>并发安全 Map</h1><h2 id="ConcurrentHashMap"><a href="#ConcurrentHashMap" class="headerlink" title="ConcurrentHashMap"></a>ConcurrentHashMap</h2><p><img src="/imgs/%E5%B9%B6%E5%8F%91/ConcurrentHashMap%E7%BB%93%E6%9E%84.png" alt="ConcurrentHashMap结构" title="ConcurrentHashMap结构"></p>
<h3 id="get"><a href="#get" class="headerlink" title="get"></a>get</h3><p>代码：java.util.concurrent.ConcurrentHashMap.get</p>
<ol>
<li>计算 key 的散列值，可以使用该散列值定位到散列表中的某个槽。<br>如果 key 是自定义类型对象，需要实现重写 hash 方法。</li>
<li>找到对象<br>hash 值是不精确匹配的，hash 值的关键是计算简单而且有一定的区分度，比如取 string 的前 3 位的和作为 hash 值。<br>要精确匹配需要使用对象的 equals 方法。<br>ConcurrentHashMap 中哈希槽的实现方法有两种：链表和红黑树，链表和红黑树的查找过程就不必细说了。</li>
</ol>
<h3 id="put"><a href="#put" class="headerlink" title="put"></a>put</h3><p><img src="/imgs/%E5%B9%B6%E5%8F%91/ConcurrentHashMap%E7%9A%84put%E6%93%8D%E4%BD%9C.png" alt="ConcurrentHashMap的put操作" title="ConcurrentHashMap的put操作"><br>代码：java.util.concurrent.ConcurrentHashMap.put</p>
<ol>
<li>hash</li>
<li>找对象<br>找对象过程与 get 的区别主要是 put 需要并发控制：<ul>
<li>如果槽是空的，则通过 CAS 直接赋值；</li>
<li>如果槽非空，则先用<code>synchronized</code>锁住槽，接下来根据槽的数据结构来插入节点，如果槽是链表，则遍历链表找该 Node 是否已存在，不存在的情况下插入到末尾，如果槽是红黑树，则通过二叉树的遍历找目标 Node，找不到的情况下插入到叶子并重新执行红黑平衡。</li>
</ul>
</li>
</ol>
<h3 id="rehash"><a href="#rehash" class="headerlink" title="rehash"></a>rehash</h3><p>扩容的触发条件与HashMap一致。<br>扩容流程大致上是：遍历哈希槽，对每个需要迁移的哈希槽进行<code>synchronized</code>加锁。<br>当扩容开始后，其他线程必须等扩容完成后才能工作，但其他线程也不是就一直阻塞等扩容完成，而是调用<code>helpTransfer</code>方法一起帮助进行扩容，实际上因为扩容的单位是哈希槽，因此多线程并发执行扩容并不会导致明显的冲突增加。</p>
<p>扩容入口：</p>
<ol>
<li>helpTransfer<br>写入操作时协助扩容，即判断hash节点是ForwardingNode则调用helpTransfer将</li>
<li>全量添加时，需要保证</li>
<li></li>
</ol>
<p>扩容代码：<br><code>java.util.concurrent.ConcurrentHashMap.transfer</code></p>
<figure class="highlight plaintext"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br><span class="line">31</span><br><span class="line">32</span><br><span class="line">33</span><br><span class="line">34</span><br><span class="line">35</span><br><span class="line">36</span><br><span class="line">37</span><br><span class="line">38</span><br><span class="line">39</span><br><span class="line">40</span><br><span class="line">41</span><br><span class="line">42</span><br><span class="line">43</span><br><span class="line">44</span><br><span class="line">45</span><br><span class="line">46</span><br><span class="line">47</span><br><span class="line">48</span><br><span class="line">49</span><br><span class="line">50</span><br><span class="line">51</span><br><span class="line">52</span><br><span class="line">53</span><br><span class="line">54</span><br><span class="line">55</span><br><span class="line">56</span><br><span class="line">57</span><br><span class="line">58</span><br><span class="line">59</span><br><span class="line">60</span><br><span class="line">61</span><br><span class="line">62</span><br><span class="line">63</span><br><span class="line">64</span><br><span class="line">65</span><br><span class="line">66</span><br><span class="line">67</span><br><span class="line">68</span><br><span class="line">69</span><br><span class="line">70</span><br><span class="line">71</span><br><span class="line">72</span><br><span class="line">73</span><br><span class="line">74</span><br><span class="line">75</span><br><span class="line">76</span><br><span class="line">77</span><br><span class="line">78</span><br><span class="line">79</span><br><span class="line">80</span><br><span class="line">81</span><br><span class="line">82</span><br><span class="line">83</span><br><span class="line">84</span><br><span class="line">85</span><br><span class="line">86</span><br><span class="line">87</span><br><span class="line">88</span><br><span class="line">89</span><br><span class="line">90</span><br><span class="line">91</span><br><span class="line">92</span><br><span class="line">93</span><br><span class="line">94</span><br><span class="line">95</span><br><span class="line">96</span><br><span class="line">97</span><br><span class="line">98</span><br><span class="line">99</span><br><span class="line">100</span><br><span class="line">101</span><br><span class="line">102</span><br><span class="line">103</span><br><span class="line">104</span><br><span class="line">105</span><br><span class="line">106</span><br><span class="line">107</span><br><span class="line">108</span><br><span class="line">109</span><br><span class="line">110</span><br><span class="line">111</span><br><span class="line">112</span><br><span class="line">113</span><br><span class="line">114</span><br><span class="line">115</span><br><span class="line">116</span><br><span class="line">117</span><br><span class="line">118</span><br><span class="line">119</span><br><span class="line">120</span><br><span class="line">121</span><br><span class="line">122</span><br><span class="line">123</span><br><span class="line">124</span><br><span class="line">125</span><br><span class="line">126</span><br><span class="line">127</span><br><span class="line">128</span><br><span class="line">129</span><br><span class="line">130</span><br><span class="line">131</span><br><span class="line">132</span><br><span class="line">133</span><br><span class="line">134</span><br><span class="line">135</span><br><span class="line">136</span><br><span class="line">137</span><br><span class="line">138</span><br><span class="line">139</span><br><span class="line">140</span><br><span class="line">141</span><br><span class="line">142</span><br><span class="line">143</span><br><span class="line">144</span><br><span class="line">145</span><br><span class="line">146</span><br><span class="line">147</span><br><span class="line">148</span><br></pre></td><td class="code"><pre><span class="line">/**</span><br><span class="line"> * Moves and/or copies the nodes in each bin to new table. See</span><br><span class="line"> * above for explanation.</span><br><span class="line"> */</span><br><span class="line">private final void transfer(Node<K,V>[] tab, Node<K,V>[] nextTab) {</span><br><span class="line"> int n = tab.length, stride;</span><br><span class="line"> if ((stride = (NCPU > 1) ? (n >>> 3) / NCPU : n) < MIN_TRANSFER_STRIDE)</span><br><span class="line"> stride = MIN_TRANSFER_STRIDE; // subdivide range</span><br><span class="line"> // 创建一个新的两倍大小的新nextTab，将老tab中的元素迁移过去</span><br><span class="line"> if (nextTab == null) { // initiating</span><br><span class="line"> try {</span><br><span class="line"> @SuppressWarnings("unchecked")</span><br><span class="line"> Node<K,V>[] nt = (Node<K,V>[])new Node<?,?>[n << 1];</span><br><span class="line"> nextTab = nt;</span><br><span class="line"> } catch (Throwable ex) { // try to cope with OOME</span><br><span class="line"> sizeCtl = Integer.MAX_VALUE;</span><br><span class="line"> return;</span><br><span class="line"> }</span><br><span class="line"> nextTable = nextTab;</span><br><span class="line"> transferIndex = n;</span><br><span class="line"> }</span><br><span class="line"> int nextn = nextTab.length;</span><br><span class="line"> // 标记节点</span><br><span class="line"> ForwardingNode<K,V> fwd = new ForwardingNode<K,V>(nextTab);</span><br><span class="line"> boolean advance = true;</span><br><span class="line"> boolean finishing = false; // to ensure sweep before committing nextTab</span><br><span class="line"> for (int i = 0, bound = 0;;) {</span><br><span class="line"> Node<K,V> f; int fh;</span><br><span class="line"> while (advance) {</span><br><span class="line"> int nextIndex, nextBound;</span><br><span class="line"> if (--i >= bound || finishing)</span><br><span class="line"> advance = false;</span><br><span class="line"> else if ((nextIndex = transferIndex) <= 0) {</span><br><span class="line"> i = -1;</span><br><span class="line"> advance = false;</span><br><span class="line"> }</span><br><span class="line"> else if (U.compareAndSwapInt</span><br><span class="line"> (this, TRANSFERINDEX, nextIndex,</span><br><span class="line"> nextBound = (nextIndex > stride ?</span><br><span class="line"> nextIndex - stride : 0))) {</span><br><span class="line"> bound = nextBound;</span><br><span class="line"> i = nextIndex - 1;</span><br><span class="line"> advance = false;</span><br><span class="line"> }</span><br><span class="line"> }</span><br><span class="line"> if (i < 0 || i >= n || i + n >= nextn) {</span><br><span class="line"> int sc;</span><br><span class="line"> if (finishing) {</span><br><span class="line"> nextTable = null;</span><br><span class="line"> table = nextTab;</span><br><span class="line"> sizeCtl = (n << 1) - (n >>> 1);</span><br><span class="line"> return;</span><br><span class="line"> }</span><br><span class="line"> if (U.compareAndSwapInt(this, SIZECTL, sc = sizeCtl, sc - 1)) {</span><br><span class="line"> if ((sc - 2) != resizeStamp(n) << RESIZE_STAMP_SHIFT)</span><br><span class="line"> return;</span><br><span class="line"> finishing = advance = true;</span><br><span class="line"> i = n; // recheck before commit</span><br><span class="line"> }</span><br><span class="line"> }</span><br><span class="line"> // 如果tab当前位置为null，则设置fwd节点</span><br><span class="line"> else if ((f = tabAt(tab, i)) == null)</span><br><span class="line"> advance = casTabAt(tab, i, null, fwd);</span><br><span class="line"> // 已经是fwd节点，则遍历下一个位置</span><br><span class="line"> else if ((fh = f.hash) == MOVED)</span><br><span class="line"> advance = true; // already processed</span><br><span class="line"> else {</span><br><span class="line"> // tab当前位置已有节点，则加锁</span><br><span class="line"> synchronized (f) {</span><br><span class="line"> if (tabAt(tab, i) == f) {</span><br><span class="line"> Node<K,V> ln, hn;</span><br><span class="line"> // 表示链表节点，如果是树节点则fh=-2</span><br><span class="line"> if (fh >= 0) {</span><br><span class="line"> // 头节点的hash值</span><br><span class="line"> int runBit = fh & n;</span><br><span class="line"> Node<K,V> lastRun = f;</span><br><span class="line"> // 链表的下一节点p</span><br><span class="line"> for (Node<K,V> p = f.next; p != null; p = p.next) {</span><br><span class="line"> // p节点的hash值</span><br><span class="line"> int b = p.hash & n;</span><br><span class="line"> // 避免成环？</span><br><span class="line"> if (b != runBit) {</span><br><span class="line"> runBit = b;</span><br><span class="line"> lastRun = p;</span><br><span class="line"> }</span><br><span class="line"> }</span><br><span class="line"> if (runBit == 0) {</span><br><span class="line"> ln = lastRun;</span><br><span class="line"> hn = null;</span><br><span class="line"> }</span><br><span class="line"> else {</span><br><span class="line"> hn = lastRun;</span><br><span class="line"> ln = null;</span><br><span class="line"> }</span><br><span class="line"> for (Node<K,V> p = f; p != lastRun; p = p.next) {</span><br><span class="line"> int ph = p.hash; K pk = p.key; V pv = p.val;</span><br><span class="line"> if ((ph & n) == 0)</span><br><span class="line"> ln = new Node<K,V>(ph, pk, pv, ln);</span><br><span class="line"> else</span><br><span class="line"> hn = new Node<K,V>(ph, pk, pv, hn);</span><br><span class="line"> }</span><br><span class="line"> // 将ln和hn转移到nextTab</span><br><span class="line"> setTabAt(nextTab, i, ln);</span><br><span class="line"> setTabAt(nextTab, i + n, hn);</span><br><span class="line"> 原tab置为fwd，表示已经被转移了</span><br><span class="line"> setTabAt(tab, i, fwd);</span><br><span class="line"> advance = true;</span><br><span class="line"> }</span><br><span class="line"> else if (f instanceof TreeBin) {</span><br><span class="line"> TreeBin<K,V> t = (TreeBin<K,V>)f;</span><br><span class="line"> TreeNode<K,V> lo = null, loTail = null;</span><br><span class="line"> TreeNode<K,V> hi = null, hiTail = null;</span><br><span class="line"> int lc = 0, hc = 0;</span><br><span class="line"> for (Node<K,V> e = t.first; e != null; e = e.next) {</span><br><span class="line"> int h = e.hash;</span><br><span class="line"> TreeNode<K,V> p = new TreeNode<K,V></span><br><span class="line"> (h, e.key, e.val, null, null);</span><br><span class="line"> if ((h & n) == 0) {</span><br><span class="line"> if ((p.prev = loTail) == null)</span><br><span class="line"> lo = p;</span><br><span class="line"> else</span><br><span class="line"> loTail.next = p;</span><br><span class="line"> loTail = p;</span><br><span class="line"> ++lc;</span><br><span class="line"> }</span><br><span class="line"> else {</span><br><span class="line"> if ((p.prev = hiTail) == null)</span><br><span class="line"> hi = p;</span><br><span class="line"> else</span><br><span class="line"> hiTail.next = p;</span><br><span class="line"> hiTail = p;</span><br><span class="line"> ++hc;</span><br><span class="line"> }</span><br><span class="line"> }</span><br><span class="line"> ln = (lc <= UNTREEIFY_THRESHOLD) ? untreeify(lo) :</span><br><span class="line"> (hc != 0) ? new TreeBin<K,V>(lo) : t;</span><br><span class="line"> hn = (hc <= UNTREEIFY_THRESHOLD) ? untreeify(hi) :</span><br><span class="line"> (lc != 0) ? new TreeBin<K,V>(hi) : t;</span><br><span class="line"> setTabAt(nextTab, i, ln);</span><br><span class="line"> setTabAt(nextTab, i + n, hn);</span><br><span class="line"> setTabAt(tab, i, fwd);</span><br><span class="line"> advance = true;</span><br><span class="line"> }</span><br><span class="line"> }</span><br><span class="line"> }</span><br><span class="line"> }</span><br><span class="line"> }</span><br><span class="line">}</span><br></pre></td></tr></table></figure>
<h3 id="size"><a href="#size" class="headerlink" title="size"></a>size</h3><p>size操作返回的是一个不精确的值，因为进行统计的过程中，很有可能会有其他线程正在进行插入和删除操作。</p>
<p>1.8之前的size：</p>
<ol>
<li>遍历segments数组，将每个segment的count加起来作为总数，将modCount加起来作为修改总数；<br>modCount会在每次segment被修改时+1（只增不减），用于比较。</li>
<li>再做一遍遍历，将这次的modCount总数和上一次的比较，如果一致则计数准确直接返回，否则重试；</li>
<li>如果重试了2次都不行，则第三次会对segment加锁再统计。</li>
</ol>
<p>1.8之后，没有了分段锁，size不会每次都遍历segments统计，而是在更新时修改总数：</p>
<figure class="highlight plaintext"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br></pre></td><td class="code"><pre><span class="line">public int size() {</span><br><span class="line"> long n = sumCount();</span><br><span class="line"> return ((n < 0L) ? 0 :</span><br><span class="line"> (n > (long)Integer.MAX_VALUE) ? Integer.MAX_VALUE :</span><br><span class="line"> (int)n);</span><br><span class="line">}</span><br><span class="line"></span><br><span class="line">final long sumCount() {</span><br><span class="line"> CounterCell[] as = counterCells; CounterCell a;</span><br><span class="line"> long sum = baseCount;</span><br><span class="line"> if (as != null) {</span><br><span class="line"> for (int i = 0; i < as.length; ++i) {</span><br><span class="line"> if ((a = as[i]) != null)</span><br><span class="line"> sum += a.value;</span><br><span class="line"> }</span><br><span class="line"> }</span><br><span class="line"> return sum;</span><br><span class="line">}</span><br></pre></td></tr></table></figure>
<p>从源码中可以看到，<code>ConcurrentHashMap#size</code>的结果就是：<br><code>baseCount + sum(counterCells)</code><br>其中：</p>
<ul>
<li>baseCount：计数，总数发生变化时通过CAS修改</li>
<li>counterCells：如果baseCount CAS修改失败，作为兜底，类似LongAdder的思路。</li>
</ul>
<p>put操作的末尾会调用addCount()更新baseCount的值，如果CAS修改失败了，则使用counterCells，如果CAS修改 counterCells失败了，则使用fullAddCount方法继续死循环操作，直到成功。</p>
<h1 id="QA"><a href="#QA" class="headerlink" title="QA"></a>QA</h1><ol>
<li><p>JUC 并发包中并发组件 CopyOnWriteArrayList 的实现原理，CopyOnWriteArrayList 是如何通过写时拷贝实现并发安全的 List？</p>
</li>
<li><p>什么是弱一致性？</p>
</li>
<li><p>说一下 ConcurrentHashMap。</p>
</li>
<li><p>ConcurrentHashMap 怎么实现并发安全？<br>相对 Hashtable 来说 ConcurrentHashMap 的锁粒度是更小的，Hashtable 中使用 synchronized 实现的一种方法级的悲观锁，相当于把整个散列表锁住了，不利于系统整体吞吐量的提升。<br>JDK1.7 中它使用的是一种分段锁来保证并发安全，是一种粒度较小的锁，写操作每次只锁住一个哈希槽，<br>JDK1.8 之后改为通过实现一种基于 CAS 的乐观锁来保证并发安全，当然，和 HashMap 一样，每个哈希槽在增长到一定程度后会自动转换为红黑树。</p>
</li>
</ol>
<h1 id="参考"><a href="#参考" class="headerlink" title="参考"></a>参考</h1><ol>
<li><a target="_blank" rel="noopener" href="http://www.cnblogs.com/leesf456/p/5550043.html">【目录】JUC 集合框架目录</a></li>
<li><a target="_blank" rel="noopener" href="http://ifeve.com/disruptor/">并发框架 Disruptor 译文</a></li>
</ol>
<script type="text/javascript" src="https://cdn.jsdelivr.net/npm/kity@2.0.4/dist/kity.min.js"></script><script type="text/javascript" src="https://cdn.jsdelivr.net/npm/kityminder-core@1.4.50/dist/kityminder.core.min.js"></script><script defer="true" type="text/javascript" src="https://cdn.jsdelivr.net/npm/hexo-simple-mindmap@0.6.0/dist/mindmap.min.js"></script><link rel="stylesheet" type="text/css" href="https://cdn.jsdelivr.net/npm/hexo-simple-mindmap@0.6.0/dist/mindmap.min.css">
</div>
<footer class="post-footer">
<div class="post-tags">
<a href="/tags/%E5%B9%B6%E5%8F%91/" rel="tag"># 并发</a>
</div>
<div class="post-nav">
<div class="post-nav-item">
<a href="/ba7cab3d.html" rel="prev" title="并发安全容器-Queue">
<i class="fa fa-angle-left"></i> 并发安全容器-Queue
</a>
</div>
<div class="post-nav-item">
<a href="/283c6d00.html" rel="next" title="Linux 基本概念">
Linux 基本概念 <i class="fa fa-angle-right"></i>
</a>
</div>
</div>
</footer>
</article>
</div>
</div>
</main>
<footer class="footer">
<div class="footer-inner">
<div class="copyright">
©
<span itemprop="copyrightYear">2025</span>
<span class="with-love">
<i class="fa fa-heart"></i>
</span>
<span class="author" itemprop="copyrightHolder">tallate</span>
</div>
<div class="powered-by">由 <a href="https://hexo.io/" rel="noopener" target="_blank">Hexo</a> & <a href="https://theme-next.js.org/" rel="noopener" target="_blank">NexT.Gemini</a> 强力驱动
</div>
</div>
</footer>
<div class="back-to-top" role="button" aria-label="返回顶部">
<i class="fa fa-arrow-up fa-lg"></i>
<span>0%</span>
</div>
<a href="https://github.com/tallate" class="github-corner" title="在 GitHub 上关注我" aria-label="在 GitHub 上关注我" rel="noopener" target="_blank"><svg width="80" height="80" viewBox="0 0 250 250" aria-hidden="true"><path d="M0,0 L115,115 L130,115 L142,142 L250,250 L250,0 Z"></path><path d="M128.3,109.0 C113.8,99.7 119.0,89.6 119.0,89.6 C122.0,82.7 120.5,78.6 120.5,78.6 C119.2,72.0 123.4,76.3 123.4,76.3 C127.3,80.9 125.5,87.3 125.5,87.3 C122.9,97.6 130.6,101.9 134.4,103.2" fill="currentColor" style="transform-origin: 130px 106px;" class="octo-arm"></path><path d="M115.0,115.0 C114.9,115.1 118.7,116.5 119.8,115.4 L133.7,101.6 C136.9,99.2 139.9,98.4 142.2,98.6 C133.8,88.0 127.5,74.4 143.8,58.0 C148.5,53.4 154.0,51.2 159.7,51.0 C160.3,49.4 163.2,43.6 171.4,40.1 C171.4,40.1 176.1,42.5 178.8,56.2 C183.1,58.6 187.2,61.8 190.9,65.4 C194.5,69.0 197.7,73.2 200.1,77.6 C213.8,80.2 216.3,84.9 216.3,84.9 C212.7,93.1 206.9,96.0 205.4,96.6 C205.1,102.4 203.0,107.8 198.3,112.5 C181.9,128.9 168.3,122.5 157.7,114.1 C157.9,116.9 156.7,120.9 152.7,124.9 L141.0,136.5 C139.8,137.7 141.6,141.9 141.8,141.8 Z" fill="currentColor" class="octo-body"></path></svg></a>
<noscript>
<div class="noscript-warning">Theme NexT works best with JavaScript enabled</div>
</noscript>
<script src="https://cdnjs.cloudflare.com/ajax/libs/animejs/3.2.1/anime.min.js" integrity="sha256-XL2inqUJaslATFnHdJOi9GfQ60on8Wx1C2H8DYiN1xY=" crossorigin="anonymous"></script>
<script src="/js/comments.js"></script><script src="/js/utils.js"></script><script src="/js/motion.js"></script><script src="/js/next-boot.js"></script>
<script src="https://cdnjs.cloudflare.com/ajax/libs/hexo-generator-searchdb/1.4.1/search.js" integrity="sha256-1kfA5uHPf65M5cphT2dvymhkuyHPQp5A53EGZOnOLmc=" crossorigin="anonymous"></script>
<script src="/js/third-party/search/local-search.js"></script>
<script class="next-config" data-name="mermaid" type="application/json">{"enable":true,"version":"7.1.2","options":null,"js":{"url":"https://cdnjs.cloudflare.com/ajax/libs/mermaid/10.3.0/mermaid.min.js","integrity":"sha256-9y71g5Lz/KLsHjB8uXwnkuWDtAMDSzD/HdIbqhJfTAI="}}</script>
<script src="/js/third-party/tags/mermaid.js"></script>
</body>
</html>