Elegir la mejor lista de concurrencia en Java

Mi grupo de subprocesos tiene un número fijo de subprocesos. Estos hilos necesitan escribir y leer con frecuencia de una lista compartida.

Entonces, ¿qué estructura de datos (mejor sea una lista, debe estar libre de monitores) en el paquete java.util.concurrent es la mejor en este caso?

sería mejor que List

La única implementación de List en java.util.concurrent es CopyOnWriteArrayList . También existe la opción de una lista sincronizada como menciona Travis Webb.

Dicho eso, ¿estás seguro de que necesitas que sea una List ? Hay muchas más opciones para las Queue y los Map simultáneos (y puede hacer que Set de Map s), y esas estructuras tienden a tener más sentido para muchos de los tipos de cosas que desea hacer con una estructura de datos compartida. .

Para las colas, tiene una gran cantidad de opciones y cuál es la más adecuada depende de cómo debe usarla:

  • ConcurrentLinkedQueue
  • ArrayBlockingQueue
  • LinkedBlockingDeque
  • LinkedBlockingQueue
  • PriorityBlockingQueue
  • SynchronousQueue
  • DelayQueue

Se puede hacer que cualquier colección de Java sea Thread-safe como esta:

List newList = Collections.synchronizedList(oldList);

O para crear una nueva lista segura para subprocesos:

List newList = Collections.synchronizedList(new ArrayList());

http://download.oracle.com/javase/6/docs/api/java/util/Collections.html#synchronizedList(java.util.List)

Si el tamaño de la lista es fijo, entonces puede usar un AtomicReferenceArray . Esto le permitiría realizar actualizaciones indexadas a un espacio. Puede escribir una vista de Lista si es necesario.

Es posible que desee ver ConcurrentDoublyLinkedList escrito por Doug Lea basado en “Una lista doblemente unida práctica Lock-Free” de Paul Martin. No implementa la interfaz java.util.List, pero ofrece la mayoría de los métodos que usaría en una lista.

De acuerdo con el javadoc:

Una implementación de lista vinculada simultánea de una Deque (cola de doble final). Las operaciones concurrentes de inserción, eliminación y acceso se ejecutan de manera segura en varios subprocesos. Los iteradores son débilmente consistentes y devuelven elementos que reflejan el estado de la deque en algún punto en o desde la creación del iterador. No lanzan ConcurrentModificationException, y pueden proceder al mismo tiempo que otras operaciones.

ConcurrentLinkedQueue utiliza una cola libre de locking (basada en la instrucción CAS más nueva).

Si el conjunto es suficiente, se puede usar ConcurrentSkipListSet . (Su implementación se basa en ConcurrentSkipListMap que implementa una lista de omisiones ).

El costo promedio de tiempo esperado es log (n) para las operaciones contains, add y remove; el método de tamaño no es una operación de tiempo constante.