Java并发 – 改进了读取时复制集合
我有一个multithreading应用程序，其中共享列表具有写入，偶尔读取行为。
具体来说，许multithreading会将数据转储到列表中，然后 – 稍后 – 另一个工作人员将获取快照以持久存储到数据存储区。
这类似于对这个问题的讨论。
在那里，提供了以下解决方案：
class CopyOnReadList { private final List items = new ArrayList(); public void add(T item) { synchronized (items) { // Add item while holding the lock. items.add(item); } } public List makeSnapshot() { List copy = new ArrayList(); synchronized (items) { // Make a copy while holding the lock. for (T t : items) copy.add(t); } return copy; } } 但是，在这种情况下，（并且，正如我从这里的问题中学到的），在任何给定时间只有一个线程可以写入支持列表。
有没有办法允许高并发写入后备列表，只有在makeSnapshot()调用期间才会锁定？
synchronized（~20 ns）非常快，即使其他操作可以允许并发，它们也可能更慢。
private final Lock lock = new ReentrantLock(); private List items = new ArrayList (); public void add(T item) { lock.lock(); // trivial lock time. try { // Add item while holding the lock. items.add(item); } finally { lock.unlock(); } } public List makeSnapshot() { List copy = new ArrayList (), ret; lock.lock(); // trivial lock time. try { ret = items; items = copy; } finally { lock.unlock(); } return ret; } public static void main(String... args) { long start = System.nanoTime(); Main ints = new Main<>(); for (int j = 0; j < 100 * 1000; j++) { for (int i = 0; i < 1000; i++) ints.add(i); ints.makeSnapshot(); } long time = System.nanoTime() - start; System.out.printf("The average time to add was %,d ns%n", time / 100 / 1000 / 1000); }
版画
The average time to add was 28 ns
这意味着如果您每秒创建3000万个条目，您将有一个线程平均访问该列表。 如果您每秒创建6000万，那么您将遇到并发问题，但此时您可能会遇到更多的资源问题。
当争用率较高时，使用Lock.lock（）和Lock.unlock（）会更快。 但是，我怀疑你的线程将花费大部分时间来构建要创建的对象，而不是等待添加对象。
您可以使用ConcurrentDoublyLinkedList 。 这里有一个很好的实现ConcurrentDoublyLinkedList 。
只要你在制作快照时在列表中向前迭代，一切都应该很好。 此实现始终保留前向链。 后向链有时是不准确的。
首先，你应该调查这是否真的太慢了。 添加到ArrayList在幸福的情况下是O(1) ，因此如果列表具有适当的初始大小，则CopyOnReadList.add基本上只是一个边界检查和对数组槽的赋值，这非常快。 （请注意，请记住CopyOnReadList编写是可以理解的，而不是CopyOnReadList 。）
如果您需要非锁定操作，可以使用以下内容：
class ConcurrentStack { private final AtomicReference> stack = new AtomicReference<>(); public void add(T value){ Node tail, head; do { tail = stack.get(); head = new Node<>(value, tail); } while (!stack.compareAndSet(tail, head)); } public Node drain(){ // Get all elements from the stack and reset it return stack.getAndSet(null); } } class Node { // getters, setters, constructors omitted private final T value; private final Node tail; }
请注意，虽然添加到此结构应该很好地处理高争用，但它有几个缺点。 来自drain的输出迭代非常慢，它使用了相当多的内存（就像所有链接列表一样），并且你也得到相反的插入顺序。 （另外，它并没有真正经过测试或validation，实际上可能会在您的应用程序中出现问题。但是，使用来自intertubes上的一些随机数据的代码总是存在风险。）
是的，有办法。 如果你知道的话，它类似于ConcurrentHashMap的方式。
对于所有写入线程，您应该从一个列表中创建自己的数据结构，但是使用多个独立列表。 每个这样的列表都应该由它自己的锁保护。 .add（）方法应该根据Thread.currentThread.id选择追加当前项目的列表（例如，只有id％listsCount）。 这将为.add（）提供良好的并发属性 – 充其量，listsCount线程将能够在没有争用的情况下进行写入。
在makeSnapshot（）上，您应该遍历所有列表，并为每个列表抓取它的锁定和复制内容。
这只是一个想法 – 有很多地方可以改进它。
您可以使用ReadWriteLock允许多个线程并行地在备份列表上执行添加操作，但只有一个线程可以创建快照。 正在准备快照时，所有其他添加和快照请求都将被暂停。
ReadWriteLock维护一对关联的锁，一个用于只读操作，另一个用于写入。 只要没有写入器，读锁定可以由多个读取器线程同时保持。 写锁是独占的。
class CopyOnReadList { // free to use any concurrent data structure, ConcurrentLinkedQueue used as an example private final ConcurrentLinkedQueue items = new ConcurrentLinkedQueue (); private final ReadWriteLock rwLock = new ReentrantReadWriteLock(); private final Lock shared = rwLock.readLock(); private final Lock exclusive = rwLock.writeLock(); public void add(T item) { shared.lock(); // multiple threads can attain the read lock // try-finally is overkill if items.add() never throws exceptions try { // Add item while holding the lock. items.add(item); } finally { shared.unlock(); } } public List makeSnapshot() { List copy = new ArrayList (); // probably better idea to use a LinkedList or the ArrayList constructor with initial size exclusive.lock(); // only one thread can attain write lock, all read locks are also blocked // try-finally is overkill if for loop never throws exceptions try { // Make a copy while holding the lock. for (T t : items) { copy.add(t); } } finally { exclusive.unlock(); } return copy; } }
编辑：
读写锁是如此命名的，因为它基于读者编写者的问题，而不是如何使用它。 使用读写锁，我们可以让多个线程实现读锁，但只有一个线程专门实现写锁。 在这种情况下，问题是相反的 – 我们希望多个线程写入（添加）并且只需要线程来读取（制作快照）。 因此，我们希望多个线程使用读锁定，即使它们实际上是在变异。 即使快照只读取，只有线程使用写锁定专门创建快照。 独占意味着在制作快照期间，其他线程不能同时为其他线程提供服务。
正如@PeterLawrey指出的那样，Concurrent队列将序列化写入aql虽然锁将尽可能少地使用。 我们可以自由使用任何其他并发数据结构，例如ConcurrentDoublyLinkedList 。 该队列仅用作示例。 主要思想是使用读写锁。