2019-08-30: 如何保证容器是线程安全的？ConcurrentHashMap如何实现高效地线程安全？

firehell commented 5 years ago

群昵称

杭州-张钊

如何保证容器是线程安全的？

通过synchronized

ConcurrentHashMap如何实现高效地线程安全？

看代码好像是给node加了关键字，这样保证在这个节点锁住时不影响使用其他节点

skylarliuu commented 5 years ago

保证容器是线程安全的，有三种方式：

使用古老的Hashtable、Vector等线程安全的容器，它们内部都用synchronized直接修饰方法来保证线程安全，性能较低。
使用Collections工具类提供的包装方法，获取一个同步的包装容器。实际上内部也只是简单用一个mutex包装一下调用方法，性能较低。
使用Java并发包提供的并发工具类，可以按照场景选择合适的工具类，这是最佳方式。

ConcurrentHashMap的底层实现在Java8发生了非常大的变化，这里主要说一下Java7和Java8中ConcurrentHashMap的实现原理。

（还没有看懂，未完待补充）

liu1813565583 commented 5 years ago

Java提供了不同层面地线程安全支持.在传统集合框架内部,除了Hashtable等同步容器.还提供了所谓地同步包装器(Synchronized Wrapper);我们可以调用Collections工具类提供地包装方法,来获取一个同步地包装容器(如Collections.synchronizedMap),但是它们都是利用非常粗粒度地同步方式,在高并发情况下,性能比较低下.

另外,更加普遍地选择是利用并发包提供地线程安全容器类,它提供了:

各种并发容器,比如ConcurrentHashMap,CopyOnWriteArrayList. 各种线程安全队列(Queue/Deque),如ArrayBlockingQueue,SynchronousQueue 各种有序容器的线程安全版本等. 具体保证线程安全的方式,包括有从简单的synchronize方式,到基于更加精细化的,比如基于分离锁实现的ConcurrentHashMap等并发实现的.

chinwetang commented 5 years ago

我在上个问题中说到ConcurrentHashMap用分段锁来解决并发编程的问题，在安全和性能之间平衡，被许多同学指出JDK1.8已经换用synchronized+CAS（Compare And Swap），惭愧之余也是赶紧补了一下课，发现JDK1.8的ConcurrentHashMap，锁的粒度更小，数组上的数据采用无锁解决方案。

synchronized与CAS的分工

看了部分源码，我发现只要是数组上的数据，既头节点，就采用CAS的来解决并发，否则就锁住头节点，用synchronized解决并发问题，这点上可以从很多代码片段看出来，比如：

remove方法，已经锁住了头节点，在链上查找要被删除的节点，但是找到最后发现只有头节点，仍然老老实实的用了内部实现为CAS的 setTabAt(tab, i, e.next)

synchronized (f) {

...省略代码...
                                if (e.hash == hash &&
                                    ((ek = e.key) == key ||
                                     (ek != null && key.equals(ek)))) {
                                    V ev = e.val;
                                    if (cv == null || cv == ev ||
                                        (ev != null && cv.equals(ev))) {
                                        oldVal = ev;
                                        if (value != null)
                                            e.val = value;
                                        else if (pred != null)
                                            pred.next = e.next;
                                        else
                                            setTabAt(tab, i, e.next);
                                    }
                                    break;
                                }

...省略代码...
}

put方法中，如果该节点在数组上为null，也是早早的用了内部实现为CAS的casTabAt(tab, i, null,new Node<K,V>(hash, key, value, null))，剩下的才用synchronized锁住进行操作。

...省略代码...
if ((f = tabAt(tab, i = (n - 1) & hash)) == null) {
                if (casTabAt(tab, i, null,
                             new Node<K,V>(hash, key, value, null)))
                    break;                   // no lock when adding to empty bin
            }
            else if ((fh = f.hash) == MOVED)
                tab = helpTransfer(tab, f);
            else {
                V oldVal = null;
                synchronized (f) {
...省略代码...

为什么这么分工？

首先每条链或者说每颗红黑树单独一个锁是可以理解的，因为锁的粒度越小，效率越高，这个是大家都可以理解的，比起之前的分段锁，现在每个坑位就是一个锁，粒度确实小了很多。

但是数组上的数据是无法通过这种方式保证并发安全的，因为可能为null，这个时候头节点都没有，也就无从谈起用头节点的锁了，可是比起链表和红黑树，数组有另一个好处就是地址是确定的，我们可以通过下标索引方便的找到那个地址，这样一来，就为CAS提供了实现的可能性，因为CAS是【比较-替换】，需要从内存地址中取出旧数据进行比较，而数组就可以很方便的取得这个内存地址。

这也是为什么链表和红黑树上的节点不采用CAS的原因，因为它们的地址是受上一个节点影响的，而一旦涉及到需要解决多个共享变量的安全问题，就不是CAS所擅长的了。

关于ConcurrentHashMap，可以做文章的地方其实有很多，比如它的多线程扩容，但是限于个人水平和时间精力有限，没办法一一阐述，光是上面讲的也是一点心得，也不能保证正确，欢迎大家给我提建议或者意见。

MicroKibaco commented 5 years ago

如何保证容器是线程安全的?

在做数据操作时候,底层加atomic 或 synchronized ,ReentrantReadWriteLock 等加锁容器 ,都能实现线程安全

ConcurrentHashMap如何实现高效地线程安全？

JDK 1.7 中 ConcurrentHashMap 线程安全是通过Segment 分段锁来实现线程安全的,解决并发问题
JDK 1.8 中, ConcurrentHashMap 线程安全是通过 synchronized + CAS 实现线程安全的。

具体实现过程,希望大家源码验证,然后把你的疑惑及时在技术讨论群里反馈。

MicroKibaco / CrazyDailyQuestion