Java thread-safe collection for a get-size-and-delete-element pattern

Question

I have a list of strings shared between a number of threads. Each thread has to:

access the list (for example via a getter method);
get the size of the list;
choose a random number n between zero and list.size();
extract the element at offset n from the list;
delete the extracted element from the list;
"save" the list back so that other threads view always the updated list

Since there is a concurrent access to a mutable shared object (the list), I need to code in a thread-safe way. Each thread has to diminish the list size by one and for this reason every other thread access must see a shorter list. My aim is to avoid a thread can see the same list seen by another thread, because in this way there is the possibility that the same element could be extracted twice.

Which is the best way to accomplish this? I was thinking about CopyOnWriteArrayList but I'm not sure it behaves like I need.

Thank you

assylias · Accepted Answer · 2013-01-08 07:09:01Z

The problem is that operations 1 to 6 need to be atomic and using a CopyOnWriteArrayList won't solve that.

One solution is to simply synchronize the whole operation:

private final List<String> list = new ArrayList<String> (); public String getNextItem() { synchronized(list) { //get the string adn remove it from the list } return next; }

Alternatively, you could review your algorithm and do something like:

create the list
shuffle it (to introduce randomness)
populate a BlockingQueue with that list (for example a LinkedBlockingQueue)
have your threads take items from the queue (thread safe atomic operation => no additional synchronization required)

the BlockingQueue approach seems simpler, because then I would have no need to save back an updated version of the list. Thank you

Adrian Shum · Accepted Answer · 2013-01-08 07:09:10Z

I don't see any reason why you cannot put the above sequence of logic in a synchronize block, or using semaphore/mutex for exclusive access to list during the above sequence of logic.

Collectives™ on Stack Overflow

Java thread-safe collection for a get-size-and-delete-element pattern

2 Answers 2

2 Comments

Comments

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

2 Comments

Comments

Related