基础设施优化学习
<h1>1. CPU缓存</h1>
<p>任何代码的执行都依赖 CPU。</p>
<p>由于 CPU 缓存由更快的 SRAM 构成（内存是由 DRAM 构成的），而且离 CPU 核心更近，如果运算时需要的输入数据是从 CPU 缓存，而不是内存中读取时，运算速度就会快很多。</p>
<h4>CPU 缓存分为数据缓存与指令缓存对于数据缓存，我们应在循环体中尽量操作同一块内存上的数据，由于缓存是根据 CPU Cache Line 批量操作数据的，所以顺序地操作连续内存数据时也有性能提升。</h4>
<h4>对于指令缓存，有规律的条件分支能够让 CPU 的分支预测发挥作用，进一步提升执行效率。对于多核系统，如果进程的缓存命中率非常高，则可以考虑绑定 CPU 来提升缓存命中率。</h4>
<h3>1.1 CPU 的多级缓存</h3>
<p>CPU 缓存离 CPU 核心更近，由于电子信号传输是需要时间的，所以离 CPU 核心越近，缓存的读写速度就越快。但 CPU 的空间很狭小，离 CPU 越近缓存大小受到的限制也越大。</p>
<p>综合硬件布局、性能等因素，CPU 缓存通常分为大小不等的三级缓存。</p>
<pre><code>Linux 系统上，离 CPU 最近的一级缓存是 32KB，二级缓存是 256KB，最大的三级缓存则是 20MB。
三级缓存要比一、二级缓存大许多倍
因为当下的 CPU 都是多核心的，每个核心都有自己的一、二级缓存，但三级缓存却是一颗CPU上所有核心共享的。</code></pre>
<p><img src="https://www.showdoc.com.cn/server/api/attachment/visitfile/sign/e431725693e724d7bcc0d35ac9f3b518" alt="" /></p>
<h4>程序执行时，会先将内存中的数据载入到共享的三级缓存中，再进入每颗核心独有的二级缓存，最后进入最快的一级缓存，之后才会被CPU使用。</h4>
<p>缓存要比内存快很多。CPU 访问一次内存通常需要 100 个时钟周期以上，而访问一级缓存只需要 4~5 个时钟周期，二级缓存大约 12 个时钟周期，三级缓存大约 30 个时钟周期（对于 2GHZ 主频的 CPU 来说，一个时钟周期是 0.5 纳秒。</p>
<p>如果 CPU 所要操作的数据在缓存中，则直接读取，这称为缓存命中。命中缓存会带来很大的性能提升，因此，我们的代码优化目标是提升 CPU 缓存的命中率。</p>
<h3>1.2 提升数据缓存的命中率</h3>
<h4>按照内存布局顺序访问</h4>
<pre><code>遍历二维数组 int array[N][N]
用 array[j][i]和 array[i][j]访问数组元素，array[j][i]执行的时间是后者 array[i][j]的 8 倍之多</code></pre>
<p>二维数组 array 所占用的内存是连续的，比如若长度 N 的值为 2，那么内存中从前至后各元素的顺序是：array[0][0]，array[0][1]，array[1][0]，array[1][1]。如果用 array[i][j]访问数组元素，则完全与上述内存中元素顺序一致，因此访问 array[0][0]时，缓存已经把紧随其后的 3 个元素也载入了，CPU 通过快速的缓存来读取后续 3 个元素就可以。如果用 array[j][i]来访问，访问的顺序就是：array[0][0]，array[1][0]，array[0][1]，array[1][1]。此时内存是跳跃访问的，如果 N 的数值很大，那么操作 array[j][i]时，是没有办法把 array[j+1][i]也读入缓存的。</p>
<p>【CPU Cache Line】 相关，它定义了缓存一次载入数据的大小，通常是 64 字节。</p>
<p>当载入 array[0][0]时，若它们占用的内存不足 64 字节，CPU 就会顺序地补足后续元素。顺序访问的 array[i][j]因为利用了这一特点，所以就会比 array[j][i]要快。也正因为这样，当元素类型是 4 个字节的整数时，性能就会比 8 个字节的高精度浮点数时速度更快，因为缓存一次载入的元素会更多。</p>
<p>在二维数组中，其实第一维元素存放的是地址，第二维存放的才是目标元素。由于 64 位操作系统的地址占用 8 个字节（32 位操作系统是 4 个字节），因此，每批 Cache Line 最多也就能载入不到 8 个二维数组元素，所以性能差距大约接近 8 倍。</p>
<pre><code>Linux 操作系统，可以通过一个名叫 Perf 的工具直观地验证缓存命中的情况（可以用 yum install perf 或者 apt-get install perf 安装)
执行 perf stat 可以统计出进程运行时的系统信息（通过 -e 选项指定要统计的事件，如果要查看三级缓存总的命中率，可以指定缓存未命中 cache-misses 事件，以及读取缓存次数 cache-references 事件，两者相除就是缓存的未命中率，用 1 相减就是命中率。类似的，通过 L1-dcache-load-misses 和 L1-dcache-loads 可以得到 L1 缓存的命中率）。</code></pre>
<h3>1.3 提升指令缓存的命中率</h3>
<pre><code>int array[N];
for (i = 0; i < TESTN; i++) array[i] = rand() % 256;</code></pre>
<p>一个元素为 0 到 255 之间随机数字组成的数组,接下来要对它做两个操作：一是循环遍历数组，判断每个数字是否小于 128，如果小于则把元素的值置为 0；二是将数组排序。</p>
<h4>结论：先排序的遍历时间只有后排序的三分之一</h4>
<h4>原因：CPU含有分支预测器</h4>
<p>当代码中出现 if、switch 等语句时，意味着此时至少可以选择跳转到两段不同的指令去执行。如果分支预测器可以预测接下来要在哪段代码执行（比如 if 还是 else 中的指令），就可以提前把这些指令放在缓存中，CPU 执行时就会很快。当数组中的元素完全随机时，分支预测器无法有效工作，而当 array 数组有序时，分支预测器会动态地根据历史命中数据对未来进行预测，命中率就会非常高。</p>
<h3>1.4 提升多核 CPU 下的缓存命中率</h3>
<p>现代 CPU 几乎都是多核的。虽然三级缓存面向所有核心，但一、二级缓存是每颗核心独享的。即使只有一个 CPU 核心，现代分时操作系统都支持许多进程同时运行。这是因为操作系统把时间切成了许多片，微观上各进程按时间片交替地占用 CPU，这造成宏观上看起来各程序同时在执行。</p>
<p>因此，若进程 A 在时间片 1 里使用 CPU 核心 1，自然也填满了核心 1 的一、二级缓存，当时间片 1 结束后，操作系统会让进程 A 让出 CPU，基于效率并兼顾公平的策略重新调度 CPU 核心 1，以防止某些进程饿死。如果此时 CPU 核心 1 繁忙，而 CPU 核心 2 空闲，则进程 A 很可能会被调度到 CPU 核心 2 上运行，这样，即使我们对代码优化得再好，也只能在一个时间片内高效地使用 CPU 一、二级缓存了，下一个时间片便面临着缓存效率的问题。</p>
<p>因此，操作系统提供了将进程或者线程绑定到某一颗 CPU 上运行的能力。如 Linux 上提供了 sched_setaffinity 方法实现这一功能，其他操作系统也有类似功能的 API 可用。当多线程同时执行密集计算，且 CPU 缓存命中率很高时，如果将每个线程分别绑定在不同的 CPU 核心上，性能便会获得非常可观的提升</p>
<h1>2. 内存池</h1>
<p>当代码申请内存时，首先会到达应用层内存池，如果应用层内存池有足够的可用内存，就会直接返回给业务代码，否则，它会向更底层的 C 库内存池申请内存。</p>
<p>当 C 库内存池无法满足内存申请时，才会向操作系统内核申请分配内存。</p>
<p><img src="https://www.showdoc.com.cn/server/api/attachment/visitfile/sign/05f52a97d135d557058512cc18e593a4" alt="" /></p>
<p>Java 已经有了应用层内存池，为什么还会受到 C 库内存池的影响呢？</p>
<pre><code>除了 JVM 负责管理的堆内存外，Java 还拥有一些堆外内存，由于它不使用 JVM 的垃圾回收机制，所以更稳定、持久，处理 IO 的速度也更快。这些堆外内存就会由 C 库内存池负责分配，这是 Java 受到 C 库内存池影响的原因。</code></pre>
<h3>2.1 C 库内存池影响着系统下依赖它的所有进程。</h3>
<p>C 库内存池工作时，会预分配比你申请的字节数更大的空间作为内存池。比如说，当主进程下申请 1 字节的内存时，Ptmalloc2 （Linux 系统的默认 C 库内存池）会预分配 132K 字节的内存（Ptmalloc2 中叫 Main Arena），应用代码再申请内存时，会从这已经申请到的 132KB 中继续分配。</p>
<p>当释放这 1 字节时，Ptmalloc2 也不会把内存归还给操作系统。Ptmalloc2 认为，与其把这 1 字节释放给操作系统，不如先缓存着放进内存池里，仍然当作用户态内存留下来，进程再次申请 1 字节的内存时就可以直接复用，这样速度快了很多。</p>
<h3>2.2Java 进程被分配几个 GB 的内存池</h3>
<h4>多线程与单线程的预分配策略并不相同</h4>
<p>每个子线程预分配的内存是 64MB（Ptmalloc2 中被称为 Thread Arena，32 位系统下为 1MB，64 位系统下为 64MB）。如果有 100 个线程，就将有 6GB 的内存都会被内存池占用。当然，并不是设置了 1000 个线程，就会预分配 60GB 的内存，子线程内存池最多只能到 8 倍的 CPU 核数，比如在 32 核的服务器上，最多只会有 256 个子线程内存池，16GB（64MB * 256 = 16GB）的内存将一直被 Ptmalloc2 占用。</p>
<p>Linux 下的 JVM 编译时默认使用了 Ptmalloc2 内存池，因此每个线程都预分配了 64MB 的内存，这造成含有上百个 Java 线程的 JVM 多使用了 6GB 的内存。在多数情况下，这些预分配出来的内存池，可以提升后续内存分配的性能。</p>
<p>但Java 中的 JVM 内存池已经管理了绝大部分内存，确实不能接受莫名多出来 6GB 的内存，如何处理？</p>
<pre><code>首先可以调整 Ptmalloc2 的工作方式。通过设置 MALLOC_ARENA_MAX 环境变量，可以限制线程内存池的最大数量，当然，线程内存池的数量减少后，会影响 Ptmalloc2 分配内存的速度。不过由于 Java 主要使用 JVM 内存池来管理对象，这点影响并不重要。
其次可以更换掉 Ptmalloc2 内存池，选择一个预分配内存更少的内存池，比如 Google 的 TCMalloc。</code></pre>
<h3>2.3 Ptmalloc2 VS TCMalloc</h3>
<ul>
<li>
<p>TCMalloc 对多线程下小内存的分配特别友好</p>
<pre><code>每次分配内存，Ptmalloc2 一定要加锁，才能解决共享资源的互斥问题。然而，加锁的消耗并不小。如果你监控分配速度的话，会发现单线程服务调整为 100 个线程，Ptmalloc2 申请内存的速度会变慢 10 倍。TCMalloc 针对小内存做了很多优化，每个线程独立分配内存，无须加锁，所以速度更快</code></pre>
</li>
<li>
<p>线程数越多，Ptmalloc2 出现锁竞争的概率就越高，速度越慢</p>
</li>
<li>Ptmalloc2 更擅长大内存的分配 (以空间换时间)</li>
</ul>
<h4>结论：如果主要分配 256KB 以下的内存，特别是在多线程环境下，应当选择 TCMalloc；否则应使用 Ptmalloc2，它的通用性更好。</h4>
<h3>2.4 从栈中分配内存会更快</h3>
<p>每个线程都有独立的栈，所以分配内存时不需要加锁保护，而且栈上对象的尺寸在编译阶段就已经写入可执行文件了，执行效率更高！性能至上的 Golang 语言就是按照这个逻辑设计的，即使你用 new 关键字分配了堆内存，但编译器如果认为在栈中分配不影响功能语义时，会自动改为在栈中分配。</p>
<pre><code>在栈中分配内存也有缺点，它有功能上的限制。一是， 栈内存生命周期有限，它会随着函数调用结束后自动释放，在堆中分配的内存，并不随着分配时所在函数调用的结束而释放，它的生命周期足够使用。二是，栈的容量有限，如 CentOS 7 中是 8MB 字节，如果你申请的内存超过限制会造成栈溢出错误（比如，递归函数调用很容易造成这种问题），而堆则没有容量限制。</code></pre>
<h4>结论：当我们分配内存时，如果在满足功能的情况下，可以在栈中分配的话，就选择栈。</h4>
<h1>3. 索引</h1>
<h4>使用更多的空间建立索引，换取更短的查询时间</h4>
<p>索引很多种，哈希表、红黑树、B 树都可以在内存中使用</p>
<pre><code>面对大量数据，显然，遍历全部数据去匹配查询关键字，会非常耗时。如果使用额外的空间为这些数据创建索引，就可以基于索引实现快速查找</code></pre>
<h3>3.1 哈希表是最快的索引</h3>
<ul>
<li>O(1) 时间复杂度
<pre><code>1.首先，哈希表基于数组实现，而数组可以根据下标随机访问任意元素。数组之所以可以随机访问，是因为它由连续内存承载，且每个数组元素的大小都相等。于是，当知道下标后，把下标乘以元素大小，再加上数组的首地址，就可以获得目标访问地址，直接获取数据。
2.其次，哈希函数直接把查询关键字转换为数组下标，再通过数组的随机访问特性获取数据。比如，如果关键字是字符串，我们使用 BKDR 哈希算法将其转换为自然数，再以哈希数组大小为除数，对它进行求余，就得到了数组下标。</code></pre>
<p>哈希函数的执行时间是常量，数组的随机访问也是常量，时间复杂度就是 O(1)</p></li>
</ul>
<h4>“位图”的时间复杂度也是 O(1)</h4>
<pre><code>本质上是哈希表的变种，限制每个哈希桶只有 1 个比特位，所以，虽然它消耗的空间更少，但仅用于辅助数据的主索引，快速判断对象是否存在。位图常用于解决缓存穿透的问题，也常用于查找数组中的可用对象</code></pre>
<p><img src="https://www.showdoc.com.cn/server/api/attachment/visitfile/sign/a8fbf642173b9588ef1855ccea28abaa" alt="" /></p>
<h4>红黑树的时间复杂度就是 O(logN)</h4>
<pre><code>如果需求中需要做范围查询、遍历，由于哈希表没办法找到关键字相邻的下一个元素，所以哈希表不支持这类操作，可以选择红黑树作为索引。采用二分法的红黑树，检索 1 万条数据需要做 14 次运算，1 亿条也只需要 27 次而已。
如果红黑树过大，内存中放不下时，可以改用 B 树，将部分索引存放在磁盘上。磁盘访问速度要比内存慢很多，但 B 树充分考虑了机械磁盘寻址慢、顺序读写快的特点，通过多分支降低了树高，减少了磁盘读写次数。</code></pre>
<h3>3.2 内存结构与序列化方案</h3>
<h4>a. 对于动态（元素是变化的）哈希表，无法避免哈希冲突</h4>
<pre><code>链接法，落到数组同一个位置中的多个数据，通过链表串在一起。使用哈希函数查找到这个位置后，再使用链表遍历的方式查找数据。Java 标准库中的哈希表就使用链接法解决冲突。</code></pre>
<pre><code>开放寻址法，插入时若发现对应的位置已经占用，或者查询时发现该位置上的数据与查询关键字不同，开放寻址法会按既定规则变换哈希函数（例如哈希函数设为 H(key,i)，顺序地把参数 i 加 1），计算出下一个数组下标，继续在哈希表中探查正确的位置。</code></pre>
<p>链接法虽然实现简单，还允许存放元素个数大于数组的大小（也叫装载因子大于 1），但链接法序列化数据的代价很大，因为使用了指针后，内存是不连续的。</p>
<p>开放寻址法确保所有对象都在数组里，就可以把数组用到的这段连续内存原地映射到文件中（参考 Linux 中的 mmap，Java 等语言都有类似的封装），再通过备份文件的方式备份哈希表。虽然操作系统会自动同步内存中变更的数据至文件，但备份前还是需要主动刷新内存（参考 Linux 中的 msync，它可以按地址及长度来分段刷新，以减少 msync 的耗时），以确定备份数据的精确时间点。而新的进程启动时，可以通过映射磁盘中的文件到内存，快速重建哈希表提供服务。</p>
<h4>如果能将数据完整的放进数组，那么开放寻址法已经解决了序列化问题，所以我们应该选择开放寻址法。</h4>
<p>但是，有两个因素使得我们必须把数据放在哈希桶之外：</p>
<ol>
<li>每条数据有上百字节</li>
<li>哈希表中一定会有很多空桶（没有存放数据）。空桶的比例越高（装载因子越小），冲突概率也会越低，但如果每个空桶都占用上百字节，亿级规模会轻松把浪费的内存放大许多倍。</li>
</ol>
<h4>所以要把数据从哈希表中分离出来，提升哈希表的灵活性（灵活调整装载因子）。</h4>
<p>此时，该如何序列化哈希表以外的数据呢？最快速的序列化方案，还是像开放寻址法的散列表一样，使用定长数组存放对象，通过原地映射文件的方式序列化数据。由于数据未必是定长的，所以又分为两种情况。</p>
<p>一、数据的长度是固定的。
可以用另一个数组 D 存放数据，其中 D 的大小是待存放元素的最大数量，注意，D 可以远小于哈希数组的大小。如果哈希表是动态的，支持新建与删除元素操作，还需要把数组 D 中空闲的位置构建一个单链表，新建时从链表头取元素，删除时将元素归还至链表头部。
<img src="https://www.showdoc.com.cn/server/api/attachment/visitfile/sign/91362197685bc1af714bd2673b080baf" alt="" /></p>
<p>二、数据的长度并不固定。
此时，可以采用有限个定长数组存放数据，用以空间换时间的思想，加快访问速度。如下图中，D1 数组存放长度小于 L1 的数据，D2 数组存放长度在 L1 和 L2 之间的数据，以此类推。而哈希表数组 H 中，每个桶用 i 位存放该数据在哪个数组中，用 j 位存放数组下标。查找数据时，前 i 位寻找数组，后 j 位作为数组下标直接访问数据。
<img src="https://www.showdoc.com.cn/server/api/attachment/visitfile/sign/0a93d4a8f820833045de9aa8054c42cb" alt="" /></p>
<p>在这两种情况里，哈希桶不需要存放 8 字节 64 位的地址。因为，或许数组 D 的大小不到 1 亿，也就是说，你最多只需要寻址 1 亿条数据，这样 30 位足够使用。要知道，减少哈希桶的尺寸，就意味着同等内存下可以扩大哈希数组，从而降低装载因子。</p>
<h4>b. 降低哈希表的冲突概率</h4>
<p>虽然哈希冲突有解决方案，但若是所有元素都发生了冲突，哈希表的时间复杂度就退化成了 O(N)，即每查找一次都要遍历所有数据。所以，为了获得与数据规模无关的常量级时间，我们必须减少冲突的概率.</p>
<p>一、调优哈希函数
<img src="https://www.showdoc.com.cn/server/api/attachment/visitfile/sign/74de503988aa7b9e05a3d3a46aa4c856" alt="" /></p>
<p>哈希函数使得“abc”和“cba”两个关键字都落在了下标 39 上，造成了哈希冲突，是因为它丢失了字母的位置信息。BKDR 是优秀的哈希算法，但它不能以 28 作为基数，这会导致字符串分布不均匀。事实上，我们应当找一个合适的素数作为基数，比如 31，Java 标准库的 BKDR 哈希算法就以它为基数，它的计算量也很小：n<em>31 可以通过先把 n 左移 5 位，再减去 n 的方式替换（n</em>31 == n<<5 - n）。</p>
<p>一次位移加一次减法，要比一次乘法快得多。当然，图中的哈希函数之所以会丢失位置信息，是因为以 28 作为基数的同时，又把 28-1 作为除数所致，数学较好的同学可以试着推导证明，这里只需要记住，基数必须是素数就可以了。</p>
<p>当哈希函数把高信息量的关键字压缩成更小的数组下标时，一定会丢失信息。我们希望只丢失一些无关紧要的信息，尽量多地保留区分度高的信息。这需要分析关键字的特点、分布规律。比如，对于 11 位手机号，前 3 位接入号区分度最差，中间 4 位表示地域的数字信息量有所增强，最后 4 位个人号信息量最高。如果哈希桶只有 1 万个，那么通过 phonenum%10000，最大化保留后 4 位信息就是个不错的选择。</p>
<p>二、 扩容</p>
<pre><code>装载因子越接近于 1，冲突概率就会越大。我们不能改变元素的数量，只能通过扩容提升哈希桶的数量，减少冲突。</code></pre>
<p>由于哈希函数必须确保计算出的下标落在数组范围中，而扩容会增加数组的大小，进而影响哈希函数，因此，扩容前存放在哈希表中的所有元素，它们在扩容后的数组中位置都发生了变化。所以，扩容需要新老哈希表同时存在，通过遍历全部数据，用新的哈希函数把关键字放到合适的新哈希桶中。可见，扩容是一个极其耗时的操作，尤其在元素以亿计的情况下。</p>
<p>那么，在耗时以小时计的扩容过程中，如何持续提供正常服务呢？其实，只要把一次性的迁移过程，分为多次后台迁移，且提供服务时能够根据迁移情况选择新老哈希表即可。如果单机内存可以存放下新老两张哈希表，那么动态扩容不需要跨主机。反之，扩容过程将涉及新老哈希表所在的两台服务器，实现更为复杂，但原理是相同的。</p>
<h1>4. 锁</h1>
<h3>4.1 互斥锁与自旋锁</h3>
<p>互斥锁的加锁成本更高，但它在加锁失败时会释放 CPU 给其他线程；自旋锁则刚好相反。</p>
<p>当你无法判断锁住的代码会执行多久时，应该首选互斥锁。
（互斥锁是一种独占锁。当 A 线程取到锁后，互斥锁将被 A 线程独自占有，当 A 没有释放这把锁时，其他线程的取锁代码都会被阻塞）</p>
<h4>对于 99% 的线程级互斥锁而言，阻塞都是由操作系统内核实现的（比如 Linux 下它通常由内核提供的信号量实现）。</h4>
<p>当获取锁失败时，内核会将线程置为休眠状态，等到锁被释放后，内核会在合适的时机唤醒线程，而这个线程成功拿到锁后才能继续执行。
<img src="https://www.showdoc.com.cn/server/api/attachment/visitfile/sign/017f096cd905d15e3db7a2353dd07ac4" alt="" /></p>
<h4>互斥锁通过内核帮忙切换线程，简化了业务代码使用锁的难度。</h4>
<p>但是，线程获取锁失败时，增加了两次上下文切换的成本：从运行中切换为休眠，以及锁释放时从休眠状态切换为运行中。上下文切换耗时在几十纳秒到几微秒之间，或许这段时间比锁住的代码段执行时间还长。而且，线程主动进入休眠是高并发服务无法容忍的行为，这让其他异步请求都无法执行。</p>
<h4>如果能确定被锁住的代码执行时间很短，就应该用自旋锁取代互斥锁。</h4>
<p>自旋锁比互斥锁快得多，因为它通过 CPU 提供的 CAS 函数（全称 Compare And Swap），在用户态代码中完成加锁与解锁操作。</p>
<pre><code>加锁流程包括 2 个步骤：第 1 步查看锁的状态，如果锁是空闲的，第 2 步将锁设置为当前线程持有。
在没有 CAS 操作前，多个线程同时执行这 2 个步骤是会出错的。比如线程 A 执行第 1 步发现锁是空闲的，但它在执行第 2 步前，线程 B 也执行了第 1 步，B 也发现锁是空闲的，于是线程 A、B 会同时认为它们获得了锁。
CAS 函数把这 2 个步骤合并为一条硬件级指令。这样，第 1 步比较锁状态和第 2 步锁变量赋值，将变为不可分割的原子指令。于是，设锁为变量 lock，整数 0 表示锁是空闲状态，整数 pid 表示线程 ID，那么 CAS(lock, 0, pid) 就表示自旋锁的加锁操作，CAS(lock, pid, 0) 则表示解锁操作。
多线程竞争锁的时候，加锁失败的线程会“忙等待”，直到它拿到锁。什么叫“忙等待”呢？它并不意味着一直执行 CAS 函数，生产级的自旋锁在“忙等待”时，会与 CPU 紧密配合 ，它通过 CPU 提供的 PAUSE 指令，减少循环等待时的耗电量；对于单核 CPU，忙等待并没有意义，此时它会主动把线程休眠。</code></pre>
<h4>当取不到锁时，互斥锁用“线程切换”来面对，自旋锁则用“忙等待”来面对。这是两种最基本的处理方式，更高级别的锁都会选择其中一种来实现，比如读写锁就既可以基于互斥锁实现，也可以基于自旋锁实现。</h4>
<h3>4.2 允许并发持有的读写锁</h3>
<h4>如果能够明确区分出读和写两种场景，可以选择读写锁。</h4>
<p>读写锁由读锁和写锁两部分构成，仅读取共享资源的代码段用读锁来加锁，会修改资源的代码段则用写锁来加锁。</p>
<p>读写锁的优势在于，当写锁未被持有时，多个线程能够并发地持有读锁，这提高了共享资源的使用率。多个读锁被同时持有时，读线程并不会修改共享资源，所以它们的并发执行不会产生数据错误。</p>
<p>而一旦写锁被持有后，不只读线程必须阻塞在获取读锁的环节，其他获取写锁的写线程也要被阻塞。写锁就像互斥锁和自旋锁一样，是一种独占锁；而读锁允许并发持有，则是一种共享锁。</p>
<h4>因此，读写锁真正发挥优势的场景，必然是读多写少的场景，否则读锁将很难并发持有。</h4>
<p>实际上，读写锁既可以倾向于读线程，又可以倾向于写线程。前者我们称为读优先锁，后者称为写优先锁。</p>
<p>读优先锁更强调效率，它期待锁能被更多的线程持有。简单看下它的工作特点：当线程 A 先持有读锁后，即使线程 B 在等待写锁，后续前来获取读锁的线程 C 仍然可以立刻加锁成功，因为这样就有 A、C 这 2 个读线程在并发持有锁，效率更高。</p>
<p>再来看写优先的读写锁。同样的情况下，线程 C 获取读锁会失败，它将被阻塞在获取锁的代码中，这样，只要线程 A 释放读锁后，线程 B 马上就可以获取到写锁。
<img src="https://www.showdoc.com.cn/server/api/attachment/visitfile/sign/a917c4b19568930dcfb1c4a2c0d80ab5" alt="" /></p>
<pre><code>读优先锁并发性更好，但问题也很明显。
如果读线程源源不断地获取读锁，写线程将永远获取不到写锁。写优先锁可以保证写线程不会饿死;
但如果新的写线程源源不断地到来，读线程也可能被饿死。</code></pre>
<h4>用队列把请求锁的线程排队，按照先来后到的顺序加锁即可，当然读线程仍然可以并发，只不过不能插队到写线程之前。</h4>
<p>Java 中的 ReentrantReadWriteLock 读写锁，就支持这种排队的公平读写锁。</p>
<h3>4.3 乐观锁：不使用锁也能同步</h3>
<p>【悲观锁】同时修改资源的概率很高，很容易出现冲突，所以访问共享资源前，先加上锁，总体效率会更优。</p>
<p>【乐观锁】假定冲突的概率很低，所以它采用的“加锁”方式是，先修改完共享资源，再验证这段时间内有没有发生冲突。如果没有其他线程在修改资源，那么操作完成。如果发现其他线程已经修改了这个资源，就放弃本次操作。</p>
<h4>乐观锁全程并没有加锁，所以它也叫无锁编程</h4>
<h4>乐观锁虽然去除了锁操作，但是一旦发生冲突，重试的成本非常高。所以，只有在冲突概率非常低，且加锁成本较高时，才考虑使用乐观锁。</h4>