ConcurrentHashMap
作者:admin
发布日期:2019-11-22

       

  。对于ConcurrentHashMap是如何提高其效率的,可能大多人只是知道它使用了多个锁代替HashTable中的单个锁,也就是。实际上,ConcurrentHashMap对提高并发方面的优化,还有一些其它的技巧在里面(比如你是否知道在get操作的时候,它是否也使用了锁来保护?)。

  我们不关心ConcurrentMap中新增的接口,重点理解一下内存一致性效果中的“happens-before”是怎么回事。因为要想从根本上讲明白,这个是无法避开的。这又不得不从Java存储模型来谈起了。

  这是一个多线程之间内存可见性(Visibility)顺序不一致的问题。有两种可能会造成上面的D选项。

  上面的话是《Java并发编程实践》一书中引自Java语言规范的,感觉翻译的不太好。简单的说:假设代码有两条语句,代码顺序是语句1先于语句2执行;那么只要语句2不依赖于语句1的结果,打乱它们的顺序对最终的结果没有影响的话,那么真正交给CPU去执行时,他们的顺序可以是没有限制的。可以允许语句2先于语句1被CPU执行,和代码中的顺序不一致。

  重排序(Reordering)是JVM针对现代CPU的一种优化,Reordering后的指令会在性能上有很大提升。(不知道这种优化对于多核CPU是否更加明显,也或许和单核多核没有关系。)

  因为我们例子中的两条赋值语句,并没有依赖关系,无论谁先谁后结果都是一样的,所以就可能有Reordering的情况,这种情况下,对于其他线程来说就可能造成了可见性顺序不一致的问题。

  JLS中对线程和主存互操作定义了6个行为,分别为load,save,read,write,assign和use,这些操作行为具有原子性,且相互依赖,有明确的调用先后顺序。这个细节也比较繁琐,我们暂不深入追究。先简单认为线程在修改一个变量时,先拷贝入线程工作内存中,在线程工作内存修改后再写回主存(Main Memery)中。

  假设例子中Reording后顺序仍与代码中的顺序一致,那么接下来呢?有意思的事情就发生在线程把Working Copy Memery中的变量写回Main Memery的时刻。线程1把变量写回Main Memery的过程对线程2的可见性顺序也是无法保证的。

  上面的列子,a=3; b=4; 这两个语句在 Working Copy Memery中执行后,写回主存的过程对于线程2来说同样可能出现先b=4;后a=3;这样的相反顺序。

  正因为上面的那些问题,JMM中一个重要问题就是:如何让多线程之间,对象的状态对于各线程的“可视性”是顺序一致的。它的解决方式就是 Happens-before 规则:

  JMM为所有程序内部动作定义了一个偏序关系,叫做happens-before。要想保证执行动作B的线程看到动作A的结果(无论A和B是否发生在同一个线程中),A和B之间就必须满足happens-before关系。

  我们现在来看一下“Happens-before”规则都有哪些(摘自《Java并发编程实践》):

  before于该线程中的每一个动作B,其中,在程序中,所有的动作B都能出现在A之后。 ② 监视器锁法则:对一个监视器锁的解锁 happens

  before于每一个后续对同一监视器锁的加锁。 ③ volatile变量法则:对volatile域的写入操作happens

  before于每一个后续对同一个域的读写操作。 ④ 线程启动法则:在一个线程里,对Thread.start的调用会happens

  before于其他线程检测到这个线程已经终结、或者从Thread.join调用中成功返回,或Thread.isAlive返回false。 ⑥ 中断法则:一个线程调用另一个线程的interrupt happens

  before于被中断的线程发现中断。 ⑦ 终结法则:一个对象的构造函数的结束happens

  早期Java中的锁只有最基本的synchronized,它是一种互斥的实现方式。在Java5之后,增加了一些其它锁,比如ReentrantLock,它基本作用和synchronized相似,但提供了更多的操作方式,比如在获取锁时不必像synchronized那样只是傻等,可以设置定时,轮询,或者中断,这些方法使得它在获取多个锁的情况可以避免死锁操作。

  b) 用volatile修饰的变量,不能保证该变量状态的改变对于其他线程来说是一种“原子化操作”。

  在Java5之前,JMM对Volatile的定义是:保证读写volatile都直接发生在main memory中,线程的working memory不进行缓存。它只承诺了读和写过程的可见性,并没有对Reording做限制,所以旧的Volatile并不太可靠。在Java5之后,JMM对volatile的语义进行了增强。就是我们看到的③ volatile变量法则。

  不变模式(immutable)是多线程安全里最简单的一种保障方式。因为你拿他没有办法,想改变它也没有机会。

  不变模式主要通过final关键字来限定的。在JMM中final关键字还有特殊的语义。Final域使得确保初始化安全性(initialization safety)成为可能,初始化安全性让不可变形对象不需要同步就能自由地被访问和共享。

  3)经过前面的了解,下面我们用Happens-Before规则理解一个经典问题:双重检测锁(DCL)为什么在java中不适用?

  我想简单的用对象创建期间的实际场景来分析一下:(注意,这种场景是我个人的理解,所看的资料也是非官方的,不完全保证正确。如果发现不对请指出。

  看看 new LazySingleton(); 这个语句的执行过程: 它不是一个原子操作,实际是由多个步骤,我们从我们关注的角度简化一下,简单的认为它主要有2步操作好了:

  此时因为线程1和线程2没有用同步,他们之间不存在“Happens-Before”规则的约束,所以在线程1创建LazySingleton对象的 a),b)这两个步骤对于线程2来说会有可能出现a)可见,b)不可见

  之所以这里举到 DCL这个例子,是因为我们后边分析ConcurrentHashMap时,也会遇到相似的情况。

  对于对象的创建,出于乐观考虑,两个线程之间没有用“Happens-Before规则来约束”另一个线程可能会得到一个未创建完整的对象,这种情况必须要检测,后续分析ConcurrentHashMap时再讨论。

  对于哈希表,Java中采用链表的方式来解决hash冲突的。一个HashMap的数据结构看起来类似下图:

  实现了同步的HashTable也是这样的结构,它的同步使用锁来保证的,并且所有同步操作使用的是同一个锁对象。这样若有n个线程同时在get时,这n个线程要串行的等待来获取锁。

  ConcurrentHashMap中对这个数据结构,针对并发稍微做了一点调整。它把区间按照并发级别(concurrentLevel),分成了若干个segment。默认情况下内部按并发级别为16来创建。对于每个segment的容量,默认情况也是16。当然并发级别(concurrentLevel)和每个段(segment)的初始容量都是可以通过构造函数设定的。

  看起来只是把以前HashTable的一个hash bucket创建了16份而已。有什么特别的吗?没啥特别的。

  Segment继承了ReentrantLock,表明每个segment都可以当做一个锁。(ReentrantLock前文已经提到,不了解的话就把当做synchronized的替代者吧)这样对每个segment中的数据需要同步操作的话都是使用每个segment容器对象自身的锁来实现。只有对全局需要改变时锁定的是所有的segment。

  面的这种做法,就称之为“分离锁(lock striping)”。有必要对“分拆锁”和“分离锁”的概念描述一下:

  分拆锁(lock spliting)就是若原先的程序中多处逻辑都采用同一个锁,但各个逻辑之间又相互独立,就可以拆(Spliting)为使用多个锁,每个锁守护不同的逻辑。 分拆锁有时候可以被扩展,分成可大可小加锁块的集合,并且它们归属于相互独立的对象,这样的情况就是分离锁(lock striping)。(摘自《Java并发编程实践》)

  看上去,单是这样就已经能大大提高多线程并发的性能了。还没完,继续看我们关注的get,put,remove这三个函数怎么保证数据同步的。

  它也没有使用锁来同步,只是判断获取的entry的value是否为null,为null时才使用加锁的方式再次去获取。

  第一步,先判断一下 count != 0;count变量表示segment中存在entry的个数。如果为0就不用找了。

  假设这个时候恰好另一个线程put或者remove了这个segment中的一个entry,会不会导致两个线程看到的count值不一致呢?

  它使用了volatile来修改。我们前文说过,Java5之后,JMM实现了对volatile的保证:对volatile域的写入操作happens-before于每一个后续对同一个域的读写操作。

  第二步,获取到要该key所在segment中的索引地址,如果该地址有相同的hash对象,顺着链表一直比较下去找到该entry。当找到entry的时候,先做了一次比较:if(v != null)我们用红色注释的地方。

  考虑一下,如果这个时候,另一个线程恰好新增/删除了entry,或者改变了entry的value,会如何?

  除了 value,其它成员都是final修饰的,也就是说value可以被改变,相当于一个Subscription集合。其它都不可以改变,包括指向下一个HashEntry的next也不能被改变。(那删除一个entry时怎么办?后续会讲到。)

  因为每个HashEntry中的next也是final的,没法对链表最后一个元素增加一个后续entry所以新增一个entry的实现方式只能通过头结点来插入了。

  newEntry对象是通过new HashEntry(K k , V v, HashEntry next)来创建的。如果另一个线程刚好new 这个对象时,当前线程来get它。因为没有同步,就可能会出现当前线程得到的newEntry对象是一个没有完全构造好的对象引用。

  回想一下我们之前讨论的DCL的问题,这里也一样,九号彩票登录网站,没有锁同步的话,new 一个对象对于多线程看到这个对象的状态是没有保障的,这里同样有可能一个线程new这个对象的时候还没有执行完构造函数就被另一个线程得到这个对象引用。

  所以才需要判断一下:if (v != null)如果确实是一个不完整的对象,则使用锁的方式再次get一次。

  有没有可能会put进一个value为null的entry? 不会的,已经做了检查,这种情况会抛出异常,所以 ②处的判断完全是出于对多线程下访问一个new出来的对象的状态检测。

  假设我们的链表元素是:e1-> e2 -> e3 -> e4 我们要删除 e3这个entry,因为HashEntry中next的不可变,所以我们无法直接把e2的next指向e4,而是将要删除的节点之前的节点复制一份,形成新的链表。

  如果我们get的也恰巧是e3,可能我们顺着链表刚找到e1,这时另一个线程就执行了删除e3的操作,而我们线程还会继续沿着旧的链表找到e3返回。这里没有办法实时保证了。

  我们第①处就判断了count变量,它保障了在 ①处能看到其他线程修改后的。①之后到②之间,如果再次发生了其他线程再删除了entry节点,就没法保证看到最新的了。

  不过这也没什么关系,即使我们返回e3的时候,它被其他线程删除了,暴漏出去的e3也不会对我们新的链表造成影响。

  这其实是一种乐观设计,设计者假设 ①之后到②之间 发生被其它线程增、删、改的操作可能性很小,所以不采用同步设计,而是采用了事后(其它线程这期间也来操作,并且可能发生非安全事件)弥补的方式。

  而因为其他线程的“改”和“删”对我们的数据都不会造成影响,所以只有对“新增”操作进行了安全检查,就是②处的非null检查,如果确认不安全事件发生,则采用加锁的方式再次get。

  这样做减少了使用互斥锁对并发性能的影响。可能有人怀疑remove操作中复制链表的方式是否代价太大,这里我没有深入比较,不过既然Java5中这么实现,我想new一个对象的代价应该已经没有早期认为的那么严重。

  我们基本分析完了get操作。对于put和remove操作,是使用锁同步来进行的,不过是用的ReentrantLock而不是synchronized,性能上要更高一些。它们的实现前文都已经提到过,就没什么可分析的了。

  我们还需要知道一点,ConcurrentHashMap的迭代器不是Fast-Fail的方式,所以在迭代的过程中别其他线程添加/删除了元素,不会抛出异常,也不能体现出元素的改动。但也没有关系,因为每个entry的成员除了value都是final修饰的,暴漏出去也不会对其他元素造成影响。

  如果线程b先执行了clear,清空了一部分segment的时候,线程a执行了put且正好把“first”放入了“清空过”的segment中,而把“second”放到了还没有清空过的segment中,就会出现上面的情况。

  第二段代码,如果线程b执行了迭代遍历到first,而此时线程a还没有remove掉first,那么即使后续删除了first,迭代器里不会反应出来,也不抛出异常,这种迭代器被称为“弱一致性”(weakly consistent)迭代器。

上一篇:【十一月初的四】与诗相遇 与你相遇|青春,是散场的电影
下一篇:没有了