并发-基于锁的并发数据结构type
status
date
slug
summary
tags
category
icon
password
Property
通过锁可以使数据结构线程安全（thread safe）
并发计数器
计数器是最简单的一种数据结构，使用广泛而且接口简单。一个非并发的计数器：
没有同步机制的计数器很简单但无法拓展，但如何让它线程安全？
这个并发计数器简单、正确。实际上，它遵循了最简单、最基本的并发数据结构中常见的数据模式：它只是加了一把锁，在调用函数操作该数据结构时获取锁，从调用返回时释放锁。这种方式类似基于
观察者（monitor）的数据结构，在调用、退出对象方法时，会自动获取锁、释放锁。现在，有了一个并发数据结构，问题可能就是性能了。如果这个结构导致运行速度太慢，那么除了简单加锁，还需要进行优化。
同步的计数器扩展性不好。单线程完成100 万次更新只需要很短的时间（大约0.03s），而两个线程并发执行，每个更新100 万次，性能下降很多。线程更多时，性能更差。
可扩展的计数器-懒惰计数器(sloppy counter)
懒惰计数器通过多个局部计数器和一个全局计数器来实现一个逻辑计数器，其中每个CPU 核心有一个局部计数器。具体来说，在4 个CPU 的机器上，有4 个局部计数器和1 个全局计数器。除了这些计数器，还有锁：每个局部计数器有一个锁，全局计数器有一个。
懒惰计数器的基本思想：如果一个核心上的线程想增加计数器，那就增加它的局部计数器，访问这个局部计数器是通过对应的局部锁同步的。因为每个 CPU 有自己的局部计数器，不同 CPU 上的线程不会竞争，所以计数器的更新操作可扩展性好。但是，为了保持全局计数器更新（以防某个线程要读取该值），局部值会定期转移给全局 计数器，方法是获取全局锁，让全局计数器加上局部计数器的值，然后将局部计数器置零。 这种局部转全局的频度，取决于一个阈值，这里称为 S（表示 sloppiness）。S 越小，懒惰计数器则越趋近于非扩展的计数器。S 越大，扩展性越强，但是全局计数器与实际计数的偏差越大。我们可以抢占所有的局部锁和全局锁（以特定的顺序，避免死锁），以获得精确值，但这种方法没有扩展性
并发链表
代码插入函数入口处获取锁，结束时释放锁。如果malloc失败，会有一点小问题，在这种情况下，代码在插入失败之前，必须释放锁。事实表明，这种异常控制流容易产生错误。
我们能够重写插入和查找函数，保持并发插入正确，但避免在失败情况下也需要调用释放锁吗？
在这个例子中，答案是可以。调整代码，让获取锁和释放锁只环绕插入代码的真正临界区。前面的方法有效是因为部分工作实际上不需要锁，假定 malloc()是线程安全的，每个线程都可以调用它，不需要担心竞争条件和其他并发缺陷。只有在更新共享列表时需要持有锁。
下面的代码展示了这些修改的细节。 对于查找函数，进行了简单的代码调整，跳出主查找循环，到单一的返回路径。这样做减少了代码中需要获取锁、释放锁的地方，降低了代码中不小心引入缺陷（诸如在返回前忘记释放锁）的可能性。
并发队列
有两个锁，一个负责队列头，另一个负责队列尾。这两个锁使得入队列操作和出队列操作可以并发执行，因为入队列只访问 tail 锁，而出队列只访问 head 锁。
Michael 和 Scott 使用了一个技巧，添加了一个假节点（在队列初始化的代码里分配的）。该假节点分开了头和尾操作。
队列在多线程程序里广泛使用。然而，这里的队列（只是加了锁）通常不能完全满足这种程序的需求。更完善的有界队列，在队列空或者满时，能让线程等待。
并发散列表
