question about threads
I wrote a small multithreaded program, each thread had access to the same ArrayList. They did their calculations and added the results to the ArrayList. Here is some sample code of what I am talking about.
import java.util.*;
publicclass Xextends Thread
{
privatestatic ArrayList data =new ArrayList();
publicstaticvoid main(String[]args)
{
//keep track of how many threads there were before more were started
int numRestingThreads = Thread.activeCount();
//spawn a few threads and have them add to data
for(int i=0; i<10; i++)
{
X newThread =new X();
newThread.start();
}
//wait for all threads to finish
while(Thread.activeCount() > numRestingThreads)
{
Thread.yield();
}
//see if everything was added correctly
for(int i=0; i<data.size(); i++)
{
System.out.println(data.get(i));
}
}//main
//add something to the list
publicvoid run()
{
data.add(new String("somedata"));
}//run
}//class
I was wondering, is it conceivable that with the instruction "data.add(...)" could get interrupted in mid-instruction? I imagine that the add method for an ArrayList can be decomposed into several intermediate instructions for the JVM. But, if that instruction was interrupted by another thread becoming active, wouldn't the ArrayList become malformed, since one thread was trying to update it and another thread interrupted it in the middle of that? Or is the add method atomic?>
[2842 byte] By [
ericodea] at [2007-11-26 16:00:23]
You should wrap the ArrayList in a synchronizedList:
private static List data = Collections.synchronizedList(new ArrayList());
You then need to synchronize the iteration (e.g., where you print the values), but adding will be synchronized automatically. Look up the synchronizedList method for details.
Also, if your items really are Strings, you don't need "new String(...)". Just use the String literal directly:
data.add("somedata");
Are you refering to Thread's [url=http://java.sun.com/j2se/1.5.0/docs/api/java/lang/Thread.html#interrupt()]interrupt[/url] method? Unless you are talking about interrupting methods like wait, join or sleep, all that happens is that the thread's interrupt status flag is set. In you case, the add method continues merrily on.
Woops! stared at your code harder this time. You are misusing the term "interrupt". What you have is threads that could concurrently access the same ArrayList. As the other poster metioned, you need to synchronized access or use a collection built for concurrent access, like [url=http://java.sun.com/j2se/1.5.0/docs/api/java/util/concurrent/ConcurrentLinkedQueue.html]ConcurrentLinkedQueue[/url].
Something I should add to my original post is that this is just a simplified example of a larger program that I wrote. The larger program would maintain around 100 threads running, each adding to the ArrayList that was shared by them. It did not matter in what order values were added to the ArrayList for the program to work.
I will have to study the Collections.synchronizedList method in more detail.
The larger program I was referring to never had any exceptions that indicated the list became malformed in the course of thread switching (switching of which thread was currently active, not "interrupting" like I mistakenly said in the first post). My question is: why didn't my program ever result in a malformed list due to the fact that the list was not synchronized?
> My question is:
> why didn't my program ever result in a malformed list
> due to the fact that the list was not synchronized?
The list wouldn't necessarily be malformed. You could lose data if two threads added to the ArrayList at the same time. If two threads called "add" at the same time, both threads would write a new element by saying (for example):
arrayUnderlyingTheArrayList[counter] = theNewElementAdded;
counter++;
So, if threadA executed the first line and then threadB executed the first line, and then threadA executed the second line and then threadB executed the second line, you'd have:
[Assume counter was 4 to begin with--the array had 5 elements so far.]
arrayUnderlyingTheArrayList[4] = elementFromThreadA;
arrayUnderlyingTheArrayList[4] = elementFromThreadB;
counter = 5;
counter = 6;
Then the next "add" would go in element #6, and element #5 would stay empty. Furthermore, you lost the "elementFromThreadA" because threadB overwrote it. If the first "add" caused the ArrayList to resize itself, you'd likely have even more disastrous results.
Using synchronizedList correctly will eliminate the possibility that the above will happen.
Yes, that makes sense. I will try to make a test program to see if I can get that to happen (lose an element when it should have been added to a list).
> Yes, that makes sense. I will try to make a test
> program to see if I can get that to happen (lose an
> element when it should have been added to a list).
I don't know a good way to force the error to occur. So, it might take a while for you to see it (although it might already have occurred without your noticing). Even if you test and don't see it occurring, you should still fix your code to make sure that it cannot occur.
I think I made a suitable test program and have results that indicate that the error does occur.
import java.util.*;
public class ThreadSafetyCheck extends Thread
{
private static ArrayList data= new ArrayList();
private int id;
public ThreadSafetyCheck(int param)
{
id = param;
}
public static void main(String[]args)
{
int numThreads = Integer.parseInt(args[0]);
int iterations = Integer.parseInt(args[1]);
int numIdleThreads = Thread.activeCount();
for(int idnum=0; idnum<iterations;)
{
for(int i=0; i><numThreads && idnum><iterations; i++)
{
//start up a bunch of threads
ThreadSafetyCheck x = new ThreadSafetyCheck(idnum);
x.start();
idnum++;
}
}
//wait for threads to finish adding to data
while(Thread.activeCount() > numIdleThreads)
{
Thread.yield();
}
//now print sum and expectation of sum
int sum=0;
for(int i=0; i<data.size(); i++)
{
sum+=((Integer)data.get(i)).intValue();
}
System.out.println("Expected size of list: " + iterations);
System.out.println("Actual size of list:" + data.size());
System.out.println("Expected sum of list: " + (iterations-1)*iterations/2);
System.out.println("Actual sum of list:" + sum);
}//main
public void run()
{
data.add(new Integer(id));
}
}//class
ode]
output from running it:
$ java ThreadSafetyCheck 150 3000
Expected size of list: 3000
Actual size of list:2994
Expected sum of list: 4498500
Actual sum of list:4493553
$ java ThreadSafetyCheck 150 3000
Expected size of list: 3000
Actual size of list:3000
Expected sum of list: 4498500
Actual sum of list:4498500
$
Message was edited by:
ericode>
> //wait for threads to finish adding to data
> while(Thread.activeCount() > numIdleThreads)
> {
> Thread.yield();
> }
The code does not necessarily do what the comment says it does. If you want to wait for the threads to finish, you'd use the Thread.join method.
