I have a multi-threaded application that has a centrlaised list that is updated (written to) only by the main thread. I then have several other threads that need to periodically retrieve the list in its current state. Is there a method that can allow me to do this?
1
-
What version of the JDK are you using? If 1.5+ then there are some default data structures which do this for you, see the Javadoc.Martijn Verburg– Martijn Verburg2010-10-15 14:36:32 +00:00Commented Oct 15, 2010 at 14:36
Add a comment
|
6 Answers
That depends on how you want to restrict the concurrency. The easiest way is probably using CopyOnWriteArrayList. When you grab an iterator from it, that iterator will mirror how the list looked at the point in time when the iterator was created - subsequent modifications will not be visible to the iterator. The upside is that it can cope with quite a lot of contention, the drawback is that adding new items is rather expensive.
The other way of doing is locking, the simplest way is probably wrapping the list with Collections.synchronizedList and synchronizing on the list when iterating.
A third way is using some kind of BlockingQueue and feed the new elements to the workers.
Edit: As the OP stated only a snapshot is needed, CopyOnWriteArrayList is probably the best out-of-the-box alternative. An alternative (for cheaper adding, but costlier reading) is just creating a copy of a synchronizedList when traversion is needed (copy-on-read rather than copy-on-write):
List<Foo> originalList = Collections.synchronizedList(new ArrayList());
public void mainThread() {
while(true)
originalList.add(getSomething());
}
public void workerThread() {
while(true) {
List<Foo> copiedList;
synchronized (originalList) {
copiedList = originalList.add(something);
}
for (Foo f : copiedList) process(f);
}
}
Edit: Come to think of it, the copy-on-read version could simplified a bit to avoid all synchronized blocks:
List<Foo> originalList = Collections.synchronizedList(new ArrayList());
public void mainThread() {
while(true)
originalList.add(getSomething());
}
public void workerThread() {
while(true) {
for (Foo f : originalList.toArray(new Foo[0]))
process(f);
}
}
Edit 2: Here's a simple wrapper for a copy-on-read list which doesn't use any helpers, and which tries to be as fine-grained in the locking as possible (I've deliberately made it somewhat excessive, bordering on suboptimal, to demonstrate where locking is needed):
class CopyOnReadList<T> {
private final List<T> items = new ArrayList<T>();
public void add(T item) {
synchronized (items) {
// Add item while holding the lock.
items.add(item);
}
}
public List<T> makeSnapshot() {
List<T> copy = new ArrayList<T>();
synchronized (items) {
// Make a copy while holding the lock.
for (T t : items) copy.add(t);
}
return copy;
}
}
// Usage:
CopyOnReadList<String> stuff = new CopyOnReadList<String>();
stuff.add("hello");
for (String s : stuff.makeSnapshot())
System.out.println(s);
Basically, when you to lock when you:
- ... add an item to the list.
- ... iterate over the list to make a copy of it.
8 Comments
jilles de wit
+1 CopyOnWriteArrayList is the way to go from what I see in the question. BlockingQueue makes no sense given the question.
Andy Thomas
+1 - good summary. A simpler way to do it with locking is to return an O(n) copy of the list on request. The synchronized list approach requires that both your class and all recipients of the list access the list through the synchronized wrapper; and iterations require synchronizing on the list.
pie154
Would I need to synchronise the writes as well for this list? Could i possibly get a smaple of the write process?
gustafc
You mean for the copy-on-read version? Yes, all the writes need synchronization. So if you declared
List<Foo> originalList = new ArrayList<Foo>() you'd have to do the add call in a synchronized (originalList) block. However, if you wrap the original list with synchronizedList as I do, all individual method calls on that list are synchronized.gustafc
I updated the copy-on-read example to take maximum advantage of
synchronizedList and avoid explicit synchronization. |
You can consider using a read - write lock mechanism. If your JDK version is 1.5 or newer, you can use ReentrantReadWriteLock.
Comments
Take a look at Java's Concurrency Package. There should be something there you can use.
Do the child threads need read only access? Do the just need an item of the top of the list? How is the list being used, might help us understand your problem better, and point you in a clearer direction.
To pass a snapshot of the list, just create a new List populated by the original list.
List<Object> newList;
synchronize (originalList)
{
newList = new ArrayList<Object>(originalList);
}
return newList;
Synchronized may or may not be beneficial here. I'm not sure.
5 Comments
pie154
The child threads need a snapshot of the whole list at the point in time they read it.
tylermac
A snapshot can be made by passing a new list with the same elements. Updated answer with an example.
sjlee
Synchronization is most definitely needed in this. And the writes need to be synchronized. The copy constructor does an iteration of the original list, and if the original list is modified while the copy is made, you will get a ConcurrentModificationException.
pie154
@sjlee how would i synchronise the writes to the list?
sjlee
It just means that write operations need to acquire the same lock (originalList itself in the above example). Gustafc's code is one example.
If the threads are only "reading" the list you're safe with just using List. If the list is going to be "written to" (get changed in any way) use Vector instead of List.
Comments
If you simply want a read-only snapshot and the list is not too large:
private static List<TypeHere> getCurrentList() {
/* code to return the list as it currently is */
}
public static List<TypeHere> snapshot() {
TypeHere[] objects = getCurrentList().toArray(new TypeHere[] {});
return Collections.unmodifiableList(Arrays.asList(objects));
}
2 Comments
Andy Thomas
It's a multi-threaded application. Perhaps some synchronization would be useful here?
Andrzej Doyle
toArray() isn't going to be threadsafe if the underlying list isn't, and since this is presumably a thread-safe wrapper class for arbitrary lists it's not going to work. Alternatively, if you require the underlying list to have the desired concurrency semantics anyway, I don't see what this wrapper is adding.If the write is not frequent and the data size is small, the CopyOnWriteArrayList is a great choice. Otherwise, your write performance may be an issue.
If you do not need a full List interface (mainly the random access via index), then you have more options. If your use case is satisfied with the Queue interface, then things like ConcurrentLinkedQueue would be an excellent choice. If you can live with the Queue interface, then something like this becomes possible:
Queue<Foo> originalList = new ConcurrentLinkedQueue<Foo>();
public void mainWrite() {
// main thread
originalList.add(getSomething()); // no locking needed
}
public void workerRead() {
// executed by worker threads
// iterate without holding the lock
for (Foo f: originalList) {
process(f);
}
}
