解决ABA问题

红太狼 2023-07-15 08:58 25阅读 0赞

前景描述：

多个线程并发地 去get遍历List，然后同时new 类去set，会出现线程安全问题，然后傻乎乎取stackOverfloer/githup

后台心态不好差差点想到把for遍历出的对象，放到queue，通过poll搞了，模拟Producer consumer的方式处理了,for处理的数量越大，，丢失的数量越多，技术不行要多读书，见图

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzMyNDQ3MzIx_size_16_color_FFFFFF_t_70][]

实解：“那个list add ，list得换成一个线程安全的，add操作会乱的 原因就是这里，，get是线程内操作，每个next是独享的没问题，，你把set全部注释，for 1000比 并发arraylist add 最终arraylist得不到1000个 因为它不安全，我纠结想解决的地方搞错了，，我一直想的时next.get地方 next被“ABA”困扰了

CopyOnWriteArrayList，，Collections.synchronizedList这种都是加锁，加锁之后就是串行处理了

**----------------------补充----------------------**

**[CopyOnWriteArrayList的实现原理][CopyOnWriteArrayList]**

还有处理方式就是把arraylist放到线程里面，作为线程的返回，最后面阻塞等待返回时addall，避免集合add的安全问题。

代码很简单，但是使用CopyOnWriteMap需要注意两件事情：

1. 减少扩容开销。根据实际需要，初始化CopyOnWriteMap的大小，避免写时CopyOnWriteMap扩容的开销。

2. 使用批量添加。因为每次添加，容器每次都会进行复制，所以减少添加次数，可以减少容器的复制次数。如使用上面代码里的addBlackList方法。

## CopyOnWrite的缺点　 ##

CopyOnWrite容器有很多优点，但是同时也存在两个问题，即内存占用问题和数据一致性问题。所以在开发的时候需要注意一下。

**　　内存占用问题**。因为CopyOnWrite的写时复制机制，所以在进行写操作的时候，内存里会同时驻扎两个对象的内存，旧的对象和新写入的对象（注意:在复制的时候只是复制容器里的引用，只是在写的时候会创建新对象添加到新容器里，而旧容器的对象还在使用，所以有两份对象内存）。如果这些对象占用的内存比较大，比如说200M左右，那么再写入100M数据进去，内存就会占用300M，那么这个时候很有可能造成频繁的Yong GC和Full GC。之前我们系统中使用了一个服务由于每晚使用CopyOnWrite机制更新大对象，造成了每晚15秒的Full GC，应用响应时间也随之变长。

针对内存占用问题，可以通过压缩容器中的元素的方法来减少大对象的内存消耗，比如，如果元素全是10进制的数字，可以考虑把它压缩成36进制或64进制。或者不使用CopyOnWrite容器，而使用其他的并发容器，如ConcurrentHashMap。

**　　数据一致性问题**。CopyOnWrite容器只能保证数据的最终一致性，不能保证数据的实时一致性。所以如果你希望写入的的数据，马上能读到，请不要使用CopyOnWrite容器。

##  CopyOnWriteArrayList为什么并发安全且性能比Vector好 ##

**　**我知道Vector是增删改查方法都加了synchronized，保证同步，但是每个方法执行的时候都要去获得锁，性能就会大大下降，而CopyOnWriteArrayList 只是在增删改上加锁，但是读不加锁，在读方面的性能就好于Vector，CopyOnWriteArrayList支持读多写少的并发情况。

[操作结果：][Link 1]

<table> 
 <tbody> 
  <tr> 
   <td>&nbsp;</td> 
   <td colspan="2">写操作</td> 
   <td colspan="2">读操作</td> 
  </tr> 
  <tr> 
   <td>&nbsp;</td> 
   <td>CopyOnWriteArrayList</td> 
   <td>&nbsp;Collections.<br> synchronizedList</td> 
   <td>CopyOnWriteArrayList</td> 
   <td>&nbsp;Collections.<br> synchronizedList</td> 
  </tr> 
  <tr> 
   <td>2</td> 
   <td>567</td> 
   <td>2</td> 
   <td>1</td> 
   <td>1</td> 
  </tr> 
  <tr> 
   <td>4</td> 
   <td>3088</td> 
   <td>3</td> 
   <td>2</td> 
   <td>2</td> 
  </tr> 
  <tr> 
   <td>8</td> 
   <td>25975</td> 
   <td>28</td> 
   <td>2</td> 
   <td>3</td> 
  </tr> 
  <tr> 
   <td>16</td> 
   <td>295936</td> 
   <td>44</td> 
   <td>2</td> 
   <td>6</td> 
  </tr> 
  <tr> 
   <td>32</td> 
   <td>－</td> 
   <td>－</td> 
   <td>3</td> 
   <td>8</td> 
  </tr> 
  <tr> 
   <td>64</td> 
   <td>－</td> 
   <td>－</td> 
   <td>7</td> 
   <td>21</td> 
  </tr> 
  <tr> 
   <td>128</td> 
   <td>－</td> 
   <td>－</td> 
   <td>9</td> 
   <td>38</td> 
  </tr> 
 </tbody> 
</table>

写操作：在线程数目增加时CopyOnWriteArrayList的写操作性能下降非常严重，而Collections.synchronizedList虽然有性能的降低，但下降并不明显。

读操作：在多线程进行读时，Collections.synchronizedList和CopyOnWriteArrayList均有性能的降低，但是Collections.synchronizedList的性能降低更加显著。

# 4 结论 #

CopyOnWriteArrayList，发生修改时候做copy，新老版本分离，保证读的高性能，适用于以读为主，读操作远远大于写操作的场景中使用，比如缓存。而Collections.synchronizedList则可以用在CopyOnWriteArrayList不适用，但是有需要同步列表的地方，读写操作都比较均匀的地方。

\---------------------------[并发][Link 2]补充------------

[并发集合][Link 2]

一个关于同步集合的缺点是，用集合的本身作为锁的对象。这意味着，在你遍历对象的时候，这个对象的其他方法已经被锁住，导致其他的线程必须等待。其他的线程无法操作当前这个被锁的集合，只有当执行的线程释放了锁。这会导致开销和性能较低。  
这就是为什么jdk1.5+以后提供了并发集合的原因，因为这样的集合性能更高。并发集合类并放在java.util.concurrent包下，根据三种安全机制被放在三个组中。

*  第一种为：写时复制集合：这种集合将数据放在一成不变的数组中；任何数据的改变，都会重新创建一个新的数组来记录值。这种集合被设计用在，读的操作远远大于写操作的情景下。有两个如下的实现类：CopyOnWriteArrayList 和 CopyOnWriteArraySet.  
    需要注意的是，写时复制集合不会抛出ConcurrentModificationException异常。因为这些集合是由不可变数组支持的，Iterator遍历值是从不可变数组中出来的，不用担心被其他线程修改了数据。
 *  第二种为：比对交换集合也称之为CAS（Compare-And-Swap）集合：这组线程安全的集合是通过CAS算法实现的。CAS的算法可以这样理解：  
    为了执行计算和更新变量，在本地拷贝一份变量，然后不通过获取访问来执行计算。当准备好去更新变量的时候，他会跟他之前的开始的值进行比较，如果一样，则更新值。  
    如果不一样，则说明应该有其他的线程已经修改了数据。在这种情况下，CAS线程可以重新执行下计算的值，更新或者放弃。使用CAS算法的集合有：ConcurrentLinkedQueue and ConcurrentSkipListMap.  
    需要注意的是，CAS集合具有不连贯的iterators，这意味着自他们创建之后并不是所有的改变都是从新的数组中来。同时他也不会抛出ConcurrentModificationException异常。
 *  第三种为：这种集合采用了特殊的对象锁（java.util.concurrent.lock.Lock）：这种机制相对于传统的来说更为灵活，可以如下理解：  
    这种锁和经典锁一样具有基本的功能，但还可以再特殊的情况下获取：如果当前没有被锁、超时、线程没有被打断。  
    不同于synchronization的代码,当方法在执行，Lock锁一直会被持有，直到调用unlock方法。有些实现通过这种机制把集合分为好几个部分来提供并发性能。比如：LinkedBlockingQueue，在队列的开后和结尾，所以在添加和删除的时候可以同时进行。  
    其他使用了这种机制的集合有：ConcurrentHashMap 和绝多数实现了BlockingQueue的实现类  
    同样的这一类的集合也具有不连贯的iterators，也不会抛出ConcurrentModificationException异常。

我们来总结下今天我们所学到的几个点：

1.  大部分在java.util包下的实现类都没有保证线程安全为了保证性能的优越，除了Vector和Hashtable以外。
2.  通过Collection可以创建线程安全类，但是他们的性能都比较差。
3.  同步集合既保证线程安全也在给予不同的算法上保证了性能，他们都在java.util.concurrent包中。

翻译来自：  
[https://www.codejava.net/java-core/collections/understanding-collections-and-thread-safety-in-java][https_www.codejava.net_java-core_collections_understanding-collections-and-thread-safety-in-java]

[AtomicStampedReference解决ABA问题][AtomicStampedReference_ABA]

`Collections.synchronizedList(new ArrayList())` returns a Thread-Safe wrapper of collection where access to each method is locked on wrapper instance which means only one thread can call any methods on this wrapper. But when you want to iterate over list and perform some mutable operations then you need to synchronize iterations over this list on wrapper object, from javadoc:

It is imperative that the user manually synchronize on the returned list when iterating over it:
    
            List list = Collections.synchronizedList(new ArrayList());
                     ...
                 synchronized (list) {
                     Iterator i = list.iterator(); // Must be in synchronized block
                     while (i.hasNext())
                         foo(i.next());
                 }
    
    Failure to follow this advice may result in non-deterministic behavior.

If it's crucial to iterate over list cuncurently then `CopyOnWriteArrayList` might be a way to go. It allows you to have multiple threads iterating over same list but I'm not sure if this is what you are looking for, because:

> A thread-safe variant of ArrayList in which all mutative operations (add, set, and so on) are implemented by making a fresh copy of the underlying array.

Which means that all changes to the list will not be visible to threads that are already iterating over it (should be fine for you unless list is not exactly what you want). From your short description I understood that you are looking for a collection which will hold some objects and you want to have multiple threads accessing this collection and polling objects one after another for some kind of processing. If my assumption is correct then you should implement this kind of functionality using a Queue rather than List (for example a [BlockingQueue][]).

[https://stackoverflow.com/questions/23040550/how-to-access-list-of-lists-concurrently?r=SearchResult][https_stackoverflow.com_questions_23040550_how-to-access-list-of-lists-concurrently_r_SearchResult]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzMyNDQ3MzIx_size_16_color_FFFFFF_t_70]: /images/20230528/27cc1f20b80544eca56bbdc3f5137bb8.png
[CopyOnWriteArrayList]: https://www.cnblogs.com/myseries/p/10877420.html
[Link 1]: https://www.cnblogs.com/yan456jie/p/5369366.html
[Link 2]: https://www.cnblogs.com/deky97/p/11024527.html
[https_www.codejava.net_java-core_collections_understanding-collections-and-thread-safety-in-java]: https://www.codejava.net/java-core/collections/understanding-collections-and-thread-safety-in-java
[AtomicStampedReference_ABA]: https://www.cnblogs.com/princessd8251/articles/5187403.html
[BlockingQueue]: http://docs.oracle.com/javase/7/docs/api/java/util/concurrent/BlockingQueue.html
[https_stackoverflow.com_questions_23040550_how-to-access-list-of-lists-concurrently_r_SearchResult]: https://stackoverflow.com/questions/23040550/how-to-access-list-of-lists-concurrently?r=SearchResults