-
Notifications
You must be signed in to change notification settings - Fork 0
/
Copy pathindex.html
898 lines (638 loc) · 141 KB
/
index.html
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
495
496
497
498
499
500
501
502
503
504
505
506
507
508
509
510
511
512
513
514
515
516
517
518
519
520
521
522
523
524
525
526
527
528
529
530
531
532
533
534
535
536
537
538
539
540
541
542
543
544
545
546
547
548
549
550
551
552
553
554
555
556
557
558
559
560
561
562
563
564
565
566
567
568
569
570
571
572
573
574
575
576
577
578
579
580
581
582
583
584
585
586
587
588
589
590
591
592
593
594
595
596
597
598
599
600
601
602
603
604
605
606
607
608
609
610
611
612
613
614
615
616
617
618
619
620
621
622
623
624
625
626
627
628
629
630
631
632
633
634
635
636
637
638
639
640
641
642
643
644
645
646
647
648
649
650
651
652
653
654
655
656
657
658
659
660
661
662
663
664
665
666
667
668
669
670
671
672
673
674
675
676
677
678
679
680
681
682
683
684
685
686
687
688
689
690
691
692
693
694
695
696
697
698
699
700
701
702
703
704
705
706
707
708
709
710
711
712
713
714
715
716
717
718
719
720
721
722
723
724
725
726
727
728
729
730
731
732
733
734
735
736
737
738
739
740
741
742
743
744
745
746
747
748
749
750
751
752
753
754
755
756
757
758
759
760
761
762
763
764
765
766
767
768
769
770
771
772
773
774
775
776
777
778
779
780
781
782
783
784
785
786
787
788
789
790
791
792
793
794
795
796
797
798
799
800
801
802
803
804
805
806
807
808
809
810
811
812
813
814
815
816
817
818
819
820
821
822
823
824
825
826
827
828
829
830
831
832
833
834
835
836
837
838
839
840
841
842
843
844
845
846
847
848
849
850
851
852
853
854
855
856
857
858
859
860
861
862
863
864
865
866
867
868
869
870
871
872
873
874
875
876
877
878
879
880
881
882
883
884
885
886
887
888
889
890
891
892
893
894
895
896
897
898
<!DOCTYPE html>
<html>
<head>
<meta charset="utf-8">
<title>Welcome to l-iberty's blog ^_^</title>
<meta name="viewport" content="width=device-width, initial-scale=1, maximum-scale=1">
<meta property="og:type" content="website">
<meta property="og:title" content="Welcome to l-iberty's blog ^_^">
<meta property="og:url" content="http://yoursite.com/index.html">
<meta property="og:site_name" content="Welcome to l-iberty's blog ^_^">
<meta property="og:locale" content="en_US">
<meta property="article:author" content="l-iberty">
<meta name="twitter:card" content="summary">
<link rel="alternate" href="/atom.xml" title="Welcome to l-iberty's blog ^_^" type="application/atom+xml">
<link rel="icon" href="/favicon.png">
<link href="//fonts.googleapis.com/css?family=Source+Code+Pro" rel="stylesheet" type="text/css">
<link rel="stylesheet" href="/css/style.css">
<meta name="generator" content="Hexo 4.2.0"></head>
<body>
<div id="container">
<div id="wrap">
<header id="header">
<div id="banner"></div>
<div id="header-outer" class="outer">
<div id="header-title" class="inner">
<h1 id="logo-wrap">
<a href="/" id="logo">Welcome to l-iberty's blog ^_^</a>
</h1>
</div>
<div id="header-inner" class="inner">
<nav id="main-nav">
<a id="main-nav-toggle" class="nav-icon"></a>
<a class="main-nav-link" href="/">Home</a>
<a class="main-nav-link" href="/archives">Archives</a>
</nav>
<nav id="sub-nav">
<a id="nav-rss-link" class="nav-icon" href="/atom.xml" title="RSS Feed"></a>
<a id="nav-search-btn" class="nav-icon" title="Search"></a>
</nav>
<div id="search-form-wrap">
<form action="//google.com/search" method="get" accept-charset="UTF-8" class="search-form"><input type="search" name="q" class="search-form-input" placeholder="Search"><button type="submit" class="search-form-submit"></button><input type="hidden" name="sitesearch" value="http://yoursite.com"></form>
</div>
</div>
</div>
</header>
<div class="outer">
<section id="main">
<article id="post-密集索引和稀疏索引" class="article article-type-post" itemscope itemprop="blogPost">
<div class="article-meta">
<a href="/2021/05/07/%E5%AF%86%E9%9B%86%E7%B4%A2%E5%BC%95%E5%92%8C%E7%A8%80%E7%96%8F%E7%B4%A2%E5%BC%95/" class="article-date">
<time datetime="2021-05-07T03:23:31.000Z" itemprop="datePublished">2021-05-07</time>
</a>
</div>
<div class="article-inner">
<header class="article-header">
<h1 itemprop="name">
<a class="article-title" href="/2021/05/07/%E5%AF%86%E9%9B%86%E7%B4%A2%E5%BC%95%E5%92%8C%E7%A8%80%E7%96%8F%E7%B4%A2%E5%BC%95/">密集索引和稀疏索引</a>
</h1>
</header>
<div class="article-entry" itemprop="articleBody">
<h2 id="密集索引"><a href="#密集索引" class="headerlink" title="密集索引"></a>密集索引</h2><p>在密集索引中，文件中的每个搜索码值都对应一个索引值。也就是说，稠密索引为数据记录文件的每一条记录都设一个“键-指针”对。如下图所示，索引项包括索引值以及指向该搜索码的第一条数据记录的指针。</p>
<p><img src="/2021/05/07/%E5%AF%86%E9%9B%86%E7%B4%A2%E5%BC%95%E5%92%8C%E7%A8%80%E7%96%8F%E7%B4%A2%E5%BC%95/dense_index.png" alt></p>
<h2 id="稀疏索引"><a href="#稀疏索引" class="headerlink" title="稀疏索引"></a>稀疏索引</h2><p>在稀疏索引中，只为搜索码的某些值建立索引项。也就是说，稀疏索引为数据记录文件的每个存储块设一个“键-指针”对，存储块内的块内存储单元连续。如下图所示。</p>
<p><img src="/2021/05/07/%E5%AF%86%E9%9B%86%E7%B4%A2%E5%BC%95%E5%92%8C%E7%A8%80%E7%96%8F%E7%B4%A2%E5%BC%95/sparse_index.png" alt></p>
<h3 id="优缺点"><a href="#优缺点" class="headerlink" title="优缺点"></a>优缺点</h3><ul>
<li>密集索引比稀疏索引能更快定位一条记录</li>
<li>稀疏索引所占空间小，并且插入和删除所需的维护开销也小，但要求存储块内部的存储单元连续</li>
</ul>
</div>
<footer class="article-footer">
<a data-url="http://yoursite.com/2021/05/07/%E5%AF%86%E9%9B%86%E7%B4%A2%E5%BC%95%E5%92%8C%E7%A8%80%E7%96%8F%E7%B4%A2%E5%BC%95/" data-id="ckp3d9fay000agwrt60koe5ri" class="article-share-link">Share</a>
</footer>
</div>
</article>
<article id="post-MySQL" class="article article-type-post" itemscope itemprop="blogPost">
<div class="article-meta">
<a href="/2021/04/30/MySQL/" class="article-date">
<time datetime="2021-04-30T06:35:52.000Z" itemprop="datePublished">2021-04-30</time>
</a>
</div>
<div class="article-inner">
<header class="article-header">
<h1 itemprop="name">
<a class="article-title" href="/2021/04/30/MySQL/">MySQL</a>
</h1>
</header>
<div class="article-entry" itemprop="articleBody">
<h2 id="一、聚集索引、非聚集索引"><a href="#一、聚集索引、非聚集索引" class="headerlink" title="一、聚集索引、非聚集索引"></a>一、聚集索引、非聚集索引</h2><p><a href="https://www.cnblogs.com/s-b-b/p/8334593.html" target="_blank" rel="noopener">聚集索引与非聚集索引的总结</a></p>
<h3 id="1-聚集索引"><a href="#1-聚集索引" class="headerlink" title="1.聚集索引"></a>1.聚集索引</h3><p><img src="/2021/04/30/MySQL/clusteredindex.png" alt></p>
<ul>
<li>叶子节点就是数据行</li>
<li>聚集索引是对主键建立的索引，数据行的物理存储顺序与主键值的顺序相同，因此一个表只能有一个聚集索引</li>
</ul>
<p><strong>插入数据时主键最好保持递增，这样在建立 B+Tree 索引结构时相当于顺序添加节点，不会对整个结构做出过大的调整</strong></p>
<h3 id="2-非聚集索引"><a href="#2-非聚集索引" class="headerlink" title="2.非聚集索引"></a>2.非聚集索引</h3><p><img src="/2021/04/30/MySQL/nonclusteredindex.png" alt></p>
<ul>
<li>叶子节点存储数据行的地址信息</li>
<li>非聚集索引是对除主键外的列建立的索引，一个表可以有多个非聚集索引</li>
</ul>
<h2 id="二、InnoDB-的-double-write"><a href="#二、InnoDB-的-double-write" class="headerlink" title="二、InnoDB 的 double write"></a>二、InnoDB 的 double write</h2><h3 id="脏页刷盘的风险："><a href="#脏页刷盘的风险：" class="headerlink" title="脏页刷盘的风险："></a>脏页刷盘的风险：</h3><p><img src="/2021/04/30/MySQL/partial_page_write.png" alt></p>
<h3 id="Double-write-方案："><a href="#Double-write-方案：" class="headerlink" title="Double write 方案："></a>Double write 方案：</h3><p><img src="/2021/04/30/MySQL/double_write.png" alt></p>
<ul>
<li>如果“<strong>(2)顺序write</strong>”出错，由于数据文件未被修改，所以不会造成问题</li>
<li>如果“<strong>(3)离散write</strong>”出错，则可以从磁盘上的共享表空间找到相应的页进行恢复</li>
</ul>
<h4 id="为什么不用-redo-log-进行恢复？"><a href="#为什么不用-redo-log-进行恢复？" class="headerlink" title="为什么不用 redo log 进行恢复？"></a>为什么不用 redo log 进行恢复？</h4><p>Redo log 恢复是以事务为单位的，前提是磁盘上的 page 保持完整。Double write 恢复策略是针对 page 刷盘时发生损坏而不完整的情形。</p>
<h4 id="为什么写日志时不需要-double-write-支持？"><a href="#为什么写日志时不需要-double-write-支持？" class="headerlink" title="为什么写日志时不需要 double write 支持？"></a>为什么写日志时不需要 double write 支持？</h4><p>因为日志刷盘是以磁盘IO的最小单位进行的，例如 HDD 的一个扇区。</p>
</div>
<footer class="article-footer">
<a data-url="http://yoursite.com/2021/04/30/MySQL/" data-id="ckp3d9fau0007gwrt80tw72bc" class="article-share-link">Share</a>
</footer>
</div>
</article>
<article id="post-CPU分支预测对性能的影响" class="article article-type-post" itemscope itemprop="blogPost">
<div class="article-meta">
<a href="/2021/04/27/CPU%E5%88%86%E6%94%AF%E9%A2%84%E6%B5%8B%E5%AF%B9%E6%80%A7%E8%83%BD%E7%9A%84%E5%BD%B1%E5%93%8D/" class="article-date">
<time datetime="2021-04-27T02:43:06.000Z" itemprop="datePublished">2021-04-27</time>
</a>
</div>
<div class="article-inner">
<header class="article-header">
<h1 itemprop="name">
<a class="article-title" href="/2021/04/27/CPU%E5%88%86%E6%94%AF%E9%A2%84%E6%B5%8B%E5%AF%B9%E6%80%A7%E8%83%BD%E7%9A%84%E5%BD%B1%E5%93%8D/">CPU分支预测对性能的影响</a>
</h1>
</header>
<div class="article-entry" itemprop="articleBody">
<p>来源：<a href="https://stackoverflow.com/questions/11227809/why-is-processing-a-sorted-array-faster-than-processing-an-unsorted-array" target="_blank" rel="noopener">StackOverflow · Why is processing a sorted array faster than processing an unsorted array?</a> 原文中已有详细探讨，此处不再赘述，只记录、补充一些关键点。</p>
<figure class="highlight cpp"><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"><span class="meta">#<span class="meta-keyword">include</span> <span class="meta-string"><algorithm></span></span></span><br><span class="line"><span class="meta">#<span class="meta-keyword">include</span> <span class="meta-string"><ctime></span></span></span><br><span class="line"><span class="meta">#<span class="meta-keyword">include</span> <span class="meta-string"><iostream></span></span></span><br><span class="line"></span><br><span class="line"><span class="function"><span class="keyword">int</span> <span class="title">main</span><span class="params">()</span></span></span><br><span class="line"><span class="function"></span>{</span><br><span class="line"> <span class="comment">// Generate data</span></span><br><span class="line"> <span class="keyword">const</span> <span class="keyword">unsigned</span> arraySize = <span class="number">32768</span>;</span><br><span class="line"> <span class="keyword">int</span> data[arraySize];</span><br><span class="line"></span><br><span class="line"> <span class="keyword">for</span> (<span class="keyword">unsigned</span> c = <span class="number">0</span>; c < arraySize; ++c)</span><br><span class="line"> data[c] = <span class="built_in">std</span>::rand() % <span class="number">256</span>;</span><br><span class="line"></span><br><span class="line"> <span class="comment">// !!! With this, the next loop runs faster.</span></span><br><span class="line"> <span class="built_in">std</span>::sort(data, data + arraySize);</span><br><span class="line"></span><br><span class="line"> <span class="comment">// Test</span></span><br><span class="line"> <span class="keyword">clock_t</span> start = clock();</span><br><span class="line"> <span class="keyword">long</span> <span class="keyword">long</span> sum = <span class="number">0</span>;</span><br><span class="line"> <span class="keyword">for</span> (<span class="keyword">unsigned</span> i = <span class="number">0</span>; i < <span class="number">100000</span>; ++i)</span><br><span class="line"> {</span><br><span class="line"> <span class="keyword">for</span> (<span class="keyword">unsigned</span> c = <span class="number">0</span>; c < arraySize; ++c)</span><br><span class="line"> { <span class="comment">// Primary loop</span></span><br><span class="line"> <span class="keyword">if</span> (data[c] >= <span class="number">128</span>)</span><br><span class="line"> sum += data[c];</span><br><span class="line"> }</span><br><span class="line"> }</span><br><span class="line"></span><br><span class="line"> <span class="keyword">double</span> elapsedTime = <span class="keyword">static_cast</span><<span class="keyword">double</span>>(clock() - start) / CLOCKS_PER_SEC;</span><br><span class="line"></span><br><span class="line"> <span class="built_in">std</span>::<span class="built_in">cout</span> << elapsedTime << <span class="built_in">std</span>::<span class="built_in">endl</span>;</span><br><span class="line"> <span class="built_in">std</span>::<span class="built_in">cout</span> << <span class="string">"sum = "</span> << sum << <span class="built_in">std</span>::<span class="built_in">endl</span>;</span><br><span class="line">}</span><br></pre></td></tr></table></figure>
<p>数据均匀地分布在<code>[0,255]</code>范围内，排序后对于后半部分的数据，<code>if</code>语句的分支预测总能成功：</p>
<figure class="highlight cpp"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br></pre></td><td class="code"><pre><span class="line"><span class="keyword">if</span> (data[c] >= <span class="number">128</span>)</span><br><span class="line"> sum += data[c];</span><br></pre></td></tr></table></figure>
<p>打开反汇编可以看到条件跳转指令<code>jl</code>。</p>
<h3 id="静态-or-动态分支预测"><a href="#静态-or-动态分支预测" class="headerlink" title="静态 or 动态分支预测"></a>静态 or 动态分支预测</h3><p>显然静态分支预测不会产生本例中的性能差异（因为大于128和不大于128的数字各占一半，如果采用静态分支预测的话总有一半的条件转移指令会预测失败），现今的处理器肯定采用更为先进的做法。</p>
<p>动态分支预测主要依靠<strong>分支历史表BHT</strong>、<strong>分支目标缓存BTB</strong>等硬件支持，此外还包括<strong>前瞻执行</strong>等技术，例如 Tomasulo 算法的前瞻执行。</p>
<h3 id="为什么三目运算符更快？"><a href="#为什么三目运算符更快？" class="headerlink" title="为什么三目运算符更快？"></a>为什么三目运算符更快？</h3><p>如果把上面那段<code>if</code>语句改成：</p>
<figure class="highlight cpp"><table><tr><td class="gutter"><pre><span class="line">1</span><br></pre></td><td class="code"><pre><span class="line">sum += (data[c] >= <span class="number">128</span>) ? data[c] : <span class="number">0</span>;</span><br></pre></td></tr></table></figure>
<p>用 Visual Studio 编译成 Release 版本，就会发现即使不对数组排序也不会有之前那么大的性能差异。这是因为三目运算符在 Release 版本下被优化成条件 mov 指令<code>cmovge</code>，该指令根据<code>cmp</code>产生的 zero 标志位决定是否将源操作数里的内容放进目的操作数，由于不存在条件转移指令那样的分支预测，以及预测失败后需要将指令kill掉的动作，所以不会有性能损失。</p>
</div>
<footer class="article-footer">
<a data-url="http://yoursite.com/2021/04/27/CPU%E5%88%86%E6%94%AF%E9%A2%84%E6%B5%8B%E5%AF%B9%E6%80%A7%E8%83%BD%E7%9A%84%E5%BD%B1%E5%93%8D/" data-id="ckp3d9fal0001gwrt01xoex4d" class="article-share-link">Share</a>
</footer>
</div>
</article>
<article id="post-设计模式" class="article article-type-post" itemscope itemprop="blogPost">
<div class="article-meta">
<a href="/2021/04/12/%E8%AE%BE%E8%AE%A1%E6%A8%A1%E5%BC%8F/" class="article-date">
<time datetime="2021-04-12T02:03:26.000Z" itemprop="datePublished">2021-04-12</time>
</a>
</div>
<div class="article-inner">
<header class="article-header">
<h1 itemprop="name">
<a class="article-title" href="/2021/04/12/%E8%AE%BE%E8%AE%A1%E6%A8%A1%E5%BC%8F/">设计模式</a>
</h1>
</header>
<div class="article-entry" itemprop="articleBody">
<ul>
<li><a href="#单例模式">1.单例模式</a><ul>
<li><a href="#传统实现">传统实现</a></li>
<li><a href="#使用智能指针">使用智能指针</a></li>
<li><a href="#多线程场景的问题">多线程场景的问题</a></li>
<li><a href="#一种更加简洁高效的实现:%20Meyers'%20Singleton">一种更加简洁高效的实现: Meyers’ Singleton</a></li>
</ul>
</li>
<li><a href="#桥接模式">2.桥接模式</a></li>
</ul>
<h2 id="单例模式"><a href="#单例模式" class="headerlink" title="单例模式"></a>单例模式</h2><p>单例属于创建型模式，它提供了一种创建对象的方式。单例模式涉及到一个单一的类，该类负责创建自己的对象，同时确保只有单个对象被创建。这个类提供了一种访问其唯一的对象的方式，可以直接访问，不需要实例化该类的对象。<br><strong>特点：</strong><br>a) 单例类只能有一个实例<br>b) 单例类必须自己创建自己的唯一实例<br>c) 单例类必须给外界提供这一实例<br><strong>意图：</strong>保证一个类仅有一个实例，并提供一个访问它的全局访问点<br><strong>主要解决：</strong>一个全局使用的类频繁地创建与销毁<br><strong>何时使用：</strong>当您想控制实例数目，节省系统资源的时候<br><strong>如何实现：</strong>判断系统是否已经有这个单例类实例，如果有则返回，如果没有则创建<br><strong>关键代码：</strong>构造函数私有化（如果是C++实现还需要禁用拷贝语义）</p>
<h3 id="传统实现"><a href="#传统实现" class="headerlink" title="传统实现"></a>传统实现</h3><figure class="highlight cpp"><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></pre></td><td class="code"><pre><span class="line"><span class="class"><span class="keyword">class</span> <span class="title">SingleObject</span> {</span></span><br><span class="line"> <span class="keyword">private</span>:</span><br><span class="line"> <span class="comment">// 构造函数为 private, 这样外界就不能创建该类的实例</span></span><br><span class="line"> SingleObject() {</span><br><span class="line"> <span class="built_in">std</span>::<span class="built_in">cout</span> << <span class="string">"constructor invoked\n"</span>;</span><br><span class="line"> }</span><br><span class="line"></span><br><span class="line"> <span class="comment">// 该类的唯一静态实例</span></span><br><span class="line"> <span class="keyword">static</span> SingleObject *instance_;</span><br><span class="line"></span><br><span class="line"> <span class="keyword">public</span>:</span><br><span class="line"> <span class="comment">// 禁用拷贝语义</span></span><br><span class="line"> SingleObject(<span class="keyword">const</span> SingleObject &obj) = <span class="keyword">delete</span>;</span><br><span class="line"> SingleObject & <span class="keyword">operator</span>=(<span class="keyword">const</span> SingleObject &obj) = <span class="keyword">delete</span>;</span><br><span class="line"></span><br><span class="line"> <span class="comment">// 析构函数为 public</span></span><br><span class="line"> ~SingleObject() {</span><br><span class="line"> <span class="built_in">std</span>::<span class="built_in">cout</span> << <span class="string">"deconstructor invoked. instance address: 0x"</span> << (<span class="keyword">void</span>*)<span class="keyword">this</span> << <span class="string">"\n"</span>;</span><br><span class="line"> }</span><br><span class="line"></span><br><span class="line"> <span class="comment">// 获取该类的唯一静态实例</span></span><br><span class="line"> <span class="function"><span class="keyword">static</span> SingleObject *<span class="title">GetInstance</span><span class="params">()</span> </span>{</span><br><span class="line"> <span class="keyword">if</span> (instance_ == <span class="literal">nullptr</span>) {</span><br><span class="line"> instance_ = <span class="keyword">new</span> SingleObject;</span><br><span class="line"> }</span><br><span class="line"> <span class="keyword">return</span> instance_;</span><br><span class="line"> }</span><br><span class="line"></span><br><span class="line"> <span class="function"><span class="keyword">void</span> <span class="title">ShowMessage</span><span class="params">()</span> </span>{</span><br><span class="line"> <span class="built_in">std</span>::<span class="built_in">cout</span> << <span class="string">"instance address: 0x"</span> << (<span class="keyword">void</span>*)<span class="keyword">this</span> << <span class="string">"\n"</span>;</span><br><span class="line"> }</span><br><span class="line">};</span><br><span class="line"></span><br><span class="line">SingleObject *SingleObject::instance_ = <span class="literal">nullptr</span>;</span><br><span class="line"></span><br><span class="line"><span class="function"><span class="keyword">int</span> <span class="title">main</span><span class="params">()</span> </span>{</span><br><span class="line"> SingleObject *obj1 = SingleObject::GetInstance();</span><br><span class="line"> SingleObject *obj2 = SingleObject::GetInstance();</span><br><span class="line"> obj1->ShowMessage();</span><br><span class="line"> obj2->ShowMessage();</span><br><span class="line">}</span><br></pre></td></tr></table></figure>
<p>输出:</p>
<figure class="highlight plain"><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">constructor invoked</span><br><span class="line">instance address: 0x00795D58</span><br><span class="line">instance address: 0x00795D58</span><br></pre></td></tr></table></figure>
<p>从输出结果可知，<code>SingleObject</code>只被实例化了一次，并且两次调用<code>SingleObject::GetInstance()</code>返回的都是同一个实例，符合单例模式的语义。</p>
<p>上述代码存在的问题是，<code>SingleObject</code>的“唯一静态实例”没有被<code>delete</code>。如果在<code>main()</code>里面<code>delete</code>要怎么实现（在析构函数为<code>public</code>的前提下）？有两种写法：</p>
<p>代码1.1：</p>
<figure class="highlight cpp"><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></pre></td><td class="code"><pre><span class="line"><span class="function"><span class="keyword">int</span> <span class="title">main</span><span class="params">()</span> </span>{</span><br><span class="line"> SingleObject *obj1 = SingleObject::GetInstance();</span><br><span class="line"> SingleObject *obj2 = SingleObject::GetInstance();</span><br><span class="line"> obj1->ShowMessage();</span><br><span class="line"> obj2->ShowMessage();</span><br><span class="line"></span><br><span class="line"> <span class="keyword">delete</span> obj1;</span><br><span class="line"> <span class="comment">// 或者 delete obj2;</span></span><br><span class="line">}</span><br></pre></td></tr></table></figure>
<p>代码1.2：</p>
<figure class="highlight cpp"><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></pre></td><td class="code"><pre><span class="line"><span class="function"><span class="keyword">int</span> <span class="title">main</span><span class="params">()</span> </span>{</span><br><span class="line"> SingleObject *obj1 = SingleObject::GetInstance();</span><br><span class="line"> SingleObject *obj2 = SingleObject::GetInstance();</span><br><span class="line"> obj1->ShowMessage();</span><br><span class="line"> obj2->ShowMessage();</span><br><span class="line"></span><br><span class="line"> <span class="keyword">delete</span> SingleObject::GetInstance();</span><br><span class="line">}</span><br></pre></td></tr></table></figure>
<p>代码1.1的问题是，<code>obj1</code>和<code>obj2</code>都指向一个对象，所以只能<code>delete</code>一个，否则会发生<em>double free</em>。这使得代码写起来很混乱，需要外界清楚单例模式的实现细节。代码1.2较简洁一些，但仍需外界清楚单例模式的实现细节。我们希望在<code>main()</code>里不编写<code>delete</code>语句的前提下完成对象的释放，一种解决方法是使用智能指针，如下所示：</p>
<h3 id="使用智能指针"><a href="#使用智能指针" class="headerlink" title="使用智能指针"></a>使用智能指针</h3><figure class="highlight cpp"><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></pre></td><td class="code"><pre><span class="line"><span class="class"><span class="keyword">class</span> <span class="title">SingleObject</span> {</span></span><br><span class="line"> <span class="keyword">private</span>:</span><br><span class="line"> <span class="comment">// 构造函数为 private, 这样外界就不能创建该类的实例</span></span><br><span class="line"> SingleObject() {</span><br><span class="line"> <span class="built_in">std</span>::<span class="built_in">cout</span> << <span class="string">"constructor invoked\n"</span>;</span><br><span class="line"> }</span><br><span class="line"></span><br><span class="line"> <span class="comment">// 该类的唯一静态实例</span></span><br><span class="line"> <span class="keyword">static</span> <span class="built_in">std</span>::<span class="built_in">shared_ptr</span><SingleObject> instance_;</span><br><span class="line"></span><br><span class="line"> <span class="keyword">public</span>:</span><br><span class="line"> <span class="comment">// 禁用拷贝语义</span></span><br><span class="line"> SingleObject(<span class="keyword">const</span> SingleObject &obj) = <span class="keyword">delete</span>;</span><br><span class="line"> SingleObject & <span class="keyword">operator</span>=(<span class="keyword">const</span> SingleObject &obj) = <span class="keyword">delete</span>;</span><br><span class="line"></span><br><span class="line"> <span class="comment">// 析构函数为 public</span></span><br><span class="line"> ~SingleObject() {</span><br><span class="line"> <span class="built_in">std</span>::<span class="built_in">cout</span> << <span class="string">"deconstructor invoked. instance address: 0x"</span> << (<span class="keyword">void</span>*)<span class="keyword">this</span> << <span class="string">"\n"</span>;</span><br><span class="line"> }</span><br><span class="line"></span><br><span class="line"> <span class="comment">// 获取该类的唯一静态实例</span></span><br><span class="line"> <span class="function"><span class="keyword">static</span> SingleObject *<span class="title">GetInstance</span><span class="params">()</span> </span>{</span><br><span class="line"> <span class="keyword">if</span> (instance_.get() == <span class="literal">nullptr</span>) {</span><br><span class="line"> instance_ = <span class="built_in">std</span>::<span class="built_in">shared_ptr</span><SingleObject>(<span class="keyword">new</span> SingleObject);</span><br><span class="line"> }</span><br><span class="line"> <span class="keyword">return</span> instance_.get();</span><br><span class="line"> }</span><br><span class="line"></span><br><span class="line"> <span class="function"><span class="keyword">void</span> <span class="title">ShowMessage</span><span class="params">()</span> </span>{</span><br><span class="line"> <span class="built_in">std</span>::<span class="built_in">cout</span> << <span class="string">"instance address: 0x"</span> << (<span class="keyword">void</span>*)<span class="keyword">this</span> << <span class="string">"\n"</span>;</span><br><span class="line"> }</span><br><span class="line">};</span><br><span class="line"></span><br><span class="line"><span class="built_in">std</span>::<span class="built_in">shared_ptr</span><SingleObject> SingleObject::instance_{ <span class="literal">nullptr</span> };</span><br><span class="line"></span><br><span class="line"><span class="function"><span class="keyword">int</span> <span class="title">main</span><span class="params">()</span> </span>{</span><br><span class="line"> SingleObject *obj1 = SingleObject::GetInstance();</span><br><span class="line"> SingleObject *obj2 = SingleObject::GetInstance();</span><br><span class="line"> obj1->ShowMessage();</span><br><span class="line"> obj2->ShowMessage();</span><br><span class="line">}</span><br></pre></td></tr></table></figure>
<p>输出：</p>
<figure class="highlight plain"><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></pre></td><td class="code"><pre><span class="line">constructor invoked</span><br><span class="line">instance address: 0x008A5D58</span><br><span class="line">instance address: 0x008A5D58</span><br><span class="line">deconstructor invoked. instance address: 0x008A5D58</span><br></pre></td></tr></table></figure>
<p>在这里，<code>SingleObject</code>的唯一静态实例<code>instance_</code>本质上是一个静态（全局）<code>std::shared_ptr</code>对象，而不再是一个<code>SingleObject</code>对象指针，所以可以利用程序最后析构全局对象的动作把<code>GetInstance()</code> <code>new</code>出来的<code>SingleObject</code>对象<code>delete</code>掉。</p>
<p>至此通过智能指针实现了一个简单的单例模式。</p>
<h3 id="多线程场景的问题"><a href="#多线程场景的问题" class="headerlink" title="多线程场景的问题"></a>多线程场景的问题</h3><p>在单线程场景下对<code>SingleObject</code>的唯一静态实例<code>instance_</code>的访问是没有问题的，但在多线程场景下会发生读写冲突，而且不能保证单例模式的语义。以下是对上述基于智能指针所实现的单例模式的多线程测试：</p>
<figure class="highlight cpp"><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></pre></td><td class="code"><pre><span class="line"><span class="function"><span class="keyword">int</span> <span class="title">main</span><span class="params">()</span> </span>{</span><br><span class="line"> <span class="keyword">enum</span> {kThreads = <span class="number">4</span>};</span><br><span class="line"> <span class="built_in">std</span>::thread thds[kThreads];</span><br><span class="line"> <span class="keyword">for</span> (<span class="keyword">int</span> i = <span class="number">0</span>; i < kThreads; i++) {</span><br><span class="line"> thds[i] = <span class="built_in">std</span>::thread([&] {</span><br><span class="line"> SingleObject *obj = SingleObject::GetInstance();</span><br><span class="line"> obj->ShowMessage();</span><br><span class="line"> });</span><br><span class="line"> }</span><br><span class="line"></span><br><span class="line"> <span class="keyword">for</span> (<span class="keyword">int</span> i = <span class="number">0</span>; i < kThreads; i++) {</span><br><span class="line"> thds[i].join();</span><br><span class="line"> }</span><br><span class="line">}</span><br></pre></td></tr></table></figure>
<p>输出：</p>
<figure class="highlight plain"><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">constructor invoked</span><br><span class="line">constructor invoked</span><br><span class="line">deconstructor invoked. instance address: 0x0034D7B8</span><br><span class="line">instance address: 0x0034D7B8</span><br><span class="line">constructor invoked</span><br><span class="line">instance address: 0x0034D7E8</span><br><span class="line">deconstructor invoked. instance address: 0x0034D7E8</span><br><span class="line">constructor invoked</span><br><span class="line">instance address: 0x0034D848</span><br><span class="line">deconstructor invoked. instance address: 0x0034D848</span><br><span class="line">instance address: 0x0034D818</span><br><span class="line">deconstructor invoked. instance address: 0x0034D818</span><br></pre></td></tr></table></figure>
<p>显然创建了多个实例，不符合单例模式的语义。最简单的方式是加锁：</p>
<figure class="highlight cpp"><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></pre></td><td class="code"><pre><span class="line"><span class="class"><span class="keyword">class</span> <span class="title">SingleObject</span> {</span></span><br><span class="line"> <span class="keyword">private</span>:</span><br><span class="line"> <span class="comment">// 构造函数为 private, 这样外界就不能创建该类的实例</span></span><br><span class="line"> SingleObject() {</span><br><span class="line"> <span class="built_in">std</span>::<span class="built_in">cout</span> << <span class="string">"constructor invoked\n"</span>;</span><br><span class="line"> }</span><br><span class="line"></span><br><span class="line"> <span class="comment">// 该类的唯一静态实例</span></span><br><span class="line"> <span class="keyword">static</span> <span class="built_in">std</span>::<span class="built_in">shared_ptr</span><SingleObject> instance_;</span><br><span class="line"></span><br><span class="line"> <span class="keyword">static</span> <span class="built_in">std</span>::mutex mu_;</span><br><span class="line"></span><br><span class="line"> <span class="keyword">public</span>:</span><br><span class="line"> <span class="comment">// 禁用拷贝语义</span></span><br><span class="line"> SingleObject(<span class="keyword">const</span> SingleObject &obj) = <span class="keyword">delete</span>;</span><br><span class="line"> SingleObject &<span class="keyword">operator</span>=(<span class="keyword">const</span> SingleObject &obj) = <span class="keyword">delete</span>;</span><br><span class="line"></span><br><span class="line"> <span class="comment">// 析构函数为 public</span></span><br><span class="line"> ~SingleObject() {</span><br><span class="line"> <span class="built_in">std</span>::<span class="built_in">cout</span> << <span class="string">"deconstructor invoked. instance address: 0x"</span> << (<span class="keyword">void</span>*)<span class="keyword">this</span> << <span class="string">"\n"</span>;</span><br><span class="line"> }</span><br><span class="line"></span><br><span class="line"> <span class="comment">// 获取该类的唯一静态实例</span></span><br><span class="line"> <span class="function"><span class="keyword">static</span> SingleObject *<span class="title">GetInstance</span><span class="params">()</span> </span>{</span><br><span class="line"> <span class="built_in">std</span>::lock_guard<<span class="built_in">std</span>::mutex> l(mu_);</span><br><span class="line"> <span class="keyword">if</span> (instance_.get() == <span class="literal">nullptr</span>) {</span><br><span class="line"> instance_ = <span class="built_in">std</span>::<span class="built_in">shared_ptr</span><SingleObject>(<span class="keyword">new</span> SingleObject);</span><br><span class="line"> }</span><br><span class="line"> <span class="keyword">return</span> instance_.get();</span><br><span class="line"> }</span><br><span class="line"></span><br><span class="line"> <span class="function"><span class="keyword">void</span> <span class="title">ShowMessage</span><span class="params">()</span> </span>{</span><br><span class="line"> <span class="built_in">std</span>::<span class="built_in">cout</span> << <span class="string">"instance address: 0x"</span> << (<span class="keyword">void</span>*)<span class="keyword">this</span> << <span class="string">"\n"</span>;</span><br><span class="line"> }</span><br><span class="line">};</span><br><span class="line"></span><br><span class="line"><span class="built_in">std</span>::<span class="built_in">shared_ptr</span><SingleObject> SingleObject::instance_{ <span class="literal">nullptr</span> };</span><br><span class="line"><span class="built_in">std</span>::mutex SingleObject::mu_;</span><br><span class="line"></span><br><span class="line"><span class="function"><span class="keyword">int</span> <span class="title">main</span><span class="params">()</span> </span>{</span><br><span class="line"> <span class="keyword">enum</span> {kThreads = <span class="number">4</span>};</span><br><span class="line"> <span class="built_in">std</span>::thread thds[kThreads];</span><br><span class="line"> <span class="keyword">for</span> (<span class="keyword">int</span> i = <span class="number">0</span>; i < kThreads; i++) {</span><br><span class="line"> thds[i] = <span class="built_in">std</span>::thread([&] {</span><br><span class="line"> SingleObject *obj = SingleObject::GetInstance();</span><br><span class="line"> obj->ShowMessage();</span><br><span class="line"> });</span><br><span class="line"> }</span><br><span class="line"></span><br><span class="line"> <span class="keyword">for</span> (<span class="keyword">int</span> i = <span class="number">0</span>; i < kThreads; i++) {</span><br><span class="line"> thds[i].join();</span><br><span class="line"> }</span><br><span class="line">}</span><br></pre></td></tr></table></figure>
<p>输出：</p>
<figure class="highlight plain"><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></pre></td><td class="code"><pre><span class="line">constructor invoked</span><br><span class="line">instance address: 0x0076D810</span><br><span class="line">instance address: 0x0076D810</span><br><span class="line">instance address: 0x0076D810</span><br><span class="line">instance address: 0x0076D810</span><br><span class="line">deconstructor invoked. instance address: 0x0076D810</span><br></pre></td></tr></table></figure>
<p>上面这种在整个<code>GetInstance()</code>函数内加锁的方式虽然保证了线程安全，但是效率很低。<strong>Double-Checked Locking</strong>方法被广泛用于实现多线程环境下单例模式懒惰加载方式实现，代码如下：</p>
<figure class="highlight cpp"><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></pre></td><td class="code"><pre><span class="line"><span class="function"><span class="keyword">static</span> SingleObject *<span class="title">GetInstance</span><span class="params">()</span> </span>{</span><br><span class="line"> <span class="keyword">if</span> (instance_.get() == <span class="literal">nullptr</span>) {</span><br><span class="line"> <span class="built_in">std</span>::lock_guard<<span class="built_in">std</span>::mutex> l(mu_);</span><br><span class="line"> <span class="keyword">if</span> (instance_.get() == <span class="literal">nullptr</span>) {</span><br><span class="line"> instance_ = <span class="built_in">std</span>::<span class="built_in">shared_ptr</span><SingleObject>(<span class="keyword">new</span> SingleObject);</span><br><span class="line"> }</span><br><span class="line"> }</span><br><span class="line"> <span class="keyword">return</span> instance_.get();</span><br><span class="line">}</span><br></pre></td></tr></table></figure>
<p>第4行的第2次<code>if</code>检查语句是必要的，否则会发生重复构造，进而产生内存泄漏。</p>
<p>但是这样还不够。这种实现依赖于处理器的内存模型、编译器的重排序以及编译器和同步库之间的工作方式。在某些内存模型中（虽然不常见）或者是由于编译器的优化以及运行时优化等等原因，使得<code>instance_</code>虽然已经不是<code>nullptr</code>但是其所指对象还没有完成构造，这种情况下，另一个线程如果调用<code>GetInstance()</code>就有可能使用到一个不完全初始化的对象。换句话说，就是代码中第4行和第5行没有正确的同步，在某种情况下会出现<code>new</code>返回了地址赋值给<code>instance_</code>而<code>SingleObject</code>此时还没有构造完全，当另一个线程随后运行到第2行时将不会进入<code>if</code>从而返回了不完全的实例对象给用户使用，造成了严重的错误。</p>
<p>要解决这个问题需要使用<code>std::atomic</code>提供的内存模型。先上代码：</p>
<figure class="highlight cpp"><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></pre></td><td class="code"><pre><span class="line"><span class="class"><span class="keyword">class</span> <span class="title">SingleObject</span> {</span></span><br><span class="line"> <span class="keyword">private</span>:</span><br><span class="line"> <span class="comment">// 构造函数为 private, 这样外界就不能创建该类的实例</span></span><br><span class="line"> SingleObject() {</span><br><span class="line"> <span class="built_in">std</span>::<span class="built_in">cout</span> << <span class="string">"constructor invoked\n"</span>;</span><br><span class="line"> }</span><br><span class="line"></span><br><span class="line"> <span class="comment">// 该类的唯一静态实例</span></span><br><span class="line"> <span class="keyword">static</span> <span class="built_in">std</span>::atomic<<span class="built_in">std</span>::<span class="built_in">shared_ptr</span><SingleObject>> instance_;</span><br><span class="line"></span><br><span class="line"> <span class="keyword">static</span> <span class="built_in">std</span>::mutex mu_;</span><br><span class="line"></span><br><span class="line"> <span class="keyword">public</span>:</span><br><span class="line"> <span class="comment">// 禁用拷贝语义</span></span><br><span class="line"> SingleObject(<span class="keyword">const</span> SingleObject &obj) = <span class="keyword">delete</span>;</span><br><span class="line"> SingleObject & <span class="keyword">operator</span>=(<span class="keyword">const</span> SingleObject &obj) = <span class="keyword">delete</span>;</span><br><span class="line"></span><br><span class="line"> <span class="comment">// 析构函数为 public</span></span><br><span class="line"> ~SingleObject() {</span><br><span class="line"> <span class="built_in">std</span>::<span class="built_in">cout</span> << <span class="string">"deconstructor invoked. instance address: 0x"</span> << (<span class="keyword">void</span>*)<span class="keyword">this</span> << <span class="string">"\n"</span>;</span><br><span class="line"> }</span><br><span class="line"></span><br><span class="line"> <span class="comment">// 获取该类的唯一静态实例</span></span><br><span class="line"> <span class="function"><span class="keyword">static</span> SingleObject *<span class="title">GetInstance</span><span class="params">()</span> </span>{</span><br><span class="line"> <span class="comment">// 默认使用 memory_order_seq_cst, sequential consistency (顺序一致性)</span></span><br><span class="line"> SingleObject *obj;</span><br><span class="line"> <span class="keyword">if</span> ((obj = instance_.load().get()) == <span class="literal">nullptr</span>) {</span><br><span class="line"> <span class="built_in">std</span>::lock_guard<<span class="built_in">std</span>::mutex> l(mu_);</span><br><span class="line"> <span class="keyword">if</span> ((obj = instance_.load().get()) == <span class="literal">nullptr</span>) {</span><br><span class="line"> obj = <span class="keyword">new</span> SingleObject;</span><br><span class="line"> instance_.store(<span class="built_in">std</span>::<span class="built_in">shared_ptr</span><SingleObject>(obj));</span><br><span class="line"> }</span><br><span class="line"> }</span><br><span class="line"> <span class="keyword">return</span> obj;</span><br><span class="line"> }</span><br><span class="line"></span><br><span class="line"> <span class="function"><span class="keyword">void</span> <span class="title">ShowMessage</span><span class="params">()</span> </span>{</span><br><span class="line"> <span class="built_in">std</span>::<span class="built_in">cout</span> << <span class="string">"instance address: 0x"</span> << (<span class="keyword">void</span>*)<span class="keyword">this</span> << <span class="string">"\n"</span>;</span><br><span class="line"> }</span><br><span class="line">};</span><br><span class="line"></span><br><span class="line"><span class="built_in">std</span>::atomic<<span class="built_in">std</span>::<span class="built_in">shared_ptr</span><SingleObject>> SingleObject::instance_{ <span class="literal">nullptr</span> };</span><br><span class="line"><span class="built_in">std</span>::mutex SingleObject::mu_;</span><br></pre></td></tr></table></figure>
<p>这里使用了<code>std::atomic</code>默认的<code>memory_order_seq_cst</code>内存模型（<code>load</code>需要等待<code>store</code>写完才能读取，所以叫“顺序一致性”）保证代码不会出现同步问题（至于为什么，我也不知道，涉及体系结构的细节，以上参考<a href="https://zhuanlan.zhihu.com/p/37469260" target="_blank" rel="noopener">https://zhuanlan.zhihu.com/p/37469260</a>）。但是这样做又导致了一个严重错误：</p>
<figure class="highlight plain"><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></pre></td><td class="code"><pre><span class="line">constructor invoked</span><br><span class="line">deconstructor invoked. instance address: 0x003AD810</span><br><span class="line">instance address: 0x003AD810</span><br><span class="line">instance address: 0x003AD810</span><br><span class="line">instance address: 0x003AD810</span><br><span class="line">instance address: 0x003AD810</span><br></pre></td></tr></table></figure>
<p>析构函数竟然先执行了！怀疑是智能指针的问题，那么不用智能指针，向<code>SingleObject</code>内嵌一个<code>GC</code>类的静态实例进行<code>instance_</code>的析构吧：</p>
<figure class="highlight cpp"><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></pre></td><td class="code"><pre><span class="line"><span class="class"><span class="keyword">class</span> <span class="title">SingleObject</span> {</span></span><br><span class="line"> <span class="keyword">private</span>:</span><br><span class="line"> <span class="comment">// 构造函数为 private, 这样外界就不能创建该类的实例</span></span><br><span class="line"> SingleObject() {</span><br><span class="line"> <span class="keyword">static</span> GC gc;</span><br><span class="line"> <span class="built_in">std</span>::<span class="built_in">cout</span> << <span class="string">"constructor invoked\n"</span>;</span><br><span class="line"> }</span><br><span class="line"></span><br><span class="line"> <span class="comment">// 该类的唯一静态实例</span></span><br><span class="line"> <span class="keyword">static</span> <span class="built_in">std</span>::atomic<SingleObject*> instance_;</span><br><span class="line"></span><br><span class="line"> <span class="keyword">static</span> <span class="built_in">std</span>::mutex mu_;</span><br><span class="line"></span><br><span class="line"> <span class="class"><span class="keyword">class</span> <span class="title">GC</span> {</span></span><br><span class="line"> <span class="keyword">public</span>:</span><br><span class="line"> GC() = <span class="keyword">default</span>;</span><br><span class="line"> ~GC() {</span><br><span class="line"> SingleObject *obj = instance_.load();</span><br><span class="line"> <span class="keyword">if</span> (obj != <span class="literal">nullptr</span>) {</span><br><span class="line"> <span class="keyword">delete</span> obj;</span><br><span class="line"> instance_.store(<span class="literal">nullptr</span>);</span><br><span class="line"> }</span><br><span class="line"> }</span><br><span class="line"></span><br><span class="line"> GC(<span class="keyword">const</span> GC &g) = <span class="keyword">delete</span>;</span><br><span class="line"> GC& <span class="keyword">operator</span>=(<span class="keyword">const</span> GC &g) = <span class="keyword">delete</span>;</span><br><span class="line"> };</span><br><span class="line"></span><br><span class="line"> <span class="keyword">public</span>:</span><br><span class="line"> <span class="comment">// 禁用拷贝语义</span></span><br><span class="line"> SingleObject(<span class="keyword">const</span> SingleObject &obj) = <span class="keyword">delete</span>;</span><br><span class="line"> SingleObject & <span class="keyword">operator</span>=(<span class="keyword">const</span> SingleObject &obj) = <span class="keyword">delete</span>;</span><br><span class="line"></span><br><span class="line"> <span class="comment">// 析构函数为 public</span></span><br><span class="line"> ~SingleObject() {</span><br><span class="line"> <span class="built_in">std</span>::<span class="built_in">cout</span> << <span class="string">"deconstructor invoked. instance address: 0x"</span> << (<span class="keyword">void</span>*)<span class="keyword">this</span> << <span class="string">"\n"</span>;</span><br><span class="line"> }</span><br><span class="line"></span><br><span class="line"> <span class="comment">// 获取该类的唯一静态实例</span></span><br><span class="line"> <span class="function"><span class="keyword">static</span> SingleObject *<span class="title">GetInstance</span><span class="params">()</span> </span>{</span><br><span class="line"> <span class="comment">// 默认使用 memory_order_seq_cst, sequential consistency (顺序一致性)</span></span><br><span class="line"> SingleObject *obj;</span><br><span class="line"> <span class="keyword">if</span> ((obj = instance_.load()) == <span class="literal">nullptr</span>) {</span><br><span class="line"> <span class="built_in">std</span>::lock_guard<<span class="built_in">std</span>::mutex> l(mu_);</span><br><span class="line"> <span class="keyword">if</span> ((obj = instance_.load()) == <span class="literal">nullptr</span>) {</span><br><span class="line"> obj = <span class="keyword">new</span> SingleObject;</span><br><span class="line"> instance_.store(obj);</span><br><span class="line"> }</span><br><span class="line"> }</span><br><span class="line"> <span class="keyword">return</span> obj;</span><br><span class="line"> }</span><br><span class="line"></span><br><span class="line"> <span class="function"><span class="keyword">void</span> <span class="title">ShowMessage</span><span class="params">()</span> </span>{</span><br><span class="line"> <span class="built_in">std</span>::<span class="built_in">cout</span> << <span class="string">"instance address: 0x"</span> << (<span class="keyword">void</span>*)<span class="keyword">this</span> << <span class="string">"\n"</span>;</span><br><span class="line"> }</span><br><span class="line">};</span><br><span class="line"></span><br><span class="line"><span class="built_in">std</span>::atomic<SingleObject*> SingleObject::instance_{ <span class="literal">nullptr</span> };</span><br><span class="line"><span class="built_in">std</span>::mutex SingleObject::mu_;</span><br></pre></td></tr></table></figure>
<p>可以得到正确的输出：</p>
<figure class="highlight plain"><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></pre></td><td class="code"><pre><span class="line">constructor invoked</span><br><span class="line">instance address: 0x004CD810</span><br><span class="line">instance address: 0x004CD810</span><br><span class="line">instance address: 0x004CD810</span><br><span class="line">instance address: 0x004CD810</span><br><span class="line">deconstructor invoked. instance address: 0x004CD810</span><br></pre></td></tr></table></figure>
<p>综上，利用“Double-Checked Locking+内存屏障”可以实现一个线程安全的单例模式。</p>
<h3 id="一种更加简洁高效的实现-Meyers’-Singleton"><a href="#一种更加简洁高效的实现-Meyers’-Singleton" class="headerlink" title="一种更加简洁高效的实现: Meyers’ Singleton"></a>一种更加简洁高效的实现: Meyers’ Singleton</h3><p>来自<em>Effective C++</em> item 04，使用 local static 变量：</p>
<figure class="highlight cpp"><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></pre></td><td class="code"><pre><span class="line"><span class="class"><span class="keyword">class</span> <span class="title">SingleObject</span> {</span></span><br><span class="line"> <span class="keyword">private</span>:</span><br><span class="line"> <span class="comment">// 构造函数为 private, 这样外界就不能创建该类的实例</span></span><br><span class="line"> SingleObject() {</span><br><span class="line"> <span class="built_in">std</span>::<span class="built_in">cout</span> << <span class="string">"constructor invoked\n"</span>;</span><br><span class="line"> }</span><br><span class="line"></span><br><span class="line"> <span class="keyword">public</span>:</span><br><span class="line"> <span class="comment">// 禁用拷贝语义</span></span><br><span class="line"> SingleObject(<span class="keyword">const</span> SingleObject &obj) = <span class="keyword">delete</span>;</span><br><span class="line"> SingleObject & <span class="keyword">operator</span>=(<span class="keyword">const</span> SingleObject &obj) = <span class="keyword">delete</span>;</span><br><span class="line"></span><br><span class="line"> <span class="comment">// 析构函数为 public</span></span><br><span class="line"> ~SingleObject() {</span><br><span class="line"> <span class="built_in">std</span>::<span class="built_in">cout</span> << <span class="string">"deconstructor invoked. instance address: 0x"</span> << (<span class="keyword">void</span>*)<span class="keyword">this</span> << <span class="string">"\n"</span>;</span><br><span class="line"> }</span><br><span class="line"></span><br><span class="line"> <span class="comment">// 获取该类的唯一静态实例</span></span><br><span class="line"> <span class="function"><span class="keyword">static</span> SingleObject &<span class="title">GetInstance</span><span class="params">()</span> </span>{</span><br><span class="line"> <span class="comment">// 仅当第一次调用该函数时执行 instance 的初始化</span></span><br><span class="line"> <span class="keyword">static</span> SingleObject instance;</span><br><span class="line"> <span class="keyword">return</span> instance;</span><br><span class="line"> }</span><br><span class="line"></span><br><span class="line"> <span class="function"><span class="keyword">void</span> <span class="title">ShowMessage</span><span class="params">()</span> </span>{</span><br><span class="line"> <span class="built_in">std</span>::<span class="built_in">cout</span> << <span class="string">"instance address: 0x"</span> << (<span class="keyword">void</span>*)<span class="keyword">this</span> << <span class="string">"\n"</span>;</span><br><span class="line"> }</span><br><span class="line">};</span><br><span class="line"></span><br><span class="line"><span class="function"><span class="keyword">int</span> <span class="title">main</span><span class="params">()</span> </span>{</span><br><span class="line"> <span class="keyword">enum</span> {kThreads = <span class="number">4</span>};</span><br><span class="line"> <span class="built_in">std</span>::thread thds[kThreads];</span><br><span class="line"> <span class="keyword">for</span> (<span class="keyword">int</span> i = <span class="number">0</span>; i < kThreads; i++) {</span><br><span class="line"> thds[i] = <span class="built_in">std</span>::thread([&] {</span><br><span class="line"> SingleObject &obj = SingleObject::GetInstance();</span><br><span class="line"> obj.ShowMessage();</span><br><span class="line"> });</span><br><span class="line"> }</span><br><span class="line"></span><br><span class="line"> <span class="keyword">for</span> (<span class="keyword">int</span> i = <span class="number">0</span>; i < kThreads; i++) {</span><br><span class="line"> thds[i].join();</span><br><span class="line"> }</span><br><span class="line">}</span><br></pre></td></tr></table></figure>
<p>输出：</p>
<figure class="highlight plain"><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></pre></td><td class="code"><pre><span class="line">constructor invoked</span><br><span class="line">instance address: 0x00E24A5C</span><br><span class="line">instance address: 0x00E24A5C</span><br><span class="line">instance address: 0x00E24A5C</span><br><span class="line">instance address: 0x00E24A5C</span><br><span class="line">deconstructor invoked. instance address: 0x00E24A5C</span><br></pre></td></tr></table></figure>
<p>该实现方式甚至保证了线程安全！世人以<em>Effective C++</em>一书的作者之名，将这种单例模式的实现命名为<em>Meyers’ Singleton</em>。</p>
<p>注意，在C++11之前，多线程环境下local static对象的初始化并不是线程安全的。具体表现就是：如果一个线程正在执行local static对象的初始化语句但还没有完成，此时若其它线程也执行到该语句，那么这个线程会认为自己是第一次执行初始化并进入该local static对象的构造函数中。这会造成这个local static对象的重复构造，进而产生内存泄露问题。</p>
<p>C++11则在语言规范中解决了这个问题。C++11规定，在一个线程开始local static对象的初始化后到完成初始化前，其他线程执行到这个local static对象的初始化语句就会等待，直到该local static对象初始化完成。</p>
<h2 id="桥接模式"><a href="#桥接模式" class="headerlink" title="桥接模式"></a>桥接模式</h2><ul>
<li>桥接模式用于把抽象化和实例化解耦，使得二者可以独立变化。桥接模式属于结构型模式，它通过提供抽象化和实例化之间的桥接结构，来实现二者的解耦。</li>
<li>参照下面的例子，桥接模式涉及到一个桥接接口(<code>DrawAPI</code>)，使得实体类(<code>Circle</code>)独立于桥接接口的实现类(<code>RedCircle</code>, <code>GreenCircle</code>)。通过使用相同的抽象类方法<code>Shape::draw()</code>但是不同的桥接实现类，来画出不同颜色的圆。</li>
</ul>
<p><img src="/2021/04/12/%E8%AE%BE%E8%AE%A1%E6%A8%A1%E5%BC%8F/bridge_pattern_demo.png" alt></p>
<h3 id="Step-1"><a href="#Step-1" class="headerlink" title="Step 1"></a>Step 1</h3><p>创建桥接接口<code>DrawAPI</code>:</p>
<figure class="highlight cpp"><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></pre></td><td class="code"><pre><span class="line"><span class="class"><span class="keyword">class</span> <span class="title">DrawAPI</span> {</span></span><br><span class="line"> <span class="keyword">public</span>:</span><br><span class="line"> DrawAPI() = <span class="keyword">default</span>;</span><br><span class="line"> <span class="keyword">virtual</span> ~DrawAPI() = <span class="keyword">default</span>;</span><br><span class="line"></span><br><span class="line"> <span class="function"><span class="keyword">virtual</span> <span class="keyword">void</span> <span class="title">drawCircle</span><span class="params">(<span class="keyword">int</span> x, <span class="keyword">int</span> y, <span class="keyword">int</span> r)</span> </span>= <span class="number">0</span>;</span><br><span class="line">};</span><br></pre></td></tr></table></figure>
<h3 id="Step-2"><a href="#Step-2" class="headerlink" title="Step 2"></a>Step 2</h3><p>创建桥接接口<code>DrawAPI</code>的实现类<code>RedCircle</code>和<code>GreenCircle</code>:</p>
<figure class="highlight cpp"><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></pre></td><td class="code"><pre><span class="line"><span class="class"><span class="keyword">class</span> <span class="title">RedCircle</span> :</span> <span class="keyword">public</span> DrawAPI {</span><br><span class="line"> <span class="keyword">public</span>:</span><br><span class="line"> <span class="function"><span class="keyword">virtual</span> <span class="keyword">void</span> <span class="title">drawCircle</span><span class="params">(<span class="keyword">int</span> x, <span class="keyword">int</span> y, <span class="keyword">int</span> r)</span> <span class="keyword">override</span> </span>{</span><br><span class="line"> <span class="built_in">std</span>::<span class="built_in">cout</span> << <span class="string">"Drawing Circle: [color: red -> ("</span></span><br><span class="line"> << x << <span class="string">","</span></span><br><span class="line"> << y << <span class="string">","</span></span><br><span class="line"> << r << <span class="string">")]\n"</span>;</span><br><span class="line"> }</span><br><span class="line">};</span><br><span class="line"></span><br><span class="line"><span class="class"><span class="keyword">class</span> <span class="title">GreenCircle</span> :</span> <span class="keyword">public</span> DrawAPI {</span><br><span class="line"> <span class="keyword">public</span>:</span><br><span class="line"> <span class="function"><span class="keyword">virtual</span> <span class="keyword">void</span> <span class="title">drawCircle</span><span class="params">(<span class="keyword">int</span> x, <span class="keyword">int</span> y, <span class="keyword">int</span> r)</span> <span class="keyword">override</span> </span>{</span><br><span class="line"> <span class="built_in">std</span>::<span class="built_in">cout</span> << <span class="string">"Drawing Circle: [color: green -> ("</span></span><br><span class="line"> << x << <span class="string">","</span></span><br><span class="line"> << y << <span class="string">","</span></span><br><span class="line"> << r << <span class="string">")]\n"</span>;</span><br><span class="line"> }</span><br><span class="line">};</span><br></pre></td></tr></table></figure>
<h3 id="Step-3"><a href="#Step-3" class="headerlink" title="Step 3"></a>Step 3</h3><p>创建依赖桥接接口<code>DrawAPI</code>的抽象类<code>Shape</code>:</p>
<figure class="highlight cpp"><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"><span class="class"><span class="keyword">class</span> <span class="title">Shape</span> {</span></span><br><span class="line"> <span class="keyword">protected</span>:</span><br><span class="line"> DrawAPI *drawAPI_;</span><br><span class="line"> <span class="keyword">public</span>:</span><br><span class="line"> Shape(DrawAPI *drawAPI) : drawAPI_(drawAPI) {}</span><br><span class="line"> <span class="keyword">virtual</span> ~Shape() {</span><br><span class="line"> <span class="keyword">delete</span> drawAPI_;</span><br><span class="line"> }</span><br><span class="line"></span><br><span class="line"> <span class="function"><span class="keyword">virtual</span> <span class="keyword">void</span> <span class="title">draw</span><span class="params">()</span> </span>= <span class="number">0</span>;</span><br><span class="line">};</span><br></pre></td></tr></table></figure>
<h3 id="Step-4"><a href="#Step-4" class="headerlink" title="Step 4"></a>Step 4</h3><p>创建抽象类<code>Shape</code>的派生类<code>Circle</code>:</p>
<figure class="highlight cpp"><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"><span class="class"><span class="keyword">class</span> <span class="title">Circle</span> :</span> <span class="keyword">public</span> Shape {</span><br><span class="line"> <span class="keyword">private</span>:</span><br><span class="line"> <span class="keyword">int</span> x_, y_, r_;</span><br><span class="line"> <span class="keyword">public</span>:</span><br><span class="line"> Circle(<span class="keyword">int</span> x, <span class="keyword">int</span> y, <span class="keyword">int</span> r, DrawAPI *drawAPI) : x_(x), y_(y), r_(r), Shape(drawAPI) {}</span><br><span class="line"> <span class="keyword">virtual</span> ~Circle() = <span class="keyword">default</span>;</span><br><span class="line"></span><br><span class="line"> <span class="function"><span class="keyword">virtual</span> <span class="keyword">void</span> <span class="title">draw</span><span class="params">()</span> <span class="keyword">override</span> </span>{</span><br><span class="line"> drawAPI_->drawCircle(x_, y_, r_);</span><br><span class="line"> }</span><br><span class="line">};</span><br></pre></td></tr></table></figure>
<h3 id="Step-5"><a href="#Step-5" class="headerlink" title="Step 5"></a>Step 5</h3><p>使用实例：</p>
<figure class="highlight cpp"><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></pre></td><td class="code"><pre><span class="line"><span class="function"><span class="keyword">int</span> <span class="title">main</span><span class="params">()</span> </span>{</span><br><span class="line"> Shape *redCircle = <span class="keyword">new</span> Circle(<span class="number">10</span>, <span class="number">10</span>, <span class="number">5</span>, <span class="keyword">new</span> RedCircle);</span><br><span class="line"> Shape *greenCircle = <span class="keyword">new</span> Circle(<span class="number">20</span>, <span class="number">20</span>, <span class="number">5</span>, <span class="keyword">new</span> GreenCircle);</span><br><span class="line"></span><br><span class="line"> redCircle->draw();</span><br><span class="line"> greenCircle->draw();</span><br><span class="line"></span><br><span class="line"> <span class="keyword">delete</span> redCircle;</span><br><span class="line"> <span class="keyword">delete</span> greenCircle;</span><br><span class="line">}</span><br></pre></td></tr></table></figure>
<p>输出结果：</p>
<figure class="highlight plain"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br></pre></td><td class="code"><pre><span class="line">Drawing Circle: [color: red -> (10,10,5)]</span><br><span class="line">Drawing Circle: [color: green -> (20,20,5)]</span><br></pre></td></tr></table></figure>
</div>
<footer class="article-footer">
<a data-url="http://yoursite.com/2021/04/12/%E8%AE%BE%E8%AE%A1%E6%A8%A1%E5%BC%8F/" data-id="ckp3d9fbc000cgwrt99i6dr3m" class="article-share-link">Share</a>
</footer>
</div>
</article>
<article id="post-linux-IO" class="article article-type-post" itemscope itemprop="blogPost">
<div class="article-meta">
<a href="/2021/04/08/linux-IO/" class="article-date">
<time datetime="2021-04-08T14:08:48.000Z" itemprop="datePublished">2021-04-08</time>
</a>
</div>
<div class="article-inner">
<header class="article-header">
<h1 itemprop="name">
<a class="article-title" href="/2021/04/08/linux-IO/">linux IO</a>
</h1>
</header>
<div class="article-entry" itemprop="articleBody">
<h2 id="阻塞IO-vs-非阻塞IO"><a href="#阻塞IO-vs-非阻塞IO" class="headerlink" title="阻塞IO vs. 非阻塞IO"></a>阻塞IO vs. 非阻塞IO</h2><p><strong>阻塞IO</strong>：当没有数据可读时内核会一直等待数据，直到数据准备好后再将数据拷贝到进程空间，然后IO系统调用返回，解除进程的阻塞。<br><img src="/2021/04/08/linux-IO/block_io.png" alt></p>
<p><strong>非阻塞IO</strong>：当没有数据可读时IO系统调用会给进程返回一个错误而不会阻塞，当进程再次发起IO系统调用时，如果内核缓冲区有数据，内核就会把数据拷贝到进程空间。非阻塞IO的编程特点：需要进程轮询调用。<br><img src="/2021/04/08/linux-IO/nonblock_io.png" alt></p>
<p>例子：在一个典型的 socket 服务端程序中通常会有这样的代码片段：</p>
<figure class="highlight c"><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"><span class="keyword">while</span> ((s = <span class="built_in">read</span>(pfds[i].fd, buf, BUF_SIZE)) > <span class="number">0</span>) {</span><br><span class="line"> <span class="built_in">printf</span>(<span class="string">"\nReceived data from client %.*s"</span>, (<span class="keyword">int</span>)s, buf);</span><br><span class="line">}</span><br></pre></td></tr></table></figure>
<p>如果连接套接字是<em>阻塞</em>模式, 当数据读完后 read 会阻塞, 直到该连接上的客户端重新发送数据. 结果就是程序不能继续处理新的客户端连接, 因为程序被阻塞在这里了. 所以我们通常会把连接套接字设置成<em>非阻塞</em>模式:</p>
<figure class="highlight c"><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"><span class="function"><span class="keyword">int</span> <span class="title">setnonblocking</span><span class="params">(<span class="keyword">int</span> sock)</span> </span>{</span><br><span class="line"> <span class="keyword">int</span> opts;</span><br><span class="line"></span><br><span class="line"> <span class="comment">// 获取sock的文件状态标志</span></span><br><span class="line"> opts = fcntl(sock, F_GETFL);</span><br><span class="line"> <span class="keyword">if</span> (opts == <span class="number">-1</span>) {</span><br><span class="line"> perror(<span class="string">"fcntl(sock, F_GETFL)"</span>);</span><br><span class="line"> <span class="keyword">return</span> <span class="number">1</span>;</span><br><span class="line"> }</span><br><span class="line"></span><br><span class="line"> <span class="comment">// 设置非阻塞I/O</span></span><br><span class="line"> opts = opts | O_NONBLOCK;</span><br><span class="line"> <span class="keyword">if</span> (fcntl(sock, F_SETFL, opts) == <span class="number">-1</span>) {</span><br><span class="line"> perror(<span class="string">"fcntl(sock,F_SETFL,opts)"</span>);</span><br><span class="line"> <span class="keyword">return</span> <span class="number">1</span>;</span><br><span class="line"> }</span><br><span class="line"> <span class="keyword">return</span> <span class="number">0</span>;</span><br><span class="line">}</span><br></pre></td></tr></table></figure>
<h2 id="IO多路复用"><a href="#IO多路复用" class="headerlink" title="IO多路复用"></a>IO多路复用</h2><p>简言之就是让一个进程同时监控多个文件描述符，当任意一个文件描述符可读写时解除进程的阻塞。IO多路复用是以<code>select</code>、<code>poll</code>、<code>epoll</code>为基础的。</p>
<h3 id="select-amp-poll"><a href="#select-amp-poll" class="headerlink" title="select & poll"></a><code>select</code> & <code>poll</code></h3><p><code>select</code>和<code>poll</code>非常相似，二者的不同在于保存文件描述符的方式：</p>
<ul>
<li><code>select</code>使用<code>fd_set</code>结构：<figure class="highlight c"><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></pre></td><td class="code"><pre><span class="line"><span class="comment">/* The fd_set member is required to be an array of longs. */</span></span><br><span class="line"><span class="keyword">typedef</span> <span class="keyword">long</span> <span class="keyword">int</span> __fd_mask;</span><br><span class="line"></span><br><span class="line"><span class="comment">/* fd_set for select and pselect. */</span></span><br><span class="line"><span class="keyword">typedef</span> <span class="class"><span class="keyword">struct</span></span></span><br><span class="line"><span class="class">{</span></span><br><span class="line"> __fd_mask fds_bits[__FD_SETSIZE / __NFDBITS];</span><br><span class="line">} fd_set;</span><br></pre></td></tr></table></figure>
</li>
</ul>
<p>这是一个长度固定的数组，所以可保存的文件描述符个数是有限的。</p>
<ul>
<li><code>poll</code>使用的是<code>pollfd</code>结构的变长数组，所以支持的最大文件描述符的数量就是OS支持的最大打开文件描述符的数量。</li>
</ul>
<p><code>select</code>和<code>poll</code>都采用“<strong>水平触发</strong>”，如果报告了fd后没有被处理，或者没有把数据全部读完，那么下次<code>select/poll</code>时会再次报告该fd。</p>
<h3 id="epoll"><a href="#epoll" class="headerlink" title="epoll"></a><code>epoll</code></h3><p><code>epoll</code>可以理解为event poll，是<strong>事件驱动</strong>的。一下内容摘自Linux manual page 对<code>epoll</code>的说明。</p>
<p>The <strong>epoll</strong> API performs a similar task to <strong>poll</strong>: monitoring multiple file descriptors to see if I/O is possible on any of them. The <strong>epoll</strong> API can be used either as an <em>edge-triggered</em> or a <em>level-triggered</em> interface and scales well to large numbers of watched file descriptors.</p>
<p>The central concept of the epoll API is the <strong>epoll</strong> instance, an in-kernel data structure which, from a user-space perspective, can be considered as a container for two lists:</p>
<ul>
<li>The <em>interest</em> list (sometimes also called the <strong>epoll</strong> set): the set of file descriptors that the process has registered an interest in monitoring.</li>
<li>The <em>ready</em> list: the set of file descriptors that are “ready” for I/O. The ready list is a subset of (or, more precisely, a set of references to) the file descriptors in the interest list. The ready list is dynamically populated by the kernel as a result of I/O activity on those file descriptors.</li>
</ul>
<h4 id="Level-triggered-and-edge-triggered"><a href="#Level-triggered-and-edge-triggered" class="headerlink" title="Level-triggered and edge-triggered"></a>Level-triggered and edge-triggered</h4><p>The <strong>epoll</strong> event distribution interface is able to behave both as edge-triggered (ET) and as level-triggered (LT). The difference between the two mechanisms can be described as follows. Suppose that this scenario happens:</p>
<ol>
<li>The file descriptor that represents the read side of a pipe (<em>rfd</em>) is registered on the <strong>epoll</strong> instance.</li>
<li>A pipe writer writes 2 kB of data on the write side of the pipe.</li>
<li>A call to <strong>epoll_wait</strong> is done that will return <em>rfd</em> as a ready file descriptor.</li>
<li>The pipe reader reads 1 kB of data from <em>rfd</em>.</li>
<li>A call to <strong>epoll_wait</strong> is done.</li>
</ol>
<p>If the <em>rfd</em> file descriptor has been added to the <strong>epoll</strong> interface using the <strong>EPOLLET</strong> (edge-triggered) flag, the call to <strong>epoll_wait</strong> done in step 5 will probably hang despite the available data still present in the file input buffer; meanwhile the remote peer might be expecting a response based on the data it already sent. The reason for this is that edge-triggered mode delivers events only when changes occur on the monitored file descriptor. So, in step 5 the caller might end up waiting for some data that is already present inside the input buffer. In the above example, an event on <em>rfd</em> will be generated because of the write done in 2 and the event is consumed in 3. Since the read operation done in 4 does not consume the whole buffer data, the call to <strong>epoll_wait</strong> done in step 5 might block indefinitely.</p>
<p>An application that employs the <strong>EPOLLET</strong> flag should use nonblocking file descriptors to avoid having a blocking read or write starve a task that is handling multiple file descriptors. The suggested way to use epoll as an edge-triggered (<strong>EPOLLET</strong>) interface is as follows:</p>
<p>a) with nonblocking file descriptors; and<br>b) by waiting for an event only after <strong>read</strong> or <strong>write</strong> return <strong>EAGAIN</strong>.</p>
<p>By contrast, when used as a level-triggered interface (the default, when <strong>EPOLLET</strong> is not specified), <strong>epoll</strong> is simply a faster <strong>poll</strong>, and can be used wherever the latter is used since it shares the same semantics.</p>
<p>If multiple threads (or processes, if child processes have inherited the epoll file descriptor across <strong>fork</strong>) are blocked in <strong>epoll_wait</strong> waiting on the same epoll file descriptor and a file descriptor in the interest list that is marked for edge- triggered (<strong>EPOLLET</strong>) notification becomes ready, just one of the threads (or processes) is awoken from <strong>epoll_wait</strong>. This provides a useful optimization for avoiding “thundering herd” wake-ups in some scenarios.</p>
<h4 id="Questions-and-answers"><a href="#Questions-and-answers" class="headerlink" title="Questions and answers"></a>Questions and answers</h4><ol>
<li><p>What happens if you register the same file descriptor on an <strong>epoll</strong> instance twice?<br>You will probably get <strong>EEXIST</strong>. However, it is possible to add a duplicate (<strong>dup</strong>, <strong>dup2</strong>, <strong>fcntl</strong> <strong>F_DUPFD</strong>) file descriptor to the same <strong>epoll</strong> instance. This can be a useful technique for filtering events, if the duplicate file descriptors are registered with different events masks.</p>
</li>
<li><p>Can two <strong>epoll</strong> instances wait for the same file descriptor? If so, are events reported to both <strong>epoll</strong> file descriptors?<br>Yes, and events would be reported to both. However, careful programming may be needed to do this correctly.</p>
</li>
<li><p>Is the <strong>epoll</strong> file descriptor itself poll/epoll/selectable?<br>Yes. If an <strong>epoll</strong> file descriptor has events waiting, then it will indicate as being readable.</p>
</li>
<li><p>What happens if one attempts to put an <strong>epoll</strong> file descriptor into its own file descriptor set?<br>The <strong>epoll_ctl</strong> call fails (<strong>EINVAL</strong>). However, you can add an <strong>epoll</strong> file descriptor inside another <strong>epoll</strong> file descriptor set.</p>
</li>
<li><p>Can I send an <strong>epoll</strong> file descriptor over a UNIX domain socket to another process?<br>Yes, but it does not make sense to do this, since the receiving process would not have copies of the file descriptors in the interest list.</p>
</li>
<li><p>Will closing a file descriptor cause it to be removed from all <strong>epoll</strong> interest lists?<br>A file descriptor is removed from an interest list only after all the file descriptors referring to the underlying open file description have been closed. This means that even after a file descriptor that is part of an interest list has been closed, events may be reported for that file descriptor if other file descriptors referring to the same underlying file description remain open. To prevent this happening, the file descriptor must be explicitly removed from the interest list (using <strong>epoll_ctl</strong> <strong>EPOLL_CTL_DEL</strong>) before it is duplicated.</p>
</li>
<li><p>If more than one event occurs between <strong>epoll_wait</strong> calls, are they combined or reported separately?<br>They will be combined.</p>
</li>
</ol>
<hr>
<ul>
<li><code>epoll</code>底层使用红黑树管理文件描述符，那么为什么不用哈希表？<br>因为内核里有现成的红黑树而没有通用的哈希表。</li>
</ul>
</div>
<footer class="article-footer">
<a data-url="http://yoursite.com/2021/04/08/linux-IO/" data-id="ckp3d9faw0009gwrt7xz12vzw" class="article-share-link">Share</a>
</footer>
</div>
</article>
<article id="post-MIT6-824的分布式KV存储系统的一致性问题" class="article article-type-post" itemscope itemprop="blogPost">
<div class="article-meta">
<a href="/2021/03/15/MIT6-824%E7%9A%84%E5%88%86%E5%B8%83%E5%BC%8FKV%E5%AD%98%E5%82%A8%E7%B3%BB%E7%BB%9F%E7%9A%84%E4%B8%80%E8%87%B4%E6%80%A7%E9%97%AE%E9%A2%98/" class="article-date">
<time datetime="2021-03-15T07:44:17.000Z" itemprop="datePublished">2021-03-15</time>
</a>
</div>
<div class="article-inner">
<header class="article-header">
<h1 itemprop="name">
<a class="article-title" href="/2021/03/15/MIT6-824%E7%9A%84%E5%88%86%E5%B8%83%E5%BC%8FKV%E5%AD%98%E5%82%A8%E7%B3%BB%E7%BB%9F%E7%9A%84%E4%B8%80%E8%87%B4%E6%80%A7%E9%97%AE%E9%A2%98/">MIT6.824的分布式KV存储系统的一致性问题</a>
</h1>
</header>
<div class="article-entry" itemprop="articleBody">
<p>Lab 要求实现<strong>强一致性</strong>或<strong>线性一致性</strong>。强一致性指的是读操作必须读到最新的数据；任何一个读操作返回最新的数据后，来自相同或其他并发客户端的所有后续的读操作不能返回更旧的数据，从而满足可线性化。</p>
<p>所以对于 Get/PutAppend 都需要将 Op 放进 raft log 里进行线性一致性排序，顺序 commit、顺序 apply。</p>
</div>
<footer class="article-footer">
<a data-url="http://yoursite.com/2021/03/15/MIT6-824%E7%9A%84%E5%88%86%E5%B8%83%E5%BC%8FKV%E5%AD%98%E5%82%A8%E7%B3%BB%E7%BB%9F%E7%9A%84%E4%B8%80%E8%87%B4%E6%80%A7%E9%97%AE%E9%A2%98/" data-id="ckp3d9fae0000gwrtfhybdvg6" class="article-share-link">Share</a>
</footer>
</div>
</article>
<article id="post-interview-腾讯-2021-3-12" class="article article-type-post" itemscope itemprop="blogPost">
<div class="article-meta">
<a href="/2021/03/12/interview-%E8%85%BE%E8%AE%AF-2021-3-12/" class="article-date">
<time datetime="2021-03-12T08:48:56.000Z" itemprop="datePublished">2021-03-12</time>
</a>
</div>
<div class="article-inner">
<header class="article-header">
<h1 itemprop="name">
<a class="article-title" href="/2021/03/12/interview-%E8%85%BE%E8%AE%AF-2021-3-12/">interview_腾讯_2021_3_12</a>
</h1>
</header>
<div class="article-entry" itemprop="articleBody">
<h3 id="辨析-OS-的堆栈"><a href="#辨析-OS-的堆栈" class="headerlink" title="辨析 OS 的堆栈"></a>辨析 OS 的堆栈</h3><h3 id="进程通信方式？效率最高的是那种？"><a href="#进程通信方式？效率最高的是那种？" class="headerlink" title="进程通信方式？效率最高的是那种？"></a>进程通信方式？效率最高的是那种？</h3><h3 id="管道通信，半双工和全双工的区别？"><a href="#管道通信，半双工和全双工的区别？" class="headerlink" title="管道通信，半双工和全双工的区别？"></a>管道通信，半双工和全双工的区别？</h3><ul>
<li>管道本质是一段固定大小的内核缓冲区</li>
<li>Linux只有匿名管道，只能用于父子进程通信；Windows还支持命名管道，所以不局限于父子进程。</li>
<li>管道只有半双工，即只能一个进程读、一个进程写，全双工管道其实是两个半双工管道，所以两端的进程同时向全双工管道写数据时不会发生覆盖。</li>
</ul>
<h3 id="红黑树和AVL树的区别？"><a href="#红黑树和AVL树的区别？" class="headerlink" title="红黑树和AVL树的区别？"></a>红黑树和AVL树的区别？</h3><ul>
<li>AVL树是严格平衡的二叉树，不管是插入还是删除都需要检查平衡条件，若不满足则需要通过旋转来保持平衡，所以AVL树适用于查询多、插入、删除少的场景。</li>
<li>红黑树也是一种平衡二叉树，但它对平衡条件的要求没有AVL树严格，相对于严格平衡的AVL树来说，它的旋转频率较低，适用于插入、删除多的场景</li>
</ul>
<table>
<thead>
<tr>
<th></th>
<th>平衡度</th>
<th>调整频率</th>
<th>适用场景</th>
</tr>
</thead>
<tbody><tr>
<td>AVL树</td>
<td>高</td>
<td>高</td>
<td>查询多、插入/删除少</td>
</tr>
<tr>
<td>红黑树</td>
<td>低</td>
<td>低</td>
<td>插入/删除多</td>
</tr>
</tbody></table>
<h3 id="读写锁-vs-互斥锁"><a href="#读写锁-vs-互斥锁" class="headerlink" title="读写锁 vs. 互斥锁"></a>读写锁 vs. 互斥锁</h3><p>读写锁可以让 readers 互不阻塞，互斥锁保证共享资源在同一时刻只能被一个 reader/writer 访问。</p>
<h3 id="MySQL-的聚集索引可以创建多个吗？"><a href="#MySQL-的聚集索引可以创建多个吗？" class="headerlink" title="MySQL 的聚集索引可以创建多个吗？"></a>MySQL 的聚集索引可以创建多个吗？</h3><p>不可以，因为聚集索引是对主键建立的索引。</p>
<p>聚集索引是对主键建立的索引。<br>如果未指定主键，InnoDB 使用表中第一个不允许为 NULL 且属性值唯一的列作为默认主键。如果不存在这样的列，InnoDB 会内置一个“隐藏主键”，用其建立聚集索引。</p>
<h3 id="事务的-Isolation-Level-有哪几种？解决什么问题？"><a href="#事务的-Isolation-Level-有哪几种？解决什么问题？" class="headerlink" title="事务的 Isolation Level 有哪几种？解决什么问题？"></a>事务的 Isolation Level 有哪几种？解决什么问题？</h3><h3 id="路由器-vs-交换机"><a href="#路由器-vs-交换机" class="headerlink" title="路由器 vs. 交换机"></a>路由器 vs. 交换机</h3><ol>
<li>路由器在网络层，交换机在链路层</li>
<li>路由器根据 IP 地址转发数据报，交换机根据 MAC 地址转发数据帧</li>
<li>交换机用于组件局域网，路由器负责让主机连接外网。多台主机可以通过网线连接到交换机，这时候就组建好了局域网，主机之间可以相互通信，但不能访问外网。局域网内的主机使用的私网IP，所以必须通过路由器映射为公网IP之后才能访问外网。</li>
</ol>
<p>网络拓扑：</p>
<p><img src="/2021/03/12/interview-%E8%85%BE%E8%AE%AF-2021-3-12/network.png" alt></p>
<h3 id="TCP-vs-UDP"><a href="#TCP-vs-UDP" class="headerlink" title="TCP vs. UDP"></a>TCP vs. UDP</h3><h3 id="TCP-的滑动窗口协议是做什么用的？"><a href="#TCP-的滑动窗口协议是做什么用的？" class="headerlink" title="TCP 的滑动窗口协议是做什么用的？"></a>TCP 的滑动窗口协议是做什么用的？</h3><p>提高网络吞吐量，允许发送方一次发送多个分组而不必每发送一个分组就停下来等待确认。</p>
<p>在滑动窗口协议下，发送方可以对分组使用<strong>累积确认</strong>：</p>
<p><img src="/2021/03/12/interview-%E8%85%BE%E8%AE%AF-2021-3-12/TCP%E7%B4%AF%E7%A7%AF%E7%A1%AE%E8%AE%A4.png" alt></p>
<p>参考：<a href="http://www.winder520.top/tcp-lei-ji-que-ren-huo-zhe-lei-ji-ying-da/" target="_blank" rel="noopener">http://www.winder520.top/tcp-lei-ji-que-ren-huo-zhe-lei-ji-ying-da/</a></p>
<p><strong>流量控制 vs. 拥塞控制</strong></p>
<ol>
<li>流量控制：如果发送方发送数据太多、太快，而接收方接受数据时非常缓慢，会容易使接收方缓存溢出。流量控制是为了消除接收方缓存溢出的可能性。TCP通过让发送方维护一个称为<strong>接收窗口</strong>的变量来提供流量控制。接收窗口用于告诉发送方，该接收方还有多少可用的缓存空间</li>
<li>拥塞控制：拥塞控制是作用于网络的，是为了防止过多的数据注入到网络中，避免出现网络负载过大的情况。<br>发现拥塞的三种途径：<br>(1) 发送方等待接收方的ACK过程中超时<br>(2) 收到3个重复的ACK<br>(3) ICMP源抑制报文</li>
</ol>
<p>为什么“收到3个重复的ACK”表示网络拥塞？ACK 指的是接收方希望收到的<strong>下一字节</strong>的序号（如上图所示），所以发送方收到3个重复的ACK就说明某个分组迟迟没有被接收方收到。</p>
<p>TCP拥塞控制的基本思想是，当出现丢包事件时，让发送方降低其发送速率（通过减小拥塞窗口的大小）。<strong>拥塞窗口</strong>的大小指的是可以连续发送（“连续发送”指的是不用每发送一个分组就停下来等待确认）的分组个数。TCP拥塞控制算法包括三个主要部分：<br><strong>(1) 加性增、乘性减</strong><br>乘性减：发送方每检测到一次丢包事件（收到3个重复的ACK）就将拥塞窗口减半。<br>加性增：发送方在检测到一次丢包事件后将拥塞窗口值减半，然后每过一个RTT（往返时延）就将拥塞窗口增加一个MSS（最大报文长度），也就是线性增长。<br><strong>(2) 慢启动</strong><br>TCP发送方在初始阶段以慢速率（因此叫慢启动）发送，但是以指数的速度快速增加其发送速率。每当一个报文段被确认后，拥塞窗口就增加一个MSS，从而使发送方得到指数级增长的发送速率。<br><strong>(3) 对超时事件的反应</strong><br>超时事件发生时，TCP发送方进入慢启动阶段，即它将拥塞窗口设置为1 MSS，然后窗口长度以指数速率增长，直到达到超时事件前窗口长度的一半为止。此后窗口以线性速率增长，就像收到3个重复ACK一样。</p>
<p><strong>TCP快速恢复/快速重传</strong>指的是“乘性减”，即收到3个重复ACK后不进入慢启动阶段，而是将拥塞窗口减半。</p>
<h3 id="一个关于-zookeeper-的问题，忘了"><a href="#一个关于-zookeeper-的问题，忘了" class="headerlink" title="一个关于 zookeeper 的问题，忘了"></a>一个关于 zookeeper 的问题，忘了</h3><h3 id="项目相关：为什么用-MongoDB-不用-MySQL？"><a href="#项目相关：为什么用-MongoDB-不用-MySQL？" class="headerlink" title="项目相关：为什么用 MongoDB 不用 MySQL？"></a>项目相关：为什么用 MongoDB 不用 MySQL？</h3><ul>
<li>因为当时项目前期，表结构还不定，MongoDB在扩展方面比较容易管理（MySQL在插入的时候各字段必须和建表时创建的字段匹配；对于MongoDB，即使是在创建集合时没有指明的字段，也可以在插入时动态创建）</li>
<li>json格式的数据比较好处理</li>
</ul>
</div>
<footer class="article-footer">
<a data-url="http://yoursite.com/2021/03/12/interview-%E8%85%BE%E8%AE%AF-2021-3-12/" data-id="ckp3d9fav0008gwrte5ly6ds0" class="article-share-link">Share</a>
</footer>
</div>
</article>
<article id="post-interview-腾讯-2021-3-11" class="article article-type-post" itemscope itemprop="blogPost">
<div class="article-meta">
<a href="/2021/03/12/interview-%E8%85%BE%E8%AE%AF-2021-3-11/" class="article-date">
<time datetime="2021-03-12T08:47:55.000Z" itemprop="datePublished">2021-03-12</time>
</a>
</div>
<div class="article-inner">
<header class="article-header">
<h1 itemprop="name">
<a class="article-title" href="/2021/03/12/interview-%E8%85%BE%E8%AE%AF-2021-3-11/">interview_腾讯_2021_3_11</a>
</h1>
</header>
<div class="article-entry" itemprop="articleBody">
<h3 id="RPC-基于什么网络协议？"><a href="#RPC-基于什么网络协议？" class="headerlink" title="RPC 基于什么网络协议？"></a>RPC 基于什么网络协议？</h3><ul>
<li>HTTP，例如 Go 的<code>rpc</code>库。</li>
</ul>
<h3 id="多个-TCP-包如何组成一个-HTTP-报文？例如连续发了-100-个-TCP-包，前-50-个属于一个-HTTP-报文，后-50-个属于另一个，接收方如何判断？"><a href="#多个-TCP-包如何组成一个-HTTP-报文？例如连续发了-100-个-TCP-包，前-50-个属于一个-HTTP-报文，后-50-个属于另一个，接收方如何判断？" class="headerlink" title="多个 TCP 包如何组成一个 HTTP 报文？例如连续发了 100 个 TCP 包，前 50 个属于一个 HTTP 报文，后 50 个属于另一个，接收方如何判断？"></a>多个 TCP 包如何组成一个 HTTP 报文？例如连续发了 100 个 TCP 包，前 50 个属于一个 HTTP 报文，后 50 个属于另一个，接收方如何判断？</h3><p>在一个会话里进行，客户端直到收到全部数据再关闭 TCP 连接结束会话。</p>
<h3 id="HTTP-会话如何创建？"><a href="#HTTP-会话如何创建？" class="headerlink" title="HTTP 会话如何创建？"></a>HTTP 会话如何创建？</h3><ol>
<li>客户端建立一条 TCP 连接（如果传输层不是 TCP，也可以是其他适合的连接）。</li>
<li>客户端发送请求并等待应答。</li>
<li>服务器处理请求并送回应答，回应包括一个状态码和对应的数据。</li>
<li>客户端关闭 TCP 连接。</li>
</ol>
<p>从 HTTP/1.1 开始，连接在完成第三阶段后不再关闭，客户端可以再次发起新的请求。这意味着第二步和第三步可以连续进行数次。</p>
<h3 id="为什么强调-Go-的并发编程特性？"><a href="#为什么强调-Go-的并发编程特性？" class="headerlink" title="为什么强调 Go 的并发编程特性？"></a>为什么强调 Go 的并发编程特性？</h3><h3 id="Goroutine-的调度算法？Go-的-map-是如何实现的？（因为我告诉他-6-824-的-KV-存储是用-map-实现的）"><a href="#Goroutine-的调度算法？Go-的-map-是如何实现的？（因为我告诉他-6-824-的-KV-存储是用-map-实现的）" class="headerlink" title="Goroutine 的调度算法？Go 的 map 是如何实现的？（因为我告诉他 6.824 的 KV 存储是用 map 实现的）"></a>Goroutine 的调度算法？Go 的 map 是如何实现的？（因为我告诉他 6.824 的 KV 存储是用 map 实现的）</h3><p>(我主攻C++，不懂Go)</p>
<h3 id="InstallSnapshot-把全部-KV-数据持久化导致开销过大，如何解决？"><a href="#InstallSnapshot-把全部-KV-数据持久化导致开销过大，如何解决？" class="headerlink" title="InstallSnapshot 把全部 KV 数据持久化导致开销过大，如何解决？"></a>InstallSnapshot 把全部 KV 数据持久化导致开销过大，如何解决？</h3><h3 id="Linux-的-VFS-是什么？"><a href="#Linux-的-VFS-是什么？" class="headerlink" title="Linux 的 VFS 是什么？"></a>Linux 的 VFS 是什么？</h3><p>在具体文件系统(ext2, ext3, NTFS, …)之上做的一个抽象层，使得OS在进行文件操作的时候无需知道文件系统的实现细节。VFS 和具体文件系统的关系类似于虚基类和子类的关系。在双系统环境下可以从 Linux 访问 Windows NTFS 的文件，就是因为 NTFS 实现了 VFS 的接口。</p>
</div>
<footer class="article-footer">
<a data-url="http://yoursite.com/2021/03/12/interview-%E8%85%BE%E8%AE%AF-2021-3-11/" data-id="ckp3d9fao0003gwrt24fbcrit" class="article-share-link">Share</a>
</footer>
</div>
</article>
<article id="post-interview-腾讯-2021-3-9" class="article article-type-post" itemscope itemprop="blogPost">
<div class="article-meta">
<a href="/2021/03/09/interview-%E8%85%BE%E8%AE%AF-2021-3-9/" class="article-date">
<time datetime="2021-03-09T14:39:47.000Z" itemprop="datePublished">2021-03-09</time>
</a>
</div>
<div class="article-inner">
<header class="article-header">
<h1 itemprop="name">
<a class="article-title" href="/2021/03/09/interview-%E8%85%BE%E8%AE%AF-2021-3-9/">interview_腾讯_2021_3_9</a>
</h1>
</header>
<div class="article-entry" itemprop="articleBody">
<h3 id="为什么要用-Raft-保证容错性？"><a href="#为什么要用-Raft-保证容错性？" class="headerlink" title="为什么要用 Raft 保证容错性？"></a>为什么要用 Raft 保证容错性？</h3><ul>
<li>Raft 不就是干这个的嘛……</li>
</ul>
<h3 id="只让-Leader-响应客户端请求有什么问题？Leader-挂了怎么办？在新的-Leader-选举出来这段时间内集群内没有-Leader，怎么让集群继续对外提供服务？"><a href="#只让-Leader-响应客户端请求有什么问题？Leader-挂了怎么办？在新的-Leader-选举出来这段时间内集群内没有-Leader，怎么让集群继续对外提供服务？" class="headerlink" title="只让 Leader 响应客户端请求有什么问题？Leader 挂了怎么办？在新的 Leader 选举出来这段时间内集群内没有 Leader，怎么让集群继续对外提供服务？"></a>只让 Leader 响应客户端请求有什么问题？Leader 挂了怎么办？在新的 Leader 选举出来这段时间内集群内没有 Leader，怎么让集群继续对外提供服务？</h3><ul>
<li>没有 Leader 还叫 Raft 吗？Raft 集群没有 Leader 还能用？？？</li>
</ul>
<h3 id="CAP-一致性、可用性、分区容错性-，Raft-保证的是-CP"><a href="#CAP-一致性、可用性、分区容错性-，Raft-保证的是-CP" class="headerlink" title="CAP (一致性、可用性、分区容错性)，Raft 保证的是 CP"></a>CAP (一致性、可用性、分区容错性)，Raft 保证的是 CP</h3><h3 id="应用-Raft-的开源软件有了解过吗？"><a href="#应用-Raft-的开源软件有了解过吗？" class="headerlink" title="应用 Raft 的开源软件有了解过吗？"></a>应用 Raft 的开源软件有了解过吗？</h3><ul>
<li>etcd，分布式 KV 数据库</li>
<li>tidb，分布式关系型数据库</li>
<li>zookeeper，分布式协调服务框架，提供的服务：配置管理、命名管理、分布式锁、集群管理</li>
</ul>
<h3 id="LRU-如何实现？"><a href="#LRU-如何实现？" class="headerlink" title="LRU 如何实现？"></a>LRU 如何实现？</h3><ul>
<li>略</li>
</ul>
<h3 id="线程通信方式？"><a href="#线程通信方式？" class="headerlink" title="线程通信方式？"></a>线程通信方式？</h3><ul>
<li>信号量、条件变量、管道、共享内存、socket</li>
</ul>
<h3 id="并发线程访问共享变量只能加锁吗？（不是，还有原子操作）原子操作怎么实现？信号量、互斥量、条件变量怎么实现？"><a href="#并发线程访问共享变量只能加锁吗？（不是，还有原子操作）原子操作怎么实现？信号量、互斥量、条件变量怎么实现？" class="headerlink" title="并发线程访问共享变量只能加锁吗？（不是，还有原子操作）原子操作怎么实现？信号量、互斥量、条件变量怎么实现？"></a>并发线程访问共享变量只能加锁吗？（不是，还有原子操作）原子操作怎么实现？信号量、互斥量、条件变量怎么实现？</h3><ul>
<li>信号量的实现：信号量维护一个线程的等待队列。信号量有一个初值<code>S</code>。信号量有两种操作：释放和等待。线程“等待”信号量时<code>S--</code>，如果<code>S < 0</code>就将当前线程添加到信号量的等待队列中，否则线程继续执行。线程“释放”信号量时<code>S++</code>，如果<code>S <= 0</code>就说明有别的线程在等待该信号量，所以要唤醒等待队列中的一个线程。</li>
<li>互斥量的实现：初值<code>S=1</code>的信号量</li>
<li>条件变量的实现：条件变量依赖于互斥量。在C++11的实现中，<code>cv.wait()</code>之前线程需要在<code>mutex</code>上获得锁，<code>cv.wait()</code>首先让线程释放原先在<code>mutex</code>上获得的锁，然后在事件对象上等待别的线程通过<code>cv.notify()</code>发送过来的信号，信号到达后重新获取在<code>mutex</code>上的锁，最后<code>cv.wait()</code>返回。所以线程在调用<code>cv.notify()</code>时不能在<code>mutex</code>上持有锁，否则另一个线程的<code>cv.wait()</code>无法返回，造成死锁。</li>
<li>C++原子操作的实现：<br>原子操作是一个非常复杂的话题，此处只简单介绍。<code>std::atomic</code>可以使用模板参数，意味着你可以对任意类型变量进行原子操作。对于字节数不超过<code>_ATOMIC_MAXBYTES_LOCK_FREE</code>（默认为8，可以根据<code>std::atomic</code>的<code>is_lock_free</code>函数寻找到）的类型，使用 Compare-And-Swap (CAS) 算法，例如<code>std::atomic<int64_t></code>的<code>store</code>就是这样实现的：<figure class="highlight cpp"><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></pre></td><td class="code"><pre><span class="line"><span class="comment">//</span></span><br><span class="line"><span class="comment">// @file d:\Program Files (x86)\Microsoft Visual Studio 12.0\VC\include\xatomic.h</span></span><br><span class="line"><span class="comment">//</span></span><br><span class="line"><span class="keyword">inline</span> _LONGLONG _InterlockedExchange64(<span class="keyword">volatile</span> _LONGLONG * _Tgt, _LONGLONG _Value)</span><br><span class="line">{</span><br><span class="line"> _Compiler_barrier();</span><br><span class="line"> __asm</span><br><span class="line"> {</span><br><span class="line"> mov esi, _Tgt;</span><br><span class="line"> mov ecx, dword ptr _Value[<span class="number">4</span>];</span><br><span class="line"> mov ebx, dword ptr _Value;</span><br><span class="line"> again:</span><br><span class="line"> lock cmpxchg8b [esi];</span><br><span class="line"> jnz again;</span><br><span class="line"> mov dword ptr _Value[<span class="number">4</span>], edx;</span><br><span class="line"> mov dword ptr _Value, eax;</span><br><span class="line"> }</span><br><span class="line"> _Compiler_barrier();</span><br><span class="line"></span><br><span class="line"> <span class="keyword">return</span> (_Value);</span><br><span class="line">}</span><br></pre></td></tr></table></figure>
在<code>cmpxchg</code>指令前加上<code>lock</code>前缀。简言之，<code>lock</code>前缀会使 CPU 宣告一个 LOCK# 信号，这样就能确保在多处理器系统或多线程竞争的环境下互斥地使用这个内存地址。当指令执行完毕，LOCK# 就会消失。详细原理如下所述：<br>LOCK# 会引起处理器缓存回写到内存。LOCK# 相当于一个内存栅栏，内存栅栏主要提供3个功能：</li>
<li>确保指令重排序时不会把其后面的指令排到内存栅栏之前的位置，也不会把前面的指令排到内存栅栏的后面；即在执行到内存栅栏这句指令时，在它前面的操作已经全部完成。</li>
<li>强制将对缓存的修改操作立即写入主存，利用缓存一致性机制阻止同时修改由两个以上 CPU 缓存的内存区域数据。</li>
<li>如果是写操作，它会导致其他 CPU 中对应的 cache line 无效。</li>
</ul>
<p>对于字节数超过<code>_ATOMIC_MAXBYTES_LOCK_FREE</code>的类型，<code>std::atomic</code>使用 SpinLock 实现原子读写。例如<code>store</code>的实现：</p>
<figure class="highlight cpp"><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"><span class="comment">/* ATOMIC OPERATIONS FOR OBJECTS WITH SIZES THAT</span></span><br><span class="line"><span class="comment"> DON'T MATCH THE SIZE OF ANY INTEGRAL TYPE */</span></span><br><span class="line"><span class="keyword">inline</span> <span class="keyword">void</span> _Atomic_copy(</span><br><span class="line"> <span class="keyword">volatile</span> _Atomic_flag_t *_Flag, <span class="keyword">size_t</span> _Size,</span><br><span class="line"> <span class="keyword">volatile</span> <span class="keyword">void</span> *_Tgt, <span class="keyword">volatile</span> <span class="keyword">const</span> <span class="keyword">void</span> *_Src,</span><br><span class="line"> memory_order _Order)</span><br><span class="line"> { <span class="comment">/* atomically copy *_Src to *_Tgt with memory ordering */</span></span><br><span class="line"> _Lock_spin_lock(_Flag);</span><br><span class="line"> <span class="built_in">memcpy</span>((<span class="keyword">void</span> *)_Tgt, (<span class="keyword">void</span> *)_Src, _Size);</span><br><span class="line"> _Unlock_spin_lock(_Flag);</span><br><span class="line"> }</span><br></pre></td></tr></table></figure>
<p>这里的 SpinLock 使用 Test-And-Set 算法实现：</p>
<figure class="highlight cpp"><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"><span class="keyword">inline</span> <span class="keyword">void</span> _Lock_spin_lock(</span><br><span class="line"> <span class="keyword">volatile</span> _Atomic_flag_t *_Flag)</span><br><span class="line"> { <span class="comment">/* spin until _Flag successfully set */</span></span><br><span class="line"> <span class="keyword">while</span> (_ATOMIC_FLAG_TEST_AND_SET(_Flag, memory_order_acquire))</span><br><span class="line"> _YIELD_PROCESSOR;</span><br><span class="line"> }</span><br><span class="line"></span><br><span class="line"><span class="keyword">inline</span> <span class="keyword">void</span> _Unlock_spin_lock(</span><br><span class="line"> <span class="keyword">volatile</span> _Atomic_flag_t *_Flag)</span><br><span class="line"> { <span class="comment">/* release previously obtained lock */</span></span><br><span class="line"> _ATOMIC_FLAG_CLEAR(_Flag, memory_order_release);</span><br><span class="line"> }</span><br></pre></td></tr></table></figure>
<p>下面是 TEST AND SET 的实现：</p>
<figure class="highlight cpp"><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"><span class="keyword">inline</span> <span class="keyword">int</span> _Atomic_flag_test_and_set(<span class="keyword">volatile</span> _Atomic_flag_t *_Flag,</span><br><span class="line"> memory_order _Order)</span><br><span class="line"> { <span class="comment">/* atomically test flag and set to true */</span></span><br><span class="line"> <span class="keyword">switch</span> (_Order)</span><br><span class="line"> {</span><br><span class="line"> <span class="keyword">case</span> memory_order_relaxed:</span><br><span class="line"> <span class="keyword">return</span> (_INTRIN_RELAXED(_interlockedbittestandset)(_Flag, <span class="number">0</span>));</span><br><span class="line"> mov eax,dword ptr [_Flag]</span><br><span class="line"> lock bts dword ptr [eax],<span class="number">0</span></span><br><span class="line"> setb cl</span><br><span class="line"> movzx eax,cl</span><br><span class="line"> jmp $LN5+<span class="number">0E1</span>h (<span class="number">0490F</span>Eh)</span><br></pre></td></tr></table></figure>
<p>关键指令是<code>lock bts</code>，<code>bts</code>即 Bit Test and Set，<code>lock</code>前缀保证了多核环境下内存读写的安全性。</p>
<p>总结：<code>std::atomic</code>实现原子操作的方法根据变量类型的大小不同分为2种：</p>
<ul>
<li>CAS 无锁算法</li>
<li>基于 Test-And-Set 实现 SpinLock，使用 SpinLock 保证读写操作的原子性</li>
</ul>
<h3 id="多线程、多进程，如何取舍？"><a href="#多线程、多进程，如何取舍？" class="headerlink" title="多线程、多进程，如何取舍？"></a>多线程、多进程，如何取舍？</h3><ul>
<li>考虑线程和进程的创建开销，不同的 OS 开销不同</li>
<li>在多核架构下建议使用多进程。因为进程是资源分配的基本单位，每个进程的资源相互独立，当每个 CPU 核心运行一个进程的时候，由于进程之间不存在上下文切换，所以多个进程的资源不会在多个 CPU 核心之间复制。如果每个 CPU 核心运行一个线程，由于每个线程需要一些共享资源（多个线程属于一个进程），线程调度的时候这些资源需要从一个 CPU 核心复制到另一个核心，带来了额外的开销。</li>
</ul>
<h3 id="孤儿进程、僵尸进程的区别及危害？"><a href="#孤儿进程、僵尸进程的区别及危害？" class="headerlink" title="孤儿进程、僵尸进程的区别及危害？"></a>孤儿进程、僵尸进程的区别及危害？</h3><ul>
<li>一个父进程退出，而它的一个或多个子进程还在运行，那么那些子进程将成为孤儿进程。孤儿进程将被<code>init</code>进程收养，并由init进程对它们完成状态收集工作。孤儿进程没有危害。</li>
<li>一个进程使用<code>fork()</code>创建子进程，如果子进程退出，而父进程并没有调用<code>wait()</code>获取子进程的状态信息，那么子进程的进程描述符仍然保存在系统中。这种进程称之为僵死进程。僵尸进程会占用系统资源。</li>
</ul>
<h3 id="用户线程、内核线程的区别？"><a href="#用户线程、内核线程的区别？" class="headerlink" title="用户线程、内核线程的区别？"></a>用户线程、内核线程的区别？</h3><ul>
<li>略</li>
</ul>
<h3 id="C-的线程是内核还是用户线程？"><a href="#C-的线程是内核还是用户线程？" class="headerlink" title="C++的线程是内核还是用户线程？"></a>C++的线程是内核还是用户线程？</h3><ul>
<li>内核级</li>
</ul>
<h3 id="C-的线程怎么实现？"><a href="#C-的线程怎么实现？" class="headerlink" title="C++的线程怎么实现？"></a>C++的线程怎么实现？</h3><h3 id="文件-I-O-的过程？open-read-write-close-的底层实现"><a href="#文件-I-O-的过程？open-read-write-close-的底层实现" class="headerlink" title="文件 I/O 的过程？open, read/write, close 的底层实现"></a>文件 I/O 的过程？open, read/write, close 的底层实现</h3><ul>
<li>read<br>找到<code>inode</code>结构（<code>file</code>结构 -> <code>dentry</code>结构 -> <code>inode</code>结构）（<code>file</code>结构表示文件读写的上下文，例如当前读写位置、访问模式、引用计数等；<code>dentry</code>结构，目录项，描述文件在 VFS 目录树中的信息；<code>inode</code>结构是文件在 VFS 中的索引节点），<code>inode</code>结构记录了文件内容在内存中所对应的缓冲页面。如果缓冲页面不再内存中，就从设备上读入；否则直接读取缓冲页面。这里涉及 Linux 的文件预读技术：当发生顺序读取时，系统会以页面为单位读取比应用程序所要求的更多的数据，将其缓存到<code>inode</code>结构所记录的缓冲页面中。缓冲页面的管理使用 LRU 替换策略。</li>
<li>write<br>如前所述，如果欲访问的文件内容已经在缓冲页面中，写操作只是把数据写到缓冲页面中，当 CPU 较空闲时会调度一个内核线程<code>kflushd</code>完成刷盘。另外，应用程序还可以调用<code>sync()</code>强制调度内核线程<code>kflushd</code>将缓冲页面落盘。</li>
<li>open<br>进程有一个“打开文件表”，其中的指针指向打开文件的<code>file</code>结构。假设文件已存在，“打开”动作就是根据路径名找到<code>dentry</code>结构、创建<code>file</code>结构并将其指针保存到进程的“打开文件表”，其在表中的索引就是文件描述符fd。</li>
<li>close<br>(1) 清除文件在进程的打开文件表中占据的位置 (将索引为fd的表项置为NULL)<br>(2) 将<code>file</code>结构中的引用计数减1，如果引用计数减至0就释放<code>file</code>结构</li>
</ul>
<p><img src="/2021/03/09/interview-%E8%85%BE%E8%AE%AF-2021-3-9/%E6%96%87%E4%BB%B6%E9%A1%B5%E9%9D%A2%E7%BC%93%E5%86%B2%E9%98%9F%E5%88%97.png" alt></p>
<p><strong>补充：软链接 vs. 硬链接</strong><br>(1) 硬链接通过与源文件共享 inode 号进行链接。即，硬链接与源文件不同名，但都指向同一个inode。硬链接的作用是允许一个文件有多个有效路径名，这样用户就可以建立硬链接到重要文件，以防止“误删”，因为只有当 inode 的引用计数被减至0时文件才会被真正删除。<br>(2) 软链接存放的是源文件的路径，它是一个独立的文件，类似于 Windows 的快捷方式。</p>
<p><img src="/2021/03/09/interview-%E8%85%BE%E8%AE%AF-2021-3-9/linux-soft-hard-link-diff.png" alt></p>
<h3 id="代码："><a href="#代码：" class="headerlink" title="代码："></a>代码：</h3><ul>
<li>Leetcode 239，用单调队列实现O(N)的解法</li>
<li>N 个并发线程，交替打印 M 个数。例如 N=4, M=8<br>Thread1-0<br>Thread2-1<br>Thread3-2<br>Thread4-3<br>Thread1-4<br>Thread2-5<br>Thread3-6<br>Thread4-7</li>
</ul>
<figure class="highlight cpp"><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></pre></td><td class="code"><pre><span class="line"><span class="function"><span class="keyword">int</span> <span class="title">main</span><span class="params">()</span> </span>{</span><br><span class="line"> <span class="keyword">int</span> n, m;</span><br><span class="line"> <span class="built_in">std</span>::<span class="built_in">cout</span> << <span class="string">"n,m? "</span>;</span><br><span class="line"> <span class="built_in">std</span>::<span class="built_in">cin</span> >> n >> m;</span><br><span class="line"></span><br><span class="line"> <span class="built_in">std</span>::atomic<<span class="keyword">int</span>> x{<span class="number">0</span>};</span><br><span class="line"></span><br><span class="line"> <span class="built_in">std</span>::atomic<<span class="keyword">bool</span>> *signal = <span class="keyword">new</span> <span class="built_in">std</span>::atomic<<span class="keyword">bool</span>>[n];</span><br><span class="line"> <span class="built_in">std</span>::mutex *mu = <span class="keyword">new</span> <span class="built_in">std</span>::mutex[n];</span><br><span class="line"> <span class="built_in">std</span>::condition_variable *cv = <span class="keyword">new</span> <span class="built_in">std</span>::condition_variable[n];</span><br><span class="line"> <span class="built_in">std</span>::thread *thds = <span class="keyword">new</span> <span class="built_in">std</span>::thread[n];</span><br><span class="line"></span><br><span class="line"> <span class="keyword">for</span> (<span class="keyword">int</span> i = <span class="number">0</span>; i < n; i++) {</span><br><span class="line"> signal[i].store(<span class="literal">false</span>);</span><br><span class="line"> thds[i] = <span class="built_in">std</span>::thread ([&, i] { <span class="comment">// 变量i以值的形式捕获, 其余变量以引用形式捕获</span></span><br><span class="line"> <span class="keyword">while</span> (x.load() < m) {</span><br><span class="line"> <span class="built_in">std</span>::unique_lock<<span class="built_in">std</span>::mutex> lock(mu[i]);</span><br><span class="line"> cv[i].wait(lock, [&] {</span><br><span class="line"> <span class="keyword">return</span> signal[i].load();</span><br><span class="line"> });</span><br><span class="line"></span><br><span class="line"> <span class="comment">// Block itself.</span></span><br><span class="line"> signal[i].store(<span class="literal">false</span>);</span><br><span class="line"></span><br><span class="line"> <span class="keyword">if</span> (x.load() < m) {</span><br><span class="line"> <span class="built_in">std</span>::<span class="built_in">cout</span> << <span class="string">"Thread-"</span> << i + <span class="number">1</span> << <span class="string">" "</span></span><br><span class="line"> << x.fetch_add(<span class="number">1</span>) << <span class="string">"\n"</span>;</span><br><span class="line"> <span class="built_in">std</span>::this_thread::sleep_for(<span class="built_in">std</span>::chrono::milliseconds(<span class="number">100</span>));</span><br><span class="line"> }</span><br><span class="line"></span><br><span class="line"> <span class="comment">// Wake up the next thread.</span></span><br><span class="line"> signal[(i + <span class="number">1</span>) % n].store(<span class="literal">true</span>);</span><br><span class="line"> cv[(i + <span class="number">1</span>) % n].notify_one();</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 class="comment">// Start the first thread.</span></span><br><span class="line"> signal[<span class="number">0</span>].store(<span class="literal">true</span>);</span><br><span class="line"> cv[<span class="number">0</span>].notify_one();</span><br><span class="line"></span><br><span class="line"> <span class="keyword">for</span> (<span class="keyword">int</span> i = <span class="number">0</span>; i < n; i++) {</span><br><span class="line"> thds[i].join();</span><br><span class="line"> }</span><br><span class="line"></span><br><span class="line"> <span class="keyword">delete</span>[] signal;</span><br><span class="line"> <span class="keyword">delete</span>[] mu;</span><br><span class="line"> <span class="keyword">delete</span>[] cv;</span><br><span class="line"> <span class="keyword">delete</span>[] thds;</span><br><span class="line">}</span><br></pre></td></tr></table></figure>
</div>
<footer class="article-footer">
<a data-url="http://yoursite.com/2021/03/09/interview-%E8%85%BE%E8%AE%AF-2021-3-9/" data-id="ckp3d9far0005gwrt9lazdlbh" class="article-share-link">Share</a>
</footer>
</div>
</article>
<article id="post-interview-蚂蚁集团-数字技术部-2021-2-28" class="article article-type-post" itemscope itemprop="blogPost">
<div class="article-meta">
<a href="/2021/03/09/interview-%E8%9A%82%E8%9A%81%E9%9B%86%E5%9B%A2-%E6%95%B0%E5%AD%97%E6%8A%80%E6%9C%AF%E9%83%A8-2021-2-28/" class="article-date">
<time datetime="2021-03-09T14:39:14.000Z" itemprop="datePublished">2021-03-09</time>
</a>
</div>
<div class="article-inner">
<header class="article-header">
<h1 itemprop="name">
<a class="article-title" href="/2021/03/09/interview-%E8%9A%82%E8%9A%81%E9%9B%86%E5%9B%A2-%E6%95%B0%E5%AD%97%E6%8A%80%E6%9C%AF%E9%83%A8-2021-2-28/">interview_蚂蚁集团-数字技术部_2021_2_28</a>
</h1>
</header>
<div class="article-entry" itemprop="articleBody">
<h3 id="丁丁识字项目"><a href="#丁丁识字项目" class="headerlink" title="丁丁识字项目"></a>丁丁识字项目</h3><ol>
<li>为什么使用 MongoDB？为什么分库？是否有分表？</li>
</ol>
<h3 id="MIT-6-824"><a href="#MIT-6-824" class="headerlink" title="MIT 6.824"></a>MIT 6.824</h3><ol>
<li>简单说一下 raft</li>
<li>为什么要引入分片？<br>负载均衡，否则所有的 key/value 数据都会落在一个集群上</li>
<li>是否考虑过集群的 TPS (每秒事务处理量(TransactionPerSecond))？如何处理海量的客户端请求？</li>
</ol>
<h3 id="CMU-15-445"><a href="#CMU-15-445" class="headerlink" title="CMU 15.445"></a>CMU 15.445</h3><ol>
<li>Buffer Pool Manager 如果面临宕机要怎么做？</li>
<li>B+Tree 的设计思想</li>
<li>2PL 如何检测死锁？如何处理？</li>
<li>MVCC<ul>
<li>The DBMS maintains multiple <strong>physical</strong> versions of a single <strong>logical</strong> object in the database:<ul>
<li>When a txn writes to an object, the DBMS creates a new version of that object.</li>
<li>When a txn reads an object, it reads the newest version that existed when the txn started.</li>
<li><strong>Writers do not block readers, readers do not block writers. But writers may block writers.</strong></li>
</ul>
</li>
<li>PCC, OCC, MVCC 的关系<ul>
<li>悲观并发控制(PCC)是一种用来解决 RW 和 WW 冲突的<strong>加锁并发控制</strong>.</li>
<li>乐观并发控制(OCC)是一种用来解决 WW 冲突的<strong>无锁并发控制</strong>，使用“Read-Validate-Write”三阶段协议，DBMS 为每个事务分配一个私有工作空间. 适用于读多写少的场景.</li>
<li>MVCC是一种用来解决 RW 冲突的<strong>无锁并发控制</strong>，在 Repeatable Read 或 Read Committed 两个隔离级别下工作. 在 MVCC 场景下，DBMS 为每个事务分配一个时间戳，每次写操作都会产生一个新的版本，每个版本都有一个开始时间戳<code>begin-ts</code>和结束时间戳<code>end-ts</code>. 假设一个事务的时间戳是<code>ts</code>，那么读操作读到的是最后一个满足<code>begin-ts ≤ ts < end-ts</code>的版本，这样读操作就不用阻塞写操作，写操作也不用阻塞读操作.</li>
</ul>
</li>
<li>MVCC 的出现就是 DBMS 不满用悲观锁解决 RW 冲突问题，为了提升性能而提出的解决方案。所以在 DBMS 中可以形成两个组合：<ul>
<li>MVCC + 悲观锁 (例如 2PL)<br>MVCC 解决 RW 冲突，悲观锁解决 WW 冲突</li>
<li>MVCC + 乐观锁<br>MVCC 解决 RW 冲突，乐观锁解决 WW 冲突</li>
</ul>
</li>
</ul>
</li>
</ol>
<h3 id="C"><a href="#C" class="headerlink" title="C++"></a>C++</h3><ol>
<li>构造函数是否可以是虚函数？</li>
<li>智能指针的实现</li>
</ol>
<h3 id="代码"><a href="#代码" class="headerlink" title="代码"></a>代码</h3><ol>
<li>LRU leetcode原题</li>
<li>来自中文 leetcode <a href="https://leetcode-cn.com/problems/IQvJ9i/" target="_blank" rel="noopener">LCP 27. 黑盒光线反射</a></li>
</ol>
</div>
<footer class="article-footer">
<a data-url="http://yoursite.com/2021/03/09/interview-%E8%9A%82%E8%9A%81%E9%9B%86%E5%9B%A2-%E6%95%B0%E5%AD%97%E6%8A%80%E6%9C%AF%E9%83%A8-2021-2-28/" data-id="ckp3d9fat0006gwrtczp557vg" class="article-share-link">Share</a>
</footer>
</div>
</article>
<nav id="page-nav">
<span class="page-number current">1</span><a class="page-number" href="/page/2/">2</a><a class="extend next" rel="next" href="/page/2/">Next &raquo;</a>
</nav>
</section>
<aside id="sidebar">
<div class="widget-wrap">
<h3 class="widget-title">Archives</h3>
<div class="widget">
<ul class="archive-list"><li class="archive-list-item"><a class="archive-list-link" href="/archives/2021/05/">May 2021</a></li><li class="archive-list-item"><a class="archive-list-link" href="/archives/2021/04/">April 2021</a></li><li class="archive-list-item"><a class="archive-list-link" href="/archives/2021/03/">March 2021</a></li><li class="archive-list-item"><a class="archive-list-link" href="/archives/2021/02/">February 2021</a></li><li class="archive-list-item"><a class="archive-list-link" href="/archives/2020/12/">December 2020</a></li><li class="archive-list-item"><a class="archive-list-link" href="/archives/2020/01/">January 2020</a></li></ul>
</div>
</div>
<div class="widget-wrap">
<h3 class="widget-title">Recent Posts</h3>
<div class="widget">
<ul>
<li>
<a href="/2021/05/07/%E5%AF%86%E9%9B%86%E7%B4%A2%E5%BC%95%E5%92%8C%E7%A8%80%E7%96%8F%E7%B4%A2%E5%BC%95/">密集索引和稀疏索引</a>
</li>
<li>
<a href="/2021/04/30/MySQL/">MySQL</a>
</li>
<li>
<a href="/2021/04/27/CPU%E5%88%86%E6%94%AF%E9%A2%84%E6%B5%8B%E5%AF%B9%E6%80%A7%E8%83%BD%E7%9A%84%E5%BD%B1%E5%93%8D/">CPU分支预测对性能的影响</a>
</li>
<li>
<a href="/2021/04/12/%E8%AE%BE%E8%AE%A1%E6%A8%A1%E5%BC%8F/">设计模式</a>
</li>
<li>
<a href="/2021/04/08/linux-IO/">linux IO</a>
</li>
</ul>
</div>
</div>
</aside>
</div>
<footer id="footer">
<div class="outer">
<div id="footer-info" class="inner">
© 2021 l-iberty<br>
Powered by <a href="http://hexo.io/" target="_blank">Hexo</a>
</div>
</div>
</footer>
</div>
<nav id="mobile-nav">
<a href="/" class="mobile-nav-link">Home</a>
<a href="/archives" class="mobile-nav-link">Archives</a>
</nav>
<script src="//ajax.googleapis.com/ajax/libs/jquery/2.0.3/jquery.min.js"></script>
<link rel="stylesheet" href="/fancybox/jquery.fancybox.css">
<script src="/fancybox/jquery.fancybox.pack.js"></script>
<script src="/js/script.js"></script>
</div>
</body>
</html>